Unsupervised anomaly detection in multivariate time series can prevent large-scale system failures and is crucial for various applications. Most existing methods only consider a single temporal pattern and insufficiently model the normal pattern, causing the model to learn incorrect temporal patterns from anomalous or noisy data. This poses a significant challenge for accurate anomaly detection. To overcome these challenges, we introduce a new dynamic decomposition and reconstruction anomaly detection algorithm, DMRAD. DMRAD captures various regular patterns of multivariate time series by designing a dynamic decomposition module that learns trend and seasonal features. By integrating improved channel and temporal attention mechanisms, DMRAD effectively learns the correlations within the sequence and dependencies across different sequences, thereby enhancing the model's capacity to distinguish between features and extract relevant information. DMRAD incorporates a latent anomaly-noise detection algorithm to identify and suppress the influence of noise and latent anomalies, elevating the overall accuracy of anomaly detection. Extensive experimental comparisons demonstrate that DMRAD achieves state-of-the-art performance on a variety of datasets for real-world application scenarios.

Anomaly detection is one of the most significant tasks in industrial automatic maintenance, such as in distributed cloud systems. However, the implementation of existing anomaly detection methods is still challenging in (i) capturing the complex spatial and temporal correlations of multivariate time series, (ii) effectively adapting to the unsupervised condition, and (iii) generalizing across nodes in distributed systems. To address these challenges, we design a multi-perspective spatio-temporal attention model, called STAMP, which consists of a prediction module ST-ATTN, a reconstruction module AutoEncoder, and an adversarial optimizing module. Specifically, ST-ATTN leverages multiple attention mechanisms to perform spatio-temporal learning from both local and global perspectives, AutoEncoder is utilized to fit implicit representations, and the adversarial optimization module employs a min-max training strategy to enhance the learning capability. By introducing pre-training strategies, STAMP can be effectively adapted to distributed systems with a strong generalization ability. Furthermore, to cope with the practical unlabeled data conditions, we propose an unsupervised framework compatible with not only STAMP but also other advanced detection models. In this framework, a screening process is first conducted by traditional methods to generate a training set of pseudo-normal samples. Second, the models are trained and then used for detection. The framework can be further optimized by performing feature selection based on model-derived information for a better detectability. Extensive experiments in real-world datasets demonstrate that the proposed model and framework achieve superior performance when compared with baselines under both semi-supervised and unsupervised conditions. In particular, the detection framework has already been applied in Huawei's GaussDB (DWS) system.

As a fundamental operation of location-based services, shortest path querying is widely adopted in real-time applications. Regrettably, most prior works overlook the impact of traffic-flow on shortest path querying. Taking traffic-flow into account is essential for finding a more convenient path through the Flow-Aware Shortest Path Querying (FSPQ). FSPQ faces the following challenges: (1) index restriction, existing indexes are only constructed by the relative spatial distance, if we leverage the traffic-flow to build the index, we can reduce the index size and improve its query efficiency. (2) maintenance latency, the traffic-flow and edges' weights undergo high-frequency changes with different traffic conditions, meaning that our index must be able to support high-frequency updates. To end this, we propose a novel Flow-Aware Hierarchical Labeling Index (FAHL) in this paper. In the index construction aspect, we propose a degree-flow joint ordering method to obtain the joint vertex ordering, and then build the index on it. In this way, FAHL can not only perceive both spatial distance and traffic-flow information but also reduce the index overhead during the query. In the index maintenance aspect, we propose Improved Structure Update (ISU) and Index Label Update (ILU) algorithms to support the index updating when high-frequency flow$\backslash$weight changes. Moreover, a flow priority shortest path search algorithm with pruning query bounds is proposed to speed up the query processing. Extensive experiments demonstrate that our proposed method achieves 33.1% speedup on average for the flow-aware shortest path querying compared to the state-of-the-art methods.

Graph embedding, which maps graph nodes to lowdimensional vectors, is a widely used technique for graph representation learning. However, most existing graph embedding models suffer from high memory consumption, limiting their scalability to large graphs. Heterogeneous memory systems that combine DRAM and Persistent Memory (PM) offer new opportunities for scaling up memory capacity. Despite this advantage, the performance gap (on the order of 5x) between DRAM and PM is magnified (by 3.3-4.2x) under non-uniform memory access (NUMA) architecture. Additionally, the inherent sparsity of graphs induces numerous random accesses in the fundamental Sparse Matrix and Dense Matrix Multiplication (SpMM) operations of graph embedding, hindering high-performance heterogeneous memory processing. To address these challenges, this paper presents OMeGa that focuses on Optimizing heterogeneous Memory processing for large-scale Graph embedding. OMeGa leverages an entropy-aware thread allocation, simultaneously achieving workload balancing and tail latency reduction across threads. It also incorporates a workload feature-aware prefetcher to alleviate random accesses during streaming heterogeneous processing. In addition, OMeGa devises a NUMA-aware data placement, aiming to minimize the adverse impact of NUMA on heterogeneous memory. The experiments conducted on billion-scale graphs demonstrate that OMeGa exhibits an average acceleration of 32.03x with strong scalability. This pioneering capability enables the efficient generation of large-scale graph embeddings, free from the memory size constraints and performance disparities typically encountered in heterogeneous memory systems.

With the development of modern cloud platforms, an increasing number of users are migrating their data analysis tasks to the cloud. Cloud platforms offer a “pay-as-you-go” model, prompting users to focus on both performance and resource costs. Existing query optimization methods primarily address query performance while neglecting resource costs. Mapping queries to their resource consumption is a complex task. To tackle this challenge, we propose a novel learning-based query resource recommendation method called LORE. LORE efficiently and accurately estimates the optimal resources for queries by leveraging dual information from SQL query statements and query execution plans. We model SQL queries and execution plans as directed acyclic graphs and utilize graph neural networks to derive comprehensive representations. To capture the dependencies among all nodes involved in data transmission within an execution plan, we assign path weights to the dependency edges of each node. Our approach integrates data distribution information and captures both direct and indirect dependencies among plan nodes while avoiding unnecessary redundant computations. Experimental results demonstrate that, compared to traditional and other learning-based methods, the LORE model achieves higher accuracy in predicting the optimal resources for queries.

Anomaly diagnosis is a fundamental problem in operation and maintenance of distributed cloud databases. Existing deep learning based methods solve this problem by classifying the anomalies with different root causes. However, since anomalies seldom occur, and anomalies with the same root cause may exhibit significantly different behaviors across different cloud database clusters, existing methods often lack sufficient training data, and they cannot generalize well from some clusters to others. Therefore, we take both anomaly and normal data into consideration, based on an observation that the discrepancy between the anomaly and normal data is relatively consistent compared to the behaviours of anomalies themselves. We design a Siamese Discrepancy Network (SDN) to learn representations of such discrepancy under the case that only a small amount of training data is available. In addition, a discrepancy-based diagnosis paradigm is proposed to construct training data for SDN and diagnose based on representations of discrepancy learned by SDN. Finally, we develop an anomaly interpretation method based on SDN, which accurately locates the symptom KPIs and root cause KPIs. Extensive experiments are conducted on both synthetic and real-world datasets. The experimental results demonstrate that the proposed method outperforms existing methods with respect to anomaly diagnosis and anomaly interpretation. In particular, the anomaly diagnosis framework has already been applied in Huawei's GaussDB (DWS) system.

Set similarity search, as a foundational operation in data processing with diverse applications in different domains, has been extensively studied. However, in the era of big data where sets sizes and quantities are rapidly increasing, set similarity search suffers from significant computational and storage overheads. Additionally, traditional approaches struggle to universally address the search problem across different similarity measures and query types. To tackle these challenges, AI techniques, with their powerful learning capabilities, may provide a viable solution. In this paper, we first propose a multi-task representation learning approach with box embeddings that accurately simulates different similarity measures simultaneously by estimating the overlap and union relationships between set pairs in latent box space. Based on the compressed representations of sets, we then introduce a universal search approach designed to answer various set similarity queries with parallel implementation. Extensive experiments conducted on real-world datasets demonstrate the universality, accuracy and efficiency of the proposed approach, showing that it outperforms competing methods. For reproduction, we release our source code on https://github.com/yangzhong901/MTBUS.

Approximate nearest neighbor (ANN) search on high-dimensional vector data is core functionality in an increasing number of real-world applications. However, most existing methods only focus on accelerating search by means of indexing that assumes that the data is static. The few methods capable of contending with dynamic data often face challenges such as decreased query accuracy following updates and low update efficiency. In this study, we propose Wolverine, the first proposal that, to our knowledge, enables efficient monotonic search path repair, thereby solving the graph-based ANN index update problem. Wolverine repairs disrupted monotonic search paths by adding in-edges to the out-neighbors of a point to be deleted. To improve efficiency, Wolverine+ restricts the search space to be within the 2-hop neighbors of the point to be deleted. In addition, Wolverine++ employs a sophisticated candidate selection policy to find high-quality candidates in the reduced search space, simultaneously improving accuracy and efficiency. An experimental study on 9 real-world datasets demonstrates that Wolverine is capable of accelerating the deletion throughput by up to 11X and achieving more stable recall during updates compared to the state-of-the-art dynamic ANN search method.

