Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
  External Selection

Sibeyn, J. F. (1999). External Selection. In C. Meinel, & S. Tison (Eds.), Proceedings of the 16th Annual Symposium on Theoretical Aspects of Computer Science (STACS-99) (pp. 291-301). Berlin: Springer.

Item is

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Sibeyn, Jop F.1, Autor
Affiliations:
1Max Planck Society, ou_persistent13              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: 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.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2010-03-021999
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: eDoc: 518035
Anderer: Local-ID: C1256428004B93B8-A1F8E22DAF812758C125688A004F1398-F.Sibeyn-STACS-1999
 Art des Abschluß: -

Veranstaltung

einblenden:
ausblenden:
Titel: Untitled Event
Veranstaltungsort: Trier
Start-/Enddatum: 1999-03-04 - 1999-03-06

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: Proceedings of the 16th Annual Symposium on Theoretical Aspects of Computer Science (STACS-99)
Genre der Quelle: Konferenzband
 Urheber:
Meinel, Christoph, Herausgeber
Tison, Sophie, Herausgeber
Affiliations:
-
Ort, Verlag, Ausgabe: Berlin : Springer
Seiten: - Band / Heft: - Artikelnummer: - Start- / Endseite: 291 - 301 Identifikator: -

Quelle 2

einblenden:
ausblenden:
Titel: Lecture Notes in Computer Science
Genre der Quelle: Reihe
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: -
Seiten: - Band / Heft: 1563 Artikelnummer: - Start- / Endseite: - Identifikator: ISSN: 0302-9743