Cleaning algorithms for novel applications

Abstract

The information managed in emerging applications, such as location-based service, sensor network, and crowdsourcing system, is usually imperfect. In many situations, data can be cleaned (e.g., removed or reduced) by performing appropriate operations. In this thesis, we study the cleaning problem under limited resources for two novel applications: querying probabilistic data, and collecting data from human intelligence tasks in crowdsourcing environments.

Probabilistic databases have been developed to handle uncertain data recently. For example, the temperature readings in a sensor network may be uncertain due to the lack of latest readings from sensors at every moment. A probabilistic database is able to capture the real value distributions of the readings, and enables evaluation of probabilistic queries on the data. However, data uncertainty may lead to ambiguous query results. By performing cleaning operations on the data, for example, probing some sensors for their latest readings, the ambiguity in query results can be reduced. In this thesis, we first study how to quantify the ambiguity of query results returned by a probabilistic top-k query. We develop efficient algorithms to compute the quality of this query under the possible world semantics. We further address the cleaning of a probabilistic database in order to improve top-k query quality. Specifically, we consider the facts that cleaning may involve a cost and fail. We propose optimal cleaning algorithms as well as several heuristics to select the data to clean under a limited budget.

In a crowdsourcing system, Human Intelligence Tasks (HITs) (e.g., translating sentences, matching photos, tagging videos with keywords) can be conveniently specified to collect data. HITs are made available to a large pool of workers, who are paid upon completing the HITs they have selected. Since workers may be casual Internet users, their answers are hardly perfect. If more workers are employed to perform a HIT, the quality of the HIT’s answer could be statistically improved. Hence, assigning the number of workers (or plurality) of each HIT is an effective way to reduce (or clean) the imperfectness of the collected data (i.e., HITs answers). In this thesis, we address the important problem of determining the plurality of each HIT so that the overall answer quality is optimized. We propose a dynamic programming (DP) algorithm for solving the plurality assignment problem (PAP). We identify two interesting properties, namely, monotonicity and diminishing return, which are satisfied by a HIT if the quality of the HIT’s answer increases monotonically at a decreasing rate with its plurality. We show for HITs that satisfy the two properties (e.g., multiple-choice-question HITs), the PAP is approximable. We propose an efficient greedy algorithm for such case.