En ny metod för k-nearest granne (k-NN) sökning med Euclidean metrisk beskrivs. Det är välkänt att många sofistikerade algoritmer inte kan slå brute-force algoritmen när dimensionaliteten är hög. I denna studie, en förmodligen korrekt metod, där rätt uppsättning av k-nearest grannar erhålls med hög sannolikhet, föreslås för att kraftigt minska söktiden. Vi utnyttjar den marginella fördelningen av kth närmaste grannar i låga dimensioner, som uppskattas från lagrade data (en empirisk percentil metod). Vi analyserar den grundläggande karaktären av marginaldistributionen och visar fördelen med den implementerade algoritmen, som är en probabilistisk variant av den partiella distanssökningen. Dess frågetid är sublinjär i datastorlek n, d.v.s. O (mnδ) med δ = o(1) i n och δ ≤ 1, för alla fasta mått m.
al, genom att utnyttja den marginella fördelningen av kth närmaste grannar i låga dimensioner, lägga fram en förmodligen korrekt strategi för kNN, vilket är en probabilistisk ändring av den partiella distans sökning REF.
Probably correct k-nearest neighbor search in high dimensions
{'venue': 'Pattern Recognit.', 'journal': 'Pattern Recognit.', 'mag_field_of_study': ['Computer Science', 'Mathematics']}