Subsequence anomaly detection for time series is a crucial problem in various real-world applications. However, existing methods proposed so far design the anomaly score functions solely based on either local neighborhood or global patterns, leading to unsatisfactory detection accuracy. In addition, these methods either cannot adapt, or yield insufficient accuracy and efficiency in streaming scenario. Therefore, we propose Sirloin, an accurate and efficient streaming time series subsequence anomaly detection framework. First, Sirloin proposes a glance and focus anomaly score function that takes both global and local information into consideration, contributing to an accurate anomaly detection. Second, Sirloin dynamically maintains an inverted file index and product quantization codebooks to index and compress the subsequences, hence is able to cope with the time series evolution and to process streaming batches efficiently. In addition, a dual index optimization strategy is put forward that further improves the efficiency. An experimental study in 11 different datasets from 5 domains offers insight into the performance of Sirloin, showing that it improves throughput on average 4x and enhances accuracy 58.02% compared to the state-of-the-art streaming method.

With the rise of Large Language Models (LLMs), tourists increasingly use it for route planning by entering keywords for attractions, instead of relying on traditional manual map services. LLMs provide generally reasonable suggestions, but often fail to generate optimal plans that account for detailed user requirements, given the vast number of potential POIs and possible routes based on POI combinations within a real-world road network. In this case, a route-planning API could serve as an external tool, accepting a sequence of keywords and returning the top-k best routes tailored to user requests. To address this need, this paper introduces the Keyword-Aware Top-k Routes (KATR) query that provides a more flexible and comprehensive semantic to route planning that caters to various user's preferences including flexible POI visiting order, flexible travel distance budget, and personalized POI ratings. Subsequently, we propose an explore-and-bound paradigm to efficiently process KATR queries by eliminating redundant candidates based on estimated score bounds from global to local levels. Extensive experiments demonstrate our approach's superior performance over existing methods across different scenarios.

As a fundamental technology in intelligent transportation systems (ITS), accurate traffic flow prediction has emerged as a critical challenge in real-time applications. How to fully utilize the traffic data, and capture the spatial temporal correlation are keys to improve the model's prediction ability. Numerous neural networks have been proposed to address this issue. However, most of these existing methods have the following two problems: 1) Lack of byroads information. Meaning that the existing methods do not consider the byroads in real-life traffic environments; 2) Lack of potential learning ability. Meaning that the existing methods suffer the non-similar forgetting and hard to gain the multi-hop correlation. To overcome these problems, we propose a novel Spatial Temporal Byroad-Aware Graph Convolution Network (ByGCN) in this paper. ByGCN consists of byroad identification and spatial temporal learning modules. In the first module, we design spatial temporal decoupling and graph diffusion blocks to identify the byroads and reconstruct them into the flow data. In the second module, with the help of spatial temporal attention and GCN, our module can capture the complex spatial temporal correlation. Experiments on four real-world traffic datasets demonstrate that ByGCN outperforms the state-of-the-art methods.

The maximum inner product search (MIPS) problem in high-dimensional vector spaces has various applications, primarily driven by the success of deep neural network-based embedding models. Existing MIPS methods designed for dense vectors using approximate techniques like locality-sensitive hashing (LSH) have been well studied, but they are not efficient and effective for searching sparse vectors due to the near-orthogonality among the sparse vectors. The solutions to MIPS over sparse vectors rely heavily on inverted lists, resulting in poor query efficiency, particularly when dealing with large-scale sparse datasets. In this paper, we introduce SOSIA, a novel framework specifically tailored to address these limitations. To handle sparsity, we propose the SOS transformation, which converts sparse vectors into a binary space while providing an unbiased estimator of the inner product between any two vectors. Additionally, we develop a minHash-based index to enhance query efficiency. We provide a theoretical analysis on the query quality of SOSIA and present extensive experiments on real-world sparse datasets to validate its effectiveness. The experimental results demonstrate its superior performance in terms of query efficiency and accuracy compared to existing methods.

Efficient query optimization is crucial for database management systems. Recently, machine learning models have been applied in query optimizers to generate better plans, but the unpredictable performance regressions prevent them from being truly applicable. To be more specific, while a learned query optimizer commonly outperforms the traditional query optimizer on average for a workload of queries, its performance regression seems inevitable for some queries due to model under-fitting and difficulty in generalization. In this paper, we propose a system called Eraser to resolve this problem. Eraser aims at eliminating performance regressions while still attaining considerable overall performance improvement. To this end, Eraser applies a two-stage strategy to estimate the model accuracy for each candidate plan, and helps the learned query optimizer select more reliable plans. The first stage serves as a coarse-grained filter that removes all highly risky plans with feature values that are seen for the first time. The second stage clusters plans in a more fine-grained manner and evaluates each cluster according to the prediction quality of learned query optimizers for selecting the final execution plan. Eraser can be deployed as a plugin on top of any learned query optimizer. We implement Eraser and demonstrate its superiority on PostgreSQL and Spark. In our experiments, Eraser eliminates most of the regressions while bringing very little negative impact on the overall performance of learned query optimizers, no matter whether they perform better or worse than the traditional query optimizer. Meanwhile, it is adaptive to dynamic settings and generally applicable to different database systems.

Learned databases, or AI4DB techniques, have rapidly developed in the last decade. Deploying machine learning (ML) and AI4DB algorithms into actual databases is the gold standard to examine their performance in practice. However, due to the complexity of database systems, the difference between ML and DB programming paradigms, and the diversity of ML models, the tasks of developing and deploying AI4DB algorithms into databases are prohibitively difficult. Most previous works focus on specific AI4DB algorithms and ML models whose deployment requires close cooperation between ML and DB developers and heavy engineering cost. In this paper, we design and implement PilotScope, an AI4DB middleware with a programming model that largely reduces such difficulties. With a novel abstraction of AI4DB algorithms for, e.g. , knob tuning and query optimization, PilotScope consists of two classes of components, AI4DB drivers and DB interactors , with different programming paradigms and roles in AI4DB tasks. ML developers focus on designing and implementing AI4DB drivers, which are algorithmic workflows that collect statistics from databases, train ML models, make decisions and optimize databases using learned models. AI4DB drivers interact with databases via DB interactors ( e.g. , for collecting data and enforcing actions in databases). DB developers focus on implementing these interactors on one or more database engines, with the interaction details hindered from ML developers. PilotScope supports a variety of AI4DB tasks, and the implementation of an AI4DB algorithm on PilotScope can be deployed in different databases with only minimum modifications. PilotScope is effective in benchmarking these AI4DB algorithms in real-world scenarios. We hope that PilotScope could significantly accelerate iterating AI4DB research and make AI4DB techniques truly applicable in production.

The protocols that satisfy Local Differential Privacy (LDP) enable untrusted third parties to collect aggregate information about a population without disclosing each user's privacy. In particular, each user locally encodes and perturbs his private data before sending it to the data collector, who aggregates and estimates the statistics about the population based on the collected perturbed values from individuals. Owing to their growing importance, LDP protocols have been widely studied and deployed in real-world scenarios (eg Chrome and Windows). However, as data poisoning attacks may be injected by attackers who introduce many fake users, the utility of the statistics is heavily poisoned. In this paper, we present a generic and extensible framework called LDPGuard to address the problem. LDPGuard provides effective defenses against data poisoning attacks to LDP protocols for frequency estimation, a basic query of most data analytics tasks. In particular, it first precisely estimates the percentage of fake users and then provides adversarial schemes to defend against particular data poisoning attacks. Experimental study on real-world and synthetic datasets demonstrates the superiority of LDPGuard compared to existing techniques.

Anomaly detection is one of the most significant tasks in multivariate time series analysis, while it remains challenging to model complex patterns for improving detection accuracy and to interpret the root causes of anomalies. However, existing studies either consider only the temporal dependencies, or simply reconstruct the original input for detection, both neglecting the hidden relationships among multivariate. We propose an adversarial graph neural network based anomaly detection model, called SGAT-AE, which consists of aSelf-learningGraphATtention network (SGAT), anAuto-Encoder (AE), and an adversarial training component. Specifically, SGAT is a prediction model that discovers the graph dependency relationships among multivariate and acts as a sample generator to confuse AE, while AE reconstructs the samples and acts as a discriminator that distinguishes a real sample from a generated one. A novel adversarial training between SGAT and AE is applied to amplify the errors of anomalies such that the prediction performance of SGAT is improved and the overfitting of AE is avoided. In addition, we aggregate the prediction error, the reconstruction error, and the adversarial error for anomaly detection, and develop a graph based anomaly interpretation method that locates the root causes from both local and global perspectives. Extensive experiments with five real-world data offer evidence that the proposed solution SGAT-AE is capable of achieving better performance when compared with the state-of-the-art proposals.

A shortest distance query is a fundamental operation of various real-time response applications in time-dependent road networks. Unfortunately, existing methods (e.g., G-treelike, 2-hop labeling-like) are prohibitively expensive in terms of space/time. To this end, we propose a novel Double Hierarchical Labeling (DHL) index, which consists of a Hierarchical Graph Partition (HGP) tree and a hierarchical border labeling list. For HGP-tree, we first use a hierarchical graph partitioning to split the entire road network into hierarchical subgraphs and then index these subgraphs by a balanced tree. To preserve all connectivity information between border vertices of subgraphs, a Time-based Distance Inverted File (TDIF) is constructed for each leaf node of the HGP-tree. For the hierarchical labeling list, we construct it only for border vertices and use it to speed up query processing. Moreover, a label propagation update is proposed to manage label updating when weights change. Finally, we propose a phase-aware search algorithm for different search situations between given query vertices to guarantee query efficiency. Extensive experiments are conducted to demonstrate the superiority of the proposed proposals on query processing and index maintenance.

