Campus Event Calendar
Event Entry
What and Who
The I/O complexity of sorting with two key lengths
Mayank Goswami
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1, AG 5
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Tuesday, 15 October 2013
13:00
30 Minutes
E1 4
024
Saarbrücken
Abstract
We consider the problem of external-memory sorting when keys are atomic and can have two different lengths. Keys are indivisible, and short keys have unit length, while the remaining (long) keys have length w (greater than B--the block size).
The key observation is that the complexity of this sorting problem depends on the interleaving of the long and short keys in the final sorted order, and the lower and upper bounds are parameterized by the final interleaving.
The sorting lower bound consists of two terms based on sorting keys of equal lengths, and a third term based on a batched searching problem---Placement of Long Elements(PLE). In the PLE problem, the objective is to place each long element between its predecessor and successor short element. The PLE lower bounds are the main results.
Contact
Goswami Mayank
--email hidden
passcode not visible
logged in users only
Goswami Mayank, 09/27/2013 13:01
Goswami Mayank, 09/26/2013 12:10 -- Created document.
Goswami Mayank, 09/26/2013 12:10 -- Created document.