JP2005509208A - 情報検索のための階層式データ駆動型ナビゲーションのシステムおよび方法 - Google Patents

Abstract

データ駆動型階層情報ナビゲーションのシステムおよび方法により、資料を特徴付けるある共通の属性でドキュメントまたはその他の資料のセットを探索することが可能になる。本発明は、このナビゲーションモードを使用するデータ駆動型階層式ナビゲーションシステムのいくつかの態様を含む。本発明のナビゲーションシステムは、インターフェース、知識ベース、ならびに知識ベースを生成するための分類法定義プロセスおよび分類プロセス、グラフベースのナビゲート可能なデータ構造、およびそのデータ構造を生成するための方法、システムのＷｏｒｌｄ Ｗｉｄｅ Ｗｅｂアプリケーション、ならびにシステムを実施するための方法という特徴を含む。ユーザは、属性に関する所望の値を選択することによってドキュメントの特定の集合を探索し、ブラウズすることができる。データ駆動型の階層情報ナビゲーションのシステムおよび方法により、用語を資料と関連付けること、用語の間で１組の階層関係を定義すること、および用語間の誘導された探索の機構を提供することによってこのナビゲーションモードが可能になる。

Description

本発明は、一般に、情報ナビゲーションシステムおよび情報探索エンジンに関する。

情報のデータベースからの情報検索は、より高い計算機能力とネットワーキングインフラストラクチャによって、大量の情報の集約、およびその情報への広汎なアクセスが可能になるにつれて、特にＷｏｒｌｄ Ｗｉｄｅ Ｗｅｂ（ＷＷＷ）上で、ますます困難な問題となっている。情報検索プロセスの目標は、ユーザの関心対象である資料の特定を可能にすることである。

ユーザが探索することができる資料の数が増加するにつれ、探索に関係のある資料を特定することが、ますます重要になるが、ますます困難にもなる。情報検索プロセスがもたらす課題には、直観的で柔軟性のあるユーザインターフェースを提供すること、妥当な時間内でユーザのニーズに関係のある資料を完全かつ正確に特定することが含まれる。情報検索プロセスは、２つの互いに関連する技術的態様、すなわち、情報編成と情報アクセスを包含する。

現行の情報ナビゲーションシステムは、通常、３つのパラダイムのうち１つに従っている。１つのタイプの情報ナビゲーションシステムは、データベースクエリシステムを使用する。通常のデータベースクエリシステムでは、ユーザが、固定のデータフィールドに対する値を指定することによって構造化されたクエリを策定し、システムは、データフィールドがそれらの値を含むドキュメントを列挙する。例えば、ＰｒｉｃｅＳＣＡＮ．ｃｏｍが、そのようなインターフェースを使用している。一般に、データベースクエリシステムは、フォームベースのインターフェースをユーザに提示し、フォーム入力をＳＱＬなどの正規のデータベース言語のクエリに変換した後、そのクエリをリレーショナル・データベース管理システム上で実行する。通常のクエリベースのシステムの欠点には、全くドキュメントを戻さないクエリをユーザが行うことを許していること、および結果セットの拡大または拡張ではなく、結果セットのさらなる限定（ユーザの探索指定に対応するドキュメント）だけをもたらすクエリ変更オプションを提供していることが含まれる。

第２のタイプの情報ナビゲーションシステムは、自由テキスト探索エンジンである。通常の自由テキスト探索エンジンでは、ユーザは、任意のテキストストリングを、しばしば、ブール式の形態で入力し、システムは、マッチするテキストを含むドキュメントを列挙することで応答する。例えば、Ｇｏｏｇｌｅ．ｃｏｍが、自由テキスト探索エンジンを含む。一般に、自由テキスト探索エンジンは、しばしば単一の行である探索フォームをユーザに提示し、あらかじめ計算された索引を使用してクエリを処理する。一般に、この索引は、ドキュメントの内容を実質的に考慮することなく、各ドキュメントをそのドキュメントに含まれる言葉の相当な部分に関連付ける。したがって、結果セットは、しばしば、関係のあるドキュメントと関係のないドキュメントを混ぜ合わせた大部の整理されていないリストである。ユーザのクエリの目的を特定し、結果セットに関連度ランク付けを与えること、または別の形で結果セットを絞り込む、または編成することを試みる変種が開発されているが、それらのシステムは、それらの目的を達するのに限界があり、信頼性を欠いている。

第３のタイプの情報ナビゲーションシステムは、ツリーベースのディレクトリである。ツリーベースのディレクトリでは、ユーザは、一般に、ツリーの根底ノードから開始して、ツリーのその他のノードにつながる精緻化する分岐を連続的に選択することによってクエリを指定する。例えば、Ｓｈｏｐｐｉｎｇ．ｙａｈｏｏ．ｃｏｍが、ツリーベースのディレクトリを使用している。通常の実施形態では、ハードコーディングされたツリーが、データ構造の中に記憶され、同じデータ構造、または別のデータ構造が、ドキュメントが配置されているツリーのノードまたはノード群にドキュメントをマップする。特定のドキュメントは、通常、ツリーを経由する１つのパスだけから、またはせいぜい、いくつかのパスだけからアクセス可能である。ナビゲーション状態の集合は、比較的静的である。すなわち、ドキュメントが、ディレクトリの中のノードに普通に追加されるが、ディレクトリの構造は、通常、変化なしである。純粋なツリーベースのディレクトリでは、ディレクトリノードは、すべてのユーザが開始する単一の根底ノードが存在するように構成され、すべての他のディレクトリノードは、根底ノードからユーザが選択する分岐の固有のシーケンスを介してだけ到達することができる。そのようなディレクトリは、ツリーの分岐が、ナビゲーション上、互いに連結していないようになっていなければならないという制限を課す。これは、ドキュメントが連結していない分岐に割り当てられている仕方が、ユーザには直観的でない可能性があっても、そうである。追加のリンクを加えてツリーを有向の非輪状（ａｃｙｃｌｉｃ）グラフに変換することによってこの柔軟性のなさに対処することが可能である。ディレクトリ構造を更新することが困難なタスクであることは変わらず、特にリーフノードが、多数の対応するドキュメントを有することになりがちである。

以上のタイプのナビゲーションシステムのすべてで、ユーザが、クエリの結果セットを閲覧した後にそのクエリを効果的に変更することが困難である可能性がある。データベースクエリシステムでは、ユーザは、クエリに用語を追加すること、またはクエリから用語を取り除くことができるが、ユーザが指定不足の（ｕｎｄｅｒｓｐｅｃｉｆｉｅｄ）クエリ（すなわち、多過ぎる結果）、または指定過剰の（ｏｖｅｒｓｐｅｃｉｆｉｅｄ）クエリ（すなわち、結果が全くない）を回避することは、一般に困難である。同じ問題が、自由テキスト探索エンジンでも生じる。ツリーベースのディレクトリにおいて、ユーザがクエリを変更する手段は、分岐を選択することによってクエリを絞り込むか、前の分岐まで後退してクエリを広げることだけである。

また、情報検索のための様々な他のシステムも利用可能である。例えば、ともに「誘導されたパラメトリック探索を実行するための方法およびシステム（Ｍｅｔｈｏｄ ａｎｄ Ｓｙｓｔｅｍ ｆｏｒ Ｅｘｅｃｕｔｉｎｇ ａ Ｇｕｉｄｅｄ Ｐａｒａｍｅｔｒｉｃ Ｓｅａｒｃｈ）」という名称のデイニッシュ（Ｄａｎｉｓｈ）他に発行された米国特許第５，７１５，４４４号明細書および米国特許第５，９８３，２１９号明細書が、ある系列の項目から単一の項目を特定するためのインターフェースを開示している。このインターフェースは、系列の項目の中に存在する特徴の１組のリストをユーザに提供し、選択された特徴を満たす項目を特定する。

本発明、階層式データ駆動型情報ナビゲーションのシステムおよび方法により、ドキュメントまたはその他の資料の集合のナビゲーションが、その資料に関連するある共通の属性を使用して可能になる。ナビゲーションシステムインターフェースは、ユーザが、現在のナビゲーション状態において資料に関連する属性に関する値を選択することを可能にし、ユーザの選択に対応する資料を戻す。本発明は、用語（属性−値ペア）をドキュメントに関連付け、用語の間で１組の階層式精緻化関係（すなわち、部分的順序）を定義し、用語のドキュメントとの関連、および用語間の関係に基づく誘導されたナビゲーション機構を提供することによって、このナビゲーションモードを可能にする。

本発明は、階層式データ駆動型情報ナビゲーションシステムに関連するいくつかの構成要素および特徴を含む。その構成要素および特徴のなかには、ユーザインターフェース、知識ベース、知識ベースを生成し、保持するためのプロセス、ナビゲート可能なデータ構造、およびそのデータ構造を生成するための方法、システムのＷＷＷベースのアプリケーション、ならびにシステムを実施する方法がある。本発明は、本明細書で、主に製品データベースをナビゲートするためのＷＷＷベースのシステムに関連して説明するが、同様のナビゲーションシステムは、資料が用語と関連付けられることが可能であり、ユーザがそれらの用語を使用して関心対象の資料を特定することができる任意のデータベースの文脈で使用することが可能であることを理解されたい。

本発明は、資料の集合に関する情報の知識ベースを使用して、妥当なナビゲーションオプションを提供することによってナビゲーション状態の集合の中でユーザを誘導するインターフェースを策定し、採用する。知識ベースは、資料に関連する属性の列挙、各属性に関する値の範囲、および用語を関係付ける部分的順序の表現（属性−値ペア）を含む。例えば、エンターテイメントに関連する資料に関する属性−値ペアは、製品：映画および監督：スパイク・リーであることが可能である。（属性−値ペアは、本明細書全体にわたって、この属性：値の形式で表わされ、ナビゲーション状態は、括弧で括られた属性−値ペアセットとして表わされる。）また、知識ベースは、資料の集合の中の各項目をその項目を特徴付ける１組の用語に関連付ける分類マッピングも含む。

知識ベースは、通常、分野によって編成され、分野は、自然なグループ化に適合する資料のセットである。好ましくは、分野は、扱いやすい数の属性で、その分野内の資料の間で効果的に区別を行い、ナビゲートするのに十分であるように選択される。知識ベースは、好ましくは、各分野の特徴付けを含み、この特徴付けは、その分野内のドキュメントの分類に関する規則、またはデフォルトの見込みを含むことが可能である。特定の項目は、複数の分野に属することが可能である。

本発明は、ナビゲーションのためのユーザインターフェースを含む。ユーザインターフェースは、好ましくは、ユーザのナビゲーション状態を属性によって編成された１組の用語として提示する。所与の１組の用語に関して、ユーザインターフェースは、その用語に関連する資料を提示し、ナビゲーション状態を絞り込むため、または広げるための妥当なナビゲーションオプションを提示する。本発明の一態様では、ユーザは、用語を選択すること、および選択解除することによって資料の集合の中でナビゲートする。

