Electronic Journal Article
@Article
Zeitschriftenartikel in einem e-Journal



Show entries of:

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

Action:

login to update

Options:








Author, Editor

Author(s):

Sanders, Peter

dblp



BibTeX cite key*:

Sanders2000

Title

Title*:

Fast Priority Queues for Cached Memory

Journal

Journal Title*:

Journal of Experimental Algorithmics

Journal's URL:

http://www.jea.acm.org/

Download URL
for the article:

http://www.jea.acm.org/2000/SandersPriority/

Language:

English

Publisher

Publisher's
Name:

ACM Press

Publisher's URL:

http://www.acm.org

Publisher's
Address:

New York, USA

ISSN:

1084-6654

Vol, No, Year, pp.

Volume:

5

Number:


Month:


Year*:

2000

Pages:

1-25

Number of VG Pages:

50

Sequence Number:


DOI:


Abstract, Links, (C)

Note:


(LaTeX) Abstract:

The cache hierarchy prevalent in todays high performance processors
has to be taken into account in order to design algorithms that
perform well in practice. This paper advocates the adaption of
external memory algorithms to this purpose. This idea and the
practical issues involved are exemplified by engineering a fast
priority queue suited to external memory and cached memory that is
based on $k$-way merging. It improves previous external memory
algorithms by constant factors crucial for transferring it to cached
memory. Running in the cache hierarchy of a workstation the algorithm
is at least two times faster than an optimized implementation of
binary heaps and 4-ary heaps for large inputs.

URL for the Abstract:


Categories / Keywords:

data structure, external memory, cache

HyperLinks / References / URLs:

http://www.mpi-sb.mpg.de/~sanders/papers/index.html

Copyright Message:


Personal Comments:


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:

@MISC{Sanders2000,
AUTHOR = {Sanders, Peter},
TITLE = {Fast Priority Queues for Cached Memory},
JOURNAL = {Journal of Experimental Algorithmics},
PUBLISHER = {ACM Press},
YEAR = {2000},
VOLUME = {5},
PAGES = {1--25},
ADDRESS = {New York, USA},
ISBN = {1084-6654},
}


Entry last modified by Christine Kiesel, 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)
Peter Sanders
Created
01/23/2001 07:45:09 PM
Revisions
6.
5.
4.
3.
2.
Editor(s)
Christine Kiesel
Anja Becker
Anja Becker
Anja Becker
Anja Becker
Edit Dates
11.09.2003 15:56:11
04.04.2001 15:20:29
20.03.2001 17:07:30
09.03.2001 15:17:40
09.03.2001 14:28:52
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section