Efficient Approximate Entity Extraction with Edit Distance Constraints

Summary: Approximate dictionary matching for NER with edit-distance constraints; tolerates typographical errors beyond token-based similarity. Partitioning-based neighborhood generation with prefix pruning; scalable document processing yields large speedups. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 4224
Venue: SIGMOD
Year: 2009
Pagerank: 7.4087786e-05
Overall Rank: 3,446 | 76.36%
DOI: 10.1145/1559845.1559925

Incoming Non-self Citations Over Time

Authors

1. Wei Wang (National ICT Australia; University of New South Wales)
2. Chuan Xiao (National ICT Australia; University of New South Wales)
3. Xuemin Lin (National ICT Australia; University of New South Wales)
4. Chengqi Zhang (University of Technology Sydney)

BibTeX Citation

@inproceedings{wang_sigmod09,
        title = {{Efficient Approximate Entity Extraction with Edit Distance Constraints}},
        author = {Wang, Wei and Xiao, Chuan and Lin, Xuemin and Zhang, Chengqi},
        series = {{SIGMOD} '09},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1559845.1559925},
        url = {https://dl.acm.org/doi/10.1145/1559845.1559925},
        year = {2009}
}

Incoming Citations (Sorted by Pagerank)

Showing 14 of 14 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,886	Pass-Join: A Partition-based Method for Similarity Joins	2012	VLDB	9.5358137e-05
3,193	Efficient Exact Edit Similarity Query Processing with the Asymmetric Signature Scheme	2011	SIGMOD	7.649474e-05
5,071	Fast Subtrajectory Similarity Search in Road Networks under Weighted Edit Distance Constraints	2020	VLDB	6.3761034e-05
5,088	String Similarity Measures and Joins with Synonyms	2013	SIGMOD	6.3673276e-05
5,412	Faerie: Efficient Filtering Algorithms for Approximate Dictionary-based Entity Extraction	2011	SIGMOD	6.2272563e-05
5,726	Pigeonring: A Principle for Faster Thresholded Similarity Search	2019	VLDB	6.1079184e-05
5,933	Exploiting Evidence from Unstructured Data to Enhance Master Data Management	2012	VLDB	6.036898e-05
7,031	Efficient Error-tolerant Query Autocompletion	2013	VLDB	5.72252e-05
7,268	Cardinality Estimation of Approximate Substring Queries using Deep Learning	2022	VLDB	5.6597123e-05
7,676	Allign: Aligning All-Pair Near-Duplicate Passages in Long Texts	2021	SIGMOD	5.5686107e-05
7,692	Efficient Top-k Algorithms for Approximate Substring Matching	2013	SIGMOD	5.5664611e-05
10,085	Local Filtering: Improving the Performance of Approximate Queries on String Collections	2015	SIGMOD	5.1559617e-05
10,086	Efficient and Effective KNN Sequence Search with Approximate n-grams	2014	VLDB	5.1559617e-05
12,283	RCSI: Scalable similarity search in thousand(s) of genomes	2013	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 15 of 15 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
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
911	Ed-Join: An Efficient Algorithm for Similarity Joins With Edit Distance Constraints	2008	VLDB	0.00013283031
1,040	VGRAM: Improving Performance of Approximate Queries on String Collections Using Variable-Length Grams	2007	VLDB	0.00012466499
1,560	Example-driven Design of Efficient Record Matching Queries	2007	VLDB	0.00010361222
2,103	Cost-Based Variable-Length-Gram Selection for String Collections to Support Approximate Queries Efficiently	2008	SIGMOD	9.1621686e-05
2,308	Hashed Samples: Selectivity Estimators For Set Similarity Selection Queries	2008	VLDB	8.7738996e-05
2,410	Leveraging Aggregate Constraints For Deduplication	2007	SIGMOD	8.6126774e-05
2,899	Extending Q-Grams to Estimate Selectivity of String Matching with Low Edit Distance	2007	VLDB	7.97814e-05
3,356	Benchmarking Declarative Approximate Selection Predicates	2007	SIGMOD	7.490881e-05
3,442	An Efficient Filter for Approximate Membership Checking	2008	SIGMOD	7.4122197e-05
4,035	Selectivity Estimation for Fuzzy String Predicates in Large Data Sets	2005	VLDB	6.9439151e-05
4,992	Scalable Ad-hoc Entity Extraction from Text Collections	2008	VLDB	6.4100657e-05
7,714	Incorporating String Transformations in Record Matching	2008	SIGMOD	5.5608517e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	176	Deep Learning for Entity Matching: A Design Space Exploration	2018	SIGMOD
2	2,120	Comparative Analysis of Approximate Blocking Techniques for Entity Resolution	2016	VLDB
3	7,692	Efficient Top-k Algorithms for Approximate Substring Matching	2013	SIGMOD
4	4,056	A Benchmarking Study of Embedding-based Entity Alignment for Knowledge Graphs	2020	VLDB
5	3,442	An Efficient Filter for Approximate Membership Checking	2008	SIGMOD
6	12,048	Automatic Entity Recognition and Typing in Massive Text Data	2016	SIGMOD
7	1,248	Entity Matching: How Similar Is Similar	2011	VLDB
8	4,992	Scalable Ad-hoc Entity Extraction from Text Collections	2008	VLDB
9	5,279	Mining Document Collections to Facilitate Accurate Approximate Entity Matching	2009	VLDB
10	5,412	Faerie: Efficient Filtering Algorithms for Approximate Dictionary-based Entity Extraction	2011	SIGMOD