Summary : I need help to write the mathematical formulation of the objective function of knn and relate it to the neighborhood definition. The definition should encorporate the demonstration of the online evaluation objective and optionally the formulation of additional hashing algorithms (eg ScanNN).

Problem: Given distance of choice eg minkowski: $d(\hat{x}, {x})$ The neighborhood of $k$ samples for the new sample $\hat{x}$, can be defined as $N_k(\hat{x}, \{x\})$. I want to express the creation of this neighborhood set as a function of the distance. But I am not sure how one can "create a set" in mathematics language.

This is what I have so far : enter image description here

Linked question: https://stackoverflow.com/posts/65334702/edit


1 Answer 1


What about the following for a list of points $P = (p_1, \ldots, p_n)$:

Let $d_i = ||x-p_i||$. Then the kNN neighbors of $x$ are $$\mbox{kNN}(x) = \{ p\in P \mbox{ with } ||p-x|| \leq rank_k(d_1,\ldots,d_n)\}$$ where $rank_k$ means the $k$-th element in the ordered list (nth_element in C++ STL lingo).

  • $\begingroup$ Please can you help me elaborate on the rank_k structure? I think it captures the problems in a nice way. Alternatively if you know some good text book reference it woudl be highly appreciated $\endgroup$
    – partizanos
    Jan 26, 2021 at 15:04
  • $\begingroup$ $rank_k$ means the k-th element in the ordered list. It is not necessary, though, to actually order the entire list (an $O(n\log n)$ algorithm) to obtain the k-th element. It is possible to compute the k-th element in $O(n)$ runtime: such an efficient implementation is readily available in the C++ STL algorithm nth_element: geeksforgeeks.org/stdnth_element-in-cpp $\endgroup$
    – cdalitz
    Jan 26, 2021 at 15:17
  • $\begingroup$ I understand but outsdie of Cpp in pure mathi is there such a thing as orderderd set ? $\endgroup$
    – partizanos
    Jan 26, 2021 at 15:26
  • $\begingroup$ No, sets are unordered. "Ordered sets" are called "lists". Unlike sets, lists can also have duplicate entries. Just to complete the terminology: there is also a mathematical structure that represents sets (unordered), but that can have duplicate entries. It is called "bags" or (sometimes) "multisets". $\endgroup$
    – cdalitz
    Jan 26, 2021 at 15:38
  • $\begingroup$ Lets use max_k then to replace rank_k in the solution what do you think ? $\endgroup$
    – partizanos
    Jan 26, 2021 at 17:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.