Abstract

Khaled Mahar
An Enhanced Dynamic Parallel Model for Segment Trees
Segment trees are considered among the important data structures in computer science. A segment tree is, in principle, a static structure that is we cannot a new segment once the structure is built. In this paper we are presenting an enhanced model for this data structure. The suggested model is a parallel dynamic one that gives the flexibility of adding new segments to the structure in an efficient way and improves the query operation performance as well. The analysis of this parallel model on the CREW PRAM using O(log n) processors shows an improvement to the time complexity of the initial construction of the tree from O(n log n) to O(n), where n is the number of segments. The query operation also improves from O(log n + k) to O(log n/(log(log n)) + k) where k is the number of reported segments. Finally, the new segment ion feature is achieved with a time complexity of O(log n + m) where m is the maximum number of segments covering the same point. This proved to be very efficient specially when handling large amount of data.