File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

postgraduate thesis: Managing query quality in probabilistic databases

TitleManaging query quality in probabilistic databases
Authors
Advisors
Issue Date2011
PublisherThe University of Hong Kong (Pokfulam, Hong Kong)
Citation
Li, X. [李想]. (2011). Managing query quality in probabilistic databases. (Thesis). University of Hong Kong, Pokfulam, Hong Kong SAR. Retrieved from http://dx.doi.org/10.5353/th_b4775313
AbstractIn many emerging applications, such as sensor networks, location-based services, and data integration, the database is inherently uncertain. To handle a large amount of uncertain data, probabilistic databases have been recently proposed, where probabilistic queries are enabled to provide answers with statistical guarantees. In this thesis, we study the important issues of managing the quality of a probabilistic database. We first address the problem of measuring the ambiguity, or quality, of a probabilistic query. This is accomplished by computing the PWS-quality score, a recently proposed measure for quantifying the ambiguity of query answers under the possible world semantics. We study the computation of the PWS-quality for the top-k query. This problem is not trivial, since directly computing the top-k query score is computationally expensive. To tackle this challenge, we propose efficient approximate algorithms for deriving the quality score of a top-k query. We have performed experiments on both synthetic and real data to validate their performance and accuracy. Our second contribution is to study how to use the PWS-quality score to coordinate the process of cleaning uncertain data. Removing ambiguous data from a probabilistic database can often give us a higher-quality query result. However, this operation requires some external knowledge (e.g., an updated value from a sensor source), and is thus not without cost. It is important to choose the correct object to clean, in order to (1) achieve a high quality gain, and (2) incur a low cleaning cost. In this thesis, we examine different cleaning methods for a probabilistic top-k query. We also study an interesting problem where different query users have their own budgets available for cleaning. We demonstrate how an optimal solution, in terms of the lowest cleaning costs, can be achieved, for probabilistic range and maximum queries. An extensive evaluation reveals that these solutions are highly efficient and accurate.
DegreeMaster of Philosophy
SubjectDatabases.
Probabilistic number theory.
Query languages (Computer science)
Dept/ProgramComputer Science

 

DC FieldValueLanguage
dc.contributor.advisorCheng, CK-
dc.contributor.advisorCheung, DWL-
dc.contributor.authorLi, Xiang-
dc.contributor.author李想-
dc.date.issued2011-
dc.identifier.citationLi, X. [李想]. (2011). Managing query quality in probabilistic databases. (Thesis). University of Hong Kong, Pokfulam, Hong Kong SAR. Retrieved from http://dx.doi.org/10.5353/th_b4775313-
dc.description.abstractIn many emerging applications, such as sensor networks, location-based services, and data integration, the database is inherently uncertain. To handle a large amount of uncertain data, probabilistic databases have been recently proposed, where probabilistic queries are enabled to provide answers with statistical guarantees. In this thesis, we study the important issues of managing the quality of a probabilistic database. We first address the problem of measuring the ambiguity, or quality, of a probabilistic query. This is accomplished by computing the PWS-quality score, a recently proposed measure for quantifying the ambiguity of query answers under the possible world semantics. We study the computation of the PWS-quality for the top-k query. This problem is not trivial, since directly computing the top-k query score is computationally expensive. To tackle this challenge, we propose efficient approximate algorithms for deriving the quality score of a top-k query. We have performed experiments on both synthetic and real data to validate their performance and accuracy. Our second contribution is to study how to use the PWS-quality score to coordinate the process of cleaning uncertain data. Removing ambiguous data from a probabilistic database can often give us a higher-quality query result. However, this operation requires some external knowledge (e.g., an updated value from a sensor source), and is thus not without cost. It is important to choose the correct object to clean, in order to (1) achieve a high quality gain, and (2) incur a low cleaning cost. In this thesis, we examine different cleaning methods for a probabilistic top-k query. We also study an interesting problem where different query users have their own budgets available for cleaning. We demonstrate how an optimal solution, in terms of the lowest cleaning costs, can be achieved, for probabilistic range and maximum queries. An extensive evaluation reveals that these solutions are highly efficient and accurate.-
dc.languageeng-
dc.publisherThe University of Hong Kong (Pokfulam, Hong Kong)-
dc.relation.ispartofHKU Theses Online (HKUTO)-
dc.rightsThe author retains all proprietary rights, (such as patent rights) and the right to use in future works.-
dc.rightsCreative Commons: Attribution 3.0 Hong Kong License-
dc.source.urihttp://hub.hku.hk/bib/B47753134-
dc.subject.lcshDatabases.-
dc.subject.lcshProbabilistic number theory.-
dc.subject.lcshQuery languages (Computer science)-
dc.titleManaging query quality in probabilistic databases-
dc.typePG_Thesis-
dc.identifier.hkulb4775313-
dc.description.thesisnameMaster of Philosophy-
dc.description.thesislevelMaster-
dc.description.thesisdisciplineComputer Science-
dc.description.naturepublished_or_final_version-
dc.identifier.doi10.5353/th_b4775313-
dc.date.hkucongregation2012-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats