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

41–50 of 95 posts

Re: Someone patented linked lists

#41

Post by dpark »

Natsu wrote: post #37
dpark wrote: post #10

Earlier quoted context omitted.

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…

You are correct in that the patent covers a multiply-linked list. Specifically, one with two or more pointers, where the other pointers allow you to traverse the list in other ways. One example would be a doubly-linked list, though they would presumably limit that claim by pointing out that the other pointers allow you to traverse the list in any way, not merely backwards. That said, I don't think you'll find many pr…

I agree that this is an obvious invention. I think using the unqualified term "linked list" is misleading, though. As I pointed out elsewhere, references typically do not include the "multiply-linked list" when defining the linked list. They'll mention single, doubly, circularly, and possibly sorted linked lists. I don't see any mention of multiply-linked lists (or equivalent) in Intro to Algos or TaoCP. *

* It's possible that TaoCP covers them somewhere, but I don't see them in the early discussion of linked lists.

Re: Someone patented linked lists

#44

Post by smussman »

dpark wrote: post #28
xilun0 wrote: post #14

Earlier quoted context omitted.

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 es…

Correct me if I'm wrong, but wouldn't a doubly-linked list be covered by this patent? If I understand the claims correctly, the backwards traversal would fall under claim 1.[1] It definitely provides a second sequence to traverse said list, even if it's stretching 'following' a little bit.

[1] The relevant part of claim 1 is:

  said auxiliary pointer being adapted to direct said 
  computer program to a second following item and defining
  a second sequence to traverse said list.

Re: Someone patented linked lists

#45

Post by monochromatic »

srl wrote: post #26

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…

Looks like it was just sitting there for about 3 years, then it got rejected once, then it was amended and allowed.

Re: Someone patented linked lists

#46

Post by dpark »

mtogo wrote: post #39
dpark wrote: post #16

Earlier quoted context omitted.

Yes, I hopped in my time machine and read xilun0's comment 13 minutes before he actually posted it.

My bad, i thought your comment was in his thread for some reason.

No worries. I'll probably do the same thing to someone else tomorrow. :)

Re: Someone patented linked lists

#47

Post by msbarnett »

davorak wrote: post #21
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?

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

Titles are completely unrelated to the actually claims a patent makes. You can title your patent whatever you want, and it carries zero legal force when it comes to evaluating whether or not an invention is or is not covered by the patent in question.

If we assume the intent here isn't deception, then basing your description of what a patent covers on the patent's title at the very least betrays a deep ignorance of how patents actually function.

None of which is to say that this patent isn't bloody obvious or ought not to be struck down.

Re: Someone patented linked lists

#48

Post by ldar15 »

dpark wrote: post #28
xilun0 wrote: post #14

Earlier quoted context omitted.

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 es…

Your appeal to "authority" doesn't change the fact that many of us have written data structures involving multiple traversal paths, that these paths are all lists, and that they are all linked, and further that in conversation with peers we have referred to them as Linked Lists.

Your appeal to "authority" requires the admission that Wikipedia actually supports the counter argument, while an Introduction to anything is hardly an appropriate authority for whether or not something is novel enough to be patented.

I'm glad you are responding to every single person claiming that their experience is wrong, because that provides ample opportunity to reduce your karma.

Re: Someone patented linked lists

#49

Post by dpark »

smussman wrote: post #44
dpark wrote: post #28

Earlier quoted context omitted.

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 es…

Correct me if I'm wrong, but wouldn't a doubly-linked list be covered by this patent? If I understand the claims correctly, the backwards traversal would fall under claim 1.[1] It definitely provides a second sequence to traverse said list, even if it's stretching 'following' a little bit. [1] The relevant part of claim 1 is: said auxiliary pointer being adapted to direct said computer program to a second following i…

Sure. That alone probably wouldn't invalidate the patent, though. The claim is for a more generic capability.

Of course the patent is obvious and there's (almost certainly) prior art for the multiply-linked list anyway.

Re: Someone patented linked lists

#50

Post by dpark »

ldar15 wrote: post #48
dpark wrote: post #28

Earlier quoted context omitted.

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 es…

Your appeal to "authority" doesn't change the fact that many of us have written data structures involving multiple traversal paths, that these paths are all lists, and that they are all linked, and further that in conversation with peers we have referred to them as Linked Lists. Your appeal to "authority" requires the admission that Wikipedia actually supports the counter argument, while an Introduction to anything i…

> Your appeal to "authority" doesn't change the fact that many of us have written data structures involving multiple traversal paths, that these paths are all lists, and that they are all linked, and further that in conversation with peers we have referred to them as Linked Lists.

Your argument doesn't change the fact that it's misleading to refer to any arbitrary linked data structure as a "linked list". You can call a skip list a linked list if you want, but that does't make it appropriate, and it doesn't redefine the language for the more general audience. Go ask your coworkers to draw a linked list on the board and see how many draw a multiply-linked list, or a skip list, or any number of other things that could be pedantically considered "linked lists".

Even if we were to accept the argument that "linked list" is just a generic term for data structures involving linked traversal paths, that would not make the HN title appropriate. If the term "linked list" were that generic, then it would be misleading to apply it to this patent, which clearly does not cover everything that would fall unto the generic "linked list" term.

> Your appeal to "authority" requires the admission that Wikipedia actually supports the counter argument,

Are you seriously trying to criticize my "appeal to authority" by making one of your own?

Nevermind the fact that Wikipedia didn't include the term "multiply-linked" until three years after this patent was granted...

> while an Introduction to anything is hardly an appropriate authority for whether or not something is novel enough to be patented.

Are you really that oblivious? I've said a dozen times that this is not a valid patent. That's not the point.

And an intro book is quite appropriate for establishing what a term covers to the general audience. If something is specialized enough that it's not covered in an intro book, then it's specialized enough that it should not be referred to by the generic term.

> I'm glad you are responding to every single person claiming that their experience is wrong, because that provides ample opportunity to reduce your karma.

Do you really think I care if you or someone else is childish enough to downvote all my comments?

Post reply on HN