Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Someone patented linked lists

google.com

Post reply on HN
Print view View original

21–30 of 95 posts

Re: Someone patented linked lists

#21

Post by davorak »

dpark wrote: post #4

This is not a patent on the linked list. It's a patent on a modification of the linked list that provides a secondary (and possibly tertiary, etc.) traversal path. The patent should not have been granted, and should be deemed invalid if it ever goes to court, but it is not a patent on just the linked list. The anti-patent crowd makes themselves look bad by trotting out examples like this and being deceptive about the…

It is the title of the patent located on the upper left in google patent. If you search for linked list patent it comes up on patent storm. This does not seem to be a case of deception.

Can you provide other examples of the "anti-patent crowd" being deceptive with their examples?

Re: Someone patented linked lists

#22

Post by davorak »

joeburke wrote: post #19
dpark wrote: post #4

This is not a patent on the linked list. It's a patent on a modification of the linked list that provides a secondary (and possibly tertiary, etc.) traversal path. The patent should not have been granted, and should be deemed invalid if it ever goes to court, but it is not a patent on just the linked list. The anti-patent crowd makes themselves look bad by trotting out examples like this and being deceptive about the…

Yes, especially when there is no actual court case. Let's talk again once the owner of the patent successfully sues over it, making millions in the process. Never going to happen. Software patents are not the problem, patent trolls are.

If you are ok with bad software patents but not patent trolls what is your solution for limiting them?

Re: Someone patented linked lists

#25

Post by colomon »

dpark wrote: post #9
phoyd wrote: post #8

Earlier quoted context omitted.

This modification looks like "Skip List" and according to Wikipedia http://en.wikipedia.org/wiki/Skip_list is was first described in 1990.

This is not a skip list, not at all. The skip list is a probabilistic data structure that gives expected access times comparable to a BBST. The patent covers a linked list with an extra set of links that provide a different traversal.

One example of which would be a doubly linked list, which (according to Wikipedia) goes back at least to IBM's TSS/360 operating system (1967), and was discussed in The Art of Computer Programming volume 1, published in 1968.

Re: Someone patented linked lists

#26

Post by srl »

This patent appears to have gone almost 4 years between being filed and being issued. One wonders what they spent that time doing. Looking through their car's user manual for prior art, perhaps? (Or perhaps they took that phrase literally, and conducted a search of the Louvre...)

Even if USPTO was actually doing a good job of vetting patents, that would still have been four years during which anybody seeking to use a multiply linked list would have to do so under the shadow of a possible lawsuit (which would be expensive, even if trivially winnable) if and when the patent was accepted.

Re: Someone patented linked lists

#27

Post by brlewis »

mark242 wrote: post #12

It's unenforceable. Check page 19 of "Programming the Logic Theory Machine", by Newell and Shaw, published in 1957, for prior art.

Legally, it's presumed valid. It may be easy to prove that the invention is not novel, but doing so would still involve time, effort, and money. The patent holder needs only to settle for a smaller amount of money than would be required to invalidate the patent.

Re: Someone patented linked lists

#28

Post by dpark »

xilun0 wrote: post #14
dpark wrote: post #4

This is not a patent on the linked list. It's a patent on a modification of the linked list that provides a secondary (and possibly tertiary, etc.) traversal path. The patent should not have been granted, and should be deemed invalid if it ever goes to court, but it is not a patent on just the linked list. The anti-patent crowd makes themselves look bad by trotting out examples like this and being deceptive about the…

At first I thought that too. But within 1 or 2s, I remembered that linked lists have never been limited to single linked lists (except maybe in poor quality courses), multiple linked lists have been around since Unix and very very probably before, have nothing inherently special, so it's absolutely all right to both simply call them "linked list" (like the patent properly does in its title) and to consider them as CS…

Never (before you) have I heard someone talk about multiply-linked lists as simply being "linked lists". That term is generally reserved for the "standard" linked list types. Skip lists are also a variant of linked lists, but very few would generally refer to them simply as "linked lists".

Singly-linked and doubly-linked lists are taught as standard linked lists. Multiply-linked lists are not, because they are not especially useful in most cases. With a doubly-linked list (perhaps more clearly called a bidirectional linked list), all the standard algorithms work with minor or no modifications. With multiply-linked lists, even just inserting an element becomes much more complex. You're now traversing m lists for insertion instead of 1. I would question the quality of your CS101 course if your professor taught you about multiply-linked lists. It's a rather specialized data structure that is generally not beneficial. That time would have been better spent covering a more useful data structure.

I don't have an intro data structures textbook anymore, but I just checked "Introduction to Algorithms, 2nd Ed." and they do not seem to mention multiply-linked lists. "A list may have one of several forms. It may be either singly or doubly linked, it may be sorted or not, and it may be circular or not." For further evidence that multiply-linked lists are not widely considered simply "linked lists", I'll note that Wikipedia didn't mention multiply-linked lists as a variant until 2009. http://en.wikipedia.org/w/index.php?title=Linked_list&di...

As I've already said, I agree that the patent is invalid. It's not novel. But I do not agree that it's simply a "linked list". That term is far more generic and its usage without further clarification implies a much broader claim than the patent makes. Out of curiosity, where in the original Unix were these multiply-linked lists used?

As for why I infer anti-patent tendency, why post this at all except as an example of how the patent system is broken? And why assign it the very broad title "Someone patented linked lists" instead of, say, the more accurate (or at least more specific) "Someone patented a variation of linked lists"? Maybe because the former is more inflammatory?

Re: Someone patented linked lists

#29

Post by [deleted] »

dpark wrote: post #10
ianterrell wrote: post #7

Earlier quoted context omitted.

Oh, so someone patented a multiply linked list. That's better? It's not like there's not oodles of prior art or it's nonobvious...

I feel like reading comprehension on HN is dropping lately, or at least that some people are willfully choosing to not read entire comments before replying. I specifically said that the patent should not have been granted . The point is that by being misleading, the anti-patent crowd diminishes their moral standing, and makes it harder for people to take their arguments seriously. This is not simply a "linked list" p…

[deleted]

Re: Someone patented linked lists

#30

Post by dpark »

colomon wrote: post #25
dpark wrote: post #9

Earlier quoted context omitted.

This is not a skip list, not at all. The skip list is a probabilistic data structure that gives expected access times comparable to a BBST. The patent covers a linked list with an extra set of links that provide a different traversal.

One example of which would be a doubly linked list, which (according to Wikipedia) goes back at least to IBM's TSS/360 operating system (1967), and was discussed in The Art of Computer Programming volume 1, published in 1968.

A doubly-linked list generally refers to a bidirectional linked list, where the pointers are next and prev. This type of list allows traversal in both directions, but it's still essentially a single traversal. Multiply-linked lists provide next1, next2, etc. pointers for multiple unrelated traversals, each in a single direction (unless we assume a "multiply-doubly-linked list").

Arguably we could consider a doubly-linked list to be a special case of the multiply-linked list, but it would be a poor choice, as certain key operations (such as insertion) are more expensive with a multiply-linked list.

Post reply on HN