Data cleaning (DC) is a crucial yet challenging step for many data engineering tasks. Traditional pre-configuration DC methods rely heavily on predefined rules or constraints, demanding significant domain knowledge and manual effort. While configuration-free DC approaches have been explored, they still demand extensive feature engineering or labeled data for intensive model training. In this paper, we propose azero-training and interpretable DCsystem, named${\sf ZeroDC}$, that leverageslarge language models(LLMs) to generate data cleaning rules and chain-of-thoughts (CoTs), without the need for model training.${\sf ZeroDC}$consists of two modules,iterative detection rule generation(IDG) andtraining-free explainable correction(TEC). To generate high-quality error detection rules with minimal human feedback, IDG first bootstraps a set of rules viacontrastive rule initiationon sampled syntactic and semantic contrastive pairs. It then progressively enhances them through aniterative rule refinementworkflow that selects the most informative elements for updates. TEC constructs acontextual-relevant tuple retrieverusing aweighted cosine similarityfunction to efficiently identify the most relevant tuples for each dirty value, reducing redundancy in the LLM prompts and lowering computational costs. It further prompts for generatingcorrection CoTsfor user-corrected representative values, as well as prompts for creatingcorrection rulesandexplainable corrections, which automatically provide explanations for correction results, all without the need for model training. Extensive experiments conducted on various real-world datasets demonstrate that${\sf ZeroDC}$achieves, on average, a 5.36% increase in accuracy and an 8.16x speedup compared to state-of-the-art methods. The codes and datasets of this paper are available athttps://github.com/YangChen32768/ZeroDC.

Error detection (ED) in tabular data is crucial yet challenging due to diverse error types and the need for contextual understanding. Traditional ED methods often rely heavily on manual criteria and labels, making them labor-intensive. Large language models (LLM) can minimize human effort but struggle with errors requiring a comprehensive understanding of data context. In this paper, we propose ZeroED, a novel hybrid error detection framework, which combines LLM reasoning ability with the machine learning pipeline via zero-shot prompting. ZeroED operates in four steps, i.e., feature representation, error labeling, training data construction, and detector training. Initially, to enhance error distinction, ZeroED generates rich data representations using LLM-driven error reason-aware binary features, pre-trained embeddings, and statistical features. Then, ZeroED employs LLM to holistically label errors through incontext learning, guided by a two-step LLM reasoning process for detailed ED guidelines. To reduce token costs, LLMs are applied only to representative data selected via clustering-based sampling. High-quality training data is constructed through in-cluster label propagation and LLM augmentation with verification. Finally, a classifier is trained to detect all errors. Extensive experiments on seven datasets demonstrate that, ZeroED outperforms state-of-the-art methods by a maximum 30 % improvement in F1 score and up to 90% token cost reduction.

Query-based pricing enables personalized data acquisition for data buyers, exhibiting potential in data markets. The state-of-the-art SQL query pricing strategy tackles the #P-hard arbitrage-free pricing task with the quadratic computational complexity, far from promptly fulfilling customer demands. In this paper, we propose a novel arbitrage-free and scalable pricing framework ARIA to calculate the prices for various query types in linear time, including select-project-join and simple aggregate (SPJA) queries. For the first time, we model what the query answer tells about the value of each tuple and formulate the tuple-level information of selection, projection, and simple aggregation queries. We develop several price functions based on the total information gain of all tuples. The containing relationship between the query information prevents possible arbitrage arising from query determinacy. We present efficient price computation algorithms to derive the prices of different types of queries with linear time complexity, which scan the common possible value set of tuples one time. In ARIA, the join query is decomposed as multiple single-relation queries for pricing in linear time. Extensive experiments on real and synthetic datasets demonstrate that, ARIA performs 3x faster than the state of the arts while enjoying desirable pricing characteristics.

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

