Papers Robust Aggregation in Sensor Networks Shrivastava04 Nisheeth Shrivastava Chiranjeeb Buragohain Divy Agrawal Subhash Suri Medians and Beyond New Aggregation Techniques for Sensor Networks ACM SenSys 04 Nov 3 5 Baltimore MD Nath04 Suman Nath Phillip B Gibbons Zachary Anderson and Srinivasan Seshan Synopsis Diffusion for Robust Aggregation in Sensor Networks In proceedings of ACM SenSys 04 Considine04 Jeffrey Considine Feifei Li George Kollios and John Byers Approximate Aggregation Techniques for Sensor Databases Proc ICDE 2004 Przydatek03 Bartosz Przydatek Dawn Song Adrian Perrig SIA Secure Information Aggregation in Sensor Networks Sensys 03 Jie Gao Computer Science Department Stony Brook University 10 25 05 Jie Gao CSE590 fall05 1 10 25 05 Problem I median Jie Gao CSE590 fall05 2 Problem I median Computing average is simple on an aggregation tree Each node x stores the average a x and the number of nodes in its subtree n x The average of a node x can be computed from its children u v n x n u n v a x a u n u a v n v n x Computing the median with a fixed amount of message is hard We do not know the rank of u s median in v s dataset We resort to approximations x u 10 25 05 Jie Gao CSE590 fall05 3 10 25 05 Median and random sampling Jie Gao CSE590 fall05 v 4 Quantile digest q q digest Problem compute the median a of n unsorted elements ai Take a random sample of k elements Compute the median x Claim x has rank within n and n with probability at least 1 2 exp 2k 2 Proof left as an exercise Choose k ln 2 2 2 then x is an approximate median with probability 1 A deterministic algorithm How about approximate histogram What if a sensor generates a list of values 10 25 05 Jie Gao CSE590 fall05 5 A data structure that answers Approximate quantile query median the kth largest reading Range queries the kth to lth largest readings Most frequent items Histograms Properties 10 25 05 Deterministic algorithm Error memory trade off Confidence factor Support multiple queries Jie Gao CSE590 fall05 6 1 Q digest Example Exact data frequency of data value f1 f2 f Compress the data Input data bucketed Buckets the nodes in a binary partition of the range 1 Each bucket v has range v min v max Only store non zero buckets Digest property Count v n k except leaf Count v Count p Count s n k except root parent 10 25 05 Information loss sibling Jie Gao CSE590 fall05 7 10 25 05 Each sensor constructs a qdigest based on its value Check the digest property bottom up two small children s count are added up and moved to the parent Information loss t undercounts since some of its value appears on ancestors Jie Gao CSE590 fall05 9 10 25 05 Space complexity and error bound Count v Count p Count s Q n k 3 v QCount v 3n v Q Count v Count p Count s Q 3k 2 10 Given q 0 1 find the value whose rank is qn Relative error r qn n where r is the true rank v Q Any value that should be counted in v can be present in one of the ancestors Count v has max error log n k 1 Jie Gao CSE590 fall05 Median and quantile query A q digest with compression parameter k has at most 3k buckets By property 2 for buckets Q 8 Merge q digests from two children Add up the values in buckets Re evaluate the digest property bottom up 10 25 05 1 Jie Gao CSE590 fall05 Merging two qq digests Construct a qq digest Q digest detailed information concerning frequent data are preserved less frequently occurring values are lumped into larger buckets resulting in information loss Error v ancestor p Count p ancestor p n k log n k MERGE maintains the same relative error 10 25 05 Error v i Error vi i log ni k Jie Gao CSE590 fall05 log n k 11 Post order traversal on Q sum the counts of all nodes visited before a node v which is the lower bound on the of values less than v max Report it when it is first time larger than qn Error bound log k 3log m where m 3k is the storage bound for each sensor 10 25 05 Jie Gao CSE590 fall05 12 2 Simulation setup Other queries Inverse quantile given a value determine its rank Traverse the tree in post order report the sum of counts v for which x v max which is within rank x rank x n A typical aggregation tree BFS tree on 40 nodes in a 200 by 200 area In the simulation they use 4000 8000 nodes Range query find values in range l h Perform two inverse quantile queries and take the difference Error bound is 2 n Frequent items given s 0 1 find all values reported by more than sn sensors Count the leaf buckets whose counts are more than sn Small false positive values with count between s n and sn may also be reported as frequent 10 25 05 Jie Gao CSE590 fall05 13 10 25 05 Simulation setup Jie Gao CSE590 fall05 15 Comparison of histogram and q digest 10 25 05 Tradeoff between error and msg size 10 25 05 Jie Gao CSE590 fall05 14 Histogram v s qq digest Random data Correlated data 3D elevation value from Death Valley 10 25 05 Jie Gao CSE590 fall05 Jie Gao CSE590 fall05 16 Saving on message size 17 10 25 05 Jie Gao CSE590 fall05 18 3 Problem II Aggregation along a spanning tree in practice Problem II Aggregation along a spanning tree in practice The impact of link dynamics on aggregation tree If a link fails the data from the entire subtree is lost Solution use multi path routing e g DAG to improve robustness under link dynamics But if both paths succeed the the same data is received twice This is ok for some aggregation such as MAX MIN How about Count SUM Wrong aggregated value Inconsistency 10 25 05 Jie Gao CSE590 fall05 19 10 25 05 Problem with spanning tree Link dynamics If a link fails the data from the entire subtree is lost Decouple routing and data aggregation Use multi path routing to improve the routing robustness If multiple paths succeed the sink receives multiple copies of the same data Design an aggregation algorithm that is insensitive to order and duplications 10 25 05 Jie Gao CSE590 fall05 21 Output the value itself Synopsis fusion SF Take the MAX MIN of the two input values Synopsis evaluation SE Jie Gao CSE590 fall05 5 Jie Gao CSE590 fall05 20 10 25 05 Jie Gao CSE590 fall05 22 ODI correctness SE SF A synopsis diffusion algorithm is ODI correct if SF and SG are order and duplicate insensitive functions Or if for any aggregation DAG the resulting synopsis is identical to the synopsis produced by the canonical left deep tree SG Output …