Multilevel Filtering for High Dimensional Nearest Neighbor Search.
Changzhou Wang, Xiaoyang Sean Wang · 2000
Searching for nearest neighbors among a large number of vectors in a high dimensional space is usually costly and time-consuming. To support such high dimensional nearest neighbor searches, low dimensional approximations of vectors are usually used to filter out many vectors (and hence to reduce the search space). However, most existing studies use only a single level approximations. This paper, instead, proposes a multilevel approximation scheme. For each data vector, with its approximation (at any given level), both a lower bound and an upper bound can be derived on its distance from the query vector. Distance bounds derived at a finer approximation level are tighter, but the cost to derive them is higher. The paper then presents two multilevel filtering methods using this approximation scheme. The coarsest level approximations, which are low in both volume and dimensionality, are indexed in a R-tree, and are used first to compute a set of candidate vectors. Finer level approximations ar...