Colección SciELO Chile

Departamento Gestión de Conocimiento, Monitoreo y Prospección
Consultas o comentarios: productividad@anid.cl
Búsqueda Publicación
Búsqueda por Tema Título, Abstract y Keywords



cKd-tree: A Compact Kd-tree
Indexado
WoS WOS:001173200100001
Scopus SCOPUS_ID:85186848596
DOI 10.1109/ACCESS.2024.3365054
Año 2024
Tipo artículo de investigación

Citas Totales

Autores Afiliación Chile

Instituciones Chile

% Participación
Internacional

Autores
Afiliación Extranjera

Instituciones
Extranjeras


Abstract



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 k(2) -tree data structures. The evaluation metrics include compression efficiency and execution time of queries. cKd-tree achieves a compression ratio comparable to that of k(2) -tree, approximately 70%, demonstrating heightened efficiency, particularly in scenarios characterized by sparse data. Additionally, consistent with expectations, k(2) -tree exhibits superior performance in querying individual points, whereas cKd-tree outperforms in the context of aggregate data queries, such as range queries.

Revista



Revista ISSN
Ieee Access 2169-3536

Métricas Externas



PlumX Altmetric Dimensions

Muestra métricas de impacto externas asociadas a la publicación. Para mayor detalle:

Disciplinas de Investigación



WOS
Computer Science, Information Systems
Telecommunications
Engineering, Electrical & Electronic
Scopus
Materials Science (All)
Computer Science (All)
Engineering (All)
SciELO
Sin Disciplinas

Muestra la distribución de disciplinas para esta publicación.

Publicaciones WoS (Ediciones: ISSHP, ISTP, AHCI, SSCI, SCI), Scopus, SciELO Chile.

Colaboración Institucional



Muestra la distribución de colaboración, tanto nacional como extranjera, generada en esta publicación.


Autores - Afiliación



Ord. Autor Género Institución - País
1 GUTIERREZ-RETAMAL, GILBERT ANTONIO Hombre Universidad del Bío Bío - Chile
2 Torres-Aviles, Rodrigo Hombre Universidad del Bío Bío - Chile
3 CANIUPAN-MARILEO, MONICA ALEJANDRA Mujer Universidad del Bío Bío - Chile

Muestra la afiliación y género (detectado) para los co-autores de la publicación.

Financiamiento



Fuente
Agencia Nacional de Investigacin y Desarrollo de Chile (ANID)

Muestra la fuente de financiamiento declarada en la publicación.

Agradecimientos



Agradecimiento
No Statement Available

Muestra la fuente de financiamiento declarada en la publicación.