見る/開く - JAIST学術研究成果リポジトリ

JAIST Repository
https://dspace.jaist.ac.jp/
Title
大規模な音楽指紋データベースの高速検索におけるク
エリの歪みへの頑健性向上に関する調査研究
Author(s)
福田, 真啓
Citation
Issue Date
2015-09
Type
Thesis or Dissertation
Text version
author
URL
http://hdl.handle.net/10119/12925
Rights
Description
Supervisor: 井口寧, 情報科学研究科, 修士
Japan Advanced Institute of Science and Technology
大規模な音楽指紋データ ベースの高速検索における
ク エリ の歪みへの頑健性向上に関す る 調査研究
北陸先端科学技術大学院大学
情報科学研究科
福田 真啓
平成 27 年 9 月
修 士 論 文
大規模な音楽指紋データ ベースの高速検索における
ク エリ の歪みへの頑健性向上に関す る 調査研究
1310203
主指導教員
審査委員主査
審査委員
福田 真啓
井口
井口
田中
金子
寧
寧
清史
峰雄
北陸先端科学技術大学院大学
情報科学研究科
平成 27 年 8 月
概要
近年のイ ン タ ーネ ッ ト は， 音楽の流通を 活発に する 場を 提供し て いる 一方で， 不正コ ピ ー
の温床に も なっ て いる 。 こ れに 対し ， エン ド ユーザが音楽データ を 通信する だけ で自動的
に ラ イ セ ン ス・ 課金情報を 受信者に 提示でき る と いう ， 手軽で合法的な 音楽共有シス テム
が提案さ れて いる 。 し かし 高速化を 続け る ネ ッ ト ワ ーク 機器内で音楽を リ ア ルタ イ ム 処理
で検索する のは決し て 容易ではな い。 データ ベース (DB) が千万曲規模に な る と な おさ ら
である 。 本研究の目的は， 千万曲以上の DB の高速かつ高精度な 音楽検索を 組込みシス テ
ム と し て 実現する こ と であ る 。
音楽の高速検索に おいて 重要な 要素技術は音楽指紋である 。 検索を 高速化・ 省メ モリ 化
でき る ため， 組込みシス テム を 前提と し た音楽の高速検索に は必須の技術である 。 し かし
単に 音楽指紋を 高速検索でき る だけ では， 手軽で合法的な 音楽共有シス テム は実用化でき
な い。 本稿では指紋検索の大規模 DB 化と 歪み対策に 焦点を 当て る 。 指紋検索の先行研究
であ る Yang の Staged LSH は指紋 DB と ハッ シュ テ ーブルに 大容量のメ モリ を 必要と す
る た め， 300 曲ま でし か実験がな さ れて いな い。 別の問題と し て ， ハッ シュ 探索を し て い
る た め指紋のビッ ト エラ ーに も 弱く ， 検索精度と 検索速度が悪化する 。
そ こ で本稿ではいかに し て 高速化と 高精度化を 両立でき る かを 調査し た。 大規模 DB 化
し つつ検索速度を 落と さ な い工夫と し て ， 複数種類のメ モリ を 用いた 階層化 Staged LSH
を 提案する 。 併せて ， 検索速度と 検索精度のト レ ード オフ を 柔軟に 調整可能な 隣接 LSH
探索も 提案する 。 こ れら の手法に よ り ， 指紋 DB を 千万曲規模に 拡大し つつ， 検索速度を
27.0 倍に 向上， 検索精度を 維持する こ と に 成功し た 。
目次
第1章
1.1
1.2
1.3
はじ めに
研究の背景 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
研究目的 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
本論文の構成 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
第2章
2.1
2.2
2.3
2.4
2.5
音楽指紋と そ の関連研究
音楽指紋と は . . . . . . . . . . . . . . . . . . . . .
通信プロ ト コ ルの解析 . . . . . . . . . . . . . . . .
PCM データ への変換 . . . . . . . . . . . . . . . . .
指紋生成 . . . . . . . . . . . . . . . . . . . . . . . .
指紋検索 . . . . . . . . . . . . . . . . . . . . . . . .
2.5.1 Yang の研究成果の概要 . . . . . . . . . . . .
2.5.2 ハミ ン グ距離のハード ウ ェ ア ア ク セ ラ レ ータ
2.5.3 Staged LSH と そ の検索ア ルゴ リ ズム . . . .
2.5.4 Staged LSH の問題点 . . . . . . . . . . . . .
ラ イ セ ン ス ・ 課金情報の送信 . . . . . . . . . . . .
まとめ . . . . . . . . . . . . . . . . . . . . . . . . .
2.6
2.7
第3章
3.1
3.2
3.3
3.4
3.5
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
階層化 Staged LSH によ る 大規模音楽指紋検索シ ス テム の実装
組込みシス テ ム と し て の音楽指紋検索 . . . . . . . . . . . . . .
階層化 Staged LSH に よ る 大規模指紋 DB の検索の高速化 . . . .
隣接 LSH 探索に よ る 高速化・ 高精度化のト レ ード オフ の調整 . .
提案シス テ ム の実装 . . . . . . . . . . . . . . . . . . . . . . . .
まとめ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
第 4 章 評価実験
4.1 現実の音楽から 生成し た 指紋 DB での評価
4.1.1 開発環境と 実験環境 . . . . . . . .
4.1.2 隣接 LSH 探索の評価 . . . . . . . .
4.1.3 リ ソ ース 使用量 . . . . . . . . . . .
4.2 千万曲分の乱数指紋 DB での評価 . . . . .
4.2.1 開発環境と 実験環境 . . . . . . . .
i
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
1
1
2
2
.
.
.
.
.
.
.
.
.
.
.
3
3
4
4
5
8
8
8
10
13
13
14
.
.
.
.
.
15
15
17
18
20
21
.
.
.
.
.
.
22
22
22
23
26
26
26
4.3
4.2.2
4.2.3
4.2.4
4.2.5
まとめ
階層化 Staged LSH の評価 . . . . . . . . . . . . . . . . .
隣接 LSH 探索の評価 . . . . . . . . . . . . . . . . . . . .
階層化 Staged LSH と 隣接 LSH 探索の組み合わせの評価
リ ソ ース 使用量 . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
26
30
32
34
34
第 5 章 ま と めと 今後の課題
35
付 録 A 理論検索時間と 理論検索精度
A.1 変数と 関数の記号 . . . . . . . . . . . . . . . . . . . . . . . .
A.2 検索精度に 関する 考察 . . . . . . . . . . . . . . . . . . . . .
A.2.1 不正解指紋が精査を パス し て し ま う 確率 . . . . . . .
A.2.2 正解指紋が精査を パス でき な い確率 . . . . . . . . . .
A.2.3 正解指紋がス ク リ ーニン グを パス でき な い確率 . . .
A.2.4 LSH のハッ シュ 値に ビッ ト エラ ーがあ る 確率 . . . .
A.2.5 ハッ シュ 値のビッ ト 数の最適値 . . . . . . . . . . . .
A.3 検索時間の理論値 . . . . . . . . . . . . . . . . . . . . . . . .
A.3.1 1 回のハッ シュ 探索と ス ク リ ーニン グの平均実行時間
A.3.2 ハッ シュ 探索の実行回数の期待値 . . . . . . . . . . .
38
38
39
39
40
41
42
43
43
44
44
ii
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
図目次
1.1
ネ ッ ト ワ ーク 機器内での音楽検索 . . . . . . . . . . . . . . . . . . . . . . .
1
2.1
2.2
2.3
2.4
2.5
2.6
2.7
2.8
2.9
2.10
2.11
2.12
2.13
2.14
音楽指紋を 用いた 高速検索 . . . . . . . . . . . . . . . . . . . . . . . . . . .
元の音楽データ を 用いた 高速でな い検索 . . . . . . . . . . . . . . . . . . .
ネ ッ ト ワ ーク 機器内での音楽指紋検索シス テ ム に 必要な 処理 . . . . . . . .
音楽指紋の歪み . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Haar ウ ェ ーブレ ッ ト 変換を 用いたマ ルチレ ベルサブバン ド 分解ア ルゴリ ズム
音楽指紋の生成ア ルゴ リ ズム (HiFP 2.0) . . . . . . . . . . . . . . . . . . .
HiFP 2.0 の図解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
HiFP2.0 の歪みのヒ ス ト グラ ム . . . . . . . . . . . . . . . . . . . . . . . .
ハミ ン グ距離を 計算する ハード ウ ェ ア . . . . . . . . . . . . . . . . . . . .
Staged LSH のア ルゴ リ ズム . . . . . . . . . . . . . . . . . . . . . . . . . .
指紋と サブ指紋と フ レ ーム . . . . . . . . . . . . . . . . . . . . . . . . . . .
Staged LSH で徐々 に 指紋 DB の探索範囲を 狭めて いく 様子 . . . . . . . . .
局所性鋭敏型ハッ シュ の生成方法 . . . . . . . . . . . . . . . . . . . . . . .
ハッ シュ テ ーブルと 指紋 DB のデータ 構造 . . . . . . . . . . . . . . . . . .
3
3
4
5
6
6
7
8
9
10
10
11
12
12
3.1
3.2
3.3
3.4
3.5
3.6
3.7
ネ ッ ト ワ ーク 機器内での音楽指紋検索 . . . . . . . .
FPGA の基本的な 構造の例 . . . . . . . . . . . . . . .
指紋 DB と ハッ シュ テ ーブルのメ モリ 格納方法 . . . .
階層化 Staged LSH のア ルゴ リ ズム (フ ロ ーチャ ート )
隣接ハッ シュ の例 . . . . . . . . . . . . . . . . . . . .
隣接 LSH 探索のア イ デア . . . . . . . . . . . . . . .
音楽指紋検索のシス テ ム と 内部モジュ ールの構成図 .
4.1
4.2
4.3
4.4
4.5
歪み率と 平均検索時間 . . . . . . . . . . . . . . . . . . . . . . . . .
歪み率と 検索精度 . . . . . . . . . . . . . . . . . . . . . . . . . . . .
階層化 Staged LSH の評価の歪み率と 平均検索時間・ 検索精度 . . .
隣接 LSH 探索の評価の歪み率と 平均検索時間・ 検索精度 . . . . . .
階層化 Staged LSH と 隣接 LSH 探索の評価の歪み率と 平均検索時間・
精度 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
15
16
17
18
19
19
20
. . .
. . .
. . .
. . .
検索
. . .
.
.
.
.
24
25
28
30
. 32
A.1 ク エリ 指紋の歪みに よ り 正解指紋が精査を パス し な い確率 . . . . . . . . . 40
iii
A.2 ク エリ 指紋の歪みに よ り 正解指紋のフ レ ーム がス ク リ ーニン グを パス し な
い確率 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
A.3 ハッ シュ 探索が 126 回全て 失敗する 確率 . . . . . . . . . . . . . . . . . . . 42
A.4 全体の検索時間の期待値 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
iv
表目次
2.1
ハミ ン グ距離の計算時間 . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.1
音楽指紋検索シス テ ム の内部モジュ ール一覧 . . . . . . . . . . . . . . . . . 20
4.1
4.2
4.3
4.4
4.5
4.6
4.7
4.8
4.9
4.10
4.11
4.12
4.13
4.14
4.15
4.16
FPGA の開発環境 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
FPGA ボード の特徴 . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
隣接 LSH 探索の評価実験の条件 . . . . . . . . . . . . . . . . . . . . . . .
Yang の手法と 隣接 LSH 探索の検索時間 . . . . . . . . . . . . . . . . . .
Yang の手法と 隣接 LSH 探索の検索精度 . . . . . . . . . . . . . . . . . .
実装し た 指紋検索モジュ ール (Staged LSH モジュ ール ) のリ ソ ース 使用量
FPGA の開発環境 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
FPGA ボード の特徴 . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
デス ク ト ッ プ PC の仕様 . . . . . . . . . . . . . . . . . . . . . . . . . . .
階層化 Staged LSH の評価実験の条件 . . . . . . . . . . . . . . . . . . . .
階層化 Staged LSH の評価実験の結果 . . . . . . . . . . . . . . . . . . . .
隣接 LSH の評価実験の条件 . . . . . . . . . . . . . . . . . . . . . . . . .
隣接 LSH 探索の評価実験の結果 . . . . . . . . . . . . . . . . . . . . . . .
階層化 Staged LSH と 隣接 LSH の評価実験の条件 . . . . . . . . . . . . .
階層化 Staged LSH と 隣接 LSH 探索の評価実験の結果 . . . . . . . . . . .
実装し た 指紋検索モジュ ール (Staged LSH モジュ ール ) のリ ソ ース 使用量
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
9
22
23
23
24
25
26
27
27
27
28
29
30
31
32
33
34
A.1 変数の一覧 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
A.2 関数の一覧 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
A.3 ハッ シュ 値のビッ ト 数と ハッ シュ テ ーブルのメ タ データ のサイ ズ . . . . . . 43
v
第 1 章 はじ めに
1.1
研究の背景
近年， イ ン タ ーネ ッ ト 上の音楽の流通が盛んに な っ て いる 。 Apple iTunes Store のよ う
に 大規模な 音楽配信サービス も 現れて おり ， そ の配信の場と し て イ ン タ ーネ ッ ト が利用さ
れて いる 。 一方でイ ン タ ーネ ッ ト は不正コ ピ ーの温床に も な っ て おり ， そ のた め 2012 年
に は著作権法が改正さ れ違法ダウ ン ロ ード が刑罰化さ れた。 イ ン タ ーネ ッ ト で音楽を 利用
でき る こ と は魅力的であ る が， 常に 著作権法を 意識し な け ればな ら な いのは窮屈であ る 。
不正コ ピ ーの対策に は複数の方法がある が， いずれも 課題が残さ れて いる 。 電子透かし
の埋め込みは， 保存形式な ど を 変更する と 埋め込ん だ 情報が失われやすいし ， 消費者に
と っ て も 自分が不正コ ピ ーを し た こ と に 気づき やすく な る わけ ではな い。 デジタ ル著作
権管理 (DRM) は暗号化技術な ど に よ り 第三者に よ る コ ン テン ツ の利用を 防ぐ 方法である
が， 専用機器や専用ソ フ ト ウ ェ ア でし か再生でき な いため消費者に と っ て 不便である 。 音
楽や動画の投稿サイ ト の巡回・ 監視に ついて は， 個人個人がメ ールな ど で音楽データ を 送
受信する ケ ース に 対応でき な い。
イ ン タ ーネ ッ ト で音楽を 気軽に 利用し た いが， 気づかぬう ち に 著作権法を 犯すこ と は
回避し たい。 こ の要求に 応え る ため， 図 1.1 のよ う な ， 著作権保護さ れた音楽を イ ン タ ー
ネ ッ ト で通信する と ， イ ン タ ーネ ッ ト サービス プロ バイ ダ (ISP) のネ ッ ト ワ ーク 機器が自
動的に そ の音楽を 検出し て ， ラ イ セ ン ス や課金情報を 受信者に 提示する シス テム が提案さ
れて いる 。 こ れが実現する と ， 世界中の消費者はメ ールや P2P で音楽を 送受信する だけ
で合法的に 音楽を 共有でき る 。
インターネット
ISPのルータ
ISPのルータ
送信者
音楽
ファイル
音楽検索
ライセンス
・課金情報
受信者
図 1.1: ネ ッ ト ワ ーク 機器内での音楽検索
注意点と し て ， こ のシス テム は暗号化通信に 対し て は無力である 。 目的は著作権者側に
よ る 利用者の監視ではな い。 利用者が音楽データ を 手軽かつ合法的に共有する こ と が目的
であ る 。 こ のシス テ ム を 有効に 利用する た めに は， 通信は平文で行う 必要があ る 。
1
1.2
研究目的
手軽で合法的な 音楽検索シス テム の実用化には， ルータ 内で高速かつ高精度に 検索でき
る 組込みシステム が必要である 。 し かし ルータ の転送速度は 40Gbps， 100Gbps， 400Gbps
と 高速化を 続け て お り ， 音楽データ が通過する 間に リ ア ルタ イ ム 処理で高精度の検索が
でき て いる 研究は多く な い。 し かも イ ン タ ーネ ッ ト に は数千万曲以上の音楽が存在する 。
少な く と も 10GB 以上のデータ ベース (DB) を 格納する 記憶装置が必要である が， 低速な
HDD や SSD は使用し た く な いので， 実験を する こ と すら 難し いのが現状であ る 。
本研究の目的は， 千万曲以上の DB の高速かつ高精度な 音楽検索を 組込みシス テム と し
て 実現する こ と である 。 音楽検索の高速化と 省メ モリ 化に 不可欠な 指紋技術を 利用し ， 回
路の変更が容易な FPGA で実装・ 評価実験を する 。 先行研究で Yang が Staged LSH と い
う 音楽指紋検索ア ルゴ リ ズム を FPGA に 実装・ 実験し て いる ので， こ れを 改良し て 大規
模 DB 化な ど を 目指す。 本研究の独創的な 点は， 千万曲の DB の格納に HDD や SSD では
な く PCI Express(PCIe) 経由の大容量の DRAM を 利用し て いる 点であり ， DDR3 経由と
PCIe 経由の 2 種類のメ モリ に ど のよ う に データ を 配置する かを 工夫し た 。 精度に ついて
も ， 高速化と 高精度化のト レ ード オフ を 柔軟に 調整でき る 手法を 考案し た 。
1.3
本論文の構成
本稿の第 1 章では研究の背景と 目的を 述べた。 第 2 章では音楽の高速検索に おけ る 重要
な 要素技術である 指紋やそ の歪み率の定義を 示し た上で， 指紋を 用いた音楽検索の先行研
究を 紹介し ， 問題点を 明ら かに する 。 第 3 章では本研究の提案手法およ び実装に ついて 述
べ， 先行研究の Staged LSH の問題点を 解決する 。 第 4 章では FPGA を 用いて 提案手法の
評価実験を 行っ たので， そ の実験環境と 実験結果を 示し た上で考察を する 。 最後に 第 5 章
でま と めと 今後の課題で締めく く る 。 付録 A は提案手法の検索速度と 検索精度の理論式
の導出であ る 。
2
第 2 章 音楽指紋と そ の関連研究
2.1
音楽指紋と は
音楽の高速検索に おいて 重要な 要素技術は音楽指紋である (単に 指紋と も 言う )。 指紋と
は， 録音し た音楽のメ ロ ディ やリ ズム な ど の聴覚的な 特徴を ま と めた小サイ ズのデータ で
あ る 。 指紋は図 2.1 の方式に よ る 音楽の高速検索に 活用さ れて いる 。 こ の方式は図 2.2 の
よ う な 元の音楽データ 同士の比較に よ る 素朴な 検索に 比べて 次のよ う な 利点があ る 。
1. 小サイ ズな ので比較回数が少な い (高速)
2. 小サイ ズな ので高速・ 小容量のメ モリ を 有効活用でき る (高速・ 省メ モリ )
3. 同じ 曲の MP3， AAC な ど の複数の保存形式を DB に用意する 必要がな い (省メ モリ )
音楽指紋
の生成
クエリ音楽
音楽指紋
の比較
検索結果
音楽指紋DB
(小サイズ)
音楽DB
(巨大サイズ)
音楽指紋
の生成
図 2.1: 音楽指紋を 用いた 高速検索
クエリ音楽
音楽データ
の比較
検索結果
音楽DB
(巨大サイズ)
図 2.2: 元の音楽データ を 用いた 高速でな い検索
3
実は前ページの図 2.1 だけ では， 1 章で示し た ネ ッ ト ワ ーク 機器内での音楽指紋検索シ
ス テム は実現でき な い。 本研究の範囲を よ り 明確に する ため， 他に 必要な 処理も 合わせた
全体像を 図 2.3 に 示す。 本研究の主な 焦点は “指紋検索” 部分であ る が， 他の処理に つい
て も 本章で簡単に 説明する 。
ISPのルータ
通信データ
通信プロトコル
の解析
音楽データ
(MP3，AACなど)
本研究の焦点
PCMデータ
への変換
PCMデータ
指紋生成
指紋
指紋検索
検索結果
(音楽ID)
ライセンス・
課金情報の送信
ライセンス・
課金情報
図 2.3: ネ ッ ト ワ ーク 機器内での音楽指紋検索シス テ ム に 必要な 処理
2.2
通信プロ ト コ ルの解析
ネッ ト ワ ーク 機器内で音楽指紋検索する にあたり ， ま ず最初に “通信プロ ト コ ルの解析”
を する 必要があ る 。 こ れは ISP のネ ッ ト ワ ーク 機器に 入っ て く る 通信データ (フ レ ーム や
パケ ッ ト ) から 音楽データ を 抽出する 処理である 。 ア プリ ケ ーショ ン 層の多様な プロ ト コ
ル (HTTP， SMTP な ど ) や符号化方式 (Base64 な ど ) やそ れら のバージョ ン アッ プな ど に
ど こ ま で対応する べき かと いう 点が主な 課題である が， 多く は仕様が公開さ れて いる ので
サポート する プロ ト コ ルを 限定すれば開発自体は容易であ る 。
2.3
PCM データ への変換
音楽データ を 抽出し た ら ， 次は “PCM データ への変換” を 行う 。 こ れは MP3 や AAC
で圧縮さ れて いる 音楽データ を ， 非圧縮の PCM(パルス 符号変調) データ に 変換する 処理
である 。 こ の変換処理に ついて は， さ ら な る 高速化の研究も 考え ら れる が， 既に 一定の高
R
R プロ セッ
速化が達成さ れて いる 。 例え ば lame 3.99.5 と いう フ リ ーソ フ ト を IntelXeon
サで実行し て みたと こ ろ ， 5.19MB の MP3 フ ァ イ ルを 0.837 秒でデコ ード し た。 こ れは変
換速度が 8 × 5.19MB ÷ 0.837 = 49.6Mbps である こ と を 意味する 。 な お本研究では後段の
処理工程であ る “指紋生成” に HiFP2.0 を 利用する た め， “PCM データ への変換” が出力
する PCM データ はサン プリ ン グ周波数 44.1kHz， 量子化ビッ ト 数 16 と する 。
本処理工程では歪みの問題が発生する こ と がある 。 歪みの問題と は図 2.4 のよ う に， 元々
が同じ 音楽データ である に も 関わら ず， 保存形式・ 圧縮率の変更に よ る 非可逆圧縮に よ っ
て 聴覚情報が歪む こ と であ る 。 聴覚情報が歪む と 後で生成する 指紋に も 多少のビッ ト エ
ラ ーを 生じ さ せて し ま う 。 こ れは現時点のど の指紋生成ア ルゴリ ズム でも 回避でき な い問
題な ので， “指紋検索” の処理工程に お いて は完全一致の探索ではな く 類似度を 利用し た
最近傍探索が必要に な る 。 な お本研究では主に 音楽 CD から コ ピ ーし た音楽の特定を 目指
し て いる た め， 録音時の雑音や録音開始のタ イ ミ ン グのずれな ど に よ る 歪みは考え な い。
4
非可逆圧縮
(元の音楽データ)
(歪んだ音楽データ)
指紋生成
指紋生成
(元の音楽指紋)
(歪んだ音楽指紋)
XOR
図 2.4: 音楽指紋の歪み
2.4
指紋生成
音楽データ の PCM データ を 得た ら ， 次は “指紋生成” を する 。 指紋生成ア ルゴ リ ズム
は複数提案さ れて いる が， 音楽の検索に 向いて いる のは， 高速に 小サイ ズの指紋を 生成で
き ， かつ歪みの問題が発生し て も 同じ 音楽か異な る 音楽かを 確実に 見分け ら れる も ので
ある 。
Haitsma ら は論文 [2] でフ ーリ エ変換を 基本と し た 指紋を 生成する 方法を 提案し た 。 論
文に は再生時間 11.6 ミ リ 秒ごと に 32 ビッ ト のサブ指紋を 生成し ， 一万曲では 2.5 億のサ
ブ指紋にな る と 記載さ れて いる 。 すな わち 一万曲ですら 1GB の指紋 DB と ハッ シュ テーブ
ルが必要であり ， そ のま ま 千万曲に 大規模化する と 1TB 以上に な る 。 ま た， DFT や FFT
な ど のフ ーリ エ変換の計算は， 前節の HiFP2.0 に 比べハード ウ ェ ア 処理が低速であ る 。
Schreiber ら は論文 [3] で Haitsma の方法を 発展さ せ， 指紋の中から 歪みに く い部分だけ
を DB に 格納する 戦略を 取っ た が， そ れでも 千万曲で 22GB と いう 見積も り であ る 。
荒木ら は文献 [1] でウ ェ ーブレ ッ ト 変換に 基づく HiFP2.0 を 提案し た 。 Haitsma ら の方
法に 比べて ハード ウ ェ ア 処理に 向いて いる 上に ， 指紋は 1 曲あたり 4096 ビッ ト (千万曲で
5.12GB) で， 保存形式・ 圧縮率の変更に よ る ビッ ト エラ ーも (論文の実験の範囲内では ) 最
大でも 15%未満と 小さ いこ と が確認さ れて いる 。 本研究ではこ の HiFP2.0 を 利用する 。
HiFP2.0 の詳細な ア ルゴ リ ズム を 図 2.5 と 図 2.6 に 示す。 図 2.5 は Harr ウ ェ ー ブ レ ッ
ト 変換を 用いた マ ルチレ ベルサブバン ド 分解 (MHWT) のア ルゴ リ ズム であ り ， 図 2.6 は
MHWT を 用いた HiFP 2.0 の全体の指紋生成ア ルゴ リ ズム であ る 。 HiFP2.0 の処理は大
ま かに MHWT と 特徴抽出に 分け ら れて おり ， 図 2.6 の 4 行目が MHWT， 8∼ 12 行目が特
徴抽出であ る 。
5
1: MHWT(wav[] ← 入力信号,
2:
n ← 入力信号のサン プル数,
3:
m ← 出力のサン プル数) {
4:
for (; n > m; n /= 2) do
5:
for (i = 0; i < n/2; i++) do
6:
Hi[i] ← (wav[2 × i] − wav[2 × i + 1])/2;
7:
Lo[i] ← (wav[2 × i] + wav[2 × i + 1])/2;
8:
end for
9:
wav[] ← Lo[];
10:
end for
11:
return (Hi, Lo);
12: }
図 2.5: Haar ウ ェ ーブレ ッ ト 変換を 用いた マ ルチレ ベルサブバン ド 分解ア ルゴ リ ズム
1: HiFP2.0(wav[] ← PCM データ ) {
2:
n ← PCM データ のサン プル数;
3:
m ← 出力のサン プル数;
4:
Hi[], Lo[] ← MHWT(wav[], n, m);
5:
j←0
6:
for (i = 0; i < m − 4; i += 4) do
7:
tmp ← Lo[i] − Lo[i + 4]
8:
if (tmp > 0) then
9:
F P ID[j] ← 1;
10:
else
11:
F P ID[j] ← 0;
12:
end if
13:
j++
14:
end for
15:
F P ID[m/4 − 1] ← 0;
16:
return F P ID;
17: }
図 2.6: 音楽指紋の生成ア ルゴ リ ズム (HiFP 2.0)
6
HiFP2.0 のア ルゴ リ ズム を 図解し た も のも 図 2.7 に 示す。 要する に HiFP2.0 は， 音楽
データ の先頭から 約 2.97 秒分を 取り ， 8 サン プ ルずつ 算術平均を 取っ て Lo 配列を 作り ，
Lo 配列を 3 つ飛ばし に 大小比較を する こ と で 4096 ビッ ト の FPID(指紋) を 生成する 。 な
お HiFP2.0 ではサン プリ ン グ周波数が 44.1kHz であ る こ と を 前提と し て お り ， 2.97 秒は
131,072 サン プルに 相当する 。 整数の加算， シフ ト 演算， 比較処理だけ で済むのでハード
ウ ェ ア 処理に 適し て いる 。
音声信号
65535
0
Lo
0.73ms
2.97s
平均
平均
平均
平均
平均
平均
平均
平均
平均
平均
平均
平均
平均
平均
21253
24536
34915
48102
48154
48319
48243
47056
36192
32053
32553
23183
26991
37921
FPID
＞
＞
0
1
・・・
4096ビット
0
最後に1ビットだけ’0’を追加
図 2.7: HiFP 2.0 の図解
音楽指紋の歪みは通常， そ れほど 大き く はな ら な い。 図 2.8 に ， 現実に 存在する 300 曲
の HiFP2.0 の指紋の歪みのヒ ス ト グラ ム を 示す。 最小 1， 平均 80， 最大 453 であっ た (最
大歪み率 11.1%)。 歪みは lame 3.99.5 と いう フ リ ーソ フ ト を 用いて 付加し た。 そ の時のコ
マ ン ド は以下の通り であ る 。 “-b 128” はビッ ト レ ート が 128kbps であ る こ と を 意味する 。
✓
✏
✒
✑
lame -b 128 --resample 44.1 オリ ジナルの WAV フ ァ イ ル MP3 フ ァ イ ル
lame --decode MP3 フ ァ イ ル 歪んだ WAV フ ァ イ ル
同様に ビッ ト レ ート を 192kbps に する と ， 最小 1， 平均 34， 最大 333 であり ， 最大歪み
率 8.1%であっ た。 ビッ ト レ ート が 256kbps だと ， 最小 0， 平均 18.3， 最大 164 であり ， 最
大歪み率 4.0%であ っ た 。
7
80
頻度(ヒストグラム)
60
40
20
0
0
100
200
300
400
500
ハミング距離
図 2.8: HiFP2.0 の歪みのヒ ス ト グラ ム
2.5
指紋検索
指紋を 生成し た ら “指紋検索” を する 。 こ れが本稿の主要テ ーマ であ る 。 指紋がど の音
楽由来な のかを 特定し ， 検索結果と し て 音楽 ID を 返す。 こ こ で音楽 ID と は， 指紋 DB に
登録済みの音楽ま た は指紋を 一意に 識別でき る 番号であ る 。
2.5.1
Yang の研究成果の概要
指紋検索に 関し て は Yang の研究が組込みシス テム 向け である 。 と いう のも 指紋の生成
に は HiFP 2.0 を 用いて おり ， かつ音楽指紋検索シス テム を FPGA に 実装し て いる から で
ある 。 Yang は文献 [4] に て ， ハミ ン グ距離を 計算する ハード ウ ェ ア ア ク セ ラ レ ータ を 開発
し ， 局所性鋭敏型ハッ シュ (Locality Sensitive Hashing; LSH) を 用いた ハッ シュ 探索を 改
良し た 。
2.5.2
ハミ ン グ距離のハード ウ ェ ア ア ク セラ レ ータ
Yang に よ る 成果の 1 つはハミ ン グ距離を 計算する ア ク セ ラ レ ータ である 。 こ れは図 2.9
のよ う な ハード ウ ェ ア であり ， 指紋を 32 ビッ ト ずつ入力する と ， 1∼ 6 段目で 32 ビッ ト の
ハミ ン グ距離を 計算し ， 7 段目でそ れま で計算し たハミ ン グ距離を 累積する 。 パイ プラ イ
ン 化し て いる ので， 計算時間は表 2.1 のよ う に 短い。
8
1段目 2段目 3段目 4段目 5段目 6段目 7段目
入力データ1
(32ビット)
出力データ
(初期値:0)
入力データ2
(32ビット)
排他的論理和
加算
図 2.9: ハミ ン グ距離を 計算する ハード ウ ェ ア
表 2.1: ハミ ン グ距離の計算時間
入力ビッ ト 数
32
64
96
..
.
4196
所要ク ロ ッ ク 数
7
8
9
..
.
134
9
2.5.3
Staged LSH と そ の検索ア ルゴリ ズム
Yang に よ る も う 1 つの成果は Staged LSH であ る 。 こ れは LSH を 用いた ハッ シュ 探索
の改良版であ る 。 4096 ビッ ト の指紋のハミ ン グ距離を いき な り 計算せず， ま ずはも っ と
少な いビッ ト 数のハミ ン グ距離を 計算し て ス ク リ ーニン グ処理する 方法であり ， 比較処理
の回数を 減ら すこ と に よ り 検索を 高速化する 。
検索全体のア ルゴリ ズム は図 2.10 の通り である 。 6 行目の “ス ク リ ーニン グ ”， 8 行目の
“精査” に ついて は， Yang の文献 [4] ではそ れぞれ “coarse search”， “exact search” と 表記
さ れて いる 。 以降では， こ のア ルゴ リ ズム に ついて 詳し く 説明する 。
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
for フ レ ーム t ∈ ク エリ 指紋 Q do
ハッ シュ 値 ← ハッ シュ 関数で t を 処理
for エン ト リ i ∈ ハッ シュ テ ーブル
if ハッ シュ 値 == i.ハッ シュ 値 then
for j ∈ i.フ レ ーム リ ス ト do
if ス ク リ ーニン グ (t, j) ≤ 閾値 1 then
P ← j の元と な る 指紋
if 精査 (P, Q) ≤ 閾値 2 かつ P < BestM atch then
BestM atch ← P
end if
end if
end for
return BestM atch
end if
end for
end for
return “一致な し ”
図 2.10: Staged LSH のア ルゴ リ ズム
ア ルゴ リ ズム の内容に 入る 前に “フ レ ーム ” に ついて 説明する 。 Yang は図 2.11 のよ う
に 4096 ビッ ト の指紋を 32 ビッ ト ずつ 128 個の “サブ指紋” と し て 区切り ， 3 つの連続し た
サブ指紋を フ レ ーム と 呼んでいる 。 1 つの指紋に は 126 フ レ ーム あ る 。
指紋
4096ビット
サブ指紋0
32ビット
サブ指紋1
32ビット
サブ指紋2
32ビット
サブ指紋3
32ビット
0x87E5291D
0x481D620F
0x3A1580E3
0x59BE109F
サブ指紋127
32ビット
・・・・・・
0x357AD20
96ビット
フレーム0
96ビット
フレーム1
96ビット
フレーム2
図 2.11: 指紋と サブ指紋と フ レ ーム
10
96ビット
フレーム125
Staged LSH の検索ア ルゴ リ ズム に は大き く ハッ シュ 探索， ス ク リ ーニン グ， 精査の 3
つの段階がある 。 図 2.12 のよ う に こ の 3 つの段階を 通し て 徐々 に 指紋 DB の探索範囲を 狭
めて いく 。
指紋DB
指紋0
指紋1
指紋2
指紋3
指紋4
ハッシュ探索
指紋0
指紋5
指紋251
クエリ指紋
スクリーニング
指紋5
指紋9,999,999
探索範囲：大
(計算量:小)
指紋4895
指紋32154
(計算量:中)
指紋8514
精査
検索結果
・・・・・・
探索範囲：小
(計算量:大)
指紋5
図 2.12: Staged LSH で徐々 に 指紋 DB の探索範囲を 狭めて いく 様子
ハッ シ ュ 探索
Staged LSH の最初の段階はハッ シュ 探索であ る 。 ハッ シュ 探索は他の多く の音楽指紋
検索の研究でも 採用さ れて おり ， 線形探索や二分探索な ど と 比べて 次の特徴を 持つ。
• 長所: DB のサイ ズに よ ら ず計算量が一定であ る 。
• 短所: ハッ シュ テ ーブルの格納に メ モリ 容量が必要であ る 。
(図 2.14 のデータ 形式では千万曲で約 5GB)
• 短所: ハッ シュ 値の衝突発生時の対応が必要であ る 。
Staged LSH で用いる ハッ シュ 関数は， 図 2.13 のよ う に 96 ビッ ト のフ レ ーム を 入力する
と ， 13 ビッ ト のハッ シュ 値を 出力する 局所性鋭敏型ハッ シュ (Locality Sensitive Hashing;
LSH) であ る 。 LSH はビッ ト 位置の交換だけ であ る から ， ハード ウ ェ ア 処理ではわずか 1
ク ロ ッ ク でハッ シュ 値を 出力でき る 点が強みである 。 ハッ シュ 探索は， こ のハッ シュ 値が
同じ に な る 指紋だけ を 指紋 DB から 選び取る 処理であり ， 例え ば図 2.14 のよ う な ハッ シュ
テーブルを 用いる と 処理が即座に 完了する 。 ハッ シュ 値の衝突発生時は， 同じ ハッ シュ 値
に な る フ レ ーム を リ ス ト に ま と めて おき ， 検索時に そ のリ ス ト 内のフ レ ーム を 全て 次段階
のス ク リ ーニン グに 渡す。
11
入力:96ビット
11010110100101011000111011010100
11110000000010100100111111101001
10111111100000100101011010110111
1011011011101
出力:13ビット
図 2.13: 局所性鋭敏型ハッ シュ の生成方法
ハッシュテーブル
のメタデータ
ハッシュ値0x0000
のフレームリスト
ハッシュ値0x0001
のフレームリスト
ハッシュ値0x1FFF
のフレームリスト
ハッシュテーブル
指紋DB
32ビット
32ビット
ハッシュ値0x0000のフレームリストの最終アドレス
ハッシュ値0x0001のフレームリストの最終アドレス
:
:
ハッシュ値0x1FFFのフレームリストの最終アドレス
ハッシュ値0x0000の1番目のフレームの先頭アドレス
ハッシュ値0x0000の2番目のフレームの先頭アドレス
:
:
ハッシュ値0x0000の最後のフレームの先頭アドレス
ハッシュ値0x0001の1番目のフレームの先頭アドレス
ハッシュ値0x0001の2番目のフレームの先頭アドレス
:
:
ハッシュ値0x0001の最後のフレームの先頭アドレス
:
:
ハッシュ値0x1FFFの1番目のフレームの先頭アドレス
ハッシュ値0x1FFFの2番目のフレームの先頭アドレス
:
:
ハッシュ値0x1FFFの最後のフレームの先頭アドレス
音楽0の指紋 (4096ビット)
音楽1の指紋 (4096ビット)
:
:
音楽9,999,999の指紋 (4096ビット)
図 2.14: ハッ シュ テ ーブルと 指紋 DB のデータ 構造
ス ク リ ーニン グ (coarse search)
ハッ シュ 探索の次はス ク リ ーニン グである 。 ス ク リ ーニン グも 精査も ハミ ン グ距離に 基
づいて 正解の指紋を 探し 当て る が， ハッ シュ 探索完了時点ではま だ多数の候補が残る こ と
がある 。 そ こ で， いき な り 4096 ビッ ト 同士のハミ ン グ距離を 計算せず， ま ずは 96 ビッ ト
のフ レ ーム だけ でハミ ン グ距離を 計算し ， 一定の閾値以上の指紋を ふる い落と す。 こ れが
Staged LSH の最大の特徴のス ク リ ーニン グであ る 。
12
精査 (exact search)
精査ではスク リ ーニン グでふる い落と さ れな かっ た指紋のみ， 4096 ビッ ト のハミ ン グ距
離を 計算し ， 閾値以下でかつ最小の指紋を 検索結果と し て 返す。 検索結果を 返せな かっ た
場合は， ク エリ 指紋の次のフ レ ーム に ついて ハッ シュ 探索から やり 直す。 さ ら に ク エリ の
最終フ レ ーム でも 検索結果を 返せな かっ た場合は “一致な し ” を 返す。 以上が Staged LSH
のア ルゴ リ ズム であ る 。
2.5.4
Staged LSH の問題点
Staged LSH はハッ シュ 探索と ス ク リ ーニン グのお かげで高速な 検索が可能であ る が，
こ の方法でも ハッ シュ テ ーブ ルのサイ ズが大き い点は他の先行研究と 同様であ る 。 ハッ
シュ テ ーブルの構造を 図 2.14 に 示し た が， こ れに は全フ レ ーム のア ド レ ス が格納さ れて
いる 。 そ のせいでハッ シュ テーブルは指紋 DB と 同程度のサイ ズに な る 。 例え ば千万曲だ
と ， ハッ シュ 値のビッ ト 数を L0 = 13 と し て
指紋 DB のサイ ズ = 10, 000, 000 × 4096 ÷ 8 = 5.12GB
ハッ シュ テ ーブルのサイ ズ = 2
L0
(2.1)
× 4 + 10, 000, 000 × 126 × 4 = 5.04GB (2.2)
と な る 。 Yang の評価実験は 300 曲ま でに と ど ま っ て いる が， こ れら のデータ を 格納する
メ モリ を 確保する のが難し かっ たから だと 思われる 。 いずれに せよ サポート 対象の曲数を
将来的に 例え ば一億曲ま で拡大し よ う と する と ， 指紋 DB と ハッ シュ テ ーブルで 100GB
以上必要に な る 。 こ れは組込みシス テ ム と し て も DRAM だけ で対応する のはふさ わし く
な い。 低速ではあ る が Solid State Drive(SSD) や Storage Class Memory(SCM) の使用を
検討する べき であ る 。
ま た， ハッ シュ 探索はハッ シュ 値に 誤り がある と 探索が失敗する と いう 問題がある 。 ク
エリ の先頭フ レ ーム でハッ シュ 探索に 失敗し て も ， も し 2 フ レ ーム 目や 3 フ レ ーム 目で
ハッ シュ 探索に 成功し ， ス ク リ ーニン グ， 精査も 成功すれば， 全体と し て は検索成功と な
る 。 し かし そ れだ け 検索時間が長引く し ， 実際に Yang の論文 [4] でも 指紋に 歪みがあ る
と 検索時間が長く な る と いう 実験結果が出て いる 。
2.6
ラ イ セン ス・ 課金情報の送信
指紋の検索結果 (音楽 ID) を 得た後は， “ラ イ セ ン ス・ 課金情報の送信” を する 。 こ れは
音楽 ID に 対応する 音楽のラ イ セ ン ス・ 課金情報を ， 音楽のダウ ン ロ ード 先へ送信する 処
理である 。 ラ イ セ ン ス・ 課金情報を 送信する ための通信のプロ ト コ ルは， 通信の信頼性や
セ キュ リ ティ な ど も 考慮の上で決定ま たは作成する 必要がある 。 ま たは本処理を “関連パ
ケ ッ ト を 遮断” や “管理会社に 報告” に 変更・ 拡張する こ と も 考え ら れる 。 し かし 大部分
はプロ ト コ ルや運用方法のポリ シーの問題であ り 技術的に 困難な 問題ではな い。
13
2.7
まとめ
本章では音楽指紋と そ の関連研究に ついて 述べた。 ネ ッ ト ワ ーク 機器内の音楽検索シス
テム を 実現する に は大き く 分け て 5 つの処理を 考え る 必要がある 。 そ の中でも 指紋生成の
HiFP 2.0 と 指紋検索の Staged LSH に ついて は詳し く 説明し た。 本研究の対象は 5 つの処
理工程の中でも 指紋検索の部分であり ， そ の重要な 課題の 1 つが大規模 DB 化， も う 1 つ
の課題が高速化と 高精度化の両立であ る 。
14
第 3 章 階層化 Staged LSH によ る 大規
模音楽指紋検索シ ス テム の実装
3.1
組込みシ ステムと し て の音楽指紋検索
本研究では FPGA で音楽を 検索する 。 と いう のも ， 本研究で実現し たいアプリ ケ ーショ
ン は， 図 3.1 のよ う な ネ ッ ト ワ ーク 機器内での音楽検索を 必要と する 。 すな わち 組込みシ
ス テ ム であ り ， 以下のよ う な 要求が想定さ れる た めであ る 。
• 小型化・ 軽量化
• 計算リ ソ ース ・ 金銭的コ ス ト の削減
• 低消費電力化
ネ ッ ト ワ ーク 機器内に 組み込める のは， ス ーパーコ ン ピュ ータ や高性能のサーバ機器では
な く ， マ イ コ ン ， ASIC， FPGA な ど であ る 。 そ の中でも 本研究で FPGA を 選ん だ のは，
上述の要求を 満た し つつ高性能化を 狙え ， し かも 繰り 返し 実機で検証でき る た めであ る 。
ポート6
プロセッサ
ポート5
パケットバッファメモリ
ポート4
ルーティングテーブル
ポート3
指紋DB等
のメモリ
ポート2
FPGA
ポート1
音楽検索システム
ISPのルータ
図 3.1: ネ ッ ト ワ ーク 機器内での音楽指紋検索
15
FPGA と は図 3.2 のよ う な 構造を 持つプロ グラ マ ブルデバイ スである 。 内蔵 SRAM に格
納さ れて いる 回路情報を も と に LUT や SM の結線を し て 動作する 。 集積回路ではある が，
エン ド ユーザでも 容易に 回路を 変更し て 実機で動作さ せる こ と ができ る 。 手順は， ま ずデ
ジタ ル回路を Verilog HDL や VHDL な ど のハード ウ ェ ア 記述言語で設計し ， Xilinx 社や
Altera 社な ど の FPGA ベン ダが提供し て いる ツ ールで “論理合成”， “配置＆ 配線”， “ビッ
ト ス ト リ ーム 生成” を 行い， そ の出力フ ァ イ ルを USB な ど で JTAG を 経由し て SRAM へ
転送すれば良い。
SM
SM
CLB
SM
SM
CLB
SM
SM
CLB
SM
SM
CLB
SM
SM
入力
CLB
SM
CLB
SM
CLB
SM
CLB
SM
出力
LUT
SM
FF
Clock
Reset
SM : Switch Matrix
CLB : Configurable Logic Block
LUT : Lookup Table
FF : Flip-Flop
図 3.2: FPGA の基本的な 構造の例
検索時間の目標に ついて も 検討する 。 望ま し いのは， ネ ッ ト ワ ーク 機器内でリ ア ルタ イ
ム 処理でき る こ と である 。 こ れは， も し 音楽の通信が同時に 多数発生し て も ， 後続の音楽
の検索を 遅延さ せな いためである 。 最近のネ ッ ト ワ ーク 機器 (有線) は 10Mbps∼ 100Gbps
の通信速度を サポート し て おり ， 400Gbps も 仕様策定が進めら れて いる 。 音楽データ のサ
イ ズは， 保存形式・ 圧縮率に も よ る が典型的に は 1 分あたり 1∼ 2MB である 。 そ こ で， 例
え ば 1MB の音楽データ が 1Gbps のネッ ト ワ ーク 機器を 通過する ま での時間を 計算する と ，
8 × (1 × 106 )
転送時間 =
秒 = 8ミ リ 秒
1 × 109
(3.1)
である 。 すな わち こ の数値例では 1 曲の検索を 8 ミ リ 秒以内に 抑え る 必要がある 。 本研究
で使う FPGA ボード では 200MHz ある いは 250MHz のク ロ ッ ク が利用可能である から ， 8
ミ リ 秒はそ れぞれ 1.6 × 106 ク ロ ッ ク， 2 × 106 ク ロ ッ ク に 相当する 。
16
3.2
階層化 Staged LSH によ る 大規模指紋 DB の検索の高
速化
Staged LSH の課題の 1 つは， 指紋 DB と ハッ シュ テーブルのサイ ズが大き いこ と であっ
た。 し かし ， だから と 言っ て HDD や SSD を 使う と データ 転送速度に 限界がある し ， 今後
別種類の二次記憶装置が登場する 可能性も ある 。 そこ で本研究では高速・ 小容量の DRAM
に 加え て ， PCIe でア ク セ ス 可能な 低速・ 大容量な メ モリ を 別途用意する こ と に し た 。
通常， コ ン ピ ュ ータ シス テム の記憶装置 (例:一次キャッ シュ， 二次キャッ シュ， DRAM，
SSD， HDD な ど ) は， 価格が同じ であ れば， 高速な も のほど 記憶容量が小さ い。 例え ば
DRAM の高速性 (例:10GB/s) と HDD の大容量性 (例:1TB) を 兼ね備え た 記憶装置を ， 特
に 組込み用途向け に 用意する のは現時点では難し い。 こ のよ う な 場合は， 頻繁に ア ク セ ス
する データ を 高速メ モリ に ， そ う でな いデータ を 大容量メ モリ に そ れぞれ格納し ， 平均的
な 転送速度の向上を 狙う のが一般的であ る 。
Yang の研究は FPGA のブロ ッ ク RAM と 外部の DRAM し か想定し て いな いので， こ
れ以上メ モリ を 追加する と Yang の実装を そ のま ま 実行でき な く な る 。 素朴な 拡張方法は，
図 3.3(a) のよ う に ハッ シュ テーブルの先頭から 一部を 高速メ モリ に ， ハッ シュ テーブルの
残り と 指紋 DB を 大容量メ モリ に 格納する こ と であ る 。
高速メモリ
(4GiB)
高速メモリ
(4GiB)
ハッシュテーブル
(千万曲，約5GiB)
高頻度指紋の
ハッシュテーブル
(400万曲，約2GiB)
高頻度指紋の
指紋DB
(400万曲，約2GiB)
低頻度指紋の
ハッシュテーブル
(600万曲，約3GiB)
大容量メモリ
(28GiB)
指紋DB
(千万曲，約5GiB)
大容量メモリ
(28GiB)
デバッグ領域
低頻度指紋の
指紋DB
(600万曲，約3GiB)
デバッグ領域
(b) 階層化 Staged LSH
(a) Yang の手法の単純拡張
図 3.3: 指紋 DB と ハッ シュ テ ーブルのメ モリ 格納方法
し かし ， こ れだと ど の指紋を 検索する 際も 必ず大容量メ モリ に アク セス し な け ればな ら
な い。 そ こ で， 現実に は人気の音楽や流行の音楽があり ， イ ン タ ーネ ッ ト 上を 通信する 音
楽に 偏り があ る こ と を 踏ま え ， 図 3.3(b) のよ う に データ を 格納し ， 高頻度で検索要求さ
れる 指紋を 高速メ モリ だけ で検索完了可能に する ために 図 3.4 のフ ロ ーチャ ート の方法を
採用し た 。 こ れが階層化 Staged LSH であ る 。 こ こ で “高頻度指紋” と は人気があ り 検索
要求さ れやすい音楽の指紋の集合であ り ， “低頻度指紋” と はそ れ以外の音楽の指紋の集
17
合であ る 。
検索時間は付録 A.3 よ り ， 指紋 DB のサイ ズ NDB お よ び 32 ビッ ト あ た り のメ モリ ア
ク セ ス 時間 T に ほぼ正比例する 。 NDB の増大は回避不能と し て ， 人気の音楽や流行の音
楽に 関し て T を 削減する こ と で， 平均的な 検索時間を 短縮する と いう 狙いであ る 。
開始
高速メモリでStaged LSH
Yes
検索結果を返した
No
低速メモリでStaged LSH
終了
図 3.4: 階層化 Staged LSH のア ルゴ リ ズム (フ ロ ーチャ ート )
3.3
隣接 LSH 探索によ る 高速化・ 高精度化のト レ ード オ フ
の調整
指紋の歪みに よ り ハッ シュ 値が 1 ビッ ト でも 変化する と ， 基本的に はハッ シュ 探索は失
敗する 。 し かし LSH では歪みが小さ け ればハッ シュ 値が変化し な いこ と があ り ， そ の場
合ハッ シュ 探索は成功する 。
LSH のハッ シュ 探索の成功確率は， ハッ シュ 値が衝突し な い確率と ト レ ード オフ の関
係に ある 。 いま 指紋の各ビッ ト が 0 と 1 である 確率はど ち ら も 1/2 である と し ， 指紋の歪
み率 (ビッ ト エラ ーの発生確率) を pber と する と ， ハッ シュ 値が L0 ビッ ト であ れば，
ハッ シュ 探索の成功確率 = (1 − pber )L0
(3.2)
1
(3.3)
2 L0
と な る 。 すな わち L0 を 小さ く すればハッ シュ 探索は成功し やすく な る が， ハッ シュ 値も
衝突し やすく な る 。 衝突が発生する と 線形探索する 対象が多く な る ので検索速度の低下に
つな がる 。 かと 言っ て L0 を 大き く する と ハッ シュ 探索が失敗し やすく な り ， 精度が低下
する 。
そ こ で検索速度と 精度の両立のため， ハミ ン グ距離的に 隣接する ハッ シュ 値である “隣
接ハッ シュ ”(図 3.5) も 探索対象に 含める “隣接 LSH 探索” 手法を 提案する 。 こ れは概念的
ハッ シュ 値の衝突確率 =
18
に は図 3.6 のよ う な ア イ デア であ り ， ハッ シュ 値のビッ ト 数 L0 を 増やし て 衝突確率を 下
げな がら ， 隣接ハッ シュ を 探索する こ と でハッ シュ 探索の成功確率を 上げる 。
付録 A.2 では， 指紋の各ビッ ト の誤り 率が一定以下であ る と 仮定し ， ハッ シュ 値を 何
ビッ ト に し て 何隣接ハッ シュ ま でを 探索する べき かを 確率計算に よ り 考察し た 。 結果は，
20 ビッ ト ， 1 隣接であ る 。
2隣接ハッシュ0 0 1 1 0 1 1 1 1 1 0 0 0 1
1隣接ハッシュ0 0 1 1 0 1 1 1 1 1 0 0 1 1
2隣接ハッシュ1 0 1 1 0 1 1 1 1 1 0 1 1 1
1隣接ハッシュ1 0 1 1 0 1 1 1 1 1 0 0 0 0
元データ 0 1 1 0 1 1 1 1 1 0 0 1 0
2隣接ハッシュ2 0 1 1 0 1 1 1 1 1 0 1 0 0
1隣接ハッシュ2 0 1 1 0 1 1 1 1 1 0 1 1 0
:
:
:
:
:
:
1隣接ハッシュ12 1 1 1 0 1 1 1 1 1 0 0 1 0
2隣接ハッシュ77 1 0 1 0 1 1 1 1 1 0 0 1 0
図 3.5: 隣接ハッ シュ の例
クエリから生成
したハッシュ値
探索対象（太線）
正解のハッシュ値
00
01
10
11
探索範囲を狭めることで、探索にかかる時間を短くする
クエリから生成
したハッシュ値
0000 0001 0011 0010
正解のハッシュ値
0100 0101 0111 0110
探索対象（太線）
1100 1101 1111 1110
1000 1001 1011 1010
探索範囲を隣まで広げることで、探索の成功確率を上げる
クエリから生成
したハッシュ値
0000 0001 0011 0010
正解のハッシュ値
0100 0101 0111 0110
探索対象（太線）
1100 1101 1111 1110
1000 1001 1011 1010
図 3.6: 隣接 LSH 探索のア イ デア
19
3.4
提案シ ステムの実装
図 3.7 に本研究の音楽指紋検索システム の内部構成図を ， 表 3.1 に構成図中の各モジュ ー
ルの説明を ， そ れぞれ示す。 提案手法では， 階層化 Staged LSH と 隣接 LSH 探索の両方を
“Staged LSH” のブロ ッ ク に機能追加する 。 “デバッ グ用” で囲んだ信号線は Ethernet(MII)
ま た は PCIe のイ ン タ フ ェ ース を 制御する モジュ ールと 接続し て おり ， 外部のパソ コ ン が
検索開始指示を 出し 検索結果を 受け 取る ために 使用し た。 Ethernet や PCIe は一般的な メ
モリ 用のイ ン タ フ ェ ース ではな いが， FPGA から はメ モリ 制御モジュ ールの特定ア ド レ
ス に データ を 読み書き する こ と でこ れら のイ ン タ フ ェ ース を 制御可能と し た 。
FPGAボード
指紋検索
パソコン
メモリ制御
アドレス
データ
Staged LSH
MIG制御
高速メモリ
検索開始
PCIe制御
または
MII制御
DDR4
内部バス
検索結果
BRAM
大容量メモリ
PCI Express
または
Ethernet
制御信号
クエリ指紋
デバッグ用
図 3.7: 音楽指紋検索のシス テ ム と 内部モジュ ールの構成図
表 3.1: 音楽指紋検索シス テ ム の内部モジュ ール一覧
モジュ ール名
指紋検索
Staged LSH
BRAM
メ モリ 制御
MIG 制御
PCIe 制御
ま たは MII 制御
説明
ク エリ 指紋を 受け 取り 検索結果を 返す。
Staged LSH 手法に よ り ク エリ 指紋を 検索する 。
提案手法では隣接 LSH 探索も 含む。
ク エリ 指紋や一時データ を 格納する 。
DDR3 の高速メ モリ を 64 ビッ ト ア ド レ ス に 一元的に マ ッ ピ ン グする 。
DDR3 経由で FPGA ボード 内蔵の DRAM(高速メ モリ ) のデータ を 読み
出す。 Xilinx のラ イ ブラ リ を 含む。
PCIe ま たは Ethernet 経由でパソ コ ン から 指紋 DB・ ハッ シュ テーブル・
ク エリ 指紋， そ し て 検索開始指示を 受け 取る 。 検索完了後は結果を 返す。
こ の構成図に おいて 指紋を 検索する のは FPGA であ る 。 デス ク ト ッ プ PC は， CPU を
用いて 指紋検索さ せる こ と はな く ， 基本的に はデバッ グと 大容量メ モリ と し て のみ使用す
る 。 よ り 正確に は次の 3 つの用途であ る 。
20
• FPGA へ検索開始を 指示する
• FPGA から 検索結果を 受け 取り ， 画面に 表示する
• FPGA へ指紋 DB な ど を 転送する (検索前＆ 検索中)
3.5
まとめ
Yang の Staged LSH は音楽検索のハード ウ ェ ア 化と 高速化に おいて 優れた 方法であ る
が， 実際に 実装する と 大容量のメ モリ が必要であ り ， そ のま ま では千万曲規模の音楽 DB
に は適さ な かっ た 。 そ こ で高速・ 小容量の DRAM に 加え て 低速・ 大容量の DRAM を 用
意する こ と で， 千万曲分の指紋 DB と ハッ シュ テ ーブルを 用いた 検索を 実現する と と も
に ， 高精度の音楽に 関する データ を 高速・ 小容量の DRAM に 格納する こ と で平均的な 検
索速度の向上を 図っ た。 併せて 検索速度と 検索精度の両立と いう 課題に 対応する ため， 隣
接ハッ シュ ま で探索対象を 広げる 隣接 LSH 探索を 考案し ， よ り 柔軟に 検索速度と 検索精
度を 調整可能に し た。 そ し て 階層化 Staged LSH と 隣接 LSH 探索も 含めた Staged LSH を
FPGA に 実装し ， 音楽指紋検索シス テ ム を 開発し た 。
21
第 4 章 評価実験
提案手法であ る 階層化 Staged LSH と 隣接 LSH 探索を 評価する た めの実験を 行う 。
4.1
現実の音楽から 生成し た指紋 DB での評価
ま ずは現実の音楽から 生成し た指紋を 用いて ， 実装し た音楽指紋検索シス テム の， 特に
隣接 LSH 探索に よ る 検索速度と 検索精度への影響を 評価する 。 こ の評価では， 音楽指紋
DB のサイ ズは 300 曲ま でであ り ， 複数メ モリ を 用いた 実験も 実施し な い。
4.1.1
開発環境と 実験環境
FPGA の開発環境を 表 4.1 に ま と める 。 回路合成から ビッ ト ス ト リ ーム 生成ま で通常は
数十分以上かかる ため， 高性能のサーバを 使用する こ と でビルド 時間を 短縮し た。 開発用
ツ ールおよ びラ イ ブラ リ は， 現時点で最新のも のを 使用し た 。
表 4.1: FPGA の開発環境
項目
CPU
メ モリ
ス ト レ ージ
OS
カ ーネ ル
開発ツ ール
MIG ラ イ ブラ リ
説明
AMD Opteron(TM) Processor 6238 (48 コ ア )
DDR3 SDRAM 271GB
ST320DM000-1BC14C (SATA 3.0, 320GB)
Scientific Linux 6.1
2.6.32-504.30.3.el6 (64 ビッ ト 版)
ISE Design Suite 14.7
Memory Interface Generator 3.92
表 4.2 に ， 実験に 用いた FPGA ボード の特徴を 簡単に 示す。 こ れら の機材は市販のも の
を そ のま ま 使用し て おり ， 未改造の状態であ る 。
22
表 4.2: FPGA ボード の特徴
項目
製品名
FPGA
クロッ ク
搭載メ モリ
4.1.2
説明
R
Xilinx 社 Virtex-6
FPGA ML605 評価キ ッ ト
Virtex-6 XC6VLX240T-1FFG1156
200MHz (MIG ラ イ ブラ リ が出力)
DDR3 SO-DIMM， 512MB
隣接 LSH 探索の評価
実験パラ メ ータ
実験条件・ 実験パラ メ ータ は表 4.3 の通り である 。 ハッ シュ 値のビッ ト 数 L0 と 隣接 LSH
探索のハミ ン グ半径 rn に ついて は， Yang の手法は文献 [4] のも のであ り ， 提案手法は付
録 A.2 で求めた 最適値であ る 。 Yang の手法のス ク リ ーニン グと 精査の閾値は文献 [4] の
5.2.2 節を 参考に し て ， 25%ま での歪み率を 想定し て 決定し た 。
表 4.3: 隣接 LSH 探索の評価実験の条件
項目
試行回数
ク エリ 指紋の歪み率 pber
ス ク リ ーニン グの閾値 ε1
精査の閾値 ε2
ハッ シュ のビッ ト 数 L0
隣接 LSH 探索のハミ ン グ距離 rn
Yang の手法 提案手法
300
300
0∼ 0.5
0∼ 0.5
24
24
1024
1024
13
20
0
0
な お指紋の元と な っ た 音楽は Yang と 同じ も のであ り ， 300 曲を 指紋 DB 化し た 。 ク エ
リ 指紋の歪み (ビッ ト 誤り ) に ついて も ， Yang と 同様に 乱数で機械的に 付与し た 。
検索速度
現実の音楽データ でま ずは検索速度を 評価する 。 Yang が用いた 300 曲から HiFP2.0 で
指紋 DB と ハッ シュ テーブルを 構築し ， メ モリ に 全データ を 格納する 。 そ の後ク エリ 指紋
と し て ， 300 曲の指紋に ラ ン ダム に 歪みを 付与し たも のを 検索シス テム に 入力し ， 検索時
間を 測定する 。
表 4.4， 図 4.1 が実験結果である 。 提案手法の方が平均検索速度に おいて 約 6.3 倍高速で
あっ た。
23
表 4.4: Yang の手法と 隣接 LSH 探索の検索時間
歪み率
0.00
0.05
0.10
0.15
0.20
0.25
0.30
0.35
0.40
0.45
0.50
5
Yang の手法の
検索時間 (ク ロ ッ ク 数)
3,459
6,495
12,850
26,838
64,244
324,776
410,223
403,908
403,561
403,553
403,553
提案手法の
検索時間 (ク ロ ッ ク 数)
781
970
1,597
3,259
8,610
75,706
71,466
66,413
66,211
66,208
66,208
Yangの手法(理論値)
提案手法(理論値)
Yangの手法(実験値)
提案手法(実験値)
検索時間 (メガクロック数)
4
3
2
1
0
0
0.1
0.2
0.3
0.4
0.5
歪み率 pber
図 4.1: 歪み率と 平均検索時間
検索精度
検索精度に ついて は図 4.2 の通り Yang の手法も 隣接 LSH 探索も 同程度であっ た。 な お
不正解指紋を 返し た 件数 (“一致な し ” ではな く 別の指紋を 誤っ て 返し た 件数) は 0 であ っ
た た め， 図表に は正答率のみを 記載し た 。
24
表 4.5: Yang の手法と 隣接 LSH 探索の検索精度
歪み率
0.00
0.05
0.10
0.15
0.20
0.25
0.30
0.35
0.40
0.45
0.50
Yang の手法の
正答率
1.00
1.00
1.00
1.00
0.41
0.00
0.00
0.00
0.00
0.00
0.00
提案手法の
正答率
1.00
1.00
1.00
1.00
0.42
0.00
0.00
0.00
0.00
0.00
0.00
1
0.8
正答率
0.6
0.4
0.2
Yangの手法(理論値)
提案手法(理論値)
Yangの手法(実験値)
提案手法(実験値)
0
0
0.1
0.2
0.3
歪み率 pber
図 4.2: 歪み率と 検索精度
25
0.4
0.5
4.1.3
リ ソ ース使用量
実装し た 指紋検索モジュ ール (Staged LSH モジュ ール ) のリ ソ ース 使用量は表 4.6 の通
り であ る 。 隣接 LSH 探索を 追加実装し て も 最大で約 1.5%の増加であ っ た 。
表 4.6: 実装し た 指紋検索モジュ ール (Staged LSH モジュ ール ) のリ ソ ース 使用量
Number
Number
Number
Number
Number
4.2
of
of
of
of
of
項目
Slice Registers
Slice LUTs
fully used LUT-FF pairs
bounded IOB
BUFG/BUFGCTRLs
従来手法
467
2206
329
115
1
提案手法
471
2235
334
115
1
千万曲分の乱数指紋 DB での評価
今度は千万曲分の指紋 DB を 乱数で生成し て 提案手法の評価を 行う 。 指紋 DB が 300 曲
の時よ り も 検索時間が長く な る こ と が予想さ れる ので， ネ ッ ト ワ ーク 機器のデータ 転送速
度に ど こ ま で追いつけ る かを 調べる と と も に ， 階層化 Staged LSH お よ び隣接 LSH 探索
に よ る 検索速度の向上や精度への悪影響の程度を 見る 。
4.2.1
開発環境と 実験環境
FPGA の開発環境を 表 4.7 にま と める 。 開発ツ ールが ISE Design Suite 14.7 から Vivado
2015.2 へ変更し た こ と 以外は前節と 同様であ る 。
表 4.8， 表 4.9 に ， 実験に 用いた FPGA ボード と デス ク ト ッ プ PC の特徴を そ れぞれ簡
単に 示す。 こ れら の機材は市販のも のを そ のま ま 使用し て おり ， 改造な ど はし て いな い。
な お FPGA ボード に は 4GB のメ モリ が 2 つある が， 実験内容を 単純に する ため片方のみ
使用し た。 デス ク ト ッ プ PC に ついて はメ モリ と PCIe の速度に 特化し たも のを 購入し た。
4.2.2
階層化 Staged LSH の評価
階層化 Staged LSH 単独の評価を 行う 。 こ のた めに 隣接 LSH 探索を 無効化する 。 千万
曲分の指紋 DB を 乱数で生成し ， そ れを 元に ハッ シュ テーブルを 構築する 。 ク エリ 指紋に
ついて は各指紋が検索要求さ れる 頻度は Zipf 則に 従う と し ， 一定の試行回数だ け 検索シ
ス テ ム に 入力し て 平均検索時間と 精度を 測定する 。 そ の他の実験条件は表 4.10 の通り で
ある 。
26
表 4.7: FPGA の開発環境
項目
CPU
メ モリ
ス ト レ ージ
OS
カ ーネ ル
開発ツ ール
MIG ラ イ ブラ リ
PCIe ラ イ ブラ リ
説明
AMD Opteron(TM) Processor 6238 (48 コ ア )
DDR3 SDRAM 271GB
ST320DM000-1BC14C (SATA 3.0, 320GB)
Scientific Linux 6.1
2.6.32-504.30.3.el6 (64 ビッ ト 版)
Vivado 2015.2
Memory Interface Generator 7 Series
Version 2.3 (Rev. 2)
Virtex-7 FPGA Gen3 Integrated Block for PCI Express
Version 4.0 (Rev. 1)
表 4.8: FPGA ボード の特徴
項目
製品名
FPGA
クロッ ク
搭載メ モリ
PCIe
説明
R
Xilinx 社 Virtex-7
FPGA VC709 コ ネ ク テ ィ ビテ ィ キ ッ ト
Virtex-7 XC7VX690T-2FFG1761C
250MHz (PCIe ラ イ ブラ リ が出力)
DDR3 SO-DIMM， 2 個， 各 4GB， 理論性能は 10.4GB/s
PCI Express 3.0 x8， 理論性能は 6.8GB/s
表 4.9: デス ク ト ッ プ PC の仕様
項目
CPU
メ モリ
ス ト レ ージ
I/O
OS
カ ーネ ル
説明
R
R
IntelXeon
CPU
E5-1620 v3 (4 コ ア )
DDR4 33.6GB (実験では 28GiB 使用)
DT01ACA050 (SATA 3.0, 500GB)
PCI Express 3.0 x8 な ど
Ubuntu 14.04.2 Long Term Support
3.16.0-45-generic (64 ビッ ト 版)
27
表 4.10: 階層化 Staged LSH の評価実験の条件
項目
試行回数
ク エリ 指紋の歪み率 pber
ス ク リ ーニン グの閾値 ε1
精査の閾値 ε2
ハッ シュ のビッ ト 数 L0
隣接 LSH 探索のハミ ン グ距離 rn
高速メ モリ から の
32 ビッ ト の平均読出時間 TH
大容量メ モリ から の
32 ビッ ト の平均読出時間 TL
メ モリ 格納方法
Yang の手法の単純拡張
300
0∼ 0.25
24
1024
13
0
提案手法
300
0∼ 0.25
24
1024
13
0
19 ナノ 秒
19 ナノ 秒
580 ナノ 秒
580 ナノ 秒
図 3.3(a)
図 3.3(b)
表 4.11， 図 4.3 が実験結果であ る 。 階層化 Staged LSH 有効の方が平均検索速度に おい
て 歪み無し 時に 1.3 倍高速， 最大で 4.3 倍高速であ り ， 精度は互角であ っ た 。 な お図中の
“1Gbps の壁” およ び “10Gbps の壁” と は， 1MB の音楽データ を 1Gbps， 10Gbps のネッ ト
ワ ーク 機器を 通過する ま での時間であり ， 3.1 節の方法で計算し た。 “256kbps”， “192kbps”，
“128kbps MP3 の圧縮に よ る 歪み率” と は， lame と いう フ リ ーソ フ ト を 用いて 各ビッ ト
レ ート の MP3 へエン コ ード し た 時の実験的な 最大歪み率であ り ， 2.4 節の方法で求めた 。
1010
1.0
0.8
108
正答率
検索の所要クロック数
両方無効
階層有効
106
0.6
1Gbpsの壁
0.4
10Gbpsの壁
0.2
256 192
kbps kbps
128kbps MP3の
圧縮による歪み率
両方無効
階層有効
4
0.0
10
0.00
0.05
0.10
0.15
0.20
0.25
0.00
クエリ指紋の歪み率
0.05
0.10
0.15
0.20
指紋の歪み率
図 4.3: 階層化 Staged LSH の評価の歪み率と 平均検索時間・ 検索精度
28
0.25
表 4.11: 階層化 Staged LSH の評価実験の結果
歪み率
0.00
0.01
0.02
0.03
0.04
0.05
0.06
0.07
0.08
0.09
0.10
0.11
0.12
0.13
0.14
0.15
0.16
0.17
0.18
0.19
0.20
0.21
0.22
0.23
0.24
0.25
Yang の手法の単純拡張
平均検索時間 (ク ロ ッ ク ) 正答率
4.53 × 106
1.000
6
4.90 × 10
1.000
5.83 × 106
1.000
6
6.81 × 10
1.000
8.24 × 106
1.000
7
1.01 × 10
1.000
1.02 × 107
1.000
7
1.31 × 10
1.000
1.54 × 107
1.000
7
1.56 × 10
1.000
1.76 × 107
1.000
7
2.09 × 10
1.000
2.42 × 107
1.000
7
2.94 × 10
1.000
3.63 × 107
1.000
7
3.36 × 10
1.000
5.29 × 107
1.000
7
4.79 × 10
1.000
6.29 × 107
1.000
7
7.27 × 10
1.000
8.15 × 107
1.000
8
1.04 × 10
1.000
1.26 × 108
0.980
8
1.58 × 10
0.986
2.02 × 108
0.866
8
3.80 × 10
0.510
提案手法
平均検索時間 (ク ロ ッ ク )
3.57 × 106
3.65 × 106
4.11 × 106
4.40 × 106
4.55 × 106
4.18 × 106
4.46 × 106
5.26 × 106
6.54 × 106
6.04 × 106
6.17 × 106
7.39 × 106
8.54 × 106
1.08 × 107
1.13 × 107
1.13 × 107
1.73 × 107
1.32 × 107
1.75 × 107
2.09 × 107
2.24 × 107
2.44 × 107
6.39 × 107
6.86 × 107
2.85 × 108
9.12 × 108
正答率
1.000
1.000
1.000
1.000
1.000
1.000
1.000
1.000
1.000
1.000
1.000
1.000
1.000
1.000
1.000
1.000
1.000
1.000
1.000
1.000
1.000
1.000
0.980
0.986
0.866
0.510
実験的に は， 階層化 Staged LSH は， 検索速度を 1.3 倍 (歪み無し 時) ま た は 4.3 倍 (歪
み有り も 含めた 最大値) に 向上し ， 検索精度は互角であっ た 。 も し 正解の指紋が大容量メ
モリ に あ る 場合に は， 階層化 Staged LSH は高速メ モリ で 126 回も のハッ シュ 探索と ス ク
リ ーニン グを 行う ので， む し ろ 図 3.3(a) の素朴な やり 方が高速であ る 可能性も 残っ て い
る 。 し かし 今回の実験パラ メ ータ では， 各試行に おいて 高頻度指紋が検索要求さ れる 確率
は合計 94.5%， 低頻度指紋は 5.5%と 大き な 差があり ， こ のこ と が階層化 Staged LSH を 有
利に し た と 考え ら れる 。
29
隣接 LSH 探索の評価
4.2.3
隣接 LSH 探索の単独の評価を する 。 こ のた めに 階層化 Staged LSH を 無効化する 。 指
紋 DB， ハッ シュ テ ーブル， ク エリ 指紋に ついて は前の節と 同じ も のを 使用する 。 そ の他
の実験条件は表 4.12 の通り であ る 。
表 4.12: 隣接 LSH の評価実験の条件
項目
試行回数
ク エリ 指紋の歪み率 pber
ス ク リ ーニン グの閾値 ε1
精査の閾値 ε2
ハッ シュ のビッ ト 数 L0
隣接 LSH 探索のハミ ン グ距離 rn
高速メ モリ から の
32 ビッ ト の平均読出時間 TH
大容量メ モリ から の
32 ビッ ト の平均読出時間 TL
メ モリ 格納方法
Yang の手法の単純拡張
300
0∼ 0.25
24
1024
13
0
提案手法
300
0∼ 0.25
24
1024
20
1
19 ナノ 秒
19 ナノ 秒
580 ナノ 秒
580 ナノ 秒
図 3.3(a)
図 3.3(a)
表 4.13， 図 4.4 が実験結果であ る 。 隣接 LSH 有効の方が平均検索速度に お いて 歪み無
し 時に 5.9 倍高速， 最大で 8.9 倍高速であ り ， 精度は互角であ っ た 。
1010
1.0
0.8
108
正答率
検索の所要クロック数
両方無効
階層有効
106
0.6
1Gbpsの壁
0.4
10Gbpsの壁
0.2
256 192
kbps kbps
128kbps MP3の
圧縮による歪み率
両方無効
階層有効
4
0.0
10
0.00
0.05
0.10
0.15
0.20
0.25
0.00
クエリ指紋の歪み率
0.05
0.10
0.15
0.20
指紋の歪み率
図 4.4: 隣接 LSH 探索の評価の歪み率と 平均検索時間・ 検索精度
30
0.25
表 4.13: 隣接 LSH 探索の評価実験の結果
歪み率
0.00
0.01
0.02
0.03
0.04
0.05
0.06
0.07
0.08
0.09
0.10
0.11
0.12
0.13
0.14
0.15
0.16
0.17
0.18
0.19
0.20
0.21
0.22
0.23
0.24
0.25
Yang の手法の単純拡張
平均検索時間 (ク ロ ッ ク ) 正答率
4.53 × 106
1.000
6
4.90 × 10
1.000
5.83 × 106
1.000
6
6.81 × 10
1.000
8.24 × 106
1.000
7
1.01 × 10
1.000
1.02 × 107
1.000
7
1.31 × 10
1.000
1.54 × 107
1.000
7
1.56 × 10
1.000
1.76 × 107
1.000
7
2.09 × 10
1.000
2.42 × 107
1.000
7
2.94 × 10
1.000
3.63 × 107
1.000
3.36 × 107
1.000
7
5.29 × 10
1.000
4.79 × 107
1.000
7
6.29 × 10
1.000
7.27 × 107
1.000
7
8.15 × 10
1.000
1.04 × 108
1.000
8
1.26 × 10
0.980
1.58 × 108
0.986
8
2.02 × 10
0.866
3.80 × 108
0.510
提案手法
平均検索時間 (ク ロ ッ ク )
7.64 × 105
7.56 × 105
7.82 × 105
8.18 × 105
1.02 × 106
1.17 × 106
1.23 × 106
1.51 × 106
1.84 × 106
1.86 × 106
2.17 × 106
2.61 × 106
2.76 × 106
3.39 × 106
4.73 × 106
3.88 × 106
5.93 × 106
7.03 × 106
7.72 × 106
9.76 × 106
1.25 × 107
1.61 × 107
1.92 × 107
2.17 × 107
3.26 × 107
6.29 × 107
正答率
1.000
1.000
1.000
1.000
1.000
1.000
1.000
1.000
1.000
1.000
1.000
1.000
1.000
1.000
1.000
1.000
1.000
1.000
1.000
1.000
1.000
1.000
0.996
0.993
0.883
0.493
今回の実験では， 隣接 LSH 探索に よ り 検索速度は 5.8 倍 (歪み無し 時) ま た は 9.8 倍 (歪
み有り も 含めた 最大値) に 改善し ， 検索精度に ついて は互角であ っ た 。 隣接 LSH 探索は，
ク エリ 指紋の歪み率が比較的小さ いと いう 事前知識を 利用し て 探索範囲を 狭める 手法であ
る 。 今回の実験パラ メ ータ では歪み率が 25%以下であ り ， そ れに 合わせて 実験条件 (ハッ
シュ のビッ ト 数 L0 ， 隣接 LSH 探索のハミ ン グ距離 rn ) を 机上の確率計算に よ り 設定する
こ と に よ り ， 検索精度を ほぼ互角に し つつ， 検索速度を 向上する こ と ができ た 。
31
階層化 Staged LSH と 隣接 LSH 探索の組み合わせの評価
4.2.4
階層化 Staged LSH と 隣接 LSH 探索を 両方有効化し た場合の評価を する 。 指紋 DB， ハッ
シュ テーブル， ク エリ 指紋に ついて は前説と 同じ も のを 使用する 。 そ の他の実験条件は表
4.14 の通り であ る 。
表 4.14: 階層化 Staged LSH と 隣接 LSH の評価実験の条件
項目
試行回数
ク エリ 指紋の歪み率 pber
ス ク リ ーニン グの閾値 ε1
精査の閾値 ε2
ハッ シュ のビッ ト 数 L0
隣接 LSH 探索のハミ ン グ距離 rn
高速メ モリ から の
32 ビッ ト の平均読出時間 TH
大容量メ モリ から の
32 ビッ ト の平均読出時間 TL
メ モリ 格納方法
Yang の手法の単純拡張
300
0∼ 0.25
24
1024
13
0
提案手法
300
0∼ 0.25
24
1024
20
1
19 ナノ 秒
19 ナノ 秒
580 ナノ 秒
580 ナノ 秒
図 3.3(a)
図 3.3(b)
表 4.15， 図 4.5 が実験結果であ る 。 隣接 LSH 有効の方が平均検索速度に お いて 歪み無
し 時に 7.5 倍高速， 最大で 27.0 倍高速であ り ， 精度は互角であ っ た 。
1010
1.0
0.8
108
正答率
検索の所要クロック数
両方無効
階層有効
106
0.6
1Gbpsの壁
0.4
10Gbpsの壁
0.2
256 192
kbps kbps
128kbps MP3の
圧縮による歪み率
両方無効
階層有効
4
0.0
10
0.00
0.05
0.10
0.15
0.20
0.25
0.00
クエリ指紋の歪み率
0.05
0.10
0.15
0.20
0.25
指紋の歪み率
図 4.5: 階層化 Staged LSH と 隣接 LSH 探索の評価の歪み率と 平均検索時間・ 検索精度
32
表 4.15: 階層化 Staged LSH と 隣接 LSH 探索の評価実験の結果
歪み率
0.00
0.01
0.02
0.03
0.04
0.05
0.06
0.07
0.08
0.09
0.10
0.11
0.12
0.13
0.14
0.15
0.16
0.17
0.18
0.19
0.20
0.21
0.22
0.23
0.24
0.25
Yang の手法の単純拡張
平均検索時間 (ク ロ ッ ク ) 正答率
4.53 × 106
1.000
6
4.90 × 10
1.000
5.83 × 106
1.000
6
6.81 × 10
1.000
8.24 × 106
1.000
7
1.01 × 10
1.000
1.02 × 107
1.000
7
1.31 × 10
1.000
1.54 × 107
1.000
7
1.56 × 10
1.000
1.76 × 107
1.000
7
2.09 × 10
1.000
2.42 × 107
1.000
7
2.94 × 10
1.000
3.63 × 107
1.000
7
3.36 × 10
1.000
5.29 × 107
1.000
7
4.79 × 10
1.000
6.29 × 107
1.000
7
7.27 × 10
1.000
8.15 × 107
1.000
8
1.04 × 10
1.000
1.26 × 108
0.980
8
1.58 × 10
0.986
2.02 × 108
0.866
8
3.80 × 10
0.510
提案手法
平均検索時間 (ク ロ ッ ク )
6.03 × 105
6.04 × 105
6.07 × 105
6.26 × 105
6.58 × 105
6.52 × 105
6.86 × 105
7.97 × 105
7.69 × 105
8.24 × 105
9.11 × 105
1.06 × 106
1.14 × 106
1.41 × 106
1.54 × 106
1.40 × 106
2.01 × 106
2.09 × 106
2.33 × 106
2.78 × 106
3.62 × 106
5.12 × 106
4.72 × 106
8.03 × 106
4.03 × 107
1.55 × 108
正答率
1.000
1.000
1.000
1.000
1.000
1.000
1.000
1.000
1.000
1.000
1.000
1.000
1.000
1.000
1.000
1.000
1.000
1.000
1.000
1.000
1.000
1.000
0.996
0.993
0.883
0.493
階層化 Staged LSH と 隣接 LSH 探索は同時に 両方有効化でき る も のであ り ， 片方だ け
を 有効化し た時よ り も 高速化が期待でき る 。 今回の実験では， 検索速度に ついて は 7.5 倍
(歪み無し 時) ま た は 27.0 倍 (歪み有り も 含めた 最大値) に 改善し た 。 こ れは今ま でのど の
方法 (階層化 Staged LSH のみ有効， 隣接 LSH 探索のみ有効， 両方無効) よ り も 高速であ
る 。 検索精度は隣接 LSH 探索と 同じ であ っ た 。
33
4.2.5
リ ソ ース使用量
階層化 Staged LSH およ び隣接 LSH 探索を 含めた 指紋検索モジュ ール (Staged LSH モ
ジュ ール ) のリ ソ ース 使用量は表 4.16 の通り であ る 。
表 4.16: 実装し た 指紋検索モジュ ール (Staged LSH モジュ ール ) のリ ソ ース 使用量
項目
FF
LUT
Memory LUT
I/O
BRAM
BUFG
MMCM
PLL
GT
4.3
使用量
463
1,190
304
0
0
0
0
0
0
使用可能量
866,400
433,200
174,200
850
1,470
32
20
20
45
使用率
0.05 %
0.27 %
0.17 %
0.00 %
0.00 %
0.00 %
0.00 %
0.00 %
0.00 %
まとめ
ま ず， 大容量メ モリ のおかげで， 千万曲分の指紋 DB と ハッ シュ テ ーブル (合計 10GiB
程度) を 用いた 指紋検索実験が可能に な っ た 。 本稿では乱数で千万曲分の指紋 DB を 構築
し て ， ク エリ 指紋に 一定の歪みを 付加し て 検索実験を 行っ た 。 今回の実験パラ メ ータ で
は， 階層化 Staged LSH は検索速度を 1.3 倍 (歪み無し 時) ま たは 4.3 倍 (歪み有り も 含めた
最大値)， 隣接 LSH 探索は検索速度を 5.8 倍 (歪み無し 時) ま た は 9.8 倍 (歪み有り も 含め
た 最大値) に そ れぞれ改善し ， 両方組み合わせる と 7.5 倍 (歪み無し 時) ま た は 27.0 倍 (歪
み有り も 含めた最大値) に な っ た。 検索精度に ついて はほぼ互角であっ た。 階層化 Staged
LSh は検索速度を 高速化する 手法であ り ， 隣接 LSH 探索は検索速度と 検索精度を 柔軟に
調整する 手法である 。 今回は検索精度を 維持し つつ検索速度を 高速化し たが， こ れは付録
A.2 で定めた 隣接 LSH 探索のパラ メ ータ の狙い通り であ る 。
34
第 5 章 ま と めと 今後の課題
ギガビッ ト 以上のネッ ト ワ ーク 機器内でリ ア ルタ イ ム に音楽を 検索でき る システム の実
用化を 目指し ， 音楽指紋検索の高速化・ 高精度化・ 大規模 DB 化の研究を 進めて き た。 先
行研究の指紋技術に よ っ て ， あ る 程度の検索の高速化と メ モリ 削減は達成さ れて いる が，
そ れでも 千万曲規模に な る と 指紋 DB が 10GB を 超え る 。 本研究では組込みシス テム を 想
定し て いる た め FPGA で実験を し て いる が， 市販の FPGA ボード 内蔵の DRAM(高速メ
モリ ) に は容量不足で 10GB を 保存でき ず， 実験すら ま ま な ら な い。
そ こ で本研究では PCIe 経由でデス ク ト ッ プ PC の DRAM(大容量メ モリ ) に ア ク セ ス 可
能に し た。 さ ら に 高頻度で検索要求さ れる 音楽のデータ を 高速メ モリ に ， そ れ以外の音楽
のデータ を 大容量メ モリ に 格納する こ と で， 高頻度の音楽を 高速メ モリ だけ で検索可能に
する 階層化 Staged LSH を 提案し た 。
加え て ， 検索速度と 検索精度のト レ ード オフ を よ り 細かく 調整可能な 隣接 LSH を 考案
し た。 確率計算に 基づく パラ メ ータ のチュ ーニン グに よ り ， 検索精度を 維持し つつ検索時
間を 向上でき る 。
こ の階層化 Staged LSH と 隣接 LSH を 組み合わせて 実験し た と こ ろ ， ク エリ 指紋に 歪
みがな い場合に 検索時間を 7.5 倍に 向上， 歪みがある 場合も 含める と 最大で 27.0 倍に 向上
でき た 。 歪みがな い場合に は， 提案手法無効時に 平均 4.18 × 106 ク ロ ッ ク であ っ た のが，
提案手法有効時に 平均 4.37 × 105 ク ロ ッ ク であり ， 3.1 節に 示し た目標 2 × 106 ク ロ ッ ク を
達成し た 。 ま た 検索精度に ついて も 維持でき て いた 。
今後の課題を 以下に 挙げる 。
• 重要な 課題の 1 つは， 高速メ モリ と 大容量メ モリ のデータ の入れ替え る ア ルゴ リ ズ
ム の開発である 。 本研究では高速メ モリ に 高頻度で検索要求さ れる 音楽のデータ を ，
大容量メ モリ に そ れ以外の音楽のデータ を 格納する と し たが， そ の割り 当て は固定
的であっ た 。 現実に は流行の音楽はそ の時々 に よ っ て 変わる ので， 各音楽の検索頻
度の移り 変わり に よ っ て ， ど のよ う な 入れ替え ア ルゴ リ ズム を 適用する べき か検討
する 余地があ る 。
• 類似指紋の区別も 重要な 課題であ る 。 音楽指紋は音楽の聴覚的特徴を も と に 生成さ
れる た め， 類似の音楽は類似の指紋に な る 可能性があ る 。 こ れを いかに し て 区別す
る か検討する 必要があ る 。
35
参考文献
[1] K. Araki, Y. Sato, V. Jain and Y. Inoguchi, “Performance Evaluation of Audio
Fingerprint Generation using Haar Wavelet Transform,” Proceedings of the 2011 International Workshop on Nonlinear Circuits, Communications and Signal Processing
(NCSP11), pp.380-383, Tianjin SaiXiang Hotel, Tianjin, China, 2011.
[2] J. Haistma and T. Kalker, “A Highly Robust Audio Fingerprinting System,” Proceedings of the International Symposium on Music Information Retrieval, 2002.
[3] H. Schreiber and M. Muller, “Accelerating Index-Based Audio Identification,” IEEE
Transactions on Multimedia, Volume 16, Issue 6, 2014.
[4] F. Yang, “Hardware Acceleration of Searching Strategy for Audio Fingerprinting
System,” Master’s thesis of Information Science, Japan Advanced Institute of Science
and Technology, 2013.
36
謝辞
本研究を 行う に あたり ， 研究室のゼミ やミ ーティ ン グやそ の他の様々 な 場面で， 手厚い
研究の御指導や情報機器の説明な ど を 受け 賜り ま し た 北陸先端科学技術大学院大学の情
報社会基盤セ ン タ ー井口 寧教授に 深く 感謝する と と も に 御礼申し 上げま す。
中間審査会で貴重な 御助言， 御意見を 頂いた金子 峰雄教授， 田中 清史准教授に 深く 感
謝いたし ま す。 ハード ウ ェ ア グループ合同ゼミ でも 金子研， 田中研， 金沢大学， 福井大学
の方々 に はお世話に な り ま し た ので感謝と 御礼を 申し 上げま す。
井口研究室のゼミ や普段の会話で， 多く の御意見， 御指導を 頂いた Tan Yiyu 氏， 佐々
木 泰氏， 中吉 達二氏， 大和 良介氏， 赤崎 翔太氏， 河村 知記氏， Faiz Al Faisal 氏に 感謝
と 御礼を 申し 上げま す。 OB と し て 多く の御意見， 御指導を 頂いた 佐藤 幸紀特任講師 (東
京工業大学)， 荒木 光一氏， Fan Yang 氏に 感謝と 御礼を 申し 上げま す。
情報セ キ ュ リ テ ィ コ ース でお 世話に な っ た 宮地 充子教授， 面 和成准教授， 布田 裕一
特任准教授， 田中 覚特任助教， 木藤 圭亮氏， STEWART, Gavin Lynn 氏， 道廣 大喜氏，
足立 大地氏， 岡村 宗一郎氏に 感謝いた し ま す。 情報セ キ ュ リ ティ の考え 方が研究室や自
宅のサーバ運用の役に 立っ て いる 他， 確率計算や誕生日のパラ ド ッ ク ス の考え 方は本研究
の理論式の導出に も 活用でき ま し た 。
北陸先端科学技術大学院大学の授業や事務手続き な ど でお世話に なっ た全て の方々 に 御
礼を 申し 上げま す。
最後に ， 日頃よ り 暖かく 見守っ て く ださ っ た 両親， 親族に 感謝いた し ま す。
37
付 録A
理論検索時間と 理論検索精度
本章では複数メ モリ を 用いた 階層化 Staged LSH と 隣接 LSH 探索の理論検索時間と 理
論検索精度に ついて 考察する 。
A.1
変数と 関数の記号
変数の一覧を 表 A.1 に ， 関数の一覧を 表 A.2 に そ れぞれ示す。
表 A.1: 変数の一覧
記号
NDB
pber
L0
L1
L2
nm
rn
ε1
ε2
説明
指紋 DB の音楽数 (すな わち 300 ま た は 10,000,000)
指紋の歪み率 (ビッ ト エラ ー率)
ハッ シュ 値のビッ ト 数
フ レ ーム のビッ ト 数 (すな わち 96)
指紋のビッ ト 数 (すな わち 4096)
ハッ シュ 探索の最大実行回数 (すな わち 126)
隣接 LSH 探索のハミ ン グ半径 (隣接 LSH 探索無効時は 0)
ス ク リ ーニン グのハミ ン グ距離の閾値 (すな わち 24)
精査のハミ ン グ距離の閾値 (すな わち 1024)
表 A.2: 関数の一覧
記号
Hash(x1 )
HD(x1 , x2 )
説明
x1 のハッ シュ 値を 求める 関数
x1 と x2 のハミ ン グ距離を 求める 関数
38
A.2
検索精度に関する 考察
本節では Staged LSH に おけ る ハッ シュ 探索， ス ク リ ーニン グ， 精査の各工程を 正解指
紋がパス する 確率を 求め， 検索精度に 大き な 影響を 与え る ハッ シュ 値のビッ ト 数に ついて
1 つの最適解を 求める 。
こ こ でいう 正解指紋と は、 ク エリ 指紋の元と なっ た音楽と 同じ 音楽から 生成さ れた指紋
のこ と である 。 逆に 不正解指紋と は， ク エリ 指紋の元と なっ た音楽と は別の音楽から 生成
さ れた 指紋のこ と であ る 。 “一致な し ” と いう 検索結果も 存在する が， こ れは正解指紋と
も 不正解指紋と も 異な る 。
精度に は指紋生成ア ルゴ リ ズム に 起因する も のと 指紋検索ア ルゴ リ ズム に 起因する も
のが考え ら れる が， 本稿では指紋生成に 関し て は十分な 精度が保証さ れて いる 想定で， 指
紋検索に 関する 精度を 考察する 。
A.2.1
不正解指紋が精査を パスし て し ま う 確率
ま ずは検索精度に ついて 考え る 。 検索精度を 確保する 上では， 異な る 音楽の指紋のハミ
ン グ距離があ る 程度離れて いる こ と が最低限必要であ る 。 でき れば ε2 よ り 大き いこ と が
望ま し い。 さ も な く ば， 不正解の音楽を 検索結果と し て 返す恐れが生じ る 。 誕生日のパラ
ド ッ ク ス に よ れば， 乱数を 大量に 発生さ せる と ， 同じ 値が複数回発生 (衝突) し て いる 確
率は直感よ り も 高い。 こ こ では 4096 ビッ ト の HiFP2.0 の指紋に ついて 誕生日のパラ ド ッ
ク ス を 考慮し て も 千万曲の指紋同士が互いに ε2 よ り 離れて いる こ と を 確認し て おき たい。
ま ず， 2 指紋 Rf p , Wf p のハミ ン グ距離が ε2 以下であ る 確率は， 指紋が乱数と みな せる
な ら ば次のよ う に 表さ れる 。
P 2,2 = P [HD(Rf p , Wf p ) ≤ ε2 ]
=
ε2
1 X
L Ci
2L2 i=0 2
(A.1)
こ れを 3 指紋， 4 指紋， · · ·， N 指紋と 増やし て いく と ，
P 2,N < 1 − {1 − P 2,2 }{1 − 2P 2,2 } · · · {1 − (N − 1)P 2,2 }
≃ 1 − {1 − NP 2,2 }(N −1)/2
"
−N(N − 1)
≃ 1 − exp
P 2,2
2
#
(A.2)
と な る 。 こ こ で途中計算の簡単化のた め N は奇数， N · P 2,2 ≪ 1 と し た 。 N が偶数の場
合も 最終的な 式は同じ であ る 。 こ の式を L2 = 4096, ε2 = 1024, N = 107 の条件で計算す
る と P 2,N ≃ 0 であ る 。 つま り HiFP2.0 が生成する 指紋が乱数に 近け れば， 千万曲の指紋
の中に ハミ ン グ距離が小さ いも のが 1 組以上存在する 確率は無視でき る 程度に 小さ い。
39
実際に は HiFP2.0 が生成する 指紋は必ずし も 乱数と はみな せな い。 特に 4096 ビッ ト の
先頭付近は 0 である こ と が多い。 指紋 DB 内に ハミ ン グ距離の近い指紋がある 場合の対応
に ついて は今後の課題と する 。
な お数値計算に は次の Mathematica ス ク リ プト を 実行し た 。
✓
✏
✒
✑
l2 = 4096;
e2 = 1024;
n = 10^7;
p22 = 2^(-l2) * Sum[l2!/k!/(l2-k)!, {k,0,e2}];
p2n = 1 - Exp[-n*(n-1)/2 * p22];
Print[N[p2n]];
A.2.2
正解指紋が精査を パスでき ない確率
歪んだク エリ 指紋と 正解指紋のハミ ン グ距離を 考え る 。 も し こ のハミ ン グ距離が精査の
閾値 ε2 よ り 大き いよ う では， ど れだけ ハッ シュ 探索と スク リ ーニン グを チュ ーニン グし て
も 検索は必ず失敗する 。 確率計算を する と ， 指紋は L2 ビッ ト である から ， 歪み率 pber > 0
のク エリ 指紋 Qf p と 正解指紋 Rf p のハミ ン グ距離が ε2 よ り 大き い確率は，
P2 = P [HD(Qf p , Rf p ) > ε2 ]
= 1−
ε2 h
X
L2 C i
· (pber )i (1 − pber )L2 −i
i=0
i
(A.3)
であ る 。 L2 = 4096, ε2 = 1024 の条件の下， 歪み率を 変え な がら こ の式の確率を 計算し た
も のを 図 A.1 に 示す。 歪み率 pber ≤ 0.22 であ れば， 0.99 以上の確率で正解指紋は精査を
パス する 。 HiFP2.0 の指紋の歪み率 (ビッ ト エラ ー率) は文献 [1] では最大 0.15 であり ， こ
の時 P2 = 1.0 × 10−62 である ので， 正解指紋が精査を パス でき な い心配はほと んど 不要で
ある 。
1
確率 P2
0.8
0.6
0.4
0.2
0
0
0.1
0.2
0.3
0.4
0.5
歪み率
図 A.1: ク エリ 指紋の歪みに よ り 正解指紋が精査を パス し な い確率
40
な お数値計算に は次の Mathematica ス ク リ プト を 実行し た 。
✓
✏
✒
✑
l2 = 4096;
e2 = 1024;
n = 10^7;
For[i = 1, i <= 50, i = i + 1,
pber = i / 100;
p2 = 1 - Sum[l2!/(k!*(l2-k)!) * pber^k * (1-pber)^(l2-k), {k,0,e2}];
Print[N[pber], " ", N[p2]];
];
A.2.3
正解指紋がスク リ ーニン グを パスでき ない確率
ス ク リ ーニン グに ついて も ， 正解指紋がパス でき な いこ と はあ ま り な い。 ク エリ 指紋
Qf r と 正解指紋 Rf r のハミ ン グ距離が ε1 よ り 大き い確率は， フ レ ーム が L1 ビッ ト であ る
から ，
P1 = P [HD(Qf r , Rf r ) > ε1 ]
= 1−
ε1 h
X
L1 C i
· (pber )i (1 − pber )L1 −i
i=0
i
(A.4)
であ る 。 L1 = 96, ε1 = 24 の条件の下， 歪み率を 変え な がら こ の式の確率を 計算し た も の
を 図 A.2 に 示す。 歪み率 pber ≤ 0.16 であ ればス ク リ ーニン グで検出でき る 確率は 0.99 以
上であ る 。
1
確率 P1
0.8
0.6
0.4
0.2
0
0
0.1
0.2
0.3
0.4
0.5
歪み率
図 A.2: ク エリ 指紋の歪みに よ り 正解指紋のフ レ ーム がス ク リ ーニン グを パス し な い確率
な お数値計算に は次の Mathematica ス ク リ プト を 実行し た 。
41
✓
✏
✒
✑
l1 = 96;
e1 = 24;
n = 10^7;
For[i = 1, i <= 50, i = i + 1,
pber = i / 100;
p1 = 1 - Sum[l1!/(k!*(l1-k)!) * pber^k * (1-pber)^(l1-k), {k,0,e1}];
Print[N[pber], " ", N[p1]];
];
A.2.4
LSH のハッ シ ュ 値にビ ッ ト エラ ーがある 確率
以上から ， 検索全体の精度はほと んど ハッ シュ 探索の成功確率のみに 左右さ れる 。 そ こ
でク エリ 指紋の 1 フ レ ーム のハッ シュ 値に rn ビッ ト よ り 多く のビッ ト エラ ーがあ る 確率
を 求める と 次の通り であ る 。
P 0 = P [Hash(Qf r ) 6= Hash(Rf r )]
= 1−
rn h
X
L0 C i
· (pber )i (1 − pber )L0 −i
i=0
i
(A.5)
こ れがハッ シュ 探索 1 回の失敗確率である 。 Staged LSH ではハッ シュ 探索を 最大で nm 回
(nm = (Lf p − Lf r + 32) ÷ 32 = 126) 繰り 返す。 nm 回全て 失敗する 確率は
P all = P 0
nm
(A.6)
であ る 。 最終的に ， Staged LSH の検索全体と し て の精度は 1 − P all に ほぼ等し い。
P all は図 A.3 のよ う に な る 。 歪み率 pber ≤ 0.25 ま でを 想定し ， 隣接 LSH の探索対象の
ハミ ン グ半径 rn = 0, 1, 2 と し た 。
1
rn = 0
rn = 1
rn = 2
確率 1 - Pall
0.8
0.6
0.4
0.2
0
0
10
20
30
40
50
ハッシュ値のビット数 L0
図 A.3: ハッ シュ 探索が 126 回全て 失敗する 確率
数値計算に は次の Mathematica ス ク リ プト を 実行し た 。
42
✓
nm
= 126;
pber = 0.25;
Print["0 0 0 0"];
For[l0 = 1, l0 <= 50, l0 = l0 + 1,
pall0 = N[(1 - (1-pber)^l0)^nm];
pall1 = N[(1 - Sum[l0!/(k!*(l0-k)!) * pber^k * (1-pber)^(l0-k), {k,0,1}])^nm];
pall2 = N[(1 - Sum[l0!/(k!*(l0-k)!) * pber^k * (1-pber)^(l0-k), {k,0,2}])^nm];
Print[l0, " ", pall0, " ", pall1, " ", pall2];
];
✒
A.2.5
✏
✑
ハッ シ ュ 値のビ ッ ト 数の最適値
ハッ シュ 値のビッ ト 数 L0 の最適解を 求める 。 L0 が大き いと ， 衝突の発生確率が下がる
ので検索速度は向上する が， ク エリ 指紋の歪みがハッ シュ 値に 波及し やすく な る ので精度
が落ち る 。 ま た ハッ シュ テ ーブルのメ タ データ が大き く な る と いう 問題も あ る 。
そ こ で一つの最適解は， ク エリ 指紋の歪み率 pber の許容上限を 設定し ， そ の範囲内で例
え ば Pall < 0.05 に な る よ う な 最大の L0 を 選ぶこ と であ る 。 図 A.3 に お いて Pall < 0.05
に 抑え る に は， rn = 0 な ら ば L0 = 13， rn = 1 な ら ば L0 = 20， rn = 2 な ら ば L0 = 26 が
そ れぞれ最適であ る 。 な お rn = 0 に ついて は， Yang の研究 [4] でも L0 = 13 が最適と さ
れて いる 。
ハッ シュ テ ーブルのメ タ データ のサイ ズに ついて 考え る と ， 図 2.14 のデータ 構造な ら
ば 2L0 · 4 バイ ト に な る 。 表 A.3 に 示す通り ， 千万曲の指紋 DB と ハッ シュ テ ーブル (本体
データ ) の合計サイ ズが約 10GB であ る こ と を 考え る と ， いずれも メ タ データ のサイ ズは
比較的小さ い。 ただし 組込み用途ではコ ス ト の観点から 10GB の DRAM を 用意する よ り ，
小容量の高速メ モリ と 大容量の低速メ モリ を 組み合わせて 使う こ と が考え ら れる 。 そ の
場合， 256MiB も あ る と 現時点では小容量の高速メ モリ を 圧迫し かねな いた め， も う 少し
ハッ シュ のビッ ト 数を 減ら すか， 1 隣接を 採用する べき であ る 。
表 A.3: ハッ シュ 値のビッ ト 数と ハッ シュ テ ーブルのメ タ データ のサイ ズ
ハッ シュ 値のビッ ト 数 L0
13
20
26
A.3
メ タ データ のサイ ズ (2L0 · 4 バイ ト )
32KiB
4MiB
256MiB
検索時間の理論値
本節では検索時間の理論値を 導出する 。
43
A.3.1
1 回のハッ シ ュ 探索と スク リ ーニン グの平均実行時間
Staged LSH の検索時間の期待値を 求める に は， 1 回のハッ シュ 探索と そ れに 伴う ス ク
リ ーニン グと 精査の平均実行時間 (図 2.10 のア ルゴ リ ズム の外側のループ 1 回) を 求め，
ハッ シュ 探索の実行回数の期待値を 乗じ れば良い。 ま ずは 1 回のハッ シュ 探索と そ れに 伴
う ス ク リ ーニン グと 精査の平均実行時間 Tall,1 を 求める 。 メ モリ の 32 ビッ ト のデータ の
平均転送時間を T ク ロ ッ ク と おく と ，
1. LSH のハッ シュ 値を 求める のに 1 ク ロ ッ ク
2. ハッ シュ 値に 対応する フ レ ーム リ ス ト のア ド レ ス 取得に T ク ロ ッ ク
3. リ ス ト 内のフ レ ーム のア ド レ ス取得に
4. リ ス ト 内のフ レ ーム 取得に
P rn
Prn
i=0 [L0 Ci ]
i=0 [L0 Ci ] × (nm × NDB ÷ 2
L0
)×T クロッ ク
× (L1 ÷ 32) × (NDB ÷ 2L0 ) × T ク ロ ッ ク
P rn
5. リ ス ト 内のフ レ ーム のハミ ン グ距離の計算に
(た だし 1 つ上の項目と 同時実行可能)
i=0 [L0 Ci ] (NDB
÷ 2 L0 ) × 9 ク ロ ッ ク
6. 精査を 実行する 場合， L2 ビッ ト の指紋の取得に (L2 ÷ 32) × T ク ロ ッ ク
7. 精査を 実行する 場合， L2 ビッ ト のハミ ン グ距離の計算に 134 ク ロ ッ ク (た だし 1 つ
上の項目と 同時実行可能)
である 。 L0 が十分大き く な い限り に おいて ， 支配的な のは項目 3 と 項目 4 であり ， 合計で
Tall,1 ≃
rn
X
[L0 Ci ] (nm + L1 ÷ 32) ×
i=0
= 129
rn
X
[L 0 C i ] ×
i=0
NDB
×T
2 L0
NDB
×T
2 L0
(A.7)
と なる 。
A.3.2
ハッ シ ュ 探索の実行回数の期待値
i 回目ま でのハッ シュ 探索で指紋を 見つけ ら れる 確率を P0,i で現す。 こ れは前述の LSH
のハッ シュ 値にビッ ト エラ ーがある 確率 P 0 を 用いて 次式で表さ れる 。 1 ≤ i ≤ nm である 。
P0,i = 1 − P 0
44
i
(A.8)
こ の P0,i を 用いて ハッ シュ 探索の実行回数を n0 の期待値を 求める 。
E[n0 ] = 1 · P0,1 + 2 · (P0,2 − P0,1 ) + 3 · (P0,3 − P0,2 )
+ · · · + (nm − 1) · (P0,nm −1 − P0,nm −2 ) + nm · (1 − P0,nm −1 )
= nm − P0,1 − P0,2 − · · · − P0,nm −1
= 1+
= 1+
nX
m −1
i=1
nX
m −1
(1 − P0,i )
P0
i
i=1
nm −1
1 − P0
= 1 + P0 ·
1 − P0
nm
1 − P0
=
1 − P0
P0,nm
=
P0,1
(A.9)
以上を 用いて ， 全体の検索時間 Tall の期待値は次で求めら れる 。
h
i
E Tall = E[n0 ] × Tall,1
(A.10)
図 A.4 に ， 次の 3 通り の条件で歪み率を 変え な がら E[Tall ] を 計算し た グラ フ を 示す。
こ こ では T = 1 ク ロ ッ ク と し た 。 いずれも 歪み率 0.25 ま でのハッ シュ 探索失敗率が 0.05
未満に な る よ う に 調整し た パラ メ ータ であ る が， 検索時間は隣接 LSH 探索を 有効に する
方が短い。
• rn = 0, L0 = 13
• rn = 1, L0 = 20
• rn = 2, L0 = 26
検索時間 E[Tall] clks
108
106
104
102
rn = 0, L0 = 13
rn = 1, L0 = 20
rn = 2, L0 = 26
0
0.1
0.2
0.3
0.4
0.5
歪み率 L0
図 A.4: 全体の検索時間の期待値
45