文献

J-GLOBAL ID：202002265968488729   整理番号：20A1867434

理論的保証を伴う重複集合類似性結合【JST・京大機械翻訳】

Overlap Set Similarity Joins with Theoretical Guarantees

著者 (3件)： Deng Dong (Massachusetts Institute of Technology, Cambridge, MA, USA) ,  Tao Yufei (Chinese University of Hong Kong, Hong Kong, Hong Kong) ,  Li Guoliang (Tsinghua University, Beijing, China)
資料名： ACM Proceedings  (ACM Proceedings)
号： SIGMOD ’18  ページ： 905-920  発行年： 2018年 
JST資料番号： D0698C  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： 本論文は,集合と一定のcの2つの収集を与えられた重複制約を有する集合類似性結合問題を研究して,少なくともc共通要素を共有するデータセットにおけるすべての集合ペアを見つける。これは,情報検索,データマイニングおよび機械学習のような多くの分野における基本的操作である。すべての既存の方法の時間複雑性は,nがすべての集合の全体のサイズであるO(n2)であった。本論文で,著者らは,kが結果の数である,O(2c)=o(n2)+O(k)のO(n2-over 1ck1)の時間複雑性を有するサイズ認識アルゴリズムを提示した。サイズ認識アルゴリズムは,それらのサイズとプロセスに基づいて,すべての集合を小型で大きなものに分割する。本論文では,大きな集合を処理し,小さな集合に焦点を当てた既存の方法を使用する。実用性能を大幅に改善する小集合に対するいくつかの最適化発見的方法を開発した。小さな集合と大きな集合の間のサイズ境界が効率に重要であるので,適切なサイズ境界を賢明に選択するための効果的なサイズ境界選択アルゴリズムを提案し,それは実際に非常に良く機能する。実世界データセットに関する実験結果は,著者らの方法が高性能を達成して,1桁まで最先端の手法より優れていることを示した。Please refer to this article’s citation page on the publisher website for specific rights information. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： *アルゴリズム ,  最適化 ,  情報検索 ,  発見的方法 ,  類似性 ,  機械学習 ,  データマイニング
準シソーラス用語： 認識アルゴリズム ,  複雑性 , 【Automatic Indexing@JST】

著者キーワード (6件)： 重複 ,  スケーラブル ,  セット ,  類似性結合 ,  サブ2次 ,  理論的保証

分類 (2件)： パターン認識  (JE07000S) ,  人工知能  (JE08000Z)

タイトルに関連する用語 (4件)： 理論 ,  保証 ,  集合 ,  類似性