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: 1206
Venue: PODS
Year: 2000
Pagerank: 0.00010218339
Overall Rank: 1,611 | 88.95%
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
560	Indexing the Positions of Continuously Moving Objects	2000	SIGMOD	0.00016525569
957	The TPR*-Tree: An Optimized Spatio-Temporal Access Method for Predictive Queries	2003	VLDB	0.00012962576
2,254	STRIPES: An Efficient Index for Predicted Trajectories	2004	SIGMOD	8.8603695e-05
2,853	Indexing Large Trajectory Data Sets With SETI*	2003	CIDR	8.0383547e-05
3,394	Prediction and Indexing of Moving Objects with Unknown Motion Patterns	2004	SIGMOD	7.4500025e-05
3,462	Continuous K-Nearest Neighbor Queries for Continuously Moving Points with Updates	2003	VLDB	7.3922569e-05
3,581	Time-Parameterized Queries in Spatio-Temporal Databases	2002	SIGMOD	7.2873782e-05
3,637	Roads, Codes, and Spatiotemporal Queries	2004	PODS	7.2339626e-05
4,174	Selectivity Estimation for Spatio-Temporal Queries to Moving Objects	2002	SIGMOD	6.8515543e-05
8,031	On Moving Object Queries (Extended Abstract)	2002	PODS	5.5043169e-05
8,210	On Nearest Neighbor Indexing of Nonlinear Trajectories	2003	PODS	5.4661361e-05
8,787	Adaptive Location Constraint Processing	2007	SIGMOD	5.3729697e-05
9,254	Boosting Moving Object Indexing through Velocity Partitioning	2012	VLDB	5.297624e-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
560	Indexing the Positions of Continuously Moving Objects	2000	SIGMOD	0.00016525569
896	On Indexing Mobile Objects	1999	PODS	0.0001334014
1,529	On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract)	1999	PODS	0.00010482997
1,561	Efficient Searching with Linear Constraints (Extended Abstract)	1998	PODS	0.00010361147
2,135	Path Caching: A Technique for Optimal External Searching (Extended Abstract)	1994	PODS	9.1133971e-05
3,790	OODB Indexing by Class-Division	1995	SIGMOD	7.1239529e-05
4,040	Temporal Conditions and Integrity Constraints in Active Database Systems	1995	SIGMOD	6.9423365e-05
5,005	DOMINO: Databases for Moving Objects Tracking	1999	SIGMOD	6.4038565e-05

Semantically Similar Papers

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