Thumbnail
Access Restriction
Subscribed

Author Pincheira, M. ♦ Gutiérrez, G. ♦ Gajardo, L.
Source IEEE Xplore Digital Library
Content type Text
Publisher Institute of Electrical and Electronics Engineers, Inc. (IEEE)
File Format PDF
Copyright Year ©2010
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Measurement ♦ Algorithms ♦ Spatial Database ♦ Clustering algorithms ♦ Data Structures ♦ Data structures ♦ Spatial databases ♦ Closest Pair Query ♦ Partitioning algorithms ♦ Indexes ♦ Proposals ♦ Closest pair query
Abstract In this work, we present an algorithm that finds the closest pair on two data sets, assuming that neither set has an index. A straightforward solution is to build the spatial index on the fly, and then apply algorithms that use such indexes. But if the sets are not used again these techniques are inefficient. Our algorithm considers two steps: First, each set is partitioned into a collection of subsets, or clusters, spatially defined by means of an MBR (Minimum Bounding Rectangle). The second step consists in processing the partitions using a family of metrics defined for the MBRs, as a filter for finding the closest pair. We experimentally compared our proposal with techniques that use indexes and techniques that do not. The results of our experiments shown that our algorithm overcome these techniques on several realist scenarios.
ISBN 9781457700736
ISSN 15224902
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research ♦ Reading
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2010-11-15
Publisher Place Chile
Rights Holder Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Size (in Bytes) 205.91 kB
Page Count 5
Starting Page 178
Ending Page 182


Source: IEEE Xplore Digital Library