Open AccessA polynomial time computable metric between point sets
Author(s) -
Jan Ramon,
Maurice Bruynooghe
Publication year - 2001
Publication title -
acta informatica
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.481
H-Index - 40
eISSN - 1432-0525
pISSN - 0001-5903
DOI - 10.1007/pl00013304
Subject(s) - theory of computation , computable function , measure (data warehouse) , metric (unit) , metric space , mathematics , polynomial , time complexity , triangle inequality , point (geometry) , set (abstract data type) , discrete mathematics , function (biology) , similarity (geometry) , algebra over a field , combinatorics , computer science , algorithm , pure mathematics , artificial intelligence , geometry , mathematical analysis , operations management , economics , database , evolutionary biology , image (mathematics) , biology , programming language
Measuring the similarity or distance between 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 Mannila 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 the points in the set.status: publishe
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom