Stop-the-world

2025振り返り

Takuya Asano — Fri, 02 Jan 2026 07:44:22 GMT

2026年になりましたね。年末年始は年越しキャンプに行っていたため年を跨いでしまいましたが、1年間の振り返り記事を書いておきます。

過去の振り返り記事はこちら。

仕事

AIエンジニアリングを始めた

3月にAIエージェントの実証実験（PoC）をやることになり、MLエンジニアと2人で、LegalOnのエージェント機能のデモを開発しました（製品開発チームがその流れを引き継ぎ、LegalOn Agentsとしてリリースされました）。その後、いくつかのAIエージェント系のプロジェクトを担当して今に至ります。

自分はここ最近ずっと検索・推薦の領域をやってきたので、ジョブチェンジに近い感じです。ということで、今年1年はAIエージェント系の技術をキャッチアップに明け暮れていました。いわゆるアンラーニングというやつかも。

検索・推薦に近いところには身を置きつつ、2026年もAIエージェントの開発をやっていくことになりそうです。

アウトプット

デブサミに登壇した

去年に公募で通過したDevelopers Summit 2025が2月にありました。LegalOnの広報の方にもかなりサポートいただいて、何とか形にはなりました。

詳細なレポートは会社ブログの方に書きました。発表したスライドへのリンクもあります。

CodeZineさんの記事もこちらに上がっていますので、よろしければどうぞ。

プロダクトの価値を高めるためにコーディング以外にできることは？コミュニケーション4つの工夫

「言っていることが伝わらない」「忙しそうで話しかけづらい」――そんな“すれ違い”が、チーム開発の足を引っ張ってはいないだろうか。本セッションではLegalOn Technologiesの浅野卓也氏が、専門用語によるミスコミュニケーションの事例や、職種間の情報格差を埋めるために開催した勉強会、対話の頻度を高める取り組みなどを紹介。実践に基づいた具体的な工夫から、異職種との連携をスムーズにするためのヒントを得よう。

CodeZine夏野かおる

AIエージェント入門の社内セミナーをやった

社内のプロダクトマネージャーやエンジニア向けに、AIエージェントの入門講座を開催しました。2024年に検索・推薦技術についての入門講座を開きましたが、それのAIエージェント版とも呼べるような内容になっています。

SNS経由で広まったためか、ITmediaさんにも記事にしていただいていました。

AIエージェントを“速習”できる入門資料、法務AIサービス企業が無料公開 - ITmedia AI＋

2025年にかなりの時間を割いてインプットした、AIエージェント関連の情報を整理して（技術的な詳細は省きつつ）まとめたので、個人的にも良い学習になりました。

社内でも好評でしたし、対外的にもそこそこ広く認知してもらえたので、三方よしということで、提案して良かった取り組みだったなと思います。

社内資料「速習 AIエージェント入門」を公開します - LegalOn Technologies Engineering Blog

こんにちは。LegalOn Technologiesでソフトウェアエンジニアをしている浅野（@takuya_b / @takuya_a）です。最近は検索推薦というよりはAIエンジニアっぽいことをしています。このたび、社内の全プロダクトマネージャー・デザイナー・エンジニア・EM向けに「速習 AIエージェント入門」というタイトルで、AIエージェント開発の社内セミナーを担当しました。その発表で使用したスライドを、弊社のSpeaker Deckに公開しましたので共有します。昨年、弊社のブログ「社内資料「プロダクトマネージャーのための検索推薦システム入門」を公開します」の中で検索推薦技術の入門講座の…

LegalOn Technologies Engineering Blogtakuya-a

まるで福利厚生！「AIエージェント」を正しく理解するための社内セミナーをやったら反響あった｜LegalOn Now

こんにちは！LegalOn Technologies採用担当の堀次です。 2025年11月5日、11月13日に、PdM・デザイナー・エンジニア・EMを対象とした「速習 AIエージェント入門」が開催されました！・DAY1（11/5）：PdM・デザイナー向け・DAY2（11/13）：エンジニア・EM向け講師は、我らがStaff Software Engineerの浅野卓也です。 AIエージェントは、もはや当社では耳にしない日がないけれど、用語だけ先行して理解が追い付いていなかったり、情報が多すぎて整理できてない人も多いのではないでしょうか。そんな中、知識や用語を整理し全員が

note（ノート）LegalOn Now

その他のアウトプット・インタビュー記事

社内LT会で「なぜ技術ブログを書くのか」というタイトルで発表しました。ここ最近、自分があまり書けていないので完全にブーメランなのですが……。2026年は小ネタでもいいので、自分のブログにもちょいちょい書いていきたい。

1Qお疲れ様でした！お寿司を囲みながら、振り返りと見直しの大切さを語るLTに｜LegalOn Now

2023年度に自分がリードしていた、LegalOnの検索推薦基盤の開発に関するインタビュー記事が上がっています。今の会社に入ってからの流れが激しすぎて、もう5年くらい前に感じる。

第8回「LegalOn」誕生の裏側：検索編 - LegalOn Technologies Engineering Blog

コミュニティ活動

検索技術勉強会

今年も @johtani さん達のおかげで開催できました。今年は検索技術領域から離れたというのもあって、あまり主体的にコミットできなかったので反省。

2026年には早速1月にシェルパ・アンド・カンパニーさんで開催予定なので、よろしくお願いします！（スピーカーも募集中です！）

Search Engineering Tech Talk 2026 Winter (2026/01/28 19:00〜)

# 勉強会・懇親会での飲食の提供の予定はありません。会場での飲食は可能ですので持ち込みで発表をお聞きいただくことはできます。 Search Engineering Tech Talk第10回目となります。検索技術勉強会の目的は、「検索」/「検索システム」にまつわる技術や手法に関して共有できる場を提供することです。検索エンジンごとの勉強会などもありますが、検索エンジンには関係なく、「検索」というシステム、サービスを作る上で共通の解決すべき課題があります。これらの課題をみんながどのように解決しているのかといった知識を共有できる場になればと思っています。 # タイムテーブル ...

connpass

LayerXさんとの合同ミートアップ

検索技術勉強会の懇親会でのLayerXの鷹取さん、ponさん、澁井さんとの会話から、2社合同でのミートアップを開催しました。検索技術も新しい局面を迎えていることを肌で感じられる、良いイベントでした。次回はLayerXさんのオフィスで開催したい！

LayerXさんと「LLM＆Search MeetUp」を開催しました！発表資料を公開します｜LegalOn Now

こんにちは！LegalOn Technologiesの堀次です。 2025年12月9日（火）、株式会社LayerXさんと合同で『LLM＆Search MeetUp』を開催しました！ LLMの進化が加速する今、検索技術はその性能を最大限に引き出すための重要な技術となっています。同じB2B SaaS領域のリーディングカンパニーとして検索技術に注力しているLayerXさんとタッグを組み、お互いの知見を共有し合うミートアップを企画しました。生成AI時代における検索の進展と実務への応用について、両社のエンジニアが話しました！ LLMを利用した検索機能の改善 RAGの精度改善

note（ノート）LegalOn Now

生活・趣味

MtGも一応続けてます

MTG Arenaはほとんど起動しなかったけど、紙のドラフト・シールド・統率者は引き続き身内コミュニティで続けています。

メルカリ時代の同僚の和田さんのコミュニティでセット発売ごとにドラフト
LegalOn社内で統率者、時々シールド
はてな時代の友達や、その繋がりで知り合ったエンジニアの方と、EDHやらシールドやら

今年は1回くらい競技イベントにも出てみたいなと思っていましたが、時間が取れず断念。来年こそ。

山にあまり行けなかった

埼玉の低山に登ったくらいで、本格的な登山はゼロでした。まずは体力をつけねば。谷川岳あたりに登ってみたい。あと、ずっと棚上げしていた剱岳のリベンジも。

自転車も再開できず

オダックス埼玉の秋の走行会に参加する予定でしたが、前述の通り、業務が忙しすぎて準備が間に合わないと判断して断念（DNS）。来年、落ち着いてからまた考えます。

本はたくさん読めた

今年は本をけっこう読めました。お風呂にKindle Paperwhiteを持ち込んで読むのが習慣化されたのが効きました。

Kindleなので、辞書を引いたり翻訳しながら読んだりが難しいので、英語で書かれた本がほとんど読めなかったのが課題です。洋書だけでなく、しっかり読み込みたい本はやはりPCで読むのが良いですね。

Nixによる環境管理を始めた

業務用のMacBookの更新を機に、Nixで設定やパッケージ管理するようにしました。正攻法でやると学習コストがかなり高いのが障壁なのですが、コーディングエージェントを使って一通りの環境が作れました。

GitHub - takuyaa/dotfiles

Contribute to takuyaa/dotfiles development by creating an account on GitHub.

GitHubtakuyaa

コマンド一発で環境がほぼ再現できるのは本当に驚きでした。また、設定が一箇所で管理できるのは認知負荷が低く、コーディングエージェントとの相性も抜群です。

設定の追加やパッケージのインストールも自然言語でできます。特に、Nixpkgsにパッケージがあればそれを、Homebrewにしかなければそれをインストールしたい、みたいなことが一言指示するだけでできるのは想像以上に便利です。

本の執筆を開始した

ありがたいことに、1月に検索技術に関する書籍のお話をいただきました。かなり迷ったのですが、えいやで引き受けることにしました。今のところ、業務とは関係なくプライベートの時間でやっているので、なかなか進みが遅いのですが、2026年中に何とか形にしたいと考えています。

健康面

ここ数年、座ったままの姿勢が長く、運動不足も相まって腰痛や肩こりにずっと悩まされています。散歩を習慣化したり、整体には通ったりはしてみているものの、抜本的な改善も見込めず、業務にも支障が出てきました。

2026年は作業環境の見直しと、ランニング・筋トレあたりを習慣化するのが目標になりそうです。

おわりに

今年はまあまあ大変な1年でした。仕事で求められるロールが大きく変わったため、膨大なインプットと業務上の成果を両立する必要がありました。それに加えて、デブサミでの登壇やら社内セミナーの準備やらもあり、ずっと働いてたなあという印象でした。

来年はもう少し仕事量を抑えて、健康面とプライベートの優先度を上げていきたい（毎年言ってる気がする）。

ではでは。

2024振り返り

Takuya Asano — Sun, 05 Jan 2025 08:11:32 GMT

あけましておめでとうございます。だいぶ遅くなってしまいましたが、2024年の振り返りです。

去年までの振り返りはこちら：

生活

投資を始めた

新NISA？ってやつをやっておくといいらしいので積立の設定とかしました。SBIのUIが難しすぎる。Discordで画面共有しながら設定方法を教えてもらってなんとか設定できました。

元同僚のt_くんに感謝。こんど焼肉おごります。

コーヒー

豆乳を買ってきてソイラテを作るようになりました。体質的に朝に（牛乳の）ラテを飲むとお腹を壊しがちなのですが、ソイラテだと大丈夫。最初は無調整豆乳を買ってきて試したが、あっさりしすぎていてイマイチ。調整豆乳のほうが絶対おいしい。

ラテアートは上達しなかった。

mixi2

mixi2が始まりましたね。最近SNSが増えすぎてどう使い分けていくのがいいのか悩んでます。

あ、はてな卒業生のためのex-hatenaコミュニティをつくりました（現役もOK）。いつかコミュでオフ会したい。

趣味

ポケカを始めた

Pokémon TCG Live（通称 PTCGL）からポケカを始めました。PTCGLはMTG Arenaとは違ってじゃんじゃんカードを配ってくれるので、ほとんどお金をかけなくてもtier 1デッキで遊べるので最高。

PTCGLはアメリカ・カナダでしかサービス提供されていないため、VPNが必要です。通常は月額500円〜1000円くらいのVPNサービスを契約するのですが、その費用をケチるためにus-west1（バージニア）に無料のGCEインスタンスを立ててそこにTailscaleをインストールし、 PTCGLをプレイするときはそのインスタンス経由でインターネットに出ていくということをしています。

PTCGL VPN設定

紙でもリザードンexの構築済みデッキからデッキを組みました。社内の大会にも出場できてよかった。

ポケポケもやってます

Pokémon Trading Card Game Pocketことポケポケを始めました。こっちはスマートフォンでできます。5分～10分くらいで遊べるので休憩時間とか移動時間に遊べるのが良い。対人戦ではミュウツーexのデッキを擦り続けていますが、幻の島環境で新しく出てきたセレビィexとギャラドスexがきつい。対人戦278勝で、300勝が見えてきた。よかったらフレンド登録お願いします。

マジック：ザ・ギャザリング

相変わらずリミテッド（シールド・ドラフト）ばっかりやってます。

前職の同僚が主催するリミテ会に参加させてもらうようになりました。初回はブルームバロウのシールドで0-3、つまり全敗したんですが、最近やったファウンデーションズのドラフトでは、Arenaでしっかり練習していったのとピックの運が異常に良くて優勝できました。運に恵まれた結果ではあれど、競技マジックをしっかりやっている人たちの中で勝てたのは少し自信がつきました。

あとは会社の人たちや友達と統率者を何回かやったくらい。2025年はもっと統率者と構築もやっていきたい。

ドラマ・アニメ

Netflix限定ですが、「三体」と「地面師たち」よかったですね。

Watch 3 Body Problem | Netflix Official Site

Watch Tokyo Swindlers | Netflix Official Site

アニメはアオのハコを観ているけど、青春の眩しさで体が溶けてしまいそうです。すまんがその石をしまってくれんか、わしには強すぎる……。

Watch Blue Box | Netflix Official Site

コミュニティ活動・アウトプット

検索技術勉強会

今年も無事に続けられました。

といっても大谷さんたち他のスタッフのおかげなのですが。改めてスタッフやスピーカー、そして参加者のみなさんに感謝。

OSS

Cookiecutter と copier の Python プロジェクトテンプレートをそれぞれ作りました。どちらも uv ベースです。

copier の方が後発だけあって洗練されている印象です。

2024年は仮想環境含め、uv だけで完結するようになってきました。数回コマンドを叩くだけで Python プロジェクトがセットアップできるので重宝しています。

Reactを触ってみた

モダンなスタックで React のチュートリアル（いわゆる3目並べ）をやってみました。

https://github.com/takuyaa/react-tutorial-tic-tac-toe

https://github.com/RicardoValdovinos/vite-react-boilerplate をベースにしました。Vite の体験がよかったのが印象に残っています。

IR Reading

今年も IR Reading （2024春）で発表しました。Multi-index hybrid query という問題設定において、multi-way merge アルゴリズムを使って高速化するという論文でした。

IR Reading 2024 Spring: OneSparse: A Unified System for Multi-index Vector Search - Google スライド

IR Reading 2024秋のほうも聴講で参加させていただきました。アカデミアの空気感を感じられる貴重なイベントなので、このまま永遠に続いてほしい。

社内LT会

エンジニア主催のLT（Lightning Talk）イベント「Tech All-in」を開催しました！｜LegalOn Now

社内でLT会をやるというので、kind (Kubernetes in Docker) というツールについて話しました。15分くらい話したのでLTではない気はする。上がってきた記事を見てみたら「なにわの検索エンジニアリングスペシャリスト」という新しい二つ名がついていました。

ブログ

ブログは2件だけ。2025年は短くていいからもっと記事出したい。

チームとしては以下の12記事が出せました（すごい！）。

デブサミ2025（予定）

会社で出した公募が通って、2025年2月のデブサミ2025で登壇することになりました。これまで参加したことなかったんですが、かなり大きいイベントみたいなので、すでに緊張してます。

プロダクトの価値を高めるためにコーディング以外にできること～共通言語でつくる異職種コミュニケーション～ - Developers Summit 2025

仕事

エンジニアリングマネージャーを経験した

前任者の退職に伴い、2月からEMの職責を担うようになりました。もともとテックリードの責務も負っていたので、以下の図^[1]でいうところの真ん中の領域にいたことになります。

実際、短期的な締め切りに追われる仕事でスケジュールが埋め尽くされ、中長期的なビジョンを考えたりするのは難しかった。そのまま燃え尽きる可能性もあったので、EMのロールを引き剥がしてくれたマネージャーには感謝しています。

EMを経験できたこと自体はよかったと感じています。マネージャーの立場からでないと見えない視点みたいなものは獲得できた気がします。螺旋階段を1周登った感覚がありました。

OSSなどから学んだヒューマンスキルと経験を武器に。人生最大の挫折を越えてなおも歩む螺旋のキャリア - Findy Engineer Lab

新規プロダクトをローンチした

去年の春ごろから開発を進めていた新規プロダクトLegalOn Cloudを4月にローンチしました。自分は検索・推薦基盤全体の開発のリードをやっていました。

関連する5つ以上のチームとコミュニケーションしながら短期間でフルスクラッチの大規模新規開発するという、かなりチャレンジングなプロジェクトで痺れました。人生で2番目くらいに大変だった。この顛末はそのうち会社のブログにでも書きたい。

まとめ

仕事しかしてない1年だったような印象があったけど、意外といろいろやってました。

2025年もいろいろやっていきたいですね。それでは。

https://newsletter.pragmaticengineer.com/p/engineering-leadership-skillset-overlaps ↩︎

近似最近傍探索における新しいビット量子化手法、RaBitQとBBQ

Takuya Asano — Thu, 26 Dec 2024 06:17:01 GMT

Elasticsearch 8.16 で Better Binary Quantization (BBQ) という、新しい密ベクトルのフィールドタイプが追加されました。

Elasticsearch ではベクトルの各次元の int8 や int4 への量子化をサポートしていますが、BBQ ではビットにまで量子化することで、さらなるインデックスサイズの削減と近似近傍探索の高速化を図っています。

この記事では、まず BBQ の元になった RaBitQ^[1] というベクトル量子化手法を解説します。そのあと、Elasticsearch における BBQ の実装について説明し、RaBitQ と BBQ の違いについて触れます。

この記事は情報検索・検索技術 Advent Calendar 2024 の 25 日目の記事です。

近似最近傍探索 (ANN)

RaBitQ の前に、その背景となっている近似最近傍探索について簡単に説明します。

ANN の問題設定

あるベクトルが与えられたときに、それから近いベクトルを探すタスクを最近傍探索 (NN query; nearest neighbor query) といいます。近似最近傍探索とは、NN のように exact に近いベクトルを探すのではなく、ある程度の誤差を許容するものです。

D 次元のユークリッド空間を考えます。近似最近傍探索 (ANN query; approximate nearest neighbor query) とは、

クエリベクトル $q$ に対して
$N$ 個のデータベクトルの集合から
$K$ 個の近似最近傍ベクトルを取得 (retrieve) する

という問題設定です。ANN query は単に ANN と呼ばれることもよくあります。そのため、以下では ANN と表記します。

言語モデルとベクトル埋め込み

単語や文、文章など、あらゆるテキストデータは言語モデル (LM; language model) により、ベクトルに変換できます。これをベクトル埋め込み (vector embeddings) と呼びます。自然言語処理 (NLP; natural language processing) では通常、100 から 1000 次元程度のベクトルに変換します。このように高次元のベクトル空間に埋め込まれたベクトルのことを、単に埋め込み (embeddings) と呼ぶこともあります。

近年のLM の急速な発展により、「質のよい」ベクトル埋め込みが簡単に計算できるようになりました。つまり、埋め込まれたベクトル空間上で近いベクトル同士は意味が近いとみなせる、ということです。この性質は情報検索 (information retrieval) などのタスクにおいて重要な意味を果たします。

ANN の重要性

