Name
Abstract | ||
|---|---|---|
Subgraph search is very useful in many real-world applications. However, users may be overwhelmed by the masses of matches. In this paper, we propose subgraph skyline search problem, denoted as S3, to support more complicated analysis over graph data. Specifically, given a large graph G and a query graph q, we want to find all the subgraphs g in G, such that g is graph isomorphic to q and not dominated by any other subgraphs. In order to improve the efficiency, we devise a hybrid feature encoding incorporating both structural and numeric features. Moreover, we present some optimizations based on partitioning strategy. We also propose a skylayer index to facilitate the dynamic subgraph skyline computation. Extensive experiments over real dataset confirm the effectiveness and efficiency of our algorithm. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1145/2661829.2662037 | CIKM |
Keywords | Field | DocType |
database applications,feature encoding,skylayer,subgraph skyline | Data mining,Line graph,Forbidden graph characterization,Graph factorization,Computer science,Induced subgraph isomorphism problem,Distance-hereditary graph,Factor-critical graph,Universal graph,Subgraph isomorphism problem | Conference |
Citations | PageRank | References |
7 | 0.47 | 26 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Weiguo Zheng | 1 | 205 | 16.87 |
| Lei Zou | 2 | 1161 | 68.43 |
| Xiang Lian | 3 | 35 | 5.25 |
| Liang Hong | 4 | 193 | 33.79 |
| Dongyan Zhao | 5 | 998 | 96.35 |