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: 3614
Venue: SIGMOD
Year: 2004
Pagerank: 0.00011308659
Overall Rank: 1,284 | 91.23%
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
222	Robust and Fast Similarity Search for Moving Object Trajectories	2005	SIGMOD	0.00024132282
903	Querying and Mining of Time Series Data: Experimental Comparison of Representations and Distance Measures	2008	VLDB	0.00013288853
1,087	A Data-adaptive and Dynamic Segmentation Index for Whole Matching on Time Series	2013	VLDB	0.00012210999
1,585	k-Shape: Efficient and Accurate Clustering of Time Series	2015	SIGMOD	0.00010262333
1,726	Indexable PLA for Efficient Similarity Search	2007	VLDB	9.8884903e-05
3,866	Calibrating Trajectory Data for Similarity-based Analysis	2013	SIGMOD	7.0449624e-05
4,239	GRAIL: Efficient Time-Series Representation Learning	2019	VLDB	6.7927773e-05
4,330	Searching Trajectories by Locations - An Efficiency Study	2010	SIGMOD	6.7364305e-05
4,619	Debunking Four Long-Standing Misconceptions of Time-Series Distance Measures	2020	SIGMOD	6.5828287e-05
5,143	STMaker–A System to Make Sense of Trajectory Data	2014	VLDB	6.3316147e-05
6,502	PPQ-Trajectory: Spatio-temporal Quantization for Querying in Large Trajectory Repositories	2021	VLDB	5.8455169e-05
6,790	On Efficiently Searching Trajectories and Archival Data for Historical Similarities	2008	VLDB	5.7587314e-05
10,829	A Structured Study of Multivariate Time-Series Distance Measures	2025	SIGMOD	5.0723324e-05
11,398	Scalable Model-Based Management of Massive High Frequency Wind Turbine Data with ModelarDB	2024	VLDB	5.0723324e-05
11,474	Correlation Joins over Time Series Data Streams Utilizing Complementary Dimension Reduction and Transformation	2023	SIGMOD	5.0723324e-05
11,493	Accelerating Similarity Search for Elastic Measures: A Study and New Generalization of Lower Bounding Distances	2023	VLDB	5.0723324e-05
12,047	Scaling Locally Linear Embedding	2017	SIGMOD	5.0723324e-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
29	Nearest Neighbor Queries	1995	SIGMOD	0.00051956566
41	Fast Subsequence Matching in Time-Series Databases	1994	SIGMOD	0.00046492911
46	A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces	1998	VLDB	0.00044727572
191	Locally Adaptive Dimensionality Reduction for Indexing Large Time Series Databases	2001	SIGMOD	0.000260113
372	Fast Similarity Search in the Presence of Noise, Scaling, and Translation in Time-Series Databases	1995	VLDB	0.00019788817
470	Fast Time Sequence Indexing for Arbitrary Lp Norms	2000	VLDB	0.00017918286
612	Efficiently Supporting Ad Hoc Queries in Large Datasets of Time Sequences	1997	SIGMOD	0.00015727451
799	Dimensionality Reduction for Similarity Searching in Dynamic Databases	1998	SIGMOD	0.00013892889
905	On Indexing Mobile Objects	1999	PODS	0.00013285601
1,608	Local Dimensionality Reduction: A New Approach to Indexing High Dimensional Spaces	2000	VLDB	0.0001019729

Semantically Similar Papers

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