Distance-join
Lists
Only you see this
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.
BibTeX
@article{zou2009distance,
author = {Lei Zou and Lei Chen and M. TAMER ÖZSU},
title = {{Distance-join}},
journal = {Proc. VLDB Endow.},
year = {2009},
url = {https://openreview.net/forum?id=rvE0CRILsN},
}Loading related content...