Emergency Medical Services (EMS) are critical for saving lives. In highly populated cities, where millions of emergencies are reported each year, delays in ambulance response and inefficient hospital routing can result in increased mortality and adverse patient outcomes. Traditional forecasting systems lack the spatial resolution and capacity to integrate essential factors like regional demand, hospital facility demand, and weather dynamics. To overcome these limitations, this paper presents a forecasting system that predicts EMS demand at ZIP-code granularity using spatio-temporal deep learning methods and a hospital routing algorithm. Utilizing a decade-long real-world EMS incident dataset, we demonstrate how the incident data patterns impact forecasting, hospital routing, and how these insights can be integrated into intelligent transportation and public health systems. Github: https://github.com/saideepthi112/EMS-Demand-Prediction-Project

In the dynamic and evolving field of computer vision, action recognition has become a key focus, especially with the advent of sophisticated methodologies like Convolutional Neural Networks (CNNs), Convolutional 3D, Transformer and spatial-temporal feature fusion. These technologies have shown promising results on well-established benchmarks but face unique challenges in real-world applications, particularly in sports analysis, where the precise decomposition of activities and the distinction of subtly different actions are crucial. Existing datasets like UCF101, HMDB51, and Kinetics have offered a diverse range of video data for various scenarios. However, there’s an increasing need for fine-grained video datasets that capture detailed categorizations and nuances within broader action categories. In this paper, we introduce the VideoBadminton dataset, which is derived from high-quality badminton footage. Through an exhaustive evaluation of leading methodologies on this dataset, this study aims to advance the field of action recognition, particularly in badminton sports. The introduction of VideoBadminton could not only serve for badminton action recognition but also provide a dataset for recognizing fine-grained actions. The insights gained from these evaluations are expected to catalyze further research in action comprehension, especially within sports contexts.

Explaining black-box models is fundamental to gaining trust and deploying these models in real applications. As existing explanation methods have been shown to lack robustness against adversarial perturbations, there has been a growing interest in generating robust explanations. However, existing works resort to empirical defense strategies and these heuristic methods fail against powerful adversaries. In this paper, we certify the robustness of explanations motivated by the success of randomized smoothing. Specifically, we compute a tight radius in which the robustness of the explanation is certified. While a challenge is how to formulate the robustness of the explanation mathematically, we quantize the explanation into discrete spaces to mimic classification in randomized smoothing. To address the high computational cost of randomized smoothing, we introduce randomized gradient smoothing. Also, we explore the robustness of the semantic explanation by certifying the robustness of capsules. In the experiment, we demonstrate the effectiveness of our method on benchmark datasets from the perspectives of post-hoc explanation and semantic explanation respectively. Our work is a promising step towards filling the gap between the theoretical robustness bound and empirical explanations. Our code has been released at https://github.com/NKUShaw/CertifiedExplanation.

Accurate short-term precipitation prediction at a high spatial resolution is crucial for effective urban water management, flooding warning, and mitigation. However, conventional numerical weather models usually face the challenge of systematic errors and spatiotemporal biases due to an inadequate understanding of many processes and unrealistic parameterizations. In recent years, deep learning techniques have gained popularity as a tool in precipitation forecasting and risk pre-warning. To support deep learning for precipitation forecasting and flooding warning, this paper introduces a large-scale multimodal Geo dataset. This dataset incorporates spatially connected features and real-world climate data, enabling the prediction of extreme precipitations. The dataset comprises Multi-Radar/Multi-Sensor System (MRMS), High-Resolution Rapid Refresh (HRRR), Geostationary Satellite Server (GOES) data, and local hydrological data from the United States Geological Survey (USGS), providing a diverse array of information sources. The compiling of multi-source data within the proposed multimodal Geo scope can improve prediction accuracy over uni-modal data and shows high accuracy in predicting heavy rain when integrating Transformer, which offers the opportunity for more efficient urban water management and improved disaster response strategies. By providing a comprehensive view of environmental conditions, this dataset enables a deeper understanding of precipitation patterns, facilitating effective mitigation efforts.

Predicting traffic accident hotspots is crucial for ensuring public safety, improving transport planning, and reducing transportation costs. Traditional deep learning models, such as Transformers and LSTMs, have been successful in this field but fail to integrate critical attributes essential for accurate prediction. To address these limitations, we propose utilizing a Temporal Convolutional Network (TCN), which efficiently learns spatial, temporal, and other external factors integral to accident hotspot prediction. Our proposed TCN architecture 1 demonstrate superior performance over state-of-the-art methods, offering valuable insights for proactive accident mitigation.

Trip recommendation has drawn considerable attention over the past decade. In trip recommendation, a sequence of point-of-interests (POIs) are recommended for a given query which includes an origin and a destination. Recently the emergence of the attention mechanism and many attention-incorporated models have achieved great success in various fields. Trip recommendation problems demonstrate similar characteristics that can potentially benefit from the attention mechanism. However, applying the attention mechanism for trip recommendation is non-trivial. We are motivated to answer the following two research questions. (1) How can we learn trip representation effectively without labels? Unlike most of the natural language processing tasks, there are no ground-truth labels available for trip recommendation. (2) How can we learn trip representation effectively without handcrafting negative samples? In this paper, we cast the trip representation learning into a natural language processing (NLP) task. We propose BERT-Trip, a self-supervised contrast learning framework, to learn effective and scalable trip representation in support of time-sensitive and user-personalized trip recommendation. BERT-Trip builds on a Siamese network to maximize the similarity between the augmentations of trips with BERT as the backbone encoder. We utilize the masking strategy for generating augmented views (positive sample pairs) of trips in the Siamese network and employ the stop-gradient on one side of the Siamese network to eliminate the need to use any negative sample pairs or momentum encoders. Extensive experiments on real-world datasets demonstrate that BERT-Trip consistently outperformed the state-of-the-art methods in terms of all effectiveness metrics. Compared with the state-of-the-art methods, BERT-Trip is able to yield up to 24 percent and 40 percent increases in F1score on the Flickr and the Weeplaces datasets, respectively. A rigorous performance evaluation of BERT-Trip on scalability up to 12800 POIs is also provided.

Exploring drug-target interaction remains one of the essential tasks in drug discovery, and it is critical to gain a thorough understanding of the biological process and disease mechanisms. Despite recent successes in the application of machine learning approaches, drug-target interaction studies are still largely under-explored due to significant challenges in modeling different types of representations and capturing the inherent correlation between targets and drugs from low-level representations. What is more, the length of the target protein sequences and the complexity of the drug-target binding complex make the problem hard to handle. In this work, we focus on increasing the generalizability and interpretability of the drug-target prediction models and propose an Extrinsic-Intrinsic Representation learning model (EIR) intended to discover the inner correlation between target proteins and drugs on both the extrinsic and intrinsic levels. Our experimental results show that EIR makes more accurate predictions than the state-of-the-art method in both drug-target affinity prediction and drug-target interface prediction tasks and demonstrate the potential of the structural-free method for drug discovery.

Protecting the privacy of users is one of the most important issues in recommender systems, where new items, e.g., books, movies, and friends in online social networking service/sites, are recommended to target users. To identify recommended items, encryption-based privacy-preserving collaborative filtering is widely used to generate recommendations. However, existing solutions are either slow or not scalable. To tackle this issue, in this paper, we first propose a privacy-preserving user-based CF protocol using the BGV fully homomorphic encryption scheme, which is named BGV-CF. By reducing interactions and the amount of communication traffic among users and recommendation servers, the proposed BGV-CF protocol significantly facilitates the recommendation process. Then, we propose an optimized BGV-CF (OBGV-CF) protocol where some computations are offloaded to users during the recommendation process. The security of the proposed schemes is qualitatively analyzed and quantitative analyses of the computation and communication costs are performed. In addition, provable security analysis using random oracles is provided. The BGV-CF and OBGV-CF protocols are implemented using C++, and testbeds using the MovieLens dataset are conducted. Experimental results demonstrate that the proposed BGV-CF and OBGV-CF successfully achieve their design goals.

