Massive Algorithms: Big Data Algorithm

Showing posts with label Big Data Algorithm. Show all posts

HyperLogLog

https://en.wikipedia.org/wiki/HyperLogLog
HyperLogLog is an algorithm for the count-distinct problem, approximating the number of distinct elements in a multiset (the cardinality).

http://highscalability.com/blog/2012/4/5/big-data-counting-how-to-count-a-billion-distinct-objects-us.html?currentPage=2

One common approach to this problem is the use of bitmaps. Bitmaps can be used to quickly and accurately get the cardinality of a given input. The basic idea with a bitmap is mapping the input dataset to a bit field using a hash function where each input element uniquely maps to one of the bits in the field. This produces zero collisions, and reduces the space required to count each unique element to 1 bit. While bitmaps drastically reduce the space requirements from the naive set implementation described above they are still problematic when the cardinality is very high and/or you have a very large number of different sets to count. For example, if we want to count to one billion using a bitmap you will need one billion bits, or roughly 120 megabytes for each counter. Sparse bitmaps can be compressed in order to gain space efficiency, but that is not always helpful.

http://blog.mparticle.com/a-must-know-for-data-scientists-hyperloglog-algorithm/

Hyperloglog is a space-efficient algorithm for accurate cardinality estimations. Nowadays a lot of data products use it, including Redis, AWS Redshift, and Druid. Redis’s implementation of HLL uses at most 12Kb of memory to estimate the cardinality of practically any set.

The basic idea of HLL is as follows. Imagine you flip a coin for 100 times and count the number of consecutive heads before the first tail. Let’s call this one experiment. You perform a few experiments, and you may get the following series (H for head and T for tail):

experiment 1: HHTHTTHH….

experiment 2: HTHHHTTT….

experiment 3: TTHTHHHT….

The number of consecutive heads at the beginning of the series is 2, 1, 0, respectively, marked in red. If you only do a small number of experiments, the chance is that the max number of consecutive heads is small. However, if you have patience to perform a lot of experiments, you may get a large number of consecutive heads from at least one experiment.

HLL essentially hashes every element in a set, counts the number of consecutive leading 0’s from each hash, and estimates the cardinality based on the largest count of consecutive leading 0’s out of the hashes.

Estimate the cardinality of union of multiple sets. It is natural to combine multiple HLL’s; simply take the largest count of consecutive leading 0’s from all the HLL’s.
Estimate the overlap of two sets. Since |A ∩ B| = |A| + |B| – |A ∪ B|, the overlap of two sets can be calculated from the cardinality of each set and the cardinality of their union.

http://research.neustar.biz/2012/10/25/sketch-of-the-day-hyperloglog-cornerstone-of-a-big-data-infrastructure/

Bit-pattern observables: these are based on certain patterns of bits occurring at the beginning of the (binary) S-values. For instance, observing in the stream S at the beginning of a string a bit- pattern is more or less a likely indication that the cardinality n of S is at least $2^\rho$ .

Order statistics observables: these are based on order statistics, like the smallest (real) values, that appear in S. For instance, if X = min(S), we may legitimately hope that n is roughly of the order of 1/X…

http://opensourceconnections.com/blog/2015/02/04/its-log-its-log-its-big-its-hyper-its-good/

https://pkghosh.wordpress.com/2014/11/16/counting-unique-mobile-app-users-with-hyperloglog/

HyperLogLog is based on analyzing some bit patterns in the hashed value of an item. We look at the length of the sequence of most significant zero bits. The maximum length among such zero bit sequences from all the hashed values is indicative of the unique item count.

In reality, to improve the quality of the result, multiple independent hash functions are used and the longest sequence zero bits resulting from each hash function is used to produce the final averaged unique count value.

Libraries

Twitter's algebird

stream-lib library (stream-lib) from ClearSpring

Java code:

http://facebook.github.io/jcommon/stats/jacoco/com.facebook.stats.cardinality/HyperLogLog.java.html

http://antirez.com/news/75

Count-Min Sketch - Approximate Algorithm

http://lkozma.net/blog/sketching-data-structures/
The Count-Min (CM) sketch is less known than the Bloom filter, but it is somewhat similar (especially to the counting variants of the Bloom filter).

The problem here is to store a numerical value associated with each element, say the number of occurrences of the element in a stream (for example when counting accesses from different IP addresses to a server). Surprisingly, this can be done using less space than the number of elements, with the trade-off that the result can be slightly off sometimes, but mostly on the small values. Again, the parameters of the data structure can be chosen such as to obtain a desired accuracy.

