| Home > Publications > Reports > Informatics (CW) |
CW 301
J. Ramon and M. Bruynooghe
A polynomial time computable metric between point sets
Abstract
Measuring the similarity or distance between two sets of points in a metric space is an important problem in machine learning and has also applications in other disciplines e.g. in computational geometry, philosophy of science, methods for updating or changing theories, ... . Recently Eiter and Manilla have proposed a new measure which is computable in polynomial time. However, it is not a distance function in the mathematical sense because it does not satisfy the triangle inequality. We introduce a new measure which is a metric while being computable in polynomial time. We also present a variant which computes a normalised metric and a variant which can associate different weights with different dimensions of the metric space.
report.pdf / mailto: J. Ramon