ERA

Download the full-sized PDF of Top-k ranking with uncertain dataDownload the full-sized PDF

Analytics

Share

Permanent link (DOI): https://doi.org/10.7939/R3KS36

Download

Export to: EndNote  |  Zotero  |  Mendeley

Communities

This file is in the following communities:

Graduate Studies and Research, Faculty of

Collections

This file is in the following collections:

Theses and Dissertations

Top-k ranking with uncertain data Open Access

Descriptions

Other title
Subject/Keyword
Pruning
Uncertainty
Top-k Ranking
Type of item
Thesis
Degree grantor
University of Alberta
Author or creator
Wang, Chonghai
Supervisor and department
You, Jia (Computing Science)
Yuan, Li-Yan (Computing Science)
Examining committee member and department
Chen, Xi (Mathematical and Statistical Sciences)
Zaiane, Osmar (Computing Science)
Lin, Xuemin (School of Computer Science and Engineering,University of New South Wales)
Sander,Joerg (Computing Science)
Department
Department of Computing Science
Specialization

Date accepted
2011-04-08T19:16:50Z
Graduation date
2011-06
Degree
Doctor of Philosophy
Degree level
Doctoral
Abstract
The goal of top-k ranking is to rank individuals so that the best k of them can be determined. Depending on the application domain, an individual can be a person, a product, an event, or just a collection of data or information for which an ordering makes sense. In the context of databases, top-k ranking has been studied in two distinct directions, depending on whether the stored information is certain or uncertain. In the former, the past research has focused on efficient query processing. In the latter case, a number of semantics based on possible worlds have been proposed and computational mechanisms investigated for what are called uncertain databases or probabilistic databases, where a tuple is associated with a membership probability indicating the level of confidence on the stored information. In this thesis, we study top-k ranking with uncertain data in two general areas. The first is on pruning for the computation of top-k tuples in a probabilistic database. We investigate the theoretical basis and practical means of pruning for the recently proposed, unifying framework based on parameterized ranking functions. As such, our results are applicable to a wide range of ranking functions. We show experimentally that pruning can generate orders of magnitude performance gains. In the second area of our investigation, we study the problem of top-k ranking for objects with multiple attributes whose values are modeled by probability distributions and constraints. We formulate a theory of top-k ranking for objects by a characterization of what constitutes the strength of an object, and show that a number of previous proposals for top-k ranking are special cases of our theory. We carry out a limited study on computation of top-k objects under our theory. We reveal the close connection between top-k ranking in this context and high-dimensional space studied in mathematics, in particular, the problem of computing the volumes of high-dimensional polyhedra expressed by linear inequations is a special case of top-k ranking of objects, and as such, the algorithms formulated for the former can be employed for the latter under the same conditions.
Language
English
DOI
doi:10.7939/R3KS36
Rights
License granted by Chonghai Wang (chonghai@ualberta.ca) on 2011-04-07 (GMT): Permission is hereby granted to the University of Alberta Libraries to reproduce single copies of this thesis and to lend or sell such copies for private, scholarly or scientific research purposes only. Where the thesis is converted to, or otherwise made available in digital form, the University of Alberta will advise potential users of the thesis of the above terms. The author reserves all other publication and other rights in association with the copyright in the thesis, and except as herein provided, neither the thesis nor any substantial portion thereof may be printed or otherwise reproduced in any material form whatsoever without the author's prior written permission.
Citation for previous publication

File Details

Date Uploaded
Date Modified
2014-04-29T17:30:48.989+00:00
Audit Status
Audits have not yet been run on this file.
Characterization
File format: pdf (Portable Document Format)
Mime type: application/pdf
File size: 891765
Last modified: 2015:10:12 19:23:43-06:00
Filename: Wang_Chonghai_Spring 2011.pdf
Original checksum: 4925771313f6e49105a3f24642bed142
Well formed: true
Valid: true
Page count: 119
Activity of users you follow
User Activity Date