Electrotechnical and Computer Engineering
Vol. 37 No. 09 (2022): Proceedings of Faculty of Technical Sciences
ANALYSIS AND COMPARISON OF K-D TREE AND BALL TREE PERFORMANCES AS SPATIAL DATA STRUCTURES IN TWO-DIMENSIONAL SPACE
Abstract
Because of the constant increase in the amount of data sets, processing and accessing specific data in large data sets becomes more complicated. A special case are data that require processing in multidimensional space. This paper presents two spatial data structures that can be used for storage, efficient access and processing of large data sets in multiple dimensions. In this paper k-d tree and ball tree, advanced data structures, with their properties are presented. Also, their performances have been analyzed and the results of the comparision have been shown.
References
[1] J. L. Bentley, “Multidimensional binary search trees used for associative searching,” Commun. ACM, vol. 18, no. 9, p. 509–517, Sep. 1975.
[2] R. A. Finkel and J. L. Bentley, “Quad trees a data structure for retrieval on composite keys,” Acta Informatica, vol. 4, no. 1, pp. 1–9, 1974.
[3] S. M. Omohundro, “Five balltree construction algorithms“, International Computer Science Institute Berkeley, 1989.
[4] A. Beygelzimer, S. Kakade, and J. Langford, “Cover trees for nearest neighbor,” Proceedings of the 23rd international conference on Machine learning, pp. 97–104, 2006.
[5] A. Guttman, “R-trees: A dynamic index structure for spatial searching,” Proceedings of the ACM SIGMOD international conference on Management of data, pp. 47–57, 1984.
[6] A.W. Moore, “An intoductory tutorial on kd-trees“, Technical Report No. 209, Computer Laboratory, University of Cambridge, 1991.