Query and Update Efficient B+-Tree Based Indexing of Moving Objects

Summary: Proposes a B+-tree index for moving objects by linearizing timestamped positions, letting one tree partition by time while preserving spatial locality and avoiding R-tree concurrency costs. Supports range, kNN, and continuous queries; outperforms TPR-tree and integrates readily into existing DBMS. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 9186
Venue: VLDB
Year: 2004
Pagerank: 0.00010611043
Overall Rank: 1,766 | 87.73%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 21 of 21 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
498	Large Scale Real-time Ridesharing with Service Guarantee on Road Networks	2014	VLDB	0.0002165768
1,554	Efficient Route Planning on Public Transportation Networks: A Labelling Approach	2015	SIGMOD	0.00011384233
1,916	A Generic Framework for Monitoring Continuous Spatial Queries over Moving Objects	2005	SIGMOD	0.00010110473
2,676	Effectively Learning Spatial Indices	2020	VLDB	8.326321e-05
4,585	ST2B-tree: A Self-Tunable Spatio-Temporal B+-tree Index for Moving Objects	2008	SIGMOD	6.0596467e-05
4,663	Towards Effective Indexing for Very Large Video Sequence Database	2005	SIGMOD	6.0066508e-05
5,579	Spitz: A Verifiable Database System	2020	VLDB	5.4224124e-05
6,171	A Benchmark for Evaluating Moving Object Indexes	2008	VLDB	5.1705603e-05
6,497	Progressive Top-K Nearest Neighbors Search in Large Road Networks	2020	SIGMOD	5.0324877e-05
6,534	Parallel Main-Memory Indexing for Moving-Object Query and Update Workloads	2012	SIGMOD	5.018905e-05
6,766	Workload-Aware Indexing of Continuously Moving Objects	2009	VLDB	4.9280867e-05
7,202	Indexing Methods for Moving Object Databases: Games and Other Applications	2013	SIGMOD	4.7975642e-05
7,300	Effectively Indexing Uncertain Moving Objects for Predictive Queries	2009	VLDB	4.7640746e-05
8,591	Boosting Moving Object Indexing through Velocity Partitioning	2012	VLDB	4.4851366e-05
8,992	Processing Proximity Relations in Road Networks	2010	SIGMOD	4.4111332e-05
9,166	An Adaptive Updating Protocol for Reducing Moving Object Database Workload	2010	VLDB	4.380727e-05
9,377	Towards Indexing Functions: Answering Scalar Product Queries	2014	SIGMOD	4.344689e-05
11,131	LARGE: A Length-Aggregation-based Grid Structure for Line Density Visualization	2024	VLDB	4.1905499e-05
11,372	Continuous Social Distance Monitoring in Indoor Space	2022	VLDB	4.1905499e-05
12,136	A Moving-Object Index for Efficient Query Processing with Peer-Wise Location Privacy	2012	VLDB	4.1905499e-05
12,146	MOIST: A Scalable and Parallel Moving Object Indexer with School Tracking	2012	VLDB	4.1905499e-05

Outgoing Citations (Sorted by Pagerank)

Showing 13 of 13 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
56	Direct Spatial Search on Pictorial Databases Using Packed R-trees	1985	SIGMOD	0.00065500256
628	Indexing the Positions of Continuously Moving Objects	2000	SIGMOD	0.00018957327
1,004	On Indexing Mobile Objects	1999	PODS	0.00014694512
1,055	The TPR*-Tree: An Optimized Spatio-Temporal Access Method for Predictive Queries	2003	VLDB	0.00014391376
1,250	Fractals for Secondary Key Retrieval	1989	PODS	0.00013037936
1,573	Performance of B-Tree Concurrency Control Algorithms	1991	SIGMOD	0.00011293832
2,492	Integrating the UB-Tree into a Database System Kernel	2000	VLDB	8.649434e-05
2,532	STRIPES: An Efficient Index for Predicted Trajectories	2004	SIGMOD	8.5886308e-05
3,042	High-Concurrency Locking in R-Trees	1995	VLDB	7.6669657e-05
3,301	Indexing the Distance: An Efficient Method to KNN Processing	2001	VLDB	7.2450912e-05
4,683	Supporting Frequent Updates in R-Trees: A Bottom-Up Approach	2003	VLDB	5.9940496e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
3,802	Time-Parameterized Queries in Spatio-Temporal Databases	2002	SIGMOD	6.7524078e-05
1,764	Indexing Moving Points (Extended Abstract)	2000	PODS	0.0001062234
4,683	Supporting Frequent Updates in R-Trees: A Bottom-Up Approach	2003	VLDB	5.9940496e-05
9,166	An Adaptive Updating Protocol for Reducing Moving Object Database Workload	2010	VLDB	4.380727e-05
4,585	ST2B-tree: A Self-Tunable Spatio-Temporal B+-tree Index for Moving Objects	2008	SIGMOD	6.0596467e-05
12,420	Towards Efficient Main-Memory Use For Optimum Tree Index Update	2008	VLDB	4.1905499e-05
7,300	Effectively Indexing Uncertain Moving Objects for Predictive Queries	2009	VLDB	4.7640746e-05
6,766	Workload-Aware Indexing of Continuously Moving Objects	2009	VLDB	4.9280867e-05
2,558	Novel Approaches to the Indexing of Moving Object Trajectories	2000	VLDB	8.5441554e-05
628	Indexing the Positions of Continuously Moving Objects	2000	SIGMOD	0.00018957327