Computing the shortest path distance between two vertices in a road network is a building block in numerous applications. To do so efficiently, the state-of-the-art proposals adopt a tree decomposition process with heuristic strategies to build 2-hop label indexes. However, these indexes suffer from large space overheads caused by either tree imbalance or a large tree height. Independently of this, reinforcement learning has recently show impressive performance at sequential decision making in spatial data management tasks. We observe that tree decomposition is naturally a sequential decision making problem that decides which vertex to process at each step. In this paper, we propose a reinforcement learning based tree decomposition (RLTD) approach that reduces the space overhead significantly. We model tree decomposition as a Markov Decision Process, exploiting features of both the network topological structure and the tree structure. We further optimize the tree decomposition process by taking the network density into account, which yields a great generalization of the model on large road networks. Extensive experiments with real-world data offer insights into the performance of the proposals, showing that they are able to reduce the space overhead by about 51% and achieve on average about 14% speedup for queries with almost the same preprocessing time when compared with the state-of-the-art proposals.

Approximate nearest neighbor (ANN) search in high-dimensional space plays an essential role in a variety of real-world applications. A well-known solution to ANN search, inverted file product quantization (IVFPQ) adopts inverted files to avoid exhaustive examination and compresses vectors using product quantization to reduce the space overhead. However, existing implementations use the same fixed probing cardinality (i.e., the number of cells to probe) setting for all queries, which leads to too many or too few cell examinations, thus increasing the average query latency or reducing the recall. To achieve a better trade-off between latency and accuracy, we enable probing cardinality estimation for high-dimensional ANN search by using deep learning techniques. We develop HBK-means, a hierarchical balanced clustering algorithm that reduces the data distribution imbalance of cells to enable a better estimation. Next, we develop PCE-Net, an encoder-decoder based neural network for estimating query-dependent minimum probing cardinality. In addition, we introduce two query optimization strategies: lower bound sorting based pruning (LBS-Pruning) and early termination (ET), to further reduce query latency. Extensive experiments with real-world data offer evidence that the proposed solution is capable of achieving better performance than IVFPQ and its variants.

Test2SQL, a natural language interface to database querying, has seen considerable improvement, in part due to advances in deep learning. However, despite recent improvement, existing Text2SQL proposals allow only input in the form of complete questions. This leaves behind users who struggle to formulate complete questions, e.g., because they lack database expertise or are unfamiliar with the underlying database schema. To address this shortcoming, we study the novel problem of Text2SQL Auto-Completion (TSAC) that extends Text2SQL to also take partial or incomplete questions as input. Specifically, the TSAC problem is to predict the complete, executable SQL query. To solve the problem, we propose a novel Relation-aware Historical Bridging Network (RHB-Net) that consists of a relation-aware union encoder and an extraction-generation sensitive decoder. RHB-Net models relations between questions and database schemas and predicts the ambiguous intents expressed in partial queries. We also propose two optimization strategies: historical query bridging that fuses historical database queries, and a dynamic context construction that prevents repeated generation of the same SQL elements. Extensive experiments with real-world data offer evidence that RHB-Net is capable of outperforming baseline algorithms.

With an exponentially growing number of graphs from disparate repositories, there is a strong need to analyze a graph database containing an extensive collection of small- or medium-sized data graphs (e.g., chemical compounds). Although subgraph enumeration and subgraph mining have been proposed to bring insights into a graph database by a set of subgraph structures, they often end up with similar or homogenous topologies, which is undesirable in many graph applications. To address this limitation, we propose the Top-k Edge-Diversified Patterns Discovery problem to retrieve a set of subgraphs that cover the maximum number of edges in a database. To efficiently process such query, we present a generic and extensible framework called Ted which achieves a guaranteed approximation ratio to the optimal result. Two optimization strategies are further developed to improve the performance. Experimental studies on real-world datasets demonstrate the superiority of Ted to traditional techniques.

Designing a space-efficient data structure to answer membership queries while ensuring high accuracy and real-time response is a challenging task in the field of stream processing. Many techniques have been developed to answer these queries in a sliding windows manner. However, assuming the user will conduct the query with the presupposed window size is not always practical. In this paper, we introduce a novel data structure called Learned Cuckoo Filter (LCF). It can provide satisfactory results for the approximate membership query on data streams, regardless of the user-defined query windows. LCF operates by adaptively maintaining cuckoo filters with the assistance of a well-trained oracle that learned the frequency feature of the data within the stream. To further enhance memory utilization, we develop a compact version of LCF (denoted by LCF_C), which selectively removes redundant information to reduce space consumption without compromising query accuracy. Furthermore, we conduct a thorough theoretical analysis of query accuracy and provide detailed guidelines for optimal parameter selection (denoted by LCF_O). Extensive experimental studies on synthetic and real-world datasets demonstrate the superiority of the proposed methods in terms of both space consumption and accuracy. Compared to the state-of-the-art algorithms, LCF_O can reduce up to 61% of space cost at the same error level, and achieve up to 12× improved accuracy with the same space cost.

The approximate nearest neighbor (ANN) search in high-dimensional spaces is a fundamental but computationally very expensive problem. Many methods have been designed for solving the ANN problem, such as LSH-based methods and graph-based methods. The LSH-based methods can be costly to reach high query quality due to the hash-boundary issues, while the graph-based methods can achieve better query performance by greedy expansion in an approximate proximity graph (APG). However, the construction cost of these APGs can be one or two orders of magnitude higher than that for building hash-based indexes. In addition, they fail short in incrementally maintaining APGs as the underlying dataset evolves. In this paper, we propose a novel approach named LSH-APG to build APGs and facilitate fast ANN search using a lightweight LSH framework. LSH-APG builds an APG via consecutively inserting points based on their nearest neighbor relationship with an efficient and accurate LSH-based search strategy. A high-quality entry point selection technique and an LSH-based pruning condition are developed to accelerate index construction and query processing by reducing the number of points to be accessed during the search. LSH-APG supports fast maintenance of APGs in lieu of building them from scratch as dataset evolves. Its maintenance cost and query cost for a point is proven to be less affected by dataset cardinality. Extensive experiments on real-world and synthetic datasets demonstrate that LSH-APG incurs significantly less construction cost but achieves better query performance than existing graph-based methods.

Maximum inner product search (MIPS) in high-dimensional spaces has wide applications but is computationally expensive due to the curse of dimensionality. Existing studies employ asymmetric transformations that reduce the MIPS problem to a nearest neighbor search (NNS) problem, which can be solved using locality-sensitive hashing (LSH). However, these studies usually maintain multiple hash tables and locally examine them one by one, which may cause additional costs on probing unnecessary points. In addition, LSH is applied without taking into account the properties of the inner product. In this paper, we develop a fast search framework FARGO for MIPS on large-scale, high-dimensional data. We propose a global multi-probing (GMP) strategy that exploits the properties of the inner product to globally examine high quality candidates. In addition, we develop two optimization techniques. First, different with existing transformations that introduce either distortion errors or data distribution imbalances, we design a novel transformation, called random XBOX transformation, that avoids the negative effects of data distribution imbalances. Second, we propose a global adaptive early termination condition that finds results quickly and offers theoretical guarantees. We conduct extensive experiments with real-world data that offer evidence that FARGO is capable of outperforming existing proposals in terms of both accuracy and efficiency.

Growing demands for the efficient processing of extreme-scale time series workloads call for more capable time series database management systems (TSDBMS). Specifically, to maintain consistency and durability of transaction processing, systems employ write-ahead logging (WAL) whereby transactions are committed only after the related log entries are flushed to disk. However, when faced with massive I/O, this becomes a throughput bottleneck. Recent advances in byte-addressable Non-Volatile Memory (NVM) provide opportunities to improve logging performance by persisting logs to NVM instead. Existing studies typically track complex transaction dependencies and use barrier instructions of NVM to ensure log ordering. In contrast, few studies consider the heavy-tailed characteristics of time series workloads, where most transactions are independent of each other. We propose DecLog, a decentralized NVM-based logging system that enables concurrent logging of TSDBMS transactions. Specifically, we propose data-driven log sequence numbering and relaxed ordering strategies to track transaction dependencies and resolve serialization issues. We also propose a parallel logging method to persist logs to NVM after being compressed and aligned. An experimental study on the YCSB-TS benchmark offers insight into the performance properties of DecLog, showing that it improves throughput by up to 4.6× while offering lower recovery time in comparison to the open source TSDBMS Beringei.

We consider a setting with an evolving set of requests for transportation from an origin to a destination before a deadline and a set of agents capable of servicing the requests. In this setting, an assignment authority is to assign agents to requests such that the average idle time of the agents is minimized. An example is the scheduling of taxis (agents) to meet incoming passenger requests for trips while ensuring that the taxis are empty as little as possible. In this paper, we study the problem of spatial-temporal demand forecasting and competitive supply (SOUP). We address the problem in two steps. First, we build a granular model that provides spatial-temporal predictions of requests. Specifically, we propose a Spatial-Temporal Graph Convolutional Sequential Learning (ST-GCSL) model that predicts the requests across locations and time slots. Second, we provide means of routing agents to request origins while avoiding competition among the agents. In particular, we develop a demand-aware route planning (DROP) algorithm that considers both the spatial-temporal predictions and the supply-demand state. We report on extensive experiments with real-world data that offer insight into the performance of the solution and show that it is capable of outperforming the state-of-the-art proposals.

