Multi-Cost and Upgradable Spatial Network Databases
Abstract
In this dissertation, we first consider data processing problems in multi-cost networks and in upgradable networks. These network types are motivated by real-life situations, which do not fall under the standard spatial network formulation and have not received much attention from database researchers. In a multi-cost network (MCN), each edge is associated with more than one weight type that may affect the user-specific perception of distance. We study two query types on MCNs, namely, the MCN skyline and the MCN top-k query. In an upgradable network, a subset of the edges are amenable to weight reduction, at a cost (e.g., monetary cost). In this context, we consider the resource constrained best upgrade plan (BUP) problem. The goal is to choose some edges for upgrade so that the sum of network distances in a specific set of source-destination pairs is minimized, without the total upgrade cost exceeding a certain budget. In the latter part of the dissertation we propose methods for the verification of shortest path search on (plain) spatial networks that are outsourced to a third-party server. Since third parties are not necessarily trusted, the users need a means to verify that the paths reported by the server are the actual shortest paths.