The task of next-item recommendation is a crucial component in recommendation systems. The challenge of this task lies in extracting complex interaction information from users’ historical interactions with items. While prior research has transformed users’ interaction histories into graphs and hypergraphs to mine high-order interactions, the integration of both remains uncharted. Existing methods treat graphs and hypergraphs separately in representation learning, missing out on their shared attributes. Addressing this gap, we introduce a novel unified framework that integrates graphs and hypergraphs into one unified message passing paradigm. Our method employs graph neural networks and hypergraph neural networks to continuously conduct representation learning, achieving end-to-end next item recommendation. Specifically, our framework consists of the following components: 1) a unique method for graph and hypergraph construction from interaction histories, with items as nodes and users as hyperedges; 2) a novel message passing framework compatible with both graph and hypergraph neural networks; and 3) an innovative hypergraph neural network aggregation module enhanced with time and position encoders. The test results on multiple public benchmarks verify that our method outperforms current best practices in performance.

Hypergraph neural networks can model more flexible connectivity relationships, are used to model higher-order interactions, and have produced strong results in many real-world applications. However, the currently existing hypergraph neural networks need more exploration in capturing the global positional information of nodes in hypergraphs. Although there have been many explorations of the problem in graph neural networks, extending these approaches to hypergraphs is fraught with challenges. The major challenge is that hyperedges in hypergraphs are the other dimensional element of the incidence structure, have more flexible definitions than edges in graphs, and require more attention when learning global positional information. We propose a novel position-aware hypergraph message-passing neural network framework to address the above challenges. Specifically, we propose a global positional embedding learning approach that can separately model global positional information for nodes and hyperedges. At the same time, we also optimize the learning of local structures with hyperedges. Experiments on several publicly available benchmark datasets find that our proposed method outperforms many state-of-the-art methods.

In real-world applications, GPS trajectories often suffer from low sampling rates, with large and irregular intervals between consecutive GPS points. This sparse characteristic presents challenges for their direct use in GPS-based systems. This paper addresses the task of map-constrained trajectory recovery, aiming to enhance trajectory sampling rates of GPS trajectories. Previous studies commonly adopt a sequence-to-sequence framework, where an encoder captures the trajectory patterns and a decoder reconstructs the target trajectory. Within this framework, effectively representing the road network and extracting relevant trajectory features are crucial for overall performance. Despite advancements in these models, they fail to fully leverage the complex spatio-temporal dynamics present in both the trajectory and the road network. To overcome these limitations, we categorize the spatio-temporal dynamics of trajectory data into two distinct aspects: spatial-temporal traffic dynamics and trajectory dynamics. Furthermore, We propose TedTrajRec, a novel method for trajectory recovery. To capture spatio-temporal traffic dynamics, we introduce PD-GNN, which models periodic patterns and learns topologically aware dynamics concurrently for each road segment. For spatio-temporal trajectory dynamics, we present TedFormer, a time-aware Transformer that incorporates temporal dynamics for each GPS location by integrating closed-form neural ordinary differential equations into the attention mechanism. This allows TedFormer to effectively handle irregularly sampled data. Extensive experiments on three real-world datasets demonstrate the superior performance of TedTrajRec. The code is publicly available at https://github.com/ysygMhdxw/TEDTrajRec/

Modeling route representation aims to obtain contextual representations of an entire route for various traffic-related tasks. In reality, spatial-temporal data often exhibits multi-scale characteristics, which are utilized by many studies to enhance their performance. However, there is still a lack of in-depth research on how to effectively incorporate the multi-scale spatial-temporal information into transformer structure to adequately model route representation. In this paper, we propose a novel hierarchical route representation framework called RouteMT, which effectively captures multi-scale spatial-temporal characteristics of routes and leverages a mixed-scale transformer architecture to fuse intra and interroute features. Experiments on real data confirm RouteMT’s superior performance and versatility.

Traffic speed prediction is vital for intelligent transportation systems. However, most existing methods focus on costly static sensors. In contrast, utilizing GPS devices from vehicles as mobile sensors offers a cost-effective means to gather dynamic traffic data. Despite the presence of historical trajectory data, mobile sensor-based traffic prediction remains under-explored. Existing methods often treat trajectories as substitutes for static sensors, missing the full utilization of the spatial-temporal signals within the complete trajectory set. To address this, we propose TrajHGT, a novel trajectory set empowered hypergraph transformer model that captures trafficrelated spatial-temporal features through adaptive attention and fusion mechanisms in both the trajectory hypergraph space and the road graph space. Real dataset experiments demonstrate the superiority of TrajHGT.

