Processing Approximate KNN Query Based on Data Source Selection
Liang Zhu, Peng Li, Yonggang Wei, Xin Song, Yu Wang · 2021
A KNN query over a relation is to find its$K$nearest neighbors/tuples from a dataset/relation according to a distance function. In this paper, we discuss approximate KNN query processing based on the selection of many data sources with various dimensions. We propose algorithms to construct a UBR- Tree and a Centroid Base for selecting related data sources and retrieving$K$NN tuples. For a$K$NN query$Q$, (1) the related data sources are selected by using the Centroid Base, (2) these data sources are sorted according to their representative tuple in the Centroid Base, (3) local$K$NN tuples in the related data sources are retrieved, and (4) a heap structure is used to merge the local$K$NN tuples to form global$K$NN tuples of$Q$. Extensive experiments over low-dimensional and high-dimensional datasets are conducted to demonstrate the performances of our proposed approaches.