Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








Author, Editor

Author(s):

Brodal, Gerth Stølting

dblp



Editor(s):





BibTeX cite key*:

Brodal98a

Title, Booktitle

Title*:

Finger Search Trees with Constant Update Time

Booktitle*:

Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-98)

Event, URLs

URL of the conference:


URL for downloading the paper:


Event Address*:

San Francisko, USA

Language:

English

Event Date*
(no longer used):

January 25-27

Organization:

Association of Computing Machinery/Society for Industrial and Applied Mathematics

Event Start Date:

6 December 2019

Event End Date:

6 December 2019

Publisher

Name*:

ACM Press / SIAM

URL:


Address*:

New York, USA

Type:


Vol, No, Year, pp.

Series:


Volume:


Number:


Month:


Pages:

540-549

Year*:

1998

VG Wort Pages:


ISBN/ISSN:

0-89871-410-9

Sequence Number:


DOI:




Note, Abstract, ©


(LaTeX) Abstract:

We consider the problem of implementing finger search trees on the
pointer machine, {\it i.e.}, how to maintain a sorted list such that
searching for an element $x$, starting the search at any arbitrary
element $f$ in the list, only requires logarithmic time in the
distance between $x$ and $f$ in the list.

We present the first pointer-based implementation of finger search
trees allowing new elements to be inserted at any arbitrary position
in the list in worst case constant time. Previously, the best known
insertion time on the pointer machine was $O(\log^{*} n)$, where $n$
is the total length of the list. On a unit-cost RAM, a constant
insertion time has been achieved by Dietz and Raman by using
standard techniques of packing small problem sizes into a constant
number of machine words.

Deletion of a list element is supported in $O(\log^{*} n)$ time, which
matches the previous best bounds. Our data structure requires linear
space.



Download
Access Level:


Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Audience:

experts only

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat



BibTeX Entry:

@INPROCEEDINGS{Brodal98a,
AUTHOR = {Brodal, Gerth Stølting},
TITLE = {Finger Search Trees with Constant Update Time},
BOOKTITLE = {Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-98)},
PUBLISHER = {ACM Press / SIAM},
YEAR = {1998},
ORGANIZATION = {Association of Computing Machinery/Society for Industrial and Applied Mathematics},
PAGES = {540--549},
ADDRESS = {San Francisko, USA},
ISBN = {0-89871-410-9},
}


Entry last modified by Uwe Brahm, 03/02/2010
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Gerth Stolting Brodal
Created
02/26/1998 04:58:38 PM
Revisions
7.
6.
5.
4.
3.
Editor(s)
Uwe Brahm
Birgit Hofmann
Uwe Brahm
Uwe Brahm
Uwe Brahm
Edit Dates
01.04.99 11:48:35
01.04.99 10:10:23
01.04.99 09:35:14
29.03.99 18:43:00
29.03.99 16:33:21