データが1次元であれば、 B-tree などのデータ構造で効率的にインデックス化・検索できますが、多次元になると難しくなります。さらに高次元、たとえば自然言語処理で使用されるような 1000 次元クラスになると、kd-tree のような多次元インデックスも役に立ちません。

そこで一定の誤差が生じることを認め、実際はもっと近いベクトルがあるけれど、だいたい近い (approximate nearest neighbor) ベクトルを返せば OK ということにしましょう、という問題設定が ANN です。

NN query から ANN query に問題を緩和 (relax) することで、高次元のベクトル検索を高速に実行することができます。例えば、FAISS、Annoy、FLANN、ScaNN、NGT、DiskANN といった手法（実装）が有名です。これらの手法は、精度 (recall) をある程度保ちながら高速に ANN の K 個のベクトルを検索することができます。他にも、 ann-benchmarks^[2] というリポジトリには、ANN のメジャーな手法とそのベンチマーク結果がまとまっています。

ANN は現在も活発に研究開発され、日進月歩でその精度と速度が向上しています。ANN に興味をもった方は、以下のスライド^[3]がよくまとまっているので、参考にするとよいでしょう。

近似最近傍探索の最前線 - Speaker Deck

ANN とベクトルの量子化

近似最近傍探索 (ANN) のインデックスには、すべてのデータベクトルを保持する必要があります。各データごとに「次元数 x スカラーのデータサイズ (e.g., float32)」の容量が必要になり、効率的とは言えません。

ベクトルの量子化 (quantization) は、一般には float32 や float64 の配列で表現されるベクトルを、 int8 や int4 などのコンパクトな整数表現等に変換する手法です。ベクトルを量子化することでメモリやディスクの使用量を抑え、また SIMD によって検索処理の高速化を狙います。

量子化に関連する代表的な ANN の高速化手法として、直積量子化 (PQ) と転置ファイル (IVF) がよく知られています。また、量子化とは直接関係はないですが、別の ANN 高速化手段として HNSW というグラフベースのインデックス手法があります。

これらについても以下の資料^[3:1]に詳しくまとまっています。

近似最近傍探索の最前線 - Speaker Deck

直積量子化 (PQ)

代表的なベクトル量子化手法の一つに、直積量子化 (PQ) があります。

ベクトル量子化 (VQ; vector quantization) は、ベクトルの集合を事前計算した K 個のセントロイドで代表する古典的な手法です。VQ では、ベクトルを最も近いセントロイドの ID で表現します。

直積量子化 (PQ; product quantization)^[4] は、ベクトルの次元を M 個に分割して、それらのスライスをそれぞれ VQ する方法です。この M 個の代表ベクトル（の ID）の集合をコードブックと呼びます。PQ では、分割した M 個ごとに近いセントロイドを探し、それら M 個の ID で表現します。

転置ファイル (IVF)

また、直積量子化 (PQ) と組み合わせて検索を効率化するデータ構造として、転置ファイル (IVF) があります。

転置ファイル (IVF; inverted file) もしくは IVFADC (Inverted File with Asymmetric Distance Computation)^[4:1] とは、転置インデックス的な補助データ構造、およびそれを利用したANN の高速化手法です。IVF ではまず、空間をいくつかに分割し、それぞれの部分空間を代表するセントロイドを用意します。ベクトルが与えられたときに、どの部分空間に入るか（＝どのセントロイドが近いか）を計算する粗量子化器 (coarse quantizer) も事前に準備しておきます ^[5]。

IVF は、以下のように、近いベクトルを代表ベクトル（セントロイド）をキーとした転置リストにまとめます^[4:2]。IVF でベクトルを検索するときには、まず量子化したベクトルを計算し、その転置リストを取得します。そのあと得られた転置リストを走査し、最終的な最近傍のベクトルを計算します。

RaBitQ

RaBitQ^[1:1] は、Jianyang Gao & Cheng Long によって提案された、新しい ANN インデックスのベクトル量子化手法です。この方法は、ベクトルの各次元を1ビットに量子化することで、インデックスサイズを小さくし、またビット演算や SIMD を活用することで検索処理を高速化しています。RaBitQ の論文では、PQ と比較したときの優位性についても説明されています。

RaBitQ の概要

RaBitQ のアルゴリズムを、インデックスフェイズ（インデックスの構築）とクエリフフェイズ（インデックスからの検索）に分けて説明します。論文^[1:2]に合わせて以下のように表記します。

表記	説明
$\bm{o_r}$	元のデータベクトル（正規化・量子化前）
$\bm{q_r}$	元のクエリベクトル（正規化・量子化前）
$\bm{o}$	正規化したデータベクトル
$\bm{q}$	正規化したクエリベクトル
$\bm{c}$	セントロイド（中心ベクトル）
$C$	量子化ベクトルのコードブック（集合）
$C_{rand}$	コードブック $C$ をランダム化したもの
$\overline{\bm{x}}$	量子化したデータベクトル（コードブック $C$ の中から選ぶ）
$\overline{\bm{o}}$	量子化したデータベクトル（コードブック $C_{rand}$ の中から選ぶ）、つまり $\overline{\bm{o}} = P \overline{\bm{x}}$
$\overline{\bm{x}}_b$	正規化したデータベクトル $\bm{o}$ を量子化し、ビット表現にしたもの
$\bm{q}\rq$	クエリベクトルをランダム射影の逆行列 $P^{-1}$ で変換したもの（ $\bm{q}\rq = P^{-1} \bm{q}$ ）
$\overline{\bm{q}}$	変換後のクエリベクトル $\bm{q}\rq$ を量子化したもの
$\overline{\bm{q}}_u$	$\overline{\bm{q}}$ の符号なし整数表現

RaBitQ では、データベクトル（$\bm{o_r}$ の集合）を以下のように量子化・インデキシングします（インデックスフェイズ）。

セントロイド $\bm{c}$ を計算し、すべてのデータベクトルを正規化（$\bm{o_r}$ を $\bm{o}$ にする）
ランダムな直交行列 $P$ をサンプリングし、コードブック $C_{rand}$ を構築
量子化されたデータベクトル $\overline{\bm{x}}_b$ を計算（コードブックの中から選ぶ）
以下を事前計算
1. データベクトルとセントロイドとの距離 $\Vert \bm{o}_r - \bm{c} \Vert$
2. 量子化されたデータベクトルと正規化したデータベクトルの内積 $\langle \overline{\bm{o}}, \bm{o}\rangle$

構築されたインデックスに対して、検索は以下のアルゴリズムで行います（クエリフェイズ）。

クエリベクトルを正規化・変換
1.のクエリベクトルを量子化
各データベクトルに対して以下を計算
1. $\frac{\langle \bm{\overline{o}}, \bm{q}\rangle}{\langle \bm{\overline{o}}, \bm{o}\rangle}$ を計算（$\langle \bm{o}, \bm{q}\rangle$ の近似値として使用する。後述）
2. 元のクエリベクトルとデータベクトルの距離の推定値を計算

それでは、RaBitQ の各ステップを詳しく見ていきましょう。まず、インデックスフェイズでもクエリフェイズでも共通で使用されることになる、ベクトルの正規化とコードブックによる量子化について説明します。

ベクトルの正規化

ベクトル $\bm{x}_1, \cdots, \bm{x}_k$ のセントロイド $\bm{c}$ は以下で計算されます。

\[ \bm{c} = \frac{1}{k} (\bm{x}_1 + \cdots + \bm{x}_k) \]

RaBitQ ではまず、与えられたデータベクトル全体から、セントロイド $\bm{c}$ を事前に計算します。

その後、各データベクトル $\bm{o}_r$ に対して、以下のように正規化されたベクトル $\bm{o}$ を得ます：

\[ \bm{o} := \frac{\bm{o}_r - \bm{c}}{\|\bm{o}_r - \bm{c}\|} \]

この様子を可視化したものが以下です^[6]。

多次元コードブック

次に、正規化したベクトルを量子化することを考えます。代表点（コード）の集合＝コードブックを考え、ベクトルをそれに最も近い代表点で表現（近似）することによって量子化できます。

正規化したデータベクトルは、単位球面上に広がって分布することが期待されます^[7]。よってコードブックも、単位球面上に一様に分布するように構成します。コードブックの要素（コード）は単位球面上の点なので、単位ベクトルであることに注意します。

ベクトル空間の次元を $D$ としたとき、自然な構成として、コードブックを以下のようにつくることが考えられます。

\[ C := \lbrace +\frac{1}{\sqrt{D}}, -\frac{1}{\sqrt{D}} \rbrace ^D \]

このように構成したコードブックは、具体的には以下のようになります（コードブックは $2^D$ 個の要素をもちます）。

1次元: $\lbrace +1, -1 \rbrace$
2次元: $\lbrace \lparen +\frac{1}{\sqrt{2}}, +\frac{1}{\sqrt{2}} \rparen, \lparen +\frac{1}{\sqrt{2}}, -\frac{1}{\sqrt{2}} \rparen, \lparen -\frac{1}{\sqrt{2}}, +\frac{1}{\sqrt{2}} \rparen, \lparen -\frac{1}{\sqrt{2}}, -\frac{1}{\sqrt{2}} \rparen, \rbrace$
3次元: $\lbrace \lparen +\frac{1}{\sqrt{3}}, +\frac{1}{\sqrt{3}}, +\frac{1}{\sqrt{3}} \rparen, \dots, \lparen -\frac{1}{\sqrt{3}}, -\frac{1}{\sqrt{3}}, -\frac{1}{\sqrt{3}} \rparen \rbrace$

2次元のときの例を考えましょう。2次元の場合、コードブック $\lbrace \lparen +\frac{1}{\sqrt{2}}, +\frac{1}{\sqrt{2}} \rparen, \lparen +\frac{1}{\sqrt{2}}, -\frac{1}{\sqrt{2}} \rparen, \lparen -\frac{1}{\sqrt{2}}, +\frac{1}{\sqrt{2}} \rparen, \lparen -\frac{1}{\sqrt{2}}, -\frac{1}{\sqrt{2}} \rparen, \rbrace$ の中から、もっとも近い代表点を選ぶことになります。幾何学的に考えると、以下のように、4象限（領域）のそれぞれにコードブックの代表点が対応していると捉えられます^[8]。

3次元の場合は領域が8個に増えるだけで、同様に各領域の「中心」に代表点が位置することになります。4次元以上になると想像するのが難しくはなりますが同様です。

さて、コードブック $C$ を構成するとき、正規化したデータベクトルが単位球面上に広がって分布することを仮定していました。しかし、恣意的に作成した人工データでもない限り、実際には偏りがあることが想定されます。この偏りを扱うために、RaBitQ では、上記のコードブックのランダム直交射影を考え、それをコードブックとします。

ランダムコードブックの計算

RaBitQ では、コードブック $C$ の各ベクトルをランダムな直交行列 (orthogonal matrix) $P$ で変換したものを最終的なコードブック $C_{rand}$ とします：

\[ C_{rand} := \lbrace P \bm{x} | \bm{x} \in C \rbrace \]

直交行列とは、以下を満たすような正方行列 R のことでした。

\[ R^T R = R R^T = I \]

直交行列の性質として、以下のようなものがあります。

直交行列の逆行列は転置行列である: $R^{-1} = R^T$
- 行列 $A$ の逆行列とは $AB = BA = I$ を満たすような行列 B のこと。
- 直交行列の定義から $R^T = R^{-1}$ である。
直交行列はノルムを不変に保つ変換である: $\Vert R \bm{u} \Vert = \Vert \bm{u} \Vert$
- R を直交行列、 u を任意のベクトルとしたとき、 $\Vert R\bm{u} \Vert^2 = \langle R\bm{u}, R\bm{u} \rangle = \langle \bm{u}, R^T R\bm{u} \rangle = \langle \bm{u},\bm{u} \rangle = \Vert\bm{u}\Vert^2$。
- よって $\Vert Ru\Vert = \Vert u \Vert$。
直交行列による変換は内積を不変に保つ: $\langle R\bm{u}, R\bm{v} \rangle = \langle \bm{u}, \bm{v} \rangle$
- R を直交行列、 u, v を任意のベクトルとしたとき、 $\langle R\bm{u}, R\bm{v} \rangle = \langle \bm{u}, R^T R\bm{v} \rangle = \langle \bm{u},\bm{v} \rangle$

$P$ は直交行列なので、単位ベクトル $\bm{x} \in C$ を変換した $P\bm{x} \in C_{rand}$ もまた単位ベクトルとなります（上記の性質「直交行列はノルムを不変に保つ変換である」より）。つまり、 $C_{rand}$ 上のベクトル（コード）は単位超球面上に分布します。

また、性質「直交行列による変換は内積を不変に保つ」により、この直交行列 $P$ による射影では任意のベクトル間の内積（距離）が保存されます。このランダム直交射影によるベクトルの変換は、1種の Johnson-Lindenstrauss Transformation^[9]^[10] になっています^[11]。

このランダム直交行列 $P$ は、各要素を乱数で初期化した行列を QR 分解することで計算できます。RabitQ では以下のように実装されていました^[12]。

G = np.random.randn(D, D).astype('float32')
Q, _ = np.linalg.qr(G)
return Q

コードブック $C$ は、 $\lbrace +\frac{1}{\sqrt{D}}, -\frac{1}{\sqrt{D}} \rbrace ^D$ のようにある意味恣意的に構成したものでした。この $P$ のランダム性により、決定性のコードブック $C$ の preference を排除することができます。

$P$ は、あらゆる変換の中からランダムにサンプリングしたものです。つまり、 $P$ により変換されたコードブック $C_{rand}$ は、単位超球面上に一様に（等確率で）分布することになります。

よって、データベクトルに偏りがあったとしても、量子化（コード化）した際、より多様なコードへと分散することが期待できます。詳細は元論文^[1:3]の Section 3.1 を参照してください。

データベクトルの量子化

コードブック $C_{rand}$ の計算が終わったので、その中から（正規化した）データベクトル $\bm{o}$ に最も近いものを探し、それをデータベクトルの量子化された表現（コード）とします（インデックスフェイズの3番目のステップに相当）。

ユークリッド距離が最も近いベクトルを探すことは、内積が最も大きくなるベクトルを探すことと同値です。そのベクトルを $\overline{\bm{o}} = P \overline{\bm{x}} \in C_{rand}$ とします。このベクトル $\overline{\bm{o}}$ の $P$ での射影前のベクトルが $\overline{\bm{x}} \in C$ です。これは以下のように書けます。

\[ \begin{align*} \overline{\bm{x}} &= \argmin_{\bm{x} \in C} \Vert \bm{o} - P \bm{x} \Vert^2 \\ &= \argmin_{\bm{x} \in C} (\Vert \bm{o} \Vert^2 + \Vert P \bm{x} \Vert^2 - 2 \langle \bm{o}, P\bm{x} \rangle) \\ &= \argmin_{\bm{x} \in C} (2 - 2 \langle \bm{o}, P \bm{x} \rangle) \\ &= \argmax_{\bm{x} \in C} \langle \bm{o}, P \bm{x} \rangle \end{align*} \]

つまり、 $\langle \bm{o}, P \bm{x} \rangle$ が最大になるような $\bm{x}$ を求めたいわけです。これはさらに以下のように変形できます。

\[ \langle \bm{o}, P \bm{x} \rangle = \langle P^{-1} \bm{o}, P^{-1} P \bm{x} \rangle = \langle P^{-1}\bm{o}, \bm{x} \rangle \]

人工的に構成したコードブックの要素 $\bm{x} \in C$ の各次元の値は $\pm 1 / \sqrt{D}$ でした。ベクトル $P^{-1} \bm{o}$ との内積が最大になるような $\bm{x}$ を決めるには、ただベクトル $P^{-1} \bm{o}$ の各次元の値の符号だけを見ればよいことがわかります^[13]。それらの符号さえわかれば、 $\overline{\bm{x}}$ をただ1つに決定することができます。よって、これらの符号の列（長さ $D$ ）を $\overline{\bm{x}}_{b} \in \{ 0, 1 \}^D$ と表し、これをインデックスに保存します。

RaBitQ では、データベクトルはこのように量子化します。このように表現することで、各データベクトルは $D$ ビットまで小さくなります。また、 $\overline{\bm{x}} = ( 2 \overline{\bm{x}}_b - \bm{1}_D ) / \sqrt{D}$ によってバイナリ表現 $\overline{\bm{x}}_b$ から量子化したデータベクトル $\overline{\bm{x}}$ を復元します。

データベクトルとクエリベクトルの距離

さて、近似最近傍探索の問題は、クエリベクトル $\bm{o_r}$ とデータベクトル $\bm{q_r}$ のユークリッド距離 $\Vert \bm{o_r} - \bm{q_r} \Vert^2$ が小さいデータベクトルを探すことでした。これはベクトルのノルムの性質 $\Vert \bm{x} - \bm{y}\Vert^2 = \Vert \bm{x} |^2 + \Vert \bm{y} \Vert^2 - 2 \cdot \langle \bm{x}, \bm{y} \rangle$ を使うと、セントロイド $\bm{c}$ を使って以下のように展開できます。

\[ \begin{align} \Vert \bm{o_r} - \bm{q_r} \Vert^2 &= \Vert (\bm{o_r} - \bm{c}) - (\bm{q_r} - \bm{c}) \Vert^2 \\ &= \Vert \bm{o_r} - \bm{c} \Vert^2 + \Vert \bm{q_r} - \bm{c}\Vert^2 - 2 \cdot \langle \bm{o_r} - \bm{c}, \bm{q_r} - \bm{c} \rangle \end{align} \]

ベクトルの正規化のところで述べましたが、正規化したデータベクトルは $\bm{o} := \frac{\bm{o_r} - \bm{c}}{\Vert\bm{o_r} - \bm{c}\Vert}$ でした。また、正規化したクエリベクトルは同様に $\bm{q} := \frac{\bm{q_r} - \bm{c}}{\Vert\bm{q_r} - \bm{c}\Vert}$ と書けます。これらの内積は以下のように書けます。

\[ \begin{align} \langle \bm{o}, \bm{q} \rangle &= \langle \frac{\bm{o_r} - \bm{c}}{\Vert \bm{o_r} - \bm{c} \Vert}, \frac{\bm{q_r} - \bm{c}}{\Vert \bm{q_r} - \bm{c} \Vert} \rangle \\ &= \frac{\langle \bm{o_r} - \bm{c}, \bm{q_r} - \bm{c} \rangle}{\Vert \bm{o_r} - \bm{c} \Vert \cdot \Vert \bm{q_r} - \bm{c} \Vert} \end{align} \]

(3) 式から (4) 式への展開には、内積の性質 $\langle a \bm{x}, \bm{y} \rangle = a \langle \bm{x}, \bm{y} \rangle$ を使用しました。この関係性（ (4) 式）を使うと、 (2) 式は以下のように変形できます。

\[ \begin{equation} \Vert \bm{o_r} - \bm{q_r} \Vert^2 = \Vert \bm{o_r} - \bm{c} \Vert^2 + \Vert \bm{q_r} - \bm{c} \Vert^2 - 2 \cdot \Vert \bm{o_r} - \bm{c} \Vert \cdot \Vert \bm{q_r} - \bm{c} \Vert \cdot \langle \bm{o}, \bm{q} \rangle \end{equation} \]

このように、クエリベクトル $\bm{o_r}$ とデータベクトル $\bm{q_r}$ のユークリッド距離 $\Vert \bm{o_r} - \bm{q_r}\Vert^2$ は、いくつかのコンポーネントに分離できます。

