An efficient length-segmented inverted index-based set similarity query algorithm
Mengjuan Li, Lianyin Jia, Juntao Hu, Ruiqi Zhang, Shoulin Wei, Mengni Pan · International Journal of Computing Science and Mathematics · 2022
Set Similarity query is extensively used in recommendation systems, near duplicate detection and many other fields. Existing approaches usually scan all relevant inverted lists or trie indexes, thus leading to low efficiency. To solve this problem, in this paper, an efficient length segmentation-based inverted index, LenSegII, is designed. LenSegII imposes a length segmentation table (LST) on inverted indexes by exploiting length filtering, thus logically dividing an inverted index into segments. Based on LenSegII, LenSC-SSQ, an efficient set similarity query algorithm is proposed. LenSC-SSQ only needs to access a certain range of inverted index segments and locates the segments efficiently by LST, thus a large number of unqualified sets can be filtered, which significantly decreases query time. Besides, LenSC-SSQ can improve space efficiency by using a more compact count array. Experiments on 2 real and 1 synthetic datasets show LenSC-SSQ outperforms the other competitors significantly and can reach a performance improvement up to 5.8X over ScanCount.