Blog | ClouderaClouderaNOW Learn about the latest innovations in data, analytics, and AI | July 16 Register now
Count-Min Sketch のライブラリを公開しました
2012-02-17 Count-Min Sketch のライブラリを公開しました written by Susumu Yata. はじめに 先日 groonga プロジェクトでの利用を目的として開発しているライブラリ Madoka を公開しました．Madoka は Count-Min Sketch という手法をライブラリ化したものであり，文書集合に含まれるキーワードの頻度を求める，クエリの頻度を求める，などの用途に使うことができます． s-yata/madoka - GitHub Documentation - Madoka ライブラリの使い方についてはドキュメントに書いてあるので，こちらは Count-Min Sketch と Madoka の特徴をまとめた内容になっています． Count-Min Sketch 頻度を求めることが目的であれば，ハッシュ表による連想配列を使うのが，おそら
Probabilistic Data Structures for Web Analytics and Data Mining
Statistical analysis and mining of huge multi-terabyte data sets is a common task nowadays, especially in the areas like web analytics and Internet advertising. Analysis of such large data sets often requires powerful distributed data stores like Hadoop and heavy data processing with techniques like MapReduce. This approach often leads to heavyweight high-latency analytical processes and poor appl
HyperLogLog++: Google’s Take On Engineering HLL –
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
Set Operations On HLLs of Different Sizes –
Introduction Here at AK, we’re in the business of storing huge amounts of information in the form of 64 bit keys. As shown in other blog posts and in the HLL post by Matt, one efficient way of getting an estimate of the size of the set of these keys is by using the HyperLogLog (HLL) algorithm. There are two important decisions one has to make when implementing this algorithm. The first is how ma
Sketch of the Day: HyperLogLog — Cornerstone of a Big Data Infrastructure –
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
Workshop on Algorithms for Modern Massive Data Sets (MMDS 2012)
MMDS. Workshop on Algorithms for Modern Massive Data Sets Website: We have moved to a new website; this page is no longer maintained. To visit the MMDS, go to mmds-data.org. Registration for MMDS 2014 is now open! Synopsis The Workshops on Algorithms for Modern Massive Data Sets (MMDS) addresses algorithmic and statistical challenges in modern large-scale data analysis. The goals of this series of
The MMDS 2012 Slides are out! Workshop on Algorithms for Modern Massive Data Sets
In case you have to take your mind off tomorrow's suspense-filled and technologically challenging landing of Curiosity on Mars (see 7 minutes of Terror, a blockbuster taking place on Mars this Summer ) Michael Mahoney, Alex Shkolnik, Gunnar Carlsson, Petros Drineas, the organizers of Workshop on Algorithms for Modern Massive Data Sets (MMDS 2012), just made available the slides of the meeting. Oth
Big Data Counting: How to count a billion distinct objects using only 1.5KB of Memory - High Scalability -
The table shows that we can count the words with a 3% error rate using only 512 bytes of space. Compare that to a perfect count using a HashMap that requires nearly 10 megabytes of space and you can easily see why cardinality estimators are useful. In applications where accuracy is not paramount, which is true for most web scale and network counting scenarios, using a probabilistic count
More data usually beats better algorithms, Part 2
Datawocky On Teasing Patterns from Data, with Applications to Search, Social Media, and Advertising The post More Data Beats Better Algorithms generated a lot of interest and comments. Since there are too many comments to address individually, I'm addressing some of them in this post. 1. Why should we have to choose between data and algorithms? Why not have more data and better algorithms? A. Ther
MurmurHash, final version.
UPDATE - If you're reading this via a link from Google or Reddit, please go here - http://murmurhash.googlepages.com. All future updates about MurmurHash will be posted there. UPDATEUPDATE - MurmurHash is now at version 2.0. The new version uses a different mix function than the below that is much faster & mixes better. Code is on the website linked above. OK, I'm done with this for the time being
Algorithms for calculating variance - Wikipedia
Algorithms for calculating variance play a major role in computational statistics. A key difficulty in the design of good algorithms for this problem is that formulas for the variance may involve sums of squares, which can lead to numerical instability as well as to arithmetic overflow when dealing with large values. A formula for calculating the variance of an entire population of size N is: Usin
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
http://kdd2012.sigkdd.org/sites/images/summerschool/Ravi-Kumar.pdf
http://www.youtube.com/watch?v=KvcBAECDaAA
Google News: The Secret Sauce
GitHub - MLnick/hive-udf: Approximate cardinality estimation with HyperLogLog, as a Hive function
http://research.google.com/pubs/archive/40671.pdf
https://algo.inria.fr/flajolet/Publications/DuFl03.pdf
HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm (PDF形式)
http://homepage.informatik.fh-gelsenkirchen.de/conen/vorlesungen/ss04/gin2-ss04/fast-implementations-of-shortest-path.pdf