Accurate radio source localization on resource-constrained hardware presents a primary challenge in wireless networks. We introduce EfficientLocNet, a novel architecture achieving superior accuracy with exceptional computational efficiency, driven by two distinct design choices. Its efficiency stems from lightweight Depthwise Separable Convolutions, while its accuracy is enhanced by two components working in tandem: Atrous Spatial Pyramid Attention to capture long-range spatial features, and a Self-Attention module to refine the latent representation. Evaluated against state-of-the-art (SOTA) methods, EfficientLocNet outperforms the top-performing model, DSLoc, on all key metrics: it reduces the mean localization error by at least 5%, possesses a 40x smaller model size, and requires over 100x fewer computations. This compelling combination of performance and efficiency validates EfficientLocNet as a powerful solution for deployment in edge computing environments.

Accurately predicting directional radio maps is crucial for various wireless applications; however, existing methods that primarily rely on Convolutional Neural Networks (CNNs) or U-Nets designed for omnidirectional signals struggle to capture the long-range dependencies and angular sensitivities inherent in directional signal propagation (especially when influenced by environmental factors like building occlusions and reflections). To overcome these limitations, we introduce a novel framework, denoted as "ViT-RefineNet," that is specifically designed for predicting directional radio maps from sparse signal measurements. Our approach integrates a Vision Transformer (ViT)-based model to capture global dependencies with multiple U-Net-like modules for localized refinement at different processing stages. By effectively combining global context understanding with local detail enhancement, ViT-RefineNet offers significant advantages over traditional CNN-based and U-Net-based methods in predicting directional radio maps from sparse directional signal measurements. Experimental results demonstrate the superior performance of our proposed ViT-RefineNet compared to state-of-the-art models.1

Accurate traffic forecasting is crucial for Intelligent Transportation Systems (ITS) but is significantly challenged by non-periodic external events that disrupt regular traffic patterns. While Graph Neural Networks (GNNs) excel at modeling periodic traffic, they often falter in predicting event-driven dynamics. Existing event-aware methods either rely on manually engineered features with limited generalization or depend on curated textual event datasets that are costly to maintain and incomplete. The advent of Large Language Models (LLMs) offers new avenues for understanding and integrating event information. However, directly applying LLMs for all spatio-temporal reasoning can be inefficient, and effectively leveraging their event understanding capabilities within structured forecasting workflows remains a challenge. This paper introduces FUSE-Traffic, a framework which synergizes the dynamic event querying and understanding prowess of LLMs with the spatio-temporal modeling capabilities of GNNs. FUSE-Traffic features an on-demand event information extraction module using LLM prompting and a cross-attention based multimodal fusion mechanism to integrate rich event semantics with traffic flow features. This design enables the model to dynamically perceive and adapt to event-triggered traffic pattern changes. Comprehensive experiments on the METR-LA and PEMS datasets demonstrate that FUSE-Traffic significantly outperforms state-of-the-art models, especially under high-impact event conditions, showcasing robust predictive accuracy and resilience where traffic patterns are most disrupted. Code available at https://github.com/GeoAICenter/FUSE-Traffic_Sigspatial2025

Geo-obfuscation is a Location Privacy Protection Mechanism used in location-based services that allows users to report obfuscated locations instead of exact ones. A formal privacy criterion, geoindistinguishability (Geo-Ind), requires real locations to be hard to distinguish from nearby locations (by attackers) based on their obfuscated representations. However, Geo-Ind often fails to consider context, such as road networks and vehicle traffic conditions, making it less effective in protecting the location privacy of vehicles, of which the mobility are heavily influenced by these factors.

Understanding and predicting Origin-Destination (OD) flows is crucial for urban planning and transportation management. Traditional OD prediction models, while effective within single cities, often face limitations when applied across different cities due to varied traffic conditions, urban layouts, and socio-economic factors.

