2 者間マッチングにおけるコストベースの最適化手法

• Item type: Trans(1)
• 公開日: 2006-03-15
• タイトル: 2 者間マッチングにおけるコストベースの最適化手法
• タイトル / 言語: en
• タイトル: Cost-based Optimization for Pair-matching Problem
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 研究論文
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 日本電信電話株式会社NTT 情報流通プラットフォーム研究所
• 著者所属: 日本電信電話株式会社NTT サイバースペース研究所
• 著者所属: 日本電信電話株式会社NTT サイバースペース研究所
• 著者所属: 日本電信電話株式会社NTT サイバースペース研究所
• 著者所属(英): en
• 著者所属(英): NTT Information Sharing Laboratories, NTT Corporation
• 著者所属(英): en
• 著者所属(英): NTT Cyber Space Laboratories, NTT Corporation
• 著者所属(英): en
• 著者所属(英): NTT Cyber Space Laboratories, NTT Corporation
• 著者所属(英): en
• 著者所属(英): NTT Cyber Space Laboratories, NTT Corporation
• 著者名: 濱田, 貴広; 西岡, 秀一; 鬼塚真; 山室, 雅司
• 著者名(英): Takahiro, Hamada; Shuichi, Nishioka; Makoto, Onizuka; Masashi, Yamamuro
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: バーターや人材仲介等のサービスでは，利用者間を仲介するマッチング機能（ユーザの取引候補を探索する機能）が重要である．これらのサービスを利用するユーザは，相手に要求するモノの条件（クエリ）と，自分が提供するモノに関する内容（データ）のペアとしてモデル化されるため，マッチング機能は入力されたペアを用いて，蓄積済みのペア集合から適合するペアを特定することと定義できる．このマッチングを処理するプランは複数あり，これらの中から最適なプラン（処理時間が最小となるプラン）を選択することが課題である．本稿では，統計値を用いたコストベースの最適化手法を提案する．本手法は，複数の結合演算の最適化技術がマッチング処理に応用できることに着目し，DB 検索処理とフィルタ処理を利用した2 つのネストループプランと，1 つのマージプランからなる3 プランを提案し，これらのコストモデルを定義する．このコストモデルについて，事前実験で得た関数，値を用いて定量化を行い，これらについて人工データによる検証実験を行った結果，提案手法は高精度で最適プランを選択することを実証した．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Internet matching services, such as bartering, and recruiting, have grown. Their main function is to detect two-party exchanges from a huge number of users, in which each user’s demand is satisfied by the supply of the other user. A user can be modeled as a pair of demand and supply expressed by queries and data, respectively. Thus the pair-matching problem of two-party exchanges is to identify a set of pairs in a pair database whose data and queries crossly match the query and data of an incoming query pair. For this problem, there are several possible execution plans and the optimum plan depends on a query pair and the statistics of the database. In this paper, we propose a cost-based optimization technique for the pairmatching problem. Similar to the optimization of relational join operations, we obtain two nested loop plans and a single merge plan by leveraging the database query processing and stream data processing. We describe a cost model for these plans, derived by investigating the database and stream processing algorithms and by pre-evaluation phase experiments. The experimental results of execution phase verified that our optimization technique could select the optimum plan with very high precision.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11464847
• 書誌情報: 情報処理学会論文誌データベース（TOD）; 巻 47, 号 SIG4(TOD29), p. 40-50, 発行日 2006-03-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7799
• 出版者 / 言語: ja
• 出版者: 情報処理学会