(57)【特許請求の範囲】
【請求項１】
ドキュメントおよびフォルダの階層編成システムにおいて、コンピュータが、指定された検索条件に基づいて検索された１つまたは２つ以上のドキュメントの中から、指定されたスコープであって、前記スコープはディレクトリ構造を有するフォルダの集まりである、そのようなスコープに合致する少なくとも１つのドキュメントでもって照会に応答する方法であって、該方法は、前記照会に応答して、
前記コンピュータが、指定された検索条件に基づいて検索された１つまたは２つ以上のドキュメントの中の一つのドキュメントをカレントドキュメントとして選択するステップと、
前記コンピュータが、前記カレントドキュメントの識別子を取得するステップと、
前記コンピュータが、前記カレントドキュメントの親フォルダの識別子を取得するステップと、
前記コンピュータが、前記親フォルダの識別子をキーとして用いてインデックス情報であるデータ構造にアクセスするステップであって、該データ構造は前記親フォルダの前記識別子と該識別子でインデックスされたフラグとからなるエントリを含む、そのようなデータ構造にアクセスするステップと、
前記コンピュータが、前記データ構造への前記アクセスによって、前記データ構造から応答を受け取るステップであって、該応答は前記カレントドキュメントが前記スコープ内にあるかどうかを示す値をもつフラグ、または前記親フォルダの識別子が前記データ構造内にないとの通知を含む、そのような応答を受け取るステップと、
前記コンピュータが、前記フラグを受け取ったとき、その値が前記カレントドキュメントが前記スコープ内にあることを示すかどうかを判断し、前記カレントドキュメントが前記スコープ内にあれば、前記カレントドキュメントの情報を前記照合の応答として返すステップと、
前記コンピュータが、前記親フォルダの識別子が前記データ構造内にないとの通知を受け取ったとき、前記親フォルダを、指定された前記スコープと比較して前記カレントドキュメントが前記スコープ内にあるかどうかを判断し、該判断結果に基づいて前記親フォルダの識別子と該識別子でインデックスされたフラグであって前記カレントドキュメントがスコープ内にあるかどうかを示す値をもつフラグとからなるエントリを前記データ構造に追加し、前記カレントドキュメントが前記スコープ内にあれば、前記カレントドキュメントの情報を結果セットに追加するステップとを備え、
前記カレントドキュメントの情報を結果セットに追加するステップの後は、前記検索条件を満たす選択されていないドキュメントが存在する間、前記カレントドキュメントを選択するステップ以降の処理を繰り返す
ことを特徴とする方法。
【請求項２】
請求項１に記載の方法において、親フォルダの識別子を取得する前記ステップは、ドキュメント識別子から親ドキュメント識別子へのマッピング・テーブルから前記親フォルダの前記識別子を検索するステップを備えることを特徴とする方法。
【請求項３】
請求項２に記載の方法において、前記親フォルダの前記識別子を検索する前記ステップは、前記カレントドキュメントの前記ドキュメント識別子をキーとして使用して、前記ドキュメント識別子から親ドキュメント識別子へのマッピング・テーブルから前記親フォルダの前記識別子を取得することを特徴とする方法。
【請求項４】
請求項１に記載の方法において、前記データ構造はハッシュ・テーブルであることを特徴とする方法。
【請求項５】
請求項１に記載の方法において、前記第２応答ステップは、前記カレントドキュメントのパス内で前記親フォルダの階層的に上位にあるフォルダの識別子を取得するステップと、前記階層的に上位にあるフォルダの前記識別子をキーとして、インデックス情報である前記データ構造にアクセスするステップと、前記データ構造への前記アクセスによって、前記階層的に上位にあるフォルダの識別子に対応するエントリが前記データ構造にあると判断される場合、前記パス内のカレントドキュメントの子供についての前記フラグを、前記階層的に上位にあるフォルダの識別子でインデックスされたフラグの値で満たすステップとを含むことを特徴とする方法。
【請求項６】
請求項１に記載の方法において、前記照会は少なくとも１つのフォルダを指定しており、前記方法は、前記少なくとも１つのフォルダの識別子でインデックスされたフラグを前記データ構造に初期値として入れておくステップをさらに備え、前記フラグは前記少なくとも１つのフォルダがスコープ内にあることを示す値をもつことを特徴とする方法。
【請求項７】
請求項１に記載の方法において、前記階層編成システムはファイル・システムであることを特徴とする方法。
【請求項８】
ドキュメントおよびフォルダの階層編成システムにおいて、指定された検索条件に基づいて検索された１つまたは２つ以上のドキュメントの中から、指定されたスコープであって、前記スコープはディレクトリ構造を有するフォルダの集まりである、そのようなスコープのセットに合致する少なくとも１つのドキュメントでもって照会に応答するコンピュータであって、該コンピュータは、前記照会に応答して、
指定された検索条件に基づいて検索された１つまたは２つ以上のドキュメントの中の一つのドキュメントをカレントドキュメントとして選択する手段と、
前記カレントドキュメントの識別子を取得する手段と、
前記カレントドキュメントの親フォルダの識別子を取得する手段と、
前記親フォルダの識別子をキーとして用いてインデックス情報であるデータ構造にアクセスする手段であって、該データ構造は前記親フォルダの前記識別子と該識別子でインデックスされたフラグとからなるエントリを含む、そのようなデータ構造にアクセスする手段と、
前記データ構造への前記アクセスによって、前記データ構造から応答を受け取る手段であって、該応答は前記カレントドキュメントが前記スコープ内にあるかどうかを示す値をもつフラグ、または前記親フォルダの識別子が前記データ構造内にないとの通知を含む、そのような応答を受け取る手段と、
前記フラグを受け取ったとき、その値が前記カレントドキュメントが前記スコープ内にあることを示すかどうかを判断し、前記カレントドキュメントが前記スコープ内にあれば、前記カレントドキュメントの情報を前記照合の応答として返す手段と、
前記親フォルダの識別子が前記データ構造内にないとの通知を受け取ったとき、前記親フォルダを、指定された前記スコープと比較して前記カレントドキュメントが前記スコープ内にあるかどうかを判断し、該判断結果に基づいて前記親フォルダの識別子と該識別子でインデックスされたフラグであって前記カレントドキュメントがスコープ内にあるかどうかを示す値をもつフラグとからなるエントリを前記データ構造に追加し、前記カレントドキュメントが前記スコープ内にあれば、前記カレントドキュメントの情報を結果セットに追加する手段とを備え、
前記カレントドキュメントの情報を結果セットに追加する手段の処理後は、前記検索条件を満たす選択されていないドキュメントが存在する間、前記カレントドキュメントを選択する手段による処理以降の処理を繰り返す
ことを特徴とするコンピュータ。
【請求項９】
請求項８に記載のコンピュータにおいて、親フォルダの識別子を取得する前記手段は、ドキュメント識別子から親ドキュメント識別子へのマッピング・テーブルから前記親フォルダの前記識別子を検索する手段を備えることを特徴とするコンピュータ。
【請求項１０】
請求項８に記載のコンピュータにおいて、前記データ構造はハッシュ・テーブルを備えることを特徴とするコンピュータ。
【請求項１１】
請求項８に記載のコンピュータにおいて、前記階層編成システムはファイル・システムであることを特徴とするコンピュータ。
【請求項１２】
請求項８に記載のコンピュータにおいて、前記第２応答手段は、前記カレントドキュメントのパス内で前記第親フォルダの階層的に上位にあるフォルダの識別子を取得する手段と、前記階層的に上位にあるフォルダの前記識別子をキーとして、インデックス情報である前記データ構造にアクセスする手段と、前記データ構造への前記アクセスによって、前記階層的に上位にあるフォルダの識別子に対応するエントリが前記データ構造にあると判断される場合、前記パス内のカレントドキュメントの子供についての前記フラグを、前記階層的に上位にあるフォルダの識別子でインデックスされたフラグの値で満たす手段とを含むことを特徴とするコンピュータ。
【発明の詳細な説明】
発明の分野
本発明は一般的にはコンピュータ・サーチエンジン（検索エンジンともいう）に関し、より具体的には、ユーザの照会（query）に応答して、サーチエンジンを使用し、ドキュメント情報を検索する改良方法およびメカニズムに関する。
発明の背景
Microsoft社のオブジェクト・ファイル・システム（OFS:Object File System）やMicrosoft社のWindows NTTMファイル・システム（NTFS:NT File System）といった、先進的コンピュータ・ファイル・システムにおける階層編成データは、サーチエンジン（照会エンジン）と関連づけられている場合がある。この照会エンジンを使用すると、ユーザはデータおよび／またはファイル・システムに問い合わせ（照会）を行い、ユーザの照会で指定したものに合致するドキュメント（つまり、ファイルまたはオブジェクト）を見つけることができる。例えば、上記ファイル・システムはこのシステムによってストアされたドキュメントのコンテンツ（内容）やプロパティのインデックスを別々に作成し、ドキュメント内のデータがデータベース・データのような構造になっていなくても、照会エンジンがそのような照会に即時に応答できるようにしている。照会に応答するために、照会エンジンはインデックスにアクセスし、見つけたドキュメントに関する情報を結果セットに入れて戻している。他の階層編成データを取り扱うサーチエンジンは他にもあるが、その扱い方は類似している。
照会で指定するものの１つに制限（restriction）があるが、これはマッチング（合致する）ドキュメントが所有する基準（コンテンツおよび／またはプロパティ）の集まりである。また、照会で指定するものの代表的なものとしては、調べようとするフォルダまたはディレクトリの集まりであるスコープ（scope：有効範囲）と、結果セットに入って戻される各マッチング・ドキュメントごとにどのプロパティを戻すべきかを特定している戻りセット（return set)がある。例えば、照会はマッチング・ドキュメントが「コンピュータ・ソフトウェア（computer software）」というテキストを含んでいること、調べるべきスコープがc:＼folderlであること、およびマッチング・ファイルのファイル名とファイル・サイズが戻りセットに入って戻されることを指定した制限で構成することができる。スコープを浅い（shallow）と指定すると、指定されたフォルダに入っているドキュメントだけが戻され、深い（deep）と指定すると、指定されたフォルダと、そのサブフォルダ（もしあれば）とに入っているマッチング・ドキュメントが戻される。
インデックスは逆テキスト・インデックス（inverted text index）である。つまり、テキストワード別に編成され、それがキーとなっており、フォルダとドキュメント間の階層関係別に編成され、それがキーとなっていない。その結果、ある照会が処理されるとき、サーチエンジンはインデックスをサーチし、スコープとは関係なく、指定された制限に合致するドキュメントを取得する。スコープ・テスト（scope test）を行うときは、サーチエンジンはドキュメントの検索時にドキュメントの各々について、プレフィックス・マッチング（prefix matching）と呼ばれるストリング（文字列）比較を行い、そのようなファイルがあれば、そのどれが指定のスコープ内にあるかを判断する。見つかったドキュメントで、照会で指定されたものに一致するプレフィックスをもつものは「スコープ内（in scope）」にあると言われる。スコープ内にある、これらのマッチング・ファイルのプロパティはそのあと結果セットに入って戻される。
しかるに、ストリング比較、従って、プレフィックス・マッチングは相対的に低速で、高価なプロセスである。プレフィックス・マッチングは長いファイル名と短いファイル名の両方を使用し、ファイル名の大文字と小文字を区別し、１つのストリングが一意的であるが、同じ意味の複数の表現をもつことができる国際的Unicode（ユニコード）ファイル名を使用しているために、さらに複雑化している。さらに、見つかった各ドキュメントごとに、ドキュメントのフォルダのフルパス（full path）がメモリに作成され、そこではスペースは、パスが任意で未知のストリング・サイズであり、一定の上限がないためにヒープから割り振られている。最後に、２つ以上のフォルダが特定のスコープ・セットで指定されることがあるために、また見つかったドキュメントがばらばらになっているために、プレフィックス・マッチングは指定されたフォルダごとに、合致するものが見つかるか、あるいはドキュメントがスコープ内にないと判断されるまで、一度に１ドキュメントずつ行う必要がある。このことは、あるセット内のすべての指定フォルダが、最終的にスコープ内にないと判断されたドキュメントを探すためにプレフィックス・マッチングが行われることを意味し、平均的には、スコープ内にあるドキュメントを探すために指定フォルダの半分がテストされてから、合致するものが見つかっている。
以上を要約すると、上述した照会解決手法は、取り扱うファイルの数がわずかであるときは有効であるが、プレフィックス・マッチング・プロセスは、相対的に多数のドキュメントがスコープ・テストされるときは大量のリソースを消費する。これと同時に、階層編成データのＯＦＳ、ＮＴＦＳおよびその他のシステムは、数十万の結果を含んでいる大きな結果セットをサポートする設計になっている。ＯＦＳとＮＴＦＳおよび類似のシステムはネットワーク構成のクライアント・サーバ環境で使用されるのが代表的であるために、照会が上記のように大きくなり、スコープ・テストに費用がかかっているのが普通である。
発明の目的と概要
従って、本発明の一般的目的はサーチエンジンの照会を大幅に改善する方法およびメカニズムを提供することである。
上記目的に関連する目的は、非常に多数のドキュメントを取り扱う照会に対するサーチエンジンの照会プロセスを大幅に改善することである。
本発明の別の目的は、照会を解決するために要する時間量を大幅に低減する、上記種類に属する方法およびメカニズムを提供することである。
上記目的に関連する目的は、上記の特徴を具備し、基準に合致したドキュメントをスコープ・テストするために要する時間量を大幅に低減する方法およびメカニズムを提供することである。
本発明のさらに別の目的は、既存のサーチエンジンおよび階層編成データと共に機能し、拡張可能である、上記種類に属する方法およびメカニズムを提供することである。
以上を要約して説明すると、本発明はファイル・システムにおけるドキュメントやフォルダなどの、階層編成されたデータ構造の照会に応答し、ドキュメントが指定された基準に基づいて検索されるとき、指定されたスコープに合致するドキュメントが戻されるようにした方法およびメカニズムを提供している。この目的のために、各検索ドキュメント（retrieved document）はカレントドキュメント（current document）として選択され、ドキュメント識別子（document identifier）がそのために取得される。カレントドキュメントの親フォルダの識別子が取得される。親フォルダのＩＤは、ある種のファイル・システムに存在する、ドキュメントＩＤから親ＩＤへのマッピング・テーブルにアクセスすることによってドキュメントのＩＤから判断することができる。このようなマッピング・テーブルはサーチエンジンによって生成することも可能である。
親識別子が取得されると、その識別子は、ハッシュ・テーブル（hash table）のように、キー（親フォルダのＩＤ）でインデックスされたフラグを含んでいるデータ構造へのキーとして使用される。フラグはカレントドキュメントを含めて、その親フォルダの下にあるドキュメントがスコープ内にあるか、スコープ内にないかを示す値をもっている。カレントドキュメントがスコープ内にあることをフラグが示していれば、そのドキュメントは、一般的にはファイル名としてそのファイルの他のプロパティと一緒に結果セットに入って戻される。カレントドキュメントがスコープ内にないことをフラグが示していれば、そのドキュメントは戻されない。
カレントドキュメントの親フォルダに対応するエントリがデータ構造になかったときは、プレフィックス・マッチングまたはなんらかの代替テストが親フォルダについて行われ、それがスコープ内にあるかどうかが判断される。そのあと、親フォルダのスコープ情報が親フォルダ識別子でインデックスされたフラグとしてデータ構造に追加され、その同じフォルダを共有する以後の検索ドキュメントはプレフィックス・マッチングを受けないで済むようにする。この方法およびメカニズムは各ドキュメントが検索されるつど繰り返され、すべてのドキュメントが上記のようにスコープ・テストされるまで続けられる。
本発明のその他の目的および利点は、添付図面を参照して以下に詳述する説明から理解される通りである。
【図面の簡単な説明】
図１は、本発明を組み込むことができるコンピュータ・ネットワークを示すブロック図である。
図２は、サーバ・コンピュータとクライアント・コンピュータを含むコンピュータ・システム内のハードウェア・コンポーネントを示すブロック図である。
図３は、サーバ・コンピュータ内のハードウェア・コンポーネントとソフトウェア・コンポーネントを示すブロック図である。
図４は、ファイル・システムまたはサーチエンジンによって維持されるインデックスの一般構造を示す概略図である。
図５は、照会の中で記述された特定の制限に合致するファイルの代表的なリスト例を示す図である。
図６は、フォルダおよびドキュメントの階層ディレクトリ構造の例を示す概略図である。
図７は、ファイル・システムまたは類似システムにおけるドキュメントおよびフォルダの識別子間の階層関係のマッピングを示す図である。
図８は、改良スコープ・テストを容易化するために本発明に従って構築されたキャッシュ・テーブルの例を示すブロック図である。
図９乃至図１１は、本発明に従って照会を解決するためにスコープ・テストを行うときとられる一般的ステップを示すフロー図である。
図１２は、結果セットに入って戻されるファイル情報の代表的なリスト例を示す図である。
図１３は、本発明に従って照会を解決するためにスコープ・テストを行うときとられる代替ステップを示すフロー図である。
図１４は、フォルダおよびドキュメントの代替階層ディレクトリ構造の例を示す概略図である。
図１５は、改良スコープ・テストを容易化するために本発明に従って構築された代替キャッシュ・テーブルの例を示すブロック図である。
好適実施例の詳細な説明
以下、添付図面を参照して説明する。まず、図１を参照して説明すると、図１は本発明を組み込むことができるコンピュータ・ネットワーキング・システム全体を２０で示したものである。図示のネットワークはサーバ２２と、公知のようにサーバに接続された、コンピュータをベースとする複数のリソース（例えば、パーソナル・コンピュータなどのクライアント・ワークステーション）２４1−２４nとを含んでいる。もちろん、以上から理解されるように、本発明はどの特定のネットワーキング環境にも限定されない。つまり、いやしくもネットワークに限定されるのではなく、スタンドアロン型パーソナル・コンピュータなどに組み込むことも可能である。事実、サーバ２０の代表例として、相対的にハイパワーのパーソナル・コンピュータがあり、本発明は、どのクライアントからも独立させてサーバ２２側のオペレーティング・システム、サーチエンジンおよび／またはファイル・システムに置いておくことが可能である。従って、ここに例示されているサーバ２２は独自のＣ：ドライブ２６をもつほかに、Ｄ：ドライブ２８やＥ：ドライブ３０などの、クライアントがアクセス可能なドライブを物理的にもっているか、あるいはそこに密に接続されている。
コンピュータ・ベースのリソース２４1−２４nは相互接続メカニズム３２上にネットワーキング方式で相互接続されているが、この相互接続メカニズムはローカルエリアネットワーク、広域ネットワークまたは他の相互接続メカニズムにすることができる。相互接続メカニズム３２によると、リソース２４1−２４nはサーバ２２のドライブＤ：とＥ：（２８、３０）に論理的にアクセスすることができる。物理的には、相互接続メカニズム３２はデバイスの各々内のハードウェア・インタフェースに関する選定標準に準拠していれば、どの周知データ伝送媒体でも含むことが可能であり、例としては、同軸ケーブル、電話ケーブル、光ファイバ・ケーブルなどがある。ARCnet（登録商標）、Ethernet（登録商標）およびToken Ring（登録商標）を含む、かかる標準およびその関連ハードウェア・インタフェースはこの分野では周知であるので、ここで詳しく説明することは省略する。ここでは、多くの商用化インタフェース・ボードはネットワーキング方式でコンピュータ・ベースのリソースを接続するために利用できる、とだけ述べておく。
図２に分かりやすく示すように、サーバは、オペレーティング・システム３８がそこにロードされているメモリ３６に接続されたプロセッサ３４を搭載している。オペレーティング・システム３８は、Microsoft社のWindows NTTMオペレーティング・システムなどの分散オペレーティング・システムであることが好ましい。本発明によれば、サーバ２２は、階層的に編成されたデータ（階層編成データという）、つまり、オペレーティング・システム３８と関連づけられているか、またはそこに組み込まれているファイル・システム４０内で維持されているような、ドキュメントの構造をそこにもっている。好ましいファイル・システム４０は、ドキュメント（つまり、ファイル、オブジェクトなど）がフォルダ（つまり、ディレクトリ、カタログなど）の下に編成できるようなタイプであり、そこでは各ドキュメントはフォルダおよびサブフォルダの階層構成の下に置くことができるが、直属親フォルダは１つだけになっている。サーバ２２は、サーバ２２を１つまたは２つ以上のネットワーク内デバイスに、キーボードおよび／またはマウスなどの１つまたは２つ以上の入力デバイス４４に、およびモニタおよび／またはスピーカなどの１つまたは２つ以上の出力デバイス４６に接続するための入出力（Ｉ／Ｏ）回路４２も備えている。サーバ２２は図１を参照して上述したＣ：ドライブ２６、Ｄ：ドライブ２８およびＥ：ドライブ３０などの不揮発性ストレージ４８も備えている。
図２にも示すように、ここでクライアント・ワークステーション２４1として示されているリソースの１つまたは２つ以上は、パーソナル・コンピュータなどにすることができるが、オペレーティング・システム５２がそこにロードされているメモリ５０を搭載している。なお、オペレーティング・システムは、同様にサーバ２２側に常駐するものと同タイプの分散オペレーティング・システムにすることができる。パーソナル・コンピュータ・ベースのクライアント・ワークステーションでは普通であるように、クライアント２４1はプロセッサ５３を搭載し、このプロセッサはメモリ５０に接続されると共に、クライアント２４1をサーバ２２に、キーボードおよび／またはマウスなどの１つまたは２つ以上の入力デバイス５６に、およびモニタおよび／またはスピーカなどの１つまたは２つ以上の出力デバイス５８に接続するための入出力（Ｉ／Ｏ）回路５４に接続されている。クライアント２４1は独自のローカルＣ：ドライブ６２1（図１）などの不揮発性ストレージ６０（図２）も備えている。
図１と図３に分かりやすく示すように、サーバ２２は照会エンジン６４を備えており、この照会エンジンを使用すると、ユーザはファイル・システム４０（または他の階層編成データ）に照会し、ユーザ入力の照会で指定したものに合致するドキュメントを見つけることができる。照会エンジン６４はWindows Explorer（エクスプローラ）または他の類似インタフェースなどの、プログラムを通してユーザとのインタフェースとなることができる。図１に詳しく示すように、クライアント・デバイス２４1−２４nは各々が独自の階層編成データ（例えば、独自のファイル・システム）またはサーバ２２側の階層編成データ（例えば、ファイル・システム４０）に照会するための類似の照会エンジン６６1−６６nを備えている。もちろん、照会エンジンを複製するのではなく、クライアント・デバイス２４1−２４nに適当なインタフェースを装備させると、そのインタフェースを通してサーバ２２の照会エンジン６４を利用することも可能である。
図３に詳細を示すように、照会エンジン６４は２つのコンポーネントを含んでいる。制限に合致するドキュメントを見つけるための基準マッチング・コンポーネントと、制限に合致するドキュメントの範囲を特定のスコープ内にあるドキュメントに狭めるスコープ・テスト・コンポーネントである。照会エンジン６４はファイル・システム４０と関連づけられ、ドライブ２６、２８および３０の各々のインデックス７２、７４および７６に影響を及ぼす。同図に示すように、インデックスはある特定ボリュームに対応づけられているが、インデックスは複数のボリュームにスパンすることも可能である。それにもかかわらず、以下で説明するように、本発明は、検索ドキュメントの情報がインデックスにも保存されているかどうかに関係なく、どの検索ドキュメントでも扱うことが可能である。
好ましいインデックス７２−７６（図３）は図４に示す編成になっているのが一般で、スペースを節約するためにビット圧縮されたビットのストリームとしてストアされている。好ましいビット圧縮は本発明の被承継人に承継された米国特許出願第07/986,754号に記載されている。図４に示すように、Ｄ：ドライブ・インデックス７４のような、各インデックスはテキストワード（ＫＥＹ1−ＫＥＹn）をキーとする逆テキスト・インデックスであり、各キー（ワード）はドキュメントのコンテンツ内のドキュメント・プロパティ値またはテキストのどちらかになっている。ドキュメント・プロパティとしては、ファイル・サイズ、作成者、作成日、修正日などのアイテム（項目）がある。
各キーの下位に、識別子、つまり、ＩＤのリストがあり、その各々は特定ボリューム上のドキュメントを整数で一意的に識別している。各ＩＤの下位には、オカレンス（occurrence）、つまり、オフセット・デルタ（offset delta）のリストがあり、これはそのキーがどのドキュメント内のどこに現れたかを示している。従って、図４に示すように、各キーはその後に１つまたは２つ以上のドキュメントＩＤが続き、各ＩＤはその後にそのＩＤで示されたドキュメント内のそのキーの１つまたは２つ以上のオカレンスが続いている。類似の逆テキスト・インデックス記憶手法はGerard Salton著「自動テキスト処理−コンピュータによる情報の変換分析と検索（Automatic Text Processing-The Transformation Analysis and Retrieval of Information By Computer）」、Addison-Wesley（1989）に説明されている。
いずれにしても、基準マッチング・コンポーネント６８のオペレーションは周知であるので、ここで詳しく説明することは省略する。ここでは、照会エンジンの基準マッチング・コンポーネント６８は該当のインデックスなどにアクセスして、ユーザの制限セットに記述された基準を具備するすべてのドキュメントを見つけている、と述べるだけにとどめておく。基準マッチング・コンポーネント６８は各ドキュメントの識別子（ドキュメントＩＤまたはＤｏｃ  ＩＤ）と一緒にドキュメント名を戻し、戻りセットの中で要求されていれば、各ドキュメントの他のプロパティへの直接または間接参照なども戻してくる。図５はこれらのドキュメントのリスト７８を示しているが、図には単純化のために人間が読める形式で示され、他のドキュメント・プロパティは示していない。
上記から理解されるように、基準マッチング・コンポーネント６８は、指定されたどのスコープにも関係なくインデックス７２−７６について操作する（一般的にスコープに示された１つまたは複数のドライブを調べてインデックスのどれをサーチすべきかを判断するのでない）。従って、図５はスコープ内のファイルだけではなく、該当のＤ：ドライブ・インデックスに置かれているすべてのファイルのリスト７８を示している。例えば、制限が「そのファイル名に‘DOC*’があるすべてのドキュメントを見つける」（ただし、“*”はワイルドカード・サーチ用語である）または「そのコンテンツに‘budget’という用語があるすべてのドキュメントを見つける」ことを指定していれば、照会エンジンはＤ：ドライブ・インデックス７４をサーチして（スコープがＤ：＼．．．であったと想定する）見つかった、かかるすべてのドキュメントのリスト７８を取得する。ここで注意すべきことは、検索ドキュメントのリスト７８が、ある任意の瞬時にストレージに物理的に存在するとは限らないことである。これは、好ましくは、各ドキュメントはその検索時にスコープ・テストされ、結果セットに追加されるか、あるいは破棄されるからである。各ドキュメントをその検索時にスコープ・テストすると、ユーザは、すべてのドキュメントが完全に検索されてから、スコープ・テストされるのを待たなくても、なんらかのサーチ結果（もしあれば）を得ることができるのが普通である。しかし、最初に２つ以上のドキュメントを得てから、あるいは最初に完全リストを得てから、スコープ・テストを行うようにすることも可能である。どの場合も、図５のリストは指定された基準に一致し、スコープ内にある場合もあれば、スコープ内にない場合もあるファイルの集まりを示す概念図である。
以下では、本発明によるスコープ・テスト・コンポーネント７０のオペレーションについて詳しく説明する。一般的に、本発明では、見つかった各ドキュメントをプレフィックス・マッチングするのではなく、本発明のスコープ・テスト・コンポーネント７０は、フォルダがほとんど常になんらかの階層構造に編成されているという事実、および各フォルダがその下に論理的に配置された複数のドキュメントをもっているのが代表的であるという事実を利用している。従って、本発明の一側面によれば、以下で詳しく説明するように、あるドキュメントのプレフィックス・マッチングの結果を使用することによって、同じ直属親フォルダの下にストアされている他のドキュメントのスコープ情報は、これらの他のドキュメントで時間のかかるプレフィックス・マッチング・アルゴリズムを実行しなくても取得できるようになっている。
各フォルダは一意的な識別子に対応しており、この識別子は以前にファイル・システムによって割り当てられ、照会エンジンによって影響を及ぼされたものであるか、あるいはサーチエンジンによって一意的に割り当てられたもののどちらかである。例えば、ＮＴＦＳはあるボリューム上の各フォルダとドキュメントに一意的な識別子を割り当てているが、この識別子はドキュメントＩＤと呼ばれることがある（フォルダがドキュメントでない場合でもそう呼ばれている）。なお、サーチエンジン６４が複数のボリュームにスパンするサーチでドキュメントＩＤを使用する場合、サーチエンジン６４は複数ボリューム間の一意性（固有性）を保つために必要に応じてドキュメントＩＤだけを変更する。
テーブル、つまり、キャッシュ８６は判明したフォルダのスコープに関する情報をストアするために使用される。最初は、キャッシュ８６は空であり、親フォルダのスコープに関する情報が分かるに伴って蓄積されていく。もっと具体的に説明すると、キャッシュ８６はある親フォルダがスコープ内にあるか、スコープ内にないかを示す“Inscope”フラグを各親フォルダごとにストアするために使用される。キャッシュ８６は、好ましくは、メモリ３６（図３）内に配列されたハッシュ・テーブルの構造になっている。もちろん、キャッシュ８６が十分に大きくなった場合や、以下で説明するように特定のキャッシュの持続性が望ましい場合は、キャッシュの一部または全部を不揮発性ストレージ（図３）に書き出すことができる。周知のように、T.Cormen、C.LeisersonおよびR.Rivest共著「アルゴリズムの紹介（Introduction to Algorithms）」MIT Press,1990の第１２章に記載されているように、ハッシュ・テーブルはデータ構造配列になっており、これは実際にストアされるキーの数に比例するサイズになっている。ハッシュ・テーブルはサーチし、そこに追加し、そこから削除することができ、高速平均速度で動作する。もちろん、他のデータ構造をキャッシュ８６として使用することも可能である。
次に、図９乃至図１１を参照して本発明について説明する。照会エンジン６４は、まず、ユーザから照会の指定を受信すると開始する。例えば、スコープ・セットは、D:＼FOLDER1＼FOLDER2,D:＼FOLDER87と指定することができ、サーチがどちらのフォルダの場合も深いこと、つまり、D:＼FOLDER1＼FOLDER2,D:＼FOLDER87のサブフォルダも、サーチの対象であることを示すことができる。ここで注意すべきことは、ＮＴＦＳの分散ファイル・システムでは、スコープを可能な限りのドライバとフォルダすべてにわたってグローバルにできることである。
上記に対する応答として、照会エンジン６４は、まず、いくつかの判明したフォルダに関するスコープ情報をキャッシュ８６に事前に入れておく。つまり、初期値として入れておく（priming）。この例では、フォルダD:＼FOLDER1＼FOLDER2およびD:＼FOLDER87のすぐ下にある検索ドキュメントは、D:＼FOLDER1＼FOLDER2およびD:＼FOLDER87のサブフォルダ情報がまだ分かっていなくても、スコープ内にあることが分かっている。なお、どの任意のフォルダ名からでも、そのドキュメントＩＤは、ファイル・システム４０から、または照会エンジンを通して即時に取得可能である。従って、図６に示すように、D:＼FOLDER1＼FOLDER2のドキュメントＩＤは８に等しく、D:＼FOLDER87のドキュメントＩＤは５０に等しくなっている。
キャッシュにこの判明情報を初期値として入れるために、ステップ１００で、照会解決プロセスは、最初の指定フォルダD:＼FOLDER1＼FOLDER2のドキュメントＩＤを取得するが、これは図６に示すように”８”に等しくなっている。ステップ１０２で、一意的ドキュメントＩＤである”８”がキャッシュ８６（図８）に追加され、Inscopeフラグは真（true）にセットされている。初期値を入れることは、指定フォルダのスコープ情報が初期値としてキャッシュに入るまで、ステップ１０４の判断に従って続けられる。従って、ステップ１０６でドキュメントＩＤの５０がD:＼FOLDER87について得られ、ステップ１０２で、キャッシュ８６は５０をキーとして使用し、Inscopeフラグを真にして初期値が入力される（図８）。
キャッシュに初期値が入力されると、ステップ１０８で、照会エンジンはマッチング・ドキュメントを検索する（ユーザ指定の基準に基づいて）。この例では、図５のリスト７８に示すように、最初の検索ドキュメントはD:＼FOLDER1＼FOLDER3＼DOC4であり、ドキュメントＩＤは２に等しくなっている。ここで注意すべきことは、図４に示すように、各ドキュメントのドキュメントＩＤはインデックス７４に入れられ、図５に示すように戻されることである。
従って、各ドキュメントのスコープ・テストは図１０のステップ２００から開始され、見つけるべきドキュメントが残っていないと、ステップ１１０（図９）で判断されるまで各検索ドキュメントで続けられる。もちろん、公知のように、ステップ２００に先立って、リスト７８内の各検索ドキュメントのパスを最初にケース（大小文字）正規化（case-normalized）とロケール正規化（locale-normalized）して短いファイル名にしておくと、スコープ・テストが高速化される。さらに、いずれかのスコープが深いときは、照会解決プロセスはスコープ・セットにリストされたフォルダを最初に合体しておき、そのセットにも指定されている他のフォルダにネストされたサブフォルダである、フォルダが別々にサーチされないようにする。例えば、D:＼FOLDER1のスコープが深いと指定され、スコープ・セットがD:＼FOLDER1とD:＼FOLDER1＼FOLDER4の両方を指定していれば、D:＼FOLDER1＼FOLDER4の下にストアされたドキュメントもD:＼FOLDER1の深いサーチの対象となるので、スコープ・セットをD:＼FOLDER1に合体することができる。これは、D:＼FOLDER1＼FOLDER4が深いと指定されているか、浅いと指定されているかに関係なく有効である。
図７に示すように、および上述したように、各ボリューム、例えば、ドライブD:＼ごとに（または複数ボリュームにまたがって）、サーチエンジン６４および／またはファイル・システム４０は密にパックされたドキュメントＩＤから親ドキュメントＩＤへのマッピング配列８０、８２および８４を維持している。この例では、配列はマッピング・テーブル８２になっており、そこから任意のドキュメントの親フォルダのドキュメントＩＤは、そのドキュメントのドキュメントＩＤをそこへの直接アドレシング・インデックスとして使用して高速に得られるようになっている。従って、この例では、最初に見つかったドキュメントはD:＼FOLDER1＼FOLDER3＼DOC4であり、ドキュメントＩＤは２に等しくなっている（図５）。ドキュメントＩＤから親ドキュメントＩＤへのマッピング・テーブル８２（図７）のインデックスとして”２”を使用すると、直属親フォルダ（D:＼FOLDER1＼FOLDER3）のドキュメントＩＤ（”３”に等しい）はステップ２０２で得られる。なお、ＮＴＦＳなどのファイル・システムは上記マッピング・テーブル８２を各ボリュームごとに直接に維持しているが、マッピング・テーブルに保存されている、上記と同じマッピング情報は、ほとんどどの階層編成データまたはファイル・システムからでも直接または間接に取得することが可能である。事実、本発明は、どの特定のドキュメントから親へのマッピングにも限定されず、それとは逆に、どの既存または将来の階層編成データまたはファイル・システムにも拡張可能であり、ドキュメントの親などに関する情報をドキュメント情報から取得または推論することが可能である。
本発明によれば、３に等しいドキュメントＩＤが取得されると、ステップ２０４でキャッシュ８６は、親ドキュメントＩＤである３をキーとして使用してサーチされる。この例では、キャッシュ８６はこのサブフォルダ情報が初期値として入っていないので、キャッシュ・サーチ・プロセスはステップ２０４（図１０）でヌル（null）、−１または他のエラーコードなどの値を戻し、親フォルダ（キーは３に等しい）は対応するエントリをもっていないことを知らせる。従って、エントリがないので、ステップ２０６で照会解決プロセスはステップ２０８にブランチする。ステップ２０８で、スコープがチェックされ、深いと指定されたスコープがあるかどうかが判断されるが、これは、以下で詳しく説明するように、浅い照会と深い照会はこの点では異なる意味合いをもつためである。
この例では、少なくとも１つのスコープは深くなっているので、プロセスは図１１のステップ３００にブランチし、そこでプレフィックス・マッチング・アルゴリズムなどのテストが行われ、親フォルダ（D:＼FOLDER1＼FOLDER3）がスコープ内にあるかどうかが判断される。公知のように、プレフィックス・マッチングはフォルダのフルパス名を、特定のスコープ・セットに指定されたパス名の各々とストリング単位で突き合わせて比較する。図６に示すツリーから明らかであるように、各フォルダとドキュメントのドキュメントＩＤはフォルダまたはドキュメントの名前の下にかっこで囲んで示されているが、プレフィックス・マッチングはD:＼FOLDER1＼FOLDER3がD:＼FOLDER1＼FOLDER2の要求されたスコープ内にないと判断している。従って、ステップ３００で、D:＼FOLDER1＼FOLDER3のInscopeフラグに偽の値（ゼロが代表例）が割り当てられ、これはスコープ内にない（not-in-scope）ステータスを示しているので、プロセスはステップ３０２でステップ３０４にブランチする。ステップ３０４でテストが行われ、スコープ・セット内に深いと指定されたフォルダのすべてがプレフィックス・テストされたかどうかが判断される。この例では、D:＼FOLDER87も深いと指定されているので、ステップ３０６でD:＼FOLDER87が選択され、プロセスはステップ３００に戻りD:＼FOLDER1＼FOLDER3をD:＼FOLDER87と突き合わせるプレフィックス・マッチングが行われる。これらのフォルダは合致していないので、Inscopeフラグは偽のままであり、ステップ３０２で再びステップ３０４にブランチする。しかし、今回は、D:＼FOLDER87は最後に指定されたフォルダであるので、ステップ３０４でステップ３０８にブランチし、そこでキャッシュ（ハッシュ・テーブル）８６へのキーは親ドキュメントＩＤである３にセットされる。このあとに続くステップ３１０で、キャッシュ（ハッシュ・テーブル）８６に入るエントリが、Inscopeフラグ値（例えば、ゼロ）に関連するキー３のために作られる。なお、図８はキャッシュ８６を示しているが、当然に理解されるように、この時点では最初の３エントリ（つまり、初期値として入力された８、１および５０、１のエントリが最近の３、０のエントリと共に）が存在している。
照会プロセスは図１０に戻り、ステップ２１０へ進み、そこでInscopeフラグのテストが行われ、ドキュメントがスコープ内にあったかどうかが判断される。ドキュメントはスコープ内になかったので、プロセスは図９のステップ１０８に戻る（ステップ２１２にブランチしてドキュメントを結果セットに追加するのではなく）。
図９のステップ１０８はインデックスにアクセスし、基準に合致する次のドキュメントを取得する。別のドキュメントD:＼FOLDER1＼FOLDER3＼DOC5がリスト７８にあるので、ステップ１１０でプロセスは図１０のステップ２００に戻り、そこで１０に等しい、このドキュメントのドキュメントＩＤが取得される。
以前と同じように、ステップ２０２でマッピング・テーブル８２（図７）が参照され、１０のドキュメントのドキュメントＩＤをインデックスとして図７のマッピング・テーブルを使用して、ステップ２０２はＤＯＣ５の直属親フォルダD:＼FOLDER1＼FOLDER3のドキュメントＩＤとして”３”を戻す。しかし、今回はループを通るとき、ステップ２０４でキャッシュ８６をサーチすることにより、キー３のエントリがキャッシュ８６に存在することが判断され、そこからキャッシュ８６はそのInscopeフラグ値（ゼロに等しい）を戻す。従って、プロセスはステップ２１０にブランチし、そこでInscopeフラグがテストされ、偽であると判断されると、プロセスは図９のステップ１０８に戻ることになる。従って、以前のドキュメントＤＯＣ４と異なり、親フォルダ（D:＼FOLDER1＼FOLDER3）のスコープはキャッシュに置かれたInscopeフラグから分かっているので、ＤＯＣ５ではプレフィックス・マッチングは不要である。以上から理解されるように、時間のかかるプレフィックス・マッチング・アルゴリズムを２回以上実行しなくても、キャッシュ８６を使用すると、D:＼FOLDER1＼FOLDER3をその親フォルダ（ドキュメントＩＤが３である）としてもつ他のドキュメントのスコープが、スコープ内にないと即時に判断することができる。サーチを大きくすると、非常に多数のドキュメントがこの親フォルダを共有できるので、時間節約は何倍にもなる。
ステップ１０８で次のドキュメントD:＼FOLDER1＼FOLDER11＼MSOFFICE＼SHEET4.XLS（図５）が検索されるので、ステップ１１０でプロセスはステップ２００にブランチする。パス・ストリングを分析すると理解されるように、共通の親フォルダD:＼FOLDER1＼FOLDER11＼MSOFFICEをもつ次の３ドキュメントは指定されたスコープ内にない。上述したステップに続いて、本発明の一側面によれば、これらの３つの最初のもの（“＼SHEET4.XLS”）だけが図１１に示すようにプレフィックス・マッチングされる。以前と同じように、最初の親フォルダがプレフィックス・マッチングされると、そのキー（例えば、ドキュメントＩＤ、従ってD:＼FOLDER1＼FOLDER11＼MSOFFICEのキーは９０に等しい）はそのゼロのInscopeフラグと一緒にキャッシュ８６に置かれる。次の２ドキュメントについては、親フォルダ９０のエントリはキャッシュ８６にあるので、これらのドキュメントのプレフィックス・マッチングは不要になる。なお、プレフィックス・マッチングによると、キャッシュに深いフォルダを初期値として入れておくことは不要になる。
図５に示す例に戻って説明すると、次のドキュメントは”D:＼FOLDER1＼FOLDER2＼FOLDER4＼DOC1”であり、ステップ１０８で検索される。図５に示すように、このドキュメントはドキュメントＩＤが４になっている。図７のドキュメントＩＤから親ドキュメントＩＤへのマッピング・テーブルから、”５”に等しい直属親フォルダのドキュメントＩＤがステップ２０２で取得される。ステップ２０４で、ドキュメントＩＤである５はキャッシュ８６へのキーとして使用される。この時点では、キャッシュ８６にはキー５のエントリがないので、キャッシュからはエントリがないことを示す値が戻される。従って、ステップ２０６でプロセスはステップ２０８にブランチし、指定されたスコープが深いので、図１１のステップ３００に進む。
ステップ３００で、プレフィックス・マッチング・アルゴリズムが実行され、D:＼FOLDER1＼FOLDER2＼FOLDER4がスコープ内にあると判断する。その結果、ドキュメントＩＤが５であるInscopeフラグにInscopeステータスを示す真の値（１が代表的）が割り当てられる。ドキュメントはスコープ内にあるので、ステップ３０２はステップ３０８にブランチする。
本発明によれば、ステップ３０８で、キャッシュ（ハッシュ・テーブル）８６へのキーは親ドキュメントＩＤである５にセットされ、ステップ３１０でキャッシュ８６に入るエントリが、真のInscopeフラグ値（例えば、１）に関連するキー５のために作られる。この時点では、図８に示すキャッシュ８６には、５個のエントリが入っていることになる。
照会プロセスは図１０に戻り、ステップ２１０へ進み、そこでInscopeフラグが真であるかどうかを判定するテストが行われる。Inscopeフラグは真であるので、ステップ２１２でDOC1のプロパティが結果セット９０（図１２）に追加される。なお、この例では、このエントリの戻りセットに指定されたプロパティはドキュメント名、サイズおよび作成日になっている。もちろん、他のプロパティが指定されていれば、これらも戻されることになる（セキュリティ・テストのように、あるドキュメントの情報を戻さないとする他の理由がある場合は除く）。そのあと、プロセスは図９のステップ１０８に戻り、次のドキュメントがあればそれを検索する。
以上から理解されるように、プロセスは図５にリストされている他のドキュメントについても上述したように続け、図１２に示すように結果セットを満たしていく。なお、D:＼FOLDER1＼FOLDER2＼FOLDER4＼DOC2がテストされるときは、プレフィックス・マッチングは行われない。これはそのドキュメントＩＤが９であり（図５）、その親ドキュメントＩＤが５に等しくなっているためである（図７）。その結果、ステップ２０６でエントリがキャッシュ８６に見つかるので、プロセスはステップ２１０にブランチする。上述したように、Inscopeフラグはこの５のエントリでは真であるので、ステップ２１０はステップ２１２にブランチし、そこでDOC2のプロパティが結果セット９０（図１２）に追加される。従って、以上から明らかなように、あるドキュメントの親フォルダがプレフィックス・マッチングされたあと、キャッシュ８６は、プレフィックス・マッチング・アルゴリズムが最終的に親フォルダがスコープ内にあったと判断したか、スコープ内になかったと判断したかに関係なく、同じ親フォルダを共有する他のドキュメントについて以後のプレフィックス・マッチングを行わなくても済むことになる。
最後に、図９のステップ１０８−１１０で、マッチング・ドキュメントはすべて検索され、スコープ・テストされていることになる。この時点で、プロセスは終了する。
以下では、照会が浅いときの照会リターン・プロセスのオペレーションについて説明するが、そこでは前例がここでも使用されているが、スコープは浅いものと指定されている。スコープが浅いときは、指定された親フォルダのすぐ下にあるドキュメントだけがスコープ内にある。その結果、スコープ・セットに指定されたフォルダの１つのドキュメントＩＤに等しいドキュメントＩＤをもつ親フォルダにマッピングされたドキュメントだけがスコープ内にあることになる。例えば、図６に示す階層編成を使用すると、スコープが浅く、D:＼FOLDER1＼FOLDER2,D:＼FOLDER87と指定されていれば、８または５０のどちらかのドキュメントＩＤをもつ親フォルダに直接にマップされた検索ドキュメントだけがスコープ内にある。従って、図６に示すように、DOC3だけがスコープ内にある。ここで注意すべきことは、前述の深い照会とは異なり、DOC1とDOC2が浅い照会ではスコープ内にないのは、これらがFOLDER4の下にあり、従ってFOLDER2の下には間接的にあるだけであるためである。以下で説明するように、この例では、図９と図１０のフロー図に例示されているスコープ・テストは他のすべてのドキュメントを除去し、プレフィックス・マッチングを行わずにDOC3だけを結果セットに追加する。
図９のステップ１００−１０６から始まって、キャッシュ８６は以前と同じように初期値が入力され、基準はこの例でも同じであるので、ステップ１０８−１１０は最終的に図５のリスト７８に示すものと同じドキュメントを検索することになる。ステップ２００−２０６で、各ドキュメントのドキュメントＩＤは以前と同じように親ドキュメントＩＤを取得し、キャッシュ８６をサーチするために使用される。従って、最初のドキュメントはD:＼FOLDER1＼FOLDER3＼DOC4であり、これはドキュメントＩＤが２になっている（ステップ２００）。図２のドキュメントＩＤから親ドキュメントＩＤへのマッピング・テーブル８２から、ステップ２０２は３に等しいDOC4の親ドキュメントＩＤを戻す。３をキャッシュへのキーとして使用して、ステップ２０４は３がキャッシュに存在しないとの値または他のエラーコードを戻すので、ステップ２０６のキャッシュ・エントリ・テストはステップ２０８にブランチする。
しかし、前述の例とは異なり、ステップ２０８でスコープは浅いと判断されるので、プロセスはドキュメントをこれ以上テストする必要はない。これはどの浅いフォルダの場合も、初期値が以前にキャッシュ８６に真として入っていたためである。直属親フォルダのドキュメントＩＤは、事前に初期値として入力されたキャッシュになかったので、スコープ内にないことが分かっている。これは初期値入力により、直接にスコープ内にあるすべてのフォルダのＩＤが追加されていたためである。
従って、ステップ２０９は図９のステップ１０８に戻り、そこで次のドキュメントが検索され、同じようにテストされる。図１０のステップをたどっていくと理解されるように、リスト７８（図５）内のドキュメントのどれも、D:＼FOLDER1＼FOLDER2＼DOC3を除きスコープ内にない。D:＼FOLDER1＼FOLDER2＼DOC3が検索されるとき（ステップ１０８）、ステップ２０２で検索されたドキュメントＩＤは８に等しくなる。その時点で、ステップ２０４は値８のエントリをキャッシュ８６内に見つける。キャッシュ８６内のすべての浅いエントリは初期値が真として入っているので、DOC3については、ステップ２１０はステップ２１２にブランチし、そこでDOC3のプロパティが結果テーブルに追加される。以上から理解されるように、本発明によれば、キャッシュに初期値を入れることにより、すべてのスコープが浅いと指定されている照会では、プレフィックス・マッチングを行う必要がまったくない。
代替実施例では、スコープが深いと指定されているとき、スコープをテストするためにプレフィックス・マッチングを行うのではなく、プロセスは図１３のステップ４００へ進み、そこでドキュメントのフォルダのパスがフォルダ・ドキュメントＩＤのセットに変換され、スコープを判断するために分析される。例えば、D:＼FOLDER1＼FOLDER3はドキュメントＩＤ3,1および0（ルート）のセットに対応している。さらに、この代替実施例では、ある種の情報はドキュメントの祖父フォルダまたは他の上位レベルの親フォルダから取得し、あるいは推論することができる。具体的には、あるドキュメントの直属親フォルダのエントリがキャッシュ８６に見つからなかったが、上位レベルの親が見つかり、スコープ内にあって深ければ、スコープ内にある上位親フォルダの下位にある、そのドキュメントおよびすべての判明ドキュメントもスコープ内にある。もちろん、上位レベルの親がキャッシュ８６に入っているが、スコープ内になければ、下位レベルのフォルダは、テストがその下位レベルのフォルダで行われない限り、しかもテストが行われるまでは、まだスコープ内にあるかどうかは分からない。
同様に、あるドキュメントがスコープ内にないと判断されたときは、そのドキュメントの上にある上位レベルのフォルダのどれもが、スコープ内になく、深くないと結論することができる。しかし、ドキュメントがスコープ内にあれば、ドキュメントの祖父フォルダ（および／またはその上のもの）が指定されたスコープ内にあることも、スコープ外にあることもあるので、上位レベルの親に関する有用な情報は分からない。
図１３はドキュメントのパスを使用してスコープを判断し、キャッシュを高速に満たす方法を示している。この代替実施例では、図１１を図１３で置き換えることができる。この例では、その目的上、図１４はＥ：ドライブ３０にストアされたフォルダとドキュメントの階層を示し、そこでは各フォルダとドキュメントのドキュメントＩＤはフォルダまたはドキュメントの名前の下にかっこで囲んで示されている。さらに、次の例では、改良型キャッシュ９８（以下で説明するように、浅いスコープを示すフラグを含んでいる）が図１５に示されている。次の例では、基準マッチングからはDOC A,DOC B,DOC G,DOC H,DOC M,DOC KおよびDOC Lがこの順序で戻されることを想定している。さらに、照会は浅いと指定されたパスE:＼F21＼F22または深いと指定されたパス“E:＼F1＼F4”または“E:＼F19”内のマッチング・ドキュメントを探し出す。
従って、図１５に示すように、キャッシュ９８は最初に22,1,1;4,1,0;および19,1,0が事前に初期値として入れられ（図９のステップ１００−１０６）、そこでは３エントリの各々の中の最後の値は浅いスコープ（１）または深いスコープ（０）を示すフラグになっている。ここで注意すべきことは、InscopeとShallowフラグは１バイトの異なるビットにできることである。図１５には４エントリ以上が示されているが、当然に理解されるように、この時点では最初の３エントリだけがキャッシュ８６に存在している。
従って、図９のステップ１０８はDOC Aを検索するが、これは、ステップ２００（図１０）でドキュメントＩＤが１１（図１４）であると判断されたものである。ドキュメントＩＤから親ドキュメントＩＤへのマッピング・テーブルなどを使用して、ステップ２０２はDOC Bの直属親フォルダ・ドキュメントＩＤが６（図１４のフォルダＦ６を表す）であると判断する。キャッシュ９８がステップ２０４でサーチされるが、６のエントリがないので、プロセスはステップ２０８にブランチし、そこで少なくとも１つの指定スコープが深いと判断される。この実施例では、プロセスは次に図１３（図１１ではなく）のステップ４００へ進む。
ステップ４００はDOC 11のパス、つまり、6,3,1,0内のすべてのフォルダのドキュメントＩＤを、該当のドキュメントＩＤから親ドキュメントＩＤへのマッピング・テーブルなどを使用して取得する。ステップ４００は、ドキュメントＩＤが６であるフォルダＦ６はキーとして使用されたが失敗していたので、カレントドキュメントＩＤをパス内の次に上のもの、つまり、親フォルダのドキュメントＩＤである３にセットする。次のステップであるステップ４０２は、カレントドキュメントＩＤを３としてキャッシュ９８をサーチする。３はキャッシュ９８にないので、ステップ４０４はステップ４０６にブランチし、そこでテストが行われ、カレントドキュメントＩＤがルート・ディレクトリのＩＤであるかどうかが判断され、そうであれば、親はこれ以上存在しないことになる。この例では、他の親が存在するので、プロセスはステップ４０８にブランチし、そこでカレントドキュメントＩＤは（親フォルダＦ１の）親ドキュメントＩＤである１にセットされる。次に、キャッシュ９８は新ドキュメントＩＤを１としてサーチされる。
図１４からと、図１３のステップ４０２−４０８から理解されるように、キャッシュ９８にはこの特定パスのエントリがないので、ルート・ディレクトリがステップ４０６で見つけられる。この時点で、パス全体がスコープ内にないことが分かっているのは、キャッシュ９８にフォルダのドキュメントＩＤと真のInscopeフラグが初期値として入っていたためである。従って、ステップ４１０は、それぞれドキュメントＩＤのキー６、２、１および０に対応するフォルダＦ６、Ｆ２、Ｆ１およびルートのInscopeフラグを偽（ゼロ）にしてキャッシュ９８に入れることになる。プロセスは図１０のステップ２１０に戻り、そこで偽のInscopeフラグは、プロセスを図９のステップ１０８に戻し、次のドキュメントを検索させる。
検索される次のドキュメントは図１４に示すようにDOC Bであり、ドキュメントＩＤは１２（図１０のステップ２００）に、親ドキュメントＩＤは４（ステップ２０２）になっている。キャッシュ９８は初期値が入っているので、４のエントリがキャッシュ９８に存在し、Inscopeフラグが真になっているので、ステップ２０２はステップ２１０にブランチし、そこからステップ２１２にブランチする。プロセスは、次に、ステップ２１２でDOC Bのプロパティを結果セットに追加し、図９のステップ１０８に戻る。
この例を続けて説明すると、DOC Gがステップ１０８で次に検索される。図１４に示すように、DOC GはドキュメントＩＤが１６（図１０のステップ２００）に、親フォルダＦ８のドキュメントＩＤが８（ステップ２０２）になっている。このフォルダにはエントリがキャッシュ９８（図１５）にないので、プロセスのステップ２０６はステップ２０８にブランチし、そこで（少なくとも１つの）指定の深いスコープはプロセスを図１３のステップ４００に進める。
ステップ４００で、DOC GのパスのドキュメントＩＤ、つまり、８、４、１および０が取得され、カレントドキュメントＩＤはパス内の次のフォルダのＩＤである４にセットされる。しかし、今回は、ステップ４０２はこのドキュメントＩＤキー４に対して真のInscopeフラグを戻す（以下で説明するように偽の“Shallow”スコープ・フラグと一緒に。これは、フォルダＦ４のスコープが浅いと指定されていなかったことを意味する）。従って、ステップ４０４はステップ４１２にブランチし、そこでShallowスコープ・フラグがテストされ、プロセスをステップ４１４にブランチさせる。ステップ４１４で、カレントドキュメントＩＤ４のすべての判明している子供、この例では、ドキュメントＩＤが８であるフォルダＦ６だけがキャッシュ９８（図１５）に追加され、Inscopeフラグは真に、Shallowフラグは偽になっている。これが可能であるのは、フォルダＦ４がスコープ内にあったことと、スコープが深いために、フォルダＦ４の下のすべての判明しているフォルダもスコープ内にあるためである。この例では、フォルダＦ８だけがＦ４の下にあることが分かっているが、他の例では、フォルダのチェイン全体がスコープ内のフォルダの下にあることが分かっている場合があり、その場合は、チェイン全体が追加されることになる。以上から理解されるように、これによりキャッシュ９８が高速に満たされる。そのあと、プロセスは図１０のステップ２１０に戻る。
Inscopeフラグは真であるので、ステップ２１０はステップ２１２にブランチし、そこでDOC Gのプロパティが結果セットに追加される。プロセスは図９のステップ１０８に戻り、そこでDOC Hが次に検索される。キャッシュ９８にはDOC Gから得た情報が入っているので、次のドキュメントDOC Hがスコープ・テストされるときは、ステップ２００−２１０（図１０）によってスコープ内にあることが即時に判断される。
しかし、次にDOC Mがテストされるときは、DOC Mはスコープ内にない。図１０と図１３を図１４と一緒にたどっていくと理解されるように、DOC Mの直属親フォルダＦ２７と、DOC Mの上位レベル・フォルダ（Ｆ２１とＦ２３−Ｆ２６）のどちらも、ドキュメントＩＤが０であるルート・ディレクトリを除き、この時点ではキャッシュ９８にエントリをもっていない。従って、ステップ４００−４０８は、最終的にはステップ４０４を通ってステップ４１２にブランチすることになる。ルート・ディレクトリは浅いと指定されていないので、判明している子供、つまり、２７、２６、２５、２４、２３および２１には、カレントドキュメントＩＤのInscopeフラグ値、つまり、偽に等しいルート・ディレクトリのInscopeフラグの値が入ることになる。これが可能であるのは、パス全体E:＼F21＼F23＼F24＼F25＼F26＼F27内の各フォルダが実効的にテストされ、上位レベルのフォルダがスコープ内にあると初期値化されていなかったためである。このようにして、キャッシュはこれらのフォルダの偽値で高速に満たされることになる。
DOC Kが次に選択されるときは、キー２１（ドキュメントＩＤ  ２１）はすでにキャッシュに偽としてストアされている。その結果、ステップ２００−２１０はプロセスを図９のステップ１０８に戻し、次のドキュメントを選択させる。
最後に、DOC Lでは、Ｆ３１はそのためのエントリをキャッシュにもっていない。チェインのさらに上のＦ２１は偽のエントリをもっているが、このことは必ずしもＦ３１またはＦ２２のどちらかが偽であることを意味しない。従って、プロセスはなんらかの方法でプロセスをショートカットするのではなく、チェインを上にたどっていく。従って、ステップ２００−２０８はＦ３１がキャッシュ９８にないと判断するので、図１３のステップ４００にブランチする。
ステップ４００−４０４で、ドキュメントＩＤが２２（図１４）であるE:＼F21＼F22はスコープ内にあると判断されるが、そのShallowフラグはそれが浅いと示している。その結果、ステップ４１２はある種の情報に基づいてステップ４１６にブランチする。具体的には、正しい合体が行われたとすると、浅いフォルダの上のどのフォルダも深いと指定されていない。そうでなければ、浅いフォルダはもっと深いフォルダに合体されていることになる。さらに、浅いフォルダの下にあるが、検索ドキュメントの上にあるフォルダがスコープ内にあって、深いと指定されていれば、キャッシュ９８に初期値を入れておくと、そのようなフォルダは、チェインを上にたどっていく間に浅いフォルダに到達する前にキャッシュ９８に見つかることが保証される。そのようなフォルダは見つからなかったので、現パス内の判明している子供はスコープ内になく、Inscopeフラグを偽にしてキャッシュ９８に追加することができる。この例では、Ｆ３１だけが分かっているので、ステップ４１６は、Inscopeフラグを０に、Shallowフラグを０にして３１をキャッシュ９８に追加する。このようにした１つの目的は、Shallowスコープ・フラグをキャッシュ９８に残しておくためである。なお、正しい合体が行われていなければ、パスのさらに上の浅いフォルダはステップ４０４でキャッシュになかったが、ステップ４１０または４１４でそのInscopeフラグが偽でオーバライトされたことがなかったものとして扱う必要がある。
ステップ４１６は図１０のステップ２１０に戻り、そこで偽のInscopeフラグが図９のステップ１０８に戻される。しかし、今回は、検索されるドキュメントは残っていないので、ステップ１１０を通ってプロセスは終了する。以上を要約すると、図９、１０および１３の代替実施例では、プレフィックス・マッチングを行うことなく、正しくスコープ内にあったドキュメントDOC B、DOC GおよびDOC Hだけが戻されている。これと同時に、キャッシュ９８は高速に満たされたので、他のドキュメントを即時にスコープ・テストすることができる。
以上から理解されるように、上述したどちらの実施例の場合も、プレフィックス・マッチングが大幅に減少または除去されると共に、キャッシュの埋め込みが高速化されるので、時間が大幅に節減されることになる。確かに、キャッシュを使用すると、実際に総時間がスコープ・テストに加わるというシナリオを考えることも可能であるが（例えば、フォルダ当たりのドキュメントが１つだけで、その各々を別々にプレフィックス・マッチングするか、長いチェインを検査する必要がある場合）、実際にはそのような事態はたとえ起こっても、めったに起こるものではない。非常に多数のドキュメントが見つかったときは、本発明によるスコープ・テストはほとんど常に大幅に高速化する。しかし、このようなまれな事態のもとでも、本発明を使用したときの時間コストは代表的な照会とフォルダ構成で本発明を使用すると得られる利点と比べれば、微々たるものである。もちろん、テスト（例えば、見つかったドキュメント数のしきい値をテストすること）を予備的に行って、本発明に従ってキャッシュ８６などを使用すべきか、あるいはプレフィックス・マッチングを行うべきかを判断するようにした代替メカニズムを考えることも可能である。
同様に、スコープ情報をインデックスに含めて、基準マッチングとスコープ・テストを実効的に１つのプロセスに結合することも可能である。しかし、スコープ情報をインデックスに含めると、これに関連してコスト上の問題や他の問題が起こることになる。例えば、これを行う１つの方法は、インデックス内の各フォルダに個別的に名前をつけることである。この場合、１つのキーが各フォルダ名になる。しかし、サーチは多数のサーチ・キーを必要とするため、サーチに大量の時間が加わることになる。別の方法として、各パスを複合キーとしてストアすることも可能である。しかし、例えば、ファイルまたはフォルダが改名されたときは、そのたびに大量の更新をインデックスに対して行い、インデックスを最新状態に保つ必要がある。以上を要約すると、スコープ情報をインデックスに入れることは可能であっても、実用的であるとは考えられない。
最後に、キャッシュ内にまたは結果セット内に入っているフォルダまたはドキュメントは照会が解決されている間に作成、改名または削除することができる。さらに、以上から理解されるように、あるスコープが与えられているとき、キャッシュを不揮発性ストレージに持続的にストアしておくことが可能である。例えば、ユーザがそこから選択できるスコープの数が制限されている場合、利用可能な各スコープごとにキャッシュを持続的にストアしておくことができる。同じように、１つまたは２つ以上の特定スコープがユーザによって頻繁に選択される場合、最も頻繁に選択されるスコープごとに１つまたは２つ以上のキャッシュをストアしておくことができる。従って、あるキャッシュの結果セットが将来の使用に備えて持続的にストアされているような場合には、ドキュメントまたはフォルダのステータスはストアしてから将来使用するまでの間に同様に変化することがある。
上記のいずれの場合も、結果セットまたはキャッシュをフォルダまたはドキュメントのステータス変化に基づいて更新することが可能である。この目的のために、Windows（登録商標）には、照会または他のプロセスに通知を行うことができるアプリケーション・プログラミング・インタフェース（ＡＰＩ）が用意されている。これらのWIN32-APIは、ＮＴＦＳではFindFirstChangeNotificationおよびFindNextChangeNotificationと名づけられており、なんらかの変更がフォルダまたはドキュメントに行われたとき、変更されたフォルダまたはドキュメントのドキュメントＩＤと変更のタイプ（例えば、改名や削除）を含む変更通知を行う。
これらのＡＰＩを使用すると、照会プロセスはドキュメントへの変更をモニタすることができる。例えば、削除通知を受け取ると、対応するドキュメントＩＤを探すためにハッシュ・テーブル・キャッシュがサーチされ、エントリが見つかると、そのエントリのスコープ情報は有効でなくなったのでエントリが削除される。改名通知を受け取ったときは、ハッシュ・テーブルが同じようにサーチされる。ドキュメントＩＤに対応するエントリがハッシュ・テーブルに見つかったときは、その改名アイテムはフォルダでなければならないので、プレフィックス・マッチングが新しいフォルダ名で行われ、そのフォルダのInscopeフラグを更新できるようにする。最後に、以上の説明から理解されるように、結果セットは、たとえ照会がまだ解決中であっても、同じように調整可能であり、照会が解決中である場合には、まだスコープ・テストされていない検索ドキュメントは上記ＡＰＩを通して同じように、追加、削除および／または改名することができる。
上述してきた詳細説明から理解されるように、本発明が提供する方法およびメカニズムによると、特に非常に多数のドキュメントを取り扱う照会では、ファイル・システムの照会が大幅に改善される。本発明の方法およびメカニズムによれば、照会を解決するために要する時間量が大幅に低減され、基準合致ドキュメントをスコープ・テストするために要する時間量が大幅に低減される。本発明の方法およびメカニズムは既存のファイル・システムと一緒に機能し、拡張が可能である。
本発明は種々態様の変更および代替構成が可能であるが、本発明の実施例のいくつかを図示し、詳しく上述してきた。しかし、当然に理解されるように、本発明は上述してきた具体的な実施態様に限定されるものではなく、本発明の精神と範囲に属するあらゆる変更または改良、代替構成、および等価技術を包含するものである。
【図１】
0004236702.tif 000002
【図２】
0004236702.tif 000003
【図３】
0004236702.tif 000004
【図４】
0004236702.tif 000005
【図５】
0004236702.tif 000006
【図６】
0004236702.tif 000007
【図７】
0004236702.tif 000008
【図８】
0004236702.tif 000009
【図９】
0004236702.tif 000010
【図１０】
0004236702.tif 000011
【図１１】
0004236702.tif 000012
【図１２】
0004236702.tif 000013
【図１３】
0004236702.tif 000014
【図１４】
0004236702.tif 000015
【図１５】
0004236702.tif 000016