Gridvoronoi: An Efficient Spatial Index for Nearest Neighbor Query Processing
In this paper, based upon Voronoi Diagram, we propose GridVoronoi which is a novel spatial index that enables users to find the spatial nearest neighbour (NN) from two-dimensional (2D) datasets in almost O(1) time. GridVoronoi augments the Voronoi Diagram with a virtual grid to promptly find out (in...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2019-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/8813059/ |
| _version_ | 1819276259551608832 |
|---|---|
| author | Chongsheng Zhang George Almpanidis Faegheh Hasibi Gaojuan Fan |
| author_facet | Chongsheng Zhang George Almpanidis Faegheh Hasibi Gaojuan Fan |
| author_sort | Chongsheng Zhang |
| collection | DOAJ |
| description | In this paper, based upon Voronoi Diagram, we propose GridVoronoi which is a novel spatial index that enables users to find the spatial nearest neighbour (NN) from two-dimensional (2D) datasets in almost O(1) time. GridVoronoi augments the Voronoi Diagram with a virtual grid to promptly find out (in a geometric space) which Voronoi cell contains the query point. It consists of an off-line data pre-processing phase and an on-line query processing phase. In the off-line phase, the digital geographical space is partitioned with a Voronoi Diagram and a virtual grid, respectively. Next, for each square unit (i.e., grid cell), the corresponding Voronoi cells that contain or intersect with this square are derived and kept in a hashmap-like structure. In the on-line phase, for each real-time spatial NN query, the algorithm first identifies which virtual square(s) contain(s) this query; then looks up the hashmap structure to find the corresponding Voronoi cell(s) for this grid cell and the final result for the query. Overall, GridVoronoi significantly reduces the time complexity in finding spatial NN in 2D space, thus improves the efficiency of real-time spatial NN queries and Location Based Services. |
| first_indexed | 2024-12-23T23:37:23Z |
| format | Article |
| id | doaj.art-339653a36b8e4c3586199f851185de4e |
| institution | Directory Open Access Journal |
| issn | 2169-3536 |
| language | English |
| last_indexed | 2024-12-23T23:37:23Z |
| publishDate | 2019-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj.art-339653a36b8e4c3586199f851185de4e2022-12-21T17:25:49ZengIEEEIEEE Access2169-35362019-01-01712099712101410.1109/ACCESS.2019.29376678813059Gridvoronoi: An Efficient Spatial Index for Nearest Neighbor Query ProcessingChongsheng Zhang0https://orcid.org/0000-0003-1632-7238George Almpanidis1Faegheh Hasibi2Gaojuan Fan3School of Computer and Information Engineering, Henan University, Kaifeng, ChinaSchool of Computer and Information Engineering, Henan University, Kaifeng, ChinaInstitute of Computing and Information Sciences, Radboud University, Nijmegen, The NetherlandsSchool of Computer and Information Engineering, Henan University, Kaifeng, ChinaIn this paper, based upon Voronoi Diagram, we propose GridVoronoi which is a novel spatial index that enables users to find the spatial nearest neighbour (NN) from two-dimensional (2D) datasets in almost O(1) time. GridVoronoi augments the Voronoi Diagram with a virtual grid to promptly find out (in a geometric space) which Voronoi cell contains the query point. It consists of an off-line data pre-processing phase and an on-line query processing phase. In the off-line phase, the digital geographical space is partitioned with a Voronoi Diagram and a virtual grid, respectively. Next, for each square unit (i.e., grid cell), the corresponding Voronoi cells that contain or intersect with this square are derived and kept in a hashmap-like structure. In the on-line phase, for each real-time spatial NN query, the algorithm first identifies which virtual square(s) contain(s) this query; then looks up the hashmap structure to find the corresponding Voronoi cell(s) for this grid cell and the final result for the query. Overall, GridVoronoi significantly reduces the time complexity in finding spatial NN in 2D space, thus improves the efficiency of real-time spatial NN queries and Location Based Services.https://ieeexplore.ieee.org/document/8813059/Geospatial analysisnearest neighbour methodsquery processingspatial databases |
| spellingShingle | Chongsheng Zhang George Almpanidis Faegheh Hasibi Gaojuan Fan Gridvoronoi: An Efficient Spatial Index for Nearest Neighbor Query Processing IEEE Access Geospatial analysis nearest neighbour methods query processing spatial databases |
| title | Gridvoronoi: An Efficient Spatial Index for Nearest Neighbor Query Processing |
| title_full | Gridvoronoi: An Efficient Spatial Index for Nearest Neighbor Query Processing |
| title_fullStr | Gridvoronoi: An Efficient Spatial Index for Nearest Neighbor Query Processing |
| title_full_unstemmed | Gridvoronoi: An Efficient Spatial Index for Nearest Neighbor Query Processing |
| title_short | Gridvoronoi: An Efficient Spatial Index for Nearest Neighbor Query Processing |
| title_sort | gridvoronoi an efficient spatial index for nearest neighbor query processing |
| topic | Geospatial analysis nearest neighbour methods query processing spatial databases |
| url | https://ieeexplore.ieee.org/document/8813059/ |
| work_keys_str_mv | AT chongshengzhang gridvoronoianefficientspatialindexfornearestneighborqueryprocessing AT georgealmpanidis gridvoronoianefficientspatialindexfornearestneighborqueryprocessing AT faeghehhasibi gridvoronoianefficientspatialindexfornearestneighborqueryprocessing AT gaojuanfan gridvoronoianefficientspatialindexfornearestneighborqueryprocessing |