Local Filtering: Improving the Performance of Approximate Queries on String Collections

Summary: Local filtering uses local dissimilarities, via positional local distance that bounds edit-distance contributions from query fragments. Indexing distances across fragments enables pruning and bit-parallel verification with speedups. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 5124
Venue: SIGMOD
Year: 2015
Pagerank: 5.1559617e-05
Overall Rank: 10,085 | 30.81%
DOI: 10.1145/2723372.2749445

Incoming Non-self Citations Over Time

Authors

1. Xiaohun Yang (Northeastern University)
2. Yaoshu Wang (University of New South Wales)
3. Bin Wang (Northeastern University)
4. Wei Wang (University of New South Wales)

BibTeX Citation

@inproceedings{yang_sigmod15,
        title = {{Local Filtering: Improving the Performance of Approximate Queries on String Collections}},
        author = {Yang, Xiaohun and Wang, Yaoshu and Wang, Bin and Wang, Wei},
        series = {{SIGMOD} '15},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/2723372.2749445},
        url = {https://dl.acm.org/doi/10.1145/2723372.2749445},
        year = {2015}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,052	Local Similarity Search for Unstructured Text	2016	SIGMOD	6.935988e-05
5,726	Pigeonring: A Principle for Faster Thresholded Similarity Search	2019	VLDB	6.1079184e-05

Outgoing Citations (Sorted by Pagerank)

Showing 18 of 18 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
254	Record Linkage: Similarity Measures and Algorithms	2006	SIGMOD	0.00023199211
911	Ed-Join: An Efficient Algorithm for Similarity Joins With Edit Distance Constraints	2008	VLDB	0.00013283031
975	Can We Beat the Prefix Filtering? An Adaptive Framework for Similarity Join and Search	2012	SIGMOD	0.00012870645
1,040	VGRAM: Improving Performance of Approximate Queries on String Collections Using Variable-Length Grams	2007	VLDB	0.00012466499
1,701	Extending Autocompletion To Tolerate Errors	2009	SIGMOD	9.9707165e-05
1,886	Pass-Join: A Partition-based Method for Similarity Joins	2012	VLDB	9.5358137e-05
2,103	Cost-Based Variable-Length-Gram Selection for String Collections to Support Approximate Queries Efficiently	2008	SIGMOD	9.1621686e-05
2,186	String Similarity Joins: An Experimental Evaluation	2014	VLDB	9.0001436e-05
2,459	WHAM: A High-throughput Sequence Alignment Method	2011	SIGMOD	8.550768e-05
3,193	Efficient Exact Edit Similarity Query Processing with the Asymmetric Signature Scheme	2011	SIGMOD	7.649474e-05
3,442	An Efficient Filter for Approximate Membership Checking	2008	SIGMOD	7.4122197e-05
3,446	Efficient Approximate Entity Extraction with Edit Distance Constraints	2009	SIGMOD	7.4087786e-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
7,031	Efficient Error-tolerant Query Autocompletion	2013	VLDB	5.72252e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,036	Bed-Tree: An All-Purpose Index Structure for String Similarity Search Based on Edit Distance	2010	SIGMOD
2	10,086	Efficient and Effective KNN Sequence Search with Approximate n-grams	2014	VLDB
3	107	Approximate String Joins in a Database (Almost) for Free	2001	VLDB
4	3,442	An Efficient Filter for Approximate Membership Checking	2008	SIGMOD
5	8,078	Indexing Mixed Types for Approximate Retrieval	2005	VLDB
6	4,776	An Efficient Index Structure for String Databases	2001	VLDB
7	12,177	Similarity Joins for Uncertain Strings	2014	SIGMOD
8	3,193	Efficient Exact Edit Similarity Query Processing with the Asymmetric Signature Scheme	2011	SIGMOD
9	6,484	A Pivotal Prefix Based Filtering Algorithm for String Similarity Search	2014	SIGMOD
10	7,692	Efficient Top-k Algorithms for Approximate Substring Matching	2013	SIGMOD