Efficient Processing of Reachability Queries with Meetings
Elena V. Strzheletska, Vassilis J. Tsotras · 2017
The prevalence of location tracking systems has resulted in large volumes of spatiotemporal data generated every day. Addressing reachability queries on such datasets is important for a wide range of applications, such as security monitoring, surveillance, public health, epidemiology, social networks, etc. Given two objects OS, OT and a time interval I, a reachability query identifies whether information (or physical items etc.) could have transferred from OS to OT during I (typically indirectly through intermediaries). While traditional graph reachability queries have been studied extensively, little work exists on processing spatiotemporal reachability queries for large disk-resident trajectory datasets. Moreover, previous research assumed that information can be passed from one object to another instantaneously. However, in many applications such transfer takes time (i.e., a short conversation), thus forcing interacting objects to stay in contact for some time interval. This requirement makes the query processing even more challenging. In this paper, we introduce a novel problem, namely, spatiotemporal reachability queries with meetings and propose two algorithms, RICCmeetMin and RICCmeetMax. To prune the search space during query time, these algorithms precompute some reachability events: the shortest valid meetings (RICCmeetMin), and the longest possible meetings (RICCmeetMax) respectively. An extended experimental evaluation examines the efficiency and pruning characteristics of both algorithms over a variety of spatiotemporal reachability queries with meetings on large disk-resident datasets.