Leveraging graph dimensions in online graph search
Publication in refereed journal


Times Cited
Altmetrics Information
.

Other information
AbstractGraphs have been widely used due to its expressive power to model complicated relationships. However, given a graph database DG = {g1; g2; �P�P�P , gn}, it is challenging to process graph queries since a basic graph query usually involves costly graph operations such as maximum common subgraph and graph edit distance computation, which are NP-hard. In this paper, we study a novel DS-preserved mapping which maps graphs in a graph database DG onto a multidimensional space MG under a structural dimension Musing a mapping function �p(). The DS-preserved mapping preserves two things: distance and structure. By the distance-preserving, it means that any two graphs gi and gj in DG must map to two data objects �p(gi) and �p(gj) in MG, such that the distance, d(�p(gi); �p(gj), between �p(gi) and �p(gj) in MG approximates the graph dissimilarity �_(gi; gj) in DG. By the structure-preserving, it further means that for a given unseen query graph q, the distance between q and any graph gi in DG needs to be preserved such that �_(q; gi) ? d(�p(q); �p(gi)). We discuss the rationality of using graph dimension M for online graph processing, and show how to identify a small set of subgraphs to form M efficiently. We propose an iterative algorithm DSPM to compute the graph dimension, and discuss its optimization techniques. We also give an approximate algorithm DSPMap in order to handle a large graph database. We conduct extensive performance studies on both real and synthetic datasets to evaluate the top-k similarity query which is to find top-k similar graphs from DG for a query graph, and show the effectiveness and efficiency of our approaches. ? 2014 VLDB.
All Author(s) ListZhu Y., Yu J.X., Qin L.
Journal nameProceedings of the VLDB Endowment
Detailed descriptionorganized by PVLDB,
Year2014
Month1
Day1
Volume Number8
Issue Number1
Pages85 - 96
ISSN2150-8097
LanguagesEnglish-United Kingdom

Last updated on 2021-03-03 at 23:44