Vi presenterar en träddatastruktur för snabb grannverksamhet i allmänna npoint-metriska utrymmen (där datamängden består av n-punkter). Datastrukturen kräver O(n) utrymme oavsett metriska struktur men ändå upprätthåller alla prestanda egenskaper för ett navigating nät (Krauthmer & Lee, 2004b). Om punktuppsättningen har en begränsad expansionskonstant c, vilket är ett mått på den inneboende dimensionaliteten, enligt definitionen i (Karger & Ruhl, 2002), kan täckträdets datastruktur konstrueras i Oc 6 n log n tid. Dessutom kräver närmaste granne frågor endast tid logaritmisk i n, särskilt O c 12 log n tid. Våra experimentella resultat visar speedups över brute force sökning varierar mellan en och flera storleksordningar på naturliga maskininlärning dataset.
I Cover-Tree REF konstrueras också en träddatastruktur för NNS.
Cover trees for nearest neighbor
{'venue': "ICML '06", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}