Searching Trajectories by Locations - An Efficiency Study

Summary: Defines k-BCT: top-k trajectories that best connect a small query-location set using distance+order similarity. Uses Incremental kNN (IKNN) on a spatial index with lower/upper bound pruning; adapts best-first/DFS k-NN and demonstrates optimizations and experiments. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: hc84f11c9306cc5cc
Venue: SIGMOD
Year: 2010
Pagerank: 6.6423022e-05
Overall Rank: 4,352 | 70.75%
DOI: 10.1145/1807167.1807197

Incoming Non-self Citations Over Time

Authors

1. Zaiben Chen (University of Queensland)
2. Heng Tao Shen (University of Queensland)
3. Xiaofang Zhou (University of Queensland)
4. Yu Zheng (Microsoft)
5. Xing Xie (Microsoft)

BibTeX Citation

@inproceedings{chen_sigmod10,
        title = {{Searching Trajectories by Locations - An Efficiency Study}},
        author = {Chen, Zaiben and Shen, Heng Tao and Zhou, Xiaofang and Zheng, Yu and Xie, Xing},
        series = {{SIGMOD} '10},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1807167.1807197},
        url = {https://dl.acm.org/doi/10.1145/1807167.1807197},
        year = {2010}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,802	UlTraMan: A Unified Platform for Big Trajectory Data Management and Analytics	2018	VLDB	7.0132896e-05
3,939	On the Spatiotemporal Burstiness of Terms	2012	VLDB	6.9147782e-05
6,097	Trajectory Similarity Join in Spatial Networks	2017	VLDB	5.887961e-05
6,521	Trip Planning by an Integrated Search Paradigm	2018	SIGMOD	5.7573717e-05
12,150	Top-k Queries over Digital Traces	2019	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
2	R-Trees: A Dynamic Index Structure For Spatial Searching	1984	SIGMOD	0.001992968
28	Nearest Neighbor Queries	1995	SIGMOD	0.00051312804
42	Fast Subsequence Matching in Time-Series Databases	1994	SIGMOD	0.00045773967
227	Robust and Fast Similarity Search for Moving Object Trajectories	2005	SIGMOD	0.0002393284
306	On The Marriage of Lp-norms and Edit Distance	2004	VLDB	0.00021575844
915	Querying and Mining of Time Series Data: Experimental Comparison of Representations and Distance Measures	2008	VLDB	0.00013099703
1,294	Indexing Spatio-Temporal Trajectories with Chebyshev Polynomials	2004	SIGMOD	0.00011145111
2,494	An Efficient and Accurate Method for Evaluating Time Series Similarity	2007	SIGMOD	8.3888883e-05
2,827	Estimating the Selectivity of Spatial Queries Using the 'Correlation' Fractal Dimension	1995	VLDB	7.967335e-05
6,890	On Efficiently Searching Trajectories and Archival Data for Historical Similarities	2008	VLDB	5.6544825e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,325	Efficient k-NN Search on Vertically Decomposed Data	2002	SIGMOD
2	1,856	Efficient Retrieval of the Top-k Most Relevant Spatial Web Objects	2009	VLDB
3	6,097	Trajectory Similarity Join in Spatial Networks	2017	VLDB
4	6,107	Progressive Top-K Nearest Neighbors Search in Large Road Networks	2020	SIGMOD
5	8,895	Simpler is More: Efficient Top-K Nearest Neighbors Search on Large Road Networks	2024	VLDB
6	2,421	Novel Approaches to the Indexing of Moving Object Trajectories	2000	VLDB
7	10,647	High-Throughput k Nearest Neighbors Search in Road Networks	2026	SIGMOD
8	11,768	Efficient Non-Learning Similar Subtrajectory Search	2023	VLDB
9	11,600	Efficient kNN Search in Public Transportation Networks	2024	VLDB
10	12,181	The Maximum Trajectory Coverage Query in Spatial Databases	2019	VLDB