Multi-view multi-label classification (MvMLC) is indispensable for modern web applications aggregating information from diverse sources. However, real-world web-scale settings are rife with missing views and continuously emerging classes, which pose significant obstacles to robust learning. Prevailing methods are ill-equipped for this reality, as they either lack adaptability to new classes or incur exponential parameter growth when handling all possible missing-view patterns, severely limiting their scalability in web environments. To systematically address this gap, we formally introduce a novel task, termed incomplete multi-view multi-label class incremental learning (IMvMLCIL), which requires models to simultaneously address heterogeneous missing views and dynamic class expansion. To tackle this task, we propose E2PL, an Effective and Efficient Prompt Learning framework for IMvMLCIL. E2PL unifies two novel prompt designs: task-tailored prompts for class-incremental adaptation and missing-aware prompts for the flexible integration of arbitrary view-missing scenarios. To fundamentally address the exponential parameter explosion inherent in missing-aware prompts, we devise an efficient prototype tensorization module, which leverages atomic tensor decomposition to elegantly reduce the prompt parameter complexity from exponential to linear w.r.t. the number of views. We further incorporate a dynamic contrastive learning strategy explicitly model the complex dependencies among diverse missing-view patterns, thus enhancing the model's robustness. Extensive experiments on three benchmarks demonstrate that E2PL consistently outperforms state-of-the-art methods in both effectiveness and efficiency. The codes and datasets are available at https://anonymous.4open.science/r/code-for-E2PL.

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.

Federated data selection strategically chooses a group of high-quality samples to train a global model, and it is promising to optimize the convergence and resource overhead of federated learning (FL). However, existing studies either fail to account for the dynamic importance of training samples or rely on external unbiased validation datasets. These shortcomings can compromise FL model performance, potentially complicating their application in real-world scenarios. In this paper, we propose a novel proxy-validated importance-aware federated sample selection framework, termed FedSelect. It employs a novel meta learning approach with a proxy validation dataset to select the most positively important clients and their most important samples, thereby accelerating the training process and optimizing FL model performance. To eliminate the dependency on external unbiased data, we present a momentum-based meta-margin function to discover influential samples as the proxy validation dataset, providing an adaptive reward for sample selection. Furthermore, we also develop an online meta model update strategy to guarantee the efficiency of FedSelect. Comprehensive experiments on four benchmark datasets demonstrate that FedSelect is superior in both effectiveness and efficiency, while maintaining strong scalability across diverse scenarios. The source code can be accessed at: https://github.com/nameyzhang/FedSelect.

Incomplete multi-view partial multi-label classification (IMvPMLC), which tackles the combined challenges of incompleteness in both multi-view and multi-label problems, has drawn considerable attention. Existing IMvPMLC methods have made progress but still face several challenges: (i) They mainly focus on the consistency of representations across multiple views but overlook the relationships among instances, leading to suboptimal representations. (ii) They primarily utilize only the available labels for supervised learning, ignoring the missing label distribution and limiting their ability to capture label correlations. In this paper, we propose a novel model named Dual Structure-guided Contrastive Network (DSCN) for IMvPMLC. Specifically, we introduce a similarity-guided instance-level contrastive learning mechanism to achieve multi-view consistent and discriminative representations across instances by leveraging instance structures, while a multi-view attention-based fusion strategy dynamically facilitates the fusion of multi-view representations to derive a robust consensus representation. Then, we design a multi-view shared classifier integrated with a correlation-guided label-level contrastive learning mechanism to enhance predictions by leveraging complementary information across multiple views and capturing label structures, effectively exploiting missing label distribution. Extensive experiments on five benchmark datasets demonstrate that, DSCN yields a more than 13% accuracy, compared with the state-of-the-art approaches. The code and datasets are available at https://anonymous.4open.science/r/DSCN-D471.

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.

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.

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.

Data quality is critical across many applications. The utility of data is undermined by various errors, making rigorous data cleaning a necessity. Traditional data cleaning systems depend heavily on predefined rules and constraints, which necessitate significant domain knowledge and manual effort. Moreover, while configuration-free approaches and deep learning methods have been explored, they struggle with complex error patterns, lacking interpretability, requiring extensive feature engineering or labeled data. This paper introduces GIDCL ( G raph-enhanced I nterpretable D ata C leaning with L arge language models), a pioneering framework that harnesses the capabilities of Large Language Models (LLMs) alongside Graph Neural Network (GNN) to address the challenges of traditional and machine learning-based data cleaning methods. By converting relational tables into graph structures, GIDCL utilizes GNN to effectively capture and leverage structural correlations among data, enhancing the model's ability to understand and rectify complex dependencies and errors. The framework's creator-critic workflow innovatively employs LLMs to automatically generate interpretable data cleaning rules and tailor feature engineering with minimal labeled data. This process includes the iterative refinement of error detection and correction models through few-shot learning, significantly reducing the need for extensive manual configuration. GIDCL not only improves the precision and efficiency of data cleaning but also enhances its interpretability, making it accessible and practical for non-expert users. Our extensive experiments demonstrate that GIDCL significantly outperforms existing methods, improving F1-scores by 10% on average while requiring only 20 labeled tuples.

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.

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

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

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

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.

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.

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

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

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

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

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

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

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

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

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

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