Pretraga podataka organiziranih u stablo

undergraduate thesis

• Title (english): Efficient Data Search Organized in Tree
• Author: Tome Radman
• Mentor: Tomislav Pribanić (mentor)
• Committee member: Tomislav Pribanić (predsjednik povjerenstva)
• Committee member: Hrvoje Džapo (član povjerenstva)
• Committee member: Maja Jurišić Bellotti (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2017-07-10, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

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.

Abstract (english)

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.

• Keywords: k-d stablo; octree; pretraživanje najbližeg susjeda
• Keywords (english): k-d tree; octree; nearest neighbour search
• Language: croatian
• URN:NBN: urn:nbn:hr:168:199210
• Study programme: Title: Computing; Study programme type: university; Study level: undergraduate; Academic / professional title: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2019-03-14 00:18:15