DBScholar

Back to papers

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
4199
Venue
SIGMOD
Year
2009
Pagerank
6.7451753e-05
Overall Rank
4,359 | 70.10%
DOI
10.1145/1559845.1559891

Incoming Non-self Citations Over Time

Authors

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,886 Pass-Join: A Partition-based Method for Similarity Joins 2012 VLDB 9.5358137e-05
2,036 Bed-Tree: An All-Purpose Index Structure for String Similarity Search Based on Edit Distance 2010 SIGMOD 9.2782094e-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,667 Efficient Approximate Search on String Collections (Tutorial) 2009 VLDB 6.1279762e-05
6,484 A Pivotal Prefix Based Filtering Algorithm for String Similarity Search 2014 SIGMOD 5.8665833e-05
6,906 Efficient Similarity Join and Search on Multi-Attribute Data 2015 SIGMOD 5.7418509e-05
9,979 Balance-Aware Distributed String Similarity-Based Query Processing System 2019 VLDB 5.1845938e-05
10,563 Balancing the Blend: An Experimental Analysis of Trade-offs in Hybrid Search 2026 VLDB 5.093636e-05
11,929 ZigZag: Supporting Similarity Queries on Vector Space Models 2018 SIGMOD 5.093636e-05
Previous Page 1 / 1 Next

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.0010828372
107 Approximate String Joins in a Database (Almost) for Free 2001 VLDB 0.00033511706
169 Efficient Exact Set-Similarity Joins 2006 VLDB 0.0002743469
200 Efficient set joins on similarity predicates 2004 SIGMOD 0.00025597287
254 Record Linkage: Similarity Measures and Algorithms 2006 SIGMOD 0.00023199211
2,103 Cost-Based Variable-Length-Gram Selection for String Collections to Support Approximate Queries Efficiently 2008 SIGMOD 9.1621686e-05
3,356 Benchmarking Declarative Approximate Selection Predicates 2007 SIGMOD 7.490881e-05
4,009 Flexible String Matching Against Large Databases in Practice 2004 VLDB 6.9612537e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

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