Performance investigation of Hamming Distance Bit Vertical Counter applied to access methods in information retrieval

A speedup improvement to an Associative Access (ASSA) method, which is an information retrieval algorithm, has been suggested by Berkovich and others. The improvement is achieved through a novel technique of vertical counting. The vertical counting approach calculates the number of “ones” in characteristic vectors without performing the shift operation repeatedly. Using this technique, the determination of qualifying records in a database can be several times faster than other implementations. Unfortunately, the performance of the suggested technique has not been studied. This paper focuses on the performance of the vertical approach, and analyzes its behavior. It determines the speedup gained from using the Hamming Distance Bit Vertical Counter in the vertical approach, and, it evaluates the parameters that influence the speedup. It also discusses the breaking point that makes the vertical approach faster than the horizontal approach, and lastly determines its time complexity.