Optimal tree structure with loyal users and batch updates
Research output: Journal Publications and Reviews (RGC: 21, 22, 62) › 21_Publication in refereed journal › peer-review
Author(s)
Related Research Unit(s)
Detail(s)
Original language | English |
---|---|
Pages (from-to) | 630-639 |
Journal / Publication | Journal of Combinatorial Optimization |
Volume | 22 |
Issue number | 4 |
Publication status | Published - Nov 2011 |
Link(s)
Abstract
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
Citation Format(s)
Optimal tree structure with loyal users and batch updates. / Chan, Yu-Ki; Li, Minming; Wu, Weiwei.
In: Journal of Combinatorial Optimization, Vol. 22, No. 4, 11.2011, p. 630-639.Research output: Journal Publications and Reviews (RGC: 21, 22, 62) › 21_Publication in refereed journal › peer-review