Alphabetic Huffman Tree (AH-Tree) is an appropriate data structure to index data set with skewed access frequencies, which fits the feature of web-based wireless data broadcast service to a mass num- ber of mobile clients. In this paper we solve a long-time open question to construct an arbitrary k-ary AH-Tree with Hu-Tucker algorithm (1) by dynamic programming, whose time complexity is O(kn 2 ), where n is cardinality of the data set. We then build a distributed AH-Tree in- dex sequence with a special control-table shrinking technique. Next, we introduce a pyramid index allocation method, which is scalable to any available broadcast channel. We prove the correctness of our algorithm, analyze the time complexity of tree-construction process, and compare our design with B + -Tree index by numerical experiments. Both mathe- matical analysis and simulation results prove the efficiency of our design. To the best of our knowledge, we are the first to propose a detailed, fast, and distributed k-ary AH-Tree index with allocation protocol, which has both theoretical and practical significance in this area.
['Yongtian Yang', 'Xiaofeng Gao', 'Xin Lu', 'Jiaofei Zhong', 'Guihai Chen']
Distributed AH-Tree Based Index Technology for Multi-channel Wireless Data Broadcast