A Survey on Truth Discovery <s> Source selection <s> Data integration systems offer users a uniform interface to a set of data sources. Previous work has typically assumed that the data sources are independent of each other; however, in scenarios involving large numbers of sources, such as the Web or large enterprises, there is an eco-system of dependent sources, where some sources copy parts of their data from others. This paper considers the new optimization problems that arise while answering queries over large number of dependent sources. These are the (1) cost-minimization problem: what is the minimum cost we must incur to get all answer tuples, (2) maximum-coverage problem: given a bound on the cost, how can we get the maximum possible coverage, and (3) the source-ordering problem: for a set of data sources, what is the best order to query them so as to retrieve answer tuples as fast as possible. We consider these optimization problems under several cost models and we show that, in general, they are intractable. We describe effective approximation algorithms that enable us to solve these problems in practice. We then identify the causes of the high complexity and show that for restricted classes, the optimization problems can be solved in polynomial time. <s> BIB001 </s> A Survey on Truth Discovery <s> Source selection <s> We are often thrilled by the abundance of information surrounding us and wish to integrate data from as many sources as possible. However, understanding, analyzing, and using these data are often hard. Too much data can introduce a huge integration cost, such as expenses for purchasing data and resources for integration and cleaning. Furthermore, including low-quality data can even deteriorate the quality of integration results instead of bringing the desired quality gain. Thus, "the more the better" does not always hold for data integration and often "less is more". ::: ::: In this paper, we study how to select a subset of sources before integration such that we can balance the quality of integrated data and integration cost. Inspired by the Marginalism principle in economic theory, we wish to integrate a new source only if its marginal gain, often a function of improved integration quality, is higher than the marginal cost, associated with data-purchase expense and integration resources. As a first step towards this goal, we focus on data fusion tasks, where the goal is to resolve conflicts from different sources. We propose a randomized solution for selecting sources for fusion and show empirically its effectiveness and scalability on both real-world data and synthetic data. <s> BIB002 </s> A Survey on Truth Discovery <s> Source selection <s> Data integration is a challenging task due to the large numbers of autonomous data sources. This necessitates the development of techniques to reason about the benefits and costs of acquiring and integrating data. Recently the problem of source selection (i.e., identifying the subset of sources that maximizes the profit from integration) was introduced as a preprocessing step before the actual integration. The problem was studied for static sources and used the accuracy of data fusion to quantify the integration profit. In this paper, we study the problem of source selection considering dynamic data sources whose content changes over time. We define a set of time-dependent metrics, including coverage, freshness and accuracy, to characterize the quality of integrated data. We show how statistical models for the evolution of sources can be used to estimate these metrics. While source selection is NP-complete, we show that for a large class of practical cases, near-optimal solutions can be found, propose an algorithmic framework with theoretical guarantees for our problem and show its effectiveness with an extensive experimental evaluation on both real-world and synthetic data. <s> BIB003 </s> A Survey on Truth Discovery <s> Source selection <s> Worker reliability is a longstanding issue in crowdsourcing, and the automatic discovery of high quality workers is an important practical problem. Most previous work on this problem mainly focuses on estimating the quality of each individual worker jointly with the true answer of each task. However, in practice, for some tasks, worker quality could be associated with some explicit characteristics of the worker, such as education level, major and age. So the following question arises: how do we automatically discover related worker attributes for a given task, and further utilize the findings to improve data quality? In this paper, we propose a general crowd targeting framework that can automatically discover, for a given task, if any group of workers based on their attributes have higher quality on average; and target such groups, if they exist, for future work on the same task. Our crowd targeting framework is complementary to traditional worker quality estimation approaches. Furthermore, an advantage of our framework is that it is more budget efficient because we are able to target potentially good workers before they actually do the task. Experiments on real datasets show that the accuracy of final prediction can be improved significantly for the same budget (or even less budget in some cases). Our framework can be applied to many real word tasks and can be easily integrated in current crowdsourcing platforms. <s> BIB004
We often expect better performance of truth discovery when more data sources are involved in. However, nothing comes for free in practice -both economic and computational costs should be taken into consideration when applying truth discovery. Moreover, BIB002 shows that the incorporation of bad sources may even hurt the performance of truth discovery. In order to solve these problems, BIB002 BIB003 BIB001 provide methods to wisely select sources for truth discovery constrained by the cost and output quality. In BIB001 , the authors propose a method to select sources under different cost constraints, in which the task is formulated as an optimization problem. Their Integrating Dependent Sources (IDS) system can return an optimal subset of sources to query, and the selection guarantees that the cost constraints are satisfied. The greedy and randomized approximation algorithms proposed for this problem run in polynomial time with provable quality guarantees. In BIB002 , source selection is performed on static data sources. The authors first provide a dynamic programming algorithm to infer the accuracy of integrating any arbitrary subset of sources. Then a randomized greedy algorithm is adopted to select the optimal subset of sources by incorporating a source in integration only if the gain of accuracy exceeds the corresponding cost. While in BIB003 , source selection is performed on dynamic data sources whose contents are updated over time. A greedy algorithm is developed to output near-optimal source selection and the optimal frequencies to acquire sources for update-to-date information. More interestingly, BIB004 claims that a source is useless only when it guesses answers randomly. Even very bad sources can make positive contributions if truth discovery approach assigns negative weights to them. In other words, if a bad source provides a piece of information, we can infer that this information might be wrong with high probability.