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)
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.
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.
I've done this kind of thing before in my programs and I am by no means a professional programmer. Just a dude who got hooked on C 17 years ago and likes to mess around with a computer. US patent law is broken. What's worse is the way the US tries to make the rest of the world accept it as well.
Seven puppies were harmed during the making of this post.
A double-linked list is a special case of the technique described in the patent, and should as such be enough to invalidate the. The summary also mention other special cases of the patent claim.
You mean like the master key in a fifth normal form database (binary normalized) data base.
Undetectable Steganography? Yep, there's an app fo
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
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.
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.