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 |
|---|---|---|---|---|
| 2,219 | WHAM: A High-throughput Sequence Alignment Method | 2011 | SIGMOD | 8.9998232e-05 |
| 6,042 | Reference-Based Alignment in Large Sequence Databases | 2009 | VLDB | 6.0592274e-05 |
| 6,753 | A Generic Framework for Efficient and Effective Subsequence Retrieval | 2012 | VLDB | 5.8414302e-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,224 | n-Gram/2L: A Space and Time Efficient Two-Level n-Gram Inverted Index Structure | 2005 | VLDB | 8.992609e-05 |
| 5,012 | Privacy-Preserving Indexing of Documents on the Network | 2003 | VLDB | 6.4689973e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 1,026 | VGRAM: Improving Performance of Approximate Queries on String Collections Using Variable-Length Grams | 2007 | VLDB | 0.00012661091 |
| 12,903 | Fast Search In Main Memory Databases | 1992 | SIGMOD | 5.1725247e-05 |
| 8,626 | Practical and Secure Substring Search | 2018 | SIGMOD | 5.4598872e-05 |
| 14,314 | Unstructured Data Bases or Very Efficient Text Searching | 1983 | PODS | - |
| 2,055 | Cost-Based Variable-Length-Gram Selection for String Collections to Support Approximate Queries Efficiently | 2008 | SIGMOD | 9.3220009e-05 |
| 7,493 | Efficient Top-k Algorithms for Approximate Substring Matching | 2013 | SIGMOD | 5.6670665e-05 |
| 2,606 | On Effective Multi-Dimensional Indexing for Strings | 2000 | SIGMOD | 8.42332e-05 |
| 13,285 | On the String Matching with k Differences in DNA Databases | 2021 | VLDB | - |
| 3,156 | Efficient Exact Edit Similarity Query Processing with the Asymmetric Signature Scheme | 2011 | SIGMOD | 7.7577179e-05 |
| 4,712 | An Efficient Index Structure for String Databases | 2001 | VLDB | 6.6145853e-05 |