ANALIZA I POREĐENJE PERFORMANSI K-D STABLA I LOPTASTOG STABLA KAO PROSTORNIH STRUKTURA PODATAKA U DVODIMENZIONALNOM PROSTORU
Ključne reči:
binarno stablo, k-d stablo, loptasto stablo, metod k-najbližih suseda
Apstrakt
Sa konstantnim povećanjem skupova podataka, proces obrade i pristupa konkretnim podacima se komplikuje. Poseban slučaj predstavljaju podaci koji zahtevaju obradu u višedimenzionalnom prostoru. U ovom radu su prikazane dve prostorne strukture podataka koje služe za skladištenje, efikasan pristup i obradu velikih skupova podataka u više dimenzija. Predstavljene su napredne strukture podataka: k-d stablo i loptasto stablo, analizirane su njihove osobine i performanse i prikazani su rezultati o uspešnosti jedne u odnosu na drugu.
Reference
[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.
Objavljeno
2022-09-07
Sekcija
Elektrotehničko i računarsko inženjerstvo
