(57)【要約】【課題】コンパクトデシジョンダイアグラムを用いた効率的インデックス付けを行うことである。【解決手段】一実施形態による方法は、キーワードを含むサーチ可能なオブジェクトのセットの逆索引にアクセスする段階を含む。逆索引は複数のリストを含み、各リストは一キーワードに対応し、その一キーワードを示すオブジェクトの一サブセットを特定する。この方法は、各リストのバイナリデシジョンダイアグラム（ＢＤＤ）を生成する段階を含む。ＢＤＤは一キーワードに対応し、ＢＤＤの各デシジョンノードはリストの一キーワードを含むサーチ可能なオブジェクトのセット中のオブジェクトを表す。この方法は、各リストをそのＢＤＤとして記憶する段階を含む。ＢＤＤの記憶により、逆索引のより効率的な記憶が容易になる。【選択図】図１
2008192157.tif 000002
【特許請求の範囲】
【請求項１】
キーワードを含むサーチ可能オブジェクトのセットの逆索引であって、一キーワードにそれぞれ対応する複数のリストを有し、前記一キーワードを有するオブジェクトの一サブセットを示す逆索引にアクセスする段階と、
各リストのバイナリデシジョンダイアグラム（ＢＤＤ）であって、そのリストの前記一キーワードに対応し、そのＢＤＤの各デシジョンノードが前記リストの前記一キーワードを有する前記サーチ可能なオブジェクトのセット中のオブジェクトを表すＢＤＤを生成する段階と、
各リストをそのＢＤＤとして記憶し、前記ＢＤＤの記憶により前記逆索引のより効率的な記憶を容易にする段階とを有する方法。
【請求項２】
前記ＢＤＤの一部はゼロ抑制ナノバイナリデシジョンダイアグラム（ナノＺＤＤ）である、
請求項１に記載の方法。
【請求項３】
前記ＢＤＤの一部は区分順序バイナリデシジョンダイアグラム（ＰＯＢＤＤ）である、
請求項１に記載の方法。
【請求項４】
前記ＢＤＤの一部はカスタム化されたノード構成を有する、
請求項１に記載の方法。
【請求項５】
前記オブジェクトはウェブページであり、ウェブサーチエンジンが記憶された前記ＢＤＤを用いてサーチ結果を生成する、
請求項１に記載の方法。
【請求項６】
ＢＤＤの記憶は、その各ノードについて、変数ＩＤ、０エッジネゲートフラグ、及びＴＨＥＮ／ＥＬＳＥポインタのみを、前記ＢＤＤのサイズに対して最小ビット数を用いて記憶することを含む、
請求項１に記載の方法。
【請求項７】
キーワードを有するサーチ可能なオブジェクトのセットの逆索引のリストであって、一キーワードに対応し、前記一キーワードを有するオブジェクトの一サブセットを特定するリストを表すバイナリデシジョンダイアグラム（ＢＤＤ）であって、前記リストの前記一キーワードを有する前記サーチ可能なオブジェクトのセットのうちのオブジェクトを表すＢＤＤにアクセスする段階と、
前記リストの要素を次の段階により決定する段階とを有する方法。
前記ＢＤＤのデシジョンノードの０エッジから、前記ＢＤＤの終了ノード１まで、１つ以上の経路に沿って前記ＢＤＤを縦断する段階と、
縦断した各経路に応じて前記リストの要素の変数配列に値のセットを割り当てる段階とを有する方法。
【請求項８】
前記リストの第１の要素の決定は、
前記ＢＤＤのデシジョンノードの０エッジから、前記ＢＤＤのルートノードから前記ＢＤＤの終了ノード１まで、第１の経路に沿って前記ＢＤＤを縦断する段階と、
前記第１の経路に１エッジを有する前記ＢＤＤのデシジョンノードに対応する前記配列中の各変数に１を割り当て、前記第１の経路に０エッジを有する前記ＢＤＤのデシジョンノードに対応するか、前記ＢＤＤから除外されたデシジョンノードに対応する前記配列中の各変数に０を割り当てる、
請求項７に記載の方法。
【請求項９】
さらに、前記リストの決定された要素を用いて、前記リストと前記逆索引の他のリストとの間の結合を計算する段階を有する、
請求項７に記載の方法。
【請求項１０】
前記ＢＤＤはゼロ抑制ナノバイナリデシジョンダイアグラム（ナノＺＤＤ）である、
請求項７に記載の方法。
【請求項１１】
前記ＢＤＤの一部は区分順序バイナリデシジョンダイアグラム（ＰＯＢＤＤ）である、
請求項７に記載の方法。
【請求項１２】
前記オブジェクトはウェブページである、
請求項７に記載の方法。
【請求項１３】
実行したとき、次の段階を実行するソフトウェアを有するコンピュータ読み取り可能媒体：
キーワードを含むサーチ可能オブジェクトのセットの逆索引であって、一キーワードにそれぞれ対応する複数のリストを有し、前記一キーワードを有するオブジェクトの一サブセットを示す逆索引にアクセスする段階と、
各リストのバイナリデシジョンダイアグラム（ＢＤＤ）であって、そのリストの前記一キーワードに対応し、そのＢＤＤの各デシジョンノードが前記リストの前記一キーワードを有する前記サーチ可能なオブジェクトのセット中のオブジェクトを表すＢＤＤを生成する段階と、
各リストをそのＢＤＤとして記憶し、前記ＢＤＤの記憶により前記逆索引のより効率的な記憶を容易にする段階。
【請求項１４】
前記ＢＤＤの一部はゼロ抑制ナノバイナリデシジョンダイアグラム（ナノＺＤＤ）である、
請求項１３に記載のコンピュータ読み取り可能媒体。
【請求項１５】
前記ＢＤＤの一部は区分順序バイナリデシジョンダイアグラム（ＰＯＢＤＤ）である、
請求項１３に記載のコンピュータ読み取り可能媒体。
【請求項１６】
前記ＢＤＤの一部はカスタム化されたノード構成を有する、
請求項１３に記載のコンピュータ読み取り可能媒体。
【請求項１７】
前記オブジェクトはウェブページであり、ウェブサーチエンジンが記憶された前記ＢＤＤを用いてサーチ結果を生成する、
請求項１３に記載のコンピュータ読み取り可能媒体。
【請求項１８】
ＢＤＤの記憶は、その各ノードについて、変数ＩＤ、０エッジネゲートフラグ、及びＴＨＥＮ／ＥＬＳＥポインタのみを、前記ＢＤＤのサイズに対して最小ビット数を用いて記憶することを含む、
請求項１３に記載のコンピュータ読み取り可能媒体。
【請求項１９】
実行したとき、次の段階を実行するソフトウェアを有するコンピュータ読み取り可能媒体：
キーワードを有するサーチ可能なオブジェクトのセットの逆索引のリストであって、一キーワードに対応し、前記一キーワードを有するオブジェクトの一サブセットを特定するリストを表すバイナリデシジョンダイアグラム（ＢＤＤ）であって、前記リストの前記一キーワードを有する前記サーチ可能なオブジェクトのセットのうちのオブジェクトを表すＢＤＤにアクセスする段階と、
前記リストの要素を次の段階により決定する段階と、
前記ＢＤＤのデシジョンノードの０エッジから、前記ＢＤＤの終了ノード１まで、１つ以上の経路に沿って前記ＢＤＤを縦断する段階と、
縦断した各経路に応じて前記リストの要素の変数配列に値のセットを割り当てる段階。
【請求項２０】
前記リストの第１の要素の決定は、
前記ＢＤＤのデシジョンノードの０エッジから、前記ＢＤＤのルートノードから前記ＢＤＤの終了ノード１まで、第１の経路に沿って前記ＢＤＤを縦断する段階と、
前記第１の経路に１エッジを有する前記ＢＤＤのデシジョンノードに対応する前記配列中の各変数に１を割り当て、前記第１の経路に０エッジを有する前記ＢＤＤのデシジョンノードに対応するか、前記ＢＤＤから除外されたデシジョンノードに対応する前記配列中の各変数に０を割り当てる、
請求項１９に記載のコンピュータ読み取り可能媒体。
【請求項２１】
前記ソフトウェアは、実行されたとき、さらに、前記リストの決定された要素を用いて、前記リストと前記逆索引の他のリストとの間の結合を計算する段階を実行する、
請求項１９に記載のコンピュータ読み取り可能媒体。
【請求項２２】
前記ＢＤＤはゼロ抑制ナノバイナリデシジョンダイアグラム（ナノＺＤＤ）である、
請求項１９に記載のコンピュータ読み取り可能媒体。
【請求項２３】
前記ＢＤＤの一部は区分順序バイナリデシジョンダイアグラム（ＰＯＢＤＤ）である、
請求項１９に記載のコンピュータ読み取り可能媒体。
【請求項２４】
前記オブジェクトはウェブページである、
請求項１９に記載の方法。
【請求項２５】
キーワードを含むサーチ可能オブジェクトのセットの逆索引であって、一キーワードにそれぞれ対応する複数のリストを有し、前記一キーワードを有するオブジェクトの一サブセットを示す逆索引にアクセスする手段と、
各リストのバイナリデシジョンダイアグラム（ＢＤＤ）であって、そのリストの前記一キーワードに対応し、そのＢＤＤの各デシジョンノードが前記リストの前記一キーワードを有する前記サーチ可能なオブジェクトのセット中のオブジェクトを表すＢＤＤを生成する手段と、
各リストをそのＢＤＤとして記憶し、前記ＢＤＤの記憶により前記逆索引のより効率的な記憶を容易にする手段とを有するシステム。
【請求項２６】
キーワードを有するサーチ可能なオブジェクトのセットの逆索引のリストであって、一キーワードに対応し、前記一キーワードを有するオブジェクトの一サブセットを特定するリストを表すバイナリデシジョンダイアグラム（ＢＤＤ）であって、前記リストの前記一キーワードを有する前記サーチ可能なオブジェクトのセットのうちのオブジェクトを表すＢＤＤにアクセスする手段と、
前記リストの要素を、
前記ＢＤＤのデシジョンノードの０エッジから、前記ＢＤＤの終了ノード１まで、１つ以上の経路に沿って前記ＢＤＤを縦断する段階と、
縦断した各経路に応じて前記リストの要素の変数配列に値のセットを割り当てる段階とにより決定する手段とを有するシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ワールドワイドウェブ中のウェブページ等のオブジェクトを検索するためのデータ構造に関する。
［関連出願］
この出願は、米国仮出願第６０／８９９８７４号（２００７年２月７日出願）の米国特許法第１１９条（ｅ）の利益を主張するものである。
【背景技術】
【０００２】
バイナリディシジョンダイアグラム（ＢＤＤ）は、コンピュータサイエンスの多くの分野で有用であり、潜在的に様々なアプリケーションに使用できる。しかし、ＢＤＤはスペース爆発（space  blowup）を起こすことが多い。スペース爆発を起こさなくても、ＢＤＤは多くのアプリケーションで大きくなりすぎるリスクが大きい。
【発明を実施するための最良の形態】
【０００３】
図１は、コンパクトデシジョンダイアグラムを用いる効率的なインデクシング（indexing）システム１０の一例を示す図である。システム１０は、ネットワーク１２を含み、このネットワーク１２により、クライアント１４と、ウェブサーバ１６と、アプリケーションサーバ１８とが相互に結合されている。一部の実施形態では、ネットワーク１２は、イントラネット、エクストラネット、仮想プライベートネットワーク（ＶＰＮ）、ローカルエリアネットワーク（ＬＡＮ）、ワイヤレスＬＡＮ（ＷＬＡＮ）、ワイドエリアネットワーク（ＷＡＮ）、メトロポリタンエリアネットワーク（ＭＡＮ）、インターネットの一部、その他のネットワーク１２、またはこれらの２つ以上の組合せである。本発明では、ネットワーク１２は任意の適切なものでよい。リンク２０により、クライアント１４、ウェブサーバ１６、アプリケーションサーバ１８はネットワーク１２に結合されている。一部の実施形態では、各リンク２０は有線リンク、無線リンク、または光リンクを含む。一部の実施形態では、各リンク２０は、イントラネット、エクストラネット、仮想プライベートネットワーク（ＶＰＮ）、ＬＡＮ、ＷＬＡＮ、ＷＡＮ、ＭＡＮ、インターネットの一部、その他のリンク２０、またはこれらの２つ以上の組合せである。本開示は、クライアント１４、ウェブサーバ１６、及びアプリケーションサーバ１８をネットワーク１２結合するリンク２０は、適切なものであればいかなるものでもよい。
【０００４】
一部の実施形態では、クライアント１４により、クライアント１４のユーザはウェブサーバ１６にあるウェブページにアクセスできる。限定としてではなく例として、クライアント１４は、ウェブブラウザを有するコンピュータシステム（デスクトップコンピュータシステム、ノートブックコンピュータシステム、携帯電話等）であってもよい。クライアント１４のユーザは、ウェブブラウザをウェブ１６に向けるＵＲＬ（Uniform  Resource  Locator）その他のアドレスを入力し、ウェブブラウザは、ＨＴＴＰ（Hyper  Text  Transfer  Protocol）リクエストを生成し、そのＨＴＴＰリクエストをウェブサーバ１６に送信する。ウェブサーバ１６は、そのＨＴＴＰリクエストを受信し、そのＨＴＴＰリクエストに応じたＨＴＭＬ（Hyper  Text  Markup  Language）文書を生成してクライアント１４に送信する。ウェブサーバ１６からのＨＴＭＬ文書はウェブページであり、クライアント１４のウェブブラウザはそれをユーザに表示する。本開示では、ウェブページは適切なものであればいかなるものでもよい。限定ではなく例として、ウェブページはＸＭＬ（Extensible  Markup  Language）文書またはＸＨＴＭＬ（Extensible  HyperText  Markup  Language）文書である。さらに、本開示では、オブジェクトは任意の適切なものでよく、ウェブサーバ１６にあるウェブページには限定されない。限定ではなく例として、必要に応じて、本開示は、データベースサーバ、ファイルサーバ、ピアツーピアネットワーク、その他にある実行ファイル、ファイル（例えば、マイクロソフトワード文書やＰＤＦ文書）、その他のオブジェクトを想定している。一部の実施形態では、ウェブサーバ１６には１つ以上のサーバが含まれる。本発明では、サーバ１６は適切なものであればいかなるものでもよい。本発明では、クライアント１４は適切なものであればいかなるものでもよい。限定ではなく例として、ウェブブラウザにウェブサーバ１６にあるウェブページにアクセスさせるのに加えて、またはそれに替えて、クライアント１４は、アプリケーションにデータベースサーバ、ファイルサーバ、ピアツーピアネットワークその他にあるオブジェクトにアクセスさせる。
【０００５】
クライアント１４のユーザからの入力に応じて、クライアント１４は、特定のキーワードを含むウェブページのクエリを生成して、そのクエリを適切なサーバ１８に送信する。実施形態では、アプリケーションサーバ１８は、クライアント１４からのクエリを受信して応答するハードウェア、ソフトウェア、組み込みロジックコンポーネント、またはこれらの構成要素の組み合わせを含む。限定ではなく一例として、アプリケーションサーバ１８は、具体的なキーワードを含むウェブページに対するクエリをクライアント１４から受信し、そのクエリを受け付け、ウェブサーチエンジン２２にアクセスしてそのクエリを実行し、そのクエリに応じてサーチ結果を生成する。次に、ウェブサーチエンジン２２はクエリを実行し、サーチ結果を生成して返す。アプリケーションサーバ１８はそのサーチ結果をクライアント１４に送信し、ユーザに表示する。一部の実施形態では、アプリケーションサーバ１８には１つ以上のサーバが含まれる。本発明のアプリケーションサーバ１８は、適切なものであればいかなるものでもよい。限定ではなく一例として、アプリケーションサーバ１８は、クライアント１４のユーザがイントラネットやエクストラネット等の分散ネットワークにわたってオブジェクトを集中的にサーチできるアクセスポイントを提供するカタログサーバを含む。
【０００６】
実施形態では、ウェブサーチエンジン２２は、クライアント１４からのクエリに応じて、ウェブページを特定するサーチ結果を生成して返すハードウェア、ソフトウェア、組み込みロジックコンポーネント、またはこれらの構成要素の組み合わせを含む。本発明のウェブ検索エンジン２２は適切なものであればいかなるものでもよい。限定ではなく一例として、ウェブサーチエンジン２２は、ＢＡＩＤＵ、ＧＯＯＧＬＥ、ＬＩＶＥ  ＳＥＡＲＣＨ、またはＹＡＨＯＯ！  ＳＥＡＲＣＨである。実施形態では、クエリに応じてクエリを実行してサーチ結果を生成するため、ウェブサーチエンジン２２はウェブサーチデータ２８にアクセスする。限定ではなく一例として、ウェブサーチデータ２８は、ウェブサーバ１６にあるウェブページの逆索引（inverted  indexes）を含む。各逆索引は、以下に説明するように、一意的なキーワードに対応するリストのセットを含む。以下に説明するように、インデックスエンジン２４は逆索引を生成し、デシジョンダイアグラムエンジン２６は逆索引のリストを表すデシジョンダイアグラム（コンパクトデシジョンダイアグラム等）を生成する。デシジョンダイアグラムは、そのリストを圧縮して記憶や処理を容易にする。インデックスエンジン２４、デシジョンダイアグラムエンジン２６、またはその両方は共同で、（以下に説明するように）逆索引またはそのリストを操作して、ウェブサーチエンジン２２によるクエリの実行とサーチ結果の生成を容易にする。実施形態では、インデックスエンジン２４は、逆索引を生成して処理するハードウェア、ソフトウェア、組み込みロジックコンポーネント、またはこれらの構成要素の組み合わせを含む。実施形態では、デシジョンダイアグラムエンジン２６は、逆索引のリストを表しそのリストを処理するためのデシジョンダイアグラムを生成するためのハードウェア、ソフトウェア、組み込みロジックコンポーネント、またはこれらの構成要素の組み合わせを含む。実施形態では、ウェブサーチエンジン２２、インデックスエンジン２４、デシジョンダイアグラムエンジン２６はすべて論理的または物理的に互いに別々である。一部の実施形態では、ウェブサーチエンジン２２とインデックスエンジン２４は、機能的、論理的、または物理的に一体である。限定ではなく一例として、インデックスエンジン２４は機能的、論理的、または物理的にウェブサーチエンジン２２を含む。一部の実施形態では、インデックスエンジン２４とデシジョンダイアグラムエンジン２６は、機能的、論理的、または物理的に一体である。限定ではなく一例として、インデックスエンジン２４は機能的、論理的、または物理的にデシジョンダイアグラムエンジン２６を含む。本発明では、ウェブサーチエンジン２２とインデックスエンジン２４とデシジョンダイアグラムエンジン２６間の機能的、論理的、または物理的な構成は、適切なものであればいかなるものでもよい。
【０００７】
一部の実施形態では、ＢＤＤはブール関数を表すルートを有する有向非巡回グラフ（rooted  directed  acyclic  graph）（ＤＡＧ）である。ＤＡＧは複数の決定ノード（ルートノードも決定ノードである）と２つの終点ノード、０−ターミナルと１−ターミナルを含む。終点ノードはブール関数の１と０を表す。各決定ノードは、サブ関数ｆを表し、ブーリアン変数ｖをラベルとして有し、子ノードに向けて１エッジと０エッジとが出ている。１エッジは関数ｖ・ｆを表すサブＢＤＤを指し、０エッジは関数
【数１】
2008192157.tif 000003
を表すサブＢＤＤを指す。言い換えると、１エッジはｖに１を付与することを表し、０エッジはｖに０を付与することを表す。２つのエッジは別のノードを指す。ＢＤＤのルートノードから１終点までの経路は、ブーリアン関数を１に設定する変数付与のセットを表す。ＢＤＤのルートノードから０終点までの経路は、ブーリアン関数を０に設定する変数付与のセットを表す。図２は、関数
【数２】
2008192157.tif 000004
を表すＢＤＤの一例を示す図である。一部の実施形態では、ＢＤＤは同型のサブグラフを含まず、ＢＤＤのルートノードから終点ノードまでの変数の順序はすべての経路で同じである。かかるＢＤＤは縮小順序ＢＤＤ（reduced  ordered  BDD）（ＲＯＢＤＤ）である。ここで、場合に応じて、ＢＤＤと言ったときにはＲＯＢＤＤを含み、その逆の場合もある。さらに、場合に応じて、ＢＤＤと言ったときには区分順序バイナリデシジョンダイアグラム（partitioned  ordered  binary  decision  diagram）（ＰＯＢＤＤ）を含み、その逆の場合もある。一部の実施形態では、簡単のため、ノードの両方のエッジが同じノードを指す場合、そのノードはＢＤＤに含めない。一部の実施形態では、ノードが負の直定値（negative  literal）であるとき、そのノードはＢＤＤに含めない。負の直定値を含まないＢＤＤは、ゼロ抑制デシジョンダイアグラム（zero-suppressed  decision  diagram）（ＺＤＤ）である。ここで、場合に応じて、ＢＤＤと言ったときにはＺＤＤを含み、その逆の場合もある。本発明のデシジョンダイアグラムは好適なものであればいかなるものでもよい。一部の実施形態では、デシジョンダイアグラムを用いたリスト（逆索引のリスト等）の表現には、そのリストの要素のブーリアン関数へのマッピングとその結果のデシジョンダイアグラムのディスクへの効率的な記憶が含まれる。
【０００８】
実施形態によりより効率的なＢＤＤの記憶が容易になる。一部の実施形態では、より効率的なＢＤＤの記憶により、中央処理装置（central  processing  unit）（ＣＰＵ）のキャッシュはＢＤＤのより多くのノードを記憶でき、ＣＰＵによるＢＤＤの処理が容易になる。一部の実施形態により、ＢＤＤを表すグラフの各ノードが必要とするバイト数を削減でき、ＢＤＤのサイズを縮小できる。一部の実施形態により、ＢＤＤのノード数を削減することなく、そのＢＤＤのサイズを削減することが容易になる。一部の実施形態により、ＢＤＤのサイズの低減が容易になるが、ＢＤＤを機能的な処理はしやすい。一部の実施形態により、モバイルタイプの消費者向けアプリケーション（かかるアプリケーションでは、データ圧縮が必要になる場合が多い）におけるＢＤＤの使用が容易になる。
【０００９】
上記の通り、デシジョンダイアグラムエンジン２６がＢＤＤを生成する。一部の実施形態では、ＢＤＤ（コンパクトデシジョンダイアグラムまたはナノデシジョンダイアグラム（ナノＤＤ）でもよい）をコンパクトにするため、デシジョンダイアグラムエンジン２６は、可変順序（variable  ordering）を破棄し、ポインタにより指定された位置をポインタ値と親ノードの位置との両方に相関させる。一部の実施形態では、かかる条件下、３２ノードを有するＢＤＤの各子ノードに必要な最小限度の情報は、次の通りである：
変数ＩＤ：５ビット
０エッジネゲートフラグ：１ビット
ＴＨＥＮ／ＥＬＳＥポインタ：
【数３】
2008192157.tif 000005
ＳはＢＤＤのノード数を表す。可変ＩＤはノードをラベル付けし、３２個のノードのラベルには、２５＝３２だから、少なくとも５ビットが必要である。ＴＨＥＮ／ＥＬＳＥポインタは子ノードを指す。一部の実施形態では、ＴＨＥＮポインタは１エッジポインタであり、ＥＬＳＥポインタは０エッジポインタである。一部の実施形態では、０エッジネゲートフラグ（０  edge  negated  flag）は、ゼロ抑制がノードをネゲートするかどうかを示す。デシジョンダイアグラムがＺＤＤであるとき、ノード構造は０エッジネゲートフラグを含む必要はない。デシジョンダイアグラムエンジン２６は、ＢＤＤの各ノードが必要とするバイト数を求める。一部の実施形態では、そのバイト数は
【数４】
2008192157.tif 000006
である。一部の実施形態では、ＢＤＤのカスタマイズされたノード構造を仮定して、そのＢＤＤを記憶する。一部の実施形態では、デシジョンダイアグラムエンジン２６が生成するナノＤＤは、ゼロ抑制ナノバイナリデシジョンダイアグラム（ナノＺＤＤ）（zero-suppressed  nano  binary  decision  diagrams）である。
【００１０】
一部の実施形態では、ＢＤＤをさらにコンパクトにするために、デシジョンダイアグラムエンジン２６は、ＴＨＥＮ／ＥＬＳＥポインタのｌｏｇ（Ｓ）ビットをドロップし、各ポインタの値とそれの親ノードの値（または位置）を、そのポインタが指す位置に相関させる。かかる条件の下、各ポインタに１乃至２バイトのみを割り当てることにより、ノードごとのメモリ必要量を削減する。一部の実施形態では、任意の適切なデシジョンダイアグラムはコンパクト化でき、デシジョンダイアグラムを記憶するために、そのデシジョンダイアグラムが大きくなると、デシジョンダイアグラムエンジン２６はテーブルの大きさを適当に変更する（そしてノードごとにより多くのビットを割り当てる）。しかし、デシジョンダイアグラムエンジン２６は、コンパクトデシジョンダイアグラムとしてデシジョンダイアグラムの構成を開始する。一部の実施形態では、デシジョンダイアグラムエンジン２６は、大きさを変えるのではなく、グラフ構成に直接的に分割・合成を行って、コンパクトデシジョンダイアグラムを縮小してないダイアグラムに直接的に変換する。一部の実施形態では、コンパクトデシジョンダイアグラムにより並列プラットフォーム間の通信が容易になる。限定ではなく一例として、第１のプラットフォームは、デシジョンダイアグラムを生成し、第１のプラットフォームと並列に動作している第２のプラットフォームに送信するためにそのデシジョンダイアグラムをコンパクト化して、そのコンパクト化したデシジョンダイアグラムを第２のプラットフォームに送信する。第２のプラットフォームは、そのコンパクト化したデシジョンダイアグラムから、第２のプラットフォームで処理するデシジョンダイアグラムを再構成してもよい。一部の実施形態では、ナノＤＤは、例えば、集積回路（ＩＣ）の合成やＩＣの形式ベリフィケーション等の任意の適切なＢＤＤのアプリケーションにおいて有用である。一部の実施形態では、ナノＤＤは任意の適切なＢＤＤ演算をサポートする。
【００１１】
一部の実施形態では、ＢＤＤを用いて、サーチエンジン（ウェブサーチエンジン２２等）や同様のアプリケーションの逆索引を実施する。一部の実施形態では、ＢＤＤを用いて逆索引を実施することにより、逆索引をより効率的に記憶できる。一部の実施形態では、逆索引の望ましい操作性に悪い影響を与えずに、逆索引をより効率的に記憶できる。一部の実施形態では、ＢＤＤを用いて逆索引を実施することにより、逆索引の操作が容易になる。
【００１２】
上記のように、インデックスエンジン２４は逆索引を生成する。一部の実施形態では、逆索引は、文書その他のオブジェクト（例えば、ワールドワイドウェブのウェブページなど）のセットに作用してキーワードを含むその文書の一部を特定するデータ構造である。限定ではなく一例として、キーワードは、ユーザがウェブサーチエンジンに送信したクエリを表す。一部の実施形態では、逆索引をリストのセットとして記憶し、各リストは一意的なキーワードｗｉに対応し、ｗｉを含む文書の数字識別子を含む。逆索引は、構成さえるにつれて非常に大きくなりがちであり、それは直ちに記憶容量とアクセス時間がかかることを意味する。一部の実施形態では、インデックスエンジン２４、デシジョンダイアグラムエンジン２６、またはその両方は、記憶のために逆索引のリストを圧縮し、必要に応じて、そのリストを素早く、増分を逆圧縮させる。
【００１３】
一部の実施形態では、素早く解凍できるようにリストを圧縮する効率的な方法は、γ符号に基づく。γ符号では、整数ｘ＞０は因数分解され、２ｅ＋ｍとなる。ここで、
【数５】
2008192157.tif 000007
ｘのコードは、単項式の（ｅ＋１）に２進数ｍを連続したものである。一例として、ｘ＝１３の符号を計算する場合、ｅ＝３、ｍ＝５であり、ｘ＝２３＋５である。（ｅ＋１）の単項表示は１１１０であり、それゆえ、ｘのγ符号は１１１０１０１である。γ符号の利点は、ｘを表すのに正確に
【数６】
2008192157.tif 000008
ビットを必要とし、ｘが平均的に比較的小さい時に、固定長２進数表現するよりも大幅な節約になる。
【００１４】
一部の実施形態では、リストに関してγ符号を次のように使用する。リストの要素を記憶し、隣接するエントリ間の対差異（pairwise  differences）をγ符号化する。限定ではなく一例として、リスト［２３，１２５，３７，５４，８６，３３］を圧縮すると、ソートされたリストと対差異のリストは次のようになる：
ソートされたリスト：［２３，３３，３７，５４，８６，１２５］
対差異のリスト：［２３，１０，４，１７，３２，３９］
それゆえ、γ符号化されるリストは、次のようになる：
［１１１１００１１１，１１１００１０，１１０００，１１１１００００１，１１１１１００００００，１１１１１０００１１１］
【００１５】
限定ではなく一例として、リスト［２３，３３，３７，５４］を考える。２進数では、リストの要素は［０１０１１１，１００００１，１００１０１，１１０１１０］である。２進数に変換する場合、最小数の変数でリストを表すブーリアン関数を求めるため、各変数を各有効ビットウェイトに割り当てる。上記のリストに対応する関数は次の通りである：
【数７】
2008192157.tif 000009
線形符号化する場合、別の表現を求めるため、各文書ＩＤに別の変数を割り当てる。しかし、かかる表現は実際的ではないかも知れない。非常に多数の文書が関係してくるからである。さらに、単一のブーリアン関数で複数のリストを表せなければ、ノードの共有は不可能かも知れない。
【００１６】
２ｋ進符号化の場合、リスト要素を２ｋ進数で表し、線形符号化と２進符号化を結合する。２ｋ個の変数を使用して、２ｋ進数の各桁をワン・ホットなやり方（in  a  one-hot  manner）で表す。限定ではなく一例として、数５４（４進法では３１２である）を符号化するには、各桁をワン・ホット符号化して、１０００：００１０：０１００を得る。それゆえ、要素５４は
【数８】
2008192157.tif 000010
と符号化できる。変数の数が増えるので効率的ではないと思われるかも知れないが、これにより共有がより容易になりよりコンパクトな表現になる。特にＺＤＤではそうである。ＺＤＤでは、上記の通り負の直定値がより効率的に記憶されるからである。
【００１７】
各リストについて、対応するブーリアン関数を構成し、適切なＢＤＤパッケージを用いてそのブーリアン関数のＢＤＤ（好ましくはＺＤＤである。負の直定値をより効率的に記憶できるからである。）を構成する。ｎを変数の数とし、ｄをＢＤＤ中のノードの数とする。ＢＤＤの各ノードについて、ノードをラベリングする変数のインデックスとしては
【数９】
2008192157.tif 000011
ビットあれば十分であり、その位置を特定するためには
【数１０】
2008192157.tif 000012
ビットあれば十分である。したがって、ナノＤＤ中の各ノードは次のように構成できる：
【表１】
2008192157.tif 000013
１つのナノＤＤノードには、ちょうど２ｓｄ＋ｓｎビットが必要である。ノードは、縦に並んだ順で（the  order  depth-first  traversal  would  visit  them）、かつ０エッジから１エッジの順でメモリまたはディスクに連続に記憶される。従って、ディスク上のナノＤＤから情報を追加的に抽出できる。終了ノードは明示的には記憶する必要はない。終了ノードには一定の「仮想的な」位置が割り当てられるからである。
【００１８】
ウェブページのインデックス（順次または逆向き）をコンパクト化する１つの方法は、ページＩＤとインデックス中のキーワードＩＤとを２進数に符号化し、各｛ｐａｇｅ＿ＩＤ，ｋｅｙ＿ｗｏｒｄ＿ＩＤ｝を最小項としてそのインデックスを表すデシジョンダイアグラムに追加することを含む。かかる方法は、ウェブページを解析してインデックスするのが非常に遅い。ウェブページのインデックスをコンパクト化する他の１つの方法は、インデックス中のページＩＤを２進数に符号化して、インデックス中の各キーワードに対して別々のデシジョンダイアグラムを構成することを含む。かかる方法は、前の方法よりもインデックスのコンパクト化の程度が低いが、ずっと早い。ウェブページのインデックスをコンパクト化するさらに他の１つの方法は、インデックス中の各キーワードに対してデシジョンダイアグラム（そのキーワードを含むウェブページのセットを表すデシジョンダイアグラム）を構成して、すべてのデシジョンダイアグラム間で共有するという考えを捨てることを含む。各デシジョンダイアグラムは、およそ数１０から数１０００のノードを含む。デシジョンダイアグラムのサイズは、構成するまで分からない。各ノードについて最小限必要な情報は次の通りである：
変数ＩＤ：５ビット
０エッジネゲートフラグ：１ビット
ＴＨＥＮ／ＥＬＳＥポインタ：
【数１１】
2008192157.tif 000014
Ｓはデシジョンダイアグラムのノード数を表す。各デシジョンダイアグラムについて、デシジョンダイアグラムエンジン２６は、そのデシジョンダイアグラムの各ノードが必要とするバイト数を特定する。そのバイト数は
【数１２】
2008192157.tif 000015
である。あるいは、デシジョンダイアグラムがＺＤＤであるとき、ノード構造は０エッジネゲートフラグを含む必要はない。デシジョンダイアグラムエンジン２６は、各デシジョンダイアグラムを、そのデシジョンダイアグラムのノード構成をカスタム化したものと仮定して、記憶する。かかる方法は、前出の２つの方法よりも大幅にインデックスをコンパクト化する。一部の実施形態では、デシジョンダイアグラム中の各キーワードについて、デシジョンダイアグラムエンジン２６は、そのデシジョンダイアグラムの（必要メモリに関する）サイズを、そのデシジョンダイアグラムが表すリストの（必要メモリに関する）サイズとを比較して、２つのうち小さい方を記憶する。一部の実施形態では、逆索引のスペース効率を向上する。一部の実施形態では、サーチ結果の逆索引に対する複雑なブーリアン演算が容易になる。一部の実施形態では、圧縮が特に有用であることが多いモバイルアプリケーションにおいて、逆索引の実施が容易になる。
【００１９】
共役は、Ｋ個の有向リスト間での共通の演算である。結合はＫウェイマージ（K-way  merge）として実施してもよい。要素を同時に読み出し、リストの最初から開始して、すべての共通要素を検出するまでリストを進む。限定ではなく一例として、次の２つのリスト間で共通の要素を検出する：
【表２】
2008192157.tif 000016
ポインタｐ１はリスト１の要素を指し、ポインタｐ２はリスト２の要素を指す。最初にｐ１はリスト１の１０を指し、ｐ２はリスト２の１６を指す。ｐ１が指す要素はｐ２が指す要素よりも小さいので、ｐ１はリスト１の次の要素２０に進む。ここで、ｐ２が指す要素はｐ１が指す要素よりも小さいので、ｐ２はリスト２の次の要素１８に進む。１８は２０より小さいので、ｐ２はリスト２の２３に進む。ｐ１はリスト１の２３に進む。ポインタｐ１とｐ２はここで最初の共通要素を指しており、その最初の共通要素すなわち２３が出力される。次にｐ１はリスト１の３６に進み、ｐ２はリスト２の４７に進む。ここで、ポインタｐ１が指す要素はポインタｐ２が指す要素より小さいので、ｐ１はリスト１の４７に進む。ポインタｐ１とｐ２は第２の共通要素を指しており、その第２の共通要素すなわち４７が出力される。ポインタｐ２はリスト２の終わりについたので、これ以上共通要素はないので、終了する。
【００２０】
リストを横断する基本的な操作はｇｅｔ＿ｎｅｘｔ＿ｅｌｅｍｅｎｔ（Ｌ）である。ナノＤＤの場合、一部の実施形態では、操作ｇｅｔ＿ｎｅｘｔ＿ｅｌｅｍｅｎｔ＿ｇｒｅｑ（Ｌ，ｅｌｅｍｅｎｔ）を効率的に実施し、リストＬの次の要素であってｅｌｅｍｅｎｔ以上のものを検出する。ｇｅｔ＿ｎｅｘｔ＿ｅｌｅｍｅｎｔ＿ｇｒｅｑ（Ｌ，ｅｌｅｍｅｎｔ）を実施するために、一部の実施形態では、ナノＤＤの変数割り当て配列Ａを維持し、そのナノＤＤを横断している間、その配列を更新する。ナノＤＤに記憶されている第１の要素を求めるために、そのナノＤＤのルートから始めて縦断する。この操作は、まず０エッジを進み、ナノＤＤの１終点に到達するまで進む。各ノードについて、ノードの変数ＩＤと、そのノードに行くエッジのＩＤとを監視する。この操作により、最初に、ナノＤＤのルートから１終点に至る経路中に現れない変数に、値０を割り当てる。
【００２１】
一部の実施形態では、インデックスエンジン２４またはデシジョンダイアグラムエンジン２６がｇｅｔ＿ｎｅｘｔ＿ｅｌｅｍｅｎｔ＿ｇｒｅｑ（Ｌ，ｅｌｅｍｅｎｔ）をコールする時、ｅｌｅｍｅｎｔの２進表現を配列Ａと比較して、ルートからの共通変数割り当ての数を検出する。最初から（または、共通の割り当てがない場合、ルートから）第１の共通でない変数に到達するまで引き返し、ｅｌｅｍｅｎｔによる残りの割り当てに従ってナノＤＤを横断する。限定ではなく一例として、図２に示したデシジョンダイアグラムに対するｇｅｔ＿ｎｅｘｔ＿ｅｌｅｍｅｎｔ＿ｇｒｅｑ（Ｌ，ｅｌｅｍｅｎｔ）の操作を考える。上記の通り、図２に示したデシジョンダイアグラムは関数
【数１３】
2008192157.tif 000017
を表す。それゆえ、デシジョンダイアグラムはリスト［８，１１，１２，１５］を符号化する。図３は、符号化されたリストの第１の要素を求めるデシジョンダイアグラムの横断例を示している。この横断（traversal）による変数割り当ては（ｘ１，ｘ２，ｘ３，ｘ４）＝（１，０，０，０）であり、リストの最初の要素８となる。リストの次の要素にアクセスするため、ｇｅｔ＿ｎｅｘｔ＿ｅｌｅｍｅｎｔ＿ｇｒｅｑ（Ｌ，９）により８より大きい次の要素をサーチする。次に、（（１，０，０，０）と（１，０，０，１）間の最初の３つの変数割り当てが同じなので）変数ｘ３に引き返し、図４に示した経路に沿って続ける。横断からの変数割り当ては（１，０，１，１）であり、１１になる。同様に、このリスト中の残りの要素を求める。
【００２２】
一部の実施形態では、上記のようにサーチにデシジョンダイアグラムを使用することにより、スキップする要素がなくてもよいとき、リスト中の要素をスキップできる。限定ではなく一例として、リスト［８，１１，１２，１５］と［７，１３，１５］の結合を考える。両方のリストの最初の要素を求める。８は７より大きいので、第２のリストをサーチして次の要素で８以上のものを探し、１３を得る。次に、第１のリストにｇｅｔ＿ｎｅｘｔ＿ｅｌｅｍｅｎｔ＿ｇｒｅｑ（Ｌ，１３）を実行する。（１，１，０，１）（２進法で１３）のみが第１の変数が（１，０，０，０）（２進法で８）と共通であることを検出する。次に、変数ｘ１に直接引き返し、要求された割り当て（１，１，０，１）と一致するナノＤＤを横断し、結局（１，１，１，１）で終わる。
【００２３】
本発明は、ここに説明した実施形態に対する、当業者が想到するだろうすべての変更、置換、変形、代替、修正を含むものである。同様に、適切な場合には、特許請求の範囲は、ここに説明した実施形態に対する、当業者が想到するだろうすべての変更、置換、変形、代替、修正を含むものである。
【図面の簡単な説明】
【００２４】
【図１】コンパクトデシジョンダイアグラムを用いる効率的なインデクシングシステムの一例を示す図である。
【図２】ＢＤＤの一例を示す図である。
【図３】ＢＤＤの横断例を示す図である。
【図４】ＢＤＤの横断の他の例を示す図である。
【図１】
2008192157.tif 000018
【図２】
2008192157.tif 000019
【図３】
2008192157.tif 000020
【図４】
2008192157.tif 000021
【外国語明細書】
2008192157000001.pdf