Det är väl etablerat att bitmap index är effektiva för read-only attribut med ett litet antal olika värden. För ett attribut med ett stort antal olika värden kan bitmap-indexets storlek vara mycket stor. För att övervinna denna storlek problem, specialiserade komprimering system används. Även om det finns empiriska belägg för att vissa av dessa kompressionssystem fungerar bra, har det inte gjorts någon systematisk analys av deras effektivitet. I detta papper analyserar vi tids- och rymdkomplexiteterna hos de två mest effektiva bitmapkompressionsteknikerna kända, Byte-aligned Bitmap Code (BBC) och Word-Aligned Hybrid (WAH) kod, och studerar deras prestanda på höga kardinalitet attribut. Våra analyser visar att båda komprimeringssystemen är optimala i tid. Den tid och det utrymme som krävs för att arbeta på två komprimerade bitkartor står i proportion till den totala storleken på de två bitkartorna. Vi visar vidare att en på plats OR algoritm kan fungera på ett stort antal glesa bitmappar i tid linjär i sin totala storlek. Våra analyser visar också att de komprimerade indexen är relativt små jämfört med vanliga index som B-träd. Med tanke på dessa fakta, drar vi slutsatsen att bitmap index är effektiv på attribut av låga kardinaliteter samt på de av höga kardinaliteter. Vi verifierar också analysresultaten med omfattande tester och identifierar ett optimalt sätt att kombinera olika alternativ för att uppnå bästa prestanda. Testresultaten bekräftar linjäriteten i den totala storleken på de komprimerade bitkartorna och att WAH överträffar BBC med ungefär en faktor på två.
I värsta fall är svarstiden proportionell mot antalet träffar på frågan REF.
On the Performance of Bitmap Indices for High Cardinality Attributes
{'venue': 'VLDB', 'journal': None, 'mag_field_of_study': ['Computer Science']}