• search hit 2 of 2
Back to Result List

Optimizing the Distance Computation Order of Multi-Feature Similarity Search Indexing

  • Multi-feature search is an effective approach to similarity search. Unfortunately, the search efficiency decreases with the number of features. Several indexing approaches aim to achieve efficiency by incrementally reducing the approximation error of aggregated distance bounds. They apply heuristics to determine the distance computations order and update the object's aggregated bounds after each computation. However, the existing indexing approaches suffer from several drawbacks. They use the same computation order for all objects, do not support important types of aggregation functions and do not take the varying CPU and I/O costs of different distance computations into account. To resolve these problems, we introduce a new heuristic to determine an efficient distance computation order for each individual object. Our heuristic supports various important aggregation functions and calculates cost-benefit-ratios to incorporate the varying computation costs of different distance functions. The experimental evaluation reveals that ourMulti-feature search is an effective approach to similarity search. Unfortunately, the search efficiency decreases with the number of features. Several indexing approaches aim to achieve efficiency by incrementally reducing the approximation error of aggregated distance bounds. They apply heuristics to determine the distance computations order and update the object's aggregated bounds after each computation. However, the existing indexing approaches suffer from several drawbacks. They use the same computation order for all objects, do not support important types of aggregation functions and do not take the varying CPU and I/O costs of different distance computations into account. To resolve these problems, we introduce a new heuristic to determine an efficient distance computation order for each individual object. Our heuristic supports various important aggregation functions and calculates cost-benefit-ratios to incorporate the varying computation costs of different distance functions. The experimental evaluation reveals that our heuristic outperforms state-of-the-art approaches in terms of the number of distance computations as well as search time.show moreshow less

Export metadata

Additional Services

Search Google Scholar
Metadaten
Author: Marcel Zierenberg, Ingo SchmittORCiDGND
URL:http://link.springer.com/chapter/10.1007/978-3-319-25087-8_8
DOI:https://doi.org/10.1007/978-3-319-25087-8_8
ISBN:978-3-319-25087-8
Title of the source (English):Similarity Search and Applications - 8th International Conference, SISAP 2015, Glasgow, UK, October 12-14, 2015, Proceedings
Editor: Giuseppe Amato, Richard Connor, Fabrizio Falchi, Claudio Gennaro
Document Type:Conference Proceeding
Language:English
Year of publication:2015
Tag:combination of features; metric indexing; multi-feature search; nearest neighbor
First Page:90
Last Page:96
Series ; volume number:Lecture Notes in Computer Science ; 9371
Faculty/Chair:Fakultät 1 MINT - Mathematik, Informatik, Physik, Elektro- und Informationstechnik / FG Datenbank- und Informationssysteme
Einverstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.