A Hierarchical Grid Index (HGI), spatial queries in wireless data broadcasting

Kwangjin Park 1 Patrick Valduriez 2
2 ZENITH - Scientific Data Management
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier, CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : The main requirements for spatial query processing via mobile terminals include rapid and accurate searching and low energy consumption. Most location-based services (LBSs) are provided using an on-demand method, which is suitable for light-loaded systems where contention for wireless channels and server processing is not severe. However, as the number of users of LBSs increases, performance deteriorates rapidly since the servers' capability to process queries is limited. Furthermore, the response time of a query may significantly increase with the concentration of users' queries in a server at the same time. That is because the server has to check the locations of users and potential objects for the final result and then individually send answers to clients via a point-to-point channel. At this time, an inefficient structure of spatial index and searching algorithm may incur an extremely large access latency. To address this problem, we propose the Hierarchical Grid Index (HGI), which provides a light-weight sequential location-based index structure for efficient LBSs. We minimize the index size through the use of hierarchical location-based identifications. And we support efficient query processing in broadcasting environments through sequential data transfer and search based on the object locations. We also propose Top-Down Search and Reduction-Counter Search algorithms for efficient searching and query processing. HGI has a simple structure through elimination of replication pointers and is therefore suitable for broadcasting environments with one-dimensional characteristics, thus enabling rapid and accurate spatial search by reducing redundant data. Our performance evaluation shows that our proposed index and algorithms are accurate and fast and support efficient spatial query processing.
Type de document :
Article dans une revue
Distributed and Parallel Databases, Springer, 2013, 31 (3), pp.413-446. 〈http://link.springer.com/article/10.1007%2Fs10619-013-7121-y〉. 〈10.1007/s10619-013-7121-y〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00797095
Contributeur : Patrick Valduriez <>
Soumis le : mardi 5 mars 2013 - 16:33:06
Dernière modification le : samedi 27 janvier 2018 - 01:32:10

Lien texte intégral

Identifiants

Collections

Citation

Kwangjin Park, Patrick Valduriez. A Hierarchical Grid Index (HGI), spatial queries in wireless data broadcasting. Distributed and Parallel Databases, Springer, 2013, 31 (3), pp.413-446. 〈http://link.springer.com/article/10.1007%2Fs10619-013-7121-y〉. 〈10.1007/s10619-013-7121-y〉. 〈lirmm-00797095〉

Partager

Métriques

Consultations de la notice

219