Name
Abstract | ||
|---|---|---|
AbstractSubgraph matching finds a set I of all occurrences of a pattern graph in a target graph. It has a wide range of applications while suffers an expensive computation. This efficiency issue has been studied extensively. All existing approaches, however, turn a blind eye to the output crisis, that is, when the system has to materialize I as a preprocessing/intermediate/final result or an index, the cost of the export of I dominates the overall cost, which could be prohibitive even for a small pattern graph.This paper studies subgraph matching via two problems. 1) Is there an ideal compression of I? 2) Will the compression of I reversely boost the computation of I? For the problem 1), we propose a technique called VCBC to compress I to code (I) which serves effectively the same as I. For problem 2), we propose a subgraph matching computation framework CBF which computes code(I)instead of I to bring down the output cost. CBF further reduces the overall cost by reducing the intermediate results. Extensive experiments show that the compression ratio of VCBC can be up to 105 which also significantly lowers the output cost of CBF. Extensive experiments show the superior performance of CBF over existing approaches. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.14778/3149193.3149198 | Hosted Content |
Field | DocType | Volume |
Graph,Data mining,Compression (physics),Computer science,Algorithm,Preprocessor,Compression ratio,Fold (higher-order function),Computation | Journal | 11 |
Issue | ISSN | Citations |
2 | 2150-8097 | 10 |
PageRank | References | Authors |
0.46 | 23 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Miao Qiao | 1 | 90 | 5.04 |
| Hao Zhang | 2 | 203 | 64.03 |
| Hong Cheng | 3 | 3694 | 148.72 |