Live data from Hacker News

Someone patented linked lists

google.com

81–90 of 95 posts

Re: Someone patented linked lists

#81
post #61

The Solaris kernel (for example) has lots of data structures that have multiple linked lists. For example, the cpu structure has at least 6 linked list pointers. For a reference published in 2001 (before the patent was filed): http://books.google.com/books?id=r_cecYD4AKkC&lpg=PA413&... Also note that a doubly linked list is described by claim one.

The cpu structure is on several different lists. That's not exactly the same as being on one list with multiple links.

The cpu structure is on several different lists. That's not exactly the same as being on one list with multiple links.

Sure it is: one list with multiple links is the exact same thing as multiple different lists that coincidentally contain the same items.

Re: Someone patented linked lists

#82
post #78

Earlier quoted context omitted.

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…

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

The 2.6 line of the Linux kernel provides an anecdotal counterargument to this. The kernel team managed to gradually rewrite significant portions of the kernel without ever having to enter a development-only phase. If we could find some way of applying the tools that make this possible (diff, git/DVCSes, peer review, integration tests[0], etc.) to the legal system, maybe the world would be a better place.

The closest thing I'm aware the legal world has now, and it's a far, far cry from what we have in software, is having as much as possible be specific to separate, local governments, so if an individual state comes up with a good solution to a problem, it can be applied elsewhere.

[0] Imagine if all prior court cases were automatically tested against any changes to the law, with changes in outcomes flagged for public review.

Re: Someone patented linked lists

#83
post #28
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…

I agree there is a risk of misinterpretation as in "all kind all linked lists have been patented, here is the patent" and for this reason, it maybe would have been better to get an even more precise title. By i'm technically still fine with the current one. The claims (both in the application and in the granted patent) barely talk about traversing the "primary" or the "auxiliary" list which provide another sequence (well, providing the same would be... useless), not any kind of tricky algorithm like efficient multiple simultaneous sorting or i don't know what, not even a plain and boring insertion is covered!

This is a special case of traversing multiple linked lists, which is a basic technique. I actually even hesitate to say it is a technique, or at least to distinguish this technique from the very same technique of using a single linked list, because I don't think I could ever come up with a plausible justification for why anybody previously knowing how to use one would not be able to use two. The restriction making this a special case is that all lists contain the same set of elements. Given the claims, that restriction is unnecessarily narrow and have no technical effect. So the only thing that distinguish this patent from a patent on a particular (but still 100% basic) use of single linked lists, is the phrasing, and the empty (still given the context) emphasis on the fact there are not one, but two, or even three lists.

So despite the fact that basic singly-linked lists + limited to one list by element would not be covered by this patent even in the parallel universe where it would be considered valid (and while we can note that on the contrary, prev/next linked list would), given that it only claims (with many more sentences) that if you have two lists, you can traverse one, or you can traverse the other, i will continue to argue that it covers linked lists, maybe under certain conditions, all right, but those conditions are insufficient to mandate the precision that this is a modification of linked lists, because it is not a modification, it is just about the basic traversal of multiple plain classical linked lists.

(Also, one a side note, I found it cute how the claims are structured, like if the author thought there was a possibility that prior art could be found for two pointers but not three.)

Edit: About the inflammatory part, it might as well have been even more inflammatory by being even more descriptive. Somebody has patented traversal of linked lists.

Re: Someone patented linked lists

#84
post #30

Earlier quoted context omitted.

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…

While I ended up arguing a lot of tangents, my original point was that the title diminishes the standing of the anti-patent crowd. Whether "linked list" is taken as a generic term that describes a whole class of data structures or whether it's restricted to just the basic "linked list" types, the title is misleading. The patent does not cover the basic linked list types nor does cover the entire the entire class.

This patent is ridiculous enough without exaggeration. I believe that the patent system is broken, but making misleading claims about frivolous patents weakens the arguments. The truth is already ridiculous enough.

As for your comment about "excessive infighting over apparently trivial concerns", I wish I could dispute that. I feel that geeks as a group tend to be pedantic jackasses, and I'm often guilty of that myself. It does hurt our credibility as a whole.

By the way, your interpretation of multiply-linked lists is correct. You can look at it as multiple separate lists crammed together for minor space savings or as a directed graph with labeled edges (labels here represents which "list" an edge is for). This is why I don't think it's an especially useful data structure; there are better alternatives for most cases.

Re: Someone patented linked lists

#85
post #35

Earlier quoted context omitted.

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

Aside from it being obvious, I'm pretty sure there's prior art for specifically what this patent describes. One of the times this was posted to Reddit someone posted a link to a book that describes pretty much exactly what's in this patent, with a diagram no less. http://my.reddit.com/r/programming/comments/1bbb3/congratula...

Re: Someone patented linked lists

#86
post #83
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…

I agree there is a risk of misinterpretation as in "all kind all linked lists have been patented, here is the patent" and for this reason, it maybe would have been better to get an even more precise title. By i'm technically still fine with the current one. The claims (both in the application and in the granted patent) barely talk about traversing the "primary" or the "auxiliary" list which provide another sequence (…

Someone else explained my problem with the title better than I managed. http://news.ycombinator.com/item?id=2875082

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.

As for claims of the patent, it does really cover traversing at all. It mentions it, but the meat of the patent is the data structure having two or three pointers built in for traversing and choosing between those pointers for different traversals. This is all very obvious and frivolous, but it's not claiming the basics of traversing a linked list.

(As for your side note, I found that really strange as well. I can't imagine why thy specifically called out the cases of 2 and 3 pointers. Were they planning on filing later for 4 and 5 when they figured it out?)

Re: Someone patented linked lists

#87
post #9
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.

The patent by itself does not describe a skip list, but the most common skip list implementations use a multilevel list data structure similar to what's described in the patent.

Re: Someone patented linked lists

#88
post #78

Earlier quoted context omitted.

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…

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). The 2.6 line of the Linux kernel provides an anecdotal counterargument to this. The kernel team managed to gradually rewrite significant portions of the kernel without ever having to enter a developm…

Actually I would the kernel a confirmation: The fixed the broken parts gradually without ever throwing everything away and starting over.

[0] would be cool, but probably not possible. You get a court case when the law is ambiguous, or the facts are not known. Neither of which can be automatically tested.

Re: Someone patented linked lists

#89
post #52
post #51

Earlier quoted context omitted.

> being misleading Someone says "linked list" when he means "double linked list". How devious! > the anti-patent crowd World conspiracy!

> Someone says "linked list" when he means "double linked list". How devious! Someone patented compression. http://www.google.com/patents?vid=4558302 Someone patented search engines. http://www.google.com/patents?vid=6285999 Someone patented public-key cryptography. http://www.google.com/patents?vid=4405829 Obviously none of those statements are misleading in any way. > World conspiracy! Just because someone doesn't…

your analogies are flawed. stop trolling.

Re: Someone patented linked lists

#90
post #27

Earlier quoted context omitted.

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.

Lady justice's scales are balanced by cash.

That's why the legal system is wrong.

Post reply on HN