Patent ID: 8195710
Filing Date: 2012-06-05
Classification: H04L

Abstract:
1. A method for producing a summary A of data points in an unaggregated data stream wherein the data points are in the form of weighted keys (a, w) where a is a key and w is a weight, and the summary is a sample of k keys a with adjusted weights w a , where k is a finite integer, comprising: a. forming a first reservoir L and a second reservoir T which are initially empty; b. providing a threshold τ whose initial value is zero; c. merging data points in the stream into the reservoir L until the reservoir L contains k keys by examining each new data point and if the key a of that data point is not already in reservoir L, then adding it to reservoir L, and if the key a of that data point is already in reservoir L, then updating the adjusted weight for that key to w d. storing the keys in reservoir L in a priority queue which identifies the key b with the minimum adjusted weight of the keys in reservoir L[arg min e. examining the next data point and f. repeating steps d and e until the data stream desired to be summarized ends; and g. providing the summary A of data points as A=L∪T , with the keys included in L and T being assigned adjusted weights ŵ