Nearest surrounder queries

Ken C.K. Lee, Wang Chien Lee, Hong Va Leong

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

31 Citations (Scopus)


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 R-tree 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 ofNSs. We evaluate the algorithms and report their performance on both synthetic and real datasets.
Original languageEnglish
Title of host publicationProceedings of the 22nd International Conference on Data Engineering, ICDE '06
Number of pages1
Publication statusPublished - 17 Oct 2006
Event22nd International Conference on Data Engineering, ICDE '06 - Atlanta, GA, United States
Duration: 3 Apr 20067 Apr 2006


Conference22nd International Conference on Data Engineering, ICDE '06
Country/TerritoryUnited States
CityAtlanta, GA

ASJC Scopus subject areas

  • Software
  • Signal Processing
  • Information Systems


Dive into the research topics of 'Nearest surrounder queries'. Together they form a unique fingerprint.

Cite this