Patent ID: 8195710

Claim:
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 a ←w a +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 bεL , w b ]; e. examining the next data point and if its key a is already in the reservoir L, then adding its weight to the adjusted weight of the key in the reservoir, and if its key a is already in the reservoir T, then updating its adjusted weight to w a ←τ+w and moving the key a from reservoir T to reservoir L; and if its key a is not already in the reservoir L or in the reservoir T, then performing the following steps: (1). updating the adjusted weight of the key a to w a ←w; (2). forming a third reservoir X which is initially empty; (3). creating a variable smallsum and updating it with the value smallsum←τ*|T|,where |T |is the number of keys in reservoir T; (4). if w>τ, then add a to reservoir L; otherwise add a to reservoir X and update smallsum←smallsum+w; (5). while smallsum≧(|T|+|X|−1)min bεL w b , then do the following: find the key b such that b←arg min bεL w b , move b from L to the end of X, and update smallsum←smallsum+w b ; (6). create a variable t with the value t←smallsum /(|T|+|X|−1); (7). generate a uniformly random number r ε∪(0,1); (8). if r<|T|(1−τ/t), then determine a value d such that d←└r/(1−τ/ t)┘ and remove T[d] from T; otherwise update r ←r−|T|(1−τ/ t), set d←0 and while r>0, update r←r−(1−w x[d] /t), update d←d+1, and remove X[d] from X; (9). update τ←t; (10). update T←T∪X; 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 ŵ a =w a if a εL and ŵ a =τ if a εand all keys not in A being assigned adjusted weights of zero.