Large Language Models (LLMs) have shown strong capabilities in open-domain question answering (QA), but deploying them in real-world online systems introduces critical challenges. These include: (1) handling both simple and complex queries with appropriate levels of reasoning, (2) minimizing latency without compromising answer quality, and (3) maintaining answer consistency under evolving and noisy retrieval contexts. To address these challenges, we propose Retain-to-Refine (ℜ2ℜ), an adaptive agent-based QA framework designed for practical deployment. ℜ2ℜ integrates a Query Critic Agent (QCA) to assess query difficulty and route it accordingly: simple queries are answered directly using fast, prompt-based LLM calls, while complex queries are handled by a Memory Augmented Agent (MAA). MAA performs iterative reasoning guided by a unique long-short memory mechanism. Long-term memory retains and consolidates stable, core facts to ground the reasoning process, while short-term memory identifies transient information gaps to formulate highly focused subsequent queries. To ensure evidence quality, a Supervised Retrospection module validates and filters retrieved documents at each step. This agent-based design enables ℜ2ℜ to dynamically allocate computation based on question complexity, reducing unnecessary overhead while preserving high-quality answers when multi-step reasoning or external knowledge is required. Extensive evaluations across various settings and datasets demonstrate that the efficiency of R2R across diverse question types. In online settings, ℜ2ℜ delivers substantial gains in both response quality and efficiency, making it well-suited for large-scale industrial deployment in real-time QA services.

Large Language Model-based Multi-Agent Systems (LLM-MAS) have attracted significant attention due to their advantages in handling complex tasks. Current research primarily focuses on task-specific agent design, cooperation mechanisms, and pipeline optimization. However, the robustness of LLM-MAS remains underexplored. Internal conflicts and insufficient information sharing among agents can expose the system to global-level failures, especially under abnormal conditions or adversarial attacks. To address these challenges, we propose a generalizable and computationally efficient protection mechanism, RollMAS. First, we design the action negotiation algorithm that mitigates risks arising from agent discrepancies by enabling multiple local policies to converge through signal synchronization in the vector space. Second, the sharing redundancy enhancement algorithm optimizes MAS robustness by maximizing an approximate natural eigenvalue of the corresponding adjacency matrix, facilitating resilient and efficient information sharing with controlled communication overhead. Extensive experiments on traffic control and question answering tasks, spanning 7 datasets and 13 baselines, demonstrate that our methods substantially enhance the robustness and effectiveness of LLM-MAS.

High-level automation is increasingly critical in AI, driven by rapid advances in large language models (LLMs) and AI agents. However, LLMs, despite their general reasoning power, struggle significantly in specialized, data-sensitive tasks such as designing Graph Neural Networks (GNNs). This difficulty arises from (1) the inherent knowledge gaps in modeling the intricate, varying relationships between graph properties and suitable architectures and (2) the external noise from misleading descriptive inputs, often resulting in generic or even misleading model suggestions. Achieving proficiency in designing data-aware models—defined as the meta-level capability to systematically accumulate, interpret, and apply data-specific design knowledge—remains challenging for existing automated approaches, due to their inefficient construction and application of meta-knowledge. To achieve meta-level proficiency, we propose DesiGNN, a knowledge-centered framework that systematically converts past model design experience into structured, fine-grained knowledge priors well-suited for meta-learning with LLMs. To account for the inherent variability and external noise, DesiGNN aligns empirical property filtering from extensive benchmarks with adaptive elicitation of literature insights via LLMs. By constructing a solid meta-knowledge between unseen graph understanding and known effective architecture patterns, DesiGNN can deliver top-5.77% initial model proposals for unseen datasets within seconds and achieve consistently superior performance with minimal search cost compared to baselines.

Generative inference with Large Language Models (LLMs) is the cornerstone of web-scale AI search, where queries are answered using vast, heterogeneous documents retrieved via Retrieval-Augmented Generation (RAG). This paradigm is critically bottlenecked by the cost of self-attention mechanism on long context. The sheer diversity of retrieved web content (multi-sourced, multi-lingual, multi-faceted) makes simple Key-Value (KV) cache optimizations with pre-fixed subsets ineffective, demanding a dynamic, content-aware approach. This challenge, however, introduces a classic chicken-and-egg problem: the model cannot foresee the necessary KV entries for attention without first inferring on the content, yet doing so on the full context is prohibitively expensive. This paper introduces P&F, a unified framework that resolves this dilemma through a core ''probe-and-fetch'' mechanism, which ingeniously integrates with speculative decoding -- an acceleration approach already adopted in web-scale AI search. The probe step repurposes the speculative draft model: while generating candidate tokens, it simultaneously probes the context to predict the most salient KV entries the large model will need for attention. The fetch step immediately acts on this prediction, asynchronously fetching these sparse entries from memory. This synergistic design piggybacks the probing step onto the drafting process, allowing the expensive gathering of a sparse KV cache to be fully masked. Crucially, this co-design breaks the sequential dependency bottleneck that cripples naive integrations of speculative decoding and prefetching due to synchronization issues. Extensive experiments show P&F significantly outperforms state-of-the-art methods in throughput and scalability, offering a practical, drop-in solution. Extensive offline evaluations across various settings and datasets demonstrate that P&F yields superior throughput and scalability compared to advanced baselines, while maintaining model quality across diverse models and scales. In online settings, P&F delivers substantial gains in throughput improvements while preserving response quality, making it well-suited for large-scale industrial deployment in real-time AI Search services.

High-quality annotated datasets are crucial for advancing machine learning in medical image analysis. However, a critical gap exists: most datasets either offer a single, clean ground truth, which hides real-world expert disagreement, or they provide multiple annotations without a separate gold standard for objective evaluation. To bridge this gap, we introduce CytoCrowd, a new public benchmark for cytology analysis. The dataset features 446 high-resolution images, each with two key components: (1) raw, conflicting annotations from four independent pathologists, and (2) a separate, high-quality gold-standard ground truth established by a senior expert. This dual structure makes CytoCrowd a versatile resource. It serves as a benchmark for standard computer vision tasks, such as object detection and classification, using the ground truth. Simultaneously, it provides a realistic testbed for evaluating annotation aggregation algorithms that must resolve expert disagreements. We provide comprehensive baseline results for both tasks. Our experiments demonstrate the challenges presented by CytoCrowd and establish its value as a resource for developing the next generation of models for medical image analysis.

Real-world temporal graphs are largely driven by sequential dynamics, and edge repetitions are rare. This characteristic has spotlighted a key limitation of existing temporal graph neural networks (T-GNNs): on such graphs, state-of-the-art T-GNNs often achieve less than 70% MRR on link prediction. Two factors drive this shortfall: (1) Memory modules and neighbor co-occurrence encodings in existing T-GNNs often fail since they rely on memorizing exact neighbor identities and on the co-occurrence assumption. (2) Existing T-GNNs are sensitive to abrupt events, which are common in sequential settings that can exceed ten million updates, thereby compromising generalization. To tackle the challenges of sequential dynamics, we propose SeqFilter, a simple yet robust neural network that functions as a composite filter for link prediction on temporal graphs. SeqFilter comprises two modules: a node rhythm memory and a frequency-selective structure encoder. The node rhythm memory shifts the focus from who interacts to when, modeling absolute timestamps with recency awareness to capture each node's interaction rhythm. To model temporal structures in complex sequential dynamics, we propose a frequency-selective structure encoder that amplifies or suppresses specific frequencies in the neighbor spectrum, enabling the effective modeling of local structure correlations. Theoretically, this encoder functions as a cascade of three learnable filters that approximate the optimal linear denoiser, helping capture the underlying structural patterns. Last, SeqFilter fuses the outputs of two modules to generate high-quality node embeddings. Extensive experiments across eight sequential dynamic datasets show that SeqFilter outperforms 11 baselines by an average improvement of 15.82% in MRR while achieving an order of magnitude speedup compared to the frequency-enhanced baseline.

Abstract Graph Neural Networks (GNNs) have become essential for solving graph-level tasks, such as classification and regression, across diverse domains including social networks and biology. However, existing GNNs struggle with the expressivity that captures complex structural patterns, and the generalization that ensures robust performance on diverse and noisy datasets. To address these challenges, we propose a novel GNN model that integrates a k -path rooted subgraph encoder, an adaptive graph contrastive learning approach, and a consistency-aware loss. The k -path rooted subgraph encoder enhances expressivity by capturing and distinguishing intricate substructures, with theoretical guarantees for counting paths and cycles. The adaptive graph contrastive learning framework improves generalization by generating domain-aware graph augmentations based on edge importance, while the consistency-aware loss ensures task-relevant properties are preserved across augmented views. Extensive experiments on 26 datasets spanning graph classification, regression, and realistic scenarios such as noise, class imbalance, and few-shot learning show that our model achieves superior performance against 18 state-of-the-art GNN models in both effectiveness and efficiency. The code is released in https://anonymous.4open.science/r/GEGNN .

Abstract Large-scale crowdsourcing with high-quality results, such as online surveys and data labeling tasks, is in wide demand. Existing techniques on task assignment result quality optimization, however, have addressed only a part of optimization space that does not necessarily reflect the real-world problem. For example, in reality, the proper worker set for task assignment and the workers’ submissions to the task are non-obvious in advance, which is not considered by existing techniques. Hence, this paper discusses a task assignment algorithm that dynamically probes the proper worker set(s) and worker submission models for the task to optimize task assignments in terms of quality, time, and expense. Specifically, we introduce CrowdBwO (Crowd Bandit with Optimization), a novel multi-armed bandit algorithm that is based on batched bandits and bandits with Knapsack and incorporates worker submission models. CrowdBwO dynamically determines and utilizes proper worker set(s) and worker submission models for each task under uncertainty to achieve high-performance crowdsourcing. We conducted extensive experiments with synthetic workers and real workers to evaluate CrowdBwO in two specific problem settings. Our extensive experimental results demonstrate that CrowdBwO is significant for real-world crowdsourcing and has a high performance.

Recently, Hyper-relational Knowledge Graphs (HKGs) have been proposed as an extension of traditional Knowledge Graphs (KGs) to better represent real-world facts with additional qualifiers. As a result, researchers have attempted to adapt classical Knowledge Graph Embedding (KGE) models for HKGs by designing extra qualifier processing modules. However, it remains unclear whether the superior performance of Hyper-relational KGE (HKGE) models arises from their base KGE model or the specially designed extension module. In this paper, we data-wise convert HKGs to KG format using decomposition methods and then evaluate several classical KGE models' performance on HKGs. Our results show that some KGE models achieve comparable performance to HKGE models. Upon further analysis, we find that the decomposition methods alter the original HKG topology and fail to fully preserve HKG information. Moreover, we observe that current HKGE models are either insufficient in capturing the graph's long-range dependency or struggle to integrate main-triple and qualifier information due to the information compression issue. To further justify our findings and provide a direction for HKGE research, we propose FormerGNN, which employs a qualifier integrator to preserve the original HKG topology, a GNN-based graph encoder to capture the graph's long-range dependencies, and an improved approach for integrating main-triple and qualifier information to mitigate compression issues. Our experimental results demonstrate that FormerGNN outperforms existing HKGE models.

Estimating spatial distributions is important in data analysis, such as traffic flow forecasting and epidemic prevention. To achieve accurate spatial distribution estimation, the analysis needs to collect sufficient user data. However, collecting data directly from individuals could compromise their privacy. Most previous works focused on private distribution estimation for one-dimensional data, which does not consider spatial data relation and leads to poor accuracy for spatial distribution estimation. In this paper, we address the problem of private spatial distribution estimation, where we collect spatial data from individuals and aim to minimize the distance between the actual distribution and estimated one under Local Differential Privacy (LDP). To leverage the numerical nature of the domain, we project spatial data and its relationships onto a one-dimensional distribution. We then use this projection to estimate the overall spatial distribution. Specifically, we propose a reporting mechanism called Disk Area Mechanism (DAM), which projects the spatial domain onto a line and optimizes the estimation using the sliced Wasserstein distance. Through extensive experiments, we show the effectiveness of our DAM approach on both real and synthetic data sets, compared with the state-of-the-art methods, such as Multi-dimensional Square Wave Mechanism (MDSW) and Subset Exponential Mechanism with Geo-I (SEM-Geo-I). Our results show that our DAM always performs better than MDSW and is better than SEM-Geo-I when the data granularity is fine enough.

In recent years, dynamic knowledge graph embedding (DKGE) has been widely studied to deal with large-scale dynamic knowledge graphs (DKG). The core idea is to encode dynamic information within DKGs into embedding vectors and decode them for various downstream tasks on the DKGs. Plenty of contributions have been made to this field. Full retraining DKG models additionally encode temporal information for higher performance, while neighboring retraining models view time data as dynamic changes in graph topology for better efficiency. However, existing approaches within these categories suffer from either effectiveness-insufficient or efficiency-insufficient issues. Recent contributions in graph area propose solutions to selectively retrain the models by choosing training data following certain criteria, but the majority of selective retraining models are designed for homogeneous graphs. The heterogeneous graph information and large graph sizes make it improper to transfer methods across scenarios. In this paper, we propose an efficient selective incremental training framework for DKGE, namely SIT. Given a restriction on training data size, we select a set of important triples instead of all triples in the DKG to improve training efficiency. In detail, we design a novel importance criteria considering DKGE model parameters, historical embedding and graph topology. Extensive experiments on open-source datasets demonstrate the effectiveness and efficiency of the SIT framework against different DKGE models.

Pre-trained language models (PLMs) have been successfully used to build high-performance ranking models for large-scale information retrieval systems. However, traditional PLM-based ranking approaches face two key challenges: (1) these models use both sparse and dense content (such as the query/title and content of documents) as inputs, which may require different attention allocations; and (2) traditional PLM-based ranking approaches have identified multiple objectives to gauge user satisfaction with ranking results, but integrating these objectives into the end-to-end training process and the subsequent feature updates and iterations usually involves significant computational resource overhead. In this paper, we propose a novel PLM-based ranking approach M2oE Rank, Multi-objective Mixture-of-Experts (MoE) enhanced Ranking. Specifically, M2oERank lever-ages a context-aware PLM-based hierarchical encoder to extract semantic relevance between the query and the document title and content, while allowing for separate dense and sparse attention for different inputs. With the extracted semantic relevance repre-sentations, multifacet user satisfaction features and task-specific annotations, M2oERank employs an MoE module to perform multi-objective pre-training of ranking models focused on user satisfaction. Finally, M2oERank uses a weight fusion module that fuses outputs from the above experts to predict ranking scores. Moreover, we present a three-stage offline training strategy and the online system workflow for deploying M2oERank at web-scale search. To demonstrate the effectiveness of our proposed approach, we conduct extensive offline and online evaluations using real-world web traffic from Baidu Search. The comparisons against numbers of advanced baselines confirmed the advantages of M2oERank in producing high-performance ranking models for web-scale search.

In the practical use of graph databases, storing graphs separately enhances maintainability, while integrating them into a unified graph facilitates advanced analytics. To address these dual needs, we present a GQL-compatible framework for creating graph views across multiple property graphs. Leveraging insights from commercial graph database environments and user-driven requirements, we identify two key graph transformations—merging and expansion—that significantly boost query efficiency. By incorporating these transformations into view generation, we effectively minimize redundant queries. Furthermore, we streamline view creation through implicit edge creation and automated property merging. To ensure views meet user expectations before full generation, we introduce a preview feature that uses sampling to effectively represent the graph structure. We assess the performance of GalaxyView across diverse workloads, with comprehensive experiments on real-world graphs demonstrating significant improvements in query performance and operational efficiency.

Ridesharing services play an essential role in modern transportation, which significantly reduces traffic congestion and exhaust pollution. In the ridesharing problem, improving the sharing rate between riders can not only save the travel cost of drivers but also utilize vehicle resources more efficiently. The existing online-based and batch-based methods for the ridesharing problem lack the analysis of the sharing relationship among riders, leading to a compromise between efficiency and accuracy. In addition, the graph is a powerful tool to analyze the structure information between nodes. Therefore, in this paper, we propose a framework, namely StructRide, to utilize the structure information to improve the results for ridesharing problems. Specifically, we extract the sharing relationships between riders to construct a shareability graph. Then, we define a novel measurement, namely shareability loss, for vehicles to select groups of requests such that the unselected requests still have high probabilities of sharing with other requests. Our SARD algorithm can efficiently solve dynamic ridesharing problems to achieve dramatically improved results. Through extensive experiments, we demonstrate the efficiency and effectiveness of our SARD algorithm on two real datasets. Our SARD can run up to 72.68 times faster and serve up to 50% more requests than the state-of-the-art algorithms.

As modern learning-to-rank (LTR) systems rely on both textual and behavioral features, it is essential to extend pre-trained language models (PLMs) from text (queries and webpages) understanding to end-to-end ranking score prediction subject to multiple objectives, such as relevance, quality, authority, and recency. While textual inputs encompass a broader array of features than mere relevance and behavioral features are frequently skewed by user feedback with position bias, an integrated solution is required to jointly disentangle and fuse these heterogeneous features, ensuring robust and unbiased ranking predictions. In this work, we introduce RankExpert, a unified framework that holistically models heterogeneous ranking signals by integrating PLM-based semantic extraction with behavioral cues. RankExpert employs a lightweight PLM with hierarchical distillation for efficient query-document representation, a mixture-of-experts (MoE) architecture to disentangle and optimize objectives across relevance, quality, authority, and recency, and a click expert to mitigate position bias in user feedback within a dual-tower design. Then, RankExpert utilizes an adaptive weight fusion layer to dynamically integrate the outputs of these specialized experts dynamically, aligning ranking predictions with diverse user intents. Extensive offline evaluations on two large-scale real-world datasets reveal that RankExpert significantly outperforms strong competitor models and substantial gains in key performance indicators. Moreover, we deploy RankExpert at Baidu Search and conduct comprehensive online evaluations with real-world web traffic, demonstrating substantial improvements in user satisfaction metrics over the online legacy system and underscoring the practicality of the proposed approach.

Citation classification, which identifies the intention behind academic citations, is pivotal for scholarly analysis. Previous works suggest fine-tuning pretrained language models (PLMs) on citation classification datasets, reaping the reward of the linguistic knowledge they gained during pretraining. However, directly fine-tuning for citation classification is challenging due to labeled data scarcity, contextual noise, and spurious keyphrase correlations. In this paper, we present a novel framework, Citss, that adapts the PLMs to overcome these challenges. Citss introduces self-supervised contrastive learning to alleviate data scarcity, and is equipped with two specialized strategies to obtain the contrastive pairs: sentence-level cropping, which enhances focus on target citations within long contexts, and keyphrase perturbation, which mitigates reliance on specific keyphrases. Compared with previous works that are only designed for encoder-based PLMs, Citss is carefully developed to be compatible with both encoder-based PLMs and decoder-based LLMs, to embrace the benefits of enlarged pretraining. Experiments with three benchmark datasets with both encoder-based PLMs and decoder-based LLMs demonstrate our superiority compared to the previous state of the art. Our code is available at: github.com/LITONG99/Citss

Single-cell RNA sequencing (scRNA-seq) technology has emerged as a powerful tool for studying complex biological systems and diseases with high resolution. However, generating sufficient high quality scRNA-seq samples for accurate downstream analyses and ensuring reproducibility remains a challenge. Previous methods often produce low-quality samples or a limited number of useful specific cell subpopulations. To address this issue, we propose a novel Efficient Single-Cell RNA-seq Flow Diffusion (named ESCFD) method based on the Diffusion Model, capable of synthesizing large-scale, high-quality scRNA-seq samples and generating either ''holistic'' or specific cellular subpopulations within a single framework. A pre-guidance mechanism is designed for synthesizing specific cellular subpopulations of high quality, and a post-guidance mechanism was designed to accelerate the sampling of scRNA-seq samples. The ESCFD can efficiently synthesize large-scale and high-quality scRNA-seq samples for various downstream tasks, surpassing previous work with faster sampling speed. Experimental results demonstrate that the ESCFD model achieves state-of-the-art performance in cell classification and cell distribution similarity when evaluated on three scRNA-seq benchmarks, and verified the effectiveness of accelerated sampling. Visualization experiments also reveal the ESCFD's ability to synthesize specific cellular subpopulations. This innovative approach has the potential to significantly advance our understanding of complex biological systems and accelerate the development of novel therapeutic interventions and personalized medicine strategies.

All known AridViper tools including MICROPSIA

Large language model (LLM) inference serving systems are essential to various LLM-based applications. As demand for LLM services continues to grow, scaling these systems to handle high request rates while meeting latency Service-Level Objectives (SLOs), referred to as effective throughput, becomes critical. However, existing systems often struggle to improve effective throughput, primarily due to a significant decline in Time To First Token (TTFT) SLO attainment. We identify two major causes of this bottleneck: (1) memory-intensive KV cache that limits batch size expansion under GPU memory constraints, and (2) rigid batch composition enforced by the default First-Come-First-Serve scheduling policy. In this paper, we introduce Apt-Serve, a scalable framework designed to enhance effective throughput in LLM inference serving. Apt-Serve features a new hybrid cache scheme that combines KV cache with a memory-efficient hidden cache for reusable input hidden state vectors, allowing large batch sizes and improving request concurrency. Based on the hybrid cache, Apt-Serve employs an adaptive runtime scheduling mechanism that dynamically optimizes batch composition. We formally define the adaptive scheduling optimization problem and propose an efficient algorithm with theoretical guarantees. Extensive evaluations on three real-world datasets and LLMs ranging from 13B to 66B parameters demonstrate that Apt-Serve achieves up to 8.8x improvement in effective throughput compared to the state-of-the-art inference serving systems.

Performance predictability, ensuring low latency variability, is crucial for the reliability and efficiency of blockchain consensus. Byzantine Fault Tolerant Proof-of-Stake (BFT-PoS) consensus aims to achieve stable transaction processing latency by scheduling block generation at consistent intervals. However, BFT-PoS's incentive mechanisms grant all transaction tips to the block proposer, which can be exploited by delaying proposals to gain extra Maximal Extractable Value (MEV) rewards, thus undermining performance predictability. Existing solutions impose penalties for delays but lack a standard for measuring the extra rewards from delays or fail in malicious environments. This paper introduces InTime, a novel approach to safeguard performance predictability in BFT-PoS by economically motivating timely block proposals. We first introduce the untimely MEV ratio , a reliable metric to measure the extra rewards gained from proposal delays, facilitating our countermeasures against deliberate delays. Furthermore, we propose the arrival rate incentive (ARI), aligning rewards with transaction arrival timing among nodes to reduce potential MEV manipulation. To make ARI robust against malicious behaviors, we establish a committee time witness (CTW) workflow to accurately gather and verify transaction arrival times. Extensive experiments demonstrate that InTime can effectively reduce latency variability by up to 95.9%.

Streaming data collection is indispensable for stream data analysis, such as event monitoring. However, publishing these data directly leads to privacy leaks. w -event privacy is a valuable tool to protect individual privacy within a given time window while maintaining high accuracy in data collection. Most existing w -event privacy studies on infinite data stream only focus on homogeneous privacy requirements for all users. In this paper, we propose personalized w -event privacy protection that allows different users to have different privacy requirements in private data stream estimation. Specifically, we design a mechanism that allows users to maintain constant privacy requirements at each time slot, namely Personalized Window Size Mechanism (PWSM). Then, we propose two solutions to accurately estimate stream data statistics while achieving w -Event є -Personalized Differential Privacy (( w,є )-EPDP), namely Personalized Budget Distribution (PBD) and Personalized Budget Absorption (PBA). PBD always provides at least the same privacy budget for the next time step as the amount consumed in the previous release. PBA fully absorbs the privacy budget from the previous k time slots, while also borrowing from the privacy budget of the next k time slots, to increase the privacy budget for the current time slot. We prove that both PBD and PBA outperform the state-of-the-art private stream estimation methods while satisfying the privacy requirements of all users. We demonstrate the efficiency and effectiveness of our PBD and PBA on both real and synthetic datasets, compared with the recent uniformity w -event approaches, Budget Distribution (BD) and Budget Absorption (BA). Our PBD achieves 68% less error than BD on average on real datasets. Besides, our PBA achieves 24.9% less error than BA on average on synthetic datasets.

Approximate Nearest Neighbor (ANN) search is a foundational yet computationally demanding query in vector databases, critical for applications such as information retrieval and generative AI inference. Hierarchical graph-based methods have attracted significant attention due to their promising query performances compared to other indexes for ANN search. However, these methods still face efficiency bottlenecks because they rely on exhaustive and level-by-level traversals within hierarchical graphs. This paper introduces SHG, a novel hierarchical graph-based index that enhances search efficiency by bypassing intermediate and redundant levels. Specifically, SHG leverages a hierarchical vector compression method to reduce the time spent on distance computations, and employs a new data structure called shortcuts to determine the number of intermediate levels that can be safely skipped. Extensive experiments demonstrate that our solution achieves 1.5–1.8× speedup compared to state-of-the-art methods. Meanwhile, our method significantly improves the robustness of ANN search, boosting recall by up to 20% for certain queries on benchmark datasets.

Temporal link prediction in dynamic graphs is a critical task with applications in diverse domains such as social networks, recommendation systems, and e-commerce platforms. While existing Temporal Graph Neural Networks (T-GNNs) have achieved notable success by leveraging complex architectures to model temporal and structural dependencies, they often suffer from scalability and efficiency challenges due to high computational overhead. In this paper, we propose EAGLE, a lightweight framework that integrates short-term temporal recency and long-term global structural patterns. EAGLE consists of a time-aware module that aggregates information from a node's most recent neighbors to reflect its immediate preferences, and a structure-aware module that leverages temporal personalized PageRank to capture the influence of globally important nodes. To balance these attributes, EAGLE employs an adaptive weighting mechanism to dynamically adjust their contributions based on data characteristics. Also, EAGLE eliminates the need for complex multi-hop message passing or memory-intensive mechanisms, enabling significant improvements in efficiency. Extensive experiments on seven real-world temporal graphs demonstrate that EAGLE consistently achieves superior performance against state-of-the-art T-GNNs in both effectiveness and efficiency, delivering more than a 50× speedup over effective transformer-based T-GNNs.

Learned indexes have attracted significant research interest due to their potential to offer better space-time trade-offs compared to B+-tree variants. Among various learned indexes, the PGM-Index based on error-bounded piecewise linear approximation is an elegant data structure that has demonstrated provably superior performance over conventional B+-tree indexes. However, despite numerous efforts to optimize the design of the PGM-Index, few systematically study the root causes of performance mismatches observed in practice. In this paper, we explore two key research questions. Q1 : Why are PGM-Indexes theoretically effective? and Q2 : Why do PGM-Indexes underperform in practice? For Q1 , we show that for a set of N sorted keys, the PGM-Index can achieve a lookup time of O (log log N ) while using O ( N ) space. For Q2 , we identify that querying PGM-Indexes is highly memory-bound, where the internal index search operations often become the bottleneck. To fill the performance gap, we propose PGM++, a simple yet effective extension to the original PGM-Index that employs a mixture of different search strategies, with hyper-parameters automatically tuned through a cost model calibrated by theoretical findings. Extensive experiments show that, at comparable space costs, PGM++ speeds up index lookup queries by up to 2.31X and 1.56X when compared to the original PGM-Index and SOTA baselines.

The rapid advancements of generative artificial intelligence (GenAI) have recently led to renewed attention towards approximate nearest neighbor (ANN) search and vector databases (VectorDB). Among various ANN methodologies, vector quantization techniques like product quantization (PQ) are widely used to generate space-efficient representations for large-scale dense vectors. However, the code-books generated by PQ often reach several gigabytes in size, making them impractical for web-scale, high-dimensional vectors in resource-constrained environments like mobile devices. In this study, we propose SegPQ , a simple yet effective framework for losslessly compressing codebooks generated by any PQ variants, enabling efficient in-memory vector search on devices with limited memory. SegPQ represents the raw PQ codewords as a trained error-bounded piecewise linear approximation model (ϵ-PLA) and pre-computed low-bit residuals. We theoretically demonstrate that, with high probability, the number of bits per compressed codeword is 1.721 + ⌈log 2 ϵ OPT ⌉, where ϵ OPT is the optimal error parameter that can be determined by data characteristics. To accelerate query execution, we further design SIMD-aware query processing algorithms on compressed codebooks to fully exploit the hardware parallelism offered by modern architectures. Extensive experimental studies on real datasets showcase that, for 1 billion vectors, SegPQ reduces PQ codebook memory consumption by up to 4.7 x (approx. 851 MB ) while incurring only 3.3% additional query processing overhead caused by decompression.

Blockchains have gained wide adoption for secure data processing. As blockchain data volumes grow, the demand for efficient data analysis, especially aggregate queries, becomes increasingly critical. However, current blockchains lack native support for efficient analytical query processing, forcing users to either maintain full replicas or rely on third-party services without integrity guarantees. In this paper, we propose an efficient framework, Merkle Bloom Filter Tree (MBFT), for authenticated aggregate queries that combine boolean keywords and range predicates on blockchains. At its core is a Bloom filter-based authenticated data structure that supports both types of predicates, constructed per block for efficient transaction indexing. For temporal predicates, we optimize time window queries through value pruning and block consolidation. We design a novel Merge Bloom Filter (MBF) for space-efficient handling of dynamic sets during query authentication. We provide a theoretical analysis of the storage overhead caused by the Bloom filter's false positive rates. Our framework employs data sketches to support various aggregate operations. Extensive experiments demonstrate that MBFT has improved the query speed by up to 286× compared to state-of-the-art authenticated query solutions.

Modern computing systems, such as HDFS and Spark, produce vast quantities of logs that developers use for tasks like anomaly detection and error analysis. To simplify log analysis, template generation methods have been proposed to standardize log formats, transforming unstructured data into structured templates. Existing heuristic-based methods and neural network-based methods suffer from low accuracy problems due to the reliance on handcrafted heuristics or specific log patterns in training sets. Recently, large language models (LLMs) have shown great potential in log template generation. However, they often struggle with ambiguous, complex, or highly specific log content, which can lead to errors in generating accurate templates. To address these challenges, we propose LLMLog, a multi-round annotation framework with adaptive in-context learning. We first propose an edit-distance-based similarity metric to evaluate log similarity. Then, we introduce a method to select the most informative k unlabeled logs for annotation by considering both the representativeness of the logs and the confidence of LLM predictions. Additionally, we design an adaptive context selection strategy that adaptively selects labeled logs to ensure comprehensive keyword coverage for unlabeled logs. These labeled logs serve as the context for LLMs to better understand the unlabeled logs, thereby enhancing the accuracy of template generation. Extensive experiments on sixteen datasets demonstrate that LLMLog outperforms the state-of-the-art approaches.

Most enterprise graph data derives from relational databases, yet transforming relational tables into query-optimized graph schemas remains challenging. Existing approaches have notable limitations: (1) transformations based on primary and foreign keys often fail to generate schemas optimized for query performance; (2) manual schema design, although flexible, is costly and requires domain expertise; and (3) machine learning methods predict graph structures based on data patterns but heavily depend on large, high-quality training datasets. To address these challenges, we propose Galaxy-Weaver, a framework to automate query-aware graph schema generation. GalaxyWeaver utilizes the reasoning power of Large Language Models (LLMs) to align graph schema designs with specific query requirements, effectively integrating domain knowledge with optimization strategies. The framework employs prompt-guided analysis to enhance the decision-making accuracy of LLM agents, facilitating iterative schema refinement. Experiments across diverse domains show that GalaxyWeaver simplifies transformation while improving query performance and reducing storage costs.

Semantic caching significantly reduces computational costs and improves efficiency by storing and reusing large language model (LLM) responses. However, existing systems rely primarily on matching individual queries, lacking awareness of multi-turn dialogue contexts, which leads to incorrect cache hits when similar queries appear in different conversational settings. This demonstration introduces ContextCache, a context-aware semantic caching system for multi-turn dialogues. ContextCache employs a two-stage retrieval architecture that first executes vector-based retrieval on the current query to identify potential matches and then integrates current and historical dialogue representations through self-attention mechanisms for precise contextual matching. Evaluation of real-world conversations shows that ContextCache improves precision and recall compared to existing methods. Additionally, cached responses exhibit approximately 10 times lower latency than direct LLM invocation, enabling significant computational cost reductions for LLM conversational applications.

Graph Neural Networks (GNNs) have achieved remarkable success in various graph-related tasks. However, training GNNs on large-scale graphs is hindered by the neighbor explosion problem, rendering full-batch training computationally infeasible. Mini-batch training with neighbor sampling is a widely adopted solution, but it introduces gradient estimation errors that slow convergence and reduce model accuracy. In this work, we identify two primary sources of these errors: (1) missing gradient contributions from unsampled target nodes, and (2) inaccuracies in messages computed from sampled nodes. While existing methods largely focus on mitigating the second source, they often overlook the first, resulting in incomplete gradient estimation. To address this gap, we propose the Pseudo Full Neighborhood Compensation (PFNC) framework, which leverages historical information to simultaneously compensate for both errors. PFNC is designed to integrate seamlessly with any neighbor sampling technique and significantly lowers memory demands by maintaining only a partial cache of historical embed-dings and gradients. Theoretical analysis demonstrates that PFNC provides a closer approximation to the ideal gradient, enhancing convergence. Extensive experiments across multiple benchmark datasets confirm that PFNC accelerates convergence and improves generalization across diverse neighbor sampling strategies.

Multimodal Entity Linking (MEL), which involves disambiguating a mention composed of multimodal inputs to a multimodal knowledge base (KB), has gained increasing attention. Although existing MEL approaches using supervised learning show promising performance, they depend heavily on large-scale labeled training data, which is expensive to obtain for each new scenario. Unsupervised learning MEL methods, on the other hand, typically consist of two main steps. In the first multimodal data encoding step, these methods either assume that the multimodal data inputs are of high quality or attempt to filter out the noisy modality. In the second entity ranking step, they employ a bipartite graph to model the relationships only between mentions and entities. However, unsupervised methods face challenges in both steps. In the first step, data quality issues arise, including limited context in textual inputs and noise in the corresponding images. Moreover, in the second step, the bipartite graph fails to capture coherence between highly correlated entities within the KB, which offers clues on shared domains among entities. This limitation hinders effective retrieval of the target entity. To address these issues, we propose a novel unsupervised learning framework, OpenMEL, for solving the MEL task. We enhance the textual modality contextual information by incorporating full context comprehension and general knowledge, and generates three levels of visual inputs for further adaptive selection to handle noise. To capture global entity coherence, we construct a tree cover structure, defining it as a maximum spanning tree with bounded nodes to meet the MEL objective. We then introduce a greedy algorithm with theoretical guarantees to solve this problem. Experimental results on three public benchmark datasets show that OpenMEL outperforms various state-of-the-art baselines.

Representation learning over dynamic graphs is critical for many real-world applications such as social network services and recommender systems. Temporal graph neural networks (T-GNNs) are powerful representation learning methods and have demonstrated remarkable effectiveness on continuous-time dynamic graphs. However, T-GNNs still suffer from high time complexity, which increases linearly with the number of timestamps and grows exponentially with the model depth, making them not scalable to large dynamic graphs. To address the limitations, we propose Orca , a novel framework that accelerates T-GNN training by caching and reusing intermediate embeddings. We design an optimal caching policy, named MRD , for the uniform cache replacement problem, where embeddings at different intermediate layers have identical dimensions and recomputation costs. MRD not only improves the efficiency of training T-GNNs by maximizing the number of cache hits but also reduces the approximation errors by avoiding keeping and reusing extremely stale embeddings. For the general cache replacement problem, where embeddings at different intermediate layers can have different dimensions and recomputation costs, we solve this NP-hard problem by presenting a novel two-stage framework with approximation guarantees on the achieved benefit of caching. Furthermore, we have developed profound theoretical analyses of the approximation errors introduced by reusing intermediate embeddings, providing a thorough understanding of the impact of our caching and reuse schemes on model outputs. We also offer rigorous convergence guarantees for model training, adding to the reliability and validity of our Orca framework. Extensive experiments have validated that Orca can obtain two orders of magnitude speedup over state-of-the-art T-GNNs while achieving higher precision on various dynamic graphs.

Programmatic Weak Supervision (PWS) is a recent data labeling paradigm, which employs several Labeling Functions (LFs) to provide weak labels and involves a Label Model (LM) for label aggregation. Despite the significant progress, there still remain some inherent challenges in PWS. From the view of labeling, LFs may wrongly label some data points. From the view of data, some data points themselves may be low-quality (e.g., ambiguous texts or blurred images). These largely stem from the lack of an explicit evaluation mechanism for LFs or data points. To this end, inspired by confident learning focusing on label quality, we propose a Confident PWS (CPWS) approach for high-quality data labeling. Specifically, several LFs are firstly utilized to provide weak labels for unlabeled data. Then, we develop an explicit Dual Evaluation Mechanism (DEM) to evaluate the quality of both LFs and data points, which not only employs data to evaluate trained models but also leverages trained models to evaluate data. Along this line, we further design a Distribution-Guided Pruning Strategy (DPS) to prune low-quality data and aggregate weak labels under the guidance of label class distribution. Extensive experiments on various benchmark datasets demonstrate the effectiveness and generalization ability of our proposed approach.

Abstract We are currently in the epoch of Large Language Models (LLMs), which have transformed numerous technological domains within the database community. In this paper, we examine the application of LLMs in text-to-visualization (text-to-vis). The advancement of natural language processing technologies has made natural language interfaces more accessible and intuitive for visualizing tabular data. However, despite utilizing advanced neural network architectures, current methods such as Seq2Vis, ncNet, and RGVisNet for transforming natural language queries into DV commands still underperform, indicating significant room for improvement. In this paper, we introduce Prompt4Vis , a novel framework that leverages LLMs and In-context learning to enhance the generation of data visualizations from natural language. Given that In-context learning’s effectiveness is highly dependent on the selection of examples, it is critical to optimize this aspect. Additionally, encoding the full database schema of a query is not only costly but can also lead to inaccuracies. This framework includes two main components: (1) an example mining module that identifies highly effective examples to enhance In-context learning capabilities for text-to-vis applications, and (2) a schema filtering module designed to streamline database schemas. Comprehensive testing on the NVBench dataset has shown that Prompt4Vis significantly outperforms the current state-of-the-art model, RGVisNet, by approximately 35.9% on development sets and 71.3% on test sets. To the best of our knowledge, Prompt4Vis is the first framework to incorporate In-context learning for enhancing text-to-vis, marking a pioneering step in the domain.

Efficient indexing is fundamental to managing and analyzing multi-dimensional data. A growing trend is to directly learn the storage layout of multi-dimensional data using simple machine learning models, leading to the concept of Learned Index . Compared to conventional indexing methods that have been used for decades (e.g., k d-tree and R-tree variants), learned indexes have demonstrated empirical advantages in both space and time efficiency on modern architectures. However, there is a lack of comprehensive evaluation across existing multi-dimensional learned indexes under a standardized benchmark, making it challenging to identify the most suitable index for specific data types and query patterns. This gap also hinders the widespread adoption of learned indexes in practical applications. In this paper, we present the first in-depth empirical study to answer the question: how good are multi-dimensional learned indexes? We evaluate ten recently published indexes under a unified experimental framework, which includes standardized implementations, datasets, query workloads, and evaluation metrics. We thoroughly investigate the evaluation results and discuss the findings that may provide insights for future learned index design.

Abstract Graph neural networks (GNNs) have emerged due to their success at modeling graph data. Yet, it is challenging for GNNs to efficiently scale to large graphs. Thus, distributed GNNs come into play. To avoid communication caused by expensive data movement between workers, we propose Sancus and its advanced version Sancus"Equation missing", the staleness and quantization-aware communication-avoiding decentralized GNN system. By introducing a set of novel bounded embedding staleness metrics and adaptively skipping broadcasts, Sancus abstracts decentralized GNN processing as sequential matrix multiplication and uses historical embeddings via cache. To further mitigate the communication volume, Sancus"Equation missing" conducts quantization-aware communication on embeddings to reduce the size of broadcast messages. Theoretically, we show bounded approximation errors of embeddings and gradients with a known fastest convergence guarantee. Empirically, we evaluate Sancus and Sancus"Equation missing" with common GNN models via different system setups on large-scale benchmark datasets. Compared to SOTA works, Sancus"Equation missing" can avoid up to $$86\%$$ 86 % communication with $$3.0\times $$ 3.0 × faster throughput on average without accuracy loss.

The prediction of stock prices is a highly sought-after topic in the data mining field. In recent decades, many promising methods have been proposed and widely adopted for stock price prediction. However, these methods have inherent limitations, such as low accuracy, lack of transparency, and failure to consider the interactions among stock factors. To address these issues, we propose a UNIversal and interpretable framework for enhancing Stock Price Prediction (abbreviated to UniSPP), which is capable of modeling the interactions among stock factors. UniSPP first builds a fully connected graph, where the nodes and edges are the stock factors and interactions between them, respectively. However, it is a non-trivial task to discover a proper feature interaction subgraph from a large space, especially in discrete graph modeling. Therefore, UniSPP proposes a novel idea to mine the real factor interactions by iteratively sampling subgraphs and optimizing the sampling controller. Empirical studies show that our framework can be incorporated with many popular forecasting models and can effectively discover the suitable factor interaction, which can significantly improve the prediction results of existing models.

An area of research on communities in signed networks aims to find structures in which each user in the graph is connected to other members in their community by more positive edges than negative edges, indicating a positive experience for the user. However, some of these communities are ‘echo chambers', a rising area of concern in modern discourse regarding social media, which contain almost exclusively positive edges indicating all users trust each other with little or no push-back. Here exists an interesting contradiction, when finding a ‘positive’ community often times the resulting structure may be the negative ‘echo chamber’. In this work we propose a signed graph community substructure named the$(\epsilon,\ \phi)$-Clique which is the best of both worlds, where each user is happy to be in their community (indicated by have a proportion of positive edges$\geq\epsilon$for each node) as well as there existing a level of disagreement in the system (indicated by the community having a proportion of negative edges$\geq \phi$). From this definition, we design algorithms to exactly find the Maximum$(\epsilon,\ \phi)$-Clique containing a query user, utilising heuristics to combat the NP-Hard and NP-Hard to approximate nature of the problem. We perform experiments to examine the improvements in efficiency of our algorithms to the proposed baseline as well as examine example community outputs to show the effectiveness of our structure.

Complex social event summarization is a problem which has been important for real-world applications, including crisis management, rumor control and government policy tracking. However, in many critical situations, social events are complex and context-sensitive, which demands the online summarization of social events in an integrated manner. Motivated by this, we propose an online complex social event summarization approach, namely SOMA, which summarizes the complex social events over multiple attributes including media content and contexts simultaneously. The evaluation shows that our proposed approach outperforms the existing solutions for event summarizaiton in terms of effectiveness and efficiency.

Querying the shortest path between two locations is a fundamental task in many applications, and has been extensively studied for static road networks. However, in reality, the travel costs of road segments evolve over time, and hence the road network can be modeled as a time-dependent graph. In this paper, we study the shortest path query over large-scale time-dependent road networks. We first present a tree decomposition method to model the time-dependent road network as a tree structure that preserves travel costs. To further improve query efficiency, a set of shortcuts is selected and built on the constructed tree structure. Specifically, we formally define a shortcut selection problem over the tree decomposition of the time-dependent road network. This problem, which is proven to be NP-hard, aims to select and build the most effective shortcut set. We first devise a dynamic programming method with exact results to solve the selection problem. To obtain the optimal shortcut set quickly, we design an approximation algorithm that guarantees a 0.5-approximation ratio. Based on the novel tree structure, we devise a shortcut-based algorithm to answer the shortest path query over time-dependent road networks. Finally, we conduct extensive performance studies using large-scale real-world road networks. The results demonstrate that our method can achieve better efficiency and scalability than the state-of-the-art method.

Graph anomaly detection attracts considerable interest across a variety of application domains, including fraud detection within social networks, identifying money laundering activities in transaction graphs, etc. The advent of Graph Neural Networks (GNNs) has enhanced existing deep learning methods to capture the anomaly patterns in the latent space and achieve satisfactory results. However, the performance deficiency of current GNNs is primarily caused by the scarce labeled anomalies in a specific real-world application. Unlike the total neglect of valuable labeled anomalies in unsupervised approaches or the potential overfitting in supervised approaches, we proposed a few-shot-oriented framework GUDI in this paper. GUDI is the first work to incorporate a self-supervised pre-training approach to capture general graph patterns across domains and design a classifier with few-shot learning to model the labeled data within a specific domain. The proposed guided diffusion mechanism synthesizes the outcomes of the pre-trained model and the domain-specific classifier in the inference phase, which negates the need for fine-tuning the large pre-trained model, thereby facilitating efficient domain adaptation. GUDI retains the ability to uncover unknown anomalies through unsupervised pre-training while also possessing the ability to identify known anomaly natterns from few-shot labels.

Graph self-supervised learning aiming to learn the graph representation without much label information is an important tasks in data mining and machine learning since labeled graph data is scarce and expensive to obtain in the real world. Contrastive learning emerges as a promising solution. However, we show existing graph contrastive learning (GCL) models have a significant issue: they generate representations that collapse into a low-dimensional subspace, resulting in a loss of information and diversity. We believe this issue arises from the strong assumption in current GCL methods that all positive samples should be close and all negative samples should be far in the representation space. From a data engineering view, this assumption fails to deeply mine the graph data and oversimplifies the complexity and heterogeneity of graph data, leading to clustered and redundant representations. To address this issue, we propose GradGCL, a novel method that leverages intrinsic gradient information as an additional input signal to regularize GCL training. The gradient information reflects the optimization process of the representations with respect to the contrastive loss, providing a complementary perspective to the representations. Furthermore, we have designed a soft separation strategy that relaxes the hard separation strategy between positive and negative samples, allowing for more flexibility and diversity in the representation space. We have conducted extensive experiments on various graph-related tasks, using different types of contrastive losses, datasets, and model architectures. We demonstrate that gradients alone can learn graph information and achieve competitive results with representation-based GCL methods. We also show that GradGCL can enhance existing GCL models and prevent the issue of dimensional collapse.

Recently, graph contrastive learning proposes to learn node representations from the unlabeled graph to alleviate the heavy reliance on node labels in graph neural networks (GNNs). The core idea is to generate diverse positive views and negative views according to local subgraphs. Then, GNNs take these views as supervised signals and train the model by maximizing the similarity between positive view pairs of each node and minimizing the similarity between positive and negative views. Regardless of the fruitful progress, existing graph contrastive learning approaches still suffer from low-efficiency, insufficient-expressivity, and unpreserved-locality issues. First, they train GNNs by all nodes, reducing the efficiency due to similar and redundant nodes. Second, they only use limited operations (e.g., edge deletion and feature masking) to generate positive views, thereby restricting their expressivity. Third, they uniformly delete edges and mask node features and may modify important edges and features, thereby damaging the important locality information of nodes. In this paper, we propose an efficient and expressive contrastive learning framework for GNNs, namely E2GCL. Specifically, given a limited node budget, we select a set of representative nodes instead of all nodes to accelerate the GNNs training. Besides, we use three general operations (edge deletion, edge addition, and feature perturbation) to generate expressive and locality-preserved positive views based on edge and feature importance. Extensive experiments on various real-world datasets demonstrate the superior effectiveness and efficiency of our proposed E2GCL.

Recently, continual learning (CL) has attracted much attention due to its widespread applications in the real world. Given a set of data sets sequentially, continual learning aims to achieve good performance on the new data sets while avoiding deterioration in performance on the old data sets. Despite the success, most CL models follow the supervised setting, which limits their potential in data scarcity cases. Thus, some pioneering works study unsupervised CL (UCL) to discuss what CL tricks suit the unsupervised setting. However, their advancements lack in-depth analysis of the characteristics of UCL, especially the lack of attention to the use of old data. We identify that using old data sets is essential for improving the UCL model performance while existing works ignore them. Unfortunately, given a limited data storage budget, it is a nontrivial task to select representative data and effectively replay them without label assistance. To further improve the UCL performance, we present a new method in this paper, named Effective Data Selection and Replay (EDSR) for UCL. Specifi-cally, we analyze that entropy can be an effective data selection metric, where representative data usually exhibit the highest entropy in the representation space. Then, to balance the model stability for old data and the plasticity for new data, we adopt a strategy of replaying those stored representative data with a noise-enhanced knowledge distillation process. The empirical study demonstrates the outstanding performance of EDSR on benchmark computer vision data sets. Especially, EDSR shows strong resistance to forgetting old data knowledge while maintaining high accuracy. The implementation is publicly available at https://github.com/LeeJarvis996/edsr_project/tree/main/EDSR.

Recommendation systems, as widely implemented nowadays on various platforms, recommend relevant items to users based on their preferences. The classical methods which rely on user-item interaction matrices has limitations, especially in scenarios where there is a lack of interaction data for new items. Knowledge graph (KG)-based recommendation systems have emerged as a promising solution. However, most KG-based methods adopt node embeddings, which do not provide personal-ized recommendations for different users and cannot generalize well to the new items. To address these limitations, we propose Knowledge-enhanced User-Centric subgraph Network (KUCNet), a subgraph learning approach with graph neural network (GNN) for effective recommendation. KUCN et constructs a U-I subgraph for each user-item pair that captures both the historical information of user-item interactions and the side information provided in KG. An attention-based GNN is designed to encode the U-I subgraphs for recommendation. Considering efficiency, the pruned user-centric computation graph is further introduced such that multiple U-I subgraphs can be simultaneously computed and that the size can be pruned by Personalized PageRank. Our proposed method achieves accurate, efficient, and interpretable recommendations especially for new items. Experimental results demonstrate the superiority of KUCNet over state-of-the-art KG-based and collaborative filtering (CF)-based methods. Our code and data is available in https://github.com/leolouis14/KUCNet.1

Annotation through crowdsourcing draws incremental attention, which relies on an effective selection scheme given a pool of workers. Existing methods propose to select workers based on their performance on tasks with ground truth, while two important points are missed. 1) The historical performances of workers in other tasks. In real-world scenarios, workers need to solve a new task whose correlation with previous tasks is not well-known before the training, which is called cross-domain. 2) The dynamic worker performance as workers will learn from the ground truth. In this paper, we consider both factors in designing an allocation scheme named cross-domain-aware worker selection with training approach. Our approach proposes two estimation modules to both statistically analyze the cross-domain correlation and simulate the learning gain of workers dynamically. A framework with a theoretical analysis of the worker elimination process is given. To validate the effectiveness of our methods, we collect two novel real-world datasets and generate synthetic datasets. The experiment results show that our method outperforms the baselines on both real-world and synthetic datasets.

Recently, graph neural networks (GNNs) have shown its unprecedented success in many graph-related tasks. However, GNNs face the label scarcity issue as other neural networks do. Thus, recent efforts try to pre-train GNNs on a large-scale unlabeled graph and adapt the knowledge from the unlabeled graph to the target downstream task. The adaptation is generally achieved by fine-tuning the pre-trained GNNs with a limited number of labeled data. However, current GNNs pre-training works focus more on how to better pre-train a GNN, but ignore the importance of fine-tuning to better leverage the transferred knowledge. Only a few works start to investigate a better fine-tuning strategy for pre-trained GNNs. But their designs either have strong assumptions or overlook the data-aware issue behind various downstream domains. To further boost pre-trained GNNs, we propose to search to fine-tune pre-trained GNNs for graph-level tasks (S2PGNN), which can adaptively design a suitable fine-tuning framework for the given pre-trained GNN and downstream data. Unfortunately, it is a non-trivial task to achieve this goal due to two technical challenges. First is the hardness of fine-tuning space design since there lack a systematic and unified exploration in existing literature. Second is the enormous computational overhead required for discovering suitable fine-tuning strategies from the discrete space. To tackle these challenges, S2PGNN first carefully summarizes a search space of fine-tuning strategies that is suitable for GNNs, which is expressive enough to enable powerful strategies to be searched. Then, S2PGNN integrates an efficient search algorithm to solve the computationally expensive search problem from a discrete and large space. The empirical studies show that S2PGNN can be implemented on the top of 10 famous pre-trained GNNs and consistently improve their performance by 9 % to 17 %. Our code is publicly available at https://github.com/zwangeo/icde2024.

The semantic annotation of tabular data plays a crucial role in various downstream tasks. Previous research has proposed knowledge graph (KG)-based and deep learning-based methods, each with its inherent limitations. KG-based methods encounter difficulties annotating columns when there is no match for column cells in the KG. Moreover, KG-based methods can provide multiple predictions for one column, making it challenging to determine the semantic type with the most suitable granularity for the dataset. This type granularity issue limits their scalability. On the other hand, deep learning-based methods face challenges related to the valuable context missing issue. This occurs when the information within the table is insufficient for determining the correct column type. This paper presents KGLink, a method that combines Wiki-Data KG information with a pre-trained deep learning language model for table column annotation, effectively addressing both type granularity and valuable context missing issues. Through comprehensive experiments on widely used tabular datasets encompassing numeric and string columns with varying type granularity, we showcase the effectiveness and efficiency of KGLink. By leveraging the strengths of KGLink, we successfully surmount challenges related to type granularity and valuable context issues, establishing it as a robust solution for the semantic annotation of tabular data.

The rapidly changing nature of information world-wide often leads to incomplete and obsolete knowledge facts stored in knowledge bases (KBs). Therefore, reasoning over the dynamic KB sequences, which targets at knowledge inference from evolving facts, is of great importance to maintain KB completeness as well as freshness. Existing approaches for KB updating mainly either focus on knowledge representation learning methods, which suffer from lack of interpretability, or attempt to mine path-based logical rules, which are limited in capturing structural semantics of KB. In this work, we present KartGPS, a system for KB updating taking advantage of temporal graph pattern-based semantic (tGPS) rules. Specifically, the tGPS rules are learned from KB sequences and thus are capable of capturing both temporal and topological regularities of KBs along the evolving of time. Due to the huge amount and imperfect quality of tGPS rules, directly generating and applying all generated rules in a brute-force manner for knowledge updating over large-scale KB sequences would be highly time-consuming and error-prone. Therefore, we investigate the problem of Knowledge Update Rule Discovery (KURD), which aims at deriving an optimal subset of tGPS rules for performing knowledge updating, considering the rule quality and coverage. We show that the KURD problem is NP-hard and design two effective approximation algorithms with greedy and pruning strategies. We demonstrate the effectiveness and efficiency of proposed approaches by extensive experiments on real-world KB datasets.

With the development of ubiquitous smart devices, shared mobility services, such as food delivery, ridesharing and crowdsourced parcel delivery, and the related problems, such as task assignment and route planning have drawn much attention from academia and industry. Specifically, shared mobility services enable one worker to deliver more than one package/passenger together such that their routes can share some common sub-routes. Tardiness (the exceeded time) can harm users' experience and reduce the revenue of workers and platforms, which is not well handled in the existing studies. In this paper, we propose a framework, TrendSharing, to minimize the total tardiness when serving all tasks. In TrendSharing, we first build a flow tree to group tasks together. Then, we propose a concept of trend, which represents a group of tasks with high sharability in the flow tree. Furthermore, we devise a decision factor$\epsilon$-score to properly select the trend from the flow tree. In addition, we devise an indicator k-regret to quantify the likelihood of tardiness for each task and devise a greedy algorithm to conduct task assignment. We observe that the insertion operation that is widely used by existing works has little effect on the objective of minimizing total tardiness. Thus, we adopt a simple yet effective strategy, which will continuously append newly planned routes to the workers' existing routes. Moreover, we design an algorithm to plan a route for the trend with an approximation ratio of 2.5. Through extensive experiments, we demonstrate the efficiency and effectiveness of our proposed approaches on real datasets.

Ridesharing services, such as Uber or Didi, have attracted considerable attention in recent years due to their positive impact on environmental protection and the economy. Existing studies require quick responses to orders, which lack the flexibility to accommodate longer wait times for better grouping opportunities. In this paper, we address a NP-hard ridesharing problem, called Minimal Extra Time RideSharing (METRS), which balances waiting time and group quality (i.e., detour time) to improve riders' satisfaction. To tackle this problem, we propose a novel approach called WATTER (WAit To be fasTER), which leverages an order pooling management algorithm allowing orders to wait until they can be matched with suitable groups. The key challenge is to customize the extra time threshold for each order by reducing the original optimization objective into a convex function of threshold, thus offering a theoretical guarantee to be optimized efficiently. We model the dispatch process using a Markov Decision Process (MDP) with a carefully designed value function to learn the threshold. Through extensive experiments on three real datasets, we demonstrate the efficiency and effectiveness of our proposed approaches.

Distant supervision is a technique that aims to create large amounts of training data at a low cost. This approach benefits various downstream systems, particularly in natural language processing and relation extraction tasks. However, due to its strong assumption that any sentence containing entities expresses the specific relation between them found in existing knowledge bases (KBs), distant supervision introduces considerable noise. Existing works attempt to denoise distant supervision data by either using the original text or replacing entities in the text with patterns representing the entity types as inputs. However, replacing a frequently repeating pattern will result in loss of context due to the excessively general semantics of the pattern. Furthermore, due to the lack of ground truth, denoising module often relies on parametric models that still learn distribution from noisy data, which further limits model performance. In this paper, we propose Triple-d, a technique for high-quality data creation through adaptive pattern replacement and a scalable non-parametric model. Specifically, we formulate the adaptive pattern replacement task as a maximum-profit bipartite graph problem and propose an approximation algorithm as a solution. Additionally, we design a non-parametric model with scalable instance normalization to efficiently estimate and eliminate the influence of each dimension in neighbors. Extensive experiments in the denoising task and a downstream relation extraction task on real-world datasets demonstrate the superior effectiveness and efficiency of Triple-d, highlighting its potential to improve the performance for high-quality data creation.11Corresponding author: Yongqi Zhang.

Urban traffic flow data is useful in transport ap-plications, playing an important role in various tasks such as road planning, site selection, ad services, etc. However, traffic flow data is the composition of personal driving trajectories, which can reveal sensitive information such as home and work locations, leading to privacy issues. Thus publishing traffic flow data while not disclosing private information remains a challenge for urban managers. To address this challenge, we study the noisy publication of traffic flow data in this paper. The noise is added to the data with respect to the differential privacy paradigm, which ensures data safety but deteriorates its utility. On the other hand, we find that the inherent relations of the flow data inherited from the road network structure can be used to correct data without hurting the privacy property. Hence, we propose post-processing techniques, which exploit the data's inherent relations for corrections over the global and local differentially private traffic flow data, respectively. Extensive experiments on real data show that the proposed post-processing techniques improve the data utility by 29.7%-41.1% and 17.3%-48.6% subjecting to the global and local differential privacy paradigm, respectively.

In this paper, we address the challenges of data augmentation in Multi-Modal Knowledge Graphs (MMKGs), a relatively under-explored area. We propose a novel diffusion-based generative model, the Simple Denoising Probabilistic Latent Diffusion Model (SimDiff). SimDiff is capable of handling different data modalities including the graph topology in a unified manner by the same diffusion model in the latent space. It enhances the utilization of multi-modal data and encourage the multi-modal fusion and reduces the dependency on limited training data. We validate our method in downstream Entity Alignment (EA) tasks in MMKGs, demonstrating that even when using only half of the seed entities in training, our methods can still achieve superior performance. This work contributes to the field by providing a new data generation or augmentation method for MMKGs, potentially paving the way for more effective use of MMKGs in various applications. Code is made available at https://github.com/ranlislz/SimDiff.

In today's fast-paced world, advertisers are increasingly demanding real-time and accurate personalized ad delivery based on dynamic preference modeling, which emphasizes the temporality existing in both user preference and product characteristics. Meanwhile, with the development of graph neural networks (GNNs), E-commerce knowledge graphs (KG) with rich semantic relatedness are invoked to improve accuracy and provide appropriate explanations to encourage advertisers' willingness to invest in ad expenses. However, it is still challenging for existing methods to comprehensively consider both time-series interactions and graph-structured knowledge triples in a unified model, i.e., the case in knowledge-aware dynamic advertising. The interaction graph between users and products changes rapidly over time, while the knowledge in KG remains relatively stable. This results in an uneven distribution of temporal and semantic information, causing existing GNNs to fail in this scenario. In this work, we quantitatively define the above phenomenon as temporal unevenness and introduce the Incremental Leveling Network (InLN) with three novel techniques: the periodic-focusing window for node-level dynamic modeling, the biased temporal walk for subgraph-level dynamic modeling and the incremental leveling mechanism for KG updating. Verified by comprehensive and intensive experiments, InLN outperforms nine baseline models in three tasks by substantial margins, reaching up to a 9.9% improvement and averaging a 5.7% increase.

The popularity of decentralized finance has drawn attention to liquidity mining (LM). In LM, a user deposits her cryptocurrencies into liquidity pools to provide liquidity for exchanges and earn yields. Different liquidity pools offer varying yields and require different pairs of cryptocurrencies. A user can exchange a cryptocurrency for another with some exchange costs. Thus, an LM solution consists of exchange transactions and deposit transactions, guaranteeing (1) each exchange transaction must exchange one cryptocurrency for another at a specific rate (i.e., the exchange constraint); (2) the amounts of cryptocurrencies deposited in a liquidity pool must exceed the required threshold (i.e., the minimum constraint); (3) each deposit transaction must deposit a specific pair of cryptocurrencies at a certain rate in a liquidity pool (i.e., the deposit constraint); and (4) the cryptocurrencies used in the solution do not exceed the cryptocurrencies that the user has (i.e., the budget constraint). Selecting the most profitable LM solution is challenging due to the vast number of candidate solutions. To address this challenge, we define the yield maximization liquidity mining (YMLM) problem. Given a set of liquidity pools, a set of the user's cryptocurrencies, a set of exchange rates, and an evaluation function, YMLM aims to find an LM solution with maximal yields, satisfying the minimum, exchange, deposit, and budget constraints. We prove that YMLM is NP-hard and cannot be solved by algorithms with constant approximation ratios. To tackle YMLM, we propose two algorithms, namely YMLM\_GD and YMLM\_SK, with parameterized approximation ratios. Extensive experiments on both real and synthetic datasets show that our approaches outperform the baselines in yields.

Recently, emergence has received widespread attention from the research community along with the success of large-scale models.Different from the literature, we hypothesize a key factor that promotes the performance during the increase of scale: the reduction of monosemantic neurons that can only form one-to-one correlations with specific features.Monosemantic neurons tend to be sparser and have negative impacts on the performance in large models.Inspired by this insight, we propose an intuitive idea to identify monosemantic neurons and inhibit them.However, achieving this goal is a non-trivial task as there is no unified quantitative evaluation metric and simply banning monosemantic neurons does not promote polysemanticity in neural networks.Therefore, we first propose a new metric to measure the monosemanticity of neurons with the guarantee of efficiency for online computation, then introduce a theoretically supported method to suppress monosemantic neurons and proactively promote the ratios of polysemantic neurons in training neural networks.We validate our conjecture that monosemanticity brings about performance change at different model scales on a variety of neural networks and benchmark datasets in different areas, including language, image, and physics simulation tasks.Further experiments validate our analysis and theory regarding the inhibition of monosemanticity.

Sparse operators, i.e., operators that take sparse tensors as input, are of great importance in deep learning models. Due to the diverse sparsity patterns in different sparse tensors, it is challenging to optimize sparse operators by seeking an optimal sparse format, i.e., leading to the lowest operator latency. Existing works propose to decompose a sparse tensor into several parts and search for a hybrid of sparse formats to handle diverse sparse patterns. However, they often make a trade-off between search space and search time: their search spaces are limited in some cases, resulting in limited operator running efficiency they can achieve. In this paper, we try to extend the search space in its breadth (by doing flexible sparse tensor transformations) and depth (by enabling multi-level decomposition). We formally define the multi-level sparse format decomposition problem, which is NP-hard, and we propose a framework STile for it. To search efficiently, a greedy algorithm is used, which is guided by a cost model about the latency of computing a sub-task of the original operator after decomposing the sparse tensor. Experiments of two common kinds of sparse operators, SpMM and SDDMM, are conducted on various sparsity patterns, and we achieve 2.1-18.0× speedup against cuSPARSE on SpMMs and 1.5 - 6.9× speedup against DGL on SDDMM. The search time is less than one hour for any tested sparse operator, which can be amortized.

Dynamic graphs are essential in real-world scenarios like social media and e-commerce for tasks such as predicting links and classifying nodes. Temporal Graph Neural Networks (T-GNNs) stand out as a prime solution for managing dynamic graphs, employing temporal message passing to compute node embeddings at specific timestamps. Nonetheless, the high CPU-GPU data loading overhead has become the bottleneck for efficient training of T-GNNs over large-scale dynamic graphs. In this work, we present SIMPLE, a versatile system designed to address the major efficiency bottleneck in training existing T-GNNs on a large scale. It incorporates a dynamic data placement mechanism, which maintains a small buffer space in available GPU memory and dynamically manages its content during T-GNN training. SIMPLE is also empowered by systematic optimizations towards data processing flow. We compare SIMPLE to the state-of-the-art generic T-GNN training system TGL on four large-scale dynamic graphs with different underlying T-GNN models. Extensive experimental results show that SIMPLE effectively cuts down 80.5% ~ 96.8% data loading cost, and accelerates T-GNN training by 1.8× ~ 3.8× (2.6× on average) compared to TGL.

Dynamic graphs play a crucial role in various real-world applications, such as link prediction and node classification on social media and e-commerce platforms. Temporal Graph Neural Networks (T-GNNs) have emerged as a leading approach for handling dynamic graphs, using temporal message passing to compute temporal node embeddings. However, training existing T-GNNs on large-scale dynamic graphs is prohibitively expensive due to the ill-suited batching scheme and significant data access overhead. In this paper, we introduce ETC, a generic framework designed specifically for efficient T-GNN training at scale. ETC incorporates a novel data batching scheme that enables large training batches improving model computation efficiency, while preserving model effectiveness by restricting information loss in each training batch. To reduce data access overhead, ETC employs a three-step data access policy that leverages the data access pattern in T-GNN training, significantly reducing redundant data access volume. Additionally, ETC utilizes an inter-batch pipeline mechanism, decoupling data access from model computation and further reducing data access costs. Extensive experimental results demonstrate the effectiveness of ETC, showcasing its ability to achieve significant training speedups compared to state-of-the-art training frameworks for T-GNNs on real-world dynamic graphs with millions of interactions. ETC provides a training speedup ranging from 1.6X to 62.4X, highlighting its potential for efficient training on large-scale dynamic graphs.

One of the most important challenges in shared mobility services ( e.g. , ride-sharing and parcel delivery) is planning routes for workers by considering real road conditions. To tackle this challenge, the "insertion operator", which computes the optimal route for the worker to serve ( i.e. , insert) the newly appeared delivery request, has been acted as the fundamental operation in existing solutions. However, existing works implicitly assume a static road network, hence are hard to fulfill the real-world scenario, where travel time between two locations is not constant at different times of a day. By contrast, we focus on the insertion operator over time-dependent road networks that capture the periodic pattern of road conditions. We also show that the time complexity of existing solutions would degrade into cubic time and hence such solutions can no longer satisfy the real-time requirement under this real-world setting. To satisfy the need for real-time computation, we propose a data summary to model the time-dependent travel time functions between pairs of vertices in the route. Based on the data summary, we design an efficient solution that can enumerate the best insertion position in linear time while satisfying complex spatiotemporal constraints. Finally, extensive experiments are conducted on real datasets from several applications of shared mobility. The results show that our solution is up to 44.5X faster than the state-of-the-art solution.

Graph neural networks (GNNs) have achieved great success on various graph tasks. However, recent studies have revealed that GNNs are vulnerable to injective attacks. Due to the openness of platforms, attackers can inject malicious nodes with carefully designed edges and node features, making GNNs misclassify the labels of target nodes. To resist such adversarial attacks, recent researchers propose GNN defenders. They assume that the attack patterns have been known, e.g., attackers tend to add edges between dissimilar nodes. Then, they remove edges between dissimilar nodes from attacked graphs, aiming to alleviate the negative impact of adversarial attacks. Nevertheless, on dynamic graphs, attackers can change their attack strategies at different times, making existing passive GNN defenders that are passively designed for specific attack patterns fail to resist attacks. In this paper, we propose a novel active GNN defender for dynamic graphs, namely ADGNN, which actively injects guardian nodes to protect target nodes from effective attacks. Specifically, we first formulate an active defense objective to design guardian node behaviors. This objective targets to disrupt the prediction of attackers and protect easily attacked nodes, thereby preventing attackers from generating effective attacks. Then, we propose a gradient-based algorithm with two acceleration techniques to optimize this objective. Extensive experiments on four real-world graph datasets demonstrate the effectiveness of our proposed defender and its capacity to enhance existing GNN defenders.

Graph neural networks (GNNs) have been gaining a reputation for effective modeling of graph data. Yet, it is challenging to train GNNs efficiently. Many frameworks have been proposed but most of them suffer from high batch preparation cost and data transfer cost for mini-batch training. In addition, existing works have limitations on the device utilization pattern, which results in fewer opportunities for pipeline parallelism. In this paper, we present DAHA, a GNN training framework with data and hardware aware execution planning to accelerate end-to-end GNN training. We first propose a data and hardware aware cost model that is lightweight and gives accurate estimates on per-operation time cost for arbitrary input and hardware settings. Based on the cost model, we further explore the optimal execution plan for the data and hardware with three optimization strategies with pipeline parallelism: (1) group-based in-turn pipelining of batch preparation neural training to explore more optimization opportunities and prevent batch preparation bottlenecks; (2) data and hardware aware rewriting for intra-batch execution planning to improve computation efficiency and create more opportunities for pipeline parallelism; and (3) inter-batch scheduling to further boost the training efficiency. Extensive experiments demonstrate that DAHA can consistently and significantly accelerate end-to-end GNN training and generalize to different message-passing GNN models.

Coin mixing methods are widely used to enhance anonymity in cryptocurrency transactions by obfuscating the linkages between recipients and senders. Specifically, coin mixing methods combine several users' transactions into a CoinJoin transaction and decompose the original transactions' outputs into a set of decomposed outputs with similar amounts. However, existing methods have two shortcomings. Firstly, CoinJoin transactions lack anonymity guarantees. Secondly, the number of decomposed outputs is not minimized. To tackle these two shortcomings, we develop a platform named CMixing for mixing transactions with anonymity guarantees and minimal fees. For a CoinJoin transaction obtained by CMixing, the probability of adversaries correctly guessing the original output of a decomposed output does not exceed c , where c is a privacy requirement. Thus, the first shortcoming is solved. Additionally, CMixing uses an approximation algorithm to decompose original outputs, which approximately minimizes the number of decomposed outputs. Thus, the second shortcoming is solved. Our demonstration will showcase how users can use CMixing to make CoinJoin transactions. We will also show the fees saved and the level of anonymity achieved using our algorithm.

Graph Neural Networks (GNNs) have gained significant popularity for learning representations of graph-structured data. Mainstream GNNs employ the message passing scheme that iteratively propagates information between connected nodes through edges. However, this scheme incurs high training costs, hindering the applicability of GNNs on large graphs. Recently, the database community has extensively researched effective solutions to facilitate efficient GNN training on massive graphs. In this tutorial, we provide a comprehensive overview of the GNN training process based on the graph data lifecycle, covering graph preprocessing, batch generation, data transfer, and model training stages. We discuss recent data management efforts aiming at accelerating individual stages or improving the overall training efficiency. Recognizing the distinct training issues associated with static and dynamic graphs, we first focus on efficient GNN training on static graphs, followed by an exploration of training GNNs on dynamic graphs. Finally, we suggest some potential research directions in this area. We believe this tutorial is valuable for researchers and practitioners to understand the bottleneck of GNN training and the advanced data management techniques to accelerate the training of different GNNs on massive graphs in diverse hardware settings.

Graph embedding aims at mapping each node to a low-dimensional vector, beneficial for various applications like pattern matching, retrieval augmented generation and recommendation. In this paper, we study the large-scale temporal graph embedding problem. Different from simple graphs, each edge has a timestamp in temporal graphs, which requires the embeddings to encode the temporal biases. Factorizing similarity matrix is a common approach for generating simple graph embeddings where similarity can be well characterized by some conventional metrics like personalized PageRank. However, how to construct a similarity that can encode interactions with temporal biases is a critical problem for large scale temporal graphs. To address this, we introduce the concept of temporal-based bipartite graph (TBG) and develop the temporal preferential attachment similarity (TPASim) that reflects concurrent node activity over time. Directly factorizing the TPASim matrix, which contains nearly n 2 non-zeros, is not feasible for large graphs with n nodes. Instead, we present LTGE, which constructs and factorizes a temporal matrix with at most 2 m non-zeros, where m is the number of edges. Our theoretical analysis shows that LTGE achieves the same embeddings as factorizing the TPASim matrix but significantly reduces complexity by a factor of n 2 / m. On the other hand, when graphs evolve over time, to avoid recomputing, we further propose LTGEInc that utilizes a novel incremental singular value decomposition (SVD) algorithm with provable guarantee for updating the embeddings. Extensive experiments on several datasets with up to 17 million nodes and 1.3 billion edges demonstrate that LTGE outperforms the state of the art significantly and is orders of magnitude faster than the baselines specially designed for temporal graphs. For embeddings update, LTGEInc retains the performance with small computational overhead.

Large language models (LLMs) demonstrate an impressive ability to internalize knowledge and answer natural language questions. Although previous studies validate that LLMs perform well on general knowledge while presenting poor performance on long-tail nuanced knowledge, the community is still doubtful about whether the traditional knowledge graphs should be replaced by LLMs. In this paper, we askif the schema of knowledge graph (i.e., taxonomy) is made obsolete by LLMs.Intuitively, LLMs should perform well on common taxonomies and at taxonomy levels that are common to people. Unfortunately, there lacks a comprehensive benchmark that evaluates the LLMs over a wide range of taxonomies from common to specialized domains and at levels from root to leaf so that we can draw a confident conclusion. To narrow the research gap, we constructed a novel taxonomy hierarchical structure discovery benchmark named TaxoGlimpse to evaluate the performance of LLMs over taxonomies. TaxoGlimpse covers ten representative taxonomies from common to specialized domains with in-depth experiments of different levels of entities in this taxonomy from root to leaf. Our comprehensive experiments of eighteen LLMs under three prompting settings validate that LLMs perform miserably poorly in handling specialized taxonomies and leaf-level entities. Specifically, the QA accuracy of the best LLM drops by up to 30% as we go from common to specialized domains and from root to leaf levels of taxonomies.

Many real-world binary relations can be modelled as bipartite graphs, which can be inherently temporal and each edge is associated with a timestamp. The ( α, β )-core, a popular structure that requires minimum degrees over two layers of vertices, is useful for understanding the organisation of bipartite networks. However, the temporal property has rarely been considered in cohesive subgraph mining in bipartite graphs. This gap prevents the finding of time-sensitive ( α, β )-cores in real-world applications. In this paper, we aim at finding ( α, β )-cores within any time window over a temporal bipartite graph. To address this problem, we propose a novel DAG (Directed Acyclic Graph)-like hierarchy with qualified time windows to describe the temporal containment property of the ( α, β )-core. Furthermore, we construct the superior-optimized index which significantly optimizes space complexity and guarantees efficient query performance. We also propose a maintenance approach that can efficiently update the index by removing stale information and incorporating newly inserted temporal edges. Extensive experiments are conducted on eight real-world graphs and the results show the effectiveness and efficiency of our indexes.

We introduce Galaxybase, a native distributed graph database that addresses the increasing demands for processing large volumes of graph data in diverse industries like finance, manufacturing, and government. Designed to handle the requirements of both transactional and analytical workloads, Galaxybase stands out with its novel data storage and transaction mechanisms. At its core, Galaxybase utilizes a Log-Structured Adjacency List coupled with an Edge Page structure, optimizing read-write operations across a spectrum of tasks such as graph traversals and single edge queries. A notable aspect of Galaxybase is its execution of custom distributed transaction modes tailored for HTAP transactions, allowing for the facilitation of bidirectional and interactive transactions. It ensures data integrity and minimal latency while enabling simultaneous processing of OLTP and OLAP workloads without blocking. Experimental results show that Galaxybase achieves high throughput and low latency in both OLTP and OLAP workloads, across various graph query scenarios and resource conditions. Galaxybase has been deployed in leading banks, education, telecommunication and energy sectors in China, consistently maintaining robust performance for HTAP workloads over the years.

With the popularity of video/audio streaming applications in recent years, the wide spread of Autonomous Sensory Meridian Response (ASMR) erotica content is becoming a serious issue in social networks. Due to the subtle nature of ASMR erotica and its relative rareness in real scenario, detecting ASMR erotica contents is a challenging task. In this article, we propose a novel neural framework for ASMR erotica content moderation. The proposed framework consists of a pipeline of novel strategies to tackle challenges unique in ASMR Erotica Contents such as data scarcity and imbalanced data. Based on large-scale industrial data, the proposed framework demonstrates high moderation accuracy in quantitative analysis and significantly outperforming the existing counterparts.

Recently, transportation-as-a-service (TaaS) becomes an increasing trend, and online taxi platforms start to apply electric vehicles to serve passengers. Since the recharging time of an electric vehicle is long and non-negligible, it is necessary to smartly arrange the recharging schedules of electric vehicles in working schedules. In order to maximize the number of served taxi-calling tasks, online taxi platforms assign electric vehicles whose remaining electric power is enough to serve the dynamically arriving taxi-calling tasks and schedule suitable idle vehicles to recharging piles to recharge. We formally define the power-aware electric vehicle assignment (PAEVA) problem to serve as many taxi-calling tasks as possible under the constraints of remaining electric power and deadline. We prove that the PAEVA problem is NP-hard. To solve PAEVA, we design a novel strategy to help arrange the schedules of electric vehicles. Specifically, the strategy requires that, in a time slot and an area gird, the ratio of the number of electric vehicles whose remaining electric power is higher than a threshold$\alpha$to the number of predicted taxi-calling tasks should be higher than a threshold$\beta$. We propose two approximation approaches with theoretical guarantees to adaptively determine the values of the two thresholds of the strategy. We evaluate our solutions’ effectiveness and efficiency by comprehensive experiments on real datasets.

Sequential recommendations have received great attention in recent years due to their wide application in e-commerce, trip planning, and online education. Contexts reveal the intention of a user in a transaction such as consuming or purchasing an item, and highly affect her behaviour. However, existing techniques cannot fully capture the context-sensitive and dynamic sequential user behaviours for effective and efficient sequential recommendation. To address this limitation, we propose a novel Dynamic Bi-layer Graph learning (DBIG)-based framework for sequential recommendation, which learns the sequence dynamics of user behaviours and contexts. Specifically, we first propose a context graph to identify the relevant contexts to a target user. Then, we propose a transaction context graph that predicts the probability of a transaction happening under certain contexts. In addition, we apply BERT (Bidirectional Encoder Representations from Transformers) to our graph embedding for understanding the user sequential behaviours in bidirectional ways and generating recommendations. Finally, we propose a cluster-structure-based algorithm, which incrementally maintains the DBIG model and BERT over dynamic transaction updates. We evaluate our DBIG-based framework by conducting extensive experiments over five public datasets. The quantitative results demonstrate the superiority of our approach in terms of effectiveness and efficiency.

With the upsurge of online banking, mobile payment, and virtual currency, new money-laundering crimes easily conceal in the enormous transaction volume. The traditional rule-based methods with large amounts of alerting thresholds are already incapable of handling the fast-changing transaction networks. Recently, the DL models represented by the graph neural networks (GNNs) show the potential to capture money-laundering modes with high accuracy. However, most related works are still far from practical deployment in the industry. Based on our practice at WeBank, there are three major challenges: Firstly, supervised learning is infeasible facing the extraordinarily large-scale but imbalanced data, with hundreds of millions of active accounts but only thousands of anomalies. Secondly, the real-world transactions form a sparse network with millions of isolated user groups, which overflows the expressive ability of current node-level GNNs. Thirdly, the explanation for each suspicious account is mandatory by the government for double check, which conflicts with the black-box nature of most DL models. Therefore, we proposed Diga, the first work to apply the diffusion probabilistic model to a graph anomaly detection problem with three novel techniques: the biased K-hop PageRank, the semi-supervised guided diffusion and the novel weight-sharing GNN layer. The effectiveness and efficiency of Diga are verified via intensive experiments on both industrial and public datasets.

Recently, the message passing neural network (MPNN) has attracted a lot of attention, which learns node representations based on the receptive field of the given node. Despite its success in many graph-related tasks, recent studies find that conventional MPNNs are incapable of handling variant receptive fields required in different graphs, and thereby some upgraded MPNNs have been developed. However, these methods are limited to designing a common solution for different graphs, which fails to capture the impact of different graph properties on the receptive fields. To alleviate such issues, we propose a novel MPNN space for data-dependent receptive fields (MpnnDRF), which enables us to dynamically design suitable MPNNs to capture the receptive field for the given graph. More concretely, we systemically investigate the capability of existing designs and propose several key design dimensions to improve them. Then, to fully explore the proposed designs and useful designs in existing works, we propose a novel search space to incorporate them and formulate a search framework. In the empirical study, the proposed MpnnDRF shows very strong robustness against the increased receptive field, which allows MpnnDRF to learn node representations based on a larger perceptual field. Therefore, MpnnDRF consistently achieves outstanding performance on benchmark node and graph classification tasks.

Graph neural networks (GNNs) have been widely studied for modeling graph-structured data. Thanks to the over-parameterization and large receptive field of deep GNNs, "deep" is a promising direction to develop GNNs further and has shown some superior performances. However, the over-stacked structures of deep architectures incur high inference cost in deployment. To compress deep GNNs, we can use knowledge distillation (KD) to make shallow student GNNs mimic teacher GNNs. Existing KD methods in graph domain focus on constructing diverse supervision on embedding or prediction produced by student GNNs, but overlook the gap of the receptive field (i.e., input information) between student and teacher, which brings difficulties to KD. We call this gap "input mismatch". To alleviate this problem, we propose a lightweight stochastic extended module to provide an estimation for missing input information for student GNNs. The estimator models the distribution of missing information. Specifically, we model the missing information as an independent distribution from graph level and a conditional distribution from node level (given the condition of observable input). These two estimates are optimized using a Bayesian methodology and combined into a balanced estimate as additional input to student GNNs. To the best of our knowledge, we are the first to address the "input mismatch" problem in deep GNNs distillation. Experiments on extensive benchmarks demonstrate that our method outperforms existing KD methods for GNNs in distillation performance, which confirms that the estimations are reasonable and effective.

Learning fair and transferable representations of users that can be used for a wide spectrum of downstream tasks (specifically, machine learning models) has great potential in fairness-aware Web services. Existing studies focus on debiasing w.r.t. a small scale of (one or a handful of) fixed pre-defined sensitive attributes. However, in real practice, downstream data users can be interested in various protected groups and these are usually not known as prior. This requires the learned representations to be fair w.r.t. all possible sensitive attributes. We name this task universal fair representation learning, in which an exponential number of sensitive attributes need to be dealt with, bringing the challenges of unreasonable computational cost and un-guaranteed fairness constraints. To address these problems, we propose a controllable universal fair representation learning (CUFRL) method. An effective bound is first derived via the lens of mutual information to guarantee parity of the universal set of sensitive attributes while maintaining the accuracy of downstream tasks. We also theoretically establish that the number of sensitive attributes that need to be processed can be reduced from exponential to linear. Experiments on two public real-world datasets demonstrate CUFRL can achieve significantly better accuracy-fairness trade-off compared with baseline approaches.

Recently, many promising embedding models have been proposed to embed knowledge graphs (KGs) and their more general forms, such as n-ary relational data (NRD) and hyper-relational KG (HKG). To promote the data adaptability and performance of embedding models, KG searching methods propose to search for suitable models for a given KG data set. But they are restricted to a single KG form, and the searched models are restricted to a single type of embedding model. To tackle such issues, we propose to build a search space for the message function in graph neural networks (GNNs). However, it is a non-trivial task. Existing message function designs fix the structures and operators, which makes them difficult to handle different KG forms and data sets. Therefore, we first design a novel message function space, which enables both structures and operators to be searched for the given KG form (including KG, NRD, and HKG) and data. The proposed space can flexibly take different KG forms as inputs and is expressive to search for different types of embedding models. Especially, some existing message function designs and some classic KG embedding models can be instantiated as special cases of our space. We empirically show that the searched message functions are data-dependent, and can achieve leading performance on benchmark KGs, NRD, and HKGs.

Graph neural networks have been widely used to learn node representations for many real-world static graphs. In general, they learn node representations by recursively aggregating information from neighbors. However, graphs in many applications are dynamic, evolving with continuous graph events, such as node feature and graph structure updates. These events require the node representations to be updated accordingly. Currently, due to the real-time requirement, how to efficiently and reliably update node representations under continuous graph events is still an open problem. Recent studies propose two solutions to partially address this problem, but their performance is still limited. First, local-based GNNs only update the nodes directly involved in events, suffering from the quality-deficit issue, since they neglect the other nodes affected by these events. Second, neighbor-sampling GNNs propose to sample neighbors to accelerate neighbor aggregation computations, encountering the neighbor-redundant issue. These sampled neighbors may be similar and cannot reflect the distribution of all neighbors, leading that node representations aggregated on these redundant neighbors may differ from those aggregated on all neighbors. In this paper, we propose an efficient and reliable graph neural network, namely EARLY, to update node representations for dynamic graphs. We first identify the top-k influential nodes that are most affected by graph events. Then, to sample neighbors diversely, we propose a diversity-aware layer-wise sampling technique. We theoretically demonstrate that this technique can decrease the sampling expectation error and learn more reliable node representations. Therefore, the top-k nodes selection and diversity-aware sampling enable EARLY to efficiently update node representations in a reliable way. Extensive experiments on the five real-world graphs demonstrate the effectiveness and efficiency of our proposed EARLY.

The acquisition of accurate rainfall distribution in space is an important task in hydrological analysis and natural disaster pre-warning. However, it is impossible to install rain gauges on every corner. Spatial interpolation is a common way to infer rainfall distribution based on available raingauge data. However, the existing works rely on some unrealistic pre-settings to capture spatial correlations, which limits their performance in real scenarios. To tackle this issue, we propose the SSIN, which is a novel data-driven self-supervised learning framework for rainfall spatial interpolation by mining latent spatial patterns from historical observation data. Inspired by the Cloze task and BERT, we fully consider the characteristics of spatial interpolation and design the SpaFormer model based on the Transformer architecture as the core of SSIN. Our main idea is: by constructing rich self-supervision signals via random masking, SpaFormer can learn informative embeddings for raw data and then adaptively model spatial correlations based on rainfall spatial context. Extensive experiments on two real-world raingauge datasets show that our method outperforms the state-of-the-art solutions. In addition, we take traffic spatial interpolation as another use case to further explore the performance of our method, and SpaFormer achieves the best performance on one large real-world traffic dataset, which further confirms the effectiveness and generality of our method.

Representation learning over dynamic graphs is critical for many real-world applications such as social network services and recommender systems. Temporal graph neural networks (T-GNNs) are powerful representation learning methods and have achieved remarkable effectiveness on continuous-time dynamic graphs. However, T-GNNs still suffer from high time complexity, which increases linearly with the number of timestamps and grows exponentially with the model depth, causing them not scalable to large dynamic graphs. To address the limitations, we propose Orca, a novel framework that accelerates T-GNN training by non-trivially caching and reusing intermediate embeddings. We design an optimal cache replacement algorithm, named MRU, under a practical cache limit. MRU not only improves the efficiency of training T-GNNs by maximizing the number of cache hits but also reduces the approximation errors by avoiding keeping and reusing extremely stale embeddings. Meanwhile, we develop profound theoretical analyses of the approximation error introduced by our reuse schemes and offer rigorous convergence guarantees. Extensive experiments have validated that Orca can obtain two orders of magnitude speedup over the state-of-the-art baselines while achieving higher precision on large dynamic graphs.

Recently, incremental learning has attracted a lot of interest in both research communities and industries. Generally, given a series of data sets sequentially, it tries to achieve good performance on the new data set while maintaining not bad performance on the old ones. Despite the recent success of incremental learning, existing works mainly assume that the coming data set is from the feature space of old ones, i.e., homogeneous feature space. And they adopt one feature extractor to forcibly project different feature spaces into one space. However, this assumption is hard to hold in real-world scenarios. Especially, the attributes of tables may sequentially increase in tabular learning. Thus, classic incremental learning models may hinder their effectiveness. In this paper, we propose a new method, incremental tabular learning on heterogeneous feature space (ILEAHE) to solve this issue. We first propose the ideas that feature extractors should be decomposed into shared and specific extractors to process the shared and specific features across different data sets respectively. Then, we propose a novel measurement named discriminative ability to measure specific extractors. Thus, two kinds of extractors can be discriminated and the specific extractor will more focus on those domain-specific features. We further demonstrate the effectiveness of ILEAHE through empirical studies.

Similarity search is getting increasingly useful in real applications. This paper focuses on the in-memory similarity search, i.e., the range query and k nearest neighbor (kNN) query, under arbitrary metric spaces, where the only known information is the distance function to measure the similarity between two objects. Although lots of research has studied this problem, the query efficiency of existing solutions is still unsatisfactory. To further improve the query efficiency, we are inspired by the tree embeddings, which map each object into a unique leaf of a well-structured tree solely based on the distances. Unlike existing embedding techniques (e.g., Lipschitz embeddings and pivot mapping) for similarity search, where an extra multi-dimensional index is needed to index the embedding space (e.g., Lp metrics), we directly use this tree to answer similarity search. This seems to be promising, but it is challenging to tailor tree embeddings for efficient similarity search. Specifically, we present a novel index called LiteHST, which is based on the most popular tree embedding (HST) and heavily customized for similarity search in the node structure and storage scheme. We propose a new construction algorithm with lower time complexity than existing methods and prove the optimality of LiteHST in the distance bound. Based on this new index, we also design optimization techniques that heavily reduce the number of distance computations and hence save running time. Finally, extensive experiments demonstrate that our solution outperforms the state-of-the-art in the query efficiency by a large margin.

Recently Graph Neural Networks (GNNs) have achieved great success in many applications. The mini-batch training has become the de-facto way to train GNNs on giant graphs. However, the mini-batch generation task is extremely expensive which slows down the whole training process. Researchers have proposed several solutions to accelerate the mini-batch generation, however, they (1) fail to exploit the locality of the adjacency matrix, (2) cannot fully utilize the GPU memory, and (3) suffer from the poor adaptability to diverse workloads. In this work, we propose DUCATI, aDual-Cache system to overcome these drawbacks. In addition to the traditionalNfeat-Cache, DUCATI introduces a newAdj-Cache to further accelerate the mini-batch generation and better utilize GPU memory. DUCATI develops a workload-awareDual-Cache Allocator which adaptively finds the best cache allocation plan under different settings. We compare DUCATI with various GNN training systems on four billion-scale graphs under diverse workload settings. The experimental results show that in terms of training time, DUCATI can achieve up to 3.33 times speedup (2.07 times on average) compared to DGL and up to 1.54 times speedup (1.32 times on average) compared to the state-of-the-artSingle-Cache systems. We also analyze the time-accuracy trade-offs of DUCATI and four state-of-the-art GNN training systems. The analysis results offer users some guidelines on system selection regarding different input sizes and hardware resources.

Signed bipartite graphs represent relationships between two sets of entities, including both positive and negative interactions, allowing for a more comprehensive modeling of real-world networks. In this work, we focus on the detection of cohesive subgraphs in signed bipartite graphs by leveraging the concept of balanced butterflies. A balanced butterfly is a cycle of length 4 that is considered stable if it contains an even number of negative edges. We propose a novel model called the balanced ( k , ϵ)-bitruss, which provides a concise representation of cohesive signed bipartite subgraphs while enabling control over density ( k ) and balance (ϵ). We prove that finding the largest balanced ( k , ϵ)-bitruss is NP-hard and cannot be efficiently approximated to a significant extent. Furthermore, we extend the unsigned butterfly counting framework to efficiently compute both balanced and unbalanced butterflies. Based on this technique, we develop two greedy heuristic algorithms: one that prioritizes followers and another that focuses on balanced support ratios. Experimental results demonstrate that the greedy approach based on balanced support ratios outperforms the follower-based approach in terms of both efficiency and effectiveness.

Subgraph matching is a fundamental problem in graph theory and has wide applications in areas like sociology, chemistry, and social networks. Due to its NP-hardness, the basic approach is a brute-force search over the whole search space. Some pruning strategies have been proposed to reduce the search space. However, they are either space-inefficient or based on assumptions that the graph has specific properties. In this paper, we propose SUFF, a general and powerful structure filtering framework, which can accelerate most of the existing approaches with slight modifications. Specifically, it builds a set of filters using matching results of past queries, and uses them to prune the search space for future queries. By fully utilizing the relationship between matches of two queries, it ensures that such pruning is sound. Furthermore, several optimizations are proposed to reduce the computation and space cost for building, storing, and using filters. Extensive experiments are conducted on multiple real-world data sets and representative existing approaches. The results show that SUFF can achieve up to 15X speedup with small overheads.

Similar subtrajectory search is a finer-grained operator that can better capture the similarities between one query trajectory and a portion of a data trajectory than the traditional similar trajectory search, which requires that the two checking trajectories are similar in their entirety. Many real applications (e.g., trajectory clustering and trajectory join) utilize similar subtrajectory search as a basic operator. It is considered that the time complexity is O ( mn 2 ) for exact algorithms to solve the similar subtrajectory search problem under most trajectory distance functions in the existing studies, where m is the length of the query trajectory and n is the length of the data trajectory. In this paper, to the best of our knowledge, we are the first to propose an exact algorithm to solve the similar subtrajectory search problem in O ( mn ) time for most of widely used trajectory distance functions (e.g., WED, DTW, ERP, EDR and Frechet distance). Through extensive experiments on three real datasets, we demonstrate the efficiency and effectiveness of our proposed algorithms.

Temporal graph neural networks (T-GNNs) are state-of-the-art methods for learning representations over dynamic graphs. Despite the superior performance, T-GNNs still suffer from high computational complexity caused by the tedious recursive temporal message passing scheme, which hinders their applicability to large dynamic graphs. To address the problem, we build the theoretical connection between the temporal message passing scheme adopted by T-GNNs and the temporal random walk process on dynamic graphs. Our theoretical analysis indicates that it would be possible to select a few influential temporal neighbors to compute a target node's representation without compromising the predictive performance. Based on this finding, we propose to utilize T-PPR, a parameterized metric for estimating the influence score of nodes on evolving graphs. We further develop an efficient single-scan algorithm to answer the top- k T-PPR query with rigorous approximation guarantees. Finally, we present Zebra, a scalable framework that accelerates the computation of T-GNN by directly aggregating the features of the most prominent temporal neighbors returned by the top- k T-PPR query. Extensive experiments have validated that Zebra can be up to two orders of magnitude faster than the state-of-the-art T-GNNs while attaining better performance.

Graph Neural Networks (GNNs) have significantly boosted the performance of many graph-based applications, yet they serve as black-box models. To understand how GNNs make decisions, explainability techniques have been extensively studied. While the majority of existing methods focus on local explainability, we propose DAG-Explainer in this work aiming for global explainability. Specifically, we observe three properties of superior explanations for a pretrained GNN: they should be highly recognized by the model, compliant with the data distribution and discriminative among all the classes. The first property entails an explanation to be faithful to the model, as the other two require the explanation to be convincing regarding the data distribution. Guided by these properties, we design metrics to quantify the quality of each single explanation and formulate the problem of finding data-aware global explanations for a pretrained GNN as an optimizing problem. We prove that the problem is NP-hard and adopt a randomized greedy algorithm to find a near optimal solution. Furthermore, we derive an improved bound of the approximation algorithm in our problem over the state-of-the-art (SOTA) best. Experimental results show that DAG-Explainer can efficiently produce meaningful and trustworthy explanations while preserving comparable quantitative evaluation results to the SOTA methods.

Deep graph networks (DGNs) have demonstrated their outstanding effectiveness on both heterogeneous and homogeneous graphs. However their black-box nature does not allow human users to understand their working mechanisms. Recently, extensive efforts have been devoted to explaining DGNs' prediction, yet heterogeneity-agnostic multi-level explainability is still less explored. Since the two types of graphs are both irreplaceable in real-life applications, having a more general and end-to-end explainer becomes a natural and inevitable choice. In the meantime, feature-level explanation is often ignored by existing techniques, while topological-level explanation alone can be incomplete and deceptive. Thus, we propose a heterogeneity-agnostic multi-level explainer in this paper, named HENCE-X, which is a causality-guided method that can capture the non-linear dependencies of model behavior on the input using conditional probabilities. We theoretically prove that HENCE-X is guaranteed to find the Markov blanket of the explained prediction, meaning that all information that the prediction is dependent on is identified. Experiments on three real-world datasets show that HENCE-X outperforms state-of-the-art (SOTA) methods in generating faithful factual and counterfactual explanations of DGNs.

The payment channel network (PCN) is a promising solution to increase the throughput of blockchains. However, unidirectional transactions can deplete a user's deposits in a payment channel (PC), reducing the success ratio of transactions (SRoT). To address this depletion issue, rebalance protocols are used to shift tokens from well-deposited PCs to under-deposited PCs. To improve SRoT, it is beneficial to increase the balance of a PC with a lower balance and a higher weight (i.e., more transaction executions rely on the PC). In this paper, we define the utility of a transaction and the utility-aware rebalance (UAR) problem. The utility of a transaction is proportional to the weight of the PC and the amount of the transaction, and inversely proportional to the balance of the receiver. To maximize the effect of improving SRoT, UAR aims to find a set of transactions with maximized utilities, satisfying the budget and conservation constraints. The budget constraint limits the number of tokens shifted in a PC. The conservation constraint requires that the number of tokens each user sends equals the number of tokens received. We prove that UAR is NP-hard and cannot be approximately solved with a constant ratio. Thus, we propose two heuristic algorithms, namely Circuit Greedy and UAR_DC. Extensive experiments show that our approaches outperform the existing approach by at least 3.16 times in terms of utilities.

Recently, more and more higher education institutions have been using student feedback questionnaires (SFQ) to evaluate teaching. However, existing SFQ systems have two shortcomings. The first is that the respondent of an SFQ is not anonymous. The second is that the statistical report of SFQs can be manipulated. To tackle these two shortcomings, we develop a novel SFQ system, namely PSFQ. In PSFQ, the respondent of an SFQ is mixed with multiple users by a ring signature. PSFQ uses an advanced ring signature approach to minimize the size of a ring signature when anonymity satisfies the requirements. Thus, the first shortcoming has been overcome. Moreover, all answers are encrypted by homomorphic encryption and stored on the blockchain, enabling users to verify the correctness of the statistical reports. Our demonstration will showcase how PSFQ provides confidential SFQ responses while ensuring the correctness of statistical reports.

Understanding the semantics of tabular data is of great importance in various downstream applications, such as schema matching, data cleaning, and data integration. Column semantic type annotation is a critical task in the semantic understanding of tabular data. Despite the fact that various approaches have been proposed, they are challenged by the difficulties of handling wide tables and incorporating complex inter-table context information. Failure to handle wide tables limits the usage of column type annotation approaches, while failure to incorporate inter-table context harms the annotation quality. Existing methods either completely ignore these problems or propose ad-hoc solutions. In this paper, we propose Related tables Enhanced Column semantic type Annotation framework (RECA), which incorporates inter-table context information by finding and aligning schema-similar and topic-relevant tables based on a novel named entity schema. The design of RECA can naturally handle wide tables and incorporate useful inter-table context information to enhance the annotation quality. We conduct extensive experiments on two web table datasets to comprehensively evaluate the performance of RECA. Our results show that RECA achieves support-weighted F1 scores of 0.853 and 0.937 with macro average F1 scores of 0.674 and 0.783 on the two datasets respectively, which outperform the state-of-the-art methods.

Community search (CS) aims at personalized subgraph discovery which is the key to understanding the organisation of many real-world networks. CS in undirected networks has attracted significant attention from researchers, including many solutions for various cohesive subgraph structures and for different levels of dynamism with edge insertions and deletions, while they are much less considered for directed graphs. In this paper, we propose incremental solutions of CS based on the D-truss in dynamic directed graphs, where the D-truss is a cohesive subgraph structure defined based on two types of triangles in directed graphs. We first analyze the theoretical boundedness of D-truss given edge insertions and deletions, then we present basic single-update algorithms. To improve the efficiency, we propose an order-based D-Index, associated batch-update algorithms and a fully-dynamic query algorithm. Our extensive experiments on real-world graphs show that our proposed solution achieves a significant speedup compared to the SOTA solution, the scalability over updates is also verified.

With the prevalence of voice devices in our daily life, speech data is accumulated at an unprecedented speed, forming an invaluable database for security surveillance and financial risk management. In these applications, a key task is given a querying speech snippet to retrieve all speech snippets that are uttered by the same speaker as the querying one, namely Identity-Oriented Speech Retrieval (IO-SR). In this paper, we propose an accuracy and scalable system for IO-SR, which seamlessly integrates speaker modeling and deep indexing techniques. Evaluations on an industrial dataset containing millions of speech snippets show that our system achieves superior performance compared with the state-of-the-art methods.

Complex social event summarization is a problem which has been shown having great utility for real-world applications, including crisis management, rumor control and government policy tracking. In recent years there has been significant research effort spent on effectively extracting meaningful textual descriptions of an event. However, in many critical situations, social events are complex and context-sensitive, which demands the online summarization of social events in an integrated manner. In this paper, we propose the first online complex social event summarization approach, namely SOMA, which summarizes the complex social events over multiple attributes including media content and contexts simultaneously. Specifically, we first propose a deep learning model that comprehensively summarizes events in regards to the text description and locations that they appear in, by utilizing their hidden connections in posts. We then propose a summary generator over time, text and location to achieve a maximal coverage of the summary over the original social event and minimal redundancy of the summary. Furthermore, we propose a location estimation method to address the location sparsity issue of complex events by mining the correlation between text and location. The evaluation over four real-event datasets and three benchmark datasets shows that our proposed approach outperforms the existing solutions for event summarizaiton in terms of effectiveness and efficiency.

The rapid growth of online service platforms has greatly influenced the way users conduct daily activities. In response to the requirements of frequent online activities, recommendation has become one of the best ways for the organizations, governments and individuals to understand their users and promote their services. Effective recommendation of online items has become critical in domains such as e-commerce and online media. Driven by the business success, academic research in this field has been active for many years. However, there are still many research challenges, such as context discovery, sequential user behavior influence, explainability and user interaction of system, big service data management. Especially, the highly dynamic online network data make these challenges even critical. Due to the high pressing interest and challenges in this area, this special issue is devoted to this topic, and focuses on the new solutions using AI and Big Data techniques.

Differential privacy (DP) has become the de facto standard of privacy protection. For graphs, there are two widely used definitions of differential privacy, namely, edge differential privacy (edge-DP) and node differential privacy (node-DP), and node-DP is preferred when the minimal unit of interest is a node. To preserve node-DP, one can develop different methods to answer each specific graph query, or develop a graph publishing method to answer all graph queries. However, no existing works worked on such graph publishing methods. In this work, we propose two methods for publishing graphs under node-DP. One is the node-level perturbation algorithm which modifies the input graph by randomly inserting and removing nodes. The other one is the edge-level perturbation algorithm which randomly removing edges and inserting nodes. Both methods can achieve a flexible privacy guarantee by adjusting the running parameters. We conduct extensive experiments on both real-world and synthetic graphs to show the effectiveness and efficiency of proposed algorithms.

User identity linkage, which aims to link identities of a natural person across different social platforms, has attracted increasing research interest recently. Existing approaches usually first embed the identities as deterministic vectors in a shared latent space, and then learn a classifier based on the available annotations. However, the formation and characteristics of real-world social platforms are full of uncertainties, which makes these deterministic embedding based methods sub-optimal. Besides, semi-supervised models utilize the unlabeled data to help capture the intrinsic data distribution. However, the existing semi-supervised linkage methods heavily rely on the heuristically defined similarity measurements to incorporate the innate closeness between labeled and unlabeled samples. Such manually designed assumptions may not be consistent with the actual linkage signals and further introduce the noises. To address the mentioned limitations, in this paper we propose a novel Noise-aware Semi-supervised Variational User Identity Linkage (NSVUIL) model. Specifically, we first propose a novel supervised linkage module to incorporate the available annotations. Each social identity is represented by a Gaussian distribution in the Wasserstein space to simultaneously preserve the fine-grained social profiles and model the uncertainty of identities. Then, a noise-aware self-learning module is designed to faithfully augment the few available annotations, which is capable of filtering noises from the pseudo-labels generated by the supervised module. The filtered reliable candidates are added into the labeled set to provide enhanced training guidance for the next training iteration. Empirically, we evaluate the NSVUIL model over multiple real-world datasets, and the experimental results demonstrate its superiority.

Graph convolutional networks (GCNs) have been successfully applied in many different real-world tasks. However, most of the existing methods are based on shallow GCN, because multiple layers involve long-distance neighborhood information but lead to the over-smoothing problem. Actually, a similar challenge exists in the depth limitation for primitive convolutional neural networks (CNNs). As the multi-layer architecture can increase the representation ability of GCN, we study and learn from the recent progress in CNN and propose Lasagne, a novel multi-layer GCN framework, empowered by node-aware layer aggregators and factorization-based layer interactions to overcome the over-smoothing problem and realize the full potentials of the GCN model. We analyze how the node locality affects the information propagation in GCN and propose a novel node aggregation mechanism in an adaptive manner. We further demystify Lasagne from a mutual information view and evaluate it on both real-world benchmark data sets and large-scale industrial production data sets. Lasagne shows strong empirical performance on the semi-supervised node classification task and outperforms the state-of-the-art methods without considering the node locality.

Range aggregation is a primitive operation in spatial data applications and there is a growing demand to support such operations over a data federation, where the entire spatial data are separately held by multiple data providers (a.k.a., data silos). Data federations notably increase the amount of data available for data-intensive applications such as smart mobility planning and public health emergency responses. Yet they also challenge the conventional implementation of range aggregation queries because the raw data cannot be shared within the federation and the data partition at each data silo is fixed during query processing. These constraints limit the design space of distributed range aggregation query processing. In this work, we propose approximate algorithms for efficient range aggregation over spatial data federation. We devise novel single-silo sampling algorithms that process queries in parallel and design a level sampling based algorithm which reduces the time complexity of local queries at each data silo to O(log 1/), where is the approximation ratio of the accuracy guarantee. Extensive evaluations with real-world data show that compared with state-of-the-arts, our solutions reduce the time cost and communication cost by up to 85.1x and 5.5x respectively, with average approximate errors of below 2.8%.

With their instant transaction confirmation and high scalability, payment channel networks (PCNs), running off-chain and in parallel with blockchain systems, have recently attracted a substantial amount of research attention. It has been shown that there exists a significant gap between the theoretically optimal performance and the performance achievable given the stringent privacy requirements in practice. However, it remains unclear what the fundamental performance limits and key factors involved are, which turns out to be a challenging problem due to the unique characteristics in PCNs. In this paper, we, for the first time, develop a mathematical model capturing the PCN performance, and examine the impact from a number of factors including channel capacity and transactions. We are articularly interested in obtaining the gap between the theoretically optimal performance and the performance achievable in practice, which characterizes the design space in PCNs for scheduling transactions. Specifically, we derive how different transactions and channel capacities affect the PCN performance and the performance gap. Our analytical characterization of PCNs offers an in-depth understanding on their fundamental trade-off, and provides important insights on the design of PCNs.

Dynamic graphs refer to graphs whose structure dynamically changes over time. Despite the benefits of learning vertex representations (i.e., embeddings) for dynamic graphs, existing works merely view a dynamic graph as a sequence of changes within the vertex connections, neglecting the crucial asynchronous nature of such dynamics where the evolution of each local structure starts at different times and lasts for various durations. To maintain asynchronous structural evolutions within the graph, we innovatively formulate dynamic graphs as temporal edge sequences associated with joining time of vertices (ToV) and timespan of edges (ToE). Then, a time-aware Transformer is proposed to embed vertices’ dynamic connections and ToEs into the learned vertex representations. Meanwhile, we treat each edge sequence as a whole and embed its ToV of the first vertex to further encode the time-sensitive information. Extensive evaluations on several datasets show that our approach outperforms the state-of-the-art in a wide range of graph mining tasks. At the same time, it is very efficient and scalable for embedding large-scale dynamic graphs.

Recent years have witnessed unprecedented amounts of data generated by telecommunication (Telco) cellular networks. For example, measurement records (MRs) are generated to report the connection states between mobile devices and Telco networks, e.g., received signal strength. MR data have been widely used to localize outdoor mobile devices for human mobility analysis, urban planning, and traffic forecasting. Existing works using first-order sequence models such as the Hidden Markov Model (HMM) attempt to capture spatio-temporal locality in underlying mobility patterns for lower localization errors. The HMM approaches typically assume stable mobility patterns of the underlying mobile devices. Yet real MR datasets exhibit heterogeneous mobility patterns due to mixed transportation modes of the underlying mobile devices and uneven distribution of the positions associated with MR samples. Thus, the existing solutions cannot handle these heterogeneous mobility patterns. To this end, we propose a multi-task learning-based deep neural network (DNN) framework, namely${{\sf PRNet}}$$^+$, to incorporate outdoor position recovery and transportation mode detection. To make sure that${{\sf PRNet}}$$^+$can work, we develop a feature extraction module to precisely learn local-, short- and long-term spatio-temporal locality from heterogeneous MR samples. Extensive evaluation on eight datasets collected at three representative areas in Shanghai indicates that${{\sf PRNet}}$${^{+}}$greatly outperforms state-of-the-arts by lower localization errors.

Personalizing the analysis for web search potentially improves the search experience. A good analytical model for web search should leverage not only collective wisdom but also individual characteristics. Most of the existing analytical models, however, focus on how to utilize the collective wisdom, from a crowd, for instance. In this paper, we address the problem of user-specific web search analysis by considering the so-called burstiness in web search, which captures the behavior of rare words appearing many times in a single document. We go beyond click graph and propose two probabilistic topic models, Topic Independence Model and Topic Dependence Model. The former adopts the assumption that the generation of query terms and URLs are topically independent, and the latter captures the coupling between search queries and URLs. We also capture the temporal burstiness of topics by utilizing continuous Beta distribution. Through a large-scale analysis of a real-life search query log, we observe that each user's web search trail enjoys multiple kinds of user-based unique characteristics. On a massive search query log, the new models achieve a better held-out likelihood than existing baselines, and they can also effectively reveal the latent evolution of topics on the corpus level and user-based level.

in this paper, we have made the first contribution by designing two right types of questions, namely Routing Query (RQ) to ask the crowd to decide the direction at each road intersection. Secondly, we propose a series of efficient algorithms to dynamically manage the questions in order to reduce the selection hardness within a limited budget. In particular, we show that there are two factors affecting the informativeness of a question: the randomness (entropy) of the question and the structural position of the road intersection. Furthermore, we extend the framework to enable multiple RQs per round. To ease the pain of the sample sensitiveness, we propose a new approach to reduce the selection hardness by reasoning on a so-called Selective Bayesian network. We compare our approach against several baselines, and the effectiveness and efficiency of our proposal are verified by the results in simulations and experiments on real-world datasets. The experimental results show that, even the Selective Bayesian Network provides only partial information of causality, the performance on the reduction of the selection hardness are dramatically improved, especially when the size of samples are relatively small.

Bike-sharing systems, where people rent bikes typically for last-mile commuting, has gained great popularity in recent years due to the rapid development of mobile networks. Station-based bike-sharing systems have been widely studied in both academia and industry, where problems like bike rental demand prediction and bike redistribution have been discussed. In contrast, not much attention has been paid to the routing algorithms for shared-bike riders. A routing solution consists of two stations, suggesting where to rent and return a bike. Existing routing works generally target a single rider. However, during the rush hours, there often exist routing requests from multiple riders simultaneously, which has not been carefully investigated before. In this paper, we study the routing problem for multiple shared-bike riders with hardness analyses and approximation algorithms. The challenge lies in how to allocate the limited resources (bikes/docks at the stations) among the competing riders. We show that this problem is NP-hard, and thus propose two heuristics. We also propose an optimization technique on routing plan generations, to improve the efficiency of the algorithms. Extensive experiments have been carried out to verify the performance of the proposed algorithms. It turns out that the greedy-based routing algorithm, which has an approximation factor of 1/3, is both effective and efficient.

Graph neural networks (GNNs) have been widely applied in the recommendation tasks and have achieved very appealing performance. However, most GNN-based recommendation methods suffer from the problem of data sparsity in practice. Meanwhile, pre-training techniques have achieved great success in mitigating data sparsity in various domains such as natural language processing (NLP) and computer vision (CV) . Thus, graph pre-training has the great potential to alleviate data sparsity in GNN-based recommendations. However, pre-training GNNs for recommendations faces unique challenges. For example, user-item interaction graphs in different recommendation tasks have distinct sets of users and items, and they often present different properties. Therefore, the successful mechanisms commonly used in NLP and CV to transfer knowledge from pre-training tasks to downstream tasks such as sharing learned embeddings or feature extractors are not directly applicable to existing GNN-based recommendations models. To tackle these challenges, we delicately design an adaptive graph pre-training framework for localized collaborative filtering (ADAPT) . It does not require transferring user/item embeddings, and is able to capture both the common knowledge across different graphs and the uniqueness for each graph simultaneously. Extensive experimental results have demonstrated the effectiveness and superiority of ADAPT.

Abstract Uncertain butterflies are one of, if not the, most important graphlet structures on uncertain bipartite networks. In this paper, we examine the uncertain butterfly structure (in which the existential probability of the graphlet is greater than or equal to a threshold parameter), as well as the global Uncertain Butterfly Counting Problem (to count the total number of these instances over an entire network). To solve this task, we propose a non-trivial exact baseline ( UBFC ), as well as an improved algorithm ( IUBFC ) which we show to be faster both theoretically and practically. We also design two sampling frameworks ( UBS and PES ) which can sample either a vertex, edge or wedge from the network uniformly and estimate the global count quickly. Furthermore, a notable butterfly-based community structure which has been examined in the past is the k -bitruss. We adapt this community structure onto the uncertain bipartite graph setting and introduce the Uncertain Bitruss Decomposition Problem (which can be used to directly answer any k -bitruss search query for any k ). We then propose an exact algorithm ( UBitD ) to solve our problem with three variations in deriving the initial uncertain support. Using a range of networks with different edge existential probability distributions, we validate the efficiency and effectiveness of our solutions.

Product attribute value extraction plays an important role for many real-world applications in e-Commerce such as product search and recommendation. Previous methods treat it as a sequence labeling task that needs more annotation for position of values in the product text. This limits their application to real-world scenario in which only attribute values are weakly-annotated for each product without their position. Moreover, these methods only use product text (i.e., product title and description) and do not consider the semantic connection between the multiple attribute values of a given product and its text, which can help attribute value extraction. In this paper, we reformulate this task as a multi-label classification task that can be applied for real-world scenario in which only annotation of attribute values is available to train models (i.e., annotation of positional information of attribute values is not available). We propose a classification model with semantic matching and negative label sampling for attribute value extraction. Semantic matching aims to capture semantic interactions between attribute values of a given product and its text. Negative label sampling aims to enhance the model’s ability of distinguishing similar values belonging to the same attribute. Experimental results on three subsets of a large real-world e-Commerce dataset demonstrate the effectiveness and superiority of our proposed model.

Event popularity prediction over social media is crucial for estimating information propagation scope, decision making, and emergency prevention. It has been widely inves-tigated by existing approaches focusing on predicting single attribute occurrences which are not comprehensive enough for representing complex social event propagation. Motivated by this, we propose a novel hashtag-influence-based event popularity prediction by mining the impact of an influential hashtag set on the event propagation. We have conducted extensive experiments to prove the effectiveness and efficiency of the proposed approach.

Interactive graph search (IGS) uses human intelligence to locate the target node in hierarchy, which can be applied for image classification, product categorization and searching a database. Specifically, IGS aims to categorize an object from a given category hierarchy via several rounds of interactive queries. In each round of query, the search algorithm picks a category and receives a boolean answer on whether the object is under the chosen category. The main efficiency goal asks for the minimum number of queries to identify the correct hierarchical category for the object. In this paper, we study the average-case interactive graph search (AIGS) problem that aims to minimize the expected number of queries when the objects follow a probability distribution. We propose a greedy search policy that splits the candidate categories as evenly as possible with respect to the probability weights, which offers an approximation guarantee of$O(\log n)$for AIGS given the category hierarchy is a directed acyclic graph (DAG), where$n$is the total number of categories. Meanwhile, if the input hierarchy is a tree, we show that a constant approximation factor of$(1+\sqrt{5})/2$can be achieved. Furthermore, we present efficient implementations of the greedy policy, namely GreedyTree and GreedyDAG, that can quickly categorize the object in practice. Extensive experiments in real-world scenarios are carried out to demonstrate the superiority of our proposed methods.

With the development of traffic prediction technology, spatiotemporal prediction models have attracted more and more attention from academia communities and industry. However, most existing researches focus on reducing model's prediction error but ignore the error caused by the uneven distribution of spatial events within a region. In this paper, we study a region partitioning problem, namely optimal grid size selection problem (OGSS), which aims to minimize the real error of spatiotemporal prediction models by selecting the optimal grid size. In order to solve OGSS, we analyze the upper bound of real error of spatiotemporal prediction models and minimize the real error by minimizing its upper bound. Through in-depth analysis, we find that the upper bound of real error will decrease then increase when the number of model grids increase from 1 to the maximum allowed value. Then, we propose two algorithms, namely Ternary Search and Iterative Method, to automatically find the optimal grid size. Finally, the experiments verify that the error of prediction has the same trend as its upper bound, and the change trend of the upper bound of real error with respect to the increase of the number of model grids will decrease then increase. Meanwhile, in a case study, by selecting the optimal grid size, the order dispatching results of a state-of-the-art prediction-based algorithm can be improved up to 13.6%, which shows the effectiveness of our methods on tuning the region partition for spatiotemporal prediction models.

Graph neural networks (GNNs) have achieved great success on various graph tasks. However, recent studies have re-vealed that GNNs are vulnerable to adversarial attacks, including topology modifications and feature perturbations. Regardless of the fruitful progress, existing attackers require node labels and GNN parameters to optimize a bi-level problem, or cannot cover both topology modifications and feature perturbations, which are not practical, efficient, or effective. In this paper, we propose a black-box attacker PEEGA, which is restricted to access node features and graph topology for practicability. Specifically, we propose to measure the negative impact of various adversarial attacks from the perspective of node representations, thereby we formulate a single-level problem that can be efficiently solved. Furthermore, we observe that existing attackers tend to blur the context of nodes through adding edges between nodes with different labels. As a result, GNNs are unable to recognize nodes. Based on this observation, we propose a GNN defender GNAT, which incorporates three augmented graphs, i.e., a topology graph, a feature graph, and an ego graph, to make the context of nodes more distinguishable. Extensive experiments on three real-world datasets demonstrate the effectiveness and efficiency of our proposed attacker, despite the fact that we do not access node labels and GNN parameters. Moreover, the effectiveness and efficiency of our proposed defender are also validated by substantial experiments.

In this paper, we propose Lasagne, a novel multi-layer graph convolutional network (GCN) framework to over-come the over-smoothing problem and realize the full poten-tials of deep GCNs. We analyze how node localities affect the information propagation in GCN, propose an adaptive novel node aggregation mechanism and further demystify from a mutual information view. Evaluation results on both real-world benchmark data sets and large-scale industrial production data sets show Lasagne significantly outperforms the state-of- the-art methods without considering the node locality.

Due to the transparency of blockchain, adversaries can observe the details of a transaction, and then utilize the amount as a unique quasi-identifier to make deanonymization. Nowadays, to obscure the linkages between receivers and senders within a transaction on the blockchain, mixing services are widely applied in many real applications to enhance cryptocurrencies' anonymity. The basic idea of mixing services is to hide an output within several other outputs in a transaction such that adversaries cannot distinguish them by their amounts since they are purposely selected to have the same amount. For a set of original outputs with different amounts, mixing services need to decompose them into a set of decomposed outputs, where any decomposed output has some other decomposed outputs with the same amount. Since the transaction fee is related to the number of outputs, we are motivated to decompose original outputs into a minimal set of decomposed outputs, which is challenging to guarantee the privacy-preserving effect at the same time. In this paper, we formally define the anonymity-aware output decomposition (AA-OD) problem, which aims to find a c-decomposition with a minimum number of decomposed outputs for a given original output set. A c-decomposition guarantees that for any original output$o$, there are at most$c$of all decomposed outputs with an amount of$x$coming from$o$. We prove that the AA-OD problem is NP-hard. Thus, we propose an approximation algorithm, namely Boggart11Boggart is a magical creature in J. K. Rowling's Harry Potter series who can shift his shape and no one knows what it looks like., to solve the AA-OD problem with a (2/c + 3)-approximation bound on the number of decomposed outputs. We verify the efficiency and effectiveness of our approach through comprehensive experiments on both real and synthetic data sets.

Data federations notably increase the amount of data available for data-intensive applications such as smart mobility planning and public health emergency responses. Yet they also challenge the conventional implementation of range aggregation queries because the raw data cannot be shared within the federation and the data partition at each data silo is fixed during query processing. In this work, we propose the first-of-its-kind approximate algorithms for efficient range aggregation over spatial data federation. We devise novel single-silo sampling algorithms that process queries in parallel and design a level sampling based algorithm which reduces the time complexity of local queries at each data silo to$O(\log\frac{1}{\epsilon})$, where ∊ is the approximation ratio of the accuracy guarantee. Extensive experiments on real-world dataset validate the efficiency and effectiveness of the solutions.

Recently, neural networks based models have been widely used for recommender systems (RS). Unfortunately, the existing neural network based RS solutions are often treated as black-boxes, which gain little trust and confidence from users. Thus, there is an increasing demand of explainability. Several explainable recommendation methods have been introduced to RS. However, there is a trade-off between explainability and performance among these methods. In this paper, we propose a novel framework, the Tower Bridge Net (TB-Net), using the proposed bidirectional embedding propagation approach to achieve both superior recommendation and explainability performances. Extensive validation on three public datasets shows that the performance of TB-Net dominates the state-of-the-art models. We quantitatively evaluate the explainability by using numerical metrics and experimentally prove that TB-Net achieves a significant improvement on explainability compared with existing methods. More importantly, TB-Net has been deployed and offers explainable recommendation service for the largest bank in China, Industrial and Commercial Bank of China Limited (ICBC). Results on a billion-scale dataset (1.2 billion nodes and edges) from ICBC show that TB-Net can provide both accurate recommendations and semantic explanations, and is very effective and deployable in practice.

Nowadays, multi-hop question answer (QA) problem is challenging and not well solved in the QA community. The dominant bottleneck of the multi-hop QA problem is the need for a reasoning retriever to fetch a document path from an open-domain corpus (e.g., Wikipedia). A reasoning retriever aims to collect an evidence document from large corpora at one hop retrieval and aggregate the evidence for subsequent hop retrieval, which yields a document path after multi-hop retrieval. There exist two challenges, (1) to fetch the evidence document in an efficient and explainable way at one hop retrieval and (2) to update the question information by aggregating the evidence from the retrieved document after each hop retrieval. To address these two challenges, we propose a triple-fact-based retrieval model to effectively retrieve a related document path in an explainable way for each question. We extract a structured representation from the unstructured document and utilize the knowledge of pre-trained language model (PLM) to do the semantic-level matching between the question and document. We evaluate the proposed Triple-fact Retriever model on the recently proposed open-domain multi-hop QA dataset, HotpotQA, and a cross-document multi-step Reading Comprehension dataset, Wikihop. The results11The source code is available on our website: https://github.com/Rebaccamin/triple_retriever. demonstrate that the Triple-fact retriever outperforms the existing baseline retrieval works.

Listing all k-cliques is a fundamental problem in graph mining, with applications in finance, biology, and social network analysis. However, owing to the exponential growth of the search space as$k$increases, listing all k-cliques is algorithmically challenging. DDegree and DDegCol are the state-of-the-art algorithms that exploit ordering heuristics based on degree ordering and color ordering, respectively. Both DDegree and DDegCol induce high time and space overhead for set intersections cause they construct and maintain all induced subgraphs. Meanwhile, it is non-trivial to implement the data level parallelism to further accelerate on DDegree and DDegCol. In this paper, we propose two efficient algorithms SDegree and BitCol for k-clique listing. We mainly focus on accelerating the set intersections for k-clique listing. Both SDegree and BitCol exploit the data level parallelism for further acceleration with single instruction multiple data (SIMD) or vector instruction sets. Furthermore, we propose two preprocessing techniques Pre-Core and Pre-List, which run in linear time. The preprocessing techniques significantly reduce the size of the original graph and prevent exploring a large number of invalid nodes. In the theoretical analysis, our algorithms have a comparable time complexity and a slightly lower space complexity than the state-of-the-art algorithms. The comprehensive experiments reveal that our algorithms outperform the state-of-the-art algorithms by 3.75x for degree ordering and 5.67x for color ordering on average.

In spite of its wide usage in various applications, existing construction methods for Knowledge Base (KB) are still on their way to obtaining 100% correct facts. Thus, employing crowd workers to validate a KB has been proposed to improve its reliability. Most of the existing works focus on devising games with proper incentives to engage workers in validating more facts, but rarely consider matching facts with proper workers. Facts have diverse domains (topics), which naturally require workers of different expertise. In addition, they also generally have different utilities, i.e., some are more heavily used than others. Thus, distinguishing the facts in terms of utility to give them different validation priorities is meaningful, especially when the budget is limited. To this end, we study the crowdsourced fact validation problem which considers worker domains and fact utilities, and find that with some reductions, it can be solved by the existing minimum cost network flow method. However, directly employing that method requires a huge time cost. We thereby propose an optimized network flow method which reduces the network complexity to save the time cost by properly grouping the facts. Furthermore, we propose an incremental validation method, which utilizes the previous results for validating an evolving KB. We finally conduct extensive experiments to demonstrate the effectiveness of the proposed methods.

Graph Neural Networks (GNNs) have attracted much research interest due to their successful applications on graph-structured data. Despite the effectiveness, due to the data dependency, GNNs are confronted with the neighborhood explosion and over-smoothing problems. Many sampling-based and level-down methods have been proposed to solve the neighborhood explosion problem to boost efficiency. However, they suffer from either poor accuracy or considerable runtime overheads. Moreover, the over-smoothing problem prevents GNNs from exploring more distant neighborhoods effectively. In this paper, we present a Community-and-Contraction-based Graph Neural Network (CC-GNN), which leverages community and contraction to boost the time and space efficiency of GNNs. Specifically, CC-GNN first performs contraction and retrieves the communities as super nodes, and connects them using a tailored similarity function to obtain an informative community contracted graph (CC-Graph). CC-GNN then learns the representations of the super nodes in the CC-Graph, which are used to reconstruct the representations of the original nodes. Finally, CC-GNN explores more distant neighborhoods without additional convolution layers, implicitly alleviating the over-smoothing problem. Since CC-GNN conducts the costly training on a much smaller contracted graph, the efficiency is boosted significantly. Most importantly, we have proved that the information loss of node representations caused by the CC-Graph is bounded. Extensive experimental studies verify the efficiency boost and the effectiveness.

Recently Graph Neural Networks (GNNs) have achieved great success in many applications. To apply GNNs to large graphs, mini-batch training and sampling are widely adopted by recent works. However, existing works generate mini-batches following a topology-oriented sampling style, which first samples a subgraph and then fetches the corresponding node features to construct a mini-batch. This inevitably incurs intensive random access of graph data, the exponential growth of the batch size, and constrained candidates during sampling. In this work, we advocate adopting a feature-oriented sampling style which can overcome these drawbacks. We first sample the node features and then induce the corresponding subgraph to form a mini-batch. We apply the feature-oriented sampling method to three mainstream GNN models to demonstrate the effectiveness and efficiency of this sampling style. Experiments on four large-scale datasets show that feature-oriented sampling can achieve comparable accuracy as topology-oriented sampling while speeding up the training procedure by 2.2 ~ 7.9 times.

The interactive graph search (IGS) problem aims to locate an initially unknown target node leveraging human intelligence. In IGS, we can gradually find the target node by sequentially asking humans some reachability queries like "is the target node reachable from a given node x?". However, human workers may make mistakes when answering these queries. Motivated by this concern, in this paper, we study a noisy version of the IGS problem. Our objective in this problem is to minimize the query complexity while ensuring accuracy. We propose a method to select the query node such that we can push the search process as much as possible and an online method to infer which node is the target after collecting a new answer. By rigorous theoretical analysis, we show that the query complexity of our approach is near-optimal up to a constant factor. The extensive experiments on two real datasets also demonstrate the superiorities of our approach.

Recent years have witnessed an exponential growth of model scale in deep learning-based recommender systems---from Google's 2016 model with 1 billion parameters to the latest Facebook's model with 12 trillion parameters. Significant quality boost has come with each jump of the model capacity, which makes us believe the era of 100 trillion parameters is around the corner. However, the training of such models is challenging even within industrial scale data centers. We resolve this challenge by careful co-design of both optimization algorithm and distributed system architecture. Specifically, to ensure both the training efficiency and the training accuracy, we design a novel hybrid training algorithm, where the embedding layer and the dense neural network are handled by different synchronization mechanisms; then we build a system called Persia (short for parallel recommendation training system with hybrid acceleration) to support this hybrid training algorithm. Both theoretical demonstrations and empirical studies with up to 100 trillion parameters have been conducted to justify the system design and implementation of Persia. We make Persia publicly available (at github.com/PersiaML/Persia) so that anyone can easily train a recommender model at the scale of 100 trillion parameters.

Many real-world applications rely on predictive models that are incrementally learned online. Specifically, models are updated with a single pass over continuously arriving data batches in a typical stream learning framework. However, this framework has three shortcomings: high training cost, low data effectiveness, and catastrophic forgetting. We describe Camel, a system that addresses the above issues. Camel includes two independent data management components: coreset selection and buffer update. To accelerate model training, Camel selects a coreset from each streaming data batch for model update. Selecting a coreset with worst-case guarantees is NP-hard. To solve this problem, we reformulate coreset selection as a submodular maximization problem by deriving an upper bound on the objective function. To mitigate catastrophic forgetting, Camel maintains a buffer of past representative samples as new data arrive. Moreover, Camel quantizes numerical data in buffer via a quantile sketch to reduce the memory footprint. Finally, extensive experiments validate the effectiveness and efficiency of Camel. In particular, our coreset selection algorithm can achieve a linear speedup with a marginal accuracy loss on redundant datasets. Furthermore, our buffer update algorithms can outperform the state-of-the-art methods for anti-forgetting on various data distributions.

The emerging deep learning techniques prefer mapping complex data objects (e.g., images, documents) to compact binary vectors (i.e., hash codes) for efficient similarity search. In this paper, we study the problem of indexing large-scale binary databases to support fast Hamming distance-based similarity queries. Existing Hamming space indices usually divide long binary vectors into short disjoint pieces and apply the Pigeonhole Principle to prune unnecessary candidates. In our work, we relax the disjoint partition constraint by allowing dimension redundancy, which yields a tighter pruning bound named Augmented Pigeonhole Principle (APP). Intuitively, APP enables more optimization opportunities by capturing the correlation between database and query workloads. Based on APP, we propose HAP, an efficient Hamming space index framework to support both Hamming range queries and k-NN queries.

Hierarchically Separated Tree (HST) is the most popular solution to embed a metric space into a tree metric. By using HSTs, many optimization problems, which are hard on defined metrics, become easier to get good approximation bounds with respect to the effectiveness, e.g., task assignment, trip planning, and facility location planning. Existing work focuses on constructing HSTs for arbitrary metric spaces, which makes a general-purpose algorithm take at least O(n2)-time to get tight distortion guarantees O(log(n)). Here, distortion is a prevalent measurement of HSTs' effectiveness and usability. However, we observe that (1) in many applications that HSTs are applied, only Lp metrics are used (e.g., Euclidean space), (2) the state-of-the-art solution is still time-consuming to construct HSTs for large-scale data, and (3) distortions of existing algorithms are only satisfactory for high-dimensional data. Thus, in this paper, we are motivated to study the Embedding Lp metrics through Tree metrics (ELT) problem. We aim to design a faster algorithm than O(n2) time to construct HSTs with not only O(log(n)) distortion guarantees but also good and robust empirical results. Specifically, we first present a divide-and-conquer based general framework and prove that it has a distortion guarantee of O(log(n)). To achieve a better time complexity than O(n2), we next design two optimization techniques: reducing to nearest neighbor search (by indexing) and sampling. Finally, extensive experiments demonstrate that our algorithm DCsam outperforms the state-of-the-art algorithms by a large margin in terms of both distortion and running time.

The configuration of 512 window size prevents transformers from being directly applicable to document ranking that requires larger context. Hence, recent works propose to estimate document relevance with fine-grained passage-level relevance signals. A limitation of such models, however, is that scoring each passage independently falls short in modeling inter-passage interactions and leads to unsatisfactory results. In this paper, we propose a Multiview inter-passage Interaction based Ranking model (MIR), to combine intra-passage interactions and inter-passage interactions in a complementary manner. The former captures local semantic relations inside each passage, whereas the latter draws global dependencies between different passages. Moreover, we represent inter-passage relationships via multi-view attention patterns, allowing information propagation at token, sentence, and passage-level. The representations at different levels of granularity, being aware of global context, are then aggregated into a document-level representation for ranking. Experimental results on two benchmarks show that modeling inter-passage interactions brings substantial improvements over existing passage-level methods.

Precipitation forecasting, modeled as an important chaotic system in earth system science, is not explicitly solved with theory-driven models. In recent years, deep learning models have achieved great success in various applications including rainfall prediction. However, these models work in an image processing manner regardless of the nature of a physical system. We found that the non-linearity relationships learned by deep learning models, which mostly rely on the activation functions, are commonly weighted piecewise continuous functions with bounded first-order derivatives. In contrast, the polynomial is one of the most widely used classes of functions for theory-driven models, applied to numerical approximation, dynamic system modeling, etc.. Researchers started to use the polynomial activation functions (Pacs in short) for neural networks from the 1990s. In recent years, with bloomed researches that apply deep learning to scientific problems, it is weird that such a powerful class of basis functions is rarely used. In this paper, we investigate it and argue that, even though polynomials are good at information extraction, it is too fragile to train stably. We finally solve its serious data flow explosion problem with Chebyshev polynomials and prepended normalization, which enables networks to go deep with Pacs. To enhance the robustness of training, a normalization called Range Norm is further proposed. Performance on synthetic dataset and summer precipitation prediction task validates the necessity of such a class of activation functions to simulate complex physical mechanisms. The new tool for deep learning enlightens a new way of automatic theoretical physics analysis.

Perturbation-based techniques are promising for explaining black-box machine learning models due to their effectiveness and ease of implementation. However, prior works have faced the problem of Out-of-Distribution (OoD) — an artifact of randomly perturbed data becoming inconsistent with the original dataset, degrading the reliability of generated explanations, which is still under-explored according to our best knowledge. This work addresses the OoD issue by designing a simple yet effective module that can quantify the affinity between the perturbed data and the original dataset distribution. Specifically, we penalize the influences of unreliable OoD data for the perturbed samples by integrating the inlier scores and prediction results of the target models, thereby making the final explanations more robust. Our solution is shown to be compatible with the most popular perturbation-based XAI algorithms: RISE, OCCLUSION, and LIME. Extensive experiments confirmed that our methods exhibit superior performance in most cases with computational and cognitive metrics. In particular, we point out the degradation problem of RISE algorithm for the first time. With our design, the performance of RISE can be boosted significantly. Besides, our solution also resolves a fundamental problem with a faithfulness indicator, a commonly used evaluation metric of XAI algorithms that appears sensitive to the OoD issue.

With the continuous development of spatial crowdsourcing platform, online task assignment problem has been widely studied as a typical problem in spatial crowdsourcing. Most of the existing studies are based on a single-platform task assignment to maximize the platform's revenue. Recently, cross online task assignment has been proposed, aiming at increasing the mutual benefit through cooperations. However, existing methods fail to consider the data privacy protection in the process of cooperation and cause the leakage of sensitive data such as the location of a request and the historical data of cooperative platforms. In this paper, we propose Privacy-preserving Cooperative Online Matching (PCOM), which protects the privacy of the users and workers on their respective platforms. We design a PCOM framework and provide theoretical proof that the framework satisfies the differential privacy property. We then propose two PCOM algorithms based on two different privacy-preserving strategies. Extensive experiments on real and synthetic datasets confirm the effectiveness and efficiency of our algorithms.

Random walk is widely used in many graph analysis tasks, especially the first-order random walk. However, as a simplification of real-world problems, the first-order random walk is poor at modeling higher-order structures in the data. Recently, second-order random walk-based applications (e.g., Node2vec, Second-order PageRank) have become attractive. Due to the complexity of the second-order random walk models and memory limitations, it is not scalable to run second-order random walk-based applications on a single machine. Existing disk-based graph systems are only friendly to the first-order random walk models and suffer from expensive disk I/Os when executing the second-order random walks. This paper introduces an I/O-efficient disk-based graph system for the scalable second-order random walk of large graphs, called GraSorw. First, to eliminate massive light vertex I/Os, we develop a bi-block execution engine that converts random I/Os into sequential I/Os by applying a new triangular bi-block scheduling strategy, the bucket-based walk management, and the skewed walk storage. Second, to improve the I/O utilization, we design a learning-based block loading model to leverage the advantages of the full-load and on-demand load methods. Finally, we conducted extensive experiments on six large real datasets as well as several synthetic datasets.. The empirical results demonstrate that the end-to-end time cost of popular tasks in GraSorw is reduced by more than one order of magnitude compared to the existing disk-based graph systems.

The increasing concerns on data security limit the sharing of data distributedly stored at multiple data owners and impede the scale of spatial queries over big urban data. In response, data federation systems have emerged to perform secure queries across multiple data owners leveraging secure multi-party computation. However, existing systems are designed for relational data. They are highly inefficient on spatial queries and limited in usability. In this demonstration, we introduce Hu-Fu, the first data federation system for secure spatial queries with high efficiency and usability. Hu-Fu is designed from the perspectives of the query user and the data owner for high usability and decomposes a spatial query into as many plaintext operators and as few secure operators as possible for high efficiency. We demonstrate the deployment and usage of Hu-Fu via cross-company taxi-calling, a popular smart city application.

Graph neural networks (GNNs) have emerged due to their success at modeling graph data. Yet, it is challenging for GNNs to efficiently scale to large graphs. Thus, distributed GNNs come into play. To avoid communication caused by expensive data movement between workers, we propose Sancus, a staleness-aware communication-avoiding decentralized GNN system. By introducing a set of novel bounded embedding staleness metrics and adaptively skipping broadcasts, Sancus abstracts decentralized GNN processing as sequential matrix multiplication and uses historical embeddings via cache. Theoretically, we show bounded approximation errors of embeddings and gradients with convergence guarantee. Empirically, we evaluate Sancus with common GNN models via different system setups on large-scale benchmark datasets. Compared to SOTA works, Sancus can avoid up to 74% communication with at least 1.86X faster throughput on average without accuracy loss.

The proof-of-work (PoW) based blockchains are more secure nowadays since profit-oriented miners contribute more computing powers in exchange for fair revenues. This virtuous circle only works under an incentive-compatible consensus, which is found to be fragile under selfish mining attacks. Specifically, selfish miners can conceal and reveal blocks strategically to earn unfairly higher revenue compared to honest behaviors. Previous countermeasures either require incompatible modifications or fail to consider the asynchronous network and multiple honest nodes setting in reality. In this paper, we introduce the unfairness measurement based on the KL-divergence from the computing power distribution to the revenue distribution of miners. To improve fairness with the existence of selfish miners, we propose a novel block promotion strategy namely Tit-for-Tat (TFT), for honest miners. In particular, based on a miner's local observation of forks, we design the suspicious probability measurement of other nodes. Rather than promoting a fresh block instantly, miners withhold it for different time periods according to others' suspicious probability before delivery. Meanwhile, to minimize the attacker's unfair revenue, we formulate the delay vector (DV) problem for honest miners to determine the optimal withholding time. We prove that DV problem is nonconvex, and thus propose two approximation algorithms that yield ϵ-suboptimal solutions. In addition, we extend TFT strategy to support dynamic networks. Extensive experiments validate the efficiency and effectiveness of our strategy and algorithms to reduce unfairness by 54.62% within bounded withholding time.

Data isolation has become an obstacle to scale up query processing over big data, since sharing raw data among data owners is often prohibitive due to security concerns. A promising solution is to perform secure queries over a federation of multiple data owners leveraging secure multi-party computation (SMC) techniques, as evidenced by recent federation work over relational data. However, existing solutions are highly inefficient on spatial queries due to excessive secure distance operations for query processing and their usage of general-purpose SMC libraries for secure operation implementation. In this paper, we propose Hu-Fu, the first system for efficient and secure spatial query processing on a data federation. The idea is to decompose the secure processing of a spatial query into as many plaintext operations and as few secure operations as possible, where fewer secure operators are involved and all secure operators are implemented dedicatedly. As a working system, Hu-Fu supports not only query input in native SQL, but also heterogeneous spatial databases ( e.g. , PostGIS, Simba, GeoMesa, and SpatialHadoop) at the backend. Extensive experiments show that Hu-Fu usually outperforms the state-of-the-arts in running time and communication cost while guaranteeing security.

Nowadays, ridesharing becomes a popular commuting mode. Dynamically arriving riders post their origins and destinations, then the platform assigns drivers to serve them. In ridesharing, different groups of riders can be served by one driver if their trips can share common routes. Recently, many ridesharing companies (e.g., Didi and Uber) further propose a new mode, namely "ridesharing with meeting points". Specifically, with a short walking distance but less payment, riders can be picked up and dropped off around their origins and destinations, respectively. In addition, meeting points enables more flexible routing for drivers, which can potentially improve the global profit of the system. In this paper, we first formally define the Meeting-Point-based Online Ridesharing Problem (MORP). We prove that MORP is NP-hard and there is no polynomial-time deterministic algorithm with a constant competitive ratio for it. We notice that a structure of vertex set, k -skip cover, fits well to the MORP. k -skip cover tends to find the vertices (meeting points) that are convenient for riders and drivers to come and go. With meeting points, MORP tends to serve more riders with these convenient vertices. Based on the idea, we introduce a convenience-based meeting point candidates selection algorithm. We further propose a hierarchical meeting-point oriented graph (HMPO graph), which ranks vertices for assignment effectiveness and constructs k -skip cover to accelerate the whole assignment process. Finally, we utilize the merits of k -skip cover points for ridesharing and propose a novel algorithm, namely SMDB, to solve MORP. Extensive experiments on real and synthetic datasets validate the effectiveness and efficiency of our algorithms.

Mining cohesive subgraphs on bipartite graphs is an important task. The k -bitruss is one of many popular cohesive subgraph models, which is the maximal subgraph where each edge is contained in at least k butterflies. The bitruss decomposition problem is to find all k -bitrusses for k ≥ 0. Dealing with large graphs is often beyond the capability of a single machine due to its limited memory and computational power, leading to a need for efficiently processing large graphs in a distributed environment. However, all current solutions are for a single machine and a centralized environment, where processors can access the graph or auxiliary indexes randomly and globally. It is difficult to directly deploy such algorithms on a shared-nothing model. In this paper, we propose distributed algorithms for bitruss decomposition. We first propose SC-HBD as the baseline, which uses H -function to define bitruss numbers and computes them iteratively to a fix point in parallel. We then introduce a subgraph-centric peeling method SC-PBD, which peels edges in batches over different butterfly complete subgraphs. We then introduce local indexes on each fragment, study the butterfly-aware edge partition problem including its hardness, and propose an effective partitioner. Finally we present the bitruss butterfly-complete subgraph concept, and divide and conquer DC-BD method with optimization strategies. Extensive experiments show the proposed methods solve graphs with 30 trillion butterflies in 2.5 hours, while existing parallel methods under shared-memory model fail to scale to such large graphs.

With the rapid development of blockchain, the concept of decentralized applications (DApps), built upon smart contracts, has attracted much attention in academia and industry. However, significant issues w.r.t. system throughput, transaction confidentiality, and the security guarantee of the DApp transaction execution and order correctness hinder the border adoption of blockchain DApps. To address these issues, we propose L2chain, a novel blockchain framework aiming to scale the system through a layer-2 network where DApps process transactions in the layer-2 network and only the system state digest, acting as the state integrity proof, is maintained on-chain. To achieve high performance, we introduce the split-execute-merge (SEM) transaction processing workflow with the help of the RSA accumulator, allowing DApps to lock and update a part of the state digest in parallel. We also design a witness cache mechanism for DApp executors to reduce the transaction processing latency. To fulfill confidentiality, we leverage the trusted execution environment (TEE) for DApps to execute encrypted transactions off-chain. To ensure transaction execution and order correctness, we propose a two-step execution process for DApps to prevent attacks ( i.e. , rollback attacks) from subverting the state transition. Extensive experiments have demonstrated that L2chain can achieve 1.5X to 42.2X and 7.1X to 8.9X throughput improvements in permissioned and permissionless settings respectively.

Real applications like crisis management require the real time awareness of critical situations. However, the services using traditional methods like phone calls can be easily delayed due to busy lines, transfer delays or limited communication ability in disaster areas. Existing social event analysis solutions enhanced the situation awareness of systems. Unfortunately, they cannot recognize the complex migrating social events that are first observed in social media at a specific time, place and state, but have further moved in space and time, which may affect the system comprehension. While the discussion on events appears in microblogs, their movement over different contexts is unavoidable. So far, the problem of migrating social event analysis from big media is not well investigated yet. To address this issue, we propose a novel framework to monitor and deliver the migrating events in big social media data, which fully exploits the social media information over multiple attributes and their inherent interactions among events. Specifically, we first propose a Concept TF/IDF model to capture the content that is constrained by the time and location of media without costly learning process. Then, we construct a novel Maximal User Influence Graph (MUIG) to extract the social interactions. With MUIG, the event migrations over space and time are well identified. Finally, we design efficient query strategies over Apache Spark for recommending events in real time. Extensive tests over big media are conducted to prove the high effectiveness and efficiency of our approach.

Event popularity prediction over social media is crucial for estimating information propagation scope, decision making, and emergency prevention. However, existing approaches only focus on predicting the occurrences of single attribute such as a message, a hashtag or an image, which are not comprehensive enough for representing complex social event propagation. In this paper, we predict the event popularity, where an event is described as a set of messages containing multiple hashtags. We propose a novel hashtag-influence-based event popularity prediction by mining the impact of an influential hashtag set on the event propagation. Specifically, we first propose a hashtag-influence-based cascade model to select the influential hashtags over an event hashtag graph built by the pairwise hashtag similarity and the topic distribution of event-related hashtags. A novel measurement is proposed to identify the hashtag influence of an event over its content and social impacts. A hashtag correlation-based algorithm is proposed to optimize the seed selection in a greedy manner. Then, we propose an event-fitting boosting model to predict the event popularity by embedding the feature importance over events into the XGBOOST model. Moreover, we propose an event-structure-based method, which incrementally updates the prediction model over social streams. We have conducted extensive experiments to prove the effectiveness and efficiency of the proposed approach.

Real-life graph datasets extracted from the Web are inevitably full of incompleteness, conflicts, and redundancies, so graph data cleaning shows its necessity. Although rules like data dependencies have been widely studied in relational data repairing, very few works exist to repair graph data. In this article, we introduce a repairing semantics for graphs, calledGraph-Repairing Rules(${\sf GRR}$s). This semantics can capture the incompleteness, conflicts, and redundancies in graphs and indicate how to correct these errors. However, this graph repairing semantics can only repair the graphs strictly isomorphic to the rule patterns, which decreases the utility of the rules. To overcome this shortcoming, we further propose a flexible rule-based graph repairing semantics (called$\delta$-GRR). We study three fundamental problems associated with both${\sf GRR}$s and$\delta$-GRRs, consistency, implication, and termination, which show whether a given set of rules make sense. Repairing the graph data using${\sf GRR}$s or$\delta$-GRRs involves a problem of finding isomorphic subgraphs of the graph data, which is NP-complete. To efficiently circumvent the complex calculation of subgraph isomorphism, we design a decomposition-and-join strategy to solve this problem. Extensive experiments on real datasets show that our two graph repairing semantics and corresponding repairing algorithms can effectively and efficiently repair real-life graph data.

With the rapid development of mobile technology, nowadays, people spend a large amount of time on mobile devices. The locations and contexts of users are easily accessed by mobile advertising brokers, and the brokers can send customers related location-based advertisements. In this paper, we consider an important location-based advertising problem, namely maximum utility advertisement assignment (MUAA) problem, with the estimation of the interests of customers and the contexts of the vendors, we want to maximize the overall utility of ads by determining the ads sent to each customer subject to the constraints of the capacities of customers, the distance ranges and the budgets of vendors. We prove that the MUAA problem is NP-hard and intractable. Thus, we propose one offline approach, namely the${\sf reconciliation\ approach}$, which has an approximation ratio of$(1-\epsilon)\cdot \theta$. In addition, we also address the online scenario, in which customers arrive in a streaming fashion, with one novel online algorithm, namely the${\sf online\ adaptive\ factor-aware\ approach}$, which has a competitive ratio (compared to the optimal solution of the offline scenario) of$\frac{\ln (g)+1}{\theta }$,$g>e$, where$e$is the base of the natural logarithm. Through extensive experiments, we demonstrate the efficiency and effectiveness of our proposed approaches over both real and synthetic datasets.

We are witnessing a fast development of Artificial Intelligence (AI), but it becomes dramatically challenging to explain AI models in the past decade. “Explanation” has a flexible philosophical concept of “satisfying the subjective curiosity for causal information”, driving a wide spectrum of methods being invented and/or adapted from many aspects and communities, including machine learning, visual analytics, human-computer interaction and so on. Nevertheless, from the view-point of data and knowledge engineering (DKE), a best explaining practice that is cost-effective in terms of extra intelligence acquisition should exploit the causal information and explaining scenarios which is hidden richly in the data itself. In the past several years, there are plenty of works contributing in this line but there is a lack of a clear taxonomy and systematic review of the current effort. To this end, we propose this survey, reviewing and taxonomizing existing efforts from the view-point of DKE, summarizing their contribution, technical essence and comparative characteristics. Specifically, we categorize methods into data-driven methods where explanation comes from the task-related data, and knowledge-aware methods where extraneous knowledge is incorporated. Furthermore, in the light of practice, we provide survey of state-of-art evaluation metrics and deployed explanation applications in industrial practice.

Heterogeneous information networks (HINs) are usually used to model information systems with multi-type objects and relations. In contrast, graphs that have a single type of nodes and edges, are often called homogeneous graphs. Measuring similarities among objects is an important task in data mining applications, such as web search, link prediction, and clustering. Currently, several similarity measures are defined for HINs. Most of these measures are based on meta-paths, which show sequences of node classes and edge types along the paths between two nodes. However, meta-paths, which are often designed by domain experts, are hard to enumerate and choose w.r.t. the quality of similarity scores. This makes using existing similarity measures in real applications difficult. To address this problem, we extend SimRank, a well-known similarity measure on homogeneous graphs, to HINs, by introducing the concept of the decay graph. The newly proposed similarity measure is called HowSim, which has the property of being meta-path free, and capturing the structural and semantic similarity simultaneously. The generality and effectiveness of HowSim, and the efficiency of our proposed algorithms for computing HowSim scores, are demonstrated by extensive experiments.

Since inaccuracies commonly exist in many applications, data uncertainty has become an important problem in database systems. To deal with data uncertainty, probabilistic databases can be used to store uncertain data, and querying facilities are provided to yield answers with confidence. However, the results from a query or mining process may not be reliable when the uncertainty propagates in the systems. In this paper, we leverage the power of crowdsourcing by designing a set of Human Intelligence Tasks, or HITs in short, to ask a crowd to improve the quality of uncertain data. In particular, we consider crowds consists of workers with diverse accuracy rates when answering the HITs. We design solutions to maximize the data quality with minimal number of HITs. There are two obstacles for this non-trivial optimization, which lead to very high computational cost for selecting the optimal set of HITs. First, members of a crowd may return incorrect answers with different probabilities. Second, the HITs decomposed from uncertain data are often correlated. We have addressed these challenges in this paper by designing an effective approximation algorithm and an efficient heuristic solution, especially for crowds with diverse individual accuracy rates. To further improve the efficiency, we derive tight lower and upper bounds for effective filtering and estimation. Extensive experiments on both a simulated crowd and a real crowdsourcing platform are conducted to evaluate our solutions.

There has been a dramatic growth of shared mobility applications such as ride-sharing, food delivery, and crowdsourced parcel delivery. Shared mobility refers to transportation services that are shared among users, where a central issue is route planning . Given a set of workers and requests, route planning finds for each worker a route, i.e., a sequence of locations to pick up and drop off passengers/parcels that arrive from time to time, with different optimization objectives. Previous studies lack practicability due to their conflicted objectives and inefficiency in inserting a new request into a route, a basic operation called insertion . In addition, previous route planning solutions fail to exploit the appearance patterns of future requests hidden in historical data for optimization. In this paper, we present a unified formulation of route planning called URPSM. It has a well-defined parameterized objective function which eliminates the contradicted objectives in previous studies and enables flexible multi-objective route planning for shared mobility. We propose two insertion-based frameworks to solve the URPSM problem. The first is built upon the plain-insertion widely used in prior studies, which processes online requests only, whereas the second relies on a new insertion operator called prophet-insertion that handles both online and predicted requests. Novel dynamic programming algorithms are designed to accelerate both insertions to only linear time. Theoretical analysis shows that no online algorithm can have a constant competitive ratio for the URPSM problem under the competitive analysis model, yet our prophet-insertion-based framework can achieve a constant optimality ratio under the instance-optimality model. Extensive experimental results on real datasets show that our insertion-based solutions outperform the state-of-the-art algorithms in both effectiveness and efficiency by a large margin (e.g., up to 30 \( \times \) more effective in the objective and up to 20 \( \times \) faster).

Graph Neural Networks (GNNs) have achieved great success in downstream applications due to their ability to learn node representations. However, in many applications, graphs are not static. They often evolve with changes, such as the adjustment of node attributes or graph structures. These changes require node representations to be updated accordingly. It is non-trivial to apply current GNNs to update node representations in a scalable manner. Recent research proposes two types of solutions. The first solution, sampling neighbors for the influenced nodes, requires expensive processing for each node. The second solution, reducing the repeated computations by merging the shared neighbors, cannot speed up the updating process if the influenced nodes do not share neighbors. Most importantly, the above solutions ignore the hidden representations obtained in the previous times that can be reused to accelerate the representation updating. In this paper, we propose a general cache-based GNN system to accelerate the representation updating. Specifically, we cache a set of hidden representations obtained in the previous times, and then reuse them in the next time. To identify valuable hidden representations, we first estimate the number of hidden representations and their combinations that can be reused. Secondly, we formulate the k-assembler problem that selects k representations to maximize the saved time for the next updating process. Experiments on three real-world graphs show that the cache-based GNN system can significantly speed up the representation updating for various GNNs.

In this paper, we study the privacy-preserving task assignment problem in spatial crowdsourcing, where the locations of both workers and tasks, prior to their release to the server, are perturbed with Geo-Indistinguishability (a differential privacy notion for location-based systems). Different from the previously studied online setting, where each task is assigned immediately upon arrival, we target the batch-based setting, where the server maximizes the number of successfully assigned tasks after a batch of tasks arrive. To achieve this goal, we propose the k-Switch solution, which first divides the workers into small groups based on the perturbed distance between workers/tasks, and then utilizes Homomorphic Encryption (HE) based secure computation to enhance the task assignment. Furthermore, we expedite HE-based computation by limiting the size of the small groups under k. Extensive experiments demonstrate that, in terms of the number of successfully assigned tasks, the k-Switch solution improves batch-based baselines by 5.9X and the existing online solution by 1.74X, with no privacy leak.

The scoring function, which measures the plausibility of triplets in knowledge graphs (KGs), is the key to ensure the excellent performance of KG embedding, and its design is also an important problem in the literature. Automated machine learning (AutoML) techniques have recently been introduced into KG to design task-aware scoring functions, which achieve the state-of-the-art performance in KG embedding. However, the effectiveness of searched scoring functions is still not as good as desired. In this paper, observing that existing scoring functions can exhibit distinct performance on different semantic patterns, we are motivated to explore such semantics by searching relationa-ware scoring functions. But the relation-aware search requires a much larger search space than the previous one. Hence, we propose to encode the space as a supernet and propose an efficient alternative minimization algorithm to search through the supernet in a one-shot manner. Finally, experimental results on benchmark datasets demonstrate that the proposed method can efficiently search relation-aware scoring functions, and achieve better embedding performance than state-of-the-art methods1.

The success of deep learning presents exciting opportunities for reusing pre-trained models from source domains to solve a target task with possibly limited training data. While various pre-trained models have been developed and become available, there is no principled way to select appropriate models for reuse. Although it is suggested that source and target tasks should be sufficiently similar, the calculation of task relevance usually requires extra storage of source training data and great efforts from domain experts, which is impractical in many applications. In this paper, we study the Multi-source Model Selection and Ensemble (MSMSE) problem. Given a collection of source models, we aim to select a subset of source models and develop an ensemble model that achieves the best performance for a target task. An ensemble of multiple models enables a boarder utilization of various underlying source knowledge and leads to better generalization ability. To this end, we present Palette, a generic framework that first selects potentially well-performed models from a source model pool, and then builds an ensemble with refinement. We introduce different model selection strategies that combine multi-armed bandits with adaptive resource allocation and Bayesian optimization techniques to accelerate the selection process. Extensive experimental results validate the effectiveness and efficiency of Palette and our model selection strategies.

Data synopsis is widely adopted to speed-up query processing over large spatial databases. As one of the most popular spatial data synopses, multi-dimensional histograms (MH) have been studied and adopted by modern DBMS and analytical systems for decades. However, existing MH construction techniques highly rely on expert knowledge and statistical assumptions, making them hard to achieve consistently satisfactory performance across different datasets. Inspired by the emerging learned index techniques where the widely used index structures like B-tree can be further improved by integrating simple machine learning models, in this paper, we propose a learned data synopsis technique named Learned Multi-dimensional Histogram (LHist). Compared with the traditional data synopsis techniques, LHist is fully data-driven, easy-to-implement, and has the potential to achieve better storage-accuracy trade-off. On the typical task of range COUNT query estimation, the extensive experimental studies on large-scale real-world datasets and synthetic benchmarks reveal that LHist can outperform the existing synopsis structures in terms of storage cost, query processing efficiency, and estimation accuracy.

To encourage users to buy more products, many online stores offer coupons. When a customer finds that the price of the products she/he wants to order is below the threshold of a coupon, she/he might want to place the order together with others to meet this threshold and enjoy more instant rebates. However, to conduct these orders and deliver products to receivers, users may need to pay extra delivery costs. When an order comprises several receivers' requests, the products in the order should first be delivered from stores to an assigned warehouse, packed into different packages, and delivered to the different receivers. It may be costly than directly delivering products from stores to receivers. For the benefits of buyers, we propose a platform, the Crowdrebate platform, which collects requests from users, groups requests into a set of orders to get more rebates, and relays products to different receivers in an order. The platform will make a profit by getting a proportion from the benefit of the receiver (defined as the rebate minus the extra cost) of orders as its revenue. In this paper, we define the Crowdrebate problem, which aims to maximize the benefit of receivers. We prove the NP-hardness of the Crowdrebate problem. Therefore, we propose a heuristic solution to address the problem. Moreover, we evaluate the effectiveness and efficiency of our algorithm via comprehensive experiments.

Knowledge extraction has become a hot topic recently with the increasing number of applications needed for large-scale knowledge bases (KBs), such as semantic search and QA systems. The goal of knowledge extraction is to extract relations and their arguments from natural language text. Recent research proposes two kinds of solutions. The first one, called Closed IE, tries to construct KB through predefined features or rules with respect to a specific domain. It requires specifying the interested predicates in advance, which restricts its application to the domains where prior knowledge about the interested predicates must be given. The second one, called Open IE, tries to extract facts by using the parsing structure from the unstructured text. However, they cannot avoid extracting redundant facts. Such extractions can hardly be directly used to populate the existing KB. Moreover, many correct extractions are not relevant to the document, which limits the applications to understand the essential information that the document conveys. In this paper, we propose an end-to-end system which takes a target incomplete KB and documents as input. It first performs joint entity and relation linking to the existing KB based on both contexts of document and background KB information. Then it summarizes the extracted facts by considering the relevance to the document and the diversity between them. Extensive experiments over real datasets demonstrate the effectiveness and efficiency of the proposed methods.

Network representation learning (NRL) has been successfully adopted in various data mining and machine learning applications. Random walk based NRL is one popular paradigm, which uses a set of random walks to capture the network structural information, and then employs word2vec models to learn the low-dimensional representations. However, until now there is lack of a framework, which unifies existing random walk based NRL models and efficiently learns from large networks. The main obstacle comes from the diverse random walk models and the inefficient sampling method for the random walk generation. In this paper, we first introduce a new and efficient edge sampler based on Metropolis-Hastings sampling technique, and theoretically show the convergence property of the edge sampler to arbitrary discrete probability distributions. Then we propose a random walk model abstraction, in which users can easily define different transition probability by specifying dynamic edge weights and random walk states. The abstraction is efficiently supported by our edge sampler, since our sampler can draw samples from unnormalized probability distribution in constant time complexity. Finally, with the new edge sampler and random walk model abstraction, we carefully implement a scalable NRL framework called UniNet. We conduct extensive experiments with five random walk based NRL models over eleven real-world datasets, and the results verify the efficiency of UniNet over billion-edge networks.

Metric embeddings have been widely used in approximate algorithms to guarantee the effectiveness of geometric problems. Among the metric embedding techniques, Hierarchically Separated Tree (HST) is one of the most prevalent data structures, which maps the points of the original metric space into a tree-based metric space. A few selected applications of the HST include clustering, task assignment, trip planning, privacy preservation, information routing in wireless sensor networks, etc. Despite the popularity in ensuring the effectiveness, the HST-based solutions can be inefficient in large-scale datasets, since the state-of-the-art construction method has high time and space complexity (O(n3) andO(n2) in the worst-case). Moreover, existing studies overlook the insertion of new points in real applications (deletions can be trivially supported), which can cause the reconstruction of the whole HST. To address these limitations, we focus on designing an efficient index for embedding arbitrary metric spaces by tree metric spaces. Specifically, for construction, we design a dynamic programming-based method, which significantly reduces the time and space complexity toO(n2) andO(n) respectively. For insertion of new points, we propose a new data structure, called Hierarchically Separated Forest (HSF),i.e., a collection of HSTs. An HSF can efficiently support insertion of new points with a tight theoretical guarantee (O(logn)). Finally, extensive experiments demonstrate the superior performance of our proposed algorithms with respect to the effectiveness and the running time. For instance, compared with the state-of-the-art algorithms, our construction method is up to 29.8× faster and our insertion method is up to 491× faster.

Recently, knowledge-graph-enhanced recommendation systems have attracted much attention, since knowledge graph (KG) can help improving the dataset quality and offering rich semantics for explainable recommendation. However, current KG-enhanced solutions focus on analyzing user behaviors on the product level and lack effective approaches to extract user preference towards product category, which is essential for better recommendation because users shopping online normally have strong preference towards distinctive product categories, not merely on products, according to various user studies. Moreover, the existing pure embedding-based recommendation methods can only utilize KGs with a limited size, which is not adaptable to many real-world applications. In this paper, we generalize the recommendation problem with preference mining as a compound knowledge reasoning task and propose a novel multi-agent system, called Mcore, which can promote model performance by mining users’ high-level interests and is adaptable to large KGs. Specifically, we split the overall problem and allocate sub-task to each agent: Coordinate Agent takes charge of recognizing the product-category preference of current user, while Relation Agent and Entity Agent perform KG reasoning cooperatively from a user node towards the preferred categories and terminate at a product node as recommendation. To train this heterogeneous multi-agent system, where agents own various functionalities, we propose an asynchronous reinforcement training pipeline, called Multi-agent Collaborative Learning. The extensive experiments on real datasets demonstrate the effectiveness and adaptability of Mcore on recommendation tasks.

Graph neural networks (GNNs) have gained increasing attention in their great success at graph representation learning. In GNNs, the neighborhood of the target node is aggregated iteratively to capture and learn its local structure and neighbor information. Observing that different nodes often require a distinct number of iterations to better learn the representation, we propose an adaptive and structure-aware graph sampling scheme GraphANGEL for GNNs. However, it is quite challenging because both the suitable range of exploration and the important substructure in the neighborhood are difficult to determine. Exploiting the unique feature of random walk mixing time and various node structural role importance measures, we first propose a lightweight component to flexibly estimate the proper neighborhood exploration depth for each target node. Then we investigate different importance metrics to identify and sample the most structurally critical subgraphs that carry a larger influence in messaging passing. Moreover, since different importance metrics unveil different aspects of the graph, we combine and ensemble various importance measures with attention to boost the final performance. In this manner, our method adaptively and explicitly embeds the structural importance information of a node and its critical neighborhood at the same time for finer structure-aware graph representation learning. Evaluation on the benchmark datasets suggests the competitive performance of GraphANGEL to the state-of-the-art approaches, demonstrating the effectiveness of our adaptive and structure-aware sampling approach.

It has been long debated that eXplainable AI (XAI) is an important technology for model and data exploration, validation, and debugging. To deploy XAI into actual systems, an executable and comprehensive evaluation of the quality of generated explanation is highly in demand. In this paper, we briefly summarize the status quo of the quantitative metrics of different properties of XAI including evaluation on faithfulness, localization, sensitivity check, and stability. With an exhaustive experimental study based on them, we conclude that among all the typical methods we compare, no single explanation method dominates others in all metrics. Nonetheless, Gradient-weighted Class Activation Mapping (Grad-CAM) and Randomly Input Sampling for Explanation (RISE) perform fairly well in most of the metrics. We further present a novel utilization of the evaluation results to diagnose the classification bases for models. Hopefully, this valuable work could serve as a guide for future research.

Deep learning has shown powerful performances in many fields, however its black-box nature hinders its further applications. In response, explainable artificial intelligence emerges, aiming to explain the predictions and behaviors of deep learning models. Among many explanation methods, counterfactual explanation has been identified as one of the best methods due to its resemblance to human cognitive process: to deliver an explanation by constructing a contrastive situation so that human may interpret the underlying mechanism by cognitively demonstrating the difference.

Currently, the most popular method for open-domain Question Answering (QA) adopts "Retriever and Reader" pipeline, where the retriever extracts a list of candidate documents from a large set of documents followed by a ranker to rank the most relevant documents and the reader extracts answer from the candidates. Existing studies take the greedy strategy in the sense that they only use samples for ranking at the current hop, and ignore the global information across the whole documents. In this paper, we propose a purely rank-based framework Thinking Path Re-Ranker (TPRR), which is comprised of Thinking Path Ranker (TPR) for generating document sequences called "a path" and External Path Reranker (EPR) for selecting the best path from candidate paths generated by TPR. Specifically, TPR leverages the scores of a dense model and conditional probabilities to score the full paths. Moreover, to further enhance the performance of the dense ranker in the iterative training, we propose a "thinking" negatives selection method that the top-K candidates treated as negatives in the current hop are adjusted dynamically through supervised signals. After achieving multiple supporting paths through TPR, the EPR component which integrates several fine-grained training tasks for QA is used to select the best path for answer extraction. We have tested our proposed solution on the multi-hop dataset "HotpotQA" with a full wiki set ting, and the results show that TPRR significantly outperforms the existing state-of-the-art models. Moreover, our method has won the first place in the HotpotQA official leaderboard since Feb 1, 2021 under the Fullwiki setting. Code is available at https://gitee.com/mindspore/mindspore/ tree/master/model_zoo/research/nlp/tprr.

The joint entity and relation linking task aims to connect the noun phrases (resp., relational phrases) extracted from natural language documents to the entities (resp., predicates) in general knowledge bases (KBs). This task benefits numerous downstream systems, such as question answering and KB population. Previous works on entity and relation linking rely on the global coherence assumption, i.e., entities and predicates within the same document are highly correlated with each other. However, this assumption is not always valid in many real-world scenarios. Due to KB incompleteness or data sparsity, sparse coherence among the entities and predicates within the same document is common. Moreover, there may exist isolated entities or predicates that are not related to any other linked concepts. In this paper, we propose TENET, a joint entity and relation linking technique, which relaxes the coherence assumption in an unsupervised manner. Specifically, we formulate the joint entity and relation linking task as a minimum-cost rooted tree cover problem on the knowledge coherence graph constructed based on the document. We then propose effective approximation algorithms with pruning strategies to solve this problem and derive the linking results. Extensive experiments on real-world datasets demonstrate the superior effectiveness and efficiency of our method against the state-of-the-art techniques.

In privacy-preserving blockchain systems, to protect a sender's identity of a transaction in privacy-preserving blockchain systems, ring signature (RS) schemes have been widely implemented, which allow users to obscure consumed tokens via including "mixin'' (i.e., chaff tokens). However, recent works point out that existing RS schemes are vulnerable to the "chain-reaction'' analysis, where adversaries eliminate mixins of RSs by utilizing the fact that each token can only be consumed in a RS. By "chain-reaction'' analysis, adversaries can find some definite token-RS pair sets (DTRSs) to confirm the sender's identity of a RS. Besides, the existing RS schemes do not consider the diversity of mixins when generating a RS. Moreover, since the transaction fee is proportional to the number of mixins, a use is motivated to use a RS with the minimum number of mixins. In this paper, we formally define the diversity-aware mixins selection (DA-MS) problem, which aims to generate a RS with the minimum number of mixins satisfying the constraints of its diversity and the anonymity of other RSs. We prove the DA-MS problem is $\#P$ and propose a breadth-first search algorithm to get the optimal solution. Furthermore, to efficiently solve the DA-MS problem, we propose two practical configurations and two approximation algorithms with theoretic guarantees. Through comprehensive experiments on real data sets as well as synthetic data sets, we illustrate the effectiveness and the efficiency of our solutions.

Zero-knowledge set membership (ZKSM) proof is widely used in blockchain to enable private membership attestation. However, existing mechanisms do not fully consider dynamic issues in the blockchain scenario. Particularly, frequent addition/removal of set elements, not only brings the significant cost to keep public parameters up to date to provers and verifiers but also affects mechanism efficiency (e.g., generation time of the proof and verification, etc.). In this paper, we propose DIV to shard elements on blockchain into independent subsets with the same cardinality to reduce the effect of dynamic issues. However, due to the diverse proof frequency, an improper element-set assignment can result in frequently used elements being easily inferred and corrupted. Thus, we formalize the assignment problem under both element addition and removal cases as two optimization problems and prove their NP-hardness. For each problem, we consider two cases if each element proof frequency is known in advance by the set maintainer or not, and propose solutions with theoretical guarantees. We implement DIV on both Merkle tree and RSA-based ZKSM mechanisms to evaluate its efficiency and effectiveness and apply DIV on a ZKSMbased application named zkSync to demonstrate its applicability. Results show that DIV can achieve O(1) time/space cost on ZKSM under dynamic situations while protecting the information about frequently used elements. It also notably reduces the system latency of zkSync.

Graph Convolutional Networks (GCNs) have become state-of-the-art methods in many supervised and semi-supervised graph representation learning scenarios. In order to achieve satisfactory performance, GCNs require a sufficient amount of labeled data. However, in real-world scenarios, labeled data is often expensive to obtain. Therefore, we propose ALG, a novel Active Learning framework for GCNs, which employs domain-specific intelligence to achieve much higher performance and efficiency compared to the generic AL frameworks. First, by decoupling GCN models, ALG serves as an effective and efficient AL framework for measuring and combining node representativeness and informativeness. Second, by exploiting the characteristic of the reception field in GCNs, ALG considers both the importance and correlation of nodes by proposing a new node selection metric that maximizes the effective reception field (ERF). We prove that this ERF maximization problem is NP-hard and provide an efficient algorithm accompanied with a provable approximation guarantee. The empirical studies on four public datasets demonstrate that ALG can significantly improve both the performance and efficiency of active learning for GCNs.

Anomaly detection in time series is a research area of increasing importance. In order to safeguard the availability and stability of services, large companies need to monitor various time-series data to detect anomalies in real time for troubleshooting, thereby reducing potential economic losses. However, in many practical applications, time-series anomaly detection is still an intractable problem due to the huge amount of data, complex data patterns, and limited computational resources. SPOT is an efficient streaming algorithm for anomaly detection, but it is only sensitive to extreme values in the whole data distribution. In this paper, we propose FluxEV, a fast and effective unsupervised anomaly detection framework. By converting the non-extreme anomalies to extreme values, our framework addresses the limitation of SPOT and achieves a huge improvement in the detection accuracy. Moreover, Method of Moments is adopted to speed up the parameter estimation in the automatic thresholding. Extensive experiments show that FluxEV greatly outperforms the state-of-the-art baselines on two large public datasets while ensuring high efficiency.

Tensor, an extension of the vector and matrix to the multi-dimensional case, is a natural way to describe the N-ary relational data. Recently, tensor decomposition methods have been introduced into N-ary relational data and become state-of-the-art on embedding learning. However, the performance of existing tensor decomposition methods is not as good as desired. First, they suffer from the data-sparsity issue since they can only learn from the N-ary relational data with a specific arity, i.e., parts of common N-ary relational data. Besides, they are neither effective nor efficient enough to be trained due to the over-parameterization problem. In this paper, we propose a novel method, i.e., S2S, for effectively and efficiently learning from the N-ary relational data. Specifically, we propose a new tensor decomposition framework, which allows embedding sharing to learn from facts with mixed arity. Since the core tensors may still suffer from the over-parameterization, we propose to reduce parameters by sparsifying the core tensors while retaining their expressive power using neural architecture search (NAS) techniques, which can search for data-dependent architectures. As a result, the proposed S2S not only guarantees to be expressive but also efficiently learns from mixed arity. Finally, empirical results have demonstrated that S2S is efficient to train and achieves state-of-the-art performance. 1

With the rapid development of smart mobile devices, the car-hailing platforms (e.g., Uber or Lyft) have attracted much attention from the academia and the industry. In this paper, we consider a dynamic car-hailing problem, namely maximum revenue vehicle dispatching (MRVD), in which rider requests dynamically arrive and drivers need to serve riders such that the entire revenue of the platform is maximized. We prove that the MRVD problem is NP-hard and intractable. To handle the MRVD problem, we propose a queueing-based vehicle dispatching framework, which first uses existing machine learning models to predict the future vehicle demand of each region, then estimates the idle time periods of drivers through a double-sided queueing model for each region. With the information of the predicted vehicle demands and estimated idle time periods of drivers, we propose two batch-based vehicle dispatching algorithms to efficiently assign suitable drivers to riders such that the expected overall revenue of the platform is maximized during each batch processing. Through extensive experiments, we demonstrate the efficiency and effectiveness of our proposed approaches over both real and synthetic datasets. In summary, our methods can achieve 3% ~ 10% increase on overall revenue without sacrificing on running speed compared with the state-of-the-art solutions.

Recently, deep neural networks (DNNs) have achieved great success in various applications, where low inference latency is important. Existing solutions either manually tune the kernel library or utilize search-based compilation to reduce the operator latency. However, manual tuning requires significant engineering effort, and the huge search space makes the search cost of the search-based compilation unaffordable in some situations. In this work, we propose ETO, a framework for speeding up DNN operator optimization based on reusing the information of performant tensor programs. Specifically, ETO defines conditions for the information reuse between two operators. For operators satisfying the conditions, based on the performant tensor program information of one operator, ETO uses a reuse-based tuner to significantly prune the search space of the other one, and keeps optimization effectiveness at the same time. In this way, for a set of operators, ETO first determines the information reuse relationships among them to reduce the total search time needed, and then tunes the operators either by the backend compiler or by the reuse-based tuner accordingly. ETO further increases the reuse opportunities among the operators by injecting extra operators as bridges between two operators which do not satisfy the reuse conditions. Compared with various existing methods, the experiments show that ETO is effective and efficient in optimizing DNN operators.

When considering uncertain bipartite networks, the number of instances of the popular graphlet structure the butterfly may be used as an important metric to quickly gauge information about the network. This Uncertain Butterfly Count has practical usages in a variety of areas such as biomedical/biological fields, E-Commerce and road networks. In this paper we formally define the uncertain butterfly structure (in which the existential probability of the butterfly is greater than or equal to some user-defined threshold t ) as well as the Uncertain Butterfly Counting Problem (to determine the number of unique instances of this structure on any uncertain bipartite network). We then examine exact solutions by proposing a non-trivial baseline (UBFC) as well as an improved solution (IUBFC) which reduces the time complexity and employs heuristics to further reduce the runtime in practice. In addition to exact solutions, we propose two approximate solutions via sampling, UBS and PES , which can be used to quickly estimate the Uncertain Butterfly Count, a powerful tool when the exact count is unnecessary. Using a range of networks with different edge existential probability distributions, we validate the efficiency and effectiveness of our solutions.

Online Social Network (OSN) providers usually conduct advertising campaigns by inserting social ads into promoted posts. Whenever a user engages in a promoted ad, she may further propagate the promoted ad to her followers recursively and the propagation process is known as the word-of-mouth effect. In order to spread the promotion cascade widely and efficiently, the OSN provider often tends to select the influencers, who normally have large audiences over the social network, to initiate the advertising campaign. This marketing model, also termed as influencer marketing, has been gaining increasing traction and investment and is rapidly becoming one of the most widely-used channels in digital marketing. In this paper, we formulate the problem for the OSN provider to derive the influence contributions of influencers given the campaign result, considering the viral propagation of the ads, namely influence contribution allocation (ICA) . We make a connection between ICA and the concept of Shapley value in cooperative game theory to reveal the rationale behind ICA. A naive method to obtain the solution to ICA is to enumerate all possible cascades delivering the campaign result, resulting in an exponential number of potential cascades, which is computationally intractable. Moreover, generating a cascade producing the exact campaign result is non-trivial. Facing the challenges, we develop an exact solution in linear time under the linear threshold (LT) model, and devise a fully polynomial-time randomized approximation scheme (FPRAS) under the independent cascade (IC) model. Specifically, under the IC model, we propose an efficient approach to estimate the expected influence contribution in probabilistic graphs modeling OSNs by designing a scalable sampling method with provable accuracy guarantees. We conduct extensive experiments and show that our algorithms yield solutions with remarkably higher quality over several baselines and improve the sampling efficiency significantly.

In recent years, online Event Based Social Network (EBSN) platforms have become increasingly popular. One typical task of EBSN platforms is to help users make suitable and personalized plans for participating in different interesting social events. Existing techniques either ignore the minimum-participant requirement constraint for each event, which is crucially needed for some events to be held successfully, or assume that events would not change once announced. In this paper, we address the above inadequacies of existing EBSN techniques. We formally define the Global Event Planning with Constraints (GEPC) problem, and its incremental variant. Since these problems are NP-hard, and provide approximate solutions. Finally, we verify the effectiveness and efficiency of our proposed algorithms through extensive experiments over real and synthetic datasets.

The group nearest neighbor (GNN) search on a road network$G_r$, i.e., finding the spatial objects as activity assembly points with the smallest sum of distances to query users on$G_r$, has been extensively studied; however, previous works neglected the fact that social relationships among query users, which ensure the maximally favorable atmosphere in the activity, can play an important role in GNN queries. Meanwhile, the ratings of spatial objects can also be used as recommended guidelines. Many real-world applications, such as location-based social networking services, require such queries. In this paper, we study two new problems: (1) a GNN search on a road network that incorporates cohesive social relationships (CGNN) and (2) a CGNN query under multi-criteria (MCGNN). Specifically, both the query users of highest closeness and the corresponding top-$j$objects are retrieved. To address critical challenges on the effectiveness of results and the efficiency of computation over large road-social networks: (1) for CGNN, we propose a filtering-and-verification framework. During filtering, we prune substantial unpromising users and objects using social and geospatial constraints. During verification, we obtain the object candidates, among which the top$j$are selected, with respect to the qualified users; (2) for MCGNN, we propose threshold-based selection and expansion strategies, where different strict boundaries are proposed to ensure that correct top-$j$objects are found early. Moreover, we further optimize search strategies to improve query performance. Finally, experimental results on real social and road networks significantly demonstrate the efficiency and efficacy of our solutions.

In-memory databases (IMDBs) are gaining increasing popularity in big data applications, where clients commit updates intensively. Specifically, it is necessary for IMDBs to have efficient snapshot performance to support certain special applications (e.g., consistent checkpoint, HTAP). Formally, the in-memory consistent snapshot problem refers to taking an in-memory consistent time-in-point snapshot with the constraints that 1) clients can read the latest data items and 2) any data item in the snapshot should not be overwritten. Various snapshot algorithms have been proposed in academia to trade off throughput and latency, but industrial IMDBs such as Redis adhere to the simple fork algorithm. To understand this phenomenon, we conduct comprehensive performance evaluations on mainstream snapshot algorithms. Surprisingly, we observe that the simple fork algorithm indeed outperforms the state-of-the-arts in update-intensive workload scenarios. On this basis, we identify the drawbacks of existing research and propose two lightweight improvements. Extensive evaluations on synthetic data and Redis show that our lightweight improvements yield better performance than fork, the current industrial standard, and the representative snapshot algorithms from academia. Finally, we have opensourced the implementation of all the above snapshot algorithms so that practitioners are able to benchmark the performance of each algorithm and select proper methods for different application scenarios.

With the rapid development of smartphones, spatial crowdsourcing platforms are getting popular. A foundational research of spatial crowdsourcing is to allocate micro-tasks to suitable crowd workers. Many existing studies focus on the offline scenario, where all the spatiotemporal information of micro-tasks and crowd workers is given. In this paper, we focus on the online scenario and identify a more practical micro-task allocation problem, called theGlobalOnlineMicro-taskAllocation in spatial crowdsourcing(GOMA) problem. We first extend the state-of-the-art algorithm for the online maximum weighted bipartite matching problem to the GOMA problem as the baseline algorithm. Although the baseline algorithm provides a theoretical guarantee for the worst case, its average performance in practice is not good enough since the worst case happens with a very low probability in the real world. Thus, we consider the average performance of online algorithms,a.k.a.random order model. We propose a two-phase-based framework, based on which we present the TGOA algorithm with a$\frac{1}{4}$-competitive ratio under the random order model. To improve its efficiency, we further design the TGOA-Greedy and TGOA-OP algorithm following this framework, which runs faster than the TGOA algorithm with a competitive ratio of$\frac{1}{8}$and$\frac{1}{4}$, respectively. We also revisit the average performance of Greedy, which has long been considered as the worst due to its unbounded competitive ratio in the worst case. Finally, we verify the effectiveness and efficiency of the proposed methods through extensive experiments on synthetic and real datasets.

With the rapid development of crowdsourcing platforms that aggregate the intelligence of Internet workers, crowdsourcing has been widely utilized to address problems that require human cognitive abilities. Considering great dynamics of worker arrival and departure, it is of vital importance to design a task assignment scheme to adaptively select the most beneficial tasks for the available workers. In this paper, in order to make the most efficient utilization of the worker labor and balance the accuracy of answers and the overall latency, we a) develop a parameter estimation model that assists in estimating worker expertise, question easiness, and answer confidence; b) propose a quality-assured synchronized task assignment scheme that executes in batches and maximizes the number of potentially completed questions (MCQ) within each batch. We prove that MCQ problem is NP-hard and present two greedy approximation solutions to address the problem. The effectiveness and efficiency of the approximation solutions are further evaluated through extensive experiments on synthetic and real datasets. The experimental results show that the accuracy and the overall latency of the MCQ approaches outperform the existing online task assignment algorithms in the synchronized task assignment scenario.

Measuring similarity among data objects is important in data analysis and mining. SimRank is a popular link-based similarity measurement among nodes in a graph. To compute the all-pairs SimRank matrix accurately, iterative methods are usually used. For static graphs, current iterative solutions are not efficient enough, both in time and space, due to the unnecessary cost and storage by the nature of iterative updating. For dynamic graphs, all current incremental solutions for updating the SimRank matrix are based on an approximated SimRank definition, and thus have no accuracy guarantee. In this paper, we propose a novel local push based algorithm for computing and tracking all-pairs SimRank. Furthermore, we develop an iterative parallel two-step framework for local push to take advantage of modern hardwares with multicore CPUs. We show that our algorithms outperform the state-of-the-art methods.

Measuring similarities among different nodes is important in graph analysis tasks, such as link prediction, and recommendation. Among different similarity measures, SimRank is one of the most popular and promising ones, and has received a lot of research attention. While most current studies focus on single-pair, single-source/top-k, and all-pairs SimRank computation, few of them have studied finding similar pairs given a set of node pairs, which has attractive applications in personalized search and recommendation tasks. In this paper, we present Carmo, an efficient algorithm for retrieving the top-k similarities from an arbitrary set of pairs. In addition, we introduce two types of indexes to boost the efficiency of Carmo: one is hub-based, the other is tree-based. We show the effectiveness and efficiency of our proposed methods by extensive experiments.

Learning network embeddings has attracted growing attention in recent years. However, most of the existing methods focus on homogeneous networks, which cannot capture the important type information in heterogeneous networks. To address this problem, in this paper, we propose TransN, a novel multi-view network embedding framework for heterogeneous networks. Compared with the existing methods, TransN is an unsupervised framework which does not require node labels or user-specified meta-paths as inputs. In addition, TransN is capable of handling more general types of heterogeneous networks than the previous works. Specifically, in our framework TransN, we propose a novel algorithm to capture the proximity information inside each single view. Moreover, to transfer the learned information across views, we propose an algorithm to translate the node embeddings between different views based on the dual-learning mechanism, which can both capture the complex relations between node embeddings in different views, and preserve the proximity information inside each view during the translation. We conduct extensive experiments on real-world heterogeneous networks, whose results demonstrate that the node embeddings generated by TransN outperform those of competitors in various network mining tasks.

With the development of mobile communication techniques, spatial crowdsourcing has become popular recently. A typical topic of spatial crowdsourcing is task assignment, which assigns crowd workers to users' requests in real time and maximizes the total revenue. However, it is common that the available crowd workers over a platform are too far away to serve the requests, so some user requests may be rejected or responded at high money cost after long waiting. Fortunately, the neighbors of a platform usually have available resources for the same services. Collaboratively conducting the task allocation among different platforms can greatly improve the quality of services, but have not been investigated yet. In this paper, we propose a Cross Online Matching (COM), which enables a platform to "borrow" unoccupied crowd workers from other platforms for completing the user requests. We propose two algorithms, deterministic cross online matching (DemCOM) and randomized cross online matching (RamCom) for COM. DemCOM focuses on the largest obtained revenue in a greedy manner, while RamCom considers the trade-off between the obtained revenue and the probability of request being accepted by the borrowed workers. Extensive experimental results verify the effectiveness and efficiency of our algorithms.

As an important operator for spatial data analytics, Region of Interest (ROI) query is of great importance in many location-based services such as event detection, location recommendation and smart transportation. To address the challenge of conducting ROI queries on the increasingly complex spatial data, we present RIDE, an efficient and effective system for generalized ROI Discovery and Exploration. Different from existing studies and systems, RIDE supports a large spectrum of region score functions and query geometries, enabling customized ROI queries for different application scenarios. This demonstration proposal introduces the basic concept of ROI queries and key components of the RIDE system, including data storage and indexing, ROI query processing and optimization and user interface.

Ubiquitous smart devices and high-quality wireless networks enable people to participate in spatial crowdsourcing tasks easily, which require workers to physically move to specific locations to conduct their assigned tasks. Spatial crowdsourcing has attracted much attention from both academia and industry. In this paper, we consider a spatial crowdsourcing scenario, where the tasks may have some dependencies among them. Specifically, one task can only be dispatched when its dependent tasks have already been assigned. In fact, task dependencies are quite common in many real-life applications, such as house repairing and holding sports games. We formally define the dependency-aware spatial crowdsourcing (DA-SC), which focuses on finding an optimal worker-and-task assignment under the constraints of dependencies, skills of workers, moving distances and deadlines to maximize the successfully assigned tasks. We prove that the DA-SC problem is NP-hard and thus intractable. Therefore, we propose two approximation algorithms, including a greedy approach and a game-theoretic approach, which can guarantee the approximate bounds of the results in each batch process. Through extensive experiments on both real and synthetic data sets, we demonstrate the efficiency and effectiveness of our DA-SC approaches.

With spatial crowdsourcing applications such as Uber and Waze deeply penetrated into everyday life, there is a growing concern to protect user privacy in spatial crowdsourcing. Particularly, locations of workers and tasks should be properly processed via certain privacy mechanism before reporting to the untrusted spatial crowdsourcing server for task assignment. Privacy mechanisms typically permute the location information, which tends to make task assignment ineffective. Prior studies only provide guarantees on privacy protection without assuring the effectiveness of task assignment. In this paper, we investigate privacy protection for online task assignment with the objective of minimizing the total distance, an important task assignment formulation in spatial crowdsourcing. We design a novel privacy mechanism based on Hierarchically Well-Separated Trees (HSTs). We prove that the mechanism is ε-Geo-Indistinguishable and show that there is a task assignment algorithm with a competitive ratio of O(ε1/4log N log2k), where ε is the privacy budget, N is the number of predefined points on the HST, and k is the matching size. Extensive experiments on synthetic and real datasets show that online task assignment under our privacy mechanism is notably more effective in terms of total distance than under prior differentially private mechanisms.

Heterogeneous information networks (HINs) are usually used to model information systems with multi-type objects and relations. Measuring the similarity among objects is an important task in data mining applications. Currently, several similarity measures are defined for HIN. Most of these measures are based on meta-paths, which show sequences of node classes and edge types along the paths between two nodes. However, meta-paths, which are often designed by domain experts, are hard to enumerate and choose w.r.t. the quality of the similarity scores. This makes the existing similarity measures difficult to use in real applications. To address this problem, we extend SimRank, a well-known similarity measure for homogeneous graphs, to HINs, by introducing the concept of decay graph. The newly proposed relevance measure is called HowSim, which has the property of being meta-path free, and capturing the structural and semantic similarity simultaneously. The generality and effectiveness of HowSim, are demonstrated by extensive experiments.

Scoring functions (SFs), which measure the plausibility of triplets in knowledge graph (KG), have become the crux of KG embedding. Lots of SFs, which target at capturing different kinds of relations in KGs, have been designed by humans in recent years. However, as relations can exhibit complex patterns that are hard to infer before training, none of them can consistently perform better than others on existing benchmark data sets. In this paper, inspired by the recent success of automated machine learning (AutoML), we propose to automatically design SFs (AutoSF) for distinct KGs by the AutoML techniques. However, it is non-trivial to explore domain-specific information here to make AutoSF efficient and effective. We firstly identify a unified representation over popularly used SFs, which helps to set up a search space for AutoSF. Then, we propose a greedy algorithm to search in such a space efficiently. The algorithm is further sped up by a filter and a predictor, which can avoid repeatedly training SFs with same expressive ability and help removing bad candidates during the search before model training. Finally, we perform extensive experiments on benchmark data sets. Results on link prediction and triplets classification show that the searched SFs by AutoSF, are KG dependent, new to the literature, and outperform the state-of- the-art SFs designed by humans.

Graph queries have emerged as one of the fundamental techniques to support modern search services, such as PageRank web search, social networking search and knowledge graph search. As such graphs are maintained globally and very huge (e.g., billions of nodes), we need to efficiently process graph queries across multiple geographically distributed datacenters, running geo-distributed graph queries. Existing graph computing frameworks may not work well for geographically distributed datacenters, because they implement a Bulk Synchronous Parallel model that requires excessive inter-datacenter transfers, thereby introducing extremely large latency for query processing. In this paper, we propose GeoGraph --a universal framework to support efficient geo-distributed graph query processing based on clustering datacenters and meta-graph, while reducing the inter-datacenter communication. Our new framework can be applied to many types of graph algorithms without any modification. The framework is developed on the top of Apache Giraph. The experiments were conducted by applying four important graph queries, i.e., shortest path, graph keyword search, subgraph isomorphism and PageRank. The evaluation results show that our proposed framework can achieve up to 82% faster convergence, 42% lower WAN bandwidth usage, and 45% less total monetary cost for the four graph queries, with input graphs stored across ten geo-distributed datacenters.

Recent years witnessed the emergence of various applications on knowledge graphs, which are often represented as RDF graphs. However, due to the lack of data schema and the complexity of SPARQL language, there is usually a gap between the user's real desire and the actual meaning of a SPARQL query, especially when the query itself is complicated. In this paper, we try to narrow this gap by modifying a given query with a set of modifiers, so that its result approaches a user-provided example set. Specifically, we model this problem as two individual sub-problems, query-restricting, and query-relaxing, both of which are shown to be NP-hard. We further prove that unless P=NP, query-restricting has no polynomial-time approximation scheme (PTAS), and query-relaxing has no polynomial-time constant-factor approximation algorithm. Despite their hardness, we propose a (1-1/ε)-approximation method for query-restricting and 2 heuristics for query-relaxing. Extensive experiments have been conducted on real-world knowledge graphs to evaluate the effectiveness and efficiency of our proposed solutions.

Second-order random walk is an important technique for graph analysis. Many applications use it to capture higher-order patterns in the graph, thus improving the model accuracy. However, the memory explosion problem of this technique hinders it from analyzing large graphs. When processing a billion-edge graph like Twitter, existing solutions (e.g., alias method) of the second-order random walk may take up 1796TB memory. Such high memory overhead comes from the memory-unaware strategies for node sampling across the graph. In this paper, to clearly study the efficiency of various node sampling methods in the context of second-order random walk, we design a cost model, and then propose a new node sampling method following the acceptance-rejection paradigm to achieve a better balance between memory and time cost. Further, to guarantee the efficiency of the second-order random walk within arbitrary memory budgets, we propose a memory-aware framework on the basis of the cost model. The framework applies a cost-based optimizer to assign desirable node sampling method for each node in the graph within a memory budget while minimizing the time cost. Finally, we provide general programming interfaces for users to benefit from the memory-aware framework easily. The empirical studies demonstrate that our memory-aware framework is robust with respect to memory and is able to achieve considerable efficiency by reducing 90% of the memory cost.

Graph Convolutional Network (GCN) is a widely used method for learning from graph-based data. However, it fails to use the unlabeled data to its full potential, thereby hindering its ability. Given some pseudo labels of the unlabeled data, the GCN can benefit from this extra supervision. Based on Knowledge Distillation and Ensemble Learning, lots of methods use a teacher-student architecture to make better use of the unlabeled data and then make a better prediction. However, these methods introduce unnecessary training costs and a high bias of student model if the teacher's predictions are unreliable. Besides, the final ensemble gains are limited due to limited diversity in the combined models. Therefore, we propose Reliable Data Distillation, a reliable data driven semi-supervised GCN training method. By defining the node reliability and edge reliability in a graph, we can make better use of high quality data and improve the graph representation learning. Furthermore, considering the data reliability and data importance, we propose a new ensemble learning method for GCN and a novel Self-Boosting SSL Framework to combine the above optimizations. Finally, our extensive evaluation of Reliable Data Distillation on real-world datasets shows that our approach outperforms the state-of-the-art methods on semi-supervised node classification tasks.

Measuring similarities among different nodes is important in graph analysis. SimRank is one of the most popular similarity measures. Given a graph G ( V , E ) and a source node u , a single-source Sim-Rank query returns the similarities between u and each node v ∈ V. This type of query is often used in link prediction, personalized recommendation and spam detection. While dealing with a large graph is beyond the ability of a single machine due to its limited memory and computational power, it is necessary to process single-source SimRank queries in a distributed environment, where the graph is partitioned and distributed across multiple machines. However, most current solutions are based on shared-memory model, where the whole graph is loaded into a shared memory and all processors can access the graph randomly. It is difficult to deploy such algorithms on shared-nothing model. In this paper, we present DISK, a distributed framework for processing single-source SimRank queries. DISK follows the linearized formulation of SimRank, and consists of offline and online phases. In the offline phase, a tree-based method is used to estimate the diagonal correction matrix of SimRank accurately, and in the online phase, single-source similarities are computed iteratively. Under this framework, we propose different optimization techniques to boost the indexing and queries. DISK guarantees both accuracy and parallel scalability, which distinguishes itself from existing solutions. Its accuracy, efficiency, parallel scalability and scalability are also verified by extensive experimental studies. The experiments show that DISK scales up to graphs of billions of nodes and edges, and answers online queries within seconds, while ensuring the accuracy bounds.

Community search in heterogeneous information networks (HINs) has attracted much attention in graph analysis. Given a vertex, the goal is to find a densely-connected sub-graph that contains the vertex. In practice, the user may need to restrict the number of connections between vertices, but none of the existing methods can handle such queries. In this paper, we propose the relational constraint that allows the user to specify fine-grained connection requirements between vertices. Base on this, we define the relational community as well as the problems of detecting and searching relational communities, respectively. For the detection problem, we propose an efficient solution that has near-linear time complexity. For the searching problem, although it is shown to be NP-hard and even hard-to-approximate, we devise two efficient approximate solutions. We further design the round index to accelerate the searching algorithm and show that it can handle dynamic graphs by its nature. Extensive experiments on both synthetic and real-world graphs are conducted to evaluate both the effectiveness and efficiency of our proposed methods.

Nowadays, most openly available knowledge bases (KBs) are incomplete, since they are not synchronized with the emerging facts happening in the real world. Therefore, knowledge base population (KBP) from external data sources, which extracts knowledge from unstructured text to populate KBs, becomes a vital task. Recent research proposes two types of solutions that partially address this problem, but the performance of these solutions is limited. The first solution, dynamic KB construction from unstructured text, requires specifications of which predicates are of interest to the KB, which needs preliminary setups and is not suitable for an in-time population scenario. The second solution, Open Information Extraction (Open IE) from unstructured text, has limitations in producing facts that can be directly linked to the target KB without redundancy and ambiguity. In this paper, we present an end-to-end system, KBPearl, for KBP, which takes an incomplete KB and a large corpus of text as input, to (1) organize the noisy extraction from Open IE into canonicalized facts; and (2) populate the KB by joint entity and relation linking, utilizing the context knowledge of the facts and the side information inferred from the source text. We demonstrate the effectiveness and efficiency of KBPearl against the state-of-the-art techniques, through extensive experiments on real-world datasets.

The dramatic development of shared mobility in food delivery, ridesharing, and crowdsourced parcel delivery has drawn great concerns. Specifically, shared mobility refers to transferring or delivering more than one passenger/package together when their traveling routes have common sub-routes or can be shared. A core problem for shared mobility is to plan a route for each driver to fulfill the requests arriving dynamically with given objectives. Previous studies greedily and incrementally insert each newly coming request to the most suitable worker with a minimum travel cost increase, which only considers the current situation and thus not optimal. In this paper, we propose a demand-aware route planning (DARP) for shared mobility services. Based on prediction, DARP tends to make optimal route planning with more information about requests in the future. We prove that the DARP problem is NP-hard, and further show that there is no polynomial-time deterministic algorithm with a constant competitive ratio for the DARP problem unless P=NP. Hence, we devise an approximation algorithm to realize the insertion operation for our goal. With the insertion algorithm, we devise a prediction based solution for the DARP problem. Extensive experiment results on real datasets validate the effectiveness and efficiency of our technique.

Ridesharing services have gained global popularity as a convenient, economic, and sustainable transportation mode in recent years. One fundamental challenge in these services is planning the shared-routes ( i.e. , sequences of origins and destinations) among the passengers for the vehicles, such that the platform's total revenue is maximized. Though many methods can solve this problem, their effectiveness is still far from optimal on either empirical study ( e.g. , over 31% lower total revenue than our approach) or theoretical study ( e.g. , arbitrarily bad or impractical theoretical guarantee). In this paper, we study the shared-route planning queries in ridesharing services and focus on designing efficient algorithms with good approximation guarantees. Particularly, our idea is to iteratively search the most profitable route among the unassigned requests for each vehicle, which is simpler than the existing methods. Unexpectedly, we prove this simple method has an approximation ratio of 0.5 to the optimal result. Moreover, we also design an index called additive tree to improve the efficiency and apply randomization to improve the approximation guarantee. Finally, experimental results on two real datasets demonstrate that our additive-tree-based approach outperforms the state-of-the-art algorithms by obtaining up to 31.4%--127.4% higher total revenue.

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.

Group recommendation has become highly demanded when users communicate in the forms of group activities in online sharing communities. These group activities include student group study, family TV program watching, friends travel decision, etc. Existing group recommendation techniques mainly focus on the small user groups. However, online sharing communities have enabled group activities among thousands of users. Accordingly, recommendation over large groups has become urgent. In this paper, we propose a new framework to accomplish this goal by exploring the group interests and the connections between group users. We first divide a big group into different interest subgroups, each of which contains users closely connected with each other and sharing the similar interests. Then, for each interest subgroup, our framework exploits the connections between group users to collect a comparably compact potential candidate set of media-user pairs, on which the collaborative filtering is performed to generate an interest subgroup-based recommendation list. After that, a novel aggregation function is proposed to integrate the recommended media lists of all interest subgroups as the final group recommendation results. Extensive experiments have been conducted on two real social media datasets to demonstrate the effectiveness and efficiency of our proposed approach.

Incomplete information often occurs along with many database applications, e.g., in data integration, data cleaning, or data exchange. The idea of data imputation is often to fill the missing data with the values of its neighbors who share the same/similar information. Such neighbors could either be identified certainly by editing rules or extensively by similarity relationships. Owing to data sparsity, the number of neighbors identified by editing rules w.r.t. value equality is rather limited, especially in the presence of data values with variances. To enrich the imputation candidates, a natural idea is to extensively consider the neighbors with similarity relationship. However, the candidates suggested by these (heterogenous) similarity neighbors may conflict with each other. In this paper, we propose to utilize the similarity rules with tolerance to small variations (instead of the aforesaid editing rules with strict equality constraints) to rule out the invalid candidates provided by similarity neighbors. To enrich the data imputation, i.e., imputing the missing values more, we study the problem of maximizing the missing data imputation. Our major contributions include (1) the NP-hardness analysis on solving as well as approximating the problem, (2) exact algorithms for tackling the problem, and (3) efficient approximation with performance guarantees. Experiments on real and synthetic data sets demonstrate the superiority of our proposal in filling accuracy. We also demonstrate that the record matching application is indeed improved, after applying the proposed imputation.

Schema matching is a central challenge for data integration systems. Inspired by the popularity and the success of crowdsourcing platforms, we explore the use of crowdsourcing to reduce the uncertainty of schema matching. Since crowdsourcing platforms are most effective for simple questions, we assume that each Correspondence Correctness Question (CCQ) asks the crowd to decide whether a given correspondence should exist in the correct matching. Furthermore, members of a crowd may sometimes return incorrect answers with different probabilities. Accuracy rates of individual crowd workers can be attributes of CCQs as well as evaluations of individual workers. We prove that uncertainty reduction equals to entropy of answers minus entropy of crowds and show how to obtain lower and upper bounds for it. We propose frameworks and efficient algorithms to dynamically manage the CCQs to maximize the uncertainty reduction within a limited budget of questions. We develop two novel approaches, namely “Single CCQ” and “Multiple CCQ”, which adaptively select, publish, and manage questions. We verify the value of our solutions with simulation and real implementation.

Recently, spatial crowdsourcing has been drawing increasing attention with its great potential in collecting geographical knowledge. The system throughput (number of assigned tasks) and workers' travel distance are two of many important factors in spatial crowdsourcing, and the improvement to one of them usually means the sacrifice of the other. However, most existing works resolve the trade-off between these two factors by simply targeting tasks within a bounding circle of each worker. In this paper, we compromise between the throughput and the distance by formulating these two factors as score terms in the objective function. This flexible formulation has the advantages of abandoning distant tasks and minimizing workers' travel distance for reachable tasks. Aside from that, we study the multi-campaign scenario of spatial crowdsourcing, which is not uncommon in practical applications while not yet discussed in existing works. The worker diversity of the campaigns is considered to be another goal and formulated as another score term in the objective function. Subsequently, the problem of multi-campaign oriented spatial crowdsourcing is to maximize the objective function comprised by the aforementioned score terms. We prove that the problem is NP-hard, thus, we propose several approximation solutions. Extensive experiments have been conducted to confirm the effectiveness and the efficiency of the devised solutions.

Maximum Range-Sum (MaxRS) query is an important operator in spatial database for retrieving regions of interest (ROIs). Given a rectangular query size a × b and a set of spatial objects associated with positive weights, MaxRS retrieves rectangular regions Q of size a × b, such that the sum of object weights covered by Q (i.e., range-sum) is maximized. Due to the inaccuracy of the location acquisition, the collected locations of spatial objects are inherently uncertain and imprecise, which can be modeled by uncertain objects. In this paper, we propose a Probabilistic Maximum Range-Sum (PMaxRS) query over uncertain spatial objects, which obtains a set γ* of rectangles such that the probability that each region Q ϵ γ* has the maximum range-sum exceeds a user-specified threshold Pt. We show that determining whether a given region Q is #P-complete. To tackle the hardness, we introduce the PMaxRS_Framework based on pruning and refinement strategies. In the pruning step, we propose a candidate generation technique to reduce the search space. In the refinement step, we design an efficient sampling-based approximation algorithm to verify the remaining candidate regions. Extensive experiments are conducted to demonstrate the effectiveness and efficiency of our algorithms.

With the increasing awareness towards protecting environment, people are paying more attention to the electric vehicles (EVs). Accompanying the rapid growing number of EVs, challenges raise at the same time about how to place EV chargers (EVC), within a city, to satisfy multiple types of charging demand. To provide a better EVC station deployment plan to benefit the whole society, we propose a problem called Social-Aware Optimal Electric Vehicle Charger Deployment (SOCD) on road network. The SOCD problem is hard and different from existing work in three aspects, 1) we assume that the charging demand should be satisfied not only in urban areas but also in relatively rural areas; 2) our work is the first one that considers an EVC station should have multiple types of charging plugs, which is more reasonable in real world; 3) different from the regional deployment solutions in previous literature, our SOCD directly works on a real road network and EVC stations are placed at appropriate POIs laying on the road network. We show that the SOCD problem is NP-hard. To deal with the hardness, we design two heuristic algorithms whose efficiency and effectiveness can be experimentally demonstrated. Furthermore, we investigate the incremental case, that is, given an existing EVC station deployment plan and extra more budget, we need to decide where and how many to place more chargers. Finally, we conduct extensive experiments on real road network of Shanghai to demonstrate both effectiveness and efficiency of our algorithms.

With the rapid development of smart mobile devices, the car-hailing platforms (e.g., Uber or Lyft) have attracted much attention from both the academia and the industry. In this paper, we consider an important dynamic car-hailing problem, namely maximum revenue vehicle dispatching (MRVD), in which rider requests dynamically arrive and drivers need to serve as many riders as possible such that the entire revenue of the platform is maximized. We prove that the MRVD problem is NP-hard and intractable. To handle the MRVD problem, we propose a queueing-based vehicle dispatching framework, which first uses existing machine learning algorithms to predict the future vehicle demand of each region, then estimates the idle time periods of drivers through a queueing model for each region. With the information of the predicted vehicle demands and estimated idle time periods of drivers, we propose one batch-based vehicle dispatching algorithm to efficiently assign suitable drivers to riders such that the expected entire revenue of the platform is maximized during each batch processing. Through experiments over real data sets, we demonstrate the efficiency and effectiveness of our proposed framework.

Nowadays, the locations and contexts of users are easily accessed by mobile advertising brokers, and the brokers can send customers related location-based advertisement. In this paper, we consider a location-based advertising problem, namely maximum utility advertisement assignment (MUAA) problem, with the estimation of the interests of customers and the contexts of the vendors, we want to maximize the overall utility of ads by determining the ads sent to each customer subject to the constraints of the capacities of customers, the distance ranges and the budgets of vendors. We prove that the MUAA problem is NP-hard and intractable. Thus, we propose one offline approach, namely the reconciliation approach, which has an approximation ratio of (1 - ε) · θ, where θ = min(a1/2n1c, a2/n2c, ⋯,am/nmc), and nz is the larger value between the number of valid vendors and the capacity aiof customer ui. Experiments on real data sets confirm the efficiency and effectiveness of our proposed approach.

Spatial crowdsourcing services, such as Uber and Grabhub, become popular recently. Task assignment plays an important role in offering high-quality services. However, most of the existing solutions for task assignment only focus on the entire performance of the platform and do not optimize the maximum assignment delay. As a result, they cannot handle some real world scenarios which require minimizing the maximum delay in task assignment. In this paper, we study the minimizing maximum delay spatial crowdsourcing (MMD-SC) problem and propose solutions aiming at achieving a worst case controlled task assignment. The MMD-SC problem assumes that both workers and requesters come dynamically and considers not only the workers' travel costs but also the buffering time of tasks, thus it is very challenging due to two-sided online setting. To address these challenges, in this work, we propose a space embedding based online random algorithm with a competitive ratio of O(log n) and two efficient heuristic algorithms, namely the threshold based greedy approach and the batch-based approach. In addition, we demonstrate the effectiveness and efficiency of our methods via extensive experiments on both synthetic and real datasets.

With the popularity of smart devices and the development of high-speed wireless networks, the spatial crowdsourcing has attracted much attention from both academia and industry (e.g., Uber and TaskRabbit). Specifically, a spatial crowdsourcing platform assigns workers to location-based tasks according to their current positions, then the workers need to physically move to the specified locations to conduct the assigned tasks. In this paper, we consider an important spatial crowdsourcing problem, namely cooperation-aware spatial crowdsourcing (CA-SC), where spatial tasks (e.g., collecting the Wi-Fi signal strength in one building) are time-constrained and require more than one worker to complete thus the cooperation among assigned workers is essential to the result. Our CA-SC problem is to assign workers to spatial tasks such that the overall cooperation quality is maximized. We prove that the CA-SC problem is NP-hard by reducing from the k-set packing problem, thus intractable. To tackle the CA-SC problem, we propose task-priority greedy (TPG) approach and game theoretic (GT) approach with two optimization methods to quickly solve the CA-SC problem and achieve high total cooperation quality scores. Through extensive experiments, we demonstrate the efficiency and effectiveness of our proposed approaches over both real and synthetic datasets.

The group nearest neighbor (GNN) search on a road network Gr, i.e., finding the spatial objects as activity assembly points with the smallest sum of distances to query users on Gr, has been extensively studied; however, previous works have neglected the fact that social relationships among query users, which ensure the maximally favorable atmosphere in the activity, can play an important role in GNN queries. Many real-world applications, such as location-based social networking services, require such queries. In this paper, we study a new problem: a GNN search on a road network that incorporates cohesive social relationships (CGNN). Specifically, both the query users of highest closeness and the corresponding top-j objects are retrieved. One critical challenge is to speed up the computation of CGNN queries over large social and road networks. To address this challenge, we propose a filtering-and-verification framework for efficient query processing. During filtering, we prune substantial unpromising users and objects using social and geographically spatial constraints. During verification, we obtain the object candidates, among which the top j are selected, with respect to the qualified users. Moreover, we further optimize search strategies to improve query performance. Finally, experimental results on real social and road networks significantly demonstrate the efficiency and efficacy of our solutions.

In this paper, we propose an efficient hierarchical index, G*-tree, to optimize spatial queries on road networks. Most existing graph indexes can only support one kind of query, and thus we need to build multiple indexes on a road network to handle various kinds of spatial queries, which is inefficient and unscalable for real-world applications. To address the problem, a recent study proposes G-tree to support multiple types of spatial queries on road networks within one framework. However, the assembly-based method on G-tree is not efficient enough to handle spatial queries when vertices, which are close in a road network, are distant in G-tree. To address the inefficiency problem of G-tree, in this paper, we propose a novel index structure on road networks, namely G*-tree, whose key idea is to build shortcuts between selected leaf nodes. Based on G*-tree, we propose three shortcut-based algorithms to answer distance queries, k-nearest neighbor queries and range queries, respectively, which are more efficient than the existing assembly-based algorithms on G-tree. Moreover, we propose a shortcut selection algorithm to optimize the performance of spatial queries on G*-tree. We conduct extensive experiments to compare our G*-tree and the state-of-the-art indexing methods on various large-scale road networks, where the results demonstrate that our G*-tree has better efficiency and scalability than the competitors to handle spatial queries.

Nowadays Open Information Extraction (Open IE) approaches, which extracttriples from unstructured text, contribute to the construction of large Open Knowledge Bases (Open KBs). However, one crucial problem is that the noun phrases and relation phrases in the extracted triples are not well canonicalized, which leads to a large number of redundant and ambiguous facts. For example, bothandmay be extracted and stored in Open KBs. Recent research proposes to solve this problem by clustering over manually-defined feature spaces based on the similarity of the noun phrases and relation phrases. However, the performance of such techniques is limited, since only the information contained in the triples is utilized to measure their similarity. In this paper, we propose to perform canonicalization over Open IE triples by incorporating the side information from the original data sources, including the candidate entities of the noun phrases detected in the source text, the types of the candidate entities and the domain knowledge of the source text. We model the canonicalization problem of noun phrases and relation phrases jointly based on such side information, and demonstrate the effectiveness of our approach through extensive experiments on two real-world datasets.

A crowdsourcing task in real-world applications often consists of thousands of atomic tasks. A common practice to distribute a large-scale crowdsourcing task is to pack atomic tasks into task bins and send to crowd workers in batches. It is challenging to decompose a large-scale crowdsourcing task into task bins to ensure reliability at a minimal total cost. In this paper, we propose the Smart Large-scAle task DEcomposer (SLADE) problem, which aims to decompose a large-scale crowdsourcing task to achieve the desired reliability at a minimal cost. We prove its NP-hardness and study two variants of the problem. For the homogeneous SLADE problem, we propose a greedy algorithm and an approximation framework using an optimal priority queue (OPQ) structure with provable approximation ratio. For the heterogeneous SLADE problem, we extend this framework and prove its approximation guarantee. Extensive experiments validate the effectiveness and efficiency of the solutions.

Procrastination is a prevalent form of self-control failure. As it often concerns with the individual's ability to meet the deadline, an efficient time management is crucial for overcoming it. Though a considerable amount of work in behavioral economics provides useful insights, there is not a computational way to guide us how to obtain an appropriate schedule for all the things to be done, especially when the relationship of the deadlines is intrinsic. In this paper, we first propose the Procrastination-aware Scheduling Problem (PSP) to model an appropriate schedule. A bipartite graph formulation is then developed to further illustrate the concepts. We find the PSP is NP-hard in the strong sense and design an approximation algorithm. In addition, we note the significance of the PSP under the online scenario (called OnlinePSP). Finally, we verify the effectiveness and efficiency of the proposed algorithms through extensive experiments on real datasets.

Weight-constrained route planning (WRP) over static graphs has been extensively studied due to its wide application to transportation networks. However, real transportation networks often evolve over time and are thus modeled as time-dependent graphs. In this paper, we study the WRP problem over a large time-dependent graph by incorporating continuous time and weight functions into it. Most existing works regarding route planning over time-dependent graphs are based on the first-in-first-out (FIFO) property. Unfortunately, the FIFO property does not hold for our problem. To solve the problem, we propose two novel route planning algorithms, namely, a baseline algorithm and an advanced algorithm. Specifically, the advanced algorithm is even more efficient than the baseline algorithm, as the advanced algorithm incorporates a fast traversal scheme and tight bounds of time functions to terminate the traversal as early as possible. We confirm the effectiveness and efficiency of our algorithms by extensive experiments on real datasets.

Knowledge graph (KG) embedding is a fundamental problem in data mining research with many real-world applications. It aims to encode the entities and relations in the graph into low dimensional vector space, which can be used for subsequent algorithms. Negative sampling, which samples negative triplets from non-observed ones in the training data, is an important step in KG embedding. Recently, generative adversarial network (GAN), has been introduced in negative sampling. By sampling negative triplets with large scores, these methods avoid the problem of vanishing gradient and thus obtain better performance. However, using GAN makes the original model more complex and harder to train, where reinforcement learning must be used. In this paper, motivated by the observation that negative triplets with large scores are important but rare, we propose to directly keep track of them with cache. However, how to sample from and update the cache are two important questions. We carefully design the solutions, which are not only efficient but also achieve good balance between exploration and exploitation. In this way, our method acts as a "distilled" version of previous GAN-based methods, which does not waste training time on additional parameters to fit the full distribution of negative triplets. The extensive experiments show that our method can gain significant improvement on various KG embedding models, and outperform the state-of-the-arts negative sampling methods based on GAN.

Ridesharing plays a more and more important role in modern transport. In this paper, we propose solutions for the bonus-offering scenario of ridesharing platforms (service providers). When vehicles are in shortage, requesters are allowed to offer bonus so that their orders can get prioritized in the dispatch process. To enable self-motivated bonus bidding of requesters, we devise an auction mechanism, where requesters are supposed to submit their bids truthfully and the platform conducts order dispatch and pricing. Our goal is to maximize the overall utility of the auction, while ensuring desirable auction properties such as truthfulness and individual rationality. To realize that, we propose a greedy and a ranking approach for order dispatch and their corresponding pricing strategies. Extensive experiments on real data suggest that the ranking approach is both effective and efficient.

As one of the most popular services over online platforms, social recommendation has attracted increasing research efforts recently. Among all the recommendation tasks, an important one is item recommendation over high speed social media streams. Existing stream recommendation techniques are not effective for handling social users with diverse interests. Meanwhile, approaches for recommending items to a particular user are not efficient when applied to a huge number of users over high speed streams. In this paper, we propose a novel framework for the social recommendation over streams. Specifically, we first propose a novel Bi-Layer Hidden Markov Model (BiHMM) that adaptively captures the users' behaviors and their interactions with influential official accounts to predict their long-term and short-term interests. Then, we design a new probabilistic entity matching scheme for identifying the relevance score of a streaming item to a user. Moreover, we propose a novel index scheme called CPPse-index for improving the efficiency of our solution. Extensive tests are conducted to prove the superiority of our approach in terms of the recommendation quality and time cost.

Context-aware recommendation has attracted significant attentions over online sites due to its smart context adaption in improving recommendation quality. However, the user's instant contexts do not follow his/her regular user behaviour patterns, thus have not been well captured for advanced personalization of recommendation generation. In this work, we propose an Interactive Context-Aware Recommender System (I-CARS), which allows users to interact and present their needs, so the system can personalize and refine user preferences. I-CARS iteratively asks a question to a user to trigger feedback in term of her recent contexts and incorporates the response to recommend items most likely satisfying his/her instant interests. Specifically, we first propose a Personalized Weighted Context-Aware Matrix Factorization (PW-CAMF) that enables the personalization of important contexts for each user. Then we propose two question selection strategies that exploit user preferences through feedback. We have conducted comprehensive experiments over two real datasets. The experimental results prove the effectiveness of our I-CARS system compare to existing competitors.

The bin packing problem is one of the most fundamental optimization problems. Owing to its hardness as a combinatorial optimization problem class and its wide range of applications in different domains, different variations of the problem are emerged and many heuristics have been proposed for obtaining approximate solutions.

Relation extraction in knowledge base construction has been researched for the last decades due to its applicability to many problems. Most classical works, such as supervised information extraction and distant supervision, focus on how to construct the knowledge base (KB) by utilizing the large number of labels or certain related KBs. However, in many real-world scenarios, the existing methods may not perform well when a new knowledge base is required but only scarce labels or few related KBs available. In this paper, we propose a novel approach called, Relation Extraction via Domain-aware Transfer Learning (ReTrans), to extract relation mentions from a given text corpus by exploring the experience from a large amount of existing KBs which may not be closely related to the target relation. We first propose to initialize the representation of relation mentions from the massive text corpus and update those representations according to existing KBs. Based on the representations of relation mentions, we investigate the contribution of each KB to the target task and propose to select useful KBs for boosting the effectiveness of the proposed approach. Based on selected KBs, we develop a novel domain-aware transfer learning framework to transfer knowledge from source domains to the target domain, aiming to infer the true relation mentions in the unstructured text corpus. Most importantly, we give the stability and generalization bound of ReTrans. Experimental results on the real world datasets well demonstrate that the effectiveness of our approach, which outperforms all the state-of-the-art baselines.

The popularity of mobile Internet techniques and Online-To-Offline(O2O) business models has led to the emergence of various spatial crowdsourcing (SC) platforms in our daily life. A core issue of SC platforms is to assign tasks to suitable crowd workers. Existing approaches usually focus on the matching of two types of objects,tasks and workers, and let workers to travel to the location of usersto provide services, which is a 2D matching problem. However, recent services provided by some new platforms, such as person-alized haircut service1and station ride-sharing, need users andworkers travel together to a third workplace to complete the service, which is indeed a 3D matching problem. Approaches in the existingstudies either cannot solve such 3D matching problem, or lack aassignment plan satisfying both users' and workers' preference inreal applications. Thus, in this paper, we propose a 3-Dimensional Stable Spatial Matching(3D-SSM) for the 3D matching problem innew SC services. We prove that the 3D-SSM problem is NP-hard, and propose two baseline algorithms and two efficient approximatealgorithms with bounded approximate ratios to solve it. Finally, weconduct extensive experiment studies which verify the efficiencyand effectiveness of the proposed algorithms on real and synthetic datasets.

Recently, crowdsourcing has emerged as a new computing paradigm to solve problems that need human intrinsic, such as image annotation. However, there are two limitations in existing crowdsourcing platforms, i.e. non-transparent incentive mechanism and isolated profiles of workers, which harms the interests of both requesters and workers. Meanwhile, Blockchain technology introduces a solution to build a transparent, immutable data model in the Byzantine environment. Moreover, Blockchain systems (e.g. Ethereum) can also support the Tuning-complete script called smart contracts. Thus, we are motivated to use the feature of the transparent data model and smart contract in Blockchain to address the two limitations. Based on the proposed solutions, we have designed a Blockchain based framework which supports foundations of general crowdsourcing platforms. In addition, our framework also has following novel features: (1) it provides the transparent incentive mechanisms; (2) it supports a trusted worker's profile sharing in a cross-platform mode.

Last-mile delivery (LMD) refers to the movement of goods from transportation origins to the final destinations. It has widespread applications such as urban logistics, e-commerce, etc. One fundamental problem in last-mile delivery is route planning, which schedules multiple couriers' routes, i.e. , sequences of origins and destinations of the requests under certain optimization objectives. Prior studies usually designed heuristic solutions to two strongly NP-hard optimization objectives: minimizing the makespan ( i.e. , maximum travel time) of couriers and total latency ( i.e. , waiting time) of requesters. There is no algorithm with theoretical guarantees for either optimization objective in practical cases. In this paper, we propose a theoretically guaranteed solution framework for both objectives. It achieves both approximation ratios of 6ρ, where ρ is the approximation ratio of a core operation, called k LMD, which plans for one courier a route consisting of k requests. Leveraging a spatial index called hierarchically separated tree, we further design an efficient approximation algorithm for k LMD with ρ = O (log n ), where n is the number of requests. Experimental results show that our approach outperforms state-of-the-art methods by averagely 48.4%-96.0% and 49.7%-96.1% for both objectives. Especially in large-scale real datasets, our algorithm has 29.3x-108.9x shorter makespan and 20.2x-175.1x lower total latency than the state-of-the-art algorithms.

For decades, the crowdsourcing has gained much attention from both academia and industry, which outsources a number of tasks to human workers. Typically, existing crowdsourcing platforms include CrowdFlower, Amazon Mechanical Turk (AMT), and so on, in which workers can autonomously select tasks to do. However, due to the unreliability of workers or the difficulties of tasks, workers may sometimes finish doing tasks either with incorrect/incomplete answers or with significant time delays. Existing studies considered improving the task accuracy through voting or learning methods, they usually did not fully take into account reducing the latency of the task completion. This is especially critical, when a task requester posts a group of tasks (e.g., sentiment analysis), and one can only obtain answers of all tasks after the last task is accomplished. As a consequence, the time delay of even one task in this group could delay the next step of the task requester's work from minutes to days, which is quite undesirable for the task requester. Inspired by the importance of the task accuracy and latency, in this paper, we will propose a novel crowdsourcing framework, namely Fast and Reliable crOwdsourcinG framework (FROG), which intelligently assigns tasks to workers, such that the latencies of tasks are reduced and the expected accuracies of tasks are met. Specifically, our FROG framework consists of two important components, task scheduler and notification modules. For the task scheduler module, we formalize a FROG task scheduling (FROG-TS) problem, in which the server actively assigns workers to tasks to achieve high task reliability and low task latency. We prove that the FROG-TS problem is NP-hard. Thus, we design two heuristic approaches, request-based and batch-based scheduling. For the notification module, we define an efficient worker notifying (EWN) problem, which only sends task invitations to those workers with high probabilities of accepting the tasks. To tackle the EWN problem, we propose a smooth kernel density estimation approach to estimate the probability that a worker accepts the task invitation. Through extensive experiments, we demonstrate the effectiveness and efficiency of our proposed FROG platform on both real and synthetic data sets.

As massive volumes of Resource Description Framework (RDF) data are growing, designing a distributed RDF database system to manage them is necessary. In designing this system, it is very common to partition the RDF data into some parts, called fragments, which are then distributed. Thus, the distribution design comprises two steps: fragmentation and allocation. In this study, we explore the workload for fragmentation and allocation, which aims to reduce the communication cost during SPARQL query processing. Specifically, we adaptively maintain some frequent access patterns (FAPs) to reflect the characteristics of the workload while ensuring the data integrity and approximation ratio. Based on these frequent access patterns, we propose three fragmentation strategies, namely vertical, horizontal, and mixed fragmentation, to divide RDF graphs while meeting different types of query processing objectives. After fragmentation, we discuss how to allocate these fragments to various sites while balancing the fragments. Finally, we discuss how to process queries based on the results of fragmentation and allocation. Experiments over large RDF datasets confirm the superior performance of our proposed solutions.

The increasing popularity of crowdsourcing markets enables the application of crowdsourcing classification tasks. How to conduct quality control in such an application to achieve accurate classification results from noisy workers is an important and challenging task, and has drawn broad research interests. However, most existing works do not exploit the label acquisition phase, which results in their disability of making a proper budget allocation. Moreover, some works impractically make the assumption of managing workers, which is not supported by common crowdsourcing platforms such as AMT or CrowdFlower. To overcome these drawbacks, in this paper, we devise a Dynamic Label Acquisition and Answer Aggregation (DLTA) framework for crowdsourcing classification tasks. The framework proceeds in a sequence of rounds, adaptively conducting label inference and label acquisition. In each round, it analyzes the collected answers of previous rounds to perform proper budget allocation, and then issues the resultant query to the crowd. To support DLTA, we propose a generative model for the collection of labels, and correspondingly strategies for label inference and budget allocation. Experimental results show that compared with existing methods, DLTA obtains competitive accuracy in the binary case. Besides, its extended version, which plugs in the state-of-the-art inference technique, achieves the highest accuracy.

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.

Real-life graph datasets extracted from Web are inevitably full of incompleteness, conflicts, and redundancies, so graph data cleaning shows its necessity. One of the main issues is to automatically repair the graph with some repairing rules. Although rules like data dependencies have been widely studied in relational data repairing, very few works exist to repair the graph data. In this paper, we introduce an automatic repairing semantic for graphs, calledGraph-Repairing Rules(GRRs). This semantic can capture the incompleteness, conflicts, and redundancies in the graphs and indicate how to correct these errors. We study three fundamental problems associated with GRRs, implication, consistency and termination, which show whether a given set of GRRs make sense. Repairing the graph data using GRRs involves a problem of finding isomorphic subgraphs of the graph data for each GRR, which is NP-complete. To efficiently circumvent the complex calculation of subgraph isomorphism, we design a decomposition-and-join strategy to solve this problem. Extensive experiments on real datasets show that our GRR semantic and corresponding repairing algorithms can effectively and efficiently repair real-life graph data.

With the success of Bitcoin, the technique behind it, Blockchain, is catching massive attention recently. Blockchain is a collection of several techniques like cryptology, P2P and distributed consensus protocol. The main idea of Blockchain is that nodes in the network keep the same distributed ledger. Because of this immutable ledger, a trusted bridge is built among parties without fully trust. Blockchain can be used in variety of areas, especially in financial fields, like supply chain management, cross-border payment and global bank settlement. Meanwhile, we can observe that mobile network is growing rapidly and nibbling the PC market. However, the current public Blockchain applications like Bitcoin or Ethereum require the nodes to store the whole ledger which exceeds the capacity of the mobile devices. Thus, we need to develop a blockchain platform to support mobile devices. In this demo, we introduce Jupiter, a mobile-based Blockchain platform which provides a novel concept called consensus unit (CU) to alleviate the storage problem of mobile. We present the system architecture and demonstrate several CU scenarios via Jupiter.

Modern networks are of huge sizes as well as high dynamics, which challenges the efficiency of community detection algorithms. In this paper, we study the problem of overlapping community detection on distributed and dynamic graphs. Given a distributed, undirected and unweighted graph, the goal is to detect overlapping communities incrementally as the graph is dynamically changing. We propose an efficient algorithm, called randomized Speaker-Listener Label Propagation Algorithm (rSLPA), based on the Speaker-Listener Label Propagation Algorithm (SLPA) by relaxing the probability distribution of label propagation. Besides detecting high-quality communities, rSLPA can incrementally update the detected communities after a batch of edge insertion and deletion operations. To the best of our knowledge, rSLPA is the first algorithm that can incrementally capture the same communities as those obtained by applying the detection algorithm from the scratch on the updated graph. Extensive experiments are conducted on both synthetic and real-world datasets, and the results show that our algorithm can achieve high accuracy and efficiency at the same time.

Recently, knowledge base systems such as Freebase, YAGO, etc. have been designed and widely applied while most of the knowledge bases are far from being of a high quality. According to the recent researches, the low quality is mainly caused by the loss and low accuracy of the RDF triples, which are the main components of knowledge base systems. In this paper, we propose approaches to enhance the RDF triples in knowledge bases, which is significant for providing good information retrieval service. Specifically, we utilize data facts stored in database systems to obtain possible updates for knowledge bases. Furthermore, inspired by the popular and successful applications of crowdsourcing platforms, we explore the use of crowdsourcing to verify the updates. We propose KD graph to model the possible updates and design a comprehensive framework for knowledge base enhancement problem. Since crowdsourcing employs human power and requires expenditure, we propose an optimal and dynamic method to select candidates for crowdsourcing within a limited budget so that the benefit of enhancing the knowledge base can be maximized. To reduce the time cost, we adopt split techniques and design Simple Split(SS) and Dynamic Split(DS) algorithms. We verify the effectiveness of our solutions by conducting crowdsourcing simulation experiments and experiments on a crowdsourcing platform namely gMission.

Graph similarity search is a common and fundamental operation in graph databases. One of the most popular graph similarity measures is the Graph Edit Distance (GED) mainly because of its broad applicability and high interpretability. Despite its prevalence, exact GED computation is proved to be NP-hard, which could result in unsatisfactory computational efficiency on large graphs. However, exactly accurate search results are usually unnecessary for real-world applications especially when the responsiveness is far more important than the accuracy. Thus, in this paper, we propose a novel probabilistic approach to efficiently estimate GED, which is further leveraged for the graph similarity search. Specifically, we first take branches as elementary structures in graphs, and introduce a novel graph similarity measure by comparing branches between graphs, i.e., Graph Branch Distance (GBD), which can be efficiently calculated in polynomial time. Then, we formulate the relationship between GED and GBD by considering branch variations as the result ascribed to graph edit operations, and model this process by probabilistic approaches. By applying our model, the GED between any two graphs can be efficiently estimated by their GBD, and these estimations are finally utilized in the graph similarity search. Extensive experiments show that our approach has better accuracy, efficiency and scalability than other comparable methods in the graph similarity search over real and synthetic data sets.

Realtime traffic speed estimation is an important issue in urban computation. Existing approaches usually focus on exploiting the periodicity properties of the traffic speed and utilize crowdsourcing techniques to facilitate real-time estimation. The quality of such estimation is limited in real world: 1) the accuracy of existing estimation over-relies on the probed data; 2) the accidental traffic variance is ignored; 3) existing strategies incur exhaustive usage of human workers to get fine-grained estimation results. Thus, a more intelligent RTSE approach is desired. In this paper, we propose the framework of CrowdRTSE (Crowdsourcing-based Real-time Traffic Speed Estimation), which adopts a hybrid offline-online process to collaboratively exploit the historical and real-time data to produce high-quality RTSE. To accomplish such a framework, we devise effective algorithms to judiciously select the best group of human workers with a constant approximation ratio, and effectively propagate the crowdsourced data with high efficiency. Comprehensive evaluations have been conducted on both synthetic and real world datasets. The experimental results verify the effectiveness and efficiency of our proposed methods.

In this paper, we study the problem of extracting a homogeneous graph from a heterogeneous graph. The key challenges of the extraction problem are how to efficiently enumerate paths matched by the provided line pattern and aggregate values for each pair of vertices from the matched paths. To address above two challenges, we propose a parallel graph extraction framework (PGE), where we use vertex-centric model to enumerate paths and compute aggregate functions in parallel. The framework compiles the line pattern into a path concatenation plan and generates the final weighted edges in a divide-and-conquer manner. The new solution outperforms the state-of-the-art ones through the comprehensive experiments.

SimRank is a popular link-based similarity measurement among nodes in a graph. To compute the all-pairs SimRank matrix accurately, iterative methods are usually used. For static graphs, current iterative solutions are not efficient enough, both in time and space, due to unnecessary cost and storage by the nature of iterative updating. For dynamic graphs, all current incremental solutions for updating the Sim-Rank matrix are based on an approximated SimRank definition, and thus have no accuracy guarantee. In this paper, we propose a novel local push based algorithm for computing all-pairs SimRank. We show that our algorithms outperform the state-of-the-art static and dynamic all-pairs SimRank algorithms.

Recently, Blockchain becomes a hot research topic due to the success of Blockchain in many applications, such as cryptocurrency, smart contract, digital assets, distributed cloud storage and so on. The power of Blockchain is that it can achieve the consensus of an ordered set of transactions among nodes which do not trust each other, even with the existence of malicious nodes. However, compared to traditional databases, the current Blockchain technology still cannot handle a massive number of transactions, which is caused by many factors, such as the consensus protocol, structure of the blocks and storage challenge. Among them, the high storage requirement is a key factor that prevents the wide usage of Blockchain on various devices such as mobile phones or low-end PCs. In this paper, to address the storage challenge, we introduce a novel concept called Consensus Unit (CU), which organizes different nodes into one unit and lets them to store at least one copy of Blockchain data in the system together. Based on this idea, we further define the Blocks Assignment Optimization (BAO) problem which determines the optimal assignment of blocks such that the storage space is fully used and the query cost is minimized. We prove that the BAO problem is NP-hard. Thus, we propose three efficient heuristic algorithms to solve the static assignment problem. Furthermore, we present solutions to address the dynamic scenarios when new blocks arrive and nodes join or depart from the CU. To verify the effectiveness of CU, we have conducted extensive experiments on synthetic data and BLOCKBENCH [1]. The results have confirmed the superiority of CU in saving the storage and maintaining the system throughput.

Spatial crowdsourcing brings in a new approach for social media and location-based services (LBS) to collect location specific information via mobile users. For example, when a user checks in at a shop on Facebook, he will immediately receive and is asked to complete a set of tasks such as "what is the opening hour of the shop". It is non-trivial to complete a set of tasks timely and accurately via spatial crowdsourcing. Since workers in spatial crowdsourcing are often transient and limited in number, these social media platforms need to properly allocate workers within the set of tasks such that all tasks are completed (i) with high quality and (ii) with a minimal latency (estimated by the arriving index of the last recruited worker). Solutions to quality and latency control in traditional crowdsourcing are inapplicable in this problem because they either assume sufficient workers or ignore the spatiotemporal factors. In this work, we define the Latency-oriented Task Completion (LTC) problem, which trades off quality and latency (number of workers) of task completion in spatial crowdsourcing. We prove that the LTC problem is NP-hard. We first devise a minimum-cost-flow based algorithm with a constant approximation ratio for the LTC problem in the offline scenario, where all information is known a prior. Then we study the more practical online scenario of the LTC problem, where workers appear dynamically and the platform needs to arrange tasks for each worker immediately based on partial information. We design two greedy-based algorithms with competitive ratio guarantees to solve the LTC problem in the online scenario. Finally, we validate the effectiveness and efficiency of the proposed solutions through extensive evaluations on both synthetic and real-world datasets.

The system throughput and workers' travel distance are two important factors in spatial crowdsourcing and improving one of them usually means sacrificing the other. However, existing works either fail to consider the trade-off between these two factors or resolve their conflicts by simply targeting tasks within a bounding circle for each worker. In this paper, we compromise between the throughput and the distance by formulating these two factors as score terms in the objective function. Apart from that, we study the multi-campaign scenario in our problem, which is not uncommon in practical applications while not yet discussed in existing works. The worker diversity of the campaigns is formulated as another score term in the objective function. The problem of multi-campaign oriented spatial crowdsourcing is to maximize the aforementioned score function. We prove the problem is NP-hard and provide several approximation solutions. Extensive experiments have been conducted to validate the devised solutions.

Transfer learning has gained increasing attention due to the inferior performance of machine learning algorithms with insufficient training data. Most of the previous homogeneous or heterogeneous transfer learning works aim to learn a mapping function between feature spaces based on the inherent correspondence across the source and target domains or labeled instances. However, in many real world applications, existing methods may not be robust when the correspondence across domains is noisy or labeled instances are not representative. In this paper, we develop a novel transfer learning framework called Transfer Learning via Feature Isomorphism Discovery (abbreviated to TLFid), which owns high tolerance for noisy correspondence between domains as well as scarce or non-existing labeled instances. More specifically, we propose a feature isomorphism approach to discovering common substructures across feature spaces and learning a feature mapping function from the target domain to the source domain. We evaluate the performance of TLFid on the cross-lingual sentiment classification tasks. The results show that our method achieves significant improvement in terms of accuracy compared with the state-of-the-art methods.

Collaborator Recommendation is a useful application in exploiting big academic data. However, existing works leave out the contextual restriction (i.e., research topics) of people's academic collaboration, thus cannot recommend suitable collaborators for the required research topics. In this work, we propose Context-aware Collaborator Recommendation (CACR), which aims to recommend high-potential new collaborators for people's context-restricted requests. To this end, we design a novel recommendation framework, which consists of two fundamental components: the Collaborative Entity Embedding network (CEE) and the Hierarchical Factorization Model (HFM). In particular, CEE jointly represents researchers and research topics as compact vectors based on their co-occurrence relationships, whereby capturing researchers' context-aware collaboration tendencies and topics' underlying semantics. Meanwhile, HFM extracts researchers' activenesses and conservativenesses, which reflect their intensities of making academic collaborations and tendencies of working with non-collaborated fellows. The extracted activenesses and conservativenesses work collaboratively with the context-aware collaboration tendencies, such that high-quality recommendation can be produced. Extensive experimental studies are conducted with large-scale academic data, whose results verify the effectiveness of our proposed approaches.

In spatial crowdsourcing, requesters submit their task-related locations and increase the demand of a local area. The platform prices these tasks and assigns spatial workers to serve if the prices are accepted by requesters. There exist mature pricing strategies which specialize in tackling the imbalance between supply and demand in a local market. However, in global optimization, the platform should consider the mobility of workers; that is, any single worker can be the potential supply for several areas, while it can only be the true supply of one area when assigned by the platform. The hardness lies in the uncertainty of the true supply of each area, hence the existing pricing strategies do not work. In the paper, we formally define this Global Dynamic Pricing(GDP) problem in spatial crowdsourcing. And since the objective is concerned with how the platform matches the supply to areas, we let the matching algorithm guide us how to price. We propose a MAtching-based Pricing Strategy (MAPS) with guaranteed bound. Extensive experiments conducted on the synthetic and real datasets demonstrate the effectiveness of MAPS.

Knowledge base construction (KBC) has become a hot and in-time topic recently with the increasing application need of large-scale knowledge bases (KBs), such as semantic search, QA systems, the Google Knowledge Graph and IBM Watson QA System. Existing KBs mainly focus on encoding the factual facts of the world, e.g., city area and company product, which are regarded as the objective knowledge, whereas the subjective knowledge, which is frequently mentioned in Web queries, has been neglected. The subjective knowledge has no documented ground truth, instead, the truth relies on people's dominant opinion, which can be solicited from online crowd workers. In our work, we propose a KBC framework for subjective knowledge base construction taking advantage of the knowledge from the crowd and existing KBs. We develop a two-staged framework for subjective KB construction which consists of core subjective KB construction and subjective KB enrichment. Firstly, we try to build a core subjective KB mined from existing KBs, where every instance has rich objective properties. Then, we populate the core subjective KB with instances extracted from existing KBs, in which the crowd is leverage to annotate the subjective property of the instances. In order to optimize the crowd annotation process, we formulate the problem of subjective KB enrichment procedure as a cost-aware instance annotation problem and propose two instance annotation algorithms, i.e., adaptive instance annotation and batch-mode instance annotation algorithms. We develop a two-stage system for subjective KB construction which consists of core subjective KB construction and subjective knowledge enrichment. We evaluate our framework on real knowledge bases and a real crowdsourcing platform, the experimental results show that we can derive high quality subjective knowledge facts from existing KBs and crowdsourcing techniques through our proposed framework.

Recently, with the rapid development of mobile devices and the crowdsourcing platforms, the spatial crowdsourcing has attracted much attention from the database community. Specifically, spatial crowdsourcing refers to sending a location-based request to workers according to their positions, and workers need to physically move to specified locations to conduct tasks. Many works have studied task assignment problems in spatial crowdsourcing, however, their problem settings are different from each other. Thus, it is hard to compare the performances of existing algorithms on task assignment in spatial crowdsourcing. In this paper, we present a comprehensive experimental comparison of most existing algorithms on task assignment in spatial crowdsourcing. Specifically, we first give general definitions about spatial workers and spatial tasks based on definitions in the existing works such that the existing algorithms can be applied on the same synthetic and real data sets. Then, we provide a uniform implementation for all the tested algorithms of task assignment problems in spatial crowdsourcing (open sourced). Finally, based on the results on both synthetic and real data sets, we discuss the strengths and weaknesses of tested algorithms, which can guide future research on the same area and practical implementations of spatial crowdsourcing systems.

In the Big Data era, truth discovery has served as a promising technique to solve conflicts in the facts provided by numerous data sources. The most significant challenge for this task is to estimate source reliability and select the answers supported by high quality sources. However, existing works assume that one data source has the same reliability on any kinds of entity, ignoring the possibility that a source may vary in reliability on different domains. To capture the influence of various levels of expertise in different domains, we integrate domain expertise knowledge to achieve a more precise estimation of source reliability. We propose to infer the domain expertise of a data source based on its data richness in different domains. We also study the mutual influence between domains, which will affect the inference of domain expertise. Through leveraging the unique features of the multi-truth problem that sources may provide partially correct values of a data item, we assign more reasonable confidence scores to value sets. We propose an integrated Bayesian approach to incorporate the domain expertise of data sources and confidence scores of value sets, aiming to find multiple possible truths without any supervision. Experimental results on two real-world datasets demonstrate the feasibility, efficiency and effectiveness of our approach.

There has been a dramatic growth of shared mobility applications such as ride-sharing, food delivery and crowdsourced parcel delivery. Shared mobility refers to transportation services that are shared among users, where a central issue is route planning . Given a set of workers and requests, route planning finds for each worker a route, i.e. , a sequence of locations to pick up and drop off passengers/parcels that arrive from time to time, with different optimization objectives. Previous studies lack practicability due to their conflicted objectives and inefficiency in inserting a new request into a route, a basic operation called insertion . In this paper, we present a unified formulation of route planning called URPSM. It has a well-defined parameterized objective function which eliminates the contradicted objectives in previous studies and enables flexible multi-objective route planning for shared mobility. We prove the problem is NP-hard and there is no polynomial-time algorithm with constant competitive ratio for the URPSM problem and its variants. In response, we devise an effective and efficient solution to address the URPSM problem approximately. We design a novel dynamic programming (DP) algorithm to accelerate the insertion operation from cubic or quadric time in previous work to only linear time. On basis of the DP algorithm, we propose a greedy based solution to the URPSM problem. Experimental results on real datasets show that our solution outperforms the state-of-the-arts by 1.2 to 12.8 times in effectiveness, and also runs 2.6 to 20.7 times faster.

With the prevalence of car-hailing applications, ridesharing becomes more and more popular because of its great potential in monetary saving and environmental protection. Order dispatch is the key problem in ridesharing, which has a strong impact on riders' experience and platform's performance. Existing order dispatch research works fail to consider the price of the orders, which can be an important reference because it directly relates to the platform's profit. Our work takes the order price into concern, and formulates a constrained optimization problem, which takes platform's profit as the optimization objective and performs controls on riders' detour distance and waiting time. We prove the problem is NP-hard, thus, we propose approximation methods. We further develop a simulation framework based on real ridesharing order and vehicle data. We conduct experiments with this simulation framework to evaluate the effectiveness and efficiency of the proposed methods.

Crowdsourcing has been shown to be effective in a wide range of applications, and is seeing increasing use. A large-scale crowdsourcing task often consists of thousands or millions of atomic tasks, each of which is usually a simple task such as binary choice or simple voting. To distribute a large-scale crowdsourcing task to limited crowd workers, a common practice is to pack a set of atomic tasks into a task bin and send to a crowd worker in a batch. It is challenging to decompose a large-scale crowdsourcing task and execute batches of atomic tasks, which ensures reliable answers at a minimal total cost. Large batches lead to unreliable answers of atomic tasks, while small batches incur unnecessary cost. In this paper, we investigate a general crowdsourcing task decomposition problem, called the Smart Large-scAle task DEcomposer (SLADE) problem, which aims to decompose a large-scale crowdsourcing task to achieve the desired reliability at a minimal cost. We prove the NP-hardness of the SLADE problem and propose solutions in both homogeneous and heterogeneous scenarios. For the homogeneous SLADE problem, where all the atomic tasks share the same reliability requirement, we propose a greedy heuristic algorithm and an efficient and effective approximation framework using an optimal priority queue (OPQ) structure with provable approximation ratio. For the heterogeneous SLADE problem, where the atomic tasks can have different reliability requirements, we extend the OPQ-based framework leveraging a partition strategy, and also prove its approximation guarantee. Finally, we verify the effectiveness and efficiency of the proposed solutions through extensive experiments on representative crowdsourcing platforms.

As crowdsourcing has been dramatically investigated and utilized to address problems in the real world, it is essential and important to think about performance optimization. Analogous to computer systems with CPUs, treating each worker as a HPU (Human Processing Unit [1]) and studying the performance optimization on top of HPUs are interesting perspectives to resolve crowdsourcing issues. However, as we characterize HPUs in detail for this purpose, we find that there are significant differences between CPUs and HPUs, leading to the need of completely new optimization algorithms. In this paper, we study the specific optimization problem of obtaining results the fastest for a crowdsourced job with a fixed total budget. In crowdsourcing, jobs are usually broken down into sets of small tasks, which are assigned to workers one at a time. We consider three scenarios of increasing complexity: Identical Round Homogeneous Tasks, Multiplex Round Homogeneous Tasks, and Multiple Round Heterogeneous Tasks. For each scenario, we analyze the stochastic behavior of the HPU clock rate as a function of the remuneration offered. After that, we develop an optimum Budget Allocation Strategy to minimize the latency of the job completion. We validate our results through extensive simulations and experiments on Amazon Mechanical Turk.

Data fusion has played an important role in data mining because high quality data is required in a lot of applications. As on-line data may be out-of-date and errors in the data may propagate with copying and referring between sources, it is hard to achieve satisfying results with merely applying existing data fusion methods to fuse Web data. In this paper, we make use of the crowd to achieve high quality data fusion result. We design a framework selecting a set of tasks to ask crowds in order to improve the confidence of data. Since data are correlated and crowds may provide incorrect answers, how to select a proper set of tasks to ask the crowd is a very challenging problem. In this paper, we design an approximation solution to address this challenge since we prove that the problem is at NP-hard. To further improve the efficiency, we design a pruning strategy and a preprocessing method, which effectively improve the performance of the proposed approximation solution. We verify the solutions with extensive experiments on a real crowdsourcing platform.

With the continued proliferation of location-based services, a growing number of web-accessible data objects are geotagged and have text descriptions. An important query over such web objects is the direction-aware spatial keyword query that aims to retrieve the top-k objects that best match query parameters in terms of spatial distance and textual similarity in a given query direction. In some cases, it can be difficult for users to specify appropriate query parameters. After getting a query result, users may find some desired objects are unexpectedly missing and may therefore question the entire result. Enabling why-not questions in this setting may aid users to retrieve better results, thus improving the overall utility of the query functionality. This paper studies the direction-aware why-not spatial keyword top-k query problem. We propose efficient query refinement techniques to revive missing objects by minimally modifying users' directionaware queries. Experimental studies demonstrate the efficiency and effectiveness of the proposed techniques.

With the rapid advancement of mobile devices and crowdsourcing platforms, spatial crowdsourcing has attracted much attention from various research communities. A spatial crowdsourcing system periodically matches a number of locationbased workers with nearby spatial tasks (e.g., taking photos or videos at some specific locations). Previous studies on spatial crowdsourcing focus on task assignment strategies that maximize an assignment score based solely on the available information about workers/tasks at the time of assignment. These strategies can only achieve local optimality by neglecting the workers/tasks that may join the system in a future time. In contrast, in this paper, we aim to improve the global assignment, by considering both present and future (via predictions) workers/tasks. In particular, we formalize a new optimization problem, namely maximum quality task assignment (MQA). The optimization objective of MQA is to maximize a global assignment quality score, under a traveling budget constraint. To tackle this problem, we design an effective grid-based prediction method to estimate the spatial distributions of workers/tasks in the future, and then utilize the predictions to assign workers to tasks at any given time instance. We prove that the MQA problem is NPhard, and thus intractable. Therefore, we propose efficient heuristics to tackle the MQA problem, including MQA greedy and MQA divide-and-conquer approaches, which can efficiently assign workers to spatial tasks with high quality scores and low budget consumptions. Through extensive experiments, we demonstrate the efficiency and effectiveness of our approaches on both real and synthetic datasets.

In recent years, online Event Based Social Network (EBSN) platforms have become increasingly popular. One typical task of EBSN platforms is to help users make suitable and personalized plans for participating in different interesting social events. Existing techniques either ignore the minimum-participant requirement constraint for each event, which is crucially needed for some events to be held successfully, or assume that events would not change once announced. In this paper, we address the above inadequacies of existing EBSN techniques. We formally define the Global Event Planning with Constraints (GEPC) problem, and its incremental variant. We prove that both are NP-hard, and provide approximate solutions. Finally, we verify the effectiveness and efficiency of our proposed algorithms through extensive experiments over real and synthetic datasets.

The prevalence of mobile Internet techniques and Online-To-Offline (O2O) business models has led the emergence of various spatial crowdsourcing (SC) platforms in our daily life. A core issue of SC is to assign real-time tasks to suitable crowd workers. Existing approaches usually focus on the matching of two types of objects, tasks and workers, or assume the static offline scenarios, where the spatio-temporal information of all the tasks and workers is known in advance. Recently, some new emerging O2O applications incur new challenges: SC platforms need to assign three types of objects, tasks, workers and workplaces, and support dynamic real-time online scenarios, where the existing solutions cannot handle. In this paper, based on the aforementioned challenges, we formally define a novel dynamic online task assignment problem, called the trichromatic online matching in real-time spatial crowdsourcing (TOM) problem, which is proven to be NP-hard. Thus, we first devise an efficient greedy online algorithm. However, the greedy algorithm can be trapped into local optimal solutions easily. We then present a threshold-based randomized algorithm that not only guarantees a tighter competitive ratio but also includes an adaptive optimization technique, which can quickly learn the optimal threshold for the randomized algorithm. Finally, we verify the effectiveness and efficiency of the proposed methods through extensive experiments on real and synthetic datasets.

With the rapid development of mobile networks and the widespread usage of mobile devices, spatial crowdsourcing [1], which outsources location-related tasks to moving workers, has drawn increasing attention. Spatial crowdsourcing differs from traditional crowdsourcing in that tasks released by a requester are location-related, and workers should physically travel to a specific spot to perform the task. Task assignment is an important issue in spatial crowdsourcing. Most existing works adopt SAT (Server Assigned Tasks) assignment mode [1], where the SC-server assigns tasks to workers in regular timestamps. However, existing works [1], [2], [3] on this mode are based on the assumption that no rejection would happen after the assignment and workers guarantee to perform their assigned tasks. In practice, a rejection would happen when the worker is not interested in the assigned tasks, which may result from long travel distance, critical time requirement, dissatisfactory payment, workers' lacking skills and etc. In the typical application of spatial crowdsourcing, Uber, workers (drivers) are allowed to reject the ride requests assigned by the server. Uber requires its drivers to accept at least 90 percent of the trip requests in order to avoid low system throughput and poor experience for riders [4]. Taking workers' rejections into concern, in spatial crowdsourcing, how to match the workers with the right tasks to maximize their acceptance is of great importance. Without consideration of workers' acceptance, the system's throughput cannot be guaranteed.

Taxi-calling apps are gaining increasing popularity for their efficiency in dispatching idle taxis to passengers in need. To precisely balance the supply and the demand of taxis, online taxicab platforms need to predict the Unit Original Taxi Demand (UOTD), which refers to the number of taxi-calling requirements submitted per unit time (e.g., every hour) and per unit region (e.g., each POI). Predicting UOTD is non-trivial for large-scale industrial online taxicab platforms because both accuracy and flexibility are essential. Complex non-linear models such as GBRT and deep learning are generally accurate, yet require labor-intensive model redesign after scenario changes (e.g., extra constraints due to new regulations). To accurately predict UOTD while remaining flexible to scenario changes, we propose LinUOTD, a unified linear regression model with more than 200 million dimensions of features. The simple model structure eliminates the need of repeated model redesign, while the high-dimensional features contribute to accurate UOTD prediction. We further design a series of optimization techniques for efficient model training and updating. Evaluations on two large-scale datasets from an industrial online taxicab platform verify that LinUOTD outperforms popular non-linear models in accuracy. We envision our experiences to adopt simple linear models with high-dimensional features in UOTD prediction as a pilot study and can shed insights upon other industrial large-scale spatio-temporal prediction problems.

Ridesharing enables drivers to share any empty seats in their vehicles with riders to improve the efficiency of transportation for the benefit of both drivers and riders. Different from existing studies in ridesharing that focus on minimizing the travel costs of vehicles, we consider that the satisfaction of riders (the utility values) is more important nowadays. Thus, we formulate the problem of utility-aware ridesharing on road networks (URR) with the goal of providing the optimal rider schedules for vehicles to maximize the overall utility, subject to spatial-temporal and capacity constraints. To assign a new rider to a given vehicle, we propose an efficient algorithm with a minimum increase in travel cost without reordering the existing schedule of the vehicle. We prove that the URR problem is NP-hard by reducing it from the 0-1 Knapsack problem and it is unlikely to be approximated within any constant factor in polynomial time through a reduction from the DENS k-SUBGRAPH problem. Therefore, we propose three efficient approximate algorithms, including a bilateral arrangement algorithm, an efficient greedy algorithm and a grouping-based scheduling algorithm, to assign riders to suitable vehicles with a high overall utility. Through extensive experiments, we demonstrate the efficiency and effectiveness of our URR approaches on both real and synthetic data sets.

Online event-based social networks (EBSNs) and studies on global event-participant arrangement strategies for EBSNs are becoming popular recently. Existing works measure satisfaction of an arrangement by a linear combination of few factors, weights of which are predefined and fixed, and do not allow users to provide feedbacks on whether accepting the arrangement or not. Besides, most of them only consider offline scenarios, where full information of users is known in advance. However, on real-world EBSN platforms, users can dynamically log in the platform and register for events on a first come, first served basis. In other words, online scenarios of event-participant arrangement strategies should be considered. In this work, we study a new event-participant arrangement strategy for online scenarios, the Feedback-Aware Social Event-participant Arrangement (FASEA) problem, where satisfaction scores of an arrangement are learned adaptively and users can choose to accept or reject the arranged events. Particularly, we model the problem as a contextual combinatorial bandit setting and use efficient and effective algorithms to solve the problem. The effectiveness and efficiency of the solutions are evaluated with extensive experimental studies and our findings indicate that the state-of-the-art Thompson Sampling that is reported to work well under basic multi-armed bandit does not perform well under FASEA.

This issue of Data Science and Engineering contains a collection of five papers from the APWeb-WAIM 2017, with one additional paper from the regular submissions to the journal.APWeb-WAIM, or the Asia Pacific Web and Web-Age Information Management Joint Conference on Web and Big Data, is an annual international database conference, aiming at attracting professionals of different communities such as industry and academic from not only Asia Pacific countries but also other continents.The objective is to share and exchange ideas, experience and techniques in the area of World Wide Web with the underlying techniques and applications, including Web technologies, database systems, information management, software engineering, and big data.The 2017 edition of APWeb-WAIM was held in Beijing, China, and attracted a total of 240 regular paper submissions, spanning over numerous active and emerging topic areas.The conference program committee selected 44 regular papers and 32 short papers to be presented at the conference and published in the conference proceedings [1].

With the rapid development of mobile internet and online to offline marketing model, various spatial crowdsourcing platforms, such as Gigwalk and Gmission, are getting popular. Most existing studies assume that spatial crowdsourced tasks are simple and trivial. However, many real crowdsourced tasks are complex and need to be collaboratively finished by a team of crowd workers with different skills. Therefore, an important issue of spatial crowdsourcing platforms is to recommend some suitable teams of crowd workers to satisfy the requirements of skills in a task. In this paper, to address the issue, we first propose a more practical problem, called Top-k team recommendation in spatial crowdsourcing (Top k TR) problem. We prove that the Top k TR problem is NP-hard and designs a two-level-based framework, which includes an approximation algorithm with provable approximation ratio and an exact algorithm with pruning techniques to address it. In addition, we study a variant of the Top k TR problem, called Top k TRL, where a team leader is appointed among each recommended team of crowd workers in order to coordinate different crowd workers conveniently, and the aforementioned framework can be extended to address this variant. Finally, we verify the effectiveness and efficiency of the proposed methods through extensive experiments on real and synthetic datasets.

Performing online selective queries against graphs is a challenging problem due to the unbounded nature of graph queries which leads to poor computation locality. It becomes even difficult when a graph is too large to be fit in the memory. Although there have been emerging efforts on managing large graphs in a distributed and parallel setting, e.g., Pregel, HaLoop and etc, these computing frameworks are designed from the perspective of scalability instead of the query efficiency. In this work, we present our solution methodology for online selective graph queries based on the shortest path distance semantic, which finds various applications in practice. The essential intuition is to build a distance-aware index for online distance-based query processing and to eliminate redundant graph traversal as much as possible. We discuss how the solution can be applied to two types of research problems, distance join and vertex set bonding, which are distance-based graph pattern discovery and finding the structure-wise bonding of vertices, respectively.

Worker Recommendation (WR) is one of the most important functions for crowdsourced Q&A services. Specifically, given a set of tasks to be solved, WR recommends each task with a certain group of workers, whom are expected to give timely answers with high qualities. To address the WR problem, recent studies have introduced a number of recommendation approaches, which take advantage of workers' expertises or preferences towards different types of tasks. However, without a thorough consideration of workers' characters, such approaches will lead to either inadequate task fulfillment or inferior answer quality. In this work, we propose the Triple-factor Aware Worker Recommendation framework, which collectively considers workers' expertises, preferences and activenesses to maximize the overall production of high quality answers. We construct the Latent Hierarchical Factorization Model, which is able to infer the tasks' underlying categories and workers' latent characters from the historical data; and we propose a novel parameter inference method, which only requires the processing of positive instances, giving rise to significantly higher time efficiency and better inference quality. What's more, the sampling-based recommendation algorithm is developed, such that the near optimal worker recommendation can be generated for a presented batch of tasks with considerably reduced time consumption. Comprehensive experiments have been carried out using both real and synthetic datasets, whose results verify the effectiveness and efficiency of our proposed methods.

Crowdsourcing is a new computing paradigm where humans are actively enrolled to participate in the procedure of computing, especially for tasks that are intrinsically easier for humans than for computers. The popularity of mobile computing and sharing economy has extended conventional web-based crowdsourcing to spatial crowdsourcing (SC), where spatial data such as location, mobility and the associated contextual information, plays a central role. In fact, spatial crowdsourcing has stimulated a series of recent industrial successes including Citizen Sensing (Waze), P2P ride-sharing (Uber) and Real-time Online-To-Offline (O2O) services (Instacart and Postmates). In this tutorial, we review the paradigm shift from web-based crowdsourcing to spatial crowdsourcing. We dive deep into the challenges and techniques brought by the unique spatio-temporal characteristics of spatial crowdsourcing. Particularly, we survey new designs in task assignment, quality control, incentive mechanism design and privacy protection on spatial crowdsourcing platforms, as well as the new trend to incorporate crowdsourcing to enhance existing spatial data processing techniques. We also discuss case studies of representative spatial crowdsourcing systems and raise open questions and current challenges for the audience to easily comprehend the tutorial and to advance this important research area.

The popularity of Online To Offline (O2O) service platforms has spurred the need for online task assignment in real-time spatial data, where streams of spatially distributed tasks and workers are matched in real time such that the total number of assigned pairs is maximized. Existing online task assignment models assume that each worker is either assigned a task immediately or waits for a subsequent task at a fixed location once she/he appears on the platform. Yet in practice a worker may actively move around rather than passively wait in place if no task is assigned. In this paper, we define a new problem Flexible Two-sided Online task Assignment (FTOA). FTOA aims to guide idle workers based on the prediction of tasks and workers so as to increase the total number of assigned worker-task pairs. To address the FTOA problem, we face two challenges: (i) How to generate guidance for idle workers based on the prediction of the spatiotemporal distribution of tasks and workers? (ii) How to leverage the guidance of workers' movements to optimize the online task assignment? To this end, we propose a novel two-step framework, which integrates offline prediction and online task assignment. Specifically, we estimate the distributions of tasks and workers per time slot and per unit area, and design an online task assignment algorithm, Prediction-oriented Online task Assignment in Real-time spatial data (POLAR-OP). It yields a 0.47-competitive ratio, which is nearly twice better than that of the state-of-the-art. POLAR-OP also reduces the time complexity to process each newly-arrived task/worker to O(1). We validate the effectiveness and efficiency of our methods via extensive experiments on both synthetic datasets and real-world datasets from a large-scale taxi-calling platform.

Matching dependencies (MDs) have recently been proposed to make data dependencies tolerant to various information representations, and found useful in data quality applications such as record matching. Instead of the strict equality function used in traditional dependency syntax (e.g., functional dependencies), MDs specify constraints based on similarity and identification. However, in practice, MDs may still be too strict and applicable only in a subset of tuples in a relation. Thereby, we study the conditional matching dependencies (CMDs), which bind matching dependencies only in a certain part of a table, i.e., MDs conditionally applicable in a subset of tuples. Compared to MDs, CMDs have more expressive power that enables them to satisfy wider application needs. In this article, we study several important theoretical and practical issues of CMDs, including irreducible CMDs with respect to the implication, discovery of CMDs from data, reliable CMDs agreed most by a relation, approximate CMDs almost satisfied in a relation, and finally applications of CMDs in record matching and missing value repairing. Through an extensive experimental evaluation in real data sets, we demonstrate the efficiency of proposed CMDs discovery algorithms and effectiveness of CMDs in real applications.

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.

The semantic Web has enabled the creation of a growing number of knowledge bases (KBs), which are designed independently using different techniques. Integration of KBs has attracted much attention as different KBs usually contain overlapping and complementary information. Automatic techniques for KB integration have been improved but far from perfect. Therefore, in this paper, we study the problem of knowledge base semantic integration using crowd intelligence. There are both classes and instances in a KB, in our work, we propose a novel hybrid framework for KB semantic integration considering the semantic heterogeneity of KB class structures. We first perform semantic integration of the class structures via crowdsourcing, then apply the blocking-based instance matching approach according to the integrated class structure. For class structure (taxonomy) semantic integration, the crowd is leveraged to help identifying the semantic relationships between classes to handle the semantic heterogeneity problem. Under the conditions of both large scale KBs and limited monetary budget for crowdsourcing, we formalize the class structure (taxonomy) semantic integration problem as a Local Tree Based Query Selection (LTQS) problem. We show that the LTQS problem is NP-hard and propose two greedy-based algorithms, i.e., static query selection and adaptive query selection. Furthermore, the KBs are usually of large scales and have millions of instances, direct pairwise-based instance matching is inefficient. Therefore, we adopt the blockingbased strategy for instance matching, taking advantage of the class structure (taxonomy) integration result. The experiments on real large scale KBs verify the effectiveness and efficiency of the proposed approaches.

Heterogeneous graph is a popular data model to represent the real-world relations with abundant semantics. To analyze heterogeneous graphs, an important step is extracting homogeneous graphs from the heterogeneous graphs, called homogeneous graph extraction. In an extracted homogeneous graph, the relation is defined by a line pattern on the heterogeneous graph and the new attribute values of the relation are calculated by user-defined aggregate functions. The key challenges of the extraction problem are how to efficiently enumerate paths matched by the line pattern and aggregate values for each pair of vertices from the matched paths. To address above two challenges, we propose a parallel graph extraction framework, where we use vertex-centric model to enumerate paths and compute aggregate functions in parallel. The framework compiles the line pattern into a path concatenation plan, which determines the order of concatenating paths and generates the final paths in a divide-and-conquer manner. We introduce a cost model to estimate the cost of a plan and discuss three plan selection strategies, among which the best plan can enumerate paths in O(log)(l) iterations, where l is the length of a pattern. Furthermore, to improve the performance of evaluating aggregate functions, we classify the aggregate functions into three categories, i.e., distributive aggregation, algebraic aggregation, and holistic aggregation. Since the distributive and algebraic aggregations can be computed from the partial paths, we speed up the aggregation by computing partial aggregate values during the path enumeration.

Graph keyword search has drawn many research interests, since graph models can generally represent both structured and unstructured databases and keyword searches can extract valuable information for users without the knowledge of the underlying schema and query language. In practice, data graphs can be extremely large, e.g., a Web-scale graph containing billions of vertices. The state-of-the-art approaches employ centralized algorithms to process graph keyword searches, and thus they are infeasible for such large graphs, due to the limited computational power and storage space of a centralized server. To address this problem, we investigate keyword search for Web-scale graphs deployed in a distributed environment. We first give a naive search algorithm to answer the query efficiently. However, the naive search algorithm uses a flooding search strategy that incurs large time and network overhead. To remedy this shortcoming, we then propose a signature-based search algorithm. Specifically, we design a vertex signature that encodes the shortest-path distance from a vertex to any given keyword in the graph. As a result, we can find query answers by exploring fewer paths, so that the time and communication costs are low. Moreover, we reorganize the graph data in the cluster after its initial random partitioning so that the signature-based techniques are more effective. Finally, our experimental results demonstrate the feasibility of our proposed approach in performing keyword searches over Web-scale graph data.

With the rapid development of mobile networks and the widespread usage of mobile devices, spatial crowdsourcing, which refers to assigning location-based tasks to moving workers, has drawn increasing attention. One of the important issues in spatial crowdsourcing is task assignment, which allocates tasks to appropriate workers. However, existing works generally assume that no rejection would happen after the task assignment is completed by the server. Ignorance of such an operation can lead to low system throughput. Thus, in this paper, we take workers' rejection into consideration and try to maximize workers' acceptance in order to improve the system throughput. Specifically, we first formally define the problem of maximizing workers' acceptance in rejection-aware spatial crowdsourcing. Unfortunately, the problem is NP-hard. We propose two exact solutions to obtain the optimal assignment, but they are not efficient enough and not scalable for large inputs. Then, we present four approximation approaches for improving the efficiency. Finally, we show the effectiveness of the proposed pruning strategy for the exact solutions and the superiority of the proposed Greedy algorithm over other approximation methods through extensive experiments.

A recent article [Vincent et al. 2015] concerns the correctness of several results in reasoning about differential dependencies ( dds ), originally reported in Song and Chen [2011]. The major concern by Vincent et al. [2015] roots from assuming a type of infeasible differential functions in the given dds for consistency and implication analysis, which are not allowed in Song and Chen [2011]. A differential function is said to be infeasible if there is no tuple pair with values that can satisfy the specified distance constraints. For example, [price(<2, > 4)] requires the difference of two price values to be < 2 and > 4 at the same time, which is clearly impossible. Although dds involving infeasible differential functions may be syntactically interesting, they are semantically meaningless and would neither be specified by domain experts nor discovered from data. For these reasons, infeasible differential functions are not considered [Song and Chen 2011] and the results in Song and Chen [2011] are correct, in contrast to what is claimed in Vincent et al. [2015].

Graphs have been widely used to model complex data in many real-world applications. Answering vertex join queries over large graphs is meaningful and interesting, which can benefit friend recommendation in social networks and link prediction, and so on. In this article, we adopt “SimRank” [13] to evaluate the similarity between two vertices in a large graph because of its generality. Note that “Simank” is purely structure dependent, and it does not rely on the domain knowledge. Specifically, we define a S im R ank-based j oin ( SRJ ) query to find all vertex pairs satisfying the threshold from two sets of vertices U and V . To reduce the search space, we propose a shortest-path-distance-based upper bound for SimRank scores to prune unpromising vertex pairs. In the verification, we propose a novel index, called h-go cover + , to efficiently compute the SimRank score of any single vertex pair. Given a graph G , we only materialize the SimRank scores of a small proportion of vertex pairs (i.e., the h-go cover + vertex pairs), based on which the SimRank score of any vertex pair can be computed easily. To find the h-go cover + vertex pairs, we propose an efficient method without building the vertex-pair graph. Hence, large graphs can be dealt with easily. Extensive experiments over both real and synthetic datasets confirm the efficiency of our solution.

The conventional crowdsourcing paradigm requires an explicit task description and payment scheme. Requesters can then easily determine whether the crowdsourced results are satisfactory, and workers will have a fairly clear expectation of the monetary reward once the task is accomplished. However, such a paradigm becomes problematic when it is applied to Object Identification (OI) tasks. First, for OI tasks, it is difficult for requesters to evaluate whether sufficient numbers of objects have been found by an individual worker, warranting payment. Second, the same objects can be detected by many workers and ending up being unnecessary workload and inefficient performance. In this paper, we design a new crowdsourcing paradigm for OI tasks. Designing such a paradigm is challenging. Firstly, an easily-detected object can be found by multiple workers, which leads to an unfair situation that the requester has to make extra payments for the duplication. Secondly, there is usually a time limit to finish the overall crowdsourcing process, which demands efficient assignment strategy. To address these challenges, we propose solutions to achieve fairness by a Pay-As-You-Go (PAYG) mechanism and efficiency by a new worker-assignment scheme, Adaptive Worker Assignment (AWA). Extensive experiments are conducted to demonstrate the advantages of this new paradigm.

As the volume of the RDF data becomes increasingly large, it is essential for us to design a distributed database system to manage it. For distributed RDF data design, it is quite common to partition the RDF data into some parts, called fragments, which are then distributed. Thus, the distribution design consists of two steps: fragmentation and allocation. In this paper, we propose a method to explore the intrinsic similarities among the structures of queries in a workload for fragmentation and allocation, which aims to reduce the number of crossing matches and the communication cost during SPARQL query processing. Specifically, we mine and select some frequent access patterns to reflect the characteristics of the workload. Based on the selected frequent access patterns, we propose two fragmentation strategies, vertical and horizontal fragmentation strategies, to divide RDF graphs while meeting different kinds of query processing objectives. Vertical fragmentation is for better throughput and horizontal fragmentation is for better performance. After fragmentation, we discuss how to allocate these fragments to various sites. Finally, we discuss how to process a query based on the results of fragmentation and allocation. Extensive experiments confirm the superior performance of our proposed solutions.

With the rapid development of smartphones, spatial crowdsourcing platforms are getting popular. A foundational research of spatial crowdsourcing is to allocate micro-tasks to suitable crowd workers. Most existing studies focus on offline scenarios, where all the spatiotemporal information of micro-tasks and crowd workers is given. However, they are impractical since micro-tasks and crowd workers in real applications appear dynamically and their spatiotemporal information cannot be known in advance. In this paper, to address the shortcomings of existing offline approaches, we first identify a more practical micro-task allocation problem, called the Global Online Micro-task Allocation in spatial crowdsourcing (GOMA) problem. We first extend the state-of-art algorithm for the online maximum weighted bipartite matching problem to the GOMA problem as the baseline algorithm. Although the baseline algorithm provides theoretical guarantee for the worst case, its average performance in practice is not good enough since the worst case happens with a very low probability in real world. Thus, we consider the average performance of online algorithms, a.k.a online random order model.We propose a two-phase-based framework, based on which we present the TGOA algorithm with 1 over 4 -competitive ratio under the online random order model. To improve its efficiency, we further design the TGOA-Greedy algorithm following the framework, which runs faster than the TGOA algorithm but has lower competitive ratio of 1 over 8. Finally, we verify the effectiveness and efficiency of the proposed methods through extensive experiments on real and synthetic datasets.

As one of the three major steps (question design, task assignment, answer aggregation) in crowdsourcing, task assignment directly affects the quality of the crowdsourcing result. A good assignment will not only improve the answers' quality, but also boost the workers' willingness to participate. Although a lot of works have been made to produce better assignment, most of them neglected one of its most important properties: the bipartition, which exists widely in real world scenarios. Such ignorance greatly limits their application under general settings.

Recently, with the development of mobile Internet and smartphones, the online minimum bipartite matching in real time spatial data (OMBM) problem becomes popular. Specifically, given a set of service providers with specific locations and a set of users who dynamically appear one by one, the OMBM problem is to find a maximum-cardinality matching with minimum total distance following that once a user appears, s/he must be immediately matched to an unmatched service provider, which cannot be revoked, before subsequent users arrive. To address this problem, existing studies mainly focus on analyzing the worst-case competitive ratios of the proposed online algorithms, but study on the performance of the algorithms in practice is absent. In this paper, we present a comprehensive experimental comparison of the representative algorithms of the OMBM problem. Particularly, we observe a surprising result that the simple and efficient greedy algorithm, which has been considered as the worst due to its exponential worst-case competitive ratio, is significantly more effective than other algorithms. We investigate the results and further show that the competitive ratio of the worst case of the greedy algorithm is actually just a constant, 3.195, in the average-case analysis. We try to clarify a 25-year misunderstanding towards the greedy algorithm and justify that the greedy algorithm is not bad at all. Finally, we provide a uniform implementation for all the algorithms of the OMBM problem and clarify their strengths and weaknesses, which can guide practitioners to select appropriate algorithms for various scenarios.

With the rapid development of mobile devices and crowdsourcing platforms, the spatial crowdsourcing has attracted much attention from the database community. Specifically, the spatial crowdsourcing refers to sending location-based requests to workers, based on their current positions. In this paper, we consider a spatial crowdsourcing scenario, in which each worker has a set of qualified skills, whereas each spatial task (e.g., repairing a house, decorating a room, and performing entertainment shows for a ceremony) is time-constrained, under the budget constraint, and required a set of skills. Under this scenario, we will study an important problem, namelymulti-skill spatial crowdsourcing(MS-SC), which finds an optimal worker-and-task assignment strategy, such that skills between workers and tasks match with each other, and workers’ benefits are maximized under the budget constraint. We prove that the MS-SC problem is NP-hard and intractable. Therefore, we propose three effective heuristic approaches, including greedy,$g$-divide-and-conquer and cost-model-based adaptive algorithms to get worker-and-task assignments. Through extensive experiments, we demonstrate the efficiency and effectiveness of our MS-SC processing approaches on both real and synthetic data sets.

Since Jeff Howe introduced the term Crowdsourcing in 2006, this human-powered problem-solving paradigm has gained a lot of attention and has been a hot research topic in the field of computer science. Even though a lot of work has been conducted on this topic, so far we do not have a comprehensive survey on most relevant work done in the crowdsourcing field. In this paper, we aim to offer an overall picture of the current state of the art techniques in general-purpose crowdsourcing. According to their focus, we divide this work into three parts, which are: incentive design, task assignment, and quality control. For each part, we start with different problems faced in that area followed by a brief description of existing work and a discussion of pros and cons. In addition, we also present a real scenario on how the different techniques are used in implementing a location-based crowdsourcing platform, gMission. Finally, we highlight the limitations of the current general-purpose crowdsourcing techniques and present some open problems in this area.

Resource Description Framework (RDF) has been widely used in the Semantic Web to describe resources and their relationships. The RDF graph is one of the most commonly used representations for RDF data. However, in many real applications such as the data extraction/integration, RDF graphs integrated from different data sources may often contain uncertain and inconsistent information (e.g., uncertain labels or that violate facts/rules), due to the unreliability of data sources. In this paper, we formalize the RDF data by inconsistent probabilistic RDF graphs, which contain both inconsistencies and uncertainty. With such a probabilistic graph model, we focus on an important problem, quality-aware subgraph matching over inconsistent probabilistic RDF graphs (QA-gMatch), which retrieves subgraphs from inconsistent probabilistic RDF graphs that are isomorphic to a given query graph and with high quality scores (considering both consistency and uncertainty). In order to efficiently answer QA-gMatch queries, we provide two effective pruning methods, namely adaptive label pruning and quality score pruning, which can greatly filter out false alarms of subgraphs. We also design an effective index to facilitate our proposed pruning methods, and propose an efficient approach for processing QA-gMatch queries. Finally, we demonstrate the efficiency and effectiveness of our proposed approaches through extensive experiments.

With the rapid development of Web 2.0 and Online To Offline (O2O) marketing model, variousonlineevent-basedsocialnetworks(EBSNs) are getting popular. An important task of EBSNs is to facilitate the most satisfactory event-participant arrangement for both sides, i.e., events enroll more participants and participants are arranged with personally interesting events. Existing approaches usually focus on the arrangement of each single event to a set of potential users, or ignore the conflicts between different events, which leads to infeasible or redundant arrangements. In this paper, to address the shortcomings of existing approaches, we first identify a more general and useful event-participant arrangement problem, calledGlobalEvent-participantArrangement withConflict andCapacity($GEACC$) problem, focusing on the conflicts of different events and making event-participant arrangements in a global view. We find that the GEACC problem is NP-hard due to the conflicts among events. Thus, we design two approximation algorithms with provable approximation ratios and an exact algorithm with pruning technique to address this problem. In addition, we propose an online setting of GEACC, called OnlineGEACC, which is also practical in real-world scenarios. We further design an online algorithm with provable performance guarantee. Finally, we verify the effectiveness and efficiency of the proposed methods through extensive experiments on real and synthetic datasets.

Although$k$NN search on a road network$G_r$, i.e., finding$k$nearest objects to a query user$q$on$G_r$, has been extensively studied, existing works neglected the fact that the$q$'s social information can play an important role in this$k$NN query. Many real-world applications, such as location-based social networking services, require such a query. In this paper, we study a new problem:$k$NN search on road networks by incorporating social influence (RSkNN). Specifically, the state-of-the-artIndependent Cascade(IC) model in social network is applied to define social influence. One critical challenge of the problem is to speed up the computation of the social influence over large road and social networks. To address this challenge, we propose three efficient index-based search algorithms, i.e., road network-based (RN-based), social network-based (SN-based), and hybrid indexing algorithms. In the RN-based algorithm, we employ a filtering-and-verification framework for tackling the hard problem of computing social influence. In the SN-based algorithm, we embed social cuts into the index, so that we speed up the query. In the hybrid algorithm, we propose an index, summarizing the road and social networks, based on which we can obtain query answers efficiently. Finally, we use real road and social network data to empirically verify the efficiency and efficacy of our solutions.

Social networks are large graphs that require multiple graph database servers to store and manage them. Each database server hosts a graph partition with the objectives of bal-ancing server loads, reducing remote traversals (edge-cuts), and adapting the partitioning to changes in the structure of the graph in the face of changing workloads. To achieve these objectives, a dynamic repartitioning algorithm is re-quired to modify an existing partitioning to maintain good quality partitions while not imposing a significant overhead to the system. In this paper, we introduce a lightweight repartitioner, which dynamically modifies a partitioning us-ing a small amount of resources. In contrast to the exist-ing repartitioning algorithms, our lightweight repartitioner is efficient, making it suitable for use in a real system. We integrated our lightweight repartitioner into Hermes, which we designed as an extension of the open source Neo4j graph database system, to support workloads over partitioned graph data distributed over multiple servers. Using real-world social network data, we show that Hermes leverages the lightweight repartitioner to maintain high quality partitions and provides a 2 to 3 times performance improvement over the de-facto standard random hash-based partitioning. 1.

Bike-sharing systems are widely deployed in many major cities, providing a convenient transportation mode for citizens' commutes. As the rents/returns of bikes at different stations in different periods are unbalanced, the bikes in a system need to be rebalanced frequently. Real-time monitoring cannot tackle this problem well as it takes too much time to reallocate the bikes after an imbalance has occurred. In this paper, we propose a hierarchical prediction model to predict the number of bikes that will be rent from/returned to each station cluster in a future period so that reallocation can be executed in advance. We first propose a bipartite clustering algorithm to cluster bike stations into groups, formulating a two-level hierarchy of stations. The total number of bikes that will be rent in a city is predicted by a Gradient Boosting Regression Tree (GBRT). Then a multi-similarity-based inference model is proposed to predict the rent proportion across clusters and the inter-cluster transition, based on which the number of bikes rent from/ returned to each cluster can be easily inferred. We evaluate our model on two bike-sharing systems in New York City (NYC) and Washington D.C. (D.C.) respectively, confirming our model's advantage beyond baseline approaches (0.03 reduction of error rate), especially for anomalous periods (0.18/0.23 reduction of error rate).

In this 3-hour tutorial, we present the landscape of recent developments in data management and mining research, and survey a selected set of state-of-the-art works that significantly extended existing database reserach in order to incorporate and exploit the novel notion of “crowdsourcing” in a creative fashion. In particular, three speakers take turns to present the topics of human-powered database operations, crowdsourced data mining, and the application of crowdsourcing in social media, respectively.

With the rapid development of Web 2.0 and Online To Offline (O2O) marketing model, various online event-based social networks (EBSNs), such as Meetup and Whova, are getting popular. An important task of EBSNs is to facilitate the most satisfactory event-participant arrangement for both sides, i.e. events enroll more participants and participants are arranged with personally interesting events. Existing approaches usually focus on the arrangement of each single event to a set of potential users, and ignore the conflicts between different events, which leads to infeasible or redundant arrangements. In this paper, to address the shortcomings of existing approaches, we first identify a more general and useful event-participant arrangement problem, called Global Event-participant Arrangement with Conflict and Capacity (GEACC) problem, focusing on the conflicts of different events and making event-participant arrangements in a global view. Though it is useful, unfortunately, we find that the GEACC problem is NP-hard due to the conflict constraints among events. Thus, we design two approximation algorithms with provable approximation ratios and an exact algorithm with pruning technique to address this problem. Finally, we verify the effectiveness and efficiency of the proposed methods through extensive experiments on real and synthetic datasets.

In this demonstration, we present the gStore RDF triple store. gStore is based on graph encoding and subgraph match, distinct from many other systems. More importantly, it can handle, in a uniform manner, different data types (strings and numerical data) and SPARQL queries with wildcards, aggregate, range and top-k operators over dynamic RDF datasets. We will demonstrate the main features of our system, show how to search Wikipedia documents using gStore and how to build users' own application using gStore through C++/Java API.

Uncertain data has been emerged as an important problem in database systems due to the imprecise nature of many applications. To handle the uncertainty, probabilistic databases can be used to store uncertain data, and querying facilities are provided to yield answers with confidence. However, the uncertainty may propagate, hence the returned results from a query or mining process may not be useful. In this paper, we leverage the power of crowdsourcing for cleaning uncertain data. Specifically, we will design a set of Human Intelligence Tasks (HIT)s to ask a crowd to improve the quality of uncertain data. Each HIT is associated with a cost, thus, we need to design solutions to maximize the data quality with minimal number of HITs. There are two obstacles for this non-trivial optimization - first, the crowd has a probability to return incorrect answers; second, the HITs decomposed from uncertain data are often correlated. These two obstacles lead to very high computational cost for selecting the optimal set of HITs. Thus, in this paper, we have addressed these challenges by designing an effective approximation algorithm and an efficient heuristic solution. To further improve the efficiency, we derive tight lower and upper bounds, which are used for effective filtering and estimation. We have verified the solutions with extensive experiments on both a simulated crowd and a real crowdsourcing platform.

Recently, taxonomy has attracted much attention. Both automatic construction solutions and human-based computation approaches have been proposed. The automatic methods suffer from the problem of either low precision or low recall and human computation, on the other hand, is not suitable for large scale tasks. Motivated by the shortcomings of both approaches, we present a hybrid framework, which combines the power of machine-based approaches and human computation (the crowd) to construct a more complete and accurate taxonomy. Specifically, our framework consists of two steps: we first construct a complete but noisy taxonomy automatically, then crowd is introduced to adjust the entity positions in the constructed taxonomy. However, the adjustment is challenging as the budget (money) for asking the crowd is often limited. In our work, we formulate the problem of finding the optimal adjustment as an entity selection optimization (ESO) problem, which is proved to be NP-hard. We then propose an exact algorithm and a more efficient approximation algorithm with an approximation ratio of 1/2(1-1/e). We conduct extensive experiments on real datasets, the results show that our hybrid approach largely improves the recall of the taxonomy with little impairment for precision.

Online event-based social network (EBSN) platforms are becoming popular these days. An important task of managing EBSNs is to arrange proper social events to interested users. Existing approaches usually assume that each user only attends one event or ignore location information. The overall utility of such strategy is limited in real world: 1) each user may attend multiple events; 2) attending multiple events will incur spatio-temporal conflicts and travel expenses. Thus, a more intelligent EBSN platform that provides personalized event planning for each participant is desired. In this paper, we first formally define the problem of Utility-aware Social Event-participant Planning (USEP), which is proven to be NP-hard. To solve the USEP problem, we first devise a greedy-based heuristic algorithm, which performs fast under certain circumstances but has no approximation guarantee. We then present a two-step approximation framework, which not only guarantees a 1/2-approximation ratio but also includes a series of optimization techniques to improve its space/time efficiency. Finally, we verify the efficiency and effectiveness of the proposed methods through extensive experiments on real and synthetic datasets.

The creation of sharing communities has resulted in the astonishing increasing of digital videos, and their wide applications in the domains such as entertainment, online news broadcasting etc. The improvement of these applications relies on effective solutions for social user access to video data. This fact has driven the recent research interest in social recommendation in shared communities. Although certain effort has been put into video recommendation in shared communities, the contextual information on social users has not been well exploited for effective recommendation. In this paper, we propose an approach based on the content and social information of videos for the recommendation in sharing communities. Specifically, we first exploit a robust video cuboid signature together with the Earth Mover's Distance to capture the content relevance of videos. Then, we propose to identify the social relevance of clips using the set of users belonging to a video. We fuse the content relevance and social relevance to identify the relevant videos for recommendation. Following that, we propose a novel scheme called sub-community-based approximation together with a hash-based optimization for improving the efficiency of our solution. Finally, we propose an algorithm for efficiently maintaining the social updates in dynamic shared communities. The extensive experiments are conducted to prove the high effectiveness and efficiency of our proposed video recommendation approach.

With the rapid development of mobile devices and the crowdsourcing platforms, the spatial crowdsourcing has attracted much attention from the database community, specifically, spatial crowdsourcing refers to sending a location-based request to workers according to their positions. In this paper, we consider an important spatial crowdsourcing problem, namely reliable diversity-based spatial crowdsourcing (RDB-SC), in which spatial tasks (such as taking videos/photos of a landmark or firework shows, and checking whether or not parking spaces are available) are time-constrained, and workers are moving towards some directions. Our RDB-SC problem is to assign workers to spatial tasks such that the completion reliability and the spatial/temporal diversities of spatial tasks are maximized. We prove that the RDB-SC problem is NP-hard and intractable. Thus, we propose three effective approximation approaches, including greedy, sampling, and divide-and-conquer algorithms. In order to improve the efficiency, we also design an effective cost-model-based index, which can dynamically maintain moving workers and spatial tasks with low cost, and efficiently facilitate the retrieval of RDB-SC answers. Through extensive experiments, we demonstrate the efficiency and effectiveness of our proposed approaches over both real and synthetic datasets.

Differential privacy (DP) has been widely explored in academia recently but less so in industry possibly due to its strong privacy guarantee. This paper makes the first attempt to implement three basic DP architectures in the deployed telecommunication (telco) big data platform for data mining applications. We find that all DP architectures have less than 5% loss of prediction accuracy when the weak privacy guarantee is adopted (e.g., privacy budget parameter ε ≥ 3). However, when the strong privacy guarantee is assumed (e.g., privacy budget parameter ε ≤ 0:1), all DP architectures lead to 15% ~ 30% accuracy loss, which implies that real-word industrial data mining systems cannot work well under such a strong privacy guarantee recommended by previous research works. Among the three basic DP architectures, the Hybridized DM (Data Mining) and DB (Database) architecture performs the best because of its complicated privacy protection design for the specific data mining algorithm. Through extensive experiments on big data, we also observe that the accuracy loss increases by increasing the variety of features, but decreases by increasing the volume of training data. Therefore, to make DP practically usable in large-scale industrial systems, our observations suggest that we may explore three possible research directions in future: (1) Relaxing the privacy guarantee (e.g., increasing privacy budget ε) and studying its effectiveness on specific industrial applications; (2) Designing specific privacy scheme for specific data mining algorithms; and (3) Using large volume of data but with low variety for training the classification models.

Large-scale, highly-interconnected networks pervade both our society and the natural world around us. Uncertainty, on the other hand, is inherent in the underlying data due to a variety of reasons, such as noisy measurements, lack of precise information needs, inference and prediction models, or explicit manipulation, e.g., for privacy purposes. Therefore, uncertain, or probabilistic, graphs are increasingly used to represent noisy linked data in many emerging application scenarios, and they have recently become a hot topic in the database research community. While many classical graph algorithms such as reachability and shortest path queries become # P -complete, and hence, more expensive in uncertain graphs; various complex queries are also emerging over uncertain networks, such as pattern matching, information diffusion, and influence maximization queries. In this tutorial, we discuss the sources of uncertain graphs and their applications, uncertainty modeling, as well as the complexities and algorithmic advances on uncertain graphs processing in the context of both classical and emerging graph queries. We emphasize the current challenges and highlight some future research directions.

SimRank is an important measure of vertex-pair similarity according to the structure of graphs. The similarity search based on SimRank is an important operation for identifying similar vertices in a graph and has been employed in many data analysis applications. Nowadays, graphs in the real world become much larger and more dynamic. The existing solutions for similarity search are expensive in terms of time and space cost. None of them can efficiently support similarity search over large dynamic graphs. In this paper, we propose a novel two-stage random-walk sampling framework (TSF) for SimRank-based similarity search (e.g., top- k search). In the preprocessing stage, TSF samples a set of one-way graphs to index raw random walks in a novel manner within O ( NR g ) time and space, where N is the number of vertices and R g is the number of one-way graphs. The one-way graph can be efficiently updated in accordance with the graph modification, thus TSF is well suited to dynamic graphs. During the query stage, TSF can search similar vertices fast by naturally pruning unqualified vertices based on the connectivity of one-way graphs. Furthermore, with additional R q samples, TSF can estimate the SimRank score with probability [EQUATION] if the error of approximation is bounded by 1 -- ε. Finally, to guarantee the scalability of TSF, the one-way graphs can also be compactly stored on the disk when the memory is limited. Extensive experiments have demonstrated that TSF can handle dynamic billion-edge graphs with high performance.

Incomplete information often occur along with many database applications, e.g., in data integration, data cleaning or data exchange. The idea of data imputation is to fill the missing data with the values of its neighbors who share the same information. Such neighbors could either be identified certainly by editing rules or statistically by relational dependency networks. Unfortunately, owing to data sparsity, the number of neighbors (identified w.r.t. value equality) is rather limited, especially in the presence of data values with variances. In this paper, we argue to extensively enrich similarity neighbors by similarity rules with tolerance to small variations. More fillings can thus be acquired that the aforesaid equality neighbors fail to reveal. To fill the missing values more , we study the problem of maximizing the missing data imputation. Our major contributions include (1) the np-hardness analysis on solving and approximating the problem, (2) exact algorithms for tackling the problem, and (3) efficient approximation with performance guarantees. Experiments on real and synthetic data sets demonstrate that the filling accuracy can be improved.

The recent surge in popularity of crowdsourcing has brought with it a new opportunity for engaging human intelligence in the process of data analysis. Crowdsourcing provides a fundamental mechanism for enabling online workers to participate in tasks that are either too difficult to be solved solely by a computer or too expensive to employ experts to perform. In the field of social science, four elements are required to form a wise crowd - Diversity of Opinion, Independence, Decentralization and Aggregation. However, while the other three elements are already studied and implemented in current crowdsourcing platforms, the 'Diversity of Opinion' has not been functionally enabled. In this paper, we address the algorithmic optimizations towards the diversity of opinion of crowdsourcing marketplaces. From a computational perspective, in order to build a wise crowd, we need to quantitatively modeling the diversity, and take it into consideration for constructing the crowd. In a crowdsourcing marketplace, we usually encounter two basic paradigms for worker selection: building a crowd to wait for tasks to come and selecting workers for a given task. Therefore, we propose our Similarity-driven Model (S-Model) and Task-driven Model (T-Model) for both of the paradigms. Under both of the models, we propose efficient and effective algorithms to enlist a budgeted number of workers, which have the optimal diversity. We have verified our solutions with extensive experiments on both synthetic datasets and real data sets.

Given two sets of vertices in a graph, it is often of a great interest to find out how these vertices are connected, especially to identify the vertices of high prominence defined on the topological structure. In this work, we formally define a V ertex S et B onding query (shorted as VSB), which returns a minimum set of vertices with the maximum importance w.r.t total betweenness and shortest path reachability in connecting two sets of input vertices. We find that such a kind of query is representative and could be widely applied in many real world scenarios, e.g., logistic planning, social community bonding and etc. Challenges are that many of such applications are constructed on graphs that are too large to fit in single server, and the VSB query evaluation turns to be NP-hard. To cope with the scalability issue and return the near optimal result in almost real time, we propose a generic solution framework on a shared nothing distributed environment. With the development of two novel techniques, guided graph exploration and betweenness ranking on exploration, we are able to efficiently evaluate queries for error bounded results with bounded space cost. We demonstrate the effectiveness of our solution with extensive experiments over both real and synthetic large graphs on the Google's Cloud platform. Comparing to the exploration only baseline method, our method achieves several times of speedup.

In many real applications, RDF (Resource Description Framework) has been widely used as a W3C standard to describe data in the Semantic Web. In practice, RDF data may often suffer from the unreliability of their data sources, and exhibit errors or inconsistencies. In this paper, we model such unreliable RDF data by probabilistic RDF graphs, and study an important problem, keyword search query over probabilistic RDF graphs (namely, the pg-KWS query). To retrieve meaningful keyword search answers, we design the score rankings for subgraph answers specific for RDF data. Furthermore, we propose effective pruning methods (via offline pre-computed score bounds and probabilistic threshold) to quickly filter out false alarms. We construct an index over the pre-computed data for RDF, and present an efficient query answering approach through the index. Extensive experiments have been conducted to verify the effectiveness and efficiency of our proposed approaches.

This paper studies the generic location-aware rank query (GLRQ) over a set of location-aware objects. A GLRQ is composed of a spatial location, a set of keywords, a query predicate, and a ranking function formulated on location, text and other attributes. The result consists of k objects satisfying the predicate ranked according to the ranking function. An example is a query searching for the restaurants that 1) are nearby, 2) offer “American” food, and 3) have high ratings (rating > 4.0). Such queries can not be processed efficiently using existing techniques. In this work, we propose a novel framework called LINQ for efficient processing of GLRQs. To handle the predicate and the attribute-based scoring, we devise a new index structure called synopses tree, which contains the synopses of different subsets of the dataset. The synopses tree enables pruning of search space according to the satisfiability of the predicate. To process the query constraints over the location and keywords, the framework integrates the synopses tree with the spatio-textual index such as IR-tree. The framework therefore is capable of processing the GLRQs efficiently and holistically. We conduct extensive experiments to demonstrate that our solution provides excellent query performance.

With the increasing availability of graph data and widely adopted cloud computing paradigm, graph partitioning has become an efficient pre-processing technique to balance the computing workload and cope with the large scale of input data. Since the cost of partitioning the entire graph is strictly prohibitive, there are some recent tentative works towards streaming graph partitioning which run faster, are easily parallelized, and can be incrementally updated. Most of the existing works on streaming partitioning assume that worker nodes within a cluster are homogeneous in nature. Unfortunately, this assumption does not always hold. Experiments show that these homogeneous algorithms suffer a significant performance degradation when running at heterogeneous environment. In this paper, we propose a novel adaptive streaming graph partitioning approach to cope with heterogeneous environment. We first formally model the heterogeneous computing environment with the consideration of the unbalance of computing ability (e.g., the CPU frequency) and communication ability (e.g., the network bandwidth) for each node. Based on this model, we propose a new graph partitioning objective function that aims to minimize the total execution time of the graph-processing job. We then explore some simple yet effective streaming algorithms for this objective function that can achieve balanced and efficient partitioning result. Extensive experiments are conducted on a moderate sized computing cluster with real-world web and social network graphs. The results demonstrate that the proposed approach achieves significant improvement compared with the state-of-the-art solutions.

Distance join queries have recently been recognized as a particularly useful operation over graph data, since they capture graph similarity in a meaningful way. Consequently, they have been studied extensively in recent years [1], [2]. However, current methods are designed for centralized systems, and rely on the graph embedding for effective pruning and indexing. As graph sizes become very large and graph data must be deployed in the distributed environment, these techniques become impractical. In this work, we propose a solution for efficient parallel processing of distance join queries over distributed large graphs. There have been emerging efforts devoted to managing large graphs in distributed and parallel systems. Programming models like Pregel [3] and iterative computing framework like HaLoop [4] have been proposed to handle queries over distributed graphs. However, they are designed in the perspective of functionality instead of the query efficiency. In this work, we define an optimization problem: combining the iterative join and the graph exploration method to minimize the evaluation time of distance join queries. Without sacrificing a system's scalability, our technique exploits a light-weight vertex centric encoding schema built on a distance-aware partition of the entire graph. Extensive experiments over both real and synthetic large graphs show that, by employing an adaptive query plan generation and scheduling method, we can effectively reduce the redundant message passing and I/O costs. Compared to simply using iterative join or graph exploration method, our solution achieves as many as one order of magnitude of time saving for the query evaluation.

In recent years, with the emergence of a number of new real applications, such as protein-protein interaction (PPI) networks, visual pattern recognition, and intelligent traffic systems, managing huge volumes of uncertain graphs has attracted much attention in the database community. Currently, most existing fundamental queries over graphs only support deterministic (or certain) graphs, although real graph data are often noisy, inaccurate, and incomplete. In this paper, we study a new type of uncertain graph query, probabilistic supergraph containment query over large uncertain graphs. Specifically, given an uncertain graph database UGD which contains a set of uncertain graphs, a deterministic query graph q, and a probabilistic threshold δ, a probabilistic supergraph containment query is to find the set of uncertain graphs from UGD, denoted as UGDq, such that UGDq={ugi∈ UGD|Pr(ugi⊆ q)≥δ} where Pr(ugi⊆q) means the likelihood that ugi is a subgraph of q. We prove that the computation of Pr(ugi⊆q) is #P-hard and design an efficient filtering-and-verification framework to avoid the expensive computation. In particular, we propose an effective filtering strategy and a novel probabilistic inverted index, called PS-Index, to enhance pruning power in the filtering phase. Furthermore, the candidate graphs which pass the filtering phase are tested in the verification phase via an efficient unequal probability sampling-based approximation algorithm. Finally, we verify the effectiveness and efficiency of the proposed methods through extensive experiments.

Many studies have been conducted on seeking an efficient solution for pattern matching over graphs. This interest is largely due to large number of applications in many fields, which require efficient solutions for pattern matching, including protein complex prediction, social network analysis and structural pattern recognition. However, in many real applications, the graph data are often noisy, incomplete, and inaccurate. In other words, there exist many uncertain graphs. Therefore, in this paper, we study pattern matching in a large uncertain graph. Specifically, we want to retrieve all qualified matches of a query pattern in the uncertain graph. Though pattern matching over an uncertain graph is NP-hard, we employ a filtering-and verification framework to speed up the search. In the filtering phase, we propose a probabilistic matching tree, PM-tree, based on match cuts obtained by a cut selection process. Based on PM-tree, we devise a collective pruning strategy to prune a large number of unqualified matches. During the verification phase, we develop an efficient sampling algorithm to validate the remaining candidates. Extensive experimental results demonstrate the effectiveness and efficiency of the proposed algorithms.

The popularity of crowdsourcing has recently brought about brand new opportunities for engaging human intelligence in the process of data analysis. Most existing works on crowdsourcing have developed sophisticated methods to utilize the crowd as a new kind of processor, a.k.a. Human Processor Units (HPU). In this paper, we propose a framework, called MaC, to combine the powers of both CPUs and HPUs. In order to build MaC, we need to tackle the following two challenges: (1) HIT Selection: Selecting the "right" HITs (Human Intelligent Tasks) can help reducing the uncertainty significantly and the results can converge quickly. Thus, we propose an entropy-based model to evaluate the informativeness of HITs. Furthermore, we find that selecting HITs has factorial complexity and the optimization function is non-linear, thus, we propose an efficient approximation algorithm with a bounded error. (2) Uncertainty Management: Crowdsourced answers can be inaccurate. To address this issue, we provide effective solutions in three common scenarios of crowdsourcing: (a) the answer and the confidence of each worker are available; (b) the confidence of each worker and the voting score for each HIT are available; (c) only the answer of each worker is available. To verify the effectiveness of the MaC framework, we built a hybrid Machine-Crowd system and tested it on three real-world applications - data fusion, information extraction and pattern recognition. The experimental results verified the effectiveness and the applicability of our framework.

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.

As travel is taking more significant part in our life, route recommendation service becomes a big business and attracts many major players in IT industry. Given a pair of user-specified origin and destination, a route recommendation service aims to provide users with the routes of best travelling experience according to criteria, such as travelling distance, travelling time, traffic condition, etc. However, previous research shows that even the routes recommended by the big-thumb service providers can deviate significantly from the routes travelled by experienced drivers. It means travellers' preferences on route selection are influenced by many latent and dynamic factors that are hard to model exactly with pre-defined formulas. In this work we approach this challenging problem with a very different perspective- leveraging crowds' knowledge to improve the recommendation quality. In this light, CrowdPlanner - a novel crowd-based route recommendation system has been developed, which requests human workers to evaluate candidate routes recommended by different sources and methods, and determine the best route based on their feedbacks. In this paper, we particularly focus on two important issues that affect system performance significantly: (1) how to efficiently generate tasks which are simple to answer but possess sufficient information to derive user-preferred routes; and (2) how to quickly identify a set of appropriate domain experts to answer the questions timely and accurately. Specifically, the task generation component in our system generates a series of informative and concise questions with optimized ordering for a given candidate route set so that workers feel comfortable and easy to answer. In addition, the worker selection component utilizes a set of selection criteria and an efficient algorithm to find the most eligible workers to answer the questions with high accuracy. A prototype system has been deployed to many voluntary mobile clients and extensive tests on real-scenario queries have shown the superiority of CrowdPlanner in comparison with the results given by map services and popular route mining algorithms.

Multi-version data is often one of the most concerned information on the Web since this type of data is usually updated frequently. Even though there exist some Web information integration systems that try to maintain the latest update version, the maintained multi-version data usually includes inaccurate and invalid information due to the data integration or update delay errors. In this demo, we present CrowdCleaner, a smart data cleaning system for cleaning multi-version data on the Web, which utilizes crowdsourcing-based approaches for detecting and repairing errors that usually cannot be solved by traditional data integration and cleaning techniques. In particular, CrowdCleaner blends active and passive crowdsourcing methods together for rectifying errors for multi-version data. We demonstrate the following four facilities provided by CrowdCleaner: (1) an error-monitor to find out which items (e.g., submission date, price of real estate, etc.) are wrong versions according to the reports from the crowds, which belongs to a passive crowdsourcing strategy; (2) a task-manager to allocate the tasks to human workers intelligently; (3) a smart-decision-maker to identify which answer from the crowds is correct with active crowdsourcing methods; and (4) a whom-to-ask-finder to discover which users (or human workers) should be the most credible according to their answer records.

Knapsack problems range over a large sphere of real world challenges [?]. For example, every year a professor has to decide her new “squad” of students/staff from possibly hundreds of candidates, while having a restricted budget of funding in consideration. Moreover, in many cases, she has to resort to her colleagues and senior students to make comparisons among the candidates. The difficulties of such tasks are mainly three-fold: 1) the knowledge about the candidates are distributed among a crowd; 2) the underlying factors are human-intrinsic and hard to be formatted; 3) the size of candidates exceeds the capacity of human for a one-shot decision. Other examples in this category include gear set preparation for a venture trip, syllabus design for a popular course and inventory design for goods shelf, where the two difficulties are commonly observed. Consequently, a person may be heavily entangled to work out a final decision, which may even be inaccurate. Driven by this demand, in this demo, we present C-DMr - a Crowd-powered Decision Maker that incorporates the wisdom of the informed crowds to solve such real world Knapsack Problems. The core module of this web-based system is a set of algorithms along with a novel interactive interface. The interface incrementally presents comparison jobs and motivates the crowd to participate with a rewarding mechanism, and the set of algorithms solves the Knapsack Problem given only pairwise preferences among candidates. We demonstrate the novelty and usefulness of C-DMr by forming a aforementioned “squad” for a recruiting professor. Specifically four functionalities are shown: 1) a Candidates Entrance that collects the information about all candidates; 2) a Jury Trial that facilitates informed crowds to contribute preferences; 3) an Knapsack Analyzer that measures the on-going “squad”; and 4) a Consultant that recommends a final set of candidates to the professor.

We often care about people's degrees of belief about certain events: e.g. causality between an action and the outcomes, odds distribution among the outcome of a horse race and so on. It is well recognized that the best form to elicit opinion from human is probability distribution instead of simple voting, because the form of distribution retains the delicate information that an opinion expresses. In the past, opinion elicitation has relied on experts, who are expensive and not always available. More recently, crowdsourcing has gained prominence as an inexpensive way to get a great deal of human input. However, traditional crowdsourcing has primarily focused on issuing very simple (e.g. binary decision) tasks to the crowd. In this paper, we study how to use crowds for Opinion Elicitation. There are three major challenges to eliciting opinion information in the form of probability distributions: how to measure the quality of distribution; how to aggregate the distributions; and, how to strategically implement such a system.

In recent years, with the widespread usage of Web 2.0 techniques, crowdsourcing plays an important role in offering human intelligence in various service websites, such as Yahoo! Answer and Quora. With the increasing amount of crowd-oriented service data, an important task is to analyze latest hot topics and track topic evolution over time. However, the existing techniques in text mining cannot effectively work due to the unique structure of crowd-oriented service data, task-response pairs, which consists of the task and its corresponding responses. In particular, existing approaches become ineffective with the ever-increasing crowd-oriented service data that accumulate along the time. In this paper, we first study the problem of discovering topics over crowd-oriented service data. Then we propose a new probabilistic topic model, the Topic Crowd Service Model (TCS model), to effectively discover latent topics from massive crowd-oriented service data. In particular, in order to train TCS efficiently, we design a novel parameter inference algorithm, the Bucket Parameter Estimation (BPE), which utilizes belief propagation and a new sketching technique, called Pairwise Sketch (pSketch). Finally, we conduct extensive experiments to verify the effectiveness and efficiency of the TCS model and the BPE algorithm.

A cohesive subgraph is a primary vehicle for massive graph analysis, and a newly introduced cohesive subgraph, k-truss, which is motivated by a natural observation of social cohesion, has attracted more and more attention. However, the existing parallel solutions to identify the k-truss are inefficient for very large graphs, as they still suffer from huge communication cost and large number of iterations during the computation. In this paper, we propose a novel parallel and efficient truss detection algorithm, called PeTa. The PeTa produces a triangle complete subgraph (TC-subgraph) for every computing node. Based on the TC-subgraphs, PeTa can detect the local k-truss in parallel within a few iterations. We theoretically prove, within this new paradigm, the communication cost of PeTa is bounded by three times of the number of triangles, the total computation complexity of PeTa is the same order as the best known serial algorithm and the number of iterations for a given partition scheme is minimized as well. Furthermore, we present a subgraph-oriented model to efficiently express PeTa in parallel graph computing systems. The results of comprehensive experiments demonstrate, compared with the existing solutions, PeTa saves 2X to 19X in communication cost, reduces 80% to 95% number of iterations and improves the overall performance by 80% across various real-world graphs.

Subgraph listing is a fundamental operation to many graph and network analyses. The problem itself is computationally expensive and is well-studied in centralized processing algorithms. However, the centralized solutions cannot scale well to large graphs. Recently, several parallel approaches are introduced to handle the large graphs. Unfortunately, these parallel approaches still rely on the expensive join operations, thus cannot achieve high performance. In this paper, we design a novel parallel subgraph listing framework, named PSgL. The PSgL iteratively enumerates subgraph instances and solves the subgraph listing in a divide-and-conquer fashion. The framework completely relies on the graph traversal, and avoids the explicit join operation. Moreover, in order to improve its performance, we propose several solutions to balance the workload and reduce the size of intermediate results. Specially, we prove the problem of partial subgraph instance distribution for workload balance is NP-hard, and carefully design a set of heuristic strategies. To further reduce the enormous intermediate results, we introduce three independent mechanisms, which are automorphism breaking of the pattern graph, initial pattern vertex selection based on a cost model, and a pruning method based on a light-weight index.

Schema matching is a central challenge for data integration systems. Due to the inherent uncertainty arose from the inability of schema in fully capturing the semantics of the represented data, automatic tools are often uncertain about suggested matching results. However, human is good at understanding data represented in various forms and crowdsourcing platforms are making the human annotation process more affordable. Thus in this demo, we will show how to utilize the crowd to find the right matching. In order to do that, we need to make the tasks posted on the crowdsouricng platforms extremely simple, to be performed by non-expert people, and reduce the number of tasks as less as possible to save the cost.

As one of the successful forms of using Wisdom of Crowd, crowdsourcing, has been widely used for many human intrinsic tasks, such as image labeling, natural language understanding, market predication and opinion mining. Meanwhile, with advances in pervasive technology, mobile devices, such as mobile phones and tablets, have become extremely popular. These mobile devices can work as sensors to collect multimedia data(audios, images and videos) and location information. This power makes it possible to implement the new crowdsourcing mode: spatial crowdsourcing. In spatial crowdsourcing, a requester can ask for resources related a specific location, the mobile users who would like to take the task will travel to that place and get the data. Due to the rapid growth of mobile device uses, spatial crowdsourcing is likely to become more popular than general crowdsourcing, such as Amazon Turk and Crowdflower. However, to implement such a platform, effective and efficient solutions for worker incentives, task assignment, result aggregation and data quality control must be developed. In this demo, we will introduce gMission, a general spatial crowdsourcing platform, which features with a collection of novel techniques, including geographic sensing, worker detection, and task recommendation. We introduce the sketch of system architecture and illustrate scenarios via several case analysis.

Matching keys, specifying what attributes to compare and how to compare them for identifying the same real-world entities, are found to be useful in applications like record matching, blocking and windowing [7]. Owing to the complex redundant semantics among matching keys, capturing a proper set of matching keys is highly non-trivial. Analogous to minimal/candidate keys w.r.t. functional dependencies, relative candidate keys (RCKs [7], with a minimal number of compared attributes, see a more formal definition in Section 2) can clear up redundant semantics w.r.t. "what attributes to compare". However, we note that redundancy issues may still exist among rcks on the same attributes about "how to compare them". In this paper, we propose to find a concise set of matching keys, which has less redundancy and can still meet the requirements on coverage and validity. Specifically, we study approximation algorithms to efficiently discover a near optimal set. To ensure the quality of matching keys, the returned results are guaranteed to be RCKs (minimal on compared attributes), and most importantly, minimal w.r.t. distance restrictions (i.e., redundancy free w.r.t. "how to compare the attributes"). The experimental evaluation demonstrates that our concise RCK set is more effective than the existing rck choosing method. Moreover, the proposed pruning methods show up to 2 orders of magnitude improvement w.r.t. time costs on concise RCK set discovery.

A broad class of data, ranging from similarity networks, workflow networks to protein networks, can be modeled as graphs with data values as vertex labels. The vertex labels (data values) are often dirty for various reasons such as typos or erroneous reporting of results in scientific experiments. Neighborhood constraints , specifying label pairs that are allowed to appear on adjacent vertexes in the graph, are employed to detect and repair erroneous vertex labels. In this paper, we study the problem of repairing vertex labels to make graphs satisfy neighborhood constraints. Unfortunately, the relabeling problem is proved to be NP hard, which motivates us to devise approximation methods for repairing, and identify interesting special cases (star and clique constraints) that can be efficiently solved. We propose several approximate repairing algorithms including greedy heuristics, contraction method and a hybrid approach. The performances of algorithms are also analyzed for the special case. Our extensive experimental evaluation, on both synthetic and real data, demonstrates the effectiveness of eliminating frauds in several types of application networks. Remarkably, the hybrid method performs well in practice, i.e., guarantees termination, while achieving high effectiveness at the same time.

With the increasing availability and scale of graph data from Web 2.0, graph partitioning becomes one of efficient preprocessing techniques to balance the computing workload. Since the cost of partitioning the entire graph is strictly prohibitive, there are some recent tentative works towards streaming graph partitioning which can run faster, be easily paralleled, and be incrementally updated. Unfortunately, the experiments show that the running time of each partitioning is still unbalanced due to the variation of workload access pattens during the supersteps. In addition, the one-pass streaming partitioning result is not always satisfactory for the algorithms' local view of the graph. In this paper, we present LogGP, a log-based graph partitioning system that records, analyzes and reuses the historical statistical information to refine the partitioning result. LogGP can be used as a middle-ware and deployed to many state-of-the-art paralleled graph processing systems easily. LogGP utilizes the historical partitioning results to generate a hyper-graph and uses a novel hyper-graph streaming partitioning approach to generate a better initial streaming graph partitioning result. During the execution, the system uses running logs to optimize graph partitioning which prevents performance degradation. Moreover, LogGP can dynamically repartition the massive graphs in accordance with the structural changes. Extensive experiments conducted on a moderate size of computing cluster with real-world graph datasets demonstrate the superiority of our approach against the state-of-the-art solutions.

With the widespread use of geo-positioning services (GPS), GPS-based navigation systems have become ever more of an integral part of our daily lives. GPS-based navigation systems usually suggest multiple paths for any given pair of source and target, leaving users perplexed when trying to select the best one among them, namely the problem of best path selection. Too many suggested paths may jeopardize the usability of the recommendation data, and decrease user satisfaction. Although existing studies have already partially relieved this problem through integrating historical traffic logs or updating traffic conditions periodically, their solutions neglect the potential contribution of human experience. In this paper, we resort to crowdsourcing to ease the pain of the best path selection. The first step of appropriately using the crowd is to ask proper questions. For the best path selection problem, simple questions (e.g. binary voting) over compete paths cannot be directly applied to road networks due to their being too complex for crowd workers. Thus, this paper makes the first contribution by designing two types of questions, namely Routing Query (RQ) and Binary Routing Query (BRQ), to ask the crowd to decide which direction to take at each road intersection. Furthermore, we propose a series of efficient algorithms to dynamically manage the questions in order to reduce the selection hardness within a limited budget. Finally, we compare the proposed methods against two baselines, and the effectiveness and efficiency of our proposals are verified by the results from simulations and experiments on a real-world crowdsourcing platform.

Anomaly detection (a.k.a., outlier or burst detection) is a well-motivated problem and a major data mining and knowledge discovery task. In this article, we study the problem of population anomaly detection, one of the key issues related to event monitoring and population management within a city. Through studying detected population anomalies, we can trace and analyze these anomalies, which could help to model city traffic design and event impact analysis and prediction. Although a significant and interesting issue, it is very hard to detect population anomalies and retrieve anomaly trajectories, especially given that it is difficult to get actual and sufficient population data. To address the difficulties of a lack of real population data, we take advantage of mobile phone networks, which offer enormous spatial and temporal communication data on persons. More importantly, we claim that we can utilize these mobile phone data to infer and approximate population data. Thus, we can study the population anomaly detection problem by taking advantages of unique features hidden in mobile phone data. In this article, we present a system to conduct Population Anomaly Detection (PAD). First, we propose an effective clustering method, correlation-based clustering , to cluster the incomplete location information from mobile phone data (i.e., from mobile call volume distribution to population density distribution). Then, we design an adaptive parameter-free detection method, R-scan , to capture the distributed dynamic anomalies. Finally, we devise an efficient algorithm, BT-miner , to retrieve anomaly trajectories . The experimental results from real-life mobile phone data confirm the effectiveness and efficiency of the proposed algorithms. Finally, the proposed methods are realized as a pilot system in a city in China.

Recently, the management of transportation systems has become increasingly important in many real applications such as location-based services, supply chain management, traffic control, and so on. These applications usually involve queries over spatial road networks with dynamically changing and complicated traffic conditions. In this paper, we model such a network by a probabilistic time-dependent graph (PT-Graph), whose edges are associated with uncertain delay functions. We propose a useful query in the PT-Graph, namely a trip planner query (TPQ), which retrieves trip plans that traverse a set of query points in PT-Graph, having the minimum traveling time with high confidence. To tackle the efficiency issue, we present the pruning methods time interval pruning and probabilistic pruning to effectively rule out false alarms of trip plans. Furthermore, we design a pre-computation technique based on the cost model and construct an index structure over the pre-computed data to enable the pruning via the index. We integrate our proposed pruning methods into an efficient query procedure to answer TPQs. Through extensive experiments, we demonstrate the efficiency and effectiveness of our TPQ query answering approach.

The importance of introducing distance constraints to data dependencies, such as differential dependencies (DDs), has recently been recognized. The differential dependencies are tolerant to small variations, which enable them to apply to wide data quality checking applications, such as detecting data violations. However, the determination of distance thresholds for the differential dependencies is non-trivial. It often relies on a truth data instance which embeds the distance constraints. To find useful distance threshold patterns from data, there are several guidelines of statistical measures to specify, e.g., support, confidence and dependent quality. Unfortunately, given a data instance, users might not have any knowledge about the data distribution, thus it is very challenging to set the right parameters. In this paper, we study the determination of distance thresholds for differential dependencies, in a parameter-free style. Specifically, we compute an expected utility based on the statistical measures from the data. According to our analysis as well as experimental verification, distance threshold patterns with higher expected utility could offer better use in real applications, such as violation detection. We then develop efficient algorithms to determine the distance thresholds having the maximum expected utility. Finally, our extensive experimental evaluation demonstrates the effectiveness and efficiency of the proposed methods.

Recently, due to ubiquitous data uncertainty in many real-life applications, it has become increasingly important to study efficient and effective processing of various probabilistic queries over uncertain data, which usually retrieve uncertain objects that satisfy query predicates with high probabilities. However, one annoying, yet challenging, problem is that, some probabilistic queries are very sensitive to low-quality objects in uncertain databases, and the returned query answers might miss some important results (due to low data quality). To identify both accurate query answers and those potentially low-quality objects, in this paper, we investigate the causes of query answers/non-answers from a novel angle of causality and responsibility (CR), and propose a new interpretation of probabilistic queries. Particularly, we focus on the problem of CR-based probabilistic nearest neighbor (CR-PNN) query, and design a general framework for answering CR-based queries (including CR-PNN), which can return both query answers with high confidences and low-quality objects that may potentially affect query results (for data cleaning purposes). To efficiently process CR-PNN queries, we propose effective pruning strategies to quickly filter out false alarms, and design efficient algorithms to obtain CR-PNN answers. Extensive experiments have been conducted to verify the efficiency and effectiveness of our proposed approaches.

With the abundance and ubiquity of mobile devices, a new class of applications, called spatial crowdsourcing, is emerging, which enables spatial tasks (i.e., tasks related to a location) assigned to and performed by human workers. However, one of the major challenges with spatial crowdsourcing is how to verify the validity of the results provided by workers, when the workers are not trusted equally. To tackle this problem, we assume every worker has a reputation score, which states the probability that the worker performs a task correctly. Moreover, we define a confidence level for every spatial task, which states that the answer to the given spatial task is only accepted if its confidence is higher than a certain threshold. Thus, the problem we are trying to solve is to maximize the number of spatial tasks that are assigned to a set of workers while satisfying the confidence levels of those tasks. Note that a unique aspect of our problem is that the optimal assignment of tasks heavily depends on the geographical locations of workers and tasks. This means that every spatial task should be assigned to enough number of workers such that their aggregate reputation satisfies the confidence of the task. Consequently, an exhaustive approach needs to compute the aggregate reputation score (using a typical decision fusion aggregation mechanism, such as voting) for all possible subsets of the workers, which renders the problem complex (we show it is NP-hard). Subsequently, we propose a number of heuristics and utilizing real-world and synthetic data in extensive sets of experiments we show that we can achieve close to optimal performance with the cost of a greedy approach, by exploiting our problem's unique characteristics.

Nowadays, many applications return to the user a set of results that take the query as their nearest neighbor, which are commonly expressed through reverse nearest neighbor (RNN) queries. When considering moving objects, users would like to find objects that appear in the RNN result set for a period of time in some real-world applications such as collaboration recommendation and anti-tracking. In this work, we formally define the problem of interval reverse nearest neighbor (IRNN) queries over moving objects, which return the objects that maintain nearest neighboring relations to the moving query objects for the longest time in the given interval. Location uncertainty of moving data objects and moving query objects is inherent in various domains, and we investigate objects that exhibit Markov correlations, that is, each object's location is only correlated with its own location at previous timestamp while being independent of other objects. There exists the efficiency challenge for answering IRNN queries on uncertain moving objects with Markov correlations since we have to retrieve not only all the possible locations of each object at current time but also its historically possible locations. To speed up the query processing, we present a general framework for answering IRNN queries on uncertain moving objects with Markov correlations in two phases. In the first phase, we apply space pruning and probability pruning techniques, which reduce the search space significantly. In the second phase, we verify whether each unpruned object is an IRNN of the query object. During this phase, we propose an approach termed Probability Decomposition Verification (PDV) algorithm which avoid computing the probability of any object being an RNN of the query object exactly and thus improve the efficiency of verification. The performance of the proposed algorithm is demonstrated by extensive experiments on synthetic and real datasets, and the experimental results show that our algorithm is more efficient than the Monte-Carlo based approximate algorithm.