Visible Reverse k-Nearest Neighbor Query Processing in Spatial Databases

被引:37
作者
Gao, Yunjun [1 ,2 ]
Zheng, Baihua [1 ]
Chen, Gencai [2 ]
Lee, Wang-Chien [3 ]
Lee, Ken C. K. [3 ]
Li, Qing [4 ]
机构
[1] Singapore Management Univ, Sch Informat Syst, Singapore 178902, Singapore
[2] Zhejiang Univ, Coll Comp Sci, Hangzhou 310027, Peoples R China
[3] Penn State Univ, Dept Comp Sci & Engn, University Pk, PA 16802 USA
[4] City Univ Hong Kong, Dept Comp Sci, Kowloon, Hong Kong, Peoples R China
基金
美国国家科学基金会;
关键词
Reverse nearest neighbor; visible reverse nearest neighbor; spatial database; query processing; algorithm;
D O I
10.1109/TKDE.2009.113
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
Reverse nearest neighbor (RNN) queries have a broad application base such as decision support, profile-based marketing, resource allocation, etc. Previous work on RNN search does not take obstacles into consideration. In the real world, however, there are many physical obstacles (e. g., buildings) and their presence may affect the visibility between objects. In this paper, we introduce a novel variant of RNN queries, namely, visible reverse nearest neighbor (VRNN) search, which considers the impact of obstacles on the visibility of objects. Given a data set P, an obstacle set O, and a query point q in a 2D space, a VRNN query retrieves the points in P that have q as their visible nearest neighbor. We propose an efficient algorithm for VRNN query processing, assuming that P and O are indexed by R-trees. Our techniques do not require any preprocessing and employ half-plane property and visibility check to prune the search space. In addition, we extend our solution to several variations of VRNN queries, including: 1) visible reverse k-nearest neighbor (VRkNN) search, which finds the points in P that have q as one of their k visible nearest neighbors; 2) delta-VRkNN search, which handles VRkNN retrieval with the maximum visible distance delta constraint; and 3) constrained VRkNN (CVRkNN) search, which tackles the VRkNN query with region constraint. Extensive experiments on both real and synthetic data sets have been conducted to demonstrate the efficiency and effectiveness of our proposed algorithms under various experimental settings.
引用
收藏
页码:1314 / 1327
页数:14
相关论文
共 21 条
[1]  
[Anonymous], 2000, ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery
[2]  
Asano T, 2000, HANDBOOK OF COMPUTATIONAL GEOMETRY, P829, DOI 10.1016/B978-044482537-7/50020-6
[3]  
BECKMANN N, 1990, SIGMOD REC, V19, P322, DOI 10.1145/93605.98741
[4]  
GAO Y, 2009, P INT C EXT DAT TECH, P144
[5]  
Guttman Antonin., 1984, SIGMOD Conference, P47, DOI [10.1145/971697.602266, DOI 10.1145/971697.602266, DOI 10.1145/602259.602266]
[6]  
Kofler M, 2000, J VISUAL COMP ANIMAT, V11, P129, DOI 10.1002/1099-1778(200007)11:3<129::AID-VIS227>3.0.CO
[7]  
2-T
[8]  
Korn F., 2002, Proceedings of the Twenty-eighth International Conference on Very Large Data Bases, P814
[9]  
Korn F, 2000, SIGMOD REC, V29, P201, DOI 10.1145/335191.335415
[10]   Ranked reverse nearest neighbor search [J].
Lee, Ken C. K. ;
Zheng, Baihua ;
Lee, Wang-Chien .
IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING, 2008, 20 (07) :894-910