Database Paper Browser

Back to papers

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
1207
Venue
PODS
Year
2000
Pagerank
0.0001062234
Overall Rank
1,764 | 87.75%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 13 of 13 citing papers.

Rank Citing Paper Year Venue Pagerank
628 Indexing the Positions of Continuously Moving Objects 2000 SIGMOD 0.00018957327
1,055 The TPR*-Tree: An Optimized Spatio-Temporal Access Method for Predictive Queries 2003 VLDB 0.00014391376
2,532 STRIPES: An Efficient Index for Predicted Trajectories 2004 SIGMOD 8.5886308e-05
2,744 Indexing Large Trajectory Data Sets With SETI* 2003 CIDR 8.1917832e-05
2,893 Prediction and Indexing of Moving Objects with Unknown Motion Patterns 2004 SIGMOD 7.9547451e-05
3,356 Roads, Codes, and Spatiotemporal Queries 2004 PODS 7.1764335e-05
3,415 Continuous K-Nearest Neighbor Queries for Continuously Moving Points with Updates 2003 VLDB 7.1162894e-05
3,802 Time-Parameterized Queries in Spatio-Temporal Databases 2002 SIGMOD 6.7524078e-05
4,142 Selectivity Estimation for Spatio-Temporal Queries to Moving Objects 2002 SIGMOD 6.4102904e-05
7,598 On Moving Object Queries (Extended Abstract) 2002 PODS 4.6975478e-05
7,635 On Nearest Neighbor Indexing of Nonlinear Trajectories 2003 PODS 4.6864934e-05
8,107 Adaptive Location Constraint Processing 2007 SIGMOD 4.5811252e-05
8,591 Boosting Moving Object Indexing through Velocity Partitioning 2012 VLDB 4.4851366e-05
Previous Page 1 / 1 Next

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
628 Indexing the Positions of Continuously Moving Objects 2000 SIGMOD 0.00018957327
1,004 On Indexing Mobile Objects 1999 PODS 0.00014694512
1,183 On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract) 1999 PODS 0.00013444058
1,499 Efficient Searching with Linear Constraints (Extended Abstract) 1998 PODS 0.00011643887
2,018 Path Caching: A Technique for Optimal External Searching (Extended Abstract) 1994 PODS 9.7852268e-05
3,794 OODB Indexing by Class-Division 1995 SIGMOD 6.7556886e-05
3,816 Temporal Conditions and Integrity Constraints in Active Database Systems 1995 SIGMOD 6.7297612e-05
4,769 DOMINO: Databases for Moving Objects Tracking 1999 SIGMOD 5.9287038e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
8,764 Dynamic Indexability and Lower Bounds for Dynamic One-Dimensional Range Query Indexes 2009 PODS 4.4520434e-05
11,558 On the I/O Complexity of the k-Nearest Neighbors Problem 2020 PODS 4.1905499e-05
8,895 Fast and Adaptive Indexing of Multi-Dimensional Observational Data 2016 VLDB 4.423024e-05
2,558 Novel Approaches to the Indexing of Moving Object Trajectories 2000 VLDB 8.5441554e-05
2,207 Independent Range Sampling 2014 PODS 9.2896559e-05
5,695 Optimal Indexing Using Near-Minimal Space [Extended Abstract] 2003 PODS 5.3675705e-05
1,004 On Indexing Mobile Objects 1999 PODS 0.00014694512
1,499 Efficient Searching with Linear Constraints (Extended Abstract) 1998 PODS 0.00011643887
1,766 Query and Update Efficient B+-Tree Based Indexing of Moving Objects 2004 VLDB 0.00010611043
1,183 On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract) 1999 PODS 0.00013444058