Database Paper Browser

Back to papers

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
5063
Venue
SIGMOD
Year
2015
Pagerank
4.245954e-05
Overall Rank
9,933 | 30.97%
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,247 Local Similarity Search for Unstructured Text 2016 SIGMOD 6.3180334e-05
6,080 Pigeonring: A Principle for Faster Thresholded Similarity Search 2019 VLDB 5.219249e-05
Previous Page 1 / 1 Next

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.00044946098
248 Efficient set joins on similarity predicates 2004 SIGMOD 0.00030888982
264 Efficient Exact Set-Similarity Joins 2006 VLDB 0.00029950264
321 Record Linkage: Similarity Measures and Algorithms 2006 SIGMOD 0.00027524716
1,203 VGRAM: Improving Performance of Approximate Queries on String Collections Using Variable-Length Grams 2007 VLDB 0.00013317317
1,232 Ed-Join: An Efficient Algorithm for Similarity Joins With Edit Distance Constraints 2008 VLDB 0.00013133604
1,396 Can We Beat the Prefix Filtering? An Adaptive Framework for Similarity Join and Search 2012 SIGMOD 0.00012215253
1,947 WHAM: A High-throughput Sequence Alignment Method 2011 SIGMOD 9.9963826e-05
2,077 Extending Autocompletion To Tolerate Errors 2009 SIGMOD 9.6038296e-05
2,196 Cost-Based Variable-Length-Gram Selection for String Collections to Support Approximate Queries Efficiently 2008 SIGMOD 9.318552e-05
2,588 Pass-Join: A Partition-based Method for Similarity Joins 2012 VLDB 8.4872437e-05
2,729 String Similarity Joins: An Experimental Evaluation 2014 VLDB 8.2175463e-05
3,583 Efficient Approximate Entity Extraction with Edit Distance Constraints 2009 SIGMOD 6.944299e-05
3,779 Efficient Exact Edit Similarity Query Processing with the Asymmetric Signature Scheme 2011 SIGMOD 6.7709545e-05
3,869 An Efficient Filter for Approximate Membership Checking 2008 SIGMOD 6.6776679e-05
5,892 Efficient Approximate Search on String Collections (Tutorial) 2009 VLDB 5.2829767e-05
6,730 A Pivotal Prefix Based Filtering Algorithm for String Similarity Search 2014 SIGMOD 4.9436522e-05
7,142 Efficient Error-tolerant Query Autocompletion 2013 VLDB 4.8151659e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
2,387 Bed-Tree: An All-Purpose Index Structure for String Similarity Search Based on Edit Distance 2010 SIGMOD 8.9075095e-05
9,934 Efficient and Effective KNN Sequence Search with Approximate n-grams 2014 VLDB 4.245954e-05
125 Approximate String Joins in a Database (Almost) for Free 2001 VLDB 0.00044946098
3,869 An Efficient Filter for Approximate Membership Checking 2008 SIGMOD 6.6776679e-05
7,775 Indexing Mixed Types for Approximate Retrieval 2005 VLDB 4.6494306e-05
4,330 An Efficient Index Structure for String Databases 2001 VLDB 6.2745131e-05
11,987 Similarity Joins for Uncertain Strings 2014 SIGMOD 4.1905499e-05
3,779 Efficient Exact Edit Similarity Query Processing with the Asymmetric Signature Scheme 2011 SIGMOD 6.7709545e-05
6,730 A Pivotal Prefix Based Filtering Algorithm for String Similarity Search 2014 SIGMOD 4.9436522e-05
7,707 Efficient Top-k Algorithms for Approximate Substring Matching 2013 SIGMOD 4.6676985e-05