Adaptive traffic signal control plays a crucial role in enhancing the traffic situation in urban cities. Recently, reinforcement learning-based methods have demonstrated remarkable performance in addressing traffic signal control problems. However, the deployment of these methods in real-world environments is limited due to their lack of robustness. When errors occur during traffic data collection, their performance tends to deteriorate significantly. This paper addresses a prevalent issue where certain intersections, referred to as blinded intersections, cannot receive traffic data either due to hardware failures or the absence of traffic detectors. Existing adaptive traffic signal control methods fail to achieve satisfactory results in such scenarios as they are unable to learn effective policies for blinded intersections. Through theoretical analysis, we identify the primary reason behind the poor performance of existing methods as improper reward selection. To mitigate this issue, we propose a novel reward function called NOVO, which incorporates Number of Vehicles and Outflow, offering a correct optimization objective with low variance. These advantages significantly enhance the performance of reinforcement learning methods. Additionally, we introduce a new reinforcement learning model called BlindLight, which employs a dual model structure to learn Q-values for different types of intersections independently. This model design enhances the robustness of the system. Experimental results conducted on public datasets demonstrate the consistent performance improvement achieved by the theoretically supported reward function NOVO in existing methods with blinded intersections. Furthermore, BlindLight outperforms all state-of-the-art traffic signal control methods significantly.

Accurately estimating route travel time is crucial for intelligent transportation systems. Urban road networks and routes can be viewed from spatial and topological perspectives while existing works typically focus on one view and disregard important information from the other perspective. In this paper, we propose TTEFORMER, a novel travel time estimation model. It incorporates an alignment-enhanced spatial-topological aware dual transformer model to adaptively incorporate intra- and inter-view features in the route, guided by cross-view location alignment matrices with clear correspondences between locations in two views. Additionally, we propose a sparsity-aware dual-view traffic feature extraction module to effectively capture temporal traffic state changes. Compared to baseline models, TTEFORMER demonstrates improved performance on the MAPE and MAE metrics for Chengdu and Shanghai datasets, achieving improvements of 8.32%, 7.03%, 8.06% and 9.51% respectively, validating the effectiveness of TTEFORMER in travel time estimation.

GPS trajectories are the essential foundations for many trajectory-based applications. Most applications require a large number of high sample rate trajectories to achieve a good performance. However, many real-life trajectories are collected with low sample rate due to energy concern or other constraints. We study the task of trajectory recovery in this paper as a means to increase the sample rate of low sample trajectories. Most existing works on trajectory recovery follow a sequence-to-sequence diagram, with an encoder to encode a trajectory and a decoder to recover real GPS points in the trajectory. However, these works ignore the topology of road network and only use grid information or raw GPS points as input. Therefore, the encoder model is not able to capture rich spatial information of the GPS points along the trajectory, making the prediction less accurate and less spatial consistent. In this paper, we propose a road network enhanced transformer-based framework, namely RNTrajRec, for trajectory recovery. RNTrajRec first uses a graph model, namely GridGNN, to learn the embedding features of each road segment. It next develops a spatial-temporal transformer model, namely GPSFormer, to learn rich spatial and temporal features along with a Sub-Graph Generation module to capture the spatial features for each GPS point in the trajectory. It finally forwards the outputs of encoder model to a multi-task decoder model to recover the missing GPS points. Extensive experiments based on three large-scale real-life trajectory datasets confirm the effectiveness of our approach.

With widespread deployment of GPS devices, massive spatiotemporal trajectories became more accessible. This booming trend paved the solid data ground for researchers to discover the regularities or patterns of human mobility. However, there are still three challenges in semantic pattern extraction including semantic absence, semantic bias and semantic complexity. We invent and apply a novel data structure namely City Semantic Diagram to overcome above three challenges. First, our approach resolves semantic absence by exactly identifying semantic behaviours from raw trajectories. Second, the design of semantic purification helps us to detect semantic complexity from human mobility. Third, we avoid semantic bias using objective data source such as ubiquitous GPS trajectories.

