数据流挖掘与查询

DataStreamMiningandQueryingSlidestakenfromanexcellentTutorialonDataStreamMiningandQueryingbyMinosGarofalakis,

JohannesGehrkeandRajeevRastogi

AndbyMino’slecturesslidesfromthere:/cs286sp07/ProcessingDataStreams:MotivationAgrowingnumberofapplicationsgeneratestreamsofdataPerformancemeasurementsinnetworkmonitoringandtrafficmanagementCalldetailrecordsintelecommunicationsTransactionsinretailchains,ATMoperationsinbanksLogrecordsgeneratedbyWebServersSensornetworkdataApplicationcharacteristicsMassivevolumesofdata(severalterabytes)RecordsarriveatarapidrateGoal:Minepatterns,processqueriesandcomputestatisticsondatastreamsinreal-timeDataStreams:ComputationModelAdatastreamisa(massive)sequenceofelements:

StreamprocessingrequirementsSinglepass:EachrecordisexaminedatmostonceBoundedstorage:LimitedMemory(M)forstoringsynopsisReal-time:Perrecordprocessingtime(tomaintainsynopsis)mustbelowStreamProcessingEngine(Approximate)AnswerSynopsisinMemoryDataStreamsDataStreamProcessingAlgorithmsGenerally,algorithmscomputeapproximateanswersDifficulttocomputeanswersaccuratelywithlimitedmemoryApproximateanswers-DeterministicboundsAlgorithmsonlycomputeanapproximateanswer,butboundsonerrorApproximateanswers-ProbabilisticboundsAlgorithmscomputeanapproximateanswerwithhighprobabilityWithprobabilityatleast,thecomputedansweriswithinafactoroftheactualanswerSingle-passalgorithmsforprocessingstreamsalsoapplicableto(massive)terabytedatabases!

Sampling:BasicsIdea:AsmallrandomsampleSofthedataoftenwell-representsallthedataForafastapproxanswer,apply“modified”querytoSExample:selectaggfromRwhereR.eisodd

(n=12)

Ifaggisavg,returnaverageofoddelementsinSIfaggiscount,returnaverageoverallelementseinSofnifeisodd0ifeisevenUnbiased:Forexpressionsinvolvingcount,sum,avg:theestimatorisunbiased,i.e.,theexpectedvalueoftheansweristheactualanswerDatastream:935271658491SampleS:9518answer:5answer:12*3/4=9ProbabilisticGuaranteesExample:Actualansweriswithin5±1withprob0.9UseTailInequalitiestogiveprobabilisticboundsonreturnedanswerMarkovInequalityChebyshev’sInequalityHoeffding’sInequalityChernoffBoundTailInequalitiesGeneralboundsontailprobabilityofarandomvariable(thatis,probabilitythatarandomvariabledeviatesfarfromitsexpectation)

BasicInequalities:LetXbearandomvariablewithexpectationandvarianceVar[X].ThenforanyProbabilitydistributionTailprobabilityMarkov:Chebyshev:TailInequalitiesforSumsPossibletoderivestrongerboundsontailprobabilitiesforthesumofindependentrandomvariablesHoeffding’sInequality:LetX1,...,Xmbeindependentrandomvariableswith0<=Xi<=r.Letandbetheexpectationof.Then,foranyApplicationtoavgqueries:missizeofsubsetofsampleSsatisfyingpredicate(3inexample)risrangeofelementvaluesinsample(8inexample)TailInequalitiesforSums(Contd.)PossibletoderiveevenstrongerboundsontailprobabilitiesforthesumofindependentBernoullitrialsChernoffBound:LetX1,...,XmbeindependentBernoullitrialssuchthatPr[Xi=1]=p(Pr[Xi=0]=1-p).Letandbetheexpectationof.Then,forany,Applicationtocountqueries:missizeofsampleS(4inexample)pisfractionofoddelementsinstream(2/3inexample)

Remark:ChernoffboundresultsintighterboundsforcountqueriescomparedtoHoeffding’sinequalityComputingStreamSampleReservoirSampling[Vit85]:

MaintainsasampleSofafixed-sizeMAddeachnewelementtoSwithprobabilityM/n,wherenisthecurrentnumberofstreamelementsIfaddanelement,evictarandomelementfromSInsteadofflippingacoinforeachelement,determinethenumberofelementstoskipbeforethenexttobeaddedtoSConcisesampling[GM98]:DuplicatesinsampleSstoredas<value,count>pairs(thus,potentiallyboostingactualsamplesize)AddeachnewelementtoSwithprobability1/T(simplyincrementcountifelementalreadyinS)IfsamplesizeexceedsMSelectnewthresholdT’>TEvicteachelement(decrementcount)fromSwithprobability1-T/T’AddsubsequentelementstoSwithprobability1/T’StreamingModel:SpecialCases

Time-SeriesModelOnlyj-thupdateupdatesA[j](i.e.,A[j]:=c[j])

Cash-RegisterModelc[j]isalways>=0(i.e.,increment-only)Typically,c[j]=1,soweseeamulti-setofitemsinonepass

TurnstileModelMostgeneralstreamingmodelc[j]canbe>0or<0(i.e.,incrementordecrement)

ProblemdifficultyvariesdependingonthemodelE.g.,MIN/MAXinTime-Seriesvs.Turnstile!Linear-Projection(akaAMS)SketchSynopsesGoal:Buildsmall-spacesummaryfordistributionvectorf(i)(i=1,...,N)seenasastreamofi-valuesBasicConstruct:

RandomizedLinearProjectionoff()=projectontoinner/dotproductoff-vectorSimpletocomputeoverthestream:Addwheneverthei-thvalueisseenGenerate‘sinsmall(logN)spaceusingpseudo-randomgeneratorsTunableprobabilisticguaranteesonapproximationerrorDelete-Proof:Justsubtracttodeleteani-thvalueoccurrenceComposable:Simplyaddindependently-builtprojectionsDatastream:3,1,2,4,2,3,5,...Datastream:3,1,2,4,2,3,5,...f(1)f(2)f(3)f(4)f(5)11122where=vectorofrandomvaluesfromanappropriatedistributionExample:Binary-JoinCOUNTQueryProblem:ComputeanswerforthequeryCOUNT(RAS)Example:Exactsolution:tooexpensive,requiresO(N)space!N=sizeof(domain(A))DatastreamR.A:41241412032134DatastreamS.A:31242412213421=10(2+2+0+6)BasicAMSSketchingTechnique[AMS96]KeyIntuition:Userandomizedlinearprojectionsoff()todefinerandomvariableXsuchthatXiseasilycomputedoverthestream(insmallspace)E[X]=COUNT(RAS)Var[X]issmall

BasicIdea:Defineafamilyof4-wiseindependent{-1,+1}randomvariables

Pr[=+1]=Pr[=-1]=1/2Expectedvalueofeach,E[]=0Variablesare4-wiseindependentExpectedvalueofproductof4distinct=0Variablescanbegeneratedusingpseudo-randomgeneratorusingonlyO(logN)space(forseeding)!Probabilisticerrorguarantees(e.g.,actualansweris10±1withprobability0.9)AMSSketchConstructionComputerandomvariables:andSimplyaddtoXR(XS)wheneverthei-thvalueisobservedintheR.A(S.A)streamDefineX=XRXStobeestimateofCOUNTqueryExample:DatastreamR.A:412414DatastreamS.A:3124241202134122134213Binary-JoinAMSSketchingAnalysisExpectedvalueofX=COUNT(RAS)

Using4-wiseindependence,possibletoshowthat

isself-joinsizeofR(second/L2moment)01BoostingAccuracyChebyshev’sInequality:

BoostaccuracytobyaveragingoverseveralindependentcopiesofX(reducesvariance)

ByChebyshev:xxxAverageyBoostingConfidenceBoostconfidencetobytakingmedianof2log(1/)independentcopiesofYEachY=BernoulliTrial

Pr[|median(Y)-COUNT|COUNT](ByChernoffBound)=Pr[#failuresin2log(1/)trials>=log(1/)]yyycopiesmedian2log(1/)“FAILURE”:SummaryofBinary-JoinAMSSketchingStep1:Computerandomvariables:andStep2:DefineX=XRXSSteps3&4:AverageindependentcopiesofX;Returnmedianofaverages

MainTheorem(AGMS99):SketchingapproximatesCOUNTtowithinarelativeerrorofwithprobabilityusingspace

Remember:O(logN)spacefor“seeding”theconstructionofeachX

xxxAverageyxxxAverageyxxxAverageycopiescopiesmedian2log(1/)ASpecialCase:Self-joinSizeEstimateCOUNT(RAR)(originalAMSpaper)Second(L2)momentofdatadistribution,Giniindexofheterogeneity,measureofskewinthedata

Inthiscase,COUNT=SJ(R),sowegetan(e,d)-estimateusingspaceonly

Best-caseforAMSstreamingjoin-sizeestimationDistinctValueEstimationProblem:Findthenumberofdistinctvaluesinastreamofvalueswithdomain[0,...,N-1]Zerothfrequencymoment,L0(Hamming)streamnormStatistics:numberofspeciesorclassesinapopulationImportantforqueryoptimizersNetworkmonitoring:distinctdestinationIPaddresses,source/destinationpairs,requestedURLs,etc.Example(N=64)Datastream:305301751037Numberofdistinctvalues:5Assumeahashfunctionh(x)thatmapsincomingvaluesxin[0,…,N-1]uniformlyacross[0,…,2^L-1],whereL=O(logN)Letlsb(y)denotethepositionoftheleast-significant1bitinthebinaryrepresentationofyAvaluexismappedtolsb(h(x))MaintainHashSketch=BITMAParrayofLbits,initializedto0Foreachincomingvaluex,setBITMAP[lsb(h(x))]=1Hash(akaFM)SketchesforDistinctValueEstimation[FM85]x=5h(x)=101100lsb(h(x))=2000001BITMAP543210Hash(akaFM)SketchesforDistinctValueEstimation[FM85]Byuniformitythroughh(x):Prob[BITMAP[k]=1]=Prob[]=Assumingddistinctvalues:expectd/2tomaptoBITMAP[0],d/4tomaptoBITMAP[1],...LetR=positionofrightmostzeroinBITMAPUseasindicatoroflog(d)[FM85]provethatE[R]=,whereEstimated=Averageseveraliidinstances(differenthashfunctions)toreduceestimatorvariancefringeof0/1saroundlog(d)000001BITMAP000111111111position<<log(d)position>>log(d)0L-1[FM85]assume“ideal”hashfunctionsh(x)(N-wiseindependence) [AMS96]:pairwiseindependenceissufficienth(x)=,wherea,barerandombinaryvectorsin[0,…,2^L-1]Small-spaceestimatesfordistinctvaluesproposedbasedonFMideasDelete-Proof:Justusecountersinsteadofbitsinthesketchlocations+1forinserts,-1fordeletesComposable:Compon