Approximate KNN Query Processing of Multiple Data Sources Based on Data Source Selection

A K NN query aims to identify the K closest neighbors or tuples from a dataset based on a specified distance metric. This paper delves into the realm of approximate K NN query processing, focusing on the meticulous selection of multiple data sources characterized by diverse dimensions. We provide a framework for processing approximate K NN queries over multiple data sources, proposing algorithms to construct a UBR-Tree and a Centroid Base for selecting related data sources and retrieving K NN tuples. We enhance and apply an index structure to quickly retrieve related data sources and K NN tuples for a query. For a K NN query Q , the query processing consists of the following steps: (1) Estimate a search distance using the index structure. (2) Use the search distance to select relevant data sources from the Centroid Base, sorting them according to their representative tuple. (3) Employ a heap structure to merge the local K NN tuples obtained from the related data sources to form global K NN tuples for Q . Additionally, update the index structure when processing the query. Extensive experiments over low-dimensional and high-dimensional datasets demonstrate the performances of our proposed approaches.