Hamming space retrieval, allowing for retrieval within a fixed Hamming radius rather than scanning all instances linearly, has gained widespread attention for retrieving nearest neighbors at a fixed computational cost. Current models have focused only on shared-label correlations as the label-wise semantics while ignoring the potential multi-hop constraints, which are the unique constraints in Hamming space retrieval under multi-label conditions. Instances with multi-dimensional labels form a multi-hop correlation graph rather than several clusters in a single-label scenario. So there are potential distance constraints between dissimilar instances connected through multi-hop correlations. Existing models blindly expanding the dissimilar instances will break the multi-hop correlations and finally disrupt the hashing consistency of the shared-label instances. This paper first defines the multi-hop correlations to address these challenges with the multi-hop preserving strategy for dissimilar instances to help the Hamming distance converge to the expected range. Meanwhile, we introduce a Wasserstein-1-distance-based loss to reduce information loss while encoding compactly. We evaluate our proposed model on three commonly used datasets with extensive experiments to demonstrate that our model achieves significant improvements over existing methods.

Hashing plays an important role in the content-based retrieval of multimedia data. Existing methods focus on designing various joint-optimization strategies to preserve the similarity relationships between different modalities and improve the performance of cross-modal retrieval. However, when the intrinsic information of any modality is significantly insufficient compared with others, the final hash space will collapse to the trivial space due to the joint training. Compared with inter-modal semantic alignment, directly aligning the semantics of each modality with the label-wise semantics can obtain higher-quality common semantic spaces, and only a pair-wise alignment between each space can obtain a unified representation. Following this idea, we design a general hash generation framework for uni-modal embedding and directly align the hashing code from different modalities using a pair-wise loss, further improving the retrieval performance within the less-semantic modality. Within this framework, we introduce two optimizations to penalize dissimilar items. First, with a Gaussian distribution to describe the hashing semantic distribution, JS-divergence is introduced to keep the consistency of label-wise semantics and hashing similarity. Then the attention mechanism is used for hard-sample re-weighting to learn fine-grained distribution alignment further. We conduct extensive experiments on three public datasets to validate the enhancements of our work.

Modeling continuous-time dynamics on irregular time series is critical to account for data evolution and correlations that occur continuously. Traditional methods including recurrent neural networks or Transformer models leverage inductive bias via powerful neural architectures to capture complex patterns. However, due to their discrete characteristic, they have limitations in generalizing to continuous-time data paradigms. Though neural ordinary differential equations (Neural ODEs) and their variants have shown promising results in dealing with irregular time series, they often fail to capture the intricate correlations within these sequences. It is challenging yet demanding to concurrently model the relationship between input data points and capture the dynamic changes of the continuous-time system. To tackle this problem, we propose ContiFormer that extends the relation modeling of vanilla Transformer to the continuous-time domain, which explicitly incorporates the modeling abilities of continuous dynamics of Neural ODEs with the attention mechanism of Transformers. We mathematically characterize the expressive power of ContiFormer and illustrate that, by curated designs of function hypothesis, many Transformer variants specialized in irregular time series modeling can be covered as a special case of ContiFormer. A wide range of experiments on both synthetic and real-world datasets have illustrated the superior modeling capacities and prediction performance of ContiFormer on irregular time series data. The project link is https://seqml.github.io/contiformer/.

Searching spatial objects is a fundamental task in spatial services such as online maps. Traditional search methods are based on filtering conditions, burdening users to specify their requirements. This paper focuses on spatial search via examples. Particularly, the user can specify an example, which is a set of objects of interest, and the purpose is to find a list of results, each containing a set of objects with similar properties to the given example. We conducted a user study, showing that a search interface based on examples can effectively complement existing approaches. However, the existing example-based search is not scalable, hindering its applications to larger datasets. To address this challenge, we propose two new algorithms, namely HSP and LORA, to efficiently answer example-based spatial queries. HSP is an algorithm based on a hierarchical partitioning of the search space, and it achieves up to 20 times faster than the state-of-the-art algorithm. LORA further improves the efficiency, running up to 5000 times faster than the state-of-the-art algorithm. We present a systematic evaluation to demonstrate the efficacy of our algorithms.

