成 凱、 上林弥彦 京都大学大学院 情報学研究科 社会情報学専攻 DBWeb2000合同シンポジウム （12月06日～08日・東京）

Presentation on theme: "成 凱、 上林弥彦 京都大学大学院 情報学研究科 社会情報学専攻 DBWeb2000合同シンポジウム （12月06日～08日・東京）"— Presentation transcript:

1 成 凱、 上林弥彦 京都大学大学院 情報学研究科 社会情報学専攻 DBWeb2000合同シンポジウム （12月06日～08日・東京）
コンテンツを意識する ウェブキャッシュ 成　　凱、　　上林弥彦 京都大学大学院　情報学研究科　社会情報学専攻 DBWeb2000合同シンポジウム （12月06日～08日・東京）

2 発表内容 背 景 ウェブキャッシュとその特徴 従来のウェブキャッシュ手法の欠点 セメンチックスよりアクセス傾向の推定
背　景 ウェブキャッシュとその特徴 従来のウェブキャッシュ手法の欠点 セメンチックスよりアクセス傾向の推定 コンテンツを意識するウェブキャッシュ コンテンツを意識する置換手法LRU-SP+ 実験結果とディスカッション 2000年12月7日 （C）上林研究室

3 サーバ能力、ネットワーク帯域幅増加だけではいけなくて 冗長データ技術（キャッシュなど）は必要不可欠
背　景 アクセススピード：ウェブユーザの最も気になる要素（GUVインターネットユーザ調査・98） Scalability対策→キャッシュ必要不可欠 インターネット・トラフィック：ウェブは75％あまり かつ半年ぐらい倍になる しかしネットワーク帯域幅：僅か年に50％増加 サーバ能力、ネットワーク帯域幅増加だけではいけなくて 冗長データ技術（キャッシュなど）は必要不可欠 2000年12月7日 （C）上林研究室

4 ウェブキャッシュとは ウェブアクセスを効率化するミッドルウェア よくアクセスされるものをキャッシュに格納 三種類： WWW 繰り返し 再利用
プロキシ・キャッシュ サーバ逆キャッシュ ブラウザ・キャッシュ 複数ユーザ 共　　　　有 2000年12月7日 （C）上林研究室

5 キャッシュに関する問題 置換手法→ヒット率（Ｈｉｔ Rate）もっと高める 一致性維持→コンテンツの新鮮さ
1 2 置換手法→ヒット率（Ｈｉｔ Rate）もっと高める 一致性維持→コンテンツの新鮮さ コンテンツ管理→キャッシュコンテンツを共有情報源として積極的利用 法的・倫理的・経済的な問題 著作権 プライバシー ウェブ広告ヒット数 2000年12月7日 （C）上林研究室

6 ウェブキャッシュの特徴 従来のキャッシュ ウェブキャッシュ キャッシュ・ユーザ システム 人 間 働く環境 CPU、OS、DBなど WWW
人　間 働く環境 CPU、OS、DBなど WWW データ単位 物理的・ブロック 論理的・ウェブページ データサイズ 単一、小さい 大きい差がある 時間制約 厳しい 余裕がある アルゴリズム 簡　単、履歴ベース 複　雑 性能測定 Hit Rate Hit Rate、Byte Hit Rate 2000年12月7日 （C）上林研究室

7 従来のウェブキャッシュ手法の欠点 利用履歴だけに基づくキャッシュ置換手法 アクセス履歴データなしでも測定できる方法は？？
アクセス頻度→60％一度しかアクセスしてない→判断できず アクセス時間 キャッシュ空間 観測時間が必要 新入者 被観測者 置換該当者 アクセス履歴データなしでも測定できる方法は？？ 2000年12月7日 （C）上林研究室

8 提案：コンテンツを意識するキャッシュ Request/Response （Hits/Misses） ④人気内容をユーザに推薦など
①　情報要求解析 どんな内容が欲しいか？ ②新規内容測定 ③キャッシュ置換 2000年12月7日 （C）上林研究室

9 新しいキャッシュ構造 制約条件 ユーザ・興味 制御部 CKBルール ストレージ ロード ブラウジング 索 引 WWW 質問 サーチ
子キャッシュ 制約条件 ユーザ・興味 制御部 CKBルール ストレージ ロード ブラウジング 索　引 WWW 質問 サーチ 2000年12月7日 （C）上林研究室

10 ユーザ情報要求（Needs）解析 順番 MFQ言葉 重み 1 Movie 3 2 database hardcore 4 Gambling
1. Most Frequently Queried 2. Most Frequently Appeared 順番 MFQ言葉 重み 1 Movie 3 2 database hardcore 4 Gambling 5 Investing 6 Game 順番 MFA言葉 重み 1 Gambling 3 2 Game Investing 4 Movie 5 ticket 6 Java W1 = 0.7 W2 = 0.3 2000年12月7日 （C）上林研究室

11 セメンチックスよりアクセス傾向の推定 順番 人気トピックP 重み 1 Movie 2.7 2 Gambling 2.3 3 Database
2.1 4 Investing 2.0 5 Game 1.6 6 hardcore 1.4 Document 内容による人気度 （類似度計算）） 2000年12月7日 （C）上林研究室

12 セメンチックスを利用する利点 内容による人気度推定 観察時間短縮 時空効率 高い 情報要求 キャッシュ空間 人気内容 置換該当者 空いている
　高い キャッシュ空間 人気内容 置換該当者 空いている 非人気内容 2000年12月7日 （C）上林研究室

13 従来のウェブキャッシュ手法 アルゴリズム 最近度 頻度 サイズ LRU O X LFU SIZE Size-Ajusted LRU
Segmented LRU LRU-SP 2000年12月7日 （C）上林研究室

14 コンテンツを意識するLRU-SP+ LRU-SP(Size-adjusted and Popularity-aware LRU, K. Cheng et al Compsac’00) LRU-SP+ (Content-Sensitive LRU-SP) 利益 小さいものをキャッシングしない RF：引用頻度； アクセス最近度 小さいものをキャッシングしない 利益 2000年12月7日 （C）上林研究室

15 LRU-SP+の実装について ③. 最終決置換 一番小さい ②.置換候補 時間的に最も長く 引用されてないもの Hit ①．オブジェクト分類
2.5KB 一番小さい 2.5KB 5KB ②.置換候補 時間的に最も長く 引用されてないもの 2.5KB 5KB Hit 2.4KB/2 4KB/2 5.2KB 5.2KB/2 5.02KB ①．オブジェクト分類 2000年12月7日 （C）上林研究室

16 実験設計 実験内容の選択 実験モデル： “コンテンツ人気度“＝１＋ コンテンツによる人気度測定は正確か?（実験中）
コンテンツの人気度＝長期的人気度?（実験中） 長期的人気度を用いてキャッシュ効率高める？ 実験モデル： “コンテンツ人気度“＝１＋ 　　　　ドキュメントAのアクセス回数　　　　　　 実験データでのすべてのアクセス記録数 2000年12月7日 （C）上林研究室

17 実験結果： Hit Rates 2000年12月7日 （C）上林研究室

18 実験結果： Byte Hit Rates 2000年12月7日 （C）上林研究室

19 終わりに ウェブの人間向き、ドキュメントベースの特徴を生かし、キャッシュ（データ！）とキャッシュの使い道（情報！）を再び検討すべき
コンテンツを積極的に利用しキャッシュ効率を高める方法は提案した。 実験的検証について コンテンツもワークロードもあるBenchmarkはない　→　シミュレーション的検証は困難 実験内容を分けて、段階的にやる必要がある 2000年12月7日 （C）上林研究室