Název:
Komprese bitových map pomocí Grayova kódu
Překlad názvu:
Gray code based bitmap compression
Autoři:
Škorvaga, David ; Dvořák, Tomáš (vedoucí práce) ; Gregor, Petr (oponent) Typ dokumentu: Bakalářské práce
Rok:
2011
Jazyk:
cze
Abstrakt: [cze][eng] Práce se zabývá kompresí bitmapových indexů. Ke zmenšení bitmapových indexů se často používají specializované algoritmy, které hledají dlouhé řetězce stejných bitů. Řádky indexu je pak výhodné vhodně přerozdělit, aby algoritmus poskytoval co nejlepší kompresní poměr. Nalezení optimálního přerozdělení je sice NP-těžký problém, existují však účinné heuristiky, které setřídí index v polynomiálním čase. V poslední době se objevily experimentální studie, které místo klasického lexikografického třídění využívají třídění podle Grayova kódu. V této práci nahrazujeme klasický Grayův kód novou konstrukcí, která generuje komprimovaný Grayův kód. Konstrukci podrobně popisujeme a na reálných i náhodně generovaných datech zkoumáme, zda je při kompresi algoritmem WAH tento kód účinnější než klasický.This thesis deals with a compression of bitmap indexes. Bitmap indexes may be reduced through specialized algorithms which look for long runs of identical bits. To improve the compression ratio, it is useful to reorder the rows of the index. Even though the problem of optimal reordering is NP-hard, there are efficient heuristics which reorder the index in polynominal time. Recent results suggest that Gray code based sorting provides an effective alternative to the classical lexicographical sorting. In this thesis, we replace the classical Gray code with a novel construction which generates a compressed Gray code. We describe this construction in detail and use both real-life and randomly generated datasets to test whether the novel construction is more efficient than the classical one when used in the WAH compression scheme.
Klíčová slova:
bitmapový index; Grayův kód; komprese; WAH; bitmap index; data compression; Gray code; WAH