Abstract

Random projection (RP) is a common technique for dimensionality reduction under $L_2$ norm for which many significant space embedding results have been demonstrated. However, many similarity search applications often require very low dimension embeddings in order to reduce overhead and boost performance. For example, a good 1D embedding can enable complex queries over standard distributed hash tables.

Inspired by the use of symmetric probability distributions in previous work, we propose a novel RP algorithm, Beta Random Projection, and give its probabilistic analyses based on Beta and Gaussian approximations. We evaluate the algorithm in terms of standard similarity metrics with other RP algorithms as well as the singular value decomposition (SVD). Our experimental results show that BRP preserves both similarity metrics well and, under various dataset types including random point sets, text (TREC5) and images, provides sharper and consistent performance.