External Selection

Sibeyn, Jop F.

Local TagsRelease HistoryDetailsSummary

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 Released

show all hide all

Basic

show hide

Item Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-35C5-1 Version Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-35C7-E

Genre: Conference Paper

Files

show Files

Locators

show

Creators

show

hide

Creators:
Sibeyn, Jop F.¹, Author

Affiliations:
1Max Planck Society, ou_persistent13

Content

show

hide

Free keywords: -

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.

Details

show

hide

Language(s): eng - English

Dates: Modified: 2010-03-02Date issued: 1999

Publication Status: Issued

Pages: -

Publishing info: -

Table of Contents: -

Rev. Type: -

Identifiers: eDoc: 518035
Other: Local-ID: C1256428004B93B8-A1F8E22DAF812758C125688A004F1398-F.Sibeyn-STACS-1999

Degree: -

Event

show

hide

Title: Untitled Event

Place of Event: Trier

Start-/End Date: 1999-03-04 - 1999-03-06

Legal Case

show

Project information

show

Source 1

show

hide

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

Source Genre: Proceedings

Creator(s):
Meinel, Christoph, Editor
Tison, Sophie, Editor

Affiliations:
-

Publ. Info: Berlin : Springer

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

Source 2

show

hide

Title: Lecture Notes in Computer Science

Source Genre: Series

Creator(s):

Affiliations:

Publ. Info: -

Pages: - Volume / Issue: 1563 Sequence Number: - Start / End Page: - Identifier: ISSN: 0302-9743