Optimal-location-selection query processing in spatial databases

Y. Gao, B. Zheng, G. Chen, Qing Li

Research output: Journal article publicationJournal articleAcademic researchpeer-review

16 Citations (Scopus)

Abstract

This paper introduces and solves a novel type of spatial queries, namely, Optimal-Location-Selection (OLS) search, which has many applications in real life. Given a data object set D-A, a target object set D-B, a spatial region R, and a critical distance d-c in a multidimensional space, an OLS query retrieves those target objects in D-B that are outside R but have maximal optimality. Here, the optimality of a target object b \in D-B located outside R is defined as the number of the data objects from D-A that are inside R and meanwhile have their distances to b not exceeding d-c. When there is a tie, the accumulated distance from the data objects to b serves as the tie breaker, and the one with smaller distance has the better optimality. In this paper, we present the optimality metric, formalize the OLS query, and propose several algorithms for processing OLS queries efficiently. A comprehensive experimental evaluation has been conducted using both real and synthetic data sets to demonstrate the efficiency and effectiveness of the proposed algorithms. © 2006 IEEE.
Original languageEnglish
Article number4815242
Pages (from-to)1162-1177
Number of pages16
JournalIEEE Transactions on Knowledge and Data Engineering
Volume21
Issue number8
DOIs
Publication statusPublished - 1 Aug 2009
Externally publishedYes

Keywords

  • Algorithm
  • Optimal-location-selection
  • Query processing
  • Spatial database

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics

Cite this