Geometric Data Structures

几何数据结构无处不在，我们不断地与它们交互。电脑和智能手机使用地理定位来确定我们的位置。利用这些信息，他们定制了我们的搜索结果，以提供与我们当前位置相关的数据。GPS设备和在线地图软件使用我们的位置来查找和显示相关的地图瓦片和附近的兴趣点。谷歌地球和地图等在线应用程序存储了有关整个地球表面的详细信息，并在用户飞行、缩放和搜索时实时提供部分信息。在每种情况下，都会查询几何数据结构以查找和检索相关信息。 拟议的研究计划旨在从理论和实践两个角度研究几何数据结构问题，如前面的应用程序中使用的问题。该计划将研究如何有效地利用数据或查询中的模式来加快查询时间和/或减少存储需求。例如，GPS设备或智能手机可以根据当前轨迹预测下一步最有可能需要检索的地图瓷砖，并可以预取它们。在线服务可以使用历史搜索数据来确定哪些搜索在哪些位置最受欢迎，并准备好从附近位置提供最常见的搜索结果。 这项研究的好处与几何数据结构的应用一样深远。智能手机应用程序将更快地回答查询，同时使用更少的电池电量。全球定位系统的设备将会更灵敏。谷歌地球和地图等大型在线服务将能够在其数据中心使用更少的计算能力，从而减少电力消耗，同时仍能提供相同或更好的响应能力。

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.