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: 11073
Venue: VLDB
Year: 2014
Pagerank: 0.00010588267
Overall Rank: 1,492 | 89.77%
DOI: 10.14778/2733085.2733094

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 19 of 19 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
43	The Case for Learned Index Structures	2018	SIGMOD	0.00046060254
447	ALEX: An Updatable Adaptive Learned Index	2020	SIGMOD	0.00018322593
477	The PGM-index: a fully-dynamic compressed learned index with provable worst-case bounds	2020	VLDB	0.00017851226
790	FITing-Tree: A Data-aware Index Structure	2019	SIGMOD	0.0001401445
2,213	Designing Succinct Secondary Indexing Mechanism by Exploiting Column Correlations	2019	SIGMOD	8.9410226e-05
2,233	FINEdex: A Fine-grained Learned Index Scheme for Scalable and Concurrent Memory Systems	2022	VLDB	8.8968964e-05
2,755	Lethe: A Tunable Delete-Aware LSM Engine	2020	SIGMOD	8.163097e-05
3,378	A Hybrid B+-tree as Solution for In-Memory Indexing on CPU-GPU Heterogeneous Computing Platforms	2016	SIGMOD	7.4587887e-05
3,413	Slalom: Coasting Through Raw Data via Adaptive Partitioning and Indexing	2017	VLDB	7.4326381e-05
3,576	Two Birds, One Stone: A Fast, yet Lightweight, Indexing Scheme for Modern Database Systems	2017	VLDB	7.2936598e-05
4,300	DILI: A Distribution-Driven Learned Index	2023	VLDB	6.773869e-05
4,826	Design Tradeoffs of Data Access Methods	2016	SIGMOD	6.4904836e-05
4,946	Spruce: A Fast yet Space-saving Structure for Dynamic Graph Storage	2024	SIGMOD	6.4319457e-05
5,447	FILM: a Fully Learned Index for Larger-than-Memory Databases	2023	VLDB	6.2149491e-05
8,056	Sieve: A Learned Data-Skipping Index for Data Analytics	2023	VLDB	5.4983582e-05
10,468	LiveBin: A Localized and Version-Aware Binned Scan Index	2026	SIGMOD	5.093636e-05
10,489	RadixGraph: A Fast, Space-Optimized Data Structure for Dynamic Graph Storage	2026	SIGMOD	5.093636e-05
11,878	HERMIT in Action: Succinct Secondary Indexing Mechanism via Correlation Exploration	2019	VLDB	5.093636e-05
11,989	Alpine: Efficient In situ Data Exploration in the Presence of Updates	2017	SIGMOD	5.093636e-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
104	Improved Query Performance with Variant Indexes	1997	SIGMOD	0.00033932213
227	Small Materialized Aggregates: A Light Weight Index Structure for Data Warehousing	1998	VLDB	0.00023958508
512	Tree Indexing on Solid State Drives	2010	VLDB	0.00017196795
789	Don't Thrash: How to Cache Your Hash on Flash	2012	VLDB	0.0001401724
961	Lazy-Adaptive Tree: An Optimized Index Structure for Flash Devices	2009	VLDB	0.00012941098
999	Flashing Up the Storage Layer	2008	VLDB	0.00012740138
1,105	FlashLogging: Exploiting Flash Devices for Synchronous Logging Performance	2009	SIGMOD	0.00012151254
1,311	uFLIP: Understanding Flash IO Patterns	2009	CIDR	0.00011207712
1,455	Query Processing Techniques for Solid State Drives	2009	SIGMOD	0.00010733981
1,507	Column Imprints: A Secondary Index Structure	2013	SIGMOD	0.0001054177
2,312	Online Aggregation and Continuous Query support in MapReduce	2010	SIGMOD	8.7642158e-05
3,747	B+-tree Index Optimization by Exploiting Internal Parallelism of Flash-based Solid State Drives	2012	VLDB	7.1555585e-05
5,564	MaSM: Efficient Online Updates in Data Warehouses	2011	SIGMOD	6.1716245e-05
6,676	Petabyte Scale Databases and Storage Systems at Facebook	2013	SIGMOD	5.8056697e-05

Semantically Similar Papers

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