8 ms·

Judy arrays are patented

42 points by CesareBorgia 14y ago

codeulike 14y ago
using System.Collections.Patented;
zrail 14y ago
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.
- lsb 14y ago
  That, 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 ago
  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-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 ago
    Just an aside, but man, that's a refreshingly readable and pleasant article...
wheaties 14y ago
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.
- munchbunny 14y ago
  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.
  - taeric 14y ago
    So... I can patent complicated math? This is essentially what you are saying, right?
    - cma 14y ago
      All inventions are complicated math.
      - jlgreco 14y ago
        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).
        cma 14y ago
        A distinction without a difference.
        jlgreco 14y ago
        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.
rossjudson 14y ago
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.
- mpyne 14y ago
  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).
  - 0x09 14y ago
    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.
    - neurotech1 14y ago
      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.)
    - mpyne 14y ago
      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#Explicit-patent-grant http://fsfe.org/campaigns/gplv3/patents-and-gplv3.en.html#Ex...
deleted 14y ago
[deleted]
gojomo 14y ago
Unless 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 ago
  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.
  - jlgreco 14y ago
    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.
    - waps 14y ago
      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.
batgaijin 14y ago
As 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 ago
  This is insane. The US patent system is beyond retarded.
dakimov 14y ago
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.
ww520 14y ago
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.
- wmf 14y ago
  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.
kleiba 14y ago
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 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 ago
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&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 ago
In case of patent lawyers, break glass and extract HAT-trie or crit-bit tree.
millrawr 14y ago
I 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.

42 points by CesareBorgia 14y ago

using System.Collections.Patented;

zrail 14y ago

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.

lsb 14y ago
That, 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 ago
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-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 ago
  Just an aside, but man, that's a refreshingly readable and pleasant article...

wheaties 14y ago

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.

munchbunny 14y ago
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.
- taeric 14y ago
  So... I can patent complicated math? This is essentially what you are saying, right?
  - cma 14y ago
    All inventions are complicated math.
    - jlgreco 14y ago
      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).
      - cma 14y ago
        A distinction without a difference.
        jlgreco 14y ago
        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.

rossjudson 14y ago

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.

mpyne 14y ago
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).
- 0x09 14y ago
  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.
  - neurotech1 14y ago
    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.)
  - mpyne 14y ago
    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#Explicit-patent-grant http://fsfe.org/campaigns/gplv3/patents-and-gplv3.en.html#Ex...

deleted 14y ago

[deleted]

gojomo 14y ago

Unless 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 ago
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.
- jlgreco 14y ago
  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.
  - waps 14y ago
    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.

batgaijin 14y ago

As 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 ago
This is insane. The US patent system is beyond retarded.

dakimov 14y ago

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.

ww520 14y ago

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.

wmf 14y ago
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.

kleiba 14y ago

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 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 ago

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&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 ago

In case of patent lawyers, break glass and extract HAT-trie or crit-bit tree.

millrawr 14y ago

I 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.