Fault-Tolerant Distributed Index Structures for Similarity Search over Heterogeneous Storage and Compute Environments

• Budi Santoso

  Universitas Negeri Surabaya, Jalan Ketintang 112, Department of Digital Systems, Surabaya, East Java, Indonesia

  Author

• Andi Wijaya

  Universitas Mulawarman, Jalan Kuaro 21, Department of Intelligent Computing, Samarinda, East Kalimantan, Indonesia

  Author

• Ariful Islam

  Dhaka, Bangladesh

  Author

Similarity search over high-dimensional embeddings is routinely deployed across fleets that combine memory, local NVMe, networked block devices, and object storage, while compute spans CPUs, GPUs, and disaggregated accelerators. In such heterogeneous environments, distributed index structures must simultaneously sustain low-latency approximate nearest neighbor retrieval, tolerate partial failures, and preserve predictable degradation when storage tiers or compute resources become unavailable. This paper develops a fault-tolerant distributed indexing approach for similarity search that treats indexing state as a layered composition of routing metadata, shard-local candidate generators, and re-ranking materializations, each mapped to distinct durability and performance envelopes. The design assumes crash-stop faults, transient network partitions, and tier-specific unavailability, while supporting concurrent insert and delete streams over continuously evolving embedding corpora. A central theme is separating the semantic correctness of top-$k$ retrieval from the operational correctness of index maintenance by introducing versioned vector state and recoverable adjacency materializations. The paper formalizes query execution under failures as a quorum-based candidate acquisition problem and derives bounds on recall loss as a function of replica diversity, routing entropy, and failure correlation across fault domains. It further introduces a heterogeneity-aware placement policy that co-optimizes tail latency and rebuild cost using a cost model spanning compute throughput, storage bandwidth, and remote fetch amplification. The resulting structure provides a principled path to predictable retrieval quality under faults while exploiting mixed hardware without assuming homogeneous performance or uniform durability.

• PDF

Copyright (c) 2026 International Journal of Scientific and Applied Computing Research

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.