A Novel Graph Indexing Approach for Uncovering Potential COVID-19 Transmission Clusters

Xuliang Zhu, Xin Huang, Longxu Sun, Jiming Liu

Research output: Contribution to journalJournal articlepeer-review


The COVID-19 pandemic has caused the society lockdowns and a large number of deaths in many countries. Potential transmission cluster discovery is to find all suspected users with infections, which is greatly needed to fast discover virus transmission chains so as to prevent an outbreak of COVID-19 as early as possible. In this article, we study the problem of potential transmission cluster discovery based on the spatio-temporal logs. Given a query of patient user q and a timestamp of confirmed infection tq, the problem is to find all potential infected users who have close social contacts to user q before time tq. We motivate and formulate the potential transmission cluster model, equipped with a detailed analysis of transmission cluster property and particular model usability. To identify potential clusters, one straightforward method is to compute all close contacts on-the-fly, which is simple but inefficient caused by scanning spatio-temporal logs many times. To accelerate the efficiency, we propose two indexing algorithms by constructing a multigraph index and an advanced BCG-index. Leveraging two well-designed techniques of spatio-temporal compression and graph partition on bipartite contact graphs, our BCG-index approach achieves a good balance of index construction and online query processing to fast discover potential transmission cluster. We theoretically analyze and compare the algorithm complexity of three proposed approaches. Extensive experiments on real-world check-in datasets and COVID-19 confirmed cases in the United States validate the effectiveness and efficiency of our potential transmission cluster model and algorithms.
Original languageEnglish
Article number24
Number of pages24
JournalACM Transactions on Knowledge Discovery from Data
Issue number2
Publication statusPublished - 20 Feb 2023

Scopus Subject Areas

  • Computer Science(all)

User-Defined Keywords

  • COVID-19
  • Graph index
  • transmission cluster


Dive into the research topics of 'A Novel Graph Indexing Approach for Uncovering Potential COVID-19 Transmission Clusters'. Together they form a unique fingerprint.

Cite this