P2Pファイル共有システムにおけるクエリトレンドパターンの分析

摘要

In P2P file sharing systems, caching of contents is one of practical methods to improve the search efficiency and the load balancing. Since the resources (e.g., disk spaces) for caching are limited, the contents to be cached may vary according to the cache replacement algorithm. However, typical cache replacement algorithms do not consider the time-dependent trends of query keywords. Therefore, the problem that many of caches that might not be effectively used remains comes to happen. Therefore, the cache replacement algorithms is necessary. In this paper, we analyze the time-dependent trends of query keywords in P2P file sharing system towards a new cache replacement method which takes query trends into consideration. First, we collect keyword (filename) queries by crawling the P2P file sharing system. We then analyze similarities of time-dependent trends of queries by using Discrete Fourier Transform. We then categorize trend pattern by applying the hierarchical clustering. As a result, we show that time-dependent trend patterns of query can be categorized into four types.%P2Pファイル共有システムでは，負荷分散や検索効率の向上を目的としたコンテンツのキャッシュ（複製）が行われている．ピアのキャッシュ容量は有限であるため，時刻やアクセス頻度によってキャッシュ内容の更新が行われている．しかし，コンテンツへの要求の時間的傾向（トレンド）を考慮したキャッシュ内容の更新は行われていない．そのため、有効に活用されることのないキャッシュが残存するという問題が起こることとなる．そこで、トレンドパターンを考慮した，効率的な新しいキャッシュ置き換えアルゴリズムを考案する必要がある．本稿では，トレンドパターンを考慮した新しいキャッシュ置き換えアルゴリズムを提案するために必要となる，P2Pファイル共有システムにおけるトレンド分析を行う．そのためにまず，P2Pファイル共有システムをクロールし，P2Pファイル共有システム上を流れる検索クエリの計測を行う．さらに，計測した個々のクエリの時系列推移データに対して離散フーリエ変換（DFT）を適用することにより，個々のクエリの時系列推移パターン間の非類似度を導出し，階層的クラスタリングによりトレンドパターンの分類を行った．その結果，P2Pファイル共有システムにおけるトレンドパターンは大きく4種類に分類できることが分かった．