LSI Patents the Doubly-Linked List 328
An anonymous reader writes "Back in April, LSI was granted patent number 7028023. This is a patent on a stunning new technique in data structures ... the concept that a linked list can in fact have multiple orderings. Of course, this has been used since the beginning of (computer) time in the form of doubly-linked lists. Even if LSI wants to (somehow) claim that the doubly-linked list doesn't count as prior art, maintaining linked lists of graphical objects sorted by both x and y co-ordinates for collision detection has been done since "graphical objects" meant ASCII characters on a green-on-black screen, and has probably been widespread in databases for probably even longer."
Not exactly (Score:5, Informative)
A double linked list implies reverse pointers allowing forward and backward traversal of a list. The patent in question is more broad than that. It is talking about multiple links allowing different orderings at the same time for the same elements. So you could have a list of, say, files with links giving alphabetical order, and links giving size order, and thirdly links giving file types without having to resort the list. You might use this in a file-list screen.
The patent is still absurd, but the summary is (as usual) inaccurate.
Linux Kernel Supports Multiple Linked Lists (Score:4, Informative)
See Linux Kernel Linked List Explained. Note on the page where it says "You can have multiple lists!". That was baked into the kernel by good, smart engineers.
Re:Prior art (Score:3, Informative)
USPTO is a joke... (Score:5, Informative)
NOT doubly-linked list. It's a triple linked list (Score:3, Informative)
Now, I don't know if there's prior art on this, and the idea seems pretty obvious to me, but it is certainly *NOT* a simple doubly-linked-list.
Re: Examiner is a joke... (Score:4, Informative)
I agree that this examiner is awful. The face of the patent lists all the prior art that he considered. In this case the examiner only found 13 issued patents that were relevant to the claimed invention. Importantly, the examiner did not search for or locate any non-patent prior art (such as the dozens of examples posted on this thread). This is a hallmark of crappy patent examination.
Even more astounding, this application was allowed after only one rejection by the USPTO, which means LSI didn't really even have to argue about the prior art (software applications are typically rejected at least two times).
Actually, not so ridiculous. (Score:3, Informative)
The patent is NOT for a "doubly linked list". It is for multiple links to access the list in multiple orders. Note that a doubly linked list allows you to traverse the list forwards and backwards; whilc this patent claims to allow multiple different orders.
This is a non-trivial problem that comes up frequently enough that a general solution would be useful. I have not read the patent in enough to see how they handle insertions and deletions, so I have no way to know if it actually works, and is fast, etc.
Re:OK, this is just ridiculous. (Score:3, Informative)
I don't know about that. Most of the most famous inventions were generally unprotected by patents or heavily overpatented. Printing presses, screw propellers (reference [rochester.edu]), internal combustion engines, transistors (existing patents from 1930 were very similar to the ones made at Bell [pbs.org]), and plenty of others. That's not to say that a lot of people didn't obtain or try to obtain patents, just that the general industry was able to work around the patents. Additionally, very few inventors have actually made much money for their patents. Most often, individual inventors have been crushed by rich corporations who stole their ideas, filed their own patents, and tied the inventors up in court for years. In general, big discoveries are created by the big thinkers who simply publish their ideas, and it's left up to industry to create practical implementations of these ideas. Patents can push industry to develop working implementations, but only if they are overbroad. The physical world allows a near infinite number of solutions to most classes of problems, so once a working device is patented it usually gives competitors enough information to build a similar device anyway. In reality, all that patents can do is prevent exact copying of a design. In that sense, it's very similar to copyright.
As for software patents, I have no problem with them on the surface (well, except for those that are obvious, but that's a problem with the patent office, not patents in general). However, I think software patents should have a more limited lifespan. After all, 20 years is a *very* long time in the world of computing (just think how different things were in 1986). Something like 4 or 5 years makes far more sense.
The reason software patents are bad is that copyright already covers the same concepts for software that patents do for hardware and machines, namely preventing the exact duplication of an invention. There is no need for softare patents because copyright law prevents competitors from exactly copying an existing solution and selling it themselves. However, there should be nothing wrong with understanding the underlying problem that needs to be solved, examining all the existing approaches, selecting the best approach, and reimplementing a working solution. In some cases, there are what can be called optimal solutions to problems in computer science, and in this case the copyright office recognizes that re-implementations of an optimal algorithm to solve the same problem may in fact be very similar, if not exactly so. The key is that they were produced from first principles and existing research and not directly copied from an existing copyrighted work. Patents work the same way (but in practice patent owners pretend they don't and file lawsuits contrary to this fact), and for instance patents on creating chemicals or medicines are merely a patent on a specific process of creating the end product, or in essence a patent on a machine (considering the entire process as a whole) that produces the end product. Someone who can build a machine to do the same thing in a slightly different way won't infringe the patent.
Any other concept of patents (or copyrights) requires that some entity can own an idea or class of ideas, and not merely a physical representation of a particular idea. I agree with you that patent terms should be shortened (along with copyright terms) to 5 to 10 years. The rate of progress is increasing, and there's no reason to pretend otherwise by having even longer terms th
You're right (Score:3, Informative)
All I can say is... (Score:4, Informative)
There was a nominal rejection under 35 USC 101 [cornell.edu] as covering non-statutory subject matter, which applicant easily overcame by typical claim redrafting used in software patents. There was also a rejection under 35 USC 102 [cornell.edu] as being anticipated by the patent to Schwartz [uspto.gov]. The latter patent discloses a singly linked list and an separate array of pointers to individual items (kind of like an index?). Clearly, this is not the same as the doubly linked list of the application, and the applicant responded by pointing this out. The application was then allowed and issued.
What was clearly missed here was the patent to Porter [uspto.gov] which discloses a "...doubly-linked list search and management method
I'm sure there are lots of other prior art showing this plus the use of more than two lists (like Fig. 3). In any event I can't see claim 1 surviving even a cursory challenge. Anyone have $ 2,520.00 free to file a reexamination request?
Re:OK, this is just ridiculous. (Score:2, Informative)
Coca Cola Recipe
Ingredients
1 oz. Citrate Caffein
3 oz. Citric Acid
1 oz. Ext. Vanilla
1 Qt. Lime Juice
2 1/2 oz. Flavoring
30 lbs. Sugar
4 oz. F.E. Coco
Caramel sufficient
2 1/2 gal. Water
Flavoring
80 Oil Orange
40 Oil Cinnamon
120 Oil Lemon
20 Oil Coriander
40 Oil Nutmeg
40 Oil Neroli
1 Qt. Alcohol
Directions
Mix Caffeine Acid and Lime Juice
1 Qt. Boiling water add vanilla and flavoring when cool.
Let stand for 24 hours.