Show simple item record

dc.contributor.authorRoumelis, George
dc.contributor.authorCorral Liria, Antonio Leopoldo
dc.contributor.authorVassilakopoulos, Michael
dc.contributor.authorManolopoulos, Yannis
dc.date.accessioned2017-11-08T08:34:11Z
dc.date.available2017-11-08T08:34:11Z
dc.date.issued2016
dc.identifier.issn1384-6175
dc.identifier.urihttp://hdl.handle.net/10835/5276
dc.description.abstractEfficient and effective processing of the distance-based join query (DJQ) is of great importance in spatial databases due to the wide area of applications that may address such queries (mapping, urban planning, transportation planning, resource management, etc.). The most representative and studied DJQs are the K Closest Pairs Query (KCPQ) and εDistance Join Query (εDJQ). These spatial queries involve two spatial data sets and a distance function to measure the degree of closeness, along with a given number of pairs in the final result (K) or a distance threshold (ε). In this paper, we propose four new plane-sweep-based algorithms for KCPQs and their extensions for εDJQs in the context of spatial databases, without the use of an index for any of the two disk-resident data sets (since, building and using indexes is not always in favor of processing performance). They employ a combination of plane-sweep algorithms and space partitioning techniques to join the data sets. Finally, we present results of an extensive experimental study, that compares the efficiency and effectiveness of the proposed algorithms for KCPQs and εDJQs. This performance study, conducted on medium and big spatial data sets (real and synthetic) validates that the proposed plane-sweep-based algorithms are very promising in terms of both efficient and effective measures, when neither inputs are indexed. Moreover, the best of the new algorithms is experimentally compared to the best algorithm that is based on the R-tree (a widely accepted access method), for KCPQs and εDJQs, using the same data sets. This comparison shows that the new algorithms outperform R-tree based algorithms, in most cases.es_ES
dc.language.isoeses_ES
dc.relationinfo:eu-repo/grantAgreement/ES/MINECO/TIN2013-41576-R/ES/Evolución de sistemas dinámicos en la nube: Un escenario marco hacia las interfaces de usuario inteligentes/ESDNEMIUIes_ES
dc.rightsAttribution-NonCommercial-NoDerivatives 4.0 Internacional*
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/4.0/*
dc.sourceGeoInformatica (on line), 2016, pp. 1-58es_ES
dc.titleNew Plane-Sweep Algorithms for Distance-Based Join Queries in Spatial Databaseses_ES
dc.typeinfo:eu-repo/semantics/articlees_ES
dc.rights.accessRightsinfo:eu-repo/semantics/openAccesses_ES
dc.identifier.doihttp://doi.org/10.1007/s10707-016-0246-1
dc.relation.projectIDTIN2013-41576-Res_ES


Files in this item

This item appears in the following Collection(s)

Show simple item record

Attribution-NonCommercial-NoDerivatives 4.0 Internacional
Except where otherwise noted, this item's license is described as Attribution-NonCommercial-NoDerivatives 4.0 Internacional