RadixZip Linear Time Compression of Token Streams ABSTRACT

RadixZip is a block compression technique for token streams. It introduces RadixZip Transform, a linear time algorithm that rearranges bytes using a technique inspired by radix sorting. For appropriate data, RadixZip Transform is analogous to the Burrows-W

RadixZip:LinearTimeCompressionofTokenStreams

BinhDaoVo

Google,USA

GurmeetSinghManku

Google,USA

binh@google.commanku@google.com

ABSTRACT

RadixZipisablockcompressiontechniquefortokenstreams.ItintroducesRadixZipTransform,alineartimealgorithmthatrearrangesbytesusingatechniqueinspiredbyradixsorting.Forappropriatedata,RadixZipTransformisanalo-goustotheBurrows-WheelerTransformusedinbzip2,butisbothsimplerinoperationandmoree ectiveincompres-sion.Inaddition,RadixZipTransformcantakeadvantageofcorrelationsbetweentokenstreamswithnocomputationaloverhead.Experimentsoverpracticaldatashowthatforcommontokenstreams,RadixZipissuperiortobzip2.

1.INTRODUCTION

Tokenstreamsarisenaturallyinloggingsystemsanddatawarehouses,bothofwhichstorelargevolumesofdata.Log lescreatedbyGoogle’sweb-servers,forexample,recordavarietyofeventssuchasclicksonadvertisements,queriessubmittedatdoc.guandang.net(key,value)pairs[24]wherethekeyrepresentsthenameandtypeofthevalue.AtGoogle,astreamoflogrecordsisdividedintoblocks.Withineachblock,valuesare rstgroupedbykeyandthencompressed.Astreamofvalueswiththesamekeyconsti-tutesatokenstream.

Inrelationaldatawarehouses,tablesarecommonlystoredinrow-majorformat,alsoknownasthen-aryStorageModel(NSM).Tablescaninsteadbestoredincolumn-majorfor-mat,alsocalledthefullydecomposedstoragemodel(DSM)byCopelandandKhosha an[11].DSMoptimizesperfor-manceforSQLqueriesthatinvolveasmallsetofcolumns.However,recorddeletionandupdatestomultiplecolumnsofarecordbecomeexpensive.AusefulcompromisebetweenNSMandDSMistodivideastreamofrecordsintoblocksandtostorerecordswithinablockincolumn-majorfor-mat.Thisideawasintroducedinthe“partitionattributesacross”(PAX)formatbyAilamakietal[2].InPAX,acol-umnwithinablockconstitutesatokenstream.

Compressionoftokenstreamscanbecarriedoutbyava-rietyoftechniques.Ifthedomainoftokenvaluesissmallandknownapriori,thenthesimplestcompressiontech-niqueistoemployastaticdictionarythatmapsvaluesto xedcodes,whichthemselvescanbeencodedwithstandardcompressiontechniquessuchasHu manencoding[18].gzip(basedonLiv-Zempelcoding[37,38])andbzip2(basedontheBurrows-WheelerTransform[9])areslowerbutmorepowerfultechniques.Bothcanworkwithtokenvalueswhosedomainisnotknown.Di erentmethodsareusedinpracticebasedonaccessperformancerequirements.Hu manencod-ingorgziparecommonlow-overheadchoicesforfrequentlyaccesseddata,andbzip2isastrongerbutmorecostlychoiceforlong-termstorage.

RadixZipTransformisalineartimealgorithmforrearrang-ingbytesinablockoftokensusingatechniqueinspiredbyradixsorting.Thealgorithmissimple,fastandeasytoimplement.ItreplacestheBurrowsWheelerTransform(BWT)inbzip2fordealingwithtokenizedstreams,andim-provesinbothrun-timeperformanceandcompressionratioforsuchdata.WealsoshowhowRadixZipTransformcanbeusedwithoutadditionalperformancecosttoimprovecom-pressionofmultiplecorrelatedtokenstreams.

Experimentsoverthreerealworlddatasetscon rmthatRadixZipbeatsbzip2intermsofbothcompressionratioandthroughput(compressionanddecompressionrates).RadixZipcanachievecompressionratiosashighas15:1,beatingbzip2byasmuchas10-20%.Compressionanddecompressionrateswerealsohigh,beatingbzip2byabout10%overall;forcertainstreams,theimprovementwasashighas10:1.Forhighlycorrelatedtokenstreams,RadixZipwasabletoimproveoverbzip2byafactorofover300:1.

Roadmap:AnoverviewofRadixZipispresentedin§2.ThecoreroutineRadixZipTransformisdescribedindetailin§3.Itsoutputisfedtothebackendcompressor,whichisde-scribedin§4.ComparisonwithBurrows-WheelerTransformandbzip2isdonein§5.WeextendRadixZiptoworkovercorrelatedstreamsin§6.Experimentsoverrealdatasetsaredescribedin§7.TheapplicabilityofRadixZiptorelationaldata,XMLdocumentsandonGooglelogsdataisoutlinedin§8.Finally,wesurveytablecompressiontechniquesin§9beforeconcludingthepaperin§10.

Permissiontocopywithoutfeeallorpartofthismaterialisgrantedprovidedthatthecopiesarenotmadeordistributedfordirectcommercialadvantage,theVLDBcopyrightnoticeandthetitleofthepublicationanditsdateappear,andnoticeisgiventhatcopyingisbypermissionoftheVeryLargeDataBaseEndowment.Tocopyotherwise,ortorepublish,topostonserversortoredistributetolists,requiresafeeand/orspecialpermissionfromthepublisher,ACM.

VLDB‘07,September23-28,2007,Vienna,Austria.

Copyright2007VLDBEndowment,ACM978-1-59593-649-3/07/09.