cKd-tree: A Compact Kd-tree
In the context of Big Data scenarios, the presence of extensive static datasets is not uncommon. To facilitate efficient queries on such datasets, the utilization of multiple indexes, such as the Kd-tree, becomes imperative. The current scale of managed points may, however, exceed the capacity of pr...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2024-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/10431741/ |
| _version_ | 1797292021500608512 |
|---|---|
| author | Gilberto Gutierrez Rodrigo Torres-Aviles Monica Caniupan |
| author_facet | Gilberto Gutierrez Rodrigo Torres-Aviles Monica Caniupan |
| author_sort | Gilberto Gutierrez |
| collection | DOAJ |
| description | In the context of Big Data scenarios, the presence of extensive static datasets is not uncommon. To facilitate efficient queries on such datasets, the utilization of multiple indexes, such as the Kd-tree, becomes imperative. The current scale of managed points may, however, exceed the capacity of primary memory, posing a significant challenge. In this article we introduce cKd-tree, a compact data structure designed to represent a Kd-tree efficiently. The structure cKd-tree is essentially an encoding of the spiral code sequence of points within an implicit Kd-tree (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. The article details the algorithms necessary for creating and manipulating a cKd-tree, as well as algorithms for evaluating two fundamental queries over points: the point query and the range query. To assess the performance of cKd-tree, a series of experiments are conducted, comparing it with iKd-tree and <inline-formula> <tex-math notation="LaTeX">$k^{2}$ </tex-math></inline-formula>-tree data structures. The evaluation metrics include compression efficiency and execution time of queries. cKd-tree achieves a compression ratio comparable to that of <inline-formula> <tex-math notation="LaTeX">$k^{2}$ </tex-math></inline-formula>-tree, approximately 70%, demonstrating heightened efficiency, particularly in scenarios characterized by sparse data. Additionally, consistent with expectations, <inline-formula> <tex-math notation="LaTeX">$k^{2}$ </tex-math></inline-formula>-tree exhibits superior performance in querying individual points, whereas cKd-tree outperforms in the context of aggregate data queries, such as range queries. |
| first_indexed | 2024-03-07T19:46:12Z |
| format | Article |
| id | doaj.art-360fed8800a349aa909ed3fbcef93472 |
| institution | Directory Open Access Journal |
| issn | 2169-3536 |
| language | English |
| last_indexed | 2024-03-07T19:46:12Z |
| publishDate | 2024-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj.art-360fed8800a349aa909ed3fbcef934722024-02-29T00:00:41ZengIEEEIEEE Access2169-35362024-01-0112286662867610.1109/ACCESS.2024.336505410431741cKd-tree: A Compact Kd-treeGilberto Gutierrez0https://orcid.org/0000-0001-6059-1453Rodrigo Torres-Aviles1Monica Caniupan2https://orcid.org/0000-0003-1543-2378Departamento de Ciencias de la Computación y Tecnologías de Información, Universidad del Bío-Bío, Chillán, ChileDepartamento de Sistemas de Información, Universidad del Bío-Bío, Chillán, ChileDepartamento de Sistemas de Información, Universidad del Bío-Bío, Chillán, ChileIn the context of Big Data scenarios, the presence of extensive static datasets is not uncommon. To facilitate efficient queries on such datasets, the utilization of multiple indexes, such as the Kd-tree, becomes imperative. The current scale of managed points may, however, exceed the capacity of primary memory, posing a significant challenge. In this article we introduce cKd-tree, a compact data structure designed to represent a Kd-tree efficiently. The structure cKd-tree is essentially an encoding of the spiral code sequence of points within an implicit Kd-tree (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. The article details the algorithms necessary for creating and manipulating a cKd-tree, as well as algorithms for evaluating two fundamental queries over points: the point query and the range query. To assess the performance of cKd-tree, a series of experiments are conducted, comparing it with iKd-tree and <inline-formula> <tex-math notation="LaTeX">$k^{2}$ </tex-math></inline-formula>-tree data structures. The evaluation metrics include compression efficiency and execution time of queries. cKd-tree achieves a compression ratio comparable to that of <inline-formula> <tex-math notation="LaTeX">$k^{2}$ </tex-math></inline-formula>-tree, approximately 70%, demonstrating heightened efficiency, particularly in scenarios characterized by sparse data. Additionally, consistent with expectations, <inline-formula> <tex-math notation="LaTeX">$k^{2}$ </tex-math></inline-formula>-tree exhibits superior performance in querying individual points, whereas cKd-tree outperforms in the context of aggregate data queries, such as range queries.https://ieeexplore.ieee.org/document/10431741/Compressionindicesspatial dataspatial pointsspatial queries |
| spellingShingle | Gilberto Gutierrez Rodrigo Torres-Aviles Monica Caniupan cKd-tree: A Compact Kd-tree IEEE Access Compression indices spatial data spatial points spatial queries |
| title | cKd-tree: A Compact Kd-tree |
| title_full | cKd-tree: A Compact Kd-tree |
| title_fullStr | cKd-tree: A Compact Kd-tree |
| title_full_unstemmed | cKd-tree: A Compact Kd-tree |
| title_short | cKd-tree: A Compact Kd-tree |
| title_sort | ckd tree a compact kd tree |
| topic | Compression indices spatial data spatial points spatial queries |
| url | https://ieeexplore.ieee.org/document/10431741/ |
| work_keys_str_mv | AT gilbertogutierrez ckdtreeacompactkdtree AT rodrigotorresaviles ckdtreeacompactkdtree AT monicacaniupan ckdtreeacompactkdtree |