Campus Event Calendar
Event Entry
What and Who
Simplified Cache-Oblivious Planar Orthogonal Range Searching
Norbert Zeh
Max-Planck-Institut für Informatik - AG 1
AG1 Mittagsseminar (own work)
AG 1, AG 2, AG 3, AG 4, AG 5
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Monday, 13 March 2006
13:30
30 Minutes
46.1 - MPII
024
Saarbrücken
Abstract
The talk will discuss cache-oblivious structures for 2- and 3-sided
planar orthogonal range searching. The structure for 2-sided range searching is
the first cache-oblivious structure for this problem that achieves the optimal
query bound and linear space. Using this structure, a new structure for 3-sided
range searching can be obtaind that matches the query and space bounds of the
best previous structure, but is simpler. At the expense of a slightly worse
query bound, the 2-sided structure can be made semi-dynamic, supporting
insertions in the same amortized bound as cache-oblivious B-trees.
Contact
Ulrich Meyer
--email hidden
passcode not visible
logged in users only
Ulrich Meyer, 03/10/2006 12:41 -- Created document.