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: h0b60df3a4e19f7e3
Venue: SIGMOD
Year: 2009
Pagerank: 6.5966903e-05
Overall Rank: 4,441 | 70.16%
DOI: 10.1145/1559845.1559891

Incoming Non-self Citations Over Time

Authors

1. Marios Hadjieleftheriou (AT&T)
2. Nick Koudas (University of Toronto)
3. Divesh Srivastava (AT&T)

BibTeX Citation

@inproceedings{hadjieleftheriou_sigmod09,
        title = {{Incremental Maintenance of Length Normalized Indexes for Approximate String Matching}},
        author = {Hadjieleftheriou, Marios and Koudas, Nick and Srivastava, Divesh},
        series = {{SIGMOD} '09},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1559845.1559891},
        url = {https://dl.acm.org/doi/10.1145/1559845.1559891},
        year = {2009}
}

Incoming Citations (Sorted by Pagerank)

Showing 10 of 10 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,934	Pass-Join: A Partition-based Method for Similarity Joins	2012	VLDB	9.341845e-05
2,074	Bed-Tree: An All-Purpose Index Structure for String Similarity Search Based on Edit Distance	2010	SIGMOD	9.0821759e-05
3,817	Trie-Join: Efficient Trie-based String Similarity Joins with Edit-Distance Constraints	2010	VLDB	7.0039415e-05
5,551	Faerie: Efficient Filtering Algorithms for Approximate Dictionary-based Entity Extraction	2011	SIGMOD	6.0852227e-05
5,797	Efficient Approximate Search on String Collections (Tutorial)	2009	VLDB	5.9898117e-05
6,608	A Pivotal Prefix Based Filtering Algorithm for String Similarity Search	2014	SIGMOD	5.73402e-05
7,032	Efficient Similarity Join and Search on Multi-Attribute Data	2015	SIGMOD	5.6147056e-05
9,136	Balance-Aware Distributed String Similarity-Based Query Processing System	2019	VLDB	5.2213971e-05
10,755	Balancing the Blend: An Experimental Analysis of Trade-offs in Hybrid Search	2026	VLDB	4.9769913e-05
12,234	ZigZag: Supporting Similarity Queries on Vector Space Models	2018	SIGMOD	4.9769913e-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
5	Optimal Aggregation Algorithms for Middleware [Extended Abstract]	2001	PODS	0.0010679903
108	Approximate String Joins in a Database (Almost) for Free	2001	VLDB	0.00033040246
168	Efficient Exact Set-Similarity Joins	2006	VLDB	0.00027151132
201	Efficient set joins on similarity predicates	2004	SIGMOD	0.00025319937
262	Record Linkage: Similarity Measures and Algorithms	2006	SIGMOD	0.00022811258
2,147	Cost-Based Variable-Length-Gram Selection for String Collections to Support Approximate Queries Efficiently	2008	SIGMOD	8.9566452e-05
3,403	Benchmarking Declarative Approximate Selection Predicates	2007	SIGMOD	7.3266624e-05
4,089	Flexible String Matching Against Large Databases in Practice	2004	VLDB	6.8116568e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,893	An Efficient Index Structure for String Databases	2001	VLDB
2	8,251	Indexing Mixed Types for Approximate Retrieval	2005	VLDB
3	2,706	On Effective Multi-Dimensional Indexing for Strings	2000	SIGMOD
4	10,057	Text Indexing for Long Patterns: Anchors are All you Need	2023	VLDB
5	5,817	Incremental Maintenance of XML Structural Indexes	2004	SIGMOD
6	1,448	Fast Incremental Indexing for Full-Text Information Retrieval	1994	VLDB
7	7,846	Efficient Top-k Algorithms for Approximate Substring Matching	2013	SIGMOD
8	9,660	Indexing for Keyword Search with Structured Constraints	2023	PODS
9	7,705	An Incrementally Maintainable Index for Approximate Lookups in Hierarchical Data	2006	VLDB
10	2,038	Incremental Updates of Inverted Lists for Text Document Retrieval	1994	SIGMOD