Open Access System for Information Sharing

Login Library

 

Conference
Cited 0 time in webofscience Cited 0 time in scopus
Metadata Downloads
Full metadata record
Files in This Item:
There are no files associated with this item.
DC FieldValueLanguage
dc.contributor.authorHAN, WOOK SHIN-
dc.contributor.authorKIM, KYOUNG MIN-
dc.contributor.author하재현-
dc.contributor.authorFletcher, George-
dc.date.accessioned2024-05-08T05:51:43Z-
dc.date.available2024-05-08T05:51:43Z-
dc.date.created2024-04-16-
dc.date.issued2023-06-19-
dc.identifier.urihttps://oasis.postech.ac.kr/handle/2014.oak/123207-
dc.description.abstractWe propose a new method for estimating the number of answers OUT of a small join query 𝑄 in a large database 𝐷, and for uniform sampling over joins. Our method is the first to satisfy all the following statements. • Support arbitrary 𝑄, which can be either acyclic or cyclic, and contain binary and non-binary relations. • Guarantee an arbitrary small error with a high probability always in 𝑂˜(𝐴𝐺𝑀/OUT) time, where 𝐴𝐺𝑀 is the AGM bound (an upper bound of OUT), and 𝑂˜ hides the polylogarithmic factor of input size. We also explain previous join size estimators in a unified framework. All methods including ours rely on certain indexes on relations in 𝐷, which take linear time to build offline. Additionally, we extend our method using generalized hypertree decompositions (GHDs) to achieve a lower complexity than 𝑂˜ (𝐴𝐺𝑀/OUT) when OUT is small, and present optimization techniques for improving estimation efficiency and accuracy-
dc.languageEnglish-
dc.publisherACM-
dc.relation.isPartOf42nd Symposium on Principles of Database Systems-
dc.relation.isPartOfIn Proc. 42nd Symposium on Principles of Database Systems-
dc.titleGuaranteeing the O(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins-
dc.typeConference-
dc.type.rimsCONF-
dc.identifier.bibliographicCitation42nd Symposium on Principles of Database Systems, pp.113 - 125-
dc.citation.conferenceDate2023-06-18-
dc.citation.conferencePlaceUS-
dc.citation.conferencePlaceHyatt Regency Bellevue hotel-
dc.citation.endPage125-
dc.citation.startPage113-
dc.citation.title42nd Symposium on Principles of Database Systems-
dc.contributor.affiliatedAuthorHAN, WOOK SHIN-
dc.contributor.affiliatedAuthorKIM, KYOUNG MIN-
dc.contributor.affiliatedAuthor하재현-
dc.description.journalClass1-
dc.description.journalClass1-

qr_code

  • mendeley

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

Related Researcher

Researcher

한욱신HAN, WOOK SHIN
Grad. School of AI
Read more

Views & Downloads

Browse