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."
OK, this is just ridiculous. (Score:5, Insightful)
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.
How to obtain a U.S.-patent: (Score:4, Insightful)
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.
Patent reform anyone? (Score:5, Insightful)
Re:OK, this is just ridiculous. (Score:5, Insightful)
No! That would only make things worse. Government is always too slow in this kind of thing anyway. Just do away with "software" patents completely. Copyright yes - of the FINISHED WORK. Patents no. It's like a painter who wants to patent or copyright every separate blob of paint on his canvas. This does not make sense.
Re:Not exactly (Score:3, Insightful)
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.
Re:Not exactly (Score:4, Insightful)
Re:OK, this is just ridiculous. (Score:3, Insightful)
Re:OK, this is just ridiculous. (Score:5, Insightful)
You know, it's up to the oil company to make sure that no one gets their hands on the software, just like Coca Cola makes sure no one finds out about the "secret formula". If someone outright steals the software and sells it to someone else, copyright law is now full of 6 figure fines and jail time - enforce THAT. What's really happening is that people are not protecting systems. They are trying to "protect" tiny parts of programs. This essentially stops anyone else from creating a program that does roughly the same thing. Even if it does that same thing in a different way, it will definitely wind up in court. That's absurd. Yes the whole system you describe warrants protection.
But not the individual algorithms for goodness sakes. Here you could argue "but what about scientific formula and drugs, and the pharmaceutical industry". That's different - these people are FORCED to reveal their work in order to pass the FDA. They need greater protection since they can't keep the contents of their meds a secret. But for the rest, I think most of burden of protecting trade secrets should fall on the industry that has the secret - not everyone else having to prove via defensive litigation that their software does NOT infringe on a "patent" for some algorithm or other because it does something similar.
Re:OK, this is just ridiculous. (Score:2, Insightful)
Unlikely that they would be able to protect it but I doubt that they did it for 'bragging rights'. It is too expensive to do it for 'bragging rights.'
No, they do it because R&D gets their bonuses based on how many patents they get.
Fifth Normal Form. (Score:3, Insightful)
Re:OK, this is just ridiculous. (Score:5, Insightful)
The "only" difference? You make that sound like it is of minor importance. It is not. Software is intellectual property. You don't go around patenting the plot of a book or a movie, the chord-progression in a song, the concept of "self-help" audiotapes, or the new mathematical theorems discovered by some genius mathematician (or algorithms, business methods, or sequences of base-pairs for that matter, although sadly the US has started doing just that)
Patents are a very specific right that is granted specifically to give the inventor of new inventions a fair chance of recouping his investments. Unlike music or software, which is protected by copyright, once someone invents e.g. the four-stroke combustion engine, anyone is free to produce it. Patents are designed to help the inventor here, it's not a general purpose mechanism of protecting all kinds of "ideas". The "default" position is to have no patents at all. Arguing that since patents protect one kind of idea, it should protect other kinds of ideas, is completely silly. And patenting software, business processes, or genes is also silly.
Exactly. We remove some of the incentive for large corporations to invest in software. At the same time, most of the incentives remains, such as having some new software "that takes existing geological maps and analyzes it in a novel way". This software can be used internally for finding oil, it can be licensed to other companies, or used in lots of other ways to generate profit.
Also, it should be made clear that even if software patents benefits large companies (which I believe was true at some point, although I'm starting to doubt it still is), it does not benefit small companies. Taking away software patents makes it easier for small companies to invest in software. I'm not particularly in favour of laws that only benefits large companies.
Re:OK, this is just ridiculous. (Score:5, Insightful)
And thus, the company never publishes the things they discovered and society has to keep reinventing them, since everyone who discovers them keeps them secret. Whereas with patents, the company gets a monopoly on that particular thing for 20 years and then society is free to use it for eternity. What you propose just results is massive duplication of research.
Re:OK, this is just ridiculous. (Score:4, Insightful)
Nice theory. It's also completely and utterly at odds with the foundation of modern free market competition.
The free market has one fundamental incentive; you do it cheaper and you do it better than the competition or you _lose your investment_.
'Protect' investments and you lose that incentive; you end up no better than protected state monopolies. See the former Soviet union for indications on the particular efficiency of state protected monopolies.
'Protection' is for investors who dont want to work for their money (aka, rent-seeking); the fundamental nature of 'investment' is that you _risk_ your money for a return.
"There needs to be some protections, they just need to be smart."
No there doesnt. In a functional market there is no god-given right to make a profit off investments, there's only an eternal struggle to be slightly more efficient and thus more profitable than the competition. You spend that billion (or preferably much less on incremental improvements instead of huge-ass failure-prone glitz projects) because if you dont the competition is going to wipe the floor with you and you might just as well liquidate while the going is still good (thus freeing up investor capital to go to some more forward looking venture).
Strawman! (Score:4, Insightful)
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.
Re:OK, this is just ridiculous. (Score:4, Insightful)
No. It's not software patents, per se, that is the problem. It's being able to "patent the bleeding obvious" that is the problem.
This particular example, IMHO as "one skilled in the art [of computer programming]", falls slap bang into the "obvious" bucket.
There is nothing wrong with having technical software (or any other method of implementing) patents provided what is being patented is novel and non-obvious.
Re:NOT doubly-linked list. It's a triple linked li (Score:4, Insightful)
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.
Re:OK, this is just ridiculous. (Score:5, Insightful)
The problem is that for almost all software patents, a monopoly is being granted for details we did not actually need to know, because they are obvious to anyone 'skilled in the art'. Or even 'unskilled in the finger daubing'. The value of the monopoly is much, much, greater than the value of the information we're getting.
I'd venture that this is true not just of software patents, but in software, the progress made in the absence of a patent regime for so many years spoke volumes about the lack of a need for patent protection.
Re:OK, this is just ridiculous. (Score:5, Insightful)
So basically we have 2 options:
1. Disallow software patents, people wishing to protect their work will keep it secret and other people can come up with their own (probably very similar) solutions to the same problem.
2. Allow software patents and therefore prevent *anyone* else from producing anything similar on their own.
Option (1) seems like the better option to me since at least it allows third parties to come up with a solution. Remember that in most cases the patent holder either won't licence their technology at all, will licence it for infeasable amounts of money, or put very restrictive terms on the licence (what good is the ability to use some technology if you're not allowed to integrate it into your FOSS project?)
And this is assuming you even realise you're infringing someone's patent. Remember, you're still infringing a patent even if you came up with the idea on your own - all too often a product is developed independently, becomes very successful and then the producer is sued for infringing a patent that they had never heard of. It's now got to the point where it's pretty much impossible to write a piece of software without infringing _someone's_ patent.
Also, from my experience the threat of people suing for patent infringement often motivates corporations to keep source code closed which they would otherwise be happy to open to the public - this is certainly not a good thing.
Patents have been turned into ammunition for large corporations - having 100,000 patents prevents the guy who only has 80,000 patents from suing you. Unfortunately the little guy who's got no patents and no money for lawyers gets completely squashed in the process. Maybe patents are sometimes good for small inventors, but they are open to abuse by large organisations. And even if you are in the right and have prior art, how the hell are you, as a single person on your own, going to be able to defend yourself in court against some huge corporation such as IBM, Microsoft, HP, etc?
Re:OK, this is just ridiculous. (Score:5, Insightful)
Give this AC the whole EFFing bakery. Finally, someone who actually understands the effects of software patents in the real world.
In the "copyright debate" there is lots of arguing back and forth about the necessity of copyrights to encourage the "progress of science the useful arts." But it is all just a bunch of postulating.
Here we have demonstrable proof that software patents are not necessary because the whole shebang is only about a decade old, and their creation has not done anything to markedly improve the situation. If anything, it has been the reverse with proprietary software stagnating and consolidating into a handful of big corps like MS and Oracle. All the really innovative stuff is happening in the Free world which is antithetical to the idea of software patents.
Re:OK, this is just ridiculous. (Score:2, Insightful)
Re:OK, this is just ridiculous. (Score:3, Insightful)
the problem being that they aren't patenting applications, but rather that they are patenting concepts, which often are timeless.
Re:OK, this is just ridiculous. (Score:5, Insightful)
Bragging rights are totally worthwhile, if they keep investors happy. And corporations routinely spend up to 30% of their revenue on keeping investors happy. The cost of a few bogus patents are peanuts as a part of that.
Re:OK, this is just ridiculous. (Score:3, Insightful)
How exactly are these companies not keeping their inventions secret? Where is the source code?
The patent system is failing to solve this problem. Companies have realised that they can simply patent some parts of their invention, and keep other parts secret, so they get the 'best' of both worlds - nobody can legally copy their invention, and nobody can technically copy it either because they don't know enough about it - and reverse engineering is now outlawed thanks to the DMCA, so nobody can legally find out how the invention works in that way either. Furthermore, the extra layer of copyright means that the patents never expire (because copyright on the patented code never expires, so even after the patent runs out, you still can't use it unless you're willing to spend large amounts of money in court, proving that your implementation doesn't infringe).
Read any software patent. It describes part of a system but doesn't say enough for a person "skilled in the art" to be able to recreate the system. By intentionally patenting only some of the system, the 'tradeoff' is completely destroyed. Patents are monopoly abuse, period.
Re:OK, this is just ridiculous. (Score:3, Insightful)
The only clear (and positive) way is, in fact, very easy: "noone".
Re:OK, this is just ridiculous. (Score:5, Insightful)
That's because being ambiguous and self-contradictory is its purpose. [fsf.org]
How is this NOT new? (Score:2, Insightful)
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.