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 language | English |
---|---|
Article number | 4815242 |
Pages (from-to) | 1162-1177 |
Number of pages | 16 |
Journal | IEEE Transactions on Knowledge and Data Engineering |
Volume | 21 |
Issue number | 8 |
DOIs | |
Publication status | Published - 1 Aug 2009 |
Externally published | Yes |
Keywords
- Algorithm
- Optimal-location-selection
- Query processing
- Spatial database
ASJC Scopus subject areas
- Information Systems
- Computer Science Applications
- Computational Theory and Mathematics