Trajectory data cardinality estimation improved with adaptive histograms
TraHist: Fast and Accurate Cardinality Estimation for Trajectory Data (Extended Version)
Databases
Summary
Estimating how many trajectory records match a query is important but hard because moving objects follow paths that break usual assumptions about data independence. The authors found that common methods split these paths improperly, causing inaccurate counts. They created TraHist, a new way to group trajectory data that better matches how objects move, reducing errors significantly. Experiments show TraHist is both faster and more accurate than existing estimators.
What this means in practice
- •For database administrators: Improve query performance for trajectory data by more accurately estimating result sizes, aiding optimizer decisions.
- •For location-based service developers: Enable faster and more precise data queries over moving object histories by integrating adaptive histograms for cardinality estimation.
Authors
Yujeong Jo, Incheol Baek, Changbeom Shim, Yon Dohn Chung
Abstract
Cardinality estimation is fundamental for query optimization in database systems. Histogram-based estimators are widely used for their simplicity and efficiency but rely on point-centric partitioning that assumes record independence. This assumption breaks in trajectory data, where records from the same moving object show strong spatiotemporal dependencies. Conventional axis-aligned histograms therefore fragment trajectories across partition boundaries, leading to overestimation through duplicate counting. This error reflects a structural limitation of partition boundaries that are misaligned with trajectory-induced density patterns. To this end, we propose TraHist, a histogram-based estimator approximating density-aligned partitioning via efficient grid-based propagation. TraHist builds density-adaptive rectilinear buckets to preserve trajectory continuity and local density coherence while keeping histogram efficiency. Experiments on large-scale real-world datasets show that TraHist reduces estimation error by over 20x relative to the strongest competing estimator in query regimes where trajectory fragmentation is a dominant source of estimation error, while maintaining sub-millisecond query latency and competitive construction cost.