Skyline queries have drawn great interest and been widely used in various application domains including multi-criteria decision making, search pruning, and personalized recommendation systems. Given multiple criteria, skyline queries return objects that are not dominated by any other objects. As an extension of traditional skyline queries, probabilistic skyline queries aim to cope with uncertain datasets. This paper presents a novel MapReduce-based framework, ProbSky, in support of fast parallel evaluation of probabilistic skyline queries on large high-dimensional data. ProbSky efficiently evaluates exact p-skyline queries on large uncertain data without compromising the quality of query results. From the theoretical point of view, we formally prove two pruning lemmas integrated with ProbSky to strengthen the early pruning capacity. ProbSky builds on top of three optimization techniques, namely, dominant instance pruning, grid-based partitioning, and pivot point-based acceleration. Extensive experiments on both real and synthetic datasets unveil that compared to the state-of-the-art, ProbSky speeds up the evaluation of exact p-skyline queries on large high-dimensional data by at least one order of magnitude in most cases. Our experimental results also validate that by balancing the memory consumption and execution time among machines, ProbSky is adroit at curbing the bottleneck effect that causes severe system performance deterioration.

Graph Neural Networks (GNNs) have shown promising performance in many applications, yet remain extremely difficult to train over large-scale graph datasets. Existing weight pruning techniques can prune out the layer weights; however, they cannot fully address the high computation complexity of GNN inference, caused by large graph size and complicated node connections. In this paper, we propose an Iterative Gradient Rank Pruning (IGRP) algorithm to find graph lottery tickets (GLT) of GNNs where each GLT includes a pruned adjacency matrix and a sub-network. Our IGRP can avoid layer collapse and the winning ticket achieves Maximal critical compression. We evaluate the proposed method on small-scale (Cora and Citeseer), medium-scale (PubMed and Wiki-CS), and large-scale (Ogbn-ArXiv and Ogbn-Products) graph datasets. We demonstrate that both Single-shot and Multi-shot of IGRP outperform the state-of-the-art unified GNN sparsification (UGS) framework on node classification. The source code can be found in https://github.com/poweiharn/IGRP_GNN.

The location-based alert system plays a primary factor on determining who is at risk during an emergency, such as a war zone in Ukraine. While users are willing to reveal their locations in exchange for timely alert in those situations, there is no guarantee that their private information does not fall into the wrong hands. For example, a soldier may be killed if his movement pattern is known by the enemy. One resolution to this issue is to encrypt the location information by trusted authority public key before it is transmitted. This approach provides location privacy and allows decryption only when the recipient’s location satisfies a certain predicate. However, the encryption itself may still be compromised if the location encoding is leaked. In this paper, we propose a Hilbert Curve Encoding which encrypts the user’s message along with her locations for private processing with the trusted authority. We further propose a hybrid HNGM−NEncoding which combines the Hilbert Curve Encoding and Gray Encoding. HNGM−Nhas the proprieties of a Hilbert Curve Encoding in its identifier and a Hamming distance of 1 between neighboring cells in a subgrid. As a consequence, the proposed HNGM−Nis less likely to leak neighboring cell identifier than Gray Encoding under random guessing attacks. Extensive experiment results show that our encoding methods are better than Hierarchical Encoding and comparable to Gray Encoding in terms of user response time, token remaining percentage, and execution time.

Query optimizers in Relational Database Management Systems (RDBMS) rely on the approximations of data distributions of attributes, which are used for cardinality-based decisions like selectivity of a predicate or finding the right join order of a multiway join in a SQL query. The commercial databases try to reach best possible approximations of data distribution using compressed histograms. The state of the art in measurement of quality of a histogram is the q-error. However, one of the shortcomings of the measurement of quality of the histograms using q-error is that it pivots the entire quality on the worst case or the infinity norm of the multiplicative errors of the estimations. This may not be symbolic of the workload or the overall range of errors that would be representative of the system. In this paper, we propose a dynamic programming algorithm to achieve an optimal histogram structure by keeping the overall multiplicative errors low. We propose a one pass linear regression on the step function and apply dynamic programming methods to achieve an optimal histogram structure that optimizes the pair (slope β and intercept α). The algorithm achieves lower slope and intercept of the resultant regression on the sorted order of multiplicative errors, thus reducing the overall estimation errors for the system. We refer to this pair as the Q-Regression of a histogram. We then introduce the metric, QRegrArea as a new means to better quantify the cumulative distribution of errors for a given histogram. We provide the experimental validation of the proposed methods against the state-of the-art models in the literature and industry.

The study of protein-ligand interaction is critical for gaining a thorough understanding of biological processes and uncovering disease mechanisms. This exciting topic has attracted much interest. Accurate and reliable prediction of the protein-ligand interactions can be challenging because the model requires successful transformation and creation of the computer interpretable representations of both protein and ligand information. Despite the recent successes in the application of the convolution neural network and graph neural network-based approaches, they remain largely under-explored due to the significant challenges in modeling the complex representations and capturing the inherent correlation between protein and ligand from low-level representations. Several challenges include: 1) Structural-free protein representation learning model is needed to successfully discover the inner correlation between protein and ligand. 2) Limited open literature to date has focused on the generalizability and interpretability for the protein-ligand interface prediction. 3) The length of the protein sequences and the complexity of the protein-ligand binding complex make the problem hard to handle. To address these problems, we propose an end-to-end model framework APIP that could learn effective representations across compound atoms and protein residues for protein-ligand interface prediction. Our experimental results show that APIP makes more accurate predictions than the state-of-the-art method in this task and demonstrate the potential of the attention-based method for drug discovery.

Context has been recognized as an important factor to consider in personalized recommender systems. Particularly in location-based services (LBSs), a fundamental task is to recommend to a mobile user where he/she could be interested to visit next at the right time. Additionally, location-based social networks (LBSNs) allow users to share location-embedded information with friends who often co-occur in the same or nearby points-of-interest (POIs) or share similar POI visiting histories, due to the social homophily theory and Tobler's first law of geography. So, both the time information and LBSN friendship relations should be utilized for POI recommendation. Tensor completion has recently gained some attention in time-aware recommender systems. The problem decomposes a user-item-time tensor into low-rank embedding matrices of users, items and times using its observed entries, so that the underlying low-rank subspace structure can be tracked to fill the missing entries for time-aware recommendation. However, these tensor completion methods ignore the social-spatial context information available in LBSNs, which is important for POI recommendation since people tend to share their preferences with their friends, and near things are more related than distant things. In this paper, we utilize the side information of social networks and POI locations to enhance the tensor completion model paradigm for more effective time-aware POI recommendation. Specifically, we propose a regularization loss head based on a novel social Hausdorff distance function to optimize the reconstructed tensor. We also quantify the popularity of different POIs with location entropy to prevent very popular POIs from being over-represented hence suppressing the appearance of other more diverse POIs. To address the sensitivity of negative sampling, we train the model on the whole data by treating all unlabeled entries in the observed tensor as negative, and rewriting the loss function in a smart way to reduce the computational cost. Through extensive experiments on real datasets, we demonstrate the superiority of our model over state-of-the-art tensor completion methods.

In this paper, we propose privacy-preserving user-based CF protocols using the BGV fully homomorphic encryption scheme, named BGV-CF and optimized BGV-CF (OBGV-CF), in order to protect privacy of users in recommender systems. The proposed schemes are implemented by C++, and testbeds using the MovieLens dataset demonstrate that the proposed protocols successfully achieve their design goals.

