Given a set of historical vehicle trajectories and their descriptive attributes, the goal is to train a generative model that produces synthetic trajectories with high physical fidelity. Here, physical fidelity is defined as fidelity to both geometric and dynamic properties of trajectories. The problem is important since trajectory generation can contribute to data augmentation for many traffic-related applications, such as popular route discovery and traffic light control. The key challenge of this problem lies in achieving high physical fidelity under coarse geospatial attributes (e.g., origin-destination pairs) that lack fine-grained details. Current methods, which mostly focus on geometric properties, have limited utility in domain-specific scenarios due to their neglect of trajectory dynamics. To address these limitations, we propose GCDM, a novel Geo-Lucid Conditional Diffusion Model framework that integrates road map attributes into the generative process through spatially hierarchical generation and map-informed latent variables. Experiments on real-world vehicle trajectory datasets show that GCDM outperforms state-of-the-art methods in geo-distribution similarity and dynamics fidelity.

Given multi-type point maps from different place-types (e.g., tumor regions), our objective is to develop a classifier trained on the source place-type to accurately distinguish between two classes of the target place-type based on their point arrangements. This problem is societally important for many applications, such as generating clinical hypotheses for designing new immunotherapies for cancer treatment. The challenge lies in the spatial variability, the inherent heterogeneity and variation observed in spatial properties or arrangements across different locations (i.e., place-types). Previous techniques focus on self-supervised tasks to learn domain-invariant features and mitigate domain differences; however, they often neglect the underlying spatial arrangements among data points, leading to significant discrepancies across different place-types. We explore a novel multi-task self-learning framework that targets spatial arrangements, such as spatial mix-up masking and spatial contrastive predictive coding, for spatially-delineated domain-adapted AI classification. Experimental results on real-world datasets (e.g., oncology data) show that the proposed framework provides higher prediction accuracy than baseline methods.

Given a collection of Boolean spatial features, Super-Colocation Pattern Discovery identifies subsets of features that are not only frequently located together but also have dense interactions.For example, the presence of multiple immune cells around cancer cells is more interesting to oncologists than a simple colocation between immune and cancer cells.This problem is important due to its societal applications, including oncology, transportation, and economic analysis.The problem is challenging due to the need to model interaction density among a subset of Boolean spatial features.Related work on colocation pattern mining is limited due to a lack of conceptual, logical, and physical models that accurately represent interaction density.Traditional interest measures (e.g., participation index) largely focus on the mere presence of another spatial feature type and overlook the number or density of neighboring instances.We propose a novel interest measure, termed Super-Colocation Density, which utilizes a matrix or tensor along with a utility-based index to quantify the interaction density among subsets of spatial features.We also introduce novel Super-Colocation Mining algorithms and evaluate the proposed methods through both theoretical analysis and experiments with real and synthetic data.

Given coarser-resolution projections from global climate models or satellite data, the downscaling problem aims to estimate finer-resolution regional climate data, capturing fine-scale spatial patterns and variability. Downscaling is any method to derive high-resolution data from low-resolution variables, often to provide more detailed and local predictions and analyses. This problem is societally crucial for effective adaptation, mitigation, and resilience against significant risks from climate change. The challenge arises from spatial heterogeneity and the need to recover finer-scale features while ensuring model generalization. Most downscaling methods [21] fail to capture the spatial dependencies at finer scales and underperform on real-world climate datasets, such as sea-level rise. We propose a novel Kriging-informed Conditional Diffusion Probabilistic Model (Ki-CDPM) to capture spatial variability while preserving fine-scale features. Experimental results on climate data show that our proposed method is more accurate than state-of-the-art downscaling techniques.

Over the last decades, a rapidly growing volume of spatiotemporal data has been collected from smartphones and GPS, terrestrial, seaborne, airborne, and spaceborne sensors, as well as computational simulations. Meanwhile, advances in deep learning technologies, especially the recent breakthroughs of generative AI and foundation models such as Large Language Models (LLMs) and Large Vision Models (LVMs), have achieved tremendous success in natural language processing and computer vision applications. There is growing anticipation of the same level of accomplishment of AI on spatiotemporal data in tackling grand societal challenges, such as national water resource management, monitoring coastal hazards, energy and food security, as well as mitigation and adaptation to climate change. When deep learning, especially emerging foundation models, intersects spatiotemporal data in scientific domains, it opens up new opportunities and challenges. The workshop aims to bring together academic researchers in both AI and scientific domains, government program managers, leaders from non-profit organizations, as well as industry executives to brainstorm and debate on the emerging opportunities and novel challenges of deep learning (foundation models) for spatiotemporal data inspired by real-world scientific applications.

Given multi-category point sets from different place-types, our goal is to develop a spatially-lucid classifier that can distinguish between two classes based on the arrangements of their points. This problem is important for many applications, such as oncology, for analyzing immune-tumor relationships and designing new immunotherapies. It is challenging due to spatial variability and interpretability needs. Previously proposed techniques require dense training data or have limited ability to handle significant spatial variability within a single place-type. Most importantly, these deep neural network (DNN) approaches are not designed to work in non-Euclidean space, particularly point sets. Existing non-Euclidean DNN methods are limited to one-size-fits-all approaches. We explore a spatial ensemble framework that explicitly uses different training strategies, including weighted-distance learning rate and spatial domain adaptation, on various place-types for spatially-lucid classification. Experimental results on real-world datasets (e.g., MxIF oncology data) show that the proposed framework provides higher prediction accuracy than baseline methods.

Given trajectories with gaps (i.e., missing data), we investigate algorithms to identify abnormal gaps in trajectories which occur when a given moving object did not report its location, but other moving objects in the same geographic region periodically did. The problem is important due to its societal applications, such as improving maritime safety and regulatory enforcement for global security concerns, such as illegal fishing, illegal oil transfers, and trans-shipments. The problem is challenging due to the difficulty of bounding the possible locations of the moving object during a trajectory gap, and the very high computational cost of detecting gaps in such a large volume of location data. The current literature on anomalous trajectory detection assumes linear interpolation within gaps, which may not be able to detect abnormal gaps since objects within a given region may have traveled away from their shortest path. In preliminary work, we introduced an abnormal gap measure that uses a classical space-time prism model to bound an object's possible movement during the trajectory gap and provided a scalable memoized gap detection algorithm (Memo-AGD). In this article, we propose a space time-aware gap detection (STAGD) approach to leverage space-time indexing and merging of trajectory gaps. We also incorporate a dynamic region merge-based (DRM) approach to efficiently compute gap abnormality scores. We provide theoretical proofs that both algorithms are correct and complete and also provide analysis of asymptotic time complexity. Experimental results on synthetic and real-world maritime trajectory data show that the proposed approach substantially improves computation time over the baseline technique.

The eco-toll estimation problem quantifies the expected environmental cost (e.g., energy consumption, exhaust emissions) for a vehicle to travel along a path. This problem is important for societal applications such as eco-routing, which aims to find paths with the lowest exhaust emissions or energy need. The challenges of this problem are threefold: (1) the dependence of a vehicle's eco-toll on its physical parameters; (2) the lack of access to data with eco-toll information; and (3) the influence of contextual information (i.e. the connections of adjacent segments in the path) on the eco-toll of road segments. Prior work on eco-toll estimation has mostly relied on pure data-driven approaches and has high estimation errors given the limited training data. To address these limitations, we propose a novel Eco-toll estimation Physics-informed Neural Network framework (Eco-PiNN) using three novel ideas, namely, (1) a physics-informed decoder that integrates the physical laws governing vehicle dynamics into the network, (2) an attention-based contextual information encoder, and (3) a physics-informed regularization to reduce overfitting. Experiments on real-world heavy-duty truck data show that the proposed method can greatly improve the accuracy of eco-toll estimation compared with state-of-the-art methods. *The full version of the paper can be accessed at https://arxiv.org/abs/2301.05739

Society must achieve net zero carbon emissions to mitigate anthropogenic climate change and preserve a livable planet. Reducing transportation emissions is an important component to achieve net zero because such emissions account for a quarter of global carbon released into the environment. Driven by increasingly available transportation big data and enhanced computational speed, data mining techniques have become powerful tools to achieve transportation decarbonization. This paper describes existing gaps in transportation decarbonization research where data mining can help address problems related to medium and heavy vehicle electrification, electric micromobility safety, and analysis of alternative fuel-powered and plug-in hybrid electric vehicles. Our recommendations encompass open research problems, opportunities for data mining applications, and examples of areas where advancements in data mining techniques are needed. We encourage the data mining community to explore these challenges and opportunities to help achieve net zero emissions goals.

With the advancement of GPS and remote sensing technologies and the pervasiveness of smartphones and IoT devices, an enormous amount of spatiotemporal data are being collected from various domains. Knowledge discovery from spatiotemporal data is crucial in addressing many grand societal challenges, ranging from flood disaster management to monitoring coastal hazards, and from autonomous driving to disease forecasting. The recent success in deep learning technologies in computer vision and natural language processing provides new opportunities for spatiotemporal data mining, but existing deep learning techniques also face unique spatiotemporal challenges (e.g., autocorrelation, non-stationarity, physics awareness). This workshop provides a premium platform for researchers from both academia and industry to exchange ideas on the opportunities, challenges, and cutting-edge techniques related to deep learning for spatiotemporal data.

The goal of spatially explainable artificial intelligence (AI) classification approach is to build a classifier to distinguish two classes (e.g., responder, non-responder) based on the their spatial arrangements (e.g., spatial interactions between different point categories) given multi-category point data from two classes. This problem is important for generating hypotheses towards discovering new immunotherapies for cancer treatment as well as for other applications in biomedical research and microbial ecology. This problem is challenging due to an exponential number of category subsets which may vary in the strength of their spatial interactions. Most prior efforts on using human selected spatial association measures may not be sufficient for capturing the relevant spatial interactions (e.g., surrounded by) which may be of biological significance. In addition, the related deep neural networks are limited to category pairs and do not explore larger subsets of point categories. To overcome these limitations, we propose a Spatial-interaction Aware Multi-Category deep neural Network (SAMCNet) architecture and contribute novel local reference frame characterization and point pair prioritization layers for spatially explainable classification. Experimental results on multiple cancer datasets (e.g., MxIF) show that the proposed architecture provides higher prediction accuracy over baseline methods. A real-world case study demonstrates that the proposed work discovers patterns that are missed by the existing methods and has the potential to inspire new scientific discoveries.

