View field nearest neighbor: A novel type of spatial queries

Sungmin Yi, Hyoseok Ryu, Jihoon Son, Yon Dohn Chung

Research output: Contribution to journalArticlepeer-review

14 Citations (Scopus)

Abstract

In this paper, we introduce a novel spatial query called the view field nearest neighbor query. Given the view field and location of a user, the view field nearest neighbor query retrieves a data object that is nearest to the user's location and falls within the user's view field. This query can be employed for applications such as augmented reality systems, tour guide systems, and CCTV-based surveillance systems. We propose a view field nearest neighbor query processing method that considers moving data objects (i.e., continuous view field nearest neighbor query processing), where we utilize the grid index. Continuous view field nearest neighbor query processing consists of two phases: (1) initial phase and (2) update phase. The first phase computes the initial result of a view field nearest neighbor query (i.e., snapshot query result) and the second phase continuously updates the result according to the movement of data objects. For the initial phase, we propose two algorithms: Naive Exploration Algorithm and Fan-shaped Exploration Algorithm. For the update phase, we propose the Fan-shaped Monitoring Algorithm to process the moving data objects efficiently. Through extensive experiments, we investigate the performance of our proposed algorithms on synthetic and real data sets.

Original languageEnglish
Pages (from-to)68-82
Number of pages15
JournalInformation Sciences
Volume275
DOIs
Publication statusPublished - 2014 Aug 10

Keywords

  • Continuous spatial query
  • Location-based service
  • Spatial database
  • View field nearest neighbor query

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Theoretical Computer Science
  • Computer Science Applications
  • Information Systems and Management
  • Artificial Intelligence

Fingerprint

Dive into the research topics of 'View field nearest neighbor: A novel type of spatial queries'. Together they form a unique fingerprint.

Cite this