By predicting the air pollutant concentration, people can take precautions to avoid overexposure to air pollutants. Consequently, accurate$\mathbf{PM}_{2.5}$prediction becomes more important. In this paper, we propose a$\mathbf{PM}_{2.5}$prediction system, which utilizes the dataset from EdiGreen Airbox and Taiwan EPA. Our$\mathbf{PM}_{2.5}$prediction system is composed of four parts: data collection, data preprocessing, prediction model construction, and Line platform. To assess the performance of the model prediction, the daily average error and the hourly average accuracy for the duration of a week are calculated. The experimental results show that LSTM based on K- means has the best performance among all methods. Therefore, LSTM based on K-means is chosen to provide real-time$\mathbf{PM}_{2.5}$prediction through the Linebot.

Depression is one of the leading factors in global disability and a top driver for suicides. Studies have shown that depression has an effect on language usage. In recent years, especially during the COVID pandemic, social media platforms have become the de facto platform for many individuals to self-disclose or discuss mental health issues like depression. This trend presents a unique opportunity for researchers and healthcare professionals to detect potential mental illnesses for early intervention or treatment by taking advantage of the recent advances in machine learning approaches. Existing depression detection methods on social media, however, suffer from two major limitations. First, these solutions heavily rely on the amount, quality, and type of user-posted content. Second, the overlooked social circle impact should be leveraged to enhance the prediction capabilities. In this paper, we propose a depression detection framework, MentalNet, based on heterogeneous graph convolution by capturing users’ interactions (replies, mentions, and quotetiveets) with their friends on social media and differentiating the intimacy of users’ social circles (e.g., family, friends, or acquaintances). Specifically, we formulate the problem of depression detection on social media as a graph classification problem by representing users’ social circles in the format of heterogeneous graphs. MentalNet embraces three modules, (1) extraction of ego-network node features, (2) construction of user interaction graphs, and (3) depression detection based on heterogeneous graph classification. The extensive experiments on Twitter data demonstrate that MentalNet consistently and significantly outperforms the state-of-the-art methods in terms of all the effectiveness metrics. Compared to the baseline methods, MentalNet is able to effectively predict early depression in Twitter users with up to 24% improvement on F1 score.

Tensor decomposition aims to factorize an input tensor into a number of latent factors. Due to the low-rank nature of tensor in real applications, the latent factors can be used to perform tensor completion in numerous tasks, such as knowledge graph completion and timely recommendation. However, existing works solve the problem in Euclidean space, where the tensor is decomposed into Euclidean vectors. Recent studies show that hyperbolic space is roomier than Euclidean space. With the same dimension, a hyperbolic vector can represent richer information (e.g., hierarchical structure) than a Euclidean vector. In this paper, we propose to decompose tensor in hyperbolic space. Considering that the most popular optimization tools (e.g, SGD, Adam) have not been generalized in hyperbolic space, we design an adaptive optimization algorithm according to the distinctive property of hyperbolic manifold. To address the non-convex property of the problem, we adopt gradient ascent in our optimization algorithm to avoid getting trapped in local optimal landscapes. We conduct experiments on various tensor completion tasks and the result validates the superiority of our method over these baselines that solve the problem in Euclidean space.

The progress of industrial development naturally leads to the demand for more electrical power. Unfortunately, due to the fear of the safety of nuclear power plants, many countries have relied on thermal power plants, which will cause more air pollutants during the process of coal burning. This phenomenon as well as increased vehicle emissions around us, have constituted the primary factors of serious air pollution. Inhaling too much particulate air pollution may lead to respiratory diseases and even death, especially PM$_{2.5}$. By predicting the air pollutant concentration, people can take precautions to avoid overexposure to air pollutants. Consequently, accurate PM$_{2.5}$prediction becomes more important. In this study, we propose a PM$_{2.5}$prediction system, which utilizes the dataset from EdiGreen Airbox and Taiwan EPA. Autoencoder and Linear interpolation are adopted for solving the missing value problem. Spearman’s correlation coefficient is used to identify the most relevant features for PM$_{2.5}$. Two prediction models (i.e., LSTM and LSTM based on K-means) are implemented which predict PM$_{2.5}$value for each Airbox device. To assess the performance of the model prediction, the daily average error and the hourly average accuracy for the duration of a week are calculated. The experimental results show that LSTM based on K-means has the best performance among all methods. Therefore, LSTM based on K-means is chosen to provide real-time PM$_{2.5}$prediction through the Linebot.

A skyline query searches the data points that are not dominated by others in the dataset. It is widely adopted for many applications which require multi-criteria decision making. However, skyline query processing is considerably time-consuming for a high-dimensional large scale dataset. Parallel computing techniques are therefore needed to address this challenge, among which$MapReduce$is one of the most popular frameworks to process big data. A great number of efficient$MapReduce$skyline algorithms have been proposed in the literature and most of their designs focus on partitioning and pruning the given dataset. However, there are still opportunities for further parallelism. In this study, we propose two parallel skyline processing algorithms using a novel$LShape$partitioning strategy and an effective$Propagation$$Filtering$method. These two algorithms are$2Phase$$LShape$and$1Phase$$LShape$, used for multiple reducers and single reducer, respectively. By extensive experiments, we verify that our algorithms outperformed the state-of-the-art approaches, especially for high-dimensional large scale datasets.

Matrix completion is a well-known approach for recommender systems. It predicts the values of the missing entries in a sparse user-item interaction matrix, based on the low-rank structure of the rating matrix. However, existing matrix completion methods do not take node polysemy and side information of social relationships into consideration, which can otherwise further improve the performance. In this paper, we propose a novel matrix completion method that employs both users’ friendships and rating entries to predict the missing values in a user-item matrix. Our approach adopts a graph-based modeling where nodes are users and items, and two types of edges are considered: user friendships and user-item interactions. Polysemy-aware node features are extracted from this heterogeneous graph through a graph convolution network by considering the multifaceted factors for edge formation, which are then connected to a hybrid loss function with two heads: (1) a social-homophily head to address node polysemy, and (2) an error head for user-item rating regression. The latter is formulated on all matrix entries to combat the sensitivity of negative sampling of the vast majority of missing entries during training, with a smart technique to reduce the time complexity. Extensive experiments over real datasets verify that our model outperforms the state-of-the-art matrix completion methods by a significant margin.

While depression is rated as the most important leading factor to global disability, early detection of depression is a non-trivial task. Existing depression detection mechanisms harvesting social media data suffer from two major limitations. First, existing solutions rely heavily on the amount, quality, and variety of content types (textual, visual, etc.) posted by users to make accurate inferences, therefore suffering from the cold-start problem when coping with users with limited training data (e.g., most existing works exclude users with fewer than 25 tweets). Second, existing approaches ignore the social impact or indication from users' social circles that can be leveraged to enhance the inference results. In this paper, we present MentalSpot, a social-contagion based depression early-screening framework using meta-learning. Specifically, we first construct a social-contagion driven data repository PsycheNet, filling the void of social-circle based depression datasets. We design a triplet network to extract users' embeddings based on the similarities of the linguistic features extracted from written texts. Afterwards, for each target user, we employ dynamic mean shift pruning to select her top-k homogeneous friends in the metric space, the texts written by whom will then be leveraged to train a friend based depression detection model. Extensive experiments show that MentalSpot outperforms the state of the art in terms of all effectiveness metrics, especially for users with very few tweets. Specifically, by using only five tweets per user, MentalSpot successfully yields an F1 score that would otherwise be achieved by the state-of-the-art methods requiring at least twenty tweets. Our approach represents a step forward to address the cold-start problem that deep learning techniques struggle with for their applications in psychiatric diagnosis. The principal beneficiaries of this study are healthcare professionals in medical institutions to determine timely and targeted interventions in a clinical setting. This study also supports non-profit groups in reaching out to people with mental health issues, helping in a global health task that cannot be fully covered by clinicians.

