Probabilistic hashing - is there such a thing?

Question

Suppose you want to implement a click tracker in which you only want to count a click on a link from any IP address once, but the number of links and clients is very large, and you do not want to keep a table of each one IP click. Say you might need this as part of something that works live against every click and doesn't want to do a large table search for every click.

Is there such a thing as probabilistic hashing or lossy hashing to see if the IP address is probably in the set, but you don't care if there is a certain error rate because you want to save resources?

Answer 1

You could (ab?) Use a flowering filter for something like this.

Answer 2

Assuming IPv4 addresses, a search space of 2 ³² exists. Each IP address requires no more than 1 bit (0 == no visit, 1 == visit). Excluding storage overhead, storage would require 512 MB (2 ²⁹ ). Thus, for simplified implementation, an array of 512 MB (or a table with 2 ²⁹ ) will be allocated, each of which stores bytes or 2 rows ²⁷ each of which stores a 32-bit integer, or 2 ²⁶ each of which stores a 64-bit integer number or ...)

You can optimize this for a sparse population by turning it into a tree.

Define the "page" size to 2 ^x . You will allocate storage for one page at a time.

Divide the search space (2 ³² ) by the size of your page. This is the total number of pages needed to represent all possible addresses in your search space.

Then, to determine if there is a hit in your hash, you first determine if the page is present, and if so, whether the corresponding bit is set on the page. To cache an address, you first determine if the page is present; if not, you will create it. Then you set the corresponding bit.

This form is fairly easy to apply to a database table. You will need only two columns: the page index and the binary array. When you select a page, you simply save the row in the table with the correct page index and an empty binary array.

For example, for a 1024-bit page size (with maximum pages < ²² ), you can structure the table as follows:

CREATE TABLE VisitedIPs( PageIndex int NOT NULL PRIMARY KEY, PageData binary(128) NOT NULL ) 

To check if you visited the IP address, you would use a code similar to (pseudocode):

 uint ip = address.To32Bit(); string sql = "SELECT PageData " + "FROM VisitedIPs " + "WHERE PageIndex = " + (ip >> 10); byte[] page = (byte[])GetFromDB(sql); byte b = page[(ip & 0x3FF) >> 3]; bool hasVisited = (b & (1 << (ip & 7)) != 0; 

The setting that the IP address visited is similar:

 uint ip = address.To32Bit(); string sql = "SELECT PageData " + "FROM VisitedIPs " + "WHERE PageIndex = " + (ip >> 10); byte[] page = (byte[])GetFromDB(sql); page[(ip & 0x3FF) >> 3] |= (1 << (ip & 7)); sql = "UPDATE VisitedIPs " + "SET PageData = @pageData " + "WHERE PageIndex = " + (ip >> 10); ExecSQL(sql, new SqlParam("@pageData", page)); 

Answer 3

All hashing is unprofitable, due to the principle of a pigment hole . Inevitably, you try to squeeze N things into M slots (where N → M). All you have to do is just not handle the collision cases and choose a fairly large hash table.

Answer 4

Of course! Decide how many “bunkers” you can afford (one bit each), say N; hash IP address in string bit B; take B modulo N. You can calculate the probability of random collisions (with some approximation, for example, suppose that all hashed IP addresses form equally probable bit strings of B) and determine N accordingly, if you have a limit on the maximum probability of a random collision, acceptable for your application.

Answer 5

Start truncated bits.

The chance of a hash collision becomes 50% if you have 2 ^ (n / 2) things out of a possible 2 ^ n. The IP address is 2 ^ 32, so the probability of collision is 50% if there are 2 ^ 16 elements in the container.

Reduce as you wish.

Answer 6

Hashing integers (ipv4) or string (ipv6) without conflict processing using the hash value (size modulo the hash table) as an index for the bitmap.