FG Datenbank- und Informationssysteme
Refine
Year of publication
- 2014 (1) (remove)
Document Type
Language
- English (1)
Keywords
- combination of features (1)
- complex query (1)
- filter refinement (1)
- metric indexing (1)
- multi-feature search (1)
- nearest neighbor (1)
Institute
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.