Judy arrays are patented

[gojomo]

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]

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.

[kleiba]

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

[wheaties]

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]

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.

[hcarvalhoalves]

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.

[aspensmonster]

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

[rossjudson]

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]

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

[hexagonc]

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.

[batgaijin]

As well as the doubly-linked list http://www.google.com/patents?id=Szh4AAAAEBAJ&printsec=a...

[dakimov]

This is insane. The US patent system is beyond retarded.

[millrawr]

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.

[zrail]

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.

[beagle3]

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

[lsb]

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

[ww520]

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]

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.

[cbsmith]

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

[codeulike]

using System.Collections.Patented;

[dakimov]

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.