How to coordinate the communication among intersections effectively in real complex traffic scenarios with multi-intersection is challenging. Existing approaches only enable the communication in a heuristic manner without considering the content/importance of information to be shared. In this paper, we propose a universal communication form UniComm between intersections. UniComm embeds massive observations collected at one agent into crucial predictions of their impact on its neighbors, which improves the communication efficiency and is universal across existing methods. We also propose a concise network UniLight to make full use of communications enabled by UniComm. Experimental results on real datasets demonstrate that UniComm universally improves the performance of existing state-of-the-art methods, and UniLight significantly outperforms existing methods on a wide range of traffic situations. Source codes are available at https://github.com/zyr17/UniLight.

Cross-modal hashing is an important approach for multimodal data management and application. Existing unsupervised cross-modal hashing algorithms mainly rely on data features in pre-trained models to mine their similarity relationships. However, their optimization objectives are based on the static metric between the original uni-modal features, without further exploring data correlations during the training. In addition, most of them mainly focus on association mining and alignment among pairwise instances in continuous space but ignore the latent structural correlations contained in the semantic hashing space. In this paper, we propose an unsupervised hash learning framework ASSPH to solve the above problems. Firstly, we propose an adaptive learning scheme, with limited data and training batches, to enrich semantic correlations of unlabeled instances during the training process and meanwhile to ensure a smooth convergence of the training process. Secondly, we present an asymmetric structural semantic representation learning scheme. We introduce structural semantic metrics based on graph adjacency relations and meanwhile align the inter- and intra-modal semantics in the hash space with an asymmetric binary optimization process. Finally, we conduct extensive experiments to validate the enhancements of our work in comparison with existing works.

With widespread deployment of GPS devices, massive spatiotemporal trajectories became more accessible. This booming trend paved the solid data ground for researchers to discover the regularities or patterns of human mobility. However, there are still three challenges in semantic pattern extraction including semantic absence, semantic bias and semantic complexity. In this paper, we invent and apply a novel data structure namelyCity Semantic Diagramto overcome above three challenges. First, our approach resolves semantic absence by exactly identifying semantic behaviours from raw trajectories. Second, the design of semantic purification helps us to detect semantic complexity from human mobility. Third, we avoid semantic bias using objective data source such as ubiquitous GPS trajectories. Comprehensive and massive experiments have been conducted based on real taxi trajectories and points of interest in Shanghai. Compared with existing approaches,City Semantic Diagramis able to discover fine-grained semantic patterns effectively and accurately.

Traffic signal control has achieved significant success with the development of reinforcement learning. However, existing works mainly focus on intersections with normal lanes with fixed outgoing directions. It is noticed that some intersections actually implement dynamic lanes, in addition to normal lanes, to adjust the outgoing directions dynamically. Existing methods fail to coordinate the control of traffic signal and that of dynamic lanes effectively. In addition, they lack proper structures and learning algorithms to make full use of traffic flow prediction, which is essential to set the proper directions for dynamic lanes. Motivated by the ineffectiveness of existing approaches when controlling the traffic signal and dynamic lanes simultaneously, we propose a new method, namely MT-GAD, in this paper. It uses a group attention structure to reduce the number of required parameters and to achieve a better generalizability, and uses multi-timescale model training to learn proper strategy that could best control both the traffic signal and the dynamic lanes. The experiments on real datasets demonstrate that MT-GAD outperforms existing approaches significantly.

Automatic map extraction is of great importance to urban computing and location-based services. Aerial image and GPS trajectory data refer to two different data sources that could be leveraged to generate the map, although they carry different types of information. Most previous works on data fusion between aerial images and data from auxiliary sensors do not fully utilize the information of both modalities and hence suffer from the issue of information loss. We propose a deep convolutional neural network called DeepDualMapper which fuses the aerial image and trajectory data in a more seamless manner to extract the digital map. We design a gated fusion module to explicitly control the information flows from both modalities in a complementary-aware manner. Moreover, we propose a novel densely supervised refinement decoder to generate the prediction in a coarse-to-fine way. Our comprehensive experiments demonstrate that DeepDualMapper can fuse the information of images and trajectories much more effectively than existing approaches, and is able to generate maps with higher accuracy.

