How To Make Responsive Image Slider Design With HTML, CSS, And JavaScript Tutorial | Slider Design
Backend Engineering: Bloom Filters
If you have your own website then surely there will be multiple users. And each user will have their own account where they can login with their username and password. Now if a new user wants to open an account then you have to make sure that someone else has already created an account using the same username that he is using.
Let’s say, you have already saved all the usernames in a database. How do you check if the username is duplicate every time a new user tries to register? The easiest way is to check the database every time the username is sent to the server.
Now suppose your website is very popular, there are 1 million users and thousands of new users are creating new accounts every minute. In that case, many requests must be sent to the server to check for duplicates, and the database must also be accessed many times. In this case you can use a cache to reduce database access but best if we can check for duplicates without sending requests to the server.
How To Make Responsive Image Slider Design With HTML, CSS, And JavaScript Tutorial | Slider Design
One way is to send the list of 10 million users to the client’s browser and check for duplication there, but then a lot of data will be sent to the browser, and the list of usernames will be leaked to everyone.
A probabilistic data structure called Bloom filter is used to solve this type of problem. It is a very simple data structure, if you have an understanding of hashing then there will be no problem to understand.
The feature of the Bloom filter is that if you input a username here, it will give two types of output, one is, “I’m sure the username is not in the database”; Another is, “I’m almost certain that username is in the database”. The point to note here is that if the Bloom filter says that the username is not in the database then it is 100% sure that the username does not exist; But if it says it’s in the database, it may or may not be there, and you’ll have to look it up in the database to be sure.
Bloom filter is a vector of m bits. All bits are initially zero.
Let us assume m=9 in this example. Now we need to define k hash functions. The job of each hash function is to take a username as input and assign it to a cell of a bit vector of size m. As an example, assume k=3
.
Now suppose the first user name is “BOB”. By hashing “BOB” with 3 hash functions we get 1, 4 and 7. We’ll turn those bits on in the Bloom filter.
2nd username is ALICE and ALICE is hashed to 3, 7 and 6. We turn the bits on.
Now we have ALICE and BOB saved in our Bloom filter.
Now to know whether a new word is in the Bloom filter or not, you first k the name
Has to hash times and go to k positions to see if the bit is on. If you get at least one bit off that means the sound is definitely not in the Bloom filter.
But if you get bits on at k positions, you can’t say for sure whether the word is there or not. For example, after hashing the name “MARY” we get 3, 1 and 6. Earlier I got {3, 7, 6} from ALICE and {1, 4, 7} from BOB. When we search for MARY we get all the bits on, but we haven’t saved the word before.
It sometimes gives false positives, meaning that the word is not in the database.
Now we will hash each username on the server and create a bloom filter. Every time the user opens the register form, we send the bit vector to the user’s browser. When the user types a name, we can immediately check the filter to see if there is a user with that name in the database. Most of the time the bloom filter will give a negative output because the new username will usually not match the other username but if it does then we need to double-check by sending a request to the server.
How To Make Responsive Image Slider Design With HTML, CSS, And JavaScript Tutorial | Slider Design
In this way, you can greatly reduce server or database access by using the Bloom filter. To increase the performance of the Bloom filter, we need to reduce false positives. The error rate of a Bloom filter mainly depends on the number of hash functions (k) and the size of the filter (m). Arrow rate can be calculated using the following formula:
where k = number of hash functions, m = size of bit vector, n = size of input. I will not describe here how the formula is derived, you can read it elsewhere if you want.
Increasing the number of hash functions or increasing the size of m will decrease the error rate. But the more times you hash, the longer the calculation will take, and increasing the value of m will require more memory. There are many tools these days that you can use to calculate arrow rates. For example using this tool I got the following data:
This means if I have 1 million strings and I want the error rate to be 0.1% and I use 5 hash functions, I need to use a Bloom filter that is 612 KB in size. As you can see the Bloom filter uses very little memory.
Some other uses of the Lum filter are:
You can keep a list of weak passwords on your server (eg: 123456, password, abcdef). When the user registers and gives a new password, you can check with the Bloom filter whether the password is in the list of weak passwords.
A spell-checker can be created with the Bloom filter. If the word typed by the user is not in the dictionary, the Bloom filter will tell it.
There is another data structure similar to the Bloom filter called “Count-Mean Sketch” that works in much the same way but with a different implementation, which you can learn now.
Bloom filter is often used in database design, you can read my article about it.
That’s it for today, happy coding.
Before Download
You must Join our Facebook Group and Subscribe YouTube Channel
All Links in Below:
Join Our FreeWebsiteCreate Facebook Group to get an instant update for projects, templates, design resources, and solutions.
Join Our YouTube Channel & Subscribe with Bell Icon for New Video:
Join Our Official Facebook Page For the Latest updates All Code Projects are Free:
Visit our service page to get premium services.
Free Website Create – HTML CSS, PHP, JavaScript Programming Projects For Free
Follow Us
Thank You,
Before Download
You must Join our Facebook Group and Subscribe YouTube Channel
FreeWebsiteCreate.net tries to provide HTML, CSS, SCSS, JavaScript, React, Android Studio, Java, PHP, Laravel, Python, Django, C#(C Sharp), and ASP.net-related projects 100% free. We try to make learning easier. Free Website Create always tries to give free projects to new learners. Free projects and source code will help to learn quickly.
They can save time and learn more. In this post, we share a free portfolio project website code with HTML and CSS. This free code portfolio contains a single landing page with a responsive design. In this post, we get a free best carpenter and craftsman service website designed by FreeWebsiteCreate with HTML, CSS, Bootstrap, and JavaScript.