[IR] Google WSDM'09講演で述べられている符号化方式を実装してみた - tsubosakaの日記
MG勉強会の後にid:sleepy_yoshiさんに教えてもらったWSDM 2009における講演"Challenges in Building Large-Scale Information Retrieval Systems"で述べられている符号化方式のGroup Varint Encodingを実装してみた。 資料 講演スライド スライドの日本語による解説記事 整数の符号化方式 転置インデックスなどで文章番号のリストを前の値との差分で表すなどの方法を用いると出現する、ほとんどの値は小さな値となるためこれを4バイト使って表現するのは記憶容量の無駄である。 このためVarint Encoding、ガンマ符号、デルタ符号、Rice Coding、Simple 9、pForDeltaなど様々な符号化方式が提案されている。このうちVarint Encodingは実装が手軽なことからよく用いられて
![[IR] Google WSDM'09講演で述べられている符号化方式を実装してみた - tsubosakaの日記](https://cdn-ak-scissors.b.st-hatena.com/image/square/d5a026a6225c4524c834d0237efa271b5b0d54f0/height=288;version=1;width=512/https%3A%2F%2Fogimage.blog.st-hatena.com%2F17680117127124028144%2F17680117127124030436%2F1557332443)
Piotr Indyk
I am a Thomas D. and Virginia W. Cabot Professor in the Department of Electrical Engineering and Computer Science. I am a co-director of Foundations of Data Science Institute (FODSI). I am also a member of Theory of Computation Group in Computer Science and Artificial Intelligence Lab, Wireless@MIT, Big Data@CSAIL and Mifods. Short bio (on wiki). Code: FALCONN - fast algorithm for similarity searc
ナイーブベイズによるテキスト分類体験アプリ - シリコンの谷のゾンビ
もともとは研究室の新入生にNaive Bayesのイメージをつけるためにつくったもの．Naive Bayesを世の中に広めるために，きちんと公開することにしました． Text classification by Naive Bayes (2008-09-11追記）好評だったので日本語を扱えるようにしました．詳しくはこちらの日記をご覧ください． Text classification by Naive Bayes ver.2 日本語はじめました Naive Bayesナニソレ？という方はとりあえずググりましょう．理屈はわかったけれど，うまくイメージがつかないなぁ．．という状態になったら本プログラムを触ってみてください．すっきりします．たぶん． 使い方の説明 単語区切りが面倒なので日本語は使えません．あしからず． 本文を入れるっぽいところにテキストを入力します． クラスを選択して学習ボタンを押
はてなグループの終了日を2020年1月31日(金)に決定しました - はてなの告知
はてなグループの終了日を2020年1月31日(金)に決定しました 以下のエントリの通り、今年末を目処にはてなグループを終了予定である旨をお知らせしておりました。 2019年末を目処に、はてなグループの提供を終了する予定です - はてなグループ日記 このたび、正式に終了日を決定いたしましたので、以下の通りご確認ください。 終了日: 2020年1月31日(金) エクスポート希望申請期限:2020年1月31日(金) 終了日以降は、はてなグループの閲覧および投稿は行えません。日記のエクスポートが必要な方は以下の記事にしたがって手続きをしてください。 はてなグループに投稿された日記データのエクスポートについて - はてなグループ日記 ご利用のみなさまにはご迷惑をおかけいたしますが、どうぞよろしくお願いいたします。 2020-06-25 追記 はてなグループ日記のエクスポートデータは2020年2月28
1日で作る全文検索エンジン - Building a full-text search engine in "ONE" day - - とあるはてな社員の日記
最近、「Introduction to Information Retrieval」というStanfordの大学院向け教科書のドラフトを読んでいます。id:naoyaあたりが勉強会で読んでいる教科書です。この教科書には、効率のいい全文検索システムを作るにはどうすればいいか、という(まさに)教科書的手法が網羅的に書いてあり、そのあたりに興味がある人には、非常に興味深く読めるお勧めの本です。 ただ、面白い面白いと言っているだけでは、エンジニアとしては価値半減ですので、GW中にrubyで一日かけて実装してみました。 さすがに実装は、一日で作ったものですから、非常に素朴です。マルチバイト文字はbi-gramで、シングルバイトはスペースなどの区切り記号で認識しています。インデックスは、rubyの処理系のHashやArrayで保持しており、外部にMarshallで書き出す、というものです。検索エンジン
Bernard Chazelle's Home Page
Eugene Higgins Professor of Computer Science Princeton University Unlike music, scientific work does not come with liner notes. Perhaps it should. I work in Algorithms, a field believed by many to hold the promise of a scientific revolution. If you are a believer, no need to click here. My current interests are in the area of natural algorithms. My wife Celia is a professor of medieval history at
特定領域 > 研究成果報告 > 列挙学校
資料 ``列挙の基本と基礎的なアルゴリズム'' 岡本 吉央 (東京工業大学) [ Slides PDF (5.3 MB) ] / [ Handout PDF (1.8 MB) ] / [ Exercises PDF (46 KB) ] C プログラム等 (岡本さんの列挙のページ) ``グラフ列挙の手法'' 中野 眞一 (群馬大学) [ Powerpoint (568 KB) ] ``パターンマイニングにおける列挙アルゴリズム'' 有村 博紀 (北海道大学) [ PDF (1.2 MB) ] ``複雑な構造の簡潔な列挙法と実装法'' 宇野 毅明 (情報学研究所) [ Powerpoint (2.0 MB) ] © The Copyrights for the PowerPoint / PDF files are owned by their authors.
列挙学校に行ってきました。 - DO++
2/28, 2/29に三浦で開かれた列挙学校に行ってきました。 公式ページに発表スライドがアップロードされています。すばらしい！[link] 列挙問題とは「与えられた条件を満たすものを漏れなく，重複なく出力する問題」で、これを時間、スペース的に効率良く列挙するのが目的になります。この列挙問題は、それ自体問題として面白いですが、実用的にもデータマイニングや機械学習、情報検索（のインデクス作成）、など多くの分野で重要となってきています。 例えば、全ての順序付き木を漏れなく、重複なく列挙するという問題については、単純にやろうと思うと、適当に木を伸ばしていって過去に作ったものと重複していないかチェックしていってというふうにやることが考えられますが、これは時間、スペースともに非常に非効率です。 この順序付き木の列挙問題については最右拡張という方法が知られています。これは、ルートのみの木からはじめて、
Topcoder
Topcoder is a crowdsourcing marketplace that connects businesses with hard-to-find expertise. The Topcoder Community includes more than one million of the world’s top designers, developers, data scientists, and algorithmists. Global enterprises and startups alike use Topcoder to accelerate innovation, solve challenging problems, and tap into specialized skills on demand.
Gap buffer - Wikipedia
This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Gap buffer" – news · newspapers · books · scholar · JSTOR (April 2012) (Learn how and when to remove this message) A gap buffer in computer science is a dynamic array that allows efficient insertion and
HTMLのドキュメントから繰り返し部分をみつける - bits and bytes
RSSを生成していないページからRSSを生成するなんでもRSS 0.1bは、公開されているJSAI2005: なんでもRSS - HTML文書からのRSS自動生成によると、日付情報を目印にしてそのHTMLドキュメントの構造を推測して、各エントリ(item要素)のタイトルと本文を単語の統計的に処理して決定し、フィードを生成していると書かれています。 ウェブ上にあるHTMLドキュメントは Ask.jp ： "xml" Search results. のように、RSSのitem要素に相当する部分に日付が含まれていないものもあります。 その中でも、大量のデータを複数のページにわけて表示しているHTMLドキュメントを対象に、ドキュメント中に含まれる繰り返し部分のXPathを生成するブログラムをjavascriptで作りました。 アプローチ 大量のデータを複数のページわけて表示しているドキュメントを
Bigtable: A Distributed Storage System for Structured Data - steps to phantasien t(2006-09-11)
2006-09-11 近況 今月は貧乏なので慎しく暮らしている. 週末もひきこもりとしてオンラインの記事を読んで過ごすことに. ウェブを眺めているといいタイミングで Google の新作論文が出ていた. ありがとう, Google の中の人. これ. GFS, MapReduce, Sawzall とつづく Google インフラ N 部作の 4 章が幕をあげた. 実はデータベースも作ってるんだぜ, という話. BigTable という名前だけは以前から O'Reilly Radar などに登場していた. ようやく公式な文書があらわれた. BigTable は GFS をはじめとする Google インフラの上に作られた分散データベース. 少し変わったデータモデルと, 運用までワンセットのヘビーな実装を持つ. 実装の話もまあ面白いんだけれど, それよりデータモデルが印象的だった. 先にその
GC - GCアルゴリズム詳細解説 - livedoor Wiki（ウィキ）
GCアルゴリズム詳細解説 日本語の資料がすくないGCアルゴリズムについて詳細に解説します トップページページ一覧メンバー編集 × GC 最終更新： author_nari 2010年03月14日(日) 20:47:11履歴 Tweet このWikiが目指す所 GCとは？ GCを学ぶ前に知っておく事 実行時メモリ構造 基本アルゴリズム編 Reference Counter Mark&Sweep Copying 応用アルゴリズム編 IncrementalGC 世代別GC スナップショット型GC LazySweep TwoFinger Lisp2 Partial Mark and Sweep -Cycle Collection- Mostly Parallel GC train gc MostlyCopyingGC(Bartlett 1989) TreadmillGC(Barker 1992)
ConsistentHashing - コンシステント・ハッシュ法
ConsistentHashing - コンシステント・ハッシュ法 目次 この文書について コンシステント・ハッシュ法 実例 実装 用途 コンシステント・ハッシュ法 この文書について "Tom White's Blog: Consistent Hashing" の日本語訳です. http://weblogs.java.net/blog/tomwhite/archive/2007/11/consistent_hash.html 推敲歓迎: 誤訳, タイポ, 訳語の不統一, そのほか... 原文のライセンス: http://creativecommons.org/licenses/by-nc-sa/2.0/ 私は今までに何度かコンシステント・ハッシュ法にとりくんだことがある。 このアイデアをあらわした論文 ( David Karger らによる Consistent Hashing and R
Rajeev Motwani
Former Professor and Director of Graduate Studies Database Group/InfoLab, and Foundations Group Computer Science Department Stanford University Ph.D. 1988 (Computer Science, U.C. Berkeley) B.Tech. 1983 (Computer Science, IIT Kanpur) Research Interests: Databases, data mining, information retrieval, and web searching. Privacy and security, particularly in the context of databases and information re
アルゴリズム設計 講義資料 2005
Algorithm Design Course Materials 2013 Oct 7: Introduction and Computational Complexity Oct 15: Search Trees Oct 21: Combinatorial Optimization Oct 28: Heuristic Search Nov 5: Text Search Nov 11: Data Compression Nov 18: Memory Management Nov 25: Graph Algorithms 1/2 Dec 2: Graph Algorithms 2/2 Dec 9: Computational Geometry Dec 16: Concurrency Control Jan 15: Canceled Jan 20: Clustering Course Pro
Google Research Publication: The Chubby Lock Service for Loosely-Coupled Distributed Systems
The Chubby Lock Service for Loosely-Coupled Distributed Systems Mike Burrows Abstract We describe our experiences with the Chubby lock service, which is intended to provide coarse-grained locking as well as reliable (though low-volume) storage for a loosely-coupled distributed system. Chubby provides an interface much like a distributed file system with advisory locks, but the design emphasis is
Masami Hagiya
情報理工学系研究科の萩谷です。 質問など、何でも is-komaba at lyon.is.s.u-tokyo.ac.jp へ！ 投票クライアント: クリックしてダウンロードしてください。 次のようにしてrubyコマンドとともに使います。 $ ruby c.rb 選択肢番号 選択肢番号は1～9に限ります。 irbなどで練習中にも投票してもらうことがありますので、 投票用にターミナルを開いておくことを勧めます。 一つの端末から何回も投票した場合、最終の投票のみ有効です。 出席点は投票数で測ります。(各週の投票回数の逆数で各投票を重み付けします。) 成績 = 1/2試験 + 3/10レポート + 2/10出席 情報科学 共通資料 授業計画: 第1章 数の計算と関数 スライド 10/19は休講でした。 第1章 復習 + 第2章 配列による画像の表示 + 第3章 条件分岐と繰り返し スライド 第1
Splay Tree Demo
A demonstration of top-down splaying Splay trees, or self-adjusting search trees are a simple and efficient data structure for storing an ordered set. The data structure consists of a binary tree, with no additional fields. It allows searching, insertion, deletion, deletemin, deletemax, splitting, joining, and many other operations, all with amortized logarithmic performance. Since the trees adapt
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Algorithms by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani