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.00013047723
Overall Rank: 926 | 93.78%
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
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
1,294	Indexing Spatio-Temporal Trajectories with Chebyshev Polynomials	2004	SIGMOD	0.00011145111
1,304	Continuous Nearest Neighbor Search	2002	VLDB	0.00011104243
1,646	Indexing Moving Points (Extended Abstract)	2000	PODS	9.9929961e-05
2,064	Query and Update Efficient B+-Tree Based Indexing of Moving Objects	2004	VLDB	9.0942902e-05
2,309	STRIPES: An Efficient Index for Predicted Trajectories	2004	SIGMOD	8.6626683e-05
2,421	Novel Approaches to the Indexing of Moving Object Trajectories	2000	VLDB	8.4897323e-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,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
4,670	Supporting Frequent Updates in R-Trees: A Bottom-Up Approach	2003	VLDB	6.47772e-05
8,107	A Trajectory Splitting Model for Efficient Spatio-Temporal Indexing	2005	VLDB	5.3942942e-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
9,702	Towards Indexing Functions: Answering Scalar Product Queries	2014	SIGMOD	5.1381851e-05
12,762	Parsimonious Linear Fingerprinting for Time Series	2010	VLDB	4.9793485e-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.001992968
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0011405675
44	The R+-Tree: A Dynamic Multi-Dimensional Index for Objects	1987	VLDB	0.00045337853
1,237	Processing Queries By Linear Constraints	1997	PODS	0.00011396286
1,589	Efficient Searching with Linear Constraints (Extended Abstract)	1998	PODS	0.00010139591
1,903	The LSD tree: spatial access to multidimensional point and non-point objects	1989	VLDB	9.4032472e-05
2,047	Indexing for Data Models with Constraints and Classes (Extended Abstract)	1993	PODS	9.123147e-05
2,205	A Qualitative Comparison Study of Data Structures for Large Line Segment Databases	1992	SIGMOD	8.8556449e-05
4,716	On Indexing Line Segments	1990	VLDB	6.4554004e-05
7,454	The hB-Pi-tree: A Modified hB-tree Supporting Concurrency, Recovery and Node Consolidation	1995	VLDB	5.5230036e-05

Semantically Similar Papers

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