Selectivity Estimation on Set Containment Search

Yang, Y; Zhang, W; Zhang, Y; Lin, X; Wang, L

Selectivity Estimation on Set Containment Search

Yang, Y Zhang, W Zhang, Y

Lin, X Wang, L

Permalink

Publication Type:: Journal Article
Citation:: Data Science and Engineering, 2019, 4 (3), pp. 254 - 268
Issue Date:: 2019-09-01

Open Access

Copyright Clearance Process

Recently Added
In Progress
Open Access

This item is open access.

Adobe PDF

Download Published VersionAdobe PDF (2.35 MB)

View on publisher's site

View statistics

Full metadata record

Field	Value	Language
dc.contributor.author	Yang, Y	en_US
dc.contributor.author	Zhang, W	en_US
dc.contributor.author	Zhang, Y https://orcid.org/0000-0002-2674-1638	en_US
dc.contributor.author	Lin, X	en_US
dc.contributor.author	Wang, L	en_US
dc.date.accessioned	2020-04-17T02:29:58Z
dc.date.available	2020-04-17T02:29:58Z
dc.date.issued	2019-09-01	en_US
dc.identifier.citation	Data Science and Engineering, 2019, 4 (3), pp. 254 - 268	en_US
dc.identifier.issn	2364-1185	en_US
dc.identifier.uri	http://hdl.handle.net/10453/140069
dc.description.abstract	© 2019, The Author(s). In this paper, we study the problem of selectivity estimation on set containment search. Given a query record Q and a record dataset S, we aim to accurately and efficiently estimate the selectivity of set containment search of query Q over S. We first extend existing distinct value estimating techniques to solve this problem and develop an inverted list and G-KMV sketch-based approach IL-GKMV. We analyze that the performance of IL-GKMV 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 OT-Sampling. OT-Sampling partitions records based on element frequency and occurrence patterns and is significantly more accurate compared with simple random sampling method and IL-GKMV. To further enhance the performance, a divide-and-conquer-based sampling approach, DC-Sampling, 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 StrRS. 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.	en_US
dc.relation.ispartof	Data Science and Engineering	en_US
dc.relation.isbasedon	10.1007/s41019-019-00104-1	en_US
dc.rights	info:eu-repo/semantics/openAccess
dc.title	Selectivity Estimation on Set Containment Search	en_US
dc.type	Journal Article
utslib.citation.volume	3	en_US
utslib.citation.volume	4	en_US
pubs.embargo.period	Not known	en_US
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/DVC (International)
pubs.organisational-group	/University of Technology Sydney/DVC (International)/Australia-China Relations Institute
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology/School of Computer Science
pubs.organisational-group	/University of Technology Sydney/Strength - CAI - Centre for Artificial Intelligence
utslib.copyright.status	open_access	*
pubs.issue	3	en_US
pubs.publication-status	Published	en_US
pubs.volume	4	en_US

Abstract:

© 2019, The Author(s). In this paper, we study the problem of selectivity estimation on set containment search. Given a query record Q and a record dataset S, we aim to accurately and efficiently estimate the selectivity of set containment search of query Q over S. We first extend existing distinct value estimating techniques to solve this problem and develop an inverted list and G-KMV sketch-based approach IL-GKMV. We analyze that the performance of IL-GKMV 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 OT-Sampling. OT-Sampling partitions records based on element frequency and occurrence patterns and is significantly more accurate compared with simple random sampling method and IL-GKMV. To further enhance the performance, a divide-and-conquer-based sampling approach, DC-Sampling, 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 StrRS. 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.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/140069