Given trajectory data with gaps, we investigate methods to identify possible rendezvous regions. The problem has societal applications such as improving maritime safety and regulatory enforcement. The challenges come from two aspects. First, gaps in trajectory data make it difficult to identify regions where moving objects may have rendezvoused for nefarious reasons. Hence, traditional linear or shortest path interpolation methods may not be able to detect such activities, since objects in a rendezvous may have traveled away from their usual routes to meet. Second, user detecting a rendezvous regions involve a large number of gaps and associated trajectories, making the task computationally very expensive. In preliminary work, we proposed a more effective way of handling gaps and provided examples to illustrate potential rendezvous regions. In this article, we are providing detailed experiments with both synthetic and real-world data. Experiments on synthetic data show that the accuracy improved by 50 percent, which is substantial as compared to the baseline approach. In this article, we propose a refined algorithm Temporal Selection Search for finding a potential rendezvous region and finding an optimal temporal range to improve computational efficiency. We also incorporate two novel spatial filters: (i) a Static Ellipse Intersection Filter and (ii) a Dynamic Circle Intersection Spatial Filter. Both the baseline and proposed approaches account for every possible rendezvous pattern. We provide a theoretical evaluation of the algorithms correctness and completeness along with a time complexity analysis. Experimental results on synthetic and real-world maritime trajectory data show that the proposed approach substantially improves the area pruning effectiveness and computation time over the baseline technique. We also performed experiments based on accuracy and precision on synthetic dataset on both proposed and baseline techniques.

With the advancement of GPS and remote sensing technologies and the pervasiveness of smartphones and mobile devices, large amounts of spatiotemporal data are being collected from various domains. Knowledge discovery from spatiotemporal data is crucial in broad societal applications. Examples range from mapping flooded areas on satellite imagery for disaster response to monitoring crop health for food security, from estimating travel time between locations on Google Maps to forecasting hotspots of diseases like Covid-19 in public health. The recent success in deep learning technologies in computer vision and natural language processing provides unique opportunities for spatiotemporal data mining (e.g., automatically extracting spatial contextual features without manual feature engineering) but also faces unique challenges (e.g., spatial autocorrelation, heterogeneity, multiple scales, and resolutions, the existence of domain knowledge and constraints). This workshop provides a premium platform for researchers from both academia and industry to exchange ideas on opportunities, challenges, and cutting-edge techniques of deep learning for spatiotemporal data. We hope to inspire novel ideas and visions through the workshop and facilitate the development of this emerging research area.

Spatial data brings an important dimension to AI’s quest for algorithmic transparency. For example, data driven computer-aided policy-decisions use measures of segregation (e.g., dissimilarity index) or income-inequality (e.g., Gini index), and these measures are affected by space partitioning choice. This may lead policymakers to underestimate the level of inequality or segregation within a region. The problem stems from the fact that many segregation based analyses use aggregated census data but do not report result sensitivity to choice of spatial partitioning (e.g., census block, tract). Beyond the well-known Modifiable Areal Unit Problem, this paper shows (via mathematical proofs as well as case studies with census data and census based synthetic micro-population data) that values of many measures (e.g., Gini index, dissimilarity index) diminish monotonically with increasing spatial-unit size in a hierarchical space partitioning (e.g., block, block-group, tract), however the ranking based on spatially aggregated measures remain sensitive to the scale of spatial partitions (e.g., block, block group). This paper highlights the need for social scientists to report how rankings of inequality are affected by the choice of spatial partitions.

The importance of spatial data science and Geo-AI is growing with the rise of spatial and spatiotemporal big data (e.g., trajectories, remote-sensing images, census and geo-social media) [1-2]. Societal use cases include Agriculture (global crop monitoring, precision agriculture), Location-based services (e.g., navigation, ride-sharing), Public Health (e.g., monitoring disease spread), Environment and Climate (change detection, land-cover classification), Smart Cities (e.g., mapping buildings), etc. [1-2]

Regions of anomalous spatial co-locations (ROASCs) are regions where co-locations between two different features are significantly stronger or weaker than expected. ROASC discovery can provide useful insights for studying unexpected spatial associations at regional scales. The main challenges are that the ROASCs are spatially arbitrary in geographic shape and the distributions of spatial features are unknown a priori. To avoid restrictive assumptions regarding the distribution of data, we propose a distribution-free method for discovering arbitrarily shaped ROASCs. First, we present a multidirectional optimization method to adaptively identify the candidate ROASCs, whose sizes and shapes are fully endogenized. Furthermore, the validity of the candidates is evaluated through significance tests under the null hypothesis that the expected spatial co-locations between two features occur consistently across space. To effectively model the null hypothesis, we develop a bivariate pattern reconstruction method by reconstructing the spatial auto- and cross-correlation structures observed in the data. Synthetic experiments and a case study conducted using Shanghai taxi datasets demonstrate the advantages of our method, in terms of effectiveness, over an available alternative method.

Spatial variability is a prominent feature of various geographic phenomena such as climatic zones, USDA plant hardiness zones, and terrestrial habitat types (e.g., forest, grasslands, wetlands, and deserts). However, current deep learning methods follow a spatial-one-size-fits-all (OSFA) approach to train single deep neural network models that do not account for spatial variability. Quantification of spatial variability can be challenging due to the influence of many geophysical factors. In preliminary work, we proposed a spatial variability aware neural network (SVANN-I, formerly calledSVANN) approach where weights are a function of location but the neural network architecture is location independent. In this work, we explore a more flexible SVANN-E approach where neural network architecture varies across geographic locations. In addition, we provide a taxonomy of SVANN types and a physics inspired interpretation model. Experiments with aerial imagery based wetland mapping show that SVANN-I outperforms OSFA and SVANN-E performs the best of all.

Cluster detection is important and widely used in a variety of applications, including public health, public safety, transportation, and so on. Given a collection of data points, we aim to detect density-connected spatial clusters with varying geometric shapes and densities, under the constraint that the clusters are statistically significant. The problem is challenging, because many societal applications and domain science studies have low tolerance for spurious results, and clusters may have arbitrary shapes and varying densities. As a classical topic in data mining and learning, a myriad of techniques have been developed to detect clusters with both varying shapes and densities (e.g., density-based, hierarchical, spectral, or deep clustering methods). However, the vast majority of these techniques do not consider statistical rigor and are susceptible to detecting spurious clusters formed as a result of natural randomness. On the other hand, scan statistic approaches explicitly control the rate of spurious results, but they typically assume a single “hotspot” of over-density and many rely on further assumptions such as a tessellated input space. To unite the strengths of both lines of work, we propose a statistically robust formulation of a multi-scale DBSCAN, namely Significant DBSCAN+, to identify significant clusters that are density connected. As we will show, incorporation of statistical rigor is a powerful mechanism that allows the new Significant DBSCAN+ to outperform state-of-the-art clustering techniques in various scenarios. We also propose computational enhancements to speed-up the proposed approach. Experiment results show that Significant DBSCAN+ can simultaneously improve the success rate of true cluster detection (e.g., 10–20% increases in absolute F1 scores) and substantially reduce the rate of spurious results (e.g., from thousands/hundreds of spurious detections to none or just a few across 100 datasets), and the acceleration methods can improve the efficiency for both clustered and non-clustered data.

Given a collection of N geo-located point samples of k types, we aim to detect spatial mixture patterns of interest, which are sub-regions of the study area that have significantly high or low mixture of points of different types. Spatial mixture patterns have important applications in many societal domains, including resilience of smart cities and communities, biodiversity, equity, business intelligence, etc. The problem is challenging because ranking and selection of candidate patterns can be highly susceptible to the effect of natural randomness, and real-world data often consists of various mixture patterns. In related work, the multi-nomial scan statistic does not support identification of high or low mixture due to its "directionless" nature and high sensitivity to the composition of mixture patterns in data. While species richness indices in biodiversity research allow specification of directions, the measures are very sensitive to spatial randomness effects. To bridge the gap, we first propose a spatial mixture index to provide robust ranking among candidate patterns. Then, we present a dual-level Monte-Carlo estimation method with a baseline algorithm for spatial mixture pattern detection. Finally, we propose both an exact algorithm and a distribution-inspired sequence-reduction heuristic to accelerate the baseline approach. Experiment results with both synthetic and real-world data show that the proposed approaches can detect mixture patterns with high accuracy, and the acceleration methods can greatly reduce computational cost while maintaining high solution quality.

Building footprints are among the most predominant features in urban areas, and provide valuable information for urban planning, solar energy suitability analysis, etc. We aim to automatically and rapidly identify building footprints by leveraging deep learning techniques and the increased availability of remote sensing datasets at high spatial resolution. The task is computationally challenging due to the use of large training datasets and large number of parameters. In related work, You-Only-Look-Once (YOLO) is a state-of-the-art deep learning framework for object detection. However, YOLO is limited in its capacity to identify small objects that appear in groups, which is the case for building footprints. We propose a LOcally-COnstrained (LOCO) You-Only-Look-Once framework to detect small and densely-distributed building footprints. LOCO is a variant of YOLO. Its layer architecture is determined by the spatial characteristics of building footprints and it uses a constrained regression modeling to improve the robustness of building size predictions. We also present an invariant augmentation based voting scheme to further improve the precision in the prediction phase. Experiments show that LOCO can greatly improve the solution quality of building detection compared to related work.

Big Data have emerged and become the norm in the past decade with its well-known 4V challenges and now adds value (a 5th V) for scientific research and the development of new applications. Such Big...

