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
- 6158
- Venue
- SIGMOD
- Year
- 2021
- Pagerank
- 4.4859208e-05
- Overall Rank
- 8,583 | 40.35%
- 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.00030155645 |
| 447 |
Storing and Querying Ordered XML Using a Relational Database System |
2002 |
SIGMOD |
0.00022927245 |
| 497 |
Filtering Algorithms and Implementation for Very Fast Publish/Subscribe Systems |
2001 |
SIGMOD |
0.00021667647 |
| 843 |
ORDPATHs: Insert-Friendly XML Node Labels |
2004 |
SIGMOD |
0.00015975516 |
| 1,417 |
ZStream: A Cost-based Query Processor for Adaptively Detecting Composite Events |
2009 |
SIGMOD |
0.00012084678 |
| 1,581 |
Execution Strategies for SQL Subqueries |
2007 |
SIGMOD |
0.00011262795 |
| 2,314 |
A Predicate Matching Algorithm for Database Rule Systems |
1990 |
SIGMOD |
9.0539046e-05 |
| 2,341 |
SASE: Complex Event Processing over Streams |
2007 |
CIDR |
9.0009661e-05 |
| 2,951 |
Indexing Boolean Expressions |
2009 |
VLDB |
7.8248136e-05 |
| 3,214 |
Cayuga: A High-Performance Event Processing Engine |
2007 |
SIGMOD |
7.3708419e-05 |
| 3,228 |
Practical Applications of Triggers and Constraints: Successes and Lingering Issues |
2000 |
VLDB |
7.3425819e-05 |
| 4,012 |
Scalable Pattern Sharing on Event Streams |
2016 |
SIGMOD |
6.5338454e-05 |
| 5,172 |
Active Complex Event Processing over Event Streams |
2011 |
VLDB |
5.6414491e-05 |
| 5,396 |
Scalable Ranked Publish/Subscribe |
2008 |
VLDB |
5.5279512e-05 |
| 5,589 |
Efficiently Evaluating Complex Boolean Expressions |
2010 |
SIGMOD |
5.4187931e-05 |
| 6,249 |
BE-Tree: An Index Structure to Efficiently Match Boolean Expressions over High-dimensional Discrete Space |
2011 |
SIGMOD |
5.132996e-05 |
| 6,995 |
An Efficient Publish/Subscribe Index for E-Commerce Databases |
2014 |
VLDB |
4.8633927e-05 |
| 9,261 |
PS-Tree-Based Efficient Boolean Expression Matching for High-Dimensional and Dense Workloads |
2019 |
VLDB |
4.3648789e-05 |
Semantically Similar Papers
| Overall Rank |
Paper |
Year |
Venue |
Pagerank |
| 9,945 |
AB-tree: Index for Concurrent Random Sampling and Updates |
2022 |
VLDB |
4.240067e-05 |
| 5,624 |
A Scalable Index for Top-k Subtree Similarity Queries |
2019 |
SIGMOD |
5.4049016e-05 |
| 6,921 |
Efficient Indexing and Querying over Syntactically Annotated Trees |
2012 |
VLDB |
4.8878659e-05 |
| 1,923 |
The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation |
2000 |
VLDB |
0.00010079134 |
| 5,580 |
Efficient Processing of XML Twig Queries with OR-Predicates |
2004 |
SIGMOD |
5.4216254e-05 |
| 5,589 |
Efficiently Evaluating Complex Boolean Expressions |
2010 |
SIGMOD |
5.4187931e-05 |
| 3,530 |
RE-Tree: An Efficient Index Structure for Regular Expressions |
2002 |
VLDB |
7.0008977e-05 |
| 2,951 |
Indexing Boolean Expressions |
2009 |
VLDB |
7.8248136e-05 |
| 9,261 |
PS-Tree-Based Efficient Boolean Expression Matching for High-Dimensional and Dense Workloads |
2019 |
VLDB |
4.3648789e-05 |
| 6,249 |
BE-Tree: An Index Structure to Efficiently Match Boolean Expressions over High-dimensional Discrete Space |
2011 |
SIGMOD |
5.132996e-05 |