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: 9767
Venue: VLDB
Year: 2007
Pagerank: 6.120274e-05
Overall Rank: 5,691 | 60.96%
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,459	WHAM: A High-throughput Sequence Alignment Method	2011	SIGMOD	8.550768e-05
6,182	Reference-Based Alignment in Large Sequence Databases	2009	VLDB	5.9493566e-05
6,858	A Generic Framework for Efficient and Effective Subsequence Retrieval	2012	VLDB	5.7523396e-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,262	n-Gram/2L: A Space and Time Efficient Two-Level n-Gram Inverted Index Structure	2005	VLDB	8.8440146e-05
5,086	Privacy-Preserving Indexing of Documents on the Network	2003	VLDB	6.3680338e-05

Semantically Similar Papers

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