TY - JOUR
T1 - Dynamic segment trees for ranges and prefixes
AU - Chang, Yeim Kuan
AU - Lin, Yung Chieh
N1 - Funding Information:
The authors would like to express their sincere thanks to the editors and the reviewers who gave very insightful and encouraging comments. This work was supported in part by the National Science Council, Republic of China, under Grant NSC-94-2213-E-006-026.
PY - 2007
Y1 - 2007
N2 - In this paper, we develop a segment tree data structure for solving dynamic table lookup problems. The proposed dynamic segment tree (DST) uses all of the distinct end points of ranges as the keys based on a new range end point scheme. The new end point scheme generates fewer end points than the traditional end point scheme. DST is implemented as a balanced binary search tree augmented with a range set in each node. The performance of accessing and updating the ranges stored in each node is improved by an efficient range set data structure that combines the priority queue and the interval tree. Based on the proposed data structures, the time complexities of search, insertion, and deletion in a set of N arbitrary ranges are O(log N), O(log N times log Max), and O(Max times log N times log Max), respectively, where Max is the maximum number of ranges covering any address. In practical routing tables, Max is a small constant (six for the routing tables we tested). The memory requirement for DST is O(N log N). The experimental results using real Internet Protocol version 4 (IPv4) routing tables show that both the DST and prefix binary tree on binary tree (PBOB) by Lu et al. (2004) perform much better than the multiway range tree (MRT) by Warkhede et al. (2004) and prefix in B-tree (PIBT) by Lu et al. (2005) in terms of update speed and memory consumption, but DST performs much better than PBOB and a little slower than MRT and PIBT in terms of search speed.
AB - In this paper, we develop a segment tree data structure for solving dynamic table lookup problems. The proposed dynamic segment tree (DST) uses all of the distinct end points of ranges as the keys based on a new range end point scheme. The new end point scheme generates fewer end points than the traditional end point scheme. DST is implemented as a balanced binary search tree augmented with a range set in each node. The performance of accessing and updating the ranges stored in each node is improved by an efficient range set data structure that combines the priority queue and the interval tree. Based on the proposed data structures, the time complexities of search, insertion, and deletion in a set of N arbitrary ranges are O(log N), O(log N times log Max), and O(Max times log N times log Max), respectively, where Max is the maximum number of ranges covering any address. In practical routing tables, Max is a small constant (six for the routing tables we tested). The memory requirement for DST is O(N log N). The experimental results using real Internet Protocol version 4 (IPv4) routing tables show that both the DST and prefix binary tree on binary tree (PBOB) by Lu et al. (2004) perform much better than the multiway range tree (MRT) by Warkhede et al. (2004) and prefix in B-tree (PIBT) by Lu et al. (2005) in terms of update speed and memory consumption, but DST performs much better than PBOB and a little slower than MRT and PIBT in terms of search speed.
UR - http://www.scopus.com/inward/record.url?scp=63049122435&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=63049122435&partnerID=8YFLogxK
U2 - 10.1109/TC.2007.1037
DO - 10.1109/TC.2007.1037
M3 - Article
AN - SCOPUS:63049122435
VL - 56
SP - 769
EP - 784
JO - IEEE Transactions on Computers
JF - IEEE Transactions on Computers
SN - 0018-9340
IS - 6
ER -