(57)【特許請求の範囲】
【請求項１】
コンピュータによって実行されるサンプリング解析のための方法であって、
複数のユーザによって提示された複数のクエリキーワードに関連するページビュー（ＰＶ）値に従って、前記複数のクエリキーワードを複数のクエリキーワードサブセットに分類し、前記複数のクエリキーワードの分類は、
前記複数のクエリキーワードに関連する前記ＰＶ値を順序付け、
同一のＰＶ値を有するクエリキーワードを、前記複数のクエリキーワードサブセットの内のそれぞれのサブセット内にグループ化すること、を含み、
前記複数のクエリキーワードサブセット内の各クエリキーワードサブセット内のそれぞれの複数のクエリキーワードのそれぞれの複数のサンプルレートを決定し、
前記複数のサンプルレートのそれぞれに従って、前記複数のクエリキーワードサブセット内でクエリデータをサンプリングし、前記サンプリングは、前記複数のクエリキーワードサブセットの全てをサンプリングすることを含み、
前記サンプリングされたクエリデータを出力すること、
を備える、方法。
【請求項２】
請求項１に記載の方法であって、クエリデータのサンプリングは、前記それぞれの複数のクエリキーワードの実際の分布と実質的に類似するサンプルクエリキーワードのサンプル分布を生成する、方法。
【請求項３】
請求項１に記載の方法であって、前記ＰＶ値は、事前設定された期間内の検索プラットフォームにおける前記複数のクエリキーワードの内のそれぞれのキーワードの出現回数に対応する、方法。
【請求項４】
請求項１に記載の方法であって、前記それぞれの複数のサンプルレートは、前記複数のクエリキーワードサブセット内の各クエリキーワードサブセットのサンプリング中に用いられるそれぞれの複数のサンプルサイズを含む、方法。
【請求項５】
請求項４に記載の方法であって、前記それぞれの複数のサンプルサイズは、
前記複数のクエリキーワードサブセット内の各クエリキーワードサブセットに関連するそれぞれの複数のサンプル確率を決定し、
予め定められたクエリキーワードのサンプルサイズおよび前記それぞれの複数のサンプル確率に従って、前記それぞれの複数のサンプルサイズを決定すること、によって決定される、方法。
【請求項６】
請求項５に記載の方法であって、前記それぞれの複数のサンプル確率を決定は、
前記クエリキーワードサブセットのＰＶ値の合計（ＳＰＶ値）を決定し、
前記ＳＰＶ値に従って、前記複数のクエリキーワードサブセット内のＰＶ値の合計（ＴＰＶ値）を決定し、
前記ＳＰＶ値および前記ＴＰＶ値に従って、前記クエリキーワードサブセットのサンプル確率を決定すること、
を備える、方法。
【請求項７】
請求項４に記載の方法であって、前記サンプルサイズに従って前記クエリキーワードサブセット内でクエリデータをサンプリングするために、無作為サンプリングが用いられる、方法。
【請求項８】
請求項７に記載の方法であって、前記無作為サンプリングは、乱数を生成し、前記乱数に関連付けられた前記クエリキーワードサブセット内のクエリキーワードを選択すること、を含む、方法。
【請求項９】
サンプリング解析システムであって、
プロセッサであって、
複数のユーザによって提示された複数のクエリキーワードに関連するページビュー（ＰＶ）値に従って、前記複数のクエリキーワードを複数のクエリキーワードサブセットに分類し、前記複数のクエリキーワードの分類は、
前記複数のクエリキーワードに関連する前記ＰＶ値を順序付けることと、
同一のＰＶ値を有するクエリキーワードを、前記複数のクエリキーワードサブセットの内のそれぞれのサブセット内にグループ化することと、を含み、
前記複数のクエリキーワードサブセット内の各クエリキーワードサブセット内のそれぞれの複数のクエリキーワードのそれぞれの複数のサンプルレートを決定し、
前記複数のサンプルレートのそれぞれに従って、前記複数のクエリキーワードサブセット内でクエリデータをサンプリングし、前記サンプリングは、前記複数のクエリキーワードサブセットの全てをサンプリングすることを含み、
前記サンプリングされたクエリデータを出力するよう構成されたプロセッサと、
前記プロセッサに接続され、前記プロセッサに命令を提供するよう構成されたメモリと、
を備える、システム。
【請求項１０】
請求項９に記載のシステムであって、前記プロセッサは、前記それぞれの複数のクエリキーワードの実際の分布と実質的に類似するサンプルクエリキーワードのサンプル分布を生成するように前記クエリデータをサンプリングするよう構成される、システム。
【請求項１１】
請求項９に記載のシステムであって、前記ＰＶ値は、事前設定された期間内の検索プラットフォームにおける前記複数のクエリキーワードの内のそれぞれのキーワードの出現回数に対応する、システム。
【請求項１２】
請求項９に記載のシステムであって、前記それぞれの複数のサンプルレートは、前記複数のクエリキーワードサブセットの内のそれぞれのサブセットのサンプリング中に用いられるそれぞれの複数のサンプルサイズを含む、システム。
【請求項１３】
請求項１２に記載のシステムであって、前記それぞれの複数のサンプルサイズは、
前記複数のクエリキーワードサブセット内の各クエリキーワードサブセットに関連するそれぞれの複数のサンプル確率を決定し、
予め定められたクエリキーワードのサンプルサイズおよび前記それぞれの複数のサンプル確率に従って、前記それぞれの複数のサンプルサイズを決定すること、によって決定される、システム。
【請求項１４】
請求項１３に記載のシステムであって、前記それぞれの複数のサンプル確率の決定は、
前記クエリキーワードサブセットのＰＶ値の合計（ＳＰＶ値）を決定し、
前記ＳＰＶ値に従って、前記複数のクエリキーワードサブセット内のＰＶ値の合計（ＴＰＶ値）を決定し、
前記ＳＰＶ値および前記ＴＰＶ値に従って、前記クエリキーワードサブセットのサンプル確率を決定すること、
を備える、システム。
【請求項１５】
請求項１２に記載のシステムであって、前記サンプルサイズに従って前記クエリキーワードサブセット内でクエリデータをサンプリングするために、無作為サンプリングが用いられる、システム。
【請求項１６】
請求項１５に記載のシステムであって、前記無作為サンプリングは、乱数を生成し、前記乱数に関連付けられた前記クエリキーワードサブセット内のクエリキーワードを選択すること、を含む、システム。
【請求項１７】
サンプリング解析のためのコンピュータプログラムであって、
複数のユーザによって提示された複数のクエリキーワードに関連するページビュー（ＰＶ）値に従って、前記複数のクエリキーワードを複数のクエリキーワードサブセットに分類するための機能と、記複数のクエリキーワードの分類は、
前記複数のクエリキーワードに関連する前記ＰＶ値を順序付けるための機能と、
同一のＰＶ値を有するクエリキーワードを、前記複数のクエリキーワードサブセットの内のそれぞれのサブセット内にグループ化するための機能とを含み、
前記複数のクエリキーワードサブセット内の各クエリキーワードサブセットに含まれるそれぞれの複数のクエリキーワードのそれぞれの複数のサンプルレートを決定するための機能と、
前記複数のサンプルレートのそれぞれに従って、前記複数のクエリキーワードサブセット内でクエリデータをサンプリングするための機能と、前記サンプリングするための機能は、前記複数のクエリキーワードサブセットの全てをサンプリングすることを含み、
前記サンプリングされたクエリデータを出力するための機能と、
をコンピュータによって実現させる、コンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
［関連出願］
本出願は、参照によって本明細書に全体を組み込まれる、発明の名称を「METHOD, SYSTEM AND DEVICE FOR SAMPLING ANALYSIS（サンプリング解析のための方法、システムおよび装置）」とする、２００９年１月２２日出願の中華人民共和国特許出願２００９１０００１１１７．０の優先権の利益を主張する。
【０００２】
本発明は、概して、ネットワーク技術の分野に関し、特に、サンプリング解析のための方法、システム、および、デバイスに関する。
【背景技術】
【０００３】
検索エンジンは、通常、ユーザのページビューを記録するよう構成される。大規模な検索エンジンでは、ある一定の期間におけるユーザのページビューが、膨大な量のデータを含む場合があり、ユーザクエリキーワードの大部分は繰り返しのクエリである。例えば、最新のニュースがあると、様々なユーザによってクエリされるクエリキーワードは、通常、類似および同一のものにさえなる。検索エンジンサービスプロバイダは、通常、サービス向上のためにユーザページビューを処理する。１つの基本的な処理技術は、同一のクエリキーワードをマージする技術であり、それにより、データストレージが占有する大量のメモリまたはディスクスペースが低減される。例えば、最近、「Ａｌｉｂａｂａ」というクエリキーワードで２０００件のクエリがあったとすると、結果として生じるマージデータ形式は、「Ａｌｉｂａｂａ  ２０００」となり、ここで、「Ａｌｉｂａｂａ」は、ユーザクエリキーワードを表し、「２０００」は、ある期間内のクエリログにおけるクエリキーワードの出現回数を表す。しかしながら、予備的に処理された統計データを得るためにクエリキーワードをサンプリングして、クエリキーワードの実際の分布に近いサンプルデータを作る方法には課題が残る。
【０００４】
既存のシステムでは、「クエリキーワード，ページビュー（ＰＶ）」のフォーマットのデータについて統計解析を行うために、システムは、まず、全クエリキーワード内での各クエリキーワードの割合を算出する。ＰＶは、検索プラットフォームにおける特定のクエリキーワードの出現回数を表す。クエリデータ「Ａｌｉｂａｂａ  ２０００」を例にとると、システムは、まず、クエリキーワードコレクション内の全クエリキーワードのＰＶ値の合計を算出する。ＰＶ値の合計が１００万である、つまり、システム内の全ユーザについて１００万のクエリキーワードが存在すると仮定すれば、全クエリキーワード中のクエリキーワード「Ａｌｉｂａｂａ」の割合を算出すると、２０００／１００００００＝０．００２５という割合が得られる。この割合は、全クエリキーワードの中でクエリキーワード「Ａｌｉｂａｂａ」が無作為にサンプリングされる確率が０．００２５であることを意味する。全クエリキーワードのサンプリング確率が決定されると、全クエリキーワードのコレクション内の特定のクエリキーワードが、クエリキーワードのサンプリング確率に従ってサンプリングされる。対応するクエリキーワードの最終的なサンプリングデータの解析に基づいて、ユーザクエリキーワードの分布が決定されうる。例えば、合計１００万ＰＶを有するコレクションにおいて、１００００ＰＶが、解析すべきサンプルとして選択される。特定のクエリキーワードサンプリング処理は以下の通りである。サンプリング確率に従って、クエリキーワードのサンプルサイズを決定する、すなわち、［クエリキーワードのサンプルサイズ］＝［期待サンプルサイズ］＊［クエリキーワードのサンプル確率］（ここで、クエリキーワードのサンプルサイズおよび期待サンプルサイズは正の整数）。例えば、クエリキーワード「Ａｌｉｂａｂａ」のサンプル確率を０．００２５とすると、キーワード「Ａｌｉｂａｂａ」での１００００＊０．００２５＝２５回のクエリが、クエリキーワードサンプルとして選択される。同様に、他のクエリキーワードのサンプルサイズが上述の公式に従って取得され、全クエリキーワードのサンプルサイズの合計は１００００となる。１００万ページビューと比べると、データ解析のために１０，０００のサンプルページビューを解析および処理すれば、作業負荷および計算手順が大幅に削減されて、効率が高くなる。
【０００５】
既存の技術には多くの問題点がある。例えば、サンプリングされるデータサイズが大きい場合には、既存の技術で用いられるサンプリング解析方法は、ある程度まで実際のデータ分布をシミュレートしうる。しかし、サンプリングされるデータサイズが中規模または小規模である場合、サンプリング結果と実際のデータ分布との間に大きな歪みが生じる。これは、多くの統計データ分布が「ロングテール」という特徴、すなわち、出現頻度の低いエンティティまたはデータが多いという特徴を持っているからである。具体的には、ユーザが検索エンジンを用いてキーワードをクエリする時に、ユーザによってクエリされるクエリキーワードの多くは、数回しか出現することがなく、例えば、一部のクエリキーワードの出現は、１または２回である。一部のクエリキーワードの出現頻度は非常に低いが、出現頻度の低いクエリキーワードを合計すると、クエリキーワードの全体サイズの大部分を占める。ロングテール分布については、既存のサンプリング解析方法を用いると、出現頻度の低いクエリキーワードが効果的にサンプリングされない。例えば、応用例の目標が２０００のクエリワードをサンプリングすることであり、ＰＶ値の合計が１００万であるとする。クエリキーワードとして、「ｅｃｏｍｍｅｒｃｅ  １」と例にとると、サンプリング確率は１００万分の１であり、かかる低頻度クエリキーワードは、上述の方法ではサンプリングできない。既存のサンプリング解析方法によって得られたサンプリングデータと、実際のデータ分布との間の差が大きいために、ユーザ需要情報および市場動向が、検索エンジンでのクエリキーワードのサンプリング解析によって使いこなされないことが多く、オンライン商取引は制約される。
【図面の簡単な説明】
【０００６】
【図１】サンプリング解析システムの一実施形態を示すブロック図。
【図２】大規模な検索エンジンクエリデータのサンプリング解析のための処理の一実施形態を示すフローチャート。
【図３】各クエリキーワードサブセットのサンプルレートを算出するための処理の一実施形態を示すフローチャート。
【図４】クエリキーワードをサンプリングするための処理の一実施形態を示すフローチャート。
【図５】無作為サンプリング処理の一実施形態を示すフローチャート。
【図６】サンプリング解析器の一実施形態を示すブロック図。
【発明を実施するための形態】
【０００７】
本発明は、処理、装置、システム、物質の組成、コンピュータ読み取り可能な格納媒体上に具現化されたコンピュータプログラム製品、および／または、プロセッサ（プロセッサに接続されたメモリに格納および／またはそのメモリによって提供される命令を実行するよう構成されたプロセッサ）を含め、様々な形態で実装されうる。本明細書では、これらの実装または本発明が取りうる任意の他の形態を、技術と呼ぶ。一般に、開示された処理の工程の順序は、本発明の範囲内で変更されてもよい。特に言及しない限り、タスクを実行するよう構成されるものとして記載されたプロセッサまたはメモリなどの構成要素は、ある時間にタスクを実行するよう一時的に構成された一般的な構成要素として、または、タスクを実行するよう製造された特定の構成要素として実装されてよい。本明細書では、「プロセッサ」という用語は、１または複数のデバイス、回路、および／または、コンピュータプログラム命令などのデータを処理するよう構成された処理コアを指すものとする。
【０００８】
以下では、本発明の原理を示す図面を参照しつつ、本発明の１または複数の実施形態の詳細な説明を行う。本発明は、かかる実施形態に関連して説明されているが、どの実施形態にも限定されない。本発明の範囲は、特許請求の範囲によってのみ限定されるものであり、多くの代替物、変形物、および、等価物を含む。以下の説明では、本発明の完全な理解を提供するために、多くの具体的な詳細事項が記載されている。これらの詳細事項は、例示を目的としたものであり、本発明は、これらの具体的な詳細事項の一部または全てがなくとも特許請求の範囲に従って実施可能である。簡単のために、本発明に関連する技術分野で周知の技術事項については、本発明が必要以上にわかりにくくならないように、詳細には説明していない。
【０００９】
図１は、サンプリング解析システムの一実施形態を示すブロック図である。システム１００は、検索プラットフォームを備え、検索プラットフォームは、検索サービスを提供するために用いられる検索エンジン１０２と、検索プラットフォームのユーザによって送信された異なるクエリキーワードのページビュー（ＰＶ）値を記録するために用いられるデータベース１０４と、を備える。ユーザは、ネットワークを通して検索エンジンにアクセスし、ユーザが用いたクエリキーワードに対応するページビュー値が、データベースに記録される。システム１００は、さらに、記録されたクエリキーワードを解析するために用いられるサンプル解析器１０６を備える。サンプル解析器は、汎用サーバ、専用デバイス、または、１または複数のプロセッサを備えたその他のハードウェア／ソフトウェア／ファームウェアの組み合わせなど、１または複数のコンピュータデバイスと、プロセッサに接続され、プロセッサに命令を提供するよう構成されたメモリと、を用いて実装されてよい。いくつかの実施形態では、検索エンジン、データベース、および、サンプル解析器の機能の一部またはすべてが組み合わされて、１または複数のデバイス上に実装される。後に詳述するように、いくつかの実施形態においてサンプル解析器によって実行される解析処理は、検索プラットフォームによって記録された異なるクエリキーワードのＰＶ値に従って１または複数のクエリキーワードサブセットにクエリキーワードを分類すること、クエリキーワードサブセットのサンプルサイズを算出すること、サンプルサイズに従ってクエリキーワードサブセット内でクエリデータをサンプリングすること、を含む。
【００１０】
図２は、大規模な検索エンジンクエリデータのサンプリング解析のための処理の一実施形態を示すフローチャートである。処理２００は、システム（図１の１００など）に実装されてよい。工程２０１で、クエリキーワードは、異なるクエリキーワードのＰＶ値に従って、１または複数のクエリキーワードサブセットに分類される。本明細書で用いられるように、ＰＶ値とは、事前設定された期間内の検索プラットフォームでのクエリキーワードの出現回数である。いくつかの実施形態では、サンプリング解析を実行する前に、ある期間中に検索エンジンによって記録された全ユーザクエリキーワードのＰＶ値が記録され、異なるクエリキーワードのＰＶ値が順序付けられる。様々な実施形態において、ＰＶ値は、昇順に（小さい方から大きい方へ）順序付けられてもよいし、降順に（大きい方から小さい方へ）順序付けられてもよい。同じＰＶ値を持つクエリキーワードは、１つのクエリキーワードサブセットとして分類される。したがって、１つのクエリキーワードサブセットが、複数のクエリキーワードを含みうる。
【００１１】
工程２０２で、対応するクエリキーワードサブセット内でのクエリキーワードのそれぞれのサンプルレートが決定される。様々な実施形態において、クエリキーワードのサンプルレートは、サンプル確率、サンプルサイズ、または、それら両方を含む。いくつかの実施形態において、全クエリキーワードのコレクションからクエリキーワードをサンプリングする前に、システムは、まず、アプリケーションの要求に従って、サンプリング解析でのクエリキーワードサイズを決定する。具体的には、システムは、まず、各クエリキーワードサブセット内のＰＶ値の合計をＳＰＶ（セットページビュー）値として算出する。ＳＰＶ値は、特定のクエリキーワードサブセットについての全体のＰＶサイズを指す。次いで、システムは、各クエリキーワードサブセットのＳＰＶ値を合計し、クエリキーワードコレクションの全体のページビューサイズ（ＴＰＶ値と呼ぶ）を取得する。ＴＰＶ値は、事前設定された期間中に検索プラットフォームで出現する全ユーザクエリキーワードの総数に対応する。クエリキーワードのサンプル確率は、取得されたＳＰＶ値とＴＰＶ値との比に従って算出される。次いで、特定のクエリキーワードサブセットのサンプルサイズが、決定されたクエリキーワードサンプルサイズと、各クエリキーワードサブセットのサンプル確率とに従って算出される。
【００１２】
工程２０３において、クエリキーワードサブセット内のクエリデータが、クエリキーワードのサンプルレートに従ってサンプリングされる。いくつかの実施形態において、クエリキーワードサブセット内のクエリデータは、無作為に生成された数字に基づく無作為抽出によって無作為サンプリングされる。他の無作為選択技術を用いてもよい。クエリキーワードサブセットから無作為サンプリングされたクエリデータは、或る期間内にユーザによって検索された異なるクエリキーワードの分布を解析するために利用され、その結果、ユーザの求める情報が理解され、システムによって利用される。
【００１３】
上述の技術を用いて、ユーザによって要求されたクエリデータが、予備的に統計処理された大量のクエリキーワードコレクションからサンプリングされる。この技術は、後の計算のために必要な記憶域を削減すると共に、低頻度のクエリを過小評価するリスクを解消することができる。これにより、中規模サイズまたは小規模サイズのサンプルが実際のデータの実際の分布に近くなり、正確なユーザ需要情報および市場動向が検索エンジンサービスプロバイダに提供されて、質が向上する。
【００１４】
多くの検索エンジンサービスプロバイダにとって、「現在ユーザが検索しているものが何か」という機能を提供する目的は、ユーザが検索エンジンに送信したクエリ要求をリアルタイムで出力することである。大規模な検索エンジンにおいて、多くのユーザがこの機能の結果を用いてクエリを実行し、各ユーザは通例、検索プラットフォーム上で複数のクエリキーワードを検索する。したがって、非常に短い期間でも、検索エンジンによって記録されるユーザクエリは、大量のデータになりうる。いくつかの検索プラットフォームでは、一日あたり１００万を越える検索要求が受信される。記録されたクエリキーワードの中で、大部分のユーザクエリキーワードが、繰り返しのクエリ、すなわち、異なるユーザによって送信された同様または同一のクエリキーワードである。現在の最新ニュースを例にとると、数百のユーザが、短期間にそのニュースをクエリするために同一のクエリ要求を送信しうる。検索エンジンサービスプロバイダは、よりよいサービスを提供するために、ある一定の期間で大量のユーザクエリ要求を処理する必要がある。１つの基本的な処理工程は、同一のユーザクエリキーワードをマージする工程であり、それにより、データストレージが占有する大量のメモリまたはディスクスペースが低減される。ユーザの需要を理解し、より良好でより便利なサービスを提供するために、ユーザクエリキーワードのサンプリング解析および調査が、一定期間中に行われる。もちろん、決定されるクエリキーワードのサンプルサイズは、全ユーザクエリキーワードの合計サイズに対して小さい割合である。処理済みのページビューがサンプリング解析に直接用いられる場合、サンプル確率は、高いクエリ頻度で出現するクエリキーワードについては非常に高くなり、クエリ頻度の低いクエリキーワードについては非常に低くなる。その結果、サンプルは、いくぶん非対称となり、サンプリングの主な目的が達成されない。さらに、正味の表示スペースは限られているため、全ユーザのクエリキーワードをリアルタイムで表示することはできない。その代わり、小規模な数理モデルを設定するために、クエリキーワードをサンプリングすることにより、選択的なクエリキーワードが表示される。しかしながら、ユーザクエリ要求をより正確に反映するには、サンプルユーザクエリキーワードの分布が、大量のユーザクエリキーワードの分布によく似ている必要がある。
【００１５】
図３は、各クエリキーワードサブセットのサンプルレートを算出するための処理の一実施形態を示すフローチャートである。いくつかの実施形態において、処理３００は、処理２００の工程２０２を実行するために用いられる。図の例において、処理３００は、検索エンジンクエリキーワードコレクション内のエントリ（「クエリキーワードＰＶ」のフォーマットで記憶される）がＰＶ値に従って順序付けられる工程３０１で開始する。様々な実施形態において、ＰＶ値は、大から小へ降順に順序付けられてもよいし、小から大へ昇順に順序付けられてもよい。例えば、一定期間内に検索エンジンによって記録された全ユーザクエリキーワードの合計サイズ（ＴＰＶ値）が１０００００であり、クエリキーワード「Ａｌｉｂａｂａ」に関する記録が２０００あって「Ａｌｉｂａｂａ  ２０００」のフォーマットで記憶され、クエリキーワード「ｅｃｏｍｍｅｒｃｅ」に関する記録が１８００あって「ｅｃｏｍｍｅｒｃｅ  １８００」のフォーマットで記憶され、クエリキーワード「コンピュータ」に関する記録が５００あって「ｃｏｍｐｕｔｅｒ  ５００」のフォーマットで記憶され、クエリキーワード「ｃｌｏｔｈｅｓ」に関する記録が５００あって「ｃｌｏｔｈｅｓ  ５００」のフォーマットで記憶され、・・・、クエリキーワード「ｇｌａｓｓ」に関する６０の記録、クエリキーワード「ｐｅｎｃｉｌ」に関する６０の記録、クエリキーワード「ｎｏｔｅｓ」に関する６０の記録などが、上述の格納フォーマット従って記憶されていると仮定する。その結果、昇順のクエリコレクションは以下のようになる：  「ｇｌａｓｓ  ６０」、「ｐｅｎｃｉｌ  ６０」、「ｎｏｔｅｓ  ６０」、・・・、「ｃｏｍｐｕｔｅｒ  ５００」、「ｃｌｏｔｈｅｓ  ５００」、「ｅｃｏｍｍｅｒｃｅ  １８００」、および、「Ａｌｉｂａｂａ２０００」、・・・。
【００１６】
工程３０２で、同じＰＶ値を有するクエリキーワードがグループ化される。同じＰＶ値を有するクエリキーワードは、クエリキーワードコレクションの１つのサブセット（ＱｕｅｒｙＳｅｔ）と見なされ、そのサブセットに属するクエリは、各クエリキーワードに対して同じＰＶ値を有する。異なるＱｕｅｒｙＳｅｔが、異なるＰＶ値に従って取得されうる。ＰＶ値が１からＫまでとすると、クエリキーワードサブセットＱｕｅｒｙＳｅｔ１、ＱｕｅｒｙＳｅｔ２、・・・、ＱｕｅｒｙＳｅｔＫが取得される。一部の状況では、異なるユーザクエリについて、各クエリキーワードのＰＶ値が、或る期間中に連続的ではない場合がある。同じＰＶ値を有するクエリキーワードは、ＱｕｅｒｙＳｅｔ６０、ＱｕｅｒｙＳｅｔ５００、ＱｕｅｒｙＳｅｔ１８００、ＱｕｅｒｙＳｅｔ２０００など、複数のクエリキーワードサブセットを得るためにマージされる。
【００１７】
工程３０３で、クエリキーワードサブセットのサンプル確率が算出される。ＰＶ値Ｉを有するクエリを含むクエリキーワードサブセットＱｕｅｒｙＳｅｔＩについては、クエリキーワードサブセットの合計ＰＶサイズＳＰＶは、ＳＰＶi＝Ｉ＊｜ＱｕｅｒｙＳｅｔＩ｜で得られる。ここで、Ｉは、ＰＶ値Ｉを表し、｜ＱｕｅｒｙＳｅｔＩ｜は、クエリキーワードサブセットのサイズ、すなわち、ＰＶ値Ｉを有するクエリキーワードがサブセットに属する数を表している。クエリキーワードサブセットＱｕｅｒｙＳｅｔ６０を例にとり、「クエリキーワード６０」のページビューが３０あると仮定すると、｜ＱｕｅｒｙＳｅｔ６０｜は３０であり、これは、クエリキーワードサブセット内に３０の異なるクエリがあり、ＳＰＶ値が６０＊３０＝１８００であることを意味する。ロングテール分布を有するデータについては、ＰＶ値が小さくなるほど、より多くのクエリキーワードが、クエリキーワードサブセットに含まれる。したがって、統計値としてのＳＰＶ値は、個々のクエリキーワードのＰＶ値が小さいことの影響を受けない。例えば、クエリデータ「ｇｌａｓｓ  ６０」については、ＰＶ値は、クエリの合計であるＴＰＶ値１０００００に比べて小さく、また、「Ａｌｉｂａｂａ  ２０００」のＰＶ値と比べても小さい。しかし、「ｇｌａｓｓ  ６０」が属するクエリキーワードサブセットＱｕｅｒｙＳｅｔ６０については、ＳＰＶ値は１８００であり、「Ａｌｉｂａｂａ  ２０００」が属するクエリキーワードサブセットのＳＰＶ値に近い（「Ａｌｉｂａｂａ  ２０００」におけるページビュー値が１つだけであると仮定する）。
【００１８】
各クエリキーワードサブセットのサンプル確率を算出するために、全クエリキーワードのＳＰＶ値が合計され、全クエリキーワードの合計サイズが取得される。全クエリキーワードの合計サイズを、ＴＰＶ値と呼ぶ。ＴＰＶ値が与えられると、サンプリング中の全クエリキーワードサブセットのサンプル確率を算出することができる。例えば、ＰＶ値ｉを有するクエリキーワードサブセットについては、サンプル確率は、Ｐi＝ＳＰＶi／ＴＰＶである。いくつかの実施形態では、全クエリキーワードサブセットのサンプル確率が取得されるまで計算が繰り返される。
【００１９】
出現頻度の低い多くのクエリキーワードについて、低頻度クエリのサンプル確率は非常に小さいが、同じＰＶ値を有するクエリキーワードサブセットについては、サブセット内の低頻度クエリキーワードの数は大きい可能性があるため、低頻度クエリキーワードを含むクエリキーワードサブセットのＳＰＶサイズは大きくなりうる。したがって、これらの低頻度クエリキーワードは全体としてサンプリングされるため、サンプル確率が効果的に大きくなり、最終的にサンプリングされるデータは実際のデータ分布とより一致するようになる。上述の例を用いると、３０のクエリキーワードを含むクエリキーワードサブセットＱｕｅｒｙＳｅｔ６０のサンプル確率は、Ｐ60＝１８００／１０００００＝０．０１８であり、クエリキーワードを１つだけ含むクエリキーワードサブセットＱｕｅｒｙＳｅｔ２０００のサンプル確率は、Ｐ2000＝２０００／１０００００＝０．０２０である。このように、クエリキーワードサブセットＱｕｅｒｙＳｅｔ６０およびＱｕｅｒｙＳｅｔ２０００のサンプル確率は非常に近いことが取得されたデータの結果からわかる。
【００２０】
サンプルサイズ「Ｋ」を仮定すると、各クエリキーワードサブセットからのサンプルクエリサイズは、各コレクションのサンプル確率に従って算出可能である。例えば、Ｋが５０００に決定され、ＰＶ＝６０を有するサブセットのサンプル確率が０．０１８であると仮定する。したがって、ＱｕｅｒｙＳｅｔ６０からサンプリングされるクエリサイズは、５０００＊０．０１８＝９０である。ＰＶ＝２を有するサブセットのサンプル確率を０．０１０と仮定すると、ＱｕｅｒｙＳｅｔ２からサンプリングされるクエリサイズは、５０００＊０．０１０＝５０である。
【００２１】
図４は、クエリキーワードをサンプリングするための処理の一実施形態を示すフローチャートである。処理４００は、処理２００の工程２０３を実行するために用いられてよい。この処理では、クエリキーワードが、ある選択されたクエリキーワードサブセットから無作為にサンプリングされる。この時点で、クエリキーワードサブセットからサンプリングされるクエリサイズＮ（Ｎは自然数）は、すでに決定されている。したがって、クエリをサンプリングするために、Ｎ個のサンプルが、対応するクエリキーワードサブセット内で選ばれる。サンプル数がＮに達するまで、毎回、ページビューがクエリキーワードサブセットから無作為に選択される。例えば、工程３０３で例に挙げたクエリキーワードサブセットＱｕｅｒｙＳｅｔ６０について、クエリキーワードサブセットからサンプリングされるクエリサイズは、クエリキーワードサブセットのサンプル確率に従って、９０となる。したがって、最終的なクエリキーワードサンプリングにおいて、クエリキーワードサブセットは、９０のページビューを取得するために９０回サンプリングされる。
【００２２】
あるクエリキーワードサブセットから１つの任意の検索エンジンページビューをサンプリングする時に、同じＰＶ値を有するクエリキーワードは、１つのクラスとして分類される。したがって、クエリキーワードサブセット内のどのクエリキーワードに対しても、サンプリングされる確率は同じである。例えば、クエリキーワードサブセットＱｅｒｙＳｅｔ６０内でサンプリングする場合、サンプリングされる９０のページビューは、「ｇｌａｓｓ」の２ページビュー、「ｐｅｎｃｉｌ」の３ページビューなどを含みうる。このように、出現頻度が低いクエリがサンプリングされる場合でも、取得されるサンプリング結果は、実際のデータ分布に近いため、サンプリング解析の主な目的が達成される。
【００２３】
いくつかの実施形態では、無作為サンプリング処理がクエリキーワードのサンプリングに用いられる。図５は、無作為サンプリング処理の一実施形態を示すフローチャートである。処理５００は、処理２００の工程２０３を実行するために用いられてよい。特定のＱｕｅｒｙＳｅｔｉ（クエリキーワードサブセットｉ）について、工程５０４で、ＱｕｅｒｙＳｅｔｉのサイズ（すなわち、サブセット内のクエリキーワード数）が決定される。サブセット内にＭ個のクエリキーワードがあると仮定すると、工程５０６で、ＱｕｅｒｙＳｅｔｉ内のページビューが、１からＭの数字に関連付けられる。工程５０８で、１からＭの間の無作為な整数値を有する乱数Ｒが生成される。工程５１０で、ＱｕｅｒｙＳｅｔｉ内のＲ番目のクエリキーワードに関連付けられたページビューが決定される。工程５１２で、ページビューの値は、この情報をシステム管理者に表示する別の処理またはモジュールに対して必要に応じて出力される。ＱｕｅｒｙＳｅｔｉをＮ回サンプリングし、すべてのクエリキーワードサブセットをサンプリングするために、この処理が繰り返されてよい。
【００２４】
上述の実施形態では、２段階のサンプリング解析が行われ、要求されたクエリは、多数のエントリを含む予備的に統計処理された検索エンジンクエリキーワードコレクションからサンプリングされ、サンプリング結果は、実際のデータの分布に近い分布を有する。このサンプリング技術を用いると、予備的な統計データは維持されて、後の計算に必要な記憶域を削減するために利用され、従来技術に関連した低頻度クエリの過小評価という問題が軽減される。サンプリングされたデータによって得られた情報に従って、検索エンジンサービスプロバイダは、便利で高速なオンライン商取引プラットフォームを提供してサービスの質を向上させるために、ユーザ需要および市場動向をより正確に理解し、ビジネスの機会を見出し、検索エンジンサービスのコンテンツを調整することができる。
【００２５】
図６は、サンプリング解析器の一実施形態を示すブロック図である。この例で示すデバイス６００は、異なるクエリキーワードのＰＶ値に従って少なくとも１つのクエリキーワードサブセットにクエリキーワードを分類するために用いられる分類モジュール２１と、分類モジュール２１によって分類されたクエリキーワードサブセットのサンプリングサイズを算出するために用いられる計算モジュール２２と、計算モジュール２２によって算出されたサンプリングサイズに従って、分類モジュール２１によって分類されたクエリキーワードサブセット内でクエリデータをサンプリングするために用いられるサンプリングモジュール２３と、を備える。いくつかの実施形態において、サンプリング解析デバイスは、さらに、事前設定された期間における少なくとも１つのクエリキーワードの出現回数である様々なクエリキーワードのＰＶ値を格納するために用いられる格納モジュール２４を備える。
【００２６】
この例では、分類モジュール２１は、さらに、格納モジュール２４によって格納された異なるクエリキーワードのＰＶ値を順序付けるために用いられる順序付けサブモジュール２１１と、順序付けサブモジュール２１１によって順序付けられた順序に従って、同じＰＶ値を有するクエリキーワードを１つのクエリキーワードサブセットとして分類するために用いられる分類サブモジュール２１２と、を備える。
【００２７】
この例では、計算モジュール２２は、さらに、クエリキーワードサブセットのサンプリング確率を算出するために用いられる確率計算サブモジュール２２１と、決定されたサンプリングクエリサイズと計算サブモジュール２２１によって算出されたサンプリング確率とに従って、クエリキーワードサブセットのサンプリングサイズを算出するために用いられるサンプリング計算サブモジュール２２２と、を備える。
【００２８】
要求されたクエリデータは、大量の予備的に統計処理されたクエリキーワードコレクションからサンプリングすることが可能であり、それにより、後の計算に必要な記憶域を削減すると共に、低頻度クエリを過小評価するリスクを解決することができ、ページビューをサンプリングする目標を達成し、中規模または小規模サンプルを実際のデータ分布に近づけ、正確なユーザ需要情報および市場動向を検索エンジンサービスプロバイダに提供することで、質の向上を図ることができる。
【００２９】
上述のモジュールは、１または複数の汎用プロセッサ上で実行されるソフトウェアコンポーネントとして、特定の機能を実行するよう設計されたプログラム可能論理デバイスおよび／または特定用途向け集積回路などのハードウェアとして、もしくは、それらの組み合わせとして実装することができる。いくつかの実施形態において、モジュールは、コンピュータデバイス（パーソナルコンピュータ、サーバ、ネットワーク装置など）に本発明の実施形態に記載された方法を実行させるための複数の命令など、不揮発性記憶媒体（光学ディスク、フラッシュ記憶装置、携帯用ハードディスクなど）に格納することができるソフトウェア製品の形態で具現化されてよい。モジュールは、単一のデバイス上に実装されてもよいし、複数のデバイスにわたって分散されてもよい。モジュールの機能は、互いに統合されてもよいし、複数のサブモジュールにさらに分割されてもよい。
【００３０】
上述の実施形態の説明を通して、この分野における技術者は、本発明がハードウェアまたはソフトウェアならびに必要な現在のハードウェアプラットフォームによって実施可能であることを明確に理解できる。この理解に基づいて、本発明の技術的プログラムは、コンピュータデバイス（パーソナルコンピュータ、サーバ、ネットワーク装置など）に本発明の実施形態に記載された方法を実行させるための複数の命令など、不揮発性記憶媒体（ＣＤ−ＲＯＭ、Ｕディスク、携帯用ハードディスクなど）に格納することができるソフトウェア製品の形態で具現化されてよい。
【００３１】
以上の記載は、本発明の好ましい実施方法に過ぎない。この分野の一般的な技術者にとっては、何らかの改良および修正を行うことが可能であり、それらも本発明の保護範囲として見なされるべきであることを理解されたい。
【００３２】
上述の実施形態は、理解しやすいようにいくぶん詳しく説明されているが、本発明は、提供された詳細事項に限定されるものではない。本発明を実施する多くの代替方法が存在する。開示された実施形態は、例示であり、限定を意図するものではない。
適用例１：サンプリング解析のための方法であって、複数のユーザによって提示された複数のクエリキーワードに関連するページビュー（ＰＶ）値に従って、前記複数のクエリキーワードを複数のクエリキーワードサブセットに分類し、前記複数のクエリキーワードサブセット内の各クエリキーワードサブセット内のそれぞれの複数のクエリキーワードのそれぞれの複数のサンプルレートを決定し、前記それぞれの複数のサンプルレートに従って、前記複数のクエリキーワードサブセットの内の各クエリキーワードサブセット内でクエリデータをサンプリングすること、を備える、方法。
適用例２：適用例１に記載の方法であって、クエリデータのサンプリングは、前記それぞれの複数のクエリキーワードの実際の分布と実質的に類似するサンプルクエリキーワードのサンプル分布を生成する、方法。
適用例３：適用例１に記載の方法であって、前記ＰＶ値は、事前設定された期間内の検索プラットフォームにおける前記複数のクエリキーワードの内のそれぞれのキーワードの出現回数に対応する、方法。
適用例４：適用例１に記載の方法であって、前記複数のクエリキーワードの分類は、前記複数のクエリキーワードに関連する前記ＰＶ値を順序付け、同一のＰＶ値を有するクエリキーワードを、前記複数のクエリキーワードサブセットの内のそれぞれのサブセット内にグループ化すること、を備える、方法。
適用例５：適用例１に記載の方法であって、前記それぞれの複数のサンプルレートは、前記複数のクエリキーワードサブセット内の各クエリキーワードサブセットのサンプリング中に用いられるそれぞれの複数のサンプルサイズを含む、方法。
適用例６：適用例５に記載の方法であって、前記それぞれの複数のサンプルサイズは、前記複数のクエリキーワードサブセット内の各クエリキーワードサブセットに関連するそれぞれの複数のサンプル確率を決定し、前記それぞれの複数のサンプルサイズおよび前記それぞれの複数のサンプル確率に従って、前記それぞれの複数のサンプルサイズを決定すること、によって決定される、方法。
適用例７：適用例６に記載の方法であって、前記それぞれの複数のサンプル確率を決定は、前記クエリキーワードサブセットのＰＶ値の合計（ＳＰＶ値）を決定し、前記ＳＰＶ値に従って、前記複数のクエリキーワードサブセット内のＰＶ値の合計を決定し、前記ＳＰＶ値および前記ＴＰＶ値に従って、前記クエリキーワードサブセットのサンプル確率を決定すること、を備える、方法。
適用例８：適用例１に記載の方法であって、前記サンプルサイズに従って前記クエリキーワードサブセット内でクエリデータをサンプリングするために、無作為サンプリングが用いられる、方法。
適用例９：適用例８に記載の方法であって、前記無作為サンプリングは、乱数を生成し、前記乱数に関連付けられた前記クエリキーワードサブセット内のクエリキーワードを選択すること、を含む、方法。
適用例１０：サンプリング解析システムであって、プロセッサであって、複数のユーザによって提示された複数のクエリキーワードに関連するページビュー（ＰＶ）値に従って、前記複数のクエリキーワードを複数のクエリキーワードサブセットに分類し、前記複数のクエリキーワードサブセット内の各クエリキーワードサブセット内のそれぞれの複数のクエリキーワードのそれぞれの複数のサンプルレートを決定し、前記それぞれの複数のサンプルレートに従って、前記複数のクエリキーワードサブセットの対応する各クエリキーワードサブセット内でクエリデータをサンプリングするよう構成されたプロセッサと、前記プロセッサに接続され、前記プロセッサに命令を提供するよう構成されたメモリと、を備える、システム。
適用例１１：適用例１０に記載のシステムであって、前記プロセッサは、前記それぞれの複数のクエリキーワードの実際の分布と実質的に類似するサンプルクエリキーワードのサンプル分布を生成するように前記クエリデータをサンプリングするよう構成される、システム。
適用例１２：適用例１０に記載のシステムであって、前記ＰＶ値は、事前設定された期間内の検索プラットフォームにおける前記複数のクエリキーワードの内のそれぞれのキーワードの出現回数に対応する、システム。
適用例１３：適用例１０に記載のシステムであって、前記複数のクエリキーワードの分類は、前記複数のクエリキーワードに関連する前記ＰＶ値を順序付けることと、同一のＰＶ値を有するクエリキーワードを、前記複数のクエリキーワードサブセットの内のそれぞれのサブセット内にグループ化することと、を含む、システム。
適用例１４：適用例１０に記載のシステムであって、前記それぞれの複数のサンプルレートは、前記複数のクエリキーワードサブセットの内のそれぞれのサブセットのサンプリング中に用いられるそれぞれの複数のサンプルサイズを含む、システム。
適用例１５：適用例１４に記載のシステムであって、前記それぞれの複数のサンプルサイズは、前記複数のクエリキーワードサブセット内の各クエリキーワードサブセットに関連するそれぞれの複数のサンプル確率を決定し、前記それぞれの複数のサンプルサイズおよび前記それぞれの複数のサンプル確率に従って、前記それぞれの複数のサンプルサイズを決定すること、によって決定される、システム。
適用例１６：適用例１５に記載のシステムであって、前記それぞれの複数のサンプル確率の決定は、前記クエリキーワードサブセットのＰＶ値の合計（ＳＰＶ値）を決定し、前記ＳＰＶ値に従って、前記複数のクエリキーワードサブセット内のＰＶ値の合計を決定し、前記ＳＰＶ値および前記ＴＰＶ値に従って、前記クエリキーワードサブセットのサンプル確率を決定すること、を備える、システム。
適用例１７：適用例１０に記載のシステムであって、前記サンプルサイズに従って前記クエリキーワードサブセット内でクエリデータをサンプリングするために、無作為サンプリングが用いられる、システム。
適用例１８：適用例１７に記載のシステムであって、前記無作為サンプリングは、乱数を生成し、前記乱数に関連付けられた前記クエリキーワードサブセット内のクエリキーワードを選択すること、を含む、システム。
適用例１９：サンプリング解析のためのコンピュータプログラム製品であって、前記コンピュータプログラム製品は、コンピュータ読み取り可能な記憶媒体内に具現化され、複数のユーザによって提示された複数のクエリキーワードに関連するページビュー（ＰＶ）値に従って、前記複数のクエリキーワードを複数のクエリキーワードサブセットに分類するためのコンピュータ命令と、前記複数のクエリキーワードサブセット内の各クエリキーワードサブセットに含まれるそれぞれの複数のクエリキーワードのそれぞれの複数のサンプルレートを決定するためのコンピュータ命令と、前記それぞれの複数のサンプルレートに従って、前記複数のクエリキーワードサブセット内の各クエリキーワードサブセット内でクエリデータをサンプリングするためのコンピュータ命令と、を備える、コンピュータプログラム製品。
【図１】
0005552496.tif 000002
【図２】
0005552496.tif 000003
【図３】
0005552496.tif 000004
【図４】
0005552496.tif 000005
【図５】
0005552496.tif 000006
【図６】
0005552496.tif 000007