Harga Pencarian Eksak

Pemindaian linear sebagai pencarian kNN eksak: benar, sederhana, dan berbiaya O(n) pada setiap query.

Daftar isi

Pencarian tetangga terdekat yang eksak dapat dilakukan tanpa indeks apa pun, yaitu dengan memindai seluruh vektor satu per satu untuk setiap query. Topik ini membahas cara kerja pemindaian linear, menyajikan implementasinya dengan NumPy, dan mengukur harganya dalam bentuk jumlah jarak yang dihitung, sehingga titik ketika pemindaian penuh berhenti masuk akal dapat ditentukan dengan angka.

Pencarian kNN eksak tanpa indeks#

Pencarian k-nearest neighbors (kNN) eksak menjawab pertanyaan berikut dengan jaminan kebenaran penuh: dari himpunan $n$ vektor, mana saja $k$ vektor yang jaraknya paling dekat ke query. Jawabannya diperoleh dengan brute force, yakni menghitung jarak dari query ke semua vektor tanpa kecuali, mengurutkannya, lalu mengambil $k$ terbaik. Tidak ada vektor yang dilewati, sehingga hasilnya selalu sama dengan jawaban optimal menurut ukuran jarak yang digunakan.

Ukuran jarak yang paling umum adalah jarak L2, yaitu panjang garis lurus antara dua vektor pada ruang berdimensi $d$ :

\|q - x_i\|_2 = \sqrt{\sum_{j=1}^{d} \left(q_j - x_{i,j}\right)^2}

Dengan notasi di atas, $q$ adalah vektor query, $x_i$ adalah vektor ke- $i$ pada dataset, dan $d$ adalah jumlah dimensi. Keunggulan pendekatan ini ada pada kesederhanaannya. Tidak ada struktur tambahan yang perlu dibangun atau dirawat, tidak ada parameter yang harus disetel, dan tidak ada memori ekstra di luar data itu sendiri. Setiap vektor baru yang ditambahkan langsung ikut dipertimbangkan pada pencarian berikutnya karena tidak ada indeks yang perlu diperbarui.

Simulasi kNN eksak dengan NumPy#

Perilaku pemindaian penuh paling mudah diamati pada angka yang nyata. Berkas berikut membangun dataset buatan berisi 10.000 vektor dengan 8 dimensi, menyiapkan tiga query, menghitung seluruh jarak L2, lalu mengambil lima tetangga terdekat untuk setiap query. Fungsi np.argpartition digunakan untuk menemukan posisi lima jarak terkecil tanpa mengurutkan seluruh hasil, sehingga yang dihemat hanya pekerjaan pengurutan, bukan perhitungan jaraknya.

python knn_eksak.py

"""Pencarian kNN eksak: pemindaian penuh 10.000 vektor untuk setiap query."""
import numpy as np

rng = np.random.default_rng(7)

# Dataset buatan: 10.000 vektor dengan 8 dimensi
X = rng.standard_normal((10000, 8))

# Tiga query buatan dengan jumlah dimensi yang sama
Q = rng.standard_normal((3, 8))
k = 5
total_jarak = 0

for i, q in enumerate(Q):
    jarak = np.linalg.norm(X - q, axis=1)   # seluruh 10.000 jarak dihitung
    total_jarak += jarak.size
    urutan = np.argpartition(jarak, k)[:k]  # posisi k jarak terkecil tanpa mengurutkan semuanya
    urutan = urutan[np.argsort(jarak[urutan])]
    tetangga = [int(t) for t in urutan]
    nilai_jarak = [round(float(j), 4) for j in jarak[urutan]]
    print(f"Query {i + 1}: tetangga = {tetangga}")
    print(f"          jarak   = {nilai_jarak}")

print(f"Total jarak dihitung : {total_jarak}")
print(f"Perhitungannya       : {Q.shape[0]} query x {X.shape[0]} vektor = {Q.shape[0] * X.shape[0]}")

text Keluaran

Query 1: tetangga = [5893, 1393, 5813, 4002, 1527]
          jarak   = [1.1595, 1.2334, 1.3335, 1.4128, 1.415]
Query 2: tetangga = [1143, 1469, 9701, 476, 5549]
          jarak   = [0.9134, 1.1098, 1.1367, 1.2031, 1.2035]
Query 3: tetangga = [8054, 8657, 1655, 3869, 991]
          jarak   = [0.8218, 0.9654, 1.02, 1.1573, 1.2075]
Total jarak dihitung : 30000
Perhitungannya       : 3 query x 10000 vektor = 30000

