Fast nGram-Based String Search Over Data Encoded Using Algebraic Signatures

Summary: Algebraic-signature encoding enables KMP/Boyer–Moore-style sublinear n-gram search while aggregating characters via Karp–Rabin signatures, yielding up to 70× speedups. Supports encrypted-at-rest, server-oblivious search for distributed databases without plaintext exposure. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: hc578ff93d54a6b0d
Venue: VLDB
Year: 2007
Pagerank: 5.9809651e-05
Overall Rank: 5,819 | 60.90%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Witold Litwin (Paris Dauphine University)
2. Riad Mokadem (Paris Dauphine University)
3. Philippe Rigaux (INRIA; Paris Dauphine University)
4. Thomas Schwarz (Santa Clara University)

BibTeX Citation

@article{litwin_vldb07,
        title = {{Fast nGram-Based String Search Over Data Encoded Using Algebraic Signatures}},
        author = {Litwin, Witold and Mokadem, Riad and Rigaux, Philippe and Schwarz, Thomas},
        journal = {PVLDB},
        series = {{VLDB} '07},
        pages = {207},
        year = {2007}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,509	WHAM: A High-throughput Sequence Alignment Method	2011	SIGMOD	8.3675232e-05
6,309	Reference-Based Alignment in Large Sequence Databases	2009	VLDB	5.815405e-05
7,007	A Generic Framework for Efficient and Effective Subsequence Retrieval	2012	VLDB	5.6207566e-05

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,316	n-Gram/2L: A Space and Time Efficient Two-Level n-Gram Inverted Index Structure	2005	VLDB	8.6509997e-05
5,215	Privacy-Preserving Indexing of Documents on the Network	2003	VLDB	6.2223111e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,062	VGRAM: Improving Performance of Approximate Queries on String Collections Using Variable-Length Grams	2007	VLDB
2	13,383	Fast Search In Main Memory Databases	1992	SIGMOD
3	8,913	Practical and Secure Substring Search	2018	SIGMOD
4	14,816	Unstructured Data Bases or Very Efficient Text Searching	1983	PODS
5	2,147	Cost-Based Variable-Length-Gram Selection for String Collections to Support Approximate Queries Efficiently	2008	SIGMOD
6	7,846	Efficient Top-k Algorithms for Approximate Substring Matching	2013	SIGMOD
7	2,706	On Effective Multi-Dimensional Indexing for Strings	2000	SIGMOD
8	13,793	On the String Matching with k Differences in DNA Databases	2021	VLDB
9	3,256	Efficient Exact Edit Similarity Query Processing with the Asymmetric Signature Scheme	2011	SIGMOD
10	4,893	An Efficient Index Structure for String Databases	2001	VLDB