Hierarchical Hexagonal Clustering and Indexing
Space-filling curves (SFCs) represent an efficient and straightforward method for sparse-space indexing to transform an <i>n</i>-dimensional space into a one-dimensional representation. This is often applied for multidimensional point indexing which brings a better perspective for data a...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2019-05-01
|
| Series: | Symmetry |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2073-8994/11/6/731 |
| _version_ | 1817988064496058368 |
|---|---|
| author | Vojtěch Uher Petr Gajdoš Václav Snášel Yu-Chi Lai Michal Radecký |
| author_facet | Vojtěch Uher Petr Gajdoš Václav Snášel Yu-Chi Lai Michal Radecký |
| author_sort | Vojtěch Uher |
| collection | DOAJ |
| description | Space-filling curves (SFCs) represent an efficient and straightforward method for sparse-space indexing to transform an <i>n</i>-dimensional space into a one-dimensional representation. This is often applied for multidimensional point indexing which brings a better perspective for data analysis, visualization and queries. SFCs are involved in many areas such as big data analysis and visualization, image decomposition, computer graphics and geographic information systems (GISs). The indexing methods subdivide the space into logic clusters of close points and they differ in various parameters including the cluster order, the distance metrics, and the pattern shape. Beside the simple and highly preferred triangular and square uniform grids, the hexagonal uniform grids have gained high interest especially in areas such as GISs, image processing and data visualization for the uniform distance between cells and high effectiveness of circle coverage. While the linearization of hexagons is an obvious approach for memory representation, it seems there is no hexagonal SFC indexing method generally used in practice. The main limitation of hexagons lies in lacking infinite decomposition into sub-hexagons and similarity of tiles on different levels of hierarchy. Our research aims at defining a fast and robust hexagonal SFC method. The Gosper fractal is utilized to preserve the benefits of hexagonal grids and to efficiently and hierarchically linearize points in a hexagonal grid while solving the non-convex shape and recursive transformation issues of the fractal. A comparison to other SFCs and grids is conducted to verify the robustness and effectiveness of our hexagonal method. |
| first_indexed | 2024-04-14T00:29:36Z |
| format | Article |
| id | doaj.art-d5d77db3ca74447c916fe3704688765b |
| institution | Directory Open Access Journal |
| issn | 2073-8994 |
| language | English |
| last_indexed | 2024-04-14T00:29:36Z |
| publishDate | 2019-05-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Symmetry |
| spelling | doaj.art-d5d77db3ca74447c916fe3704688765b2022-12-22T02:22:34ZengMDPI AGSymmetry2073-89942019-05-0111673110.3390/sym11060731sym11060731Hierarchical Hexagonal Clustering and IndexingVojtěch Uher0Petr Gajdoš1Václav Snášel2Yu-Chi Lai3Michal Radecký4Department of Computer Science, VŠB-Technical University of Ostrava, Ostrava-Poruba 708 00, Czech RepublicDepartment of Computer Science, VŠB-Technical University of Ostrava, Ostrava-Poruba 708 00, Czech RepublicDepartment of Computer Science, VŠB-Technical University of Ostrava, Ostrava-Poruba 708 00, Czech RepublicDepartment of Computer Science and Information Engineering, National Taiwan University of Science and Technology, 43, Sec.4, Keelung Rd., Taipei 106, TaiwanDepartment of Computer Science, VŠB-Technical University of Ostrava, Ostrava-Poruba 708 00, Czech RepublicSpace-filling curves (SFCs) represent an efficient and straightforward method for sparse-space indexing to transform an <i>n</i>-dimensional space into a one-dimensional representation. This is often applied for multidimensional point indexing which brings a better perspective for data analysis, visualization and queries. SFCs are involved in many areas such as big data analysis and visualization, image decomposition, computer graphics and geographic information systems (GISs). The indexing methods subdivide the space into logic clusters of close points and they differ in various parameters including the cluster order, the distance metrics, and the pattern shape. Beside the simple and highly preferred triangular and square uniform grids, the hexagonal uniform grids have gained high interest especially in areas such as GISs, image processing and data visualization for the uniform distance between cells and high effectiveness of circle coverage. While the linearization of hexagons is an obvious approach for memory representation, it seems there is no hexagonal SFC indexing method generally used in practice. The main limitation of hexagons lies in lacking infinite decomposition into sub-hexagons and similarity of tiles on different levels of hierarchy. Our research aims at defining a fast and robust hexagonal SFC method. The Gosper fractal is utilized to preserve the benefits of hexagonal grids and to efficiently and hierarchically linearize points in a hexagonal grid while solving the non-convex shape and recursive transformation issues of the fractal. A comparison to other SFCs and grids is conducted to verify the robustness and effectiveness of our hexagonal method.https://www.mdpi.com/2073-8994/11/6/731space-filling curvepoint clusteringGosper curvehexagonal grid |
| spellingShingle | Vojtěch Uher Petr Gajdoš Václav Snášel Yu-Chi Lai Michal Radecký Hierarchical Hexagonal Clustering and Indexing Symmetry space-filling curve point clustering Gosper curve hexagonal grid |
| title | Hierarchical Hexagonal Clustering and Indexing |
| title_full | Hierarchical Hexagonal Clustering and Indexing |
| title_fullStr | Hierarchical Hexagonal Clustering and Indexing |
| title_full_unstemmed | Hierarchical Hexagonal Clustering and Indexing |
| title_short | Hierarchical Hexagonal Clustering and Indexing |
| title_sort | hierarchical hexagonal clustering and indexing |
| topic | space-filling curve point clustering Gosper curve hexagonal grid |
| url | https://www.mdpi.com/2073-8994/11/6/731 |
| work_keys_str_mv | AT vojtechuher hierarchicalhexagonalclusteringandindexing AT petrgajdos hierarchicalhexagonalclusteringandindexing AT vaclavsnasel hierarchicalhexagonalclusteringandindexing AT yuchilai hierarchicalhexagonalclusteringandindexing AT michalradecky hierarchicalhexagonalclusteringandindexing |