Publicación:
THE LARGEST EMPTY RECTANGLE CONTAINING ONLY A QUERY OBJECT IN SPATIAL DATABASES

dc.creatorGILBERTO ANTONIO GUTIÉRREZ RETAMAL
dc.date2014
dc.date.accessioned2025-01-10T14:52:10Z
dc.date.available2025-01-10T14:52:10Z
dc.date.issued2014
dc.description.abstractLET S BE A SET OF N POINTS IN A FIXED AXIS-PARALLEL RECTANGLE R?R2, I.E. IN THE TWO-DIMENSIONAL SPACE (2D). ASSUMING THAT THOSE POINTS ARE STORED IN AN R-TREE, THIS PAPER PRESENTS SEVERAL ALGORITHMS FOR FINDING THE EMPTY RECTANGLE IN R WITH THE LARGEST AREA, SIDES PARALLEL TO THE AXES OF THE SPACE, AND CONTAINING ONLY A QUERY POINT Q. THIS POINT CAN NOT BE PART OF S, THAT IS, IT IS NOT STORED IN THE R-TREE. ALL ALGORITHMS FOLLOW THE BASIC IDEA OF DISCARDING PART OF THE POINTS OF S, IN SUCH A WAY THAT THE PROBLEM CAN BE SOLVED ONLY CONSIDERING THE REMAINING POINTS. AS A CONSEQUENCE, THE ALGORITHMS ONLY HAVE TO ACCESS A VERY SMALL PORTION OF THE NODES (DISK BLOCKS) OF THE R-TREE, SAVING MAIN MEMORY RESOURCES AND COMPUTATION TIME. WE PROVIDE FORMAL PROOFS OF THE CORRECTNESS OF OUR ALGORITHMS AND, IN ORDER TO EVALUATE THE PERFORMANCE OF THE ALGORITHMS, WE RUN AN EXTENSIVE SET OF EXPERIMENTS USING SYNTHETIC AND REAL DATA. THE RESULTS HAVE DEMONSTRATED THE EFFICIENCY AND SCALABILITY OF OUR ALGORITHMS FOR DIFFERENT DATASET CONFIGURATIONS.
dc.formatapplication/pdf
dc.identifier.doi10.1007/s10707-013-0178-y
dc.identifier.issn1573-7624
dc.identifier.issn1384-6175
dc.identifier.urihttps://repositorio.ubiobio.cl/handle/123456789/9326
dc.languagespa
dc.publisherGEOINFORMATICA
dc.relation.uri10.1007/s10707-013-0178-y
dc.rightsPUBLICADA
dc.titleTHE LARGEST EMPTY RECTANGLE CONTAINING ONLY A QUERY OBJECT 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