Indexing Methods for Moving Object Databases: Games and Other Applications

Summary: Proposes the loose quadtree/octree for moving objects, expanding cells by p so an object's expanded cell size is independent of position. Shows O(1) updates for p≥0.5; p near 1 yields peak throughput, validated on game-like motion and N-body workloads. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 4801
Venue: SIGMOD
Year: 2013
Pagerank: 5.7116663e-05
Overall Rank: 7,070 | 51.50%
DOI: 10.1145/2463676.2465332

Incoming Non-self Citations Over Time

Authors

1. Hanan Samet (University of Maryland)
2. Jagan Sankaranarayanan (NEC Corporation; University of Maryland)
3. Michael Auerbach (University of Maryland)

BibTeX Citation

@inproceedings{samet_sigmod13,
        title = {{Indexing Methods for Moving Object Databases: Games and Other Applications}},
        author = {Samet, Hanan and Sankaranarayanan, Jagan and Auerbach, Michael},
        series = {{SIGMOD} '13},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/2463676.2465332},
        url = {https://dl.acm.org/doi/10.1145/2463676.2465332},
        year = {2013}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,482	Overlap Interval Partition Join	2014	SIGMOD	6.6753072e-05
8,499	THERMAL-JOIN: A Scalable Spatial Join for Dynamic Workloads	2015	SIGMOD	5.4133616e-05
9,525	Towards Indexing Functions: Answering Scalar Product Queries	2014	SIGMOD	5.2555551e-05

Outgoing Citations (Sorted by Pagerank)

Showing 14 of 14 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
329	Hilbert R-tree: An Improved R-tree Using Fractals	1994	VLDB	0.00021068647
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,901	A Generic Approach to Bulk Loading Multidimensional Index Structures	1997	VLDB	9.5068846e-05
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
3,668	Efficient Processing of Window Queries in The Pyramid Data Structure	1990	PODS	7.2125892e-05
5,202	Filter Trees for Managing Spatial Data Over a Range of Size Granularities	1996	VLDB	6.3194496e-05
5,795	Benchmarking Spatial Join Operations with Spatial Output	1995	VLDB	6.0859946e-05
6,488	Parallel Main-Memory Indexing for Moving-Object Query and Update Workloads	2012	SIGMOD	5.865078e-05
9,254	Boosting Moving Object Indexing through Velocity Partitioning	2012	VLDB	5.297624e-05
9,255	Database Research in Computer Games	2009	SIGMOD	5.297624e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	9,143	Processing Proximity Relations in Road Networks	2010	SIGMOD
2	6,089	Window Query-Optimal Clustering of Spatial Objects	1995	PODS
3	1,611	Indexing Moving Points (Extended Abstract)	2000	PODS
4	9,322	An Adaptive Updating Protocol for Reducing Moving Object Database Workload	2010	VLDB
5	896	On Indexing Mobile Objects	1999	PODS
6	6,458	Workload-Aware Indexing of Continuously Moving Objects	2009	VLDB
7	560	Indexing the Positions of Continuously Moving Objects	2000	SIGMOD
8	2,375	Novel Approaches to the Indexing of Moving Object Trajectories	2000	VLDB
9	7,463	Effectively Indexing Uncertain Moving Objects for Predictive Queries	2009	VLDB
10	2,020	Query and Update Efficient B+-Tree Based Indexing of Moving Objects	2004	VLDB