Fast nGram-Based String Search Over Data Encoded Using Algebraic Signatures
Summary: Algebraic-signature based nGram search encodes records into single symbols, enabling sublinear traversal with Rabin-Karp aggregation for faster matching than BM/KMP. Privacy-preserving encoded storage for DAS/DBs; servers never see plaintext; up to 70x DNA, 11x ASCII, 6x XML speedups. (summarized by gpt-5-nano on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Witold Litwin
- 2. Riad Mokadem
- 3. Philippe Rigaux
- 4. Thomas Schwarz
Incoming Citations (Sorted by Pagerank)
Showing 3 of 3 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 1,944 | WHAM: A High-throughput Sequence Alignment Method | 2011 | SIGMOD | 0.00010004608 |
| 5,812 | Reference-Based Alignment in Large Sequence Databases | 2009 | VLDB | 5.3172025e-05 |
| 6,983 | A Generic Framework for Efficient and Effective Subsequence Retrieval | 2012 | VLDB | 4.8732757e-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,213 | n-Gram/2L: A Space and Time Efficient Two-Level n-Gram Inverted Index Structure | 2005 | VLDB | 9.2765152e-05 |
| 4,341 | Privacy-Preserving Indexing of Documents on the Network | 2003 | VLDB | 6.2763011e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 1,202 | VGRAM: Improving Performance of Approximate Queries on String Collections Using Variable-Length Grams | 2007 | VLDB | 0.00013326298 |
| 12,893 | Fast Search In Main Memory Databases | 1992 | SIGMOD | 4.1945683e-05 |
| 8,537 | Practical and Secure Substring Search | 2018 | SIGMOD | 4.4937074e-05 |
| 14,300 | Unstructured Data Bases or Very Efficient Text Searching | 1983 | PODS | - |
| 2,193 | Cost-Based Variable-Length-Gram Selection for String Collections to Support Approximate Queries Efficiently | 2008 | SIGMOD | 9.3178557e-05 |
| 7,708 | Efficient Top-k Algorithms for Approximate Substring Matching | 2013 | SIGMOD | 4.6721808e-05 |
| 1,184 | On Effective Multi-Dimensional Indexing for Strings | 2000 | SIGMOD | 0.00013455208 |
| 13,272 | On the String Matching with k Differences in DNA Databases | 2021 | VLDB | - |
| 3,774 | Efficient Exact Edit Similarity Query Processing with the Asymmetric Signature Scheme | 2011 | SIGMOD | 6.7757301e-05 |
| 4,333 | An Efficient Index Structure for String Databases | 2001 | VLDB | 6.2805237e-05 |