English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We propose a novel application of coded computing to the problem of thenearest neighbor estimation using MatDot Codes [Fahim. et.al. 2017], that areknown to be optimal for matrix multiplication in terms of recovery thresholdunder storage constraints. In approximate nearest neighbor algorithms, it iscommon to construct efficient in-memory indexes to improve query response time.One such strategy is Multiple Random Projection Trees (MRPT), which reduces theset of candidate points over which Euclidean distance calculations areperformed. However, this may result in a high memory footprint and possiblypaging penalties for large or high-dimensional data. Here we propose twotechniques to parallelize MRPT, that exploit data and model parallelismrespectively, by dividing both the data storage and the computation effortsamong different nodes in a distributed computing cluster. This is especiallycritical when a single compute node cannot hold the complete dataset in memory.We also propose a novel coded computation strategy based on MatDot codes forthe model-parallel architecture that, in a straggler-prone environment,achieves the storage-optimal recovery threshold, i.e., the number of nodes thatare required to serve a query. We experimentally demonstrate that, in theabsence of straggling, our distributed approaches require less query time thanexecution on a single processing node, providing near-linear speedups withrespect to the number of worker nodes. Through our experiments on real systemswith simulated straggling, we also show that our strategy achieves a fasterquery execution than the uncoded strategy in a straggler-prone environment.

An Application of Storage-Optimal MatDot Codes for Coded Matrix Multiplication: Fast k-Nearest Neighbors Estimation