Optimal tree structure with loyal users and batch updates

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

4 Scopus Citations
View graph of relations


Related Research Unit(s)


Original languageEnglish
Pages (from-to)630-639
Journal / PublicationJournal of Combinatorial Optimization
Issue number4
Publication statusPublished - Nov 2011


We study the probabilistic model in the key tree management problem. Users have different behaviors. Normal users have probability p to issue join/leave request while the loyal users have probability zero. Given the numbers of such users, our objective is to construct a key tree with minimum expected updating cost. We observe that a single LUN (Loyal User Node) is enough to represent all loyal users. When 1-p≤0.57 we prove that the optimal tree that minimizes the cost is a star. When 1-p>0.57, we try to bound the size of the subtree rooted at every non-root node. Based on the size bound, we construct the optimal tree using dynamic programming algorithm in O(n·K+K 4) time where K=min∈{4(log∈(1-p) -1) -1,n} and n is the number of normal users. © 2010 Springer Science+Business Media, LLC.

Research Area(s)

  • Group keys, Key trees, Optimality, Probability, Updating cost