(57)【要約】  メディア識別システムは、既知のメディアサンプルのための参照フィンガープリントを生成すると共に、参照データベースに参照フィンガープリントを保存する。メディア識別システムは、参照フィンガープリントを使用して、未知のメディアサンプルから生成されるフィンガープリントとマッチングを行い、未知のサンプルを識別する。参照データベースに新たな参照フィンガープリントを保存するときには、データベースのパーティションは、メディア識別システムが使用する際にデータベースにかかる検索負荷を平衡化するよう選択される。例えば、選択されたパーティションは、メディア識別システムによってパーティションのアクセスレートに少なくとも部分的に基づいて判定することができる。新たな参照フィンガープリントは、他のパーティションよりも相対的に低いアクセスレートを有するパーティション内に配置されるようになり、これにより、メディア識別システムによってパーティションにかかる検索負荷を平衡化するようにする。【選択図】      図１
2012529704.tif 000002
【特許請求の範囲】
【請求項１】
データベースに参照フィンガープリントを追加してメディア識別システムによってデータベースにかかる検索負荷を平衡化するためのコンピュータに実装される方法であって、
各々が既知のメディアサンプルから生成される参照フィンガープリントのセットを保存する複数のパーティションを含む参照データベースを保持するステップと、
前記メディア識別システムによって前記パーティションのアクセスレートを監視するステップと、
前記参照データベース内に１又はそれ以上の新たな参照フィンガープリントを保存するリクエストを受信するステップと、
前記パーティションのアクセスレートに少なくとも部分的に基づいて前記参照データベースのパーティションを選択するステップと、
前記参照データベースの選択されたパーティション内に前記新たな参照フィンガープリントを保存するステップと、
を含む、方法。
【請求項２】
前記各パーティションが、前記参照データベースの論理的に定義されたデータリポジトリである、請求項１に記載の方法。
【請求項３】
前記参照データベースを保持するステップが、
前記参照フィンガープリントの特徴により前記データベースにおいて前記参照フィンガープリントのインデックスを作成するステップと、
前記参照データベースの同じパーティション内で同じインデックスが作成された特徴を有する前記参照フィンガープリントをグループ化するステップと、
を含む、請求項１に記載の方法。
【請求項４】
前記参照データベースが更に、参照データベース内の参照フィンガープリントに対応する既知のメディアサンプルに関するメタデータを更に含む、請求項１に記載の方法。
【請求項５】
前記参照データベースの特定のパーティションに対するアクセスレートが、指定された時間期間にわたって前記パーティションから参照フィンガープリントを読み出す複数のリクエストを含む、請求項１に記載の方法。
【請求項６】
前記参照フィンガープリントのうちの１又はそれ以上が、既知のオーディオサンプルから生成される、請求項１に記載の方法。
【請求項７】
前記参照フィンガープリントのうちの１又はそれ以上が、既知のビデオサンプルから生成される、請求項１に記載の方法。
【請求項８】
データベースに参照フィンガープリントを追加して、メディア識別システムによって前記データベースにかかる検索負荷を平衡化するためのコンピュータプログラム製品であって、前記コンピュータプログラム製品は、
各々が既知のメディアサンプルから生成される参照フィンガープリントのセットを保存する複数のパーティションを含む参照データベースを保持するステップと、
前記メディア識別システムによって前記パーティションのアクセスレートを監視するステップと、
前記参照データベース内に１又はそれ以上の新たな参照フィンガープリントを保存するリクエストを受信するステップと、
前記パーティションのアクセスレートに少なくとも部分的に基づいて前記参照データベースのパーティションを選択するステップと、
前記参照データベースの選択されたパーティション内に前記新たな参照フィンガープリントを保存するステップと、
を含む動作を実行するためのコンピュータプログラムコードを含むコンピュータ読み取り可能記憶媒体を備える、コンピュータプログラム製品。
【請求項９】
前記各パーティションが、前記参照データベースの論理的に定義されたデータリポジトリである、請求項８に記載のコンピュータプログラム製品。
【請求項１０】
前記参照データベースを保持するステップが、
前記参照フィンガープリントの特徴により前記データベースにおいて前記参照フィンガープリントのインデックスを作成するステップと、
前記参照データベースの同じパーティション内で同じインデックスが作成された特徴を有する前記参照フィンガープリントをグループ化するステップと、
を含む、請求項８に記載のコンピュータプログラム製品。
【請求項１１】
前記参照データベースが更に、参照データベース内の参照フィンガープリントに対応する既知のメディアサンプルに関するメタデータを更に含む、請求項８に記載のコンピュータプログラム製品。
【請求項１２】
前記参照データベースの特定のパーティションに対するアクセスレートが、指定された時間期間にわたって前記パーティションから参照フィンガープリントを読み出す複数のリクエストを含む、請求項８に記載のコンピュータプログラム製品。
【請求項１３】
前記参照フィンガープリントのうちの１又はそれ以上が、既知のオーディオサンプルから生成される、請求項８に記載のコンピュータプログラム製品。
【請求項１４】
前記参照フィンガープリントのうちの１又はそれ以上が、既知のビデオサンプルから生成される、請求項８に記載のコンピュータプログラム製品。
【請求項１５】
メディア識別システムにおいて、
各々が既知のメディアサンプルから生成される参照フィンガープリントのセットを保存する複数のパーティションを含む参照データベースと、
未知のメディアサンプルから生成された検査フィンガープリントを前記参照データベース内の１又はそれ以上参照フィンガープリントと比較することによって前記未知のメディアサンプルとマッチングするように構成されるフィンガープリントマッチングシステムと、
前記既知のメディアサンプルから新たな参照フィンガープリントを生成するように構成され、且つ前記フィンガープリントマッチングシステムによって前記パーティションのアクセスレートに少なくとも部分的に基づいて選択される前記参照データベースのパーティション内に前記新たな参照フィンガープリントを保存するように構成されるフィンガープリント生成システムと、
を備える、メディア識別システム。
【請求項１６】
前記各パーティションが、前記参照データベースの論理的に定義されたデータリポジトリである、請求項１５に記載のシステム。
【請求項１７】
前記参照データベースを保持することは、前記参照フィンガープリントの特徴によって該参照フィンガープリントのインデックスを作成したインデックスを含み、前記同じインデックスが作成された特徴を有する前記参照フィンガープリントが、前記参照データベースの同じパーティション内でグループ化される、請求項１５に記載のシステム。
【請求項１８】
前記参照データベースが更に、前記参照データベース内の参照フィンガープリントに対応する前記既知のメディアサンプルに関するメタデータを含む、請求項１５に記載のシステム。
【請求項１９】
前記参照データベースの特定のパーティションに対するアクセスレートが、指定された時間期間にわたって前記パーティションから参照フィンガープリントを読み出す複数のリクエストを含む、請求項１５に記載のシステム。
【請求項２０】
前記参照フィンガープリントのうちの１又はそれ以上が、既知のオーディオサンプルから生成される、請求項１５に記載のシステム。
【請求項２１】
前記参照フィンガープリントのうちの１又はそれ以上が、既知のビデオサンプルから生成される、請求項１５に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に、メディア識別システムに関し、詳細には、未知の検査サンプルとのマッチングを行うためのメディア識別システムによって使用される参照フィンガープリントのデータベースの管理に関する。
【背景技術】
【０００２】
デジタルフィンガープリント法は、オーディオ又はビデオサンプルなどのような未知のデジタルメディアサンプルを識別するのに使用できる処理である。例示的なメディア識別システムでは、デジタルフィンガープリントは、幾つかの既知のメディアサンプルの各々に対して生成され、このメディアサンプルは、データファイル、放送番組、ストリーミングメディア、又は他の種々のメディアソースのうちのいずれかから取得することができる。各デジタルフィンガープリントは、デジタルフィンガープリントが生成されたメディアサンプルについての特徴情報を含むデータセグメントを含むことができる。引用により全体が本明細書に組み込まれる米国特許第７、５１６、０７４号では、データ信号から特徴的なデジタルフィンガープリントを生成する実施形態について記載している。
【０００３】
参照フィンガープリントは、データベース又はリポジトリに保存され、参照フィンガープリントを参照フィンガープリントの対応するメディアサンプル及び／又は該メディアサンプルに関係するメタデータと関連付けるようにしてインデックスが作成される。米国特許第７、５１６、０７４号はまた、データベース内の参照フィンガープリントのインデックスを作成する実施形態も開示している。参照フィンガープリントのデータベースを使用して、未知のメディアサンプルを識別することができる。検査フィンガープリントは、未知のメディアアイテムを識別するためにメディアアイテムのサンプルから生成される。次に、参照フィンガープリントのデータベースに照らして検査フィンガープリントのマッチングを行い、マッチングが判明した場合、未知のメディアサンプルは、マッチングする参照フィンガープリントに関連付けられたメディアサンプルであると宣言される。種々の正確なマッチング及びファジーマッチングアルゴリズム、並びに正規マッチングを宣言するための基準を使用することができる。
【０００４】
参照フィンガープリントは、通常、フィンガープリントのベクトル座標又はフィンガープリントに含まれるデータの他の何らかの部分などのような、フィンガープリントに共通する特徴に従ってデータベースにインデックスが作成される。この種のインデックス作成方式は、多段階マッチング処理を考慮する。例えば、検査フィンガープリントを調べ、データベース内の参照フィンガープリントの１又はそれ以上の候補セットとの予備的なマッチングをインデックス作成方式に基づいて判定することができる。次いで、識別されたそれぞれの候補を検査フィンガープリントと比較し（例えば、ビット単位で）、マッチングが存在するかどうかを判定する。この多段階マッチング処理は、より計算集約的なフィンガープリント比較を行う前に候補リストを絞り込むことによって、データベース内の各々及び全ての参照フィンガープリントにアクセスして検査フィンガープリントと各参照フィンガープリントを比較する必要性が排除される。
【０００５】
一部のメディアマッチングシステムのアプリケーションでは、拡大する既知のメディアサンプルセットに照らして未知のメディアサンプルをマッチングする。例えば、未知のメディアサンプルは、オンラインビデオ共有ウェブサイトからのビデオクリップであってもよく、これらのメディアサンプルを放送番組のような既知のメディアサンプルに照らして検査することができる。既知のメディアサンプルセットが増大するにつれて、新たな参照フィンガープリントが上記サンプルから生成され、その後、参照フィンガープリントデータベースに追加される。
【０００６】
参照フィンガープリントのデータベースが極めて大きなアプリケーションでは、データベースは、「サイロ」とも呼ばれる多数の物理パーティション及び／又は論理パーティションにわたって実装することができる。参照データベースが複数のパーティションを含む場合、参照サンプルは、通常、各パーティションに含まれるデータ量に基づいて実質的に均等にパーティションにわたって配信される。参照フィンガープリントを保存するための特定のアルゴリズムは、参照フィンガープリントが得られるメディアサンプルのソースに依存することができる。放送番組から取得する場合、例えば、サンプルは、サンプルを取得した放送チャネル又はサンプルの他のメタ特性のいずれかに応じてパーティションに追加することができる。
【発明の概要】
【発明が解決しようとする課題】
【０００７】
このアルゴリズムは、各パーティションに保存されたデータ量を平衡化しようとしているが、目的とするデータベースの使用に最適な状況をもたらすことはできない。これは、実際には、メディアサンプルのメタ特性とこれらメディアサンプルの人気との間に相関関係があることが多いことに起因する。例えば、メディアマッチングシステムの実施例では、検査サンプルは、別のソースではなく一般的にはある特定のソースに由来することが多い。これは、インデックスを作成するシステムでは、検査サンプルに対する候補をパーティションにグループ化するので、他のパーティションに比べてパーティションの一部に対してより多くのアクセス負荷（例えば、読み出しリクエスト）をもたらす傾向になる。メディアマッチングシステムによるアクセスに基づいて結果として生じる一部のパーティションに対する過負荷は、システムの最適以下の性能を生じる可能性が高い。
【課題を解決するための手段】
【０００８】
メディア識別システムの参照データベースに参照フィンガープリントを保存するときに、本発明の実施形態は、メディア識別システムが参照フィンガープリントを使用する際のデータベースにかかる検索負荷を平衡化する。詳細には、データベースに１又はそれ以上の新たな参照フィンガープリントを保存するときに、本発明の実施形態は、新たな参照フィンガープリントの保存対象となるデータベースの１又はそれ以上のパーティションを選択する。この選択されたパーティションは、メディア識別システムによってパーティションのアクセスレート（例えば、所与の時間期間にわたる各パーティションに対する検索回数）に少なくとも部分的に基づいて決定される。１つの実施形態では、新たな参照フィンガープリントは、その他のパーティションに比べて比較的低いアクセスレートを有するパーティションに配置されるようになる。パーティションへの参照フィンガープリントの追加により、当該パーティションに対するアクセスレートが高くなる傾向があるので、相対的に低いアクセスレートを有するデータベースのパーティションに新たな参照フィンガープリントを追加することで、メディア識別システムによってパーティションにかかる検索負荷が平衡化される傾向になる。
【０００９】
１つの実施形態では、本システムは、既存のパーティションの検索負荷を低減するために新たなパーティションを作成して既存のデータベースにリンクさせることができる。例えば、既存の参照データファイルを新たに作成されたパーティションに転送することによって、全てのパーティションの検索負荷が更に平衡化された状態になり、これによってデータベース全体のアクセスレートを向上させることができる。他の実施形態では、システムは、フィンガープリントのアクセスレートに応じてデータベース内の既存の参照フィンガープリントを移動することにより、パーティションにかかる負荷の再平衡化を行うことができる。パーティションは、参照データに関するメタ情報によりグループ化することができ、検索負荷の平衡化は、各新たな参照フィンガープリントに対して個々に行うのではなく、グループレベルで行うことができる。
【図面の簡単な説明】
【００１０】
【図１】本発明の実施形態による、メディアフィンガープリントシステムの概略図である。
【図２】本発明の実施形態による、参照フィンガープリントのデータベースの概略図である。
【図３】図２のデータベースに参照フィンガープリントを保存するデータ構造の概略図である。
【図４】本発明の実施形態による、フィンガープリントマッチングシステムで使用されるデータベースの概略図である。
【図５Ａ】本発明の実施形態による、デジタルフィンガープリントをマッチングするアプリケーションにより実行されるステップを示すフロー図である。
【図５Ｂ】本発明の実施形態による、デジタルフィンガープリントをマッチングするアプリケーションにより実行されるステップを示すフロー図である。
【図６】データ構造内に保存されることになる参照フィンガープリントの候補セットを描いた、図３に示すデータ構造の実施例である。
【図７】本発明の実施形態による、参照フィンガープリントのデータベースにかかる検索負荷を平衡化する方法のフロー図である。
【００１１】
各図は、単に例証の目的で本発明の種々の実施形態を示している。当業者であれば、本明細書に例示された構造及び方法の代替の実施形態を本明細書に記載する発明の原理から逸脱することなく利用できることは、以下の説明から容易に認識されるであろう。
【発明を実施するための形態】
【００１２】
デジタルフィンガープリントアプリケーションでは、未知のオーディオ又はビデオコンテンツからサンプリングされたデジタルフィンガープリントを既知のオーディオ又はビデオプログラミングから取得されたデジタルフィンガープリントの参照データベースと比較して、未知のコンテンツを識別するようにする。未知のコンテンツのメタデータに修正を許可する場合、或いは、他の多くのメディア識別システムのアプリケーションの中で著作権のある素材の配信制御を可能にする場合には、未知のコンテンツを識別することが望ましい。
【００１３】
図１はデータベースシステムにおいてデジタルフィンガープリントアプリケーションを実施するための構成を示す。参照フィンガープリントのデータベース１００及びデータベースサーバ１２５が図示されている。データベースサーバ１２５は、メディアサンプルから参照フィンガープリントを作成するフィンガープリント生成アルゴリズムを実行する。１つの実施形態では、データベースサーバは、放送局１３０により送信された放送番組１４０から参照フィンガープリントを生成する。他の実施形態では、データベースサーバ１２５は、ファイル共有ネットワーク又はインターネットウェブサイトなどのコンピュータネットワーク１３５からメディアコンテンツをサンプリングし、このサンプリングされたメディアコンテンツから参照フィンガープリントを作成する。データベースサーバ１２５は、生成された参照フィンガープリントをデータベース１００上に保存し、これにより、本明細書で説明するように、これら参照フィンガープリントを使用して未知のメディアサンプルを識別することができる。
【００１４】
図２は、データベース１００の１つの実施形態をより詳細に示す。データベース１００は、データ構造１１０内に保存された標準サイズの複数の参照フィンガープリント１０５を含む。参照フィンガープリント１０５は、オーディオ又はビデオコンテンツの部分についてのデジタルフィンガープリントを含むことができる。また、データベース１００には、各参照フィンガープリント１０５に関連付けられたメタデータ１１５が含められる。メタデータ１１５は、参照フィンガープリント１０５に帰属するデジタルメディアコンテンツに関して、タイトル、アーティスト、ジャンル、製作者、及び著作権日付などの情報を含むことができる。メタデータ１１５は、放送番組１４０から抽出するか、或いは、データベースサーバ１２５により取得することができる。データベース１００はまた、本明細書でより詳細に説明するように、検査フィンガープリントとマッチングできるフィンガープリントの候補セットを識別するのに使用可能な幾つかのインデックス１２０を含む。
【００１５】
インデックス作成方法は、検査フィンガープリントとマッチングできる参照フィンガープリントの候補セットを識別するのに使用される。フィンガープリントの候補セットは、論理的に予め定義された「バケット」に候補セットが出現することに基づいて識別され、ここで各バケットは、当該バケットに関連付けられたテンプレートにより指定される特定のビット位置において同じビット値を共有するフィンガープリントグループを参照する。対応するテンプレート内で指定されたビット位置において検査フィンガープリントにマッチングするビット値のフィンガープリントを含むバケットがマークされる。フィンガープリントは多くの異なるバケットにおいて参照することができ、各マークされたバケットは、当該バケットによって参照されたフィンガープリントがマッチである可能性が高いことを示しているので、フィンガープリントのグループは、最も高いものとしてマークされたバケットにおけるフィンガープリントの再出現に基づいて、当該フィンガープリントの候補セットとして識別することができる。
【００１６】
図３は、参照フィンガープリント１０５が保存されるデータ構造１１０をより詳細に示している。データ構造１１０は、パーティション２００と呼ばれる複数のデータリポジトリを含む。１つの実施形態では、パーティション２００は、例えば、ＬＤＡＰプロトコルによって論理的に定義され、各パーティション２００の実際のデータコンテンツを同じ位置又は異なる位置にある幾つかの物理的記憶メディア上に保存することができる。各パーティション２００のコンテンツは、参照フィンガープリント１０５のサブセットを含む。
【００１７】
図４に示す典型的なマッチングのアプリケーションでは、未知のメディアコンテンツ３００は、検査フィンガープリント３１０を生成するためにデータベースサーバ１２５によりサンプリングされる。未知のコンテンツ３００は、ユーザ生成のコンテンツをアップロードする許可を与えるウェブサイトのような、ウェブサイトからサンプリングされたデジタルオーディオ又はビデオデータを含むことができる。サンプリングは、データベースサーバ１２５にあるソフトウェアプログラムによって、或いは、検査フィンガープリント３１０をデータベースサーバ１２５に通信する遠隔プログラムによって自動的に実行することができる。このようなソフトウェアプログラムは、サンプリングするために共有にされたオーディオ又はビデオコンテンツを探してインターネットを自動的にクロールする、一般に「ロボット」又は「スパイダ」と呼ばれる自動プログラムとすることができる。未知のコンテンツ３００はまた、ファイル共有ネットワークにわたって共有されるデータを含むこともできる。
【００１８】
検査フィンガープリント３１０は、未知のコンテンツ３００の一部から取得したデジタルフィンガープリントであってもよい。同じオーディオ又はビデオストリームから複数のデジタルフィンガープリントを取得することができる。１つの実施例では、新たな検査フィンガープリントは、サンプリングされたコンテンツから５秒毎に生成される。検査フィンガープリント３１０が取得されると、データベース１００に照らしてマッチングを行い、データベース１００に含まれる参照フィンガープリント１０５が検査フィンガープリント３１０にマッチングするかどうかを判定することができる。マッチングが判明した場合、マッチングした参照フィンガープリント３０５のメタデータ１１５を調べて、未知のコンテンツ３００を識別し、例えば、著作権所有者への通知、コンテンツ内への広告の挿入、又はコンテンツのブロックなど、適切で更なるステップを行うことができる。検査フィンガープリント３１０は、参照フィンガープリント１０５と完全にマッチングする必要はない。忠実度の損失又は未知のコンテンツ３００のノイズに起因する他のひずみは、検査フィンガープリント３１０と対応する参照フィンガープリント１０５との間の相違をもたらす結果となる場合があるので、十分に高レベルの確実さで検査フィンガープリントを識別するには部分的なマッチングで十分であると考えられる。
【００１９】
図５Ａは、参照フィンガープリント１０５に照らして検査フィンガープリント３１０をマッチングする方法の概略を示す。ブロック４００に示す第１のステップでは、参照フィンガープリント５００の候補セットが生成される。ブロック４０５に示す第２のステップでは、検査フィンガープリント３１０が、候補セット５００の参照フィンガープリントの各々と比較され、マッチングするかどうかを判定する。
【００２０】
図５Ｂは、図５Ａの識別ステップ４００のある実施を示す。図５Ｂにおいて、参照フィンガープリントの候補セット５００を識別するのにインデックス作成方法が使用される。各インデックス１２０は、参照フィンガープリントの特徴に従って参照フィンガープリントのインデックスを作成する。例えば、インデックスは、特定の座標に対して同じ値を有する参照フィンガープリントをグループ化することができる。ブロック４１０に示す第１のステップでは、検査フィンガープリント１０５は第１のインデックス１２０と比較され、検査フィンガープリントとマッチングすることができるフィンガープリントの候補セットを識別する。識別された場合、ブロック４２０に示すように、インデックス１２０に関連付けられた参照フィンガープリントがマークされる。インデックスの全てが検査フィンガープリント３１０と比較されて、検査フィンガープリントについて可能性のある全ての候補参照フィンガープリントが識別されるまで、インデックス１２０の各々に対して処理が反復される。この方法の終了時に、複数の参照フィンガープリント１０５がマークされることになる。参照フィンガープリントは、２つ以上のインデックス１２０によって定義された検査フィンガープリント３１０のインデックス化された特徴とマッチングする場合もあるので、参照フィンガープリント１０５は、候補として複数回マークすることができる。次いで、ブロック４２５に示すように、全ての参照フィンガープリント候補がグループ化される。
【００２１】
上述のステップでは、参照フィンガープリントの実際のコピーを取得する必要もなく、候補参照フィンガープリントがインデックスによって識別される。しかしながら、候補フィンガープリントが識別されると、候補参照フィンガープリントのコピーが取得され、これによって、マッチングアルゴリズムは、各識別された候補フィンガープリントを検査フィンガープリントと比較し、マッチングが存在するかどうかを判定することができる。候補フィンガープリントのコピーを参照データベースから取得するステップは、候補参照フィンガープリントが配置されたデータベース内のパーティションへの「アクセス」を含むことができ、これは読み出し動作であるので、従って、参照データベースのリソースに対するロードである。
【００２２】
図６は、データ構造１１０内の参照フィンガープリントの候補セット５００が識別された実施例に関するデータ構造１１０を示す。図６の実施例では、４つのパーティション２００が図示されており、これらの４つのパーティション２００は、識別された候補フィンガープリントを合計で２００個含む。左から右に図示するように、第１のパーティション２００は候補セットの参照フィンガープリントを１００個含み、第２のパーティション２００は参照フィンガープリントを１７個含み、第３のパーティション２００は１個の参照フィンガープリントを含み、第４のパーティション２００は参照フィンガープリントを８２個含む。
【００２３】
候補セット５００内の参照フィンガープリントのうちのいずれかが検査フィンガープリント３１０とマッチングするかどうかを識別するために、フィンガープリントマッチングアルゴリズムは、検査フィンガープリント３１０と候補セット５００の参照フィンガープリントのうちの各々の参照フィンガープリントとの間でビット毎の比較を実行することができる。このビット毎の比較は、図５Ａに示した比較段階４０５中に実行することができる。この比較を行うために、フィンガープリントマッチングシステムは、最初に、各パーティション２００から候補参照フィンガープリントのコピーを取得する。この読み出し動作は、パーティション２００の各々において同時に実行することができるが、しかしながら、比較段階の全体の速度は、最も低速のパーティション２００からの読み出し速度によって制限され、最も低速のパーティション２００は、最大数の候補フィンガープリントを保有するパーティション２００である可能性が高い。この実施例では、より多くの識別候補フィンガープリントを含むパーティションは、より少数の識別候補アルゴリズムを含むパーティションよりもマッチングアルゴリズムにフィンガープリントを提供するのにより多くの時間を要する可能性が高い。なぜなら、この実施例では、候補のフィンガープリント数は均等に平衡化されておらず、全体の比較速度が最適以下となるためである。参照フィンガープリントの候補セット５００がパーティション２００にわたってより均等に分散されている場合には、比較段階はより迅速に進むことになる。このケースにおいて、候補セットの２００個のフィンガープリントがより均等に分散されている場合には、各パーティションは候補セットに約５０個のフィンガープリントを有することになり、マッチングの全体速度を大幅に迅速にすることができる。
【００２４】
図７は、本発明によるデータベース内の検索負荷を平衡化するためのコンピュータに実装された方法のフロー図を示す。ブロック６００に示すように、各パーティション２００についてアクセスレートが監視される。アクセスレートは、フィンガープリントの候補セット５００に含まれる当該パーティションに関する参照フィンガープリントの平均個数として求められ、複数の検査フィンガープリント３１０を比較する間に測定される。アクセスレートは、限定ではないが、月当たり、週当たり、１日当たり、１時間当たり、分単位、又は秒単位を含む、複数の時間期間にわたって測定することができる。
【００２５】
ブロック６１０に示すように、データベース内のパーティションに対するアクセスレートを監視する間、データベースサーバ１２５は、データベース１００に新たな参照フィンガープリントを追加するためのリクエストを受信することができる。このリクエストは、図１に示すような既知の放送局１４０のサンプリングの結果とすることができる。次いで、ブロック６２０に示すように、新たな参照フィンガープリントは、他のパーティション２００と比べて相対的に低いアクセスレートを有する少なくとも一つのパーティション２００上に保存される。
【００２６】
より低いアクセスレートを有するパーティション上に新たな参照フィンガープリントを継続的に保存することによって、パーティションにわたるアクセスレートがほとんどの検索に対するアクセスレートをほぼそのまま維持されるように改善され、その結果、平均検索速度を向上させることができる。また、参照フィンガープリントは、パーティションのアクセスレートの負荷平衡を行うように動的に再分配することもできる。
【００２７】
データベースはまた、より低いアクセスレートを有するパーティション上に新たな参照フィンガープリントの保存のみを行うのではなく、より高いアクセスレートを有するパーティションからより低いアクセスレートを有するパーティションに参照フィンガープリントを転送することによって、周期的に再平衡化することができる。この再平衡化は、継続的に、或いは指定されたスケジュールのメンテナンス時に実行することができる。
【００２８】
更に、参照フィンガープリントは、グループ内のパーティション上に保存することができ、参照フィンガープリントに対する最適位置の決定は、各参照フィンガープリントに対して個々に行われるのではなく、グループレベルで行われる。例えば、参照フィンガープリントが放送番組の特定のエピソードに対して生成されるときには、そのエピソードに対する参照フィンガープリントの全てを最も低いアクセスレートを有するパーティション上に保存することができる。その後、次のエピソードが放送されるときにだけ、その１つのコンテンツに対して新たに作成された参照フィンガープリントを相対的に低いアクセスレートを有する該当エピソードのためのパーティションのグループに保存することができる。或いは、参照フィンガープリントの指定個数又はデータサイズを一緒にグループ化し、データベース内でグループが保存されることになる場所に配置することができる。
【００２９】
１つの実施形態では、データベースが大きくなるにつれて、既存のパーティションのサイズを単に増やすのではなく、パーティションのグループにパーティションを追加することが望ましい場合がある。パーティションが追加される際に、データベースシステム内に新たなパーティションを実装する１つの方法は、既存のパーティションのうちの１又はそれ以上のパーティションから新たなパーティションに参照フィンガープリントを転送することである。このようにすることで、新たなパーティションのアクセスレートは、既存のパーティションの平均アクセスレートとほぼ同じか又はそれ未満であると予想することができる。
【００３０】
本発明の実施形態に関する上述の説明は、例示を目的として提示されたものであり、開示された厳密な形態のみを包含すること、又はその形態に限定することを意図するものではない。関連技術における当業者は、上記開示事項に照らして多くの修正及び変形形態が可能であることは理解することができる。
【００３１】
この説明の一部は、アルゴリズム及び情報に関する動作の象徴的表現に関する本発明の実施形態を記載している。これらのアルゴリズム記述及び表現は、これらの作業内容を他の当業者に効率的に伝えるためにデータ処理技術の当業者により一般的に使用されている。これらの動作は、機能的、計算的、又は論理的に説明されているが、コンピュータプログラム又は同等の電気回路、マイクロコード等によって実施されることは理解される。更にまた、一般性を失わずに、モジュールとしてこれらの動作の構成を指すのに好都合であることが分かっている。記載された動作及び関連するモジュールは、ソフトウェア、ファームウェア、ハードウェア又はこれらのいずれかの組み合わせで具現化することができる。
【００３２】
本明細書に記載のステップ、動作又は処理のうちのいずれかは、１又はそれ以上のハードウェア又はソフトウェアモジュールによって単独で又は他の装置と組み合わせて実行又は実装することができる。１つの実施形態では、ソフトウェアモジュールは、コンピュータプログラムコードを含むコンピュータ読み取り可能媒体を備えたコンピュータプログラム製品で実施され、コンピュータプログラムコードは、記載されるステップ、動作又は処理のうちのいずれか、或いは全てを実行するためのコンピュータプロセッサによって実行することができる。
【００３３】
本発明の実施形態はまた、本明細書の動作を実行するための装置に関するものであってもよい。この装置は、所要の目的のために特別に構成することができ、及び／又は、コンピュータ内に保存されたコンピュータプログラムによって選択的に作動又は再構成される汎用コンピュータデバイスを備えることができる。このようなコンピュータプログラムは、有形のコンピュータ読み取り可能記憶媒体、又はいずれかの種類の電子的な命令の保存に好適な媒体に保存され、コンピュータシステムバスに結合することができる。更に、明細書において言及されたいずれかの計算システムは、単一プロセッサを含むことができ、或いは、高い計算能力のためにマルチプロセッサ設計を採用するアーキテクチャとすることができる。
【００３４】
本発明の実施形態はまた、搬送波に組み込まれたコンピュータデータ信号に関するものであってもよく、ここでコンピュータデータ信号は、コンピュータプログラム製品又は本明細書に記載の他のデータの組み合わせのいずれかの実施形態を含む。コンピュータデータ信号は、有形の媒体又は搬送波内に提示されて搬送波内で変調又は符号化される製品であり、当該搬送波は有形であり、いずれかの好適な送信方法に従って送信される。
【００３５】
最後に、本明細書で使用される用語は、主に可読性及び指示を目的として選択されたものであり、本発明の主題を正確に説明するため、又は制限するために選択されたものではない。そのため、本発明の範囲は、この詳細な説明によって限定されるものではなく、むしろ、本明細書に基づく応用に由来する請求項のいずれかによって限定されるものとする。従って、本発明の実施形態の開示は、限定ではないが、以下の請求項に記載された本発明の範囲を例証するものとする。
【符号の説明】
【００３６】
１００  参照フィンガープリントのデータベース
１２５  データベースサーバ
１３０  放送局
１３５  コンピュータネットワーク
１４０  放送番組
【図１】
2012529704.tif 000003
【図２】
2012529704.tif 000004
【図３】
2012529704.tif 000005
【図４】
2012529704.tif 000006
【図５Ａ】
2012529704.tif 000007
【図５Ｂ】
2012529704.tif 000008
【図６】
2012529704.tif 000009
【図７】
2012529704.tif 000010
【国際調査報告】
2012529704.tif 000011