0
$\begingroup$

Imagine Google wanted to make their chrome browser faster. Let "database" be all the machines which serve content from Google's servers, including Search and Google cloud services. Google begins using machine learning to analyze thousands of petabytes of data on their database to extract a dictionary of the most redundant file sequences. Lets say the most redundant hexadecimal found was the sequence:

"64 65 63 69 6d 61 6c 20 66 6f 72 6d 61 74 2e 20 43 6f 6d 70 75 74 65 72 73 20 73 74 6f 72 65 20 74 65 78 74 20 61 73 20 6e 75 6d 62 65 72 73 2c 20 61 6e 64 20 77 69 74 68 20 68 65 78 20 79 6f 75 20 64 69 73 70 6c 61 79 20 74 68 65 20 6e 75 6d 62 65 72 73 20 6e 6f 74 20 61 73 20 61 20 64 65 63 69 6d 61 6c 20 6e 75 6d 62 65 72 2c 20 62 75 74 20 69 6e 20 62 61 73 65 20 31 36 2e 20 48 65 78 20 6f 72 20 62 61 73 65 20 31 36 20 6f 72 20 68 65 78 61 64 65 63 69 6d 61 6c 20 69 73 20 61 20 6e 75 6d 65 72 61 6c 20 73 79 73 74 65 6d"

They stored this sequence in their dictionary at index 1 and included this dictionary file in their Chrome update. For every user that had the latest Chrome update if they requested a file that had this sequence Google's server would return a flag and the index 1 (e.g. "D 1") such that the Chrome browser could lookup the bytes locally without the need of transferring them over the network. In essence the file being transferred would become something like "data data data D 1 data data"

Furthermore, they did this for gigabytes of sequences causing a larger Chrome update but faster file transfer times.

And to make things more interesting they used machine learning to analyze end-user behavior to predict which sequences were more likely to be requested.

After adding this functionality they achieved faster load times and decreased network congestion and possibly saved in electricity costs by removing redundancy across their entire network.

Questions:

What would this be called? Distributed Cached file transfer? Would this be practical or desirable? I imagine it could save money in terms of electricity for a large company like google.

$\endgroup$
  • $\begingroup$ It is not quite clear what you are asking. Are you asking whether this would be feasible? Whether it would get noticeable gains? Or are you asking whether it has been done before? Please ask only one question, this helps us keep answers focused. You can always ask any remaining questions in another thread. $\endgroup$ – Discrete lizard Mar 29 at 14:37
  • 2
    $\begingroup$ It's possible, probably not feasible though, and definitely not "better than perfect". Deep learning isn't required and probably isn't helpful; all you need is the space and patience to build a big enough suffix array. $\endgroup$ – j_random_hacker Mar 29 at 14:43
  • 1
    $\begingroup$ Chrome made a Webserver/browser Compression that is similar to what you are asking called "Brotli" See: en.wikipedia.org/wiki/Brotli . The issue of better than perfect is subject to interpretation. BACKUP software that removes/encode pointers to duplicates, get much better compression than is possible when compression only one copy of a data chunk. but to recover the data, the receiver must have the decode information to decompress. $\endgroup$ – Phillip Williams Mar 29 at 19:45
2
$\begingroup$

Is it possible to achieve greater than perfect compression...

No. Any lossless compression scheme that makes at least one string shorter must make at least one string longer. This is an unavoidable consequence of the simple fact that there are more long strings than short ones.

The best you can do is be smart about what strings get made shorter, and I guess that's what you're trying to do with machine learning, big data, and any other applicable buzzwordstechnologies. Effectively, though, you're trying to use a big global dictionary. This is probably less efficient than standard dictionary compression which builds up the dictionary from the data that's being compressed (a dictionary containing lots of Spanish and Chinese isn't going to be useful for compressing Stack Exchange, for example). Also, if you're going to cut network traffic, that big global dictionary needs to be already sitting on your computer, taking up huge amounts of space for dictionary entries you'll probably never use. Indeed, if that huge dictionary comes as part of my next Chrome update, it's not even obvious that there'll be a net saving in data transfer.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.