Trajectory similarity computation is a core problem in the field of trajectory data queries. However, the high time complexity of calculating the trajectory similarity has always been a bottleneck in real-world applications. Learning-based methods can map trajectories into a uniform embedding space to calculate the similarity of two trajectories with embeddings in constant time. In this paper, we propose a novel trajectory representation learning framework Traj2SimVec that performs scalable and robust trajectory similarity computation. We use a simple and fast trajectory simplification and indexing approach to obtain triplet training samples efficiently. We make the framework more robust via taking full use of the sub-trajectory similarity information as auxiliary supervision. Furthermore, the framework supports the point matching query by modeling the optimal matching relationship of trajectory points under different distance metrics. The comprehensive experiments on real-world datasets demonstrate that our model substantially outperforms all existing approaches.

We propose the Unified Visual-Semantic Embeddings (Unified VSE) for learning a joint space of visual representation and textual semantics. The model unifies the embeddings of concepts at different levels: objects, attributes, relations, and full scenes. We view the sentential semantics as a combination of different semantic components such as objects and relations; their embeddings are aligned with different image regions. A contrastive learning approach is proposed for the effective learning of this fine-grained alignment from only image-caption pairs. We also present a simple yet effective approach that enforces the coverage of caption embeddings on the semantic components that appear in the sentence. We demonstrate that the Unified VSE outperforms baselines on cross-modal retrieval tasks; the enforcement of the semantic coverage improves the model's robustness in defending text-domain adversarial attacks. Moreover, our model empowers the use of visual cues to accurately resolve word dependencies in novel sentences.

Spatio-temporal trajectory classification is a fundamental problem for location-based services with many real-world applications such as travel mode classification, animal mobility detection, and location recommendation. In the literature, many approaches have been proposed to solve this classification task including deep learning models like LSTM recently for sequence classification. However, these approaches fail to consider both spatial and temporal interval information simultaneously, but share some common drawbacks: omitting either the spatial information or the temporal interval information out. Some models like Time-LSTM, have been proposed to handle the temporal interval information for spatio-temporal trajectories, but they do not take into account the spatial information. Note that, considering both spatial and temporal interval information is crucial for spatio-temporal data mining in order not to miss any spatio-temporal pattern. In this study, we propose a trajectory classifier called Spatio-Temporal GRU to better model the spatio-temporal correlations and irregular temporal intervals prevalently present in spatio-temporal trajectories. We introduce a novel segmented convolutional weight mechanism to capture short-term local spatial correlations in trajectories and propose an additional temporal gate to control the information flow related to the temporal interval information. Performance evaluation demonstrates that our proposed model outperforms popular deep learning approaches for the travel model classification problem.

Estimating the travel time of a path is of great importance to smart urban mobility. Existing approaches are either based on estimating the time cost of each road segment which are not able to capture many cross-segment complex factors, or designed heuristically in a non-learning-based way which fail to leverage the natural abundant temporal labels of the data, i.e., the time stamp of each trajectory point. In this paper, we leverage on new development of deep neural networks and propose a novel auxiliary supervision model, namely DeepTravel, that can automatically and effectively extract different features, as well as make full use of the temporal labels of the trajectory data. We have conducted comprehensive experiments on real datasets to demonstrate the out-performance of DeepTravel over existing approaches.

Trajectory outlier detection is a fundamental building block for many location-based service (LBS) applications, with a large application base. We dedicate this paper on detecting the outliers from vehicle trajectories efficiently and effectively. In addition, we want our solution to be able to issue an alarm early when an outlier trajectory is only partially observed (i.e., the trajectory has not yet reached the destination). Most existing works study the problem on general Euclidean trajectories and require accesses to the historical trajectory database or computations on the distance metric that are very expensive. Furthermore, few of existing works consider some specific characteristics of vehicles trajectories (e.g., their movements are constrained by the underlying road networks), and majority of them require the input of complete trajectories. Motivated by this, we propose a vehicle outlier detection approach namely DB-TOD which is based on probabilistic model via modeling the driving behavior/preferences from the set of historical trajectories. We design outlier detection algorithms on both complete trajectory and partial one. Our probabilistic model-based approach makes detecting trajectory outlier extremely efficient while preserving the effectiveness, contributed by the relatively accurate model on driving behavior. We conduct comprehensive experiments using real datasets and the results justify both effectiveness and efficiency of our approach.

Modeling trajectory data is a building block for many smart-mobility initiatives. Existing approaches apply shallow models such as Markov chain and inverse reinforcement learning to model trajectories, which cannot capture the long-term dependencies. On the other hand, deep models such as Recurrent Neural Network (RNN) have demonstrated their strength of modeling variable length sequences. However, directly adopting RNN to model trajectories is not appropriate because of the unique topological constraints faced by trajectories. Motivated by these findings, we design two RNN-based models which can make full advantage of the strength of RNN to capture variable length sequence and meanwhile to address the constraints of topological structure on trajectory modeling. Our experimental study based on real taxi trajectory datasets shows that both of our approaches largely outperform the existing approaches.

