Publicación:
THE K CLOSEST PAIRS IN SPATIAL DATABASES

Vista sencilla de ítem
dc.creatorGILBERTO ANTONIO GUTIÉRREZ RETAMAL
dc.date2013
dc.date.accessioned2025-01-10T14:52:08Z
dc.date.available2025-01-10T14:52:08Z
dc.date.issued2013
dc.description.abstractWE PROVIDE IN THIS ARTICLE A BRANCH-AND-BOUND ALGORITHM THAT SOLVES THE PROBLEM OF FINDING THE K CLOSEST PAIRS OF POINTS (P,Q), P???P,Q???Q, CONSIDERING TWO SETS OF POINTS IN THE EUCLIDEAN PLANE P,Q STORED IN EXTERNAL MEMORY ASSUMING THAT ONLY ONE OF THE SETS HAS A SPATIAL INDEX. THIS PROBLEM ARISES NATURALLY IN MANY SCENARIOS, FOR INSTANCE WHEN THE SET WITHOUT AN INDEX IS THE ANSWER TO A SPATIAL QUERY. THE MAIN IDEA OF OUR ALGORITHM IS TO PARTITION THE SPACE OCCUPIED BY THE SET WITHOUT AN INDEX INTO SEVERAL CELLS OR SUBSPACES AND TO MAKE USE OF THE PROPERTIES OF A SET OF METRICS DEFINED ON TWO MINIMUM BOUNDING RECTANGLES (MBRS). WE EVALUATED OUR ALGORITHM FOR DIFFERENT VALUES OF K BY MEANS OF A SERIES OF EXPERIMENTS THAT CONSIDERED BOTH SYNTHETICAL AND REAL WORLD DATASETS. WE COMPARED THE PERFORMANCE OF OUR ALGORITHM WITH THAT OF TECHNIQUES THAT EITHER ASSUME THAT BOTH DATASETS HAVE A SPATIAL INDEX OR THAT NONE HAS AN INDEX. THE RESULTS SHOW THAT OUR ALGORITHM NEEDS ONLY BETWEEN A 0.3 AND A 35 % OF THE DISK ACCESSES REQUIRED BY SUCH TECHNIQUES. OUR ALGORITHM ALSO SHOWS A GOOD SCALABILITY, BOTH IN TERMS OF K AND OF THE SIZE OF THE DATA SET.
dc.formatapplication/pdf
dc.identifier.doi10.1007/s10707-012-0169-4
dc.identifier.issn1573-7624
dc.identifier.issn1384-6175
dc.identifier.urihttps://repositorio.ubiobio.cl/handle/123456789/9323
dc.languagespa
dc.publisherGEOINFORMATICA
dc.relation.uri10.1007/s10707-012-0169-4
dc.rightsPUBLICADA
dc.titleTHE K CLOSEST PAIRS IN SPATIAL DATABASES
dc.typeARTÍCULO
dspace.entity.typePublication
ubb.EstadoPUBLICADA
ubb.Otra ReparticionDEPARTAMENTO DE CIENCIAS DE LA COMPUTACION Y TECNOLOGIA DE LA INFORMACION.
ubb.SedeCHILLÁN
Archivos
Colecciones
Artículos científicos