Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

Dalhousie University

$29,000.00

Theory and implementation of algorithms & data structures for memory hierarchies

EF 2007-08

Résumé
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.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Nova Scotia, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data

Tel que publié

Application id
298332-2007
Name nom
Zeh, Norbert
Department département
Computer Science, Faculty of
Organization id
79
Institution établissement
Dalhousie University
Province en
Nova Scotia
Province fr
Nouvelle-Écosse
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2007
Competition year année de concours
2007
Award amount
29000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
331
Committee name en
Computing and Information Sciences - B
Committee name fr
Informatique - B
Area of application code
801
Area of application group en
Information and communication services
Area of application group fr
Services d'information et de télécommunications
Area of application en
Computer software
Area of application fr
Logiciel
Research subject code
2713
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Algorithms
Research subject fr
Algorithmes
Partie
1
Nb partie
5
Application title
Theory and implementation of algorithms & data structures for memory hierarchies
Keyword
NA
Application summary
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.