Grant: Discovery Grants Program - Individual
Carleton University
$36,000.00
Geometric Data Structures
EF 2013-14
Résumé
Geometric data structures are everywhere, and we interact with them continually. Computers and smart phones use geolocation to determine our location. Using this information, they tailor our search results to provide data that is relevant to our current location. GPS units and online mapping software use our location to find and display relevant map tiles and nearby points of interest. Online applications like Google Earth and Maps store detailed information about the entire surface of the earth and serve up parts of this information, in real time, as users fly, zoom, and search through it. In each case, geometric data structures are queried to find and retrieve the relevant information.The proposed research program aims to study geometric data structuring problems like the ones used in the preceding applications, from both a theoretical and a practical perspective. The program will study how patterns in the data or in the queries can be effectively used to speed up query times and/or reduce storage requirements. For example, a GPS device or smartphone can predict, based on the current trajectory, which map tiles will most likely need to be retrieved next and can pre-fetch them. Online services can use historical search data to determine which searches are popular from which locations and have the most common search results ready to serve from a nearby location.The benefits of this research are as far reaching as the applications of geometric data structures. Smart phone applications will answer queries more quickly while simultaneously using less battery power. GPS units will be more responsive. Large online services like Google Earth and Maps will be able to use less computing power, and hence electricity, in their data centres while still providing the same, or better, responsiveness.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Ontario, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data
Tel que publié
Application id
250380-2013
Name nom
Morin, Patrick
Department département
Computer Science, School of
Organization id
23
Institution établissement
Carleton University
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2013
Competition year année de concours
2013
Award amount
36000
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
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
802
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
Information systems and technology
Area of application fr
Systèmes d'information et technologie de l'information
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
Geometric Data Structures
Keyword
NSERC
Application summary
Geometric data structures are everywhere, and we interact with them continually. Computers and smart phones use geolocation to determine our location. Using this information, they tailor our search results to provide data that is relevant to our current location. GPS units and online mapping software use our location to find and display relevant map tiles and nearby points of interest. Online applications like Google Earth and Maps store detailed information about the entire surface of the earth and serve up parts of this information, in real time, as users fly, zoom, and search through it. In each case, geometric data structures are queried to find and retrieve the relevant information.The proposed research program aims to study geometric data structuring problems like the ones used in the preceding applications, from both a theoretical and a practical perspective. The program will study how patterns in the data or in the queries can be effectively used to speed up query times and/or reduce storage requirements. For example, a GPS device or smartphone can predict, based on the current trajectory, which map tiles will most likely need to be retrieved next and can pre-fetch them. Online services can use historical search data to determine which searches are popular from which locations and have the most common search results ready to serve from a nearby location.The benefits of this research are as far reaching as the applications of geometric data structures. Smart phone applications will answer queries more quickly while simultaneously using less battery power. GPS units will be more responsive. Large online services like Google Earth and Maps will be able to use less computing power, and hence electricity, in their data centres while still providing the same, or better, responsiveness.