Dynamic Graph Streaming Algorithm for Digital Contact Tracing
share
Digital contact tracing of an infected person, testing the possible infection for the contacted persons, and isolation play a crucial role in alleviating the outbreak. Here, we design a dynamic graph streaming algorithm that can trace the contacts under the control of the Public Health Authorities (PHA). The algorithm can work as the augmented part of the PHA for the crisis period. Our algorithm receives proximity data from the mobile devices as contact data streams and uses a sliding window model to construct a dynamic contact graph sketch. Prominently, we introduce the edge label of the contact graph as a contact vector, which acts like a sliding window and holds the latest D days of social interactions. Importantly, the algorithm prepares the direct and indirect (multilevel) contact list from the contact graph sketch for a given set of infected persons. The algorithm also uses a disjoint set data structure to construct the infectious trees for the trace list. The present study offers the design of algorithms with underlying data structures for digital contact trace relevant to the proximity data produced by Bluetooth enabled mobile devices. Our analysis reveals that for COVID-19 close contact parameters, the storage space requires maintaining the contact graph of ten million users having 14 days close contact data in PHA server takes 55 Gigabytes of memory and preparation of the contact list for a given set of the infected person depends on the size of the infected list.
READ FULL TEXT