The string similarity search is core functionality in a range of applications, including data cleaning, near-duplicate object detection, and data integration. We study the problem of threshold similarity search with the edit distance, where given a set of strings, a threshold$k$, and a query string$q$, we aim to find all strings in the set whose edit distances to$q$are no larger than$k$. Extensive studies have been proposed for the threshold similarity search problem with the edit distance. However, they suffer from a huge space consumption issue when achieving only an acceptable efficiency, especially for long strings. In this paper, we propose a simple yet small index, called minIL, to eliminate this issue. First, we adopt a minhash family to capture pivot characters and to construct sketch representations for strings. Second, we develop a multi-level inverted index to search sketches with a low space consumption. Finally, we apply a novel learned index technique on top of the index that further improves the query efficiency. Extensive experiments on real-world datasets offer insight into the performance of our method and show that it substantially reduces the index size, and is capable of outperforming the baseline approaches.

Computing shortest-path distances in road networks is core functionality in a range of applications. To enable the efficient computation of such distance queries, existing proposals frequently apply 2-hop labeling that constructs a label for each vertex and enables the computation of a query by performing only a linear scan of labels. However, few proposals take into account the spatio-temporal characteristics of query workloads. We observe that real-world workloads exhibit (1) spatial skew, meaning that only a small subset of vertices are queried frequently, and (2) temporal locality, meaning that adjacent time intervals have similar query distributions. We propose a Workload-aware Core-Forest label index (WCF) to exploit spatial skew in workloads. In addition, we develop a Reinforcement Learning based Time Interval Partitioning (RL-TIP) algorithm that exploits temporal locality to partition workloads to achieve further performance improvements. Extensive experiments with real-world data offer insights into the performance of the proposals, showing that they achieve 62% speedup on average for query processing with less preprocessing time and space overhead when compared with the state-of-the-art proposals.

Predicting the Origin-Destination (OD) traffic is a fundamental problem and of great significance in transportation research and civil engineering. There are three expectations for a good OD traffic predictor: 1) higher accuracy; 2) longer horizon; 3) better applicability. This paper proposes a Hybrid Spatio-Temporal Network (HSTN) model to predict OD traffic. The model emphasizes capturing more comprehensive spatial correlations among the sources of the traffic flows and temporal correlations between historical values and future prediction. HSTN is designed to have a Hybrid Spatial Module (HSM) and a Hybrid Temporal Module (HTM). HSM consists of three units to learn three types of spatial relationships and HTM consists of two units to quantity the influence of the input sequence on the target result. We evaluate HSTN on three real-world datasets of different travel modes in different cities. Results show that the proposed HSTN outperforms existing methods in both short-term and long-term predictions in all datasets.

Online ride-hailing platforms have reduced significantly the amounts of the time that taxis are idle and that passengers spend on waiting. As a key component of these platforms, the fleet management problem can be naturally modeled as a Markov Decision Process, which enables us to use the deep reinforcement learning. However, existing studies are proposed based on simplified problem settings that fail to model the complicated supply-dynamics and restrict the performance in the real traffic environment. In this article, we propose a supply-demand-aware deep reinforcement learning algorithm for taxi dispatching, where we use a deep Q-network with action sampling policy, called AS-DQN, to learn an optimal dispatching policy. Furthermore, we utilize a dueling network architecture, called AS-DDQN, to improve the performance of AS-DQN. Extensive experiments on real-world datasets offer insight into the performance of our model and show that it is capable of outperforming the baseline approaches.

Many datasets including social media data and bibliographic data can be modeled as graphs. Clustering such graphs is able to provide useful insights into the structure of the data. To improve the quality of clustering, node attributes can be taken into account, resulting in attributed graphs. Existing attributed graph clustering methods generally consider attribute similarity and structural similarity separately. In this paper, we represent attributed graphs as star-schema heterogeneous graphs, where attributes are modeled as different types of graph nodes. This enables the use of personalized pagerank (PPR) as a unified distance measure that captures both structural and attribute similarities. We employ DBSCAN for clustering, and we update edge weights iteratively to balance the importance of different attributes. The rapidly growing volume of data nowadays challenges traditional clustering algorithms, and thus, a distributed method is required. Hence, we adopt a popular distributed graph computing system Blogel, based on which, we develop four exact and approximate approaches that enable efficient PPR score computation when edge weights are updated. To improve the effectiveness of the clustering, we propose a simple yet effective edge weight update strategy based on entropy. In addition, we present a game theory based method that enables trading efficiency for result quality. Extensive experiments on real-life datasets offer insights into the effectiveness and efficiency of our proposals.

Knowledge graphs (KGs) have become popular structures for unifying real-world entities by modelling the relationships between them and their attributes. To support multilingual applications, a significant number of language-specific KGs have been built by different parties using various data sources. As a result, these monolingual KGs are often disconnected, causing semantic heterogeneity and detracting from the original purpose of KGs. Entity alignment – the task of identifying corresponding entities across different KGs – has attracted a great deal of attention in both academia and industry. However, existing alignment techniques often require large amounts of labelled data, are unable to encode multi-modal data simultaneously, and enforce only a few consistency constraints. In this paper, we propose an end-to-end, unsupervised entity alignment framework for cross-lingual KGs that fuses different types of information in order to fully exploit the richness of KG data. The model captures the relation-based correlation between entities by using a multi-order graph convolutional neural (GCN) model that is designed to satisfy the consistency constraints, while incorporating the attribute-based correlation via a translation machine. We adopt a late-fusion mechanism to combine all the information together, which allows these approaches to complement each other and thus enhances the final alignment result, and makes the model more robust to consistency violations. Empirical results for various scenarios on real-world and synthetic KGs show that our model is up to 22.71 percent more accurate and orders of magnitude faster than existing baselines. We also demonstrate its sensitivity to hyper-parameters, effort saving in terms of labelling, and the robustness against adversarial conditions.

Streaming spatial-textual data that contains geographic and textual information, e.g., geo-tagged tweets, has an unprecedented increase in amount. As one of the basic operations, the continuous spatial-textual queries that retrieve real-time results continuously on large-scale spatial-textual streams call for means of efficient distributed processing. However, existing proposals either are spatialaware only, or superficially exploit textual information for pruning. We propose a distributed system, called HASTE, for hybrid and adaptive processing on streaming spatial-textual data. The novelty lies on three aspects: (1) We propose a novel method to reduce the workload beforehand by dividing objects and queries into mutually exclusive types; (2) We develop a novel load partitioning strategy and a novel cost model that consider both spatial and textual properties; (3) We design a multi-level load adjustment strategy that adaptively copes with different degrees of load imbalance. We report on extensive experiments with real-world data that offer insight into the performance of the solution, and show that the solution is capable of outperforming the state-of-the-art proposals.

Many navigation applications take natural language speech as input, which avoids typing in words with their hands and decreases the occurrence of traffic accidents. We propose the SpearkNav navigation system that enables users to describe intended routes via speech and supports clue-based route retrieval. SpeakNav includes a route description language understanding model for determining POIs and distances along expected routes, and it includes an efficient algorithm to compute desired routes. In addition, SpeakNav supports basic POI and location search and location-based route navigation. We demonstrate how SpeakNav accurately recognizes users' intentions and recommends appropriate routes in real application scenarios.

Online car-hailing services have gained substantial popularity. An effective taxi fleet management strategy should not only increase taxi utilization by reducing taxi idle time, but should also improve passenger satisfaction by minimizing passenger waiting time. We demonstrate a fleet management system called SOUP that aims at minimizing taxi idle time and that monitors the fleet movement status. SOUP includes a passenger request prediction model called ST-GCSL that predicts the number of requests in the near future, and it includes a demand-aware route planning algorithm called DROP that provides idle taxis with search routes to serve potential requests. In addition, SOUP supports visualizing and analyzing historical passenger requests, simulating fleet movement, and computing evaluation metrics. We demonstrate how SOUP accurately predicts passenger demand and significantly reduces taxi idle time.

Knowledge graph (KG) entity alignment is the task of identifying corresponding entities across different KGs. Existing alignment techniques often require large amounts of labelled data, are unable to encode multi-modal data simultaneously, and enforce only a few consistency constraints. In this paper, we propose an end-to-end, unsupervised entity alignment framework for cross-lingual KGs using multi-order graph convolutional networks. An evaluation of our method using real-world datasets reveals that it consistently outperforms the state-of-the-art in terms of accuracy, efficiency, and label saving.

Trajectory similarity computation is a fundamental component in a variety of real-world applications, such as ridesharing, road planning, and transportation optimization. Recent advances in mobile devices have enabled an unprecedented increase in the amount of available trajectory data such that efficient query processing can no longer be supported by a single machine. As a result, means of performing distributed in-memory trajectory similarity search are called for. However, existing distributed proposals either suffer from computing resource waste or are unable to support the range of similarity measures that are being used. We propose a distributed in-memory management framework called REPOSE for processing top-k trajectory similarity queries on Spark. We develop a reference point trie (RP-Trie) index to organize trajectory data for local search. In addition, we design a novel heterogeneous global partitioning strategy to eliminate load imbalance in distributed settings. We report on extensive experiments with real-world data that offer insight into the performance of the solution, and show that the solution is capable of outperforming the state-of-the-art proposals.

