Centre dedocumentation
scientifique

Combined geo-social search : computing top-k join queries over incomplete information / Yaron Kanza in Geoinformatica, vol 22 n° 3 (July 2018)  

Public [article]  inGeoinformatica > vol 22 n° 3 (July 2018) . - pp 615 - 660 Titre : Combined geo-social search : computing top-k join queries over incomplete information Type de document : Article/Communication Auteurs : Yaron Kanza, Auteur ; Mirit Shalem, Auteur Année de publication : 2018 Article en page(s) : pp 615 - 660 Note générale : Bibliographie Langues : Anglais (eng) Descripteur : [Vedettes matières IGN] Bases de données localisées [Termes IGN] approximation [Termes IGN] données localisées [Termes IGN] jointure [Termes IGN] requête spatiale [Termes IGN] réseau social Résumé : (Auteur) Geo-social data sets, which fuse the social and the geospatial facets of data, are vibrant data sources that associate people and activities with locations. In a combined geo-social search, several search queries are posed over geospatial and social data sources, or over data sources with both geospatial and social facets; and the search results, provided as ranked lists of items, are integrated by associating matching items, yielding combinations. Each combination has a score which is a function of the scores of the items it comprises, and the goal is to compute the k combinations with the highest score, that is, the top-k combinations. However, since geo-social data sources are heterogeneous, data items may not have matching items in all the ranked lists. Such items cannot be included in complete combinations. Hence, we study the approach where combinations are padded by nulls for missing items, as in outer-join. A combination is maximal if it cannot be extended by replacing a null by an item. We show that if some of the top-k maximal combinations contain null values, the computation requires reading entire lists, and hence, traditional top-k algorithms and optimization techniques are not as effective as in the case of an ordinary top-k join. Thus, we present two novel algorithms for computing the top-k maximal combinations. One novel algorithm is instance optimal over the class of algorithms that compute a ??approximation to the answer. The second algorithm is more efficient than the modification of two common top-k algorithms to compute maximal combinations. We show this analytically, and experimentally over real and synthetic data. Numéro de notice : A2018-370 Affiliation des auteurs : non IGN Thématique : GEOMATIQUE Nature : Article nature-HAL : ArtAvecCL-RevueIntern DOI : 10.1007/s10707-017-0297-y Date de publication en ligne : 25/03/2017 En ligne : https://doi.org/10.1007/s10707-017-0297-y Format de la ressource électronique : URL article Permalink : https://documentation.ensg.eu/index.php?lvl=notice_display&id=90762 [article]

A dilution-matching-encoding compaction of trajectories over road networks / Ranit Gotsman in Geoinformatica, vol 19 n° 2 (April - June 2015)  

Public [article]  inGeoinformatica > vol 19 n° 2 (April - June 2015) . - pp 331-364 Titre : A dilution-matching-encoding compaction of trajectories over road networks Type de document : Article/Communication Auteurs : Ranit Gotsman, Auteur ; Yaron Kanza, Auteur Année de publication : 2015 Article en page(s) : pp 331-364 Note générale : bibliographie Langues : Anglais (eng) Descripteur : [Vedettes matières IGN] Géomatique web [Termes IGN] calcul d'itinéraire [Termes IGN] chemin le plus court, algorithme du [Termes IGN] géocodage [Termes IGN] noeud [Termes IGN] positionnement par GPS [Termes IGN] réseau routier [Termes IGN] stockage de données [Termes IGN] vectorisation Résumé : (auteur) Many devices nowadays record traveled routes as sequences of GPS locations. With the growing popularity of smartphones, millions of such routes are generated each day, and many routes have to be stored locally on the device or transmitted to a remote database. It is, thus, essential to encode the sequences, in order to decrease the volume of the stored or transmitted data. In this paper we study the problem of encoding routes over a vectorial road network (map), where GPS locations can be associated with vertices or with road segments. We consider a three-step process of dilution, map-matching and coding, which helps reducing the amount of transmitted data between the cellular device and remote servers. We present two methods to code routes. The first method represents the given route as a sequence of greedy paths. We provide two algorithms to generate a greedy-path code for a sequence of n vertices on the map. The first algorithm has O(n) time complexity, and the second one has O(n 2) time complexity, but it is optimal, meaning that it generates the shortest possible greedy-path code. Decoding a greedy-path code can be done in O(n) time. The second method encodes a route as a sequence of shortest paths. We provide algorithms to generate unidirectional and bidirectional optimal shortest-path codes. Encoding and decoding a shortest-path code can be done in O(k n 2 logn) time, where k is the length of the produced code, assuming the graph valency is bounded. Our experimental evaluation shows that shortest-path codes are more compact than greedy-path codes, justifying the larger time complexity. Numéro de notice : A2015-491 Affiliation des auteurs : non IGN Thématique : GEOMATIQUE Nature : Article DOI : 10.1007/s10707-014-0216-4 Date de publication en ligne : 11/08/2014 En ligne : https://doi.org/10.1007/s10707-014-0216-4 Format de la ressource électronique : URL article Permalink : https://documentation.ensg.eu/index.php?lvl=notice_display&id=77284 [article]

