A survey of self-organizing data structures

Albers, Susanne; Westbrook, Jeffery

Local TagsRelease HistoryDetailsSummary

A survey of self-organizing data structures

Albers, S., & Westbrook, J.(1996). A survey of self-organizing data structures (MPI-I-1996-1-026). Saarbrücken: Max-Planck-Institut für Informatik.

Item is Released

show all hide all

Basic

show hide

Item Permalink: https://hdl.handle.net/11858/00-001M-0000-0014-A03D-0 Version Permalink: https://hdl.handle.net/21.11116/0000-0001-2868-E

Genre: Report

Files

show Files

hide Files

:

MPI-I-96-1-026-1.pdf (Any fulltext), 339KB

View Save

File Permalink:
https://hdl.handle.net/21.11116/0000-0001-2869-D

Name:
MPI-I-96-1-026-1.pdf

Description:
-

OA-Status:

Visibility:
Public

MIME-Type / Checksum:
application/pdf / [MD5]

Technical Metadata:

View

Copyright Date:
-

Copyright Info:
-

License:
-

Locators

show

Creators

show

hide

Creators:
Albers, Susanne¹, Author
Westbrook, Jeffery², Author

Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019
2External Organizations, ou_persistent22

Content

show

hide

Free keywords: -

Abstract: This paper surveys results in the design and analysis of self-organizing data structures for the search problem. We concentrate on two simple but very popular data structures: the unsorted linear list and the binary search tree. A self-organizing data structure has a rule or algorithm for changing pointers or state data. The self-organizing rule is designed to get the structure into a good state so that future operations can be processed efficiently. Self-organizing data structures differ from constraint structures in that no structural invariant, such as a balance constraint in a binary search tree, has to be satisfied. In the area of self-organizing linear lists we present a series of deterministic and randomized on-line algorithms. We concentrate on competitive algorithms, i.e., algorithms that have a guaranteed performance with respect to an optimal offline algorithm. In the area of binary search trees we present both on-line and off-line algorithms. We also discuss a famous self-organizing on-line rule called splaying and present important theorems and open conjectures on splay trees. In the third part of the paper we show that algorithms for self-organizing lists and trees can be used to build very effective data compression schemes. We report on theoretical and experimental results.

Details

show

hide

Language(s): eng - English

Dates: Date issued: 1996

Publication Status: Issued

Pages: 39 p.

Publishing info: Saarbrücken : Max-Planck-Institut für Informatik

Table of Contents: -

Rev. Type: -

Identifiers: Report Nr.: MPI-I-1996-1-026
BibTex Citekey: AlbersWestbrook96

Degree: -

Event

show

Legal Case

show

Project information

show

Source 1

show

hide

Title: Research Report / Max-Planck-Institut für Informatik

Source Genre: Series

Creator(s):

Affiliations:

Publ. Info: -

Pages: - Volume / Issue: - Sequence Number: - Start / End Page: - Identifier: -