On Indexing Mobile Objects

Summary: Dynamic external-memory indexes for mobile objects in 1D (with 2D extensions): a worst-case linear-space algorithm and a practical dynamic approximation with linear space and expected log query time. Also: restricted-case log queries, a d‑dimensional I/O lower bound, and initial experiments vs. traditional indexes. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h224bef402ca77b03
Venue: PODS
Year: 1999
Pagerank: 0.00013000067
Overall Rank: 930 | 93.77%
DOI: 10.1145/303976.304002

Incoming Non-self Citations Over Time

Authors

1. George Kollios (Polytechnic University)
2. Dimitrios Gunopulos (University of California Riverside)
3. Vassilis J. Tsotras (University of California Riverside)

BibTeX Citation

@inproceedings{kollios_pods99,
        address = {New York, NY, USA},
        series = {{PODS} '99},
        title = {{On Indexing Mobile Objects}},
        url = {https://dl.acm.org/doi/10.1145/303976.304002},
        doi = {10.1145/303976.304002},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Kollios, George and Gunopulos, Dimitrios and Tsotras, Vassilis J.},
        year = {1999}
}

Incoming Citations (Sorted by Pagerank)

Showing 21 of 21 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
576	Indexing the Positions of Continuously Moving Objects	2000	SIGMOD	0.00016130425
990	The TPR*-Tree: An Optimized Spatio-Temporal Access Method for Predictive Queries	2003	VLDB	0.00012637792
1,298	Indexing Spatio-Temporal Trajectories with Chebyshev Polynomials	2004	SIGMOD	0.00011104678
1,311	Continuous Nearest Neighbor Search	2002	VLDB	0.00011063629
1,654	Indexing Moving Points (Extended Abstract)	2000	PODS	9.9565797e-05
2,076	Query and Update Efficient B+-Tree Based Indexing of Moving Objects	2004	VLDB	9.0622765e-05
2,322	STRIPES: An Efficient Index for Predicted Trajectories	2004	SIGMOD	8.6301008e-05
2,436	Novel Approaches to the Indexing of Moving Object Trajectories	2000	VLDB	8.4576934e-05
2,923	Indexing Large Trajectory Data Sets With SETI*	2003	CIDR	7.8423791e-05
3,475	Prediction and Indexing of Moving Objects with Unknown Motion Patterns	2004	SIGMOD	7.2559012e-05
3,666	Time-Parameterized Queries in Spatio-Temporal Databases	2002	SIGMOD	7.0975312e-05
3,703	Roads, Codes, and Spatiotemporal Queries	2004	PODS	7.0617129e-05
4,269	Selectivity Estimation for Spatio-Temporal Queries to Moving Objects	2002	SIGMOD	6.6778228e-05
4,685	Supporting Frequent Updates in R-Trees: A Bottom-Up Approach	2003	VLDB	6.4533027e-05
8,132	A Trajectory Splitting Model for Efficient Spatio-Temporal Indexing	2005	VLDB	5.3739121e-05
8,211	On Moving Object Queries (Extended Abstract)	2002	PODS	5.3609606e-05
8,402	On Nearest Neighbor Indexing of Nonlinear Trajectories	2003	PODS	5.3233293e-05
8,981	Adaptive Location Constraint Processing	2007	SIGMOD	5.2326057e-05
9,463	Boosting Moving Object Indexing through Velocity Partitioning	2012	VLDB	5.1592099e-05
9,739	Towards Indexing Functions: Answering Scalar Product Queries	2014	SIGMOD	5.1187707e-05
12,811	Parsimonious Linear Fingerprinting for Time Series	2010	VLDB	4.9605343e-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.0019892478
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0011386412
44	The R+-Tree: A Dynamic Multi-Dimensional Index for Objects	1987	VLDB	0.00045231517
1,241	Processing Queries By Linear Constraints	1997	PODS	0.00011373551
1,594	Efficient Searching with Linear Constraints (Extended Abstract)	1998	PODS	0.00010103178
1,915	The LSD tree: spatial access to multidimensional point and non-point objects	1989	VLDB	9.368237e-05
2,051	Indexing for Data Models with Constraints and Classes (Extended Abstract)	1993	PODS	9.1080736e-05
2,217	A Qualitative Comparison Study of Data Structures for Large Line Segment Databases	1992	SIGMOD	8.8230488e-05
4,733	On Indexing Line Segments	1990	VLDB	6.4311314e-05
7,477	The hB-Pi-tree: A Modified hB-tree Supporting Concurrency, Recovery and Node Consolidation	1995	VLDB	5.5022037e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	576	Indexing the Positions of Continuously Moving Objects	2000	SIGMOD
2	8,988	Dynamic Data Structures for Document Collections and Graphs	2015	PODS
3	2,436	Novel Approaches to the Indexing of Moving Object Trajectories	2000	VLDB
4	4,862	A Lower Bound Theorem for Indexing Schemes and its Application to Multidimensional Range Queries	1998	PODS
5	3,825	Spatial Online Sampling and Aggregation	2016	VLDB
6	9,129	Dynamic Indexability and Lower Bounds for Dynamic One-Dimensional Range Query Indexes	2009	PODS
7	12,104	On the I/O Complexity of the k-Nearest Neighbors Problem	2020	PODS
8	2,051	Indexing for Data Models with Constraints and Classes (Extended Abstract)	1993	PODS
9	1,654	Indexing Moving Points (Extended Abstract)	2000	PODS
10	1,514	On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract)	1999	PODS