Cache-Aided Multi-User Private Information Retrieval using PDAs
We consider the problem of cache-aided multi-user private information retrieval (MuPIR). In this problem, $N$ independent files are replicated across $S \geq 2$ non-colluding servers. There are $K$ users, each equipped with cache memory which can store $M$ files. Each user wants to retrieve a file from the servers, but the users don't want any of the servers to get any information about their demand. The user caches are filled with some arbitrary function of the files before the users decide their demands, known as the placement phase. After deciding their demands, users cooperatively send queries to the servers to retrieve their desired files privately. Upon receiving the queries, servers broadcast coded transmissions which are a function of the queries they received and the files, known as the delivery phase. Conveying queries to the servers incurs an upload cost for the users, and downloading the answers broadcasted by the servers incurs a download cost. To implement cache-aided MuPIR schemes, each file has to be split into $F$ packets. In this paper, we propose MuPIR schemes that utilize placement delivery arrays (PDAs) to characterize placement and delivery. Proposed MuPIR schemes significantly reduce subpacketization levels while slightly increasing the download cost. The proposed scheme also substantially reduces the upload cost for the users. For PDAs based on {\it Ali-Niesen} scheme for centralized coded caching, we show that our scheme is order optimal in terms of download cost. We recover the optimal single-user PIR scheme presented by {\it Tian et al.} as a special case. Our scheme also achieves optimal rate for single-user cache-aided PIR setup reported by R. Tondon.
Code (0)
등록된 구현이 없습니다.
Tasks
Information RetrievalRetrievalSimilar Papers 제목 키워드 기반
On the Fundamental Limits of Cache-aided Multiuser Private Information Retrieval
We consider the problem of cache-aided Multiuser Private Information Retrieval (MuPIR) which is an extension of the single-user cache-aided PIR problem to the case of multiple users. In MuPIR, each of the $K_{\rm u}$ cac…
Information RetrievalRetrievalOn Cache-Aided Multi-User Private Information Retrieval with Small Caches
In this paper, we propose a scheme for the problem of cache-aided multi-user private information retrieval with small caches, in which $K$ users are connected to $S$ non-colluding databases via shared links. Each databas…
AllInformation RetrievalRetrievalA New Design of Cache-aided Multiuser Private Information Retrieval with Uncoded Prefetching
In the problem of cache-aided multiuser private information retrieval (MuPIR), a set of $K_{\rm u}$ cache-equipped users wish to privately download a set of messages from $N$ distributed databases each holding a library …
Information RetrievalRetrievalCache-Aided Massive MIMO: Linear Precoding Design and Performance Analysis
In this paper, we propose a novel joint caching and massive multiple-input multiple-output (MIMO) transmission scheme, referred to as cache-aided massive MIMO, for advanced downlink cellular communications. In addition t…
Efficient Dynamic WFST Decoding for Personalized Language Models
We propose a two-layer cache mechanism to speed up dynamic WFST decoding with personalized language models. The first layer is a public cache that stores most of the static part of the graph. This is shared globally amon…
DecoderLanguage ModelingLanguage Modellingspeech-recognition+1