Proposal of Effective Orthogonal and Hexagonal Hierarchical Structures for Disc Queries
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F61989100%3A27240%2F18%3A10242620" target="_blank" >RIV/61989100:27240/18:10242620 - isvavai.cz</a>
Result on the web
<a href="https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=8779924" target="_blank" >https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=8779924</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1109/CRC.2018.00013" target="_blank" >10.1109/CRC.2018.00013</a>
Alternative languages
Result language
angličtina
Original language name
Proposal of Effective Orthogonal and Hexagonal Hierarchical Structures for Disc Queries
Original language description
The Fixed-Radius Nearest Neighbors (FRNN) query is a common task in scientific areas dealing with multidimensional point clouds (PCs) such as computer graphics, image processing, geographic information systems, machine learning and pattern recognition. We especially focus on 2D points in this paper. The FRNN means search all the points within defined radius for tasks when local properties of data are crucial. As this procedure is time consuming, an effective accelerating structure indexing the points is required. The standard methods are based on the orthogonal grids subdividing the space into uniform cells or hierarchies of orthogonal grids. However, several papers highlight the regular hexagonal grids for their superior theoretical metrics, e.g. better coverage of query discs, uniform distance to all six neighbors or lower number of passed cells. This paper provides a comparison of effectiveness of orthogonal and hexagonal hierarchies and traditional algorithms for FRNN disc queries. To do this, we propose a novel hierarchical method based on the hexagonal space-filling curve called the Node-Gosper curve which defines the hierarchical location of points in the hexagonal grids and their linear order. This method is tested with similar structure based on the orthogonal Z-order curve to show the real features of both approaches in practice. (C) 2018 IEEE.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10200 - Computer and information sciences
Result continuities
Project
—
Continuities
S - Specificky vyzkum na vysokych skolach
Others
Publication year
2018
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Proceedings - 2018 3rd International Conference on Control, Robotics and Cybernetics, CRC 2018
ISBN
978-1-5386-7738-4
ISSN
—
e-ISSN
—
Number of pages
7
Pages from-to
20-26
Publisher name
IEEE
Place of publication
Piscataway
Event location
Penang
Event date
Sep 26, 2018
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—