{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,17]],"date-time":"2025-10-17T14:06:46Z","timestamp":1760710006800,"version":"3.37.3"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2019,9,1]],"date-time":"2019-09-01T00:00:00Z","timestamp":1567296000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2019,9,23]],"date-time":"2019-09-23T00:00:00Z","timestamp":1569196800000},"content-version":"vor","delay-in-days":22,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Data Sci. Eng."],"published-print":{"date-parts":[[2019,9]]},"abstract":"<jats:title>Abstract<\/jats:title>\n              <jats:p>In this paper, we study the problem of selectivity estimation on set containment search. Given a query record <jats:italic>Q<\/jats:italic> and a record dataset <jats:inline-formula><jats:alternatives><jats:tex-math>$${\\mathcal {S}}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mi>S<\/mml:mi>\n                    <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, we aim to accurately and efficiently estimate the selectivity of set containment search of query <jats:italic>Q<\/jats:italic> over <jats:inline-formula><jats:alternatives><jats:tex-math>$${\\mathcal {S}}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mi>S<\/mml:mi>\n                    <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. We first extend existing distinct value estimating techniques to solve this problem and develop an inverted list and <jats:italic>G-KMV<\/jats:italic> sketch-based approach <jats:italic>IL-GKMV<\/jats:italic>. We analyze that the performance of <jats:italic>IL-GKMV<\/jats:italic> degrades with the increase in vocabulary size. Motivated by limitations of existing techniques and the inherent challenges of the problem, we resort to developing effective and efficient sampling approaches and propose an ordered trie structure-based sampling approach named <jats:italic>OT-Sampling<\/jats:italic>. <jats:italic>OT-Sampling<\/jats:italic> partitions records based on element frequency and occurrence patterns and is significantly more accurate compared with simple random sampling method and <jats:italic>IL-GKMV<\/jats:italic>. To further enhance the performance, a divide-and-conquer-based sampling approach, <jats:italic>DC-Sampling<\/jats:italic>, is presented with an inclusion\/exclusion prefix to explore the pruning opportunities. Meanwhile, we consider weighted set containment selectivity estimation and devise stratified random sampling approach named <jats:italic>StrRS<\/jats:italic>.\n We theoretically analyze the proposed techniques regarding various accuracy estimators. Our comprehensive experiments on nine real datasets verify the effectiveness and efficiency of our proposed techniques.<\/jats:p>","DOI":"10.1007\/s41019-019-00104-1","type":"journal-article","created":{"date-parts":[[2019,9,23]],"date-time":"2019-09-23T14:03:26Z","timestamp":1569247406000},"page":"254-268","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Selectivity Estimation on Set Containment Search"],"prefix":"10.1007","volume":"4","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4840-3023","authenticated-orcid":false,"given":"Yang","family":"Yang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wenjie","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ying","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xuemin","family":"Lin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Liping","family":"Wang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,9,23]]},"reference":[{"key":"104_CR1","unstructured":"http:\/\/www.informatik.uni-freiburg.de\/~cziegler\/BX\/"},{"key":"104_CR2","unstructured":"http:\/\/dai-labor.de\/IRML\/datasets"},{"key":"104_CR3","unstructured":"http:\/\/socialnetworks.mpi-sws.org\/data-imc2007.html"},{"key":"104_CR4","unstructured":"http:\/\/vi.sualize.us\/"},{"key":"104_CR5","unstructured":"https:\/\/grouplens.org\/datasets\/movielens\/"},{"key":"104_CR6","unstructured":"https:\/\/snap.stanford.edu\/data\/amazon-meta.html"},{"key":"104_CR7","unstructured":"http:\/\/www.occamslab.com\/petricek\/data\/"},{"key":"104_CR8","unstructured":"Agarwal PK (1996) Range searching. Technical report, Duke Univ Durham NC Department of Computer Science"},{"key":"104_CR9","doi-asserted-by":"crossref","unstructured":"Agrawal P, Arasu A, Kaushik R (2010) On indexing error-tolerant set containment. In: SIGMOD, pp 927\u2013938","DOI":"10.1145\/1807167.1807267"},{"key":"104_CR10","volume-title":"Modern information retrieval","author":"R Baeza-Yates","year":"1999","unstructured":"Baeza-Yates R, Ribeiro-Neto B et al (1999) Modern information retrieval, vol 463. ACM press, New York"},{"key":"104_CR11","doi-asserted-by":"crossref","unstructured":"Bar-Yossef Z, Jayram T, Kumar R, Sivakumar D, Trevisan L (2002) Counting distinct elements in a data stream. In: International workshop on randomization and approximation techniques in computer science. Springer, pp 1\u201310","DOI":"10.1007\/3-540-45726-7_1"},{"key":"104_CR12","doi-asserted-by":"crossref","unstructured":"Beyer P, Haas PJ, Reinwald B, Sismanis Y, Gemulla R (2007) On synopses for distinct-value estimation under multiset operations. In: SIGMOD, pp 199\u2013210","DOI":"10.1145\/1247480.1247504"},{"issue":"1","key":"104_CR13","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1007\/s10115-015-0895-7","volume":"49","author":"P Bouros","year":"2016","unstructured":"Bouros P, Mamoulis N, Ge S, Terrovitis M (2016) Set containment join revisited. Knowl Inf Syst 49(1):375\u2013402","journal-title":"Knowl Inf Syst"},{"key":"104_CR14","doi-asserted-by":"crossref","unstructured":"Chen Z, Korn F, Koudas N, Muthukrishnan S (2000) Selectivity estimation for boolean queries. In: PODS, pp 216\u2013225","DOI":"10.1145\/335168.335225"},{"key":"104_CR15","doi-asserted-by":"crossref","unstructured":"Cohen E, Cormode G, Duffield NG (2011) Structure-aware sampling on data streams. In: SIGMETRICS, pp 197\u2013208","DOI":"10.1145\/1993744.1993763"},{"key":"104_CR16","unstructured":"Cohen E, Cormode G, Duffield NG (2014) Is min-wise hashing optimal for summarizing set intersction? In: PODS, pp 109\u2013120"},{"key":"104_CR17","doi-asserted-by":"crossref","unstructured":"Das A, Gehrke J, Riedewald M (2004) Approximation techniques for spatial data. In: SIGMOD, pp 695\u2013706","DOI":"10.1145\/1007568.1007646"},{"key":"104_CR18","doi-asserted-by":"crossref","unstructured":"Goldman R, Widom J (2000) Wsq\/dsq: a practical approach for combined querying of databases and the web. In: ACM SIGMOD record, vol\u00a029. ACM, pp 285\u2013296","DOI":"10.1145\/335191.335422"},{"issue":"3","key":"104_CR19","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1007\/s00778-003-0106-0","volume":"12","author":"S Helmer","year":"2003","unstructured":"Helmer S, Moerkotte G (2003) A performance study of four index structures for set-valued attributes of low cardinality. VLDB J 12(3):244\u2013261","journal-title":"VLDB J"},{"key":"104_CR20","doi-asserted-by":"crossref","unstructured":"Jampani R, Pudi V (2005) Using prefix-trees for efficiently computing set joins. In: International conference on database systems for advanced applications. Springer, pp 761\u2013772","DOI":"10.1007\/11408079_69"},{"key":"104_CR21","doi-asserted-by":"crossref","unstructured":"Li C, Lu J, Lu Y (2008) Efficient merging and filtering algorithms for approximate string searches. In: ICDE, pp 257\u2013266","DOI":"10.1109\/ICDE.2008.4497434"},{"key":"104_CR22","doi-asserted-by":"crossref","unstructured":"Luo Y, Fletcher GH, Hidders J, De\u00a0Bra P (2015) Efficient and scalable trie-based algorithms for computing set containment relations. In: ICDE. IEEE, pp 303\u2013314","DOI":"10.1109\/ICDE.2015.7113293"},{"key":"104_CR23","doi-asserted-by":"crossref","unstructured":"Mamoulis N (2003) Efficient processing of joins on set-valued attributes. In: SIGMOD. ACM, pp 157\u2013168","DOI":"10.1145\/872757.872778"},{"issue":"1","key":"104_CR24","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1145\/762471.762474","volume":"28","author":"S Melnik","year":"2003","unstructured":"Melnik S, Garcia-Molina H (2003) Adaptive algorithms for set containment joins. TODS 28(1):56\u201399","journal-title":"TODS"},{"key":"104_CR25","unstructured":"Ramasamy K, Patel JM, Naughton JF, Kaushik R (2000) Set containment joins: the good, the bad and the ugly. In: VLDB, pp 351\u2013362"},{"key":"104_CR26","doi-asserted-by":"crossref","unstructured":"Shrivastava A, Li P (2015) Asymmetric minwise hashing for indexing binary inner products and set containment. In: Proceedings of the 24th international conference on world wide web. International World Wide Web Conferences Steering Committee, pp 981\u2013991","DOI":"10.1145\/2736277.2741285"},{"issue":"4","key":"104_CR27","doi-asserted-by":"publisher","first-page":"633","DOI":"10.1007\/s00454-006-1269-4","volume":"36","author":"S Suri","year":"2006","unstructured":"Suri S, Toth C, Zhou Y (2006) Range counting over multidimensional data streams. Discrete Comput Geom 36(4):633\u2013655","journal-title":"Discrete Comput Geom"},{"key":"104_CR28","doi-asserted-by":"crossref","unstructured":"Terrovitis M, Bouros P, Vassiliadis P, Sellis T, Mamoulis N (2011) Efficient answering of set containment queries for skewed item distributions. In: Proceedings of the 14th international conference on extending database technology. ACM, pp 225\u2013236","DOI":"10.1145\/1951365.1951394"},{"issue":"1","key":"104_CR29","first-page":"3","volume":"22","author":"K Tzoumas","year":"2013","unstructured":"Tzoumas K, Deshpande A, Jensen CS (2013) Efficiently adapting graphical models for selectivity estimation. PVLDB 22(1):3\u201327","journal-title":"PVLDB"},{"key":"104_CR30","doi-asserted-by":"crossref","unstructured":"Vernica R, Carey MJ, Li C (2010) Efficient parallel set-similarity joins using mapreduce. In: SIGMOD, pp 495\u2013506. ACM","DOI":"10.1145\/1807167.1807222"},{"key":"104_CR31","doi-asserted-by":"crossref","unstructured":"Wang J, Li G, Feng J (2012) Can we beat the prefix filtering?: an adaptive framework for similarity join and search. In: SIGMOD, pp 85\u201396","DOI":"10.1145\/2213836.2213847"},{"issue":"2","key":"104_CR32","first-page":"101","volume":"8","author":"X Wang","year":"2014","unstructured":"Wang X, Zhang Y, Zhang W, Lin X, Wang W (2014) Selectivity estimation on streaming spatio-textual data using local correlations. PVLDB 8(2):101\u2013112","journal-title":"PVLDB"},{"key":"104_CR33","doi-asserted-by":"crossref","unstructured":"Xiao C, Wang W, Lin X, Yu JX (2008) Efficient similarity joins for near duplicate detection. In: WWW, pp 131\u2013140","DOI":"10.1145\/1367497.1367516"},{"key":"104_CR34","doi-asserted-by":"crossref","unstructured":"Yang J, Zhang W, Yang S, Zhang Y, Lin X (2017) Tt-join: efficient set containment join. In: ICDE, pp 509\u2013520","DOI":"10.1109\/ICDE.2017.107"},{"key":"104_CR35","unstructured":"Yang Y, Zhang Y, Zhang W, Huang Z (2018) Gb-kmv: an augmented kmv sketch for approximate containment similarity search. arXiv preprint \n                    arXiv:1809.00458"},{"key":"104_CR36","doi-asserted-by":"crossref","unstructured":"Zhu E, Nargesian F, Pu KQ, Miller RJ (2016) Lsh ensemble: internet scale domain search. In: VLDB, pp 1185\u20131196","DOI":"10.14778\/2994509.2994534"}],"container-title":["Data Science and Engineering"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s41019-019-00104-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s41019-019-00104-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s41019-019-00104-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,9,21]],"date-time":"2020-09-21T23:26:13Z","timestamp":1600730773000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s41019-019-00104-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,9]]},"references-count":36,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,9]]}},"alternative-id":["104"],"URL":"https:\/\/doi.org\/10.1007\/s41019-019-00104-1","relation":{},"ISSN":["2364-1185","2364-1541"],"issn-type":[{"type":"print","value":"2364-1185"},{"type":"electronic","value":"2364-1541"}],"subject":[],"published":{"date-parts":[[2019,9]]},"assertion":[{"value":"30 June 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 August 2019","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 August 2019","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 September 2019","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}