DBScholar

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
9512
Venue
VLDB
Year
2005
Pagerank
6.9439151e-05
Overall Rank
4,035 | 72.32%
DOI
-

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@article{jin_vldb05,
        title = {{Selectivity Estimation for Fuzzy String Predicates in Large Data Sets}},
        author = {Jin, Liang and Li, Chen},
        journal = {PVLDB},
        series = {{VLDB} '05},
        pages = {397},
        year = {2005}
}

Incoming Citations (Sorted by Pagerank)

Showing 10 of 10 citing papers.

Rank Citing Paper Year Venue Pagerank
975 Can We Beat the Prefix Filtering? An Adaptive Framework for Similarity Join and Search 2012 SIGMOD 0.00012870645
2,103 Cost-Based Variable-Length-Gram Selection for String Collections to Support Approximate Queries Efficiently 2008 SIGMOD 9.1621686e-05
2,308 Hashed Samples: Selectivity Estimators For Set Similarity Selection Queries 2008 VLDB 8.7738996e-05
2,899 Extending Q-Grams to Estimate Selectivity of String Matching with Low Edit Distance 2007 VLDB 7.97814e-05
3,446 Efficient Approximate Entity Extraction with Edit Distance Constraints 2009 SIGMOD 7.4087786e-05
5,667 Efficient Approximate Search on String Collections (Tutorial) 2009 VLDB 6.1279762e-05
7,692 Efficient Top-k Algorithms for Approximate Substring Matching 2013 SIGMOD 5.5664611e-05
8,078 Indexing Mixed Types for Approximate Retrieval 2005 VLDB 5.492543e-05
9,844 Cardinality Estimation of LIKE Predicate Queries using Deep Learning 2025 SIGMOD 5.2094602e-05
10,505 The Case For Language Model Approximated LIKE Predicate 2026 SIGMOD 5.093636e-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
35 Improved Histograms for Selectivity Estimation of Range Predicates 1996 SIGMOD 0.00048481081
58 The Merge/Purge Problem for Large Databases 1995 SIGMOD 0.00040116748
107 Approximate String Joins in a Database (Almost) for Free 2001 VLDB 0.00033511706
118 Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries 1988 SIGMOD 0.00031922279
158 Robust and Efficient Fuzzy Match for Online Data Cleaning 2003 SIGMOD 0.00028199923
267 Optimal Histograms with Quality Guarantees 1998 VLDB 0.00022798161
306 Eliminating Fuzzy Duplicates in Data Warehouses 2002 VLDB 0.00021839661
901 Estimating the Selectivity of XML Path Expressions for Internet Scale Applications 2001 VLDB 0.00013334162
977 Dynamic Maintenance of Wavelet-Based Histograms 2000 VLDB 0.00012864017
1,140 Estimating Alphanumeric Selectivity in the Presence of Wildcards 1996 SIGMOD 0.0001200574
2,061 Selectivity Estimation For Boolean Queries 2000 PODS 9.2445049e-05
3,207 Multi-Dimensional Substring Selectivity Estimation 1999 VLDB 7.6364508e-05
4,438 XPathLearner: An On-Line Self-Tuning Markov Histogram for XML Path Selectivity Estimation 2002 VLDB 6.7061802e-05
8,078 Indexing Mixed Types for Approximate Retrieval 2005 VLDB 5.492543e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 4,136 Approximating Predicates and Expressive Queries on Probabilistic Databases 2008 PODS
2 4,009 Flexible String Matching Against Large Databases in Practice 2004 VLDB
3 280 Selectivity Estimation using Probabilistic Models 2001 SIGMOD
4 12,177 Similarity Joins for Uncertain Strings 2014 SIGMOD
5 4,743 Probabilistic String Similarity Joins 2010 SIGMOD
6 35 Improved Histograms for Selectivity Estimation of Range Predicates 1996 SIGMOD
7 4,846 A Comparison of Selectivity Estimators for Range Queries on Metric Attributes 1999 SIGMOD
8 2,061 Selectivity Estimation For Boolean Queries 2000 PODS
9 934 Selectivity Estimation and Query Optimization in Large Databases with Highly Skewed Distributions of Column Values 1988 VLDB
10 2,899 Extending Q-Grams to Estimate Selectivity of String Matching with Low Edit Distance 2007 VLDB