Fast Algorithms for Parsing Sequences of Parentheses with Few Errors
Summary: First algorithm to repair unbalanced-parentheses sequences in O(n) + d^{O(1)} time, i.e., linear in input size when minimum edit distance d is small, improving on cubic-time DP. Enables fast repair of semi-structured docs (XML/JSON) with few errors. (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
No non-self incoming citations found for this paper in this database.
Authors
- 1. Arturs Backurs (Massachusetts Institute of Technology)
- 2. Krzysztof Onak (IBM)
BibTeX Citation
@inproceedings{backurs_pods16,
address = {New York, NY, USA},
series = {{PODS} '16},
title = {{Fast Algorithms for Parsing Sequences of Parentheses with Few Errors}},
url = {https://dl.acm.org/doi/10.1145/2902251.2902304},
doi = {10.1145/2902251.2902304},
booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
publisher = {Association for Computing Machinery},
author = {Backurs, Arturs and Onak, Krzysztof},
year = {2016}
}
Incoming Citations (Sorted by Pagerank)
Showing 0 of 0 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 1 of 1 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 5,338 | On Repairing Structural Problems In Semi-structured Data | 2013 | VLDB | 6.2609275e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 10,372 | From Suspicious Errors to Valid Data: On Repairing Spatio-Temporal Data via Spatial and Temporal Dependencies | 2026 | SIGMOD |
| 2 | 12,081 | Cleaning Timestamps with Temporal Constraints | 2016 | VLDB |
| 3 | 185 | A Cost-Based Model and Effective Heuristic for Repairing Constraints by Value Modification | 2005 | SIGMOD |
| 4 | 1,399 | Computing Optimal Repairs for Functional Dependencies | 2018 | PODS |
| 5 | 8,103 | The Computation of Optimal Subset Repairs | 2020 | VLDB |
| 6 | 10,784 | The Best of Both Worlds: On Repairing Timestamps and Attribute Values for Multivariate Time Series | 2025 | SIGMOD |
| 7 | 12,299 | Deterministic Regular Expressions in Linear Time | 2012 | PODS |
| 8 | 13,683 | Efficient Evaluation for a Temporal Logic on Changing XML Documents | 2011 | PODS |
| 9 | 9,523 | Repairing Data through Regular Expressions | 2016 | VLDB |
| 10 | 5,338 | On Repairing Structural Problems In Semi-structured Data | 2013 | VLDB |