More and more advanced technologies have become available to collect and integrate an unprecedented amount of data from multiple sources, including GPS trajectories about the traces of moving objects. Given the fact that GPS trajectories are vast in size while the information carried by the trajectories could be redundant, we focus on trajectory compression in this article. As a systematic solution, we propose a comprehensive framework, namely, COMPRESS ( Comprehensive Paralleled Road-Network-Based Trajectory Compression ), to compress GPS trajectory data in an urban road network. In the preprocessing step, COMPRESS decomposes trajectories into spatial paths and temporal sequences, with a thorough justification for trajectory decomposition. In the compression step, COMPRESS performs spatial compression on spatial paths, and temporal compression on temporal sequences in parallel. It introduces two alternative algorithms with different strengths for lossless spatial compression and designs lossy but error-bounded algorithms for temporal compression. It also presents query processing algorithms to support error-bounded location-based queries on compressed trajectories without full decompression. All algorithms under COMPRESS are efficient and have the time complexity of O (| T |), where | T | is the size of the input trajectory T . We have also conducted a comprehensive experimental study to demonstrate the effectiveness of COMPRESS, whose compression ratio is significantly better than related approaches.

Locating only one GPS position to a road segment accurately is crucial to many location-based services such as mobile taxi-hailing service, geo-tagging, POI check-in, etc. This problem is challenging because of errors including the GPS errors and the digital map errors (misalignment and the same representation of bidirectional roads) and a lack of context information. To the best of our knowledge, no existing work studies this problem directly and the work to reduce GPS signal errors by considering hardware aspect is the most relevant. Consequently, this work is the first attempt to solve the problem of locating one GPS position to a road segment. We study the problem in a data-driven view to make this process ubiquitous by proposing a tractable, efficient and robust generative model. In addition, we extend our solution to the real application scenario, i.e., taxi-hailing service, and propose an approach to further improve the result accuracy by considering destination information. We use the real taxi GPS data to evaluate our approach. The results show that our approach outperforms all the existing approaches significantly while maintaining robustness, and it can achieve an accuracy as high as 90% in some situations.

Vehicle trajectories are one of the most important data in location-based services. The quality of trajectories directly affects the services. However, in the real applications, trajectory data are not always sampled densely. In this paper, we study the problem of recovering the entire route between two distant consecutive locations in a trajectory. Most existing works solve the problem without using those informative historical data or solve it in an empirical way. We claim that a data-driven and probabilistic approach is actually more suitable as long as data sparsity can be well handled. We propose a novel route recovery system in a fully probabilistic way which incorporates both temporal and spatial dynamics and addresses all the data sparsity problem introduced by the probabilistic method. It outperforms the existing works with a high accuracy (over 80%) and shows a strong robustness even when the length of routes to be recovered is very long (about 30 road segments) or the data is very sparse.

Map data are widely used in mobile services, but most maps might not be complete. Updating the map automatically is an important problem because road networks are frequently changed with the development of the city. This paper studies the problem of recovering missing road segments via GPS trajectories, especially low sampled data. Our approach takes the GPS noise into consideration and proposes an effective self-adaptive algorithm. Besides, we propose theoretical models behind all the important parameters to enable self-adaptive parameter setting. To the best of our knowledge, this is the first work that addresses the parameter setting issue successfully to make sure our approach is free of parameter-tuning. In addition, we also propose a quantitative evaluation method for map updating problem. The result shows our algorithm has a much better performance than the existing approaches.

The accuracy and completeness of a digital map plays a critical role in determining the quality of most location-based services. Unfortunately, road networks change frequently. Consequently, we study the issue of automatic map update in this paper. We propose a system called COBWEB which takes all the unmatched trajectories as input and generates the missing road segments with both the geometry properties and topology features well preserved. We conduct a comprehensive experimental study via real trajectory data generated by roughly 15,000 taxis in Singapore within a 5-month period. Compared with existing work, COBWEB demonstrates a better and more stable performance and a stronger resilience to various sampling rates and data sizes.

