pipette
ENEnglish

TraHist: Fast and Accurate Cardinality Estimation for Trajectory Data (Extended Version)

Yujeong Jo, Incheol Baek, Changbeom Shim, Yon Dohn Chung

Preprint

En palabras de los autores

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.

Resultado principalEl resumen no menciona limitaciones.

Apareció: viernes, 16 de octubre. arXiv. Preprint, todavía sin revisión por pares.

Comentario de los autores: Extended version of the paper to appear in PACMMOD Vol. 4, No. 6 (SIGMOD 2027)