DC Field | Value | Language |
---|---|---|
dc.contributor.author | HAN, WOOK SHIN | - |
dc.contributor.author | SHIN, WONSEOK | - |
dc.contributor.author | SONG, SIWOO | - |
dc.contributor.author | PARK, KUNSOO | - |
dc.date.accessioned | 2024-03-06T07:20:29Z | - |
dc.date.available | 2024-03-06T07:20:29Z | - |
dc.date.created | 2024-02-28 | - |
dc.date.issued | 2024-08-25 | - |
dc.identifier.uri | https://oasis.postech.ac.kr/handle/2014.oak/122292 | - |
dc.description.abstract | Subgraph counting is a fundamental problem in understanding and analyzing graph structured data, yet computationally challenging. This calls for an accurate and efficient algorithm for Subgraph Cardinality Estimation, which is to estimate the number of all isomorphic embeddings of a query graph in a data graph. We present FaSTest, a novel algorithm that combines (1) a powerful filtering technique to significantly reduce the sample space, (2) an adaptive tree sampling algorithm for accurate and efficient estimation, and (3) a worst-case optimal stratified graph sampling algorithm for hard instances. Extensive experiments on real-world datasets show that FaSTest outperforms state-of-the-art sampling-based methods by up to two orders of magnitude and GNN-based methods by up to three orders of magnitude in terms of accuracy. | - |
dc.language | English | - |
dc.publisher | VLDB Endowment | - |
dc.relation.isPartOf | 50th Int’l Conf. on Very Large Data Bases (VLDB) | - |
dc.relation.isPartOf | In 50th Int’l Conf. on Very Large Data Bases (VLDB) / Proc. the VLDB Endowment (PVLDB) | - |
dc.title | Cardinality Estimation of Subgraph Matching: A Filtering-Sampling Approach | - |
dc.type | Conference | - |
dc.type.rims | CONF | - |
dc.identifier.bibliographicCitation | 50th Int’l Conf. on Very Large Data Bases (VLDB) | - |
dc.citation.conferenceDate | 2024-08-25 | - |
dc.citation.conferencePlace | CC | - |
dc.citation.conferencePlace | Langham Place | - |
dc.citation.title | 50th Int’l Conf. on Very Large Data Bases (VLDB) | - |
dc.contributor.affiliatedAuthor | HAN, WOOK SHIN | - |
dc.description.journalClass | 1 | - |
dc.description.journalClass | 1 | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.
library@postech.ac.kr Tel: 054-279-2548
Copyrights © by 2017 Pohang University of Science ad Technology All right reserved.