This is a search field with an auto-suggest feature attached.
今年の始め、私が Rust を習いはじめのころ、手本となるプログラムがあまり見つからないことが不満でした。GitHub で探せば、Rust で書かれた実用的なライブラリーが数多く見つかりますが、それらを読むのは入門者にとっては敷居が高過ぎます。私が欲しかったのは、学習用に書かれたプログラムで、入門者が手軽に試せて、いろいろといじれるプログラム例でした。 そんなわけで、そういうプログラム例を書いてみようと思います。２回に分けて、Rust で簡単なツールを作ります。 今回は乱択アルゴリズムの一種である、probability cardinarity estimatior（確率的カーディナリティ推定機）を実装します。HyperLogLog という名前のデータ構造です。 次回は HyperLogLog を使って、ウィキペディア日本語版の全記事で使われているユニーク単語数を、プラスマイナス約 2%
A probabilistic data structure for frequency/k-occurrence cardinality estimation of multisets. Sample implementation "How many colours appear n-times?" In the figure above, we first group nodes by colour, then count each occurrence, then regroup on the frequency of those occurrences, finally counting the number of coloured nodes which appeared more than n times. Our HyperLogSandwich is an estimato
本日，PFI セミナーにて「乱択データ構造の最新事情 −MinHash と HyperLogLog の最近の進歩−」というタイトルで話をさせてもらいました．スライドは以下になります． Ustream の録画もあります． http://www.ustream.tv/recorded/48151077 内容としては，以下の操作を効率的に行うための集合に関するデータ構造 (Sketch) の最近の進歩を紹介しました． 集合の類似度の推定 (Jaccard 係数) 集合異なり数の推定 (distinct counting) どちらも重要かつ基礎的な操作で，b-bit MinHash や HyperLogLog など，既に実用的な手法が提案されており，実際にも使われています．しかし，2014 年になって，Odd Sketch や HIP Estimator という，これらをさらに改善する手法が立て続
Sketch of the Day: HyperLogLog — Cornerstone of a Big Data Infrastructure Intro In the Zipfian world of AK, the HyperLogLog distinct value (DV) sketch reigns supreme. This DV sketch is the workhorse behind the majority of our DV counters (and we’re not alone) and enables us to have a real time, in memory data store with incredibly high throughput. HLL was conceived of by Flajolet et. al. in the ph
antirez 4392 days ago. 483973 views. Generally speaking, I love randomized algorithms, but there is one I love particularly since even after you understand how it works, it still remains magical from a programmer point of view. It accomplishes something that is almost illogical given how little it asks for in terms of time or space. This algorithm is called HyperLogLog, and today it is introduced
We’ll look briefly in how you would utilize awesomeness of both Cascalog and HyperLogLog in order to execute Hadoop M/R tasks with amounts of data too big to have them in their original form. Intro HyperLogLog Cardinality estimator allowing you to count amount of distinct values. Cascalog The main use cases for Cascalog are processing "Big Data" on top of Hadoop or doing analysis on your local com
はじめに 「さぁ、お前の罪の異なり数を数えろ！」と言われたときに使えそうな「HyperLogLog」という異なり数をカウントする方法を教えてもらったので、遊んでみた。 いつもながら論文ちゃんと読んでないので、条件やコード間違ってるかも。。。 HyperLogLogとは cardinalityと呼ばれる、要素の異なり数を決定する問題 かなり省メモリで精度のよい異なり数を推定できる方法 要素をそのまま保存せず、ハッシュ値に変換したものをうまくレジスタに保存しておく ので、レジスタサイズ程度しかメモリを使わない 並列化もできて、最近のbigdataとかで注目されている また、googleが並列計算用に改善したHyperLogLogを提案してるみたい http://blog.aggregateknowledge.com/2013/01/24/hyperloglog-googles-take-on-
Sketch of the Day: HyperLogLog — Cornerstone of a Big Data Infrastructure Intro In the Zipfian world of AK, the HyperLogLog distinct value (DV) sketch reigns supreme. This DV sketch is the workhorse behind the majority of our DV counters (and we’re not alone) and enables us to have a real time, in memory data store with incredibly high throughput. HLL was conceived of by Flajolet et. al. in the ph
Matt Abrams recently pointed me to Google’s excellent paper “HyperLogLog in Practice: Algorithmic Engineering of a State of The Art Cardinality Estimation Algorithm” [UPDATE: changed the link to the paper version without typos] and I thought I’d share my take on it and explain a few points that I had trouble getting through the first time. The paper offers a few interesting improvements that are w
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
