Temporal Betweenness Centrality (TBC) measures how often a node appears on optimal temporal paths, reflecting its importance in temporal networks. However, exact computation is highly expensive, and real-world TBC distributions are extremely imbalanced, causing learning-based models to overfit to zero-centrality nodes and fail to identify truly central nodes. Existing graph neural networks (GNNs) either ignore temporal dependencies or cannot handle such extreme imbalance. To address these issues, we propose CLGNN, a scalable and inductive contrastive learning-based GNN for accurate TBC prediction. CLGNN preserves temporal path validity through an instance graph and encodes structural, path-time aware dependencies via dual aggregation. To mitigate imbalance, a stability-based clustering-guided contrastive module separates nodes of different centrality levels in representation space, while a regression head estimates TBC values. Extensive experiments on diverse benchmarks demonstrate that CLGNN is scalable, generalizable, and effective.

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

Database parameter automatic tuning is one of the challenging and difficult tasks that database administrators (DBAs) frequently encounter in artificial intelligence (AI) enabled database (DB) systems. Preferentially optimizing key parameters emerges as a critical point in addressing this issue, and it can help identify important parameters by exploring the interactions between parameters. Aiming to overcome the disadvantages of existing methods, we propose a collaborative multi-agents model called CMA+DB to automatically tune DB parameters in an effective and efficient fashion. CMA+DB integrates three components including SAPM (Single-Agent Pre-trained Model), MATM (Multi-Agent Joint Training Model), and PJTM (Probability-based Joint Training Model). SAPM applies the deep deterministic policy gradient to explore the impact of one single agent on DB performance, MATM uses multi-agent deep deterministic policy gradients to find agents that collaboratively work to improve DB performance, and PJTM can enhance parameter tuning by important agents based on a probabilistic selection factor. In the CMA+DB model, each agent is responsible for tuning a portion of the parameters, and multiple agents collaborate to recommend the optimal parameter configuration. This hybrid model can expand the number of tunable parameters in order to perform parameter tuning from the aspects of functions and parameter levels (i.e., global, DB, and session level). Experimental results reveal that CMA+DB obtains the fastest convergence performance (when reaching the largest throughput) of 14.83% faster than the state-of-the-art (SOTA) algorithms in the TPC-C benchmark on average. Essentially, after the phase of SAPM model training, CMA+DB outperforms the performance of the SOTA models in throughput. Furthermore, DB performance of CMA+DB can be improved by 1.758% through the phases of MATM and PJTM model training.

Spatial crowdsourcing (SC) is becoming increasingly popular recently. As a critical issue in SC, task assignment currently faces challenges due to the imbalanced spatiotemporal distribution of tasks. Hence, many related studies and applications focusing on cross-platform task allocation in SC have emerged. Existing work primarily focuses on the maximization of total revenue for inner platform in cross task assignment. In this work, we formulate a SC problem called Cross Dynamic Task Assignment (CDTA) to maximize the overall utility and propose improved solutions aiming at creating a win-win situation for inner platform, task requesters, and outer workers. We first design a hybrid batch processing framework and a novel cross-platform incentive mechanism. Then, with the purpose of allocating tasks to both inner and outer workers, we present a KM-based algorithm that gets the accurate assignment result in each batch and a density-aware greedy algorithm with high efficiency. To maximize the revenue of inner platform and outer workers simultaneously, we model the competition among outer workers as a potential game that is shown to have at least one pure Nash equilibrium and develop a game-theoretic method. Additionally, a simulated annealing-based improved algorithm is proposed to avoid falling into local optima. Last but not least, since random thresholds lead to unstable results when picking tasks that are preferentially assigned to inner workers, we devise an adaptive threshold selection algorithm based on multi-armed bandit to further improve the overall utility. Extensive experiments demonstrate the effectiveness and efficiency of our proposed algorithms on both real and synthetic datasets.

Time series anomaly detection aims to identify samples that deviate from a normal distribution in a time series, which is practically important to a variety of real-world applications. Existing approaches are mostly centralized and domain-specific, and thus they are hard to generalize to time series of different domains that are decentralized due to the privacy concerns and the resulting data silos across institutions. To bridge this gap, we propose FAST-MAD, the first resource-aware framework for efficient federated time series anomaly detection. Operating under a client-server architecture, different clients in FAST-MAD can handle time series from distinct domains. In particular, FAST-MAD first employs a multi-resolution transformation module to capture hierarchical local semantics, frequency-oriented patching as well as inter-time-series interaction. An LLM serves as the main body of the local model for each client, owing to its strong knowledge transfer capabilities. Further, an adaptive modularized separation mechanism is integrated with sharded federated training to reduce computational costs, which innovatively splits the LLM into a U-shaped architecture. To address data heterogeneity across different clients, we propose a decomposed client-server alignment mechanism, featuring a tailored low-rank parameter decomposition that extracts domain-common knowledge. Extensive experiments on multiple cross-domain time series datasets offer insight into the effectiveness and efficiency of FAST-MAD, which outperforms SOTA baselines by up to 10.25% in terms of F1-score and reduces the training time by 40.93%.

Multivariate time series (MTS) anomaly detection identifies abnormal patterns where each timestamp contains multiple variables. Existing MTS anomaly detection methods fall into three categories: reconstruction-based, prediction-based, and classifier-based methods. However, these methods face three key challenges: (1) Unsupervised learning methods, such as reconstruction-based and prediction-based methods, rely on error thresholds, which can lead to inaccuracies; (2) Semi-supervised methods mainly model normal dataand often underuse anomaly labels, limiting detection of subtle anomalies; (3) Supervised learning methods, such as classifier-based approaches, often fail to capture local relationships, incur high computational costs, and are constrained by the scarcity of labeled data. To address these limitations, we proposeMoon, a supervised modality conversion-based multivariate time series anomaly detection framework.Moonenhances the efficiency and accuracy of anomaly detection while providing detailed anomaly analysis reports. First,Moonintroduces a novel multivariate Markov Transition Field (MV-MTF) technique to convert numeric time series data into image representations, capturing relationships across variables and timestamps. Since numeric data retains unique patterns that cannot be fully captured by image conversion alone,Moonemploys a Multimodal-CNN to integrate numeric and image data through a feature fusion model with parameter sharing, enhancing training efficiency. Finally, a SHAP-based anomaly explainer identifies key variables contributing to anomalies, improving interpretability. Extensive experiments on six real-world MTS datasets demonstrate thatMoonoutperforms six state-of-the-art methods by up to 93% in efficiency, 4% in accuracy and, 10.8% in interpretation performance.

Temporal knowledge graphs (TKGs) effectively capture the dynamic evolution of events over time, emerging as a critical driving force in the advancement of artificial intelligence. In recent years, temporal knowledge graph reasoning (TKGR) has garnered significant attention for its ability to address the intrinsic incompleteness of TKGs. Among various TKGR methods, reinforcement learning (RL)-based multi-hop reasoning stands out due to the decision-making capabilities and interpretability. However, existing multi-hop reasoning methods are predominantly designed for the transductive setting where test entities are observed during training, and they exhibit limited performance in the fully-inductive setting where training and test entities are entirely disjoint. Moreover, the sparse links of newly emerged unseen entities in TKGs hinder multi-hop reasoning methods from utilizing sufficient actions to construct multihop relational paths, ultimately impairing reasoning accuracy. To address these challenges, we propose ARLIE (Adaptive Reinforcement Learning with Inductive Embeddings), a novel method capable of conducting multi-hop reasoning in both fully-inductive and transductive settings over TKGs. Specifically, ARLIE consists of the following two key components. (1) A context-based inductive representation method generates finegrained embeddings for unseen entities by exploiting queryrelated contextual information. (2) After obtaining temporal evolution and semantic dependencies of unseen entities, an actionaugmented adaptive RL framework leverages diverse actions to infer missing elements step-by-step over TKGs. Finally, experimental results show that ARLIE surpasses state-of-the-art TKGR methods across both fully-inductive and transductive settings.

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

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

The$\eta$-threshold decomposition in uncertain graphs, which calculates the$\eta$-thresholds for each vertex, is a fundamental problem for graph analysis. While existing studies on$\eta$-threshold decomposition primarily focus on static uncertain graphs, numerous real-world scenarios involve highly dynamic uncertain graphs. It is costly to recompute all$\eta$-thresholds from scratch whenever the uncertain graphs face update operations, e.g., edge insertion and deletion, and the modifications on edge probability. Motivated by this, we introduce efficient$\eta$-threshold maintenance algorithms tailored for dynamic uncertain graphs in this paper. Firstly, we investigate the impact of edge insertion and deletion on$\eta$-thresholds. Building upon this analysis, we introduce the maintenance algorithms designed to adjust the$\eta$thresholds for edge insertions or deletions within the uncertain graphs. Our approaches involve identifying a compact subgraph encompassing all vertices necessitating$\eta$-threshold updates, followed by an iterative process of vertex deletion to complete the$\eta$-threshold updates. To improve the efficiency, we devise three optimizations to further reduce the number of candidate$\eta$-thresholds requiring adjustment. Moreover, we extend the proposed algorithms to handle the$\eta$-threshold maintenance for edge probability change. Extensive experiments on both real and synthetic datasets demonstrate the efficiency of the proposed algorithms. The results reveal that our proposed algorithms consistently outperform the baselines, exhibiting improvements ranging from at least three orders of magnitude to as high as seven orders of magnitude.

Data Preparation (DP), which involves tasks such as data cleaning, imputation and integration, is a fundamental process in data-driven applications. Recently, Large Language Models (LLMs) fine-tuned for DP tasks, i.e., DP-LLMs, have achieved state-of-the-art performance. However, transferring DP-LLMs to novel datasets and tasks typically requires a substantial amount of labeled data, which is impractical in many real-world scenarios. To address this, we propose a knowledge augmentation framework for data preparation, dubbed KNOWTRANS. This framework allows DP-LLMs to be transferred to novel datasets and tasks with a few data points, significantly decreasing the dependence on extensive labeled data. KNOWTRANS comprises two components: Selective Knowledge Concentration and Automatic Knowledge Bridging. The first component re-uses knowledge from previously learned tasks, while the second automatically integrates additional knowledge from external sources. Extensive experiments on 13 datasets demonstrate the effectiveness of KNOWTRANS. KNOWTRANS boosts the performance of the state-of-the-art DP-LLM, Jellyfish-7B, by an average of 4.93%, enabling it to outperform both GPT-4 and GPT-4o.

Trajectory data analysis benefits numerous real-world applications and has attracted substantial attention from the research community. With the rapid proliferation of IoT devices and the emergence of edge computing, there has been an increasing demand for efficient trajectory data analytics in edge environments. However, most existing trajectory analysis systems are designed for cloud-based architectures, which face significant limitations in edge settings. These include resource constraints, dynamic network conditions, and inefficient query handling, leading to sub-optimal performance in edge scenarios. To fill this gap, we propose TrajEdge, an efficient and lightweight framework for trajectory data analysis in edge environments. Implementing TrajEdge requires overcoming obstacles posed by limited resources and the dynamic nature of edge networks. To achieve this, we design a novel trajectory composite compression algorithm that delivers high compression ratios, significantly reducing storage pressure on edge devices. Additionally, we introduce three coflow control strategies optimized for varying network conditions, enabling higher system throughput. To further enhance the efficiency of trajectory queries, we develop a spatiotemporal-aware trie-based peer-to-peer (P2P) index. Experimental evaluations on two real-world datasets and one larger synthetic dataset demonstrate that TrajEdge achieves remarkable performance improvements: more than 200 × gains in storage and query efficiency, up to 64% increases in network throughput, compression ratios of up to 95%, and exceptional scalability compared to the state-of-the-art systems. Our source code is available at https://github.com/ZJU-DAILY/TrajEdge.

Sparse Matrix-Matrix Multiplication (SpMM) is a fundamental operation in graph computing and analytics. However, the irregularity of real-world graphs poses significant challenges to achieving efficient SpMM for graph data on GPUs. Recently, the introduction of new efficient computing cores within GPUs offers new opportunities for acceleration. In this paper, we present HC-SpMM, a pioneering algorithm that leverages Hybrid GPU Cores (Tensor cores and CUDA cores) to accelerate SpMM for graphs. To adapt to the computing characteristics ofdifferent GPU cores, we investigate the impact of sparse graph features on the performance of different cores, develop a data partitioning technique for the graph adjacency matrix, and devise a novel strategy for intelligently selecting the most efficient cores for processing each submatrix. Additionally, we optimize it by considering memory access and thread utilization. To support complex graph computing workloads, we integrate HC-SpMM into the GNN training pipeline. Furthermore, we propose a kernel fusion strategy to enhance data reuse, as well as a cost-effective graph layout reorganization method to mitigate the irregularity of real-world graphs, better fitting the computational models of hybrid GPU cores. Extensive experiments on 14 real-world datasets demonstrate that HC-SpMM achieves an average speedup of 1.33× and 1.23× over state-of-the-art SpMM kernels and GNN frameworks.

An average person usually contains more than 10 trillion human cells, and each cell's transcriptome can be profiled by a single-cell RNA sequence (scRNA-seq). The huge volume and high complexity of scRNA-seq data put challenges on fundamental tasks of scRNA-seq data analysis, i.e., cell type identification and new cell type discovery. In this paper, we demonstrate scRAG, which can efficiently remove batch effect in cell-type identification and enable reliable new cell discovery, facilitated by GPU-based scRNA-seq data management and Large Language Models (LLMs). The GPU-based scRNA-seq data management enables high throughput scRNA-seq data retrieval and update, while the LLM utilizes the retrieval results to remove the batch effect and discover novel cells. We demonstrate scRAG for its: (a) interfaces, (b) GPU-based scRNA-seq data management, and (c) applications in batch effect removal and cancer cell discovery.

In directed graphs, the relationship between users is asymmetric, resulting in two types of triangles: cycle triangles and flow triangles. This paper studies the problem of privacy-preserving triangle counting in directed graphs. Based on different applications, we consider two scenarios, i.e., trusted and untrusted servers. In the literature, privacy-preserving triangle counting in undirected graphs has been widely studied. However, directly applying these algorithms to address our problem suffers from many issues. Concretely, for the trusted server scenario, the differentially private triangle counting algorithms, designed for undirected graphs, exhibit suboptimal performance when applied to directed graphs. Hence, we propose a new centralized differentially private algorithm that adds Laplacian noise to the exact numbers by analyzing global sensitivity. Furthermore, for the untrusted server scenario, the existing techniques cannot be used to count cycle and flow triangles with differential privacy because the local view of each user in directed graphs is limited to out-neighbors rather than all neighbors. Therefore, we design a novel locally differentially private algorithm to provide local unbiased estimation, which implies that after aggregating all the local estimations on the central server side, an unbiased estimation for the numbers of cycle and flow triangles is deduced. Empirical experiments on six real-world graph datasets demonstrate that our proposed algorithms achieve high efficiency and utility.

The missing data problem widely exists in real-life scenarios. The incomplete data analysis through imputation can amplify the errors or bias, hindering the effective analysis. Ex-isting tabular data representation methods overlook the missing state of data values, and thus cannot effectively deal with the incomplete data. In this paper, we propose a novel incomplete tabular data representation system, named MISS. It is capable of enabling all Transformer-based tabular representation methods to effectively handle incomplete data. MISS consists of two modules, i.e., missing mechanism learning (MML) and incomplete data representation (IDR). MML leverages a new missingness propensity score calculation strategy to learn the observed data distribution and missing mechanisms within incomplete data. IDR introduces a novel probability-driven Transformer block, in conjunction with an unbiased representation loss function, for effective representation. We prove that, MISS can eliminate the bias resulting from missingness. Extensive experiments on four public real-world datasets demonstrate that, MISS yields a more than 57 % accuracy gain with competitive efficiency, compared with the state-of-the-art approaches.

Spatio-temporal traffic series prediction is essential in intelligent transportation systems, benefiting various applications such as route planning, vehicle dispatching, and congestion prediction. To tackle privacy leakage aroused by centralized forecasting methods, Federated Learning (FL), a privacy-preserving approach for decentralized model training into disjointed federated clients, has garnered widespread adoption in numerous traffic prediction endeavors. However, existing FL-based approaches ignore spatio-temporal heterogeneity among federated clients, including spatial feature skew, temporal coverage skew, and data quality skew. This makes them inapplicable and unsuitable to real-world scenarios and exhibits subpar prediction performance. To this end, we perform the first study of heterogeneous-aware traffic prediction in the federated environment, proposing a unified and effective framework named Fed4TP. It offers general federated capability for various centralized forecast models, supporting flow, speed, and occupancy prediction tasks. To address spatial feature heterogeneity, Fed4TP develops multi-dimensional personalized federated learning with positive samples contrastive learning for clustering to achieve personalized aggregation and global sharing across diverse clients. To overcome temporal coverage heterogeneity, Fed4TP designs a time window-based federated training mechanism, sequentially training client models and learning missed traffic information with varying time coverage. To tackle data quality heterogeneity, Fed4TP introduces a dual-driven method, i.e., global detection and local denoising, to improve client data quality. Extensive experiments on 4 real-life datasets verify the effectiveness and scalability superiority of Fed4TP in various federated-based traffic prediction tasks, compared with 24 well-known and state-of-the-art baselines. The source code and data of this work are available at https://github.com/ZJU-DAILY/Fed4TP.

With the growing availability of large data repositories within and across organizations, it is becoming feasible to selectively acquire data in the wild for data augmentation, tailored to specific downstream tasks. However, current methodologies concentrate primarily on single-dimensional augmentation tasks for tabular data, such as increasing the number of data points or enriching features. These approaches are not designed for trajectory data, which cannot fully utilize its spatio-temporal characteristics, resulting in suboptimal performance.

Approximate Nearest Neighbor Search (ANNS) in high-dimensional spaces finds extensive applications in databases, information retrieval, recommender systems, etc. While graph-based methods have emerged as the leading solution for ANNS due to their superior query performance, they still face several challenges, such as struggling with local optima and redundant computations. These issues arise because existing methods (i) fail to fully exploit the topological information underlying the proximity graph G, and (ii) suffer from severe distribution mismatches between the base data and queries in practice. To this end, this paper proposes GATE, high-tier proximity Graph with Adaptive Topology and Query Awareness, as a lightweight and adaptive module atop the graph-based indexes to accelerate ANNS. Specifically, GATE formulates the critical problem to identify an optimal entry point in the proximity graph for a given query, facilitating faster online search. By leveraging the inherent clusterability of high-dimensional data, GATE first extracts a small set of hub nodes V as candidate entry points. Then, resorting to a contrastive learning-based two-tower model, GATE encodes both the structural semantics underlying G and the query-relevant features into the latent representations of these hub nodes V. A navigation graph index on V is further constructed to minimize the model inference overhead. Extensive experiments demonstrate that GATE achieves a 1.2-2.0X speed-up in query performance compared to state-of-the-art graph-based indexes.