Correcting missing or erroneous data values is an essential task in data cleaning. Traditional pre-configuration error correction (EC) methods rely heavily on predefined rules or constraints, demanding significant domain knowledge and manual effort. While configuration-free EC approaches have been explored, they still demand extensive feature engineering or labeled data for intensive model training. In this paper, we propose a zero-training and interpretable EC system, named ZeroEC, that leverages large language models (LLMs) to generate chain-of-thoughts (CoTs) and correction rules for EC, without the need for model training. ZeroEC consists of two modules, contextual-relevant tuple search (CTS) and training-free explainable correction (TEC). CTS constructs a contextual-relevant tuple retriever using a weighted cosine similarity function to efficiently identify the most relevant tuples for each dirty tuple, reducing redundancy in the LLM prompts and lowering computational costs. TEC employs a clustering-based representative tuple sampling strategy to alleviate “hallucination” risk by exposing LLMs to diverse types of data errors. It further prompts for generating correction CoTs for user-corrected representative tuples, as well as prompts for creating correction rules and explainable ECs, which automatically provide explanations for EC, all without the need for model training. Extensive experiments conducted on various real-world datasets demonstrate that ZeroEC achieves a 66.82% increase in accuracy and a 6.87x speedup compared to state-of-the-art methods. The codes and datasets of this paper are available at https://github.com/YangChen32768/ZeroEC.

Session-based Recommendation (SBR) explores dynamic user interests based on short anonymous sessions. The performance of traditional ID-collaborative SBR models is constrained by the limited session length. To this end, we focus on Multi-modal Session-based Recommendation (MMSBR), which aims to leverage modality knowledge to promote short-term user interest modeling. Previous studies cannot solve the MMSBR problem well due to issues as: (I1) Modal-invariant and specific dependencies are difficult to disentangle and unify. (I2) Multiple modal transitions produce mutual effects. (I3) Modal-aware personalized preference discrepancy exists. Thus, we propose a modality-aware diffusion-based framework MDSD with subspace disentanglement, which decouples multi-modal collaborations and provides a new paradigm that integrates modality representation generation into next-item prediction. We first employ modality-disentangled consistency graphs based on affinity semantics to extract the unified modal subspace. Then we design a cross-modal contrastive attention fusion that explores cross-modality interplay, enhancing modal alignment and consistency. To interpret personalized interest discrepancy, we realize the preference-guided multi-modal diffusion, which combines modality-aware interest generation with prediction based on collaborative signals, thus providing comprehensive recommendation results. Extensive experiments on real-world datasets demonstrate the effectiveness of MDSD.

Electronic health records (EHRs) are the de facto standard for analyzing comprehensive patient conditions. Existing methods mainly employ specialized neural networks to extract modality-specific information, followed by modality correlation modeling to support clinical decision-making. However, these methods generally overlook the issue of ''contaminated'' representations inherent in routine EHR data, which can undermine the model's discriminative ability, as less relevant representations associated with false positive correlations may impede the recognition of truly effective representations. To address the issue of representation contamination, we propose CLEAR, a counterfactual disparity learning model for explicit multimodal EHR analytics. The core idea is to first model the contamination in representations, and subsequently perform calibration and enhancement to construct highly discriminative representations. Specifically, CLEAR first proposes the Counterfactual Prompt Learning Module to capture the representation discrepancy to model representation contamination. Subsequently, an Adaptive Dynamic Imputation Module is devised to decouple the elementwise representations for representation calibration, while a gating mechanism is further proposed to incorporate discriminative discrepancy information for representation enhancement. Finally, the Multimodal Representation Fusion Module establishes intra- and inter-modality correlations, thereby creating a seamless integration towards downstream analytic tasks. To our knowledge, CLEAR is the first to model and resolve representation contamination in multimodal EHR analytics. Experimental results on two real-world datasets demonstrate that CLEAR consistently outperforms state-of-the-art baselines in facilitating multimodal healthcare analytics.

