@inproceedings{Zierenberg, author = {Zierenberg, Marcel}, title = {Partial Refinement for Similarity Search with Multiple Features}, series = {Similarity Search and Applications - 7th International Conference, SISAP 2014, Los Cabos, Mexico, October 29-31, 2014, Proceedings}, booktitle = {Similarity Search and Applications - 7th International Conference, SISAP 2014, Los Cabos, Mexico, October 29-31, 2014, Proceedings}, editor = {Traina, Agma Juci Machado and Traina, Caetano and Cordeiro, Robson Leonardo Ferreira}, publisher = {Springer International Publishing}, isbn = {978-3-319-11987-8}, doi = {10.1007/978-3-319-11988-5_2}, pages = {13 -- 24}, abstract = {Filter refinement is an efficient and flexible indexing approach to similarity search with multiple features. However, the conventional refinement phase has one major drawback: when an object is refined, the partial distances to the query object are computed for all features. This frequently leads to more distance computations being executed than necessary to exclude an object. To address this problem, we introduce partial refinement, a simple, yet efficient improvement of the filter refinement approach. It incrementally replaces partial distance bounds with exact partial distances and updates the aggregated bounds accordingly each time. This enables us to exclude many objects before all of their partial distances have been computed exactly. Our experimental evaluation illustrates that partial refinement significantly reduces the number of required distance computations and the overall search time in comparison to conventional refinement and other state-of-the-art techniques.}, language = {en} } @inproceedings{ZierenbergSchmitt, author = {Zierenberg, Marcel and Schmitt, Ingo}, title = {Optimizing the Distance Computation Order of Multi-Feature Similarity Search Indexing}, series = {Similarity Search and Applications - 8th International Conference, SISAP 2015, Glasgow, UK, October 12-14, 2015, Proceedings}, booktitle = {Similarity Search and Applications - 8th International Conference, SISAP 2015, Glasgow, UK, October 12-14, 2015, Proceedings}, editor = {Amato, Giuseppe and Connor, Richard and Falchi, Fabrizio and Gennaro, Claudio}, isbn = {978-3-319-25087-8}, doi = {10.1007/978-3-319-25087-8_8}, pages = {90 -- 96}, abstract = {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 our heuristic outperforms state-of-the-art approaches in terms of the number of distance computations as well as search time.}, language = {en} }