ＸＭＬのための簡素インデックス構造
簡素データおよびインデックス構造は、理論上の最適条件付近に記憶サイズの条件を設定している場合に更新および検索動作の効率を最大にすることを目的とする。本発明の簡潔なインデックス構造は、階層構造で表されたデータに索引をつける。前記インデックスは、キーとして全ての異なった根から葉への経路または固有要素のタグ名の記号表に含まれる。記号表におけるキーのエントリは、前記キーに関連したノードの変換された位相情報とともに（図２２）、前記位相情報で使用された変換方法の表示情報を持っており（図１７）、使用された前記変換方法は、前記キーに関連したノード間の位相関係に基づいている。また、本発明は、前記簡素インデックス構造を構成、使用および更新するためのコンピュータシステムおよびコンピュータソフトウェアに関する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、簡素なデータおよびインデックス構造が理論的な最適条件に近づくように記憶容量サイズの制限条件を設定している間に、いかなるデータについても更新および検索動作の効率を最大にすることを目的としている。より詳細には、本発明は、簡素インデックス構造、簡素インデックス構造を使用する方法、簡素インデックス構造を作成する方法、簡素インデックスを作成する方法を実行するコンピュータソフトウェアアプリケーション、簡潔インデックスを作成および使用するためのコンピュータシステムに関するものである。
【０００２】
本願は、２００５年１２月６日に出願されたオーストラリア仮特許出願第２００５９０６８４６号に基づく優先権を主張し、その内容が引用によってここに組み込まれている。
【背景技術】
【０００３】
拡張マーク付け言語（ＸＭＬ）データと従来の関係データとの間の主な相違点は、関係データが二次元テーブルを使用して組織化されている一方、ＸＭＬデータは階層構造を持つツリーで構成されている。
【０００４】
例えば、ＸＭＬの短片が以下の数１のように与えられる。
【０００５】
【数１】
【０００６】
これは図１に示されているような階層的ツリーで表すことができる。
【０００７】
ＸＭＬ照会を効率的に処理するために、いくつかのツリー探査方法が存在するが、セットベース問い合わせ処理（従来の関係データベース）がさらに好ましい。例えば、大きなＸＭＬ文書で照会処理をするとき、探査に基づいた方法を使用して実行するために、照会処理が困難になるとともに実行時間が長くなる。
【０００８】
関係データベース管理システムでは、セットベースの処理の中に中間結果を返すデータベース・インデックスを作成および使用することによって照会性能を高めることができる。しかしながら、関係データベースに存在しないＸＭＬデータにおけるセットベース問い合わせ処理には欠点がある。これらの欠点は、あらゆるノードを照会するときに、２つの任意のＸＭＬノードの位相関係を問い合わせる必要性があることで生ずる。
【０００９】
ＸＭＬ照会は、複数のパス表現で構成することもできる。パス表現は、結果ノードが満たす必要がある位相関係を有することとしてもよい。例えば、パス表現 /a[b]/c は、ノードラベルとしてｃがある全てのノードを求めるとともに、ラベルａがある親ノードとラベルｂがある兄弟ノードとを持つ全てのノードを求める。いかなる種類の先祖／子孫についての照会にも効率的に答えるためには、構造的接続動作が必要である。構造的接続動作は、以下の技術として名称がある。潜在的派生ノードリストとともに潜在的先祖ノードリストが与えられれば、前記リストのノード間の先祖−子孫関係が決定される。
【発明の開示】
【発明が解決しようとする課題】
【００１０】
インデックスは、特定ラベルの条件を満たす１セットのノードを取得するためにたびたび提供される。位相関係を判断するために必要なナンバリング構造を有するインデックスは、作成およびメンテナンスに高いコストがかかる。最も一般的なナンバリング構造は、スタート−エンド−深さのトリプレット、前順−後順−深さのトリプレット、またはデューイ符号化を使用する。ｎノードとともにＸＭＬ文書が与えられれば、トリプレットの中の各ナンバを表すために少なくとも log n ビットを必要とする。インデックスが文書サイズに比例しているノードセットを返す場合、そのようなセットを表すためだけに少なくとも O(n log n) ビットが必要となる。全体の位相を簡素に表すためには 2n + o(n) ビットのみが必要となる、ことが知られている。したがって、そのようなインデックス（最も一般的なナンバリング・スキーマによる）は、オリジナル文書自体よりも実質的に多くのスペースを使用するので、インデックスの有用性を顕著に制限する。
【課題を解決するための手段】
【００１１】
第１の態様によれば、本発明は、階層構造で表されたインデックスデータのための簡素インデックス構造を提供し、前記インデックス構造は、キーとして全ての異なった根から葉への経路の記号表、またはキーとして固有要素のタグ名の記号表を有し、前記記号表におけるキーについてのエントリは、前記キーに関連したノードの変換された位相情報とともに、前記位相情報で使用される変換方法の表示情報を持っており、使用される前記変換方法は、前記キーに関連付けられたノード間の位相関係に基づいている。
【００１２】
前記位相情報は、各ノードについてトリプレット番号づけ構造を有することとしてもよい。前記トリプレット番号づけ構造は、スタート・エンド・深さトリプレット番号づけ構造または前順・後順・深さトリプレット番号づけ構造であることとしてもよい。前記トリプレットは、ツリー探査オーダの中にあることとしてもよい。
【００１３】
前記階層構造は、エクステンシブルマークアップ言語（ＸＭＬ）であることとしてもよい。
【００１４】
前記変換方法は、前記リストの各トリプレットにおける各値を差分符号化するように、前記位相情報を差分符号化するステップを有することとしてもよい。前記トリプレットの第１の差分符号化値は、連続したトリプレットのスタート位置の差であることとしてもよい。各ノードのスタート位置とエンド位置との間の差が与えられれば、前記トリプレットの第２の差分符号化値は、連続したトリプレット間のそれらの値の差であることとしてもよい。第３の差分符号化値は、連続したトリプレットの深さについての差であることとしてもよい。
【００１５】
前記変換方法の情報は、シフトされたキーに関連した各ノードについてのトリプレットの前記第１、第２または第３の値のそれぞれであるシフト値を有することとしてもよい。
【００１６】
前記変換方法の情報は、全てのノードの前記トリプレットの前記第１、第２または第３の値のそれぞれをグラフ表示する棒グラフの形状の表示情報を有することとしてもよい。
【００１７】
前記変換方法の情報は、前記キーに関連した全てのノードの前記トリプレットの前記第１、第２または第３の値を出力するパターン関数を有していることとしてもよい。
【００１８】
前記変換方法の情報は、前記変換された位相情報が前記位相情報と同一であることを示すものとしてもよい。
【００１９】
キーについてのエントリは、前記位相情報の変換に使用された複数の方法を保持していることとしてもよい。前記キーに関連付けられた全てのノードの前記トリプレットの前記第１、第２または第３の値のそれぞれについて方法があることとしてもよい。
【００２０】
前記変換された位相情報は、更新圧縮形式で保存されている。
【００２１】
前記位相情報は、簡素データ構造から取得されることとしてもよい。前記簡素データは、平衡カッコ表示を使用しているノードの入れ子を表す位相レイヤ（層０）を有することとしてもよい。すなわち、ツリーの前順探査は、開タグが遭遇されたとき、１ビット（開カッコ）出力し、閉タグが遭遇されたとき、反対ビット（閉カッコ）を出力する。
【００２２】
第２の態様によれば、本発明は、簡素インデックス構造を使用する方法であって、
記号表において所要キーを位置付けるステップと、
前記キーに関連したノードの前記位相情報の変換に使用された変換方法に基づき、前記キーに関連した全てのノードの位相情報を検索するために前記変換された位相情報を再変換するステップと、を有する簡素インデックス構造を使用する方法を提供する。
【００２３】
前記簡素インデックス構造は、構造的結合の照会を処理するために使用されることとしてもよい。
【００２４】
第３の態様によれば、本発明は、階層構造で表されたデータについて簡素インデックスを作成する方法を提供するものであって、前記方法は、
１
ツリー探査命令におけるノードの位相符号化リストを生成するためにデータを解析するステップと、 異なった根から葉への経路に関連したノードまたは固有要素のタグ名に関連したノードについて、前記ノード間の位相関係を評価するステップと、
２
前記評価に基づき、前記異なった根から葉への経路または固有タグ名に関連したノードの前記位相符号化リストを変換するステップと、
３
キーとして前記異なった根から葉への経路または固有タグ名を持っている記号表においてエントリを作成するステップと、を有し、
前記エントリは、使用された前記変換方法の表示情報と共に前記キーに関連した変換された位相情報に含まれる。
【００２５】
前記解析するステップは、拡張アレイに記憶された位相符号化リストを生成するために前記ツリーを探査するステップを有することとしてもよい。前記位相符号化リストは、各ノードについてトリプレット番号づけ構造を有していることとしてもよい。前記トリプレット番号づけ構造は、スタート・エンド・深さトリプレット番号づけ構造であることとしてもよい。
【００２６】
前記拡張アレイは、一旦、所定のブロックサイズを持ち、前記方法は、位相符号化リストを生成し続けるとともに、新たなブロックの拡張アレイに記憶するステップをさらに有することとしてもよい。
【００２７】
位相符号化リストを生成した後に、上記で説明したように前記位相符号化リストを別個に再符号化する。前記方法は、クラスタ化アルゴリズムを実行するステップをさらに有することとしてもよく、複数のクラスタが特定される場合、前記ブロックが各クラスタのより小さいブロックに分割されることとしてもよい。
【００２８】
前記変換方法の情報は、シフトされている値、グラフ化された値、または上記で説明されたパターン関数を生成する情報を有することとしてもよい。
【００２９】
第４の態様によれば、本発明は、階層構造で表されたデータについて簡素インデックスを作成する方法を実行するコンピュータソフトウェアアプリケーションを提供する。
【００３０】
第５の態様によれば、本発明は、階層構造で表されたデータについて簡潔インデックスを作成するためのコンピュータシステムを提供するものであって、前記コンピュータシステムは、
異なった根から葉への経路に関連したノードまたは固有要素のタグ名に関連したノードについて、前記ノードの間の位相関係を評価するために、ツリー探査命令におけるノードの位相符号化リストを生成するようにデータを解析する処理手段と、
前記評価に基づき、前記異なった根から葉への経路または固有タグ名に関連したノードの前記位相符号化リストを変換する処理手段と、
キーとして前記異なった根から葉への経路または固有タグ名を持つエントリとともにインデックスを記憶する記憶手段と、を有し、
前記エントリは、使用された前記変換方法の情報と共に前記キーに関連した変換された位相情報に含まれる。
【００３１】
前記記憶手段は、コンピュータ読取り可能記憶媒体であるとともに、上記で説明された階層構造で表されたデータについて簡潔インデックスを作成する方法の実行動作が可能なコンピュータソフトウェアアプリケーションを記憶することとしてもよい。前記コンピュータシステムは、ＰＤＡ，携帯電話またはラップトップなどの携帯型コンピュータである。
【００３２】
第６の態様によれば、本発明は、上記で説明された階層構造で表されたデータについて簡素インデックスを使用するためのコンピュータシステムを提供するものであって、前記コンピュータシステムは、
前記簡素インデックスを記憶する記憶手段と、
前記キーに関連したノードの前記位相情報の変換に使用された変換方法に基づき、前記キーに関連した全てのノードの位相情報を検索するために前記変換された位相情報を再変換するように、前記記号表において所要キーを位置付ける処理手段と、を有する。
【００３３】
前記記憶手段は、コンピュータ読取り可能記憶媒体であるとともに、上記で説明された階層構造で表されたデータについて簡素インデックスを使用する方法を実行するための動作が可能なコンピュータソフトウェアアプリケーションを記憶することとしてもよい。
【００３４】
前記コンピュータシステムは、インターネットなどを介して、遠隔装置からデータ処理要求信号を受信する通信手段をさらに有することとしてもよい。
【００３５】
前記コンピュータシステムまたは遠隔装置は、ＰＤＡ，携帯電話またはラップトップなどの携帯型コンピュータであることとしてもよい。
【００３６】
前記インデックスは、データの位相構造を取得する方法としてスペース効率が良いとともに、ＸＭＬデータを効率的に実行する構造的結合を可能にすることができる。ＸＭＬデータを処理するとき、メモリ使用量の大部分が中間結果セットを表すことに費やされる（最終結果セットと同様に）。メモリスペースが不足しているとき、付随的なディスク入出力動作のために照会性能がかなり低下する。本発明のインデックスを使用すれば、中間セットは、簡素な形で表されるとともに、構造的結合が効率的動作を実行するように使用されることができる。
【発明を実施するための最良の形態】
【００３７】
ここで、本発明の実施形態は、添付図面を参照して説明される。
【００３８】
図３は、本発明の実施形態を実現できるコンピュータシステム４を示すブロック図である。デスクトップコンピュータ６とＰＤＡまたはモバイル８とは、共に、本発明に使用できるコンピュータの実施形態である。両方の装置は、一般に本技術分野で理解されている所定の処理手段、記憶手段、通信手段、入力手段および出力手段を具備している。
【００３９】
本発明を適用するために、装置６および８の両方は、本発明の簡素インデックスにアクセスするためにソフトウェアアプリケーション１０を使用する必要がある。本実施形態において、装置６および８は、それぞれの記憶手段上でコンピュータ６および８にローカルに記憶されたインデックス１２を持つことができる。しかしながら、ＰＤＡ８のような装置は、より小さい処理手段および記憶容量を持っているとしてもよく、簡素インデックス１２にアクセスするためにインターネット１４を使用することとしてもよい。すなわち、全てのインデックス１２と関連処理１６、インデックス１２とソフトウェア１８は、ＰＤＡ８から分離されて記憶されている。
【００４０】
前記ソフトウェア（または遠隔ソフトウェアへのログイン）１０は、照会エンジン１６の所定処理を（ローカルまたはリモートのいずれかで）実行するようにプロセッサを動作させることができる。照会エンジン１６は、装置８および１０に入力された問い合わせを解決するために簡素インデックス１２を使用する。簡素インデックス１２は、（ローカルまたはリモートのいずれかの）メモリに記憶されているとともに、以下に詳細に説明するように作成および更新される。本発明の簡素インデックス１２は、インデクサソフトウェアコンポーネント１８に関して作成されている。コンポーネント１８は、ＸＭＬ文書２０およびサードパーティ・データベース２２などを、入力して様々な情報に直接索引を付ける。あるいはまた、ＸＭＬ文書２０およびサードパーティ・データベース２２は、簡素な形式にデータ変換する簡素エンコーダ２４を使用して符号化されることができ、その後に記憶される２６。また、インデクサ１８は、簡素インデックス１２を形成するための入力としてこれを取得することができる。さらなるソフトウェアとして、簡素ＤＢＭＳを解釈できる簡素アクセサ２８を有する。簡素アクセサ２８は、装置６または８への照会の結果を提供するためのものであり、または簡素処理時にプロセッサ１６によって使用される。
【００４１】
照会は、簡素データベース２６に保存された記録を返信することとしてもよい。これらの結果をコンピュータ８または１０に返信するために、さらなるコンピュータアプリケーション２８が簡素データベース２６にアクセスして解釈するように照会エンジン１６によって使用されることとしてもよい。あるいはまた、コンピュータ８または１０は、直接に簡素ＤＢＭＳ２６にアクセスして解釈するために簡素アクセスソフトウェア２８に使用されることとしてもよい。
【００４２】
ここで、集積簡素（ISX）システムの簡素記憶レイヤ２６について説明する。ＩＳＸは三層、すなわち、位相レイヤと内部ノードレイヤとリーフノードレイヤとを有している。これらのレイヤの概要が図３に示されている。
【００４３】
位相レイヤは、ＸＭＬ文書のツリー構造を記憶するとともに、高速ナビゲーションアクセスと構造的な結合と更新とを容易にする。内部ノードレイヤは、高速な照会のために、ＸＭＬ要素と、属性と、テストデータのシグネチャとを記憶する。最後に、リーフノードレイヤは、文書のテキストデータを記憶する。テキストデータは、様々な一般的な圧縮法によって圧縮でき、位相レイヤを使用して参照できる。
【００４４】
本実施形態の説明では位相レイヤに集中する。従来の方法と異なり、位相レイヤのこの表示では、ポインタを利用しない。それは、効率的なノードナビゲーションおよび更新を支援する平衡カッコ符号化に基づいている。
【００４５】
層０に使用される平衡カッコ符号化は、あらゆるＸＭＬ文書における要素ノードの入れ子もたらすとともに、前記ツリーの前順探査によって構成することができる。開カッコは開タグが探査時に遭遇されたときに出力され、閉カッコは閉タグが探査時に遭遇されたときに出力される。
【００４６】
例えば、図４に示すＸＭＬ文書の抜粋を挙げると、層０の平衡カッコ符号化は図５に示すように記憶される。カッコの下部の矢印は、カッコの組を示している。明瞭化のため、ビットごとの動作の詳細およびオブジェクトのような１ビット（カッコ）の処理は省略する。
【００４７】
余分は、前記位相の与えられたセクションで生じている開カッコおよび閉カッコの数の間での差分である。例えば、図５において、「dblp」の開カッコと「＠mdate」の閉カッコとの間の余分は２である。テキストノード「2003」の閉カッコと「booktitle」の開カッコとの間の余分は、−１である。ＸＭＬ文書ツリーにおけるノードＸの深さは、Ｘの開カッコと前記文書の始まりとの間の余分を検出することによって計算することができる。例えば、図５において、「author」における開カッコの深さは３である。
【００４８】
この符号化方法には、いくつかの利点がある。第１に、位相的性質（深さ、スタート／エンド位置、前順番号／後順番号）、位相的関係（原型／派生物、文書順番）、文書探査、ＤＯＭネビゲーションおよびＸパス軸は、上記のカッコ表示を使用して全て決定することができる。第２に、小セットの物理的な演算子を持つだけでデータベースが簡素化する。
【００４９】
2n ＝ O(n) から望ましくない下記数式２へ、スペース用途を増加させるので、リンクするためのポインタに基づいたあらゆる手法を回避する。これは図６に図示されている。
【００５０】
【数２】
【００５１】
図７のフローチャートと下記数式３のＸＭＬ文書抜粋とを参照して、ＩＳＸシステムのさらなる実施形態がここで説明される。
【００５２】
【数３】
【００５３】
実際には、ＸＭＬ文書は、ここで説明された抜粋よりもかなり大きい。平衡カッコを使用して、この文書は下記の数式４のように表すことができる。
【００５４】
【数４】
【００５５】
そこで、平衡カッコを使用するＸＭＬ文書の抜粋の位相は、下記のように表される（ステップ３０）。
（ （（（））） （（（））） （（（））） ）
開カッコはバイナリ・ビット０によってメモリ内で表されるとともに、閉カッコはバイナリ・ビット１としてメモリ内で表される。これに続いて、階層構造が下記数式のようにメモリ内に記憶される（ステップ３２）。
00001110001110001111
【００５６】
そこで、すべての「０」が新しいノードのスタートを示している。すべての「０１」の組合せがリープノードなどの変換を示している。
【００５７】
このシステムを使用すると、あらゆる文書のための記憶空間が２ｎビットになる（ここで、ｎはノードの数である）。
【００５８】
もちろん、ステップ３０および３２は１つの単一ステップとして実行することができる。さらに、「１」ビットが開カッコを示すとともに、「０」ビットが閉カッコを示すように、ビットの使用は簡単に交換できる。
【００５９】
以下の抜粋（上記から繰り返される）は、ここではノードのラベルおよび各ビットの位置番号とともに垂直に並べられている。
【００６０】
【数５】
【００６１】
ここで、ノード＜ａ＞が位置「０」にあるとともに、第３ノード＜ｂ＞が位置１３にあることが分かる。
【００６２】
ここで、位相のビット表示を使用することでブロックに照会を実行することができる。例えば、照会は「位置１３のノードの親の位置はなにか」としてもよい。
【００６３】
本実施形態ではカッコが組みの形式であることを知っているので、「１」よりも２つ多く「０」が見つかるまで後向きにブロックを走査した場合、親の位置を見出すことができる。この場合の親の位置は位置「０」である。
【００６４】
文書のビット表示は、初めに、特定サイズのブロックに分割される（ステップ３４）。例えば、上記説明の抜粋は、下記の数式６のように２つのブロックに分割される。
【００６５】
【数６】
【００６６】
各ブロックは、層１を有する組(tuples)を生成するために要約される（ステップ３６）。各ブロックについて下記の情報が計算される。
・ ブロックにおける「０」の数。
・ ブロックにおける「１」の数。
・ 前方最大差分、すなわち、左から右にブロックを走査している間のランニング合計が計算される。「０」のランニング合計値から始まって、「０」ビットが遭遇するたびにランニング合計が１だけ増加され、「１」ビットが遭遇するたびにランニング合計が１だけ減少される。ブロックにおけるあらゆる位置に及ぶ前記ランニング合計での最大値が前方最大差分になる。
・ 前方最小差分、すなわち、ランニング合計は上記のように計算される。ブロックにおけるあらゆる位置に及び前記ランニング合計での最小値が前方最小差分になる。
・ 後方最大差分、すなわち、ランニング合計は前方最大差分を参照して上記のように計算されるが、その代わりにブロックは右から左に走査される。
・ 後方最小差分、すなわち、ランニング合計は前方最小差分を参照して上記のように計算されるが、その代わりにブロックは右から左に走査される。
・ ノードの数、すなわち、「０１」の組合せの回数がブロックで検出される。最終ビットについて、以下のブロックのビットが検査されることとしてもよい（あるいはまた、選択された方法が一貫して提供されて、前ブロックの最終ビットが検査されることとしてもよい）。
【００６７】
そこで、ブロック「００００１１１０００」について、概要情報は（７、３、４、１、４、０、２）として現れる。
【００６８】
そして、ブロック「１１１０００１１１１」について、概要情報は（３、７、０ ４の−１−４、１）として現れる。
【００６９】
この概要情報を使用して、層１の組の上記２つの実施形態に基づき、ＤＯＭ照会をここで説明することができる。例えば、「位置１３でのノードの親はなにか」のように照会を取る。
【００７０】
本実施形態では、位置１３でのビットから開始してブロックの発端まで後方に走査する。位置１３からブロックの発端まで、本実施形態では以下のビッット「１１１０」を持つ。「０」の数は１であり、そして「１」の数は３である。「１」の数から「０」の数を引くと「−２」が求まる。本実施形態ではここで、前ブロックから後方最大差である「４」を得るとともに、数「２」を得るために「−２」を加える。これから、本実施形態では、一致しているビットが前ブロックのなかにあることを、ここで知得する。
【００７１】
文書が大きいとき、層１の要約の組を生成するプロセスを繰り返すことができ（ステップ３８）、このとき、層２の生成が層１のデータに基づいて行われる。全ての場合、通常、２層で十分である。一方、本実施形態では、層１の組をブロックに分割するとともに、層２を生成するために更なる概要組を生成する。
【００７２】
ＸＭＬ文書の位相情報を表すこの方法は、理論的に最小限の恒常的要因のなかで、空間効率が良い所定スペースを持つ。常数ｅについて、１≦ｅ≦２、ｎノードの文書であるとき、概要情報（ｏ（ｅｎ））に加えてＸＭＬ文書（２ｎ）の位相を表すために、本実施形態では「２ｅｎ＋ｏ（ｅｎ）」ビットを必要とする。ノード挿入は平均して一定時間で処理することができるが、最悪の場合「Ｏ（ｌｇ２ｎ）」時間であるとともに、全てのノードナビゲーション動作は下記数式７の時間を要するが平均して一定時間である。
【００７３】
【数７】
【００７４】
また、位相情報を表すこの方法は、データ処理のための全ての所定初期動作について低いアクセスおよび更新コストを維持する。また、それは、ほぼ一定時間でのナビゲーション動作を支援する。
【００７５】
ＸＭＬ文書を表す「０」および「１」の第１点検を支援するために、簡素インデックス構造（ＳＩＳ）１２を構成することができる。このインデックスは、より効率的に文書を照会する方法を提供する。
【００７６】
ＳＩＳは、記号表で作られる。記号表は、全ての異なった根から葉への経路のエントリまたは異なるタグ名を持っている。例えば、図１においてＸＭＬ文書抽出のために、異なった根から葉への経路は｛/a, /a/b, /a/b/c｝であるとともに、異なるタグ名は
｛a,b,c｝である。
【００７７】
記号表の各エントリは、何らかの統計情報の他に実インデックス（生インデックスとして知られている）もまた保持し、その経路またはタグ名を構成するタグの全てのインスタンスを容易に位置付ける。前記統計情報は、生インデックスの変換を規定する。それは、タグ名の人気と照会および更新の頻度とに関する情報を有している。
【００７８】
生インデックスの変換は、スペース用法と、照会性能と、更新コストとについて良い妥協案を提供する。前記変換法は、その時々で与えられたＸＭＬ文書に最も合う方法にしたがって複数の生インデックスに作用する。
【００７９】
生インデックスは、下記のデータ構造、ブロック、ノードセットサイズへの依存、照会および更新の頻度、の一つ以上で構成されている。
・ 全位相符号化リスト：それは、元の形のままでトリプレット（スタート、エンド、深さ）のリストで構成される。各トリプレットはノードの位相情報を符号化する。前記リストは、如何なる圧縮フォーマットも使用せずに記憶される。このデータ構造は、インデックスが付けられるＸＭＬ文書の中で生じる更新のところに現れる。また、それは、、生インデックスのエンドに現れ、新たに生成されたトリプレットはフルサイズブロックを生成しない。
・ ノード識別子リスト：ノード識別子リストは、全位相符号化リストの他の形であり、層（例えば、層０，層１および層２）から間接的に派生したトリプレット（スタート、エンド、深さ）の中の３つの値とともに、永続的ノード識別子を使用している。ノード識別子リストは、スペースが主要な関心事項であるときに使用され、少なくとも前記値を引き出す性能オーバーヘッドがトリプレットをロードすることよりもかなり良い。
・ ビットアレイフラグ：ビットアレイフラグはノード識別子リストの他の形であり、ここでノード識別子の総数はＸＭＬ文書におけるノードの総数の一定差分の範囲内にある。
・ 部分位相符号化リスト：データ構造は明示のノード識別子を持っておらず、またトリプレットの中のスタート値は（非永続的）識別子として機能することができる。ここで、本実施形態では、トリプレットの代わりにスタート値のみを記憶する。
・ 差分、全位相符号化リスト：このデータ構造は、概要を生成するために第２パイプラインへ全位相符号化リストの完全ブロックを送信することの結果である。前記概要は３つの棒グラフから構成され、各棒グラフは連続したトリプレットのスタート、エンドおよび深さの間の差分値間の関係を表す。前記概要は、固定サイズの値で可変サイズにトリプレットを符号化するための符号化方法を特定する。符号化トリプレットの結果のリストは、概要に隣接して記憶される。
・ 差分ノード識別子リスト：差分ノード識別子リストは、前記「差分、全位相符号化リスト」と同様の方法でノード識別子の差分値の棒グラフを記憶する。
・ 差分部分位相符号化リスト：差分部分位相符号化リストは、前記「差分、全位相符号化リスト」と同様の方法で部分位相符号化リストを記憶する。
・ パターン記述子機能：文書の概要が正確であるとともにトリプレットの差分値が一定であるとき、全位相符号化リストの全体は、破棄されることができるとともに、前記概要およびそれらの前の値にそれぞれ基づく次の「スタート、エンドおよび深さ」値を返す機能に置き換えられることができる。これらのパターン関数は、更新（例えば、新しいノードが前記リストに挿入される）による影響を受けない。
【００８０】
前記インデックスの解釈は、３つのパイプラインを一度に通してＸＭＬ文書を解析することで行われる。ここで、各パイプラインは、前のパイプラインの出力を入力する。第１パイプラインは、ＸＭＬ文書を探査するとともに、リストとして表されたＸＭＬ文書を位相符号化した単純セットを生成する。第２パイプラインは、位相符号化リストの最適差分符号化を決定する。最終的に、第３パイプラインは、前記差分符号化リストからパターン記述子を生成する。ここで本実施形態では、ノードを挙げて、データベースが一定時間で位相ナンバリングを検索できる、と仮定する。
【００８１】
図８のフローチャートを参照して、インデックスを構成する方法を説明する。
【００８２】
第１に、ＸＭＬ文書の簡素表示が探査されるとともに、単純位相符号化リストが生成される（ステップ５０）。
【００８３】
位相符号化リストはトリプレットのリストで構成され、ここで、各トリプレットは単一ノードの位相情報を表す。すなわち、ＸＭＬ文書における各ノードについて、符号化ナンバの３つのタイプがトリプレットを作成するために計算される。それぞれのトリプレットの符号化ナンバは以下を表す。
「０」（開カッコ）のビット位置はノードのスタート
「１」（閉カッコ）のビット位置はノードのエンド
深さ、すなわち、ツリーにおいてどれだけ下側にノードがあるか、またはツリーにおけるノードのレベルがどれだけか。
これらのトリプレットは、ＸＭＬ文書の位相構造を表現するそれらの間と間接的関係がある。「０」のビット位置は各ノードの事前予約ナンバと同一であり、その結果、深さとともにツリーを再構成することが可能となる。しかしながら、「１」のビット位置がなければ、２つのノード間の先祖−子孫関係を応答するのに時間がかかりすぎる。
【００８４】
図１に示されたＸＭＬ文書に基づく照会は以下の数８のようになる。
//b//c[text() = "e"]
すなわち、ノードｂは子孫ｃとともにテキスト「ｅ」を持っているか。本実施形態ではＳＩＳを使用することで応答を得ることができる。
【００８５】
インデックスは、全てのｂと、全てのｃと、全ての「ｅ」とを返す。そこで、本実施形態では、正しい親／子孫方向で関連していることを確認するために、返されたノード間の構造関係を判断する。これをするために、本実施形態では各ノードについて計算されたトリプレットを使用する。
【００８６】
例えば、
【００８７】
【数８】
【００８８】
前記構造関係は、この情報から判断することができる。ここで、本実施形態では、ノードａの第１「０」ビットが「０」のスタートビット位置にあるとともに、ノードａの最後の「１」ビットが「１９」の位置にある、ことがわかる。また、ここで、本実施形態では、第２ノードｂの第１「０」ビットが「７」のスタートビット位置にあるとともに、第２ノードｂの最後の「１」ビットが「１２」の位置にある、ことがわかる。
【００８９】
そこで、ノードｂがノードａの子孫である場合、ノードａのスタート位置がノードｂよりも小さくなるべきである（０＜７）。さらに、ノードｂのエンド位置は、ノードａのエンド位置よりも小さくなるべきである（１２＜１９）。
【００９０】
下記の数式９は、上記で説明したトリプレットに基づき図１から抽出したＸＭＬ文書についての位相符号化リストである。
【００９１】
【数９】
【００９２】
例えば、上記
//b//c[text() = "f" ]
のように同一の照会に応答するために、本実施形態では上記３つの位相符号化リストと、ｃリスト対「ｅ」リストの第１マッチとを検索して、「ｅ」の中のあらゆるトリプレットの親であるｃリストの中に全てのトリプレットを返す。トリプレットc2:(8,11,2)と、「ｅ」1:(9,10,3)とについて、
c2.start (8) < “ｅ”1.start (9) and c2.end (11) > “e”1.end (10) and
c2.depth (2) + 1 = “e”1.dpeth (3)
なので、c2 (8,11,2)
は、可能な応答のリストの中にある。
【００９３】
第２に、本実施形態では、ｂリストに対して新たに作成されたリストに一致するとともに、いかなるｂトリプレットの子供に属しないトリプレットをフィルタ出力する。
b2: (7,12,1)については、
b2.start (7) < c2.start (8) and b2.end (12) > c2.end (11) and
b2.depth (1) + 1 = c2.depth
のようになる。c2がテスト条件を満たすので、それが応答である。
【００９４】
前記リストにおけるノードの数が少ない場合のみ、または、ｎノード文書の全体に対する前記リストの割合が小さい場合のみ、例えば、インデックスにおいてO(lgn)ノードからO(n/lg2n)ノードにいたるまで、本実施形態では全位相符号化リストを維持する。位相符号化リストは、拡張アレイと呼ばれる特別なデータ構造で維持される。ノードセットは、それらの関連文書命令、すなわち、ノードセットにおけるそれらの各ノードの事前予約値にしたがって記憶されなければならないことに留意すべきである。
【００９５】
一旦、閾値に達すると、拡張アレイの一部はブロックを有するとみなされる。本実施形態では、第２パイプラインの中にそのブロックを有する拡張アレイを通すとともに、差分符号化を持つ新たな拡張アレイの構築を続行する（ステップ５２）。この手法の利点は、新たに挿入されたノードがその後の更新によってさらなる影響を受けることになりそうであると推定できることである。
【００９６】
第２パイプラインは、拡張アレイにおける１ノード当たりの各符号化数の間での値の差分を第１検査する動作をするとともに、差分符号化を使用して再符号化する。再符号化をしている間、差分値のおおまかな分布に伴う最小差分および最大差分の２つの値の軌跡を保持する。差分値のおおまかな分布に伴う最小差分と最大差分。本実施形態では、位相リストを符号化する前に、棒グラフとして後にスケーリングするために最大差分および最小差分の値を記憶する。
【００９７】
第１に、同一のサイズのブロックにトリプレットを分割する。すなわち、第１ブロックは以下の通りである。
( s1, e1, d1) ( s2, e2, d2) ... ( sb, eb, db )
そして、第２ブロックは以下の通りである。
(+1, eb+1, db+1) (sb+2, eb+2, db+2), . . (s2b, e2b, d2b)
【００９８】
そして、ブロックにおいて特定のノードタイプに関連する各トリプレットについて、以下に基づき３つの棒グラフを作成する。
連続したトリプレットのスタート位置の間の差分（Δスタートと呼ばれる）、すなわち、
s2-s1, s3-s2, s4-s3, ..., sb-sb-1
連続したトリプレットのエンド位置とスタート位置との間の差分の差分（Δエンドと呼ばれる）、すなわち、
(e2-s2)-(e1-s1), (e3-s3)-(e2-s2), ..., (eb-sb)-(eb-1-sb-1)
連続したトリプレットの深さの間の差分（Δ深さと呼ばれる）、すなわち、
d2-d1, d3-d2, d4-d3, ...,db-db-1
【００９９】
各棒グラフは、対応するΔの中の異なる値の全てで構成されている。それぞれの異なる値について、発生回数の軌跡を保持する。また、本実施形態では、それらの異なる値が生ずる範囲の軌跡を保持する。
【０１００】
そして、クラスタ化アルゴリズムが前記棒グラフに実行される。差分値の複数のクラスタが存在している場合、拡張アレイおよび３つの棒グラフをそれらのクラスタに分割するとともに、次のステップを別々に実行する。
【０１０１】
各クラスタについて、最小差分の値を記憶するとともに、オリジナルとして最小差分を使用して全ての差分値を再調整する。これは、全ての差分値をより少ないビットで符号化できることを意味している。
【０１０２】
また、各クラスタについて、本実施形態では、棒グラフの形を検査して、以下のカテゴリに分類する。
・ 慎重(Discreet)
慎重シナリオの下では、前記棒グラフはあらゆる範囲に渡ることができるが、その全ての値は差がｋの差分値の小セットに渡るだけである。ここで、ｋは、1g nより小さいかまたはほぼ同一である。本実施形態では、エントリｋの慎重テーブルを構築し、差分値を記憶する。慎重テーブルにインデックスを表現する1g kビットを持たせ、１つの値当たりオリジナル1g nビットではなく、全ての差分値について1g k < 1g 1g n ビットを使用してブロックを再符号化する。
・ 平坦
慎重とは異なり、このシナリオは適度により長い範囲 [j, k]で平坦カーブを持つ。ここで、k - j > 1g n である。本実施形態では、前記棒グラフを再調整し、オリジナルとしてjを扱うとともにk - jとしてkを扱う。慎重と同様であるが、テーブルの必要性はなく、１つの値当たり1g (k - j)ビットを使用しての差分値を再符号化することができる。k-jがnよりもかなり小さい値であることが証明でき、あらゆる正常数において、インデックスが付けられるノードの数がn/cである場合に等しい。
・ 下降
下降カーブについて、本実施形態では、第１に、平坦シナリオのように棒グラフを再調整し、次に値のアレイを取得して、それらの差分値を使用してそれらをあらゆるＲＬＥ（ランレングス符号化）方法で再符号化する。ここで、本実施形態では、マイクロ・コードと呼ばれる簡単な、しかし有効な方法を提示する。それぞれ再調整された差分値vは、２つの部分に符号化される。本実施形態では、第１に下記の数１２を単項に符号化し、二進数で下記の数１３の値が続く。
【０１０３】
【数１０】
【数１１】
【０１０４】
この場合、最も一般的に生ずる差分値は、ビットの最小値で符号化される。
・ 上昇
棒グラフのカーブの傾きがより大きな値に向かって傾いている場合、本実施形態では、また、μコードでそれを符号化するが、棒グラフを左から右へ反転させるとともに、上昇シナリオについて同一方法を使用する。
・ 通常
これは、カーブが正規分布で形成されているときである。本実施形態では、第１に、カーブのピークをオリジナルに再調整する。先ず、第１ビットが差分値のサインを示すようにして、次に、差分値の絶対値を取得し、そして残りのビットを再符号化するためにＲＬＥを使用する。
・ 高密度
慎重カテゴリと同様であるが、より大きい。これは、棒グラフがｋ差の差分値の小セットに下降するときであるが、ｋは1g nよりも大きい常数であり、それでも、ｋはnよりも小さい。
【０１０５】
それで、ノードタイプｂに関連した位相符号化リストは、
b (1,6,1) (7,12,1) (13,18,1)
となる。
【０１０６】
棒グラフは、以下のように計算される。スタートの差分についての値（Δスタート）は6 (7-1) および 6 (13-7)である。そして、これらの値の棒グラフは、図９に示すようにプロットされている。
【０１０７】
エンドの差分についての値（Δエンド）は、
0 ((6-1)-(12-7)) および 0 ((12-7)-(18- 13))である。そして、これらの値の棒グラフは、図１０に示すようにプロットされている。
【０１０８】
深さの差分（Δ深さ）については、その値が 0 (-1-1) および 0 (1-1)である。そして、これらの値の棒グラフは、図１１に示すようにプロットされている。
【０１０９】
そして、各棒グラフの分布が分析される。例えば、分布は上昇であるか、下降であるか、通常であるか。分布に依存して、あるオプションは、同一値へ全ての値をシフトするとともに、使用したシフト値を記憶することである。あるいはまた、本実施形態では、異なる形についてＲＬＥなどを符号化する差分変数ビットを使用することができ、またはＺＬ圧縮を使用して高密度にすることができる。
【０１１０】
各棒グラフについて、棒グラフタイプ（慎重、平坦、下降、上昇、通常）が記憶されている。本実施形態では、棒グラフのタイプを検査することで、照会中に前記リストの圧縮型を復号化し、圧縮型を復号化する方法を判断することができる。
【０１１１】
その結果、棒グラフのクラスタは第３パイプラインに渡される（ステップ５４）。ツリーパターンは、特定スキーマに結合するＸＭＬ文書について頻繁に繰り返される。これは、第３パイプラインにおいて更なるスペース効率を獲得するために利用できる。第３パイプラインは、特定パターンがクラスタの差分値の中に生じるか否か発見しようとする。そのようなパターンが存在している場合、全部のクラスタは、前記パターンに結合する値を出力するパターン関数によって置換される。その方法の一つとして、繰り返しパターンを位置付けるＺＬＭ圧縮技術がある。
【０１１２】
３つのパイプラインでの処理の後に、位相符号化のオリジナルリストは、パターン関数と差分符号化リストと位相符号化リストの拡張アレイとの混合リストになる。
【０１１３】
そして、その結果は記号表にリンクされる。上記実施形態において、ｂにインデックスを符号化したように、記号表へのエントリが根から葉への経路に記憶される場合、リンクがエントリ{/a/b}に帰り、または、記号表へのエントリがタグ名のみの構成である場合、リンクが{b}のみに帰る。
【０１１４】
更新は、パターン関数と差分符号化リストと拡張アレイとを有するインデックスのあらゆる部分で実行することができる。更新が生じるにつれて、１ブロック当たりのトリプレットの数が一定である必要はない。
【０１１５】
厳密なスキーマについては、全くパターン関数を実行する必要がない。しかしながら、不規則な構造がノード間に挿入されている場合、パターン関数を２つの別個の関数に分割する必要がある場合もあるとともに、新たに更新されたノードを記憶するためにそれらの間に拡張アレイを挿入する必要がある場合もある。拡張アレイが閾値に達するとき、上記で説明したように、他のパイプラインを通す。更新後にスペースの使用を最小にするために、新しいパターン関数が隣接のパターン関数と同一であるとき、併合処理が起こる。
【０１１６】
下記は、図１２に示されたＸＭＬ文書に基づきＳＩＳを生成する詳細な実施形態である。
【０１１７】
図１３に示すように生成された記号表は、図１２のＸＭＬ文書の全ての固有タグ名を有する。
【０１１８】
第１パイプライン５０は、 記号表の各エントリについて全ての位相符号化リストを生成する。すなわち、各ノードタイプについて、トリプレットがそれぞれ対応するノードのために生成される。図１３において、実インデックスについて生成される位置設定記号が図示されており、そこで、図１４に示すように、位相符号化リストが生成される。これらのトリプレットは、拡張アレイに記憶される。
【０１１９】
そして、図１４の位相符号化リストは、図１５の差分全位相符号化リストを生成するために第２パイプライン５２に渡される。差分値は、上記で説明したように計算される。すなわち、差分値Δスタート、ΔエンドおよびΔ深さは、上記で説明したように計算される。
【０１２０】
本実施形態では、棒グラフが各固有タグ名の各差分値について計算される。すなわち、差分値の発生回数は、図１６に示すようにグラフで表される。図１５で灰色にされた値は、それらが前のエントリを持たないように、棒グラフの中に組み入れられない。そこで、棒グラフのそれぞれの形は、図１７に示された一つの棒グラフのタイプに分類される。図１８は、図１６に示されたそれぞれの棒グラフの分類を示している。また、図１７は、それぞれの棒グラフを分類するための固定ビット符号化値を示している。これらは、使用された変換方法の表示として記号表の中に棒グラフタイプを記憶するために使用される。
【０１２１】
実施形態として、図１９，２０，２１は、どのように、ノードタイプＡの差分値が最適差分符号化を使用して記憶されるか、を示している。図１９（ａ）は、Δスタートについて記録した値を示している。棒グラフのカテゴリは、１００（降下）として記録されている。本実施形態では最小のΔスタート値が１４であったことが分かっているので、棒グラフの全ての値を１４だけシフトすることができるとともに、数字１４がシフト値として記録される。第１の値が棒グラフに含まれていないので（図１５で灰色にされている）、この値９は、また第１の値として記憶される。そして、残っている１２のトリプレットについて（すなわち、第１を除く全てのトリプレット）、Δスタート値がリストアップされる。図１９（ｂ）は、図１９（ａ）の後に残っている値が整列された状態を示しており、すなわち、残っている値のそれぞれはシフト値１４だけ引き算されている。図１９（ｃ）は、図１９（ｂ）の変数ビット符号化バージョンを示している。
【０１２２】
ＡについてのΔエンドおよびΔ深さの値の差分値は全て同一の値であるので、この場合は、棒グラフ符号化よりむしろパターン関数がより適当である。図２１はＡのΔエンドについて示しており、カテゴリが001（パターン関数）であるとともに、変数ビット符号化における増分値は１である（それはゼロに等しい）。図２２はＡのΔ深さを示しており、すなわち、カテゴリが再び００１であるとともに、変数ビット符号化における増分値は０である。
【０１２３】
そして、この情報は、図２１に示す表を出力するために、図１３に示されたオリジナルの記号表の中に挿入される。スタートＡについてのエントリは「１００」で始まる。この「１００」は、形が下降している棒グラフ変換機能が使用されたことを示す。エンドＡおよび深さＡについてのエントリは「００１」で始まる。この「００１」は、パターン関数変換が使用されたことを示している。
【０１２４】
更なる実施形態として、図２３は、どのように、ノードタイプｂのΔエンド値が最適差分符号化を使用して記憶されるか、を示している。図２３（ａ）は、Δエンドについて記録された値を示している。棒グラフのカテゴリは、１１０（通常）として記録されている。本実施形態では最小Δスタート値が０であったことを知っているので、シフト値も０である。第１の値が棒グラフの中に含まれていないので（図１５で灰色にされている）、この値１５も第１の値として記憶される。そこで、残っている１２のトリプレット（すなわち、第１を除く全ての組）について、Δスタート値がリストアップされる。図２３（ｂ）は、図２３（ａ）の後に残っている値が整列された状態を示しているが、ここではシフト値が０なので、図２３（ａ）および（ｂ）における残っている値は同一状態のままである。図２３（ｃ）は、図２３（ｂ）の変数ビット符号化バージョンを示している。
【０１２５】
同様に、図２４においてノードタイプＢについてのΔスタート値が示されているとともに、タグ名についてのスタートが示されている。
【０１２６】
同様に、値の残りについての記号表が図２５に示されている。これは、図１２に示された文書についてのインデックスを表している。カッコで特定された値は、ノーマル整数として記憶される。
【０１２７】
特定の実施形態で示される本発明について、広く説明される本発明の趣旨および範囲から逸脱することなく、多くの変形および／または修正が可能であることは当業者により理解される。したがって、本実施形態は、あらゆる点で実例であるとともに制限的なものではないことが考慮されるべきである。
【図面の簡単な説明】
【０１２８】
【図１】ＸＭＬ文書抜粋の階層表現を示している（従来技術）。
【図２】本発明を使用できるコンピュータシステムの構成図を示している。
【図３】位相記憶レイヤの図式的外観を示している。
【図４】更なるＸＭＬ文書抜粋の階層表現を示している。
【図５】図４における抜粋の平衡カッコ符号化を示している。
【図６】ポインタに基づいた方法と平衡カッコ方法とを使用したときの記憶空間の相違を示している。
【図７】集積簡素（Integrated Succinct：ISX）システムによるＸＭＬ文書を記憶する方法を示すフローチャートである。
【図８】本発明に係るインデックスを構成する方法を示すフローチャートである。
【図９】全てのｂノードの位相符号化リストに基づいた差分値を示す棒グラフである。
【図１０】全てのｂノードの位相符号化リストに基づいた差分値を示す棒グラフである。
【図１１】全てのｂノードの位相符号化リストに基づいた差分値を示す棒グラフである。
【図１２】本発明に係るＸＭＬ文書の簡素インデックスを示している。
【図１３】本発明に係る図１２に示すＸＭＬ文書の簡素インデックスの作成方法を示している。
【図１４】本発明に係る図１２に示すＸＭＬ文書の簡素インデックスの作成方法を示している。
【図１５】本発明に係る図１２に示すＸＭＬ文書の簡素インデックスの作成方法を示している。
【図１６Ａ】本発明に係る図１２に示すＸＭＬ文書の簡素インデックスの作成方法を示している。
【図１６Ｂ】本発明に係る図１２に示すＸＭＬ文書の簡素インデックスの作成方法を示している。
【図１７】本発明に係る図１２に示すＸＭＬ文書の簡素インデックスの作成方法を示している。
【図１８】本発明に係る図１２に示すＸＭＬ文書の簡素インデックスの作成方法を示している。
【図１９】本発明に係る図１２に示すＸＭＬ文書の簡素インデックスの作成方法を示している。
【図２０】本発明に係る図１２に示すＸＭＬ文書の簡素インデックスの作成方法を示している。
【図２１】本発明に係る図１２に示すＸＭＬ文書の簡素インデックスの作成方法を示している。
【図２２】本発明に係る図１２に示すＸＭＬ文書の簡素インデックスの作成方法を示している。
【図２３】本発明に係る図１２に示すＸＭＬ文書の簡素インデックスの作成方法を示している。
【図２４】本発明に係る図１２に示すＸＭＬ文書の簡素インデックスの作成方法を示している。
【図２５】本発明に係る図１２に示すＸＭＬ文書の簡素インデックスの作成方法を示している。
【符号の説明】
【０１２９】
６ デスクトップ・クライアント
８ ＰＤＡ／モバイル
１０ アプリケーション・ログイン
１２ 簡素インデックス
１４ インターネット
１６ 照会エンジン
１８ インデクサ
２０ ＸＭＬ文書
２２ サードパーティＤＢＭＳ
２４ 簡素エンコーダ／デコーダ
２６ 簡素ＤＢＭＳ
２８ 簡素アクセサ
【技術分野】
【０００１】
本発明は、簡素なデータおよびインデックス構造が理論的な最適条件に近づくように記憶容量サイズの制限条件を設定している間に、いかなるデータについても更新および検索動作の効率を最大にすることを目的としている。より詳細には、本発明は、簡素インデックス構造、簡素インデックス構造を使用する方法、簡素インデックス構造を作成する方法、簡素インデックスを作成する方法を実行するコンピュータソフトウェアアプリケーション、簡潔インデックスを作成および使用するためのコンピュータシステムに関するものである。
【０００２】
本願は、２００５年１２月６日に出願されたオーストラリア仮特許出願第２００５９０６８４６号に基づく優先権を主張し、その内容が引用によってここに組み込まれている。
【背景技術】
【０００３】
拡張マーク付け言語（ＸＭＬ）データと従来の関係データとの間の主な相違点は、関係データが二次元テーブルを使用して組織化されている一方、ＸＭＬデータは階層構造を持つツリーで構成されている。
【０００４】
例えば、ＸＭＬの短片が以下の数１のように与えられる。
【０００５】
【数１】
【０００６】
これは図１に示されているような階層的ツリーで表すことができる。
【０００７】
ＸＭＬ照会を効率的に処理するために、いくつかのツリー探査方法が存在するが、セットベース問い合わせ処理（従来の関係データベース）がさらに好ましい。例えば、大きなＸＭＬ文書で照会処理をするとき、探査に基づいた方法を使用して実行するために、照会処理が困難になるとともに実行時間が長くなる。
【０００８】
関係データベース管理システムでは、セットベースの処理の中に中間結果を返すデータベース・インデックスを作成および使用することによって照会性能を高めることができる。しかしながら、関係データベースに存在しないＸＭＬデータにおけるセットベース問い合わせ処理には欠点がある。これらの欠点は、あらゆるノードを照会するときに、２つの任意のＸＭＬノードの位相関係を問い合わせる必要性があることで生ずる。
【０００９】
ＸＭＬ照会は、複数のパス表現で構成することもできる。パス表現は、結果ノードが満たす必要がある位相関係を有することとしてもよい。例えば、パス表現 /a[b]/c は、ノードラベルとしてｃがある全てのノードを求めるとともに、ラベルａがある親ノードとラベルｂがある兄弟ノードとを持つ全てのノードを求める。いかなる種類の先祖／子孫についての照会にも効率的に答えるためには、構造的接続動作が必要である。構造的接続動作は、以下の技術として名称がある。潜在的派生ノードリストとともに潜在的先祖ノードリストが与えられれば、前記リストのノード間の先祖−子孫関係が決定される。
【発明の開示】
【発明が解決しようとする課題】
【００１０】
インデックスは、特定ラベルの条件を満たす１セットのノードを取得するためにたびたび提供される。位相関係を判断するために必要なナンバリング構造を有するインデックスは、作成およびメンテナンスに高いコストがかかる。最も一般的なナンバリング構造は、スタート−エンド−深さのトリプレット、前順−後順−深さのトリプレット、またはデューイ符号化を使用する。ｎノードとともにＸＭＬ文書が与えられれば、トリプレットの中の各ナンバを表すために少なくとも log n ビットを必要とする。インデックスが文書サイズに比例しているノードセットを返す場合、そのようなセットを表すためだけに少なくとも O(n log n) ビットが必要となる。全体の位相を簡素に表すためには 2n + o(n) ビットのみが必要となる、ことが知られている。したがって、そのようなインデックス（最も一般的なナンバリング・スキーマによる）は、オリジナル文書自体よりも実質的に多くのスペースを使用するので、インデックスの有用性を顕著に制限する。
【課題を解決するための手段】
【００１１】
第１の態様によれば、本発明は、階層構造で表されたインデックスデータのための簡素インデックス構造を提供し、前記インデックス構造は、キーとして全ての異なった根から葉への経路の記号表、またはキーとして固有要素のタグ名の記号表を有し、前記記号表におけるキーについてのエントリは、前記キーに関連したノードの変換された位相情報とともに、前記位相情報で使用される変換方法の表示情報を持っており、使用される前記変換方法は、前記キーに関連付けられたノード間の位相関係に基づいている。
【００１２】
前記位相情報は、各ノードについてトリプレット番号づけ構造を有することとしてもよい。前記トリプレット番号づけ構造は、スタート・エンド・深さトリプレット番号づけ構造または前順・後順・深さトリプレット番号づけ構造であることとしてもよい。前記トリプレットは、ツリー探査オーダの中にあることとしてもよい。
【００１３】
前記階層構造は、エクステンシブルマークアップ言語（ＸＭＬ）であることとしてもよい。
【００１４】
前記変換方法は、前記リストの各トリプレットにおける各値を差分符号化するように、前記位相情報を差分符号化するステップを有することとしてもよい。前記トリプレットの第１の差分符号化値は、連続したトリプレットのスタート位置の差であることとしてもよい。各ノードのスタート位置とエンド位置との間の差が与えられれば、前記トリプレットの第２の差分符号化値は、連続したトリプレット間のそれらの値の差であることとしてもよい。第３の差分符号化値は、連続したトリプレットの深さについての差であることとしてもよい。
【００１５】
前記変換方法の情報は、シフトされたキーに関連した各ノードについてのトリプレットの前記第１、第２または第３の値のそれぞれであるシフト値を有することとしてもよい。
【００１６】
前記変換方法の情報は、全てのノードの前記トリプレットの前記第１、第２または第３の値のそれぞれをグラフ表示する棒グラフの形状の表示情報を有することとしてもよい。
【００１７】
前記変換方法の情報は、前記キーに関連した全てのノードの前記トリプレットの前記第１、第２または第３の値を出力するパターン関数を有していることとしてもよい。
【００１８】
前記変換方法の情報は、前記変換された位相情報が前記位相情報と同一であることを示すものとしてもよい。
【００１９】
キーについてのエントリは、前記位相情報の変換に使用された複数の方法を保持していることとしてもよい。前記キーに関連付けられた全てのノードの前記トリプレットの前記第１、第２または第３の値のそれぞれについて方法があることとしてもよい。
【００２０】
前記変換された位相情報は、更新圧縮形式で保存されている。
【００２１】
前記位相情報は、簡素データ構造から取得されることとしてもよい。前記簡素データは、平衡カッコ表示を使用しているノードの入れ子を表す位相レイヤ（層０）を有することとしてもよい。すなわち、ツリーの前順探査は、開タグが遭遇されたとき、１ビット（開カッコ）出力し、閉タグが遭遇されたとき、反対ビット（閉カッコ）を出力する。
【００２２】
第２の態様によれば、本発明は、簡素インデックス構造を使用する方法であって、
記号表において所要キーを位置付けるステップと、
前記キーに関連したノードの前記位相情報の変換に使用された変換方法に基づき、前記キーに関連した全てのノードの位相情報を検索するために前記変換された位相情報を再変換するステップと、を有する簡素インデックス構造を使用する方法を提供する。
【００２３】
前記簡素インデックス構造は、構造的結合の照会を処理するために使用されることとしてもよい。
【００２４】
第３の態様によれば、本発明は、階層構造で表されたデータについて簡素インデックスを作成する方法を提供するものであって、前記方法は、
１
ツリー探査命令におけるノードの位相符号化リストを生成するためにデータを解析するステップと、 異なった根から葉への経路に関連したノードまたは固有要素のタグ名に関連したノードについて、前記ノード間の位相関係を評価するステップと、
２
前記評価に基づき、前記異なった根から葉への経路または固有タグ名に関連したノードの前記位相符号化リストを変換するステップと、
３
キーとして前記異なった根から葉への経路または固有タグ名を持っている記号表においてエントリを作成するステップと、を有し、
前記エントリは、使用された前記変換方法の表示情報と共に前記キーに関連した変換された位相情報に含まれる。
【００２５】
前記解析するステップは、拡張アレイに記憶された位相符号化リストを生成するために前記ツリーを探査するステップを有することとしてもよい。前記位相符号化リストは、各ノードについてトリプレット番号づけ構造を有していることとしてもよい。前記トリプレット番号づけ構造は、スタート・エンド・深さトリプレット番号づけ構造であることとしてもよい。
【００２６】
前記拡張アレイは、一旦、所定のブロックサイズを持ち、前記方法は、位相符号化リストを生成し続けるとともに、新たなブロックの拡張アレイに記憶するステップをさらに有することとしてもよい。
【００２７】
位相符号化リストを生成した後に、上記で説明したように前記位相符号化リストを別個に再符号化する。前記方法は、クラスタ化アルゴリズムを実行するステップをさらに有することとしてもよく、複数のクラスタが特定される場合、前記ブロックが各クラスタのより小さいブロックに分割されることとしてもよい。
【００２８】
前記変換方法の情報は、シフトされている値、グラフ化された値、または上記で説明されたパターン関数を生成する情報を有することとしてもよい。
【００２９】
第４の態様によれば、本発明は、階層構造で表されたデータについて簡素インデックスを作成する方法を実行するコンピュータソフトウェアアプリケーションを提供する。
【００３０】
第５の態様によれば、本発明は、階層構造で表されたデータについて簡潔インデックスを作成するためのコンピュータシステムを提供するものであって、前記コンピュータシステムは、
異なった根から葉への経路に関連したノードまたは固有要素のタグ名に関連したノードについて、前記ノードの間の位相関係を評価するために、ツリー探査命令におけるノードの位相符号化リストを生成するようにデータを解析する処理手段と、
前記評価に基づき、前記異なった根から葉への経路または固有タグ名に関連したノードの前記位相符号化リストを変換する処理手段と、
キーとして前記異なった根から葉への経路または固有タグ名を持つエントリとともにインデックスを記憶する記憶手段と、を有し、
前記エントリは、使用された前記変換方法の情報と共に前記キーに関連した変換された位相情報に含まれる。
【００３１】
前記記憶手段は、コンピュータ読取り可能記憶媒体であるとともに、上記で説明された階層構造で表されたデータについて簡潔インデックスを作成する方法の実行動作が可能なコンピュータソフトウェアアプリケーションを記憶することとしてもよい。前記コンピュータシステムは、ＰＤＡ，携帯電話またはラップトップなどの携帯型コンピュータである。
【００３２】
第６の態様によれば、本発明は、上記で説明された階層構造で表されたデータについて簡素インデックスを使用するためのコンピュータシステムを提供するものであって、前記コンピュータシステムは、
前記簡素インデックスを記憶する記憶手段と、
前記キーに関連したノードの前記位相情報の変換に使用された変換方法に基づき、前記キーに関連した全てのノードの位相情報を検索するために前記変換された位相情報を再変換するように、前記記号表において所要キーを位置付ける処理手段と、を有する。
【００３３】
前記記憶手段は、コンピュータ読取り可能記憶媒体であるとともに、上記で説明された階層構造で表されたデータについて簡素インデックスを使用する方法を実行するための動作が可能なコンピュータソフトウェアアプリケーションを記憶することとしてもよい。
【００３４】
前記コンピュータシステムは、インターネットなどを介して、遠隔装置からデータ処理要求信号を受信する通信手段をさらに有することとしてもよい。
【００３５】
前記コンピュータシステムまたは遠隔装置は、ＰＤＡ，携帯電話またはラップトップなどの携帯型コンピュータであることとしてもよい。
【００３６】
前記インデックスは、データの位相構造を取得する方法としてスペース効率が良いとともに、ＸＭＬデータを効率的に実行する構造的結合を可能にすることができる。ＸＭＬデータを処理するとき、メモリ使用量の大部分が中間結果セットを表すことに費やされる（最終結果セットと同様に）。メモリスペースが不足しているとき、付随的なディスク入出力動作のために照会性能がかなり低下する。本発明のインデックスを使用すれば、中間セットは、簡素な形で表されるとともに、構造的結合が効率的動作を実行するように使用されることができる。
【発明を実施するための最良の形態】
【００３７】
ここで、本発明の実施形態は、添付図面を参照して説明される。
【００３８】
図３は、本発明の実施形態を実現できるコンピュータシステム４を示すブロック図である。デスクトップコンピュータ６とＰＤＡまたはモバイル８とは、共に、本発明に使用できるコンピュータの実施形態である。両方の装置は、一般に本技術分野で理解されている所定の処理手段、記憶手段、通信手段、入力手段および出力手段を具備している。
【００３９】
本発明を適用するために、装置６および８の両方は、本発明の簡素インデックスにアクセスするためにソフトウェアアプリケーション１０を使用する必要がある。本実施形態において、装置６および８は、それぞれの記憶手段上でコンピュータ６および８にローカルに記憶されたインデックス１２を持つことができる。しかしながら、ＰＤＡ８のような装置は、より小さい処理手段および記憶容量を持っているとしてもよく、簡素インデックス１２にアクセスするためにインターネット１４を使用することとしてもよい。すなわち、全てのインデックス１２と関連処理１６、インデックス１２とソフトウェア１８は、ＰＤＡ８から分離されて記憶されている。
【００４０】
前記ソフトウェア（または遠隔ソフトウェアへのログイン）１０は、照会エンジン１６の所定処理を（ローカルまたはリモートのいずれかで）実行するようにプロセッサを動作させることができる。照会エンジン１６は、装置８および１０に入力された問い合わせを解決するために簡素インデックス１２を使用する。簡素インデックス１２は、（ローカルまたはリモートのいずれかの）メモリに記憶されているとともに、以下に詳細に説明するように作成および更新される。本発明の簡素インデックス１２は、インデクサソフトウェアコンポーネント１８に関して作成されている。コンポーネント１８は、ＸＭＬ文書２０およびサードパーティ・データベース２２などを、入力して様々な情報に直接索引を付ける。あるいはまた、ＸＭＬ文書２０およびサードパーティ・データベース２２は、簡素な形式にデータ変換する簡素エンコーダ２４を使用して符号化されることができ、その後に記憶される２６。また、インデクサ１８は、簡素インデックス１２を形成するための入力としてこれを取得することができる。さらなるソフトウェアとして、簡素ＤＢＭＳを解釈できる簡素アクセサ２８を有する。簡素アクセサ２８は、装置６または８への照会の結果を提供するためのものであり、または簡素処理時にプロセッサ１６によって使用される。
【００４１】
照会は、簡素データベース２６に保存された記録を返信することとしてもよい。これらの結果をコンピュータ８または１０に返信するために、さらなるコンピュータアプリケーション２８が簡素データベース２６にアクセスして解釈するように照会エンジン１６によって使用されることとしてもよい。あるいはまた、コンピュータ８または１０は、直接に簡素ＤＢＭＳ２６にアクセスして解釈するために簡素アクセスソフトウェア２８に使用されることとしてもよい。
【００４２】
ここで、集積簡素（ISX）システムの簡素記憶レイヤ２６について説明する。ＩＳＸは三層、すなわち、位相レイヤと内部ノードレイヤとリーフノードレイヤとを有している。これらのレイヤの概要が図３に示されている。
【００４３】
位相レイヤは、ＸＭＬ文書のツリー構造を記憶するとともに、高速ナビゲーションアクセスと構造的な結合と更新とを容易にする。内部ノードレイヤは、高速な照会のために、ＸＭＬ要素と、属性と、テストデータのシグネチャとを記憶する。最後に、リーフノードレイヤは、文書のテキストデータを記憶する。テキストデータは、様々な一般的な圧縮法によって圧縮でき、位相レイヤを使用して参照できる。
【００４４】
本実施形態の説明では位相レイヤに集中する。従来の方法と異なり、位相レイヤのこの表示では、ポインタを利用しない。それは、効率的なノードナビゲーションおよび更新を支援する平衡カッコ符号化に基づいている。
【００４５】
層０に使用される平衡カッコ符号化は、あらゆるＸＭＬ文書における要素ノードの入れ子もたらすとともに、前記ツリーの前順探査によって構成することができる。開カッコは開タグが探査時に遭遇されたときに出力され、閉カッコは閉タグが探査時に遭遇されたときに出力される。
【００４６】
例えば、図４に示すＸＭＬ文書の抜粋を挙げると、層０の平衡カッコ符号化は図５に示すように記憶される。カッコの下部の矢印は、カッコの組を示している。明瞭化のため、ビットごとの動作の詳細およびオブジェクトのような１ビット（カッコ）の処理は省略する。
【００４７】
余分は、前記位相の与えられたセクションで生じている開カッコおよび閉カッコの数の間での差分である。例えば、図５において、「dblp」の開カッコと「＠mdate」の閉カッコとの間の余分は２である。テキストノード「2003」の閉カッコと「booktitle」の開カッコとの間の余分は、−１である。ＸＭＬ文書ツリーにおけるノードＸの深さは、Ｘの開カッコと前記文書の始まりとの間の余分を検出することによって計算することができる。例えば、図５において、「author」における開カッコの深さは３である。
【００４８】
この符号化方法には、いくつかの利点がある。第１に、位相的性質（深さ、スタート／エンド位置、前順番号／後順番号）、位相的関係（原型／派生物、文書順番）、文書探査、ＤＯＭネビゲーションおよびＸパス軸は、上記のカッコ表示を使用して全て決定することができる。第２に、小セットの物理的な演算子を持つだけでデータベースが簡素化する。
【００４９】
2n ＝ O(n) から望ましくない下記数式２へ、スペース用途を増加させるので、リンクするためのポインタに基づいたあらゆる手法を回避する。これは図６に図示されている。
【００５０】
【数２】
【００５１】
図７のフローチャートと下記数式３のＸＭＬ文書抜粋とを参照して、ＩＳＸシステムのさらなる実施形態がここで説明される。
【００５２】
【数３】
【００５３】
実際には、ＸＭＬ文書は、ここで説明された抜粋よりもかなり大きい。平衡カッコを使用して、この文書は下記の数式４のように表すことができる。
【００５４】
【数４】
【００５５】
そこで、平衡カッコを使用するＸＭＬ文書の抜粋の位相は、下記のように表される（ステップ３０）。
（ （（（））） （（（））） （（（））） ）
開カッコはバイナリ・ビット０によってメモリ内で表されるとともに、閉カッコはバイナリ・ビット１としてメモリ内で表される。これに続いて、階層構造が下記数式のようにメモリ内に記憶される（ステップ３２）。
00001110001110001111
【００５６】
そこで、すべての「０」が新しいノードのスタートを示している。すべての「０１」の組合せがリープノードなどの変換を示している。
【００５７】
このシステムを使用すると、あらゆる文書のための記憶空間が２ｎビットになる（ここで、ｎはノードの数である）。
【００５８】
もちろん、ステップ３０および３２は１つの単一ステップとして実行することができる。さらに、「１」ビットが開カッコを示すとともに、「０」ビットが閉カッコを示すように、ビットの使用は簡単に交換できる。
【００５９】
以下の抜粋（上記から繰り返される）は、ここではノードのラベルおよび各ビットの位置番号とともに垂直に並べられている。
【００６０】
【数５】
【００６１】
ここで、ノード＜ａ＞が位置「０」にあるとともに、第３ノード＜ｂ＞が位置１３にあることが分かる。
【００６２】
ここで、位相のビット表示を使用することでブロックに照会を実行することができる。例えば、照会は「位置１３のノードの親の位置はなにか」としてもよい。
【００６３】
本実施形態ではカッコが組みの形式であることを知っているので、「１」よりも２つ多く「０」が見つかるまで後向きにブロックを走査した場合、親の位置を見出すことができる。この場合の親の位置は位置「０」である。
【００６４】
文書のビット表示は、初めに、特定サイズのブロックに分割される（ステップ３４）。例えば、上記説明の抜粋は、下記の数式６のように２つのブロックに分割される。
【００６５】
【数６】
【００６６】
各ブロックは、層１を有する組(tuples)を生成するために要約される（ステップ３６）。各ブロックについて下記の情報が計算される。
・ ブロックにおける「０」の数。
・ ブロックにおける「１」の数。
・ 前方最大差分、すなわち、左から右にブロックを走査している間のランニング合計が計算される。「０」のランニング合計値から始まって、「０」ビットが遭遇するたびにランニング合計が１だけ増加され、「１」ビットが遭遇するたびにランニング合計が１だけ減少される。ブロックにおけるあらゆる位置に及ぶ前記ランニング合計での最大値が前方最大差分になる。
・ 前方最小差分、すなわち、ランニング合計は上記のように計算される。ブロックにおけるあらゆる位置に及び前記ランニング合計での最小値が前方最小差分になる。
・ 後方最大差分、すなわち、ランニング合計は前方最大差分を参照して上記のように計算されるが、その代わりにブロックは右から左に走査される。
・ 後方最小差分、すなわち、ランニング合計は前方最小差分を参照して上記のように計算されるが、その代わりにブロックは右から左に走査される。
・ ノードの数、すなわち、「０１」の組合せの回数がブロックで検出される。最終ビットについて、以下のブロックのビットが検査されることとしてもよい（あるいはまた、選択された方法が一貫して提供されて、前ブロックの最終ビットが検査されることとしてもよい）。
【００６７】
そこで、ブロック「００００１１１０００」について、概要情報は（７、３、４、１、４、０、２）として現れる。
【００６８】
そして、ブロック「１１１０００１１１１」について、概要情報は（３、７、０ ４の−１−４、１）として現れる。
【００６９】
この概要情報を使用して、層１の組の上記２つの実施形態に基づき、ＤＯＭ照会をここで説明することができる。例えば、「位置１３でのノードの親はなにか」のように照会を取る。
【００７０】
本実施形態では、位置１３でのビットから開始してブロックの発端まで後方に走査する。位置１３からブロックの発端まで、本実施形態では以下のビッット「１１１０」を持つ。「０」の数は１であり、そして「１」の数は３である。「１」の数から「０」の数を引くと「−２」が求まる。本実施形態ではここで、前ブロックから後方最大差である「４」を得るとともに、数「２」を得るために「−２」を加える。これから、本実施形態では、一致しているビットが前ブロックのなかにあることを、ここで知得する。
【００７１】
文書が大きいとき、層１の要約の組を生成するプロセスを繰り返すことができ（ステップ３８）、このとき、層２の生成が層１のデータに基づいて行われる。全ての場合、通常、２層で十分である。一方、本実施形態では、層１の組をブロックに分割するとともに、層２を生成するために更なる概要組を生成する。
【００７２】
ＸＭＬ文書の位相情報を表すこの方法は、理論的に最小限の恒常的要因のなかで、空間効率が良い所定スペースを持つ。常数ｅについて、１≦ｅ≦２、ｎノードの文書であるとき、概要情報（ｏ（ｅｎ））に加えてＸＭＬ文書（２ｎ）の位相を表すために、本実施形態では「２ｅｎ＋ｏ（ｅｎ）」ビットを必要とする。ノード挿入は平均して一定時間で処理することができるが、最悪の場合「Ｏ（ｌｇ２ｎ）」時間であるとともに、全てのノードナビゲーション動作は下記数式７の時間を要するが平均して一定時間である。
【００７３】
【数７】
【００７４】
また、位相情報を表すこの方法は、データ処理のための全ての所定初期動作について低いアクセスおよび更新コストを維持する。また、それは、ほぼ一定時間でのナビゲーション動作を支援する。
【００７５】
ＸＭＬ文書を表す「０」および「１」の第１点検を支援するために、簡素インデックス構造（ＳＩＳ）１２を構成することができる。このインデックスは、より効率的に文書を照会する方法を提供する。
【００７６】
ＳＩＳは、記号表で作られる。記号表は、全ての異なった根から葉への経路のエントリまたは異なるタグ名を持っている。例えば、図１においてＸＭＬ文書抽出のために、異なった根から葉への経路は｛/a, /a/b, /a/b/c｝であるとともに、異なるタグ名は
｛a,b,c｝である。
【００７７】
記号表の各エントリは、何らかの統計情報の他に実インデックス（生インデックスとして知られている）もまた保持し、その経路またはタグ名を構成するタグの全てのインスタンスを容易に位置付ける。前記統計情報は、生インデックスの変換を規定する。それは、タグ名の人気と照会および更新の頻度とに関する情報を有している。
【００７８】
生インデックスの変換は、スペース用法と、照会性能と、更新コストとについて良い妥協案を提供する。前記変換法は、その時々で与えられたＸＭＬ文書に最も合う方法にしたがって複数の生インデックスに作用する。
【００７９】
生インデックスは、下記のデータ構造、ブロック、ノードセットサイズへの依存、照会および更新の頻度、の一つ以上で構成されている。
・ 全位相符号化リスト：それは、元の形のままでトリプレット（スタート、エンド、深さ）のリストで構成される。各トリプレットはノードの位相情報を符号化する。前記リストは、如何なる圧縮フォーマットも使用せずに記憶される。このデータ構造は、インデックスが付けられるＸＭＬ文書の中で生じる更新のところに現れる。また、それは、、生インデックスのエンドに現れ、新たに生成されたトリプレットはフルサイズブロックを生成しない。
・ ノード識別子リスト：ノード識別子リストは、全位相符号化リストの他の形であり、層（例えば、層０，層１および層２）から間接的に派生したトリプレット（スタート、エンド、深さ）の中の３つの値とともに、永続的ノード識別子を使用している。ノード識別子リストは、スペースが主要な関心事項であるときに使用され、少なくとも前記値を引き出す性能オーバーヘッドがトリプレットをロードすることよりもかなり良い。
・ ビットアレイフラグ：ビットアレイフラグはノード識別子リストの他の形であり、ここでノード識別子の総数はＸＭＬ文書におけるノードの総数の一定差分の範囲内にある。
・ 部分位相符号化リスト：データ構造は明示のノード識別子を持っておらず、またトリプレットの中のスタート値は（非永続的）識別子として機能することができる。ここで、本実施形態では、トリプレットの代わりにスタート値のみを記憶する。
・ 差分、全位相符号化リスト：このデータ構造は、概要を生成するために第２パイプラインへ全位相符号化リストの完全ブロックを送信することの結果である。前記概要は３つの棒グラフから構成され、各棒グラフは連続したトリプレットのスタート、エンドおよび深さの間の差分値間の関係を表す。前記概要は、固定サイズの値で可変サイズにトリプレットを符号化するための符号化方法を特定する。符号化トリプレットの結果のリストは、概要に隣接して記憶される。
・ 差分ノード識別子リスト：差分ノード識別子リストは、前記「差分、全位相符号化リスト」と同様の方法でノード識別子の差分値の棒グラフを記憶する。
・ 差分部分位相符号化リスト：差分部分位相符号化リストは、前記「差分、全位相符号化リスト」と同様の方法で部分位相符号化リストを記憶する。
・ パターン記述子機能：文書の概要が正確であるとともにトリプレットの差分値が一定であるとき、全位相符号化リストの全体は、破棄されることができるとともに、前記概要およびそれらの前の値にそれぞれ基づく次の「スタート、エンドおよび深さ」値を返す機能に置き換えられることができる。これらのパターン関数は、更新（例えば、新しいノードが前記リストに挿入される）による影響を受けない。
【００８０】
前記インデックスの解釈は、３つのパイプラインを一度に通してＸＭＬ文書を解析することで行われる。ここで、各パイプラインは、前のパイプラインの出力を入力する。第１パイプラインは、ＸＭＬ文書を探査するとともに、リストとして表されたＸＭＬ文書を位相符号化した単純セットを生成する。第２パイプラインは、位相符号化リストの最適差分符号化を決定する。最終的に、第３パイプラインは、前記差分符号化リストからパターン記述子を生成する。ここで本実施形態では、ノードを挙げて、データベースが一定時間で位相ナンバリングを検索できる、と仮定する。
【００８１】
図８のフローチャートを参照して、インデックスを構成する方法を説明する。
【００８２】
第１に、ＸＭＬ文書の簡素表示が探査されるとともに、単純位相符号化リストが生成される（ステップ５０）。
【００８３】
位相符号化リストはトリプレットのリストで構成され、ここで、各トリプレットは単一ノードの位相情報を表す。すなわち、ＸＭＬ文書における各ノードについて、符号化ナンバの３つのタイプがトリプレットを作成するために計算される。それぞれのトリプレットの符号化ナンバは以下を表す。
「０」（開カッコ）のビット位置はノードのスタート
「１」（閉カッコ）のビット位置はノードのエンド
深さ、すなわち、ツリーにおいてどれだけ下側にノードがあるか、またはツリーにおけるノードのレベルがどれだけか。
これらのトリプレットは、ＸＭＬ文書の位相構造を表現するそれらの間と間接的関係がある。「０」のビット位置は各ノードの事前予約ナンバと同一であり、その結果、深さとともにツリーを再構成することが可能となる。しかしながら、「１」のビット位置がなければ、２つのノード間の先祖−子孫関係を応答するのに時間がかかりすぎる。
【００８４】
図１に示されたＸＭＬ文書に基づく照会は以下の数８のようになる。
//b//c[text() = "e"]
すなわち、ノードｂは子孫ｃとともにテキスト「ｅ」を持っているか。本実施形態ではＳＩＳを使用することで応答を得ることができる。
【００８５】
インデックスは、全てのｂと、全てのｃと、全ての「ｅ」とを返す。そこで、本実施形態では、正しい親／子孫方向で関連していることを確認するために、返されたノード間の構造関係を判断する。これをするために、本実施形態では各ノードについて計算されたトリプレットを使用する。
【００８６】
例えば、
【００８７】
【数８】
【００８８】
前記構造関係は、この情報から判断することができる。ここで、本実施形態では、ノードａの第１「０」ビットが「０」のスタートビット位置にあるとともに、ノードａの最後の「１」ビットが「１９」の位置にある、ことがわかる。また、ここで、本実施形態では、第２ノードｂの第１「０」ビットが「７」のスタートビット位置にあるとともに、第２ノードｂの最後の「１」ビットが「１２」の位置にある、ことがわかる。
【００８９】
そこで、ノードｂがノードａの子孫である場合、ノードａのスタート位置がノードｂよりも小さくなるべきである（０＜７）。さらに、ノードｂのエンド位置は、ノードａのエンド位置よりも小さくなるべきである（１２＜１９）。
【００９０】
下記の数式９は、上記で説明したトリプレットに基づき図１から抽出したＸＭＬ文書についての位相符号化リストである。
【００９１】
【数９】
【００９２】
例えば、上記
//b//c[text() = "f" ]
のように同一の照会に応答するために、本実施形態では上記３つの位相符号化リストと、ｃリスト対「ｅ」リストの第１マッチとを検索して、「ｅ」の中のあらゆるトリプレットの親であるｃリストの中に全てのトリプレットを返す。トリプレットc2:(8,11,2)と、「ｅ」1:(9,10,3)とについて、
c2.start (8) < “ｅ”1.start (9) and c2.end (11) > “e”1.end (10) and
c2.depth (2) + 1 = “e”1.dpeth (3)
なので、c2 (8,11,2)
は、可能な応答のリストの中にある。
【００９３】
第２に、本実施形態では、ｂリストに対して新たに作成されたリストに一致するとともに、いかなるｂトリプレットの子供に属しないトリプレットをフィルタ出力する。
b2: (7,12,1)については、
b2.start (7) < c2.start (8) and b2.end (12) > c2.end (11) and
b2.depth (1) + 1 = c2.depth
のようになる。c2がテスト条件を満たすので、それが応答である。
【００９４】
前記リストにおけるノードの数が少ない場合のみ、または、ｎノード文書の全体に対する前記リストの割合が小さい場合のみ、例えば、インデックスにおいてO(lgn)ノードからO(n/lg2n)ノードにいたるまで、本実施形態では全位相符号化リストを維持する。位相符号化リストは、拡張アレイと呼ばれる特別なデータ構造で維持される。ノードセットは、それらの関連文書命令、すなわち、ノードセットにおけるそれらの各ノードの事前予約値にしたがって記憶されなければならないことに留意すべきである。
【００９５】
一旦、閾値に達すると、拡張アレイの一部はブロックを有するとみなされる。本実施形態では、第２パイプラインの中にそのブロックを有する拡張アレイを通すとともに、差分符号化を持つ新たな拡張アレイの構築を続行する（ステップ５２）。この手法の利点は、新たに挿入されたノードがその後の更新によってさらなる影響を受けることになりそうであると推定できることである。
【００９６】
第２パイプラインは、拡張アレイにおける１ノード当たりの各符号化数の間での値の差分を第１検査する動作をするとともに、差分符号化を使用して再符号化する。再符号化をしている間、差分値のおおまかな分布に伴う最小差分および最大差分の２つの値の軌跡を保持する。差分値のおおまかな分布に伴う最小差分と最大差分。本実施形態では、位相リストを符号化する前に、棒グラフとして後にスケーリングするために最大差分および最小差分の値を記憶する。
【００９７】
第１に、同一のサイズのブロックにトリプレットを分割する。すなわち、第１ブロックは以下の通りである。
( s1, e1, d1) ( s2, e2, d2) ... ( sb, eb, db )
そして、第２ブロックは以下の通りである。
(+1, eb+1, db+1) (sb+2, eb+2, db+2), . . (s2b, e2b, d2b)
【００９８】
そして、ブロックにおいて特定のノードタイプに関連する各トリプレットについて、以下に基づき３つの棒グラフを作成する。
連続したトリプレットのスタート位置の間の差分（Δスタートと呼ばれる）、すなわち、
s2-s1, s3-s2, s4-s3, ..., sb-sb-1
連続したトリプレットのエンド位置とスタート位置との間の差分の差分（Δエンドと呼ばれる）、すなわち、
(e2-s2)-(e1-s1), (e3-s3)-(e2-s2), ..., (eb-sb)-(eb-1-sb-1)
連続したトリプレットの深さの間の差分（Δ深さと呼ばれる）、すなわち、
d2-d1, d3-d2, d4-d3, ...,db-db-1
【００９９】
各棒グラフは、対応するΔの中の異なる値の全てで構成されている。それぞれの異なる値について、発生回数の軌跡を保持する。また、本実施形態では、それらの異なる値が生ずる範囲の軌跡を保持する。
【０１００】
そして、クラスタ化アルゴリズムが前記棒グラフに実行される。差分値の複数のクラスタが存在している場合、拡張アレイおよび３つの棒グラフをそれらのクラスタに分割するとともに、次のステップを別々に実行する。
【０１０１】
各クラスタについて、最小差分の値を記憶するとともに、オリジナルとして最小差分を使用して全ての差分値を再調整する。これは、全ての差分値をより少ないビットで符号化できることを意味している。
【０１０２】
また、各クラスタについて、本実施形態では、棒グラフの形を検査して、以下のカテゴリに分類する。
・ 慎重(Discreet)
慎重シナリオの下では、前記棒グラフはあらゆる範囲に渡ることができるが、その全ての値は差がｋの差分値の小セットに渡るだけである。ここで、ｋは、1g nより小さいかまたはほぼ同一である。本実施形態では、エントリｋの慎重テーブルを構築し、差分値を記憶する。慎重テーブルにインデックスを表現する1g kビットを持たせ、１つの値当たりオリジナル1g nビットではなく、全ての差分値について1g k < 1g 1g n ビットを使用してブロックを再符号化する。
・ 平坦
慎重とは異なり、このシナリオは適度により長い範囲 [j, k]で平坦カーブを持つ。ここで、k - j > 1g n である。本実施形態では、前記棒グラフを再調整し、オリジナルとしてjを扱うとともにk - jとしてkを扱う。慎重と同様であるが、テーブルの必要性はなく、１つの値当たり1g (k - j)ビットを使用しての差分値を再符号化することができる。k-jがnよりもかなり小さい値であることが証明でき、あらゆる正常数において、インデックスが付けられるノードの数がn/cである場合に等しい。
・ 下降
下降カーブについて、本実施形態では、第１に、平坦シナリオのように棒グラフを再調整し、次に値のアレイを取得して、それらの差分値を使用してそれらをあらゆるＲＬＥ（ランレングス符号化）方法で再符号化する。ここで、本実施形態では、マイクロ・コードと呼ばれる簡単な、しかし有効な方法を提示する。それぞれ再調整された差分値vは、２つの部分に符号化される。本実施形態では、第１に下記の数１２を単項に符号化し、二進数で下記の数１３の値が続く。
【０１０３】
【数１０】
【数１１】
【０１０４】
この場合、最も一般的に生ずる差分値は、ビットの最小値で符号化される。
・ 上昇
棒グラフのカーブの傾きがより大きな値に向かって傾いている場合、本実施形態では、また、μコードでそれを符号化するが、棒グラフを左から右へ反転させるとともに、上昇シナリオについて同一方法を使用する。
・ 通常
これは、カーブが正規分布で形成されているときである。本実施形態では、第１に、カーブのピークをオリジナルに再調整する。先ず、第１ビットが差分値のサインを示すようにして、次に、差分値の絶対値を取得し、そして残りのビットを再符号化するためにＲＬＥを使用する。
・ 高密度
慎重カテゴリと同様であるが、より大きい。これは、棒グラフがｋ差の差分値の小セットに下降するときであるが、ｋは1g nよりも大きい常数であり、それでも、ｋはnよりも小さい。
【０１０５】
それで、ノードタイプｂに関連した位相符号化リストは、
b (1,6,1) (7,12,1) (13,18,1)
となる。
【０１０６】
棒グラフは、以下のように計算される。スタートの差分についての値（Δスタート）は6 (7-1) および 6 (13-7)である。そして、これらの値の棒グラフは、図９に示すようにプロットされている。
【０１０７】
エンドの差分についての値（Δエンド）は、
0 ((6-1)-(12-7)) および 0 ((12-7)-(18- 13))である。そして、これらの値の棒グラフは、図１０に示すようにプロットされている。
【０１０８】
深さの差分（Δ深さ）については、その値が 0 (-1-1) および 0 (1-1)である。そして、これらの値の棒グラフは、図１１に示すようにプロットされている。
【０１０９】
そして、各棒グラフの分布が分析される。例えば、分布は上昇であるか、下降であるか、通常であるか。分布に依存して、あるオプションは、同一値へ全ての値をシフトするとともに、使用したシフト値を記憶することである。あるいはまた、本実施形態では、異なる形についてＲＬＥなどを符号化する差分変数ビットを使用することができ、またはＺＬ圧縮を使用して高密度にすることができる。
【０１１０】
各棒グラフについて、棒グラフタイプ（慎重、平坦、下降、上昇、通常）が記憶されている。本実施形態では、棒グラフのタイプを検査することで、照会中に前記リストの圧縮型を復号化し、圧縮型を復号化する方法を判断することができる。
【０１１１】
その結果、棒グラフのクラスタは第３パイプラインに渡される（ステップ５４）。ツリーパターンは、特定スキーマに結合するＸＭＬ文書について頻繁に繰り返される。これは、第３パイプラインにおいて更なるスペース効率を獲得するために利用できる。第３パイプラインは、特定パターンがクラスタの差分値の中に生じるか否か発見しようとする。そのようなパターンが存在している場合、全部のクラスタは、前記パターンに結合する値を出力するパターン関数によって置換される。その方法の一つとして、繰り返しパターンを位置付けるＺＬＭ圧縮技術がある。
【０１１２】
３つのパイプラインでの処理の後に、位相符号化のオリジナルリストは、パターン関数と差分符号化リストと位相符号化リストの拡張アレイとの混合リストになる。
【０１１３】
そして、その結果は記号表にリンクされる。上記実施形態において、ｂにインデックスを符号化したように、記号表へのエントリが根から葉への経路に記憶される場合、リンクがエントリ{/a/b}に帰り、または、記号表へのエントリがタグ名のみの構成である場合、リンクが{b}のみに帰る。
【０１１４】
更新は、パターン関数と差分符号化リストと拡張アレイとを有するインデックスのあらゆる部分で実行することができる。更新が生じるにつれて、１ブロック当たりのトリプレットの数が一定である必要はない。
【０１１５】
厳密なスキーマについては、全くパターン関数を実行する必要がない。しかしながら、不規則な構造がノード間に挿入されている場合、パターン関数を２つの別個の関数に分割する必要がある場合もあるとともに、新たに更新されたノードを記憶するためにそれらの間に拡張アレイを挿入する必要がある場合もある。拡張アレイが閾値に達するとき、上記で説明したように、他のパイプラインを通す。更新後にスペースの使用を最小にするために、新しいパターン関数が隣接のパターン関数と同一であるとき、併合処理が起こる。
【０１１６】
下記は、図１２に示されたＸＭＬ文書に基づきＳＩＳを生成する詳細な実施形態である。
【０１１７】
図１３に示すように生成された記号表は、図１２のＸＭＬ文書の全ての固有タグ名を有する。
【０１１８】
第１パイプライン５０は、 記号表の各エントリについて全ての位相符号化リストを生成する。すなわち、各ノードタイプについて、トリプレットがそれぞれ対応するノードのために生成される。図１３において、実インデックスについて生成される位置設定記号が図示されており、そこで、図１４に示すように、位相符号化リストが生成される。これらのトリプレットは、拡張アレイに記憶される。
【０１１９】
そして、図１４の位相符号化リストは、図１５の差分全位相符号化リストを生成するために第２パイプライン５２に渡される。差分値は、上記で説明したように計算される。すなわち、差分値Δスタート、ΔエンドおよびΔ深さは、上記で説明したように計算される。
【０１２０】
本実施形態では、棒グラフが各固有タグ名の各差分値について計算される。すなわち、差分値の発生回数は、図１６に示すようにグラフで表される。図１５で灰色にされた値は、それらが前のエントリを持たないように、棒グラフの中に組み入れられない。そこで、棒グラフのそれぞれの形は、図１７に示された一つの棒グラフのタイプに分類される。図１８は、図１６に示されたそれぞれの棒グラフの分類を示している。また、図１７は、それぞれの棒グラフを分類するための固定ビット符号化値を示している。これらは、使用された変換方法の表示として記号表の中に棒グラフタイプを記憶するために使用される。
【０１２１】
実施形態として、図１９，２０，２１は、どのように、ノードタイプＡの差分値が最適差分符号化を使用して記憶されるか、を示している。図１９（ａ）は、Δスタートについて記録した値を示している。棒グラフのカテゴリは、１００（降下）として記録されている。本実施形態では最小のΔスタート値が１４であったことが分かっているので、棒グラフの全ての値を１４だけシフトすることができるとともに、数字１４がシフト値として記録される。第１の値が棒グラフに含まれていないので（図１５で灰色にされている）、この値９は、また第１の値として記憶される。そして、残っている１２のトリプレットについて（すなわち、第１を除く全てのトリプレット）、Δスタート値がリストアップされる。図１９（ｂ）は、図１９（ａ）の後に残っている値が整列された状態を示しており、すなわち、残っている値のそれぞれはシフト値１４だけ引き算されている。図１９（ｃ）は、図１９（ｂ）の変数ビット符号化バージョンを示している。
【０１２２】
ＡについてのΔエンドおよびΔ深さの値の差分値は全て同一の値であるので、この場合は、棒グラフ符号化よりむしろパターン関数がより適当である。図２１はＡのΔエンドについて示しており、カテゴリが001（パターン関数）であるとともに、変数ビット符号化における増分値は１である（それはゼロに等しい）。図２２はＡのΔ深さを示しており、すなわち、カテゴリが再び００１であるとともに、変数ビット符号化における増分値は０である。
【０１２３】
そして、この情報は、図２１に示す表を出力するために、図１３に示されたオリジナルの記号表の中に挿入される。スタートＡについてのエントリは「１００」で始まる。この「１００」は、形が下降している棒グラフ変換機能が使用されたことを示す。エンドＡおよび深さＡについてのエントリは「００１」で始まる。この「００１」は、パターン関数変換が使用されたことを示している。
【０１２４】
更なる実施形態として、図２３は、どのように、ノードタイプｂのΔエンド値が最適差分符号化を使用して記憶されるか、を示している。図２３（ａ）は、Δエンドについて記録された値を示している。棒グラフのカテゴリは、１１０（通常）として記録されている。本実施形態では最小Δスタート値が０であったことを知っているので、シフト値も０である。第１の値が棒グラフの中に含まれていないので（図１５で灰色にされている）、この値１５も第１の値として記憶される。そこで、残っている１２のトリプレット（すなわち、第１を除く全ての組）について、Δスタート値がリストアップされる。図２３（ｂ）は、図２３（ａ）の後に残っている値が整列された状態を示しているが、ここではシフト値が０なので、図２３（ａ）および（ｂ）における残っている値は同一状態のままである。図２３（ｃ）は、図２３（ｂ）の変数ビット符号化バージョンを示している。
【０１２５】
同様に、図２４においてノードタイプＢについてのΔスタート値が示されているとともに、タグ名についてのスタートが示されている。
【０１２６】
同様に、値の残りについての記号表が図２５に示されている。これは、図１２に示された文書についてのインデックスを表している。カッコで特定された値は、ノーマル整数として記憶される。
【０１２７】
特定の実施形態で示される本発明について、広く説明される本発明の趣旨および範囲から逸脱することなく、多くの変形および／または修正が可能であることは当業者により理解される。したがって、本実施形態は、あらゆる点で実例であるとともに制限的なものではないことが考慮されるべきである。
【図面の簡単な説明】
【０１２８】
【図１】ＸＭＬ文書抜粋の階層表現を示している（従来技術）。
【図２】本発明を使用できるコンピュータシステムの構成図を示している。
【図３】位相記憶レイヤの図式的外観を示している。
【図４】更なるＸＭＬ文書抜粋の階層表現を示している。
【図５】図４における抜粋の平衡カッコ符号化を示している。
【図６】ポインタに基づいた方法と平衡カッコ方法とを使用したときの記憶空間の相違を示している。
【図７】集積簡素（Integrated Succinct：ISX）システムによるＸＭＬ文書を記憶する方法を示すフローチャートである。
【図８】本発明に係るインデックスを構成する方法を示すフローチャートである。
【図９】全てのｂノードの位相符号化リストに基づいた差分値を示す棒グラフである。
【図１０】全てのｂノードの位相符号化リストに基づいた差分値を示す棒グラフである。
【図１１】全てのｂノードの位相符号化リストに基づいた差分値を示す棒グラフである。
【図１２】本発明に係るＸＭＬ文書の簡素インデックスを示している。
【図１３】本発明に係る図１２に示すＸＭＬ文書の簡素インデックスの作成方法を示している。
【図１４】本発明に係る図１２に示すＸＭＬ文書の簡素インデックスの作成方法を示している。
【図１５】本発明に係る図１２に示すＸＭＬ文書の簡素インデックスの作成方法を示している。
【図１６Ａ】本発明に係る図１２に示すＸＭＬ文書の簡素インデックスの作成方法を示している。
【図１６Ｂ】本発明に係る図１２に示すＸＭＬ文書の簡素インデックスの作成方法を示している。
【図１７】本発明に係る図１２に示すＸＭＬ文書の簡素インデックスの作成方法を示している。
【図１８】本発明に係る図１２に示すＸＭＬ文書の簡素インデックスの作成方法を示している。
【図１９】本発明に係る図１２に示すＸＭＬ文書の簡素インデックスの作成方法を示している。
【図２０】本発明に係る図１２に示すＸＭＬ文書の簡素インデックスの作成方法を示している。
【図２１】本発明に係る図１２に示すＸＭＬ文書の簡素インデックスの作成方法を示している。
【図２２】本発明に係る図１２に示すＸＭＬ文書の簡素インデックスの作成方法を示している。
【図２３】本発明に係る図１２に示すＸＭＬ文書の簡素インデックスの作成方法を示している。
【図２４】本発明に係る図１２に示すＸＭＬ文書の簡素インデックスの作成方法を示している。
【図２５】本発明に係る図１２に示すＸＭＬ文書の簡素インデックスの作成方法を示している。
【符号の説明】
【０１２９】
６ デスクトップ・クライアント
８ ＰＤＡ／モバイル
１０ アプリケーション・ログイン
１２ 簡素インデックス
１４ インターネット
１６ 照会エンジン
１８ インデクサ
２０ ＸＭＬ文書
２２ サードパーティＤＢＭＳ
２４ 簡素エンコーダ／デコーダ
２６ 簡素ＤＢＭＳ
２８ 簡素アクセサ
【特許請求の範囲】
【請求項１】
階層構造で表されたインデックスデータのための簡素インデックス構造であって、
前記インデックス構造は、キーとして全ての異なった根から葉への経路の記号表、またはキーとして固有要素のタグ名の記号表を有し、
前記記号表におけるキーについてのエントリは、前記キーに関連したノードの変換された位相情報とともに、前記位相情報で使用される変換方法の表示情報を持っており、
使用される前記変換方法は、前記キーに関連付けられたノード間の位相関係に基づいていることを特徴とする簡素インデックス構造。
【請求項２】
前記位相情報は、各ノードについてトリプレット番号づけ構造を有する請求項１に記載の簡素インデックス構造。
【請求項３】
前記トリプレット番号づけ構造は、スタート・エンド・深さトリプレット番号づけ構造または前順・後順・深さトリプレット番号づけ構造である請求項２に記載の簡素インデックス構造。
【請求項４】
前記階層構造は、エクステンシブルマークアップ言語（ＸＭＬ）である請求項１，２または３に記載の簡素インデックス構造。
【請求項５】
前記変換方法は、前記位相情報を差分符号化するステップを有する請求項１から４のいずれか一項に記載の簡素インデックス構造。
【請求項６】
前記トリプレット番号づけ構造は、スタート・エンド・深さトリプレット番号づけ構造であるとともに、前記変換方法は、各トリプレットにおける各値を差分符号化するステップを有する請求項２に記載の簡素インデックス構造。
【請求項７】
前記トリプレットの第１の差分符号化値は、連続したトリプレットのスタート位置の差である請求項６に記載の簡素インデックス構造。
【請求項８】
各ノードのスタート位置とエンド位置間には差があり、
前記トリプレットの第２の差分符号化値は、連続したトリプレット間のそれらの値の差である請求項６または７に記載の簡素インデックス構造。
【請求項９】
第３の差分符号化値は、連続したトリプレットの深さについての差である請求項６，７または８のいずれか一項に記載の簡素インデックス構造。
【請求項１０】
前記変換方法の情報は、シフトされたキーに関連した各ノードについてのトリプレットの前記第１、第２または第３の値のそれぞれであるシフト値を有する請求項２から９のいずれか一項に記載の簡素インデックス構造。
【請求項１１】
前記変換方法の情報は、全てのノードの前記トリプレットの前記第１、第２または第３の値のそれぞれをグラフ表示する棒グラフの形状の表示情報を有する請求項２から１０のいずれか一項に記載の簡素インデックス構造。
【請求項１２】
前記変換方法の情報は、前記キーに関連した全てのノードの前記トリプレットの前記第１、第２または第３の値を出力するパターン関数を有している請求項２から１１のいずれか一項に記載の簡素インデックス構造。
【請求項１３】
キーについてのエントリは、前記位相情報の変換に使用された複数の方法を構成している請求項１から１２のいずれか一項に記載の簡素インデックス構造。
【請求項１４】
前記位相情報は、簡素データ構造から得られる請求項１から１３のいずれか一項に記載の簡素インデックス構造。
【請求項１５】
前記データは、前記階層データの前順探査によって作成された平衡カッコ表示を使用しているノードの入れ子を表す位相レイヤを有する請求項１４に記載の簡素インデックス構造。
【請求項１６】
請求項１から１５のいずれか一つに記載の簡素インデックス構造を使用する方法であって、
前記記号表において所要キーを位置付けるステップと、
前記キーに関連したノードの前記位相情報の変換に使用された変換方法に基づき、前記キーに関連した全てのノードの位相情報を検索するために前記変換された位相情報を再変換するステップと、を有する簡素インデックス構造を使用する方法。
【請求項１７】
前記方法は、構造的結合の照会を処理するために実行される請求項１６に記載の簡素インデックス構造を使用する方法。
【請求項１８】
階層構造で表されたデータについて簡素インデックスを作成する方法であって、
ツリー探査命令におけるノードの位相符号化リストを生成するためにデータを解析するステップと、
異なった根から葉への経路に関連したノードまたは固有要素のタグ名に関連したノードについて、前記ノード間の位相関係を評価するステップと、
前記評価に基づき、前記異なった根から葉への経路または固有タグ名に関連したノードの前記位相符号化リストを変換するステップと、
キーとして前記異なった根から葉への経路または固有タグ名を持っている記号表においてエントリを作成するステップと、を有し、
前記エントリは、使用された前記変換方法の表示情報と共に前記キーに関連した変換された位相情報に含まれることを特徴とする簡素インデックスを作成する方法。
【請求項１９】
前記解析するステップは、拡張アレイに記憶された位相符号化リストを生成するために前記ツリーを探査するステップを有する請求項１８に記載の簡素インデックスを作成する方法。
【請求項２０】
前記位相符号化リストは、各ノードについてトリプレット番号づけ構造を有している請求項１８または１９に記載の簡素インデックスを作成する方法。
【請求項２１】
前記トリプレット番号づけ構造は、スタート・エンド・深さトリプレット番号づけ構造または前順・後順・深さトリプレット番号づけ構造である請求項２０に記載の簡素インデックスを作成する方法。
【請求項２２】
前記拡張アレイは、一旦、所定のブロックサイズを持ち、
前記方法は、位相符号化リストを生成し続けるとともに、新たなブロックの拡張アレイに記憶するステップをさらに有する請求項１８から２１のいずれか一項に記載の簡素インデックスを作成する方法。
【請求項２３】
前記方法は、位相符号化リストを生成した後に、前記位相符号化リストを別個に再符号化するステップをさらに有する請求項２０に記載の簡素インデックスを作成する方法。
【請求項２４】
前記トリプレット番号づけ構造は、スタート・エンド・深さトリプレット番号づけ構造であるとともに、前記変換方法は、各トリプレットにおける各値を別個に再符号化するステップを有する請求項２３に記載の簡素インデックスを作成する方法。
【請求項２５】
前記トリプレットの第１の値を前記差分符号化するステップは、連続トリプレットのスタート位置における差である第１差分符号化値とともにトリプレットの第1の値を再符号化するステップを有する請求項２４に記載の簡素インデックスを作成する方法。
【請求項２６】
各ノードのスタート位置とエンド位置間には差があり、
前記トリプレットの第２の値を前記差分符号化するステップは、第２差分符号化値とともにトリプレットの第２の値を再符号化するステップを有し、
前記第２差分符号化値は、連続したトリプレット間のそれらの値の差である請求項２４または２５に記載の簡素インデックスを作成する方法。
【請求項２７】
前記トリプレットの第３の値を前記差分符号化するステップは、第３差分符号化値とともにトリプレットの第３の値を再符号化するステップを有し、
前記第３差分符号化値は、連続したトリプレットの前記深さの差である請求項２４，２５または２６に記載の簡素インデックスを作成する方法。
【請求項２８】
前記変換するステップは、同一の値に基づく前記キーに関連した各ノードについて前記トリプレットの前記第１、第２または第３の値のそれぞれをシフトするステップを有する請求項２０から２７のいずれか一項に記載の簡素インデックスを作成する方法。
【請求項２９】
前記変換するステップは、全てのノードの前記トリプレットの前記第１、第２または第３の値のそれぞれをグラフ表示する棒グラフの形状を決定するステップを有する請求項２０から２７のいずれか一項に記載の簡素インデックスを作成する方法。
【請求項３０】
前記変換するステップは、前記キーに関連した全てのノードの前記トリプレットの前記第１、第２または第３の値を出力するパターン関数を決定するステップを有する請求項２０から２９のいずれか一項に記載の簡素インデックスを作成する方法。
【請求項３１】
前記方法は、クラスタ化アルゴリズムを実行するステップをさらに有しているとともに、複数のクラスタが特定される場合、前記ブロックが各クラスタのより小さいブロックに分割される請求項３０に記載の簡素インデックスを作成する方法。
【請求項３２】
請求項１８から３１のいずれか一項に記載の階層構造で表されたデータについて簡素インデックスを作成する方法を実行するコンピュータソフトウェアアプリケーション。
【請求項３３】
階層構造で表されたデータについて簡潔インデックスを作成するためのコンピュータシステムであって、
異なった根から葉への経路に関連したノードまたは固有要素のタグ名に関連したノードについて、前記ノードの間の位相関係を評価するために、ツリー探査命令におけるノードの位相符号化リストを生成するようにデータを解析する処理手段と、
前記評価に基づき、前記異なった根から葉への経路または固有タグ名に関連したノードの前記位相符号化リストを変換する処理手段と、
キーとして前記異なった根から葉への経路または固有タグ名を持つエントリとともにインデックスを記憶する記憶手段と、を有し、
前記エントリは、使用された前記変換方法の情報と共に前記キーに関連した変換された位相情報に含まれる、ことを特徴とする簡潔インデックスを作成するためのコンピュータシステム。
【請求項３４】
前記記憶手段は、コンピュータ読取り可能記憶媒体であるとともに、請求項１８から３１のいずれか一項に記載の階層構造で表されたデータについて簡潔インデックスを作成する方法の実行動作が可能なコンピュータソフトウェアアプリケーションを記憶する請求項３３に記載の簡潔インデックスを作成するためのコンピュータシステム。
【請求項３５】
前記コンピュータシステムは、ＰＤＡ，携帯電話またはラップトップなどの携帯型コンピュータである請求項３３または３４に記載の簡潔インデックスを作成するためのコンピュータシステム。
【請求項３６】
請求項１から１５のいずれか一項に記載の階層構造で表されたデータについて簡素インデックスを使用するためのコンピュータシステムであって、
前記簡素インデックスを記憶する記憶手段と、
前記記号表において所要キーを位置付ける処理手段と、を有し、
前記キーに関連したノードの前記位相情報の変換に使用された変換方法に基づき、前記キーに関連した全てのノードの位相情報を検索するために前記変換された位相情報を再変換するように、前記記号表において所要キーを位置付ける処理手段と、を有する簡素インデックスを使用するためのコンピュータシステム。
【請求項３７】
前記記憶手段は、コンピュータ読取り可能記憶媒体であるとともに、請求項１６または１７に記載の階層構造で表されたデータについて簡素インデックスを使用する方法を実行するための動作が可能なコンピュータソフトウェアアプリケーションを記憶する請求項３６に記載の簡素インデックスを使用するためのコンピュータシステム。
【請求項３８】
前記コンピュータシステムは、遠隔装置からデータ処理要求信号を受信する通信手段をさらに有する請求項３６または３７に記載の簡素インデックスを使用するためのコンピュータシステム。
【請求項３９】
前記コンピュータシステムは、ＰＤＡ，携帯電話またはラップトップなどの携帯型コンピュータである請求項３６または３７に記載の簡素インデックスを使用するためのコンピュータシステム。
【請求項１】
階層構造で表されたインデックスデータのための簡素インデックス構造であって、
前記インデックス構造は、キーとして全ての異なった根から葉への経路の記号表、またはキーとして固有要素のタグ名の記号表を有し、
前記記号表におけるキーについてのエントリは、前記キーに関連したノードの変換された位相情報とともに、前記位相情報で使用される変換方法の表示情報を持っており、
使用される前記変換方法は、前記キーに関連付けられたノード間の位相関係に基づいていることを特徴とする簡素インデックス構造。
【請求項２】
前記位相情報は、各ノードについてトリプレット番号づけ構造を有する請求項１に記載の簡素インデックス構造。
【請求項３】
前記トリプレット番号づけ構造は、スタート・エンド・深さトリプレット番号づけ構造または前順・後順・深さトリプレット番号づけ構造である請求項２に記載の簡素インデックス構造。
【請求項４】
前記階層構造は、エクステンシブルマークアップ言語（ＸＭＬ）である請求項１，２または３に記載の簡素インデックス構造。
【請求項５】
前記変換方法は、前記位相情報を差分符号化するステップを有する請求項１から４のいずれか一項に記載の簡素インデックス構造。
【請求項６】
前記トリプレット番号づけ構造は、スタート・エンド・深さトリプレット番号づけ構造であるとともに、前記変換方法は、各トリプレットにおける各値を差分符号化するステップを有する請求項２に記載の簡素インデックス構造。
【請求項７】
前記トリプレットの第１の差分符号化値は、連続したトリプレットのスタート位置の差である請求項６に記載の簡素インデックス構造。
【請求項８】
各ノードのスタート位置とエンド位置間には差があり、
前記トリプレットの第２の差分符号化値は、連続したトリプレット間のそれらの値の差である請求項６または７に記載の簡素インデックス構造。
【請求項９】
第３の差分符号化値は、連続したトリプレットの深さについての差である請求項６，７または８のいずれか一項に記載の簡素インデックス構造。
【請求項１０】
前記変換方法の情報は、シフトされたキーに関連した各ノードについてのトリプレットの前記第１、第２または第３の値のそれぞれであるシフト値を有する請求項２から９のいずれか一項に記載の簡素インデックス構造。
【請求項１１】
前記変換方法の情報は、全てのノードの前記トリプレットの前記第１、第２または第３の値のそれぞれをグラフ表示する棒グラフの形状の表示情報を有する請求項２から１０のいずれか一項に記載の簡素インデックス構造。
【請求項１２】
前記変換方法の情報は、前記キーに関連した全てのノードの前記トリプレットの前記第１、第２または第３の値を出力するパターン関数を有している請求項２から１１のいずれか一項に記載の簡素インデックス構造。
【請求項１３】
キーについてのエントリは、前記位相情報の変換に使用された複数の方法を構成している請求項１から１２のいずれか一項に記載の簡素インデックス構造。
【請求項１４】
前記位相情報は、簡素データ構造から得られる請求項１から１３のいずれか一項に記載の簡素インデックス構造。
【請求項１５】
前記データは、前記階層データの前順探査によって作成された平衡カッコ表示を使用しているノードの入れ子を表す位相レイヤを有する請求項１４に記載の簡素インデックス構造。
【請求項１６】
請求項１から１５のいずれか一つに記載の簡素インデックス構造を使用する方法であって、
前記記号表において所要キーを位置付けるステップと、
前記キーに関連したノードの前記位相情報の変換に使用された変換方法に基づき、前記キーに関連した全てのノードの位相情報を検索するために前記変換された位相情報を再変換するステップと、を有する簡素インデックス構造を使用する方法。
【請求項１７】
前記方法は、構造的結合の照会を処理するために実行される請求項１６に記載の簡素インデックス構造を使用する方法。
【請求項１８】
階層構造で表されたデータについて簡素インデックスを作成する方法であって、
ツリー探査命令におけるノードの位相符号化リストを生成するためにデータを解析するステップと、
異なった根から葉への経路に関連したノードまたは固有要素のタグ名に関連したノードについて、前記ノード間の位相関係を評価するステップと、
前記評価に基づき、前記異なった根から葉への経路または固有タグ名に関連したノードの前記位相符号化リストを変換するステップと、
キーとして前記異なった根から葉への経路または固有タグ名を持っている記号表においてエントリを作成するステップと、を有し、
前記エントリは、使用された前記変換方法の表示情報と共に前記キーに関連した変換された位相情報に含まれることを特徴とする簡素インデックスを作成する方法。
【請求項１９】
前記解析するステップは、拡張アレイに記憶された位相符号化リストを生成するために前記ツリーを探査するステップを有する請求項１８に記載の簡素インデックスを作成する方法。
【請求項２０】
前記位相符号化リストは、各ノードについてトリプレット番号づけ構造を有している請求項１８または１９に記載の簡素インデックスを作成する方法。
【請求項２１】
前記トリプレット番号づけ構造は、スタート・エンド・深さトリプレット番号づけ構造または前順・後順・深さトリプレット番号づけ構造である請求項２０に記載の簡素インデックスを作成する方法。
【請求項２２】
前記拡張アレイは、一旦、所定のブロックサイズを持ち、
前記方法は、位相符号化リストを生成し続けるとともに、新たなブロックの拡張アレイに記憶するステップをさらに有する請求項１８から２１のいずれか一項に記載の簡素インデックスを作成する方法。
【請求項２３】
前記方法は、位相符号化リストを生成した後に、前記位相符号化リストを別個に再符号化するステップをさらに有する請求項２０に記載の簡素インデックスを作成する方法。
【請求項２４】
前記トリプレット番号づけ構造は、スタート・エンド・深さトリプレット番号づけ構造であるとともに、前記変換方法は、各トリプレットにおける各値を別個に再符号化するステップを有する請求項２３に記載の簡素インデックスを作成する方法。
【請求項２５】
前記トリプレットの第１の値を前記差分符号化するステップは、連続トリプレットのスタート位置における差である第１差分符号化値とともにトリプレットの第1の値を再符号化するステップを有する請求項２４に記載の簡素インデックスを作成する方法。
【請求項２６】
各ノードのスタート位置とエンド位置間には差があり、
前記トリプレットの第２の値を前記差分符号化するステップは、第２差分符号化値とともにトリプレットの第２の値を再符号化するステップを有し、
前記第２差分符号化値は、連続したトリプレット間のそれらの値の差である請求項２４または２５に記載の簡素インデックスを作成する方法。
【請求項２７】
前記トリプレットの第３の値を前記差分符号化するステップは、第３差分符号化値とともにトリプレットの第３の値を再符号化するステップを有し、
前記第３差分符号化値は、連続したトリプレットの前記深さの差である請求項２４，２５または２６に記載の簡素インデックスを作成する方法。
【請求項２８】
前記変換するステップは、同一の値に基づく前記キーに関連した各ノードについて前記トリプレットの前記第１、第２または第３の値のそれぞれをシフトするステップを有する請求項２０から２７のいずれか一項に記載の簡素インデックスを作成する方法。
【請求項２９】
前記変換するステップは、全てのノードの前記トリプレットの前記第１、第２または第３の値のそれぞれをグラフ表示する棒グラフの形状を決定するステップを有する請求項２０から２７のいずれか一項に記載の簡素インデックスを作成する方法。
【請求項３０】
前記変換するステップは、前記キーに関連した全てのノードの前記トリプレットの前記第１、第２または第３の値を出力するパターン関数を決定するステップを有する請求項２０から２９のいずれか一項に記載の簡素インデックスを作成する方法。
【請求項３１】
前記方法は、クラスタ化アルゴリズムを実行するステップをさらに有しているとともに、複数のクラスタが特定される場合、前記ブロックが各クラスタのより小さいブロックに分割される請求項３０に記載の簡素インデックスを作成する方法。
【請求項３２】
請求項１８から３１のいずれか一項に記載の階層構造で表されたデータについて簡素インデックスを作成する方法を実行するコンピュータソフトウェアアプリケーション。
【請求項３３】
階層構造で表されたデータについて簡潔インデックスを作成するためのコンピュータシステムであって、
異なった根から葉への経路に関連したノードまたは固有要素のタグ名に関連したノードについて、前記ノードの間の位相関係を評価するために、ツリー探査命令におけるノードの位相符号化リストを生成するようにデータを解析する処理手段と、
前記評価に基づき、前記異なった根から葉への経路または固有タグ名に関連したノードの前記位相符号化リストを変換する処理手段と、
キーとして前記異なった根から葉への経路または固有タグ名を持つエントリとともにインデックスを記憶する記憶手段と、を有し、
前記エントリは、使用された前記変換方法の情報と共に前記キーに関連した変換された位相情報に含まれる、ことを特徴とする簡潔インデックスを作成するためのコンピュータシステム。
【請求項３４】
前記記憶手段は、コンピュータ読取り可能記憶媒体であるとともに、請求項１８から３１のいずれか一項に記載の階層構造で表されたデータについて簡潔インデックスを作成する方法の実行動作が可能なコンピュータソフトウェアアプリケーションを記憶する請求項３３に記載の簡潔インデックスを作成するためのコンピュータシステム。
【請求項３５】
前記コンピュータシステムは、ＰＤＡ，携帯電話またはラップトップなどの携帯型コンピュータである請求項３３または３４に記載の簡潔インデックスを作成するためのコンピュータシステム。
【請求項３６】
請求項１から１５のいずれか一項に記載の階層構造で表されたデータについて簡素インデックスを使用するためのコンピュータシステムであって、
前記簡素インデックスを記憶する記憶手段と、
前記記号表において所要キーを位置付ける処理手段と、を有し、
前記キーに関連したノードの前記位相情報の変換に使用された変換方法に基づき、前記キーに関連した全てのノードの位相情報を検索するために前記変換された位相情報を再変換するように、前記記号表において所要キーを位置付ける処理手段と、を有する簡素インデックスを使用するためのコンピュータシステム。
【請求項３７】
前記記憶手段は、コンピュータ読取り可能記憶媒体であるとともに、請求項１６または１７に記載の階層構造で表されたデータについて簡素インデックスを使用する方法を実行するための動作が可能なコンピュータソフトウェアアプリケーションを記憶する請求項３６に記載の簡素インデックスを使用するためのコンピュータシステム。
【請求項３８】
前記コンピュータシステムは、遠隔装置からデータ処理要求信号を受信する通信手段をさらに有する請求項３６または３７に記載の簡素インデックスを使用するためのコンピュータシステム。
【請求項３９】
前記コンピュータシステムは、ＰＤＡ，携帯電話またはラップトップなどの携帯型コンピュータである請求項３６または３７に記載の簡素インデックスを使用するためのコンピュータシステム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６Ａ】
【図１６Ｂ】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６Ａ】
【図１６Ｂ】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【公表番号】特表２００９−５１８７１８（Ｐ２００９−５１８７１８Ａ）
【公表日】平成２１年５月７日（２００９．５．７）
【国際特許分類】
【出願番号】特願２００８−５４３６１１（Ｐ２００８−５４３６１１）
【出願日】平成１８年１２月５日（２００６．１２．５）
【国際出願番号】ＰＣＴ／ＡＵ２００６／００１８４３
【国際公開番号】ＷＯ２００７／０６５２０７
【国際公開日】平成１９年６月１４日（２００７．６．１４）
【出願人】（５０７０７４１３３）ナショナル・アイシーティ・オーストラリア・リミテッド (10)
【Ｆターム（参考）】
【公表日】平成２１年５月７日（２００９．５．７）
【国際特許分類】
【出願日】平成１８年１２月５日（２００６．１２．５）
【国際出願番号】ＰＣＴ／ＡＵ２００６／００１８４３
【国際公開番号】ＷＯ２００７／０６５２０７
【国際公開日】平成１９年６月１４日（２００７．６．１４）
【出願人】（５０７０７４１３３）ナショナル・アイシーティ・オーストラリア・リミテッド (10)
【Ｆターム（参考）】
[ Back to top ]