Deep learning has assisted modern life in various ways. One example is that accurate economic prediction helps people better allocate and distribute their resources. In the U.S., home prices have been accelerating during the COVID-19 pandemic and climbed 13.3% in March 2021 from the previous year. Real estate market prediction is critical for home buyers and investors to make wise decisions. In some circumstances, accurate predictions on home prices are more important than usual in helping decision-makers to reduce financial mistakes.

Knowing the locations of tweets can benefit a wide variety of applications such as venue recommendation, event detection, and monitoring disaster outbreaks. However, the problem of fine-grained tweet geolocation prediction is challenging since tweets are short and therefore may not contain any geo-indicative words or may contain ambiguous, noisy information. Existing solutions either yield an unsatisfactory accuracy in practical applications or make predictions that even experts struggle to interpret, failing to engender sufficient trust and actionability for real-world deployment. Our paper presents a tweet geolocation prediction framework, EDGE (Entity-Diffusion Gaussian Ensemble), which delivers predictions that are both accurate and highly interpretable without requiring any additional contextual information such as user profile and location history. In EDGE, we cast the geolocation problem as a neutral network optimization problem by learning probabilistic generative models. Compared with existing works, EDGE has two distinctive features: (1) the inference builds on mining the correlation between non geo-indicative entities and geo-indicative entities by diffusing their semantic embeddings over the constructed graph neural network (Entity Diffusion) and (2) each prediction result is represented as a Gaussian mixture instead of specific geographical coordinates (Gaussian Ensemble). Extensive experiments using real-world tweet datasets validate the superiority of EDGE over the state of the art in terms of all distance-based and POI-based metrics.

In this study, we propose two parallel skyline processing algorithms using a novel LShape partitioning strategy and an effective Propagation Filtering method. By extensive experiments, we verify that our algorithms outperformed the state-of-the-art approaches, especially for high-dimensional large scale datasets.

Real-time traffic prediction is essential for mitigating traffic congestion and reducing travel time. Recent advancement in graph convolutional network (GCN) has motivated a series of GCN-based models for traffic forecasting on an urban road network. However, these graph-based methods cannot capture the intricate dependencies of consecutive road segments such as no left turn, and dynamic spatial dependency. In this paper, we propose Trajectory WaveNet, or T-wave in short, a traffic forecasting model that utilizes the actual vehicle trajectories to capture the above intricate dependencies to improve prediction performance. Both trajectories and traffic data are obtained from the floating car data collected by ridesharing companies such as DiDi. T-wave treats vehicle trajectories as first-class citizens, and applies dilated causal convolutions along both the temporal dimension (i.e., recent, daily-periodic and weekly-periodic historical traffic data) and the spatial dimension (i.e., trajectories). For effective training, a trajectory mini-batch sampling technique is devised considering both spatial and temporal proximity. Extensive experiments on real datasets show that T-wave consistently bests the state-of-the-art models.

Ridesharing companies such as Ube and DiDi provide ride-hailing services where passengers and drivers are matched via mobile apps. As a result, large amounts of vehicle trajectories and vehicle speed data are collected that can be used for traffic prediction. The recent popularity of graph convolutional networks (GCNs) has opened up new possibilities for real-time traffic prediction and many GCN-based models have been proposed to capture the spatial correlation on the urban road network. However, the graph-based approaches fail to capture the intricate dependencies of consecutive road segments that are well captured by trajectories.

Determining a protein's 3D from its sequences is one of the most challenging problems in biology. Recently, geometric deep learning has achieved great success on non-Euclidean domains including social networks, chemistry, and computer graphics. Although it is natural to present protein structures as 3D graphs, existing research has rarely studied protein structures as graphs directly. The present research explores the geometry deep learning of three-dimensional graphs on protein structures and proposes a graph neural network architecture to address these challenges. The proposed Protein Geometric Graph Neural Network (PG-GNN) models both distance geometric graph representation and dihedral geometric graph representation by geometric graph convolutions. This research shed new light on protein 3D structure studies. We investigated the effectiveness of graph neural networks over five real datasets. Our results demonstrate the potential of GNNs for 3D structure prediction.

With the rapid progress of global urbanization and function division among different geographical regions, it is of urgent need to develop methods that can find regions of desired future function distributions in applications. For example, a company tends to open a new branch in a region where the growth trend of industrial sectors fits its strategic goals, or is similar to that of an existing company location; while a job hunter tends to search regions where his/her expertise aligns with the industrial growth trend providing sufficient job opportunities to sustain future employment and job-hopping.

In mobile crowdsourcing, workers are financially motivated to perform self-selected tasks to maximize their revenue. Unfortunately, the existing task scheduling approaches in mobile crowdsourcing fail to scale for massive tasks and large geographic areas. We present Turbo-GTS, a system that assigns tasks to each worker to maximize the total number of the tasks that can be completed for an entire worker group while taking into account various spatial and temporal constraints, such as task execution duration, task expiration time, and worker/task geographic locations. The core of Turbo-GTS is WBT-NNH and WBT-NUD, our two newly developed scheduling algorithms, which build on the algorithms, QT-NNH and QT-NUD, proposed in our prior work [5]. The key idea is that Turbo-GTS performs dynamic workload balancing among all workers using the proposed Workload-balancing Bisection Tree (WBT) in support of large-scale Geo-Task Scheduling (GTS). Turbo-GTS includes an interactive interface for users to load the current task/worker distributions and compare the task assignment of each worker returned by different algorithms in a real-time fashion. Using the Foursquare mobile user check-in data in New York City and Tokyo, we show the superiority of Turbo-GTS over the state of the art in terms of the total number of the tasks that can be accomplished by the entire worker group and the corresponding running time. We also demonstrate the front-end interface of Turbo-GTS with two exploratory use cases in New York City.

Mining from a big graph those subgraphs that satisfy certain conditions is useful in many applications such as community detection and subgraph matching. These problems have a high time complexity, but existing systems to scale them are all IO-bound in execution. We propose the first truly CPU-bound distributed framework called G-thinker that adopts a user-friendly subgraph-centric vertex-pulling API for writing distributed subgraph mining algorithms. To utilize all CPU cores of a cluster, G-thinker features (1) a highly-concurrent vertex cache for parallel task access and (2) a lightweight task scheduling approach that ensures high task throughput. These designs well overlap communication with computation to minimize the CPU idle time. Extensive experiments demonstrate that G-thinker achieves orders of magnitude speedup compared even with the fastest existing subgraph-centric system, and it scales well to much larger and denser real network data. G-thinker is open-sourced at http://bit.ly/gthinker with detailed documentation.

Relational database management systems (RDBMSs) are powerful because they are able to optimize and execute queries against relational databases. However, when it comes to NLIDB (natural language interface for databases), the entire system is often custom-made for a particular database. Overcoming the complexity and expressiveness of natural languages so that a single NLI can support a variety of databases is an unsolved problem. In this work, we show that it is possible to separate data specific components from latent semantic structures in expressing relational queries in a natural language. With the separation, transferring an NLI from one database to another becomes possible. We develop a neural network classifier to detect data specific components and an adversarial mechanism to locate them in a natural language question. We then introduce a general purpose transfer-learnable NLI that focuses on the latent semantic structure. We devise a deep sequence model that translates the latent semantic structure to an SQL query. Experiments show that our approach outperforms previous NLI methods on the WikiSQL [49] dataset, and the model we learned can be applied to other benchmark datasets without retraining.

