Probabilistic ranking techniques in relational databases
By: Ihab F. Ilyas, Mohamed A. Soliman
Contributors: Soliman, Mohamed A.
Series: Synthesis lectures on data management -- # 14
Publisher: Morgan & Claypool; Morgan & Claypool Publishers
Published: 2011
Place of publication: San Rafael, Calif. (1537 Fourth Street, San Rafael, CA 94901 USA)
Language: eng
Format: [electronic resource] /
Number of pages: 63
ISBN-13: 9781608455683; 9781608455676
Subjects: Ranking and selection (Statistics); Uncertainty (Information theory); Querying (Computer science)
Other titles: Synthesis digital library of engineering and computer science.
Description: Ranking queries are widely used in data exploration, data analysis and decision making scenarios. While most of the currently proposed ranking techniques focus on deterministic data, several emerging applications involve data that are imprecise or uncertain. Ranking uncertain data raises new challenges in query semantics and processing, making conventional methods inapplicable. Furthermore, the interplay between ranking and uncertainty models introduces new dimensions for ordering query results that do not exist in the traditional settings. This lecture describes new formulations and processing techniques for ranking queries on uncertain data. The formulations are based on marriage of traditional ranking semantics with possible worlds semantics under widely-adopted uncertainty models. In particular, we focus on discussing the impact of tuple-level and attribute-level uncertainty on the semantics and processing techniques of ranking queries. Under the tuple-level uncertainty model, we describe new processing techniques leveraging the capabilities of relational database systems to recognize and handle data uncertainty in score-based ranking. Under the attribute-level uncertainty model, we describe new probabilistic ranking models and a set of query evaluation algorithms, including sampling-based techniques. We also discuss supporting rank join queries on uncertain data, and we show how to extend current rank join methods to handle uncertainty in scoring attributes.
Notes: Part of: Synthesis digital library of engineering and computer science.

Series from website.

Includes bibliographical references (p. 59-62).

Abstract freely available; full-text restricted to subscribers or individual document purchasers.

Also available in print.

Mode of access: World Wide Web.

System requirements: Adobe Acrobat Reader.
Table of contents: title: 1. Introduction; title: Tuple level uncertainty; title: Attribute level uncertainty; title: Challenges; title: State-of-the-art; title: 2. Uncertainty models; title: Tuple uncertainty models; title: Attribute uncertainty models; title: Discrete uncertain scores; title: Continuous uncertain scores; title: 3. Query semantics; title: Mode-based semantics; title: Aggregation-based semantics; title: Applications; title: 4. Methodologies; title: Branch and bound search; title: UTop-prefix under Tuple uncertainty; title: UTop-prefix under attribute uncertainty; title: Monte-Carlo simulation; title: Computing UTop-rank query; title: Computing UTop-prefix and UTop-set queries; title: Dynamic programming; title: UTop-rank query under independence; title: Generating functions; title: Probabilistic threshold; title: Typical top-k answers; title: Other methodologies; title: Expected ranks; title: Uncertain rank aggregation; title: 5. Uncertain rank join; title: Uncertain rank join problem; title: Computing the top-k join results; title: Ranking the top-k join results; title: Join-aware sampling; title: Incremental ranking; title: 6. Conclusion; title: Bibliography; title: Authors' biographies.