StreamDelete: Penghapusan Node Efisien pada DiskANN Memori untuk Data Streaming

Palito, Hasan (2026) StreamDelete: Penghapusan Node Efisien pada DiskANN Memori untuk Data Streaming. Other thesis, Institut Teknologi Sepuluh Nopember.

Text 5024221042_Undergraduate_Thesis.pdf - Accepted Version Restricted to Repository staff only Download (4MB) | Request a copy

Abstract

Aplikasi berbasis data vektor berskala besar, seperti sistem rekomendasi, pencarian semantik, dan Retrieval-Augmented Generation (RAG), membutuhkan metode Approximate Nearest Neighbor Search (ANNS) yang mampu menangani data dinamis secara efisien. Meskipun DiskANN menawarkan kinerja pencarian yang tinggi, mekanisme penghapusan data pada skenario streaming dengan true window semantics masih menjadi tantangan karena pendekatan lazy deletion menimbulkan biaya komputasi yang besar dan sulit diskalakan pada beban kerja yang dinamis. Penelitian ini mengusulkan mekanisme backup-based deletion pada DiskANN in-memory dengan memanfaatkan kandidat edge hasil RobustPrune sebagai backup neighbors untuk memperbaiki struktur graf secara oportunistik selama proses greedy search tanpa memerlukan konsolidasi global. Selain itu, penelitian ini menggunakan desain mapped storage berbasis cell untuk mendukung manajemen memori yang lebih adaptif. Evaluasi dilakukan dengan membandingkan metode yang diusulkan terhadap lazy deletion menggunakan metrik recall, latency, dan throughput. Tujuan penelitian ini adalah mempertahankan kualitas pencarian sekaligus meningkatkan efisiensi proses penghapusan data pada skenario streaming waktu nyata.
=======================================================================================================================================
Large-scale vector-based applications such as recommendation systems, semantic search, and Retrieval-Augmented Generation (RAG) require Approximate Nearest Neighbor Search (ANNS) systems that can efficiently support dynamic data. Although DiskANN provides high search performance, data deletion in streaming scenarios with true window semantics remains challenging, as lazy deletion introduces significant computational overhead and scales poorly under bursty workloads. This research proposes a backup-based deletion mechanism for in-memory DiskANN, which leverages high-quality neighbor candidates discarded during RobustPrune as backup neighbors to opportunistically repair graph connectivity during greedy search traversal without global consolidation. In addition, a cell-based mapped storage design is introduced to enable adaptive memory management under fluctuating workloads. The proposed approach is evaluated against lazy deletion using recall, latency, and throughput metrics, with the goal of maintaining search quality while significantly improving deletion efficiency in real-time streaming environments.

Item Type:	Thesis (Other)
Uncontrolled Keywords:	Approximate Nearest Neighbor Search, DiskANN, Streaming Data, Backup based Deletion, Graph Index
Subjects:	Q Science > QA Mathematics > QA76.9 Computer algorithms. Virtual Reality. Computer simulation. Q Science > QA Mathematics > QA76.9.D33 Data compression (Computer science) Q Science > QA Mathematics > QA76.9.D343 Data mining. Querying (Computer science) Q Science > QA Mathematics > QA76.F56 Data structures (Computer science)
Divisions:	Faculty of Intelligent Electrical and Informatics Technology (ELECTICS) > Computer Engineering > 90243-(S1) Undergraduate Thesis
Depositing User:	Hasan Palito
Date Deposited:	26 Jul 2026 10:03
Last Modified:	26 Jul 2026 10:03
URI:	http://repository.its.ac.id/id/eprint/137704

Actions (login required)

View Item