本発明の一態様では、ユーザインターフェースは、ユーザが複数の用語から成る包括的なクエリを構成してサブミットするのを待つのではなく、用語の選択、または選択解除に即時に応答する。クエリが実行されると、ユーザは、追加の用語を選択すること、または既存の用語を精緻にすることによってナビゲーション状態を絞り込むことができる。あるいは、ユーザは、既に選択されている用語を選択解除すること、または用語を一般化することによってナビゲーション状態を広げることができる。好ましい実施形態では、ユーザは、用語が選択されたのとは異なる順序で用語を選択解除することによってナビゲーション状態を広げることができる。例えば、ユーザは、｛製品：映画｝で開始し、追加の用語を選択することによって｛製品：映画；ジャンル：ドラマ｝に絞り込み、｛製品：映画；ジャンル：ドラマ；監督：スパイク・リー｝にまで再び絞り込んだ後、用語を選択解除することによって｛製品：映画；監督：スパイク・リー｝に広げることができる。

本発明の別の態様では、ユーザインターフェースは、ユーザが、自由テキスト探索を使用して関心対象の用語を見出すことを可能にする。本発明の別の態様では、ユーザインターフェースは、ユーザが、資料に関連する記述的情報に対して自由テキスト探索を使用することも可能にする。

本発明の別の態様では、ユーザインターフェースは、ナビゲーション状態を絞り込むための文脈依存のナビゲーションオプションをユーザに提示する。ユーザインターフェースは、選択されると結果のナビゲーション状態で対応するドキュメントが全く存在しない用語をユーザに提示しない。ユーザインターフェースは、現在のナビゲーション状態で少なくとも１つの項目に関連する用語だけをユーザに提示する。また、ユーザインターフェースは、新たなナビゲーションオプションをそのオプションが妥当になるにつれて提示する。知識ベースは、特定の属性または用語が、いつナビゲーションのためにユーザに供与されるかを決める規則を含むことが可能である。

本発明の別の態様では、例えば、資料が、様々なソースから購入可能な製品に対応する場合、知識ベースは、その資料から集約された規範的な表現のカタログを含む。
本発明の別の態様では、知識ベースは、一度に探索可能であるようにグループ化された資料のセットであるストアの定義を含むことが可能である。ストアは、１つまたは複数の分野からのドキュメントを含むことが可能である。項目は、複数のストアに割り当てることができる。知識ベースは、特定のストアに関するナビゲーションをカスタマイズする規則も含むことが可能である。

本発明の別の態様では、知識ベースは、多段式の反復プロセスを介して開発される。ワークフローマネージメントが、知識ベースを生成し、保持することの効率を最大化するようにリソースを割り振る。

知識ベースは、資料の集合の中のナビゲーションをサポートするデータ構造を生成するのに使用される。本発明の一態様では、ナビゲーションシステムは、用語のセットをその用語が関連付けられる資料のセットにマップするナビゲーション状態の階層（すなわち、部分的順序）から成る。本発明の別の態様では、ナビゲーション状態は、あるナビゲーション状態から別のナビゲーション状態に絞り込むのに使用される用語に対応する遷移によって関係付けられる。ナビゲーション状態は、完全に、または部分的にあらかじめ計算されること、あるいは完全にランタイムに計算されることが可能である。

本発明は、本発明の以上の特徴およびその他の特徴を含め、以下の説明、および添付の図面からより十分に理解することができる。

ユーザインターフェース
本発明の一実施形態によれば、図１は、階層式データ駆動型ナビゲーションシステムに対するユーザインターフェース１０を示している。ナビゲーションシステムは、知識ベースの中で定義されたドキュメントの集合に対して動作する。図示するとおり、ユーザには、好ましくは、ナビゲーションシステムを使用する少なくとも２つの代替の方法が提示される。すなわち、（１）用語を選択してドキュメントの集合の中をナビゲートすることによる方法、または（２）所望のキーワードを探索ボックスに入力することによる方法である。

ナビゲーションシステムは、好ましくは、分野によってドキュメントを編成する。本発明の一実施形態によれば、図１〜１０に示されたユーザインターフェース１０は、ワイン分野の一部である１組のドキュメントに対して動作する。好ましくは、分野は、自然なグループ化を反映するドキュメントの集合の一部分を定義する。一般に、分野内のドキュメントを分類するのに使用される属性のセットは、ドキュメントの集合全体を分類するのに使用される属性の扱いやすいサブセットである。分野定義は、製品のタイプ、例えば、ワイン、または家庭用電化製品であることが可能である。分野は、下位分野に分割してドキュメントの集合をさらに編成することができる。例えば、テレビジョン、ステレオ機器等の下位分野に分割される家庭用電化製品分野が存在することが可能である。ドキュメントは、品物またはサービスに対応することが可能である。

ユーザインターフェースは、ユーザが、一度に１分野内でナビゲートすることができるようにすることが可能である。代替として、ユーザインターフェースは、特にある属性が複数の分野に共通である場合、複数の分野の同時のナビゲーションをできるようにすることが可能である。

ユーザインターフェースは、ユーザが、ナビゲーション状態の集合の中をナビゲートすることを可能にする。各状態は、１組の用語、およびその用語に関連するドキュメントのセットから成る。ユーザは、用語の選択および選択解除を行って選択された用語の各セットに対応するナビゲーション状態を獲得することにより、ナビゲーション状態の集合の中をナビゲートする。好ましくは、図４のように、ユーザインターフェース１０は、用語５２のリスト５０と、状態に対応するドキュメント４２のいくつか、またはすべてのリスト４１をともに表示することによってナビゲーション状態を提示する。好ましくは、ユーザインターフェースは、属性によって編成されたナビゲーション状態の用語５２を提示する。好ましくは、初期ナビゲーション状態は、用語が全く選択されていないことに対応し、したがって、集合の中のドキュメントのすべてに対応する根底（ｒｏｏｔ）状態である。

図２に示すとおり、ユーザインターフェース１０は、ユーザが、属性２２に関する値２８を選択することにより、または現在、選択されている値をより特定の値で置き換えることにより（適切である場合）、ナビゲーション状態を絞り込むことができるようにする。好ましくは、ユーザインターフェース１０は、現在のナビゲーション状態を絞り込むのに利用可能なオプションをユーザに提示し、好ましくは、妥当な用語が属性によって編成される。本発明の一部の実施形態では、図２に示すとおり、ユーザは、現在のナビゲーション状態における属性２２によって編成されたインディケータ２４によって示されるドロップダウンリスト２６から値２８を選択することができる。ユーザインターフェースは、これらのナビゲーションオプションを様々な形式で提示することができる。例えば、値は、テキストとしてではなく、図形として、または記号として提示することができる。インターフェースは、用語を選択するあらゆる方法、例えば、マウスクリック、キーボードストローク、または音声コマンドを許容することが出来る。インターフェースは、テレビジョンまたはＷＷＷや電話デバイスまたは無線デバイスなどの様々な媒体およびデバイスを介して提供することができる。本明細書では主に視覚的インターフェースとして説明しているが、インターフェースは、音声構成要素も含むこと、または主に音声ベースであることも可能である。

好ましくは、現在のナビゲーション状態では、ユーザインターフェースは、少なくとも１つのドキュメントを有するナビゲーション状態をもたらすナビゲーション状態を絞り込むためのオプションだけしか提示しない。ナビゲーションオプションを提供することに関するこの好ましい基準により、「行き止まり」、つまり空の結果セットに対応するナビゲーション状態が存在しないことが確実にされる。

好ましくは、ユーザインターフェースは、ナビゲーション状態を絞り込むためのオプションが、現在のナビゲーション状態よりも確定的に少ないドキュメントを有するナビゲーション状態をもたらす場合にだけ、そのオプションを提示する。そうすることにより、ユーザインターフェースが、現在のナビゲーション状態における用語によって既に暗示されている選択をユーザに提示しないことが確実にされる。

好ましくは、ユーザインターフェースは、ユーザが現在のナビゲーション状態を絞り込むように用語２８を選択するとすぐに、ユーザによるさらなるトリガアクションなしに、新しいナビゲーション状態を提示する。システムは、各ユーザに即時フィードバックで応答するため、ユーザは、包括的なクエリを策定してから、そのクエリをサブミットする必要がない。

本発明の一実施形態では、図３および４で示すとおり、ユーザインターフェース１０は、ユーザが、選択された用語のリスト５０から用語５２を取り除くことを可能にすることにより、現在のナビゲーション状態を広げることを可能にすることができる。例えば、インターフェース１０は、選択を取り除くためのチェックボックス５４、および新たな探索をトリガするボタン５６を有するリスト５０を提供することができる。例示する実施形態では、ユーザは、選択された用語５２を任意の順序で取り除くことができ、一度に複数の選択５２を取り除くことができる。

好ましくは、ユーザに提示されるナビゲーションオプションは、文脈に依存する。例えば、以前に選択された用語を精緻にする用語が、結果のナビゲーション状態におけるナビゲーションオプションになることが可能である。例えば、図５を参照すると、香り：木材と木の実の香り５２という用語が選択された後（ユーザは、香りという属性に関して木材と木の実の香りという値２３を選択している）、木材と木の実の香り２３が、属性のリスト２０において新たなナビゲーション状態に関するインターフェースの中で出現し、クエリのさらなる精緻化のために特定の属性に関係する値２８の選択を可能にする。ユーザインターフェースは、最初、提示されなかったある属性も、その属性が新たに妥当になるにつれて提示することが可能である。例えば、図３を図２と比較すると、フランスのブドウ園という属性２５が、ユーザが前のナビゲーション状態において地域：フランスの地域という用語を既に選択した後になってはじめて、属性２０のリストの中に出現している。属性は、このようにして、所望されるだけの数のレベルに組み込まれることが可能である。属性を、その属性が妥当となった際にナビゲーションオプションとして提示することにより、ナビゲーションオプションが有意義なものとなる前に、そのオプションでユーザが圧倒されることが回避される。

さらに、一部の属性２２に関して、値２８の複数の比較できない（精緻化されない）選択が該当する可能性がある。例えば、香りという属性に関して、どちらも他方を精緻化しないフルーツのようなという値と木の実のようなという値がともに選択されて、香り：フルーツのようなという用語、および香り：木の実のようなという用語が、ナビゲーション状態を絞り込むようになることが可能である。したがって、ユーザは、ときとして、単一の属性の下で複数の値を選択することによってクエリを精緻化することができる可能性がある。

