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

Summary: Introduces a two-level n-gram inverted index that normalizes away redundant position information via subsequence decomposition, retaining language neutrality and error tolerance. On 1-GB databases, it cuts space 1.9–2.7× and accelerates queries up to 13.1×. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 9505
Venue: VLDB
Year: 2005
Pagerank: 8.8440146e-05
Overall Rank: 2,262 | 84.49%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Min-Soo Kim (Korea Advanced Institute of Science and Technology)
2. Kyu-Young Whang (Korea Advanced Institute of Science and Technology)
3. Jae-Gil Lee (Korea Advanced Institute of Science and Technology)
4. Min-Jae Lee (Korea Advanced Institute of Science and Technology)

BibTeX Citation

@article{kim_vldb05,
        title = {{n-Gram/2L: A Space and Time Efficient Two-Level n-Gram Inverted Index Structure}},
        author = {Kim, Min-Soo and Whang, Kyu-Young and Lee, Jae-Gil and Lee, Min-Jae},
        journal = {PVLDB},
        series = {{VLDB} '05},
        pages = {325},
        year = {2005}
}

Incoming Citations (Sorted by Pagerank)

Showing 9 of 9 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
975	Can We Beat the Prefix Filtering? An Adaptive Framework for Similarity Join and Search	2012	SIGMOD	0.00012870645
1,040	VGRAM: Improving Performance of Approximate Queries on String Collections Using Variable-Length Grams	2007	VLDB	0.00012466499
2,103	Cost-Based Variable-Length-Gram Selection for String Collections to Support Approximate Queries Efficiently	2008	SIGMOD	9.1621686e-05
2,459	WHAM: A High-throughput Sequence Alignment Method	2011	SIGMOD	8.550768e-05
3,731	Trie-Join: Efficient Trie-based String Similarity Joins with Edit-Distance Constraints	2010	VLDB	7.1663952e-05
5,412	Faerie: Efficient Filtering Algorithms for Approximate Dictionary-based Entity Extraction	2011	SIGMOD	6.2272563e-05
5,691	Fast nGram-Based String Search Over Data Encoded Using Algebraic Signatures	2007	VLDB	6.120274e-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 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
1	6,818	Space-efficient Substring Occurrence Estimation	2011	PODS
2	1,529	On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract)	1999	PODS
3	12,490	Secondary Indexing in One Dimension: Beyond B-trees and Bitmap Indexes	2009	PODS
4	6,832	A Scalable Index for Top-k Subtree Similarity Queries	2019	SIGMOD
5	4,776	An Efficient Index Structure for String Databases	2001	VLDB
6	2,103	Cost-Based Variable-Length-Gram Selection for String Collections to Support Approximate Queries Efficiently	2008	SIGMOD
7	1,989	Incremental Updates of Inverted Lists for Text Document Retrieval	1994	SIGMOD
8	11,081	An Evaluation of N-Gram Selection Strategies for Regular Expression Indexing in Contemporary Text Analysis Tasks	2025	VLDB
9	10,086	Efficient and Effective KNN Sequence Search with Approximate n-grams	2014	VLDB
10	4,359	Incremental Maintenance of Length Normalized Indexes for Approximate String Matching	2009	SIGMOD