(5) 式の最初と最後の項にあらわれる $\Vert \bm{o_r} - \bm{c}\Vert$ は、データベクトルとセントロイドの距離です。セントロイドはインデックス構築時に計算済みのため、これは事前に計算できます。事前計算した $\Vert \bm{o_r} - \bm{c} \Vert$ はインデックスと一緒に保存しておきます（インデックスフェイズの4番目）。また、クエリベクトルとセントロイドの距離 $\Vert \bm{q_r} - \bm{c} \Vert$ は検索時に1回だけ計算すればよいため、問題にはなりません。

では、最後のコンポーネントである内積 $\langle \bm{o}, \bm{q} \rangle$ を RaBitQ がどう計算するかを見ていきます。

データベクトルとクエリベクトルの内積の推定

RabitQ では、内積 $\langle \bm{o}, \bm{q} \rangle$ の推定値として $\frac{\langle \overline{\bm{o}}, \bm{q} \rangle}{\langle \overline{\bm{o}}, \bm{o} \rangle}$ を使用します。

データベクトル $\bm{o}$ とクエリベクトル $\bm{q}$ が共線 (colinear) である、つまり $\bm{o} = \bm{q}$ もしくは $\bm{o} = - \bm{q}$ であるとき、 $\langle \overline{\bm{o}}, \bm{q} \rangle = \langle \overline{\bm{o}}, \bm{o} \rangle \cdot \langle \bm{o}, \bm{q} \rangle$ が成り立ちます（共線であれば任意のベクトルに対して成り立つ）。この場合、内積 $\langle \bm{o}, \bm{q} \rangle$ については簡単に解けて、

\[ \begin{equation} \langle \bm{o}, \bm{q} \rangle = \frac{\langle \overline{\bm{o}}, \bm{q} \rangle}{\langle \overline{\bm{o}}, \bm{o} \rangle} \end{equation} \]

となります。これを推定値として使います。共線でないときにはもちろん誤差が出ますが、この誤差は $O(1 / \sqrt{D})$ 以下（ $D$ はデータベクトル・クエリベクトルの次元数）であり、かつ unbiased^[14] になることが論文中^[1:4]の Section 3.2 で証明されています。

$\langle \overline{\bm{o}}, \bm{o} \rangle$ はデータベクトルだけから事前に計算できるため、これもインデックスに保存しておきます（インデックスフェイズの4番目のステップ）^[15]。 $\langle \overline{\bm{o}}, \bm{q} \rangle$ の計算については後述します。

RabitQ のインデックスフェイズ

ここで、RabitQ でのデータベクトルの量子化・インデキシングをまとめておきましょう（再掲）。

セントロイド $\bm{c}$ を計算し、すべてのデータベクトルを正規化（$\bm{o_r}$ を $\bm{o}$ にする）
ランダムな直交行列 $P$ をサンプリングし、コードブック $C_{rand}$ を構築
量子化されたデータベクトル $\overline{\bm{x}}_b$ を計算（コードブックの中から選ぶ）
以下を事前計算
1. データベクトルとセントロイドとの距離 $\Vert \bm{o}_r - \bm{c} \Vert$
2. 量子化されたデータベクトルと正規化したデータベクトルの内積 $\langle \overline{\bm{o}}, \bm{o}\rangle$ （オプション）

インデックスには以下の情報を保存します。

セントロイド $\bm{c}$
量子化されたデータベクトル $\overline{\bm{x}}_b$ （データベクトルごとに $D$ ビット）
各データベクトルとセントロイドとの距離 $\Vert \bm{o}_r - \bm{c}\Vert$
量子化されたデータベクトルと正規化したデータベクトルの内積 $\langle \overline{\bm{o}}, \bm{o}\rangle$ （オプション）

データベクトルとクエリベクトルの内積の近似計算

さて、データベクトルとクエリベクトルの内積（(6) 式）を計算するためには、残る $\langle \overline{\bm{o}}, \bm{q} \rangle$ を計算すればよくなりました。これはランダム射影 $P$ を使うと、以下のように変形できます。

\[ \begin{equation} \langle \overline{\bm{o}}, \bm{q} \rangle = \langle P \overline{\bm{x}}, \bm{q} \rangle = \langle P^{-1} P \overline{\bm{x}}, P^{-1} \bm{q} \rangle = \langle \overline{\bm{x}}, \bm{q}\rq \rangle \end{equation} \]

ここで、 $\overline{\bm{x}}$ は量子化後のデータベクトルです。また、便利のために $\bm{q}\rq = P^{-1} \bm{q}$ とおきました。

クエリベクトルの量子化

もともと (6) 式は近似ですから、 (7) 式も正確な値を計算する必要はなく、一定の誤差を許容した近似値で代用できます。RaBitQ では $\bm{q}\rq$ の代わりに、それを量子化したものを使って計算を効率化しています。ただし 1 ビットではなく、誤差を抑えるために $B_q$ ビットで量子化します（非対称な量子化）。

$\bm{q}\rq$ を量子化したものを $\overline{\bm{q}}$ としましょう。前のセクションで $\langle \overline{\bm{x}}, \bm{q}\rq \rangle$ を計算したいという話をしましたが、 $\langle \overline{\bm{x}}, \overline{\bm{q}} \rangle$ をこの近似として使います。

$v_l \coloneqq \min_{1 \leq i \leq D} \bm{q}\rq[i]$ （ $\bm{q}\rq$ の最小値）
$v_r \coloneqq \max_{1 \leq i \leq D} \bm{q}\rq[i]$（ $\bm{q}\rq$ の最大値）
$\Delta \coloneqq (v_r - v_l) / (2^{B_q} - 1)$ （量子化の刻み幅）
$u_i$ を $[0, 1]$ の一様分布からサンプリングした値

としたとき、RaBitQ では $\overline{\bm{q}}$ のバイナリ表現 $\overline{\bm{q}}_u$ （の $i$ 番目の要素）を以下の式で計算します。

\[ \begin{equation} \overline{\bm{q}}_u [i] \coloneqq \lfloor \frac{\bm{q}\rq[i] - v_l}{\Delta} + u_i \rfloor \end{equation} \]

この計算は直感的には、離散化するときに「左」の離散値にするか「右」の離散値にするかを 1/2 の確率で選んでいることになります。こうすることにより、値の分布に依存せずに unbiased にすることができます^[16]。

バイナリ表現 $\overline{\bm{q}}_u$ から $\overline{\bm{q}}$ を復元するには、 $\overline{\bm{q}} = \Delta \cdot \overline{\bm{q}}_u + v_l \cdot \bm{1}_D$ （ $\bm{1}_D$ はすべて 1 が立っているビットベクトル）とすればOKです。

クエリベクトルのビット数 $B_q$ を $\Theta (\log \log D)$ としたとき、高い確率で近似による量子化誤差 $| \langle \overline{\bm{x}}, \bm{q}\rq \rangle - \langle \overline{\bm{x}}, \overline{\bm{q}} \rangle |$ が $O(1/ \sqrt{D})$ に収まることが論文中で証明されています（Theorem 3.3^[1:5]）。また実験的にも、 $D = 128$ （SIFTデータセット）や $D = 960$ （GISTデータセット）の場合に、 $B_q = 4$ まで増やすと誤差が十分に小さく収束することが示されています（Fig. 6^[1:6]）。

量子化したデータベクトルとクエリベクトルの内積計算

さて、データベクトルのバイナリ表現 $\overline{\bm{x}}_b$ とクエリベクトルのバイナリ表現 $\overline{\bm{q}}_u$ を得たところで、これを使って前述した $\langle \overline{\bm{x}}, \overline{\bm{q}} \rangle$ を計算するのが次の関心事になります。これを効率的に計算するために、ビット演算を利用できる形に変形していきます。

$\overline{\bm{x}} = ( 2 \overline{\bm{x}}_b - \bm{1}_D ) / \sqrt{D}$ 、 $\overline{\bm{q}} = \Delta \cdot \overline{\bm{q}}_u + v_l \cdot \bm{1}_D$ でしたから、 $\langle \overline{\bm{x}}, \overline{\bm{q}} \rangle = \left\langle \frac{2 \overline{\bm{x}}_b - \bm{1}_D}{\sqrt{D}}, \Delta \cdot \overline{\bm{q}}_u + v_l \cdot \bm{1}_D \right\rangle$ です。これはさらに、

\[ \begin{equation} \langle \overline{\bm{x}}, \overline{\bm{q}} \rangle = \frac{2 \Delta}{\sqrt{D}} \langle \overline{\bm{x}}_b, \overline{\bm{q}}_u \rangle + \frac{2 v_l}{\sqrt{D}} \sum_i^D \overline{\bm{x}}_b [i] - \frac{\Delta}{\sqrt{D}} \sum_i^D \overline{\bm{q}}_u [i] - \sqrt{D} \cdot v_l \end{equation} \]

という形に展開できます。この第 2 項に表れる $\sum_i \overline{\bm{x}}_b \lbrack i \rbrack$ は、このビットベクトルの 1 の立っている数であり、インデックスフェイズに事前計算できます。

また、 $D$ は固定値であり、 $\Delta$ や $v_l$ はクエリベクトルの量子化時にすでに計算されています。同様に第3項の $\sum^D \overline{\bm{q}}_{u} [i]$ もクエリ時に一度だけ計算すればよく、計算コストはほとんどかかりません。つまり、第1項の $\langle \overline{\bm{x}}_b, \overline{\bm{q}}_u \rangle$ をどう効率的に計算するかが主な関心になります。

SIMD による内積計算の高速化

ここで、 $D$ 次元のクエリベクトルのバイナリ表現 $\overline{\bm{q}}_u$ を 4 ビット（ $B_q = 4$ ）として、データベクトルのバイナリ表現 $\overline{\bm{x}}_b$ との内積計算を考えてみましょう。Fig. 2 の左図の点線がクエリの1つの次元です（4 ビット表現）。クエリは $4D$ ビットで表現されることになり、各セルは 0/1 のバイナリの値です。

内積の値は1次元ずつ計算できて $\langle \overline{\bm{x}}_b, \overline{\bm{q}}_u \rangle = ( {\overline{\bm{q}}_u}^{(0)} [1] \cdot 2^0 + {\overline{\bm{q}}_u}^{(1)} [1] \cdot 2^1 + {\overline{\bm{q}}_u}^{(2)} [1] \cdot 2^2 + {\overline{\bm{q}}_u}^{(3)} [1] \cdot 2^3 ) + \cdots$ となります。一方、加算は交換できるので、0ビット目から4ビット目までを別々に計算することもできます。つまり、 $\langle \overline{\bm{x}}_b, \overline{\bm{q}}_u \rangle = ( {\overline{\bm{q}}_u}^{(0)} [1] \cdot 2^0 + {\overline{\bm{q}}_u}^{(0)} [2] \cdot 2^0 + {\overline{\bm{q}}_u}^{(0)} [3] \cdot 2^0 + {\overline{\bm{q}}_u}^{(0)} [4] \cdot 2^0 + \cdots ) + \cdots$ で計算することもできます（Fig. 2 右図）。

こうすることで、各ビットベクトル ${\overline{\bm{q}}_u}^{(0)}$ 、 ${\overline{\bm{q}}_u}^{(1)}$ 、 ${\overline{\bm{q}}_u}^{(2)}$ 、 ${\overline{\bm{q}}_u}^{(3)}$ と ${\overline{\bm{x}}_b}$ の論理積（AND）をとったあと、1が立っている数をカウントし、積和演算（それぞれ 1, 2, 4, 8 を掛けて足す）することで内積が求まります。

これは SIMD 演算で効率的に計算することができ、とくにビットを数えるステップは popcount として知られる専用の命令を使用することで高速に計算できます。たとえば SSE や AVX では POPCNT と呼ばれる命令群が用意されています。

論文^[1:7]の Section 3.3.2 ではさらに、複数のデータベクトルをバッチで処理することでクエリを高速化する方法についても述べられています。

内積計算の最適化の具体例

この内積計算をもう少し具体的に見てみましょう。以下はクエリベクトルが [8, 15, 10, 7, 4, 0, 9, 9] のときの例です^[17]。

要素はそれぞれ 4 ビットで表現されています。クエリベクトルは 8 次元ごとに分割します（8x4 = 32 ビット単位）。この例では 8 次元ちょうどなのでそのままです。次に、8 個の 4 ビットの各位置のビット（0 ビット目から 4 ビット目まで）を取り出し、4 つの int8 に変換します。

データベクトルは 1 ビット、クエリベクトルは 4 ビットで量子化されるのでした。量子化されたデータベクトルを [0, 1, 1, 0, 0, 0, 0, 0] 、クエリベクトルを [8, 15, 10, 7, 4, 0, 9, 9] として、その内積を計算してみましょう。

普通に計算すると、 0 * 8 + 1 * 15 + 1 * 10 + 0 * 7 + 0 * 4 + 0 * 0 + 0 * 9 + 0 * 9 == 15 + 10 == 25 ですね。この内積計算をビット演算を利用して高速化します。

量子化されたクエリベクトル [8, 15, 10, 7, 4, 0, 9, 9] のバイナリ表現は、先頭から

0b1000 (= 8)
0b1111 (= 15)
0b1010 (= 10)
0b0111 (= 7)
0b0100 (= 4)
0b0000 (= 0)
0b1001 (= 9)
0b1001 (= 9)

ですね。データベクトルが 1 の次元だけ計算すればよいので、2番目 (0b1111 = 15) と3番目 (0b1010 = 10) を足せば答え (0b1111 + 0b1010 = 25) が求まります。この計算をビット演算風に表現すると (1 + 1) << 3 + (1 + 0) << 2 + (1 + 1) << 1 + (1 + 0) << 0 == 2 * (2**3) + 1 * (2**2) + 2 * (2**1) + 1 * (2**0) == 25 です。

つまり、データベクトル 0, 1, 1, 0, 0, 0, 0, 0] でマスクしたあと（2番目と3番目だけが残る）、各ビット位置ごとにビット数をカウントし、最終的な結果を計算すればよいわけです。これらの計算は、論理積 (AND)、ビットカウント、ビットシフト、そして加算のみで計算できます。

このように、異なるビット数のベクトル同士の内積計算を、簡単なビット演算に帰着させることができます。

RaBitQ のクエリフェイズ

ここまでをおさらいします。インデックスには以下の情報が保存されています：

セントロイド $\bm{c}$
量子化されたデータベクトル $\overline{\bm{x}}_b$ （データベクトルごとに $D$ ビット）
各データベクトルとセントロイドとの距離 $\Vert \bm{o}_r - \bm{c}\Vert$
量子化されたデータベクトルと正規化したデータベクトルの内積 $\langle \overline{\bm{o}}, \bm{o}\rangle$ （オプション）

計算したいのは生のデータベクトル $\bm{o_r}$ とクエリベクトル $\bm{q_r}$ の距離でした。 (5) 式を思い出してください。

\[ \begin{equation*} \Vert \bm{o_r} - \bm{q_r} \Vert^2 = \Vert \bm{o_r} - \bm{c} \Vert^2 + \Vert \bm{q_r} - \bm{c} \Vert^2 - 2 \cdot \Vert \bm{o_r} - \bm{c} \Vert \cdot \Vert \bm{q_r} - \bm{c} \Vert \cdot \langle \bm{o}, \bm{q} \rangle \end{equation*} \]

$\Vert \bm{o}_r - \bm{c}\Vert$ はインデックスに保存されていますし、 $\bm{c}$ も保存されているため $\Vert \bm{q_r} - \bm{c}\Vert$ もクエリ時に直ちに計算できます。残る $\langle \bm{o}, \bm{q} \rangle$ は (6) 式で近似するのでした：

\[ \begin{equation*} \langle \bm{o}, \bm{q} \rangle = \frac{\langle \overline{\bm{o}}, \bm{q} \rangle}{\langle \overline{\bm{o}}, \bm{o} \rangle} \end{equation*} \]

内積 $\langle \overline{\bm{o}}, \bm{o}\rangle$ はインデックスに保存されているためそれを使います^[18]。内積 $\langle \overline{\bm{o}}, \bm{q}\rangle$ は $\langle \overline{\bm{x}}, \overline{\bm{q}} \rangle$ で近似するのでした。(9) 式を思い出します。

\[ \begin{equation*} \langle \overline{\bm{x}}, \overline{\bm{q}} \rangle = \frac{2 \Delta}{\sqrt{D}} \langle \overline{\bm{x}}_b, \overline{\bm{q}}_u \rangle + \frac{2 v_l}{\sqrt{D}} \sum_i^D \overline{\bm{x}}_b [i] - \frac{\Delta}{\sqrt{D}} \sum_i^D \overline{\bm{q}}_u [i] - \sqrt{D} \cdot v_l \end{equation*} \]

前述した通り、第2項以降は素直に計算してもそれほどコストはかかりません。第1項の内積 $\langle \overline{\bm{x}}_b, \overline{\bm{q}}_u \rangle$ は、データベクトルごとにビット演算と SIMD で計算します。

以上をまとめると、RaBitQ のクエリフェイズは以下の通りです（再掲）。

クエリベクトルを正規化・変換
1.のクエリベクトルを量子化
各データベクトルに対して以下を計算
1. $\frac{\langle \bm{\overline{o}}, \bm{q}\rangle}{\langle \bm{\overline{o}}, \bm{o}\rangle}$ を計算（$\langle \bm{o}, \bm{q}\rangle$ の近似値として使用する）
2. 元のクエリベクトルとデータベクトルの距離の推定値を計算（(5) 式より）

RaBitQ と ANN

クエリフェイズのデータベクトルごとに計算する部分（擬似コードの3行目から5行目）は、前述した IVF といった ANN の手法を併用して高速化できます（Section 4 を参照）。RaBitQ では、バッチでのクエリフェイズの計算が困難という理由で、HNSW のようなグラフベースの手法ではなく、 IVF を使って ANN による高速化を行っています。

RaBitQ では IVF のインデックスからデータベクトルを多めに取得し、リランキングします。RaBitQ では誤差の上限が計算できるため、それを利用してリランク対象のデータベクトルの数を調整します。

RaBitQ の拡張

RaBitQ はデータベクトルを 1 ビットで表現する手法でした。これを複数ビットに拡張することでさらに誤差を下げる手法 Extended RaBitQ^[19] が提案されています。この手法については以下のブログポストが参考になるでしょう。

Extended RaBitQ: an Optimized Scalar Quantization Method

BBQ

BBQ (Better Binary Quantization) は、Elastic で開発されたビット量子化手法です。RaBitQ から着想を得て開発されたとのことです。

Elasticsearch での利用方法

Elasticsearch 8.16 以降、BBQ が dense_vector フィールドとして使用できるように Elasticsearch に組み込まれています。 dense_vector フィールドの mapping 定義で、 index_options.type に以下のいずれかを設定することができます：

bbq_hnsw （グラフベースの HNSW で ANN のデータベクトルを取得）
bbq_flat （ブルートフォースで kNN のデータベクトルを取得）

{
  "mappings": {
    "properties": {
      "my_vector": {
        "type": "dense_vector",
        "dims": 64,
        "index": true,
        "index_options": {
          "type": "bbq_hnsw"
        }
      }
    }
  }
}

詳細は公式ドキュメントを参照してください。

Dense vector field type | Elasticsearch Guide [8.16] | Elastic

BBQ によるデータベクトルの量子化

BBQ では RaBitQ と同様に、データベクトルの各次元を1ビットに量子化します。