A natural language interface (NLI) to databases is an interface that translates a natural language question to a structured query that is executable by database management systems (DBMS). However, an NLI that is trained in the general domain is hard to apply in the spatial domain due to the idiosyncrasy and expressiveness of the spatial questions. Inspired by the machine comprehension model, we propose a spatial comprehension model that is able to recognize the meaning of spatial entities based on the semantics of the context. The spatial semantics learned from the spatial comprehension model is then injected to the natural language question to ease the burden of capturing the spatial-specific semantics. With our spatial comprehension model and information injection, our NLI for the spatial domain, named SpatialNLI, is able to capture the semantic structure of the question and translate it to the corresponding syntax of an executable query accurately. We also experimentally ascertain that SpatialNLI outperforms state-of-the-art methods.

Due to the inadequacy of GPS signals in indoor spaces, Indoor Positioning Services (IPSs) have drawn great attention. The popular smartphone localization technique relies on a centralized server to achieve localization, allowing the server to acquire a user's location in fine granularity. To ensure the privacy of IPS users, we propose an Encrypted Indoor Positioning Service (EIPS) model that protects users' privacy from the centralized server and maintains localization accuracy simultaneously. Our EIPS model enables users to encrypt and decrypt their query through an Encryption and Decryption Server (EDS) bi-directionally in a commutative way, so the users' locations remain private to both EIPS and EDS. We also propose Query Split, Artificial Dimensions and Columns to prevent Known Plaintext Attack (KPA). Our analytical and experimental evaluations show that our model is resilient to a variety of privacy attacks without loss of efficiency and accuracy.

This research proposes an advanced approach that improves the efficiency of skyline query processing by significantly reducing the computational cost on object comparisons, i.e., dominance tests between objects. Our solutions are based on two novel concepts. The skyline query over Minimum Bounding Rectangles (MBRs) receives a set of MBRs and returns the MBRs that are not dominated by other MBRs. In the dominance test for MBRs, the detailed attribute values of objects in the MBRs are not accessed. Moreover, the dependent group of MBRs reduces the search space for dominance tests. Objects in an MBR are only compared with the ones in the corresponding dependent groups of the MBR rather than with the entire dataset. Our solutions apply the two concepts to the R-tree in order to use its hierarchical structure in which every node is a natural abstraction of an MBR. Specifically, given the R-tree index of an input dataset, we first eliminate unqualified objects by utilizing the skyline query over MBRs (i.e., intermediate nodes in the R-tree). Subsequently, we generate dependent groups for the skyline MBRs. Two dependent group generation methods that rely on either the sorting technique or the R-tree index are developed. Further, we apply an existing skyline algorithm to every dependent group, and the results of the original skyline query are the union of skyline objects in the dependent groups. In addition, we also analyze the cardinality of the two new concepts based on a probabilistic model, which enables us to analyze the computational complexity of the proposed solutions. Our experimental results show that the proposed solutions are clearly more efficient than the state-of-the-art approaches.

This paper presents an exact solution and a heuristic solution to a UAV-assisted parcel delivery problem, in which UAVs can only be operated in Visual-Line-Of-Sight (VLOS) areas. In our proposed problem, we assume that trucks travel on road networks, and UAVs move in Euclidean spaces and can launch at any locations on roads. We first demonstrate the overview of our exact solution that iterates all permutations of destinations for an optimal delivery route. Given a specific delivery order, an intuitive approach needs to check all possible locations on roads in the VLOS areas and find a globally optimal location for every destination if UAVs are used for delivery. To avoid high computational cost of searching the optimal location at runtime, we propose an advanced index-based alternative, which computes optimal delivery routes in a pre-processing stage. Due to the nature of NP-hard problems, we also propose a heuristic approach that utilizes delivery groups for the proposed problem of practical size. All proposed solutions are evaluated through extensive experiments.

In this paper, we study the problem of recommending time-sensitive location sequence for mobile users using their check-in data on location-based social networks. Most of the existing studies on Point of Interest (POI) recommendation and prediction fail to address the following two key challenges: (1) how to handle the scenario where the user-location matrix is very sparse (i.e., each user has a very limited number of check-ins, or to say, cold-start users), and (2) how to recommend an optimal time-sensitive visit sequence where each venue matches a time slot specified by users, based on their check-in histories. Motivated by the two challenges above, we propose a predictive framework that enables time-sensitive location sequence recommendation leveraging both the users' semantic and spatial similarities, especially for cold-start users. Our novel framework consists of three modules: semantic similarity modeling, spatial similarity modeling, and on-line sequence recommendation. In semantic modeling, we calculate users' similarity scores by comparing users' temporal hierarchical semantic trees. In spatial modeling, we use Gaussian Mixture Model (GMM) to compute users' similarity scores with respect to their geographical movement paterns. Aferwards, we combine the check-in data of the target user with those of her top-k most similar users in terms of both semantic and spatial similarities to train a personalized Hidden Markov Model (HMM) to predict the most probable venue category for each specified time slot. At last, we recommend location sequence based on the predicted venue category sequence for the target user using geographical mapping.

In mobile crowdsourcing, workers are financially motivated to perform as many self-selected tasks as possible to maximize their revenue. Unfortunately, the existing task scheduling approaches in mobile crowdsourcing fail to consider task execution duration and do not scale for massive tasks and large geographic areas (e.g., a whole city). In this paper, we study on the geo-task scheduling problem (GTS) under the various spatial and temporal constraints in real-world mobile crowdsourcing applications, including task execution duration and task expiration time. Given the location of a worker, the goal of our study is to find an optimal task execution sequence that maximizes the number of tasks that could be finished. Since the exact solution to the maximum task scheduling is computationally intractable, we propose two sub-optimal approaches (LCPF and NUD-IC) based on the particle filtering and the DBSCAN clustering.

Link prediction is a fundamental problem in social network analysis. Although the link prediction problem is not new, the challenge of how to exploit various existing network information, such as network structure data and node attribute data, to enable AI-style knowledge inference for large social networks still remains unsolved. In this paper, we design and implement a scalable framework that treats link prediction as knowledge reasoning using Markov Logic Networks (MLNs). Differing from other probabilistic graphical models, MLNs allow undirected relationships with cycles and long-range (non-adjacent) dependency, which are essential and abound in social networks. In our framework, the prior knowledge is captured as the structure dependency (such as friendship) and the attribute dependency (such as social communities) in terms of inference rules, associated with uncertainty represented as probabilities. Next, we employ the random walk to discover the inference subgraph, on which probabilistic inference is performed, so that the required computation and storage cost can be significantly reduced without much sacrifice of the inference accuracy. Our extensive experiments with real-world datasets verify the superiority of our proposed approaches over two baseline methods and show that our approaches are able to provide a tunable tradeoff between inference accuracy and efficiency.

RFID (Radio Frequency Identification)-based object tracking is increasingly deployed and used in indoor environments such as airports, shopping malls, etc. However, the inherent noise in the raw RFID data makes it difficult to support queries and analyses on the data. In this paper, we propose an RFID data cleansing based on regular expressions. We generate the regular expressions in an automaton that captures all possible indoor paths from the spatial and temporal aspects of indoor space and deployed readers. Given the raw data of an object, the proposed matching algorithm finds all the matching paths using the automaton. We evaluate the proposed approach by conducting experimental studies using real dataset. The results demonstrate the effectiveness of the propose approach.

A variety of optimal location problems have been extensively studied in the literature. However, limited visualization systems have been developed for illustrating optimal location selection process. In this demonstration, we present a system that visualizes an advanced solution that can efficiently answer multi-criteria optimal location updating query by incrementally updating the Minimum Overlapping Voronoi Diagram (MOVD) model. Not only does our system display an example as a practical multi-criteria optimal location updating query, but also visualizes the process of the query evaluation in a more intuitive manner. With the object insertion and deletion operations defined over the MOVD model, any object changes in an MOVD can be represented by removing the objects from initial datasets and adding them back with updated attributes. Moreover, Haxe toolkit is used to provide friendly and flexible user interfaces in our system.

