Geometric Data Structures

点击翻译按钮获取中文摘要

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.