Distributions stables, générateurs pseudorandom, embeddings et calcul de flux de données

Dans cet article, nous montrons plusieurs résultats obtenus en combinant l'utilisation de distributions stables avec des générateurs pseudorandom pour un espace borné. En particulier : nous démontrons comment maintenir (en utilisant seulement O(log n//spl epsiv//sup 2/) mots de stockage) un sketch C(p) d'un point p/spl isin/l/sub 1//sup n/ sous des mises à jour dynamiques de ses coordonnées, de sorte qu'étant donné les sketches C(p) et C(q), on peut estimer |p-q|/sub 1/ jusqu'à un facteur de (1+/spl epsiv/) avec une grande probabilité. Nous obtenons une autre fonction de sketch C' qui mappe l/sub 1//sup n/ dans un espace normé l/sub 1//sup m/ (contrairement à C), tel que m=m(n) est beaucoup plus petit que n ; à notre connaissance, ceci est le premier lemme de réduction de dimension pour la norme l/sub 1/ ; nous donnons un embedding explicite de l/sub 2//sup n/ dans l/sub l//sup nO(log n)/ avec une distorsion (1+1/n/sup /spl theta/(1)/) et un embedding non constructif de l/sub 2//sup n/ dans l/sub 1//sup O(n)/ avec une distorsion (1+/spl epsiv/) tel que l'embedding peut être représenté en utilisant seulement O(n log/sup 2/ n) bits (contrairement à au moins n/sup 2/ utilisés par des méthodes antérieures).