Improved Hamming-space-based similarity search algorithm. (12th January 2023)

• Record Type: Journal Article
• Authors: Singh, Vikram; Kumar, Chandradeep
• Is Part Of: International journal of intelligent information and database systems. Volume 16:Number 1(2023)
• Page Start: 20
• Page End: 38
• Publication Date: 2023-01-12
• Subjects: Hamming-space -- information retrieval -- similarity search; Database management -- Computer programs -- Periodicals; Information retrieval -- Computer programs -- Periodicals; Information storage and retrieval systems -- Computer programs -- Periodicals; Artificial intelligence -- Periodicals; Expert systems (Computer science) -- Periodicals; Intelligent agents (Computer software) -- Periodicals; 006.33
• Languages: English
• ISSNs: 1751-5858

Abstract

In the modern context, similarity is driven by the quality-features of the data objects and steered by content preserving stimuli, as retrieval of relevant 'nearest neighbourhood' objects and the way similar objects are pursued. Current similarity searches in Hamming-space-based strategies finds all the data objects within a threshold Hamming-distance for a user query. Though, the numbers of computations for Hamming-distance and candidate generation are the key concerns from the several years. The Hamming-space paradigm extends the range of alternatives for an optimised search experience. A novel 'counting-based' similarity search strategy is proposed, with an a priori and improved Hamming-space estimation, e.g., optimised candidate generation and verification functions. The strategy adapts towards the lesser set of user query dimensions and subsequently constraints the Hamming-space computations with each data objects, driven by generated statistics. The extensive evaluation asserts that the proposed counting-based approach can be combined with any pigeonhole principle-based similarity search to further improve its performance.