Trajectory anomaly detection aims to identify patterns in trajectory data that deviate significantly from normal behavior, such as taxi detours, and plays a crucial role in urban computing. However, real-world trajectories are inherently complex, containing diverse anomalies and unavoidable noise. Existing research mainly focuses on coarse-grained trajectory anomalies, such as detour and switch anomalies, while paying limited attention to fine-grained trajectory anomalies, such as time and loop anomalies. Furthermore, they tend to disregard the impact of inherent noise in trajectories. As a result, there remains a gap in developing robust models with strong generalization capabilities to effectively detect fine-grained trajectory anomalies, even in noisy environments.

In this paper, we investigate a new problem of truss-based why-not community search. Given a k-truss community C in a graph G and a why-not vertex w ∉ C, the goal is to insert the minimum number of new edges into G to ensure that w becomes part of the k-truss community. This problem has a wide range of applications, such as friends recommendation and transportation planning. We prove that the truss-based why-not community search problem is NP-hard and propose two efficient heuristic algorithms: the expansion-based algorithm and the simulation-based algorithm. Specifically, the expansion-based algorithm incrementally inserts the edges one by one, guided by a carefully designed edge goodness function that quantifies edge quality to ensure optimal selection. In contrast, the simulation-based algorithm firstly inserts a sufficient number of edges into G to immediately include w in a k-truss community and then removes redundant edges to minimize insertions. Furthermore, we implement a set of optimizations to further enhance the efficiency of both algorithms. Extensive experiments on real-world graphs demonstrate the efficiency and effectiveness of our proposed methods and optimizations.

Maximum Inner Product Search (MIPS) is a fundamental challenge in machine learning and information retrieval, particularly in high-dimensional data applications. Existing approaches to MIPS either rely solely on Inner Product (IP) similarity, which faces issues with local optima and redundant computations, or reduce the MIPS problem to the Nearest Neighbor Search under the Euclidean metric via space projection, leading to topology destruction and information loss. Despite the divergence of the two paradigms, we argue that there is no inherent binary opposition between IP and Euclidean metrics. By stitching IP and Euclidean in the design of indexing and search algorithms, we can significantly enhance MIPS performance. Specifically, this paper explores the theoretical and empirical connections between these two metrics from the MIPS perspective. Our investigation, grounded in graph-based search, reveals that different indexing and search strategies offer distinct advantages for MIPS, depending on the underlying data topology. Building on these insights, we introduce a novel graph-based index called Metric-Amphibious Graph (MAG) and a corresponding search algorithm, Adaptive Navigation with Metric Switch (ANMS). To facilitate parameter tuning for optimal performance, we identify three statistical indicators that capture essential data topology properties and correlate strongly with parameter tuning. Extensive experiments on 12 real-world datasets demonstrate that MAG outperforms existing state-of-the-art methods, achieving up to 4x search speedup while maintaining adaptability and scalability.

Abstract In daily life, there is an increasing demand for efficient management and analysis of spatio-temporal data. However, current systems struggle to balance multi-functionality, scalability, and computational efficiency in this domain. To address this challenge, we introduce PostMan: a productive spatio-temporal data management system. PostMan is based on Apache Spark and Apache Hadoop HDFS. It extensively, efficiently, and scalably supports spatio-temporal data types and operators across multiple API levels. To realize effective data management and analysis, PostMan designs the unified partition management and hybrid index. Based on this, PostMan has designed and implemented a variety of optimization strategies for vector and raster operators. PostMan also introduces a two-phase static partitioning (TPSP) method to maintain load balance before and after partition filtering during the query process. In the first phase, partitions are generated using an enhanced R*-Tree algorithm, while the second phase allocates partitions by modeling the task as an optimization problem solved through greedy algorithms. For faster computation, PostMan introduces processes and program interfaces for GPU accelerated spatio-temporal operators in Spark. Moreover, extensive evaluations using real-world datasets show PostMan’s notable efficiency and scalability advantages (e.g., 13%-36% improvement) over baseline systems, as well as their constituent techniques. Finally, PostMan has been deployed on the public cloud in a Software as a Service (SaaS) model, garnering substantial attention from customers.

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

In high-dimensional vector spaces, Approximate Nearest Neighbor Search (ANNS) is a key component in database and artificial intelligence infrastructures. Graph-based ANNS methods, particularly HNSW, have emerged as leading solutions, offering an impressive trade-off between search efficiency and accuracy. Many vector databases utilize graph indexes as their core algorithms, benefiting from various optimizations to enhance search performance. However, the high indexing time associated with graph algorithms poses a significant challenge, especially given the increasing volume of data, query processing complexity, and dynamic index maintenance demand. This has rendered indexing time a critical performance metric for users. In this paper, we comprehensively analyze the underlying causes of the low graph indexing efficiency on modern CPUs, identifying that distance computation dominates indexing time, primarily due to high memory access latency and suboptimal arithmetic operation efficiency. We demonstrate that distance comparisons during index construction can be effectively performed using compact vector codes at an appropriate compression error. Drawing from insights gained through integrating existing compact coding methods in the graph indexing process, we propose a novel compact coding strategy, named Flash, designed explicitly for graph indexing and optimized for modern CPU architectures. By minimizing random memory accesses and maximizing the utilization of SIMD (Single Instruction, Multiple Data) instructions, Flash significantly enhances cache hit rates and arithmetic operations. Extensive experiments conducted on eight real-world datasets, ranging from ten million to one billion vectors, exhibit that Flash achieves a speedup of 10.4× to 22.9× in index construction efficiency, while maintaining or improving search performance.

Attributed graphs are extensively utilized in marketing, friend recommendations, disease prediction, etc. In attributed graphs, nodes are associated with attributes to enrich the graph representation, while edges indicate relationships between nodes. However, ensuring data privacy when publishing attributed graphs is a significant challenge due to the sensitive nature of both attributes and relationships. Existing methods fail to preserve graph structures effectively and neglect correlations among node attributes, leading to diminished utility for published synthetic graphs. To address these issues, we propose PrivAGS, a framework for publishing attributed graphs with Rényi Differential Privacy (RDP) guarantees. PrivAGS reconstructs graph structures and attributes based on community structures to capture tightly connected features. We propose a bounded Gaussian threshold mechanism to preserve attribute correlations and utilize probabilistic graph models with optimized inference structures to infer distributions and release node attributes. Additionally, PrivAGS introduces a new structural model, MCEG, to capture clustering structures and enable efficient graph reconstruction. Extensive experiments on five real-world datasets show that PrivAGS generates privacy-preserving, high-utility synthetic data.

Maximum Inner Product Search (MIPS) for high-dimensional vectors is pivotal across databases, information retrieval, and artificial intelligence. Existing methods either reduce MIPS to Nearest Neighbor Search (NNS) while suffering from harmful vector space transformations, or attempt to tackle MIPS directly but struggle to mitigate redundant computations due to the absence of the triangle inequality. This paper presents a novel theoretical framework that equates MIPS with NNS without requiring space transformation, thereby allowing us to leverage advanced graph-based indices for NNS and efficient edge pruning strategies, significantly reducing unnecessary computations. Despite a strong baseline set by our theoretical analysis, we identify and address two persistent challenges to further refine our method: the introduction of the P roximity Graph with S pherical P athway (PSP), designed to mitigate the issue of MIPS solutions clustering around large-norm vectors, and the implementation of A daptive E arly T ermination (AET), which efficiently curtails the excessive exploration once an accuracy bottleneck is reached. Extensive experiments reveal that our method is superior to existing state-of-the-art techniques in search efficiency, scalability, and practical applicability. Compared with state-of-the-art graph-based methods, it achieves an average 35% speed-up in query processing and a 3× reduction in index size. Notably, our approach has been validated and deployed in the search engines of Shopee, a well-known online shopping platform. Our code and an industrial-scale dataset for offline evaluation will also be released to address the absence of e-commerce data in public benchmarks.

Vector search is widely employed in recommendation systems, search engines, etc. With the explosive growth of online data and streaming processing engines, streaming vector search has attracted increasing research attention. However, prevailing vector search systems like Vearch, Vespa, and Milvus typically operate as external batch services for streaming processing requirements, resulting in sub-optimal performance for streaming processing scenarios. In this paper, we propose VStream, a distributed streaming vector search system. Implementing such a system is non-trivial, raising three technical challenges in streaming adaptability, system scalability, and real-time response. Specifically, VStream offers a dynamic partitioner that adapts to data distribution changes in vector streams. Additionally, VStream features an effective hierarchical storage architecture facilitated by streaming state management, enabling a hybrid of four-level storage media with diverse access speeds and targets. Furthermore, VStream utilizes dynamic hot-cold patterns, such as access frequency, in the streaming vector data, incorporating a specialized hot-cold separation mechanism to enhance query efficiency. Extensive experiments prove that VStream outperforms existing vector search systems, e.g., achieving 251–373× improvements in query efficiency, 2.2–2.5× savings in CPU usage, and 1.5–2.0× reductions in memory overhead.

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

Trajectory similarity computation in road networks is crucial for data analytics. However, both non-learning-based and learning-based methods face challenges. First, they suffer from low accuracy due to manual parameter selection for model training and the omission of key spatio-temporal features in road networks. Second, they have low efficiency, stemming from the high time complexity of similarity computation and the time-consuming training process. Third, learning-based methods struggle with poor model generality due to the small size of available training samples. To address these challenges, we propose an effective and efficient trajectory similarity learning framework for road networks, called SimRN. To our knowledge, SimRN is the first deep reinforcement learning (DRL) approach for trajectory similarity computation. Specifically, SimRN consists of three key modules: the spatio-temporal prompt information extraction (STP) module, the trajectory representation based on DRL (TrajRL) module, and the graph contrastive learning (GCL) module. The STP module captures spatio-temporal features from road networks to improve the training of the trajectory representation. The TrajRL module automatically selects optimal parameters and enables parallel training, improving both trajectory representation and the efficiency of similarity computations. The GCL module employs a self-supervised contrastive learning paradigm to generate sufficient samples while preserving spatial constraints and temporal dependencies of trajectories. Extensive experiments on two real-world datasets, compared with three state-of-the-art methods, show that SimRN: (i) improves accuracy by 20%–40%, (ii) achieves speedups of 2–4x, and (iii) demonstrates strong generality, enabling effective similarity learning with very small sample sizes.

Community search is a fundamental problem in graph analysis and has attracted much attention for its ability to discover personalized communities. In this paper, we focus on community search over multilayer graphs. We design a novel cohesive subgraph model called synergetic core for multilayer graphs, which requires both local and global cohesiveness. Specifically, the synergetic core mandates that the vertices within the subgraph are not only densely connected on some individual layers but also form more cohesive connections on the projected graph that considers all layers. The local and global cohesiveness collectively ensure the superiority of the synergetic core. Based on this new model, we formulate the problem of synergetic community search. To efficiently retrieve the community, we propose two algorithms. The first is a progressive search algorithm, which enumerates potential layer combinations to compute the synergetic core. The second is a trie-based search algorithm , leveraging our novel index called dominant layers-based trie (DLT). DLT compactly stores synergetic cores within the trie structure. By traversing the DLT, we can efficiently identify the synergetic core. We conduct extensive experiments on ten real-world datasets. Experimental results demonstrate that (1) the synergetic core can find communities with the best quality among the state-of-the-art models, and (2) our proposed algorithms are up to five orders of magnitude faster than the basic method.

Semantic join discovery, which aims to find columns in a table repository with high semantic joinabilities to a query column, is crucial for dataset discovery. Existing methods can be divided into two categories: cell-level methods and column-level methods. However, neither of them ensures both effectiveness and efficiency simultaneously. Cell-level methods, which compute the joinability by counting cell matches between columns, enjoy ideal effectiveness but suffer poor efficiency. In contrast, column-level methods, which determine joinability only by computing the similarity of column embeddings, enjoy proper efficiency but suffer poor effectiveness due to the issues occurring in their column embeddings: (i) semantics-joinability-gap, (ii) size limit, and (iii) permutation sensitivity. To address these issues, this paper proposes to compute column embeddings via proxy columns; furthermore, a novel column-level semantic join discovery framework,${\sf Snoopy}$, is presented, leveraging proxy-column-based embeddings to bridge effectiveness and efficiency. Specifically, the proposed column embeddings are derived from the implicit column-to-proxy-column relationships, which are captured by the lightweight approximate-graph-matching-based column projection. To acquire good proxy columns for guiding the column projection, we introduce a rank-aware contrastive learning paradigm. Extensive experiments on four real-world datasets demonstrate that${\sf Snoopy}$outperforms SOTA column-level methods by 16% in Recall@25 and 10% in NDCG@25, and achieves superior efficiency—being at least 5 orders of magnitude faster than cell-level solutions, and 3.5× faster than existing column-level methods.

The query efficiency of Spark SQL is significantly impacted by its configurations. Therefore, configuration tuning has drawn great attention, and various automatic configuration tuning methods have been proposed. However, existing methods suffer from two issues: (1) high tuning overhead: they need to repeatedly execute the workloads several times to obtain the training samples, which is time-consuming; and (2) low throughput: they need to occupy resources like CPU cores and memory for a long time, causing other Spark SQL workloads to wait, thereby reducing the overall system throughput. These issues impede the use of automatic configuration tuning methods in practical systems which have limited tuning budget and many concurrent workloads. To address these issues, this paper proposes aLow-Overhead andFlexible approach for Spark SQL configurationTuning, dubbedLOFTune. LOFTune reduces the tuning overhead via a sample-efficient optimization framework, which is proposed based on multi-task SQL representation learning and multi-armed bandit. Furthermore, LOFTune solves the low throughput issue with a recommendation-sampling-decoupled tuning framework. Extensive experiments validate the effectiveness of LOFTune. In the sampling-allowed case, LOFTune can save up to 90% of the workload runs comparing with the state-of-the-art methods. Besides, in the zero-sampling case, LOFTune can reduce up to 41.26% of latency.

Link prediction, which aims to predict the existence of a link between two nodes in a network, has various applications ranging from friend recommendation to protein interaction prediction. Recently, Graph Neural Network (GNN)-based link prediction has demonstrated its advantages and achieved the state-of-the-art performance. Typically, GNN-based link prediction can be formulated as a binary classification problem. However, in link prediction, we only have positive data (observed links) and unlabeled data (unobserved links), but no negative data. Therefore, Positive Unlabeled (PU) learning naturally fits the link prediction scenario. Unfortunately, the unknown class prior and data imbalance of networks impede the use of PU learning in link prediction. To deal with these issues, this paper proposes a novel model-agnostic PU learning algorithm for GNN-based link prediction by means ofPositive-Unlabeled Area Under the Receiver Operating Characteristic Curve(PU-AUC) optimization. The proposed method is free of class prior estimation and able to handle the data imbalance. Moreover, we propose an accelerated method to reduce the operational complexity of PU-AUC optimization from quadratic to approximately linear. Extensive experiments back up our theoretical analysis and validate that the proposed method is capable of boosting the performance of the state-of-the-art GNN-based link prediction models.

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

Due to the extraordinarily large number of parameters, fine-tuning large language models (LLMs) to update long-tail or out-of-date knowledge is impractical in lots of applications. To avoid fine-tuning, we can alternatively treat a LLM as a black-box (i.e., freeze the parameters of the LLM) and augment it with a retrieval-augmented generation (RAG) system, namely black-box RAG. Recently, black-box RAG has achieved success in knowledge-intensive tasks and has gained much attention. Existing black-box RAG methods typically fine-tune the retriever to cater to LLMs’ preferences and concatenate all the retrieved documents as the input, which suffers from two issues: (1) Ignorance of Factual Information. The LLM preferred documents may not contain the factual information for the given question, which can mislead the retriever and hurt the effectiveness of black-box RAG; (2) Waste of Tokens. Simply concatenating all the retrieved documents brings large amounts of unnecessary tokens for LLMs, which degenerates the efficiency of black-box RAG. To address these issues, this article proposes a novel black-box RAG framework which utilizes the factual information in the retrieval and reduces the number of tokens for augmentation, dubbed FIT-RAG. FIT-RAG utilizes the factual information by constructing a bi-label document scorer which takes the factual information and LLMs’ preferences as labels respectively. Besides, it reduces the tokens by introducing a self-knowledge recognizer and a sub-document-level token reducer, which enables FIT-RAG to avoid unnecessary augmentation and reduce augmentation tokens as much as possible. FIT-RAG achieves both superior effectiveness and efficiency, which is validated by extensive experiments across three open-domain question-answering datasets: TriviaQA, NQ, and PopQA. FIT-RAG can improve the answering accuracy of Llama2-13B-Chat by 14.3% on TriviaQA, 19.9% on NQ and 27.5% on PopQA, respectively. Furthermore, it can save approximately half of the tokens on average across the three datasets.

Long-term time series forecasting has gained significant attention in recent years due to its widely-application in various fields. Transformer-based models have gained popularity for the ability to capture long-sequence interactions. However, these models are limited in real-world use because of the memory consumption and computation explosion. The CNN-based models are also one of the main models used for time series prediction, but their performance has always been inferior to the transformer-based models in previous works. We have reconsidered the role of CNN components and redefined the way CNN basic components are used for time series prediction. In addition, the time lags information between periods in the time series is important. Unfortunately, existing works lack consideration of this classic but important information. Motivated by these factors, we propose a fast yet effective CNN model with time lags for multivariate long-term time series forecasting, named LagCNN. Specifically, the time series is transformed into lag-patches to capture the correlation between periods. Then, a fast CNN model is performed in the feature dimension rather than the time dimension like most previous works do. Meanwhile, information aggregation is performed in the time dimension to extract complex temporal patterns. LagCNN significantly outperforms state-of-the-art on multiple publicly available datasets. One step further, LagCNN exhibits significant efficiency advantages over the most efficient Transformer model (PatchTST), resulting in a significant reduction in memory usage (4.4×) and runtime (10.7×).

In the era of observability, massive amounts of time series data have been collected to monitor the running status of the target system, where anomaly detection serves to identify observations that differ significantly from the remaining ones and is of utmost importance to enable value extraction from such data. While existing reconstruction-based methods have demonstrated favorable detection capabilities in the absence of labeled data, they still encounter issues of training bias on abnormal times and distribution shifts within time series. To address these issues, we propose a simple yet effective Temporal-Frequency Masked AutoEncoder (TFMAE) to detect anomalies in time series through a contrastive criterion. Specifically, TFMAE uses two Transformer-based autoencoders that respectively incorporate a window-based temporal masking strategy and an amplitude-based frequency masking strategy to learn knowledge without abnormal bias and reconstruct anomalies by the extracted normal information. Moreover, the dual autoencoder undergoes training through a contrastive objective function, which minimizes the discrepancy of representations from temporal-frequency masked autoencoders to highlight anomalies, as it helps alleviate the negative impact of distribution shifts. Finally, to prevent over-fitting, TFMAE adopts adversarial training during the training phase. Extensive experiments conducted on seven datasets provide evidence that our model is able to surpass the state-of-the-art in terms of anomaly detection accuracy.

