Layered Working-Set Trees

Details Layered Working-Set Trees Layered Working-Set Trees

2009-07-13

arxiv.org/abs/0907.2071v1

Computer Science

Data Structures and Algorithms

10 pages, 3 figures

Scientific paper

The working-set bound [Sleator and Tarjan, J. ACM, 1985] roughly states that searching for an element is fast if the element was accessed recently. Binary search trees, such as splay trees, can achieve this property in the amortized sense, while data structures that are not binary search trees are known to have this property in the worst case. We close this gap and present a binary search tree called a layered working-set tree that guarantees the working-set property in the worst case. The unified bound [Badoiu et al., TCS, 2007] roughly states that searching for an element is fast if it is near (in terms of rank distance) to a recently accessed element. We show how layered working-set trees can be used to achieve the unified bound to within a small additive term in the amortized sense while maintaining in the worst case an access time that is both logarithmic and within a small multiplicative factor of the working-set bound.

Affiliated with

Also associated with

No associations

Rating

Layered Working-Set Trees does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Layered Working-Set Trees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Layered Working-Set Trees will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-100146