More Web Proxy on the site http://driver.im/

research-article

Hashed samples: selectivity estimators for set similarity selection queries

Authors:

Marios Hadjieleftheriou,

Divesh SrivastavaAuthors Info & Claims

Proceedings of the VLDB Endowment, Volume 1, Issue 1

Pages 201 - 212

https://doi.org/10.14778/1453856.1453883

Published: 01 August 2008 Publication History

Abstract

We study selectivity estimation techniques for set similarity queries. A wide variety of similarity measures for sets have been proposed in the past. In this work we concentrate on the class of weighted similarity measures (e.g., TF/IDF and BM25 cosine similarity and variants) and design selectivity estimators based on a priori constructed samples. First, we study the pitfalls associated with straightforward applications of random sampling, and argue that care needs to be taken in how the samples are constructed; uniform random sampling yields very low accuracy, while query sensitive realtime sampling is more expensive than exact solutions (both in CPU and I/O cost). We show how to build robust samples a priori, based on existing synopses for distinct value estimation. We prove the accuracy of our technique theoretically, and verify its performance experimentally. Our algorithm is orders of magnitude faster than exact solutions and has very small space overhead.

References

[1]

N. Alon, M. Dietzfelbinger, P. B. Miltersen, E. Petrank, and G. Tardos. Linear hash functions. Journal of the ACM (JACM), 46(5):667--683, 1999.

Digital Library

[2]

A. Arasu, V. Ganti, and R. Kaushik. Efficient exact set-similarity joins. In Proc. of Very Large Data Bases (VLDB), pages 918--929, 2006.

Digital Library

[3]

AT&T Inc. Business listings from YellowPages.com. proprietary.

[4]

R. Baeza-Yates and B. Ribeiro-Neto. Modern Information Retrieval. Addison Wesley, May 1999.

Digital Library

[5]

R. A. Baeza-Yates and G. Navarro. Faster approximate string matching. Algorithmica, 23(2):127--158, 1999.

[6]

K. Beyer, P. J. Haas, B. Reinwald, Y. Sismanis, and R. Gemulla. On synopses for distinct-value estimation under multiset operations. In Proc. of ACM Management of Data (SIGMOD), pages 199--210, 2007.

Digital Library

[7]

A. Blumer, A. Ehrenfeucht, D. Haussler, and M. K. Warmuth. Learnability and the vapnik-chervonenkis dimension. Journal of the ACM (JACM), 36(4):929--965, 1989.

Digital Library

[8]

J. L. Carter and M. N. Wegman. Universal classes of hash functions. Journal of Computer and System Sciences, 18(2):143--154, 1979.

[9]

A. Chandel, O. Hassanzadeh, N. Koudas, M. Sadoghi, and D. Srivastava. Benchmarking declarative approximate selection predicates. In Proc. of ACM Management of Data (SIGMOD), pages 353--364, 2007.

Digital Library

[10]

M. Charikar, S. Chaudhuri, R. Motwani, and V. Narasayya. Towards estimation error guarantees for distinct values. In Proc. of ACM Symposium on Principles of Database Systems (PODS), pages 268--279, 2000.

Digital Library

[11]

S. Chaudhuri, G. Das, and U. Srivastava. Effective use of block-level sampling in statistics estimation. In Proc. of ACM Management of Data (SIGMOD), pages 287--298, 2004.

Digital Library

[12]

S. Chaudhuri, V. Ganti, and L. Gravano. Selectivity estimation for string predicates: Overcoming the underestimation problem. In Proc. of International Conference on Data Engineering (ICDE), pages 227--238, 2004.

Digital Library

[13]

S. Chaudhuri, V. Ganti, and R. Kaushik. A primitive operator for similarity joins in data cleaning. In Proc. of International Conference on Data Engineering (ICDE), page 5, 2006.

Digital Library

[14]

P. Flajolet and G. N. Martin. Probabilistic counting algorithms for data base applications. Journal of Computer and System Sciences, 31(2):182--209, 1985.

Digital Library

[15]

L. Gravano, P. G. Ipeirotis, H. V. Jagadish, N. Koudas, S. Muthukrishnan, and D. Srivastava. Approximate string joins in a database (almost) for free. In Proc. of Very Large Data Bases (VLDB), pages 491--500, 2001.

Digital Library

[16]

