An Asymmetric-difference based Document Exact Similarity Search Algorithm

Retrieving similar documents serves as a fundamental building block for numerous information retrieval applications. Existing symmetric-difference based exact similarity search algorithm generates excessively large key bounds, resulting in reduced efficiency. To address this issue, we introduce a novel asymmetric-difference, which decomposes the symmetric-difference into an upper-bound difference and a lower-bound difference, thereby achieving tighter key bounds. Based on the asymmetric-difference, we design a novel key inverted index, KIL, and the corresponding exact similarity search algorithm, AD-Search. KIL maps a document and its length to an integer key, enabling direct pruning of documents that fail to meet length constraints. AD-Search employs an asymmetric-difference based strategy for both key bound generation and key filtering. This approach efficiently prunes non-qualifying keys, and thus greatly reduces the number of candidates. Experimental results on real-world datasets demonstrate that AD-Search outperforms MultiTree by up to 58.71× and LeBQ⁺ by up to 3.93×.