Exploring the Potential of k^n-tree for Efficient Representation of n-ary Relations

Sebastián Alexis Moraga

doi:10.62370/hbds.v25i2.274490

pdf

Published: Jul 26, 2024

DOI: https://doi.org/10.62370/hbds.v25i2.274490

Keywords:

Compact data structures k^n-tree n-ary relations scalability

Sebastián Alexis Moraga

Asia-Pacific International University

Abstract

The objective of this experimental study was to investigate the scalability of $gif.latex?k^n$ -trees, a compact data structure designed for representing $gif.latex?n$ -ary relations, compared to a baseline based on a plain representation of adjacency lists. A literature review of compact data structures was conducted, focusing on $gif.latex?k^n$ -trees and their potential for efficient $gif.latex?n$ -ary data representation. To assess scalability, experiments comparing $gif.latex?k^n$ -trees performance against the baseline using set intersection as a benchmark were conducted. Results demonstrated superior $gif.latex?k^n$ -trees scalability in terms of time and memory, especially for high-dimensional and clustered datasets. On average, $gif.latex?k^n$ -trees were eight times faster and consumed times less memory than the baseline. The study also analyzed the impact of the order parameter $gif.latex?\kappa$ on performance, revealing a trade-off between space efficiency and query time. This study provides valuable insights into the practical applicability of $gif.latex?k^n$ -trees for managing and querying high-dimensional data.

Issue

Vol. 25 No. 2 (2024): Human Behavior, Development and Society

Section

Research Articles

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Copyright: Asia-Pacific International University reserve exclusive rights to publish, reproduce and distribute the manuscript and all contents therein.

References

Barbay, J., Claude, F., Gagie, T., Navarro, G., & Nekrich, Y. (2014). Efficient fully-compressed sequence representations. Algorithmica, 69(1), 232–268. https://doi.org/10.1007/s00453-012-9726-3

Barbay, J., & Navarro, G. (2013). On compressing permutations and adaptive sorting. Theoretical Computer Science, 513, 109–123. https://doi.org/10.1016/j.tcs.2013.10.019

Benoit, D., Demaine, E. D., Munro, J. I., Raman, R., Raman, V., & Rao, S. S. (2005). Representing trees of higher degree. Algorithmica, 43, 275–292. https://doi.org/10.1007/s00453-004-1146-6

Boldi, P., Rosa, M., Santini, M., & Vigna, S. (2011, March). Layered label propagation: A multiresolution coordinate-free ordering for compressing social networks. In Proceedings of the 20th International Conference on World Wide Web (pp. 587–596). https://doi.org/10.1145/1963405.1963488

Brisaboa, N. R., Ladra, S., & Navarro, G. (2014). Compact representation of web graphs with extended functionality. Information Systems, 39, 152–174. https://doi.org/10.1016/j.is.2013.08.003

Chierichetti, F., Kumar, R., Lattanzi, S., Mitzenmacher, M., Panconesi, A., & Raghavan, P. (2009, June). On compressing social networks. In Proceedings of the 15th ACM SIGKDD International Conference On Knowledge Discovery and Data Mining (pp. 219–228). https://doi.org/10.1145/1557019.1557049

Clark, D. (1997). Compact pat trees [Doctoral dissertation, The University of Waterloo, Canada]. https://uwspace.uwaterloo.ca/bitstream/handle/10012/64/nq21335.pdf

Claude, F., & Ladra, S. (2011, October). Practical representations for web and social graphs. In Proceedings of the 20th ACM International Conference on Information and Knowledge Management (pp. 1185–1190). https://doi.org/10.1145/2063576.2063747

Claude, F., & Navarro, G. (2011). Self-indexed grammar-based compression. Fundamenta Informaticae, 111(3), 313–337. https://dl.acm.org/doi/10.5555/2361502.2361504

de Bernardo, G. (2014). New data structures and algorithms for the efficient management of large spatial datasets [Doctoral dissertation, Universidade da Coruña, Spain]. http://hdl.handle.net/2183/13769

De Bernardo, G., Álvarez-García, S., Brisaboa, N. R., Navarro, G., & Pedreira, O. (2013). Compact querieable representations of raster data. In O. Kurland, M. Lewenstein, & Porat, E. (eds.), String processing and information retrieval. SPIRE 2013. Lecture Notes in Computer Science, vol 8214. Springer, Cham. https://doi.org/10.1007/978-3-319-02432-5_14

Delpratt, O. N., Rahman, N., & Raman, R. (2006). Engineering the LOUDS succinct tree representation. In C. Àlvarez & M. Serna (eds.), Experimental algorithms. WEA 2006. Lecture Notes in Computer Science, vol 4007. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11764298_12

Elias, P. (1975). Universal codeword sets and representations of the integers. IEEE Transactions on Information Theory, 21(2), 194–203. https://doi.org/10.1109/TIT.1975.1055349

Ferragina, P., & Venturini, R. (2007). A simple storage scheme for strings achieving entropy bounds. Theoretical Computer Science, 372(1), 115–121. https://doi.org/10.1016/j.tcs.2006.12.012

Golynski, A., Munro, J. I., & Rao, S. S. (2006, January). Rank/select operations on large alphabets: A tool for text indexing. In SODA (Vol. 6, pp. 368–373). In Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2006, Miami, Florida, USA.

Golynski, A., Raman, R., & Rao, S. S. (2008, July). On the redundancy of succinct data structures. In J. Gudmundsson (eds.) Algorithm theory – SWAT 2008. SWAT 2008. Lecture Notes in Computer Science, vol 5124. Springer, Berlin, Heidelberg. Scandinavian Workshop on Algorithm Theory (pp. 148–159). Springer Berlin Heidelberg. https://doi.org/10.1007/978-3-540-69903-3_15

Grabowski, S., & Bieniecki, W. (2014). Tight and simple web graph compression for forward and reverse neighbor queries. Discrete Applied Mathematics, 163, 298–306. https://doi.org/10.1016/j.dam.2013.05.028

Grossi, R., Gupta, A., & Vitter, J. S. (2003). High-order entropy-compressed text indexes. In Proceedings of SODA '03: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms. https://dl.acm.org/doi/10.5555/644108.644250

Grossi, R., Orlandi, A., & Raman, R. (2010). Optimal trade-offs for succinct string indexes. In Automata, Languages and Programming: 37th International Colloquium, ICALP 2010, Bordeaux, France, July 6-10, 2010, Proceedings, Part I 37 (pp. 678–689). Springer Berlin Heidelberg. https://doi.org/10.1007/978-3-642-14165-2_57

Hernández, C., & Navarro, G. (2014). Compressed representations for web and social graphs. Knowledge and Information Systems, 40(2), 279–313. https://doi.org/10.1007/s10115-013-0648-4

Jacobson, G. (1989, October). Space-efficient static trees and graphs. In Proceedings of the 30th Annual Symposium on Foundations of Computer Science (pp. 549–554). IEEE Computer Society. http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=63533

Maserrat, H., & Pei, J. (2010, July). Neighbor query friendly compression of social networks. In Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (pp. 533–542). https://doi.org/10.1145/1835804.1835873

Munro, J. I., & Raman, V. (2001). Succinct representation of balanced parentheses and static trees. SIAM Journal on Computing, 31(3), 762–776. https://doi.org/10.1137/S0097539799364092

Navarro, G. (2016). Compact data structures: A practical approach. Cambridge University Press.

Pagh, R. (2001). Low redundancy in static dictionaries with constant query time. SIAM Journal on Computing, 31(2), 353–363. https://doi.org/10.1137/S0097539700369909

Quijada-Fuentes, C., Penabad, M. R., Ladra, S., & Gutiérrez, G. (2019). Set operations over compressed binary relations. Information Systems, 80, 76–90. https://doi.org/10.1016/j.is.2018.10.001

Raman, R., Raman, V., & Satti, S. R. (2007). Succinct indexable dictionaries with applications to encoding k-ary trees, prefix sums and multisets. ACM Transactions on Algorithms (TALG), 3(4), 43–es. https://doi.org/10.1145/1290672.1290680

Article Sidebar

Main Article Content

Abstract

Article Details

References