好ましくは、ある属性は、その属性がもはや有効な選択、または役立つ選択ではなくなった場合、ナビゲーションオプションとして消去される。例えば、結果セットの中のドキュメントのすべてが、ある共通の用語（そのナビゲーション状態に到達するのに選択された用語に加えて）を共有する場合、その用語の選択により、結果セットがさらに精緻化されることはなく、したがって、その用語に関連する属性は、ナビゲーションオプションとして消去される。例えば、図６を図４と比較すると、属性ワインタイプ２７が、ナビゲーションオプションとして消去されている。というのは、結果セットの中のドキュメント４２のすべてが、ワインタイプ：原産地呼称ワインという用語を共有しているからである。好ましい実施形態では、インターフェース１０のさらなる特徴は、この情報が、結果セットの中のドキュメント４２の共通特性としてユーザに提示されることである。例えば、図６を参照すると、インターフェース１０は、結果セットの中のドキュメント４２の共通特性を示す表示６０を含む。結果セットの中のドキュメントのすべてがある用語を共有する場合にナビゲーションオプションとしてその用語を取り除くことにより、ユーザが、結果セットを精緻化しない用語を選択することによって時間を浪費することが防止される。

また、好ましくは、ユーザインターフェースは、値を選択することにより、結果セットの中でドキュメントが全くもたらされない場合、その値をナビゲーションオプションとして消去することも行う。例えば、図８を図７と比較すると、ユーザが、ワインスペクテータ（Ｗｉｎｅ Ｓｐｅｃｔａｔｏｒ）範囲：９５〜１００という用語を選択した後、ユーザインターフェースは、原産地呼称という属性２２に関する値のうち、アレグザンダバレー（Ａｌｅｘａｎｄｅｒ Ｖａｌｌｅｙ）２９という値およびナパバレー（Ｎａｐａ Ｖａｌｌｅｙ）という値２９を例外として、リスト２６の中のすべての値２８、２９をナビゲーションオプションとして消去している。原産地呼称という属性に関する値のリスト２６の中で、結果セットにおいて少なくとも１つのドキュメントを戻す値は、アレグザンダバレー２９とナパバレー２９の２つだけである。空の結果セットをもたらす値をナビゲーションオプションとして取り除くことは、ユーザが行き止まりに到達するのを防止することによってユーザ時間を節約する。

好ましくは、ユーザインターフェースは、ユーザが、自由テキスト探索を使用して所望の語を探索することを可能にする。図９に例示する本発明の一実施形態によれば、探索ボックス３０により、好ましくは、ユーザが、ドキュメント自体の全テキスト探索を行うのではなく、関心対象の用語に関する自由テキスト探索を行うことが可能になる。好ましくは、ユーザインターフェースは、属性３６によって編成された用語を含む用語３４のリスト３２を提示し、ユーザがその用語のなかから選択できるようにすることによってそのような探索に応答する。好ましくは、ユーザインターフェースは、ユーザの選択に対して、その用語の選択に対応するナビゲーション状態をユーザに提示することで応答する。次に、ユーザは、その状態からナビゲートする（すなわち、その状態を絞り込む、または広げることにより）か、または用語に関するさらなる自由テキスト探索を行うことができる。

好ましくは、ユーザインターフェース１０は、現在のナビゲーション状態に対応するドキュメントの完全なリストまたは部分的なリスト４１を提示する。好ましくは、ユーザは、特定のドキュメント４２に関心を有する場合、図１０に示すとおり、そのドキュメントを選択し、そのドキュメントに関連する用語７４のリスト７２を含め、そのドキュメントに関するさらなる情報を含むレコード７０を獲得することができる。好ましくは、ユーザインターフェース１０は、ユーザが、それらの用語７４の任意のサブセットを選択することを可能にして、選択された用語セットに対応するナビゲーション状態にナビゲートすることを可能にする。

好ましくは、ユーザインターフェース１０は、現在のナビゲーション状態に関係があるが、必ずしも現在のナビゲーション状態の一般化、または精緻化ではない関連するナビゲーション状態に直接にリンクするナビゲーションオプションも提供する。このリンクは、好ましくは、現在のナビゲーション状態からユーザの関心を推測し、ユーザが関係するトピックに乗り換えることができるようにする。例えば、ユーザが食料品分野のある特定のナビゲーション状態を訪れている場合、リンクにより、ワイン分野でその食料品を補完するワインのナビゲーション状態にユーザが誘導されることが可能である。

ナビゲーションシステムに対するインターフェースを本明細書では、ユーザインターフェース１０として説明してきたが、インターフェースは、ナビゲーションシステムに対する他の形態のアクセスを提供することも可能である。代替の実施形態では、インターフェースは、他のアプリケーションのために、または他のアプリケーションを介してナビゲーションシステムへのアクセスを可能にするアプリケーション・プログラム・インターフェースであることが可能である。また、インターフェースは、独立のデータ指向アプリケーションの機能を強化することも可能である。また、インターフェースは、ＷＷＷベースのアプリケーション、またはＸＭＬベースのアプリケーションの文脈で使用することもできる。また、ナビゲーションシステムが、複数のインターフェースモードを同時にサポートすることも可能である。ナビゲーションシステムは、様々な仕方で、例えば、無線通信デバイスを介して、またはハンドヘルドデバイス上で供与することが可能である。

知識ベース
好ましくは、ナビゲーションシステムは、ナビゲーションに関係のあるすべての情報を知識ベースの中に記憶する。知識ベースは、分類法定義と分類という２つのプロセスからの情報のリポジトリである。分類法定義は、ドキュメントを特徴付ける妥当な属性を特定し、それらの属性に関する許容できる値（値のリストまたは範囲などの）を決め、用語の間の精緻化関係（属性−値ペア）の部分的順序を定義するプロセスである。分類は、用語をドキュメントに関連付けるプロセスである。また、知識ベースを使用して、分野、分類規則、およびデフォルトの見込みなどの以上２つのプロセスをサポートするあらゆる情報資産を保持することもできる。さらに、知識ベースを使用して、ユーザのナビゲーション体験に影響を及ぼす補足的な情報、および補足的な資料を保持することもできる。

分類法定義プロセスは、ドキュメントを適切に特徴付ける１組の属性を特定する。分類法定義プロセスを編成する通常のやり方は、自然なグループ化に適合するドキュメントのセットであり、分野内のドキュメントの間で効果的に区別を行い、ナビゲートするのに、扱いやすい数の属性で十分である分野に、ドキュメントの集合を編成することである。知識ベースは、好ましくは、各分野の特徴付けを含み、特徴付けは、その分野内のドキュメントの分類に関する規則、またはデフォルトの見込みを含むことが可能である。

また、分類法定義プロセスは、各属性に関して、適宜、様々なレベルの特定性で、完全なセットの値を特定することも行う。値は、好ましくは、集合の中のドキュメントの特定の特性を明らかにする。値は、明示的に列挙されること、または暗黙的に定義されることが可能である。例えば、「色」属性に関して、有効な色の値の完全なセットを指定することができるが、「価格」属性、または「日付」属性に関しては、範囲を定義することなく、値が収まることが可能な範囲、または一般的なデータタイプを指定することができる。これらの値を特定するプロセスには、分野に到達すること、またはドキュメントの集合を解析することが含まれることが可能である。

分類法定義プロセスは、用語の間の精緻化関係（属性−値ペア）の部分的順序も定義する。例えば、「原産地：フランス」という用語により、「原産地：欧州」という用語が精緻化されることが可能である。精緻化関係は、推移的であり、反対称であるが、必ずしも完全ではない。推移的とは、用語Ａにより用語Ｂが精緻化され、かつ用語Ｂにより用語Ｃが精緻化される場合、用語Ａにより用語Ｃが精緻化されることを意味する。例えば、原産地：パリにより原産地：フランスが精緻化され、かつ原産地：フランスにより原産地：欧州が精緻化される場合、原産地：パリにより原産地：欧州が精緻化される。反対称とは、２つの用語が異なる場合、両方の用語によって互いが精緻化されることは不可能であることを意味する。例えば、原産地：パリにより原産地：フランスが精緻化される場合、原産地：フランスにより原産地：パリが精緻化されることはない。

さらに、用語の間の精緻化関係の部分的順序は、必ずしも完全な関係ではない。例えば、どちらの用語によっても他方の用語が精緻化されないような２つの用語、原産地：フランスと原産地：スペインが存在する可能性がある。この特性を有する２つの用語は、比較できないという言い方がされる。一般に、２つまたはそれより多くの用語のセットは、そのセットから選択された異なる用語のすべてのペアに関して、２つの用語が比較できない場合、互いに比較できない。通常、ただし、必然的にではなく、異なる属性を有する２つの用語は、比較できない。

用語のセットを所与として、用語は、その用語により精緻化される他の用語がそのセットの中で全く存在しない場合、セットの中の最大用語であり、その用語を精緻化する他の用語がそのセットの中で全く存在しない場合、セットの中の最小用語である。例えば、セット｛原産地：フランス，原産地：パリ，原産地：スペイン，原産地：マドリード｝の中で、原産地：フランス、および原産地：スペインが最大であり、原産地：パリ、および原産地：マドリードは最小である。知識ベースの中で、用語は、その用語により精緻化される他の用語が全く存在しない場合、根底用語であり、その用語を精緻化する他の用語が全く存在しない場合、リーフ用語である。

図１１Ａ、１１Ｂ、１１Ｃは、ワインを分類するために使用することが可能な、部分的順序関係に従って構成された属性１１２および値１１４を示している。属性１１２は、タイプ／品種もの、原産地、および醸造年である。各属性１１２は、その属性に関する最大用語に対応する。属性１１２は、互いに比較できない値（例えば、醸造年）の平坦なセット、値（例えば、原産地）のツリー、または値により２つまたはそれより多くの互いに比較できない値（例えば、タイプ／品種もの）が精緻化されることを可能にする一般的な部分的順序を有することが可能である。矢印１１３は、値１１４の間の精緻化関係を示している。

属性および値は、ドキュメントの手動または自動の処理、およびドキュメントの解析を含め、いくつかのやり方で特定され、開発されることが可能である。さらに、この種の解析は、トップダウン式であること、またはボトムアップ式であることが可能である。つまり、根底用語から開始して、リーフ用語に向かって徐々に進むこと、またはリーフ用語から開始して根底用語に向かって徐々に進むことが可能である。この提示する発明を使用して情報を広めることに関心を有する小売業者、またはその他の人々が、属性および用語を定義することも可能である。

分類プロセスは、各ドキュメントを１組の用語に関連付けることによってナビゲーション状態の集合の中でドキュメントを探し出す。各ドキュメントは、１組の互いに比較できない用語、例えば、｛タイプ／品種もの：キャンティ，原産地：イタリア、醸造年：１９９６｝、ならびに任意の他の所望の記述情報に関連付けられる。ドキュメントが所与の用語に関連付けられる場合、ドキュメントは、所与の用語によって精緻化される用語のすべてにも関連付けられる。

