6 ms·
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 p
by dpark 15y ago
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 actual content of the patent.
- phoyd 15y agoThis modification looks like "Skip List" and according to Wikipedia http://en.wikipedia.org/wiki/Skip_list http://en.wikipedia.org/wiki/Skip_list is was first described in 1990.
- dpark 15y agoThis 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.
- colomon 15y agoOne 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.
- dpark 15y agoA 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.
- nitrogen 15y agoThis 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 ;).
- dpark 15y agoWhile 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.
- akdubya 15y agoThe 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.
- ianterrell 15y agoOh, 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...
- dpark 15y agoI 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" patent, and anyone with any software development experience who bothers to read past the title should know that.
- mtogo 15y agoIt is though, did you read any of the above comments?
- deleted 15y ago[deleted]
- 15y ago
- xilun0 15y agoAt 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 101. The patent is both obviously invalid and properly named "Linked List". That it is does not cover the single linked list special case does not changes this fact. The title is neutral, and you are inferring an anti-patent tendency from a neutral reporting (from which crowd btw?). I would be hugely curious to hear on which base you inferred that.
- dpark 15y agoNever (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&diff=284781514&oldid=284772880 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?
- sophacles 15y agoSorry, but Linked List is class of similar things -- Single-, Double-, Multiple-linkings are all part of the Linked List genre. Just because you associate Linked List strongest with the singly-linked list does not mean that other forms of the same thing, all of which qualify as linked list, can't be called it as well. You are just being disingenuous -- stop it, that is not cool.
- dpark 15y agoA skip list is also part of the "linked list" genre, but it would be misleading to say that William Pugh patented "linked lists" if he actually patented the skip list. (I don't believe he actually patented the skip list, just to be clear.) The term "linked list" refers to singly and doubly-linked lists, which may be circular and/or sorted. This is from Intro to Algorithms (2nd ed). It's not just my personal association here.
- sophacles 15y agoI suspect that maybe an intro book skips over some stuff in order to present a good conceptual base rather than a fully rigorous, complete set of definitions and options. Compare an intro to calculus book: it presents you with several differentiation or integration methods, yet when you come across the Lebesgue integration technique, you don't run to your intro book and claim "It's not in here, it's not actually integration!" Again: please stop with the disingenuous stuff -- it's still not cool. edit: Someone please explain the downvotes to me? Is it because im calling out a guy who repeatedly tells people to not appeal to authority is appealing to authority for that disingenuous behavior?
- dpark 15y ago> I suspect that maybe an intro book skips over some stuff in order to present a good conceptual base rather than a fully rigorous, complete set of definitions and options. I suspect that the intro book leaves it out because it's not widely associated with the term, because it's a rather specialized data structure. TaoCP also doesn't seem to mention multiply-linked lists or anything equivalent in its discussion of linked lists. > Compare an intro to calculus book: it presents you with several differentiation or integration methods, yet when you come across the Lebesgue integration technique, you don't run to your intro book and claim "It's not in here, it's not actually integration!" Compare someone claiming that Henri Lebesgue invented integration. It's misleading, not because he didn't invent a type of integration, but because he did not invent integration. To my mind, the linked list claim is worse than this, because even to advanced practitioners in the field, "linked list" has a relatively specific meaning, and is not generally used to refer to "any data structure with linked elements". One could argue that a graph is a form of linked list, but that's not a common definition. > Again: please stop with the disingenuous stuff -- it's still not cool. What's not cool is repeatedly calling someone disingenuous when they take the time to answer you thoughtfully. You're coming off as self-righteous and rude.
- joeburke 15y agoYes, 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.
- davorak 15y agoIf you are ok with bad software patents but not patent trolls what is your solution for limiting them?
- joeburke 15y agoI've seen several proposals, such as making patents non transferable, shortening their life time or not allowing cases to go to court unless you can prove your business depends on that patent.
- davorak 15y agoIt 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?
- pbhjpbhj 15y ago54, the title, at least in UK (and IIRC in Europe) has no bearing on the field or scope of the invention. I've the vaguest recollection of a case in the UK facing this issue and being judged that the title was not allowed to be used in determining the scope. If the title could be used for such purposes then you need the title to be as broad as possible to avoid reducing the scope of the patent unnecessarily. Suppose you patent "an improvement to a automobile engine" and it's later seen that the same improvement is good for boat engines, rocket engines maybe, etc.. This would be equivalent to file wrapper estoppel¹. However, the claims define the invention and the title (again at least in the UK) must only signify the field of the invention. If you improve "linked lists" in your invention then you don't make up a new field you call it that. Simply "Linked Lists" is broad, it could easily be shorthand for "Linked Lists used in non-traditional fields" or "An alternative to linked lists", etc., and so is highly unlikely to limit the patent but still meets the regulatory obligation to provide a relevant title. There I said it. Titles don't matter. Granted claims matter, in this case the claims in the B2, http://www.google.com/patents?id=Szh4AAAAEBAJ&printsec=claims&zoom=4#v=onepage&q&f=false http://www.google.com/patents?id=Szh4AAAAEBAJ&printsec=c... (which don't look modified but I didn't really check). -- ¹ Firefox spellcheck says it's "estoppal" but I think I'm right (for a change ;0)>)
- dpark 15y agoI'd argue it's still a case of deception. The fact that the patent is poorly titled doesn't change that. If the patent were titled "wheel and axle" but contained its current content, it would still be misleading to say that someone had patented the wheel and axle. And no, I don't feel like digging through a bunch of anti-patent articles looking for misleading claims. Even if this were the only example, the point would stand that using misleading claims makes it harder to trust the movement.
- 15y ago
- guelo 15y agoYou are trolling. Your comment uses a pedantic point to purposefully arouse a negative reaction in readers. Bad form.
- 18pfsmt 15y agoThe 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).