Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/29517
Title: Nearest surrounder queries
Authors: Lee, KCK
Lee, WC
Leong, HV 
Keywords: Algorithms.
Nearest surrounder queries
R-tree
Spatial query processing
Issue Date: 2010
Publisher: Institute of Electrical and Electronics Engineers
Source: IEEE transactions on knowledge and data engineering, 2010, v. 22, no. 10, 5184841, p. 1444-1458 How to cite?
Journal: IEEE transactions on knowledge and data engineering 
Abstract: In this paper, we present a new type of spatial queries called Nearest Surrounder (NS) queries. An NS query determines the nearest polygon-shaped spatial objects (referred to as nearest surrounder objects) and their orientations with respect to a query point from an object set. Besides, we derive two NS query variants, namely, multitier NS (m-NS) queries and angle-constrained NS (ANS) queries. An m-NS query searches multiple layers of NS objects for the same range of angles from a query point. An ANS query searches for NS objects within a specified range of angles. To evaluate NS queries and their variants, we explore angle-based and distance-based bound properties of polygons, and devise two efficient algorithms, namely, Sweep and Ripple, based on R-tree. The algorithms access objects in an order according to their orientations and distances with respect to a given query point, respectively. They are efficient as they can finish a search with one index lookup. Besides, they can progressively deliver a query result. Through empirical studies, we evaluate the proposed algorithms and report their performance for both synthetic and real object sets.
URI: http://hdl.handle.net/10397/29517
ISSN: 1041-4347 (print)
1558-2191 (online)
DOI: 10.1109/TKDE.2009.172
Appears in Collections:Journal/Magazine Article

Access
View full-text via PolyU eLinks SFX Query
Show full item record

SCOPUSTM   
Citations

9
Last Week
0
Last month
1
Citations as of May 26, 2017

WEB OF SCIENCETM
Citations

4
Last Week
0
Last month
Citations as of May 29, 2017

Page view(s)

25
Last Week
0
Last month
Checked on May 28, 2017

Google ScholarTM

Check

Altmetric



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.