Daniel Lemire の投稿 The Mythical Bitmap Index ( http://lemire.me/blog/archives/2008/08/20/the-mythical-bitmap-index/ ) を読んでいて、その投稿で彼は次のように述べています。
ビットマップ インデックスの圧縮サイズは、多くてもテーブルのサイズに比例します。個別の値の数に関係なく!
彼がこの値をどのように計算したかを理解するのに苦労しています。
長さ N の Run-Length-Encoded テキストの最悪の場合のスペース使用量は、N (2N?) に比例するため、O(N) であることを私は知っています。
また、特定の列のビットマップ インデックスの数の最悪のケースは、列のカーディナリティが N の場合であり、N はテーブル内のレコードの数であることも知っています (したがって、すべてのレコードがその特定の列で一意の値を持つようになります)。 . これは、N 個のビットマップ インデックスがあることを意味します。
ただし、ビットマップ インデックスの最悪の場合の仮定の下では、各ビットマップ インデックスは、ランレングス エンコードされると、一定のスペース使用量になります。これは、いくつかのゼロ、1、それに続くいくつかのゼロ、つまり O(1) になるためです。
したがって、最高カーディナリティ N の下でのすべてのビットマップ インデックスの合計スペース使用量は、ちょうど N x O(1) = O(N) になります。
ただし、この特定の計算から、考えられるすべてのケースの最悪のケースにどのように進むのでしょうか? 私が説明したカーディナリティ = N のケースが、すべてのビットマップ インデックスを合計した最悪のケースのスペース使用量であることは明らかではありません。
テーブル内の列に対して、ランレングスでエンコードされたすべてのビットマップ インデックスを合計した場合の最悪の場合のスペース使用量をどのように計算しますか?