Computational complexity comparison of floating-point Euclidean distance calculation with binary fixed-point Hamming-distance calculation

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?

• 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. – Yuval Filmus Aug 21 '17 at 11:32
• This doesn't seem to be quite in scope here. – Yuval Filmus Aug 21 '17 at 11:33
• "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. – David Richerby Aug 21 '17 at 12:42
• @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. – Sohrab Aug 21 '17 at 12:57
• @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? – Sohrab Aug 21 '17 at 13:09