(57)【要約】【課題】ベクトル量子化の混合に基づく符号化方法及びこれを用いた最近傍探索（ＮＮＳ）方法を提供する。【解決手段】本発明は、候補データセットからクエリの最近傍を検索するための候補ベクトルの符号化方法において、入力ベクトル（この時、最初の入力ベクトルは前記候補ベクトル）を正規化して方向ベクトル及びベクトルエネルギーを取得する正規化段階、前記方向ベクトルを量子化してコードワード及び残差ベクトルを取得する量子化段階、前記残差ベクトルを前記入力ベクトルとして、前記正規化段階及び前記量子化段階を予め設定された符号化次数だけ反復する段階、前記反復による一つ以上のコードワード及び一つ以上のベクトルのエネルギーを用いて前記候補ベクトルを符号化する段階を含むことを特徴とする。本発明によれば、エネルギー値の範囲が非常に大きいデータセットを効果的に近似し、より高い精密度を得ることができる。【選択図】図１
2020515986.tif 000002
【特許請求の範囲】
【請求項１】
候補データセットからクエリの最近傍を検索するための候補ベクトルの符号化方法であって、
入力ベクトル（この時、最初の入力ベクトルは前記候補ベクトル）を正規化して方向ベクトル及びベクトルエネルギーを取得する正規化段階と、
前記方向ベクトルを量子化してコードワード及び残差ベクトルを取得する量子化段階と、
前記残差ベクトルを前記入力ベクトルとして、前記正規化段階及び前記量子化段階を予め設定された符号化次数だけ反復する段階と、
前記反復による一つ以上のコードワード及び一つ以上のベクトルのエネルギーを用いて前記候補ベクトルを符号化する段階と、
を含むベクトル符号化方法。
【請求項２】
前記量子化段階は、前記方向ベクトルの次数に対応するコードブックで前記方向ベクトルに最近接したワードを前記コードワードとして返還する段階を含む、請求項１に記載のベクトル符号化方法。
【請求項３】
前記符号化する段階は、
前記符号化次数を予め設定された基準によって低次数と高次数とに分類する段階と、
前記低次数の入力ベクトルに対応するコードワードを用いて逆リストのインデクシングキーを生成する段階と、
前記高次数の入力ベクトルに対応するコードワード及び低次数の入力ベクトルに対応するベクトルエネルギーを用いてＲＮＱコードを生成する段階とを含み、
符号化された候補ベクトルは、前記インデクシングキーと前記ＲＮＱコードとの組合せであり、前記符号化次数は、前記低次数と前記高次数との和である、
請求項１に記載のベクトル符号化方法。
【請求項４】
前記ＲＮＱコードは、前記逆リストにおいて前記インデクシングキーに対応する連結リストに保存され、前記連結リストの各項目は、候補ベクトルの識別情報及びＲＮＱコードを含むことを特徴とする、請求項３に記載のベクトル符号化方法。
【請求項５】
前記符号化次数を分類する段階は、前記候補データセットのサイズが大きくなるほど、前記低次数に分類される値のサイズを増加させる段階をさらに含む、請求項３に記載のベクトル符号化方法。
【請求項６】
前記符号化次数を４、前記低次数ｉを２、前記高次数ｊを２に設定した場合、前記候補ベクトルは下記の式のように近似化され、
【数１】
2020515986.tif 000075
前記インデクシングキーは、前記
【数２】
2020515986.tif 000076
に対応するＣ１及び前記
【数３】
2020515986.tif 000077
に対応するＣ２を用いて次のように生成され、
インデクシングキー：Ｃ１Ｃ２
前記ＲＮＱコードは、前記ｅ０に対応するｈ０及び前記ｅ１に対応するｈ１及び前記
【数４】
2020515986.tif 000078
に対応するＣ３及び前記
【数５】
2020515986.tif 000079
に対応するＣ４を用いて次のように生成される、請求項３に記載のベクトル符号化方法。
ＲＮＱコード：Ｃ３ｈ０Ｃ４ｈ１
【数６】
2020515986.tif 000080
：第１次コードブック（Ｖ１）で残差ベクトルの方向ベクトルとの最近接コードワード
【数７】
2020515986.tif 000081
：第２次コードブック（Ｖ２）で残差ベクトルの方向ベクトルとの最近接コードワード
【数８】
2020515986.tif 000082
：第３次コードブック（Ｖ３）で残差ベクトルの方向ベクトルとの最近接コードワード
【数９】
2020515986.tif 000083
：第４次コードブック（Ｖ４）で残差ベクトルの方向ベクトルとの最近接コードワード
ｅ０：第３残差ベクトルのエネルギー（スカラー値）
ｅ１：第４残差ベクトルのエネルギー（スカラー値）
ｐ１：
【数１０】
2020515986.tif 000084
残差方向ベクトルの投影
ｐ２：
【数１１】
2020515986.tif 000085
残差方向ベクトルの投影
【請求項７】
請求項１〜６のいずれかに記載の方法を実行させるためにコンピュータ読取り可能媒体に格納されたベクトル符号化応用プログラム。
【請求項８】
候補データセットからクエリの最近傍を検索する方法であって、
前記クエリを正規化及び量子化して取得した一つ以上のコードワードを含む逆リストのインデクシングキーと前記クエリ間の距離を計算する段階と、
前記計算された距離を昇順に整列し、整列された距離が上位の特定百分位数以内である逆リストを候補連結リストに設定する段階と、
前記候補連結リストに含まれた候補ベクトルと前記クエリ間の距離を計算して前記最近傍を取得する段階と、
を含む最近傍探索方法。
【請求項９】
前記距離を計算する段階は、
１次コードブックに含まれる第１コードワード
【数１２】
2020515986.tif 000086
及び２次コードブックに含まれる第２コードワード
【数１３】
2020515986.tif 000087
の合成ベクトル
【数１４】
2020515986.tif 000088
と前記クエリｑ間の距離ｄを計算する段階を含む、請求項８に記載の最近傍探索方法。
【請求項１０】
前記距離を計算する段階は、前記距離ｄの計算が次の式によってなされることを特徴とする、請求項９に記載の最近傍探索方法。
【数１５】
2020515986.tif 000089
【請求項１１】
前記距離を計算する段階は、
前記クエリと第１コードワード間の距離を計算して昇順に整列する段階と、
前記クエリと第２コードワード間の距離を計算して昇順に整列する段階と、
前記整列された距離が上位の特定百分位数以内である第１コードワード及び第２コードワードを用いて前記合成ベクトルＩとクエリｑ間の距離を計算する段階と、
を含む、請求項１０に記載の最近傍探索方法。
【請求項１２】
前記最近傍を取得する段階は、前記候補ベクトルｖと前記クエリｑ間の距離を下記の式を用いて計算する段階を含む、請求項８に記載の最近傍探索方法。
【数１６】
2020515986.tif 000090
【請求項１３】
請求項８〜１２のいずれかに記載の方法を実行させるためにコンピュータ読取り可能媒体に格納された最近傍探索応用プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報検索、マルチメディア検索に関し、より詳細には、ベクトル量子化の混合に基づく符号化方法及びこれを用いた最近傍探索（ＮＮＳ）方法に関する。
【背景技術】
【０００２】
最近傍探索（ＮＮＳ）方法は、多くのコンピュータ分野で重点的に研究されている方法であり、これは、データベース、機械学習、コンピュータ起動、及び情報検索のような広範囲な分野で基礎的な役割を果たす。最近傍探索（ＮＮＳ）問題は、次のように簡単に定義することができる。クエリｑ∈ＲＤ及びクエリと同じ次元の候補ベクトルｎ個が与えられた時、最近傍探索（ＮＮＳ）問題は特定メトリック（一般に、ｌ１−距離、又はｌ２−距離）によって空間的に最も近いクエリに対するサンプルを返さなければならない。
【０００３】
最近傍は、全候補セットを線形スキャン（探索）することによって識別することができるが、線形探索の時間複雑度はＯ（ｎ・Ｄ）である。線形探索の時間複雑度は次元及びデータセットの規模のいずれにも線形的に増加するが、次元及びデータの両方とも増加する場合、時間複雑度は実際に２次的に増加する。したがって、実時間検索は高次元、大規模、高密度ベクトル空間ではほぼ不可能である。このような場合、Ｋ−Ｄツリー、Ｒ−ツリー、及びＬＳＨ（Ｌｏｃａｌｉｔｙ  Ｓｅｎｓｉｔｉｖｅ  Ｈａｓｈｉｎｇ）などの大部分の伝統的な方法では満足すべき結果が得られない。
【０００４】
ここ数年でベクトル量子化に基づく方法が、簡単な計算、遥かに低い空間複雑度、及び高次元データにおける良好な結果によって益々大衆化しつつある。代表的な方法には、積量子化器（Ｐｒｏｄｕｃｔ  Ｑｕａｎｔｉｚｅｒ；ＰＱ）、加算量子化器（Ａｄｄｉｔｉｖｅ  Ｑｕａｎｔｉｚｅｒ；ＡＱ）、及び結合量子化器（Ｃｏｍｂｉｎｅｄ  Ｑｕａｎｔｉｚｅｒ；ＣＱ）がある。
【０００５】
ＰＱは高次元ベクトルを複数のセグメントに分解する。各セグメント（サブ−ベクトル）は該当のサブ−空間で訓練された量子化器によって量子化される。最後に、原ベクトルはそれらのサブ−空間量子化器から一連の最近接コードワードの連結によって近似化される。クエリと候補ベクトルとの間の距離は、クエリとサブ−空間における最近接コードワードとの間の距離によって近似化される。
【０００６】
ＰＱとは違い、ＡＱ及びＣＱはベクトルをセグメントに分けない。両方とも同一次元にある複数の要素ベクトルの和でベクトルを示す。このような要素ベクトルは、一連の事前訓練されたコードブックの中から選択される（最大で一つのベクトルが一つのコードブックから選択される。）
【０００７】
ＰＱと類似に、クエリと候補ベクトルとの間の距離は、クエリと選択された要素ベクトルとの間の距離の和によって近似化され、これは、ルックアップテーブルを確認して効率的に計算することができる。
【０００８】
量子化接近法には２つの長所がある。一つは、候補ベクトルが圧縮（一般的にメモリー消費が１桁だけ減少）されて迅速な検索を支援するために全参照セットをメモリーにロードできるという点である。もう一つは、クエリと全候補との間の距離の計算は、クエリとコードブックコードワードとの間の距離の計算によって近似化されるときに非常に効率的であるという点である。
【０００９】
しかし、このような量子化に基づく方法においてはインデクシングされるべきデータに暗示的仮定が与えられなければならない。計算費用の問題のためごく限られた数のコードワードしか量子化に使用されず、量子化は、広いエネルギースペクトルにわたっている全てのベクトルの正確な近似値を求めることができない。
【００１０】
例えば、与えられたベクトル［０．１，０．０３，−−−］１×１２８及び［５５，１２２，−−−］１×１２８のベクトル長は非常に異なる。大きいエネルギー差のため、既存の方法では上のいずれか一方のベクトルしか近似できず、他方のベクトルは近似できなくなる。結果的に、ＡＱ、ＣＱ及びＰＱに対して、エネルギー分布が広い範囲にわたっている一般的な場合には、低い近似誤差を達成することがほぼ困難である。しかも、ＡＱ、ＣＱ及びＰＱのような現在の圧縮方式は、ベクトル符号化イシューだけを言及している。これら方法のいずれか一つで最近傍探索（ＮＮＳ）を行うとき、クエリと符号化された候補との比較は不回避であり、このような方法を大規模の検索作業に拡張することは難しい。
【発明の概要】
【発明が解決しようとする課題】
【００１１】
本発明は、前述した問題を解決するためのものであり、エネルギー値の範囲が非常に大きいデータセットを効果的に近似し、より高い精密度が得られる符号化方法を提供することを目的とする。
【００１２】
また、本発明は、逆リストのインデックスを構築できる符号化方法を提供することを他の目的とする。
【００１３】
また、本発明は、ベクトル量子化のための符号化訓練及び量子化過程を簡素化し、高い符号化正確性が得られる符号化方法を提供することを他の目的とする。
【００１４】
また、本発明は、クエリと候補ベクトルとの距離の計算を簡素化し、検索速度を改善できる最近傍探索方法を提供することをさらに他の目的とする。
【課題を解決するための手段】
【００１５】
このような目的を達成するための本発明は、候補データセットからクエリの最近傍を検索するための候補ベクトルの符号化方法であって、入力ベクトル（この時、最初の入力ベクトルは前記候補ベクトル）を正規化して方向ベクトル及びベクトルエネルギーを取得する正規化段階、前記方向ベクトルを量子化してコードワード及び残差ベクトルを取得する量子化段階、前記残差ベクトルを前記入力ベクトルとして、前記正規化段階及び前記量子化段階を、予め設定された符号化次数だけ反復する段階、及び前記反復による一つ以上のコードワード及び一つ以上のベクトルのエネルギーを用いて前記候補ベクトルを符号化する段階を含むことを特徴とする。
【００１６】
また、本発明は、候補データセットからクエリの最近傍を検索する方法であって、前記クエリを正規化及び量子化して取得した一つ以上のコードワードを含む逆リストのインデクシングキーと前記クエリ間の距離を計算する段階、前記計算された距離を昇順に整列し、整列された距離が上位の特定百分位数以内である逆リストを候補連結リストに設定する段階、及び前記候補連結リストに含まれた候補ベクトルと前記クエリ間の距離を計算して前記最近傍を取得する段階を含むことを特徴とする。
【発明の効果】
【００１７】
前述したような本発明によれば、エネルギー値の範囲が非常に大きいデータセットを効果的に近似し、より高い精密度を得ることができる。
【００１８】
また、本発明によれば、逆リストのインデックスを構築することができる。
【００１９】
また、本発明によれば、ベクトル量子化のための符号化訓練及び量子化過程を簡素化し、高い符号化正確性を得ることができる。
【００２０】
また、本発明によれば、クエリと候補ベクトルとの距離の計算を簡素化し、検索速度を改善することができる。
【図面の簡単な説明】
【００２１】
【図１】本発明の一実施例による最近傍探索方法を概略的に説明するための順序図である。
【図２】本発明の一実施例による正規化ベクトル量子化を説明するための図である。
【図３】本発明の一実施例による再帰的近似化を説明するための図である。
【図４】本発明の一実施例によるベクトル量子化の混合に基づく符号化結果をＨＫＭと比較するための図である。
【図５】ベクトル量子化の混合に基づくベクトル符号化方法を説明するための順序図である。
【図６】本発明の一実施例によるベクトル符号化方法を説明するための図である。
【図７】ＳＩＦＴ１Ｍ及びＧＩＳＴ１Ｍデータセットにおいて本発明の一実施例によるベクトル量子化の混合に基づく符号化による結果をＩＶＦＰＱ、ＩＶＦＲＶＱ、ＩＭＩの結果と対比するための図である。
【図８】本発明の一実施例によるベクトル量子化の混合に基づく符号化を用いた最近傍探索方法を説明するための順序図である。
【発明を実施するための形態】
【００２２】
前述した目的、特徴及び長所が添付図面を参照して詳細に後述され、これに基づいて、本発明の属する技術分野における通常の知識を有する者にとって本発明の技術的思想が容易に実施可能であろう。本発明の説明において、本発明に関連している公知技術の具体的な説明が本発明の要旨を余分に曖昧にし得ると判断される場合には詳細な説明を省略する。
【００２３】
図面中、同一の参照符号は同一又は類似の構成要素を表し、明細書及び特許請求の範囲に記載された全ての組み合わせは、任意の方式で組み合わせることができる。そして、特に規定しない限り、単数と記載したものは一つ以上を含むことができ、単数表現に対する言及は複数表現をも含み得ると理解されるべきである。
【００２４】
前述した問題を解決するために、本発明は、残差ベクトル量子化（Ｒｅｓｉｄｕａｌ  Ｖｅｃｔｏｒ  Ｑｕａｎｔｉｚａｔｉｏｎ；ＲＶＱ）に基づく方法を提案している。本発明は、２つの側面、符号化及びインデクシング段階の両方において最近傍探索（ＮＮＳ）の問題を解決することを目的とする。
【００２５】
ＲＶＱは、前段階のベクトル量子化から得た残差ベクトルを再帰量子化して原ベクトルに接近する方法である。試験結果によれば、簡単な訓練で簡単なＲＶＱを行う場合にも、複雑な訓練が要求されるＡＱ、ＣＱ及びＳＱと略同一の結果が得られるという事実がわかった。
【００２６】
また、本発明は従来のＲＶＱを改善して、ベクトルのエネルギーが広い範囲にわたってインデクシングされた場合にも適用可能である。
【００２７】
本発明の一実施例による再帰正規化されたベクトル量子化（Ｒｅｃｕｒｓｉｖｅ  Ｎｏｒｍａｌｉｚｅｄ  Ｖｅｃｔｏｒ  Ｑｕａｎｔｉｚａｔｉｏｎ；以下、‘ＲＮＱ’という。）方法は、ベクトルと残差ベクトルを量子化する前に正規化を行い、ベクトルの方向及びエネルギーを得た後に、ベクトルの方向及びエネルギーをそれぞれ量子化（符号化）する。
【００２８】
本発明に係る速い最近傍探索（ＮＮＳ）方法は、ＲＶＱ及びＲＮＱを混合した符号化方式を利用している。具体的に、相対的に低い次数の残差ベクトルはＲＶＱによって符号化される。残りの相対的に高い次数の残差ベクトルはＲＮＱで符号化される。このデザインは、ＲＶＱの低い次数の符号化効率性及びＲＮＱの低い符号化誤差という両方の長所を有する。オンライン検索において低い次数のＲＶＱコードは逆リスト（ｉｎｖｅｒｔｅｄ  ｌｉｓｔ）のインデクシングキーとして結合される。
【００２９】
本発明は、区別されるインデクシングキー値を生成して最近傍探索（ＮＮＳ）の速度を上げるためにＲＶＱコードブック設定（符号化設定）に対する包括的な研究を行った結果に関する。
【００３０】
各次数のコードブックサイズを慎重に構成すると符号化誤りが非常に減少する。本発明は、精巧な加重値体系よりも重要である。本発明の内容と関連して、我々は小さいコードブックの多重次数（ｍｕｌｔｉｐｌｅ  ｏｒｄｅｒｓ）から反転されたキー（ｉｎｖｅｒｔｅｄ  ｋｅｙ）を作ることが、大きいコードブックの単一次数（ｓｉｎｇｌｅ  ｏｒｄｅｒ）からキーを作ることに比べてより有利であることを発見した。前者は顕著に低い量子化費用と符号化誤差につながるためである。また、このような多次元キー生成方式（ｍｕｌｔｉ−ｏｒｄｅｒ  ｋｅｙ  ｇｅｎｅｒａｔｉｏｎ  ｓｃｈｅｍｅ）を用いて兆（ｔｒｉｌｌｉｏｎ）単位レベルの検索作業に拡張することが非常に便利であることが明らかになった。
【００３１】
ツリー分割接近法の主な短所は、多いメモリーを要求するという点である。一方では、速い比較を支援するために全候補ベクトルがメモリーにロードされるが、他方では、インデクシングに用いられるツリーノードが相当な量の追加メモリーを占める。全般的にメモリー消費が参照セットのサイズよりも大きい。
【００３２】
ツリー分割接近法とは別に、最近傍探索（ＮＮＳ）に局所性鋭敏型ハッシュ（ＬＳＨ）を適用しようとするいくつかの試みがあった。一般に、検索段階には２つの段階がある。段階１は、クエリと同一又は類似のハッシュキーを共有する候補を収集し、段階２は、最近傍を探すためにクエリと全ての選択された候補とをいちいち比較する。局所性鋭敏型ハッシュ（ＬＳＨ）は、大量の最近傍を要求するアプリケーションに適する。また、段階２において速い比較を支援するために全参照セットをメモリーにロードしなければならず、多くのメモリーが消費される。
【００３３】
ここ数年、ＮＮＳの問題はベクトル量子化によって扱われた。積量子化器を適用する技術は、数十年間解けずにいた問題を解決する新しい方法を提示した。
【００３４】
本発明に係るクエリの最近傍探索は、大略的に、図１に示すように、候補ベクトルをベクトル量子化（ＲＶＱ及びＲＮＱ）の混合に基づく符号化によって圧縮し（Ｓ１０）、圧縮された候補ベクトルを用いてクエリの最近傍を検索（Ｓ２０）することを含むことができる。また、段階２０において、圧縮された候補ベクトルとクエリとの間の距離はコードワードとクエリとの間の距離によって近似化され得る。
【００３５】
以下では、図２〜図７を参照して、本発明の一実施例による段階１０におけるベクトル量子化の混合に基づく符号化について説明し、これを用いた最近傍探索方法について、図８を参照してより詳しく説明する。
【００３６】
ベクトル量子化の混合に基づく符号化を説明するために、本明細書では、まず、残差ベクトル量子化（ＲＶＱ）を検討し、次に、残差ベクトルが各段階で量子化される前に正規化されるＲＶＱの変形（ＲＮＱ）を提示する。さらに、圧縮されないクエリとＲＶＱ及びＲＮＱで圧縮された候補ベクトル間の距離の計算方法が提示される。
【００３７】
Ａ．残差ベクトル量子化（ＲＶＱ）
複数のベクトルの合成によってベクトルを近似化するアイデアは、“２段階残差ベクトル量子化”の設計に遡ることができる。この方法において、入力ベクトルは量子化器によって符号化され、それの残差（量子誤差）は他の量子化器によって順次に符号化される。この手法は、以前の量子化段階で残された残差ベクトルが再帰的に量子化される複数の次数（段階）に拡張された。
【００３８】
候補ベクトル（以下、ベクトルという。）をｖ∈ＲＤ、一連のコードブックをＶ１，Ｖ２，．．．Ｖｋとすれば、ベクトルｖはこのようなコードブックのコードワード構成によって近似化される。特に、１コードワードは１段階のコードブックの中から選択される。この再帰的量子化がｋ番目の段階まで反復されると、ベクトルｖは次の式１のように近似化される。
【００３９】
【数１】
2020515986.tif 000003
【００４０】
式１において、段階ｍにおけるＶｍは、ｍ−１段階で収集された残差
【数２】
2020515986.tif 000004
で訓練されたものである。
【００４１】
いくつかの手法がＲＶＱの量子化誤差を減少させるために提案された。Ｃ．Ｆ．Ｂａｒｎｅｓ，Ｓ．Ａ．Ｒｉｚｖｉ，ａｎｄ  Ｎ．Ｍ．Ｎａｓｒａｂａｄｉ，“Ａｄｖａｎｃｅｓ  ｉｎ  ｒｅｓｉｄｕａｌ  ｖｅｃｔｏｒ  ｑｕａｎｔｉｚａｔｉｏｎ：ａ  ｒｅｖｉｅｗ．，”ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｉｍａｇｅ  Ｐｒｏｃｅｓｓｉｎｇ，ｖｏｌ．５，ｎｏ．２，ｐｐ．２２６２６２，１９９６．と特定される文献（以下、先行文献１）、及びＷ．−Ｙ．Ｃｈａｎ  ａｎｄ  Ａ．Ｇｅｒｓｈｏ，“Ｅｎｈａｎｃｅｄ  ｍｕｌｔｉｓｔａｇｅ  ｖｅｃｔｏｒ  ｑｕａｎｔｉｚａｔｉｏｎ  ｗｉｔｈ  ｃｏｎｓｔｒａｉｎｅｄ  ｓｔｏｒａｇｅ，”  ｉｎ  Ｔｗｅｎｔｙ−Ｆｏｕｒｔｈ  Ａｓｉｌｏｍａｒ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｓｉｇｎａｌｓ，Ｓｙｓｔｅｍ  ａｎｄ  Ｃｏｍｐｕｔｉｎｇ，ｐｐ．６５９６６３，Ｎｏｖ．１９９０．と特定される文献（以下、先行文献２）によれば、多重段階のコードブックはこれらを共同で訓練することによって最適化された。
【００４２】
本発明の一実施例において、我々はＲＶＱの単純実施だけを考慮し、各段階におけるコードブックは、以前段階で収集した残差から独立して訓練されたものである。先行文献１及び先行文献２で提案された共同最適化は、性能をより強化させることができる。
【００４３】
単純であるが、ＲＶＱはＡＱ及びＣＱのような最近の構成的圧縮接近法に比べて長所がある。ＲＶＱの方法では、ベクトルのエネルギーは個別の量子化器に無作為に分配される。ＡＱ、ＣＱ又はＰＱとは違い、ＲＶＱは、低い段階の量子化器においてより多い原ベクトルのエネルギーを維持する。
【００４４】
ＲＶＱは実際に原ベクトルに対して粗密（ｃｏａｒｓｅ−ｔｏ−ｆｉｎｅ）圧縮を形成する。言い換えると、相対的に低い段階のコードは相対的に高い段階のコードよりも多い情報を伝達する。結果的に、下位段階のコードは逆ファイル（ｉｎｖｅｒｔｅｄ  ｆｉｌｅｓ）を生成するインデクシングキーとして使用するのに特に適合するので、速いＡＮＮ検索を可能にする。
【００４５】
一方、これらのコードは、他の逆リストにベクトルがバラバラに分布するように空間を最大限に分割することができる。他方では、インデクシングキーの長さは最小限に抑えられ、逆ファイル構造の規模を可能な限り小さくさせる。
【００４６】
Ｂ．再帰的正規化ベクトル量子化（ＲＮＱ）
一つの量子化段階で使用可能なコードワードの数が制限されているため、各段階における残余空間が正しく量子化されないことがある。これは残差のエネルギーが広い範囲にわたっている時に特にそうである。この問題を解決するために、本発明の一実施例によれば、量子化に提供する前に残差ベクトルをｌ２−正規化することが好ましい。言い換えると、ベクトルのエネルギーとその単位長ベクトルは別々に量子化されるので、量子化が容易となる。
【００４７】
ベクトルｖ∈ＲＤとすれば、
【数３】
2020515986.tif 000005
であり、
【数４】
2020515986.tif 000006
はベクトルのエネルギーを維持する。ＡＱ、ＰＱ、及びＣＱとは違い、ベクトルのエネルギーｅ０と正規化されたベクトル（すなわち、方向ベクトル）
【数５】
2020515986.tif 000007
は個別に符号化されるだろう。ｅがスカラー値であるので、ｅは、符号化及びインデクシングが容易である。
【００４８】
以下では単位長ベクトル
【数６】
2020515986.tif 000008
をどのように符号化するかについて重点的に説明する。
【００４９】
既に訓練されたコードブック
【数７】
2020515986.tif 000009
であり、
【数８】
2020515986.tif 000010
である。量子化関数Ｑ（ｘ，Ｖ）は、ベクトルｘのためのコードブックＶから最近傍を返還する。したがって、ベクトルｕは次の式２のように表される。
【００５０】
【数９】
2020515986.tif 000011
【００５１】
【数１０】
2020515986.tif 000012
であり、
【数１１】
2020515986.tif 000013
がベクトルＱ（ｕ０，Ｖ１）に直交（ｏｒｔｈｏｇｏｎａｌ）する残差ベクトルである場合、
【数１２】
2020515986.tif 000014
であることを考慮すれば、上記の式２を式３のように整理することができる。
【００５２】
【数１３】
2020515986.tif 000015
【００５３】
図２は、（ａ）はベクトルｕ０、
【数１４】
2020515986.tif 000016
、
【数１５】
2020515986.tif 000017
及びそれらの関係を２次元空間に示すものである。残差ベクトル
【数１６】
2020515986.tif 000018
は同一の方式でさらに近似化され得る。
【数１７】
2020515986.tif 000019
であることを考慮して、ｅ１が
【数１８】
2020515986.tif 000020
のエネルギーを維持し、ｕ１がｌ２−正規化ベクトルである場合、ｕ１は次の式４のように近似化される。
【００５４】
【数１９】
2020515986.tif 000021
【００５５】
【数２０】
2020515986.tif 000022
が他のコードブックＶ２でｕ１に最近接したコードワードである場合、ｕ０は次の式５のように表される。
【００５６】
【数２１】
2020515986.tif 000023
【００５７】
同様に、符号化プロセスを式６のようにさらに高い次元に拡張させることは非常に自然である。
【００５８】
【数２２】
2020515986.tif 000024
【００５９】
４次数で近似化を止めた場合、次の式７を得ることができた。
【００６０】
【数２３】
2020515986.tif 000025
【００６１】
このベクトルｕ０の近似は
【数２４】
2020515986.tif 000026
と表示される。式７でｐｉとｅｉはベクトルｕｉ−１とコードワードｗｉ間のコサインとサインである。結果的に、それらは結合される。そのいずれか一方が知られると、他方が固定されるという意味であり、これは符号化便宜性を提供する。符号化において装置はｐｉシリーズとｅｉシリーズのいずれか一方でのみスカラー量子化を行えばいい。
【００６２】
式７において、ｐｉとｅｉはいずれも［０，１］の範囲内にあるため、ｍ番目の次数に維持される実際エネルギーは
【数２５】
2020515986.tif 000027
であり、これは、以前次数に維持されたエネルギーよりも大きくない。したがって、ＲＮＱの多重次数（ｍｕｌｔｉｐｌｅ  ｏｒｄｅｒｓ）はベクトル空間に対して粗密（ｃｏａｒｓｅ−ｔｏ−ｆｉｎｅ）分割を形成するＲＶＱに類似している。
【００６３】
図３は、１次数から４次数までの近似を示す図である。原ベクトルｖは
【数２６】
2020515986.tif 000028
と表現される。
【００６４】
全般的に、本発明の一実施例による符号化とＲＶＱとの主な差異点は、本発明がコードブックコードワードに代えて、コードブックコードワードに投影してベクトルを近似化するという点である。
【００６５】
従来の構成接近法と比較すれば、本発明は、エネルギーを符号化するための余分のビットを必要とする。しかし、これは多量のメモリーを消費しない。本発明の一実施例による実験結果によれば、一般に、各次数のエネルギーを符号化するのには４ビットで十分である。
【００６６】
ｎ次量子化器でベクトルを近似化するためにはｎ個のコードブックが必要である。このようなコードブックは、以前段階で正規化された残差を収集して訓練される。
【００６７】
各次数における訓練にはｋ−平均法（ｋ−ｍｅａｎｓ）クラスタリングを用いることができる。ｋ−平均法クラスタリング後にはクラスタリングの中心は単位長にｌ２−正規化され、符号化コードワードとして使用され得る。
【００６８】
前述した新しい符合化方法を再帰的正規化ベクトル量子化（ＲＮＱ）という。
【００６９】
Ｃ．ＲＮＱとＲＶＱとの混合に基づく符号化
ＲＮＱの場合、符号化誤りはＲＶＱに比べて非常に小さいが、各次数に４ビットがさらに必要である。一般に、速いＮＮＳのために、ＲＮＱ／ＲＶＱコードの初めの２つの次数で逆インデクシングキーを生成する。結果的に、逆変換されたキーはＲＶＱよりも８ビット長くなる。インデクシングキーがＲＶＱよりも明確であるが、キースペースキーのボリュームは、ベクトル空間を不要に低い密度に分けるＲＶＱに比べて２５６倍さらに大きい。この理由から、速いＮＮＳにおいて本発明に係る装置は、与えられたベクトルに対する混合符号化を選好する。一般に、ＲＶＱは符号化の初めの２つの次数に用いられ、インデクシングキーを生成するために用いられる。
【００７０】
２次数ＲＶＱで残った残差はＲＮＱでさらに符号化される。結果的に、ベクトルは４次数に近似され、近似値は次の式８の通りである。
【００７１】
【数２７】
2020515986.tif 000029
【００７２】
混合符号化方法は、図５及び図６に示す通りであり、前述したＡ〜Ｃを含むベクトルの符号化方法を、図５を参照して整理すると次の通りである。
【００７３】
まず、入力ベクトル
【数２８】
2020515986.tif 000030
を正規化すれば、スカラー値を有するベクトルエネルギー
【数２９】
2020515986.tif 000031
と方向ベクトル
【数３０】
2020515986.tif 000032
を取得することができる（Ｓ１００）。
【００７４】
次に、方向ベクトルを量子化して（Ｓ２００）、ｍ次コードワードとｍ次残差ベクトルを取得することができる（Ｓ３００）。段階２００は、前述したＢ．再帰的ベクトル量子化において説明した通りである。
【００７５】
例えば、最初に候補ベクトルｖを入力すると、正規化によって方向ベクトルｕ０を取得し、方向ベクトルを量子化してコードワード
【数３１】
2020515986.tif 000033
と残差ベクトル
【数３２】
2020515986.tif 000034
を取得することができる。
【００７６】
量子化関数は方向ベクトルが入力されると、当該方向ベクトルに対応するコードブックに含まれたコードワードのうち、前記方向ベクトルの最近傍（コードワード）を返還する。量子化段階で残される量子誤差を残差ベクトルといい、これは、上述した式２で
【数３３】
2020515986.tif 000035
に該当する。残差ベクトルは量子化関数が返還するコードワードに直交するものであり得る。参考として、本発明では残差ベクトルを複数の次数で再帰的に量子化し、本明細書では反復される全次数を符号化次数と命名し、符号化次数ｎは近似化設定によって変わり得る。
【００７７】
次の段階で、現在次数ｍが符号化次数ｎよりも小さい場合（Ｓ４００）、次数ｍはｍ＋１と１次数増加し、ｍ次残差ベクトルは段階１００〜段階３００で正規化及び量子化過程を経る。したがって、符号化次数ｎだけ段階１００〜段階３００は反復され、本発明の一実施例によるＲＮＱにはｎ個のコードブックが要求され、ＲＮＱによってｎ個のコードワードを取得することができる。
【００７８】
段階６００は、段階１００〜段階３００の反復実行による一つ以上のコードワード及び一つ以上のベクトルのエネルギーを用いて候補ベクトルを符号化することができる。
【００７９】
図６を用いて段階６００についてより詳しく述べる。図６は、インデクシング及び符号化の便宜性を向上させるＲＶＱ及びＲＮＱの混合符号化フレームワークである。説明の明確性のために図６にはそれぞれに対して４個の符号化次数だけを表示した。高いＮＮＳ品質を達成するために、より高い次数に拡張されてもよい。図６でｈｊは一つの次数のエネルギーに対するスカラー量子化値である。
【００８０】
まず、符号化次数の数ｎは、予め設定された基準によって低次数ｉと高次数ｊに分類できる。すなわち、ｎ＝ｉ＋ｊであり、このうち、ｊは具体的な問題によって決定され、検索すべき候補データセットが大きい場合、ｉの値が大きくなり得る。その理由は、低次数ｉが逆インデクシング構造のインデックスに活用されるためであり、ｉの値が大きいほど生成されたインデックス値も多くなり、インデクシング可能なデータ数も大きくなる。これは、可能な限りデータセットを散らして、毎度、最近傍クエリで少数の候補ベクトルだけをアクセスするためである。
【００８１】
次に、低次数の入力ベクトルに対応するコードワードを用いて逆リストのインデクシングキーを生成することができる。例えば、ｎ＝４、ｉ＝２、ｊ＝２である図５の例示において、候補ベクトルは式７のように近似化できるが、低次数は、ｉ＝２であるので、１次、２次を意味し、よって、低次数の入力ベクトルに対応するコードワードは
【数３４】
2020515986.tif 000036
と
【数３５】
2020515986.tif 000037
である。すなわち、インデクシングキーは、
【数３６】
2020515986.tif 000038
と
【数３７】
2020515986.tif 000039
を組み合わせてＣ１Ｃ２に設定することができる。
【００８２】
ここで、
【数３８】
2020515986.tif 000040
は第１次コードブック（Ｖ１）で正規化された候補ベクトルと最近接したコードワードであり、
【数３９】
2020515986.tif 000041
は第２次コードブック（Ｖ２）で残差ベクトルと最近接したコードワードを意味する。
【００８３】
次に、高次数の入力ベクトルに対応するコードワード及び低次数の入力ベクトルに対応するベクトルエネルギーを用いてＲＮＱコードを生成することができる。上記の例示において、ｊ＝２なので、高次数は３次、４次を意味し、よって、ＲＮＱコードの生成にはコードワード
【数４０】
2020515986.tif 000042
と
【数４１】
2020515986.tif 000043
を用いることができる。
【数４２】
2020515986.tif 000044
は第３次コードブック（Ｖ３）で残差ベクトルの方向ベクトルとの最近接コードワード、
【数４３】
2020515986.tif 000045
は第４次コードブック（Ｖ４）で残差ベクトルの方向ベクトルとの最近接コードワードを意味する。また、ベクトルエネルギー値を用いることができるが、ｅ０は候補ベクトルのエネルギー（スカラー値）であって、第３残差ベクトルのエネルギー（スカラー値）でよく、ｅ１は第４残差ベクトルのエネルギー（スカラー値）でよい。
【００８４】
ｐ１とｐ２は、Ｂ．で前述したように、
【数４４】
2020515986.tif 000046
，
【数４５】
2020515986.tif 000047
でよく、これはそれぞれ３次、４次方向ベクトルの最近接コードワードへの投影（ｐｒｏｊｅｃｔｉｏｎ）であり得る。すなわち、ｐ１とｐ２は、
【数４６】
2020515986.tif 000048
と
【数４７】
2020515986.tif 000049
の残差方向ベクトルの投影であり得る。
【００８５】
上述したスカラー量子化値と高次数のベクトル量子化値とを組み合わせてＲＮＱコード（符号化コード）を生成でき、図６の例示によれば、ＲＮＱコードはＣ３ｈ０Ｃ４ｈ１であり得る。
【００８６】
すなわち、候補ベクトルはインデクシングキーと前記ＲＮＱコードとの組合せであるＣ１Ｃ２Ｃ３ｈ０Ｃ４ｈ１と符号化できる。上述したように、Ｃ１、Ｃ２は残差ベクトルを量子化した後のコードであり、この２つのコードは逆リストのインデクシングキー値として合わせられる。残ったコードであるＣ３ｈ０Ｃ４ｈ１は、逆リストの該当のインデクシングキー値に対応する連結リストに保存され、連結リストの各項目には候補ベクトルの識別情報及びＲＮＱコードが保存され得る。例えば、ｎ＝４の上の実施例において、連結リストの各候補項目は＜ＩＤ，Ｃ３ｈ０Ｃ４ｈ１＞であり得る。
【００８７】
図７に示すように、大部分の配置状況においてベクトル量子化混合（ＭＸＱ）のリコール率が最も高く、特にＧＩＳＴＩＭデータセットにおいて他の方法に比べて優れていた。ＩＶＦＲＶＱとＭＸＱの符号化は類似であるが、ＭＸＱの結果はＩＶＦＲＶＱに比べて優れており、これは、残存ベクトルの方向及びエネルギーを個別に符号化することが、ＲＶＱに比べて効果的であるという事実を示している。
【００８８】
ＩＶＦＰＱに対応する方法は、Ｈ．Ｊｅｇｏｕ等が提案した方法である（Ｐｒｏｄｕｃｔ  ｑｕａｎｔｉｚａｔｉｏｎ  ｆｏｒ  ｎｅｉｇｈｂｏｒ  ｓｅａｒｃｈ，ｉｎ：ＩＥＥＥ  ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  ｐａｔｔｅｒｎ  ａｎａｌｙｓｉｓ  ａｎｄ  ｍａｃｈｉｎｅ  ｉｎｔｅｌｌｉｇｅｎｃｅ，２０１１，３３（１）：１１７−１２８）。
【００８９】
ＩＶＦＲＶＱに対応する方法は、Ｙ．Ｃｈｅｎ等が提案した方法である（Ａｐｐｒｏｘｉｍａｔｅ  ｎｅａｒｅｓｔ  ｎｅｉｇｈｂｏｒ  ｓｅａｒｃｈ  ｂｙ  ｒｅｓｉｄｕａｌ  ｖｅｃｔｏｒ  ｑｕａｎｔｉｚａｔｉｏｎ，ｉｎ：Ｓｅｎｓｏｒｓ，ｖｏｌ．１０，ｐｐ．１１２５９−１１２７３，２０１０．）。
【００９０】
ＩＭＩに対応する方法は、Ａ．Ｂａｂｅｎｋｏ等が提案した方法である（Ｔｈｅ  ｉｎｖｅｒｔｅｄ  ｍｕｌｔｉ−ｉｎｄｅｘ，ｉｎ：Ｃｏｍｐｕｔｅｒ  Ｖｉｓｉｏｎ  ａｎｄ  Ｐａｔｔｅｒｎ  Ｒｅｃｏｇｎｉｔｉｏｎ（ＣＶＰＲ）、２０１２  ＩＥＥＥ，２０１２：３０６９−３０７６．）。
【００９１】
最近傍探索方法
図８を参照して、等級剪定に基づくオンライン検索戦略について説明する。候補データセットからクエリｑの最近傍を検索するために、段階１０００において逆リストのインデックスキーとクエリとの間の距離を計算する。このとき、インデックスキー値ＩをＣ１とＣ２とに分割できる。Ｃ１とＣ２は第１次コードブックのベクトル（第１コードワード
【数４８】
2020515986.tif 000050
）及び第２次コードブックのベクトル（第２コードワード
【数４９】
2020515986.tif 000051
）のそれぞれに対応し、クエリｑとＩ間の距離を計算することは、クエリｑ及び合成ベクトル
【数５０】
2020515986.tif 000052
間の距離を計算することに転換することができる。
【００９２】
例えば、ｑと合成ベクトルＩ間の距離は、下記の式のように表現できる。
【００９３】
【数５１】
2020515986.tif 000053
【００９４】
計算速度を上げる段階
上記の式９において、計算速度を上げるために、クエリｑと第１コードワード
【数５２】
2020515986.tif 000054
の距離をまず計算することができる（式９のｔｅｒｍ１）。これによって、クエリｑ及び１次数の各符号化コード間の距離を得ることができ、距離はサイズによって整列され得る。後ろにある９５％の１次符号化コードに対応するインデックス項目は無視してもよく、残り５％の１次符号化コードに対して続けてクエリｑ及び２次符号化コードから得られた合成ベクトルＩとの距離を計算することができる。同様の方法により、クエリｑ及び全ての２次符号化コード間の距離を計算した後、インデックス項目を距離によって整列し、後ろにある９０％のインデックス項目を無視することができる。すなわち、逆リストのうち、上位の特定百分位数以内の連結リストだけを考慮して検索することができる。このような方式は、ｉ＞２の場合へと拡張できる。
【００９５】
式９において、
【数５３】
2020515986.tif 000055
、
【数５４】
2020515986.tif 000056
、
【数５５】
2020515986.tif 000057
は、あらかじめ計算でき、次にリストを照会すれば式９による計算が速く行われ得る。これは、図８の段階２０００において距離を昇順に整列し、整列された距離が既に設定された上位百分位数以内である逆リストを候補連結リストに設定することに対応する。
【００９６】
次に、候補連結リストに含まれた候補ベクトルｖとクエリｑ間の距離を計算して最近傍を取得することができる（Ｓ３０００）。
【００９７】
段階３０００において候補ベクトルｖとクエリｑ間の距離の計算は、下記の式１０によって行うことができ、したがって、ベクトル量子化の混合に基づく符号化方法で符号化された候補ベクトルｖとクエリｑ間の距離を取得することによって、クエリｑの最近傍ベクトルを取得することができる。
【００９８】
【数５６】
2020515986.tif 000058
【００９９】
本発明に係るベクトル量子化混合に基づく符号化方法は、既存の量子化方法と比較すれば、前の２つの次数はＲＶＱ符号化を使用し、後ろ２つの次数は残差ベクトルのエネルギーと方向ベクトルをそれぞれ符号化する。したがって、本発明によれば、逆リストのインデックスを構築可能である他、エネルギー値の範囲が非常に大きいデータセットもより効果的に近似することができ、より高い精密度を得ることができる。
【０１００】
また、本発明の等級剪定による最近傍探索戦略によれば、クエリポイントと距離計算が必要な候補項目の数が効果的に減少し、検索過程を加速化することができる。
【０１０１】
本発明は、既存の他の量子化方法と比較した時、当該方法の符号化訓練及び量子化過程がいずれも既存方法に比べて簡単であり、比較的優れた符号化正確性も得ることができる。
【０１０２】
本明細書で説明される方法は、一つ以上のプロセッサによって実行される一つ以上のコンピュータプログラムによって具現することができる。コンピュータプログラムは非一時的な類型のコンピュータ読取り可能媒体に格納されるプロセッサ実行可能命令を含む。コンピュータプログラムはまた、格納されたデータを含むことができる。非一時的な類型のコンピュータ読取り可能媒体（ｎｏｎ−ｔｒａｎｓｉｔｏｒｙ  ｔａｎｇｉｂｌｅ  ｃｏｍｐｕｔｅｒ  ｒｅａｄａｂｌｅ  ｍｅｄｉｕｍ）の非限定的な例は、不揮発性メモリーシステム、磁気格納所及び光学格納所である。
【０１０３】
（付記）
（付記１）
候補データセットからクエリの最近傍を検索するための候補ベクトルの符号化方法であって、
入力ベクトル（この時、最初の入力ベクトルは前記候補ベクトル）を正規化して方向ベクトル及びベクトルエネルギーを取得する正規化段階と、
前記方向ベクトルを量子化してコードワード及び残差ベクトルを取得する量子化段階と、
前記残差ベクトルを前記入力ベクトルとして、前記正規化段階及び前記量子化段階を予め設定された符号化次数だけ反復する段階と、
前記反復による一つ以上のコードワード及び一つ以上のベクトルのエネルギーを用いて前記候補ベクトルを符号化する段階と、
を含むベクトル符号化方法。
【０１０４】
（付記２）
前記量子化段階は、前記方向ベクトルの次数に対応するコードブックで前記方向ベクトルに最近接したワードを前記コードワードとして返還する段階を含む、付記１に記載のベクトル符号化方法。
【０１０５】
（付記３）
前記符号化する段階は、
前記符号化次数を予め設定された基準によって低次数と高次数とに分類する段階と、
前記低次数の入力ベクトルに対応するコードワードを用いて逆リストのインデクシングキーを生成する段階と、
前記高次数の入力ベクトルに対応するコードワード及び低次数の入力ベクトルに対応するベクトルエネルギーを用いてＲＮＱコードを生成する段階とを含み、
符号化された候補ベクトルは、前記インデクシングキーと前記ＲＮＱコードとの組合せであり、前記符号化次数は、前記低次数と前記高次数との和である、
付記１に記載のベクトル符号化方法。
【０１０６】
（付記４）
前記ＲＮＱコードは、前記逆リストにおいて前記インデクシングキーに対応する連結リストに保存され、前記連結リストの各項目は、候補ベクトルの識別情報及びＲＮＱコードを含むことを特徴とする、付記３に記載のベクトル符号化方法。
【０１０７】
（付記５）
前記符号化次数を分類する段階は、前記候補データセットのサイズが大きくなるほど、前記低次数に分類される値のサイズを増加させる段階をさらに含む、付記３に記載のベクトル符号化方法。
【０１０８】
（付記６）
前記符号化次数を４、前記低次数ｉを２、前記高次数ｊを２に設定した場合、前記候補ベクトルは下記の式のように近似化され、
【数５７】
2020515986.tif 000059
前記インデクシングキーは、前記
【数５８】
2020515986.tif 000060
に対応するＣ１及び前記
【数５９】
2020515986.tif 000061
に対応するＣ２を用いて次のように生成され、
インデクシングキー：Ｃ１Ｃ２
前記ＲＮＱコードは、前記ｅ０に対応するｈ０及び前記ｅ１に対応するｈ１及び前記
【数６０】
2020515986.tif 000062
に対応するＣ３及び前記
【数６１】
2020515986.tif 000063
に対応するＣ４を用いて次のように生成される、付記３に記載のベクトル符号化方法。
ＲＮＱコード：Ｃ３ｈ０Ｃ４ｈ１
【数６２】
2020515986.tif 000064
：第１次コードブック（Ｖ１）で残差ベクトルの方向ベクトルとの最近接コードワード
【数６３】
2020515986.tif 000065
：第２次コードブック（Ｖ２）で残差ベクトルの方向ベクトルとの最近接コードワード
【数６４】
2020515986.tif 000066
：第３次コードブック（Ｖ３）で残差ベクトルの方向ベクトルとの最近接コードワード
【数６５】
2020515986.tif 000067
：第４次コードブック（Ｖ４）で残差ベクトルの方向ベクトルとの最近接コードワード
ｅ０：第３残差ベクトルのエネルギー（スカラー値）
ｅ１：第４残差ベクトルのエネルギー（スカラー値）
ｐ１：
【数６６】
2020515986.tif 000068
残差方向ベクトルの投影
ｐ２：
【数６７】
2020515986.tif 000069
残差方向ベクトルの投影
【０１０９】
（付記７）
付記１〜６のいずれかに記載の方法を実行させるためにコンピュータ読取り可能媒体に格納されたベクトル符号化応用プログラム。
【０１１０】
（付記８）
候補データセットからクエリの最近傍を検索する方法であって、
前記クエリを正規化及び量子化して取得した一つ以上のコードワードを含む逆リストのインデクシングキーと前記クエリ間の距離を計算する段階と、
前記計算された距離を昇順に整列し、整列された距離が上位の特定百分位数以内である逆リストを候補連結リストに設定する段階と、
前記候補連結リストに含まれた候補ベクトルと前記クエリ間の距離を計算して前記最近傍を取得する段階と、
を含む最近傍探索方法。
【０１１１】
（付記９）
前記距離を計算する段階は、
１次コードブックに含まれる第１コードワード
【数６８】
2020515986.tif 000070
及び２次コードブックに含まれる第２コードワード
【数６９】
2020515986.tif 000071
の合成ベクトル
【数７０】
2020515986.tif 000072
と前記クエリｑ間の距離ｄを計算する段階を含む、付記８に記載の最近傍探索方法。
【０１１２】
（付記１０）
前記距離を計算する段階は、前記距離ｄの計算が次の式によってなされることを特徴とする、付記９に記載の最近傍探索方法。
【数７１】
2020515986.tif 000073
【０１１３】
（付記１１）
前記距離を計算する段階は、
前記クエリと第１コードワード間の距離を計算して昇順に整列する段階と、
前記クエリと第２コードワード間の距離を計算して昇順に整列する段階と、
前記整列された距離が上位の特定百分位数以内である第１コードワード及び第２コードワードを用いて前記合成ベクトルＩとクエリｑ間の距離を計算する段階と、
を含む、付記１０に記載の最近傍探索方法。
【０１１４】
（付記１２）
前記最近傍を取得する段階は、前記候補ベクトルｖと前記クエリｑ間の距離を下記の式を用いて計算する段階を含む、付記８に記載の最近傍探索方法。
【数７２】
2020515986.tif 000074
【０１１５】
（付記１３）
付記８〜１２のいずれかに記載の方法を実行させるためにコンピュータ読取り可能媒体に格納された最近傍探索応用プログラム。
【図１】
2020515986.tif 000091
【図２】
2020515986.tif 000092
【図３】
2020515986.tif 000093
【図４】
2020515986.tif 000094
【図５】
2020515986.tif 000095
【図６】
2020515986.tif 000096
【図７】
2020515986.tif 000097
【図８】
2020515986.tif 000098
【国際調査報告】
2020515986.tif 000099
2020515986.tif 000100
2020515986.tif 000101
2020515986.tif 000102
2020515986.tif 000103
2020515986.tif 000104