検索のためのユーザ定義の関連性ランク付け
本明細書では、とりわけ、検索エンジンがユーザ定義の関連性関数を利用できるようにする技術について詳述する。この技術の一手法では、ユーザ定義の関連性関数を適用する方法について述べる。この手法では、複合的な検索クエリが単純な演算子に分解される。単純な演算子は、ユーザ定義の関連性関数と関連付けられる。検索クエリと合致する文書が取り出され、ユーザ定義の関連性関数を使用して文書のランクが計算される。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、検索のためのユーザ定義の関連性ランク付けに関する。
【背景技術】
【０００２】
デジタル情報の根本的な問題の１つは、所与の時点で、最も関連性のある情報を見つけるためにどのように膨大なデータを効果的にソートするかである。検索エンジンは、この課題に対処するために、関連性またはランク付け関数を備える。これらの関連性関数を使用して、検索基準を必要とする文書に異なる重みを与える。次いで、割り当てられた重みまたはランクを使用して、例えばある順序で結果を表示することによって、情報のプールをさらに操作することができる。
【０００３】
多くの検索エンジン、特にデータベースとの対話に使用される検索エンジンは、ｔｆ−ｉｄｆ重み方式の何らかの変形を使用するが、この方式では、特定の文書における用語の発生頻度が、逆文書頻度（その用語が文書のプール中でどれくらいの頻度で出現するかの尺度）に対して重み付けされる。異なる検索エンジンが、この方式の異なる変形を実施することになり、個々の検索エンジンは、その特定の関連性関数を使用するように最適化される。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
本明細書では、とりわけ、検索エンジンがユーザ定義の関連性関数を利用できるようにする技術について詳述する。
【課題を解決するための手段】
【０００５】
この技術の一手法では、ユーザ定義の関連性関数を適用する方法について述べる。この手法では、複合的な検索クエリが単純な演算子に分解される。単純な演算子は、ユーザ定義の関連性関数と関連付けられる。検索クエリと合致する文書が取り出され、ユーザ定義の関連性関数を使用して文書のランクが計算される。
【０００６】
この技術の別の手法では、コンピュータ実行可能命令を有するコンピュータ可読媒体について述べる。この手法では、ユーザ定義のランク付け関数が受け取られ、検索クエリが受け取られる。検索クエリは、いくつかの単純な演算に分解される。これらの単純な演算はそれぞれ、関連性関数と関連付けられる。より単純な演算に対応するいくつかの結果が取り出され、関連する関連性関数を使用してこれらの各結果のランクが計算される。
【０００７】
この技術の別の手法では、バスとプロセッサとメモリとデータ記憶デバイスとを有するシステムが、複合的な検索クエリを受け取るように構成される。システムはさらに、この複合的な検索クエリをいくつかのより単純な演算に解析するように構成される。システムはまた、これらのより単純な演算に対応する結果を取り出し、ユーザ定義の関連性関数を適用することによって各結果のランクを計算するように構成される。
【０００８】
「課題を解決するための手段」は、以下に「発明を実施するための形態」でさらに述べる概念の精選を、単純化した形で紹介するために提供するものである。この「課題を解決するための手段」は、特許請求する主題の鍵となる特徴または必須の特徴を識別するものとはせず、また、特許請求する主題の範囲を限定するために使用されるものともしない。
【０００９】
本明細書に組み込まれその一部をなす添付の図面は実施形態を示し、記述と共に、特許請求する主題の原理を説明する働きをする。
【図面の簡単な説明】
【００１０】
【図１】実施形態を実施できる例示的なコンピューティングシステムのブロック図である。
【図２】実施形態を実施できる例示的なデータベーステーブルの図である。
【図３】一実施形態による、ユーザ定義の関連性関数を適用する方法のフローチャートである。
【図４Ａ】一実施形態による例示的なデータベースクエリの図である。
【図４Ｂ】一実施形態による検索ツリーを描いた図である。
【図４Ｃ】一実施形態による中間検索ツリーを描いた図である。
【図４Ｄ】一実施形態によるクエリツリーを描いた図である。
【発明を実施するための形態】
【００１１】
次に、いくつかの実施形態を詳細に参照する。代替実施形態に関して主題を述べるが、これらは、特許請求する主題をこれらの実施形態に限定するものとはしないことは理解されるであろう。反対に、特許請求する主題は、代替、修正、および均等物をカバーするものとし、これらの代替、修正、および均等物は、添付の特許請求の範囲によって定義される特許請求する主題の趣旨および範囲に含めることができる。
【００１２】
さらに、以下の詳細な記述では、特許請求する主題の完全な理解を提供するために多くの具体的詳細を示す。しかし、これらの具体的詳細がなくても、あるいはその均等物を用いても実施形態を実現できることは、当業者には理解されるであろう。他の場合では、主題の態様および特徴を不必要に曖昧にしないために、周知の方法、手順、コンポーネント、および回路については詳細に述べていない。
【００１３】
以下の詳細な記述の一部については、方法の点から提示および考察する。この方法のステップおよび順序付けを、この方法の動作を記述する本明細書中の図（例えば図３）に開示するが、このようなステップおよび順序付けは例である。実施形態は、他の様々なステップを、または本明細書中の図のフローチャートに列挙するステップの変形を、本明細書に図示および記述する以外の順序で実施するのにもよく適する。
【００１４】
詳細な記述のいくつかの部分は、コンピュータメモリ上で実施できるデータビットに対する操作の、手順、ステップ、論理ブロック、処理、および他の象徴的表現の点から提示する。これらの記述および表現は、データ処理技術分野の当業者によって、その作業の実体を他の当業者に最も効果的に伝えるのに使用される手段である。手順、コンピュータ実行ステップ、論理ブロック、プロセスなどは、本明細書では、また一般には、所望の結果に至る首尾一貫した一連のステップまたは命令と考えられる。ステップは、物理的量の物理的操作を必要とするステップである。必須ではないが通常、これらの量は、コンピュータシステム中で記憶、転送、結合、比較、および他の方法によって操作されることが可能な、電気信号または磁気信号の形をとる。これらの信号をビット、値、要素、記号、文字、用語、数字などとして言及することが、主に一般使用の理由で、しばしば好都合であることがわかっている。
【００１５】
しかし、これらおよび類似の用語はすべて、適切な物理的量に関連付けられるべきであって、これらの量に適用される好都合なラベルに過ぎないことに留意されたい。以下の考察から明らかなように別段の指定がない限り、全体を通して、「アクセスする」、「書く」、「含む」、「記憶する」、「伝送する」、「横断する」、「関連付ける」、「識別する」などの用語を利用した考察は、コンピュータシステムのレジスタおよびメモリ内の物理的（電子的）量として表されるデータを操作して、コンピュータシステムメモリまたはレジスタ内、あるいは他のそのような情報記憶、伝送、または表示デバイス内の物理的量として同様に表される他のデータに変換するコンピュータシステムまたは同様の電子計算デバイスの、アクションおよびプロセスに言及することを理解されたい。
【００１６】
コンピューティングシステム環境１０などのコンピューティングデバイスは、通常、少なくとも何らかの形のコンピュータ可読媒体を備える。コンピュータ可読媒体は、コンピューティングデバイスによってアクセス可能な任意の利用可能な媒体とすることができる。限定ではなく例として、コンピュータ可読媒体は、コンピュータ記憶媒体および通信媒体を含むことができる。コンピュータ記憶媒体は、コンピュータ可読命令、データ構造、プログラムモジュール、または他のデータなどの情報を記憶するための任意の方法または技術で実現された、揮発性と不揮発性、取外し可能と取外し不可能の媒体を含む。コンピュータ記憶媒体は、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、フラッシュメモリ、または他のメモリ技術、ＣＤ−ＲＯＭ、デジタル多用途ディスク（ＤＶＤ）、または他の光学記憶装置、磁気カセット、磁気テープ、磁気ディスク記憶装置、または他の磁気記憶デバイス、あるいは、所望の情報を記憶するのに使用できコンピューティングデバイスによってアクセスできる他の任意の媒体を含むが、これらに限定されない。通信媒体は通常、コンピュータ可読命令、データ構造、プログラムモジュール、または他のデータを、搬送波や他のトランスポート機構などの被変調データ信号に組み入れるものであり、任意の情報送達媒体を含む。用語「被変調データ信号」は、信号中の情報を符号化するようにしてその特性の１つまたは複数が設定または変更される信号を意味する。限定ではなく例として、通信媒体は、有線ネットワークまたは直接有線接続などの有線媒体と、音響、無線周波数、赤外線などのワイヤレス媒体および他のワイヤレス媒体とを含む。以上のいずれかの組合せも、コンピュータ可読媒体の範囲に含めるべきである。
【００１７】
いくつかの実施形態については、１つまたは複数のコンピュータまたは他のデバイスによって実行されるプログラムモジュールなどのコンピュータ実行可能命令の一般的なコンテキストで述べることができる。一般に、プログラムモジュールは、特定のタスクを実施するかまたは特定の抽象データ型を実装するルーチン、プログラム、オブジェクト、コンポーネント、データ構造などを含む。通常、プログラムモジュールの機能は、様々な実施形態で望むように結合または分散させることができる。
【００１８】
基本的なコンピューティングデバイス
図１を参照すると、実施形態を実施するための例示的なシステムが、コンピューティングシステム環境１０などの汎用コンピューティングシステム環境を含む。コンピューティングシステム環境１０は通常、その最も基本的な構成では、少なくとも１つの処理ユニット１２と、メモリ１４とを備える。コンピューティングシステム環境の厳密な構成およびタイプに応じて、メモリ１４は、揮発性（ＲＡＭなど）、不揮発性（ＲＯＭ、フラッシュメモリなど）、またはこの２つの何らかの組合せとすることができる。この最も基本的な構成は、図１では破線１６で示されている。加えて、コンピューティングシステム環境１０は、追加の機構／機能を有することもできる。例えば、コンピューティングシステム環境１０は、追加の記憶装置（取外し可能および／または取外し不可能）を備えることができ、これらは磁気または光学のディスクまたはテープを含むが、これらに限定されない。このような追加の記憶装置は、図１では、取外し可能記憶装置１８および取外し不可能記憶装置２０で示されている。コンピュータ記憶媒体は、コンピュータ可読命令、データ構造、プログラムモジュール、または他のデータなどの情報を記憶するための任意の方法または技術で実現された、揮発性と不揮発性、取外し可能と取外し不可能の媒体を含む。メモリ１４、取外し可能記憶装置１８、および取外し不可能記憶装置２０はすべて、コンピュータ記憶媒体の例である。
【００１９】
コンピューティングシステム環境１０はまた、コンピューティングシステム環境１０が他のデバイスと通信できるようにする通信接続２２を備えることもできる。通信接続２２は、通信媒体の例である。図示の例では、コンピューティングシステム環境１０が通信接続２２を介してデータベース３０と通信するのが示されている。データベース３０の性質および内容は、種々の実施形態にわたって変わる場合がある。さらに、いくつかの実施形態では、データベース３０は、例えば取外し可能記憶装置１８および／または取外し不可能記憶装置２０内に実装された、内部データベースとすることができる。
【００２０】
コンピューティングシステム環境１０はまた、キーボード、マウス、ペン、音声入力デバイス、タッチ入力デバイスなど、入力デバイス（複数可）２４を有することもできる。また、表示装置、スピーカ、プリンタなど、出力デバイス（複数可）２６を備えることもできる。本明細書で論じる特定の実施形態では、タッチ入力デバイスを、表示装置、例えばタッチスクリーンと組み合わせる。これらのデバイスはすべて当技術分野で周知であり、ここで詳細に論じる必要はない。
【００２１】
ユーザ定義の関連性関数
関連性関数は検索エンジンの必要かつ貴重な部分だが、単一の関連性関数があらゆる状況に適するわけではないかもしれない。以下の実施形態で述べるように、検索エンジンによって適用されている関連性関数をユーザが修正できる検索エンジンを有することは、価値があるであろう。さらに、いくつかの実施形態では、ユーザは、ユーザの特定の必要性をよりよく反映するよう検索エンジンを調整するために、関連性関数のいくらかまたはすべてを完全に置き換えることができる場合もある。
【００２２】
したがって、以下の実施形態では、検索エンジンと共に使用するためのランク付け関数をユーザが指定できるようにする手法について述べる。いくつかの実施形態では、これは、関連性関数の基本的な構成単位、例えばマルチウェイマージ結合論理演算子(multiway merge join logical operators)を、ランク付け関数の書き手に公開することによって達成される。
【００２３】
データベーステーブル
次に図２を参照すると、一実施形態により、例示的なデータベーステーブル２００が示されている。具体的な列挙された特徴および要素を組み込むものとしてデータベーステーブル２００を示すが、実施形態は、追加の、より少ない、または異なる特徴または要素を含む適用例にもよく適することを理解されたい。特に、２つの列だけを含む単純なテーブルとしてデータベーステーブル２００を示すが、実施形態は、幅広い検索タイプおよびデータタイプにわたる適用例に適することを理解されたい。
【００２４】
データベーステーブル２００は、いくつかのデータベース行またはエントリ、例えば行２１０から２６０を含むものとして示されている。各データベース行は、文書キー列、例えばｄｏｃｋｅｙ２１２を含み、これは、その行に記憶された文書に対する一意の識別子を含む。各データベース行はまた、文書列、例えばｄｏｃｕｍｅｎｔ２１４を含み、これは、その特定のｄｏｃｋｅｙに対応する文書の文書テキストを含む。図示の実施形態では、複数の文書列エントリが複数の用語を含むものとして示されており、これらを使用して以下にさらに他の例を示す。
【００２５】
関連性関数
種々の実施形態で、種々のタイプのクエリまたは検索が受け入れられる。例えば、一実施形態では、ブール検索、例えばＡＮＤ、ＯＲ、またはＡＮＤ ＮＯＴなどのブール論理演算子を使用して用語を組み合わせる検索がサポートされる。別の実施形態では、ベクトル指定、例えば用語のいくつかまたはすべてに異なる重みを割り当てて複数の用語を検索することがサポートされる。別の実施形態、例えばウェブ検索では、返される検索文書の最終的なランク付けは、文書に関連する外部考慮事項、例えばメタデータに、部分的に依存することがある。別の実施形態では、他の検索手法が利用される。
【００２６】
多くの適用例では、特定の検索エンジンに組み込まれた関連性関数にユーザが依拠するのではなく、検索エンジンによって適用される関連性関数をユーザが操作または修正できることが有利である。例えば、ユーザは、異なる関連性関数を異なるシナリオまたはデータセットに適用することを選択することができ、あるいは、検索結果に適用されるランク付けを改変して何らかの望ましい基準を満たすために、ランク付け関数を修正することができる。この操作する自由は、ユーザに利点をもたらす。
【００２７】
いくつかの実施形態では、ユーザは、利用可能な異なる演算子に対応する、複数のランク付け関数を供給することを選択することができる。例えば、ブール論理演算子を扱うとき、ユーザは、ＡＮＤ演算子とＯＲ演算子に対して別々の関連性関数を供給することができる。さらに、いくつかのこのような実施形態では、ユーザ提供の関連性関数によってオーバライドされない演算子と共に使用されるように、検索エンジンによってデフォルトの関連性関数を供給することができる。
【００２８】
ユーザ定義の関連性関数の適用
次に図３を参照すると、一実施形態により、ユーザ定義の関数を適用する方法のフローチャート３００が示されている。フローチャート３００には特定のステップを開示するが、このようなステップは例である。すなわち、実施形態は、様々な他の（追加の）ステップを、またはフローチャート３００に列挙したステップの変形を実施するのにもよく適する。フローチャート３００中のステップは、提示したのと異なる順序で実施してもよいこと、および、フローチャート３００中のすべてのステップを実施しなくてもよいことを理解されたい。
【００２９】
ここでステップ３１０を参照すると、ユーザ指定のランク付け関数が受け取られる。種々の実施形態で、このような関連性関数を供給するための種々の方法が利用される。例えば、いくつかの実施形態では、ユーザは、プログラミング言語、例えばＴ−ＳＱＬで書かれた関連性関数を供給することができる。いくつかのこのような実施形態では、宣言言語、例えばＳＱＬまたはダイアレクト(dialect)が、ユーザ定義の関連性関数に使用される。また、種々の実施形態で、ランク付け関数の動作は変動する場合がある。例えば、一実施形態では、ランク付け関数は、ブール演算子ＡＮＤに適用される場合があり、ＴＦ−ＩＤＦ方式を検索結果に適用する場合がある。
【００３０】
次にステップ３２０を参照すると、クエリが分解される。いくつかの実施形態では、複合的なクエリが、より単純な演算子のツリーに分解される。いくつかの他の実施形態では、クエリが、いくつかのより単純な演算に分解される。例えば、一実施形態では、フルテキストクエリが、結合で接続されたいくつかの単純な演算を含むツリーに分離される。このような一実施形態では、結合のタイプは、単純な演算を接続する論理演算子に基づく。例えば、ＡＮＤは内部結合として扱われ、ＯＲは外部結合として扱われ、ＡＮＤ ＮＯＴは存在しないとして対処される。いくつかの実施形態では、より単純な演算はそれぞれ、同種の論理演算子、例えばＡＮＤまたはＯＲのみを含む。このような一実施形態では、同種の論理演算子に対するランク付け関数は可換として扱われる。
【００３１】
次にステップ３３０を参照すると、単純な演算がランク付け関数と関連付けられる。いくつかの実施形態では、単純な演算は、ユーザ供給のランク付け関数と関連付けることができる。いくつかの実施形態では、単純な演算を、ユーザ供給のランク付け関数が利用可能であればそれとリンクさせることができ、あるいはデフォルトのランク付け関数とリンクさせることができる。いくつかの実施形態では、ランク付け関数は、共通のシグネチャを有し、インデックスアクセスのための言語要素を基本ツールとして使用する。このような実施形態では、コンテキスト情報がランク付け関数に提供され、ランク付け関数は、インデックスアクセスを実施する要素に渡される。さらに、コンテキスト情報を他のテーブル値関数（ＴＶＦ）に渡して、ランク関数にとって重要だがインデックス中に存在しない情報を得ることができる。
【００３２】
次にステップ３４０を参照すると、検索が実施され、対応する結果が取り出される。種々の実施形態で、この検索および取出しの動作は、種々の方法で実施される。実施形態は、多くの異なる検索手法と結果取出し手法の両方を用いた適用例によく適することを理解されたい。いくつかの実施形態では、取り出された結果は、関連性関数が結果のランク付けを計算するのに必要な情報を含む。このような情報は、文書カウント、用語頻度、用語重み、および他の情報などの要素を含むことができる。いくつかの実施形態では、前述の分解された単純な演算を使用して、複数の検索が実施される。このような一実施形態では、コンテキスト情報を提供することにより、インデックスアクセス要素は、より単純な演算に対応する部分的なクエリに合致する行を取り出すことができる。
【００３３】
次にステップ３５０を参照すると、適切な１つまたは複数のランク付け関数に従って、取り出された結果がランク付けされる。いくつかの実施形態では、ランク付け関数は、集合体およびスカラユーザ定義関数など、標準的なＳＱＬプログラミングコンストラクトを使用して、各文書のスコアを計算する。
【００３４】
いくつかの実施形態では、クエリ分解、およびランク付け関数を単純な演算子に関連付けることは、コンパイル段階の間に実施され、検索、取出し、およびランク付けは、ランタイム段階の間に実施される。他の実施形態では、これらの動作のタイミングは変動する場合がある。
【００３５】
ストリーミングテーブル値関数
前述の方法を実施するいくつかの実施形態では、ストリーミングテーブル値関数（ＳＴＶＦ）を使用してインデックスアクセスが提供される。このような一実施形態では、ＳＴＶＦの使用は、いくつかの利点をもたらす。これらの利点の中には、反転インデックスにわたるマルチウェイＡＮＤおよびＯＲのための効率的な実施、ならびに、効率的な反転があり、文書識別子が反転インデックス中で内部列であっても、出力は、文書識別子の小さい順にソートされる。他の実施形態では、他の検索結果順序付け、例えば関連性順を利用することができる。さらに、ＳＴＶＦの使用は、ユーザ要求に基づいて異なるレベルで圧縮解除することを可能にし、例えば、文書識別子圧縮解除の場合はレベル１での圧縮解除、あるいは発生圧縮解除の場合はレベル２での圧縮解除を可能にする。加えて、ＳＴＶＦの使用は、ランク付けに必要とされる情報、例えば文書カウント、用語頻度、用語重み、または列重みを、効率的に取り出すことを可能にする。さらに、ＳＴＶＦの使用は正確な濃度推定を可能にし、このことは、データベースクエリオプティマイザによる効果的な最適化を可能にする。
【００３６】
クエリの分解
次に図４Ａを参照すると、一実施形態により、例示的なデータベースクエリ４００が示されている。クエリ４００は、特定の定義された要素を組み込むものとして示されているが、実施形態は、追加の、より少ない、または異なる要素を含む適用例、あるいは異なる要素配置を特徴とする適用例にもよく適することを理解されたい。
【００３７】
クエリ４００は、図示の実施形態では、ＳＱＬデータベースに向けたフルテキストクエリとして示されている。この実施形態では、クエリ４００は、クエリが複数のより単純な演算に還元されるようにして構築されたいくつかの変換を経て、ユーザ供給のランク付け関数の包含を可能にする。
【００３８】
図示の実施形態では、Ｔは、テーブル２００などのデータベーステーブルである。ｄｏｃｕｍｅｎｔおよびｄｏｃｋｅｙは、データベーステーブル内の列である。検索ストリングは、図示の実施形態では「ａｐｐｌｅｓ ＡＮＤ ｏｒａｎｇｅｓ ＯＲ ｇｒａｐｅｓ ＡＮＤ ｐｅａｒｓ」である。ＣＯＮＴＡＩＮＳＴＡＢＬＥは、検索ストリングを適格とする行、ならびにこの検索ストリングに対する文書のランクを返す、Ｔ−ＳＱＬ ＴＶＦである。図示の実施形態では、このクエリは、ｄｏｃｕｍｅｎｔ列がキーワードａｐｐｌｅｓとｏｒａｎｇｅｓの両方、またはキーワードｇｒａｐｅｓとｐｅａｒｓの両方を含む、テーブルＴのすべての行およびそれらのランク値を返すように、検索エンジンに命令する。
【００３９】
一実施形態では、クエリは解析されバインドされる。解析およびバインドのプロセスの間、ＣＯＮＴＡＩＮＳＴＡＢＬＥ関数が識別され、フルテキストクエリコンパイラが呼び出されて検索ストリングが処理される。フルテキストクエリコンパイラは、検索ストリングを、クエリキーワードとそれらをバインドする論理演算子とを表すツリーに変換する。そのようなツリーの１つであるツリー４０１を、図４Ｂに示す。
【００４０】
ツリー４０１に示すように、クエリ４００からの検索ストリングが、ツリー構造に変換されている。ツリー４０１は、検索ストリングによって関連付けられるツリー要素を論理演算子がバインドするように構成されている。このようにして、ＯＲ４１０が、ＡＮＤ４２０をＡＮＤ４２５とバインドする。ＡＮＤ４２０は、ａｐｐｌｅｓ４３１をｏｒａｎｇｅｓ４３３とバインドし、ＡＮＤ４２５は、ｇｒａｐｅｓ４３５をｐｅａｒｓ４３７とバインドする。
【００４１】
いくつかの実施形態では、検索ストリングが単純化されたツリー構造に還元された後、ＡＮＤおよびＯＲ演算子など同種の論理演算子が識別される。いくつかのこのような実施形態では、単純な用語、例えばキーワードをバインドする同種の論理表現は、ＳＴＶＦとして実施されるマルチウェイスキップマージ結合演算子に変換される。このような一実施形態を、図４Ｃに中間ツリー４４１として示す。
【００４２】
中間ツリー４４１に示すように、ツリー４０１のＡＮＤ印字は、ＳＴＶＦとして実施されるマルチウェイスキップマージ結合演算子で置き換えられている。ＯＲ４５０は今や、要素４６０と４６５をバインドし、これらはそれぞれマルチウェイスキップマージ結合演算子である。
【００４３】
いくつかの実施形態では、クエリがこのようにして変換された後、システムは、適切な演算子に対してユーザから提供されたランク付け関数をロードすることになる。例えば、中間ツリー４４１を参照すると、システムは、ＡＮＤ演算子に対してユーザから提供されたランク付け関数をロードすることになる。ランク付け関数のコンパイル中に、システムは適宜、実際のマルチウェイマージ結合演算子を挿入することになる。いくつかの実施形態では、特定の演算子に対してユーザからランク付け関数が提供されない場合は、代わりにデフォルトのシステム提供の関数がロードされコンパイルされる。
【００４４】
次いで、ランク付け関数によって返されたランク値が、より高いレベルで、例えば図４ＣのＯＲ４５０のレベルで組み合わせられる。いくつかの実施形態では、この組合せは、デフォルトのシステム動作によって対処される。例えば、ＯＲ演算子の場合は、組み合わせられたランクを最大値として計算し、ＡＮＤ演算子の場合は最小値として計算する。他の実施形態では、ユーザは、ユーザ指定のランク関数と同様にして、ユーザ指定の組合せ関数を提供することができる。
【００４５】
図４Ｄに、一実施形態によりクエリツリー４７１を示す。クエリツリー４７１は、前述のような組合せ関数と共に、クエリ４００の最終状態を示す。図示の実施形態では、フルテキストクエリツリー中の非リーフノードが、関係演算子に、例えばＡＮＤの場合は内部結合、ＯＲの場合は外部結合、またはＡＮＤ ＮＯＴの場合は半結合に変換される。図示のように、ＯＲ４５０が外部結合４８５で置き換えられている。ランク付け関数４９０および４９５が、それぞれマルチウェイスキップマージ結合演算子４９２および４９７に対してロードされている。ブロック４８０が組合せ関数を示すが、ここでは、ランク付け関数４９０および４９５の返却ランク値の最大値として示されている。
【００４６】
いくつかの実施形態では、このクエリツリーは、ＳＱＬクエリ全体に組み込まれて、全体として最適化される。いくつかのこのような実施形態では、この最適化により、ユーザ定義のランク付け関数は、どんなに複雑であっても、ユーザ提供のクエリの一部であるかのような程度と同程度まで、システムによって最適化されることが確実になる。
【００４７】
構造上の特徴および／または方法上の行為に特有の言葉で主題について述べたが、添付の特許請求の範囲に定義する主題は、必ずしも前述の特定の特徴または行為に限定されないことを理解されたい。そうではなく、前述の特定の特徴および行為は、特許請求の範囲を実施する例示的な形として開示する。
【技術分野】
【０００１】
本発明は、検索のためのユーザ定義の関連性ランク付けに関する。
【背景技術】
【０００２】
デジタル情報の根本的な問題の１つは、所与の時点で、最も関連性のある情報を見つけるためにどのように膨大なデータを効果的にソートするかである。検索エンジンは、この課題に対処するために、関連性またはランク付け関数を備える。これらの関連性関数を使用して、検索基準を必要とする文書に異なる重みを与える。次いで、割り当てられた重みまたはランクを使用して、例えばある順序で結果を表示することによって、情報のプールをさらに操作することができる。
【０００３】
多くの検索エンジン、特にデータベースとの対話に使用される検索エンジンは、ｔｆ−ｉｄｆ重み方式の何らかの変形を使用するが、この方式では、特定の文書における用語の発生頻度が、逆文書頻度（その用語が文書のプール中でどれくらいの頻度で出現するかの尺度）に対して重み付けされる。異なる検索エンジンが、この方式の異なる変形を実施することになり、個々の検索エンジンは、その特定の関連性関数を使用するように最適化される。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
本明細書では、とりわけ、検索エンジンがユーザ定義の関連性関数を利用できるようにする技術について詳述する。
【課題を解決するための手段】
【０００５】
この技術の一手法では、ユーザ定義の関連性関数を適用する方法について述べる。この手法では、複合的な検索クエリが単純な演算子に分解される。単純な演算子は、ユーザ定義の関連性関数と関連付けられる。検索クエリと合致する文書が取り出され、ユーザ定義の関連性関数を使用して文書のランクが計算される。
【０００６】
この技術の別の手法では、コンピュータ実行可能命令を有するコンピュータ可読媒体について述べる。この手法では、ユーザ定義のランク付け関数が受け取られ、検索クエリが受け取られる。検索クエリは、いくつかの単純な演算に分解される。これらの単純な演算はそれぞれ、関連性関数と関連付けられる。より単純な演算に対応するいくつかの結果が取り出され、関連する関連性関数を使用してこれらの各結果のランクが計算される。
【０００７】
この技術の別の手法では、バスとプロセッサとメモリとデータ記憶デバイスとを有するシステムが、複合的な検索クエリを受け取るように構成される。システムはさらに、この複合的な検索クエリをいくつかのより単純な演算に解析するように構成される。システムはまた、これらのより単純な演算に対応する結果を取り出し、ユーザ定義の関連性関数を適用することによって各結果のランクを計算するように構成される。
【０００８】
「課題を解決するための手段」は、以下に「発明を実施するための形態」でさらに述べる概念の精選を、単純化した形で紹介するために提供するものである。この「課題を解決するための手段」は、特許請求する主題の鍵となる特徴または必須の特徴を識別するものとはせず、また、特許請求する主題の範囲を限定するために使用されるものともしない。
【０００９】
本明細書に組み込まれその一部をなす添付の図面は実施形態を示し、記述と共に、特許請求する主題の原理を説明する働きをする。
【図面の簡単な説明】
【００１０】
【図１】実施形態を実施できる例示的なコンピューティングシステムのブロック図である。
【図２】実施形態を実施できる例示的なデータベーステーブルの図である。
【図３】一実施形態による、ユーザ定義の関連性関数を適用する方法のフローチャートである。
【図４Ａ】一実施形態による例示的なデータベースクエリの図である。
【図４Ｂ】一実施形態による検索ツリーを描いた図である。
【図４Ｃ】一実施形態による中間検索ツリーを描いた図である。
【図４Ｄ】一実施形態によるクエリツリーを描いた図である。
【発明を実施するための形態】
【００１１】
次に、いくつかの実施形態を詳細に参照する。代替実施形態に関して主題を述べるが、これらは、特許請求する主題をこれらの実施形態に限定するものとはしないことは理解されるであろう。反対に、特許請求する主題は、代替、修正、および均等物をカバーするものとし、これらの代替、修正、および均等物は、添付の特許請求の範囲によって定義される特許請求する主題の趣旨および範囲に含めることができる。
【００１２】
さらに、以下の詳細な記述では、特許請求する主題の完全な理解を提供するために多くの具体的詳細を示す。しかし、これらの具体的詳細がなくても、あるいはその均等物を用いても実施形態を実現できることは、当業者には理解されるであろう。他の場合では、主題の態様および特徴を不必要に曖昧にしないために、周知の方法、手順、コンポーネント、および回路については詳細に述べていない。
【００１３】
以下の詳細な記述の一部については、方法の点から提示および考察する。この方法のステップおよび順序付けを、この方法の動作を記述する本明細書中の図（例えば図３）に開示するが、このようなステップおよび順序付けは例である。実施形態は、他の様々なステップを、または本明細書中の図のフローチャートに列挙するステップの変形を、本明細書に図示および記述する以外の順序で実施するのにもよく適する。
【００１４】
詳細な記述のいくつかの部分は、コンピュータメモリ上で実施できるデータビットに対する操作の、手順、ステップ、論理ブロック、処理、および他の象徴的表現の点から提示する。これらの記述および表現は、データ処理技術分野の当業者によって、その作業の実体を他の当業者に最も効果的に伝えるのに使用される手段である。手順、コンピュータ実行ステップ、論理ブロック、プロセスなどは、本明細書では、また一般には、所望の結果に至る首尾一貫した一連のステップまたは命令と考えられる。ステップは、物理的量の物理的操作を必要とするステップである。必須ではないが通常、これらの量は、コンピュータシステム中で記憶、転送、結合、比較、および他の方法によって操作されることが可能な、電気信号または磁気信号の形をとる。これらの信号をビット、値、要素、記号、文字、用語、数字などとして言及することが、主に一般使用の理由で、しばしば好都合であることがわかっている。
【００１５】
しかし、これらおよび類似の用語はすべて、適切な物理的量に関連付けられるべきであって、これらの量に適用される好都合なラベルに過ぎないことに留意されたい。以下の考察から明らかなように別段の指定がない限り、全体を通して、「アクセスする」、「書く」、「含む」、「記憶する」、「伝送する」、「横断する」、「関連付ける」、「識別する」などの用語を利用した考察は、コンピュータシステムのレジスタおよびメモリ内の物理的（電子的）量として表されるデータを操作して、コンピュータシステムメモリまたはレジスタ内、あるいは他のそのような情報記憶、伝送、または表示デバイス内の物理的量として同様に表される他のデータに変換するコンピュータシステムまたは同様の電子計算デバイスの、アクションおよびプロセスに言及することを理解されたい。
【００１６】
コンピューティングシステム環境１０などのコンピューティングデバイスは、通常、少なくとも何らかの形のコンピュータ可読媒体を備える。コンピュータ可読媒体は、コンピューティングデバイスによってアクセス可能な任意の利用可能な媒体とすることができる。限定ではなく例として、コンピュータ可読媒体は、コンピュータ記憶媒体および通信媒体を含むことができる。コンピュータ記憶媒体は、コンピュータ可読命令、データ構造、プログラムモジュール、または他のデータなどの情報を記憶するための任意の方法または技術で実現された、揮発性と不揮発性、取外し可能と取外し不可能の媒体を含む。コンピュータ記憶媒体は、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、フラッシュメモリ、または他のメモリ技術、ＣＤ−ＲＯＭ、デジタル多用途ディスク（ＤＶＤ）、または他の光学記憶装置、磁気カセット、磁気テープ、磁気ディスク記憶装置、または他の磁気記憶デバイス、あるいは、所望の情報を記憶するのに使用できコンピューティングデバイスによってアクセスできる他の任意の媒体を含むが、これらに限定されない。通信媒体は通常、コンピュータ可読命令、データ構造、プログラムモジュール、または他のデータを、搬送波や他のトランスポート機構などの被変調データ信号に組み入れるものであり、任意の情報送達媒体を含む。用語「被変調データ信号」は、信号中の情報を符号化するようにしてその特性の１つまたは複数が設定または変更される信号を意味する。限定ではなく例として、通信媒体は、有線ネットワークまたは直接有線接続などの有線媒体と、音響、無線周波数、赤外線などのワイヤレス媒体および他のワイヤレス媒体とを含む。以上のいずれかの組合せも、コンピュータ可読媒体の範囲に含めるべきである。
【００１７】
いくつかの実施形態については、１つまたは複数のコンピュータまたは他のデバイスによって実行されるプログラムモジュールなどのコンピュータ実行可能命令の一般的なコンテキストで述べることができる。一般に、プログラムモジュールは、特定のタスクを実施するかまたは特定の抽象データ型を実装するルーチン、プログラム、オブジェクト、コンポーネント、データ構造などを含む。通常、プログラムモジュールの機能は、様々な実施形態で望むように結合または分散させることができる。
【００１８】
基本的なコンピューティングデバイス
図１を参照すると、実施形態を実施するための例示的なシステムが、コンピューティングシステム環境１０などの汎用コンピューティングシステム環境を含む。コンピューティングシステム環境１０は通常、その最も基本的な構成では、少なくとも１つの処理ユニット１２と、メモリ１４とを備える。コンピューティングシステム環境の厳密な構成およびタイプに応じて、メモリ１４は、揮発性（ＲＡＭなど）、不揮発性（ＲＯＭ、フラッシュメモリなど）、またはこの２つの何らかの組合せとすることができる。この最も基本的な構成は、図１では破線１６で示されている。加えて、コンピューティングシステム環境１０は、追加の機構／機能を有することもできる。例えば、コンピューティングシステム環境１０は、追加の記憶装置（取外し可能および／または取外し不可能）を備えることができ、これらは磁気または光学のディスクまたはテープを含むが、これらに限定されない。このような追加の記憶装置は、図１では、取外し可能記憶装置１８および取外し不可能記憶装置２０で示されている。コンピュータ記憶媒体は、コンピュータ可読命令、データ構造、プログラムモジュール、または他のデータなどの情報を記憶するための任意の方法または技術で実現された、揮発性と不揮発性、取外し可能と取外し不可能の媒体を含む。メモリ１４、取外し可能記憶装置１８、および取外し不可能記憶装置２０はすべて、コンピュータ記憶媒体の例である。
【００１９】
コンピューティングシステム環境１０はまた、コンピューティングシステム環境１０が他のデバイスと通信できるようにする通信接続２２を備えることもできる。通信接続２２は、通信媒体の例である。図示の例では、コンピューティングシステム環境１０が通信接続２２を介してデータベース３０と通信するのが示されている。データベース３０の性質および内容は、種々の実施形態にわたって変わる場合がある。さらに、いくつかの実施形態では、データベース３０は、例えば取外し可能記憶装置１８および／または取外し不可能記憶装置２０内に実装された、内部データベースとすることができる。
【００２０】
コンピューティングシステム環境１０はまた、キーボード、マウス、ペン、音声入力デバイス、タッチ入力デバイスなど、入力デバイス（複数可）２４を有することもできる。また、表示装置、スピーカ、プリンタなど、出力デバイス（複数可）２６を備えることもできる。本明細書で論じる特定の実施形態では、タッチ入力デバイスを、表示装置、例えばタッチスクリーンと組み合わせる。これらのデバイスはすべて当技術分野で周知であり、ここで詳細に論じる必要はない。
【００２１】
ユーザ定義の関連性関数
関連性関数は検索エンジンの必要かつ貴重な部分だが、単一の関連性関数があらゆる状況に適するわけではないかもしれない。以下の実施形態で述べるように、検索エンジンによって適用されている関連性関数をユーザが修正できる検索エンジンを有することは、価値があるであろう。さらに、いくつかの実施形態では、ユーザは、ユーザの特定の必要性をよりよく反映するよう検索エンジンを調整するために、関連性関数のいくらかまたはすべてを完全に置き換えることができる場合もある。
【００２２】
したがって、以下の実施形態では、検索エンジンと共に使用するためのランク付け関数をユーザが指定できるようにする手法について述べる。いくつかの実施形態では、これは、関連性関数の基本的な構成単位、例えばマルチウェイマージ結合論理演算子(multiway merge join logical operators)を、ランク付け関数の書き手に公開することによって達成される。
【００２３】
データベーステーブル
次に図２を参照すると、一実施形態により、例示的なデータベーステーブル２００が示されている。具体的な列挙された特徴および要素を組み込むものとしてデータベーステーブル２００を示すが、実施形態は、追加の、より少ない、または異なる特徴または要素を含む適用例にもよく適することを理解されたい。特に、２つの列だけを含む単純なテーブルとしてデータベーステーブル２００を示すが、実施形態は、幅広い検索タイプおよびデータタイプにわたる適用例に適することを理解されたい。
【００２４】
データベーステーブル２００は、いくつかのデータベース行またはエントリ、例えば行２１０から２６０を含むものとして示されている。各データベース行は、文書キー列、例えばｄｏｃｋｅｙ２１２を含み、これは、その行に記憶された文書に対する一意の識別子を含む。各データベース行はまた、文書列、例えばｄｏｃｕｍｅｎｔ２１４を含み、これは、その特定のｄｏｃｋｅｙに対応する文書の文書テキストを含む。図示の実施形態では、複数の文書列エントリが複数の用語を含むものとして示されており、これらを使用して以下にさらに他の例を示す。
【００２５】
関連性関数
種々の実施形態で、種々のタイプのクエリまたは検索が受け入れられる。例えば、一実施形態では、ブール検索、例えばＡＮＤ、ＯＲ、またはＡＮＤ ＮＯＴなどのブール論理演算子を使用して用語を組み合わせる検索がサポートされる。別の実施形態では、ベクトル指定、例えば用語のいくつかまたはすべてに異なる重みを割り当てて複数の用語を検索することがサポートされる。別の実施形態、例えばウェブ検索では、返される検索文書の最終的なランク付けは、文書に関連する外部考慮事項、例えばメタデータに、部分的に依存することがある。別の実施形態では、他の検索手法が利用される。
【００２６】
多くの適用例では、特定の検索エンジンに組み込まれた関連性関数にユーザが依拠するのではなく、検索エンジンによって適用される関連性関数をユーザが操作または修正できることが有利である。例えば、ユーザは、異なる関連性関数を異なるシナリオまたはデータセットに適用することを選択することができ、あるいは、検索結果に適用されるランク付けを改変して何らかの望ましい基準を満たすために、ランク付け関数を修正することができる。この操作する自由は、ユーザに利点をもたらす。
【００２７】
いくつかの実施形態では、ユーザは、利用可能な異なる演算子に対応する、複数のランク付け関数を供給することを選択することができる。例えば、ブール論理演算子を扱うとき、ユーザは、ＡＮＤ演算子とＯＲ演算子に対して別々の関連性関数を供給することができる。さらに、いくつかのこのような実施形態では、ユーザ提供の関連性関数によってオーバライドされない演算子と共に使用されるように、検索エンジンによってデフォルトの関連性関数を供給することができる。
【００２８】
ユーザ定義の関連性関数の適用
次に図３を参照すると、一実施形態により、ユーザ定義の関数を適用する方法のフローチャート３００が示されている。フローチャート３００には特定のステップを開示するが、このようなステップは例である。すなわち、実施形態は、様々な他の（追加の）ステップを、またはフローチャート３００に列挙したステップの変形を実施するのにもよく適する。フローチャート３００中のステップは、提示したのと異なる順序で実施してもよいこと、および、フローチャート３００中のすべてのステップを実施しなくてもよいことを理解されたい。
【００２９】
ここでステップ３１０を参照すると、ユーザ指定のランク付け関数が受け取られる。種々の実施形態で、このような関連性関数を供給するための種々の方法が利用される。例えば、いくつかの実施形態では、ユーザは、プログラミング言語、例えばＴ−ＳＱＬで書かれた関連性関数を供給することができる。いくつかのこのような実施形態では、宣言言語、例えばＳＱＬまたはダイアレクト(dialect)が、ユーザ定義の関連性関数に使用される。また、種々の実施形態で、ランク付け関数の動作は変動する場合がある。例えば、一実施形態では、ランク付け関数は、ブール演算子ＡＮＤに適用される場合があり、ＴＦ−ＩＤＦ方式を検索結果に適用する場合がある。
【００３０】
次にステップ３２０を参照すると、クエリが分解される。いくつかの実施形態では、複合的なクエリが、より単純な演算子のツリーに分解される。いくつかの他の実施形態では、クエリが、いくつかのより単純な演算に分解される。例えば、一実施形態では、フルテキストクエリが、結合で接続されたいくつかの単純な演算を含むツリーに分離される。このような一実施形態では、結合のタイプは、単純な演算を接続する論理演算子に基づく。例えば、ＡＮＤは内部結合として扱われ、ＯＲは外部結合として扱われ、ＡＮＤ ＮＯＴは存在しないとして対処される。いくつかの実施形態では、より単純な演算はそれぞれ、同種の論理演算子、例えばＡＮＤまたはＯＲのみを含む。このような一実施形態では、同種の論理演算子に対するランク付け関数は可換として扱われる。
【００３１】
次にステップ３３０を参照すると、単純な演算がランク付け関数と関連付けられる。いくつかの実施形態では、単純な演算は、ユーザ供給のランク付け関数と関連付けることができる。いくつかの実施形態では、単純な演算を、ユーザ供給のランク付け関数が利用可能であればそれとリンクさせることができ、あるいはデフォルトのランク付け関数とリンクさせることができる。いくつかの実施形態では、ランク付け関数は、共通のシグネチャを有し、インデックスアクセスのための言語要素を基本ツールとして使用する。このような実施形態では、コンテキスト情報がランク付け関数に提供され、ランク付け関数は、インデックスアクセスを実施する要素に渡される。さらに、コンテキスト情報を他のテーブル値関数（ＴＶＦ）に渡して、ランク関数にとって重要だがインデックス中に存在しない情報を得ることができる。
【００３２】
次にステップ３４０を参照すると、検索が実施され、対応する結果が取り出される。種々の実施形態で、この検索および取出しの動作は、種々の方法で実施される。実施形態は、多くの異なる検索手法と結果取出し手法の両方を用いた適用例によく適することを理解されたい。いくつかの実施形態では、取り出された結果は、関連性関数が結果のランク付けを計算するのに必要な情報を含む。このような情報は、文書カウント、用語頻度、用語重み、および他の情報などの要素を含むことができる。いくつかの実施形態では、前述の分解された単純な演算を使用して、複数の検索が実施される。このような一実施形態では、コンテキスト情報を提供することにより、インデックスアクセス要素は、より単純な演算に対応する部分的なクエリに合致する行を取り出すことができる。
【００３３】
次にステップ３５０を参照すると、適切な１つまたは複数のランク付け関数に従って、取り出された結果がランク付けされる。いくつかの実施形態では、ランク付け関数は、集合体およびスカラユーザ定義関数など、標準的なＳＱＬプログラミングコンストラクトを使用して、各文書のスコアを計算する。
【００３４】
いくつかの実施形態では、クエリ分解、およびランク付け関数を単純な演算子に関連付けることは、コンパイル段階の間に実施され、検索、取出し、およびランク付けは、ランタイム段階の間に実施される。他の実施形態では、これらの動作のタイミングは変動する場合がある。
【００３５】
ストリーミングテーブル値関数
前述の方法を実施するいくつかの実施形態では、ストリーミングテーブル値関数（ＳＴＶＦ）を使用してインデックスアクセスが提供される。このような一実施形態では、ＳＴＶＦの使用は、いくつかの利点をもたらす。これらの利点の中には、反転インデックスにわたるマルチウェイＡＮＤおよびＯＲのための効率的な実施、ならびに、効率的な反転があり、文書識別子が反転インデックス中で内部列であっても、出力は、文書識別子の小さい順にソートされる。他の実施形態では、他の検索結果順序付け、例えば関連性順を利用することができる。さらに、ＳＴＶＦの使用は、ユーザ要求に基づいて異なるレベルで圧縮解除することを可能にし、例えば、文書識別子圧縮解除の場合はレベル１での圧縮解除、あるいは発生圧縮解除の場合はレベル２での圧縮解除を可能にする。加えて、ＳＴＶＦの使用は、ランク付けに必要とされる情報、例えば文書カウント、用語頻度、用語重み、または列重みを、効率的に取り出すことを可能にする。さらに、ＳＴＶＦの使用は正確な濃度推定を可能にし、このことは、データベースクエリオプティマイザによる効果的な最適化を可能にする。
【００３６】
クエリの分解
次に図４Ａを参照すると、一実施形態により、例示的なデータベースクエリ４００が示されている。クエリ４００は、特定の定義された要素を組み込むものとして示されているが、実施形態は、追加の、より少ない、または異なる要素を含む適用例、あるいは異なる要素配置を特徴とする適用例にもよく適することを理解されたい。
【００３７】
クエリ４００は、図示の実施形態では、ＳＱＬデータベースに向けたフルテキストクエリとして示されている。この実施形態では、クエリ４００は、クエリが複数のより単純な演算に還元されるようにして構築されたいくつかの変換を経て、ユーザ供給のランク付け関数の包含を可能にする。
【００３８】
図示の実施形態では、Ｔは、テーブル２００などのデータベーステーブルである。ｄｏｃｕｍｅｎｔおよびｄｏｃｋｅｙは、データベーステーブル内の列である。検索ストリングは、図示の実施形態では「ａｐｐｌｅｓ ＡＮＤ ｏｒａｎｇｅｓ ＯＲ ｇｒａｐｅｓ ＡＮＤ ｐｅａｒｓ」である。ＣＯＮＴＡＩＮＳＴＡＢＬＥは、検索ストリングを適格とする行、ならびにこの検索ストリングに対する文書のランクを返す、Ｔ−ＳＱＬ ＴＶＦである。図示の実施形態では、このクエリは、ｄｏｃｕｍｅｎｔ列がキーワードａｐｐｌｅｓとｏｒａｎｇｅｓの両方、またはキーワードｇｒａｐｅｓとｐｅａｒｓの両方を含む、テーブルＴのすべての行およびそれらのランク値を返すように、検索エンジンに命令する。
【００３９】
一実施形態では、クエリは解析されバインドされる。解析およびバインドのプロセスの間、ＣＯＮＴＡＩＮＳＴＡＢＬＥ関数が識別され、フルテキストクエリコンパイラが呼び出されて検索ストリングが処理される。フルテキストクエリコンパイラは、検索ストリングを、クエリキーワードとそれらをバインドする論理演算子とを表すツリーに変換する。そのようなツリーの１つであるツリー４０１を、図４Ｂに示す。
【００４０】
ツリー４０１に示すように、クエリ４００からの検索ストリングが、ツリー構造に変換されている。ツリー４０１は、検索ストリングによって関連付けられるツリー要素を論理演算子がバインドするように構成されている。このようにして、ＯＲ４１０が、ＡＮＤ４２０をＡＮＤ４２５とバインドする。ＡＮＤ４２０は、ａｐｐｌｅｓ４３１をｏｒａｎｇｅｓ４３３とバインドし、ＡＮＤ４２５は、ｇｒａｐｅｓ４３５をｐｅａｒｓ４３７とバインドする。
【００４１】
いくつかの実施形態では、検索ストリングが単純化されたツリー構造に還元された後、ＡＮＤおよびＯＲ演算子など同種の論理演算子が識別される。いくつかのこのような実施形態では、単純な用語、例えばキーワードをバインドする同種の論理表現は、ＳＴＶＦとして実施されるマルチウェイスキップマージ結合演算子に変換される。このような一実施形態を、図４Ｃに中間ツリー４４１として示す。
【００４２】
中間ツリー４４１に示すように、ツリー４０１のＡＮＤ印字は、ＳＴＶＦとして実施されるマルチウェイスキップマージ結合演算子で置き換えられている。ＯＲ４５０は今や、要素４６０と４６５をバインドし、これらはそれぞれマルチウェイスキップマージ結合演算子である。
【００４３】
いくつかの実施形態では、クエリがこのようにして変換された後、システムは、適切な演算子に対してユーザから提供されたランク付け関数をロードすることになる。例えば、中間ツリー４４１を参照すると、システムは、ＡＮＤ演算子に対してユーザから提供されたランク付け関数をロードすることになる。ランク付け関数のコンパイル中に、システムは適宜、実際のマルチウェイマージ結合演算子を挿入することになる。いくつかの実施形態では、特定の演算子に対してユーザからランク付け関数が提供されない場合は、代わりにデフォルトのシステム提供の関数がロードされコンパイルされる。
【００４４】
次いで、ランク付け関数によって返されたランク値が、より高いレベルで、例えば図４ＣのＯＲ４５０のレベルで組み合わせられる。いくつかの実施形態では、この組合せは、デフォルトのシステム動作によって対処される。例えば、ＯＲ演算子の場合は、組み合わせられたランクを最大値として計算し、ＡＮＤ演算子の場合は最小値として計算する。他の実施形態では、ユーザは、ユーザ指定のランク関数と同様にして、ユーザ指定の組合せ関数を提供することができる。
【００４５】
図４Ｄに、一実施形態によりクエリツリー４７１を示す。クエリツリー４７１は、前述のような組合せ関数と共に、クエリ４００の最終状態を示す。図示の実施形態では、フルテキストクエリツリー中の非リーフノードが、関係演算子に、例えばＡＮＤの場合は内部結合、ＯＲの場合は外部結合、またはＡＮＤ ＮＯＴの場合は半結合に変換される。図示のように、ＯＲ４５０が外部結合４８５で置き換えられている。ランク付け関数４９０および４９５が、それぞれマルチウェイスキップマージ結合演算子４９２および４９７に対してロードされている。ブロック４８０が組合せ関数を示すが、ここでは、ランク付け関数４９０および４９５の返却ランク値の最大値として示されている。
【００４６】
いくつかの実施形態では、このクエリツリーは、ＳＱＬクエリ全体に組み込まれて、全体として最適化される。いくつかのこのような実施形態では、この最適化により、ユーザ定義のランク付け関数は、どんなに複雑であっても、ユーザ提供のクエリの一部であるかのような程度と同程度まで、システムによって最適化されることが確実になる。
【００４７】
構造上の特徴および／または方法上の行為に特有の言葉で主題について述べたが、添付の特許請求の範囲に定義する主題は、必ずしも前述の特定の特徴または行為に限定されないことを理解されたい。そうではなく、前述の特定の特徴および行為は、特許請求の範囲を実施する例示的な形として開示する。
【特許請求の範囲】
【請求項１】
ユーザ定義の関連性関数を適用する方法であって、
複合的な検索クエリを単純な演算子に分解するステップと、
前記単純な演算子を前記ユーザ定義の関連性関数と関連付けるステップと、
前記複合的な検索クエリと合致する合致文書を取り出すステップと、
前記ユーザ定義の関連性関数を使用して前記合致文書のランクを計算するステップとを含むことを特徴とする方法。
【請求項２】
前記ユーザ定義の関連性関数を受け取るステップをさらに含むことを特徴とする請求項１に記載の方法。
【請求項３】
データベース中で前記合致文書を検索するステップをさらに含むことを特徴とする請求項１に記載の方法。
【請求項４】
前記合致文書は、前記ユーザ定義の関連性関数によって前記ランクの計算に使用される情報を含むことを特徴とする請求項１に記載の方法。
【請求項５】
前記計算するステップは、前記ユーザ定義の関連性関数が、前記合致文書に関連する情報を使用して前記ランクを計算するステップを含むことを特徴とする請求項１に記載の方法。
【請求項６】
前記分解するステップは、同種の論理表現をマルチウェイスキップマージ結合演算子に変換するステップを含むことを特徴とする請求項１に記載の方法。
【請求項７】
前記複合的な検索クエリはブール論理クエリを含むことを特徴とする請求項１に記載の方法。
【請求項８】
前記分解するステップは前記複合的な検索クエリを演算子のツリーに分解するステップを含むことを特徴とする請求項１に記載の方法。
【請求項９】
ユーザ定義のランク付け関数を受け取るステップと、
検索クエリを受け取るステップと、
前記検索クエリを複数の単純な演算に分解するステップと、
前記複数の単純な演算それぞれを前記ユーザ定義のランク付け関数と関連付けるステップと、
前記複数の単純な演算に対応する複数の結果を取り出すステップと、
前記ユーザ定義のランク付け関数を使用して前記複数の結果それぞれのランクを計算するステップとを実施するためのコンピュータ実行可能命令を有することを特徴とするコンピュータ可読媒体。
【請求項１０】
複数のユーザ定義のランク付け関数を受け取るステップと、
前記複数のユーザ定義のランク付け関数を前記複数の単純な演算と関連付けるステップとをさらに含むことを特徴とする請求項９に記載のコンピュータ可読媒体。
【請求項１１】
前記複数の結果の前記ランクを組み合わせて、前記複数の結果それぞれの全体的なランクを生み出すステップをさらに含むことを特徴とする請求項９に記載のコンピュータ可読媒体。
【請求項１２】
前記組み合わせるステップは、前記複数の結果の前記ランクから最大ランク値を計算するステップを含むことを特徴とする請求項１１に記載のコンピュータ可読媒体。
【請求項１３】
前記分解するステップは、
前記検索クエリを検索ツリーに変換するステップと、
前記検索ツリー中の同種の演算子を識別するステップと、
前記同種の演算子をマルチウェイスキップマージ結合演算子に変換するステップとを含むことを特徴とする請求項９に記載のコンピュータ可読媒体。
【請求項１４】
前記マルチウェイスキップマージ結合演算子はストリーミングテーブル値関数（ＳＴＶＦ）を含むことを特徴とする請求項１３に記載のコンピュータ可読媒体。
【請求項１５】
前記検索クエリはベクトルクエリを含むことを特徴とする請求項９に記載のコンピュータ可読媒体。
【請求項１６】
前記ベクトルクエリは複数のキーワードを含み、各キーワードは検索重みに関連することを特徴とする請求項１５に記載のコンピュータ可読媒体。
【請求項１７】
バスと、
前記バスに結合された、情報を処理するためのプロセッサと、
前記バスに結合された、情報を記憶するためのメモリと、
前記バスに結合された、情報を記憶するためのデータ記憶デバイスとを備えるシステムであって、複合的な検索クエリを受け取り、前記複合的な検索クエリを複数のより単純な演算に解析し、前記複数のより単純な演算に対応する複数の結果を取り出し、ユーザ定義の関連性関数を適用することによって前記複数の結果それぞれのランクを計算するように構成されたことを特徴とするシステム。
【請求項１８】
前記複合的な検索クエリを検索ツリーに還元し、前記ツリー中の同種の演算子をマルチウェイスキップマージ結合演算子に変換し、前記検索ツリーの非リーフノードを関係演算子に変換することによって、前記複合的な検索クエリを解析するように構成されたことを特徴とする請求項１７に記載のシステム。
【請求項１９】
前記ユーザ定義の関連性関数を前記検索ツリーの一部として最適化するようにさらに構成されたことを特徴とする請求項１８に記載のシステム。
【請求項２０】
前記ユーザ定義の関連性関数は、宣言言語で書かれた関数を含むことを特徴とする請求項１７に記載のシステム。
【請求項１】
ユーザ定義の関連性関数を適用する方法であって、
複合的な検索クエリを単純な演算子に分解するステップと、
前記単純な演算子を前記ユーザ定義の関連性関数と関連付けるステップと、
前記複合的な検索クエリと合致する合致文書を取り出すステップと、
前記ユーザ定義の関連性関数を使用して前記合致文書のランクを計算するステップとを含むことを特徴とする方法。
【請求項２】
前記ユーザ定義の関連性関数を受け取るステップをさらに含むことを特徴とする請求項１に記載の方法。
【請求項３】
データベース中で前記合致文書を検索するステップをさらに含むことを特徴とする請求項１に記載の方法。
【請求項４】
前記合致文書は、前記ユーザ定義の関連性関数によって前記ランクの計算に使用される情報を含むことを特徴とする請求項１に記載の方法。
【請求項５】
前記計算するステップは、前記ユーザ定義の関連性関数が、前記合致文書に関連する情報を使用して前記ランクを計算するステップを含むことを特徴とする請求項１に記載の方法。
【請求項６】
前記分解するステップは、同種の論理表現をマルチウェイスキップマージ結合演算子に変換するステップを含むことを特徴とする請求項１に記載の方法。
【請求項７】
前記複合的な検索クエリはブール論理クエリを含むことを特徴とする請求項１に記載の方法。
【請求項８】
前記分解するステップは前記複合的な検索クエリを演算子のツリーに分解するステップを含むことを特徴とする請求項１に記載の方法。
【請求項９】
ユーザ定義のランク付け関数を受け取るステップと、
検索クエリを受け取るステップと、
前記検索クエリを複数の単純な演算に分解するステップと、
前記複数の単純な演算それぞれを前記ユーザ定義のランク付け関数と関連付けるステップと、
前記複数の単純な演算に対応する複数の結果を取り出すステップと、
前記ユーザ定義のランク付け関数を使用して前記複数の結果それぞれのランクを計算するステップとを実施するためのコンピュータ実行可能命令を有することを特徴とするコンピュータ可読媒体。
【請求項１０】
複数のユーザ定義のランク付け関数を受け取るステップと、
前記複数のユーザ定義のランク付け関数を前記複数の単純な演算と関連付けるステップとをさらに含むことを特徴とする請求項９に記載のコンピュータ可読媒体。
【請求項１１】
前記複数の結果の前記ランクを組み合わせて、前記複数の結果それぞれの全体的なランクを生み出すステップをさらに含むことを特徴とする請求項９に記載のコンピュータ可読媒体。
【請求項１２】
前記組み合わせるステップは、前記複数の結果の前記ランクから最大ランク値を計算するステップを含むことを特徴とする請求項１１に記載のコンピュータ可読媒体。
【請求項１３】
前記分解するステップは、
前記検索クエリを検索ツリーに変換するステップと、
前記検索ツリー中の同種の演算子を識別するステップと、
前記同種の演算子をマルチウェイスキップマージ結合演算子に変換するステップとを含むことを特徴とする請求項９に記載のコンピュータ可読媒体。
【請求項１４】
前記マルチウェイスキップマージ結合演算子はストリーミングテーブル値関数（ＳＴＶＦ）を含むことを特徴とする請求項１３に記載のコンピュータ可読媒体。
【請求項１５】
前記検索クエリはベクトルクエリを含むことを特徴とする請求項９に記載のコンピュータ可読媒体。
【請求項１６】
前記ベクトルクエリは複数のキーワードを含み、各キーワードは検索重みに関連することを特徴とする請求項１５に記載のコンピュータ可読媒体。
【請求項１７】
バスと、
前記バスに結合された、情報を処理するためのプロセッサと、
前記バスに結合された、情報を記憶するためのメモリと、
前記バスに結合された、情報を記憶するためのデータ記憶デバイスとを備えるシステムであって、複合的な検索クエリを受け取り、前記複合的な検索クエリを複数のより単純な演算に解析し、前記複数のより単純な演算に対応する複数の結果を取り出し、ユーザ定義の関連性関数を適用することによって前記複数の結果それぞれのランクを計算するように構成されたことを特徴とするシステム。
【請求項１８】
前記複合的な検索クエリを検索ツリーに還元し、前記ツリー中の同種の演算子をマルチウェイスキップマージ結合演算子に変換し、前記検索ツリーの非リーフノードを関係演算子に変換することによって、前記複合的な検索クエリを解析するように構成されたことを特徴とする請求項１７に記載のシステム。
【請求項１９】
前記ユーザ定義の関連性関数を前記検索ツリーの一部として最適化するようにさらに構成されたことを特徴とする請求項１８に記載のシステム。
【請求項２０】
前記ユーザ定義の関連性関数は、宣言言語で書かれた関数を含むことを特徴とする請求項１７に記載のシステム。
【図１】
【図２】
【図３】
【図４Ａ】
【図４Ｂ】
【図４Ｃ】
【図４Ｄ】
【図２】
【図３】
【図４Ａ】
【図４Ｂ】
【図４Ｃ】
【図４Ｄ】
【公表番号】特表２０１０−５２８３６９（Ｐ２０１０−５２８３６９Ａ）
【公表日】平成２２年８月１９日（２０１０．８．１９）
【国際特許分類】
【出願番号】特願２０１０−５０９４８２（Ｐ２０１０−５０９４８２）
【出願日】平成２０年５月１６日（２００８．５．１６）
【国際出願番号】ＰＣＴ／ＵＳ２００８／０６３９９１
【国際公開番号】ＷＯ２００８／１４７７３６
【国際公開日】平成２０年１２月４日（２００８．１２．４）
【出願人】（５０００４６４３８）マイクロソフト コーポレーション (3,165)
【Ｆターム（参考）】
【公表日】平成２２年８月１９日（２０１０．８．１９）
【国際特許分類】
【出願日】平成２０年５月１６日（２００８．５．１６）
【国際出願番号】ＰＣＴ／ＵＳ２００８／０６３９９１
【国際公開番号】ＷＯ２００８／１４７７３６
【国際公開日】平成２０年１２月４日（２００８．１２．４）
【出願人】（５０００４６４３８）マイクロソフト コーポレーション (3,165)
【Ｆターム（参考）】
[ Back to top ]