Bulk updates and cache sensitivity in search trees

Thumbnail Image

Files

isbn9789522480385.pdf (840.89 KB)

URL

Journal Title

Journal ISSN

Volume Title

Doctoral thesis (monograph)
Checking the digitized thesis and permission for publishing
Instructions for the author
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.

Authors

Date

2009

Department

Tietotekniikan laitos

Major/Subject

Mcode

Degree programme

Language

en

Pages

Verkkokirja (861 KB, 126 s.)

Series

TKK research reports in computer science and engineering, A, 2/09

Abstract

This thesis examines two topics related to binary search trees: cache-sensitive memory layouts and AVL-tree bulk-update operations. Bulk updates are also applied to adaptive sorting. Cache-sensitive data structures are tailored to the hardware caches in modern computers. The thesis presents a method for adding cache-sensitivity to binary search trees without changing the rebalancing strategy. Cache-sensitivity is maintained using worst-case constant-time operations executed when the tree changes. The thesis presents experiments performed on AVL trees and red-black trees, including a comparison with cache-sensitive B-trees. Next, the thesis examines bulk insertion and bulk deletion in AVL trees. Bulk insertion inserts several keys in one operation. The number of rotations used by AVL-tree bulk insertion is shown to be worst-case logarithmic in the number of inserted keys, if they go to the same location in the tree. Bulk deletion deletes an interval of keys. When amortized over a sequence of bulk deletions, each deletion requires a number of rotations that is logarithmic in the number of deleted keys. The search cost and total rebalancing complexity of inserting or deleting keys from several locations in the tree are also analyzed. Experiments show that the algorithms work efficiently with randomly generated input data. Adaptive sorting algorithms are efficient when the input is nearly sorted according to some measure of presortedness. The thesis presents an AVL-tree-based variation of the adaptive sorting algorithm known as local insertion sort. Bulk insertion is applied by extracting consecutive ascending or descending keys from the input to be sorted. A variant that does not require a special bulk-insertion algorithm is also given. Experiments show that applying bulk insertion considerably reduces the number of comparisons and time needed to sort nearly sorted sequences. The algorithms are also compared with various other adaptive and non-adaptive sorting algorithms.

Description

Keywords

cache-sensitivity, cache-consciousness, bulk insertion, bulk deletion, adaptive sorting, AVL tree, binary search tree

Other note

Citation

Permanent link to this item

https://urn.fi/URN:ISBN:978-952-248-038-5

Collections

[diss] Perustieteiden korkeakoulu / SCI