Leong Hou U

The spatiotemporal network K-function is used widely in diverse domains, e.g., transportation science, criminology, and social science, for analyzing spatiotemporal point patterns in location datasets. Domain experts calculate multiple spatiotemporal network K-functions, considering different spatial and temporal thresholds, to generate a spatiotemporal network K-function plot. However, generating this plot is computationally expensive and does not scale to large-scale location datasets. To address this shortcoming, we propose two novel methods, called edge augmentation with range-tree (EAR) and multi-threshold sharing (MTS), that reduce the time complexity for computing a spatiotemporal network K-function and generating the corresponding plot. By wisely combining these two methods, our new approach, EARTH, achieves the lowest time complexity for generating a spatiotemporal network K-function plot. Experimental results based on four large-scale location datasets show that the new methods enable speedups ranging from 2.26x to 19.04x over the state-of-the-art solutions. The implementation of this paper can be found in https://github.com/edisonchan2013928/EARTH.

Point-to-Line Nearest Neighbor Search (PLNNS) aims to project each location data point to the nearest line (or road), which is a prior step for many commonly used road network analysis tools. Therefore, PLNNS has been adopted in many application domains, e.g., transportation science, crime science, and urban planning. However, PLNNS is computationally expensive, which acts as the main bottleneck in a road network analysis pipeline. To address the efficiency issue of PLNNS, we first develop the approximate grid compression method, called GRID_COMP^APPROX, which utilizes a small number of grid cells to represent all data points for efficiently solving the PLNNS problem with a non-trivial approximation guarantee. In order to ensure the exact correctness in road network analysis, we then develop GRID_COMP^EXACT, which further achieves the exact result of solving the PLNNS problem. Our experiment results on four large-scale datasets show that GRID_COMP^APPROX and GRID_COMP^EXACT achieve 7.72x to 524.3x and 5.64x to 18.76x speedups, respectively, compared with the state-of-the-art solution. The implementation of all methods can be found in https://github.com/fastnsa/grid-comp-plnns.

Multivariate time series (MTS) anomaly detection identifies abnormal patterns where each timestamp contains multiple variables. Existing MTS anomaly detection methods fall into three categories: reconstruction-based, prediction-based, and classifier-based methods. However, these methods face three key challenges: (1) Unsupervised learning methods, such as reconstruction-based and prediction-based methods, rely on error thresholds, which can lead to inaccuracies; (2) Semi-supervised methods mainly model normal dataand often underuse anomaly labels, limiting detection of subtle anomalies; (3) Supervised learning methods, such as classifier-based approaches, often fail to capture local relationships, incur high computational costs, and are constrained by the scarcity of labeled data. To address these limitations, we propose Moon, a supervised modality conversion-based multivariate time series anomaly detection framework. Moon enhances the efficiency and accuracy of anomaly detection while providing detailed anomaly analysis reports. First, Moon introduces a novel multivariate Markov Transition Field (MV-MTF) technique to convert numeric time series data into image representations, capturing relationships across variables and timestamps. Since numeric data retains unique patterns that cannot be fully captured by image conversion alone, Moon employs a Multimodal-CNN to integrate numeric and image data through a feature fusion model with parameter sharing, enhancing training efficiency. Finally, a SHAP-based anomaly explainer identifies key variables contributing to anomalies, improving interpretability. Extensive experiments on six real-world MTS datasets demonstrate that Moon outperforms six state-of-the-art methods by up to 93% in efficiency, 4% in accuracy and, 10.8% in interpretation performance.

Graphs offer a flexible structure for vision tasks, with CNNs and Transformers conditioned as two specific cases of graph structures. In CNNs, the input images are treated as graphs where only neighboring patches are connected, whereas Transformers view images as fully connected graphs. To leverage the potential of graphs in video representation learning, effective graph generation and training methods are crucial. To this end, we propose VideoGNN, which represents the video as a discrete time dynamic graph and learns the dynamic graph efficiently. Given the multitude of frames in videos, we introduce an efficient graph generation module characterized by low complexity and high quality, facilitating the transformation of videos into dynamic graphs. Additionally, we introduce a dual-view graph neural network to capture spatial and temporal information from the generated dynamic graphs. Then, a sequential model is applied to capture the long-term temporal information and generate the final frame embeddings. Experiments demonstrate that VideoGNN can achieve competitive results in terms of graph quality assessment and video downstream tasks. The codes are available at https://github.com/Dodo-D-Caster/VideoGNN .