An efficient nearest neighbor search in high-dimensional data spaces

✍ Scribed by Dong-Ho Lee; Hyoung-Joo Kim

• Publisher: Elsevier Science
• Year: 2002
• Tongue: English
• Weight: 240 KB
• Volume: 81
• Category: Article
• ISSN: 0020-0190
• DOI: 10.1016/s0020-0190(01)00236-8

✦ Synopsis

the result that basically none of the querying and indexing techniques which provide good results on lowdimensional data also performs sufficiently well on high-dimensional data. Many researchers have called this problem the "curse of dimensionality" [3], and many database-related projects have tried to tackle it. As a result of these research efforts, a variety of new index structures [11,9], cost models [10] and query processing techniques [7] have been proposed. However, most of the high-dimensional index structures are extensions of the R-tree or the kd-tree adapted to the requirements of high-dimensional indexing. Thus, all of these index structures are limited with respect to data space partitioning and suffer from specific drawbacks of the R-tree or the kd-tree.

To overcome these drawbacks, in our earlier work we proposed the SPY-TEC [2], an efficient index structure for similarity search in high-dimensional spaces and proposed the algorithm for processing range queries on the SPY-TEC. However, we could not propose an algorithm for processing nearest neighbor queries on the SPY-TEC.

In this paper, we introduce a new metric that can be used to guide an ordered best-first traversal when finding nearest neighbors on the SPY-TEC. Based on