A novel indexing scheme for similarity search in metric spaces

Sparse spatial selection (SSS) allows insertions of new database objects and dynamically promotes some of the new objects as pivots. In this paper, we argue that SSS has fundamental problems that result in poor query performance for clustered or otherwise skewed distributions. Real datasets have often been observed to show such characteristics. We show that SSS has been optimized to work for a symmetrical, balanced distribution and for a specific radius value. Our main contribution is offering a new pivot promotion scheme that can perform robustly for clustered or skewed distributions. We show that our new indexing scheme performs significantly better than tree based dynamic structures while having lower insertion costs. (C) 2015 Elsevier B.V. All rights reserved.