In this paper, we investigate a novelInfluencePersistenceMaximization (InfPM) problem in temporal social networks. Given a temporal graph, InfPM aims to identify a fixed seed node set$S$that maximizes the total duration of persistent influence across consecutive snapshots. After proving that InfPM is NP-hard, monotonic, and non-submodular, we develop two efficient solutions: (1) RevG, a reverse greedy algorithm that iteratively removes low-contribution nodes, and (2) LRep, a replacement-based method that progressively improves the quality of seed node set. To accelerate influence computation in RevG and LRep, we propose a new influence computation method integrating snapshot compression, probability-aware sampling, and a specialized influence estimator offering unbiased estimation. Additionally, we explore a practical variant of InfPM, termed Win-InfPM, which relaxes the requirement of consecutive snapshots by introducing a flexible time window model. Extensive experiments on seven real-world networks demonstrate that (1) RevG and LRep effectively identify high-quality seed nodes, achieving up to 100% improvement in total influence persistence over the baselines; and (2) the proposed influence computation method improves the efficiency of RevG and LRep by up to 400%, while maintaining comparable influence persistence.

In this paper, we investigate the Time-aware Influence Minimization (TIMIN) problem in social networks, focusing on minimizing negative influence concerning a critical deadline by temporarily blocking specific nodes in the given social network. First, we introduce the Temporal Linear Threshold (TLT) model, a novel framework that incorporates time delay in influence propagation, the decay of influence power over time, and the lifecycle of influence. Building on this model, we formally define the Timin problem and prove its NP-hardness, monotonicity, and supermodularity. To tackle the Timin problem, we develop the Timin-Greedy, a greedy algorithm that achieves$(1\ -1/e)$approximation. Since exact computation of negative influence spread for any node set in Timin-Greedy is #P-hard, we propose TESTIM, a scalable implementation that provides$(1-1/e-\epsilon)$approximation. To further enhance the efficiency, we introduce NReplacer, a heuristic algorithm leveraging the insight that potential blocking nodes often cluster near the negative source. Our extensive experimental evaluations demonstrate several key findings: (1) TESTIM is up to 10× faster than the baselines while achieving 30%–50% more reductions in negative influence spread, and (2) NReplacer exhibits a 5× speedup compared to TESTIM, with comparable reductions in negative influence spread.

In this paper, we address a novel problem in social network analysis: the Most Influenced Community Search (MICS). Given a graph and a seed node set$S$, the MICS problem seeks to identify a densely connected sub graph that is most significantly impacted by$S$. We formally define MICS, prove its NP-hardness, and show that constant-factor approximation is not feasible. To solve MICS efficiently, we propose a two-phase framework. In the first phase, we compute the influenced expectation for each node, representing its likelihood of being influenced by$S$. We develop two algorithms: S-InfExp, a sampling-based method with theoretical guarantees, and L-InfExp, a learning-based approach for faster predictions. In the second phase, we introduce two algorithms, GlobalSearch and LocalSearch, to find the most influenced community. GlobalSearch uses a top-down, greedy approach, while LocalSearch applies a bottom-up strategy. Experiments on eight real-world datasets demonstrate that (1) L-InfExp is up to 100× faster than S-InfExp with comparable accuracy, (2) LocalSearch is 10× faster than GlobalSearch, with both algorithms effectively identifying the community with the highest influenced expectations, and (3) our algorithms outperform all baselines.

Approximate nearest neighbor search (ANNS) in high-dimensional vector spaces has a wide range of real-world applications. Numerous methods have been proposed to handle ANNS efficiently, while graph-based indexes have gained prominence due to their high accuracy and efficiency. However, the indexing overhead of graph-based indexes remains substantial. With exponential growth in data volume and increasing demands for dynamic index adjustments, this overhead continues to escalate, posing a critical challenge. In this paper, we introduce Tagore, a fas T library a ccelerated by G PUs f or graph ind e xing, which has powerful capabilities of constructing refinement-based graph indexes such as NSG and Vamana. We first introduce GNN-Descent, a GPU-specific algorithm for efficient k-Nearest Neighbor (k-NN) graph initialization. GNN-Descent speeds up the similarity comparison by a two-phase descent procedure and enables highly parallelized neighbor updates. Next, aiming to support various k-NN graph pruning strategies, we formulate a universal pruning procedure termed CFS and devise two generalized GPU kernels for parallel processing complex dependencies in neighbor relationships. For large-scale datasets exceeding GPU memory capacity, we propose an asynchronous GPU-CPU-disk indexing framework with a cluster-aware caching mechanism to minimize the I/O pressure on the disk. Extensive experiments on 7 real-world datasets exhibit that Tagore achieves 1.32x to 112.79x speedup while maintaining the index quality.

Deterministic databases are revolutionizing batch transaction processing in shared-nothing architectures, with efficiency largely hinging on minimizing cross-partition operations. However, achieving a universal data partition that eliminates cross-partition operations is often impractical. Thus, developing effective transaction partitioning strategies becomes crucial. Existing methods tend to partition and optimize transactions individually, neglecting the overarching commonalities between transactions within a batch. This oversight results in suboptimal partitioning of transactions that share similar read-write sets, ultimately missing opportunities for global batch execution optimization. In this paper, we present DelayPart, a deterministic database transaction engine that employs a ''wait and see'' strategy to address contextual conflicts between transactions within each batch. DelayPart models transaction batch partitioning as a k -cut problem based on transaction similarity and employs a LSH forest-based approach to approximate solutions efficiently in linear time, factoring in the global overhead of remote operations for each batch. By postponing the allocation and execution of individual transactions, DelayPart systematically analyzes inter-transaction relationships, enhancing overall performance without compromising execution efficiency. We evaluated DelayPart's performance against various benchmarks on a large-scale cluster, demonstrating that it significantly outperforms state-of-the-art transaction partitioning methods.

Natural language (NL)-driven table discovery identifies relevant tables from large table repositories based on NL queries. While current deep-learning-based methods using the traditional dense vector search pipeline, i.e., representation-index-search , achieve remarkable accuracy, they face several limitations that impede further performance improvements: (i) the errors accumulated during the table representation and indexing phases affect the subsequent search accuracy; and (ii) insufficient query-table interaction hinders effective semantic alignment, impeding accuracy improvements. In this paper, we propose a novel framework Birdie, using a differentiate search index. It unifies the indexing and search into a single encoder-decoder language model, thus getting rid of error accumulations. Birdie first assigns each table a prefix-aware identifier and leverages a large language model-based query generator to create synthetic queries for each table. It then encodes the mapping between synthetic queries/tables and their corresponding table identifiers into the parameters of an encoder-decoder language model, enabling deep query-table interactions. During search, the trained model directly generates table identifiers for a given query. To accommodate the continual indexing of dynamic tables, we introduce an index update strategy via parameter isolation, which mitigates the issue of catastrophic forgetting. Extensive experiments demonstrate that Birdie outperforms state-of-the-art dense methods by 16.8% in accuracy, and reduces forgetting by over 90% compared to other continual learning approaches.

Similarity search finds objects that are similar to a given query object based on a similarity metric. As the amount and variety of data continue to grow, similarity search in metric spaces has gained significant attention. Metric spaces can accommodate any type of data and support flexible distance metrics, making similarity search in metric spaces beneficial for many real-world applications, such as multimedia retrieval, personalized recommendation, trajectory analytics, data mining, decision planning, and distributed servers. However, existing studies mostly focus on indexing metric spaces on a single machine, which faces efficiency and scalability limitations with increasing data volume and query amount. Recent advancements in similarity search turn towards distributed methods, while they face challenges including inefficient local data management, unbalanced workload, and low concurrent search efficiency. To this end, we proposeDIMS, an efficientDistributedIndex for similarity search inMetricSpaces. First, we design a novel three-stage heterogeneous partition to achieve workload balance. Then, we present an effective three-stage indexing structure to efficiently manage objects. We also develop concurrent search methods with filtering and validation techniques that support efficient distributed similarity search. Additionally, we devise a cost-based optimization model to balance communication and computation cost. Extensive experiments demonstrate that DIMS significantly outperforms existing distributed similarity search approaches.

Continuous top-$k$query over sliding window is a fundamental challenge in the domain of streaming data management. Specifically, a continuous top-k query$q$monitors the window$W$, returning the$k$objects with the highest scores to the system with each slide of the window. This paper delves into one of its important variants, referred to as multiple continuous top.$k$queries over data stream, which holds significant applications. While various efforts have been made to support continuous top-k query, few have addressed the complexities of multiple continuous top-k queries. The prevailing approach involves selecting a minimal number of objects in the window as candidates, incrementally maintaining them, and using them to support query processing as efficiently as possible. However, these endeavors exhibit sensitivity to the query workload scale or query parameters such as$k$, the window length$n$, and others. Consequently, they incur high running/space cost in updating the candidate set. In this paper, we propose a novel index PH-Tree (Partition and Heap-based Binary Tree), designed to facilitate multiple continuous top-k queries. We partition the query window into a group of disjoint partitions and use PH-Tree to organize these partitions. Additionally, the PH-Tree allows for flexible candidate selection based on the size of each partition, parameter distribution of queries and score distribution of objects. We further develop a group of efficient algorithms to support candidate set incremental maintenance and query processing. The effectiveness and efficiency of the proposed algorithms are validated through extensive theoretical analysis and exneriments detailed in this paper.

Owing to the widespread deployment of smartphones and networked devices, massive amount of data in different types are generated every day, including numeric data, locations, text data, images, etc. Nearest neighbour search in multi-metric spaces has attracted much attention, as it can accommodate any type of data and support search on flexible combinations of multiple metrics. However, most existing methods focus on single metric queries, failing to answer multi-metric queries efficiently due to the complex metric combinations. In this paper, for the first time, we study the approximate nearest neighbour search (ANNS) in multi-metric spaces, and propose HJG, a hierarchical joint graph, to solve the multi-metric query efficiently and effectively. HJG constructs hierarchical graphs for modeling objects of various types, and applies our presented balancing techniques to improve the graph distribution. To support efficient and accurate nearest neighbour search, we join individual graphs dynamically with high efficiency, and develop filtering techniques with efficient search strategy for HJG. Extensive experiments on four datasets demonstrate the superior effectiveness and scalability of our proposed HJG.

