(original) (raw)

%!PS-Adobe-2.0 %%Creator: dvips(k) 5.86 Copyright 1999 Radical Eye Software %%Title: icac2004.dvi %%Pages: 8 %%PageOrder: Ascend %%BoundingBox: 0 0 596 842 %%DocumentFonts: Times-Bold Times-Roman Times-Italic Courier %%+ Helvetica-Bold Helvetica %%EndComments %DVIPSWebPage: (www.radicaleye.com) %DVIPSCommandLine: dvips -f icac2004.dvi -o icac2004.ps %DVIPSParameters: dpi=600, compressed %DVIPSSource: TeX output 2004.03.23:1556 %%BeginProcSet: texc.pro %! /TeXDict 300 dict def TeXDict begin/N{def}def/B{bind def}N/S{exch}N/X{S N}B/A{dup}B/TR{translate}N/isls false N/vsize 11 72 mul N/hsize 8.5 72 mul N/landplus90{false}def/@rigin{isls{[0 landplus90{1 -1}{-1 1}ifelse 0 0 0]concat}if 72 Resolution div 72 VResolution div neg scale isls{ landplus90{VResolution 72 div vsize mul 0 exch}{Resolution -72 div hsize mul 0}ifelse TR}if Resolution VResolution vsize -72 div 1 add mul TR[ matrix currentmatrix{A A round sub abs 0.00001 lt{round}if}forall round exch round exch]setmatrix}N/@landscape{/isls true N}B/@manualfeed{ statusdict/manualfeed true put}B/@copies{/#copies X}B/FMat[1 0 0 -1 0 0] N/FBB[0 0 0 0]N/nn 0 N/IEn 0 N/ctr 0 N/df-tail{/nn 8 dict N nn begin /FontType 3 N/FontMatrix fntrx N/FontBBox FBB N string/base X array /BitMaps X/BuildChar{CharBuilder}N/Encoding IEn N end A{/foo setfont}2 array copy cvx N load 0 nn put/ctr 0 N[}B/sf 0 N/df{/sf 1 N/fntrx FMat N df-tail}B/dfs{div/sf X/fntrx[sf 0 0 sf neg 0 0]N df-tail}B/E{pop nn A definefont setfont}B/Cw{Cd A length 5 sub get}B/Ch{Cd A length 4 sub get }B/Cx{128 Cd A length 3 sub get sub}B/Cy{Cd A length 2 sub get 127 sub} B/Cdx{Cd A length 1 sub get}B/Ci{Cd A type/stringtype ne{ctr get/ctr ctr 1 add N}if}B/id 0 N/rw 0 N/rc 0 N/gp 0 N/cp 0 N/G 0 N/CharBuilder{save 3 1 roll S A/base get 2 index get S/BitMaps get S get/Cd X pop/ctr 0 N Cdx 0 Cx Cy Ch sub Cx Cw add Cy setcachedevice Cw Ch true[1 0 0 -1 -.1 Cx sub Cy .1 sub]/id Ci N/rw Cw 7 add 8 idiv string N/rc 0 N/gp 0 N/cp 0 N{ rc 0 ne{rc 1 sub/rc X rw}{G}ifelse}imagemask restore}B/G{{id gp get/gp gp 1 add N A 18 mod S 18 idiv pl S get exec}loop}B/adv{cp add/cp X}B /chg{rw cp id gp 4 index getinterval putinterval A gp add/gp X adv}B/nd{ /cp 0 N rw exit}B/lsh{rw cp 2 copy get A 0 eq{pop 1}{A 255 eq{pop 254}{ A A add 255 and S 1 and or}ifelse}ifelse put 1 adv}B/rsh{rw cp 2 copy get A 0 eq{pop 128}{A 255 eq{pop 127}{A 2 idiv S 128 and or}ifelse} ifelse put 1 adv}B/clr{rw cp 2 index string putinterval adv}B/set{rw cp fillstr 0 4 index getinterval putinterval adv}B/fillstr 18 string 0 1 17 {2 copy 255 put pop}for N/pl[{adv 1 chg}{adv 1 chg nd}{1 add chg}{1 add chg nd}{adv lsh}{adv lsh nd}{adv rsh}{adv rsh nd}{1 add adv}{/rc X nd}{ 1 add set}{1 add clr}{adv 2 chg}{adv 2 chg nd}{pop nd}]A{bind pop} forall N/D{/cc X A type/stringtype ne{]}if nn/base get cc ctr put nn /BitMaps get S ctr S sf 1 ne{A A length 1 sub A 2 index S get sf div put }if put/ctr ctr 1 add N}B/I{cc 1 add D}B/bop{userdict/bop-hook known{ bop-hook}if/SI save N @rigin 0 0 moveto/V matrix currentmatrix A 1 get A mul exch 0 get A mul add .99 lt{/QV}{/RV}ifelse load def pop pop}N/eop{ SI restore userdict/eop-hook known{eop-hook}if showpage}N/@start{ userdict/start-hook known{start-hook}if pop/VResolution X/Resolution X 1000 div/DVImag X/IEn 256 array N 2 string 0 1 255{IEn S A 360 add 36 4 index cvrs cvn put}for pop 65781.76 div/vsize X 65781.76 div/hsize X}N /p{show}N/RMat[1 0 0 -1 0 0]N/BDot 260 string N/Rx 0 N/Ry 0 N/V{}B/RV/v{ /Ry X/Rx X V}B statusdict begin/product where{pop false[(Display)(NeXT) (LaserWriter 16/600)]{A length product length le{A length product exch 0 exch getinterval eq{pop true exit}if}{pop}ifelse}forall}{false}ifelse end{{gsave TR -.1 .1 TR 1 1 scale Rx Ry false RMat{BDot}imagemask grestore}}{{gsave TR -.1 .1 TR Rx Ry scale 1 1 false RMat{BDot} imagemask grestore}}ifelse B/QV{gsave newpath transform round exch round exch itransform moveto Rx 0 rlineto 0 Ry neg rlineto Rx neg 0 rlineto fill grestore}B/a{moveto}B/delta 0 N/tail{A/delta X 0 rmoveto}B/M{S p delta add tail}B/b{S p tail}B/c{-4 M}B/d{-3 M}B/e{-2 M}B/f{-1 M}B/g{0 M} B/h{1 M}B/i{2 M}B/j{3 M}B/k{4 M}B/w{0 rmoveto}B/l{p -4 w}B/m{p -3 w}B/n{ p -2 w}B/o{p -1 w}B/q{p 1 w}B/r{p 2 w}B/s{p 3 w}B/t{p 4 w}B/x{0 S rmoveto}B/y{3 2 roll p a}B/bos{/SS save N}B/eos{SS restore}B end %%EndProcSet %%BeginProcSet: 8r.enc % @@psencodingfile@{ % author = "S. Rahtz, P. MacKay, Alan Jeffrey, B. Horn, K. Berry", % version = "0.6", % date = "22 June 1996", % filename = "8r.enc", % email = "kb@@mail.tug.org", % address = "135 Center Hill Rd. // Plymouth, MA 02360", % codetable = "ISO/ASCII", % checksum = "119 662 4424", % docstring = "Encoding for TrueType or Type 1 fonts to be used with TeX." % @} % % Idea is to have all the characters normally included in Type 1 fonts % available for typesetting. This is effectively the characters in Adobe % Standard Encoding + ISO Latin 1 + extra characters from Lucida. % % Character code assignments were made as follows: % % (1) the Windows ANSI characters are almost all in their Windows ANSI % positions, because some Windows users cannot easily reencode the % fonts, and it makes no difference on other systems. The only Windows % ANSI characters not available are those that make no sense for % typesetting -- rubout (127 decimal), nobreakspace (160), softhyphen % (173). quotesingle and grave are moved just because it's such an % irritation not having them in TeX positions. % % (2) Remaining characters are assigned arbitrarily to the lower part % of the range, avoiding 0, 10 and 13 in case we meet dumb software. % % (3) Y&Y Lucida Bright includes some extra text characters; in the % hopes that other PostScript fonts, perhaps created for public % consumption, will include them, they are included starting at 0x12. % % (4) Remaining positions left undefined are for use in (hopefully) % upward-compatible revisions, if someday more characters are generally % available. % % (5) hyphen appears twice for compatibility with both ASCII and Windows. % /TeXBase1Encoding [ % 0x00 (encoded characters from Adobe Standard not in Windows 3.1) /.notdef /dotaccent /fi /fl /fraction /hungarumlaut /Lslash /lslash /ogonek /ring /.notdef /breve /minus /.notdef % These are the only two remaining unencoded characters, so may as % well include them. /Zcaron /zcaron % 0x10 /caron /dotlessi % (unusual TeX characters available in, e.g., Lucida Bright) /dotlessj /ff /ffi /ffl /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef % very contentious; it's so painful not having quoteleft and quoteright % at 96 and 145 that we move the things normally found there down to here. /grave /quotesingle % 0x20 (ASCII begins) /space /exclam /quotedbl /numbersign /dollar /percent /ampersand /quoteright /parenleft /parenright /asterisk /plus /comma /hyphen /period /slash % 0x30 /zero /one /two /three /four /five /six /seven /eight /nine /colon /semicolon /less /equal /greater /question % 0x40 /at /A /B /C /D /E /F /G /H /I /J /K /L /M /N /O % 0x50 /P /Q /R /S /T /U /V /W /X /Y /Z /bracketleft /backslash /bracketright /asciicircum /underscore % 0x60 /quoteleft /a /b /c /d /e /f /g /h /i /j /k /l /m /n /o % 0x70 /p /q /r /s /t /u /v /w /x /y /z /braceleft /bar /braceright /asciitilde /.notdef % rubout; ASCII ends % 0x80 /.notdef /.notdef /quotesinglbase /florin /quotedblbase /ellipsis /dagger /daggerdbl /circumflex /perthousand /Scaron /guilsinglleft /OE /.notdef /.notdef /.notdef % 0x90 /.notdef /.notdef /.notdef /quotedblleft /quotedblright /bullet /endash /emdash /tilde /trademark /scaron /guilsinglright /oe /.notdef /.notdef /Ydieresis % 0xA0 /.notdef % nobreakspace /exclamdown /cent /sterling /currency /yen /brokenbar /section /dieresis /copyright /ordfeminine /guillemotleft /logicalnot /hyphen % Y&Y (also at 45); Windows' softhyphen /registered /macron % 0xD0 /degree /plusminus /twosuperior /threesuperior /acute /mu /paragraph /periodcentered /cedilla /onesuperior /ordmasculine /guillemotright /onequarter /onehalf /threequarters /questiondown % 0xC0 /Agrave /Aacute /Acircumflex /Atilde /Adieresis /Aring /AE /Ccedilla /Egrave /Eacute /Ecircumflex /Edieresis /Igrave /Iacute /Icircumflex /Idieresis % 0xD0 /Eth /Ntilde /Ograve /Oacute /Ocircumflex /Otilde /Odieresis /multiply /Oslash /Ugrave /Uacute /Ucircumflex /Udieresis /Yacute /Thorn /germandbls % 0xE0 /agrave /aacute /acircumflex /atilde /adieresis /aring /ae /ccedilla /egrave /eacute /ecircumflex /edieresis /igrave /iacute /icircumflex /idieresis % 0xF0 /eth /ntilde /ograve /oacute /ocircumflex /otilde /odieresis /divide /oslash /ugrave /uacute /ucircumflex /udieresis /yacute /thorn /ydieresis ] def %%EndProcSet %%BeginProcSet: texps.pro %! TeXDict begin/rf{findfont dup length 1 add dict begin{1 index/FID ne 2 index/UniqueID ne and{def}{pop pop}ifelse}forall[1 index 0 6 -1 roll exec 0 exch 5 -1 roll VResolution Resolution div mul neg 0 0]/Metrics exch def dict begin Encoding{exch dup type/integertype ne{pop pop 1 sub dup 0 le{pop}{[}ifelse}{FontMatrix 0 get div Metrics 0 get div def} ifelse}forall Metrics/Metrics currentdict end def[2 index currentdict end definefont 3 -1 roll makefont/setfont cvx]cvx def}def/ObliqueSlant{ dup sin S cos div neg}B/SlantFont{4 index mul add}def/ExtendFont{3 -1 roll mul exch}def/ReEncodeFont{CharStrings rcheck{/Encoding false def dup[exch{dup CharStrings exch known not{pop/.notdef/Encoding true def} if}forall Encoding{]exch pop}{cleartomark}ifelse}if/Encoding exch def} def end %%EndProcSet %%BeginProcSet: special.pro %! TeXDict begin/SDict 200 dict N SDict begin/@SpecialDefaults{/hs 612 N /vs 792 N/ho 0 N/vo 0 N/hsc 1 N/vsc 1 N/ang 0 N/CLIP 0 N/rwiSeen false N /rhiSeen false N/letter{}N/note{}N/a4{}N/legal{}N}B/@scaleunit 100 N /@hscale{@scaleunit div/hsc X}B/@vscale{@scaleunit div/vsc X}B/@hsize{ /hs X/CLIP 1 N}B/@vsize{/vs X/CLIP 1 N}B/@clip{/CLIP 2 N}B/@hoffset{/ho X}B/@voffset{/vo X}B/@angle{/ang X}B/@rwi{10 div/rwi X/rwiSeen true N}B /@rhi{10 div/rhi X/rhiSeen true N}B/@llx{/llx X}B/@lly{/lly X}B/@urx{ /urx X}B/@ury{/ury X}B/magscale true def end/@MacSetUp{userdict/md known {userdict/md get type/dicttype eq{userdict begin md length 10 add md maxlength ge{/md md dup length 20 add dict copy def}if end md begin /letter{}N/note{}N/legal{}N/od{txpose 1 0 mtx defaultmatrix dtransform S atan/pa X newpath clippath mark{transform{itransform moveto}}{transform{ itransform lineto}}{6 -2 roll transform 6 -2 roll transform 6 -2 roll transform{itransform 6 2 roll itransform 6 2 roll itransform 6 2 roll curveto}}{{closepath}}pathforall newpath counttomark array astore/gc xdf pop ct 39 0 put 10 fz 0 fs 2 F/|______Courier fnt invertflag{PaintBlack} if}N/txpose{pxs pys scale ppr aload pop por{noflips{pop S neg S TR pop 1 -1 scale}if xflip yflip and{pop S neg S TR 180 rotate 1 -1 scale ppr 3 get ppr 1 get neg sub neg ppr 2 get ppr 0 get neg sub neg TR}if xflip yflip not and{pop S neg S TR pop 180 rotate ppr 3 get ppr 1 get neg sub neg 0 TR}if yflip xflip not and{ppr 1 get neg ppr 0 get neg TR}if}{ noflips{TR pop pop 270 rotate 1 -1 scale}if xflip yflip and{TR pop pop 90 rotate 1 -1 scale ppr 3 get ppr 1 get neg sub neg ppr 2 get ppr 0 get neg sub neg TR}if xflip yflip not and{TR pop pop 90 rotate ppr 3 get ppr 1 get neg sub neg 0 TR}if yflip xflip not and{TR pop pop 270 rotate ppr 2 get ppr 0 get neg sub neg 0 S TR}if}ifelse scaleby96{ppr aload pop 4 -1 roll add 2 div 3 1 roll add 2 div 2 copy TR .96 dup scale neg S neg S TR}if}N/cp{pop pop showpage pm restore}N end}if}if}N/normalscale{ Resolution 72 div VResolution 72 div neg scale magscale{DVImag dup scale }if 0 setgray}N/psfts{S 65781.76 div N}N/startTexFig{/psf$SavedState save N userdict maxlength dict begin/magscale true def normalscale currentpoint TR/psf$ury psfts/psf$urx psfts/psf$lly psfts/psf$llx psfts /psf$y psfts/psf$x psfts currentpoint/psf$cy X/psf$cx X/psf$sx psf$x psf$urx psf$llx sub div N/psf$sy psf$y psf$ury psf$lly sub div N psf$sx psf$sy scale psf$cx psf$sx div psf$llx sub psf$cy psf$sy div psf$ury sub TR/showpage{}N/erasepage{}N/copypage{}N/p 3 def @MacSetUp}N/doclip{ psf$llx psf$lly psf$urx psf$ury currentpoint 6 2 roll newpath 4 copy 4 2 roll moveto 6 -1 roll S lineto S lineto S lineto closepath clip newpath moveto}N/endTexFig{end psf$SavedState restore}N/@beginspecial{SDict begin/SpecialSave save N gsave normalscale currentpoint TR @SpecialDefaults count/ocount X/dcount countdictstack N}N/@setspecial{ CLIP 1 eq{newpath 0 0 moveto hs 0 rlineto 0 vs rlineto hs neg 0 rlineto closepath clip}if ho vo TR hsc vsc scale ang rotate rwiSeen{rwi urx llx sub div rhiSeen{rhi ury lly sub div}{dup}ifelse scale llx neg lly neg TR }{rhiSeen{rhi ury lly sub div dup scale llx neg lly neg TR}if}ifelse CLIP 2 eq{newpath llx lly moveto urx lly lineto urx ury lineto llx ury lineto closepath clip}if/showpage{}N/erasepage{}N/copypage{}N newpath}N /@endspecial{count ocount sub{pop}repeat countdictstack dcount sub{end} repeat grestore SpecialSave restore end}N/@defspecial{SDict begin}N /@fedspecial{end}B/li{lineto}B/rl{rlineto}B/rc{rcurveto}B/np{/SaveX currentpoint/SaveY X N 1 setlinecap newpath}N/st{stroke SaveX SaveY moveto}N/fil{fill SaveX SaveY moveto}N/ellipse{/endangle X/startangle X /yrad X/xrad X/savematrix matrix currentmatrix N TR xrad yrad scale 0 0 1 startangle endangle arc savematrix setmatrix}N end %%EndProcSet %%BeginProcSet: color.pro %! TeXDict begin/setcmykcolor where{pop}{/setcmykcolor{dup 10 eq{pop setrgbcolor}{1 sub 4 1 roll 3{3 index add neg dup 0 lt{pop 0}if 3 1 roll }repeat setrgbcolor pop}ifelse}B}ifelse/TeXcolorcmyk{setcmykcolor}def /TeXcolorrgb{setrgbcolor}def/TeXcolorgrey{setgray}def/TeXcolorgray{ setgray}def/TeXcolorhsb{sethsbcolor}def/currentcmykcolor where{pop}{ /currentcmykcolor{currentrgbcolor 10}B}ifelse/DC{exch dup userdict exch known{pop pop}{X}ifelse}B/GreenYellow{0.15 0 0.69 0 setcmykcolor}DC /Yellow{0 0 1 0 setcmykcolor}DC/Goldenrod{0 0.10 0.84 0 setcmykcolor}DC /Dandelion{0 0.29 0.84 0 setcmykcolor}DC/Apricot{0 0.32 0.52 0 setcmykcolor}DC/Peach{0 0.50 0.70 0 setcmykcolor}DC/Melon{0 0.46 0.50 0 setcmykcolor}DC/YellowOrange{0 0.42 1 0 setcmykcolor}DC/Orange{0 0.61 0.87 0 setcmykcolor}DC/BurntOrange{0 0.51 1 0 setcmykcolor}DC /Bittersweet{0 0.75 1 0.24 setcmykcolor}DC/RedOrange{0 0.77 0.87 0 setcmykcolor}DC/Mahogany{0 0.85 0.87 0.35 setcmykcolor}DC/Maroon{0 0.87 0.68 0.32 setcmykcolor}DC/BrickRed{0 0.89 0.94 0.28 setcmykcolor}DC/Red{ 0 1 1 0 setcmykcolor}DC/OrangeRed{0 1 0.50 0 setcmykcolor}DC/RubineRed{ 0 1 0.13 0 setcmykcolor}DC/WildStrawberry{0 0.96 0.39 0 setcmykcolor}DC /Salmon{0 0.53 0.38 0 setcmykcolor}DC/CarnationPink{0 0.63 0 0 setcmykcolor}DC/Magenta{0 1 0 0 setcmykcolor}DC/VioletRed{0 0.81 0 0 setcmykcolor}DC/Rhodamine{0 0.82 0 0 setcmykcolor}DC/Mulberry{0.34 0.90 0 0.02 setcmykcolor}DC/RedViolet{0.07 0.90 0 0.34 setcmykcolor}DC /Fuchsia{0.47 0.91 0 0.08 setcmykcolor}DC/Lavender{0 0.48 0 0 setcmykcolor}DC/Thistle{0.12 0.59 0 0 setcmykcolor}DC/Orchid{0.32 0.64 0 0 setcmykcolor}DC/DarkOrchid{0.40 0.80 0.20 0 setcmykcolor}DC/Purple{ 0.45 0.86 0 0 setcmykcolor}DC/Plum{0.50 1 0 0 setcmykcolor}DC/Violet{ 0.79 0.88 0 0 setcmykcolor}DC/RoyalPurple{0.75 0.90 0 0 setcmykcolor}DC /BlueViolet{0.86 0.91 0 0.04 setcmykcolor}DC/Periwinkle{0.57 0.55 0 0 setcmykcolor}DC/CadetBlue{0.62 0.57 0.23 0 setcmykcolor}DC /CornflowerBlue{0.65 0.13 0 0 setcmykcolor}DC/MidnightBlue{0.98 0.13 0 0.43 setcmykcolor}DC/NavyBlue{0.94 0.54 0 0 setcmykcolor}DC/RoyalBlue{1 0.50 0 0 setcmykcolor}DC/Blue{1 1 0 0 setcmykcolor}DC/Cerulean{0.94 0.11 0 0 setcmykcolor}DC/Cyan{1 0 0 0 setcmykcolor}DC/ProcessBlue{0.96 0 0 0 setcmykcolor}DC/SkyBlue{0.62 0 0.12 0 setcmykcolor}DC/Turquoise{0.85 0 0.20 0 setcmykcolor}DC/TealBlue{0.86 0 0.34 0.02 setcmykcolor}DC /Aquamarine{0.82 0 0.30 0 setcmykcolor}DC/BlueGreen{0.85 0 0.33 0 setcmykcolor}DC/Emerald{1 0 0.50 0 setcmykcolor}DC/JungleGreen{0.99 0 0.52 0 setcmykcolor}DC/SeaGreen{0.69 0 0.50 0 setcmykcolor}DC/Green{1 0 1 0 setcmykcolor}DC/ForestGreen{0.91 0 0.88 0.12 setcmykcolor}DC /PineGreen{0.92 0 0.59 0.25 setcmykcolor}DC/LimeGreen{0.50 0 1 0 setcmykcolor}DC/YellowGreen{0.44 0 0.74 0 setcmykcolor}DC/SpringGreen{ 0.26 0 0.76 0 setcmykcolor}DC/OliveGreen{0.64 0 0.95 0.40 setcmykcolor} DC/RawSienna{0 0.72 1 0.45 setcmykcolor}DC/Sepia{0 0.83 1 0.70 setcmykcolor}DC/Brown{0 0.81 1 0.60 setcmykcolor}DC/Tan{0.14 0.42 0.56 0 setcmykcolor}DC/Gray{0 0 0 0.50 setcmykcolor}DC/Black{0 0 0 1 setcmykcolor}DC/White{0 0 0 0 setcmykcolor}DC end %%EndProcSet TeXDict begin @defspecial userdict begin /bop-hook{gsave 200 50 translate 65 rotate /Times-Roman findfont 216 scalefont setfont 0 0 moveto .85 setgray (DRAFT) show grestore} def end @fedspecial end TeXDict begin 39158280 55380996 1000 600 600 (icac2004.dvi) @start /Fa 135[45 45 45 1[45 3[45 45 45 45 45 2[45 45 2[45 45 45 40[45 10[45 45 46[{TeXBase1Encoding ReEncodeFont}17 74.7198 /Courier rf /Fb 133[29 33 1[50 33 37 21 29 29 1[37 37 37 54 21 33 1[21 37 37 21 33 37 33 37 37 9[62 46 54 42 37 46 1[46 54 50 62 42 50 33 25 1[54 46 46 54 50 1[46 6[25 4[37 37 1[37 1[37 21 19 25 19 2[25 25 37[37 2[{TeXBase1Encoding ReEncodeFont}55 74.7198 /Times-Italic rf %DVIPSBitmapFont: Fc cmmi5 5 1 /Fc 1 117 df<13C0EA01E0A3EA03C0A4EAFFFCA2EA0780A2EA0F00A4121EA31304EA3C 0CA213181370EA1FE0EA0F800E1A7D9917>116 D E %EndDVIPSBitmapFont /Fd 134[42 1[58 42 46 25 42 29 46 46 46 46 66 21 2[21 46 46 25 42 46 42 46 42 13[50 54 3[54 10[54 13[42 42 5[21 46[{TeXBase1Encoding ReEncodeFont}29 74.7198 /Helvetica-Bold rf /Fe 105[37 27[33 37 37 54 37 37 21 29 25 1[37 37 37 58 21 37 21 21 37 37 25 33 37 33 37 33 3[25 1[25 1[54 1[71 54 54 46 42 50 54 42 54 54 66 46 54 29 25 54 54 42 46 54 50 50 54 6[21 37 37 37 37 37 37 37 37 37 37 1[19 25 19 2[25 25 22[21 13[42 42 2[{TeXBase1Encoding ReEncodeFont}71 74.7198 /Times-Roman rf /Ff 137[29 1[18 1[26 2[33 9[29 98[33 2[{TeXBase1Encoding ReEncodeFont}6 66.4176 /Times-Italic rf /Fg 137[33 1[18 26 22 1[33 33 33 52 18 33 1[18 33 33 22 29 33 29 33 29 9[63 12[26 6[44 10[33 2[33 33 1[33 33 2[17 22 17 41[37 2[{TeXBase1Encoding ReEncodeFont}31 66.4176 /Times-Roman rf %DVIPSBitmapFont: Fh cmex10 10 1 /Fh 1 81 df80 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fi cmmi7 7 6 /Fi 6 123 df<013FB612F0A2903901FC00074A1301160001031560A25CA21307A25CED 0180010F0103130093C7FC14C05D131F151EECFFFEA290383F801E150C1400A249131C15 18137E92C8FC13FEA25BA21201A25BA21203B512F0A22C287DA72A>70 D99 D102 D<130E131F5BA2133E131C90C7FC A7EA03E0487EEA0C78EA187C1230A212605B12C0A2EA01F0A3485AA2485AA2EBC180EA0F 81A2381F0300A213066C5A131CEA07F06C5A11287DA617>105 D<131C133EA25BA45BA4 485AB512E0A23801F000485AA4485AA4485AA448C7FC1460A214C0123EEB0180EB0300EA 1E06EA1F1CEA0FF8EA03E013267EA419>116 D<013E13C0137F9038FF818048EBC30048 13FF380701FE3806000C00045BC75A5C5CEB03800106C7FC5B5B5B5B9038C00180EA0380 39060003005C380FF81E381FFFFE38383FFC38601FF86D5A38C007C01A1B7D9920>122 D E %EndDVIPSBitmapFont /Fj 205[29 29 49[{TeXBase1Encoding ReEncodeFont}2 58.1154 /Times-Roman rf /Fk 134[46 46 1[46 51 28 46 32 1[51 51 51 74 23 2[23 51 51 28 46 51 46 51 46 12[51 55 2[55 2[69 6[51 55 1[60 1[60 11[46 46 46 46 46 2[23 28 23 44[{ TeXBase1Encoding ReEncodeFont}37 83.022 /Helvetica-Bold rf %DVIPSBitmapFont: Fl cmmi10 10 33 /Fl 33 123 df<121C127FEAFF80A5EA7F00121C0909798817>58 D<121C127FEAFF80A213C0A3127F121C1200A412011380A2120313005A1206120E5A5A5A 12600A19798817>I<126012FCB4FCEA7FC0EA1FF0EA07FCEA01FF38007FC0EB1FF0EB07 FCEB01FF9038007FC0EC1FF0EC07FCEC01FF9138007FC0ED1FF0ED07FCED01FF9238007F C0EE1FF0EE07FCEE01FF9338007F80EF1FC0A2EF7F80933801FF00EE07FCEE1FF0EE7FC0 4B48C7FCED07FCED1FF0ED7FC04A48C8FCEC07FCEC1FF0EC7FC04948C9FCEB07FCEB1FF0 EB7FC04848CAFCEA07FCEA3FF0EA7FC048CBFC12FC1270323279AD41>62 D<9339FF8001C0030F13E0037F9038F80380913A01FF807E07913A07F8000F0FDA1FE0EB 079FDA3F80903803BF0002FFC76CB4FCD901FC80495A4948157E495A495A4948153E017F 163C49C9FC5B1201484816385B1207485A1830121F4993C7FCA2485AA3127F5BA312FF90 CCFCA41703A25F1706A26C160E170C171C5F6C7E5F001F5E6D4A5A6C6C4A5A16076C6C02 0EC8FC6C6C143C6C6C5C6CB4495A90393FE00FC0010FB5C9FC010313FC9038007FC03A3D 7CBA3B>67 D<0103B812E05BA290260007F8C7123F4B140FF003C0140F18015DA2141FA2 5D1980143FA25D1760027F14E095C7FC92C75AA24A1301A24A495A16070101141F91B6FC 94C8FCA2903903FC001F824A130EA21307A24A130CA2010F141CA24A90C9FCA2131FA25C A2133FA25CA2137FA291CBFC497EB612C0A33B397DB835>70 DI<0103B5D8F803B512F8495DA290260007F8C73807F8004B5DA2020F150F61 5DA2021F151F615DA2023F153F615DA2027F157F96C7FC92C8FCA24A5D605CA249B7FC60 A202FCC7120101031503605CA201071507605CA2010F150F605CA2011F151F605CA2013F 153F605CA2017F157F95C8FC91C8FC496C4A7EB690B6FCA345397DB845>I<902603FFF8 91381FFFF8496D5CA2D90007030113006FEC007C02061678DA0EFF157081020C6D1460A2 DA1C3F15E0705CEC181F82023815016F6C5C1430150702706D1303030392C7FC02607FA2 DAE0015C701306ECC0008201016E130EEF800C5C163F0103EDC01C041F131891C713E016 0F49EDF03818300106140717F8010E02031370EFFC60130CEE01FE011C16E004005B0118 15FF177F1338600130153FA20170151F95C8FC01F081EA07FCB512E01706A245397DB843 >78 D<0103B7FC4916E018F8903B0007F80007FC4BEB00FE187F020FED3F80F01FC05DA2 021F16E0A25DA2143FF03FC05DA2027FED7F80A292C8130018FE4A4A5A604AEC07F04D5A 0101ED3FC04CB4C7FC91B612FC17E0D903FCCAFCA25CA21307A25CA2130FA25CA2131FA2 5CA2133FA25CA2137FA291CBFC497EB6FCA33B397DB835>80 D<0103B612F849EDFF8018 E0903B0007F8001FF84BEB03FCEF00FE020F157FA24BEC3F80A2021F16C0A25DA2143FF0 7F805DA2027FEDFF006092C7485A4D5A4A4A5A4D5A4AEC1F80057FC7FC0101EC07F891B6 12E094C8FC9139FC000FC00103EC03F0707E4A6D7E831307177E5C177F010F5D5F5CA201 1F1401A25CA2133F16034A4A1360A2017F17E019C091C71401496C01011480B615039339 00FE0700EF7E0ECAEA1FFCEF07F03B3B7DB83F>82 D<0003B812FEA25A903AF8003FC001 01C0913880007E4848163C90C7007F141C121E001C92C7FCA2485CA200305C0070171800 60130112E0485CA21403C716005DA21407A25DA2140FA25DA2141FA25DA2143FA25DA214 7FA292C9FCA25CA25CA21301A25CA21303A25CEB0FFC003FB6FC5AA237397EB831>84 D<49B500F890387FFFF095B5FC1AE0D90003018090380FFC004BC713E00201ED07804EC7 FC6E6C140E606F5C705B606F6C485A4D5A031F91C8FCEEE0065F6F6C5A5F03075B705A16 F96FB45A94C9FC6F5AA36F7EA34B7FED037F9238063FC0150E4B6C7E1538ED700F03E07F 15C04A486C7EEC0300020613034A805C4A6D7E14704A1300494880495A49C86C7E130E01 1E153F017E4B7ED803FF4B7E007F01E0011FEBFFC0B5FC6144397EB845>88 DI<91B712FCA25B9239E00007F84AC7EA0FF0D9 03F8EC1FE04AEC3FC04AEC7F804A150049485C91C7485A4C5A010E4A5A4C5A010C4A5A01 1C4A5A01185D167F4CC7FC90C7485A4B5A4B5A4B5A5E151F4B5A4B5A4BC8FC4A5A4A5A4A 5A5D140F4A5A4A5A4A48130C4AC7FC495A4A141C01031518495A49481438494814304948 1470495A49C812F0495D000115014848140348484A5A4848140F4848141F4848EC7F8048 48EB07FF90B7FCB8FC94C7FC36397BB839>I<147E903803FF8090390FC1C38090391F00 EFC0017E137F49133F485A4848EB1F8012075B000F143F48481400A2485A5D007F147E90 C7FCA215FE485C5AA214015D48150CA21403EDF01C16181407007C1538007E010F133000 3E131F027B13706C01E113E03A0F83C0F9C03A03FF007F80D800FCEB1F0026267DA42C> 97 D99 D<163FED1FFFA3ED007F167EA216FEA216FCA21501A216F8A21503A216F0A215 07A2027E13E0903803FF8790380FC1CF90381F00EF017EEB7FC049133F485A4848131F00 0715805B000F143F485A1600485A5D127F90C7127EA215FE5A485CA21401A248ECF80CA2 1403161CEDF0181407007C1538007E010F1330003E131F027B13706C01E113E03A0F83C0 F9C03A03FF007F80D800FCEB1F00283B7DB92B>II<16F8ED03FEED0F8792381F 0F80ED3E3F167F157CA215FC1700161C4A48C7FCA414035DA414075DA20107B512F0A390 26000FE0C7FC5DA4141F5DA4143F92C8FCA45C147EA514FE5CA413015CA4495AA45C1307 A25C121E123F387F8F80A200FF90C9FC131E12FEEA7C3CEA7878EA1FF0EA07C0294C7CBA 29>I<14E0EB03F8A21307A314F0EB01C090C7FCAB13F8EA03FEEA070F000E1380121C12 1812381230EA701F1260133F00E0130012C05BEA007EA213FE5B1201A25B12035BA20007 131813E01438000F133013C01470EB806014E014C01381EB838038078700EA03FEEA00F8 15397EB71D>105 D<150FED3F80A2157FA31600151C92C7FCABEC0F80EC3FE0ECF0F090 3801C0F849487E14005B130E130C131CEB1801133801305BA2EB0003A25DA21407A25DA2 140FA25DA2141FA25DA2143FA292C7FCA25CA2147EA214FEA25CA21301001E5B123F387F 83F0A238FF87E0495A00FE5BD87C1FC8FCEA707EEA3FF8EA0FC0214981B722>I108 DIII<90390F8003F090391FE0 0FFC903939F03C1F903A70F8700F80903AE0FDE007C09038C0FF80030013E00001491303 018015F05CEA038113015CA2D800031407A25CA20107140FA24A14E0A2010F141F17C05C EE3F80131FEE7F004A137E16FE013F5C6E485A4B5A6E485A90397F700F80DA383FC7FC90 387E1FFCEC07E001FEC9FCA25BA21201A25BA21203A25B1207B512C0A32C3583A42A>I< 3903E001F83907F807FE390E3C1E07391C3E381F3A183F703F800038EBE07F0030EBC0FF 00705B00601500EC007E153CD8E07F90C7FCEAC07EA2120013FE5BA312015BA312035BA3 12075BA3120F5BA3121F5B0007C9FC21267EA425>114 D<14FF010313C090380F80F090 383E00380178131C153C4913FC0001130113E0A33903F000F06D13007F3801FFE014FC14 FF6C14806D13C0011F13E013039038003FF014071403001E1301127FA24814E0A348EB03 C012F800E0EB07800070EB0F006C133E001E13F83807FFE0000190C7FC1E267CA427>I< EB01C0497E1307A4130F5CA3131F5CA3133F91C7FC007FB51280A2B6FCD8007EC7FCA313 FE5BA312015BA312035BA312075BA3120FEBC006A2140E001F130CEB801C141814385C14 6014E0380F81C038078780D803FEC7FCEA00F819357EB31E>I<01F8EB03C0D803FEEB07 E0D8070F130F000E018013F0121C12180038140700301403D8701F130112601500D8E03F 14E000C090C7FC5BEA007E16C013FE5B1501000115805B150316001203495B1506150E15 0C151C151815385D00015C6D485A6C6C485AD97E0FC7FCEB1FFEEB07F024267EA428> 118 D<903907E001F090391FF807FC9039783E0E0F9039E01F1C1FD801C09038383F803A 03800FF07F0100EBE0FF5A000E4A1300000C157E021F133C001C4AC7FC1218A2C7123FA2 92C8FCA25CA2147EA214FEA24A130CA20101141C001E1518003F5BD87F81143801835C00 FF1560010714E03AFE0E7C01C0D87C1C495A2778383E0FC7FC391FF00FFC3907C003F029 267EA42F>120 D<13F8D803FE1470D8070F14F8000EEB8001121C121800381403003015 F0EA701F1260013F130700E0010013E012C05BD8007E130F16C013FE5B151F000115805B A2153F000315005BA25D157EA315FE5D1401000113033800F80790387C1FF8EB3FF9EB0F E1EB00035DA2000E1307D83F805B007F495AA24A5A92C7FCEB003E007C5B00705B6C485A 381E07C06CB4C8FCEA01FC25367EA429>II E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fm cmr10 10 21 /Fm 21 112 df<017C166048B416F02607C3801401260F81C01403D900E04A5A001E0178 4A5A003E6D141F003C013FEC7F80007C90271BE003FFC7FC0218B512BF007891381FFC3E 00F8011CC75A020C14FC5F4C5A16035F4C5A160F5F4CC8FC021C5B00780118133E007C5D 16FC003C01385B003E90383001F0001EEB70036C01E05B903981C007C03907C3800F2601 FF005BD8007C49C9FC90C748EB07C0033EEB1FF04BEB3C3803FCEBF81C4B497E913A01F0 01E00602030103130703E0497E912607C0071480020F15011580DA1F00018013C04A010F 1300143E5C14FC5C495A13035C495A130F4A0107130149C701C013805B013E1603490203 140001FC6F5A49020113064848913800F00E0003705A49ED3C3849ED1FF06C48ED07C03A 437BBD45>37 D<146014E0EB01C0EB0380EB0700130E131E5B5BA25B485AA2485AA21207 5B120F90C7FCA25A121EA2123EA35AA65AB2127CA67EA3121EA2121F7EA27F12077F1203 A26C7EA26C7E1378A27F7F130E7FEB0380EB01C0EB00E01460135278BD20>40 D<12C07E12707E7E7E120F6C7E6C7EA26C7E6C7EA21378A2137C133C133E131EA2131F7F A21480A3EB07C0A6EB03E0B2EB07C0A6EB0F80A31400A25B131EA2133E133C137C1378A2 5BA2485A485AA2485A48C7FC120E5A5A5A5A5A13527CBD20>I<15301578B3A6007FB812 F8B912FCA26C17F8C80078C8FCB3A6153036367BAF41>43 D48 DIII<1538A2157815F8A2140114031407A2140F 141F141B14331473146314C313011483EB030313071306130C131C131813301370136013 C01201EA038013005A120E120C5A123812305A12E0B712F8A3C73803F800AB4A7E0103B5 12F8A325397EB82A>I<0006140CD80780133C9038F003F890B5FC5D5D158092C7FC14FC 38067FE090C9FCABEB07F8EB3FFE9038780F803907E007E090388003F0496C7E12066E7E C87EA28181A21680A4123E127F487EA490C71300485C12E000605C12700030495A00385C 6C1303001E495A6C6C485A3907E03F800001B5C7FC38007FFCEB1FE0213A7CB72A>II<12301238123E003FB612E0A316C05A168016000070C7 12060060140E5D151800E01438485C5D5DC712014A5A92C7FC5C140E140C141C5CA25CA2 14F0495AA21303A25C1307A2130FA3495AA3133FA5137FA96DC8FC131E233B7BB82A>I< EB03F8EB1FFF017F13C09038FC07E03903F803F048486C7E48486C7E49137E121F48487F A2007F158090C7FCA248EC1FC0A616E0A56C143FA27F123F001F147FA26C6C13FF3907E0 01DF0003149F3801F0033900FC0F1FD93FFC13C0EB07F090C7FC153F1680A316005D000F 147E487E486C5BA24A5A4A5A49485A6C48485A001C495A260F807FC7FC3807FFFC000113 F038003FC0233A7DB72A>57 D<121C127FEAFF80A5EA7F00121CC7FCB2121C127F5A1380 A4127F121D1201A412031300A25A1206A2120E5A121812385A1260093479A317>59 D<007FB812F8B912FCA26C17F8CCFCAE007FB812F8B912FCA26C17F836167B9F41>61 D91 D93 D<13101338137C13FE487E3803C780380783C0380F01E038 1E00F04813780070131C48130E00401304170D77B92A>I103 D108 D111 D E %EndDVIPSBitmapFont /Fn 134[46 46 66 1[51 30 36 41 51 51 46 51 76 25 2[25 1[46 30 41 51 41 1[46 12[61 1[66 2[71 1[86 61 71 1[36 71 1[56 61 66 66 61 2[46 9[46 46 46 46 46 2[23 46[{ TeXBase1Encoding ReEncodeFont}40 91.3242 /Times-Bold rf /Fo 133[50 50 50 2[50 50 50 50 50 50 50 50 4[50 50 2[50 50 50 1[50 10[50 1[50 1[50 4[50 3[50 4[50 6[50 19[50 50 6[50 33[{TeXBase1Encoding ReEncodeFont}27 83.022 /Courier rf /Fp 136[60 42 46 28 32 37 1[46 42 46 69 23 46 1[23 46 42 28 37 46 37 46 42 14[60 3[60 5[65 1[51 4[60 18[21 28 45[{TeXBase1Encoding ReEncodeFont}28 83.022 /Times-Bold rf %DVIPSBitmapFont: Fq cmsy10 10 9 /Fq 9 107 df<007FB81280B912C0A26C17803204799641>0 D<121C127FEAFF80A5EA7F 00121C0909799917>I3 D15 D20 D<91381FFFFE91B6FC1303010F14FED91FF0C7FCEB7F8001FEC8FCEA01F8485A 485A485A5B48C9FCA2123EA25AA2127812F8A25AA2B712FE16FFA216FE00F0C9FCA27EA2 1278127CA27EA27EA26C7E7F6C7E6C7E6C7EEA00FEEB7F80EB1FF06DB512FE010314FF13 00021F13FE283279AD37>50 D102 D<12FCEAFFC0EA07F0EA01FCEA007E7F80131F80130FB3A7801307806D7E6D7EEB007EEC 1FF0EC07F8EC1FF0EC7E00495A495A495A5C130F5CB3A7131F5C133F91C7FC137E485AEA 07F0EAFFC000FCC8FC1D537ABD2A>I<126012F0B3B3B3B3A91260045377BD17>106 D E %EndDVIPSBitmapFont /Fr 107[37 37 21[40 1[40 37 42 42 60 42 42 23 32 28 42 42 42 42 65 23 42 23 23 42 42 28 37 42 37 42 37 3[28 1[28 3[78 60 60 51 46 55 1[46 60 60 74 51 60 32 28 60 60 46 51 60 55 55 60 5[23 23 42 42 42 42 42 42 42 42 42 42 23 21 28 21 47 1[28 28 28 1[69 1[42 32[46 2[{ TeXBase1Encoding ReEncodeFont}77 83.022 /Times-Roman rf /Fs 134[37 37 55 37 42 23 32 32 42 42 42 42 60 23 37 1[23 42 42 23 37 42 37 42 42 9[69 4[51 1[51 60 55 69 3[28 2[51 51 1[55 51 12[42 42 42 42 42 2[21 28 21 4[28 36[42 2[{TeXBase1Encoding ReEncodeFont}45 83.022 /Times-Italic rf /Ft 134[50 50 1[50 55 33 39 44 1[55 50 55 83 28 55 1[28 55 50 33 44 55 44 55 50 9[100 2[66 55 72 5[66 2[39 3[66 72 72 66 72 8[50 50 50 50 50 50 50 50 2[25 46[{TeXBase1Encoding ReEncodeFont}42 99.6264 /Times-Bold rf /Fu 130[40 1[40 39 44 1[66 44 50 28 39 39 2[50 50 72 28 44 28 28 50 1[28 44 50 44 50 50 11[72 11[33 5[66 61 1[92 17[25 1[25 44[{TeXBase1Encoding ReEncodeFont}31 99.6264 /Times-Italic rf /Fv 134[50 1[72 4[33 2[50 50 78 28 50 1[28 50 50 1[44 50 44 1[44 6[61 1[72 10[89 61 1[39 33 3[61 1[66 66 72 18[25 1[25 44[{TeXBase1Encoding ReEncodeFont}27 99.6264 /Times-Roman rf /Fw 138[66 1[47 53 2[60 66 1[33 2[33 1[60 1[53 1[53 1[60 11[86 80 13[73 1[86 68[{ TeXBase1Encoding ReEncodeFont}15 119.552 /Times-Bold rf end %%EndProlog %%BeginSetup %%Feature: *Resolution 600dpi TeXDict begin %%PaperSize: A4 %%EndSetup %%Page: 1 1 1 0 bop Black Black Black Black Black 892 374 a Fw(F)m(ailur)n(e)31 b(Diagnosis)e(Using)h(Decision)h(T)-9 b(r)n(ees)456 690 y Fv(Mik)o(e)24 b(Chen,)h(Alice)g(X.)g(Zheng,)f(Jim)g(Llo)o(yd,)g (Michael)g(I.)h(Jordan,)g(Eric)f(Bre)n(wer)878 806 y Fu(Univer)o(sity)g(of)h(California)e(at)h(Berk)o(ele)m(y)h(and)g(eBay)g (Inc.)474 922 y({mik)o(ec)o(hen,)f(alicez,)g(jor)l(dan,)g(br)l(e)o (wer}@cs.berk)o(ele)m(y)-5 b(.edu,)24 b(jlloyd@ebay)-5 b(.com)p Black 617 1240 a Ft(Abstract)-83 1445 y Fs(W)d(e)18 b(pr)m(esent)e(a)h(decision)e(tr)m(ee)i(learning)f(appr)l(oac)o(h)e(to) j(dia)o(gnos-)-182 1545 y(ing)j(failur)m(es)h(in)g(lar)m(g)o(e)g (Internet)f(sites.)i(W)-8 b(e)21 b(r)m(ecor)m(d)g(runtime)g(pr)l(op-) -182 1644 y(erties)i(of)f(eac)o(h)f(r)m(equest)h(and)f(apply)g (automated)f(mac)o(hine)g(learn-)-182 1744 y(ing)33 b(and)f(data)h (mining)f(tec)o(hniques)g(to)h(identify)g(the)h(causes)f(of)-182 1844 y(failur)m(es.)24 b(W)-8 b(e)25 b(tr)o(ain)f(decision)f(tr)m(ees)j (on)d(the)i(r)m(equest)f(tr)o(aces)g(fr)l(om)-182 1943 y(time)15 b(periods)g(in)h(whic)o(h)f(user)n(-visible)g(failur)m(es)h (ar)m(e)f(pr)m(esent.)g(P)-7 b(aths)-182 2043 y(thr)l(ough)15 b(the)h(tr)m(ee)h(ar)m(e)g(r)o(ank)o(ed)e(accor)m(ding)g(to)i(their)g (de)m(gr)m(ee)e(of)i(cor)n(-)-182 2142 y(r)m(elation)f(with)h(failur)m (e)o(,)g(and)f(nodes)g(ar)m(e)h(mer)m(g)o(ed)g(accor)m(ding)e(to)i(the) -182 2242 y(observed)24 b(partial)h(or)m(der)g(of)g(system)h (components.)d(W)-8 b(e)26 b(e)o(valuate)-182 2342 y(this)18 b(appr)l(oac)o(h)d(using)i(actual)g(failur)m(es)h(fr)l(om)g(eBay)-5 b(,)17 b(and)g(\002nd)f(that,)-182 2441 y(among)g(hundr)m(eds)g(of)j (potential)d(causes,)i(the)g(algorithm)f(success-)-182 2541 y(fully)g(identi\002es)f(13)h(out)g(of)g(14)g(true)g(causes)g(of)h (failur)m(e)o(,)e(along)g(with)-182 2641 y(2)25 b(false)h(positives.)f (W)-8 b(e)27 b(discuss)e(some)h(r)m(esults)g(in)g(applying)d(sim-)-182 2740 y(pli\002ed)h(decision)h(tr)m(ees)i(on)e(eBay')m(s)g(pr)l (oduction)f(site)j(for)f(se)o(ver)o(al)-182 2840 y(months.)18 b(In)h(addition,)f(we)i(give)f(a)h(cost-bene\002t)d(analysis)i(of)h (man-)-182 2940 y(ual)i(vs.)h(automated)e(dia)o(gnosis)h(systems.)i (Our)f(contrib)n(utions)e(in-)-182 3039 y(clude)30 b(the)i(statistical) g(learning)e(appr)l(oac)o(h,)f(the)i(adaptation)e(of)-182 3139 y(decision)16 b(tr)m(ees)i(to)f(the)g(conte)n(xt)g(of)g(failur)m (e)g(dia)o(gnosis,)f(and)g(the)h(de-)-182 3238 y(ployment)g(and)g(e)o (valuation)g(of)h(our)g(tools)h(on)f(a)g(high-volume)e(pr)l(o-)-182 3338 y(duction)i(service)o(.)-182 3689 y Ft(1.)69 b(Intr)n(oduction)-83 3924 y Fr(F)o(ast)28 b(reco)o(v)o(ery)d(remains)i(one)g(of)g(the)h(k)o (e)o(y)e(challenges)h(to)g(de-)-182 4024 y(signers)i(and)g(operators)g (of)g(lar)o(ge)g(netw)o(ork)o(ed)f(systems.)i(Before)-182 4123 y(reco)o(v)o(ery)19 b(can)j(tak)o(e)h(place,)f(ho)n(we)n(v)o(er)m (,)d(one)j(must)g(\002rst)h(detect)f(and)-182 4223 y(diagnose)27 b(the)h(f)o(ailure.)f(W)-7 b(e)30 b(de\002ne)d(f)o(ailure)h Fs(detection)f Fr(to)i(be)f(the)-182 4322 y(task)j(of)g(determining)e (when)i(a)h(system)f(is)h(e)o(xperiencing)d(prob-)-182 4422 y(lems.)35 b(F)o(ailure)h Fs(dia)o(gnosis)p Fr(,)e(then,)h(is)i (the)f(task)g(of)f(locating)g(the)-182 4522 y(source)27 b(of)h(a)h(system)f(f)o(ault)h(once)e(it)i(is)g(detected.)f(In)g(this)h (paper)m(,)-182 4621 y(we)24 b(assume)g(that)g(f)o(ailures)f(ha)n(v)o (e)h(been)f(detected)g(within)h(the)g(sys-)-182 4721 y(tem,)c(and)g(concentrate)e(on)i(the)h(subsequent)e(problem)g(of)h (diagno-)-182 4821 y(sis.)-83 4926 y(In)k(a)g(lar)o(ge)f(scale)h (Internet)e(system,)i(there)f(are)h(man)o(y)f(compo-)-182 5026 y(nents)29 b(at)h(w)o(ork)f(during)f(the)h(lifetime)g(of)h(a)f (request.)g(F)o(or)g(e)o(xam-)-182 5126 y(ple,)d(a)h(f)o(ailed)f (database)g(query)f(could)h(be)g(caused)g(by)g(a)h(miscon-)-182 5225 y(\002gured)19 b(application)f(serv)o(er)m(,)h(a)i(b)n(ug)e(in)i (a)f(ne)n(w)g(v)o(ersion)f(of)h(the)g(ap-)-182 5325 y(plication,)30 b(a)h(netw)o(ork)f(problem,)g(a)h(bad)g(disk)g(on)g(the)h(database)p Black Black 1974 1240 a(serv)o(er)m(,)24 b(or)i(a)g(combination)d(of)i (these)h(errors)f(and)g(more.)g(As)i(net-)1974 1339 y(w)o(ork)o(ed)j (systems)h(gro)n(w)f(in)h(size)h(and)e(comple)o(xity)-5 b(,)28 b(it)k(becomes)1974 1439 y(increasingly)23 b(impractical)h(to)h (e)o(xamine)f(each)h(component)d(man-)1974 1538 y(ually)31 b(for)h(sources)f(of)h(error)-5 b(.)31 b(Manual)g(diagnosis)g(is)i (time)f(con-)1974 1638 y(suming,)21 b(error)n(-prone,)d(requires)j (much)g(e)o(xpertise,)g(and)g(does)g(not)1974 1738 y(scale.)16 b(An)h(automated)e(approach)f(is)j(essential)g(if)f(we)h(w)o(ant)g(to)f (con-)1974 1837 y(tinue)25 b(at)i(the)f(current)e(gro)n(wth)h(rate)h (and)f(impro)o(v)o(e)f(system)i(a)n(v)n(ail-)1974 1937 y(ability)-5 b(.)2073 2040 y(Man)o(y)33 b(systems)h(today)e(record)g (requests)h(with)h(simple)f(run-)1974 2140 y(time)28 b(properties)f(for)h(monitoring)d(and)j(billing)g(purposes.)e(The)o(y) 1974 2239 y(typically)d(record)g(properties)f(such)i(as)h(the)f (timestamps,)g(request)1974 2339 y(types,)36 b(and)f(the)i(frontend)d (machines)h(servicing)g(the)i(requests.)1974 2439 y(Our)18 b(approach)e(uses)j(aggressi)n(v)o(e)e(logging)f(to)j(trace)f(request)f (paths)1974 2538 y(through)28 b(tiered)i(systems,)h(recording)d(the)j (system)f(components)1974 2638 y(and)37 b(databases)g(used)h(by)f(each) h(request)f([5)o(].)h(Using)f(machine)1974 2738 y(learning)15 b(algorithms,)f(we)i(le)n(v)o(erage)f(the)h(recorded)e(runtime)h(prop-) 1974 2837 y(erties)h(from)f(a)i(lar)o(ge)e(number)f(of)h(independent)f (requests)h(to)h(simul-)1974 2937 y(taneously)j(e)o(xamine)g(man)o(y)g (potential)g(causes.)2073 3040 y(The)40 b(follo)n(wing)e(observ)n (ation)f(from)i(systems)h(operation)d(is)1974 3140 y(crucial)23 b(in)g(designing)f(our)g(system:)i(the)f(e)o(xact)f(root)h(cause)g(of)g (er)n(-)1974 3239 y(ror)m(,)15 b(such)i(as)h(the)e(line)h(of)g(code)f (containing)f(a)i(b)n(ug,)f(is)i(often)e(not)g(re-)1974 3339 y(quired)24 b(for)g(reco)o(v)o(ery)f(to)i(tak)o(e)g(place.)g(The)g (operators)f(only)g(need)1974 3439 y(enough)16 b(con\002dence)g(in)i (the)h(diagnosis)e(to)h(apply)f(well-kno)n(wn)f(re-)1974 3538 y(co)o(v)o(ery)h(techniques)g(lik)o(e)j(reboot,)d(f)o(ailo)o(v)o (er)m(,)g(and)h(rollback.)g(Hence)1974 3638 y(these)i(are)g(the)h (goals)f(of)f(our)h(approach:)p Black 2057 3797 a Fq(\017)p Black 41 w Fp(High)i(diagnosis)h(rate.)e Fr(W)-7 b(e)24 b(need)e(to)g(be)h(able)f(to)h(localize)f(a)2140 3897 y(lar)o(ge)f(percentage)f(of)i(the)h(errors)e(in)h(order)f(to)i(garner) d(con\002-)2140 3997 y(dence)f(from)g(the)i(system)f(reco)o(v)o(ery)e (operator)-5 b(.)p Black 2057 4141 a Fq(\017)p Black 41 w Fp(F)n(ew)21 b(false)g(positi)o(v)o(es.)g Fr(F)o(alse)h(positi)n (v)o(es,)e(which)g(are)h(correct)2140 4240 y(beha)n(vior)j(of)h(the)g (system)h(that)f(are)h(mistak)o(en)f(for)f(an)i(error)m(,)2140 4340 y(are)c(costly)f(in)i(terms)e(of)h(time)g(w)o(asted)g(on)g(reco)o (v)o(ery)d(and)i(re-)2140 4439 y(diagnosis.)p Black 2057 4583 a Fq(\017)p Black 41 w Fp(Rob)n(ust)27 b(to)f(noise.)h Fr(Fe)n(w)g(systems)g(are)f(free)g(from)g(f)o(ailures.)2140 4683 y(It)c(is)h(common)d(to)i(\002nd)f(a)h(small)h(number)d(of)h(f)o (ailures)h(at)g(an)o(y)2140 4783 y(moment)f(on)i(a)g(lar)o(ge)f (system.)h(An)g(ideal)g(algorithm)e(should)2140 4882 y(be)j(able)g(to)h(\002lter)g(out)f(noise)g(and)g(prioritize)f(f)o (aults)i(that)f(are)2140 4982 y(impacting)19 b(the)h(a)n(v)n (ailability)g(of)f(a)i(system.)p Black 2057 5126 a Fq(\017)p Black 41 w Fp(Near)h(r)o(eal-time)g(tur)o(n-ar)o(ound.)f Fr(The)h(algorithm)g(needs)g(to)2140 5225 y(be)g(f)o(ast)h(enough)d(in) i(order)f(to)i(deri)n(v)o(e)d(bene\002ts)i(o)o(v)o(er)f(manual)2140 5325 y(approaches.)p Black Black eop %%Page: 2 2 2 1 bop Black Black -83 83 a Fr(In)32 b(this)h(paper)m(,)d(we)i (present)g(a)g(system)g(that)g(analyzes)g(read-)-182 183 y(ily)24 b(a)n(v)n(ailable)g(request)f(traces)h(in)g(order)f(to)h (automatically)f(locate)-182 282 y(sources)k(of)g(error)-5 b(.)27 b(W)-7 b(e)29 b(demonstrate)d(our)h(methods)f(at)i(w)o(ork)f(on) -182 382 y(eBay')-5 b(s)33 b(web)g(request)g(log)g(system,)g(and)g (analyze)f(ho)n(w)g(well)i(it)-182 482 y(achie)n(v)o(es)16 b(the)i(four)e(goals)h(stated)h(abo)o(v)o(e.)d(Being)j(one)f(of)g(the)g (lar)o(ger)-182 581 y(Internet)j(service)h(sites)i(in)e(e)o(xistence)g (today)-5 b(,)20 b(eBay)i(mak)o(es)f(for)g(an)-182 681 y(ideal)29 b(case)h(study;)f(successful)g(deplo)o(yment)e(on)i(the)h (eBay)g(sys-)-182 780 y(tem)20 b(may)g(ultimately)f(assure)h(success)h (on)f(smaller)g(sites)h(as)g(well.)-83 881 y(W)-7 b(e)27 b(start)e(of)n(f)g(by)g(describing)f(the)h(eBay)g(logging)f(frame)n(w)o (ork)-182 981 y(in)19 b(section)g(2,)g(follo)n(wed)f(by)h(a)h(detailed) f(e)o(xplanation)e(of)i(our)f(deci-)-182 1080 y(sion)k(tree)h(approach) e(in)i(section)f(3.)h(Section)g(4)f(describes)h(the)g(e)o(x-)-182 1180 y(perimental)c(setup,)h(and)g(section)g(5)g(presents)g(some)h (diagnosis)e(re-)-182 1280 y(sults.)28 b(W)-7 b(e)28 b(conclude)e(with)i(a)g(discussion)f(of)g(our)g(approach)e(and)-182 1379 y(possible)h(impro)o(v)o(ements)d(in)k(section)f(6,)g(plus)g(a)h (brief)e(surv)o(e)o(y)g(of)-182 1479 y(related)19 b(w)o(ork)h(in)g (section)g(7.)-182 1715 y Ft(2.)69 b(The)26 b(eBay)f(Inter)o(net)h(Ser) o(vice)g(System)-83 1934 y Fr(The)20 b(Centralized)f(Application)f (Logging)f(\(CAL\))j(frame)n(w)o(ork)-182 2034 y(at)37 b(eBay)g(is)h(a)g(central)e(repository)f(of)i(application-le)n(v)o(el)d (logs.)-182 2133 y(CAL)25 b(e)o(xports)e(an)h(API)h(that)f(enables)g (platform)f(and)g(application)-182 2233 y(de)n(v)o(elopers)k(to)j (record)e(information)f(associated)i(with)h(each)f(re-)-182 2333 y(quest.)d(CAL)i(is)g(the)f(foundation)e(for)h(se)n(v)o(eral)h(of) g(the)g(tools)g(used)-182 2432 y(by)17 b(the)h(operations)e(team)h(to)h (detect)g(and)f(diagnose)f(f)o(ailures.)h(CAL)-182 2532 y(is)25 b(also)g(used)g(by)f(de)n(v)o(elopers)f(for)h(deb)n(ugging)f (and)h(performance)-182 2632 y(tuning,)d(and)h(for)h(b)n (usiness-related)f(purposes)f(such)i(as)h(fraud)d(de-)-182 2731 y(tection)e(and)h(b)n(usiness)g(intelligence.)-83 2832 y(At)33 b(eBay)-5 b(,)31 b(both)g(the)h(application)e(serv)o(ers)i (and)f(the)h(applica-)-182 2932 y(tions)21 b(the)o(y)g(host)g(are)h (instrumented)e(to)h(log)g(to)h(CAL.)g(The)o(y)f(asyn-)-182 3031 y(chronously)15 b(write)i(information)e(about)i(each)g(request)g (to)g(the)h(Har)n(-)-182 3131 y(v)o(ester)33 b(cluster)g(o)o(v)o(er)f (persistent)h(TCP)h(connections.)e(The)h(Har)n(-)-182 3231 y(v)o(esters)17 b(are)g(responsible)f(for)g(writing)h(logs)g(to)g (persistent)g(storage.)-182 3330 y(The)o(y)e(also)h(publish)f(the)i (logs)f(in)g(real)g(time)g(onto)g(a)g(message)g(b)n(us)h(to)-182 3430 y(mak)o(e)25 b(the)h(information)e(a)n(v)n(ailable)i(to)g(v)n (arious)f(analysis)i(and)e(vi-)-182 3529 y(sualization)j(engines.)h (CAL)g(uses)h(load)f(balancing)f(switches)i(to)-182 3629 y(pro)o(vide)18 b(high)h(a)n(v)n(ailability)h(and)f(scalability)-5 b(.)-83 3730 y(The)17 b(CAL)h(API)g(requires)e(the)h(application)f(de)n (v)o(eloper)f(to)j(mark)-182 3829 y(the)j(start)g(and)g(the)g(end)g(of) g(a)g(request,)f(and)h(also)g(supply)f(the)i(name)-182 3929 y(and)c(the)h(status)h(code)e(of)h(a)g(request)g(\(i.e.)f(success) i(or)e(f)o(ailure\).)g(Ad-)-182 4029 y(ditional)c(information)f(such)j (as)g(v)o(ersion)e(number)m(,)f(host)j(name,)e(and)-182 4128 y(pool)22 b(name)g(are)g(automatically)g(recorded)e(by)j(the)f (platform.)f(Be-)-182 4228 y(cause)31 b(the)h(application)e(serv)o(ers) h(are)g(threaded,)f(the)h(intermedi-)-182 4328 y(ate)d(logs)g(between)f (the)h(start)h(and)e(the)h(end)g(mark)o(ers)f(can)h(be)g(as-)-182 4427 y(sociated)i(with)h(the)g(request)f(using)g(the)h(triplet)f({)p Fo(thread)49 b(ID)p Fr(,)-182 4527 y Fo(process)f(ID)p Fr(,)25 b Fo(host)49 b(ID)p Fr(}.)26 b(CAL)f(also)h(supports)e(nested)h (re-)-182 4626 y(quests.)d(F)o(or)g(e)o(xample,)e(an)i(HTTP)h(request)e (may)h(result)g(in)g(multi-)-182 4726 y(ple)j(database)g(accesses.)h (All)h(of)e(these)h(child)f(database)g(requests)-182 4826 y(are)20 b(automatically)e(associated)i(with)h(the)f(parent)f (request.)-83 4926 y(A)27 b(basic)g(request)f(trace)g(includes)g(the)g (request)g(type,)g(request)-182 5026 y(name,)h(host)h(name,)f(pool)g (name,)g(v)o(ersion,)g(timestamp,)g(and)h(the)-182 5126 y(status)i(of)g(the)g(requests.)f(Most)h(lar)o(ge)f(Internet)f (services)i(record)-182 5225 y(similar)37 b(information)e(for)i (monitoring)e(and)i(billing)f(purposes.)-182 5325 y(On)c(CAL,)g(this)h (basic)f(trace)g(can)g(be)g(e)o(xtended)e(to)i(include)f(the)p Black Black 1974 83 a(databases)j(accessed)h(by)f(each)g(request,)g (pro)o(viding)e(additional)1974 183 y(visibility)38 b(into)f(the)h (runtime)f(beha)n(vior)f(and)h(resource)g(depen-)1974 282 y(denc)o(y)19 b(of)h(each)f(request.)2073 396 y(The)h(CAL)h(system) f(currently)e(services)i(more)f(than)g(tw)o(o)h(thou-)1974 495 y(sand)f(application)g(serv)o(ers)g(at)h(more)f(than)g(one)g (billion)g(URLs/day)1974 595 y(and)i(a)h(peak)f(data)g(rate)h(of)f (200Mbps.)f(It)i(stores)g(1TB)f(of)h(ra)o(w)f(logs)1974 695 y(per)f(day)-5 b(,)19 b(or)h(150GB)f(gzipped.)1974 969 y Ft(3.)69 b(A)25 b(Decision)g(T)-7 b(r)n(ee)26 b(Lear)o(ning)f(A)n (ppr)n(oach)2073 1226 y Fr(There)31 b(are)g(man)o(y)g(possible)g (machine)f(learning)g(approaches)1974 1326 y(to)n(w)o(ard)f(f)o(ailure) g(diagnosis.)g(In)h(this)g(paper)m(,)f(we)h(treat)g(the)g(prob-)1974 1425 y(lem)i(as)h(one)f(of)g(\002nding)f(system)h(components)e(that)i (are)g(corre-)1974 1525 y(lated)17 b(with)h(f)o(ailure.)f(More)g (speci\002cally)-5 b(,)16 b(we)i(train)f(a)h(decision)f(tree)1974 1625 y(to)26 b(classify)g(the)g(f)o(ailed)g(and)g(successful)f (requests)h(that)g(occurred)1974 1724 y(during)15 b(the)i(f)o(aulty)f (period.)g(W)-7 b(e)18 b(then)e(post-process)f(the)i(paths)g(that)1974 1824 y(lead)30 b(to)g(f)o(ailure-predicting)c(nodes)k(and)f(e)o(xtract) g(rele)n(v)n(ant)g(com-)1974 1924 y(ponents.)d(While)j(decision)e (trees)i([3)o(])f(are)g(not)g(al)o(w)o(ays)g(the)g(most)1974 2023 y(competiti)n(v)o(e)16 b(classi\002ers)k(in)e(terms)g(of)g (prediction,)e(the)o(y)i(enjo)o(y)f(the)1974 2123 y(crucial)30 b(adv)n(antage)f(of)h(yielding)g(human-interpretable)c(results,)1974 2222 y(which)i(is)h(important)e(if)h(the)h(method)e(is)i(to)f(be)h (adopted)d(by)i(real)1974 2322 y(netw)o(ork)19 b(operators.)1974 2571 y Fn(3.1.)63 b(Lear)o(ning)20 b(Decision)i(T)-7 b(r)n(ees)2073 2820 y Fr(Here)25 b(is)h(what)f(a)g(decision)f(tree)h (might)f(look)g(lik)o(e)h(in)g(our)f(sys-)1974 2920 y(tem.)d(Suppose)e (there)i(are)g(tw)o(o)g(sources)f(of)h(error)m(,)e(one)h(associated) 1974 3020 y(with)28 b(machine)e Fo(x)p Fr(,)i(the)g(other)f(associated) h(with)g(request)f(type)g Fo(y)p Fr(.)1974 3119 y(Suppose)g(there)i (are)f Fm(15)h Fr(f)o(ailed)f(and)g Fm(5)h Fr(successful)g(requests)f (ob-)1974 3219 y(serv)o(ed)19 b(on)g(machine)g Fo(x)p Fr(,)h Fm(10)f Fr(f)o(ailed)g(and)h Fm(6)f Fr(successful)h(requests)f (of)1974 3319 y(type)24 b Fo(y)p Fr(,)g(and)f Fm(20)h Fr(other)f(successful)h(requests.)g(Figure)f(1)i(sho)n(ws)f(a)1974 3418 y(possible)17 b(decision)f(tree)h(learned)f(from)g(this)i(data.)e (Each)h(leaf)g(node)1974 3518 y(is)g(labeled)f(with)g(the)h(majority)e (v)n(ote)h(of)g(the)g(data)h(contained)d(at)j(that)1974 3617 y(node.)24 b(F)o(or)h(e)o(xample,)f(the)i(leftmost)f(path)g(of)g (\()p Fo(Machine)49 b(=)g(x)p Fr(\))1974 3717 y(results)31 b(in)g(a)h(leaf)f(node)f(predicting)f(f)o(ailure,)h(with)h(15)g (support-)1974 3817 y(ing)18 b(v)n(otes)h(\(i.e.,)f(f)o(ailures\))g (and)g(5)g(dissenting)g(v)n(otes)h(from)e(training)1974 3916 y(data.)k(By)i(e)o(xamining)c(the)j(paths)g(that)g(lead)f(to)h(f)o (ailure-predicting)1974 4016 y(leaf)i(nodes,)f(one)g(may)h(distinguish) e(the)i(possible)g(sources)f(of)h(er)n(-)1974 4116 y(ror)-5 b(.)2073 4229 y(Learning)18 b(a)i(decision)f(tree)g(in)m(v)n(olv)o(es)f (deciding)g(which)h(split)h(to)1974 4329 y(mak)o(e)28 b(at)h(each)f(node,)g(and)g(ho)n(w)g(deep)g(the)g(tree)h(should)f(be.)g (Let)1974 4428 y Fl(X)34 b Fr(denote)27 b(our)g(feature)f(v)o(ector)h (and)g Fl(y)k Fr(the)c(class)i(label.)e(F)o(or)g(bi-)1974 4528 y(nary)i(classi\002cation,)g Fl(y)44 b Fq(2)d(f)p Fm(0)p Fl(;)14 b Fm(1)p Fq(g)p Fr(,)28 b(where)h Fm(1)h Fr(denotes)f(a)h(f)o(ailure)1974 4628 y(and)21 b Fm(0)h Fr(success.)g(The)f(v)o(ector)g Fl(X)29 b Fr(may)21 b(includes)g (features)g(such)g(as)1974 4727 y(the)30 b(name)g(of)g(the)g(machine,)f (the)i(name)e(of)h(the)h(softw)o(are)f(b)n(uild)1974 4827 y(running)18 b(on)j(that)f(machine,)f(etc.)i(The)f(root)g(node)g (of)g(the)h(decision)1974 4926 y(tree)c(contains)f(all)h(of)f(the)h (data.)f(At)i(each)e(node,)f(the)i(dataset)g(is)h(split)1974 5026 y(according)j(to)j(the)f(v)n(alues)g(of)h(one)f(particular)f (feature.)g(Splits)i(are)1974 5126 y(pick)o(ed)g(to)i(maximize)e(the)h Fl(Gain)h Fr(in)f(information.)e(This)i(contin-)1974 5225 y(ues)k(until)g(no)g(further)e(split)j(is)g(possible,)f(or)g(the)g (node)f(contains)1974 5325 y(only)33 b(one)g(class.)h(After)g(the)g (tree)f(is)i(fully)e(gro)n(wn,)f(entire)i(sub-)p Black Black eop %%Page: 3 3 3 2 bop Black Black -182 28 1969 4 v Black Black Black -33 1261 a @beginspecial 0 @llx 0 @lly 263 @urx 189 @ury 1440 @rhi @setspecial %%BeginDocument: DTExample.eps %!PS-Adobe-2.0 EPSF-2.0 %%Title: DTExample.fig %%Creator: fig2dev Version 3.2 Patchlevel 4 %%CreationDate: Sun Mar 21 18:25:13 2004 %%For: alicez@alice.speakeasy.net (Alice Zheng) %%BoundingBox: 0 0 263 189 %%Magnification: 1.0000 %%EndComments /$F2psDict 200 dict def F2psDictbeginF2psDict begin F2psDictbeginF2psDict /mtrx matrix put /col-1 {0 setgray} bind def /col0 {0.000 0.000 0.000 srgb} bind def /col1 {0.000 0.000 1.000 srgb} bind def /col2 {0.000 1.000 0.000 srgb} bind def /col3 {0.000 1.000 1.000 srgb} bind def /col4 {1.000 0.000 0.000 srgb} bind def /col5 {1.000 0.000 1.000 srgb} bind def /col6 {1.000 1.000 0.000 srgb} bind def /col7 {1.000 1.000 1.000 srgb} bind def /col8 {0.000 0.000 0.560 srgb} bind def /col9 {0.000 0.000 0.690 srgb} bind def /col10 {0.000 0.000 0.820 srgb} bind def /col11 {0.530 0.810 1.000 srgb} bind def /col12 {0.000 0.560 0.000 srgb} bind def /col13 {0.000 0.690 0.000 srgb} bind def /col14 {0.000 0.820 0.000 srgb} bind def /col15 {0.000 0.560 0.560 srgb} bind def /col16 {0.000 0.690 0.690 srgb} bind def /col17 {0.000 0.820 0.820 srgb} bind def /col18 {0.560 0.000 0.000 srgb} bind def /col19 {0.690 0.000 0.000 srgb} bind def /col20 {0.820 0.000 0.000 srgb} bind def /col21 {0.560 0.000 0.560 srgb} bind def /col22 {0.690 0.000 0.690 srgb} bind def /col23 {0.820 0.000 0.820 srgb} bind def /col24 {0.500 0.190 0.000 srgb} bind def /col25 {0.630 0.250 0.000 srgb} bind def /col26 {0.750 0.380 0.000 srgb} bind def /col27 {1.000 0.500 0.500 srgb} bind def /col28 {1.000 0.630 0.630 srgb} bind def /col29 {1.000 0.750 0.750 srgb} bind def /col30 {1.000 0.880 0.880 srgb} bind def /col31 {1.000 0.840 0.000 srgb} bind def end save newpath 0 189 moveto 0 0 lineto 263 0 lineto 263 189 lineto closepath clip newpath -274.5 246.2 translate 1 -1 scale /cp {closepath} bind def /ef {eofill} bind def /gr {grestore} bind def /gs {gsave} bind def /sa {save} bind def /rs {restore} bind def /l {lineto} bind def /m {moveto} bind def /rm {rmoveto} bind def /n {newpath} bind def /s {stroke} bind def /sh {show} bind def /slc {setlinecap} bind def /slj {setlinejoin} bind def /slw {setlinewidth} bind def /srgb {setrgbcolor} bind def /rot {rotate} bind def /sc {scale} bind def /sd {setdash} bind def /ff {findfont} bind def /sf {setfont} bind def /scf {scalefont} bind def /sw {stringwidth} bind def /tr {translate} bind def /tnt {dup dup currentrgbcolor 4 -2 roll dup 1 exch sub 3 -1 roll mul add 4 -2 roll dup 1 exch sub 3 -1 roll mul add 4 -2 roll dup 1 exch sub 3 -1 roll mul add srgb} bind def /shd {dup dup currentrgbcolor 4 -2 roll mul 4 -2 roll mul 4 -2 roll mul srgb} bind def /DrawEllipse { /endangle exch def /startangle exch def /yrad exch def /xrad exch def /y exch def /x exch def /savematrix mtrx currentmatrix def x y tr xrad yrad sc 0 0 1 startangle endangle arc closepath savematrix setmatrix } def /$F2psBegin {$F2psDict begin /$F2psEnteredState save def} def /$F2psEnd {$F2psEnteredState restore end} def F2psBegin10setmiterlimit0slj0slc0.060000.06000scF2psBegin 10 setmiterlimit 0 slj 0 slc 0.06000 0.06000 sc % % Fig objects follow % % % here starts figure with depth 50 % Ellipse 7.500 slw n 6000 1200 237 237 0 360 DrawEllipse gs col0 s gr % Ellipse n 5100 2400 237 237 0 360 DrawEllipse gs col0 s gr % Ellipse n 6900 2400 237 237 0 360 DrawEllipse gs col0 s gr % Ellipse n 6000 3600 237 237 0 360 DrawEllipse gs col0 s gr % Ellipse n 7800 3600 237 237 0 360 DrawEllipse gs col0 s gr % Polyline n 5850 1425 m 5325 2250 l gs col0 s gr % Polyline n 6150 1425 m 6675 2250 l gs col0 s gr % Polyline n 6750 2625 m 6225 3450 l gs col0 s gr % Polyline n 7050 2625 m 7575 3450 l gs col0 s gr /Times-Roman ff 180.00 scf sf 5625 4050 m gs 1 -1 sc (Fail \(10/6\)) col0 sh gr /Times-Roman ff 180.00 scf sf 4575 1725 m gs 1 -1 sc (Machine = x) col0 sh gr /Times-Roman ff 180.00 scf sf 6450 1725 m gs 1 -1 sc (Machine != x) col0 sh gr /Times-Roman ff 180.00 scf sf 4725 2850 m gs 1 -1 sc (Fail \(15/5\)) col0 sh gr /Times-Roman ff 180.00 scf sf 7575 3150 m gs 1 -1 sc (RequestType != y) col0 sh gr /Times-Roman ff 180.00 scf sf 7275 4050 m gs 1 -1 sc (Success\(20/0\)) col0 sh gr /Times-Roman ff 180.00 scf sf 5025 3150 m gs 1 -1 sc (RequestType = y) col0 sh gr % here ends figure; F2psBegin10setmiterlimit0slj0slc0.060000.06000scF2psEnd rs showpage %%EndDocument @endspecial Black Black Black -83 1480 a Fk(Figure)30 b(1.)g(An)g(e)o(xample)f(decision)h(tree)g(f)n(or)g(dia)o(g-)-83 1579 y(nosis.)p -182 1692 V -182 1875 a Fr(branches)c(with)i(lo)n(w)g (o)o(v)o(erall)f Fl(Gain)h Fr(v)n(alue)f(are)h(pruned)e(back)i(in)-182 1975 y(order)19 b(to)h(a)n(v)n(oid)g(o)o(v)o(er\002tting.)686 1944 y Fj(1)-83 2074 y Fr(There)30 b(are)g(man)o(y)f(possible)g (de\002nitions)h(for)f(the)h Fl(Gain)h Fr(of)e(a)-182 2174 y(split.)34 b(It)f(is)i(generally)d(observ)o(ed)g(that)h(the)h (choice)f(of)g(splitting)-182 2274 y(criterion)27 b(does)h(not)g(af)n (fect)f(the)i(ultimate)f Fs(classi\002cation)f Fr(perfor)n(-)-182 2373 y(mance)33 b([3)o(].)h(Our)g(ultimate)g(goal,)g(ho)n(we)n(v)o(er)m (,)d(is)k(not)f(classi\002ca-)-182 2473 y(tion)18 b(b)n(ut)g(path)g (selection.)g(In)g(our)g(e)o(xperiments,)e(we)j(e)o(xamine)e(tw)o(o) -182 2572 y(dif)n(ferent)k(splitting)i(criteria,)f(and)h(the)g (selected)g(paths)f(do)h(indeed)-182 2672 y(sometimes)d(dif)n(fer)-5 b(.)-83 2772 y(The)27 b(popular)e(decision)h(tree)h(learning)f (algorithm)f Fs(C4.5)i Fr([17)o(])-182 2872 y(de\002nes)20 b(the)g Fl(Gain)g Fr(function)f(for)g(feature)g Fl(x)1117 2884 y Fi(i)1166 2872 y Fr(at)i(node)e Fl(t)i Fr(as:)261 3046 y Fl(Gain)p Fm(\()p Fl(x)528 3058 y Fi(i)556 3046 y Fl(;)14 b(t)p Fm(\))23 b(=)g Fl(H)7 b Fm(\()p Fl(t)p Fm(\))19 b Fq(\000)f Fl(H)7 b Fm(\()p Fl(x)1193 3058 y Fi(i)1221 3046 y Fl(;)14 b(t)p Fm(\))p Fl(;)-182 3221 y Fr(where)41 b Fl(H)7 b Fm(\()p Fl(t)p Fm(\))43 b Fr(denotes)e(the)h (binary)f(entrop)o(y)g(at)h(node)f Fl(t)p Fr(,)h(and)-182 3321 y Fl(H)7 b Fm(\()p Fl(x)-27 3333 y Fi(i)1 3321 y Fl(;)14 b(t)p Fm(\))32 b Fr(is)g(the)f(sum)g(of)g(entrop)o(y)f(of)h (child)f(nodes)h(after)g(mak-)-182 3420 y(ing)d(the)h(split)h(based)f (on)f(feature)g Fl(x)895 3432 y Fi(i)923 3420 y Fr(.)i(Entrop)o(y)d(is) j(one)e(of)h(man)o(y)-182 3520 y(possible)16 b(measures)g(of)h (\223pureness\224)e(of)i(the)f(distrib)n(ution)g(amongst)-182 3619 y(classes.)22 b(If)f Fl(Z)27 b Fr(is)22 b(a)f(discrete)g(random)f (v)n(ariable)g(and)g Fl(p)p Fm(\()p Fl(Z)6 b Fm(\))22 b Fr(its)g(dis-)-182 3719 y(trib)n(ution,)k(then)h(the)h(entrop)o(y)e (of)i Fl(Z)34 b Fr(is)28 b(de\002ned)f(as)h Fl(H)7 b Fm(\()p Fl(p)p Fm(\()p Fl(Z)f Fm(\)\))38 b(=)-182 3819 y Fq(\000)-103 3756 y Fh(P)-16 3844 y Fi(z)36 3819 y Fl(p)p Fm(\()p Fl(z)t Fm(\))14 b(log)f Fl(p)p Fm(\()p Fl(z)t Fm(\))p Fr(.)43 b(The)f(entrop)o(y)e(function)h(is)i(maximized) -182 3918 y(when)19 b(the)h(distrib)n(ution)f(is)i(uniform,)d(and)i (decreases)g(to)n(w)o(ard)f Fm(0)h Fr(as)-182 4018 y(the)i(distrib)n (ution)f(sk)o(e)n(ws)i(to)n(w)o(ard)e(certain)h(feature)f(v)n(alues.)g (Hence)-182 4118 y(a)f(smaller)g(entrop)o(y)f(indicates)h(lar)o(ger)f (sk)o(e)n(w)h(in)h(the)f(distrib)n(ution.)-83 4217 y(In)26 b(contrast)g(with)h Fs(C4.5)p Fr(,)e(our)h(implementation)e(at)j(eBay)f (cur)n(-)-182 4317 y(rently)33 b(deplo)o(ys)f(an)i(algorithm)e(that)i (we)g(call)g Fs(MinEntr)l(opy)p Fr(.)e(Its)-182 4417 y Fl(Gain)d Fr(function)f(is)i(based)f(on)g(the)g(entrop)o(y)f(of)h(a)h (dif)n(ferent)e(ran-)-182 4516 y(dom)c(v)n(ariable,)g(and,)h(due)g(to)h (time)f(and)g(resource)g(constraints,)f(it)-182 4616 y(only)e(follo)n(ws)g(the)h(path)g(that)g(is)h(the)f(most)g (\223suspicious.)-6 b(\224)23 b(Instead)-182 4716 y(of)18 b(pruning,)e(it)j(uses)g(an)g(early)f(stopping)f(criterion)g(and)h (stop)h(split-)-182 4815 y(ting)h(when)f(the)h Fl(Gain)h Fr(f)o(alls)g(belo)n(w)e(a)i(certain)e(threshold.)-83 4915 y(Suppose)d(feature)f Fl(x)510 4927 y Fi(i)555 4915 y Fr(has)i Fl(d)g Fr(possible)f(v)n(alues.)g(In)g(MinEntrop)o(y)-5 b(,)-182 5015 y(we)23 b(look)e(at)i(the)g(probability)d(that)j(a)g(f)o (ailed)f(request)g(at)h(a)g(particu-)p Black -182 5111 788 4 v Black -182 5220 a Fg(1)p Black 85 w(When)14 b(a)g(model)g (trades)h(of)n(f)f(performance)i(on)e(test)h(data)g(for)e(better)j (\002t)e(of)f(train-)-64 5294 y(ing)k(data,)h(it)g(is)e(said)i(to)f Ff(o)o(ver\002t)p Fg(.)p Black Black Black 1974 83 a Fr(lar)j(node)f Fl(t)i Fr(tak)o(es)g(on)e(a)i(particular)e(v)n(alue.) 2002 311 y Fl(P)12 b Fm(\()p Fl(x)2146 323 y Fi(i)2197 311 y Fm(=)23 b Fl(j)5 b Fm(;)14 b Fl(t)p Fm(\))23 b(=)2544 255 y Fr(#)d(of)g(f)o(ailed)g(requests)g(at)g(node)g Fl(t)g Fr(with)h Fl(x)3727 267 y Fi(i)3778 255 y Fm(=)h Fl(j)p 2544 292 1361 4 v 2751 368 a Fr(#)e(of)g(f)o(ailed)g(requests)g (at)g(node)f Fl(t)2366 469 y Fr(and)82 b Fl(Gain)p Fm(\()p Fl(x)2836 481 y Fi(i)2864 469 y Fl(;)14 b(t)p Fm(\))23 b(=)g Fq(\000)p Fl(H)7 b Fm(\()p Fl(P)12 b Fm(\()p Fl(x)3391 481 y Fi(i)3419 469 y Fm(;)i Fl(t)p Fm(\)\))1974 658 y Fl(P)e Fm(\()p Fl(x)2118 670 y Fi(i)2169 658 y Fm(=)23 b Fl(j)5 b Fm(;)14 b Fl(t)p Fm(\))19 b Fr(represents)f(a)h(multinomial) e(distrib)n(ution)g(o)o(v)o(er)h(v)n(al-)1974 757 y(ues)j(of)f Fl(x)2243 769 y Fi(i)2271 757 y Fr(.)h(This)g(method)e(mak)o(es)h(the)h (assumption)e(that,)i(for)f(each)1974 857 y(request)26 b(contained)f(in)i(node)f Fl(t)p Fr(,)h(determining)e(its)i(v)n(alue)f (for)h(fea-)1974 957 y(ture)21 b Fl(x)2172 969 y Fi(i)2223 957 y Fr(is)i(lik)o(e)f(tossing)g(a)h(d-sided)e(die)g(with)i(the)f (right)f(empirical)1974 1056 y(distrib)n(ution.)26 b(Our)g(goal)h(is)h (to)g(\002nd)f(the)g(particular)f(v)n(alue)g(of)h(the)1974 1156 y(feature)e(that)h(seems)h(to)f(be)g(correlated)e(with)j(an)f (unusually)e(high)1974 1256 y(number)15 b(of)h(f)o(ailures.)g(Thus)h (at)g(each)f(step,)h(we)g(split)g(the)g(tree)g(based)1974 1355 y(on)k(the)g(feature)g(with)g(the)h(lo)n(west)f(entrop)o(y)-5 b(,)20 b(and)g(follo)n(w)h(the)h(child)1974 1455 y(node)d Fl(j)26 b Fr(with)20 b(the)g(highest)g(f)o(ailure)f(probability)g(\()p Fl(P)12 b Fm(\()p Fl(x)3561 1467 y Fi(i)3612 1455 y Fm(=)22 b Fl(j)5 b Fm(;)14 b Fl(t)p Fm(\))p Fr(\).)1974 1684 y Fn(3.2.)63 b(F)n(ailur)n(e)22 b(Diagnosis)f(fr)n(om)i(Decision)f(T)-7 b(r)n(ee)22 b(Output)2073 1914 y Fr(Learning)17 b(the)h(decision)f (tree)h(is)h(only)e(half)h(the)g(battle.)g(W)-7 b(e)19 b(also)1974 2013 y(need)j(to)g(select)h(the)g(important)e(features)h (that)g(correlate)g(with)g(the)1974 2113 y(lar)o(gest)k(number)e(of)j (f)o(ailures.)f(W)-7 b(e)27 b(do)f(this)h(using)f(the)h(follo)n(wing) 1974 2213 y(four)19 b(heuristics:)p Black 2036 2398 a(1.)p Black 41 w(W)-7 b(e)26 b(ignore)f(the)g(leaf)g(nodes)g(corresponding)d (to)j(successful)2140 2498 y(requests.)k(Most)h(of)f(them)g(do)g(not)h (contain)e(an)o(y)h(f)o(ailed)g(re-)2140 2598 y(quests,)20 b(and)g(are)g(thus)g(useless)h(in)f(diagnosing)e(f)o(ailures.)p Black 2036 2752 a(2.)p Black 41 w Fs(Noise)k(F)l(iltering)p Fr(:)g(W)-7 b(e)23 b(ignore)d(lea)n(v)o(es)i(containing)e(less)j(than) 2140 2852 y Fl(c)p Fm(\045)c Fr(of)g(the)g(total)g(number)e(of)h(f)o (ailures.)h(This)f(corresponds)f(to)2140 2952 y(making)i(the)h (reasonable)f(assumptions)h(that)h(there)f(are)g(only)2140 3051 y(a)26 b(fe)n(w)f(independent)e(sources)i(of)g(error)m(,)f(and)g (each)h(of)h(them)2140 3151 y(accounts)16 b(for)h(a)g(lar)o(ge)f (fraction)g(of)h(the)g(total)h(number)d(of)i(f)o(ail-)2140 3250 y(ures.)p Black 2036 3405 a(3.)p Black 41 w Fs(Node)e(Mer)m(ging)p Fr(:)g(Before)g(reporting)e(the)i(\002nal)h(diagnosis,)e(we)2140 3505 y(mer)o(ge)24 b(nodes)h(on)g(a)h(path)f(by)g(eliminating)f (ancestor)h(nodes)2140 3604 y(that)c(are)g(logically)f (\223subsumed\224)f(by)i(successor)g(nodes.)f(F)o(or)2140 3704 y(e)o(xample,)27 b(if)h(machine)f Fo(x)i Fr(only)e(runs)h(softw)o (are)g(v)o(ersion)f Fo(y)p Fr(,)2140 3804 y(then)h(the)g(path)f Fo(\(Version=y)48 b(and)h(Machine=x\))27 b Fr(is)2140 3903 y(equi)n(v)n(alent)15 b(to)i Fo(\(Machine=x\))p Fr(.)e(This)i(kind)e(of)i(\223subsump-)2140 4003 y(tion\224)j(between)g (system)h(components)d(de\002nes)j(a)g(partial)f(or)n(-)2140 4102 y(der)25 b(on)g(our)g(features,)g(where)g(feature1)31 b Fq(\024)h Fr(feature2)24 b(if)n(f)i(all)2140 4202 y(requests)20 b(containing)e(feature1)h(also)h(contain)f(feature2.)p Black 2036 4357 a(4.)p Black 41 w Fs(Ranking)p Fr(:)14 b(W)-7 b(e)16 b(sort)f(the)h(predicted)e(causes)h(by)g(f)o(ailure)g (counts)2140 4456 y(to)20 b(prioritize)f(their)h(importance.)2073 4628 y(Applying)29 b(these)i(heuristics)g(to)g(the)g(e)o(xample)e (decision)h(tree)1974 4727 y(in)e(Figure)f(1,)h(the)g(right-most)e (leaf)i(node)f(w)o(ould)g(be)h(eliminated)1974 4827 y(in)h(step)h(1)f (because)f(it)i(does)f(not)g(contain)f(an)o(y)g(f)o(ailures.)h(In)g (step)1974 4926 y(2,)h(if)g(we)g(ha)n(v)o(e)f(a)h(noise)g(\002ltering)f (threshold)g(of)g(10\045,)h(then)f(the)1974 5026 y(remaining)24 b(leaf)i(nodes,)f(with)h(40\045)g(and)f(60\045)h(of)g(the)g(total)g(f)o (ail-)1974 5126 y(ures,)21 b(will)i(both)e(be)h(retained)f(as)h (candidates.)f(In)g(step)h(3,)g(we)g(pro-)1974 5225 y(duce)35 b(tw)o(o)h(predicted)e(sources)h(of)g(error:)g(\()p Fo(Machine=x)p Fr(\))f(and)1974 5325 y(\()p Fo(Machine!=x)47 b(and)j(RequestType=y)p Fr(\).)24 b(If)j(none)f(of)h(the)p Black Black eop %%Page: 4 4 4 3 bop Black Black -182 28 1969 4 v Black -93 65 1790 4 v -95 164 4 100 v -59 134 a Fe(Host)p 113 164 V 66 w(DB)p 283 164 V 66 w(Host,)19 b(Host)p 670 164 V 66 w(Host,)g(DB)p 1018 164 V 66 w(Host,)g(SW)p 1375 164 V 65 w(DB,)f(SW)p 1695 164 V -93 168 1790 4 v -93 184 V -95 284 4 100 v -8 254 a(2)p 113 284 V 152 w(4)p 283 284 V 242 w(1)p 670 284 V 330 w(1)p 1018 284 V 316 w(1)p 1375 284 V 301 w(1)p 1695 284 V -93 287 1790 4 v Black Black Black -83 454 a Fk(T)-7 b(ab)o(le)40 b(1.)g Fd(Summar)q(y)35 b(of)g(combinations)d(of)j(types)f(of)-83 554 y(faults)29 b(occurring)f(in)i(our)f(snapshots)e(of)j(the)g(request)-83 653 y(logs.)p -182 781 1969 4 v -182 933 V Black -135 970 1875 4 v -137 1069 4 100 v -102 1039 a Fe(T)-6 b(ype)p 77 1069 V 67 w(Name)p 322 1069 V 67 w(Pool)p 526 1069 V 66 w(Machine)p 853 1069 V 68 w(V)e(ersion)p 1148 1069 V 67 w(Database)p 1488 1069 V 67 w(Status)p 1737 1069 V -135 1073 1875 4 v -135 1089 V -137 1189 4 100 v -65 1159 a(10)p 77 1189 V 136 w(300)p 322 1189 V 132 w(15)p 526 1189 V 173 w(260)p 853 1189 V 238 w(7)p 1148 1189 V 261 w(40)p 1488 1189 V 240 w(8)p 1737 1189 V -135 1192 1875 4 v Black Black Black -83 1359 a Fk(T)h(ab)o(le)41 b(2.)f Fd(Names)35 b(of)h(f)o(eatures)e(and)h(the)g(n)o(umber)g(of)-83 1458 y(unique)18 b(v)o(alues)f(of)j(eac)o(h)e(f)o(eature)h(in)g(the)g (request)f(logs.)p -182 1586 1969 4 v -182 1768 a Fr(f)o(ailed)j (requests)g(with)h(with)f(request)g(type)g Fo(y)h Fr(is)h(e)o(x)o (ecuted)c(on)i(ma-)-182 1868 y(chine)28 b Fo(x)p Fr(,)i(then)e(the)i (machine)e(feature)g(is)i(subsumed)e(by)h(the)g(re-)-182 1968 y(quest)j(type)h(and)g(the)g(tw)o(o)g(nodes)f(mer)o(ge)g(into)h (one.)f(The)h(diag-)-182 2067 y(nosis)26 b(is)g(no)n(w)f(\()p Fo(Machine=x)p Fr(\))f(and)i(\()p Fo(RequestType=y)p Fr(\).)c(Fi-)-182 2167 y(nally)-5 b(,)18 b(in)h(Step)g(4,)g(the)g(tw)o (o)g(predicted)e(causes)j(are)f(rank)o(ed)e(by)i(f)o(ail-)-182 2266 y(ure)k(count;)g(\()p Fo(Machine=x)p Fr(\))g(causes)h(15)g(f)o (ailures,)f(which)h(places)-182 2366 y(it)d(before)d(\()p Fo(RequestType=y)p Fr(\))g(with)i(10)g(f)o(ailures.)-182 2598 y Ft(4.)69 b(Experimental)26 b(Setup)-182 2812 y Fn(4.1.)63 b(Data)22 b(Collection)-83 3019 y Fr(W)-7 b(e)35 b(ha)n(v)o(e)d(collected)h(10)g(most)g(recent)g(one-hour)d (snapshots)-182 3119 y(of)j(logs)h(that)f(are)h(kno)n(wn)e(to)i (contain)f(system)h(f)o(aults.)f(F)o(our)g(of)-182 3218 y(these)18 b(snapshots)f(ha)n(v)o(e)h(tw)o(o)g(independent)e(f)o(aults) i(each,)g(so)g(the)g(to-)-182 3318 y(tal)25 b(number)e(of)i(f)o(aults)g (is)h(14.)e(Of)h(these)g(14)g(f)o(aults,)g(6)g(are)f(single-)-182 3417 y(host)i(f)o(aults,)g(6)h(are)f(database)g(f)o(aults,)g(and)g(2)g (are)h(softw)o(are)e(b)n(ugs.)-182 3517 y(The)17 b(true)h(causes)g(of)g (the)g(problems)e(are)i(identi\002ed)g(by)f(e)o(xamining)-182 3617 y(post-mortems,)30 b(operations)i(chat)g(logs,)h(and)f (application)f(logs.)-182 3716 y(T)-7 b(able)20 b(1)g(contains)f(a)i (summary)e(of)h(dif)n(ferent)e(types)i(of)g(f)o(aults.)-83 3816 y(A)34 b(complete)e(request)g(trace)h(contains)f(a)h(basic)g (trace)g(and)f(a)-182 3916 y(database)21 b(path)g(trace.)g(The)h(basic) g(trace)f(contains)g(6)h(features:)f(re-)-182 4015 y(quest)f(type,)f (request)h(name,)f(pool,)g(host,)h(v)o(ersion,)f(and)h(the)g(status) -182 4115 y(of)28 b(each)g(request.)g(The)h(e)o(xtended)d(database)i (trace)h(contains)f(the)-182 4214 y(list)17 b(of)g(databases)f (accessed)g(by)h(each)f(request.)g(\(See)g(T)-7 b(able)17 b(2)g(for)e(a)-182 4314 y(summary)g(of)h(the)g(features.\))f(Each)h (hour)n(-long)e(snapshot)i(contains)-182 4414 y(complete)25 b(request)i(traces)g(from)f(a)h(\002x)o(ed)g(set)g(of)g(15)g(pools,)f (con-)-182 4513 y(strained)17 b(to)g(the)h(minutes)f(during)f(which)h (the)h(f)o(aults)g(are)g(kno)n(wn)e(to)-182 4613 y(be)24 b(present.)g(Each)g(of)g(these)g(one-minute)f(slices)i(contains)f (about)-182 4713 y(200,000)15 b(requests,)h(0.001\045-2\045)g(of)h (which)g(has)h(an)f(outcome)f(sta-)-182 4812 y(tus)k(of)g(f)o(ailure.) -182 5019 y Fn(4.2.)63 b(Implementation)-83 5225 y Fr(W)-7 b(e)20 b(ha)n(v)o(e)d(implemented)g(the)h(MinEntrop)o(y)e(algorithm)g (in)j(both)-182 5325 y(C++)i(and)g(Ja)n(v)n(a.)g(The)g(C++)g(v)o (ersion)f(currently)f(runs)i(on)g(the)g(eBay)p Black Black 1974 83 a(site)30 b(and)e(performs)g(automated)f(diagnosis)h(on)h (eBay')-5 b(s)29 b(produc-)1974 183 y(tion)20 b(site)h(in)f(less)h (than)f(10)g(seconds.)2073 297 y(W)-7 b(e)32 b(use)f(implementations)e (of)h(C4.5)g(and)g(association)g(rules)1974 396 y(from)d(the)i(machine) e(learning)g(tools)i(package)e(W)-7 b(eka)3614 366 y Fj(2)3676 396 y Fr([13)o(],)28 b(an)1974 496 y(open-source)33 b(machine)i(learning)g(package.)f(The)i(e)o(xperiments)1974 595 y(are)27 b(run)g(using)g(JDK)i(1.4.2)d(on)h(quad-PIII)e(2GHz)j (Linux)e(2.4.18)1974 695 y(machines)c(with)i(4GB)f(of)g(RAM.)h(The)f (algorithms)e(\002rst)j(load)f(the)1974 795 y(traces)d(into)g(memory)-5 b(,)18 b(then)i(compute)e(the)j(results.)1974 1070 y Ft(5.)69 b(Results)2073 1328 y Fr(W)-7 b(e)30 b(compare)c(the)j (decision)e(tree)h(approach)e(against)i(a)h(data-)1974 1428 y(mining)16 b(technique)g(kno)n(wn)g(as)i(\223association)f (rules\224)h([2)o(])f(that)h(sim-)1974 1528 y(ply)h(ranks)f(all)h (possible)g(combinations)e(of)i(features)f(according)f(to)1974 1627 y(their)j(observ)o(ed)e(probability)g(of)i(request)g(f)o(ailure.) 2073 1741 y(Each)26 b(algorithm)f(returns)h(a)h(set)g(of)f(candidates)g (\(i.e.,)f(combi-)1974 1841 y(nations)g(of)h(system)h(components\))d (that)i(are)g(deemed)f(to)h(be)h(cor)n(-)1974 1940 y(related)h(with)g (user)n(-visible)f(f)o(ailures.)h(T)-7 b(o)29 b(e)n(v)n(aluate)e(their) h(perfor)n(-)1974 2040 y(mance,)16 b(we)h(mak)o(e)f(use)h(of)f(the)h Fs(r)m(ecall)g Fr(and)f Fs(pr)m(ecision)g Fr(metrics.)h(Re-)1974 2140 y(call)24 b(measures)f(the)h(percentage)e(of)i(f)o(ailure)f (causes)h(that)g(are)g(cor)n(-)1974 2239 y(rectly)d(diagnosed)f(by)h (the)h(algorithm.)e(Precision)h(measures)h(ho)n(w)1974 2339 y(concise)e(the)g(candidate)f(set)i(is.)2073 2453 y(During)34 b(system)h(reco)o(v)o(ery)-5 b(,)32 b(each)j(e)o(xtra)f (component)e(in)j(the)1974 2552 y(candidate)41 b(may)i(incur)f(added)g (cost)h(to)g(the)g(reco)o(v)o(ery)e(ef)n(fort.)1974 2652 y(Hence)c(the)g(de\002nition)g(of)g(precision)f(needs)h(to)h(tak)o(e)f (into)g(ac-)1974 2752 y(count)24 b(not)g(only)h(the)g(number)e(of)h (candidates)g(retained,)g(b)n(ut)h(also)1974 2851 y(whether)c(the)i (list)g(of)g(components)d(in)i(each)h(candidate)e(is)i(as)g(suc-)1974 2951 y(cinct)33 b(as)g(can)g(be.)g(The)g(number)e(of)h Fs(false)i(positives)f Fr(contained)1974 3051 y(in)c(a)h(candidate)e (is)j(tak)o(en)d(to)i(be)f(the)h(number)d(of)i(e)o(xtra)g(compo-)1974 3150 y(nents)d(included)g(which)g(are)h(not)f(actual)h(sources)f(of)h (error)-5 b(.)26 b(Sup-)1974 3250 y(pose)36 b(the)g(candidate)e(is)j Fo(\(Machine=x)48 b(and)h(Version=n)1974 3349 y(and)g(RequestType=z\))p Fr(.)30 b(If)i(only)g(machine)f Fo(x)h Fr(is)i(at)e(f)o(ault,)1974 3449 y(then)18 b(the)g(candidate)f(contains)g(tw)o(o)h(f)o(alse)h (positi)n(v)o(es,)e(one)h(for)g(each)1974 3549 y(e)o(xtra)26 b(component.)e(If)i(the)h(f)o(ault)f(is)i(in)e(the)h(combination)d(of)j (ma-)1974 3648 y(chine)20 b Fo(x)h Fr(and)f(softw)o(are)h(v)o(ersion)e Fo(n)p Fr(,)i(then)f(the)h(only)f(f)o(alse)h(positi)n(v)o(e)1974 3748 y(is)g Fo(RequestType=z)p Fr(.)2073 3862 y(Let)h Fl(C)28 b Fr(denote)20 b(the)h(number)e(of)i(ef)n(fecti)n(v)o(e)f (components)f(in)i(the)1974 3961 y(candidate)26 b(set.)i(Let)g Fl(N)37 b Fr(be)28 b(number)e(of)h(distinct)h(causes)g(of)f(f)o(ail-) 1974 4061 y(ures,)16 b(and)g Fl(n)h Fr(the)f(number)f(of)h(correctly)f (identi\002ed)h(f)o(ailure)g(causes.)1974 4161 y(W)-7 b(e)21 b(de\002ne:)2556 4364 y Fl(R)q(ecal)r(l)83 b Fm(=)3044 4307 y Fl(n)p 3031 4344 76 4 v 3031 4420 a(N)2659 4547 y(f)9 b(pr)86 b Fm(=)3031 4490 y Fl(C)25 b Fq(\000)18 b Fl(n)p 3031 4528 217 4 v 3107 4604 a(C)2425 4709 y(P)12 b(r)r(ecision)83 b Fm(=)3039 4653 y Fl(n)p 3031 4690 66 4 v 3031 4766 a(C)3129 4709 y Fm(=)23 b(1)18 b Fq(\000)g Fl(f)9 b(pr)1974 4934 y Fr(Perfect)42 b(diagnosis)g(w)o(ould)g(ha)n(v)o (e)g(both)g(recall)h(and)f(precision)1974 5033 y(equal)19 b(to)i(1.)p Black 1974 5186 788 4 v Black 1974 5294 a Fg(2)p Black 85 w(W)-5 b(eka)17 b(implements)i(a)e(v)n(ariant)i(of)e (C4.5)g(called)i(J4.8.)p Black Black Black eop %%Page: 5 5 5 4 bop Black Black -182 28 1969 4 v Black Black Black -182 1640 a @beginspecial 42 @llx 187 @lly 547 @urx 592 @ury 2362 @rwi @setspecial %%BeginDocument: rp-no-db.eps %!PS-Adobe-2.0 EPSF-1.2 %%Creator: MATLAB, The Mathworks, Inc. %%Title: rp-no-db.eps %%CreationDate: 03/19/2004 23:47:11 %%DocumentNeededFonts: Helvetica %%DocumentProcessColors: Cyan Magenta Yellow Black %%Extensions: CMYK %%Pages: 1 %%BoundingBox: 42 187 547 592 %%EndComments %%BeginProlog % MathWorks dictionary /MathWorks 160 dict begin % definition operators /bdef {bind def} bind def /ldef {load def} bind def /xdef {exch def} bdef /xstore {exch store} bdef % operator abbreviations /c /clip ldef /cc /concat ldef /cp /closepath ldef /gr /grestore ldef /gs /gsave ldef /mt /moveto ldef /np /newpath ldef /cm /currentmatrix ldef /sm /setmatrix ldef /rm /rmoveto ldef /rl /rlineto ldef /s {show newpath} bdef /sc {setcmykcolor} bdef /sr /setrgbcolor ldef /sg /setgray ldef /w /setlinewidth ldef /j /setlinejoin ldef /cap /setlinecap ldef /rc {rectclip} bdef /rf {rectfill} bdef % page state control /pgsv () def /bpage {/pgsv save def} bdef /epage {pgsv restore} bdef /bplot /gsave ldef /eplot {stroke grestore} bdef % orientation switch /portraitMode 0 def /landscapeMode 1 def /rotateMode 2 def % coordinate system mappings /dpi2point 0 def % font control /FontSize 0 def /FMS {/FontSize xstore findfont [FontSize 0 0 FontSize neg 0 0] makefont setfont} bdef /reencode {exch dup where {pop load} {pop StandardEncoding} ifelse exch dup 3 1 roll findfont dup length dict begin { 1 index /FID ne {def}{pop pop} ifelse } forall /Encoding exch def currentdict end definefont pop} bdef /isroman {findfont /CharStrings get /Agrave known} bdef /FMSR {3 1 roll 1 index dup isroman {reencode} {pop pop} ifelse exch FMS} bdef /csm {1 dpi2point div -1 dpi2point div scale neg translate dup landscapeMode eq {pop -90 rotate} {rotateMode eq {90 rotate} if} ifelse} bdef % line types: solid, dotted, dashed, dotdash /SO { [] 0 setdash } bdef /DO { [.5 dpi2point mul 4 dpi2point mul] 0 setdash } bdef /DA { [6 dpi2point mul] 0 setdash } bdef /DD { [.5 dpi2point mul 4 dpi2point mul 6 dpi2point mul 4 dpi2point mul] 0 setdash } bdef % macros for lines and objects /L {lineto stroke} bdef /MP {3 1 roll moveto 1 sub {rlineto} repeat} bdef /AP {{rlineto} repeat} bdef /PDlw -1 def /W {/PDlw currentlinewidth def setlinewidth} def /PP {closepath eofill} bdef /DP {closepath stroke} bdef /MR {4 -2 roll moveto dup 0 exch rlineto exch 0 rlineto neg 0 exch rlineto closepath} bdef /FR {MR stroke} bdef /PR {MR fill} bdef /L1i {{currentfile picstr readhexstring pop} image} bdef /tMatrix matrix def /MakeOval {newpath tMatrix currentmatrix pop translate scale 0 0 1 0 360 arc tMatrix setmatrix} bdef /FO {MakeOval stroke} bdef /PO {MakeOval fill} bdef /PD {currentlinewidth 2 div 0 360 arc fill PDlw -1 eq not {PDlw w /PDlw -1 def} if} def /FA {newpath tMatrix currentmatrix pop translate scale 0 0 1 5 -2 roll arc tMatrix setmatrix stroke} bdef /PA {newpath tMatrix currentmatrix pop translate 0 0 moveto scale 0 0 1 5 -2 roll arc closepath tMatrix setmatrix fill} bdef /FAn {newpath tMatrix currentmatrix pop translate scale 0 0 1 5 -2 roll arcn tMatrix setmatrix stroke} bdef /PAn {newpath tMatrix currentmatrix pop translate 0 0 moveto scale 0 0 1 5 -2 roll arcn closepath tMatrix setmatrix fill} bdef /vradius 0 def /hradius 0 def /lry 0 def /lrx 0 def /uly 0 def /ulx 0 def /rad 0 def /MRR {/vradius xdef /hradius xdef /lry xdef /lrx xdef /uly xdef /ulx xdef newpath tMatrix currentmatrix pop ulx hradius add uly vradius add translate hradius vradius scale 0 0 1 180 270 arc tMatrix setmatrix lrx hradius sub uly vradius add translate hradius vradius scale 0 0 1 270 360 arc tMatrix setmatrix lrx hradius sub lry vradius sub translate hradius vradius scale 0 0 1 0 90 arc tMatrix setmatrix ulx hradius add lry vradius sub translate hradius vradius scale 0 0 1 90 180 arc tMatrix setmatrix closepath} bdef /FRR {MRR stroke } bdef /PRR {MRR fill } bdef /MlrRR {/lry xdef /lrx xdef /uly xdef /ulx xdef /rad lry uly sub 2 div def newpath tMatrix currentmatrix pop ulx rad add uly rad add translate rad rad scale 0 0 1 90 270 arc tMatrix setmatrix lrx rad sub lry rad sub translate rad rad scale 0 0 1 270 90 arc tMatrix setmatrix closepath} bdef /FlrRR {MlrRR stroke } bdef /PlrRR {MlrRR fill } bdef /MtbRR {/lry xdef /lrx xdef /uly xdef /ulx xdef /rad lrx ulx sub 2 div def newpath tMatrix currentmatrix pop ulx rad add uly rad add translate rad rad scale 0 0 1 180 360 arc tMatrix setmatrix lrx rad sub lry rad sub translate rad rad scale 0 0 1 0 180 arc tMatrix setmatrix closepath} bdef /FtbRR {MtbRR stroke } bdef /PtbRR {MtbRR fill } bdef /stri 6 array def /dtri 6 array def /smat 6 array def /dmat 6 array def /tmat1 6 array def /tmat2 6 array def /dif 3 array def /asub {/ind2 exch def /ind1 exch def dup dup ind1 get exch ind2 get sub exch } bdef /tri_to_matrix { 2 0 asub 3 1 asub 4 0 asub 5 1 asub dup 0 get exch 1 get 7 -1 roll astore } bdef /compute_transform { dmat dtri tri_to_matrix tmat1 invertmatrix smat stri tri_to_matrix tmat2 concatmatrix } bdef /ds {stri astore pop} bdef /dt {dtri astore pop} bdef /db {2 copy /cols xdef /rows xdef mul dup 3 mul string currentfile exch readhexstring pop dup 0 3 index getinterval /rbmap xdef dup 2 index dup getinterval /gbmap xdef 1 index dup 2 mul exch getinterval /bbmap xdef pop pop}bdef /it {gs np dtri aload pop moveto lineto lineto cp c cols rows 8 compute_transform rbmap gbmap bbmap true 3 colorimage gr}bdef /il {newpath moveto lineto stroke}bdef currentdict end def %%EndProlog %%BeginSetup MathWorks begin 0 cap end %%EndSetup %%Page: 1 1 %%BeginPageSetup %%PageBoundingBox: 42 187 547 592 MathWorks begin bpage %%EndPageSetup %%BeginObject: obj1 bplot /dpi2point 12 def portraitMode 0216 7344 csm 297 231 6060 4860 MR c np 93 dict begin %Colortable dictionary /c0 { 0 0 0 sr} bdef /c1 { 1 1 1 sr} bdef /c2 { 1 0 0 sr} bdef /c3 { 0 1 0 sr} bdef /c4 { 0 0 1 sr} bdef /c5 { 1 1 0 sr} bdef /c6 { 1 0 1 sr} bdef /c7 { 0 1 1 sr} bdef c0 1 j 1 sg 0 0 6913 5186 PR 6 w 0 4226 5356 0 0 -4226 899 4615 4 MP PP -5356 0 0 4226 5356 0 0 -4226 899 4615 5 MP stroke 4 w DO 0 sg 899 4615 mt 6255 4615 L 6255 4615 mt 6255 4615 L 899 4192 mt 6255 4192 L 6255 4192 mt 6255 4192 L 899 3769 mt 6255 3769 L 6255 3769 mt 6255 3769 L 899 3347 mt 6255 3347 L 6255 3347 mt 6255 3347 L 899 2924 mt 6255 2924 L 6255 2924 mt 6255 2924 L 899 2502 mt 6255 2502 L 6255 2502 mt 6255 2502 L 899 2079 mt 6255 2079 L 6255 2079 mt 6255 2079 L 899 1656 mt 6255 1656 L 6255 1656 mt 6255 1656 L 899 1234 mt 6255 1234 L 6255 1234 mt 6255 1234 L 899 811 mt 6255 811 L 6255 811 mt 6255 811 L 899 389 mt 6255 389 L 6255 389 mt 6255 389 L SO 6 w 899 4615 mt 6255 4615 L 899 389 mt 6255 389 L 899 4615 mt 899 389 L 6255 4615 mt 6255 389 L 899 4615 mt 6255 4615 L 899 4615 mt 899 389 L 899 4615 mt 899 4561 L 899 389 mt 899 442 L %%IncludeResource: font Helvetica /Helvetica /ISOLatin1Encoding 192 FMSR 846 4827 mt (0) s 1970 4615 mt 1970 4561 L 1970 389 mt 1970 442 L 1837 4827 mt (0.2) s 3041 4615 mt 3041 4561 L 3041 389 mt 3041 442 L 2908 4827 mt (0.4) s 4112 4615 mt 4112 4561 L 4112 389 mt 4112 442 L 3979 4827 mt (0.6) s 5183 4615 mt 5183 4561 L 5183 389 mt 5183 442 L 5050 4827 mt (0.8) s 6255 4615 mt 6255 4561 L 6255 389 mt 6255 442 L 6202 4827 mt (1) s 899 4615 mt 952 4615 L 6255 4615 mt 6201 4615 L 758 4686 mt (0) s 899 4192 mt 952 4192 L 6255 4192 mt 6201 4192 L 598 4263 mt (0.1) s 899 3769 mt 952 3769 L 6255 3769 mt 6201 3769 L 598 3840 mt (0.2) s 899 3347 mt 952 3347 L 6255 3347 mt 6201 3347 L 598 3418 mt (0.3) s 899 2924 mt 952 2924 L 6255 2924 mt 6201 2924 L 598 2995 mt (0.4) s 899 2502 mt 952 2502 L 6255 2502 mt 6201 2502 L 598 2573 mt (0.5) s 899 2079 mt 952 2079 L 6255 2079 mt 6201 2079 L 598 2150 mt (0.6) s 899 1656 mt 952 1656 L 6255 1656 mt 6201 1656 L 598 1727 mt (0.7) s 899 1234 mt 952 1234 L 6255 1234 mt 6201 1234 L 598 1305 mt (0.8) s 899 811 mt 952 811 L 6255 811 mt 6201 811 L 598 882 mt (0.9) s 899 389 mt 952 389 L 6255 389 mt 6201 389 L 758 460 mt (1) s 899 4615 mt 6255 4615 L 899 389 mt 6255 389 L 899 4615 mt 899 389 L 6255 4615 mt 6255 389 L gs 899 389 5357 4227 MR c np 36 w /c8 { 0.000000 0.000000 1.000000 sr} bdef c8 765 89 765 905 765 0 3577 389 4 MP stroke gr 36 w c8 0 j 36 47 -36 47 -36 -47 36 -47 3577 436 5 MP DP 36 47 -36 47 -36 -47 36 -47 4342 436 5 MP DP 36 47 -36 47 -36 -47 36 -47 5107 1341 5 MP DP 36 47 -36 47 -36 -47 36 -47 5872 1430 5 MP DP gs 899 389 5357 4227 MR c np gr -41 71 -41 -71 82 0 4683 1388 4 MP /c9 { 0.000000 1.000000 0.000000 sr} bdef c9 DP gs 899 389 5357 4227 MR c np DA /c10 { 1.000000 0.000000 1.000000 sr} bdef c10 1071 -140 1071 669 3577 1973 3 MP stroke gr c10 DA SO 0 -58 -58 0 0 58 58 0 3548 1944 5 MP DP 0 -58 -58 0 0 58 58 0 4619 2613 5 MP DP 0 -58 -58 0 0 58 58 0 5690 2473 5 MP DP DA gs 899 389 5357 4227 MR c np gr 0 sg 3311 5023 mt (Recall) s 500 2896 mt -90 rotate (Precision) s 90 rotate SO 6 w 1 sg 0 699 2160 0 0 -699 959 4555 4 MP PP -2160 0 0 699 2160 0 0 -699 959 4555 5 MP stroke 4 w DO SO 6 w 0 sg 959 4555 mt 3119 4555 L 959 3856 mt 3119 3856 L 959 4555 mt 959 3856 L 3119 4555 mt 3119 3856 L 959 4555 mt 3119 4555 L 959 4555 mt 959 3856 L 959 4555 mt 3119 4555 L 959 3856 mt 3119 3856 L 959 4555 mt 959 3856 L 3119 4555 mt 3119 3856 L 1492 4052 mt (C4.5) s 1492 4273 mt (MinEntropy) s 1492 4494 mt (Association Rules) s gs 959 3856 2161 700 MR c np 36 w c8 320 0 1065 3987 2 MP stroke gs 1115 3877 221 221 MR c np 36 47 -36 47 -36 -47 36 -47 1225 4034 5 MP DP gr gs 1115 4098 221 221 MR c np -41 71 -41 -71 82 0 1184 4232 4 MP c9 DP gr c9 DA c10 320 0 1065 4430 2 MP stroke SO gs 1115 4320 221 221 MR c np 0 -58 -58 0 0 58 58 0 1196 4401 5 MP DP gr 6 w gr c10 end eplot %%EndObject epage end showpage %%Trailer %%EOF %%EndDocument @endspecial Black Black Black -83 1859 a Fk(Figure)22 b(2.)g(Precision-recall)i(cur)q(ves)e(f)n(or)g(C4.5,)h(Mi-)-83 1958 y(nEntr)n(op)o(y)-7 b(,)23 b(and)g(association)g(rules.)p -182 2087 V -182 2289 a Fn(5.1.)63 b(Results)21 b(on)i(Basic)f(Request) f(T)-7 b(races)-83 2516 y Fr(The)26 b(basic)g(type)g(of)f(request)h (trace)g(is)g(common)f(to)h(man)o(y)f(In-)-182 2616 y(ternet)16 b(services)g(for)g(performance)d(monitoring,)h(f)o(ailure)h(monitor)n (-)-182 2715 y(ing,)21 b(and)g(billing.)g(It)h(does)f(not)g(contain)g (an)o(y)g(database)g(access)h(in-)-182 2815 y(formation.)c(In)j(a)h (basic)f(trace,)g(a)g(database)g(f)o(ault)g(w)o(ould)f(manifest)-182 2914 y(itself)g(in)h(what)f(appears)f(to)i(be)f(man)o(y)f(minor)g(f)o (ailures.)-83 3021 y(In)32 b(our)f(dataset,)h(6)g(out)g(of)f(14)h(f)o (aults)g(are)g(database-related.)-182 3120 y(\(See)i(T)-7 b(able)33 b(1)h(for)f(a)i(summary)d(of)i(the)g(types)f(of)h(f)o (aults.\))f(The)-182 3220 y(ground)d(truth)h(cause)i(for)e(each)h (database)g(f)o(ault)g(is)i(tak)o(en)d(to)i(be)-182 3319 y(the)24 b(name)h(of)f(the)h(request)f(that)h(accesses)g(the)g (database)f(and)h(has)-182 3419 y(the)34 b(most)g(number)e(of)h(f)o (ailures.)h(F)o(or)f(e)o(xample,)g(a)h(f)o(ault)g(in)g(the)-182 3519 y(feedback)23 b(database)i(is)h(translated)e(into)h(a)h(softw)o (are)f(f)o(ault)g(of)g(the)-182 3618 y(request)37 b(name)g(V)-5 b(ie)n(wFeedback.)36 b(Prediction)h(of)g(other)g(related)-182 3718 y(symptoms)26 b(is)i(counted)d(neither)h(as)i(a)g(correct)e (diagnosis)g(nor)g(as)-182 3818 y(a)18 b(f)o(alse)h(positi)n(v)o(e,)e (and)h(therefore)e(has)j(no)f(ef)n(fect)f(on)h(precision)f(and)-182 3917 y(recall.)-83 4023 y(Figure)24 b(2)g(sho)n(ws)g(the)h (precision-recall)d(curv)o(es)h(of)h(C4.5,)g(Mi-)-182 4123 y(nEntrop)o(y)-5 b(,)19 b(and)j(association)h(rules)f(on)g(the)h (basic)g(request)f(traces.)-182 4223 y(The)f(curv)o(es)f(are)i (obtained)e(by)h(v)n(arying)f(the)h(cutof)n(f)f(threshold)h(for)-182 4322 y(the)27 b(number)e(of)i(retained)f(candidates.)g(At)i(a)f(f)o (ailure)g(rate)g(cutof)n(f)-182 4422 y(of)22 b Fm(50\045)p Fr(,)g(C4.5)g(returns)g(se)n(v)o(en)g(candidate)f(components)g(o)o(v)o (er)g(ten)-182 4521 y(snapshots.)i(This)i(gi)n(v)o(es)f(us)h(a)g (precision)f(of)g Fm(100\045)g Fr(at)i(a)f(recall)f(of)-182 4621 y Fm(50\045)p Fr(.)30 b(As)h(we)g(lo)n(wer)f(the)h(cutof)n(f)e (threshold,)g(the)i(candidate)e(set)-182 4721 y(gro)n(ws:)22 b(17)h(candidate)e(components)g(are)i(retained)f(at)h(a)h(cutof)n(f)d (of)-182 4820 y Fm(5\045)p Fr(,)f(bringing)e(us)i(to)h Fm(93\045)f Fr(recall)g(and)g Fm(76\045)g Fr(precision.)-83 4926 y(Since)35 b(MinEntrop)o(y)c(al)o(w)o(ays)k(produces)e(one)g(and)h (only)f(one)-182 5026 y(prediction,)38 b(it)j(is)g(a)f(\002x)o(ed)g (point)f(in)i(this)f(graph.)f(Out)h(of)g(the)-182 5126 y(13)26 b(components)f(returned)g(by)i(MinEntrop)o(y)-5 b(,)23 b(it)28 b(correctly)e(iden-)-182 5225 y(tify)e(10)g(actual)h(f)o (aults)g(of)f(the)h(system)f(\(one)g(for)g(each)g(snapshot\).)-182 5325 y(Hence)e(its)j(precision)d(score)h(is)h Fm(76)p Fl(:)p Fm(92\045)e Fr(at)i Fm(71)p Fl(:)p Fm(43\045)e Fr(recall.)h(This)p Black Black 1974 83 a(precision)c(score)h(is)h (comparable)d(to)i(that)g(of)g(C4.5)g(at)h(the)f Fm(5\045)h Fr(cut-)1974 183 y(of)n(f)c(threshold,)f(though)f(its)k(recall)e(score) h(suf)n(fers)f(from)f(the)i(single-)1974 282 y(candidate)e(limitation)h (and)g(is)h(much)e(lo)n(wer)h(as)h(a)g(result.)f(Thus)g(Mi-)1974 382 y(nEntrop)o(y)22 b(pro)o(v)o(es)h(to)i(be)g(a)g(good)f(alternati)n (v)o(e)f(to)i(C4.5)f(when)g(re-)1974 482 y(sources)c(are)g(scarce.)2073 589 y(Both)i(C4.5)f(and)g(the)g(simpli\002ed)g(MinEntrop)o(y)e (approach)h(per)n(-)1974 689 y(forms)i(much)g(better)g(than)g (association)h(rules)g(at)g(all)g(le)n(v)o(els)g(of)f(re-)1974 788 y(call.)1974 1020 y Fn(5.2.)63 b(Experiments)21 b(on)h(Complete)g (T)-7 b(races)2073 1251 y Fr(Each)18 b(request)e(in)i(the)g(eBay)g (system)f(may)g(access)i(one)e(or)g(more)1974 1351 y(of)k(the)g(40)g (databases)g(multiple)f(times.)i(F)o(or)e(this)i(e)o(xperiment,)d(we) 1974 1451 y(include)29 b(database)g(access)i(information)d(in)i(the)g (request)f(traces.)1974 1550 y(Because)d(the)g(causes)g(of)f (database-related)f(f)o(ailures)h(are)h(no)n(w)f(in)1974 1650 y(the)32 b(trace,)g(we)g(e)o(xpect)f(the)i(algorithms)d(to)j (correctly)d(diagnose)1974 1750 y(snapshots)19 b(in)m(v)n(olving)g (database)g(f)o(aults.)2073 1857 y(Since)39 b(each)f(request)g(may)g (access)h(a)g(v)n(ariable)f(number)e(of)1974 1957 y(databases,)18 b(we)g(tak)o(e)g(each)g(database)g(to)g(be)g(a)h(binary)e(feature)g (with)1974 2056 y(the)j(v)n(alues)g(T)m(rue)f(or)h(F)o(alse.)2073 2164 y(T)-7 b(o)45 b(underscore)e(the)i(importance)d(of)j(noise)f (\002ltering)h(and)1974 2264 y(node)59 b(mer)o(ging,)e(we)j(compare)f (the)h(results)g(obtained)e(us-)1974 2363 y(ing)42 b(un-processed)f (C4.5)h(paths,)h(C4.5)f(with)h(noise)g(\002ltering,)1974 2463 y(and)29 b(C4.5)g(with)g(noise)g(\002ltering)g(and)g(node)f(mer)o (ging.)f(The)i(cut-)1974 2563 y(of)n(f)37 b(threshold)f(is)j(set)f(to)g (10\045)f(of)g(all)i(observ)o(ed)c(f)o(ailures)j(and)1974 2662 y(the)46 b(results)h(are)g(presented)e(in)i(Figure)e(3.)i(All)g (three)f(v)n(aria-)1974 2762 y(tions)g(of)g(the)g(algorithm)e (correctly)h(identify)g(13)g(out)h(of)g(14)1974 2861 y(true)k(f)o(ailures,)h(making)e(the)i(recall)g(rate)g(93\045.)f(In)g (particu-)1974 2961 y(lar)m(,)i(all)h(three)e(v)n(ariations)g (correctly)g(identify)g(all)i(the)g(true)1974 3061 y(causes)36 b(in)g(the)g(four)e(cases)j(that)f(ha)n(v)o(e)f(tw)o(o)h(independent)d (f)o(ail-)1974 3160 y(ures.)2073 3268 y(The)38 b(importance)e(of)i (post-processing)d(is)k(apparent)d(in)i(the)1974 3368 y(precision)21 b(scores.)h(Our)g(result-aggre)o(gation)d(heuristic)i (increases)1974 3467 y(precision)g(from)g(18\045)h(to)h(76\045.)f(This) g(means)g(that)h(the)f(f)o(alse)h(pos-)1974 3567 y(iti)n(v)o(e)g(rate)g (drops)g(from)f(82\045)h(to)h(24\045,)f(which)g(is)h(a)g(dramatic)e (im-)1974 3666 y(pro)o(v)o(ement.)g(These)i(statistics)i(suggest)f (that)g(more)f(than)g(58\045)g(of)1974 3766 y(components)h(in)i(the)g (ra)o(w)g(decision)f(tree)h(paths)g(are)g(e)o(xtraneous.)1974 3866 y(These)18 b(are)h(paths)f(that)h(contain)f(the)g(correct)g (sources)g(of)g(error)m(,)f(b)n(ut)1974 3965 y(also)23 b(contain)e(other)h(features)g(that)h(are)g(not)f(related)g(to)h(an)o (y)f(f)o(aults)1974 4065 y(\(cf.)i(the)g(sample)g(decision)g(tree)h (and)e(discussion)h(of)g(node)g(mer)o(g-)1974 4165 y(ing)17 b(in)g(Section)g(3\).)g(The)g(e)o(xtraneous)e(features)h(were)i (necessary)e(in)1974 4264 y(the)g(construction)e(of)i(the)g(decision)g (tree,)f(b)n(ut)i(are)f(useless)g(as)h(an)f(in-)1974 4364 y(dicator)22 b(of)g(error)-5 b(.)22 b(Hence)g(post-processing)f (of)h(the)h(decision)f(tree)1974 4463 y(paths)e(is)h(a)g(crucial)e (step.)1974 4695 y Fn(5.3.)63 b(Ho)o(w)22 b(Many)g(Candidates)g(to)h(K) n(eep?)2073 4926 y Fr(Our)g(post-processing)d(procedure)f(relies)k(on)f (a)h(cutof)n(f)e(thresh-)1974 5026 y(old)k(in)h(the)g(noise)g (\002ltering)f(step)i(\(c.f.)e(Section)g(3.2\).)g(The)g(cutof)n(f)1974 5126 y(threshold)16 b Fl(c)h Fr(is)h(based)f(on)g(the)g(percentage)e (of)i(request)f(f)o(ailures)h(ac-)1974 5225 y(counted)22 b(for)h(by)g(a)h(particular)e(path)h(in)g(the)h(decision)f(tree.)g(Let) h Fl(F)1974 5325 y Fr(be)g(the)g(total)h(number)d(of)i(f)o(ailed)g (requests)g(observ)o(ed)e(during)h(one)p Black Black eop %%Page: 6 6 6 5 bop Black Black -182 28 1969 4 v Black Black Black -182 1707 a @beginspecial 49 @llx 179 @lly 543 @urx 592 @ury 2362 @rwi @setspecial %%BeginDocument: rp-c45-db.eps %!PS-Adobe-2.0 EPSF-1.2 %%Creator: MATLAB, The Mathworks, Inc. %%Title: rp-c45-db.eps %%CreationDate: 03/19/2004 16:43:38 %%DocumentNeededFonts: Helvetica %%DocumentProcessColors: Cyan Magenta Yellow Black %%Extensions: CMYK %%Pages: 1 %%BoundingBox: 49 179 543 592 %%EndComments %%BeginProlog % MathWorks dictionary /MathWorks 160 dict begin % definition operators /bdef {bind def} bind def /ldef {load def} bind def /xdef {exch def} bdef /xstore {exch store} bdef % operator abbreviations /c /clip ldef /cc /concat ldef /cp /closepath ldef /gr /grestore ldef /gs /gsave ldef /mt /moveto ldef /np /newpath ldef /cm /currentmatrix ldef /sm /setmatrix ldef /rm /rmoveto ldef /rl /rlineto ldef /s {show newpath} bdef /sc {setcmykcolor} bdef /sr /setrgbcolor ldef /sg /setgray ldef /w /setlinewidth ldef /j /setlinejoin ldef /cap /setlinecap ldef /rc {rectclip} bdef /rf {rectfill} bdef % page state control /pgsv () def /bpage {/pgsv save def} bdef /epage {pgsv restore} bdef /bplot /gsave ldef /eplot {stroke grestore} bdef % orientation switch /portraitMode 0 def /landscapeMode 1 def /rotateMode 2 def % coordinate system mappings /dpi2point 0 def % font control /FontSize 0 def /FMS {/FontSize xstore findfont [FontSize 0 0 FontSize neg 0 0] makefont setfont} bdef /reencode {exch dup where {pop load} {pop StandardEncoding} ifelse exch dup 3 1 roll findfont dup length dict begin { 1 index /FID ne {def}{pop pop} ifelse } forall /Encoding exch def currentdict end definefont pop} bdef /isroman {findfont /CharStrings get /Agrave known} bdef /FMSR {3 1 roll 1 index dup isroman {reencode} {pop pop} ifelse exch FMS} bdef /csm {1 dpi2point div -1 dpi2point div scale neg translate dup landscapeMode eq {pop -90 rotate} {rotateMode eq {90 rotate} if} ifelse} bdef % line types: solid, dotted, dashed, dotdash /SO { [] 0 setdash } bdef /DO { [.5 dpi2point mul 4 dpi2point mul] 0 setdash } bdef /DA { [6 dpi2point mul] 0 setdash } bdef /DD { [.5 dpi2point mul 4 dpi2point mul 6 dpi2point mul 4 dpi2point mul] 0 setdash } bdef % macros for lines and objects /L {lineto stroke} bdef /MP {3 1 roll moveto 1 sub {rlineto} repeat} bdef /AP {{rlineto} repeat} bdef /PDlw -1 def /W {/PDlw currentlinewidth def setlinewidth} def /PP {closepath eofill} bdef /DP {closepath stroke} bdef /MR {4 -2 roll moveto dup 0 exch rlineto exch 0 rlineto neg 0 exch rlineto closepath} bdef /FR {MR stroke} bdef /PR {MR fill} bdef /L1i {{currentfile picstr readhexstring pop} image} bdef /tMatrix matrix def /MakeOval {newpath tMatrix currentmatrix pop translate scale 0 0 1 0 360 arc tMatrix setmatrix} bdef /FO {MakeOval stroke} bdef /PO {MakeOval fill} bdef /PD {currentlinewidth 2 div 0 360 arc fill PDlw -1 eq not {PDlw w /PDlw -1 def} if} def /FA {newpath tMatrix currentmatrix pop translate scale 0 0 1 5 -2 roll arc tMatrix setmatrix stroke} bdef /PA {newpath tMatrix currentmatrix pop translate 0 0 moveto scale 0 0 1 5 -2 roll arc closepath tMatrix setmatrix fill} bdef /FAn {newpath tMatrix currentmatrix pop translate scale 0 0 1 5 -2 roll arcn tMatrix setmatrix stroke} bdef /PAn {newpath tMatrix currentmatrix pop translate 0 0 moveto scale 0 0 1 5 -2 roll arcn closepath tMatrix setmatrix fill} bdef /vradius 0 def /hradius 0 def /lry 0 def /lrx 0 def /uly 0 def /ulx 0 def /rad 0 def /MRR {/vradius xdef /hradius xdef /lry xdef /lrx xdef /uly xdef /ulx xdef newpath tMatrix currentmatrix pop ulx hradius add uly vradius add translate hradius vradius scale 0 0 1 180 270 arc tMatrix setmatrix lrx hradius sub uly vradius add translate hradius vradius scale 0 0 1 270 360 arc tMatrix setmatrix lrx hradius sub lry vradius sub translate hradius vradius scale 0 0 1 0 90 arc tMatrix setmatrix ulx hradius add lry vradius sub translate hradius vradius scale 0 0 1 90 180 arc tMatrix setmatrix closepath} bdef /FRR {MRR stroke } bdef /PRR {MRR fill } bdef /MlrRR {/lry xdef /lrx xdef /uly xdef /ulx xdef /rad lry uly sub 2 div def newpath tMatrix currentmatrix pop ulx rad add uly rad add translate rad rad scale 0 0 1 90 270 arc tMatrix setmatrix lrx rad sub lry rad sub translate rad rad scale 0 0 1 270 90 arc tMatrix setmatrix closepath} bdef /FlrRR {MlrRR stroke } bdef /PlrRR {MlrRR fill } bdef /MtbRR {/lry xdef /lrx xdef /uly xdef /ulx xdef /rad lrx ulx sub 2 div def newpath tMatrix currentmatrix pop ulx rad add uly rad add translate rad rad scale 0 0 1 180 360 arc tMatrix setmatrix lrx rad sub lry rad sub translate rad rad scale 0 0 1 0 180 arc tMatrix setmatrix closepath} bdef /FtbRR {MtbRR stroke } bdef /PtbRR {MtbRR fill } bdef /stri 6 array def /dtri 6 array def /smat 6 array def /dmat 6 array def /tmat1 6 array def /tmat2 6 array def /dif 3 array def /asub {/ind2 exch def /ind1 exch def dup dup ind1 get exch ind2 get sub exch } bdef /tri_to_matrix { 2 0 asub 3 1 asub 4 0 asub 5 1 asub dup 0 get exch 1 get 7 -1 roll astore } bdef /compute_transform { dmat dtri tri_to_matrix tmat1 invertmatrix smat stri tri_to_matrix tmat2 concatmatrix } bdef /ds {stri astore pop} bdef /dt {dtri astore pop} bdef /db {2 copy /cols xdef /rows xdef mul dup 3 mul string currentfile exch readhexstring pop dup 0 3 index getinterval /rbmap xdef dup 2 index dup getinterval /gbmap xdef 1 index dup 2 mul exch getinterval /bbmap xdef pop pop}bdef /it {gs np dtri aload pop moveto lineto lineto cp c cols rows 8 compute_transform rbmap gbmap bbmap true 3 colorimage gr}bdef /il {newpath moveto lineto stroke}bdef currentdict end def %%EndProlog %%BeginSetup MathWorks begin 0 cap end %%EndSetup %%Page: 1 1 %%BeginPageSetup %%PageBoundingBox: 49 179 543 592 MathWorks begin bpage %%EndPageSetup %%BeginObject: obj1 bplot /dpi2point 12 def portraitMode 0216 7344 csm 374 234 5931 4951 MR c np 91 dict begin %Colortable dictionary /c0 { 0 0 0 sr} bdef /c1 { 1 1 1 sr} bdef /c2 { 1 0 0 sr} bdef /c3 { 0 1 0 sr} bdef /c4 { 0 0 1 sr} bdef /c5 { 1 1 0 sr} bdef /c6 { 1 0 1 sr} bdef /c7 { 0 1 1 sr} bdef c0 1 j 1 sg 0 0 6913 5186 PR 6 w 0 4226 5356 0 0 -4226 899 4615 4 MP PP -5356 0 0 4226 5356 0 0 -4226 899 4615 5 MP stroke 4 w DO 0 sg 899 4615 mt 6255 4615 L 6255 4615 mt 6255 4615 L 899 4192 mt 6255 4192 L 6255 4192 mt 6255 4192 L 899 3769 mt 6255 3769 L 6255 3769 mt 6255 3769 L 899 3347 mt 6255 3347 L 6255 3347 mt 6255 3347 L 899 2924 mt 6255 2924 L 6255 2924 mt 6255 2924 L 899 2502 mt 6255 2502 L 6255 2502 mt 6255 2502 L 899 2079 mt 6255 2079 L 6255 2079 mt 6255 2079 L 899 1656 mt 6255 1656 L 6255 1656 mt 6255 1656 L 899 1234 mt 6255 1234 L 6255 1234 mt 6255 1234 L 899 811 mt 6255 811 L 6255 811 mt 6255 811 L 899 389 mt 6255 389 L 6255 389 mt 6255 389 L SO 6 w 899 4615 mt 6255 4615 L 899 389 mt 6255 389 L 899 4615 mt 899 389 L 6255 4615 mt 6255 389 L 899 4615 mt 6255 4615 L 899 4615 mt 899 389 L 1791 4615 mt 1791 4561 L 1791 389 mt 1791 442 L 3577 4615 mt 3577 4561 L 3577 389 mt 3577 442 L 5362 4615 mt 5362 4561 L 5362 389 mt 5362 442 L 899 4615 mt 952 4615 L 6255 4615 mt 6201 4615 L %%IncludeResource: font Helvetica /Helvetica /ISOLatin1Encoding 192 FMSR 587 4686 mt (0%) s 899 4192 mt 952 4192 L 6255 4192 mt 6201 4192 L 480 4263 mt (10%) s 899 3769 mt 952 3769 L 6255 3769 mt 6201 3769 L 480 3840 mt (20%) s 899 3347 mt 952 3347 L 6255 3347 mt 6201 3347 L 480 3418 mt (30%) s 899 2924 mt 952 2924 L 6255 2924 mt 6201 2924 L 480 2995 mt (40%) s 899 2502 mt 952 2502 L 6255 2502 mt 6201 2502 L 480 2573 mt (50%) s 899 2079 mt 952 2079 L 6255 2079 mt 6201 2079 L 480 2150 mt (60%) s 899 1656 mt 952 1656 L 6255 1656 mt 6201 1656 L 480 1727 mt (70%) s 899 1234 mt 952 1234 L 6255 1234 mt 6201 1234 L 480 1305 mt (80%) s 899 811 mt 952 811 L 6255 811 mt 6201 811 L 480 882 mt (90%) s 899 389 mt 952 389 L 6255 389 mt 6201 389 L 374 460 mt (100%) s 899 4615 mt 6255 4615 L 899 389 mt 6255 389 L 899 4615 mt 899 389 L 6255 4615 mt 6255 389 L gs 899 389 5357 4227 MR c np /c8 { 0.000000 1.000000 1.000000 sr} bdef c8 0 3925 408 0 0 -3925 1332 4615 4 MP PP 0 sg -408 0 0 3925 408 0 0 -3925 1332 4615 5 MP stroke c8 0 3925 408 0 0 -3925 3117 4615 4 MP PP 0 sg -408 0 0 3925 408 0 0 -3925 3117 4615 5 MP stroke c8 0 3925 408 0 0 -3925 4903 4615 4 MP PP 0 sg -408 0 0 3925 408 0 0 -3925 4903 4615 5 MP stroke /c9 { 1.000000 0.000000 1.000000 sr} bdef c9 0 382 408 0 0 -382 1842 4615 4 MP PP 0 sg -408 0 0 382 408 0 0 -382 1842 4615 5 MP stroke c9 0 1446 408 0 0 -1446 3628 4615 4 MP PP 0 sg -408 0 0 1446 408 0 0 -1446 3628 4615 5 MP stroke c9 0 3232 408 0 0 -3232 5413 4615 4 MP PP 0 sg -408 0 0 3232 408 0 0 -3232 5413 4615 5 MP stroke gr 1 sg 0 477 1405 0 0 -477 4790 926 4 MP PP -1405 0 0 477 1405 0 0 -477 4790 926 5 MP stroke 4 w DO SO 6 w 0 sg 4790 926 mt 6195 926 L 4790 449 mt 6195 449 L 4790 926 mt 4790 449 L 6195 926 mt 6195 449 L 4790 926 mt 6195 926 L 4790 926 mt 4790 449 L 4790 926 mt 6195 926 L 4790 449 mt 6195 449 L 4790 926 mt 4790 449 L 6195 926 mt 6195 449 L 5323 644 mt (recall) s 5323 865 mt (precision) s gs 4790 449 1406 478 MR c np c8 0 -163 -320 0 0 163 320 0 4896 498 5 MP PP 0 sg 0 0 0 -163 -320 0 0 163 320 0 4896 498 6 MP stroke c9 0 -162 -320 0 0 162 320 0 4896 720 5 MP PP 0 sg 0 0 0 -162 -320 0 0 162 320 0 4896 720 6 MP stroke gr 1055 4925 mt (Un-processed ) s 2882 4938 mt (Noise-filtered ) s 4585 4925 mt (Noise-filtered +) s 4585 5146 mt ( Node-merged ) s end eplot %%EndObject epage end showpage %%Trailer %%EOF %%EndDocument @endspecial Black Black Black -83 1926 a Fk(Figure)28 b(3.)g Fd(Recall)23 b(and)g(precision)g(rates)g(of)i(C4.5)e(with)-83 2025 y(diff)o(erent)c(heuristics)f(on)j(traces)e(containing)f(database) -83 2125 y(accesses.)p -182 2237 V -182 2424 a Fr(snapshot,)i(and)h Fl(f)334 2436 y Fi(t)385 2424 y Fr(the)h(number)e(of)i(f)o(ailed)f (requests)g(grouped)f(un-)-182 2523 y(der)25 b(leaf)h(node)e Fl(t)p Fr(.)i(If)457 2486 y Fi(f)489 2494 y Fc(t)p 457 2504 60 4 v 461 2552 a Fi(F)560 2523 y Fl(>)33 b(c)p Fr(,)26 b(then)f(the)h(path)f(leading)g(to)h(node)e Fl(t)-182 2623 y Fr(is)k(retained)e(as)i(a)g(candidate.)d(Raising)j(\(lo)n (wering\))d Fl(c)j Fr(w)o(ould)e(de-)-182 2722 y(crease)20 b(\(increase\))f(the)h(number)e(of)i(retained)f(paths.)-83 2823 y(There)k(are)g(man)o(y)g(dif)n(ferent)e(w)o(ays)j(to)g(select)g (the)g(threshold)e Fl(c)p Fr(.)-182 2923 y(Here)k(we)g(e)o(xplore)f(tw) o(o)i(approaches:)d(\(1\))i(selection)g(based)g(on)f(a)-182 3023 y(metric)e(that)h(combines)e(recall)i(and)f(precision)f(and)h (\(2\))g(selection)-182 3122 y(based)17 b(on)g(a)h(metric)f(that)h (measures)f(the)g(e)o(xpected)f(reco)o(v)o(ery)f(time.)-83 3223 y(The)29 b(F-score)f(is)i(de\002ned)e(as)h(the)g(harmonic)e(mean)h (of)h(preci-)-182 3323 y(sion)20 b(and)f(recall:)261 3523 y(F-score)j Fm(=)642 3467 y Fl(P)12 b(r)r(ecision)18 b Fq(\003)g Fl(R)q(ecal)r(l)p 631 3504 702 4 v 631 3580 a(P)12 b(r)r(ecision)18 b Fm(+)g Fl(R)q(ecal)r(l)-182 3728 y Fr(Figure)e(4)i(plots)f(the)h(F-scores)f(\(a)n(v)o(eraged)f(o)o (v)o(er)g(the)h(10)g(basic)h(trace)-182 3828 y(snapshots\))33 b(for)g(C4.5)g(against)g(v)n(arious)g(v)n(alues)h(of)f Fl(c)p Fr(.)h(The)g(5\045)-182 3928 y(threshold)15 b(returns)h(the)h (highest)f(F-score)g(with)h(a)g(v)n(alue)f(of)h Fm(0)p Fl(:)p Fm(4194)p Fr(.)-182 4027 y(This)35 b(puts)g(us)h(at)g(the)f (rightmost)f(end)h(of)g(the)g(recall-precision)-182 4127 y(curv)o(e)19 b(in)h(Figure)f(2.)-83 4228 y(Alternati)n(v)o(ely)-5 b(,)21 b(we)j(can)f(pick)g Fl(c)g Fr(to)h(optimize)e(a)i(reco)o(v)o (ery)d(cost)-182 4327 y(function.)j(F)o(or)h(each)h(component)d(of)j (the)g(system,)f(we)i(kno)n(w)e(\(1\))-182 4427 y(whether)31 b(or)h(not)g(it)h(contains)e(a)i(real)f(source)f(of)h(error)m(,)f(and)h (\(2\))-182 4527 y(whether)24 b(or)h(not)g(our)f(algorithm)g(labels)h (the)g(path)g(as)h(a)g(potential)-182 4626 y(source)e(of)h(error)-5 b(.)24 b(Let)h Fl(Y)44 b Fr(denote)24 b(the)h(ground)e(truth)h(label)h (of)g(the)-182 4726 y(component,)h(where)j Fl(Y)58 b Fm(=)40 b(1)29 b Fr(if)h(and)e(only)h(if)g(it)h(is)h(truly)d(corre-) -182 4826 y(lated)20 b(with)g(error)-5 b(.)19 b(Let)510 4805 y Fm(^)498 4826 y Fl(Y)39 b Fr(be)20 b(the)h(label)f(gi)n(v)o(en)f (by)g(our)h(algorithm.)-83 4926 y(Let)h Fl(a)f Fr(be)g(the)h(amount)d (of)i(time)h(it)f(tak)o(es)h(to)f(run)g(the)g(automatic)-182 5026 y(diagnosis)26 b(algorithm,)g Fl(r)31 b Fr(the)d(time)f(it)i(tak)o (es)e(to)h(perform)e(the)h(re-)-182 5126 y(co)o(v)o(ery)-5 b(,)23 b Fl(v)31 b Fr(the)26 b(time)h(it)g(tak)o(es)g(to)f(v)o(erify)f (whether)h(or)g(not)g(the)g(re-)-182 5225 y(co)o(v)o(ery)15 b(action)j(\002x)o(ed)f(the)h(b)n(ug,)f(and)g Fl(m)h Fr(the)g(time)g(for)f(a)h(human)f(op-)-182 5325 y(erator)23 b(to)i(manually)e(e)o(xamine)g(the)i(system)g(and)f(locate)g(the)h(b)n (ug.)p Black Black 1974 28 1969 4 v Black Black Black 1974 1583 a @beginspecial 37 @llx 189 @lly 557 @urx 591 @ury 2362 @rwi @setspecial %%BeginDocument: f-score-c45.eps %!PS-Adobe-2.0 EPSF-1.2 %%Creator: MATLAB, The Mathworks, Inc. %%Title: f-score-c45.eps %%CreationDate: 03/19/2004 14:26:37 %%DocumentNeededFonts: Helvetica %%DocumentProcessColors: Cyan Magenta Yellow Black %%Extensions: CMYK %%Pages: 1 %%BoundingBox: 37 189 557 591 %%EndComments %%BeginProlog % MathWorks dictionary /MathWorks 160 dict begin % definition operators /bdef {bind def} bind def /ldef {load def} bind def /xdef {exch def} bdef /xstore {exch store} bdef % operator abbreviations /c /clip ldef /cc /concat ldef /cp /closepath ldef /gr /grestore ldef /gs /gsave ldef /mt /moveto ldef /np /newpath ldef /cm /currentmatrix ldef /sm /setmatrix ldef /rm /rmoveto ldef /rl /rlineto ldef /s {show newpath} bdef /sc {setcmykcolor} bdef /sr /setrgbcolor ldef /sg /setgray ldef /w /setlinewidth ldef /j /setlinejoin ldef /cap /setlinecap ldef /rc {rectclip} bdef /rf {rectfill} bdef % page state control /pgsv () def /bpage {/pgsv save def} bdef /epage {pgsv restore} bdef /bplot /gsave ldef /eplot {stroke grestore} bdef % orientation switch /portraitMode 0 def /landscapeMode 1 def /rotateMode 2 def % coordinate system mappings /dpi2point 0 def % font control /FontSize 0 def /FMS {/FontSize xstore findfont [FontSize 0 0 FontSize neg 0 0] makefont setfont} bdef /reencode {exch dup where {pop load} {pop StandardEncoding} ifelse exch dup 3 1 roll findfont dup length dict begin { 1 index /FID ne {def}{pop pop} ifelse } forall /Encoding exch def currentdict end definefont pop} bdef /isroman {findfont /CharStrings get /Agrave known} bdef /FMSR {3 1 roll 1 index dup isroman {reencode} {pop pop} ifelse exch FMS} bdef /csm {1 dpi2point div -1 dpi2point div scale neg translate dup landscapeMode eq {pop -90 rotate} {rotateMode eq {90 rotate} if} ifelse} bdef % line types: solid, dotted, dashed, dotdash /SO { [] 0 setdash } bdef /DO { [.5 dpi2point mul 4 dpi2point mul] 0 setdash } bdef /DA { [6 dpi2point mul] 0 setdash } bdef /DD { [.5 dpi2point mul 4 dpi2point mul 6 dpi2point mul 4 dpi2point mul] 0 setdash } bdef % macros for lines and objects /L {lineto stroke} bdef /MP {3 1 roll moveto 1 sub {rlineto} repeat} bdef /AP {{rlineto} repeat} bdef /PDlw -1 def /W {/PDlw currentlinewidth def setlinewidth} def /PP {closepath eofill} bdef /DP {closepath stroke} bdef /MR {4 -2 roll moveto dup 0 exch rlineto exch 0 rlineto neg 0 exch rlineto closepath} bdef /FR {MR stroke} bdef /PR {MR fill} bdef /L1i {{currentfile picstr readhexstring pop} image} bdef /tMatrix matrix def /MakeOval {newpath tMatrix currentmatrix pop translate scale 0 0 1 0 360 arc tMatrix setmatrix} bdef /FO {MakeOval stroke} bdef /PO {MakeOval fill} bdef /PD {currentlinewidth 2 div 0 360 arc fill PDlw -1 eq not {PDlw w /PDlw -1 def} if} def /FA {newpath tMatrix currentmatrix pop translate scale 0 0 1 5 -2 roll arc tMatrix setmatrix stroke} bdef /PA {newpath tMatrix currentmatrix pop translate 0 0 moveto scale 0 0 1 5 -2 roll arc closepath tMatrix setmatrix fill} bdef /FAn {newpath tMatrix currentmatrix pop translate scale 0 0 1 5 -2 roll arcn tMatrix setmatrix stroke} bdef /PAn {newpath tMatrix currentmatrix pop translate 0 0 moveto scale 0 0 1 5 -2 roll arcn closepath tMatrix setmatrix fill} bdef /vradius 0 def /hradius 0 def /lry 0 def /lrx 0 def /uly 0 def /ulx 0 def /rad 0 def /MRR {/vradius xdef /hradius xdef /lry xdef /lrx xdef /uly xdef /ulx xdef newpath tMatrix currentmatrix pop ulx hradius add uly vradius add translate hradius vradius scale 0 0 1 180 270 arc tMatrix setmatrix lrx hradius sub uly vradius add translate hradius vradius scale 0 0 1 270 360 arc tMatrix setmatrix lrx hradius sub lry vradius sub translate hradius vradius scale 0 0 1 0 90 arc tMatrix setmatrix ulx hradius add lry vradius sub translate hradius vradius scale 0 0 1 90 180 arc tMatrix setmatrix closepath} bdef /FRR {MRR stroke } bdef /PRR {MRR fill } bdef /MlrRR {/lry xdef /lrx xdef /uly xdef /ulx xdef /rad lry uly sub 2 div def newpath tMatrix currentmatrix pop ulx rad add uly rad add translate rad rad scale 0 0 1 90 270 arc tMatrix setmatrix lrx rad sub lry rad sub translate rad rad scale 0 0 1 270 90 arc tMatrix setmatrix closepath} bdef /FlrRR {MlrRR stroke } bdef /PlrRR {MlrRR fill } bdef /MtbRR {/lry xdef /lrx xdef /uly xdef /ulx xdef /rad lrx ulx sub 2 div def newpath tMatrix currentmatrix pop ulx rad add uly rad add translate rad rad scale 0 0 1 180 360 arc tMatrix setmatrix lrx rad sub lry rad sub translate rad rad scale 0 0 1 0 180 arc tMatrix setmatrix closepath} bdef /FtbRR {MtbRR stroke } bdef /PtbRR {MtbRR fill } bdef /stri 6 array def /dtri 6 array def /smat 6 array def /dmat 6 array def /tmat1 6 array def /tmat2 6 array def /dif 3 array def /asub {/ind2 exch def /ind1 exch def dup dup ind1 get exch ind2 get sub exch } bdef /tri_to_matrix { 2 0 asub 3 1 asub 4 0 asub 5 1 asub dup 0 get exch 1 get 7 -1 roll astore } bdef /compute_transform { dmat dtri tri_to_matrix tmat1 invertmatrix smat stri tri_to_matrix tmat2 concatmatrix } bdef /ds {stri astore pop} bdef /dt {dtri astore pop} bdef /db {2 copy /cols xdef /rows xdef mul dup 3 mul string currentfile exch readhexstring pop dup 0 3 index getinterval /rbmap xdef dup 2 index dup getinterval /gbmap xdef 1 index dup 2 mul exch getinterval /bbmap xdef pop pop}bdef /it {gs np dtri aload pop moveto lineto lineto cp c cols rows 8 compute_transform rbmap gbmap bbmap true 3 colorimage gr}bdef /il {newpath moveto lineto stroke}bdef currentdict end def %%EndProlog %%BeginSetup MathWorks begin 0 cap end %%EndSetup %%Page: 1 1 %%BeginPageSetup %%PageBoundingBox: 37 189 557 591 MathWorks begin bpage %%EndPageSetup %%BeginObject: obj1 bplot /dpi2point 12 def portraitMode 0216 7344 csm 237 247 6239 4822 MR c np 91 dict begin %Colortable dictionary /c0 { 0 0 0 sr} bdef /c1 { 1 1 1 sr} bdef /c2 { 1 0 0 sr} bdef /c3 { 0 1 0 sr} bdef /c4 { 0 0 1 sr} bdef /c5 { 1 1 0 sr} bdef /c6 { 1 0 1 sr} bdef /c7 { 0 1 1 sr} bdef c0 1 j 1 sg 0 0 6917 5186 PR 6 w 0 4226 5360 0 0 -4226 899 4615 4 MP PP -5360 0 0 4226 5360 0 0 -4226 899 4615 5 MP stroke 4 w DO 0 sg 899 4615 mt 6259 4615 L 6259 4615 mt 6259 4615 L 899 4192 mt 6259 4192 L 6259 4192 mt 6259 4192 L 899 3769 mt 6259 3769 L 6259 3769 mt 6259 3769 L 899 3347 mt 6259 3347 L 6259 3347 mt 6259 3347 L 899 2924 mt 6259 2924 L 6259 2924 mt 6259 2924 L 899 2502 mt 6259 2502 L 6259 2502 mt 6259 2502 L 899 2079 mt 6259 2079 L 6259 2079 mt 6259 2079 L 899 1656 mt 6259 1656 L 6259 1656 mt 6259 1656 L 899 1234 mt 6259 1234 L 6259 1234 mt 6259 1234 L 899 811 mt 6259 811 L 6259 811 mt 6259 811 L 899 389 mt 6259 389 L 6259 389 mt 6259 389 L SO 6 w 899 4615 mt 6259 4615 L 899 389 mt 6259 389 L 899 4615 mt 899 389 L 6259 4615 mt 6259 389 L 899 4615 mt 6259 4615 L 899 4615 mt 899 389 L 899 4615 mt 899 4561 L 899 389 mt 899 442 L %%IncludeResource: font Helvetica /Helvetica /ISOLatin1Encoding 168 FMSR 778 4805 mt (0%) s 1792 4615 mt 1792 4561 L 1792 389 mt 1792 442 L 1624 4805 mt (10%) s 2685 4615 mt 2685 4561 L 2685 389 mt 2685 442 L 2517 4805 mt (20%) s 3579 4615 mt 3579 4561 L 3579 389 mt 3579 442 L 3411 4805 mt (30%) s 4472 4615 mt 4472 4561 L 4472 389 mt 4472 442 L 4304 4805 mt (40%) s 5365 4615 mt 5365 4561 L 5365 389 mt 5365 442 L 5197 4805 mt (50%) s 6259 4615 mt 6259 4561 L 6259 389 mt 6259 442 L 6091 4805 mt (60%) s 899 4615 mt 952 4615 L 6259 4615 mt 6205 4615 L 771 4677 mt (0) s 899 4192 mt 952 4192 L 6259 4192 mt 6205 4192 L 538 4254 mt (0.05) s 899 3769 mt 952 3769 L 6259 3769 mt 6205 3769 L 631 3831 mt (0.1) s 899 3347 mt 952 3347 L 6259 3347 mt 6205 3347 L 538 3409 mt (0.15) s 899 2924 mt 952 2924 L 6259 2924 mt 6205 2924 L 631 2986 mt (0.2) s 899 2502 mt 952 2502 L 6259 2502 mt 6205 2502 L 538 2564 mt (0.25) s 899 2079 mt 952 2079 L 6259 2079 mt 6205 2079 L 631 2141 mt (0.3) s 899 1656 mt 952 1656 L 6259 1656 mt 6205 1656 L 538 1718 mt (0.35) s 899 1234 mt 952 1234 L 6259 1234 mt 6205 1234 L 631 1296 mt (0.4) s 899 811 mt 952 811 L 6259 811 mt 6205 811 L 538 873 mt (0.45) s 899 389 mt 952 389 L 6259 389 mt 6205 389 L 631 451 mt (0.5) s 899 4615 mt 6259 4615 L 899 389 mt 6259 389 L 899 4615 mt 899 389 L 6259 4615 mt 6259 389 L gs 899 389 5361 4227 MR c np 36 w /c8 { 0.000000 0.000000 1.000000 sr} bdef c8 -447 -224 -1340 -13 -2233 -490 5365 1797 4 MP stroke gr 36 w c8 0 j 0 -58 -58 0 0 58 58 0 5336 1768 5 MP DP 0 -58 -58 0 0 58 58 0 3103 1278 5 MP DP 0 -58 -58 0 0 58 58 0 1763 1265 5 MP DP 0 -58 -58 0 0 58 58 0 1316 1041 5 MP DP gs 899 389 5361 4227 MR c np gr 0 sg %%IncludeResource: font Helvetica /Helvetica /ISOLatin1Encoding 192 FMSR 2873 5001 mt (Cutoff Threshold) s 440 2867 mt -90 rotate (F-Score) s 90 rotate 6 w end eplot %%EndObject epage end showpage %%Trailer %%EOF %%EndDocument @endspecial Black Black Black 2073 1802 a Fk(Figure)33 b(4.)f(A)m(vera)o(g)q(e)h(F-score)g(vs.)g(cutoff)e(thresh-)2073 1901 y(old)23 b(f)n(or)g(C4.5)h(on)e(the)h(basic)g(trace)h(dataset.)p 1974 2014 V 1974 2200 V Black Black Black 1974 3791 a @beginspecial 49 @llx 189 @lly 557 @urx 591 @ury 2362 @rwi @setspecial %%BeginDocument: utility-c45.eps %!PS-Adobe-2.0 EPSF-1.2 %%Creator: MATLAB, The Mathworks, Inc. %%Title: utility-c45.eps %%CreationDate: 03/20/2004 03:51:57 %%DocumentNeededFonts: Helvetica %%DocumentProcessColors: Cyan Magenta Yellow Black %%Extensions: CMYK %%Pages: 1 %%BoundingBox: 49 189 557 591 %%EndComments %%BeginProlog % MathWorks dictionary /MathWorks 160 dict begin % definition operators /bdef {bind def} bind def /ldef {load def} bind def /xdef {exch def} bdef /xstore {exch store} bdef % operator abbreviations /c /clip ldef /cc /concat ldef /cp /closepath ldef /gr /grestore ldef /gs /gsave ldef /mt /moveto ldef /np /newpath ldef /cm /currentmatrix ldef /sm /setmatrix ldef /rm /rmoveto ldef /rl /rlineto ldef /s {show newpath} bdef /sc {setcmykcolor} bdef /sr /setrgbcolor ldef /sg /setgray ldef /w /setlinewidth ldef /j /setlinejoin ldef /cap /setlinecap ldef /rc {rectclip} bdef /rf {rectfill} bdef % page state control /pgsv () def /bpage {/pgsv save def} bdef /epage {pgsv restore} bdef /bplot /gsave ldef /eplot {stroke grestore} bdef % orientation switch /portraitMode 0 def /landscapeMode 1 def /rotateMode 2 def % coordinate system mappings /dpi2point 0 def % font control /FontSize 0 def /FMS {/FontSize xstore findfont [FontSize 0 0 FontSize neg 0 0] makefont setfont} bdef /reencode {exch dup where {pop load} {pop StandardEncoding} ifelse exch dup 3 1 roll findfont dup length dict begin { 1 index /FID ne {def}{pop pop} ifelse } forall /Encoding exch def currentdict end definefont pop} bdef /isroman {findfont /CharStrings get /Agrave known} bdef /FMSR {3 1 roll 1 index dup isroman {reencode} {pop pop} ifelse exch FMS} bdef /csm {1 dpi2point div -1 dpi2point div scale neg translate dup landscapeMode eq {pop -90 rotate} {rotateMode eq {90 rotate} if} ifelse} bdef % line types: solid, dotted, dashed, dotdash /SO { [] 0 setdash } bdef /DO { [.5 dpi2point mul 4 dpi2point mul] 0 setdash } bdef /DA { [6 dpi2point mul] 0 setdash } bdef /DD { [.5 dpi2point mul 4 dpi2point mul 6 dpi2point mul 4 dpi2point mul] 0 setdash } bdef % macros for lines and objects /L {lineto stroke} bdef /MP {3 1 roll moveto 1 sub {rlineto} repeat} bdef /AP {{rlineto} repeat} bdef /PDlw -1 def /W {/PDlw currentlinewidth def setlinewidth} def /PP {closepath eofill} bdef /DP {closepath stroke} bdef /MR {4 -2 roll moveto dup 0 exch rlineto exch 0 rlineto neg 0 exch rlineto closepath} bdef /FR {MR stroke} bdef /PR {MR fill} bdef /L1i {{currentfile picstr readhexstring pop} image} bdef /tMatrix matrix def /MakeOval {newpath tMatrix currentmatrix pop translate scale 0 0 1 0 360 arc tMatrix setmatrix} bdef /FO {MakeOval stroke} bdef /PO {MakeOval fill} bdef /PD {currentlinewidth 2 div 0 360 arc fill PDlw -1 eq not {PDlw w /PDlw -1 def} if} def /FA {newpath tMatrix currentmatrix pop translate scale 0 0 1 5 -2 roll arc tMatrix setmatrix stroke} bdef /PA {newpath tMatrix currentmatrix pop translate 0 0 moveto scale 0 0 1 5 -2 roll arc closepath tMatrix setmatrix fill} bdef /FAn {newpath tMatrix currentmatrix pop translate scale 0 0 1 5 -2 roll arcn tMatrix setmatrix stroke} bdef /PAn {newpath tMatrix currentmatrix pop translate 0 0 moveto scale 0 0 1 5 -2 roll arcn closepath tMatrix setmatrix fill} bdef /vradius 0 def /hradius 0 def /lry 0 def /lrx 0 def /uly 0 def /ulx 0 def /rad 0 def /MRR {/vradius xdef /hradius xdef /lry xdef /lrx xdef /uly xdef /ulx xdef newpath tMatrix currentmatrix pop ulx hradius add uly vradius add translate hradius vradius scale 0 0 1 180 270 arc tMatrix setmatrix lrx hradius sub uly vradius add translate hradius vradius scale 0 0 1 270 360 arc tMatrix setmatrix lrx hradius sub lry vradius sub translate hradius vradius scale 0 0 1 0 90 arc tMatrix setmatrix ulx hradius add lry vradius sub translate hradius vradius scale 0 0 1 90 180 arc tMatrix setmatrix closepath} bdef /FRR {MRR stroke } bdef /PRR {MRR fill } bdef /MlrRR {/lry xdef /lrx xdef /uly xdef /ulx xdef /rad lry uly sub 2 div def newpath tMatrix currentmatrix pop ulx rad add uly rad add translate rad rad scale 0 0 1 90 270 arc tMatrix setmatrix lrx rad sub lry rad sub translate rad rad scale 0 0 1 270 90 arc tMatrix setmatrix closepath} bdef /FlrRR {MlrRR stroke } bdef /PlrRR {MlrRR fill } bdef /MtbRR {/lry xdef /lrx xdef /uly xdef /ulx xdef /rad lrx ulx sub 2 div def newpath tMatrix currentmatrix pop ulx rad add uly rad add translate rad rad scale 0 0 1 180 360 arc tMatrix setmatrix lrx rad sub lry rad sub translate rad rad scale 0 0 1 0 180 arc tMatrix setmatrix closepath} bdef /FtbRR {MtbRR stroke } bdef /PtbRR {MtbRR fill } bdef /stri 6 array def /dtri 6 array def /smat 6 array def /dmat 6 array def /tmat1 6 array def /tmat2 6 array def /dif 3 array def /asub {/ind2 exch def /ind1 exch def dup dup ind1 get exch ind2 get sub exch } bdef /tri_to_matrix { 2 0 asub 3 1 asub 4 0 asub 5 1 asub dup 0 get exch 1 get 7 -1 roll astore } bdef /compute_transform { dmat dtri tri_to_matrix tmat1 invertmatrix smat stri tri_to_matrix tmat2 concatmatrix } bdef /ds {stri astore pop} bdef /dt {dtri astore pop} bdef /db {2 copy /cols xdef /rows xdef mul dup 3 mul string currentfile exch readhexstring pop dup 0 3 index getinterval /rbmap xdef dup 2 index dup getinterval /gbmap xdef 1 index dup 2 mul exch getinterval /bbmap xdef pop pop}bdef /it {gs np dtri aload pop moveto lineto lineto cp c cols rows 8 compute_transform rbmap gbmap bbmap true 3 colorimage gr}bdef /il {newpath moveto lineto stroke}bdef currentdict end def %%EndProlog %%BeginSetup MathWorks begin 0 cap end %%EndSetup %%Page: 1 1 %%BeginPageSetup %%PageBoundingBox: 49 189 557 591 MathWorks begin bpage %%EndPageSetup %%BeginObject: obj1 bplot /dpi2point 12 def portraitMode 0216 7344 csm 372 247 6100 4822 MR c np 91 dict begin %Colortable dictionary /c0 { 0 0 0 sr} bdef /c1 { 1 1 1 sr} bdef /c2 { 1 0 0 sr} bdef /c3 { 0 1 0 sr} bdef /c4 { 0 0 1 sr} bdef /c5 { 1 1 0 sr} bdef /c6 { 1 0 1 sr} bdef /c7 { 0 1 1 sr} bdef c0 1 j 1 sg 0 0 6913 5186 PR 6 w 0 4226 5356 0 0 -4226 899 4615 4 MP PP -5356 0 0 4226 5356 0 0 -4226 899 4615 5 MP stroke 4 w DO 0 sg 899 4615 mt 6255 4615 L 6255 4615 mt 6255 4615 L 899 4086 mt 6255 4086 L 6255 4086 mt 6255 4086 L 899 3558 mt 6255 3558 L 6255 3558 mt 6255 3558 L 899 3030 mt 6255 3030 L 6255 3030 mt 6255 3030 L 899 2502 mt 6255 2502 L 6255 2502 mt 6255 2502 L 899 1973 mt 6255 1973 L 6255 1973 mt 6255 1973 L 899 1445 mt 6255 1445 L 6255 1445 mt 6255 1445 L 899 917 mt 6255 917 L 6255 917 mt 6255 917 L 899 389 mt 6255 389 L 6255 389 mt 6255 389 L SO 6 w 899 4615 mt 6255 4615 L 899 389 mt 6255 389 L 899 4615 mt 899 389 L 6255 4615 mt 6255 389 L 899 4615 mt 6255 4615 L 899 4615 mt 899 389 L 899 4615 mt 899 4561 L 899 389 mt 899 442 L %%IncludeResource: font Helvetica /Helvetica /ISOLatin1Encoding 168 FMSR 778 4805 mt (0%) s 1791 4615 mt 1791 4561 L 1791 389 mt 1791 442 L 1623 4805 mt (10%) s 2684 4615 mt 2684 4561 L 2684 389 mt 2684 442 L 2516 4805 mt (20%) s 3577 4615 mt 3577 4561 L 3577 389 mt 3577 442 L 3409 4805 mt (30%) s 4469 4615 mt 4469 4561 L 4469 389 mt 4469 442 L 4301 4805 mt (40%) s 5362 4615 mt 5362 4561 L 5362 389 mt 5362 442 L 5194 4805 mt (50%) s 6255 4615 mt 6255 4561 L 6255 389 mt 6255 442 L 6087 4805 mt (60%) s 899 4615 mt 952 4615 L 6255 4615 mt 6201 4615 L 673 4677 mt (-4) s 899 4086 mt 952 4086 L 6255 4086 mt 6201 4086 L 673 4148 mt (-2) s 899 3558 mt 952 3558 L 6255 3558 mt 6201 3558 L 771 3620 mt (0) s 899 3030 mt 952 3030 L 6255 3030 mt 6201 3030 L 771 3092 mt (2) s 899 2502 mt 952 2502 L 6255 2502 mt 6201 2502 L 771 2564 mt (4) s 899 1973 mt 952 1973 L 6255 1973 mt 6201 1973 L 771 2035 mt (6) s 899 1445 mt 952 1445 L 6255 1445 mt 6201 1445 L 771 1507 mt (8) s 899 917 mt 952 917 L 6255 917 mt 6201 917 L 678 979 mt (10) s 899 389 mt 952 389 L 6255 389 mt 6201 389 L 678 451 mt (12) s 899 4615 mt 6255 4615 L 899 389 mt 6255 389 L 899 4615 mt 899 389 L 6255 4615 mt 6255 389 L gs 899 389 5357 4227 MR c np 36 w /c8 { 0.000000 0.000000 1.000000 sr} bdef c8 -446 -449 -1339 -449 -2232 -449 5362 1973 4 MP stroke gr 36 w c8 0 j 0 -58 -58 0 0 58 58 0 5333 1944 5 MP DP 0 -58 -58 0 0 58 58 0 3101 1495 5 MP DP 0 -58 -58 0 0 58 58 0 1762 1046 5 MP DP 0 -58 -58 0 0 58 58 0 1316 597 5 MP DP gs 899 389 5357 4227 MR c np gr 0 sg %%IncludeResource: font Helvetica /Helvetica /ISOLatin1Encoding 192 FMSR 2871 5001 mt (Cutoff Threshold) s 575 4280 mt -90 rotate (Expected Savings in Recovery Time \(min\)) s 90 rotate 6 w end eplot %%EndObject epage end showpage %%Trailer %%EOF %%EndDocument @endspecial Black 2109 3960 a(Figure)f(5.)g(Sa)o(vings)g(in)g(reco)n (ver)q(y)h(time)f(f)n(or)g(C4.5.)p 1974 4039 V 1974 4255 a Fr(Each)17 b(of)g(the)h(four)e(combinations)g(of)h Fl(Y)36 b Fr(and)3309 4235 y Fm(^)3296 4255 y Fl(Y)h Fr(has)18 b(a)g(certain)f(cost)1974 4355 y(in)j(terms)g(of)g(reco)o(v)o (ery)e(time:)p Black 2057 4552 a Fq(\017)p Black 41 w Fl(Y)42 b Fm(=)22 b(1)p Fl(;)2408 4531 y Fm(^)2396 4552 y Fl(Y)41 b Fm(=)23 b(1)p Fr(:)d(requires)g(time)g Fm(\()p Fl(a)e Fm(+)h Fl(r)i Fm(+)d Fl(v)s Fm(\))p Fr(;)p Black 2057 4718 a Fq(\017)p Black 41 w Fl(Y)42 b Fm(=)22 b(1)p Fl(;)2408 4697 y Fm(^)2396 4718 y Fl(Y)41 b Fm(=)23 b(0)p Fr(:)d(requires)g(time)g Fm(\()p Fl(a)e Fm(+)h Fl(v)i Fm(+)d Fl(m)h Fm(+)f Fl(r)r Fm(\))p Fr(;)p Black 2057 4885 a Fq(\017)p Black 41 w Fl(Y)42 b Fm(=)22 b(0)p Fl(;)2408 4864 y Fm(^)2396 4885 y Fl(Y)41 b Fm(=)23 b(1)p Fr(:)d(requires)g(time) g Fm(\()p Fl(a)e Fm(+)h Fl(r)i Fm(+)d Fl(v)s Fm(\))p Fr(;)p Black 2057 5051 a Fq(\017)p Black 41 w Fl(Y)42 b Fm(=)22 b(0)p Fl(;)2408 5030 y Fm(^)2396 5051 y Fl(Y)41 b Fm(=)23 b(0)p Fr(:)d(requires)g(time)g Fm(\()p Fl(a)p Fm(\))p Fr(.)2073 5225 y(One)j(may)f(w)o(ant)h(to)g(pick)f(a)h(cutof)n (f)e(threshold)h Fl(c)h Fr(which)f(w)o(ould)1974 5325 y(w)o(ould)29 b(minimize)h(the)g(e)o(xpected)f(system)i(reco)o(v)o(ery) c(time)k(E)13 b Fm([)p Fl(T)f Fm(])p Black Black eop %%Page: 7 7 7 6 bop Black Black -182 83 a Fr(under)18 b(the)j(distrib)n(ution)e Fl(P)605 95 y Fi(c)639 83 y Fm(\()684 62 y(^)671 83 y Fl(Y)g Fq(j)p Fl(Y)f Fm(\))p Fr(:)-52 252 y(E)c Fm([)p Fl(T)e Fm(])82 b(=)h Fl(P)403 264 y Fi(c)437 252 y Fm(\()482 231 y(^)469 252 y Fl(Y)42 b Fm(=)23 b(1)p Fq(j)p Fl(Y)41 b Fm(=)22 b(1\))d Fq(\001)f Fm(\()p Fl(a)h Fm(+)f Fl(r)j Fm(+)d Fl(v)s Fm(\))350 356 y(+)p Fl(P)468 368 y Fi(c)501 356 y Fm(\()546 335 y(^)533 356 y Fl(Y)42 b Fm(=)23 b(0)p Fq(j)p Fl(Y)41 b Fm(=)23 b(1\))18 b Fq(\001)h Fm(\()p Fl(a)f Fm(+)g Fl(v)k Fm(+)c Fl(m)g Fm(+)g Fl(r)r Fm(\))350 461 y(+)p Fl(P)468 473 y Fi(c)501 461 y Fm(\()546 440 y(^)533 461 y Fl(Y)42 b Fm(=)23 b(1)p Fq(j)p Fl(Y)41 b Fm(=)23 b(0\))18 b Fq(\001)h Fm(\()p Fl(a)f Fm(+)g Fl(r)k Fm(+)c Fl(v)s Fm(\))350 565 y(+)p Fl(P)468 577 y Fi(c)501 565 y Fm(\()546 544 y(^)533 565 y Fl(Y)42 b Fm(=)23 b(0)p Fq(j)p Fl(Y)41 b Fm(=)23 b(0\))18 b Fq(\001)h Fm(\()p Fl(a)p Fm(\))-182 734 y Fr(The)j(e)o(xpected)f(amount)h(of)h (time)g(sa)n(v)o(ed)f(by)h(using)f(automatic)g(in-)-182 833 y(stead)e(of)f(manual)g(diagnosis)g(is)i(then)e Fl(m)e Fm(+)f Fl(r)k Fq(\000)c Fr(E)e Fm([)p Fl(T)e Fm(])o Fr(.)20 b(The)g(prob-)-182 933 y(ability)26 b(distrib)n(ution)g Fl(P)519 945 y Fi(c)553 933 y Fm(\()598 912 y(^)585 933 y Fl(Y)19 b Fq(j)p Fl(Y)g Fm(\))27 b Fr(at)g(v)n(arious)f(cutof)n(f)g (thresholds)f Fl(c)-182 1033 y Fr(can)20 b(be)g(estimated)g(directly)f (from)g(our)h(e)o(xperiments:)307 1201 y Fl(P)360 1213 y Fi(c)394 1201 y Fm(\()439 1180 y(^)426 1201 y Fl(Y)42 b Fm(=)23 b(1)p Fq(j)p Fl(Y)41 b Fm(=)22 b(1\))h(=)g Fl(R)q(ecal)r(l)1265 1213 y Fi(c)235 1323 y Fl(P)288 1335 y Fi(c)322 1323 y Fm(\()367 1302 y(^)354 1323 y Fl(Y)42 b Fm(=)23 b(0)p Fq(j)p Fl(Y)41 b Fm(=)23 b(1\))g(=)f(1)c Fq(\000)g Fl(R)q(ecal)r(l)1336 1335 y Fi(c)-29 1479 y Fl(P)24 1491 y Fi(c)58 1479 y Fm(\()103 1458 y(^)90 1479 y Fl(Y)42 b Fm(=)23 b(1)p Fq(j)p Fl(Y)41 b Fm(=)22 b(0\))h(=)853 1423 y Fr(#)d(of)g(f)o(alse)h(positi)n(v)o(es)p 704 1460 920 4 v 704 1536 a(#)f(of)g(non-f)o(aulty)e(components)-29 1679 y Fl(P)24 1691 y Fi(c)58 1679 y Fm(\()103 1658 y(^)90 1679 y Fl(Y)42 b Fm(=)23 b(0)p Fq(j)p Fl(Y)41 b Fm(=)22 b(0\))h(=)858 1623 y Fr(#)e(of)e(true)h(ne)o(gati)n(v)o(es)p 704 1660 V 704 1736 a(#)g(of)g(non-f)o(aulty)e(components)-83 1894 y(W)-7 b(e)17 b(plot)e(the)g(e)o(xpected)f(amount)g(of)h(time)h (sa)n(v)o(ed,)f Fl(m)q Fm(+)q Fl(r)s Fq(\000)q Fr(E)c Fm([)p Fl(T)h Fm(])p Fr(,)-182 1993 y(using)32 b(reasonable)f(v)n (alues)i(for)f Fl(a;)14 b(r)n(;)g(v)s Fr(,)33 b(and)f Fl(m)p Fr(.)h(Based)g(on)g(our)-182 2093 y(con)m(v)o(ersations)24 b(with)j(operations)e(teams)i(at)g(se)n(v)o(eral)f(lar)o(ge)g(Inter)n (-)-182 2193 y(net)i(sites,)h(we)g(set)g Fl(m)38 b Fm(=)f(15)28 b Fr(minutes,)g Fl(r)41 b Fm(=)c(3)29 b Fr(minute,)e Fl(v)41 b Fm(=)d(1)-182 2292 y Fr(minutes,)17 b(and)g Fl(a)23 b Fm(=)g(1)18 b Fr(minute.)f(Figure)g(5)h(sho)n(ws)g(the)g(e)o (xpected)e(re-)-182 2392 y(co)o(v)o(ery)e(time)j(for)f(the)h(f)o(aults) g(in)g(our)f(basic)h(trace)f(dataset.)h(On)f(a)n(v)o(er)n(-)-182 2491 y(age,)22 b(the)h(5\045)g(cutof)n(f)f(threshold)g(sa)n(v)o(es)h Fm(11)p Fl(:)p Fm(1)g Fr(minutes)f(o)o(v)o(er)g(man-)-182 2591 y(ual)e(diagnosis.)-182 2821 y Ft(6.)69 b(Discussion)-83 3034 y Fr(W)-7 b(e)21 b(ha)n(v)o(e)e(demonstrated)e(the)j (applicability)e(of)h(decision)g(trees)-182 3133 y(to)33 b(this)h(speci\002c)g(task)g(of)f(f)o(ailure)g(diagnosis.)g(While)h (there)f(are)-182 3233 y(other)26 b(classi\002ers)h(with)g(perhaps)f (better)g(f)o(ailure)g(prediction)f(per)n(-)-182 3332 y(formance,)e(decision)j(trees)g(return)f(easily)h(interpretable)f (lists)i(of)-182 3432 y(suspicious)32 b(system)h(components.)d(There)i (has)h(been)f(much)f(re-)-182 3532 y(lated)k(w)o(ork)g(in)h(the)g(area) f(of)h(feature)f(selection)g([1)o(])h([12)o(],)f(and)-182 3631 y(speci\002cally)18 b(in)h(the)g(conte)o(xt)e(of)h(decision)g (trees)h([10)o(].)g(In)f(our)g(con-)-182 3731 y(te)o(xt,)28 b(ho)n(we)n(v)o(er)m(,)e(it)j(is)h(not)e(suf)n(\002cient)g(to)h(just)g (include)e(the)i(set)g(of)-182 3831 y(features)c(used)i(in)f(all)h(of)f (the)h(paths)f(leading)g(to)g(f)o(ailed)h(requests.)-182 3930 y(Rather)m(,)i(we)i(ha)n(v)o(e)e(demonstrated)g(that)h (post-processing)e(of)i(the)-182 4030 y(candidate)23 b(paths)i(is)h(necessary)e(to)h(eliminate)f(costly)h(f)o(alse)g(posi-) -182 4129 y(ti)n(v)o(es.)-83 4229 y(The)36 b(domain)g(of)g(f)o(ailure)g (diagnosis)g(from)f(request)h(logs)h(is)-182 4329 y(characterized)23 b(by)h(the)h(ready)f(a)n(v)n(ailability)g(of)h(lar)o(ge)e(amounts)h(of) -182 4428 y(unlabeled)30 b(data.)i(Labeled)f(data,)h(such)g(as)h(the)f (snapshots)g(used)-182 4528 y(in)c(our)f(e)o(xperiments)g(here,)g(are)i (relati)n(v)o(ely)e(scarce.)h(The)f(related)-182 4628 y(problem)20 b(of)h(f)o(ailure)h(detection)f(concentrates)f(on)i (labeling)f(snap-)-182 4727 y(shots)28 b(as)i(either)e(f)o(aulty)g(or)g (normal.)f(One)h(could)g(perhaps)f(mak)o(e)-182 4827 y(use)j(of)g(unlabeled)e(snapshots)i(within)g(f)o(ailure)f(diagnosis)h (itself.)-182 4926 y(F)o(or)24 b(instance,)g(one)h(could)f(enrich)g (the)g(noise)h(\002ltering)g(step)g(with)-182 5026 y(a)f(notion)f(of)h (\223normal\224)f(amount)g(of)h(noise,)g(learned)f(from)g(statis-)-182 5126 y(tics)e(deri)n(v)o(ed)d(from)h(unlabeled)g(data.)-83 5225 y(Another)c(problem)f(is)j(in)g(detecting)e(whether)g(or)h(not)g (an)o(y)f(cause)-182 5325 y(is)i(disco)o(v)o(ered)e(at)j(all.)f(This)g (is)h(necessary)e(when)h(the)g(features)f(con-)p Black Black 1974 83 a(tained)23 b(in)g(the)h(traces)g(do)f(not)g(include)f (the)i(actual)f(sources)g(of)g(er)n(-)1974 183 y(ror)m(,)16 b(such)g(as)i(the)f(database)f(f)o(aults)h(presented)f(abo)o(v)o(e.)f (In)i(this)g(case,)1974 282 y(we)29 b(need)e(to)i(be)f(able)h(to)f (distinguish)g(between)g(a)g(decision)g(tree)1974 382 y(whose)f(leaf)h(nodes)f(seem)i(to)f(be)f(just)i(noise,)e(v)o(ersus)h (a)g(decision)1974 482 y(tree)33 b(whose)g(leaf)g(nodes)g(contain)f (useful)h(information)e(re)o(gard-)1974 581 y(ing)c(the)g(cause)g(of)f (f)o(ailures.)h(A)h(possible)e(approach)f(is)j(to)f(e)o(xam-)1974 681 y(ine)22 b(the)h(distrib)n(ution)e(of)h(f)o(ailed)h(cases)g(among)e (the)h(leaf)h(nodes.)e(If)1974 780 y(e)o(xamples)14 b(of)i(f)o(ailed)f (requests)g(are)g(concentrated)f(in)h(a)h(small)g(num-)1974 880 y(ber)21 b(of)h(leaf)g(nodes,)f(then)h(we)g(w)o(ould)f(lik)o(ely)h (get)g(high)f(quality)g(re-)1974 980 y(sults.)e(Otherwise,)f(if)h(f)o (ailures)f(are)g(e)n(v)o(enly)f(spread)h(among)f(a)i(lar)o(ge)1974 1079 y(number)i(of)i(leaf)g(nodes,)f(then)g(chances)g(are)h(we)h(do)e (not)h(ha)n(v)o(e)f(the)1974 1179 y(right)28 b(feature)h(that)g(causes) g(the)h(root)e(f)o(ailure.)h(W)-7 b(e)30 b(can)f(measure)1974 1279 y(the)20 b(\223spread\224)f(of)g(the)h(f)o(ailure)g(distrib)n (ution)e(by)i(looking)e(at)j(the)f(en-)1974 1378 y(trop)o(y)f(of)h(the) g(leaf)g(nodes)g(corresponding)d(to)j(f)o(ailures.)1974 1614 y Ft(7.)69 b(Related)26 b(W)-7 b(ork)2073 1834 y Fr(There)19 b(has)h(been)f(much)g(w)o(ork)g(in)g(the)h(\002eld)g(of)f (f)o(ailure)g(diagno-)1974 1934 y(sis,)k(though)e(most)i(pre)n(vious)e (w)o(ork)h(e)o(xplicitly)g(models)g(causal)g(or)1974 2033 y(dependence)13 b(interactions)i(between)g(the)h(v)n(arious)f (components)e(of)1974 2133 y(the)26 b(system.)g(Our)g(approach,)e(in)j (comparison,)d(mak)o(es)i(only)f(im-)1974 2233 y(plicit)c(use)f(of)h (the)f(underlying)e(structure)i(during)f(the)h(node)g(mer)o(g-)1974 2332 y(ing)e(phase.)h(It)g(is)h(also)f(necessary)f(to)h(stress)h(that,) f(though)e(we)j(ha)n(v)o(e)1974 2432 y(made)c(references)f(to)i (\223cause-\002nding,)-6 b(\224)14 b(we)j(do)g(not)f(attempt)g(to)h (in-)1974 2532 y(fer)i(an)o(y)f(causal)i(relationships)e(between)g(an)o (y)h(of)g(the)g(components)1974 2631 y(and)i(the)h(outcome.)e(There)h (has)h(been)f(much)g(w)o(ork)h(in)g(causal)g(net-)1974 2731 y(w)o(ork)j(modeling)f([18)o(],)h(and)g(also)h(on)g(inferring)e (causal)h(relation-)1974 2830 y(ships)g(from)f(observ)n(ational)f(data) j([8)o(].)f(Ho)n(we)n(v)o(er)m(,)e(that)i(is)h(not)f(the)1974 2930 y(approach)18 b(tak)o(en)i(in)g(this)h(paper)-5 b(.)2073 3031 y(There)30 b(are)h(man)o(y)e(commercial)g(management)g (systems)i(that)1974 3131 y(aid)16 b(f)o(ailure)g(diagnosis,)f(such)i (as)g(HP')-5 b(s)17 b(OpenV)-5 b(ie)n(w)16 b([9)o(])h(and)e(IBM')-5 b(s)1974 3230 y(T)m(i)n(v)n(oli)30 b([16)o(].)h(These)f(systems)h (typically)f(either)g(emplo)o(y)f(e)o(xpert)1974 3330 y(systems)f(with)h(human-generated)24 b(rules)k(or)g(rely)f(on)h(the)g (use)g(of)1974 3430 y(dependenc)o(y)18 b(models)i([7)o(,)i(11)o(].)f (Ho)n(we)n(v)o(er)m(,)e(these)i(systems)h(do)e(not)1974 3529 y(consider)c(ho)n(w)h(the)g(required)f(dependenc)o(y)e(models)j (are)g(obtained.)1974 3629 y(More)27 b(recent)f(research)h(has)g (focused)f(on)h(automatically)f(gener)n(-)1974 3728 y(ating)h (dependenc)o(y)e(models)j(based)f(on)h(dynamic)e(observ)n(ations.)1974 3828 y(Bro)n(wn)32 b(et)h(al.)f([4])g(use)h(acti)n(v)o(e)f (perturbation)e(of)i(the)g(system)h(to)1974 3928 y(identify)f (dependencies)e(and)j(use)g(statistical)h(modeling)d(of)i(the)1974 4027 y(system)24 b(to)g(compute)f(dependenc)o(y)e(strengths.)i(The)g (dependenc)o(y)1974 4127 y(strengths)34 b(can)h(be)g(used)g(to)g(order) f(the)h(potential)f(root)g(causes.)1974 4227 y(Ho)n(we)n(v)o(er)m(,)21 b(the)i(approach)e(is)j(intrusi)n(v)o(e)d(and)i(less)h(suitable)f(for)f (di-)1974 4326 y(agnosing)c(a)j(production)c(site.)2073 4427 y(The)30 b(authors)f(of)g([19)o(])h(present)f(a)h(f)o(ault)f (localization)g(system)1974 4527 y(that)21 b(models)g(f)o(aults)g(in)h (an)f(end-to-end)d(service)j(system.)h(The)f(de-)1974 4626 y(pendence)32 b(graph)g(models)i(dif)n(ferent)e(layers)i(within)g (each)f(host)1974 4726 y(and)21 b(linkage)f(pattern)h(between)g(hosts.) h(Each)f(layer)g(is)h(associated)1974 4826 y(with)k(multiple)g (possible)g(f)o(ailure)g(modes.)g(After)g(observing)e(cer)n(-)1974 4925 y(tain)c(symptoms)f(in)i(the)f(system,)g(belief)g(propagation)c (algorithms)1974 5025 y(are)31 b(run)f(on)h(the)g(graph,)f(and)g(the)h (posterior)f(beliefs)h(are)g(e)o(xam-)1974 5124 y(ined)20 b(to)g(pick)g(out)f(the)i(most)f(lik)o(ely)g(causes)g(for)g(the)g (symptoms.)2073 5225 y(In)c([20)n(],)g(a)g(netw)o(ork)e(management)f (system)j(is)g(b)n(uilt)g(to)g(monitor)1974 5325 y(e)o(xceptional)h(e)n (v)o(ents.)g(A)j(causal)e(model)g(of)h(the)f(system)h(is)h(b)n(uilt)f (by)p Black Black eop %%Page: 8 8 8 7 bop Black Black -182 83 a Fr(e)o(xperts)14 b(with)i(domain)e(kno)n (wledge,)g(containing)f(symptom)i(nodes)-182 183 y(and)k(problem)f (nodes.)h(A)h(codebook)d(is)k(then)e(b)n(uilt)h(that)g(optimally)-182 282 y(compresses)27 b(the)h(symptoms)f(gi)n(v)o(en)g(a)h(designated)f (set)i(of)f(prob-)-182 382 y(lems)19 b(one)g(wishes)h(to)g(monitor)-5 b(.)18 b(F)o(ault)h(correlation)f(then)h(becomes)-182 482 y(a)h(decoding)e(problem)h(gi)n(v)o(en)g(a)h(certain)g(set)h(of)f (observ)o(ed)e(e)n(v)o(ents.)-83 581 y(In)28 b(the)g(approach)e(tak)o (en)i(by)g([15)n(])h(and)e([14)o(],)h(the)g(netw)o(ork)f(is)-182 681 y(again)g(modeled)f(as)j(a)g(Bayesian)f(netw)o(ork.)e(The)i (authors)f(in)m(v)o(es-)-182 780 y(tigate)h(the)h(problem)e(of)h (designing)g(and)g(sending)g(the)g(optimum)-182 880 y(number)d(of)i (\223acti)n(v)o(e)f(probes\224)g(so)i(as)g(to)f(achie)n(v)o(e)f(a)i (certain)e(le)n(v)o(el)-182 980 y(of)18 b(accurac)o(y)f(in)i (diagnosis.)f(In)h(addition,)e(ef)n(\002cient)h(local)h(approx-)-182 1079 y(imation)28 b(techniques)g(is)i(applied)e(to)h(the)g(inference)f (task)h(on)g(the)-182 1179 y(Bayes)20 b(net,)g(and)g(accurac)o(y)e(is)j (sho)n(wn)f(to)g(de)o(grade)e(gracefully)h(un-)-182 1279 y(der)g(increasing)g(noise)h(in)h(the)f(netw)o(ork.)-83 1378 y(Our)31 b(earlier)f(w)o(ork,)g(Pinpoint)f([6])i(and)f(ObsLogs)g (at)h(T)-6 b(ellme)-182 1478 y(Netw)o(orks)20 b([5)o(],)h(also)g (dynamically)e(trace)i(request)f(paths)h(through)-182 1577 y(tiered)27 b(systems.)g(Pinpoint)g(uses)g(clustering)g(to)g (correlate)g(appli-)-182 1677 y(cation)19 b(components)f(with)j(f)o (ailures.)-182 1902 y Ft(8.)69 b(Conclusion)-83 2111 y Fr(W)-7 b(e)31 b(ha)n(v)o(e)f(presented)f(a)h(ne)n(w)g(approach)e(to) i(diagnosing)e(f)o(ail-)-182 2211 y(ures)d(in)h(lar)o(ge)f(systems.)h (W)-7 b(e)26 b(record)f(the)g(runtime)g(properties)f(of)-182 2310 y(each)19 b(request)g(and)g(apply)f(statistical)j(learning)d (techniques)h(to)g(au-)-182 2410 y(tomatically)26 b(identify)g(the)h (causes)g(of)g(f)o(ailures.)g(The)g(k)o(e)o(y)f(to)h(this)-182 2510 y(ability)f(is)h(a)f(lar)o(ge)g(amount)e(of)i(requests)g(and)g (runtime)f(informa-)-182 2609 y(tion,)19 b(which)h(enables)g (meaningful)e(statistical)j(analysis.)-83 2709 y(W)-7 b(e)20 b(v)n(alidate)e(our)g(approach)f(using)h(actual)g(f)o(ailure)h (cases)g(from)-182 2809 y(eBay)-5 b(.)41 b(The)g(MinEntrop)o(y)e (algorithm)h(has)i(been)f(deplo)o(yed)e(at)-182 2908 y(eBay)21 b(for)g(se)n(v)o(eral)g(months.)f(F)o(or)h(single-f)o(ault)f (cases,)i(it)g(correctly)-182 3008 y(identi\002es)i(100\045)g(of)g(f)o (aults)h(with)g(a)g(f)o(alse)g(positi)n(v)o(e)f(rate)g(of)g(25\045.) -182 3107 y(The)36 b(C4.5)h(decision)g(tree)g(algorithm)e(performs)h (well)h(in)h(both)-182 3207 y(single-)17 b(and)h(multi-f)o(ault)f (cases.)i(When)f(applied)f(to)i(request)e(paths)-182 3307 y(that)i(includes)g(databases)g(accessed,)g(it)i(correctly)d (identi\002es)h(93\045)-182 3406 y(of)h(f)o(aults)g(with)g(a)h(f)o (alse)g(positi)n(v)o(e)e(rate)h(of)g(24\045.)-83 3506 y(W)-7 b(e)26 b(are)e(currently)f(e)o(xploring)f(a)j(v)n(ariety)f(of)g (statistical)i(learn-)-182 3606 y(ing)i(algorithms)f(to)i(impro)o(v)o (e)e(the)h(diagnosis)g(performance.)e(W)-7 b(e)-182 3705 y(are)21 b(also)h(e)o(xperimenting)d(with)i(streaming)g(v)o(ersions)g (of)g(these)h(al-)-182 3805 y(gorithms)17 b(to)i(be)f(deplo)o(yed)f(on) h(production)e(systems.)j(Finally)-5 b(,)18 b(we)-182 3904 y(plan)25 b(to)g(e)o(xtend)f(our)h(approach)f(to)h(diagnose)f (wide-area)h(system)-182 4004 y(f)o(ailures.)-182 4147 y Fp(Ackno)o(wledgments)41 b Fr(This)c(w)o(ork)g(w)o(as)h(supported)e (in)h(part)g(by)-182 4247 y(ONR)26 b(MURI)g(Grant)f(N00014-00-1-0637)19 b(and)25 b(D)m(ARP)-8 b(A)27 b(AR)m(O-)-182 4346 y(MURI)20 b(A)m(CCLIMA)-9 b(TE)20 b(D)m(AAD-19-02-1-0383)o(.)-182 4572 y Ft(Refer)n(ences)p Black -145 4772 a Fe([1])p Black 42 w(A.)i(Blum)h(and)g(P)-8 b(.)22 b(Langle)o(y.)39 b(Selection)23 b(of)g(rele)n(v)n(ant)g(features)g(and)-16 4864 y(e)o(xamples)f(in)f(machine)h(learning.)36 b Fb(Arti\002cial)20 b(Intellig)o(ence)p Fe(,)i(pages)-16 4955 y(245\226271,)e(1997.)p Black -145 5051 a([2])p Black 42 w(R.)g(Agra)o(w)o(al,)i(T)-6 b(.)21 b(Imielinski,)g(and)i(A.)e(N.)g(Sw)o(ami.)35 b(Mining)22 b(Asso-)-16 5142 y(ciation)g(Rules)g(between)h(Sets)e(of)h(Items)g(in)g (Lar)o(ge)g(Databases.)38 b(In)-16 5234 y Fb(Pr)m(oceedings)23 b(of)g(the)f(A)n(CM)g(SIGMOD)h(Confer)m(ence)h(on)f(Mana)o(g)o(e-)-16 5325 y(ment)c(of)f(Data)p Fe(,)h(pages)h(207\226216,)h(W)-6 b(ashington,)19 b(D.C.,)f(1993.)p Black Black Black 2011 83 a([3])p Black 42 w(L.)24 b(Breiman,)i(J.)f(H.Friedman,)g(R.)f(A.)h (Olshen,)h(and)g(C.)f(J.)g(Stone.)2140 174 y Fb(Classi\002cation)20 b(and)f(Re)m(gr)m(ession)h(T)l(r)m(ees)p Fe(.)27 b(W)-6 b(adsw)o(orth,)19 b(1984.)p Black 2011 267 a([4])p Black 42 w(A.)33 b(Bro)n(wn,)i(G.)e(Kar)m(,)h(and)h(A.)e(K)n(eller)l(.)76 b(An)34 b(Acti)n(v)o(e)g(Approach)2140 359 y(to)27 b(Characterizing)g (Dynamic)g(Dependencies)i(for)e(Problem)g(De-)2140 450 y(termination)45 b(in)g(a)f(Distrib)o(uted)h(En)m(vironment.)111 b(In)44 b Fb(Se)o(venth)2140 541 y(IFIP/IEEE)19 b(International)24 b(Symposium)f(on)f(Inte)m(gr)o(ated)h(Network)2140 633 y(Mana)o(g)o(ement)p Fe(,)e(Seattle,)d(W)-9 b(A,)17 b(May)j(2001.)p Black 2011 726 a([5])p Black 42 w(M.)29 b(Chen,)g(A.)g(Accardi,)g(E.)f (K\021c\021man,)h(J.)g(Llo)o(yd,)g(D.)g(P)o(atterson,)2140 817 y(A.)e(F)o(ox,)h(and)h(E.)f(Bre)n(wer)l(.)56 b(P)o(ath-based)29 b(F)o(ailure)e(and)i(Ev)o(olution)2140 908 y(Management.)69 b(In)32 b Fb(Pr)m(oceedings)g(of)g(the)g(F)m(ir)o(st)e(Symposium)j(on) 2140 1000 y(Network)o(ed)18 b(Systems)g(Design)g(and)g(Implementation)h (\(NSDI\))p Fe(,)e(San)2140 1091 y(Francisco,)i(CA,)f(2004.)p Black 2011 1184 a([6])p Black 42 w(M.)29 b(Chen,)g(E.)g(K\021c\021man,) g(E.)f(Fratkin,)g(E.)h(Bre)n(wer)m(,)f(and)i(A.)f(F)o(ox.)2140 1275 y(Pinpoint:)d(Problem)g(Determination)h(in)f(Lar)o(ge,)f(Dynamic)i (Inter)o(-)2140 1367 y(net)g(Services.)53 b(In)27 b Fb(International)i (Computer)e(P)-6 b(erformance)29 b(and)2140 1458 y(Dependability)20 b(Symposium)p Fe(,)g(2002.)p Black 2011 1551 a([7])p Black 42 w(J.)e(Choi,)h(M.)g(Choi,)f(and)i(S.)e(Lee.)27 b(An)19 b(alarm)f(correlation)i(and)f(f)o(ault)2140 1643 y(identi\002cation)h(scheme)h(based)h(on)e(OSI)g(managed)i(object)e (classes.)2140 1734 y(In)d Fb(IEEE)f(International)i(Confer)m(ence)h (on)e(Communications)p Fe(,)i(V)-8 b(an-)2140 1825 y(couv)o(er)m(,)19 b(BC,)f(Canada,)i(1999.)p Black 2011 1918 a([8])p Black 42 w(G.)32 b(F)-6 b(.)32 b(Cooper)l(.)71 b(A)32 b(simple)h(algorithm)g (for)f(ef)n(\002ciently)h(mining)2140 2010 y(observ)n(ational)i (databases)h(for)e(causal)g(relationships.)76 b Fb(J)n(ournal)2140 2101 y(of)21 b(Data)f(Mining)i(and)g(Knowledg)o(e)g(Disco)o(very)p Fe(,)f(1\(1-2\):245\226271,)2140 2192 y(1997.)p Black 2011 2285 a([9])p Black 42 w(H.)14 b(P)-8 b(.)14 b(Corporation.)k(HP)d (Open)m(vie)n(w)-5 b(.)19 b Fa(http://www.hp.com/)2140 2377 y(openview/index.html)p Fe(.)p Black 1974 2470 a([10])p Black 42 w(G.)d(H.)g(John,)i(R.)e(K)m(oha)o(vi)i(and)f(K.)f(P\003e)o (ger.)22 b(Irrele)n(v)n(ant)c(features)f(and)2140 2561 y(the)24 b(subset)g(selection)h(problem.)43 b Fb(Mac)o(hine)26 b(Learning:)e(Pr)m(oceed-)2140 2652 y(ings)k(of)g(the)g(Ele)o(venth)g (International)h(Confer)m(ence)p Fe(,)g(pages)g(121\226)2140 2744 y(129,)19 b(1994.)p Black 1974 2837 a([11])p Black 42 w(B.)e(Gruschk)o(e.)26 b(A)17 b(ne)n(w)h(approach)i(for)d(e)n(v)o (ent)i(correlation)f(based)h(on)2140 2928 y(dependenc)o(y)24 b(graphs.)36 b(In)22 b Fb(5th)f(W)-7 b(orkshop)24 b(of)d(the)h(OpenV)-6 b(ie)o(w)22 b(Uni-)2140 3019 y(ver)o(sity)d(Association)p Fe(,)g(1998.)p Black 1974 3112 a([12])p Black 42 w(I.)k(Guyon)j(and)f (A.)e(Elisseef)n(f.)43 b(An)25 b(introduction)g(to)f(v)n(ariable)h(and) 2140 3204 y(feature)c(selection.)34 b Fb(JMLR)21 b(Special)g(Issue)h (on)f(V)-8 b(ariable)21 b(and)h(F)-6 b(ea-)2140 3295 y(tur)m(e)19 b(Selection)p Fe(,)g(3\(Mar\):1157-1182,)j(2003.)p Black 1974 3388 a([13])p Black 42 w(I.)e(H.)h(W)m(itten)f(and)i(E.)e (Frank.)35 b Fb(Data)21 b(Mining:)h(Pr)o(actical)f(mac)o(hine)2140 3479 y(learning)31 b(tools)g(with)f(J)m(ava)i(implementations)p Fe(.)64 b(Mor)o(gan)31 b(Kauf-)2140 3571 y(mann.)p Black 1974 3664 a([14])p Black 42 w(I.)j(Rish)h(and)h(M.)e(Brodie)h(and)h(N.) e(Odintso)o(v)n(a)i(and)g(S.)e(Ma,)h(G.)2140 3755 y(Grabarnik.)47 b(Real-time)25 b(problem)h(determination)f(in)g(distrib)o(uted)2140 3846 y(systems)i(using)h(acti)n(v)o(e)g(probing.)54 b(In)27 b Fb(Network)g(Oper)o(ations)i(and)2140 3938 y(Mana)o(g)o(ement)21 b(Systems)p Fe(,)e(2004.)p Black 1974 4031 a([15])p Black 42 w(I.)d(Rish,)h(M.)g(Brodie,)f(and)i(S.)e(Ma.)23 b(Accurac)o(y)18 b(vs.)f(ef)n(\002cienc)o(y)g(trade-)2140 4122 y(of)n(fs)g(in)f (probabilistic)i(diagnosis.)23 b(In)17 b Fb(AAAI-2002,)f(Edmonton,)h (Al-)2140 4214 y(berta,)i(Canada)p Fe(,)h(2002.)p Black 1974 4307 a([16])p Black 42 w(IBM.)44 b(T)m(i)n(v)o(oli)24 b(Business)h(Systems)f(Manager,)h(2001.)46 b Fa(http://)2140 4398 y(www.tivoli.com)p Fe(.)p Black 1974 4491 a([17])p Black 42 w(J.)19 b(R.)g(Quinlan.)29 b Fb(C4.5:)19 b(Pr)m(o)o(gr)o(ams)h (for)g(Mac)o(hine)g(Learning)p Fe(.)30 b(Mor)o(-)2140 4582 y(gan)19 b(Kaufmann,)h(1993.)p Black 1974 4675 a([18])p Black 42 w(J.)c(Pearl.)k Fb(Causality:)d(Models,)f(Reasoning)o(,)i(and) f(Infer)m(ence)p Fe(.)23 b(Cam-)2140 4767 y(bridge)c(Uni)n(v)o(ersity)h (Press,)e(2000.)p Black 1974 4860 a([19])p Black 42 w(M.)f(Steinder)h (and)g(A.)f(Sethi.)23 b(End-to-end)c(service)f(f)o(ailure)f(diagno-) 2140 4951 y(sis)j(using)i(belief)e(netw)o(orks.)33 b(In)21 b Fb(Network)g(Oper)o(ations)g(and)h(Man-)2140 5042 y(a)o(g)o(ement)e (Symposium)p Fe(,)g(2002.)p Black 1974 5135 a([20])p Black 42 w(A.)e(Y)-7 b(emini)18 b(and)h(S.)e(Kliger)l(.)26 b(High)18 b(speed)i(and)f(rob)o(ust)f(e)n(v)o(ent)h(corre-)2140 5227 y(lation.)42 b Fb(IEEE)23 b(Communication)i(Ma)o(gazine)p Fe(,)g(34\(5\):82\22690,)h(May)2140 5318 y(1996.)p Black Black eop %%Trailer end userdict /end-hook known{end-hook}if %%EOF