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: 1179
Venue: PODS
Year: 1999
Pagerank: 0.0001334014
Overall Rank: 896 | 93.86%
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
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
1,280	Indexing Spatio-Temporal Trajectories with Chebyshev Polynomials	2004	SIGMOD	0.00011354776
1,281	Continuous Nearest Neighbor Search	2002	VLDB	0.00011349245
1,611	Indexing Moving Points (Extended Abstract)	2000	PODS	0.00010218339
2,020	Query and Update Efficient B+-Tree Based Indexing of Moving Objects	2004	VLDB	9.2983514e-05
2,254	STRIPES: An Efficient Index for Predicted Trajectories	2004	SIGMOD	8.8603695e-05
2,375	Novel Approaches to the Indexing of Moving Object Trajectories	2000	VLDB	8.6753909e-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,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
4,569	Supporting Frequent Updates in R-Trees: A Bottom-Up Approach	2003	VLDB	6.6255507e-05
7,939	A Trajectory Splitting Model for Efficient Spatio-Temporal Indexing	2005	VLDB	5.5181056e-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
9,525	Towards Indexing Functions: Answering Scalar Product Queries	2014	SIGMOD	5.2555551e-05
12,471	Parsimonious Linear Fingerprinting for Time Series	2010	VLDB	5.093636e-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.0020210012
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.001157935
42	The R+-Tree: A Dynamic Multi-Dimensional Index for Objects	1987	VLDB	0.00046170812
1,219	Processing Queries By Linear Constraints	1997	PODS	0.00011620957
1,561	Efficient Searching with Linear Constraints (Extended Abstract)	1998	PODS	0.00010361147
1,877	The LSD tree: spatial access to multidimensional point and non-point objects	1989	VLDB	9.5658249e-05
2,003	Indexing for Data Models with Constraints and Classes (Extended Abstract)	1993	PODS	9.3214272e-05
2,168	A Qualitative Comparison Study of Data Structures for Large Line Segment Databases	1992	SIGMOD	9.0469646e-05
4,620	On Indexing Line Segments	1990	VLDB	6.6025691e-05
7,310	The hB-Pi-tree: A Modified hB-tree Supporting Concurrency, Recovery and Node Consolidation	1995	VLDB	5.6494751e-05

Semantically Similar Papers

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