16 pages

English

comad-tutorial

Ubba - Gautam Das

Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres

16 pages

English

Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres

A propos
Informations
Extrait

Description

Survey of Approximate Query AcknowledgementsProcessing Techniques Brian Babcock (Stanford) Kaushik Chakrabarti (MSR) Mayur Datar (Stanford)Gautam Das Minos Garofalakis (Bell Labs) Venky Ganti (MSR)University of Texas at Arlingtonhttp://ranger.uta.edu/~gdas/2Outline Introduction Introduction Approximate Query Processing (AQP) Non-Sampling Based Methodsin Relational Databases – Histograms – Wavelets Sampling Based Methods Focus on answering Aggregate queries– Uniform Random Sampling – Aggregation queries often arise in OLAP – Biased/Non-Uniform Random Sampling and Data-Mining for large Databases– Distinct Value Estimation Conclusions3 4Examples of Aggregate Motivation for AQPQueries Answering complex aggregation queries over large data warehouses exactly can be SPJ queries with time consuming– aggregation operators such as If approximate answers are acceptable, • Count, Sum, Count(Distinct), Avgcan we answer these queries much faster? – Group By– Along with approximate answers, an estimate of the error in the approximation is important• Confidence Intervals5 61Example Quantifying ErrorSELECT State, COUNT (*) as ItemCountFROM SalesDataWHERE ProductID = 5437 Consider a simple aggregation queryGROUP BY StateORDER BY ItemCount DESC – Answer is a single numberExact Answer Approximate Answer – Relative error of query QState EstItemCount EstErrorStateItemCountExactAnswer− ApproxAnswer3425 3400WA WA 50 Error(Q) ...

Informations

Publié par	Ubba
Nombre de lectures	41
Langue	English

Extrait

             !"!

6  /!  01 %! +! 2 3 2 4   %! +! 2  ,!  2 %!01 ,!  2  . 5  *

+    $      ! $   &    /  $  &8  $ $    9 2  $  $8           : *! /





#$!  % %&# '!(  )# *#& '+,(  +  '!(  + # '% -&(  .#  '+,(



/!     '(  , &  7  $   2      6- ! 1+   & 

5     ;  $      : *8 8 *'(8  2  %





5  8 *60 '<(  /*    !/ = >?@A    !  /* !     /*  5/* 55 4 @?B> 4 @?FF >F * EFC> * EE>F EFF 4D ?@B 4D ?FF >F 0 B@> )D >C 5       & 

%     ! 2 *!  2 1!  ,$         





3   & '( !     &#  / 2 3$   2 4     &# 2 3$    $     -       $   G 

 5  *!     2 $    & 2 ,               7 ,61%D  2 5   =    

   38 48   * ! ! 2 *    -  2  ! !  2 ,   ! ! 2 +  ! :      #

E1 3 51                          5 &  $  &# 2 % &#  









51 3 *  7 8  # %1E 1!   7  8 # 1 !    2 0  &#  *   1  



$  '/(    &#     8         *   * !                       &#   !  0!                                 

+1 3    &  1! &#  !   P ! !&   ! Q   $ &# "$ !#$% " !#$%      



$                             '<(  , $ ? , H= E> H=   $ 7 < I,I%8 $ 2 7 = &  &#8 ! 8      2   J B < I,I% $ @> < I,IC J F> < I,IC

E1 3 .16   &#  G   $ &# K/!8  L>M  6'%<0NB(  !   K;!  8 LOM

+1 3 *  * &   !   $ ! K+#   LLM  +1! 1!  K+#8 4 OOM 2 7  !   ! E8 B8 8 # 2 -  = #   !!   &# 2 G % = ! !& 2 7  = E8 8 # :   &#  %   1!    2   &#  #& !   &#GR !  ! ! ! !     









+1 3 *  +3/  K 8 /! LA M 2    : *  &# &  %   &   $      !   :  &     '8 =B( &#  +3/  &#!   &!   8  $      &#G '   (  5     1! 



3     E1     +   1  !            !                           & & 2+!    P! !   3&         



61 3 4   $ &8   !! !  ,    *                           3 $ !         

6 +1   3 K   LFM 2 $   &#  3 K%   FEM 2 4#! &! 2 *! ! &#

4  +    !         !





