Resizable-LSHによる閾値可変の近似的類似検索手法の高速化
スポンサーリンク
概要
- 論文の詳細を見る
本稿では,筆者らがこれまでに提案している Resizable-LSH を改善し,広域な閾値に対しても類似検索を可能にする手法を提案する.近年,類似度の尺度として距離を用いた高速な類似検索手法の 1 つとして,Locality-Sensitive Hashing (局所性鋭敏型ハッシング,以下 LSH) による近似的な類似検索が注目されている.LSH とは 「距離が近い入力同士は高い確率で衝突する」 特徴を持つハッシュ関数を用いたデータマッピング手法である.しかし事前計算の際に類似度の閾値を固定とすることで高速化しているため,エンドユーザが閾値を変更しながら類似検索をすることはできない.そこで Resizable-LSH ではハッシュ値が近いデータも検索することで,閾値を可変とした類似検索を実現しているが,閾値が大きくなると検索量も膨大になるため,速度低下を招いていた.本稿では Resizable-LSH のハッシュ値検索方式を変更してハッシュ値探索とデータ探索を同時に行う手法を提案する.本手法により,従来の Resizable-LSH と比較して 800 倍以上の速度向上を達成し,広域な閾値を設定した場合でも高速な類似検索を実現する.
- 2010-09-15
著者
-
山名 早人
早稲田大学
-
山名 早人
早稲田大学大学院理工学研究化情報科学専攻
-
山? 邦弘
早稲田大学大学院基幹理工学研究科修士課程
-
山名 早人
電子技術総合研究所情報アーキテクチャ部
-
YAMANA Hayato
Electrotechnical Laboratory
-
山名 早人
電子技術総合研究所
-
Yamana Hayato
Dept. Of Computer Science Waseda Univ.
-
山名 早人
早稲田大学理工学術院
関連論文
- OLTPのための自動グループコミット手法の提案(ストレージ 並列分散データベース,データ工学論文)
- 安価なWebカメラを用いたModel-Based視線推定 (ヒューマン情報処理)
- 配列プロファイルを利用したドメインリンカー予測(DNA・タンパク質構造)
- 手書き数式入力システムMathBox(テーマセッション4(数式),文字・文書の認識・理解)
- 単独記事フィルタリングを用いた時系列ニュース記事分類法の提案(テーマ,膨大なデータから学ぶもの)
- 多数のランドマークを用いるためのALTアルゴリズム拡張
- Hit Count Dance--検索エンジンのヒット数に対する信頼性検証
- Webページを対象とした著作権違反自動検知システム(ウェブ属性抽出,夏のデータベースワークショップDBWS 2006)
- Webページを対象とした著作権違反自動検知システム(ウェブ属性抽出)
- 選択注視点における特徴ベクトルの階層化クラスタリング(テーマ関連セッション2)
- 選択注視点における特徴ベクトルの階層化クラスタリング(テーマセッション(2),CVのためのパターン認識・学習理論の新展開)
- 選択注視を用いた画像検索システムの提案(一般セッション,文字認識・文書理解)
- Predictive Codingの誤差情報による選択注視(一般セッション(4))
- Predictive Coding の誤差情報による選択注視
- 複数キーワードクエリに対する検索ヒット数の信頼性検証(一般,「ユビキタス,センサ環境におけるデータベース」,及び一般)
- グラフデータ処理エンジンの実装と評価(ウェブ情報とデータベースに関して(ポスター講演))
- 8.100億規模のWebページ収集・分析への挑戦(第2部:情報の高信頼蓄積・検索技術等の開発,学と産の連携による基盤ソフトウェアの先進的開発)
- 検索エンジンの信頼性(情報の信頼性評価)
- 商用検索エンジンのヒット数に対する信頼性の検証(セッション5a:Webマイニング)
- Webページ間の関連性の伝播を用いたWebコミュニティ抽出手法(セッション5a:Webマイニング)
- アクセスパターンマイニングによるOSレベルでの動的なI/O最適化(セッション3a:Data Mining and Enterprise DB)
- ウィキペディアを対象とした編集回数に依存しない編集者の信頼度測定手法(一般,膨大なデータから学ぶもの)
- 100億規模のWebページ収集とその活用(膨大なデータから学ぶもの)
- 検索エンジンのランキングにおける日本語版ウィキペディアの影響力(テーマ,膨大なデータから学ぶもの)
- 100億規模のWebページ収集とその活用(招待講演,膨大なデータから学ぶもの)
- メニーコア時代におけるOSレベルでのI/O最適化(jDBワークショップ)
- 全世界のWebサーバの地理的位置・バックリンク数の解析(Web解析・検索クエリ)
- MPIプログラム実行時間予測ツールMPIETEの評価(MPI性能評価)
- MPIプログラムの簡易実行による実行時間予測手法の評価(HPC-9 : 性能評価)(2003年並列/分散/協調処理に関する『松江』サマー・ワークショップ(SWoPP松江2003))
- 実測に基づいたMPIプログラムの実行時間予測手法
- 検索エンジンを使った翻訳サポートシステムの構築(応用・事例1)(夏のデータベースワークショップDBWS2004)
- マルチプルアラインメントプログラムPRIMEの速度・精度両面からの改良
- 検索語の重みの2段階調整手法(センサデータ処理及び一般,センサデータ処理,ストリームデータベース,及び一般)
- 選択注視を用いた画像検索システムの提案(一般セッション,文字認識・文書理解)
- マルチプルアラインメントプログラムPRIMEの速度・精度両面からの改良
- 単独記事フィルタリングを用いた時系列ニュース記事分類法の提案(テーマ,膨大なデータから学ぶもの)
- ウィキペディアを対象とした編集回数に依存しない編集者の信頼度測定手法(一般,膨大なデータから学ぶもの)
- 検索エンジンのランキングにおける日本語版ウィキペディアの影響力(テーマ,膨大なデータから学ぶもの)
- 特徴領域の位置関係に着目したテンプレートマッチングによる類似物体検出
- ロックフリーGCLOCKページ置換アルゴリズム
- Resizable-LSHによる閾値可変の近似的類似検索手法の高速化
- 安価なWebカメラを用いたModel-Based視線推定(テーマ関連,顔・人物・ジェスチャ・行動)
- 安価なWebカメラを用いたModel-Based視線推定(テーマ関連,顔・人物・ジェスチャ・行動)
- ミニブログにおける注目語抽出手法の提案と注目語を用いたメディア間での話題追跡
- クラウド環境でのストリーミングアプリケーション向け動的資源配置手法
- 並列処理システム-晴-におけるマクロブロック終了検出
- 並列処理システム-晴-の待ち合わせ記憶構成
- 2-way prediction法によるGPCRリガンドの結合予測
- ウェブクローラ向けの効率的な重複URL検出手法
- 3ZK-10 Webページ間最短経路探索システムの構築(情報爆発時代におけるWeb技術およびWeb情報抽出,学生セッション,「情報爆発」時代に向けた新しいIT基盤技術)
- イベント発生時間間隔を考慮したシーケンシャルパターンマイニング(データマイニング, 夏のデータベースワークショップDBWS2005)
- イベント発生時間間隔を考慮したシーケンシャルパターンマイニング(データマイニング, 夏のデータベースワークショップ2005)
- インターネットオークションにおける不正行為者の発見支援(マイニング,夏のデータベースワークショップDBWS 2006)
- インターネットオークションにおける不正行為者の発見支援(マイニング)
- 先行評価に適したマクロタスク生成手法
- 分散メモリ型並列計算機AP1000上への疎行列用BLAS-3の実装
- 先行評価を用いたマクロタスクの多段仮実行方式における分散制御手法
- はれだすにおけるループ間依存関係の記述方法とその適用例
- 超並列のためのマルチアーキテクチャコンパイラはれだすの内部表現
- データ駆動計算機におけるDOACROSS型ループに対するフロー処理方式の提案
- 先行評価を用いたFORTRANプログラムの並列化と実行方式
- マルチプロセッサシステムにおける多段先行評価制御手順
- 多重ループの最適なベクトル化手法の提案
- 並列処理システム : 晴における条件分岐文の並列処理とその効果
- 並列処理システム-晴-におけるカラー管理方式
- 6K-7 データアクセスパターンに基づくデータマイニング手法の分類(情報爆発時代における並列分散処理技術,一般セッション,「情報爆発」時代に向けた新IT基盤技術,情報処理学会創立50周年記念(第72回)全国大会)
- マルチコア・SMTプロセッサ上におけるシェルスクリプト高速化手法(コンパイラ及びツール,「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2007))
- マルチコア・SMTプロセッサ上におけるシェルスクリプト高速化手法(コンパイラ及びツール,「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2007))
- 拡張多視点SPSによる3次元形状と反射属性の推定(一般セッション15)
- Improvement in Speed and Accuracy of Multiple Sequence Alignment Program PRIME
- ユーザクエリによる画像へのキーワード付けを利用した画像検索 : 利用によって賢くなる検索エンジン(一般セッション5(映像処理2),文字・文書の認識・理解)
- 拡張多視点SFSによる3次元形状と反射属性の推定(一般セッション(5),CVのためのパターン認識・学習理論の新展開)
- テクスチャと非テクスチャの区別を用いた輪郭線抽出(スポーツ・運動映像のパターン認識・理解)
- 検索エンジンを用いた英文冠詞誤りの検出(夏のデータベースワークショップ2007(データ工学,一般))
- 検索エンジンを用いた英文冠詞誤りの検出(検索エンジン応用,夏のデータベースワークショップ2007(データ工学,一般))
- F-033 共有メモリ型並列計算機上での強化学習の並列学習法(F.人工知能)
- 強化学習並列化による学習の高速化(一般 : マルチエージェントと学習)
- 強化学習並列化による学習の高速化(一般(マルチエージェントと学習))(「社会システムにおける知能」及び一般)
- メニーコア時代におけるOSレベルでのI/O最適化(jDBワークショップ)
- リモートメモリを用いたランダムディスクアクセス高速化手法(ARC-9 : システム制御,2007年並列/分散/協調処理に関する『旭川』サマー・ワークショップ(SWoPP旭川2007))
- 商用検索エンジンのランキングに関する定量的評価と特徴解析(夏のデータベースワークショップ2007(データ工学,一般))
- 商用検索エンジンのランキングに関する定量的評価と特徴解析(ランキング,夏のデータベースワークショップ2007(データ工学,一般))
- N-gram と離散型共起表現を用いたワードサラダ型スパム検出手法の提案
- N-gram と離散型共起表現を用いたワードサラダ型スパム検出手法の提案
- 全世界のWebサーバの地理的位置・バックリンク数の解析(Web解析・検索クエリ)
- 全世界のWebサーバの地理的位置・バックリンク数の解析
- 二種類のSVMを用いたオンライン類似数式文字識別(テーマセッション,文字認識・文書理解)
- 二種類のSVMを用いたオンライン類似数式文字識別(テーマセッション,文字認識・文書理解)
- デジタルペンによるオンライン数式サンプル採取システムと採取文字サンプルに対する認識実験(一般, 顔・ジェスチャーの認識・理解)
- 先読みスレッドを用いたDiskアクセスの高速化(セキュアアーキテクチャ,「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2007))
- 先読みスレッドを用いたDiskアクセスの高速化(セキュアアーキテクチャ,「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2007))
- 5L-1 全世界のWebページのTLD・言語分布解析(リーディングプロジェクト e-society:WebアーカイブとWebデータ解析技術,一般セッション,リーディングプロジェクト e-society)
- 10. 21世紀COEプロジェクト「プロダクティブICTアカデミア」(21世紀卓越した情報研究拠点プログラムの目指す研究(前編))
- 21世紀COEプロジェクト「プロダクティブICTアカデミア」
- 1. 検索エンジンの概要(検索エンジン2005-Webの道しるべ-)
- C-013 スレッドレベル投機的実行に関する考察(C分野:アーキテクチャ・ハードウェア)
- Tri-Mode分岐予測器の提案(プロセッサ技術(1), 「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2005))
- Tri-Mode分岐予測器の提案(プロセッサ技術(1), 「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2005))
- Tri-Mode 分岐予測器の提案
- BTBのエントリ有無を参照した分岐予測器(プロセッサアーキテクチャ)