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: 井口寧, 情報科学研究科, 修士
大規模な音楽指紋データ ベースの高速検索における ク エリ の歪みへの頑健性向上に関する 調査研究
北陸先端科学技術大学院大学 情報科学研究科
福田 真啓
平成27年9月
修 士 論 文
大規模な音楽指紋データ ベースの高速検索における ク エリ の歪みへの頑健性向上に関する 調査研究
1310203 福田 真啓
主指導教員
井口 寧
審査委員主査
井口 寧
審査委員
田中 清史 金子 峰雄
北陸先端科学技術大学院大学 情報科学研究科
平成27年8月
概 要
近年のイ ン タ ーネッ ト は， 音楽の流通を 活発にする 場を 提供し て いる 一方で， 不正コ ピー の温床にも なっ て いる 。 こ れに対し ， エン ド ユーザが音楽データ を 通信する だけで自動的 にラ イ セン ス・ 課金情報を 受信者に提示でき る と いう ， 手軽で合法的な音楽共有システム が提案さ れて いる 。 し かし 高速化を 続ける ネッ ト ワ ーク 機器内で音楽を リ アルタ イ ム処理 で検索する のは決し て 容易ではない。 データ ベース(DB)が千万曲規模になる と なおさ ら である 。 本研究の目的は， 千万曲以上のDBの高速かつ高精度な音楽検索を 組込みシステ ム と し て 実現する こ と である 。
音楽の高速検索において 重要な要素技術は音楽指紋である 。 検索を 高速化・ 省メ モリ 化 でき る ため， 組込みシステムを 前提と し た音楽の高速検索には必須の技術である 。 し かし 単に音楽指紋を 高速検索でき る だけでは， 手軽で合法的な音楽共有システムは実用化でき ない。 本稿では指紋検索の大規模DB化と 歪み対策に焦点を 当て る 。 指紋検索の先行研究 である YangのStaged LSHは指紋DBと ハッ シュ テーブルに大容量のメ モリ を 必要と す る ため， 300曲ま でし か実験がな さ れて いな い。 別の問題と し て ， ハッ シュ 探索を し て い る ため指紋のビッ ト エラ ーにも 弱く ， 検索精度と 検索速度が悪化する 。
そこ で本稿ではいかにし て 高速化と 高精度化を 両立でき る かを 調査し た。 大規模DB化 し つつ検索速度を 落と さ な い工夫と し て ， 複数種類のメ モリ を 用いた階層化Staged LSH を 提案する 。 併せて ， 検索速度と 検索精度のト レ ード オフ を 柔軟に 調整可能な 隣接LSH 探索も 提案する 。 こ れら の手法によ り ， 指紋DBを 千万曲規模に拡大し つつ， 検索速度を 27.0倍に向上， 検索精度を 維持する こ と に成功し た。
目 次
第1章 はじ めに 1
1.1 研究の背景 . . . 1
1.2 研究目的 . . . 2
1.3 本論文の構成 . . . 2
第2章 音楽指紋と そ の関連研究 3 2.1 音楽指紋と は . . . 3
2.2 通信プロ ト コ ルの解析 . . . 4
2.3 PCMデータ への変換 . . . 4
2.4 指紋生成 . . . 5
2.5 指紋検索 . . . 8
2.5.1 Yangの研究成果の概要. . . 8
2.5.2 ハミ ン グ距離のハード ウ ェ アアク セラ レ ータ . . . 8
2.5.3 Staged LSHと その検索アルゴリ ズム . . . 10
2.5.4 Staged LSHの問題点 . . . 13
2.6 ラ イ セン ス・ 課金情報の送信 . . . 13
2.7 ま と め . . . 14
第3章 階層化Staged LSHによ る 大規模音楽指紋検索シ ステムの実装 15 3.1 組込みシステム と し て の音楽指紋検索 . . . 15
3.2 階層化Staged LSHによ る 大規模指紋DBの検索の高速化 . . . 17
3.3 隣接LSH探索によ る 高速化・ 高精度化のト レ ード オフ の調整. . . 18
3.4 提案システム の実装 . . . 20
3.5 ま と め . . . 21
第4章 評価実験 22 4.1 現実の音楽から 生成し た指紋DBでの評価 . . . 22
4.1.1 開発環境と 実験環境 . . . 22
4.1.2 隣接LSH探索の評価 . . . 23
4.1.3 リ ソ ース使用量 . . . 26
4.2 千万曲分の乱数指紋DBでの評価 . . . 26
4.2.1 開発環境と 実験環境 . . . 26
4.2.2 階層化Staged LSHの評価 . . . 26
4.2.3 隣接LSH探索の評価 . . . 30
4.2.4 階層化Staged LSHと 隣接LSH探索の組み合わせの評価 . . . 32
4.2.5 リ ソ ース使用量 . . . 34
4.3 ま と め . . . 34
第5章 ま と めと 今後の課題 35 付 録A 理論検索時間と 理論検索精度 38 A.1 変数と 関数の記号 . . . 38
A.2 検索精度に関する 考察 . . . 39
A.2.1 不正解指紋が精査を パスし て し ま う 確率 . . . 39
A.2.2 正解指紋が精査を パスでき な い確率 . . . 40
A.2.3 正解指紋がスク リ ーニン グを パスでき な い確率 . . . 41
A.2.4 LSHのハッ シュ 値にビッ ト エラ ーがある 確率 . . . 42
A.2.5 ハッ シュ 値のビッ ト 数の最適値 . . . 43
A.3 検索時間の理論値 . . . 43
A.3.1 1回のハッ シュ 探索と スク リ ーニン グの平均実行時間 . . . 44
A.3.2 ハッ シュ 探索の実行回数の期待値 . . . 44
図 目 次
1.1 ネ ッ ト ワ ーク 機器内での音楽検索 . . . 1
2.1 音楽指紋を 用いた高速検索 . . . 3
2.2 元の音楽データ を 用いた高速でな い検索 . . . 3
2.3 ネ ッ ト ワ ーク 機器内での音楽指紋検索システム に必要な 処理 . . . 4
2.4 音楽指紋の歪み . . . 5
2.5 Haarウ ェ ーブレ ッ ト 変換を 用いたマ ルチレ ベルサブバン ド 分解アルゴリ ズム 6 2.6 音楽指紋の生成アルゴリ ズム(HiFP 2.0) . . . 6
2.7 HiFP 2.0の図解 . . . 7
2.8 HiFP2.0の歪みのヒ スト グラ ム . . . 8
2.9 ハミ ン グ距離を 計算する ハード ウ ェ ア . . . 9
2.10 Staged LSHのアルゴリ ズム . . . 10
2.11 指紋と サブ指紋と フ レ ーム . . . 10
2.12 Staged LSHで徐々 に指紋DBの探索範囲を 狭めて いく 様子 . . . 11
2.13 局所性鋭敏型ハッ シュ の生成方法 . . . 12
2.14 ハッ シュ テーブルと 指紋DBのデータ 構造 . . . 12
3.1 ネ ッ ト ワ ーク 機器内での音楽指紋検索 . . . 15
3.2 FPGAの基本的な 構造の例. . . 16
3.3 指紋DBと ハッ シュ テーブルのメ モリ 格納方法 . . . 17
3.4 階層化Staged LSHのアルゴリ ズム(フ ロ ーチャ ート ) . . . 18
3.5 隣接ハッ シュ の例 . . . 19
3.6 隣接LSH探索のアイ デア . . . 19
3.7 音楽指紋検索のシステム と 内部モジュ ールの構成図 . . . 20
4.1 歪み率と 平均検索時間 . . . 24
4.2 歪み率と 検索精度 . . . 25
4.3 階層化Staged LSHの評価の歪み率と 平均検索時間・ 検索精度 . . . 28
4.4 隣接LSH探索の評価の歪み率と 平均検索時間・ 検索精度 . . . 30
4.5 階層化Staged LSHと 隣接LSH探索の評価の歪み率と 平均検索時間・ 検索 精度 . . . 32
A.1 ク エリ 指紋の歪みによ り 正解指紋が精査を パスし な い確率 . . . 40
A.2 ク エリ 指紋の歪みによ り 正解指紋のフ レ ーム がスク リ ーニン グを パスし な い確率 . . . 41 A.3 ハッ シュ 探索が126回全て 失敗する 確率 . . . 42 A.4 全体の検索時間の期待値 . . . 45
表 目 次
2.1 ハミ ン グ距離の計算時間 . . . 9
3.1 音楽指紋検索システム の内部モジュ ール一覧 . . . 20
4.1 FPGAの開発環境. . . 22
4.2 FPGAボード の特徴 . . . 23
4.3 隣接LSH探索の評価実験の条件 . . . 23
4.4 Yangの手法と 隣接LSH探索の検索時間 . . . 24
4.5 Yangの手法と 隣接LSH探索の検索精度 . . . 25
4.6 実装し た指紋検索モジュ ール(Staged LSHモジュ ール)のリ ソ ース使用量 . 26 4.7 FPGAの開発環境. . . 27
4.8 FPGAボード の特徴 . . . 27
4.9 デスク ト ッ プPCの仕様 . . . 27
4.10 階層化Staged LSHの評価実験の条件 . . . 28
4.11 階層化Staged LSHの評価実験の結果 . . . 29
4.12 隣接LSHの評価実験の条件 . . . 30
4.13 隣接LSH探索の評価実験の結果 . . . 31
4.14 階層化Staged LSHと 隣接LSHの評価実験の条件 . . . 32
4.15 階層化Staged LSHと 隣接LSH探索の評価実験の結果 . . . 33
4.16 実装し た指紋検索モジュ ール(Staged LSHモジュ ール)のリ ソ ース使用量 . 34 A.1 変数の一覧 . . . 38
A.2 関数の一覧 . . . 38
A.3 ハッ シュ 値のビッ ト 数と ハッ シュ テーブルのメ タ データ のサイ ズ. . . 43
第 1 章 はじ めに
1.1 研究の背景
近年， イ ン タ ーネ ッ ト 上の音楽の流通が盛んになっ て いる 。 Apple iTunes Storeのよ う に大規模な音楽配信サービスも 現れて おり ， その配信の場と し て イ ン タ ーネッ ト が利用さ れて いる 。 一方でイ ン タ ーネ ッ ト は不正コ ピ ーの温床にも な っ て おり ， そのため2012年 には著作権法が改正さ れ違法ダウ ン ロ ード が刑罰化さ れた。 イ ン タ ーネッ ト で音楽を 利用 でき る こ と は魅力的である が， 常に著作権法を 意識し な け ればな ら な いのは窮屈である 。 不正コ ピーの対策には複数の方法がある が， いずれも 課題が残さ れて いる 。 電子透かし の埋め込みは， 保存形式な ど を 変更する と 埋め込んだ情報が失われやすいし ， 消費者に と っ て も 自分が不正コ ピ ーを し たこ と に 気づき やすく な る わけ ではな い。 デジタ ル著作 権管理(DRM)は暗号化技術など によ り 第三者によ る コ ン テン ツ の利用を 防ぐ 方法である が， 専用機器や専用ソ フ ト ウ ェ アでし か再生でき ないため消費者にと っ て 不便である 。 音 楽や動画の投稿サイ ト の巡回・ 監視について は， 個人個人がメ ールなど で音楽データ を 送 受信する ケ ースに対応でき な い。
イ ン タ ーネ ッ ト で音楽を 気軽に 利用し たいが， 気づかぬう ち に 著作権法を 犯すこ と は 回避し たい。 こ の要求に応え る ため， 図1.1のよ う な， 著作権保護さ れた音楽を イ ン タ ー ネ ッ ト で通信する と ， イ ン タ ーネ ッ ト サービスプロ バイ ダ(ISP)のネ ッ ト ワ ーク 機器が自 動的にその音楽を 検出し て ， ラ イ セン スや課金情報を 受信者に提示する システムが提案さ れて いる 。 こ れが実現する と ， 世界中の消費者はメ ールやP2Pで音楽を 送受信する だけ で合法的に音楽を 共有でき る 。
ISPのルータ インターネット
ライセンス
・課金情報 ファイル音楽
送信者
受信者 ISPのルータ
音楽検索
図 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.1 音楽指紋と は
音楽の高速検索において 重要な要素技術は音楽指紋である(単に指紋と も 言う)。 指紋と は， 録音し た音楽のメ ロ ディ やリ ズムなど の聴覚的な特徴を ま と めた小サイ ズのデータ で ある 。 指紋は図2.1の方式によ る 音楽の高速検索に活用さ れて いる 。 こ の方式は図2.2の よ う な 元の音楽データ 同士の比較によ る 素朴な 検索に比べて 次のよ う な 利点がある 。
1. 小サイ ズな ので比較回数が少な い (高速)
2. 小サイ ズな ので高速・ 小容量のメ モリ を 有効活用でき る (高速・ 省メ モリ)
3. 同じ 曲のMP3， AACなどの複数の保存形式を DBに用意する 必要がない(省メ モリ)
音楽指紋の比較 検索結果 クエリ音楽
音楽指紋DB (小サイズ)
(巨大サイズ)音楽DB 音楽指紋の生成
音楽指紋の生成
図 2.1: 音楽指紋を 用いた高速検索
音楽データ
の比較 検索結果
クエリ音楽
(巨大サイズ)音楽DB
図 2.2: 元の音楽データ を 用いた高速でな い検索
実は前ページの図2.1だけ では， 1章で示し たネ ッ ト ワ ーク 機器内での音楽指紋検索シ ステムは実現でき ない。 本研究の範囲を よ り 明確にする ため， 他に必要な処理も 合わせた 全体像を 図2.3に 示す。 本研究の主な 焦点は“指紋検索”部分である が， 他の処理に つい て も 本章で簡単に説明する 。
通信プロトコル
の解析 指紋生成 指紋検索 ライセンス・
課金情報の送信 PCMデータ
への変換
検索結果(音楽ID) ISPのルータ
本研究の焦点 指紋
PCMデータ 音楽データ
(MP3，AACなど) ライセンス・
通信データ 課金情報
図 2.3: ネ ッ ト ワ ーク 機器内での音楽指紋検索システム に必要な 処理
2.2 通信プロト コ ルの解析
ネッ ト ワ ーク 機器内で音楽指紋検索する にあたり ， ま ず最初に“通信プロ ト コ ルの解析”
を する 必要がある 。 こ れはISPのネ ッ ト ワ ーク 機器に入っ て く る 通信データ (フ レ ーム や パケッ ト )から 音楽データ を 抽出する 処理である 。 アプリ ケ ーショ ン 層の多様な プロ ト コ ル(HTTP， SMTPなど)や符号化方式(Base64など)やそれら のバージョ ン アッ プなど に ど こ ま で対応する べき かと いう 点が主な課題である が， 多く は仕様が公開さ れて いる ので サポート する プロ ト コ ルを 限定すれば開発自体は容易である 。
2.3 PCM データ への変換
音楽データ を 抽出し たら ， 次は“PCMデータ への変換”を 行う 。 こ れはMP3や AAC で圧縮さ れて いる 音楽データ を ， 非圧縮のPCM(パルス符号変調)データ に変換する 処理 である 。 こ の変換処理について は， さ ら なる 高速化の研究も 考え ら れる が， 既に一定の高 速化が達成さ れて いる 。 例え ばlame 3.99.5と いう フ リ ーソ フ ト を IntelXeonR プロ セッR サで実行し て みたと こ ろ ， 5.19MBのMP3フ ァ イ ルを 0.837秒でデコ ード し た。 こ れは変 換速度が8×5.19MB÷0.837 = 49.6Mbpsである こ と を 意味する 。 なお本研究では後段の 処理工程である “指紋生成”に HiFP2.0を 利用する ため， “PCMデータ への変換”が出力 する PCMデータ はサン プリ ン グ周波数44.1kHz， 量子化ビッ ト 数16と する 。
本処理工程では歪みの問題が発生する こ と がある 。 歪みの問題と は図2.4のよ う に， 元々 が同じ 音楽データ である にも 関わら ず， 保存形式・ 圧縮率の変更によ る 非可逆圧縮によ っ て 聴覚情報が歪むこ と である 。 聴覚情報が歪むと 後で生成する 指紋に も 多少のビッ ト エ ラ ーを 生じ さ せて し ま う 。 こ れは現時点のど の指紋生成アルゴリ ズムでも 回避でき ない問 題な ので， “指紋検索”の処理工程に おいて は完全一致の探索ではな く 類似度を 利用し た 最近傍探索が必要になる 。 なお本研究では主に音楽CDから コ ピーし た音楽の特定を 目指 し て いる ため， 録音時の雑音や録音開始のタ イ ミ ン グのずれな ど によ る 歪みは考え な い。
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行目が特 徴抽出である 。
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)
HiFP2.0のア ルゴ リ ズム を 図解し た も のも 図2.7に 示す。 要する に HiFP2.0は， 音楽 データ の先頭から 約2.97秒分を 取り ， 8サン プルずつ算術平均を 取っ てLo配列を 作り ， Lo配列を 3つ飛ばし に大小比較を する こ と で4096ビッ ト のFPID(指紋)を 生成する 。 な おHiFP2.0ではサン プリ ン グ周波数が44.1kHzである こ と を 前提と し て おり ， 2.97秒は 131,072サン プルに相当する 。 整数の加算， シフ ト 演算， 比較処理だけ で済むのでハード ウ ェ ア処理に適し て いる 。
65535
0 2.97s
音声信号
平均 平均 平均 平均 平均 平均 平均 平均 平均 平均 平均
Lo
＞ ＞
FPID 0 1 ・・・
4096ビット
21253 24536 34915 48102 48154 48319 48243 47056 36192 32053 32553
0
最後に1ビットだけ’0’を追加 0.73ms
23183 26991 37921 平均 平均 平均
図 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%であっ た。
0 20 40 60 80
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のよ う に短い。
1段目 2段目 3段目 4段目 5段目
出力データ (初期値:0) 6段目
入力データ1 (32ビット)
入力データ2 (32ビット)
7段目
排他的論理和 加算
図 2.9: ハミ ン グ距離を 計算する ハード ウ ェ ア
表 2.1: ハミ ン グ距離の計算時間
入力ビッ ト 数 所要ク ロ ッ ク 数
32 7
64 8
96 9
... ...
4196 134
2.5.3 Staged LSH と そ の検索ア ルゴリ ズム
Yangによ る も う 1つの成果はStaged LSHである 。 こ れはLSHを 用いたハッ シュ 探索 の改良版である 。 4096ビッ ト の指紋のハミ ン グ距離を いき な り 計算せず， ま ずはも っ と 少ないビッ ト 数のハミ ン グ距離を 計算し て スク リ ーニン グ処理する 方法であり ， 比較処理 の回数を 減ら すこ と によ り 検索を 高速化する 。
検索全体のアルゴリ ズムは図2.10の通り である 。 6行目の“スク リ ーニン グ”， 8行目の
“精査”について は， Yangの文献[4]ではそれぞれ“coarse search”， “exact search”と 表記 さ れて いる 。 以降では， こ のアルゴリ ズム について 詳し く 説明する 。
1: forフ レ ームt∈ク エリ 指紋Qdo
2: ハッ シュ 値←ハッ シュ 関数でtを 処理 3: forエン ト リ i∈ハッ シュ テーブル 4: if ハッ シュ 値==i.ハッ シュ 値then 5: forj ∈i.フ レ ーム リ スト do
6: if スク リ ーニン グ(t, j)≤閾値1then 7: P ←jの元と な る 指紋
8: if 精査(P, Q)≤閾値2 かつ P < BestM atchthen
9: BestM atch←P
10: end if
11: end if
12: end for
13: returnBestM atch
14: end if
15: end for 16: end for
17: return“一致な し”
図 2.10: Staged LSHのアルゴリ ズム
ア ルゴリ ズム の内容に 入る 前に“フ レ ーム”に ついて 説明する 。 Yangは図2.11のよ う に 4096ビッ ト の指紋を 32ビッ ト ずつ128個の“サブ指紋”と し て 区切り ， 3つの連続し た サブ指紋を フ レ ーム と 呼んでいる 。 1つの指紋には126フ レ ーム ある 。
サブ指紋0
指紋
0x87E5291D 0x481D620F
32ビット 32ビット
0x3A1580E3 32ビット
0x59BE109F 32ビット サブ指紋1 サブ指紋2 サブ指紋3
0x357AD20
・・・・・・
32ビット サブ指紋127 4096ビット
フレーム0 96ビット
フレーム1 96ビット
フレーム125 96ビット フレーム2
96ビット
図 2.11: 指紋と サブ指紋と フ レ ーム
Staged LSHの検索ア ルゴリ ズム に は大き く ハッ シュ 探索， ス ク リ ーニン グ， 精査の3 つの段階がある 。 図2.12のよ う にこ の3つの段階を 通し て 徐々 に指紋DBの探索範囲を 狭 めて いく 。
ハッシュ探索
スクリーニング
精査
指紋DB ・・・・・・
指紋0 指紋5 指紋251 指紋4895
指紋0 指紋1 指紋2 指紋9,999,999
指紋5 指紋8514
指紋5 検索結果 クエリ指紋
(計算量:小)
(計算量:大) (計算量:中)
指紋32154
指紋3 指紋4 探索範囲：大
探索範囲：小
図 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のよ う なハッ シュ テーブルを 用いる と 処理が即座に完了する 。 ハッ シュ 値の衝突発生時は， 同じ ハッ シュ 値 になる フ レ ームを リ スト にま と めて おき ， 検索時にそのリ スト 内のフ レ ームを 全て 次段階
0
1 0
1 1 11 01 00 10 1 0 11 00 0 1 1 1 01 10 10 10 0
0 0
1 1 1 11 1
1
1 0
1 1 1 0 0 00 0 0 01 01 00 10 01 11 11 11 01 00 1 0
1 1 11 11 11 00 0 0 01 00 10 10 11 0
0 1 1 0 1 1 0 1 1 1 0 1
入力:96ビット
出力:13ビット
図 2.13: 局所性鋭敏型ハッ シュ の生成方法
ハッシュ値0x0000のフレームリストの最終アドレス 32ビット
ハッシュ値0x0001のフレームリストの最終アドレス :
:
ハッシュ値0x0000の1番目のフレームの先頭アドレス ハッシュ値0x0000の2番目のフレームの先頭アドレス
: :
: :
ハッシュ値0x1FFFのフレームリストの最終アドレス
ハッシュ値0x1FFFの1番目のフレームの先頭アドレス ハッシュ値0x1FFFの2番目のフレームの先頭アドレス
: :
ハッシュ値0x0000の最後のフレームの先頭アドレス ハッシュ値0x0000
のフレームリスト
ハッシュ値0x0001の1番目のフレームの先頭アドレス ハッシュ値0x0001の2番目のフレームの先頭アドレス
: :
ハッシュ値0x0001の最後のフレームの先頭アドレス ハッシュ値0x0001
のフレームリスト ハッシュテーブル
のメタデータ
ハッシュ値0x1FFFの最後のフレームの先頭アドレス ハッシュ値0x1FFF
のフレームリスト
音楽0の指紋 (4096ビット) 32ビット
音楽1の指紋 (4096ビット)
: :
音楽9,999,999の指紋 (4096ビット)
ハッシュテーブル 指紋DB
図 2.14: ハッ シュ テーブルと 指紋DBのデータ 構造
スク リ ーニン グ(coarse search)
ハッ シュ 探索の次はスク リ ーニン グである 。 スク リ ーニン グも 精査も ハミ ン グ距離に基 づいて 正解の指紋を 探し 当て る が， ハッ シュ 探索完了時点ではま だ多数の候補が残る こ と がある 。 そこ で， いき なり 4096ビッ ト 同士のハミ ン グ距離を 計算せず， ま ずは96ビッ ト のフ レ ームだけでハミ ン グ距離を 計算し ， 一定の閾値以上の指紋を ふる い落と す。 こ れが Staged LSHの最大の特徴のスク リ ーニン グである 。
精査(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.1) ハッ シュ テーブルのサイ ズ = 2L0×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に対応する 音楽のラ イ セン ス・ 課金情報を ， 音楽のダウ ン ロ ード 先へ送信する 処 理である 。 ラ イ セン ス・ 課金情報を 送信する ための通信のプロ ト コ ルは， 通信の信頼性や セキュ リ ティ など も 考慮の上で決定ま たは作成する 必要がある 。 ま たは本処理を “関連パ
2.7 ま と め
本章では音楽指紋と その関連研究について 述べた。 ネッ ト ワ ーク 機器内の音楽検索シス テムを 実現する には大き く 分けて5つの処理を 考え る 必要がある 。 その中でも 指紋生成の HiFP 2.0と 指紋検索のStaged LSHについて は詳し く 説明し た。 本研究の対象は5つの処 理工程の中でも 指紋検索の部分であり ， その重要な課題の1つが大規模DB化， も う 1つ の課題が高速化と 高精度化の両立である 。
第 3 章 階層化 Staged LSH によ る 大規 模音楽指紋検索シ ステムの実装
3.1 組込みシステムと し て の音楽指紋検索
本研究ではFPGAで音楽を 検索する 。 と いう のも ， 本研究で実現し たいアプリ ケーショ ン は， 図3.1のよ う なネ ッ ト ワ ーク 機器内での音楽検索を 必要と する 。 すなわち 組込みシ ステム であり ， 以下のよ う な 要求が想定さ れる ためである 。
• 小型化・ 軽量化
• 計算リ ソ ース・ 金銭的コ スト の削減
• 低消費電力化
ネッ ト ワ ーク 機器内に組み込める のは， スーパーコ ン ピュ ータ や高性能のサーバ機器では な く ， マ イ コ ン ， ASIC， FPGAな ど である 。 そ の中でも 本研究でFPGAを 選んだのは，
上述の要求を 満たし つつ高性能化を 狙え ， し かも 繰り 返し 実機で検証でき る ためである 。
ISPのルータ ポート1
ポート2 ポート3 ポート4
パケットバッファメモリ
ルーティングテーブル プロセッサ
音楽検索システム FPGA 指紋DB等
のメモリ ポート5
ポート6
図 3.1: ネ ッ ト ワ ーク 機器内での音楽指紋検索
FPGAと は図3.2のよ う な構造を 持つプロ グラ マブルデバイ スである 。 内蔵SRAMに格 納さ れて いる 回路情報を も と にLUTやSMの結線を し て 動作する 。 集積回路ではある が，
エン ド ユーザでも 容易に回路を 変更し て 実機で動作さ せる こ と ができ る 。 手順は， ま ずデ ジタ ル回路を Verilog HDLや VHDLな ど のハード ウ ェ ア記述言語で設計し ， Xilinx社や Altera社など のFPGAベン ダが提供し て いる ツ ールで“論理合成”， “配置＆ 配線”， “ビッ ト スト リ ーム生成”を 行い， その出力フ ァ イ ルを USBなど でJTAGを 経由し て SRAMへ 転送すれば良い。
SM SM
: Switch Matrix CLB
SM
: Configurable Logic Block CLB
CLB
SM SM
SM SM
CLB CLB
CLB CLB
CLB CLB
SM
SM
SM
SM
SM
SM
SM SM
SM
LUT : Lookup Table LUT
FF : Flip-Flop FF 入力
Clock Reset
出力
図 3.2: FPGAの基本的な 構造の例
検索時間の目標について も 検討する 。 望ま し いのは， ネッ ト ワ ーク 機器内でリ アルタ イ ム処理でき る こ と である 。 こ れは， も し 音楽の通信が同時に多数発生し て も ， 後続の音楽 の検索を 遅延さ せないためである 。 最近のネ ッ ト ワ ーク 機器(有線)は10Mbps〜100Gbps の通信速度を サポート し て おり ， 400Gbpsも 仕様策定が進めら れて いる 。 音楽データ のサ イ ズは， 保存形式・ 圧縮率にも よ る が典型的には1分あたり 1〜2MBである 。 そこ で， 例 えば1MBの音楽データ が1Gbpsのネッ ト ワ ーク 機器を 通過する ま での時間を 計算する と ，
転送時間= 8×(1×106)
1×109 秒= 8ミ リ 秒 (3.1) である 。 すなわち こ の数値例では1曲の検索を 8ミ リ 秒以内に抑え る 必要がある 。 本研究 で使う FPGAボード では200MHzある いは250MHzのク ロ ッ ク が利用可能である から ， 8 ミ リ 秒はそれぞれ1.6×106ク ロ ッ ク， 2×106ク ロ ッ ク に相当する 。
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を 大容量メ モリ に格納する こ と である 。
(千万曲，約5GiB)指紋DB
デバッグ領域 高速メモリ
(4GiB)
大容量メモリ (28GiB)
ハッシュテーブル (千万曲，約5GiB)
(a) Yangの手法の単純拡張
高頻度指紋の ハッシュテーブル (400万曲，約2GiB)
高頻度指紋の (400万曲，約2GiB)指紋DB
低頻度指紋の ハッシュテーブル (600万曲，約3GiB)
低頻度指紋の (600万曲，約3GiB)指紋DB
デバッグ領域 高速メモリ
(4GiB)
大容量メモリ (28GiB)
(b) 階層化Staged LSH 図 3.3: 指紋DBと ハッ シュ テーブルのメ モリ 格納方法
し かし ， こ れだと ど の指紋を 検索する 際も 必ず大容量メ モリ にアク セスし なければなら ない。 そこ で， 現実には人気の音楽や流行の音楽があり ， イ ン タ ーネッ ト 上を 通信する 音 楽に 偏り がある こ と を 踏ま え ， 図3.3(b)のよ う に データ を 格納し ， 高頻度で検索要求さ れる 指紋を 高速メ モリ だけで検索完了可能にする ために図3.4のフ ロ ーチャ ート の方法を 採用し た。 こ れが階層化Staged LSHである 。 こ こ で“高頻度指紋”と は人気があり 検索
合である 。
検索時間は付録A.3よ り ， 指紋DBのサイ ズNDBおよ び32ビッ ト あたり のメ モリ ア ク セス時間T にほぼ正比例する 。 NDBの増大は回避不能と し て ， 人気の音楽や流行の音 楽に関し て T を 削減する こ と で， 平均的な 検索時間を 短縮する と いう 狙いである 。
開始
検索結果を返した Yes
No
終了 高速メモリでStaged LSH
低速メモリでStaged LSH
図 3.4: 階層化Staged LSHのアルゴリ ズム (フ ロ ーチャ ート )
3.3 隣接 LSH 探索によ る 高速化・ 高精度化のト レ ード オ フ の調整
指紋の歪みによ り ハッ シュ 値が1ビッ ト でも 変化する と ， 基本的にはハッ シュ 探索は失 敗する 。 し かし LSHでは歪みが小さ け ればハッ シュ 値が変化し な いこ と があり ， その場 合ハッ シュ 探索は成功する 。
LSHのハッ シュ 探索の成功確率は， ハッ シュ 値が衝突し な い確率と ト レ ード オフ の関 係にある 。 いま 指紋の各ビッ ト が0と 1である 確率はど ち ら も 1/2である と し ， 指紋の歪 み率(ビッ ト エラ ーの発生確率)を pberと する と ， ハッ シュ 値がL0ビッ ト であれば，
ハッ シュ 探索の成功確率= (1−pber)L0 (3.2) ハッ シュ 値の衝突確率= 1
2L0 (3.3)
と な る 。 すな わち L0を 小さ く すればハッ シュ 探索は成功し やすく な る が， ハッ シュ 値も 衝突し やすく なる 。 衝突が発生する と 線形探索する 対象が多く なる ので検索速度の低下に つな がる 。 かと 言っ て L0を 大き く する と ハッ シュ 探索が失敗し やすく な り ， 精度が低下 する 。
そこ で検索速度と 精度の両立のため， ハミ ン グ距離的に隣接する ハッ シュ 値である “隣 接ハッ シュ”(図3.5)も 探索対象に含める “隣接LSH探索”手法を 提案する 。 こ れは概念的
に は図3.6のよ う な ア イ デア であり ， ハッ シュ 値のビッ ト 数L0を 増やし て 衝突確率を 下 げな がら ， 隣接ハッ シュ を 探索する こ と でハッ シュ 探索の成功確率を 上げる 。
付録A.2では， 指紋の各ビッ ト の誤り 率が一定以下である と 仮定し ， ハッ シュ 値を 何 ビッ ト にし て 何隣接ハッ シュ ま でを 探索する べき かを 確率計算によ り 考察し た。 結果は，
20ビッ ト ， 1隣接である 。
0 1 1 0 1 1 1 1 1 0 0 1 0 元データ
1隣接ハッシュ0 0 1 1 0 1 1 1 1 1 0 0 1 1 0 1 1 0 1 1 1 1 1 0 0 0 0 1隣接ハッシュ2 0 1 1 0 1 1 1 1 1 0 1 1 0 1隣接ハッシュ1
: :
1 1 1 0 1 1 1 1 1 0 0 1 0 1隣接ハッシュ12
2隣接ハッシュ0 0 1 1 0 1 1 1 1 1 0 0 0 1 0 1 1 0 1 1 1 1 1 0 1 1 1 2隣接ハッシュ2 0 1 1 0 1 1 1 1 1 0 1 0 0 2隣接ハッシュ1
: : : :
1 0 1 0 1 1 1 1 1 0 0 1 0 2隣接ハッシュ77
図 3.5: 隣接ハッ シュ の例
クエリから生成 したハッシュ値
探索対象（太線）
正解のハッシュ値
探索範囲を狭めることで、探索にかかる時間を短くする
探索範囲を隣まで広げることで、探索の成功確率を上げる 0000 000100110010
0100 010101110110 1100 110111111110 1000 100110111010
0000 000100110010 0100 010101110110 1100 110111111110 1000 100110111010
00 01
11 10
正解のハッシュ値 クエリから生成
したハッシュ値
クエリから生成
したハッシュ値 正解のハッシュ値
探索対象（太線）
探索対象（太線）
図 3.6: 隣接LSH探索のアイ デア
3.4 提案システムの実装
図3.7に本研究の音楽指紋検索システムの内部構成図を ， 表3.1に構成図中の各モジュー ルの説明を ， それぞれ示す。 提案手法では， 階層化Staged LSHと 隣接LSH探索の両方を
“Staged LSH”のブロッ ク に機能追加する 。 “デバッ グ用”で囲んだ信号線はEthernet(MII) ま たはPCIeのイ ン タ フ ェ ースを 制御する モジュ ールと 接続し て おり ， 外部のパソ コ ン が 検索開始指示を 出し 検索結果を 受け取る ために使用し た。 EthernetやPCIeは一般的なメ モリ 用のイ ン タ フ ェ ース ではな いが， FPGAから はメ モリ 制御モジュ ールの特定ア ド レ スにデータ を 読み書き する こ と でこ れら のイ ン タ フ ェ ースを 制御可能と し た。
FPGAボード 指紋検索
パソコン メモリ制御
内部バス
DDR4
アドレス データ 制御信号 検索開始 検索結果 クエリ指紋
高速メモリ 大容量メモリ
BRAM Staged LSH
PCIe制御 MII制御または
デバッグ用
MIG制御
PCI Express または Ethernet
図 3.7: 音楽指紋検索のシステム と 内部モジュ ールの構成図
表 3.1: 音楽指紋検索システム の内部モジュ ール一覧
モジュ ール名 説明
指紋検索 ク エリ 指紋を 受け取り 検索結果を 返す。
Staged LSH Staged LSH手法によ り ク エリ 指紋を 検索する 。 提案手法では隣接LSH探索も 含む。
BRAM ク エリ 指紋や一時データ を 格納する 。
メ モリ 制御 DDR3の高速メ モリ を 64ビッ ト アド レ スに一元的にマ ッ ピン グする 。 MIG制御 DDR3経由でFPGAボード 内蔵のDRAM(高速メ モリ)のデータ を 読み
出す。 Xilinxのラ イ ブラ リ を 含む。
PCIe制御 PCIeま たはEthernet経由でパソ コ ン から 指紋DB・ ハッ シュ テーブル・
ま たはMII制御 ク エリ 指紋， そし て 検索開始指示を 受け取る 。 検索完了後は結果を 返す。
こ の構成図において 指紋を 検索する のはFPGAである 。 デスク ト ッ プ PCは， CPUを 用いて 指紋検索さ せる こ と はなく ， 基本的にはデバッ グと 大容量メ モリ と し て のみ使用す る 。 よ り 正確には次の3つの用途である 。
• FPGAへ検索開始を 指示する
• FPGAから 検索結果を 受け 取り ， 画面に表示する
• FPGAへ指紋DBな ど を 転送する (検索前＆ 検索中)
3.5 ま と め
YangのStaged LSHは音楽検索のハード ウ ェ ア 化と 高速化に おいて 優れた方法である が， 実際に実装する と 大容量のメ モリ が必要であり ， そのま ま では千万曲規模の音楽DB には適さ な かっ た。 そこ で高速・ 小容量のDRAMに加え て 低速・ 大容量のDRAMを 用 意する こ と で， 千万曲分の指紋DBと ハッ シュ テーブルを 用いた検索を 実現する と と も に， 高精度の音楽に関する データ を 高速・ 小容量のDRAMに格納する こ と で平均的な 検 索速度の向上を 図っ た。 併せて 検索速度と 検索精度の両立と いう 課題に対応する ため， 隣 接ハッ シュ ま で探索対象を 広げる 隣接LSH探索を 考案し ， よ り 柔軟に検索速度と 検索精 度を 調整可能にし た。 そし て 階層化Staged LSHと 隣接LSH探索も 含めたStaged LSHを FPGAに実装し ， 音楽指紋検索システム を 開発し た。
第 4 章 評価実験
提案手法である 階層化Staged LSHと 隣接LSH探索を 評価する ための実験を 行う 。
4.1 現実の音楽から 生成し た指紋 DB での評価
ま ずは現実の音楽から 生成し た指紋を 用いて ， 実装し た音楽指紋検索システムの， 特に 隣接LSH探索によ る 検索速度と 検索精度への影響を 評価する 。 こ の評価では， 音楽指紋 DBのサイ ズは300曲ま でであり ， 複数メ モリ を 用いた実験も 実施し な い。
4.1.1 開発環境と 実験環境
FPGAの開発環境を 表4.1にま と める 。 回路合成から ビッ ト スト リ ーム生成ま で通常は 数十分以上かかる ため， 高性能のサーバを 使用する こ と でビルド 時間を 短縮し た。 開発用 ツ ールおよ びラ イ ブラ リ は， 現時点で最新のも のを 使用し た。
表 4.1: FPGAの開発環境
項目 説明
CPU AMD Opteron(TM) Processor 6238 (48コ ア) メ モリ DDR3 SDRAM 271GB
スト レ ージ ST320DM000-1BC14C (SATA 3.0, 320GB) OS Scientific Linux 6.1
カ ーネ ル 2.6.32-504.30.3.el6 (64ビッ ト 版) 開発ツ ール ISE Design Suite 14.7
MIGラ イ ブラ リ Memory Interface Generator 3.92
表4.2に， 実験に用いたFPGAボード の特徴を 簡単に示す。 こ れら の機材は市販のも の を そのま ま 使用し て おり ， 未改造の状態である 。
表 4.2: FPGAボード の特徴
項目 説明
製品名 Xilinx社 Virtex-6 FPGA ML605R 評価キッ ト FPGA Virtex-6 XC6VLX240T-1FFG1156
ク ロ ッ ク 200MHz (MIGラ イ ブラ リ が出力) 搭載メ モリ DDR3 SO-DIMM， 512MB
4.1.2 隣接 LSH 探索の評価
実験パラ メ ータ
実験条件・ 実験パラ メ ータ は表4.3の通り である 。 ハッ シュ 値のビッ ト 数L0と 隣接LSH 探索のハミ ン グ半径rnについて は， Yangの手法は文献[4]のも のであり ， 提案手法は付 録A.2で求めた最適値である 。 Yangの手法のス ク リ ーニン グと 精査の閾値は文献[4]の 5.2.2節を 参考にし て ， 25%ま での歪み率を 想定し て 決定し た。
表 4.3: 隣接LSH探索の評価実験の条件
項目 Yangの手法 提案手法
試行回数 300 300
ク エリ 指紋の歪み率pber 0〜0.5 0〜0.5 スク リ ーニン グの閾値ε1 24 24
精査の閾値ε2 1024 1024 ハッ シュ のビッ ト 数L0 13 20 隣接LSH探索のハミ ン グ距離rn 0 0
な お指紋の元と な っ た音楽はYangと 同じ も のであり ， 300曲を 指紋DB化し た。 ク エ リ 指紋の歪み(ビッ ト 誤り)について も ， Yangと 同様に乱数で機械的に付与し た。
検索速度
現実の音楽データ でま ずは検索速度を 評価する 。 Yangが用いた 300曲から HiFP2.0で 指紋DBと ハッ シュ テーブルを 構築し ， メ モリ に全データ を 格納する 。 その後ク エリ 指紋 と し て ， 300曲の指紋にラ ン ダムに歪みを 付与し たも のを 検索システムに入力し ， 検索時 間を 測定する 。
表4.4， 図4.1が実験結果である 。 提案手法の方が平均検索速度において 約6.3倍高速で
表 4.4: Yangの手法と 隣接LSH探索の検索時間
歪み率 Yangの手法の 提案手法の
検索時間(ク ロ ッ ク 数) 検索時間(ク ロ ッ ク 数)
0.00 3,459 781
0.05 6,495 970
0.10 12,850 1,597
0.15 26,838 3,259
0.20 64,244 8,610
0.25 324,776 75,706
0.30 410,223 71,466
0.35 403,908 66,413
0.40 403,561 66,211
0.45 403,553 66,208
0.50 403,553 66,208
0 1 2 3 4 5
0 0.1 0.2 0.3 0.4 0.5
検索時間 (メガクロック数)
歪み率 pber
Yangの手法(理論値) 提案手法(理論値) Yangの手法(実験値) 提案手法(実験値)
図 4.1: 歪み率と 平均検索時間
検索精度
検索精度について は図4.2の通り Yangの手法も 隣接LSH探索も 同程度であっ た。 なお 不正解指紋を 返し た件数(“一致な し”ではな く 別の指紋を 誤っ て 返し た件数)は0であっ たため， 図表には正答率のみを 記載し た。
表 4.5: Yangの手法と 隣接LSH探索の検索精度
歪み率 Yangの手法の 提案手法の
正答率 正答率
0.00 1.00 1.00
0.05 1.00 1.00
0.10 1.00 1.00
0.15 1.00 1.00
0.20 0.41 0.42
0.25 0.00 0.00
0.30 0.00 0.00
0.35 0.00 0.00
0.40 0.00 0.00
0.45 0.00 0.00
0.50 0.00 0.00
0 0.2 0.4 0.6 0.8 1
0 0.1 0.2 0.3 0.4 0.5
正答率
歪み率 pber
Yangの手法(理論値) 提案手法(理論値) Yangの手法(実験値) 提案手法(実験値)
図 4.2: 歪み率と 検索精度
4.1.3 リ ソ ース使用量
実装し た指紋検索モジュ ール(Staged LSHモジュ ール)のリ ソ ース使用量は表4.6の通 り である 。 隣接LSH探索を 追加実装し て も 最大で約1.5%の増加であっ た。
表 4.6: 実装し た指紋検索モジュ ール(Staged LSHモジュ ール)のリ ソ ース使用量
項目 従来手法 提案手法
Number of Slice Registers 467 471
Number of Slice LUTs 2206 2235
Number of fully used LUT-FF pairs 329 334
Number of bounded IOB 115 115
Number of BUFG/BUFGCTRLs 1 1
4.2 千万曲分の乱数指紋 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の通り で ある 。
表 4.7: FPGAの開発環境
項目 説明
CPU AMD Opteron(TM) Processor 6238 (48コ ア) メ モリ DDR3 SDRAM 271GB
スト レ ージ ST320DM000-1BC14C (SATA 3.0, 320GB) OS Scientific Linux 6.1
カ ーネ ル 2.6.32-504.30.3.el6 (64ビッ ト 版) 開発ツ ール Vivado 2015.2
MIGラ イ ブラ リ Memory Interface Generator 7 Series Version 2.3 (Rev. 2)
PCIeラ イ ブラ リ Virtex-7 FPGA Gen3 Integrated Block for PCI Express Version 4.0 (Rev. 1)
表 4.8: FPGAボード の特徴
項目 説明
製品名 Xilinx社 Virtex-7 FPGA VC709R コ ネ ク ティ ビティ キッ ト FPGA Virtex-7 XC7VX690T-2FFG1761C
ク ロ ッ ク 250MHz (PCIeラ イ ブラ リ が出力)
搭載メ モリ DDR3 SO-DIMM， 2個， 各4GB， 理論性能は10.4GB/s PCIe PCI Express 3.0 x8， 理論性能は6.8GB/s
表 4.9: デスク ト ッ プPCの仕様
項目 説明
CPU IntelXeonR CPU E5-1620 v3 (4R コ ア) メ モリ DDR4 33.6GB (実験では28GiB使用) スト レ ージ DT01ACA050 (SATA 3.0, 500GB)
I/O PCI Express 3.0 x8な ど
OS Ubuntu 14.04.2 Long Term Support カ ーネ ル 3.16.0-45-generic (64ビッ ト 版)
