s970 burdick

50 %
50 %
Information about s970 burdick
Education

Published on February 5, 2008

Author: Stella

Source: authorstream.com

OLAP Over Uncertain and Imprecise Data:  OLAP Over Uncertain and Imprecise Data T.S. Jayram (IBM Almaden) with Doug Burdick (Wisconsin), Prasad Deshpande (IBM), Raghu Ramakrishnan (Wisconsin), Shivakumar Vaithyanathan (IBM) Dimensions in OLAP:  CA MA NY TX East West All Location Civic Sierra F150 Camry Truck Sedan All Automobile Dimensions in OLAP Measures, Facts, and Queries:  Auto = Truck Loc = East SUM(Repair) = ? Measures, Facts, and Queries MA NY TX CA West East ALL Civic Sierra F150 Camry Truck Sedan ALL Automobile p1 Auto = F150 Loc = NY Repair = $200 Location Slide4:  Extend the OLAP model to handle data ambiguity Imprecision Uncertainty Imprecision:  MA NY TX CA West East ALL Location Civic Sierra F150 Camry Truck Sedan ALL Automobile p1 p2 p3 p4 p5 p6 p7 p8 Auto = F150 Loc = East Repair = $200 p9 p10 Imprecision p11 Representing Imprecision using Dimension Hierarchies :  Representing Imprecision using Dimension Hierarchies Dimension hierarchies lead to a natural space of “partially specified” objects Sources of imprecision: incomplete data, multiple sources of data Motivating Example:  Sierra F150 Truck MA NY East p5 Motivating Example Query: COUNT Desideratum I: Consistency:  Desideratum I: Consistency Consistency specifies the relationship between answers to related queries on a fixed data set Sierra F150 Truck MA NY East p5 Desideratum II: Faithfulness:  Desideratum II: Faithfulness Faithfulness specifies the relationship between answers to a fixed query on related data sets Sierra F150 MA NY Data Set 1 Data Set 2 Data Set 3 Slide10:  Formal definitions of both Consistency and Faithfulness depend on the underlying aggregation operator Can we define query semantics that satisfy these desiderata? Slide11:  p1 p2 Query Semantics Possible Worlds [Kripke63,…] p4 p1 p3 p5 p2 p1 p3 p4 p5 p2 p4 p1 p3 p5 p2 w1 w2 w3 w4 Possible Worlds Query Semantics:  Possible Worlds Query Semantics Given all possible worlds together with their probabilities, queries are easily answered (using expected values) But number of possible worlds is exponential! Allocation:  Allocation Allocation gives facts weighted assignments to possible completions, leading to an extended version of the data Size increase is linear in number of (completions of) imprecise facts Queries operate over this extended version Key contributions: Appropriate characterization of the large space of allocation policies Designing efficient allocation policies that take into account the correlations in the data Storing Allocations using Extended Data Model:  Storing Allocations using Extended Data Model p1 p2 Truck East Classifying Allocation Policies:  Classifying Allocation Policies Ignored Used Ignored Used Uniform EM Count Measure Correlation Dimension Correlation Results on Query Semantics:  Results on Query Semantics Evaluating queries over extended version of data yields expected value of the aggregation operator over all possible worlds intuitively, the correct value to compute Efficient query evaluation algorithms for SUM, COUNT consistency and faithfulness for SUM, COUNT are satisfied under appropriate conditions Dynamic programming algorithm for AVERAGE Unfortunately, consistency does not hold for AVERAGE Alternative Semantics for AVERAGE:  Alternative Semantics for AVERAGE APPROXIMATE AVERAGE E[SUM] / E[COUNT] instead of E[SUM/COUNT] simpler and more efficient satisfies consistency extends to aggregation operators for uncertain measures Uncertainty:  Uncertainty Measure value is modeled as a probability distribution function over some base domain e.g., measure Brake is a pdf over values {Yes,No} sources of uncertainty: measures extracted from text using classifiers Adapt well-known concepts from statistics to derive appropriate aggregation operators Our framework and solutions for dealing with imprecision also extend to uncertain measures Summary:  Summary Consistency and faithfulness desiderata for designing query semantics for imprecise data Allocation is the key to our framework Efficient algorithms for aggregation operators with appropriate guarantees of consistency and faithfulness Iterative algorithms for allocation policies Correlation-based Allocation:  Correlation-based Allocation Involves defining an objective function to capture some underlying correlation structure a more stringent requirement on the allocations solving the resulting optimization problem yields the allocations EM-based iterative allocation policy interesting highlight: allocations are re-scaled iteratively by computing appropriate aggregations

Add a comment

Related presentations

Related pages

s970-burdick - scribd.com

s970-burdick - Download as Powerpoint Presentation (.ppt), PDF File (.pdf), Text File (.txt) or view presentation slides online.
Read more

OLAP Over Uncertain and Imprecise Data - vldb2005.org

OLAP Over Uncertain and Imprecise Data T.S. Jayram (IBM Almaden) with Doug Burdick (Wisconsin), Prasad Deshpande (IBM), Raghu Ramakrishnan (Wisconsin ...
Read more

Symbiosis Linear Schedule - scribd.com

Symbiosis Linear Schedule - Free download as PDF File (.pdf), Text File (.txt) or view presentation slides online.
Read more

MidAmeriCon II - Progress Report 1 (Current Side) by ...

Title: MidAmeriCon II - Progress Report 1 (Current Side ... Bumby A261 Bruce Burdick A262 Jason Burns ... S969 Sarah Skran S970 John L ...
Read more

JoVE Table of Contents: Issue 79, September 2013

Table of Contents: Issue 79, September 2013 Jump to: ... INSERM UMR-S970, ... Monica M. Burdick 1,2.
Read more

HEWLETT PACKARD PHOTOSMART EAIO B 210 - sav.support

... siwamat xlp 1260 chaudiere gaz roca 20 20 matrix pcs 46-45 hoover vhw964d service repair sport direct cc-511 t135 s970 acm 720 ne continental ...
Read more

EAU MORCO D51B PICES DTACHES 】 Notice, mode d'emploi, manuel

... bpl prima 18ka1 quigg dbs600 whirlpool 6th sense awod privileg 8650 amtc dt180u utilisation edy w 500 dp4vr t135 s970 imit logic week marantz sd ...
Read more

It Feels So Good - MIDI Songs - Songs

Composer Sonique, Linus Burdick; Genre Pop; Lead Voice Female Solo; BPM 136; Skill Level Advanced; Keyboard Part Right Hand; Arrangement Realistic; Samples ...
Read more