그래프 DB를 사용하여 PHP로 위치 간 거리 저장

Question

주어진 대상에 대해 n 개의 가장 가까운 대상을 신속하게 찾고 n 개 대상에 대한 n x n 거리 매트릭스 및 두 개 이상의 대상 간 거리와 관련된 여러 가지 기타 연산을 계산할 수 있어야합니다.

그래프 DB는 MySQL 데이터베이스에 비해 훨씬 우수한 성능을 제공한다는 것을 알게되었습니다. 내 응용 프로그램은 PHP로 작성되었습니다.

내 질문에 - PHP 응용 프로그램에서 그래프 DB를 사용할 수 있습니까? 그렇다면 어느 것이 가장 좋은 옵션이고 오픈 소스이며이 데이터를 그래프 DB에 저장하는 방법과 어떻게 액세스 할 수 있습니까?

미리 감사드립니다.

Answer 1

Neo4j은 매우 견고한 그래프 DB이며 유연한 (조금 복잡한 경우) 라이센스가 있습니다. Blueprints API를 구현하며 PHP를 비롯한 모든 언어에서 사용하기가 쉽습니다. 그것은 또한 REST API을 가지고 있습니다. 이것은 얻을 수있는만큼 융통성이 있으며, 적어도 PHP에서는 one good example이 사용됩니다.

보유하고있는 데이터에 따라 데이터를 저장하는 방법에는 여러 가지가 있습니다.

포인트가 이미 특정 경로를 통해 서로 연결되어있는 (즉, 한 지점에서 다른 지점으로 직접 이동할 수없는) "경로"데이터가있는 경우 각 지점을 노드로 만들고 경로상의 점 사이에있는 연결은 노드 사이의 가장자리이며 해당 가장자리의 속성으로 거리가 있습니다. 이렇게하면 고전적인 "여행 세일즈맨"처럼 보이는 그래프를 얻을 수 있으며 노드 간의 거리를 계산하는 것은 가중치가있는 폭 우선 검색을 수행하는 것입니다 (최단 경로를 원한다고 가정).

데이터 세트가있는 곳으로 이동하려는 경우 그래프가 fully connected입니다. 분명히 이것은 많은 양의 데이터이고 더 많은 목적지를 추가 할 때 2 차적으로 커지지만 관계형 DB보다 그래프 DB가 더 잘 처리 할 것입니다. 거리를 저장하려면 그래프에 노드를 추가 할 때 노드의 속성 중 하나로서 미리 계산 된 거리를 사용하여 기존 노드 각각에 가장자리를 추가합니다. 그런 다음 한 쌍의 노드 사이의 거리를 검색하려면 두 노드 사이의 가장자리를 찾고 거리 속성을 가져옵니다. 당신이 완전히 연결된 노드의 큰 수있는 경우

그러나, 당신은 아마 그 노드의 좌표를 저장하고 필요에 따라-의 거리를 계산하고, 선택적으로 일을 가속화하는 결과를 캐싱 더 나을 것 . 당신이 Gremlin 및 Rexter 같은 청사진 API와 그 스택의 다른 도구를 사용하는 경우

마지막으로, 당신은 당신이 다른 구현 함께 놀러 수/아웃 어떤 호환 그래프 데이터베이스에서 교환 할 수 있어야 을 Cassandra/Hadoop 클러스터 상단에 사용하는 등 더 나은 서비스를 제공 할 수 있습니다.

Answer 2

예, 그래프 데이터베이스는 MySQL의 확장 기능보다 성능이 뛰어납니다. 그렇지 않으면 Postgres에서 수행 할 수 있습니다. 하나는 looks really slick이며, 전송 계층으로 beta implementation in PHP using the binary protocol과 another one that uses HTTP이 있습니다.

( odino.org에서) 예제 코드 알레산드로로서는

는 full explanation of how to use it with OrientDB to find the minimum distance between cities 함께 Dijkstra's algorithm의 implementation 썼다.

Answer 3

실제로 인덱스와 관련하여 데이터베이스에 관해서 그다지 중요하지 않습니다. 필자는 MongoDB의 geospatial indexing과 검색 (문서 DB)을 사용했으며, 여기에는 주어진 좌표에 가장 가까운 여러 요소를 찾기 위해 설계된 지오 인덱스가 있습니다. 좋은 결과가 있습니다. 여전히 - 단순한 쿼리 만 실행하고 (가장 가까운 것을 찾습니다) 인덱스가 RAM에 맞지 않으면 약간 느려집니다 (좌표가있는 8MBn 위치의 geonames DB를 사용했으며 VM의 쿼리 당 0.005-2.5s를 가졌습니다 - 1. 하드 디스크 오버 헤드 2. 아마도 인덱스가 RAM에 맞지 않습니다.