データベクトルのセントロイドは事前に計算しておく点も同様です。セントロイドの計算は、データベクトルが入ってくるたびにインメモリでインクリメンタルに実行できるので、インデックス構築時にはすでに計算が終わっています。

データベクトルは以下のように 8 次元単位で量子化します^[17:1]。

データベクトルからセントロイドを引く（正規化）
1のベクトルの各次元の値が 0 より大きければ 1 、そうでなければ 0 に量子化
corrections を事前計算
1. データベクトルからセントロイドの距離（1 で計算済み）
2. 元のデータベクトルと、量子化後のベクトルの内積（どのくらい離れていたか）

BBQ での距離推定

corrections は検索時に量子化によって失われた情報を「復元」し、クエリベクトルとデータベクトルの距離をより正確に推定するために使います。このあたりは RaBitQ と同様の計算しているようです。さらに詳しい解説は以下のブログを参照してください。

RaBitQ binary quantization 101 - Elasticsearch Labs

BBQ のバイナリフォーマット

BBQ が Lucene インデックスに保存されるときのバイナリフォーマットは以下のようになっています^[17:2]。

量子化されたデータベクトルは 8 次元ずつ pack されます。8次元ごとに量子化されたビットをまとめて byte として保存します。その直後に corrections （長さ 2 から 3 の float の配列）を置く形になっています。

BBQ のインデックス構築の実装

インデックスへの書き込みの実装はこのあたりです：

距離 (similarity) がユークリッドノルムの場合の流れをまとめてみると、以下のようになります。

BBQ のクエリ処理

BBQ では RaBitQ と同様、データベクトルの各次元を 1 ビットに、クエリベクトルは各次元を 4 ビットの int4 （0 から 15 の範囲）にスカラ量子化し、精度の向上を狙っています。BBQ ではクエリベクトルとデータベクトルの内積を最適化するため、クエリベクトルを 8 次元ごとにビットを並べ替えます。

ベンチマーク

PQ と BBQ を比較した結果が以下のブログで公開されています。

Better Binary Quantization vs. Product Quantization - Elasticsearch Labs

PQ と比較すると、BBQ はインデックス構築時間やレイテンシがかなり短く、精度 (recall) も僅かですが良いようです。

まとめ

この記事では、ANN でのベクトル量子化手法である RaBitQ と、Elasticsearch の BBQ (Better Binary Quantization) を紹介しました。

RaBitQ と BBQ の主な違いは、BBQ ではランダム射影 $P$ を使っていないという点です^[20]。これはデータベクトルの分布によっては量子化誤差が大きくなってしまうことを意味し、誤差の上限を保証することもできません。論文の筆頭著者である Gao による以下の記事は、RaBitQ が高精度を達成できる直感的な理由が解説されています。

Quantization in The Counterintuitive High-Dimensional Space

また、ANN を併用した BBQ （ bbq_hnsw ）ではグラフベースアルゴリズムの HNSW を利用するため、誤差上限を利用したリランキングを利用することもできません（そもそも誤差上限の保証もありませんが）。

Elasticsearch の BBQ は、RaBitQ のランダム射影とリランキングを取り入れることで、さらに精度・速度の向上の余地がありそうです。

この記事は人力で書かれました。BBQ を利用する方の参考になれば幸いです。

Jianyang Gao and Cheng Long. 2024. RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Search. Proc. ACM Manag. Data 2, 3, Article 167 (June 2024), 27 pages. https://doi.org/10.1145/3654970 ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎
https://github.com/erikbern/ann-benchmarks ↩︎
松井勇佑. 2019. 近似最近傍探索の最前線. MIRU 2019 チュートリアル. https://speakerdeck.com/matsui_528/jin-si-zui-jin-bang-tan-suo-falsezui-qian-xian ↩︎ ↩︎
Herve Jegou, Matthijs Douze, and Cordelia Schmid. 2011. Product Quantization for Nearest Neighbor Search. IEEE Trans. Pattern Anal. Mach. Intell. 33, 1 (January 2011), 117–128. https://doi.org/10.1109/TPAMI.2010.57 ↩︎ ↩︎ ↩︎
余談ですが、IVF での粗量子化器を HNSW にする手法もあります。 ↩︎
https://www.elastic.co/search-labs/blog/rabitq-explainer-101 ↩︎
実際には偏りがありますが、これをどのように解消するかを後で説明します。 ↩︎
https://www.elastic.co/search-labs/blog/rabitq-explainer-101 ↩︎
William B Johnson and Joram Lindenstrauss. 1984. Extensions of Lipschitz mappings into a Hilbert space. In: Proceedings of the 1982 Conference in Modern Analysis and Probability. Vol. 26. Contemporary Mathematics. AMS, 1984, pp. 189–206. https://doi.org/10.1090/conm/026/737400 ↩︎
Casper Benjamin Freksen. 2021. An introduction to Johnson-Lindenstrauss Transforms. arXiv [cs.DS]. Retrieved December 25, 2024 from http://arxiv.org/abs/2103.00564 ↩︎
Johnson-Lindenstraussの補題により、変換をしても2つのベクトルの距離が一定の誤差内に抑えられるという性質が証明されています（たとえ射影先が低次元でも）。 ↩︎
ランダム射影による特異値分解（次元削減）は、scikit-learn にも実装されています。 https://scikit-learn.org/stable/modules/generated/sklearn.decomposition.TruncatedSVD.html#sklearn.decomposition.TruncatedSVD ↩︎
なお、データベクトルを正規化して $\bm{o}$ を計算するために $\bm{o_r}$ からセントロイド $\bm{c}$ を引いた後、ノルムで割って正規化していますが、実は量子化するうえではノルムで割らなくても同じ結果が得られます。RaBitQ でも BBQ でも、ノルムでの割り算は省略しています。 ↩︎
ランダム射影を使ったからだと思われる ↩︎
なお、この内積の値の保存はオプションです。保存しない場合、この値の理論値である 0.8 を使用することができます（Section 3.2.1）。 ↩︎
ここについては、実用上は確率的にサンプリングせず、四捨五入などで決定的に丸めるだけでも十分かもしれません。 ↩︎
https://www.elastic.co/search-labs/blog/better-binary-quantization-lucene-elasticsearch ↩︎ ↩︎ ↩︎
前の脚注で説明した通り、保存しない場合は理論値である 0.8 を使用します。 ↩︎
Jianyang Gao, Yutong Gou, Yuexuan Xu, Yongyi Yang, Cheng Long, and Raymond Chi-Wing Wong. 2024. Practical and asymptotically optimal quantization of high-dimensional vectors in Euclidean space for approximate nearest neighbor search. arXiv [cs.DB] http://arxiv.org/abs/2409.09913 ↩︎
https://x.com/gaoj0017/status/1872475912589165017 ↩︎

2023振り返り

Takuya Asano — Wed, 03 Jan 2024 14:04:13 GMT

年が明けてしまいましたが、2023年の振り返りです。

去年の振り返りはこちら。

2022振り返り

普段、こういったブログはあまり書かないが、いい機会だし、書き残してあると、のちのち見返すのに便利かなと思い、今年やったことを書き出してみる。ほとんど趣味の話です。 * 電子工作 * 競技プログラミング * パソコン * ゲーム * 登山 * コーヒー * 論文読み * 仕事 * おわりに電子工作去年、コンピュータシステムの理論と実装という本をすこし読んでハードウェアというか電子回路方面に興味が湧き、年末にブレッドボードやら抵抗やらを買い揃えて、LED光らせて遊んだりしていた。電子工作入門する pic.twitter.com/F3MQLZiFlS — tak…

Stop-the-worldTakuya Asano

買ってよかったもの

Keychron Q11

Out-of-the-box で使える分割式キーボードである Keychron Q11 を買いました。

キーマップは VIA でカスタマイズできます。自分は Windows と macOS どっちも使うので、モードの切り替えスイッチも便利。

ロータリーエンコーダが左右それぞれについているので、右はボリューム、左は画面の拡大・縮小（macOS の場合 G(KC_MINS) G(KC_EQL) ）に割り当てています。

mng pic.twitter.com/MmFLUWY8lt
— takuya-a (@takuya_b) December 7, 2023

マキタの空気入れ

マキタのバッテリーで動く空気入れを買いました。‌‌

これまで高気圧までハアハア言いながら入れていたのはなんだったんだ。めちゃくちゃ楽です。‌‌動作音はけっこう大きいので環境は選ぶかも。

思ったよりコンパクト pic.twitter.com/dRvJmG7goO
— takuya-a (@takuya_b) January 24, 2023

Homelab

Mastodon

去年から自宅サーバで mstdon.takuya-a.net を運用しています。‌‌

ECK で Elasticsearch をたてて、全文検索できるようにしました。‌‌あと、気が向いたときにちょいちょいバージョンアップ作業などしています。

Tailscale

VPN 的な用途で tailscale を導入しました。‌‌ホストに tailscale のクライアントをインストールしておくと、クライアント同士で Wireguard ベースの VPN 通信ができるようになります。

ついに外からでも SSH 経由で kubectl 叩けるようになった pic.twitter.com/PIST8wHsnJ
— takuya-a (@takuya_b) March 12, 2023

今回は Bastion 的な VM を立てて、そこに tailscale のクライアントをインストールしました。‌‌iPad やスマホに tailscale とターミナルアプリを入れておくと、外から VPN で内部ネットワークに入り、自宅サーバのメンテができるようになりました。

ゲーム

MTG

仲間内で統率者戦 (EDH) をやってみたいという話になり、1月に（紙の）構築済みデッキを買いました。‌‌

おもちゃ届いた pic.twitter.com/0wmviwf38Q
— takuya-a (@takuya_b) January 23, 2023

実は会社にも MTG のサークル活動が存在しており、おおよそ週1で EDH をやっていることが判明し、時間をみつけて参加するようになりました。‌‌そこからずるずると沼に引き込まれていき、デッキが6個に増殖しました。助けて。‌‌

ポケスリ

ポケスリを始めましたが、睡眠時間が短くてぜんぜん攻略が捗らない。‌‌2024年は睡眠時間を増やしたい。

アニメ

スキップとローファー

今年見たアニメの中ではスキップとローファーがよかったです。癒やされます。‌‌疲れている人はみるといいと思います。癒やされます。

スキップとローファー | Netflix

高校入学を機に上京した美津未。勉強はできるが人間関係に不器用な彼女は学校で浮いた存在となるが、のんびり屋の志摩と友達になったことをきっかけに、都会での新生活に少しずつなじんでいく。

Netflix

勉強会・コミュニティ活動

IR Reading

6月に開催された IR Reading 2023 Spring で Optimizing Guided Traversal for Fast Learned Sparse Retrieval (WWW 2023) という論文を紹介しました。LSR (Learned Sparse Retrieval) の OR 検索を高速化する手法に関する論文です。

IR Reading 2023 Spring: Optimizing Guided Traversal for Fast Learned Sparse Retrieval

IR Reading 2023 Spring: Optimizing Guided Traversal for Fast Learned Sparse Retrieval (WWW ’23) Takuya Asano LegalOn Technologies, Inc.

Google Docs

当日の様子は会社のブログにも書きましたので、興味のある方はこちらもどうぞ。

その他、今年は LSR に関する論文をけっこう読みました。‌‌まだ途中ですが、 LSR 関連の主な手法を概観できるような資料を作っています。前半部分は社内の勉強会で発表しましたが、後半部分がまだなので、2024年中にぜんぶ読んでスライドを完成させたい。

A Quick Tour of Learned Sparse Retrieval

A Quick Tour of Learned Sparse Retrieval Takuya Asano

Google Docs

検索技術勉強会

4年ぶりに検索技術勉強会を再開しました。なんとか無事に開催できて、手伝ってくださった@johtaniさん、@ikawahaさん、@minoru_osukaさんや、LegalOn Technologies の皆様に感謝。懇親会も盛況でした。

Search Engineering Tech Talk 2023 Winter (2023/12/20 19:30〜)

Search Engineering Tech Talk再始動です。第5回目となります。検索技術勉強会の目的は、「検索」/「検索システム」にまつわる技術や手法に関して共有できる場を提供することです。検索エンジンごとの勉強会などもありますが、検索エンジンには関係なく、「検索」というシステム、サービスを作る上で共通の解決すべき課題があります。これらの課題をみんながどのように解決しているのかといった知識を共有できる場になればと思っています。今後も、以前のように3ヶ月に1回くらいのペースで開催予定です。スピーカー募集してます! ### 各参加枠の説明 * 一般参加: 特...

connpass

OSS

法令XMLパーサー

法令データをパースしてpydanticのモデルに変換するライブラリ ja-law-parser を公開しました。

詳しい話はブログにまとめましたので、法律データについて興味のある方はどうぞ。

法律のデータ構造と検索

デジタル庁は、法令標準 XML スキーマに準拠した、現行の法令データをe-Gov法令検索というサイト上で公開しています[1]。今回、この法令XMLをパースするPythonライブラリ ja-law-parser をつくり、法令データの全文検索をしてみました。この記事では、日本の法令とそのデータ構造、法令XMLパーサについて解説し、最後に、それらを使った法令データの全文検索システムを実装する方法をご紹介します。法令検索の実装についても、GitHubリポジトリで公開しています。この記事は、情報検索・検索技術 Advent Calendar 2023の16日目の記事です。 * 法律と…

Stop-the-worldTakuya Asano

仕事

US向けサービスのローンチ

1月末でメルカリを退職し、2月1日から LegalOn Technologies の検索推薦チームに所属しています。‌‌最初の2ヶ月で US 向けのサービスの検索推薦基盤を立ち上げるというミッションをいただきましたが、なんとか無事にローンチできました（大変だった・・・）。

【AI契約レビュー支援ソフトウェア「LegalOn Review」正式リリース🇺🇸】
OpenAIの最新GPT技術を活用した契約書の修正文案表示機能「AI Revise」を搭載した「LegalOn Review」をアメリカで正式リリースしました！
アメリカでも、契約審査の効率化と品質向上の両立を支援します。https://t.co/dGmYzeqvUe
— 株式会社LegalOn Technologies（リーガルオンテクノロジーズ）【公式】 (@legalontech_jp) April 25, 2023

テックリード業

検索推薦チームではテックリードというロールを拝命しまして、開発者として手を動かすこと以外にも、情報を集めて何かしらの技術的判断をしたり、ドキュメントを書いたりといった仕事に時間を多く費やすようになりました。‌‌

また、採用・育成や技術ブランディングを含む、チームをさらに良くするための組織づくり・組織改善にも関わるようになりました。

おわりに

2024年は、睡眠の改善と、検索技術勉強会を継続させることを目標にやっていきたいと思います（スピーカーの応募ぜひお願いします！）。‌‌

ではでは。

法律のデータ構造と検索

Takuya Asano — Mon, 18 Dec 2023 18:53:27 GMT

デジタル庁は、法令標準 XML スキーマに準拠した、現行の法令データをe-Gov法令検索というサイト上で公開しています^[1]。今回、この法令XMLをパースするPythonライブラリ ja-law-parser をつくり、法令データの全文検索をしてみました。

この記事では、日本の法令とそのデータ構造、法令XMLパーサについて解説し、最後に、それらを使った法令データの全文検索システムを実装する方法をご紹介します。法令検索の実装についても、GitHubリポジトリで公開しています。

この記事は、情報検索・検索技術 Advent Calendar 2023の16日目の記事です。

法律と法令
法令のデータ構造
法令XMLパーサ： ja-law-parser
- ja-law-parser のインストール
- ja-law-parser の使いかた
法令の検索
おわりに

法律と法令

法律とは

法律とは、主に国家によって定められる、強制力をもった規範です^[2]。日本の法律は、国会の議決を経て制定されます。

社会生活を営むにあたって法やルールを遵守することが大事なのは言うまでもありませんが、知らず知らずのうちに法律に違反したことで制裁が課されたり社会的な信用を失うこともあるため、法律を正しく知ることは重要です。

法律の制定と公布

日本において法律案は、国会議員もしくは内閣から提出され、定められたワークフローに則り審査が行われます。それが可決されると、法律として制定され、官報（紙媒体）で公表されます。これを法律の公布といいます。公布された法律は、定められた施行日から効力を発揮します（公布日と施行日が同日になることもあります）。

たとえば内閣が提出した法律案（閣法）は、以下のプロセスで審議・成立・公布されます^[3]。

法律案の原案作成
内閣法制局における審査
国会提出のための閣議決定
国会に置ける審議
法律の成立
法律の公布

公布された法律は、官報（紙媒体）だけでなく、e-Gov法令検索（旧法令データ提供システム）をはじめとした、以下のようなオンラインサービスやデータベースでも公開されます^[4]。

法律と法令の違い

法令というのは、法律に加えて、憲法や政令などを含んだ法規範のことを指します。一般には以下のものを含むようです^[5]^[6]。

憲法
条約
法律
政令
命令
- 政令
- 府令・省令

法令は、より上位の法令が下位の法令より優先される、という階層構造になっています。いいかえると、基本的に上位の法令が優先し、それに違反する下位の法令は効力をもちません。たとえば、憲法は最も強い規範であり、憲法に違反するような法令は無効となります^[7]。

この記事では扱いませんが、日本における規範としては他にも、行政機関等が発する訓令・通達・通知・告示や、地方公共団体が制定する条例・規則などがあります。

法律の改正

日本における法律の改正には、法令の全文を改める全部改正と、条文の一部を改める一部改正があります。

全部改正の場合は、新たな法令として制定されます（法令番号も変わります）。もとの法令と題名は同じままになることが多い^[8]ため、区別できるよう、題名につづく制定文において「〜法の全部を改正する」という記述がなされます。たとえば、全部改正された法令の一つとして、著作権法（昭和四十五年法律第四十八号）があり、制定文には「著作権法（明治三十二年法律第三十九号）の全部を改正する。」と書かれています。

一部改正の際、日本では溶け込み方式と呼ばれる方法をとっており、条文の変更内容を既存の条文に適用し、上書きしてしまいます（溶かし込みといいます）。つまり、改正の内容を追跡しなくても、その時点で有効な法令の内容が一目でわかるようになっています。しかし、法令データでは改正前の条文に溶かし込まれた状態で公開されるため、変更内容がわからなくなっています。変更内容は、官報や法令全書においては、一部改正法として公布されるので、変更点を知りたい場合は、そちらもあわせて確認する必要があります^[5:1]。

また、法令を改正するにあたって、全部改正とは異なり、既存の法律を廃止し、新たにそれに代わる法令を制定する廃止制定があります^[9]。全部改正と似ていますが、こちらには制定文に「〜法の全部を改正する」という記述はされません。その代わり、附則にて、「〜法は廃止する」という記述がなされます。国籍法（昭和二十五年法律第百四十七号）は題名は同じですが、国籍法（明治三十二年法律第六十六号）が廃止制定されたもので、附則2項に「国籍法（明治三十二年法律第六十六号）は、廃止する。」と書かれています。

法令のデータ構造

e-Govの法令データ

e-Gov法令検索が公開している法令データ（以下、単に法令データとします）は、2023年12月16日現在、以下の9,111件です^[10]。

法令種別	登録数
憲法	1
法律	2,122
政令	2,302
勅令	71
府省令	4,181
規則	434

この法令データは、以下のURLから、すべてのXMLが含まれたzipファイル（ all_xml.zip ）をダウンロードできます。

XML一括ダウンロード | e-Gov法令検索

