Researchers propose Onyx, a cost-efficient approach to disk-oblivious approximate nearest neighbor (ANN) search that balances bandwidth and access count by inverting the design of state-of-the-art ORAM-ANN systems.
Onyx introduces two co-designed components: Onyx-ANNS uses a compact intermediate representation to prune bandwidth-intensive accesses without hurting recall, while Onyx-ORAM employs a locality-aware shallow tree design to reduce access count. This approach minimizes bandwidth consumption in the ANN layer and access count in the ORAM layer, addressing the overutilization of SSD resources found in previous designs.
Compared to existing oblivious ANN search systems, Onyx achieves 1.7−9.9× lower cost and 2.3−12.3× lower latency.