Spatial queries such as range query and kNN query in road networks have received a growing number of attention in real life. Considering the large population of the users and the high overhead of network distance computation, it is extremely important to guarantee the efficiency and scalability of query processing. Motivated by the scalable and secure properties of wireless broadcast model, this paper presents an air index called Network Partition Index (NPI) to support efficient spatial query processing in road networks via wireless broadcast. The main idea is to partition the road network into a number of regions and then build the index to carry some pre-computation information of each region. We also propose multiple client-side algorithms to facilitate the processing of different spatial queries such as kNN query, range query and CNN query. A comprehensive experimental study has been conducted to demonstrate the efficiency of our scheme.

Many developing countries are suffering from air pollution, especially the Particulate Matter with diameter of 2.5 micrometers or less (PM2.5). While quite a few air quality monitoring stations have been built by governments in a city's public areas, the indoor PM2.5 has not yet been monitored and dealt with effectively. Though many office buildings have an HVAC (heating, ventilation, and air conditioning) system, PM2.5 is not considered as a factor when the system circulates fresh air from outdoors. This paper introduces a real system that we have deployed in the offices of four Microsoft campuses in China. This system instantly monitors indoor air quality on different floors of a building (including office areas, gyms, garages, and restaurants), enabling Microsoft employees to enquire the air quality of a place by using a mobile phone or checking a website. The information can guide a user's decision making, e.g., finding the right time to work out in the gym or turn on individual air filters in her own office. Through analyzing the indoor and outdoor air quality data collected over a long period, our system can even offer actionable and energy-efficient suggestion to HVAC systems, e.g., automatically turning on the system only a few hours earlier than usual if it is a heavily polluted day, or identifying the filters in HVAC system that should be renewed.

Location data becomes more and more important. In this paper, we focus on the trajectory data, and propose a new framework, namely PRESS ( Paralleled Road-Network-Based Trajectory Compression ), to effectively compress trajectory data under road network constraints. Different from existing work, PRESS proposes a novel representation for trajectories to separate the spatial representation of a trajectory from the temporal representation, and proposes a Hybrid Spatial Compression (HSC) algorithm and error Bounded Temporal Compression (BTC) algorithm to compress the spatial and temporal information of trajectories respectively. PRESS also supports common spatial-temporal queries without fully decompressing the data. Through an extensive experimental study on real trajectory dataset, PRESS significantly outperforms existing approaches in terms of saving storage cost of trajectory data with bounded errors.

XML data broadcast is an efficient way to disseminate semistructured information in wireless mobile environments. In this paper, we propose a novel two-tier index structure to facilitate the access of XML document in an on-demand broadcast system. It provides the clients with an overall image of all the XML documents available at the server side and hence enables the clients to locate complete result sets accordingly. A pruning strategy is developed to cut down the index size and a two-tier structure is proposed to further remove any redundant information. In addition, two index distribution strategies, namely naive distribution and partial distribution, have been designed to interleave the index information with the XML documents in the wireless channels. Theoretical analysis and simulation experiments are also put forward to show the benefits of our indexing methods.

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.

The ACM SIGSPATIAL Cup 2013 is about geo-fencing, a problem of determining whether sampled location points fall inside or within a certain distance from virtual perimeters for real-world geographic areas. This paper describes one of the winning submissions of the competition. The approach applies two novel techniques, namely Trajectory Partitioning (TP) and Boundary Simplification (BS). TP partitions the movement trajectory of an object into segments and processes the points within the same segment simultaneously. BS simplifies the polygons thus accelerates the geo-fencing process.

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.

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.

In the environment of Mobile Ad-hoc Networks (MANETs), devices can collaborate under the service-oriented architecture (SOA). However, as MANETs are infrastructure-less, devices may move randomly and join and leave the network at any time which leads to a permanently changing topology of the network. What adds to the unpredictability of the network is the limited resource of the nodes, including battery power, processing capacity and memory limit which are common problems for mobile devices. All these features pose a potential risk of failure to the process of service execution. Therefore, service recovery is indispensable to guarantee the success rate when the service execution plan cannot be conducted as the user expects. In this paper, we proposed a novel strategy of service execution and service recovery. By employing additional control messages, the point of fault can be quickly acknowledge by the closest device which will then take the responsibility of service recovery. Using the distributed service cache which is maintained by each node in the network, a back-up service execution plan will be elected promptly. The simulation shows that our strategy can effectively reduce the response time and increase the success rate of service execution.

