Границы аппроксимирующих частотных моментов

Пусть - последовательность целых чисел, где каждый . Для , пусть, - й момент частоты определяется какa 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.$

В своей известной работе «Пространственная сложность аппроксимации частотных моментов» Alon et al. дать алгоритм потоковой передачи, который приближает используя примерно пространство. Они также используют методы сложности связи для получения нижней границы для . Для они обеспечивают более или менее совпадающие верхнюю и нижнюю границы. O ( n 1 - $F_k$Ω(n1-$O(n^{1-\frac{1}{k}}(\log n + \log m))$k>5k=0,1,$\Omega(n^{1-\frac{5}{k}})$$k > 5$$k = 0,1,2$

Были ли улучшения этих границ с тех пор, и был ли прогресс для ?$k = 3,4,5$

Там был значительный прогресс. В конкретной задаче существует верхняя и нижняя границы для . Верхние границы взяты из этой работы Indyk и Woodruff (которая появилась в STOC 2005), а нижние границы - через структуру информационной сложности, благодаря Bar-Yossef et al. И Chakrabarti et al .n 1 - 2 / k k > $F_k$$n^{1-2/k}$$k > 2$

Для к <= 2

1) k = 0, предел равен с http://people.seas.harvard.edu/~minilek/papers/f0.pdf .$O(1/\epsilon^2+log(n))$

2) k = 1. В работе Алона и др. Содержится ссылка на статью Морриса, которая занимает пространство.$\tilde{O}(log(log(n))$

3) k = 2, я думаю, что эскиз AMS из их бумаги является оптимальным

Нечто связанное.

Я думаю, что была также некоторая связанная работа по приближению где не обязательно является целым числом. http://www.stat.cornell.edu/~li/SODA09_CC.pdf - это то, о чем я знаю. Я не совсем знаком с этим, но я думаю, что их основной интерес представляет зависимость от а не . α ϵ $F_\alpha$$\alpha$$\epsilon$$n$