Published rANS patent by Storeleap

[Jarek]

Last year there was information about rANS patent ( http://cbloomrants.blogspot.com/2015...e-fucking.html ), it is now published:
https://www.ipo.gov.uk/p-ipsum/Case/...er/GB1502286.6
https://www.ipo.gov.uk/p-ipsum/Docum...20document.pdf
Here is a timeline for UK Patent application: http://www.withersrogers.com/wp-cont..._time_line.pdf

It seems extremely general:
Title: "System and method for compressing data using asymmetric numeral systems with probability distributions"
Abstract: "A data compression method using the range variant of Asymmetric Numeral Systems, rANS, to encode a data stream, where the probability distribution table(s) used is constructed using a Markov model. A plurality of probability distribution tables may be used each constructed from a subset of the data stream and each used to encode another subset of the data stream. The probability distribution table may compromise a special code (or 'escape code') which marks a temporary switch to second probability distribution table. The probability distribution table itself may be stored in a compressed format. The data stream may be information containing gene sequences or related information."

How to fight it?

update: there is also US patent application - http://www.freepatentsonline.com/y2016/0248440.html

update1: editable Google doc to reply to the patent - please add a short description about your earlier than 11.02.2015 connected compressor (or some you know, or e.g. paper) - emphasizing similarities:
https://docs.google.com/document/d/1-86_o0fzTHs6TyU4TaF-ufOZ4Xr3zEskyLYI6Nehavw/edit

update2: non-final rejection for the US application with comments from USPTO expert:
https://register.epo.org/ipfwretrieve?apn=US.201615041228.A&lng=en
https://dl.dropboxusercontent.com/u/...1479580692.pdf

[Sportman]

I shall first phone him to check when he invented it with what proof:

http://www.petagene.com/
(beta.companieshouse.gov.uk/company/10100283/officers)

http://www.storleap.com/contact.html
http://www.fonleap.com/about/
(beta.companieshouse.gov.uk/company/07362405/officers)

If you are part of the conversation then you are allowed to (secret) record it.

[Nania Francesco]

This I think is one of the reasons why I don't put my open source programs. Surely fatherhood is Jarek and legal action at the right time is due.
All will check how much different it was presented as a theory and practice.

[dnd]

IANAL, but i think the filed date is decisive for prior art.
- date of filing of the patent: 11.02.2015
- Interleaved entropy coders submitted: 14.02.2014
- Ryg_rans initial version : 02.02.2014

[Jarek]

Sportman, there is more than a year for the fight - let us prepare first.

Nania, being closed-source is not sufficient (e.g. https://github.com/powzix/kraken ) - much better protection from patent trolls should be making idea public with a good open documentation, like arxiv or at least Google discussion forum (using discussion forum on private server like encode.su seems easier to discredit ... unless there is a copy e.g. on archive.org).

dnd, so they emphasize using Markov - it is definitely mentioned in my earlier arxiv, but first open order1 rANS implementation came probably with CRAM 3.0, which is 1st June 2015 (?)
https://samtools.github.io/hts-specs/CRAMv3.pdf
Is there anything else really new there as for 11.02.2015?
ps. they cite both my and Fabian's arxiv.

[LawCounsels]

they can only ever be granted patent on some narrow particular improvement feature/s and only if really non-obvious to a person skill in the art

even today anyone can apply patent on specific narrow particular improvement feature part which are really non-obvious

ANS is safe !

[JamesB]

Sportman, there is more than a year for the fight - let us prepare first.

Nania, being closed-source is not sufficient (e.g. https://github.com/powzix/kraken ) - much better protection from patent trolls should be making idea public with a good open documentation, like arxiv or at least Google discussion forum (using discussion forum on private server like encode.su seems easier to discredit ... unless there is a copy e.g. on archive.org).

dnd, so they emphasize using Markov - it is definitely mentioned in my earlier arxiv, but first open order1 rANS implementation came probably with CRAM 3.0, which is 1st June 2015 (?)
https://samtools.github.io/hts-specs/CRAMv3.pdf
Is there anything else really new there as for 11.02.2015?
ps. they cite both my and Fabian's arxiv.

Order-1 rANS, as used in CRAM, was released publically in Feb 2014 (here):

http://encode.su/threads/1867-Unroll...ll=1#post36630

Infact I think it was this work that got these people interested in higher order rANS in the first place as they were looking at existing bioinformatics data formats. This certainly means the earlier rANS work is all fine and free.

This particular patent doesn't seem to be claiming invention of rANS, but rather the methods of using it in conjunction with higher order models. We already have PPM using arithmetic coding and this is primarly a claim to replace PPM + AC with PPM + ANS instead. Yes, it's "novel", but only because everything + ANS was novel once ANS arrived. To a skilled practitioner of data compression it would be blatantly obvious that replacing one entropy encoder with a newer entropy encoder is not an inventive step. There are a few foibles surrounding the reverse order of rANS in conjuction with a context, but the static order-1 rANS had already demonstrated one solution to this.

There are specifics about SIMD construction, which perhaps are more in line with the work of Charles and Fabian using rANS as a true adaptive coder rather than static construction. I don't know if others had any (or discussed openly) adaptive rANS before this filing date and whether SIMD was mentioned. I haven't had time for more than a cursory glance through it so far though.

Edit: also see Fabian Giesen's paper on interleaving ANS. This explicitly mentions both SIMD and adaptive modelling. Eg:
"For adaptive models, they can still be vectorized safely as long as no two SIMD lanes ever try to update the same model at the same time; one way to ensure this is to keep separate contexts for every SIMD lane."

https://arxiv.org/abs/1402.3392

Regarding claim 6, I clearly stated use of ANS for genomic data in 2014: https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4173023/
"This demonstrates room for improvement in future CRAM versions, partially achieved by replacing Zlib with arithmetic coding or an Asymmetric Numerical System (Duda, 2013)."

[Sportman]

Sportman, there is more than a year for the fight - let us prepare first.

You don't want a lawsuit also they are backed by the UK government agency Innovate UK:

https://www.gov.uk/government/organi...ovate-uk/about

http://gtr.rcuk.ac.uk/projects?ref=710579
http://gtr.rcuk.ac.uk/organisation/F...2-549733A77783

Better first talk with him and Innovate UK if they can stop the patent application process or add your name.

The best protection is fill your own patent before somebody else do it.

[LawCounsels]

EPO patent applications page has button for public to submit comments / evidences on prior arts/ novelty/ non-obviousness to Examiners notice

UKIPO likewise or similar mechanism

if unreasonable not acted upon granted patents regularly gets invalidated in courts of law by Defendant corporations

[JamesB]

You don't want a lawsuit also they are backed by the UK government agency Innovate UK:

https://www.gov.uk/government/organi...ovate-uk/about

http://gtr.rcuk.ac.uk/projects?ref=710579
http://gtr.rcuk.ac.uk/organisation/F...2-549733A77783

Better first talk with him and Innovate UK if they can stop the patent application process or add your name.

The best protection is fill your own patent before somebody else do it.

That's really just a funding agency, but I agree it's best to speak to them first and ask if they'll just drop it.

I did speak to Dan Greenfield early on and he was rather embarrassed by the whole affair, explaining that they're more or less obliged to create patents as they're "magic pixie dust" to investors who like to see something concrete for their money. So perhaps they're now with a new investor or have milked it for what they needed (gaining favour with a funder) and don't really care about the patent itself. Worth asking.

I don't like the whole "file your own patent before somebody else" approach though. Publishing is sufficient to block patents, especially if you include a bunch of "and here are some of the cool ideas we could improve on this" statements so block patents with obvious extensions. Basically anything you put in a patent could also be put up in a public github repository and have the same impact (I think) with regards to being prior art. I'm not sure what more having a patent really grants you if it's just the protection against other patents. (With the usual IANAL disclaimers.)

[Bulat Ziganshin]

there is one obvious difference. by publishing code you show just one way to implement that. in patent, you can descriobe idea as general as possible, even if it's obvious

[JamesB]

there is one obvious difference. by publishing code you show just one way to implement that. in patent, you can descriobe idea as general as possible, even if it's obvious

What if you publish a description of the idea, written to be as general as possible (exactly as would appear in the patent)?

I'm probably missing something important though, or maybe that's just what the patent lawyers want us to believe!

[thorfdbg]

What if you publish a description of the idea, written to be as general as possible (exactly as would appear in the patent)?

Certainly prior art. So for example, if you have a publication of a paper with a documented publication date, then the idea described in the paper cannot be patented anymore. Same here: Apparently, the idea was already described in this forum. So the best that can be done is to collect sufficient evidence, such as print out the web-page for a start, ask the administrator to check for logs, collect witnesses that can provide evidence that the article really existed before the patent application. In the end, I would suggest that Jarek just continues to use the algorithm. What is the worst that could happen? In the end, the "patent holder" would have to go do court, and would then have a hard standing providing evidence that he invented it first. Hence, it would be outright stupid to sue anyone. It's probably just patented to claim that the patenting company owns some "intellectual property" to collect some money from investors that are stupid enough to believe the claims. Thus, I doubt that this patent will withstand in court.

[JamesB]

I don't think they're claiming ownership of the rANS algorithm, and indeed they even reference Jarek's papers so it's obvious there is prior art there.

Their claims are around applications of the algorithm, specifically how to do incremental updates to the frequency table piece meal. Instead of building statistics on a block of data and then encoding that same block of data, they are using statistics from a previous block to encode the next block with an escape mechanism for handling new observations that would otherwise be predicted with zero probability. This is pretty standard techniques, but applied around rANS instead of arithmetic coding.

That makes it less obvious to challenge (unless there is specific prior art of that technique in conjunction with ANS too) as it then boils down to deciding whether the invention is obvious to someone skilled in the art. One avenue here is to look at what techniques have been applied using arithmetic coding and then to decide whether changing arithmetic coding with ANS is an obvious step and not inventive. Personally I'd hope that this can be demonstrated as otherwise it just opens the floodgates of "X + ANS" patents for all X where we currently use "X + AC".

[LawCounsels]

I don't think they're claiming ownership of the rANS algorithm, and indeed they even reference Jarek's papers so it's obvious there is prior art there.

Their claims are around applications of the algorithm, specifically how to do incremental updates to the frequency table piece meal. Instead of building statistics on a block of data and then encoding that same block of data, they are using statistics from a previous block to encode the next block with an escape mechanism for handling new observations that would otherwise be predicted with zero probability. This is pretty standard techniques, but applied around rANS instead of arithmetic coding.

That makes it less obvious to challenge (unless there is specific prior art of that technique in conjunction with ANS too) as it then boils down to deciding whether the invention is obvious to someone skilled in the art. One avenue here is to look at what techniques have been applied using arithmetic coding and then to decide whether changing arithmetic coding with ANS is an obvious step and not inventive. Personally I'd hope that this can be demonstrated as otherwise it just opens the floodgates of "X + ANS" patents for all X where we currently use "X + AC".

this a standard techniques routine common considered OR seen with other compression methods ? then prima facie non-inventive

rare exception is where this particular 'X + ANS' combination brings about unexpected ( very much beyond that one would normally expect from X introduction contribution ) astounding magnitude/s of improvement usually solved a pent-up long felt need in the market

anyone with the good luck stumble upon such should always proceed apply for patent first before 'talking'

[Jarek]

It turns out it's not only UK, there is also US application: http://www.freepatentsonline.com/y2016/0248440.html

[Nania Francesco]

Jarek, hope you can win, in this sad story!

[Jarek]

Thanks Nania, there is no way I could afford lawyers specializing in UK and US patent law, and if it will be granted and e.g. sold to a patent troll, they will not sue me but the companies which can gain financial benefits from it, like bio-informatics, RAD Tool Games or Google (I have noticed) - I hope they feel financially motivated to fight this very general patent.

It seems just rANS + some PPM, there is needed:
1) documentation about existence of similar earlier PPM approaches, how different the proposed approach is? I am aware that there are dozens of them (PPM, DMC, CTW), but haven't studied them in details - which one is the closest?

2) some kind of review of law and cases where "A + X" and "B" are known, and somebody wants to patent "B + X" - separately for US and UK. Where is the boundary of obviousness?

The second point seems to require a specialized lawyer ...

[Bulat Ziganshin]

i'm not sure but my CM used lower-order contexts to encode stats for higher-order contexts. together with Jarek's idea mentioned in his paper that ANS can replace arithmetic in any algo, this looks to cover at least the general idea of this patent?

[Jarek]

Great, let's gather such similar approaches - briefly describing similarities and differences, and prepare a document from it - to report to the patent offices.

update: editable Google doc - please add a short description about your compressor (or some you know) - emphasizing similarities and differences:
https://docs.google.com/document/d/1...YI6Nehavw/edit

[JamesB]

What is the precise definition of a Markov Model? The Wikipedia page isn't desparately clear, but it implies use of the current state than actual history for computing the probabilities of transitions to new states.

UK patent claim 1 ("rANS utilises a probability distribution table that is constructed using a Markov Model): I think my order-1 rANS is a (very simple) Markov Model in as far as the current state represents the last symbol and the probabilities are derived from the entire block of data. That makes it a static model rather than an adaptive one, but I believe it still qualifies. I don't know if I ever posted anywhere public about ideas for higher order models (for sure I had them as it's obvious, but deemed the compression improvement for my specific task to be too small to warrant the extra complexity).

Claim 5 ("probability distribution table saved in non-volatile storage in a compressed format") is also done in my code. Admittedly it's a poor compression, just using variable sized integers to squash 12 bit quantities to 8 bit whenever able and RLE. I did experiment with shoving the entire order-1 table through the order-0 codec, but also deemed it not worth while on the types of data I was dealing with. Again, I don't know if there are remnants of this in the code anywhere, but even simplistic byte packing is compression and sufficient I think. There was also discussion on ways of compressing the frequencies using Gamma coding on the public cram-dev mailing list in March 2014. Eg see http://listserver.ebi.ac.uk/pipermai...ch/000435.html and http://listserver.ebi.ac.uk/pipermai...ne/000491.html

Claim 6 ("data stream contains gene sequences or other related information") is covered by CRAM. The DNA bases are stored as delta to the reference, but this is often order-0 rans. "Related information" would be quality values of each dna nucleotide, which is usually encoded with order-1 model plus rans.

Other claims are simply legalese for previous claims + computer/storage and irrelevant if the earlier claims do not hold up.

[Bulat Ziganshin]

afaik "order-N" is just common shorthand for "order-N Markov model", so you definitely use Markov model

[nemequ]

Jarek,

For the US, at least, I would suggest contacting the EFF and/or the SFLC; they may be able to help you. rANS is pretty important, so blocking this early would be a big win for them.

Another idea would be contacting the Alliance for Open Media to ask for help. IIRC they're considering ANS for some stuff, blocking a patent on it would be in their interest, and it certainly wouldn't hurt to have Google, Microsoft, Cisco, Amazon, Netflix, etc. on your side (and I'm sure they all have plenty of lawyers).

Edit: Even if they're not planning on using it, they may want to in the future so it's still in their best interest to kill this patent application.

[dnd]

Some pointers using similar methods:

1 - Lookup for a key using SIMD is pretty elementar:
- How fast can you make linear search?

2 - Symbol decoding using a two levels tree structure (used also in oodle)
- file "qsmodel.c"
- Comparative Analysis of Arithmetic Coding Computational Complexity
- file "arithmetic_codec.cpp" in FastAC

3 - Using contexts with adaptive arithmetic coding
- Comparative Analysis of Arithmetic Coding Computational Complexity
- Introduction to Arithmetic Coding Theory and Practice
- file "acfile.cpp" in FASTAC

4 - Compression of the probability distribution in ANS
Reducing the header - optimal quantization/compression of probability distribution?

5 - Using an escape code for previously unseen symbols:
Arithmetic Coding + Statistical Modeling = Data Compression

PS: This is the first post mentioning the patent

[Jarek]

Non-final rejection for the US application with comments from USPTO expert:
https://register.epo.org/ipfwretriev...41228.A&lng=en

All claims but 4, 10 and 16 are rejected.

"4. The method according to claim 1, wherein the probability distribution table is extended with an escape code to form an extended probability distribution table, wherein the escape code is used to mark a temporary switch to a secondary probability distribution table for encoding transitions or symbols in the data stream that cannot be encoded using said probability distribution table.

10. The system as set forth in claim 7, wherein the computing hardware is further configured to extend the probability distribution table with an escape code, wherein the escape code is used to mark a temporary switch to a secondary probability distribution table for encoding transitions or symbols in the data stream that cannot be encoded using said probability distribution table.

16. The non-transitory computer-readable medium of claim 13, wherein the instructions further cause the processor to extend the probability distribution table with an escape code, wherein the escape code is used to mark a temporary switch to a secondary probability distribution table for encoding transitions or symbols in the data stream that cannot be encoded using said probability distribution table."

So of question is the use of "escape symbol".

[Bulat Ziganshin]

it looks like a very definition of escape symbol in PPM model

[JamesB]

Did any submission get made to the UK patent office? I'm wondering if I should comment on it. I know the US one got (mostly) rejected, although the remaining bits are arguably incorrect too.

Edit: I'll send something anyway as I can counter all bar claims 2 and 3. I don't think it's an issue if they get rebuttals from multiple sources. I should have done this ages ago!

[Jarek]

There is nothing new in the UK website since publishing: https://www.ipo.gov.uk/p-ipsum/Case/...er/GB1502286.6
Let me know if you think I should try to do something about it.

[JamesB]

I sent you an email of my comments to them. Although in due course they will be made public, I've no idea how long that takes.

[Jarek]

I have just found a recently published Google patent application mentioning ANS - which seems extremely general regarding data compression:
"Folded integer encoding"
"Techniques of data compression involve performing a separate compression operation on each set of corresponding bits of a sequence of bit strings in which each bit string represents a number having an upper bound. Advantageously, compressing the sets of corresponding bits produces an improved compression ratio over compressing each number in the sequence. Further, decompression is straightforward as long as sequence order is preserved and the upper bound of each number in the sequence is known."
http://patents.justia.com/patent/9595976

update: It seems granted (in a few months?) ... http://patents.com/us-9595976.html
It is hard to say what it really claims without the pictures, but the "subdivision of the bounding box" suggests it's related to Google Draco, however, I don't see intersecting authors
patent: Hemmer; Michael (San Francisco, CA), Stava; Ondrej (San Jose, CA)
Draco: https://github.com/google/draco/graphs/contributors

Subdivision of bounding box while storing an unsorted set of numbers is a very basic technique, e.g. http://fabpedigree.com/james/appixm.htm or https://arxiv.org/pdf/1206.4555