GeoSOT-Based Spatiotemporal Index of Massive Trajectory Data

Chunyao Qian, Chao Yi, Chengqi Cheng, Guoliang Pu, Xiaofeng Wei, Huangchuang ZhangISPRS Int. J. Geo Inf 2019 · DOI

TL;DR

This paper introduces GeoSOT ST-index, a novel spatiotemporal indexing method that extends the GeoSOT spatial partitioning scheme to include time, creating a unified grid for massive trajectory data. This approach significantly improves query efficiency and scalability by converting complex 3D queries into simpler 1D searches, outperforming existing composite indexes by approximately 40%.

What Problem Does This Paper Address?

The explosion of location-based services and mobile devices has led to an unprecedented growth in trajectory data. While this data is invaluable for applications like traffic analysis and user behavior studies, its sheer volume and complexity create a significant bottleneck for storage and, more critically, for efficient querying. Traditional indexing methods struggle with the spatiotemporal nature of this data, often requiring separate indexing for spatial and temporal dimensions, which leads to inefficient, multi-step query processing. This paper addresses the challenge of efficiently querying massive, dynamic spatiotemporal trajectory data, particularly for large-scale range queries.

Methods

The core of the proposed solution is the GeoSOT ST-index. This method builds upon the existing GeoSOT spatial partitioning scheme, which recursively divides the Earth's surface into a hierarchical grid. The innovation lies in extending this partitioning to the time dimension, creating a global space-time subdivision scheme.

Here's a breakdown of the key methodological steps:

  • Global Space-Time Subdivision: The GeoSOT spatial partitioning is extended to incorporate time. This creates a unified, multi-level grid that covers both geographical space (latitude and longitude) and time.
  • GeoSOT ST-code Generation: Each trajectory point (defined by latitude, longitude, and timestamp) is converted into a unique GeoSOT ST-code. This code is generated by:
  • Converting spatial coordinates and time into decimal values within their respective GeoSOT grid cells.
  • Interleaving the binary representations of these spatial and temporal values to create a one-dimensional code, similar to a Morton code but in three dimensions. This effectively maps a 3D space-time point to a 1D code.
  • Multilevel Spatiotemporal Grid Index: The GeoSOT ST-index is constructed hierarchically, organizing trajectory data based on these generated ST-codes. This allows for efficient retrieval by matching query ranges to specific ST-codes.
  • Spatiotemporal Range Query Processing: The method converts a 3D spatiotemporal range query (spatial region + time interval) into a 1D query on the GeoSOT ST-codes. This involves determining an optimal subdivision level for the query range and then mapping the query cube's vertices to corresponding ST-codes. The final retrieval condition is then based on these de-duplicated ST-codes.

Datasets

The paper uses a GPS trajectory dataset collected by Microsoft, containing approximately 10 million GPS trajectories from 10,357 taxis in Beijing. This dataset is used for evaluating the performance of the proposed GeoSOT ST-index against other indexing methods. No new benchmarks are introduced; rather, existing real-world data is utilized.

Key Insights and Ideas

  • Unified Space-Time Indexing: The most significant insight is the successful integration of the time dimension into a spatial partitioning scheme (GeoSOT). This unified approach is crucial for efficiently handling spatiotemporal queries, avoiding the inefficiencies of separate spatial and temporal indexing.
  • 1D Querying for 3D Data: The conversion of complex 3D spatiotemporal range queries into simple 1D code matching is a powerful optimization. This drastically reduces the search space and computational overhead.
  • Scalability with Data Volume: The GeoSOT ST-index demonstrates superior scalability, with query time increasing much more gradually than composite indexes as data volume grows. This is attributed to the underlying B-tree structure for ST-codes, offering O(logN) time complexity for searches.
  • Robustness to Query Range Expansion: The index is less affected by increases in query range size compared to composite indexes, suggesting its suitability for broad spatiotemporal queries.

Key Results

  • Query Efficiency: The GeoSOT ST-index improves query efficiency by approximately 40% compared to the MongoDB spatiotemporal composite index.
  • Scalability: When the amount of data increased 10-fold, the query time for the GeoSOT ST-index remained relatively stable, showcasing its excellent scalability.
  • Encoding Efficiency: The generation of GeoSOT ST-codes is highly efficient, with conversion times completed within 3 microseconds per trajectory point, making the encoding cost negligible in practical applications.

Limitations and Future Work

  • Limitations:
    • The paper focuses on range queries. More complex query types (e.g., nearest neighbor, trajectory similarity) are not explicitly addressed.
  • While the ST-code generation is fast, the paper doesn't detail the index update costs beyond stating that it's low (adding/removing records).
  • Future Work:
    • The authors plan to investigate more complex query types using the proposed index.
  • Further comparisons will be made with existing solutions like ArcGIS and GeoMesa to provide a more comprehensive assessment of the proposed index's performance.

Summary updated

BibTeX
@article{qian2019geosot,
  author = {Chunyao Qian and Chao Yi and Chengqi Cheng and Guoliang Pu and Xiaofeng Wei and Huangchuang Zhang},
  title = {{GeoSOT-Based Spatiotemporal Index of Massive Trajectory Data}},
  journal = {ISPRS Int. J. Geo Inf.},
  year = {2019},
  doi = {10.3390/ijgi8060284},
}
Figure