This paper presents a publicly accessible large-scale geo-tagged Twitter dataset, comprising 95.8 million tweets from 247 countries, spanning from Jan. 2012 to Dec. 2021. To systematically extract this dataset from over 57.18 TB of raw tweets, we employed parallel computing on a 40-node cluster with 480 CPU cores. Distinguishing it from most existing Twitter datasets, our dataset includes four-level granularity tweet locations, two-level granularity user profile locations, and tweet text languages, enabling personalized queries. To enhance the open accessibility of our dataset, we have designed an innovative interactive online query system (https://sigspatial.yunhefeng.me) and provided free-to-use JSON APIs (https://github.com/ResponsibleAILab/unt-geotweet-api) for customized queries to retrieve tweet IDs in tweet coordinate, tweet text-based location, and user location modes. Then users can use https://github.com/ResponsibleAILab/unt-tweet-rehydration to download complete tweet information. Furthermore, we have demonstrated the practical utility of our dataset through two applications: human movement modeling and geo-aware Large Language Model (LLM) tuning. Our geo-tagged Twitter dataset, along with the accompanying query system and APIs, contributes to the research community and opens up avenues for multidisciplinary investigations and the advancement of knowledge.

Bike-sharing service as an important public transportation system has grown over 1800% from 2014 to 2018 in worldwide. Accurate bike demand prediction of bike-sharing system is critical for increasing user satisfaction, improving the system efficiency, and expand bike stations to new regions. There are two major challenges for existing bike demand prediction methods: First, several current works heavily rely on historical bike transition records and can not predict bike demands for new stations. Second, people movement patterns as an important factor for bike demand prediction are not considered. To address these challenges, in this paper, we develop a place representation based bike demand prediction framework, which uses large scale people movement data to analyze bike demand. The framework is based on an origin-destination algorithm, which is a novel approach for learning latent representation of places, and a feature selection process to reduce place's embedding size to a proper number. Hourly bike check-ins/check-outs of each station is predicted by integrating three factors: place embedding, station geography, and POI distribution. Experiments on NYC CitiBike system show that compared with the state-of-the-art function zone based method, our model reduces error rate by 6% and root mean squared logarithmic error by 4% in prediction of existing bike station demand and by 6% and 5% for new stations in error rate and root mean squared logarithmic error respectively.

Ridesharing can save energy, reduce pollution, and alleviate congestion. These societal benefits can only occur, however, if sufficient trust is established between rideshare partners. Trust judgments heavily influence the usage of ridesharing platforms. Towards trust building, ridesharing systems are starting to allow drivers to provide personal information about themselves. Some previous work already built a trust prediction model using information from Instagram profiles. Their results indicated both social account information and picture information factors influenced judgments of trust of potential rideshare partners. In this paper, we advance these findings by describing a co-training approach that uses social account information and picture information as two independent views to predict trust judgments. Specifically, this analysis addresses the problem of accurate labeling of complex pictures from social media by using the hashtags of pictures for trust inference. We use a topic model to summarize the hashtags of pictures into a small number of groups called topics. The final results show that using hashtags as picture information yields a better result than the use of picture category. The co-training approach with social account information and hashtags outperforms supervised and semisupervised classifiers. Often, in order to make an accurate trust prediction model, large amounts of expensive labeled training data are needed. The co-training approach described allows for faster labeling of large datasets, saving resources by avoiding intensive human labeling effort.

The number of bike-sharing services worldwide has grown over 1800% from 2014 to 2018. Accurate flow prediction of bike-sharing systems is critical for increasing user satisfaction, improving the efficiency, and planning new stations. Current flow prediction methods leave out important contextual features. In this paper, we propose a context-aware framework to predict bike flows for both existing stations and new stations. The model incorporates spatiotemporal, network, and environment contexts in a synergistic manner. The proposed model is evaluated on a bike-sharing system in New York City (NYC). Our model reduced error rate by 9% and root mean squared logarithmic error by 8% compared with the state-of-the-art neural network based method using context features. We also extend our model to a clustered bike flow prediction model, which is the focus of most of the current literature. Our model outperformed the state-of-the-art clustered model by 23% and 25% under anomalous situations in error rate and root mean squared logarithmic error respectively.

Understanding and reasoning about places and their relationships are critical for many applications. Places are traditionally curated by a small group of people as place gazetteers and are represented by an ID with spatial extent, category, and other descriptions. However, a place context is described to a large extent by movements made from/to other places. Places are linked and related to each other by these movements. This important context is missing from the traditional representation.We present DeepMove, a novel approach for learning latent representations of places. DeepMove advances the current deep learning based place representations by directly model movements between places. We demonstrate DeepMove's latent representations on place categorization and clustering tasks on large place and movement datasets with respect to important parameters. Our results show that DeepMove outperforms state-of-the-art baselines. Without sophisticated weighting schemes, DeepMove's representations can provide up to 15% higher than competing methods in matching rate of place category and result in up to 39% higher silhouette coefficient value for place clusters evaluated on a dataset with 19,194 point of interests (POIs) and 14 million trips.DeepMove is spatial and temporal context aware. It is scalable. It outperforms competing models using much smaller training dataset (a month or 1/12 of data). These qualities make it suitable for a broad class of real-world applications.

Geotagged tweets allow one to extract geo-information-trend, search local events, and identify natural disasters. In this paper, we propose a Hidden-Markov-based model to integrate tweet contents and user movements for geotagging. A language model is obtained for different locations from training datasets and movements of users among cities are analyzed. Home cities of users are considered in modeling the patterns of user movements. Evaluation on a large Twitter dataset shows that our method can significantly improve geotagging accuracy by 55% for home cities and 2% for other non-home cities as well as reduce error distances by orders of magnitude compared with pure text-based methods.

The analysis of Twitter data can help to predict or explain many real world phenomena. The relationships among events in the real world can be reflected among the topics on social media. In this paper, we propose the concept of topic association and the associated mining algorithms. Topics with close temporal and spatial relationship may have direct or potential association in the real world. Our goal is to mine such topic associations and show their relationships in different time-region frames. We propose to use the concepts of participation ratio and participation index to measure the closeness among topics and propose a spatiotemporal index to calculate them efficiently. With the topic filtering and the topic combination, we further optimize the mining process and the mining results. The algorithms are evaluated on a Twitter dataset with 27,956,257 tweets.

Twitter is one of the most popular social media platforms where people can share their opinions, thoughts, interests, and whereabouts. In this work, we propose a Local Event Discovery and Summarization (LEDS) framework to detect local events from Twitter. Many existing algorithms for event detection focus on larger-scale events and are not sensitive to smaller-scale local events. Most of the local events detected by these methods are major events such as important sports, shows, or large natural disasters. In this paper, we propose the LEDS framework to detect both larger and smaller events. LEDS contains three key steps: 1) Detecting possible event related terms by monitoring abnormal distribution in different locations and times; 2) Clustering tweets based on their key terms, time, and location distribution; and 3) Extracting descriptions including time, location, and key sentences of local events from clusters. The framework is evaluated on a real world Twitter dataset with more than 60 million tweets. The results show that compared with previous work, LEDS can detect smaller-scale and greater variety of local events. More than 43 percent of detected local events do not have an official organizer, cannot be seen on news media, and only attract the attention from a small group of people.

