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,947 | WHAM: A High-throughput Sequence Alignment Method | 2011 | SIGMOD | 9.9963826e-05 |
| 5,823 | Reference-Based Alignment in Large Sequence Databases | 2009 | VLDB | 5.3122255e-05 |
| 6,982 | A Generic Framework for Efficient and Effective Subsequence Retrieval | 2012 | VLDB | 4.8685999e-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,215 | n-Gram/2L: A Space and Time Efficient Two-Level n-Gram Inverted Index Structure | 2005 | VLDB | 9.2695849e-05 |
| 4,339 | Privacy-Preserving Indexing of Documents on the Network | 2003 | VLDB | 6.2703057e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 1,203 | VGRAM: Improving Performance of Approximate Queries on String Collections Using Variable-Length Grams | 2007 | VLDB | 0.00013317317 |
| 12,903 | Fast Search In Main Memory Databases | 1992 | SIGMOD | 4.1905499e-05 |
| 8,536 | Practical and Secure Substring Search | 2018 | SIGMOD | 4.4893996e-05 |
| 14,314 | Unstructured Data Bases or Very Efficient Text Searching | 1983 | PODS | - |
| 2,196 | Cost-Based Variable-Length-Gram Selection for String Collections to Support Approximate Queries Efficiently | 2008 | SIGMOD | 9.318552e-05 |
| 7,707 | Efficient Top-k Algorithms for Approximate Substring Matching | 2013 | SIGMOD | 4.6676985e-05 |
| 1,184 | On Effective Multi-Dimensional Indexing for Strings | 2000 | SIGMOD | 0.00013442644 |
| 13,285 | On the String Matching with k Differences in DNA Databases | 2021 | VLDB | - |
| 3,779 | Efficient Exact Edit Similarity Query Processing with the Asymmetric Signature Scheme | 2011 | SIGMOD | 6.7709545e-05 |
| 4,330 | An Efficient Index Structure for String Databases | 2001 | VLDB | 6.2745131e-05 |