(57)【要約】例えば音声、ビデオ、および／またはその他のデータ等のキャッシュ・データについて、キャッシュ・パフォーマンスの改善のために、将来のアクセス要求情報を含む情報を用いる方法およびシステム。典型例の実施形態によれば、キャッシュ・システム（２０）は、複数のデータ項目をキャッシュするように動作するキャッシュ（２２）を含んでいる。プロセッサ（２８）は、キャッシュ（２２）のデータ項目のうち少なくとも１つが、当該少なくとも１つのデータ項目の将来のアクセス要求情報を用いて置換されることを可能にするように動作する。
2008516334.tif 000002
【特許請求の範囲】
【請求項１】
キャッシュ・システムを運用する方法（３００）であって、
前記キャッシュ・システムのキャッシュにおいて、複数のデータ項目を受信するステップ（３１０）と、
前記キャッシュにおいて、少なくとも１つの前記データ項目に対する将来のアクセス要求情報を用いて、少なくとも１つの前記データ項目を置換するステップ（３２０、３９０）と、
を含む、前記方法。
【請求項２】
前記置換するステップが、前記少なくとも１つのデータ項目に対する過去のアクセス情報を用いるステップ（３４０、３６０）を更に含む、請求項１に記載の方法（３００）。
【請求項３】
前記過去のアクセス情報が、前記少なくとも１つのデータ項目が以前にアクセスされた回数を含む（３４０）、請求項２に記載の方法（３００）。
【請求項４】
前記過去のアクセス情報が、前記少なくとも１つのデータ項目が以前に最後にアクセスされた時刻を更に含む（３６０）、請求項２に記載の方法（３００）。
【請求項５】
前記将来のアクセス要求情報が、前記少なくとも１つのデータ項目が将来のアクセスを要求された時刻を含む、請求項１に記載の方法（３００）。
【請求項６】
前記少なくとも１つのデータ項目が、ビデオ・データを含む、請求項１に記載の方法（３００）。
【請求項７】
前記少なくとも１つのデータ項目が、音声データを含む、請求項１に記載の方法（３００）。
【請求項８】
データ処理装置（２０）であって、
複数のデータ項目をキャッシュするキャッシュ手段（２２）と、
前記キャッシュ手段（２２）において、少なくとも１つの前記データ項目が、少なくとも１つの前記データ項目に対する将来のアクセス情報を用いて置換されることを可能にする処理手段（２８）と、
を含む、前記データ処理装置。
【請求項９】
前記処理手段（２８）は、前記少なくとも１つのデータ項目が、前記少なくとも１つのデータ項目に対する過去のアクセス情報を用いて置換されることを可能にする、請求項８に記載のデータ処理装置（２０）。
【請求項１０】
前記過去のアクセス情報が、前記少なくとも１つのデータ項目が以前アクセスされた回数を含む、請求項９に記載のデータ処理装置（２０）。
【請求項１１】
前記過去のアクセス情報が、前記少なくとも１つのデータ項目が以前に最後にアクセスされた時刻を更に含む、請求項１０に記載のデータ処理装置（２０）。
【請求項１２】
前記将来のアクセス要求情報が、前記少なくとも１つのデータ項目が将来のアクセスを要求された時刻を含む、請求項８に記載のデータ処理装置（２０）。
【請求項１３】
前記少なくとも１つのデータ項目が、ビデオ・データを含む、請求項８に記載のデータ処理装置（２０）。
【請求項１４】
前記少なくとも１つのデータ項目が、音声データを含む、請求項８に記載のデータ処理装置（２０）。
【請求項１５】
キャッシュ・システム（２０）であって、
複数のデータ項目をキャッシュするように動作するキャッシュ（２２）と、
前記キャッシュ（２２）において、少なくとも１つの前記データ項目が、前記少なくとも１つのデータ項目についての将来のアクセス要求情報を用いて置換されることを可能にするようにするプロセッサ（２８）と、
を含む、前記キャッシュ・システム。
【請求項１６】
前記プロセッサ（２８）が、更に前記少なくとも１つのデータ項目が前記少なくとも１つのデータ項目についての過去のアクセス情報を用いて置換されることを可能にするように動作する、請求項１５に記載のキャッシュ・システム（２０）。
【請求項１７】
前記過去のアクセス情報が、前記少なくとも１つのデータ項目が以前アクセスされた回数を含む、請求項１６に記載のキャッシュ・システム（２０）。
【請求項１８】
前記過去のアクセス情報が、前記少なくとも１つのデータ項目が以前アクセスされた最後の時刻を更に含む、請求項１７に記載のキャッシュ・システム（２０）。
【請求項１９】
前記将来のアクセス要求情報が、前記少なくとも１つのデータ項目が将来のアクセスを要求された時刻を含む、請求項１５に記載のキャッシュ・システム（２０）。
【請求項２０】
前記少なくとも１つのデータ項目が、ビデオ・データを含む、請求項１５に記載のキャッシュ・システム（２０）。
【請求項２１】
前記少なくとも１つのデータ項目が、音声データを含む、請求項１５に記載のキャッシュ・システム（２０）。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に、例えば音声（オーディオ）、ビデオ、および／またはその他のデータ等のデータをキャッシングする技術に関する。そして、より詳細には、キャッシュ・パフォーマンス（性能）を改善するために、将来のアクセス要求情報を含む情報を用いてデータをキャッシングする方法およびシステムに関する。
【背景技術】
【０００２】
データ・キャッシングは、例えばメモリ・システム、ファイル・システム、およびインターネット（即ち、ウェブ）システム等のコンピュータ・システムの様々な形態において重要である。データ・キャッシングの基本的概念は、容量は限られるが比較的高速で高価な、エンドユーザに「身近な」キャッシュ記憶素子に、近い将来、アクセスが見込まれるデータを配置するためのものである。キャッシュの記憶容量は限られているので、キャッシュが満杯で、新規なデータ項目を導入する必要がある時に、キャッシュから追い出すべきデータ項目を決定する置換アルゴリズムは、あらゆるキャッシュ・システムの中核をなしている。
【０００３】
データ・アクセス順序は事前にはわからない場合があるので、既存のキャッシュ技術は過去のアクセス情報に基いた置換アルゴリズムを用いている。「最長時間未使用」（ＬＲＵ：Ｌｅａｓｔ  Ｒｅｃｅｎｔ  Ｕｓｅ）アルゴリズムとして知られている１つの既存の置換アルゴリズムは、一度アクセスされたデータ項目は将来再びアクセスされる見込みがあるという仮定に基づいている。従って、ＬＲＵアルゴリズムによれば、キャッシュされたデータ項目の中で最も長時間アクセスされていないデータ項目が最初に置換される。ＬＲＵアルゴリズムは、例えば、特にメモリおよびファイル・システムに適用することができる。
【０００４】
「最小使用頻度」（ＬＦＵ：Ｌｅａｓｔ  Ｆｒｅｑｕｅｎｔｌｙ  Ｕｓｅｄ）アルゴリズムとして知られているもう１つの既存の置換アルゴリズムは、頻繁にアクセスされたデータ項目は将来再びアクセスされる見込みがあるという仮定に基づいている。従って、ＬＦＵアルゴリズムによれば、キャッシュされたデータ項目の中で過去に最もアクセスされた回数が少ないデータ項目が最初に置換される。ＬＦＵアルゴリズムは、例えば、特にインターネットまたはウェブ・ベースのシステムに適用することができる。
【発明の開示】
【０００５】
例えば、上述したＬＲＵおよびＬＦＵアルゴリズム等の既存の置換アルゴリズムは、特定の用途には有益であるが、それらは過去のアクセス情報だけを用い、将来のアクセス情報を考慮に入れていないという点で不十分である。
【０００６】
従って、キャッシュ・パフォーマンス（性能）の向上のため、将来のアクセス要求情報を含む情報を用いたデータをキャッシングする技術が求められている。本発明は、これらの問題および／またはその他の問題に対処する。
【０００７】
本発明の１つの態様によれば、キャッシュ・システムを運用する方法が開示される。典型例の実施形態によれば、当該方法は、キャッシュ・システムのキャッシュにおいて複数のデータ項目を受信するステップと、将来のアクセス要求情報を用いて、当該キャッシュのデータ項目のうち少なくとも１つを少なくとも１つのデータ項目で置換するステップと、を含んでいる。
【０００８】
本発明の他の態様によれば、データ処理装置が開示される。典型例の実施形態によれば、当該データ処理装置は、複数のデータ項目をキャッシュするためのキャッシュ手段を含んでいる。処理手段は、将来のアクセス要求情報を用いて、キャッシュ手段のデータ項目のうち少なくとも１つが少なくとも１つのデータ項目で置換されることを可能にする。
【０００９】
本発明の更に別の態様によれば、キャッシュ・システムが開示される。典型例の実施形態によれば、当該キャッシュ・システムは、複数のデータ項目をキャッシュするように動作するキャッシュを含んでいる。プロセッサは、将来のアクセス要求情報を用いて、キャッシュのデータ項目のうち少なくとも１つが少なくとも１つのデータ項目で置換されることを可能にするようにする。
【発明を実施するための最良の形態】
【００１０】
以下、説明する例示は本発明の好適な実施形態についてなされるものであり、そのような例示は、いかなる方法でも本発明の範囲を限定するものとみなされるものではない。
【００１１】
図面、より詳細には図１を参照することにより、本発明を実施するのに適している典型的な環境１００が示される。図１に示すように、環境１００は、コンテンツ・サーバ１０と、１つ以上のキャッシュ・システム２０と、ユーザ装置３０と、を含んでいる。典型例の実施形態によれば、環境１００は、キャッシュ・システム２０を介して、コンテンツ・サーバ１０からユーザ装置３０まで音声、ビデオ、および／または他のデータを配信することが可能なネットワークを表している。
【００１２】
コンテンツ・サーバ１０は、データを記憶して、配信するように動作する。典型例の実施形態によれば、コンテンツ・サーバ１０は、音声、ビデオ、および／または他のデータを含むデータを記憶して、要求信号に応答してキャッシュ・システム２０を介してユーザ装置３０を含む１つ以上のユーザ装置にそれをダウンロードすることによって、この様なデータを配信するように動作する。コンテンツ・サーバ１０により記憶され、配信されるデータは、本明細書において、「データ項目（ｄａｔａ  ｉｔｅｍ）」と称されてもよく、この各データ項目は、例えば、映画、楽曲、その他の音声および／またはビデオ・コンテンツを表すことができる。
【００１３】
キャッシュ・システム２０は、データ・キャッシュ機能を含むデータ処理機能を実行するように動作する。典型例の実施形態によれば、各キャッシュ・システム２０は、コンテンツ・サーバ１０および／または他のキャッシュ・システム２０を含む１つ以上のデータソースからダウンロードされる音声、ビデオ、および／または他のデータをキャッシュし、キャッシュされたデータを要求信号に応答してユーザ装置３０を含む１つ以上のユーザ装置に提供するように動作する。例示および説明のために、図１において環境１００は、２つのキャッシュ・システム２０により示される。しかしながら、本発明によれば、キャッシュ・システムの数はこれに限定されず、より少ない、或いは、より多くの数のキャッシュ・システム２０が用いられてもよい。従って、実際に使用するキャッシュ・システム２０の数は、設計に応じて選択可能なものとしてよい。典型例の実施形態によれば、各キャッシュ・システム２０は、キャッシュ・パフォーマンスを改善するために、将来のアクセス要求情報を含む情報を用いる。各キャッシュ・システム２０に関する詳細は、本願明細書において、後述する。
【００１４】
ユーザ装置３０は、コンテンツ・サーバ１０および／またはキャッシュ・システム２０を含む１つ以上のデータ・ソースから、例えば音声、ビデオ、および／またはその他のデータ等のデータをダウンロードするための要求信号を生成し、こうしてダウンロードしたデータを受信して、処理するように動作する。典型例の実施形態によれば、ユーザ装置３０は、データ項目の要求信号を生成し、要求したデータ項目を受信することが可能なあらゆるタイプの装置、機器、またはシステムで実現可能である。例えば、ユーザ装置３０は、例えばテレビ受像機、コンピュータ、セットトップ・ボックス（ＳＴＢ）、ビデオ・カセット・レコーダ（ＶＣＲ）、ディジタル多用途ディスク（ＤＶＤ）プレーヤ、テレビ・ゲーム機、パーソナル・ビデオ・レコーダ（ＰＶＲ）、または他の装置等のあらゆるタイプの家電装置として実現することができるが、これらに限定されるものではない。ユーザ装置３０は、例えば携帯用のリモコン装置、有線および／または無線のキーボード、またはその他の入力装置等の、ユーザがユーザ装置３０に要求信号を生成させる入力を行うことが可能な入力部を含んでもよい。ユーザ装置３０は、表示装置を内臓してもよく、且つ／或いは付属の表示装置と連動してもよい。
【００１５】
図２を参照すると、図１の各キャッシュ・システム２０の更に典型的な詳細を説明するブロック図が示されている。図２に示すように、各キャッシュ・システム２０は、例えばキャッシュ２２等のキャッシュ手段および例えばプロセッサ２８等の処理手段を含んでいる。前述の図２に示す構成要素は、１つ以上の集積回路（ＩＣ）を用いて実現することができる。記載を明瞭にするために、キャッシュ・システム２０に関連する電源信号および／またはその他の構成要素など特定の従来の構成要素の中には、図２には示されていないものもある。
【００１６】
キャッシュ２２は、キャッシュ・システム２０のデータ・キャッシュ機能を実行するように動作する。典型例の実施形態によれば、プロセッサ２８の制御に基づいて、キャッシュ２２は、例えばコンテンツ・サーバ１０および／またはその他のキャッシュ・システム２０等の１つ以上のデータ・ソースからダウンロードされる音声、ビデオ、および／またはその他のデータを含むデータをキャッシュするように動作する。また、典型例の実施形態によれば、キャッシュ２２は、音声、ビデオ、および／またはその他のデータを含むキャッシュ・データをプロセッサ２８の制御に基づいてその他のキャッシュ・システム２０および／またはユーザ装置３０にダウンロードするように動作する。
【００１７】
プロセッサ２８は、キャッシュ・システム２０の様々な処理機能を実行するように動作する。典型例の実施形態によれば、プロセッサ２８は、データをダウンロードする機能を実現するために、他のキャッシュ・システム２０および／またはユーザ装置３０から供給される要求信号を受信し、処理するように動作する。図２に示すように、プロセッサ２８は、受信した要求信号に応答して新たな要求信号を生成してコンテンツ・サーバ１０および／または他のキャッシュ・システム２０に送り、これにより１つ以上の要求データ項目をキャッシュ２２にダウンロードさせることができる。プロセッサ２８はまた、キャッシュ２２のデータ項目が置換されることを可能にする置換アルゴリズムを実行するように動作する。典型例の実施形態によれば、プロセッサ２８は、キャッシュ２２の１つ以上のデータ項目が、将来のアクセス要求情報を用いて、１つ以上のデータ項目で置換されることを可能にする制御信号を供給するように動作する。
【００１８】
この典型例の実施形態によれば、キャッシュ２２に保存される各データ項目は、個別のデータ項目について将来のアクセスを要求された時刻を示す将来のアクセス要求情報を含んでいてもよい。個別のデータ項目に対する将来のアクセス時刻は、そのデータ項目に対する事前のユーザ要求に基づいてもよい。
【００１９】
本願明細書において後述するように、プロセッサ２８は、キャッシュ２２において将来のアクセス時刻が一番遠いデータ項目が最初に置換されるようにすることができる。更に、プロセッサ２８は、置換アルゴリズムを実現するときに、データ項目の過去のアクセス情報を用いてもよい。典型例の実施形態によれば、この個別のデータ項目の過去のアクセス情報は、当該データ項目が以前にアクセスされた回数および／または、当該データ項目がアクセスされた最新の時刻を含んでいてもよい。これらの本発明の態様に関する詳細は、本願明細書において後述する。
【００２０】
本発明の理解を容易にするために、ここで実施例を用いて説明する。
【００２１】
図３を参照すると、本発明の典型例の実施形態によるステップを説明するフローチャート３００が示されている。理解を容易にするための例として、図３のステップは、図１の環境１００で図２のキャッシュ・システム２０を用いた場合について説明している。図３のステップは、典型例の一つにすぎず、いかなる方法によっても本発明を限定することを意図するものではない。
【００２２】
ステップ３１０で、複数のデータ項目は、対応するキャッシュ・システム２０のキャッシュ２２に配置される。典型例の実施形態によれば、データ項目は、ユーザ要求信号に応答して、例えばコンテンツ・サーバ１０または他のキャッシュ・システム２０等のデータ・ソースから、キャッシュ２２にダウンロードされる。データ項目は、例えば、映画、楽曲、またはその他のコンテンツを示す音声、ビデオ、および／またはその他のデータを含んでもよい。また、典型例の実施形態によれば、ステップ３１０で、キャッシュ２２に配置されている各データ項目Ｃｉは、各々対応する値を示すｆｉ、ｎｉ、およびｐｉの少なくとも３つの情報を含んでいる。第１の情報要素ｆｉは、データ項目Ｃｉに対する、最初の将来のアクセス時刻を示す。換言すれば、最初の将来のアクセス時刻ｆｉは、データ項目Ｃｉが次回のアクセスを要求された将来の時刻を示す。将来のアクセス情報が所定のデータ項目Ｃｉに対して存在しない場合、ｆｉは無限大にセットされる。例えば、データ項目Ｃｉがキャッシュ２２にダウンロードされ、データ項目Ｃｉに対して将来のアクセス要求がない場合にこのことが起こりうる。第２の情報要素ｎｉは、データ項目Ｃｉが以前にアクセスされた回数を示す。第３の情報要素ｐｉは、データ項目Ｃｉの最後のアクセス時刻を示す。
【００２３】
ステップ３２０で、将来のアクセス時刻が一番遠いデータ項目が識別される。典型例の実施形態によれば、ステップ３２０で、プロセッサ２８は、キャッシュ２２のデータ項目の各々の最初の将来のアクセス時刻ｆｉを調べる。この典型例の実施形態によれば、ステップ３２０で、キャッシュ２２においてｆｉが最大の値を有する１つ以上のデータ項目がプロセッサ２８により識別される。
【００２４】
ステップ３３０で、ステップ３２０で複数のデータ項目が識別されたかどうかが判定される。典型例の実施形態によれば、ステップ３３０で、プロセッサ２８は、キャッシュ２２においてｆｉが最大の値を有するデータ項目が複数あるかどうかを判定する。
【００２５】
ステップ３３０の判定が否である場合、処理フローはステップ３９０へ進み、ステップ３２０で識別された１つのデータ項目が新規なデータ項目と置き換えられる。典型例の実施形態によれば、ステップ３９０で、プロセッサ２８は、１つ以上の制御信号をキャッシュ２２に提供してデータ項目の置換を実施する。
【００２６】
或いは、ステップ３３０で該当するデータ項目が複数あると判定した場合、処理フローは、ステップ３４０へ進み、ステップ３２０で識別された複数のデータ項目のうち最も少ない頻度でアクセスされたデータ項目が識別される。典型例の実施形態によれば、ステップ３４０で、プロセッサ２８は、ステップ３２０で識別された複数のデータ項目を調べて、それらのデータ項目のうちｎｉが最小の値を有する１つ以上のデータ項目を識別する。
【００２７】
ステップ３５０で、複数のデータ項目がステップ３４０で識別されたかどうかが判定される。典型例の実施形態によれば、ステップ３５０で、プロセッサ２８は、ステップ３４０で識別されたｎｉが最小の値を有するデータ項目が複数あるかどうかを判定する。
【００２８】
ステップ３５０の判定が否である場合、処理フローはステップ３９０へ進み、ステップ３４０で識別された１つのデータ項目が新規なデータ項目と置き換えられる。典型例の実施形態によれば、ステップ３９０で、プロセッサ２８は、１つ以上の制御信号をキャッシュ２２に提供してデータ項目の置換を実施する。
【００２９】
或いは、ステップ３５０で該当するデータが複数あると判定した場合、処理フローはステップ３６０へ進み、ステップ３４０で識別された複数のデータ項目の中で最後にアクセスされてから最も長い時間が経過したデータ項目が識別される。典型例の実施形態によれば、ステップ３６０で、プロセッサ２８は、ステップ３４０で識別された複数のデータ項目を調べて、それらのデータ項目のうちｐｉが最も小さい値を有する１つ以上のデータ項目を識別する。
【００３０】
ステップ３７０で、複数のデータ項目がステップ３６０で識別されたかどうかが判定される。典型例の実施形態によれば、ステップ３７０で、プロセッサ２８は、ステップ３６０で、ｐｉが最も小さい値を有するデータ項目が複数あるかどうかを判定する。
【００３１】
ステップ３７０の判定が否である場合、処理フローはステップ３９０へ進み、ステップ３６０で識別された１つのデータ項目が新規のデータ項目と置き換えられる。典型例の実施形態によれば、ステップ３９０で、プロセッサ２８は、１つ以上の制御信号をキャッシュ２２に提供してデータ項目の置換を実施する。
【００３２】
或いは、ステップ３７０で該当するデータが複数あると判定した場合、処理フローはステップ３８０へ進み、キャッシュ２２からの１つのデータ項目がランダムに選択され、本願明細書において既に説明したように、ステップ３９０で、プロセッサ２８の制御に基づいて置換される。異なる選択基準を適用することもできるが、典型例の実施の形態によれば、ステップ３８０で、プロセッサ２８は、キャッシュ２２の最後のデータ項目を選択する。
【００３３】
上記の図３のステップは、所定の順序でデータ項目をキャッシュ２２に配列した後、新規なデータ項目を受信した際に、当該所定の順序の最後のデータ項目を置換することにより実行することができる。
【００３４】
データ項目の当該所定の順序は、以下の通りである。キャッシュ２２の全てのデータ項目は、まず、上記のｆｉの値に基づいて、昇順（即ち、最大のものが最後）で配列される。複数のデータ項目が同じｆｉの値を有する場合（例えば、無限値を有する２つのデータ項目は、等価とみなされる）、同じｆｉの値を有するそれらのデータ項目は上記のｎｉの値に基づいて、降順（即ち、最小のものが最後）で配列される。複数のデータ項目が同じｎｉの値を有する場合、同じｎｉの値を有するデータ項目は上記のｐｉの値に基づいて、降順（即ち、最小のものが最後）で配列される。最後に、等しいｐｉの値を有するデータ項目が残った場合、それら残留データ項目はランダムに配列される。置換がなされなければならないときに、当該順序で最後のデータ項目が置換される。
【００３５】
図４および図５を参照すると、図３の置換アルゴリズムのシミュレーション結果が示されている。これらのシミュレーション結果は、図３の置換アルゴリズムが既存の特定の置換アルゴリズムより良い結果を提供することを示している。
【００３６】
あらゆるキャッシュ・システムにおいて重要なパラメータは、全アクセス回数に対する個別のデータ項目のアクセス回数の比率で示される「的中率（ｈｉｔ  ｒａｔｉｏ：ヒット率）」である。図４は、異なる置換アルゴリズムの的中率を異なるキャッシュ容量（ｘ軸に沿う数は、データ項目の大きさが一様であると仮定した場合のキャッシュの記憶容量を示す）に対して説明するグラフ４００である。図５は、異なる置換アルゴリズムの的中率をキャッシュの異なる数のデータ項目に対して説明するグラフ５００である。
【００３７】
図４および図５に示されるシミュレーション結果は、ユーザがビデオの要求をして、後でそれらをダウンロードするとした場合の、ビデオのダウンロード・シナリオに基づく。これらのビデオのアクセス・パターンは、ビデオレンタル、図書館の本の貸し出し等を表現するために多用される周知のＺｉｐｆ分布に基づく。要求到着は、平均到着間隔を３分とするポアソン分布に基づき、遅延時間は、平均時間を３時間とする正規分布に基づく。
【００３８】
図４および図５は、図３の（「計画された（ｓｃｈｅｄｕｌｅｄ）」）置換アルゴリズムに加えて、本願明細書において先述のＬＦＵアルゴリズムと、経験的に最も人気があるデータ項目をキャッシュに配置する静的なアルゴリズムと、および達成可能な最大的中率を生じる最適なアルゴリズムと、の結果を示す。図４および図５から示されるように、特に異なるデータ項目の合計数が比較的小さい（例えば、図５の２０００未満を参照）ときに、図３の置換アルゴリズムは他の現実的な置換アルゴリズムより一貫して高い的中率を生じる。本願明細書において説明している様に、キャッシュ・パフォーマンスの改善のために、例えば音声、ビデオ、および／または他のデータ等のデータをキャッシングする方法およびシステムは、将来のアクセス要求情報を含む情報を用いる。
【００３９】
本発明は好適な設計を有するものとして説明しているため、本発明はこの開示の趣旨および範囲内において、更に変更されることができる。例えば、本発明は、本願明細書において、明確に記載されている以外の方法で、将来のアクセス要求情報を用いるキャッシュ・システムに適用することができる。本特許出願は、従って、その一般の原理を用いる本発明のあらゆるバリエーション、使用、または適応をもカバーすることを意図している。更に、本特許出願は、本発明が関係し、特許請求の範囲に入る、当該技術の周知或いは慣習的な実行の範囲内において、本開示の範囲からの派生の範囲をカバーすることを意図している。
【図面の簡単な説明】
【００４０】
本発明の上記のおよび他の特徴および優位性、並びにそれらを達成する方法については、添付図面に関連付けて、本発明の実施形態の以下の説明を参照することにより、より明確になり、更に理解が進むことであろう。
【図１】本発明を実施するのに適当な典型的な環境を示す図である。
【図２】図１の各キャッシュ・システムの更に典型的な詳細を説明するブロック図である。
【図３】本発明の典型例の実施形態によるステップを示すフローチャートである。
【図４】異なるキャッシュ容量に対する、異なる置換アルゴリズムの的中率を説明するグラフである。
【図５】異なるデータ項目数に対する、異なる置換アルゴリズムの的中率を説明するグラフである。
【図１】
2008516334.tif 000003
【図２】
2008516334.tif 000004
【図３】
2008516334.tif 000005
【図４】
2008516334.tif 000006
【図５】
2008516334.tif 000007
【手続補正書】
【提出日】平成19年10月2日(2007.10.2)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
キャッシュ・システムを運用する方法であって、
前記キャッシュ・システムのキャッシュにおいて、複数のデータ項目を受信するステップと、
前記キャッシュにおいて、少なくとも１つの前記データ項目に対するアクセス要求情報における将来のアクセス時刻および過去のアクセス情報を用いて、少なくとも１つの前記データ項目を置換するステップと、
を含む、前記方法。
【請求項２】
前記置換される少なくとも一つのデータ項目は、最も遠い将来のアクセス時刻を有する前記データ項目の１つである、請求項１に記載の方法。
【請求項３】
前記過去のアクセス情報が、前記少なくとも１つのデータ項目が以前にアクセスされた回数を含む、請求項１に記載の方法。
【請求項４】
前記過去のアクセス情報が、前記少なくとも１つのデータ項目が以前に最後にアクセスされた時刻を更に含む、請求項１に記載の方法。
【請求項５】
前記将来のアクセス要求情報が、前記少なくとも１つのデータ項目が以前にアクセスされた時刻を含む、請求項１に記載の方法。
【請求項６】
前記少なくとも１つのデータ項目が、ビデオ・データを含む、請求項１に記載の方法。
【請求項７】
前記少なくとも１つのデータ項目が、音声データを含む、請求項１に記載の方法。
【請求項８】
データ処理装置であって、
複数のデータ項目をキャッシュするキャッシュ手段と、
前記キャッシュ手段において、少なくとも１つの前記データ項目が、少なくとも１つの前記データ項目に対するアクセス要求情報における将来のアクセス時刻と過去のアクセス情報を用いて置換されることを可能にする処理手段と、
を含む、前記データ処理装置。
【請求項９】
前記置換される少なくとも一つのデータ項目は、最も遠い将来のアクセス時刻を有する前記データ項目の１つである、請求項８に記載のデータ処理装置。
【請求項１０】
前記過去のアクセス情報が、前記少なくとも１つのデータ項目が以前アクセスされた回数を含む、請求項８に記載のデータ処理装置。
【請求項１１】
前記過去のアクセス情報が、前記少なくとも１つのデータ項目が以前に最後にアクセスされた時刻を更に含む、請求項８に記載のデータ処理装置。
【請求項１２】
前記将来のアクセス要求情報が、前記少なくとも１つのデータ項目が以前にアクセスされた時刻を含む、請求項８に記載のデータ処理装置。
【請求項１３】
前記少なくとも１つのデータ項目が、ビデオ・データを含む、請求項８に記載のデータ処理装置。
【請求項１４】
前記少なくとも１つのデータ項目が、音声データを含む、請求項８に記載のデータ処理装置。
【国際調査報告】
2008516334.tif 000008