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: h1a0d2a6ed380837c
Venue: SIGMOD
Year: 2015
Pagerank: 5.0418674e-05
Overall Rank: 10,298 | 30.77%
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,147	Local Similarity Search for Unstructured Text	2016	SIGMOD	6.7803631e-05
5,444	Pigeonring: A Principle for Faster Thresholded Similarity Search	2019	VLDB	6.1268526e-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
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
929	Ed-Join: An Efficient Algorithm for Similarity Joins With Edit Distance Constraints	2008	VLDB	0.00013020115
963	Can We Beat the Prefix Filtering? An Adaptive Framework for Similarity Join and Search	2012	SIGMOD	0.00012816649
1,061	VGRAM: Improving Performance of Approximate Queries on String Collections Using Variable-Length Grams	2007	VLDB	0.00012213729
1,737	Extending Autocompletion To Tolerate Errors	2009	SIGMOD	9.7494976e-05
1,933	Pass-Join: A Partition-based Method for Similarity Joins	2012	VLDB	9.3459285e-05
2,144	Cost-Based Variable-Length-Gram Selection for String Collections to Support Approximate Queries Efficiently	2008	SIGMOD	8.9608583e-05
2,220	String Similarity Joins: An Experimental Evaluation	2014	VLDB	8.8146984e-05
2,508	WHAM: A High-throughput Sequence Alignment Method	2011	SIGMOD	8.371338e-05
3,255	Efficient Exact Edit Similarity Query Processing with the Asymmetric Signature Scheme	2011	SIGMOD	7.4890984e-05
3,501	An Efficient Filter for Approximate Membership Checking	2008	SIGMOD	7.2531528e-05
3,512	Efficient Approximate Entity Extraction with Edit Distance Constraints	2009	SIGMOD	7.2439455e-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,172	Efficient Error-tolerant Query Autocompletion	2013	VLDB	5.5941906e-05

Semantically Similar Papers

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