Portrait animation aims to transfer the facial expressions and movements of a target character onto a reference character. This task presents two main challenges: accurately transferring motion and expressions while fully preserving the identity features of the reference portrait. We introduce Vividportraits, a diffusion-based model designed to effectively meet these objectives. In contrast to existing methods that rely on sparse representations such as facial landmarks, our approach leverages facial parsing maps for motion guidance, enabling a more precise conveyance of subtle expressions. A random scaling technique is applied during training to prevent the model from internalizing identity-specific features from the driving images. Furthermore, we perform foreground-background segmentation on the reference portrait to reduce data redundancy. The long-video generation process is refined to improve consistency across sequences. Our model, exclusively trained on public datasets, demonstrates superior performance relative to current state-of-the-art methods, achieving a notable 8% improvement in expression metric. More visual results are available on the anonymous website https://www.vividportraits.cn.

Sequence distance computation is a critical and fundamental task in many fields, such as bioinformatics, and time series analysis. Traditional functions for computing the distance between sequences are often based on dynamic programming to find a globally optimal alignment, which has quadratic complexity and is difficult to parallelize, thus limiting their application in large-scale datasets with long sequences. To solve this problem, various fields have designed some specialized models to approximate these distance functions inspired by deep representation learning, i.e., projecting the sequence into a geometric embedding space through an embedding function, so that the distance between sequences can be approximated by the distance in the high-dimensional embedding space, thereby reducing the quadratic complexity to linear. However, we note that even though the element types in sequence and distance functions are different across various fields, the core problem that needs to be solved remains the same. In this paper, we attempt to unify the sequence distance computation approximation from various fields and propose GnesDA. Specifically, we first unify the input representation of sequences in which the element type is the symbol and numeric values. We then encode the sequence using a convolutional block and a Transformer block sequentially, which can effectively capture local patterns and long dependencies respectively. Extensive experiments on four distance functions as well as four large-scale real-world datasets demonstrate that GnesDA achieves state-of-the-art in terms of both versatility and effectiveness. For the task of similarity retrieval, GnesDA can improve the edit distance, NW distance, DTW, and EDR by an average of 10.55%, 6.67%, 4.51%, and 12.00% on all metrics.

The missing values widely existed in tabular data hinder the effective analysis of algorithmic fairness. Existing fairness intervention algorithms incorporate constraints or regularizers to reduce discrimination which rely on the complete information. They cannot effectively handle common tabular data with missing values in both sensitive and non-sensitive attributes without imputation. In this paper, we propose a novel Transformer-based fairness-aware prediction model FATE that mitigates the bias introduced by missing values to achieve algorithmic fairness without imputation. FATE consists of two modules, i.e., an incomplete data encoding (IDE) module and a debiased representation learning (DRL) module. IDE designs an incomplete tabular data embedding strategy and a missingness-aware Transformer block to effectively learn the observed data distribution and the missing state information. DRL converts fairness into attention parity when the sensitive attributes are completely missing. It offers a debiased attention mechanism to normalize attention weights in the attention score calculation process. We theoretically prove that, the differences in attention scores can represent the demographic disparities among sensitive groups which in FATE are bounded by a constant, substantially minimizing the group discrimination. Extensive experiments on three public real-world datasets demonstrate that, FATE, with the competitive fairness, yields more than 22% accuracy gain, compared to the state of the arts.

Snapshot technology is crucial for data protection and system recovery in virtualized environments, particularly with the growing need for continuous snapshots to maintain the integrity of long-running web-based and distributed applications. However, traditional snapshot methods often suffer from performance bottlenecks, and inefficient storage usage. These challenges are closely tied to the way memory pages are accessed during VM execution, where memory access patterns show significant disparities between frequently accessed "hot" pages and less-used "cold" pages. In this paper, we introduce HeatSnap, a continuous snapshot system designed to address these issues by leveraging the uneven access frequencies of memory pages. HeatSnap distinguishes between intensive hot pages and dirty pages, applying specialized snapshotting and storage strategies to optimize the handling of both hot and cold memory regions. This approach aims to optimize snapshot efficiency, minimize performance impact on the VM, and decrease storage costs. Our implementation of HeatSnap on QEMU/KVM demonstrates significant improvements in VM performance loss, snapshot duration, and storage efficiency compared to existing methods, as evidenced by evaluations on common web and cloud-based workloads.

