• a database of N objects   (obj₁ , obj₂ , ..., obj_N)

• representations of objects as d-dimensional vectors   (v_obj1 , v_obj2 , ..., v_objN)
  (each vector may represent one or more features of the object)

• a query object q with associated d-dimensional vector (v_q)

• a distance measure   D(v_i , v_j) : [0..1)     (D=0    v_i=v_j)

Outputs

• a list of the k nearest objects in the database   [a₁ ,   a₂ ,   ...   a_k]

• ordered by distance to query object   D(v_a1 ,v_q)     D(v_a2 ,v_q)     ...     D(v_ak ,v_q)

And all done as efficiently as possible ... (time most important, space less so)