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

71–80 of 95 posts

Re: Someone patented linked lists

#71

Post by dpark »

sophacles wrote: post #69
function_seven wrote: post #67

Earlier quoted context omitted.

Imagine the headline read, "Gas up to $8.23 a gallon" and only upon reading the article did you discover that the "gas" they're talking about is 110 octane race gas. Yes, race gas is a type of gas(oline), but the headline is still quite misleading, as the common definition, without qualifiers, is the pump variety.

In this case, I don't think your analogy holds, because I don't see it as any different than a doubly linked list -- one of the common types. It is just a generalization case of doubly linked list honestly. I see it as about as misleading as finding out the headline gas price was about the premium grade standard pump gasoline rather than the low grade standard pump gasoline, which is maybe a bit tricky, but not rant-…

function_seven's analogy is extremely apt.

What you're experiencing right now is called cognitive dissonance or cognitive disequilibrium. You've found that the argument you've been making is at odds with the facts. Claiming that you see no difference between a multiply-linked list and a doubly-linked list is an attempt to shrug off a legitimate point with a nonsensical argument. (Or alternatively you are not skilled enough at programming to understand the topic at hand).

Re: Someone patented linked lists

#72

Post by 18pfsmt »

guelo wrote: post #38
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…

You are trolling. Your comment uses a pedantic point to purposefully arouse a negative reaction in readers. Bad form.

The ensuing discussion was very helpful for someone like me that is learning. The underlying topics have been intimidating, but have been made much less so by this discussion (YMMV). These discussions often have so much jargon in them, that it becomes frustrating.

In other words, this "trolling" was helpful for me (which is a first).

Re: Someone patented linked lists

#73

Post by ars »

CamperBob wrote: post #53
alecbenzer wrote: post #13

Earlier quoted context omitted.

What exactly does a patent office do to determine if something is actually original or not? Like did some clerk look at this and say "Yeah, I'm no computer scientist, but this sounds original to me"?

More or less nothing. They rely on the applicant to disclose any prior art. Disagreements about patentability are a matter for the courts, in the USPTO's view. The only solution is to defund them and shut them down.

A: That is not true. Which I know first hand, since I worked with someone who was in a very long dispute with the patent office on the patentability of something.

B: That is the only solution? You can not think of any other possible solution?

Re: Someone patented linked lists

#74

Post by CamperBob »

ars wrote: post #73
CamperBob wrote: post #53

Earlier quoted context omitted.

More or less nothing. They rely on the applicant to disclose any prior art. Disagreements about patentability are a matter for the courts, in the USPTO's view. The only solution is to defund them and shut them down.

A: That is not true. Which I know first hand, since I worked with someone who was in a very long dispute with the patent office on the patentability of something. B: That is the only solution? You can not think of any other possible solution?

So how does something like this patent on multiply-linked lists happen, if the USPTO does even the most cursory prior art search on its own? The rules say one thing, the reality says another.

That is the only solution? You can not think of any other possible solution?

Law is the code we live by. You don't fix code this broken. You rewrite it.

Re: Someone patented linked lists

#75

Post by [deleted] »

dpark wrote: post #50
ldar15 wrote: post #48

Earlier quoted context omitted.

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

[deleted]

Re: Someone patented linked lists

#76

Post by grabastic »

brlewis wrote: post #27
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.

Exactly. Many smaller businesses can't afford a lengthy legal battle even if they are likely to win.

Re: Someone patented linked lists

#77

Post by nitrogen »

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…

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.

Meta: Since your account is relatively new: I was ready to upvote your comment to try to bring it out of the gray text region (i.e. Hope this helps.

Re: Someone patented linked lists

#78

Post by ars »

CamperBob wrote: post #74
ars wrote: post #73

Earlier quoted context omitted.

A: That is not true. Which I know first hand, since I worked with someone who was in a very long dispute with the patent office on the patentability of something. B: That is the only solution? You can not think of any other possible solution?

So how does something like this patent on multiply-linked lists happen, if the USPTO does even the most cursory prior art search on its own? The rules say one thing, the reality says another. That is the only solution? You can not think of any other possible solution? Law is the code we live by. You don't fix code this broken. You rewrite it.

As Daniel_Newby said: "the patent office checks if the patent is substantially similar to previous patents".

They do a check, and a thorough one, just not in the same places you do. Remember that they are not programmers.

> Law is the code we live by. You don't fix code this broken. You rewrite it.

Oh please. A simple solution would be requiring them to hire an expert in each field to double check patents. This would cost too much which is why they don't. But it's a simple solution.

PS. In the real world no one rewrites broken code once it gets used a lot. You fix the broken parts. The only time you rewrite code is before many people use it, or in the new product (which is basically the same thing).

Re: Someone patented linked lists

#79

Post by nitrogen »

dpark wrote: post #30
colomon wrote: post #25

Earlier quoted context omitted.

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…

This multiply-linked list just seems to be a special case of an item being in multiple separate lists. In this case, the separate lists also happen to contain all the same items as the first list. Further, these are all special cases of the directed graph.

Regarding the overall conversation, it looks like everyone is arguing over whether "linked list" should be interpreted inclusively to contain all list-like linked data structures, or exclusively to refer strictly to those data structures referred to by the "linked list" moniker in traditional CS textbooks. There is also the issue of whether "linked list" has an informal, conversational meaning among a subset of programmers that differs from its formal definition (I believe this thread demonstrates that it does), and whether it should have such separate meanings.

It is my opinion that neither of these arguments is helpful to the anti-bad-patent/anti-software-patent cause, and it seems that excessive infighting over apparently trivial concerns is a credibility-destryoing hallmark of the stereotypical geek. After all, if you were a politician, would you continue to listen to a presentation in which the presenters started arguing with each other over whether the background color of the slides was more appropriately described as purple or fuchsia (Is fuchsia a subset of purple, or are they separate entirely? Sounds familiar...)?

As an aside, sometimes I wish I could draw a circle around an entire thread and say, "I'm responding to this whole blob," with the page layout updated accordingly ;).

Re: Someone patented linked lists

#80

Post by nitrogen »

dpark wrote: post #35
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.

Sorry, this patent is invalid, but your prior art covers a different invention. Page 19 shows a singly-linked list. Page 20 shows nested lists (a list where some elements are also lists). I don't see anything in this document that covers the same type of multiply-linked lists that the patent claims.

As I vaguely alluded to in another response to one of your comments, the argument could go like this:

1. The linked list was described in 1957 or earlier.

2. The cited mention of the linked list also considers more complex permutations of lists.

3. This patent effectively describes adding a single set of items to multiple lists (I haven't read the patent, so I may be glossing over details).

4. #2 demonstrates that such a permutation of the concept of a list would be obvious to anyone skilled in the art.

5. Therefore, the patent is invalid.

Post reply on HN