Centre de documentation
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]