Given a path in a spatial or temporal framework, we aim to find all contiguous subpaths that are both interesting (e.g., abrupt changes) and statistically significant (i.e., persistent trends rather than local fluctuations). Discovering interesting subpaths can provide meaningful information for a variety of domains including Earth science, environmental science, urban planning, and the like. Existing methods are limited to detecting individual points of interest along an input path but cannot find interesting subpaths. Our preliminary work provided a Subpath Enumeration and Pruning (SEP) algorithm to detect interesting subpaths of arbitrary length. However, SEP is not effective in avoiding detections that are random variations rather than meaningful trends, which hampers clear and proper interpretations of the results. In this article, we extend our previous work by proposing a significance testing framework to eliminate these random variations. To compute the statistical significance, we first show a baseline Monte-Carlo method based on our previous work and then propose a Dynamic Search-and-Prune (D-SAP) algorithm to improve its computational efficiency. Our experiments show that the significance testing can greatly suppress the noisy detections in the output and D-SAP can greatly reduce the execution time.

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.

Tree management is becoming a big issue in a variety of societal domains. In recent years, historic wildfires and blackouts caused by failures in tree management have increased in both quantity and severity, resulting in many deaths and financial loses in the tens of billions of dollars. Many communities are also suffering from massive tree loss (e.g., in the millions) that affects the health and well-being of citizens. These problems are likely to worsen due to climate change, aging infrastructure and population growth. Tree management needs a revolution to deal with these urgent problems. This opens up new challenges and opportunities for the spatial community. This paper presents some of the open research problems from the perspectives of individual tree mapping and characterization as well as decision making and in-field intervention.

Hotspot detection aims to find sub-regions of a space that have higher probability density of generating certain events (e.g., disease, crimes) than the other regions. Finding hotspots has important applications in many domains including public health, crime analysis, transportation, etc. Existing methods of hotspot detection rely on test statistics (e.g., likelihood ratio, density) that do not consider spatial nondeterminism, leading to false and missing detections. We provide theoretical insights into the limitations of related work, and propose a new framework, namely, Nondeterministic Normalization based scan statistic (NN-scan), to address the issues. We also propose a DynamIc Linear Approximation (DILA) algorithm to improve NN-scan's efficiency. In experiments, we show that NN-scan can significantly improve the precision and recall of hotspot detection and DILA can greatly reduce the computational cost.

The trajectory-aware lowest-cost path selection problem aims to find the lowest-cost path using trajectory data. Trajectory data is valuable since it carries information about travel cost along paths, and also reflects travelers' routing preference. Path-centric travel cost estimation models using trajectory data grows popular recently, which considers the auto-correlation of the energy consumption on different segments of a path. However, path-centric models are more computationally expensive than edge-centric models. The main challenge of this problem is that the travel cost of every candidate path explored during the process of searching for the lowest-cost path need to be estimated, resulting in high computational cost. The current path selection algorithms that use path-centric cost estimation models still follow the pattern of "path + edge" when exploring candidate paths, which may result in redundant computation. We introduce a trajectory-aware graph model in which each node is a maximal trajectory-aware path. Two nodes in the trajectory-aware graph are linked by an edge if their union forms a trajectory-union path. We then propose a path selection algorithm to find a path in the proposed trajectory-aware graph which corresponds to the lowest-cost path in the input spatial network. We prove theoretically the proposed algorithm is correct and complete. Moreover, we prove theoretically that the proposed path selection algorithm cost much less computational time than the algorithm used in the related work, and validate it through experiments using real-world trajectory data.

Given a collection of geo-distributed points, we aim to detect statistically significant clusters of varying shapes and densities. Spatial clustering has been widely used many important societal applications, including public health and safety, transportation, environment, etc. The problem is challenging because many application domains have low-tolerance to false positives (e.g., falsely claiming a crime cluster in a community can have serious negative impacts on the residents) and clusters often have irregular shapes. In related work, the spatial scan statistic is a popular technique that can detect significant clusters but it requires clusters to have certain predefined shapes (e.g., circles, rings). In contrast, density-based methods (e.g., DBSCAN) can find clusters of arbitrary shape efficiently but do not consider statistical significance, making them susceptible to spurious patterns. To address these limitations, we first propose a modeling of statistical significance in DBSCAN based clustering. Then, we propose a baseline Monte Carlo method to estimate the significance of clusters and a Dual-Convergence algorithm to accelerate the computation. Experiment results show that significant DBSCAN is very effective in removing chance patterns and the Dual-Convergence algorithm can greatly reduce execution time.

Class ambiguity refers to the phenomenon whereby similar features correspond to different classes at different locations. Given heterogeneous geographic data with class ambiguity, the spatial ensemble learning (SEL) problem aims to find a decomposition of the geographic area into disjoint zones such that class ambiguity is minimized and a local classifier can be learned in each zone. The problem is important for applications such as land cover mapping from heterogeneous earth observation data with spectral confusion. However, the problem is challenging due to its high computational cost. Related work in ensemble learning either assumes an identical sample distribution (e.g., bagging, boosting, random forest) or decomposes multi-modular input data in the feature vector space (e.g., mixture of experts, multimodal ensemble) and thus cannot effectively minimize class ambiguity. In contrast, we propose a spatial ensemble framework that explicitly partitions input data in geographic space. Our approach first preprocesses data into homogeneous spatial patches and uses a greedy heuristic to allocate pairs of patches with high class ambiguity into different zones. We further extend our spatial ensemble learning framework with spatial dependency between nearby zones based on the spatial autocorrelation effect. Both theoretical analysis and experimental evaluations on two real world wetland mapping datasets show the feasibility of the proposed approach.

Given a spatial road network, an origin, a destination, and trajectory data of vehicles on the network, the Energy-efficient Path Selection (EPS) problem aims to find the most energy-efficient path (i.e., with least energy consumption) between the origin and the destination. With world energy consumption growing rapidly, estimating and reducing the energy consumption of road transportation is becoming critical. The main challenge of this problem is to adopt energy consumption as the cost metric of paths, which is neglected by the related work in shortest path selection problem whose typical metrics are distance and time. Additionally, negative energy consumption caused by the use of regenerative braking on electrified vehicles prevents classical algorithms like Dijkstra's algorithm from functioning correctly. We introduce a Physics-guided Energy Consumption (PEC) model based on a low-order physics model, which estimates energy consumption as a function of the vehicle parameters (e.g., mass and powertrain system efficiency) and use the estimation in the proposed adaptive dynamic programming algorithm for path selection. Our PEC model treats energy consumption as a unique metric that is determined not only by the path and vehicle's motion along the path, but also on properties of the vehicle itself. Experiments show that the PEC model estimates are more similar to real trajectory data than the estimates represented by the mean or histogram of historical data. Also, the path found by the proposed method is more energy-efficient than both the currently used path and the fastest path found by a commercial routing package. As far as we know, this is the first paper to use a physics-guided method to estimate the vehicle energy consumption and perform path selection.

Given remote sensing datasets in a spatial domain, we aim to detect geospatial objects with minimum bounding rectangles (i.e., angle-aware) leveraging deep learning frameworks. Geospatial objects (e.g., buildings, vehicles, farms) provide meaningful information for a variety of societal applications, including urban planning, census, sustainable development, security surveillance, agricultural management, etc. The detection of these objects are challenging because their directions are often heavily mixed and not parallel to the orthogonal directions of an image frame due to topography, planning, etc. In addition, there is very limited training data with angle information for most types of objects. In related work, state-of-the-art deep learning frameworks detect objects using orthogonal bounding rectangles (i.e., sides are parallel to the sides of an input image), so they cannot identify the directions of objects and generate loose rectangular bounds on objects. We propose an Unsupervised Augmentation (UA) framework to detect geospatial objects with general minimum bounding rectangles (i.e., with angles). The UA framework contains two schemes, namely a ROtation-Vector (ROV) based scheme and a context-based scheme. The schemes completely avoid the need for: (1) additional ground-truth data with annotated angles; (2) restructuring of existing network architectures; and (3) re-training. Experimental results show that the UA framework can well approximate the angles of objects and generate much tighter bounding boxes on objects.

Tree inventories are important datasets for many societal applications (e.g., urban planning). However, tree inventories still remain unavailable in most urban areas. We aim to automate tree identification at individual levels in urban areas at a large scale using remote sensing datasets. The problem is challenging due to the complexity of the landscape in urban scenarios and the lack of ground truth data. In related work, tree identification algorithms have mainly focused on controlled forest regions where the landscape is mostly homogeneous with trees, making the methods difficult to generalize to urban environments. We propose a TIMBER framework to find individual trees in complex urban environments and a Core Object REduction (CORE) algorithm to improve the computational efficiency of TIMBER. Experiments show that TIMBER can efficiently detect urban trees with high accuracy.

Given a set of GPS trajectories, avoidance region discovery (ARD) finds regions that are avoided by drivers. ARD is important for applications such as sociology, city/transportation planning and crime mitigation, where it can help domain users understand the driver behavior under different concerns (e.g. rush hour, congestion, dangerous neighborhood, etc.). ARD is challenging because of the large number of trajectories with thousands of GPS points, large number of candidate avoidance regions, and the cost of evaluating those. Related work is focused on finding evasive trajectories for a given set of avoidance regions. Distinct from the related work, we propose an Avoidance Region Miner (ARM) approach that can detect both the avoidance regions and evasive trajectories just by using the trajectories in hand without the need of an additional input. A case study on real trajectory data confirms that ARM discovers such regions for further investigation by domain users. Experiments show that ARM yields substantial computational savings compared to a baseline approach.

Class ambiguity refers to the phenomenon whereby samples with similar features belong to different classes at different locations. Given heterogeneous geographic data with class ambiguity, the spatial ensemble learning (SEL) problem aims to find a decomposition of the geographic area into disjoint zones such that class ambiguity is minimized and a local classifier can be learned in each zone. SEL problem is important for applications such as land cover mapping from heterogeneous earth observation data with spectral confusion. However, the problem is challenging due to its high computational cost (finding an optimal zone partition is NP-hard). Related work in ensemble learning either assumes an identical sample distribution (e.g., bagging, boosting, random forest) or decomposes multi-modular input data in the feature vector space (e.g., mixture of experts, multimodal ensemble), and thus cannot effectively minimize class ambiguity. In contrast, our spatial ensemble framework explicitly partitions input data in geographic space. Our approach first preprocesses data into homogeneous spatial patches and uses a greedy heuristic to allocate pairs of patches with high class ambiguity into different zones. Both theoretical analysis and experimental evaluations on two real world wetland mapping datasets show the feasibility of the proposed approach.