Action recognition is one of the most important components for video analysis. In addition to objects and atomic actions, temporal relationships are important characteristics for many actions and are not fully exploited in many approaches. We model the temporal structures of midlevel actions (referred to as components) based on dense trajectory components, obtained by clustering individual trajectories. The trajectory components are a higher level and a more stable representation than raw individual trajectories. Based on the temporal ordering of trajectory components, we describe the temporal structure using Allen's temporal relationships in a discriminative manner and combine it with a generative model using bag of components. The main idea behind the model is to extract midlevel features from domain-independent dense trajectories and classify the actions by exploring the temporal structure among these midlevel features based on a set of relationships. We evaluate the proposed approach on public data sets and compare it with a bag-of-words–based approach and state-of-the-art application of the Markov logic network for action recognition. The results demonstrate that the proposed approach produces better recognition accuracy.

Many real world systems or web services can be represented as a network such as social networks and transportation networks. In the past decade, many algorithms have been developed to detect the communities in a network. However, the impact of locations on community has not been fully investigated by the research literature. In this paper, we propose a method to determine if a location-based community detection method is suitable for a given network and provide a new community detection algorithm that pushes the location information into the community detection. We test our proposed method on both synthetic data and real world network datasets. The results show that the communities detected by our method distribute in a smaller area compared with the traditional methods and have the similar or higher tightness on network connections.

