Results 1 to 4 of 4

Thread: Homomorphic compression

  1. #1
    Member SolidComp's Avatar
    Join Date
    Jun 2015
    Location
    USA
    Posts
    353
    Thanks
    131
    Thanked 54 Times in 38 Posts

    Homomorphic compression

    Hi all – Has anyone worked on homomorphic compression codecs? Is this a vibrant area of research? I first learned of the concept when I stumbled on XGrind, an XML compressor that lets you access the data without decompressing it – that's what I mean by homomorphic.

    There's a recent paper by Jang, Na, and Yoon about homomorphic parameter compression for deep learning training data. I've only found a handful of papers, so I guess that answers my second question... There's another paper about using RLE with encrypted data.

    I ultimately want a data serialization format that is more efficient than Protocol Buffers, FlatBuffers, and MessagePack. Ideally it would be homomorphic and/or extremely fast to unpack. From a programmer perspective I wonder if super fast unpacking is as good, or nearly as good, as technically homomorphic. If we had something for small data, with SLZ-like overhead (almost zero), that compressed better than gzip 9, well that would be awesome.

    It strikes that static Huffman tables gives you something close to homomorphic since you know what all the symbols represent in advance. I guess it's not technically homomorphic since logically there's a decoding step, but realistically any act of parsing would seem to rely on exogenous data or awareness, so I'm not clear on the definition and boundary here.

  2. #2
    Member
    Join Date
    Jun 2015
    Location
    Switzerland
    Posts
    876
    Thanks
    242
    Thanked 325 Times in 198 Posts
    Quote Originally Posted by SolidComp View Post
    I ultimately want a data serialization format that is more efficient than Protocol Buffers, FlatBuffers, and MessagePack. Ideally it would be homomorphic and/or extremely fast to unpack. From a programmer perspective I wonder if super fast unpacking is as good, or nearly as good, as technically homomorphic. If we had something for small data, with SLZ-like overhead (almost zero), that compressed better than gzip 9, well that would be awesome.

    It strikes that static Huffman tables gives you something close to homomorphic since you know what all the symbols represent in advance. I guess it's not technically homomorphic since logically there's a decoding step, but realistically any act of parsing would seem to rely on exogenous data or awareness, so I'm not clear on the definition and boundary here.
    Riegeli in transposed mode has such properties. Within the riegeli format you can do some filtering, search for attributes, or search a sorted key in O(log n) in a riegeli file without decompressing. You can do more complicated stuff with partial decompression.

  3. Thanks:

    SolidComp (16th June 2020)

  4. #3
    Member SolidComp's Avatar
    Join Date
    Jun 2015
    Location
    USA
    Posts
    353
    Thanks
    131
    Thanked 54 Times in 38 Posts
    Nice. Never heard of riegeli before. Is there a paper?

  5. #4
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,977
    Thanks
    296
    Thanked 1,304 Times in 740 Posts

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •