Online Subgraph Skyline Analysis over Knowledge Graphs.

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 a subgraph skyline analysis problem, denoted as $S^2A$<alternatives><inline-graphic xlink:type="simple" xlink:href="zou-ieq1-2530063.gif"/></alternatives>, to support more complicated analysis over graph data. Specifically, given a large graph $G$<alternatives><inline-graphic xlink:type="simple" xlink:href="zou-ieq2-2530063.gif"/></alternatives> and a query graph $q$<alternatives><inline-graphic xlink:type="simple" xlink:href="zou-ieq3-2530063.gif"/></alternatives>, we want to find all the subgraphs $g$<alternatives><inline-graphic xlink:type="simple" xlink:href="zou-ieq4-2530063.gif"/></alternatives> in $G$<alternatives><inline-graphic xlink:type="simple" xlink:href="zou-ieq5-2530063.gif"/></alternatives>, such that $g$<alternatives><inline-graphic xlink:type="simple" xlink:href="zou-ieq6-2530063.gif"/></alternatives> is graph isomorphic to $q$<alternatives><inline-graphic xlink:type="simple" xlink:href="zou-ieq7-2530063.gif"/></alternatives> 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 based on a partitioning strategy, and discuss how to optimize the space partitioning. We also present a skylayer index to facilitate the dynamic subgraph skyline computation. Moreover, an attribute cluster-based method is proposed to deal with the curse of dimensionality. Extensive experiments over real datasets confirm the effectiveness and efficiency of our algorithm. [ABSTRACT FROM PUBLISHER]