iDistance

パターン認識において、iDistanceは、多次元メトリック空間における点データに対するk近傍クエリのためのインデックス作成およびクエリ処理技術です。kNNクエリは、多次元データ、特にデータの次元数が多い場合における最も困難な問題の一つです。iDistanceは、高次元空間におけるkNNクエリを効率的に処理するように設計されており、実際のデータセットでよく見られる偏ったデータ分布に対して非常に優れたパフォーマンスを発揮します。

iDistanceは、候補領域の初期フィルタリングとそれに続く結果の精緻化という2段階の検索戦略を採用しています。これは、フィルタ・リファイン原則（FRP）に沿ったアプローチです。つまり、インデックスはまず検索空間を整理して可能性の低い候補を除外し、次に精緻化ステップで真の最近傍を検証します。これは、データベース検索アルゴリズムで使用される一般的なFRPパラダイムに従います。^{[ 1 ]} iDistanceインデックスは、機械学習モデルで拡張してデータ分布を学習し、多次元データの検索と保存を改善することもできます。^{[ 2 ]}

インデックス作成

iDistance インデックスの構築には 2 つのステップがあります。

データ空間内の複数の参照点が選択されます。参照点の選択方法は様々ですが、クラスター中心を参照点として使用するのが最も効率的です。データ点は、適切に選択された参照点に基づいてボロノイセルに分割されます。
データポイントとそれに最も近い参照点との間の距離が計算されます。この距離にスケーリング値を加算したものが、そのポイントのiDistanceと呼ばれます。これにより、多次元空間内のポイントは1次元の値にマッピングされ、その後、 iDistance をキーとして B ⁺ツリーを使用してポイントをインデックス化できます。

右の図は、3つの参照点（O ₁、O ₂、O ₃）が選択された例を示しています。これらのデータ点は1次元空間にマッピングされ、B ⁺木でインデックス付けされます。効果的なクエリパフォーマンスを実現するために参照点を選択するための様々な拡張が提案されており、その中には機械学習を用いて参照点の識別を学習する手法も含まれます。

クエリ処理

kNNクエリを処理するには、クエリを複数の1次元範囲クエリにマッピングします。これらのクエリはB ⁺ツリー上で効率的に処理できます。上図では、クエリQがB ⁺ツリー内の値にマッピングされ、kNN検索「球面」がB ^{+ツリー内の範囲にマッピングされています。k個のNNが見つかるまで、検索球面は徐々に拡大します。これは、B}⁺ツリーにおける徐々に拡大する範囲検索に対応しています。

iDistance 技術は、シーケンシャルスキャンを高速化する手法と捉えることができます。データファイルの先頭から末尾までレコードをスキャンするのではなく、iDistance は、最近傍レコードを非常に高い確率で早期に取得できる場所からスキャンを開始します。

アプリケーション

iDistanceは、次のような多くのアプリケーションで使用されています。

画像検索^{[ 3 ]}
ビデオインデックス作成^{[ 4 ]}
P2Pシステムにおける類似性検索^{[ 5 ]}
モバイルコンピューティング^{[ 6 ]}
レコメンデーションシステム^{[ 7 ]}

歴史的背景

iDistanceは、2001年にCui Yu、Beng Chin Ooi、Kian-Lee Tan、 HV Jagadishによって初めて提案されました。 ^{[ 8 ]}その後、Rui Zhangとともに、彼らはこの技術を改良し、2005年にさらに包括的な研究を行いました。^{[ 9 ]}

参照

参考文献

