Jordan University of Science and Technology

Performance Investigation of Hamming Distance Bit Vertical Counter Applied to Associative Access Methods in Information Retrieval

Authors:  E. El-Qawasmeh and I. Hemidi

Abstract 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.