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
9321
Venue
VLDB
Year
2005
Pagerank
6.1898903e-05
Overall Rank
4,438 | 69.13%
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.00012204748
2,193 Cost-Based Variable-Length-Gram Selection for String Collections to Support Approximate Queries Efficiently 2008 SIGMOD 9.3178557e-05
2,779 Hashed Samples: Selectivity Estimators For Set Similarity Selection Queries 2008 VLDB 8.1320575e-05
3,226 Extending Q-Grams to Estimate Selectivity of String Matching with Low Edit Distance 2007 VLDB 7.3433307e-05
3,578 Efficient Approximate Entity Extraction with Edit Distance Constraints 2009 SIGMOD 6.9503858e-05
5,887 Efficient Approximate Search on String Collections (Tutorial) 2009 VLDB 5.2879769e-05
7,708 Efficient Top-k Algorithms for Approximate Substring Matching 2013 SIGMOD 4.6721808e-05
7,777 Indexing Mixed Types for Approximate Retrieval 2005 VLDB 4.653704e-05
9,726 Cardinality Estimation of LIKE Predicate Queries using Deep Learning 2025 SIGMOD 4.2943379e-05
10,216 The Case For Language Model Approximated LIKE Predicate 2026 SIGMOD 4.1945683e-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
64 Improved Histograms for Selectivity Estimation of Range Predicates 1996 SIGMOD 0.00063612837
67 The Merge/Purge Problem for Large Databases 1995 SIGMOD 0.00061348205
116 Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries 1988 SIGMOD 0.00046148737
125 Approximate String Joins in a Database (Almost) for Free 2001 VLDB 0.00044847972
155 Robust and Efficient Fuzzy Match for Online Data Cleaning 2003 SIGMOD 0.00040637896
280 Eliminating Fuzzy Duplicates in Data Warehouses 2002 VLDB 0.00029113044
326 Optimal Histograms with Quality Guarantees 1998 VLDB 0.00027358981
1,046 Estimating the Selectivity of XML Path Expressions for Internet Scale Applications 2001 VLDB 0.00014462307
1,127 Dynamic Maintenance of Wavelet-Based Histograms 2000 VLDB 0.00013819179
1,146 Estimating Alphanumeric Selectivity in the Presence of Wildcards 1996 SIGMOD 0.00013679782
2,171 Selectivity Estimation For Boolean Queries 2000 PODS 9.3807165e-05
3,035 Multi-Dimensional Substring Selectivity Estimation 1999 VLDB 7.6748073e-05
4,660 XPathLearner: An On-Line Self-Tuning Markov Histogram for XML Path Selectivity Estimation 2002 VLDB 6.014625e-05
7,777 Indexing Mixed Types for Approximate Retrieval 2005 VLDB 4.653704e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
4,442 Approximating Predicates and Expressive Queries on Probabilistic Databases 2008 PODS 6.186154e-05
4,026 Flexible String Matching Against Large Databases in Practice 2004 VLDB 6.5169976e-05
372 Selectivity Estimation using Probabilistic Models 2001 SIGMOD 0.00025354779
11,979 Similarity Joins for Uncertain Strings 2014 SIGMOD 4.1945683e-05
4,901 Probabilistic String Similarity Joins 2010 SIGMOD 5.8411648e-05
64 Improved Histograms for Selectivity Estimation of Range Predicates 1996 SIGMOD 0.00063612837
5,082 A Comparison of Selectivity Estimators for Range Queries on Metric Attributes 1999 SIGMOD 5.711623e-05
2,171 Selectivity Estimation For Boolean Queries 2000 PODS 9.3807165e-05
897 Selectivity Estimation and Query Optimization in Large Databases with Highly Skewed Distributions of Column Values 1988 VLDB 0.00015528028
3,226 Extending Q-Grams to Estimate Selectivity of String Matching with Low Edit Distance 2007 VLDB 7.3433307e-05