S. Guha, N. Koudas, D. Srivastava, and X. Yu. Reasoning about approximate match query results. In Proc. of International Conference on Data Engineering (ICDE), pages 8--18, 2006.

Digital Library

[17]

P. J. Haas and C. König. A bi-level bernoulli scheme for database sampling. In Proc. of ACM Management of Data (SIGMOD), pages 275--286, 2004.

Digital Library

[18]

M. Hadjieleftheriou, A. Chandel, N. Koudas, and D. Srivastava. Fast indexes and algorithms for set similarity selection queries. In Proc. of International Conference on Data Engineering (ICDE), 2008.

Digital Library

[19]

D. Haussler and E. Welzl. Epsilon-nets and simplex range queries. In Proc. of Annual Symposium on Computational Geometry (SCG), pages 61--71, 1986.

Digital Library

[20]

IMDB. IMDB database. http:// www.imdb.com/interfaces.

[21]

H. V. Jagadish, O. Kapitskaia, R. T. Ng, and D. Srivastava. One-dimensional and multi-dimensional substring selectivity estimation. The VLDB Journal, 9(3):214--230, 2000.

Digital Library

[22]

L. Jin and C. Li. Selectivity estimation for fuzzy string predicates in large data sets. In Proc. of Very Large Data Bases (VLDB), pages 397--408, 2005.

Digital Library

[23]

H. Lee, R. Ng, and K. Shim. Extending q-grams to estimate selectivity of string matching with low edit distance. In Proc. of Very Large Data Bases (VLDB), pages 195--205, 2007.

Digital Library

[24]

M. Ley. DBLP database. http://dblp.uni-trier.de/xml.

[25]

A. Mazeika, M. H. Böhlen, N. Koudas, and D. Srivastava. Estimating the selectivity of approximate string queries. ACM Transactions on Database Systems (TODS), 32(2):12, 2007.

Digital Library

[26]

F. Olken. Random sampling from databases. PhD thesis, University of California, Berkeley, CA, 1993.

[27]

V. Poosala, P. J. Haas, Y. E. Ioannidis, and E. J. Shekita. Improved histograms for selectivity estimation of range predicates. In Proc. of ACM Management of Data (SIGMOD), pages 294--305, 1996.

Digital Library

[28]

S. C. Sahinalp, M. Tasan, J. Macker, and Z. M. Özsoyoglu. Distance based indexing for string proximity search. In Proc. of International Conference on Data Engineering (ICDE), pages 125--136, 2003.

[29]

S. Sarawagi and A. Bhamidipaty. Interactive deduplication using active learning. In Proc. of ACM Knowledge Discovery and Data Mining (SIGKDD), pages 269--278, 2002.

Digital Library

[30]

S. Sarawagi and A. Kirpal. Efficient set joins on similarity predicates. In Proc. of ACM Management of Data (SIGMOD), pages 743--754, 2004.

Digital Library

[31]

S. Tata and J. M. Patel. Estimating the selectivity of tf-idf based cosine similarity predicates. SIGMOD Record, 36(2):7--12, 2007.

Digital Library

[32]

V. N. Vapnik and A. Y. Chrervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. SIAM: Theory of Probability and its Applications (TPA), 16(2):264--280, 1971.

[33]

J. S. Vitter. Random sampling with a reservoir. ACM Transactions on Mathematical Software, 11(1):37--57, 1985.

Digital Library

Cited By

Meng ZCao XCong G(2023)Selectivity Estimation for Queries Containing Predicates over Set-Valued AttributesProceedings of the ACM on Management of Data10.1145/36267551:4(1-26)Online publication date: 12-Dec-2023
https://dl.acm.org/doi/10.1145/3626755
Mundra PZhang JNargesian FAugsten N(2023)Koios: Top-k Semantic Overlap Set Search2023 IEEE 39th International Conference on Data Engineering (ICDE)10.1109/ICDE55515.2023.00121(1531-1543)Online publication date: Apr-2023
https://doi.org/10.1109/ICDE55515.2023.00121
Stoddard JMustafa AGoela N(2021)Tanium revealProceedings of the VLDB Endowment10.14778/3476311.347638614:12(3096-3109)Online publication date: 28-Oct-2021
https://dl.acm.org/doi/10.14778/3476311.3476386
Show More Cited By

Index Terms

Hashed samples: selectivity estimators for set similarity selection queries

Recommendations

