Locality Sensitive Hashing for Data Placement to Optimize Parallel Subgraph Query Evaluation

Recently, parallel computing systems composed of interconnected workers through a high-speed network have become readily available, thereby presenting an opportunity for parallelizing subgraph queries in large graphs. To effectively evaluate these subgraph queries, it is crucial to place vertices among different workers. In contrast to widely used hash-based techniques, our approach leverages the utilization of locality sensitive hashing methods for data placement. This paper introduces a novel graph locality sensitive hashing method named VMH, which is specifically designed for data placement by considering the labels of vertices. By employing VMH, we can effectively place similar vertices to the same worker while considering the labels of vertices, thereby reducing redundant communication and computation across multiple workers during parallel subgraph query evaluation. Extensive experimental studies conducted on both large real and synthetic graphs demonstrate that our proposed techniques lead to significant improvements in query performance compared to existing methods.