Indexing Moving Points (Extended Abstract)

Summary: External-memory indexing for N planar points moving linearly: first structure uses O(N/B) blocks and answers rectangle-at-time queries in O((N/B)^{1/2+ε}+K/B) I/Os, supports time-interval reports and O(log_{2B} N) updates. Also: an evolving-index that trades query time vs. index-update frequency for chronological queries, a scheme whose query cost is monotone in |tq−now|, and an efficient index for approximate nearest neighbors among moving points. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h43fdc9443e03d86d
Venue: PODS
Year: 2000
Pagerank: 9.9929961e-05
Overall Rank: 1,646 | 88.94%
DOI: 10.1145/335168.335220

Incoming Non-self Citations Over Time

Authors

1. Pankaj K. Agarwal (Duke University)
2. Lars Arge (Duke University)
3. Jeff Erickson (University of Illinois Urbana-Champaign)

BibTeX Citation

@inproceedings{agarwal_pods00,
        address = {New York, NY, USA},
        series = {{PODS} '00},
        title = {{Indexing Moving Points (Extended Abstract)}},
        url = {https://dl.acm.org/doi/10.1145/335168.335220},
        doi = {10.1145/335168.335220},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Agarwal, Pankaj K. and Arge, Lars and Erickson, Jeff},
        year = {2000}
}

Incoming Citations (Sorted by Pagerank)

Showing 13 of 13 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
574	Indexing the Positions of Continuously Moving Objects	2000	SIGMOD	0.00016173068
985	The TPR*-Tree: An Optimized Spatio-Temporal Access Method for Predictive Queries	2003	VLDB	0.00012685169
2,309	STRIPES: An Efficient Index for Predicted Trajectories	2004	SIGMOD	8.6626683e-05
2,911	Indexing Large Trajectory Data Sets With SETI*	2003	CIDR	7.8720638e-05
3,462	Prediction and Indexing of Moving Objects with Unknown Motion Patterns	2004	SIGMOD	7.2834147e-05
3,522	Continuous K-Nearest Neighbor Queries for Continuously Moving Points with Updates	2003	VLDB	7.2350043e-05
3,658	Time-Parameterized Queries in Spatio-Temporal Databases	2002	SIGMOD	7.1243855e-05
3,704	Roads, Codes, and Spatiotemporal Queries	2004	PODS	7.0839867e-05
4,251	Selectivity Estimation for Spatio-Temporal Queries to Moving Objects	2002	SIGMOD	6.7020655e-05
8,188	On Moving Object Queries (Extended Abstract)	2002	PODS	5.3812931e-05
8,377	On Nearest Neighbor Indexing of Nonlinear Trajectories	2003	PODS	5.3435192e-05
8,950	Adaptive Location Constraint Processing	2007	SIGMOD	5.2524216e-05
9,427	Boosting Moving Object Indexing through Velocity Partitioning	2012	VLDB	5.178769e-05

Outgoing Citations (Sorted by Pagerank)

Showing 8 of 8 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
574	Indexing the Positions of Continuously Moving Objects	2000	SIGMOD	0.00016173068
926	On Indexing Mobile Objects	1999	PODS	0.00013047723
1,559	On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract)	1999	PODS	0.00010252232
1,589	Efficient Searching with Linear Constraints (Extended Abstract)	1998	PODS	0.00010139591
2,179	Path Caching: A Technique for Optimal External Searching (Extended Abstract)	1994	PODS	8.9120272e-05
3,859	OODB Indexing by Class-Division	1995	SIGMOD	6.9667626e-05
4,120	Temporal Conditions and Integrity Constraints in Active Database Systems	1995	SIGMOD	6.7947455e-05
5,125	DOMINO: Databases for Moving Objects Tracking	1999	SIGMOD	6.2614937e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	9,100	Dynamic Indexability and Lower Bounds for Dynamic One-Dimensional Range Query Indexes	2009	PODS
2	12,054	On the I/O Complexity of the k-Nearest Neighbors Problem	2020	PODS
3	9,204	Fast and Adaptive Indexing of Multi-Dimensional Observational Data	2016	VLDB
4	2,421	Novel Approaches to the Indexing of Moving Object Trajectories	2000	VLDB
5	2,495	Independent Range Sampling	2014	PODS
6	6,715	Optimal Indexing Using Near-Minimal Space [Extended Abstract]	2003	PODS
7	926	On Indexing Mobile Objects	1999	PODS
8	1,589	Efficient Searching with Linear Constraints (Extended Abstract)	1998	PODS
9	2,064	Query and Update Efficient B+-Tree Based Indexing of Moving Objects	2004	VLDB
10	1,559	On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract)	1999	PODS