Abstract

Abstract
Point Set Registration (PSR) algorithms have very different underlying theoretical models to define a process that calculates the alignment solution between two point clouds. The selection of a particular PSR algorithm can be based on the efficiency (time to compute the alignment) and accuracy (a measure of error using the estimated alignment). In our specific context, previous work used a CPD algorithm to detect and quantify change in spatiotemporal datasets composed of moving and shape-changing objects represented by a sequence of time stamped 2D polygon boundaries. Though the results were promising, we question if the selection of a particular PSR algorithm influences the results of detection and quantification of change. In this work we review and compare several PSR algorithms, characterize test datasets and used metrics, and perform tests for the selected datasets. The results show pyCPD and cyCPD implementations of CPD to be good alternatives and that BCPD can have potential to be yet another alternative. The results also show that detection and quantification accuracy change for some of the tested PSR implementations.

Abstract
Index structures were often used to optimise fetch operations to external storage devices (secondary memory). Nowadays, this also holds for increasingly large amounts of data residing in main-memory (primary memory). Within this scope, this work focuses on index structures that efficiently insert, query and delete valid-time data from very large datasets. This work performs a comparative study on the performance of the Interval B+ tree (IB+ tree) and the Improved Interval B+ tree (I2B+ tree): a variant that improves the time-efficiency of the deletion operation by reducing the number of traversed nodes to access siblings. We performed an extensive analysis of the performance of two operations: insertions and deletions, on both index structures, using multiple datasets with growing volumes of data, distinct temporal distributions and tree parameters (time-split alpha and node order). Results confirm that the I2B+ tree globally outperforms the IB+ tree, since, on average, deletion operations are 7% faster, despite insertions requiring 2% more time. Furthermore, results also allowed to determine the key factors that augment the performance difference on deletions between both trees. Copyright © 2021 by Author/s and Licensed by Veritas Publications Ltd., UK.

Abstract

Abstract
Index structures are fast-access methods. In the past, they were often used to minimise fetch operations to external storage devices (secondary memory). Nowadays, this also holds for increasingly large amounts of data residing in main-memory (primary memory). Examples of software that deals with this fact are in-memory databases and mobile device applications. Within this scope, this paper focuses on index structures to store, access and delete interval-based time-dependent (temporal) data from very large datasets, in the most efficient way. Index structures for this domain have specific characteristics, given the nature of time and the requirement to index time intervals. This work presents an open-source time-efficiency focused variant of the original Interval B+ tree. We designate this variant Improved Interval B+ tree (I2B+ tree). Our contribution adds to the performance of the delete operation by reducing the amount of traversed nodes to access siblings. We performed an extensive analysis of insert, range queries and deletion operations, using multiple datasets with growing volumes of data, distinct temporal distributions and tree parameters (time-split and node order). Results of the experiments validate the logarithmic performance of these operations and propose the best-observed tree parameter ranges.