Many navigation applications take natural language speech as input, which avoids users typing in words and thus improves traffic safety. However, navigation applications often fail to understand a user's free-form description of a route. In addition, they only support input of a specific source or destination, which does not enable users to specify additional route requirements. We propose a SpeakNav framework that enables users to describe intended routes via speech and then recommends appropriate routes. Specifically, we propose a novel Route Template based Bidirectional Encoder Representation from Transformers (RT-BERT) model that supports the understanding of natural language route descriptions. The model enables extraction of information of intended POI keywords and related distances. Then we formalize a template-driven path query that uses the extracted information. To enable efficient query processing, we develop a hybrid label index for computing network distances between POIs, and we propose a branch-and-bound algorithm along with a pivot reverse B-tree (PB-tree) index. Experiments with real and synthetic data indicate that RT-BERT offers high accuracy and that the proposed algorithm is capable of outperforming baseline algorithms.

Nowadays, the booming demand of big data analytics and the constraints of computational ability and network bandwidth have made it difficult for a stand-alone agent/service provider to provide suitable information for every user from the large volume online data within the limited time. To handle this challenge, a recommender system (RS) can call in a group of agents to collaborate to learn users' preference and taste, which is known as a distributed recommender system (DRS). DRSs can improve the accuracy of a traditional RS by requesting agents to share information with each other. However, it is challenging for DRSs to make personalized recommendations for each user due to the large amount of candidates. In addition, information sharing among agents raises a privacy concern. Thus, we propose a privacy-preserving DRS in this paper, and then model each service provider as a distributed online learner with context-awareness. Service providers collaborate to make personalized recommendations by learning users' preferences according to the user context and users' history behaviors. We adopt the federated learning framework to help train a high quality privacy- preserving centralized model over a large number of distributed agents which is probably unreliable with relatively slow network connections. To handle big data scenario, we build an item-cluster tree to deal with online and increasing datasets from top to the bottom. We further consider the structure of social network and present an efficient algorithm to avoid more performance loss adaptively. Theoretical proofs show that our proposed algorithm can achieve sublinear regret and differential privacy protection simultaneously for service providers and users. Numerical results confirm that our novel framework can handle increasing big datasets and strike a trade-off between privacy-preserving level and the prediction accuracy.

The ACM SIGSPATIAL GIS Cup 2020 focuses on the Collaborative Spatio-Temporal Searching (CSTS) problem, in which a fleet of mobile agents search for stationary resources on a road network. While each resource can be obtained by exactly one agent, agents can collaborate to obtain resources as quickly as possible. The key of solving CSTS is to guide agents to "hotspot" areas and to avoid the competition by considering agent collaboration. We propose a fleet management method by formulating CSTS as a minimum cost flow problem, called MCF-FM. In addition, we develop a continuous order dispatch strategy. Our submission is the top performer in the agent utilization scenario and runner-up in the customer experience scenario. Our source code is available at: https://github.com/Chriszblong/MCF-FM.

The set similarity join (SSJ) is core functionality in a range of applications, including data cleaning, near-duplicate object detection, and data integration. Threshold-based SSJ queries return all pairs of sets with similarity no smaller than a given threshold. As results, and their utility, are very sensitive to the choice of threshold value, it is a problem that it is difficult to choose such an appropriate value. Doing so requires prior knowledge of the data, which users often do not have. To avoid this problem, we propose a solution to the top-k overlap set similarity join (TkOSSJ) that returns k pairs of sets with the highest overlap similarities. The state-of-the-art solution disregards the effect of the so-called step size, which is the number of elements accessed in each iteration of the algorithm. This affects its performance negatively. To address this issue, we first propose an algorithm that uses a fixed step size, thus taking advantage of the benefits of a large step size, and then we present an adaptive step size algorithm that is capable of automatically adjusting the step size, thus reducing redundant computations. An extensive empirical study offers insight into the new algorithms and indicates that they are capable of outperforming the state-of-the-art method on real, large-scale data sets.

In Pickup-and-Delivery problems (PDP), mobile workers are employed to pick up and deliver items with the goal of reducing travel and fuel consumption. Unlike most existing efforts that focus on finding a schedule that enables the delivery of as many items as possible at the lowest cost, we consider trichromatic (worker-item-task) utility that encompasses worker reliability, item quality, and task profitability. Moreover, we allow customers to specify keywords for desired items when they submit tasks, which may result in multiple pickup options, thus further increasing the difficulty of the problem. Specifically, we formulate the problem of Online Trichromatic Pickup and Delivery Scheduling (OTPD) that aims to find optimal delivery schedules with highest overall utility. In order to quickly respond to submitted tasks, we propose a greedy solution that finds the schedule with the highest utility-cost ratio. Next, we introduce a skyline kinetic tree-based solution that materializes intermediate results to improve the result quality. Finally, we propose a density-based grouping solution that partitions streaming tasks and efficiently assigns them to the workers with high overall utility. Extensive experiments with real and synthetic data offer evidence that the proposed solutions excel over baselines with respect to both effectiveness and efficiency.

The open nature of the Web enables users to produce and propagate any content without authentication, which has been exploited to spread thousands of unverified claims via millions of online documents. Maintenance of credible knowledge bases thus has to rely on fact checking that constructs a trusted set of facts through credibility assessment. Due to an inherent lack of ground truth information and language ambiguity, fact checking cannot be done in a purely automated manner without compromising accuracy. However, state-of-the-art fact checking services, rely mostly on human validation, which is costly, slow, and non-transparent. This paper presents FactCatch, a human-in-the-loop system to guide users in fact checking that aims at minimisation of the invested effort. It supports incremental quality estimation, mistake mitigation, and pay-as-you-go instantiation of a high-quality fact database.

Nearest neighbor (NN) search in high-dimensional spaces is inherently computationally expensive due to the curse of dimensionality. As a well-known solution to approximate NN search, locality-sensitive hashing (LSH) is able to answer c-approximate NN ( c -ANN) queries in sublinear time with constant probability. Existing LSH methods focus mainly on building hash bucket based indexing such that the candidate points can be retrieved quickly. However, existing coarse-grained structures fail to offer accurate distance estimation for candidate points, which translates into additional computational overhead when having to examine unnecessary points. This in turn reduces the performance of query processing. In contrast, we propose a fast and accurate LSH framework, called PM-LSH, that aims to compute the c -ANN query on large- scale, high-dimensional datasets. First, we adopt a simple yet effective PM-tree to index the data points. Second, we develop a tunable confidence interval to achieve accurate distance estimation and guarantee high result quality. Third, we propose an efficient algorithm on top of the PM-tree to improve the performance of computing c -ANN queries. Extensive experiments with real-world data offer evidence that PM-LSH is capable of outperforming existing proposals with respect to both efficiency and accuracy.

The pervasiveness of GPS-enabled devices and wireless communication technologies results in massive trajectory data, incurring expensive cost for storage, transmission, and query processing. To relieve this problem, in this paper we propose a novel framework for compressing trajectory data, REST (Reference-based Spatio-temporal trajectory compression), by which a raw trajectory is represented by concatenation of a series of historical (sub-)trajectories (called reference trajectories) that form the compressed trajectory within a given spatio-temporal deviation threshold. In order to construct a reference trajectory set that can most benefit the subsequent compression, we propose three kinds of techniques to select reference trajectories wisely from a large dataset such that the resulting reference set is more compact yet covering most footprints of trajectories in the area of interest. To address the computational issue caused by the large number of combinations of reference trajectories that may exist for resembling a given trajectory, we propose efficient greedy algorithms that run in the blink of an eye and dynamic programming algorithms that can achieve the optimal compression ratio. Compared to existing work on trajectory compression, our framework has few assumptions about data such as moving within a road network or moving with constant direction and speed, and better compression performance with fairly small spatio-temporal loss. In addition, by indexing the reference trajectories directly with an in-memory R-tree and building connections to the raw trajectories with inverted index, we develop an extremely efficient algorithm that can answer spatio-temporal range queries over trajectories in their compressed form. Extensive experiments on a real taxi trajectory dataset demonstrate the superiority of our framework over existing representative approaches in terms of both compression ratio and efficiency.

With the proliferation of geo-textual objects on the web, extensive efforts have been devoted to improving the efficiency of top-k spatial keyword queries in different settings. However, comparatively much less work has been reported on enhancing the quality and usability of such queries. In this context, we propose means of enhancing the usability of a top-k group spatial keyword query, where a group of users aim to find k objects that contain given query keywords and are nearest to the users. Specifically, when users receive the result of such a query, they may find that one or more objects that they expect to be in the result are in fact missing, and they may wonder why. To address this situation, we develop a so-called why-notquery that is able to minimally modifythe original query into a query that returns the expected, but missing, objects, in addition to other objects. Specifically, we formalize the why-not query in relation to the top-k group spatial keyword query, called the Why-not Group Spatial Keyword Query (WGSK) that is able to provide a group of users with a more satisfactory query result. We propose a three-phase framework for efficiently computing the WGSK. The first phase substantially reduces the search space for the subsequent phases by retrieving a set of objects that may affect the ranking of the user-expected objects. The second phase provides an incremental sampling algorithm that generates candidate weightings of more promising queries. The third phase determines the penalty of each refined query and returns the querywith minimal penalty, i.e., the minimally modified query. Extensive experiments with real and synthetic data offer evidence that the proposed solution excels over baselines with respect to both effectiveness and efficiency.

