0

私は、データ インデックス作成用のワード アライン ビットマップ圧縮アルゴリズムを開発しています。アルゴリズムは、WAH 圧縮研究論文に基づいています。しかし、圧縮されたビットマップを変更すると、圧縮されたワードサイズのブロックを分割する必要があり、いくつかの memmove がパフォーマンスのボトルネックを引き起こすため、あまり効率的ではありません。

次の例を見てください。

例: データセット - [1000000,34,9,23456,6543,10000000,23440004,100,345]

データセットのランダムな性質によりパフォーマンスが低下します。実際のアプリケーション シナリオでは、これが発生する可能性があります。

  1. このパフォーマンスの問題を克服する方法についてのヒントを教えてもらえますか?
4

1 に答える 1

1

Daniel Lemireは、圧縮とパフォーマンスを向上させるための事前ソートに関する論文を2つ持っています。最新情報は次のとおりです：http：//arxiv.org/abs/1207.2189

彼のEWahバリアントも見ることができます。

ほとんどの実装では、変更のたびにインデックスが破棄および再構築されるため、データセットの変更が遅い場合、ビットマップ配列の圧縮技術がうまく機能するというのが一般的な感覚です。より頻繁に変更されるデータセットの場合、従来のインデックスアプローチ（Bツリーバリアントなど）が依然として重要です。

実装：https ：//github.com/lemire/javaewahおよびhttps://github.com/lemire/EWAHBoolArray

于 2012-10-22T18:59:16.480 に答える