DBScholar

Back to papers

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
9376
Venue
VLDB
Year
2004
Pagerank
9.2983514e-05
Overall Rank
2,020 | 86.15%
DOI
10.1016/B978-012088469-8.50068-1

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@article{jensen_vldb04,
        title = {{Query and Update Efficient B+-Tree Based Indexing of Moving Objects}},
        author = {Jensen, Christian S. and Lin, Dan and Ooi, Beng Chin},
        journal = {PVLDB},
        series = {{VLDB} '04},
        pages = {768--779},
        doi = {10.1016/B978-012088469-8.50068-1},
        url = {https://doi.org/10.1016/B978-012088469-8.50068-1},
        year = {2004}
}

Incoming Citations (Sorted by Pagerank)

Showing 21 of 21 citing papers.

Rank Citing Paper Year Venue Pagerank
1,035 Large Scale Real-time Ridesharing with Service Guarantee on Road Networks 2014 VLDB 0.00012505885
1,598 Efficient Route Planning on Public Transportation Networks: A Labelling Approach 2015 SIGMOD 0.00010242826
1,698 A Generic Framework for Monitoring Continuous Spatial Queries over Moving Objects 2005 SIGMOD 9.980335e-05
1,840 Effectively Learning Spatial Indices 2020 VLDB 9.6404567e-05
4,043 ST2B-tree: A Self-Tunable Spatio-Temporal B+-tree Index for Moving Objects 2008 SIGMOD 6.9403241e-05
4,618 Towards Effective Indexing for Very Large Video Sequence Database 2005 SIGMOD 6.6036373e-05
5,213 Spitz: A Verifiable Database System 2020 VLDB 6.3143934e-05
5,740 A Benchmark for Evaluating Moving Object Indexes 2008 VLDB 6.1035012e-05
5,987 Progressive Top-K Nearest Neighbors Search in Large Road Networks 2020 SIGMOD 6.0183678e-05
6,458 Workload-Aware Indexing of Continuously Moving Objects 2009 VLDB 5.8736158e-05
6,488 Parallel Main-Memory Indexing for Moving-Object Query and Update Workloads 2012 SIGMOD 5.865078e-05
7,070 Indexing Methods for Moving Object Databases: Games and Other Applications 2013 SIGMOD 5.7116663e-05
7,463 Effectively Indexing Uncertain Moving Objects for Predictive Queries 2009 VLDB 5.6111155e-05
9,143 Processing Proximity Relations in Road Networks 2010 SIGMOD 5.3153925e-05
9,254 Boosting Moving Object Indexing through Velocity Partitioning 2012 VLDB 5.297624e-05
9,322 An Adaptive Updating Protocol for Reducing Moving Object Database Workload 2010 VLDB 5.289545e-05
9,525 Towards Indexing Functions: Answering Scalar Product Queries 2014 SIGMOD 5.2555551e-05
11,334 LARGE: A Length-Aggregation-based Grid Structure for Line Density Visualization 2024 VLDB 5.093636e-05
11,568 Continuous Social Distance Monitoring in Indoor Space 2022 VLDB 5.093636e-05
12,324 A Moving-Object Index for Efficient Query Processing with Peer-Wise Location Privacy 2012 VLDB 5.093636e-05
12,334 MOIST: A Scalable and Parallel Moving Object Indexer with School Tracking 2012 VLDB 5.093636e-05
Previous Page 1 / 1 Next

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.0020210012
4 The R*-tree: An Efficient and Robust Access Method for Points and Rectangles 1990 SIGMOD 0.001157935
116 Direct Spatial Search on Pictorial Databases Using Packed R-trees 1985 SIGMOD 0.0003221055
560 Indexing the Positions of Continuously Moving Objects 2000 SIGMOD 0.00016525569
896 On Indexing Mobile Objects 1999 PODS 0.0001334014
957 The TPR*-Tree: An Optimized Spatio-Temporal Access Method for Predictive Queries 2003 VLDB 0.00012962576
1,202 Fractals for Secondary Key Retrieval 1989 PODS 0.00011672157
1,663 Performance of B-Tree Concurrency Control Algorithms 1991 SIGMOD 0.00010073735
2,155 Integrating the UB-Tree into a Database System Kernel 2000 VLDB 9.0713545e-05
2,254 STRIPES: An Efficient Index for Predicted Trajectories 2004 SIGMOD 8.8603695e-05
2,979 Indexing the Distance: An Efficient Method to KNN Processing 2001 VLDB 7.8984588e-05
3,057 High-Concurrency Locking in R-Trees 1995 VLDB 7.807389e-05
4,569 Supporting Frequent Updates in R-Trees: A Bottom-Up Approach 2003 VLDB 6.6255507e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 3,581 Time-Parameterized Queries in Spatio-Temporal Databases 2002 SIGMOD
2 1,611 Indexing Moving Points (Extended Abstract) 2000 PODS
3 4,569 Supporting Frequent Updates in R-Trees: A Bottom-Up Approach 2003 VLDB
4 9,322 An Adaptive Updating Protocol for Reducing Moving Object Database Workload 2010 VLDB
5 4,043 ST2B-tree: A Self-Tunable Spatio-Temporal B+-tree Index for Moving Objects 2008 SIGMOD
6 12,605 Towards Efficient Main-Memory Use For Optimum Tree Index Update 2008 VLDB
7 7,463 Effectively Indexing Uncertain Moving Objects for Predictive Queries 2009 VLDB
8 6,458 Workload-Aware Indexing of Continuously Moving Objects 2009 VLDB
9 2,375 Novel Approaches to the Indexing of Moving Object Trajectories 2000 VLDB
10 560 Indexing the Positions of Continuously Moving Objects 2000 SIGMOD