VTRQ: Enabling Verifiable Trajectory Range Queries in Hybrid-Storage Blockchains
2026-08-21 • Databases
Databases
AI summaryⓘ
The authors address the problem of checking if trajectory data queries on outsourced cloud service providers are correct and complete. They propose VTRQ, a framework that uses two special data structures: one for efficiently verifying locations on road networks, and another for verifying the timing of trajectories. By handling the spatial and temporal parts separately, their method makes query checking faster and more reliable. They also combine these parts to correctly filter results in both space and time.
trajectory datahybrid-storage blockchainauthenticated data structuresspatial indexingtemporal indexinginterval treesrange queriesdata verificationspatio-temporal filtering
Authors
Zhongming Yao, Junchang Xin, Yumeng Song, Yusen Mao, Kristian Torp, Yuemin Ding, Divesh Srivastava, Yushuai Li, Christian S. Jensen, Tianyi Li
Abstract
Due to their increasingly large volumes, outsourcing of trajectory storage and querying to third-party service providers has become attractive. However, in such outsourced environments, service providers may return incorrect, e.g., incomplete, tampered, or invalid query results, making verifiability of query results an important consideration. Existing hybrid-storage blockchains offer limited support for trajectory data, lacking authenticated data structures (ADS) that enable efficient verification. For example, ADSs designed for queries on one-dimensional data are unsuitable for queries on multidimensional trajectory data, while ADSs tailored for discrete data may yield incomplete results when applied to continuous trajectory data. We propose the first framework for verifiable trajectory range queries in hybrid-storage blockchains, called VTRQ. It features two efficient ADSs: (i) a spatial ADS for road networks that leverages hierarchical organization to aggregate trajectory, edge, and node hashes, thus reducing redundant computations and improving spatial verification efficiency; and (ii) a temporal ADS based on interval trees, which indexes only the start and end times of trajectories, thereby enabling pruning and efficient temporal verification. By separating spatial and temporal indexing, the method reduces the need for data comparison, enhancing both query and verification efficiency. To aggregate spatial and temporal query results, VTRQ provides a spatio-temporal edge aggregation mechanism that combines temporal verification of spatial nodes, spatial intersection computation, and temporal intersection analysis to achieve spatio-temporal filtering.