連想配列型分散データ構造におけるキーの局所性を考慮した負荷分散(分散処理, <特集>ブロードバンド・ユビキタス・ネットワークとその応用)
スポンサーリンク
概要
- 論文の詳細を見る
特徴量に基づく類似検索や3次元位置情報管理システム等では, クエリ解決において局所的なデータ集合に対して処理を行う必要性が生じる.このような場合, データの配置がシステムの性能を決定する重要な要素となる.本稿では大規模分散環境において前述の処理を行うのに適した負荷分散について述べる.ハッシュテーブルに基づく従来の負荷分散ではキーの局所性が損なわれるため, システムの効率性が失われてしまう.そこでブロックリダイレクションという手法を導入し, キーの局所性を維持した負荷の分散を実現した.以下に示した手法ではシステムの平均負荷がほぼ一定であり, かつその平均負荷が定数倍の範囲で事前に分かっている場合, 任意のデータ分布に対して, 最も負荷の重いホストにかかる負荷が高い確率で平均負荷のΘ(log log N/log l)倍になるという特性が得られる.他方, システムの平均負荷が事前に分かっていない場合についても, 前述の特性の保証は得られないものの, 優れた負荷分散が図られることをシミュレーションによって検証した.
- 2006-02-15
著者
-
森川 博之
東京大学大学院新領域創成科学研究科
-
岡 敏生
東京大学大学院新領域創成科学研究科
-
青山 友紀
東京大学大学院工学系研究科電子情報工学専攻
-
青山 友紀
東京大学大学院工学系研究科
-
森川 博之
東京大学大学院工学系研究科
関連論文
- セッション層アーキテクチャにおけるフロー情報を用いた通信資源管理機構(モバイルユビキタス時代のネットワークとサービス(キーワード: ユビキタス, センサーNWネットワークアーキテクチャ, Ad-Hoc, 及び, そのアプリケーションなど))
- 1 社会創造に資するセンシングプラットフォーム(センシングネットワーク)
- 光バーストスイッチングネットワークテストベッドの設計と実装(フォトニックネットワーク向けデバイス, GMPLS, 光バースト/パケットスイッチング, 一般)
- 頑健性及び安全性を備えたモビリティサポートシステムの実装と評価
- B-6-33 分散システムを利用したモビリティサポート手法(B-6. ネットワークシステム)
- B-5-170 CSMA/CA 型無線 LAN におけるジッタ抑制手法
- 無線LANでの分散型待ち時間制御
- NGN/IMSを用いたユビキタスヘルスモニタリングシステムの設計と実装(ユビキタス,WEB,アプリ)
- Xquery可能なXDMSの設計と実装(ユビキタスNW,オーバーレイネットワーク,VPN,DDoS,ネットワークセキュリティ,P2P通信,ネットワークソフトウェア,一般)
- B-7-7 XQuery可能なXDMSの設計と実装(B-7.情報ネットワーク,一般セッション)
- 無線センサネットワークによる地震モニタリングシステムの実装と評価(アプリケーション品質,モバイルP2P,ユビキタスネットワーク,アドホックネットワーク,センサネットワーク,一般)
- [招待講演]モバイルインターネットワーキングへのロードマップ(モバイルネットワーク, アドホックネットワーク及び一般)
- 実空間センサ情報を用いたエンターテインメントアプリケーションのJa-Netへの実装(デモセッション)
- B-20-32 オフィスチェアにおけるコンテキスト推定手法の初期的検討(B-20.ユビキタス・センサネットワーク,一般セッション)
- ヘテロジニアスリンク環境のためのパーソナルメッシュの設計と実装
- ヘテロジニアスリンク環境のためのパーソナルメッシュの設計と実装
- 認知症患者の日常生活動作を支援するコンテキストアウェア案内システムの設計と実装(UBIセッション1)
- 頑健性及び安全性を備えたモビリティサポートシステムの実装と評価
- 無線LANでの分散型待ち時間制御
- 無線LANでの分散型待ち時間制御
- 無線LANでの分散型待ち時間制御
- B-6-20 ユビキタス環境に向けたセンサネットワーク開発用モジュール U^3 (U-Cube) の設計と実装
- ユビキタス環境に向けたセンサネットワークアプリケーション構築支援のための開発用モジュールU^3(U-cube)の設計と実装(セッション6)
- ユビキタス環境に向けたセンサネットワークアプリケーション構築支援のための開発用モジュールU^3(U-cube)の設計と実装
- 無線センサネットワークの未来
- [招待講演]モバイルインターネットワーキングへのロードマップ(モバイルネットワーク, アドホックネットワーク及び一般)
- [招待講演]モバイルインターネットワーキングへのロードマップ(モバイルネットワーク, アドホックネットワーク及び一般)
- B-15-23 GPS搭載携帯電話を用いた移動経路履歴に基づく訪問地予測方式(B-15.モバイルマルチメディア通信,一般セッション)
- A-15-12 マーカとマッチングコンテンツを用いたアナログメディアからの情報取得(A-15.ヒューマン情報処理,一般セッション)
- 不可視バーコードにおける印刷支援システム
- B-7-109 NGN/IMSを用いたユビキタスヘルスモニタリングシステムにおけるイベント/データ管理手法(B-7.情報ネットワーク,一般セッション)
- B-20-10 プレゼンスを活用したインフォーマルコミュニケーション支援システムの試作(B-20. ユビキタス社会とライフスタイル, 通信2)
- インフォーマルコミュニケーションを支援するプレゼンス技術
- SB-3-4 ユーザ主導型プレゼンスシステムの設計と実装(SB-3. プレゼンス技術)
- 複数ユーザ同士の関係を考慮したプレゼンス交換と合成手法(セッション7)
- 複数ユーザ同士の関係を考慮したプレゼンス交換と合成手法(セッション7)
- B-7-79 コミュニケーションプレゼンスを考慮したブートストラップ機構
- 日本のICT産業における技術戦略に関する考察(一般,ワイヤレスインターネット,マルチホップネットワーク,メッシュネットワーク,ネットワーク符号化,クロスレイヤ技術,無線通信及び一般)
- DLNAデバイスの操作履歴取得手法の検討
- 地震モニタリングに向けた高精度分散同期サンプリング(モバイルP2P,ユビキタスネットワーク,アドホックネットワーク,センサネットワーク,一般)
- B-20-22 地域規模の高密度地震モニタリングに向けた同期サンプリング機構の初期的評価(B-20.ユビキタス・センサネットワーク,一般セッション)
- B-20-24 地震モニタリングのための切り替え型MACプロトコルの検討(B-20. ユビキタス・センサネットワーク,一般セッション)
- B-20-20 地震モニタリングのための高精度センシングを実現するMACプロトコル(B-20.ユビキタス・センサネットワーク,一般講演)
- 11002 ユビキタス・センサネットワーク用加速度センサモジュールの開発(システム化技術, 情報システム技術)
- 11042 ユビキタス・センサネットワーク用MEMS加速度センサの振動台実験(可視化ほか,情報システム技術)
- ユーザの暖昧な行動情報を自動収集するIMSネットワークアプリケーション(IMS,NGN,VoIP,FMC,自律分散ネットワーク,ソフトウェアエージェント,Webサービス,Web2.0及び一般)
- B-20-33 無線センサノード向けマルチコアCPUのコンセプト検証(B-20. ユビキタス・センサネットワーク,一般セッション)
- B-12-7 プリアンブル遅延型ラベル更新処理を用いた光パケット転送機構のヘッダ長に関する評価(B-12.フォトニックネットワーク,一般講演)
- 多波長光パケットネットワークにおける遅延線バッファを用いた衝突回避機構の評価
- 自己ルーティングスイッチを用いた光パケット交換ネットワークにおけるヘッダ長の評価
- セッション層アーキテクチャを用いたIPTVサービスの実現(移動通信ワークショップ)
- B-6-52 セッション層アーキテクチャを用いたWWW閲覧システムの設計と実装(B-6.ネットワークシステム, 通信2)
- B-6-5 セッション層アーキテクチャにおける実通信機構の設計と実装(B-6. ネットワークシステム, 通信2)
- B-6-4 セッション層アーキテクチャを用いた遠隔会議システムの設計と実装(B-6. ネットワークシステム, 通信2)
- B-5-112 低受信待機電力無線通信のための階層型ウェイクアップ機構(B-5. 無線通信システムB(ワイヤレスアクセス),一般セッション)
- プリアンブル遅延によるラベル更新処理を用いた自己ルーチング型光パケット転送機構(ネットワーク)
- ドメイン間パスを用いたショートカットIPルーテイング機構(セッション6)
- ホスト情報を利用した多対多アプリケーションレベル経路制御手法(映像通信, コンテンツ配信ネットワーク, マルチキャスト, 一般)
- B-6-3 MyNetSpaceを構築するための端末管理機構(B-6. ネットワークシステム, 通信2)
- B-6-1 MyNetSpaceにおける仮想端末間通信機構の設計と実装(B-6. ネットワークシステム, 通信2)
- MyNetSpace : 柔軟なアクセス制御を実現するためのユーザ主導仮想閉域ネットワーク
- MyNetSpace : 柔軟なアクセス制御を実現するためのユーザ主導仮想閉域ネットワーク
- 実空間指向エンターテインメントアプリケーションの自律分散動作機構(サービス指向コンピューティング)
- 低受信待機電力無線通信のための多段ウェイクアップ機構(省電力)
- デプロイメントスケーラブルセンサネットワーク(ユビキタス・センサネットワークを支える理論,および一般)
- A-21-1 類似検索を用いた電力予測によるバッテリレス無線センサネットワークの制御(A-21.センサネットワーク,一般講演)
- バッテリレス無線センサネットワークの設計と実装(モバイルサービス,サービス品質,一般)
- バッテリレス無線センサネットワークの設計と実装(モバイルサービス,サービス品質,一般)
- B-7-151 MIRAIシグナリングによる異種網間高速ハンドオーバの検討(B-7.情報ネットワーク,一般講演)
- MIRAIシグナリングを用いた異なる移動通信ネットワーク間のハンドオーバの検討
- シームレス通信環境のためのコンテキスト情報を利用したネットワーク・アプリケーション制御機構(モバイルコンピューティング, マルチメディア, 分散, 協調とモバイル(DICOMO2004))
- B-6-32 Predicting Energy Consumption of Multi-service Terminals for Energy-efficient Selection of Wireless Interfaces
- B-15-40 U^1-Chip : インスタントサービス実現に向けての無線通信モジュール(B-15.モバイルマルチメディア通信)
- B-12-8 プリアンブル遅延型ラベル処理を用いた光バケット転送ノードの検証実験(B-12.フォトニックネットワーク,一般講演)
- プリアンブル遅延型ラベル更新手法を用いた光パケット転送ノードの実装
- B-6-10 視覚的操作による通信制御機構の設計と実装(B-6.ネットワークシステム,一般講演)
- 実空間操作に基づくリンク層におけるデバイスグルーピング機構
- B-6-80 至近距離通信デバイスを用いた視覚的操作による通信制御機構(B-6.ネットワークシステム, 通信2)
- B-6-36 CommoNetにおける基地局探索及び通信保護機構(B-6. ネットワークシステム, 通信2)
- GPS搭載携帯電話を用いた移動経路履歴に基づく訪問地・経由地予測システム
- B-7-5 着信時プライバシー保護のための条件付き別名SIPアドレス生成機構(B-7.情報ネットワーク,一般講演)
- 別名アドレスを用いた選択的着呼制御機構の実装と評価(セキュリティ)
- B-20-11 柔軟な入出力形態をもつ周辺認知情報提示システムの設計と実装(B-20. ユビキタス社会とライフスタイル, 通信2)
- ディジタルビデオを用いたリアルタイムマルチメディア通信システム
- 多対多マルチキャストにおけるメンバークラスタリング手法
- B-15-3 セッション層モビリティサポートによる端末間ハンドオフの実現
- B-20-56 Carrier Phase GPSを用いたセンサネットワークのローカライゼーション(B-20. ユビキタス・センサネットワーク,一般セッション)
- 自律分散的マイクロモビリティサポートのための基地局間マルチホップ網(セッション5A:モビリティ)(ユビキタスモバイルサービス)
- 自律分散的マイクロモビリティサポートのための基地局間マルチホツプ網(セッション5A : モビリティ)(ユビキタスモバイルサービス)
- B-6-65 CommoNet : 基地局間連携による自律分散的マイクロモビリティサポート(B-6. ネットワークシステム)
- B-6-40 セッション層モビリティサポートにおける高信頼データ転送の性能評価
- B-5-130 IEEE 802.11b 基地局における TCP プロキシのスリープ間隔に関する性能評価
- A-21-42 無線センサノードのための仮想マシンの性能評価(A-21.センサネットワーク,一般講演)
- A-21-41 ハードリアルタイム処理を保証する無線センサノード用オペレーティングシステムの評価(A-21.センサネットワーク,一般講演)
- 無線センサノード向けハードリアルタイムオペレーティングシステムの設計(UBIセッション3)
- 無線センサノード向けハードリアルタイムオペレーティングシステムの設計(UBIセッション3)
- B-15-4 無線センサネットワークを用いた動線検出システムの試作
- B-12-30 光パケット衝突回避手法における取得情報の違いによる棄却性能差の評価(B-12.フォトニックネットワーク,一般講演)
- 高密度ネットワークにおける相対距離を用いた経路制御手法
- 次世代フォトニックインターネットに向けたバーストスイッチネットワークテストベッド