Publication Type

Journal Article

Version

acceptedVersion

Publication Date

8-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.

Keywords

Query processing, optimal-location-selection, spatial database, algorithm

Discipline

Databases and Information Systems | Numerical Analysis and Scientific Computing

Research Areas

Data Science and Engineering

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

Copyright Owner and License

Authors

Additional URL

https://doi.org/10.1109/TKDE.2009.81

Download

Share

COinS