PIGEON: Progress indicator for subgraph queries
Xiaojing Xie, Zhe Fan, Byron Koon Kau Choi, Peipei Yi, Sourav Saha Bhowmick, Shuigeng Zhou · 2015
Subgraph queries have been a fundamental query for retrieving patterns from graph data. Due to the well known NP hardness of subgraph queries, those queries may sometimes take a long time to complete. Our recent investigation on real- world datasets revealed that the performance of queries on graphs generally varies greatly. In other words, query clients may occasionally encounter “unexpectedly” long execution from a subgraph query processor. This paper aims to demonstrate a tool that alleviates the problem by monitoring subgraph query progress. Specifically, we present a novel subgraph query progress indicator called PIGEON that exploits query-time information to report to users accurate estimated query progress. In the demonstration, users may interact with PIGEON to gain insights on the query evaluation, which include the following: Users are enabled to (i) monitor query progress; (ii) analyze the causes of long query times; and (iii) abort queries that run abnormally long, which may sometimes contain human errors.