分類プロセスは、様々なワークフローに従って行われることが可能である。ドキュメントは、直列に、または並列に分類されることが可能であり、自動分類ステップおよび手動分類ステップが、１回または複数回、任意の順序で行われることが可能である。精度およびスループットを向上させるため、ドキュメントの特定のサブセットに関する分類タスクを監督する、またはドキュメントの特定のサブセットに関する特定の属性さえ監督するように、人間のエキスパートを専門家として割り当てることができる。さらに、分類プロセスおよび分類法プロセスは、特に、一方のプロセスから得られた知識によって他方における改良が可能になるにつれ、交互配置することができる。

図１２は、分類プロセス２５０に関する可能なフローにおける段階を示している。データ獲得ステップ２５２、つまり、データベースのためのドキュメントの収集が、いくつかの異なる仕方で行われることが可能である。例えば、ナビゲーションシステムが動作する対象の製品カタログを有する小売業者が、自らの製品を事前定義されたセットとして記述する１組のドキュメントを提供する可能性がある。代替として、ドキュメントは、１つのソース、例えば、１つのＷｅｂサイトから、またはいくつかのソース、例えば、複数のＷｅｂサイトから収集された後、集約されることが可能である。所望のドキュメントがＷｅｂページである場合、ドキュメントは、Ｗｅｂを適切に巡回し（ｃｒａｗｌ）、ドキュメントを選択し、分野に合わないドキュメントを廃棄することによって収集することができる。データ翻訳ステップ２５４で、収集されたドキュメントが、さらなる処理を容易にするように形式設定され、構文解析される。自動分類ステップ２５６で、形式設定され、構文解析されたドキュメントが、ドキュメントを用語に自動的に関連付けるために処理される。手動分類ステップ２５８で、人間の検閲者が、自動分類を検証し、補正して、品質管理を確実にすることができる。好ましくは、自動分類ステップ２５６、または手動分類ステップ２５８で違反が行われた規則、または見込みが存在した場合、その違反が行われた規則、または見込みにフラッグが立てられて、手動分類ステップ２５８の一環として人間の検閲者に提示される。ドキュメントの集合が分野に分割される場合、各分野からのドキュメントを分類するのに使用されるある最小セットの属性、または好ましいセットの属性を指定する規則、ならびにその他の分野特有の分類規則が、通常、存在する。分類プロセスが完了した時点で、各ドキュメントには、そのドキュメントをナビゲーション状態の集合の中で探し出す１組の用語が関連している。

図１３で、テーブル１８０が、分類されたワインボトルの集合の可能な表現を示している。好ましくは、各エントリには、汎用識別子であることが可能なドキュメント番号１８２、名前１８４、および関連する用語１８６が関連している。名前は、好ましくは、自由テキスト探索エンジンを介するとともに、用語ベースのナビゲーションシステムを介して集合にアクセスできるようにすることが可能な記述情報である。

本発明の別の態様では、知識ベースは、ドキュメントの規範的な表現のカタログも含む。各カタログエントリは、１つまたは複数のドキュメントに関連することが可能な概念上、別個の項目を表わす。カタログにより、その項目に関係する、場合により、複数のソースからの複数のドキュメントからのプロファイル情報の集約が可能になる。例えば、同じワインが２つの取扱業者によって販売されており、１つの取扱業者が醸造年情報および地理的場所情報を提供し、もう１つの取扱業者が、味情報を提供する場合、２つの業者からのその情報をそのタイプのワインに関するカタログエントリにおいて結合することができる。カタログは、重複するプロファイリングをなくすことによって分類プロセスの効率を向上させることもできる。図１２で、カタログ生成ステップ２６０が、分類されたドキュメントをカタログエントリに関連付け、適宜、新しいカタログエントリを生成する。参照を容易にするため、項目は、汎用識別子によってカタログの中で一意的に特定されることが可能である。

知識ベースは、ストアも定義することが可能であり、ストアは、一度に探索可能であるようにグループ化されたドキュメントのサブ集合である。例えば、特定のオンラインワイン商店が、その商店の競合他社によって販売される製品に対応するドキュメントを表示することを、知識ベースがそのようなドキュメントを含んでいる場合でも、望まない可能性がある。この場合、知識ベースは、その商店の競合他社によって販売されるワインを含まないドキュメントのストアを定義することができる。図１２で、ストア生成ステップ２６２が、ドキュメントの属性、用語、または任意の他の特性に基づいてストアを定義することが可能である。ドキュメントは、複数のストアで特定されることが可能である。知識ベースは、特定のストアに合わせてカスタマイズされた属性、または用語も含むことが可能である。

図１２で、エクスポートプロセスステップ２６４が、ナビゲート可能なデータ構造を生成するのに必要なさらなる処理を行うシステム内の別の段階に知識ベースから情報をエクスポートする。

ナビゲーション状態
ナビゲーションシステムは、ナビゲーション状態の集合を明示的、または暗黙的に表わす。このナビゲーション状態は、用語を関係付ける部分的順序から導出された精緻化の部分的順序によって関係付けられる。

ナビゲーション状態は、２つの表現を有する。第１に、ナビゲーション状態は、ドキュメントの集合のサブセットに対応する。第２に、ナビゲーション状態は、１組の互いに比較できない用語に対応する。図１４は、前述したワインの例に基づいてドキュメントおよび用語に関するいくつかのナビゲーション状態を示している。例えば、１つのナビゲーション状態２２４は、｛原産地：南米｝（ドキュメント＃１、＃４、＃５）であり、第２のナビゲーション状態２２４は、｛タイプ／品質もの：白，原産地：米国｝（ドキュメント＃２、＃９）である。各ナビゲーション状態に対応するドキュメントのサブセットは、対応する１組の互いに比較できない用語のなかの用語のすべてに共通で関連するドキュメントを含む。同時に、各ナビゲーション状態に対応する１組の互いに比較できない用語は、ドキュメントのそのサブセットに共通な用語セットからの、すなわち、そのサブセットの中のすべてのドキュメントに共通で関連する用語セットからの最小用語のすべてを含む。各ナビゲーション状態は、好ましくは、一意的に、十分に指定される。すなわち、特定の１組の用語、または所与の１組のドキュメントに関して、対応するナビゲーション状態は１つしか存在しない。

ナビゲーション状態の集合を定義するのに選好される１つのやり方は、規範的な１組の互いに比較できない用語によって各ナビゲーション状態を一意的に特定することである。任意の用語セットを規範的な１組の互いに比較できない用語にマップする２ステップマッピングプロセスにより、この特性を満たす状態が生成される。プロセスの第１のステップで、任意の１組の用語が、その用語のすべてに関連するドキュメントのサブセットにマップされる。あるドキュメントが所与の用語に関連している場合、そのドキュメントは、その所与の用語によって精緻化される用語のすべてにも関連していることを想い起こすと、プロセスの第２のステップで、このサブセットのドキュメントは、そのドキュメントセットのなかのドキュメントのすべてに共通する用語セットの中の最小用語セットにマップされる。この第２のステップから導出された用語セットは、ドキュメントの対応するサブセットを一意的に特定する１組の互いに比較できない用語であり、したがって、ナビゲーション状態の規範的な表現である。例示として、図１４のワインの例を参照すると、用語セット｛原産地：フランス｝が、ドキュメントのサブセット｛ドキュメント＃８、＃１１｝にマップされ、ドキュメントのサブセットは、規範的な用語セット｛タイプ／品種もの：赤，原産地：フランス｝にマップされている。

ナビゲーション状態２２２、２２４、２２６は、用語を関係付ける部分的順序から導出された精緻化関係２２０の部分的順序によって関係付けられている。この部分的順序は、ナビゲーション状態を定義するドキュメントのサブセットまたは用語セットに関して表現することができる。ドキュメントのサブセットに関して表現されると、状態Ａに対応するドキュメントのセットが、状態Ｂに対応するドキュメントのセットのサブセットである場合、ナビゲーション状態Ａにより、ナビゲーション状態Ｂが精緻化される。用語セットに関して表現されると、状態Ｂにおける用語のすべてが、状態Ａの中にある、または状態Ａにおける用語によって精緻化される場合、ナビゲーション状態Ａによってナビゲーション状態Ｂが精緻化される。図１４を参照すると、用語セット｛タイプ／品種もの：赤，原産地：チリ｝（ドキュメント＃４）に対応するナビゲーション状態２２６により、｛原産地：チリ｝（ドキュメント＃４、＃５）に対応するナビゲーション状態２２４が精緻化される。ナビゲーション状態の間の精緻化関係により部分的順序が生じるので、この精緻化関係は、推移的であり、反対称である。例では、｛タイプ／品種もの：赤，原産地：チリ｝（ドキュメント＃４）により、｛原産地：チリ｝（ドキュメント＃４、＃５）が精緻化され、｛原産地：チリ｝（ドキュメント＃４、＃５）により、｛原産地：南米｝（ドキュメント＃１、＃４、＃５）が精緻化され、したがって、｛タイプ／品種もの：赤，原産地：チリ｝（ドキュメント＃４）により、｛原産地：南米｝（ドキュメント＃１，＃４，＃５）が精緻化される。根底ナビゲーション状態２２２は、ドキュメントの集合全体に対応するナビゲーション状態であると定義される。リーフナビゲーション状態２２６は、さらに精緻化することができず、しばしば（ただし、必然的にではなく）、個々のドキュメントに対応するナビゲーション状態であると定義される。根底２２２とリーフ２２６の間に任意の数だけの中間ナビゲーション状態２２４が存在することが可能である。ＢによりＡが精緻化されるナビゲーション状態ＡとＢのペアを所与として、ＡをＢに部分的順序で結合する中間ナビゲーション状態２２４の複数のパスが存在することが可能である。定義の便宜上、本明細書で説明する実施形態に関しては、ナビゲーションは、自らを精緻化するものと考える。

ユーザは、通常、根底ナビゲーション状態２２２から開始して一連の１つまたは複数のナビゲーション状態を訪れることによってドキュメントの集合をブラウズする。それらの状態の間でナビゲーションの３つの基本モードが存在する。第１のモードは、精緻化であり、つまり現在のナビゲーション状態から、現在のナビゲーション状態を精緻化するナビゲーション状態に移動することである。ユーザは、現在のナビゲーション状態に用語を追加することによるか、または現在のナビゲーション状態における用語を精緻化する、すなわち、用語をその用語の精緻化で置き換えることによって精緻化を行うことができる。ユーザが用語を追加した、または精緻化した後、前述した２ステップマッピングに従って新たな用語セットを規範的な用語セットにマップすることができる。第２のモードは、一般化であり、つまり、現在のナビゲーション状態から現在のナビゲーション状態よりも一般的なナビゲーション状態に移動することである。ユーザは、現在のナビゲーション状態から用語を取り除くことによるか、または現在のナビゲーション状態における用語を一般化する、すなわち、現在の用語によって精緻化される用語で現在の用語を置き換えることによって一般化を行うことができる。ユーザが用語を取り除いた後、または一般化した後、新しい用語セットを規範的な用語セットにマップすることができる。第３のモードは、やはり規範的な用語セットにマップしてナビゲーション状態を得ることができる所望の用語セットの形態でクエリを生成することである。

