Limites des moments de fréquence approximatifs

Soit une séquence d'entiers où chacun . Pour , soit. Le ème moment de fréquence est défini comme étanta j ∈ { 1 , 2 , … , n } i ∈ { 1 , 2 , … , n } m i = | { j : a j = i } | $a_1, a_2,\dotsc, a_m$$a_j \in \{1,2,\dotsc,n\}$$i \in \{1,2,\dotsc,n\}$$m_i = |\{j : a_j = i\}|$$k$

$\displaystyle F_k = \sum_{i=1}^n m_i^k.$

Dans leur article bien connu, La complexité spatiale de l'approximation des moments de fréquence , Alon et al. donner un algorithme de streaming qui se rapproche de utilisant approximativement l' . Ils utilisent également des techniques de complexité de communication pour obtenir une limite inférieure de pour . Pour , ils fournissent des bornes supérieure et inférieure plus ou moins concordantes. O ( n 1 - $F_k$$O(n^{1-\frac{1}{k}}(\log n + \log m))$$\Omega(n^{1-\frac{5}{k}})$$k > 5$$k = 0,1,2$

Y a-t-il eu des améliorations à ces bornes depuis lors, et y a-t-il eu des progrès pour ?$k = 3,4,5$

Il y a eu pas mal de progrès. Sur le problème spécifique de , il existe une limite supérieure et inférieure correspondante de n 1 - 2 / k pour k > 2 . Les limites supérieures proviennent de cet article d'Indyk et Woodruff (paru dans STOC 2005) et les limites inférieures sont via le cadre de complexité de l'information, en raison de Bar-Yossef et al et Chakrabarti et al .$F_k$$n^{1-2/k}$$k > 2$

Pour k <= 2

1) k = 0, la limite est de http://people.seas.harvard.edu/~minilek/papers/f0.pdf .$O(1/\epsilon^2+log(n))$

2) k = 1, l'article d'Alon et all fait référence à l'article de Morris qui prend un espace de .$\tilde{O}(log(log(n))$

3) k = 2, je pense que le croquis AMS de leur papier est optimal

Quelque chose de lié.

$F_\alpha$$\alpha$$\epsilon$$n$