この法令データは、さまざまなアプリケーションの開発を想定されており、二次利用が可能です。

Q7：e-Gov法令検索で提供しているデータの二次利用をしたいのですが？
A：提供している法令データについては、特に利用制限を設けておりません。
ただし、デジタル庁及び各府省は、本システムの法令データの利用に伴って発生した不利益や問題について、何ら責任を負いませんので、ご承知ください。

ヘルプ - e-Gov法令検索

法令標準XMLスキーマ

法令データのファイルの内容は、法令標準XMLスキーマ（PDF, xsd）に準拠した形式になっています^[11]。

たとえば法令XMLにおいて、もっとも「外側」の要素である、法令（ Law ）は以下のように定義されています。

法令データは、大きくは以下のような構造をもちます（カッコ書きの要素はオプショナル）。

法令 Law
- 法令番号 LawNum
- 法令本体 LawBody
  - 題名 LawTitle
  - （制定文 EnactStatement ）
  - （目次 TOC ）
- （前文 Preamble ）
- 本則 MainProvision
- （附則 SupplProvision ）
- （別表 AppdxTable 、別記 AppdxNote 、付録 Appdx 等）

法令標準XMLスキーマを見やすい形で公開しているサイトがありますので、スキーマについて詳しく知りたい方はそちらを参照するとよいでしょう。

Web知財法

法令番号と法令ID

法令は公布の際に、一意に識別できる法令番号が付与されます。たとえば、現在の会社法の法令番号は「平成十七年法律第八十六号」となっています。

e-Govが提供する法令データでは、各法令に一意な法令IDが付与されます（改正法にも法令IDが付与されます）。たとえば法律の法令IDは、以下のコード体系で決定されます^[12]。

桁数	意味
1	年号
2-3	年
4-5	種別（法律の場合 AC）
6-12	閣法と議員立法の区別
13-15	法令の号番号

法令が改正された場合、前述のとおり、もとの法令に改正法を溶かし込んだ（マージされた）ものが公開されています。

ただし、法令データには、施行日が未来のもの、つまり未施行の法令が含まれるので注意が必要です。たとえば会社法（平成十七年法律第八十六号）の場合、法令データには未施行のものを含め、以下のファイルが含まれています。

417AC0000000086_20230614_505AC0000000053.xml （2023年6月14日施行 ← 現在有効）
417AC0000000086_20250616_504AC0000000068.xml （未施行）
417AC0000000086_20251213_505AC0000000053.xml （未施行）
417AC0000000086_20260524_504AC0000000048.xml （未施行）
417AC0000000086_20280613_505AC0000000053.xml （未施行）

このように、法令データは、法令の改正に対応するため、一意に識別できる形でファイル名がつけられています。

e-Gov法令検索では、いつ時点のデータであるかを明示するために「法令ID_改正法の施行日_改正法の法令ID」をURLとしています。
「129AC0000000089_20200401_501AC0000000034」

ヘルプ - e-Gov法令検索

つまり、現在有効な法令を探すには、ファイル名に含まれる「改正法の施行日」が過去のものを対象にする必要があります。

題名

法令番号だけではどんな法令なのか認識しづらいこともあり、新たに制定される法令には、題名（ LawTitle ）がつけられ、法令が判別しやすくなっています。

ただし、昭和22年ごろまでに制定された法令のなかには題名のないものがありました。しかし、法令番号だけでは意味を類推できず、不便です。そのため、題名のない法令については、公布文から件名をとって便宜的な法令名として扱うようです。

たとえば、決闘罪について規定された明治二十二年法律第三十四号には題名がありません。この法令は「決闘罪ニ関スル件」と呼ばれており、法令データでも「明治二十二年法律第三十四号（決闘罪ニ関スル件）」という題名がつけられています。

本則と附則

法令の構造は、大きくは法令の実質的な内容が書かれている本則（ MainProvision ）と、条文の施行期日などの付帯的な情報が書かれた附則（ SupplProvisoin ）からなります（「法令標準XMLスキーマ」の項目を参照）。

附則では、その法令によって影響を受ける関連法令についても言及されることがあります。また、本則の特例など例外事項について書かれることもあり^[13]、附則も本則とあわせて確認する必要があります。

条・項・号

法令の内容のもっとも基本的な単位は条（ Article ）であり、法令は条（条文）の集まりからなる、と考えることができます^[7:1]^[14]。

では、条の構造を詳しく見ていきましょう。以下は、労働基準法（昭和二十二年法律第四十九号）の第24条を抜粋したものです。この条には、以下のように2つの項があります。

（賃金の支払）

第二十四条　賃金は、通貨で、直接労働者に、その全額を支払わなければならない。ただし、法令若しくは労働協約に別段の定めがある場合又は厚生労働省令で定める賃金について確実な支払の方法で厚生労働省令で定めるものによる場合においては、通貨以外のもので支払い、また、法令に別段の定めがある場合又は当該事業場の労働者の過半数で組織する労働組合があるときはその労働組合、労働者の過半数で組織する労働組合がないときは労働者の過半数を代表する者との書面による協定がある場合においては、賃金の一部を控除して支払うことができる。
②　賃金は、毎月一回以上、一定の期日を定めて支払わなければならない。ただし、臨時に支払われる賃金、賞与その他これに準ずるもので厚生労働省令で定める賃金（第八十九条において「臨時の賃金等」という。）については、この限りでない。

労働基準法（昭和二十二年法律第四十九号）

法令データにおいて条（ Article ）は、条名（ ArticleTitle ）や条見出し（ ArticleCaption 、省略可）、そして一般には複数の項 ( Paragraph ) から構成されます（項が1つだけの条も多い）。項は、実際の内容が書かれる項文（ ParagraphSentence ）をもちます。項文は段（ Sentence ）という文字列型の文のリストとして定義されます。先ほどの第24条は、法令データでは以下のようなXMLになっています。


  （賃金の支払）
  第二十四条
  
  
    
      賃金は、通貨で、直接労働者に、その全額を支払わなければならない。
      ただし、法令若しくは労働協約に別段の定めがある場合又は厚生労働省令で定める賃金について確実な支払の方法で厚生労働省令で定めるものによる場合においては、通貨以外のもので支払い、また、法令に別段の定めがある場合又は当該事業場の労働者の過半数で組織する労働組合があるときはその労働組合、労働者の過半数で組織する労働組合がないときは労働者の過半数を代表する者との書面による協定がある場合においては、賃金の一部を控除して支払うことができる。
    
  
  
    
    
      賃金は、毎月一回以上、一定の期日を定めて支払わなければならない。
      ただし、臨時に支払われる賃金、賞与その他これに準ずるもので厚生労働省令で定める賃金（第八十九条において「臨時の賃金等」という。）については、この限りでない。

基本的に項文（ ParagraphSentence ）に含まれる段（ Sentence ）は1つの本文（属性が Function="main" のもの）のみですが、この第24条のように、ただし書（属性が Function="proviso" ）の段（ Sentence ）をもつことがあります^[15]。

項の内容をさらに細分化して記述する必要がある場合には号（ Item ）が用いられます。著作権法第10条第3項には、3つの号が含まれています。

３　第一項第九号に掲げる著作物に対するこの法律による保護は、その著作物を作成するために用いるプログラム言語、規約及び解法に及ばない。この場合において、これらの用語の意義は、次の各号に定めるところによる。

一　プログラム言語　プログラムを表現する手段としての文字その他の記号及びその体系をいう。
　二　規約　特定のプログラムにおける前号のプログラム言語の用法についての特別の約束をいう。
　三　解法　プログラムにおける電子計算機に対する指令の組合せの方法をいう。

著作権法（昭和四十五年法律第四十八号）

法令データでは、以下のようになっています（著作権法第10条第3項より第1号までを抜粋）。


  ３
  
    第一項第九号に掲げる著作物に対するこの法律による保護は、その著作物を作成するために用いるプログラム言語、規約及び解法に及ばない。
    この場合において、これらの用語の意義は、次の各号に定めるところによる。
  
  
    一
    
      
        プログラム言語
      
      
        プログラムを表現する手段としての文字その他の記号及びその体系をいう。
      
    
  
  
（以下略）

編・章・節・款・目

条文数の多い法令については、編（ Part ）、章（ Chapter ）、節（ Section ）、款（ Subsection ）、目（ Division ）という区分を用いて条をまとめます（ただし、必ずしも全ての階層が存在するわけではありません）。

よって一般には、法令の内容（本則）は、以下のような階層構造となります。

本則 MainProvision
- 編 Part
  - 章 Chapter
    - 節 Section
      - 款 Subsection
        
        目 Division

なお、条名（条番号）は区分をまたいでも通し番号が振られます。つまり、章をまたいだとしても、ふたたび第一条から始めるといったことはしません。

法令XMLパーサ： ja-law-parser

さて、XMLファイルを解析し、なんらかのデータ処理をするときには、適当なXMLライブラリ（Pythonの場合は lxml など）を使ってパースし、XPathで特定の要素を取り出すことになると思います。

ですが、法令データは前述の通り、オプショナルな要素を含む複雑な構造をもっており、場合によっては困難が伴います。目的とする要素を取り出したり、データに応じて柔軟にデータ処理をするには、複雑なXPathを組んだり、深くネストしたコードを書く必要があるかもしれません。また、法令標準XMLスキーマの仕様について適切に理解していないと、目的の要素が抽出できていなかった、といったこともありえます。

そこで、上記の法令標準XMLスキーマに準拠する法令XMLファイルをパースし、Pythonのオブジェクト（pydanticのモデル）に変換するライブラリ ja-law-parser をつくりました。このパーサライブラリは GitHub と PyPI で公開しています。

このライブラリを使って法令データを解析することで、たとえば以下のような利点があります。

明示的にXMLを扱わずにすみ、Python APIだけで汎用的なデータ処理ができる
- XMLやXPathの学習コストを払わずにすむ
- 必要な構造のみを簡単に抽出できる
Pydanticのモデルに変換されるので、pydanticのAPIを利用して、モデルをJSONなどの他のデータ構造に変換できる

ja-law-parser のインストール

pip を使う場合、以下のコマンドでインストールできます。

pip install ja-law-parser

poetry の場合は以下でインストールできます。

poetry add ja-law-parser

ja-law-parser の使いかた

LawParser を import し、 parse 関数にXMLのファイルパスを与える、もしくは parse_from 関数にXMLの内容（文字列もしくはバイナリ）を与えることで、法令（ Law ）型のオブジェクトが返ってきます。このオブジェクトには与えた法令の情報がすべて含まれているので、自由に属性（attributes）にアクセスしたり、テキストを取り出したりすることができます。

from ja_law_parser.model import Article, Chapter, Law, Paragraph
from ja_law_parser.parser import LawParser

parser = LawParser()

law: Law = parser.parse(path="321CONSTITUTION_19470503_000000000000000.xml")
print(law.law_body.law_title.text)
# => 日本国憲法

chapter3: Chapter = law.law_body.main_provision.chapters[2]
print(chapter3.chapter_title.text)
# => 三章　国民の権利及び義務

article11: Article = chapter3.articles[1]
print(article11.article_title.text)
# => 第十一条

paragraph11: Paragraph = article11.paragraphs[0]
print(paragraph11.paragraph_sentence.sentences[0].text)
# => 国民は、すべての基本的人権の享有を妨げられない。
print(paragraph11.paragraph_sentence.sentences[1].text)
# => この憲法が国民に保障する基本的人権は、侵すことのできない永久の権利として、現在及び将来の国民に与へられる。

法令の検索

前置きが長くなりましたが、法令データをElasticsearchにインデックスし、検索してみましょう^[16]。

Elasticsearchのマッピング

今回は簡単に、法令番号（ law_num ）、題名（ law_title ）、制定文（ enact_statement ）、本則のみをインデックスしてみます。Elasticsearchのマッピングはたとえば以下のようになります。

{
  "mappings": {
    "properties": {
      "law_num": {
        "type": "text",
        "fields": {
          "keyword": {
            "type": "keyword"
          }
        }
      },
      "law_title": {
        "type": "text",
        "fields": {
          "keyword": {
            "type": "keyword"
          }
        }
      },
      "enact_statement": {
        "type": "text",
        "fields": {
          "keyword": {
            "type": "keyword"
          }
        }
      },
      "main_provision": {
        "type": "text"
      }
    }
  }
}

法令データのインデクシング

いよいよ法令XMLパーサで法令データをパースし、Elasticsearchにデータを登録してみましょう。以下のような index_law 関数を書いてみました（実際のコードはGitHubリポジトリにあります）。

from typing import Generator, Protocol

from elasticsearch import Elasticsearch

from ja_law_parser.model import Law
from ja_law_parser.parser import LawParser

def index_law() -> None:
    parser = LawParser()
    client = Elasticsearch(hosts="http://localhost:9200/")

		# 指定したディレクトリに含まれるXMLファイルをイテレート
    for file in Path("../data").glob("**/*.xml"):
				# ファイル名から法令を識別するIDを抽出（法令ID_改正法の施行日_改正法の法令ID）
        file_name = file.stem

				# 施行日が未来の法令はインデックスしない
        enforce_date = date.fromisoformat(file_name.split(sep="_")[1])
        today = date.today()
        if today < enforce_date:
            continue

				# XMLをパースしてpydanticのモデルに変換
        law: Law = parser.parse(path=file)

				# Elasticsearchにインデックス
        client.index(
						index="ja_law",
            id=file.stem,
            document={
                "law_num": law.law_num,
                "law_title": text_or_none(law.law_body.law_title),
                "enactg_statement": text_or_none(law.law_body.enact_statement),
                "main_provision": texts_or_none(law.law_body.main_provision),
            },
        )

class Text(Protocol):
    @property
    def text(self) -> str:
        ...

class Texts(Protocol):
    def texts(self) -> Generator[str, None, None]:
        ...

def text_or_none(obj: Text | None) -> str | None:
    if obj is None:
        return None
    return obj.text

def texts_or_none(obj: Texts | None) -> str | None:
    if obj is None:
        return None
    return " ".join(obj.texts())

今回は本則以下のテキストをまるまる検索対象としてインデックスしましたが、特定の要素はスキップするなどの工夫もできそうです。

法令データの検索

検索側のコードは以下のように書けます。今回はシンプルに multi-match query で複数のフィールド（法令番号、題名、本則）を単にフレーズ検索しています。このあたりも色々工夫の余地がありそうです。

from elastic_transport import ObjectApiResponse
from elasticsearch import Elasticsearch

def search_law(keyword: str, size: int) -> ObjectApiResponse[Any]:
    client = Elasticsearch(hosts="http://localhost:9200/")
    return client.search(
        index="ja_law",
        query={
            "multi_match": {
                "query": keyword,
                "type": "phrase",
                "fields": ["law_num", "law_title", "main_provision"],
            }
        },
        size=size,
        fields=["law_num.keyword", "law_title.keyword"],
        highlight={
            "fields": {"*": {"pre_tags": [" **"], "post_tags": ["** "]}},
            "number_of_fragments": 1,
        },
    )

検索UI

今回はUIとして streamlit を使いました。フォームにクエリを入力してEnterキーを押すと検索結果が表示される、というだけのシンプルなUIです。

import streamlit as st

from japanese_law_search.search import search_law

st.title("Japanese Law Search")

# クエリの入力フォーム
query = st.text_input("Query", value="")
if query:
		# 検索を実行して top-20 を取得
    res = search_law(index_name="ja_law", keyword=query, size=20)
    st.write(f"{res.total_hits} hits")
    for doc in res.docs:
        c = st.container(border=True)
				# 題名と法令番号、e-Govへのリンクを表示
        c.markdown(
            f"[{doc.law_title}（{doc.law_num}）](https://elaws.e-gov.go.jp/document?lawid={doc.id})"
        )
				# ヒットしたフィールドのハイライトを表示
        c.caption(
            "".join(["".join(highlites[0]) for highlites in doc.highlight.values()])
        )

要素が少ないとはいえ、これだけのコードで簡単に検索画面のWeb UIが作成できてしまいます。実際に検索してみると、こんな感じで検索結果が表示されます。

ドキュメント数が少なくクエリも単純なので、結果は瞬時に返ってきます。ハイライトがあると、どの条文にヒットしたのかわかりやすくていいですね。ただ、ヒットした条番号と、条文の全文が表示されると、より使い勝手がよくなりそうな気がします^[17]。

おわりに

この記事では、日本の法令制度について概観したあと、デジタル庁が公開している法令データの形式を解説し、それをパースするPythonライブラリを紹介しました。

さらに、Elasticsearchを使って、実際に法令データのインデックスと検索を実装するサンプルを見てきました。今回はとりあえず動くサンプルを雑につくりましたが、マッピングやクエリ、言語解析（analyzer）などを改善することで、もっとよい法令検索がつくれるのではないかと思います。

みなさんが法律や法令について、少しでも身近に感じられるようになったなら幸いです。

2021年よりe-Gov法令検索は総務省からデジタル庁に移管されました。 https://www.e-gov.go.jp/news/2021-09-02t1914240900_715.html ↩︎
法律 - Wikipedia https://ja.wikipedia.org/wiki/法律 ↩︎
法律ができるまで（内閣法制局） https://www.clb.go.jp/recent-laws/process/ ↩︎
日本-法令の調べ方 - リサーチ・ナビ（国立国会図書館） https://rnavi.ndl.go.jp/jp/guides/japan-hourei-research.html ↩︎
いしかわまりこ; 藤井康子; 村井のり子. リーガル・リサーチ . 日本評論社. https://www.nippyo.co.jp/shop/book/7055.html ↩︎ ↩︎
法令 - Wikipedia https://ja.wikipedia.org/wiki/法令 ↩︎
法律等を読み解くうえで必要な基礎知識（株式会社みらい） ↩︎ ↩︎
全部改正にあたって、必要に応じて法令の題名が変えることがあります。たとえば、スポーツ基本法（平成二十三年法律第七十八号）は、スポーツ振興法（昭和三十六年法律第百四十一号）が全部改正された法令です。 https://houseikyoku.sangiin.go.jp/column/column039.htm ↩︎
https://houseikyoku.sangiin.go.jp/column/column039.htm ↩︎
DB登録法令数（e-Gov法令検索） https://elaws.e-gov.go.jp/registdb/ ↩︎
ヘルプ - e-Gov法令検索 https://elaws.e-gov.go.jp/help/ ↩︎
法令IDについて（e-Gov法令検索） https://elaws.e-gov.go.jp/file/LawIdNamingConvention.pdf ↩︎
https://houseikyoku.sangiin.go.jp/column/column010.htm ↩︎
例外として、法令データのなかには、条（ Article ）から始まらず、項（ Paragraph ）から始まる法令もあるため、注意が必要です。例：有明海及び八代海等を再生するための特別措置に関する法律第十一条第一項に規定する特定事業を定める省令（令和三年総務省令第四十四号） ↩︎
法令とは？法律との違いや読み方のコツを解説！ - 契約ウォッチ https://keiyaku-watch.jp/media/kisochishiki/hourei_yomikata/ ↩︎
Geminiなどで条文の文埋め込みを計算し、ElasticsearchのkNN searchで検索する、というのも試してみたかったのですが、時間が足りなかったので今後の宿題とします。 ↩︎
もしかしたら、条の単位をドキュメントとしてインデックスし、パッセージ検索のような形にするのがいいのかもしれません。スコアリングは難しくなりそうですが。 ↩︎

2022振り返り

Takuya Asano — Fri, 30 Dec 2022 08:20:13 GMT