Metro system serves as the backbone for urban public transportation. Accurate passenger load prediction for the metro system plays a crucial role in metro service quality improvement, such as helping operators schedule train timetables and passengers plan their trips. However, existing works can only predict low‐grained passenger flows of origin‐destination (O‐D) paths or inflows/outflows of each station but cannot predict passenger load distribution over the whole metro network. To this end, this paper proposes an end‐to‐end inference framework, PIPE, for passenger load prediction of every metro segment between two adjacent stations, by only utilizing smart card data. In particular, PIPE includes two modules. The first is the core. It formulates the travel time distribution of each metro segment as a truncated Gaussian distribution. Since there might be several possible routes for certain O‐D paths, the population‐level travel time distribution of these O‐D paths would be a mixture of travel times of different routes. Considering the route preference may change over time, a dynamic truncated Gaussian mixture model is proposed for parameter inference of each truncated Gaussian distribution of each metro segment. The second module serves as the supplement, which compiles a bunch of methods for predicting passenger flows of O‐D paths. Built upon them, PIPE is able to predict the travel time that future passengers of each O‐D path will take for passing each metro segment and consequently can predict the passenger load of each metro segment in the short future. Numerical studies from Singapore’s metro system demonstrate the efficacy of our method.

Similarity search, the task of identifying objects most similar to a given query object under a specific metric, has gathered significant attention due to its practical applications. However, the absence of coordinate information to accelerate similarity search and the high computational cost of measuring object similarity hinder the efficiency of existing CPU-based methods. Additionally, these methods struggle to meet the demand for high throughput data management. To address these challenges, we propose GTS, a GPU-based tree index designed for the parallel processing of similarity search in general metric spaces, where only the distance metric for measuring object similarity is known. The GTS index utilizes a pivot-based tree structure to efficiently prune objects and employs list tables to facilitate GPU computing. To efficiently manage concurrent similarity queries with limited GPU memory, we have developed a two-stage search method that combines batch processing and sequential strategies to optimize memory usage. The paper also introduces an effective update strategy for the proposed GPU-based index, encompassing streaming data updates and batch data updates. Additionally, we present a cost model to evaluate search performance. Extensive experiments on five real-life datasets demonstrate that GTS achieves efficiency gains of up to two orders of magnitude over existing CPU baselines and up to 20x efficiency improvements compared to state-of-the-art GPU-based methods.

Nearest neighbor search (NNS) is fundamental for high-dimensional space retrieval and impacts various fields, such as pattern recognition, information retrieval, recommendation systems, and vector database management. Among existing NNS methods, graph-based methods often excel in query accuracy and efficiency. However, these methods face significant challenges, including high construction costs and difficulties with dynamic data updates. Recent efforts have focused on combining graph methods with hashing, quantization, and tree-based approaches to address these issues, but problems with large index sizes and update performance remain unresolved. In response, this paper proposes GTI, a novel, lightweight, and dynamic graph-based tree index for high-dimensional NNS. GTI constructs a tree index built across the entire dataset and employs a lightweight graph index at the level 1 of the tree to significantly reduce graph construction costs. It also features effective data insertion and deletion algorithms that enable logarithmic real-time updates. Additionally, we have developed an effective NNS algorithm for GTI, which not only achieves approximate search performance on par with SOTA graph-based methods but also supports exact NNS. Extensive experiments on six real-world datasets demonstrate that GTI achieves an approximately 10× improvement in update efficiency compared to SOTA tree-based methods, while achieving search effectiveness comparable to SOTA approximate NNS methods. These results underscore the potential of GTI for effective application in dynamic and evolving scenarios.

This paper proposes a novel graph structure to address the problems of information spreading in a real-world, frequently updating graph, with two main contributions at hand: accurately tracing infection diffusion according to fine-grained user movements and finding vulnerable vertices under the virus immunization scenario to mitigate infection diffusion. Unlike previous work that primarily predicts the long-term epidemic trend at the census level, this study aims to intervene in the short-term at the individual level. Therefore, two downstream tasks are formulated to illustrate practicalities:EpidemicMitigating in PublicArea problem ($EMA$) andEpidemic MaximizedSpread in PublicArea problem ($ESA$), where$EMA$aims to find intervention strategies, and$ESA$is an adversarial solution against the intervention strategy to test the robustness. Comprehensive experiments are conducted using two real-world datasets with millions of public transport trips, which demonstrate the effectiveness of our approach and highlight the importance of considering the dynamic nature of close contacts in epidemic modelling.

While many countries are developing appropriate actions towards a greener future and moving towards adopting sustainable mobility activities, the real-time management and planning of innovative transportation facilities and services in urban environments still require the development of advanced mobile data management infrastructures. Novel green mobility solutions, such as electric, hybrid, solar and hydrogen vehicles, as well as public and gig-based transportation resources are very likely to reduce the carbon footprint. However, their successful implementation still needs efficient spatio-temporal data management resources and applications to provide a clear picture and demonstrate their effectiveness. This paper discusses the major data management challenges, open issues, and application opportunities closely related to urban green mobility. Additionally, it reports on recent successful experiences and challenging research questions. Furthermore, it highlights the global benefits one can expect when developing green mobility and emphasizes how mobile data infrastructures and services will play a crucial role in achieving these goals.

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.

In this demonstration, we present a fully data driven solution to retrieve passengers’ actual paths within a metro system that are not captured by an Automated Fare Collection (AFC) system. The majority of public transit systems employ AFC systems with smart cards, which record the exact origin, destination, admission time, and exit time of each passenger’s metro trip. Our solution uses AFC data to first infer travel times and route preferences and then estimates the passengers’ travel paths for all trips to provide a statistical view of passengers’ crowdedness inside a metro network over time.

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.

In this modern era, traffic congestion has become a major source of negative economic and environmental impact for urban areas worldwide. One of the most efficient ways to mitigate this issue is through traffic prediction. This research field has evolved greatly ever since its inception in the late 70s. Recently, deep neural network models have gained popularity thanks to its predictive power, but despite this, literature surveys of such methods are rare; making it difficult to ascertain the progress of this research field. In this work, we address this issue by presenting an up-to-date survey of deep neural network for traffic prediction. We provide detailed explanations of popular deep neural network architectures used in the traffic flow prediction literatures, categorize and describe the literatures themselves, present an overview of the commonalities and differences among different works, and finally provide a discussion regarding the challenges and future directions for this field.

Entity Resolution (ER) is a fundamental problem in data preparation. Standard deep ER methods have achieved state-of-the-art effectiveness, assuming that relations from different organizations are centrally stored. However, due to privacy concerns, it can be difficult to centralize data in practice, rendering standard deep ER solutions inapplicable. Despite efforts to develop rule-based privacy-preserving ER methods, they often neglect subtle matching mechanisms and have poor effectiveness as a result. To bridge effectiveness and privacy, in this paper, we propose CampER, an effective framework for privacy-aware deep entity resolution. Specifically, we first design a training pair self-generation strategy to overcome the absence of manually labeled data in privacy-aware scenarios. Based on the self-constructed training pairs, we present a collaborative fine-tuning approach to learn the match-aware and uni-space individual tuple embeddings for accurate matching decisions. During the matching decision-making process, we first introduce a cryptographically secure approach to determine matches. Furthermore, we propose an order-preserving perturbation strategy to significantly accelerate the matching computation while guaranteeing the consistency of ER results. Extensive experiments on eight widely-used benchmark datasets demonstrate that CampER not only is comparable with the state-of-the-art standard deep ER solutions in effectiveness, but also preserves privacy.

k-closest pair (KCP for short) search is a fundamental problem in database research. Given a set of d-dimensional streaming data S, KCP search aims to retrieve k pairs with the shortest distances between them. While existing works have studied continuous 1-closest pair query (i.e., k=1) over dynamic data environments, which allow for object insertions/deletions, they require high computational costs and cannot easily support KCP search with k>1. This paper investigates the problem of KCP search over data stream, aiming to incrementally maintain as few pairs as possible to support KCP search with arbitrarily k. To achieve this, we introduce the concept of NNS (short for N earest N eighbour pair- S et), which consists of all the nearest neighbour pairs and allows us to support KCP search via only accessing O(k) objects. We further observe that in most cases, we only need to use a small portion of NNS to answer KCP search as typically kłl n. Based on this observation, we propose TNNS (short for T hreshold-based NN pair S et), which contains a small number of high-quality NN pairs, and a partition named τ-DLBP (short for τ- D istance L ower- B ound based P artition) to organize objects, with τ being an integer significantly smaller than n. τ-DLBP organizes objects using up to O(łog n / τ) partitions and is able to support the construction and update of TNNS efficiently.

Trajectory data has the potential to greatly benefit a wide-range of real-world applications, such as tracking the spread of the disease through people's movement patterns and providing personalized location-based services based on travel preference. However, privacy concerns and data protection regulations have limited the extent to which this data is shared and utilized. To overcome this challenge, local differential privacy provides a solution by allowing people to share a perturbed version of their data, ensuring privacy as only the data owners have access to the original information. Despite its potential, existing point-based perturbation mechanisms are not suitable for real-world scenarios due to poor utility, dependence on external knowledge, high computational overhead, and vulnerability to attacks. To address these limitations, we introduce LDPTrace, a novel locally differentially private trajectory synthesis framework. Our framework takes into account three crucial patterns inferred from users' trajectories in the local setting, allowing us to synthesize trajectories that closely resemble real ones with minimal computational cost. Additionally, we present a new method for selecting a proper grid granularity without compromising privacy. Our extensive experiments using real-world as well as synthetic data, various utility metrics and attacks, demonstrate the efficacy and efficiency of LDPTrace.

