Judy arrays are patented

#1

Post by CesareBorgia » Fri, Jan 11, 2013, 5:17 PM UTC

Judy arrays are patented
en.wikipedia.org

Re: Judy arrays are patented

#2

Post by wheaties » Fri, Jan 11, 2013, 6:29 PM UTC

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.

Re: Judy arrays are patented

#3

Post by codeulike » Fri, Jan 11, 2013, 6:40 PM UTC

using System.Collections.Patented;

Re: Judy arrays are patented

#4

Post by zrail » Fri, Jan 11, 2013, 6:45 PM UTC

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.

Re: Judy arrays are patented

#5

Post by rossjudson » Fri, Jan 11, 2013, 6:57 PM UTC

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.

Re: Judy arrays are patented

#6

Post by munchbunny » Fri, Jan 11, 2013, 7:01 PM UTC

wheaties wrote: post #2

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.

Re: Judy arrays are patented

#7

Post by taeric » Fri, Jan 11, 2013, 7:02 PM UTC

munchbunny wrote: post #6

wheaties wrote: post #2

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.

So... I can patent complicated math? This is essentially what you are saying, right?

Re: Judy arrays are patented

#8

Post by mpyne » Fri, Jan 11, 2013, 7:02 PM UTC

rossjudson wrote: post #5

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

Re: Judy arrays are patented

#9

Post by lsb » Fri, Jan 11, 2013, 7:06 PM UTC

zrail wrote: post #4

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.

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

Re: Judy arrays are patented

#10

Post by beagle3 » Fri, Jan 11, 2013, 7:07 PM UTC

zrail wrote: post #4

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