Data science models, although successful in a number of commercial domains, have had limited applicability in scientific problems involving complex physical phenomena. Theory-guided data science (TGDS) is an emerging paradigm that aims to leverage the wealth of scientific knowledge for improving the effectiveness of data science models in enabling scientific discovery. The overarching vision of TGDS is to introduce scientific consistency as an essential component for learning generalizable models. Further, by producing scientifically interpretable models, TGDS aims to advance our scientific understanding by discovering novel domain insights. Indeed, the paradigm of TGDS has started to gain prominence in a number of scientific disciplines such as turbulence modeling, material discovery, quantum chemistry, bio-medical science, bio-marker discovery, climate science, and hydrology. In this paper, we formally conceptualize the paradigm of TGDS and present a taxonomy of research themes in TGDS. We describe several approaches for integrating domain knowledge in different research themes using illustrative examples from different disciplines. We also highlight some of the promising avenues of novel research for realizing the full potential of theory-guided data science.

Meteorological parameters are often considered as crucial factors for climatological pattern analysis. Predictions of these parameters have been studied extensively in the field of remote sensing and GIS. It is one of the most critical steps involved in most of the meteorological data mining process. Spatial interpolation is an efficient technique to yield minimal error in prediction. From existing literatures, it is evident that the land-use/land-cover (LULC) distribution of the terrain influences these parameters in a varying manner and it is important to model their behaviour for climatological analyses. However, this semantic LULC knowledge of the terrain is generally ignored in the prediction process of the meteorological parameters. Recently, we have proposed a new spatial interpolation technique, namely semantic kriging (SemK) [3,5,7], which considers the semantic LULC knowledge for land-atmospheric interaction modeling and incorporates it into the existing interpolation process for better accuracy. However, the a-priori correlation analysis of SemK ignores the effect of other nearby LULC classes on each other. This article presents a new variant of SemK, namely a-posterior probabilistic Bayesian SemK (BSemK), which extends the a-priori correlation analysis of SemK with a-posterior probabilistic analysis. The proposed approach provides more accurate estimation of the parameters. Experimentation with LST data advocates the efficacy of the proposed approach compared to the a-priori SemK and other existing interpolation techniques.

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.

Given a set of activity points (e.g., crime, disease locations), Ring-Shaped Hotspot Detection (RHD) finds ring-shaped areas where the concentration of activities inside is significantly higher than that outside. RHD is societally important for applications such as environmental criminology, epidemiology, and biology to investigate evasive patterns. RHD is computationally challenging because of the large number of candidate rings, non-monotonic interest measure, and cost of the statistical significance test. Previous approaches (e.g., spatial scan statistics tools) focus on simply-connected shaped areas (e.g., circles, rectangles) and can not detect statistically significant rings. In this paper, a novel algorithm, DGPLMR, is proposed to discover statistically significant ring-shaped hotspots based on the ideas of dual grid based pruning and best enclosing ring refining. Theoretical evaluation proves that the proposed approach is a correct approach (i.e., all outputs satisfy input thresholds) to detect ring-shaped hotspots. Case study on real disease data shows that the proposed approach finds ring-shaped hotspots which were not detected by the existing techniques. Cost analysis and experimental results on synthetic data show that the proposed approach with algorithmic refinements yields substantial computational savings.

Modern vehicles are increasingly being equipped with rich instrumentation that enables them to collect location aware data on a wide variety of travel related phenomena such as the real-world performance of engines and powertrain, driver preferences, context of the vehicle with respect to others nearby, and--indirectly--traffic on the transportation network itself. Combined with their increased access to the Internet, these connected vehicles are opening up vast opportunities to improve the safety, environmental friendliness, and the overall experience of urban travel. However, significant spatial computing challenges need to be addressed before we can realize the full potential of connected vehicles. This paper presents some of the open research questions under this theme from the perspectives of query processing, data science and data engineering.

Given a spatio-temporal network, a source, a destination, and a desired departure time interval, the All-departure-time Lagrangian Shortest Paths (ALSP) problem determines a set which includes the shortest path for every departure time in the given interval. ALSP is important for critical societal applications such as eco-routing. However, ALSP is computationally challenging due to the non-stationary ranking of the candidate paths across distinct departure-times. Current related work for reducing the redundant work, across consecutive departure-times sharing a common solution, exploits only partial information e.g., the earliest feasible arrival time of a path. In contrast, our approach uses all available information, e.g., the entire time series of arrival times for all departure-times. This allows elimination of all knowable redundant computation based on complete information available at hand. We operationalize this idea through the concept of critical-time-points (CTP), i.e., departure-times before which ranking among candidate paths cannot change. In our preliminary work, we proposed a CTP based forward search strategy. In this paper, we propose a CTP based temporal bi-directional search for the ALSP problem via a novel impromptu rendezvous termination condition. Theoretical and experimental analysis show that the proposed approach outperforms the related work approaches particularly when there are few critical-time-points.

Given learning samples from a raster data set, spatial decision tree learning aims to find a decision tree classifier that minimizes classification errors as well as salt-and-pepper noise. The problem has important societal applications such as land cover classification for natural resource management. However, the problem is challenging due to the fact that learning samples show spatial autocorrelation in class labels, instead of being independently identically distributed. Related work relies on local tests (i.e., testing feature information of a location) and cannot adequately model the spatial autocorrelation effect, resulting in salt-and-pepper noise. In contrast, we recently proposed a focal-test-based spatial decision tree (FTSDT), in which the tree traversal direction of a sample is based on both local and focal (neighborhood) information. Preliminary results showed that FTSDT reduces classification errors and salt-and-pepper noise. This paper extends our recent work by introducing a new focal test approach with adaptive neighborhoods that avoids over-smoothing in wedge-shaped areas. We also conduct computational refinement on the FTSDT training algorithm by reusing focal values across candidate thresholds. Theoretical analysis shows that the refined training algorithm is correct and more scalable. Experiment results on real world data sets show that new FTSDT with adaptive neighborhoods improves classification accuracy, and that our computational refinement significantly reduces training time.

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 spatio-temporal network (STN) and a set of STN operations, the goal of the Storing Spatio-Temporal Networks (SSTN) problem is to produce an efficient method of storing STN data that minimizes disk I/O costs for given STN 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. Our preliminary work proposed a non-orthogonal partitioning approach in which we optimized the LGetOneSuccessor() operation that retrieves a single successor for a given node on STN. In this paper, we provide a method to optimize the LGetAllSuccessors() operation, which retrieves all successors for a given node on a STN. This new approach uses the concept of a Lagrangian Family Set (LFS) to model data access patterns for STN queries. Experimental results using real-world road and flight traffic datasets demonstrate that the proposed approach outperforms prior work for LGetAllSuccessors() computation workloads.

Given a raster spatial framework, as well as training and test sets, the spatial decision tree learning (SDTL) problem aims to minimize classification errors as well as salt-and-pepper noise. The SDTL problem is important due to many societal applications such as land cover classification in remote sensing. However, the SDTL problem is challenging due to the spatial autocorrelation of class labels, and the potentially exponential number of candidate trees. Related work is limited due to the use of local-test-based decision nodes, which can not adequately model spatial autocorrelation during test phase, leading to high salt-and-pepper noise. In contrast, we propose a focal-test-based spatial decision tree (FTSDT) model, where the tree traversal direction for a location is based on not only local but also focal (i.e., neighborhood) properties of the location. Experimental results on real world remote sensing datasets show that the proposed approach reduces salt-and-pepper noise and improves classification accuracy.

No abstract available.

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.

Given learning samples from a spatial raster dataset, the geographical classification problem aims to learn a decision tree classifier that minimizes classification errors as well as salt-n-pepper noise. The problem is important in many applications, such as land cover classification in remote sensing and lesion classification in medical diagnosis. However, the problem is challenging due to spatial autocorrelation. Existing decision tree learning algorithms, i.e. ID3, C4.5, CART, produce a lot of salt-n-pepper noise in classification results, due to their assumption that data items are drawn independently from identical distributions. In contrast, we propose a spatial decision tree learning algorithm, which incorporates spatial autocorrelation effect by a new spatial information gain (SIG) measure. The proposed approach is evaluated in a case study on a remote sensing dataset from Chanhassen, MN. Case study results show that the proposed approach outperforms the traditional approach in not only reducing salt-n-pepper noise but also improving classification accuracy.

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.

Given a collection of Boolean spatiotemporal (ST) event-types, the cascading spatiotemporal pattern (CSTP) discovery process finds partially ordered subsets of these event-types whose instances are located together and occur serially. For example, analysis of crime data sets may reveal frequent occurrence of misdemeanors and drunk driving after and near bar closings on weekends, as well as after and near large gatherings such as football games. Discovering CSTPs from ST data sets is important for application domains such as public safety (e.g., identifying crime attractors and generators) and natural disaster planning, (e.g., preparing for hurricanes). However, CSTP discovery presents multiple challenges; three important ones are 1) the exponential cardinality of candidate patterns with respect to the number of event types, 2) computationally complex ST neighborhood enumeration required to evaluate the interest measure and 3) the difficulty of balancing computational complexity and statistical interpretation. Current approaches for ST data mining focus on mining totally ordered sequences or unordered subsets. In contrast, our recent work explores partially ordered patterns. Recently, we represented CSTPs as directed acyclic graphs (DAGs); proposed a new interest measure, the cascade participation index (CPI); outlined the general structure of a cascading spatiotemporal pattern miner (CSTPM); evaluated filtering strategies to enhance computational savings using a real-world crime data set and proposed a nested loop-based CSTPM to address the challenge posed by exponential cardinality of candidate patterns. This paper adds to our recent work by offering a new computational insight, namely, that the computational bottleneck for CSTP discovery lies in the interest measure evaluation. With this insight, we propose a new CSTPM based on spatiotemporal partitioning that significantly lowers the cost of interest measure evaluation. Analytical evaluation shows that our new CSTPM is correct and complete. Results from significant amount of new experimental evaluation with both synthetic and real data show that our new ST partitioning-based CSTPM outperforms the CSTPM from our previous work. We also present a case study that verifies the applicability of CSTP discovery process.

