On a Recurrence Arising in Graph Compression - Publikacja - MOST Wiedzy

Wyszukiwarka

On a Recurrence Arising in Graph Compression

Abstrakt

In a recently proposed graphical compression algorithm by Choi and Szpankowski (2012), the following tree arose in the course of the analysis. The root contains n balls that are consequently distributed between two subtrees according to a simple rule: In each step, all balls independently move down to the left subtree (say with probability p) or the right subtree (with probability 1􀀀p). A new node is created as long as there is at least one ball in that node. Furthermore, a nonnegative integer d is given, and at level d or greater one ball is removed from the leftmost node before the balls move down to the next level. These steps are repeated until all balls are removed (i.e., after n + d steps). Observe that when d = 1 the above tree can be modeled as a trie that stores n independent sequences generated by a binary memoryless source with parameter p. Therefore, we coin the name (n; d)-tries for the tree just described, and to which we often refer simply as d-tries. We study here in detail the path length, and show how much the path length of such a d-trie diers from that of regular tries. We use methods of analytic algorithmics, from Mellin transforms to analytic poissonization.

Cytuj jako

Pełna treść

pełna treść publikacji nie jest dostępna w portalu

Słowa kluczowe

Informacje szczegółowe

Kategoria:
Publikacja w czasopiśmie
Typ:
artykuł w czasopiśmie wyróżnionym w JCR
Opublikowano w:
ELECTRONIC JOURNAL OF COMBINATORICS nr 19, strony 1 - 22,
ISSN: 1077-8926
Język:
angielski
Rok wydania:
2012
Opis bibliograficzny:
Choi Y., Knessl C., Szpankowski W.: On a Recurrence Arising in Graph Compression// ELECTRONIC JOURNAL OF COMBINATORICS. -Vol. 19, iss. 3 (2012), s.1-22
Weryfikacja:
Politechnika Gdańska

wyświetlono 62 razy

Publikacje, które mogą cię zainteresować

Meta Tagi