超高速データサイエンス

WebDB夏のワークショップ2025、オーガナイズドセッション、2025/9/16 @浜松
https://amagata-daichi.notion.site/20ab718c179d80d9aa83d1962eb64283

松井勇佑（東京大学）http://yusukematsui.me/index_jp.html

Transcript

1. https://bit.ly/3IeOHDq 1 超高速データサイエンス WebDB夏のワークショップ2025, オーガナイズドセッション 2025/9/16 @浜松 松井勇佑 （東京大学・講師） 天方大地 （大阪大学・准教授） 塩川浩昭 （筑波大学・准教授） 西村真衣 （オムロンサイニックエックス・ シニアリサーチャー）
2. https://bit.ly/3IeOHDq 2 ➢ JST AIP加速課題「超高速データサイエンス基盤」の取り組みと成果を紹介 ➢ 多様な分野を対象としたDSに関わる様々な処理を高速化するオプションを周知 ➢ コンピュータビジョン、ロボティクス、人工知能、情報検索、データベース ➢ 探索は古典的な技術だが、今再注目され熱い！LLM, RAG, Vector Databases, … 時間 講演者 タイトル 13:30 – 14:05 松井 勇佑@東京大学 LotusFilter: 学習型足切り表による高速な多様近傍探索 14:05 – 14:40 天方 大地@大阪大学 データベースサイズおよび探索結果の公平な削減 15:00 – 15:35 塩川 浩昭@筑波大学 超高速なグラフ問合せとその応用 15:35 – 16:10 西村 真衣@OSX ロボット学習における大規模検索技術の展開と応用 16:30 – 16:55 佐藤 篤樹＠東京大学 Fast PLBF: Partitioned Learned Bloom Filterの高速構築法と理論解析 16:55 – 17:20 木戸 渓人＠大阪大学 動的な高次元データにおける近似最近傍探索 「探索」をキーワードに様々な高速化技法の紹介
3. https://bit.ly/3IeOHDq 3 松井勇佑 ✓ コンピュータビジョン・データ構造・機械学習 ✓ 高速・大規模なAIシステム http://yusukematsui.me 講師（東京大学 情報理工学系研究科 電子情報学専攻） @utokyo_bunny @matsui528 漫画画像のみから漫画意味理解 [Li+, ACMMM 24] 多様な近傍探索 [Matsui, CVPR 25] 機械学習により強化された ブルームフィルタ [Sato & Matsui, NeurIPS 23]
4. https://bit.ly/3IeOHDq 4 LotusFilter: 学習型足切り表による 高速な多様近傍探索 (CVPR2025) 𝒒 𝒙25 𝒙61 𝒙19 松井勇佑 https://arxiv.org/abs/2506.04790
5. https://bit.ly/3IeOHDq 5 𝒒 𝒙13 𝒙28 𝒙25 𝒒 𝜀 𝒙25 𝒙61 𝒙19 𝒙𝑖 − 𝒙𝑗 2 2 ≥ 𝜀 結果は似うる 結果は似ない 概要 高速で多様な近似最近傍探索 通常の近似最近傍探索 多様な近似最近傍探索
6. https://bit.ly/3IeOHDq 6 背景 𝒒 23, 45, 17, … 23, 92 𝒙𝑛 𝑛=1 𝑁 クエリ ベクトル DB 初期探索結果 𝒮 最終結果 𝒦 近似最近傍探索 絞り込み ➢ RAGやCLIP検索などで、多様な探索の需要高まる CLIP CLIP 全部似てると イマイチな場合ある 多様だと嬉しい
7. https://bit.ly/3IeOHDq 7 背景 𝒒 23, 45, 17, … 23, 92 𝒙𝑛 𝑛=1 𝑁 クエリ ベクトル DB 初期探索結果 𝒮 最終結果 𝒦 近似最近傍探索 絞り込み ➢ RAGやCLIP検索などで、多様な探索の需要高まる CLIP CLIP 全部似てると イマイチな場合ある 多様だと嬉しい
8. https://bit.ly/3IeOHDq 8 背景 𝒒 23, 45, 17, … 23, 92 𝒙𝑛 𝑛=1 𝑁 クエリ ベクトル DB 初期探索結果 𝒮 最終結果 𝒦 近似最近傍探索 絞り込み ➢ RAGやCLIP検索などで、多様な探索の需要高まる ➢ 絞り込み：部分集合選択問題 argmin 𝒦⊆𝒮, 探索誤差 + 多様化誤差 問題①：集合選択 は近似しても遅い 問題②：全ての既存方式は 生データにアクセス 問題③：既存方式は探索と 密結合。最新探索を使えない
9. https://bit.ly/3IeOHDq 9 背景 𝒒 23, 45, 17, … 23, 92 𝒙𝑛 𝑛=1 𝑁 クエリ ベクトル DB 初期探索結果 𝒮 最終結果 𝒦 近似最近傍探索 絞り込み ➢ RAGやCLIP検索などで、多様な探索の需要高まる ➢ 絞り込み：部分集合選択問題 argmin 𝒦⊆𝒮, 探索誤差 + 多様化誤差 問題①：集合選択 は近似しても遅い 問題②：全ての既存方式は 生データにアクセス 問題③：既存方式は探索と 密結合。最新探索を使えない 提案： 近いものを事前に表に記録。探索結果を表引きで貪欲に削る。 ➢ 貪欲削除なので早い。0.02 [ms/クエリ]。 ➢ 探索時に生データ不要。 ➢ 後処理モジュール。最新探索と組み合わせ可能。
10. https://bit.ly/3IeOHDq 1 2 3 6 4 5 14 8 10 9 12 13 7 11 10
11. https://bit.ly/3IeOHDq 1 2 3 6 4 5 14 8 10 9 12 13 7 11 𝑘 ℒ𝑘 1 4, 8 2 3 11, 14 4 1, 8 5 10 6 7 12 8 1, 4 9 10 5 11 3, 14 12 7 13 14 3, 11 提案（前処理） 𝜀 ➢ 足切りパラメータ𝜀 ➢ 各点について、𝜀より 近い点のIDを記録 11
12. https://bit.ly/3IeOHDq 1 2 3 6 4 5 14 8 10 9 12 13 7 11 𝒒 𝑘 ℒ𝑘 1 4, 8 2 3 11, 14 4 1, 8 5 10 6 7 12 8 1, 4 9 10 5 11 3, 14 12 7 13 14 3, 11 𝒮 = 5, 10, 3, 14, 7, 11 提案（探索） クエリに対し、まず 近似最近傍探索 12
13. https://bit.ly/3IeOHDq 5 10 9 1 2 3 6 4 14 8 12 13 7 11 𝒒 𝑘 ℒ𝑘 1 4, 8 2 3 11, 14 4 1, 8 5 10 6 7 12 8 1, 4 9 10 5 11 3, 14 12 7 13 14 3, 11 𝒮 = 5, 10, 3, 14, 7, 11 𝒦 = { } 提案（探索） 13
14. https://bit.ly/3IeOHDq 10 9 1 2 3 6 4 14 8 12 13 7 11 5 𝒒 𝑘 ℒ𝑘 1 4, 8 2 3 11, 14 4 1, 8 5 10 6 7 12 8 1, 4 9 10 5 11 3, 14 12 7 13 14 3, 11 𝒮 = 5, 10, 3, 14, 7, 11 𝒦 = {5} 提案（探索） Pop 第一候補を採用 14
15. https://bit.ly/3IeOHDq 9 1 2 3 6 4 14 8 12 13 7 11 5 10 𝒒 𝑘 ℒ𝑘 1 4, 8 2 3 11, 14 4 1, 8 5 10 6 7 12 8 1, 4 9 10 5 11 3, 14 12 7 13 14 3, 11 𝒮 = 5, 10, 3, 14, 7, 11 𝒦 = {5} 提案（探索） Pop 第一候補を採用 近い点を 表引き 15
16. https://bit.ly/3IeOHDq 9 1 2 3 6 4 14 8 12 13 7 11 5 10 𝒒 𝑘 ℒ𝑘 1 4, 8 2 3 11, 14 4 1, 8 5 10 6 7 12 8 1, 4 9 10 5 11 3, 14 12 7 13 14 3, 11 𝒮 = 5, 10, 3, 14, 7, 11 𝒦 = {5} 提案（探索） Pop 近い点を 表引き 第一候補を採用 消す 16
17. https://bit.ly/3IeOHDq 3 11 9 10 1 2 6 4 8 12 13 7 5 𝑘 ℒ𝑘 1 4, 8 2 3 11, 14 4 1, 8 5 10 6 7 12 8 1, 4 9 10 5 11 3, 14 12 7 13 14 3, 11 14 𝒒 𝒮 = 3, 14, 7, 11 𝒦 = {5} 提案（探索） 17
18. https://bit.ly/3IeOHDq 9 10 1 2 6 4 8 12 13 7 5 𝑘 ℒ𝑘 1 4, 8 2 3 11, 14 4 1, 8 5 10 6 7 12 8 1, 4 9 10 5 11 3, 14 12 7 13 14 3, 11 3 14 11 𝒒 𝒮 = 3, 14, 7, 11 𝒦 = {5, 3} Pop 提案（探索） 第二候補を採用 18
19. https://bit.ly/3IeOHDq 9 10 1 2 6 4 8 12 13 7 5 𝑘 ℒ𝑘 1 4, 8 2 3 11, 14 4 1, 8 5 10 6 7 12 8 1, 4 9 10 5 11 3, 14 12 7 13 14 3, 11 3 14 11 𝒒 𝒮 = 3, 14, 7, 11 𝒦 = {5, 3} Pop 提案（探索） 近い点を 表引き 第二候補を採用 19
20. https://bit.ly/3IeOHDq 9 10 1 2 6 4 8 12 13 7 5 𝑘 ℒ𝑘 1 4, 8 2 3 11, 14 4 1, 8 5 10 6 7 12 8 1, 4 9 10 5 11 3, 14 12 7 13 14 3, 11 3 14 11 𝒒 𝒮 = 3, 14, 7, 11 𝒦 = {5, 3} Pop 提案（探索） 近い点を 表引き 消す 第二候補を採用 20
21. https://bit.ly/3IeOHDq 14 11 9 10 1 2 6 4 8 12 13 7 5 𝑘 ℒ𝑘 1 4, 8 2 3 11, 14 4 1, 8 5 10 6 7 12 8 1, 4 9 10 5 11 3, 14 12 7 13 14 3, 11 3 𝒒 𝒮 = 7 𝒦 = {5, 3} 提案（探索） 21
22. https://bit.ly/3IeOHDq 22 計算量 𝑂 近傍探索 + 𝑆 + 𝐾𝐿 ➢ 𝒮は「Pop」と 「要素削除」が必要 ➢ 𝒮をOrderedSetで表現すると 初期探索結果𝒮 の大きさ 最終トップK 表の平均 要素数 ➢ 速い ➢ 登場変数 スキャンと同じ
23. https://bit.ly/3IeOHDq 23 評価 多様化方式 性能（↓） 合計実行時間（↓） メモリオーバーヘッド 無し（探索のみ） 0.20 0.9 [ms/クエリ] 無し クラスタリング 0.22 7.8 [ms/クエリ] 𝒙𝑛 𝑛=1 𝑁 を所持する必要 GMM [2] 0.18 14.4 [ms/クエリ] 𝒙𝑛 𝑛=1 𝑁 を所持する必要 LotusFilter（提案） 0.17 1.0 [ms/クエリ] 表のために追加メモリ 探索無視し多様化 GMM・クラスタリングは遅く、 元データの所持が必要 ➢ 提案は高速 省メモリ ➢ 探索のみとほぼ同じ 速度で多様化達成 [1] Markov+, “Efficient and Robust Approximate Nearest Neighbor Search using Hierarchical Navigable Small World, TPAMI 2020 [2] Ravi+, “Heuristic and Special Case Algorithms for Dispersion Problems”, OR 1994 3.2 GHz Intel Xeon 仮想32コア 64 GiBメモリ (aws c7i.8xlarge) OpenAIデータセット（𝑁 = 9 × 105, 1536次元） 近似最近傍探索：HNSW [1] 𝒮にk-means
24. https://bit.ly/3IeOHDq 24 まとめ 𝒒 𝜀 𝒙25 𝒙61 𝒙19 ✓ 高速な多様近傍探索 ✓ 探索結果を表引きで貪欲削除 メリット： ➢ 貪欲削除なので早い。0.02 [ms/クエリ] ➢ 探索時に生データ不要 ➢ 独立した後処理モジュール デメリット： ➢ 訓練・表構築ステップ ➢ 表のためのメモリ消費 ➢ 𝐾を事前に決定 Y. Mtasui, “LotusFilter: Fast Diverse Nearest Neighbor Search via a Learned Cutoff Table”, CVPR 2025 https://arxiv.org/abs/2506.04790
25. https://bit.ly/3IeOHDq 25 ライブラリ紹介 https://github.com/matsui528/lotf $ pip install lotf ノウハウ共有 ➢ faissに合わせたAPI設計 ➢ nanobindでpython中からc++を使う ➢ boost unordered ➢ AIコーディング
26. https://bit.ly/3IeOHDq 26 ライブラリ紹介：faissに合わせたAPI設計 import lotf import faiss import numpy as np Xb = np.random.rand(10000, 128).astype('float32') Xq = np.random.rand(5, 128).astype('float32') index = faiss.IndexFlatL2(Xb.shape[1]) index.add(Xb) epsilon = 15.0 ctable = lotf.CutoffTable(X=Xb, index=index, epsilon=epsilon) candidate_k = 300 candidate_dists, candidate_ids = index.search(Xq, candidate_k) final_k = 100 diverse_dists, diverse_ids = ctable.filter( dists=candidate_dists, ids=candidate_ids, final_k=final_k ) faissのインデックス構築 前処理：足切り表構築 faissの探索 faissの探索結果 を多様化 ➢ 探索の研究は「ツールの提供」 ➢ オレオレAPIではなくデファクトを大事に
27. https://bit.ly/3IeOHDq 27 ライブラリ紹介：nanobindでpython中からc++を使う ➢ c++で書いて終わりにせず、pythonインタフェースを提供しよう ➢ pybind11が有名 同じ作者が新しく作ったnanobindがオススメ std::vector<int> double_it(const std::vector<int> &in) { std::vector<int> out(in.size()); for (size_t i = 0; i < in.size(); ++i) out[i] = in[i] * 2; return out; } ➢ 変数のやり取りがシンプルでモダンで効率的 ➢ numpy arrayにconst参照で触れる https://nanobind.readthedocs.io/en/latest/exchanging.html
28. https://bit.ly/3IeOHDq 28 ライブラリ紹介：boost unordered ➢ 最近のboostには良いものが結構ある。要チェック ➢ stdの代替になりうる ➢ std::unordered_set boost::unordered_flat_set 多少だが確実に高速 https://www.boost.org/doc/libs/latest/libs/unordered/doc/html/unordered/intro.html ➢ std::unorderedはclosed addressing ➢ boost::unordered_flatはopen addressingの ハッシュテーブルを提供 ➢ 近年のコンピュータでは、キャッシュ的にopen addressingのほうが基本的に強い（らしい） ➢ SIMDもバリバリ使う 詳細解説。オススメ！
29. https://bit.ly/3IeOHDq 29 ライブラリ紹介：AIコーディング ➢ AIコーディングはやるべき ➢ 2025/9月現在、とりあえずclaude codeとか ➢ 忙しいPIでもコーディングが出来うる世界になった “SphinxにFuroのテーマ でドキュメント作って” Claude code
30. https://bit.ly/3IeOHDq 30 PhD学生募集中！ ➢ 松井研では2027/4以降入学のPhD学生（現M1）を募集しています！ ➢ 研究領域：コンピュータビジョン、データベース、機械学習、etc ➢ 求める人材： ✓ 研究大好き（最重要） ✓ トップ会議・トップ論文誌採択経験があると良いです ➢ 応募希望の方は必ず指導教員と相談したうえで松井まで連絡ください ➢ 社会人博士も受け付けています ➢ WebDB2025にはフル参加しますので、 興味があるという方はカジュアルに お声がけください 研究室ブログで雰囲気が わかるかもしれません https://mti-lab.github.io/blog/