Wireless broadcast provides a scalable and secure spatial data dissemination approach for geographical applications in wireless mobile environments. Among various location-based services, the shortest path query on road networks is one of the most popular and essential services in our daily life. In this paper, we propose an energy-efficient scheme for on air shortest path query processing on road networks, which leverages an elaborate air index called BagIndex based upon the novel Hilbert-based heuristic tree decomposition for the road networks. Experimental results show that the proposed approach incurs less energy consumption on both communication and computation than the previous schemes.

Aggregate nearest neighbor (ANN) query returns a common interesting data object that minimizes an aggregate distance for multiple query points. In this paper, we propose a novel approach to efficiently process ANN queries in road networks. This approach includes two processes: initializing process and pruning process, which are both based on computing kNN of query points in network Voronoi diagram. Experimental results show that our approach outperforms existing approaches on both response time and page accesses.

XML data broadcast is an efficient way to disseminate semi-structured information in wireless mobile environments. Air indexing is the common method to improve the access time, and reduce the energy consumption in a broadcast system. In this paper, we propose a novel two-tier air indexing method that provides an overall picture of the document set in the server which is necessary for XML data retrieving in on-demand mode. The efficiency of our indexing method is contributed by two distinct advantages. First, the proposed pruning technique and the two-tier structure significantly reduce the index size. Second, the two-tier structure enables efficient access protocol at the client which can further reduce the tuning time during the index look up. Simulation experiments show the benefits of our indexing methods.

Data broadcast is an efficient way of data dissemination in the wireless mobile environment. Recently, many researchers pay attention to broadcast scheduling for multi-item queries which is a more practical problem in this field. However, only a few works discuss the scheduling problem in on-demand environment. In this paper, we propose a heuristic approach called LRL for the broadcast scheduling problem. Performance analysis is put forward and simulation experiments show that our approaches achieve a comparative improvement compared with the existing methods.

Wireless sensor networks have emerged recently as an effective way of gathering useful information from areas of interest. Prolonging the network lifetime has become the primary concern in data gathering due to the limited battery power of sensors. An underlying assumption of most existing work is that all the sensors are working simultaneously during the whole process of data gathering. In this paper, we introduce a new definition of the network lifetime in view of the coverage condition, and then investigate the coverage-based maximum lifetime data gathering problem theoretically. Two critical issues are how to selectively organize part of sensors to work and how to execute routing in a single working set. Considering both of these two problems together, we propose the algorithm CODAG. CODAG employs the tree structured routing scheme and enables the routing effects of two different sets theoretically comparable. Based on the maximal increased weight in the routing tree, it divides all the sensors into disjoint cover sets without redundant ones, which in turn leads to the better routing effect. Experimental results show that our algorithm has the good performance for prolonging the lifetime of the whole sensor network.

In name and in practice, the World-Wide Web (hereafter Web) is used around the World beyond English-speaking areas. This creates a tremendous need to internationalize standard terminology used in the technologies that make the Web possible. Existing efforts on XML internationalization (i18n) and localization (i10n) have focused on the content of XML documents instead of the terms used in markup (annotations) such as elements and attributes. The SGML standard ISO 8879 supports the use of Unicode (ISO 10646) throughout a document, including markups. However, most elements and attributes of XML documents are still defined in English, thereby limiting their use among non-English speakers. This paper presents an XSLT-based method that can completely localize the markup of XML documents into different natural languages. We also describe how the proposed technique can be applied to translation problems in programming (e.g. C and Java) or documentation (e.g. LATEX or other formatting languages) so that a program or a document can be converted to and from an XML format. Copyright © 2004 John Wiley & Sons, Ltd.

In mobile wireless systems data on air can be accessed by a large number of mobile users. Many of these applications such as wireless internets and traffic information systems are pull-based, that is, they respond to on-demand user requests. In this paper, we study the scheduling problems of on-demand broadcast environments. Traditionally, the response time of the requests has been used as a performance measure. In this paper we consider the performance as the average cost of request composed of three kinds of costs—access time cost, tuning time cost, and cost of handling failure request. Our main contribution is a self-adaptive scheduling algorithm named LDFC, which computes the delay cost of data item as the priority for broadcast. It performs well compared with some previous algorithms in this context.