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...
Not quite. The patent is for objects that are indexed on multiple lists rather a double linked list as most programmers know it. It's still a common contstruct.
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.
"Method of using the method of strongly straining the waist muscles in order to help turd excretion"
"Method of dissolving a solid dissolvable material in water utilizing the method of mixing the fluid and solid with a tool"
"Method of moving a finger back and forth and applying limited pressure, thereby removing an itch in a body part which has been itching"
and so on.
Read radical news here
If the submitter and editor had bothered to RTFP (read the f*cking patent), they would see it is covering avery specific implementation of a linked list. The patent covers the idea of having a linked list of pointers with *two ancillary linkakges*. What this allows essentially, is for you to have a list sorted in two totally different orders at the same time... if you traverse linkage A, you get one order, if you traverse linkage B, you get the other.
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.
What the patent says is may be traversed in at least two sequences.
You mean like forward and backward???
What are you doing now, you lazy drunken obscene unsayable son of an unnameable gipsy obscenity?
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.
It looks like no one has bothered to read the patent (even the original poster who kindly included a link to it).
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.
Give the man a cookie. Finally, someone who actually understands the purpose of patents. The whole deal, here, is that, in the past, people just kept their inventions secret if they could. The end result? Techniques could die with their inventor (read about Damascus steel for a great example of this). And, as you say, meanwhile people have to duplicate the effort.
And where is the evidence that the system is working? In practice, it looks like companies are primarily using software patents to protect (1) things they have to disclose anyway as part of doing business, (2) application areas without actually disclosing how to do anything, and (3) ideas that are basically just straightforward engineering.
Patent protection keeps other people from using their own ideas and the results of their own labor. That is something extraordinary, and it should require extraordinary evidence to keep it in place. So far, software patent proponents have provided not a shred of evidence that software patents are beneficial.
as I read the patent it's simply a patent for list elements that are in more than one list at the same time - prior art up the wazoo of course (Unix V6 from the late '70s for a start)
..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?
I would have loved to tell my Data Structures professor a year ago that I couldn't do my homework because it would infringe on a patent.
Ok, to summarize said claims and said summary:
... It would therefore be advantageous to provide a system and method for quickly traversing a sequential list in a second sequence."
1) A data structure where each item has two (or three) pointers, and specifically it has to be done so that there are exactly two (or three) ways of traversing the list.
This is not a doubly linked list, nor does it resemble one: doubly linked lists have ONE ordering, each item using two pointers to point forwards or backwards with respect to the ordering. The point is that this patent presents a completely and utterly useless data structure. A linked list is not made for searching quickly. But yet, the patent claims:
"The conventional method of searching a list is sequential. This involves traversing the list to locate a specific item in the list. [...] The conventional method is time consuming and may require many computational cycles to find the necessary items in the proper sequence."
This method is not conventional. It's the only method. That's the whole point of linked lists. Then it continues:
"Lists may be sorted so that the items may be accessed sequentially. Once the list is sorted into a particular sequence, the individual items may be accessed in order very quickly. However, there is substantial overhead in the reordering of the items into the desired order."
If it means accessing an individual item randomly, this cannot be done, unless the list is first sorted into an array and use binary search, which breaks away from the linked-list structure. If it means accessing all items in order, then no, there is no substantial overhead in the reordering of the items.... it's the same overhead as accessing the items in order.
Then the conclusion sums up these fallacious arguments into its climax:
"In some cases, there is a need for the list to be presented in more than one order.
Indeed it would be nice to quickly traverse the list in a different order. But first this does now allow us to search better (as suggested in the first paragraph), nor is the new data structure more efficient than other data structures out there (you CANNOT do better than linear time sorting if you need to traverse the list!).
This is like a classic example of a "bad, horrible" data structure that undergraduates are asked to analyze in a homework question, like "here's a data structure. Write a paragraph showing why it isn't a good idea. Can you come up with something better?"
Notice that this structure does NOT allow constant time insertion/deletion, which is the whole point of linked lists (the tradeoff for not being able to search quickly). Without a tree structure, there is no way of knowing where to insert a random element, except to prepend or append it to the list. So when insertion/deletion is frequent, binary search trees are better, as they still allow linear time traversal. If search time is critical, use hash tables. If one needs multiple orderings, then use multiple index trees (aka database). When the data is fixed and never changes, then multiple arrays storing values and pointers to the items are better, because they not only allow linear time traversal, but also fast search. I can go on and on here... to put it bluntly, the said data structure is a new idea, in the sense that it's so stupid no one would actually use it (and thus would never mention it).
Don't worry guys. This patent managed to dig so low technically that it is worse than obvious data structures. And if anyone is dumb enough to pay them for such patent... well, natural selection.
Did you know that the XOR function was patented and earned the Patent Holder countless millions until it recently expired? are also patented!? This patent was actually enforced in 1994 to stop the sale of the Amiga Computer in the USA after Commodore stopped paying royalties on the patent. The XOR function was used to move the cursor around the screen.
Patents on algorithms and software should be disallowed.. as these types of patents are ripe for abuse!
Yahma
ProxyStorm - An anonymous, free, apache based proxy server.