普段、こういったブログはあまり書かないが、いい機会だし、書き残してあると、のちのち見返すのに便利かなと思い、今年やったことを書き出してみる。ほとんど趣味の話です。

電子工作
競技プログラミング
パソコン
ゲーム
登山
コーヒー
論文読み
仕事
おわりに

電子工作

去年、コンピュータシステムの理論と実装という本をすこし読んでハードウェアというか電子回路方面に興味が湧き、年末にブレッドボードやら抵抗やらを買い揃えて、LED光らせて遊んだりしていた。

電子工作入門する pic.twitter.com/F3MQLZiFlS
— takuya-a (@takuya_b) December 15, 2021

My first project pic.twitter.com/vUo1ZI3ao3
— takuya-a (@takuya_b) December 15, 2021

そこからLTSpiceを勉強したりして、シュミットトリガ回路と、それを使ったオンオフ回路を組めるようになった。

シュミットトリガ実際に組んだ。意図通りの挙動してるかどうかはオシロスコープないとわからなさそう pic.twitter.com/4NsetMyYi1
— takuya-a (@takuya_b) January 1, 2022

ローパスフィルタ+シュミットトリガによるチャタリング防止つきオンオフ回路。パラメータの調整が大変だった… pic.twitter.com/S8t3PxG1Bx
— takuya-a (@takuya_b) January 10, 2022

それから、いくつかの基本的な論理回路をディスクリートのMOSFETだけを使って実装するというのにチャレンジした。最終的にはNOT, NAND, NOR, XOR, XNOR、Dフリップフロップ、マルチプレクサ、半加算器・全加算器あたりまではMOSFETだけで実装できることを確認した。

非同期リセットつきDフリップフロップできたあああ！トランスファーゲートを使ったりしてトランジスタ数すこし減らせたけど、28石使って1ビット保存できるだけの回路 pic.twitter.com/KS7SJcn9bC
— takuya-a (@takuya_b) January 23, 2022

芸術点の高そうな4chマルチプレクサできたから見て pic.twitter.com/gi71DMYYgG
— takuya-a (@takuya_b) January 26, 2022

あとは並行してCPUの創り方という書籍を読んで、簡易的なものではあるが、CPUの構成要素が細部に渡って理解できたのはよかった。

この本に登場するTD4というシンプルな4bit CPUをディスクリート部品だけで実装するというのをやってみたかったが、時間とお金がかかりすぎるというのもあって断念（中断）してしまった。それに必要なコンポーネントは一通り実装できたので、できそうというのがわかったところで満足してしまっている状態。

CPUの創りかた|Tech Book Zone Manatee

マナティ

関連書籍で読んだものだと、コンピュータシステムの理論と実装という本もあるが、こちらはシミュレータを前提にしているので、少し趣が異なる。

コンピュータシステムの理論と実装

コンピュータを理解するための最善の方法はゼロからコンピュータを作ることです。コンピュータの構成要素は、ハードウェア、ソフトウェア、コンパイラ、OSに大別できます。本書では、これらコンピュータの構成要素をひとつずつ組み立てます。具体的には、NANDという電子素子からスタートし、論理ゲート、加算器、CPUを設計します。そして、オペレーティングシステム、コンパイラ、バーチャルマシンなどを実装しコンピュータを完成させて、最後にその上でアプリケーション（テトリスなど）を動作させます。実行環境はJava（Mac、Windows、Linuxで動作）。 ● 本書のサポートサイト● 本書で使用するツール「N…

O'Reilly logoNoam Nisan、Shimon Schocken　著、斎藤康毅　訳

Raspberry Pi Pico も買ったので来年はマイコンも触ってみたい。

競技プログラミング

4月ごろ、最近コード書いてないぞということに気づき、ずっと気になっていたAtCoderを始めてみた。

AtCoder Beginners Selection - AtCoder https://t.co/3WYm9QLFMK 最近あんまりコード書いてなかったのでAtCoder登録して精選10問にトライしてみたんだけど、何回かに分けてなんとか全問ACできた
— takuya-a (@takuya_b) April 30, 2022

AtCoderにはまずはこれをやってみましょうという入門用の問題が用意されている。「精選10問」と呼ばれていて、ABS (AtCoder Beginners Selection) という名前でAtCoder上にコンテストとして公開されており、いつでも自由に解いてコードを提出して実行結果を確認する、というプロセスを体験できるようになっている。

AtCoder に登録したら次にやること～これだけ解けば十分闘える！過去問精選 10 問～ - Qiita

NTT データ数理システムでリサーチャーをしている大槻 (通称、けんちょん) です。好きなアルゴリズムは最小カットやマッチングですが、会社ではなぜか「DP が好きな人」と呼ばれています。今回は、最近注目度が急上昇している AtCo...

Qiitadrken

AtCoder Beginners Selection - AtCoder

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

AtCoderAtCoder Inc.

精選10問を解いた後、5月末くらいにかけて、いくつかのコンテストの初心者向け問題を解いた。

典型90問はその名の通り、競プロの典型的な問題からなる問題集で、様々な難易度の問題が含まれており、自分の実力に合わせて楽しめるような構成になっている。

競プロ典型 90 問 - AtCoder

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

AtCoderAtCoder Inc.

他には、ABC (AtCoder Beginner Contest)と呼ばれる初心者〜中級者向けのカテゴリがあり、それもいくつか解いてみた（ちなみにAtCoderには、ABCよりも難しいARC (AtCoder Regular Contest)、AGC (AtCoder Grand Contest)、最適化問題などを扱うAHC (AtCoder Heuristic Contest)などの様々なカテゴリがある）。

提出の結果はAtCoder Problemsというサイトで確認できる。自分の提出結果は以下のような感じ。

AtCoder Problems

Manage your AtCoder problems.

週末にちょこちょこと進めたけど、散歩したりちょっとしたスキマ時間に解法を考えるのが思いのほか楽しかったので、来年また再開したいなと思う。

AtCoderちゃんと始めるにあたって、Python用のテンプレートとちょっとしたスクリプトを作って、コマンドをいくつか叩くだけでコンテスト用の環境を作れるようにしたので、興味のある方は覗いてみてください。

GitHub - takuyaa/atcoder: AtCoder solutions.

AtCoder solutions. Contribute to takuyaa/atcoder development by creating an account on GitHub.

GitHubtakuyaa

自宅サーバー

去年まではただの暖房だったサーバを、ちゃんと構築しはじめた。

寒いので電源入れた。暖房兼ASMR。 pic.twitter.com/ta9JPkrKHO
— takuya-a (@takuya_b) December 15, 2021

仮想化基盤としてProxmoxを物理マシンにインストールするところからスタートした。ProxmoxはKVMに管理画面や便利APIなどがついたもので、vCPUなどの制限なしにフリーで使えるので近年自宅サーバー界隈で流行している様子。

Proxmox - Powerful open-source server solutions

Proxmox develops the open-source virtualization platform Proxmox VE, the backup solution Proxmox Backup Server, and the Proxmox Mail Gateway, an open-source email security solution to protect your mail server.

Powerful open-source server solutions

KubernetesのディストリビューションとしてRancherが作っているRKE2を検証していて、いまのところ大きな障害もなく安定して動いている。

Introduction | RKE 2

RKE2, also known as RKE Government, is Rancher’s next-generation Kubernetes distribution.

logo

各種VM（RKE2のノードを含む）はTerraformを通してProxmox上に構築した。ネットワーク面では、KubernetesのLoadBalancer typeの実装としてMetalLBを入れた。ルータとBGPピアを張ってBGPモードで動いている。MetalLBによってKubernetesの外から見えるIPが振られるので、それをリバースプロキシやルータから参照する。ストレージはRKE2と同じくRancherが作っているLonghornを採用。

最初は仲間内で遊ぶためのゲームサーバーを動かしてみたりしていて、そのうちドメインを取ったり、Cloudflare CDNの設定やらなんやらをして、最終的にKubernetes上で動いているWebサーバがインターネットから見えるところまでできた。

https://t.co/X1CPdhdJ5R 開通したよ。家のKubernetesクラスタで動いてるpodにつながってます
— takuya-a (@takuya_b) August 7, 2022

いまは以下のサーバが自宅Kubernetesクラスタで動いている。

ゲーム

Webサービス

Ghost（ブログエンジン。このブログ https://takuya-a.net/blog/ はGhostで動いている）
Littlelink（プロフィールページ: https://takuya-a.net/）
Mastodon（分散型SNS: https://mstdn.takuya-a.net/about）

その他

Inadyn (Dynamic DNS)
Traefik （リバースプロキシ）
Prometheus & Grafana（サーバのモニタリング）

おうちのk8sクラスタにPrometheusとGrafanaいれたよ pic.twitter.com/Tf7do4Bxoq
— takuya-a (@takuya_b) September 23, 2022

他にも、VMのバックアップのためにTrueNASをiSCSI targetとして動かしている。あとはPCルータとしてOpenWRTを検証中。たまにルータがおかしくなってインターネット接続が壊れてしまうことが何回かあったので、OpenWRTでWANを冗長化したいと考えている。

来年はリモート接続環境を整えたり、複数人でクラスタを運用できるようになると楽しいかなとか妄想している。いろいろ知見も溜まってきたので、Kubernetesのマニフェストを問題ない範囲で公開したり、ブログかなんかにまとめたいと思う。

パソコン

引き続き5年前に買った自作PCを使い続けている。CPUクーラーを静音のものに買い替えたくらい。CPUファンの音がほとんど聞こえないくらい静かにはなったが、近くにあるサーバーがうるさすぎて意味はなかった。

NF-A12x25 PWM

The NF-A12x25 is a highly optimised next-generation 120mm fan that integrates Noctua’s latest innovations in aerodynamic engineering in order to achieve an unprecedented level of quiet cooling performance. It takes state-of-the-art technologies such as the AAO (Advanced Acoustic Optimisation) frame…

noctua

PCの用途は主にゲームと、趣味のプログラミングとかサーバーの設定作業とか。ゲーム以外では基本的にWSL2の中のUbuntuで作業している。エディタはVSCodeを使っていて、WSLだから困ったということは起きていない。中でとくに難しいことはしていないので、通常のLinuxでの開発と同等の体験が得られている。

ゲーム

今年はMagic: The Gatheringがマイブームで、デジタル・アナログ問わずけっこう遊んだ。デジタルのほうは、数年前からMTG Arenaを構築メインでやっていたけど、今年はリミテッド、特にドラフトも遊ぶようになった（マジックは遊び方がめちゃくちゃいっぱい存在する！）。

Play the CCG Free on PC, iOS and Android | Magic: The Gathering Arena

Magic: The Gathering Arena puts the original CCG at your fingertips. Build a deck to play with friends or challenge the AI to master your strategy!

MAGIC: THE GATHERING

アナログ（紙）は、去年の秋ごろから、エキスパンションが出るたびにそれを1ボックス買って、4人で集まってリミテッドというフォーマットで遊ぶ、というのをやっている。ボックスには1パック15枚入りのブースターパックが36パック入っているので、ドラフト1回で12パック、残りの24パックでシールドを1回やる、というルーチンになっている。そのうち8人のドラフトもやってみたい。

なぜか紙のデッキ構築にも興味が出てきて、パイオニアチャレンジャーデッキという構築済みデッキをベースにデッキを組み始めた。少しずつカードを買い集めてデッキを組んでいくのはデジタルとは違った体験で、とても尊い。せっかくデッキを組んだので、来年は店舗で開催されている大会に参加してみたいと思っている。

あとは、統率者というフォーマットに誘われたので、手持ちのカードをベースにデッキを組んでみている。これはこれでデッキのセオリーが全然違うので楽しい。

登山

夏に大平山にハイキングに行ったのが今年唯一の登山活動。真夏だったのでめちゃくちゃ暑かったけど楽しかった。雄大な風景のアルプスもいいけど、低山の楽しさもまたある。

勝上山・鷲峰山・大平山・天園 / takuyaさんの鎌倉アルプス（大平山・天台山）の活動データ | YAMAP / ヤマップ

No.1登山アプリYAMAP。オフラインの山中でも現在地を確認できる。最新のルート状況をはじめ、全国各地の登山情報を網羅。YAMAPであなたの登山はもっと楽しく、安全に。

YAMAPtakuya

来年には槍ヶ岳に誘われているので、山にももっと行きたい。

1年くらい前に奮発してLOWAの登山靴を買ったのだけど、足に合ってないっぽくて毎回足が痛くなっているので、買い換えようかと思っている。山に行けてない理由の大きな理由のひとつになっているので、シュッと買ったらよさそう。

チェベダーレ EVO GT Ws・L220052（アルパイン） LOWAローバー公式サイト｜イワタニ・プリムス株式会社

LOWA（ローバー）〇〇〇〇の製品紹介ページです。

イワタニ・プリムスLOWA（ローバー）

コーヒー

去年の春にセミコマーシャルのエスプレッソマシンを買ったけど、2022年もほぼ毎日使った。タンパーを買い替えたり、いくつか周辺機器をアップデートした。

58.5mmのタンパーが欲しくてPullmanのBigStep（3万3000円くらいする）買いそうになってたけどクリック直前で踏みとどまってアリエクで探したら2500円のがあったので買った。3万円得しました。 https://t.co/EgkYKSB4uv
— takuya-a (@takuya_b) March 19, 2022

ラテアートはそんなに上達してなくて、まだハートが描ける程度。しかも、たまに失敗する。来年はリーフとか描けるようになりたい。

この投稿をInstagramで見る

浅野卓也(@takuya_asn)がシェアした投稿

論文読み

秋に、1年ぶりにIR Readingで論文紹介した。ANN（近似近傍探索）のインデックスを、対照学習の枠組みで最適化するといったような内容で、なかなか面白かった。

インデックスといえば、2021 年の夏はLuceneインデックスのバイナリを解析していた（完成してなくてまだ下書き状態・・・）。来年、Lucene 9ベースでまたちゃんと解析してブログも書き上げたい。

https://stop-the-world.hatenablog.com/draft/entry/NXbtOo1V1X261E94FKRPr5eNXmM

今年は、転置インデックスの圧縮技法に関する論文をサーベイしてメモを書いた。

転置インデックスの圧縮技法

転置インデックスは、検索エンジンの実装において、中心的な役割を果たすデータ構造である。転置インデックスのデータ構造とアルゴリズムは、クエリ処理アルゴリズムとともに、検索エンジンの性能に直結する。とくに大規模な検索エンジンにおいては、キャッシュ効率を高めてクエリ処理を高速化するために、転置インデックスの圧縮は必要不可欠となっている。この記事では、転置インデックス、とくにポスティングリストの圧縮について、近年の手法を簡単にまとめる。目次 * 転置インデックスの基本 * 転置インデックスのデータ構造と特性 * 転置インデックスのアクセスパターン * 近…

Stop-the-worldTakuya Asano

代表的なアルゴリズムについては、そのうちRustあたりで再実装してベンチマークを取ってみたい。

仕事

年明けの1月31日付で現職を退職することになった。盛大な送別会も開いていただいて、立派な色紙まで頂いて感激してしまった。本当にありがとうございました。いろんな方に感謝の言葉をいただけたので、チームに多少は貢献できたのかなと嬉しい気持ちになりました。

来年2月1日からはLegalOn Technologiesという会社で働きます。ひきつづき検索・推薦に関わることになるので、界隈の皆さんはまたよろしくお願いします。

おわりに

来年も楽しい1年にしていきたいですね。ではでは。

転置インデックスの圧縮技法

Takuya Asano — Sun, 23 Oct 2022 14:09:36 GMT

転置インデックスは、検索エンジンの実装において、中心的な役割を果たすデータ構造である。

転置インデックスのデータ構造とアルゴリズムは、クエリ処理アルゴリズムとともに、検索エンジンの性能に直結する。とくに大規模な検索エンジンにおいては、キャッシュ効率を高めてクエリ処理を高速化するために、転置インデックスの圧縮は必要不可欠となっている。

この記事では、転置インデックス、とくにポスティングリストの圧縮について、近年の手法を簡単にまとめる。

転置インデックスの基本
- 転置インデックスのデータ構造と特性
- 転置インデックスのアクセスパターン
近年のインデックス圧縮技法
- Variable-Byte Family
- Simple Family
  - Simple9
  - Simple16
  - Simple8b
  - QMX
- PFor Family
- Elias-Fano Family
  - Elias-Fano
  - PEF
  - Roaring
  - Slicing
- Binary Interpolative
  - BIC
- Directly-Addressable
  - DAC
- Dictionary-based
  - DINT
- Bitmap Compression
  - BBC
  - WAH
  - EWAH
  - CONCISE
  - PLWAH
  - VALWAH
  - SBH
実装とベンチマーク
参考文献

転置インデックスの基本

具体的なポスティングリストの圧縮技法について触れる前に、転置インデックスの基本について、ざっくりと説明する。

転置インデックスのデータ構造と特性

転置インデックス (inverted index) は、ターム辞書 (term dictionary) とポスティングリスト (posting lists) （転置リスト (inverted list) とも）から構成される。

転置インデックスは以下のような構造をもち、ターム (term) とポスティングリストが一対一で対応している。

Christopher D. Manning, Prabhakar Raghavan, and Hinrich Schütze. 2008. Introduction to Information Retrieval. p.7 Figure 1.3

ポスティングリストの各要素のことを、ポスティング (posting) といい、そのタームが含まれる文書 ID を意味している。たとえば上記の例では、文書 2, 31, 54, 101 に Calpurnia というタームが含まれている。

ポスティングリストは、以下のような特徴をもっている。

非負の整数のみが含まれる
同じ数は含まれない
単調増加数列（ソートされている）
コレクション（文書集合）によるが、値の分布は偏っていることが多い

多くの技法がこれらの特性をうまく使って、効率的な圧縮を実現している。

転置インデックスのアクセスパターン

検索クエリ処理において、ポスティングリストは基本、シーケンシャルに（前から順番に）アクセスされる。

ただし、AND クエリ (conjunction query, intersection) などの、複数のポスティングリストをまたぐクエリ処理では、効率化のため、いずれかのポスティングのカーソルを特定の文書 ID までスキップするという最適化が行われる。

OR クエリ (disjunction query, union) においても、MaxScore や WAND などの枝刈り (pruning) アルゴリズムにより、このようなスキップが積極的に行われる。

近年のインデックス圧縮技法

Techniques for Inverted Index Compression というサーベイ論文にて、2019年までの整数（列）圧縮技法が調査されている [Pibiri&Venturini21]。

Giulio Ermanno Pibiri and Rossano Venturini. 2020. Techniques for Inverted Index Compression. Table 1

Techniques for Inverted Index Compression | ACM Computing Surveys

The data structure at the core of large-scale search engines is the inverted index, which is essentially a collection of sorted integer sequences called inverted lists. Because of the many documents indexed by such engines and stringent performance...

ACM Computing SurveysGiulio Ermanno Pibiri ISTI-CNR, Pisa, Italy

また、 An Experimental Study of Bitmap Compression vs. Inverted List Compression では、 bitmap compression と呼ばれる手法群と、整数列圧縮技法との比較がなされている [Wang+17]。

Jianguo Wang, Chunbin Lin, Yannis Papakonstantinou, and Steven Swanson. 2017. An Experimental Study of Bitmap Compression vs. Inverted List Compression. Figure 1

An Experimental Study of Bitmap Compression vs. Inverted List Compression | Proceedings of the 2017 ACM International Conference on Management of Data

ACM ConferencesJianguo Wang University of California, San Diego, San Diego, CA, USA

