Abstract

We introduce cKd-tree, a compact data structure designed to represent a Kd-tree index efficiently. The structure cKd-tree is essentially an encoding of the spiral code sequence of points within an implicit Kdtree (iKd-tree) using Directly Addressable Codes (DACs). The unique feature of cKd-tree lies in its ability to perform spiral encoding and decoding of points by relying solely on knowledge of their parent points within the iKd-tree. This inherent property, combined with DACs’ direct access capability to sequence elements, enables cKd-tree to traverse and explore the tree while decoding only the nodes relevant to queries. We compare cKd-tree with iKd-tree and ???? 2-tree data structures evaluating compression efficiency and execution time of point queries and the range queries. cKd-tree achieves a compression ratio comparable to that of ????2-tree, approximately 70%, demonstrating heightened efficiency, particularly in scenarios characterized by sparse data. Additionally, ???? 2-tree exhibits superior performance in querying individual points, whereas cKd-tree outperforms in the context of aggregate data queries, such as range queries.