Pretraga podataka organiziranih u stablo

završni rad

• Naslov (engleski): Efficient Data Search Organized in Tree
• Autor: Tome Radman
• Mentor: Tomislav Pribanić (mentor)
• Član povjerenstva: Tomislav Pribanić (predsjednik povjerenstva)
• Član povjerenstva: Hrvoje Džapo (član povjerenstva)
• Član povjerenstva: Maja Jurišić Bellotti (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Fakultet elektrotehnike i računarstva; Zagreb
• Datum i država obrane: 2017-07-10, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

Sažetak

Računalni vid i ostale grane računarske znanosti često se bave obradom podataka o velikom broju točaka. Javlja se potreba za učinkovitom organizacijom točkovnih podataka koja bi omogućila njihovo brže pretraživanje. Strukture podataka razvijene u tu svrhu uglavnom imaju hijerarhijsku organizaciju u obliku stabla.

Od poznatijih takvih struktura vrijedi izdvojiti BSP stablo, \emph{k}-d stablo , quadtree i octree. Sve su zasnovane na principu podjele prostora u kojem se nalazi promatrani skup točaka na podregije te pridruživanju točaka pripadnim podregijama.

Jedan od važnijih problema u kojem se spomenute strukture koriste je pretraživanje najbližeg susjeda, koje se bavi pronalaskom točke iz predodređenog skupa koja je najbliža određenoj točki. Uz korištenje vlastitih programskog ostvarenja struktura \emph{k}-d stablo i octree pokazuje se da hijerarhijska organizacija točkovnih podataka znatno poboljšava izvedbu pretraživanja najbližeg susjeda.

Sažetak (engleski)

Computer vision, along with other branches of computer science, often deals with processing point data, which causes a need for efficient organization of points which would allow faster searching. Data structures developed for this purpose commonly have a hierarchical organization in shape of a tree.

BSP tree, \emph{k}-d tree, quadtree and octree are among the well-known such structures. They are all based on the principle of recursive subdivision of point space and placing points into correspondent regions.

Nearest neighbour search is one of the notable problems which uses mentioned structures. The problem deals with finding a point in a predetermined set which is nearest to the given query point. It is determined, using self-implemented \emph{k}-d tree and octree, that hierarchical organization significantly improves nearest neighbour search.

• Ključne riječi: k-d stablo; octree; pretraživanje najbližeg susjeda
• Ključne riječi (engleski): k-d tree; octree; nearest neighbour search
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:199210
• Studijski program: Naziv: Računarstvo; Vrsta studija: sveučilišni; Stupanj studija: preddiplomski; Akademski / stručni naziv: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (univ.bacc.ing.comp.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Zatvoreni pristup
• Datum i vrijeme pohrane: 2019-03-14 00:18:15