Improvement of Searching Methodology for Network Applications using Bloom Filters and Hashing
Dhiraj Pandey, Kavita Pandey · 2020
To reduce processing and networking costs, probabilistic techniques are very much popular for many network solutions. Binary Search Trees provide searching with worst-case time complexity of O (log n). In this work, we propose a generic novel way in which Bloom Filters are used with Hashing to reduce the search time complexity. The proposed approach provides a solution using a Hash Table in Bloom Filter. The objective is to reduce the worst-case complexity of hashing to O (1) and provide space and time complexity of O(1) at the cost of introducing a controlled number of False Positives and to guarantee no occurrence of False Negatives. The proposed approach provides a solution to this problem by using the hash tables in Bloom Filter. Two types of test cases have been used in this work for testing purposes in the scenario of Hashing to show the problem with Hashing and in the approach with Bloom Filters showing the solution to the problem that exists in Hashing. Results indicate that Bloom Filter-based approach can be used to obtain optimal performance in time elapsed in searching.