Database Paper Browser

Back to papers

Selectivity Estimation for Fuzzy String Predicates in Large Data Sets

Summary: Proposes Sepia, a histogram-based selectivity estimator for fuzzy string predicates. It clusters strings, builds per-cluster and global histograms, and uses a pivot to propagate q–s similarity via edit distance; extensible to other similarity measures and robust to nonuniform errors. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
9322
Venue
VLDB
Year
2005
Pagerank
6.1852739e-05
Overall Rank
4,433 | 69.20%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 10 of 10 citing papers.

Rank Citing Paper Year Venue Pagerank
1,396 Can We Beat the Prefix Filtering? An Adaptive Framework for Similarity Join and Search 2012 SIGMOD 0.00012215253
2,196 Cost-Based Variable-Length-Gram Selection for String Collections to Support Approximate Queries Efficiently 2008 SIGMOD 9.318552e-05
2,779 Hashed Samples: Selectivity Estimators For Set Similarity Selection Queries 2008 VLDB 8.1314377e-05
3,229 Extending Q-Grams to Estimate Selectivity of String Matching with Low Edit Distance 2007 VLDB 7.3390133e-05
3,583 Efficient Approximate Entity Extraction with Edit Distance Constraints 2009 SIGMOD 6.944299e-05
5,892 Efficient Approximate Search on String Collections (Tutorial) 2009 VLDB 5.2829767e-05
7,707 Efficient Top-k Algorithms for Approximate Substring Matching 2013 SIGMOD 4.6676985e-05
7,775 Indexing Mixed Types for Approximate Retrieval 2005 VLDB 4.6494306e-05
9,725 Cardinality Estimation of LIKE Predicate Queries using Deep Learning 2025 SIGMOD 4.290223e-05
10,216 The Case For Language Model Approximated LIKE Predicate 2026 SIGMOD 4.1905499e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 14 of 14 cited papers.

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

Rank Cited Paper Year Venue Pagerank
63 Improved Histograms for Selectivity Estimation of Range Predicates 1996 SIGMOD 0.00063595699
67 The Merge/Purge Problem for Large Databases 1995 SIGMOD 0.00061419648
114 Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries 1988 SIGMOD 0.00046317654
125 Approximate String Joins in a Database (Almost) for Free 2001 VLDB 0.00044946098
155 Robust and Efficient Fuzzy Match for Online Data Cleaning 2003 SIGMOD 0.00040666376
279 Eliminating Fuzzy Duplicates in Data Warehouses 2002 VLDB 0.00029141798
326 Optimal Histograms with Quality Guarantees 1998 VLDB 0.0002737538
1,045 Estimating the Selectivity of XML Path Expressions for Internet Scale Applications 2001 VLDB 0.00014451072
1,126 Dynamic Maintenance of Wavelet-Based Histograms 2000 VLDB 0.0001381102
1,145 Estimating Alphanumeric Selectivity in the Presence of Wildcards 1996 SIGMOD 0.00013672625
2,168 Selectivity Estimation For Boolean Queries 2000 PODS 9.3877451e-05
3,036 Multi-Dimensional Substring Selectivity Estimation 1999 VLDB 7.671524e-05
4,657 XPathLearner: An On-Line Self-Tuning Markov Histogram for XML Path Selectivity Estimation 2002 VLDB 6.0098065e-05
7,775 Indexing Mixed Types for Approximate Retrieval 2005 VLDB 4.6494306e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
4,439 Approximating Predicates and Expressive Queries on Probabilistic Databases 2008 PODS 6.1806955e-05
4,033 Flexible String Matching Against Large Databases in Practice 2004 VLDB 6.5125692e-05
373 Selectivity Estimation using Probabilistic Models 2001 SIGMOD 0.00025354685
11,987 Similarity Joins for Uncertain Strings 2014 SIGMOD 4.1905499e-05
4,907 Probabilistic String Similarity Joins 2010 SIGMOD 5.8365853e-05
63 Improved Histograms for Selectivity Estimation of Range Predicates 1996 SIGMOD 0.00063595699
5,066 A Comparison of Selectivity Estimators for Range Queries on Metric Attributes 1999 SIGMOD 5.7157182e-05
2,168 Selectivity Estimation For Boolean Queries 2000 PODS 9.3877451e-05
896 Selectivity Estimation and Query Optimization in Large Databases with Highly Skewed Distributions of Column Values 1988 VLDB 0.00015486851
3,229 Extending Q-Grams to Estimate Selectivity of String Matching with Low Edit Distance 2007 VLDB 7.3390133e-05