Urban traffic gridlock is a familiar scene. At the same time, the mean occupancy rate of personal vehicle trips in the United States is only 1.6 persons per vehicle mile. Ridesharing has the potential to solve many environmental, congestion, pollution, and energy problems. In this paper, we introduce the problem of large scale real-time ridesharing with service guarantee on road networks. Trip requests are dynamically matched to vehicles while trip waiting and service time constraints are satisfied. We first propose two scheduling algorithms: a branch-and-bound algorithm and an integer programing algorithm. However, these algorithms do not adapt well to the dynamic nature of the ridesharing problem. Thus, we propose kinetic tree algorithms which are better suited to efficient scheduling of dynamic requests and adjust routes on-the-fly. We perform experiments on a large Shanghai taxi dataset. Results show that the kinetic tree algorithms outperform other algorithms significantly.

A tremendous amount of information is being shared everyday on social media sites such as Facebook, Twitter or Google+. But only a small portion of users provide their location information, which can be helpful in targeted advertisement and many other services. In this demo we present our large scale user location estimation system, SPOT, which showcase different location estimating models on real world data sets. The demo shows three different location estimation algorithms: a friend-based, a social closeness-based, and an energy and local social coefficient based. The first algorithm is a baseline and the other two new algorithms utilize social closeness information which was traditionally treated as a binary friendship. The two algorithms are based on the premise that friends are different and close friends can help to estimate location better. The demo will also show that all three algorithms benefit from a confidence-based iteration method. The demo is web-based. A user can specify different settings, explore the estimation results on a map, and observe the statistical information, e.g. accuracy and average friends used in the estimation, dynamically. The demo provides two datasets: Twitter (148,860 located users) and Gowalla (99,563 located users). Furthermore, a user can filter users with certain features, e.g. with more than 100 friends, to see how the estimating models work on a particular case. The estimated and real locations of those users as well as their friends will be displayed on the map.

Aggregate nearest neighbor query, which returns a common interesting point that minimizes the aggregate distance for a given query point set, is one of the most important operations in spatial databases and their application domains. This paper addresses the problem of finding the aggregate nearest neighbor for a merged set that consists of the given query point set and multiple points needed to be selected from a candidate set, which we name as merged aggregate nearest neighbor(MANN) query. This paper proposes an effective algorithm to process MANN query in road networks based on our pruning strategies. Extensive experiments are conducted to examine the behaviors of the solutions and the overall experiments show that our strategies to minimize the response time are effective and achieve several orders of magnitude speedup compared with the baseline methods.

This demo presents Noah: a dynamic ridesharing system. Noah supports large scale real-time ridesharing with service guarantee on road networks. Taxis and trip requests are dynamically matched. Different from traditional systems, a taxi can have more than one customer on board given that all waiting time and service time constraints of trips are satisfied. Noah's real-time response relies on three main components: (1) a fast shortest path algorithm with caching on road networks; (2) fast dynamic matching algorithms to schedule ridesharing on the fly; (3) a spatial indexing method for fast retrieving moving taxis. Users will be able to submit requests from a smartphone, choose specific parameters such as number of taxis in the system, service constraints, and matching algorithms, to explore the internal functionalities and implementations of Noah. The system analyzer will show the system performance including average waiting time, average detour percentage, average response time, and average level of sharing. Taxis, routes, and requests will be animated and visualized through Google Maps API. The demo is based on trips of 17,000 Shanghai taxis for one day (May 29, 2009); the dataset contains 432,327 trips. Each trip includes the starting and destination coordinates and the start time. An iPhone application is implemented to allow users to submit a trip request to the Noah system during the demonstration.

