A dynamic balanced quadtree for real-time streaming data

摘要

With the advent of big data, industries and individuals generate a large amount of stream data through various intelligent devices. Stream data arrive gradually over time, unlike historical data. This causes an increasingly unbalanced tree because of the unpredictable data density when an index method such as the classical quadtree is used. To solve this problem, this paper formally defines the quadtree imbalance problem caused by constant stream data density, defines a more reasonable measure to evaluate the balance of a quadtree, and proposes a dynamic balanced quadtree (DB-quadtree) for realtime stream data. Experiments on one synthetic dataset and three real datasets show that the method can improve the balance of the tree.(c) 2023 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/).