As a dominant paradigm in modern web applications, cloud computing has seen a surge in adoption. The deployment of vast and various workloads encapsulated within containers has become ubiquitous across cloud platforms, imposing substantial demands on the supporting infrastructure. However, Kubernetes (k8s), the de facto standard for container orchestration, struggles with low scheduling throughput and high latency in large-scale clusters. The primary challenges are identified as excessive load from read requests and resource contention between co-located components. In this paper, we present MerKury, a general and lightweight framework designed to enhance the Kubernetes performance for large-scale clusters. MerKury employs a dual strategy: first, it preprocesses specific requests to alleviate excessive load; second, it introduces an adaptive resource allocation algorithm to mitigate resource contention. Evaluations across various cluster scales demonstrate that MerKury notably augments node capacity by up to 4.5×, increases scheduling throughput by up to 7.3×, and reduces request latency by 5.6%-57.7%, outperforming vanilla Kubernetes and baseline resource allocation methods.

Hybrid storage solutions have emerged as potent strategies to alleviate the data storage bottlenecks prevalent in blockchain systems. These solutions harness off-chain Storage Services Providers (SP) in conjunction with Authenticated Data Structures (ADS) to ensure data integrity and accuracy. Despite these advancements, the reliance on centralized SPs raises concerns about query correctness, as the integrity of query results depends on the SPs' trustworthiness. Although ADS can verify the integrity of individual data points, they fall short of preventing SPs from omitting valid results. In this paper, we delineate the fundamental distinctions between data retrieval in blockchains and traditional database systems. Drawing upon these insights, we introduce the BPI framework, which employs a suite of validation models that ascertain the inclusion of all valid content in retrieval outcomes, with low overhead. We further present ''Articulated Search'', a query pattern specifically tailored for blockchain environments, which not only enhances retrieval efficiency but also substantially reduces costs during data user updates. Extensive experimental evaluations demonstrate that the BPI framework achieves outstanding scalability and performance in keyword searches within blockchain environments, surpassing EthMB+ and state-of-the-art search databases commonly used in mainstream hybrid storage blockchains (HSB). Notably, the Articulated Search pattern improves query performance by over three orders of magnitude, highlighting its potential as a transformative approach to blockchain query optimization.

Tabular data is abundant and crucial across both industry and academia. Federated learning (FL) offers a promising solution for the analysis of tabular data distributed across multiple organizations, without the need to share the privacy information of each client. Existing federated tabular data prediction methods optimize performance and privacy leakage under the completeness assumption of tabular data. They are not applicable in real-world scenarios that are struggling with missing values in tabular data. In this paper, we propose a novel federated prediction framework for incomplete tabular data, named DARN, which leverages the missing complementarity to directly optimize prediction performance without relying on the imputed values. It is especially beneficial when clients exhibit heterogeneity in missing data distributions, and the pairwise observed data are complementary. Specifically, each client trains a missing distribution learning model to capture the distribution of locally incomplete data. To assist in this, we present a missing-aware transformer block with a novel missing-aware attention mechanism to represent incomplete tabular data directly. The server calculates the personalized weights of the prediction models by combining missing complementary score and observed sample size score , thereby maximizing the utility of the available data. Extensive experiments on four publicly available real-world datasets demonstrate that DARN outperforms state-of-the-art methods with 25.80% improvement in both classification and regression tasks.

With the growing privacy concerns in recommender systems, recommendation unlearning is getting increasing attention. Existing studies predominantly use training data, i.e., model inputs, as unlearning target. However, attackers can extract private information from the model even if it has not been explicitly encountered during training. We name this unseen information as attribute and treat it as unlearning target. To protect the sensitive attribute of users, Attribute Unlearning (AU) aims to make target attributes indistinguishable. In this article, we focus on a strict but practical setting of AU, namely Post-Training Attribute Unlearning (PoT-AU), where unlearning can only be performed after the training of the recommendation model is completed. To address the PoT-AU problem in recommender systems, we propose a two-component loss function. The first component is distinguishability loss, where we design a distribution-based measurement to make attribute labels indistinguishable from attackers. We further extend this measurement to handle multi-class attribute cases with efficient computational overhead. The second component is regularization loss, where we explore a function-space measurement that effectively maintains recommendation performance compared to parameter-space regularization. We use stochastic gradient descent algorithm to optimize our proposed loss. Extensive experiments on four real-world datasets demonstrate the effectiveness of our proposed methods.

