• 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 ...

... where time is the most important efficiency factor