comparing two complex numbers via cosine similarity: reasonable?

[DiTBho]

I have written a polymorphic b+tree algorithm that can accept any data type, uint32, strings, even complex numbers.

if comparing []={ ==, !=, >, >=, <, <=} { (uint32,uint32), (sint32, sint32) } is easy ...
comparing (string, string) requires a special method, namely lexicographical ordering ...

but ... what about comparing (cplx_sint32_t, cplx_sint32_t) ?

Code: [Select]

typedef struct
{
   sint32_t re;
   sint32_t im;
} cplx_sint32_t;

as a first approach, I thought of the infinite norm

Code: [Select]

l_x = sqrt((x.re)*(x.re) + (x.im)*(x.im));
l_y = sqrt((x.re)*(x.re) + (x.im)*(x.im));

cmp = compare(l_x, l_y);
but this doesn't say anything about the direction in which the vectors point ...
in the same direction?
are they orthogonal?
are they exactly in antiphase?

I don't know... 

If you can go from integers to fixed-point or floating-point numbers...
... I think "cosine similarity" might answer this question

Code: [Select]

z = ((x.re / l_x) * (y.re / l_y)) + ((x.im / l_x) * (y.im / l_y));


Code: [Select]

z = [-1 ... +1]

z=0 ---> they are orthogonal
z=+1 ---> they point to the same direction
z=-1 ---> they are exactly in antiphase

however, since each vector is normalized (by dividing by the length of the vector)
the information about the "magnitude" of the vectors is lost ...

... so does it make sense? 

[brucehoult]

For what purpose are you storing them in the tree?

If it's just for the purposes of finding them again later in O(log N) time then just do the same as for strings or any other composite type: compare the first element for < or > and if they are equal then compare the second element.

It really doesn't matter whether your complex numbers are in X,Y form or angle,radius for or any other form.

If you're putting them in the tree in order to later print them in sorted order then YOU need to decide what sorted means for you.

[golden_labels]

Using a comparator based on lexicographical ordering may be not optimal for your purpose, but it is safe. And therefore often used unless proven insufficient.

Safe from what, you may ask. From an easy to overlook trap. In a total order relation, the comparator must be transitive and antisymmetric. Chasing either performance or abstractions, countless programmers failed to fulfil at least one of these. Only to be detected after a long time, when some conditions have changed or a particular values range was encountered. Lexicographical orderings guarantee this to never happen.

So think what your goals are and what ordering would be the best, but mind the trap.

[Tation]

Provided that (if I understood it correctly) your application uses a lexycographical order when working with strings, and that is enough for it to work, then you can compare complex numbers in the same way and it will work too. That's, provided \(z_0=a+bj\), \(z_1=c+dj\), then \(z_0<z_1\) iff (\(a<c\)) || (\(a=c\) && \(b<d\)).

This, in fact, defines a strict total order over complex numbers, although this order is not conserved under multiplication, so it does not turn complex numbers into an ordered field. But, as I said, if your b+tree works with strings, it will also work with complex numbers (or with any kind of objects) provided that any strict total order exists for them.

This is not the only lexycographical order you can use on complex numbers. Using the same approach with magnitude and argument, or whatever, will also work, but this order is easy and fast.

[DiTBho]

For what purpose are you storing them in the tree?
If it's just for the purposes of finding them again later in O(log N) time

precisely, I have about ~ 2M items in the b+tree!

With strings it's quite obvious to use lexicographic ordering, human dictorionaries are sorted this way.
With complex numbers... I don't know, it leaves me a bit more perplexed.
More than I do with vectors in "vector similarity" problems.

object_A -> neural network -> features extractor as n-dimensional vector (of float32_t)
object_B -> neural network -> features extractor as n-dimensional vector (of float32_t)

query(db) --> list the first k similar objects --> b+tree scan -> vector similarity: cmp(object_A, object_B)


----

it's about the same algorithm that google-image uses, I implemented it from scratch, in myC.

Complex numbers instead have to do with complex analysis.
I find myself a bit "displaced", even if ...
... complex numbers are nothing more than a two-component vector
and in vector similarity using 1024-component vectors ...

However in "vector similarity" I can very well allow myself to use the "cosine similarity"
a number between -1 and +1 to compare two "object-feature-vectors(1)".

That is, I don't care at all about the magniture of the vectors
only whether or not they point in the same direction,
because if they point in the same direction alpha, it means that that feature-alpha is common


It's profoundly different! 


(1) a vector that tries to express with numbers how-much "feature" is present

[Tation]

When your b+tree compares strings, what does it need to know? That they are different? That one in "greater/smaller/equal" than the other? That they point in the same direction? That they are orthogonal? That they are similar? That the distance between them is X units?

EDIT: or you need to sort them?

[ejeffrey]

There is no "proper" total ordering of complex that satisfies sensible conditions, so don't bother trying to find one. If you just need retrieval, use lexographic ordering, that is sort first by real and then imaginary components.  If you need something else you will need to be more specific