Trajectory streams are being generated from location-aware devices, such as smartphones and in-vehicle navigation systems. Due to the sensitive nature of the location data, directly sharing user trajectories suffers from privacy leakage issues. Local differential privacy (LDP), which perturbs sensitive data on the user side before it is shared or analyzed, emerges as a promising solution for private trajectory stream collection and analysis. Unfortunately, existing stream release approaches often neglect the rich spatial-temporal context information within trajectory streams, resulting in suboptimal utility and limited types of downstream applications. To this end, we propose RetraSyn, a novel real-time trajectory synthesis framework, which is able to perform on-the-f1y trajectory synthesis based on the mobility patterns privately extracted from users' trajectory streams. Thus, the downstream trajectory analysis can be performed on the high-utility synthesized data with privacy protection. We also take the genuine behaviors of real-world mobile travelers into consideration, ensuring authenticity and practicality. The key components of RetraSyn include the global mobility model, dynamic mobility update mechanism, real-time synthesis, and adaptive allocation strategy. We conduct extensive experiments on multiple real-world and synthetic trajectory datasets under various location-based utility metrics, encompassing both streaming and historical scenarios. The empirical results demonstrate the superiority and versatility of our proposed framework.

Task assignment is a fundamental problem in spatial crowdsourcing. In many spatial crowdsourcing platforms, such as Didi, AMAP, and Uber, there are hybrid tasks, including real-time and reservation-type tasks, which are with different constraints and unevenly distributed in spatial and temporal. For these hybrid tasks, most existing studies suffer from low task completion rate and low profit for two reasons: firstly, they focus on homogeneous tasks with uniform constraints, and assign hybrid tasks separately; secondly, they cannot effectively address the uneven distribution of hybrid tasks. Inspired by this, we delve into the problem of online hybrid task assignment (HyTAO) with the goal of maximizing total revenue by simultaneously assigning both real-time and reservation-type tasks online for the first time. We prove the NP-hardness of the offline version of the HyTAO problem. To solve HyTAO effectively, we utilize a cross-platform cooperation model to tackle the challenge of non-uniform distribution. Following this, we design a binary tree-based search algorithm, namely BTS, which is capable of uniformly processing various types of tasks and quickly searching for available workers. Additionally, we discuss the parallel optimization strategies of BTS. To further enhance performance, we develop TBTS, which identifies tasks with high increased revenue based on a threshold. Finally, we conduct a comprehensive analysis of the complexity and competitive ratio of both BTS and TBTS. Extensive experiments are performed to demonstrate the efficiency of our approaches.

Nowadays, geo-textual data, which consists of both spatial and textual information, have become increasingly preva-lent. The location-based services are ubiquitous in daily life to help users find desirable geo-textual objects. For example, spatial keyword queries return the geo-textual objects that are the most relevant to query location and query keywords. However, entering complete queries (e.g., the query keywords) can be cumbersome and prone to errors. To overcome these limitations, we present a real-time query system called TASKS for instant error-tolerant spatial keyword queries on road networks. TASKS not only returns the results as soon as users type in some characters instead of a complete keyword, but also tolerates typographical errors of input keywords and supports the queries over road networks. We have implemented four modules for TASKS, i.e., Index Module, Query Module, Update Module, and Route Module. In this demonstration, participants will be invited to use TASKS to explore geo-textual objects and routes in a “search-as-you-type” manner.

Due to the ubiquity of missing data, data imputation has received extensive attention in the past decades. It is a well-recognized problem impacting almost all fields of scientific study. Existing imputation algorithms differ in problem settings, model selection, and data evaluation. There is a lack of systematic comparison study among imputation algorithms. In this paper, we survey this interesting and evolving research topic by broadly reviewing and experimentally comparing the state-of-the-art missing data imputation algorithms. We analyze and categorize 19 imputation algorithms. Extensive experiments over 15 real-world benchmark datasets are conducted under various settings of data types, missing mechanisms, missing rates, dataset parameters, as well as the post-imputation prediction task. We shed light on a series of constructive insights on imputation algorithms to tackle missing data problem in real-life scenarios. Moreover, we put forward promising future directions for data imputation.

Subgraph matching has garnered increasing attention for its diverse real-world applications. Given the dynamic nature of real-world graphs, addressing evolving scenarios with-out incurring prohibitive overheads has been a focus of research. However, existing approaches for dynamic subgraph matching often proceed serially, retrieving incremental matches for each updated edge individually. This approach falls short when handling batch data updates, leading to a decrease in system throughput. Leveraging the parallel processing power of GPUs, which can execute a massive number of cores simultaneously, has been widely recognized for performance acceleration in various domains. Surprisingly, systematic exploration of subgraph matching in the context of batch-dynamic graphs, particularly on a GPU platform, remains untouched. In this paper, we bridge this gap by introducing an efficient framework, GAMMA (GPU-Accelerated Batch-Dynamic Subgraph Matching). Our approach features a DFS-based warp-centric batch-dynamic subgraph matching algorithm. To ensure load balance in the DFS-based search, we propose warp-level work stealing via shared memory. Additionally, we introduce coalesced search to reduce redundant computations. Comprehensive experiments demonstrate the superior performance of GAMMA. Compared to state-of-the-art algorithms, GAMMA showcases a performance improvement up to hundreds of times.

Counting ($p$, q)-bicliques in bipartite graphs poses a foundational challenge with broad applications, from densest sub-graph discovery in algorithmic research to personalized content recommendation in practical scenarios. Despite its significance, current leading ($p$, q)-biclique counting algorithms fall short, particularly when faced with larger graph sizes and clique scales. Fortunately, the problem's inherent structure, allowing for the independent counting of each biclique starting from every vertex, combined with a substantial set intersections, makes it highly amenable to parallelization. Recent successes in GPU-accelerated algorithms across various domains motivate our exploration into harnessing the parallelism power of GPUs to efficiently address the ($p$, q)-biclique counting challenge. We introduce GBC (GPU-based Biclique Counting), a novel approach designed to enable efficient and scalable ($p$, q)-biclique counting on GPUs. To address major bottleneck arising from redundant comparisons in set intersections (occupying an average of 90% of the runtime), we introduce a novel data structure that hashes adjacency lists into truncated bitmaps to enable efficient set intersection on GPUs via bit-wise AND operations. Our in-novative hybrid DFS-BFS exploration strategy further enhances thread utilization and effectively manages memory constraints. A composite load balancing strategy, integrating pre-runtime and runtime workload allocation, ensures equitable distribution among threads. Additionally, we employ vertex reordering and graph partitioning strategies for improved compactness and scalability. Experimental evaluations on eight real-life and two synthetic datasets demonstrate that GBC outperforms state-of-the-art algorithms by a substantial margin. In particular, GBC achieves an average speedup of$497.8\times$, with the largest instance achieving a remarkable$1217.7\times$speedup when$p=q=8$.

We investigate the problem of multimodal search of target modality, where the task involves enhancing a query in a specific target modality by integrating information from auxiliary modalities. The goal is to retrieve relevant objects whose contents in the target modality match the specified multimodal query. The paper first introduces two baseline approaches that integrate techniques from the Database, Information Retrieval, and Computer Vision communities. These baselines either merge the results of separate vector searches for each modality or perform a single-channel vector search by fusing all modalities. However, both baselines have limitations in terms of efficiency and accuracy as they fail to adequately consider the varying importance of fusing information across modalities. To overcome these limitations, the paper proposes a novel framework, Multimodal Search of Target Modality, called MUST. Our framework employs a hybrid fusion mechanism, combining different modalities at multiple stages. Notably, we leverage vector weight learning to determine the importance of each modality, thereby enhancing the accuracy of joint similarity measurement. Additionally, the proposed framework utilizes a fused proximity graph index, enabling efficient joint search for multimodal queries. MUST offers several other advantageous properties, including a plug-gable design to integrate any advanced embedding techniques, user flexibility to customize weight preferences, and modularized index construction. Extensive experiments on real-world datasets demonstrate the superiority of MUST over the baselines in terms of both search accuracy and efficiency. Our framework achieves over 10× faster search times while attaining an average of 93% higher accuracy. Furthermore, MUST exhibits scalability to datasets containing more than 10 million data elements.

Time series classification assigns predefined labels or classes to sequences of data points ordered chronologically, which is a fundamental task for time series analysis. Existing time series classification methods mainly focus on a specific type of time series (i.e., univariate time series or multivariate time series), while failing to support both of them efficiently and effectively. In addition, most of existing multivariate time series classification methods model all variables collectively, resulting in protracted computational times and suboptimal accuracy. In this paper, we introduce TSec, an innovative time series classification framework that exhibits high training efficiency and classification accuracy for both univariate time series and multivariate time series. During online classification, TSec first involves sequence segmentation and de-duplication, and then employs pre-trained models to perform classifications. To opti-mize the classification performance, TSec (i) utilizes correlation analysis to reveal closely interconnected groups of variables within multivariate time series data; (ii) incorporates time series alignment and different sliding windows to generate potential shapelets; (iii) applies PAA and SAX techniques to eliminate duplicates, thereby enhancing the quality of shapelets; (iv) adopts Bi-GRU and GCN-GRU models to effectively capture the characteristics of the two types of time series. Extensive experiments on 112 public univariate time series datasets and 26 public multivariate time series datasets show that TSec can achieve both high efficiency and accuracy compared with the state-of-the-art 19 toolkits.

Contact tracing query (CTQ) plays a crucial role in the prevention of epidemic diseases. In real-world applications, user trajectory, encompassing a wealth of sensitive information, is typically dispersed across various devices or organizations. Consequently, safeguarding user privacy becomes imperative in the context of CTQ. Simultaneously, for effective epidemic control, it is essential to identify contacts efficiently and accurately, enabling prompt implementation of necessary measures. However, existing CTQ studies face limitations as they struggle to concurrently meet the demands of privacy, accuracy and efficiency. This constraint impedes their practical application in real-world scenarios. To this end, we define the Federated Contact Tracing Query (F-CTQ) problem and propose the FedCTQ framework based on hierarchical federation. To the best of our knowledge, this is the first solution grounded in federation, offering a simultaneous fulfillment of privacy, accuracy and efficiency requirements. Specifically, to ensure the privacy of F-CTQ, we introduce a meticulously designed binary-based secret-sharing (BSS) scheme, which delivers an effective privacy guarantee for user data while preserving the accuracy of the query results. Concurrently, to enhance the efficiency of F-CTQ, we propose a binary-based distance tree (DistTree) index that maximizes computational resources for parallel queries. Based on DistTree, FedCTQ enables nearly the real-time and accurate execution of F-CTQ. Extensive experiments on four datasets demonstrate the superiority of FedCTQ, showcasing a remarkable performance improvement ranging from$4.7\times$to$14.8\times$over state-of-the-art approaches.

Entity Matching (EM), which aims to identify all pairs of records referring to the same real-world entity from relational tables, is one of the most important tasks in real-world data management systems. Due to the labeling process of EM being extremely labor-intensive, unsupervised EM is more applicable than supervised EM in practical scenarios. Traditional unsupervised EM assumes that all entities come from two tables; however, it is more common to match entities from multiple tables in practical applications, that is, multi-table entity matching (multi-table EM). Unfortunately, effective and efficient unsupervised multi-table EM remains under-explored. To fill this gap, this paper formally studies the problem of unsupervised multi-table entity matching and proposes an effective and efficient solution, termed as MultiEM. MultiEM is a parallelable pipeline of enhanced entity representation, table-wise hierarchical merging, and density-based pruning. Extensive experimental results on six real-world benchmark datasets demonstrate the superiority of MultiEM in terms of effectiveness and efficiency.

Top-k sparsification has recently been widely used to reduce the communication volume in distributed deep learning. However, due to the Sparse Gradient Accumulation (SGA) dilemma, the performance of top-k sparsification still has limitations. Recently, a few methods have been put forward to handle the SGA dilemma. Regrettably, even the state-of-the-art method suffers from several drawbacks, e.g., it relies on an inefficient communication algorithm and requires extra transmission steps. Motivated by the limitations of existing methods, we propose a novel efficient sparse communication framework, called SparDL. Specifically, SparDL uses the Spar-Reduce-Scatter algorithm, which is based on an efficient Reduce-Scatter model, to handle the SGA dilemma without additional communication operations. Besides, to further reduce the latency cost and improve the efficiency of SparDL, we propose the Spar-All-Gather algorithm. Moreover, we propose the global residual collection algorithm to ensure fast convergence of model training. Finally, extensive experiments are conducted to validate the superiority of SparDL.

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

Accurate vehicle trajectory recovery enables providing indispensable data foundations in intelligent urban transportation. However, existing methods face two challenges: i) the inability to process city-wide vehicle trajectories, and ii) the dependence on a substantial amount of accurate GPS trajectories for model training, leading to poor generalization ability. To address these issues, we propose a novel trajectory recovery system based on vehicle snapshots captured by traffic cameras, named TrajRecovery. TrajRecovery consists of three main components: i) Preprocessor processes traffic cameras and vehicle snapshots to provide necessary data for trajectory recovery; ii) Spatial Transfer Probabilistic Model (STPM) integrates road conditions and driver behavior to compute turning probability at intersections; iii) Trajectory Generator utilizes the output probabilities from STPM to recover a continuous and most likely complete trajectory. We evaluate TrajRecovery on two real datasets from a city in China, demonstrating substantial performance gains compared to state-of-the-art methods. Furthermore, our system is deployed in practical applications at Huawei Company, achieving extraordinary profits in business scenarios.

Betweenness centrality of a vertex in a graph evaluates how often the vertex occurs in the shortest paths. It is a widely used metric of vertex importance in graph analytics. While betweenness centrality on static graphs has been extensively investigated, many real-world graphs are time-varying and modeled as temporal graphs. Examples include social networks and telecommunication networks, where a relationship between two vertices occurs at a specific time. Hence, in this paper, we target efficient methods for temporal betweenness centrality computation. We firstly propose an exact algorithm with the new notion of time instance graph, based on which, we derive a temporal dependency accumulation theory for iterative computation. To reduce the size of the time instance graph and improve the efficiency, we propose an additional optimization, which compresses the time instance graph with equivalent vertices and edges, and extends the dependency theory to the compressed graph. Since it is theoretically complex to compute temporal betweenness centrality, we further devise a probabilistically guaranteed approximate method to handle massive temporal graphs. Extensive experimental results on real-world temporal networks demonstrate the superior performance of the proposed methods. In particular, our exact and approximate methods outperform the state-of-the-art methods by up to two and five orders of magnitude, respectively.

Generating explanations for graph neural networks (GNNs) has been studied to understand their behaviors in analytical tasks such as graph classification. Existing approaches aim to understand the overall results of GNNs rather than providing explanations for specific class labels of interest, and may return explanation structures that are hard to access, nor directly queryable. We propose GVEX, a novel paradigm that generates Graph Views for GNN EXplanation. (1) We design a two-tier explanation structure called explanation views. An explanation view consists of a set of graph patterns and a set of induced explanation subgraphs. Given a database G of multiple graphs and a specific class label l assigned by a GNN-based classifier M, it concisely describes the fraction of G that best explains why l is assigned by M. (2) We propose quality measures and formulate an optimization problem to compute optimal explanation views for GNN explanation. We show that the problem is Σ2P-hard. (3) We present two algorithms. The first one follows an explain-and-summarize strategy that first generates high-quality explanation subgraphs which best explain GNNs in terms of feature influence maximization, and then performs a summarization step to generate patterns. We show that this strategy provides an approximation ratio of 1/2. Our second algorithm performs a single-pass to an input node stream in batches to incrementally maintain explanation views, having an anytime quality guarantee of 1/4-approximation. Using real-world benchmark data, we experimentally demonstrate the effectiveness, efficiency, and scalability of GVEX. Through case studies, we showcase the practical applications of GVEX.

Core models are well-known cohesive subgraph models for graph analytics that have been extensively studied. These models, including (α, β)-core, (k, l)-core, and k -core, have multiple parameters, which are referred to as multi-dimensional cores. The goal of core search is to retrieve subgraphs from a graph that satisfy the semantics of a given core model. In the literature, various indexes have been proposed to accelerate core search for different core models. However, existing indexes suffer from several limitations, such as significant redundancy, lack of scalability with respect to the number of parameters, limited generality, and inadequate consideration of index maintenance. To address these limitations, in this paper, we thoroughly investigate the problem of multi-dimensional core search. In particular, we propose a novel index called MCR-Tree, which can be applied to different core models. The MCR-Tree projects all vertices into a multi-dimensional space by leveraging the skyline corenesses, which are indexed by an R-tree. Furthermore, the MCR-Tree integrates the connectivity information of subgraphs into the nodes of the R-tree to facilitate multi-dimensional core search. Subsequently, an efficient branch-and-bound algorithm is designed to perform multi-dimensional core search by traversing the MCR-Tree. Additionally, we discuss how to maintain the MCR-Tree for graph updates. Extensive experiments demonstrate that the MCR-Tree is up to two orders of magnitude smaller than existing indexes and the MCR-Tree-based core search method is up to an order of magnitude faster than existing algorithms.

High-dimensional vector similarity search (HVSS) is gaining prominence as a powerful tool for various data science and AI applications. As vector data scales up, in-memory indexes pose a significant challenge due to the substantial increase in main memory requirements. A potential solution involves leveraging disk-based implementation, which stores and searches vector data on high-performance devices like NVMe SSDs. However, implementing HVSS for data segments proves to be intricate in vector databases where a single machine comprises multiple segments for system scalability. In this context, each segment operates with limited memory and disk space, necessitating a delicate balance between accuracy, efficiency, and space cost. Existing disk-based methods fall short as they do not holistically address all these requirements simultaneously. In this paper, we present Starling, an I/O-efficient disk-resident graph index framework that optimizes data layout and search strategy within the segment. It has two primary components: (1) a data layout incorporating an in-memory navigation graph and a reordered disk-based graph with enhanced locality, reducing the search path length and minimizing disk bandwidth wastage; and (2) a block search strategy designed to minimize costly disk I/O operations during vector query execution. Through extensive experiments, we validate the effectiveness, efficiency, and scalability of Starling. On a data segment with 2GB memory and 10GB disk capacity, Starling can accommodate up to 33 million vectors in 128 dimensions, offering HVSS with over 0.9 average precision and top-10 recall rate, and latency under 1 millisecond. The results showcase Starling's superior performance, exhibiting 43.9x higher throughput with 98% lower query latency compared to state-of-the-art methods while maintaining the same level of accuracy.

Time series compression encodes the information in a time-ordered sequence of data points into fewer bits, thereby reducing storage costs and possibly other costs. Compression methods are either general or XOR-based. General compression methods are time-consuming and are not suitable in streaming scenarios, while XOR-based methods are unable to consistently maintain high compression ratios. Further, existing methods compress the integer and decimal parts of floating-point values as a whole, thus disregarding the different characteristics of the two parts. We propose Camel , a new compression method for floating-point time series with the goal of advancing the compression ratios and efficiency achievable. Camel compresses the integer and decimal parts of the double-precision floating-point numbers in time series separately; and instead of performing XOR operations on values using their previous value, Camel identifies values that enable higher compression ratios. Camel also includes means of indexing compressed data, thereby making it possible to query compressed data efficiently. We report on an empirical study of Camel and 11 lossless and 6 lossy compression methods on 22 public datasets and three industrial datasets from AliCloud. The study offers evidence that Camel is capable of outperforming existing methods in terms of both compression ratio and efficiency and is capable of excellent compression performance on both time series and non-time series data.

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

