文档介绍：The Story Begins with ... The Model 1421345235212 Alice observes A(t) by time t Bob observes B(t ) by time tA(t), B (t ): multisets Carole tries pute f (A(t)UB(t )) for all t All parties have puting power Goal is to munication t The Model 1421345235212231313253322 k sites munication Model / Distributed Streaming bination of Two Models 31 124 231 124 munication model 14213 Streaming model munication Model Distributed Streaming Model One-shot Model “” Other Models [Gibbons and Tirthapura , 2001] 1421345235212 Carole tries pute f (AUB) in the end All parties make one pass using small memory ? small communication t Applied Motivation: Distributed Monitoring ? Large-scale querying/monitoring: Inherently distributed! ? Streams physically distributed across remote sites ., stream of UDP packets through routers ? Challenge is “ holistic ” querying/monitoring ? Queries over the union of distributed streams Q(S 1 ∪S 2 ∪…) ? Streaming data is spread throughout work Operations Center (NOC) Query site Query 0 11 1 10 01 1 0 0 110 11 0 110 11 Q(S 1∪S 2∪…)S 6S 5S 4S 3S 1S 2 Slide from the tutorial “ Streaming in a connected world: Querying and tracking distributed data streams ” at VLDB ’ 06 and SIGMOD ’ 07 [ Cormode and Garofalakis ] Applied Motivation: Distributed Monitoring ? Traditional approach: “ pull ” based ? Query all nodes once for a while ? munication, most is wasted ? urate ? Current trend: moving towards a “ push ” based approach ? The remote sites alert the coordinator when something interesting work Operations Center (NOC) Query site Query 0 11 1 10 01 1 0 0 110 11 0 110 11 Q(S 1∪S 2∪…)S 6S 5S 4S 3S 1S 2 Theoretical Questions ? Upper bounds: Worst-munication bounds for a given f ? ? Lower bounds: Is there a gap in the plexity between the one-shot model and the continuous model? The Frequency Moments ? Assume integer domain [ n ] = { 1, …, n} ?i appears m i times ? The p- th frequency moment: ?F 1 is the cardinality of A ?F 0