Regional co-location patterns (RCPs) represent collections of feature types frequently located together in certain localities. For example, RCP < (Bar, Alcohol -- Crimes), Downtown >suggests that a co-location pattern involving alcohol-related crimes and bars is often localized to downtown regions. Given a set of Boolean feature types, their geo-located instances, a spatial neighbor relation, and a prevalence threshold, the RCP discovery problem finds all prevalent RCPs (pairs of co-locations and their prevalence localities). RCP discovery is important in many societal applications, including public safety, public health, climate science and ecology. The RCP discovery problem involves three major challenges: (a) an exponential number of subsets of feature types, (b) an exponential number of candidate localities and (c) a tradeoff between accurately modeling pattern locality and achieving computational efficiency. Related work does not provide computationally efficient methods to discover all interesting RCPs with their natural prevalence localities. To address these limitations, this paper proposes a neighborhood graph based approach that discovers all interesting RCPs and is aware of a pattern's prevalence localities. We identify partitions based on the pattern instances and neighbor graph. We introduce two new interest measures, a regional participation ratio and a regional participation index to quantify the strength of RCPs. We present two new algorithms, Pattern Space (PS) enumeration and Maximal Locality (ML) enumeration and show that they are correct and complete. Experiments using real crime datasets show that ML pruning outperforms PS enumeration.

Given a spatiotemporal (ST) dataset and a path in its embedding spatiotemporal framework, the goal is to to identify all interesting sub-paths defined by an interest measure. Sub-path discovery is of fundamental importance for understanding climate changes, agriculture, and many other application. However, this problem is computationally challenging due to the massive volume of data, the varying length of sub-paths and non-monotonicity of interestingness throughout a sub-path. Previous approaches find interesting unit sub-paths (e.g., unit time interval) or interesting points. By contrast, we propose a Sub-path Enumeration and Pruning (SEP) approach that finds collections of long interesting sub-paths. Two case studies using climate change datasets show that SEP can find long interesting sub-paths which represent abrupt climate change. We provide theoretical analyses of correctness, completeness and computational complexity of the proposed approach. We also provide experimental evaluation of two traversal strategies for enumerating and pruning candidate sub-paths.

Given a set of operators and a spatio-temporal network, the goal of the Storing Spatio-Temporal Networks (SSTN) problem is to produce an efficient data storage method that minimizes disk I/O access costs. Storing and accessing spatio-temporal networks is increasingly important in many societal applications such as transportation management and emergency planning. This problem is challenging due to strains on traditional adjacency list representations when storing temporal attribute values from the sizable increase in length of the time-series. Current approaches for the SSTN problem focus on orthogonal partitioning (e.g., snapshot, longitudinal, etc.), which may produce excessive I/O costs when performing traversal-based spatio-temporal network queries (e.g., route evaluation, arrival time prediction, etc) due to the desired nodes not being allocated to a common page. We propose a Lagrangian-Connectivity Partitioning (LCP) technique to efficiently store and access spatio-temporal networks that utilizes the interaction between nodes and edges in a network. Experimental evaluation using the Minneapolis, MN road network showed that LCP outperforms traditional orthogonal approaches.

Summary form only given. The recent advances and price reduction of technologies for collecting spatial and spatio-temporal data like Satellite Images, Cellular Phones, Sensor Networks, and GPS devices has facilitated the collection of data referenced in space and time. These huge collections of data often hide interesting information which conventional systems and classical data mining techniques are unable to discover. Spatial and spatio-temporal data are embedded in continuous space, whereas classical datasets (e.g. transactions) are often discrete. Spatial and spatio-temporal data require complex data preprocessing, transformation, data mining, and post-processing techniques to extract novel, useful, and understandable patterns. The importance of spatial and spatio-temporal data mining is growing with the increasing incidence and importance of large geo-spatial datasets such as maps, repositories of remote-sensing images, trajectories of moving objects generated by mobile devices, etc. Applications include Mobile-commerce industry (location-based services), climatologically effects of El Nino, land-use classification and global change using satellite imagery, finding crime hot spots, local instability in traffic, migration of birds, fishing control, pedestrian behavior analysis, and so on. Thus, new methods are needed to analyze spatial and spatio-temporal data to extract interesting, useful, and non-trivial patterns. The main goal of this tutorial is to disseminate this research field, giving an overview of the current state of the art and the main methodologies and algorithms for spatial and spatio-temporal data mining. This tutorial is directed to researches and practitioners, experts in data mining, analysts of spatial and spatio-temporal data, as well as knowledge engineers and domain experts from different application areas.

Given a collection of Boolean spatio-temporal(ST) event types, the cascading spatio-temporal pattern (CSTP) discovery process finds partially ordered subsets of event-types whose instances are located together and occur in stages. For example, analysis of crime datasets may reveal frequent occurrence of misdemeanors and drunk driving after bar closings on weekends and after large gatherings such as football games. Discovering CSTPs from ST datasets is important for application domains such as public safety (e.g. crime attractors and generators) and natural disaster planning(e.g. hurricanes). However, CSTP discovery is challenging for several reasons, including both the lack of computationally efficient, statistically meaningful metrics to quantify interestingness, and the large cardinality of candidate pattern sets that are exponential in the number of event types. Existing literature for ST data mining focuses on mining totally ordered sequences or unordered subsets. In contrast, this paper models CSTPs as partially ordered subsets of Boolean ST event types. We propose a new CSTP interest measure (the Cascade Participation Index) that is computationally cheap(O(n2)vs. exponential, where n is the dataset size) as well as statistically meaningful. We propose a novel algorithm exploiting the ST nature of datasets and evaluate filtering strategies to quickly prune uninteresting candidates. We present a case study to find CSTPs from real crime reports and provide a statistical explanation. Experimental results indicate that the proposed multiresolution spatio-temporal(MST) filtering strategy leads to significant savings in computational costs.

This paper presents a novel algorithm for Incremental and General Evaluation of continuous Reverse Nearest neighbor queries (IGERN, for short). The IGERN algorithm is general in that it is applicable for both continuous monochromatic and bichromatic reverse nearest neighbor queries. This problem is faced in a number of applications such as enhanced 911 services and in army strategic planning. A main challenge in these problems is to maintain the most up-to-date query answers as the data set frequently changes over time. Previous algorithms for monochromatic continuous reverse nearest neighbor queries rely mainly on monitoring at the worst case of six pie regions, whereas IGERN takes a radical approach by monitoring only a single region around the query object. The IGERN algorithm clearly outperforms the state-of-the-art algorithms in monochromatic queries. We also propose a new optimization for the monochromatic IGERN to reduce the number of nearest neighbor searches. Furthermore, a filter and refine approach for IGERN (FR-IGERN) is proposed for the continuous evaluation of bichromatic reverse nearest neighbor queries which is an optimized version of our previous approach. The computational complexity of IGERN and FR-IGERN is presented in comparison to the state-of-the-art algorithms in the monochromatic and bichromatic cases. In addition, the correctness of IGERN and FR-IGERN in both the monochromatic and bichromatic cases, respectively, are proved. Extensive experimental analysis using synthetic and real data sets shows that IGERN and FR-IGERN is efficient, is scalable, and outperforms previous techniques for continuous reverse nearest neighbor queries.

This paper presents a study of Multi-type Nearest Neighbor (MTNN) Queries in road networks with time window constraints. Specifically, we provide a label correcting algorithm, which is based on a time aggregated multi-type graph. This algorithm gives the best start time, a turn-by-turn route, and the shortest path in terms of least travel time for a given MTNN query.

Given a time stamped transaction database and a user-defined reference sequence of interest over time, similarity-profiled temporal association mining discovers all associated item sets whose prevalence variations over time are similar to the reference sequence. The similar temporal association patterns can reveal interesting relationships of data items which co-occur with a particular event over time. Most works in temporal association mining have focused on capturing special temporal regulation patterns such as cyclic patterns and calendar scheme-based patterns. However, our model is flexible in representing interesting temporal patterns using a user-defined reference sequence. The dissimilarity degree of the sequence of support values of an item set to the reference sequence is used to capture how well its temporal prevalence variation matches the reference pattern. By exploiting interesting properties such as an envelope of support time sequence and a lower bounding distance for early pruning candidate item sets, we develop an algorithm for effectively mining similarity-profiled temporal association patterns. We prove the algorithm is correct and complete in the mining results and provide the computational analysis. Experimental results on real data as well as synthetic data show that the proposed algorithm is more efficient than a sequential method using a traditional support-pruning scheme.

Given a spatial crime data warehouse, that is updated infrequently and a set of operations O as well as constraints of storage and update overheads, the index type selection problem is to find a set of index types that can reduce the I/O cost of the set of operations. The index type selection problem is important to improve user experience and system resource utilization in crucial spatial statistics application domains such as mapping and analysis for public safety, public health, ecology, and transportation. This is because the response time of frequent queries based on the set of operations can be improved significantly by an effective choice of index types. Many spatial statistical queries in these application domains make use of a spatial neighborhood matrix, known as W in spatial statistics, which can be thought of as a spatial self-join in spatial database terminology. Currently supported index types such as B-Tree and R-Tree families do not adequately support spatial statistical analysis because they require on-the-fly computation of the WMatrix, slowing down spatial statistical analysis. In contrast, this paper argues that Spatial Database Management Systems (SDBMS) should support a join index to materialize the WMatrix and eliminate on-the-fly computation of the common selfjoin. A detailed case study using the popular spatial statistical software package for public safety, namely CrimeStat, shows that join indices can significantly speed up spatial analysis such as calculation of Ripley's K and identification of hotspots.