実施形態
知識ベースは、本発明を実施するためにナビゲート可能なデータ構造に移される。ナビゲーション状態は、完全にあらかじめ計算すること、ランタイムに動的に計算すること、または部分的にあらかじめ計算することができる。キャッシュを使用して、ナビゲーション状態の冗長な計算を回避することができる。

好ましい実施形態では、ナビゲーション状態の集合をグラフとして、好ましくは、ラベル付きのエッジを有する有向の非輪状マルチグラフとして表わすことができる。グラフは、各エッジが１対のノードをリンクするノードおよびエッジから成る組合せの構造である。エッジによってリンクされた２つのノードは、端点と呼ばれる。本発明に関して、ノードは、ナビゲーション状態に対応し、エッジは、１つのナビゲーション状態から別のナビゲーション状態に精緻化する遷移を表わす。精緻化は、方向を有するので、各エッジは、より一般的なノードから、そのノードを精緻化するノードに向けられる。ナビゲーション状態に関して部分的順序が存在するため、グラフにおいて有向サイクルが存在する可能性はない。すなわち、グラフは、非輪状である。好ましくは、グラフは、マルチグラフである。というのは、マルチグラフにより、複数のエッジが所与の１対のノードに結合する可能性が許されるからである。各エッジには、用語でラベルが付けられる。各エッジは、より一般的な端点の用語セットから開始して、エッジ用語を追加し、２ステップマップを使用してその用語セットを規範的な形態にすることが、他方の端点であるナビゲーション状態をもたらす精緻化につながるという特性を有する。つまり、各エッジは、単一の用語の追加に基づくノード間の精緻化遷移を表わす。

グラフの構造を理解するために以下の定義が役立つ。すなわち、子孫、祖先、最小共通祖先（ＬＣＡ）、固有祖先（ｐｒｏｐｅｒ ａｎｃｅｓｔｏｒ）、固有子孫（ｐｒｏｐｅｒ ｄｅｓｃｅｎｄａｎｔ）、および最大下界（ＧＬＢ,greatest lower bound）である。以上の定義は、用語の間、およびノードの間の精緻化の部分的順序に適用される。ＡおよびＢが用語であり、ＢによってＡが精緻化される場合、Ｂは、Ａの子孫であると言われ、Ａは、Ｂの祖先であると言われる。さらに、ＡとＢが別々の用語である場合、Ｂは、Ａの固有子孫であると言われ、Ａは、Ｂの固有祖先であると言われる。ＡとＢがともにノードである場合も、同じ定義が適用される。

ＣがＡの祖先であり、Ｃは、Ｂの祖先でもある場合、Ｃは、ＡとＢの共通祖先であると言われ、ただし、Ａ、Ｂ、およびＣは、すべて用語であるか、またはすべてノードである。ＡとＢの共通祖先のセットの最小要素は、最小共通祖先（ＬＣＡ）と呼ばれる。１対の比較できない祖先を有する用語が存在しない場合、２つの用語の、または２つのノードのＬＣＡは、固有である。例えば、原産地：アルゼンチンと原産地：チリのＬＣＡは、図１１Ｂの用語１１０の部分的順序における原産地：南米である。ただし、一般に、所与の１組の用語またはノードに関して１組のＬＣＡが存在する可能性がある。

グラフにおけるノードの計算は、好ましくは、ボトムアップ式で行われる。グラフの中のリーフノード、つまりリーフナビゲーション状態に対応するノードは、分類されたドキュメントから直接に計算することができる。通常、ただし、必然的にではなく、リーフノードは、単一のドキュメントを含むセットに対応する。残りのリーフでないノードは、リーフノードのＬＣＡ閉包（ｃｌｏｓｕｒｅ）、すなわち、リーフノードのサブセットのＬＣＡであるノードのすべてを計算することによって得られる。

グラフのエッジは、表記法の都合上、Ｒファンクションと呼ぶ精緻化ファンクションに従って決定される。Ｒファンクションは、ＡがＢの固有祖先である２つのノード、ＡおよびＢを引数としてとり、用語ＣがＲ（Ａ，Ｂ）の中にある場合、用語Ｃを使用してノードＡを精緻化することにより、Ａの固有子孫であり、Ｂの（必ずしも固有ではない）祖先であるノードがもたらされるように最小用語セットを戻す。例えば、図１４で、Ｒ（｛タイプ／品種もの：赤｝，｛タイプ／品種もの：メルロー，原産地：アルゼンチン，醸造年：１９８８｝）＝｛タイプ／品種もの：メルロー，原産地：南米，醸造年：１９８８｝である。Ｂ_１がＢ_２の祖先である場合、ＡがＢ_１とＢ_２の両方の固有祖先であると想定すると、Ｒ（Ａ，Ｂ_１）は、Ｒ（Ａ，Ｂ_２）のサブセットである。例えば、Ｒ（｛タイプ／品種もの：赤｝，｛タイプ／品種もの：赤，原産地：南米｝）＝｛原産地：南米｝である。

グラフにおいて、ノードＡとＢの間のエッジは、Ｒ（Ａ，Ｂ）の中の用語のサブセットに対応する。また、単一の祖先ノードＡからの２つのエッジが、精緻化のために同一の用語を使用することはない。ノードＡが、子孫ノード｛Ｂ_１，Ｂ_２，．．．｝の集合を有し、用語Ｃが、Ｒ（Ａ，Ｂ_ｉ）のすべての中にあるようになっている場合、用語Ｃを有するノードＡからのエッジだけが、ＬＣＡ（Ｂ_１，Ｂ_２，．．．）に向かい、ＬＣＡ（Ｂ_１，Ｂ_２，．．．）は、Ｂ_ｉの間の唯一の最大ノードであることが保証される。図１４で、例えば、用語、原産地：南米を有するノード｛タイプ／品種もの：赤｝からのエッジが、そのノードの固有子孫｛タイプ／品種もの：メルロー，原産地：南米，醸造年：１９９８｝および｛タイプ／品種もの：赤，原産地：チリ｝にではなく、ノード｛タイプ／品種もの：赤，原産地：南米｝に向かう。グラフのＬＣＡ閉包特性により、Ｂ_ｉの間の唯一の最大ノードの存在が確実になる。したがって、各エッジは、ノード−用語ペアをそのノードの固有子孫に一意的にマップする。

グラフのＬＣＡ閉包により、所与の用語セットＳに関して、用語セットがＳを精緻化するノードのセットは、唯一の最大ノードを有するという役立つ特性がもたらされる。このノードは、Ｓの最大下界（ＧＬＢ）と呼ばれる。

グラフは、明示的に計算し、組合せのデータ構造の中に記憶することができる。グラフは、ノードおよびエッジの明示的な表現を必ずしも含まない構造の中で暗黙的に表現することができる。あるいは、グラフは、以上の戦略を組み合わせる方法を使用して表わすことができる。ナビゲーションシステムは、通常、ドキュメントの大きな集合を対象に動作するため、グラフは、スケーラブルな方法によって表わされることが好ましい。

グラフは、リーフノードのすべての可能なサブセットのＬＣＡを計算することによって得ることができる。ただし、そのような手法は、リーフノードの数を指数関数的に増加させ、本来的にスケーラブルではない。ＬＣＡ閉包を得るための代替の戦略は、グラフの中のノードのすべてのペアを繰返し考慮し、各ペアのＬＣＡがグラフの中にあるかどうかを検査し、そのＬＣＡを必要に応じてグラフに追加することである。この戦略は、前の戦略からは相当に改良されているが、依然として、比較的スケーラブルではない。

ノードをあらかじめ計算するより効率的なやり方は、ドキュメントセットを順次に処理し、各ドキュメントに関するノードを計算し、そのノードを、ＬＣＡ閉包を維持するのに必要な他のノードが存在すればそれらのノードとともに、グラフに追加することである。システムは、ノードおよびエッジを有向の非輪状マルチグラフとして記憶する。グラフは、空の用語セットに対応する単一のノード、根底ノードを含むように初期設定される。図１５を参照すると、新しいノードをグラフに挿入するためのプロセス２３０において、ステップ２３２で、既存のノードに対応しないグラフに挿入されるべきそれぞれの新しいドキュメントに関して、システムが、新しいノードを生成する。ステップ２３４で、新しいノードをグラフに挿入する前に、システムは、根底ノード（または祖先ノード）と新しいノードの間で欠落しているＬＣＡノードが存在すれば、そのＬＣＡノードを再帰的に生成し、挿入する。各回のノード挿入後のＬＣＡ閉包を確実にするため、システムは、ドキュメントノードを最後に、そのノードの固有祖先であるすべての他のノードを挿入した後に、ステップ２３６および２３８で挿入する。

新しいノードを挿入することは、ステップ２３６で、祖先からそのノードに、ステップ２３８で、その新しいノードからの子孫に、適切なエッジを追加することを必要とする。ノードに入るエッジは、好ましくは、新しいノードに入る精緻化用語を有し、新しいノードの中間祖先につながるエッジ上で使用される精緻化用語を既に有してはいない祖先を特定することによって決められる。ノードから出るエッジは、好ましくは、新しいノードのＧＬＢを計算し、新しいノードからＧＬＢに、またＧＬＢがエッジを向けているノードにエッジを適切に追加することによって決められる。

グラフ全体が、集合の中の各ドキュメントに関する前述した手続きに従うことにより、あらかじめ計算されることが可能である。グラフをあらかじめ計算することは、グラフのサイズが扱いやすい場合、またはユーザが、すべてのナビゲーション状態を等しい確率で訪れる可能性が高い場合、好ましい可能性がある。ただし、実際には、ユーザは、通常、一部のナビゲーション状態をその他のナビゲーション状態よりも頻繁に訪れる。実際、グラフが大きくなるにつれ、一部のナビゲーション状態は、決して訪問されない可能性がある。残念ながら、ナビゲーション状態が訪問される頻度の信頼できる予測は、困難である。

ナビゲーション状態をあらかじめ計算する代替の戦略は、ナビゲーション状態が動的に計算されることを可能にする索引を生成することである。具体的には、各ドキュメントに、そのドキュメントに関連する用語のすべてで、またはそのドキュメントに関連する精緻化を有する用語のすべてで索引を付けることができる。結果の索引のサイズは、一般に、ナビゲーション状態のグラフを記憶するデータ構造よりもはるかに小さい。この動的手法は、スペースと事前計算時間を節約する可能性があるが、オペレーションに関するより長い応答時間、またはより高い計算要件という代償を払ってそうする。動的実施形態は、所与のナビゲーション状態からのすべての精緻化用語を戻すＲファンクションの１引数バージョン、ならびに用語セットのＧＬＢを計算するための手続きを使用することができる。

