BE-Tree: An Index Structure to Efficiently Match Boolean Expressions over High-dimensional Discrete Space

Summary: BE-Tree: dynamic index for efficient Boolean-expr matching in high-dim discrete spaces. 2-phase space-cutting leverages discrete-domain properties; self-adjusting policies adapt to workloads; evaluation shows superiority over top Boolean indexes. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 4481
Venue: SIGMOD
Year: 2011
Pagerank: 6.0082425e-05
Overall Rank: 6,016 | 58.73%
DOI: 10.1145/1989323.1989390

Incoming Non-self Citations Over Time

Authors

1. Mohammad Sadoghi (University of Toronto)
2. Hans-Arno Jacobsen (University of Toronto)

BibTeX Citation

@inproceedings{sadoghi_sigmod11,
        title = {{BE-Tree: An Index Structure to Efficiently Match Boolean Expressions over High-dimensional Discrete Space}},
        author = {Sadoghi, Mohammad and Jacobsen, Hans-Arno},
        series = {{SIGMOD} '11},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1989323.1989390},
        url = {https://dl.acm.org/doi/10.1145/1989323.1989390},
        year = {2011}
}

Incoming Citations (Sorted by Pagerank)

Showing 6 of 6 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,650	SKYPE: Top-k Spatial-keyword Publish/Subscribe Over Sliding Window	2016	VLDB	6.5863543e-05
6,861	An Efficient Publish/Subscribe Index for E-Commerce Databases	2014	VLDB	5.7517379e-05
7,042	Location-Aware Pub/Sub System: When Continuous Moving Queries Meet Dynamic Event Streams	2015	SIGMOD	5.7189999e-05
8,577	A-Tree: A Dynamic Data Structure for Efficiently Indexing Arbitrary Boolean Expressions	2021	SIGMOD	5.409313e-05
9,400	PS-Tree-Based Efficient Boolean Expression Matching for High-Dimensional and Dense Workloads	2019	VLDB	5.2755515e-05
10,520	Efficient Temporal Subgraph Management: A New Interval Index	2026	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 11 of 11 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
85	The X-tree: An Index Structure for High-Dimensional Data	1996	VLDB	0.00035405879
2,495	A Predicate Matching Algorithm for Database Rule Systems	1990	SIGMOD	8.5034389e-05
2,739	Indexing Boolean Expressions	2009	VLDB	8.1872509e-05
2,867	Cayuga: A High-Performance Event Processing Engine	2007	SIGMOD	8.016634e-05
3,342	High-Performance Dynamic Pattern Matching over Disordered Streams	2010	VLDB	7.4999147e-05
3,356	Benchmarking Declarative Approximate Selection Predicates	2007	SIGMOD	7.490881e-05
3,631	DejaVu: Declarative Pattern Matching over Live and Archived Streams of Events	2009	SIGMOD	7.2379481e-05
3,846	Efficient Event Processing through Reconfigurable Hardware for Algorithmic Trading	2010	VLDB	7.0765817e-05
4,914	A General Solution of the n-dimensional B-tree Problem	1995	SIGMOD	6.4477987e-05
5,199	Efficiently Evaluating Complex Boolean Expressions	2010	SIGMOD	6.3216824e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,047	Similarity Evaluation on Tree-structured Data	2005	SIGMOD
2	6,451	Efficient Search of Multidimensional B-Trees	1995	VLDB
3	1,492	BF-Tree: Approximate Tree Indexing	2014	VLDB
4	2,036	Bed-Tree: An All-Purpose Index Structure for String Similarity Search Based on Edit Distance	2010	SIGMOD
5	4,914	A General Solution of the n-dimensional B-tree Problem	1995	SIGMOD
6	3,742	RE-Tree: An Efficient Index Structure for Regular Expressions	2002	VLDB
7	8,003	Towards Designing and Learning Piecewise Space-Filling Curves	2023	VLDB
8	2,739	Indexing Boolean Expressions	2009	VLDB
9	9,400	PS-Tree-Based Efficient Boolean Expression Matching for High-Dimensional and Dense Workloads	2019	VLDB
10	8,577	A-Tree: A Dynamic Data Structure for Efficiently Indexing Arbitrary Boolean Expressions	2021	SIGMOD