A-Tree: A Dynamic Data Structure for Efficiently Indexing Arbitrary Boolean Expressions

Summary: Proposes A-Tree, a dynamic, multirooted index for arbitrary Boolean expressions that shares predicates and subexpressions to avoid exponential expansion. Self-adjusting, with event-matching optimizations, it outperforms existing arbitrary- and conjunctive-expression matchers in memory, time, and index construction. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h2914a58340737bd1
Venue: SIGMOD
Year: 2021
Pagerank: 5.2879425e-05
Overall Rank: 8,745 | 41.21%
DOI: 10.1145/3448016.3457266

Incoming Non-self Citations Over Time

Authors

1. Shuping Ji (Institute of Software, Chinese Academy of Sciences)
2. Hans-Arno Jacobsen (University of Toronto)

BibTeX Citation

@inproceedings{ji_sigmod21,
        title = {{A-Tree: A Dynamic Data Structure for Efficiently Indexing Arbitrary Boolean Expressions}},
        author = {Ji, Shuping and Jacobsen, Hans-Arno},
        series = {{SIGMOD} '21},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3448016.3457266},
        url = {https://dl.acm.org/doi/10.1145/3448016.3457266},
        year = {2021}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
9,052	Optimizing Disjunctive Queries with Tagged Execution	2024	SIGMOD	5.230408e-05
10,705	Efficient Temporal Subgraph Management: A New Interval Index	2026	VLDB	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 18 of 18 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
241	High-Performance Complex Event Processing over Streams	2006	SIGMOD	0.00023419748
374	Storing and Querying Ordered XML Using a Relational Database System	2002	SIGMOD	0.00019707844
451	Filtering Algorithms and Implementation for Very Fast Publish/Subscribe Systems	2001	SIGMOD	0.00018025073
733	ORDPATHs: Insert-Friendly XML Node Labels	2004	SIGMOD	0.00014379182
1,029	ZStream: A Cost-based Query Processor for Adaptively Detecting Composite Events	2009	SIGMOD	0.00012416974
1,378	Execution Strategies for SQL Subqueries	2007	SIGMOD	0.00010864448
2,363	SASE: Complex Event Processing over Streams	2007	CIDR	8.5673723e-05
2,542	A Predicate Matching Algorithm for Database Rule Systems	1990	SIGMOD	8.3237167e-05
2,793	Indexing Boolean Expressions	2009	VLDB	8.0052633e-05
2,935	Cayuga: A High-Performance Event Processing Engine	2007	SIGMOD	7.8379783e-05
3,410	Scalable Pattern Sharing on Event Streams	2016	SIGMOD	7.3258817e-05
3,600	Practical Applications of Triggers and Constraints: Successes and Lingering Issues	2000	VLDB	7.1765044e-05
5,059	Active Complex Event Processing over Event Streams	2011	VLDB	6.2917112e-05
5,324	Efficiently Evaluating Complex Boolean Expressions	2010	SIGMOD	6.179987e-05
5,655	Scalable Ranked Publish/Subscribe	2008	VLDB	6.0501178e-05
6,140	BE-Tree: An Index Structure to Efficiently Match Boolean Expressions over High-dimensional Discrete Space	2011	SIGMOD	5.8734337e-05
7,007	An Efficient Publish/Subscribe Index for E-Commerce Databases	2014	VLDB	5.6226844e-05
9,582	PS-Tree-Based Efficient Boolean Expression Matching for High-Dimensional and Dense Workloads	2019	VLDB	5.1571823e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	10,315	AB-tree: Index for Concurrent Random Sampling and Updates	2022	VLDB
2	6,973	A Scalable Index for Top-k Subtree Similarity Queries	2019	SIGMOD
3	7,670	Efficient Indexing and Querying over Syntactically Annotated Trees	2012	VLDB
4	1,793	The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation	2000	VLDB
5	5,421	Efficient Processing of XML Twig Queries with OR-Predicates	2004	SIGMOD
6	5,324	Efficiently Evaluating Complex Boolean Expressions	2010	SIGMOD
7	3,829	RE-Tree: An Efficient Index Structure for Regular Expressions	2002	VLDB
8	2,793	Indexing Boolean Expressions	2009	VLDB
9	9,582	PS-Tree-Based Efficient Boolean Expression Matching for High-Dimensional and Dense Workloads	2019	VLDB
10	6,140	BE-Tree: An Index Structure to Efficiently Match Boolean Expressions over High-dimensional Discrete Space	2011	SIGMOD