Due to the proliferation of Location-Based Service and popularity of online geo-tagged web pages, spatial keyword search has attracted significant attention from both academic and industrial communities. In this paper, we study the problem of finding the nearest aggregate point from multiple query points travelling through a set objects described by a given set of keywords, as well as the optimal routes from the query points to the aggregate point. This problem is defined as the Aggregate Keyword Routing (AKR) Query. We devise an exact algorithm to AKR query based on ellipse pruning. Next we propose an efficient approximate algorithm for AKR: Center Based Assignment (CBA). The performance of the proposed algorithms are evaluated with real data, the results demonstrate the efficiency and the effectiveness.

Thousands of taxis cruise a metropolitan road network looking for passengers that may be scattered or clustered in highly active locations. Taxicab drivers tend to gravitate to the known clusters, often leading to supply and demand disequilibrium as areas become under or over served. Many cities monitor their taxi fleet's locations using GPS devices and track passenger occupancy through trip meters, thereby producing data streams of taxicab trajectories and passenger activities. This paper presents the Service Disequilibrium Detection (SDD) framework which aims at identifying regions of service disequilibrium using this information. The SDD framework models request wait time and taxicab location uncertainty inherent in the discrete data streams and identifies the disequilibrium regions using two methods: (1) Bayesian spatial scan statistics, and (2) Poisson-based hypothesis testing. We claim the SDD framework can detect emerging disequilibrium and validate this claim using a large Shanghai taxi GPS data set.

The ACM SIGSPATIAL Cup 2012 is about map matching, a problem of correctly matching a sequence of GPS sampling points to the roads on a digital map. This paper describes one of the winning submissions of the competition. The approach applies multi-threading technology to map matching in order to reduce running time and we propose an improvement to the Hidden Markov Model (HMM) map matching algorithm.

The term "indoor" here refers generally to enclosed space partitioned into subspaces with connecting doors or gates. Examples include the inside of office buildings, amusement parks, and indoor shopping malls. In many applications, it is desirable to keep track of the distribution of people within the enclosed space. These applications range from smart house with automatically controlled air-conditioning and lighting, shopping assistance allocation, to business intelligence. Contact sensors are accurate but obstructive. Non-contact sensors such as automated visual recognition and RFID tags can be expensive in calibration or cost in order to obtain accurate readings. An interesting cost optimization problem is to understand how to obtain relatively accurate dynamic distribution of people from inaccurate point sensors using correlations among the point sensor readings. The paper formalizes a framework that uses a flow model and a particle-filter learning algorithm for this optimization problem based on the hypotheses that (1) there is an underlying stochastic "flow model" of people moving within the space, and (2) with the help of this flow model, counting of people can be made more accurate by taking advantage of the continuous, albeit inaccurate, point sensor readings. The main challenge is that the performance of particle filters deteriorates rapidly with the number of doors in the indoor space. We propose a divide and conquer method that uses relatively more accurate sensors at a few strategically chosen locations to achieve overall good accuracy. Experimental results given herein show that the algorithm is effective.

We propose a flexible mini-shuttle like transportation system called flexi, with routes formed by analyzing passenger trip data from a large set of taxi trajectories. The usage of public transportation is declining as often it no longer matches with individual needs. Thus, the flexi system provides a transportation mode in between buses and taxis so that inconvenience in switching to the system can be minimized overall. To generate flexi routes, we propose a two-phase approach. In the first phase, a fast diameter-constrained agglomerative clustering algorithm is developed and applied to the set of trips derived from the GPS data. This phase identifies a set of heavily traveled spatio-temporal trip clusters called hot lines. In the second phase, a directed acyclic graph is constructed from the hot lines. Then, an optimal single flexi route discovery algorithm on graph searching is proposed. Multiple routes are discovered by iteratively applying the single routing algorithm. Extensive experiments using a large set of real taxi trajectory data show that the flexi system can save a large percentage of trip mileage.

