Title

Efficient Access to Non-Sequential Elements of a Search Tree

Document Type

Article

Publication Date

Winter 1-23-2011

Publication Source

The Third International Conference on Advances in Databases, Knowledge, and Data Applications

Inclusive pages

181-185

Publisher

International Academy, Research , and Industry Association

Place of Publication

St. MaartenThe Netherlands Antilles

ISBN/ISSN

978-1-61208-002-4

Peer Reviewed

yes

Abstract

This article describes how a search tree can be extended in order to allow efficient access to predefined subsets of the stored elements. This is achieved by marking some of the elements of the search tree with marker bits. We show that our approach does not affect the asymptotic logarithmic complexity for existing operations. At the same time, it is beneficial because the modified search tree can now efficiently support requests on predefined subsets of the search elements that it previously could not.

Keywords

marker bits; search trees; data structures

Disciplines

Computer Sciences