(57)【要約】【課題】【解決手段】ＡＮＤ条件およびＯＲ条件を指定するクエリを受信することと、ＡＮＤインデックス構造に基づいて、クエリのＡＮＤ条件を満たす、コーパス内の複数の文書のうちの文書のセットを判断することと、文書のセット内の第１の文書についてクエリ類似性スコアを計算することであって、クエリ類似性スコアが、クエリのＯＲ条件について計算される第１のハッシュ値、ＯＲ条件についての重み値、およびＯＲインデックスにおいて指定される第１の文書についての第２のハッシュ値に基づく、計算することと、クエリへの応答として第１の文書の標示およびクエリ類似性スコアを返すことと、を含む動作を実施するように構成される、システム、方法、およびコンピュータ・プログラム製品である。【選択図】図１
2021500664.tif 000002
【特許請求の範囲】
【請求項１】
ＡＮＤ条件およびＯＲ条件を指定するクエリを受信することと、
ＡＮＤインデックス構造に基づいて、前記クエリの前記ＡＮＤ条件を満たす、コーパス内の複数の文書のうちの文書のセットを判断することと、
プロセッサによって、前記文書のセット内の第１の文書についてクエリ類似性スコアを計算することであって、前記クエリ類似性スコアが、前記クエリの前記ＯＲ条件について計算される第１のハッシュ値、前記ＯＲ条件についての重み値、およびＯＲインデックスにおいて指定される前記第１の文書についての第２のハッシュ値に基づく、前記計算することと、
前記クエリへの応答として前記第１の文書の標示および前記クエリ類似性スコアを返すことと
を含む方法。
【請求項２】
前記ＡＮＤインデックスは、複数の特徴のそれぞれの特徴を含む各文書についての文書識別子（ＩＤ）を記憶するように構成されるポスティング・リストを含み、前記ＯＲインデックスは、前記複数の文書のそれぞれについてのそれぞれのハッシュ値を含み、前記第１のハッシュ値、前記第２のハッシュ値、および前記ＯＲインデックス内の前記複数のハッシュ値は、局所性鋭敏型ハッシュ関数に基づいて計算される、請求項１に記載の方法。
【請求項３】
前記クエリは、複数のＡＮＤ条件を指定し、判断された前記文書のセットは、前記複数のＡＮＤ条件のそれぞれを満たし、前記文書のセットを判断することは、
前記クエリにおいて指定される前記複数のＡＮＤ条件のそれぞれの標示を含む検索クエリを生成することと、
前記ＡＮＤインデックスに対して前記検索クエリを処理することと、
前記ＡＮＤインデックスから、前記文書のセット内の各文書の前記文書ＩＤを含む前記文書のセットを受信することと、を含む、請求項２に記載の方法。
【請求項４】
前記クエリは、複数のＯＲ条件を指定し、前記クエリ類似性スコアを計算することは、
（ｉ）前記複数のＯＲ条件の各ＯＲ条件、および（ｉｉ）前記複数のＯＲ条件、についてのそれぞれのハッシュ値を計算することと、
前記複数のＯＲ条件に対する前記第１の文書についての全体類似性スコアを、前記複数のＯＲ条件についての前記ハッシュ値、および前記ＯＲインデックスから受信される前記第１の文書についての前記第２のハッシュ値に基づいて計算することと、
各ＯＲ条件に対する前記第１の文書についてのそれぞれのＯＲ類似性スコアを、前記ＯＲインデックスから受信される前記第１の文書についての前記第２のハッシュ値、および前記それぞれのＯＲ条件についての前記ハッシュ値に基づいて計算することと、
事前定義された閾値を超えるそれぞれのＯＲ類似性スコアについて、前記それぞれのＯＲ条件に関連付けられた重みを前記全体類似性スコアに加算することと、
前記全体類似性スコアを前記クエリ類似性スコアとして返すことと、を含む、請求項２に記載の方法。
【請求項５】
前記第１の文書についての前記類似性スコアを計算する前に、
前記ＯＲインデックスから前記第１の文書についての文書識別子（ＩＤ）を受信することと、
前記第１の文書についての前記文書ＩＤが前記文書のセットに含まれると判断することと
をさらに含む、請求項１に記載の方法。
【請求項６】
前記コーパス内の前記複数の文書の第２の文書についての文書識別子（ＩＤ）を前記ＯＲインデックスから受信することと、
前記第２の文書についての前記文書ＩＤが前記文書のセットに含まれないと判断することと、
前記第２の文書についてのクエリ類似性スコアを計算することを抑制することと、
前記クエリへの応答として前記第２の文書を返すことを抑制することと
をさらに含む、請求項５に記載の方法。
【請求項７】
前記ＡＮＤインデックスおよび前記ＯＲインデックスは、前記コーパス内の前記複数の文書の前処理段階の間に生成される、請求項１に記載の方法。
【請求項８】
プロセッサと、
メモリであって、前記プロセッサによる実行時に、
ＡＮＤ条件およびＯＲ条件を指定するクエリを受信することと、
ＡＮＤインデックス構造に基づいて、前記クエリの前記ＡＮＤ条件を満たす、コーパス内の複数の文書のうちの文書のセットを判断することと、
前記文書のセット内の第１の文書についてクエリ類似性スコアを計算することであって、前記クエリ類似性スコアは、前記クエリの前記ＯＲ条件について計算される第１のハッシュ値、前記ＯＲ条件についての重み値、およびＯＲインデックスにおいて指定される前記第１の文書についての第２のハッシュ値に基づく、前記計算することと、
前記クエリへの応答として前記第１の文書の標示および前記クエリ類似性スコアを返すことと
を含む動作を実施するプログラムを含む前記メモリと
を備えるシステム。
【請求項９】
前記ＡＮＤインデックスは、複数の特徴のそれぞれの特徴を含む各文書についての文書識別子（ＩＤ）を記憶するように構成されるポスティング・リストを含み、前記ＯＲインデックスは、前記複数の文書のそれぞれについてのそれぞれのハッシュ値を含み、前記第１のハッシュ値、前記第２のハッシュ値、および前記ＯＲインデックス内の前記複数のハッシュ値は、局所性鋭敏型ハッシュ関数に基づいて計算される、請求項８に記載のシステム。
【請求項１０】
前記クエリは、複数のＡＮＤ条件を指定し、前記判断された文書のセットは、前記複数のＡＮＤ条件のそれぞれを満たし、前記文書のセットを判断することは、
前記クエリにおいて指定される前記複数のＡＮＤ条件のそれぞれの標示を含む検索クエリを生成することと、
前記ＡＮＤインデックスに対して前記検索クエリを処理することと、
前記ＡＮＤインデックスから、前記文書のセット内の各文書の前記文書ＩＤを含む前記文書のセットを受信することと
を含む、請求項９に記載のシステム。
【請求項１１】
前記クエリは、複数のＯＲ条件を指定し、前記クエリ類似性スコアを計算することは、
（ｉ）前記複数のＯＲ条件の各ＯＲ条件、および（ｉｉ）前記複数のＯＲ条件、についてのそれぞれのハッシュ値を計算することと、
前記複数のＯＲ条件に対する前記第１の文書についての全体類似性スコアを、前記複数のＯＲ条件についての前記ハッシュ値、および前記ＯＲインデックスから受信される前記第１の文書についての前記第２のハッシュ値に基づいて計算することと、
各ＯＲ条件に対する前記第１の文書についてのそれぞれのＯＲ類似性スコアを、前記ＯＲインデックスから受信される前記第１の文書についての前記第２のハッシュ値、および前記それぞれのＯＲ条件についての前記ハッシュ値に基づいて計算することと、
事前定義された閾値を超えるそれぞれのＯＲ類似性スコアについて、前記それぞれのＯＲ条件に関連付けられた重みを前記全体類似性スコアに加算することと、
前記全体類似性スコアを前記クエリ類似性スコアとして返すことと
を含む、請求項９に記載のシステム。
【請求項１２】
前記第１の文書についての前記類似性スコアを計算する前に、前記動作が、
前記ＯＲインデックスから前記第１の文書についての文書識別子（ＩＤ）を受信することと、
前記第１の文書についての前記文書ＩＤが前記文書のセットに含まれると判断することと
をさらに含む、請求項８に記載のシステム。
【請求項１３】
前記動作は、
前記コーパス内の前記複数の文書の第２の文書についての文書識別子（ＩＤ）を前記ＯＲインデックスから受信することと、
前記第２の文書についての前記文書ＩＤが前記文書のセットに含まれないと判断することと、
前記第２の文書についてのクエリ類似性スコアを計算することを抑制することと、
前記クエリへの応答として前記第２の文書を返すことを抑制することと
をさらに含む、請求項１２に記載のシステム。
【請求項１４】
前記ＡＮＤインデックスおよび前記ＯＲインデックスが、前記コーパス内の前記複数の文書の前処理段階の間に生成される、請求項８に記載のシステム。
【請求項１５】
具現化されたコンピュータ可読プログラム・コードを有する非一過性コンピュータ可読記憶媒体であって、前記コンピュータ可読プログラム・コードは、
ＡＮＤ条件およびＯＲ条件を指定するクエリを受信することと、
ＡＮＤインデックス構造に基づいて、前記クエリの前記ＡＮＤ条件を満たす、コーパス内の複数の文書のうちの文書のセットを判断することと、
前記文書のセット内の第１の文書についてクエリ類似性スコアを計算することであって、前記クエリ類似性スコアは、前記クエリの前記ＯＲ条件について計算される第１のハッシュ値、前記ＯＲ条件についての重み値、およびＯＲインデックスにおいて指定される前記第１の文書についての第２のハッシュ値に基づく、前記計算することと、
前記クエリへの応答として前記第１の文書の標示および前記クエリ類似性スコアを返すことと
を含む動作を実施するためにプロセッサによって実行可能である、前記非一過性コンピュータ可読記憶媒体
を含む、コンピュータ・プログラム製品。
【請求項１６】
前記ＡＮＤインデックスが、複数の特徴のそれぞれの特徴を含む各文書についての文書識別子（ＩＤ）を記憶するように構成されるポスティング・リストを含み、前記ＯＲインデックスが、前記複数の文書のそれぞれについてのそれぞれのハッシュ値を含み、前記第１のハッシュ値、前記第２のハッシュ値、および前記ＯＲインデックス内の前記複数のハッシュ値が、局所性鋭敏型ハッシュ関数に基づいて計算される、請求項１５に記載のコンピュータ・プログラム製品。
【請求項１７】
前記クエリが、複数のＡＮＤ条件を指定し、前記判断された文書のセットが、前記複数のＡＮＤ条件のそれぞれを満たし、前記文書のセットを判断することが、
前記クエリにおいて指定される前記複数のＡＮＤ条件のそれぞれの標示を含む検索クエリを生成することと、
前記ＡＮＤインデックスに対して前記検索クエリを処理することと、
前記ＡＮＤインデックスから、前記文書のセット内の各文書の前記文書ＩＤを含む前記文書のセットを受信することと
を含む、請求項１６に記載のコンピュータ・プログラム製品。
【請求項１８】
前記クエリは、複数のＯＲ条件を指定し、前記クエリ類似性スコアを計算することは、
（ｉ）前記複数のＯＲ条件の各ＯＲ条件、および（ｉｉ）前記複数のＯＲ条件、についてのそれぞれのハッシュ値を計算することと、
前記複数のＯＲ条件に対する前記第１の文書についての全体類似性スコアを、前記複数のＯＲ条件についての前記ハッシュ値、および前記ＯＲインデックスから受信される前記第１の文書についての前記第２のハッシュ値に基づいて計算することと、
各ＯＲ条件に対する前記第１の文書についてのそれぞれのＯＲ類似性スコアを、前記ＯＲインデックスから受信される前記第１の文書についての前記第２のハッシュ値、および前記それぞれのＯＲ条件についての前記ハッシュ値に基づいて計算することと、
事前定義された閾値を超えるそれぞれのＯＲ類似性スコアについて、前記それぞれのＯＲ条件に関連付けられた重みを前記全体類似性スコアに加算することと、
前記全体類似性スコアを前記クエリ類似性スコアとして返すことと、を含む、請求項１６に記載のコンピュータ・プログラム製品。
【請求項１９】
前記第１の文書についての前記類似性スコアを計算する前に、前記動作が、
前記ＯＲインデックスから前記第１の文書についての文書識別子（ＩＤ）を受信することと、
前記第１の文書についての前記文書ＩＤが前記文書のセットに含まれると判断することと
をさらに含む、請求項１５に記載のコンピュータ・プログラム製品。
【請求項２０】
前記ＡＮＤインデックスおよび前記ＯＲインデックスは、前記コーパス内の前記複数の文書の前処理段階の間に生成され、前記動作は、
前記コーパス内の前記複数の文書の第２の文書についての文書識別子（ＩＤ）を前記ＯＲインデックスから受信することと、
前記第２の文書についての前記文書ＩＤが前記文書のセットに含まれないと判断することと、
前記第２の文書についてのクエリ類似性スコアを計算することを抑制することと、
前記クエリへの応答として前記第２の文書を返すことを抑制することと、
をさらに含む、請求項１９に記載のコンピュータ・プログラム製品。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、クエリ処理に関する。
【背景技術】
【０００２】
検索クエリは、多くの場合多数の条件を含む。条件の種類は、論理積条件（例えば、「猫  ＡＮＤ  犬」）、および論理和条件（例えば、「リンゴ  ＯＲ  オレンジ」）を含み得る。検索クエリを処理するための従来技術は、１種類のクエリ条件に対して最適化されることが多い。例えば、論理積条件を効率的に処理し得るデータ構造は、論理和条件を処理するには効率的ではない。さらに、それらの性質によって、論理和条件を効率的に処理するデータ構造は、正確に論理積条件を処理することができない。クエリ条件が、１００、１０００、またはそれ以上に達し得ると、従来技術は、両方の種類の条件を含むクエリを効率的に処理することができない。
【発明の概要】
【０００３】
発明の実施形態は、クエリ処理に関し、より具体的には、類似性検索のためのクエリの論理和条件および論理積条件のハイブリッド処理に関する。
【０００４】
本発明の１つの実施形態によれば、方法は、ＡＮＤ条件およびＯＲ条件を指定するクエリを受信することと、ＡＮＤインデックス構造に基づいて、クエリのＡＮＤ条件を満たす、コーパス内の複数の文書のうちの文書のセットを判断することと、文書のセット内の第１の文書についてクエリ類似性スコアを計算することであって、クエリ類似性スコアが、クエリのＯＲ条件について計算される第１のハッシュ値、ＯＲ条件についての重み値、およびＯＲインデックスにおいて指定される第１の文書についての第２のハッシュ値に基づく、計算することと、クエリへの応答として第１の文書の標示およびクエリ類似性スコアを返すことと、を含む。
【０００５】
別の実施形態において、システムは、プロセッサと、メモリであって、プロセッサによる実行時に、ＡＮＤ条件およびＯＲ条件を指定するクエリを受信することと、ＡＮＤインデックス構造に基づいて、クエリのＡＮＤ条件を満たす、コーパス内の複数の文書のうちの文書のセットを判断することと、文書のセット内の第１の文書についてクエリ類似性スコアを計算することであって、クエリ類似性スコアが、クエリのＯＲ条件について計算される第１のハッシュ値、ＯＲ条件についての重み値、およびＯＲインデックスにおいて指定される第１の文書についての第２のハッシュ値に基づく、計算することと、クエリへの応答として第１の文書の標示およびクエリ類似性スコアを返すことと、を含む動作を実施するプログラムを含むメモリと、を備える。
【０００６】
別の実施形態において、非一過性コンピュータ可読媒体が、プロセッサによる実行時に、ＡＮＤ条件およびＯＲ条件を指定するクエリを受信することと、ＡＮＤインデックス構造に基づいて、クエリのＡＮＤ条件を満たす、コーパス内の複数の文書のうちの文書のセットを判断することと、文書のセット内の第１の文書についてクエリ類似性スコアを計算することであって、クエリ類似性スコアが、クエリのＯＲ条件について計算される第１のハッシュ値、ＯＲ条件についての重み値、およびＯＲインデックスにおいて指定される第１の文書についての第２のハッシュ値に基づく、計算することと、クエリへの応答として第１の文書の標示およびクエリ類似性スコアを返すことと、を含む動作を実施する命令を記憶する。
【０００７】
本発明の実施形態が、ここで単なる例として添付図面を参照して説明される。
【図面の簡単な説明】
【０００８】
【図１】１つの実施形態による、類似性検索についての検索クエリの論理和条件および論理積条件のハイブリッド処理を実施するクエリ処理システムを示す図である。
【図２】１つの実施形態による、類似性検索についての検索クエリの論理和条件および論理積条件のハイブリッド処理のための方法を示すフローチャートである。
【図３】１つの実施形態による、文書前処理のための方法を示すフローチャートである。
【図４】１つの実施形態による、論理和条件および論理積条件のハイブリッド処理を用いてクエリを処理する方法を示すフローチャートである。
【図５】１つの実施形態による、クエリ内の各ＡＮＤ条件を満たす各文書の文書リストを生成する方法を示すフローチャートである。
【図６】１つの実施形態による、クエリ内の全ＯＲ条件に対する文書についての類似性スコアを計算する方法を示すフローチャートである。
【図７】１つの実施形態による、類似性検索についての検索クエリの論理和条件および論理積条件のハイブリッド処理を実施するシステムを示す図である。
【発明を実施するための形態】
【０００９】
本明細書に開示される実施形態は、クエリ内の論理積条件（「ＡＮＤ条件」とも呼ばれる）および論理和条件（「ＯＲ条件」とも呼ばれる）を効率的に処理する技術を提供する。概して、インデックス構造の第１の種類が、受信したクエリのＡＮＤ条件を処理するために使用され、ハッシュ技術が、クエリのＯＲ条件を処理するために別個で使用される。ＡＮＤ条件およびＯＲ条件を処理した結果は、次いで、最終検索結果セットを計算するためにマージされ得る。最終検索結果セットは、指定されたクエリ内の全てのＡＮＤ条件を完全に満たす結果を含み、結果セット内の結果は、クエリのＯＲ条件が所与の結果によって満たされる度合いによってソートされる。
【００１０】
図１は、１つの実施形態による、類似性検索についての検索クエリの論理和条件および論理積条件のハイブリッド処理を実施するクエリ処理システム１００を示す。図示するように、クエリ処理システム１００は、クエリ１０１を受信する。クエリ１０１は、コマンド・ライン・インターフェース、グラフィカル・ユーザ・インターフェース、アプリケーション・インターフェースなどの任意の種類のインターフェースから受信され得る。概して、クエリ１０１は、コーパス１２０に記憶された文書の集合を対象とする。コーパス１２０に記憶された文書は、「著者」、「場所」、「発行日：」、「主題」などのメタデータ属性、および各メタデータ属性に対応する値を含み得る。コーパス１２０に記憶された文書は、一意の文書識別子（ＩＤ）によって識別され得る。クエリ１０１は、あるメタデータ属性（「特徴」とも呼ばれる）に合致するコーパス１２０内の文書を検索するために指定され得る。例えば、クエリ１０１は、「ソクラテス  ＡＮＤ  アリストテレス」という著者、「ギリシャ  ＯＲ  アテネ」という場所、および「哲学  ＯＲ  試験」という主題を有する文書を返すように指定し得る。クエリ１０１の構文は、現在既知または未知の任意の構文であってもよい。
【００１１】
クエリ１０１を処理するために、クエリ処理システム１００は、クエリ１０１をＯＲ条件のセット１０２およびＡＮＤ条件のセット１０３に構文解析する。ＯＲ条件１０２は、上記例のクエリにおける「ギリシャ  ＯＲ  アテネ」などの、クエリ内の任意の論理和「ＯＲ」条件に対応する。ＡＮＤ条件１０３は、上記例のクエリにおける「ソクラテス  ＡＮＤ  アリストテレス」などの、クエリ内の任意の論理積「ＡＮＤ」条件に対応する。ＡＮＤ条件１０３を処理するために、クエリ生成器１０５は、検索クエリ（または複数の検索クエリ）１０７を生成する。検索クエリ１０７は、クエリ１０１において指定された各ＡＮＤ条件１０３を含む１つまたは複数の検索クエリを表す。検索クエリ１０７は、論理積検索１０８において処理され、論理積検索１０８は、ＡＮＤインデックス１０９を活用する。ＡＮＤインデックス１０９は、コーパス１２０内の文書の事前処理段階の間に生成され、ＡＮＤ条件１０３を満たすコーパス１２０内の文書を効率的に返すために使用されるインデックス構造である。１つの実施形態では、ＡＮＤインデックス１０９は、Ｌｕｃｅｎｅ（Ｒ）ポスティング・リストのセットである。概して、ＡＮＤインデックス１０９は、複数のメタデータ属性（例えば、「著者：ソクラテス」）のそれぞれの標示、および合致するメタデータ属性を含むコーパス１２０内の各文書の標示（例えば、文書ＩＤ）を記憶する。例えば、事前処理段階の間、クエリ処理システム１００は、「１」、「２００」、および「１３３７」という例としてのＩＤを有する文書が、文書の著者がソクラテスであったと指定するメタデータ属性を含むと判断し得る。したがって、ＡＮＤインデックス１０９は、「著者：ソクラテス」の標示、ならびに「１」、「２００」、および「１３３７」の文書ＩＤを含む。少なくとも１つの実施形態では、ＡＮＤインデックス１０９内のエントリが、所与のメタデータ属性についての文書ＩＤの昇順でソートされる。
【００１２】
したがって、ＡＮＤインデックス１０９の論理積検索１０８の結果が、クエリ１０１における各ＡＮＤ条件１０３を満たすコーパス１２０内の文書のリスト１１０（またはセット）を返す。例えば、（文書ＩＤ「１」および「１３３７」が、ＡＮＤインデックス１０９において「アリストテレス」に関連付けられていると仮定すると、）リスト１１０は、「ソクラテス」および「アリストテレス」の著者値を有する文書として文書ＩＤ「１」および「１３３７」を指定し得る。
【００１３】
ＯＲ条件１０２を処理するために、クエリ処理システム１００は、１つまたは複数のハッシュ値１０６を計算するためにハッシュ生成器１０４を活用する。ハッシュ生成器１０４は、属性（または特徴）のセットを入力として用いる任意の局所性鋭敏型ハッシュ（ＬＳＨ）関数を表し、入力に基づいてハッシュ値を計算する。概して、ハッシュ生成器１０４は、類似の入力（例えば、類似の属性のセット）が同一の（または近傍の）ハッシュ値にマッピングするように、ハッシュ値を生成するように構成される。そうすることによって、コーパス１２０からの２つ以上の文書が、計算されたハッシュ値に基づいて比較されることが可能となる。概して、ハッシュ生成器１０４は、クエリ１０１内の各ＯＲ条件１０２についてのそれぞれのハッシュ値「ｈ（ｘ）」（ここで、「ｘ」はＯＲ条件である）１０６を計算し、ハッシュ値「ｈ（Ｏ）」（ここで、「Ｏ」は、クエリ１０１内の全てのＯＲ条件のセットである）１０６をクエリ１０１内のＯＲ条件１０２のそれぞれに基づいて計算する。したがって、前の例のクエリ１０１を続けると、ハッシュ生成器１０４は、「ギリシャ」についての第１のハッシュ値１０６、「アテネ」についての第２のハッシュ値１０６、「哲学」についての第３のハッシュ値１０６、「試験」についての第４のハッシュ値１０６、および「ギリシャ  アテネ  哲学  試験」についての第５のハッシュ値１０６を計算する（第５のハッシュ値を計算する際に、スペースは含まれても含まれなくてもよく、同様に、他の区切り記号が、各ＯＲ条件の語を分離するために含まれても含まれなくてもよいことに留意する）。
【００１４】
ブロック１１３において、クエリ処理システム１００は、文書リスト１１０（例えば、クエリ１０１の各ＡＮＤ条件１０３を満たす文書のセット）内の各文書について１つまたは複数のスコアを計算する。そのために、クエリ処理システム１００は、ＯＲインデックス１１２を活用し、ＯＲインデックス１１２も、コーパス１２０の事前処理段階の間に生成される。概して、ＯＲインデックス１１２は、コーパス１２０内の各文書についての、ハッシュ生成器１０４によって計算されるハッシュ値「ｈ（ｄ）」（ここで、「ｄ」は文書である）のアレイである（例えば、コーパス１２０内の各文書の特徴のセットがハッシュ生成器１０４への入力である）。ＯＲインデックス１１２は、コーパス１２０内の各文書についてのそれぞれの文書ＩＤをさらに含み、文書ＩＤは、ハッシュ生成器１０４によって生成されるそれぞれのハッシュ値ｈ（ｄ）に関連付けられる。少なくとも１つの実施形態では、ＯＲインデックス１１２は、文書ＩＤの昇順でソートされる。
【００１５】
クエリ処理システム１０１は、次いで、ＯＲインデックス１１２に記憶された各文書についてループを実行する。概して、ループの所与の反復において、現在の文書ＩＤが文書リスト１１０に含まれない場合、文書がクエリの各ＡＮＤ条件１０３を満たさなかったために、クエリ処理システムは、現在の文書をスキップする。そうでない場合、クエリ処理システム１００は、現在の文書に対するクエリについてのクエリ類似性スコア「ｓ（Ｑ，ｄ）」を初期化する（例えば、スコアｓ（Ｑ，ｄ）を０にセットし、「Ｑ」は、クエリ１０１であり、「ｄ」は、現在の文書である）。クエリ処理システム１００は、次いで、現在の文書とクエリ１０１のＯＲ条件１０２との間の全体ＯＲ類似性スコア「ｓ（Ｏ，ｄ）」を計算する（ここで、「Ｏ」は、全てのＯＲ条件１０２であり、「ｄ」は、現在の文書である）。概して、クエリ処理システムは、現在の文書についてのハッシュ値（例えば、ＯＲインデックス１１２から取り出されたｈ（ｄ））、およびクエリ１０１における全ての結合されたＯＲ条件について計算されたハッシュ値１０６（例えば、ｈ（Ｏ）、上記例の第５のハッシュ値１０６）に基づいて、全体ＯＲ類似性スコアｓ（Ｏ，ｄ）を計算する。少なくとも１つの実施形態では、クエリ処理システム１００は、ハッシュ値ｈ（Ｏ）、ｈ（ｄ）のジャカード類似性係数（Ｊａｃｃａｒｄ  ｓｉｍｉｌａｒｉｔｙ  ｃｏｅｆｆｉｃｉｅｎｔ）を用いて全体ＯＲ類似性スコアｓ（Ｏ，ｄ）を計算する。クエリ処理システム１００は、次いで、現在の文書についての全体ＯＲ類似性スコアｓ（Ｏ，ｄ）を、現在の文書に対するクエリについてのクエリ類似性スコアｓ（Ｑ，ｄ）として設定する。クエリ処理システム１００は、次いで、クエリ１０１内の各ＯＲ条件１０２についてのループを実行する。概して、各ＯＲ条件１０２について、クエリ処理システム１００は、現在のＯＲ条件に対する文書の類似度を反映するスコアｓ（ｄ，ｘ）（ここで、「ｄ」は現在の文書であり、「ｘ」は現在のＯＲ条件である）を計算する。少なくとも１つの実施形態において、スコアｓ（ｄ，ｘ）は、（ＯＲインデックス１１２から取り出された）現在の文書についてのハッシュ値ｈ（ｄ）および現在のＯＲ条件について計算されたハッシュ値１０６ｈ（ｘ）に適用される、ジャカード類似性係数を用いて計算される。スコアｓ（ｄ，ｘ）が、事前定義された閾値（例えば、０）より大きい場合、現在の文書のテキストが、現在のＯＲ条件を満たす（例えば、著者、場所などの現在の特徴を含む）可能性があり、クエリ処理システム１００は、現在のＯＲ条件についての重み値ｗ（ｘ）（ここで「ｘ」はＯＲ条件である）をクエリ類似性スコアｓ（Ｑ，ｄ）に加算、例えば、ｓ（Ｑ，ｄ）＝ｓ（Ｑ，ｄ）＋ｗ（ｘ）とする。重み値は、特徴重み１２１に記憶される。概して、特徴重み１２１は、著者、場所、タイトルなどの複数の異なる特徴（メタデータ属性またはＯＲ条件あるいはその両方とも呼ばれる）のそれぞれについての浮動小数点数値を記憶する。少なくとも１つの実施形態では、特徴重み１２１は、機械学習アルゴリズムを用いて事前定義され、または生成され、あるいはその両方である。各ＯＲ条件が処理されると、クエリ類似性��コアｓ（Ｑ，ｄ）が、現在の文書についての類似性スコアとして返され、現在の文書が検索クエリ１０１に類似する度合いを反映する。少なくとも１つの実施形態では、クエリ処理システム１００は、クエリ１０１へ応答した検索結果１１４として、文書の標示とともにクエリ類似性スコアｓ（Ｑ，ｄ）を返す。いくつかの実施形態では、クエリ処理システム１００は、最高クエリ類似性スコアｓ（Ｑ，ｄ）のリスト、および対応する文書を維持し、クエリ１０１へ応答した検索結果１１４としてリストを返す。リストのサイズは、任意の事前定義されたサイズ（例えば、１０、２０、１００など）であってもよい。
【００１６】
図２は、１つの実施形態による、類似性検索についての検索クエリの論理和条件および論理積条件のハイブリッド処理のための方法２００を示すフローチャートである。図示されるように、方法２００は、ブロック２１０において開始し、図３を参照してより詳細に説明される。ここで、クエリ処理システム１００は、コーパス１２０の文書の事前処理段階の間に、ＡＮＤインデックス１０９およびＯＲインデックス１１２を生成する。さらに、事前処理段階は、特徴重み１２１において重みを更新することも含み得る。ブロック２２０において、クエリ処理システム１００は、少なくとも１つの論理積条件を有するコーパス１２０からの文書および少なくとも１つの論理積条件を返すように指定するクエリを受信する。例えば、クエリは、コーパス１２０からの任意の照合ドキュメントが、「アリス」という例としての著者によって著され、東京という都市に合致する場所属性（例えば、発行都市、設定、著者の位置など）を有しなければならないことを示す、論理積条件「著者：アリス  ＡＮＤ  場所：東京」を指定し得る。クエリは、また、「主題：オレンジ  ＯＲ  主題：リンゴ」などの論理積条件を指定してもよく、主題としてオレンジもしくはリンゴを含む（または、概して「オレンジ」もしくは「リンゴ」という語に言及する）コーパス１２０からの文書を返すように指定する。
【００１７】
ブロック２３０において、クエリ処理システム１００は、図１を参照して上述したハイブリッド手法を用いてクエリを処理する。概して、ブロック２３０において、クエリ処理システム１００は、ＡＮＤインデックス１０９を用いてＡＮＤ条件を処理して、クエリ内の各ＡＮＤ条件を満たすコーパス１２０からの文書１１０のリスト（またはセット）を返す。並行して、クエリ処理システム１００は、クエリ内のＯＲ条件のそれぞれについてのハッシュ値、およびクエリ内の結合されたＯＲ条件についてのハッシュ値を計算することによって、ＯＲ条件を処理する。クエリ処理システム１００は、次いで、各ＡＮＤ条件を満たす文書１１０のリストでもある、ＯＲインデックス１１２内の各文書についてクエリ類似性スコアを計算する。各文書についてのクエリ類似性スコアは、クエリにおいて指定された各ＯＲ条件に対する文書の類似度に基づいて重み付けされる。ここで、重みは、特徴重み１２１に定義される。ブロック２４０において、クエリ処理システム１００は、クエリへの応答としてコーパス１２０からの文書のセットを返す。例えば、クエリ処理システム１００は、文書のセットおよび対応するクエリ類似性スコアを含むグラフィカル・ユーザ・インターフェース（ＧＵＩ）を生成し得る。少なくとも１つの実施形態において、ＧＵＩは、最高クエリ類似性スコアを有するコーパス１２０からの事前定義された数の文書を含む。
【００１８】
図３は、１つの実施形態による、文書前処理のためのブロック２１０に対応する方法３００を示すフローチャートである。図示されるように、方法３００は、ブロック３１０において開始し、複数の文書を含むコーパス１２０が、クエリ処理システム１００によって受信される。コーパス１２０内の各文書は、文書を説明する複数の特徴または属性を含み得る。例えば、特徴は、文書の著者、発行日、発行都市、主題、キーワードなどを含み得るが、これらに限定されない。ブロック３１５において、クエリ処理システム１００は、特徴重み１２１を受信し、任意選択で、特徴重み１２１内の特徴のそれぞれについて更新された特徴重み値を計算する。少なくとも１つの実施形態において、特徴重み１２１内の更新された特徴重み値が、機械学習アルゴリズムを用いて更新される。概して、特徴重み１２１内の重みは、コーパス１２０内の文書における各特徴の関連重要度または頻度あるいはその両方に基づいて、異なる特徴（例えば、著者、都市、日付など）に適用される重みを反映する。例えば、クエリ類似性スコアを計算する際に著者名が最も重要な特徴であると機械学習が判断する場合、著者名についての特徴重み１２１が、特徴重み１２１内の他の特徴と比較して最大の重みを有し得る。
【００１９】
ブロック３２０において、クエリ処理システム１００は、コーパス１２０内の各文書についてブロック３２５〜３５５を含むループを実行する。ブロック３２５において、クエリ処理システム１００は、現在の文書の特徴を判断する。クエリ処理システム１００は、現在の文書に関連付けられたメタデータに基づいて特徴を判断し得る。さらに、クエリ処理システム１００は、自然言語処理を文書のテキストに適用して、文書から追加の特徴（または属性）を抽出する。ブロック３３０において、クエリ処理システム１００は、ブロック３２５において識別される現在の文書の各特徴について、ブロック３３５〜３４０を含むループを実行する。ブロック３３５において、クエリ処理システム１００は、現在の文書が現在の特徴を含むことを反映する標示を、ＡＮＤインデックス１０９に記憶する。概して、ＡＮＤインデックス１０９は、現在の特徴の標示、およびそれぞれの特徴を含む文書ＩＤのリストを含む。ＡＮＤインデックス１０９内の文書ＩＤのリストは、文書ＩＤの昇順でソートされ得る。ブロック３４０において、クエリ処理システム１００は、特徴がさらに現在の文書に残っているかどうかを判断する。特徴がさらに残っている場合、クエリ処理システム１００は、ブロック３３０に戻り、そうでない場合、クエリ処理システム１００は、ブロック３４５に進む。
【００２０】
ブロック３４５において、クエリ処理システム１００は、ハッシュ生成器１０４を呼び出して、現在の文書についてのハッシュ値１０６（「ｈ（ｄ）」とも呼ばれる）を計算する。前述の通り、ハッシュ生成器１０４は、文書の特徴のセットに局所性鋭敏型ハッシュ関数を適用して、文書についてのハッシュ値１０６を計算する。ブロック３５０において、クエリ処理システム１００は、現在の文書ＩＤとともに、計算されたハッシュ値１０６をＯＲインデックス１１２に記憶する。少なくとも１つの実施形態では、クエリ処理システム１００は、文書ＩＤの昇順でＯＲインデックス１１２を順序付けする。ブロック３５５において、クエリ処理システム１００は、文書がさらにコーパス１２０に残っているかどうかを判断する。文書がさらに残っている場合、クエリ処理システム１００は、残っている文書を事前処理するためにブロック３２０に戻る。そうでない場合、方法３００は終了する。
【００２１】
図４は、１つの実施形態による、論理和条件および論理積条件のハイブリッド処理を用いてクエリを処理する、ブロック２３０に対応する方法４００を示すフローチャートである。図示されるように、方法４００は、ブロック４１０において開始し、図５を参照してより詳細に説明される。ここで、クエリ処理システム１００は、クエリ内の各ＡＮＤ条件を満たす各文書の文書リスト１１０を生成する。概して、クエリ処理システム１００は、ＡＮＤインデックス１０９を活用して、コーパス１２０内のどの文書がクエリ内の各ＡＮＤ条件を満たすかを判断する。文書ＩＤがＡＮＤインデックス１０９内の所与の特徴に関連付けられる場合、クエリ処理システム１００は、それぞれのＡＮＤ条件が満たされると判断する。ブロック４２０において、クエリ処理システム１００は、ハッシュ生成器１０４を呼び出して、クエリ内の各ＯＲ条件についてのハッシュ値「ｈ（ｘ）」を計算する。ここで、「ｘ」は、所与のＯＲ条件（例えば、「場所：日本」）である。ハッシュ生成器１０４は、また、クエリ内のＯＲ条件全てについてのハッシュ値「ｈ（Ｏ）」、例えば（「場所：日本  タイトル：オレンジ  キーワード：果物」）のハッシュを計算する。
【００２２】
ブロック４３０において、クエリ処理システム１００は、ＯＲインデックス１１２内の各文書についてブロック４４０〜４６０を含むループを実行する。ブロック４４０において、クエリ処理システム１００は、現在の文書の文書ＩＤが、ブロック４１０において生成された各ＡＮＤ条件を満たす文書の文書リスト１１０に含まれるかどうかを判断する。現在の文書が文書リスト１１０内にない場合、文書は、クエリの各ＡＮＤ条件を満たさず、クエリ処理システム１００は、ブロック４６０に進む（例えば、可能な検索結果として現在の文書を破棄する）。そうでない場合、クエリ処理システム１００は、ブロック４５０に進み、クエリ処理システム１００は、現在の文書についてのクエリ類似性スコアｓ（Ｑ，ｄ）を計算する。クエリ類似性スコアｓ（Ｑ，ｄ）は、現在の文書がクエリのＯＲ条件を満たす度合いを反映する。
【００２３】
ブロック４６０において、クエリ処理システム１００は、さらなる文書がＯＲインデックス１１２に残っているかどうかを判断する。文書がさらに残っている場合、クエリ処理システム１００は、ブロック４３０に戻る。そうでない場合、クエリ処理システム１００は、ブロック４７０に進み、クエリ処理システム１００は、任意選択で、ブロック４５０において計算されたクエリ類似性スコアに基づいて検索結果を順序付けする。ブロック４５０において各ＡＮＤ条件を満たすそれらの文書のみクエリ類似性スコアが計算されるため、そうすることによって、各文書がクエリ内の各ＯＲ条件を満たす度合いに基づいて結果が順序付けされる。ブロック４８０において、クエリ処理システム１００は、クエリへの応答として検索結果を返す。前述の通り、クエリ処理システム１００は、任意選択で、返される検索結果の数を、事前定義された結果の数に制限してもよく、その場合に、（クエリ類似性スコアに基づく）最高ランキング結果のみが返される。
【００２４】
図５は、１つの実施形態による、クエリ内の各ＡＮＤ条件を満たす各文書の文書リストを生成する、ブロック４１０に対応する方法５００を示すフローチャートである。図示されるように、方法５００は、ブロック５１０において開始し、クエリ処理システム１００が、クエリにおいて指定される各ＡＮＤ条件を含むクエリを生成する。例えば、クエリが「著者：スミス  ＡＮＤ  都市：ニューヨーク  ＡＮＤ  キーワード：タクシー」という標示を含んでいる場合、クエリ処理システム１００は、「スミス」という著者名、「ニューヨーク」という発行都市、および「タクシー」というキーワードを有するＡＮＤインデックス１０９からの文書ＩＤを返すように指定するクエリを生成する。ブロック５２０において、クエリ処理システム１００は、ＡＮＤインデックス１０９に対してブロック５２０において生成されたクエリを処理する。ブロック５３０において、ブロック５１０において生成されたクエリ内のＡＮＤ条件のそれぞれを満たす各文書ＩＤを含む文書のリスト１１０が、ＡＮＤインデックス１０９から返される。
【００２５】
図６は、１つの実施形態による、クエリ内の全ＯＲ条件に対する文書についてのクエリ類似性スコアを計算する、ブロック４５０に対応する方法６００を示すフローチャートである。図示されるように、方法６００は、ブロック６１０において開始し、クエリ処理システム１００が、現在の文書についてのクエリ類似性スコアＳ（Ｑ，ｄ）を０に等しく設定する。ブロック６２０において、クエリ処理システム１００は、クエリのＯＲ条件の全てに対する文書についての全体ＯＲ類似性スコアｓ（Ｏ，ｄ）を計算する。１つの実施形態において、全体ＯＲ類似性スコアｓ（Ｏ，ｄ）は、ブロック４２０において（クエリ内のＯＲ条件の全てについて）計算されるハッシュ値ｈ（Ｏ）、および文書の文書ＩＤに基づいてＯＲインデックス１１２から取り出される文書についてのハッシュ値ｈ（ｄ）に基づいて、ジャカード類似性スコアに基づき計算される。ブロック６３０において、クエリ処理システム１００は、文書についてのクエリ類似性スコアｓ（Ｑ，ｄ）をブロック６２０において計算された全体ＯＲ類似性スコアｓ（Ｏ，ｄ）に等しく設定し、例えば、ｓ（Ｑ，ｄ）＝ｓ（Ｏ，ｄ）に設定する。
【００２６】
ブロック６４０において、クエリ処理システム１００は、クエリ内の各ＯＲ条件についてブロック６５０〜６８０を含むループを実行する。ブロック６５０において、クエリ処理システム１００は、現在のＯＲ条件に対する文書についてのＯＲ類似性スコアｓ（ｄ，ｘ）を計算する。少なくとも１つの実施形態において、ｓ（ｄ，ｘ）は、ＯＲインデックス１１２から取り出される文書についてのハッシュ値ｈ（ｄ）およびブロック４２０において現在のＯＲ条件について計算されるハッシュ値１０６ｈ（ｘ）のジャカード係数に基づいて計算される。ブロック６６０において、クエリ処理システム１００は、ブロック６５０において計算されたスコアｓ（ｄ，ｘ）が、０より大きいかどうかを判断する。スコアｓ（ｄ，ｘ）が０以下である場合、クエリ処理システム１００は、ブロック６８０に進み、文書が現在のＯＲ条件を満たさない（例えば、ＯＲ条件によって指定される現在の特徴がクエリ内に存在しない）ことをスコアｓ（ｄ，ｘ）が示すときに、現在の特徴に基づいて任意の重みをクエリ類似性スコアｓ（Ｑ，ｄ）に加算することを抑制する。一方、スコアｓ（ｄ，ｘ）が０より大きい場合、文書は現在のＯＲ条件を満たす（例えば、前の例を続けると、「スミス」という著者名または「ニューヨーク」という場所を有する）可能性があり、クエリ処理システム１００は、ブロック６７０に進む。
【００２７】
ブロック６７０において、クエリ処理システム１００は、ｓ（Ｑ，ｄ）＝ｓ（Ｑ，ｄ）＋ｗ（ｘ）であり、ｗ（ｘ）が、特徴重みのうちの現在のＯＲ条件についての特徴重みであるように、現在のＯＲ条件についての特徴重み１２１からの重み値を加算することによって、クエリ類似性スコアｓ（Ｑ，ｄ）を更新する。例えば、現在の条件が文書の著者に関連する場合、ｗ（ｘ）は、特徴重み１２１において「著者」に関連付けられる特徴重みとなる。ブロック６８０において、クエリ処理システム１００は、ＯＲ条件がさらにクエリに残っているかどうかを判断する。文書がさらに残っている場合、クエリ処理システム１００は、ブロック６４０に戻る。そうでない場合、クエリ処理システム１００は、ブロック６９０に進み、クエリ類似性スコアｓ（Ｑ、ｄ）が文書に対して返される。そうすることによって、文書が各ＯＲ条件だけでなく、結合された全てのＯＲ条件も満たす度合いを考慮するスコアが返される。文書が所与のＯＲ条件を満たす場合、特徴重み１２１からの対応する重みｗ（ｘ）が、文書についてのクエリ類似性スコアｓ（Ｑ，ｄ）に加算される。同様に、ＯＲ類似性スコアｓ（Ｏ，ｄ）がブロック６２０において考慮されるため、文書がクエリの全てのＯＲ条件を満たす度合いが、クエリ類似性スコアｓ（Ｑ，ｄ）に反映される。
【００２８】
図７は、１つの実施形態による、類似性検索についての検索クエリの論理和条件および論理積条件のハイブリッド処理を実施するクエリ処理システム１００を示すブロック図である。ネットワーク化されたシステム１００は、コンピューティング・システム７０２を含む。コンピューティング・システム７０２は、また、ネットワーク７３０を介して他のコンピュータに接続され得る。概して、ネットワーク７３０は、電気通信ネットワークまたはワイド・エリア・ネットワーク（ＷＡＮ）、あるいはその両方であってもよい。具体的な実施形態では、ネットワーク７３０は、インターネットである。
【００２９】
コンピューティング・システム７０２は、概して、バス７２０を介してメモリ７０６またはストレージ７０８あるいはその両方から、命令およびデータを取得するプロセッサ７０４を含む。コンピューティング・システム７０２は、バス７２０に接続された、１つまたは複数のネットワーク・インターフェース・デバイス７１８、入力デバイス７２２、および出力デバイス７２４も含み得る。コンピューティング・システム７０２は、概して、オペレーティング・システム（図示せず）の制御下にある。オペレーティング・システムの例は、ＵＮＩＸオペレーティング・システム、Ｍｉｃｒｏｓｏｆｔ  Ｗｉｎｄｏｗｓ（Ｒ）オペレーティング・システムのバージョン、およびＬｉｎｕｘオペレーティング・システムの配布物を含む。（ＵＮＩＸは、米国および他の国々におけるＯｐｅｎ  Ｇｒｏｕｐの登録商標である。ＭｉｃｒｏｓｏｆｔおよびＷｉｎｄｏｗｓは、米国、他の国、またはその両方におけるＭｉｃｒｏｓｏｆｔ  Ｃｏｒｐｏｒａｔｉｏｎの商標である。Ｌｉｎｕｘは、米国、他の国、またはその両方におけるＬｉｎｕｓ  Ｔｏｒｖａｌｄｓの登録商標である。）さらに概して、本明細書に開示される機能をサポートする任意のオペレーティング・システムが使用されてもよい。プロセッサ７０４は、命令、ロジック、および数学的処理を実施するプログラマブル・ロジック・デバイスであり、１つまたは複数のＣＰＵを表し得る。ネットワーク・インターフェース・デバイス７１８は、コンピューティング・システム７０２がネットワーク７３０を介して他のコンピュータと通信することを可能にする、任意の種類のネットワーク通信デバイスであり得る。
【００３０】
ストレージ７０８は、ハードディスク・ドライブ、ソリッド・ステート・ドライブ、フラッシュ・メモリ・デバイス、光学媒体などを表す。概して、ストレージ７０８は、コンピューティング・システム７０２による使用のためのアプリケーション・プログラムおよびデータを記憶する。さらに、メモリ７０６およびストレージ７０８は、他の場所、例えばバス７２０を介してコンピューティング・システム７０２に連結された別のコンピュータ上に、物理的に位置するメモリを含むように考慮されてもよい。
【００３１】
入力デバイス７２２は、コンピューティング・システム７０２に入力を提供するための任意のデバイスであってもよい。例えば、キーボードまたはマウス、あるいはその両方が使用されてもよい。入力デバイス７２２は、キーボード、マウス、コントローラなどを含む多種多様な入力デバイスを表す。さらに、入力デバイス７２２は、ボタン、スイッチ、またはコンピューティング・システム７０２を制御するための他の物理デバイス機構のセットを含み得る。出力デバイス７２４は、モニタ、タッチ・スクリーン・ディスプレイなどの出力デバイスを含み得る。
【００３２】
図示するように、メモリ７０６は、クエリ・プロセッサ７１２を含み、クエリ・プロセッサ７１２は、図１〜６のクエリ処理システム１００を参照して本明細書に説明されるハイブリッド手法を用いて、クライアント・コンピューティング・システム７６０のクエリ・インターフェース７６０から受信されるクエリを処理するように概して構成されるアプリケーションである。メモリは、ハッシュ生成器１９４、ＡＮＤインデックス１０９、およびＯＲインデックス１１２をさらに含み、それぞれが上記でさらに詳細に説明されている。図示するように、ストレージ７０８は、コーパス１２０および特徴重み１２１を含み、それぞれが上記でさらに詳細に説明されている。概して、クエリ・プロセッサ７１２およびコンピューティング・システム７０２は、図１〜６を参照して上述した全ての機能性を実装するように構成される。
【００３３】
有利なことに、本明細書に開示される実施形態は、論理積条件および論理和条件を含むクエリを効率的に処理するための技術の有効な統合を提供する。上述の通り、本明細書に開示される実施形態は、各文書について計算されたハッシュ値を活用して、対応する特徴が文書内に存在するかどうかを判断し、各文書の全ての特徴を記憶する必要があるメモリ量を大幅に減少させる。同様に、クエリが多数のＡＮＤ条件を含み得るとしても、各ＡＮＤ条件を満たさない文書のＯＲ条件についての類似性スコアを計算することを抑制することによって、処理リソースが節約される。
【００３４】
本発明の多様な実施形態の説明は、例示の目的で提示されているが、網羅的であること、または開示される実施形態に限定することを意図したものではない。多くの修正および変形が、説明される実施形態の範囲から逸脱することなく当業者には明らかであろう。本明細書で使用される用語は、実施形態の原理、実用的な適用、もしくは市場で見出される技術を超える技術的改善を最もよく説明するため、または他の当業者が本明細書に開示される実施形態を理解することを可能にするために、選択された。
【００３５】
上記において、本開示に提示される実施形態に対する参照が行われている。しかしながら、本開示の範囲は、特定の説明される実施形態に限定されない。その代わりに、列挙される特徴および要素の任意の組み合わせが、異なる実施形態に関連するか否かにかかわらず、考えられる実施形態を実施および実践するように考慮される。さらに、本明細書に開示される実施形態は、他の可能な解決策を超える、または先行技術を超える利点を達成し得るが、特定の利点が所与の実施形態によって達成されるか否かは、本開示の範囲の限定ではない。よって、列挙される態様、特徴、実施形態、および利点は、単なる例示であり、特許請求の範囲において明示的に列挙されている場合を除いて、添付の特許請求の範囲の要素または限定を考慮しない。同様に、「発明」に対する参照は、本明細書に開示される任意の発明的主題の一般化として解釈されてはならず、特許請求の範囲において明示的に列挙されている場合を除いて、添付の特許請求の範囲の要素または限定であると考えられてはならない。
【００３６】
本発明の態様は、全て本明細書において「回路」、「モジュール」、または「システム」と概して呼ばれ得る、完全なハードウェア実施形態、完全なソフトウェア実施形態（ファームウェア、常駐ソフトウェア、マイクロコードなどを含む）、またはソフトウェアおよびハードウェア態様を組み合わせた実施形態の形式を取ってもよい。
【００３７】
本発明は、システム、方法、またはコンピュータ・プログラム製品、あるいはその組み合わせであってもよい。コンピュータ・プログラム製品は、プロセッサに本発明の態様を実行させるためのコンピュータ可読プログラム命令をその上に有するコンピュータ可読記憶媒体（または複数の媒体）を含み得る。
【００３８】
コンピュータ可読記憶媒体は、命令実行デバイスにより使用するための命令を保持し、記憶し得る有形デバイスであり得る。コンピュータ可読記憶媒体は、例えば、電子記憶デバイス、磁気記憶デバイス、光学記憶デバイス、電磁気記憶デバイス、半導体記憶デバイス、または前述したものの任意の適当な組み合わせであってもよいが、これらに限定されない。コンピュータ可読記憶媒体のより具体的な例の非網羅的リストは、ポータブル・コンピュータ・ディスケット、ハード・ディスク、ランダム・アクセス・メモリ（ＲＡＭ）、読み取り専用メモリ（ＲＯＭ）、消去可能プログラマブル読み取り専用メモリ（ＥＰＲＯＭまたはフラッシュ・メモリ）、静的ランダム・アクセス・メモリ（ＳＲＡＭ）、ポータブル・コンパクト・ディスク読み取り専用メモリ（ＣＤ−ＲＯＭ）、デジタル多用途ディスク（ＤＶＤ）、メモリ・スティック、フロッピー（Ｒ）・ディスク、パンチカードまたはその上に記録された命令を有する溝内の隆起構造などの機械的に符号化されたデバイス、および前述したものの任意の適当な組み合わせを含む。本明細書で用いられるコンピュータ可読記憶媒体は、本来、電波もしくは他の自由伝播する電磁波、導波管もしくは他の送信媒体を通って伝播する電磁波（例えば、光ファイバ・ケーブルを通過する光パルス）、または電線を通って送信される電気信号などの、一過性信号であると解釈されるべきではない。
【００３９】
本明細書で説明されるコンピュータ可読プログラム命令は、コンピュータ可読記憶媒体からそれぞれのコンピューティング／処理デバイスに、またはネットワーク、例えば、インターネット、ローカル・エリア・ネットワーク、ワイド・エリア・ネットワーク、もしくはワイヤレス・ネットワーク、またはその組み合わせを介して外部コンピュータまたは外部ストレージ・デバイスに、ダウンロードされ得る。ネットワークは、銅伝送ケーブル、光伝送ファイバ、ワイヤレス伝送、ルータ、ファイアウォール、スイッチ、ゲートウェイ・コンピュータ、またはエッジ・サーバ、あるいはその組み合わせを含み得る。各コンピューティング／処理デバイス内のネットワーク・アダプタ・カードまたはネットワーク・インターフェースは、コンピュータ可読プログラム命令をネットワークから受信し、それぞれのコンピューティング／処理デバイス内のコンピュータ可読記憶媒体の記憶用にコンピュータ可読プログラム命令を転送する。
【００４０】
本発明の動作を実行するためのコンピュータ可読プログラム命令は、アセンブラ命令、命令セット・アーキテクチャ（ＩＳＡ）命令、機械命令、機械依存命令、マイクロコード、ファームウェア命令、状態設定データ、またはＳｍａｌｌｔａｌｋ（Ｒ）、Ｃ＋＋などのオブジェクト指向プログラミング言語、および「Ｃ」プログラミング言語もしくは類似のプログラミング言語などの従来の手続き型プログラミング言語を含む、１つもしくは複数のプログラミング言語の任意の組み合わせで書かれたソース・コードもしくはオブジェクト・コードのいずれかであってもよい。コンピュータ可読プログラム命令は、ユーザのコンピュータ上で完全に、ユーザのコンピュータ上で部分的に、スタンドアロン・ソフトウェア・パッケージとして、ユーザのコンピュータ上で部分的にかつリモート・コンピュータ上で部分的に、またはリモート・コンピュータもしくはサーバ上で完全に、実行してもよい。後者のシナリオでは、リモート・コンピュータは、ローカル・エリア・ネットワーク（ＬＡＮ）またはワイド・エリア・ネットワーク（ＷＡＮ）を含む任意の種類のネットワークを通して、ユーザのコンピュータに接続されてもよい。あるいは、接続は、（例えば、インターネット・サービス・プロバイダを使用してインターネットを通して）外部コンピュータに対して行われてもよい。いくつかの実施形態では、例えば、プログラマブル・ロジック回路、フィールド・プログラマブル・ゲート・アレイ（ＦＰＧＡ）、またはプログラマブル・ロジック・アレイ（ＰＬＡ）を含む電子回路は、本発明の態様を実施するために、コンピュータ可読プログラム命令の状態情報を利用して電子回路を個別化することによって、コンピュータ可読プログラム命令を実行し得る。
【００４１】
本発明の態様は、発明の実施形態による、方法、装置（システム）、およびコンピュータ・プログラム製品のフローチャート図またはブロック図あるいはその両方を参照して、本明細書において説明される。フローチャート図またはブロック図あるいはその両方の各ブロック、およびフローチャート図またはブロック図あるいはその両方のブロックの組み合わせは、コンピュータ可読プログラム命令によって実施され得ると理解されたい。
【００４２】
コンピュータまたは他のプログラマブル・データ処理装置のプロセッサによって実行する命令が、フローチャートまたはブロック図あるいはその両方の１つまたは複数のブロックにおいて指定される機能／動作を実施する手段を作り出すように、これらのコンピュータ可読プログラム命令は、汎用コンピュータ、専用コンピュータ、または機械を生成する他のプログラマブル・データ処理装置のプロセッサに提供され得る。コンピュータ可読記憶媒体に記憶される命令を有するコンピュータ可読記憶媒体が、フローチャートまたはブロック図あるいはその両方の１つまたは複数のブロックにおいて指定される機能／動作の態様を実施する命令を含む製品を含むように、これらのコンピュータ可読プログラム命令は、また、コンピュータ、プログラマブル・データ処理装置、または他のデバイス、あるいはその組み合わせが特定のやり方で機能するように指示し得る、コンピュータ可読記憶媒体に記憶され得る。
【００４３】
コンピュータ、他のプログラマブル装置、または他のデバイス上で実行する命令が、フローチャートまたはブロック図あるいはその両方の１つまたは複数のブロックにおいて指定される機能／動作を実施するように、コンピュータ可読プログラム命令は、また、一連の動作ステップが、コンピュータ実装されたプロセスを生成するためにコンピュータ、他のプログラマブル装置、または他のデバイス上で実施されるようにするために、コンピュータ、他のプログラマブル・データ処理装置、または他のデバイス上にロードされ得る。
【００４４】
図面中のフローチャートおよびブロック図は、本発明の様々な実施形態によるシステム、方法、およびコンピュータ・プログラム製品の考えられる実装のアーキテクチャ、機能性、および動作を示している。この点に関して、フローチャートまたはブロック図の各ブロックは、指定された論理機能を実施するための１つまたは複数の実行可能命令を含む、モジュール、セグメント、または命令の一部を表し得る。いくつかの代替的な実装において、ブロック内に記載された機能は、図面中に記載された順序以外で発生し得る。例えば、連続して示される２つのブロックが、実際には、実質的に同時に実行されてもよく、または、ブロックが、関係する機能性次第で逆の順序で実行されることがあってもよい。ブロック図またはフローチャート図あるいはその両方の各ブロック、およびブロック図またはフローチャート図あるいはその両方におけるブロックの組み合わせが、指定された機能もしくは動作を実施するかまたは専用ハードウェアおよびコンピュータ命令の組み合わせを実行する、専用ハードウェア・ベース・システムによって実施され得ることにも留意されたい。
【００４５】
発明の実施形態は、クラウド・コンピューティング・インフラストラクチャを通して、エンド・ユーザに提供され得る。クラウド・コンピューティングは、概して、ネットワーク上のサービスとしてのスケーラブルなコンピューティング・リソースの提供をいう。より正式には、クラウド・コンピューティングは、コンピューティング・リソースとその基礎となる技術的アーキテクチャ（例えば、サーバ、ストレージ、ネットワーク）との間の抽象概念を提供するコンピューティング・ケイパビリティとして定義されてもよく、最小限度の管理努力またはサービス・プロバイダ・インタラクションで急速に提供およびリリースされ得る、構成可能なコンピューティング・リソースの共有プールへの便利なオンデマンド・ネットワーク・アクセスを可能にする。したがって、クラウド・コンピューティングは、コンピューティング・リソースを提供するために使用される基礎となる物理的システム（またはそれらのシステムの場所）に関係なく、ユーザが「クラウド」内の仮想コンピューティング・リソースに（例えば、ストレージ、データ、アプリケーション、および完全に仮想化されたコンピューティング・システムにさえ）アクセスすることを可能にする。
【００４６】
典型的には、クラウド・コンピューティング・リソースは、ペイパーユーズ単位でユーザに提供され、その場合、ユーザは、実際に使用されたコンピューティング・リソース（例えば、ユーザによって消費されたストレージ空間の量、またはユーザによってインスタンス化された仮想化システムの数）のみに対して課金される。ユーザは、クラウド内に存在するリソースのいずれかに、いつでも、かつインターネットをわたってどこからでもアクセス可能である。本発明の文脈において、ユーザは、クラウド内で利用可能なアプリケーションまたは関連データにアクセスし得る。例えば、クエリ・プロセッサ７１２は、クラウド内のコンピューティング・システム上で実行可能であり、上述のようなハイブリッド手法を用いてクエリを処理し得る。このような場合、クエリ・プロセッサ７１２は、ＡＮＤインデックス１０９およびＯＲインデックス１１２を生成し、クラウド内のストレージ位置にインデックス１０９、１１２を記憶する。そうすることによって、ユーザは、クラウドに接続されたネットワーク（例えば、インターネット）にアタッチされた任意のコンピューティング・システムからこの情報にアクセスすることが可能となる。
【００４７】
上記は、本発明の実施形態を対象とするが、発明の他の実施形態、およびさらなる実施形態が、その基本的範囲および以下の特許請求の範囲によって決定される範囲から逸脱することなく考案され得る。
【図１】
2021500664.tif 000003
【図２】
2021500664.tif 000004
【図３】
2021500664.tif 000005
【図４】
2021500664.tif 000006
【図５】
2021500664.tif 000007
【図６】
2021500664.tif 000008
【図７】
2021500664.tif 000009
【手続補正書】
【提出日】令和2年5月1日(2020.5.1)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
ＡＮＤ条件およびＯＲ条件を指定するクエリを受信することと、
ＡＮＤインデックス構造に基づいて、前記クエリの前記ＡＮＤ条件を満たす、コーパス内の複数の文書のうちの文書のセットを判断することと、
プロセッサによって、前記文書のセット内の第１の文書についてクエリ類似性スコアを計算することであって、前記クエリ類似性スコアが、前記クエリの前記ＯＲ条件について計算される第１のハッシュ値、前記ＯＲ条件についての重み値、およびＯＲインデックスにおいて指定される前記第１の文書についての第２のハッシュ値に基づく、前記計算することと、
前記クエリへの応答として前記第１の文書の標示および前記クエリ類似性スコアを返すことと
を含む方法。
【請求項２】
前記ＡＮＤインデックスは、複数の特徴のそれぞれの特徴を含む各文書についての文書識別子（ＩＤ）を記憶するように構成されるポスティング・リストを含み、前記ＯＲインデックスは、前記複数の文書のそれぞれについてのそれぞれのハッシュ値を含み、前記第１のハッシュ値、前記第２のハッシュ値、および前記ＯＲインデックス内の前記複数のハッシュ値は、局所性鋭敏型ハッシュ関数に基づいて計算される、請求項１に記載の方法。
【請求項３】
前記クエリは、複数のＡＮＤ条件を指定し、判断された前記文書のセットは、前記複数のＡＮＤ条件のそれぞれを満たし、前記文書のセットを判断することは、
前記クエリにおいて指定される前記複数のＡＮＤ条件のそれぞれの標示を含む検索クエリを生成することと、
前記ＡＮＤインデックスに対して前記検索クエリを処理することと、
前記ＡＮＤインデックスから、前記文書のセット内の各文書の前記文書ＩＤを含む前記文書のセットを受信することと、を含む、請求項２に記載の方法。
【請求項４】
前記クエリは、複数のＯＲ条件を指定し、前記クエリ類似性スコアを計算することは、
（ｉ）前記複数のＯＲ条件の各ＯＲ条件、および（ｉｉ）前記複数のＯＲ条件、についてのそれぞれのハッシュ値を計算することと、
前記複数のＯＲ条件に対する前記第１の文書についての全体類似性スコアを、前記複数のＯＲ条件についての前記ハッシュ値、および前記ＯＲインデックスから受信される前記第１の文書についての前記第２のハッシュ値に基づいて計算することと、
各ＯＲ条件に対する前記第１の文書についてのそれぞれのＯＲ類似性スコアを、前記ＯＲインデックスから受信される前記第１の文書についての前記第２のハッシュ値、および前記それぞれのＯＲ条件についての前記ハッシュ値に基づいて計算することと、
事前定義された閾値を超えるそれぞれのＯＲ類似性スコアについて、前記それぞれのＯＲ条件に関連付けられた重みを前記全体類似性スコアに加算することと、
前記全体類似性スコアを前記クエリ類似性スコアとして返すことと、を含む、請求項２に記載の方法。
【請求項５】
前記第１の文書についての前記類似性スコアを計算する前に、
前記ＯＲインデックスから前記第１の文書についての文書識別子（ＩＤ）を受信することと、
前記第１の文書についての前記文書ＩＤが前記文書のセットに含まれると判断することと
をさらに含む、請求項１に記載の方法。
【請求項６】
前記コーパス内の前記複数の文書の第２の文書についての文書識別子（ＩＤ）を前記ＯＲインデックスから受信することと、
前記第２の文書についての前記文書ＩＤが前記文書のセットに含まれないと判断することと、
前記第２の文書についてのクエリ類似性スコアを計算することを抑制することと、
前記クエリへの応答として前記第２の文書を返すことを抑制することと
をさらに含む、請求項５に記載の方法。
【請求項７】
前記ＡＮＤインデックスおよび前記ＯＲインデックスは、前記コーパス内の前記複数の文書の前処理段階の間に生成される、請求項１に記載の方法。
【請求項８】
プロセッサと、
メモリであって、前記プロセッサによる実行時に、
ＡＮＤ条件およびＯＲ条件を指定するクエリを受信することと、
ＡＮＤインデックス構造に基づいて、前記クエリの前記ＡＮＤ条件を満たす、コーパス内の複数の文書のうちの文書のセットを判断することと、
前記文書のセット内の第１の文書についてクエリ類似性スコアを計算することであって、前記クエリ類似性スコアは、前記クエリの前記ＯＲ条件について計算される第１のハッシュ値、前記ＯＲ条件についての重み値、およびＯＲインデックスにおいて指定される前記第１の文書についての第２のハッシュ値に基づく、前記計算することと、
前記クエリへの応答として前記第１の文書の標示および前記クエリ類似性スコアを返すことと
を含む動作を実施するプログラムを含む前記メモリと
を備えるシステム。
【請求項９】
前記ＡＮＤインデックスは、複数の特徴のそれぞれの特徴を含む各文書についての文書識別子（ＩＤ）を記憶するように構成されるポスティング・リストを含み、前記ＯＲインデックスは、前記複数の文書のそれぞれについてのそれぞれのハッシュ値を含み、前記第１のハッシュ値、前記第２のハッシュ値、および前記ＯＲインデックス内の前記複数のハッシュ値は、局所性鋭敏型ハッシュ関数に基づいて計算される、請求項８に記載のシステム。
【請求項１０】
前記クエリは、複数のＡＮＤ条件を指定し、前記判断された文書のセットは、前記複数のＡＮＤ条件のそれぞれを満たし、前記文書のセットを判断することは、
前記クエリにおいて指定される前記複数のＡＮＤ条件のそれぞれの標示を含む検索クエリを生成することと、
前記ＡＮＤインデックスに対して前記検索クエリを処理することと、
前記ＡＮＤインデックスから、前記文書のセット内の各文書の前記文書ＩＤを含む前記文書のセットを受信することと
を含む、請求項９に記載のシステム。
【請求項１１】
前記クエリは、複数のＯＲ条件を指定し、前記クエリ類似性スコアを計算することは、
（ｉ）前記複数のＯＲ条件の各ＯＲ条件、および（ｉｉ）前記複数のＯＲ条件、についてのそれぞれのハッシュ値を計算することと、
前記複数のＯＲ条件に対する前記第１の文書についての全体類似性スコアを、前記複数のＯＲ条件についての前記ハッシュ値、および前記ＯＲインデックスから受信される前記第１の文書についての前記第２のハッシュ値に基づいて計算することと、
各ＯＲ条件に対する前記第１の文書についてのそれぞれのＯＲ類似性スコアを、前記ＯＲインデックスから受信される前記第１の文書についての前記第２のハッシュ値、および前記それぞれのＯＲ条件についての前記ハッシュ値に基づいて計算することと、
事前定義された閾値を超えるそれぞれのＯＲ類似性スコアについて、前記それぞれのＯＲ条件に関連付けられた重みを前記全体類似性スコアに加算することと、
前記全体類似性スコアを前記クエリ類似性スコアとして返すことと
を含む、請求項９に記載のシステム。
【請求項１２】
前記第１の文書についての前記類似性スコアを計算する前に、前記動作が、
前記ＯＲインデックスから前記第１の文書についての文書識別子（ＩＤ）を受信することと、
前記第１の文書についての前記文書ＩＤが前記文書のセットに含まれると判断することと
をさらに含む、請求項８に記載のシステム。
【請求項１３】
前記動作は、
前記コーパス内の前記複数の文書の第２の文書についての文書識別子（ＩＤ）を前記ＯＲインデックスから受信することと、
前記第２の文書についての前記文書ＩＤが前記文書のセットに含まれないと判断することと、
前記第２の文書についてのクエリ類似性スコアを計算することを抑制することと、
前記クエリへの応答として前記第２の文書を返すことを抑制することと
をさらに含む、請求項１２に記載のシステム。
【請求項１４】
前記ＡＮＤインデックスおよび前記ＯＲインデックスが、前記コーパス内の前記複数の文書の前処理段階の間に生成される、請求項８に記載のシステム。
【請求項１５】
具現化されたコンピュータ可読プログラム・コードを有する非一過性コンピュータ可読記憶媒体であって、前記コンピュータ可読プログラム・コードは、
ＡＮＤ条件およびＯＲ条件を指定するクエリを受信することと、
ＡＮＤインデックス構造に基づいて、前記クエリの前記ＡＮＤ条件を満たす、コーパス内の複数の文書のうちの文書のセットを判断することと、
前記文書のセット内の第１の文書についてクエリ類似性スコアを計算することであって、前記クエリ類似性スコアは、前記クエリの前記ＯＲ条件について計算される第１のハッシュ値、前記ＯＲ条件についての重み値、およびＯＲインデックスにおいて指定される前記第１の文書についての第２のハッシュ値に基づく、前記計算することと、
前記クエリへの応答として前記第１の文書の標示および前記クエリ類似性スコアを返すことと
を含む動作を実施するためにプロセッサによって実行可能である、前記非一過性コンピュータ可読記憶媒体
を含む、コンピュータ・プログラム。
【請求項１６】
前記ＡＮＤインデックスが、複数の特徴のそれぞれの特徴を含む各文書についての文書識別子（ＩＤ）を記憶するように構成されるポスティング・リストを含み、前記ＯＲインデックスが、前記複数の文書のそれぞれについてのそれぞれのハッシュ値を含み、前記第１のハッシュ値、前記第２のハッシュ値、および前記ＯＲインデックス内の前記複数のハッシュ値が、局所性鋭敏型ハッシュ関数に基づいて計算される、請求項１５に記載のコンピュータ・プログラム。
【請求項１７】
前記クエリが、複数のＡＮＤ条件を指定し、前記判断された文書のセットが、前記複数のＡＮＤ条件のそれぞれを満たし、前記文書のセットを判断することが、
前記クエリにおいて指定される前記複数のＡＮＤ条件のそれぞれの標示を含む検索クエリを生成することと、
前記ＡＮＤインデックスに対して前記検索クエリを処理することと、
前記ＡＮＤインデックスから、前記文書のセット内の各文書の前記文書ＩＤを含む前記文書のセットを受信することと
を含む、請求項１６に記載のコンピュータ・プログラム。
【請求項１８】
前記クエリは、複数のＯＲ条件を指定し、前記クエリ類似性スコアを計算することは、
（ｉ）前記複数のＯＲ条件の各ＯＲ条件、および（ｉｉ）前記複数のＯＲ条件、についてのそれぞれのハッシュ値を計算することと、
前記複数のＯＲ条件に対する前記第１の文書についての全体類似性スコアを、前記複数のＯＲ条件についての前記ハッシュ値、および前記ＯＲインデックスから受信される前記第１の文書についての前記第２のハッシュ値に基づいて計算することと、
各ＯＲ条件に対する前記第１の文書についてのそれぞれのＯＲ類似性スコアを、前記ＯＲインデックスから受信される前記第１の文書についての前記第２のハッシュ値、および前記それぞれのＯＲ条件についての前記ハッシュ値に基づいて計算することと、
事前定義された閾値を超えるそれぞれのＯＲ類似性スコアについて、前記それぞれのＯＲ条件に関連付けられた重みを前記全体類似性スコアに加算することと、
前記全体類似性スコアを前記クエリ類似性スコアとして返すことと、を含む、請求項１６に記載のコンピュータ・プログラム。
【請求項１９】
前記第１の文書についての前記類似性スコアを計算する前に、前記動作が、
前記ＯＲインデックスから前記第１の文書についての文書識別子（ＩＤ）を受信することと、
前記第１の文書についての前記文書ＩＤが前記文書のセットに含まれると判断することと
をさらに含む、請求項１５に記載のコンピュータ・プログラム。
【請求項２０】
前記ＡＮＤインデックスおよび前記ＯＲインデックスは、前記コーパス内の前記複数の文書の前処理段階の間に生成され、前記動作は、
前記コーパス内の前記複数の文書の第２の文書についての文書識別子（ＩＤ）を前記ＯＲインデックスから受信することと、
前記第２の文書についての前記文書ＩＤが前記文書のセットに含まれないと判断することと、
前記第２の文書についてのクエリ類似性スコアを計算することを抑制することと、
前記クエリへの応答として前記第２の文書を返すことを抑制することと、
をさらに含む、請求項１９に記載のコンピュータ・プログラム。

【国際調査報告】
2021500664.tif 000010
2021500664.tif 000011