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: 5062
Venue: SIGMOD
Year: 2015
Pagerank: 4.2500258e-05
Overall Rank: 9,932 | 30.91%
DOI: 10.1145/2723372.2749445

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,250	Local Similarity Search for Unstructured Text	2016	SIGMOD	6.3241139e-05
6,074	Pigeonring: A Principle for Faster Thresholded Similarity Search	2019	VLDB	5.2242306e-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
125	Approximate String Joins in a Database (Almost) for Free	2001	VLDB	0.00044847972
250	Efficient set joins on similarity predicates	2004	SIGMOD	0.00030661988
266	Efficient Exact Set-Similarity Joins	2006	VLDB	0.00029718727
322	Record Linkage: Similarity Measures and Algorithms	2006	SIGMOD	0.00027518768
1,202	VGRAM: Improving Performance of Approximate Queries on String Collections Using Variable-Length Grams	2007	VLDB	0.00013326298
1,234	Ed-Join: An Efficient Algorithm for Similarity Joins With Edit Distance Constraints	2008	VLDB	0.00013122499
1,396	Can We Beat the Prefix Filtering? An Adaptive Framework for Similarity Join and Search	2012	SIGMOD	0.00012204748
1,944	WHAM: A High-throughput Sequence Alignment Method	2011	SIGMOD	0.00010004608
2,073	Extending Autocompletion To Tolerate Errors	2009	SIGMOD	9.6142791e-05
2,193	Cost-Based Variable-Length-Gram Selection for String Collections to Support Approximate Queries Efficiently	2008	SIGMOD	9.3178557e-05
2,592	Pass-Join: A Partition-based Method for Similarity Joins	2012	VLDB	8.4795761e-05
2,740	String Similarity Joins: An Experimental Evaluation	2014	VLDB	8.1980628e-05
3,578	Efficient Approximate Entity Extraction with Edit Distance Constraints	2009	SIGMOD	6.9503858e-05
3,774	Efficient Exact Edit Similarity Query Processing with the Asymmetric Signature Scheme	2011	SIGMOD	6.7757301e-05
3,868	An Efficient Filter for Approximate Membership Checking	2008	SIGMOD	6.6822543e-05
5,887	Efficient Approximate Search on String Collections (Tutorial)	2009	VLDB	5.2879769e-05
6,726	A Pivotal Prefix Based Filtering Algorithm for String Similarity Search	2014	SIGMOD	4.9484027e-05
7,141	Efficient Error-tolerant Query Autocompletion	2013	VLDB	4.8197901e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
2,376	Bed-Tree: An All-Purpose Index Structure for String Similarity Search Based on Edit Distance	2010	SIGMOD	8.9424361e-05
125	Approximate String Joins in a Database (Almost) for Free	2001	VLDB	0.00044847972
9,933	Efficient and Effective KNN Sequence Search with Approximate n-grams	2014	VLDB	4.2500258e-05
3,868	An Efficient Filter for Approximate Membership Checking	2008	SIGMOD	6.6822543e-05
7,777	Indexing Mixed Types for Approximate Retrieval	2005	VLDB	4.653704e-05
4,333	An Efficient Index Structure for String Databases	2001	VLDB	6.2805237e-05
11,979	Similarity Joins for Uncertain Strings	2014	SIGMOD	4.1945683e-05
3,774	Efficient Exact Edit Similarity Query Processing with the Asymmetric Signature Scheme	2011	SIGMOD	6.7757301e-05
6,726	A Pivotal Prefix Based Filtering Algorithm for String Similarity Search	2014	SIGMOD	4.9484027e-05
7,708	Efficient Top-k Algorithms for Approximate Substring Matching	2013	SIGMOD	4.6721808e-05