Spatial Query Processing Using Object Decomposition Method

Yong-Ju Lee, Ho-Hyun Park, Nam-Hee Hong, Chin-Wan ChungCIKM 1996 · DOI

TL;DR

This paper introduces a novel "controlled decomposition" method (DMBRs) for breaking down complex spatial objects into simpler components. This approach, coupled with a two-step indexing structure, significantly improves the efficiency of spatial query processing by intelligently managing the trade-off between approximation accuracy and the number of components.

What Problem Does This Paper Address?

Spatial databases often deal with complex, irregularly shaped objects (like cities, roads, or lakes) that are difficult to query efficiently. Traditional methods often approximate these objects using Minimum Bounding Rectangles (MBRs), which can lead to many "false hits" during query filtering, requiring expensive refinement steps. While object decomposition techniques offer better approximations, they can generate an overwhelming number of components, also impacting performance. This paper addresses the challenge of efficiently querying complex spatial objects by proposing a method that balances the accuracy of approximation with a manageable number of decomposed components.

Methods

The core of the paper is the Decomposed Minimum Bounding Rectangles (DMBRs) method. This technique recursively divides a spatial object's MBR into two sub-polygons, creating new DMBRs for each. This process continues until a constraint related to the "accuracy of decomposition" (AOD) is met, controlled by a parameter 'g'. This parameter allows for tuning the decomposition to balance the number of components and the accuracy of the approximation.

To support this, the authors propose a two-step indexing structure:

  1. Ro-tree: An extension of the R-tree that stores MBRs of original objects. Each leaf node in the Ro-tree points to a second-level index.
  2. Rd-tree: A two-dimensional binary tree that stores the decomposed components (DMBRs) generated by the controlled decomposition method.

This structure facilitates efficient spatial query processing through a two-step filter-refinement approach: the Ro-tree filters candidates using MBRs, and the Rd-tree refines these candidates using the more accurate DMBRs. The paper also details algorithms for point, region, and spatial join queries within this framework.

Datasets

The paper evaluates its method using three real-world spatial objects: "Park," "Lake," and "Korea," which are described by their number of vertices, area, MBR area, and "cover" (area of the object normalized to its MBR area). These objects are representative of data found in geographic information systems. No new benchmarks were introduced.

Key Insights and Ideas

  • Controlled Decomposition is Key: The ability to control the decomposition process with a parameter 'g' is crucial. This allows for a flexible trade-off between the number of components and the accuracy of approximation, which is a significant improvement over methods that either produce too few (inaccurate) or too many (complex) components.
  • Two-Step Indexing for Efficiency: The combination of a traditional R-tree (Ro-tree) for initial filtering and a specialized binary tree (Rd-tree) for decomposed components provides a powerful hierarchical approach to query processing.
  • MBRs are Not Enough for Complex Objects: The paper clearly demonstrates that while MBRs are fast, their inherent inaccuracy leads to significant overhead in the refinement stage for complex spatial objects.
  • Balancing Performance Metrics: The analytical study highlights that optimizing for a single metric (like minimizing components or maximizing accuracy) leads to poor overall performance. A balanced approach, achievable with DMBRs, is essential.

Key Results

The paper presents an analytical study comparing its proposed method (C5) with traditional decomposition methods (classified into C1-C4). The results suggest that the DMBRs method (C5) offers superior performance by allowing the tuning of the decomposition parameter 'g'. Experimental results (Table 2) show that an optimal 'g' value (around 3) leads to significantly faster query times for point, region, and spatial join queries compared to no decomposition (g=0) or high decomposition (g=6). The analytical complexity analysis (Table 5) also indicates that C5 provides a better balance across the number of components (NC), quality of approximation (QA), and simplification of objects (SO).

Limitations and Future Work

The authors acknowledge that their analytical study is preliminary and suggest that a more general cost model and experimental verification are needed. They also note that while their method provides a good balance, it doesn't necessarily achieve the absolute best value for each individual criterion (NC, QA, SO) when considered in isolation. Future work could involve extending the analytical study to a more comprehensive cost model and conducting extensive experimental validation across a wider range of datasets and query types.

Summary updated

BibTeX
@inproceedings{lee1996spatial,
  author = {Yong-Ju Lee and Ho-Hyun Park and Nam-Hee Hong and Chin-Wan Chung},
  title = {{Spatial Query Processing Using Object Decomposition Method}},
  booktitle = {ACM International Conference on Information and Knowledge Management},
  year = {1996},
  doi = {10.1145/238355.238374},
}
Figure