Recent years have witnessed a growing trend toward employing deep reinforcement learning (Deep-RL) to derive heuristics for combinatorial optimization (CO) problems on graphs. Maximum Coverage Problem (MCP) and its probabilistic variant on social networks, Influence Maximization (IM), have been particularly prominent in this line of research. In this paper, we present a comprehensive benchmark study that thoroughly investigates the effectiveness and efficiency of five recent Deep-RL methods for MCP and IM. These methods were published in top data science venues, namely S2V-DQN, Geometric-QN, GCOMB, RL4IM, and LeNSE. Our findings reveal that, across various scenarios, the Lazy Greedy algorithmconsistently outperforms allDeep-RL methods for MCP. In the case of IM, theoretically sound algorithms like IMM and OPIM demonstrate superior performance compared to Deep-RL methods in most scenarios. Notably, we observe anabnormal phenomenonin IM problem where Deep-RL methods slightly outperform IMM and OPIM when the influence spread nearly does not increase as the budget increases. Furthermore, our experimental results highlight common issues when applying Deep-RL methods to MCP and IM in practical settings. Finally, we discuss potential avenues for improving Deep-RL methods. Our benchmark study sheds light on potential challenges in current deep reinforcement learning research for solving combinatorial optimization problems.

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

Retrieval-augmented Large Language Models (LLMs) have reshaped traditional query-answering systems, offering unparalleled user experiences. However, existing retrieval techniques often struggle to handle multi-modal query contexts. In this paper, we present an interactive M ulti-modal Q uery A nswering (MQA) system, empowered by our newly developed multi-modal retrieval framework and navigation graph index, integrated with cutting-edge LLMs. It comprises five core components: Data Preprocessing, Vector Representation, Index Construction, Query Execution, and Answer Generation, all orchestrated by a dedicated coordinator to ensure smooth data flow from input to answer generation. One notable aspect of MQA is its utilization of contrastive learning to assess the significance of different modalities, facilitating precise measurement of multimodal information similarity. Furthermore, the system achieves efficient retrieval through our advanced navigation graph index, refined using computational pruning techniques. Another highlight of our system is its pluggable processing framework, allowing seamless integration of embedding models, graph indexes, and LLMs. This flexibility provides users diverse options for gaining insights from their multi-modal knowledge base. A preliminary video introduction of MQA is available at https://youtu.be/xvUuo2ZIqWk.

Materialized views (MVs) are critical for improving query performance of database systems, especially in online analytical processing (OLAP) databases. Typically, MVs are maintained by DBAs, which relies on prior knowledge and manual operations. Recently, autonomous solutions are designed for specific databases. However, a data warehouse for OLAP is typically hierarchical, which uses different database engines at different stages. Hence, existing methods have limitations in terms of autonomy and unification to support practical applications. Motivated by these, we develop UniView, a unified autonomous materialized view management system that supports various popular databases, including Spark SQL, PostgreSQL, and ClickHouse. Moreover, we provide a cross-platform web user interface, where users can carry out the process of materialized views and evaluate the optimization performance. In the demonstration, we show that UniView is user-friendly and can achieve superior performance in the practical industry scenarios.

The growth in sensor technologies, IoT devices, and information systems has opened up new opportunities for managing time series data across various domains. Despite significant progress, existing time series management systems face two crucial limitations: insufficient functionality and inadequate adaptability. This highlights the need for more comprehensive systems that not only improve data quality and analysis but also effectively manage the variety and volume of time series data. This paper presents TENDS, a time series management system based on model selection. TENDS uniquely combines advanced functionalities for imputation, prediction, and anomaly detection, offering a comprehensive analysis of time series data. It features (i) an effective model selection mechanism to adapt to various data types and to improve efficiency; (ii) fourteen state-of-the-art prediction methods and three state-of-the-art imputation methods; and (iii) a dynamic expert knowledge base for anomaly detection, evolving continuously with new data to ensure accuracy. TENDS boasts a comprehensive suite of visualization tools. With its configurable offline and online interfaces, TENDS (i) provides extensive flexibility in model selection and parameter adjustment, (ii) facilitates easy visualization of training results, and (iii) supports real-time documentation and statistical analysis of time series.

Selecting a good execution plan can significantly improve the query efficiency of Spark SQL. Several machine learning-based techniques have been proposed to select good execution plans for DBMS, but none of them perform well on Spark SQL due to the following issues. (1) Limited compatibility with Spark SQL: these approaches rely on physical operator enumeration, while Spark SQL doesn't support it; (2) Unreliable cost estimation: they often select execution plans with poor performance due to inaccurate cost estimation; (3) Time-consuming plan enumeration: they take much time to generate a large number of candidate execution plans in Spark SQL. To overcome these issues, in this paper, we propose LEAP, the first learned query optimizer tailored for Spark SQL, which can be integrated seamlessly into Spark SQL and solves the compatibility issue. Also, to avoid the unreliable cost value estimation, LEAP selects execution plans with an estimation-free method, which directly performs comparisons between the plans. Furthermore, LEAP employs an efficient progressive plan enumeration algorithm with pruning techniques to find better plans with fewer enumerations. Extensive experiments on three public benchmarks show the effectiveness of LEAP. It reduces the end-to-end execution time of the native optimizer by up to 54% and other learned methods by up to 94%.

Centralised data management systems (e.g., data lakes) support queries over multi-source heterogeneous data. However, the query results from multiple sources commonly involve between-source conflicts, which makes query results unreliable and confusing and degrades the usability of centralised data management systems. Therefore, resolving the between-sourced conflicts is one of the most important problems for centralised data management systems. To solve it, many batch data fusion-based methods have been proposed, which require traversing all the data in the centralised data management systems and cause scalability and flexibility issues. To address these issues, this paper explores the problem of on-demand fusion queries, where the between-sourced conflicts are solved with only the query-related data; moreover, we propose an efficient on-demand fusion query framework, FusionQuery, which consists of a query stage and a fusion stage. In the query stage, we frame the heterogeneous data query problem as a knowledge graph matching problem and present a line graph-based method to accelerate it. In the fusion stage, we develop an Expectation Maximization-style algorithm to iteratively updates data veracity and source trustworthiness. Furthermore, we design an incremental estimation method of source trustworthiness to address the lack of sufficient observations. Extensive experiments on two real-world datasets demonstrate that FusionQuery outperforms state-of-the-art data fusion methods in terms of both effectiveness and efficiency.

With the widespread use of GPS-enabled devices and services, trajectory data fuels services in a variety of fields, such as transportation and smart cities. However, trajectory data often contains errors stemming from inaccurate GPS measurements, low sampling rates, and transmission interruptions, yielding low-quality trajectory data with negative effects on downstream services. Therefore, a crucial yet tedious endeavor is to assess the quality of trajectory data, serving as a guide for subsequent data cleaning and analyses. Despite some studies addressing general-purpose data quality assessment, no studies exist that are tailored specifically for trajectory data. To more effectively diagnose the quality of trajectory data, we propose T-Assess, an automated trajectory data quality assessment system. T-Assess is built on three fundamental principles: i) extensive coverage, ii) versatility, and iii) efficiency. To achieve comprehensive coverage, we propose assessment criteria spanning validity, completeness, consistency, and fairness. To provide high versatility, T-Assess supports both offline and online evaluations for full-batch trajectory datasets as well as real-time trajectory streams. In addition, we incorporate an evaluation optimization strategy to achieve assessment efficiency. Extensive experiments on four real-life benchmark datasets offer insight into the effectiveness of T-Assess at quantifying trajectory data quality beyond the capabilities of state-of-the-art data quality systems.

With the explosive ubiquity of GPS-equipped devices, e.g., mobile phones, vehicles, and vessels, a massive amount of real-time, unbounded, and varying-sampling trajectory streams are being generated continuously. Clustering trajectory streams is useful in real-life applications, such as traffic congestion prediction, crowd flow detection, and moving behavior study. Although several sliding-window based algorithms (that adopt the classic two-phases online-offline processing framework) are proposed for trajectory stream clustering, three challenges exist to meet ever-increasing application demands for effective, efficient, and scalable online clustering: i) How to effectively model unbounded trajectory streams in the online settings for effective clustering? ii) How to achieve truly real-time online processing? iii) How to improve the scalable capability of the clustering algorithm to support large-scale moving trajectory streams? In this paper, we propose an efficient and distributed trajectory stream clustering framework that can: i) model trajectory streams dynamically and effectively in a self-adaptive manner, i.e.,$k$-Segment, which considers both spatial and temporal aspects of trajectory streams, ii) support distributed indexing, processing, and workload balance, and iii) incrementally cluster trajectory streams in an efficient manner. Experiments on a wide range of real-world trajectory datasets show that our framework outperforms state-of-the-art baselines in terms of clustering quality, efficiency, and scalability.

Spatio-temporal trajectory analytics are useful in diversified applications such as urban planning, infrastructure development, and vehicular networks. Trajectory similarity measure, which aims to evaluate the distance between two trajectories, is a fundamental functionality of trajectory analytics. In this paper, we propose a comprehensive survey that investigates all the most common and representative spatio-temporal trajectory measures. First, we provide an overview of spatio-temporal trajectory measures in terms of three hierarchical perspectives: Non-learning versus Learning, Free Space versus Road Network, and Standalone versus Distributed. Next, we present an evaluation benchmark by designing five real-world transformation scenarios. Based on this benchmark, extensive experiments are conducted to study the effectiveness, robustness, efficiency, and scalability of each measure, which offers guidelines for trajectory measure selection among multiple techniques and applications such as trajectory data mining, deep learning, and distributed processing. Specifically, i) Effectiveness: In terms of trajectory length, DFD and Seg-Frechet are length-sensitive, while OWD and Hausdorff always return same results when varying query trajectory length. In terms of trajectory shape, LCRS and LORS are able to effectively find similar trajectories for query trajectories with different shapes; ii) Robustness: Learning based measures are more robust compared with non-learning based ones. Among non-learning based measures, DFD, Hausdorff, OWD and Seg-Frechet are relatively non-sensitive to noises and different sampling rates; and iii) Efficiency& Scalability: Compared to non-learning based measures, learning based and distributed based measures are more efficient and scalable.

The ubiquitous GPS sensors collect massive trajectory data from moving objects, which is useful in data mining applications. However, trajectory data is enormous in volume, and thus, directly storing and processing the raw data is expensive. Using trajectory simplification, a trajectory can be reduced to a set of continuous line segments with acceptable data loss, which is an efficient method. Although many algorithms are proposed, they still suffer from the following issues including (i) non-data driven capability as most studies rely on human-crafted rules or pre-defined parameters, (ii) bound with error measures that yield high computational cost, and (iii) focusing only on the local information preservation in trajectories, but failing in capturing the global mobility patterns for trajectory compression.To address the above issues, we propose a Seq2Seq2Seq framework, abbreviated S3, which consists of two chained Seq2Seq. With differentiable reconstruction learning, S3 enables self-supervised trajectory simplification in a lightweight manner. Besides, we deploy S3 over the graph neural architecture to capture the context-aware mobility patterns and enhance the representation paradigm of trajectories with geographical semantics, where a context-aware distance measure is designed for quality evaluation. An online extension of S3 is also developed to enable streaming trajectory simplifications. Finally, extensive experiments using two real-world datasets in both offline and online scenarios show that S3 achieves much higher efficiency (e.g., it achieves up to one order of magnitude speed-up gains) and comparable compression quality, compared with both non-learning and state-of-the-art learning-based methods.

Table interpretation (TI), which aims to predict the column types and relations of tables, plays an essential role in necessary decision-making actions for data management systems. Typically, TI is followed by a manual verification, where experts manually verify the correctness of TI’s predictions. Manual verification is able to ensure the quality of decision-making actions but labor-intensive. To reduce the labour costs, providing explanations for TI’s predictions is necessary as these explanations can help them do faster and more accurate verification. However, existing TI approaches overlook the manual verification process and lack explainability1. To fill this gap, this paper explores the challenging explainable table interpretation problem, which aims to provide faithful explanations and meanwhile achieve high prediction performance. Furthermore, we propose ExplainTI framework. ExplainTI consists of two phases: (i) tables are converted to sequences and lightweight column graphs; and (ii) a pre-trained transformer encoder is fine-tuned to provide multi-view explanations and aggregate contextual information. Extensive experiments on both real Web tables and database tables confirm that ExplainTI outperforms competitive baselines. Moreover, systematical analysis of explainability demonstrates that our framework can provide faithful explanations to facilitate the manual verification process.

(α, β)-core is an important cohesive subgraph model for bipartite graphs. Given a bipartite graph G, the problem of (α, β)-core decomposition is to compute non-empty (α, β)-cores for all possible values of α and β. The state-of-the-art (α, β)-core decomposition algorithm is a peeling-based algorithm, which iteratively deletes the vertex from high degree to low degree. However, as the peeling-based algorithm is designed for centralized environments, it cannot be applied to distributed environments, where graphs are partitioned and stored in different machines. Motivated by this, in this paper, we study the distributed (α, β)-core decomposition problem, aiming to develop new algorithms to support (α, β)-core decomposition in distributed environments. To this end, first, we analyze the local properties of (α, β)-core, and devise n-order Bi-indexes for the vertex, which are iteratively defined using the vertex neighbors’ (n − 1)-order Bi-indexes. Next, we propose an algorithm for (α, β)-core decomposition through iteratively calculating n-order Bi-indexes for every vertex. To further improve the efficiency of the algorithm, we propose two optimizations. Then, we extend our proposed algorithms to different distributed graph processing frameworks to make them run in distributed environments. Finally, extensive experimental results on both real and synthetic bipartite graphs demonstrate the efficiency of our proposed algorithms.

Trading the machine learning-based prediction services has been up-and-coming for individuals and small companies. It serves to directly provide the predictions, e.g., classifications, for consumers without domain knowledge. Existing prediction service pricing methods closely rely on the strong assumption of completely known information on service quality and consumers’ valuations. In this paper, we study the profit maximization problem of pricing prediction services under incomplete information for the first time. We propose a novel Service Market model, named SMELT, considering multiple types of customers with dEmand and quaLity-aware valuaTions. We first derive the theoretical optimal solution to maximize service profit with complete information. Then, we develop an effective framework PSPricer under the profit ratio guarantee to solve the profit maximization problem with incomplete information. It is capable of not only efficiently getting the sub-optimal service price with bounded revenue loss, but also effectively estimating the service quality function with the maximum likelihood estimation. Extensive experiments on real-life datasets demonstrate our theoretical findings and the effectiveness and efficiency of PSPricer, compared with the state-of-the-art approaches.

As a novel intelligent sensing paradigm, spatial crowdsourcing has received extensive attention. Task assignment is a key issue in spatial crowdsourcing. In practice, tasks are unevenly distributed in time and space. Accordingly, the problem of cross task assignment attracts growing attention in both industry and academia. Although there has been a research on this problem, it focuses only on maximizing total revenues for inner platforms. Therefore, it can also be improved to bring a multi-win situation for outer workers and task requesters as well as the inner platform. Inspired by this, we first formulate a new cross dynamic task assignment (CDTA) problem by introducing the reputation scores of workers, and prove it to be NP-hard. For the CDTA problem, a hybrid batch-based framework is presented on the basis of a new cross-platform incentive mechanism and a hybrid batch processing strategy, which are efficient in solving the problem of uneven spatial and time distribution of tasks, respectively. After that, a KM-based algorithm and a density-aware greedy algorithm are proposed to gain an accurate assignment result of tasks in each batch and good performance, respectively. Furthermore, the CDTA problem is modeled as a potential game that is proven to have at least a pure Nash Equilibrium theoretically. Last but not least, a game-theoretic approach is developed to maximize the revenues of the inner platform and outer workers at the same time. Extensive experiments on both real and synthetic datasets are conducted to demonstrate the effectiveness and efficiency of the proposed algorithms.

Federated learning (FL) has emerged as a paradigm to train a global machine learning model in a distributed manner while taking privacy concerns and data protection regulations into consideration. Although a variety of FL algorithms have been proposed, the training efficiency of FL remains challenging due to massive mathematical computations and expensive client-server communication costs. However, existing FL-acceleration studies are limited as they can only solve the computation and communication overheads separately, which is suboptimal and constrains their acceleration ability. Moreover, previous studies are typically designed for specific FL scenarios and can support only one or two FL models, thus exhibiting poor generality.To fill these critical voids, we propose FLBooster, which provides unified and efficient acceleration capacity for a broad range of FL models. This is the first proposal to solve the computation and communication overheads simultaneously. Specifically, we utilize GPUs to boost the computation-intensive homomorphic encryption (HE) operations in a parallel manner, which significantly reduces the computation costs. On the other hand, a simple but efficient compression method is designed to lighten the exchange of data volumes between client and server. Extensive experiments using four standard FL models on three datasets show that FLBooster acquires superior speed-up gains (i.e., 14.3× – 138×) over state-of-the-art acceleration systems. Finally, we integrate FLBooster into the open-source FL benchmark FATE and offer user-friendly APIs for development.

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

Entity alignment (EA) aims to find equivalent entities in different knowledge graphs (KGs). State-of-the-art EA approaches generally use Graph Neural Networks (GNNs) to encode entities. However, most of them train the models and evaluate the results in a full-batch fashion, which prohibits EA from being scalable on large-scale datasets. To enhance the usability of GNN-based EA models in real-world applications, we present SEA, a scalable entity alignment system that enables to (i) train large-scale GNNs for EA, (ii) speed up the normalization and the evaluation process, and (iii) report clear results for users to estimate different models and parameter settings. SEA can be run on a computer with merely one graphic card. Moreover, SEA encompasses six state-of-the-art EA models and provides access for users to quickly establish and evaluate their own models. Thus, SEA allows users to perform EA without being involved in tedious implementations, such as negative sampling and GPU-accelerated evaluation. With SEA, users can gain a clear view of the model performance. In the demonstration, we show that SEA is user-friendly and is of high scalability even on computers with limited computational resources.

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.

Knowledge graph (KG), which contains rich side information, becomes an essential part to boost the recommendation performance and improve its explainability. However, existing knowledge-aware recommendation methods directly perform information propagation on KG and user-item bipartite graph, ignoring the impacts of task-irrelevant knowledge propagation and vulnerability to interaction noise, which limits their performance. To solve these issues, we propose a robust knowledge-aware recommendation framework, called Knowledge-refined Denoising Network (KRDN), to prune the task-irrelevant knowledge associations and noisy implicit feedback simultaneously. KRDN consists of an adaptive knowledge refining strategy and a contrastive denoising mechanism, which are able to automatically distill high-quality KG triplets for aggregation and prune noisy implicit feedback respectively. Besides, we also design the self-adapted loss function and the gradient estimator for model optimization. The experimental results on three benchmark datasets demonstrate the effectiveness and robustness of KRDN over the state-of-the-art knowledge-aware methods like KGIN, MCCLK, and KGCL, and also outperform robust recommendation models like SGL and SimGCL. The implementations are available at https://github.com/xj-zhu98/KRDN.