The explosive growth of e-commerce has led to the development of the recommendation system. The recommendation system aims to provide a set of items that meet users’ personalized needs through analyzing users’ consumption records. However, the timeliness of purchasing data and the implicity of feedback data pose severe challenges for the existing recommendation methods. To alleviate these challenges, we exploit the user’s consumption records from the perspectives of user and item, by modeling the data on both item and user level, where the item-level value reflects the grade of item, and the user-level value reflects the user’s purchase intention. In this article, we collect the description information and the reviews of the items from public websites, then adopt sentiment analysis techniques to model the similarities on user level and item level, respectively. In particular, we extend the traditional latent factor model and propose two novel methods— I tem L evel Similarity M atrix F actorization (ILMF) and U ser L evel Similarity M atrix F actorization (ULMF)—by introducing two novel similarity measure methods. In ILMF and ULMF, the consistency between latent factors and explicit aspects is naturally incorporated into learning latent factors of the users and items, such that we can predict the users’ preferences on different items more accurately. Moreover, we propose I tem- U ser L evel Similarity M atrix F actorization (IULMF), which combines these two methods to study their contributions on the final performance. Experimental evaluations on the real datasets show that our methods outperform the baseline approaches in terms of both the precision and NDCG.

Detecting rumor source in social networks is one of the key issues for defeating rumors automatically. Although many efforts have been devoted to defeating online rumors, most of them are proposed based an assumption that the underlying propagation model is known in advance. However, this assumption may lead to impracticability on real data, since it is usually difficult to acquire the actual underlying propagation model. Some attempts are developed by using label propagation to avoid the limitation caused by lack of prior knowledge on the underlying propagation model. Nonetheless, they still suffer from the shortcoming that the node label is simply an integer which may restrict the prediction precision. In this paper, we propose a deep learning based model, namely GCNSI (Graph Convolutional Networks based Source Identification), to locate multiple rumor sources without prior knowledge of underlying propagation model. By adopting spectral domain convolution, we build node representation by utilizing its multi-order neighbors information such that the prediction precision on the sources is improved. We conduct experiments on several real datasets and the results demonstrate that our model outperforms state-of-the-art model.

The turn-by-turn route descriptions provided in the existing navigation applications are exclusively derived from underlying road network topology information, i.e., the connectivity of edges to each other. Therefore, the turn-by-turn route descriptions are simplified as metric translation of physical world (e.g. distance/time to turn) to spoken language. Such translation that ignores human cognition of the geographic space, is frequently verbose and redundant for the drivers who have knowledge of the geographical areas. In this paper, we study a Personalized Route Description system dubbed PerRD-with which the goal is to generate more customized and intuitive route descriptions based on user generated content. PerRD utilizes a wealth of user generated historical trajectory data to extract frequently visited routes in the road network. The extracted information is used to make cognitive customized route description for each user. We formalize this task as a problem of finding the optimal partition for a given route that maximizes the familiarity while minimizing the number of partitions, and finding a proper sentence to describe each partition. For empirical study, our solution is applied to three trajectory datasets and users' real experiences to evaluate the performance and effectiveness of PerRD.

The competitive spatial-temporal searching (CSTS) problem finds many applications in the daily life, such as ridesharing, car parking, and EV charging, where the mobile agents search for stationary resources on a road network. A key issue of CSTS is how agents should choose their search path such that the search time is minimized. To solve CSTS, we are faced with two main challenges: (1) how to find an optimal space partitioning granularity such that the resource availability pattern of each region is well modeled; (2) how to design a route search algorithm to avoid the "herding" effect as the agents tend to adopt a common search strategy. In this paper, we propose a Spatial-Temporal Partitioning (STP) approach to cope with these two issues. First, we partition the search space into regions by considering both spatial and temporal information of the historical resource records, and compute a weight for each region. Second, we assign a shortest-travel-time path to each agent from its current location to a relatively popular region according to the current time. Extensive experiments are conducted on a real dataset, which show that STP outperforms the baseline algorithm about 24 to 29 seconds in terms of average search time, and about 38% to 54% in terms of average wait time. The source code is available at: https://github.com/Chriszblong/STP.

Many datasets including social media data and bibliographic data can be modeled as graphs. Clustering such graphs is able to provide useful insights into the structure of the data. To improve the quality of clustering, node attributes can be taken into account, resulting in attributed graphs. Existing attributed graph clustering methods generally consider attribute similarity and structural similarity separately. In this paper, we represent attributed graphs as star-schema heterogeneous graphs, where attributes are modeled as different types of graph nodes. This enables the use of personalized pagerank (PPR) as a unified distance measure that captures both structural and attribute similarity. We employ DBSCAN for clustering, and we update edge weights iteratively to balance the importance of different attributes. To improve the efficiency of the clustering, we develop two incremental approaches that aim to enable efficient PPR score computation when edge weights are updated. To boost the effectiveness of the clustering, we propose a simple yet effective edge weight update strategy based on entropy. In addition, we present a game theory based method that enables trading efficiency for result quality. Extensive experiments on real-life datasets offer insight into the effectiveness and efficiency of our proposals, compared with existing methods.

Nowadays, mobile devices are already seen everywhere in life, which makes the application of vehicle navigation more and more widely. The traditional turn-by-turn navigation does the path planning just based on the characteristics of the roads themselves, and then gives mechanized steering instructions at each corner. For those roads people are familiar with in this route, path descriptions which provide detailed route description information, will become redundant and verbose. In this paper, we study a Personalized Route Description system dubbed PerRD - with which the goal is to generate more customized and intuitive route descriptions based on user generated content. The goal is to optimize a given route description with paths which users know well, which makes the route more consistent with users' driving habits, and to create a concise and meaningful route descriptions with POIs and street names.

With the proliferation of geo-textual objects on the web, extensive efforts have been devoted to improving the efficiency of top-k spatial keyword queries in different settings. However, comparatively much less work has been reported on enhancing the quality and usability of such queries. In this context, we propose means of enhancing the usability of a top-k group spatial keyword query, where a group of users aim to find k objects that contain given query keywords and are nearest to the users. Specifically, when users receive the result of such a query, they may find that one or more objects that they expect to be in the result are in fact missing, and they may wonder why. To address this situation, we develop a so-called why-not query that is able to minimally modify the original query into a query that returns the expected, but missing, objects, in addition to other objects. Specifically, we formalize the why-not query in relation to the top-k group spatial keyword query, called the Why-not Group Spatial Keyword Query (WGSK) that is able to provide a group of users with a more satisfactory query result. We propose a three-phase framework for efficiently computing he WGSK. Extensive experiments with real and synthetic data offer evidence that the proposed solution excels over baselines with respect to both effectiveness and efficiency.

The time signals behind a user's historical behaviors are important for better inferring what she prefers to interact with at the next time. For the attention-based recommendation methods, relative position encoding and time intervals division are two common ways to model the time signal behind each behavior. They either only consider the relative position of each behavior in the behavior sequence, or process the continuous temporal features into discrete category features for subsequent tasks, which can hardly capture the dynamic preferences of a user. In addition, although the existing recommendation methods have considered both long-term preference and short-term preference, they ignore the fact that the long-term preference of a user may be multi-faceted, and it is difficult to learn a user's fine-grained short-term preference. In this paper, we propose a Dynamic Multi-faceted Fine-grained Preference model (DMFP), where the multi-hops attention mechanism and the feature-level attention mechanism together with a vertical convolution operation are adopted to capture users' multi-faceted long-term preference and fine-grained short-term preference, respectively. Therefore, DMFP can better support the next item recommendation. Extensive experiments on three real-world datasets illustrate that our model can improve the effectiveness of the recommendation compared with the state-of-the-art methods.

Social platforms became a major source of rumours. While rumours can have severe real-world implications, their detection is notoriously hard: Content on social platforms is short and lacks semantics; it spreads quickly through a dynamically evolving network; and without considering the context of content, it may be impossible to arrive at a truthful interpretation. Traditional approaches to rumour detection, however, exploit solely a single content modality, e.g., social media posts, which limits their detection accuracy. In this paper, we cope with the aforementioned challenges by means of a multi-modal approach to rumour detection that identifies anomalies in both, the entities (e.g., users, posts, and hashtags) of a social platform and their relations. Based on local anomalies, we show how to detect rumours at the network level, following a graph-based scan approach. In addition, we propose incremental methods, which enable us to detect rumours using streaming data of social platforms. We illustrate the effectiveness and efficiency of our approach with a real-world dataset of 4M tweets with more than 1000 rumours.

The Web constitutes a valuable source of information. In recent years, it fostered the construction of large-scale knowledge bases, such as Freebase, YAGO, and DBpedia. The open nature of the Web, with content potentially being generated by everyone, however, leads to inaccuracies and misinformation. Construction and maintenance of a knowledge base thus has to rely on fact checking, an assessment of the credibility of facts. Due to an inherent lack of ground truth information, such fact checking cannot be done in a purely automated manner, but requires human involvement. In this paper, we propose a comprehensive framework to guide users in the validation of facts, striving for a minimisation of the invested effort. Our framework is grounded in a novel probabilistic model that combines user input with automated credibility inference. Based thereon, we show how to guide users in fact checking by identifying the facts for which validation is most beneficial. Moreover, our framework includes techniques to reduce the manual effort invested in fact checking by determining when to stop the validation and by supporting efficient batching strategies. We further show how to handle fact checking in a streaming setting. Our experiments with three real-world datasets demonstrate the efficiency and effectiveness of our framework: A knowledge base of high quality, with a precision of above 90%, is constructed with only a half of the validation effort required by baseline techniques.

