나는주기적인 경계 조건을 가진 D 차원 공간에 N 개의 점으로 이루어진 점 구름을 가지고 있습니다. 여기서 N은 500에서 10 ^ 8의 범위를 가질 수 있고 D는 1에서 20의 범위를 가질 수 있습니다. 점의 분포는 완전히 균일 한 것에서 매우 뭉친 것까지 매우 다양합니다. 함께. 포인트 클라우드의 각 포인트에 대해 해당 포인트에 가장 가까운 k 개의 이웃을 찾아야합니다. 또한 각 지점의 거리, 특히 maxnorm 거리 내에 얼마나 많은 지점이 있는지 찾아야합니다. 반경 내에 어떤 점이 있는지 알 필요는 없지만 얼마나 많은지 알 필요는 없지만 좋은 추가가 될 것입니다.
나는 kd-trees를 시도했지만 래핑 경계를 처리하지 않으며 더 큰 나무의 경우 복제가 가능하지 않습니다. 또한 더 높은 차원에서는 느려집니다.
Vantage Point Trees를 발견하고 코드를 시도했지만 kd-tree보다 느립니다. 내가 찾은 코드는 일괄 처리가없는 재귀 검색 방법을 사용하지만. 긍정적 인 측면 중 하나는 기본적으로 래핑 조건을 처리 할 수 있으므로 중복이 필요하지 않습니다.
반복적 접근 방식으로 변환하고 일괄 검색을 할 수 있는지 확인하여 VP 트리에서 더 많은 성능을 끌어낼 수 있는지 확인하려고합니다.하지만 생각이있었습니다. 이 모든 데이터 구조는 임의의 쿼리 포인트에 가장 가까운 이웃을 찾는 데 작동하지만 내 쿼리 포인트는 포인트 클라우드의 포인트로 제한됩니다. 이 제한은 좀 더 성능이 좋은 구조를 허용 할 수 있다고 생각합니다 (아마도 일종의 탐색 메시일까요?). 나는 이것을 처리 할 구조를 검색하려고 시도했지만 내 google-fu가 실패했습니다. 따라서 다음을 처리 할 수있는 데이터 구조를 아는 사람이 있는지 궁금합니다.
감사
당신의 매우 복잡한 문제에 대한 완전하고 확실한 답이 있을지 의심 스럽기 때문에 저는 제 생각을 공유합니다. 문제 사양은 함께 잘 작동하지 않는 여러 가지를 결합합니다 (높은 차원, 비 유클리드 메트릭, 완전히 다른 유형의 쿼리). 알고리즘이 일반적인 경우를 가정해야하는 경우 반드시 느립니다.
먼저 좋은 데이터 구조가 알려진 특수한 경우를 분류 해 보겠습니다.
이 모든 것이 적용되지 않는 경우 (실용적인 적용을 염두에두고있는 경우 당사와 공유하십시오) 귀하의 사례는 매우 일반적입니다.
언급 한 알고리즘 외에도 GNAT (Geometric Near-Neighbor Access Tree)를 사용해보아야합니다. http://infolab.stanford.edu/~sergey/near.html 일반 측정 항목 (귀하의 측정 항목 포함)에 적용되며 비 균일 분포도 처리합니다.
또한 여러분의 기대가 매우 높다고 생각합니다. 유클리드 메트릭으로 만 문제를 해결 하는 좋은 kd- 트리 구현 (예 : https://github.com/mariusmuja/flann ) 과 비교할 수 있습니다. 시간이 오래 걸리면보다 일반적인 메트릭이 더 빨리 해결 될 것으로 기 대해서는 안됩니다.
물론 더 일반적인 방법은 쿼리가 클라우드의 지점이라는 제약 조건을 사용할 수 없습니다. 그러한 해결책이 있다면 매우 관심이있을 것입니다.
이 기사는 인터넷에서 수집됩니다. 재 인쇄 할 때 출처를 알려주십시오.
침해가 발생한 경우 연락 주시기 바랍니다[email protected] 삭제
몇 마디 만하겠습니다