n-Gram/2L: A Space and Time Efficient Two-Level n-Gram Inverted Index Structure

Summary: Two-level n-gram inverted index (n-gram/2L) reduces size and boosts query speed while keeping language-neutral, error-tolerant advantages. Two-step construction removes position redundancy (normalization of multivalued dependencies); experiments on ~1 GB show up to 2× smaller index and up to 13× faster queries. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 9314
Venue: VLDB
Year: 2005
Pagerank: 9.2765152e-05
Overall Rank: 2,213 | 84.61%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 9 of 9 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,202	VGRAM: Improving Performance of Approximate Queries on String Collections Using Variable-Length Grams	2007	VLDB	0.00013326298
1,396	Can We Beat the Prefix Filtering? An Adaptive Framework for Similarity Join and Search	2012	SIGMOD	0.00012204748
1,944	WHAM: A High-throughput Sequence Alignment Method	2011	SIGMOD	0.00010004608
2,193	Cost-Based Variable-Length-Gram Selection for String Collections to Support Approximate Queries Efficiently	2008	SIGMOD	9.3178557e-05
4,216	Trie-Join: Efficient Trie-based String Similarity Joins with Edit-Distance Constraints	2010	VLDB	6.3521675e-05
5,073	Faerie: Efficient Filtering Algorithms for Approximate Dictionary-based Entity Extraction	2011	SIGMOD	5.7177424e-05
5,397	Fast nGram-Based String Search Over Data Encoded Using Algebraic Signatures	2007	VLDB	5.5299002e-05
5,812	Reference-Based Alignment in Large Sequence Databases	2009	VLDB	5.3172025e-05
6,983	A Generic Framework for Efficient and Effective Subsequence Retrieval	2012	VLDB	4.8732757e-05

Outgoing Citations (Sorted by Pagerank)

Showing 0 of 0 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
5,813	Space-efficient Substring Occurrence Estimation	2011	PODS	5.3170565e-05
1,182	On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract)	1999	PODS	0.00013455963
12,295	Secondary Indexing in One Dimension: Beyond B-trees and Bitmap Indexes	2009	PODS	4.1945683e-05
5,615	A Scalable Index for Top-k Subtree Similarity Queries	2019	SIGMOD	5.4101086e-05
4,333	An Efficient Index Structure for String Databases	2001	VLDB	6.2805237e-05
2,193	Cost-Based Variable-Length-Gram Selection for String Collections to Support Approximate Queries Efficiently	2008	SIGMOD	9.3178557e-05
1,517	Incremental Updates of Inverted Lists for Text Document Retrieval	1994	SIGMOD	0.00011578859
10,857	An Evaluation of N-Gram Selection Strategies for Regular Expression Indexing in Contemporary Text Analysis Tasks	2025	VLDB	4.1945683e-05
9,933	Efficient and Effective KNN Sequence Search with Approximate n-grams	2014	VLDB	4.2500258e-05
4,988	Incremental Maintenance of Length Normalized Indexes for Approximate String Matching	2009	SIGMOD	5.783959e-05