Federated Recommendation (FedRec) has been widely applied recently for realizing privacy preservation in recommender systems. However, due to direct uploads of model gradients from all clients, FedRec is vulnerable to potential poisoning attacks. In this article, we focus on the targeted model poisoning attacks in FedRec, which aims to raise the exposure ratio of specific target items by generating poisoned gradients to influence global training. Challenges emerge when implementing this kind of attack. On the one hand, simulating authentic users on the malicious clients for downstream poisoning is hard when access to prior knowledge is limited. On the other hand, distinguished item attributes and personalized user preferences require the attack to be adaptive to complex distributions. To this end, we propose a novel attack DuAda with two modules, i.e., dummy user simulator and adaptive distribution attacker . The dummy user simulator is designed to generate malicious users with characteristics similar to real users, which exploits authentic user representations and preference labels simultaneously through two-stage inversion optimization. The attacker first extracts heterogeneous distributions by a special multi-prototype clustering method, and then conducts adaptive attacks from both explicit and implicit promotion perspectives. The explicit promotion raises the prediction scores of target items based on the inherent characteristics, while the implicit promotion imbues them with the features of popular items. Targeted at our proposed attack method, we also design a merged adaptive defense mechanism to fight against DuAda and conduct defensive experiments. Empirical studies on four real-world datasets demonstrate the effectiveness and interpretability of DuAda.

Online data marketplaces emerge in diverse data-driven applications, where dynamically arriving consumers pur-chase the data at posted prices. The data value decays over time in many tasks, such as machine learning predictions and realtime systems. Existing query pricing methods do not consider the time-discounting data value. In this paper, we study the query feature-based data pricing problem with unknown time-discounting data valuation. We propose an effective online data pricing mechanism Pride to maximize the cumulative sales revenue. It leverages the powerful property of the ellipsoid method to efficiently solve online optimization via exploration and exploitation. Based on Thompson sampling, we present a novel non-stationary MAB algorithm Biased-TS to determine a suitable discount factor and attain the dynamic posted price. It is theoretically proved that, the regret upper bound order of Pride is dominated by the discretization error$O(\frac{T}{k})$, where$K$and$T$are the numbers of discount candidates and total trading rounds, respectively. Biased-TS gets a sub-linear regret upper bound$O(K^{3}\sqrt{T\ln T}+K\exp\{4\sqrt{\ln T}\})$. Extensive experiments using both synthetic and real datasets demonstrate that Pride yields around 90% of the optimal cumulative revenue, and it substantially outperforms the state-of-the-art methods.

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

The dramatically increasing volume of incomplete data makes the imputation models computationally infeasible in many real-life applications. In this paper, we propose an effective scalable imputation system named SCIS to significantly speed up the training of the differentiable generative adversarial imputation models under accuracy-guarantees for large-scale incomplete data. SCIS consists of two modules, differentiable imputation modeling (DIM) and sample size estimation (SSE). DIM leverages a new masking Sinkhorn divergence function to make an arbitrary generative adversarial imputation model differentiable, while for such a differentiable imputation model, SSE can estimate an appropriate sample size to ensure the user-specified imputation accuracy of the final model. Moreover, SCIS can also accelerate the autoencoder based imputation models. Extensive experiments upon several real-life large-scale datasets demonstrate that, our proposed system can accelerate the generative adversarial model training by 6.23x. Using around 1.27% samples, SCIS yields competitive accuracy with the state-of-the-art imputation methods in much shorter computation time.

