어떻게이 KD 트리를 만들 수 있습니까?

위도, 경도 및 시간대의 세 부분으로 구성된 매우 긴 반 정렬 목록이 있습니다. 주어진 위도와 경도에 가장 가까운 시간대를 찾기 위해이 목록을 빨리 검색 할 수 있기를 원합니다. 그래서이 목록을 KD 트리로 만들고 싶습니다.어떻게이 KD 트리를 만들 수 있습니까?

저는 전체 파일을 먼저 어떤 종류의 데이터 구조 (어떤 데이터 구조입니까? 아마도 ArrayList<Triplet<Double, Double, String>>?)로 읽어야한다고 생각합니다. 그런 다음 그 구조의 중간 요소를 가져 와서 루트로 만들고 왼쪽 및 오른쪽 목록을 남겨 둡니다. 그런 다음 각 목록의 중간 요소를 계속 가져 와서 왼쪽 또는 오른쪽 자식으로 추가하십시오.

이것에 첫번째 시도는 느리고 비효율적 인 것처럼 보였다 ... 그러나 나는 그것을 잘못한 것처럼 느낀다. 당신이 알고리즘이나 의사 코드를 제공해 줄 수 있습니까?

출처

2012-10-01 Kalina

KDTree에 궁금한 점이 있으면 알려주십시오. 여전히 느리고 비효율적이라면 알려주십시오. 나는 호기심있다! – Justin

구현을 Java-ML (http://java-ml.sourceforge.net/)의 KDTree 구현과 비교 했으므로 k 개의 가장 가까운 이웃을 추출하는 속도가 훨씬 느립니다. 귀하의 인터페이스가 더 멋지 네요 :) –

또한, 여기에 더 빠른 구현이 있습니다 : http://robowiki.net/wiki/Kd-tree#Implementations –

도움이된다면 XYZPoint라는 내부 클래스에서 XYZ를 두 배로 가져 오는 KD-Tree in Java이 있습니다. 시간대 데이터로 XYZ 지점을 확대하고 경도로 X, 위도로 Y를 사용하고 Z에서 Z를 사용할 수 있습니다. 최소한 출발점 일 수 있습니다.

그런 다음 가장 가까운 표준 시간대에 대해 이미 구현 된 가장 가까운 이웃 (유클리드 거리) 방법을 사용할 수 있습니다.

또한 KD 트리를 채우기 위해 wikipeda은 HeapSort (my Java implementation linked)을 사용하고 중간 값을 반복적으로 제거 할 것을 제안합니다.

출처

2012-10-01 01:08:58 Justin

어떻게이 KD 트리를 만들 수 있습니까?

답변

관련 문제