CM works as follows: we have k different hash functions and kdifferent tables which are indexed by the outputs of these functions (note that the Bloom filter can be implemented in this way as well). The fields in the tables are now integer values. Initially we have all fields set to 0 (all unseen elements have count 0). When we increase the count of an element, we increment all the corresponding k fields in the different tables (given by the hash values of the element). If a decrease operation is allowed (which makes things more difficult), we similarly subtract a value from all k elements.

To obtain the count of an element, we take the minimum of the kfields that correspond to that element (as given by the hashes). This makes intuitive sense. Out of the k values, probably some have been incremented on other elements also (if there were collisions on the hash values). However, if not all k fields have been returned by the hash functions on other elements, the minimum will give the correct value.

we want to notice if an IP address is responsible for a lot of traffic (to further investigate if there is a problem or some kind of attack). The CM structure allows us to do this without storing a record for each address. When we increment the fields corresponding to an address, simultaneously we check if the minimum is above some threshold and we do some costly operation if it is (which might be a false alert). On the other hand, the real count can never be larger than the reported number, so if the minimum is a small number, we don’t have to do anything (this holds for the presented simple variant that does not allow decreases). As the example shows, CM sketch is most useful for detecting “heavy hitters” in a stream.

Java code:
https://github.com/addthis/stream-lib/blob/master/src/main/java/com/clearspring/analytics/stream/frequency/CountMinSketch.java
http://www.sanfoundry.com/java-program-implement-count-min-sketch/

```
class CountMinSketch
```
```
{
```
```
    private int[] h1;
```
```
    private int[] h2;
```
```
    private int[] h3;
```
```
    private int size;
```

    private static int DEFAULT_SIZE = 11;

```
 
```
```
    /** Constructor **/
```
```
    public CountMinSketch()
```
```
    {
```
```
        size = DEFAULT_SIZE;
```
```
        h1 = new int[ size ];
```
```
        h2 = new int[ size ];
```
```
        h3 = new int[ size ];
```
```
    }
```

    /** Function to clear al counters **/

```
    public void clear()
```
```
    {
```
```
        size = DEFAULT_SIZE;
```
```
        h1 = new int[ size ];
```
```
        h2 = new int[ size ];
```
```
        h3 = new int[ size ];
```
```
    }
```
```
    /** Function to insert value **/
```
```
    public void insert(int val)
```
```
    {
```
```
        int hash1 = hashFunc1(val);
```
```
        int hash2 = hashFunc2(val);
```
```
        int hash3 = hashFunc3(val);
```
```
        /** increment counters **/
```
```
        h1[ hash1 ]++;
```
```
        h2[ hash2 ]++;
```
```
        h3[ hash3 ]++;
```
```
    }
```

    /** Function to get sketch count **/

```
    public int sketchCount(int val)
```
```
    {
```
```
        int hash1 = hashFunc1(val);
```
```
        int hash2 = hashFunc2(val);
```
```
        int hash3 = hashFunc3(val);
```

        return min( h1[ hash1 ], h2[ hash2 ], h3[ hash3 ] );

```
    }
```

    private int min(int a, int b, int c)

```
    {
```
```
        int min = a;
```
```
        if (b < min)
```
```
            min = b;
```
```
        if (c < min)
```
```
            min = c;
```
```
        return min;
```
```
    }
```
```
    /** Hash function 1 **/
```
```
    private int hashFunc1(int val)
```
```
    {
```
```
        return val % size;
```
```
    }
```
```
    /** Hash function 2 **/
```
```
    private int hashFunc2(int val)
```
```
    {
```

        return ((val * (val + 3)) % size);

```
    }
```
```
    /** Hash function 3 **/
```
```
    private int hashFunc3(int val)
```
```
    {
```
```
        return (size - 1) - val % size;
```
```
    }   
```
```
}
```

Ruminations of a Programmer: Count-Min Sketch - A Data Structure for Stream Mining Applications
The idea is quite simple and the data structure is based on probabilistic algorithms to serve various types of queries on streaming data. The data structure is parameterized by two factors - ε and δ, where the error in answering the query is within a factor of ε with probability δ. So you can tune these parameters based on the space that you can afford and accordingly amortize the accuracy of results that the data structure can serve you.

https://dzone.com/articles/count-min-sketch-data
One widely used technique for storing a subset of data is through Random Sampling, where the data stored is selected through some stochastic mechanism.

