Database Paper Browser

Back to papers

Extending Q-Grams to Estimate Selectivity of String Matching with Low Edit Distance

Summary: Extends q-grams with wildcards to estimate selectivity for approximate string matching. Proposes replacement semi-lattice and string hierarchy; presents BasicEQ and two improvements to OptEQ; experiments on three benchmarks show OptEQ outperforms SEPIA. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
9576
Venue
VLDB
Year
2007
Pagerank
7.3390133e-05
Overall Rank
3,229 | 77.56%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 15 of 15 citing papers.

Rank Citing Paper Year Venue Pagerank
1,232 Ed-Join: An Efficient Algorithm for Similarity Joins With Edit Distance Constraints 2008 VLDB 0.00013133604
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,779 Hashed Samples: Selectivity Estimators For Set Similarity Selection Queries 2008 VLDB 8.1314377e-05
3,583 Efficient Approximate Entity Extraction with Edit Distance Constraints 2009 SIGMOD 6.944299e-05
4,352 Astrid: Accurate Selectivity Estimation for String Predicates using Deep Learning 2021 VLDB 6.2542257e-05
4,871 Power-Law Based Estimation of Set Similarity Join Size 2009 VLDB 5.8568724e-05
4,907 Probabilistic String Similarity Joins 2010 SIGMOD 5.8365853e-05
5,071 Faerie: Efficient Filtering Algorithms for Approximate Dictionary-based Entity Extraction 2011 SIGMOD 5.7122974e-05
5,892 Efficient Approximate Search on String Collections (Tutorial) 2009 VLDB 5.2829767e-05
7,188 LPLM: A Neural Language Model for Cardinality Estimation of LIKE-Queries 2024 SIGMOD 4.8017628e-05
7,473 Cardinality Estimation of Approximate Substring Queries using Deep Learning 2022 VLDB 4.7149077e-05
7,707 Efficient Top-k Algorithms for Approximate Substring Matching 2013 SIGMOD 4.6676985e-05
9,725 Cardinality Estimation of LIKE Predicate Queries using Deep Learning 2025 SIGMOD 4.290223e-05
9,947 SSCard: Substring Cardinality Estimation using Suffix Tree-Guided Learned FM-Index 2026 SIGMOD 4.2391999e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 9 of 9 cited papers.

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

Rank Cited Paper Year Venue Pagerank
36 Fast Algorithms for Mining Association Rules 1994 VLDB 0.00076114894
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
1,045 Estimating the Selectivity of XML Path Expressions for Internet Scale Applications 2001 VLDB 0.00014451072
1,145 Estimating Alphanumeric Selectivity in the Presence of Wildcards 1996 SIGMOD 0.00013672625
1,379 Substring Selectivity Estimation 1999 PODS 0.00012280308
4,433 Selectivity Estimation for Fuzzy String Predicates in Large Data Sets 2005 VLDB 6.1852739e-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
2,168 Selectivity Estimation For Boolean Queries 2000 PODS 9.3877451e-05
1,203 VGRAM: Improving Performance of Approximate Queries on String Collections Using Variable-Length Grams 2007 VLDB 0.00013317317
3,779 Efficient Exact Edit Similarity Query Processing with the Asymmetric Signature Scheme 2011 SIGMOD 6.7709545e-05
3,036 Multi-Dimensional Substring Selectivity Estimation 1999 VLDB 7.671524e-05
1,232 Ed-Join: An Efficient Algorithm for Similarity Joins With Edit Distance Constraints 2008 VLDB 0.00013133604
2,196 Cost-Based Variable-Length-Gram Selection for String Collections to Support Approximate Queries Efficiently 2008 SIGMOD 9.318552e-05
125 Approximate String Joins in a Database (Almost) for Free 2001 VLDB 0.00044946098
1,379 Substring Selectivity Estimation 1999 PODS 0.00012280308
4,433 Selectivity Estimation for Fuzzy String Predicates in Large Data Sets 2005 VLDB 6.1852739e-05
7,707 Efficient Top-k Algorithms for Approximate Substring Matching 2013 SIGMOD 4.6676985e-05