Max{stable sketches: estimation of `®¡norms, dominance norms and point queries for non{negative signals

Let f: f1; 2; : : : ; Ng! [0;1) be a non{negative signal, de¯ned over a very large domain and suppose that we want to be able to address approximate aggregate queries or point queries about f. To answer queries about f, we introduce a new type of random sketches called max{stable sketches. The (ideal precision) max{stable sketch of f, Ej(f); 1 · j · K, is de¯ned as: Ej(f): = max 1·i·N f(i)Zj(i); 1 · j · K; where the KN random variables Zj(i)'s are independent with standard ®¡Fr¶echet dis-tribution, that is, PfZj(i) · xg = expf¡x¡®g; x> 0, where ® is an arbitrary positive parameter. Max{stable sketches are particularly natural when dealing with maximally updated data streams, logs of record events and dominance norms or relations between large signals. By using only max{stable sketches of relatively small size K << N, we can compute in small space and time: (i) the `®¡norm, ®> 0, of the signal (ii) the distanc