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,500 | FalconDB: Blockchain-based Collaborative Database | 2020 | SIGMOD | 7.0373486e-05 |
| 4,538 | VeriDB: An SGX-based Verifiable Database | 2021 | SIGMOD | 6.1040708e-05 |
| 9,643 | PoneglyphDB: Efficient Non-interactive Zero-Knowledge Proofs for Arbitrary SQL-Query Verification | 2025 | SIGMOD | 4.3109001e-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,828 | Authenticated Join Processing in Outsourced Databases | 2009 | SIGMOD | 0.00010389392 |
| 3,932 | Authenticating the Query Results of Text Search Engines | 2008 | VLDB | 6.6184355e-05 |
| 6,319 | ERA: Efficient Serial and Parallel Suffix Tree Construction for Very Long Strings | 2012 | VLDB | 5.1132714e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 395 | Dynamic Authenticated Index Structures for Outsourced Databases | 2006 | SIGMOD | 0.00024433049 |
| 12,365 | Improving Suffix Array Locality for Fast Pattern Matching on Disk | 2008 | SIGMOD | 4.1945683e-05 |
| 5,367 | Fast Range Query Processing with Strong Privacy Protection for Cloud Computing | 2014 | VLDB | 5.5457837e-05 |
| 9,450 | Lightweight Authentication of Linear Algebraic Queries on Data Streams | 2013 | SIGMOD | 4.3396633e-05 |
| 10,346 | Differentially Private Substring and Document Counting | 2025 | PODS | 4.1945683e-05 |
| 4,589 | Scalable Regular Expression Matching on Data Streams | 2008 | SIGMOD | 6.06476e-05 |
| 3,932 | Authenticating the Query Results of Text Search Engines | 2008 | VLDB | 6.6184355e-05 |
| 4,447 | Proof-Infused Streams: Enabling Authentication of Sliding Window Queries On Streams | 2007 | VLDB | 6.1791516e-05 |
| 6,962 | Efficient Secure Query Evaluation over Encrypted XML Databases | 2006 | VLDB | 4.883323e-05 |
| 4,423 | Scalable Verification for Outsourced Dynamic Databases | 2009 | VLDB | 6.1989913e-05 |