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
h0b60df3a4e19f7e3
Venue
SIGMOD
Year
2009
Pagerank
6.5998035e-05
Overall Rank
4,439 | 70.16%
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,933 Pass-Join: A Partition-based Method for Similarity Joins 2012 VLDB 9.3459285e-05
2,072 Bed-Tree: An All-Purpose Index Structure for String Similarity Search Based on Edit Distance 2010 SIGMOD 9.0864612e-05
3,816 Trie-Join: Efficient Trie-based String Similarity Joins with Edit-Distance Constraints 2010 VLDB 7.0072547e-05
5,549 Faerie: Efficient Filtering Algorithms for Approximate Dictionary-based Entity Extraction 2011 SIGMOD 6.088104e-05
5,795 Efficient Approximate Search on String Collections (Tutorial) 2009 VLDB 5.9926463e-05
6,605 A Pivotal Prefix Based Filtering Algorithm for String Similarity Search 2014 SIGMOD 5.7367357e-05
7,030 Efficient Similarity Join and Search on Multi-Attribute Data 2015 SIGMOD 5.6173605e-05
9,126 Balance-Aware Distributed String Similarity-Based Query Processing System 2019 VLDB 5.22387e-05
10,745 Balancing the Blend: An Experimental Analysis of Trade-offs in Hybrid Search 2026 VLDB 4.9793485e-05
12,228 ZigZag: Supporting Similarity Queries on Vector Space Models 2018 SIGMOD 4.9793485e-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.0010679641
108 Approximate String Joins in a Database (Almost) for Free 2001 VLDB 0.0003305531
168 Efficient Exact Set-Similarity Joins 2006 VLDB 0.00027163517
201 Efficient set joins on similarity predicates 2004 SIGMOD 0.00025331535
262 Record Linkage: Similarity Measures and Algorithms 2006 SIGMOD 0.00022821392
2,144 Cost-Based Variable-Length-Gram Selection for String Collections to Support Approximate Queries Efficiently 2008 SIGMOD 8.9608583e-05
3,403 Benchmarking Declarative Approximate Selection Predicates 2007 SIGMOD 7.3300953e-05
4,087 Flexible String Matching Against Large Databases in Practice 2004 VLDB 6.8148535e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

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