Indexing Spatio-Temporal Trajectories with Chebyshev Polynomials

Summary: Chebyshev-polynomial minimax approx for d-D spatio-temporal trajectories as indexing basis; compact, pruning-friendly. Lower Bounding Lemma: trajectory distance ≥ weighted Chebyshev-distance; no false negatives; experiments show Chebyshev indexing beats APCA. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h3ad4170b24ec0157
Venue: SIGMOD
Year: 2004
Pagerank: 0.00011145111
Overall Rank: 1,294 | 91.31%
DOI: 10.1145/1007568.1007636

Incoming Non-self Citations Over Time

Authors

1. Yuhan Cai (University of British Columbia)
2. Raymond Ng (University of British Columbia)

BibTeX Citation

@inproceedings{cai_sigmod04,
        title = {{Indexing Spatio-Temporal Trajectories with Chebyshev Polynomials}},
        author = {Cai, Yuhan and Ng, Raymond},
        series = {{SIGMOD} '04},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1007568.1007636},
        url = {https://dl.acm.org/doi/10.1145/1007568.1007636},
        year = {2004}
}

Incoming Citations (Sorted by Pagerank)

Showing 17 of 17 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
227	Robust and Fast Similarity Search for Moving Object Trajectories	2005	SIGMOD	0.0002393284
915	Querying and Mining of Time Series Data: Experimental Comparison of Representations and Distance Measures	2008	VLDB	0.00013099703
1,095	A Data-adaptive and Dynamic Segmentation Index for Whole Matching on Time Series	2013	VLDB	0.00012050625
1,579	k-Shape: Efficient and Accurate Clustering of Time Series	2015	SIGMOD	0.00010186397
1,731	Indexable PLA for Efficient Similarity Search	2007	VLDB	9.7639519e-05
3,770	Calibrating Trajectory Data for Similarity-based Analysis	2013	SIGMOD	7.0297827e-05
4,316	GRAIL: Efficient Time-Series Representation Learning	2019	VLDB	6.6683448e-05
4,352	Searching Trajectories by Locations - An Efficiency Study	2010	SIGMOD	6.6423022e-05
4,703	Debunking Four Long-Standing Misconceptions of Time-Series Distance Measures	2020	SIGMOD	6.4621968e-05
5,228	STMaker–A System to Make Sense of Trajectory Data	2014	VLDB	6.2197988e-05
6,596	PPQ-Trajectory: Spatio-temporal Quantization for Querying in Large Trajectory Repositories	2021	VLDB	5.7410544e-05
6,890	On Efficiently Searching Trajectories and Archival Data for Historical Similarities	2008	VLDB	5.6544825e-05
7,641	A Structured Study of Multivariate Time-Series Distance Measures	2025	SIGMOD	5.4772833e-05
11,657	Scalable Model-Based Management of Massive High Frequency Wind Turbine Data with ModelarDB	2024	VLDB	4.9793485e-05
11,730	Correlation Joins over Time Series Data Streams Utilizing Complementary Dimension Reduction and Transformation	2023	SIGMOD	4.9793485e-05
11,749	Accelerating Similarity Search for Elastic Measures: A Study and New Generalization of Lower Bounding Distances	2023	VLDB	4.9793485e-05
12,290	Scaling Locally Linear Embedding	2017	SIGMOD	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
28	Nearest Neighbor Queries	1995	SIGMOD	0.00051312804
42	Fast Subsequence Matching in Time-Series Databases	1994	SIGMOD	0.00045773967
45	A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces	1998	VLDB	0.0004503446
193	Locally Adaptive Dimensionality Reduction for Indexing Large Time Series Databases	2001	SIGMOD	0.00025648171
385	Fast Similarity Search in the Presence of Noise, Scaling, and Translation in Time-Series Databases	1995	VLDB	0.0001946565
478	Fast Time Sequence Indexing for Arbitrary Lp Norms	2000	VLDB	0.00017631293
621	Efficiently Supporting Ad Hoc Queries in Large Datasets of Time Sequences	1997	SIGMOD	0.00015492309
811	Dimensionality Reduction for Similarity Searching in Dynamic Databases	1998	SIGMOD	0.00013745617
926	On Indexing Mobile Objects	1999	PODS	0.00013047723
1,634	Local Dimensionality Reduction: A New Approach to Indexing High Dimensional Spaces	2000	VLDB	0.0001001862

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	13,004	Indexing for Function Approximation	2006	VLDB
2	42	Fast Subsequence Matching in Time-Series Databases	1994	SIGMOD
3	6,715	Optimal Indexing Using Near-Minimal Space [Extended Abstract]	2003	PODS
4	9,204	Fast and Adaptive Indexing of Multi-Dimensional Observational Data	2016	VLDB
5	6,890	On Efficiently Searching Trajectories and Archival Data for Historical Similarities	2008	VLDB
6	6,943	Indexing the Edges – A simple and yet efficient approach to high-dimensional indexing	2000	PODS
7	2,421	Novel Approaches to the Indexing of Moving Object Trajectories	2000	VLDB
8	193	Locally Adaptive Dimensionality Reduction for Indexing Large Time Series Databases	2001	SIGMOD
9	8,377	On Nearest Neighbor Indexing of Nonlinear Trajectories	2003	PODS
10	1,731	Indexable PLA for Efficient Similarity Search	2007	VLDB