Slashdot Mirror
LSI Patents the Doubly-Linked List
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."
While one could at least make a somewhat intelligent argument why software that costed companies like Apple or Microsoft Millions (or even Billions) of dollars to create should be patented, there's no logical argument for patenting data structures. This patent was first submitted in 2002, which probably means it was turned down and appealed at least twice. As anyone who has gone through the patent process knows, if you appeal enough times eventually you might find an examiner who is clueless enough to grant the patent.
I couldn't imagine LSI ever intends to protect the patent (since it obviously would never stand up in court). Most likely, they are just seeking bragging rights "Hey look, we had 30 patents approved this year".
Our government needs to more clearly delineate what software can and cannot be patented in order to prevent more ridiculous patents. I'm more in the 'No Software Patents' camp, but I think there are exceptions, particularly for very specialized software in specific industries.
Huh? Don't mind me, I'm just the new guy.
1. Take a fundamental concept
2. Describe it as complicated as possible
3. Put the result through a patent-lawyers office in order to make sure the claims get even more obfuscated
4. Apply successfully for a patent
5. Profit!
CC.
TaijiQuan (Huang, 5 loosenings)
The author seems to think that rational thought, logic and common sense plays some part in the patent granting process in the USA.
AT&ROFLMAO
Patents do not have to be meaningful, or even have a remote chance of standing up in court. They are weapons in corporate world and you use them mostly to cause damage. If your public company is sued you lose money in legal fees, might lose investor confidence in a critical moment and overall end up in a loss even if you easily won it. Just look at Research In Motion if you need to see how much damage can frivolous patent deal.
What are the patent trolls doing now -- reading computer science textbooks and language tutorial books and trying to figure out clever redefinitions of these techniques because they can't be bothered to create product (e.g., new wealth) to offer in the marketplace?
This is:
- prior art
- obvious use of technology
- using existing technology exactly as intended AND documented
- merely a clever rewording of existing techniques
America really, REALLY needs to eliminate software patents, and the USPTO should issue a statement saying "to protect your software innovations, refer to the Copyright Act." But of course, patent application fees keep the USPTO running and provide job security, so we won't see that common sense rule come into place in the foreseeable future.
The Christian Right is Neither (Christian nor right). See: Matthew 23, Matthew 25, Ezekiel 16:48-50
As someone that's currently working on some of LSI's driver code (as a customer, bought in), I wouldn't be at all surprised if they think its something new. Their code is terribly unstructured, uncommented, makes use of dynamically changing function pointers, has random inline assembler and has little in the way of API layering to make it understandable. Its a nightmare from a developers point of view. They probably think its a new and exciting breakthrough. :(
They'd have a decent revenue stream from high quality patents and an incentive NOT to just push things through a past a rubber stamp...
They'd have to employ real talent then for patent examiners...
Donald 'Duck' Dunn: We had a band powerful enough to turn goat piss into gasoline.
a patent on "An array data structure that automatically grows itself when it's current size is exceeded"...
:)
That patent is already owned by Microsoft, and is in use in their operating systems and device drivers. Most people call it "bloat"
Seven puppies were harmed during the making of this post.
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.
Sometimes it's best to just let stupid people be stupid.
Fuck, I'm patenting the binary search tree. What do mean prior art? Who do you think you are, Donald Knuth?
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.
The world will not get better through technology. We must seek to be better people.
From an old slashdot comment by ShadyG (written before this patent was submitted btw) http://yro.slashdot.org/comments.pl?sid=11208&cid= 350375 :
:)
"The example of one-click shopping is even more illustrative. Something that is obvious will have no prior art, for the very reason that it's not worth publishing. What am I going to do, publish a solution for a doubly-linked list just to prevent a patent from getting issued on it? "
Indeed, I guess you should have
Those of you with a cynical nerve will probably claim that we will soon see a patent that deals with NUL termination of a string of characters...
This very same examiner (John Breene) has also granted patents #6944634 (file caching) and #6745181 (query based search).
You mean like the master key in a fifth normal form database (binary normalized) data base.
Undetectable Steganography? Yep, there's an app fo
If you describe something in a complicated enough manner then it is quite possible to pwnfuse someone into accepting it. Now if there was only some way to demonstrate prior art or the fact that it is an obvious function..
Until that day comes along, I guess we just have to see Parent and ensure we keep patenting appropriately.
Oops, I now have a doubly-linked post. I suppose I should expect a call from LSI soon.
Proof by very large bribes. QED.
A large oil company spends $1 Billion developing software that takes existing geological maps and analyzes it in a novel way. This robot is so effective at what it does that they patent it to ensure they protect their investment.
For argument's sake, tell me the difference between these two scenarios:
The difference is, nobody spends $1 billion developing a basic software algorithm. It's telling that the example you are trying to use to justify software patents is fictional.
paintball
I am not a computer science programming guy, so I wouldn't know how to find prior art on this. I am not a lawyer, so I don't quite know how to make an Amicus Brief that would be useful in court against any suit.
However, it appears that a bunch of the posters are, and do know of possible prior art.
So how about creating a little space on Sourceforge, or Groklaw, that is a repository for anti-patent prior art. We (community) use this example as a nugget for action. Use this patent's number as an index, and make a searchable repository of information, like "I saw the prior art against this in 'Introduction to Database Design by Ewe Eediot, published by Killatree, 1978'. Even better to include the ISBN number of the book. Then we just need a lawyer to convert it into a usable amicus brief. Leave it all open information so that anyone can use this to kill this dumb patent. Lather rinse repeat for any other patent.
Oh, and maybe a link to donate to the owner of the repository for their costs. You know, for when a $billion$ dollar lawsuit is filed, and this repository saves someone's corporate donkey. And the lawyer (or company owner) realizes that this has been a help, and wants to play nice. It'd be cool for Groklaw to suddenly be fully funded due to having solved the patent mess.
If this has been taught in computer science, it has been published, right? Even the obvious stuff has to be shown to a beginner.
Oh, does referencing code that Does This Action count? Can we reference a block of MySql that shows in 1997 this was already possible, and obvious? Doesn't the release date of Open Source material count as 'publishing'? It is being released for replication, and viewing by multiple people. And it does carry a copyright with certain restrictions.
This would be a good disincentive for the pursuit of these patents, and if done right (searchable) might create a way for the (clueless) patent examiners to more easily find prior art. We could work with the patent exaiminers instead of complaining about them.
I'm serious here. Sorry to only be an idea guy. Please reply to this with why it will/won't work. Or better off, go implement this. Happy Thanksgiving!
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).
There's one claim for a list where the nodes have two pointers, and another where the nodes have three pointers. A double-linked list is a specific implementation of the first claim, where the two sort orders happen to be forward and backward. His claim is broader than that, since his two sort orders can be unrelated to each other, but since a double-linked list falls into his definition, his first claim is certainly not novel. And, of course, nothing he claims would be non-obvious to a programmer, but I have no idea how one goes about showing that in court.
..holy sh*t, this is incredible (Well, sadly not). For convenience, here's the PTO's version of the patent, better to use because it has links to some of the cited prior art patents. Additionally, consider looking at the prosecution of the application. You can download a pdf of the "image file wrapper" which includes the examiner's action and applicant's response.
..." Now Porter goes on to add an auxiliary array of
pointers (but for a more refined use than just an index) but the basic
concept of a doubly linked list is here. Even the examiner very briefly
acknowledged in passing that Porter showed a doubly linked list, but
obviously failed to recognize that this fully meets claim 1 (including
the redrafted version); she obviously did not understand what the
applicant was showing. If there are any doubts about what arrangement
of data are being disclosed and claimed here then just look a Figure
one in the drawings (You have to use the "Images" link at the top which
will take you to a clumsy page that displays the sheets of the actual
patent specification using some specific tiff format, so your browser
must be capable of displaying these images).
There was a nominal rejection under 35 USC 101 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 as being anticipated by the patent to Schwartz. 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 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?