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: hf2cf1b45a5d69b4f
Venue: SIGMOD
Year: 2008
Pagerank: 6.787575e-05
Overall Rank: 4,134 | 72.21%
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,731	An Efficient Query Indexing Mechanism for Filtering Geo-Textual Data	2013	SIGMOD	7.0676307e-05
5,863	A Benchmark for Evaluating Moving Object Indexes	2008	VLDB	5.9667924e-05
6,578	Workload-Aware Indexing of Continuously Moving Objects	2009	VLDB	5.744723e-05
7,584	Effectively Indexing Uncertain Moving Objects for Predictive Queries	2009	VLDB	5.4903974e-05
8,658	THERMAL-JOIN: A Scalable Spatial Join for Dynamic Workloads	2015	SIGMOD	5.2933372e-05
9,427	Boosting Moving Object Indexing through Velocity Partitioning	2012	VLDB	5.178769e-05
9,501	An Adaptive Updating Protocol for Reducing Moving Object Database Workload	2010	VLDB	5.1708619e-05
9,702	Towards Indexing Functions: Answering Scalar Product Queries	2014	SIGMOD	5.1381851e-05
10,002	BT-Tree: A Reinforcement Learning Based Index for Big Trajectory Data	2024	SIGMOD	5.0979044e-05
11,367	Polaris: An Interactive and Scalable Data Infrastructure for Polar Science	2025	VLDB	4.9793485e-05
11,921	Budget-Conscious Fine-Grained Configuration Optimization for Spatio-Temporal Applications	2022	VLDB	4.9793485e-05
12,625	MOIST: A Scalable and Parallel Moving Object Indexer with School Tracking	2012	VLDB	4.9793485e-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
151	An Efficient, Cost-Driven Index Selection Tool for Microsoft SQL Server	1997	VLDB	0.00028672526
300	OPTICS: Ordering Points To Identify the Clustering Structure	1999	SIGMOD	0.00021810545
574	Indexing the Positions of Continuously Moving Objects	2000	SIGMOD	0.00016173068
965	The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems	1990	VLDB	0.00012809362
985	The TPR*-Tree: An Optimized Spatio-Temporal Access Method for Predictive Queries	2003	VLDB	0.00012685169
1,227	SINA: Scalable Incremental Processing of Continuous Queries in Spatio-temporal Databases	2004	SIGMOD	0.000114264
2,064	Query and Update Efficient B+-Tree Based Indexing of Moving Objects	2004	VLDB	9.0942902e-05
2,243	Conceptual Partitioning: An Efficient Method for Continuous Nearest Neighbor Monitoring	2005	SIGMOD	8.7678247e-05
2,309	STRIPES: An Efficient Index for Predicted Trajectories	2004	SIGMOD	8.6626683e-05

Semantically Similar Papers

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