Participatory sensing has become a new data collection paradigm that leverages the wisdom of the crowd for big data applications without spending cost to buy dedicated sensors. It collects data from human sensors by using their own devices such as cell phone accelerometers, cameras, and GPS devices. This benefit comes with a drawback: human sensors are arbitrary and inherently uncertain due to the lack of quality guarantee. Moreover, participatory sensing data are time series that exhibit not only highly irregular dependencies on time but also high variance between sensors. To overcome these limitations, we formulate the problem of validating uncertain time series collected by participatory sensors. In this article, we approach the problem by an iterative validation process on top of a probabilistic time series model. First, we generate a series of probability distributions from raw data by tailoring a state-of-the-art dynamical model, namely Generalised Auto Regressive Conditional Heteroskedasticity (GARCH), for our joint time series setting. Second, we design a feedback process that consists of an adaptive aggregation model to unify the joint probabilistic time series and an efficient user guidance model to validate aggregated data with minimal effort. Through extensive experimentation, we demonstrate the efficiency and effectiveness of our approach on both real data and synthetic data. Highlights from our experiences include the fast running time of a probabilistic model, the robustness of an aggregation model to outliers, and the significant effort saving of a guidance model.

Both reviews and user-item interactions (i.e., rating scores) have been widely adopted for user rating prediction. However, these existing techniques mainly extract the latent representations for users and items in an independent and static manner. That is, a single static feature vector is derived to encode user preference without considering the particular characteristics of each candidate item. We argue that this static encoding scheme is incapable of fully capturing users’ preferences, because users usually exhibit different preferences when interacting with different items. In this article, we propose a novel c ontext- a ware user-item r epresentation l earning model for rating prediction, named CARL. CARL derives a joint representation for a given user-item pair based on their individual latent features and latent feature interactions. Then, CARL adopts Factorization Machines to further model higher order feature interactions on the basis of the user-item pair for rating prediction. Specifically, two separate learning components are devised in CARL to exploit review data and interaction data, respectively: review-based feature learning and interaction-based feature learning . In the review-based learning component, with convolution operations and attention mechanism, the pair-based relevant features for the given user-item pair are extracted by jointly considering their corresponding reviews. However, these features are only reivew-driven and may not be comprehensive. Hence, an interaction-based learning component further extracts complementary features from interaction data alone, also on the basis of user-item pairs. The final rating score is then derived with a dynamic linear fusion mechanism. Experiments on seven real-world datasets show that CARL achieves significantly better rating prediction accuracy than existing state-of-the-art alternatives. Also, with the attention mechanism, we show that the pair-based relevant information (i.e., context-aware information) in reviews can be highlighted to interpret the rating prediction for different user-item pairs.

What-if analysis is a data-intensive exploration to inspect how changes in a set of input parameters of a model influence some outcomes. It is motivated by a user trying to understand the sensitivity of a model to a certain parameter in order to reach a set of goals that are defined over the outcomes. To avoid an exploration of all possible combinations of parameter values, efficient what-if analysis calls for a partitioning of parameter values into data ranges and a unified representation of the obtained outcomes per range. Traditional techniques to capture data ranges, such as histograms, are limited to one outcome dimension. Yet, in practice, what-if analysis often involves conflicting goals that are defined over different dimensions of the outcome. Working on each of those goals independently cannot capture the inherent trade-off between them. In this paper, we propose techniques to recommend data ranges for what-if analysis, which capture not only data regularities, but also the trade-off between conflicting goals. Specifically, we formulate a parametric data partitioning problem and propose a method to find an optimal solution for it. Targeting scalability to large datasets, we further provide a heuristic solution to this problem. By theoretical and empirical analyses, we establish performance guarantees in terms of runtime and result quality.

With the advances in geo-positioning technologies and location-based services, it is nowadays quite common for road networks to have textual contents on the vertices. Previous work on identifying an optimal route that covers a sequence of query keywords has been studied in recent years. However, in many practical scenarios, an optimal route might not always be desirable. Therefore, in this paper, we investigate the problem of clue-based route search (CRS), which allows a user to provide clues on keywords and spatial relationships. First, we propose a greedy algorithm and a dynamic programming algorithm as baselines. To improve efficiency, we develop a branch-and-bound algorithm that prunes unnecessary vertices in query processing. In order to quickly locate candidate, we propose an AB-tree that stores both the distance and keyword information in tree structure. To further reduce the index size, we construct a PB-tree by utilizing the virtue of 2-hop label index to pinpoint the candidate. Extensive experiments are conducted and verify the superiority of our algorithms and index structures.

The pervasiveness of GPS-enabled devices and wireless communication technologies results in massive trajectory data, incurring expensive cost for storage, transmission, and query processing. To relieve this problem, in this paper we propose a novel framework for compressing trajectory data, REST (Reference-based Spatio-temporal trajectory compression), by which a raw trajectory is represented by concatenation of a series of historical (sub-)trajectories (called reference trajectories) that form the compressed trajectory within a given spatio-temporal deviation threshold. In order to construct a reference trajectory set that can most benefit the subsequent compression, we propose three kinds of techniques to select reference trajectories wisely from a large dataset such that the resulting reference set is more compact yet covering most footprints of trajectories in the area of interest. To address the computational issue caused by the large number of combinations of reference trajectories that may exist for resembling a given trajectory, we propose efficient greedy algorithms that run in the blink of an eye and dynamic programming algorithms that can achieve the optimal compression ratio. Compared to existing work on trajectory compression, our framework has few assumptions about data such as moving within a road network or moving with constant direction and speed, and better compression performance with fairly small spatio-temporal loss. Extensive experiments on a real taxi trajectory dataset demonstrate the superiority of our framework over existing representative approaches in terms of both compression ratio and efficiency.

Given a pair of Origin-Destination (OD) locations, the set of trajectories passing from the original to destination, usually possesses the nature to reflect different traveling patterns between OD. In general, the higher diversity these trajectories have, the more various traveling behaviors and greater robustness of the connectivity can be revealed, which highly raises the value of transportation analysis towards the corresponding OD pair. Therefore, in this paper, we introduce a comprehensive and rational measure for trajectory diversity, on top of which we propose a novel query, Top-k Diversified Search (TkDS), that aims to find a set of k OD pairs among all the given OD pairs such that the trajectories traversing in-between have the highest diversity. Owing to the intrinsic characteristics of trajectory data, the computational cost for diversity is considerably high. Thus we present an efficient bounding algorithm with early termination to filter the candidates that are impossible to contribute the result. Finally, we demonstrate some case studies for trajectory diversity on real world dataset and give a comprehensive performance evaluation on the Top-k Diversified Search.

Measuring the similarity (or distance) between trajectories of moving objects is a common procedure taken by most trajectory data-driven applications. One of the biggest challenges of trajectory distances measurement is that the distance needs to be carefully defined in order to reflect the true underlying similarity. This is due to the fact that trajectories are essentially non-uniform sequential data with variable length, attached with both spatial and temporal attributes, which may or may not be considered for similarity measures. Therefore, tens of similarity measures for trajectory data have been proposed; every technique claim an advantage over the others in a different aspect. Hence, it's difficult for users to choose the best-suited technique, as well as the appropriate parameter values, since each technique has distinct performance and characteristics depending on various factors. In this paper, we develop an application that allows to evaluate several techniques in different aspects (accuracy, sensitivity to trajectory features, performance, etc.). We believe that this tool will be able to serve as a practical guideline for both researchers and developers. While researchers can use our tool to assess existing or new techniques, developers can reuse its components to reduce the development complexity.

The turn-by-turn directions provided in existing navigation applications are exclusively derived from underlying road network topology information, i.e., the connectivity of edges to each other. Therefore, the turn-by-turn directions are simplified as metric translation of physical world (e.g. distance/time to turn) to spoken language. Such translation - that ignores human cognition of the geographic space - is often verbose and redundant for the drivers who have knowledge about the geographical areas. In this paper, we study a Personalized RoutE Guidance System dubbed PaRE - with which the goal is to generate more customized and intuitive directions based on user generated content. PaRE utilizes a wealth of user generated historical trajectory data to extract namely "landmarks" (e.g., point of interests or intersections) and frequently visited routes between them from the road network. The extracted information is used to obtain cognitive customized directions for each user. We formalize this task as a problem of finding the optimal partition for a given route that maximizes the familiarity while minimizing the number of segments in the partition, and propose two efficient algorithms to solve it. For empirical study, we apply our solution to both real and synthetic trajectory datasets to evaluate the performance and effectiveness of PaRE.

Single-source and top- k SimRank queries are two important types of similarity search in graphs with numerous applications in web mining, social network analysis, spam detection, etc. A plethora of techniques have been proposed for these two types of queries, but very few can efficiently support similarity search over large dynamic graphs, due to either significant preprocessing time or large space overheads. This paper presents ProbeSim , an index-free algorithm for single-source and top- k SimRank queries that provides a non-trivial theoretical guarantee in the absolute error of query results. ProbeSim estimates SimRank similarities without precomputing any indexing structures, and thus can naturally support real-time SimRank queries on dynamic graphs. Besides the theoretical guarantee, ProbeSim also offers satisfying practical efficiency and effectiveness due to non-trivial optimizations. We conduct extensive experiments on a number of benchmark datasets, which demonstrate that our solutions outperform the existing methods in terms of efficiency and effectiveness. Notably, our experiments include the first empirical study that evaluates the effectiveness of SimRank algorithms on graphs with billion edges, using the idea of pooling.

