Grant: Discovery Grants Program - Individual
University of New Brunswick
$20,000.00
Spatial data structures
FY 2012-13
Summary
Extremely large amounts of spatial data (e.g. LiDAR data for digital elevation models, mulitbeam sonar data measuring sea floor bathymetry, high resolution aerial and satellite imagery) are being collected at an increasing rate. Society is increasingly data driven, and this trend is likely to continue and even accelerate in the coming years. The Large Hadron Collider, for example, generates 37 terabytes (37,000 gigabytes) of useful data per day. Data is so large that traditional computational models (e.g. the RAM and pointer machine models) are being replaced by models such as the I/O-model that consider disk I/Os as the only meaningful performance measure of an algorithm. The research program proposed here investigates new I/O-efficient data structures and algorithms to efficiently answer queries and provide updates (additions and deletions) for such massive spatial data. These algorithms and data structures form the basis for geographical information systems and for other software systems (e.g. databases, on-line mapping and image services) that make massive spatial data useful for businesses, scientists, government and the general public.
These new spatial data structures will play an important role for operations performed on spatial data, such as isosurface extraction (e.g. for use in flood prediction), volume computations (e.g. for dredging operations) or dynamic path planning for navigation. We will also explore data structures supporting efficient search to detect features among massive amounts of video and colour imagery (some with audio tracks or associated text), which is valuable for ongoing maintenance of civil infrastructure and security. This research will contribute directly to improving computer software products that use spatial data. Canadian companies that sell systems or services incorporating spatial data (or multi-dimensional data in general) can directly use the results of this research to improve the performance or increase the functionality of their software. Canadian companies will also benefit by hiring the highly qualified personnel (eight graduate students, three postdoctoral fellows) proposed to be funded under this research program.
Program
Discovery Grants Program - Individual
Recipient
Location
New Brunswick, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
36866-2011
Name nom
Nickerson, Bradford
Department département
Computer Science, Faculty of
Organization id
75
Institution établissement
University of New Brunswick
Province en
New Brunswick
Province fr
Nouveau-Brunswick
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2012
Competition year année de concours
2011
Award amount
20000
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
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
2
Nb partie
5
Application title
Spatial data structures
Keyword
NSERC
Application summary
Extremely large amounts of spatial data (e.g. LiDAR data for digital elevation models, mulitbeam sonar data measuring sea floor bathymetry, high resolution aerial and satellite imagery) are being collected at an increasing rate. Society is increasingly data driven, and this trend is likely to continue and even accelerate in the coming years. The Large Hadron Collider, for example, generates 37 terabytes (37,000 gigabytes) of useful data per day. Data is so large that traditional computational models (e.g. the RAM and pointer machine models) are being replaced by models such as the I/O-model that consider disk I/Os as the only meaningful performance measure of an algorithm. The research program proposed here investigates new I/O-efficient data structures and algorithms to efficiently answer queries and provide updates (additions and deletions) for such massive spatial data. These algorithms and data structures form the basis for geographical information systems and for other software systems (e.g. databases, on-line mapping and image services) that make massive spatial data useful for businesses, scientists, government and the general public.
These new spatial data structures will play an important role for operations performed on spatial data, such as isosurface extraction (e.g. for use in flood prediction), volume computations (e.g. for dredging operations) or dynamic path planning for navigation. We will also explore data structures supporting efficient search to detect features among massive amounts of video and colour imagery (some with audio tracks or associated text), which is valuable for ongoing maintenance of civil infrastructure and security. This research will contribute directly to improving computer software products that use spatial data. Canadian companies that sell systems or services incorporating spatial data (or multi-dimensional data in general) can directly use the results of this research to improve the performance or increase the functionality of their software. Canadian companies will also benefit by hiring the highly qualified personnel (eight graduate students, three postdoctoral fellows) proposed to be funded under this research program.