Collaborative Filtering (CF) is a widely used and effective technique for recommender systems. In recent decades, there have been significant advancements in latent embedding-based CF methods for improved accuracy, such as matrix factorization, neural collaborative filtering, and LightGCN. However, the explainability of these models has not been fully explored. Adding explainability to recommendation models can not only increase trust in the decision-making process, but also have multiple benefits such as providing persuasive explanations for item recommendations, creating explicit profiles for users and items, and assisting item producers in design improvements.

Entity alignment (EA) is a fundamental data integration task that identifies equivalent entities between different knowledge graphs (KGs). Temporal Knowledge graphs (TKGs) extend traditional knowledge graphs by introducing timestamps, which have received increasing attention. State-of-the-art time-aware EA studies have suggested that the temporal information of TKGs facilitates the performance of EA. However, existing studies have not thoroughly exploited the advantages of temporal information in TKGs. Also, they perform EA by pre-aligning entity pairs, which can be labor-intensive and thus inefficient. In this paper, we present DualMatch that effectively fuses the relational and temporal information for EA. DualMatch transfers EA on TKGs into a weighted graph matching problem. More specifically, DualMatch is equipped with an unsupervised method, which achieves EA without necessitating the seed alignment. DualMatch has two steps: (i) encoding temporal and relational information into embeddings separately using a novel label-free encoder, Dual-Encoder; and (ii) fusing both information and transforming it into alignment using a novel graph-matching-based decoder, GM-Decoder. DualMatch is able to perform EA on TKGs with or without supervision, due to its capability of effectively capturing temporal information. Extensive experiments on three real-world TKG datasets offer the insight that DualMatch significantly outperforms the state-of-the-art methods.

Trajectory similarity queries, including similarity search and similarity join, offer a foundation for many geo-spatial applications. With the rapid increase of streaming trajectory data volumes, e.g., data from mobile phones, vessel monitoring, or traffic systems, many location-based services benefit from online similarity analytics over trajectory data streams, where moving objects continually emit real-time position data. However, most existing studies focus on offline settings, and thus several major challenges remain unanswered in an online setting. To this end, we describe Ghost, a distributed stream processing framework that enables generic, efficient, and scalable online trajectory similarity search and join. We propose a novel incremental online similarity computation (IOSC) mechanism to accelerate pair-wise streaming trajectory distance calculation, which supports a broad range of trajectory distance metrics. Compared with previous studies, IOSC reduces the complexity from quadratic to linear in terms of trajectory length. Building on this foundation, we propose histogram-based algorithms that exploit histogram indexes and a series of pruning bounds to enable streaming trajectory similarity search and join. Finally, we extend our methods to the distributed platform Flink for scalability, where a CostPartitioner is developed to ensure parallel processing and workload balancing. An experimental study using two real-life and one synthetic datasets shows that Ghost (i) acquires 6-20× efficiency/throughput gains and one order of magnitude memory overhead savings over state-of-the-art baselines, (ii) achieves 3--8× workload balancing gains on Flink, and (iii) exhibits low parameter sensitivity and high robustness.

Cardinality estimation, predicting the query result size, is a fundamental problem in databases. Existing skyline cardinality estimation methods are computationally infeasible for massive skyline queries over the large-scale database. In this paper, we introduce a unified skyline family w.r.t. various skyline variants. We propose an efficient and effective skyline family cardinality estimation model, named EECE, in an end-to-end manner. EECE consists of two modules, unsupervised data distribution learning (DDL) and supervised monotonic cardinality estimation (MCE). DDL leverages the mixture data guided transformer to learn the distribution of database and query parameters for model pre-training. MCE further incorporates supervised learning and parameter clamping to enhance the estimation under monotonicity guarantees. We develop an efficient incremental learning algorithm for EECE to adapt the database and query logs update. Extensive experiments on several real-world and synthetic datasets demonstrate that, EECE speeds up the cardinality estimation by six orders of magnitude, with more than 39% accuracy gain, compared to the state-of-the-art approaches.

Bipartite graphs characterize relationships between two different sets of entities, like actor-movie, user-item, and author-paper. The butterfly, a 4-vertices 4-edges (2,2)-biclique, is the simplest cohesive motif in a bipartite graph and is the fundamental component of higher-order substructures. Counting and enumerating the butterflies offer significant benefits across various applications, including fraud detection, graph embedding, and community search. While the corresponding motif, the triangle, in the unipartite graphs has been widely studied in both static and temporal settings, the extension of butterfly to temporal bipartite graphs remains unexplored. In this paper, we investigate the temporal butterfly counting and enumeration problem: count and enumerate the butterflies whose edges establish following a certain order within a given duration. Towards efficient computation, we devise a non-trivial baseline rooted in the state-of-the-art butterfly counting algorithm on static graphs, further, explore the intrinsic property of the temporal butterfly, and develop a new optimization framework with a compact data structure and effective priority strategy. The time complexity is proved to be significantly reduced without compromising on space efficiency. In addition, we generalize our algorithms to practical streaming settings and multi-core computing architectures. Our extensive experiments on 11 large-scale real-world datasets demonstrate the efficiency and scalability of our solutions.

The social network host has knowledge of the network structure and user characteristics and can earn a profit by providing merchants with viral marketing campaigns. We investigate the problem of host profit maximization by leveraging performance incentives and user flexibility. To incentivize the host's performance, we propose setting a desired influence threshold that would allow the host to receive full payment, with the possibility of a small bonus for exceeding the threshold. Unlike existing works that assume a user's choice is frozen once they are activated, we introduce the Dynamic State Switching model to capture "comparative shopping" behavior from an economic perspective, in which users have the flexibilities to change their minds about which product to adopt based on the accumulated influence and propaganda strength of each product. In addition, the incentivized cost of a user serving as an influence source is treated as a negative part of the host's profit. The host profit maximization problem is NP-hard, submodular, and non-monotone. To address this challenge, we propose an efficient greedy algorithm and devise a scalable version with an approximation guarantee to select the seed sets. As a side contribution, we develop two seed allocation algorithms to balance the distribution of adoptions among merchants with small profit sacrifice. Through extensive experiments on four real-world social networks, we demonstrate that our methods are effective and scalable.

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

Instant spatial keyword queries return the results as soon as users type in some characters instead of a complete keyword, which allow users to query the geo-textual data in a type-as-you-search manner. However, the existing methods of instant spatial keyword queries suffer from several limitations. For example, the existing methods do not consider the typographical errors of input keywords, and cannot be applied to the road networks. To overcome these limitations, in this paper, we propose a new query type, i.e., instant error-tolerant spatial keyword queries on road networks. To answer the queries efficiently, we present a framework, termed as Task, which consists of index component, query component, and update component. In the index component, we design a novel index called reverse 2-hop label based trie, which seamlessly integrates spatial and textual information for each vertex of the road network. Based on our proposed index, we devise efficient algorithms to progressively return and update the query results in the query component and update component, respectively. Finally, we conduct extensive experiments on real-world road networks to evaluate the performance of our presented Task. Empirical results show that our proposed index and algorithms are up to 1--2 orders of magnitude faster than the baseline.

Hosting database services on cloud systems has become a common practice. This has led to the increasing volume of database workloads, which provides the opportunity for pattern analysis. Discovering workload patterns from a business logic perspective is conducive to better understanding the trends and characteristics of the database system. However, existing workload pattern discovery systems are not suitable for large-scale cloud databases which are commonly employed by the industry. This is because the workload patterns of large-scale cloud databases are generally far more complicated than those of ordinary databases. In this paper, we propose Alibaba Workload Miner (AWM), a real-time system for discovering workload patterns in complicated large-scale workloads. AW M encodes and discovers the SQL query patterns logged from user requests and optimizes the querying processing based on the discovered patterns. First, Data Collection & Preprocessing Module collects streaming query logs and encodes them into high-dimensional feature embeddings with rich semantic contexts and execution features. Next, Online Workload Mining Module separates encoded query by business groups and discovers the workload patterns for each group. Meanwhile, Offline Training Module collects labels and trains the classification model using the labels. Finally, Pattern-based Optimizing Module optimizes query processing in cloud databases by exploiting discovered patterns. Extensive experimental results on one synthetic dataset and two real-life datasets (extracted from Alibaba Cloud databases) show that AW M enhances the accuracy of pattern discovery by 66% and reduce the latency of online inference by 22%, compared with the state-of-the-arts.

Time series forecasting, that predicts events through a sequence of time, has received increasing attention in past decades. The diverse range of time series forecasting models presents a challenge for selecting the most suitable model for a given dataset. As such, the Alibaba Cloud database monitoring system must address the issue of selecting an optimal forecasting model for a single time series data. While several model selection frameworks, including AutoAI-TS, have been developed to predict a dataset, their effectiveness may be limited as they may not adapt well to all types of time series, resulting in reduced prediction accuracy. Alternatively, models such as AutoForecast, which train on individual data points, may offer better adaptability but are limited by longer training time required. In this paper, we introduce SimpleTS, a versatile framework for time series forecasting that exhibits high efficiency and accuracy across all types of time series data. When performing an online prediction task, SimpleTS first classifies input time series into one type, and then efficiently selects the most suitable prediction model for this type. To optimize performance, SimpleTS (i) clusters models with similar performance to improve the efficiency of classification; (ii) uses soft labeling and weighted representation learning to achieve higher classification accuracy for different time series types. Extensive experiments on 3 private datasets and 52 public datasets show that SimpleTS outperforms the state-of-the-art toolkits in terms of both training time and prediction accuracy.

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.

Crowdsourcing techniques have been extensively explored in the past decade, including task allocation, quality assessment, and so on. Most of professional crowdsourcing platforms adopt the fixed pricing scheme to offer a fixed price for crowd tasks. It is neither incentive for crowd workers to produce good performance, nor profitable for the requester to gain high utility with low budget. In this article, we study the problem of pricing crowdsourcing tasks with optional bonuses. We propose a dynamic pricing mechanism, named CrowdPricer for incentively delivering bonuses to the crowd workers of completing tasks, in addition to offering a base payment for completing a task. We leverage a deep time sequence model to learn the effect of bonuses on workers’ quality for crowd tasks. CrowdPricer makes decisions on whether to provide bonuses on workers, so as to maximize the requester’s utility in expectation. We present an efficient bonus delivery algorithm under the help of beam search technique, in order to efficiently solve the decision making problem. Extensive experiments using both a real crowdsourcing platform and simulations demonstrate that CrowdPricer yields the higher utility for the requester. It also obtains more correct crowd answers than the state-of-the-art pricing methods.

A knowledge graph (KG) consists of a set of interconnected typed entities and their attributes. Recently, KGs are popularly used as the auxiliary information to enable more accurate, explainable, and diverse user preference recommendations. Specifically, existing KG-based recommendation methods target modeling high-order relations/dependencies from long connectivity user-item interactions hidden in KG. However, most of them ignore the cold-start problems (i.e., user cold-start and item cold-start) of recommendation analytics, which restricts their performance in scenarios when involving new users or new items. Inspired by the success of meta-learning on scarce training samples, we propose a novel meta-learning based framework called MetaKG, which encompasses a collaborative-aware meta learner and a knowledge-aware meta learner, to capturemetausers’ preference and entities’ knowledge for cold-start recommendations. The collaborative-aware meta learner aims to locally aggregate user preferences for each preference learning task. In contrast, the knowledge-aware meta learner is to globally generalize knowledge representation across different user preference learning tasks. Guided by two meta learners, MetaKG can effectively capture the high-order collaborative relations and semantic representations, which could be easily adapted to cold-start scenarios. Besides, we devise a novel adaptive task scheduler which can adaptively select the informative tasks for meta learning in order to prevent the model from being corrupted by noisy tasks. Extensive experiments on various cold-start scenarios using three real datasets demonstrate that our presented MetaKG outperforms all the existing state-of-the-art competitors in terms of effectiveness, efficiency, and scalability.

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

Influential community search aims to find cohesive subgraphs (communities) with considerable influence. It is a fundamental graph management operator that can play a crucial role in biological network analysis, activity organization, and other real-life applications. Existing research on influential community search is mainly focused on deterministic graphs with the assumption that influences between entities are certain. This assumption is invalid in many cases because it ignores the uncertainty which is an inherent property of influence. Against this backdrop, in this paper, we introduce an uncertain influential community model, namely$(k, \eta)$-influential community, based on which the influential community search problem over uncertain graphs is formulated. Furthermore, we propose an online approach by integrating a peeling-pruning strategy that can progressively refine the given uncertain graph to find the$(k, \eta)$-influential communities. To further improve the search performance, two novel indexes, ICU-Index and FICU-Index, are developed to organize the$(k, \eta)$-influential communities at different probabilistic intervals. The indexes decompose the probabilistic interval into multiple subintervals and based on this, the$(k, \eta)$-influential communities are divided into different groups in turn. Compared with ICU-Index, FICU-Index requires considerably less space with the introduction of two optimization strategies. These indexes help obtain results of an influential community search problem more efficiently. Extensive experiments on large real and synthetic datasets demonstrate the efficiency and effectiveness of our proposed algorithms.

Due to the ubiquity of missing data, data imputation has received extensive attention in the past decades. It is a well-recognized problem impacting almost all fields of scientific study. Existing imputation algorithms differ in problem settings, model selection, and data evaluation. There is a lack of systematic comparison study among imputation algorithms. In this paper, we survey this interesting and evolving research topic by broadly reviewing and experimentally comparing the state-of-the-art missing data imputation algorithms. We analyze and categorize 19 imputation algorithms. Extensive experiments over 15 real-world benchmark datasets are conducted under various settings of data types, missing mechanisms, missing rates, dataset/model parameters, as well as the post-imputation prediction task. We shed light on a series of constructive insights on imputation algorithms to tackle imputation problem in real-life scenarios. Moreover, we put forward promising future directions for data imputation problem.

Materialized model query aims to find the most appropriate materialized model as the initial model for model reuse. It is the precondition of model reuse, and has recently attracted much attention. Nonetheless, the existing methods suffer from the need to provide source data, limited range of applications, and inefficiency since they do not construct a suitable metric to measure the target-related knowledge of materialized models. To address this, we present${\sf MMQ}$, a source-data free, general, efficient, and effective materialized model query framework. It uses a Gaussian mixture-based metric called separation degree to rank materialized models. For each materialized model,${\sf MMQ}$first vectorizes the samples in the target dataset into probability vectors by directly applying this model, then utilizes Gaussian distribution to fit for each class of probability vectors, and finally uses separation degree on the Gaussian distributions to measure the target-related knowledge of the materialized model. Moreover, we propose an improved${\sf MMQ}$(${\sf I\text{-}MMQ}$), which significantly reduces the query time while retaining the query performance of${\sf MMQ}$. Extensive experiments on a range of practical model reuse workloads demonstrate the effectiveness and efficiency of${\sf MMQ}$.

Travel time prediction is a critical task in intelligent transportation system and location-based service. Existing studies build models based on the features extracted from trajectories, but few of them consider the sparsity of trajectory data from both temporal and spatial dimensions, as well as the spatial structure and heterogeneity. To address these issues, we propose a novel Multi-scale spatial-temporal model for Travel Time Prediction, abbreviated as MTTPRE. Specifically, the study area is represented as a flexible Voronoi graph according to a variable-sized partition scheme and the missing features on it are recovered via a spatial-temporal context-based method. Subsequently, a geospatial network with POI information is established to represent the spatial structure based on the Voronoi graph. Next, the multi-dimensional traffic condition features and graph-trajectory-POI multilevel features are extracted as spatial-temporal features. Finally, these features are fed into a hierarchical multi-task learning layer to complete the travel time prediction task. Extensive experiments on two real-world datasets show that the MTTPRE outperforms all the competitors with significant improvement and remarkable robustness.

The widespread deployment of smartphones, net-worked in-vehicle devices with geo-positioning capabilities, and vessel tracking technologies renders it feasible to collect the evolving geo-locations of populations of land- and sea-based moving objects. The continuous clustering of such data can enable a variety of real-time services, such as road traffic management and vessel collision risk assessment. However, little attention has so far been given to the quality of moving-object clusters-for example, it is beneficial to smooth short-term fluctuations in clusters to achieve robustness to exceptional data and to improve existing applications. We propose the notion of evolutionary clustering of moving objects, abbreviated ECM, that enhances the quality of moving object clustering by means of temporal smoothing that prevents abrupt changes in clusters across successive timestamps. Employing the notions of snapshot and historical costs, we formalize ECM and formulate ECM as an optimization problem. We prove that ECM can be performed approximately in linear time, thus eliminating iterative processes employed in previous studies. Further, we propose a minimal-group structure and a seed-point shifting strategy to facilitate temporal smoothing. Finally, we present all algorithms underlying ECM along with a set of optimization techniques. Extensive experiments with three real-life datasets offer insights into ECM and show that it outperforms state-of-the-art solutions in terms of both clustering quality and clustering efficiency.

Deploying database services on cloud systems has gained increasing popularity and has become a common practice in the industry. However, the complicated cloud environments make performance issues inevitable, which could violate the service level guarantee if not addressed in a timely manner. Among the various problems, anomalies in SQL queries are the most commonly reported sources that cause performance issues in database applications. These anomalous queries can be divided into High-impact SQLs (H-SQLs) and Root Cause SQLs (R-SQLs), representing the related SQLs that are correlated with the anomalies and the ones that are the root causes of the performance issue, respectively. In the presence of a large number of queries, to pinpoint the R-SQLs is far more difficult than to identify the H-SQLs. To address this challenge, we aim at automatically pinpointing the R-SQLs to resolve performance issues in cloud databases. This paper introduces PinSQL, an autonomous diagnosing system for Alibaba Cloud, which has four modules that are executed sequentially, including data collection and pre-processing, anomaly detection, root cause analysis, and repairing actions. First, the related performance metrics and query logs from monitored cloud database instances are collected and aggregated as the data sources. Then, based on these inputs, efficient anomaly detection is conducted in real-time. Upon the detection of an anomaly, the root cause SQLs are pinpointed through tracking the propagation chain of the involved SQLs. Finally, repairing actions are suggested and then executed on R-SQLs to address the anomalies. Extensive experiments on an Alibaba production system show that PinSQL can achieve an 80% accuracy for pinpointing the top-1 R-SQLs and successfully resolve the database performance issues resultantly.

As a typical most-to-most connected quasi-biclique model, k-biplex is a superset of bicliques, which allows nodes on each side of a fully connected subgraph to lose at most$k$connections. In this paper, we investigate the maximum biplex search problem for the first time. The goal here is to find a k-biplex with the maximum number of edges and we have proved that the problem is NP-hard. It is widely used in fraudulent reviewer group detection, gene expression analysis, social recommendation, and other real-life applications. To solve this problem, a maximum k-biplex search algorithm (MBS) is first presented by integrating two pruning strategies, including degree-based and 2-hop-based pruning. In addition, we define a new dense subgraph over bipartite graphs,$\langle x, y\rangle$-core, and develop a core-based maximum k-biplex search algorithm (MBS-Core) which can significantly reduce the search space with the introduction of a core-based graph reduction technique. In particular, it only needs to search these cores instead of the entire graph to obtain the maximum k-biplex. Moreover, a parallel algorithm and a heuristic algorithm are developed to achieve better query performance on larger-scale bipartite graphs. Extensive experiments have been conducted on real-life and synthetic datasets to verify the efficiency and effectiveness of the proposed algorithms. Our results show that MBS-Core is up to 3 orders of magnitude faster than the existing approaches.