Passenger satisfaction is extremely important for the success of a public transportation system. Many studies have shown that passenger satisfaction strongly depends on the time they have to wait at the bus stop (waiting time) to get on a bus. To be specific, user satisfaction drops faster as the waiting time increases. Therefore, service providers want to provide a bus to the waiting passengers within a threshold to keep them satisfied. It is a two-pronged problem: (a) to satisfy more passengers the transport planner may increase the frequency of the buses, and (b) in turn, the increased frequency may impact the service operational costs. To address it, we propose PASS and COST as the two variants that satisfy different optimization criteria mentioned above. The optimization goal of PASS is the number of satisfied passengers while the optimization goal of COST is the number of passengers served per unit of driving time. Consequently, PASS utilizes resources to the maximum to satisfy the highest number of passengers, while COST optimizes for both passenger satisfaction and operational costs. Accordingly, we propose two algorithms to solve PASS and COST respectively and evaluate their performance based on real passenger demand data-set.

Entity Matching (EM) aims to identify whether two tuples refer to the same real-world entity and is well-known to be labor-intensive. It is a prerequisite to anomaly detection, as comparing the attribute values of two matched tuples from two different datasets provides one effective way to detect anomalies. Existing EM approaches, due to insufficient feature discovery or error-prone inherent characteristics, are not able to achieve stable performance. In this paper, we present${{\sf CollaborEM}}$, a self-supervised entity matching framework via multi-features collaboration. It is capable of (i) obtaining reliable EM results with zero human annotations and (ii) discovering adequate tuples’ features in a fault-tolerant manner.${{\sf CollaborEM}}$consists of two phases, i.e., automatic label generation (ALG) and collaborative EM training (CEMT). In the first phase, ALG is proposed to generate a set of positive tuple pairs and a set of negative tuple pairs. ALG guarantees the high quality of the generated tuples, and hence ensures the training quality of the subsequent CEMT. In the second phase, CEMT is introduced to learn the matching signals by discovering graph features and sentence features of tuples collaboratively. Extensive experimental results over eight real-world EM benchmarks show that${{\sf CollaborEM}}$outperforms all the existing unsupervised EM approaches and is comparable or even superior to the state-of-the-art supervised EM methods.

Knowledge graph (KG) plays an increasingly important role to improve the recommendation performance and interpretability. A recent technical trend is to design end-to-end models based on the information propagation schemes. However, existing propagation-based methods fail to (1) model the underlying hierarchical structures and relations, and (2) capture the high-order collaborative signals of items for learning high-quality user and item representations.

The ubiquity of implicit feedback makes them the default choice to build modern recommender systems. Generally speaking, observed interactions are considered as positive samples, while unobserved interactions are considered as negative ones. However, implicit feedback is inherently noisy because of the ubiquitous presence of noisy-positive and noisy-negative interactions. Recently, some studies have noticed the importance of denoising implicit feedback for recommendations, and enhanced the robustness of recommendation models to some extent. Nonetheless, they typically fail to (1) capture the hard yet clean interactions for learning comprehensive user preference, and (2) provide a universal denoising solution that can be applied to various kinds of recommendation models.

Similarity search finds similar objects for a given query object based on a certain similarity metric. Similarity search in metric spaces has attracted increasing attention, as the metric space can accommodate any type of data and support flexible distance metrics. However, a metric space only models a single data type with a specific similarity metric. In contrast, a multi-metric space combines multiple metric spaces to simultaneously model a variety of data types and a collection of associated similarity metrics. Thus, a multi-metric space is capable of performing similarity search over any combination of metric spaces. Many studies focus on indexing a single metric space, while only a few aims at indexing multi-metric space to accelerate similarity search. In this paper, we propose DESIRE, an efficient dynamic cluster-based forest index for similarity search in multi-metric spaces. DESIRE first selects high-quality centers to cluster objects into compact regions, and then employs B+-trees to effectively index distances between centers and corresponding objects. To support dynamic scenarios, efficient update strategies are developed. Further, we provide filtering techniques to accelerate similarity queries in multi-metric spaces. Extensive experiments on four real datasets demonstrate the superior efficiency and scalability of our proposed DESIRE compared with the state-of-the-art multi-metric space indexes.

Text classification is a fundamental task in content analysis. Nowadays, deep learning has demonstrated promising performance in text classification compared with shallow models. However, almost all the existing models do not take advantage of the wisdom of human beings to help text classification. Human beings are more intelligent and capable than machine learning models in terms of understanding and capturing the implicit semantic information from text. In this article, we try to take guidance from human beings to classify text. We propose Crowd-powered learning for Text Classification (CrowdTC for short). We design and post the questions on a crowdsourcing platform to extract keywords in text. Sampling and clustering techniques are utilized to reduce the cost of crowdsourcing. Also, we present an attention-based neural network and a hybrid neural network to incorporate the extracted keywords as human guidance into deep neural networks. Extensive experiments on public datasets confirm that CrowdTC improves the text classification accuracy of neural networks by using the crowd-powered keyword guidance.

Time-varying dynamic Bayesian network (TVDBN) is essential for describing time-evolving directed conditional dependence structures in complex multivariate systems. In this article, we construct a TVDBN model, together with a score-based method for its structure learning. The model adopts a vector autoregressive (VAR) model to describe inter-slice and intra-slice relations between variables. By allowing VAR parameters to change segment-wisely over time, the time-varying dynamics of the network structure can be described. Furthermore, considering some external information can provide additional similarity information of variables. Graph Laplacian is further imposed to regularize similar nodes to have similar network structures. The regularized maximum a posterior estimation in the Bayesian inference framework is used as a score function for TVDBN structure evaluation, and the alternating direction method of multipliers (ADMM) with L-BFGS-B algorithm is used for optimal structure learning. Thorough simulation studies and a real case study are carried out to verify our proposed method’s efficacy and efficiency.

Reorganizing bus frequencies to cater for the actual travel demands can significantly save the cost of the public transport system. Many, if not all, previous studies formulate this as a bus frequency optimization problem that tries to minimize passengers’ average waiting time. On the other hand, many investigations have confirmed that the user satisfaction drops faster as the waiting time increases. Consequently, this paper studies the bus frequency optimization problem considering the user satisfaction. Specifically, for the first time to our best knowledge, we study how to schedule the buses such that the total number of passengers who could receive their bus services within the waiting time threshold can be maximized. We propose two variants of the problem, FAST and FASTCO, to cater for different application needs and prove that both are NP-hard. To solve FAST effectively and efficiently, we first present an index-based$(1-1/e)$-approximation algorithm. By exploiting the locality property of routes in a bus network, we further propose a partition-based greedy method that achieves a$(1-\rho)(1-1/e)$approximation ratio. Then we propose a progressive partition-based greedy method to further boost the efficiency while achieving a$(1-\rho)(1-1/e-\varepsilon)$approximation ratio. For the FASTCO problem, two greedy-based heuristic methods are proposed. Experiments on a real city-wide bus dataset in Singapore have been conducted to verify the efficiency, effectiveness, and scalability of our methods in addressing FAST and FASTCO respectively.

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.

In this modern era, traffic congestion has become a major source of severe negative economic and environmental impact for urban areas worldwide. One of the most efficient ways to mitigate traffic congestion is through future traffic prediction. The research field of traffic prediction has evolved greatly ever since its inception in the late 70s. Earlier studies mainly use classical statistical models such as ARIMA and its variants. Recently, researchers have started to focus on machine learning models because of their power and flexibility. As theoretical and technological advances emerge, we enter the era of deep neural network, which gained popularity due to its sheer prediction power which can be attributed to the complex and deep structure. Despite the popularity of deep neural network models in the field of traffic prediction, literature surveys of such methods are rare. In this work, we present an up-to-date survey of deep neural network for traffic prediction. We will provide a detailed explanation of popular deep neural network architectures commonly used in the traffic flow prediction literatures, categorize and describe the literatures themselves, present an overview of the commonalities and differences among different works, and finally provide a discussion regarding the challenges and future directions for this field.

A robust Origin-Destination (OD) prediction is key to urban mobility. A good forecasting model can reduce operational risks and improve service availability, among many other upsides. Here, we examine the use of Graph Convolutional Net-work (GCN) and its hybrid Markov-Chain (GCN-MC) variant to perform a context-aware OD prediction based on a large-scale public transportation dataset in Singapore. Compared with the baseline Markov-Chain algorithm and GCN, the proposed hybrid GCN-MC model improves the prediction accuracy by 37% and 12% respectively. Lastly, the addition of temporal and historical contextual information further improves the performance of the proposed hybrid model by 4 –12%.

Tensor decomposition is a fundamental multidimensional data analysis tool for many data-driven applications, such as social computing, computer vision, and bioinformatics, to name but a few. However, the rapidly increasing streaming data nowadays introduces new challenges to traditional static tensor decomposition. It requires an efficient distributed dynamic tensor decomposition without re-computing the whole tensor from scratch. In this paper, we propose DisMASTD, an efficient distributed multi-aspect streaming tensor decomposition. First, we prove the optimal tensor partitioning problem is NP-hard. Second, we present two heuristic tensor partitioning approaches to ensure the load balancing. Third, we develop a distributed multi-aspect streaming tensor decomposition computation method, which avoids repetitive computation and reduces network communication by maintaining and reusing the intermediate results. Last but not least, we perform extensive experiments with both real and synthetic datasets to demonstrate the efficiency and scalability of DisMASTD.

