Incremental Maintenance of Length Normalized Indexes for Approximate String Matching

Summary: Lazy-update framework for length-normalized indexes in approximate string matching enables incremental updates rather than periodic rebuilds. Guarantees: no false negatives, bounded false positives; prototype demonstrates practicality on real data. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 4138
Venue: SIGMOD
Year: 2009
Pagerank: 5.8537044e-05
Overall Rank: 4,878 | 66.10%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 10 of 10 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,387	Bed-Tree: An All-Purpose Index Structure for String Similarity Search Based on Edit Distance	2010	SIGMOD	8.9075095e-05
2,588	Pass-Join: A Partition-based Method for Similarity Joins	2012	VLDB	8.4872437e-05
4,215	Trie-Join: Efficient Trie-based String Similarity Joins with Edit-Distance Constraints	2010	VLDB	6.3464157e-05
5,071	Faerie: Efficient Filtering Algorithms for Approximate Dictionary-based Entity Extraction	2011	SIGMOD	5.7122974e-05
5,892	Efficient Approximate Search on String Collections (Tutorial)	2009	VLDB	5.2829767e-05
6,730	A Pivotal Prefix Based Filtering Algorithm for String Similarity Search	2014	SIGMOD	4.9436522e-05
7,106	Efficient Similarity Join and Search on Multi-Attribute Data	2015	SIGMOD	4.8250163e-05
9,831	Balance-Aware Distributed String Similarity-Based Query Processing System	2019	VLDB	4.2710095e-05
10,275	Balancing the Blend: An Experimental Analysis of Trade-offs in Hybrid Search	2026	VLDB	4.1905499e-05
11,730	ZigZag: Supporting Similarity Queries on Vector Space Models	2018	SIGMOD	4.1905499e-05

Outgoing Citations (Sorted by Pagerank)

Showing 8 of 8 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
8	Optimal Aggregation Algorithms for Middleware [Extended Abstract]	2001	PODS	0.0015436578
125	Approximate String Joins in a Database (Almost) for Free	2001	VLDB	0.00044946098
248	Efficient set joins on similarity predicates	2004	SIGMOD	0.00030888982
264	Efficient Exact Set-Similarity Joins	2006	VLDB	0.00029950264
321	Record Linkage: Similarity Measures and Algorithms	2006	SIGMOD	0.00027524716
2,196	Cost-Based Variable-Length-Gram Selection for String Collections to Support Approximate Queries Efficiently	2008	SIGMOD	9.318552e-05
3,258	Benchmarking Declarative Approximate Selection Predicates	2007	SIGMOD	7.3129307e-05
4,033	Flexible String Matching Against Large Databases in Practice	2004	VLDB	6.5125692e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
4,330	An Efficient Index Structure for String Databases	2001	VLDB	6.2745131e-05
7,775	Indexing Mixed Types for Approximate Retrieval	2005	VLDB	4.6494306e-05
1,184	On Effective Multi-Dimensional Indexing for Strings	2000	SIGMOD	0.00013442644
9,723	Text Indexing for Long Patterns: Anchors are All you Need	2023	VLDB	4.2913201e-05
5,679	Incremental Maintenance of XML Structural Indexes	2004	SIGMOD	5.3760807e-05
1,152	Fast Incremental Indexing for Full-Text Information Retrieval	1994	VLDB	0.00013633341
7,707	Efficient Top-k Algorithms for Approximate Substring Matching	2013	SIGMOD	4.6676985e-05
9,327	Indexing for Keyword Search with Structured Constraints	2023	PODS	4.351469e-05
6,734	An Incrementally Maintainable Index for Approximate Lookups in Hierarchical Data	2006	VLDB	4.9434384e-05
1,514	Incremental Updates of Inverted Lists for Text Document Retrieval	1994	SIGMOD	0.00011571661