Utility systems such as electric, fiber/telco, gas, and water require the realistic modeling of network attributes or values over distance. For example, consider hydraulic pressure in a pipe network; as water flows away from the reservoir or pump, pressure decreases due to pipe friction, leakage, consumption, etc. Attribute propagation is the process whereby network attributes that change over distance (e.g., maximum allowable operating pressure, phase, etc.) are calculated and maintained. This is important for improving safety as well as efficiency. However, attribute propagation is challenging due to the size of the data, which could have tens of millions of nodes and edges per utility, and billions of nodes and edges at the nationwide scale. Additionally, results may need to be calculated and available quickly for interactive analysis. Previous approaches require immediate updates to all nodes and edges downstream of a node/edge being edited (to account for changes in attribute values), which could be computationally intensive and result in a slow user experience for editing attribute values. This paper presents Propagators, which feature an in-memory approach to attribute propagation. Propagators leverage a network index as well as a heuristic based on colocated sources with similar attribute values to increase computational savings. We present experiments that demonstrate the scalability of Propagators, which have been implemented in ArcGIS Pro and ArcGIS Enterprise.

Given a utility network and one or more starting points that define where analysis should begin, the problem of analyzing utility networks entails assembling a subset of network elements that meet some specified criteria. Analyzing utility network data has several applications and provides tremendous business value to utilities. For example, analysis may answer questions about the current state of the network (e.g., what valves need to be closed to shut off water flow to a location of a pipe leak), help to design future facilities (e.g., how many houses are fed by a transformer and can the transformer supply another house without overloading its capacity?), and help to organize business practices (e.g., create circuit maps for work crews to facilitate damage assessment after an ice storm). Analyzing utility networks is a challenging problem due to 1) the size of the data, which could have many tens of millions of network elements per utility, and billions of elements at the nationwide or continental scale, 2) modeling and analyzing utility assets at high fidelity (level of detail), and 3) the different analysis requirements across utility domains (e.g., water, wastewater, sewer, district heating, gas, electric, fiber, and telecom). This paper describes the trace framework for utility network analysis that has been implemented in ArcGIS Pro 2.1/ArcGIS Enterprise 10.6. The trace framework features algorithms in a services-based architecture for addressing analysis tasks across a wide array of utility domains. Previous approaches have focused on solving specific problems in specific domains whereas the trace framework provides a more general, scalable solution. We present experiments that demonstrate the scalability of the trace framework and a case study that highlights its value in performing a wide variety of analytics on utility networks.

In smart cities, commuters have the opportunities for smart routing that may enable selecting a route with less car accidents, or one that is more scenic, or perhaps a straight and flat route. Such smart personalization requires a data management framework that goes beyond a static road network graph. This paper introduces PreGo, a novel system developed to provide real time personalized routing. The recommended routes by PreGo are smart and personalized in the sense of being (1) adjustable to individual users preferences, (2) subjective to the trip start time, and (3) sensitive to changes of the road conditions. Extensive experimental evaluation using real and synthetic data demonstrates the efficiency of the PreGo system.

Given a spatial network and a collection of activities (e.g., pedestrian fatality reports, crime reports), Significant Linear Hotspot Discovery (SLHD) finds all shortest paths in the spatial network where the concentration of activities is statistically significantly high. SLHD is important for societal applications in transportation safety or public safety such as finding paths with significant concentrations of accidents or crimes. SLHD is challenging because 1) there are a potentially large number of candidate paths ( 1016) in a given dataset with millions of activities and road network nodes and 2) test statistic (e.g., density ratio) is not monotonic. Hotspot detection approaches on euclidean space (e.g., SaTScan) may miss significant paths since a large fraction of an area bounded by shapes in euclidean space for activities on a path will be empty. Previous network-based approaches consider only paths between road intersections but not activities. This paper proposes novel models and algorithms for discovering statistically significant linear hotspots using the algorithms of neighbor node filter, shortest path tree pruning, and Monte Carlo speedup. We present case studies comparing the proposed approaches with existing techniques on real data. Experimental results show that the proposed algorithms yield substantial computational savings without reducing result quality.