Keluaran menunjukkan sesuatu yang sederhana tetapi penting. Untuk tiga query pada 10.000 vektor, jumlah jarak yang dihitung adalah 30.000, yaitu tepat 10.000 untuk setiap query. Nilai ini tidak bergantung pada seberapa dekat tetangganya sebenarnya, melainkan selalu sebanyak vektor yang dipindai. Fungsi np.argpartition hanya menata ulang posisi indeks agar lima jarak terkecil berada di bagian depan array, kemudian lima indeks itu diurutkan ulang agar tampil berurutan dari yang terdekat.

Biaya yang tumbuh linear dengan jumlah vektor#

Menghitung satu jarak L2 memerlukan $d$ perkalian dan pengurangan, sehingga memindai $n$ vektor untuk satu query berbiaya $O(n \cdot d)$ . Karena $d$ tetap untuk satu dataset, pertumbuhan biayanya dikuasai oleh $n$ . Menggandakan jumlah vektor berarti menggandakan jumlah jarak yang dihitung untuk setiap query, dan pembayaran itu berulang pada setiap query yang datang.

Jumlah vektor	Dimensi	Jarak dihitung per query
10.000	8	10.000
100.000	768	100.000
1.000.000	1536	1.000.000

Tabel di atas menggunakan jumlah jarak sebagai ukuran biaya, bukan waktu. Jumlah jarak bersifat deterministik dan dapat dihitung dari bentuk datanya saja, sedangkan waktu bergantung pada mesin yang menjalankannya. Hubungan keduanya bersifat kualitatif: makin banyak jarak yang dihitung, makin lama satu query selesai, karena setiap jarak memerlukan pekerjaan perkalian yang tidak dapat dilewati.

Pada penerapan nyata, vektor embedding yang keluar dari model teks atau model gambar umumnya berdimensi antara 384 dan 1536. Satu juta vektor berdimensi 1536 dalam format float32 menempati sekitar 6 GB, dan pemindaian penuhnya menghitung satu juta jarak untuk setiap query yang masuk. Meskipun mahal pada skala besar, pemindaian penuh tetap memiliki peran. Pada dataset kecil, biayanya rendah dan kesederhanaannya mengalahkan kerumitan perawatan indeks. Pemindaian penuh juga menjadi jawaban acuan ketika kesetiaan indeks aproksimatif diukur.

Kesalahan umum#

Kesalahan pertama adalah mengukur biaya pemindaian penuh dengan stopwatch pada satu mesin lalu menjadikannya angka yang berlaku umum. Waktu bergantung pada perangkat keras, versi library, dan beban sistem, sehingga angka itu berubah di tempat lain. Ukuran yang stabil adalah jumlah jarak yang dihitung, sebagaimana digunakan pada bagian sebelumnya, sedangkan waktu hanya melengkapinya secara kualitatif.

Kesalahan kedua adalah menghitung jarak satu per satu dalam perulangan Python, misalnya dengan memanggil np.linalg.norm(X[i] - q) untuk setiap indeks. Hasilnya benar, tetapi konstanta biayanya membengkak karena setiap panggilan membawa overhead tersendiri, padahal np.linalg.norm(X - q, axis=1) menghitung seluruh jarak dalam satu operasi array.

Kesalahan ketiga adalah melaporkan jarak kuadrat sebagai jarak. Menghilangkan akar kuadrat tidak mengubah urutan tetangga karena akar bersifat monoton, tetapi nilai yang dilaporkan ke pengguna tetap keliru bila metrik yang dijanjikan adalah jarak L2.

Ringkasan#

Pencarian kNN eksak memindai seluruh $n$ vektor untuk setiap query, mengurutkan jaraknya, lalu mengambil $k$ terbaik, sehingga hasilnya selalu optimal menurut ukuran jarak yang digunakan.
Biaya per query adalah $O(n \cdot d)$ , dengan $d$ jumlah dimensi, sehingga bertumbuh linear terhadap jumlah vektor dan berulang pada setiap query.
Keunggulannya adalah kebenaran penuh, kesederhanaan, dan ketiadaan indeks untuk dirawat, sedangkan kelemahannya adalah biaya pemindaian yang tidak pernah turun di bawah $n$ .

Referensi#

Search — Qdrant — Dokumentasi pencarian Qdrant yang menjelaskan perilaku pencarian kemiripan pada mesin basis data vektor.
pgvector — GitHub — Dokumentasi ekstensi pgvector untuk PostgreSQL yang mencakup opsi indeks dan pencarian vektor.