Distance-join

TLDR

Graph databases have spurred data management challenges such as subgraph search, shortest‑path, reachability, and pattern matching, with pattern matching offering greater flexibility and informativeness. The study aims to retrieve all matches in a large graph G that preserve the connectivity of a query pattern Q. The authors embed graph vertices into a vector space, reformulating pattern matching as a distance‑based multi‑way join, and introduce pruning strategies plus a join‑order selection to accelerate processing. Extensive experiments on both real and synthetic datasets show that the proposed method outperforms existing ones by orders of magnitude.

Abstract

The growing popularity of graph databases has generated interesting data management problems, such as subgraph search, shortest-path query, reachability verification, and pattern match. Among these, a pattern match query is more flexible compared to a subgraph search and more informative compared to a shortest-path or reachability query. In this paper, we address pattern match problems over a large data graph G. Specifically, given a pattern graph (i.e., query Q ), we want to find all matches (in G ) that have the similar connections as those in Q. In order to reduce the search space significantly, we first transform the vertices into points in a vector space via graph embedding techniques, coverting a pattern match query into a distance-based multi-way join problem over the converted vector space. We also propose several pruning strategies and a join order selection method to process join processing efficiently. Extensive experiments on both real and synthetic datasets show that our method outperforms existing ones by orders of magnitude.