View in EDS

Uncoded Placement With Linear Sub-Messages for Private Information Retrieval From Storage Constrained Databases.

Saved in:
Bibliographic Details
Title: Uncoded Placement With Linear Sub-Messages for Private Information Retrieval From Storage Constrained Databases.
Authors: Woolsey, Nicholas1 nicholas.woolsey@utah.edu, Chen, Rong-Rong1 rchen@ece.utah.edu, Ji, Mingyue1 mingyue.ji@utah.edu
Source: IEEE Transactions on Communications. Oct2020, Vol. 68 Issue 10, p6039-6053. 15p.
Subjects: Information organization, Information retrieval, Databases
Abstract: We propose capacity-achieving schemes for private information retrieval (PIR) from uncoded databases (DBs) with both homogeneous and heterogeneous storage constraints. In the PIR setting, a user queries a set of DBs to privately download a message, where privacy implies that no one DB can infer which message the user desires. In general, a PIR scheme is comprised of storage placement and delivery designs. Previous works have derived the capacity, or infimum download cost, of PIR with uncoded storage placement and sufficient conditions of storage placement to meet capacity. However, the currently proposed storage placement designs require splitting each message into an exponential number of sub-messages with respect to the number of DBs. In this work, when DBs have the same storage constraint, we propose two simple storage placement designs that satisfy the capacity conditions. Then, for more general heterogeneous storage constraints, we translate the storage placement design process into a “filling problem”. We design an iterative algorithm to solve the filling problem where, in each iteration, messages are partitioned into sub-messages and stored at subsets of DBs. All of our proposed storage placement designs require a number of sub-messages per message at most equal to the number of DBs. [ABSTRACT FROM AUTHOR]
Copyright of IEEE Transactions on Communications is the property of IEEE and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
FullText Text:
  Availability: 0
Header DbId: egs
DbLabel: Engineering Source
An: 146512713
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: Uncoded Placement With Linear Sub-Messages for Private Information Retrieval From Storage Constrained Databases.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Woolsey%2C+Nicholas%22">Woolsey, Nicholas</searchLink><relatesTo>1</relatesTo><i> nicholas.woolsey@utah.edu</i><br /><searchLink fieldCode="AR" term="%22Chen%2C+Rong-Rong%22">Chen, Rong-Rong</searchLink><relatesTo>1</relatesTo><i> rchen@ece.utah.edu</i><br /><searchLink fieldCode="AR" term="%22Ji%2C+Mingyue%22">Ji, Mingyue</searchLink><relatesTo>1</relatesTo><i> mingyue.ji@utah.edu</i>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22IEEE+Transactions+on+Communications%22">IEEE Transactions on Communications</searchLink>. Oct2020, Vol. 68 Issue 10, p6039-6053. 15p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Information+organization%22">Information organization</searchLink><br /><searchLink fieldCode="DE" term="%22Information+retrieval%22">Information retrieval</searchLink><br /><searchLink fieldCode="DE" term="%22Databases%22">Databases</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: We propose capacity-achieving schemes for private information retrieval (PIR) from uncoded databases (DBs) with both homogeneous and heterogeneous storage constraints. In the PIR setting, a user queries a set of DBs to privately download a message, where privacy implies that no one DB can infer which message the user desires. In general, a PIR scheme is comprised of storage placement and delivery designs. Previous works have derived the capacity, or infimum download cost, of PIR with uncoded storage placement and sufficient conditions of storage placement to meet capacity. However, the currently proposed storage placement designs require splitting each message into an exponential number of sub-messages with respect to the number of DBs. In this work, when DBs have the same storage constraint, we propose two simple storage placement designs that satisfy the capacity conditions. Then, for more general heterogeneous storage constraints, we translate the storage placement design process into a “filling problem”. We design an iterative algorithm to solve the filling problem where, in each iteration, messages are partitioned into sub-messages and stored at subsets of DBs. All of our proposed storage placement designs require a number of sub-messages per message at most equal to the number of DBs. [ABSTRACT FROM AUTHOR]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>Copyright of IEEE Transactions on Communications is the property of IEEE and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=146512713
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1109/TCOMM.2020.3010988
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 15
        StartPage: 6039
    Subjects:
      – SubjectFull: Information organization
        Type: general
      – SubjectFull: Information retrieval
        Type: general
      – SubjectFull: Databases
        Type: general
    Titles:
      – TitleFull: Uncoded Placement With Linear Sub-Messages for Private Information Retrieval From Storage Constrained Databases.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Woolsey, Nicholas
      – PersonEntity:
          Name:
            NameFull: Chen, Rong-Rong
      – PersonEntity:
          Name:
            NameFull: Ji, Mingyue
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 10
              Text: Oct2020
              Type: published
              Y: 2020
          Identifiers:
            – Type: issn-print
              Value: 00906778
          Numbering:
            – Type: volume
              Value: 68
            – Type: issue
              Value: 10
          Titles:
            – TitleFull: IEEE Transactions on Communications
              Type: main
ResultId 1