Top-n query processing in spatial databases considering bi-chromatic reverse k-nearest neighbors |
| |
| Affiliation: | 1. Department of Computer Science, National Tsing Hua University, Hsinchu, Taiwan, ROC;2. Cloud Computing Center for Mobile Applications, Industrial Technology Research Institute, Hsinchu, Taiwan, ROC;3. Department of Computer Science, National Chengchi University, Taipei, Taiwan, ROC;1. Centre for Complex Cooperative Systems, University of the West of England, Coldharbour Lane, Bristol BS16 1QY, United Kingdom;2. CERN, 1217 Geneva 23, Switzerland;1. Key Labs of Data Engineering and Knowledge Engineering, Ministry of Education, China;2. Department of Management Science and Engineering, Tsinghua University, China;3. Department of Systems Engineering and Engineering Management, Chinese University of Hong Kong, Hong Kong, China;4. School of Information, Renmin University of China, China;1. Department of Mechanical Engineering, McGill University, Montreal, Quebec, Canada H3A 0C3;2. School of Mechanical, Materials and Mechatronic Engineering, University of Wollongong, NSW 2522, Australia;1. School of Software, Tsinghua University, Beijing, China;2. Key Lab for Information System Security, Ministry of Education, Beijing, China;3. National Laboratory for Information Science and Technology, Beijing, China;4. Logistical Engineering University, Chongqing, China;5. Queensland University of Technology, Brisbane, Australia;6. Eindhoven University of Technology, Eindhoven, The Netherlands;1. Insight Centre Data Analytics, Dublin, Ireland;2. CLARITY: Centre for Sensor Web Technologies, Dublin City University, Dublin, Ireland;3. Applied Sports Performance Research, School of Health and Human Performance, Dublin City University, Dublin, Ireland;4. Sports Surgery Clinic, Santry Demense, Dublin 9, Ireland |
| |
| Abstract: | A reverse k-nearest neighbor (RkNN) query retrieves the data points which regard the query point as one of their respective k nearest neighbors. A bi-chromatic reverse k-nearest neighbor (BRkNN) query is a variant of the RkNN query, considering two types of data. Given two types of data G and C, a BRkNN query regarding a data point q in G retrieves the data points from C that regard q as one of their respective k-nearest neighbors among the data points in G. Many existing approaches answer either the RkNN query or the BRkNN query. Different from these approaches, in this paper, we make the first attempt to propose a top-n query based on the concept of BRkNN queries, which ranks the data points in G and retrieves the top-n points according to the cardinalities of the corresponding BRkNN answer sets. For efficiently answering this top-n query, we construct the Voronoi Diagram of G to index the data points in G and C. From the information associated with the Voronoi Diagram of G, the upper bound of the cardinality of the BRkNN answer sets for each data point in G can be quickly computed. Moreover, based on an existing approach to answering the RkNN query and the characteristics of the Voronoi Diagram of G, we propose a method to find the candidate region regarding a BRkNN query, which tightens the corresponding search space. Finally, based on the triangle inequality, we propose an efficient refinement algorithm for finding the exact BRkNN answers from the candidate regions. To evaluate our approach on answering the top-n query, it is compared with an approach which applies a state-of-the-art algorithm for answering the BRkNN query to each data point in G. The experiment results reveal that our approach has a much better performance. |
| |
| Keywords: | Spatial databases |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