The recent growth in sensor technology allows easier information gathering in real-time as sensors have grown smaller, more accurate, and less expensive. The resulting data is often in a geo-stream format---continuously changing input with a spatial extent. Researchers developing geo-streaming management systems (GSMS) require a benchmark system for evaluation, which is currently lacking. This paper presents GSMark, a benchmark for evaluating GSMSs. GSMark provides a data generator that creates a combination of synthetic and real geo-streaming data, a workload simulator to present the data to the GSMS as a data stream, and a set of benchmark queries that evaluate typical GSMS functionality and query performance. In particular, GSMark generates both moving points and evolving spatial regions, two fundamental data types for a broad range of geo-stream applications, and the geo-streaming queries on this data.

Large graphs are difficult to represent, visualize, and understand. In this paper, we introduce "gate graph" a new approach to perform graph simplification. A gate graph provides a simplified topological view of the original graph. Specifically, we construct a gate graph from a large graph so that for any "non-local" vertex pair (distance greater than some threshold) in the original graph, their shortest-path distance can be recovered by consecutive "local" walks through the gate vertices in the gate graph. We perform a theoretical investigation on the gate-vertex set discovery problem. We characterize its computational complexity and reveal the upper bound of minimum gate- vertex set using VC-dimension theory. We propose an efficient mining algorithm to discover a gate-vertex set with guaranteed logarithmic bound. The detailed experimental results using both real and synthetic graphs demonstrate the effectiveness and efficiency of our approach.

GPS-equipped taxis can be regarded as mobile sensors probing traffic flows on road surfaces, and taxi drivers are usually experienced in finding the fastest (quickest) route to a destination based on their knowledge. In this paper, we mine smart driving directions from the historical GPS trajectories of a large number of taxis, and provide a user with the practically fastest route to a given destination at a given departure time. In our approach, we propose a time-dependent landmark graph, where a node (landmark) is a road segment frequently traversed by taxis, to model the intelligence of taxi drivers and the properties of dynamic road networks. Then, a Variance-Entropy-Based Clustering approach is devised to estimate the distribution of travel time between two landmarks in different time slots. Based on this graph, we design a two-stage routing algorithm to compute the practically fastest route. We build our system based on a real-world trajectory dataset generated by over 33,000 taxis in a period of 3 months, and evaluate the system by conducting both synthetic experiments and in-the-field evaluations. As a result, 60-70% of the routes suggested by our method are faster than the competing methods, and 20% of the routes share the same results. On average, 50% of our routes are at least 20% faster than the competing approaches.

The applications of wireless sensor networks often require region representations of the phenomena that the networks monitor for visualization and interaction with spatial databases. However, there is a fundamental gap between the point-based sensor observation of non-regular sensor deployment and the spatio-temporal phenomena represented by regions. This paper proposes to bridge the gap by providing low-communication-cost approaches to create regions from the distributed sensors. The solution is based on Spatial Grid partition and the task is distributed among a set of sensors called ``cell leaders''. We formalize the problem of cell-leader selection with the objective of minimizing sensor communication cost. We propose two heuristic algorithms, i.e., Greedy Lattice Search and Subregion Centroid Approximation. We also propose Energy-Aware Local Update model to allow the dynamic re-assignment of cell leaders. The experiments performed on a real sensor observation dataset demonstrated that our heuristic approaches can achieve much better communication cost compared with the baseline methods.

Map-matching is the process of aligning a sequence of observed user positions with the road network on a digital map. It is a fundamental pre-processing step for many applications, such as moving object management, traffic flow analysis, and driving directions. In practice there exists huge amount of low-sampling-rate (e.g., one point every 2--5 minutes) GPS trajectories. Unfortunately, most current map-matching approaches only deal with high-sampling-rate (typically one point every 10--30s) GPS data, and become less effective for low-sampling-rate points as the uncertainty in data increases. In this paper, we propose a novel global map-matching algorithm called ST-Matching for low-sampling-rate GPS trajectories. ST-Matching considers (1) the spatial geometric and topological structures of the road network and (2) the temporal/speed constraints of the trajectories. Based on spatio-temporal analysis, a candidate graph is constructed from which the best matching path sequence is identified. We compare ST-Matching with the incremental algorithm and Average-Fréchet-Distance (AFD) based global map-matching algorithm. The experiments are performed both on synthetic and real dataset. The results show that our ST-matching algorithm significantly outperform incremental algorithm in terms of matching accuracy for low-sampling trajectories. Meanwhile, when compared with AFD-based global algorithm, ST-Matching also improves accuracy as well as running time.