^ Ooi, Beng Chin; Pang, Hwee Hwa; Wang, Hao; Wong, Limsoon; Yu, Cui (2002).部分列選択のための高速フィルタ・リファインアルゴリズム. 国際データベースエンジニアリング・アプリケーションシンポジウム. IEEE. doi : 10.1109/IDEAS.2002.1029677 .
^ Angjela Davitkova、Evica Milchevski、Sebastian Michel、「ML-Index: ポイント、範囲、および最近傍クエリ用の多次元学習インデックス」、第23回国際データベース技術拡張会議の議事録、デンマーク、コペンハーゲン、407-410、2020年。
^ Junqi Zhang、Xiangdong Zhou、Wei Wang、Baile Shi、Jian Pei、「高次元インデックスを使用した関連性フィードバックベースのインタラクティブな画像検索のサポート」、第32回国際大規模データベース会議の議事録、韓国ソウル、1211-1214、2006年。
^ Heng Tao Shen、Beng Chin Ooi、Xiaofang Zhou、「大規模ビデオシーケンスデータベースの効果的なインデックス作成に向けて」、ACM SIGMOD 国際データ管理会議の議事録、メリーランド州ボルチモア、米国、730-741、2005 年。
^ Christos Doulkeridis、Akrivi Vlachou、Yannis Kotidis、Michalis Vazirgiannis、「メトリック空間でのピアツーピア類似性検索」、第33回国際大規模データベース会議の議事録、オーストリア、ウィーン、986-997、2007年。
^ Sergio Ilarri、Eduardo Mena、Arantza Illarramendi、「モバイルコンテキストでの位置依存クエリ: モバイルエージェントを使用した分散処理」、IEEE Transactions on Mobile Computing、第 5 巻、第 8 号、2006 年 8 月、ページ: 1029 - 1043。
^ Yang Song、Yu Gu、Rui Zhang、Ge Yu、「ProMIPS：軽量インデックスを使用した効率的な高次元c近似最大内積探索」、第37回IEEE国際データエンジニアリング会議、ギリシャ、ハニア、1619-1630、2021年。
^ Cui Yu、Beng Chin Ooi、Kian-Lee Tan、HV Jagadish「距離のインデックス作成：KNN処理の効率的な方法」、第27回国際大規模データベース会議の議事録、ローマ、イタリア、421-430、2001年。
^ HV Jagadish、Beng Chin Ooi、Kian-Lee Tan、Cui Yu、Rui Zhang iDistance: 最近傍検索のための適応型 B+ ツリーベースのインデックス作成方法、ACM Transactions on Data Base Systems (ACM TODS)、30、2、364-397、2005 年 6 月。

外部リンク

[1] Ooi, Beng Chin; Pang, Hwee Hwa; Wang, Hao; Wong, Limsoon; Yu, Cui (2002).部分列選択のための高速フィルタ・リファインアルゴリズム. 国際データベースエンジニアリング・アプリケーションシンポジウム. IEEE. doi : 10.1109/IDEAS.2002.1029677 .

[2] Angjela Davitkova、Evica Milchevski、Sebastian Michel、「ML-Index: ポイント、範囲、および最近傍クエリ用の多次元学習インデックス」、第23回国際データベース技術拡張会議の議事録、デンマーク、コペンハーゲン、407-410、2020年。

[3] Junqi Zhang、Xiangdong Zhou、Wei Wang、Baile Shi、Jian Pei、「高次元インデックスを使用した関連性フィードバックベースのインタラクティブな画像検索のサポート」、第32回国際大規模データベース会議の議事録、韓国ソウル、1211-1214、2006年。

[4] Heng Tao Shen、Beng Chin Ooi、Xiaofang Zhou、「大規模ビデオシーケンスデータベースの効果的なインデックス作成に向けて」、ACM SIGMOD 国際データ管理会議の議事録、メリーランド州ボルチモア、米国、730-741、2005 年。

[5] Christos Doulkeridis、Akrivi Vlachou、Yannis Kotidis、Michalis Vazirgiannis、「メトリック空間でのピアツーピア類似性検索」、第33回国際大規模データベース会議の議事録、オーストリア、ウィーン、986-997、2007年。

[6] Sergio Ilarri、Eduardo Mena、Arantza Illarramendi、「モバイルコンテキストでの位置依存クエリ: モバイルエージェントを使用した分散処理」、IEEE Transactions on Mobile Computing、第 5 巻、第 8 号、2006 年 8 月、ページ: 1029 - 1043。

[7] Yang Song、Yu Gu、Rui Zhang、Ge Yu、「ProMIPS：軽量インデックスを使用した効率的な高次元c近似最大内積探索」、第37回IEEE国際データエンジニアリング会議、ギリシャ、ハニア、1619-1630、2021年。

[8] Cui Yu、Beng Chin Ooi、Kian-Lee Tan、HV Jagadish「距離のインデックス作成：KNN処理の効率的な方法」、第27回国際大規模データベース会議の議事録、ローマ、イタリア、421-430、2001年。

[9] HV Jagadish、Beng Chin Ooi、Kian-Lee Tan、Cui Yu、Rui Zhang iDistance: 最近傍検索のための適応型 B+ ツリーベースのインデックス作成方法、ACM Transactions on Data Base Systems (ACM TODS)、30、2、364-397、2005 年 6 月。

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]