Development of a hashing-based data structure for the fast retrieval of 3D terrestrial laser scanned data

Soohee Han, Sangmin Kim, Jae Hoon Jung, Changjae Kim, Kiyun Yu, Joon Heo

Research output: Contribution to journalArticlepeer-review

20 Citations (Scopus)


The volume of point cloud data obtained by 3-dimensional terrestrial laser scanners has grown very large as a result of scanner enhancements and application extensions. Quick point querying is therefore essential for efficient point cloud processing, and several data structures are applicable for that purpose. Octree, for example, is utilized in similar approaches and is considered a good candidate. This paper introduces hashing-based virtual grid (HVG), both as a competitor for octree and an improvement on the 3-dimensional virtual grid (3DVG). Whereas 3DVG is defined as a 3-dimensional array, HVG substitutes hashes for 3DVG's vertical indices. The performance of HVG was evaluated against those of octree and 3DVG by a point-querying operation. The selected operation finds neighboring points residing within a given radius for every individual point in the point cloud. HVG proved its balancing aspects throughout the operation, showing reasonable performance and memory efficiency. 3DVG, while its performance was excellent, required a significantly larger amount of memory. In summary, HVG is a suitable alternative to octree, and is expected to be effectively utilized as a base data structure for any application dealing with a massive amount of 3-dimensional point cloud data.

Original languageEnglish
Pages (from-to)1-10
Number of pages10
JournalComputers and Geosciences
Publication statusPublished - 2012 Feb

Bibliographical note

Funding Information:
This research was supported by two grants: one from Cutting-edge Urban Development–Korean Land Spatialization Research Project funded by the Ministry of Construction & Transportation of Korea (Grant 07KLSGC04 ), and the other from the Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education, Science, and Technology (Grant 2010-0006802 ).

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Computers in Earth Sciences


Dive into the research topics of 'Development of a hashing-based data structure for the fast retrieval of 3D terrestrial laser scanned data'. Together they form a unique fingerprint.

Cite this