for queries are then randomly picked. The rest of the dataset (about 1M points) is used for the database.

### Existing methods to be compared

We choose counterpart methods as follows: **Sparse Random Rotation (SRR)**: This is a random method corresponding to our sequence of sparse matrices scheme. The transformation matrix for SRR has the same form as our method (Fig. \[illustration:basic\_rotation\]), whereas there is no sorting and rotation angle for each pair is randomly chosen. The number of basic rotation applied is set to $\lceil \log_2 n \rceil$. **Iterative Quantization (ITQ)**[@Gong2013b]: This is one of the most well-known methods that keeps nearly-state-of-the-art performance for a wide range of data. It is considered as a reasonable performance counterpart for low-dimensional case. **Isotropic Hashing (ISO)**[@Kong2012]: This is the original method that generates orthogonal transformation to make variances completely isotropic. For high-dimensional case ($d \ge 3$), there are generally an infinite number of isotropic states for any variance-covariance matrix. Each isotropic state has different retrieval performance because it differs from others in terms of entropy and higher-order cumulants (non-gaussian effects). It is considered as a counterpart that measures the quality of our isotropic transformation. We use Lift-and-Projection optimization algorithm proposed in [@Kong2012]. 