Spatial hotspot discovery aims at discovering regions with statistically significant concentration of activities. It has shown great value in many important societal applications such as transportation engineering, public health, and public safety. This paper formulates the problem of Linear Hotspot Detection on All Simple Paths (LHDA) which identifies hotspots from the complete set of simple paths enumerated from a given spatial network. LHDA overcomes the limitations of existing methods which miss hotspots that naturally occur along linear simple paths on a road network. To address the computational challenges, we propose a novel algorithm named bidirectional fragment-multi-graph traversal (ASP_FMGT) and two path reduction approaches ASP_NR and ASP_HD. Experimental analyses show that ASP_FMGT has substantially improved performance over state-of-the-art approach (ASP_Base) while keeping the solution complete and correct. Moreover, a case study on real-world datasets showed that ASP_FMGT outperforms existing approaches.
more »
« less
This content will become publicly available on November 13, 2024
Scalable Evaluation of Local K-Function for Radius-Accurate Hotspot Detection in Spatial Networks
The widespread of geotagged data combined with modern map services allows for the accurate attachment of data to spatial networks. Applying statistical analysis, such as hotspot detection, over spatial networks is very important for precise quantification and patterns analysis, which empowers effective decision-making in various important applications. Existing hotspot detection algorithms on spatial networks either lack statistical evidence on detected hotspots, such as clustering, or they provide statistical evidence at a prohibitive computational overhead. In this paper, we propose efficient algorithms for detecting hotspots based on the network local K-function for predefined and unknown hotspot radii. The network local K-function is a widely adopted statistical approach for network pattern analysis that enables the understanding of the density and distribution of activities and events in the spatial
network. However, its practical application has been limited due to the inefficiency of existing algorithms, particularly for large-sized networks. Extensive experimental evaluation using real and synthetic datasets shows that our algorithms are up to 28 times faster than the state-of-the-art algorithms in computing hotspots with a
predefined radius and up to more than four orders of magnitude faster in identifying hotspots without a predefined radius.
more »
« less
- Award ID(s):
- 2237348
- NSF-PAR ID:
- 10494684
- Publisher / Repository:
- ACM
- Date Published:
- Journal Name:
- The 31st ACM International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL '23)
- ISBN:
- 9798400701689
- Page Range / eLocation ID:
- 1 to 12
- Subject(s) / Keyword(s):
- Hotspot Detection, K-function, Spatial Network
- Format(s):
- Medium: X
- Location:
- Hamburg, Germany
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Liquid jet impingement is one of the most effective methods for dissipating local hotpot heat fluxes in microelectronics. Due to its normal incident flow-field, jet impingement cooling can achieve heat transfer coefficients (HTCs) approaching ≈1 MW/m 2 ·K due to its ability to thin the local thermal boundary layer in the stagnation region. This experimental study presents HTC data for water jet impingement cooling of a laser heated Hafnium (Hf) thin-film on glass. A laser diode induces local hotspots for either a steady- or pulsed-laser operation mode. The hotspots have areas ranging within 0.04 mm 2 to 0.2 mm 2 and heat fluxes up to ≈3.5 MW/m 2 . A submerged jet impingement configuration is pursued with an inlet jet diameter of ~1.2 mm, jet nozzle to hotspot/surface distance of ~3.2 mm, and the jet Reynolds Number of ~2004. The HTCs are measured using infrared (IR) thermometry using a 1.5-5 μm spectral resolution FLIR camera. Also investigated is the spatial dependence of the HTC relative to the offset between jet/wall stagnation point and the center of the local hotspot. For example, for impinging jets that are co-aligned with the hotspot center, HTCs of ~650 kW/m 2 ·K and ~470 kW/m 2 ·K are measured for steady and pulsed-modulated laser heating (respectively), whereas, for offsets beyond ~6 mm (x/D >5), the measured HTCs are <; 100 kW/m 2 ·K.more » « less
-
more » « less
An increase in volcanic thermal emissions can indicate subsurface and surface processes that precede, or coincide with, volcanic eruptions. Space-borne infrared sensors can detect hotspots—defined here as localized volcanic thermal emissions—in near-real-time. However, automatic hotspot detection systems are needed to efficiently analyze the large quantities of data produced. While hotspots have been automatically detected for over 20 years with simple thresholding algorithms, new computer vision technologies, such as convolutional neural networks (CNNs), can enable improved detection capabilities. Here we introduce HotLINK: the Hotspot Learning and Identification Network, a CNN trained to detect hotspots with a dataset of −3,800 satellite-based, Visible Infrared Imaging Radiometer Suite (VIIRS) images from Mount Veniaminof and Mount Cleveland volcanoes, Alaska. We find that our model achieves an accuracy of 96% (F1-score 0.92) when evaluated on −1,700 unseen images from the same volcanoes, and 95% (F1-score 0.67) when evaluated on −3,000 images from six additional Alaska volcanoes (Augustine Volcano, Bogoslof Island, Okmok Caldera, Pavlof Volcano, Redoubt Volcano, Shishaldin Volcano). In comparison with an existing threshold-based hotspot detection algorithm, MIROVA (Coppola et al., Geological Society, London, Special Publications, 2016, 426, 181–205), our model detects 22% more hotspots and produces 12% fewer false positives. Additional testing on −700 labeled Moderate Resolution Imaging Spectroradiometer (MODIS) images from Mount Veniaminof demonstrates that our model is applicable to this sensor’s data as well, achieving an accuracy of 98% (F1-score 0.95). We apply HotLINK to 10 years of VIIRS data and 22 years of MODIS data for the eight aforementioned Alaska volcanoes and calculate the radiative power of detected hotspots. From these time series we find that HotLINK accurately characterizes background and eruptive periods, similar to MIROVA, but also detects more subtle warming signals, potentially related to volcanic unrest. We identify three advantages to our model over its predecessors: 1) the ability to detect more subtle volcanic hotspots and produce fewer false positives, especially in daytime images; 2) probabilistic predictions provide a measure of detection confidence; and 3) its transferability, i.e., the successful application to multiple sensors and multiple volcanoes without the need for threshold tuning, suggesting the potential for global application.
-
null (Ed.)Outlier detection is a statistical procedure that aims to find suspicious events or items that are different from the normal form of a dataset. It has drawn considerable interest in the field of data mining and machine learning. Outlier detection is important in many applications, including fraud detection in credit card transactions and network intrusion detection. There are two general types of outlier detection: global and local. Global outliers fall outside the normal range for an entire dataset, whereas local outliers may fall within the normal range for the entire dataset, but outside the normal range for the surrounding data points. This paper addresses local outlier detection. The best-known technique for local outlier detection is the Local Outlier Factor (LOF), a density-based technique. There are many LOF algorithms for a static data environment; however, these algorithms cannot be applied directly to data streams, which are an important type of big data. In general, local outlier detection algorithms for data streams are still deficient and better algorithms need to be developed that can effectively analyze the high velocity of data streams to detect local outliers. This paper presents a literature review of local outlier detection algorithms in static and stream environments, with an emphasis on LOF algorithms. It collects and categorizes existing local outlier detection algorithms and analyzes their characteristics. Furthermore, the paper discusses the advantages and limitations of those algorithms and proposes several promising directions for developing improved local outlier detection methods for data streams.more » « less
-
more » « less
Abstract GIS analyses use moving window methods and hotspot detection to identify point patterns within a given area. Such methods can detect clusters of point events such as crime or disease incidences. Yet, these methods do not account for
connections between entities, and thus, areas with relatively sparse event concentrations but high network connectivity may go undetected. We develop two scan methods (i.e., moving window or focal processes), EdgeScan and NDScan, for detecting local spatial‐social connections. These methods capture edges and network density, respectively, for each node in a given focal area. We apply methods to a social network of Mafia members in New York City in the 1960s and to a 2019 spatial network of home‐to‐restaurant visits in Atlanta, Georgia. These methods successfully capture focal areas where Mafia members are highly connected and where restaurant visitors are highly local; these results differ from those derived using traditional spatial hotspot analysis using the Getis–Ord Gi* statistic. Finally, we describe how these methods can be adapted to weighted, directed, and bipartite networks and suggest future improvements.
