Back to papers
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
- 6157
- Venue
- SIGMOD
- Year
- 2021
- Pagerank
- 4.4902253e-05
- Overall Rank
- 8,587 | 40.27%
- DOI
-
10.1145/3448016.3457266
Incoming Non-self Citations Over Time
Incoming Citations (Sorted by Pagerank)
Showing 2 of 2 citing papers.
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 |
| 259 |
High-Performance Complex Event Processing over Streams |
2006 |
SIGMOD |
0.00030174924 |
| 446 |
Storing and Querying Ordered XML Using a Relational Database System |
2002 |
SIGMOD |
0.00022925415 |
| 500 |
Filtering Algorithms and Implementation for Very Fast Publish/Subscribe Systems |
2001 |
SIGMOD |
0.00021637423 |
| 849 |
ORDPATHs: Insert-Friendly XML Node Labels |
2004 |
SIGMOD |
0.00015962987 |
| 1,418 |
ZStream: A Cost-based Query Processor for Adaptively Detecting Composite Events |
2009 |
SIGMOD |
0.00012089363 |
| 1,582 |
Execution Strategies for SQL Subqueries |
2007 |
SIGMOD |
0.00011265079 |
| 2,305 |
A Predicate Matching Algorithm for Database Rule Systems |
1990 |
SIGMOD |
9.062692e-05 |
| 2,340 |
SASE: Complex Event Processing over Streams |
2007 |
CIDR |
9.004232e-05 |
| 2,949 |
Indexing Boolean Expressions |
2009 |
VLDB |
7.8340452e-05 |
| 3,212 |
Cayuga: A High-Performance Event Processing Engine |
2007 |
SIGMOD |
7.3730439e-05 |
| 3,224 |
Practical Applications of Triggers and Constraints: Successes and Lingering Issues |
2000 |
VLDB |
7.3496543e-05 |
| 4,007 |
Scalable Pattern Sharing on Event Streams |
2016 |
SIGMOD |
6.5397067e-05 |
| 5,182 |
Active Complex Event Processing over Event Streams |
2011 |
VLDB |
5.6410216e-05 |
| 5,391 |
Scalable Ranked Publish/Subscribe |
2008 |
VLDB |
5.533552e-05 |
| 5,582 |
Efficiently Evaluating Complex Boolean Expressions |
2010 |
SIGMOD |
5.4241353e-05 |
| 6,243 |
BE-Tree: An Index Structure to Efficiently Match Boolean Expressions over High-dimensional Discrete Space |
2011 |
SIGMOD |
5.1402191e-05 |
| 6,992 |
An Efficient Publish/Subscribe Index for E-Commerce Databases |
2014 |
VLDB |
4.8701339e-05 |
| 9,254 |
PS-Tree-Based Efficient Boolean Expression Matching for High-Dimensional and Dense Workloads |
2019 |
VLDB |
4.3690661e-05 |
Semantically Similar Papers
| Overall Rank |
Paper |
Year |
Venue |
Pagerank |
| 9,949 |
AB-tree: Index for Concurrent Random Sampling and Updates |
2022 |
VLDB |
4.2421586e-05 |
| 5,615 |
A Scalable Index for Top-k Subtree Similarity Queries |
2019 |
SIGMOD |
5.4101086e-05 |
| 6,919 |
Efficient Indexing and Querying over Syntactically Annotated Trees |
2012 |
VLDB |
4.8925595e-05 |
| 1,925 |
The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation |
2000 |
VLDB |
0.00010073407 |
| 5,574 |
Efficient Processing of XML Twig Queries with OR-Predicates |
2004 |
SIGMOD |
5.4268403e-05 |
| 5,582 |
Efficiently Evaluating Complex Boolean Expressions |
2010 |
SIGMOD |
5.4241353e-05 |
| 3,526 |
RE-Tree: An Efficient Index Structure for Regular Expressions |
2002 |
VLDB |
7.0078308e-05 |
| 2,949 |
Indexing Boolean Expressions |
2009 |
VLDB |
7.8340452e-05 |
| 9,254 |
PS-Tree-Based Efficient Boolean Expression Matching for High-Dimensional and Dense Workloads |
2019 |
VLDB |
4.3690661e-05 |
| 6,243 |
BE-Tree: An Index Structure to Efficiently Match Boolean Expressions over High-dimensional Discrete Space |
2011 |
SIGMOD |
5.1402191e-05 |