TARS: traffic-aware route search / Roy Levin in Geoinformatica, vol 18 n° 3 (July 2014)  

Public [article]  inGeoinformatica > vol 18 n° 3 (July 2014) . - pp 461-500 Titre : TARS: traffic-aware route search Type de document : Article/Communication Auteurs : Roy Levin, Auteur ; Yaron Kanza, Auteur Année de publication : 2014 Article en page(s) : pp 461-500 Note générale : Bibliographie Langues : Anglais (eng) Descripteur : [Vedettes matières IGN] Navigation et positionnement [Termes IGN] méthode heuristique [Termes IGN] navigation automobile [Termes IGN] requête spatiale [Termes IGN] système d'information géographique [Termes IGN] trafic routier Résumé : (Auteur) In a traffic-aware route search (TARS), the user provides start and target locations and sets of search terms. The goal is to find the fastest route from the start location to the target via geographic entities (points of interest) that correspond to the search terms, while taking into account variations in the travel speed due to changes in traffic conditions, and the possibility that some visited entities will not satisfy the search requirements. A TARS query may include temporal constraints and order constraints that restrict the order by which entities are visited. Since TARS generalizes the Traveling-Salesperson Problem, it is an NP-hard problem. Thus, it is unlikely to find a polynomial-time algorithm for evaluating TARS queries. Hence, we present in this paper three heuristics to answer TARS queries--a local greedy approach, a global greedy approach and an algorithm that computes a linear approximation to the travel speeds, formulates the problem as a Mixed Integer Linear Programming (MILP) problem and uses a solver to find a solution. We provide an experimental evaluation based on actual traffic data and show that using a MILP solver to find a solution is effective and can be done within a limited running time in many real-life scenarios. The local-greedy approach is the least effective in finding a fast route, however, it has the best running time and it is the most scalable. Numéro de notice : A2014-498 Affiliation des auteurs : non IGN Thématique : POSITIONNEMENT Nature : Article DOI : 10.1007/s10707-013-0185-z Date de publication en ligne : 07/07/2013 En ligne : https://doi.org/10.1007/s10707-013-0185-z Format de la ressource électronique : URL article Permalink : https://documentation.ensg.eu/index.php?lvl=notice_display&id=74090 [article]

Réservation

Réserver ce document

Exemplaires (1)

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

Location-based algorithms for finding sets of corresponding objects over several geo-spatial data sets / E. Safra in International journal of geographical information science IJGIS, vol 24 n°1-2 (january 2010)  

Public [article]  inInternational journal of geographical information science IJGIS > vol 24 n°1-2 (january 2010) . - pp 69 - 106 Titre : Location-based algorithms for finding sets of corresponding objects over several geo-spatial data sets Type de document : Article/Communication Auteurs : E. Safra, Auteur ; Yaron Kanza, Auteur ; Y. Sagiv, Auteur ; et al., Auteur Année de publication : 2010 Article en page(s) : pp 69 - 106 Note générale : Bibliographie Langues : Anglais (eng) Descripteur : [Vedettes matières IGN] Bases de données localisées [Termes IGN] analyse comparative [Termes IGN] classification barycentrique [Termes IGN] imprécision géométrique [Termes IGN] intégration de données [Termes IGN] jeu de données localisées [Termes IGN] jointure spatiale [Termes IGN] objet géographique Résumé : (Auteur) When integrating geo-spatial data sets, a join algorithm is used for finding sets of corresponding objects (i.e., objects that represent the same real-world entity). This article investigates location-based join algorithms for integration of several data sets. First, algorithms for integration of two data sets are presented and their performances, in terms of recall and precision, are compared. Then, two approaches for integration of more than two data sets are described. In one approach, all the integrated data sets are processed simultaneously. In the second approach, a join algorithm for two data sets is applied sequentially, either in a serial manner, where in each join at least one of the joined data sets is a single source, or in a hierarchical manner, where two join results can be joined. For the two approaches, join algorithms are given. The algorithms are designed to perform well even when location of objects are imprecise and each data set represents only some of the real-world entities. Results of extensive experiments with the different approaches are provided and analyzed. The experiments show the differences, in accuracy and efficiency, between the approaches, under different circumstances. The results also show that all our algorithms have much better accuracy than applying the commonly used one-sided nearest-neighbor join. Copyright Taylor & Francis Numéro de notice : A2010-113 Affiliation des auteurs : non IGN Thématique : GEOMATIQUE/INFORMATIQUE Nature : Article DOI : 10.1080/13658810802275560 En ligne : http://dx.doi.org/10.1080/13658810802275560 Format de la ressource électronique : URL article Permalink : https://documentation.ensg.eu/index.php?lvl=notice_display&id=30309 [article]

Réservation

Réserver ce document

Exemplaires (2)

Code-barres	Cote	Support	Localisation	Section	Disponibilité
079-2010012	RAB	Revue	Centre de documentation	En réserve L003	Disponible
079-2010011	RAB	Revue	Centre de documentation	En réserve L003	Disponible