RFID is widely used for object tracking in indoor environments, e.g., airport baggage tracking. Analyzing RFID data offers insight into the underlying tracking systems as well as the associated business processes. However, the inherent uncertainty in RFID data, including noise (cross readings) and incompleteness (missing readings), pose challenges to high-level RFID data querying and analysis. In this paper, we address these challenges by proposing a learning-based data cleansing approach that, unlike existing approaches, requires no detailed prior knowledge about the spatio-temporal properties of the indoor space and the RFID reader deployment. Requiring only minimal information about RFID deployment, the approach learns relevant knowledge from raw RFID data and uses it to cleanse the data. In particular, we model raw RFID readings as time series that are sparse because the indoor space is only partly covered by a limited number of RFID readers.

In this demonstration, we present a visualization system offering two advanced solutions that can efficiently address a novel multi-criteria optimal location query by using Overlapping Voronoi Diagrams (OVDs). Our system not only displays an example that applies the advanced solutions to a practical optimal location query, but also visualizes the process of query evaluation by using the solutions, which can help users better understand the two solutions in a more intuitive way. The Real Region as Boundary (RRB) approach calculates real regions of overlapped Voronoi cells, while the Minimum Bounding Rectangle as Boundary (MBRB) approach approximates the cells by their MBRs to simplify region overlapping calculation. For efficient query evaluation and better demonstration, global and local datasets are managed separately and only the local dataset is displayed in a limited visualization area. User interactions are provided in diverse manners in our system by using the Standard Widget Toolkit (SWT) and Open Graphics Library (OpenGL).

This paper presents a novel optimal location selection problem, which can be applied to a wide range of applications.After providing a formal definition of the novel query type, we explore an intuitive approach that sequentially scans all possible object combinations in the search space.Then, we propose an Overlapping Voronoi Diagram (OVD) model that defines OVDs and Minimum OVDs, and construct an algebraic structure under an OVD overlap operation.Based on the OVD model, we design an advanced approach to answer the query.Due to the high complexity of Voronoi diagram overlap computation, we improve the overlap operation by replacing the real boundaries of Voronoi diagrams with their Minimum Bounding Rectangles (MBR).We also propose a cost-bound iterative approach that efficiently processes a large number of Fermat-Weber problems.Our experimental results show that the proposed algorithms can evaluate the novel query type effectively and efficiently.

In this paper, we propose two parameterized frameworks, namely the Uniform Watchtower (UW) framework and the Hot zone-based Watchtower (HW) framework, for the evaluation of spatial queries on large road networks. The motivation of this research is twofold: (1) how to answer spatial queries efficiently on large road networks with massive POI data and (2) how to take advantage of social data in spatial query processing. In UW, the network traversal terminates once it acquires the Point of Interest (POI) distance information stored in watchtowers. In HW, by observing that users' movements often exhibit strong spatial patterns, we employ probabilistic clustering to model mobile user check-in data as a mixture of 2-dimensional Gaussian distributions to identify hot zones so that watchtowers can be deployed discriminatorily. Our analyses verify the superiority of HW over UW in terms of query response time.

Outsourcing spatial databases to the cloud provides an economical and flexible way for data owners to deliver spatial data to users of location-based services. However, in the database outsourcing paradigm, the third-party service provider is not always trustworthy, therefore, ensuring spatial query integrity is critical. In this paper, we propose an efficient road network k-nearest-neighbor query verification technique which utilizes the network Voronoi diagram and neighbors to prove the integrity of query results. Unlike previous work that verifies k-nearest-neighbor results in the Euclidean space, our approach needs to verify both the distances and the shortest paths from the query point to its kNN results on the road network. We evaluate our approach on real-world road networks together with both real and synthetic points of interest datasets. Our experiments run on Google Android mobile devices which communicate with the service provider through wireless connections. The experiment results show that our approach leads to compact verification objects (VO) and the verification algorithm on mobile devices is efficient, especially for queries with low selectivity.

People spend a significant amount of time in indoor spaces (e.g., office buildings, subway systems, etc.) in their daily lives. Therefore, it is important to develop efficient indoor spatial query algorithms for supporting various location-based applications. However, indoor spaces differ from outdoor spaces because users have to follow the indoor floor plan for their movements. In addition, positioning in indoor environments is mainly based on sensing devices (e.g., RFID readers) rather than GPS devices. Consequently, we cannot apply existing spatial query evaluation techniques devised for outdoor environments for this new challenge. Because particle filters can be employed to estimate the state of a system that changes over time using a sequence of noisy measurements made on the system, in this research, we propose the particle filter-based location inference method as the basis for evaluating indoor spatial queries with noisy RFID raw data. Furthermore, two novel models, indoor walking graph model and anchor point indexing model, are created for tracking object locations in indoor environments. Based on the inference method and tracking models, we develop innovative indoor range and k nearest neighbor (kNN) query algorithms. We validate our solution through extensive simulations with real-world parameters. Our experimental results show that the proposed algorithms can evaluate indoor spatial queries effectively and efficiently.

An increasing number of spatial keyword query techniques that return qualified objects based on a comprehensive consideration of spatial and keyword constraints have been presented in the literature. Due to the complexity of the solutions to spatial keyword queries, systems that can effectively demonstrate the mechanisms will attract interest from the spatial database research community. However, very limited visualization systems have been developed for illustrating spatial keyword query evaluation. In this demonstration, we present a system that visualizes advanced solutions to efficiently answer the Spatial Keyword k Nearest Neighbor (SKkNN) query. With the two-level data management method and the friendly user interface implemented by the Standard Widget Toolkit (SWT) and Open Graphics Library (OpenGL), our system is able to not only interact with users in diverse manners, visualize datasets, and display the SKkNN query evaluation process, but it also helps users better understand the solutions in a more intuitive way.

As one of the most important Semantic Web applications, social network analysis has attracted more and more interest from researchers due to the rapidly increasing availability of massive social network data. A desired solution for social network analysis should address the following issues. First, in many real world applications, inference rules are partially correct. An ideal solution should be able to handle partially correct rules. Second, applications in practice often involve large amounts of data. The inference mechanism should scale up towards large-scale data. Third, inference methods should take into account probabilistic evidence data because these are domains abounding with uncertainty. Various solutions for social network analysis have existed for quite a few years; however, none of them support all the aforementioned features. In this paper, we design and implement LinkProbe, a prototype to quantitatively predict the existence of links among nodes in large-scale social networks, which are empowered by Markov Logic Networks (MLNs). MLN has been proved to be an effective inference model which can handle complex dependencies and partially correct rules. More importantly, although MLN has shown acceptable performance in prior works, it is also reported as impractical in handling large-scale data due to its highly demanding nature in terms of inference time and memory consumption. In order to overcome these limitations, LinkProbe retrieves the k-backbone graphs and conducts the MLN inference on both the most globally influencing nodes and most locally related nodes. Our extensive experiments show that LinkProbe manages to provide a tunable balance between MLN inference accuracy and inference efficiency.

Numerous geographic information system applications need to retrieve spatial objects which bear user specified keywords close to a given location. In this research, we present efficient approaches to answer spatial keyword queries on spatial networks. In particular, we formally introduce definitions of Spatial Keyword k Nearest Neighbor (SKkNN) and Spatial Keyword Range (SKR) queries. Then, we present a framework of a spatial keyword query evaluation system which is comprised of Keyword Constraint Filter (KCF), Keyword and Spatial Refinement (KSR), and the spatial keyword ranker. KCF employs an inverted index to calculate keyword relevancy of spatial objects, and KSR refines intermediate results by considering both spatial and keyword constraints with the spatial keyword ranker. In addition, we design novel algorithms for evaluating SKkNN and SKR queries. These algorithms employ the inverted index technique, shortest path search algorithms, and network Voronoi diagrams. Our extensive simulations show that the proposed SKkNN and SKR algorithms can answer spatial keyword queries effectively and efficiently.

