Efficient way to perform vector dot product

steven7

Hi I recently have the requirement to perform dot-product on two vectors in Elixir and I was wondering what would be the most efficient way. Imagine the following scenario,

Say I have ~1M vectors stored in memory, each with the following format [{"foo", 0.123}, {"bar", 0.777}, .........]. I now have a query vector with the same format and I need to compute the dot product of the query vector and each of the ~1M stored vectors. By dot-product I mean, if both vectors contains the same string key, multiple their float value and sum it all up.

Now my most naive/straightforward solutions is something like, instead of storing them as array of tuples, I convert them into Map and store them in memory as before, so my vector would become something like a hash-table %{"foo" => 0.123, "bar" => 0.777} and then:

Enum.filter(stored_vectors, fn -> vector 
  # Since we only need to process the "overlapped keys"
  query = Map.take(query_vector, Map.keys(vector))

  Enum.map(query, fn {k, v} -> 
      v * vector[k]
  end)
  |> Enum.sum
  |> Kernel.>(0.5)
end)

Now my issue is that Map.take is extremely slow when I am querying against 1M vectors. But if I remove that code and just do multiplication anyway like this:

Enum.filter(stored_vectors, fn -> vector 

  Enum.map(query_vector, fn {k, v} -> 
      v * (vector[k] || 0)
  end)
  |> Enum.sum
  |> Kernel.>(0.5)
end)

Its even slower. I am running out of options and was wondering how can I optimise my code.

P/S: I also tried one more thing like this but to no avail:

keys1 = query_vector |> Map.keys |> MapSet.new()

Enum.filter(stored_vectors, fn -> vector 
  overlapped_keys = MapSet.intersection(keys1, vector |> Map.keys |> MapSet.new())
  Enum.map(overlapped_keys, fn k-> 
      query_vector[k] * vector[k]
  end)
  |> Enum.sum
  |> Kernel.>(0.5)
end)

33 comments

#data-structures

0 3933 33

2025-09-18 17:59:51 UTC

Showing Posts 1 to 10

Show Best Posts
Show All (oldest first)
Show All (newest first)

LostKobrakai

Did you try ETS for storage? :ets.lookup(key) is documented to be constant for any table size.

Post #1

steven7

Yes I did but apparently I cannot do such advanced lookup (dot-product) in :ets. The idea is to return a list of vectors that has a dot-product of > 0.5. I mean if ETS supports something like this then my life would be way much easier.

fun = :ets.fun2ms(fn {id, vector} when dot_product(query_vector, vector) > 0.5 -> id end)

:ets.select(:stored_vectors, fun)

Where dot_product is a routine that compute the dot-product.

Post #2

LostKobrakai

If sounded like Map.take was your problem and :ets.lookup would be a faster alternative. I wasn’t suggesting that ets should do the calculation, but rather the storage.

Post #3

steven7

Hmm.. I am not sure if I understand your suggestion. You mean to store all the Map keys in ETS?

Post #4

LostKobrakai

Not just the keys, but the keys and their values. I’m not sure how dynamic your data is, but once data is in ets it should be retrievable quite quickly.

Post #5

steven7

Well the data can be quite different from each other, I am still not sure what you meant by using ETS. Something like this?

Enum.each(stored_vectors, fn vector -> 
 :ets.insert(:stored_vectors, {"some_randomly_generated_id", vector})
end)

Then how do I retrieve it?

EDIT: Ah I see there might be some confusion, my bad. Each vector is represents an array of tuples so in my example there are 1M arrays of tuples (and each array can contains up to hundreds of tuples). Unless I use Map, then each array of tuples becomes a Map with again, hundred of KV pairs.

Post #6

LostKobrakai

So for each map you currently have you’d create an ets table, where you’d store a row for each key/value pair: :ets.insert(table_vector_1, {key, float}). I’m not sure how quick inserts are in ets compared to maps, which you’d need to try out.

Once you have that you can do your calculation just like you did with maps, but instead of using Map.take(query_vector, Map.keys(vector)) or vector[k] you’d use :ets.first/:ets.next() and :ets.lookup.

Also as you’re doing sums here I’d not “filter” keys before iterating, but simply iterate over all keys and just return 0 if the key is not present in the compared vector.

Post #7

steven7

Hmm that would mean…1M of tables in ETS? Would that be a problem actually?

Actually on my second solution I didn’t do any key filtering, where I just try to compute the dot product of say
query = %{"foo" => 0.5, "bar" => 0.25} and %{"foo" => 0.125, "baz" => 0.8} (one of the vector in stored_vectors). The iteration would be:

query["foo"] * (stored_vector["foo"] || 0 )= 0.5 * 0.125
query["bar"] * (stored_vector["bar"] || 0 )= 0.5 * 0

But its much more slower than filtering the keys beforehand and just do

query["foo"] * stored_vector["foo"] = 0.5 * 0.123

Post #8

NobbZ

If I understand @steven7 correctly, he has 1M inputs which are also huge. Converting each of those inputs to ETS might blow up table space.

Using the table just as ephimeral throwaway conversion might cost to much of time during conversion from one to another.

As I’ve already mentioned in the chat yesterday, I’m still under the assumption that this should be one of the fastest possibilities (in the chat it sounded as if maps as input where given and unchangable):

m1 = %{…}
m2 = %{…}

Enum.reduce(m1, 0, fn {k, v}, sum -> sum + v * (m2[k] || 0) end)

This is optimised on the size of m1, so if m2 is the smaller map, just swap them around.

And I’ll stick to my opinion until I got proven otherwise by benchmarks with data sets of realistical sizes.

And if the input type is not actually fixed to maps but can be changed, and insertion/building time does not matter that much (or data is already sorted anyway), then a pre-sorted proplist like list might actually be the way to go and using algorithms for calculating intersections of sorted listsets to actually calculate the “product” in the accumulator instead of the intersection should be the way to go.

Post #9

LostKobrakai

Is there a limit to ETS? I mean the data seems to fit into memory already and the references for the ets table should also not sweat with that number. But I’ve not have had to deal with such amounts of data as well.

Post #10

Load more posts (23 remaining)