Improving the Efficiency of Point Cloud Data Management
Creators: name: Bormann, Pascal
name: :Unav
Publisher: name: Fraunhofer-Gesellschaft
Year: 2024
Subjects: Branche: Bioeconomics and Infrastructure
Research Line: Computer graphics (CG)
LTA: Scalable architectures for massive data sets
LTA: Generation, capture, processing, and output of images and 3D models
Point clouds
Parallel algorithms
Data management

description: The collection of point cloud data has increased drastically in recent years, which poses challenges for the data management layer. Multi-billion point datasets are commonplace and users are getting accustomed to real-time data exploration in the Web. To make this possible, existing point cloud data management approaches rely on optimized data formats which are time- and resource-intensive to generate. This introduces long wait times before data can be used and frequent data duplication, since these optimized formats are often domain- or application-specific. As a result, data management is a challenging and expensive aspect when developing applications that use point cloud data. We observe that the interaction between applications and the point cloud data management layer can be modeled as a series of queries similar to those found in traditional databases. Based on this observation, we evaluate current point cloud data management using three query metrics: Responsiveness, throughput, and expressiveness. We contribute to the current state of the art by improving these metrics for both the handling of raw files without preprocessing, as well as indexed point clouds. In the domain of unindexed point cloud data, we introduce the concept of ad-hoc queries, which are queries executed ad-hoc on raw point cloud files. We demonstrate that ad-hoc queries can improve query responsiveness significantly as they do not require long wait times for indexing or database imports. Using columnar memory layouts, queries on datasets of up to a billion points can be answered in interactive or near-interactive time, with throughputs of more than one hundred million points per second on unindexed data. A demonstration of an adaptive indexing method shows that spending a few seconds per query on index creation can improve responsiveness by up to an order of magnitude. Our experiments also confirm the importance of high-throughput systems when querying point cloud data, as the overhead of data transmission has a significant effect on the overall query performance. For situations where indexing is mandatory, we demonstrate improvements to the runtime performance of existing point cloud indexing tools. We developed a fast indexer based on task-parallel programming, using Morton indices to efficiently sort and distribute point batches onto worker threads. This system, called Schwarzwald, outperformed existing indexers by up to a factor 9 when it was first published, and still has competitive performance to current out-of-core capable indexers. Additionally we adapted our indexing algorithm for distributed processing in a Cloud-environment and demonstrate that its horizontal scalability allows it to outperform all existing indexers by up to a factor of 3. Lastly we demonstrated point cloud indexing in real-time during Light Detection And Ranging (LiDAR) capturing, based on a similar task-based algorithm but optimized for progressive indexing. Our real-time indexer is able to keep up with current LiDAR sensors in a real-world test, with end-to-end latencies as low as 0.1 seconds. Together, our improvements significantly reduce wait times for working with point cloud data and increase the overall efficiency of the data access layer.
description: Die Größe und Menge von Punktwolken-Datensätzen, welche durch verschiedene Verfahren generiert werden, ist im letzten Jahrzehnt stark gewachsen. Datensätze mit Milliarden oder sogar Billionen von Punkten sind keine Seltenheit mehr. Moderne Verfahren ermöglichen den interaktiven Umgang mit verschiedensten Geodaten. Um die Arbeit mit Punktwolken im gleichen Maße zu ermöglichen, bedarf es ausgefeilter Datenhaltungs-Lösungen. Hierbei kommen dabei aktuell zeit- und rechenintensive Verfahren zum Einsatz, welche Punktwolkendaten strukturieren und in optimierte Formate bringen. Dabei kommt es zu langen Wartezeiten in der Aufbereitung und häufig zur Duplikation der Daten, da viele dieser optimierten Formate domänen- oder anwendungsspezifisch sind. In der Entwicklung von Anwendungen auf Basis von Punktwolken ist daher eine effiziente Datenhaltung eine der großen Herausforderungen. Auch wenn Datenbanken nach wie vor eine Nischenlösung in der Datenhaltung von Punktwolken sind, so lässt sich die Interaktion zwischen Anwendungen und der Datenhaltung analog zu Datenbank-Abfragen darstellen. Basierend auf dieser Beobachtung lassen sich die aktuellen Ansätze zur Punktwolken-Datenhaltung anhand von drei Kriterien bewerten: Die Antwortzeit, der Durchsatz, und die Ausdruckskraft von Punktwolken-Abfragen. Unser Beitrag zum aktuellen Stand der Forschung sind Verbesserungen dieser drei Kriterien für zwei gängige Datenhaltungs-Ansätze: Das Arbeiten mit Rohdaten sowie die Indexierung von Punktwolken. Im Bereich der Arbeit mit Rohdaten führen wir das Konzept der Ad-hoc Abfragen ein und zeigen, dass moderne Hardware effizient genug ist, um viele gängige Abfragen in kurzer Zeit und ohne Vorverarbeitung durchführen zu können. Im Vergleich zu typischen Indexierungsprozessen oder einem Datenbank-Import können Ad-hoc Abfragen die Antwortzeit deutlich verbessern. Mit Hilfe spaltenbasierter Datenformate ist dabei ein Durchsatz von über 100 Millionen Punkten pro Sekunde möglich. Weiterhin demonstrieren wir, dass adaptive Indexierung die Antwortzeiten bestimmter Abfragen um bis zu einer Größenordnung verringern kann. Eine umfangreiche Evaluation von Ad-hoc Abfragen demonstriert deren Machbarkeit und zeigt den Zusammenhang zwischen Datendurchsatz und Antwortzeit auf. Im Bereich indexierter Punktwolken verbessern wir die Laufzeit aktueller Indexierungs-Algorithmen. Basierend auf dem task-parallel programming Ansatz und Morton Indizes haben wir Schwarzwald entwickelt, ein System zur schnellen Berechnung eines für die Visualisierung optimierten Index. Zum Zeitpunkt der Erstveröffentlichung war Schwarzwald bis zu 9 mal schneller beim Erstellen eines gleichwertigen Index verglichen mit bestehenden Lösungen. Die Laufzeit der schnellsten aktuell verfügbaren Out-Of-Core Indexer ist vergleichbar zu der von Schwarzwald, wie wir in mehreren Testreihen belegen. Wir demonstrieren außerdem, dass der zugrundeliegende Algorithmus von Schwarzwald für die verteilte Verarbeitung in der Cloud adaptiert werden kann, was zu besserer Skalierbarkeit und bis zu dreimal kürzeren Laufzeiten verglichen mit bestehenden Systemen führt. Zur weiteren Reduktion von Wartezeiten demonstrieren wir außerdem das erste echtzeitfähige Indexierungs-System für Punktwolken, welches eine Indexierung direkt während der Aufnahme am LiDAR Sensor ermöglicht. Die Verwendung unseres Echtzeit-Indexers reduziert dabei die Wartezeit von der Aufnahme bis zur Nutzung der Daten um mehrere Größenordnungen in den Bereich unterhalb einer Sekunde. Unsere Verbesserungen verringern bestehende Wartezeiten in der Vorverarbeitung signifikant und erhöhen somit die Effizient in der Punktwolken-Datenhaltung