また、ナビゲーション状態のサブセットをあらかじめ計算することも可能である。動的に計算するのにかかる費用が最も高い状態をあらかじめ計算することが好ましい。例えば、ある状態がドキュメントの大きなサブセットに対応する場合、そのサブセットをあらかじめ計算することが好ましい可能性がある。１つの可能な部分的事前計算の手法では、しきい値サイズを越えるドキュメントのサブセットに対応するすべてのナビゲーション状態が、あらかじめ計算されることが可能である。また、ある状態をあらかじめ計算することは、その状態が頻繁に訪問される場合も好ましい。一部の場合、ナビゲーション状態が訪問される頻度を予測できる可能性がある。ナビゲーション状態が訪問される頻度をあらかじめ予測することができない場合でも、動的計算の結果をキャッシュに入れることにより、絶え間なく再計算する必要性を減らすことができる。最後に訪問された状態、または最も頻繁に訪問された状態をキャッシュに入れることが可能である。

インターフェースに関連して前述したとおり、システムは、３つの種類のクエリオペレーション、すなわち、精緻化、一般化、および１組の用語を指定することによるクエリをサポートする。以上のオペレーションをグラフに関連してさらに説明することができる。クエリ精緻化に関して、システムは、現在のナビゲーション状態に対応するノードからのエッジ上にある用語を列挙する。ユーザが精緻化のための用語を選択した場合、システムは、エッジがつながる先のノードを提示することで応答する。同様に、クエリ一般化オプションに関して、システムは、現在のナビゲーション状態に対応するノードにつながる（そのノードからではない）エッジを列挙し、選択する。代替として、クエリ一般化は、１組の用語を指定することによるクエリの特殊ケースとして実施することもできる。１組のキーワードを指定することによるクエリに関して、システムは、所与の用語セットに対応する仮想ノードを生成し、グラフの中で仮想ノードのＧＬＢを決定する。ＧＬＢが見付からなかった場合、そのクエリを満たすドキュメントは存在しない。見付かった場合、ＧＬＢノードは、すべてのドキュメントがそのクエリを満たすナビゲーション状態に対応するグラフの中の最も一般的なノードである。

本発明のナビゲーションシステムにより、情報プロバイダが、ナビゲーションシステムをドキュメントの任意の集合の上に被せることが可能になる。本発明の知識ベースの態様、およびナビゲーションの態様は、異なるプロバイダによって独立に行われることが可能であり、情報プロバイダは、これらの機能を別個のエンティティに外部委託することができる。同様に、一般化された知識ベースが、ナビゲーション専門家によってインポートされることが可能である。また、情報プロバイダは、このナビゲーション要件をナビゲーションシステムプロバイダに外部委託することもできる。ナビゲーションシステムプロバイダは、使用の量とは独立に、システムに関するライセンス料金を顧客に課金することが可能である。代替として、ナビゲーションシステムプロバイダは、１クリック当たりで、製品がシステムを介して入手可能な場合、１回の購入当たりで、あるいはナビゲーションシステムを介してクリックから生成された１回のトランザクション当たりで、顧客に課金することも可能である。また、ナビゲーションシステムプロバイダは、いくつかのソースからの記録をまとめ、その記録を結合してグローバルデータセットにし、そのデータセットを探索するナビゲーションシステムを生成する集約者（ａｇｇｒｅｇａｔｏｒ）として機能することも可能である。

また、本発明によるナビゲーションシステムにより、ユーザプロファイリング能力、およびマーチャンダイジング（ｍｅｒｃｈａｎｄｉｓｉｎｇ）能力が強化されることも可能である。ナビゲーションシステムは、ナビゲーション状態の集合を探査するのに選択された特定のパスを含め、ユーザの選択に基づいてユーザのプロファイルを保持することができる。知識ベースを使用して、システムは、関係するドキュメントに関する情報、知識ベースの中の属性および用語で選択情報を補足することにより、ユーザの選好および関心に関するさらなる情報を推測することもできる。ユーザの関心対象のドキュメントに関係する品物およびサービスを販売するのに、その情報を使用することができる。

以上の説明は、本発明の特定の実施形態を対象としてきた。本発明は、本発明の趣旨および範囲を逸脱することなく、その他の特定の形態で実施することも可能である。本明細書で使用した実施形態、図、用語、および例は、参考および例示としてだけのものであり、限定するものではない。本発明の範囲は、頭記の特許請求の範囲によって示され、特許請求の範囲と等価の意味および範囲に入るすべての変更は、特許請求の範囲に包含されるものとする。

本発明の実施形態によるナビゲーションシステムに対するユーザインターフェースを示す図である。 ナビゲート可能な用語のドロップダウン選出リストを示す図１のユーザインターフェースの図である。 ナビゲーション状態を示す図１のユーザインターフェースの図である。 ナビゲーション状態を示す図１のユーザインターフェースの図である。 ナビゲーション状態を示す図１のユーザインターフェースの図である。 ナビゲーション状態を示す図１のユーザインターフェースの図である。 ナビゲーション状態を示す図１のユーザインターフェースの図である。 ナビゲーション状態を示す図１のユーザインターフェースの図である。 用語に関する自由テキスト探索の結果を示す図１のユーザインターフェースの図である。 特定のドキュメントについての情報を示す図１のユーザインターフェースの図である。 図１１Ａは、本発明の実施形態によるどのように属性に関する値の範囲に部分的に順序付けを行うことができるかの代表例である。図１１Ｂは、本発明の実施形態によるどのように属性に関する値の範囲に部分的に順序付けを行うことができるかの代表例である。図１１Ｃは、本発明の実施形態によるどのように属性に関する値の範囲に部分的に順序付けを行うことができるかの代表例である。 本発明の実施形態によるドキュメントを収集し、分類するためのプロセスを示すブロック図である。 本発明の実施形態によるどのように１組のドキュメントを分類することができるかを示すテーブルである。 本発明の実施形態によるナビゲーション状態の代表的な部分的順序を示す図である。 本発明の実施形態によるナビゲーション状態をあらかじめ計算するためのプロセスを示すブロック図である。

Claims (84)

1. 資料のセットに関するナビゲーションシステムであって、
   前記資料を特徴付ける複数の属性と、
   前記属性の少なくとも１つにそれぞれが関連しており、各関連が属性−値ペアを定義し、前記属性−値ペアのいくつかが、前記属性−値ペアのその他を精緻化する前記資料を記述する複数の値と、
   属性−値ペアの特定のセット、および前記資料の特定のサブセットにそれぞれ対応する複数のナビゲーション状態と、
   前記ナビゲーション状態の２つの間の直接パスをそれぞれが提供する複数の遷移を提供するインターフェースであって、
   各遷移が、元のナビゲーション状態に対応する属性−値のセットから、宛先ナビゲーション状態に対応する属性−値のセットへの変化を表わし、一連の１つまたは複数の遷移が、任意の２つのナビゲーション状態の間のパスを提供し、前記ナビゲーション状態の少なくとも第１の状態と前記ナビゲーション状態の第２の状態の間で複数のパスが存在するインターフェースとを含むシステム。
