I detta dokument presenterar vi en ny kostnadsmodell för närmaste grannsökning i högdimensionellt datautrymme. Vi först analysera olika närmaste grannalgoritmer, presentera en generalisering av en algoritm som ursprungligen har föreslagits för Quadtrees [13], och visa att denna algoritm är optimal. Sedan utvecklar vi en kostnadsmodell som - i motsats till tidigare modeller - tar hänsyn till gränseffekter och därför också fungerar i höga dimensioner. Fördelarna med vår modell är i synnerhet: Vår modell fungerar för datamängder med ett godtyckligt antal dimensioner och ett godtyckligt antal datapunkter, är tillämplig på olika datadistributioner och indexstrukturer, och ger korrekta uppskattningar av den förväntade körningstiden för frågor. För att visa vår modells praktiska relevans och noggrannhet utför vi en detaljerad analys med hjälp av syntetiska och verkliga data. Resultaten av att tillämpa vår modell på Hilbert och X-tree index visar att den ger en bra uppskattning av frågeprestandan, vilket är betydligt bättre än uppskattningarna från tidigare modeller särskilt för högdimensionella data.
I REF har en kostnadsmodell föreslagits som är mycket korrekt även i högdimensioner eftersom modellen tar hänsyn till gränseffekter.
A cost model for nearest neighbor search in high-dimensional data space
{'venue': "PODS '97", 'journal': None, 'mag_field_of_study': ['Computer Science']}