Diversified Top-k Answering of Cypher Queries over Large Data Graphs

Cypher is the most used language for querying data graphs and it represents the main part of the Neo4j graph database system. Neo4j proposes several techniques for efficient answering of a Cypher query C over a data graph G. These techniques remain insufficient for the following raisons: 1) the answering is based on the notion of subgraph-isomorphism; 2) real-life data graphs are very large which increases dramatically the answering time; 3) there may exist an exponential number of matches, even though C is very simple, which makes inspection very difficult. On the other hand, users are often interested in only k relevant matches which are as diverse as possible. Existing solutions rely all on a formal class of queries which does not cover all features used in practice. Moreover, it is hard to see how they can be integrated within a commercial system like Neo4j. This paper proposes heuristic solutions for the diversified top-k answering of Cypher queries. We first investigate a solution that is based on level-wise strategy and aims to enhance the quality of the diversified k matches. As it examines the entire match set, this solution may be time-consuming in large data graphs. Indeed, we propose a second solution that rectifies the limit of the first one by applying the early-termination property. This solution is a trade-off between quality and efficiency as it allows to find high quality diversified k matches in a reasonable time. We show effectiveness and efficiency of our solutions using real-life and synthetic data. To our knowledge, this paper presents the first solutions for the diversified top-k answering of Cypher queries, which can be easily integrated within Neo4j.