Asymptotic Bounds on the Length of Functional Batch and PIR Codes
Name
Teele Tars
Abstract
Batch codes were first introduced in 2004 by Ishai et al. to be used in
distributed storage systems for load balancing. Batch codes can be viewed as a special case of another family of codes called Private Information Retrieval (PIR) codes. PIR codes are used for retrieving information from a distributed storage system so that the
system does not know what information was requested. This thesis studies variants of batch and PIR codes called functional batch and functional PIR codes, respectively. For both of these types of codes, it is desirable to find codes that can support as many simultaneous queries as possible, while minimizing the storage overhead. Bounds on the length of these codes for a fixed query size are presented and a simplex-based near-optimal construction for these bounds is described. The bounds are compared with the minimum code lengths found by computer search.
distributed storage systems for load balancing. Batch codes can be viewed as a special case of another family of codes called Private Information Retrieval (PIR) codes. PIR codes are used for retrieving information from a distributed storage system so that the
system does not know what information was requested. This thesis studies variants of batch and PIR codes called functional batch and functional PIR codes, respectively. For both of these types of codes, it is desirable to find codes that can support as many simultaneous queries as possible, while minimizing the storage overhead. Bounds on the length of these codes for a fixed query size are presented and a simplex-based near-optimal construction for these bounds is described. The bounds are compared with the minimum code lengths found by computer search.
Graduation Thesis language
English
Graduation Thesis type
Bachelor - Computer Science
Supervisor(s)
Vitaly Skachek
Defence year
2024