(57)【要約】  リソースおよびスペース効率よく大規模データセットを分析することを容易にする、コンピュータ記憶媒体上に符号化されたコンピュータプログラムを含む、方法、システム、および装置。方法は、データセット内のオブジェクトに関する活動データを取得するステップを含む。データセット内の各データ項目について、オブジェクトの識別子を使用して、バイナリ表現を有するハッシュ化パラメータが生成される。ハッシュ化パラメータに基づいて、レジスタのセットの中からレジスタが識別される。オブジェクトのハッシュ化パラメータがデータセット内のオブジェクトの出現回数を指定する集計量に寄与することの判定がなされる。この判定に基づいて、レジスタ内に記憶された集計量が更新される。レジスタのセット内に記憶された集計量に基づいて、オブジェクトの活動データに基づいてデータセット内のオブジェクトの集計分布を提供する報告出力が生成される。
2022500714.tif 000002
【特許請求の範囲】
【請求項１】
データセット内の複数のオブジェクトに関する活動データを取得するステップであって、前記データセット内の各オブジェクトが、デジタル環境内で活動を実行し、前記活動データが、前記活動を表す、ステップと、
前記データセット内の各データ項目について、
前記データ項目において指定されたオブジェクトの識別子を使用して、前記オブジェクトのハッシュ化パラメータを生成するステップであって、前記ハッシュ化パラメータが、バイナリ表現である、ステップと、
前記ハッシュ化パラメータの前記バイナリ表現に基づいて、レジスタのセットの中からレジスタを識別するステップであって、前記レジスタのセット内の各レジスタが、前記データセット内のオブジェクトに関するデータを記憶するために使用される、ステップと、
前記ハッシュ化パラメータの前記バイナリ表現に基づいて、前記オブジェクトの前記ハッシュ化パラメータが前記データセット内の前記オブジェクトの出現回数を指定する集計量に寄与していることを判定するステップと、
前記オブジェクトの前記ハッシュ化パラメータが前記集計量に寄与しているとの判定に応答して、前記レジスタ内に記憶された前記集計量を更新するステップと、
前記レジスタのセット内に記憶された前記集計量に基づいて、データ項目のセットを示す報告出力を生成するステップであって、各データ項目が、特定の集計量において前記デジタル環境内で活動を実行した前記データセット内のオブジェクトの推定数を識別する、ステップとを含む、
コンピュータで実行される方法。
【請求項２】
各オブジェクトが、ユーザを表し、
集計量が頻度値を表す、
請求項1に記載のコンピュータで実行される方法。
【請求項３】
前記ハッシュ化パラメータの前記バイナリ表現に基づいてレジスタのセットの中からレジスタを識別するステップが、
前記ハッシュ化パラメータの前記バイナリ表現の第1の部分を識別するステップと、
前記ハッシュ化パラメータの前記バイナリ表現の前記第1の部分を使用して前記レジスタを識別するステップとを含む、
請求項1に記載のコンピュータで実行される方法。
【請求項４】
前記レジスタのセット内の各レジスタが、受信されたハッシュ化パラメータに関するデータを記憶するデータ構造を備え、
前記データ構造が、
前記受信されたハッシュ化パラメータの第2の部分における先行ゼロの数を指定するデータを記憶するための第1のフィールドと、
前記受信されたハッシュ化パラメータの前記第2の部分内の後続ビットを指定するデータを記憶するための第2のフィールドと、
(i)前記第1のフィールド内の既存のデータ値が前記先行ゼロの数と一致し、(ii)前記第2のフィールド内の既存のデータ値が前記後続ビットと一致する場合の出現回数を示す集計量を指定するデータを記憶するための第3のフィールドとを含む、
請求項1に記載のコンピュータで実行される方法。
【請求項５】
前記ハッシュ化パラメータの前記バイナリ表現に基づいて、前記オブジェクトの前記ハッシュ化パラメータが集計量に寄与していることを判定するステップが、
前記ハッシュ化パラメータの前記バイナリ表現の前記第2の部分から先行ゼロの数を決定するステップと、
前記ハッシュ化パラメータの前記バイナリ表現の前記第2の部分から後続ビットを決定するステップと、
前記先行ゼロの数と前記後続ビットとに基づいて、前記ハッシュ化パラメータが前記レジスタの前記データ構造の前記第3のフィールド内に記憶された既存のデータ値に影響を与えることを判定するステップとを含む、
請求項4に記載のコンピュータで実行される方法。
【請求項６】
前記先行ゼロの数と後続ビットの最大数とに基づいて、前記ハッシュ化パラメータが前記レジスタの前記データ構造の前記第3のフィールド内に記憶された既存のデータ値に影響を与えることを判定するステップが、
前記レジスタの前記データ構造の前記第1のフィールド内に記憶された前記既存のデータ値が前記先行ゼロの数と同じであることを判定するステップと、
前記レジスタの前記データ構造の前記第2のフィールド内に記憶された前記既存のデータ値が前記後続ビットの最大数と同じであることを判定するステップとを含む、
請求項5に記載のコンピュータで実行される方法。
【請求項７】
前記レジスタ内に記憶された前記集計量を更新するステップが、前記レジスタの前記データ構造の前記第3のフィールド内に記憶された前記既存のデータ値を1だけ増分するステップを含む、
請求項5に記載のコンピュータで実行される方法。
【請求項８】
前記レジスタのセット内に記憶された集計量に基づいて、データ項目のセットを示す報告出力を生成するステップであって、各データ項目が、特定の集計量において前記デジタル環境内で活動を実行した前記データセット内のオブジェクトの推定数を識別する、ステップが、
前記レジスタのセット内に記憶された集計量に基づいて、一意の集計量のセットを識別するステップと、
前記集計量のセット内の各々の特定の集計量について、前記特定の集計量において活動を実行した前記データセットのオブジェクトの推定数を決定するステップとを含み、前記推定数を決定するステップが、
前記特定の集計量に一致する集計量を記憶するレジスタの数を決定するステップと、
ハッシュ衝突補正係数に基づいて、前記特定の集計量と一致する前記集計量を記憶する前記レジスタの数を調整するステップと、
前記レジスタのセットの各レジスタ内に記憶されたオブジェクトの平均数を決定するステップと、
前記オブジェクトの平均数によって前記レジスタの調整された数をスケーリングするステップとを含む、
請求項4に記載のコンピュータで実行される方法。
【請求項９】
命令を記憶する1つまたは複数のメモリデバイスと、
前記1つまたは複数のメモリデバイスと対話するように構成され、かつ前記命令の実行時に動作を実行する1つまたは複数のデータ処理装置とを備える、
システムであって、前記動作が、
データセット内の複数のオブジェクトに関する活動データを取得するステップであって、前記データセット内の各オブジェクトが、デジタル環境内で活動を実行し、前記活動データが前記活動を表す、ステップと、
前記データセット内の各データ項目について、
前記データ項目において指定されたオブジェクトの識別子を使用して、前記オブジェクトのハッシュ化パラメータを生成するステップであって、前記ハッシュ化パラメータが、バイナリ表現である、ステップと、
前記ハッシュ化パラメータの前記バイナリ表現に基づいて、レジスタのセットの中からレジスタを識別するステップであって、前記レジスタのセット内の各レジスタが、前記データセット内のオブジェクトに関するデータを記憶するために使用される、ステップと、
前記ハッシュ化パラメータの前記バイナリ表現に基づいて、前記オブジェクトの前記ハッシュ化パラメータが前記データセット内の前記オブジェクトの出現回数を指定する集計量に寄与していることを判定するステップと、
前記オブジェクトの前記ハッシュ化パラメータが前記集計量に寄与しているとの判定に応答して、前記レジスタ内に記憶された前記集計量を更新するステップと、
前記レジスタのセット内に記憶された前記集計量に基づいて、データ項目のセットを示す報告出力を生成するステップであって、各データ項目が、特定の集計量において前記デジタル環境内で活動を実行した前記データセット内のオブジェクトの推定数を識別する、ステップとを含む、
システム。
【請求項１０】
各オブジェクトが、ユーザを表し、
集計量が、頻度値を表す、
請求項9に記載のシステム。
【請求項１１】
前記ハッシュ化パラメータの前記バイナリ表現に基づいてレジスタのセットの中からレジスタを識別するステップが、
前記ハッシュ化パラメータの前記バイナリ表現の第1の部分を識別するステップと、
前記ハッシュ化パラメータの前記バイナリ表現の前記第1の部分を使用して前記レジスタを識別するステップとを含む、
請求項9に記載のシステム。
【請求項１２】
前記レジスタのセット内の各レジスタが、受信されたハッシュ化パラメータに関するデータを記憶するデータ構造を備え、
前記データ構造が、
前記受信されたハッシュ化パラメータの第2の部分における先行ゼロの数を指定するデータを記憶するための第1のフィールドと、
前記受信されたハッシュ化パラメータの前記第2の部分内の後続ビットを指定するデータを記憶するための第2のフィールドと、
(i)前記第1のフィールド内の既存のデータ値が前記先行ゼロの数と一致し、(ii)前記第2のフィールド内の既存のデータ値が前記後続ビットと一致する場合の出現回数を示す集計量を指定するデータを記憶するための第3のフィールドとを含む、
請求項9に記載のシステム。
【請求項１３】
前記ハッシュ化パラメータの前記バイナリ表現に基づいて、前記オブジェクトの前記ハッシュ化パラメータが集計量に寄与していることを判定するステップが、
前記ハッシュ化パラメータの前記バイナリ表現の前記第2の部分から先行ゼロの数を決定するステップと、
前記ハッシュ化パラメータの前記バイナリ表現の前記第2の部分から後続ビットを決定するステップと、
前記先行ゼロの数と前記後続ビットとに基づいて、前記ハッシュ化パラメータが前記レジスタの前記データ構造の前記第3のフィールド内に記憶された既存のデータ値に影響を与えることを判定するステップとを含む、
請求項12に記載のシステム。
【請求項１４】
前記先行ゼロの数と後続ビットの最大数とに基づいて、前記ハッシュ化パラメータが前記レジスタの前記データ構造の前記第3のフィールド内に記憶された既存のデータ値に影響を与えることを判定するステップが、
前記レジスタの前記データ構造の前記第1のフィールド内に記憶された前記既存のデータ値が前記先行ゼロの数と同じであることを判定するステップと、
前記レジスタの前記データ構造の前記第2のフィールド内に記憶された前記既存のデータ値が前記後続ビットの最大数と同じであることを判定するステップとを含む、
請求項13に記載のシステム。
【請求項１５】
前記レジスタ内に記憶された前記集計量を更新するステップが、
前記レジスタの前記データ構造の前記第3のフィールド内に記憶された前記既存のデータ値を1だけ増分するステップを含む、
請求項13に記載のシステム。
【請求項１６】
前記レジスタのセット内に記憶された集計量に基づいて、データ項目のセットを示す報告出力を生成するステップであって、各データ項目が、特定の集計量において前記デジタル環境内で活動を実行した前記データセット内のオブジェクトの推定数を識別する、ステップが、
前記レジスタのセット内に記憶された集計量に基づいて、一意の集計量のセットを識別するステップと、
前記集計量のセット内の各々の特定の集計量について、前記特定の集計量において活動を実行した前記データセットのオブジェクトの推定数を決定するステップとを含み、前記推定数を決定するステップが、
前記特定の集計量に一致する集計量を記憶するレジスタの数を決定するステップと、
ハッシュ衝突補正係数に基づいて、前記特定の集計量と一致する前記集計量を記憶する前記レジスタの数を調整するステップと、
前記レジスタのセットの各レジスタ内に記憶されたオブジェクトの平均数を決定するステップと、
前記オブジェクトの平均数によって前記レジスタの調整された数をスケーリングするステップとを含む、
請求項12に記載のシステム。
【請求項１７】
1つまたは複数のデータ処理装置に以下の動作を実行させるための命令を記憶するコンピュータ可読記憶媒体であって、前記動作が、
データセット内の複数のオブジェクトに関する活動データを取得するステップであって、前記データセット内の各オブジェクトが、デジタル環境内で活動を実行し、前記活動データが、前記活動を表す、ステップと、
前記データセット内の各データ項目について、
前記データ項目において指定されたオブジェクトの識別子を使用して、前記オブジェクトのハッシュ化パラメータを生成するステップであって、前記ハッシュ化パラメータがバイナリ表現である、ステップと、
前記ハッシュ化パラメータの前記バイナリ表現に基づいて、レジスタのセットの中からレジスタを識別するステップであって、前記レジスタのセット内の各レジスタが、前記データセット内のオブジェクトに関するデータを記憶するために使用される、ステップと、
前記ハッシュ化パラメータの前記バイナリ表現に基づいて、前記オブジェクトの前記ハッシュ化パラメータが、前記データセット内の前記オブジェクトの出現回数を指定する集計量に寄与していることを判定するステップと、
前記オブジェクトの前記ハッシュ化パラメータが前記集計量に寄与しているとの判定に応答して、前記レジスタ内に記憶された前記集計量を更新するステップと、
前記レジスタのセット内に記憶された前記集計量に基づいて、データ項目のセットを示す報告出力を生成するステップであって、各データ項目が、特定の集計量において前記デジタル環境内で活動を実行した前記データセット内のオブジェクトの推定数を識別する、ステップとを含む、
コンピュータ可読記憶媒体。
【請求項１８】
各オブジェクトが、ユーザを表し、
集計量が、頻度値を表す、
請求項17に記載のコンピュータ可読記憶媒体。
【請求項１９】
前記ハッシュ化パラメータの前記バイナリ表現に基づいてレジスタのセットの中からレジスタを識別するステップが、
前記ハッシュ化パラメータの前記バイナリ表現の第1の部分を識別するステップと、
前記ハッシュ化パラメータの前記バイナリ表現の前記第1の部分を使用して前記レジスタを識別するステップとを含む、
請求項17に記載のコンピュータ可読記憶媒体。
【請求項２０】
前記レジスタのセット内の各レジスタが、受信されたハッシュ化パラメータに関するデータを記憶するデータ構造を備え、
前記データ構造が、
前記受信されたハッシュ化パラメータの第2の部分における先行ゼロの数を指定するデータを記憶するための第1のフィールドと、
前記受信されたハッシュ化パラメータの前記第2の部分内の後続ビットを指定するデータを記憶するための第2のフィールドと、
(i)前記第1のフィールド内の既存のデータ値が前記先行ゼロの数と一致し、(ii)前記第2のフィールド内の既存のデータ値が前記後続ビットと一致する場合の出現回数を示す集計量を指定するデータを記憶するための第3のフィールドとを含む、
請求項17に記載のコンピュータ可読記憶媒体。
【請求項２１】
前記ハッシュ化パラメータの前記バイナリ表現に基づいて、前記オブジェクトの前記ハッシュ化パラメータが集計量に寄与していることを判定するステップが、
前記ハッシュ化パラメータの前記バイナリ表現の前記第2の部分から先行ゼロの数を決定するステップと、
前記ハッシュ化パラメータの前記バイナリ表現の前記第2の部分から後続ビットを決定するステップと、
前記先行ゼロの数と前記後続ビットとに基づいて、前記ハッシュ化パラメータが前記レジスタの前記データ構造の前記第3のフィールド内に記憶された既存のデータ値に影響を与えることを判定するステップとを含む、
請求項20に記載のコンピュータ可読記憶媒体。
【請求項２２】
前記先行ゼロの数と後続ビットの最大数とに基づいて、前記ハッシュ化パラメータが前記レジスタの前記データ構造の前記第3のフィールド内に記憶された既存のデータ値に影響を与えることを判定するステップが、
前記レジスタの前記データ構造の前記第1のフィールド内に記憶された前記既存のデータ値が前記先行ゼロの数と同じであることを判定するステップと、
前記レジスタの前記データ構造の前記第2のフィールド内に記憶された前記既存のデータ値が前記後続ビットの最大数と同じであることを判定するステップとを含む、
請求項21に記載のコンピュータ可読記憶媒体。
【請求項２３】
前記レジスタ内に記憶された前記集計量を更新するステップが、
前記レジスタの前記データ構造の前記第3のフィールド内に記憶された前記既存のデータ値を1だけ増分するステップを含む、
請求項21に記載のコンピュータ可読記憶媒体。
【請求項２４】
前記レジスタのセット内に記憶された集計量に基づいて、データ項目のセットを示す報告出力を生成するステップであって、各データ項目が、特定の集計量において前記デジタル環境内で活動を実行した前記データセット内のオブジェクトの推定数を識別する、ステップが、
前記レジスタのセット内に記憶された集計量に基づいて、一意の集計量のセットを識別するステップと、
前記集計量のセット内の各々の特定の集計量について、前記特定の集計量において活動を実行した前記データセットのオブジェクトの推定数を決定するステップとを含み、前記推定数を決定するステップが、
前記特定の集計量に一致する集計量を記憶するレジスタの数を決定するステップと、
ハッシュ衝突補正係数に基づいて、前記特定の集計量と一致する前記集計量を記憶する前記レジスタの数を調整するステップと、
前記レジスタのセットの各レジスタ内に記憶されたオブジェクトの平均数を決定するステップと、
前記オブジェクトの平均数によって前記レジスタの調整された数をスケーリングするステップとを含む、
請求項20に記載のコンピュータ可読記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本明細書は、一般に、リソースおよびスペース効率よく、大規模データセットを記憶および分析するためのコンピューティングプロセスに関する。
【背景技術】
【０００２】
デジタル環境内の異なるオブジェクト(例えば、オンライン対話、構成要素、リソースなど)に関するデータを収集および分析することは、コンテンツ、製品、および/またはサービスのプロバイダにとって有益である可能性がある。場合によっては、プロバイダは、多数の(例えば、数百万または数十億)のオブジェクトに関するデータを集計し、例えば、プロバイダのサービスを改善する、および/またはユーザのオンライン体験を改善することができる。例えば、プロバイダは、サーバファームの構成要素がどれくらい頻繁に失敗しているか(または、特定の方法で動作しているか)を決定するために、サーバファームの構成要素またはリソースに関するデータを集計する場合がある。別の例として、プロバイダは、特定のコンテンツと対話するいくつかのデバイスがどれくらい頻繁にコンテンツと対話するかを決定するために、これらのデバイスに関するデータを集計する場合がある。これらのタイプの動作は、特に、大きいデータセットに対して実行された場合、データを効率的に処理、クエリ、および記憶する上で重大な技術的課題を提示する可能性があり、正確な結果を取得することは、重大なシステムレイテンシを引き起こす可能性がある。
【発明の概要】
【課題を解決するための手段】
【０００３】
一般に、本明細書で説明する主題の1つの革新的な態様は、データセット内の複数のオブジェクトに関する活動データを取得する動作であって、データセット内の各オブジェクトがデジタル環境内で活動を実行し、活動データが活動を表す、動作と、データセット内の各データ項目について、データ項目において指定されたオブジェクトの識別子を使用して、オブジェクトのハッシュ化されたパラメータ(以下、ハッシュ化パラメータ)を生成する動作であって、ハッシュ化パラメータがバイナリ表現である、動作と、ハッシュ化パラメータのバイナリ表現に基づいて、レジスタのセットの中からレジスタを識別する動作であって、レジスタのセット内の各レジスタがデータセット内のオブジェクトに関するデータを記憶するために使用される、動作と、ハッシュ化パラメータのバイナリ表現に基づいて、オブジェクトのハッシュ化パラメータがデータセット内のオブジェクトの出現回数を指定する集計量に寄与していることを判定する動作と、オブジェクトのハッシュ化パラメータが集計量に寄与しているとの判定に応答して、レジスタ内に記憶された集計量を更新する動作と、レジスタのセット内に記憶された集計量に基づいて、データ項目のセットを示す報告出力を生成する動作であって、各データ項目が、特定の集計量においてデジタル環境内で活動を実行したデータセット内のオブジェクトの推定数を識別する、動作と、を含む方法において具体化され得る。この態様の他の実施形態は、方法のアクションを実行するように構成された対応するシステム、デバイス、装置、およびコンピュータプログラムを含む。コンピュータプログラム(例えば、命令)は、コンピュータ記憶デバイス上に符号化され得る。これらおよび他の実施形態は、各々、オプションで、以下の特徴のうちの1つまたは複数を含むことができる。
【０００４】
いくつかの実装形態において、各オブジェクトは、ユーザを表し、集計量は、頻度値を表す。
【０００５】
いくつかの実装形態において、ハッシュ化パラメータのバイナリ表現に基づいてレジスタのセットの中からレジスタを識別することは、ハッシュ化パラメータのバイナリ表現の第1の部分を識別することと、ハッシュ化パラメータのバイナリ表現の第1の部分を使用してレジスタを識別することとを含む。
【０００６】
いくつかの実装形態において、レジスタのセット内の各レジスタは、受信されたハッシュ化パラメータに関するデータを記憶するデータ構造を備え、データ構造は、受信されたハッシュ化パラメータの第2の部分における先行ゼロの数を指定するデータを記憶するための第1のフィールドと、受信されたハッシュ化パラメータの第2の部分内の後続ビットを指定するデータを記憶するための第2のフィールドと、(i)第1のフィールド内の既存のデータ値が先行ゼロの数と一致し、(ii)第2のフィールド内の既存のデータ値が後続ビットと一致する場合の出現回数を示す集計量を指定するデータを記憶するための第3のフィールドとを含む。
【０００７】
いくつかの実装形態において、ハッシュ化パラメータのバイナリ表現に基づいて、オブジェクトのハッシュ化パラメータが集計量に寄与していることを判定することは、ハッシュ化パラメータのバイナリ表現の第2の部分から先行ゼロの数を決定することと、ハッシュ化パラメータのバイナリ表現の第2の部分から後続ビットを決定することと、先行ゼロの数と後続ビットとに基づいて、ハッシュ化パラメータがレジスタのデータ構造の第3のフィールド内に記憶された既存のデータ値に影響を与えることを判定することとを含む。
【０００８】
いくつかの実装形態において、先行ゼロの数と後続ビットの最大数とに基づいて、ハッシュ化パラメータがレジスタのデータ構造の第3のフィールド内に記憶された既存のデータ値に影響を与えることを判定することは、レジスタのデータ構造の第1のフィールド内に記憶された既存のデータ値が先行ゼロの数と同じであることを判定することと、レジスタのデータ構造の第2のフィールド内に記憶された既存のデータ値が後続ビットの最大数と同じであることを判定することとを含む。
【０００９】
いくつかの実装形態において、レジスタ内に記憶された集計量を更新することは、レジスタのデータ構造の第3のフィールド内に記憶された既存のデータ値を1だけ増分することを含む。
【００１０】
いくつかの実装形態において、レジスタのセット内に記憶された集計量に基づいて、データ項目のセットを示す報告出力を生成することであって、各データ項目が、特定の集計量においてデジタル環境内で活動を実行したデータセット内のオブジェクトの推定数を識別する、ことが、レジスタのセット内に記憶された集計量に基づいて、一意の集計量のセットを識別することと、集計量のセット内の各々の特定の集計量について、特定の集計量において活動を実行したデータセットのオブジェクトの推定数を決定することと、を含み、決定することが、特定の集計量に一致する集計量を記憶するレジスタの数を決定することと、ハッシュ衝突補正係数に基づいて、特定の集計量と一致する集計量を記憶するレジスタの数を調整することと、レジスタのセットの各レジスタ内に記憶されたオブジェクトの平均数を決定することと、オブジェクトの平均数によってレジスタの調整された数をスケーリングすることと、を含む。
【００１１】
本明細書で説明する主題の特定の実施形態は、データセット内のオブジェクトの分布をそれらの活動データに基づいて効率的に決定することを可能にするスペース効率的な方法において、オブジェクトに関する活動データを(以下でさらに説明するように)記憶することによって、HyperLogLog(HLL)などの確率的データ構造を拡張するように実装され得る。従来の方法は、本明細書で説明する技法および/またはシステムによって必要とされるものよりも大幅に多くの計算リソースおよびストレージリソースを必要とし、それは特に、大きいデータセットに対してこれらの動作を実行する場合である。対照的に、本明細書における技法および/またはシステムは、実質的により少ないストレージを必要とし、オブジェクトの活動データに基づいて、データセット内のオブジェクトの頻度分布を決定するために、より時間およびリソース効率的な処理を実行することができる。
【００１２】
本明細書で説明する主題の1つまたは複数の実施形態の詳細は、添付図面および以下の説明において記載されている。主題の他の特徴、態様、および利点は、説明、図面、および特許請求の範囲から明らかになるであろう。
【図面の簡単な説明】
【００１３】
【図１】データセットに関する情報を計算するための例示的なコンピューティングシステムのブロック図である。
【図２】データセット内のオブジェクトに関する活動データに基づいて、集計分布を計算するための例示的なプロセスのフローチャートである。
【図３】本明細書で説明する方法に関連して使用され得るコンピューティングシステムのブロック図である。
【発明を実施するための形態】
【００１４】
様々な図面における同様の参照番号および名称は、同様の要素を示す。
【００１５】
本明細書は、オブジェクトの活動データに基づいて異なる集計値(例えば、頻度)にわたるデータセット内のオブジェクトの分布を提供するための、HyperLogLogデータ構造などの確率的カーディナリティ推定器を使用するための技法について説明する。本明細書で説明する技法は、従来のHyperLogLog(HLL)データ構造を使用しては不可能である集計(例えば、頻度)分布などを計算することを可能にする方法で、従来のHLLデータ構造を拡張する。本明細書で説明する技法を実装するために、他のタイプの確率的データ構造も使用され得ることが理解されるであろう。
【００１６】
オブジェクトは、ユーザ、スパムイベント、システム構成要素、デジタル資産などの、エンティティ、リソース、または構成要素であり得る。データセット内の各オブジェクトは、デジタル環境における特定のイベントに関連付けられるか、またはそれを実行し、データセット内の活動データは、オブジェクトの活動を表す。これは、例えば、ユーザが特定のデジタルキャンペーンをクリック、視聴、または他の方法で対話したような、特定のデジタル資産(例えば、コンテンツの一部)とのデバイス対話を記述するデータを含むことができる。別の例として、活動データは、ネットワーク環境におけるハードウェア/構成要素イベント(例えば、障害、リセット、停電、ネットワーク呼び出し、メモリアクセス、または他のイベント)に関するログデータを含むことができる。
【００１７】
コンテキストについて、従来のHLLデータ構造は、大きいデータセット内の一意のオブジェクトの数(すなわち、データセットのカーディナリティ)を測定または推定するために使用され得る。しかしながら、従来のHLLデータ構造は、オブジェクトの活動データに基づいて、オブジェクトの集計分布を決定することができない。例えば、従来のHLLデータ構造は、特定のデジタルコンテンツと対話したデータセット内のユーザの数を決定するために使用され得るが、このデータ構造は、特定の頻度(1回、2回、3回など)においてコンテンツを視聴したユーザの数の分布を決定するために使用され得ない。
【００１８】
以下で、および、本明細書全体でより詳細に説明するように、本明細書で説明する技法は、デジタル環境におけるデータセット内のオブジェクトの活動データに基づいて、これらのオブジェクトの集計(例えば、頻度)分布を決定することを可能にするように、従来のHLLデータ構造を拡張する。HLLデータ構造のHLLレジスタは、3つのフィールド、すなわち、最上位の非0ビット(標準のHLLレジスタによってすでに記憶されている)のビット位置も表す、データセット内のオブジェクトの先行ゼロの数を記憶する1つのフィールドと、そのオブジェクトの後続ビット(または、例えば、pビットから構成されたオブジェクトの個別のハッシュ値などの、オブジェクトの別の安定した識別子)を記憶する第2のフィールドと、同じキーを有するすべてのオブジェクトに関する情報を記憶する可換還元関数(commutative reduction function)f(S_t,I)=S_[t+1]の結果に基づく集計カウンタを記憶する第3のフィールドとを含むように拡張され得る。そのような集計カウンタの例は、数ある中で、(1)データセット内のオブジェクトの出現回数をカウントする頻度カウンタ、(2)特定のイベントが記録された最近のタイムスタンプをカウントするカウンタ、および(3)各エラーログレベルにおいてエラーコードが観察された回数をカウントするカウンタを含むことができる。
【００１９】
HLLデータエンジンは、データセット内のオブジェクトをM個のレジスタのセットに割り当てる。オブジェクトのデータが受信されると、オブジェクトの一意の識別子(以下でさらに説明する)は、バイナリ表現を有するハッシュ化パラメータ(以下でさらに説明する)を生成するために、ハッシュ関数を使用してハッシュされる。HLLデータエンジンは、オブジェクトをM個のレジスタのうちの1つに割り当てるために、ハッシュ化パラメータの特定の数のビット(例えば、最初の4ビット)を使用する。
【００２０】
HLLデータエンジンは、オブジェクトが特定の活動に関連付けられたか、またはそれを実行した集計回数を決定する。以下で、および本明細書全体でより詳細に説明するように、HLLデータエンジンは、ハッシュ化パラメータの残りのビット(すなわち、レジスタを識別するために使用されたビット以外のビット)が、例えば、データセット内のオブジェクトの出現回数を指定する集計量に寄与するかどうかを評価することによってこれを成し遂げる。
【００２１】
HLLデータエンジンは、ハッシュ化パラメータの残りのビットに対する先行ゼロの数(最上位の非ゼロビットのビット位置も表す)を決定する。先行ゼロの数がレジスタの第1のフィールド内に記憶された値と同じである場合、HLLデータエンジンは、以前に決定された最上位ビットに関する先行ビットのセット(または、上記で説明したように、別の適切な安定した識別子)を決定する。決定された後続ビットがレジスタの後続pビットフィールド内に記憶された値と同じである場合、HLLデータエンジンは、現在のオブジェクトが、データがレジスタ内にすでに記憶されているオブジェクトと同じであると判定する。結果として、HLLデータエンジンは、例えば、そのフィールド内に記憶された値を1だけ増分するか、または、別の適切な可換還元演算を実行することによって、レジスタの集計カウンタフィールドを更新する。
【００２２】
HLLデータエンジンは、特定の集計値(例えば頻度)においておよび/またはそれを超えて発生したデータセット内のオブジェクトの数を決定することができる。HLLデータエンジンは、レジスタあたりのオブジェクトの平均数によって、集計カウンタが特定の集計値に設定された(例えば、任意のハッシュ衝突を考慮して調整された)レジスタの数をスケーリングすることによって、この値を計算する。
【００２３】
この文書全体の説明に加えて、本明細書で説明するシステム、プログラム、もしくは特徴が情報(例えば、ユーザのソーシャルネットワーク、ソーシャルアクション、もしくは活動、職業、ユーザの選好、またはユーザの現在の場所)の収集を可能にし得るかどうか、およびいつ可能にし得るかと、ユーザがサーバからコンテンツまたは通信を送信されているかどうかの両方に関する選択をユーザが行うことを可能にする制御がユーザに提供されてもよい。加えて、特定のデータは、記憶または使用される前に、個人を特定できる情報が除去されるように、1つまたは複数の方法で処理されてもよい。例えば、ユーザの識別情報は、個人を特定する情報がユーザに対して決定され得ないように処理されてもよく、または、位置情報(都市、ZIPコード、または州レベル)が取得される場合、ユーザの地理的位置は、ユーザの特定の場所が決定され得ないように一般化されてもよい。したがって、ユーザは、どんな情報がユーザについて収集されるか、その情報がどのように使用されるか、および、どんな情報がユーザに提供されるかを制御してもよい。
【００２４】
図1は、データセットに関する情報を計算するための例示的なコンピューティングシステム100のブロック図である。システム100は、一般に、コンピューティングサーバ102と、HLLデータエンジン104と、データ記憶デバイス130と、データ取り込みエンジン140とを含む。以下でより詳細に説明するように、システム100は、オブジェクトに関する活動データに基づいて、データセット内のオブジェクトの集計分布を測定または推定する特定の計算ルールを実行するように構成された専用ハードウェア回路を含む。これらの技法は、様々な用途に適用され得る。例えば、本明細書で説明する技法は、デジタルキャンペーンリーチ評価において使用され得、デジタルキャンペーンリーチ評価は、異なる頻度において特定のキャンペーンと相互作用したユーザの分布、例えば、どれくらい多くの一意のユーザがデジタルコンテンツと1回、2回、3回など相互作用した(例えば、視聴した、クリックしたなど)かを記述するデータを生成することを含む。別の例として、本明細書で説明する技法は、大規模ネットワーク環境におけるハードウェア/構成要素の障害を分析するために使用され得、この分析は、ネットワーク環境において特定の構成要素またはコンピューティングデバイスがどれくらいの頻度で障害を起こすかについての統計を生成することを含む。本明細書で説明する技法は、他の用途において同様に使用されてもよいことが理解されよう。
【００２５】
図1に示すように、システム100は、オブジェクトの活動レベルに基づいてデータセット内のオブジェクトの集計分布を決定するためにHyperLogLog(HLL)データエンジン104を使用するように構成されたコンピューティングサーバ102を含む。本明細書で使用されるエンジンという用語は、タスクのセットを実行するデータ処理装置を指す。
【００２６】
HLLデータエンジン104は、1つまたは複数のプロセッサマイクロチップを含むハードウェア回路(例えば、専用回路)のサブシステムとしてコンピューティングサーバ102内に含まれる。一般に、コンピューティングサーバ102は、コンピューティングサーバ102のコンピュータシステムを集合的に形成する、プロセッサ(例えば、中央処理装置またはグラフィックス処理装置)と、メモリと、データ記憶デバイス106とを含むことができる。これらのプロセッサシステムのプロセッサは、システム100の例示的なディスプレイモニタにおいて出力用のグラフィカル情報を表示するために、メモリ内またはデータセット記憶デバイス106上に記憶された命令を含む、サーバ102による実行のための命令を処理する。
【００２７】
いくつかの実装形態において、記憶された命令の実行は、本明細書で説明するアクションのうちの1つまたは複数をコンピューティングサーバ102またはHLLデータエンジン104によって実行させる。いくつかの実装形態において、複数のプロセッサは、必要に応じて、複数のメモリおよびメモリのタイプとともに使用されてもよい。例えば、コンピューティングサーバ102は、複数の他のコンピューティングデバイスと接続されてもよく、各デバイス(例えば、サーババンク、サーバのグループ、モジュール、またはマルチプロセッサシステム)は、本明細書で説明するアクション、動作、または論理フローの一部を実行する。
【００２８】
システム100は、データ取り込みエンジン140を介して、デジタル環境における複数のオブジェクトに関する活動データを含むデータセットを受信することができる。受信されたデータセットは、コンピューティングサーバ102のHLLデータエンジン104に提供される。
【００２９】
図2を参照して以下でさらに説明するように、HLLデータエンジン104は、メモリ106内のM個のレジスタ125のセット内にデータセットのデータを記憶するために、ハッシュロジック108と、先行ゼロロジック110と、レジスタIDロジック112とを含むロジックエンジン116を使用する。
【００３０】
データ取り込みエンジン140は、クエリも受信し、クエリは、特定の頻度におけるデジタル環境内の活動に関連するか、またはそれを実行したデータセット内のオブジェクトの数に関するデータを要求する。例えば、クエリ150は、特定の回数(例えば、1回、2回、3回など)コンテンツに対して視聴、アクセス、または他の方法で相互作用したデータセット内の一意のユーザの数に関するデータを要求することができる。データ取り込みエンジン140は、クエリ150をコンピューティングサーバ102に送信し、コンピューティングサーバ102は、データセット内の別個のユーザの数と、それらの活動データに基づく、様々な頻度にわたるそれらの分布とを決定するために、HLLデータエンジン104(および、特に、報告ロジック114)を使用する。HLLデータエンジン104は、次いで、単独で、またはコンピューティングサーバ102のフロントエンドエンジンと組み合わせて、決定された分布データを報告出力180として提供する。上記の例において、報告出力180は、様々な頻度、例えば、1回、2回などにおいて特定の活動に関連するか、またはそれを実行したユーザの数を示す、テキストまたは視覚的表現(例えば、ヒストグラム、円グラフなど)の形態における統計であり得る。代替的に、または加えて、報告出力180は、コンピューティングサーバ102または別のコンピューティングデバイスによって処理され得るデータ構造の形態であってもよい。
【００３１】
そのような統計を生成する際に使用される(図1に示すような)HLLデータエンジン104の構成要素、およびこれらの構成要素のそれぞれの動作について、以下に図2を参照してさらに説明する。
【００３２】
図2は、データセット内のオブジェクトに関する活動データに基づいて集計分布を計算するための例示的なプロセス200のフローチャートである。プロセス200は、システム100のコンピューティングリソースと、特に、上記で説明したHLLデータエンジン104とを使用して実装または実行され得る。プロセス200の動作について、例示の目的のみのために以下で説明する。プロセス200の動作は、任意の適切なデバイスまたはシステム、例えば、任意の適切なデータ処理装置によって実行され得る。プロセス200の動作はまた、非一時的コンピュータ可読媒体(図1を参照して説明したメモリおよび/またはデータ記憶デバイス130など)上に記憶され、コンピュータサーバ102の少なくとも1つのプロセッサによって実行されるプログラムされた命令として実装され得る。
【００３３】
データ取り込みエンジン140は、(202において)データセット内の複数のオブジェクトに関する活動データを取得する。いくつかの実装形態において、データ取り込みエンジン140は、データセット内のオブジェクトに関するデジタル環境における活動データを指定するデータログを受信する(各オブジェクトは、データセットにおいて1回または複数回発生する可能性がある)。データログは、オブジェクトに関するオブジェクト識別子とオブジェクトに関する対応する活動データとに対応する個別のフィールド(または、異なるデータ項目を区切るために使用され得るデリミタ)を含むことができる。本明細書で使用されるオブジェクト識別子は、データセット内の特定のオブジェクトを一意に識別する値(例えば、数、英数字文字列、データ構造)である。いくつかの実装形態において、オブジェクト識別子は、バイト(例えば、8ビット)であるが、他の実装形態において、オブジェクト識別子は、例えば、12ビット、16ビット、32ビット、または64ビットによって形成されるデータワードである。場合によっては、オブジェクト識別子を形成するために、64ビット超または64ビット未満などの可変数のビットが使用され得る。
【００３４】
データ取り込みエンジン140は、受信したデータセットをコンピューティングサーバ102のHLLデータエンジン104に送信する。データセット内の各データ項目について、プロセス200は、次いで、以下でさらに説明する動作204、206、208、および210を実行する。これらの動作を実行した結果として、プロセス200は、これらのオブジェクトに関連付けられるか、またはこれらのオブジェクトによって実行された活動データに基づいて、データセット内のオブジェクトの集計分布を蓄積する。
【００３５】
HLLデータエンジン104は、(204において)ハッシュロジック108を使用してオブジェクトに関するハッシュ化パラメータ128を生成する。いくつかの実装形態において、ハッシュロジック108は、ハッシュ化パラメータ(ハッシュ、ハッシュコード、またはハッシュ値と呼ばれる場合もある)を生成するために、1つまたは複数のハッシュ関数(任意の従来のハッシュ関数を含んでもよい)をオブジェクトのオブジェクト識別子に適用する。ハッシュ化パラメータは、バイナリ表現を有し、バイナリ表現の長さは、ハッシュ関数自体、またはハッシュ関数のパラメータに依存する。オブジェクトのオブジェクト識別子のハッシュは、図1に示すように、ハッシュ化パラメータ128として示される。
【００３６】
HLLデータエンジン104は、(206において)オブジェクトに関するデータを記憶するために使用され得るレジスタのセットの中からレジスタを識別する。いくつかの実装形態において、データセットに関するデータは、M個のレジスタ125のセット内に記憶され得る。オブジェクトのハッシュ化パラメータ128の第1の部分(例えば、最初の4ビット)を使用して、レジスタIDロジック112は、オブジェクトに関するデータを記憶するために使用され得るM個のレジスタのうちの1つを識別する。例えば、ハッシュ化パラメータ128(0001  0101  0100)について、レジスタIDロジック112は、M個のレジスタのうちの1つを識別するために、最初の4ビット(0001)を使用することができる。レジスタ125の数は、データセット内のデータ項目の数よりも少ないことが理解されよう。
【００３７】
HLLデータエンジン104は、(208において)ハッシュ化パラメータが頻度量に寄与するかどうかを判定する。いくつかの実装形態において、ハッシュロジック108は、ハッシュ化パラメータ128の第2の部分を識別し、ハッシュ化パラメータ128の第2の部分は、(動作206において上記で説明したように)適切なレジスタを識別するために使用されるビットの第1のセットなしのハッシュ化パラメータのビットを含む。ハッシュ化パラメータ128(0001  0101  0100)について、ビット(0101  0100)は、(前の段落で説明したように)適切なレジスタを識別するためにレジスタIDロジック112によって使用される最初の4ビットを含まない。
【００３８】
先行ゼロロジック110は、ビットの第2の部分またはセット内の先行ゼロの数(最上位の非ゼロビットのビット位置も表す)を決定する。いくつかの実装形態において、先行ゼロロジック110は、ビットの第2のセット内の最初の「1」のビット位置が識別されるまで、ゼロの数を左から右に数えることによって、先行ゼロの数を決定する。例えば、ハッシュ化パラメータ128のビットの第2のセット(0101  0100)に関する先行ゼロの数は、左から右に数えると、最初の「1」に遭遇する前に1つのゼロが識別されるので、1である。
【００３９】
HLLデータエンジン104は、前の段落で識別されたように、ビットの第2のセット内の最上位ビットに関する後続ビットの数を決定する。いくつかの実装形態において、HLLデータエンジン110は、(前の段落で説明したように)左から右に数えたときに最初の「1」が識別される場所である最上位ビットの後のビットの第2のセット内のすべてのビットを識別することによって、後続ビットを決定する。例えば、ビットの第2のセット(0101  0100)内の後続ビットは、ビットの第2のセットに関する先行ゼロをカウントするときに識別された最初の「1」に続くビットであるので、「010100」である。
【００４０】
図1に示すように、M個のレジスタ125のセット内の各レジスタは、3つのフィールド、すなわち、最上位ビットのためのフィールド122と、後続のpビットのためのフィールド124と、集計カウンタのためのフィールド126とを含む。いくつかの実装形態において、後続のpビットを記憶する代わりに、フィールド124は、ビットの第2のセット内の最上位ビットに関する任意の数の後続ビット、または、代替的には、pビットからなる個別のハッシュ値などのオブジェクトに関する安定した識別子を記憶する。
【００４１】
全体で、各レジスタ内に記憶される情報の総量は、2バイト(または16ビット)のみであり得る。対照的に、各レジスタ内に先行ゼロの数を記憶するだけの標準的なHLLアルゴリズムは、通常6ビットのデータを必要とした。言い換えれば、標準的なHLLアルゴリズムと比較して、本明細書で説明するHLLレジスタは、(2バイトをはるかに超える記憶スペースを必要とする、データセット内のオブジェクトに関する活動データ全体を記憶することと比較すると)レジスタごとの記憶要件の重要でない増加のみでデータセット内のオブジェクトに関する追加データを記憶することができる。
【００４２】
いくつかの実装形態において、集計カウンタフィールド126は、データセット内のオブジェクトの出現回数を指定する頻度量を記憶する。以下でさらに説明するように、オブジェクトのハッシュ化パラメータは、(HLLデータエンジン104によって決定された)ハッシュ化パラメータの先行ゼロの数および後続ビットの、それぞれ、(動作206において識別された)レジスタ内のデータ構造120の最上位ビットフィールド122および後続pビットフィールド124内に記憶された値との比較に基づく集計量に寄与する。いくつかの実装形態において、各オブジェクトの頻度カウントを記憶する代わりに、集計カウンタフィールド126は、同じキーを有するオブジェクトに関する情報を集計することができる(例えば、特定のイベントが記録された最近のタイムスタンプをカウントする、各エラーログレベルにおいてエラーコードが観察された回数をカウントする、など)。
【００４３】
先行ゼロロジック110によって決定された先行ゼロの数がフィールド122内に記憶された値未満である場合、先行ゼロロジック110は、データ構造120を更新しない。言い換えれば、フィールド122、124、および126内の既存の値は、保持される。この動作は、集計カウンタフィールド126を更新しないので、オブジェクトのハッシュ化パラメータは、集計(例えば、頻度)量に寄与しない。
【００４４】
先行ゼロロジック110によって決定された先行ゼロの数がフィールド122内に記憶された値を超えると、先行ゼロロジック110は、先行ゼロロジック110によって決定された最上位ビットの値でフィールド122を更新する。そのような場合、HLLデータエンジン104はまた、(1)HLLデータエンジン104によって計算された後続ビット値でフィールド124内に記憶された値を更新し、(2)フィールド126内に記憶された値をゼロにリセットする。
【００４５】
先行ゼロロジック110によって決定された先行ゼロの数がフィールド122内に記憶された値と同じである場合、先行ゼロロジック110は、フィールド122内に記憶された値を更新しない。そのような場合、HLLデータエンジン104は、フィールド124および126内に記憶された値を更新するかどうかも決定する。以下でさらに説明するように、それは、HLLデータエンジン104によって決定された後続ビットを、データ構造120の後続pビットフィールド124内に記憶された値と比較することによって行われる。
【００４６】
HLLデータエンジン104によって決定された後続ビットの値がデータ構造120の後続pビットフィールド124内に記憶された値よりも大きい場合、HLLデータエンジン104は、(1)HLLデータエンジン104によって決定された後続ビットの値でフィールド124を更新し、(2)集計カウンタフィールド126の値をゼロにリセットする。
【００４７】
HLLデータエンジン104によって決定された後続ビットの値が、データ構造120の後続pビットフィールド124内に記憶された値未満である場合、HLLデータエンジン104は、フィールド122、124、および126内に記憶された値を保持する(すなわち、更新しない)。
【００４８】
しかしながら、HLLデータエンジン104によって決定された後続ビットの値が、データ構造120の後続pビットフィールド124内に記憶された値と同じである場合、HLLデータエンジン104は、現在のオブジェクトが、データがデータ構造120内にすでに記憶されているオブジェクトと同じであると判定する。そのような場合、HLLデータエンジン104は、(1)後続pビットフィールド124内にすでに記憶された値を更新せず、(210において)(2)フィールドおよびオブジェクトの現在の値を含む可換還元関数に基づいて、集計カウンタフィールド126内に記憶された値を更新する。集計カウンタフィールド126が頻度カウンタである実装形態において、HLLデータエンジンは、このフィールド126内に記憶された値を1だけ増分することによってこのフィールド内の値を更新する(例えば、集計カウンタフィールド106内に記憶された値が2である場合、HLLデータエンジン104は、その値を1だけ増分し、その結果として3の値を生じる)。頻度以外の集計分布が決定されるべき場合、HLLデータエンジン104は、フィールド126内の値を適切にスケーリング(例えば、乗算、除算、2以上の増分など)するために、可換還元関数を使用する。
【００４９】
上記で説明した動作は、集計カウンタフィールド126を更新することになるので、オブジェクトのハッシュ化パラメータは、集計量に寄与する。
【００５０】
上記で説明したように、いくつかの実装形態において、HLLデータエンジン104は、動作204においてオブジェクトに対して生成された単一のハッシュ表現に基づいて動作206、208、および210を実行する。他の実装形態において、HLLデータエンジン104は、個別のハッシュ表現を使用して動作206、208、および210を実行することができる。言い換えれば、ハッシュロジック108は、個別のハッシュ表現、すなわち、M個のレジスタ125のセット内の適切なレジスタを識別するために使用され得る1つのハッシュ表現と、先行ゼロの数が決定される第2のハッシュ表現と、および後続ビットが決定される第3のハッシュ表現とを生成するためにオブジェクト識別子を使用することができる。上記で説明した動作206から210は、次いで、これらの個別のハッシュ表現を使用して実行され得る。
【００５１】
データ取り込みエンジン140は、(212において)異なる頻度においてデジタル環境内で活動を実行したデータセット内のオブジェクトの数の集計分布を要求するクエリ150を受信する。例えば、クエリ150は、様々な頻度(1回、2回、3回など)において特定のデジタルコンテンツと対話したデータセット内のユーザの数の頻度分布を要求することができる。いくつかの実装形態において、データ取り込みエンジン140は、クエリ150をコンピューティングサーバ102に送信し、コンピューティングサーバ102は、クエリ150をロジックエンジン116の報告ロジック114にルーティングする。
【００５２】
クエリ150に応答して、報告ロジック114は、(212において)関連する活動、またはデジタル環境内でこれらのオブジェクトによって実行された活動に基づいて、データセット内のオブジェクトの集計分布を表す報告出力を生成する。報告ロジック114は、レジスタ125内に記憶された集計値に基づいて集計分布を推定する。報告ロジック114は、以下の動作を実行することによって、この報告出力を生成する。いくつかの実装形態において、報告ロジック114は、レジスタ125のセット内の集計カウンタフィールド126内に記憶された一意の集計値を含む値のセットを識別することによって、様々な可能な集計値を決定する。いくつかの実装形態において、クエリ150は、集計値を識別してもよく、その場合、報告ロジック114は、レジスタのフィールド126内に記憶された様々な可能な集計値を識別する動作をスキップすることができる。いくつかの実装形態において、報告ロジック114は、システムの管理者によって指定された(および、データ記憶デバイス130内に記憶された)集計値のセットにアクセスしてもよく、その場合、報告ロジック114は、レジスタ内に記憶された様々な可能な集計値を識別する動作をスキップすることができる。
【００５３】
いくつかの実装形態において、識別された各集計値について、報告ロジック114は、識別された集計値と同じ値が集計カウンタフィールド126内に記憶されているレジスタの数を決定する。そのような実装形態において、報告ロジック114は、集計カウンタフィールド126内の値が識別された集計値と同じであるすべてのレジスタをカウントする。他の実装形態において、報告ロジック114は、集計カウンタフィールド126内の値が識別された集計値と同じか、またはそれよりも大きいすべてのレジスタをカウントする。
【００５４】
場合によっては、レジスタ125のデータ構造120内に値を記憶および更新するときに、ハッシュ衝突が発生する場合がある。例えば、データセット内の2つの異なるオブジェクトに関する2つのオブジェクト識別子は、ハッシュロジック108によってハッシュされたとき、同じレジスタを更新する場合があり、同じ数の先行ゼロと、同じ後続ビットとを有する場合がある。頻度カウンタの場合、このフィールドの値は、このシナリオでは1だけ増分されなければならないだけであるが、ハッシュ衝突のため、このフィールド126の値は、代わりに誤って2だけ増分される。言い換えれば、両方のオブジェクトが、例えば、同じコンテンツと一度だけ相互作用した可能性があるとしても、集計カウンタフィールド126は、単一のオブジェクトが同じコンテンツと2回相互作用したことを誤って反映する可能性がある。別の集計(例えば、頻度以外)が測定されているいくつかの実装形態において、報告ロジック114は、フィールド126内の値をブール値にマッピングする(例えば、カウント内に含めるまたは含めない)関数を提供する、クエリ(例えば、1つの報告レベルにおいて別の報告レベルよりも多くのエラーを有する、または、2つの境界の間の値を有する)において指定され得る、いくつかの基準を満たすすべてのレジスタをカウントする。
【００５５】
ハッシュ衝突から生じるそのようなエラーを説明するために、報告ロジック114は、集計カウンタフィールド126内の値が識別された集計値と同じであるか、またはそれよりも大きいレジスタのカウントを取得し、次いで、補正係数によってこのカウントを調整(例えば、低減)する。補正係数(ハッシュ衝突補正係数とも呼ばれる)Fは、F(C,M,n)によって表すことができ、M個のレジスタ125のセット内に記憶された、特定の活動を実行した、またはそれに関連するデータセット内の別個のオブジェクトの数(C)に関する識別された集計値(n)において予想されるハッシュ衝突の数を推定する。特定の活動を実行した、またはそれに関連する個別の要素の数(すなわち、データセットのカーディナリティ(C))は、標準的なHLLアルゴリズムを使用して決定される。いくつかの実装形態において、補正係数は、C、M、およびfによってインデックス付けされた低減値の経験的に決定されたルックアップテーブルに基づく。
【００５６】
特定の集計値におけるオブジェクトの総数を取得するために、報告ロジック114は、特定の集計値における(前の段落において決定された)レジスタの調整された数を、レジスタあたりのオブジェクトの平均数によってスケーリングする(例えば、乗算する)。レジスタあたりのオブジェクトの平均数は、(標準的なHLLアルゴリズムを使用して決定される)データセットCのカーディナリティを、レジスタ125の数であるMで割ることによって決定される。報告ロジック114は、識別された周波数ごとに上記の動作を繰り返す。そのようにして、特定の集計値におけるオブジェクトの総数は、以下の式、
【００５７】
【数１】
2022500714.tif 000003
【００５８】
を使用して表すことができ、ここで、(1)Rnは、特定の集計値nにおけるオブジェクトの数であり、(2)Bnは、集計カウンタフィールドがnに設定されたバケットの数であり、(3)Cは、データセットのカーディナリティであり、(4)Mは、レジスタ125の総数であり、(5)F(C,M,n)は、補正係数である。
【００５９】
いくつかの実装形態において、報告ロジック114は、識別された頻度と決定されたオブジェクトの対応する数とを、コンピューティングサーバ102のフロントエンドエンジンに送信し、フロントエンドエンジンは、報告、例えば、報告出力180を生成するためにこれらの値を使用し、報告は、クエリ150が受信されたエンティティに提供される。フロントエンドエンジンは、データ項目のセットを含む統計を生成するために報告ロジック114によって提供された値を使用することができ、各データ項目は、特定の頻度においてデジタル環境内の活動に関連するか、またはそれを実行したデータセット内のオブジェクトの推定数を識別する。これらの統計は、報告出力180上のテキストおよび/またはビジュアル(例えば、ヒストグラム、円グラフなど)の形態であり得、オブジェクトの活動データに基づいて様々な頻度におけるオブジェクトの数の分布を示す。
【００６０】
図3は、クライアント、またはサーバもしくは複数のサーバのいずれかとして、本文書で説明するシステムおよび方法を実装するために使用され得るコンピューティングデバイス300、350のブロック図である。コンピューティングデバイス300は、ラップトップ、デスクトップ、ワークステーション、携帯情報端末、サーバ、ブレードサーバ、メインフレーム、および他の適切なコンピュータなどの、様々な形態のデジタルコンピュータを表すことを意図している。コンピューティングデバイス350は、携帯情報端末、携帯電話、スマートフォン、スマートウォッチ、頭部装着型デバイス、および他の同様のコンピューティングデバイスなどの、様々な形態のモバイルデバイスを表すことを意図している。ここに示されている構成要素、それらの構成要素および関係、ならびにそれらの機能は、例示的であることのみを意図するものであり、この文書において説明および/または特許請求されている実装形態を制限することを意図するものではない。
【００６１】
コンピューティングデバイス300は、プロセッサ302と、メモリ304と、記憶デバイス306と、メモリ304および高速拡張ポート310に接続する高速インターフェース308と、低速バス314および記憶デバイス306に接続する低速インターフェース312とを含む。構成要素302、304、306、308、310、および312の各々は、様々なバスを使用して相互接続され、必要に応じて共通のマザーボード上にまたは他の方法で取り付けられてもよい。プロセッサ302は、高速インターフェース308に結合されたディスプレイ316などの外部入力/出力デバイス上にGUIのためのグラフィカル情報を表示するために、メモリ304内または記憶デバイス306上に記憶された命令を含む、コンピューティングデバイス300内で実行するための命令を処理することができる。他の実装形態において、必要に応じて、複数のメモリおよびメモリのタイプとともに、複数のプロセッサおよび/または複数のバスが使用されてもよい。また、複数のコンピューティングデバイス300が接続されてもよく、各デバイスは、(例えば、サーババンク、ブレードサーバのグループ、またはマルチプロセッサシステムとして)必要な動作の一部を提供する。
【００６２】
メモリ304は、コンピューティングデバイス300内に情報を記憶する。一実装形態において、メモリ304は、コンピュータ可読媒体である。一実装形態において、メモリ304は、揮発性メモリユニットである。別の実装形態において、メモリ304は、不揮発性メモリユニットである。
【００６３】
記憶デバイス306は、コンピューティングデバイス300のための大容量ストレージを提供することができる。一実装形態において、記憶デバイス306は、コンピュータ可読媒体である。様々な異なる実装形態において、記憶デバイス306は、ハードディスクデバイス、光ディスクデバイス、もしくはテープデバイス、フラッシュメモリもしくは他の同様のソリッドステートメモリデバイス、または、ストレージエリアネットワークもしくは他の構成内のデバイスを含むデバイスのアレイであってもよい。一実装形態において、コンピュータプログラム製品は、情報担体において有形に具体化される。コンピュータプログラム製品は、実行されると、上記で説明した方法などの1つまたは複数の方法を実行する命令を含む。情報担体は、メモリ304、記憶デバイス306、またはプロセッサ302上のメモリなどの、コンピュータまたは機械可読媒体である。
【００６４】
高速コントローラ308は、コンピューティングデバイス300のための帯域幅集約的動作を管理し、低速コントローラ312は、より低い帯域幅集約的動作を管理する。そのような仕事の配分は、例示に過ぎない。一実装形態において、高速コントローラ308は、メモリ304、ディスプレイ316(例えば、グラフィックスプロセッサまたはアクセラレータを介して)、および、様々な拡張カード(図示せず)を受け入れることができる高速拡張ポート310に結合される。実装形態において、低速コントローラ312は、記憶デバイス306および低速拡張ポート314に結合される。様々な通信ポート(例えば、USB、Bluetooth(登録商標)、イーサネット(登録商標)、ワイヤレスイーサネット(登録商標))を含むことができる低速拡張ポートは、キーボード、ポインティングデバイス、スキャナ、または、例えば、ネットワークアダプタを介してスイッチもしくはルータなどのネットワーキングデバイスなどの、1つまたは複数の入力/出力デバイスに結合されてもよい。
【００６５】
コンピューティングデバイス300は、図に示すように、いくつかの異なる形態において実装されてもよい。例えば、それは、標準的なサーバ320として、または、そのようなサーバのグループにおいて複数回実装されてもよい。それはまた、ラックサーバシステム324の一部として実装されてもよい。加えて、それは、ラップトップコンピュータ322などのパーソナルコンピュータにおいて実装されてもよい。代替的には、コンピューティングデバイス300からの構成要素は、デバイス350などのモバイルデバイス(図示せず)内の他の構成要素と組み合わされてもよい。そのようなデバイスの各々は、コンピューティングデバイス300、350のうちの1つまたは複数を含んでもよく、システム全体は、互いに通信する複数のコンピューティングデバイス300、350から構成されてもよい。
【００６６】
コンピューティングデバイス350は、プロセッサ352と、メモリ364と、とりわけ、ディスプレイ354、通信インターフェース366、およびトランシーバ368などの入力/出力デバイスなどとを含む。デバイス350はまた、追加のストレージを提供するために、マイクロドライブまたは他のデバイスなどの記憶デバイスを備えてもよい。構成要素350、352、364、354、366、および368の各々は、様々なバスを使用して相互接続され、構成要素のうちのいくつかは、必要に応じて共通のマザーボード上にまたは他の方法で取り付けられてもよい。
【００６７】
プロセッサ352は、メモリ364内に記憶された命令を含む、コンピューティングデバイス350内で実行するための命令を処理することができる。プロセッサは、別個のアナログおよびデジタルプロセッサも含んでもよい。プロセッサは、例えば、ユーザインターフェースの制御、デバイス350によって実行されるアプリケーション、およびデバイス350によるワイヤレス通信などの、デバイス350の他の構成要素の調整を提供してもよい。
【００６８】
プロセッサ352は、ディスプレイ354に結合された制御インターフェース358およびディスプレイインターフェース356を介して、ユーザと通信してもよい。ディスプレイ354は、例えば、TFT LCDディスプレイもしくはOLEDディスプレイ、または他の適切なディスプレイ技術であってもよい。ディスプレイインターフェース356は、グラフィカル情報および他の情報をユーザに提示するためにディスプレイ354を駆動するための適切な回路を備えてもよい。制御インターフェース358は、ユーザからのコマンドを受信し、それらをプロセッサ352への提出のために変換してもよい。加えて、他のデバイスとのデバイス350の近距離通信を可能にするために、プロセッサ352と通信する外部インターフェース362が設けられてもよい。外部インターフェース362は、例えば、有線通信(例えば、ドッキング手順を介する)またはワイヤレス通信(例えば、Bluetooth(登録商標)または他のそのような技術を介する)を提供してもよい。
【００６９】
メモリ364は、コンピューティングデバイス350内に情報を記憶する。一実装形態において、メモリ364は、コンピュータ可読媒体である。一実装形態において、メモリ364は、揮発性メモリユニットである。別の実装形態において、メモリ364は、不揮発性メモリユニットである。拡張メモリ374も設けられ、例えば、SIMMカードインターフェースを含み得る拡張インターフェース372を介してデバイス350に接続されてもよい。そのような拡張メモリ374は、デバイス350のための追加の記憶空間を提供してもよく、または、デバイス350のためのアプリケーションまたは他の情報を記憶してもよい。具体的には、拡張メモリ374は、上記で説明したプロセスを実行または補足するための命令を含んでもよく、セキュア情報も含んでもよい。したがって、例えば、拡張メモリ374は、デバイス350のためのセキュリティモジュールとして提供されてもよく、デバイス350の安全な使用を可能にする命令を用いてプログラムされてもよい。加えて、ハッキング不可能な方法でSIMMカード上に識別情報を配置するなどして、追加の情報とともにSIMMカードを介してセキュアアプリケーションが提供されてもよい。
【００７０】
メモリは、例えば、以下で論じるように、フラッシュメモリおよび/またはMRAMメモリを含んでもよい。一実装形態において、コンピュータプログラム製品は、情報担体において有形に具体化される。コンピュータプログラム製品は、実行されると、上記で説明した方法などの1つまたは複数の方法を実行する命令を含む。情報担体は、メモリ364、拡張メモリ374、またはプロセッサ352上のメモリなどの、コンピュータまたは機械可読媒体である。
【００７１】
デバイス350は、必要に応じてデジタル信号処理回路を含む通信インターフェース366を介してワイヤレスで通信してもよい。通信インターフェース366は、とりわけ、GSM(登録商標)音声通話、SMS、EMS、もしくはMMSメッセージング、CDMA(登録商標)、TDMA、PDC、WCDMA(登録商標)、CDMA200、またはGPRSなどの様々なモードまたはプロトコルの下で通信を提供してもよい。そのような通信は、例えば、無線周波数トランシーバ368を介して生じてもよい。加えて、Bluetooth(登録商標)、WiFi、または他のそのようなトランシーバ(図示せず)を使用するなどして、短距離通信が生じてもよい。加えて、GPS受信機モジュール370は、デバイス350上で実行されているアプリケーションによって必要に応じて使用され得る追加のワイヤレスデータをデバイス350に提供してもよい。
【００７２】
デバイス350はまた、オーディオコーデック360を使用して聴覚的に通信してもよく、オーディオコーデック360は、ユーザからの発話情報を受信し、それを使用可能なデジタル情報に変換してもよい。オーディオコーデック360は、同様に、例えば、デバイス350のハンドセット内のスピーカを介するなどして、ユーザのための可聴音を生成してもよい。そのような音は、音声電話通話からの音を含んでもよく、記録された音(例えば、音声メッセージ、音楽ファイルなど)を含んでもよく、デバイス350上で動作するアプリケーションによって生成された音を含んでもよい。
【００７３】
コンピューティングデバイス350は、図に示すように、いくつかの異なる形態において実装されてもよい。例えば、それは、携帯電話380として実装されてもよい。それはまた、スマートフォン382、携帯情報端末、または他の同様のモバイルデバイスの一部として実装されてもよい。
【００７４】
本明細書で説明するシステムおよび技法の様々な実装形態は、デジタル電子回路、集積回路、特別に設計されたASIC、コンピュータハードウェア、ファームウェア、ソフトウェア、および/またはそれらの組合せにおいて実現され得る。これらの様々な実装形態は、少なくとも1つのプログラム可能なプロセッサを含むプログラム可能なシステム上で実行可能および/または解釈可能な1つまたは複数のコンピュータプログラムにおける実装形態を含むことができ、プログラム可能なプロセッサは、記憶システム、少なくとも1つの入力デバイス、および少なくとも1つの出力デバイスからデータおよび命令を受信し、それらにデータおよび命令を送信するように結合された、専用または汎用であり得る。
【００７５】
プログラム、ソフトウェア、ソフトウェアアプリケーション、またはコードとしても知られるこれらのコンピュータプログラムは、プログラム可能なプロセッサのための機械命令を含み、高級手続き型および/もしくはオブジェクト指向プログラミング言語、ならびに/またはアセンブリ/機械語において実装され得る。本明細書で使用される「機械可読媒体」「コンピュータ可読媒体」という用語は、任意のコンピュータプログラム製品、装置、および/またはデバイス、例えば、機械可読信号として機械命令を受信する機械可読媒体を含む、プログラム可能なプロセッサに機械命令および/またはデータを提供するために使用される磁気ディスク、光ディスク、メモリ、プログラマブルロジックデバイス(PLD)を指す。「機械可読信号」という用語は、機械命令および/またはデータをプログラム可能なプロセッサに提供するために使用される任意の信号を指す。
【００７６】
ユーザとの対話を提供するために、本明細書で説明するシステムおよび技法は、ユーザに情報を表示するための表示デバイス、例えば、CRT(陰極線管)またはLCD(液晶ディスプレイ)と、ユーザがコンピュータに入力を提供するキーボードおよびポインティングデバイス、例えば、マウスまたはトラックボールとを有するコンピュータにおいて実装され得る。対話をユーザに提供するために、同様に他の種類のデバイスが使用され得、例えば、ユーザに提供されるフィードバックは、任意の形態の感覚フィードバック、例えば、視覚フィードバック、聴覚フィードバック、または触覚フィードバックであり得、ユーザからの入力は、音響、音声、または触覚入力を含む任意の形態において受け取られ得る。
【００７７】
本明細書で説明するシステムおよび技法は、例えば、データサーバとしてバックエンド構成要素を含むか、または、アプリケーションサーバなどのミドルウェア構成要素を含むか、または、ユーザが本明細書で説明するシステムおよび技法の実装形態を対話することができるグラフィカルユーザインターフェースもしくはWebブラウザを有するクライアントコンピュータなどのフロントエンド構成要素を含むか、または、そのようなバックエンド構成要素、ミドルウェア構成要素、もしくはフロントエンド構成要素の任意の組合せを含むコンピューティングシステムにおいて実装され得る。システムの構成要素は、通信ネットワークなどのデジタルデータ通信の任意の形式または媒体によって相互接続され得る。通信ネットワークの例は、ローカルエリアネットワーク(LAN)、ワイドエリアネットワーク(WAN)、およびインターネットを含む。
【００７８】
コンピューティングシステムは、クライアントとサーバとを含むことができる。クライアントおよびサーバは、一般に、互いにリモートであり、典型的には、通信ネットワークを介して対話する。クライアントとサーバとの関係は、それぞれのコンピュータ上で実行され、互いにクライアント-サーバ関係を有するコンピュータプログラムによって生じる。
【００７９】
本明細書で使用される「モジュール」、「エンジン」、および「構成要素」という用語は、限定はしないが、コンピュータの処理ユニット/デバイスに1つまたは複数の機能を実行させるプログラムコードを含む1つまたは複数のソフトウェアプログラムを実行するように構成された1つまたは複数のコンピュータを含むことが意図されている。「コンピュータ」という用語は、デスクトップコンピュータ、ラップトップコンピュータ、メインフレームコンピュータ、携帯情報端末、サーバ、ハンドヘルドデバイス、スマートフォン、タブレットコンピュータ、電子リーダ、またはデータを処理することができる任意の他の電子デバイスなどの、任意のデータ処理またはコンピューティングデバイス/システムを含むことが意図されている。
【００８０】
いくつかの実施形態について説明した。それにもかかわらず、本発明の要旨および範囲から逸脱することなく、様々な修正がなされてもよいことが理解されよう。したがって、他の実施形態は、以下の特許請求の範囲内にある。本明細書は、多くの特定の実装形態の詳細を含んでいるが、これらは、特許請求され得るものの範囲に対する制限として解釈されるべきではなく、特定の実施形態に特有であり得る特徴の説明として解釈されるべきである。別個の実施形態の文脈において本明細書で説明されている特定の特徴は、単一の実施形態において組み合わせて実装することもできる。
【００８１】
逆に、単一の実施形態の文脈において説明した様々な特徴は、複数の実施形態において別々に、または任意の適切な部分的組合せにおいて実装することもできる。さらに、特徴が特定の組合せにおいて作用するものとして上記で説明され、そのように当初に特許請求されている場合さえあるが、特許請求されている組合せからの1つまたは複数の特徴は、場合によっては、組合せから削除することができ、特許請求されている組合せは、部分的組合せまたは部分的組合せのバリエーションを対象としてもよい。
【００８２】
同様に、図面において動作が特定の順序で示されているが、これは、所望の結果を達成するために、そのような動作が示された順序またはシーケンシャルな順序で実行されること、または、すべての例示された動作が実行されることを必要とするものとして理解されるべきではない。特定の状況では、マルチタスクおよび並列処理が有利な場合がある。さらに、上記で説明した実施形態における様々なシステムモジュールおよび構成要素の分離は、すべての実施形態においてそのような分離を必要とするものとして理解されるべきではなく、説明されているプログラム構成要素およびシステムは、一般に、単一のソフトウェア製品に統合されるか、または複数のソフトウェア製品にパッケージ化され得ることが理解されるべきである。
【００８３】
主題の特定の実施形態について説明してきた。他の実施形態は、以下の特許請求の範囲内にある。例えば、特許請求の範囲において列挙されたアクションは、異なる順序で実行されても、依然として所望の結果を達成することができる。一例として、添付図面に示されているいくつかのプロセスは、所望の結果を達成するために、示されている特定の順序またはシーケンシャルな順序を必ずしも必要としない。
【符号の説明】
【００８４】
100  コンピューティングシステム、システム
102  コンピューティングサーバ、サーバ
104  HLLデータエンジン、HyperLogLog(HLL)データエンジン
106  データ記憶デバイス、データセット記憶デバイス、メモリ、集計カウンタフィールド
108  ハッシュロジック
110  先行ゼロロジック
112  レジスタIDロジック
114  報告ロジック
116  ロジックエンジン
120  データ構造
122  最上位ビットのためのフィールド、最上位ビットフィールド、フィールド
124  後続のpビットのためのフィールド、後続pビットフィールド、フィールド
125  レジスタ
126  集計カウンタのためのフィールド、集計カウンタフィールド、フィールド
128  ハッシュ化パラメータ
130  データ記憶デバイス
140  データ取り込みエンジン
150  クエリ
180  報告出力
300  コンピューティングデバイス
302  プロセッサ
304  メモリ
306  記憶デバイス
308  高速インターフェース、高速コントローラ
310  高速拡張ポート
312  低速インターフェース、低速コントローラ
314  低速バス、低速拡張ポート
316  ディスプレイ
320  サーバ
322  ラップトップコンピュータ
324  ラックサーバシステム
350  コンピューティングデバイス、デバイス
352  プロセッサ
354  ディスプレイ
356  ディスプレイインターフェース
358  制御インターフェース
360  オーディオコーデック
362  外部インターフェース
364  メモリ
366  通信インターフェース
368  トランシーバ、無線周波数トランシーバ
370  GPS受信機モジュール
372  拡張インターフェース
374  拡張メモリ
380  携帯電話
382  スマートフォン
【図１】
2022500714.tif 000004
【図２】
2022500714.tif 000005
【図３】
2022500714.tif 000006
【国際調査報告】
2022500714.tif 000007
2022500714.tif 000008
2022500714.tif 000009