n 차원 공간에서 k- 가장 가까운 값을 찾으려면 어떻게해야합니까?

Question

kd-trees에 대해 읽었지 만 공간의 차원이 높으면 비효율적입니다. 나는 가치있는 데이터베이스를 가지고 있으며, 쿼리의 특정 해밍 거리 내에있는 값을 찾고 싶다. 예를 들어, 데이터베이스는 32 비트 숫자 목록이며 쿼리 값과 다른 모든 숫자를 3 비트 미만으로 찾고 싶습니다.

나는 MultiVariate 파티션 트리에 대해 들었지만 좋은 참조를 찾을 수 없었다. 나는 min-Hash가 좋은 근사치를 제공한다는 것을 알고 있지만, 정확한 답을 원합니다.

Answer 1

해밍 거리는 levenshtein distance과 밀접한 관련이 있으며 맞춤법 교정에 사용되는 알고리즘과 유사합니다.

작동 방법은 trie에서 branch-and-bound 검색입니다. 거리가 가까울수록 사전 크기가 선형이 될 때까지 지수 함수적인 시간이 걸립니다.

walk(trie, word, i, hit, budget){ 
    if (budget < 0 || i > word.length) return; 
    if (trie==NULL){ 
    if (i==word.length) print hit; 
    return; 
    } 
    hit[i] = 0; 
    walk(trie.subtrie[0], word, i+1, hit, (word[i]==0 ? budget : budget-1)); 
    hit[i] = 1; 
    walk(trie.subtrie[1], word, i+1, hit, (word[i]==1 ? budget : budget-1)); 
} 

main(){ 
    for (int budget = 0; ; budget++){ 
    walk(trie, word, 0, hit, budget); 
    /* quit if enough hits have been printed */ 
    } 
} 

아이디어는 당신이 추적하는 전체 트라이을 도보 : 사전 엄격한 해밍 거리 이진 트라이에 저장된 이진 단어 인 경우

, 여기에 간단한 의사 코드 현재 트라이 노드와 원래 단어 사이의 거리. 얼마만큼의 거리를 허용 할 것인지 예산을 세우면 검색이 생략됩니다. 이것은 당신이 트라이 깊숙이 갈수록 거리가 줄어들 수 없기 때문에 가능합니다.

그런 다음 원하는 히트를 인쇄 할 때까지 예산을 0에서 시작하여 단계적으로 늘리면됩니다. 각 보행은 후속 보행보다 훨씬 적은 수의 노드를 다루기 때문에 다중 보행을하는 것이 아 닙니다. k이 수정 된 경우 간단히 예산으로 시작할 수 있습니다.