Community search (CS) on graphs returns the largest densely connected vertex subset containing a query vertex, namely k-community, where every vertex's degree in the induced subgraph is not less than$k$. It has significant influence in many real-life applications including event organization and friend recommendation. Many complex networks such as social networks and protein-protein interaction (PPI) networks are often modeled as uncertain graphs. In this paper, we identify and study the problem of reliable community search on uncertain graphs (UCS for short). Given an uncertain graph, a query vertex$q$, a positive integer$k$and a probability threshold θ, the reliable community, viz., (k, θ) -community, of$q$is the largest vertex subset, so that the probability of every vertex to be in$q$'s k-community is not less than θ. We prove that it is a NP-hard problem. We propose two novel pruning strategies to reduce the candidate set to a much smaller size. We develop an efficient index, namely CD-index, with which the pruning process can be done in optimal time. We also present efficient sampling algorithms on top of stratified sampling and lazy sampling to accelerate the search under accuracy guarantees. Extensive experiments using four real-world datasets demonstrate the superior performance of proposed algorithms to the state-of-the-art approaches.

Welfare maximization (WM) aims to select a group of seed nodes to allocate different items for marketing, so that the whole welfare after diffusion over a social network is maximized. It has attracted much attention due to the practical applications such as viral marketing and online advertisements, where the economic incentives are incorporated into users' adoption behaviors. However, existing studies ignore the time impact on the diffusion and consider a single item type. In this paper, we propose an effective time-aware utility-driven independent cascade (TUIC) model, that incorporates the time-aware multi-item propagation, utility-driven item adoption, and mixed item relationships together. We identify and formulate the time-aware welfare maximization problem. We develop a general framework to address the problem for mixed competitive, complementary, and independent items. It derives item allocation with the$(1 -1/e-\epsilon)$approximate social welfare in special cases. Extensive experiments on several real-life social networks demonstrate the effectiveness of TUIC model and the efficiency of the proposed framework, compared to the state of the arts.

Set label-constrained reachability (SLCR) query in edge-labeled graphs is a building block of many graph-based applications. Formally, given two sets$S$and$T$of source and target vertices and a label set (, it returns all reachable vertex pairs (s, t) under the constraint of (, where$s$∊$S$and$t$∊T. There have been abundant index-based approaches to be applied to process the SLCR query. However, distributed approaches are desirable to process large-scale graphs because of the advantages of good scalability and real-time response. Now, there is no efficient distributed approach to the SLCR query. Most index-based approaches face limitations in terms of index construction and query performance when being extended to the distributed environment for processing large-scale graphs. To alleviate these problems, we first build a boundary graph-based index (BoundG) to reduce the time overhead of index construction. Consider the query performance of the BoundG-based approach has no noticeable improvement. We further construct a novel two layers 2-hop index (TL2hop), and a TL2hop-based query algorithm (TLQA) is designed by integrating an early termination strat-egy that reduces the communication overhead and boosts the query performance. Experimental results over eight data graphs demonstrate that the index time of BoundG is comparable to that of the state-of-the-art, and TL2hop significantly outperforms the state-of-the-art technique in terms of query response time (up to 4 orders of magnitude speedup).

Task assignment is a crucial issue in spatial crowd-sourcing. In most existing studies, the results of the task assignment cannot satisfy the workers and tasks at the same time. This is because only one-sided preferences are taken into account. Moreover, tasks are always assigned based on the locations of workers instead of the trajectories. Accordingly, they are not appropriate to the specific applications, such as carpool. Inspired by this, we investigate an interesting problem of task assignment, namely bilateral preference-aware task assignment (BPTA), with the goal of maximizing the overall satisfaction of workers and tasks by assigning tasks to suitable workers based on their routine trajectories. To tackle this problem effectively, we first propose greedy algorithms, namely task preference priority greedy and worker preference priority greedy algorithms, which are task-driven and worker-driven, respectively. Although these algorithms can solve the BPTA problem effectively, they cannot ensure the stability of the task assignment results. In other words, there can be better choices for some workers and tasks. Accordingly, we further explore deferred acceptance algorithms to find a stable matching for workers and tasks by simultaneously considering the preferences of workers and tasks. Moreover, two optimizing strategies, including a parallel strategy and a top-$k$strategy, are introduced to boost the performance in handling the BPTA problem. Extensive experiments on both real and synthetic datasets have validated the efficiency and effectiveness of our proposed algorithms.

Deep learning based trajectory similarity computation holds the potential for improved efficiency and adaptability over traditional similarity computation. However, existing learning-based trajectory similarity learning solutions prioritize spatial similarity over temporal similarity, making them suboptimal for time-aware analyses. To this end, we propose ST2Vec, a representation learning based solution that considers fine-grained spatial and temporal relations between trajectories to enable spatio-temporal similarity computation in road networks. Specifically, ST2Vec encompasses two steps: (i) spatial and temporal modeling that encode spatial and temporal information of trajectories, where a generic temporal modeling module is proposed for the first time; and (ii) spatio-temporal co-attention fusion, where two fusion strategies are designed to enable the generation of unified spatio-temporal embeddings of trajectories. Further, under the guidance of triplet loss, ST2Vec employs curriculum learning in model optimization to improve convergence and effectiveness. An experimental study offers evidence that ST2Vec outperforms state-of-the-art competitors substantially in terms of effectiveness and efficiency, while showing low parameter sensitivity and good model robustness. Moreover, similarity involved case studies including top-k querying and DBSCAN clustering offer further insight into the capabilities of ST2Vec.

Entity alignment (EA) aims at finding equivalent entities in different knowledge graphs (KGs). Embedding-based approaches have dominated the EA task in recent years. Those methods face problems that come from the geometric properties of embedding vectors, including hubness and isolation. To solve these geometric problems, many normalization approaches have been adopted for EA. However, the increasing scale of KGs renders it hard for EA models to adopt the normalization processes, thus limiting their usage in real-world applications. To tackle this challenge, we present ClusterEA, a general framework that is capable of scaling up EA models and enhancing their results by leveraging normalization methods on mini-batches with a high entity equivalent rate. ClusterEA contains three components to align entities between large-scale KGs, including stochastic training, ClusterSampler, and SparseFusion. It first trains a large-scale Siamese GNN for EA in a stochastic fashion to produce entity embeddings. Based on the embeddings, a novel ClusterSampler strategy is proposed for sampling highly overlapped mini-batches. Finally, ClusterEA incorporates SparseFusion, which normalizes local and global similarity and then fuses all similarity matrices to obtain the final similarity matrix. Extensive experiments with real-life datasets on EA benchmarks offer insight into the proposed framework, and suggest that it is capable of outperforming the state-of-the-art scalable EA framework by up to 8 times in terms of [email protected]

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

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

Entity Matching (EM) aims to find data instances from different sources that refer to the same real-world entity. The existing EM techniques can be either costly or tailored for a specific data type. We present ZeroMatcher, a cost-off entity matching system, which supports (i) handling EM tasks with different data types, including relational tables and knowledge graphs; (ii) keeping its EM performance always competitive by enabling the sub-modules to be updated in a lightweight manner, thus reducing development costs; and (iii) performing EM without human annotations to further slash the labor costs. First, ZeroMatcher automatically suggests users a set of appropriate modules for EM according to the data types of the input datasets. Users could specify the modules for the subsequent EM process according to their preferences. Alternatively, users are able to customize the modules of ZeroMatcher. Then, the system proceeds to the EM task, where users can track the entire EM process and monitor the memory usage changes in real-time. When the EM process is completed, ZeroMatcher visualizes the EM results from different aspects to ease the understanding for users. Finally, ZeroMatcher provides EM results evaluation, enabling users to compare the effectiveness among different parameter settings.

Abstract As a fundamental part of indoor scene understanding, the research of indoor room layout estimation has attracted much attention recently. The task is to predict the structure of a room from a single image. In this paper, we illustrate that this task can be well solved even without sophisticated post-processing program, by adopting Feature Pyramid Networks (FPN) to solve this problem with adaptive changes. The proposed model employs two strategies to deliver quality output. First, it can predicts the coarse positions of key points correctly by preserving the order of these key points in the data augmentation stage. Then the coordinate of each corner point is refined by moving each corner point to its nearest image boundary as output. Our method has demonstrated great performance on the benchmark LSUN dataset on both processing efficiency and accuracy. Compared with the state-of-the-art end-to-end method, our method is two times faster at processing speed (32 ms) than its speed (86 ms), with 0.71% lower key point error and 0.2% higher pixel error respectively. Besides, the advanced two-step method is only 0.02% better than our result on key point error. Both the high efficiency and accuracy make our method a good choice for some real-time room layout estimation tasks.

Entity Matching (EM), which aims to identify whether two entity records from two relational tables refer to the same real-world entity, is one of the fundamental problems in data management. Traditional EM assumes that two tables are homogeneous with the aligned schema, while it is common that entity records of different formats (e.g., relational, semi-structured, or textual types) involve in practical scenarios. It is not practical to unify their schemas due to the different formats. To support EM on format-different entity records, Generalized Entity Matching (GEM) has been proposed and gained much attention recently. To do GEM, existing methods typically perform in a supervised learning way, which relies on a large amount of high-quality labeled examples. However, the labeling process is extremely labor-intensive, and frustrates the use of GEM. Low-resource GEM, i.e., GEM that only requires a small number of labeled examples, becomes an urgent need. To this end, this paper, for the first time, focuses on the low-resource GEM and proposes a novel low-resource GEM method, termed as PromptEM. PromptEM has addressed three challenging issues (i.e., designing GEM-specific prompt-tuning, improving pseudo-labels quality, and running efficient self-training) in low-resource GEM. Extensive experimental results on eight real benchmarks demonstrate the superiority of PromptEM in terms of effectiveness and efficiency.

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

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

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.

With the increase of dirty data, data cleaning turns into a crux of data analysis. The accuracy limitation of the existing integrity constraints-based cleaning approaches results from insufficient rules. In this paper, we present a novel hybrid data cleaning framework on top of Markov logic networks (MLNs), termed as${\sf MLNClean}$, which is capable of learning instantiated rules to supplement the insufficient integrity constraints.${\sf MLNClean}$consists of two steps, i.e.,pre-processingandtwo-stage data cleaning. In the pre-processing step,${\sf MLNClean}$first infers a set of probable instantiated rules according to MLNs and then builds a two-layer MLN index structure to generate multiple data versions and facilitate the cleaning process. In the two-stage data cleaning step,${\sf MLNClean}$first presents a concept ofreliability scoreto clean errors within each data version separately, and afterward eliminates the conflict values among different data version using a novel concept offusion score. Considerable experimental results on both real and synthetic scenarios demonstrate the effectiveness of${\sf MLNClean}$in practice.

Data have significant economic or social value in many application fields including science, business, governance, etc. This naturally leads to the emergence of many data markets such as GBDEx and YoueData. As a result, the data trade through data markets has started to receive attentions from both industry and academia. During the data buying and selling, how to price the data is an indispensable problem. However, pricing incomplete data is more challenging, even though incomplete data exist pervasively in a vast lot of real-life scenarios. In this paper, we attempt to explore thepricing problem for queries over incomplete data. We propose a sophisticated pricing mechanism, termed as${\sf iDBPricer}$, which takes a series of essential factors into consideration, including thedata contribution/usage,data completeness, andquery quality. We present two novel price functions, namely, the usage, and completeness-aware price function (UCA pricefor short) and the quality, usage, and completeness-aware price function (QUCA pricefor short). Moreover, we develop efficient algorithms for deriving the query prices. Extensive experiments using both real and benchmark datasets demonstrate${\sf iDBPricer}$is of excellent performance in terms of effectiveness and scalability, compared with the state-of-the-art price functions.

Trajectory clustering has played an essential role in trajectory mining tasks. It serves in a wide range of real-life applications, including transportation, location-based services, behavioral study, and so on. To support trajectory clustering analytics, a plethora of trajectory clustering methods have been proposed, which mainly extend traditional clustering algorithms by using spatio-temporal characteristics of trajectories. However, existing traditional trajectory clustering approaches based on raw trajectory representation highly rely on hand-craft similarity metrics, and can not capture hidden spatial dependencies in trajectory data, which is inefficient and inflexible for clustering analysis. To this end, we propose an end-to-end deep trajectory clustering framework via self-training, termed as E2DTC, inspired by the data-driven capabilities of deep neural networks. E2DTC does not require any additional manual feature extraction operations, and can be easily adapted for trajectory clustering analytics on any trajectory dataset. Extensive experimental evaluations on three real-life datasets show that our framework E2DTC achieves superior accuracy and efficiency, compared with classical clustering methods (i.e., K-Medoids) and state-of-the-art neural-network based approaches (i.e., t2vec).

With the growth of dirty data, data cleaning turns into a crux of data analysis. In this paper, we propose a novel hybrid data cleaning framework, termed as MLNClean, which is capable of learning instantiated rules to supplement the insufficient integrity constraints. MLNClean consists of two steps, i.e., pre-processing and two-stage data cleaning. In the pre-processing step, MLNClean first infers a set of probable instantiated rules according to Markov logic network (MLN) and then builds a two-layer MLN index to generate multiple data versions and facilitate the cleaning process. In the two-stage data cleaning step, MLNClean first presents a concept of reliability score to clean errors within each data version separately, and then, it eliminates the conflict values among different data versions using a novel concept of fusion score. Considerable experimental results on both real and synthetic scenarios demonstrate the effectiveness of MLNClean.

A reverse top-k keyword-based location query returns the influence zone for the query object. Given a specified query object q, the influence zone of q varies for different key-word sets. Users may be interested in identifying the maximum influence zone of the query object. To this end, we study the problem called MaxiZone that finds the keyword set maximizing the influence zone of a specified query object. The MaxiZone problem has many real-life applications, e.g., a business owner would like to identify the maximum influence zone so as to attract as many customers as possible. To address the MaxiZone problem, we propose three algorithms, including a basic algorithm, an index-centric algorithm together with a series of optimizations and a sampling-based algorithm. Extensive empirical study using real-world datasets demonstrates the effectiveness and efficiency of proposed algorithms.

As data markets have started to receive much attention from both industry and academia, how to price the tradable data is an indispensable problem. Pricing incomplete data is more practical and challenging, due to the pervasiveness of incomplete data. In this paper, we explore the pricing problem for queries over incomplete data. We propose a sophisticated pricing mechanism, termed as iDBPricer, which considers a series of essential factors, including the data contribution/usage, data completeness, and query quality. We present two novel price functions, namely, the usage and completeness-aware price function (UCA price for short) and the quality, usage, and completeness-aware price function (QUCA price for short). Moreover, we develop efficient algorithms for deriving the query prices. Extensive experiments using both real and benchmark datasets confirm the superiority of iDBPricer to the state-of-the-art price functions.

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

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

Traffic prediction has drawn increasing attention for its ubiquitous real-life applications in traffic management, urban computing, public safety, and so on. Recently, the availability of massive trajectory data and the success of deep learning motivate a plethora of deep traffic prediction studies. However, the existing neural-network-based approaches tend to ignore the correlations between multiple types of moving objects located in the same spatio-temporal traffic area, which is suboptimal for traffic prediction analytics. In this paper, we propose a multi-source deep traffic prediction framework over spatio-temporal trajectory data, termed as MDTP. The framework includes two phases: spatio-temporal feature modeling and multi-source bridging. We present an enhanced graph convolutional network (GCN) model combined with long short-term memory network (LSTM) to capture the spatial dependencies and temporal dynamics of traffic in the feature modeling phase. In the multi-source bridging phase, we propose two methods, Sum and Concat, to connect the learned features from different trajectory data sources. Extensive experiments on two real-life datasets show that MDTP i) has superior efficiency, compared with classical time-series methods, machine learning methods, and state-of-the-art neural-network-based approaches; ii) offers a significant performance improvement over the single-source traffic prediction approach; and iii) performs traffic predictions in seconds even on tens of millions of trajectory data. we develop MDTP + , a user-friendly interactive system to demonstrate traffic prediction analysis.

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

Data imputation has been extensively explored to solve the missing data problem. The dramatically rising volume of missing data makes the training of imputation models computationally infeasible in real-life scenarios. In this paper, we propose an efficient and effective data imputation system withinfluence functions, named EDIT, which quickly trains a parametric imputation model with representative samples under imputation accuracy guarantees. EDIT mainly consists of two modules, i.e., animputation influence evaluation(IIE) module and arepresentative sample selection(RSS) module. IIE leverages the influence functions to estimate the effect of (in)complete samples on the prediction result of parametric imputation models. RSS builds a minimum set of the high-effect samples to satisfy a user-specified imputation accuracy. Moreover, we introduce a weighted loss function that drives the parametric imputation model to pay more attention on the high-effect samples. Extensive experiments upon ten state-of-the-art imputation methods demonstrate that, EDIT adopts only about 5% samples to speed up the model training by 4x in average with more than 11% accuracy gain.

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.

Graph pattern matching has been extensively investigated on general graphs without time information over decades. Nevertheless, few studies focus on temporal graphs, where a relationship between two vertices takes place at a specific moment and lingers for some time. In this paper, we propose a new notion so-calledtime-respecting flow graph, in which all paths are time-respecting (i.e., a sequence of contacts with non-decreasing time), and one vertex is distinguished as the root, from which other vertices can be reached via a time-respecting path. Based on this, we explore the problem oftime-respecting flow graph pattern matching on temporal graphs. This problem motivates important applications in epidemiology, information diffusion, crime detection, etc. To address it, we present one baseline algorithm as well as two optimized algorithms that utilize several efficient matching strategies and topological sort based technique to boost efficiency. Extensive experimental evaluation using both real and synthetic data sets demonstrates the effectiveness and efficiency of our proposed algorithms. Compared with baseline method, our optimized algorithms could achieve up to three orders of magnitude speedup.

To infer structures in diffusion networks, existing approaches mostly need to know not only the final infection statuses of network nodes, but also the exact times when infections occur. In contrast, in many real-world settings, such as disease propagation, monitoring exact infection times is often infeasible due to a high cost. We investigate the problem of how to learn diffusion network structures based on only the final infection statuses of nodes. Instead of utilizing sequences of timestamps to determine potential parent-child influence relationships between nodes, we propose to find influence relationships with high statistical significance. To this end, we design a probabilistic generative model of the final infection statuses to quantitatively measure the likelihood of potential structures of the objective diffusion network, taking into account network complexity. Based on this model, we can infer an appropriate number of most probable parent nodes for each node in the network. Furthermore, to reduce redundant inference computations, we are able to preclude insignificant candidate parent nodes from being considered during inferencing, if their infections have little correlation with the infections of the corresponding child nodes. Extensive experiments on both synthetic and real-world networks offer evidence that the proposed approach is effective and efficient.