The alignment of separate ontologies by matching related concepts continues to attract great attention within the database and artificial intelligence communities, especially since semantic heterogeneity across data sources remains a widespread and relevant problem. In particular, the Geographic Information System (GIS) domain presents unique forms of semantic heterogeneity that require a variety of matching approaches.

Intelligent image information mining for thematic pattern extraction is a complex task. Ever increasing spatial, spectral, and temporal resolution poses several challenges to the geographic knowledge discovery community. Although the improvements in sensor technology and data collection methods may lead to improved geoinformation generation, it also places several constraints on data mining techniques. Moreover thematic classes are spectrally overlapping, that is, many thematic classes can not be separated by spectral features alone. In recent years we have developed several innovative machine learning approaches to address these problems. The resulting software system, called *Miner, was tested on several real world multisource spatiotemporal datasets. Experimental evaluation showed improved accuracy over conventional data mining approaches. In addition, we integrated *Miner with another popular open source machine learning system called Weka. In this demo we show the utility of *Miner for thematic information extraction from multisource spatiotemporal data (remote sensing images and ancillary geospatial databases).

Given a percentage-threshold and readings from a pair of consecutive upstream and downstream sensors, flow anomaly discovery identifies dominant time intervals where the fraction of time instants of significantly mis-matched sensor readings exceed the given percentage-threshold. Discovering flow anomalies (FA) is an important problem in environmental flow monitoring networks and early warning detection systems for water quality problems. However, mining FAs is computationally expensive because of the large (potentially infinite) number of time instants of measurement and potentially long delays due to stagnant (e.g. lakes) or slow moving (e.g. wetland) water bodies between consecutive sensors. Traditional outlier detection methods (e.g. t-test) are suited for detecting transient FAs (i.e., time instants of significant mis-matches across consecutive sensors) and cannot detect persistent FAs (i.e., long variable time-windows with a high fraction of time instant transient FAs) due to a lack of a pre-defined window size. In contrast, we propose a Smart Window Enumeration and Evaluation of persistence-Thresholds (SWEET) method to efficiently explore the search space of all possible window lengths. Computation overhead is brought down significantly by restricting the start and end points of a window to coincide with transient FAs, using a smart counter and efficient pruning techniques. Experimental evaluation using a real dataset shows our proposed approach outperforms Nainodotve alternatives.

Mixed-drove spatio-temporal co-occurrence patterns (MDCOPs) represent subsets of two or more different object-types whose instances are often located in spatial and temporal proximity. Discovering MDCOPs is an important problem with many applications such as identifying tactics in battlefields, games, and predator-prey interactions. However, mining MDCOPs is computationally very expensive because the interest measures are computationally complex, datasets are larger due to the archival history, and the set of candidate patterns is exponential in the number of object-types. We propose a monotonic composite interest measure for discovering MDCOPs and novel MDCOP mining algorithms. Analytical results show that the proposed algorithms are correct and complete. Experimental results also show that the proposed methods are computationally more efficient than naive alternatives.

Given a transportation network having source nodes with evacuees and destination nodes, we want to find a contraflow network configuration, i.e., ideal direction for each edge, to minimize evacuation time. Contraflow is considered a potential remedy to reduce congestion during evacuations in the context of homeland security and natural disasters (e.g., hurricanes). This problem is computationally challenging because of the very large search space and the expensive calculation of evacuation time on a given network. To our knowledge, this paper presents the first macroscopic approaches for the solution of contraflow network reconfiguration incorporating road capacity constraints, multiple sources, congestion factor, and scalability. We formally define the contraflow problem based on graph theory and provide a framework of computational workload to classify our approaches. A greedy heuristic is designed to produce high quality solutions with significant performance. A bottleneck relief heuristic is developed to deal with large numbers of evacuees. We evaluate the proposed approaches both analytically and experimentally using real world datasets. Experimental results show that our contraflow approaches can reduce evacuation time by 40% or more.

Given a transportation network, a vulnerable population, and a set of destinations, evacuation route planning identifies routes to minimize the time to evacuate the vulnerable population. Evacuation route planning is a vital components of efforts by civil authorities to prepare for both natural and man-made disasters (e.g., hurricanes, terrorist acts, etc). However, evacuation route planning is computationally challenging due to the size of transportation networks, the large number of evacuees, and capacity constraints. For example, the number of evacuees often far exceeds the bottleneck capacity, i.e., the minimum cut of a given network. Current approaches (e.g., linear programming and Capacity Constrained Route Planner (CCRP), a recently proposed evacuation planning algorithm) do not scale well because of intensive computation needs in order to produce the schedules of evacuees as well as routing plans.

This paper presents a novel algorithm for Incremental and General Evaluation of continuous Reverse Nearest neighbor queries (IGERN, for short). The IGERN algorithm is general as it is applicable for both the monochromatic and bichromatic reverse nearest neighbor queries. The incremental aspect of IGERN is achieved through determining only a small set of objects to be monitored. While previous algorithms for monochromatic queries rely mainly on monitoring six pie regions, IGERN takes a radical approach by monitoring only a single region around the query object. The IGERN algorithm clearly outperforms the state-of-the-art algorithms in monochromatic queries. In addition, the IGERN algorithm presents the first attempt for continuous evaluation of bichromatic reverse nearest neighbor queries. The computational complexity of IGERN is presented in comparison to the state-of-the-art algorithms in the monochromatic case and to the use of Voronoi diagrams for the bichromatic case. In addition, the correctness of IGERN in both the monochromatic and bichromatic cases are proved. Extensive experimental analysis shows that IGERN is efficient, is scalable, and outperforms previous techniques for continuous reverse nearest neighbor queries.

Zonal co-location patterns represent subsets of featuretypes that are frequently located in a subset of space (i.e., zone). Discovering zonal spatial co-location patterns is an important problem with many applications in areas such as ecology, public health, and homeland defense. However, discovering these patterns with dynamic parameters (i.e., repeated specification of zone and interest measure values according to user preferences) is computationally complex due to the repetitive mining process. Also, the set of candidate patterns is exponential in the number of feature types, and spatial datasets are huge. Previous studies have focused on discovering global spatial co-location patterns with a fixed interest measure threshold. In this paper, we propose an indexing structure for co-location patterns and propose algorithms (Zoloc-Miner) to discover zonal colocation patterns efficiently for dynamic parameters. Extensive experimental evaluation shows our proposed approaches are scalable, efficient, and outperform na¨ive alternatives.

The discovery of a person's meaningful places involves obtaining the physical locations and their labels for a person's places that matter to his daily life and routines. This problem is driven by the requirements from emerging location-aware applications, which allow a user to pose queries and obtain information in reference to places, for example, “home”, “work” or “Northwest Health Club”. It is a challenge to map from physical locations to personally meaningful places due to a lack of understanding of what constitutes the real users' personally meaningful places. Previous work has explored algorithms to discover personal places from location data. However, we know of no systematic empirical evaluations of these algorithms, leaving designers of location-aware applications in the dark about their choices. Our work remedies this situation. We extended a clustering algorithm to discover places. We also defined a set of essential evaluation metrics and an interactive evaluation framework. We then conducted a large-scale experiment that collected real users' location data and personally meaningful places, and illustrated the utility of our evaluation framework. Our results establish a baseline that future work can measure itself against. They also demonstrate that that our algorithm discovers places with reasonable accuracy and outperforms the well-known K-Means clustering algorithm for place discovery. Finally, we provide evidence that shapes more complex than “points” are required to represent the full range of people's everyday places.

Given a query point and a collection of spatial features, a multi-type nearest neighbor query finds the shortest tour for the query point in a way such that only one instance of each feature type is visited during the tour. For example, a tourist may be interested in finding the shortest tour which starts at a hotel and passes through a post office, a gas station, and a grocery store. The multi-type nearest query problem is different from the traditional nearest neighbor query problem, since there are many objects for each feature type and the shortest tour should pass through only one object from each feature type. In this paper, we propose R-tree based optimal solutions, which exploit a page-level upper bound for efficient computation. Also, since this problem is a generalized Traveling Salesman Problem (TSP) and is NP-hard, we provide several heuristic methods for the case that there are a large number of feature types in the data. Finally, experimental results are provided to show the strength of the proposed algorithms and design decisions related to performance tuning.

Mixed-drove spatio-temporal co-occurrence patterns (MDCOPs) represent subsets of object-types that are located together in space and time. Discovering MDCOPs is an important problem with many applications such as identifying tactics in battlefields, games, and predator-prey interactions. However, mining MDCOPs is computationally very expensive because the interest measures are computationally complex, datasets are larger due to the archival history, and the set of candidate patterns is exponential in the number of object-types. We propose a monotonic composite interest measure for discovering MDCOPs and a novel MDCOP mining algorithm. Analytical and experimental results show that the proposed algorithm is correct and complete. Results also show the proposed method is computationally more efficient than naïve alternatives.

A spatial co-located event set represents a subset of spatial events whose instances are located in a spatial neighborhood. The discovery of co-evolving spatial event sets involves finding co-located event sets whose spatial prevalence variations over time are similar to a specific query sequence. Mining co-evolving spatial event sets is computationally challenging due to the high computational cost of finding co-located event instances on continuous geographic space, large temporal space and a composite interest measure, i.e., the spatial prevalence time sequence of a co-located event set. We propose a novel method for mining co-evolving spatial event sets. We analyze the proposed algorithm in terms of correctness and completeness, and experimentally evaluate the algorithm.

