A novel indexing scheme for similarity search in metric spaces

•We show that SSS works for symmetrical, balanced distribution.•Our scheme performs robustly for clustered, skewed distributions.•Our scheme performs better than tree-based dynamic structures.•Insertion costs for our scheme is low.•Our scheme selects pivots dynamically using a distribution based pivot promotion.

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.