Research On Reverse K-nearest Neighbor Query Algorithm Based On Data Federation

As an important spatial query,Reverse k-nearest Neighbor(RkNN)query has been widely studied and received attention.RkNN query retrieves the set of objects that have the query point as one of their k-nearest neighbors.RkNN query can reflect the impact of the query point on the result set,so it is of great significance in applications such as site selection and travel platform matching of user drivers.However,most existing RkNN query methods are based on the assumption of centralized data distribution and are difficult to adapt to the needs of data sharing and governance in today’s social multi-platform federation scenarios.To ensure privacy and security constraints,this paper will follow the guiding principle of"data not moved,computing moved" to explore the design and implementation of a data federated RkNN query algorithm,and achieve "virtual" shared computing.Research will be conducted in the following three aspects.:(1)Reverse k-nearest neighbor(RkNN)Exact query algorithm based on Data Federation.Guided by the idea of "data not moved,computing moved",this paper constructs a computing framework for accurate reverse k-nearest neighbor(RkNN)query in data federated scenarios.To address the time and communication overheads caused by secure computing in the framework,this paper proposes an optimization algorithm based on exponential search and heuristic strategy,and introduces the point-dominant filtering method to reduce unnecessary secure computing,thereby reducing the time and communication costs of the algorithm.Experimental results show that,compared with traditional encryption schemes,the reverse k-nearest neighbor query algorithm based on data federation achieves better results in both time performance and communication cost.(2)Approximate Reverse k-Nearest Neighbor Query Algorithm Based on Data Federation.This paper addresses the issue of the excessive time performance and communication cost of the exact query method presented in the previous chapter in actual highthroughput query scenarios.It proposes a data-federated approximate reverse k-nearest neighbor(RkNN)query problem and designs a unilateral sampling computing framework that approximates the global result with local results from a single platform.The framework proposes two approximation algorithms based on global fuzzy grid indexing and grid-tree indexing to optimize the federated secure query module.The experimental results show that,compared with the exact query scheme,the reverse k-nearest neighbor query algorithm based on data federation can efficiently respond to high-throughput query scenarios under the premise of ensuring accuracy,demonstrating the parallelism of this algorithm in the face of high-frequency queries.(3)A Reverse k Nearest Neighbor Query System Based on Data Federation.This paper implements a reverse k-nearest neighbor query system based on data federation,which is convenient for users to construct federated scenarios,customize configuration of reverse k-nearest neighbor query,and review and analyze historical query results.It provides a practical tool for researchers working on reverse k-nearest neighbor query in the data federation scenario,which enables the research in this paper to be applied.In this paper,the reverse k-nearest neighbor query algorithm based on data federation is studied from two aspects of exact query and approximate query.Conducted research and implemented a reverse k-nearest neighbor query system based on data federation.This article’s reflection on the data federation scenario.The research work of this paper on the reverse k-nearest neighbor query in the data federation scenario has important theoretical significance and application value for the spatial query calculation of the current shared and co-governed multi-platform massive data.