5 백만개의 요소 카탈로그에있는 각 요소에 대한 3D 유클리드 공간에서 가장 가까운 10 개의 점 찾기

Question

3D 공간에서 x, y, z 위치와 함께 5 백만 점의 카탈로그가 있다고 가정합니다. 이 5 백만 점 중 각각에 대해 가장 가까운 10 점 (직선적 인 3 차원 유클리드 거리 공식)을 찾고 싶습니다.

파이썬에서 테이블의 모든 요소에 대해 간단한 for 루프를 수행하고 for 루프 내에서 현재 작업 좌표와 다른 모든 점 사이의 거리를 찾는 배열 연산 (두 번째 루프가 아닙니다!)을 수행합니다. 카탈로그에서 이것은 일/주 걸릴 것입니다. 저는 정렬과 점 사이의 거리 계산에 관련된 몇 가지 작업을 시도했습니다. +/- 각 테이블 요소 둘레의 몇 천 개의 행이지만, 여전히 일 걸릴 것입니다.

파이썬에서이 작업을 수행하는 더 빠른 방법은 무엇입니까? for 루프를 일종의 벡터화 된 연산으로 변환 할 수있는 방법이 있습니까? 어떤 기계 학습 기술 (예 : scikit-learn)이 도움이 될까요? 아니면 어떻게 든 코드를 병렬 처리하는 데 도움이 될까요?

Answer 1

R에서 "Approximate"가장 가까운 이웃을 찾는 패키지 된 RANN을 사용했습니다. 나는 25M 관측과 8 차원으로 몇 분 만에 달렸고 결과는 나의 유스 케이스에 충분했다. 내가 사용하는 패키지의 파이썬 버전이있는 경우

는 잘 모르겠지만, 나는 대안을 많이 가지고이 링크를 발견 : 즉 데이터의 차원을 감안할 때 Benchmark of ANN Libraries

Benchmark of ANN Libraries