Paper Info
Title
Join-distinct aggregate estimation over update streams
Abstract
There is growing interest in algorithms for processing andquerying continuous data streams (i.e., data that is seenonly once in a fixed order) with limited memory resources.Providing (perhaps approximate) answers to queries over suchstreams is a crucial requirement for many application environments;examples include large IP network installations where performancedata from different parts of the network needs to be continuouslycollected and analyzed.The ability to estimate the number of distinct (sub)tuples inthe result of a join operation correlating two data streams (i.e.,the cardinality of a projection with duplicate elimination over ajoin) is an important requirement for several data-analysisscenarios. For instance, to enable real-time traffic analysis andload balancing, a network-monitoring application may need toestimate the number of distinct (source,destination) IP-address pairs occurring in the stream of IP packetsobserved by router R1,where the source address is also seen in packets routed through adifferent router R2.Earlier work has presented solutions to the individual problems ofdistinct counting and join-size estimation (without duplicateelimination) over streams. These solutions, however, arefundamentally different and extending or combining them to handleour more complex "Join-Distinct" estimation problem is far fromobvious. In this paper, we propose the firstspace-efficient algorithmic solution to the general Join-Distinctestimation problem over continuous data streams (our techniques canactually handle general update streamscomprising tuple deletions as well as insertions). Our estimatorsare probabilistic in nature and rely on novel algorithms forbuilding and combining a new class of hash-based synopses (termed"JD sketches") for individual update streams. Wedemonstrate that our algorithms can provide low error,high-confidence Join-Distinct estimates using only small space andsmall processing time per update. In fact, we present lower boundsshowing that the space usage of our estimators is within smallfactors of the best possible for the Join-Distinct problem.Preliminary experimental results verify the effectiveness of ourapproach.
Year
DOI
Venue
2005
10.1145/1065167.1065200
PODS
Keywords
Field
DocType
andquerying continuous data stream,continuous data stream,general join-distinctestimation problem,individual update stream,estimation problem,individual problem,high-confidence join-distinct,join-distinct problem,join-distinct aggregate estimation,general update,data stream,consistency,concurrency control,two phase locking,anomaly,network monitoring,snapshot isolation,serializability
Data stream mining,Traffic analysis,Computer science,Tuple,Network packet,Cardinality,Theoretical computer science,Hash function,Router,Probabilistic logic
Conference
ISBN
Citations 
PageRank 
1-59593-062-0
10
0.60
References 
Authors
17
4
Name
Order
Citations
PageRank
Sumit Ganguly1813236.01
Minos Garofalakis24904664.22
Amit Kumar324017.84
Rajeev Rastogi46151827.22