fcicqのブックマーク - はてなブックマーク

fcicq id:fcicq

ブックマーク / tsubosaka.hatenadiary.org (4)

Simple-9について解説 - tsubosakaの日記
前回に引き続き転置インデックスの圧縮を実装してみる。今回紹介するのは[2]で提案されているSimple-9というアルゴリズムである。 Simple-9は32bitのwordにできるだけ数字を詰めていくという圧縮アルゴリズムである。例えば2bitの数が16個ならんでいれば32bitで表現できる。しかし、実際は大きい数字も出現するため数字の長さの情報も格納する必要がある。Simple-9では4bitを用いて残りの28bitがどう詰められているかを表す。 28bitの表し方としては上位bit 符号の個数符号のビット長 0000 28 1 0001 14 2 0010 9 3 0011 7 4 0100 5 5 0101 4 7 0110 3 9 0111 2 14 1000 1 28 の9通りがあり、これがSimple-9の名前の由来となっている。例えば ( 3 , 5 , 0 , 0 ,
fcicq 2017/07/04
4+28

algorithms
リンク
Streaming k-means approximation - tsubosakaの日記
実家に帰省中，電車の中で読んでた論文の紹介。概要 k-meansはクラスタリングテクニックとして非常に基本的な手法である。しかし、k-meansでは全データに対してラベリングを複数回繰り返す必要があり、全データ点を保存する必要がある、そこでk-meansの出力であるk個のクラスタ中心をワンパスで見つける方法を提案する。ここで得られるクラスタ中心は最適値と比較したときにO(log k)の近似となっているストリームアルゴリズムについて本論文で言っているStreamingの意味としては入力を前から見ていって、すべて保存しないアルゴリズムのことを言っている。いわゆるオンラインアルゴリズムのように入力が入ってくるたびに何かしらの結果が得られるわけではない。また，ストリームの長さは有限である事を仮定している。 k-meansとは k-meansとはデータ点 X = {x_1 , ... x_
fcicq 2012/03/21
k-means# from NIPS2009, Streaming k-means approximation

algorithms

datamining
リンク
[IR] 転置インデックスとtop-k query - tsubosakaの日記
転置インデックスから上位k件の文章を取ってくる手法について、知ってる範囲でまとめてみました。転置インデックスとTop k-query View more presentations from tsubosaka この辺の話は教科書だと Information Retrieval: Implementing and Evaluating Search Engines (MIT Press) 作者: Stefan Buettcher,Charles L. A. Clarke,Gordon V. Cormack出版社/メーカー: The MIT Press発売日: 2010/07/23メディア: ハードカバー購入: 2人クリック: 78回この商品を含むブログ (8件) を見るのChapter 5とかに疑似コードなども含め載っているので、参考になるかと思います。
fcicq 2012/02/13
have read. ranking with inverted index.

search

ir

presentation
リンク
[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は実装が手軽なことからよく用いられて
fcicq 2011/01/27
Group Varint Encoding

algorithms

google
リンク
1