Practical Authenticated Pattern Matching with Optimal Proof Size
Summary: Builds the first authenticated pattern-matching structure directly over a suffix tree using cryptographic accumulators. It provides constant-size proofs (≤500 bytes for text, ≤243 bytes for XML), with fast, parallelizable generation and verification independent of document or answer size. (summarized by gpt-5.6-luna on Jul 24 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Dimitrios Papadopoulos (Boston University)
- 2. Charalampos Papamanthou (University of Maryland)
- 3. Roberto Tamassia (Brown University)
- 4. Nikos Triandopoulos (Boston University; RSA Laboratories)
BibTeX Citation
@article{papadopoulos_vldb15,
title = {{Practical Authenticated Pattern Matching with Optimal Proof Size}},
author = {Papadopoulos, Dimitrios and Papamanthou, Charalampos and Tamassia, Roberto and Triandopoulos, Nikos},
journal = {PVLDB},
series = {{VLDB} '15},
volume = {8},
number = {7},
pages = {750--761},
doi = {10.14778/2752938.2752942},
url = {https://doi.org/10.14778/2752938.2752942},
year = {2015}
}Incoming Citations (Sorted by Pagerank)
Showing 3 of 3 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 3,122 | FalconDB: Blockchain-based Collaborative Database | 2020 | SIGMOD | 7.7356769e-05 |
| 4,304 | VeriDB: An SGX-based Verifiable Database | 2021 | SIGMOD | 6.7709608e-05 |
| 9,770 | PoneglyphDB: Efficient Non-interactive Zero-Knowledge Proofs for Arbitrary SQL-Query Verification | 2025 | SIGMOD | 5.2209769e-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,804 | Authenticated Join Processing in Outsourced Databases | 2009 | SIGMOD | 9.7171985e-05 |
| 4,031 | Authenticating the Query Results of Text Search Engines | 2008 | VLDB | 6.9458015e-05 |
| 7,057 | ERA: Efficient Serial and Parallel Suffix Tree Construction for Very Long Strings | 2012 | VLDB | 5.7159515e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 437 | Dynamic Authenticated Index Structures for Outsourced Databases | 2006 | SIGMOD |
| 2 | 12,558 | Improving Suffix Array Locality for Fast Pattern Matching on Disk | 2008 | SIGMOD |
| 3 | 5,102 | Fast Range Query Processing with Strong Privacy Protection for Cloud Computing | 2014 | VLDB |
| 4 | 9,608 | Lightweight Authentication of Linear Algebraic Queries on Data Streams | 2013 | SIGMOD |
| 5 | 10,642 | Differentially Private Substring and Document Counting | 2025 | PODS |
| 6 | 4,391 | Scalable Regular Expression Matching on Data Streams | 2008 | SIGMOD |
| 7 | 4,031 | Authenticating the Query Results of Text Search Engines | 2008 | VLDB |
| 8 | 4,381 | Proof-Infused Streams: Enabling Authentication of Sliding Window Queries On Streams | 2007 | VLDB |
| 9 | 7,115 | Efficient Secure Query Evaluation over Encrypted XML Databases | 2006 | VLDB |
| 10 | 4,887 | Scalable Verification for Outsourced Dynamic Databases | 2009 | VLDB |