Joins on samples: a theoretical guide for practitioners

Despite decades of research on AQP (approximate query processing), our understanding of sample-based joins has remained limited and, to some extent, even superficial. The common belief in the community is that joining random samples is futile. This ...
Estimating set intersection using small samples
ACSC '10: Proceedings of the Thirty-Third Australasian Conferenc on Computer Science - Volume 102

The similarity of two sets A, B can be measured by the size of their intersection A ∩ B, relative to the size of A and B. The classic measure here is resemblance or Jaccard similarity, but other useful measures (e.g. subset containment) can be derived ...
Unbiased Similarity Estimators Using Samples
Similarity Search and Applications
Abstract
Computing a similarity measure (or a distance) between two complex objects is a fundamental building block for a huge number of applications in a wide variety of domains. Since many tasks involve computing such similarities among many pairs of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Proceedings of the VLDB Endowment

Proceedings of the VLDB Endowment Volume 1, Issue 1

August 2008

1216 pages

ISSN:2150-8097

Issue’s Table of Contents

Publisher

VLDB Endowment

Publication History

Published: 01 August 2008

Published in PVLDB Volume 1, Issue 1

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

47
Total Citations
View Citations
294
Total Downloads

Downloads (Last 12 months)6
Downloads (Last 6 weeks)0

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Meng ZCao XCong G(2023)Selectivity Estimation for Queries Containing Predicates over Set-Valued AttributesProceedings of the ACM on Management of Data10.1145/36267551:4(1-26)Online publication date: 12-Dec-2023
https://dl.acm.org/doi/10.1145/3626755
Mundra PZhang JNargesian FAugsten N(2023)Koios: Top-k Semantic Overlap Set Search2023 IEEE 39th International Conference on Data Engineering (ICDE)10.1109/ICDE55515.2023.00121(1531-1543)Online publication date: Apr-2023
https://doi.org/10.1109/ICDE55515.2023.00121
Stoddard JMustafa AGoela N(2021)Tanium revealProceedings of the VLDB Endowment10.14778/3476311.347638614:12(3096-3109)Online publication date: 28-Oct-2021
https://dl.acm.org/doi/10.14778/3476311.3476386
Li YYu XKoudas N(2021)LES3Proceedings of the VLDB Endowment10.14778/3476249.347626314:11(2073-2086)Online publication date: 1-Jul-2021
https://dl.acm.org/doi/10.14778/3476249.3476263
Shanghooshabad AKurmanji MMa QShekelyan MAlmasi MTriantafillou PLi GLi ZIdreos SSrivastava D(2021)PGMJoins: Random Join Sampling with Graphical ModelsProceedings of the 2021 International Conference on Management of Data10.1145/3448016.3457302(1610-1622)Online publication date: 9-Jun-2021
https://dl.acm.org/doi/10.1145/3448016.3457302
Izquierdo YGarcía GMenendez ELeme LNeves ALemos MFinamore AOliveira CCasanova M(2021)Keyword search over schema-less RDF datasets by SPARQL query compilationInformation Systems10.1016/j.is.2021.101814102:COnline publication date: 1-Dec-2021
https://dl.acm.org/doi/10.1016/j.is.2021.101814
Augustine JShetiya SAsudeh AThirumuruganathan SNazi AZhang NDas GSrivastava D(2020)Orca-SRProceedings of the VLDB Endowment10.14778/3415478.341552313:12(2977-2980)Online publication date: 1-Aug-2020
https://dl.acm.org/doi/10.14778/3415478.3415523
Rafiei DDeng F(2020)Similarity Join and Similarity Self-Join Size Estimation in a Streaming EnvironmentIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2019.289317532:4(768-781)Online publication date: 1-Apr-2020
https://doi.org/10.1109/TKDE.2019.2893175
Li LZheng SCai JLi J(2020)Efficient Source Selection for Error Detection via Matching DependenciesDatabase Systems for Advanced Applications10.1007/978-3-030-59410-7_13(211-227)Online publication date: 24-Sep-2020
https://dl.acm.org/doi/10.1007/978-3-030-59410-7_13
Huang DYoon DPettie SMozafari B(2019)Joins on samplesProceedings of the VLDB Endowment10.14778/3372716.337272613:4(547-560)Online publication date: 9-Dec-2019
https://dl.acm.org/doi/10.14778/3372716.3372726
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents