| In many application scenarios, an item, such as a message, a piece of sensitive information, contagious virus or a malicious malware, passes between two objects, such as moving vehicles, individuals or cell phone devices, when the objects are sufficiently close (i.e., when they are, so-called, in contact), and some application specific constraints are satisfied. An example of "constraint" in the transmission of a malware is that it takes some time such that the malware is activated on a cell phone and then it can be transmitted to another one via Bluetooth. As another example for constraint, a message passes between two vehicles with a probability which depends on various conditions such as the distance between the vehicles. In such applications, once an item is initiated, it can penetrate the object population through the evolving network of contacts among objects, termed "contact network''. A reachability query evaluates whether two objects are "reachable'' through the contact network. In this dissertation, we define and study reachability query in large (i.e., disk resident) contact datasets which verifies whether two objects are "reachable" through the contact network represented by such contact datasets. The main characteristics of our problem are the large scale of the contact dataset as well as the dynamism of the network which models the contact dataset. This underlying network evolves over the time period during which the contact dataset is constructed as the objects are moving in the environment and subsequently new contacts appear and old contacts disappear over time.;In this dissertation, due to the complexity of the general problem, we first simplify the problem by focusing on reachability in contact datasets with no-constraints. With such contact datasets, an item passes between two objects when they are close enough. We propose two contact dataset indexes, termed ReachGrid and ReachGraph, for efficient reachability query processing. With ReachGrid, at the query time only a small necessary portion of the contact dataset is constructed and traversed. With ReachGraph, we precompute and leverage reachability at different scales for efficient query processing. We optimize the disk placement of both indexes for efficient query processing.;Afterward, we extend ReachGrid and ReachGraph for contact networks with constraints. To this end, as a case study we focus on a specific type of constraint, i.e., the latency constraint, and adopt ReachGraph and ReachGrid for efficient reachability query processing. Furthermore, we discuss how to generalize ReachGraph and ReachGrid for contact networks with general constraints based on the insights we obtain from focusing on contact networks with latency. |