3 4 *  3 ! * ST   '# S T(                                                   '% ( 



41&!   ) !    &  $  K+   LOM   2 * $   $$) ( (#$% 2 * (%'   &HHI*I   & # : #    #$%*()$ 2 !    P &   2 6   + ! '-B( 5 : !  ! 2 ,  !    !  

+1 3 4  % $  ! ! !     ! !  $ & ! 11   S$T 2 !! 3 ! KG   LCM 2 01!! 3 ! K*#&   FFM 

  % /!    !     ! ,  $1   ! 2 7    $8      Q ST   2    !   $    !& &  $   

5   ,  'H= UH= &( = *VK&M 1 *VK1EM 2 *V   '( S!T  !& 2  6'W&8 0X(8 $ & = G  $  0= G  !    0YE   !!    *  



4   &  1 !   5      &  +1! $ !  & !!    $ 8 $     &      

 %      58    BFZ                   ,     6   '<(  , $ , = F * = EF ,$   > < '<(   $  = F 5  = ><B = EF





01%!    ! !  !  2 58  !      &   5  P  !     $  && P 2 / !8   !!!    $    = EP       !" # # # $ $ % &&&  &&& &&&  6 ,$   ',(  ,  ' < (   $ ,& H > $ & H > ',( = E@F '<( EF<@ Y >F<B = E@F = 

5 5  - , = W E 8  B 8 [8   X &    & - ',( = D  -  &     G #  , - '( =                         5 !   & !  * -  2 58 >?8FFF J CFF $ &&  L>Z

!  %!    !# # $( .%%'0 +%%'  ,$ #$ %% ./$ %'0 "%- -  





5 5  %#( %  8 8   2 /8  !    $     $     $ !!  2  G 2 .   !    & ! $  && 2 -    %(% %)   $  $   K8&  2&& M $   : 58 >?8FFF J CFF $ &&  LF



6  1!   6 2 *   $ '  ( 2 6     8  !   ! !  !# : 6    K38 3  FEM  1! 2   !    '& Q  ( : '%         ( 2 6  1!   !   2 +!!$ *  $  %+8   !  

 ,!   1  %    2 5!  G  <0 8 $      2 !!    ,    $ &&  2 -$ !8  ! !   1*  ,  K. O>M 2 +     !1G <0 2 !!  $    $  && 2 / 8   !    2 /!       8 !  &    # &    & !!!   



!!   ,!  ! 2  2 5  ! 2 -  !  : - !  : -$  

-$         %' $ ! &   , 

6 /!     ' (+ .  , + ,   )' *(  )' -*(   *(







-  . @  ? ! B    > EZ    EF?>AB >  L      [ 

%!   6 /!  % /! K*!   FEM 2         !    ! 2 )   !    ! 2   !  $  !   $  

  6 /!    '&P   (           / / / /     !       !   # # /0 /0 . / 0 . /1/0 & /0  /0 . /1





 6 /! / / / /   '( 3 4/5 / / / /  2 3  / / / /  2 3  2 3  2 3 



  3$    &$  !  !9  6 !    8  2 0   * 8 + 8 +  & 6  - 6 

$&# $   ,!   / 8  &   *  $     5 2 *!   !    4    !  2   &!  +!   & !    ! ! 4 2 /  8     $  



 /  ,        +  ! = B < G   !



%!   /*/*-5 K   FFM  - 4 = WE8 B8 X &   $#!  %!    !  2   '8 \ (   1!   %!   ! ! ! 'S1T(   $#! 

-   4#! 4#! 4  E 8[8  4 4 &  8 8 4 ! /    !   /    $ 4   !  $   !   &   4 



&   2 , , 2 4#! 4  E 8[8  2  !      +  S   4 ',(  , ! $ 4 T      $ 4

+ /  * $#! 4  E 8[8   - ,  Y ,' E (  Y [  Y ,'  (  *   4 ',( !   - 0$    !  4 ',(  &    -  Y ,'( 2 ,    !  0 -   G!





/*/*-5           $      4            '&        4  ' ( ,  (        /   '(   $  $#! 48     ' ( 4 ',(    !  !  &    $ !   !          ! !  

/*/*-5  ,'(     , !  $   /  4 ',( ,!   ,  Y ,' E (  Y[[  Y ,'  ( 2  !    #  &   4 ',(      ,! 3 6        

,  4#!  +     & $! ]  4   !   $#!9 2 ! &$   !  ,  $#!    2 !  ! 2 ,      



%!   *     %  K   FFM 2      !   Q     $   : 5 &     S  T      &  &      +G      '  (   1&  

