  The COVID19 pandemic created a worldwide emergency as it is estimated that
such a large number of infections are due to human-to-human transmission of the
COVID19. As a necessity, there is a need to track users who came in contact
with users having travel history, asymptomatic and not yet symptomatic, but
they can be in the future. To solve this problem, the present work proposes a
solution for contact tracing based on assisted GPS and cloud computing
technologies. An application is developed to collect each user's assisted GPS
coordinates once all the users install this application. This application
periodically sends assisted GPS data to the cloud. To determine which devices
are within the permissible limit of 5m, we perform clustering over assisted GPS
coordinates and track the clusters for about t mins to allow the measure of
spread. We assume that it takes around 3 or 5 mins to get the virus from an
infected object. For clustering, the proposed M way like tree data structure
stores the assisted GPS coordinates in degree, minute, and second format. Thus,
every user is mapped to a leaf node of the tree. We split the "seconds" part of
the assisted GPS location into m equal parts, which amount to d meter in
latitude(longitude). Hence, two users who are within d meter range will map to
the same leaf node. Thus, by mapping assisted GPS locations every t mins, we
can find out how many users came in contact with a particular user for at least
t mins. Our work's salient feature is that it runs in linear time O(n) for n
users in the static case, i.e., when users are not moving. We also propose a
variant of our solution to handle the dynamic case, that is, when users are
moving. Besides, the proposed solution offers potential hotspot detection and
safe-route recommendation as an additional feature, and proof of concept is
presented through experiments on simulated data of 10M users.
