Centre de documentation
scientifique

Uncertain Voronoi cell computation based on space decomposition / Klaus Arthur Schmid in Geoinformatica, vol 21 n° 4 (October - December 2017)  

Public [article]  inGeoinformatica > vol 21 n° 4 (October - December 2017) . - pp 763 -795 Titre : Uncertain Voronoi cell computation based on space decomposition Type de document : Article/Communication Auteurs : Klaus Arthur Schmid, Auteur ; Andreas Züfle, Auteur ; Tobias Emrich, Auteur ; et al., Auteur Année de publication : 2017 Article en page(s) : pp 763 -795 Note générale : Bibliographie Langues : Anglais (eng) Descripteur : [Vedettes matières IGN] Analyse spatiale [Termes IGN] décomposition spatiale [Termes IGN] diagramme de Voronoï [Termes IGN] incertitude des données [Termes IGN] plus proche voisin, algorithme du [Termes IGN] traitement parallèle Résumé : (Auteur) To facilitate (k)-Nearest Neighbor queries, the concept of Voronoi decomposition is widely used. In this work, we propose solutions to extend the concept of Voronoi-cells to uncertain data. Due to data uncertainty, the location, the shape and the extent of a Voronoi cell are random variables. To facilitate reliable query processing despite the presence of uncertainty, we employ the concept of possible-Voronoi cells and introduce the novel concept of guaranteed-Voronoi cells: The possible-Voronoi cell of an object U consists of all points in space that have a non-zero probability of having U as their nearest-neighbor; and the guaranteed-Voronoi cell, which consists of all points in space which must have U as their nearest-neighbor. Since exact computation of both types of Voronoi cells is computationally hard, we propose approximate solutions. Therefore, we employ hierarchical access methods for both data and object space. Our proposed algorithm descends both index structures simultaneously, constantly trying to prune branches in both trees by employing the concept of spatial domination. To support (k)-Nearest Neighbor queries having k > 1, this work further pioneers solutions towards the computation of higher-order possible and higher-order guaranteed Voronoi cells, which consist of all points in space which may (respectively must) have U as one of their k-nearest neighbors. For this purpose, we develop three algorithms to explore our index structures and show that the approach that descends both index structures in parallel yields the fastest query processing times. Our experiments show that we are able to approximate uncertain Voronoi cells of any order much more effectively than the state-of-the-art while improving run-time performance. Since our approach is the first to compute guaranteed-Voronoi cells and higher order (possible and guaranteed) Voronoi cells, we extend the existing state-of-the-art solutions to these concepts, in order to allow a fair experimental evaluation. Numéro de notice : A2017-604 Affiliation des auteurs : non IGN Thématique : GEOMATIQUE Nature : Article DOI : 10.1007/s10707-017-0293-2 En ligne : https://doi.org/10.1007/s10707-017-0293-2 Format de la ressource électronique : URL article Permalink : https://documentation.ensg.eu/index.php?lvl=notice_display&id=86913 [article]

On reverse-k-nearest-neighbor joins / Tobias Emrich in Geoinformatica, vol 19 n° 2 (April - June 2015)  

Public [article]  inGeoinformatica > vol 19 n° 2 (April - June 2015) Titre : On reverse-k-nearest-neighbor joins Type de document : Article/Communication Auteurs : Tobias Emrich, Auteur ; Hans-Peter Kriege, Auteur ; Peer Kröger, Auteur ; et al., Auteur Année de publication : 2015 Note générale : bibliographie Langues : Anglais (eng) Descripteur : [Vedettes matières IGN] Géomatique [Termes IGN] analyse comparative [Termes IGN] classification barycentrique [Termes IGN] espace métrique [Termes IGN] espace vectoriel [Termes IGN] jointure spatiale [Termes IGN] requête (informatique) [Termes IGN] requête spatiale inverse Résumé : (auteur) A reverse k-nearest neighbour (RkNN) query determines the objects from a database that have the query as one of their k-nearest neighbors. Processing such a query has received plenty of attention in research. However, the effect of running multiple RkNN queries at once (join) or within a short time interval (bulk/group query) has only received little attention so far. In this paper, we analyze different types of RkNN joins and provide a classification of existing RkNN join algorithms. We discuss possible solutions for solving the non-trivial variants of the problem in vector spaces, including self and mutual pruning strategies. Further, we generalize the developed algorithms to general metric spaces. During an extensive performance analysis we provide evaluation results showing the IO and CPU performance of the compared algorithms for a wide range of different setups and suggest appropriate query algorithms for specific scenarios. Numéro de notice : A2015-490 Affiliation des auteurs : non IGN Thématique : GEOMATIQUE Nature : Article DOI : 10.1007/s10707-014-0215-5 Date de publication en ligne : 23/08/2014 En ligne : https://doi.org/10.1007/s10707-014-0215-5 Format de la ressource électronique : URL article Permalink : https://documentation.ensg.eu/index.php?lvl=notice_display&id=77283 [article]

Spatial inverse query processing / Thomas Bernecker in Geoinformatica, vol 17 n° 3 (July 2013)  

Public [article]  inGeoinformatica > vol 17 n° 3 (July 2013) . - pp 449 - 487 Titre : Spatial inverse query processing Type de document : Article/Communication Auteurs : Thomas Bernecker, Auteur ; Tobias Emrich, Auteur ; Hans-Peter Kriegel, Auteur ; Nikos Mamoulis, Auteur ; et al., Auteur Année de publication : 2013 Article en page(s) : pp 449 - 487 Note générale : Bibliographie Langues : Anglais (eng) Descripteur : [Vedettes matières IGN] Bases de données localisées [Termes IGN] plus proche voisin, algorithme du [Termes IGN] requête spatiale [Termes IGN] requête spatiale inverse Résumé : (Auteur) Traditional spatial queries return, for a given query object q, all database objects that satisfy a given predicate, such as epsilon range and k-nearest neighbors. This paper defines and studies inverse spatial queries, which, given a subset of database objects Q and a query predicate, return all objects which, if used as query objects with the predicate, contain Q in their result. We first show a straightforward solution for answering inverse spatial queries for any query predicate. Then, we propose a filter-and-refinement framework that can be used to improve efficiency. We show how to apply this framework on a variety of inverse queries, using appropriate space pruning strategies. In particular, we propose solutions for inverse epsilon range queries, inverse k-nearest neighbor queries, and inverse skyline queries. Furthermore, we show how to relax the definition of inverse queries in order to ensure non-empty result sets. Our experiments show that our framework is significantly more efficient than naive approaches. Numéro de notice : A2013-382 Affiliation des auteurs : non IGN Thématique : GEOMATIQUE/INFORMATIQUE Nature : Article DOI : 10.1007/s10707-012-0162-y Date de publication en ligne : 24/08/2012 En ligne : https://doi.org/10.1007/s10707-012-0162-y Format de la ressource électronique : URL article Permalink : https://documentation.ensg.eu/index.php?lvl=notice_display&id=32520 [article]

Exemplaires(1)

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