05-04-2012, 10:23 AM
Optimal-Location-Selection Query Processing in Spatial Databases
ttTKDE09_OSL.pdf (Size: 3.52 MB / Downloads: 33)
INTRODUCTION
SPATIAL databases play an important role in many real
applications, including geographical information systems,
decision support, intelligent transportation, and
resource allocation. The key characteristic that makes a
spatial database become a powerful tool is its ability to
manipulate (e.g., model, index, and query, etc.), but not
simply store, spatial data objects (e.g., points, line segments,
rectangles, and polygons, etc.).
Motivation
Over the last decade, efficient query processing for spatial
data objects has received considerable attention from the
database research community. Representative spatial
queries include range query [26], nearest neighbor (NN)
search [5], [17], [33], spatial join [4], [21], [27], [28], and
closest pair query [6], [7], [16]. However, there are still some
interesting applications involving spatial data for decision
making that cannot be efficiently supported by existing
spatial query processing techniques. Consider the following
two example applications.
Contributions
A naive solution to answer OLS (k-OLS) queries is to derive
the optimality of each target object in DB, and then, locate
these k objects with the highest optimality. In the rest of this
paper, we refer to this solution as a baseline approach. To be
more specific, the baseline method adopts a filtering and
refinement framework.
Organization of the Paper
The rest of this paper is organized as follows: Section 2
surveys the existing work related to the OLS query
problem. Section 3 elaborates three efficient k-OLS query
processing algorithms. Section 4 presents comprehensive
performance evaluation and reports our findings. Finally,
Section 5 concludes the paper with some directions for the
future work.
2 RELATED WORK
In this section, we first briefly overview the R-tree and
algorithms for range and NN queries, and then, review NN
query variants and distance join queries.
CONCLUSION
In this paper, we introduce and solve a new form of spatial
queries, namely, OLS search. It takes a data object set DA, a
target object set DB, a critical distance dc, and a spatial
region R as inputs, and returns those target objects outside R
with maximal optimality. We develop the optimality metric,
formalize the OLS query and its generalization (i.e., k-OLS
query), and propose three algorithms, including TS, RB, and
RRB, for efficient k-OLS query processing.