सटीक k-Nearest Neighbours

सरल, सटीक, और अक्सर काफ़ी

k-nearest neighbours (kNN) खोज query के सबसे पास के k vectors लौटाती है। सटीक तरीक़ा, brute force या flat index, हर संचित vector की दूरी निकालता है और सबसे अच्छे k रखता है। इसकी लागत प्रति query N × आयाम ऑपरेशन है, जो हज़ारों vectors के लिए नगण्य है और batching के साथ आधुनिक CPU या GPU पर कुछ लाख के लिए भी ठीक। Brute force सटीक है (कोई पड़ोसी नहीं छूटता), प्रशिक्षण या tuning नहीं चाहिए, और कोई भी filter समर्थित करता है। हमेशा यहीं से शुरू करें: यह वह ground truth देता है जिससे आप हर approximate तरीक़े को परखेंगे, और अक्सर इतना तेज़ है कि आपको और की ज़रूरत नहीं पड़ती।

सब कुछ जाँचे बिना निकटतम खोजें

Brute force सटीक है; IVF और HNSW जैसे indexes थोड़ा recall देकर बहुत अधिक गति पाते हैं।

Library के विरुद्ध brute force, चलाकर

मैंने यह Python virtual environment में numpy 2.5.3, scikit-learn 1.9.1 और faiss-cpu 1.15.1 के साथ चलाया, निश्चित random seeds के साथ ताकि संख्याएँ दोहराई जाएँ। numpy brute-force खोज और scikit-learn का brute-force NearestNeighbors query के लिए ठीक वही पाँच पड़ोसी लौटाते हैं।

import numpy as np
from sklearn.neighbors import NearestNeighbors

rng = np.random.default_rng(1)
data = rng.normal(size=(500, 16)); q = rng.normal(size=(1, 16))
brute = np.argsort(np.linalg.norm(data - q, axis=1))[:5]
nn = NearestNeighbors(n_neighbors=5, algorithm="brute").fit(data)
lib = nn.kneighbors(q, return_distance=False)[0]
print("numpy brute force:", brute.tolist())
print("sklearn           :", lib.tolist(), "| identical:", brute.tolist() == lib.tolist())

Output:

numpy brute force: [109, 179, 258, 325, 168]
sklearn           : [109, 179, 258, 325, 168] | identical: True

GPUs brute force को आगे ले जाते हैं

GPU पर batched matrix गुणन लाखों vectors को तेज़ी से brute-force कर सकता है, जिससे अक्सर ANN index की ज़रूरत हट जाती है।

त्वरित जाँच: Brute force से शुरू क्यों करें?

• इसे GPU चाहिए
• यह किसी भी आकार पर हमेशा सबसे तेज़ है
• यह सटीक है और approximate तरीक़ों को परखने का ground truth देता है
• यह filter नहीं कर सकता