TY - GEN
T1 - 4DHI
T2 - 10th IEEE International Conference on Cloud Engineering, IC2E 2022
AU - Hewage, Chamin Nalinda Lokugam
AU - Vo, Anh Vu
AU - Le-Khac, Nhien An
AU - Laefer, Debra
AU - Bertolotto, Michela
N1 - Publisher Copyright:
© 2022 IEEE.
PY - 2022
Y1 - 2022
N2 - State-of-the-art, scalable, indexing techniques in location-based image data retrieval are primarily focused on supporting window and range queries. However, support of these indexes is not well explored when there are multiple spatially similar images to retrieve for a given geographic location. Adoption of existing spatial indexes such as the kD-tree pose major scalability impediments. In response, this work proposes a novel scalable, key-value, database oriented, secondary-memory based, spatial index to retrieve the top k most spatially similar images to a given geographic location. The proposed index introduces a 4-dimensional Hilbert index (4DHI). This space filling curve is implemented atop HBase (a key-value database). Experiments performed on both synthetically generated and real world data demonstrate comparable accuracy with MD-HBase (a state of the art, scalable, multidimensional point data management system) and better performance. Specifically, 4DHI yielded 34% - 39% storage improvements compared to the disk consumption of the original index of MD-HBase. The compactness in 4DHI also yielded up to 3.4 and 4.7 fold gains when retrieving 6400 and 12800 neighbours, respectively; compared to the adoption of original index of MD-HBase for respective neighbour searches. An optimization technique termed 'Bounding Box Displacement' (BBD) is introduced to improve the accuracy of the top k approximations in relation to the results of in-memory kD-tree. Finally, a method of reducing row key length is also discussed for the proposed 4DHI to further improve the storage efficiency and scalability in managing large numbers of remotely sensed images.
AB - State-of-the-art, scalable, indexing techniques in location-based image data retrieval are primarily focused on supporting window and range queries. However, support of these indexes is not well explored when there are multiple spatially similar images to retrieve for a given geographic location. Adoption of existing spatial indexes such as the kD-tree pose major scalability impediments. In response, this work proposes a novel scalable, key-value, database oriented, secondary-memory based, spatial index to retrieve the top k most spatially similar images to a given geographic location. The proposed index introduces a 4-dimensional Hilbert index (4DHI). This space filling curve is implemented atop HBase (a key-value database). Experiments performed on both synthetically generated and real world data demonstrate comparable accuracy with MD-HBase (a state of the art, scalable, multidimensional point data management system) and better performance. Specifically, 4DHI yielded 34% - 39% storage improvements compared to the disk consumption of the original index of MD-HBase. The compactness in 4DHI also yielded up to 3.4 and 4.7 fold gains when retrieving 6400 and 12800 neighbours, respectively; compared to the adoption of original index of MD-HBase for respective neighbour searches. An optimization technique termed 'Bounding Box Displacement' (BBD) is introduced to improve the accuracy of the top k approximations in relation to the results of in-memory kD-tree. Finally, a method of reducing row key length is also discussed for the proposed 4DHI to further improve the storage efficiency and scalability in managing large numbers of remotely sensed images.
KW - approximate k nearest neighbor search
KW - key-value databases
KW - remotely sensed images
KW - scalability
UR - http://www.scopus.com/inward/record.url?scp=85143164735&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85143164735&partnerID=8YFLogxK
U2 - 10.1109/IC2E55432.2022.00025
DO - 10.1109/IC2E55432.2022.00025
M3 - Conference contribution
AN - SCOPUS:85143164735
T3 - Proceedings - 2022 IEEE International Conference on Cloud Engineering, IC2E 2022
SP - 170
EP - 181
BT - Proceedings - 2022 IEEE International Conference on Cloud Engineering, IC2E 2022
PB - Institute of Electrical and Electronics Engineers Inc.
Y2 - 26 September 2022 through 30 September 2022
ER -