情報ファイルの最速な圧縮転送を求める2つの線形時間アルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
本研究では, コンピュータネットワーク上で, 情報ファイルを理論的に最高速で圧縮転送するためには, どこでその情報ファイルを圧縮・展開すべきかを決める問題を扱う. この問題では, 必要な情報ファイルが置かれているコンピュータをソースと呼び, その情報ファイルを必要としているコンピュータをシンクと呼ぶ. また, 転送の途中で, その情報ファイルを圧縮するコンピュータを圧縮マシンと呼び, 圧縮された情報ファイルを展開する (元の形に戻す) コンピュータを展開マシンと呼ぶ. 現在のファイル転送では, 圧縮マシン及び展開マシンは, それぞれソース及びシンクに限られている. 本研究での「ファイルの圧縮転迭」は, 転送経路上のソースやシンク以外のコンピュータでも, 圧縮マシンや展開マシンとなりうることを仮定する. その上で, ソースから圧縮マシンへのファイルの転送時間, 圧縮マシンでのファイルの圧縮時間, 圧縮マシンから展開マシンへのファイルの転送時間, 展開マシンでのファイルの展開時間, 及び展開マシンからシンクへのファイルの転送時間, これら全ての時間の総和を以て, ファイルの圧縮転送時間と定義し, この時間を最小にするような圧縮マシン及び展開マシンをいかに速く求めるかがファイルの最適な圧縮転送を求める問題である. この問題自体は, 最短路問題に帰着できることが既に示されている. また, 情報ファイルが転送される経路が固定されている場合, この問題は線形時間で解くことができることが示されているが, そのアルゴリズムは, 1. 最短路問題によるもの, 2. 点上の2つのパラメータを使ったもの, の2種類である. 本報告では, これらのアルゴリズムを, 実際にコーディングしてシミュレーションを行うことで, どちらが効率的であるかを比較検証する.
- 1998-01-29
著者
関連論文
- A-15-5 3種類の2連打鍵による個人認識について(A-15.ヒューマン情報処理,一般講演)
- 大規模な一個人打鍵情報による,小規模な参照データに対する個人の特定
- A-7-5 打鍵認証でのUW法におけるdigraphの選択について(A-7. 情報セキュリティ,一般セッション)
- 発進局選択での最適なfile transferの構成について
- 発進局選択での最適なfile transferの構成について
- 発進局選択での最適なfile transferの構成について
- 発進局選択での最適なfile transfer の構成について
- シミュレーティッド・アニーリングを用いたfile transferの構成法について
- マルチプロセッサスケジューリング問題における近傍解の構成法について
- simple tree-out & tree-in型クスクグラフスケジューリング問題の一考察
- 大規模高速データ転送並列処理システムに対するスケジューリングアルゴリズム
- 論文発表プログラム自動作成ソフトウェア「江戸っ子」 : 偏りある割り当てへの対応(デモ展示・ポスター講演,ネットワークプロセッサ,通信のための信号処理,無線LAN/PAN,一般)
- 論文発表プログラム自動作成ソフトウェア「江戸っ子」 : 偏りある割り当てへの対応(デモ展示・ポスター講演,ネットワークプロセッサ,通信のための信号処理,無線LAN/PAN,一般)
- 論文発表プログラム自動作成ソフトウェア「江戸っ子」 : 偏りある割り当てへの対応(デモ展示・ポスター講演,ネットワークプロセッサ,通信のための信号処理,無線LAN/PAN,一般)
- キーストロークダイナミクスでの評価関数の切替手法について(グラフ,ペトリネット,ニューラルネット及び一般)
- キーストロークダイナミクスでの評価関数の切替手法について(グラフ,べトリネット,ニューラルネット及び一般)
- 固定ルート上の情報ファイルの転送方法を求める線形時間のアルゴリズムについて
- 固定ルート上の情報ファイルの転送方法を求める線形時間のアルゴリズムについて
- ファイル加工ネットワーク上の最速のファイル圧縮転送について
- 非圧縮転送を考慮した,固定ルート上のファイルの最適な圧縮転送について(ネットワーク(1))
- ルートが固定された2点間の最短時間のファイル圧縮転送について
- 最短時間のファイル圧縮転送を与える2点を決定する線形時間のアルゴリズムについて
- 区間グラフ上の頂点のbetweennes値について
- 梯子型ネットワークの最短路を求める線形時間アルゴリズム
- 情報ファイルの最速な圧縮転送を求める2つの線形時間アルゴリズム
- B-21-9 アドホックネットワークでの経路探索での容量モデル活用(B-21.アドホックネットワーク,一般セッション)
- スタティックなアドホックネットワークにおけるシンクルーティングについて--ネットワークフローへの帰着 (アドホックネットワーク)
- An Optimal File Transfer on an Undirected Path Network with 2-level Arc Cost
- An Optimal File Transfer on an Undirected Path Network with 2-level Arc Cost
- 複製コストが増加するネットワークに対する最適なfile transferの構成について(グラフ,ペトリ,ニューラルネット,及び一般)
- 複製コストが増加するネットワークに対する最適なfile transferの構成について(グラフ,ペトリ,ニューラルネット,及び一般)
- 複製コストが増加するネットワークに対する最適な file transfer の構成について
- グラフを使った, 順序つきデータのコンセンサス作成法について
- グラフを使った, 順序つきデータのコンセンサス作成法について
- 発信局2個の2段階転送コストを持つパスネットワークにおける最小コストのファイル転送方法について(グラフ・ネットワーク(1))
- プログラミング演習としてのグラフ・ネットワーク理論
- 2段階転送コストを持つ, パス構造ネットワークでの最適なfile transferの構成について(III)
- 2段階転送コストを持つ,パス構造ネットワークでの最適なfile transferの構成について (II)
- 2段階転送コストを持つ,パス構造ネットワークでの最適なfile transferの構成について (II)
- B-18-3 A new dissimilarity measure in keystroke dynamics
- 2段階の転送コストを持つネットワークシステムでの最適な情報ファイルの転送について
- 2段階の転送コストを持つネットワークシステムでの最適な情報ファイルの転送について
- 2個の始点を持つファイル転送ネットワークの最適なファイルスケジューリングの構成について
- 2-中継点網の構成問題について
- ネットワークにおける,ファイル複製・転送総コストが最小となるための発信局設定について(グラフ・ネットワーク(2))
- 2段階転送コストを持つ, バス構造ネットワークでの最適なfile transferの構成について(I)
- 各点の需要値が高々1であるネットワークでの最適なfile transferの構成について
- 2段階転送コストを持つ,パス構造ネットワークでの最適なfile transferの構成について(2)
- オリジナルファイルを任意部数持つネットワークでの最適なファイル転送について
- ファイル転送ネットワークにおける枝の本数に制限のある最適なfile transferについて(II)
- ハミング距離似のフィルタリングを用いたキーストロークダイナミクスによるパスワード強化
- ハミング距離似のフィルタリングを用いたキーストロークダイナミクスによるパスワード強化
- 木構造のファイル複製ネットワークの最適な2 : ファイルスケジューリングについて
- ファイル転送ネットワーク上の最適な2-ファイルスケジューリングについて
- 1-H-1 Multi-data filtering method in keystroke dynamics-based user authentication
- ハミング距離似のフィルタリングを用いたキーストロークダイナミクスによるパスワード強化
- ソースファイルが点在するネットワーク上の森型ファイル転送の最適性について
- オリジナルファイルが任意部数与えられたファイル転送ネットワーク上の最適なfile transferの構成について(グラフ,ネットワークとアルゴリズムおよび一般)