loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
22nd International Conference on Data Engineering (ICDE'06)
Nearest Surrounder Queries
Atlanta, Georgia
April 03-April 07
ISBN: 0-7695-2570-9
Ken C.K. Lee, Pennsylvania State University
Wang-Chien Lee, The Hong Kong Polytechnic University
Hong Va Leong, Pennsylvania State University
In this paper, we study a new type of spatial query, Nearest Surrounder (NS), which searches the nearest surrounding spatial objects around a query point. NS query can be more useful than conventional nearest neighbor (NN) query as NS query takes the object orientation into consideration. To address this new type of query, we identify angle-based bounding properties and distance-bound properties of Rtree index. The former has not been explored for conventional spatial queries. With these identified properties, we propose two algorithms, namely, Sweep and Ripple. Sweep searches surrounders according to their orientation, while Ripple searches surrounders ordered by their distances to the query point. Both algorithms can deliver result incrementally with a single dataset lookup. We also consider the multiple-tier NS (mNS) query that searches multiple layers of NSs. We evaluate the algorithms and report their performance on both synthetic and real datasets.
Citation:
Ken C.K. Lee, Wang-Chien Lee, Hong Va Leong, "Nearest Surrounder Queries," icde, pp.85, 22nd International Conference on Data Engineering (ICDE'06), 2006
Usage of this product signifies your acceptance of the Terms of Use.