With the advances in geo-positioning technologies and location-based services, it is nowadays quite common for road networks to have textual contents on the vertices. Previous work on identifying an optimal route that covers a sequence of query keywords has been studied in recent years. However, in many practical scenarios, an optimal route might not always be desirable. For example, a personalized route query is issued by providing some clues that describe the spatial context between PoIs along the route, where the result can be far from the optimal one. Therefore, in this paper, we investigate the problem of clue-based route search (CRS), which allows a user to provide clues on keywords and spatial relationships. First, we propose a greedy algorithm and a dynamic programming algorithm as baselines. To improve efficiency, we develop a branch-and-bound algorithm that prunes unnecessary vertices in query processing. In order to quickly locate candidate, we propose an AB-tree that stores both the distance and keyword information in tree structure. To further reduce the index size, we construct a PB-tree by utilizing the virtue of 2-hop label index to pinpoint the candidate. Extensive experiments are conducted and verify the superiority of our algorithms and index structures.

It is nowadays quite common for road networks to have textual contents on the vertices, which describe auxiliary information (e.g., business, traffic, etc.) associated with the vertex. In such road networks, which are modelled as weighted undirected graphs, each vertex is associated with one or more keywords, and each edge is assigned with a weight, which can be its physical length or travelling time. In this paper, we study the problem of keyword-aware continuous k nearest neighbour (KCkNN) search on road networks, which computes the k nearest vertices that contain the query keywords issued by a moving object and maintains the results continuously as the object is moving on the road network. Reducing the query processing costs in terms of computation and communication has attracted considerable attention in the database community with interesting techniques proposed. This paper proposes a framework, called a Labelling AppRoach for Continuous kNN query (LARC), on road networks to cope with KCkNN query efficiently. First we build a pivot-based reverse label index and a keyword-based pivot tree index to improve the efficiency of keyword-aware k nearest neighbour (KkNN) search by avoiding massive network traversals and sequential probe of keywords. To reduce the frequency of unnecessary result updates, we develop the concepts of dominance interval and region on road network, which share the similar intuition with safe region for processing continuous queries in Euclidean space but are more complicated and thus require more dedicated design. For high frequency keywords, we resolve the dominance interval when the query results changed. In addition, a path-based dominance updating approach is proposed to compute the dominance region efficiently when the query keywords are of low frequency. We conduct extensive experiments by comparing our algorithms with the state-of-the-art methods on real data sets. The empirical observations have verified the superiority of our proposed solution in all aspects of index size, communication cost and computation time.

In this paper, we study a route summarization framework for Personalized Navigation dubbed PerNav - with which the goal is to generate more intuitive and customized turn-by-turn directions based on user generated content. The turn-by-turn directions provided in the existing navigation applications are exclusively derived from underlying road network topology information i.e., the connectivity of nodes to each other. Therefore, the turn-by-turn directions are simplified as metric translation of physical world (e.g. distance/time to turn) to spoken language. Such translation- that ignores human cognition about the geographic space- is often verbose and redundant for the drivers who have knowledge about the geographical areas. PerNav utilizes wealth of user generated historical trajectory data to extract namely "landmarks" (e.g., point of interests or intersections) and frequently visited routes between them from the road network. Then this extracted information is used to obtain cognitive turn-by-turn directions customized for each user.

Route recommendation is one of the most widely used location-based services nowadays, as it is vital for nice-driving experience and smooth public traffic. Given a pair of user-specified origin and destination, a route recommendation service aims to provide users with the routes of the best travelling experience according to given criteria. However, even the routes recommended by the big-thumb service providers can deviate significantly from the ones travelled by experienced drivers, which motivates the previous research that leverages crowds’ knowledge to improve the recommendation quality. Since route recommendation is normally an online task, low-latency response to drivers’ queries is required in this kind of systems. Unfortunately, latency of crowdsourced systems is usually high, because they need to generate tasks and wait for workers’ feedbacks before answering queries. To address this issue, we extend our previous system—CrowdPlanner—by proposing some strategies to reuse existing answers (truths) to deal with newly coming queries more efficiently. A prototype system has been deployed to many voluntary mobile clients and extensive tests on real-scenario queries have shown the superiority of our system in comparison with the results given by map services and popular route-mining algorithms.

Conventional top-k spatial keyword queries require users to explicitly specify their preferences between spatial proximity and keyword relevance. In this work we investigate how to eliminate this requirement by enhancing the conventional queries with interaction, resulting in Interactive Top-k Spatial Keyword (ITkSK) query. Having confirmed the feasibility by theoretical analysis, we propose a three-phase solution focusing on both effectiveness and efficiency. The first phase substantially narrows down the search space for subsequent phases by efficiently retrieving a set of geo-textual k-skyband objects as the initial candidates. In the second phase three practical strategies for selecting a subset of candidates are developed with the aim of maximizing the expected benefit for learning user preferences at each round of interaction. Finally we discuss how to determine the termination condition automatically and estimate the preference based on the user's feedback. Empirical study based on real PoI datasets verifies our theoretical observation that the quality of top-k results in spatial keyword queries can be greatly improved through only a few rounds of interactions.

Driven by the advances in location positioning techniques and the popularity of location sharing services, semantic enriched trajectory data have become unprecedentedly available. While finding relevant Point-of-Interest (POIs) based on users' locations and query keywords has been extensively studied in the past years, it is largely untouched to explore the keyword queries in the context of semantic trajectory database. In this paper, we study the problem of approximate keyword search in massive semantic trajectories. Given a set of query keywords, an approximate keyword query of semantic trajectory (AKQST) returns k trajectories that contain the most relevant keywords to the query and yield the least travel effort in the meantime. The main difference between AKQST and conventional spatial keyword queries is that there is no query location in AKQST, which means the search area cannot be localized. To capture the travel effort in the context of query keywords, a novel utility function, called spatio-textual utility function, is first defined. Then we develop a hybrid index structure called GiKi to organize the trajectories hierarchically, which enables pruning the search space by spatial and textual similarity simultaneously. Finally an efficient search algorithm and fast evaluation of the minimum value of spatio-textual utility function are proposed. The results of our empirical studies based on real check-in datasets demonstrate that our proposed index and algorithms can achieve good scalability.

The last decade has witnessed the prevalence of sensor and GPS technologies that produce a high volume of trajectory data representing the motion history of moving objects. However some characteristics of trajectories such as variable lengths and asynchronous sampling rates make it difficult to fit into traditional database systems that are disk-based and tuple-oriented. Motivated by the success of column store and recent development of in-memory databases, we try to explore the potential opportunities of boosting the performance of trajectory data processing by designing a novel trajectory storage within main memory. In contrast to most existing trajectory indexing methods that keep consecutive samples of the same trajectory in the same disk page, we partition the database into frames in which the positions of all moving objects at the same time instant are stored together and aligned in main memory. We found this column-wise storage to be surprisingly well suited for in-memory computing since most frames can be stored in highly compressed form, which is pivotal for increasing the memory throughput and reducing CPU-cache miss. The independence between frames also makes them natural working units when parallelizing data processing on a multi-core environment. Lastly we run a variety of common trajectory queries on both real and synthetic datasets in order to demonstrate advantages and study the limitations of our proposed storage.

The efficiency of spatial query processing is crucial for many applications such as location-based services. In spatial networks, queries like k-NN queries are all based on network distance evaluation. Classic solutions for these queries rely on network expansion and are not efficient enough for large networks. Some approaches have improved the query efficiency but brought considerable space cost for index. To address these problems, we propose a hierarchical graph partitioning based index named Partition Tree. It organizes the vertices of a spatial network into a hierarchy through a series of graph partitioning processes. Meanwhile precomputed distances are associated with this hierarchy to facilitate efficient query processing. Inspired by the observation that queries are usually invoked around objects of interest, we propose a query-oriented optimization on top of the Partition Tree. It uses a cost model to evaluate the influence of the object distribution and partitioning topology on the query efficiency. Then a cost-efficient graph partitioning method is developed based on this cost model. Experimental results on real datasets demonstrate that our proposed index and algorithms have superior performance over the state-of-the-art approaches and are scalable to large spatial networks.

Understanding the dynamics of human daily mobility patterns is essential for the management and planning of urban facilities and services. Travel smart cards, which record users' public transporting histories, capture rich information of users' mobility pattern. This provides the opportunity to discover valuable knowledge from these transaction records. In recent years, research on measuring user similarity for behavior analysis has attracted a lot of attention in applications such as recommendation systems, crowd behavior analysis applications, and numerous data mining tasks. In this paper, our goal is to estimate the similarity between users' travel patterns according to their travel smart card data. The core of our proposal is a novel user similarity measurement, namely, Travel Spatial-Temporal Similarity (TST), which measures the spatial range and temporal similarity between users. Moreover, we also propose a hybrid index structure, which integrates inverted files and cluster-based partitioning, to allow for efficient retrieval of the top-K most similar users. Through experimental evaluation, our proposed approach is shown to deliver scalable performance.