Title

Optimal-Location-Selection Query Processing in Spatial Databases

Publication Type

Journal Article

Publication Date

2009

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.

Discipline

Databases and Information Systems | Numerical Analysis and Scientific Computing

Research Areas

Data Management and Analytics

Publication

IEEE Transactions on Knowledge and Data Engineering

Volume

21

Issue

8

First Page

1162

Last Page

1177

ISSN

1041-4347

Identifier

10.1109/TKDE.2009.81

Publisher

IEEE

Additional URL

http://dx.doi.org/10.1109/TKDE.2009.81