CR-precis: A Deterministic Summary Structure for Update Data Streams
CR-precis: A Deterministic Summary Structure for Update Data Streams
复制标题
DOI：
10.1007/978-3-540-74450-4_5
复制
发表时间：
2006-09
影响因子：
--
通讯作者：
Sumit Ganguly;Anirban Majumder
中科院分区：
文献类型：
--
作者：
Sumit Ganguly;Anirban Majumder
我们提出了解决更新数据流问题的确定性亚线性空间算法，包括估计项和范围的频率、寻找近似频繁项和近似φ分位数、估计内积、构造近最优B桶直方图和估计熵。我们还提出了改进的下界结果更新数据流的几个问题。
We present deterministic sub-linear space algorithms for problems over update data streams, including, estimating frequencies of items and ranges, finding approximate frequent items and approximateφ-quantiles, estimating inner-products, constructing near-optimalB-bucket histograms and estimating entropy. We also present improved lower bound results for several problems over update data streams.