With the popularity of location-based services and the abundant usage of smart phones and GPS-enabled devices, the necessity of outsourcing spatial data has grown rapidly over the past few years. Meanwhile, the fast arising trend of cloud storage and cloud computing services has provided a flexible and cost-effective platform for hosting data from businesses and individuals, further enabling many location-based applications. Nevertheless, in this database outsourcing paradigm, the authentication of the query results at the client remains a challenging problem. In this paper, we focus on the Outsourced Spatial Database (OSDB) model and propose an efficient scheme, called VN-Auth, which allows a client to verify the correctness and completeness of the result set. Our approach is based on neighborhood information derived from the Voronoi diagram of the underlying spatial data set and can handle fundamental spatial query types, such as k nearest neighbor and range queries, as well as more advanced query types like reverse k nearest neighbor, aggregate nearest neighbor, and spatial skyline. We evaluated VN-Auth based on real-world data sets using mobile devices (Google Droid smart phones with Android OS) as query clients. Compared to the current state-of-the-art approaches (i.e., methods based on Merkle Hash Trees), our experiments show that VN-Auth produces significantly smaller verification objects and is more computationally efficient, especially for queries with low selectivity.

The past few years have witnessed the emergence of an increasing number of applications for tracking and tracing based on radio frequency identification (RFID) technologies. However, raw RFID readings are usually of low quality and may contain numerous anomalies. An ideal solution for RFID data cleansing should address the following issues. First, in many applications, duplicate readings of the same object are very common. The solution should take advantage of the resulting data redundancy for data cleaning. Second, prior knowledge about the environment may help improve data quality, and a desired solution must be able to take into account such knowledge. Third, the solution should take advantage of physical constraints in target applications to elevate the accuracy of data cleansing. There are several existing RFID data cleansing techniques. However, none of them support all the aforementioned features. In this paper, we propose a Bayesian inference-based framework for cleaning RFID raw data. We first design an n-state detection model and formally prove that the three-state model can maximize the system performance. Then, we extend the n-state model to support two-dimensional RFID reader arrays and compute the likelihood efficiently. In addition, we devise a Metropolis-Hastings sampler with constraints, which incorporates constraint management to clean RFID data with high efficiency and accuracy. Moreover, to support real-time object monitoring, we present the streaming Bayesian inference method to cope with realtime RFID data streams. Finally, we evaluate the performance of our solutions through extensive experiments.

The results of skyline queries performed on data sets with partially-ordered domains vary depending on users' preference profiles specified for the partially-ordered domains. Existing work has addressed the issue of handling each individual query with some efficiency. However, processing large volumes of such queries for online applications with low response time is still very challenging. In this paper, we introduce a novel approach, termed CSS, to reduce the latency by caching query results with their unique user preferences. Of paramount importance in this case is that cached queries with compatible preference profiles need to be utilized. For this purpose, we introduce a similarity measure that establishes the level of a relation of a new query to each of the previously cached queries and profiles. The similarity measure allows the cached entries to be effectively ordered according to descending values; hence, query processing can start with the most promising candidates. If a new query is only partially answerable from the cache, the proposed method pursues a second optimization step. The query processor utilizes the partial result sets and augments them by performing less expensive constraint skyline queries guided by constraint violations between different query preference profiles. Extensive experiments are presented to demonstrate the performance and utility of our novel approach.

Outsourcing spatial databases, including both road networks and points of interest, to a third party Cloud service provider has attracted much attention from individual and business data owners. With popularity of mobile devices, providing instant and reliable location-based services to smartphones and tablets has been a major means of delivering spatial data to real-world users. Therefore, ensuring spatial query integrity in database outsourcing paradigms is critical. In this paper, we propose a novel road network k-nearest-neighbor query verification technique which utilizes the network Voronoi diagrams and neighbors to prove the integrity of the query result. Unlike previous work that verifies k-nearest-neighbor results in the Euclidean space, our approach verifies both the distances and the shortest paths from the query point to its kNN result on the road network.

Skyline is a popular query type which retrieves data objects that are not dominated by any other object with respect to multiple attributes. Skyline queries have broad applications; however, limited studies have been done on skyline in the broadcast data model. No study has been done on flexible skyline query evaluations in this model that can handle a combination of minimum and maximum attributes. In this paper, we propose the Tree-based Distributed Index (TDI) and the skyline algorithms that incorporate TDI to efficiently evaluate skyline in broadcast environments. Our extensive simulations show that the proposed algorithms can answer skyline queries in broadcast environments effectively and efficiently.

The techniques of utilizing spatial data on the Semantic Web have attracted more and more interest from researchers due to the rapidly increasing applications based on geographic information. However, there are currently limited solutions providing efficient spatial query evaluation based on Semantic Web data. In this demonstration, we present Geo-Store, a novel spatially-augmented SPARQL evaluation system. By extending the standard SPARQL query language with spatial query filters, Geo-Store is able to process complex spatial queries with common spatial constraints. These spatial filters are designed based on our Spatially Aware Mapping (SAM) scheme. With SAM, spatial data are pre-processed and encoded with their Hilbert values by employing the Hilbert curve, resulting in more efficient spatial query processing than the existing approaches. The Geo-Store demonstration includes both a server and a web browser-based client.

Skyline query processing has become an important feature in multi-dimensional, data-intensive applications. Such computations are especially challenging under dynamic conditions, when either snapshot queries need to be answered with short user response times or when continuous skyline queries need to be maintained efficiently over a set of objects that are frequently updated. To achieve high performance, we have recently designed the ESC algorithm, an Efficient update approach for Skyline Computations. ESC creates a pre-computed candidate skyline set behind the first skyline (a “second line of defense,” so to speak) that facilitates an incremental, two-stage skyline update strategy which results in a quicker query response time for the user. Our demonstration presents the two-threaded SkyEngine system that builds upon and extends the base-features of the ESC algorithm with innovative, user-oriented functionalities that are termed SkyAlert and AutoAdjust. These functions enable a data or service provider to be informed about and gain the opportunity of automatically promoting its data records to remain part of the skyline, if so desired. The SkyEngine demonstration includes both a server and a web browser based client. Finally, the SkyEngine system also provides visualizations that reveal its internal performance statistics.

Data uncertainty arises in many situations. A common approach to query processing uncertain data is to sample many "possible worlds" from the uncertain data and to run queries against the possible worlds. However, sampling is not a trivial task, as a randomly sampled possible world may not satisfy known constraints imposed on the data. In this paper, we focus on an important category of constraints, the aggregate constraints. An aggregate constraint is placed on a set of records instead of on a single record, and a real-life system usually has a large number of aggregate constraints. It is a challenging task to find qualified possible worlds in this scenario, since tuple by tuple sampling is extremely inefficient because it rarely leads to a qualified possible world. In this paper, we introduce two approaches for querying uncertain data with aggregate constraints: constraint aware sampling and MCMC sampling. Our experiments show that the new approaches lead to high quality query results with reasonable cost.

With the popularity of location-based services and the abundant usage of smart phones and GPS enabled devices, the necessity of outsourcing spatial data has grown rapidly over the past few years. Nevertheless, in the database outsourcing paradigm, the authentication of the query results at the client remains a challenging problem. In this paper, we focus on the Outsourced Spatial Database (OSDB) model and propose an efficient scheme, called VN-Auth, that allows a client to verify the correctness and completeness of the result set. Our approach can handle both k nearest neighbor (kNN) and range queries, and is based on neighborhood information derived by the Voronoi diagram of the underlying spatial dataset. Specifically, upon receiving a query result, the client can verify its integrity by examining the signatures and exploring the neighborhood of every object in the result set. Compared to the current state-of-the-art approaches (i.e., methods based on Merkle hash trees), VN-Auth produces significantly smaller verification objects (VO) and is more computationally efficient, especially for queries with low selectivity.

