R-Train+: A dynamic structure for high-dimensional data

摘要

In this paper, we present a new structure for searching large amounts of points and spatial data in high dimensional space. An analysis shows that index structures such as the R-trees or R*-tree are not adequate for high-dimensional data sets. The major problem of R-tree-based index structures is the time complexity that is even unacceptable in worst case scenarios, as the time of searching is dependent on the depth of the tree which increases with growing dimensions and data. To avoid this problem, we introduce a new way to organise points and spatial objects with reduced time complexity. This organized structure will also keep a time dimension as mandatory to keep track of historical movements of objects. Hence enhance its applicability exponentially. The data structure R-Train accepts a greater responsibility to outperform the already known structures to handle multidimensional space.