다른 점에서 가장 가까운 점을 효율적으로 찾을 수 있습니다.

Question

~ 10.000 점의 좌표 (십진법의 latitute, longitute) 목록과 ~ 100 만 점의 동일한 유형 좌표의 두 번째 목록 B가 있습니다.

나는 목록 B.의 각 요소에 대한 목록 A의 가장 가까운 지점을 찾으려면

내가 이미 수행 한 것은 두 목록의 직교 제품을 만들고 하버 사인을 사용하는 모든 조합의 거리를 찾을 수있다 공식. 총 조합이 10 개 이상의 억, 거리를 계산하는 데 걸리는 시간이 너무 긴 때문에

은 그 때 나는 목록 B.

의 각 포인트의 최소 거리가 목록 A의 포인트를 얻을.

목록 B의 모든 점이 목록 A의 점과 일치하지만 성능을 향상시킬 수있는 방법이 있습니까?

Answer 1

이미 교차 제품을 작성하고 haversine 거리를 계산 한 적이 있다면 이미 대부분의 작업을 완료 했으므로 새로운 세트 A 및 B가있는 경우 어떻게해야하는지에 대한 질문이 있다고 가정합니다

인공 지능에서 가장 가까운 점을 반복적으로 찾으려면 A에 점을 포함하는 일종의 트리 구조를 만들고 트리의 각 노드에 정보를 저장합니다.이 정보는 바운딩 박스 또는 그 자손을 모두 포함하는 등가물에 해당합니다. 그런 다음 A에서 가장 가까운 점을 찾으려고하면 A를 포함하는 트리를 재귀 적으로 검색하여 노드에 도달했을 때 재귀 호출에서 돌아오고 거기에 저장된 정보를 바탕으로 모든 자손이 대상 점에서 멀리 떨어져 있음을 확인할 수 있습니다 지금까지 가장 가까운 성냥보다.

이 코드를 사용하려면 바운딩 박스 정보가 정확해야하지만 나무가 어리석은 경우 검색 속도가 느려지지만 정답을 찾을 수 없습니다. 이것은 특히 나무를 만들 때 180W = 180E로 감싸는 경시의 불편한 습관을 무시할 수 있다는 것을 의미합니다. lat-long은 직사각형 격자이고 kd 트리를 구성하고 위도와 경도를 결합하여 비트 인터리브하고 결과에 1 차원 검색 트리를 만들 수 있다고 가정하면 https://en.wikipedia.org/wiki/Geohash을 계산하고 검색 트리를 작성할 수 있습니다 이것을 바탕으로, 또는 당신은 haversine을 많이 계산하고 https://en.wikipedia.org/wiki/Cover_tree을 만들 수 있습니다 -이 모든 것이 효과가 있고 어떤 것이 가장 좋을지 모르겠다 - 그것은 당신이 가지고있는 당신의 자료와 도서관에 달려 있을지도 모른다.

Answer 2

spatstat 패키지의 nncross 함수를 사용하여 두 개의 서로 다른 데이터 세트의 점 거리를 찾을 수 있습니다.이 함수를 사용하면 시간이 많이 걸릴 것입니다. https://www.rdocumentation.org/packages/spatstat/versions/1.53-2/topics/nncross