Entity alignment (EA) is a prerequisite for enlarging the coverage of a unified knowledge graph. Previous EA approaches either restrain the performance due to inadequate information utilization or need labor-intensive pre-processing to get external or reliable information to perform the EA task. This paper proposes EASY, an effective end-to-end EA framework, which is able to (i) remove the labor-intensive pre-processing by fully discovering the name information provided by the entities themselves; and (ii) jointly fuse the features captured by the names of entities and the structural information of the graph to improve the EA results. Specifically, EASY first introduces NEAP, a highly effective name-based entity alignment procedure, to obtain an initial alignment that has reasonable accuracy and meanwhile does not require much memory consumption or any complex training process. Then, EASY invokes SRS, a novel structure-based refinement strategy, to iteratively correct the misaligned entities generated by NEAP to further enhance the entity alignment. Extensive experiments demonstrate the superiority of our proposed EASY with significant improvement against 13 existing state-of-the-art competitors.

Influence maximization has been studied extensively from the perspective of the influencer. However, the influencer typically purchases influence from a provider, for example in the form of purchased advertising. In this paper, we study the problem from the perspective of the influence provider. Specifically, we focus on influence providers who sell Out-of-Home (OOH) advertising on billboards. Given a set of requests from influencers, how should an influence provider allocate resources to minimize regret, whether due to forgone revenue from influencers whose needs were not met or due to over-provisioning of resources to meet the needs of influencers? We formalize this as the \underlineM inimizing \underlineR egret for the \underlineO OH \underlineA dvertising \underlineM arket problem (\problem). We show that \problem is both NP-hard and NP-hard to approximate within any constant factor. The regret function is neither monotone nor submodular, which renders any straightforward greedy approach ineffective. Therefore, we propose a randomized local search framework with two neighborhood search strategies, and prove that one of them ensures an approximation factor to a dual problem of \problem. Experiments on real-world user movement and billboard datasets in New York City and Singapore show that on average our methods outperform the baselines in effectiveness by five times.

Entity alignment (EA) aims to find equivalent entities in different knowledge graphs (KGs). Current EA approaches suffer from scalability issues, limiting their usage in real-world EA scenarios. To tackle this challenge, we propose LargeEA to align entities between large-scale KGs. LargeEA consists of two channels, i.e., structure channel and name channel. For the structure channel, we present METIS-CPS, a memory-saving mini-batch generation strategy, to partition large KGs into smaller mini-batches. LargeEA, designed as a general tool, can adopt any existing EA approach to learn entities' structural features within each mini-batch independently. For the name channel, we first introduce NFF, a name feature fusion method, to capture rich name features of entities without involving any complex training process; we then exploit a name-based data augmentation to generate seed alignment without any human intervention. Such design fits common real-world scenarios much better, as seed alignment is not always available. Finally, LargeEA derives the EA results by fusing the structural features and name features of entities. Since no widely-acknowledged benchmark is available for large-scale EA evaluation, we also develop a large-scale EA benchmark called DBP1M extracted from real-world KGs. Extensive experiments confirm the superiority of LargeEA against state-of-the-art competitors.

To improve the classification performance of support vector machines (SVMs) on imbalanced datasets, cost-sensitive learning methods have been proposed, e.g., Different Error Costs (DEC) and Fuzzy SVM for Class Imbalance Learning (FSVM-CIL). They relocate the hyperplane by adjusting the costs associated with misclassifying samples. However, the error costs are determined either empirically or by performing an exhaustive search in the parameter space. Both strategies can not guarantee effectiveness and efficiency simultaneously. In this paper, we proposeATEC, a solution that can efficiently find a preferable hyperplane by automatically tuning the error cost for between-class samples.ATECdistinguishes itself from all existing parameter tuning strategies by two main features: (1) it can evaluate how effective an error cost is in terms of classification accuracy; and (2) it changes the error cost in the right direction if it is not effective. Extensive experiments show that compared with the state-of-art methods, SVMs that are equipped withATECcan not only obtain comparable improvements in terms of F1 score of minority class, area under the precision-recall curve (AUC-PR) and area under the ROC curve (AUC-ROC) scores, but also outperform the grid-search parameter tuning strategy by two orders of magnitude in terms of the training time when a high F1 score is required.

An alternative to current mainstream preprocessing methods is proposed: Value Selection (VS). Unlike the existing methods such as feature selection that removes features and instance selection that eliminates instances, value selection eliminates the values (with respect to each feature) in the dataset with two purposes: reducing the model size and preserving its accuracy. Two probabilistic methods based on information theory's metric are proposed: PVS and P+VS. Extensive experiments on the benchmark datasets with various sizes are elaborated. Those results are compared with the existing preprocessing methods such as feature selection, feature transformation, and instance selection methods. Experiment results show that value selection can achieve the balance between accuracy and model size reduction.

In this paper, we demonstrate a satisfaction-boosting bus scheduling assistant called FASTS, which assists users to find an optimal bus schedule. FASTS performs bus scheduling based on the constraints specified by the user in either a coarse-grained or a fine-grained manner, supports different explorations with a varying number of constraints, and provides analysis to quantify the performance of bus schedules and presents the results in a visually pleasing way. We demonstrate FASTS using real-world bus routes (396 routes) and one-week bus touch-on/touch-off records (28 million trip records) in Singapore.

Moving objects equipped with location-positioning devices continuously generate a large amount of spatio-temporal trajectory data. An interesting finding over a trajectory stream is a group of objects that are travelling together for a certain period of time. We observe that existing studies on mining co-moving objects do not consider an important correlation between co-moving objects, which is the reoccurrence of the co-moving pattern. In this study, we propose the problem of finding recurrent co-moving patterns from streaming trajectories, enabling us to discover recent co-moving patterns that are repeated within a given time period. Experimental results on real-life trajectory data verify the efficiency and effectiveness of our method.

In this paper, we aim at studying the group travel behaviour (GTB) patterns from large-scale auto fare collection (AFC) data. GTB is defined as two or more commuters intentionally and regularly traveling together from an origin to a destination. We propose a method to identify GTB accurately and efficiently and apply our method to the Singapore AFC dataset to reveal the GTB patterns of Singapore commuters. The case study proves that our method is able to identify GTB patterns more accurately and efficiently than the state-of-the-art.

Moving objects equipped with location-positioning devices continuously generate a large amount of spatio-temporal trajectory data. An interesting finding over a trajectory stream is a group of objects that are travelling together for a certain period of time. Existing studies on mining co-moving objects do not consider an important correlation between co-moving objects, which is the reoccurrence of the movement pattern. In this study, we define a problem of finding recurrent pattern of co-moving objects from streaming trajectories and propose an efficient solution that enables us to discover recent co-moving object patterns repeated within a given time period. Experimental results on a real-life trajectory database show the efficiency of our method.

Recording and querying time-stamped trajectories incurs high cost of data storage and computing. In this paper, we explore characteristics of the trajectories in road networks, which have motivated the idea of coding trajectories by associating timestamps with relative spatial path and locations. Such a representation contains large number of duplicate information to achieve a lower entropy compared with the existing representations, thereby drastically cutting the storage cost. We propose techniques to compress spatial path and locations separately, which can support fast positioning and achieve better compression ratio. For locations, we propose two novel encoding schemes such that the binary code can preserve distance information, which is very helpful for LBS applications. In addition, an unresolved question in this area is whether it is possible to perform search directly on the compressed trajectories, and if the answer is yes, then how. Here we show that directly querying compressed trajectories based on our encoding scheme is possible and can be done efficiently.We design a set of primitive operations for this purpose, and propose index structures to reduce query response time. We demonstrate the advantage of our method and compare it against existing ones through a thorough experimental study on real trajectories in road network.

Similarity queries, including range queries and k nearest neighbor ( k NN) queries, in metric spaces have applications in many areas such as multimedia retrieval, computational biology and location-based services. With the growing volumes of data, a distributed method is required. In this paper, we propose an A synchronous M etric D istributed S ystem (AMDS), to support efficient metric similarity queries in the distributed environment. AMDS uniformly partitions the data with the pivot-mapping technique to ensure the load balancing, and employs publish/subscribe communication model to asynchronous process large scale of queries. The employment of asynchronous processing model also improves robustness and efficiency of AMDS. In addition, we develop efficient similarity search algorithms using AMDS. Extensive experiments using real and synthetic data demonstrate the performance of metric similarity queries using AMDS. Moreover, the AMDS scales sublinearly with the growing data size.

The mass rapid transit (MRT) network is playing an increasingly important role in Singapore's transit network, thanks to its advantages of higher capacity and faster speed. Unfortunately, due to aging infrastructure, increasing demand, and other reasons like adverse weather condition, commuters in Singapore recently have been facing increasing unexpected train delays (UTDs), which has become a source of frustration for both commuters and operators. Most, if not all, existing works on delay management do not consider commuters' behavior. We dedicate this paper to the study of commuters' behavior during UTDs. We adopt a data-driven approach to analyzing the six-month' real data collected by automated fare collection system in Singapore and build a classification model to predict whether commuters switch from MRT to other transportation modes because of UTDs.

Continuous top-k query over streaming data is a fundamental problem in database. In this paper, we focus on sliding window scenario, where a continuous top-k query returns the top-k objects within each query window on the data stream. Existing algorithms support this type of queries via incrementally maintaining a subset of objects in the window and try to retrieve the answer from this subset as much as possible whenever the window slides. However, since all the existing algorithms are sensitive to query parameters and data distribution, they all suffer from expensive incremental maintenance cost. In this paper, we propose a self-adaptive partition framework to support continuous top-k query. It partitions the window into subwindows and only maintains a small number of candidates with highest scores in each sub-window. Based on this framework, we have developed several partition algorithms to cater for different object distributions and query parameters. It is the first algorithm that achieves logarithmic complexity w.r.t. k for incremental maintaining the candidate set even in the worst case.