以下では、それぞれの圧縮技法について、簡単に紹介する。

Variable-Byte Family

整数値をそれぞれ圧縮
ビットではなくバイト単位に揃える (byte-aligned)
SIMD が使えるので高速化しやすい

VByte (Variable-Byte) [Thiel&Heaps72]

整数値をバイトの並びにする
- 1 byte は 1 bit のコントロールビットと 7 bit のデータビットで表現
最初のバイトのみコントロールビットを 0 にする
- 続いているバイトではコントロールビットは 1
たとえば、 65790 は 00000100.10000001.11111110 となる
デコードするときはデータビットを連結
大きい整数値のときには効率的

参考

Information Retrieval: Implementing and Evaluating Search Engines 6.3.4, 6.6
下記の講義スライド p.16

data_compression_course/2_integer_codes.pdf at master · jermp/data_compression_course

A Crash Course on Data Compression. Contribute to jermp/data_compression_course development by creating an account on GitHub.

GitHubjermp

Varint-GB [Dean09]

バイト単位 (byte-aligned) なのは同じ
最初の 2 bit を長さを表現するのに使う
4つの整数値ごとにグルーピング
- グループごとの 2 bit を集めて、 8 bit のタグを作る
- タグを見れば 4 つの整数値をそれぞれどの長さでデコードすればよいかわかる
デコードが Variable-Byte より高速
- 従来の Variable-Byte は ~180M numbers/sec
- Varint-GB は ~400M numbers/sec
Google の転置インデックスのフォーマットに採用された
Varint-GB と呼ばれている
- Group varint で、長さのエンコードは binary (not unary)

Jeffrey Dean. 2009. Challenges in building large-scale information retrieval systems: invited talk p.63

参考

下記のスライド pp.55-63

Challenges in building large-scale information retrieval systems: invited talk – Google Research

Google Research

Varint-G8IU [Stepanov+11]

SIMD 命令でデコードをベクトル化
Varint-GB と同じようにグループごとに 1 byte のコントロールバイト（タグ）を使う
ひとつのグループの中に 2 から 8 の整数を入れられる
- 固定サイズ (e.g., 8 bytes) のブロックにできるだけ多くの整数を詰め込む
- 固定サイズであることで SIMD と相性がいい
Amazon の Stepanov によって開発された
- 特許が取られている

Alexander Stepanov, Anil Gangolli, Daniel Rose, Ryan Ernst, and Paramjit Oberoi. 2011. SIMD-based decoding of posting lists. Figure 3

Alexander Stepanov, Anil Gangolli, Daniel Rose, Ryan Ernst, and Paramjit Oberoi. 2011. SIMD-based decoding of posting lists. Figure 5

SIMD-based decoding of posting lists | Proceedings of the 20th ACM international conference on Information and knowledge management

ACM ConferencesAlexander A. Stepanov A9.com, Palo Alto, CA, USA

参考

Stream VByte: breaking new speed records for integer compression

In many information systems, we work with arrays of integers. For example, maybe you need to keep track of which records in a database contain a given value. This sort of mapping can be expressed as an array of integers. These arrays can end up taking up a large fraction of your memory or disk … Con…

Daniel Lemire's blogView all posts by Daniel Lemire

Masked-VByte [Plaisance+15]

同じく VByte の SIMD 実装
フォーマットはオリジナルの Variable-Byte と同じ
デコード
- 専用の SIMD 命令を使って、最初に MSBs (most significant bits) を集める
- 事前に構築されたルックアップテーブルとシャッフル命令を使って整数に変換する
オリジナルの VByte よりは速いが、 Varint-G8IU よりは遅い
- ただし、 Varint-G8IU と違ってパテントフリー
Indeed の Jeff Plaisance によって開発された

Jeff Plaisance, Nathan Kurz, and Daniel Lemire. 2015. Vectorized VByte Decoding. Figure 1

Vectorized VByte Decoding

We consider the ubiquitous technique of VByte compression, which representseach integer as a variable length sequence of bytes. The low 7 bits of eachbyte encode a portion of the integer, and the high bit of each byte is reservedas a continuation flag. This flag is set to 1 for all bytes except t…

arXiv.orgJeff Plaisance

実装

https://maskedvbyte.org/ から C/C++ 実装がダウンロード可能

Stream-VByte [Lemire+18]

SIMD で高速なデコードを達成
Varint-GB は制御バイトとデータバイトがインターリーブで保存されているので、SIMD による並行処理が難しかった
- 可変長なので、前のグループの制御バイトをデコードしないと次のグループがどこに保存されているのかわからない
- このデータの依存関係により、並列化しようとしてもCPUが遊んでしまう
制御ビットとデータビットを別の場所に保存することで CPU にデータを供給しつづけることができる
Varint-G8IU よりデコードが最大で2倍高速
- 条件によっては memcpy を超える速度

Daniel Lemire, Nathan Kurz, and Christoph Rupp. 2018. Stream VByte: Faster byte-oriented integer compression. Figure 3

Daniel Lemire, Nathan Kurz, and Christoph Rupp. 2018. Stream VByte: Faster byte-oriented integer compression. Figure 5

Stream VByte: Faster Byte-Oriented Integer Compression

Arrays of integers are often compressed in search engines. Though there aremany ways to compress integers, we are interested in the popular byte-orientedinteger compression techniques (e.g., VByte or Google’s Varint-GB). They areappealing due to their simplicity and engineering convenience. Amazo…

arXiv.orgDaniel Lemire

実装

GitHub - lemire/streamvbyte: Fast integer compression in C using the StreamVByte codec

Fast integer compression in C using the StreamVByte codec - GitHub - lemire/streamvbyte: Fast integer compression in C using the StreamVByte codec

GitHublemire

Opt-VByte [Pibiri&Venturini20]

複数の可変長のブロックに分割
密なブロックはビットベクトルで、疎なブロックは VByte でエンコードする
- Cardinality によるパーティショニング
- PEF と同じアプローチ
ブロックの選び方を最適化する
- 最適な分割を時間計算量 Θ(n)、空間計算量 O(1) で厳密解を見つけられる
- 定数係数は非常に小さいので、実際にはかなり高速
- VByte でなくても、 point-wise な整数のエンコーダー（Unary, Golomb, etc）ならなんでも適用可能

Giulio Ermanno Pibiri and Rossano Venturini. 2020. On Optimally Partitioning Variable-Byte Codes. Fig. 2

On Optimally Partitioning Variable-Byte Codes | IEEE Transactions on Knowledge and Data Engineering

The ubiquitous Variable-Byte encoding is one of the fastest compressedrepresentation for integer sequences. However, its compression ratio is usually notcompetitive with other more sophisticated encoders, especially when the integers to...

IEEE Transactions on Knowledge and Data EngineeringGiulio Ermanno Pibiri ISTI-CNR and the University of Pisa, Pisa, Italy

https://rossanoventurini.github.io/papers/TKDE20.pdf

実装

GitHub - jermp/opt_vbyte: Optimal partitioning of Variable-Byte codes for better compression and fast decoding.

Optimal partitioning of Variable-Byte codes for better compression and fast decoding. - GitHub - jermp/opt_vbyte: Optimal partitioning of Variable-Byte codes for better compression and fast decoding.

GitHubjermp

Simple Family

Variable-Byte とは違って、ソート済みリストの圧縮に適した手法（PForなどと同様）
リストの要素間の差分 (gap) をエンコードする
複数の差分を 1 word (32 bits - 128 bits) に詰め込む
セレクタによってデータ部分をどうデコードするか（ビットパターン）を決める

Simple9 [Anh&Moffat05]

Simple4b とも呼ばれる
32 bits の中にできるだけ差分 (gap) を詰め込む
4 bits からなるセレクタと、残りの 28 bits に分ける
全9種類のセレクタによって残りの 28 bits に何個の整数を詰めるかを決める
- たとえば、セレクタが 0000 のときは 1 bit の整数 28 個を詰める
- 0010 のときは 3 bits の整数を 9 個詰める（このとき 1 bit は無駄になる）

Giulio Ermanno Pibiri and Rossano Venturini. 2020. Techniques for Inverted Index Compression. Table 6

Inverted Index Compression Using Word-Aligned Binary Codes | Information Retrieval

We examine index representation techniques for document-based inverted files, andpresent a mechanism for compressing them using word-aligned binary codes. The newapproach allows extremely fast decoding of inverted lists during query processing,while ...

Information RetrievalVo Ngoc Anh Department of Computer Science and Software Engineering, The University of Melbourne, Victoria 3010, Australia

Simple16 [Zhang+08]

Simple9 と同様に、32 bit の中にできるだけ差分 (gap) を詰め込む
4 bits からなるセレクタと、残りの 28 bits に分ける
全16種類のセレクタで、残りの 28 bits にどのように整数を詰めるか（ビットパターン）を決める
- たとえば 5, 5, 5, 5, 4, 4 で合計 28 bits
- Simple9 では無駄なビットがあったが、それがなくなる
- 全ビットパターン: https://github.com/lemire/JavaFastPFOR/blob/1b9f1290edf66ec2b439c5d192a91c187d292812/src/main/java/me/lemire/integercompression/Simple16.java#L174-L182

Performance of compressed inverted list caching in search engines | Proceedings of the 17th international conference on World Wide Web

ACM ConferencesJiangong Zhang Polytechnic University, Brooklyn, NY, USA

http://ra.ethz.ch/CDstore/www2008/www2008.org/papers/pdf/p387-zhangA.pdf

Simple8b [Anh&Moffat10]

Simple16 の亜種
32 bits ではなく 64 bits の中に整数を詰める
4 bits のセレクタと、残りの 60 bits に分ける
全14種類のセレクタ

Index compression using 64-bit words | Software—Practice & Experience

Modern computers typically make use of 64-bit words as the fundamental unit of dataaccess. However the decade-long migration from 32-bit architectures has not been reflectedin compression technology, because of a widespread assumption that effective ...

Software—Practice & ExperienceVo Ngoc Anh Department of Computer Science and Software Engineering, The University of Melbourne, Victoria 3010, Australia

QMX [Trotman14]

SIMD 命令を活用
同じく Simple の亜種で、128 bits もしくは 256 bits のなかに整数を詰める
他の Simple とは違い、セレクタ（eXtractors と呼ぶ）とデータ（Quantities と呼ぶ）を別々に保存する
- 別のストリームとすることで CPU が遊ばないようにする
セレクタのストリームはランレングス符号 (RLE) でエンコードされる
- セレクタは 16 種類しかないので、同じものが続きやすいため
- (value, length) のペア
- たとえばセレクタのストリームが [12, 12, 12, 5, 7, 7, 7, 7, 9, 9] だったとき、RLE は [(12, 3), (5, 1), (7, 4), (9, 2)] となる

Compression, SIMD, and Postings Lists | Proceedings of the 2014 Australasian Document Computing Symposium

ACM Other conferencesAndrew Trotman Department of Computer Science, University of Otago, Dunedin, New Zealand

PFor Family

Patched Frame-of-Reference
Simple と同様に、ソート済みリストの圧縮に適した手法
- リストの要素間の差分 (gap) をエンコードする
ブロック単位でエンコード
ブロック中に大きい差分があると、それを表現するのに必要なビット数が増えるため、スペース効率が悪くなる
ブロック中の大きい差分は別の場所に保存すれば、小さい差分は少ないビット数でエンコードできる
- 実データにおいては、ポスティングリストの差分はほとんどの場合小さい
- たとえば差分が 15 以下なら、各差分は 4 ビットでエンコード可能
- このアプローチを patching と呼ぶ

PForDelta [Zukowski+06]

ブロックごとに2つのパラメータ b と k を選ぶ
- ブロックの中の整数のほとんど (e.g., 90%) が [b, b + 2^k - 1) の範囲に入るようにする
その範囲に入る差分 x は、 x - b を k ビットでエンコードする
k ビットに収まらない、大きい差分は例外 (exception) として別の場所に保存する
たとえば [3, 4, 7, 21, 9, 12, 5, 16, 6, 2, 34] というリストがあったとき、b = 2, k = 4 を選ぶと
- [1, 2, 5, *, 7, 10, 3, *, 4, 0, *] となり（ * は exception）、 exception は [21, 17, 34] となる
元論文では、ディスク上での各ブロックのレイアウトを以下のように定めている
- header: パラメータ (b, k) の値と、他の領域の開始位置とサイズなどが保存される
- entry point section: 128個ごとに、次の例外の位置と、対応する exception section のオフセットを保存する領域
- code section: それぞれのエンコードされた値を格納する領域
  - 例外の場合には、次の例外へのオフセットが書かれる
  - 次の例外が離れすぎていて k ビットで表現できない場合、例外でない値を適当に選んで例外として扱う必要がある
- exception section: 例外の値を保存する、後ろに向かって伸びる領域
デコードで分岐予測が発生しないので高速

Marcin Zukowski, Sandor Heman, Niels Nes, and Peter Boncz. 2006. Super-Scalar RAM-CPU Cache Compression. Figure 3

https://www.researchgate.net/publication/4234735_Super-scalar_RAM-CPU_cache_compression

Today’s Paper Hao Yan, Shuai Ding and Torsten Suel - ppt download

背景知識

ppt download

NewPFD [Yan+09]

PForDelta + Simple16
例外 (exception) を表現するために、例外のオフセット値と例外を2つの別の配列に保存する
- code section の例外に対応する場所には、例外の下位 b ビットを書く
- 例外の残りのビットを別の配列に書く
- 例外のオフセット（次の例外への位置差分）を別の配列に書く
- この2つの配列を Simple16 でさらに圧縮する

Inverted index compression and query processing with optimized document ordering | Proceedings of the 18th international conference on World wide web

ACM ConferencesHao Yan Polytechnic Institute of NYU, Brooklyn, NY, USA

整数列圧縮 from JAVA DM

Today’s Paper Hao Yan, Shuai Ding and Torsten Suel - ppt download

背景知識

ppt download

Opt-PFor [Yan+09]

PForDelta の最適化バージョン
ブロックのサイズが小さくなるように、パラメータ b, k を最適化
PForDelta より小さくなるが、速度は少しだけ落ちる
NewPFD と同じ論文で提唱された

Inverted index compression and query processing with optimized document ordering | Proceedings of the 18th international conference on World wide web

ACM ConferencesHao Yan Polytechnic Institute of NYU, Brooklyn, NY, USA

実装

kamikaze/PForDelta.java at master · javasoze/kamikaze

DocId set compression and set operation library. Contribute to javasoze/kamikaze development by creating an account on GitHub.

GitHubjavasoze

Fast-PFor, SIMDPforDelta, SIMDBP128 [Lemire&Boytsov15]

これも PForDelta の亜種
例外をページ（ブロックのグループ）に圧縮する
- たとえば 1 ページは 32 個のブロックで構成される
- ページごとに例外をまとめて記録する
ページ単位でまとめてデコードすることで高速化
SIMD でさらに高速化できる
- SIMDPforDelta, SIMDBP128

Decoding billions of integers per second through vectorization | Software—Practice & Experience

In many important applications-such as search engines and relational database systems-dataare stored in the form of arrays of integers. Encoding and, most importantly, decodingof these arrays consumes considerable CPUtime. Therefore, substantial ...

Software—Practice & ExperienceD. Lemire LICEF Research Center, TELUQ, Montreal, QC, Canada

Decoding billions of integers per second through vectorization

In many important applications -- such as search engines and relationaldatabase systems -- data is stored in the form of arrays of integers. Encodingand, most importantly, decoding of these arrays consumes considerable CPU time.Therefore, substantial effort has been made to reduce costs associate…

arXiv.orgDaniel Lemire

実装

GitHub - lemire/JavaFastPFOR: A simple integer compression library in Java

A simple integer compression library in Java . Contribute to lemire/JavaFastPFOR development by creating an account on GitHub.

GitHublemire

Elias-Fano Family

Elias-Fano とその亜種（他の手法と組み合わせたハイブリッドを含む）

Elias-Fano [Elias74, Fano71]

ソート済み整数配列は上位ビットが共有しやすいことに着目
下位ビット（ l ビットとする）と上位ビットを分けて保存する
- 下位ビットはそのまま
- 上位ビットは、同じ上位ビットをもつ組み合わせ（クラスタ）ごとに、そのクラスタの個数を Unary code でエンコードする
- たとえば以下の例では、クラスタの数がそれぞれ 3, 3, 1, 1, 2, 0, 1, 1 なので、上位ビットは 1110.1110.10.10.110.0.10.10 というビットベクトルにエンコードされる

Giulio Ermanno Pibiri and Rossano Venturini. 2020. Techniques for Inverted Index Compression. Table 7

ランダムアクセスが可能
- 下位ビットの配列 ( low_bits ) からのデコードは、単に low_bits[i] でよい
- 上位ビットをエンコードした配列 ( high_bits ) はビットベクトルなので、 Rank 演算と Select 演算を利用できる
- i 番目の要素の上位ビットのデコードは、 Rank0(Select1(i)) を計算すればよい

Efficient Storage and Retrieval by Content and Address of Static Files | Journal of the ACM

We consider a set of static files or inventories, each consisting of the same numberof entries, each entry a binary word of the same fixed length selected (with replacement)from the set of all binary sequences of that length, and the entries in each ...

Journal of the ACMPeter Elias Department of Electrical Engineering, Massachusetts Institute of Technology, Cambridge, MA

PEF [Ottaviano&Venturini14]

Partitioned Elias-Fano
Elias-Fano に対して、カーディナリティによるパーティショニングを行う
ソート済み整数列が近くに集まっている場合、それらを密ビットベクトル、いわゆるビットベクトル (characteristic bit-vector) で表現する
- たとえば [2,3,4,5,6,7,10,11,13] は 0111111001101 （左から 1, 2, 3, … を表す）で表現できる
- 整数列が密な場合、ビットベクトル表現もコンパクトになる
疎な整数列の部分に対しては、 Elias-Fano でエンコードする

A Crash Course on Data Compression. 3. List Compressors p.24

Partitioned Elias-Fano indexes | Proceedings of the 37th international ACM SIGIR conference on Research & development in information retrieval

ACM ConferencesGiuseppe Ottaviano ISTI-CNR, Pisa, Italy

Roaring [Chambi+16, Lemire+16, Lemire+18]

Universe （エンコード対象がとりうる整数値の空間）に対するパーティショニングを行う
- PEF のようにカーディナリティによってパーティショニングするのではなく、固定のビット数でパーティショニングする
- たとえば Universe が 2^32 だったとして、上位 16 ビットでパーティショニングすると、空間は 2^16 のチャンクに分割される
各チャンクは、密な場合はビットベクトルでエンコードし、疎な場合は sorted list としてエンコードする
- 疎な場合は、同様にさらに Universe を分割できる
- たとえば、上の例では、 2^16 の Universe をさらに 2^8 に分割できる
カーディナリティによるパーティショニングよりもサイズは大きくなるが、 intersection や union は高速にできる
- すべてのポスティングリストにおいて、空間が同じように分割されているため

A Crash Course on Data Compression. 3. List Compressors p.25

Better bitmap performance with Roaring bitmaps

Bitmap indexes are commonly used in databases and search engines. Byexploiting bit-level parallelism, they can significantly accelerate queries.However, they can use much memory, and thus we might prefer compressed bitmapindexes. Following Oracle’s lead, bitmaps are often compressed using run-len…

arXiv.orgSamy Chambi

Consistently faster and smaller compressed bitmaps with Roaring

