What is a good algorithm to check for the presence or absence of a number in multiple sets without finding them?

Question

Scenario

Let's say you have several databases in 3 zones. Zone A , B and C Each zone at different geographical points. At the same time, you have an application that will route the username and password based on the user's geographic location. For example, user A will be redirected to a database in zone A User B Zone B , etc.

Now let's say user A moves to zone B The request zone of application B will not find anything. Request zone A and zone C may take some time due to the fact that the zones are far away and you will have to query all databases in all zones.

My question

How can you check if a string / number exists in multiple sets?

or

How can you verify that a row exists in a database before sending a query?

My algorithm

This is not perfect, but it will give you an idea of ​​what I'm trying to do.

If we have a database with the following three users

• Foo
• bar
• Foobar

We accept the hash of all three users and look for the next prime if the hash is not prime.

 sum = hash(foo).nextPrime() * hash(bar).nextPrime() * hash(foobar).nextPrime() 

This amount is distributed between all zones. If I want to check foo , I can just take the hash of foo and look for the next prime number, and then take gcd(foo,sum) . If it is not equal to one. This means that foo exists in some database. If it is equal to one, then foo does not exist at all. If I want to add a new username. I just can do sum = sum * hash(newUserName).nextPrime().

The amount will increase to such an extent that it will query all databases faster.

Do you know a similar algorithm to solve this problem?

Answer 1

One data structure suitable for this application is the Bloom filter .

The Bloom filter is a probabilistic data structure that allows you to check whether an element is already in the set. If the test returns false, then the element is definitely not included in the set (0% false negatives), if true, then it can be in the set, but is not guaranteed (false positives are possible).

The filter is implemented as a bit array with m bits and a set of k hash functions. To add an element to an array (for example, a username), hash an element using each of the hash functions, and then take modulo m of each hash value to calculate the indices to set in the bitmap. To check if an element is in the set, calculate all hashes and indexes and check that all the corresponding bits in the array are set to 1. If any of them is zero, the element is definitely not in the set, if all 1, then the element is most likely , is installed in the set, but there is a small chance that it cannot be, the percentage of false positives can be reduced using a larger m.

To implement k hash functions, you can simply use the same hash algorithm (for example, CRC32, MD5, etc.), but attach a name for each of them before passing the hash function, effectively creating a “new” hash function for every salt. For given m and n (the number of elements added), the optimal number of hash functions k = (m / n) ln 2

For your application, the Bloom matrix bit filter will be shared across all ABC zones, etc. When a user tries to log in, you can first check the database of the local zone, and if so, then write them down as usual. If there is no local database, check the Bloom filter, and if the result is negative, you know for sure that they do not exist in another zone. If this is positive, you still need to check the databases in other zones (due to the possibility of a false positive result), but apparently this is not a big problem, because in any case you must contact other zones to transfer data to the user in the event that he was truly positive.

One aspect of using the Bloom filter is that it is difficult (although not impossible ) to remove items from the collection as soon as they are added.