🎱Lab 3

Exact NN vs. HNSW

Pengantar

Pada praktikum ini, kita akan melakukan hal yang sama dengan praktikum sebelumnya. Akan tetapi, kali ini kita akan membandingkan exact NN dengan HNSW.

Langkah 1 - Instal Library

!pip install hnswlib

Langkah 2 - Import Library

import hnswlib
import numpy as np
import time
from sklearn.neighbors import NearestNeighbors

Langkah 3 - Buat Dataset Dummy

# Build Dummy Dataset
num_elements = 1000
dim = 2
data = np.random.random((num_elements, dim)).astype(np.float32)

# Query point
query = np.array([[0.5, 0.5]], dtype=np.float32)
k = 5  # cari 5 tetangga terdekat

Langkah 4 - Buat Model NN

# Build NN Model
nn = NearestNeighbors(n_neighbors=k, algorithm='brute', metric='euclidean')
nn.fit(data)

# Compute time performace
start = time.time()
distances, indices = nn.kneighbors(query)
end = time.time()

print("=== Exact NN ===")
print("Indices:", indices)
print("Distances:", distances)
print("Waktu:", end - start, "s")

Hasilnya,

=== Exact NN ===
Indices: [[102 238 579 373 486]]
Distances: [[0.01328841 0.01816678 0.03427347 0.03446613 0.0375734 ]]
Waktu: 0.0011098384857177734 s

Langkah 5 - Buat Model HNSW

# Initiate Index
p = hnswlib.Index(space='l2', dim=dim)  

# Define Max Elements
p.init_index(max_elements=num_elements, ef_construction=100, M=16)

# Add Data
p.add_items(data)

# Set searching parameter
p.set_ef(50)   # tradeoff speed vs accuracy

start = time.time()
labels, distances = p.knn_query(query, k=k)
end = time.time()

print("\n=== HNSW ===")
print("Indices:", labels)
print("Distances:", distances)
print("Waktu:", end - start, "s")

Hasilnya,

=== HNSW ===
Indices: [[102 238 579 373 486]]
Distances: [[0.00017658 0.00033003 0.00117467 0.00118791 0.00141176]]
Waktu: 0.00013875961303710938 s