Given a user-specified minimum correlation threshold /spl theta/ and a market-basket database with N items and T transactions, an all-strong-pairs correlation query finds all item pairs with correlations above the threshold /spl theta/. However, when the number of items and transactions are large, the computation cost of this query can be very high. The goal of this paper is to provide computationally efficient algorithms to answer the all-strong-pairs correlation query. Indeed, we identify an upper bound of Pearson's correlation coefficient for binary variables. This upper bound is not only much cheaper to compute than Pearson's correlation coefficient, but also exhibits special monotone properties which allow pruning of many item pairs even without computing their upper bounds. A two-step all-strong-pairs correlation query (TAPER) algorithm is proposed to exploit these properties in a filter-and-refine manner. Furthermore, we provide an algebraic cost model which shows that the computation savings from pruning is independent of or improves when the number of items is increased in data sets with Zipf-like or linear rank-support distributions. Experimental results from synthetic and real-world data sets exhibit similar trends and show that the TAPER algorithm can be an order of magnitude faster than brute-force alternatives. Finally, we demonstrate that the algorithmic ideas developed in the TAPER algorithm can be extended to efficiently compute negative correlation and uncentered Pearson's correlation coefficient.

Spatial colocations represent the subsets of features which are frequently located together in geographic space. Colocation pattern discovery presents challenges since spatial objects are embedded in a continuous space, whereas classical data is often discrete. A large fraction of the computation time is devoted to identifying the instances of colocation patterns. We propose a novel joinless approach for efficient colocation pattern mining. The joinless colocation mining algorithm uses an instance-lookup scheme instead of an expensive spatial or an instance join operation for identifying colocation instances. We prove the joinless algorithm is correct and complete in finding colocation rules. We also describe a partial join approach for a spatial data set often clustered in neighborhood areas. We provide the algebraic cost models to characterize the performance dominance zones of the joinless method and the partial join method with a current join-based colocation mining method, and compare their computational complexities. In the experimental evaluation, using synthetic and real-world data sets, our methods performed more efficiently than the join-based method and show more scalability in dense data.

Since 1960, the chimpanzees (Pan troglodytes) of Gombe National Park, Tanzania, have been studied by behavioral ecologists, including Jane Goodall. Data have been collected for more than 40 years and are being analyzed by researchers in order to increase our understanding of the social structure of chimpanzees. In this paper, we consider the following question of interest to behavioral ecologists - "Does clustering exist among female chimpanzees in terms of their spatial locations ?" The analysis of this question will help behavioral ecologists to learn about the space use and the social interactions between female chimpanzees. The data collected for this analysis are marked spatial point patterns over the park. Current spatial clustering methods lack the ability to handle such marked point patterns directly. This paper presents a novel application of spatial point pattern analysis and data mining techniques to the ecological problem of clustering female chimpanzees. We found that Ripley's K-function provides a powerful statistical tool for evaluating clustering behavior among spatial point patterns. We then proposed two clustering approaches for marked point patterns using the K-function. Experimental results using the proposed clustering methods provide significant insight into the dynamics of female chimpanzee space use and into the overall social stucture of the species. In addition, the proposed methods can be extended to also include temporal information.

Spatial co-location patterns represent the subsets of features whose instances are frequently located together in geographic space. Co-location pattern discovery presents challenges since the instances of spatial features are embedded in a continuous space and share a variety of spatial relationships. A large fraction of the computation time is devoted to identifying the instances of co-location patterns. We propose a novel join-less approach for co-location pattern mining, which materializes spatial neighbor relationships with no loss of co-location instances and reduces the computational cost of identifying the instances. The join-less co-location mining algorithm is efficient since it uses an instance-lookup scheme instead of an expensive spatial or instance join operation for identifying co-location instances. The experimental evaluations show the join-less algorithm performs more efficiently than a current join-based algorithm and is scalable in dense spatial datasets.

Given a user-specified minimum correlation threshold θ and a market basket database with N items and T transactions, an all-strong-pairs correlation query finds all item pairs with correlations above the threshold θ. However, when the number of items and transactions are large, the computation cost of this query can be very high. In this paper, we identify an upper bound of Pearson's correlation coefficient for binary variables. This upper bound is not only much cheaper to compute than Pearson's correlation coefficient but also exhibits a special monotone property which allows pruning of many item pairs even without computing their upper bounds. A Two-step All-strong-Pairs corrElation que Ry (TAPER) algorithm is proposed to exploit these properties in a filter-and-refine manner. Furthermore, we provide an algebraic cost model which shows that the computation savings from pruning is independent or improves when the number of items is increased in data sets with common Zipf or linear rank-support distributions. Experimental results from synthetic and real data sets exhibit similar trends and show that the TAPER algorithm can be an order of magnitude faster than brute-force alternatives.

Co-location patterns are subsets of spatial features (e.g. freeways, frontage roads) usually located together in geographic space. Recent literature has provided a transaction-free approach to discover co-location patterns over spatial point data sets to avoid potential loss of proximity relationship information in partitioning continuous geographic space into transactions. This paper provides a more general transaction-free approach to mining data sets with extended spatial objects, e.g. line-strings and polygons. Key challenges include modeling of neighborhood and relationships among extended spatial objects as well as control of related geometric computation costs. The approach we propose is based on a new buffer-based definition of neighborhoods. Furthermore, we introduce and compare two pruning approaches, namely a prevalence-based pruning approach and a geometric filter-and-refine approach. Experimental evaluation with a real data set (a digital roadmap of the Minneapolis and St. Paul metropolitan area) shows that the geometric filter-and-refine approach can speed up the prevalence-based pruning approach by a factor of 30 to 40. Finally, we show how the extended co-location mining algorithm proposed in this paper has been used to find line-string co-location patterns, which can help with decision-makings on selecting most challenging field test routes. These field test routes are important for evaluating a GPS-based approach to accessing road user charges.

Given a collection of Boolean spatial features, the colocation pattern discovery process finds the subsets of features frequently located together. For example, the analysis of an ecology data set may reveal symbiotic species. The spatial colocation rule problem is different from the association rule problem since there is no natural notion of transactions in spatial data sets which are embedded in continuous geographic space. We provide a transaction-free approach to mine colocation patterns by using the concept of proximity neighborhood. A new interest measure, a participation index, is also proposed for spatial colocation patterns. The participation index is used as the measure of prevalence of a colocation for two reasons. First, this measure is closely related to the cross-K function, which is often used as a statistical measure of interaction among pairs of spatial features. Second, it also possesses an antimonotone property which can be exploited for computational efficiency. Furthermore, we design an algorithm to discover colocation patterns. This algorithm includes a novel multiresolution pruning technique. Finally, experimental results are provided to show the strength of the algorithm and design decisions related to performance tuning.

Nearest neighbor query is one of the most important operations in spatial databases and their application domains, e.g., location-based services, advanced traveler information systems, etc. This paper addresses the problem of finding the in-route nearest neighbor (IRNN) for a query object tuple which consists of a given route with a destination and a current location on it. The IRNN is a facility instance via which the detour from the original route on the way to the destination is smallest. This paper addresses four alternative solution methods. Comparisons among them are presented using an experimental framework. Several experiments using real road map datasets are conducted to examine the behavior of the solutions in terms of three parameters affecting the performance. Our experiments show that the computation costs for all methods except the precomputed zone-based method increase with increases in the road map size and the query route length but decreases with increase in the facility density. The precomputed zone-based method shows the most efficiency when there are no updates on the road map.

Direction-based spatial relationships are critical in many domains, including geographic information systems (GIS) and image interpretation. They are also frequently used as selection conditions in spatial queries. In this paper, we explore the processing of object-based direction queries and propose a new open shape-based strategy (OSS). OSS models the direction region as an open shape and converts the processing of the direction predicates into the processing of topological operations between open shapes and closed geometry objects. The proposed strategy OSS makes it unnecessary to know the boundary of the embedding world and also eliminates the computation related to the world boundary. OSS reduces both I/O and CPU costs by greatly improving the filtering effectiveness. Our experimental evaluation shows that OSS consistently outperforms classical range query strategies (RQS) while the degree of performance improvement varies by several parameters. Experimental results also demonstrate that OSS is more scalable than RQS for large data sets.

Summary form only given. The enormous size of vector maps and limited storage available in hand-held devices motivate the need for data compression techniques. Compression techniques for vector maps can allow PDAs to carry larger subsets of vector maps or free-up memory for other datasets and can also reduce the communication cost of downloading new maps to the PDA, possibly over low-bandwidth wireless channels (e.g. beaming, cell phone modems). We propose the use of clustering techniques (e.g. K-mean clustering) to identify dictionary entries while minimizing errors of approximation for locations of spatial objects in the map. Vectors relative to the first node of a road or relative to the previous node of a road are feed into clustering algorithms. Clustering algorithms take as input a fixed number and generates that many clusters for the given dataset as output. The cluster centroids obtained becomes our dictionary. Based on this dictionary, we encode the vector dataset that we obtained earlier. Since each vector would now be assigned to a particular cluster, that vector would now be represented in terms of a reference to that cluster's centroid entry in the dictionary. We formally show that this proposed dictionary construction approach often yields a lower error of approximation than the error from conventional fixed dictionary techniques.

A join-index is a data structure used for processing join queries in databases. Join-indices use precomputation techniques to speed up online query processing and are useful for data sets which are updated infrequently. The I/O cost of join computation using a join-index with limited buffer space depends primarily on the page-access sequence used to fetch the pages of the base relations. Given a join-index, we introduce a suite of methods based on clustering to compute the joins. We derive upper bounds on the length of the page-access sequences. Experimental results with Sequoia 2000 data sets show that the clustering method outperforms existing methods based on sorting and online-clustering heuristics.

Identification of outliers can lead to the discovery of unexpected, interesting, and useful knowledge. Existing methods are designed for detecting spatial outliers in multidimensional geometric data sets, where a distance metric is available. In this paper, we focus on detecting spatial outliers in graph structured data sets. We define statistical tests, analyze the statistical foundation underlying our approach, design several fast algorithms to detect spatial outliers, and provide a cost model for outlier detection procedures. In addition, we provide experimental results from the application of our algorithms on a Minneapolis-St.Paul(Twin Cities) traffic dataset to show their effectiveness and usefulness.

