Query Evaluation Over SLP-Represented Document Databases With Complex Document Editing
Summary: Bring dynamic updates to SLP-compressed document DBs: support complex editor-like edits (copy/paste, delete, concat) while retaining O(log |Di|)-delay enumeration of k regular spanners by maintaining SLP balancing. Each edit expression φ applied in O(k·|φ|·log d) time (d = max intermediate length), independent of SLP size, permitting updates that produce documents exponentially larger than the update time. (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
Incoming Citations (Sorted by Pagerank)
Showing 3 of 3 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 8,738 | Enumeration for MSO-Queries on Compressed Trees | 2024 | PODS | 4.456315e-05 |
| 8,753 | Document Spanners — A Brief Overview of Concepts, Results, and Recent Developments | 2022 | PODS | 4.456315e-05 |
| 10,339 | A Lower Bound on Unambiguous Context Free Grammars via Communication Complexity | 2025 | PODS | 4.1945683e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 2 of 2 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,929 | Complexity Bounds for Relational Algebra over Document Spanners | 2019 | PODS | 7.8800307e-05 |
| 3,563 | Spanner Evaluation over SLP-Compressed Documents | 2021 | PODS | 6.9690833e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 10,009 | The Space-Time Complexity of Sum-Product Queries | 2026 | PODS | 4.1945683e-05 |
| 11,557 | Aggregate Queries on Sparse Databases | 2020 | PODS | 4.1945683e-05 |
| 6,167 | Enumeration of First-Order Queries on Classes of Structures With Bounded Expansion | 2013 | PODS | 5.1717635e-05 |
| 9,653 | Probabilistic Databases under Updates: Boolean Query Evaluation and Ranked Enumeration | 2021 | PODS | 4.3109001e-05 |
| 3,781 | Trade-offs in Static and Dynamic Evaluation of Hierarchical Queries | 2020 | PODS | 6.7723513e-05 |
| 13,484 | Efficient Evaluation for a Temporal Logic on Changing XML Documents | 2011 | PODS | - |
| 8,738 | Enumeration for MSO-Queries on Compressed Trees | 2024 | PODS | 4.456315e-05 |
| 8,496 | Dynamic Data Structures for Document Collections and Graphs | 2015 | PODS | 4.4981899e-05 |
| 8,437 | Insert-Only versus Insert-Delete in Dynamic Query Evaluation | 2024 | PODS | 4.5138778e-05 |
| 3,563 | Spanner Evaluation over SLP-Compressed Documents | 2021 | PODS | 6.9690833e-05 |