Map Reduce 〜入門編：仕組みの理解とアルゴリズムデザイン〜
This document discusses using sliding windows to aggregate streaming data in MapReduce. It proposes buffering input tuples in mappers until a window is full, then emitting the aggregate. Combiners and reducers combine partial aggregates across windows. Window ranges are initialized and updated during merging to remove outdated data and handle late arrivals. This approach allows streaming aggregati
livedoor Techブログ : decision tree (決定木) でユーザエージェント判定器を作ってみる
アクセスログのユーザエージェント(UA)からブラウザを判別するのって，みんな何使ってますか？ 自分が作ったアクセス解析システムでは HTTP::BrowserDetect と HTTP::MobileAgent にそれぞれ独自パッチをあてたものを使っています。これらはルールベースの判定器なので，新しいブラウザや新種の bot が登場するたびに手作業でルールを追加し，パッチを作って配布するという作業が必要になります。 この更新作業が大変面倒くさくて対応が遅れがちになるので，「このUA文字列はこのブラウザですよ、という例を大量に与えたら、自分で勝手に判定ルールを学習してくれるようになったら便利なのになぁ」と思い，decision tree (決定木)を使ってみることを思い立ちました。 目標は， "Mozilla/5.0 (Windows; U; Windows NT 6.1; ja; rv:1
大規模グラフデータベースの類似度検索ソフトウェア(gWT:graph-indexing wavelet tree)を公開しました - Yasuo Tabeiの日記
昨日のブログで紹介した大規模グラフの類似度検索のC++による実装(gWT:graph-indexing wavelet tree*1 )を公開しました。googlecodeよりダウンロードすることができます。 初めに、gWTはgwt-buildによりグラフデータベースの索引付けを行います。以下にサンプルを示します。 ./gwt-build -iteration 2 ../dat/mutagen.gsp index この例では、mutagen.gspが入力のグラフデータベースファイルで、indexが索引の出力ファイルです。-iterationオプションでは、Weisfeiler-Lehman手続きのイテレーション回数を指定します。ここでは２回に指定しています。入力ファイルの形式は、各行がノードラベルまたはエッジラベルとノードとの接続関係を表現します。各行の意味は以下を参照してください。 "t
開発メモ: IndexDB: 転置インデックスのためのDB
大震災の時分に何だが、Kyoto Cabinetベースで検索エンジンの核となる転置インデックスを作るのに適したDBを実装したという話。 転置インデックスとappend操作 多くの検索エンジンの核となる転置インデックスとは、検索語に一致する表現がどこに出てきたかという位置情報のリストを保持するものであり、検索語をキーとして位置情報リストを値とする連想配列である（転置インデックスを使わない検索エンジンもあるが）。この位置情報リストをposting listとか呼んだりするらしい。転置インデックスにもいくつか流儀があり、検索語をどのように切り分けるかで単語（分かち書き）方式とか文字N-gram方式とか呼ばれるものがあったりするが、いずれにせよ、小さいキーと、非常にでかい値を保持する連想配列を作ることには変わりない。 で、素朴に転置インデックスを作ろうとすると、検索対象の文書を解析しながら、得られ
検索エンジンはいかにして動くのか？ 記事一覧 | gihyo.jp
運営元のロゴ Copyright © 2007-2024 All Rights Reserved by Gijutsu-Hyoron Co., Ltd. ページ内容の全部あるいは一部を無断で利用することを禁止します。個別にライセンスが設定されている記事等はそのライセンスに従います。
B木から要素を削除する方法を学ぼう（1/3）－ ＠IT
第6回 B木から要素を削除する方法を学ぼう はやしつとむ アナハイムテクノロジー株式会社 2009/7/16 オブジェクト指向によって、アルゴリズムは隠ぺいされていることが多くなった。しかし、「用意されていない処理」が求められたときに対応できるだろうか（編集部） 第5回「RDBMSで使われるB木を学ぼう」では、木構造の中でもメジャーなバランス木の一種であるB木（B-Tree）について解説しました。 前回はB木への要素の追加について説明しましたので、今回はB木からの要素の削除を取り上げたいと思います。 本論に入る前に、前回のおさらいとなりますが、B木がどのようなものであるかを確認しておきましょう。 B木はAVL木と同様なバランス木の一種です。B木は、節点に複数のキーを格納できます（これをバケットと呼びます）。そして、新しく追加されるキーは、それぞれのキーに対する大小によって子の節点へと振り分
B木 (B-tree)
□ 多レベル索引の一種 挿入や削除のタイミングで動的な再編成が効率良く可能． レベル数は層レコード数 に対して ですむ． □ B-tree よりも後述の B-tree の方が良く使われるが，原理の 理解は B-tree の方が理解しやすいので，先に説明する． 以下ではキー値に重複がないものと仮定する． 定義 8 (B木 (B-tree)) が正整数であるとする．次の B木 (a B-tree of degree ) の 各ノードは次のような情報を持つページで，以下に述べる条件を満たすものである (図 6.5, p112 参照．): はroot ノード以外では である． root ノードでは である． レコード のキー値を で表すとすると， である． レコードは最大で 個まで持てる． はページへのポインタである． (つまり部分木へのポインタである．) 中に現れる全てのレコード
B-Tree - アルゴリズム・イントロダクション 18章 - ninjinkun's diary
アルゴリズム・イントロダクション勉強会，B-Treeの章を担当しましたので，資料を公開いたします． Algorithm Introduction #18 B-Tree View more presentations from ninjinkun. B-Treeはデータ容量が主記憶に収まらないような場合に有効なデータ構造で，MySQLなどのDBや，最新のファイルシステムのインデックスとして用いられています．（MySQLはインデックス管理の方式を選択可能） 主に以下の利点があります． ノードの大きさをページサイズに最適化できる ページの読み込みがディスクアクセスに最適化される ページの読み込み数を木の高さhに抑えられる ディスクへのアクセス回数を抑えることができる id:naoyaのブログも参考になります． B木 - naoyaのはてなダイアリー 当日の発表はテンパってしまい，アレな感じになっ
コーディングに役立つ！ アルゴリズムの基本 － ＠IT
本連載ではアルゴリズムとデータ構造を学ぶ、または学び直すことで、プログラミングのスキルを深めていきます。アルゴリズムは学問として取り扱われることが多いですが、この連載では開発の現場に役立つスキルを身に付けることを目的とします。 機械学習／Deep Learningが気になる人も要注目、「アルゴリズム」の基本が学べる無料の電子書籍150ページ 人気連載まとめ読み！ ＠IT eBook（29） 人気過去連載を電子書籍化して無料ダウンロード提供する＠IT eBookシリーズ。第29弾では「コーディングに役立つ！アルゴリズムの基本」10回分を1冊のPDFとしてまとめた。アルゴリズムとは何か？ なぜ学ぶべきなのだろうか？
待ち行列に入門した - steps to phantasien(2008-08-12)
先週, 会社をさぼって システム性能評価と待ち行列理論 という講義を受けてきた. 待ち行列理論の入門講義で, 大学の学部でやるレベルの話らしい. 私は学部でも学部以外でも勉強したことがない話題だったので, とても興味深く聞いた. 受講後はすっかり盛り上り, 待ち行列で性能評価するぜ! という気分になったのだが, 実際は難しい. 性能評価一般の難しさはさておくとして, 待ち行列理論そのものがけっこう複雑. 数学が苦手な身には辛い. 理論の常として, 待ち行列の理論もまず解析対象の特性に様々な制限や前提を設けた上でモデルをたてる. そのモデルがうまく解析できたら, 少しずつ制限をとりはずしていく. 現実を扱えるモデルに至る道程は険しそうだ. 高価なツールを使えばそんな洗練されたモデルも扱えるのかもしれないけれど, もうちょっと庶民に優しい路線であってほしい. 解析に挫ける一方, 理論の成果が明
アルゴリズムの紹介
ここでは、プログラムなどでよく使用されるアルゴリズムについて紹介したいと思います。 元々は、自分の頭の中を整理することを目的にこのコーナーを開設してみたのですが、最近は継続させることを目的に新しいネタを探すようになってきました。まだまだ面白いテーマがいろいろと残っているので、気力の続く限りは更新していきたいと思います。 今までに紹介したテーマに関しても、新しい内容や変更したい箇所などがたくさんあるため、新規テーマと同時進行で修正作業も行なっています。 アルゴリズムのコーナーで紹介してきたサンプル・プログラムをいくつか公開しています。「ライン・ルーチン」「円弧描画」「ペイント・ルーチン」「グラフィック・パターンの処理」「多角形の塗りつぶし」を一つにまとめた GraphicLibrary と、「確率・統計」より「一般化線形モデル」までを一つにまとめた Statistics を現在は用意していま
「1000のアルゴリズムを持つ男」vs.「やわらか頭脳」
「1000のアルゴリズムを持つ男」vs.「やわらか頭脳」：最強最速アルゴリズマー養成講座（1/3 ページ） 典型的なアルゴリズムをたくさん知っている人間が最強か――？ いいえ、典型的なアルゴリズムを知らなくても、違ったアプローチで答えに迫る方法はいくらでも存在します。短い実行時間で正確な答えを導き出せるかを考える習慣をつけましょう。 アルゴリズマー養成講座と銘打ってスタートした本連載。もしかすると読者の方の興味は、はやりのアルゴリズムや汎用的なアルゴリズムを知ることにあるのかもしれません。しかし、今回は、いわゆる「典型的なアルゴリズム」を用いずに進めていきたいと思います。 なぜ典型的なアルゴリズムを用いないのか。それは、典型的なアルゴリズムばかりを先に覚え、それだけでTopCoderなどを戦っていこうとした場合、それに少しでもそぐわない問題が出た場合に、まったく太刀打ちできなくなってしまう
オーダーを極める思考法
プログラムの実行に掛かる時間を把握しておくのは、プログラミングを行う上で基本的な注意点です。今回は、計算量のオーダーについて学びながら、TopCoderのMedium問題を考えてみましょう。 プログラムの実行時間 業務としてプログラミングをされている方には釈迦に説法かもしれませんが、プログラムの実行に掛かる時間を把握しておくのは、プログラミングを行う上で基本的な注意点です。そしてこれは、TopCoderなどのコンテストでプログラムを組む際にもよく当てはまります。通常、こうしたことは感覚的に理解している方がほとんどだと思いますが、具体的にどれくらいのループを回すと何秒掛かる、といった基準を持っている人は少ないのではないでしょうか？ 非常に基本的なことですが、プログラムの実行時間に関して再確認しておきたいと思います。 TopCoderの制限に関して TopCoderでは、実行時間およびメモリ使
algorithm
奥村晴彦さんの「C言語による最新アルゴリズム事典」技術評論社、1991年、の C 言語プログラムの Ruby への翻訳に挑戦します。プログラムの説明は同書を読んでください。変換はできるだけ逐語的に行っています。プログラムの動作は原作の C プログラムのそれと比較してチェックしていますが、うまく動作しないときは C から Ruby への変換のさいに起きたものです。バグレポートは tnomura@mnet.ne.jp までお願いします。 この Ruby 翻訳版はできるだけレイアウトも含めて原作の C プログラムを変更しないようにしたため、必ずしもRuby らしいコーディングスタイルとは言えないかもしれませんが、プログラムがきちんと動作することを優先しました。C から Ruby への翻訳の著作権に関しては Ruby のライセンスに準じます。配布、改変は自由です。ただし、プログラム本体には原作者の
[を] 転置インデックスによる検索システムを作ってみよう！
転置インデックスによる検索システムを作ってみよう！ 2007-11-26-5 [Algorithm][Programming] 転置インデックス[2007-06-17-6]による検索システムの実装は パフォーマンスを無視すれば意外と簡単です。 それを示すために Perl で簡単な検索システムを作ってみました。 検索方式は転置インデックス(Inverted Index)、 ランキングには TF-IDF[2005-10-12-1] を用いました。 検索対象ファイルは一行一記事で以下のフォーマットとします。 [記事ID][SPC][記事内容]\n 記事IDは数字、記事内容は UTF-8 の文字で構成されるものとします。 以下のようなサンプル test.txt を用意しました。 1 これはペンです 2 最近はどうですか？ 3 ペンギン大好き 4 こんにちは。いかがおすごしですか？ 5 ここ最近疲れ
![[を] 転置インデックスによる検索システムを作ってみよう！](https://cdn-ak-scissors.b.st-hatena.com/image/square/af37977ee866988286b95e74fff98500a190545c/height=288;version=1;width=512/https%3A%2F%2Fchalow.net%2Fimages%2Ftcl-logo-25.png){kind=logo}
Regular Expression Matching Can Be Simple And Fast
Regular Expression Matching Can Be Simple And Fast (but is slow in Java, Perl, PHP, Python, Ruby, ...) Russ Cox rsc@swtch.com January 2007 Introduction This is a tale of two approaches to regular expression matching. One of them is in widespread use in the standard interpreters for many languages, including Perl. The other is used only in a few places, notably most implementations of awk and grep.
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Project Eulerに挑戦
Amazon.co.jp: ガベージコレクションのアルゴリズムと実装: 中村成洋 (著), 相川光 (著), 竹内郁雄 (監修), 竹内郁雄 (読み手): 本
カンガルーハウス：テキストライブラリ：2007年7月 A*（A-star：エースター）探索アルゴリズム
加藤 和彦 Kazuhiko KATO, Dr. Prof.
