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.9837891e-05
Overall Rank: 5,818 | 60.89%
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,508	WHAM: A High-throughput Sequence Alignment Method	2011	SIGMOD	8.371338e-05
6,305	Reference-Based Alignment in Large Sequence Databases	2009	VLDB	5.818151e-05
7,006	A Generic Framework for Efficient and Effective Subsequence Retrieval	2012	VLDB	5.6234186e-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,313	n-Gram/2L: A Space and Time Efficient Two-Level n-Gram Inverted Index Structure	2005	VLDB	8.6550779e-05
5,212	Privacy-Preserving Indexing of Documents on the Network	2003	VLDB	6.2252569e-05

Semantically Similar Papers

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