Recommendation is a key mechanism for modern users to access items of their interests from massive entities and information. Recently, graph contrastive learning (GCL) has demonstrated satisfactory results on recommendation, due to its ability to enhance representation by integrating graph neural networks (GNNs) with contrastive learning. However, those methods often generate contrastive views by performing random perturbation on edges or embeddings, which is likely to bring noise in representation learning. Besides, in all these methods, the degree of user preference on items is omitted during the representation learning process, which may cause incomplete user/item modeling. To address these limitations, we propose the Adaptive Fusion of Multi-View Graph Contrastive Recommendation (AMGCR) model. Specifically, to generate the informative and less noisy views for better contrastive learning, we design four view generators to learn the edge weights focusing on weight adjustment, feature transformation, neighbor aggregation, and attention mechanism, respectively. Then, we employ an adaptive multi-view fusion module to combine different views from both the view-shared and the view-specific levels. Moreover, to make the model capable of capturing preference information during the learning process, we further adopt a preference refinement strategy on the fused contrastive view. Experimental results on three real-world datasets demonstrate that AMGCR consistently outperforms the state-of-the-art methods, with average improvements of over 10% in terms of Recall and NDCG. Our code is available on https://github.com/Du-danger/AMGCR.

Data quality is paramount in today's data-driven world, especially in the era of generative AI. Dirty data with errors and inconsistencies usually leads to flawed insights, unreliable decision-making, and biased or low-quality outputs from generative models. The study of repairing erroneous data has gained significant importance. Existing data repair algorithms differ in information utilization, problem settings, and are tested in limited scenarios. In this paper, we compare and summarize these algorithms with a driven information-based taxonomy. We systematically conduct a comprehensive evaluation of 12 mainstream data repair algorithms on 12 datasets under the settings of various data error rates, error types, and 4 downstream analysis tasks, assessing their error reduction performance with a novel but practical metric. We develop an effective and unified repair optimization strategy that substantially benefits the state of the arts. We conclude that, it is always worthy of data repair. The clean data does not determine the upper bound of data analysis performance. We provide valuable guidelines, challenges, and promising directions in the data repair domain. We anticipate this paper enabling researchers and users to well understand and deploy data repair algorithms in practice.

The multi-view data with incomplete information hinder effective data analysis. Existing multi-view imputation methods, which learn the mapping between a complete view and acompletely missingview, are not able to deal with the typical multi-view data withmissing featureinformation. In this paper, we propose a unified generative imputation model named UGit with optimal transport theory to simultaneously impute the missing features/values of all incomplete views. This imputation is conditional onallthe observed values from the multi-view data. UGit consists of two modules, i.e., aunified multi-view generator(UMG) and amasking energy discriminator(MED). To effectively and efficiently impute missing features across all views, the generator UMG employs aunified autoencoderin conjunction with thecross-view attention mechanismto learn the data distribution from all observed multi-view data. The discriminator MED leverages a novelmasking energydivergence function to make UGit differentiable for imputation accuracy enhancement. Extensive experiments on several real-world multi-view data sets demonstrate that, UGit speeds up the model training by 4.28x with more than 41% accuracy gain on average, compared to the state-of-the-art approaches.

Data imputation has been extensively explored to solve the missing data problem. The dramatically increasing volume of incomplete data makes the imputation models computationally infeasible in many real-life applications. In this paper, we propose an effective scalable imputation system named SCIS to significantly speed up the training of the differentiable generative adversarial imputation models under accuracy-guarantees for large-scale incomplete data. SCIS consists of two modules,differentiable imputation modeling(DIM) andsample size estimation(SSE). DIM leverages a newmasking Sinkhorndivergence function to make an arbitrary generative adversarial imputation model differentiable, while for such a differentiable imputation model, SSE can estimate an appropriate sample size to ensure the user-specified imputation accuracy of the final model. Moreover, SCIS can also accelerate the autoencoder based imputation models. Extensive experiments upon several real-life large-scale datasets demonstrate that, our proposed system can accelerate the generative adversarial model training by 6.23x. Using around 1.27% samples, SCIS yields competitive accuracy with the state-of-the-art imputation methods in much shorter computation time.

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

