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]

Algorithms for constrained k-nearest neighbor queries over moving object trajectories / Yunjun Gao in Geoinformatica, vol 14 n° 2 (April 2010)  

Public [article]  inGeoinformatica > vol 14 n° 2 (April 2010) . - pp 241 - 276 Titre : Algorithms for constrained k-nearest neighbor queries over moving object trajectories Type de document : Article/Communication Auteurs : Yunjun Gao, Auteur ; B. Zheng, Auteur ; G. Chen, Auteur ; Qi Li, Auteur Année de publication : 2010 Article en page(s) : pp 241 - 276 Note générale : Bibliographie Langues : Anglais (eng) Descripteur : [Vedettes matières IGN] Bases de données localisées [Termes IGN] arbre-R [Termes IGN] base de données d'objets mobiles [Termes IGN] base de données spatiotemporelles [Termes IGN] classification barycentrique [Termes IGN] objet mobile [Termes IGN] processus spatial [Termes IGN] programmation par contraintes [Termes IGN] requête spatiale Résumé : (Auteur) An important query for spatio-temporal databases is to find nearest trajectories of moving objects. Existing work on this topic focuses on the closest trajectories in the whole data space. In this paper, we introduce and solve constrained k-nearest neighbor (CkNN) queries and historical continuous CkNN (HCCkNN) queries on R-tree-like structures storing historical information about moving object trajectories. Given a trajectory set D, a query object (point or trajectory) q, a temporal extent T, and a constrained region CR, (i) a CkNN query over trajectories retrieves from D within T, the k (? 1) trajectories that lie closest to q and intersect (or are enclosed by) CR; and (ii) an HCCkNN query on trajectories retrieves the constrained k nearest neighbors (CkNNs) of q at any time instance of T. We propose a suite of algorithms for processing CkNN queries and HCCkNN queries respectively, with different properties and advantages. In particular, we thoroughly investigate two types of CkNN queries, i.e., CkNNP and CkNNT, which are defined with respect to stationary query points and moving query trajectories, respectively; and two types of HCCkNN queries, namely, HCCkNNP and HCCkNNT, which are continuous counterparts of CkNNP and CkNNT, respectively. Our methods utilize an existing data-partitioning index for trajectory data (i.e., TB-tree) to achieve low I/O and CPU cost. Extensive experiments with both real and synthetic datasets demonstrate the performance of the proposed algorithms in terms of efficiency and scalability. Copyright Springer Numéro de notice : A2010-067 Affiliation des auteurs : non IGN Thématique : GEOMATIQUE/INFORMATIQUE Nature : Article DOI : 10.1007/s10707-009-0084-5 Date de publication en ligne : 28/04/2009 En ligne : https://doi.org/10.1007/s10707-009-0084-5 Format de la ressource électronique : URL article Permalink : https://documentation.ensg.eu/index.php?lvl=notice_display&id=30263 [article]

Exemplaires(1)

Code-barres	Cote	Support	Localisation	Section	Disponibilité
057-2010021	RAB	Revue	Centre de documentation	En réserve L003	Disponible