ST2B-tree: A Self-Tunable Spatio-Temporal B+-tree Index for Moving Objects

Summary: ST2 B-tree: a self-tunable spatio-temporal B+-tree for moving objects that adapts to evolving data and workloads. Online tuning framework reconfigures subtrees (reference points, grid size) with negligible overhead, enabling automatic, non-disruptive tuning and reduced query degradation. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 4037
Venue: SIGMOD
Year: 2008
Pagerank: 6.9403241e-05
Overall Rank: 4,043 | 72.27%
DOI: 10.1145/1376616.1376622

Incoming Non-self Citations Over Time

Authors

1. Su Chen (National University of Singapore)
2. Beng Chin Ooi (National University of Singapore)
3. Kian-Lee Tan (National University of Singapore)
4. Mario A. Nascimento (University of Alberta)

BibTeX Citation

@inproceedings{chen_sigmod08,
        title = {{ST2B-tree: A Self-Tunable Spatio-Temporal B+-tree Index for Moving Objects}},
        author = {Chen, Su and Ooi, Beng Chin and Tan, Kian-Lee and Nascimento, Mario A.},
        series = {{SIGMOD} '08},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1376616.1376622},
        url = {https://dl.acm.org/doi/10.1145/1376616.1376622},
        year = {2008}
}

Incoming Citations (Sorted by Pagerank)

Showing 12 of 12 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,646	An Efficient Query Indexing Mechanism for Filtering Geo-Textual Data	2013	SIGMOD	7.2282847e-05
5,740	A Benchmark for Evaluating Moving Object Indexes	2008	VLDB	6.1035012e-05
6,458	Workload-Aware Indexing of Continuously Moving Objects	2009	VLDB	5.8736158e-05
7,463	Effectively Indexing Uncertain Moving Objects for Predictive Queries	2009	VLDB	5.6111155e-05
8,499	THERMAL-JOIN: A Scalable Spatial Join for Dynamic Workloads	2015	SIGMOD	5.4133616e-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
10,990	Polaris: An Interactive and Scalable Data Infrastructure for Polar Science	2025	VLDB	5.093636e-05
11,193	BT-Tree: A Reinforcement Learning Based Index for Big Trajectory Data	2024	SIGMOD	5.093636e-05
11,613	Budget-Conscious Fine-Grained Configuration Optimization for Spatio-Temporal Applications	2022	VLDB	5.093636e-05
12,334	MOIST: A Scalable and Parallel Moving Object Indexer with School Tracking	2012	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 9 of 9 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
156	An Efficient, Cost-Driven Index Selection Tool for Microsoft SQL Server	1997	VLDB	0.00028636811
291	OPTICS: Ordering Points To Identify the Clustering Structure	1999	SIGMOD	0.00022264197
560	Indexing the Positions of Continuously Moving Objects	2000	SIGMOD	0.00016525569
936	The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems	1990	VLDB	0.00013092484
957	The TPR*-Tree: An Optimized Spatio-Temporal Access Method for Predictive Queries	2003	VLDB	0.00012962576
1,201	SINA: Scalable Incremental Processing of Continuous Queries in Spatio-temporal Databases	2004	SIGMOD	0.00011674339
2,020	Query and Update Efficient B+-Tree Based Indexing of Moving Objects	2004	VLDB	9.2983514e-05
2,205	Conceptual Partitioning: An Efficient Method for Continuous Nearest Neighbor Monitoring	2005	SIGMOD	8.9591376e-05
2,254	STRIPES: An Efficient Index for Predicted Trajectories	2004	SIGMOD	8.8603695e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	560	Indexing the Positions of Continuously Moving Objects	2000	SIGMOD
2	2,853	Indexing Large Trajectory Data Sets With SETI*	2003	CIDR
3	3,581	Time-Parameterized Queries in Spatio-Temporal Databases	2002	SIGMOD
4	6,458	Workload-Aware Indexing of Continuously Moving Objects	2009	VLDB
5	7,463	Effectively Indexing Uncertain Moving Objects for Predictive Queries	2009	VLDB
6	9,887	Adaptive Indexing of Objects with Spatial Extent	2023	VLDB
7	957	The TPR*-Tree: An Optimized Spatio-Temporal Access Method for Predictive Queries	2003	VLDB
8	9,322	An Adaptive Updating Protocol for Reducing Moving Object Database Workload	2010	VLDB
9	2,375	Novel Approaches to the Indexing of Moving Object Trajectories	2000	VLDB
10	2,020	Query and Update Efficient B+-Tree Based Indexing of Moving Objects	2004	VLDB