The dramatically increasing volume of incomplete data makes the imputation models computationally infeasible in many real-life applications. In this demonstration, we propose a scalable and extendible data imputation toolbox, SEMI, to deal with large-scale incomplete data imputation efficiently and visually. SEMI consists of three modules: data preprocessing, data imputation, and post-imputation prediction. It is built upon SCIS, a scalable imputation system, to significantly speed up the training of generative adversarial imputation models under accuracy-guarantees for large-scale incomplete data. Using a public real-world large-scale incomplete weather dataset, we demonstrate that, SEMI is capable of assisting users to efficiently address real-life large-scale imputation issues, from the aspects of high-efficient imputation system, user-friendly performance visualization, and easy-to-use interaction operation.

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

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

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

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

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

Deep Neural Networks (DNNs) have achieved remarkable progress in various real-world applications, especially when abundant training data are provided. However, data isolation has become a serious problem currently. Existing works build privacy-preserving DNN models from either algorithmic perspective or cryptographic perspective. The former mainly splits the DNN computation graph between data holders or between data holders and server, which demonstrates good scalability but suffers from accuracy loss and potential privacy risks. In contrast, the latter leverages time-consuming cryptographic techniques, which has strong privacy guarantee but poor scalability. In this article, we propose SPNN—a Scalable and Privacy-preserving deep Neural Network learning framework, from an algorithmic-cryptographic co-perspective. From algorithmic perspective, we split the computation graph of DNN models into two parts, i.e., the private-data-related computations that are performed by data holders and the rest heavy computations that are delegated to a semi-honest server with high computation ability. From cryptographic perspective, we propose using two types of cryptographic techniques, i.e., secret sharing and homomorphic encryption, for the isolated data holders to conduct private-data-related computations privately and cooperatively. Furthermore, we implement SPNN in a decentralized setting and introduce user-friendly APIs. Experimental results conducted on real-world datasets demonstrate the superiority of our proposed SPNN.

Graph classification problem is becoming one of research hotspots in the realm of graph mining, which has been widely used in cheminformatics, bioinformatics and social network analytics. Existing approaches, such as graph kernel methods and graph Convolutional Neural Network, are facing the challenges of non-interpretability and high dimensionality. To address the problems, we propose a novel recurrent attention model, called g-Inspector, which applies the attention mechanism to investigate the significance of each region to make the results interpretable. It also takes a shift operation to guide the inspector agent to discover the next relevant region, so that the model sequentially loads small regions instead of the entire large graph, to solve the high dimensionality problem. The experiments conducted on standard graph datasets show the effectiveness of our g-Inspector in graph classification problems.

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

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

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

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

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

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

Parkinson’s disease is a progressive nervous system disorder afflicting millions of patients. Among its motor symptoms, bradykinesia is one of the cardinal manifestations. Experienced doctors are required for the clinical diagnosis of bradykinesia, but sometimes they also miss subtle changes, especially in early stages of such disease. Therefore, developing auxiliary diagnostic methods that can automatically detect bradykinesia has received more and more attention. In this article, we employ a two-stage framework for bradykinesia recognition based on the video of patient movement. First, convolution neural networks are trained to localize keypoints in each video frame. These time-varying coordinates form motion trajectories that represent the whole movement. From the trajectory, we then propose novel measurements, namely stability , completeness , and self-similarity , to quantify different motor behaviors. We also propose a periodic motion model called PMNet . An encoder--decoder structure is applied to learn a low dimensional representation of a motion process. The compressed motion process and quantified motor behaviors are combined as inputs to a fully-connected neural network. Different from the traditional means, our solution extends the application scenario outside the hospital and can be easily transplanted to conduct similar tasks. A commonly used clinical assessment is served as a case study. Experimental results based on real-world data validate the effectiveness of our approach for bradykinesia recognition.

