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):

Sibeyn, Jop F.

dblp



Editor(s):

Meinel, Christoph
Tison, Sophie

dblp
dblp



BibTeX cite key*:

F.Sibeyn-STACS-1999

Title, Booktitle

Title*:

External Selection

Booktitle*:

Proceedings of the 16th Annual Symposium on Theoretical Aspects of Computer Science (STACS-99)

Event, URLs

URL of the conference:


URL for downloading the paper:


Event Address*:

Trier

Language:

English

Event Date*
(no longer used):

March 4-6, 1999

Organization:


Event Start Date:

4 March 1999

Event End Date:

6 March 1999

Publisher

Name*:

Springer

URL:


Address*:

Berlin

Type:


Vol, No, Year, pp.

Series:

Lecture Notes in Computer Science

Volume:

1563

Number:


Month:

March

Pages:

291-301

Year*:

1999

VG Wort Pages:


ISBN/ISSN:

0302-9743

Sequence Number:


DOI:




Note, Abstract, ©


(LaTeX) Abstract:

Sequential selection has been solved in linear time by Blum e.a.
Running this algorithm on a problem of size $N$ with $N > M$, the
size of the main-memory, results in an algorithm that reads and
writes $\go{N}$ elements, while the number of comparisons is also
bounded by $\go{N}$. This is asymptotically optimal, but the
constants are so large that in practice sorting is faster for
most values of $M$ and $N$.

This paper provides the first detailed study of the external
selection problem. A randomized algorithm of a conventional type is
close to optimal in all respects. Our deterministic algorithm is
more or less the same, but first the algorithm builds an index
structure of all the elements. This effort is not wasted: the index
structure allows the retrieval of elements so that we do not need a
second scan through all the data. This index structure can also
be used for repeated selections, and can be extended over time. For
a problem of size $N$, the deterministic algorithm reads $N + o(N)$
elements and writes only $o(N)$ elements and is thereby optimal to
within lower-order terms.

Keywords:

Algorithms, External Memory, Selection



Download
Access Level:

Public

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Audience:

Expert

Appearance:

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



BibTeX Entry:

@INPROCEEDINGS{F.Sibeyn-STACS-1999,
AUTHOR = {Sibeyn, Jop F.},
EDITOR = {Meinel, Christoph and Tison, Sophie},
TITLE = {External Selection},
BOOKTITLE = {Proceedings of the 16th Annual Symposium on Theoretical Aspects of Computer Science (STACS-99)},
PUBLISHER = {Springer},
YEAR = {1999},
VOLUME = {1563},
PAGES = {291--301},
SERIES = {Lecture Notes in Computer Science},
ADDRESS = {Trier},
MONTH = {March},
ISBN = {0302-9743},
}


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)
Jop F. Sibeyn
Created
02/19/2000 03:23:43 PM
Revisions
3.
2.
1.
0.
Editor(s)
Uwe Brahm
Uwe Brahm
Anja Becker
Jop F. Sibeyn
Edit Dates
02/14/2005 08:10:32 PM
02/14/2005 08:10:06 PM
29.03.2000 14:04:37
19/02/2000 15:23:43
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section