Algebras for Querying Text Regions (Extended Abstract)
Summary: Defines a set-at-a-time region algebra for text substrings that combines pattern searches with hierarchical (nesting/ordering) queries and connects its expressiveness to the monadic first-order theory of binary trees. Shows optimization is Co-NP-hard in general (polynomial for a key fragment), identifies expressiveness gaps for some nesting/ordering properties, and proposes extensions to trade off added power against optimization complexity. (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Mariano P. Consens
- 2. Tova Milo
Incoming Citations (Sorted by Pagerank)
Showing 2 of 2 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 239 | Holistic Twig Joins: Optimal XML Pattern Matching | 2002 | SIGMOD | 0.00031581944 |
| 1,149 | A Comprehensive XQuery to SQL Translation using Dynamic Interval Encoding | 2003 | SIGMOD | 0.00013649094 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 5 of 5 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 393 | From Structured Documents to Novel Query Facilities | 1994 | SIGMOD | 0.00024506032 |
| 467 | Querying and Updating the File* | 1993 | VLDB | 0.00022431377 |
| 919 | Mind Your Grammar: a New Approach to Modelling Text | 1987 | VLDB | 0.00015283347 |
| 2,296 | The Rufus System: Information Organization for Semi-Structured Data | 1993 | VLDB | 9.0814726e-05 |
| 2,572 | Optimizing Queries on Files | 1994 | SIGMOD | 8.5141353e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 6,921 | Efficient Indexing and Querying over Syntactically Annotated Trees | 2012 | VLDB | 4.8878659e-05 |
| 392 | Indexing and Querying XML Data for Regular Path Expressions | 2001 | VLDB | 0.00024546229 |
| 3,671 | Querying Structured Text in an XML Database | 2003 | SIGMOD | 6.853634e-05 |
| 3,530 | RE-Tree: An Efficient Index Structure for Regular Expressions | 2002 | VLDB | 7.0008977e-05 |
| 1,662 | Conjunctive Queries over Trees | 2004 | PODS | 0.00010966423 |
| 2,345 | Rewriting of Regular Expressions and Regular Path Queries | 1999 | PODS | 8.9933611e-05 |
| 12,527 | An Algebraic Query Model for Effective and Efficient Retrieval of XML Fragments | 2006 | VLDB | 4.1905499e-05 |
| 3,115 | Processing Queries on Tree-Structured Data Efficiently | 2006 | PODS | 7.5414053e-05 |
| 5,722 | Flexible and Efficient XML Search with Complex Full-Text Predicates | 2006 | SIGMOD | 5.3534445e-05 |
| 5,874 | Query Automata (extended abstract) | 1999 | PODS | 5.2893146e-05 |