You should think about how to handle the standard floating point corner cases: nan, inf, -inf, and -0 only now you have to consider nonsense cases like having a finite real part and infinite imaginary part, or `inf + i*nan`  likely you want to coerce those to a single infinity and a single nan value.

It's not clear if you need to intermix real and complex numbers but if so you want to make sure that a + i0 sorts the same as floating point a.

If you really  need to find nearby points you will need a different data structure like an R-tree or at least modify your query algorithm to do something smarter than pairwise comparison.

[SiliconWizard]

Apparently, the norm of the complex numbers wasn't enough for the OP. He mentioned taking the direction into account. Not sure exactly what he wants to achieve.
But, if both the norm and the direction must be taken into account for comparison, we need to know which of the two should prevail over the other.
(We can now think of the numbers as vectors as this is apparently what the OP is considering.)

Given what he said, comparing first the norm and second the argument would probably make more sense than comparing real and imaginary parts. Of course, as I said above, that assumes the norm would prevail over the argument. If it's the other way around, just swap the order of comparisons.

Note that you obviously don't need to compute the square root for the norm as it doesn't change the order, so just don't. Comparing the sum of squares of real and imaginary parts is all it take. Much cheaper.
The argument is a more expensive operation: atan2(im, re), which is arctan(y/x) at its core, but handling all particular cases and quadrants. Note that arctan(x) is continuous and strictly increasing, so here again, absolutely no need to compute any arctan, computing y/x is enough when x /= 0 (and otherwise handle all cases for atan2 as usual, just no need to compute the arctan itself).

Just a tip, I still don't know exactly how you want to order your complex numbers, but the above looks like a reasonable approach if you really want to have something that looks like it takes the norm and "direction" of the complex numbers as if they were vectors. Merely comparing the real part first and imaginary part second may be enough, although slightly less subtle. Just consider both and see.

[gf]

Given what he said, comparing first the norm and second the argument would probably make more sense than comparing real and imaginary parts. Of course, as I said above, that assumes the norm would prevail over the argument. If it's the other way around, just swap the order of comparisons.

I'm not sure if the mapping from x to the pair { |x|, arg(x) } is guaranteed to be injective if the norm and arg are calculated with (limited) floating point precision (where x is complex).

[golden_labels]

There is no "proper" total ordering of complex that satisfies sensible conditions, so don't bother trying to find one. (…)

I agree that lexicographic ordering is the best first choice, and I’d also argue for using other structures where spatial features are relevant.⁽¹⁾ But to be correct it’s worth noting that there do exist reasonable total orderings of complex numbers.

Many space-filling curves fall into this category. Examples include Hilbert curve, Morton curve, and Moore curve. Whether the cost of the transformation is worth it, is a separate issue.

And a note on why we are even bothered about such “theoretical details.” It’s because B+trees specifically require total ordering. Since not every algorithm or structure has that strict requirements, it’s a thing easy to miss.

⁽¹⁾ R-trees, quadtrees to name the common ones.

[Tation]

AFAIK, the lexycographical order for complex numbers cited above is an strict total order.

[SiliconWizard]

Given what he said, comparing first the norm and second the argument would probably make more sense than comparing real and imaginary parts. Of course, as I said above, that assumes the norm would prevail over the argument. If it's the other way around, just swap the order of comparisons.

I'm not sure if the mapping from x to the pair { |x|, arg(x) } is guaranteed to be injective if the norm and arg are calculated with (limited) floating point precision (where x is complex).

Yes, well, just comparing floating point numbers in general can be a problem for maintaining a given order. Fortunately, from what I can read, the OP wants to deal with integers as he shows a complex number type made of integer real and imaginary parts, and as I suggested, the norm and argument can be compared without resorting to floating point in that case.
But again, possibly just comparing the real part first and imaginary part second (which are integers) is enough to fit his purpose, and it's much cheaper.
If it's just for building B+ trees, as I understand (but I admit I find the whole description a bit confusing as to the end goal), it should be fine. At least I don't see any obvious issue.

[ejeffrey]

I'm not sure if the mapping from x to the pair { |x|, arg(x) } is guaranteed to be injective if the norm and arg are calculated with (limited) floating point precision (where x is complex).

Definitely not just by the pigeon hole principle.  Almost all bit patterns for complex (a + ib) represent valid distinct complex values.  Only inf/nan values and the singular negative zero are redundant.  The magnitude must be real and arg(z) can't have an exponent greater than 2.   So quite a lot of inputs must map to the same outputs.

It's not clear if that matters or not for the OP or if any of this is suitable.

[DiTBho]

Code: [Select]

typedef struct
{
   sint32_t re;
   sint32_t im;
} cplx_sint32_t;

Each complex number, represents a complex frequency.

The b+tree algorithm has been implemented deliberately so as not to allow collisions, so the first thing it has to do as soon as a pair of complex numbers arrives is to verify that they are NOT already present in the tree, and, if they are already present, increment the count without adding anything than this.

