Browsing by Subject "Capacity Constrained Network Voronoi Diagram"

Now showing 1 - 1 of 1
  • Thumbnail Image
    Item
    Spatial Network Big Data: Challenges, Approaches, and Opportunities
    (2015-05) Yang, KwangSoo
    Spatial Network Big Data (SNBD) refers to spatial network datasets whose size, variety, or update rate exceeds the capacity of commonly-used spatial network computing and spatial network database technologies to learn, manage, and process with reasonable effort. SNBD has the potential to transform society via next-generation routing services, emergency and disaster response, and discovery of potentially useful patterns embedded in these datasets. However, the enormous complexity of SNBD raises many computer science challenges. My research aims to address these challenges via applying novel SNDB database systems to effectively harness the power of SNBD. This thesis studied three challenging SNDB database problems. To address the challenge of query processing for resource and shelter allocation in the wake of man-made and natural disasters, we investigated the problem of Capacity-Constrained Network-Voronoi Diagram (CCNVD). Given a graph and a set of service center nodes, CCNVD partitions the graph into a set of contiguous service areas that meet service center capacities and minimize the sum of the shortest distances from graph-nodes to allotted service centers. The CCNVD problem is important for critical societal applications such as assigning evacuees to shelters and assigning patients to hospitals. This problem is NP-hard; it is computationally challenging because of the large size of the transportation network and the constraint that service areas must be contiguous in the graph to simplify communication of allotments. Previous work has focused on honoring either service area contiguity (e.g., Network Voronoi Diagrams) or service center capacity constraints (e.g., min-cost flow), but not both. We proposed novel Pressure Equalizer (PE) approaches for CCNVD to meet the capacity constraints of service centers while maintaining the contiguity of service areas. Experiments using road maps from five different regions demonstrate that the proposed approaches significantly reduce computational cost. To address the challenge of query processing for traffic congestion and choke-points during or after disasters, we explored the problem of Evacuation Route Planning (ERP). Given a transportation network, a population, and a set of destinations, the goal of evacuation route planning is to produce routes that minimize the evacuation time for the population. Evacuation planning is essential for ensuring public safety in the wake of man-made or natural disasters (e.g., terrorist acts, hurricanes, and nuclear accidents). The problem is challenging because of the large size of network data, the large number of evacuees, and the need to account for capacity constraints in the road network. Promising methods that incorporate capacity constraints into route planning have been developed but new insights are needed to reduce the high computational costs incurred by these methods with large-scale networks. In this work, we propose a novel scalable approach that explicitly exploits the spatial structure of road networks to minimize the computational time. Our new approach accelerates the routing algorithm by partitioning the network using dartboard network-cuts and groups node-independent shortest routes to reduce the number of search iterations. Experimental results using a Minneapolis, MN road network demonstrate that the proposed approach significantly reduces the computational cost for evacuation route computation. To address the challenge of storing Spatio-Temporal Networks (STN), we explored the problem of Storing Spatio-Temporal Networks (SSTN). Given a spatio-temporal network (STN) and a set of STN operations, the goal of SSTN is to find a storage scheme that minimizes the I/O costs of the operations. The SSTN problem is important for many societal applications such as surface and air transportation management systems. The problem is NP hard, and is challenging due to an inherently large data volume and novel semantics (e.g., Lagrangian reference frame). Related works rely on orthogonal partitioning approaches (e.g., snapshot and longitudinal) and incur excessive I/O costs when performing common STN queries. In this work, we proposed novel non-orthogonal partitioning approaches in which we optimize the STN operation for a given node on an STN. Experimental results using real-world road and flight traffic datasets demonstrate that the proposed approaches outperform prior work for STN query computation workloads. The work in this thesis is the first step towards understanding the immense challenges and novel applications of SNBD database systems. In this thesis, we have formally modeled two query processing strategies (i.e., CCNVD and ERP) and begun to explore scalable algorithms to minimize the computational cost for query processing. We have also investigated a method of storing SNBD and studied how to develop I/O efficient storage and access methods. Possible directions for future work include SNBD Logical Data Model, SNBD Query Language, SNBD Query Processing Strategy, and SNBD Storage Model.