English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

Frequency estimation data structures such as the count-min sketch (CMS) havefound numerous applications in databases, networking, computational biology andother domains. Many applications that use the count-min sketch process massiveand rapidly evolving datasets. For data-intensive applications that aim to keepthe overestimate error low, the count-min sketch may become too large to storein available RAM and may have to migrate to external storage (e.g., SSD.) Dueto the random-read/write nature of hash operations of the count-min sketch,simply placing it on SSD stifles the performance of time-critical applications,requiring about 4-6 random reads/writes to SSD per estimate (lookup) and update(insert) operation.  In this paper, we expand on the preliminary idea of the Buffered Count-MinSketch (BCMS) [15], an SSD variant of the count-min sketch, that used hashlocalization to scale efficiently out of RAM while keeping the total errorbounded. We describe the design and implementation of the buffered count-minsketch, and empirically show that our implementation achieves 3.7x-4.7x thespeedup on update (insert) and 4.3x speedup on estimate (lookup) operations.  Our design also offers an asymptotic improvement in the external-memory model[1] over the original data structure: r random I/Os are reduced to 1 I/O forthe estimate operation. For a data structure that uses k blocks on SSD, was theword/counter size, r as the number of rows, M as the number of bits in the mainmemory, our data structure uses kwr/M amortized I/Os for updates, or, if kwr/M>1, 1 I/O in the worst case. In typical scenarios, kwr/M is much smaller than1. This is in contrast to O(r) I/Os incurred for each update in the originaldata structure.

Buffered Count-Min Sketch on SSD: Theory and Experiments