Pub/Sub環境におけるkNNデータモニタリングの分散処理のためのクエリ割当てアルゴリズム

• Item type: Trans(1)
• 公開日: 2019-10-23
• タイトル: Pub/Sub環境におけるkNNデータモニタリングの分散処理のためのクエリ割当てアルゴリズム
• タイトル / 言語: en
• タイトル: Query Assignment Algorithm for Distributed Processing of kNN Data Monitoring in Pub/Sub Systems
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: [研究論文] Pub/Sub，kNNクエリ，分散処理
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 大阪大学大学院情報科学研究科
• 著者所属: 大阪大学大学院情報科学研究科
• 著者所属: 大阪大学大学院情報科学研究科
• 著者所属: 大阪大学大学院情報科学研究科
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science and Technology
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science and Technology
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science and Technology
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science and Technology
• 著者名: 鶴岡, 翔平; 西尾, 俊哉; 天方, 大地; 原, 隆浩
• 著者名(英): Shohei, Tsuruoka; Syunya, Nishio; Daichi, Amagata; Takahiro, Hara
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 近年，パブリッシュ/サブスクライブ（Pub/Sub）モデルに基づいてデータを配信するアプリケーションが多く存在し，ユーザは自身の興味のあるデータのみを取得する．また，スマートフォンやSNSの普及により，データやクエリ（サブスクリプション）の数が増加しており，単一のワーカですべての処理を行うとリアルタイム性を保持することが困難になっている．本稿では，Pub/Subモデルにおいて，複数のワーカにクエリを分散して処理を分担することにより，各クエリに対して，クエリのキーワードを含むデータの中でクエリの指定位置に最も近いk個のデータ（kNNデータ）を効率的にモニタリングする問題に取り組む．単純にクエリを分散させると，各ワーカの処理量に偏りが生まれ，その結果，新たなデータが生成されたとき，処理量の大きいワーカの処理時間が長くなり，全体の処理時間も長くなる．この問題を解決するため，各ワーカの処理時間が均一かつ全体の処理時間が短くなるようにクエリを分散するアルゴリズムを提案する．実データを用いた実験により，提案手法がベースライン手法と比べて数倍から数十倍高速にkNNデータを更新できることを確認した．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Recently, in many applications, data objects have been generated based on Publish/Subscribe (Pub/Sub) model, and users receive only their preferable data objects. Due to the prevalence of smartphones and SNS, a large numbers of data objects and queries (subscriptions) have been published and registered, respectively. This makes a single worker difficult to monitor the result of each query. In this paper, we address the problem of monitoring k nearest neighbor data objects which contain the query keywords in a distributed Pub/Sub system. A straightforward approach, which assigns the queries to workers randomly, cannot balance the workloads of the workers. To solve this, we propose an algorithm that assigns queries to balance the workload of each worker and to minimize the total amount of workload. Our experiments using real datasets verify that our proposed algorithm can update the kNN results more than several times faster compared with baseline algorithms
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11464847
• 書誌情報: 情報処理学会論文誌データベース（TOD）; 巻 12, 号 4, p. 53-65, 発行日 2019-10-23
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7799
• 出版者 / 言語: ja
• 出版者: 情報処理学会