(57)【要約】  少なくとも１つのデータ構造を少なくとも１つのデータソースから構築する方法が開示される。そのデータソース及びそのデータソースの少なくとも１つのプレビアスビューの表現が構築される（たとえば、２３０００）。次いで、この表現から、少なくとも１つの義務的エンティティ（たとえば、「支社」（ｂｒａｎｃｈ））が識別される。これは、一般に、ユーザ選択によって行うことができる。次いで、この方法では、義務的エンティティと１つまたは複数のコンテキスト・エンティティとを含むデータ構造（たとえば、２５０００、２６０００）が構築され、ここで、コンテキスト・エンティティは、その表現とプレビアスビューから得られたコンテキスト・データとから得られる。通常、データソースは階層的であり、データ構造は階層的である。
2007519086.tif 000002
【特許請求の範囲】
【請求項１】
少なくとも１つのデータソースからデータを提示する方法であって、
（ｉ）前記少なくとも１つのデータソース、及び該少なくとも１つのデータソースの少なくとも１つのプレビアスビュー、の表現を提供する表現提供ステップと、
（ｉｉ）前記表現内の少なくとも１つの義務的エンティティを識別する識別ステップと、
（ｉｉｉ）前記少なくとも１つの義務的エンティティと１つまたは複数のコンテキスト・エンティティとを含むデータ構造を提示する提示ステップと、
を含み、
前記コンテキスト・エンティティは、前記少なくとも１つのプレビアスビューから得られたコンテキスト・データを用いて、前記表現から得られることを特徴とする方法。
【請求項２】
前記少なくとも１つのデータソースが階層的であり、前記データ構造が階層的であることを特徴とする請求項１に記載の方法。
【請求項３】
前記表現がグラフィカルな表現を含むことを特徴とする請求項１に記載の方法。
【請求項４】
前記グラフィカルな表現が、前記少なくとも１つのデータソースと前記少なくとも１つのプレビアスビューとのスキーマ表現を含むことを特徴とする請求項３に記載の方法。
【請求項５】
前記コンテキスト・データが、前記コンテキスト・エンティティの前記義務的エンティティに対する関連性の尺度を表すために評価されるデータを含むことを特徴とする請求項１に記載の方法。
【請求項６】
前記コンテキスト・データが、少なくとも１つの関連する数値データを含むことを特徴とする請求項５に記載の方法。
【請求項７】
前記少なくとも１つの関連する数値データが、前記少なくとも１つのプレビアスビュー内で観測された前記表現内のエンティティの生起および同時生起頻度を含むことを特徴とする請求項６に記載の方法。
【請求項８】
前記少なくとも１つの階層的なデータ構造のルート・ノードが、前記表現内の前記少なくとも１つの義務的エンティティの祖先ノードであることを特徴とする請求項２に記載の方法。
【請求項９】
前記少なくとも１つの階層的なデータ構造に、前記少なくとも１つの義務的エンティティのそれぞれの生起のもとでのルート・ノードの生起確率に等しいスコアが割り当てられることを特徴とする請求項２に記載の方法。
【請求項１０】
前記１つまたは複数のコンテキスト・エンティティが、
（ａ）前記ルート・ノード、
（ｂ）前記ルート・ノードから前記少なくとも１つの義務的エンティティへの、前記表現内の少なくとも１つの有向パスに沿うノードからなる第１の組、
（ｃ）前記表現内の前記ルート・ノードの子孫ノードから選択されるノードからなる第２の組であって、前記第２の組の中の前記ノードそれぞれは、対応する生起確率に基づいて選択され、前記生起確率それぞれは、前記ルート・ノードを含めてそれまでの前記ノードの祖先および前記少なくとも１つの義務的エンティティの生起から導出される組、
（ｄ）前記表現内の前記ルート・ノードの子孫ノードから選択されるノードからなる第３の組であって、選択が前記第３の組のノードの前記表現内の前記ルート・ノードからの対応する距離に基づいて行われる組、および
（ｅ）前記表現内の前記ルート・ノードの子孫ノードから選択されるノードからなる第４の組であって、選択が前記第４の組のノードの前記表現内の前記少なくとも１つの義務的エンティティからの対応する距離に基づいて行われる組
からなる群から選択されることを特徴とする請求項８に記載の方法。
【請求項１１】
前記ノードからなる第２の組が、前記ルート・ノードから前記少なくとも１つの義務的エンティティへの前記有向パスに沿って存在する、前記表現内の少なくとも１つの親ノードの０個以上の子ノードを含むことを特徴とする請求項１０に記載の方法。
【請求項１２】
前記対応する距離が、前記表現内の対象となるノードを隔てるリンクの数を含むことを特徴とする請求項１０に記載の方法。
【請求項１３】
前記提示ステップに関して、前記０個以上の子ノードが、前記少なくとも１つの親ノードの子ノードすべてからコンテキスト・ノードとして選択され、前記選択が、
（ｉｉｉ−ａ）前記親ノード、前記ルート・ノードを含めてそれまでの前記親ノードの祖先、および前記少なくとも１つの義務的エンティティの生起のもとで、第５の組のノード以外のその子ノードのどれともともには現れない前記親ノードの第１の生起確率を計算するステップであって、前記第５の組は、前記親ノードから前記少なくとも１つの義務的エンティティへの有向パスに沿って存在する前記親ノードの子ノードを含むステップと、
（ｉｉｉ−ｂ）前記親ノード、前記ルート・ノードを含めてそれまでの前記親ノードの祖先、および前記少なくとも１つの義務的エンティティの生起のもとで、第６の組のノードのうちでの子ノードそれぞれの第２の生起確率を計算するステップであって、前記第６の組は、前記親ノードから前記少なくとも１つの義務的エンティティへの有向パスに沿って存在しない前記親ノードの子ノードを含むステップと、
（ｉｉｉ−ｃ）前記第１の生起確率および前記第２の生起確率の合計を計算するステップと、
（ｉｉｉ−ｄ）架空のノードを作成し、前記架空のノードに前記第１の生起確率を割り当てるステップと、
（ｉｉｉ−ｅ）前記第５の組の子ノードをコンテキスト・ノードとして選択するステップと、
（ｉｉｉ−ｆ）前記第１の生起確率または前記第２の生起確率の降下する値の順に配列された前記第６の組の子ノードおよび前記架空のノードから形成される第７の組の子ノードをコンテキスト・ノードとして選択するステップであって、このためには、前記第７の組の子ノードの前記第１の生起確率または前記第２の生起確率の和が前記合計の半分以上であるステップと、
（ｉｉｉ−ｇ）前記架空のノードが前記第７の組の子ノードのうちで選択された場合、前記架空のノードのコンテキスト・ノードとしての選択を解除するステップとを含み、
前記第１の生起確率および前記第２の生起確率の近似が、前記少なくとも１つのプレビアスビュー内で観測された、前記表現内のノードの少なくとも１つの生起頻度、前記表現内の一対のノードの間の共起頻度、および前記表現内のｎ−組のノードの間の同時生起頻度を用いて行われることを特徴とする請求項１１に記載の方法。
【請求項１４】
ノードはその和が前記合計の半分を超えるまでコンテキスト・ノードとして選択されることから、前記架空のノードは、関連づけられている確率が前記架空のノードに関連づけられている確率より小さい他のノードが選択されることを妨げることを特徴とする請求項１３に記載の方法。
【請求項１５】
前記提示ステップに関して、前記０個以上の子ノードが、前記少なくとも１つの親ノードの子ノードすべてからコンテキスト・ノードとして選択され、前記選択が、
（ｉｉｉ−ａ）前記親ノード、前記ルート・ノードを含めてそれまでの前記親ノードの祖先、および前記少なくとも１つの義務的エンティティの生起のもとで、第５の組のノード以外のその子ノードのどれともともには現れない前記親ノードの第１の生起確率を計算するステップであって、前記第５の組は、前記親ノードから前記少なくとも１つの義務的エンティティへの有向パスに沿って存在する前記親ノードの子ノードを含むステップと、
（ｉｉｉ−ｂ）前記第５の組の子ノードをコンテキスト・ノードとして選択するステップと、
前記第１の生起確率が０．５以下である場合に、
（ｉｉｉ−ｃ）前記親ノード、前記ルート・ノードを含めてそれまでの前記親ノードの祖先、および前記少なくとも１つの義務的エンティティの生起のもとで、第６の組のノードのうちでの子ノードそれぞれの第２の生起確率を計算するステップであって、前記第６の組は、前記親ノードから前記少なくとも１つの義務的エンティティへの有向パスに沿って存在しない前記親ノードの子ノードを含むステップと、
（ｉｉｉ−ｄ）前記第２の組の子ノードの前記第２の生起確率の合計を計算するステップと、
（ｉｉｉ−ｅ）前記第２の生起確率の降下する値の順の前記第６の組の子ノードから形成される第７の組の子ノードをコンテキスト・ノードとして選択することを、前記第７の組の子ノードの前記第２の生起確率の和が前記合計の半分以上になるまで行うステップとを含み、
前記第１の生起確率および前記第２の生起確率の近似が、前記少なくとも１つのプレビアスビュー内で観測された、前記表現内のノードの少なくとも１つの生起頻度、前記表現内の一対のノードの間の共起頻度、および前記表現内のｎ−組のノードの間の同時生起頻度を用いて行われることを特徴とする請求項１１に記載の方法。
【請求項１６】
前記ノードからなる第２の組が、前記ルート・ノードから前記少なくとも１つの義務的エンティティへの前記有向パスに沿って存在しない、前記表現内の少なくとも１つの親ノードの０個以上の子ノードを含むことを特徴とする請求項１０に記載の方法。
【請求項１７】
前記提示ステップに関して、前記０個以上の子ノードが、前記少なくとも１つの親ノードの子ノードすべてから選択され、前記選択が、
（ｉｉｉ−ａ）前記親ノード、前記ルート・ノードを含めてそれまでの前記親ノードの祖先、および前記少なくとも１つの義務的エンティティの生起のもとで、その子ノードのどれもなしに現れる前記親ノードの第１の生起確率を計算するステップと、
（ｉｉｉ−ｂ）前記親ノード、前記ルート・ノードを含めてそれまでの前記親ノードの祖先、および前記少なくとも１つの義務的エンティティの生起のもとで、前記親ノードの子ノードそれぞれの第２の生起確率を計算するステップと、
（ｉｉｉ−ｃ）前記親ノードの子ノードすべての前記第１の生起確率および前記第２の生起確率の合計を計算するステップと、
（ｉｉｉ−ｄ）架空のノードを作成し、前記架空のノードに前記第１の生起確率を割り当てるステップと、
（ｉｉｉ−ｅ）前記第１の生起確率または前記第２の生起確率の降下する値の順に配列された前記架空のノードおよび前記親ノードの子ノードすべてからなる組からのノードをコンテキスト・ノードとして選択することを、選択されたノードの前記第１の生起確率または前記第２の生起確率の和が前記合計の半分以上になるまで行うステップと、
（ｉｉｉ−ｆ）前記架空のノードが前記選択されたノードのうちにある場合、前記架空のノードのコンテキスト・ノードとしての選択を解除するステップとを含み、
前記第１の生起確率および前記第２の生起確率の近似が、前記少なくとも１つのプレビアスビュー内で観測された、前記表現内のノードの少なくとも１つの生起頻度、前記表現内の一対のノードの間の共起頻度、および前記表現内のｎ−組のノードの間の同時生起頻度を用いて行われることを特徴とする請求項１６に記載の方法。
【請求項１８】
前記提示ステップに関して、前記０個以上の子ノードが、前記少なくとも１つの親ノードの子ノードすべてから選択され、前記選択が、
（ｉｉｉ−ａ）前記親ノード、前記ルート・ノードを含めてそれまでの前記親ノードの祖先、および前記少なくとも１つの義務的エンティティの生起のもとで、その子ノードのどれもなしに現れる前記親ノードの第１の生起確率を計算するステップと、
前記第１の生起確率が０．５以下である場合に、
（ｉｉｉ−ｂ）前記親ノード、前記ルート・ノードを含めてそれまでの前記親ノードの祖先、および前記少なくとも１つの義務的エンティティの生起のもとで、前記親ノードの子ノードそれぞれの第２の生起確率を計算するステップと、
（ｉｉｉ−ｃ）前記親ノードの子ノードすべての前記第２の生起確率の合計を計算するステップと、
（ｉｉｉ−ｄ）前記第２の生起確率の降下する値の順の前記親ノードの子ノードすべてからなる組からのノードをコンテキスト・ノードとして選択することを、選択されたノードの前記第２の生起確率の和が前記合計の半分以上になるまで行うステップとを含み、
前記第１の生起確率および前記第２の生起確率の近似が、前記少なくとも１つのプレビアスビュー内で観測された、前記表現内のノードの少なくとも１つの生起頻度、前記表現内の一対のノードの間の共起頻度、および前記表現内のｎ−組のノードの間の同時生起頻度を用いて行われることを特徴とする請求項１６に記載の方法。
【請求項１９】
前記義務的エンティティが、
（ｉ）１つまたは複数の検索キーワードの場所、および
（ｉｉ）ユーザの選択したエンティティ
のうちの１つを表すことを特徴とする請求項１に記載の方法。
【請求項２０】
前記グラフィカルな表現が、ツリー表現を含み、前記表現提供ステップまたは識別ステップが、ユーザの、前記表現のサブツリーの選択を検出することを含み、前記提示ステップに関して、前記ユーザの選択したサブツリーの中の少なくとも１つの親ノードの０個以上の子ノードの選択が、１組のコンテキスト・ノードの中で行われ、前記選択が、
（ｉｉｉ−ａ）前記ユーザの選択したサブツリーの前記親ノード、前記ルート・ノードを含めてそれまでの前記親ノードの祖先の生起のもとで、その子ノードのどれもなしに現れる前記親ノードの第１の生起確率を計算するステップと、
（ｉｉｉ−ｂ）前記ユーザの選択したサブツリーの前記親ノード、前記ルート・ノードを含めてそれまでの前記親ノードの祖先の生起のもとで、前記親ノードの子ノードそれぞれの第２の生起確率を計算するステップと、
（ｉｉｉ−ｃ）前記親ノードの子ノードすべての前記第１の生起確率および前記第２の生起確率の合計を計算するステップと、
（ｉｉｉ−ｄ）架空のノードを作成し、前記架空のノードに前記第１の生起確率を割り当てるステップと、
（ｉｉｉ−ｅ）前記第１の生起確率または前記第２の生起確率の降下する値の順の前記架空のノードおよび前記親ノードの子ノードすべてからなる組からのノードをコンテキスト・ノードとして選択することを、選択されたノードの前記第１の生起確率または前記第２の生起確率の和が前記合計の半分以上になるまで行うステップと、
（ｉｉｉ−ｆ）前記架空のノードが前記選択されたノードのうちにある場合、前記架空のノードの選択を解除するステップと
を含むことを特徴とする請求項３に記載の方法。
【請求項２１】
前記グラフィカルな表現が、ツリー表現を含み、前記表現提供ステップまたは前記識別ステップが、ユーザの、前記表現のサブツリーの選択を検出することを含み、提示ステップに関して、前記ユーザの選択したサブツリーの中の少なくとも１つの親ノードの０個以上の子ノードの選択が、１組のコンテキスト・ノードの中で行われ、前記選択が、
（ｉｉｉ−ａ）前記ユーザの選択したサブツリーの前記ルート・ノードまで、及びそれを含む前記親ノードの祖先、及び前記親ノードの生起のもとで、子ノードなしに現れる前記親ノードの第１の生起確率を計算するステップと、
前記第１の生起確率が０．５以下である場合に、
（ｉｉｉ−ｂ）前記ユーザの選択したサブツリーの前記ルート・ノードまで、及びそれを含む前記親ノードの祖先、及び前記親ノードの生起のもとで、前記親ノードの子ノードそれぞれについての第２の生起確率を計算するステップと、
（ｉｉｉ−ｃ）前記親ノードの子ノードすべての前記第２の生起確率の合計を計算するステップと、
（ｉｉｉ−ｄ）前記第２の生起確率の降下する値の順の前記親ノードの子ノードすべてからなる組からのノードをコンテキスト・ノードとして選択することを、選択されたノードの前記第２の生起確率の和が前記合計の半分以上になるまで行うステップと
を含むことを特徴とする請求項３に記載の方法。
【請求項２２】
少なくとも１つの検索キーワードを含む少なくとも１つのデータソースにおけるキーワード検索操作のためにデータの構築および提示を行う方法であって、
（ｉ）前記少なくとも１つのデータソースと前記少なくとも１つのデータソースの少なくとも１つのプレビアスビューとのグラフィカルな表現を構築するステップと、
（ｉｉ）前記グラフィカルな表現内の少なくとも１つの義務的エンティティを識別するステップであって、前記義務的エンティティは１つまたは複数の前記少なくとも１つの検索キーワードの場所を表す、前記グラフィカルな表現内のノードであるステップと、
（ｉｉｉ）前記少なくとも１つの義務的エンティティと１つまたは複数のコンテキスト・エンティティとを含む少なくとも１つのデータ構造の構築を、少なくとも１つの検索キーワードに対応して行うステップであって、前記コンテキスト・エンティティは、前記グラフィカルな表現から、前記少なくとも１つのプレビアスビューから得られたコンテキスト・データを用いて得られるステップと、
（ｉｖ）前記少なくとも１つのデータ構造を前記キーワード検索操作の結果として提示するステップと
を含むことを特徴とする方法。
【請求項２３】
少なくとも１つの前記データソースが、階層的であることを特徴とする請求項２２に記載の方法。
【請求項２４】
プログラムがその上に記録されているコンピュータ可読媒体であって、前記プログラムは、少なくとも１つのデータソースからのデータを提示する手続きをコンピュータに実行させるように構成され、
（ｉ）前記少なくとも１つのデータソースと前記少なくとも１つのデータソースの少なくとも１つのプレビアスビューとの表現を提供するためのコードと、
（ｉｉ）前記表現内の少なくとも１つの義務的エンティティを識別するためのコードと、
（ｉｉｉ）前記少なくとも１つの義務的エンティティと１つまたは複数のコンテキスト・エンティティとを含むデータ構造を提示するためのコードとを含み、前記コンテキスト・エンティティは、前記表現から、前記少なくとも１つのプレビアスビューから得られたコンテキスト・データを用いて得られることを特徴とするコンピュータ可読媒体。
【請求項２５】
少なくとも１つの前記データソースが階層的であり、前記データ構造が階層的であることを特徴とする請求項２４に記載のコンピュータ可読媒体。
【請求項２６】
プログラムがその上に記録されているコンピュータ可読媒体であって、前記プログラムは、少なくとも１つの検索キーワードを含む少なくとも１つのデータソースにおけるキーワード検索操作のためにデータの構築および提示を行う手続きをコンピュータに実行させるように構成され、
（ｉ）前記少なくとも１つのデータソースと前記少なくとも１つのデータソースの少なくとも１つのプレビアスビューとのグラフィカルな表現を構築するためのコードと、
（ｉｉ）前記グラフィカルな表現内の少なくとも１つの義務的エンティティを識別するためのコードであって、前記義務的エンティティは１つまたは複数の前記少なくとも１つの検索キーワードの場所を表す、前記グラフィカルな表現内のノードであるコードと、
（ｉｉｉ）前記少なくとも１つの義務的エンティティと１つまたは複数のコンテキスト・エンティティとを含む少なくとも１つのデータ構造の構築を行うためのコードであって、前記コンテキスト・エンティティは、前記グラフィカルな表現から、前記少なくとも１つのプレビアスビューから得られたコンテキスト・データを用いて得られるコードと、
（ｉｖ）前記少なくとも１つのデータ構造を前記キーワード検索操作の結果として提示するためのコードと
を含むことを特徴とするコンピュータ可読媒体。
【請求項２７】
少なくとも１つの前記データソースが階層的であり、少なくとも１つの前記データ構造が階層的であることを特徴とする請求項２６に記載のコンピュータ可読媒体。
【請求項２８】
少なくとも１つのデータ構造を少なくとも１つのデータソースから構築するためのコンピュータ機器であって、
前記少なくとも１つのデータソースと前記少なくとも１つのデータソースの少なくとも１つのプレビアスビューとの表現を構築するように構成された第１の構築モジュールと、
前記表現内の少なくとも１つの義務的エンティティを識別するように構成された識別モジュールと、
前記少なくとも１つの義務的エンティティと１つまたは複数のコンテキスト・エンティティとを含む前記少なくとも１つのデータ構造を構築するように構成された第２の構築モジュールとを含み、前記コンテキスト・エンティティは、前記表現から、前記少なくとも１つのプレビアスビューから得られたコンテキスト・データを用いて得られることを特徴とする機器。
【請求項２９】
少なくとも１つの前記データソースが階層的であり、前記少なくとも１つのデータ構造が階層的であることを特徴とする請求項２８に記載のコンピュータ機器。
【請求項３０】
少なくとも１つの検索キーワードを含む少なくとも１つのデータソースにおけるキーワード検索操作のためにデータの構築および提示を行うためのコンピュータ機器であって、
前記少なくとも１つのデータソースと前記少なくとも１つのデータソースの少なくとも１つのプレビアスビューとのグラフィカルな表現を構築するように適合された構築モジュールと、
前記グラフィカルな表現内の少なくとも１つの義務的エンティティを識別するように適合された識別モジュールであって、前記義務的エンティティは１つまたは複数の前記少なくとも１つの検索キーワードの場所を表す、前記グラフィカルな表現内のノードであるモジュールと、
前記少なくとも１つの義務的エンティティと１つまたは複数のコンテキスト・エンティティとを含む少なくとも１つのデータ構造の構築を行うように適合された構築モジュールであって、前記コンテキスト・エンティティは、前記グラフィカルな表現から、前記少なくとも１つのプレビアスビューから得られたコンテキスト・データを用いて得られるモジュールと、
前記少なくとも１つのデータ構造を前記キーワード検索操作の結果として提示するように適合された提示モジュールと
を含むことを特徴とする機器。
【請求項３１】
本明細書で、図面を用いて示されているいずれか１つの実施形態を参照して実質的に説明された、少なくとも１つのデータ構造を構築する方法。
【請求項３２】
コンピュータに請求項３１に記載の方法を実行させるように構成されたコンピュータ・プログラムを記録していることを特徴とするコンピュータ可読媒体。
【請求項３３】
請求項３１の方法に従って、少なくとも１つのデータ構造を構築することを特徴とするコンピュータ機器。
【請求項３４】
前記少なくとも１つのデータ構造が階層的であることを特徴とする請求項３１から３３のいずれか一項に記載の発明。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報検索（ｒｅｔｒｉｅｖａｌ）の一般分野に関し、特に、関連性の高いデータを大規模な階層データの情報源から自動的に識別および検索することに関する。
【背景技術】
【０００２】
ＸＭＬ（Ｅｘｔｅｎｓｉｂｌｅ  Ｍａｒｋｕｐ  Ｌａｎｇｕａｇｅ、拡張可能なマーク付け言語）は、情報を保存および交換するための一般的な階層フォーマットにますますなりつつある。ＸＭＬの階層的な性質により、ＸＭＬは、データ・オブジェクト間の関係を捉えるための優れた手段となる一方で、キーワード検索をより困難にもしている。
【０００３】
キーワード検索は、ＸＭＬなどの構造化されたデータ・フォーマットを扱うときには特に重要であるが、その理由は、これによってユーザが特定のキーワードを、データの内部構造を知ることを必要とせずに迅速に見つけられるようになることにある。これはＸＭＬで作業を行うときに難問となるが、それは、キーワード検索の結果を提示するための最適のまたは明らかに好ましい方法がないためである。伝統的な構造化されていないテキストの環境では、データ・システムから、通常、ユーザに対して、見つかったキーワードをその付近にある他のテキストと一緒に提示される。「ヒット」が１つより多い場合、隣接するテキストにより、ヒット同士を区別するための有用なコンテキストを提供され、それにより、ユーザは、関連性の最も高いヒットの選択をユーザの必要に応じて行えるようになる。
【０００４】
構造化されているＸＭＬの環境では、互いに関係するデータはＸＭＬ文書内部のいくつかのばらばらな（ｄｉｓｊｏｉｎｔ）場所にある可能性があるため、「隣接するデータ」（ｎｅｉｇｈｂｏｕｒｉｎｇ  ｄａｔａ）のはっきりした概念がない。このため、キーワード検索においてヒットに適したコンテキストを識別または構築することが難しい。したがって、既存のたいていのＸＭＬベースのシステムでは、ある文書の内部でキーワード・ヒットが生じた場合、（ＸＭＬ文書からなるある集まりの中から）単にそのＸＭＬ文書全体を返し、実質的にその文書全体にそのヒットに対するコンテキストの役割をさせている。これは、文書が大きく、ユーザがその内容のすべてを見ることに興味のないときには、望ましくない。
【０００５】
現実的なデータソース、特にデータベースは、しばしば、ユーザがとにかく一度で見たいと思うよりもずっと多くのデータを含んでいる。たとえば、メール注文の店にあるデータベースには、その製品、顧客、納入業者、運送業者、ならびに過去および未発送の注文のすべてについての詳細が含まれているかもしれない。店員は、特定の製品の現在の在庫量を見たいと希望することもあろうし、ある顧客に対する注文のステータスを確認したいと思うこともあろう。他方、店のマネージャーが、何ヶ月にもわたって特定の製品の総売り上げの変動を見たいと希望することがあるかもしれない。こうした場合のそれぞれで、さらに別の関連性のないデータが雪崩のように提示されるとすれば、それはあまりにもユーザを惑わせることになろう。さらに、ユーザは、そのデータベースの構造に詳しくない限り、通常は、自分の興味がある情報を特定することができないはずである。
【０００６】
関連性の高いデータだけを提供するための伝統的な方法は、システム管理者など、データソースの構造に詳しい誰かの準備した、あらかじめ作成済みの「ビュー」の使用によるものである。各ビューは、そのデータソースの何らかのサブセットを引き出してまとめるものであり、はっきりした目的に合わせて作られている。先に挙げた例では、店員は「在庫量」ビューまたは「注文ステータス」ビューを調べるであろうし、マネージャーは「売上」ビューを持ち出すことになろう。
【０００７】
このあらかじめ作成済みのビューを使用するというアプローチは、ありそうな使用法の想定状況をすべて見越しておけるときには十分であるが、キーワード検索には適していない。キーワード検索の操作では、ユーザは、１つまたは複数のキーワードを入力し、システムは、（ＡＮＤのブール値キーワード検索操作を仮定すると）そのキーワードすべての出現を含むデータ・セットまたはビューによって応答する。ＸＭＬなどの階層的な環境では、キーワード・ヒットは、階層内の異なる場所にあるいくつかのデータ項目の中に生じる可能性がある。ユーザの与える可能性のある可能なキーワードの組合せすべてを見越しておくことは実現可能でない以上、階層内のどこでヒットが生じるかをあらかじめ判定することは可能でない。したがって、検索の想定状況すべてをまかなうようなあらかじめ作成済みのビューを提供することは可能ではない。
【０００８】
これに類したキーワード検索の問題点は、関係データベースの環境でも存在する。関係データベースは、そのプライマリおよびフォーリンのキーによって併合されたテーブルを含み、ここで各テーブルは、あるエンティティに対する属性の値からなるｎ−組（ｎ−ｔｕｐｌｅ）をそれぞれが表す複数の行を含む。Ｈｒｉｓｔｉｄｉｓ，Ｖ．ａｎｄ  Ｐａｐａｋｏｎｓｔａｎｔｉｎｏｕ，Ｙ．、「ＤＩＳＣＯＶＥＲ：Ｋｅｙｗｏｒｄ  Ｓｅａｒｃｈ  ｉｎ  Ｒｅｌａｔｉｏｎａｌ  Ｄａｔａｂａｓｅｓ」、Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ２８ｔｈ  ＶＬＤＢ  Ｃｏｎｆｅｒｅｎｃｅ、２００２年で記述されている、関係データベースにおけるキーワード検索に対する伝統的な解決策は、キーワード・ヒットすべてを含む併合済みテーブル全体にわたって併合される行の最小のネットワークである、最小併合ネットワーク（ｍｉｎｉｍａｌ  ｊｏｉｎｉｎｇ  ｎｅｔｗｏｒｋ）を返すことである。このアプローチの問題点は、キーワード・ヒットがデータベース・テーブルのある行の中のどこかで生じた場合、その行全体がそのヒットに対するコンテキストとして返されるという点で、行が最小のデータ「チャンク」として効果的に扱われることである。このことから、極端な量のデータがユーザに提示されることになる可能性があるが、これは、典型的な関係データベースのテーブルが、しばしば、ユーザには普通興味のない多くの列を含んでいるためである。
【０００９】
さらに、上の技法を、ＸＭＬなどの階層的なデータ構造に適合させると、コンテキストの情報が不十分になる可能性がある。階層的な環境では、関係するデータは、階層内の異なるレベルで格納されている可能性があり、このためしばしば、親または祖先のノードあるいはその子からは、キーワード検索に対する非常に有用なコンテキストが、たとえ最小データ・セットには含まれないかもしれない場合でも、提供される可能性がある。
【００１０】
階層データにおけるキーワード検索の問題に取り組むために、いくつかの試みがなされてきている。Ｆｌｏｒｅｓｃｕ，Ｄ．「Ｉｎｔｅｇｒａｔｉｎｇ  Ｋｅｙｗｏｒｄ  Ｓｅａｒｃｈ  ｉｎｔｏ  ＸＭＬ  Ｑｕｅｒｙ  Ｐｒｏｃｅｓｓｉｎｇ」、Ｎｉｎｔｈ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｗｏｒｌｄ  Ｗｉｄｅ  Ｗｅｂ  Ｃｏｎｆｅｒｅｎｃｅ、２０００年５月では、構造化問い合わせ言語をキーワード検索演算子ｃｏｎｔａｉｎｓで拡張する方法が開示されている。この演算子では、指定したサブツリーがいくつかの指定したキーワードを含む場合に、評価が真となる。ユーザは、この演算子を、問い合わせを構築するときに使用して、望ましくないデータをふるい除けることができる。この有用な機能では、ユーザは、所与のサブツリー内部のヒットしたキーワードの正確な場所を指定する必要はないが、返されるデータの正確なフォーマットをやはり検索問い合わせの中で指定する必要があり、このため、データソースの構造に詳しいことが必要であるため、十分ではない。言い換えると、フリー・テキストのキーワード検索は、ユーザがデータソース全体を検索の結果として受け入れる気がない限り、依然として可能ではないのである。
【００１１】
ＸＭＬデータソースにおけるキーワード検索に対する既存の別のアプローチでは、ユーザが、スキーマ要素からなる所与のリストから、返されるデータのルート・ノードに相当する要素を選択する必要がある。キーワード・ヒットが生じるのが、選択したスキーマ要素の表すデータ要素の子孫ノード内である場合、ヒットしたキーワードを含む、そのデータ要素の下のサブツリー全体がユーザへと返される。このアプローチは、ユーザの介入を必要とするため、扱いにくい。さらに、ユーザは、サブツリー全体を、たとえそのユーザに興味のないデータを含むかもしれない場合でも、受け入れるよう強いられる。
【００１２】
したがって、階層的なデータの環境における１組の関連性の高いデータの判定を、ユーザの介入またはユーザの事前の階層データの構造の知識を必要としない、キーワードの任意の組合せを含むキーワード検索操作に応答して行うための方法が必要とされている。
【非特許文献１】Ｈｒｉｓｔｉｄｉｓ，Ｖ．ａｎｄ  Ｐａｐａｋｏｎｓｔａｎｔｉｎｏｕ，Ｙ．、「ＤＩＳＣＯＶＥＲ：Ｋｅｙｗｏｒｄ  Ｓｅａｒｃｈ  ｉｎ  Ｒｅｌａｔｉｏｎａｌ  Ｄａｔａｂａｓｅｓ」、Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ２８ｔｈ  ＶＬＤＢ  Ｃｏｎｆｅｒｅｎｃｅ、２００２年
【非特許文献２】Ｆｌｏｒｅｓｃｕ，Ｄ．「Ｉｎｔｅｇｒａｔｉｎｇ  Ｋｅｙｗｏｒｄ  Ｓｅａｒｃｈ  ｉｎｔｏ  ＸＭＬ  Ｑｕｅｒｙ  Ｐｒｏｃｅｓｓｉｎｇ」、Ｎｉｎｔｈ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｗｏｒｌｄ  Ｗｉｄｅ  Ｗｅｂ  Ｃｏｎｆｅｒｅｎｃｅ、２０００年５月
【特許文献１】オーストラリア特許出願第２００３２０４８２４号
【特許文献２】米国特許出願第１０／４６５２２２号
【発明の開示】
【発明が解決しようとする課題】
【００１３】
既存の諸方法の１つまたは複数の不利な点を克服または少なくとも改善することが、本発明の一目的である。
【課題を解決するための手段】
【００１４】
本発明のある態様によれば、少なくとも１つのデータソースからのデータを提示する方法であって、
（ｉ）前記少なくとも１つのデータソース及び前記少なくとも１つのデータソースの少なくとも１つのプレビアスビュー、の表現を保持するステップと、
（ｉｉ）前記表現内の少なくとも１つの義務的エンティティを識別するステップと、
（ｉｉｉ）前記少なくとも１つの義務的エンティティと１つまたは複数のコンテキスト・エンティティとを含むデータ構造を提示するステップとを含み、
前記コンテキスト・エンティティは、前記表現と前記少なくとも１つのプレビアスビューから得られるコンテキスト・データとから得られることを特徴とする方法が開示される。
【００１５】
より具体的には、少なくとも１つのデータソースから少なくとも１つのデータ構造を構築する方法であって、
（ｉ）前記少なくとも１つのデータソースと前記最小の１つのデータソースの少なくとも１つのプレビアスビューとの表現を構築するステップと、
（ｉｉ）前記表現内の少なくとも１つの義務的エンティティを識別するステップと、
（ｉｉｉ）前記少なくとも１つの義務的エンティティと１つまたは複数のコンテキスト・エンティティとを含む前記少なくとも１つのデータ構造を構築するステップとを含み、前記コンテキスト・エンティティは、前記表現と前記少なくとも１つのプレビアスビューから得られるコンテキスト・データとから得られることを特徴とする方法が開示される。
【００１６】
通常、データソースとデータ構造のうちのいずれかまたはいずれもが階層的である。
【００１７】
本発明の別の態様によれば、データソースからデータを選択する方法であって、
（ｉ）前記データソースのグラフィカルな表現を形成するステップと、
（ｉｉ）前記表現のうち、ユーザが選択した部分を検出するステップと、
（ｉｉｉ）前記ユーザ選択された部分内の１組のコンポーネントの選択を、前記ユーザ選択された部分のコンポーネントがあるときの前記１組のコンポーネントの生起確率に基づいて行うステップとを含むことを特徴とする方法が開示される。
【００１８】
本発明の別の態様によれば、少なくとも１つの検索キーワードを含む少なくとも１つのデータソースにおけるキーワード検索操作のためのデータの構築および提示の方法であって、
（ｉ）前記少なくとも１つのデータソースと前記少なくとも１つのデータソースの少なくとも１つのプレビアスビューとのグラフィカルな表現を構築するステップと、
（ｉｉ）前記表現内の少なくとも１つの義務的エンティティを識別するステップであって、前記義務的エンティティは、１つまたは複数の前記最小の検索キーワードの場所を表す前記グラフィカルな表現内のノードであるステップと、
（ｉｉｉ）前記最小の１つの義務的エンティティと１つまたは複数のコンテキスト・エンティティとを含む少なくとも１つのデータ構造を構築するステップであって、前記コンテキスト・エンティティは、前記グラフィカルな表現と前記最小の１つのプレビアスビューから得られるコンテキスト・データとから得られるステップと、
（ｉｖ）前記少なくとも１つのデータ構造を、前記キーワード検索操作の結果として提示するステップとを含むことを特徴とする方法が開示される。
【００１９】
本発明の別の態様によれば、階層的に表示されたデータからなるサブツリーからのデータソースの提示の方法であって、
（ｉ）前記サブツリー内の１組の子孫ノードの選択を、前記階層的に表示されたデータの少なくとも１つのそれまでの表現から得られるコンテキスト・データに基づいて行うステップと、
（ｉｉ）前記サブツリーのルート・ノードおよび前記選択された１組の子孫ノードを含む階層的なデータ構造を構築し提示するステップとを含むことを特徴する方法が提示される。
【００２０】
機器およびコンピュータ媒体を含む、本発明の他の諸態様も開示される。
【００２１】
ここで、本発明の少なくとも１つの実施形態を、図面を参照して説明することにする。
【発明を実施するための最良の形態】
【００２２】
以下に、図面を参照して、この発明の好適な実施の形態を例示的に詳しく説明する。ただし、この実施の形態に記載されている構成要素はあくまで例示であり、この発明の範囲をそれらのみに限定する趣旨のものではない。
【００２３】
本開示により、階層的なデータの環境における１組の関連性の高いデータの判定を、１つまたは複数のキーワードを含むキーワード検索操作に応答して行うための方法が提供される。好ましい一実施形態は、階層的なデータ構造におけるデータの好ましいビューの構築を、データが過去のエピソードでどのようにアクセスされたかに基づいて行うベイズ確率に基づく方法を含む。より具体的には、この方法では、データ項目の対とベクトルの間の過去の同時生起の頻度を利用して、あるデータ項目がいくつかの他の義務的データ項目にとって関連性が高いことの確率を計算する。通常、義務的データ項目は、キーワード・ヒットを含むものであり、このため、ユーザに対してキーワード検索結果に入れて返さなければならない。義務的でないデータ項目は、義務的データ項目にとって関連性が高いことの確率が高い場合には、検索結果に入れて返されてキーワード・ヒットに対するコンテキストとして役立つことが見込まれる。
【００２４】
ここに開示する配置の、伝統的なあらかじめ作成されたビューに基づくアプローチに対する顕著な特徴は、前者が、単に既存の保存されたビューを返すのではなく、新しいビューを合成できることである。このため、そのような配置は、任意のキーワード組合せを含むキーワード検索操作を扱うことができ、またビューは、動的に生成されるため、あらかじめ作成されたビューの固定のプールから得られるものよりも、個々の操作によりよく合わせることができる。
【００２５】
ここに開示する方法では、通常、いくつもの代替のビューを構築し、そのビューがユーザにとってどのくらい興味があるものかを示すスコアを、各ビューに対して割り当てる。ある実装形態では、構築したもののうちでスコアの最も高い単一のビューがユーザに返される。ある代替実施形態では、最高から最低へとそのスコアに従ってソートされたビューのリストが返される。
【００２６】
ここに開示する方法は、キーワード検索がその第一の動機ではあるが、ともに「Ｍｅｔｈｏｄｓ  ｆｏｒ  Ｉｎｔｅｒａｃｔｉｖｅｌｙ  Ｄｅｆｉｎｉｎｇ  Ｔｒａｎｓｆｏｒｍｓ  ａｎｄ  ｆｏｒ  Ｇｅｎｅｒａｔｉｎｇ  Ｑｕｅｒｉｅｓ  ｂｙ  Ｍａｎｉｐｕｌａｔｉｎｇ  Ｅｘｉｓｔｉｎｇ  Ｑｕｅｒｙ  Ｄａｔａ」という名称の２００３年６月１９日に出願されたオーストラリア特許出願第２００３２０４８２４号、およびこれに対応する、２００３年６月２０日に出願された米国特許出願第１０／４６５２２２号に記載のものなどの、階層データの提示の方法を向上させるのに使用することもできる。その公開（ｐｕｂｌｉｃａｔｉｏｎ）では、最も適切な提示タイプ（テーブル、グラフ、プロット、ツリーなど）の選択を階層的なデータソースの構造および内容に基づいて行うための方法が開示されている。この方法は、提示タイプの選択の前に、本開示の好ましい一実施形態を、表示に最も好ましいデータソースのサブセットを自動的に選択する手段として組み込むことによって向上させることができる。データの好ましいサブセットだけをこのようにして表示することがしばしば有用であるが、これは、階層的なデータソースが、しばしば、ユーザに普通興味のあるはずのものよりも多くの情報を含むためであり、このため、本発明の好ましい実施形態などの「興味のない」データをふるい除ける方法は、ユーザの経験をより満足の行く生産的なものにするのに役立つ可能性がある。
【００２７】
以下にある説明のいくつかの部分は、明示的にまたは暗黙に、コンピュータ・メモリ内部のデータに対する操作のアルゴリズムおよび記号表現によって提示してある。こうしたアルゴリズムの説明および表現は、データ処理の当業者がその作業の実質を他の当業者に最も効率よく伝えるのに使用する手段である。アルゴリズムは、ここでは、また一般的には、所望の結果をもたらす自己整合的な一連のステップと考えられている。ステップは、物理量の物理的操作を必要とするものである。こうした量は、必ずではないが、普通、保存、転送、組合せ、比較、および他の方法で操作するのに堪える電気または磁気の信号の形式をとる。時折、主に一般的に使用されているという理由で、こうした信号をビット、値、要素、記号、キャラクタ、項、数などと呼ぶと好都合であることがわかっている。
【００２８】
しかし、上のおよび類似の用語は、適切な物理量に関連づけられるべきであり、そうした量に適用される便宜的なラベルにすぎないことを銘記すべきである。そうでないと特に述べない限り、また以下から明らかなように、本明細書を通して、「スキャンする」、「計算する」、「判定する」、「置き換える」、「生成する」、「初期化する」、「出力する」などの用語を使用する議論が指すのは、コンピュータ・システムのレジスタおよびメモリ内部の物理（電子的）量として表現されたデータを、コンピュータ・システムのメモリまたはレジスタあるいはそのような他の情報の保存、伝達、または表示の装置内部の物理量として同様に表現される他のデータへと操作または変換するコンピュータ・システムまたは類似の電子的装置の動作およびプロセスであることが理解されよう。
【００２９】
また、本明細書では、この方法の操作を行うための機器の開示を行う。そのような機器は、必要な目的向けに特別に構築することができ、またはコンピュータ内に格納したコンピュータ・プログラムによって選択的に活性化または再構成される汎用コンピュータまたは他の装置を含んでもよい。本明細書で提示するアルゴリズムおよび表示は、特定のどのようなコンピュータまたは他の機器とも固有の関係をもたない。様々な汎用の機械を、本明細書中の教示によるプログラムとともに使用することができる。あるいは、必要な方法ステップを行うためにより特化した機器を構築することが適切であることもある。従来の汎用コンピュータの構造は、下の説明の中で行うことにする。
【００３０】
さらにまた、本明細書では、この方法の操作を行うためのコンピュータ・プログラムを含むコンピュータ可読媒体の開示を行う。コンピュータ可読媒体は、本明細書では、送信元とあて先の間でコンピュータ・プログラムを通信で送るためのどのような伝送媒体も含むと解釈する。伝送媒体は、磁気もしくは光ディスク、メモリ・チップなどのストレージ装置、または汎用コンピュータとのインターフェースを行うのに適した他のストレージ装置を含むことができる。また、伝送媒体は、インターネット・システムの形で例示されるような配線接続（ｈａｒｄ−ｗｉｒｅｄ）の媒体、またはＧＳＭ移動体電話システムの形で例示されるような無線媒体を含んでもよい。コンピュータ・プログラムは、特定のどのようなプログラミング言語およびその実装形態にも限定されるものではない。様々なプログラミング言語およびそのコーディングは、本明細書に含まれる開示の教示を実装するのに使用できることが理解されよう。
【００３１】
添付の図面の１つまたは複数のいずれかにおいて、符号（ｒｅｆｅｒｅｎｃｅ  ｎｕｍｅｒａｌｓ）の同じステップおよび／または特徴への参照を行っている場合、これらのステップおよび／または特徴は、この説明の目的にとっては、それに反する意図を示していない限り、機能または操作は同じである。
【００３２】
この一般にはキーワード検索、特に階層的なデータ構造の構築の諸方法の実施は、好ましくは、図１から３６のプロセスを、コンピュータ・システム３７００内部で実行されるアプリケーション・プログラムなどのソフトウェアとして実装できる、図３７に示すものなどの汎用コンピュータ・システム３７００を用いて行う。特に、キーワード検索の諸ステップは、コンピュータの実行するソフトウェアの中の命令によってもたらされる。この命令は、それぞれが１つまたは複数の特定のタスクを行うための、１つまたは複数のコード・モジュールとして形成することができる。また、このソフトウェアは、第１の部分が検索の方法を行い、第２の部分が第１の部分とユーザとの間のユーザ・インターフェースを管理する、２つの別々の部分に分割することができる。次いで、このソフトウェアは、たとえば、下で説明するストレージ装置を含むコンピュータ可読媒体に格納することができる。このソフトウェアは、そのコンピュータ可読媒体からコンピュータへとロードされ、次いで、そのコンピュータによって実行される。そのようなソフトウェアまたはコンピュータ・プログラムがその上に記録してあるコンピュータ可読媒体が、コンピュータ・プログラム製品である。そのコンピュータ内のコンピュータ・プログラム製品の使用により、好ましくは、キーワード検索および階層的なデータ構造の構築のための有利な機器がもたらされる。
【００３３】
コンピュータ・システム３７００は、コンピュータ・モジュール３７０１、キーボード３７０２やマウス３７０３などの入力装置、プリンタ３７１５、ディスプレイ装置３７１４、およびラウドスピーカ３７１７を含む出力装置によって形成される。モデム（Ｍｏｄｅｍ、Ｍｏｄｕｌａｔｏｒ−Ｄｅｍｏｄｕｌａｔｏｒ）トランシーバ装置３７１６は、コンピュータ・モジュール３７０１で使用して、たとえば、電話回線３７２１または他の機能媒体（ｆｕｎｃｔｉｏｎａｌ  ｍｅｄｉｕｍ）を介して接続可能な、通信ネットワーク３７２０との間の通信が行われる。モデム３７１６は、インターネット、および、ＬＡＮ（Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ、構内通信網）やＷＡＮ（Ｗｉｄｅ  Ａｒｅａ  Ｎｅｔｗｏｒｋ、広域通信網）など、他のネットワーク・システムへのアクセスを得るのに使用することができ、一部の実装形態では、コンピュータ・モジュール３７０１へと組み込むこともできる。
【００３４】
コンピュータ・モジュール３７０１は、通常、少なくとも１つのプロセッサ・ユニット３７０５と、たとえば半導体ＲＡＭ（ｒａｎｄｏｍ  ａｃｃｅｓｓ  ｍｅｍｏｒｙ）およびＲＯＭ（ｒｅａｄ  ｏｎｌｙ  ｍｅｍｏｒｙ）から形成される、メモリ・ユニット３７０６とを含む。また、モジュール３７０１は、ビデオ・ディスプレイ３７１４およびラウドスピーカ３７１７へと結合されるオーディオ−ビデオ・インターフェース３７０７、キーボード３７０２およびマウス３７０３、および自由選択でジョイスティック（図示せず）に対する入出力インターフェース３７１３、ならびにモデム３７１６およびプリンタ３７１５に対するインターフェース３７０８を含むいくつもの入出力（Ｉ／Ｏ）インターフェースを含む。一部の実施形態では、モデム３７１６を、コンピュータ・モジュール３７０１内部、たとえばインターフェース３７０８内部に組み込んでもよい。ストレージ装置３７０９が提供されており、通常、ハード・ディスク・ドライブ３７１０およびフロッピー・ディスク・ドライブ３７１１を含む。また、磁気テープ・ドライブ（図示せず）を使用してもよい。ＣＤ−ＲＯＭドライブ３７１２は、通常、データの非揮発性の情報源として提供されている。コンピュータ・モジュール３７０１のコンポーネント３７０５から３７１３は、通常、通信を、相互接続されたバス３７０４を介して、また当業者に知られているコンピュータ・システム３７００の従来の利用モード（ｍｏｄｅ  ｏｆ  ｏｐｅｒａｔｉｏｎ）になるような仕方で行う。ここで説明する配置を実施できるコンピュータの例としては、ＩＢＭ−ＰＣおよびその互換機、Ｓｕｎ  Ｓｐａｒｃｓｔａｔｉｏｎｓ、またはそれから発展した類似のコンピュータ・システムがある。
【００３５】
通常、アプリケーション・プログラムは、ハード・ディスク・ドライブ３７１０上にあり、プロセッサ３７０５により、その実行中に読み込みおよび制御が行われる。このプログラムおよびネットワーク３７２０からフェッチされるどのようなデータの中間ストレージも、半導体メモリ３７０６を用いて、おそらくハード・ディスク・ドライブ３７１０と協力して達成される。一部の場合には、このアプリケーション・プログラムは、ＣＤ−ＲＯＭまたはフロッピー・ディスク上にエンコードされてユーザへと供給され、対応するドライブ３７１２または３７１１を介して読み込まれるが、または代替方法として、ユーザがネットワーク３７２０からモデム装置３７１６を介して読み込むのでもよい。またさらに、このソフトウェアのコンピュータ・システム３７００へのロードは、他のコンピュータ可読媒体から行うことも可能である。本明細書で使用する「コンピュータ可読媒体」という用語は、命令および／またはデータを実行および／または処理のためにコンピュータ・システム３７００へと提供するのにあずかるどのようなストレージ媒体または伝送媒体も指す。ストレージ媒体の例としては、フロッピー・ディスク、磁気テープ、ＣＤ−ＲＯＭ、ハード・ディスク・ドライブ、ＲＯＭまたは集積回路、光磁気（ｍａｇｎｅｔｏ−ｏｐｔｉｃａｌ）ディスク、またはＰＣＭＣＩＡカードなどのコンピュータ可読カードなどがあり、そのような装置がコンピュータ・モジュール３７０１の内部または外部にあることを問わない。伝送媒体の例としては、無線または赤外線の伝送チャネルならびに別のコンピュータまたはネットワーク化装置へのネットワーク接続、電子メール転送およびＷｅｂサイト上に記録された情報を含むインターネットまたはイントラネットなどがある。
【００３６】
階層的な環境におけるキーワード検索は、その１つまたは複数のキーワードが生起する階層的なデータ構造内のノードまたは要素を識別し、次いで、他のどのような要素がそのキーワードにとって関連性が高いかを判定することを含む。典型的なキーワード検索の想定状況では、ユーザへと提示される結果のデータは、第１のデータ構造から抽出され、検索キーワードのすべてまたは一部およびこうしたキーワードにとって関連性が高いと考えられる他のデータを含む第２の階層的なデータ構造である。そのような、キーワード検索操作の結果としてユーザへと提示される階層的なデータ構造を、コンテキストツリー（ｃｏｎｔｅｘｔ  ｔｒｅｅ）と呼ぶ。
【００３７】
ＸＭＬではしばしばあることであるが、検索されている階層的なデータに支配的な（ｇｏｖｅｒｎｉｎｇ）スキーマがあるとき、一般に有利なのは、そのスキーマのレベルで動作する関連性の高いデータを識別するための方法を使用することである。すなわち、スキーマ表現内部の要素が、解析されて、検索キーワードにとって関連性が高いかどうかが判定される。次いで、関連性の高いスキーマ要素によって総体的に表現されるデータソース内のデータ項目のすべてのインスタンスが、キーワード検索操作の結果としてユーザへと返される。ＸＭＬでは、支配的なスキーマは、それ自体が別の階層的なデータ構造である、ＸＭＬ  Ｓｃｈｅｍａの形をとることが可能である。ＸＭＬ  Ｓｃｈｅｍａでは、関連するＸＭＬデータの構造、そのＸＭＬデータ内の要素および属性のリスト、およびそれらの親子関係が指定される。ＸＭＬ  Ｓｃｈｅｍａ内の要素または属性のそれぞれは、通常、ＸＭＬデータ内の要素および属性の多くのインスタンスを表現しているため、ＸＭＬ  Ｓｃｈｅｍａは、潜在的にずっと小さなデータ構造であり、このため、より効率よく解析することができる。
【００３８】
しばしば、キーワードの検索を、１つより多くの階層的なデータソースの中で行うことが望ましい。階層的なデータソースそれぞれは、それ自体はツリー構造をしているが、複数のデータソースを考慮すると、結果となるデータ構造はより一般的な形式をとる可能性がある。データベースの環境で不可避的に生じるそのようなある形式を図１に示している。この構造は、本質的に、共有ノードのあるいくつものツリーを含み、ここで、ツリーそれぞれは、別々の階層的なデータソースのスキーマを表現しており、共有ノードは、内容が複数のデータソースにわたるデータ・ビューの結果である。具体的には、図１の点線の矩形１００５および１０１０は、第１および第２のデータソースのスキーマをそれぞれ表し、ノード１０１５は、第１のデータソースからのノード１０２０および１０２５と第２のデータソースからのノード１０３０を一緒にするデータ・ビューのルート・ノードである。図１の複数の共有ツリーの構造は、本明細書ではこれをスキーマ・グラフ（ｓｃｈｅｍａ  ｇｒａｐｈ）と呼ぶが、有向非巡回グラフの特別な形式であり、どの２つのノード間にも多くとも１つの有向パスがあるという重要な特徴をもつ。たとえば、ノード１０１５からノード１０３５へは有向パスが１つしかなく、このパスはノード１０２０を通過する。
【００３９】
スキーマ・グラフは、好ましくは、キーワード検索操作の前に構築され、階層的なデータソースの初めは互いに素な個々のツリー構造をしたスキーマからなる。次いで、こうしたスキーマツリーは、１つより多くのデータソースにわたるデータ・ビューが作成されると、併合される。データ・ビューは、通常、（ＸＭＬの環境におけるＸＱｕｅｒｙなどの）問い合わせを含み、データベース管理者またはユーザが作成することができる。どちらの場合でも、データベース・システムは、好ましくは、こうした問い合わせをログまたは記録をそのストレージ装置で行う。スキーマ・グラフの構築中、ログ済みの問い合わせそれぞれのスキーマ表現が作成され、そのスキーマ・グラフへと挿入される。こうすると、２つ以上の別々のスキーマツリーの併合が、挿入されるスキーマが図１に示すこれらのツリーからのノードを含む場合には、行われることになる。スキーマ・グラフへと挿入されるスキーマが、ただ１つのデータソースからのノードしか含まないこともあり得るのであり、その場合には、別々のスキーマツリーの併合は生じない。その代わりに、挿入操作によって、単に、新しいノードがスキーマ・グラフ内の単一のスキーマツリーからの既存のノードへと追加およびリンクされることになる。
【００４０】
スキーマ・グラフの更新は、絶えず、新しい問い合わせのログのたびに行うこともでき、または新しい問い合わせおよびデータ・ビューがある期間にわたって集められた後、１つまたは複数の機会に行うこともできる。スキーマ・グラフの更新の頻度にかかわらず、キーワード検索操作が開始されると、その操作の時点で現在のものである（ｃｕｒｒｅｎｔ）スキーマ・グラフは、ユーザへと返されるデータ・ビューを判定するのに使用されるものである。この文書の残りの部分では、「スキーマ・グラフ」という用語は、キーワード検索操作が行われる時点で現在のものである（ｃｕｒｒｅｎｔ）スキーマ・グラフを指す。
【００４１】
単一のデータソースの場合でのように、複数の階層的なデータソースの内部でのキーワード検索は、まず、「ヒット」ノードと呼ばれる、検索キーワードの見つかったスキーマ・グラフの内部のノードを識別し、次いで、「コンテキスト」ノードと呼ばれる、そのヒット・ノードにとって関連性の高いノードを識別することを含む。次いで、ヒット・ノードおよびコンテキスト・ノードを含むデータ構造が構築され、ユーザへと提示される。ヒット・ノードは１つより多くのデータソースにあり得るため、ユーザへと提示される結果のデータ構造は、複数のデータソースにわたる可能性がある。また、結果のデータ構造は、その意図している適用例は階層的なデータの環境においてであるため、好ましくは、ツリー構造をしている。
【００４２】
図４に、キーワード検索操作の好ましい構成４０００および一般化された利用モード（ｍｏｄｅ  ｏｆ  ｏｐｅｒａｔｉｏｎ）を示している。構成４０００は、ネットワーク内で一緒に接続された、ＰＣクライアント４００５、データ・サーバ４０１０、データベース４０１５、キーワード検索クライアント４０２５、およびインデックス・サーバ４０３０を含む。
【００４３】
装置４００５、４０１０、４０２５、および４０３０のそれぞれは、通常、システム３７００などの対応する汎用コンピュータ・システムによって形成され、それぞれはネットワーク３７２０によってリンクされるが、これを図４にもっぱら概念的に示している。この概念的な図示を使用して、様々な装置４００５、４０１０、４０２５、および４０３０の間の、ネットワーク３７２０の両側で生じるデータ・フローの煩雑でない表現を提供している。様々な装置４００５、４０１０、４０２５、および４０３０は、必要、適当、または好都合なときには、数のより少ない別個のコンピュータ・システム３７００へとまとめることができる。たとえば、一部の実装形態では、サーバ４０１０と４０３０を組み合わせて１つのコンピュータ・システム３７００にし、クライアント４００５と４０２５を組み合わせて別のコンピュータ・システム３７００にし、それらのシステム３７００はネットワーク３７２０でリンクされるようにすることが好都合である可能性がある。
【００４４】
データベース４０１５に格納されているデータへのアクセスは、通常、ＰＣクライアント４００５でブラウズを行うユーザによって行われる。クライアント４００５内で動作するブラウズ用アプリケーションからは、コマンドの発行が、好ましくは、ＸＱｕｅｒｙ４００６の形式で行われ、次いで、これがデータ・サーバ４０１０へと送信される。ＸＱｕｅｒｙ４００６は、それぞれ、ログ４０２０に記録され、データ・サーバ４０１０によって解析され、その後、要求されたデータ４００７がデータベース４０１５からフェッチされ、ＰＣクライアントのユーザ４００５へと送付される。ある時点、好ましくは十分な量のＸＱｕｅｒｙ４００６のログが行われた後で、インデックス・サーバ４０３０が活性化され、ログ済みのＸＱｕｅｒｙ４０２０が、インデックス・テーブル４０３５を作るために解析される。このプロセスは、データベース４０１５内に格納されたデータのスキーマ・グラフ表現、および、ログ済みのＸＱｕｅｒｙ４０２０によって表現されるその既存のビューを構築し、これらのビューに関連する様々な頻度テーブルを作り、データベース内の検索可能なキーワードを識別し、１つまたは複数のコンテキストツリーの決定およびコンテキストツリーそれぞれに対応するＸＱｕｅｒｙを構築し、最後に、これらのキーワードおよびＸＱｕｅｒｙのインデックス・テーブル４０３５への記録を、後で迅速に取り出せるように行うことを含む。
【００４５】
インデックス・テーブル４０３５の作成プロセスが完了した後は、システム４０００では、キーワード検索クライアント４０２５で呼び出されたキーワード検索操作を行う準備ができている。ユーザの入力した検索キーワード４０２６は、インデックス・サーバ４０３０へと送信され、ここで、そのルック・アップがインデックス・テーブル４０３５と突き合わせて行われ、１つまたは複数のＸＱｕｅｒｙ４０３１が取り出され、検索キーワードにとっての関連性の高さに従って適切にランク付けされて、ユーザへと提示される。ユーザがＸＱｕｅｒｙ４０２７をリストから選択すると、そのＸＱｕｅｒｙ４０２７は、キーワード検索クライアント４０２５によってデータ・サーバ４０１０へと送信され、これは適切なデータ４０１１で応答する。
【００４６】
１つまたは複数の階層的なデータソースを含むキーワード検索の方法２０００を、図２のフローチャートで要約している。方法２０００は、好ましくは、インデックス・サーバ４０３０のコンピュータ上で実行される。方法２０００は、ステップ２００５で始まり、ここでスキーマ・グラフ内のヒット・ノードが識別される。ＸＭＬの環境では、ヒット・ノードがスキーマ・グラフ内で生じる可能性のある仕方が２つある。すなわち、（ｉ）その要素名が検索キーワードのうちの１つを含む可能性があり、または（ｉｉ）それが表現する１つまたは複数のＸＭＬノードが検索キーワードのうちの１つを含む可能性がある。ステップ２００５に続いて、ステップ２０１０では、スキーマ・グラフ内のヒット・ノードおよびコンテキスト・ノードで表現されるデータソース内のノードをそれぞれが含む、スキーマ・グラフ内のコンテキストツリーが識別される。最後にステップ２０１５で、識別されたコンテキストツリーがＸＱｕｅｒｙへと変換され、ランク付けされたリストとしてユーザに提示される。
【００４７】
図２のステップ２０１０の表すコンテキストツリーを識別するための方法の説明を、ここで詳細に行う。まず、スキーマ・グラフ内に単一のヒット・ノードがある特別な場合に対する方法を提示し、その後、１つより多くのヒット・ノードを含む場合を扱えるより一般的な方法が続く。どちらの方法も、２フェーズで動作する。その第１は、スキーマ・グラフのヒット・ノードからのボトム・アップ走査（ｔｒａｖｅｒｓａｌ）であって、その親および祖先のうちのどれがコンテキスト・ノードであるかを判定し、第２のフェーズは、これからトップ・ダウン的に進んで、その子孫のうちのどれが同様にコンテキスト・ノードであるかを判定する。次いで、ヒット・ノードの、コンテキスト・ノードと判定された最上位の祖先は、キーワード検索操作の結果としてユーザへと提示されるコンテキストツリーのルート・ノードに相当する。スキーマ・グラフ内のノードがコンテキスト・ノードであるかどうかを判定する目的で、好ましくは、少なくとも生起頻度テーブルおよび共起頻度テーブルが維持される。前者では、スキーマ・グラフ内の各ノードがログ済みの問い合わせまたはデータ・ビューの中で生起する頻度が記録されるのに対し、後者では、スキーマ・グラフ内のノードの対が、同じログ済みの問い合わせまたはデータ・ビューの中で共起する頻度が記録される。スキーマ・グラフが、新しいノードを含む新しい問い合わせまたはデータ・ビューで更新されると、この新しいノードに相当する新しいエントリが生起頻度テーブルに追加され、それぞれには、そのノードが新しく、それまでに観測されたことがないことを示す頻度の初期値１が与えられる。同様にして、２つの新しいノードまたは新しいノードと既存のノードを含む、新しい問い合わせからのノード対それぞれについては、新しいエントリが共起頻度テーブルに追加され、頻度の初期値１が与えられるのに対して、新しい問い合わせの中にない、新しいノードと既存のノードを含むノード対それぞれについては、新しいエントリは共起頻度テーブルに追加されるが、頻度の初期値０が与えられる。
【００４８】
スキーマ・グラフが走査される際、ヒット・ノードの生起数のもとでの、ノードごとの生起確率が計算される。こうした条件付き確率の値の計算または近似は、それまでにログの行われた問い合わせまたはデータ・ビューが原因で頻度テーブルに保存された値から行われ、あるノードがコンテキスト・ノードであるかどうかの判定に使用される。
【００４９】
以下は、単一のヒット・ノードがある特別な場合に対する第１の方法の説明である。このヒット・ノードをＸで表すことにする。
【００５０】
第１のフェーズでは、スキーマ・グラフを通してのボトム・アップ走査はノードＸを始めにして行われる。Ｘの祖先Ｙｉのそれぞれを順番に考え、そのＸの生起のもとでの生起確率を計算する。
【００５１】
【数１】
2007519086.tif 000003
【００５２】
ここで、確率の値は、生起頻度ｆｒｅｑ（Ｘ）および共起頻度ｆｒｅｑ（Ｙｉ、Ｘ）で近似されている。後者は、ＸとＹｉが共起する頻度を表し、ここでＹｉはＸの祖先である。どちらも、前に述べた生起頻度テーブルおよび共起頻度テーブルから直接に得られる。Ｘの祖先ノードに関して計算されたこれらの確率の値から、Ｘのもとで、特定の祖先Ｙｉがルート・ノードである確率を決定することが可能である。Ｚ１，．．ＺｎがＹｉの親ノードを表すとすると、
Ｐｒ［Ｙｉ  ｒｏｏｔ｜Ｘ］＝Ｐｒ［¬Ｚ１∧．．．∧¬Ｚｎ∧Ｙｉ｜Ｘ］      式２
となる。
【００５３】
すなわち、Ｘのもとで、Ｙｉがルートである確率は、Ｙｉが存在しその親のどれもが存在しない確率である。式２の右辺を展開すると、
Ｐｒ［Ｙｉ  ｒｏｏｔ｜Ｘ］＝Ｐｒ［¬Ｚ１∧．．．∧¬Ｚｎ｜Ｙｉ∧Ｘ］Ｐｒ［Ｙｉ∧Ｘ］
＝（１−Ｐｒ［Ｚ１∨．．．∨Ｚｎ｜Ｙｉ∧Ｘ］）Ｐｒ［Ｙｉ∧Ｘ］                                                                  式３
が得られる。
【００５４】
Ｚ１，．．Ｚｎは、Ｙｉが与えられると互いに排他的であることから（Ｙｉは、実際のどのような階層的なデータ構造でも、多くとも１つの親をもつことができる）、
【００５５】
【数２】
2007519086.tif 000004
【００５６】
しかし、ＺｊとＸの間には多くとも１つの有向パスしかない（スキーマ・グラフの１つの特徴）ことから、このパスはＹｉを含まなければならないことになり、これより
Ｐｒ［Ｚｊ∧Ｙｉ∧Ｘ］＝Ｐｒ［Ｚｊ∧Ｘ］      式５
⇔  Ｐｒ［Ｚｊ∧Ｙｉ｜Ｘ］＝Ｐｒ［Ｚｊ｜Ｘ］      式６
【００５７】
【数３】
2007519086.tif 000005
【００５８】
となる。
【００５９】
好ましい一実装形態では、いくつもの代替のコンテキストツリーがキーワード検索操作の結果としてユーザへと、関連づけられている確率Ｐｒ［Ｙｉ  ｒｏｏｔ｜Ｘ］が０より大きいＸの祖先ノードＹｉごとに１つ、返される。これらの代替のコンテキストツリーは、それぞれ、関連づけられている確率Ｐｒ［Ｙｉ  ｒｏｏｔ｜Ｘ］が割り当てられ、このスコアに従って、最高から最低へとソートされている。スコアがより高いコンテキストツリーは、スコアがより低いものよりもユーザにとって興味があると考えられる。一代替実施形態では、スコアが最高のコンテキストツリーだけが、キーワード検索操作の結果としてユーザへと返される。
【００６０】
コンテキストツリーのルート・ノードの役割のできる（すなわち、そのＰｒ［Ｙｉ  ｒｏｏｔ｜Ｘ］＞０）祖先ノードＹｉそれぞれについて、第２のフェーズ、すなわちＹｉからのトップ・ダウン走査が、その子孫（ヒット・ノードＸを除く）のうちのどれがコンテキスト・ノードであるかを判定するために行われる。このフェーズ中に訪問した親ノードＰｊそれぞれについて、解析が、その子のうちのどれがコンテキスト・ノードであるかを判定するために行われる。コンテキスト・ノードであると判定された子ノードそれぞれについて、その子が順番にトップ・ダウン的に解析されて、そのうちのコンテキスト・ノードが識別される。
【００６１】
親ノードＰｊの解析には、図３Ａおよび３Ｂに示すように、２つの別々の想定状況がある。第１のものは、図３Ａに示す特別な場合であり、ここでは、Ｐｊはルート・ノードＹｉ  ３００５からヒット・ノードＸ  ３０２０へのパスに沿って存在する。これには、Ｐｊ＝Ｙｉの場合が含まれるが、Ｐｊ＝Ｘの場合は除外される。この想定状況では、ＰｊからＸへのパスに沿って存在する、Ｐｊ  ３０１０の少なくとも１つの子ノード、すなわちこの場合では子ノードＣｉ３０１５が、コンテキスト・ノードとして識別されなければならない。より一般的な、第２の想定状況では、図３に示すように残りの場合すべてを包摂しているが、親ノードＰｊ  ３０３０は、ルート・ノードＹｉからヒット・ノードＸ  ３０３５への有向パスに沿っては存在せず、このため、Ｐｊのどれかの子ノードをコンテキスト・ノードとして識別することは義務的ではない。この第２の想定状況を扱うためのアルゴリズムを最初に提示することにする。
【００６２】
所与のヒット・ノードＸ、および、コンテキストツリーのルート・ノードの役割をする特定のノードＹｉに関して、親ノードＰｊのある子ノードＣｋをコンテキスト・ノードとして識別すべきかどうかを選ぶことは、一般に、ＹｉからＸへの有向パスに沿ったノードすべての存在のもとで、Ｃｋが生起する確率の関数
Ｐｒ［Ｃｋ｜Ｘ∧．．．∧Ｙｉ  ｒｏｏｔ∧．．．∧Ｐｊ］
である。
【００６３】
この確率の評価または推定は、前にふれた生起および共起の頻度テーブルだけでは可能ではないため、何らかの形の単純化または近似が必要である。採用することが好ましいそのような単純化の１つは、上の確率の式の中のＹｉからＣｋまでのノード以外のノードすべての影響を無視することであり、次の式
Ｐｒ［Ｃｋ｜Ｙｉ  ｒｏｏｔ∧．．．∧Ｐｊ］
ここで
【００６４】
【数４】
2007519086.tif 000006
【００６５】
Ｚｌ、ｌ＝１，．．．，ｐがＹｉの親ノードを表すとすると、式８の右辺は、
【００６６】
【数５】
2007519086.tif 000007
【００６７】
と展開することができる。
【００６８】
しかし、上の式は、個々の子ノードＣｋそれぞれを孤立して扱っているのにすぎない。Ｃｋが（Ｙｉ  ｒｏｏｔのもとで）互いに独立ない限りは、それらの同時確率を考える必要がある。しかし、これには、ノードからなる大量の組合せの同時生起頻度を格納する頻度テーブルを維持することが必要であるが、そのうちの多くは、ほとんど観測されず、そのため、その同時確率の信頼できる推定をその同時生起頻度から行うことは可能ではないはずである。他方、（Ｙｉ  ｒｏｏｔのもとで）Ｃｋの間の独立を仮定すると、子ノードＣｋが、その個々の（Ｙｉ  ｒｏｏｔのもとでの）生起確率が低い場合に、どれも選択されないなどの望ましくない結果がもたらされる。
【００６９】
Ｃｋの間の独立の過程の望ましくない影響を避ける一方で、同時に、大量の同時生起頻度の値を維持する必要性を避けるために、図５のフローチャートで示すヒューリスティックな方法５０００を、子ノードをコンテキスト・ノードとして選択するのに使用することができる。方法５０００は、好ましくは、サーバ４０３０上の方法２０００内部のサブプログラムとして動作する。
【００７０】
方法５０００は、ステップ５００５で始まり、ここで、Ｑｋ＝Ｐｒ［Ｃｋ｜Ｙｉ  ｒｏｏｔ∧．．．∧Ｐｊ］で表される、ルート・ノードＹｉのもとでの子ノードＣｋそれぞれの生起確率の計算が、式８および式９を用いて行われる。次のステップ５０１０で、確率Ｑｋが子ノードＣｋすべてにわたって総計されるが、その総和はＴで表される。方法５０００は継続され、ステップ５０１５で確率の値が最も大きいノードＣｋがコンテキスト・ノードとして選択される。確率の値が同じで最大である子ノードが１つより多くある場合は、そのようなノードはすべてコンテキスト・ノードとして選択される。次いで、それまでにコンテキスト・ノードとして選択された子ノードすべての確率の総和Ｓの計算が、ステップ５０２０で行われる。次いで、実行は判断ステップ５０２５へと進み、このポイントで、子ノードＣｋがすべてコンテキスト・ノードとして選択されている場合には、方法はステップ５０４０で終了する。しかし、まだコンテキスト・ノードとして選択されていない１つまたは複数の子ノードＣｋがある場合は、方法５０００はもう１つの判断ステップ５０３０へと続く。ステップ５０３０で、Ｓ≧Ｔ／２かどうかを確かめるために検査が行われ、そうである場合、方法はここでもステップ５０４０で終了する。Ｓ＜Ｔ／２である場合、実行はステップ５０３５へと進む。ここでは、現在まだコンテキスト・ノードとして選択されていない子ノードＣｋのリストが検査されて、そのうちで確率が最大のものが識別される。それがコンテキスト・ノードとして選択され、方法５０００は、ステップ５０２０へと戻って、上で論じたような処理をさらに行う。
【００７１】
方法５０００には、いくつもの望ましい特徴がある。すなわち、
・ログ済みの問い合わせまたはデータ・ビューに共通部分があって頻度が十分に高い（すなわち、比較的多数の子ノードが共通にある）場合、方法５０００はその共通部分をコンテキスト・ノードとして返す傾向がある。これからは、十分に大きな共通部分は（ヒット・ノードに関する）十分なコンテキスト情報を担う傾向があるため、容認できる結果がもたらされそうである。
【００７２】
・ログ済みの問い合わせまたはデータ・ビューに、共通に比較的少数の子ノードしかなかった場合、結果となるコンテキスト・ノードの組は、その共通部分だけでなくさらに別のノードも含む傾向がある。発明者の行った実験では、結果となるコンテキストの子ノードの組は、頻度が最も高いログ済みの問い合わせまたはデータ・ビューのそれを反映する傾向がある。このことは、共通部分だけでは十分なコンテキスト情報を含むことはありそうにないであろうから、重要である。
【００７３】
・確率の値が等しく最大である子ノードをまとめて含めることが原因で、方法５０００は、ノードのコンテキスト・ノードとしての識別を、少なくではなく多く行う方へのバイアスをもつ。ログ済みの問い合わせの中にある子ノードの組が互いに排他的であり等しい頻度で生じる場合には、この方法では、子ノードすべてがコンテキスト・ノードとして識別される。
【００７４】
方法５０００では、親ノードがコンテキスト・ノードと同じであるときには、その子のうちの１つまたは複数も、必ずコンテキスト・ノードとして識別される。このことは、親ノードが、まったく子がない状態で生じる（すなわち、葉ノードとして生じる）ログ済みの問い合わせまたはデータ・ビューが数多くある場合には、望ましくない。直観的には、これが十分しばしば生じる場合には、その親ノードだけを、まったく子がないコンテキスト・ノードとして識別して、頻繁に観察される振る舞いを反映させるべきである。
【００７５】
この問題点を改善するために、好ましい一実装形態では、インデックス・サーバ４０３０の生成および保存する追加の葉共起頻度テーブルを利用する。このテーブルでは、ノードＰｊが、葉ノードとして過去のログ済みの問い合わせおよびデータ・ビュー内でその祖先Ｙｉと共起している頻度を、スキーマ・グラフ内に子のないノードＰｊを除き、そのようなノードＰｊとＹｉのあらゆる可能な対に対して保存する。次いで、この新しい頻度テーブルを使用して、Ｐｊおよびあるルート・ノードＹｉのもとで、ノードＰｊが葉ノードとして生起する確率
【００７６】
【数６】
2007519086.tif 000008
【００７７】
が推定される。ここで、Ｚｌ、ｌ＝１，．．．，ｐは、前に定義したようにＹｉの親ノードを表し、ｆｒｅｑ（Ｙｉ，Ｐｊ  ｌｅａｆ）およびｆｒｅｑ（Ｚｊ，Ｐｊ  ｌｅａｆ）は、新しい葉共起頻度テーブルから得られる共起頻度の値である。
【００７８】
確率Ｐｒ［Ｐｊ  ｌｅａｆ｜Ｙｉ  ｒｏｏｔ∧Ｐｊ］は、好ましくは、図５に与える方法５０００に先立つ追加の判断ステップで決定され、Ｐｊのどの子ノードがコンテキスト・ノードであるかが識別される。Ｐｒ［Ｐｊ  ｌｅａｆ｜Ｙｉ  ｒｏｏｔ∧Ｐｊ］が０．５より小さい場合は、Ｐｊの子ノードはコンテキスト・ノードとしては選択されず、そうでない場合は、方法５０００が行われて、どの子ノードがコンテキスト・ノードであるかが識別される。
【００７９】
代替実施形態も可能であり、そこでは、フローチャートを図６に与えている代替の方法６０００を使用して、１組の子ノードＣｋ、ｋ＝１，．．．，ｍのうちでコンテキスト・ノードが選択される。方法６０００は、これもインデックス・サーバ４０３０で行われるが、ステップ６００１で始まり、そこでは、概念上、架空の子ノードＣ０が作成され、実際の子ノードＣ１，．．．，Ｃｍからなるリストへと追加され、確率値Ｐｒ［Ｐｊ  ｌｅａｆ｜Ｙｉ  ｒｏｏｔ∧Ｐｊ］が式１０を用いて割り当てられる。次のステップ６００５で、実際の子ノードＣｋには、その通常の確率値Ｑｋ＝Ｐｒ［Ｃｋ｜Ｙｉ  ｒｏｏｔ∧Ｐｊ］が式８および式９を用いて割り当てられる。次いで、方法６０００は継続され、ステップ６００６で、方法５０００をステップ５０１０で呼び出して（ステップ５００５を飛ばして）子ノードＣ０，．．．，Ｃｍのうちで１組のコンテキスト・ノードを選択する。方法５０００を抜けると、方法６０００は再開され、判断ステップ６０１０で検査が行われて、架空の子ノードＣ０がコンテキスト・ノードとして選択されたかどうかが判定される。そうである場合、実行は継続され、ステップ６０２０で、Ｃ０がコンテキスト・ノードとして除外される。方法６０００は、その後、ステップ６０１５で終了する。検査が６０１０で失敗した場合、方法６０００は、直接に終了ステップ６０１５へと進む。
【００８０】
Ｐｊの子ノードのうちのどれもコンテキスト・ノードではないという可能性を組み込むための代替の方法６０００の背後にある考え方は、第１の方法と本質的に同じである。すなわち、Ｐｒ［Ｐｊ  ｌｅａｆ｜Ｙｉ  ｒｏｏｔ∧Ｐｊ］が十分に大きいときである。しかし、コンテキスト・ノードの最終的なセットに対するＰｒ［Ｐｊ  ｌｅａｆ｜Ｙｉ  ｒｏｏｔ∧Ｐｊ］の影響は、この代替のアプローチでは、よりゆるやかであり、一般に、第１のアプローチでの急激なオン・オフの切り替えよりも好適である。
【００８１】
親ノードＰｊがルート・ノードＹｉからヒット・ノードＸへの有向パスに沿って存在する特別な想定状況では、ＰｊからＸへのパスに沿って存在するＰｊの子ノードがコンテキスト・ノードとして識別されるように、特別な考慮がなされなければならない。一般性を失うことなく、この子ノードを、図３に項目３０１５として示すＣ１とする。前に提示した一般的な想定状況用の方法５０００は、（たとえば、Ｃ１の生起確率を他の子ノードすべてのそれを上回るように、ステップ５０１５の前に、吊り上げておくことによって）変更が可能であるが、そのようなアプローチは正しい結果を生じない可能性がある。その理由は、説明した方法５０００は、ルートＹｉおよび親Ｐｊのもとでコンテキスト・ノードとして最も頻繁に生起する子ノードの組を選択するように工夫されているためである。この組が自然にＣ１を含まない場合、それは基本的に、Ｃ１がその組の中のノードと関係がないことを意味している。Ｃ１を無理に含めても、ただ、共通するところが少ししかない子ノードの組ができてしまい、Ｃ１に対する（またその後Ｘに対する）コンテキストは少ししか得られないはずである。
【００８２】
方法５０００を変更する代わりに、好ましくは、異なるが手続き的にはいくぶん似ている、図７に示す方法７０００が、別の実装形態では採用される。新しい７０００と以前の５０００の間の違いは、使用される確率の独立性の仮定にある。ＰｊがＹｉからＸへの有向パスに沿って存在しない、一般的な場合に行った第１の単純化が、
Ｐｒ［Ｃｋ｜Ｘ∧．．．∧Ｙｉ  ｒｏｏｔ∧．．．∧Ｐｊ］
は、ＹｉからＰｊまでのノード以外のノードとは独立であるという仮定であったことを想起されたい。Ｐｊの１つの子ノードＣ１がＸからＰｊへのパスに沿って存在するという現在の想定状況では、Ｃｋが（Ｃ１を含めて）ＰｊからＸまでのノードとは独立であると仮定することは、これらがヒット・キーワードＸをＣｋにリンクするＸの必要な祖先であることから、賢明ではあるまい。問題を扱いやすくしておくには単純化がいくつか必要であるため、ＣｋとそのＰｊより上位のルート・ノードＹｉに向かう祖先の間の確率の独立性を仮定することはよい選択肢ということになる。この仮定のもとで、興味の対象となる確率は、
Ｐｒ［Ｃｋ｜Ｘ∧．．．∧Ｃ１∧Ｐｊ］    ｋ≠１
である。
【００８３】
再び、ＸとＰｊをリンクする有向パスが多くとも１つあるため、上の式は
【００８４】
【数７】
2007519086.tif 000009
【００８５】
に等しい。
【００８６】
式１１の右辺の分子は、２つではなく３つのノードを含んでいる以上、これまでにふれた生起および共起の頻度テーブルからは得ることができない。したがって、ノードの３つ組（３−ｔｕｐｌｅ）の間の、追加の同時生起頻度テーブルが必要である。さいわい、こうした３つ組は、（ノードの任意のどの対もではなく）親子ノードＣｋとＰｊからなる対を含んでおり、各ノードＣｋには、実際には、少数の親しかないため、新しい同時生起頻度テーブルは、ノードの対を含む共起頻度テーブルよりも、わずかに大きいのにすぎないはずである。
【００８７】
新しい同時生起頻度テーブルにより、Ｐｒ［Ｃｋ｜Ｘ∧Ｐｊ］は
【００８８】
【数８】
2007519086.tif 000010
【００８９】
と推定することができ、ここで、ｆｒｅｑ（Ｃｋ，Ｐｊ，Ｘ）は、ノードＣｋ、Ｐｊ、およびＸの間の同時生起頻度を表し、ＰｊはＣｋの親でＸの祖先であり、ＣｋはＸでもＸの祖先でもない。
【００９０】
Ｃ１とともにコンテキスト・ノードとして含めるべきＣ１の兄弟（ｓｉｂｌｉｎｇｓ）からなる組を決定するための方法７０００は、すでに説明した方法５０００に非常に似ている。方法７０００は、ステップ７００１で始まり、ここでは、Ｑｋ＝Ｐｒ［Ｃｋ｜Ｘ∧Ｐｊ］で表される、親ノードＰｊおよびヒット・ノードＸのもとでの各子ノードＣｋ≠Ｃ１の生起確率の計算が式１２を用いて行われる。次のステップ７００５で、確率Ｑｋが子ノードＣｋ≠Ｃ１すべてにわたって総計されるが、その総和はＴで表される。方法７０００は継続され、ステップ７０１０で、ノードＣ１がコンテキスト・ノードとして選択され、次いでその後ステップ７０１５で、確率の値が最大のＣｋ≠Ｃ１もコンテキスト・ノードとして選択される。確率の値が最大で同じ子ノードが１つより多く存在する場合は、そのようなノードはすべてコンテキスト・ノードとして選択される。次いで、Ｃ１を除きそれまでにコンテキスト・ノードとして選択した子ノードすべての確率の総和の計算を、ステップ７０２０で行い、その総和はＳで表される。次いで、実行は、判断ステップ７０２５へと進み、このポイントで、子ノードＣｋがすべてコンテキスト・ノードとして選択されている場合、方法７０００は、ステップ７０４０で終了する。しかし、１つまたは複数の子ノードＣｋがまだコンテキスト・ノードとして選択されていない場合は、この方法は、別の判断ステップ７０３０へと続く。ステップ７０３０で、検査を行ってＳ≧Ｔ／２であるかどうかを確かめ、そうである場合は、方法７０００は、ここでも、ステップ７０４０で終了する。Ｓ＜Ｔ／２である場合は、実行はステップ７０３５へと進む。ここで、現在まだコンテキスト・ノードとして選択されていない子ノードＣｋ≠Ｃ１からなるリストが検査されて、それらのうちで確率の値が最大のものが識別される。これらは、コンテキスト・ノードとして選択され、方法は、処理をさらに行うためにステップ７０２０へと戻る。
【００９１】
Ｃ１の兄弟が解に含まれていない場合を見越して、方法７０００にいくつかの変更が必要である。これは、ノードＰｊが、過去のログ済みの問い合わせおよびデータ・ビューにＰｊの子ノードが１つしかない（ＰｊからＸへのパスに沿うＣ１）ようなその子孫Ｘのうちの１つと共起する頻度の格納されている単独子共起頻度テーブルを導入することによって達成される。次いで、この頻度テーブルを使用して、親Ｐｊおよびヒット・ノードＸのもとでＣ１に兄弟がない確率
【００９２】
【数９】
2007519086.tif 000011
【００９３】
が推定され、ここで、ｆｒｅｑ（Ｐｊ  ｈａｓ  １  ｃｈｉｌｄ，Ｘ）は、Ｐｊがその子孫Ｘと共起し、Ｐｊに単一の子ノード（Ｃ１）がある頻度を表しており、新しい頻度テーブルから得られる。
【００９４】
ある実装形態では、確率Ｐｒ［Ｃ１  ｎｏ  ｓｉｂｌｉｎｇ｜Ｐｊ∧Ｘ］を、図７に与えている方法７０００に先立つ追加の判断ステップで使用して、Ｐｊのどの子ノードがコンテキスト・ノードであるかが識別される。Ｐｒ［Ｃ１  ｎｏ  ｓｉｂｌｉｎｇ｜Ｐｊ∧Ｘ］が０．５より小さい場合は、Ｃ１以外のＰｊの子ノードはコンテキスト・ノードとして選択されず、そうでない場合は、方法７０００が行われてどの子ノードがコンテキスト・ノードであるかが識別される。
【００９５】
代替実施形態も可能である。ここでは、フローチャートを図８に与えている代替の方法８０００を使用して、１組の子ノードＣｋ、ｋ＝１，．．．，ｍのうちでコンテキスト・ノードが選択される。方法８０００は、ステップ８００１で始まり、そこでは、概念上、架空の子ノードＣ０が作成され、実際の子ノードＣ１，．．．，Ｃｍからなるリストへと追加され、確率値Ｑ０＝Ｐｒ［Ｃ１  ｎｏ  ｓｉｂｌｉｎｇ｜Ｐｊ∧Ｘ］が式１３を用いて割り当てられる。ステップ８００５で、Ｃ１を除く実際の子ノードＣｋには、その通常の確率値Ｑｋ＝Ｐｒ［Ｃｋ｜Ｘ∧Ｐｊ］が式１１を用いて割り当てられる。次いで、方法８０００は継続され、ステップ８００６で、方法７０００をステップ７００５で呼び出して（ステップ７００１を飛ばして）子ノードＣ０，．．．，Ｃｍのうちで１組のコンテキスト・ノードを選択する。方法７０００を抜けると、方法８０００は再開され、判断ステップ８０１０で検査が行われて、架空の子ノードＣ０がコンテキスト・ノードとして選択されたかどうかが判定される。そうである場合、実行は継続され、ステップ８０２０で、Ｃ０がコンテキスト・ノードとして除外される。方法８０００は、その後、ステップ８０１５で終了する。検査が８０１０で失敗した場合、方法８０００は、直接に終了ステップ８０１５へと進む。
【００９６】
これまでの議論で、コンテキスト・ノードである１組の子ノードから決定するための２つの異なる方法６０００および８０００を説明している。好ましくは、後者は、親ノードＰｊがルート・ノードＹｉからヒット要素Ｘへの有向パスに沿って存在する想定状況で適用されるのに対し、前者は他の親ノードすべてに対して使用される。一代替実装形態では、第１の方法６０００は、ＰｊがＹｉからＸへのパスに沿って存在する場合でも使用される。これからＣ１を含む１組のコンテキストの子ノードができる場合は、その組が採用されるが、そうでない場合は、その組は捨てられ、第２の方法８０００が、コンテキストの子ノードからなる新しい組を決定するために適用される。この第１の方法の有利さの背後にある理論的根拠は、そこで計算される確率の値が条件としているのが、ルート要素Ｙｉであり、ヒット・ノードＸではないことである。本発明者の行った試験は、データ・ビューのルート要素が、どのようなノードがそのビュー内にあるかのよりよい指標であることを示唆するように思われる。
【００９７】
本明細書で開示するキーワード検索システム４０００は、学習システムの一形式である。ログ済みの問い合わせおよび既存のデータ・ビューの組、これはトレーニングの例に似ているが、これからシステムは、データの新しいビューを合成することができる。ログ済みの問い合わせまたはデータ・ビューの中にパターンが存在する場合、そのパターンは頻度テーブルの中に反映され、これが今度はシステム４０００の振る舞いに影響することになる。どのような学習システムにとっても望ましい特徴は、その学習システムが、関係があるがまだ見たことのない問題を扱うときに、１組の問題から学習したパターンを使用してそのパフォーマンスを改善することができる何らかの形の一般化を行う能力である。階層的な環境で重要な一般化の１つの側面は、データの特定の下位構造の生起パターンを観察し、それを他の類似または同一の下位構造へと一般化する能力である。
【００９８】
図９に示すデータ構造９０００を考えるが、この中には、２つの同じ従業員（Ｅｍｐｌｏｙｅｅ）下位構造９０１０および９０３０が（点線の曲線で囲まれている）、１つは管理職（Ｍａｎａｇｅｒ）９００５の下に、もう１つはプロジェクト・メンバー（Ｐｒｏｊｅｃｔ  Ｍｅｍｂｅｒ）９０２５の下にある。ログ済みの問い合わせまたはデータ・ビューすべての中で、第１のＥｍｐｌｏｙｅｅサブツリー内の下位要素の名（ＦｉｒｓｔＮａｍｅ）９０１５および姓（ＬａｓｔＮａｍｅ）９０２０が、ともに現れることがすでに観察されているのに対して、第２の従業員（Ｅｍｐｌｏｙｅｅ）サブツリー９０３０を含む問い合わせまたはデータ・ビューはまだ何も観察されていないとする。さらに、従業員の名前に対するキーワード検索操作が呼び出されて、「ヒット」が第２の従業員（Ｅｍｐｌｏｙｅｅ）サブツリー９０３０の名（ＦｉｒｓｔＮａｍｅ）下位要素９０３５の中で見つかり、９０３５がヒット・ノードになっているとする。たとえ、この下位要素が存在する問い合わせまたはビューの例に出遭っていなくても、第１の従業員（Ｅｍｐｌｏｙｅｅ）サブツリー９０１０に関して観察された生起パターンから、第２の従業員（Ｅｍｐｌｏｙｅｅ）サブツリー９０３０内の下位要素の姓（ＬａｓｔＮａｍｅ）９０４０をコンテキスト・ノードとして識別すべきであることは、直観的に明らかである。
【００９９】
そのような一般化の能力は、ＸＭＬデータの作業を行うときには、同一のデータ下位構造が、しばしば、データ階層内のいくつかの場所に存在するため（たとえば、参照されるスキーマ要素を使用する結果として）、特に重要である。そのようなものは、確率平均化（ｐｒｏｂａｂｉｉｔｙ  ａｖｅｒａｇｉｎｇ）を通して実現することができる。確率平均化の動作は、スキーマ・グラフ内で名前またはＩＤまたはラベルが同一のノードの生起確率を適切に平均することによって行われる。ここで、確率平均化の適用の説明を、まずコンテキストツリーの構築の第１のトップ・ダウンのフェーズについて、そうしてその後で第２のボトム・アップのフェーズについて行う。
【０１００】
第１のフェーズの動作は、確率の値Ｐｒ［Ｙｉ｜Ｘ］を利用していることを想起されたい。ここで、Ｙｉはヒット・ノードＸの祖先である。確率平均化を容易にするために、Ｐｒ［Ｙｉ｜Ｘ］を、好ましくは、次のように漸化式（ｉｎｃｒｅｍｅｎｔａｌ  ｆｏｒｍ）へと定式化し直す。すなわち、Ｗを、ＹｉからＸへの唯一の有向パスに沿って存在する、Ｙｉの子とする。すると、Ｐｒ［Ｙｉ｜Ｘ］を
【０１０１】
【数１０】
2007519086.tif 000012
【０１０２】
のように書き直すことができる。
【０１０３】
すなわち、Ｐｒ［Ｙｉ｜Ｘ］は、その子ノードＷの確率の値、すなわちＰｒ［Ｗ｜Ｘ］から漸進的に得ることができる。考え方は、手続きをヒット・ノードＸで始め、上の式を利用して、次々に上位の祖先ノードに対する確率の値を得ることである。各ステップで、そのときに確率平均化の方法が、式１４の右辺の第１項に適用される。たとえば、Ｐｒ’［Ｂ｜Ｘ］が、あるノードＢの確率平均化の結果としての変更後の確率の値を表すとすると、Ｐｒ’［Ｙｉ｜Ｘ］を、次の再帰式（ｒｅｃｕｒｓｉｖｅ  ｆｏｒｍｕｌａｅ）で定義することができる。すなわち
Ｐｒ’［Ｘ｜Ｘ］＝１    式１５
【０１０４】
【数１１】
2007519086.tif 000013
【０１０５】
ここで
【０１０６】
【数１２】
2007519086.tif 000014
【０１０７】
であり、これが表すのは、（Ｙｉ，Ｘ）に等しい（ｋのある値に対する）ノードの対（Ｙｉｋ，Ｘｋ）すべてにわたって、Ｘ０およびＹｉ０（すなわち、ｋ＝０）をそれぞれＸおよびＹｉの別名（ａｌｉａｓｅｓ）として計算した、ＷおよびＸのもとでのＹｉの重み付け平均（ａｖｅｒａｇｅ  ｏｒ  ｍｅａｎ）確率である。これらの等しい対（Ｙｉｋ，Ｘｋ）のそれぞれに対して、総和の中の項Ｗｋは、ＹｉｋからＸｋへの有向パスに沿って存在する、Ｙｉｋのすぐ下の（ｉｍｍｅｄｉａｔｅ）子を表す。
【０１０８】
ノード対（Ｙｉｋ，Ｘｋ）がノード対（Ｙｉ，Ｘ）に等しいというのは、
（ｉ）Ｙｉｋの名前またはラベルまたはＩＤがＹｉと同じであり、Ｘｋの名前、ラベル、またはＩＤがＸと同じである、
（ｉｉ）ＹｉｋとＸｋの間に直接の祖先−子孫関係があり、ＹｉとＸの間でも同様である、
（ｉｉｉ）ＹｉｋからＸｋへの有向パスに沿うノードＷｋそれぞれに対して、（Ｗｋ，Ｘ）が（Ｗ，Ｘ）に等しく、（Ｙｉ，Ｗｋ）が（Ｙｉ，Ｗ）に等しいようなＹｉからＸへの有向パスに沿う対応するノードＷがなければならない、
（ｉｖ）ＹｉとＹｉｋにちょうど同じ数の親があり、Ｙｉの親Ｚｊそれぞれに対して、（Ｚｋｊ，Ｙｉｋ）および（Ｚｊ，Ｙｉ）が上の条件（ｉ）から（ｉｉｉ）を満たすようなＹｉｋの親Ｚｋｊがある
場合である。
【０１０９】
すると、確率平均化が原因で変更された、ＸのもとでＹｉがルートである確率は、
【０１１０】
【数１３】
2007519086.tif 000015
【０１１１】
ここで、式１６から、ＹｉをＺｊで、ＷをＹｉで置き換えることによって得られるように、
Ｐｒ’［Ｚｊ｜Ｘ］＝Ｐｒｍｅａｎ［Ｚｊ｜Ｙｉ∧Ｘ］Ｐｒ’［Ｙｉ｜Ｘ］    式１９
である、
式１７の右辺の分母が０である場合、これはログ済みの問い合わせおよびデータ・ビューでノード対（Ｗｋ，Ｘｋ）のうちのどれも観察されていないことを示すが、式１７、したがって式１９および式１８は不定（ｕｎｄｅｆｉｎｅｄ）となり、したがって、コンテキスト・ノードを識別するための何らかの代替方法が必要になる。好ましい一アプローチは、Ｐｒｍｅａｎ［Ｚｊ｜Ｙｉ∧Ｘ］の代替の定義を、次のように、Ｚｊのヒット・ノードＸからの距離によって行うことである。すなわち
【０１１２】
【数１４】
2007519086.tif 000016
【０１１３】
ここで、ｄｍａｘはある閾値の定数であり、ｄｉｓｔ（Ａ，Ｂ）は、２つのノードＡとＢの間のスキーマ・グラフ内での距離であり、ＡとＢの間のパスに沿うリンクの数として定義される。関連性の高い過去のログ済みの問い合わせおよびデータ・ビューがない場合は、２つのノードの間の距離によって、それらが互いにどう関係しているかのよい表示が与えられるが、これは、実際には、関係のあるデータは、普通、互いに近くに保存されているためである。
【０１１４】
ヒット・ノードＸの祖先ノードＹｉがコンテキストツリーのルート・ノードである確率の計算を、確率平均化によって、祖先ノードＹｉすべてについて行うための方法１００００のフローチャートを、図１０に示している。方法１００００は、ステップ１０００１で、Ｙｉ＝Ｘ、したがってＰｒ’［Ｙｉ｜Ｘ］＝１として始まる。次のステップ１０００５で、式１９および式２０を使用して、Ｐｒ’［Ｚｊ｜Ｘ］の計算がＹｉの親ノードＺｊそれぞれに対して行われる。ステップ１０００５の後、ステップ１００１０では、Ｐｒ’［Ｙｉ  ｒｏｏｔ｜Ｘ］の計算が式１８に従って行われる。次いで、ステップ１００２５では、検査が、Ｙｉの親ノードすべてが処理されているかどうかを判定するために行われる。そうでない場合、方法１００００は、ステップ１００１５へと進み、ここで、Ｙｉの親ノードＺｊが選択される。ステップ１００２０に到達すると、方法１００００は、ステップ１０００５で（ステップ１０００１を飛ばして）再帰的に、ただし選択した親ノードＺｊがＹｉの役割を果たす状態で呼び出される。この呼び出しが戻ると、方法１００００の現在の実行は再開され、ステップ１００２５へと戻って、親ノードがまだあるかの検査が行われる。親ノードがすべて処理されてしまうと、方法１００００は、ステップ１００３０で終わる。
【０１１５】
確率平均化は、第２のトップ・ダウン走査のフェーズにも適用される。このフェーズで、親ノードＰｊがルート・ノードＹｉからヒット・ノードＸへの有向パスに沿って存在しない一般の場合には、確率平均化を第１のフェーズで使用したのと同じ方法で適用することができる。キーワード検索の結果にコンテキスト・ノードとして含めるためのＹｉの子ノードＣｋの選択は、確率
Ｐｒ［Ｃｋ｜Ｙｉ  ｒｏｏｔ∧Ｐｊ］
に基づく。確率平均化によって、上の式は、平均確率
【０１１６】
【数１５】
2007519086.tif 000017
【０１１７】
によって置き換えられるが、ここで、（Ｙｉｈ，Ｃｋｈ）は（Ｙｉ，Ｃｋ）に等しく、（Ｐｊｈ，Ｃｋｈ）は（Ｐｊ，Ｃｋ）に等しく、Ｙｉ０、Ｃｋ０、およびＰｊ０（すなわち、ｈ＝０）はそれぞれ、Ｙｉ、Ｃｋ、およびＰｊの別名とする。ＺｊをＹｉの親、同様にＺｊｈをＹｉｈの対応する親とする。上の式を展開して
【０１１８】
【数１６】
2007519086.tif 000018
【０１１９】
にすることができる。
【０１２０】
上の式が平均確率Ｐｒｍｅａｎ［Ｃｋ｜Ｙｉ  ｒｏｏｔ∧Ｐｊ］の正確な近似であるためには、右辺の分母が十分に大きくなければならない（たとえば、＞ある正定数ｆｍｉｎ）。そうでないときには、好ましい一実装形態において採用された好ましい改善方法を使用して、まずＰｒｍｅａｎ［Ｃｋ｜Ｙｉ  ｒｏｏｔ∧Ｐｊ］が、Ｐｒｍｅａｎ［Ｃｋ｜Ｙｉ∧Ｐｊ］で近似され、ここで、確率は、Ｙｉ  ｒｏｏｔ∧Ｐｊでなく、Ｙｉ∧Ｐｊを条件としている。こうして
【０１２１】
【数１７】
2007519086.tif 000019
【０１２２】
式２３の右辺の分母がやはり十分に大きくない場合は、Ｐｒｍｅａｎ［Ｃｋ｜Ｙｉ∧Ｐｊ］はさらに、ＹｉではなくＷを条件とする確率で近似され、ここで、ＷはＹｉのすぐ下の子であり、Ｃｋの祖先である。すなわち
【０１２３】
【数１８】
2007519086.tif 000020
【０１２４】
この方法は繰り返して、さらに、右辺の分母に十分に大きな値が得られるまで、そうでない場合は、ＷがＣｋの親を表すまで行われる。後者の場合、Ｐｒｍｅａｎ［Ｃｋ｜Ｙｉ  ｒｏｏｔ∧Ｐｊ］への値の割り当ては、ＣｋとＹｉの間の距離に基づいて
【０１２５】
【数１９】
2007519086.tif 000021
【０１２６】
または、Ｃｋとヒット・ノードＸの間の距離に基づいて
【０１２７】
【数２０】
2007519086.tif 000022
【０１２８】
のように行われる。
【０１２９】
Ｐｒｍｅａｎ［Ｃｋ｜Ｙｉ  ｒｏｏｔ∧Ｐｊ］の近似が、最終的に式２２、式２３、式２４、式２５、または式２６で行われたのに応じて、ルート・ノードＹｉのもとで、親ノードＰｊにコンテキストの子ノードがない平均確率の計算は、それぞれ、式２７、式２８、式２９、式３０、または式３１を用いて行われる。
【０１３０】
【数２１】
2007519086.tif 000023
【０１３１】
【数２２】
2007519086.tif 000024
【０１３２】
【数２３】
2007519086.tif 000025
【０１３３】
【数２４】
2007519086.tif 000026
【０１３４】
【数２５】
2007519086.tif 000027
【０１３５】
ルート要素Ｙｉのもとでの親ノードＰｊに対するコンテキストの子ノードの決定を、ＰｊがＹｉからヒット・ノードＸへの有向パスに沿って存在しない一般の場合について、確率平均化によって行うための好ましい手続きは、図６に示すものに類似しており、これを図１３に示している。方法１３０００は、ステップ１３００１で始まり、そこでは、概念上、架空の子ノードＣ０が作成され、実際の子ノードＣ１，．．．，Ｃｍからなるリストへと追加され、確率値Ｑ０＝Ｐｒｍｅａｎ［Ｐｊ  ｌｅａｆ｜Ｙｉ  ｒｏｏｔ∧Ｐｊ］が、式２７、式２８、式２９、式３０、または式３１を用いて計算されて割り当てられ、次のステップ１３００５で、実際の子ノードＣｋには、それに対応して、確率値Ｑｋ＝Ｐｒｍｅａｎ［Ｃｋ｜Ｙｉ  ｒｏｏｔ∧Ｐｊ］が、それぞれ、式２２、式２３、式２４、式２５、または式２６を用いて計算されて割り当てられる。どの場合でも、ステップ１３００６がステップ１３００５に続き、方法５０００をステップ５０１０で呼び出して（ステップ５００５を飛ばして）、子ノードＣ０，．．．，Ｃｍのうちで１組のコンテキスト・ノードを選択する。方法５０００を抜けると、方法１３０００は再開され、判断ステップ１３０１０で検査が行われて、架空の子ノードＣ０がコンテキスト・ノードとして選択されたかどうかが判定される。そうである場合、実行は継続され、ステップ１３０２０で、Ｃ０がコンテキスト・ノードとして除外される。方法１３０００は、その後、ステップ１３０１５で終了する。検査が１３０１０で失敗した場合、この方法は、直接に終了ステップ１３０１５へと進む。
【０１３６】
方法１３０００および６０００は、そのキーワード検索での用途とは別に、階層的なデータの選択的な提示の手段としても使用することができる。すでに論じたように、実際の階層的なデータソースは、通常、ユーザが任意の所与の時点で見たいと希望するよりもずっと多くのデータを含んでいる。ユーザが、階層的なデータソースの閲覧を、そのデータ構造内部のノードを選択することによって行うとき、通常、提示アプリケーションは、選択したノードの下のサブツリーの中のデータ項目すべてを表示し、そのうちの一部は、しばしば、ユーザにとって興味のないものである可能性がある。その提示アプリケーションが、興味のないデータのふるい除けを、ユーザの何らかのそれまでに観察された閲覧パターンに基づいて行えるのであれば、非常に望ましいはずである。説明した方法１３０００および６０００は、この作業に非常に適している。Ｙｉ＝ユーザが閲覧のために選択したルート・ノードと設定することにより、その方法によって識別されたコンテキスト・ノードの組は、ユーザにとって興味があり、表示することが好ましいそうなノードを構成し、一方、コンテキスト・ノードとして識別されていない残りのノードは、好ましくはふるい除けられる。
【０１３７】
親ノードＰｊがルート・ノードＹｉからヒット・ノードＸへの有向パス上に存在する特殊な場合に関しては、コンテキスト・ノードとして含めるためのＹｉの子ノードＣｋの選択が、確率
【０１３８】
【数２６】
2007519086.tif 000028
【０１３９】
に基づくことを想起されたい。確率平均化によって、これらは、平均確率
【０１４０】
【数２７】
2007519086.tif 000029
【０１４１】
によって置き換えられるが、ここで、（Ｐｊｈ，Ｃｋｈ）は（Ｐｊ，Ｃｋ）に等しく、（Ｐｊｈ，Ｘｈ）は（Ｐｊ，Ｘ）に等しく、Ｐｊ０、Ｃｋ０、およびＸ０（すなわち、ｈ＝０）はそれぞれ、Ｐｊ、Ｃｋ、およびＸの別名とする。
【０１４２】
上の式が平均確率Ｐｒｍｅａｎ［Ｃｋ｜Ｘ∧Ｐｊ］の正確な近似であるためには、式３３の右辺の分母が十分に大きくなければならない（たとえば、＞ｆｍｉｎ）。そうでないときには、使用することのできる別の好ましい改善方法は、Ｐｒｍｅａｎ［Ｃｋ｜Ｘ∧Ｐｊ］の近似を、Ｐｒｍｅａｎ［Ｃｋ｜Ｘ’∧Ｐｊ］、すなわち、ＸではなくＸ’に対する条件付き確率で行うことであり、ここでＸ’はＹｉからＸへの有向パス上に存在するＸのすぐ上の親である。
【０１４３】
Ｐｒｍｅａｎ［Ｃｋ｜Ｘ∧Ｐｊ］に対する近似の決定に使用するノードＸ’を識別するための方法２２０００のフローチャートを、図２２に示している。方法２２０００は、ステップ２２００５で始まり、ここで、Ｘ’はまずＸに初期化される。次のステップ２２０１０で、総和
【０１４４】
【数２８】
2007519086.tif 000030
【０１４５】
が計算され、Ｄに割り当てられるが、ここでノード対（Ｐｊｈ，Ｘ’ｈ）は（Ｐｊ，Ｘ’）に等しい。次いで、判断ステップ２２０１５が続き、Ｄがある正の閾値定数ｆｍｉｎ以上であるかどうかの検査が行われる。そうである場合は、方法２２０００は、ステップ２２０２５で抜けて成功となる。判断ステップ２２０１５が失敗した場合は、実行は別の判断ステップ２２０３０へと進み、ここで検査が行われて、Ｘ’がＰｊのすぐ下の子であるかどうかが判定される。そうである場合は、この方法はステップ２２０３５で抜けて失敗となり、そうでない場合は、方法は継続して、ステップ２２０４０で、Ｘ’が、ＰｊからＸへの有向パスに沿って存在するその親で置き換えられる。次いで、方法２２０００は、ループしてステップ２２０１０へと戻る。
【０１４６】
方法２２０００が成功して、ノードＸ’および対応する値Ｄが得られた場合、Ｐｒｍｅａｎ［Ｃｋ｜Ｘ∧Ｐｊ］には、値
【０１４７】
【数２９】
2007519086.tif 000031
【０１４８】
が割り当てられる。
【０１４９】
方法２２０００を抜けて失敗になった場合には、Ｐｒｍｅａｎ［Ｃｋ｜Ｘ∧Ｐｊ］への値の割り当ては、ＣｋとＹｉの間の距離に基づいて
【０１５０】
【数３０】
2007519086.tif 000032
【０１５１】
または、Ｃｋとヒット・ノードＸの間の距離に基づいて
【０１５２】
【数３１】
2007519086.tif 000033
【０１５３】
行われる。
【０１５４】
Ｐｒｍｅａｎ［Ｃｋ｜Ｘ∧Ｐｊ］の近似が、最終的に式３４、式３５、または式３６で行われたのに応じて、親ノードＰｊに、コンテキストの子ノードが、ＰｊからＸへの有向パス上に存在する子ノードＣ１以外ないことの、Ｐｊおよびヒット・ノードＸのもとでの平均確率の計算は、それぞれ、式３７、式３８、または式３９を用いて行われる。すなわち
【０１５５】
【数３２】
2007519086.tif 000034
【０１５６】
【数３３】
2007519086.tif 000035
【０１５７】
【数３４】
2007519086.tif 000036
【０１５８】
ここで、（Ｐｊｈ，Ｘ’ｈ）は（Ｐｊ，Ｘ’）に等しく、Ｘ’およびＤは方法２２０００によって得られる。
【０１５９】
親ノードＰｊに対するコンテキストの子ノードの決定を、ＰｊがＹｉからヒット・ノードＸへの有向パスに沿って存在する特別な場合について、確率平均化によって行うための好ましい手続きは、図８に示すものに非常に類似しており、これを図１４に示している。
【０１６０】
図１４に示す方法１４０００は、ステップ１４００１で始まり、そこでは、概念上、架空の子ノードＣ０が作成され、実際の子ノードＣ１，．．．，Ｃｍからなるリストへと追加され、確率値Ｑ０＝Ｐｒｍｅａｎ［Ｃ１  ｎｏ  ｓｉｂｌｉｎｇ｜Ｐｊ∧Ｘ］が、式３７、式３８、または式３９を用いて計算されて割り当てられ、次のステップ１４００５で、Ｃ１を除く実際の子ノードＣｋには、それに対応して、確率値Ｑｋ＝Ｐｒｍｅａｎ［Ｃｋ｜Ｘ∧Ｐｊ］が、それぞれ、式３４、式３５、または式３６を用いて計算されて割り当てられる。どの場合でも、ステップ１４００６がステップ１４００５に続き、方法７０００をステップ７００５で呼び出して（ステップ７００１を飛ばして）、子ノードＣ０，．．．，Ｃｍのうちで１組のコンテキスト・ノードを選択する。方法７０００を抜けると、方法１４０００は再開され、判断ステップ１４０１０で検査が行われて、架空の子ノードＣ０がコンテキスト・ノードとして選択されたかどうかが判定される。そうである場合、実行は継続され、ステップ１４０２０で、Ｃ０がコンテキスト・ノードとして除外される。方法１４０００は、その後、ステップ１４０１５で終了する。検査が１４０１０で失敗した場合、この方法は、直接に終了ステップ１４０１５へと進む。
【０１６１】
前述の議論では、スキーマ・グラフ内に多くとも単一のヒット・ノードがある特別な場合においてコンテキスト・ノードを識別するための方法を説明している。これは、ユーザが単一の検索キーワードだけを入力するときの普通の想定状況である。そのキーワードがスキーマ・グラフ内の複数の場所に現れる場合には、これは１つより多くのヒットがあることを意味するが、ヒットそれぞれを別々に扱うことが好ましい。すなわち、説明した方法がスキーマ・グラフ内の第１のヒット・ノードに対して適用され、複数のコンテキストツリーがそのヒット・ノードに対して決定される。次いでその後で、同じ方法が残りのヒット・ノードのそれぞれに対して適用されて、新しい複数のコンテキストツリーが得られる、などである。ヒット・ノードすべてが処理されてしまうと、生成されたコンテキストツリーは、複数のヒット・ノードを包摂するとわかった場合には、スコアが付け直され、さらに重複しているコンテキストツリーは取り除かれる。次いで、残りのコンテキストツリーのリストは、（もしあれば）その新しいスコアに従って整列し直され、キーワード検索操作の結果としてユーザへと返される。
【０１６２】
しかし、ユーザが、ブール値のＡＮＤ操作で結合された複数の検索キーワードを含む「すべて見つける」（ｆｉｎｄ  ａｌｌ）キーワード検索操作を開始した場合は、キーワード・ヒットは、潜在的に、スキーマ・グラフ内の２つ以上のヒット・ノードに現れる可能性がある。コンテキストツリーを決定するためのより一般的な方法の説明を、ここで、そのような想定状況を扱うために行う。
【０１６３】
図１１に、内部に複数のヒット・ノード１１０１０、１１０２０、および１１０２５のある、スキーマ・グラフの例１１０００を示している。これらのヒット・ノードをＸ１，．．．，Ｘｎで表すことにする。当然、コンテキストツリーがヒット・ノードすべてを含むためには、Ａで表している（ノード１１００５）、ヒット・ノードすべてを含む最も小さいサブツリーのルート・ノードが、コンテキスト・ノードとして、Ａからヒット・ノードそれぞれへの有向パスに沿って存在するノードすべてとともに返されなければならない。したがって、ノード１１０１５は、ＡからＸ２へ（またＡからＸ３へ）の有向パスに沿って存在するため、コンテキスト・ノードでなければならない。
【０１６４】
コンテキストツリー決定の方法の第１の、ボトム・アップのフェーズは、ノードＡで始まり、走査は上向きに行われる。ＹｉをＡまたはＡの祖先とするが、ヒット・ノードのもとでのそれの確率、すなわちＰｒ［Ｙｉ｜Ｘ１∧．．．∧Ｘｎ］を評価することが、コンテキストツリーの可能なルート・ノードを決定するためには必要である。これを数学的に表現すると
【０１６５】
【数３５】
2007519086.tif 000037
【０１６６】
となる。
【０１６７】
この時点で、何らかの確率の独立性の仮定が必要であるが、理由は、式４０の右辺の分子と分母はどちらも、ｎの一般の値について既存の頻度テーブルから直接に求めまたは推定することが（ｎ≦２のときの分母を除いて）できないためである。妥当な１つの仮定は、Ｘｌの組が、共通の祖先Ｙｉのもとで、互いに独立というものである。言い換えれば、
Ｐｒ［Ｘ１∧．．．∧Ｘｎ｜Ｙｉ］＝Ｐｒ［Ｘ１｜Ｙｉ］．．．Ｐｒ［Ｘｎ｜Ｙｉ］                                                                              式４１
したがって、
【０１６８】
【数３６】
2007519086.tif 000038
【０１６９】
Ｐｒ［Ｙｉ］＝０のときの特異性を取り除くために、Ｐｒ［Ｙｉ∧Ｘ１∧．．．∧Ｘｎ］は
【０１７０】
【数３７】
2007519086.tif 000039
【０１７１】
同様に
【０１７２】
【数３８】
2007519086.tif 000040
【０１７３】
単一のヒット・ノードしかない場合のように、ヒット・ノードすべてのもとでのＹｉの生起確率の表現は、好ましくは、そのすぐ下の子ノードの確率によって漸進的に、確率平均化が容易になるように、次のように行われる。すなわち、Ｗが、ＹｉからＡへの有向パスに沿うＹｉのすぐ下の子ノードを表すとすると、
【０１７４】
【数３９】
2007519086.tif 000041
【０１７５】
ここで
【０１７６】
【数４０】
2007519086.tif 000042
【０１７７】
ここで、対（Ｙｉｈ，Ｗｈ）は（Ｙｉ，Ｗ）に等しく、ｌ＝１，．．．，ｎに対して（Ｗｈ，Ｘｌｈ）は（Ｗ，Ｘｌ）に等しく、Ｙｉ０、Ｗ０、およびＸｌ０（ｈ＝０）はそれぞれ、Ｙｉ、Ｗ、およびＸｌの別名とする。分子の総和の内側の項は、式４３で置き換えることができる。分母の総和の内側の項も、ＷにＹｉの役割をさせることにより、式４３で置き換えることができ、こうして
【０１７８】
【数４１】
2007519086.tif 000043
【０１７９】
が得られ、ここで
【０１８０】
【数４２】
2007519086.tif 000044
【０１８１】
【数４３】
2007519086.tif 000045
【０１８２】
Ｐｒｍｅａｎ［Ｙｉ｜Ｗ∧Ｘｌ∧．．．∧Ｘｎ］は、
【０１８３】
【数４４】
2007519086.tif 000046
【０１８４】
の場合には不定である。これが起きるとき、Ｐｒｍｅａｎ［Ｙｉ｜Ｗ∧Ｘｌ∧．．．∧Ｘｎ］への値の割り当ては、好ましくは、Ｙｉからヒット・ノードＸ１，．．．，Ｘｎへの距離に基づいて次のように行われる。すなわち
【０１８５】
【数４５】
2007519086.tif 000047
【０１８６】
ノードＹｉが、ヒット・ノードすべてを含むコンテキストツリーのルート・ノードである確率の計算を、Ｙｉとして選んだものすべてについて行うための方法１２０００のフローチャートを、図１２に示している。方法１２０００は、ステップ１２００１で始まり、ここでは、ヒット・ノードすべてを含む、スキーマ・グラフ内の最小のサブツリーのルート・ノードが識別され、Ａで表される。次いで、実行は継続して、ステップ１２００２で、ＹｉがＡに初期化され、したがってＰｒ’［Ｙｉ｜Ｘ１∧．．．∧Ｘｎ］＝１となる。次のステップ１２００５で、式４５、式４７を、式４８および式４９、またはその代わりに式５０とともに使用して、Ｐｒ’［Ｚｊ｜Ｘ１∧．．．∧Ｘｎ］の計算が、Ｙｉの親ノードＺｊそれぞれに対して行われる。ステップ１２００５の後、ステップ１２０１０では、Ｐｒ’［Ｙｉ  ｒｏｏｔ｜Ｘ１∧．．．∧Ｘｎ］の計算が、式
【０１８７】
【数４６】
2007519086.tif 000048
【０１８８】
に従って行われる。
【０１８９】
次いで、方法１２０００はステップ１２０１５へと進み、ここで、Ｙｉの親ノードＺｊが選択される。ステップ１２０２０に到達すると、方法１２０００は、ステップ１２００５で（ステップ１２００１および１２００２を飛ばして）再帰的に、ただし選択した親ノードＺｊがＹｉの役割を果たす状態で呼び出される。この再帰呼び出しが戻ると、実行が判断ステップ１２０２５で再開され、ここで検査が行われて、Ｙｉの親ノードすべてが処理されているかどうかの判定が行われる。そうである場合は、方法はステップ１２０３０で終わり、そうでない場合は、方法は継続して、ステップ１２０１５でＹｉの別の親ノードＺｊが、処理のために選択される。
【０１９０】
第２のトップ・ダウン走査のフェーズで、親ノードＰｊがルート・ノードＹｉからどのヒット・ノードへの有向パスに沿っても存在しない一般の場合には、Ｐｊの子ノードがコンテキスト・ノードであるかどうかを判定するための方法は、これまでに単一のヒット・ノードしかない場合のために使用した方法１３０００とそのまま変わらない。
【０１９１】
親ノードＰｊがＹｉから１つまたは複数のヒット・ノードへの有向パスに沿って存在する特別な場合には、単一のヒット・ノードの場合のために使用した方法を変更して、１つより多くのＰｊの子ノードをコンテキスト・ノードとして含めなければならない可能性を見越しておく必要がある。１つのヒット・ノードＸだけしか含まない場合には、子ノードＣｋがコンテキスト・ノードであるかどうかの判定は、確率の値
Ｐｒ［Ｃｋ｜Ｘ∧Ｐｊ］
に基づいて行われることを想起されたい。ここで、ＸはＰｊの子孫であるが、ＣｋまたはＣｋの子孫ではない。１つより多くのヒット・ノードがあるときの拡張は、子ノードＣｋ、ｋ＝１，．．．，ｍの選択プロセスを、親ノードＰｊおよびＰｊの子孫のであるヒット・ノードＸｌすべてのもとでのＣｋの確率に基づくようにし、一方でＰｊの子孫ではないヒット・ノードの影響を無視することである。当然、それ自身がヒット・ノードであり、または１つまたは複数のヒット・ノードの祖先である子ノードＣｋすべては、コンテキスト・ノードでなければならない。一般性を失うことなく、これらの子ノードを、Ｃ１，．．．，Ｃｒとし、ここで１≦ｒ≦ｍとする。同様に、Ｃ１，．．．，Ｃｒの子孫であるヒット・ノードの組をＸ１，．．．，Ｘｓとし、ここでｒ≦ｓ≦ｎとする。ｓ＝１（したがってｒ＝１）の場合、この想定状況は、単一のヒット・ノードしかない場合に等しく、したがって、この場合に関して説明した方法１４０００を使用することができる。ｓ＞１の場合に関して一般化するための好ましい実装形態で採用する方法は、項Ｐｒ［Ｃｋ｜Ｘ∧Ｐｊ］を、式
【０１９２】
【数４７】
2007519086.tif 000049
【０１９３】
で置き換えることであり、これは、確率平均化の後、
【０１９４】
【数４８】
2007519086.tif 000050
【０１９５】
となり、ここでＰｒｍｅａｎ［Ｃｋ｜Ｘ∧Ｐｊ］は、式３３で定義した通りである。Ｑｋは、任意のＸｌ、ｌ＝１，．．．，ｓに対してｆｒｅｑｍｅａｎ（Ｐｊ，Ｘｌ）＝０の場合には、不定となり、ここで
【０１９６】
【数４９】
2007519086.tif 000051
【０１９７】
であり、（Ｐｊｈ，Ｘｌｈ）は（Ｐｊ，Ｘｌ）に等しい。ｆｒｅｑｍｅａｎ（Ｐｊ，Ｘｌ）が非零ではあるが小さな数である（たとえば、＜ｆｍｉｎ）のときでも、Ｑｋの推定は、頻度テーブルからは十分な精度で行うことができない。単一のヒット・ノードを含む場合のように、この問題の克服は、ヒット・ノードＸ１，．．．，Ｘｓを、そのヒット・ノードの一部またはすべてをその祖先で置き換えた新しいノードの組Ｓで置き換え、その後でＱｋをＳの要素によって定義し直すことによって行うことができる。
【０１９８】
図２１のフローチャートで示している方法２１０００が、好ましくは、ヒット・ノードＸ１，．．．，Ｘｓを置き換えるこのノードの新しい組Ｓを決定するのに使用される。方法２１０００は、ステップ２１００５で始まり、ここで、ヒット・ノードの初期の組Ｘ１，．．．，ＸｓはＳで表される。次のステップ２１０１０で、Ｓのうちの処理済みでない要素Ｘｐが選択される。次いで、判断ステップ２１０１５が続き、ここでは検査が行われて、ｆｒｅｑｍｅａｎ（Ｐｊ，Ｘｐ）が、ある閾値定数ｆｍｉｎ以上であるかが判定される。そうである場合、Ｘｐは組Ｓの中に保持され、方法２１０００は判断ステップ２１０２０へと続き、ここで検査が行われてＳの中の要素すべてが処理されているかが判定される。１つまたは複数の処理済みでない要素が残っている場合は、実行はステップ２１０１０へと戻って、Ｓの別の要素が処理のために選択される。他方、要素すべてが処理されている場合は、方法はステップ２１０２５で終わって成功になる。
【０１９９】
ここで判断ステップ２１０１５へと戻る。検査の条件が失敗した場合、別の判断ステップ２１０３０が続き、これにより、選択したノードＸｐがＰｊの子ノードであるかが検査される。そうである場合は、方法２１０００はステップ２１０４０で終わって失敗となり、そうでない場合は、ステップ２１０３５が続く。ステップ２１０３５で、Ｓの中の要素Ｘｐは、ＰｊからＸｐへの有向パスに沿って存在するその親Ｘ’ｐで置き換えられ、Ｘ’ｐの子孫すべてがＳから取り除かれる。次いで、実行はステップ２１０２０へと進む。
【０２００】
上で説明した方法２１０００が成功で戻った場合は、結果となる組Ｓの中の要素を使用して、値Ｑｋの計算が子ノードＣ１，．．．，Ｃｒそれぞれに対して行われる。すなわち
【０２０１】
【数５０】
2007519086.tif 000052
【０２０２】
しかし、方法２１０００が失敗で戻った場合は、値Ｑｋの決定は、好ましくは、Ｃｋとルート・ノードＹｉの間の距離から、すなわち
【０２０３】
【数５１】
2007519086.tif 000053
【０２０４】
またはこの代わりに、Ｃｋとヒット・ノードＸ１，．．．，Ｘｎの間の距離から、すなわち
【０２０５】
【数５２】
2007519086.tif 000054
【０２０６】
のように行われる。
【０２０７】
また、単一のヒット・ノードＸがある場合、親ノードＰｊおよびヒット・ノードＸのもとで、Ｐｊの１つの子ノードＣ１だけが生起する確率
Ｐｒ［Ｃ１  ｎｏ  ｓｉｂｌｉｎｇ｜Ｘ∧Ｐｊ］
の評価が必要であることを想起されたい。ここで、Ｃ１はＸであり、またはＸの祖先である。
【０２０８】
この量を現在の想定状況へと一般化する際、２つの可能性、すなわち、ｒ＝１である特別な場合、およびｒ＞１であるより一般的な場合が生じる可能性がある。前者の例を図１５に示しているが、そこには、ノード１５００５をルートとするサブツリーの内部にある３つのヒット・ノード１５０３０、１５０３５、および１５０４０がある。しかし、３つのヒット・ノードはすべて、ノード１５００５の単一の子ノード１５０１０の下にある。
【０２０９】
この特別な場合を扱うための１つのアプローチは、項Ｐｒ［Ｃｌ  ｎｏ  ｓｉｂｌｉｎｇ｜Ｘ∧Ｐｊ］の式
【０２１０】
【数５３】
2007519086.tif 000055
【０２１１】
による置き換えを、量Ｑｋを式５２で使用したのと類似のしかたで行うことである。上のＱｋの場合でと同様に、式５６は、任意のＸｌ、ｌ＝１，．．．，ｓに対してｆｒｅｑｍｅａｎ（Ｐｊ，Ｘｌ）＝０の場合には、不定となる可能性がある。したがって、Ｑ０に割り当てられる実際の値は、方法２１０００が成功で戻った場合は、方法２１０００から得られた組Ｓに基づく。すなわち
【０２１２】
【数５４】
2007519086.tif 000056
【０２１３】
そうでなく方法２１０００が失敗であった場合は、Ｑ０への値の割り当ては、Ｐｊのルート・ノードＹｉからの距離に基づいて
【０２１４】
【数５５】
2007519086.tif 000057
【０２１５】
またはこの代わりに、Ｐｊとヒット・ノードＸ１，．．．，Ｘｎの間の距離に基づいて
【０２１６】
【数５６】
2007519086.tif 000058
【０２１７】
行われる。
【０２１８】
親ノードＰｊの子ノードＣｋの組のうちでコンテキスト・ノードの識別をｒ＝１、ｓ＞１の場合に関して行うための、図１６のフローチャートに示す方法１６０００は、単一のヒット・ノードの場合のための方法１４０００に非常に似ている。方法１６０００は、ステップ１６００１で始まり、そこでは、概念上、架空の子ノードＣ０が作成され、実際の子ノードＣ１，．．．，Ｃｍからなるリストへと追加され、式５７、式５８、または式５９の中で定義された値Ｑ０が割り当てられ、次のステップ１６００５で、Ｃ１を除く実際の子ノードＣｋには、それに対応して、それぞれ、式５３、式５４、または式５５の中で定義された値Ｑｋが割り当てられる。ステップ１６００６はステップ１６００５に続き、方法７０００をステップ７００５で呼び出して（ステップ７００１を飛ばして）、子ノードＣ０，．．．，Ｃｍのうちで１組のコンテキスト・ノードを選択する。方法７０００を抜けると、方法１６０００は再開され、判断ステップ１６０１０で検査が行われて、架空の子ノードＣ０がコンテキスト・ノードとして選択されたかどうかが判定される。そうである場合、実行は継続され、ステップ１６０２０で、Ｃ０がコンテキスト・ノードとして除外される。方法１６０００は、その後、ステップ１６０１５で終了する。検査が１６０１０で失敗した場合、方法１６０００は、直接に終了ステップ１６０１５へと進む。
【０２１９】
ｒ＞１（したがってｓ＞１）である一般の場合では、ｒ＝１の場合に使用したＰｒ［Ｃ１  ｎｏ  ｓｉｂｌｉｎｇ｜Ｘ１∧．．．∧Ｘｓ∧Ｐｊ］に類似した量は
【０２２０】
【数５７】
2007519086.tif 000059
【０２２１】
であり、ここで、Ｓは、方法２１０００が成功で抜けた場合に、これによって返される組である。残念ながら、総和の中にある確率の推定は、既存の頻度テーブルからは容易に行うことができない。したがって、わずかに異なる式がその代わりに使用される。子ノードＣｋ、１≦ｋ≦ｒそれぞれにルートがあるサブツリーの中にない組Ｓの要素を１≦ｌ≦ｓｋに対するＨｋｌで表すとし、ここでｓｋ≦｜Ｓ｜である。子ノードＣｋ、１≦ｋ≦ｒそれぞれに対し、次のものが計算される。すなわち
【０２２２】
【数５８】
2007519086.tif 000060
【０２２３】
上の式の量の背後にある理論的根拠は、Ｃｋ、１≦ｋ≦ｒすべてにわたって足し合わせると、子ノードＣ１，．．．，Ｃｒがともに生起する確率を近似する量が得られるというものである（が、＞１である値をとることがあるため、真の確率ではない）。ｒ＝１の場合でのように、方法２１０００が失敗で戻った場合、Ｑｋは、Ｐｊのルート・ノードＹｉからの距離から、１≦ｋ≦ｒに対して
【０２２４】
【数５９】
2007519086.tif 000061
【０２２５】
またはこの代わりに、Ｐｊとヒット・ノードＸ１，．．．，Ｘｎの間の距離から
【０２２６】
【数６０】
2007519086.tif 000062
【０２２７】
のように得られる。
【０２２８】
子ノードの組Ｃ１，．．．，Ｃｍのうちでコンテキスト・ノードを選択するための方法１７０００を、ここで、ｒ＞１、ｓ＞１の一般の場合に関して、図１７のフローチャートを参照して説明する。方法１７０００は、ステップ１７００１で始まり、ここで、子ノードＣｋ、１≦ｋ≦ｒそれぞれには、式６０、式６１、または式６２を用いて計算された値Ｑｋが割り当てられる。ステップ１７００５がこれに続き、ここでは、残りの子ノードには、それに対応して、式５３、式５４、または式５５を用いて計算された値Ｑｋが、それぞれ、割り当てられる。次のステップ１７０１０で、値Ｑｋが、子ノードすべてにわたって総計され、Ｔと表される。方法１７０００は継続して、ステップ１７０１５で、そのサブツリーにヒット・ノードを含む子ノードすべて、すなわち、Ｃｋ、１≦ｋ≦ｒがコンテキスト・ノードとして選択される。次のステップ１７０２０で、割り当てられた値が残りの子ノードのうちで最高のノードＣｋもコンテキスト・ノードとして選択される。値が最大で同じ子ノードが１つより多く存在する場合は、そのようなノードはすべて、コンテキスト・ノードとして選択される。次いで、それまでにコンテキスト・ノードとして選択された子ノードすべての割り当てられた値の総和が、ステップ１７０２５で計算され、Ｓと表される。次いで、実行は判断ステップ１７０３０へと進み、このポイントで、子ノードＣｋすべてがコンテキスト・ノードとして選択されている場合、方法１７０００は、ステップ１７０４０で終了する。しかし、コンテキスト・ノードとしてまだ選択されていない１つまたは複数の子ノードＣｋがある場合は、方法１７０００は、別の判断ステップ１７０３５へと続く。ステップ１７０３５で、検査が行われて、Ｓ≧Ｔ／２であるかどうかが確かめられ、そうである場合、方法１７０００はここでもステップ１７０４０で終了する。Ｓ＜Ｔ／２である場合は、実行はステップ１７０２０へと戻り、ここでノードのコンテキスト・ノードとしての選択がさらに行われる。
【０２２９】
以上の説明では、階層的なデータ構造内のキーワード検索を行うときに出遭う異なる段階および動作の想定状況を扱うための様々な方法を提示している。こうした方法は、単一の全体的な手続き１８０００へと組み込まれるが、これは、図２のステップ２０１０を詳細にしたものであり、図１９および図２０にそれぞれ示す下位の手続き１９０００および２００００を含む図１８のフローチャートで示している。方法１８０００は、判断ステップ１８００５で始まり、ここで、検査が行われて、スキーマ・グラフ内に複数のヒット・ノードがあるかどうかの判定が行われる。そうである場合、実行はステップ１８０１５へと進み、ここで方法２００００が呼び出され、そうでない場合は、実行はステップ１８０１０へと進み、ここで方法１９０００が呼び出される。どちらの場合でも、方法２００００または１９０００は、コンテキストツリーからなるリストとともに戻り、それぞれには、スコアが関連づけられている。以下は、方法１９０００の詳細な説明であり、これに方法２００００のそれが続く。
【０２３０】
方法１９０００は、ステップ１９００１で始まり、ここで、方法１００００が呼び出されて、ヒット・ノードＸの祖先ノードである可能なルート・ノードＹｉからなるリストが決定される。Ｙｉそれぞれは、可能なコンテキストツリーのルート・ノードである。また、方法１００００では、値Ｓｉ＝Ｐｒ’［Ｙｉ｜Ｘ］の計算がノードＹｉそれぞれに対して行われる。次いで、方法１９０００は継続して、ステップ１９００５で、その前のステップで決定されたノードＹｉが処理のために選択される。次のステップ１９０１０で、方法１９０００内部にある下位プロセスである方法３８０００が呼び出されて、ノードＹｉをルートとするサブツリーの中にあるコンテキスト・ノードが識別される。次いで、方法１９０００は継続して、ステップ１９０３０で、識別されたコンテキスト・ノードすべてを含み、Ｙｉをルート・ノードとするコンテキストツリーが構築される。このツリーには、ステップ１９００１で計算されたＳｉのスコアが割り当てられる。次いで、方法１９０００は、判断ステップ１９０３５へと進む。ステップ１９００１で得られたノードＹｉすべてが処理されている場合は、この方法はステップ１９０４０で終わり、そうでない場合は、この方法はステップ１９００５へと戻って、別のノードＹｉの処理が行われる。
【０２３１】
方法１９０００の内部で呼び出される方法３８０００は、ステップ３８０１０で始まり、ここで、ノードＹｉが、まずＰｊに割り当てられる。実行は、判断ステップ３８０１５へ、次いで、ＰｊがＹｉからヒット・ノードＸへの有向パス上に存在しない場合は、３８０２０へと進む。ステップ３８０２０で、方法１３０００が呼び出されて、Ｐｊの子ノードのうちで１組のコンテキスト・ノードが選択される。続くステップ３８０２５では、方法３８０００の再帰的な呼び出しが、ステップ３８０２０で（ステップ３８０１０および３８０１５を飛ばして）、コンテキスト・ノードとして選択された葉でない子ノードＣｋそれぞれに対して行われ、ＣｋにＰｊの役割をさせることによって、さらに別のコンテキスト・ノードがその子孫のうちで識別される。そのような子ノードすべてに対する呼び出しが戻ると、方法３８０００は、ステップ３８０４０で終了する。また、方法３８０００は、Ｐｊに子ノードがない場合、またはその葉でない子ノードのうちのどれもが、ステップ３８０２０でコンテキスト・ノードとして選択されていない場合には、直接に終了ステップ３８０４０へと進む。
【０２３２】
判断ステップ３８０１５は、ＰｊがＹｉからＸへの有向パス上に存在する場合に成功し、その場合、実行はステップ３８０４５へと進む。ここで、方法１４０００が呼び出されて、Ｐｊの子ノードのうちで１組のコンテキスト・ノードが選択されるが、Ｃ１は、ＰｊからＸへの有向パス上に存在する子ノードを表す。続くステップ３８０５０で、方法３８０００の再帰的な呼び出しが、ステップ３８０１５で（ステップ３８０１０を飛ばして）、コンテキスト・ノードとして選択された葉でない子ノードＣｋそれぞれに対して行われ、ＣｋにＰｊの役割をさせることによって、さらに別のコンテキスト・ノードがその子孫のうちで識別される。そのような子ノードすべてに対する呼び出しが戻ると、方法３８０００は、ステップ３８０４０で終了する。
【０２３３】
方法２００００は、ステップ２０００１で始まり、ここで、方法１２０００が呼び出されて、ヒット・ノードＸ１，．．．，Ｘｎの祖先ノードである可能なルート・ノードＹｉからなるリストが決定される。Ｙｉそれぞれは、可能なコンテキストツリーのルート・ノードである。また、方法１２０００では、値Ｓｉ＝Ｐｒ’［Ｙｉ｜Ｘ１∧．．．∧Ｘｎ］の計算がノードＹｉそれぞれに対して行われる。次いで、方法２００００は継続して、ステップ２０００５で、その前のステップで決定されたノードＹｉが処理のために選択される。次のステップ２００１０で、方法２００００内部にある下位プロセスである方法３９０００が呼び出されて、ノードＹｉをルートとするサブツリーの中にあるコンテキスト・ノードが識別される。次いで、方法２００００は継続して、ステップ２００６０で、識別されたコンテキスト・ノードすべてを含み、Ｙｉをルート・ノードとするコンテキストツリーが構築される。このツリーには、ステップ２０００１で計算されたＳｉのスコアが割り当てられる。次いで、方法２００００は、判断ステップ２００６５へと進む。ステップ２０００１で得られたノードＹｉすべてが処理されている場合は、この方法はステップ２００７０で終わり、そうでない場合は、この方法はステップ２０００５へと戻って、別のノードＹｉの処理が行われる。
【０２３４】
方法１９０００の内部で呼び出される方法３９０００は、ステップ３９０１０で始まり、ここで、ノードＹｉが、まずＰｊに割り当てられる。実行は、判断ステップ３９０１５へ、次いで、Ｐｊのところのサブツリーのルートにおいてヒット・ノードがない場合は、ステップ３９０２０へと進む。ステップ３９０２０で、方法１３０００が呼び出されて、Ｐｊの子ノードのうちで１組のコンテキスト・ノードが選択される。続くステップ３９０２５では、方法３９０００の再帰的な呼び出しが、ステップ３９０２０で（ステップ３９０１０および３９０１５を飛ばして）、コンテキスト・ノードとして選択された葉でない子ノードＣｋそれぞれに対して行われ、ＣｋにＰｊの役割をさせることによって、さらに別のコンテキスト・ノードがその子孫のうちで識別される。そのような子ノードすべてに対する呼び出しが戻ると、方法３９０００は、ステップ３９０６０で終了する。また、方法３９０００は、Ｐｊに子ノードがない場合、またはその葉でない子ノードのうちのどれもが、ステップ３９０２０でコンテキスト・ノードとして選択されていない場合には、直接に終了ステップ３９０６０へと進む。
【０２３５】
判断ステップ３９０１５は、Ｐｊをルートとするサブツリーの内部に１つまたは複数のヒット・ノードがある場合に成功し、その場合、実行は別のステップ３９０３０へと進む。Ｐｊの下のサブツリーの中に単一のヒット・ノードしかない場合は、この判断ステップは失敗し、実行はステップ３９０３５へと進み、そうでない場合は、実行はまた別の判断ステップ３９０４０へと進む。判断ステップ３９０４０で、検査が行われて、Ｐｊの下のヒット・ノードすべてが、その子ノードのうちの１つの下にしかないかどうかが判定される。そうである場合は、実行はステップ３９０４５へと進み、そうでない場合は、実行はステップ３９０５０へと進む。ステップ３９０５０では、Ｃ１，．．．，Ｃｒで１つまたは複数のヒット・ノードが下にあるＰｊの子ノードを表すとして、方法１７０００が呼び出されて、Ｐｊの子ノードのうちで１組のコンテキスト・ノードが選択される。しかし、判断ステップ３９０４０からステップ３９０４５へと導かれた場合は、方法１６０００が呼び出されて、Ｐｊの子ノードのうちで１組のコンテキスト・ノードを選択することが、Ｃ１をそのサブツリーの中にヒット・ノードを含む、Ｐｊの唯一の子ノードとして行われる。
【０２３６】
ここで３９０３５へと戻り、Ｐｊからその唯一の子孫のヒット・ノードへのパスが、その子ノードＣ１を通過するとする。方法１４０００が呼び出されて、Ｐｊの子ノードのうちで１組のコンテキスト・ノードが選択される。
【０２３７】
ステップ３９０３５、３９０４５、および３９０５０のそれぞれが完了すると、方法３９０００のそれ自体の再帰的な呼び出しが、ステップ３９０１５で（ステップ３９０１０を飛ばして）、コンテキスト・ノードとして選択された葉でない子ノードＣｋそれぞれに対して行われ、ＣｋにＰｊの役割をさせることによって、さらに別のコンテキスト・ノードがその子孫のうちで識別される。そのような子ノードすべてに対する呼び出しが戻ると、方法３９０００は、ステップ３９０６０で終了する。
【０２３８】
説明のための例
ここで、好ましい実装形態の動作の説明を、下の階層的なＸＭＬデータソースの例によって行う。このＸＭＬソースは、「ＸＹＺ」という名称の企業に関する、Ｗｅｂアドレス、支社の名称および場所、各支社での販売製品の範囲などのデータを含んでいる。このＸＭＬデータのスキーマ・グラフ表現を、図２３に示している。
【０２３９】
ＸＭＬソース
＜ｃｏｍｐａｎｙ＞  ＜！−−企業−−＞
＜ｎａｍｅ＞ＸＹＺ＜／ｎａｍｅ＞  ＜！−−名称−−＞
＜ｗｅｂ＞ｈｔｔｐ：／／ｗｗｗ．ｘｙｚ．ｃｏｍ＜／ｗｅｂ＞  ＜！−−  Ｗｅｂアドレス−−＞
＜ｄｅｓｃｒｉｐｔｉｏｎ＞  ＜！−−説明−−＞
Ｃｏｍｐａｎｙ  ｆｏｕｎｄｅｄ  ｉｎ  １９９９  ｓｐｅｃｉａｌｉｓｉｎｇ  ｉｎ  ｈｉ−ｔｅｃｈ  ｃｏｎｓｕｍｅｒｓ  ｅｌｅｃｔｒｏｎｉｃｓ  ＜！−−１９９９年設立のハイテク家電製品に特化した企業−−＞
＜／ｄｅｓｃｒｉｐｔｉｏｎ＞
＜ｂｒａｎｃｈ＞  ＜！−−支社−−＞
＜ｎａｍｅ＞Ｎｏｒｔｈ  Ｒｙｄｅ＜／ｎａｍｅ＞  ＜！−−名称−−＞
＜ｐｈｏｎｅ＞０２９１２３００００＜／ｐｈｏｎｅ＞  ＜！−−電話番号−−＞
＜ａｄｄｒｅｓｓ＞  ＜！−−住所−−＞
＜ｎｕｍｂｅｒ＞１＜／ｎｕｍｂｅｒ＞  ＜！−−番地−−＞
＜ｓｔｒｅｅｔ＞Ｌａｎｅ  Ｃｏｖｅ＜／ｓｔｒｅｅｔ＞  ＜！−−街区  Ｃｏｖｅ通り−−＞
＜ｃｉｔｙ＞Ｓｙｄｎｅｙ＜／ｃｉｔｙ＞  ＜！−−都市  シドニー−−＞
＜ｃｏｕｎｔｒｙ＞Ａｕｓｔｒａｌｉａ＜／ｃｏｕｎｔｒｙ＞  ＜！−−国  オーストラリア−−＞
＜／ａｄｄｒｅｓｓ＞
＜ｍａｎａｇｅｒ＞  ＜！−−支社長−−＞
＜ｆｉｒｓｔＮａｍｅ＞Ｊｉｍ＜／ｆｉｒｓｔＮａｍｅ＞  ＜！−−名−−＞
＜ｌａｓｔＮａｍｅ＞Ｓｍｉｔｈ＜／ｌａｓｔＮａｍｅ＞  ＜！−−姓−−＞
＜ｅｍａｉｌ＞ｊｓｍｉｔｈ＠ｘｙｚ．ｃｏｍ＜／ｅｍａｉｌ＞  ＜！＠電子メール−−＞
＜／ｍａｎａｇｅｒ＞
＜ｐｒｏｄｕｃｔ＞  ＜！−−製品−−＞
＜ｉｄ＞１＜／ｉｄ＞  ＜！−−ＩＤ−−＞
＜ｎａｍｅ＞Ｐｌａｓｍａ  ＴＶ＜／ｎａｍｅ＞  ＜！−−名称プラズマＴＶ  −−＞
＜ｐｒｉｃｅ＞＄１００００＜／ｐｒｉｃｅ＞  ＜！−−価格−−＞
＜ｓｕｐｐｌｉｅｒ＞ＪＥＣ＜／ｓｕｐｐｌｉｅｒ＞  ＜！−−メーカー−−＞
＜ｓｔｏｃｋ＞１０＜／ｓｔｏｃｋ＞  ＜！−−在庫数−−＞
＜／ｐｒｏｄｕｃｔ＞
＜ｐｒｏｄｕｃｔ＞  ＜！−−製品−−＞
＜ｉｄ＞２＜／ｉｄ＞  ＜！−−ＩＤ−−＞
＜ｎａｍｅ＞Ｍｐ３  ｐｌａｙｅｒ＜／ｎａｍｅ＞  ＜！−−名称  ＭＰ３プレイヤー−−＞
＜ｐｒｉｃｅ＞＄５００  ＜／ｐｒｉｃｅ＞  ＜！−−価格−−＞
＜ｓｕｐｐｌｉｅｒ＞ＨＧ＜／ｓｕｐｐｌｉｅｒ＞  ＜！−−メーカー−−＞
＜ｓｔｏｃｋ＞２０＜／ｓｔｏｃｋ＞  ＜！−−在庫数−−＞
＜／ｐｒｏｄｕｃｔ＞
＜／ｂｒａｎｃｈ＞
＜ｂｒａｎｃｈ＞  ＜！−−支社−−＞
＜ｎａｍｅ＞Ｍｏｒｌｅｙ＜／ｎａｍｅ＞  ＜！−−名称−−＞
＜ｐｈｏｎｅ＞０８９１２３００００＜／ｐｈｏｎｅ＞  ＜！−−電話番号−−＞
＜ａｄｄｒｅｓｓ＞  ＜！−−住所−−＞
＜ｎｕｍｂｅｒ＞１＜／ｎｕｍｂｅｒ＞  ＜！−−番地−−＞
＜ｓｔｒｅｅｔ＞Ｒｕｓｓｅｌ＜／ｓｔｒｅｅｔ＞  ＜！−−街区  Ｒｕｓｓｅｌ−−＞
＜ｃｉｔｙ＞Ｐｅｒｔｈ＜／ｃｉｔｙ＞  ＜！−−都市  パース−−＞
＜ｃｏｕｎｔｒｙ＞Ａｕｓｔｒａｌｉａ＜／ｃｏｕｎｔｒｙ＞  ＜！−−国  オーストラリア−−＞
＜／ａｄｄｒｅｓｓ＞
＜ｍａｎａｇｅｒ＞  ＜！−−支社長−−＞
＜ｆｉｒｓｔＮａｍｅ＞Ｔｅｄ＜／ｆｉｒｓｔＮａｍｅ＞  ＜！−−名−−＞
＜ｌａｓｔＮａｍｅ＞Ｗｈｉｔｅ＜／ｌａｓｔＮａｍｅ＞  ＜！−−姓−−＞
＜ｅｍａｉｌ＞ｔｗｈｉｔｅ＠ｘｙｚ．ｃｏｍ＜／ｅｍａｉｌ＞  ＜！＠電子メール−−＞
＜／ｍａｎａｇｅｒ＞
＜ｐｒｏｄｕｃｔ＞  ＜！−−製品−−＞
＜ｉｄ＞３＜／ｉｄ＞  ＜！−−ＩＤ−−＞
＜ｎａｍｅ＞Ｖｉｄｅｏ  ｐｈｏｎｅ＜／ｎａｍｅ＞  ＜！−−名称  ビデオ電話−−＞
＜ｐｒｉｃｅ＞＄２０００＜／ｐｒｉｃｅ＞  ＜！−−価格−−＞
＜ｓｕｐｐｌｉｅｒ＞ＮＶＣ＜ｓｕｐｐｌｉｅｒ＞  ＜！−−メーカー−−＞
＜ｓｔｏｃｋ＞１５＜／ｓｔｏｃｋ＞  ＜！−−在庫数−−＞
＜／ｐｒｏｄｕｃｔ＞
＜ｐｒｏｄｕｃｔ＞  ＜！−−製品−−＞
＜ｉｄ＞４＜／ｉｄ＞  ＜！−−ＩＤ−−＞
＜ｎａｍｅ＞ＰＤＡ＜／ｎａｍｅ＞  ＜！−−名称  ＰＤＡ−−＞
＜ｐｒｉｃｅ＞＄１０００＜／ｐｒｉｃｅ＞  ＜！−−価格−−＞
＜ｓｕｐｐｌｉｅｒ＞ＬＰ＜／ｓｕｐｐｌｉｅｒ＞  ＜！−−メーカー−−＞
＜ｓｔｏｃｋ＞５０＜／ｓｔｏｃｋ＞  ＜！−−在庫数−−＞
＜／ｐｒｏｄｕｃｔ＞
＜／ｂｒａｎｃｈ＞
＜／ｃｏｍｐａｎｙ＞
図２３で、各ノードの次に示す整数は、そのノードに割り当てられている一意のＩＤである。このデータソースの既存のビューが３つあるとする。第１のものは、この企業の名称、説明、およびＷｅｂアドレスを表示しているビューである。第２のものは、この企業の支社およびその場所のリストであり、最後に第３のビューには、各支社での製品の範囲（ｌｉｎｅ）がリストされている。これらのビューのスキーマ・グラフ表現を、図２４、図２５、および図２６にそれぞれ示してある。これらのビューの結果として、生起２７０００、共起２８０００、葉共起２９０００、および単独子共起３００００の頻度テーブルを、図２７、図２８、図２９、および図３０にそれぞれ示してある。同時生起頻度テーブルは、３次元であるが、５つの別々の２次元テーブル３１０００、３２０００、３３０００、３４０００、および３５０００によって示してある。図３１は、Ｐｊ＝ノード１であるテーブル内のエントリｆｒｅｑ（Ｃｋ，Ｐｊ，Ｘ）を含んでいる。同様に、図３２、図３３、図３４、および図３５それぞれは、Ｐｊ＝ノード３、ノード８、ノード９、およびノード１０であるエントリをそれぞれ含む。ここに示す頻度テーブルすべてにおいて、図２８に見られるような、項目２８００５などの空のセルは、それに関連する頻度を保存する必要のない無効なノードの組合せを表す。
【０２４０】
ユーザが、自分のいる市の中で特定の製品を見つけることを希望しているとする。ユーザは、その製品の名前、「ＭＰ３プレイヤー」および市の名前「シドニー」を入力し、両方の名前に対するキーワード検索を行う。図２３からわかるように、これから、２つのヒット・ノードＸ１＝ノード１９およびＸ２＝ノード１３が得られる。このキーワード検索操作に対する可能なコンテキストツリーを決定するために、システム４０００では、図１８の方法１８０００を呼び出す。ヒット・ノードが１つより多くあることから、方法１８０００は、その後、方法２００００の呼び出しをステップ１８０１５で行う。方法２００００は、今度は、方法１２０００の呼び出しをステップ２０００１で行って、結果となるコンテキストツリーのルート・ノードの役をするノードＹｉのリストが得られる。
【０２４１】
方法１２０００では、まず、ステップ１２００１で、ノード３を、ヒット・ノードＸ１とＸ２をどちらも含む最小のサブツリーのルート・ノードとして識別する。したがって、Ａ＝ノード３である。次いで、方法１２０００は、再帰手続きを始めて、このヒット・ノードのもとで、Ａおよびその祖先のそれぞれに対する生起確率の値を計算する。ノードＡでは
Ｐｒ’［Ａ｜Ｘ１∧Ｘ２］＝１
である。Ｙ１＝ノード１、すなわちノードＡの親では、式４７、式４８、および式４９を用いて
【０２４２】
【数６１】
2007519086.tif 000063
【０２４３】
したがって
Ｐｒ’［ｎｏｄｅ  １｜Ｘ１∧Ｘ２］＝０
であり
Ｐｒ’［Ａ  ｒｏｏｔ｜Ｘ１∧Ｘ２］＝１
である。
【０２４４】
このため、方法１２０００は、ノードＡをコンテキストツリーの単一のルート・ノード候補として抜ける。このコンテキストツリーには１というスコアが割り当てられる。方法１２０００の完了後、方法２００００では、第２の、トップ・ダウン走査のフェーズが続けられ、そこでは、ルート・ノードＹ１＝Ａの子孫が処理されて、それらのうちでコンテキスト・ノードが識別される。このフェーズはステップ２００１０で始まり、ここで、Ｐｊがまずノード３になるように設定される。このノードは、２つの異なる子ノードの下にある、ヒット・ノードＸ１およびＸ２の祖先であることから、実行は、結局、方法３９０００のステップ３９０５０へと進み、ここで方法１７０００が呼び出されて、コンテキスト・ノードがその子のうちで決定される。方法１７０００の結果、ノード３の子ノード６〜１０それぞれに割り当てられる値Ｑ１，．．．，Ｑ５は、次の通りである。
【０２４５】
【数６２】
2007519086.tif 000064
【０２４６】
したがって、降順でソートされた組Ｑ１，．．．，Ｑ５は、｛Ｑ１，Ｑ２，Ｑ４，Ｑ３，Ｑ５｝であり、その総計はＴ＝５となる。方法１７０００によって選択されたコンテキスト・ノードの組は、こうして、ノード６、ノード７（Ｑ１＋Ｑ２＞Ｔ／２であるため）、およびノード８、ノード１０（ヒット・ノードの祖先であるため）を含む。次いで、方法３９０００は、ステップ３９０５５で再開して、それ自体を再帰的に呼び出して、子のある選択されたノードそれぞれに対してコンテキストの子ノードの識別を行う。
【０２４７】
Ｐｊ＝ノード８の場合、実行は、ノード８に単一の子孫のヒット・ノード（ノード１３）があることから、ステップ３９０３５へと進み、このポイントで方法１４０００が呼び出されて、コンテキスト・ノードが子ノードの組１１〜１４のうちで識別される。方法１４０００の結果、Ｐｊの子ノード１１、１２、および１４にそれぞれ割り当てられる確率の値Ｑ１、Ｑ２、Ｑ４は次の通りである。
【０２４８】
【数６３】
2007519086.tif 000065
【０２４９】
さらに、方法１４０００では、架空の子ノードＣ０に対する値Ｑ０の計算も行われる。
【０２５０】
【数６４】
2007519086.tif 000066
【０２５１】
したがって、降順でソートされた確率の値の組は、｛Ｑ１，Ｑ２，Ｑ４，Ｑ０｝であり、その総計はＴ＝３となる。方法１４０００によって選択されたコンテキスト・ノードの組は、こうして、ノード１１、ノード１２、ノード１４（Ｑ１＋Ｑ２＋Ｑ４＞Ｔ／２かつＱ１＝Ｑ２＝Ｑ４であるため）、およびノード１３（ヒット・ノードの祖先であるため）を含む。
【０２５２】
これに似た実行パスを、Ｐｊ＝ノード１０の場合にはたどることになり、似た結果が得られる。ノード１０のコンテキストの子ノードの組は、ノード１８〜２２である。したがって、このコンテキストツリーのスキーマ・グラフ３６００は、図３６に示すものようになり、ヒット・ノード１９および１３、ならびにコンテキスト・ノード３、６〜８、１０〜１４、１８〜２２を含む。これらのノードの表現するデータ項目を含む、ユーザへと返される実際のコンテキストツリーは、次のようなものである。
【０２５３】
＜ｂｒａｎｃｈ＞  ＜！−−支社−−＞
＜ｎａｍｅ＞Ｎｏｒｔｈ  Ｒｙｄｅ＜／ｎａｍｅ＞  ＜！−−名称−−＞
＜ｐｈｏｎｅ＞０２９１２３００００＜／ｐｈｏｎｅ＞  ＜！−−電話番号−−＞
＜ａｄｄｒｅｓｓ＞  ＜！−−住所−−＞
＜ｎｕｍｂｅｒ＞１＜／ｎｕｍｂｅｒ＞  ＜！−−番地−−＞
＜ｓｔｒｅｅｔ＞Ｌａｎｅ  Ｃｏｖｅ＜／ｓｔｒｅｅｔ＞  ＜！−−街区  Ｃｏｖｅ通り−−＞
＜ｃｉｔｙ＞Ｓｙｄｎｅｙ＜／ｃｉｔｙ＞  ＜！−−都市  シドニー−−＞
＜ｃｏｕｎｔｒｙ＞Ａｕｓｔｒａｌｉａ＜／ｃｏｕｎｔｒｙ＞  ＜！−−国  オーストラリア−−＞
＜／ａｄｄｒｅｓｓ＞
＜ｐｒｏｄｕｃｔ＞  ＜！−−製品−−＞
＜ｉｄ＞１＜／ｉｄ＞  ＜！−−ＩＤ−−＞
＜ｎａｍｅ＞Ｐｌａｓｍａ  ＴＶ＜／ｎａｍｅ＞  ＜！−−名称  プラズマＴＶ−−＞
＜ｐｒｉｃｅ＞＄１００００＜／ｐｒｉｃｅ＞  ＜！−−価格−−＞
＜ｓｕｐｐｌｉｅｒ＞ＪＥＣ＜／ｓｕｐｐｌｉｅｒ＞  ＜！−−メーカー−−＞
＜ｓｔｏｃｋ＞１０＜／ｓｔｏｃｋ＞  ＜！−−在庫数−−＞
＜／ｐｒｏｄｕｃｔ＞
＜ｐｒｏｄｕｃｔ＞  ＜！−−製品−−＞
＜ｉｄ＞２＜／ｉｄ＞  ＜！−−ＩＤ−−＞
＜ｎａｍｅ＞Ｍｐ３  ｐｌａｙｅｒ＜／ｎａｍｅ＞  ＜！−−名称  ＭＰ３プレイヤー−−＞
＜ｐｒｉｃｅ＞＄５００＜／ｐｒｉｃｅ＞  ＜！−−価格−−＞
＜ｓｕｐｐｌｉｅｒ＞ＨＧ＜／ｓｕｐｐｌｉｅｒ＞  ＜！−−メーカー−−＞
＜ｓｔｏｃｋ＞２０＜／ｓｔｏｃｋ＞  ＜！−−在庫数−−＞
＜／ｐｒｏｄｕｃｔ＞
＜／ｂｒａｎｃｈ＞
＜ｂｒａｎｃｈ＞  ＜！−−支社−−＞
＜ｎａｍｅ＞Ｍｏｒｌｅｙ＜／ｎａｍｅ＞  ＜！−−名称−−＞
＜ｐｈｏｎｅ＞０８９１２３００００＜／ｐｈｏｎｅ＞  ＜！−−電話番号−−＞
＜ａｄｄｒｅｓｓ＞  ＜！−−住所−−＞
＜ｎｕｍｂｅｒ＞１＜／ｎｕｍｂｅｒ＞  ＜！−−番地−−＞
＜ｓｔｒｅｅｔ＞Ｒｕｓｓｅｌ＜／ｓｔｒｅｅｔ＞  ＜！−−街区  Ｒｕｓｓｅｌ−−＞
＜ｃｉｔｙ＞Ｐｅｒｔｈ＜／ｃｉｔｙ＞  ＜！−−都市  パース−−＞
＜ｃｏｕｎｔｒｙ＞Ａｕｓｔｒａｌｉａ＜／ｃｏｕｎｔｒｙ＞  ＜！−−国  オーストラリア−−＞
＜／ａｄｄｒｅｓｓ＞
＜ｐｒｏｄｕｃｔ＞  ＜！−−製品−−＞
＜ｉｄ＞３＜／ｉｄ＞  ＜！−−ＩＤ−−＞
＜ｎａｍｅ＞Ｖｉｄｅｏ  ｐｈｏｎｅ＜／ｎａｍｅ＞  ＜！−−名称  ビデオ電話−−＞
＜ｐｒｉｃｅ＞＄２０００＜／ｐｒｉｃｅ＞＜！−−価格−−＞
＜ｓｕｐｐｌｉｅｒ＞ＮＶＣ＜ｓｕｐｐｌｉｅｒ＞  ＜！−−メーカー−−＞
＜ｓｔｏｃｋ＞１５＜／ｓｔｏｃｋ＞  ＜！−−在庫数−−＞
＜／ｐｒｏｄｕｃｔ＞
＜ｐｒｏｄｕｃｔ＞  ＜！−−製品−−＞
＜ｉｄ＞４＜／ｉｄ＞  ＜！−−ＩＤ−−＞
＜ｎａｍｅ＞ＰＤＡ＜／ｎａｍｅ＞  ＜！−−名称  ＰＤＡ−−＞
＜ｐｒｉｃｅ＞＄１０００＜／ｐｒｉｃｅ＞  ＜！−−価格−−＞
＜ｓｕｐｐｌｉｅｒ＞ＬＰ＜／ｓｕｐｐｌｉｅｒ＞  ＜！−−メーカー−−＞
＜ｓｔｏｃｋ＞５０＜／ｓｔｏｃｋ＞  ＜！−−在庫数−−＞
＜／ｐｒｏｄｕｃｔ＞
＜／ｂｒａｎｃｈ＞
産業上の利用可能性
上記から、説明した配置がコンピュータおよびデータ処理の産業に対して、特に複数の検索からの情報を提示することに関して適用可能であることは明らかである。
【０２５４】
上記では、本発明の一部の実施形態だけを説明しており、これへの変更および／または改変は、本発明の範囲および趣旨から逸脱することなく行うことができ、これら実施形態は例示的であり、制限的ではない。
【０２５５】
（オーストラリア限定）この明細書の文脈では、「含む」（ｃｏｍｐｒｉｓｉｎｇ）が意味するのは、「主として、しかし必ずしももっぱらにではなく含む」（ｉｎｃｌｕｄｉｎｇ  ｐｒｉｎｃｉｐａｌｌｙ  ｂｕｔ  ｎｏｔ  ｎｅｃｅｓｓａｒｉｌｙ  ｓｏｌｅｌｙ）または「有する」（ｈａｖｉｎｇ）または「含む」（ｉｎｃｌｕｄｉｎｇ）であって、「だけから構成される」（ｃｏｎｓｉｓｔｉｎｇ  ｏｎｌｙ  ｏｆ）ではない。「ｃｏｍｐｒｉｓｅ」や「ｃｏｍｐｒｉｓｅｓ」など、「ｃｏｍｐｒｉｓｉｎｇ」という語の変種の意味は、これに対応して変わる。
【図面の簡単な説明】
【０２５６】
【図１】スキーマ・グラフの例の図である。
【図２】キーワード検索方法のフローチャートである。
【図３Ａ】スキーマ・グラフ内の親ノードの２つの例を示す図である。
【図３Ｂ】スキーマ・グラフ内の親ノードの２つの例を示す図である。
【図４】サーバおよびクライアントのコンピュータからなるネットワークの図である。
【図５】ルート・ノードからヒット・ノードへの有向パスに沿って存在しない親ノードの１組の子ノードのうちでコンテキスト・ノードを識別するための方法のフローチャートである。
【図６】ルート・ノードからヒット・ノードへの有向パスに沿って存在しない親ノードの１組の子ノードのうちでコンテキスト・ノードを識別するための別の方法のフローチャートである。
【図７】ルート・ノードからヒット・ノードへの有向パスに沿って存在する親ノードの１組の子ノードのうちでコンテキスト・ノードを識別するための方法のフローチャートである。
【図８】ルート・ノードからヒット・ノードへの有向パスに沿って存在する親ノードの１組の子ノードのうちでコンテキスト・ノードを識別するための別の方法のフローチャートである。
【図９】２つの同じサブツリーをスキーマ・グラフの例の図である。
【図１０】確率平均化によるコンテキスト・ノード識別方法の第１の、ボトム・アップ横断フェーズのフローチャートである。
【図１１】複数のヒット・ノードのあるスキーマ・グラフの例の図である。
【図１２】確率平均化による、複数のヒット・ノードを含むコンテキスト・ノード識別方法の第１の、ボトム・アップ横断フェーズのフローチャートである。
【図１３】確率平均化による、ルート・ノードからヒット・ノードへの有向パスに沿って存在しない親ノードの１組の子ノードのうちでコンテキスト・ノードを識別するための方法のフローチャートである。
【図１４】確率平均化による、ルート・ノードからヒット・ノードへの有向パスに沿って存在する親ノードの１組の子ノードのうちでコンテキスト・ノードを識別するための方法のフローチャートである。
【図１５】子孫のヒット・ノードがすべて単一の子ノードの下に位置する親ノードの例の図である。
【図１６】複数のヒット・ノードすべてが単一の子ノードの下に位置する場合に対する、確率平均化による、ルート・ノードからヒット・ノードへの有向パスに沿って存在する親ノードの１組の子ノードのうちでコンテキスト・ノードを識別するための方法のフローチャートである。
【図１７】複数のヒット・ノードが複数の子ノードの下に位置する場合に対する、確率平均化による、ルート・ノードからヒット・ノードへの有向パスに沿って存在する親ノードの１組の子ノードのうちでコンテキスト・ノードを識別するための方法のフローチャートである。
【図１８】１つまたは複数のヒット・ノードが存在する可能性のある、コンテキスト・ノードを識別するための方法のフローチャートである。
【図１９】単一のヒット・ノードを含む場合に対するコンテキストツリーを構築するための方法のフローチャートである。
【図２０】複数のヒット・ノードを含む場合に対するコンテキストツリーを構築するための方法のフローチャートである。
【図２１】観測頻度がヒット・ノードからなる元の組での観測頻度よりも高いヒット・ノードからなる代替の組を構築するための方法のフローチャートである。
【図２２】観測頻度がヒット・ノードからなる組よりも高いそのヒット・ノードからなる組の祖先を選択するための方法のフローチャートである。
【図２３】スキーマ・グラフの例の図である。
【図２４】データ・ビューの例のスキーマ・グラフの図である。
【図２５】データ・ビューの別の例のスキーマ・グラフの図である。
【図２６】データ・ビューのさらに別の例のスキーマ・グラフの図である。
【図２７】図２４、２５、および２６のデータ・ビューから生じる生起頻度テーブルの図である。
【図２８】図２４、２５、および２６のデータ・ビューから生じる共起頻度テーブルの図である。
【図２９】図２４、２５、および２６のデータ・ビューから生じる葉の共起頻度テーブルの図である。
【図３０】図２４、２５、および２６のデータ・ビューから生じる単独子の共起頻度テーブルの図である。
【図３１】図２４、２５、および２６のデータ・ビューから生じる同時生起頻度テーブルのある部分の図である。
【図３２】図２４、２５、および２６のデータ・ビューから生じる同時生起頻度テーブルの別の部分の図である。
【図３３】図２４、２５、および２６のデータ・ビューから生じる同時生起頻度テーブルのさらに別の部分の図である。
【図３４】図２４、２５、および２６のデータ・ビューから生じる同時生起頻度テーブルのさらに別の部分の図である。
【図３５】図２４、２５、および２６のデータ・ビューから生じる同時生起頻度テーブルのさらに別の部分の図である。
【図３６】２つのキーワードを含むキーワード検索操作の結果として返されるコンテキストツリーのスキーマ・グラフの図である。
【図３７】記載した配置を実施できる汎用コンピュータの図式的な構成図である。
【図３８】図１９に示す単一のヒット・ノードを含む場合に対するコンテキストツリーを構築するための方法内部の下位プロセスのフローチャートである。
【図３９】図２０に示す複数のヒット・ノードを含む場合に対するコンテキストツリーを構築するための方法内部の下位プロセスのフローチャートである。
【図１】
2007519086.tif 000067
【図２】
2007519086.tif 000068
【図３Ａ】
2007519086.tif 000069
【図３Ｂ】
2007519086.tif 000070
【図４】
2007519086.tif 000071
【図５】
2007519086.tif 000072
【図６】
2007519086.tif 000073
【図７】
2007519086.tif 000074
【図８】
2007519086.tif 000075
【図９】
2007519086.tif 000076
【図１０】
2007519086.tif 000077
【図１１】
2007519086.tif 000078
【図１２】
2007519086.tif 000079
【図１３】
2007519086.tif 000080
【図１４】
2007519086.tif 000081
【図１５】
2007519086.tif 000082
【図１６】
2007519086.tif 000083
【図１７】
2007519086.tif 000084
【図１８】
2007519086.tif 000085
【図１９】
2007519086.tif 000086
【図２０】
2007519086.tif 000087
【図２１】
2007519086.tif 000088
【図２２】
2007519086.tif 000089
【図２３】
2007519086.tif 000090
【図２４】
2007519086.tif 000091
【図２５】
2007519086.tif 000092
【図２６】
2007519086.tif 000093
【図２７】
2007519086.tif 000094
【図２８】
2007519086.tif 000095
【図２９】
2007519086.tif 000096
【図３０】
2007519086.tif 000097
【図３１】
2007519086.tif 000098
【図３２】
2007519086.tif 000099
【図３３】
2007519086.tif 000100
【図３４】
2007519086.tif 000101
【図３５】
2007519086.tif 000102
【図３６】
2007519086.tif 000103
【図３７】
2007519086.tif 000104
【図３８】
2007519086.tif 000105
【図３９】
2007519086.tif 000106
【国際調査報告】
2007519086.tif 000107
2007519086.tif 000108
2007519086.tif 000109