Bloom filter の気持ち - アスペ日記
Bloom filter について書いてみる。 実装例についてはBloom filterのシンプルな実装 - 西尾泰和のはてなダイアリー等があるので、ここでは「気持ち」中心に。 前提:ハッシュ関数と key-value store の知識 注意:途中、説明のために実際の Bloom filter とは違う実装を導入している。 次の 4点はお互いに関連しているため、適当に混ぜながら書く。 1. Bloom filter でできることはどういうことか 2. Bloom filter はどのように実装されているのか 3. Bloom filter はどのような計算量的特性を持っているか 4. Bloom filter を使うと、どういう時にうれしいか まず、「Bloom filter でできることはどういうことか」について、key-value store (KVS) , set との違いという観
Log-structured merge-tree - Wikipedia
In computer science, the log-structured merge-tree (also known as LSM tree, or LSMT[1]) is a data structure with performance characteristics that make it attractive for providing indexed access to files with high insert volume, such as transactional log data. LSM trees, like other search trees, maintain key-value pairs. LSM trees maintain data in two or more separate structures, each of which is o
Paxosアルゴリズム覚え書き – OpenGroove
分散システムとともに語られることが多いPaxosアルゴリズムについて、触りだけでもまとめておこうかと。 もともとは、以下の記事からPaxosという用語を知ったのがきっかけ。Hadoop NameNode QJM HAの実装でそのアルゴリズムが使われている。 CDH4.1におけるクォーラムベースジャーナリング ちなみに、Hadoop NameNode QJM HAの実装に必要なJournalNodeはPaxosを使っているが、ZooKeeperはPaxosじゃなくてZAB（ZooKeeper Atomic Broadcast）である、ってのがちょっとややこしい。 以下覚え書き。 Paxosの由来は、ギリシャのPaxos島で行われていたとされる議会の逸話 Google Chubbyで有名になった Google App Engineのデータストアでも途中からPaxosを採用（参考） ZooKee
Paxosアルゴリズム - Wikipedia
Paxosとは信頼性が低いプロセッサのネットワークにおいて合意の問題を解決するためのプロトコルの集合である。 合意とは参加者のグループにおいて単一の結果について合意を得るプロセスである。参加者や通信手法に障害が起きる可能性がある場合、この問題は困難なものとなる[1]。 合意プロトコルは分散コンピューティングにおける状態機械アプローチの基礎であり、これはレスリー・ランポート[2]により提案され、Fred Schneiderによってサーベイがなされている[3]。 Paxosプロトコルは1990年に登場し命名されたが、論文として出版されたのは1998年であった[4]。 これ以前に、ナンシー・リンチ、Cynthia Dwork、Larry Stockmeyerは"部分同期"システムの広い範囲における合意形成方法を例証している。Paxosは分散トランザクションの文脈において、1988年にOkiとBa
Tree Edit Distanceアルゴリズムの応用と実装 - アドファイブ日記（ミラー版）
今日はアドファイブの製品開発の中身について少し。 背景(実装を早く見たい方はここはスキップして次節へ) バナー広告に代わる広告フォーマットとしてネイティブ広告というのが欧米を中心に盛り上がっています。TwitterやFacebookのフィードに紛れ込んでくる広告もネイティブ広告の一種と言われています。 ネイティブ広告特有の技術として、サイトのデザインに自動的にフィットさせる技術を開発する必要があります。 例えば、このNativoというネイティブ広告プラットフォームベンダはWebサイトを自動的に解析してネイティブ広告をプレビューできるという技術を持っています。手動で色々とインタラクティブにデザインの定義や設定をするUIでも良いのですが、やはりNativo社のような自動化エンジンを開発したくなります。 TwitterやFacebookのフィード広告のように、ネイティブ広告の代表例は「フィード型
Tree Edit Distanceと自然言語処理への応用 - Preferred Networks Research & Development
海野です。ちょっと時間があいてしまいましたが、昨年の12月に開催されたNTCIR-9という会議のRecognizing Inference in TExt (RITE)というタスクに、前職の方々と共著で出場しました。 Syntactic Difference Based Approach for NTCIR-9 RITE Task. Yuta Tsuboi, Hiroshi Kanayama, Masaki Ohno and Yuya Unno. NTCIR-9, 2011. [pdf] 含意関係認識といわれるこのタスクは、大雑把に言うと与えられた2つの文が同じ意味のことを言っているかどうか判定しなさいというタスクです（厳密には一方からもう一方が帰結できるかの判定です）。今日は、その中で使ったTree Edit Distance (TED) について解説します。 TEDは2つの順序付き木が
Diff algorithm - 枕を欹てて聴く
id:smoking186 さんの指摘を受け, First Authorの名前などを付加しました. どうもです. 記事内のcodeは最適化などを施しておらず, 冗長に, 定義どおりに書いています. ifがまとめられたりとかしますが, そのあたりはご容赦を... Rubyでlevenshtein距離を見て以来, 個人的にdiffブームが来ていた. 計算量O(ND) / O(NP)のalgorithmなどがあるのは知っていたが, 論文(英語)および, 解説のみ, またはソースコードのみなど分かれているものが多く, algorithmに疎い自分には理解するのに大変時間がかかってしまった. しかしやっとわかったので, 解説+JS実装してみる. 解説とソースコードがセットだと, 多少はわかりやすくなるかと... 自分は正直これくらい細かく言われないとすぐにはわかんない人なので(the O(ND)だけ
映画｢Algorithm｣は内容も収益モデルもハッカー流
無料からスタートしてうまくいったら有料化。 新しい映画｢Algorithm｣（アルゴリズム）は、フリーランスのハッカーが政府機密を扱うシステム会社に侵入し、彼らが最近開発したプログラムをすべてダウンロードするという内容です。そんなテーマにふわさしく、この映画のビジネスモデルも今どきのテクノロジー業界の動向を反映しています。まず無料で公開し、あとから有料にするんです。 ｢Algorithm｣はまず、日本時間7月14日午前7時1分から24時間、Vimeo上で公開されました。現在公式には公開終了していますが、こちらでは引き続き視聴可能です。 今後8月1日（米国太平洋時間）にはストリーミングとダウンロードで本格公開されます。そこでもし需要があると判断されれば映画館での上映となります。なので現時点での収益源は視聴者からの寄付のみとなっています。 このビジネスモデルのベースとなっているのは書籍｢リーン
1.uematsu.indd
解 説 論 文 8 Fundamentals Review Vol.1 No.1 1．シャノン理論とは何か シャノン理論とは，97 年に亡くなられたベル研究所の Wyner博士の造語であり，何らかの符号化問題の限界とその 限界を達成するアルゴリズムあるいは符号化法を追求する理 論体系の総称である．情報源の可逆圧縮における平均符号長 の限界（情報源のエントロピー）を求めることや，通信路符号 化問題における任意に小さい誤り率を達成できる伝送速度の 限界（通信路容量）を求めることなどがその代表的な例であ る．しかしながら，このような符号化のしきい値を求めるこ とだけが，シャノン理論の問題ではない．情報源符号化定理 や通信路符号化定理の精密化もまたシャノン理論の問題であ る．例えば情報源符号化では，1入力記号当りの平均符号長 がエントロピーよりも以上長い符号語が得られる確率（オー
Blog - 機械学習の「朱鷺の杜Wiki」
機械学習関連ブログ・ニュース・ポータル† 情報論的学習理論，機械学習，データマイニングなどの研究について研究者・学生が書いているブログやWikiについてリンクして下さい． ID は ibis でパスワードは VC 次元の V のフルスペルです（頭だけ大文字） 関連分野のWiki・ポータルサイト† 日本語 Baysian Fun Site：初心者からディープなベイジアンまで 言語情報処理ポータル 長岡技科大自然言語処理研：自然言語処理用語集 アルゴリズム データベース：アルゴリズムの説明 + Javaアプレット OR事典Wiki：最適化などの用語集 SLP Wiki：音声言語処理・音響信号処理 音楽情報学wiki RjpWiki：統計ソフトRの日本語Wiki TeXWiki：日本語TeX 英語 Machine Learning News @ Googleグループ Data Mining Bl
異常行動検出入門 – 行動データ時系列のデータマイニング –
【論文読み会】Deep Clustering for Unsupervised Learning of Visual Features
BDD/ZDDを基盤とする 離散構造と演算処理系の最近の展開 Recent Topics on Discrete Structures and Algebraic Operations Based on BDDs/ZDDs 湊 真一 Shin-ichi MINATO アブストラクト 二分決定グラフ（BDD: Binary Decision Di
BDD/ZDDを基盤とする 離散構造と演算処理系の最近の展開 Recent Topics on Discrete Structures and Algebraic Operations Based on BDDs/ZDDs 湊 真一 Shin-ichi MINATO アブストラクト 二分決定グラフ（BDD: Binary Decision Diagram）は，論理関数を効率良く表現するデータ構造の一種であ る．BDD に関する処理技法は主に VLSI 設計技術の分野で 1990 年代に発展したものであるが，近年ではデータマイニング や知識発見の分野でも効果的に活用されるようになってきている．中でも，ゼロサプレス型 BDD（ZDD: Zero-suppressed BDD）と呼ばれる BDD の変化形は，データベース解析の多くの問題で見られるような「疎な組合せの集合」を扱う場合に 特に効果
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Paxos
edit distance algorithm in Haskell - performance tuning
http://www.umiacs.umd.edu/~jimmylin/MapReduce-book-final.pdf