GeoHashTree, A Multi-resolution Data Structure For Managing Point Clouds In PostgreSQL

Nouri Sabo (Natural Resources Canada)

10:00 on Saturday 21st September (in Session 51, starting at 9 a.m., EMCC: Room 4)

Show in Timetable

Description: Natural Resources Canada's new elevation data management system includes a novel hierarchical data structure, the GeoHashTree, for managing point clouds and other types of elevation data. It is a component of POINTPACH, the new extension for the management of point clouds in PostgreSQL. We wll explain the system architecture and the new data structure together with the results of tests conducted with the GeoHashTree.

Elevation data are increasingly used in many application areas. The growing number of applications using elevation data demonstrates the interest of users vis-à-vis this type of data. In fact, the needs continue to grow and specialize and acquisition technologies for this type of data are becoming more numerous, efficient and accessible. In this area, LiDAR is one of the technologies that has radically changed the way elevation data is acquired. If, on one hand, this technology allows to acquire data of high precision, it remains that the storage, management and exploitation of these data pose serious challenges due to their irregular distribution, their density and the amount of information they contain. This difficulty to manage and use point clouds often led some organizations to transform LiDAR points to regular data (e.g. raster) to facilitate data handling. In Canada, elevation data managed by Natural Resources Canada were stored and distributed as CDED (Canadian Digital Elevation Data). The CDED has a very restrictive format which supports only one resolution, making it impossible to manage data at a high resolution such as LiDAR. This is why, a little more than two years ago, the Mapping Information Branch of Natural Resources Canada initiated a project to develop a new flexible system for the management and dissemination of Canadian elevation data from various sources. This new system is mainly based on Open Source tools and also includes a new data structure called GeoHashTree. GeoHashTree is a generic data structure that allows to store, access and manipulate point clouds. It integrates both data with different types (irregular and regular data) and different resolutions in the same structure. GeoHashTree is a hierarchical structure which can present irregular data with various levels of abstraction (e.g. the same LiDAR data can have multiple representations with minimum storage overhead). At each level of the structure, several statistics such as multiple attributes' min, max and mean are presented. The structure itself is based on the Geohash which is a global geocoding system based on a hash function that divides the surface of the earth into a hierarchical grid. Inside the structure, each point is indexed and the search for a point is accomplished by a simple character string comparison, which greatly facilitates its integration into a database. GeoHashTree structure is a component of POINTPACH, a new extension to manage point clouds in PostgreSQL. Based on this structure, a system for the management of point clouds in PostgreSQL was developed. The system allows to interact with the database through spatial and attributive queries. For example, a user can select certain attributes from LiDAR points included in a bounding box, whose elevation is greater than 150 m. In addition to providing arbitrary access to the data, the ability to aggregate data and the ability to manage multi-resolution data, this structure allows the management of point clouds in a database while minimizing storage (more compact than LAS). In addition, our tests have shown that this structure allows to obtain an excellent performance in terms of access (better than LAS with arbitrary access to the data). In this paper, the system architecture and the new structure will be exposed. Then, the results of tests conducted with the new structure in terms of storage and performance will be presented. And finally, future developments based on this structure will be discussed.