Given a geo-textual dataset O, a set φ of keywords, a query object q ∈ O keyword-based location query returns the influence zoneRof q such that q belongs to the result of a top-k spatial keyword query with query keywords φ and any location inRas arguments. For a query object q, the influence zone of q varies for different keywords φ. Users may be interested in identifying the maximum influence zone of the query object. To this end, in this paper, we study the problem called MaxiZone that finds the keyword set maximizing the influence zone of a specified query object. The MaxiZone problem has many real-life applications, e.g., a business owner would like to identify the maximum influence zone so as to attract as many customers as possible. A straightforward way to tackle the MaxiZone problem is to compute the influence zone for every candidate keyword set. Obviously, this is infeasible if there are a large number of candidate keyword sets. We propose a more efficient index-centric algorithm together with a series of optimizations as well as a sampling-based algorithm, to facilitate the query processing. Moreover, we extend the proposed algorithms to address a variant of MaxiZone problem called τ-MaxiZone problem, which finds top-τ keyword sets having the maximum influence zones. Extensive empirical study using real-world datasets demonstrates the effectiveness and efficiency of our proposed algorithms.

Due to the pervasiveness of incomplete data, incomplete data queries are vital in a large number of real-life scenarios. Current models and approaches for incomplete data queries mainly rely on the machine power. In this paper, we study the problem ofskyline queries over incomplete data with crowdsourcing. We propose a novel query framework, termed as${\sf BayesCrowd}$, which takes into account the data correlation using the Bayesian network. We leverage the typicalc-tablemodel on incomplete data to represent objects. Considering budget and latency constraints, we present a suite of effective task selection strategies. Moreover, we introduce amarginal utilityfunction to measure the benefit of crowdsourcing one task. In particular, the probability computation of each object being an answer object is at least as hard as #SAT problem. To this end, we propose anadaptiveDPLL (i.e., Davis-Putnam-Logemann- Loveland) algorithm to speed up the computation. Extensive experiments using both real and synthetic data sets confirm the superiority of${\sf BayesCrowd}$to the state-of-the-art method, in terms of execution time, monetary cost, and latency minimization.

Previous work on the spatio-temporal index often adopts a simple linear model to predict the future positions of moving objects, which may generate numerous errors for complex road networks and fast moving objects. In this paper, we propose NEIST, a neural-enhanced index to process spatio-temporal queries with enhanced efficiency and accuracy, by intelligently leveraging the movement patterns among moving objects. NEIST applies a Recurrent Neural Network (RNN) model to predict future positions of moving objects based on observed trajectories. To reduce the prediction overhead, a suffix-tree is further built to index trajectories with similar suffixes, and thus similar objects within a given similarity bound are grouped together to share the same prediction result. A prediction result in NEIST represents possible positions of a group of moving objects in the next t time slots. Inside each time slot, traditional linear prediction model is then adopted and a TPR-Tree is built to support spatio-temporal queries. We use Singapore and Porto taxi trajectory datasets to evaluate NEIST. Compared to previous approaches, NEIST achieves a much more efficient query performance and is able to produce about 70 percent more accurate results.

Reconstructing the topology of a diffusion network based on observed diffusion results is an open challenge in data mining. Existing approaches mostly assume that the observed diffusion results are available and consist of not only the final infection statuses of nodes, but also the exact timestamps that pinpoint when infections occur. Nonetheless, the exact infection timestamps are often unavailable in practice, due to a high cost and uncertainties in the monitoring of node infections. In this work, we investigate the problem of how to infer the topology of a diffusion network from only the final infection statuses of nodes. To this end, we propose a new scoring criterion for diffusion network reconstruction, which is able to estimate the likelihood of potential topologies of the objective diffusion network based on infection status results with a relatively low statistical error. As the proposed scoring criterion is decomposable, our problem is transformed into finding for each node in the network a set of most probable parent nodes that maximizes the value of a local score. Furthermore, to eliminate redundant computations during the search of most probable parent nodes, we identify insignificant candidate parent nodes by checking whether their infections have negative or extremely low positive correlations with the infections of a corresponding child node, and exclude them from the search space. Extensive experiments on both synthetic and real-world networks are conducted, and the results verify the effectiveness and efficiency of our approach.

Attributed community search aims to find the community with strong structure and attribute cohesiveness from attributed graphs. However, existing works suffer from two major limitations: (i) it is not easy to set the conditions on query attributes; (ii) the queries support only a single type of attributes. To make up for these deficiencies, in this paper, we study a novel attributed community search called vertex-centric attributed community (VAC) search. Given an attributed graph and a query vertex set, the VAC search returns the community which is densely connected (ensured by the k-truss model) and has the best attribute score. We show that the problem is NP-hard. To answer the VAC search, we develop both exact and approximate algorithms. Specifically, we develop two exact algorithms. One searches the community in a depth-first manner and the other is in a best-first manner. We also propose a set of heuristic strategies to prune the unqualified search space by exploiting the structure and attribute properties. In addition, to further improve the search efficiency, we propose a 2-approximation algorithm. Comprehensive experimental studies on various realworld attributed graphs demonstrate the effectiveness of the proposed model and the efficiency of the developed algorithms.

Due to the pervasiveness of incomplete data, incomplete data queries are vital in a large number of real-life scenarios. Current models and approaches for incomplete data queries mainly rely on the machine power. In this paper, we study the problem of skyline queries over incomplete data with crowdsourcing. We propose a novel query framework, termed as BayesCrowd, on top of Bayesian network and the typical c-table model on incomplete data. Considering budget and latency constraints, we present a suite of effective task selection strategies. In particular, since the probability computation of each object being an answer object is at least as hard as #SAT problem, we propose an adaptive DPLL (i.e., Davis-Putnam-Logemann-Loveland) algorithm to speed up the computation. Extensive experiments using both real and synthetic data sets confirm the superiority of BayesCrowd to the state-of-the-art method.

There is an emerging trend of integrating machine learning (ML) techniques into database systems (DB). Considering that almost all the ML toolkits assume that the input of ML algorithms is a single table even though many real-world datasets are stored as multiple tables due to normalization in DB. Thus, data scientists have to perform joins before learning a ML model. This strategy is called learning after joins, which incurs redundancy avoided by normalization. In the area of ML, the Support Vector Machine (SVM) is one of the most standard classification tools. In this paper, we focus on the factorized SVM with gaussian kernels over normalized data. We present factorized learning approaches for two main SVM optimization methods, i.e., Gradient Descent (GD) and Sequential Minimal Optimization (SMO), by factorizing gaussian kernel function computation. Furthermore, we transform the normalized data into matrices, and boost the efficiency of SVM learning via linear algebra operations. Extensive experiments with nine real normalized data sets demonstrate the efficiency and scalability of our proposed approaches.

The aim of real-time co-movement pattern mining for streaming trajectories is to discover co-moving objects that satisfy specific spatio-temporal constraints in real time. This functionality serves a range of real-world applications, such as traffic monitoring and management. However, little work targets the visualization and interaction with such co-movement detection on streaming trajectories. To this end, we develop CoMing, a real-time co-movement pattern mining system, to handle streaming trajectories. CoMing leverages ICPE, a real-time distributed co-movement pattern detection framework, and thus, it has its capacity of good performance. This demonstration offers hands-on experience with CoMing's visual and user-friendly interface. Moreover, several applications in the traffic domain, including object monitoring and traffic statistics visualization, are also provided to users.

Community search enables personalized community discovery and has wide applications in large real-world graphs. While community search has been extensively studied for undirected graphs, the problem for directed graphs has received attention only recently. However, existing studies suffer from several drawbacks, e.g., the vertices with varied in-degrees and out-degrees cannot be included in a community at the same time. To address the limitations, in this paper, we systematically study the problem of community search over large directed graphs. We start by presenting a novel community model, called D-truss, based on two distinct types of directed triangles, i.e., flow triangle and cycle triangle. The D-truss model brings nice structural and computational properties and has many advantages in comparison with the existing models. With this new model, we then formulate the D-truss community search problem, which is proved to be NP-hard. In view of its hardness, we propose two efficient 2-approximation algorithms, named Global and Local, that run in polynomial time yet with quality guarantee. To further improve the efficiency of the algorithms, we devise an indexing method based on D-truss decomposition. Consequently, the D-truss community search can be solved upon the D-truss index without time-consuming accesses to the original graph. Experimental studies on real-world graphs with ground-truth communities validate the quality of the solutions we obtain and the efficiency of the proposed algorithms.

The G-Skyline (GSky) query is a powerful tool to analyze optimal groups in decision support. Compared with other group skyline queries, it releases users from providing an aggregate function. Besides, it can get much comprehensive results without overlooking some important results containing non-skylines. However, it is hard for the users to make sensible choices when facing so many results the GSky query returns, especially over a large, high-dimensional dataset or with a large group size. In this article, we investigate k representative G-Skyline ( k GSky) queries to obtain a manageable size of optimal groups. The k GSky query can also inherit the advantage of the GSky query; its results are representative and diversified. Next, we propose three exact algorithms with novel techniques including an upper bound pruning, a grouping strategy, a layered optimum strategy, and a hybrid strategy to efficiently process the k GSky query. Consider these exact algorithms have high time complexity and the precise results are not necessary in many applications. We further develop two approximate algorithms to trade off some accuracy for efficiency. Extensive experiments on both real and synthetic datasets demonstrate the efficiency, scalability, and accuracy of the proposed algorithms.

To identify the data examples of rare categories that form small compact clusters in large data sets, existing approaches mostly require enough labeled data examples as a training set to learn a classifier, assuming that the rare-category clusters are spherical or nearly spherical. Nonetheless, a large enough training set is usually difficult to obtain in practice, and rare categories in many real-world applications often form small compact clusters with arbitrary shapes. In this paper, we investigate how to identify all data examples of a rare category with an arbitrary shape based on only one seed (i.e., a labeled rare-category data example). Instead of finding a compact and spherical local region around the seed, we locally explore the data set from the seed by continuously searching and visiting the k-nearest neighbors of each newly visited data example. The local exploration connects the data examples in the objective rare category by the relationship of k-nearest neighbors, and meanwhile, suspected external data examples are filtered out if they are not close enough to any visited data example. Experimental results on both synthetic and real-world data sets are conducted, and the results verify the effectiveness and efficiency of our approach.

Textile pattern design is a challenging task that can be hardly resolved by a single deep neural network, due to the requirements on high resolution, periodic tiling, copyright protection and aesthetic preference of designers. In this paper, we present our NAD system which can automatically produce high-quality textile patterns for printing industry. Our NAD system splits the work into three steps: layout design, image filtering and pattern style transfer. In the first and last step, we employ different neural models to learn the process of artwork creation by human designers. Specifically, a reinforcement learning model is first developed for layout adjustment, followed by a CNN-based model for style transfer. We have employed our NAD system in an online production system with real customers and the results are very impressive and promising. The NAD system not only frees human designers from the labor intensive design process, but also results in a 2%-5% daily purchase rate.

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.

The range-based skyline (r-skyline) query on road networks retrieves the skyline objects of taking each point within a road region as a query point, in terms of objects' spatial and non-spatial attributes. In this paper, we systematically carry out the study of why-not questions on the r-skyline query in the road network (abbreviated as the why-not RSQ problem). We present three modification strategies, including modifying the query range, modifying the why-not point, and modifying both of them, for the why-not RSQ problem. In particular, a suite of newly presented effective concepts/techniques are leveraged, such as the concepts of skyline scope and skyline dominance region, non-spatial attribute modification pruning, and G-tree index. Extensive experiments using both real and synthetic data sets demonstrate the performance of our proposed algorithms.

Probabilistic queries usually suffer from the noisy query result sets, due to data uncertainty. In this paper, we propose an efficient optimization framework, termed as QueryClean, for both probabilistic skyline computation and probabilistic similarity search. Its goal is to optimize query quality by selecting a group of uncertain objects to clean under limited resource available, where an entropy based quality function is leveraged. We develop an efficient index to organize the possible result sets of probabilistic queries, which is able to help avoid multiple probabilistic query evaluations over a large number of possible worlds for quality computation. Moreover, using two newly presented heuristics, we present exact and approximate algorithms for the optimization problem. Extensive experiments on both real and synthetic data sets demonstrate the efficiency and scalability of QueryClean.

DBSCAN is one of important density-based clustering methods, which has a wide range of applications in machine learning and data mining, to name but a few. However, the rapid growing volume and variety of data nowadays challenges traditional DBSCAN, and thus, distributed DBSCAN in metric spaces is required. In this paper, we propose DBSCAN-MS, a distributed density-based clustering in metric spaces. To ensure load balancing, we present a k-d tree based partitioning approach. It utilizes pivots to map the data in metric spaces to vector spaces, and employs k-d tree partitioning technique to equally divide the data. To avoid unnecessary computation and communication cost, we propose a framework that divides data into partitions, find out local DBSCAN result, and merge local result based on a merging graph. In addition, the pivot filtering and the sliding window techniques are also used in the framework for pruning. Extensive experiments with both real and synthetic datasets demonstrate the efficiency and scalability of our proposed DBSCAN-MS.

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

With the widespread deployment of mobile devices with positioning capabilities, increasingly massive volumes of trajectory data are being collected that capture the movements of people and vehicles. This data enables co-movement pattern detection, which is important in applications such as trajectory compression and future-movement prediction. Existing co-movement pattern detection studies generally consider historical data and thus propose offline algorithms. However, applications such as future movement prediction need real-time processing over streaming trajectories. Thus, we investigate real-time distributed co-movement pattern detection over streaming trajectories. Existing off-line methods assume that all data is available when the processing starts. Nevertheless, in a streaming setting, unbounded data arrives in real time, making pattern detection challenging. To this end, we propose a framework based on Apache Flink, which is designed for efficient distributed streaming data processing. The framework encompasses two phases: clustering and pattern enumeration. To accelerate the clustering, we use a range join based on two-layer indexing, and provide techniques that eliminate unnecessary verifications. To perform pattern enumeration efficiently, we present two methods FBA and VBA that utilize id-based partitioning. When coupled with bit compression and candidate-based enumeration techniques, we reduce the enumeration cost from exponential to linear. Extensive experiments offer insight into the efficiency of the proposed framework and its constituent techniques compared with existing methods.

Data cleaning is a prerequisite to subsequent data analysis, and is know to often be time-consuming and labor-intensive. We present IHCS, a hybrid data cleaning system that integrates error detection and repair to contend effectively with multiple error types. In a preprocessing step that precedes the data cleaning, IHCS formats an input dataset to be cleaned, and transforms applicable data quality rules into a unified format. Then, an MLN index structure is formed according to the unified rules, enabling IHCS to handle multiple error types simultaneously. During the cleaning, IHCS first tackles abnormalities through an abnormal group process, and then, it generates multiple data versions based on the MLN index. Finally, IHCS eliminates conflicting values across the multiple versions, and derives the final unified clean data. A visual interface enables cleaning process monitoring and cleaning result analysis.

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

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

This paper explores the Time-Aware Boolean Spatial Keyword Query (TABSKQ) that finds the geo-tagged objects satisfying user's spatial, textual, and temporal constraints. Towards this, we propose an efficient index structure so-called the TA-tree and its corresponding algorithms, which can efficiently prune the search space using both spatio-temporal and textual information. Extensive experiments with real datasets offer insight into the performance of our proposed index and algorithms.

Ridesharing refers to a transportation scenario where travellers with similar itineraries and time schedules share a vehicle for a trip and split the travel cost, which may include fuel, tolls, and parking fees. Ridesharing is popular among travellers because it can reduce their travel costs, and it also holds the potential to reduce travel time, congestion, air pollution, and overall fuel consumption. However, existing ridesharing systems often offer each traveller only one choice that aims to minimize system-wide vehicle travel distance or time. We propose a solution that offers more options. Specifically, we do this by considering both pick-up time and price, so that travellers are able to choose the vehicle that matches their preferences best. In order to identify quickly vehicles that satisfy incoming ridesharing requests, we propose two efficient matching algorithms that follow the single-side and dual-side search paradigms, respectively. To further accelerate the matching, indexes on the road network and vehicles are developed, based on which several pruning heuristics are designed. Extensive experiments on a large Shanghai taxi dataset offer insights into the performance of our proposed techniques and compare with a baseline that extends the state-of-the art method.

A top-k geo-social keyword (TkGSK) query retrieves the objects by considering spatial, social, and textual constraints. After a user issues an initial TkGSK query and gets back its result, however, the user may find that some expected objects are missing and hence may wonder why. In this paper, we explore the why-not top-k geo-social keyword (WNGSK) query in road networks, due to its importance in decision making. We propose techniques which not only adapt user's query keywords but also recommend new social links, so that expected, but missing objects, are included in the result. We first present a nontrivial basic algorithm having some optimizations. To improve efficiency, we develop a new index so-called PIM-tree, and based on it, we present WNGSK query algorithm with several pruning strategies. Extensive experimental results offer insight into the effectiveness and efficiency of our proposed index and algorithms.

Massive trajectory data is being collected and used widely in many applications such as transportation, location-based services, and urban computing. As a result, abundant methods and systems have been proposed for managing and processing trajectory data. However, it remains difficult for users to interact well with data management and processing, due to the lack of efficient data processing methods and effective visualization techniques for big trajectory data. In this demonstration, we present a new framework, VIPTRA, to process big trajectory data visually and interactively. VIPTRA builds upon UlTraMan, a distributed in-memory system for big trajectory data, and thus, it takes advantage of its capability of high performance. The demonstration shows the efficiency of data processing and user-friendly visualization and interaction techniques provided in VIPTRA, via several scenarios of visual analysis and trajectory editing tasks.

Ridesharing is popular among travellers because it can reduce their travel costs, and it also holds the potential to reduce travel time, congestion, air pollution, and overall fuel consumption. Existing ridesharing systems (e.g., lyft, uberPOOL) often offer each traveler only one choice that aims to minimize system-wide vehicle travel distance or time. In this demonstration, we present a price-and-time-aware ridesharing system, termed as PTRider, which provides more options. It considers both pick-up time and price, so that travellers are able to choose the vehicle matching their preferences best. To answer the ridesharing request in real time, PTRider builds indexes on the road network and vehicles separately, and utilizes corresponding efficient matching methods. A real-life dataset that contains 432,327 trips extracted from 17,000 Shanghai taxis for one day (May 29, 2009) is used to demonstrate that PTRider can return various options for every ridesharing request in real time.

Massive trajectory data is being generated by GPS-equipped devices, such as cars and mobile phones, which is used increasingly in transportation, location-based services, and urban computing. As a result, a variety of methods have been proposed for trajectory data management and analytics. However, traditional systems and methods are usually designed for very specific data management or analytics needs, which forces users to stitch together heterogeneous systems to analyze trajectory data in an inefficient manner. Targeting the overall data pipeline of big trajectory data management and analytics, we present a unified platform, termed as UlTraMan. In order to achieve scalability, efficiency, persistence , and flexibility , (i) we extend Apache Spark with respect to both data storage and computing by seamlessly integrating a key-value store, and (ii) we enhance the MapReduce paradigm to allow flexible optimizations based on random data access. We study the resulting system's flexibility using case studies on data retrieval, aggregation analyses, and pattern mining. Extensive experiments on real and synthetic trajectory data are reported to offer insight into the scalability and performance of UlTraMan.

