GLogS: Interactive Graph Pattern Matching Query At Large Scale

Authors:

Longbin Lai, Alibaba Group, China; Yufan Yang, The Chinese University of Hong Kong, Shenzhen; Zhibin Wang, Nanjing University; Yuxuan Liu (4th Author) and Haotian Ma, The Chinese University of Hong Kong, Shenzhen; Sijie Shen, Bingqing Lyu, Xiaoli Zhou, Wenyuan Yu, and Zhengping Qian, Alibaba Group, China; Chen Tian and Sheng Zhong, Nanjing University; Yeh-Ching Chung, The Chinese University of Hong Kong, Shenzhen; Jingren Zhou, Alibaba Group, China

Abstract:

Interactive GPM (iGPM) is becoming increasingly important, where a series of graph pattern matching (GPM) queries are created and submitted in an interactive manner based on the insights provided by the prior queries. To solve the iGPM problem, three key considerations must be taken into account: performance, usability and scalability, namely if results can be returned in a timely manner, if queries can be written in a declarative way without the need of imperative fine-tune, and if it can work on large graphs. In this paper, we propose the GLogS system that allows users to interactively submit queries using a declarative language. The system will compile and automatically compute optimal execution plans for the queries, and execute them on an existing distributed dataflow engine. In the evaluation, we compare GLogS with the alternatives systems Neo4j and TigerGraph. GLogS outperforms Neo4j by 51 × on a single machine due to better execution plans. Additionally, GLogS can scale to processing large graphs with distributed capability. While compared to TigerGraph, GLogS is superior in usability, featuring an optimizer that can automatically compute optimal execution plans, eliminating the need of manual query tuning as required in TigerGraph.

My Duties

I am responsible for implementing the basic data structure of Catalogue and binary join operators, and the graph isomorphism algorithm to determine if two patterns are identical in structure. Most of them server as the fundamental work of the GLogS system.

Recommended citation: @inproceedings {288723, author = {Longbin Lai and Yufan Yang and Zhibin Wang and Yuxuan Liu and Haotian Ma and Sijie Shen and Bingqing Lyu and Xiaoli Zhou and Wenyuan Yu and Zhengping Qian and Chen Tian and Sheng Zhong and Yeh-Ching Chung and Jingren Zhou}, title = {{GLogS}: Interactive Graph Pattern Matching Query At Large Scale}, booktitle = {2023 USENIX Annual Technical Conference (USENIX ATC 23)}, year = {2023}, isbn = {978-1-939133-35-9}, address = {Boston, MA}, pages = {53--69}, url = {https://www.usenix.org/conference/atc23/presentation/lai}, publisher = {USENIX Association}, month = jul }
Download Paper | Download Slides