https://github.com/addthis/stream-lib/blob/master/src/main/java/com/clearspring/analytics/stream/frequency/CountMinSketch.java
Read full article from Ruminations of a Programmer: Count-Min Sketch - A Data Structure for Stream Mining Applications

Bloom filters in Java: example implementation

Bloom filters in Java: example implementation
Bloom Filters: an example Java implementation Having introduced the concept of a Bloom filter , we now look at an example Java implementation. We will consider the case of representing a set of strings. Generating hash codes The basic component that we need to implement our Bloom filter is a way of generating an arbitrary number of good-quality hash codes for a given string. Previously, we discussed a strong hash code implementation which produced 64-bit hash codes based on a table of random 64-bit numbers.

http://www.cnblogs.com/dolphin0520/archive/2012/11/10/2755089.html
布隆过滤器（Bloom Filter），它是由Burton Howard Bloom在1970年提出的，它结合了位图和Hash表两者的优点，位图的优点是节省空间，但是只能处理整型值一类的问题，无法处理字符串一类的问题，而Hash表却恰巧解决了位图无法解决的问题，然而Hash太浪费空间。针对这个问题，布隆提出了一种基于二进制向量和一系列随机函数的数据结构-布隆过滤器。它的空间利用率和时间效率是很多算法无法企及的，但是它也有一些缺点，就是会有一定的误判率并且不支持删除操作。

　　尤其要注意的是，布隆过滤器是不允许删除元素的，因为若删除一个元素，可能会发生漏判的情况。不过有一种布隆过滤器的变体Counter Bloom Filter，可以支持删除元素

　　布隆过滤器在很多场合能发挥很好的效果，比如：网页URL的去重，垃圾邮件的判别，集合重复元素的判别，查询加速（比如基于key-value的存储系统）等，下面举几个例子：

　　1.有两个URL集合A,B，每个集合中大约有1亿个URL，每个URL占64字节，有1G的内存，如何找出两个集合中重复的URL。

　　很显然，直接利用Hash表会超出内存限制的范围。这里给出两种思路：

　　第一种：如果不允许一定的错误率的话，只有用分治的思想去解决，将A,B两个集合中的URL分别存到若干个文件中{f1,f2...fk}和{g1,g2....gk}中，然后取f1和g1的内容读入内存，将f1的内容存储到hash_map当中，然后再取g1中的url，若有相同的url，则写入到文件中，然后直到g1的内容读取完毕，再取g2...gk。然后再取f2的内容读入内存。。。依次类推，知道找出所有的重复url。

　　第二种：如果允许一定错误率的话，则可以用布隆过滤器的思想。

　　2.在进行网页爬虫时，其中有一个很重要的过程是重复URL的判别，如果将所有的url存入到数据库中，当数据库中URL的数量很多时，在判重时会造成效率低下，此时常见的一种做法就是利用布隆过滤器，还有一种方法是利用berkeley db来存储url，Berkeley db是一种基于key-value存储的非关系数据库引擎，能够大大提高url判重的效率。

http://www.fgdsb.com/2015/01/03/estimate-the-number-of-unique-strings-with-limited-memory/

Estimate the number of unique strings with limited memory
Given a large array of strings S = [s1, s2, … sN], determine Uniq(S) = how many unique strings there are in S.

If it’s only required to estimate the number with limited memory, It’s possible to use a simplified hash table to do this.
We can define a boolean array S
For each iteration we calculate the hash function H of current string, and check if the S[H] is true which means that we have inserted the same string before current iteration, so we do not count the string.
If the hash function have no collision, the algorithm can always get the accurate result.
To minimize the collision, we can use a group of hash functions like a bloom filter ….(each time we check S1[H1] S2[H2] .. SN[HN], if all those variable have been set, we assert that the string is duplicated)

Assuming good hashing scheme, this can do 4 billion strings in 512MB memory (ideal case). This means ~64 billion strings in 8GB. If N becomes two large, a distributed hash table can be used to span the data across multiple servers. Another alternative could be to store the data on disk and maintain indexes for faster seeks and updates

Also read https://code.google.com/p/guava-libraries/source/browse/guava/src/com/google/common/hash/BloomFilter.java
Read full article from Bloom filters in Java: example implementation

HyperLogLog

Count-Min Sketch - Approximate Algorithm

Bloom filters in Java: example implementation

Labels

Popular Posts