It is cost-effective for data owners to publicize their spatial databases via database outsourcing; however, data privacy and query integrity are major challenges. In this demonstration, we implemented the INTACT (spatial query INTegrity AssuranCe framework for locaTion-based services) framework on the iPhone and the .NET Framework that protects data privacy using space encryption and ensures query integrity via audit queries.

A k-Range Nearest Neighbor (or kRNN for short) query in road networks finds the k nearest neighbors of every point on the road segments within a given query region based on the network distance. The kRNN query is significantly important for location-based applications in many realistic scenarios. For example, (1) the user’s location is uncertain, i.e., user’s location is modeled by a spatial region, and (2) the user is not willing to reveal her exact location to preserve her privacy, i.e., her location is blurred into a spatial region. However, the existing solutions for kRNN queries simply apply the traditional k-nearest neighbor query processing algorithm multiple times, which poses a huge redundant searching overhead. To this end, we propose an efficient kRNN query processing algorithm in this paper. Our algorithm (1) employs a shared execution approach to eliminate the redundant searching overhead, and (2) provides a parameter that can be tuned to achieve a tradeoff between the query processing performance and the storage overhead, while guaranteeing the user’s exact k-nearest neighbors are included in the query answers. The experimental results show that our algorithm always outperforms the existing solution in terms of query response time, and the introduced tuning parameter is an effective way to achieve the tradeoff between the query response time and the storage overhead.

Radio Frequency Identification (RFID) technologies are used in many applications for data collection. However, raw RFID readings are usually of low quality and may contain many anomalies. An ideal solution for RFID data cleansing should address the following issues. First, in many applications, duplicate readings (by multiple readers simultaneously or by a single reader over a period of time) of the same object are very common. The solution should take advantage of the resulting data redundancy for data cleaning. Second, prior knowledge about the readers and the environment (e.g., prior data distribution, false negative rates of readers) may help improve data quality and remove data anomalies, and a desired solution must be able to quantify the degree of uncertainty based on such knowledge. Third, the solution should take advantage of given constraints in target applications (e.g., the number of objects in a same location cannot exceed a given value) to elevate the accuracy of data cleansing. There are a number of existing RFID data cleansing techniques. However, none of them support all the aforementioned features. In this paper we propose a Bayesian inference based approach for cleaning RFID raw data. Our approach takes full advantage of data redundancy. To capture the likelihood, we design an n-state detection model and formally prove that the 3-state model can maximize the system performance. Moreover, in order to sample from the posterior, we devise a Metropolis-Hastings sampler with Constraints (MH-C), which incorporates constraint management to clean RFID raw data with high efficiency and accuracy. We validate our solution with a common RFID application and demonstrate the advantages of our approach through extensive simulations.

The k-anonymity technique is widely used to provide location privacy protection for accessing location-based services (LBS), i.e., the exact location of a query initiator is cloaked into a spatial region that contains at least k indistinguishable users. However, a centralized location anonymizer may pose serious privacy threats and could be the system bottleneck. Moreover, many cloaking methods are developed for the Euclidean space and fail to consider the features of road networks. In this demonstration, we present the technologies and implementations which protect location privacy by peer-to-peer based cloaking on road networks. We name the prototype system as PROS. With PROS, a mobile user forms a cloaked road segment set by collaborating with her peers when she needs to retrieve information from location-based service providers. Afterward, the cloaked road segment set is sent to the service provider for query processing and an inclusive query result set is returned to the query initiator after the query evaluation.

The PLUS system is designed to efficiently track moving object locations on a road network and execute continuous spatial queries in support of location-based services. PLUS implements a novel lazy position update mechanism that significantly reduces the communication overhead and server indexing load related to frequent location updates in moving object and moving query scenarios. The contribution of this demo is to present how the lazy position update scheme can achieve message-efficiency under various conditions which can be interactively set via user-selectable parameters in a graphical user interface.

Trip planning search (TPS) represents an important class of queries in Geographic Information Systems (GIS). In many real-world applications, TPS requests are issued with a number of constraints. Unfortunately, most of these constrained TPS cannot be directly answered by any of the existing algorithms. By formulating each restriction into rules, we propose a novel form of route query, namely the multi-rule partial sequenced route (MRPSR) query. Our work provides a unified framework that also subsumes the well-known trip planning query (TPQ) and the optimal sequenced route (OSR) query. In this paper, we first prove that MRPSR is NP-hard and then present three heuristic algorithms to search for near-optimal solutions for the MRPSR query. Our extensive simulations show that all of the proposed algorithms can answer the MRPSR query effectively and efficiently. Using both real and synthetic datasets, we investigate the performance of our algorithms with the metrics of the route distance and the response time in terms of the percentage of the constrained points of interest (POI) categories. Compared to the LORD-based brute-force solution, the response times of our algorithms are remarkably reduced while the resulting route length is only slightly longer than the shortest route.

Continuous spatial queries posted within an environment of moving objects produce as their results a time-varying set of objects. In the most ambitious case both queries and data objects are dynamic, making it very challenging to find an efficient query evaluation strategy. The significant overhead related to frequent location updates from moving objects often results in poor performance. The most advanced existing techniques use the concept of simple geometric safe regions to delay or avoid location updates. We introduce a Partition-based Lazy Update (PLU) algorithm that elevates this idea further by adopting Location Information Tables (LIT) which (a) allow each moving object to estimate possible query movements and issue a location update only when it may affect any query results and (b) enable smart server probing that results in fewer messages. Among the significant advantages, our technique performs well even in very highly dynamic environments (with up to 100% mobility) where many other techniques deteriorate. PLU can be efficiently implemented and we demonstrate its query performance improvement of up to 28% over the current state-of-the-art.

Location-based spatial queries (LBSQs) refer to spatial queries whose answers rely on the location of the inquirer. Efficient processing of LBSQs is of critical importance with the ever-increasing deployment and use of mobile technologies. We show that LBSQs have certain unique characteristics that traditional spatial query processing in centralized databases does not address. For example, a significant challenge is presented by wireless broadcasting environments, which often exhibit high-latency database access. In this paper, we present a novel query processing technique that, while maintaining high scalability and accuracy, manages to reduce the latency considerably in answering location-based spatial queries. Our approach is based on peer-to-peer sharing, which enables us to process queries without delay at a mobile host by using query results cached in its neighboring mobile peers. We illustrate the appeal of our technique through extensive simulation results.

In this demonstration we present MAPLE, a scalable peer-to-peer nearest neighbor (NN) query system for mobile environments. MAPLE is designed for the efficient sharing of query results cached in the local storage of mobile peers. The MAPLE system is innovative in its ability to either fully or partially compute location-dependent nearest neighbor objects on each host. The demonstration illustrates how cooperative data sharing and distributed processing among mobile peers results in a considerable reduction of the load on remote spatial databases.

Nearest neighbor (NN) searches represent an important class of queries in geographic information systems (GIS). Most nearest neighbor algorithms rely on static distance information to compute NN queries (e.g., Euclidean distance or spatial network distance). However, the final goal of a user when performing an NN search is often to travel to one of the search results. Based on this observation, finding the nearest neighbors in terms of travel time is more realistic than the actual distance. In the existing NN algorithms dynamic real-time events (e.g., traffic congestions, detours, etc.) are usually not considered and hence the pre-computed nearest neighbor objects may not accurately reflect the shortest travel time. In this demonstration we present ANNATTO, a novel adaptive nearest neighbor query model for travel time networks which integrates both spatial networks and real-time traffic event information. The ANNATTO system includes the implementation of a globalbased adaptive nearest neighbor algorithm and a localbased greedy nearest neighbor algorithm that both utilize real-time traffic information to provide adaptive nearest neighbor search results.