An improved algorithm based on Bloom filter and its application in bar code recognition and processing

Abstract

In many cases, databases are incompetent to meet the requirement of the quick query identification and processing of bar codes, such as the automatic sorting system of giant logistics warehouse. Bloom filter can be faster than databases, but its high false positive rate may seriously affect the efficiency of work. Although increasing the width of bit vector and the number of hash functions can reduce the false positive rate, the effect will be not significant after a certain threshold value, and this approach will increase the cost of processing time. So, it could not be increased indefinitely. This paper presents an improved algorithm based on Bloom filter and its application in bar code recognition and processing. The bit vector of Bloom filter is divided into two parts. Every element ai could be mapped to a part of the bit vector by some hash functions. For each element to amplify the difference by g (), which makes g (ai) = a*i, the a*i is mapped to another part of the bit vector by some hash functions too. This algorithm can significantly reduce the false positive rate of the Bloom filter, but does not increase much time and space costs.