Massive amounts of images textually annotated by different users are provided by social image websites, e.g., Flickr. Social images are always associated with various information, such as visual features, tags, and users. In this paper, we utilize hypergraph instead of ordinary graph to model social images, since relations among various information are more sophisticated than pairwise. Based on the hypergraph, we propose HIRT, a scalable image retrieval and tagging system, which uses Personalized PageRank to measure vertex similarity, and employs top-k search to support image retrieval and tagging. To achieve good scalability and efficiency, we develop parallel and approximate top-k search algorithms with quality guarantees. Experiments on a large Flickr dataset confirm the effectiveness and efficiency of our proposed system HIRT compared with existing state-of-the-art hypergraph based image retrieval system. In addition, our parallel and approximate top-k search methods are verified to be more efficient than the state-of-the-art methods and meanwhile achieve higher result quality.

Given two object sets Q and O, a metric similarity join finds similar object pairs according to a certain criterion. This operator has a wide range of applications in data cleaning, data mining, etc. In this paper, we employ a popular distributed framework, namely, MapReduce, to support scalable metric similarity joins. To ensure load balancing, we present two sampling based partition methods, i.e., clustering based partition method and KD-tree based partition method. To avoid unnecessary object pair evaluation, we propose a framework that maps the two involved object sets in order, where plane sweeping and pivot based filtering techniques are utilized for pruning. Extensive experiments confirm that our solution outperforms significantly existing state-of-the-art competitors.

Nowadays, many location-based applications require the ability of querying k-nearest neighbors over a very large scale of moving objects in road networks, e.g., taxi-calling and ride-sharing services. Traditional grid index with equal-sized cells can not adapt to the skewed distribution of moving objects in real scenarios. Thus, to obtain the fast querying response time, the grid needs to be split into more smaller cells which introduces the side-effect of higher memory cost, i.e., maintaining such a large volume of cells requires a much larger memory space at the server side. In this paper, we present SIMkNN, a scalable and in-memory kNN query processing technique. SIMkNN is dual-index driven, where we adopt a R-tree to store the topology of the road network and a hierarchical grid model to manage the moving objects in non-uniform distribution. To answer a kNN query in real time, SIMkNN adopts the strategy that incrementally enlarges the search area for network distance based nearest neighbor evaluation. It is far from trivial to perform the space expansion within the hierarchical grid index. For a given cell, we first define its neighbors in different directions, then propose a cell communication technique which allows each cell in the hierarchical grid index to be aware of its neighbors at anytime. Accordingly, an efficient space expansion algorithm to generate the estimation area is proposed. The experimental evaluation shows that SIMkNN outperforms the baseline algorithm in terms of time and memory efficiency.

Recording and querying time-stamped trajectories incurs high cost of data storage and computing. In this paper, we explore several characteristics of the trajectories in road networks, which have motivated the idea of coding trajectories by associating timestamps with relative spatial path and locations. Such a representation contains a large number of duplicate information to achieve a lower entropy compared with the existing representations, thereby drastically cutting the storage cost. We propose several techniques to compress spatial path and locations separately, which can support fast positioning and achieve better compression ratio. For locations, we propose two novel encoding schemes such that the binary code can preserve distance information, which is very helpful for LBS applications. In addition, an unresolved question in this area is whether it is possible to perform a search directly on the compressed trajectories, and if the answer is yes, then how. Here, we show that directly querying compressed trajectories based on our encoding scheme is possible and can be done efficiently. We design a set of primitive operations for this purpose, and propose index structures to reduce query response time. We demonstrate the advantage of our method and compare it against existing ones through a thorough experimental study on real trajectories in road network.

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.

This paper explores the causality and responsibility problem (CRP) for the non-answers to probabilistic reverse skyline queries (PRSQ). Towards this, we propose an efficient algorithm called CP to compute the causality and responsibility for the non-answers to PRSQ. CP first finds candidate causes, and then, it performs verification to obtain actual causes with their responsibilities, during which several strategies are used to boost efficiency. Extensive experiments using both real and synthetic data sets demonstrate the effectiveness and efficiency of the presented algorithms.

The general notion of a metric space encompasses a diverse range of data types and accompanying similarity measures. Hence, metric search plays an important role in a wide range of settings, including multimedia retrieval, data mining, and data integration. With the aim of accelerating metric search, a collection of pivot-based indexing techniques for metric data has been proposed, which reduces the number of potentially expensive similarity comparisons by exploiting the triangle inequality for pruning and validation. However, no comprehensive empirical study of those techniques exists. Existing studies each offers only a narrower coverage, and they use different pivot selection strategies that affect performance substantially and thus render cross-study comparisons difficult or impossible. We offer a survey of existing pivot-based indexing techniques, and report a comprehensive empirical comparison of their construction costs, update efficiency, storage sizes, and similarity search performance. As part of the study, we provide modifications for two existing indexing techniques to make them more competitive. The findings and insights obtained from the study reveal different strengths and weaknesses of different indexing techniques, and offer guidance on selecting an appropriate indexing technique for a given setting.

Given two object sets Q and O, a metric similarity join finds similar object pairs according to a certain criterion. This operation has a wide variety of applications in data cleaning and data mining, to name but a few. However, the rapidly growing volume of data nowadays challenges traditional metric similarity join methods, and thus, a distributed method is required. In this paper, we adopt a popular distributed framework, namely, MapReduce, to support scalable metric similarity joins. To ensure the load balancing, we present two sampling based partition methods. One utilizes the pivot and the space-filling curve mappings to cluster the data into one-dimensional space, and then selects high quality centroids to enable equal-sized partitions. The other uses the KD-tree partitioning technique to equally divide the data after the pivot mapping. To avoid unnecessary object pair evaluation, we propose a framework that maps the two involved object sets in order, where the range-object filtering, the double-pivot filtering, the pivot filtering, and the plane sweeping techniques are utilized for pruning. Extensive experiments with both real and synthetic data sets demonstrate that our solutions outperform significantly existing state-of-the-art competitors.

Continuous top-k query over streaming data is a fundamental problem in database. In this paper, we focus on the sliding window scenario, where a continuous top-k query returns the top-k objects within each query window on the data stream. Existing algorithms support this type of queries via incrementally maintaining a subset of objects in the window and try to retrieve the answer from this subset as much as possible whenever the window slides. However, since all the existing algorithms are sensitive to query parameters and data distribution, they all suffer from expensive incremental maintenance cost. In this paper, we propose a self-adaptive partition framework to support continuous top-k query. It partitions the window into sub-windows and only maintains a small number of candidates with highest scores in each sub-window. Based on this framework, we have developed several partition algorithms to cater for different object distributions and query parameters. To our best knowledge, it is the first algorithm that achieves logarithmic complexity w.r.t. k for incrementally maintaining the candidate set even in the worstcase scenarios.

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.

The top-k dominating (TKD) query returns the k objects that dominate the maximum number of the objects in a given dataset. Incomplete data exists in a wide spectrum of real datasets, due to device failure, privacy preservation, data loss, etc. In this paper, for the first time, we carry out a systematic study of TKD queries on incomplete data, which involves the data having some missing dimensional value(s). We formalize this problem, and propose a suite of efficient algorithms for supporting it. Our methods utilize some novel techniques, such as upper bound score pruning and bitmap binning strategy, to boost query efficiency. Extensive experiments with both real and synthetic data sets demonstrate the efficiency of our presented algorithms.

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.

Causality and responsibility is an essential tool in the database community for providing intuitive explanations for answers/non-answers to queries. Causality denotes the causes for the answers/non-answers to queries, and responsibility represents the degree of a cause which reflects its influence on the answers/non-answers to queries. In this paper, we study the causality and responsibility problem (CRP) for the non-answers to probabilistic reverse skyline queries (PRSQ). We first formalize CRP on PRSQ, and then, we propose an efficient algorithm termed as CP to compute the causality and responsibility for the non-answers to PRSQ. CP first finds candidate causes, and then, it performs verification to obtain actual causes with their responsibilities, during which several strategies are used to boost efficiency. Further, we explore the CRP for the non-answers to reverse skyline queries. Towards this, we extend CP to identify directly all the actual causes and their responsibilities for a non-answer to reverse skyline queries without additional verification. Extensive experiments using both real and synthetic data sets demonstrate the effectiveness and efficiency of our presented algorithms.

The top-k dominating (TKD) query returns the k objects that dominate the maximum number of objects in a given dataset. It combines the advantages of skyline and top-k queries, and plays an important role in many decision support applications. Incomplete data exists in a wide spectrum of real datasets, due to device failure, privacy preservation, data loss, and so on. In this paper, for the first time, we carry out a systematic study of TKD queries on incomplete data, which involves the data having some missing dimensional value(s). We formalize this problem, and propose a suite of efficient algorithms for answering TKD queries over incomplete data. Our methods employ some noveltechniques, such as upper bound score pruning, bitmap pruning, and partial score pruning, to boost query efficiency. Extensive experimental evaluation using both real and synthetic datasets demonstrates the effectiveness of our developed pruning heuristics and the performance of our presented algorithms.

The problem of finding matches of a regular expression (RE) on a string exists in many applications, such as text editing, biosequence search, and shell commands. Existing techniques first identify candidates using substrings in the RE, then verify each of them using an automaton. These techniques become inefficient when there are many candidate occurrences that need to be verified. In this article, we propose a novel technique that prunes false negatives by utilizing negative factors , which are substrings that cannot appear in an answer. A main advantage of the technique is that it can be integrated with many existing algorithms to improve their efficiency significantly. We present a detailed description of this technique. We develop an efficient algorithm that utilizes negative factors to prune candidates, then improve it by using bit operations to process negative factors in parallel. We show that negative factors, when used with necessary factors (substrings that must appear in each answer), can achieve much better pruning power. We analyze the large number of negative factors, and develop an algorithm for finding a small number of high-quality negative factors. We conducted a thorough experimental study of this technique on real datasets, including DNA sequences, proteins, and text documents, and show significant performance improvement of the state-of-the-art tools by an order of magnitude.

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.

