Optimal tree structure with loyal users and batch updates |
| |
Authors: | Yu-Ki Chan Minming Li Weiwei Wu |
| |
Institution: | 1.Department of Computer Science,City University of Hong Kong,Hong Kong,PR China;2.Department of Computer Science,University of Science and Technology of China,Hefei,PR China;3.USTC-CityU Joint Research Institute,Suzhou,PR China |
| |
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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|