UCL Discovery
UCL home » Library Services » Electronic resources » UCL Discovery

Parallel processing of big point clouds using Z-Order-based partitioning

Alis, C; Boehm, J; Liu, K; (2016) Parallel processing of big point clouds using Z-Order-based partitioning. In: Proceedings of the XXIII ISPRS Congress. (pp. pp. 71-77). International Society of Photogrammetry and Remote Sensing (ISPRS): Prague, Czech Republic. Green open access

Boehm_isprs-archives-XLI-B2-71-2016.pdf - Published version

Download (3MB) | Preview


As laser scanning technology improves and costs are coming down, the amount of point cloud data being generated can be prohibitively difficult and expensive to process on a single machine. This data explosion is not only limited to point cloud data. Voluminous amounts of high-dimensionality and quickly accumulating data, collectively known as Big Data, such as those generated by social media, Internet of Things devices and commercial transactions, are becoming more prevalent as well. New computing paradigms and frameworks are being developed to efficiently handle the processing of Big Data, many of which utilize a compute cluster composed of several commodity grade machines to process chunks of data in parallel. A central concept in many of these frameworks is data locality. By its nature, Big Data is large enough that the entire dataset would not fit on the memory and hard drives of a single node hence replicating the entire dataset to each worker node is impractical. The data must then be partitioned across worker nodes in a manner that minimises data transfer across the network. This is a challenge for point cloud data because there exist different ways to partition data and they may require data transfer. We propose a partitioning based on Z-order which is a form of locality-sensitive hashing. The Z-order or Morton code is computed by dividing each dimension to form a grid then interleaving the binary representation of each dimension. For example, the Z-order code for the grid square with coordinates (x = 1 = 012, y = 3 = 112) is 10112 = 11. The number of points in each partition is controlled by the number of bits per dimension: The more bits, the fewer the points. The number of bits per dimension also controls the level of detail with more bits yielding finer partitioning. We present this partitioning method by implementing it on Apache Spark and investigating how different parameters affect the accuracy and running time of the k nearest neighbour algorithm for a hemispherical and a triangular wave point cloud.

Type: Proceedings paper
Title: Parallel processing of big point clouds using Z-Order-based partitioning
Event: XXIII ISPRS Congress
Location: Prague, Czech Republic
Dates: 12 July 2016 - 19 July 2016
Open access status: An open access version is available from UCL Discovery
DOI: 10.5194/isprsarchives-XLI-B2-71-2016
Publisher version: http://dx.doi.org/10.5194/isprs-archives-XLI-B2-71...
Language: English
Additional information: All site content, except where otherwise noted, is licensed under the Creative Commons Attribution 3.0 License.
Keywords: Z-order, Spatial partitioning, Big Data, LiDAR, Point Cloud, Apache Spark
UCL classification: UCL
UCL > Provost and Vice Provost Offices
UCL > Provost and Vice Provost Offices > UCL BEAMS
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Civil, Environ and Geomatic Eng
URI: https://discovery.ucl.ac.uk/id/eprint/1539080
Downloads since deposit
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item