App usage prediction, i.e. which apps will be used next, is very useful for smartphone system optimization, such as operating system resource management, battery energy consumption optimization, and user experience improvement as well. However, it is still challenging to achieve usage prediction of high accuracy. In this paper, we propose a novel framework for app usage prediction, called AppUsage2Vec, inspired by Doc2Vec. It models app usage records by considering the contribution of different apps, user personalized characteristics, and temporal context. We measure the contribution of each app to the target app by introducing an app-attention mechanism. The user personalized characteristics in app usage are learned by a module of dual-DNN. Furthermore, we encode the top-k supervised information in loss function for training the model to predict the app most likely to be used next. The AppUsage2Vec was evaluated on a dataset of 10,360 users and 46,434,380 records in three months. The results demonstrate the state-of-the-art performance.

As more business workflow systems are being deployed in modern enterprises and organizations, more employee-activity log data are being collected and analyzed. In this paper, we develop a latent ability model (LAM) as a generative probabilistic learning framework for workforce analytics over employee-activity logs. The LAM development is novel in three aspects. First, we introduce the concept of latent ability variables to model hidden relations between employees and activities in terms of job performance, such as the set of skills provided by an employee and the set of skills required by an activity, and how well they matchup in employee-activity assignment. Second, we construct the latent ability model by learning latent ability parameters from the employee-activity log data using expectation-maximization and gradient descent. Finally, we leverage LAM to build inference and prediction models for employee performance prediction, employee ability comparison, and employee-activity matchup quality estimation. We evaluate the accuracy and efficiency of our approach using real log datasets collected from a workflow system deployed in the government of the city of Hangzhou, China, which consists of 5,287,621 log records over two years involving 744 activities and 1,725 employees. We show that LAM approach outperforms existing representative methods in both accuracy and efficiency.

NgramCNN is a deep convolutional neural network developed for classification of graphs based on common substructure patterns and their latent relationships in the collection of graphs. Our NgramCNN deep learning framework consists of three novel components: (1) The concept of n-gram graph block to transform each raw graph object into a sequence of n-gram blocks connected through overlapping regions. (2) The diagonal convolution layer to extract local patterns and connectivity features hidden in the n-gram blocks by performing n-gram normalization before conducting deep learning through the network of convolution layers. (3) The extraction of deeper global patterns based on the local patterns and the ways that they respond to overlapping regions by building a n-gram deep convolutional neural network. Extensive evaluation of NgramCNN using five real graph repositories from bioinformatics and social networks domains show the effectiveness of NgramCNN over the existing state of art methods with high accuracy and comparable performance.

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

Convolutional Neural Network (CNN) has gained attractions in image analytics and speech recognition in recent years. However, employing CNN for classification of graphs remains to be challenging. This paper presents the Ngram graph-block based convolutional neural network model for classification of graphs. Our Ngram deep learning framework consists of three novel components. First, we introduce the concept of n-gram block to transform each raw graph object into a sequence of n-gram blocks connected through overlapping regions. Second, we introduce a diagonal convolution step to extract local patterns and connectivity features hidden in these n-gram blocks by performing n-gram normalization. Finally, we develop deeper global patterns based on the local patterns and the ways that they respond to overlapping regions by building a n-gram deep learning model using convolutional neural network. We evaluate the effectiveness of our approach by comparing it with the existing state of art methods using five real graph repositories from bioinformatics and social networks domains. Our results show that the Ngram approach outperforms existing methods with high accuracy and comparable performance.

How to improve the modeling efficiency and accuracy has become a burning problem. The popularization of recommendation technique in E-Commerce provide us new trajectories that can be used for addressing the problem. In this paper, we propose a graph-based workflow recommendation for improving business process modeling. The start point is so-called "workflow repository" including a set of already developed process models. Graph mining method is used to extract the process patterns from the repository. Based on graph edit distance (GED) [2], we calculate the distance between patterns and the partial business process, viewed as reference model, which is under modeling and select the candidate nodes with smaller distances for recommendation. The performance study show its feasibility for practical uses.