類似性述語における効率的な集合結合

本論文では、交差サイズ、ジャッカード係数、コサイン類似度、編集距離といったさまざまな類似性尺度を含む述語に対して集合結合を実行するための効率的でスケーラブルな一般的アルゴリズムを提示します。これは、集合含有性、等価性、非ゼロ重複などの単純な述語に対する既存の集合結合アルゴリズムのスイートを拡張します。基本的な逆インデックスに基づく探索方法から始め、実行時間が1桁から2桁改善される最適化のシーケンスを追加します。アルゴリズムは、任意の利用可能なメインメモリに収まるよう圧縮されたインデックスで効率的に動作できるデータパーティショニング戦略を組み込みます。私たちのアルゴリズムで使用された最適化は、セット間の部分的な単語重複に対するいくつかの加重および非加重の尺度に一般化されます。