Perpustakaan Digital ITB

Pada tugas akhir ini dilakukan penelitian untuk mengakselerasi kecepatan penjawaban kueri k-Nearest Neighbor (k-NN) pada algoritma Product Quantization (PQ). Product Quantization adalah algoritma similarity search aproksimasi untuk data set berukuran besar dan berdimensi tinggi. Ide utama algoritma PQ adalah mendekomposisi dimensi data menjadi beberapa subdimensi kecil, untuk kemudian dikuantisasi secara terpisah. Saat penjawaban kueri, hasil kuantisasi data digunakan untuk mengaproksimasi jarak kueri ke tiap-tiap data point. Akselerasi terhadap PQ dilakukan dengan memanfaatkan teorema ketaksamaan segitiga atau triangle inequality guna memotong kalkulasi jarak yang tidak diperlukan. Akselerasi bertujuan untuk menunjukkan bahwa kecepatan penjawaban kueri k-NN algoritma PQ dapat ditingkatkan dengan tanpa mengurangi kualitas nearest neighbor hasil pencarian dan tanpa bergantung pada instruksi spesifik CPU jenis tertentu seperti yang terjadi pada metode lain yang bergantung pada instruksi SIMD. Teknik triangle inequality pruning dipilih sebagai teknik akselerasi karena keberhasilannya dalam mengakselerasi algoritma k-NN brute-force dengan tetap mempertahankan kualitas nearest neighbor dan tanpa memerlukan instruksi SIMD. Pada tugas akhir ini dilakukan analisis mengenai cara mengadaptasikan teknik triangle inequality pruning pada algoritma Product Quantization. Hasil eksperimen menggunakan beberapa data set menunjukkan bahwa teknik ini berhasil mengakselerasi waktu kueri 6-7 kali lebih cepat dengan sedikit atau tidak sama sekali mengorbankan kualitas nearest neighbor apabila digunakan nilai parameter yang tepat. Selain itu, teknik triangle inequality pruning cukup kompetitif dibandingkan dengan metode akselerasi lain yang bergantung pada instruksi SIMD dari segi waktu kueri dan akurasi pencarian. Tak hanya itu, penggunaan teknik triangle inequality pruning juga tidak membatasi fleksibilitas konfigurasi PQ dan tidak bergantung pada instruksi SIMD seperti yang dilakukan metode yang kunci akselerasinya terletak pada SIMD.