Abstrakt. Vi karakteriserar prestandan av skillnaden kodning för komprimera uppsättningar och databasrelationer genom en analys av problemet med att uppskatta antalet bitar som behövs för att lagra mellanrum mellan värden i uppsättningar av heltal. Vi tillhandahåller analytiska uttryck för att uppskatta effektiviteten av skillnad kodning när elementen i uppsättningarna eller attributfälten i databas tuples hämtas från den enhetliga och Ziff distributioner. Vi undersöker också fallet där en enhetligt distribuerad domän kombineras med en zif-distribution, och med en godtycklig distribution. Vi presenterar begränsningar i de flesta fall, och probabilistisk konvergens resulterar i andra fall. Vi undersöker också effekterna av attribut domänomordning på kompressionsförhållandet. Våra simuleringar visar utmärkt enighet med teori.
Wu och Al. REF presenterar den teoretiska analysen av skillnadskodning för uppsättningar och relationstabeller.
The performance of difference coding for sets and relational tables
{'venue': 'JACM', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}