1. A computer-implemented method for estimating similarities comprising: receiving, by a computer, a set of data; dividing, by the computer, the set of data into a first subset and a second subset,  wherein the second subset is larger than the first subset; computing, by the computer, similarity calculations for each element of the second subset and the elements of the first subset; computing, by the computer, an approximation matrix from the computed similarity calculations; generating, by the computer, a similarity measure for a query element based on the approximation matrix.