【手続補正書】
【提出日】平成24年6月25日(2012.6.25)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
記憶媒体に記憶された、内容参照可能データを構築するシステムであって、
不変の規則的なブロックの集合と、不変の検索可能なブロックの集合とを有し、
前記不変の規則的なブロックの集合の各規則的なブロックは、前記システムによってそれぞれの規則的なブロックのデータ内容から導き出された内容アドレスで参照することができ、
前記不変の検索可能なブロックの集合の各検索可能なブロックは、それぞれの検索可能なブロックのユーザーが定めた検索キーで参照することができ、ＤＡＧノードとして前記規則的な複数のブロックの少なくとも部分集合を含む有向非巡回グラフ（ＤＡＧ）の根源である、
システム。
【請求項２】
前記規則的なブロックおよび前記検索可能なブロックの各々は、ＤＡＧポインタとして働く露出した内容アドレス、またはバイナリデータのバイトの少なくとも一方を含む、請求項１に記載のシステム。
【請求項３】
前記内容アドレスの各々は、それぞれの規則的なブロックのデータ内容にハッシュ関数を適用することによって導き出され、前記検索可能なブロックの各々は、それぞれの検索可能なブロックの対応する、ユーザーが定めた検索キーに前記ハッシュ関数を適用することによって得られる内部保持キーで場所を特定することができる、請求項１に記載のシステム。
【請求項４】
前記規則的なブロックの集合および検索可能なブロックの集合は、前記内容アドレスおよび前記内部保持キーを対応する規則的なブロックおよび検索可能なブロックにそれぞれマッピングする分散ハッシュテーブルに記憶されている、請求項３に記載のシステム。
【請求項５】
前記検索可能な複数のブロックの少なくとも部分集合が検索可能なブロックのバージョン化されたシーケンスを構成し、前記シーケンスの各検索可能なブロックは異なるバージョン番号によって特定され、対応する、ユーザーが定めた検索キーで検索可能である、請求項１に記載のシステム。
【請求項６】
少なくとも１つの削除元をさらに有し、
各削除元は、１つの前記検索可能なブロックのユーザー定義の検索キーから導き出された内部削除キーで書き込まれ、前記検索可能なブロックの１つに削除の印を付ける、
請求項１に記載のシステム。
【請求項７】
前記規則的なブロックの集合、前記検索可能なブロックの集合、および前記少なくとも１つの削除元は、前記内容アドレス、前記内部保持キー、および前記内部削除キーを対応する規則的なブロック、検索可能なブロック、および削除元にそれぞれマッピングする分散ハッシュテーブルに記憶されている、請求項６に記載のシステム。
【請求項８】
削除の印が付けられていないあらゆる検索可能なブロックから到達できないブロックを削除するように構成されたガーベッジコレクションモジュールをさらに有する、請求項７に記載のシステム。
【請求項９】
記憶媒体を含む連想記憶システム上のデータを管理する方法であって、
ユーザーが定めた検索キーとデータ内容とを含む書き込み要求を受け取り、不変の検索可能なブロックを書き込むことと、
前記ユーザーが定めた検索キーに基づいて内部保持キーを導き出すことと、
前記検索可能なブロックが不変の規則的なブロックの有向非巡回グラフ（ＤＡＧ）を根づかせるように、前記記憶媒体に前記不変の検索可能なブロックを記憶することと、
を含み、
前記検索可能なブロックは前記データ内容を含み、かつ前記内部保持キーで場所を特定することができ、前記規則的なブロックの各アドレスは、それぞれの規則的なブロックの内容から導き出された内容アドレスである、
方法。
【請求項１０】
前記導き出すことは、前記ユーザーが定めた定義の検索キーにハッシュ関数を適用して前記内部保持キーを生成することをさらに含み、前記内容アドレスは、それぞれの規則的なブロックの各々に記憶された内容に前記ハッシュ関数を適用することによって生成されたハッシュキーから導き出される、請求項９に記載の方法。
【請求項１１】
分散ハッシュテーブル（ＤＨＴ）が前記内部保持キーおよび前記内容アドレスを前記検索可能なブロックおよび対応する規則的なブロックにそれぞれマッピングするように、前記検索可能なブロックおよび前記内部保持キーを該分散ハッシュテーブル（ＤＨＴ）に挿入することをさらに含む、請求項１０に記載の方法。
【請求項１２】
前記挿入前にＤＨＴルックアップを実行して前記内部保持キーを前記ＤＨＴのエントリと比較することをさらに含み、前記挿入は、前記ＤＨＴが前記内部保持キーを含んでいない場合、または該ＤＨＴが前記内部保持キーを含み、かつ該内部保持キーを前記データ内容と同一の値にマッピングする場合に行われる、請求項１１に記載の方法。
【請求項１３】
前記ユーザーが定めた定義の検索キーを含む読み出し要求を受け取り、前記データ内容を検索することと、
前記読み出し要求を受け取ることに応答して、前記ハッシュ関数を前記ユーザーが定めた検索キーに適用して、前記内部保持キーを導き出すことと、
前記内部保持キーでＤＨＴルックアップを実行して、前記データ内容を検索することと、
をさらに含む、請求項１２に記載の方法。
【請求項１４】
バージョン番号を持つ、ユーザーが定めた定義の検索キーを内部的に追加して、前記検索可能なブロックを、検索可能なブロックのバージョン化されたシーケンスの構成要素として特定することをさらに含み、前記内部保持キーは前記ユーザーが定めた検索キーおよび前記バージョン番号の両方に基づいている、請求項１３に記載の方法。
【請求項１５】
前記読み出し要求は、前記バージョン化されたシーケンスの一部である前記検索可能なブロックのバージョンを検索する前記バージョン番号を含む、請求項１４に記載の方法。
【請求項１６】
前記ユーザーが定めた検索キーを含む削除要求を受け取り、前記データ内容を削除することと、
前記検索キーに基づいて内部削除キーを導き出すことと、
前記内部削除キーで削除元ブロックを前記記憶媒体に書き込み、前記検索可能なブロックに削除の印を付けることと、
をさらに含む、請求項９に記載の方法。
【請求項１７】
前記検索可能なブロックに関連付けられた規則的なブロックにガーベッジコレクション動作を行うことをさらに含む、請求項１６に記載の方法。
【請求項１８】
記憶媒体を含む連想記憶システム上のデータを削除する方法であって、
前記記憶媒体に記憶された検索可能なブロックによって根づかされた規則的なブロックの有向非巡回グラフ（ＤＡＧ）を有する不変のデータブロックの集合を提供することを含み、各検索可能なブロックはそれぞれの検索可能なブロックの、ユーザーが定めた検索キーで場所を特定することができ、各規則的なブロックはそれぞれの規則的なブロックの内容から導き出された内容アドレスで場所を特定することができ、
前記ユーザーが定めた検索キーの１つである第１の検索キーを含む要求を受け取り、前記ＤＡＧの１つで編成されたデータ内容に削除の印を付けることと、
前記第１の検索キーに基づいて内部削除キーを導き出すことと、
前記内部削除キーで削除元ブロックを前記記憶媒体に書き込むことと、
前記記憶媒体から、前記削除元ブロックと、前記第１の検索キーで場所が特定可能な前記検索可能なブロックを削除することと、
を含む、記憶媒体を含む連想記憶システム上のデータを削除する方法。
【請求項１９】
前記削除することは、
前記削除元と、前記第１の検索キーで場所を特定することができる検索可能なブロックに削除の印を付けることと、
削除の印を付けられていない検索可能なブロックから到達できない規則的なブロックすべてに反復して削除の印を付けることと、
削除の印を付けられたブロックすべてを取り除くことと、
をさらに含む、請求項１８に記載の方法。