Does Bloom Filter is the efficient Data Structure for large DataBase Lookup?

-


Happy to see all the software enthusiastic landing to this post to know about Bloom Filter. There are various Data Structures available but what depends is the use case for which a particular Data structure will serve the purpose efficiently. 


Recently I was going through the Data structure to quickly lookup the database content and explored many props and conclusions of various data structures according to my requirement. During the process, I heard about "Bloom Filter", an efficient data structure for a database lookup. As the name suggests it is primarily targeted to filter out some set of lists. 

Similarly, like other Data Structures Bloom Filter also has some disadvantages. Before diving into this let's understand the logic behind this.

The core logic is to get a hash from the input data and set a bit in the bit array while inserting data into the list. When lookup generates the hash key and checks the bit, if it is set, then data is present.

for example, if we are storing a list of employees/students in the database with the key being the employee name and the value being the details of the employee.

1st entry - Person1


for the above data generate the hash key and suppose let's say the hash key is 9 and 5

hash1("Person1") = 9;

hash2("Person1") = 5;


Now let's have bit array of size 32 bits

bit array = 0000 0000 0000 0000 0000 0000 0000 0000


enable/set bit 9 and 5

bit array = 0000 0000 0000 0000 0000 0001 0001 0000


Now let's take a second input

  1st entry - Person1


for the above data generate the hash key and suppose let's say the hash key is 1 and 5

hash1("Person2") = 1;

hash2("Person2") = 5;


set bit 1 and 5

bit array = 0000 0000 0000 0000 0000 0001 0001 0001


With the bit array now we can quickly do person lookup. Generate the hash key for the input person and check whether the bit is set or not. If the bit is set then the person entry is there in the list.


The disadvantage of this algorithm is some data may produce the subset of the key which is already set in the list. With this, there may be a wrong assumption that even though the data is not present we'll get the output as the data is present. This is not highly reliable for large mission-critical database lookups.

As earlier said pick an algorithm as per your need considering its advantages and disadvantages. With this, I'll end my short blog on this. Let's catch up in the next blog........:-)






Comments

Post a Comment

Popular posts from this blog

PostgreSQL Write-Ahead-Logging(WAL) Archiving Functionality

-
Image
 To recover from PostgreSQL Database crashes Postgres provides WAL archiving functionality from which a standby database can be created by replaying the WAL logs in the recovery site.This interm helps in recovering the database to a particular point in time which is termed as PITR(Point-In-Time_Recovery). WAL files contain the transaction logs from which the database operation can be replayed.Whenever a database operation is triggered a WAL record is created first and then the corresponding data is flushed to disk. In case of any crash, the lost data is recreated by replaying the WAL record. To enable WAL recovering below configuration needs to be configured in postgresql.conf file
Read more

Database Emergency Exit from unforeseen Disasters

-
Image
 With the emerging transformation in the field of AI(Artificial Intelligence) and ML(Machine Learning), data plays a very important role because it allows organizations to store large amounts of business data and retrieve them to get insight into products and customers, which will drive the business. The DataBase helps in accomplishing this. Database Management system provides facilities to access and modify these data efficiently and effectively. Database are very important because of following reasons, Databases enable businesses to efficiently and neatly store and handle massive volumes of data. This facilitates the retrieval and access of particular information when needed. Organizations can use databases to evaluate and interpret their data . Through the utilization of tools like pivot tables and SQL queries, organizations can acquire valuable insights into patterns, trends, and other significant data that can assist in making informed decisions. Through the provision of securit
Read more

RCU Kernel Implementation

-
Image
In our last session, we learned how to use RCU API as a synchronization mechanism using a sample driver. Please visit the  last session  if you missed. In this blog, we will be going through Kernel Implementation of RCU API. The below diagram depicts the overall RCU API used for synchronization. rcu_read_lock() -  The kernel implementation is as follows - static inline void rcu_read_lock(void) {         __rcu_read_lock();         __acquire(RCU);         rcu_lock_acquire(&rcu_lock_map);         rcu_lockdep_assert(rcu_is_watching(),                            "rcu_read_lock() used illegally while idle"); } Basically the above function disables the preemption on the particular cpu on which it is running. So that no other process can preempt this process and the process completes its execution without interruption. After holding rcu_read_lock() it is illegal for the process to explicitly call sleep. rcu_read_unlock()- static inline void rcu_read_unlock
Read more