Cardinality Estimation of Subgraph Matching: A Filtering-Sampling Approach
- Title
- Cardinality Estimation of Subgraph Matching: A Filtering-Sampling Approach
- Authors
- HAN, WOOK SHIN; SHIN, WONSEOK; SONG, SIWOO; PARK, KUNSOO
- Date Issued
- 2024-08-25
- Publisher
- VLDB Endowment
- 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.
- URI
- https://oasis.postech.ac.kr/handle/2014.oak/122292
- Article Type
- Conference
- Citation
- 50th Int’l Conf. on Very Large Data Bases (VLDB), 2024-08-25
- Files in This Item:
- There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.