In this demo paper, we report our experience of designing and implementing a geospatial data stream query engine in SECONDO. Compared with current data stream and moving object query systems, our query engine not only supports point geo-streams that represent continuously moving points, but also line and region geo-streams that represent complex spatio-temporal phenomena elevated from geo-referenced raw readings. We implement the data types, operators, and language extensions as a modular algebra in SECONDO. We also provide an independent SQL parser for specifying continuous queries using SQL-like syntax as well as an Ajax-driven web interface for dynamic visualization of steaming results.

This paper proposes a new type of query for moving object trajectories -- continuous interval-based nearest neighbor (CINN) query. We clearly define the CINN in the context of streaming trajectory data. To efficiently process CINN queries, we first propose a spatial hashing algorithm (SH). Then we show theta new temporal hashing algorithm (TH) using speed constraints can save substantial computation cost. To reduce memory cost, we further propose the temporal hashing with dropping optimization (THwD) algorithm. Extensive experiment results on large trajectory datasets show that CINN queries can be effectively answered using our proposed algorithms. With realistic speed constraints, the TH optimization can save the computation time by nearly an order of magnitude compared with the BF algorithm, and by 5 times compared with the SH algorithm. The THwD algorithm can further save the memory space by nearly an order of magnitude.

Given a large spatio-temporal database of events, where each event consists of the fields event ID, time, location, and event type, mining spatio-temporal sequential patterns identifies significant event-type sequences. Such spatio-temporal sequential patterns are crucial to the investigation of spatial and temporal evolutions of phenomena in many application domains. Recent research literature has explored the sequential patterns on transaction data and trajectory analysis on moving objects. However, these methods cannot be directly applied to mining sequential patterns from a large number of spatio-temporal events. Two major research challenges still remain: 1) the definition of significance measures for spatio-temporal sequential patterns to avoid spurious ones and 2) the algorithmic design under the significance measures, which may not guarantee the downward closure property. In this paper, we propose a sequence index as the significance measure for spatio-temporal sequential patterns, which is meaningful due to its interpretability using spatial statistics. We propose a novel algorithm called Slicing-STS-miner to tackle the algorithmic design challenge using the spatial sequence index, which does not preserve the downward closure property. We compare the proposed algorithm with a simple algorithm called STS-miner that utilizes the weak monotone property of the sequence index. Performance evaluations using both synthetic and real-world data sets show that the slicing-STS-miner is an order of magnitude faster than STS-Miner for large data sets.

The development of areas such as remote and airborne sensing, location based services, and geosensor networks enables the collection of large volumes of spatial data. These datasets necessitate the wide application of spatial databases. Queries on these geo-referenced data often require the aggregation of isolated data points to form spatial clusters and obtain properties of the clusters. However, current SQL standard does not provide an effective way to form and query spatial clusters. In this paper, we aim at introducing Cluster By into spatial databases to allow a broad range of interesting queries to be posted on spatial clusters. We also provide a language construct to specify spatial clustering algorithms. The extension is demonstrated with several motivating examples.

Given a large spatio-temporal database of events, where each event consists of the following fields: event-ID, time, location, event-type, mining spatio-temporal sequential patterns is to identify significant event type sequences. Such spatiotemporal sequential patterns are crucial to investigate spatial and temporal evolutions of phenomena in many application domains. In this paper, we propose a sequence index as the significance measure for spatio-temporal sequential patterns, which is meaningful due to its interpretability using spatial statistics. We propose two algorithms, namely STSMiner and Slicing-STS-Miner, to tackle the algorithmic design challenges under the spatial sequence index which does not preserve the downward closure property. We evaluate the algorithms by experimentally conducting performance evaluations using both synthetic and real world datasets.

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.

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.