Practical Authenticated Pattern Matching with Optimal Proof Size
Summary: Suffix-tree–based authenticated data structure for verifiable pattern matching on outsourced text, using cryptographic accumulators to yield constant-size proofs. Supports text pattern matching and exact-path XML queries with proofs at most 500 bytes (text) or 243 bytes (XML), independent of data/answer size, and enables parallelization with sub-10 µs proof generation. (summarized by gpt-5-nano 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 |
|---|---|---|---|---|
| 3,070 | FalconDB: Blockchain-based Collaborative Database | 2020 | SIGMOD | 7.8580484e-05 |
| 4,244 | VeriDB: An SGX-based Verifiable Database | 2021 | SIGMOD | 6.8721687e-05 |
| 9,627 | PoneglyphDB: Efficient Non-interactive Zero-Knowledge Proofs for Arbitrary SQL-Query Verification | 2025 | SIGMOD | 5.3018378e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 3 of 3 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 1,780 | Authenticated Join Processing in Outsourced Databases | 2009 | SIGMOD | 9.8538043e-05 |
| 3,976 | Authenticating the Query Results of Text Search Engines | 2008 | VLDB | 7.0529859e-05 |
| 6,938 | ERA: Efficient Serial and Parallel Suffix Tree Construction for Very Long Strings | 2012 | VLDB | 5.8044765e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 424 | Dynamic Authenticated Index Structures for Outsourced Databases | 2006 | SIGMOD | 0.00018772558 |
| 12,373 | Improving Suffix Array Locality for Fast Pattern Matching on Disk | 2008 | SIGMOD | 5.1725247e-05 |
| 5,037 | Fast Range Query Processing with Strong Privacy Protection for Cloud Computing | 2014 | VLDB | 6.4581476e-05 |
| 9,459 | Lightweight Authentication of Linear Algebraic Queries on Data Streams | 2013 | SIGMOD | 5.3283617e-05 |
| 10,358 | Differentially Private Substring and Document Counting | 2025 | PODS | 5.1725247e-05 |
| 4,328 | Scalable Regular Expression Matching on Data Streams | 2008 | SIGMOD | 6.8326732e-05 |
| 3,976 | Authenticating the Query Results of Text Search Engines | 2008 | VLDB | 7.0529859e-05 |
| 4,316 | Proof-Infused Streams: Enabling Authentication of Sliding Window Queries On Streams | 2007 | VLDB | 6.8370945e-05 |
| 6,997 | Efficient Secure Query Evaluation over Encrypted XML Databases | 2006 | VLDB | 5.7864128e-05 |
| 4,820 | Scalable Verification for Outsourced Dynamic Databases | 2009 | VLDB | 6.5605242e-05 |