A similarity skyline approach for handling graph queries - A preliminary report

One of the fundamental problems in graph databases is similarity search for graphs of interest. Existing approaches dealing with this problem rely on a single similarity measure between graph structures. In this paper, we suggest an alternative approach allowing for searching similar graphs to a graph query where similarity between graphs is rather modeled by a vector of scalars than a unique scalar. To this end, we introduce the notion of similarity skyline of a graph query defined by the subset of graphs of the target database that are the most similar to the query in a Pareto sense. The idea is to achieve a d-dimensional comparison between graphs in terms of d local distance (or similarity) measures and to retrieve those graphs that are maximally similar in the sense of the Pareto dominance relation. A diversity-based method for refining the retrieval result is proposed as well.