Existing works on identity privacy protection on social networks make the assumption that all the user identities in a social network are private and ignore the fact that in many real-world social networks, there exists a considerable amount of users such as celebrities, media users, and organization users whose identities are public. In this paper, we demonstrate that the presence of public users can cause serious damage to the identity privacy of other ordinary users. Motivated attackers can utilize the connection information of a user to some known public users to perform re-identification attacks, namely connection fingerprint (CFP) attacks. We propose two k-anonymization algorithms to protect a social network against the CFP attacks. One algorithm is based on adding dummy vertices. It can resist powerful attackers with the connection information of a user with the public users within n hops (n ≥ 1) and protect the centrality utility of public users. The other algorithm is based on edge modification. It is only able to resist attackers with the connection information of a user with the public users within 1 hop but preserves a rich spectrum of network utility. We perform comprehensive experiments on real-world networks and demonstrate that our algorithms are very efficient in terms of the running time and are able to generate k-anonymized networks with good utility.

Range queries in metric spaces have applications in many areas such as multimedia retrieval, computational biology, and location-based services, where metric uncertain data exists in different forms, resulting from equipment limitations, high-throughput sequencing technologies, privacy preservation, or others. In this paper, we represent metric uncertain data by using an object-level model and a bi-level model, respectively. Two novel indexes, the uncertain pivot B+-tree (UPB-tree) and the uncertain pivot B+-forest (UPB-forest), are proposed accordingly in order to support probabilistic range queries w.r.t. a wide range of uncertain data types and similarity metrics. Both index structures use a small set of effective pivots chosen based on a newly defined criterion, and employ the B+-tree(s) as the underlying index. By design, they are easy to be integrated into any existing DBMS. In addition, we present efficient metric probabilistic range query algorithms, which utilize the validation and pruning techniques based on our derived probability lower and upper bounds. Extensive experiments with both real and synthetic data sets demonstrate that, compared against existing state-of-the-art indexes for metric uncertain data, the UPB-tree and UPB-forest incur much lower construction costs, consume smaller storage spaces, and can support more efficient metric probabilistic range queries.

Why-not questions, which aim to seek clarifications on the missing tuples for query results, have recently received considerable attention from the database community. In this paper, we systematically explore why-not questions on reverse top-k queries , owing to its importance in multi-criteria decision making. Given an initial reverse top- k query and a missing/why-not weighting vector set W m that is absent from the query result, why-not questions on reverse top- k queries explain why W m does not appear in the query result and provide suggestions on how to refine the initial query with minimum penalty to include W m in the refined query result. We first formalize why-not questions on reverse top- k queries and reveal their semantics, and then propose a unified framework called WQRTQ to answer why-not questions on both monochromatic and bichromatic reverse top- k queries. Our framework offers three solutions, namely, (i) modifying a query point q , (ii) modifying a why-not weighting vector set W m and a parameter k , and (iii) modifying q , W m , and k simultaneously, to cater for different application scenarios. Extensive experimental evaluation using both real and synthetic data sets verifies the effectiveness and efficiency of the presented algorithms.

Reverse k nearest neighbor (RkNN) queries have a broad application base such as decision support, profile-based marketing, and resource allocation. Previous work on RkNN search does not take textual information into consideration or limits to the Euclidean space. In the real world, however, most spatial objects are associated with textual information and lie on road networks. In this paper, we introduce a new type of queries, namely, reverse top-k Boolean spatial keyword (RkBSK) retrieval, which assumes objects are on the road network and considers both spatial and textual information. Given a data set P on a road network and a query point q with a set of keywords, an RkBSK query retrieves the points in P that have q as one of answer points for their top-k Boolean spatial keyword queries. We formalize the RkBSK query and then propose filter-and-refinement framework based algorithms for answering RkBSK search with arbitrary k and no any pre-computation. To accelerate the query process, several novel pruning heuristics that utilize both spatial and textual information are employed to shrink the search space efficiently. In addition, a new data structure called count tree has been developed to further improve query performance. A comprehensive experimental evaluation using both real and synthetic data sets demonstrates the effectiveness of our presented pruning heuristics and the performance of our proposed algorithms.

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.

Researchers have begun studying content obtained from microblogging services such as Twitter to address a variety of technological, social, and commercial research questions. The large number of Twitter users and even larger volume of tweets often make it impractical to collect and maintain a complete record of activity; therefore, most research and some commercial software applications rely on samples, often relatively small samples, of Twitter data. For the most part, sample sizes have been based on availability and practical considerations. Relatively little attention has been paid to how well these samples represent the underlying stream of Twitter data. To fill this gap, this article performs a comparative analysis on samples obtained from two of Twitter’s streaming APIs with a more complete Twitter dataset to gain an in-depth understanding of the nature of Twitter data samples and their potential for use in various data mining tasks.

This exploratory work studies hashtag diffusion in Twitter. The analysis is conducted from two aspects. From the macro perspective, we study general properties of hashtag diffusion, and classify hashtags into three main classes based on their temporal dynamics referred as “single spike”, “multi-spikes”, and “fluctuation”, and find that each of these classes has some unique characteristics. From the micro perspective, we investigate individual diffusion.We adopt Edelman's “topology of influence” theory to identify four type of users with different influence levels in diffusion based on their dynamic retweet behaviors. The results of our study are useful for gaining more insights of information diffusion in Twitter.

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.

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.

Enriching many location-based applications, various new skyline queries are proposed and formulated based on the notion of locational dominance, which extends conventional one by taking objects' nearness to query positions into account additional to objects' nonspatial attributes. To answer a representative class of skyline queries for location-based applications efficiently, this paper presents two index-based approaches, namely, augmented R-tree and dominance diagram. Augmented R-tree extends R-tree by including aggregated nonspatial attributes in index nodes to enable dominance checks during index traversal. Dominance diagram is a solution-based approach, by which each object is associated with a precomputed nondominance scope wherein query points should have the corresponding object not locationally dominated by any other. Dominance diagram enables skyline queries to be evaluated via parallel and independent comparisons between nondominance scopes and query points, providing very high search efficiency. The performance of these two approaches is evaluated via empirical studies, in comparison with other possible approaches.

In this paper, we present a new system framework called ROAD for spatial object search on road networks. ROAD is extensible to diverse object types and efficient for processing various location-dependent spatial queries (LDSQs), as it maintains objects separately from a given network and adopts an effective search space pruning technique. Based on our analysis on the two essential operations for LDSQ processing, namely, network traversal and object lookup, ROAD organizes a large road network as a hierarchy of interconnected regional subnetworks (called Rnets). Each Rnet is augmented with 1) shortcuts and 2) object abstracts to accelerate network traversals and provide quick object lookups, respectively. To manage those shortcuts and object abstracts, two cooperating indices, namely, Route Overlay and Association Directory are devised. In detail, we present 1) the Rnet hierarchy and several properties useful in constructing and maintaining the Rnet hierarchy, 2) the design and implementation of the ROAD framework, and 3) a suite of efficient search algorithms for single-source LDSQs and multisource LDSQs. We conduct a theoretical performance analysis and carry out a comprehensive empirical study to evaluate ROAD. The analysis and experiment results show the superiority of ROAD over the state-of-the-art approaches.

In this paper, we study a new form of reverse nearest neighbor (RNN) queries, i.e., obstructed reverse nearest neighbor (ORNN) search. It considers the impact of obstacles on the distance between objects, which is ignored by the existing work on RNN retrieval. Given a data set P, an obstacle set O, and a query point q in a 2D space, an ORNN query finds all the points/objects in P that have q as their nearest neighbor, according to the obstructed distance metric, i.e., the length of the shortest path between two points without crossing any obstacle. We formalize ORNN search, develop effective pruning heuristics (via introducing a novel boundary region concept), and propose efficient algorithms for ORNN query processing, assuming that both P and O are indexed by traditional data-partitioning indexes (e.g., R-trees). Extensive experiments demonstrate the effectiveness of our developed pruning heuristics and the performance of our proposed algorithms, using both real and synthetic datasets.

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.

In this paper, we first introduce the traffic status estimation service, a location-based continuous range query application provided by the CarWeb system. The service provides users nearby realtime traffic estimation according to their locations and moving behaviors. This paper focuses on how to provide users with the most relevant information efficiently and accurately. We propose the Continuous Query with Dynamic Fan-Shape framework (CQ-DFS) which dynamically changes parameters of fan shape range query to efficiently acquire more useful query results without compromising the performance of the system. We conduct extensive experiments to demonstrate the effectiveness of CQ-DFS framework by using real world vehicle trajectories.

Given a geographic query that is composed of query keywords and a location, a geographic search engine retrieves documents that are the most textually and spatially relevant to the query keywords and the location, respectively, and ranks the retrieved documents according to their joint textual and spatial relevances to the query. The lack of an efficient index that can simultaneously handle both the textual and spatial aspects of the documents makes existing geographic search engines inefficient in answering geographic queries. In this paper, we propose an efficient index, called IR-tree, that together with a top-k document search algorithm facilitates four major tasks in document searches, namely, 1) spatial filtering, 2) textual filtering, 3) relevance computation, and 4) document ranking in a fully integrated manner. In addition, IR-tree allows searches to adopt different weights on textual and spatial relevance of documents at the runtime and thus caters for a wide variety of applications. A set of comprehensive experiments over a wide range of scenarios has been conducted and the experiment results demonstrate that IR-tree outperforms the state-of-the-art approaches for geographic document searches.

