7 ms·
Judy arrays are patented
- wheaties 14y agoYou 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.
- munchbunny 14y agoDid 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.
- taeric 14y agoSo... I can patent complicated math? This is essentially what you are saying, right?
- cma 14y agoAll inventions are complicated math.
- jlgreco 14y agoNo, 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).
- cma 14y agoA distinction without a difference.
- jlgreco 14y agoYou 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.
- cma 14y agohttp://en.wikipedia.org/wiki/Mathematical_universe_hypothesis http://en.wikipedia.org/wiki/Mathematical_universe_hypothesi...
- deleted 14y ago[deleted]
- 30thElement 14y agoAll software patents are patents on complicated math.
- tjoff 14y agoFrom what I've seen software patents seems to be mostly trivial math.
- jlgreco 14y agoTrivial 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.
- munchbunny 14y agoNon-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.
- munchbunny 14y agoThat'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.
- jlgreco 14y ago> 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.
- jlgreco 14y agoSo is JPEG's complexity the cutoff for you? What do you think of the LZW patents then? LZW is simple as hell.
- munchbunny 14y agoTo 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.
- jlgreco 14y agoLZW 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 http://rosettacode.org/wiki/LZW_compression#Clojure
- munchbunny 14y agoYou'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.
- jlgreco 14y ago
- hcarvalhoalves 14y agoRegarding 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.
- jlgreco 14y ago> 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?
- hcarvalhoalves 14y agoBlaming 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.
- jlgreco 14y agoI 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.
- munchbunny 14y agoBe 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.
- 14y ago
- codeulike 14y agousing System.Collections.Patented;
- zrail 14y agoThis 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.
- lsb 14y agoThat, and because they need to be tuned for each individual cache line size. See http://nothings.org/computer/judy/ http://nothings.org/computer/judy/ for a more thorough analysis of Judy arrays (at 20 kLoC) versus straightforward hash tables (at 0.2 kLoC).
- beagle3 14y agoThey 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-a-judy-array 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).
- snogglethorpe 14y agoJust an aside, but man, that's a refreshingly readable and pleasant article...
- rossjudson 14y agoIt'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.
- mpyne 14y agoStrictly 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).
- 0x09 14y agoAny 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.
- neurotech1 14y agoIMHO 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.)
- mpyne 14y agoI 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#Explicit-patent-grant http://fsfe.org/campaigns/gplv3/patents-and-gplv3.en.html#Ex...
- deleted 14y ago[deleted]
- gojomo 14y agoUnless you are a patent lawyer/expert specifically in someone's employ, pointing out that in your layman's opinion that "something appears to be patented" isn't doing anyone any favors, and may in fact be harming them. 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.
- nitrogen 14y agoThe 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.
- jlgreco 14y agoNot 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.
- waps 14y agoHumans 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.
- batgaijin 14y agoAs well as the doubly-linked list http://www.google.com/patents?id=Szh4AAAAEBAJ&printsec=abstract#v=onepage&q&f=false http://www.google.com/patents?id=Szh4AAAAEBAJ&printsec=a...
- dakimov 14y agoThis is insane. The US patent system is beyond retarded.
- dakimov 14y agoThat'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.
- kleiba 14y agoAt 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 http://judy.sourceforge.net/downloads/10minutes.htm [2] http://www.gnu.org/licenses/lgpl-2.1.html http://www.gnu.org/licenses/lgpl-2.1.html
- aspensmonster 14y agoSince 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&diff=532589496&oldid=531806885 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."
- cbsmith 14y agoIn case of patent lawyers, break glass and extract HAT-trie or crit-bit tree.
- ww520 14y agoAre 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.
- wmf 14y agoPatents 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.
- millrawr 14y agoI actually asked about this on the mailing list some time ago: http://comments.gmane.org/gmane.comp.lib.judy.devel/244 http://comments.gmane.org/gmane.comp.lib.judy.devel/244 tl;dr: patent was done for defensive reasons.