近似最近傍探索における新しいビット量子化手法、RaBitQとBBQ
Elasticsearch 8.16 で Better Binary Quantization (BBQ) という、新しい密ベクトルのフィールドタイプが追加されました。 Dense vector field type | Elasticsearch Guide | Elastic Elasticsearch version 8.16.0 New features | Elasticsearch Guide | Elastic Adding new experimental bbq index types by benwtrent · Pull Request #114439 · elastic/elasticsearch · GitHub Elasticsearch ではベクトルの各次元の int8 や int4 への量子化をサポートしていますが、BBQ ではビットにまで量子化することで、
AtCoder での実力アップを目指そう！ ～競プロ典型 90 問～ - Qiita
競プロにおける「上達の壁」 そこで私は、主に以下の 3 点が競技プログラミングにおける上達の壁になっているのではないかと考えています。 基礎的なコーディングの知識。for 文・条件分岐・配列などを使った基本的なプログラムが書けるかどうか。（レーティング 1～99 程度） 競プロで戦うために必要な、最低限のアルゴリズムや数学の知識。例えば二分探索・動的計画法・グラフ理論・逆元といったものが挙げられる。（レーティング 100～1199 程度） アルゴリズムや数学的知識 [2. で扱ったもの] をどうやって実際の問題に応用するか、考察面・実装面両方含めた典型テクニック。（レーティング 200～1999 程度） 今はどの壁が問題か？ 現在、1. と 2. についてはかなり教材が整備されており、例えば 1. のプログラミングの基本を学ぶにあたっては、 C++入門 AtCoder Programmin
Minimal Perfect Hash Functions | Gopher Academy Blog
A regular hash function turns a key (a string or a number) into an integer. Most people will know them as either the cryptographic hash functions (MD5, SHA1, SHA256, etc) or their smaller non-cryptographic counterparts frequently encountered in hash tables (the map keyword in Go). Collisions, where two input values hash to the same integer, can be an annoyance in hash tables and disastrous in cryp
Indeed MPH:高速で小さいイミュータブルなキー・バリューストア - Indeed エンジニアリング・ブログ
膨大なデータを抱えるアプリケーションをスケールする際に、どのようなストレージを導入するべきなのでしょうか？どうしたら大量のデータセットを安全に保存し、効率的に読み書きを行えるのでしょうか？こうした疑問は、よく SQL か NoSQL のどちらを使うべきかという議論になりがちですが、どちらもそれぞれメリットとデメリットがあります。 ですが、もしデータデースにまつわる問題を全て回避できる三番目の選択肢があるとしたらどうでしょうか？ コンシューマは数分おきにしか更新を必要としていないかもしれません。この場合、データセットをメモリ内に読み込めると、劇的にアクセス速度があがり、大規模のスケールが可能になります。このことから、 Indeed では多くのプロジェクトで、必要なデータの完全なコピーを、各コンシューマに渡しているので、 SQL 対 NoSQL の議論をする必要がありません。これを実現するに
Perfect Hashing
Initial hash returns (A,B), final hash is A^tab[B] The perfect hash algorithm I use isn't a Pearson hash. My perfect hash algorithm uses an initial hash to find a pair (A,B) for each keyword, then it generates a mapping table tab[] so that A^tab[B] (or A^scramble[tab[B]]) is unique for each keyword. tab[] is always a power of two. When tab[] has 4096 or more entries, scramble[] is used and tab[] h
最小完全ハッシュ関数の作り方
■順列型の最小完全ハッシュ関数 ０から４までの５個の数字が下のように並んでいる場合を例にして説明します。 ５個の数字の並べ方は５！通りありますので５！(=120)通りの並べ方の総てに対して0から119までの数値を一意に割り付けることが目的となります。 ３４１０２ ここでは左側から順に数字を見ていくことにします。最初の数字は３で残りの数字の個数は４個ですね。 この残れさた数字の個数分の総順列数は４！ですが、この数量を基数と言います。 つまり左端の数字が何であるかを完全に識別する為に最低限必要な基本となる重みのことです。 従って先ず最初の数字３に基数である４！を掛け算してはじき出します。 [３]４１０２ → ３＊４！ 次に左から２番目の数字ですが、ここから先はとても注意が必要です。 ２番目の数字は４で残りの数字の個数は３個です。残りの数字の個数が３個なので基数は３！になります。つまり基数が変化
DAWG(4-1): 完全ハッシュ関数 - sileのブログ
四回目の前半。 DAWGのキーに一意なIDをマッピングするための最小完全ハッシュ関数を実装。 ※ ただし今回実装分は、"最小"のつかないただの完全ハッシュ関数まで 参考元 『Simple and Space-Efficient Minimal Perfect Hash Functions』*1を参考にした。 ただし、まだ実装に必要な箇所に軽く目を通しただけなので、詳細は理解していない。 ※ いつものことだけど、ちゃんと知りたい人はもとの論文を参照のこと 概要 とりあえず現状での理解。※ 間違っている可能性あり! 定義: 完全ハッシュ関数(PHF, perfect hash function): N個のキーを0からM未満の一意な値(整数値?)にマッピングする関数 ※ M >= N 最小完全ハッシュ関数(MPHF, minimal perfect hash function): N個のキーを0
Order-Maintenance Problem - たまに書く
記念すべき最初の記事です。 最近忘却がひどいので、学んだことをちゃんとここに残していけたらなと思います。 内容 本記事では以下の論文 Bender M.A., Cole R., Demaine E.D., Farach-Colton M., Zito J. Two Simplified Algorithms for Maintaining Order in a List. ESA 2002. の内容（の一部）を紹介します。 内容 問題設定 Benderらの解法 (ESA 2002) 再割当アルゴリズム 疎な境界タグ区間 定理： order を O(1) 時間で実行できる 定理： insert を O(log n) ならし時間で実行できる まとめ 問題設定 系列 (x_1, x_2, ..., x_n) に対し、以下の操作を提供するデータ構造を考えます。 insert(x, x_i): 新し
文字列から浮動小数点数に変換する、なるべく速く - toge's diary
TL;DR 文字列から浮動小数点数に変換するならfastfloat使いましょう。 私が試せる環境で比較する限り、とても速いです。 細かいことが気になります C++でちょっとしたプログラムを書くときにいつも気になるのが 「文字列データから指定データ型への変換処理をどうやって効率的に書くか」 です。私だけかもしれませんが。 特に悩んでしまうのが「文字列→浮動小数点」です。 std::scanf, std::stringstreamを使うものは大抵すごく遅い std::strtodstd::stodはstd::stringへの変換が入るので避けたい std::from_charsは(libstdc++が)浮動小数点型に対応していない boost::sprit::qiが何故か速いのだけれどこのためにboost::sprit使うのは重い と色々制約が多いのです。どうにかならないものか。 fast_f
赤黒木の本質 - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? この記事はデータ構造とアルゴリズム Advent Calendar 2019 16日目の記事です。 15日目は@minaminaoさんによる「すごいTrie」です。 17日目は@takilogさんによる「Fréchet距離の計算アルゴリズム」です。 はじめに この記事では有名なデータ構造である赤黒木がなぜあのようなトリッキーな定義になっているのかその本質について解説します。 赤黒木の定義を見てトリッキーと思うかどうかは個人差あるかと思いますが、少なくとも僕が初めて赤黒木を学んだ時はなぜこのような定義になっているのか、そしてどうやって思い
TrailNote : トラックポイントを間引くアルゴリズム
旧バージョンでは、独自のアルゴリズムでトラックポイントを間引いていたのですが、とても処理が遅く性能も悪かったので、Ver1.2からは先人の知恵をお借りすることにしました。 調べた所、点を間引く方式としては、Douglas-Peuckerアルゴリズムが有名なようです。 Douglas−Peuckerアルゴリズム Douglas-Peuckerアルゴリズムは、ラインを単純化するアルゴリズムで、とてもシンプルです。 手順は、以下のようになるようです（こちらを参考にしました）。 ルートの始点、終点をプロット対象とする。 プロット対象をつなげた直線と、その間の各点との距離を調べる。 許容距離(ε)以上離れた点で、最も離れた点を探し出し、そこを新たにプロット対象とする。 もし、ε以上離れた点がなければ、終了。 2〜3の処理を再帰的に繰り返す。 最も離れた点（ルートの形を特徴づける点）を残していき、近い
Re: 明日使えないすごいビット演算 - えびちゃんの日記
たぶん今日も使えないと思うんですけど（名推理）． タイトルの元ネタは これ． 上のスライドでは，ワードサイズ \(w\) に対して，以下の演算を \(O(\log w)\) time で求める方法が書かれています． 立っている最上位のビットを取り出す：msb 立っているビットの個数を取り出す：popcount この記事では，このうち msb の添字を \(O(1)\) time で求める方法を紹介してみます． 今後，単に msb と言った場合に添字の方を指すことにします． ソースコードは一番下にあります． 参考にした資料はいつもの CS166 の スライド． 以下では，ワードサイズの四則演算およびビット演算を一単位時間で計算できることを仮定します*1．すなわち，\(w\) bits の整数に関するこれらの演算を一単位時間で行えます． また，扱う整数は符号なし整数とし，\(2^w\) を法と
明日使えないすごいビット演算
最適輸送問題（Wasserstein 距離）を解く方法についてのさまざまなアプローチ・アルゴリズムを紹介します。 線形計画を使った定式化の基礎からはじめて、以下の五つのアルゴリズムを紹介します。 1. ネットワークシンプレックス法 2. ハンガリアン法 3. Sinkhorn アルゴリズム 4. ニューラルネットワークによる推定 5. スライス法 このスライドは第三回 0x-seminar https://sites.google.com/view/uda-0x-seminar/home/0x03 で使用したものです。自己完結するよう心がけたのでセミナーに参加していない人にも役立つスライドになっています。 『最適輸送の理論とアルゴリズム』好評発売中！ https://www.amazon.co.jp/dp/4065305144 Speakerdeck にもアップロードしました: https
キャッシュ機構 TinyLFU のアーキテクチャと、それを支えるアルゴリズム - 好奇心に殺される。
Computer Science キャッシュ機構 TinyLFU のアーキテクチャと、それを支えるアルゴリズム TinyLFUの論文を読んだので概要と、それを支えるアルゴリズムを紹介します。 Overview TinyLFU はアクセス頻度を近似し、軽量でハイパフォーマンスに設計されたキャッシュアルゴリズムです。最近、Database Internals を読んでいて TinyLFU を知ったのですが、Database Internals では TinyLFU の詳細が書かれていなかったので、TinyLFUが提案されている論文を読んでみました。その内容をザックリ解説してみようと思います。 論文はこちらです。 TinyLFU: A Highly Efficient Cache Admission Policy いきなりTinyLFUの紹介を始めると混乱するので、ベースとなる技術やアルゴリズム
Run-Length FM-Index - koki
FM-index は検索対象のテキストから予め索引を構築しておくことで，テキストに含まれる任意のパターン文字列の個数を数えるクエリ$ \mathrm{count} を，テキストのサイズに依らず高速に実行できるデータ構造です．加えて，suffix array や inverse suffix array の一部を追加で保持しておくことで，パターンの位置の列挙 $ \mathrm{locate}やテキストの復元 $ \mathrm{extract}といったクエリを高速に実行することができます（自己索引）． 主要な応用としてゲノム解析（例：HISAT2）などが挙げられます．身近なところでは，arXiv をコーパスとした高速な英文コロケーション検索を提供する Hyper Collocation でも用いられています（解説）． FM-Index に関しては，高速文字列解析の世界 や 簡潔データ構造
様々なrate limitアルゴリズム - Carpe Diem
概要 インターネットに晒されているWebサービスでは TV等で紹介されたことによる大量流入 悪意ある人物からの攻撃 クライアントのバグに依る大量リクエスト など、本来想定していた以上のトラフィックが来ることはよくあります。 単純にシステムを構築すると大規模トラフィックに対応できずシステムがスローダウンしてしまうため、何かしらrate limitをかけておいた方が良いです。 ただしrate limitと一口に入っても色々あるため、今回は主なrate limitアルゴリズムを紹介します。 Leaky bucket Leaky bucketはデータ転送レートを一定にする（＝上限を設定する）アルゴリズムです。 下の図のように、様々な流量の水流がそのバケツに流れ込んでも小さな穴からは一定の水流が流れ出す仕組みです。 ref: What is the difference between token
Rustで簡潔データ構造のライブラリを3つリリースしました
活動報告。 Rustで簡潔データ構造のライブラリを3つリリースしました。 これらの簡潔データ構造に興味のある方、APIを綺麗に整備してREADMEも分かりやすく書いたつもりですので、是非スターをお願いします✌ SIGMOD 2018の論文を眺めていて、Best PaperのSuRF: Practical Range Query Filtering with Fast Succinct Triesを読んで興味を持ちました。 一致検索も範囲検索も高速にできる省メモリなデータ構造SuRFに関する論文。どうやら簡潔データ構造を使っているらしい。 簡潔データ構造というのは、データサイズが情報理論的下限と同程度に小さく、かつ非圧縮なデータ構造と比肩する高速さを兼ね備えたデータ構造です。 チート級ですが、多くの場合「データの追加や更新には対応してない」などの制約があるため、使う場面は限定されたりします。
How we keep Search relevant and useful
When you come to Google Search, our goal is to connect you with useful information as quickly as possible. That information can take many forms, and over the years the search results page has evolved to include not only a list of blue links to pages across the web, but also useful features to help you find what you’re looking for even faster. Some examples include featured snippets, which highligh
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Number Parsing at a Gigabyte per Second – Daniel Lemire's blog
Space- and Time-Efficient String Dictionaries - Tokushima University Institutional Repository