4 ms·

This has been discussed before, it is not just a linked list. It is a list which has elements that not only point to the next element, but the element after it

by sturmeh 14y ago

This has been discussed before, it is not just a linked list. It is a list which has elements that not only point to the next element, but the element after it, and so on. (As to provide a recovery method if one element is to be destroyed, or to ease implementation for removal etc. However that's still fringing on patent trolls.

vonmoltke 14y ago
And, as presented in this patent, its a trivial enhancement on a conventional linked list. This is a patent for a data structure. There is no implementation there. Hell, there is no algorithm there. Its just someone who said, "Hey, I can put two forward pointers in each element of a linked list!" and wrapped a bunch of legalistic crap around it. This patent doesn't need prior art to be invalid.
- dpark 14y ago
  > its a trivial enhancement on a conventional linked list. Indeed it is. The patent should not have been granted, and from previous discussions about this, there is ample evidence of prior art. However, exaggerating this patent by claiming it is a "linked list" patent diminishes the conversation around patents. It doesn't make patents sound worse. It makes those who are anti-patent seem disingenuous. This patent is bad enough on its own merits without implying that someone was granted a patent for the linked list concept as a whole. If Subaru were issued a patent for a new method of fuel injection, would it be appropriate to claim that they were issued a patent for the internal combustion engine? > This is a patent for a data structure. There is no implementation there. What is a data structure if not an implementation?
  - Evbn 14y ago
    In the patent-law sense, an implementation is a manifestation in hardware that performs some function.
    - dpark 14y ago
      Sure, but "system and method" is a sham to get past the "can't patent math rule". Software patents by necessity describe an abstract implementation. Rarely do software patents describe the hardware in any meaningful fashion.
  - jedbrown 14y ago
    > What is a data structure if not an implementation? The patent is a cartoon of a half-baked idea. It does not even describe how to implement element addition or removal. (Unless the caller maintains some special structure, many O(1) list operations become O(N). Removal is delicate because you need all incoming pointers.). It's unclear whether the "inventor" ever implemented the data structure.
    - dpark 14y ago
      First, it should be obvious that I was not defending this patent. Attacking the patent as "a cartoon of a half-baked idea" is pointless, and doesn't answer my question at all. Second, the patent describes an implementation that allows multiple traversals. That it doesn't cover addition or removal seems irrelevant. The patent is for the structure that allows the traversals. You could build up the structure in a number of ways, but the end result would be the same.
      - jedbrown 14y ago
        "The implementation of a data structure usually requires writing a set of procedures that create and manipulate instances of that structure." (http://en.wikipedia.org/wiki/Data_structure http://en.wikipedia.org/wiki/Data_structure) If you gloss over construction and modification details, this "invention" is entirely covered by "Fortran-style" linked lists which have been in common use since the 1950s. (Store the primary list in an array, then have one or more integer arrays containing the index of the next node. Relative to storing the "aux_next" pointer inside the node, this allows dynamically creating and destroying an arbitrary number of indices.)
        dpark 14y ago
        I don't think the patent office or judicial system generally refers to Wikipedia for what constitutes an implementation. This invention is obvious and trivial and there seems to be lots of prior art. I'm not sure why you still seem to think I'm defending it. Regardless, describing how these lists should be constructed would not make this any less trivial or obvious.
  - vonmoltke 14y ago
    > However, exaggerating this patent by claiming it is a "linked list" patent diminishes the conversation around patents. The title of the patent is "Linked List". How is that an exaggeration? > If Subaru were issued a patent for a new method of fuel injection, would it be appropriate to claim that they were issued a patent for the internal combustion engine? I think you misunderstand my point. I did not claim that this person patented linked lists. I claimed this person patented a trivial enhancement to a conventional linked list, and did not provide any implementation detail (which is really what makes it trivial). On the subject of implementation, I do not see a data structure description as an implementation, any more than I see an algorithm as an implementation. Being an electrical engineer I am biased towards thinking of implementation as an actual, functional system (not necessarily hardware). I know there are many patents where this definition of implementation doesn't hold, but that is why I am uncomfortable with software and business method patents in general, and think chemical and drug patents should be a special category.
    - dpark 14y ago
      > The title of the patent is "Linked List". How is that an exaggeration? So it's a poorly titled patent. All that tells me is that the inventor was too unoriginal to even come up with a better name. If he'd titled it "the wheel", would it be accurate to claim that a patent was granted on the wheel? >I think you misunderstand my point. I did not claim that this person patented linked lists. I claimed this person patented a trivial enhancement to a conventional linked list, and did not provide any implementation detail (which is really what makes it trivial). I actually think you misunderstand my point. I agree that this is trivial and obvious. However, that doesn't justify exaggerating the actual claims ("linked list patented!"). People who are already dead-set against software patents might enjoy this, but they're just being self-congratulatory, and there's no real point. People who are in favor of software patents or on the fence will instead recognize the exaggeration and dismiss the argument as disengenuous. Worse, they may take this as evidence that the anti-software-patent movement has no real basis, because the movement demonstrates that it has to exaggerate in order to even make its point.
      - rayiner 14y ago
- geofft 14y ago
  Honestly, patents on data structures seem more in line with patent law than patents on algorithms. They're supposed to cover physical devices, like a vegetable peeler or something. Patenting an algorithm usually works by saying "a computer that implement this algorithm"; patenting a virtual object seems a lot cloaer to the spirit of patents than patenting a procedure by embedding it in a general-purpose physical object.
DennisP 14y ago
Sounds like a skip list, first described in 1990: http://en.wikipedia.org/wiki/Skip_list http://en.wikipedia.org/wiki/Skip_list

by sturmeh 14y ago

vonmoltke 14y ago

And, as presented in this patent, its a trivial enhancement on a conventional linked list. This is a patent for a data structure. There is no implementation there. Hell, there is no algorithm there. Its just someone who said, "Hey, I can put two forward pointers in each element of a linked list!" and wrapped a bunch of legalistic crap around it. This patent doesn't need prior art to be invalid.

dpark 14y ago
> its a trivial enhancement on a conventional linked list. Indeed it is. The patent should not have been granted, and from previous discussions about this, there is ample evidence of prior art. However, exaggerating this patent by claiming it is a "linked list" patent diminishes the conversation around patents. It doesn't make patents sound worse. It makes those who are anti-patent seem disingenuous. This patent is bad enough on its own merits without implying that someone was granted a patent for the linked list concept as a whole. If Subaru were issued a patent for a new method of fuel injection, would it be appropriate to claim that they were issued a patent for the internal combustion engine? > This is a patent for a data structure. There is no implementation there. What is a data structure if not an implementation?
- Evbn 14y ago
  In the patent-law sense, an implementation is a manifestation in hardware that performs some function.
  - dpark 14y ago
    Sure, but "system and method" is a sham to get past the "can't patent math rule". Software patents by necessity describe an abstract implementation. Rarely do software patents describe the hardware in any meaningful fashion.
- jedbrown 14y ago
  > What is a data structure if not an implementation? The patent is a cartoon of a half-baked idea. It does not even describe how to implement element addition or removal. (Unless the caller maintains some special structure, many O(1) list operations become O(N). Removal is delicate because you need all incoming pointers.). It's unclear whether the "inventor" ever implemented the data structure.
  - dpark 14y ago
    First, it should be obvious that I was not defending this patent. Attacking the patent as "a cartoon of a half-baked idea" is pointless, and doesn't answer my question at all. Second, the patent describes an implementation that allows multiple traversals. That it doesn't cover addition or removal seems irrelevant. The patent is for the structure that allows the traversals. You could build up the structure in a number of ways, but the end result would be the same.
    - jedbrown 14y ago
      "The implementation of a data structure usually requires writing a set of procedures that create and manipulate instances of that structure." (http://en.wikipedia.org/wiki/Data_structure http://en.wikipedia.org/wiki/Data_structure) If you gloss over construction and modification details, this "invention" is entirely covered by "Fortran-style" linked lists which have been in common use since the 1950s. (Store the primary list in an array, then have one or more integer arrays containing the index of the next node. Relative to storing the "aux_next" pointer inside the node, this allows dynamically creating and destroying an arbitrary number of indices.)
      - dpark 14y ago
        I don't think the patent office or judicial system generally refers to Wikipedia for what constitutes an implementation. This invention is obvious and trivial and there seems to be lots of prior art. I'm not sure why you still seem to think I'm defending it. Regardless, describing how these lists should be constructed would not make this any less trivial or obvious.
- vonmoltke 14y ago
  > However, exaggerating this patent by claiming it is a "linked list" patent diminishes the conversation around patents. The title of the patent is "Linked List". How is that an exaggeration? > If Subaru were issued a patent for a new method of fuel injection, would it be appropriate to claim that they were issued a patent for the internal combustion engine? I think you misunderstand my point. I did not claim that this person patented linked lists. I claimed this person patented a trivial enhancement to a conventional linked list, and did not provide any implementation detail (which is really what makes it trivial). On the subject of implementation, I do not see a data structure description as an implementation, any more than I see an algorithm as an implementation. Being an electrical engineer I am biased towards thinking of implementation as an actual, functional system (not necessarily hardware). I know there are many patents where this definition of implementation doesn't hold, but that is why I am uncomfortable with software and business method patents in general, and think chemical and drug patents should be a special category.
  - dpark 14y ago
    > The title of the patent is "Linked List". How is that an exaggeration? So it's a poorly titled patent. All that tells me is that the inventor was too unoriginal to even come up with a better name. If he'd titled it "the wheel", would it be accurate to claim that a patent was granted on the wheel? >I think you misunderstand my point. I did not claim that this person patented linked lists. I claimed this person patented a trivial enhancement to a conventional linked list, and did not provide any implementation detail (which is really what makes it trivial). I actually think you misunderstand my point. I agree that this is trivial and obvious. However, that doesn't justify exaggerating the actual claims ("linked list patented!"). People who are already dead-set against software patents might enjoy this, but they're just being self-congratulatory, and there's no real point. People who are in favor of software patents or on the fence will instead recognize the exaggeration and dismiss the argument as disengenuous. Worse, they may take this as evidence that the anti-software-patent movement has no real basis, because the movement demonstrates that it has to exaggerate in order to even make its point.
    - rayiner 14y ago
geofft 14y ago
Honestly, patents on data structures seem more in line with patent law than patents on algorithms. They're supposed to cover physical devices, like a vegetable peeler or something. Patenting an algorithm usually works by saying "a computer that implement this algorithm"; patenting a virtual object seems a lot cloaer to the spirit of patents than patenting a procedure by embedding it in a general-purpose physical object.

DennisP 14y ago

Sounds like a skip list, first described in 1990: http://en.wikipedia.org/wiki/Skip_list http://en.wikipedia.org/wiki/Skip_list