Compressed bitmap indexes are used in databases and search engines. Manybitmap compression techniques have been proposed, almost all relying primarilyon run-length encoding (RLE). However, on unsorted data, we can get superiorperformance with a hybrid compression technique that uses both uncompre…

arXiv.orgDaniel Lemire

Roaring Bitmaps: Implementation of an Optimized Software Library

Compressed bitmap indexes are used in systems such as Git or Oracle toaccelerate queries. They represent sets and often support operations such asunions, intersections, differences, and symmetric differences. Severalimportant systems such as Elasticsearch, Apache Spark, Netflix’s Atlas,LinkedIn’…

arXiv.orgDaniel Lemire

Slicing [Pibiri19]

Sliced Indexes とも
Roaring と同様、 Universe によるパーティショニングを行う
- Roaring が 2 階層までの分割だったのに対して、こちらは最大 3 階層

Fast and Compact Set Intersection through Recursive Universe Partitioning

We present a data structure that encodes a sorted integer sequence in small space allowing, at the same time, fast intersection operations. The data layout is carefully designed to exploit word-level parallelism and SIMD instructions, hence providing good practical performance. The core algorithmic…

IEEE Xplore

On Slicing Sorted Integer Sequences

Representing sorted integer sequences in small space is a central problem forlarge-scale retrieval systems such as Web search engines. Efficient queryresolution, e.g., intersection or random access, is achieved by carefullypartitioning the sequences. In this work we describe and compare two diffe…

arXiv.orgGiulio Ermanno Pibiri

実装

GitHub - jermp/s_indexes: Universe-sliced indexes in C++.

Universe-sliced indexes in C++. Contribute to jermp/s_indexes development by creating an account on GitHub.

GitHubjermp

Binary Interpolative

BIC [Moffat&Stuiver96, Moffat&Stuiver00]

Binary Interpolative coding (BIC)
2分木を使った再帰的なアルゴリズム
- 中央の要素から深さ優先順にエンコードしていく
S[i, j] の範囲を BIC でエンコードするとき、中央の要素の位置を m とすると、中央の要素は S[m] - low - m + i でエンコードされる
- low はその範囲の最小値 (= S[i])
- S[m] - low は最小値からの相対量
- そこからさらに中央の要素の相対位置を引く
下の例では、 [7, 2, 0, 0, 18, 5, 3, 16, 1, 7] となる
整数列が密なとき、非常にコンパクト
一方で、再帰的なため、デコードは遅め

Giulio Ermanno Pibiri and Rossano Venturini. 2020. Inverted Index Compression. Figure 2

Binary Interpolative Coding for Effective Index Compression | Information Retrieval

Information retrieval systems contain large volumes of text, and currently have typicalsizes into the gigabyte range. Inverted indexes are one important method for providingsearch facilities into these collections, but unless compressed require a ...

Information Retrieval[email protected]

Directly-Addressable

ランダムアクセスが可能

DAC [Brisaboa+13]

Directly-addressable code (DAC)
すべての整数を b ビットずつに分割
すべての整数の最初の b ビットをストリーム C1 に入れる、（あれば）次の b ビットを C2 に入れる…と繰り返す
- 1 ビットの制御ビットも入れる（続きがあれば 1、なければ 0）

Nieves R Brisaboa, Susana Ladra, and Gonzalo Navarro. 2013. DACs: Bringing direct access to variable-length codes. Fig. 1

制御ビットの配列 B1, B2, … に対して Rank1 することで、もとの整数配列を全部デコードせずにランダムアクセスが可能
下記の例（記法が論文と少し違うので注意）で L[5] にアクセスしたいとき、
- B1[5] が 1 なので、次のチャンク (C2) にアクセスする必要がある
- C2 のインデックスは Rank1(B1, 5) = 2
- B2[2] は 0 なので、これで終わり
- C1[5] = 101 と C2[2] = 001 を連結して 001.101 (=13) を得る

A Crash Course on Data Compression. 3. List Compressors p.45

Repositorio Académico - Universidad de Chile

Repositorio académico de la Universidad de Chile. Tesis, artículos y libros publicados en formato digital con distintos niveles de acceso

Brisaboa, Nieves R.

実装

https://lbd.udc.es/research/DACS/

Dictionary-based

DINT [Pibiri+19]

辞書を使ってポスティングリストの圧縮率を高めた
圧縮率と速度を両立

Giulio Ermanno Pibiri, Matthias Petri, and Alistair Moffat. 2019. Fast Dictionary-Based Compression for Inverted Indexes. Fig. 6

Fast Dictionary-Based Compression for Inverted Indexes | Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining

ACM ConferencesGiulio Ermanno Pibiri University of Pisa & ISTI-CNR, Pisa, Italy

Bitmap Compression

整数値をビットマップで表現する
- 整数 i を表現するとき、ビット配列の i 番目の位置にビットを立てる
- 0100100001 なら 2, 5, 10
このビットマップを圧縮する技法が bitmap compression

Jianguo Wang, Chunbin Lin, Yannis Papakonstantinou, and Steven Swanson. 2017. An Experimental Study of Bitmap Compression vs. Inverted List Compression. p.3 Figure 1

整数列圧縮の手法（PforDelta など）と比較して Intersection (AND) は速い
Union (OR) やデコードは整数列圧縮のほうが速い
Roaring はビットマップ圧縮と整数列圧縮のハイブリッド
- 他の bitmap compression の手法と違って RLE (run length encoding) を使っていない
- 全体的に他の bitmap compression の手法より Roaring のほうが良い

Jianguo Wang, Chunbin Lin, Yannis Papakonstantinou, and Steven Swanson. 2017. An Experimental Study of Bitmap Compression vs. Inverted List Compression. Figure 3

An Experimental Study of Bitmap Compression vs. Inverted List Compression from Takeshi Yamamuro

BBC [Antoshenkov95]

Byte-aligned Bitmap Code
ビットマップを 1 byte (8-bit) ずつに分割
これらの byte を fill byte と literal byte に分類
- fill byte: すべてのビットが同じ byte
- literal byte: それ以外
fill byte と literal byte の並びのパターンごとに圧縮

Jianguo Wang, Chunbin Lin, Yannis Papakonstantinou, and Steven Swanson. 2017. An Experimental Study of Bitmap Compression vs. Inverted List Compression. Figure 2

WAH [Kesheng+01]

Word-Alighned Hybrid
ビットマップを 31-bit ずつの group に分割
これらを fill group と literal group に分類
- fill group: すべてのビットが同じ
- literal group: それ以外
先頭に 1 bit の判定フラグを足す
- 1 なら fill group
fill group は RLE でエンコード
- 2 bit 目に 1-fill group かどうかのフラグをもつ
- 残りの 30 bits に長さをエンコード
literal group はそのまま
Intersection (AND) や Union (OR) はデコードせずに計算可能

Notes on Design and Implementation of Compressed Bit Vectors

EWAH [Lemire+10]

Enhanced Word-Alighned Hybrid
WAH の改良
- literal group が多い場合に WAH は容量効率が悪い
ビットマップを 32-bit の group に分割
p 個（p ≤ 65535）の fill groups と q 個（q ≤ 32767）の literal group をひとかたまりとする
先頭に 32-bit の marker を置く
- 最初の 1 bit: 1-fill group かどうかのフラグ
- 次の 16 bits: fill groups の数 p をエンコード
- 最後の 15 bits: literal groups の数 q をエンコード

Sorting improves word-aligned bitmap indexes

Bitmap indexes must be compressed to reduce input/output costs and minimizeCPU usage. To accelerate logical operations (AND, OR, XOR) over bitmaps, we usetechniques based on run-length encoding (RLE), such as Word-Aligned Hybrid(WAH) compression. These techniques are sensitive to the order of the…

arXiv.orgDaniel Lemire

CONCISE [Colantonio&Pietro10]

Compressed N Composable Integer Set
WAH の改良
- fill group と 1 ビットだけ異なる値をもつ literal group （mixed fill group と呼ぶ）に着目
- そのビットを odd bit と呼び、その位置をエンコードすることで容量を削減する
ビットマップを 31-bit ずつの group に分割（WAHと同じ）
先頭の 1 bit を literal group かどうかの判定フラグにする
- literal group の場合、残りの 31 bits に literal group をそのまま保存
連続する fill group の並びは、以下のように RLE で表現
- EWAH の marker のように fill group の run を 32-bit で表現
- 1 bit 目は 0（literal group と区別するため）
- 2 bit 目に 1-fill group かどうかのフラグをもつ（WAHと同じ）
- 次の 5 bits で odd bit の位置をエンコード
  - odd bit がない場合は 00000
- 残りの 25 bits で fill groups の数 - 1 を保存

CONCISE: Compressed ‘n’ Composable Integer Set

Bit arrays, or bitmaps, are used to significantly speed up set operations inseveral areas, such as data warehousing, information retrieval, and datamining, to cite a few. However, bitmaps usually use a large storage space, thusrequiring compression. Nevertheless, there is a space-time tradeoff am…

arXiv.orgAlessandro Colantonio

PLWAH [Deliège&Pedersen10]

Position List WAH
CONCISE に似ているが、mixed fill group の表現が異なる

François Deliège and Torben Bach Pedersen. 2010. Position list word aligned hybrid: optimizing space and performance for compressed bitmaps. Figure 1

François Deliège and Torben Bach Pedersen. 2010. Position list word aligned hybrid: optimizing space and performance for compressed bitmaps. Figure 2

https://openproceedings.org/2010/conf/edbt/DeliegeP10.pdf

VALWAH [Guzun+14]

Variable-Aligned WAH
WAH は 30 bits の RLE で fill groups の並びを表現していたが、実際には連続する fill groups は少ない
32-bit に複数のセグメントをエンコード
- 可変のセグメント長
容量のオーバーヘッドとクエリの速度のトレードオフを調整するパラメータ lambda をもつ
セグメント長を可変にすることで容量は小さくなるが、アラインメントの問題でクエリは遅い

SBH [Kim+16]

Super Byte-Aligned Hybrid
容量効率を上げるために word-aligned ではなく byte-aligned にした
ビットマップを 7-bit のグループに分割
連続する fill groups の数 k （k ≤ 4093）をエンコード
- k ≤ 63 のとき
  - 1 bit 目は 0
  - 2 bit 目に 1-fill group かどうかのフラグをもつ
  - 残りの 6 bits で k をエンコード
- 63 < k ≤ 4093 のとき、2バイトで fill groups を表現
  - 1 byte 目
    - 1 bit 目は 0
    - 2 bit 目に 1-fill group かどうかのフラグをもつ
    - 残りの 6 bits で k の下位 6 bits をエンコード
  - 2 byte 目
    - 最初の 2 bits は 1 byte 目と同じ
    - 残りの 6 bits で k の上位 6 bits をエンコード

https://dbs.snu.ac.kr/papers/sbh16.pdf

実装とベンチマーク

整数（列）圧縮アルゴリズムとそのベンチマークの Java 実装。以下の実装が含まれる。

BinaryPacking
XorBinaryPacking
DeltaZigzagBinaryPacking
FastPFor
Group Simple9
NewPFD, NewPDFS9, NewPFDS16
OptPFD, OptPFDS9, OptPFDS16
Simple16
Simple9
VByte

現時点 (2022-10-23) では動作させるために Java 19 の実行環境が必要。

ビルドとベンチマークの実行には Maven が使用できる。

mvn compile

mvn exec:java

参考文献

Vo Ngoc Anh and Alistair Moffat. 2005. Inverted Index Compression Using Word-Aligned Binary Codes. Inf. Retr. 8, 1 (January 2005), 151–166. https://doi.org/10.1023/B:INRT.0000048490.99518.5c
Vo Ngoc Anh and Alistair Moffat. 2010. Index compression using 64-bit words. Softw. Pract. Exper. 40, 2 (February 2010), 131–147.
G. Antoshenkov. 1995. Byte-aligned bitmap compression. In Proceedings of the Conference on Data Compression (DCC '95). IEEE Computer Society, USA, 476.
Nieves R Brisaboa, Susana Ladra, and Gonzalo Navarro. 2013. DACs: Bringing direct access to variable-length codes. Information Processing & Management 49, 1 (2013), 392–404.
Stefan Büttcher, Charles Clarke, and Gordon V. Cormack. 2010. Information Retrieval: Implementing and Evaluating Search Engines. The MIT Press.
Samy Chambi, Daniel Lemire, Owen Kaser, and Robert Godin. 2016. Better bitmap performance with Roaring bitmaps. Softw. Pract. Exper. 46, 5 (May 2016), 709–719. https://doi.org/10.1002/spe.2325
Alessandro Colantonio and Roberto Di Pietro. 2010. Concise: Compressed 'n' Composable Integer Set. Inf. Process. Lett. 110, 16 (July, 2010), 644–650. https://doi.org/10.1016/j.ipl.2010.05.018
Jeffrey Dean. 2009. Challenges in building large-scale information retrieval systems: invited talk. In Proceedings of the Second ACM International Conference on Web Search and Data Mining (WSDM '09). Association for Computing Machinery, New York, NY, USA, 1. https://doi.org/10.1145/1498759.1498761
François Deliège and Torben Bach Pedersen. 2010. Position list word aligned hybrid: optimizing space and performance for compressed bitmaps. In Proceedings of the 13th International Conference on Extending Database Technology (EDBT '10). Association for Computing Machinery, New York, NY, USA, 228–239. https://doi.org/10.1145/1739041.1739071
Peter Elias. 1974. Efficient Storage and Retrieval by Content and Address of Static Files. J. ACM 21, 2 (April 1974), 246–260. https://doi.org/10.1145/321812.321820
G. Guzun, G. Canahuate, D. Chiu, and J. Sawin. A tunable compression framework for bitmap indices. In ICDE, pages 484–495, 2014.
Robert Mario Fano. 1971. On the number of bits required to implement an associative memory. Memorandum 61, Computer Structures Group, MIT (1971).
A. S. Kesheng Wu, Ekow J. Otoo and H. Nordberg. Notes on design and implementation of compressed bit vectors, 2001.
S. Kim, J. Lee, S. R. Satti, and B. Moon. Sbh: Super byte-aligned hybrid bitmap compression. IS, 62:155--168, 2016.
Daniel Lemire, Owen Kaser, and Kamel Aouiche. 2010. Sorting improves word-aligned bitmap indexes. Data Knowl. Eng. 69, 1 (January, 2010), 3–28. https://doi.org/10.1016/j.datak.2009.08.006
D. Lemire and L. Boytsov. 2015. Decoding billions of integers per second through vectorization. Softw. Pract. Exper. 45, 1 (January 2015), 1–29. https://doi.org/10.1002/spe.2203
Daniel Lemire, Gregory Ssi-Yan-Kai, and Owen Kaser. 2016. Consistently faster and smaller compressed bitmaps with Roaring. Softw. Pract. Exper. 46, 11 (November 2016), 1547–1569. https://doi.org/10.1002/spe.2402
Daniel Lemire, Owen Kaser, Nathan Kurz, Luca Deri, Chris O’Hara, François Saint-Jacques, and Gregory Ssi-Yan-Kai. 2018. Roaring bitmaps: Implementation of an optimized software library. Software: Practice and Experience 48, 4 (2018), 867–895.
Daniel Lemire, Nathan Kurz, and Christoph Rupp. 2018. Stream VByte: Faster byte-oriented integer compression. Inf. Process. Lett. 130, (February 2018), 1–6. https://doi.org/10.1016/j.ipl.2017.09.011
Christopher D. Manning, Prabhakar Raghavan, and Hinrich Schütze. 2008. Introduction to Information Retrieval. Cambridge University Press, USA.
Alistair Moffat and Lang Stuiver. 1996. Exploiting clustering in inverted file compression. In Proceedings of the Data Compression Conference (DCC’96). 82--91.
Alistair Moffat and Lang Stuiver. 2000. Binary Interpolative Coding for Effective Index Compression. Inf. Retr. 3, 1 (July 2000), 25–47. https://doi.org/10.1023/A:1013002601898
Giuseppe Ottaviano and Rossano Venturini. 2014. Partitioned Elias-Fano indexes. In Proceedings of the 37th international ACM SIGIR conference on Research & development in information retrieval (SIGIR '14). Association for Computing Machinery, New York, NY, USA, 273–282. https://doi.org/10.1145/2600428.2609615
Giulio Ermanno Pibiri, Matthias Petri, and Alistair Moffat. 2019. Fast Dictionary-Based Compression for Inverted Indexes. In Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining (WSDM '19). Association for Computing Machinery, New York, NY, USA, 6–14. https://doi.org/10.1145/3289600.3290962
Giulio Ermanno Pibiri. 2019. On Slicing Sorted Integer Sequences. CoRR abs/1907.01032 (2019). http://arxiv.org/abs/1907.01032
Giulio Ermanno Pibiri and Rossano Venturini. 2020. On Optimally Partitioning Variable-Byte Codes. IEEE Trans. on Knowl. and Data Eng. 32, 9 (Sept. 2020), 1812–1823. https://doi.org/10.1109/TKDE.2019.2911288
Giulio Ermanno Pibiri and Rossano Venturini. 2020. Techniques for Inverted Index Compression. ACM Comput. Surv. 53, 6, Article 125 (November 2021), 36 pages. https://doi.org/10.1145/3415148
Jeff Plaisance, Nathan Kurz, and Daniel Lemire. 2015. Vectorized VByte Decoding. In International Symposium on Web Algorithms.
Alexander A. Stepanov, Anil R. Gangolli, Daniel E. Rose, Ryan J. Ernst, and Paramjit S. Oberoi. 2011. SIMD-based decoding of posting lists. In Proceedings of the 20th ACM international conference on Information and knowledge management (CIKM '11). Association for Computing Machinery, New York, NY, USA, 317–326. https://doi.org/10.1145/2063576.2063627
Larry H Thiel and HS Heaps. 1972. Program design for retrospective searches on large data bases. Information Storage and Retrieval 8, 1 (1972), 1–20.
Andrew Trotman. 2014. Compression, SIMD, and Postings Lists. In Proceedings of the 2014 Australasian Document Computing Symposium (ADCS '14). Association for Computing Machinery, New York, NY, USA, 50–57. https://doi.org/10.1145/2682862.2682870
Jianguo Wang, Chunbin Lin, Yannis Papakonstantinou, and Steven Swanson. 2017. An Experimental Study of Bitmap Compression vs. Inverted List Compression. In Proceedings of the 2017 ACM International Conference on Management of Data (SIGMOD '17). Association for Computing Machinery, New York, NY, USA, 993–1008. https://doi.org/10.1145/3035918.3064007
Hao Yan, Shuai Ding, and Torsten Suel. 2009. Inverted index compression and query processing with optimized document ordering. In Proceedings of the 18th international conference on World wide web (WWW '09). Association for Computing Machinery, New York, NY, USA, 401–410. https://doi.org/10.1145/1526709.1526764
Jiangong Zhang, Xiaohui Long, and Torsten Suel. 2008. Performance of compressed inverted list caching in search engines. In Proceedings of the 17th international conference on World Wide Web (WWW '08). Association for Computing Machinery, New York, NY, USA, 387–396. https://doi.org/10.1145/1367497.1367550
Marcin Zukowski, Sandor Heman, Niels Nes, and Peter Boncz. 2006. Super-Scalar RAM-CPU Cache Compression. In Proceedings of the 22nd International Conference on Data Engineering (ICDE '06). IEEE Computer Society, USA, 59. https://doi.org/10.1109/ICDE.2006.150