The range-based skyline (r-skyline) query on road networks retrieves the skyline objects for each of the query points that are within a road region, considering the objects' spatial and non-spatial attributes. However, reasoning about missing query results, specified by why-not questions, has not till recently received the attention it is worth of. In this paper, we systematically carry out the study of why-not questions on the r-skyline query in the road network environment (abbrev. as the why-not RSQ problem). We present three modification strategies, including modifying the query range, modifying the why-not point, and modifying both of them, for supporting the why-not RSQ problem. We also propose three efficient algorithms to tackle the why-not RSQ problem, where several newly presented effective concepts/techniques are leveraged, such as the concepts of skyline scope and skyline dominance region, non-spatial attribute modification pruning, and G-tree index. Extensive experimental evaluation using both real and synthetic data sets demonstrates the performance of our proposed algorithms.

Probabilistic queries have been extensively explored to provide answers with confidence, in order to support the real-life applications struggling with uncertain data, such as sensor networks and data integration. However, the uncertainty of data may propagate, and thus, the results returned by probabilistic queries contain much noise, which degrades query quality significantly. In this paper, we propose an efficient optimization framework, termed as QueryClean, for both probabilistic skyline computation and probabilistic similarity search. The goal of QueryClean is to optimize query quality via selecting a group of uncertain objects to clean under limited resource available, where a joint-entropy based quality function is leveraged. We develop an efficient structure called ASI to index the possible result sets of probabilistic queries, which helps to avoid many types of probabilistic query evaluations over a large number of the possible worlds for quality computation. Moreover, we present exact and approximate algorithms for the optimization problem, using two newly presented heuristics. Considerable experimental results on both real and synthetic data sets demonstrate the efficiency and scalability of our proposed framework QueryClean.

Community discovery plays an essential role in the analysis of the structural features of complex networks. Since online networks grow increasingly large and complex over time, the methods traditionally used for community discovery cannot efficiently handle large-scale network data. This introduces the important problem of how to effectively and efficiently discover large communities from complex networks. In this study, we propose a fast parallel community discovery model called picaso (a parallel community discovery algorithm based on approximate optimization), which integrates two new techniques: (1) Mountain model, which works by utilizing graph theory to approximate the selection of nodes needed for merging, and (2) Landslide algorithm, which is used to update the modularity increment based on the approximated optimization. In addition, the GraphX distribution computing framework is employed in order to achieve parallel community detection over complex networks. In the proposed model, clustering on modularity is used to initialize the Mountain model as well as to compute the weight of each edge in the networks. The relationships among the communities are then simplified by applying the Landslide algorithm, which allows us to obtain the community structures of the complex networks. Extensive experiments were conducted on real and synthetic complex network datasets, and the results demonstrate that the proposed algorithm can outperform the state of the art methods, in effectiveness and efficiency, when working to solve the problem of community detection. Moreover, we demonstratively prove that overall time performance approximates to four times faster than similar approaches. Effectively our results suggest a new paradigm for large-scale community discovery of complex networks.

The spatial keyword query takes as inputs a query location and a set of query keywords and returns the answer objects by considering both their spatial distances to the query location and textual similarity with the query keywords. However, temporal information plays an important role in the spatial keyword query (where there is, to our knowledge, no prior work considering temporal information of the objects), since objects are not always valid. For instance, visitors may plan their trips according to the opening hours of attractions. Moreover, in real-life applications, objects are located on a predefined road network, and the spatial proximity of two objects is measured by the shortest path distance or travelling time between them. In this article, we study the problem oftime-aware spatial keyword(TSK)query, which assumes that objects are located on the road network, and finds thekobjects satisfying users’ spatio-temporal description and textual constraint. We first present the pruning strategy and algorithm based on an existing index. Then, we design an efficient index structure calledTG indexand propose several algorithms using the TG index that can prune the search space with both spatio-temporal and textual information simultaneously. Further, we show that the TG index technique can also be applied to improve the performance of time-travel text search and spatial keyword query. Extensive experiments using both real and synthetic datasets demonstrate the effectiveness and efficiency of the presented index and algorithms.

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

We develop IS2R, an efficient interactive system for refining reverse top-k queries, to eliminate unexpected query results including (i) the absence of expected objects, (ii) the presence of unexpected objects, and (iii) the empty query result. The IS2R returns the refinement suggestions with the minimal costs based on penalty models. In this demonstration (available at https://youtu.be/GnSm4T9Uslk), we show different scenarios on how IS2R can be used to refine the original reverse top-k query, and verify its effectiveness and efficiency.

Identifying prospective customers is an important aspect of marketing research. In this paper, we provide support for a new type of query, the Reverse Top-k Geo-Social Keyword (RkGSK) query. This query takes into account spatial, textual, and social information, and finds prospective customers for geotagged objects. As an example, a restaurant manager might apply the query to find prospective customers. To address this, we propose a hybrid index, the GIM-tree, which indexes locations, keywords, and social information of geo-tagged users and objects, and then, using the GIM-tree, we present efficient RkGSK query processing algorithms that exploit several pruning strategies. The effectiveness of RkGSK retrieval is characterized via a case study, and extensive experiments using real datasets offer insight into the efficiency of the proposed index and algorithms.

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

Spatial queries including similarity search and similarity joins are useful in many areas, such as multimedia retrieval, data integration, and so on. However, they are not supported well by commercial DBMSs. This may be due to the complex data types involved and the needs for flexible similarity criteria seen in real applications. In this paper, we propose a versatile and efficient disk-based index for metric data, the Space-fillingcurve and Pivot-based B+-tree (SPB-tree). This index leverages the B+-tree, and uses space-filling curve to cluster data into compact regions, thus achieving storage efficiency. It utilizes a small set of so-called pivots to reduce significantly the number of distance computations when using the index. Further, it makes use of a separate random access file to support abroad range of data. By design, it is easyto integrate the SPB-tree into an existing DBMS. We present efficient algorithms for processing similarity search and similarity joins, as well as corresponding cost models based on SPB-trees. Extensive experiments using both real and synthetic data show that, compared with state-of-the-art competitors, the SPB-tree has much lower construction cost, smallerstorage size, and supports more efficient similarity search and similarity joins with high accuracy cost models.

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

With advances in geo-positioning technologies and mobile internet, location-based services have attracted much attention, and spatial keyword queries are catching on fast. However, as far as we aware, no prior work considers the temporal information of geotagged objects. Temporal information is important in the spatial keyword query because many objects are not always valid. For example, visitors may plan their trips according to the opening time of attractions. In this paper, we identify and solve a novel problem, i.e., the time-aware Boolean spatial keyword query (TABSKQ), which returns the k objects that satisfy users' spatio-temporal description and textual constraint. We first present pruning strategies and algorithm based on the CIR+-tree (i.e., the CIR-tree with temporal information). Then, we propose an efficient index structure, called the TA-tree, and its corresponding algorithms, which can prune the search space using both spatio-temporal and textual information. Furthermore, we study an interesting TABSKQ variant, i.e., Joint TABSKQ (JTABSKQ), which aims to process a set of TABSKQs jointly, and extend our techniques to tackle it. Extensive experiments with real datasets offer insight into the performance of our proposed indices and algorithms.

An all-k-nearest-neighbor (AkNN) query finds from a given object set O, k nearest neighbors for each object in a specified query set Q. This operation is common in many applications such as GIS, data mining, and image analysis. Although it has received much attention in the Euclidean space, there is little prior work on the metric space. In this paper, we study the problem of AkNN retrieval in metric spaces, termed metric AkNN (MAkNN) search, and propose efficient algorithms for supporting MAkNN queries with arbitrary k value. Our methods utilize dynamic disk-based metric indexes, employ a series of pruning rules, take advantage of grouping, reuse, pre-processing and progressive pruning techniques, require no detailed representations of objects, and can be applied as long as the distance metric satisfies the triangle inequality. Extensive experiments using both real and synthetic data sets verify the efficiency of our proposed algorithms, compared with state-of-the-art Euclidean AkNN and MAkNN algorithms.

Metric probabilistic range queries (MPRQ) have received substantial attention due to their utility in multimedia and text retrieval, decision making, etc. Existing MPRQ studies generally aim to improve query efficiency and resource usage. In contrast, we define and offer solutions to why-not questions on MPRQ. Given an original metric probabilistic range query and a why-not set W of uncertain objects that are absent from the query result, a why-not question on MPRQ explains why the uncertain objects in W do not appear in the query result, and provides refinements of the original query and/or W with the minimal penalty, so that the uncertain objects in W appear in the result of the refined query. Specifically, we propose a framework that consists of three efficient solutions, one that modifies the original query, one that modifies the why-not set, and one that modifies both the original query and the why-not set. Extensive experiments using both real and synthetic data sets offer insights into the properties of the proposed algorithms, and show that they are effective and efficient.

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

As location-based services (LBSs) become popular, location-dependent queries have raised serious privacy concerns since they may disclose sensitive information in query processing. Among typical queries supported by LBSs, shortest path queries may reveal information about not only current locations of the clients, but also their potential destinations and travel plans. Unfortunately, existing methods for private shortest path computation suffer from issues of weak privacy property, low performance or poor scalability. In this paper, we aim at a strong privacy guarantee, where the adversary cannot infer almost any information about the queries, with better performance and scalability. To achieve this goal, we introduce a general system model based on the concept of Oblivious Storage (OS), which can deal with queries requiring strong privacy properties. Furthermore, we propose a new oblivious shuffle algorithm to optimize an existing OS scheme. By making trade-offs between query performance, scalability and privacy properties, we design different schemes for private shortest path computation. Eventually, we comprehensively evaluate our schemes upon real road networks in a practical environment and show their efficiency.

The incomplete data is universal in many real-life applications due to data integration, the limitation of devices, etc. In this demonstration, we present S i 2 p , a restaurant recommendation System with Preference queries on Incomplete Information. S i 2 p is capable of friendly recommending desirable restaurants based on preference queries that take the incomplete ratings information into consideration. It adopts the browser-server model, and incorporates three functionality modules including friendly and convenient query submission , flexible and useful result explanation , timely and incremental dataset interaction. S i 2 p provides the server side based on an extended PostgreSQL database that integrates two types of preference queries, namely, skyline and top- k dominating queries over incomplete data. It also offers the browser-based interface for the users to interact with the system. Using a real restaurant dataset from TripAdvisor, we demonstrate S i 2 p can recommend and explore the restaurants in a friendly way.

An all-k-nearest-neighbor (AkNN) query finds from a given object set O, k nearest neighbors for each object in a specified query set Q. This operation is common in many applications such as GIS, data mining, and image analysis. Although it has received much attention in the Euclidean space, there is little prior work on the metric space. In this paper, we study the problem of AkNN retrieval in metric spaces, termed metric AkNN(MAkNN) search, and propose efficient algorithms for supporting MAkNN queries with arbitrary k value. Our methods utilize dynamic disk-based metric indexes (e.g., M-tree), employ a series of pruning rules, take advantage of grouping, reuse, pre-processing, and progressive pruning techniques, require no detailed representations of objects, and can be applied as long as the distance metric satisfies the triangle inequality. In addition, we extend our approaches to tackle metric self-AkNN (MSAkNN) search, a natural variation of MAkNN queries, where the query set Q is identical to the object set O. Extensive experiments using both real and synthetic data sets demonstrate, compared with state-of-the-art euclidean AkNN, MAkNN, and MSAkNN algorithms, the performance of our proposed algorithms and the effectiveness of our presented techniques.

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

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

The goal in similarity search is to find objects similar to a specified query object given a certain similarity criterion. Although useful in many areas, such as multimedia retrieval, pattern recognition, and computational biology, to name but a few, similarity search is not yet supported well by commercial DBMS. This may be due to the complex data types involved and the needs for flexible similarity criteria seen in real applications. We propose an efficient disk-based metric access method, the Space-filling curve and Pivot-based B+-tree (SPB-tree), to support a wide range of data types and similarity metrics. The SPB-tree uses a small set of so-called pivots to reduce significantly the number of distance computations, uses a space-filling curve to cluster the data into compact regions, thus improving storage efficiency, and utilizes a B+-tree with minimum bounding box information as the underlying index. The SPB-tree also employs a separate random access file to efficiently manage a large and complex data. By design, it is easy to integrate the SPB-tree into an existing DBMS. We present efficient similarity search algorithms and corresponding cost models based on the SPB-tree. Extensive experiments using real and synthetic data show that the SPB-tree has much lower construction cost, smaller storage size, and can support more efficient similarity queries with high accuracy cost models than is the case for competing techniques. Moreover, the SPB-tree scales sublinearly with growing dataset size.

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

State-of-the-art classical influence maximization (IM) techniques are "competition-unaware" as they assume that a group (company) finds seeds (users) in a network independent of other groups who are also simultaneously interested in finding such seeds in the same network. However, in reality several groups often compete for the same market (e.g., Samsung, HTC, and Apple for the smart phone market) and hence may attempt to select seeds in the same network. This has led to increasing body of research in devising IM techniques for competitive networks. Despite the considerable progress made by these efforts toward finding seeds in a more realistic settings, unfortunately, they still make several unrealistic assumptions (e.g., a new company being aware of a rival's strategy, alternate seed selection, etc.) making their deployment impractical in real-world networks. In this paper, we propose a novel framework based on game theory to provide a more realistic solution to the IM problem in competitive networks by jettisoning these unrealistic assumptions. Specifically, we seek to find the "best" IM strategy (an algorithm or a mixture of algorithms) a group should adopt in the presence of rivals so that it can maximize its influence. As each group adopts some strategy, we model the problem as a game with each group as competitors and the expected influences under the strategies as payoffs. We propose a novel algorithm called GetReal to find each group's best solution by leveraging the competition between different groups. Specifically, it seeks to find whether there exist a Nash Equilibrium (NE) in a game, which guarantees that there exist an "optimal" strategy for each group. Our experimental study on real-world networks demonstrates the superiority of our solution in a more realistic environment.

Massive amounts of geo-tagged and textually annotated images are provided by online photo services such as Flickr and Zommr. However, most existing image retrieval engines only consider text annotations. We present I2RS, a system that allows users to view geo-textual images on Google Maps, find hot topics within a specific geographic region and time period, retrieve images similar to a query image, and receive recommended images that they might be interested in. I2RS is a distributed geo-textual image retrieval and recommendation system that employs SPB-trees to index geo-textual images, and that utilizes metric similarity queries, including top- m spatio-temporal range and k nearest neighbor queries, to support geo-textual image retrieval and recommendation. The system adopts the browser-server model, whereas the server is deployed in a distributed environment that enables efficiency and scalability to huge amounts of data and requests. A rich set of 100 million geo-textual images crawled from Flickr is used to demonstrate that, I2RS can return high-quality answers in an interactive way and support efficient updates for high image arrival rates.

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

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

Mining arbitrary shaped clusters in large data sets is an open challenge in data mining. Various approaches to this problem have been proposed with high time complexity. To save computational cost, some algorithms try to shrink a data set size to a smaller amount of representative data examples. However, their user-defined shrinking ratios may significantly affect the clustering performance. In this paper, we present CLASP an effective and efficient algorithm for mining arbitrary shaped clusters. It automatically shrinks the size of a data set while effectively preserving the shape information of clusters in the data set with representative data examples. Then, it adjusts the positions of these representative data examples to enhance their intrinsic relationship and make the cluster structures more clear and distinct for clustering. Finally, it performs agglomerative clustering to identify the cluster structures with the help of a mutual k-nearest neighbors-based similarity metric called Pk. Extensive experiments on both synthetic and real data sets are conducted, and the results verify the effectiveness and efficiency of our approach.

In this paper, for the first time, we study the problem of mapping keyword queries to questions on community-based question answering (CQA) sites. Mapping general web queries to questions enables search engines not only to discover explicit and specific information needs (questions) behind keywords queries, but also to find high quality information (answers) for answering keyword queries. In order to map queries to questions, we propose a ranking algorithm containing three steps: Candidate Question Selection, Candidate Question Ranking, and Candidate Question Grouping. Preliminary experimental results using 60 queries from search logs of a commercial engine show that the presented approach can efficiently find the questions which capture user's information needs explicitly.

Commodity information such as prices and public reviews is always the concern of consumers. Helping them conveniently acquire these information as an instant reference is often of practical significance for their purchase activities. Nowadays, Web 2.0, linked data clouds, and the pervasiveness of smart hand held devices have created opportunities for this demand, i.e., users could just snap a photo of any commodity that is of interest at anytime and anywhere, and retrieve the relevant information via their Internet-linked mobile devices. Nonetheless, compared with the traditional keyword-based information retrieval, extracting the hidden information related to the commodities in photos is a much more complicated and challenging task, involving techniques such as pattern recognition, knowledge base construction, semantic comprehension, and statistic deduction. In this paper, we propose a framework to address this issue by leveraging on various techniques, and evaluate the effectiveness and efficiency of this framework with experiments on a prototype.

Browse with either web directories or social bookmarks is an important complementation to search by keywords in web information retrieval. To improve users' browse experiences and facilitate the web directory construction, in this paper, we propose a novel browse system called Social Web Directory (SWD for short) by integrating web directories and social bookmarks. In SWD, (1) web pages are automatically categorized to a hierarchical structure to be retrieved efficiently, and (2) the popular web pages, hottest tags, and expert users in each category are ranked to help users find information more conveniently. Extensive experimental results demonstrate the effectiveness of our SWD system.

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

In recent years, personalized web search (PWS) has demonstrated effectiveness in improving the quality of search service on the Internet. Unfortunately, the need for collecting private information in PWS has become a major barrier for its wide proliferation. We study privacy protection in PWS engines which capture personalities in user profiles. We propose a PWS framework called UPS that can generalize profiles in for each query according to user-specified privacy requirements. Two predictive metrics are proposed to evaluate the privacy breach risk and the query utility for hierarchical user profile. We develop two simple but effective generalization algorithms for user profiles allowing for query-level customization using our proposed metrics. We also provide an online prediction mechanism based on query utility for deciding whether to personalize a query in UPS. Extensive experiments demonstrate the efficiency and effectiveness of our framework.

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

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

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

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

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

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

Given two sets DAand DBof multidimensional objects, a spatial region R, and a critical distance dc, an optimal-nearest- neighbor (ONN) query retrieves outside R, the object in DBwith maximum optimality. Let CAR (Sp,p) be the cardinality of the subset Sp of objects in DAwhich locate within R and are enclosed by the vicinity circle centered at p with radius dc. Then, an objectois said to be better than another one o' if (i) CAR (So,o) = CAR (So,o'), or (ii) when CAR (So,o) = CAR (So',o') the sum of the weighted distance from each object in Sotoois smaller than the sum of the weighted distance between every object in So' and o'. This type of queries is quite useful in many decision making applications. In this paper, we formalize the ONN query, develop the optimality metric, and propose several algorithms for finding optimal nearest neighbors efficiently. Our techniques assume that both DAand DBare indexed by R-trees. Extensive experiments demonstrate the efficiency and scalability of our proposed algorithms using both real and synthetic datasets.

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