On Nearest Neighbor Indexing of Nonlinear Trajectories

Summary: Introduces the convex-hull property for nonlinear trajectories and shows that trajectories satisfying it can be encoded for nearest-neighbor queries using standard spatial indexes. Proposes approximation techniques to make many nonlinear paths conform and validates empirically. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1296
Venue: PODS
Year: 2003
Pagerank: 5.4661361e-05
Overall Rank: 8,210 | 43.68%
DOI: 10.1145/773153.773178

Incoming Non-self Citations Over Time

Authors

1. Charu C. Aggarwal (IBM)
2. Dakshi Agrawal (IBM)

BibTeX Citation

@inproceedings{aggarwal_pods03,
        address = {New York, NY, USA},
        series = {{PODS} '03},
        title = {{On Nearest Neighbor Indexing of Nonlinear Trajectories}},
        url = {https://dl.acm.org/doi/10.1145/773153.773178},
        doi = {10.1145/773153.773178},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Aggarwal, Charu C. and Agrawal, Dakshi},
        year = {2003}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,394	Prediction and Indexing of Moving Objects with Unknown Motion Patterns	2004	SIGMOD	7.4500025e-05

Outgoing Citations (Sorted by Pagerank)

Showing 6 of 6 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.0020210012
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.001157935
85	The X-tree: An Index Structure for High-Dimensional Data	1996	VLDB	0.00035405879
560	Indexing the Positions of Continuously Moving Objects	2000	SIGMOD	0.00016525569
896	On Indexing Mobile Objects	1999	PODS	0.0001334014
1,611	Indexing Moving Points (Extended Abstract)	2000	PODS	0.00010218339

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,620	On Indexing Line Segments	1990	VLDB
2	9,034	Fast and Adaptive Indexing of Multi-Dimensional Observational Data	2016	VLDB
3	3,710	Efficient Reverse k-Nearest Neighbor Search in Arbitrary Metric Spaces	2006	SIGMOD
4	2,964	Direction-Preserving Trajectory Simplification	2013	VLDB
5	1,280	Indexing Spatio-Temporal Trajectories with Chebyshev Polynomials	2004	SIGMOD
6	7,463	Effectively Indexing Uncertain Moving Objects for Predictive Queries	2009	VLDB
7	560	Indexing the Positions of Continuously Moving Objects	2000	SIGMOD
8	1,611	Indexing Moving Points (Extended Abstract)	2000	PODS
9	896	On Indexing Mobile Objects	1999	PODS
10	2,375	Novel Approaches to the Indexing of Moving Object Trajectories	2000	VLDB