title: Get minimum Euclidean distance between a given vector and vectors in the database
body: <p>I store 128D vectors in PostgreSQL table as double precision []:</p>
  
  <pre><code>create table tab (
     id integer,
     name character varying (200),
     vector double precision []
   )
  </code></pre>
  
  <p>For a given vector, I need to return one record from the database with the minimum Euclidean distance between this vector and the vector in the table entry.</p>
  
  <p>I have a function that computes the Euclidean distance of two vectors according to the known formula SQRT ((v11-v21) ^ 2 + (v1 [2] -v2 [2]) ^ 2 + .... + (v1 [128] -v2 [128] ]) ^ 2):</p>
  
  <pre><code>CREATE OR REPLACE FUNCTION public.euclidian (
    arr1 double precision [],
    arr2 double precision [])
    RETURNS double precision AS
  $ BODY $
    select sqrt (SUM (tab.v)) as euclidian from (SELECT
       UNNEST (vec_sub (arr1, arr2)) as v) as tab;
  $ BODY $
  LANGUAGE sql IMMUTABLE STRICT
  </code></pre>
  
  <p>Ancillary function:</p>
  
  <pre><code>CREATE OR REPLACE FUNCTION public.vec_sub (
    arr1 double precision [],
    arr2 double precision [])
  RETURNS double precision [] AS
  $ BODY $
    SELECT array_agg (result)
      FROM (SELECT (tuple.val1 - tuple.val2) * (tuple.val1 - tuple.val2)
          AS result
          FROM (SELECT UNNEST ($ 1) AS val1
                 , UNNEST ($ 2) AS val2
                 , generate_subscripts ($ 1, 1) AS ix) tuple
      ORDER BY ix) inn;
  $ BODY $
  LANGUAGE sql IMMUTABLE STRICT
  </code></pre>
  
  <p>Query:</p>
  
  <pre><code>select tab.id as tabid, tab.name as tabname,
          euclidian ('{0.1,0.2,...,0.128}', tab.vector) as eucl from tab
  order by eulc ASC
  limit 1
  </code></pre>
  
  <p>Everything works fine since I have several thousands of records in tab. But the DB is going to be grown and I need to avoid full scan of tab running the query, add a kind of index search. Would be great to filter-out at least 80% of records by index, the remaining 20% can be handled by full scan. </p>
  
  <p>One of the current directions of the solution search: PostGIS extension allows to search and sort by distance (ST_3DDistance), filter by distance (ST_3DWithin), etc. This works great and fast using indicies. Is it possible to abstract for N-dimensional space?</p>
  
  <p>Some observations:</p>
  
  <ul>
  <li><p>all coordinate values are between [-0.5...0.5] (I do not know exactly, I think [-1.0 ...1.0] are theoretical limits)</p></li>
  <li><p>the vectors are not normalized, the distance from (0,0,... 0) is in range [1.2...1.6].</p></li>
  </ul>
  
  <p><a href="https://ru.stackoverflow.com/questions/764135/%D0%9F%D0%BE%D0%B8%D1%81%D0%BA-%D0%BF%D0%BE-%D0%BC%D0%B8%D0%BD%D0%B8%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D0%BE%D0%BC%D1%83-%D1%8D%D0%B2%D0%BA%D0%BB%D0%B8%D0%B4%D0%BE%D0%B2%D0%BE%D0%BC%D1%83-%D1%80%D0%B0%D1%81%D1%81%D1%82%D0%BE%D1%8F%D0%BD%D0%B8%D1%8E-%D0%BC%D0%B5%D0%B6%D0%B4%D1%83-%D0%B7%D0%B0%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D0%BC-%D0%B2%D0%B5%D0%BA%D1%82%D0%BE%D1%80%D0%BE%D0%BC-%D0%B8-%D0%B2%D0%B5%D0%BA%D1%82%D0%BE%D1%80%D0%B0%D0%BC%D0%B8">That is the translated post from StackExchange Russian</a>.</p>