[DiTBho]

It's not clear if that matters or not for the OP or if any of this is suitable.

it matters in my use case.
You answered one of the doubts I had.
Thanks!

[SiliconWizard]

Code: [Select]

typedef struct
{
   sint32_t re;
   sint32_t im;
} cplx_sint32_t;

Each complex number, represents a complex frequency.

The b+tree algorithm has been implemented deliberately so as not to allow collisions, so the first thing it has to do as soon as a pair of complex numbers arrives is to verify that they are NOT already present in the tree, and, if they are already present, increment the count without adding anything than this.

Then just comparing the re and im parts should work with no problem.

[radiolistener]

If your goal is to define a total order for complex numbers for use in a b+tree, it's crucial not to lose part of information, such as magnitude or direction of the vector. Approaches like cosine similarity normalize the vectors, discarding their magnitude, and thus cannot provide a strict ordering. A better solution is to define a lexicographical order based on all fields of the vector, include both re and im for complex or all x, y, z, w for 4D.

[brucehoult]

I'm not sure if the mapping from x to the pair { |x|, arg(x) } is guaranteed to be injective if the norm and arg are calculated with (limited) floating point precision (where x is complex).

Definitely not just by the pigeon hole principle.  Almost all bit patterns for complex (a + ib) represent valid distinct complex values.  Only inf/nan values and the singular negative zero are redundant.  The magnitude must be real and arg(z) can't have an exponent greater than 2.   So quite a lot of inputs must map to the same outputs.

It's not clear if that matters or not for the OP or if any of this is suitable.

That is easily solved: just sort by { |x|, arg(x), re, im }

Or, I think from what has been said, better would be { arg(x), |x|, re, im }

Or { signum(re), im/re, re^2+im^2, |re|, im }

[Tation]

I still do not understand what is the interesting property that turns ordering lexycographically by { |z|, arg(z) } (and variants) appealing enough to prefer it over { re, im }. Both are strict total orders, the "highest rank" of order achievable over the complex numbers. But, as pointed, when working with finite precission, the first order may show problems (as I understand this, turning it into a non-strict total order, where two distinct objects a & b may be neither a < b nor b < a). Evenmore, it is harder to compute it. So, what's its point?

[ejeffrey]

If you are just ordering because it's a requirement for tree-based data structures to have ordering, it doesn't matter at all.  You could use bit-reversed comparisons if you wanted to.

But if you want to do spatial queries, like "find all points where 3 <= |z| <= 7, you want a geometrically appropriate ordering.  That only makes sense if you know what you want, otherwise there is no reason to prefer it and many reasons to avoid it.

Ideally you might want to be able to say "find all the points within some distance dx of a target point a + i*b".  That's a very generic concept and mimics the way we can do binary search on an ordinary sorted list.  But there is no ordering you can apply that guarantees the ability to do that efficiently with a simple tree structure.  This is what R-Trees are for.  They are a more complex data structure that work with nested bounding boxes, allowing multi-dimensional searching.

Space filling curves like the hilbert curve are another option that have the reverse type of locality.  Two points that are close together on the hilbert curve are guaranteed to be close to each other in space, but the reverse is not true.  So again, it requires a particular application that takes advantage of that locality property.

So it's all back to: without a specific application, lexical sort is the easiest and most common choice.

[radiolistener]

But if you want to do spatial queries, like "find all points where 3 <= |z| <= 7, you want a geometrically appropriate ordering.  That only makes sense if you know what you want, otherwise there is no reason to prefer it and many reasons to avoid it.

So it's all back to: without a specific application, lexical sort is the easiest and most common choice.

I agree - there's no reason to hardcode any specific comparison logic into the B+ tree or the complex vector structure itself. The most flexible and maintainable approach is to let the user provide a custom comparator function for ordering, searching, and insertion. This way, users can define their own semantics - whether it's based on |z|, bit-reversed ordering, Hilbert curve keys, or any other domain-specific criteria. The tree just needs a consistent total order, how that order is defined should be left to the user.

[bson]

You can't compare two complex numbers by 'cosine similarity' because the difference between two cosines is a cosine.  More specifically, it has a phase and a frequency, so is also complex.

In short, there is no natural order for complex numbers.

For some applications they can be treated as a structure, so hash them for example to maintain a set or key a map off.  This way you can quickly detect duplicates.  And if you don't care what specifically the order is, only that there is some order, then they can be ordered off this, too.  For example to arbitrate, where you need to pick a winner and a loser.

Edit: of course you can define any order you want, but you will never be able to use those to implement for example ranges that can be split and joined correctly.  One example would be distance from 0, in the z plane.  Another it's distance from the real axis on the unit circle if plotted according to re^2 + im^2 = 1.  A range could be defined as the rectangle enclosed between two complex numbers in the plane.  Etc.  But none of that really holds up to range operators, while some can be split, joining two ranges become very complicated and has no single correct result, nor can the set of correct results be captured as a range.