Search and analytics, data ingestion, and visualization – all at your fingertips.
Search and analytics, data ingestion, and visualization – all at your fingertips.
圧縮されたソート済の整数列ってのは汎用的なデータ構造で、たとえば検索エンジンの転置インデックスとか、いろんなところで使うわけです。で、検索エンジンの場合は速度重要なので、PForDeltaとか様々なデータ構造が研究されてる。 一方、H2O には、ブラウザキャッシュに載ってない js や css をサーバプッシュする仕組み「cache-aware server push」があって、何がキャッシュされているか判定するためにブルームフィルタを全ての HTTP リクエストに含める必要がある。 で、ブルームフィルタを圧縮しようと思うと、ブルームフィルタってのはソート済の整数列として表現できるので、これを圧縮しようって話になる。 検索エンジン等で使う場合は速度重要だけど、HTTPリクエストに載せる場合は空間効率のほうが重要になる。ってことで、空間効率が理論限界に近いゴロム符号（の特殊系であるライス符号
Efficient Data Storage for Analytics with Parquet 2.0 - Hadoop Summit 2014 Apache Parquet is an open-source columnar storage format for efficient data storage and analytics. It provides efficient compression and encoding techniques that enable fast scans and queries of large datasets. Parquet 2.0 improves on these efficiencies through techniques like delta encoding, dictionary encoding, run-length
Ville Tuulos Principal Engineer @ AdRoll ville.tuulos@adroll.com We faced the key technical challenge of modern Business Intelligence: How to query tens of billions of events interactively? Our solution, DeliRoll, is implemented in Python. Everyone knows that Python is SLOW. You can't handle big data with low latency in Python! Small Benchmark Data: 1.5 billion rows, 400 columns - 660GB. Smaller e
Compression encodings - Amazon Redshift
Amazon Redshift will no longer support the creation of new Python UDFs starting November 1, 2025. If you would like to use Python UDFs, create the UDFs prior to that date. Existing Python UDFs will continue to function as normal. For more information, see the blog post . Compression encodings A compression encoding specifies the type of compression that is applied to a column of data values as row
A simple integer compression library for C/C++/Java ================= Overview ----------- Released vpacker-0.1.0, which compresses a 32-bit or 64-bit integer array. It is assumed to encode a sequence of integers with highly positive skewness. The skewness is a distribution where the mass of the distribution is concentrated on the left, i.e., an element of the sequence is rarely a large integer. T
LinkedIn operates the world’s largest professional network with more than 645 million members in over 200 countries and territories. This team builds distributed systems that collect, manage and analyze this digital representation of the world's economy, while our AI experts, data scientists and researchers conduct applied research that fuel LinkedIn’s data-driven products and provide insights tha
通常の整数は 32 ビットは 4 バイトの固定長によるバイナリ符号ですが、小さな数字がたくさん出現し、大きな数字はほとんど出現しないという確率分布のもとでは無駄なビットが目立ちます。 Variable Byte Code (Byte Aligned 符号とも呼ばれます) は整数の符号化手法の一つで、この無駄を幾分解消します。詳しくは Introduction to Information Retrieval (以下 IIR) の第5章に掲載されています。(http://nlp.stanford.edu/IR-book/html/htmledition/variable-byte-codes-1.html で公開されています) Variable Byte Code はその名の通りバイトレベルの可変長符号で、1バイトの先頭1ビットを continuation ビットとして扱い、続く 7 ビット
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%2Fsiteproxy.ruqli.workers.dev%3A443%2Fhttps%2Fogimage.blog.st-hatena.com%2F17680117127124028144%2F17680117127124030436%2F1557332443)
はじめに 第2回で、索引は多くの場合圧縮されていることに言及しました。また第7回では、索引構築時にどの部分で索引を圧縮すればよいかを疑似コードを用いて説明しました。今回は、転置索引の具体的な圧縮方法について説明していきます。 圧縮の目的 中規模から大規模な索引の場合、転置リストは非常に長くなり、検索時にはディスクからの大量のデータの読み取りが行われます。転置索引（を用いた検索エンジン）では、これによる検索処理時間の増加を防ぐために、転置リストを圧縮しディスクからの読み込み時間の短縮を図ります。 この場合、圧縮された転置リストをディスクから読み込みさらに復元処理を行う必要がありますが、通常は次のようになります。 これは、近年のCPUとディスクの速度差が大きいため、主にCPUにおける処理である復元処理が高速に行えることによるものです。よって、圧縮というと容量を節約の意図で使うことが多いと思いま
前回に引き続き転置インデックスの圧縮を実装してみる。今回紹介するのは[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 ,
ちょうど二年ぐらい前，機械学習で疎ベクトルの圧縮に情報検索でよく使われる整数列の圧縮技術を使うことを検討したことがあった（オンライン学習でキャッシュを実装してみた - ny23の日記）．そのときは，オンラインで圧縮し Disk に保存，圧縮したベクトルは陽にメモリに置かず読む（OS に任せる）という実装で，（Disk IO のオーバーヘッドが大きく）圧縮さえすれば何を使っても大差なしという身も蓋もない結論になった（結局2行で書ける最も単純な Variable byte code を採用）． それ以降は整数列圧縮アルゴリズムに関する知識も NewPFD ぐらいで止まっていたのだけど，つい先日，現時点で最速の圧縮アルゴリズムの提案＋ここ数年の主な整数列圧縮アルゴリズム（Simple-8b (J. Software Pract. Exper. 2010), VSEncoding (CIKM 20
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