1 Introduction Widespread use of spatial databases[24] is leading to an increasing interest in mining interesting and useful but implicit spatial patterns[14, 17, 10, 22]. Efficient tools for extracting information from geo-spatial data, the focus of this work, are crucial to organizations which make decisions based on large spatial data sets. These organizations are spread across many domains including ecology and environment management, public safety, transportation, public health, business, travel and tourism[2, 12].

The integration of disparate heterogeneous spatial databases for extending queries is a challenging task. The authors present a novel framework, based on a k-nearest neighbor (kNN) algorithm, for integrating remote sensing imagery with Forest Inventory Analysis (FIA) sample point/plot data managed in a relational database system. We then demonstrate how queries to this system may be extended over any arbitrary region of interest in a Web based geographical information system. To build the integrated database, spectral signatures are collected at FIA plot locations from the Landsat TM image. A plot-id image is produced by assigning each pixel to the closest FIA plot in multi-dimensional spectral space. The resulting image provides an interface to the Forest Inventory Analysis Data-Base (FIADB) and allows generalizations of the estimates for any user defined query window or region of interest (ROI). This methodology, along with geostatistical analysis, is integrated into a client/server Web based geographical information system, which provides Internet users with an easy to use query interface for the FIADB and spatial databases.

Spatial databases, addressing the growing data management and analysis needs of spatial applications such as geographic information systems, have been an active area of research for more than two decades. This research has produced a taxonomy of models for space, spatial data types and operators, spatial query languages and processing strategies, as well as spatial indexes and clustering techniques. However, more research is needed to improve support for network and field data, as well as query processing (e.g., cost models, bulk load). Another important need is to apply spatial data management accomplishments to newer applications, such as data warehouses and multimedia information systems. The objective of this paper is to identify recent accomplishments and associated research needs of the near term.

Declustering and load balancing are important issues in designing a high performance geographic information system (HPGIS), which is a central component of many interactive applications such as real time terrain visualization. The current literature provides efficient methods for declustering spatial point data. However, there has been little work toward developing efficient declustering methods for collections of extended objects, like chains of line segments and polygons. We focus on the data partitioning approach to parallelizing GIS operations. We provide a framework for declustering collections of extended spatial objects by identifying the following key issues: (1) work load metric; (2) spatial extent of the work load; (3) distribution of the work load over the spatial extent; and (4) declustering method. We identify and experimentally evaluate alternatives for each of these issues. In addition, we also provide a framework for dynamically balancing the load between different processors. We experimentally evaluate the proposed declustering and load balancing methods on a distributed memory MIMD machine (Cray T3D). Experimental results show that the spatial extent and the work load metric are important issues in developing a declustering method. Experiments also show that the replication of data is usually needed to facilitate dynamic load balancing, since the cost of local processing is often less than the cost of data transfer for extended spatial objects. In addition, we also show that the effectiveness of dynamic load balancing techniques can be improved by using declustering methods to determine the subsets of spatial objects to be transferred during runtime.

Current spatial database management systems (SDBMS) provide efficient access methods and operators for point and range queries over collections of spatial points, line segments, and polygons. However, it is not clear if existing spatial access methods can efficiently support network computations which traverse line segments in a spatial network based on connectivity rather than geographic proximity. The expected I/O cost for many network operations can be reduced by maximizing the Weighted Connectivity Residue Ratio (WCRR), i.e., the chance that a pair of connected nodes that are more likely to be accessed together are allocated to a common page of the file. CCAM is an access method for general networks that uses connectivity clustering. CCAM supports the operations of insert, delete, create, and find as well as the new operations, get-A-successor and get-successors, which retrieve one or all successors of a node to facilitate aggregate computations on networks. The nodes of the network are assigned to disk pages via a graph partitioning approach to maximize the WCRR. CCAM includes methods for static clustering, as well as dynamic incremental reclustering, to maintain high WCRR in the face of updates, without incurring high overheads. We also describe possible modifications to improve the WCRR that can be achieved by existing spatial access methods. Experiments with network computations on the Minneapolis road map show that CCAM outperforms existing access methods, even though the proposed modifications also substantially improve the performance of existing spatial access methods.

Resolving domain incompatibility among independently developed databases often involves uncertain information. DeMichiel (1989) showed that uncertain information can be generated by the mapping of conflicting attributes to a common domain, based on some domain knowledge. We show that uncertain information can also arise when the database integration process requires information not directly represented in the component databases, but can be obtained through some summary of data. We therefore propose an extended relational model based on Dempster-Shafer theory of evidence to incorporate such uncertain knowledge about the source databases. The extended relation uses evidence sets to represent uncertainty in information, which allow probabilities to be attached to subsets of possible domain values. We also develop a full set of extended relational operations over the extended relations. In particular, an extended union operation has been formalized to combine two extended relations using Dempster's rule of combination. The closure and boundedness properties of our proposed extended operations are formulated. We also illustrate the use of extended operations by some query examples.

We propose a new similarity-based technique for declustering data. The proposed method can adapt to available information about query distributions, data distributions, data sizes and partition-size constraints. The method is based on max-cut partitioning of a similarity graph defined over the given set of data, under constraints on the partition sizes. It maximizes the chances that a pair of data-items that are to be accessed together by queries are allocated to distinct disks. We show that the proposed method can achieve optimal speed-up for a query-set, if there exists any other declustering method which will achieve the optimal speed-up. Experiments in parallelizing grid files show that the proposed method outperforms mapping-function-based methods for interesting query distributions as well for non-uniform data distributions.>

CCAM is an access method for general networks. It uses connectivity clustering. The nodes of the network are assigned to disk pages via the graph partitioning approach to maximize the CRR, i.e., the chances that a pair of connected nodes are allocated to a common page of the file. CCAM supports the operations of insert, delete, create, and find as well as the new operations, get-A-successor and get-successors, which retrieve one or all successors of a node to facilitate aggregate computations on networks. CCAM includes methods for static clustering, as well as dynamic incremental reclustering, to maintain, high CRR, in the face of updates without incurring high overheads. Experimental analysis indicates that CCAM can outperform many other access methods for network operations.>

Resolving domain incompatibility among independently developed databases often involves uncertain information. DeMichiel (1989) showed that uncertain information can be generated by the mapping of conflicting attributes to a common domain, based on some domain knowledge. The authors show that uncertain information can also arise when the database integration process requires information not directly represented in the component databases, but can be obtained through some summary of data. They therefore propose an extended relational model based on Dempster-Shafer theory of evidence (1976) to incorporate such uncertain knowledge about the source databases. They also develop a full set of extended relational operations over the extended relations. In particular, an extended union operation has been formalized to combine two extended relations using Dempster's rule of combination. The closure and boundedness properties of the proposed extended operations are formulated.>

The grid file is a well known access method for multi-dimensional and spatial data. The response time needed to process path and range queries on the grid file access method can be improved significantly by distributing the data pages over multiple disks. The paper explores the disk allocation methods used to allocate the data pages of grid file among a set of disks, which can be accessed in parallel. Given N disks, a perfect allocation will speed up the processing of each query by a factor of N in this environment. The authors show that no disk allocation is perfect for the set of all orthogonal range queries, even on uniformly distributed read-only data. They then introduce two families of allocation methods, namely the Linear allocation method and the Lattice allocation method, which are perfect for a large collection of interesting path queries (rows, columns, diagonals, anti-diagonals) and range queries (small rectangles), on an interesting set of data distributions. They address the issues in extending disk allocation methods to general data distributions with random updates. Finally, they provide experimental results on the performance of the proposed methods and other well known disk allocation methods on different query sets, data distributions and data set sizes.>

Three path-planning algorithms for single-pair path computation are evaluated. These algorithms are the iterative breath-first search, Dijkstra's single-source path-planning algorithm, and the A* single-path planning algorithm. The performance of the algorithms is evaluated on graphs representing the roadmap of Minneapolis. In order to get an insight into their relative performance, synthetic grid maps are used as a benchmark computation. The effects of two parameters, namely path length and edge-cost-distribution, on the performance of the algorithms are examined. The effects of implementation decisions on the performance of the A* algorithm are discussed. The main hypothesis is that estimator functions can improve the average-case performance of single-pair path computation when the length of the path is small compared to the diameter of the graph. This hypothesis is examined using experimental studies and analytical cost modeling.>

An approach to learning query-transformation rules based on analyzing the existing data in the database is proposed. A framework and a closure algorithm for learning rules from a given data distribution are described. The correctness, completeness, and complexity of the proposed algorithm are characterized and a detailed example is provided to illustrate the framework.>

Efforts in database design for observational scientific data concerned with path query specification and an access method design are discussed. The goal is to understand the issues related to scientific data and computations. The authors propose a representation of path queries and an access method, MoBiLe files, to capture space-time continuity. A survey on spatial indexing methods is given. The model of scientific data and computation is described. An example of scientific databases is also given. Path queries are then specified. The MoBiLe mapping functions and MoBiLe file design are described. The experiment used to verify the access methods and the data model are outlined. The experimental results and this observation and analysis are presented.>

The authors discuss the requirements of learning for generalization, where the traditional methods based on gradient descent have limited success. A stochastic learning algorithm based on simulated annealing in weight space is presented. The authors verify the convergence properties and feasibility of the algorithm. An implementation of the algorithm and validation experiments are described.>

Conventional expert systems based on a single flat knowledge base have fared well in solving a narrow range of problems. Their architectures, however, do not extend to large applications like automated factories, which require multidisciplinary knowledge and are geographically distributed. To solve multidisciplinary problems, a knowledge-based system must be able to: reason about the need for cooperation, understand global knowledge to locate relevant expert systems and select appropriate cooperation plans. Cooperations models to characterize three essential decisions in the cooperation process are proposed. A computational method is devised to decide if an expert system has enough knowledge to solve a given problem or if it needs to consult with other expert systems. The use of a yellow-pages technique to represent global knowledge and to select appropriate cooperation plans is proposed. The approach lets expert systems autonomously resolve the three fundamental decisions in cooperation at run time, in contrast to contemporary approaches in which the decisions are made at design time by the programmers.>