2. 元のナビゲーション状態から宛先ナビゲーション状態への前記遷移の少なくとも１つが、前記元のナビゲーション状態に関する属性−値ペアの対応するセットのうち１つのペアの値の精緻化を表わす請求項１に記載のナビゲーションシステム。
3. 元のナビゲーション状態から宛先ナビゲーション状態への前記遷移の少なくとも１つが、前記元のナビゲーション状態に関する属性−値ペアの対応するセットのうち１つのペアの値の一般化を表わす請求項１に記載のナビゲーションシステム。
4. 元のナビゲーション状態から宛先ナビゲーション状態への前記遷移の少なくとも１つが、前記元のナビゲーション状態に関する属性−値ペアの対応するセットのうち１つのペアの属性の選択解除を表わす請求項１に記載のナビゲーションシステム。
5. 元のナビゲーション状態から第１の宛先ナビゲーション状態への遷移のうち第１の遷移が、第１の属性に対応する属性−値ペアの選択を表わし、前記元のナビゲーション状態から第２のナビゲーション状態への遷移のうち第２の遷移が、第２の属性に対応する属性−値ペアの選択を表わす請求項１に記載のナビゲーションシステム。
6. 元のナビゲーション状態から宛先ナビゲーション状態への遷移のうち少なくとも１つが、前記元のナビゲーション状態に対応する属性−値ペアのセットの中に対応する属性−値ペアが存在しない属性に対応する属性−値ペアの指定を表わす請求項１に記載のナビゲーションシステム。
7. 元のナビゲーション状態が、資料の前記セットの１つに対応し、前記元のナビゲーション状態から宛先ナビゲーション状態への遷移の少なくとも１つが、前記ナビゲーション状態に関連する特定の属性−値ペアの選択を表わしている請求項１に記載のナビゲーションシステム。
8. 前記複数の属性の少なくとも１つに関連する値が、明示的に定義される請求項１に記載のナビゲーションシステム。
9. 前記複数の属性の少なくとも１つに関連する値が、暗黙的に定義される請求項１に記載のナビゲーションシステム。
10. 共通の属性を共有する属性−値ペアに関して、複数の互いに比較できない属性−値ペアを精緻化する属性−値ペアが存在しない請求項１に記載のナビゲーションシステム。
11. 共通の属性を共有する属性−値ペアに関して、少なくとも１つの属性−値ペアによって複数の互いに比較できない属性−値ペアが精緻化される請求項１に記載のナビゲーションシステム。
12. 複数の互いに比較できない属性−値ペアを精緻化する属性−値ペアが存在しない請求項１に記載のナビゲーションシステム。
13. 少なくとも１つの属性−値ペアによって複数の互いに比較できない属性−値ペアが精緻化される請求項１に記載のナビゲーションシステム。
14. 異なる属性に対応する任意の２つの属性−値ペアに関して、前記２つの属性−値ペアが比較できない請求項１に記載のナビゲーションシステム。
15. 資料の前記セットが、単一の主題領域に関係する資料を含む請求項１に記載のナビゲーションシステム。
16. 資料の前記セットが、複数の主題領域に関係する資料を含む請求項１に記載のナビゲーションシステム。
17. 資料の前記セットが、前記資料のサブセットを含み、前記サブセットが、一体としてナビゲート可能であり、資料の前記セットの中の資料の一部分が、前記サブセットに割り当てられている請求項１に記載のナビゲーションシステム。
18. 前記インターフェースが、資料の前記サブセットに関係する複数の遷移を提供するように適合された請求項１７に記載のナビゲーションシステム。
19. 資料の前記セットが、それぞれ独立に一体としてナビゲート可能である複数のサブセットを含み、資料の前記セットの中の資料の一部分が、各サブセットに割り当てられており、前記資料の少なくとも１つが、複数のサブセットに割り当てられている請求項１７に記載のナビゲーションシステム。
20. 資料の前記セットの中の資料のそれぞれに関するプロファイルをさらに含み、前記プロファイルが、属性−値ペアのセットを含む請求項１に記載のナビゲーションシステム。
21. 前記プロファイルが、記述情報をさらに含む請求項２０に記載のナビゲーションシステム。
22. 前記インターフェースが、人間ユーザインターフェースを含む請求項１に記載のナビゲーションシステム。
23. 前記インターフェースが、アプリケーションプログラムインターフェースを含む請求項１に記載のナビゲーションシステム。
24. 前記インターフェースが、Ｗｏｒｌｄ Ｗｉｄｅ Ｗｅｂベースの環境において動作可能である請求項１に記載のナビゲーションシステム。
25. 前記インターフェースが、ＸＭＬベースの環境において動作可能である請求項１に記載のナビゲーションシステム。
26. 前記インターフェースが、独立のデータ指向プログラムの機能を補足する請求項１に記載のナビゲーションシステム。
27. 前記インターフェースが、前記複数のナビゲーション状態の間の前記複数の遷移に基づく現在のナビゲーション状態からのナビゲーションを可能にするための誘導された探索ツールを含む請求項１に記載のナビゲーションシステム。
28. 前記インターフェースが、前記属性を探索するための自由テキスト探索ツールを含む請求項２７に記載のナビゲーションシステム。
29. 前記インターフェースが、前記値を探索するための自由テキスト探索ツールを含む請求項２７に記載のナビゲーションシステム。
30. 資料の前記セットの中の資料のそれぞれに関するプロファイルをさらに含み、前記プロファイルが、記述情報を含み、前記インターフェースが、前記プロファイルの中の前記記述情報を探索するための自由テキスト探索ツールを含む請求項２７に記載のナビゲーションシステム。
31. 前記インターフェースが、資料の前記セットの中の資料へのアクセスを含む請求項２７に記載のナビゲーションシステム。
32. 前記インターフェースが、前記現在のナビゲーション状態に対応する属性−値ペアの提示を含む請求項２７に記載のナビゲーションシステム。
33. 前記現在のナビゲーション状態に対応する属性−値ペアの前記提示が、ユーザによって選択された属性−値ペア、および推測された属性−値ペアを含み、前記インターフェースが、ユーザによって選択された属性−値ペアおよび推測された属性−値ペアの指示を含む請求項３２に記載のナビゲーションシステム。
34. 前記現在のナビゲーション状態に対応する属性−値ペアの前記提示が、互いに比較できない属性−値ペアだけを含む請求項３２に記載のナビゲーションシステム。
35. 前記提示が、前記現在のナビゲーション状態に対応する属性−値ペアを属性によって編成する請求項３２に記載のナビゲーションシステム。
36. 前記提示が、前記現在のナビゲーション状態に対応する属性−値ペアをより一般的な属性−値ペアによって編成する請求項３２に記載のナビゲーションシステム。
37. 前記誘導された探索ツールが、前記現在のナビゲーション状態からの選択に関するナビゲーションオプションの提示を含み、前記オプションが、前記現在のナビゲーション状態からの遷移に対応する請求項２７に記載のナビゲーションシステム。
38. 前記ナビゲーションオプションが、前記現在のナビゲーション状態に対応する属性−値ペアの精緻化である属性−値ペアを含む請求項３７に記載のナビゲーションシステム。
39. 前記オプションが、前記属性の１つにそれぞれが対応する属性−値ペアの１組のリストの提示を含み、リストが、前記現在のナビゲーション状態に対応する属性−値ペアを精緻化する属性−値ペアを含み、一部のリストが、前記現在のナビゲーション状態に対応する属性−値ペアと比較できない属性−値ペアを含む請求項３８に記載のナビゲーションシステム。
40. 前記提示が、前記ナビゲーションオプションを属性によって編成する請求項３７に記載のナビゲーションシステム。
41. 前記提示が、前記ナビゲーションオプションをより一般的な属性−値ペアによって編成する請求項３７に記載のナビゲーションシステム。
42. 前記ナビゲーションオプションが、前記現在のナビゲーション状態に対応する属性−値ペアと比較できない属性−値ペアを含む請求項３７に記載のナビゲーションシステム。
43. 前記ナビゲーションオプションが、前記現在のナビゲーション状態に対応する属性−値ペアの一般化である属性−値ペアを含む請求項３７に記載のナビゲーションシステム。
44. 前記ナビゲーションオプションが、前記現在のナビゲーション状態に対応する属性−値ペアのセットからの属性−値ペアの選択解除を含む請求項３７に記載のナビゲーションシステム。
45. 前記ナビゲーションオプションが、関連するナビゲーション状態へのリンクをさらに含む請求項３７に記載のナビゲーションシステム。
46. 前記関連するナビゲーション状態が、前記現在のナビゲーション状態の一般化である請求項４５に記載のナビゲーションシステム。
47. 前記関連するナビゲーション状態が、前記現在のナビゲーション状態の精緻化である請求項４５に記載のナビゲーションシステム。
48. 前記リンクが、２つまたはそれより多くの遷移のパスに対応する請求項４５に記載のナビゲーションシステム。
49. 資料のセットに関する分類法を定義するための方法であって、
    資料の前記セットの中の資料を特徴付ける複数の属性を定義するステップと、
    資料の前記セットの中の資料を記述する複数の値を定義するステップであって、
    前記値のそれぞれが、前記属性の少なくとも１つに対する関連を有し、各関連が、属性−値ペアを定義するステップと、
    前記属性−値ペアの間の精緻化関係の階層を定義するステップであって、
    前記階層が、前記属性−値ペアの間の部分的順序を定義し、前記複数の属性の少なくとも１つに関して、前記階層が、根底レベルからの複数の精緻化レベルを含むステップとを含む方法。
50. 資料のセットを分類するための方法であって、
    資料の前記セットの中の資料を特徴付ける複数の属性を定義するステップと、
    資料の前記セットの中の資料を記述する複数の値を定義するステップであって、
    前記値が、前記属性の少なくとも１つに対する関連を有し、各関連が、属性−値ペアを定義するステップと、
    前記属性−値ペアの間の精緻化関係の階層を定義するステップであって、
    前記階層が、前記属性−値ペアの間の部分的順序を定義し、前記複数の属性の少なくとも１つに関して、前記階層が、根底レベルからの複数の精緻化レベルを含むステップと、
    前記資料のそれぞれを属性−値ペアのセットに関連付けることによって前記資料のそれぞれに関するプロファイルを定義するステップとを含む方法。
51. 前記資料のそれぞれに関するプロファイルを定義するステップが、前記資料のそれぞれを属性−値ペアの限定されたサブセットからの少なくとも１つの属性−値ペアに関連付けるステップを含む請求項５０に記載の方法。
52. 属性−値ペアの前記制限されたサブセットが、１つの属性に対応する属性−値ペアから成る請求項５１に記載の方法。
53. 前記資料のそれぞれに関するプロファイルを定義するステップが、前記資料の一部を属性−値ペアの限定されたサブセットからの１つだけの属性−値ペアに関連付けるステップを含む請求項５０に記載の方法。
54. 属性−値ペアの前記限定されたサブセットが、１つの属性に対応する属性−値ペアから成る請求項５３に記載の方法。
55. 前記資料のそれぞれに関するプロファイルを定義するステップが、前記資料の一部を属性−値ペアに関連付けて、第１の属性−値ペアに対する関連が、第２の属性−値ペアに対する関連を暗黙指定するようにする請求項５０に記載の方法。
56. 前記資料のそれぞれに関するプロファイルを定義するステップが、前記資料のそれぞれを記述情報に関連付けるステップを含む請求項５０に記載の方法。
57. 資料のセットに対して動作する情報ナビゲーションシステムのための知識ベースであって、
    前記資料を特徴付ける複数の属性と、
    前記属性の１つまたは複数に対する関連をそれぞれが有する前記資料を記述する複数の値であって、
    各関連が、属性−値ペアを定義する値と、
    前記属性−値ペアの間の部分的順序を定義する前記属性−値ペアの間の精緻化関係の階層であって、
    前記複数の属性の少なくとも１つに関して、根底レベルからの複数の精緻化レベルを含む階層と、
    属性−値ペアのセットを含む前記資料のそれぞれに関するプロファイルとを含む知識ベース。
58. 分類規則のセットをさらに含む請求項５７に記載の知識ベース。
59. 分類プロセスに関するデフォルトの見込みのセットをさらに含む請求項５７に記載の知識ベース。
60. 資料の前記セットの中のサブセットの定義のセットをさらに含む請求項５７に記載の知識ベース。
61. ナビゲーション規則のセットをさらに含む請求項５７に記載の知識ベース。
62. 複数の属性が資料を特徴付け、複数の値が前記資料を記述し、前記値のそれぞれが、前記属性の少なくとも１つに対する関連を有し、各関連が、属性−値ペアを定義し、前記属性−値ペアの一部が、前記属性−値ペアのその他を精緻化するユーザが前記資料のセットをブラウズすることを可能にするための方法であって、
    属性−値ペアの特定のセットおよび前記資料の特定のサブセットにそれぞれが対応する複数のナビゲーション状態を定義するステップと、
    前記ナビゲーション状態の２つの間の直接パスをそれぞれが提供する複数の遷移を提供するインターフェースを提供するステップであって、
    各遷移が、元のナビゲーション状態に対応する属性−値ペアのセットから宛先ナビゲーション状態に対応する属性−値ペアのセットへの変化を表わし、一連の１つまたは複数の遷移が、任意の２つのナビゲーション状態の間のパスを提供し、前記ナビゲーション状態の少なくとも第１の状態と前記ナビゲーション状態の第２の状態の間で複数のパスが存在するステップと、
    選択のために遷移の表示を提供するステップと、
    遷移の選択を受け入れるステップと、
    前記選択された遷移に関連する結果のナビゲーション状態を獲得するステップと、
    前記結果のナビゲーション状態の中で遷移の改訂された表示を選択のために提供するステップとを含む方法。
