Query as Region Partition in Managing Moving Objects for Concurrent Continuous Query

Ming Qi, Guangzhong Sun, Yun XuInternational Journal of Research in Computer Science 2011 · DOI

TL;DR

This paper introduces a novel "query as region partition" approach for managing moving objects and their continuous queries in main memory. By treating query regions as partitions within spatial indices (uniform grid and k-d tree), they unify index updating and query processing, leading to significantly improved performance, especially for stationary queries. Their fine-grained concurrency control further enhances throughput on multi-core systems.

What Problem Does This Paper Address?

Location-Based Services (LBS) are becoming increasingly prevalent, relying heavily on managing and querying large numbers of moving objects in real-time. A critical operation in LBS is continuous querying, where users constantly monitor objects within specific regions. Traditional approaches struggle to handle the high throughput and real-time update demands of these applications, especially with the growing ubiquity of mobile devices and sensors. Existing spatial indexing methods often fall short in efficiently managing both object updates and continuous queries concurrently, leading to performance bottlenecks. The paper aims to address this by proposing a more integrated and efficient method for managing moving objects and their continuous queries, leveraging multi-core processing and in-memory indexing.

Methods

The core innovation is the "query as region partition" scheme. Instead of treating queries as separate entities that overlay a spatial index, this approach integrates query regions directly into the spatial partitioning. This means that when an object moves, its update is handled within the context of the query regions it might enter or leave.

The authors explore this concept using two primary spatial index structures:

  • Uniform Grid: In this scheme, each grid cell maintains a list of references to query regions that overlap with it. The "region" of a grid cell is effectively its area minus any overlapping query regions. This simplifies updates as objects are managed within these defined partitions.
  • Regional k-d Tree: Similar to the uniform grid, query regions are treated as sustainable partitions within the k-d tree structure. Overlapping query regions lead to object duplication in the results, which the authors deem reasonable as each query should have its complete result set.

To manage concurrent access, they propose:

  • Fine-grain Locking: For object updates within index buckets (implemented as linked lists), a fine-grain locking mechanism is used. This involves locking only the necessary nodes (deleting node, predecessor, and insert position) to minimize contention and allow for atomic-like operations.
  • Coarse-grain Locking: For structural alterations (query creation, deletion, or modification), a coarser-grained locking approach is employed to protect affected regions. This uses read-locks, SIX-locks, and exclusive-locks to ensure consistency during these less frequent but more impactful operations.

Datasets

The experiments were conducted using a dataset of moving objects on a road network in the city of Oldenburg [17]. This dataset contains 200,000 objects with coordinates within a 30x30 km² area. The queries used were randomly generated with sizes within 6x6 km².

Key Insights and Ideas

  • Unifying Query and Partitioning: The most significant insight is that treating query regions as partitions simplifies both object updates and query processing. This eliminates the need for separate data structures to manage query results, reducing redundancy and complexity.
  • Stationary Queries are Key: The "query as region partition" approach shines when queries are relatively stationary. In such cases, continuous query operations become very efficient, essentially just returning the contents of the relevant partitions.
  • Fine-grained Locking for Throughput: The fine-grained locking mechanism is crucial for achieving high throughput in concurrent environments. By minimizing the scope of locks, it allows for more parallel operations without sacrificing data consistency.
  • Uniform Grid Advantage: For updating moving objects, the uniform grid generally outperforms the k-d tree. This is attributed to the O(1) complexity of finding a grid cell for a given position, compared to O(log B) for a k-d tree (where B is the number of buckets).

Key Results

  • Update Performance: The uniform grid consistently shows better update performance than the k-d tree, especially as the number of objects increases.
  • Query Throughput: The paper demonstrates that when query alteration is infrequent (high query/alteration ratio), the proposed scheme achieves significantly higher query throughput compared to scenarios with frequent alterations.
  • Concurrency Speedup: With their concurrency controls, both the uniform grid and k-d tree exhibit good parallel speedup as the number of concurrent threads increases. The uniform grid shows nearly linear speedup, while the k-d tree's speedup is slightly lower due to tree node splitting and merging.

Limitations and Future Work

  • Query Alteration Impact: The paper acknowledges that query alteration operations are computationally more intensive than continuous queries. The overall performance is significantly affected by the alteration ratio, with the proposed scheme offering less advantage when alterations are frequent.
  • Starvation-Free Guarantee: While the coarse-grain lock for structure alteration is deadlock-free, it is not starvation-free, meaning a thread might theoretically wait indefinitely for a lock.
  • Future Directions: The authors suggest future work could focus on:
  • Indexing moving objects with multiple attributes.
  • Handling sophisticated continuous queries like k-NN queries.
  • Utilizing more specialized index structures.
  • Applying these techniques to more complex, real-world problems.

Summary updated

Abstract

Applications in location-based services rely on the efficient management of large scale moving objects, and one of the most important operations is real-time continuous query over moving objects, such as monitoring the objects of a certain region. In order to satisfy the high throughput and handle real-time updates and queries, it is a good choice to introduce multi-core parallel processing and managing spatial indices in main memory. In this paper, we propose a new scheme of processing continuous query on a novel spatial index based on uniform grid which is proved to be a good indexing scheme in main memory. The novelty of our index is to manage query region as the partition in the spatial index, which unified the index updating and query processing. Our experiments indicate that this sophisticated approach has better performance especially when the query is rather stationary..
BibTeX
@article{qi2011query,
  author = {Ming Qi and Guangzhong Sun and Yun Xu},
  title = {{Query as Region Partition in Managing Moving Objects for Concurrent Continuous Query}},
  journal = {International Journal of Research in Computer Science},
  year = {2011},
  doi = {10.7815/ijorcs.21.2011.008},
}
Figure