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: 4739
Venue: SIGMOD
Year: 2013
Pagerank: 4.8019323e-05
Overall Rank: 7,203 | 49.90%
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,190	Overlap Interval Partition Join	2014	SIGMOD	5.6381091e-05
8,575	THERMAL-JOIN: A Scalable Spatial Join for Dynamic Workloads	2015	SIGMOD	4.4928872e-05
9,453	Towards Indexing Functions: Answering Scalar Product Queries	2014	SIGMOD	4.339214e-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.0032169493
6	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0016162015
354	Hilbert R-tree: An Improved R-tree Using Fractals	1994	VLDB	0.00026137988
631	Indexing the Positions of Continuously Moving Objects	2000	SIGMOD	0.00018935493
1,067	The TPR*-Tree: An Optimized Spatio-Temporal Access Method for Predictive Queries	2003	VLDB	0.00014327945
1,774	Query and Update Efficient B+-Tree Based Indexing of Moving Objects	2004	VLDB	0.00010604097
2,136	A Generic Approach to Bulk Loading Multidimensional Index Structures	1997	VLDB	9.4721139e-05
2,534	STRIPES: An Efficient Index for Predicted Trajectories	2004	SIGMOD	8.5890923e-05
3,615	Efficient Processing of Window Queries in The Pyramid Data Structure	1990	PODS	6.9127616e-05
4,612	Filter Trees for Managing Spatial Data Over a Range of Size Granularities	1996	VLDB	6.0484423e-05
5,860	Benchmarking Spatial Join Operations with Spatial Output	1995	VLDB	5.2990241e-05
6,537	Parallel Main-Memory Indexing for Moving-Object Query and Update Workloads	2012	SIGMOD	5.0235647e-05
8,592	Boosting Moving Object Indexing through Velocity Partitioning	2012	VLDB	4.4894309e-05
9,110	Database Research in Computer Games	2009	SIGMOD	4.3942503e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
8,986	Processing Proximity Relations in Road Networks	2010	SIGMOD	4.4153655e-05
6,076	Window Query-Optimal Clustering of Spatial Objects	1995	PODS	5.223696e-05
1,766	Indexing Moving Points (Extended Abstract)	2000	PODS	0.000106236
9,256	An Adaptive Updating Protocol for Reducing Moving Object Database Workload	2010	VLDB	4.3690661e-05
1,002	On Indexing Mobile Objects	1999	PODS	0.00014702555
6,819	Workload-Aware Indexing of Continuously Moving Objects	2009	VLDB	4.9158166e-05
631	Indexing the Positions of Continuously Moving Objects	2000	SIGMOD	0.00018935493
2,541	Novel Approaches to the Indexing of Moving Object Trajectories	2000	VLDB	8.5795657e-05
7,365	Effectively Indexing Uncertain Moving Objects for Predictive Queries	2009	VLDB	4.7517889e-05
1,774	Query and Update Efficient B+-Tree Based Indexing of Moving Objects	2004	VLDB	0.00010604097