🟤ANNOY

Approximate Nearest Neighbors Oh Yeah

ANNOY (Approximate Nearest Neighbors Oh Yeah) adalah sebuah library yang dikembangkan oleh Spotify sekitar tahun 2013. Awalnya, Annoy dipakai untuk sistem rekomendasi musik. Misalnya, ketika seorang pengguna sedang mendengarkan satu lagu, sistem harus bisa dengan cepat menemukan lagu lain yang mirip, dari jutaan koleksi lagu. Mencari tetangga terdekat secara exact di ruang berdimensi tinggi (high-dimensional space) akan sangat mahal secara komputasi. Karena itulah, Spotify membuat ANNOY untuk mempercepat pencarian dengan cara mendekati hasil aslinya (approximate), tetapi tetap cukup akurat dan jauh lebih cepat.

ANNOY bekerja dengan membuat banyak pohon biner (binary tree) yang dibangun menggunakan hyperplane acak. Setiap hyperplane digunakan untuk membagi ruang data menjadi dua bagian, sehingga membentuk struktur pohon yang memecah dataset hingga ke level leaf. Saat kita melakukan query, titik yang dicari hanya akan dibandingkan dengan data yang berada pada leaf yang sama. Dengan cara ini, Annoy tidak perlu menghitung jarak dengan semua data, melainkan hanya dengan sebagian kecil data yang relevan. Metric kedekatan yang digunakan pada ANNOY adalah Euclidean atau Angular Distance.

Ada kelemahan yang cukup mendasar bila kita hanya menggunakan satu pohon. Bisa saja ada titik data yang sebenarnya sangat dekat dengan query point, tetapi karena jatuh di sisi hyperplane yang berbeda, titik tersebut tidak ikut dipertimbangkan. Dengan kata lain, tetangga terdekat bisa “hilang” hanya karena terpisah oleh hyperplane acak. Untuk mengatasi hal ini, Annoy membangun banyak pohon (misalnya 10, 50, atau bahkan 100 pohon). Di pohon pertama mungkin titik dekat tidak terambil karena berbeda sisi, tetapi di pohon kedua atau ketiga hyperplane bisa membagi data dengan cara berbeda, sehingga titik dekat itu akhirnya masuk ke leaf yang sama dengan query point. Dari kumpulan kandidat yang ditemukan di semua pohon, Annoy memilih titik yang benar-benar paling dekat. Inilah mengapa Annoy disebut approximate nearest neighbor: semakin banyak pohon, hasilnya semakin akurat, tetapi waktu pencarian juga sedikit lebih lama.