Theory and implementation of algorithms & data structures for memory hierarchies

My research focuses on the theory and implementation of algorithms and data structures for memory hierarchies. Current technological developments lead to a rapidly widening gap between processor speeds and memory (RAM) transfer rates. This gap is even more significant if disk access times are taken into account. Hence, today's processors are useless unless there is a way to bridge the gap between processor and memory speeds. The approach to this problem taken in state-of-the-art computers is the use of a hierarchy of several levels of fast, but relatively small, cache memory. This approach is useful only if the programs that are run have sufficiently local memory access patterns that ensure that most memory accesses can be served from cache rather than from main memory or disk. Achieving this locality is challenging for many computational problems. This is the focus of my research. My research programme has a theoretical and a more applied facet. The theoretical work aims at developing general techniques for designing algorithms and data structures with high access locality. The applied work will apply these techniques and evaluate their usefulness in particular problem settings through implementation and experimentation. The particular problems I focus on are:(1) Graph problems. This is motivated by applications that have to process massive graphs efficiently, such as web mining and web modelling, geographic information systems, and information retrieval.(2) Data structures and algorithms for fundamental geometric search problems, most notably range search problems. The motivation is the need to answer such search problems efficiently in database applications and geographic information systems.