N- 차이에서 점 사이의 거리를 결정합니다

Question

N- 차이에서 MySQL 테이블 목록 포인트를 구축하고 있으며 각 차원은 색인화됩니다. N 차원 시스템의 어느 지점을 고려할 때, 나는 선택한 지점과의 거리에서 다른 모든 지점을 출력 할 수 있기를 원합니다.

간단한 해결책은 피타고라스 정리를 사용하여 각 지점의 거리를 계산하는 것입니다 ... SQRT (x^2+y^2) = z. 나는보다 효율적인 방법을 찾고 있습니다. 대략적인 순서 만 필요하므로 매우 열린 마음이 있습니다.

감사.

-속이다

Answer 1

주어진 것과 함께, 당신은 또한 당신의 포인트를 "binning"하는 것을 고려할 수도 있습니다. 즉, (적어도 정신적으로) "지도"에 그리드를 그려서 어떤 정사각형에 기반한 지점을 추적 할 수 있습니다. 기본적으로, 당신은 같은 정사각형의 지점으로 시작한 다음 선택한 지점의 정사각형을 둘러싼 "링", 다음 링은 바깥쪽으로 시작됩니다. 사용하는 그리드의 크기에 따라 원하는만큼 정확하거나 근사 할 수 있습니다. 물론 2D 그리드는 2D 포인트입니다. 더 많은 치수가있는 경우 그리드의 차원을 일치시켜야합니다.

Answer 2

이런 종류의 일반적인 기술은 제곱근을 제거하는 실제 거리 대신 제곱 거리를 고려하는 것입니다. 그러나 질문을 올바르게 이해하고 있다면 인덱스에서 실제 거리를 검색 할 필요가 없습니다. 이 경우 각 구성 요소의 절대 값의 합을 사용할 수 있습니다.