63. 選択のために遷移の表示を提供するステップは、属性−値ペアの表示を提供するステップを含む請求項６２に記載の方法。
64. 遷移の選択を受け入れるステップは、属性−値ペアの選択を受け入れるステップを含む請求項６２に記載の方法。
65. 遷移の改訂された表示を提供するステップは、属性−値ペアの改訂されたセットの表示を提供するステップを含む請求項６２に記載の方法。
66. 属性−値ペアの改訂されたセットの表示を提供するステップは、前に選択された属性−値ペアに関して、精緻化する属性−値ペアのセットの表示を提供するステップを含む請求項６５に記載の方法。
67. 属性−値ペアの前記選択を受け入れるステップは、結果のナビゲーション状態を獲得するステップをトリガする請求項６４に記載の方法。
68. 表示を提供するステップは、属性−値ペアを属性によって編成するステップを含む請求項６３に記載の方法。
69. 属性−値ペアの改訂されたセットの表示を提供するステップは、前記属性−値ペアをより一般的な属性−値ペアによって編成するステップを含む請求項６５に記載の方法。
70. 改訂された表示を提供するステップは、前記表示の中で前に示されていなかった属性を追加するステップを含む請求項６２に記載の方法。
71. 追加の選択された属性−値ペアを受け入れるステップと、
    前記選択された属性−値ペアおよび前記追加の選択された属性−値ペアに関連する追加の結果のナビゲーション状態を獲得するステップとをさらに含む請求項６２に記載の方法。
72. 前記追加の選択された属性−値ペアが、前記選択された属性−値ペアとは異なる属性に関連する請求項７１に記載の方法。
73. 前に選択された属性−値ペアのリストを表示するステップをさらに含む請求項６２に記載の方法。
74. 選択された属性−値ペアの選択解除を受け入れるステップと、
    改訂された結果のナビゲーション状態を獲得するステップとをさらに含む請求項７３に記載の方法。
75. 複数の属性が資料を特徴付け、複数の値が前記資料を記述し、前記値のそれぞれが、前記属性の少なくとも１つに対する関連を有し、各関連が、属性−値ペアを定義し、前記属性−値ペアの一部が、前記属性−値ペアのその他を精緻化し、複数のナビゲーション状態のそれぞれが、特定の属性−値ペアのセットおよび資料の特定のサブセットに対応し、インターフェースが、複数の遷移を提供し、各遷移が、前記ナビゲーション状態の２つの間で直接パスを提供し、各遷移が、元のナビゲーション状態に対応する属性−値ペアのセットから宛先ナビゲーション状態に対応する属性−値ペアのセットへの変化を表わし、一連の１つまたは複数の遷移が、任意の２つのナビゲーション状態の間のパスを提供し、前記ナビゲーション状態の少なくとも第１の状態と前記ナビゲーション状態の第２の状態の間で複数のパスが存在するユーザが前記資料のセットをブラウズすることを可能にするための方法であって、
    自由テキスト探索ボックスを表示するステップと、
    前記自由テキスト探索ボックスの中に入力された探索用語を受け入れるステップと、
    前記探索用語にマッチする属性−値ペアを特定するステップと、
    前記探索用語に対する前記マッチする属性−値ペアを表示するステップと、
    マッチする属性−値ペアの選択を受け入れるステップと、
    前記マッチする属性−値ペアの前記選択に対応するナビゲーション状態を入力するステップとを含む方法。
76. 複数の属性が資料を特徴付け、複数の値が前記資料を記述し、前記値のそれぞれが、前記属性の少なくとも１つに対する関連を有し、各関連が、属性−値ペアを定義し、前記属性−値ペアの一部が、前記属性−値ペアのその他を精緻化し、複数のナビゲーション状態のそれぞれが、特定の属性−値ペアのセットおよび資料の特定のサブセットに対応し、インターフェースが、複数の遷移を提供し、各遷移が、前記ナビゲーション状態の２つの間で直接パスを提供し、各遷移が、元のナビゲーション状態に対応する属性−値ペアのセットから宛先ナビゲーション状態に対応する属性−値ペアのセットへの変化を表わし、一連の１つまたは複数の遷移が、任意の２つのナビゲーション状態の間のパスを提供し、前記ナビゲーション状態の少なくとも第１の状態と前記ナビゲーション状態の第２の状態の間で複数のパスが存在する前記資料のセットに対して動作するナビゲーションシステムのためのナビゲーション状態に対応するノードとナビゲーション状態間の遷移に対応するエッジを含むナビゲート可能なデータ構造を生成するための方法であって、
    既に前記ナビゲート可能なデータ構造の中に存在してはいない資料の前記セットの中の資料のそれぞれに関する新しいノードを生成するステップと、
    前記新しいノード、および前記ナビゲート可能なデータ構造の中に既に存在する各ノードに関して最小共通祖先を前記データ構造の中に挿入することを、そのような最小共通祖先が前記データ構造の中に既に存在しているのでない限り行うステップと、
    各新しいノードに関して、前記ノードの中にエッジを追加することによって前記ノードを挿入するステップとを含む方法。
77. 資料のセットと、前記資料を特徴付ける複数の属性と、属性−値ペアの一部が前記属性−値ペアのその他を精緻化する前記属性−値ペアをそれぞれが定義する前記属性の少なくとも１つに対する関連をそれぞれが有する前記資料を記述する複数の値と、属性−値ペアの特定のセットおよび前記資料の特定のサブセットにそれぞれが対応する複数のナビゲーション状態とを含む情報ナビゲーションシステムを提供するための方法であって、
    前記ナビゲーション状態を計算するステップと、
    前記ナビゲーション状態をデータ構造の中に記憶するステップと、
    前記ナビゲーション状態の２つの間で直接パスをそれぞれが提供する複数の遷移を提供する前記情報ナビゲーションシステムに対するインターフェースを提供するステップであって、
    各遷移が、元のナビゲーション状態に対応する属性−値ペアのセットから宛先ナビゲーション状態に対応する属性−値ペアのセットへの変化を表わし、一連の１つまたは複数の遷移が、任意の２つのナビゲーション状態の間のパスを提供し、前記ナビゲーション状態の少なくとも第１の状態と前記ナビゲーション状態の第２の状態の間で複数のパスが存在するステップと、
    前記ナビゲーションシステムに対するクエリを受け入れるステップと、
    前記クエリに応答して記憶されているナビゲーション状態を検索するステップとを含む方法。
78. 前記データ構造が、ナビゲーション状態を表わすノード、および遷移を表わすノード間のエッジを含むグラフデータ構造である請求項７７に記載の方法。
79. 資料のセットと、前記資料を特徴付ける複数の属性と、属性−値ペアの一部が前記属性−値ペアのその他を精緻化する前記属性−値ペアをそれぞれが定義する前記属性の少なくとも１つに対する関連をそれぞれが有する前記資料を記述する複数の値と、属性−値ペアの特定のセットおよび前記資料の特定のサブセットにそれぞれが対応する複数のナビゲーション状態とを含む情報ナビゲーションシステムを提供するための方法であって、
    あらかじめ計算されたナビゲーション状態の部分的セットを生成するステップと、
    あらかじめ計算されたナビゲーション状態の前記部分的セットを記憶するステップと、
    前記ナビゲーション状態の２つの間で直接パスをそれぞれが提供する複数の遷移を提供する前記情報ナビゲーションシステムに対するインターフェースを提供するステップであって、
    各遷移が、元のナビゲーション状態に対応する属性−値ペアのセットから宛先ナビゲーション状態に対応する属性−値ペアのセットへの変化を表わし、一連の１つまたは複数の遷移が、任意の２つのナビゲーション状態の間のパスを提供し、前記ナビゲーション状態の少なくとも第１の状態と前記ナビゲーション状態の第２の状態の間で複数のパスが存在する、ステップと、
    前記ナビゲーションシステムに対するクエリを受け入れるステップと、
    応答するあらかじめ計算されたナビゲーション状態を検索すること、または応答するナビゲーション状態を計算することによって応答するナビゲーション状態を戻すステップとを含む方法。
80. 資料のセットと、前記資料を特徴付ける複数の属性と、属性−値ペアの一部が前記属性−値ペアのその他を精緻化する前記属性−値ペアをそれぞれが定義する前記属性の少なくとも１つに対する関連をそれぞれが有する前記資料を記述する複数の値と、属性−値ペアの特定のセットおよび前記資料の特定のサブセットにそれぞれが対応する複数のナビゲーション状態とを含む情報ナビゲーションシステムを提供するための方法であって、
    前記ナビゲーション状態を暗黙的な表現の中に記憶するステップと、
    前記ナビゲーション状態の２つの間で直接パスをそれぞれが提供する複数の遷移を提供する前記情報ナビゲーションシステムに対するインターフェースを提供するステップであって、
    各遷移が、元のナビゲーション状態に対応する属性−値ペアのセットから宛先ナビゲーション状態に対応する属性−値ペアのセットへの変化を表わし、一連の１つまたは複数の遷移が、任意の２つのナビゲーション状態の間のパスを提供し、前記ナビゲーション状態の少なくとも第１の状態と前記ナビゲーション状態の第２の状態の間で複数のパスが存在する、ステップと、
    前記ナビゲーションシステムに対するクエリを受け入れるステップと、
    前記暗黙的な表現から応答するナビゲーション状態を生成するステップと、
    前記応答するナビゲーション状態を提示するステップとを含む方法。
81. 前記応答するナビゲーション状態をキャッシュの中に記憶するステップをさらに含む請求項８０に記載の方法。
82. ナビゲーションシステムのユーザのプロファイリングを行うための方法であって、
    資料のセットと、前記資料を特徴付ける複数の属性と、属性−値ペアの一部が前記属性−値ペアのその他を精緻化する前記属性−値ペアをそれぞれが定義する前記属性の少なくとも１つに対する関連をそれぞれが有する前記資料を記述する複数の値と、属性−値ペアの特定のセットおよび前記資料の特定のサブセットにそれぞれが対応する複数のナビゲーション状態と、前記ナビゲーション状態の２つの間で直接パスをそれぞれが提供する複数の遷移を提供するインターフェースとを含むナビゲーションシステムを提供するステップであって、
    各遷移が、元のナビゲーション状態に対応する属性−値ペアのセットから宛先ナビゲーション状態に対応する属性−値ペアのセットへの変化を表わし、一連の１つまたは複数の遷移が、任意の２つのナビゲーション状態の間のパスを提供し、前記ナビゲーション状態の少なくとも第１の状態と前記ナビゲーション状態の第２の状態の間で複数のパスが存在するステップと、
    属性−値ペアのユーザの選択を受け入れて、前記複数のナビゲーション状態の中をナビゲートするステップと、
    属性−値ペアのユーザの選択を追跡するステップとを含む方法。
83. 属性−値ペアのユーザの選択に基づいてユーザプロファイルを開発するステップをさらに含む請求項８２に記載の方法。
84. ユーザプロファイルを開発するステップは、ユーザによって訪問されたナビゲーション状態に対応する属性−値ペアに基づいて前記ユーザプロファイルを補足するステップをさらに含む請求項８３に記載の方法。

Images