Given a graph and a set of service center nodes, a Capacity Constrained Network-Voronoi Diagram (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 NPO-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 introduced a novel Pressure Equalizer (PE) approach for CCNVD to meet the capacity constraints of service centers while maintaining the contiguity of service areas. However, we find that the main bottleneck of the PE algorithm is testing whether service areas are contiguous. We propose novel algorithms that reduce the computational cost. Experiments using road maps from five different regions demonstrate that the proposed approaches significantly reduce computational cost for the PE approach.

Existing routing services calculate the best route from source to destination over a road network graph. Most commercial routing services offer the best route in terms of either the shortest travel distance or the shortest travel time (with or without considering current traffic conditions). While travel distance and travel time are crucial route preferences for the commuter, other preferences are equally, or even more, important. Examples of other route preferences include fuel consumption, gas emissions, road safety, points of interest along the route, construction activities, open shops and restaurants. While some route preferences are static (e.g., travel distance and points of interests), other route preferences are dynamic and vary according to the time of the day (e.g., traffic-dependent travel time and the number of open shops/restaurants). Volunteered Geographic information (VGI) has been proposed as an approach to collect massive amounts of route information and, more specifically, the time varying parameters. This demo presents PreGo, a time-dependent multi-preference routing engine. During the demo, audience would interact with the PreGo routing engine to (1) find the optimal route w.r.t. The user's personal preferences for a given start time, (2) dynamically obtain the best start time for a trip given a set of preferences, (3) feed the system with VGI and examine their effect on the chosen route at real time, and (4) examine the correctness and efficiency of the PreGo selected routes compared to routes chosen by other commercial systems.

Given a graph and a set of service center nodes, a Capacity Constrained Network-Voronoi Diagram (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. Our preliminary work introduced a novel Pressure Equalizer (PE) approach for CCNVD to meet the capacity constraints of service centers while maintaining the contiguity of service areas. However, we find that the main bottleneck of the PE algorithm is testing whether service areas are contiguous. In this paper, we extend our previous work and propose novel algorithms that reduce the computational cost. Experiments using road maps from five different regions demonstrate that the proposed approaches significantly reduce computational cost for the PE approach.

Given a collection of geo-located activities (e.g., Crime reports), ring-shaped hotspot detection (RHD) finds rings, where concentration of activities inside the ring is much higher than outside. RHD is important for the applications such as crime analysis, where it may focus the search for crime source's location, e.g. The home of a serial criminal. RHD is challenging because of the large number of candidate rings and the high computational cost of the statistical significance test. Previous statistically significant hotspot detection techniques (e.g., Sat Scan) identify circular/rectangular areas, but can not discover rings. This paper proposes a dual grid based pruning (DGP) approach to detect ring-shaped hotspots. A case study on real crime data confirms that DGP detects novel ring-shaped regions, regions that go undetected by Sat Scan. Experiments show that DGP improves the computational cost of a naive approach substantially.

Data summarization is an important concept in data mining for finding a compact representation of a dataset. In spatial network activity summarization (SNAS), we are given a spatial network and a collection of activities (e.g., pedestrian fatality reports, crime reports) and the goal is to find k shortest paths that summarize the activities. SNAS is important for applications where observations occur along linear paths such as roadways, train tracks, etc. SNAS is computationally challenging because of the large number of k subsets of shortest paths in a spatial network. Previous work has focused on either geometry or subgraph-based approaches (e.g., only one path), and cannot summarize activities using multiple paths. This paper proposes a K-Main Routes (KMR) approach that discovers k shortest paths to summarize activities. KMR generalizes K-means for network space but uses shortest paths instead of ellipses to summarize activities. To improve performance, KMR uses network Voronoi, divide and conquer, and pruning strategies. We present a case study comparing KMR's network-based output (i.e., shortest paths) to geometry-based outputs (e.g., ellipses) on pedestrian fatality data. Experimental results on synthetic and real data show that KMR with our performance-tuning decisions yields substantial computational savings without reducing summary path coverage.

Given a set of GPS trajectories on a road network, the goal of the k-Primary Corridors (k-PC) problem is to summarize trajectories into k groups, each represented by its most central trajectory. This problem is important to a variety of domains, such as transportation services interested in finding primary corridors for public transportation or greener travel (e.g., bicycling) by leveraging emerging GPS trajectory datasets. Related trajectory mining approaches, e.g., density or frequency based hot-routes, focus on anomaly detection rather than summarization and may not be effective for the k-PC problem. The k-PC problem is challenging due to the computational cost of creating the track similarity matrix. A naïve graph-based approach to compute a single element of this track similarity matrix requires multiple invocations of common shortest-path algorithms (e.g., Dijkstra). To reduce the computational cost of creating this track similarity matrix, we propose a novel algorithm that switches from a graph-based view to a matrix-based view, computing each element in the matrix with a single invocation of a shortest-path algorithm. Experimental results show that these ideas substantially reduce computational cost without altering the results.

Efficient tools are needed to identify routes and schedules to evacuate affected populations to safety in the event of natural disasters. Hurricane Rita and the recent tsunami revealed limitations of traditional approaches to provide emergency preparedness for evacuees and to predict the effects of evacuation route planning (ERP). Challenges arise during evacuations due to the spread of people over space and time and the multiple paths that can be taken to reach them; key assumptions such as stationary ranking of alternative routes and optimal substructure are violated in such situations. Algorithms for ERP were first developed by researchers in operations research and transportation science. However, these proved to have high computational complexity and did not scale well to large problems. Over the last decade, we developed a different approach, namely the Capacity Constrained Route Planner (CCRP), which generalizes shortest path algorithms by honoring capacity constraints and the spread of people over space and time. The CCRP uses time-aggregated graphs to reduce storage overhead and increase computational efficiency. Experimental evaluation and field use in Twin Cities Homeland Security scenarios demonstrated that CCRP is faster, more scalable, and easier to use than previous techniques. We also propose a novel scalable algorithm that exploits the spatial structure of transportation networks to accelerate routing algorithms for large network datasets. We evaluated our new approach for large-scale networks around downtown Minneapolis and riverside areas. This article summarizes experiences and lessons learned during the last decade in ERP and relates these to Professor Goodchild's contributions.