# Do I need a vector database to solve this problem?

**URL:** <https://discourse.julialang.org/t/do-i-need-a-vector-database-to-solve-this-problem/100629>\
**Category:** Offtopic\
**Created:** [June 21, 2023, 12:02am UTC](https://discourse.julialang.org/t/do-i-need-a-vector-database-to-solve-this-problem/100629 "2023-06-21T00:02:08Z")\
**Posts on this page:** 10\
**Page:** 1

<div class="post-metadata">

**Author:** ![maxkapur](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/maxkapur/32/21208_2.png) [@maxkapur](https://discourse.julialang.org/u/maxkapur)\
**Post date:** [June 21, 2023, 12:02am UTC](https://discourse.julialang.org/t/do-i-need-a-vector-database-to-solve-this-problem/100629/1 "2023-06-21T00:02:08Z")

</div>

Suppose I have a list of known vectors x\_i \in \mathbb{R}^m for i = 1 \dots n.

Now my boss comes to me and gives me a vector y \in \mathbb{R}^m and says, find the i that minimizes

\| y - x\_i \|.

Clearly, the best you can do is compute the norm for each i and find the smallest one, at computational cost O(nm).

Now, what changes if I am allowed to _preprocess_ the x\_i prior to my boss timing my code? In the m = 1 case, I could get clever and _sort_ the (scalar) x\_i values. Then I can find the optimal i using binary search, so (not counting the time to sort the list) the search takes only O(m \log n) time.

Is there a similar approach for the m-dimensional case?

I have heard whispers of something called a “vector database” that is optimized for these kinds of operations, but I suspect that anything with the word “database” in it is probably overkill for this simple (?) problem, and I’m wondering if there’s a straightforward data structure one could use.

(Note that you don’t get to know y at the preprocessing stage, only the x\_i.)

* * *

Miss this community—haven’t been as active since changing jobs and doing almost everything in Python.

---

<div class="post-metadata">

**Author:** ![Oscar\_Smith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oscar_smith/32/25343_2.png) [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)\
**Post date:** [June 21, 2023, 12:15am UTC](https://discourse.julialang.org/t/do-i-need-a-vector-database-to-solve-this-problem/100629/2 "2023-06-21T00:15:33Z")

</div>

This is a problem where you get to pick 2 of fast, easy, and exact. The fast easy approximate solution is to pick `k<m` (think 3 or so) random vectors `vₖ` of length `m` and compute `xᵢ⋅vₖ` for each `i,k`. If `∥y−xᵢ∥` is small, then `yᵢ⋅vₖ≈xᵢ⋅vₖ`. You do the binary searches on `xᵢ⋅vₖ` with the key `yᵢ⋅vₖ`, and find the ones that are close for all three. Making this algorithm robust and good takes some effort.

---

<div class="post-metadata">

**Author:** ![ericphanson](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ericphanson/32/215186_2.png) [@ericphanson](https://discourse.julialang.org/u/ericphanson)\
**Post date:** [June 21, 2023, 12:26am UTC](https://discourse.julialang.org/t/do-i-need-a-vector-database-to-solve-this-problem/100629/3 "2023-06-21T00:26:58Z")

</div>

If I’m following right, this is exactly the problem of [nearest neighbor search](https://en.m.wikipedia.org/wiki/Nearest_neighbor_search) (in m-dimensional Euclidean space). There’s a bunch of approximate and exact techniques to solve it (many at the Wikipedia link there).

---

<div class="post-metadata">

**Author:** ![votroto](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/votroto/32/16416_2.png) [@votroto](https://discourse.julialang.org/u/votroto)\
**Post date:** [June 21, 2023, 12:34am UTC](https://discourse.julialang.org/t/do-i-need-a-vector-database-to-solve-this-problem/100629/4 "2023-06-21T00:34:56Z")

</div>

I think you may want to look into space partitioning datastructures. Database technologies ALWAYS generate absurd hype. Whether they solve your problem or not I don’t know, but proceed with caution. Always benchmark, you will be surprised.

---

<div class="post-metadata">

**Author:** ![nsajko](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/nsajko/32/221187_2.png) [@nsajko](https://discourse.julialang.org/u/nsajko)\
**Post date:** [June 21, 2023, 1:08am UTC](https://discourse.julialang.org/t/do-i-need-a-vector-database-to-solve-this-problem/100629/5 "2023-06-21T01:08:57Z")

</div>

> [@maxkapur](#):
>
> at computational cost O(nm).

If n and m are known in advance, I guess that O(n m) = O(1), though?

Eric pointed to the Wikipedia page which lists (presumably) all the known algorithms, however I’d like to point out that there’s a way of improving the _naive_ (linear search) solution in a “Julian” manner: move the data known in advance into the type domain.

Furthermore, to maximally exploit CPU architecture parallelism, the “linear” search could be restructured as a binary tree (because n is known in advance).

Once all the data is in the type domain in an appropriate manner, and assuming the arithmetic (whatever represents \mathbb{R}) is some machine-native type like `Float64`, I think Julia could generate blazing fast code, especially if everything fits into the instruction cache.

But the move into the type domain necessitates a run time dispatch, so this can’t be efficient when n and m are small.

---

<div class="post-metadata">

**Author:** ![barucden](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/barucden/32/26154_2.png) [@barucden](https://discourse.julialang.org/u/barucden)\
**Post date:** [June 21, 2023, 11:27am UTC](https://discourse.julialang.org/t/do-i-need-a-vector-database-to-solve-this-problem/100629/6 "2023-06-21T11:27:34Z")

</div>

You might also preprocess your data.

The task is \arg\min\_x \lVert y - x \rVert which is equivalent to \arg\min\_x \lVert y - x \rVert^2.The squared norm expands to \lVert y \rVert^2 + \lVert x \rVert^2 - 2x^Ty. The optimization is done w.r.t. x, so \lVert y \rVert^2 is just an additive constant and the problem reduces to \arg\min\_x \lVert x \rVert^2 - 2x^Ty.

If the list of vectors x\_i is fixed, you can precompute the squared norms \lVert x\_i \rVert^2 for each i=1,\ldots, n. When your boss comes :), you only have to compute the dot products. The complexity remains \theta(n m) but it is less computation and it can be parallelized easily.

Edit: One more tweak: \arg\min\_x \lVert x \rVert^2 - 2x^Ty = \arg\min\_x \frac{1}{2} \lVert x \rVert^2 - x^Ty. So you can precompute \frac{1}{2} \lVert x\_i \rVert^2 and save n multiplications when the boss comes!

---

<div class="post-metadata">

**Author:** ![aplavin](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/aplavin/32/222056_2.png) [@aplavin](https://discourse.julialang.org/u/aplavin)\
**Post date:** [June 21, 2023, 1:47pm UTC](https://discourse.julialang.org/t/do-i-need-a-vector-database-to-solve-this-problem/100629/7 "2023-06-21T13:47:00Z")

</div>

Sounds like exactly the problem for [GitHub - KristofferC/NearestNeighbors.jl: High performance nearest neighbor data structures and algorithms for Julia.](https://github.com/KristofferC/NearestNeighbors.jl)

---

<div class="post-metadata">

**Author:** ![maxkapur](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/maxkapur/32/21208_2.png) [@maxkapur](https://discourse.julialang.org/u/maxkapur)\
**Post date:** [June 21, 2023, 9:23pm UTC](https://discourse.julialang.org/t/do-i-need-a-vector-database-to-solve-this-problem/100629/8 "2023-06-21T21:23:19Z")

</div>

If I’m understanding this correctly, you have to compute n dot products of m-vectors, so this is still O(nm) complexity, right?

---

<div class="post-metadata">

**Author:** ![maxkapur](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/maxkapur/32/21208_2.png) [@maxkapur](https://discourse.julialang.org/u/maxkapur)\
**Post date:** [June 21, 2023, 9:24pm UTC](https://discourse.julialang.org/t/do-i-need-a-vector-database-to-solve-this-problem/100629/9 "2023-06-21T21:24:39Z")

</div>

Cool!

---

<div class="post-metadata">

**Author:** ![barucden](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/barucden/32/26154_2.png) [@barucden](https://discourse.julialang.org/u/barucden)\
**Post date:** [June 22, 2023, 5:12am UTC](https://discourse.julialang.org/t/do-i-need-a-vector-database-to-solve-this-problem/100629/10 "2023-06-22T05:12:19Z")

</div>

Yes, the complexity is the same.