Judy arrays are patented(en.wikipedia.org)
en.wikipedia.org
Judy arrays are patented
http://en.wikipedia.org/wiki/Judy_array#Drawbacks
59 comments
The fact that it takes a lawyer to even guess whether a patent applies, and that the typical strategy is to keep a low profile and hope nobody notices, is itself a serious flaw in the patent system. Any system in which it's impossible to predict ahead of time what is safe or legal is broken.
Not to mention the fact that engineers are routinely advised to never read patents, since doing so would increase liability when they inevitably independently reinvent the same obvious idea.
Humans are a learning algorithm in a body. Very, very few learning algorithms incorporate original thought, because it's computationally expensive. Extremely, extremely expensive. Genetic algorithms are close to the only ones and the best reason to use generic algorithms is when you have no example data whatsoever, and even with datacenters full of machines, a lot of patience is required. Otherwise, genetic algorithms are going to get clobbered in performance by almost every other algorithm.
Which brings me to my point : imho the chances that humans are capable of real original thought is nil. Don't get me wrong, humans are very capable of creatively combining ideas from very different disciplines and non-human sources to arrive at surprising insights and works. But I'm pretty sure humans are not in fact capable of creating something out of nothing, even when it comes to intellectual works.
Which brings me to my point : imho the chances that humans are capable of real original thought is nil. Don't get me wrong, humans are very capable of creatively combining ideas from very different disciplines and non-human sources to arrive at surprising insights and works. But I'm pretty sure humans are not in fact capable of creating something out of nothing, even when it comes to intellectual works.
Especially when it is the theoretical target audience (other engineers!) that can't understand them.
What a pity the lawyers have misinterpreted the patent to mean that the application's language itself should be non-obvious to a person having ordinary skill in the art.
At the same time, Doug Baskins, the author of Judy, open sourced an implementation under the LGPL [1]. This license insists "that any patent license obtained for a version of the library must be consistent with the full freedom of use specified in this license." [2]
[1] http://judy.sourceforge.net/downloads/10minutes.htm
[2] http://www.gnu.org/licenses/lgpl-2.1.html
[1] http://judy.sourceforge.net/downloads/10minutes.htm
[2] http://www.gnu.org/licenses/lgpl-2.1.html
You can patent a data structure!? Seriously? This is straight up an abstract idea. I think non-abstract patents are beneficial and help society. This is just plain idiocy.
Did you see how complex the data structure actually is? If I had to choose between implementing a Judy array and implementing JPEG, I'd much rather try to write the JPEG code.
Patenting a data structure sounds ridiculous, but it's a little less ridiculous once you consider how complex the underlying algorithms actually are.
Patenting a data structure sounds ridiculous, but it's a little less ridiculous once you consider how complex the underlying algorithms actually are.
So... I can patent complicated math? This is essentially what you are saying, right?
That's not what I'm saying and you know it. Please don't turn my point into a caricature.
JPEG was patented. I can understand why. It was novel, it was not obvious, and it was useful. That trio makes a pretty good case for patentability, ignoring whether algorithms can/should be patented in general.
From what I've read, Judy arrays are novel, not obvious (moreso than JPEG, in my subjective opinion), and useful. So it doesn't seem far fetched to patent Judy arrays, ignoring whether algorithms can/should be patented in general.
Which is why I said "a little less ridiculous". This has nothing to do with complicated math, even though both data structures/algorithms involve complicated math.
JPEG was patented. I can understand why. It was novel, it was not obvious, and it was useful. That trio makes a pretty good case for patentability, ignoring whether algorithms can/should be patented in general.
From what I've read, Judy arrays are novel, not obvious (moreso than JPEG, in my subjective opinion), and useful. So it doesn't seem far fetched to patent Judy arrays, ignoring whether algorithms can/should be patented in general.
Which is why I said "a little less ridiculous". This has nothing to do with complicated math, even though both data structures/algorithms involve complicated math.
> It was novel, it was not obvious, and it was useful.
You could say the same of the Pythagorean theorem, or FFT. Thankfully in the case of the later, IBM's patent lawyers exhibited sanity.
You could say the same of the Pythagorean theorem, or FFT. Thankfully in the case of the later, IBM's patent lawyers exhibited sanity.
All software patents are patents on complicated math.
From what I've seen software patents seems to be mostly trivial math.
Trivial math with a relatively inaccessible notation. The notation is why most people seem to have a hard time recognizing it as math I think, people have tunnel-vision and think of "math" as the stuff they learned in primary school.
Non-trivial theoretical basis, reduced to trivial math for implementation.
JPEG and wavelet compression in practice is surprisingly simple math. But the theory that explains why and how it works is far from trivial.
JPEG and wavelet compression in practice is surprisingly simple math. But the theory that explains why and how it works is far from trivial.
All inventions are complicated math.
No, some inventions are describable with math. Some 'inventions' are math. A Wankel engine is not math. You can model it and describe it with math, but that is irrelevant.
Any equation that you can make will merely describe a Wenkel engine, not be one. Equations for mathematical concepts are those concepts (expressed in a particular format).
Any equation that you can make will merely describe a Wenkel engine, not be one. Equations for mathematical concepts are those concepts (expressed in a particular format).
A distinction without a difference.
You really don't see a difference?
If I write out a book parametrization a Wankel engine and describing the chemistry and physics of the system necessary to make it turn, I have not implemented a Wankel engine, and I am in violation of no patents. It is a description of the engine, not an engine.
A mathematical description of an algorithm can be executed. It is the algorithm. The description is an implementation and any implementation is the description. There is literally no line between the two, the only thing that you can change is the notation in which you write it.
If you don't see the difference, you are just being obtuse. The difference is as plain the difference between physics and mathematics.
If I write out a book parametrization a Wankel engine and describing the chemistry and physics of the system necessary to make it turn, I have not implemented a Wankel engine, and I am in violation of no patents. It is a description of the engine, not an engine.
A mathematical description of an algorithm can be executed. It is the algorithm. The description is an implementation and any implementation is the description. There is literally no line between the two, the only thing that you can change is the notation in which you write it.
If you don't see the difference, you are just being obtuse. The difference is as plain the difference between physics and mathematics.
[deleted]
So is JPEG's complexity the cutoff for you? What do you think of the LZW patents then? LZW is simple as hell.
To be completely honest, I'm not sure where I stand because it's a very complex issue.
JPEG met the novelty, non-obviousness, and usefulness tests, as did LZW. That they're considered nearly trivial these days is because they were such influential algorithms that they've become part of the programming canon.
That said, please don't represent my stance as a matter of a cutoff. Many things in this world, including the question of patentability, are fuzzy distinctions that require some subjective "good judgement." Common law legal systems are bad at handling this, which is partly why judicial philosophy is so complex.
If I oppose patenting an algorithm/data structure, it's because I don't think patent protection is necessary in order for people to push the state of the art forward.
JPEG met the novelty, non-obviousness, and usefulness tests, as did LZW. That they're considered nearly trivial these days is because they were such influential algorithms that they've become part of the programming canon.
That said, please don't represent my stance as a matter of a cutoff. Many things in this world, including the question of patentability, are fuzzy distinctions that require some subjective "good judgement." Common law legal systems are bad at handling this, which is partly why judicial philosophy is so complex.
If I oppose patenting an algorithm/data structure, it's because I don't think patent protection is necessary in order for people to push the state of the art forward.
LZW isn't considered trivial because it has "become part of programming canon".
It is considered trivial because it is trivial: http://rosettacode.org/wiki/LZW_compression#Clojure
It is considered trivial because it is trivial: http://rosettacode.org/wiki/LZW_compression#Clojure
You're calling it trivial with over 30 years of advancements in computer science behind you. Also, thanks for picking the shortest sample on the page to show that it's trivial.
If it were trivial when the patentability question came up, it wouldn't have been a published paper in the IEEE Transactions on Information Theory and an active area of publication for at least the next six years.
Whether or not it's trivial today, this was the cutting edge of computer science when the patent was granted.
If it were trivial when the patentability question came up, it wouldn't have been a published paper in the IEEE Transactions on Information Theory and an active area of publication for at least the next six years.
Whether or not it's trivial today, this was the cutting edge of computer science when the patent was granted.
All of those examples are trivial, they're all the same algorithm. I merely picked one of the more terse, which really has nothing to do with triviality.
Seriously, read that.
You're calling it trivial with over 30 years of advancements in computer science behind you.
Yes, of course I fucking can. The ability to do that is part of what makes a "person having ordinary skill in the art" an important concept. Even 30 years ago LZW represented an incremental improvement on the current state of the art.
Regardless of the novelty of the idea, LZW has always been trivial to implement.
> it wouldn't have been a published paper in the IEEE Transactions on Information Theory and an active area of publication for at least the next six years.
I am not arguing that it fails the usefulness test, nor that it was not important.
Your "this looks like a pain in the ass to implement" defense of the patent is absurd. You clearly would support the patent regardless, since you seem to be fine with the LZW patents.
Seriously, read that.
You're calling it trivial with over 30 years of advancements in computer science behind you.
Yes, of course I fucking can. The ability to do that is part of what makes a "person having ordinary skill in the art" an important concept. Even 30 years ago LZW represented an incremental improvement on the current state of the art.
Regardless of the novelty of the idea, LZW has always been trivial to implement.
> it wouldn't have been a published paper in the IEEE Transactions on Information Theory and an active area of publication for at least the next six years.
I am not arguing that it fails the usefulness test, nor that it was not important.
Your "this looks like a pain in the ass to implement" defense of the patent is absurd. You clearly would support the patent regardless, since you seem to be fine with the LZW patents.
You didn't read everything I said about software patents. I oppose software patents because I don't think our society needs them. But then again, you can try to pidgeonhole my opinion if you want to.
I'm talking about patents. You're answering that LZW is trivial today. Yes, it is, but the time difference is huge when you're talking about a patent that is 30 years old and now public domain, especially when you're talking about a "person having ordinary skill in the art" regarding a patent application.
The great thing about threads like this is that we probably agree on the key points, but it becomes a disagreement the moment you escalate your language.
I'm talking about patents. You're answering that LZW is trivial today. Yes, it is, but the time difference is huge when you're talking about a patent that is 30 years old and now public domain, especially when you're talking about a "person having ordinary skill in the art" regarding a patent application.
The great thing about threads like this is that we probably agree on the key points, but it becomes a disagreement the moment you escalate your language.
Both the LZW patents and the Judy array patents are software patents...
I am not saying that LZW patents were bad patents because LZW is or was trivial. I am saying that defending Judy array patents because of Judy arrays are hard to implement is foolish because no such defense can be mounted for LZW.
The reason both should be unpatentable is that they are both algorithms.
I am not saying that LZW patents were bad patents because LZW is or was trivial. I am saying that defending Judy array patents because of Judy arrays are hard to implement is foolish because no such defense can be mounted for LZW.
The reason both should be unpatentable is that they are both algorithms.
Regarding patents, people always complain a particular patent couldn't have been granted because it's not novel enough, anyone could have thought it, or that it's math.
Patent law is a black-on-white subject, either you support it or not. It's impossible to grant some patents under subjective premises and be fair at the same time.
Patent law is a black-on-white subject, either you support it or not. It's impossible to grant some patents under subjective premises and be fair at the same time.
Patent law is not a black-and-white subject, and you certainly don't have to support all of it to support some of it. All law necessarily involves line drawing, and line drawing is subjective. Welcome to the wonderful world of being human and dealing with human society.
> It's impossible to grant some patents under subjective premises and be fair at the same time.
Is that not the job of patent examiners?
Is that not the job of patent examiners?
Blaming it on the examiner is not the point.
The idea behind patents is protecting the innovator. How does patent law protect anyone when it's trivial to argue a patent shouldn't have been granted in the first place (because it's not novel, or it's just math, blah blah)? You could say that about all patents ever filled.
It defeats the whole purpose behind patents. Whoever has the biggest patent pool and deepest pocket wins, not the little guy on the sweatshop. The only people to benefit from patents are lawyers.
The idea behind patents is protecting the innovator. How does patent law protect anyone when it's trivial to argue a patent shouldn't have been granted in the first place (because it's not novel, or it's just math, blah blah)? You could say that about all patents ever filled.
It defeats the whole purpose behind patents. Whoever has the biggest patent pool and deepest pocket wins, not the little guy on the sweatshop. The only people to benefit from patents are lawyers.
Be careful. The idea behind patents and IP law in general isn't protecting the innovator. It's incentivizing the innovator to advance society through new ideas. The subtle difference is that, when society no longer benefits from protecting the "innovator", that person shouldn't get protection from IP law.
Unfortunately, IP law today is a perversion of this original principle.
Unfortunately, IP law today is a perversion of this original principle.
I am not "blaming" anything on patent examiners. I am saying that they exist for their ability to interpret and decide. Were patent law black and white as you suggest, they would have no purpose.
As others have said, it is not black and white. You can support patents on "things" and not patents on "ideas." There's a big difference.
I can tell you mathematically how a windmill grinds corn but that does not make my description into a windmill. On the other hand, laying down the mathematical description of a Judy Array IS the array itself!
I can tell you mathematically how a windmill grinds corn but that does not make my description into a windmill. On the other hand, laying down the mathematical description of a Judy Array IS the array itself!
Well, I'm against software patents pretty much as much as anyone here, as you can verify from my comment history, but describing the mathematics of an array isn't the same as the array itself. The patent isn't violated until you start executing that mathematics of a Judy Array on a running computer. Otherwise, you could violate a patent by just talking about it.
You're saying the description of how a windmill works is not a description of a windmill, while the description of how the array works is a array.
How is that true? Isn't a description a model [1], never the thing itself?
[1] http://en.wikipedia.org/wiki/Conceptual_model
How is that true? Isn't a description a model [1], never the thing itself?
[1] http://en.wikipedia.org/wiki/Conceptual_model
[deleted]
Since the article has been updated and the "Drawbacks" section removed, here's the diff showing the original contents of the "Drawbacks" section that the story linked to, along with the deletion by user Fintler:
http://en.wikipedia.org/w/index.php?title=Judy_array&dif...
"Removed speculation that this subject is related to the referenced patent. Wikipedia is not a crystal ball or a place to discuss how the law MAY be applied."
http://en.wikipedia.org/w/index.php?title=Judy_array&dif...
"Removed speculation that this subject is related to the referenced patent. Wikipedia is not a crystal ball or a place to discuss how the law MAY be applied."
It's released under the LGPL, according to its COPYING file, by HP. I am pretty sure that means the patent doesn't matter; HP is granting you a license to use it.
Strictly speaking the LGPL is a license that relates to copyright, not patenting. A separate patent license would also be required, unless you use a copyright license that also includes patent terms (I haven't reviewed LGPL in awhile to confirm, and obviously you need to specify about what exact version of LGPL you're referring to anyways).
Any GPL (any version) explicitly forbids distributing the software with external conditions restricting its ability to be redistributed. That puts it at odds with almost any conceivable patent license.
I think you're underestimating the creativity of patent lawyers a bit.
For instance, just off the top of my head, consider this: "OK, you can distribute the source all you want, but as soon as you compile it, you've created a patented product, the binary of which you can't distribute."
After all, the patent itself is supposed to give all the description one needs of how to implement the patented invention, it's when you fix the patent into something real that you violate the patent.
Edit: What drove me to mentioning the separateness of patents and copyright was some of the discussion around GPLv3, e.g. http://fsfe.org/campaigns/gplv3/patents-and-gplv3.en.html#Ex...
For instance, just off the top of my head, consider this: "OK, you can distribute the source all you want, but as soon as you compile it, you've created a patented product, the binary of which you can't distribute."
After all, the patent itself is supposed to give all the description one needs of how to implement the patented invention, it's when you fix the patent into something real that you violate the patent.
Edit: What drove me to mentioning the separateness of patents and copyright was some of the discussion around GPLv3, e.g. http://fsfe.org/campaigns/gplv3/patents-and-gplv3.en.html#Ex...
IMHO your mistaken about the second part. You can have a separate patent license. If the patent holder distributes software under the GPL, this would effectively license the patent for the related GPL work, or it wouldn't be correctly licensed under the standard GPL.
If a separate implementation is NOT a derived GPL work, then patent licensing may be a factor.(IANAL etc.)
If a separate implementation is NOT a derived GPL work, then patent licensing may be a factor.(IANAL etc.)
Unfortunately, the copyright terms have nothing to do with whether you can actually use the algorithm/datastructure. It only means you can copy the source-code of a particular implementation of the algorithm/datastructure under the terms of the LGPL. If you want to actually run the code on a computer then you must contend with whatever enforcement or non-enforcement mechanism the author has in place for the patent.
As well as the doubly-linked list http://www.google.com/patents?id=Szh4AAAAEBAJ&printsec=a...
This is insane. The US patent system is beyond retarded.
I actually asked about this on the mailing list some time ago: http://comments.gmane.org/gmane.comp.lib.judy.devel/244
tl;dr: patent was done for defensive reasons.
tl;dr: patent was done for defensive reasons.
This has been true for quite a long time, and IIRC is why they're not more widely used. That and they're pretty complicated to implement properly.
They are only better for some workloads and not others. e.g., they are excellent for accessing data in-order, but are worse than a very simple hash table for random access:
http://preshing.com/20130107/this-hash-table-is-faster-than-...
(yes, this hash table is vulnerable to timing attacks; point is, for many workloads Judy brings in considerable complexity but is actually inferior to other solutions).
http://preshing.com/20130107/this-hash-table-is-faster-than-...
(yes, this hash table is vulnerable to timing attacks; point is, for many workloads Judy brings in considerable complexity but is actually inferior to other solutions).
Just an aside, but man, that's a refreshingly readable and pleasant article...
That, and because they need to be tuned for each individual cache line size.
See http://nothings.org/computer/judy/ for a more thorough analysis of Judy arrays (at 20 kLoC) versus straightforward hash tables (at 0.2 kLoC).
See http://nothings.org/computer/judy/ for a more thorough analysis of Judy arrays (at 20 kLoC) versus straightforward hash tables (at 0.2 kLoC).
Are we talking about the implementation is patented? Or the algorithm itself is patented?
You can't patent an algorithm, at least not in the U.S. The expression of an algorithm can be patented. Patent lawyers often tell people to replace an algorithm with a system, which is an expression of the algorithm.
You can't patent an algorithm, at least not in the U.S. The expression of an algorithm can be patented. Patent lawyers often tell people to replace an algorithm with a system, which is an expression of the algorithm.
Patents tend to be written like "any system that implements algorithm X" and "any machine-readable medium containing software that implements algorithm X", which is equivalent to a patent on the algorithm itself.
[deleted]
In case of patent lawyers, break glass and extract HAT-trie or crit-bit tree.
using System.Collections.Patented;
That's no problem, actually, even if it is patented, because Judy Array is not a concise algorithm or a data structure, but instead a compilation of a number of well-known unpatented data structures and algorithms, so you can basically change a couple of algorithms used there, and get out of the patent.
Patents use their own specific, strange language. The claims, as modified by other precedents, only apply in certain specific situations which may be different than what a casual reading would imply. And, for any of dozens of reasons the holder may not be interested in ever trying to enforce the patent.
So simply by raising the possibility, causing attention to be drawn, and uninformed discussions to be spawned, people's time is being wasted. If they become uneasy, or start spending engineering effort to 'work around' something that they hardly understand and that may never be enforced, more time is wasted.
And by getting more eyes on the fuzzy patent, you may have put more people/projects at risk of treble damages for 'willful infringement', in the rare case where the patent is actually enforced later, or undermined their ability to make a case for obviousness (because many teams came up with the same approach without seeing the patent).
The better policy is to ignore such "appears to be patented" reports, unless and until there's a credible threat from the holder(s) to enforce in specific ways, as checked by experts. Let these patents (and panicked overbroad interpretations) wither away in unenforced obscurity.