ANALYSIS AND COMPARISON OF K-D TREE AND BALL TREE PERFORMANCES AS SPATIAL DATA STRUCTURES IN TWO-DIMENSIONAL SPACE
DOI:
https://doi.org/10.24867/19BE10KovacevicKeywords:
binary tree, k-d tree, ball tree, k-nearest neighbours searchAbstract
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.
[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.
Downloads
Published
2022-09-07
Issue
Section
Electrotechnical and Computer Engineering
