講演抄録/キーワード |
講演名 |
2011-06-20 17:15
ウェーブレット木によるバイナリコードの高速検索 ○田部井靖生(JST)・津田宏治(産総研/JST) IBISML2011-15 |
抄録 |
(和) |
近年, データの大規模化に伴いバイナリコードを用いた類似度検索はますます重要度を増している.
従来の空間分割に基づく手法(e.g., cover tree)とは異なり, 数値ベクトルはハッシュテーブルにより効率的に扱うことができる離散シンボルへと変換され処理される. しかし, ハッシュテーブルに基づく手法はベクトル空間の幾何的性質を扱うことが困難であり既存の手法は必ずしも効率的とは言えない.
そこで, 本稿ではウェーブレット木(Grossi et al., SODA'03)によるバイナリコードの効率的な検索手法を提案する. 提案手法は幾何的制約探索空間を効率よく枝刈りすることができ, ハッシュテーブルを使った処方よりも効率的である. 実験により, 提案手法は約8000万の大規模画像データに対しても適応可能であることを示す. |
(英) |
Similarity search using locality sensitive codes is recently of increasing interest due to unprecedented scalability. Unlike space-partitioning indexes (e.g.,cover tree), numerical vectors are converted to discrete symbols that can be handled efficiently by hash tables. Efficiency of the hash-based search, however, is still suboptimal, because they cannot exploit geometric properties of the vector space. We propose a new search algorithm of locality sensitive codes on a wavelet tree (Grossi et al., SODA'03). It is much more efficient that hash tables, as it allows us to narrow down the search space with geometric constraints. In experiments, our algorithm was successfully applied to 80 million images. |
キーワード |
(和) |
類似度検索 / ウェーブレット木 / バイナリコード / / / / / |
(英) |
similarity search / wavelet tree / locality sensitive binary codes / / / / / |
文献情報 |
信学技報, vol. 111, no. 87, IBISML2011-15, pp. 103-110, 2011年6月. |
資料番号 |
IBISML2011-15 |
発行日 |
2011-06-13 (IBISML) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
IBISML2011-15 |
研究会情報 |
研究会 |
IBISML |
開催期間 |
2011-06-20 - 2011-06-21 |
開催地(和) |
武田ホール |
開催地(英) |
Takeda Hall |
テーマ(和) |
機械学習とその応用 |
テーマ(英) |
Machine learning and its applications |
講演論文情報の詳細 |
申込み研究会 |
IBISML |
会議コード |
2011-06-IBISML |
本文の言語 |
日本語 |
タイトル(和) |
ウェーブレット木によるバイナリコードの高速検索 |
サブタイトル(和) |
|
タイトル(英) |
Fast Similarity Search of Binary Codes with Wavelet Tree |
サブタイトル(英) |
|
キーワード(1)(和/英) |
類似度検索 / similarity search |
キーワード(2)(和/英) |
ウェーブレット木 / wavelet tree |
キーワード(3)(和/英) |
バイナリコード / locality sensitive binary codes |
キーワード(4)(和/英) |
/ |
キーワード(5)(和/英) |
/ |
キーワード(6)(和/英) |
/ |
キーワード(7)(和/英) |
/ |
キーワード(8)(和/英) |
/ |
第1著者 氏名(和/英/ヨミ) |
田部井 靖生 / Yasuo Tabei / タベイ ヤスオ |
第1著者 所属(和/英) |
科学技術振興機構 ERATO湊離散構造処理系プロジェクト (略称: JST)
JST ERATO Minato Project (略称: JST) |
第2著者 氏名(和/英/ヨミ) |
津田 宏治 / Koji Tsuda / |
第2著者 所属(和/英) |
産業技術総合研究所 生命情報工学研究センター (略称: 産総研/JST)
Computational Biology Research Center, National Institute of Advanced Science and Technology (略称: CBRC) |
第3著者 氏名(和/英/ヨミ) |
/ / |
第3著者 所属(和/英) |
(略称: )
(略称: ) |
第4著者 氏名(和/英/ヨミ) |
/ / |
第4著者 所属(和/英) |
(略称: )
(略称: ) |
第5著者 氏名(和/英/ヨミ) |
/ / |
第5著者 所属(和/英) |
(略称: )
(略称: ) |
第6著者 氏名(和/英/ヨミ) |
/ / |
第6著者 所属(和/英) |
(略称: )
(略称: ) |
第7著者 氏名(和/英/ヨミ) |
/ / |
第7著者 所属(和/英) |
(略称: )
(略称: ) |
第8著者 氏名(和/英/ヨミ) |
/ / |
第8著者 所属(和/英) |
(略称: )
(略称: ) |
第9著者 氏名(和/英/ヨミ) |
/ / |
第9著者 所属(和/英) |
(略称: )
(略称: ) |
第10著者 氏名(和/英/ヨミ) |
/ / |
第10著者 所属(和/英) |
(略称: )
(略称: ) |
第11著者 氏名(和/英/ヨミ) |
/ / |
第11著者 所属(和/英) |
(略称: )
(略称: ) |
第12著者 氏名(和/英/ヨミ) |
/ / |
第12著者 所属(和/英) |
(略称: )
(略称: ) |
第13著者 氏名(和/英/ヨミ) |
/ / |
第13著者 所属(和/英) |
(略称: )
(略称: ) |
第14著者 氏名(和/英/ヨミ) |
/ / |
第14著者 所属(和/英) |
(略称: )
(略称: ) |
第15著者 氏名(和/英/ヨミ) |
/ / |
第15著者 所属(和/英) |
(略称: )
(略称: ) |
第16著者 氏名(和/英/ヨミ) |
/ / |
第16著者 所属(和/英) |
(略称: )
(略称: ) |
第17著者 氏名(和/英/ヨミ) |
/ / |
第17著者 所属(和/英) |
(略称: )
(略称: ) |
第18著者 氏名(和/英/ヨミ) |
/ / |
第18著者 所属(和/英) |
(略称: )
(略称: ) |
第19著者 氏名(和/英/ヨミ) |
/ / |
第19著者 所属(和/英) |
(略称: )
(略称: ) |
第20著者 氏名(和/英/ヨミ) |
/ / |
第20著者 所属(和/英) |
(略称: )
(略称: ) |
講演者 |
第1著者 |
発表日時 |
2011-06-20 17:15:00 |
発表時間 |
30分 |
申込先研究会 |
IBISML |
資料番号 |
IBISML2011-15 |
巻番号(vol) |
vol.111 |
号番号(no) |
no.87 |
ページ範囲 |
pp.103-110 |
ページ数 |
8 |
発行日 |
2011-06-13 (IBISML) |
|