(57)【要約】      （修正有）【課題】  データベース群にインデックスを付けるため、およびデータベース群を探索するための方法およびシステムを提供する。【解決手段】  探索システムが、データベース群を生成的にサンプリングすることにより、データベース群に対するインデックスを生成し、そのインデックスを使用して、そのデータベース群を探索するためのクエリを特定し、構築する。生成されたインデックスは、ドメイン属性インデックスと呼ばれ、ドメインレベルインデックスおよびサイトレベルインデックスを含む。データベースに対するサイトレベルインデックスは、サイト属性をデータベース内の相異なる属性値にマップする。ドメインに対するドメインレベルインデックスは、属性値を、それらの属性値を含むデータベースとサイト属性のペアにマップする。【選択図】  図１
2006012125.tif 000002
【特許請求の範囲】
【請求項１】
１つのデータベースの１つのエントリの少なくとも１つの属性内にそれぞれが含まれる複数の属性値に関して、前記属性値から、データベース、およびデータベースのエントリの属性の中に該属性値を含む該データベースの該属性へのマッピングを含む、データベース群の探索をサポートするためのデータ構造を含むことを特徴とするコンピュータ読み取り可能な記録媒体。
【請求項２】
前記データ構造は、ドメインスキーマのドメイン属性をデータベース群の対応する属性にマップする対応情報を含むことを特徴とする請求項１に記載のコンピュータ読み取り可能な記録媒体。
【請求項３】
前記データ構造は、各データベース、および該データベース内の各属性に関して、該データベース内のエントリの該属性内に含まれる相異なる属性値へのマッピングを含むことを特徴とする請求項１に記載のコンピュータ読み取り可能な記録媒体。
【請求項４】
相異なる属性値への各マッピングは、前記データベースのエントリの該属性内の該属性値の頻度の指示を含むことを特徴とする請求項３に記載のコンピュータ読み取り可能な記録媒体。
【請求項５】
データベースは、Ｗｅｂデータベースであることを特徴とする請求項１に記載のコンピュータ読み取り可能な記録媒体。
【請求項６】
前記マッピングは、前記データベースのエントリの該属性内の前記属性値の出現頻度の指示を含むことを特徴とする請求項１に記載のコンピュータ読み取り可能な記録媒体。
【請求項７】
前記マッピングは、属性に基づいて分離されることを特徴とする請求項１に記載のコンピュータ読み取り可能な記録媒体。
【請求項８】
前記マッピングは、ドメイン属性インデックスのドメインレベルを表すことを特徴とする請求項１に記載のコンピュータ読み取り可能な記録媒体。
【請求項９】
前記データ構造は、各データベースに関して、サイトレベルインデックスを含むことを特徴とする請求項８に記載のコンピュータ読み取り可能な記録媒体。
【請求項１０】
コンピュータシステムにおける、Ｗｅｂデータベース群を探索するための方法であって、
項目を有する非構造化クエリを受け取るステップと、
属性項目をＷｅｂデータベースの属性に対応する項目として識別するステップと、
属性値項目をＷｅｂデータベースの属性値に対応する項目として識別するステップと、
属性項目と属性値項目のペアに関して、前記属性値項目に設定された前記属性項目に対応する前記属性を有するクエリを構築するステップと、
前記構築されたクエリをＷｅｂデータベース群に送信するステップと
を備えることを特徴とする方法。
【請求項１１】
前記構築されたクエリを送信する前に、前記構築されたクエリを送信するための前記Ｗｅｂデータベース群のサブセットを特定するステップを含むことを特徴とする請求項１０に記載の方法。
【請求項１２】
属性項目および属性値項目を前記識別するステップは、ドメイン属性インデックスを使用することを特徴とする請求項１０に記載の方法。
【請求項１３】
前記ドメイン属性インデックスは、１つのデータベースの１つのエントリの少なくとも１つの属性内にそれぞれが含まれる複数の属性値に関して、前記属性値から、データベース、およびデータベースのエントリの属性の中に該属性値を含む該データベースの該属性へのマッピングを提供することを特徴とする請求項１２に記載の方法。
【請求項１４】
前記ドメイン属性インデックスは、各データベース、および該データベース内の各属性に関して、該データベース内のエントリの該属性内に含まれる相異なる属性値へのマッピングを提供することを特徴とする請求項１２に記載の方法。
【請求項１５】
前記ドメイン属性インデックスは、ドメインレベルインデックスおよびサイトレベルインデックスを含むことを特徴とする請求項１２に記載の方法。
【請求項１６】
Ｗｅｂデータベース群を探索するためのコンピュータシステムにおける方法であって、
属性と属性値のペアを受け取るステップと、
それぞれの受け取られたペアに関するクエリを構築するステップと、
ドメイン属性インデックスを使用して、前記構築されたクエリが送信されるべきＷｅｂデータベース群を特定するステップと、
前記構築されたクエリを前記特定されたＷｅｂデータベース群に送信するステップと
を備えることを特徴とする方法。
【請求項１７】
前記ドメイン属性インデックスは、１つのデータベースの１つのエントリの少なくとも１つの属性内にそれぞれが含まれる複数の属性値に関して、前記属性値から、データベース、およびデータベースのエントリの属性の中に該属性値を含む該データベースの該属性へのマッピングを提供することを特徴とする請求項１６に記載の方法。
【請求項１８】
前記ドメイン属性インデックスは、各データベース、および該データベース内の各属性に関して、該データベース内のエントリの該属性内に含まれる相異なる属性値へのマッピングを提供することを特徴とする請求項１６に記載の方法。
【請求項１９】
前記ドメイン属性インデックスは、ドメインレベルインデックスおよびサイトレベルインデックスを含むことを特徴とする請求項１６に記載の方法。
【請求項２０】
ドメイン内のデータベース群をサンプリングするためのコンピュータシステムにおける方法であって、
前記ドメインの属性に属性値のセットを与えるステップと、
サンプリングされるべきデータベースを選択するステップと、
属性を選択し、選択された前記属性の属性値を選択するステップと、
選択された前記属性値を有する選択された前記属性にクエリを行うクエリを選択された前記データベースに送信するステップであって、
送信された前記クエリは、結果を生成するステップと、
前記結果に基づいて選択された前記データベースと前記属性値の間のマッピングを生成するステップと
を備えることを特徴と摺る方法。
【請求項２１】
前記結果に基づいて前記ドメインの属性に関する属性値の前記セットを更新して、クエリが次回に送信される際に、更新されたセットからの属性値を使用することができるようにすることを特徴とする請求項２０に記載の方法。
【請求項２２】
生成された前記マッピングは、ドメイン属性インデックスであることを特徴とする請求項２０に記載の方法。
【請求項２３】
生成された前記マッピングは、サイトレベルインデックスであることを特徴とする請求項２２に記載の方法。
【請求項２４】
生成された前記マッピングは、ドメインレベルインデックスであることを特徴とする請求項２２に記載の方法。
【請求項２５】
属性および属性値は、ランダムに選択されることを特徴とする請求項２０に記載の方法。
【請求項２６】
最少の数の相異なる属性値を有する属性が選択されることを特徴とする請求項２０に記載の方法。
【請求項２７】
まだ選択されていない属性値の中で最多の出現回数を有する属性値が選択されることを特徴とする請求項２０に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
説明する技術は、一般に、データベース群の探索に関し、より詳細には、Ｗｅｂデータベース群の探索に関する。
【背景技術】
【０００２】
Ｗｏｒｌｄ  Ｗｉｄｅ  Ｗｅｂ（「Ｗｅｂ」）は、Ｗｅｂページを介してアクセス可能である膨大な量の情報を提供する。Ｗｅｂページは、静的コンテンツまたは動的コンテンツを含むことが可能である。静的コンテンツとは、一般に、Ｗｅｂページの多数回のアクセスを通して同一のままである情報を指す。動的コンテンツとは、一般に、Ｗｅｂデータベースの中に格納されており、探索要求に応答してＷｅｂページに追加される情報を指す。動的コンテンツは、深層Ｗｅｂまたは隠されたＷｅｂと呼ばれてきたものを表す。
【０００３】
多くの探索エンジンサービスは、ユーザが、Ｗｅｂの静的コンテンツを探索することを可能にする。ユーザが、探索項目を含む探索要求または探索クエリを送信した後、探索エンジンサービスは、それらの探索項目に関連する可能性があるＷｅｂページを特定する。それらのＷｅｂページが、探索結果である。関連するＷｅｂページを迅速に特定するため、探索エンジンサービスは、Ｗｅｂページに対するキーワードのマッピングを保持することができる。このマッピングは、「Ｗｅｂ」を「クロール（ｃｒａｗｌ）」して各Ｗｅｂページのキーワードを特定することにより、生成することができる。Ｗｅｂをクロールするのに、探索エンジンサービスは、ルートＷｅｂページのリストを使用して、それらのルートＷｅｂページを介してアクセス可能であるすべてのＷｅｂページを特定することができる。任意の特定のＷｅｂページのキーワードは、見出しの語、Ｗｅｂページのメタデータの中で供給される語、強調表示された語などを特定するなどの、様々な周知の情報取得技術を使用して特定することができる。
【０００４】
しかし、それらの探索エンジンサービスは、一般に、クロール可能でないコンテンツと考えられてもいる、動的コンテンツの探索を可能にしない。動的コンテンツの探索が抱える１つの問題は、いくつかの理由で、Ｗｅｂデータベースのコンテンツを効果的に取り出し、インデックスを付けることができないことである。１つの理由は、複数のＷｅｂデータベースのコンテンツが、取り出し、インデックスを付けるには大き過ぎる可能性があることである。別の理由は、Ｗｅｂデータベースのスキーマが、探索インタフェースの背後に隠されていること、すなわち、探索Ｗｅｂページ（および結果Ｗｅｂページ）の属性だけが、ユーザに公開されていることである。動的コンテンツの探索が抱える別の問題は、生成されたインデックスが、非構造化クエリと構造化クエリをともにサポートする必要があることである。非構造化クエリは、ドキュメントを探索する場合に一般に使用される探索項目のリストである。例えば、非構造化クエリは、「Ｈａｒｒｙ  Ｐｏｔｔｅｒ  Ｒｏｗｌｉｎｇ」であることが可能である。構造化クエリは、データベースを探索する場合に一般に使用される属性および属性値のリストである。例えば、構造化クエリは、「ｔｉｔｌｅ＝Ｈａｒｒｙ  Ｐｏｔｔｅｒ  ａｎｄ  ａｕｔｈｏｒ＝Ｒｏｗｌｉｎｇ」であることが可能である。
【０００５】
複数のＷｅｂデータベースにわたる探索を提供する「メタサーチャ（ｍｅｔａｓｅａｒｃｈｅｒ）」を開発することの相当な研究が行われてきた。メタサーチャは、クエリを受け取ると、「ソース選択」と呼ばれる、関連するコンテンツを含む可能性が最も高いＷｅｂデータベース群の選択を行う。次に、メタサーチャは、「クエリ変換」と呼ばれる、特定されたＷｅｂデータベース群のそれぞれに適したフォーマットへのクエリの変換を行う。例えば、メタサーチャは、メタサーチャのクエリの属性を、それぞれの選択されたＷｅｂデータベースのサイト属性にどのようにマップするかを理解する必要がある。例えば、メタサーチャが、「フォーマット」という名前の属性を使用して、本の媒体（例えば、ペーパーバックまたはハードカバー）を指すのに対し、Ｗｅｂデータベースは、「タイプ」という名前の属性を使用して同一のデータを指す可能性がある。クエリ変換は、メタサーチャのフォーマット属性をＷｅｂデータベースのタイプ属性にマップする必要がある。メタサーチャは、「ディスパッチ（ｄｉｓｐａｔｃｈ）」と呼ばれる、変換されたクエリの選択されたＷｅｂデータベースへの送信を行う。メタサーチャは、探索の結果を受け取ると、「結果統合」と呼ばれる、結果の全体的結果への統合を行う。
【０００６】
いくつかの文献に上述のような従来の技術に関連した技術内容が開示されている（例えば、非特許文献１参照）。
【０００７】
【非特許文献１】Inpeirotis, Panagiotis G.他, "Probe, Count, and Classify: Categorizing Hidden-Web Databases," ACM SGMOD 2001 May 21-24, Santa Barbara, California, Copyright 2001
【発明の開示】
【発明が解決しようとする課題】
【０００８】
非構造化クエリと構造化クエリの両方を使用した効果的な探索を可能にする、Ｗｅｂデータベースに対するインデックスを効率的に生成するための技術を有することが望まれている。
【０００９】
本発明は、このような状況に鑑みてなされたもので、その目的とするところは、効果的な探索を可能にする、データベース群にインデックスを付けるため、およびデータベース群を探索するための方法およびシステムを提供することにある。
【課題を解決するための手段】
【００１０】
ドメイン内のＷｅｂデータベース群にインデックスを付けるため、およびＷｅｂデータベース群を探索するための方法およびシステムを提供する。一実施形態では、探索システムは、データベース群を生成的に（ｇｅｎｅｒａｔｉｖｅｌｙ）サンプリングすることによってＷｅｂデータベース群に対するインデックスを生成し、そのインデックスを使用して、データベース群を探索するためのクエリを特定し、構築する（ｆｏｒｍｕｌａｔｅ）。生成されたインデックスは、ドメイン属性インデックスと呼ばれ、ドメインレベルインデックスを含み、各データベースに関して、サイトレベルインデックスを含む。データベースに対するサイトレベルインデックスは、サイト属性をデータベース内の相異なる属性値にマップする。ドメインに対するドメインレベルインデックスは、属性値を、それらの属性値を含むデータベースとサイト属性のペアにマップする。あるドメイン内のデータベースに対するサイトレベルインデックスを生成するのに、探索システムは、そのドメインに関するサンプルデータの初期セットから始める。探索システムは、ドメイン−サイトマッピングを使用して、ドメイン属性に対応するデータベースのサイト属性を選択する。探索システムは、そのドメイン属性に関するサンプルデータから属性値を選択する。次に、探索システムは、データベースに対するサンプリングクエリを生成して、送信し、選択されたサイト属性の中で選択された属性値と合致するエントリを探索する。エントリをクエリ結果として受け取ると、探索システムは、そのデータベースに対するサイトレベルインデックスを生成し、このインデックスは、サイト属性を、それらのサイト属性内に含まれる相異なる属性値にマップする。探索システムは、様々なサイトレベルインデックスからドメインレベルインデックスを生成することができる。
【００１１】
一実施形態では、探索システムは、ユーザが、複数のデータベースを探索する場合に、非構造化クエリまたは構造化クエリを指定することができるようにする。探索システムは、非構造化クエリの項目が、ドメインレベルインデックスに基づく属性または属性値を表すかどうかをまず識別することにより、非構造化クエリを一連の構造化クエリにマップする。属性項目および属性値項目のセットを識別した後、探索システムは、属性項目と属性値項目のそれぞれの組み合わせに関するクエリを生成する。探索システムは、非構造化クエリに関して使用されるのと同様なマッピングを実行する必要なしに、構造化クエリの属性と属性値のペアを直接に使用することができる。探索システムは、ドメインレベルインデックスを使用し、どのデータベースにクエリが送信されるべきかを識別する。
【発明を実施するための最良の形態】
【００１２】
以下、図面を参照して本発明を適用できる実施形態を詳細に説明する。Ｗｅｂデータベース群にインデックスを付けるため、およびＷｅｂデータベース群を探索するための方法およびシステムを提供する。一実施形態では、探索システムが、データベース群を生成的にサンプリングすることによってＷｅｂデータベース群に対するインデックスを生成し、そのインデックスを使用して、そのデータベース群を探索するためのクエリを構築する。生成されたインデックスは、ドメイン属性インデックスと呼ばれ、ドメインレベルインデックスを含み、各データベースに関して、サイトレベルインデックスを含む。ドメインは、特定のトピック（例えば、書籍または自動車）を対象とするデータベースの集合である。各ドメインは、そのドメインのデータベース群のスキーマの中で一般に見出されるドメイン属性のセットを定義する、ドメインスキーマ（「グローバルスキーマ」とも呼ばれる）を有する。例えば、ドメインが書籍に関係する場合、ドメインスキーマは、著者属性および書名属性を含むことが可能である。というのは、ほとんどの書籍データベースは、それらの属性を有するからである。データベースに対するサイトレベルインデックスは、サイト属性をデータベース内の相異なる属性値にマップする。例えば、データベースが、Ｔｏｌｋｉｅｎという属性値を有する著者属性を有するエントリを含む場合、サイトレベルインデックスは、著者属性をＴｏｌｋｉｅｎにマップする。探索システムは、以下に説明するとおりデータベース群をサンプリングすることにより、サイトレベルインデックスを生成する。ドメインレベルインデックスは、属性値を、それらの属性値を含むデータベースとサイト属性のペアにマップする。例えば、ドメインレベルインデックスは、Ｔｏｌｋｉｅｎの書籍に関するエントリを含むデータベース、およびそのデータベースの著者属性にマップされた、Ｔｏｌｋｉｅｎという属性値に関するエントリを含む。探索システムは、サイトレベルインデックスからドメインレベルインデックスを生成することができる。ドメインレベルインデックスは、サイトレベルインデックスのマージされ、逆転された形態である。クエリを処理するのに、探索システムは、ドメイン属性インデックスを使用して、いずれのデータベース群が探索されるべきかを選択し、ドメイン−サイト属性マッピングを使用して、クエリを、それぞれの選択されたデータベースに適切なクエリに変換する。次に、探索システムは、変換されたクエリを選択されたデータベース群に送信する。次に、探索システムは、ドメイン−サイト属性マッピングを使用してクエリの結果を統合して、サイト属性からの結果をドメイン属性にマップする。
【００１３】
あるドメイン内のデータベースに対するサイトレベルインデックスを生成するのに、探索システムは、そのドメインに関するサンプルデータの初期セットから始める。サンプルデータは、ドメイン内のデータベース群に関するサンプルエントリを提供する。エントリは、ドメインスキーマのドメイン属性の属性値を提供する。例えば、書籍のドメイン内のサンプルデータは、「Ｈａｒｒｙ  Ｐｏｔｔｅｒ  ａｎｄ  ｔｈｅ  Ｏｒｄｅｒ  ｏｆ  ｔｈｅ  Ｐｈｏｅｎｉｘ」に設定された書名属性、およびＲｏｗｌｉｎｇに設定された著者属性を有する１つのエントリ、ならびに「Ｔｈｅ  Ｆｅｌｌｏｗｓｈｉｐ  ｏｆ  ｔｈｅ  Ｒｉｎｇ」に設定された書名属性、およびＴｏｌｋｉｅｎに設定された著者属性を有する別のエントリを含むことが可能である。データベースをサンプリングするのに、探索システムは、ドメイン−サイトマッピングを使用して、ドメイン属性に対応するデータベースのサイト属性を選択する。探索システムは、そのドメイン属性に関するサンプルデータから属性値を選択する。次に、探索システムは、データベースに対するサンプリングクエリを生成し、送信して、選択されたサイト属性の中の選択された属性値に合致するエントリを探索する。例えば、選択されたサイト属性が著者であり、選択された属性値がＴｏｌｋｉｅｎであった場合、クエリは、Ｔｏｌｋｉｎｅによって書かれた書籍に関するエントリを探索する。クエリ結果としてエントリを受け取ると、探索システムは、そのデータベースに対するサイトレベルインデックスを生成し、このインデックスは、サイト属性を、それらのサイト属性内に含まれる相異なる属性値にマップする。例えば、結果は、Ｄｅｌ  Ｒｅｙによって出版されたＴｏｌｋｉｅｎの書籍「Ｓｉｌｍａｒｉｌｌｉｏｎ」に関するエントリ、Ｈｏｕｇｈｔｏｎ  Ｍｉｆｆｌｉｎによって出版されたＴｏｌｋｉｅｎの書籍「Ｒｏｖｅｒａｎｄｏｍ」に関するエントリ、およびＨｏｕｇｈｔｏｎ  Ｍｉｆｆｌｉｎによって出版されたＴｏｌｋｉｅｎの書籍「Ｔｈｅ  Ｈｏｂｂｉｔ」を含むことが可能である。そうである場合、サイトレベルインデックスは、書名サイト属性をＳｉｌｍａｒｉｌｌｉｏｎ、Ｒｏｖｅｒａｎｄｏｍ、およびＨｏｂｂｉｔという語にマップし、出版元サイト属性をＤｅｌ、Ｒｅｙ、Ｈｏｕｇｈｔｏｎ、およびＭｉｆｆｌｉｎという語にマップする。探索システムは、各属性値がサンプル結果内で出現する回数も把握していることが可能である。例えば、２という出現カウントが、Ｈｏｕｇｈｔｏｎという属性値に関連していることが可能である。というのは、Ｈｏｕｇｈｔｏｎが、そのサンプル結果の２つのエントリの中で出現するからである。データベースの有効範囲（ｃｏｖｅｒａｇｅ）、つまり、サイトレベルインデックスの中で表されるエントリの数を増大させるため、探索システムは、サンプル結果のデータを使用して、そのデータベースに対する新たなサンプリングクエリを構築する。例えば、探索システムは、Ｈｏｕｇｈｔｏｎに設定されたサイト出版元属性を有するサンプリングクエリを構築することができ、このクエリは、Ｈｏｕｇｈｔｏｎ  Ｍｉｆｆｌｉｎによって出版された書籍に関するすべてのエントリを取り出す。次に、探索システ���は、サイトレベルインデックスを更新して、サイトレベルインデックスが、データベースのすべてのＨｏｕｇｈｔｏｎ  Ｍｉｆｆｌｉｎの書籍を「範囲に含む（ｃｏｖｅｒ）」するようにして、データベースの有効範囲を増大させる。探索システムは、そのサンプリング結果を使用して、さらなるサンプリングクエリを生成することができる。このため、探索システムは、サンプリング探索の以前のサンプリング結果に基づき、データベースの有効範囲を生成的に拡大する。
【００１４】
一実施形態では、探索システムは、様々なサイトレベルインデックスからドメインレベルインデックスを生成する。探索システムは、サイトレベルインデックスの間のそれぞれの相異なる属性値に関して、ドメインレベルインデックスにエントリを追加する。例えば、５つのデータベースが、Ｔｏｌｋｉｅｎによる書籍に関するエントリを有する場合、ドメインレベルインデックスは、その５つのデータベースの１つ、およびそのデータベースの著者サイト属性をそれぞれが特定する少なくとも５つのサブエントリを有する、Ｔｏｌｋｉｅｎに関するエントリを有する。データベースの１つが、「Ｊ．Ｒ．Ｒ．Ｔｏｌｋｉｅｎ：Ａｒｃｈｉｔｅｃｔ  ｏｆ  Ｍｉｄｄｌｅ  Ｅａｒｔｈ：Ａ  Ｂｉｏｇｒａｐｈｙ」という書籍に関するエントリを含む場合、Ｔｏｌｋｉｅｎに対するドメインレベルインデックスのエントリは、書名サイト属性を特定するそのデータベースに関するサブエントリも含むことが可能である。ドメインレベルインデックスは、各データベース内におけるその属性値の頻度を示す頻度情報も、各サブエントリの中に含むことが可能である。探索システムは、クエリを送信するためのデータベース群を選択する際、その頻度情報を使用することができる。一実施形態では、探索システムは、ドメイン属性に基づいてドメインレベルインデックスを分割する、または分離することができる。例えば、ドメインレベルインデックスは、書名ドメイン属性に対するサブインデックス、および著者ドメイン属性に対する別のサブインデックスを有することが可能である。サブインデックスのそれぞれは、複数のデータベース内におけるその属性のそれぞれの相異なる属性値に関するエントリを含む。サブインデックスの使用は、探索システムが、属性値をまず選択し、次に、その属性に対応するサブクエリを探索しなければならないのではなく、構造化クエリの属性に対して適切なサブインデックスをまず選択し、次に、その属性値を含むエントリ（その属性にすべて対応するサブエントリ群を含む）を選択することができるようにすることにより、構造化クエリを変換することを容易にする。
【００１５】
一実施形態では、探索システムは、ユーザが、複数のデータベースを探索する際、非構造化クエリまたは構造化クエリを指定することができるようにする。探索システムは、非構造化クエリの項目が、ドメインレベルインデックスに基づく属性または属性値を表すかどうかをまず識別することにより、非構造化クエリを一連の構造化クエリにマップする。例えば、非構造化クエリは、ユーザが、Ｔｏｌｋｉｅｎという著者について書かれた書籍を探索することを所望する場合、「ｔｉｔｌｅ（書名）ａｕｔｈｏｒ（著者）Ｔｏｌｋｉｅｎ」であることが可能である。探索システムは、ドメインスキーマ内の属性の名前であるために、ともにドメイン属性である書名という項目と著者という項目を識別する。探索システムは、書名、著者、およびＴｏｌｋｉｅｎという項目が、データベース内の属性値であるため、属性値であることも識別することができる。書名および著者という項目は、データベースの１つが、「１９９７  Ｈａｒｖａｒｄ  Ｂｕｓｉｎｅｓｓ  Ｓｃｈｏｏｌ  Ｃｏｒｅ  Ｃｏｌｌｅｃｔｉｏｎ：Ａｎ  Ａｕｔｈｏｒ，Ｔｉｔｌｅ，ａｎｄ  Ｓｕｂｊｅｃｔ  Ｇｕｉｄｅ」という書籍に関するエントリを有するため、属性値であることが可能である。属性項目および属性値項目のセットを識別した後、探索システムは、属性項目と属性値項目の各組み合わせに関するクエリを生成する。例えば、探索システムは、書名、著者、およびＴｏｌｋｉｅｎという属性値を使用して書名属性に関するクエリを生成し、書名、著者、およびＴｏｌｋｉｅｎという属性値を使用して著者属性に関するクエリを生成する。探索システムは、非構造化クエリに関して使用されるのと同様なマッピングを実行する必要なしに、構造化クエリの属性と属性値のペアを直接に使用することができる。非構造化クエリまたは構造化クエリを使用して、探索システムは、ドメイン属性を選択されたデータベース群のサイト属性に変換する。次に、探索システムは、それらのクエリを、ドメイン属性インデックスに基づいて選択されたデータベース群に送信する。というのは、例えば、そのようなデータベース群は、クエリの属性および属性値に対応するエントリを有することが分かっているからである。探索システムは、ドメイン属性インデックスの情報に基づき、クエリが送信されるべき順序も特定することができる。例えば、探索システムは、データベース群が多くのエントリを戻す可能性が高い（例えば、頻度数が、多数のエントリが戻されることを示す）ことをドメイン属性インデックスが示すかどうかに基づき、データベース群を順序付けることを選択することができる。
【００１６】
データベースのサンプリングは、データベースに重い負荷をかける可能性があるため、探索システムは、様々な技術を使用して、より少ないサンプリングでデータベースのより大きい有効範囲を確実にすることができる。探索システムは、ランダムサンプリング、属性適応サンプリング、および値適応サンプリングを含むことが可能な、様々なサンプリング基準を使用することができる。ランダムサンプリングを使用する場合、探索システムは、サイト属性をランダムに選択し、その選択された属性のまだ選択されていない属性値をランダムに選択する。属性適応サンプリングを使用する場合、探索システムは、データベース群のすべての属性の中で最少の数の相異なる属性値を有するサイト属性を選択する。次に、探索システムは、そのサイト属性の未使用の属性値をランダムに選択する。値適応サンプリングを使用する場合、探索システムは、最少の数の相異なる属性値を有するサイト属性を選択するが（属性適応サンプリングと同様に）、まだ選択されておらず、まだ選択されていないすべての属性値の間で最多の出現回数を有する、属性の属性値を選択する。ドメイン属性インデックス内で最少の数の相異なる値を有する属性は、サンプリングされたデータベースの中でも少数の相異なる値を有することが可能である。つまり、平均でその属性からの値は、その他の属性からの値よりも、サンプリングされたデータベースエントリの多くに合致する確率がより高いことが可能である。同様に、ドメイン属性インデックスの中でより多く出現する値は、サンプリングされたデータベースの中でもより頻繁に出現することが可能である。つまり、より多く出現する値を使用してデータベースをサンプリングすることにより、データベースエントリのより多くが取り出されることが可能である。
【００１７】
一実施形態では、探索システムは、サンプリング停止基準を適用して、サンプリングされるデータベースのサンプリングを終了する。データベースの徹底的なサンプリングは、可能であるが、データベースに重い負荷を課し、データベースのＷｅｂサイトが、データベースに余りにも頻繁にアクセスするユーザを締め出す可能性がある。探索システムは、最大クエリ回数、または最大時間に基づく絶対的なサンプリング停止基準を使用することもできる。代替として、探索システムは、クエリ結果に基づいてサイトレベルインデックスに追加された新たなコンテンツの量で示される、最近数回のサンプリングクエリの限界価値（ｍａｒｇｉｎａｌ  ｖａｌｕｅ）に基づく、相対的なサンプリング停止基準を使用することもできる。探索システムは、絶対的なサンプリング停止基準と相対的なサンプリング停止基準の組み合わせを使用することもできる。例えば、探索システムは、１０００回のクエリの後、または限界価値が閾値を下回った場合のいずれか先に生じた方で、停止することができる。
【００１８】
図１は、一実施形態における探索システムのコンポーネントを示すブロック図である。Ｗｅｂデータベース群１０１が、通信リンク１０２を介して探索システム１１０に接続される。探索システムは、クエリ生成コンポーネント１１１と、構造化クエリ構築コンポーネント１１２と、非構造化クエリ構築コンポーネント１１３と、ドメイン属性インデックス生成コンポーネント１１４と、クエリ選択コンポーネント１１５と、サイトレベルインデックス更新コンポーネント１１６と、ドメインレベルインデックス更新コンポーネント１１７とを含む。また、探索システムは、ドメインレベルインデックス１２１を含み、各データベースに関して、サイトレベルインデックス１２２を含むドメイン属性インデックス１２０も含む。また、探索システムは、対応テーブル１２３も含む。ドメインレベルインデックスは、属性値をデータベース群およびデータベース群の中のサイト属性にマップする値−属性インデックスである。サイトレベルインデックスは、データベースのサイト属性を対応する相異なる値にマップする属性−値インデックスである。対応テーブルは、ドメイン属性を各データベースのサイト属性にマップする。サイト属性は、ドメイン属性にマップされ、その逆も同様であるため、何かがサイト属性にマップされる場合はいつでも、その何かは、直接にマップされることも、ドメイン属性を介して間接的にマップされることも可能であり、ドメイン属性に関してもその逆が該当することが当業者には認められよう。クエリ生成コンポーネントは、ユーザクエリを受け取り、そのクエリが構造化されている、または構造化されていないかを判定し、構造化クエリ構築コンポーネントまたは非構造化クエリ構築コンポーネントを適宜、呼び出す。構造化クエリ構築コンポーネントは、構造化クエリの属性および属性値に基づいてクエリを生成する。非構造化クエリ構築コンポーネントは、クエリの属性項目および属性値項目を識別し、その属性項目と属性値項目の組み合わせに基づいてクエリを生成する。クエリ生成コンポーネントは、データベース群を選択し、それらのデータベース群にクエリを送信する。ドメイン属性インデックス生成コンポーネントは、ドメインレベルインデックスおよびサイトレベルインデックスを含むドメイン属性インデックスの生成を制御する。ドメイン属性インデックス生成コンポーネントは、クエリ選択コンポーネントを呼び出して、データベースをサンプリングするために使用されるクエリを生成する。ドメイン属性インデックス生成コンポーネントは、サイトレベルインデックス更新コンポーネントを呼び出して、サンプリングされたデータベースに対するサイトレベルインデックスを更新する。ドメイン属性インデックス生成コンポーネントは、ドメインレベルインデックス更新コンポーネントを呼び出して、サイトレベルインデックスの情報に基づいてドメインレベルインデックスを更新する。
【００１９】
探索システムが実施されるコンピューティングデバイスは、中央処理装置、メモリ、入力デバイス群（例えば、キーボードおよびポインティングデバイス群）、出力デバイス群（例えば、ディスプレイデバイス群）、および記憶装置群（例えば、ディスクドライブ群）を含むことが可能である。メモリおよび記憶装置群は、探索システムを実施する命令を含むことが可能なコンピュータ可読媒体である。さらに、データ構造およびメッセージ構造が、通信リンク上の信号などのデータ伝送媒体を介して、格納される、または伝送されることが可能である。インターネット、ローカルエリアネットワーク、ワイドエリアネットワーク、またはポイントツーポイントダイヤルアップ接続などの、様々な通信リンクを使用することができる。探索システムは、Ｗｅｂデータベース群以外のデータベース群に対して使用することもできることが当業者には認められよう。例えば、データベース群は、メタサーチャを介して探索されることが可能な異なる組織（例えば、企業または政府機関）のデータベース群であることも可能である。
【００２０】
探索システムは、パーソナルコンピュータ、サーバコンピュータ、ハンドヘルドデバイスまたはラップトップデバイス、マルチプロセッサシステム、マイクロプロセッサベースのシステム、プログラマブル家庭用電化製品、ネットワークＰＣ（personal computer）、ミニコンピュータ、メインフレームコンピュータ、以上のシステムまたはデバイスのいずれかを含む分散コンピューティング環境などを含む、様々な動作環境において実施することができる。
【００２１】
探索システムは、１つまたは複数のコンピュータまたは他のデバイスによって実行されるプログラムモジュール群などの、コンピュータ実行可能命令の一般的な状況で説明することができる。一般に、プログラムモジュール群には、特定のタスクを実行する、または特定の抽象データ型を実装するルーチン、プログラム、オブジェクト、コンポーネント、データ構造などが含まれる。通常、プログラムモジュール群の機能は、様々な実施形態において、所望に応じて組み合わせることも、分散させることもできる。図示したデータ構造は、データを編成するのに使用することができるデータ構造のサンプルタイプに過ぎないことが当業者には認められよう。
【００２２】
図２は、一実施形態における対応テーブルを示す。対応テーブル２００（ドメイン−サイト属性マッピングとも呼ぶ）は、各ドメイン属性２０１を各データベースに関する対応するサイト属性にマップする。例えば、対応テーブルの行２０２は、著者ドメイン属性が、第１のデータベースの著者サイト属性、および第２のデータベースの「ａｕ」サイト属性に対応することを示す。行２０３は、フォーマットドメイン属性が、第１のデータベースのタイプサイト属性、および第２のデータベースのフォーマットサイト属性に対応することを示す。対応テーブルの生成は、参照により本明細書に組み込まれている、２００４年５月１４日に出願した「Ｗｅｂデータベース群のスキーママッチングのための方法およびシステム」という名称の米国特許出願において説明されている。
【００２３】
図３は、一実施形態におけるドメイン属性インデックスに関するサイトレベルインデックスを示す。サイトレベルインデックス３００は、Ｗｅｂサイトのデータベースに関する各サイト属性に関してエントリを有する。この例では、サイト属性に関するエントリは、テーブル内の行で表される。各エントリは、そのサイト属性のそれぞれの相異なる値に関するサブエントリをデータベース内に含む。また、サブエントリは、データベースをサンプリングした際に属性値が見つかった出現の頻度または回数も示すことが可能である。例えば、著者サイト属性に関するエントリは、Ｒｏｗｌｉｎｇという属性値に関するサブエントリ、およびＴｏｌｋｉｅｎという属性値に関する別のサブエントリを有する。書名サイト属性に関するエントリは、ｓｏｒｃｅｒｅｒ（魔法使い）という属性値に関するサブエントリ、およびｒｉｎｇ（指輪）という属性値に関するサブエントリを含む。
【００２４】
図４は、一実施形態におけるドメイン属性インデックスに関するドメインレベルインデックスを示す。ドメイン属性インデックス４００は、サイトレベルインデックス内のそれぞれの相異なる属性値に関するエントリ、ならびにその属性値を、その値を含むデータベース群およびサイト属性にマップするサブエントリを含む。この例では、エントリ４０１は、Ｔｏｌｋｉｅｎという属性値に対応し、Ｔｏｌｋｉｅｎ属性値が、第１のデータベースの書名サイト属性、第１のデータベースの著者サイト属性、および第２のデータベースの書名サイト属性の中で見つかったことを示すサブエントリを有する。エントリ４０２は、Ｈｏｕｇｈｔｏｎという属性値に対応し、Ｈｏｕｇｈｔｏｎ属性値が、第１のデータベースの出版元サイト属性、第２のデータベースの出版元サイト属性、第２のデータベースの著者サイト属性、および第２のデータベースの書名サイト属性の中で見つかったことを示すサブエントリを有する。
【００２５】
図５は、一実施形態におけるクエリ生成コンポーネントの出力を示す流れ図である。このコンポーネントは、構造化されていることも、構造化されていないことも可能なクエリを受け取り、様々なデータベースに送信されるクエリを生成する。判定ブロック５０１で、受け取られたクエリが構造化されている場合、コンポーネントは、ブロック５０２に進み、構造化されていない場合、コンポーネントは、ブロック５０３に進む。ブロック５０２で、コンポーネントは、構造化クエリ構築コンポーネントを呼び出して、データベース群に対するクエリを生成する。ブロック５０３で、コンポーネントは、非構造化クエリ構築コンポーネントを呼び出して、非構造化クエリからクエリを構築する。ブロック５０４で、コンポーネントは、データベース選択コンポーネントを呼び出して、クエリが送信されるべきデータベース群を選択する。コンポーネントは、クエリをドメイン属性から、選択されたデータベース群のサイト属性に変換することもできる。ブロック５０５で、コンポーネントは、最も望ましい結果をより早く生成することができる順序でクエリを送信することができるように、データベース群を順序付ける。例えば、データベース群は、いずれのデータベース群が、ある属性値に関連する最も多くのエントリを有する可能性があるかに基づき、順序付けることができる。また、コンポーネントは、論理ＯＲで属性と属性値を結合することにより、データベースに対するクエリを結合することもできる。その後、コンポーネントは、完了する。
【００２６】
図６は、一実施形態における非構造化クエリ構築コンポーネントの処理を示す流れ図である。ブロック６０１で、このコンポーネントは、クエリから、属性項目および属性値項目を識別するコンポーネントを呼び出す。ブロック６０２〜６０６で、コンポーネントは、属性項目と属性値のペアを選択してループし、そのペアに関するクエリを構築する。ブロック６０２で、コンポーネントは、次の属性項目を選択する。判定ブロック６０３で、すべての属性項目が既に選択済みである場合、コンポーネントは戻り、選択済みではない場合、コンポーネントは、ブロック６０４に進む。ブロック６０４で、コンポーネントは、次の属性値項目を選択する。判定ブロック６０５で、すべての属性値項目が既に選択済みである場合、コンポーネントは、ブロック６０２にループして次の属性項目を選択し、選択済みではない場合、コンポーネントは、ブロック６０６に進む。ブロック６０６で、コンポーネントは、選択された属性項目に対応するドメイン属性を選択された属性値項目に設定することにより、クエリを構築する。次に、コンポーネントは、ブロック６０４にループして次の属性値項目を選択する。
【００２７】
図７は、一実施形態における属性項目および属性値項目を識別するコンポーネントの処理を示す流れ図である。ブロック７０１で、このコンポーネントは、属性項目のリスト、および属性値項目のリストを初期化して空にする。ブロック７０２〜７０７で、コンポーネントは、クエリの各項目を選択してループし、その項目が属性項目であるか、属性値項目であるか、あるいはその両方であるかを判定する。ブロック７０２で、コンポーネントは、クエリの次の項目を選択する。判定ブロック７０３で、クエリのすべての項目が既に選択済みである場合、コンポーネントは戻り、選択済みではない場合、コンポーネントは、ブロック７０４に進む。判定ブロック７０４で、選択された項目が属性値項目であった場合、コンポーネントは、ブロック７０５に進み、属性値項目ではなかった場合、コンポーネントは、ブロック７０６に進む。項目は、その項目が、ドメインレベルインデックスのエントリの中にある場合、属性値項目である。ブロック７０５で、コンポーネントは、選択された項目を属性値項目のリストに追加し、次に、ブロック７０６に進む。判定ブロック７０６で、選択された項目が属性項目であった場合、コンポーネントは、ブロック７０７に進み、属性項目ではなかった場合、コンポーネントは、ブロック７０２にループしてクエリの次の項目を選択する。項目は、その項目が、ドメインレベルインデックスのエントリのいずれか１つのエントリ内のサブエントリの中にある場合、属性項目である。ブロック７０７で、コンポーネントは、選択された項目を属性項目のリストに追加し、次に、ブロック７０２にループしてクエリの次の項目を選択する。
【００２８】
図８は、一実施形態におけるクエリを送信するためのデータベース群を選択するコンポーネントの処理を示す流れ図である。このコンポーネントは、そのデータベースが、ドメインレベルインデックス内のクエリの属性値に関するエントリのサブエントリの中にあるかどうかに基づき、データベース群を選択する。ブロック８０１で、このコンポーネントは、次の構築済みのクエリを選択する。判定ブロック８０２で、すべてのクエリが既に選択済みである場合、コンポーネントは戻り、選択済みではない場合、コンポーネントは、ブロック８０３に進む。ブロック８０３で、コンポーネントは、選択されたクエリの属性に関するエントリ内のサブエントリを選択する。判定ブロック８０４で、すべてのそのようなサブエントリが選択済みである場合、コンポーネントは、ブロック８０１にループして次のクエリを選択し、選択済みではない場合、コンポーネントは、ブロック８０５に進む。ブロック８０５で、コンポーネントは、そのクエリに関してデータベース、属性、および属性値のトリプレット（ｔｒｉｐｌｅｔ）を生成し、次に、ブロック８０３にループして次のサブエントリを選択する。トリプレットは、データベースに送信されるべきクエリを示す。また、コンポーネントは、ドメイン属性をデータベースの対応するサイト属性に変換することもできる。
【００２９】
図９は、一実施形態におけるドメイン属性インデックス生成コンポーネントの処理を示す図である。この実施形態では、このコンポーネントは、すべての属性と属性値の組み合わせに関するクエリを残らず（ｅｘｈａｕｓｔｉｖｅｌｙ）生成し、属性および属性値をランダムに選択する。ブロック９０１〜９０４は、異なるサンプリング基準（例えば、属性適応サンプリング）およびサンプリング停止基準を実施するコンポーネントによって置き換えられることが可能である。ブロック９０１で、コンポーネントは、次のドメイン属性を選択する。判定ブロック９０２で、すべてのドメイン属性が既に選択済みである場合、コンポーネントは、ブロック９８０に進み、選択済みではない場合、コンポーネントは、９０３に進む。ブロック９０３で、コンポーネントは、次の属性値を選択する。判定ブロック９０４で、すべての属性値が既に選択済みである場合、コンポーネントは、ブロック９０１に進み、選択済みではない場合、コンポーネントは、ブロック９０５に進む。ブロック９０５で、コンポーネントは、選択されたドメイン属性（対応するサイト属性にマップされた）、および選択された属性値に基づき、サンプリングクエリを送信する。ブロック９０６で、コンポーネントは、サンプリング結果のエントリを抽出する。例えば、コンポーネントは、最初の１０のエントリ、または他の何らかの数のエントリを抽出することができる。ブロック９０７で、コンポーネントは、サイトレベルインデックス更新コンポーネントを呼び出して、サンプリングされたデータベースに対するサイトレベルインデックスを更新する。次に、コンポーネントは、ブロック９０３にループして、選択されたドメイン属性の次の属性値を選択する。ブロック９０８で、コンポーネントは、ドメインレベルインデックス更新コンポーネントを呼び出して、更新されたサイトレベルインデックスに基づいてドメインレベルインデックスを更新する。
【００３０】
図１０は、一実施形態におけるサイトレベルインデックス更新コンポーネントの処理を示す流れ図である。コンポーネントは、サンプリング結果を受け取り、サンプリング結果内のそれぞれの属性と属性値のペアを選択し、そのペアがサイトレベルインデックスに入っているかどうかを判定する。入っていない場合、コンポーネントは、そのペアをインデックスに追加する。入っている場合、コンポーネントは、既存のペアに関する頻度を更新する。ブロック１００１で、コンポーネントは、サンプリング結果の次のエントリを選択する。判定ブロック１００２で、すべてのエントリが既に選択済みである場合、コンポーネントは戻り、選択済みではない場合、コンポーネントは、ブロック１００３に進む。ブロック１００３で、コンポーネントは、選択されたエントリの次の属性を選択する。判定ブロック１００４で、選択されたエントリのすべての属性が既に選択済みである場合、コンポーネントは、ブロック１００１にループして次のエントリを選択し、選択済みではない場合、コンポーネントは、ブロック１００５に進む。判定ブロック１００５で、選択された属性、およびその属性の属性値が、既にサイトレベルインデックスの中のペアである場合、コンポーネントは、ブロック１００６に進み、サイトレベルインデックスの中のペアではない場合、コンポーネントは、ブロック１００７に進む。ブロック１００７で、コンポーネントは、属性と属性値のペアをサイトレベルインデックスに追加し、次に、ブロック１００６に進む。ブロック１００６で、コンポーネントは、属性と属性値のペアに関する頻度をサイトレベルインデックスの中で更新し、次に、ブロック１００３にループして、サンプリング結果の選択されたエントリに関する次の属性を選択する。
【００３１】
探索システムの特定の諸実施形態を例示のために本明細書で説明してきたが、本発明の趣旨および範囲を逸脱することなく、様々な変形を行うことができることが当業者には認められよう。したがって、本発明は、添付の特許請求の範囲による以外は、限定されない。
【図面の簡単な説明】
【００３２】
【図１】一実施形態における探索システムのコンポーネントを示すブロック図である。
【図２】一実施形態における対応テーブルの図である。
【図３】一実施形態におけるドメイン属性インデックスに関するサイトレベルインデックスを示す図である。
【図４】一実施形態におけるドメイン属性インデックスに関するドメインレベルインデックスを示す図である。
【図５】一実施形態におけるクエリ生成コンポーネントの処理を示す流れ図である。
【図６】一実施形態における非構造化クエリ構築コンポーネントの処理を示す流れ図である。
【図７】一実施形態における属性項目および属性値項目を識別するコンポーネントの処理を示す流れ図である。
【図８】一実施形態におけるクエリを送信するためのデータベース群を選択するコンポーネントの処理を示す流れ図である。
【図９】一実施形態におけるドメイン属性インデックス生成コンポーネントの処理を示す流れ図である。
【図１０】一実施形態におけるサイトレベルインデックス更新コンポーネントの処理を示す流れ図である。
【符号の説明】
【００３３】
１０１  Ｗｅｂデータベース群
１０２  通信リンク
１１０  探索システム
１１１  クエリ生成コンポーネント
１１２  構造化クエリ構築コンポーネント
１１３  非構造化クエリ構築コンポーネント
１１４  ドメイン属性インデックス生成コンポーネント
１１５  クエリ選択コンポーネント
１１６  サイトレベルインデックス更新コンポーネント
１１７  ドメインレベルインデックス更新コンポーネント
１２０  ドメイン属性インデックス
１２１  ドメインレベルインデックス
１２２  サイトレベルインデックス
１２３  対応テーブル
【図１】
2006012125.tif 000003
【図２】
2006012125.tif 000004
【図３】
2006012125.tif 000005
【図４】
2006012125.tif 000006
【図５】
2006012125.tif 000007
【図６】
2006012125.tif 000008
【図７】
2006012125.tif 000009
【図８】
2006012125.tif 000010
【図９】
2006012125.tif 000011
【図１０】
2006012125.tif 000012
【外国語明細書】
2006012125000001.pdf