Centre de documentation
scientifique

Aggregate keyword nearest neighbor queries on road networks / Pengfei Zhang in Geoinformatica, vol 22 n° 2 (April 2018)  

Public [article]  inGeoinformatica > vol 22 n° 2 (April 2018) . - pp 237 - 268 Titre : Aggregate keyword nearest neighbor queries on road networks Type de document : Article/Communication Auteurs : Pengfei Zhang, Auteur ; Huaizhong Lin, Auteur ; Yunjun Gao, Auteur ; Dongming Lu, Auteur Année de publication : 2018 Article en page(s) : pp 237 - 268 Note générale : Bibliographie Langues : Anglais (eng) Descripteur : [Vedettes matières IGN] Systèmes d'information géographique [Termes IGN] langage naturel (informatique) [Termes IGN] plus proche voisin, algorithme du [Termes IGN] point d'intérêt [Termes IGN] requête spatiale [Termes IGN] réseau routier [Termes IGN] système d'information géographique Résumé : (Auteur) Given a group Q of query points and a set P of points of interest (POIs), aggregate nearest neighbor (ANN) queries find a POI p from P that achieves the smallest aggregate distance. Specifically, the aggregate distance is defined over the set of distances between p and all query points in Q$\mathcal {Q}$. Existing studies on ANN query mainly consider the spatial proximity, whereas the textual similarity has received considerable attention recently. In this work, we utilize user-specified query keywords to capture textual similarity. We study the aggregate keyword nearest neighbor (AKNN) queries, finding the POI that has the smallest aggregate distance and covers all query keywords. Nevertheless, existing methods on ANN query are either inapplicable or inefficient when applied to the AKNN query. To answer our query efficiently, we first develop a dual-granularity (DG) indexing schema. It preserves abstracts of the road network by a tree structure, and preserves detailed network information by an extended adjacency list. Then, we propose a minimal first search (MFS) algorithm. It traverses the tree and explores the node with the minimal aggregate distance iteratively. This method suffers from false hits arising from keyword tests. Thus, we propose the collaborative filtering technique, which performs keywords test by multiple keyword bitmaps collectively rather than by only one. Extensive experiments on both real and synthetic datasets demonstrate the superiority of our algorithms and optimizing strategies. Numéro de notice : A2018-364 Affiliation des auteurs : non IGN Thématique : GEOMATIQUE Nature : Article nature-HAL : ArtAvecCL-RevueIntern DOI : 10.1007/s10707-017-0315-0 Date de publication en ligne : 29/12/2017 En ligne : https://doi.org/10.1007/s10707-017-0315-0 Format de la ressource électronique : URL article Permalink : https://documentation.ensg.eu/index.php?lvl=notice_display&id=90726 [article]