Top-k文書列挙問題 - DO++
いろいろとありまして去年読んだ論文で面白かったものランキングとか書けなかったのが残念ですが、もしあげるとしたら次の論文は入れると思います（知ったのは年明けだったけど）。 "Space-Efficient Framework for Top-k String Retrieval Problems", FOCS 2009, Wing Kai Hon, Rahul Shah and Jeffrey Scott Vitter (pdf) 扱っているのは次のような問題です（説明のため本来のと言い換えています） n個の葉からなる木が入力として与えられ，各葉には色（1以上d以下の整数とします）が与えられています． この時、木中の任意の節点と正整数kがクエリとして与えられたときに、その節点の子孫の中で出現回数が大きい色を順にk個答えよという問題です。 簡単に思いつくのは，各節点に適当な個数(d)の答えをあ
vcdiff: Data Compression Using Long Common Strings | kzk's blog
Recently, I have a strong demand for storing many many HTML contents, downloaded from the web. But storing them in raw data seems not clever way. Of course, we need the efficient compression. One of the most famous data compression is gzip, which uses LZ77 algorithm. LZ77 finds the repeating substring in the small window, and replace the repeating strings into (offset, size) pair. Although HTML ha
[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)
References on Nearest Neighbors and Similarity Search
The Homepage of Nearest Neighbors and Similarity Search Maintained by Yury Lifshits Update: this page is frozen. Please visit the successor page by Arnoldo Muller I am now trying to sort all papers by topic. This work is in progress. Please email me all papers I missed so far. Subareas: Nearest neighbors in general metric space Branch and bound for Euclidean space Mapping-based techniques: localit
Vowpal Wabbit (Fast Learning)
This is a project started at Yahoo! Research and continuing at Microsoft Research to design a fast, scalable, useful learning algorithm. VW is the essence of speed in machine learning, able to learn from terafeature datasets with ease. Via parallel learning, it can exceed the throughput of any single machine network interface when doing linear learning, a first amongst learning algorithms. We prim
SODA2010 ALENEX2010＠テキサス - DO++
先日までTexas Austinで開催されていたALENEX2010とSODA2010に参加してきました。 一緒に行った吉田さんの感想もありますのでそれも参照してください まず一応自分のALENEXでの発表資料は以下にありますので参照ください "Conjunctive Filter: Conjunctive Filter: Breaking the Entropy Barrier"論文、発表スライド(pptx pdf) 他に聞いた中で印象的だったものを下に書いてみます。ただ、大部分の発表は私の基礎知識が足りなくてついていけませんでした。残念 昨年末の研究開発セミナーでも紹介しましたが、簡潔木とよばれる限界まで圧縮した上で（ノード数がnの時2n+o(n) bit）様々な木上での操作（親を辿る、子を辿る、共通祖先を探すなど）のあらゆる操作を統一された操作の組み合わせで実現するというものの理論的
Cerevo TechBlog - (株)Cerevoの中の人が書く、様々な技術情報を発信するBlog.
はじめに USBシリアル変換のICとしてすっかり定着したCP210xシリーズですが、Windowsで使う時にUSBハブ上の物理的な位置とCOM番号の関係を知りたいことはないでしょうか。 方法は簡単なのですがweb上であま […]
SIMD-oriented Fast Mersenne Twister (SFMT)
SIMD-oriented Fast Mersenne Twister (SFMT): twice faster than Mersenne Twister*1. English Version 最新情報 SFMT ver1.5.1 をリリースしました。(2017/2/22) SFMT ver1.5 をリリースしました。 53bit精度double出力にバグがありました。(2017/2/7) SFMT 論文の正誤表 を追加しました。(2015/9/1) dSFMT ver2.2.3 をリリースしました。(2013/12/19) SFMT ver1.4.1 をリリースしました。(2013/12/19) dSFMT ver2.2.2 をリリースしました。 ver2.2.2 はVisual C++ 2012 でコンパイルエラーになる部分を修正しました。 (2013/9/17) dSFMT ver
軽量データクラスタリングツールbayon - mixi engineer blog
逆転検事を先日クリアして、久しぶりに逆転裁判1〜3をやり直そうか迷い中のfujisawaです。シンプルなデータクラスタリングツールを作成しましたので、そのご紹介をさせていただきます。 クラスタリングとは クラスタリングとは、対象のデータ集合中で似ているもの同士をまとめて、いくつかのグループにデータ集合を分割することです。データマイニングや統計分析などでよく利用され、データ集合の傾向を調べたいときなどに役に立ちます。 例えば下図の例ですと、当初はデータがゴチャゴチャと混ざっていてよく分からなかったのですが、クラスタリングすることで、実際は3つのグループのデータのみから構成されていることが分かります。 様々なクラスタリング手法がこれまでに提案されていますが、有名なところではK-means法などが挙げられます。ここでは詳細については触れませんが、クラスタリングについてより詳しく知りたい方は以下の
Sign in - Google Accounts
Not your computer? Use a private browsing window to sign in. Learn more about using Guest mode
Burrows-Wheeler変換の線形時間アルゴリズム - DO++
研究紹介です。今夏のSPIRE 2009という学会で "A Linear-Time Burrows-Wheeler Transform using Induced Sorting", D. Okanohara, K. Sadakane, SPIRE 2009 pdf(draft) というのを発表します。これは与えられた文字列に対し接尾辞配列を経ないでBurrows-Wheeler変換を直接行うというもので、アルファベットサイズによらず入力長に対して線形時間で行えます。基本的なアイディアは昨年のInduced Sortingによる接尾辞配列の線形時間構築アルゴリズム（いわゆるSAIS）を接尾辞配列を使わないでシミュレートするものです。pushとpop操作だけからなり、そのまま外部記憶上での構築とかにも対応できるようになっています。 Burrows-Wheeler変換（BWT, Block S
CarpeDiem: Optimizing the Viterbi Algorithm and Applications to Supervised Sequential Learning
CarpeDiem: Optimizing the Viterbi Algorithm and Applications to Supervised Sequential Learning Roberto Esposito, Daniele P. Radicioni; 10(64):1851−1880, 2009. Abstract The growth of information available to learning systems and the increasing complexity of learning tasks determine the need for devising algorithms that scale well with respect to all learning parameters. In the context of supervised
MaximumCompression
In thе digital agе, whеrе data is both abundant and prеcious, thе sеcurity of our filеs is paramount. Comprеssion softwarе, which еnablеs us to rеducе thе sizе of filеs for storagе and transmission, plays a crucial rolе in our daily… File compression is а vitаl tool for mаnаging digitаl dаtа, enаbling us to reduce file sizes for storаge, trаnsmission, аnd аrchivаl purposes. However, аchieving opti
FrontPage - アルゴリズムとデータ構造入門 - Kyoto Univ.
アルゴリズムとデータ構造入門 TAのページ 京都大学 工学部 情報学科 1回生配当の授業 アルゴリズムとデータ構造入門（奥乃先生担当)のTAが管理するページです。 連絡 (2007/10/01) 2007年度用に更新。 (2006/10/31) Meadowの使い方を公開しました。 (2006/11/14) 改行コードで困っていた方が多かったので改行コードに関する設定についてまとめました。 (2006/10/27) 質問掲示板を移行 使い勝手が悪く、あまり評判もよくないので質問掲示板を移行しました。これからは新しい方に質問を書いてください。 (2006/10/13) cygwinとTUTSchemeのインストールの説明に間違いがあったので追加・修正しました。 このページの通りにインストールを行って、Can't find a usable init.tcl in the following
non-Negative Matrix Factorization (NMF) - naoyaのはてなダイアリー
以前に Latent Semantic Indexing (LSI) や HITS 絡みで SVD や主成分分析について少し書きました。 http://d.hatena.ne.jp/naoya/20090212/latent_semantic_indexing http://d.hatena.ne.jp/naoya/20090301/hits LSI では SVD を使って単語文書行列を分解し、低階数近似を行います。これにより、似たような次元をまとめたりといった効果が得られるのでした。自分の考察では HITS も同様のことを行っているという認識でした。 さて、集合知プログラミングを読んでいたら、第10章で "non-Negative Matrix Factorization" (非負値行列因子分解, 以下NMF) という手法が出てきました。NMF も SVD や主成分分析に同じく行列を分解
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
http://www.neurosci.aist.go.jp/~akaho/thesis/thesis-www/node16.html
Lawrence Cayton's former webpage
Google Code Archive - Long-term storage for Google Code Project Hosting.
http://feedblog.org/2008/10/12/google-bigtable-compression-zippy-and-bmdiff/
RX