1
$\begingroup$

This could relate to different applications, but my application of interest is in similarity-search systems based on high-dimensional feature vectors. In these systems, since search based on Euclidean distance is costly, the vectors are encoded as binary vectors. Then the search is done based on Hamming distance computation which is supposed to be faster than the Euclidean counterpart. My question is, practically, how much is this speed-up for an average architecture?

More formally, suppose we have a database $\mathrm{X} = [\mathbf{x}_1, \cdots, \mathbf{x}_i, \cdots, \mathbf{x}_N]$ of $N$ vectors of dimension $n$, and a vector $\mathbf{y}$ of the same dimensionality. Now imagine two cases:

  • Vectors are real-valued, i.e., $\mathbf{x}_i \in \Re^n$. We are interested in finding the $\mathbf{x}_i$ from $\mathrm{X}$ with the minimum Euclidean distance to $\mathbf{y}$, i.e.:

\begin{equation} i = \underset{{1 \leqslant i \leqslant N}}{\text{argmin}} ||\mathbf{y} - \mathbf{x}_i||_2. \end{equation}

  • Vectors are binary, i.e., $\mathbf{x}_i \in \mathcal{B}^n$ with $\mathcal{B} = \{0,1\}$. We are interested in finding the $\mathbf{x}_i$ from $\mathrm{X}$ with the minimum Hamming distance to $\mathbf{y}$, i.e.:

\begin{equation} i = \underset{{1 \leqslant i \leqslant N}}{\text{argmin}} \sum_{j=1}^n \big( \mathbf{y}(j) \oplus \mathbf{x}_i(j) \big), \end{equation} where $\oplus$ denotes the XOR operation.

Both of these operations have complexity of $\mathcal{O}(Nn)$. However, the real case requires doing the operations in floating-point arithmetic while the binary case enjoys the fixed-point binary operations which are faster.

My question is, in practice, how are these complexities different? Can we say, very roughly though, that they have different constant factors and the ratio of these factors is a constant value? What would that constant value be then? Around 10 or 100 maybe? And how much is it architecture dependent?

$\endgroup$
  • 1
    $\begingroup$ The answer depends on many factors such as the exact architecture, the exact data types, the operation being performed, and so on. I suggest doing some experiments to know what happens in your case. $\endgroup$ – Yuval Filmus Aug 21 '17 at 11:32
  • $\begingroup$ This doesn't seem to be quite in scope here. $\endgroup$ – Yuval Filmus Aug 21 '17 at 11:33
  • $\begingroup$ "practice, how are these complexities different" It's not really clear what this means. The complexities you quote are theoretical: they're based on some machine model and are asymptotic as the size of the input goes to infinity. Complexity theory doesn't operate at the kind of specificity that you're looking for. $\endgroup$ – David Richerby Aug 21 '17 at 12:42
  • $\begingroup$ @DavidRicherby Since it is clear what the complexities are in big-O terms, I guess I was wrong with the "complexity-theory" tag. Well, I just removed it . In fact, my question is very general and I am interested insome practical insights. Of course the answer is going to be architecture-dependent. Nevertheless, I am hoping for a very approximative answer based on some average machine in terms of run-time. $\endgroup$ – Sohrab Aug 21 '17 at 12:57
  • $\begingroup$ @YuvalFilmus Surely yes. It depends on many factors for an exact answer. However, I am just interested in some crude average analyses. My application is in large-scale similarity search setups where direct Euclidean distance computation is replaced with search using Hamming distance on binary codes. I simply want to see how much is this idea speeding up these systems. Do you think I can ask this question some other place? $\endgroup$ – Sohrab Aug 21 '17 at 13:09
1
$\begingroup$

The asymptotic complexity is the same (assuming you treat each floating-point operation as a constant-time operation, which is probably the right assumption). The practical running time may be different. Asymptotics ignores constant factors, but constant factors can be important in practice.

The way to tell how much faster it is in practice is to implement it and do some experiments, i.e., benchmark it on realistic workloads. Asymptotic analysis probably won't be very helpful in this case for predicting how much faster it will be. No one is likely to be able to give you a prediction for what the results of those experiments will be; you'll just have to try it and see.

$\endgroup$
1
$\begingroup$

The asymptotic complexity for the worst case is the same. Actually, the constant factors will be quite close together on a typical modern processor - if you don't calculate the execution time depending on n, but depending on the input size. The size of a vector of n bits is say 64 times less than the size of a vector of n floating point numbers. The execution time for a vectors of n bits will be lower only because 64 bit operations can be calculated simultaneously with one integer operation. So the ratio (execution time) / (input size) will be close.

In practice, the average complexity will be data dependent. As soon as a vector quite close to y is found, you may be able to prove that the distance to another vector xi is larger, based on examining a few vector elements only.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.