PIGEON: Progress indicator for subgraph queries

Xiaojing Xie, Zhe Fan, Koon Kau CHOI, Peipei Yi, Sourav S. Bhowmick, Shuigeng Zhou

Research output: Chapter in book/report/conference proceedingConference proceedingpeer-review

7 Citations (Scopus)


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.

Original languageEnglish
Title of host publication2015 IEEE 31st International Conference on Data Engineering, ICDE 2015
PublisherIEEE Computer Society
Number of pages4
ISBN (Electronic)9781479979639
Publication statusPublished - 26 May 2015
Event31st IEEE International Conference on Data Engineering, ICDE 2015 - Seoul, Korea, Republic of
Duration: 13 Apr 201517 Apr 2015

Publication series

NameProceedings - International Conference on Data Engineering
ISSN (Print)1084-4627


Conference31st IEEE International Conference on Data Engineering, ICDE 2015
Country/TerritoryKorea, Republic of

Scopus Subject Areas

  • Software
  • Signal Processing
  • Information Systems


Dive into the research topics of 'PIGEON: Progress indicator for subgraph queries'. Together they form a unique fingerprint.

Cite this