Иван Комаров (dfyz) wrote,
Иван Комаров
dfyz

Материалы к докладу на DUMP-2013

Слайды презентации.

Статьи
Мини-статья с обзором различных подходов к приближённому подсчёту.
Исходная статья 1985 года (алгоритм PCSA, про который я рассказывал).
Развитие темы: алгоритм LogLog 2003 года (рекомендуется сразу читать про его улучшенную версию с гармоническим средним вместо арифметического, которая называется HyperLogLog).

Посты в блогах
http://highlyscalable.wordpress.com/2012/05/01/probabilistic-structures-web-analytics-data-mining/
http://blog.aggregateknowledge.com/2013/04/02/sketch-of-the-day-probabilistic-counting-with-stochastic-averaging-pcsa/
http://blog.aggregateknowledge.com/2012/10/25/sketch-of-the-day-hyperloglog-cornerstone-of-a-big-data-infrastructure/

Некриптографические хеш-функции
http://en.wikipedia.org/wiki/MurmurHash
http://en.wikipedia.org/wiki/CityHash
http://en.wikipedia.org/wiki/Jenkins_hash_function#SpookyHash


Java-библиотека с реализацией этих (и многих других алгоритмов)
https://github.com/clearspring/stream-lib
Subscribe
  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your IP address will be recorded 

  • 2 comments