BF-Tree: Approximate Tree Indexing

Summary: BF-Trees use Bloom filters in approximate tree indexes to trade pruning accuracy for dramatically lower footprint on SSDs. Exploiting temporal ordering/partitioning, they achieve 1.6–48× smaller indexes with competitive search latency across synthetic, TPC-H, and monitoring workloads. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: h6562c3f6ce5c9cd4
Venue: VLDB
Year: 2014
Pagerank: 0.00010448376
Overall Rank: 1,506 | 89.88%
DOI: 10.14778/2733085.2733094
PDF: Download (CC BY-NC-ND 3.0)

Incoming Non-self Citations Over Time

Authors

1. Manos Athanassoulis (EPFL)
2. Anastasia Ailamaki (EPFL)

BibTeX Citation

@article{athanassoulis_vldb14,
        title = {{BF-Tree: Approximate Tree Indexing}},
        author = {Athanassoulis, Manos and Ailamaki, Anastasia},
        journal = {PVLDB},
        series = {{VLDB} '14},
        volume = {7},
        number = {14},
        pages = {1881--1892},
        doi = {10.14778/2733085.2733094},
        url = {https://doi.org/10.14778/2733085.2733094},
        year = {2014}
}

Incoming Citations (Sorted by Pagerank)

Showing 20 of 20 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
40	The Case for Learned Index Structures	2018	SIGMOD	0.00046363107
422	ALEX: An Updatable Adaptive Learned Index	2020	SIGMOD	0.00018488849
458	The PGM-index: a fully-dynamic compressed learned index with provable worst-case bounds	2020	VLDB	0.00017880664
768	FITing-Tree: A Data-aware Index Structure	2019	SIGMOD	0.00014107655
2,237	Designing Succinct Secondary Indexing Mechanism by Exploiting Column Correlations	2019	SIGMOD	8.7738349e-05
2,270	FINEdex: A Fine-grained Learned Index Scheme for Scalable and Concurrent Memory Systems	2022	VLDB	8.7166469e-05
2,788	Lethe: A Tunable Delete-Aware LSM Engine	2020	SIGMOD	8.0114055e-05
3,374	A Hybrid B+-tree as Solution for In-Memory Indexing on CPU-GPU Heterogeneous Computing Platforms	2016	SIGMOD	7.3606793e-05
3,445	Slalom: Coasting Through Raw Data via Adaptive Partitioning and Indexing	2017	VLDB	7.2911896e-05
3,592	Two Birds, One Stone: A Fast, yet Lightweight, Indexing Scheme for Modern Database Systems	2017	VLDB	7.1807308e-05
4,366	DILI: A Distribution-Driven Learned Index	2023	VLDB	6.6330579e-05
4,875	Design Tradeoffs of Data Access Methods	2016	SIGMOD	6.3699172e-05
5,068	Spruce: A Fast yet Space-saving Structure for Dynamic Graph Storage	2024	SIGMOD	6.2872138e-05
5,405	FILM: a Fully Learned Index for Larger-than-Memory Databases	2023	VLDB	6.1435108e-05
8,207	Sieve: A Learned Data-Skipping Index for Data Analytics	2023	VLDB	5.3763264e-05
10,666	LiveBin: A Localized and Version-Aware Binned Scan Index	2026	SIGMOD	4.9769913e-05
10,687	RadixGraph: A Fast, Space-Optimized Data Structure for Dynamic Graph Storage	2026	SIGMOD	4.9769913e-05
11,001	Demonstrating Indexing for Near-Sorted Data	2026	VLDB	4.9769913e-05
12,184	HERMIT in Action: Succinct Secondary Indexing Mechanism via Correlation Exploration	2019	VLDB	4.9769913e-05
12,293	Alpine: Efficient In situ Data Exploration in the Presence of Updates	2017	SIGMOD	4.9769913e-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
107	Improved Query Performance with Variant Indexes	1997	SIGMOD	0.00033459417
216	Small Materialized Aggregates: A Light Weight Index Structure for Data Warehousing	1998	VLDB	0.00024485637
513	Tree Indexing on Solid State Drives	2010	VLDB	0.00017040424
789	Don't Thrash: How to Cache Your Hash on Flash	2012	VLDB	0.00013972179
982	Lazy-Adaptive Tree: An Optimized Index Structure for Flash Devices	2009	VLDB	0.00012712097
1,014	Flashing Up the Storage Layer	2008	VLDB	0.0001250085
1,124	FlashLogging: Exploiting Flash Devices for Synchronous Logging Performance	2009	SIGMOD	0.00011923526
1,334	uFLIP: Understanding Flash IO Patterns	2009	CIDR	0.00010992028
1,485	Query Processing Techniques for Solid State Drives	2009	SIGMOD	0.00010531092
1,531	Column Imprints: A Secondary Index Structure	2013	SIGMOD	0.00010344951
2,362	Online Aggregation and Continuous Query support in MapReduce	2010	SIGMOD	8.5729053e-05
3,795	B+-tree Index Optimization by Exploiting Internal Parallelism of Flash-based Solid State Drives	2012	VLDB	7.0144802e-05
5,640	MaSM: Efficient Online Updates in Data Warehouses	2011	SIGMOD	6.0541838e-05
6,806	Petabyte Scale Databases and Storage Systems at Facebook	2013	SIGMOD	5.6768452e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,587	Efficient Search of Multidimensional B-Trees	1995	VLDB
2	8,865	Adaptive Index Structures	2002	VLDB
3	7,029	BP-tree: Overcoming the Point-Range Operation Tradeoff for In-Memory B-trees	2023	VLDB
4	6,613	Making In-Memory Learned Indexes Efficient on Disk	2024	SIGMOD
5	5,026	A General Solution of the n-dimensional B-tree Problem	1995	SIGMOD
6	2,065	Query and Update Efficient B+-Tree Based Indexing of Moving Objects	2004	VLDB
7	513	Tree Indexing on Solid State Drives	2010	VLDB
8	9,295	Revisiting B-tree Compression: An Experimental Study	2024	SIGMOD
9	7,974	Efficient B-tree Based Indexing for Cloud Data Processing	2010	VLDB
10	6,486	Bf-Tree: A Modern Read-Write-Optimized Concurrent Larger-Than-Memory Range Index	2024	VLDB