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: 4740
Venue: SIGMOD
Year: 2013
Pagerank: 4.7975642e-05
Overall Rank: 7,202 | 49.95%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,197	Overlap Interval Partition Join	2014	SIGMOD	5.6308314e-05
8,572	THERMAL-JOIN: A Scalable Spatial Join for Dynamic Workloads	2015	SIGMOD	4.4885798e-05
9,377	Towards Indexing Functions: Answering Scalar Product Queries	2014	SIGMOD	4.344689e-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.0032118946
6	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0016113151
356	Hilbert R-tree: An Improved R-tree Using Fractals	1994	VLDB	0.00026091196
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
1,766	Query and Update Efficient B+-Tree Based Indexing of Moving Objects	2004	VLDB	0.00010611043
2,139	A Generic Approach to Bulk Loading Multidimensional Index Structures	1997	VLDB	9.4618572e-05
2,532	STRIPES: An Efficient Index for Predicted Trajectories	2004	SIGMOD	8.5886308e-05
3,619	Efficient Processing of Window Queries in The Pyramid Data Structure	1990	PODS	6.9061356e-05
4,613	Filter Trees for Managing Spatial Data Over a Range of Size Granularities	1996	VLDB	6.0427196e-05
5,864	Benchmarking Spatial Join Operations with Spatial Output	1995	VLDB	5.2947135e-05
6,534	Parallel Main-Memory Indexing for Moving-Object Query and Update Workloads	2012	SIGMOD	5.018905e-05
8,591	Boosting Moving Object Indexing through Velocity Partitioning	2012	VLDB	4.4851366e-05
9,109	Database Research in Computer Games	2009	SIGMOD	4.390048e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
8,992	Processing Proximity Relations in Road Networks	2010	SIGMOD	4.4111332e-05
6,073	Window Query-Optimal Clustering of Spatial Objects	1995	PODS	5.2215154e-05
1,764	Indexing Moving Points (Extended Abstract)	2000	PODS	0.0001062234
9,166	An Adaptive Updating Protocol for Reducing Moving Object Database Workload	2010	VLDB	4.380727e-05
1,004	On Indexing Mobile Objects	1999	PODS	0.00014694512
6,766	Workload-Aware Indexing of Continuously Moving Objects	2009	VLDB	4.9280867e-05
628	Indexing the Positions of Continuously Moving Objects	2000	SIGMOD	0.00018957327
2,558	Novel Approaches to the Indexing of Moving Object Trajectories	2000	VLDB	8.5441554e-05
7,300	Effectively Indexing Uncertain Moving Objects for Predictive Queries	2009	VLDB	4.7640746e-05
1,766	Query and Update Efficient B+-Tree Based Indexing of Moving Objects	2004	VLDB	0.00010611043