アドホックネットワークにおけるヒストグラムを用いたTop-k検索手法

• 佐々木, 勇和

• 萩原, 亮

• 原, 隆浩

• 篠原, 昌子

• 西尾, 章治郎

書誌事項

タイトル別名

• A Top-k Query Method using Histogram in Mobile Ad Hoc Networks

抄録

アドホックネットワークでは、膨大なデータの中から必要なデータのみを効率的に取得するため、端末が何らかの値（スコア）によって順序付けられたデータの上位k個のものを検索するTop-K検索を用いることが有効である。本稿では、アドホックネットワークにおいて、トラヒックの削減と検索結果の取得精度の低下を抑止を目的とするTop-K検索手法を提案する。提案手法では、各端末がヒストグラムを作成し、ネットワーク全体のk番目のスコアを推定する。次に、推定したk番目のスコア以上のスコアを持つデータを返信することで、できる限り検索結果に入るデータのみを返信する。また、返信先の端末とのリンク切断を検出した端末は、他の隣接端末にクエリ応答を返信することで、検索結果の取得精度の低下を抑止する。

In mobile ad hoc networks, to acquire only necessary data items, it is effective that each mobile node retrieves data items using a top-k query, in which data items are ordered by the score of a particular attribute and the query-issuing mobile node acquires data items with the k highest scores. In this paper, we propose a query processing method for top-k query for reducing traffic and also keeping high accuracy of the query results. In this method, each node constructs a histogram and estimates the k-th score in the entire network. When transmitting a reply, each mobile node sends back only data items whose socres are larger than the estimated k-th score to reduce traffic as much as possible. Moreover, when a mobile node detects the disconnection of a radio link, it sends the reply to another neighboring node to keep high accuracy of the query result.

収録刊行物

• マルチメディア通信と分散処理ワークショップ論文集 = Multimedia Communication and Distributed Processing System Workshop

  マルチメディア通信と分散処理ワークショップ論文集 = Multimedia Communication and Distributed Processing System Workshop 2009 (9), 13-18, 2009-09-30

詳細情報

• CRID: 1050292572120297216
• NII論文ID: 170000075037
• Web Site: http://id.nii.ac.jp/1001/00089927/
• 本文言語コード: ja
• 資料種別: conference paper
• データソース種別:
  • IRDB
  • CiNii Articles