On Fuzzy vs. Metric Similarity Search in Complex Databases

0352610 - ÚI 2011 RIV DE eng C - Conference Paper (international conference)
Eckhardt, Alan - Skopal, T. - Vojtáš, Peter
On Fuzzy vs. Metric Similarity Search in Complex Databases.
Flexible Query Answering Systems. Berlin: Springer, 2009 - (Andreasen, T.; Yager, R.; Bulskov, H.; Christiansen, H.; Larsen, H.), s. 64-75. Lecture Notes in Artificial Intelligence, 5822. ISBN 978-3-642-04956-9. ISSN 0302-9743.
[FQAS 2009. International Conference on Flexible Query Answering Systems /8./. Roskilde (DK), 26.10.2009-28.10.2009]
R&D Projects: GA AV ČR 1ET100300517; GA ČR GD201/09/H057
Grant - others:GA ČR(CZ) GA201/09/0683
Institutional research plan: CEZ:AV0Z10300504
Keywords : fuzzy operators * non-metric search * similarity search * indexing
Subject RIV: IN - Informatics, Computer Science

The task of similarity search is widely used in various areas of computing, including multimedia databases, data mining, bioinformatics, social networks, etc. For a long time, the database-oriented applications of similarity search employed the definition of similarity restricted to metric distances. Due to the metric postulates (reflexivity, non-negativity, symmetry and triangle inequality), a metric similarity allows to build a metric index above the database which can be subsequently used for efficient (fast) similarity search. On the other hand, the metric postulates limit the domain experts (providers of the similarity measure) in similarity modeling. In this paper we propose an alternative non-metric method of indexing for efficient similarity search. The requirement on metric is replaced by the requirement on fuzzy similarity satisfying the transitivity property with a tuneable fuzzy conjunctor. We also show a duality between the fuzzy approach and the metric one.
Permanent Link: http://hdl.handle.net/11104/0192083