Despite the ubiquity of physical obstacles (e.g., buildings, hills, and blindages, etc.) in the real world, most of spatial queries ignore the obstacles. In this article, we study a novel form of continuous nearest-neighbor queries in the presence of obstacles, namely continuous obstructed nearest-neighbor (CONN) search, which considers the impact of obstacles on the distance between objects. Given a data set P , an obstacle set O , and a query line segment q , in a two-dimensional space, a CONN query retrieves the nearest neighbor p ∈ P of each point p′ on q according to the obstructed distance, the shortest path between p and p ′ without crossing any obstacle in O . We formalize CONN search, analyze its unique properties, and develop algorithms for exact CONN query-processing assuming that both P and O are indexed by conventional data-partitioning indices (e.g., R-trees). Our methods tackle CONN retrieval by performing a single query for the entire query line segment, and only process the data points and obstacles relevant to the final query result via a novel concept of control points and an efficient quadratic-based split point computation approach. Then, we extend our techniques to handle variations of CONN queries, including (1) continuous obstructed k nearest neighbor (CO k NN) search which, based on obstructed distances, finds the k (≥ 1) nearest neighbors (NNs) to every point along q ; and (2) trajectory obstructed k nearest-neighbor (TO k NN) search, which, according to obstructed distances, returns the k NNs for each point on an arbitrary trajectory (consisting of several consecutive line segments). Finally, we explore approximate CO k NN (ACO k NN) retrieval. Extensive experiments with both real and synthetic datasets demonstrate the efficiency and effectiveness of our proposed algorithms under various experimental settings.

Navigational path query, one of the most popular location-based services (LBSs), determines a route from a source to a destination on a road network. However, issuing path queries to some non-trustworthy service providers may pose privacy threats to the users. For instance, given a query requesting for a path from a residential address to a psychiatrist, some adversaries may deduce "who is related to what disease". In this paper, we present an obfuscator framework that reduces the likelihood of path queries being revealed, while supporting different user privacy protection needs and retaining query evaluation efficiency. The framework consists of two major components, namely, an obfuscator and an obfuscated path query processor. The former formulates obfuscated path queries by intermixing true and fake sources and destinations and the latter facilitates efficient evaluation of the obfuscated path queries in an LBS server. The framework supports three types of obfuscated path queries, namely, independent obfuscated path query, shared obfuscated path query, and anti-collusion obfuscated path query. Our proposal strikes a balance between privacy protection strength and query processing overheads, while enhancing privacy protection against collusion attacks. Finally, we validate the proposed ideas and evaluate the performance of our framework based on an extensive set of empirical experiments.

In this paper, we identify and solve a new type of spatial queries, called continuous visible nearest neighbor (CVNN) search. Given a data set P, an obstacle set O, and a query line segment q, a CVNN query returns a set of (p, R) tuples such that p e P is the nearest neighbor (NN) to every point r along the interval R e q as well as p is visible to r. Note that p may be NULL, meaning that all points in P are invisible to all points in R, due to the obstruction of some obstacles in O. In this paper, we formulate the problem and propose efficient algorithms for CVNN query processing, assuming that both P and O are indexed by R-trees. In addition, we extend our techniques to several variations of the CVNN query. Extensive experiments verify the efficiency and effectiveness of our proposed algorithms using both real and synthetic datasets.

In this paper, we present ROAD, a general framework to evaluate Location-Dependent Spatial Queries (LDSQ)s that searches for spatial objects on road networks. By exploiting search space pruning technique and providing a dynamic object mapping mechanism, ROAD is very efficient and flexible for various types of queries, namely, range search and nearest neighbor search, on objects over large-scale networks. ROAD is named after its two components, namely, Route Overlay and Association Directory, designed to address the network traversal and object access aspects of the framework. In ROAD, a large road network is organized as a hierarchy of interconnected regional sub-networks (called Rnets) augmented with 1) shortcuts for accelerating network traversals; and 2) object abstracts for guiding traversals. In this paper, we present (i) the Rnet hierarchy and several properties useful to construct Rnet hierarchy, (ii) the design and implementation of the ROAD framework, (iii) efficient object search algorithms for various queries, and (iv) incremental update techniques for framework maintenance in presence of object and network changes. We conducted extensive experiments with real road networks to evaluate ROAD. The experiment result shows the superiority of ROAD over the state-of-the-art approaches.

Reverse nearest neighbor (RNN) queries have a broad application base such as decision support, profile-based marketing, resource allocation, data mining, etc. Previous work on RNN search does not take obstacles into consideration. In the real world, however, there are many physical obstacles (e.g., buildings, blindages, etc.), and their presence may affect the visibility/distance between two objects. In this paper, we introduce a novel variant of RNN queries, namely visible reverse nearest neighbor (VRNN) search, which considers the obstacle influence on the visibility of objects. Given a data set P, an obstacle set O, and a query point q, a VRNN query retrieves the points in P that have q as their nearest neighbor and are visible to q. We propose an efficient algorithm for VRNN query processing, assuming that both P and O are indexed by R-trees. Our method does not require any pre-processing, and employs half-plane property and visibility check to prune the search space.

Directions search returns the shortest path from a source to a destination on a road network. However, the search interests of users may be exposed to the service providers, thus raising privacy concerns. For instance, a path query that finds a path from a resident address to a clinic may lead to a deduction about "who is related to what disease". To protect user privacy from accessing directions search services, we introduce the OPAQUE system, which consists of two major components: (1) an obfuscator that formulates obfuscated path queries by mixing true and fake sources/destinations; and (2) an obfuscated path query processor installed in the server for obfuscated path query processing. OPAQUE reduces the likelihood of path queries being revealed and allows retrieval of requested paths. We propose two types of obfuscated path queries, namely, independently obfuscated path query and shared obfuscated path query to strike a balance between privacy protection strength and query processing overhead, and to enhance privacy protection against collusion attacks.

In this paper, we study a novel form of continuous nearest neighbor queries in the presence of obstacles, namely continuous obstructed nearest neighbor (CONN) search. It considers the impact of obstacles on the distance between objects, which is ignored by most of spatial queries. Given a data set P, an obstacle set O, and a query line segment q in a two-dimensional space, a CONN query retrieves the nearest neighbor of each point on q according to the obstructed distance, i.e., the shortest path between them without crossing any obstacle. We formulate CONN search, analyze its unique properties, and develop algorithms for exact CONN query processing, assuming that both P and O are indexed by conventional data-partitioning indices (e.g., R-trees). Our methods tackle the CONN retrieval by performing a single query for the entire query segment, and only process the data points and obstacles relevant to the final result, via a novel concept of control points and an efficient quadratic-based split point computation algorithm. In addition, we extend our solution to handle the continuous obstructed k-nearest neighbor (COkNN) search, which finds the k (≥1)nearest neighbors to every point along q based on obstructed distances. A comprehensive experimental evaluation using both real and synthetic datasets has been conducted to demonstrate the efficiency and effectiveness of our proposed algorithms.

This paper introduces and solves a novel type of spatial queries, namely, Optimal-Location-Selection (OLS) search, which has many applications in real life. Given a data object set D_A, a target object set D_B, a spatial region R, and a critical distance d_c in a multidimensional space, an OLS query retrieves those target objects in D_B that are outside R but have maximal optimality. Here, the optimality of a target object b \in D_B located outside R is defined as the number of the data objects from D_A that are inside R and meanwhile have their distances to b not exceeding d_c. When there is a tie, the accumulated distance from the data objects to b serves as the tie breaker, and the one with smaller distance has the better optimality. In this paper, we present the optimality metric, formalize the OLS query, and propose several algorithms for processing OLS queries efficiently. A comprehensive experimental evaluation has been conducted using both real and synthetic data sets to demonstrate the efficiency and effectiveness of the proposed algorithms.

Reverse nearest neighbor (RNN) queries have a broad application base such as decision support, profile-based marketing, resource allocation, etc. Previous work on RNN search does not take obstacles into consideration. In the real world, however, there are many physical obstacles (e.g., buildings) and their presence may affect the visibility between objects. In this paper, we introduce a novel variant of RNN queries, namely, visible reverse nearest neighbor (VRNN) search, which considers the impact of obstacles on the visibility of objects. Given a data set P, an obstacle set O, and a query point q in a 2D space, a VRNN query retrieves the points in P that have q as their visible nearest neighbor. We propose an efficient algorithm for VRNN query processing, assuming that P and O are indexed by R-trees. Our techniques do not require any preprocessing and employ half-plane property and visibility check to prune the search space. In addition, we extend our solution to several variations of VRNN queries, including: 1) visible reverse k-nearest neighbor (VRkNN) search, which finds the points in P that have q as one of their k visible nearest neighbors; 2) \delta-VRkNN search, which handles VRkNN retrieval with the maximum visible distance \delta constraint; and 3) constrained VRkNN (CVRkNN) search, which tackles the VRkNN query with region constraint. Extensive experiments on both real and synthetic data sets have been conducted to demonstrate the efficiency and effectiveness of our proposed algorithms under various experimental settings.

In this paper, we investigate the trade off between performance and confidentiality in signature-based air indexing schemes for wireless data broadcast. Two metrics, namely, false drop probability and false guess probability, are defined to quantify the filtering efficiency and confidentiality loss of a signature scheme. Our analysis reveals that false drop probability and false guess probability share a similar trend as the tuning parameters of a signature scheme change and it is impossible to achieve a low false drop probability and a high false guess probability simultaneously. In order to balance the performance and confidentiality, we perform an analysis to provide a guidance for parameter settings of the signature schemes to meet different system requirements. In addition, we propose the jump pointer technique and the XOR signature scheme to further improve the performance and confidentiality. A comprehensive simulation has been conducted to validate our findings.

In this research, we develop ROAD, a system framework for processing location dependent spatial queries (LDSQs) that search for spatial objects of interest on road networks. By exploiting search space pruning, ROAD is very efficient and flexible for various LDSQs on different types of objects over large-scale networks. In ROAD, a large road network is organized as a set of interconnected regional sub-networks (called Rnets) augmented with 1) shortcuts for accelerating search traversals; and 2) object abstracts for guiding object search. In this poster, we outline this framework and explain how it can support efficient location-dependent nearest neighbor search.

Wireless data broadcast is an efficient and scalable means to provide information access for a large population of clients in mobile environments. With Location-Based Services (LBSs) deployed upon a broadcast channel, mobile clients can collect data from the channel to answer their location-dependent spatial queries (LDSQs). Since the results of LDSQs would become invalid when mobile client moves to new locations, the knowledge of valid scopes for LDSQ results is necessary to assist clients to determine if their previous LDSQ results can be reused after they moved. This effectively improves query response time and client energy consumption. In this paper, we devise efficient algorithms to determine valid scopes for various LDSQs including range, window and nearest neighbor queries along with LDSQ processing over a broadcast channel. We conduct an extensive set of experiments to evaluate the performance of our proposed algorithms. While the proposed valid scope algorithm incurs only little extra processing overhead, unnecessary LDSQ reevaluation is significantly eliminated, thus providing faster query response and saving client energy.

Wireless broadcast is an efficient way for information dissemination due to its good scalability [10]. Existing works typically assume mobile devices, such as cell phones and PDAs, can access only one channel at a time. In this paper, we consider a scenario of near future where a mobile device has the ability to process queries using information simultaneously received from multiple channels. We focus on the query processing of the transitive nearest neighbor (TNN) search [19]. Two TNN algorithms developed for a single broadcast channel environment are adapted to our new broadcast enviroment. Based on the obtained insights, we propose two new algorithms, namely Double-NN-Search and Hybrid-NN-Search algorithms. Further, we develop an optimization technique, called approximate-NN (ANN), to reduce the energy consumption in mobile devices. Finally, we conduct a comprehensive set of experiments to validate our proposals. The result shows that our new algorithms provide a better performance than the existing ones and the optimization technique efficiently reduces energy consumption.

Given a set of trajectories D, a query object (point or trajectory) q, and a query interval T, a mutual (i.e., symmetric) nearest neighbor (MNN) query over trajectories finds from D within T, the set of trajectories that are among the k1nearest neighbors (NNs) of q, and meanwhile, have q as one of their k2NNs. This type of queries considers proximity of q to the trajectories and the proximity of the trajectories to q, which is useful in many applications (e.g., decision making, data mining, pattern recognition, etc.). In this paper, we first formalize MNN query and identify some problem characteristics, and then develop two algorithms to process MNN queries efficiently. In particular, we thoroughly investigate two classes of queries, viz. MNNPand MNNTqueries, which are defined w.r.t. stationary query points and moving query trajectories, respectively. Our techniques utilize the advantages of batch processing and reusing technology to reduce the I/O (i.e., number of node/page accesses) and CPU costs significantly. Extensive experiments demonstrate the efficiency and scalability of our proposed algorithms using both real and synthetic datasets.

Given a set of data points with both spatial coordinates and non-spatial attributes, point a location-dependently dominates point b with respect to a query point q if a is closer to q than b and meanwhile a dominates b. A location- dependent skyline query (LDSQ) issued at point q is to retrieve all the points that are not location-dependently dominated by other points with regard to q. In this paper, we focus on the query processing and result validation of LDSQ over static objects. Two algorithms, namely brute-forth and delta-scanning, are proposed. The former serves as the baseline algorithm while the latter significantly improves the performance via space pruning. We further conduct a comprehensive simulation to demonstrate the performance of proposed algorithms.

Given a set of data points P and a query point q in a multidimensional space, reverse nearest neighbor (RNN) query finds data points in P whose nearest neighbors are q. Reverse k-nearest neighbor (RkNN) query (where k ges 1) generalizes RNN query to find data points whose kNNs include q. For RkNN query semantics, q is said to have influence to all those answer data points. The degree of q's influence on a data point p (isin P) is denoted by kappap where q is the kappap-th NN of p. We introduce a new variant of RNN query, namely, ranked reverse nearest neighbor (RRNN) query, that retrieves t data points most influenced by q, i.e., the t data points having the smallest kappa's with respect to q. To answer this RRNN query efficiently, we propose two novel algorithms, kappa-counting and kappa-browsing that are applicable to both monochromatic and bichromatic scenarios and are able to deliver results progressively. Through an extensive performance evaluation, we validate that the two proposed RRNN algorithms are superior to solutions derived from algorithms designed for RkNN query.

Location based service (LBS) is emerging as a killer application in mobile data services thanks to the rapid development in wireless communication and location positioning technologies. Users with location-aware wireless devices can query about their surroundings (e.g., finding the nearest Japanese restaurant or all shopping malls within 5 miles) at any place, anytime. While this ubiquitous computing paradigm brings great convenience for information access, the constraints of mobile environments, the spatial property of location-dependent data, and the mobility of mobile users pose a great challenge for the provision of location-based services to mobile users. This seminar will provide an overview of research issues arising from accessing of location-based services in a mobile computing environment and discuss the state-of-theart solutions.

Location-based services (LBS) have emerged as one of the killer applications for mobile and pervasive computing environments. Due to limited bandwidth and scarce client resources, client-side data caching plays an important role of enhancing the data availability and improving the response time. In this demonstration, we present CS Cache Engine suitable for LBS. The underlying caching model is Complementary Space Caching (CS caching) scheme that we have recently presented in [citation]. Different from conventional data caching schemes, CS caching preserves a global view of the database by maintaining physical objects and capturing those objects in the server but not in the cache as Complementary Regions (CRs) in the cache. As a result, with the CS Cache Engine implementing CS caching, client assertiveness on their own answered queries is enhanced so that unnecessary requests over the wireless channel can be avoided; various kinds of location-based queries are naturally supported; and the client's ability to prefetch objects is introduced such that the response time can be further improved. In this demonstration paper, we discuss the architecture and the functionality of the CS Caching Engine that adopts CS caching. Specifically, for this demonstration, a tourist information named TravelGuide is prototyped with the support of this cache engine.

Studies on the performance issues (i.e., access latency and energy conservation) of wireless data broadcast have appeared in the literature. However, the important security issues have not been well addressed. This paper investigates the tradeoff between performance and security of signature-based air index schemes in wireless data broadcast. From the performance perspective, keeping low false drop probability helps clients retrieve the information from a broadcast channel efficiently. Meanwhile, from the security perspective, achieving high false guess probability prevents the hacker from guessing the information easily. There is a tradeoff between these two aspects. An administrator of the wireless broadcast system may balance this tradeoff by carefully configuring the signatures used in broadcast. This study provides a guidance for parameter settings of the signature schemes in order to meet the performance and security requirements. Experiments are performed to validate the analytical results and to obtain optimal signature configuration corresponding to different application criteria.

Semantic caching enables mobile clients to answer spatial queries locally by storing the query descriptions together with the results. However, it supports only a limited number of query types, and sharing results among these types is difficult. To address these issues, we propose a proactive caching model which caches the result objects as well as the index that supports these objects as the results. The cached index enables the objects to be reused for all common types of queries. We also propose an adaptive scheme to cache such an index, which further optimizes the query response time for the best user experience. Simulation results show that proactive caching achieves a significant performance gain over page caching and semantic caching in mobile environments where wireless bandwidth and battery are precious resources.

To support location-based services in wireless data broadcast systems, a distributed spatial index (called DSI) is proposed in this paper. DSI is highly efficient because it has a linear yet fully distributed structure that naturally facilitates multiple replications of the index by sharing links in different search trees. Search algorithms for point queries, window queries, and kNN queries, based on DSI are presented. Empirical evaluation of DSI are conducted. Result shows that DSI significantly out-performs R-tree and Hilbert curve index, two state-of-the-art spatial indexing techniques for wireless data broadcast.

Wireless broadcast is very suitable for delivering information to a large user population. In this paper, we concentrate on data allocation methods for multiple broadcast channels. To the best of our knowledge, this is the first allocation model that takes into the consideration of items' access frequencies, items' lengths. and bandwidth of different channels. We first derive the optimal average expected delay for multiple channels for the general case where data access frequencies, data sizes, and channel bandwidths can all be non-uniform. Second, we develop TOSA, a multi-channel allocation method that does not assume a uniform broadcast schedule for data items on the same channel. TOSA is based on the idea of two-level data allocation, i.e., a high-level optimization step for allocating data to the channels, followed by a low-level optimization step to schedule data within a channel. We show that TOSA achieves near-optimal performance in terms of average waiting time and significantly outperforms the existing algorithms.

Location-based services (LBSs), considered as a killer application in the wireless data market, provide information based on locations specified in the queries. In this paper, we examine the indexing issue for querying location-dependent data in wireless LBSs; in particular, we focus on an important class of queries, planar point queries. To address the issues of responsiveness, energy consumption, and bandwidth contention in wireless communications, an index has to minimize the search time and maintain a small storage overhead. It is shown that the traditional point-location algorithms and spatial index structures fail to achieve either objective or both. This paper proposes a new index structure, called D-tree, which indexes spatial regions based on the divisions that form the boundaries of the regions. We describe how to construct a binary D-tree index, how to process queries based on the D-tree, and how to page the binary D-tree. Moreover, two parameterized methods for partitioning the original space, called fixed grid assignment (FGA) and adaptive grid assignment (AGA), are proposed to enhance the D-tree. The performance of the D-tree is evaluated using both synthetic and real data sets. Experimental results show that the proposed D-tree outperforms the well-known indexes such as the R/sup */-tree, and that both the FGA and AGA approaches can achieve different performance trade-offs between the index search time and storage overhead by fine-tuning their algorithmic parameters.

We are witnessing in recent years growing interest for location-dependent information services among mobile users. We examine the issue of processing location-dependent queries in a mobile broadcast environment. Different from a traditional environment, mobile users are concerned with not only access latencies but also power conservation. The planar point location algorithms and conventional spatial index structures are shown inefficient. We propose a new index data structure, called D-tree, for querying location-dependent data in mobile broadcast environments. The basic idea is to index data regions based on the divisions between them. We describe how to construct the binary D-tree index, how to process location-dependent queries based on this index structure, and how to page the D-tree to fit the packet capacity. The performance of the D-tree is evaluated using both synthetic and real datasets. Experimental results show that the proposed D-tree provides a much better overall performance than the well-known existing schemes such as the R*-tree.