16 pages
English

-

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

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) ...

Sujets

##### Sciences formelles

Informations

 Publié par Nombre de lectures 41 Langue English
            !"!
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 01!! 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!  62 *   \$ '  ( 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   > EZ   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  & * \$    52 *!   !    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 44 & 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&  