SQL実行時のブルームフィルタ(Bloom Filter)アルゴリズム | フューチャー技術ブログ
1. 初めにDBにおける処理はSQLによって記述しますが、データの取得するために具体的にどのような内部処理を行うかという点までは記述しません。 ここでいう内部処理とは「SQLの書き換え」「インデックスの使用」「結合アルゴリズムの選択」などがDBMSのオプティマイザによって選択されて実施されることを指します。 SQLのパフォーマンスを見るにあたっては上記の内部処理について正しく理解する必要があります。 本Blogでは、重要なアルゴリズムであるにもかかわらず、まとまった情報が少ないSQL実行時におけるブルームフィルタ(Bloom Filter)についてOracleをもとに紹介を行います。 Bloom Filterは結合処理を効率化するために、結合の前段階で利用される技術になります。 公式なドキュメントとしては以下になります。 Oracle Database SQLチューニング・ガイド 12cリ
確率的データ構造の比較：カッコウフィルタ対ブルームフィルタ | POSTD
確率的データ構造は少ないメモリでデータをコンパクトに保存し、保存されたデータに関するクエリに対し、おおよその答えを提供してくれます。クエリに対し空間効率の良い方法で答えるように設計されており、それはつまり、正確さを犠牲にするということにもなります。しかし、これらは一般的に、問われているデータ構造の仕様にもよりますが、誤差率の保証と境界を提供してくれます。メモリ使用量が少ないため、確率的データ構造はストリーミングや低出力の設定に特に有用なのです。ですから、動画の視聴回数を数えたり、過去に投稿された一意となるツイートのリストを維持したりするなど、ビッグデータの環境下では非常に有用です。例えば、 HyperLogLog++ 構造 は、2.56KBのメモリで最大790億の一意のアイテムを数えることができるのですが、誤差率はわずか1.65パーセントです。 Fast Forward Labsのチームは
CHAGEの裏側: ブルームフィルタとISONの逆引き高速化 | IIJ Engineers Blog
セキュリティ本部 セキュリティ情報統括室に所属 システム開発者。2000年問題で「2038年問題は定年で対応しなくていい！」とフラグを...。 CHAGE開発者のヒラマツです。 前回（CHAGEの裏側: D3.jsの紹介）同様、CHAGEの紹介と並行して、CHAGEの中が気になる人に、CHAGEで使われている技術をちょっと濃い目に解説するという企画です。 今回は、本編（CHAGE の動き）がISONネタなので、こちらもISONに関係ある話として、ブルームフィルタについて書きます。 ブルームフィルタをざっくり解説してから、ブルームフィルタの具体的な使用例としてISONでの逆引き高速化の方法を紹介していきたいと思います。 目指すのは、ちゃんとした理解ではなく、「ブルームフィルタの雰囲気を知って、利用価値をなんとなく判断できる」ところです。 今回は、以下の知識を前提にしているので、そこはご了承く
線分集合の交点列挙： Bentley-Ottmann のやり方
今回は、線分集合の交点列挙について Bentley-Ottmann のやり方を調べたので、そのメモです。よろしくお願いします。 現在、気が向いたときに平面性テストのデバッグをしているのですけど、ある平面描画に対して、辺対の交差チェックができたら良いなぁって思っていました。そもそも、いまのところ、ちっちゃいグラフが対象なので、\(O(n^2)\) で良いし、無理する必要なかったのですけど、軽い気持ちで Bentley-Ottmann のやり方に着手してしまいました。 まだ、きちんとテストしきれてないので、バグバグだと思いますけど、際どい境界条件とかじゃない限り動いていそうなので「モウイヤニナッタヨ」で切り上げました。よろしくお願いします。 python コード 今回のもやっぱり未完成で暫定的なものですけど、github に置きました。参考になるとは思いませんけど、もし腹が立ったら、ごめんあそ
組合せ最適化における最先端アルゴリズムと機械学習
30分程度の動画なので夕食を見ながら食べるのに最適です。 ================================================ Vertex Coverと巡回セールスマン問題はどちらも非常に研究の歴史が長いNP-hard問題です。 これらの問題には多項式時間アルゴリズムが存在しないと考えられているにも関わらず、最先端のソルバは数万頂点のインスタンスにさえ、厳密解を与えることがあります。 それとは別に、近年、機械学習によってこうした離散最適化問題を解こうとする試みが生まれています。機械学習によるアプローチの難しさはどうしたところから生まれるのかを皆さんにも考えていただきたいです。
xoshiro/xoroshiro generators and the PRNG shootout
Introduction This page describes some new pseudorandom number generators (PRNGs) we (David Blackman and I) have been working on recently, and a shootout comparing them with other generators. Details about the generators can be found in our paper. Information about my previous xorshift-based generators can be found here, but they have been entirely superseded by the new ones, which are faster and b
Dinic法について - TAISA_'s blog
理解にかなり手間取った&面白かったのでメモ。 アルゴリズム やっていることは、「長さが短い順に増加路を使っていく」というだけ。 以下、頂点数 、辺数 、始点 、終点 のネットワークを考える。 残余グラフを構築しておく。 増加路がなくなるまで、以下を繰り返す。この一回の繰り返しを「1ステップ」とする。 BFSで、「容量正の辺のみを使った時の、 から までの最短路長」 を求める。 長さ の増加路がなくなるまで、DFSで増加路を選び、フローを増やす。 なる辺 以外はないものとして扱えば、増加路は全て長さ になる。 DFSの際には、「その辺を使ったフローがこれ以上流せない」状態になった辺を記録し、以降の探索では無視するようにする。つまり、その辺を使おうとしたが、 に辿り着けなかった時と、容量が0になった時、辺は死ぬ。 なお、辺が死んでも1回のステップが終わったら復活する。 計算量(一般のグラフの場
量子フーリエ変換を「位相差に情報を埋め込む」という視点で理解してみる - めもめも
enakai00.hatenablog.com 何の話かと言うと 上記の記事で説明した量子フーリエ変換は、本質的には、 --- (1) という線形変換（ユニタリ変換）を量子回路で実装しただけのことですが、「なぜ (1) の表式が量子回路と相性がよいのか？」という部分を踏み込んで考えてみます。 位相差情報の抽出機としての（逆）フーリエ変換 もともとの話の流れでは、数学的に知られていたフーリエ変換 を量子ビットで表現したら、なんとも不思議な (1) の表式が得られた・・・・という事になりますが、実は、(1) はアダマール変換 の自然な拡張と見なすことができます。 どいういうことかと言うと、容易に分かるように、アダマール変換 は次のように表すことができます。 これは、1量子ビットの生の値を同じ量子ビットの位相差に変換する。つまり、位相差に情報を埋め込む演算とみなすことができます。 実は (1)
Rolling Hashについて（survey + 研究） | maspyのHP
新しい数値設定や実装方法を提案するものではありません。 衝突確率の下からの評価に対して、見たことがない考察を行ったので、記しておきます。 前提知識 本記事では簡単のため、アルファベットの集合を $\Sigma = \{0,1,\ldots,\sigma-1\}$ とします。英子文字であれば、ASCII コードによりアルファベットを $128$ 未満の整数に対応させたり、それをずらして $26$ 未満の整数に対応させることで、アルファベットを整数と見なせます。 Rolling Hash とは Rolling Hash は、文字列 $S = S_0,S_1,S_2,\ldots$ を次のようにHash化する手法です： 【Rolling Hash】 法 $m$, 基数 $r$ を何らかの方法でとる。 文字列 $S = S_0,S_1,S_2,\ldots$ の Hash値 を$\mathrm{h
【全方位木DP】明日使える便利な木構造のアルゴリズム - Qiita
この記事について この記事では、一部で全方位木DP、Rerooting等と呼ばれているアルゴリズムの紹介/解説と、その実装についての簡単な説明を行います。 全方位木DPなどと物騒そうな名前がついていますが、発想自体は全く難しくありません。また、実装もそこまで難しいものではないです。 前提知識として、最低限のグラフ理論の知識(特に木構造について)を要求します。(有向木の根/部分木等…) 謝辞 この記事中に挿入されている図は、殆どを @259_Momone さんに提供して頂きました。素晴らしく美しい図を提供して頂き、この記事を分かりやすいものとして頂いたことに感謝いたします。 全方位木DPとは 各点から深さ優先探索を行って解くことができる問題のうち特定の条件(後述)を満たすものについて、全頂点についての答えを同等の計算量で求めることができるアルゴリズムです。 まず、全方位木DPで解くことができ
文系でもプログラミングはできる。実技コンテストを主宰する社長に聞いた | bizSPA!
IT技術の発展に伴いIT人材（システムエンジニアやプログラマーなど）の需要が年々高まっているのにもかかわらず、IT人材不足が深刻だ。経済産業省によれば、2030年には実に45万人ものIT人材が不足するとの試算が出されている。 世界的に見れば、米国のGAFA（Google、Apple、Facebook、Amazon）や中国のBATH（Baidu、Alibaba、Tencent、Huawei）などの世界経済を牽引するIT企業を中心に、人材獲得が激化している状況だ。 いかにIT人材を確保するかが、日本の産業活性化に繋がると言っても過言ではない。そんななか、プログラミングスキルをコンテスト形式で評価する「競技プログラミング」の存在が注目を集めている。 今回は、世界3大競技プログラミングコンテストのひとつである「AtCoder」を運営し、数々の競技プログラミングコンテントで優勝経験を誇る、AtCod
Go Conference 2019 Autumn に登壇しました | フューチャー技術ブログ
こんにちは。TIG DXチーム 2の辻です。 先日開催された Go Conference 2019 Autumn に参加/登壇したので、その内容をレポートします。 The Gopher character is based on the Go mascot designed by Renée French. きっかけマネージャーとの面談で、勉強会やカンファレンスで登壇して貢献していきたいと話していたところ Go Conference 2019 Autumn の CfP を募集を見かけたので応募しました。 アイデアの種Go の goroutine や channel を用いることで並行処理をシンプルに書くことができます。基本的な計算をマルチスレッドで高速化する試みは、私が Qiita に書いた Golangを用いた様々な計算の高速化 の記事が詳しいです。 もちろん同じアルゴリズムを用いて G
熨斗袋 on Twitter: "高速なハッシュテーブルを設計する | POSTD https://t.co/QdhusBEp6k @POSTDccより これ、読み物としてかなり面白かった 特に設計の方針が"
高速なハッシュテーブルを設計する | POSTD https://t.co/QdhusBEp6k @POSTDccより これ、読み物としてかなり面白かった 特に設計の方針が
【競技プログラミング】ダイクストラ法の計算量はなぜO(E)なのか
この記事の目的ダイクストラ法の計算量は、O(ElogV)である。 仮に、エッジの長さが0か1ならばO(E)、つまりエッジの数に比例することになる。 「どうしてそうなるのか全く理解出来ない」と誰でも思うだろう。 優先度キューを使ってBFSで探索していけば、毎回エッジの分だけ分岐があるんだから なんらかの計算量はその分岐がどんどん積み重なっていき、 指数オーダーになってしかるべきだろう。 ふつうの人はそう考える。 どういうメカニズムで探索が省略されているのかなんとなく木を書き出して考えてみても、 なんとなくわかった気になったあとでやっぱりわからんとなる。 それが、ダイクストラ法を題材にしたちょっとした応用問題が出た時に手も足も出なくなる原因である。 グラフがぽいっと渡されて、はいs-t最短距離を計算してくださいと言われたら、 準備していたライブラリに食わせて終わりだが、 よく考えるとグラフ探索
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
ꑄ꒖ꐇꌅꏂ🐾 on Twitter: "なんかニコニコ大百科にマルコフアルゴリズムの記事が出来たらしく、読んでみたらめちゃ秀逸だった。ありがとうございます。 https://t.co/6A1hkN9AYT #MarkovAO"
GitHub - Reputeless/Xoshiro-cpp: Header-only Xoshiro/Xoroshiro PRNG wrapper library for modern C++ (C++17/C++20)
Ryo Suzuki on Twitter: "疑似乱数生成器 Xorshift の現代版、「Xoshiro」シリーズの C++ ラッパーライブラリのプロジェクトを公開しました。C++20 の標準乱数生成インタフェースに対応、ゲーム開発や研究プロジェクトに便利です (MIT ラ… https://t.co/JqzFiwvvVy"
講談社サイエンティフィク on Twitter: "＼50周年！／『データサイエンス入門シリーズ』新刊2冊を抽選で3名に同時プレゼント。応募締切4/21(火) 23:59 『モンテカルロ統計計算』 https://t.co/gpURfqNqME 『データサイエンスのためのデータベ… https://t.co/NGXLQeSRT0"
piqcy on Twitter: "言語モデルで実際文を生成するときに必要なDecodingについて、各種手法とTransformernによる実装を紹介している記事。単純に一番確率が高い単語をとっていくGreedy Searchから代表的なBeam Searchなど… https://t.co/faETArJFzQ"
Java Compare and Swap Example - CAS Algorithm