Slashdot Log In
LSI Patents the Doubly-Linked List
Posted by
CmdrTaco
on Thu Nov 23, 2006 11:45 AM
from the all-your-b-trees-are-belong-to-me dept.
from the all-your-b-trees-are-belong-to-me dept.
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."
This discussion has been archived.
No new comments can be posted.
The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.
Full
Abbreviated
Hidden
Loading... please wait.
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.
Re:OK, this is just ridiculous. (Score:5, Interesting)
Ah no this is not necessarily the case. Sometimes it takes longer then this without having to go through appeal.
This is often true but usually it is the first one that is clueless. If it is appealed then the second examiner has the comments of the first - as well as the listed prior art. So the end result is that appeal you actually need to come back and show why the claimed prior art is not really prior art. This is tougher. (Been there done that.)
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.'
Parent
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.
Parent
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.
Parent
Re:OK, this is just ridiculous. (Score:5, Interesting)
A large oil company spends $1 Billion developing a 3d nuclear imaging robot that burrows into the ground to explore for oil. This robot is so effective at what it does that they patent it to ensure they protect their investment.
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.
The investment and results are the same in either case, the only difference is that we're talking about something physical instead of software. An outright "No Software Patents" stance would say that any company could then duplicate the oil company's unique software, leaving them no protection for their massive investment and intellectual property. Why would software be any different than a machine here?
If we remove all software patents, we also remove part of the incentive for large corporations to invest in software. There needs to be some protections, they just need to be smart.
Parent
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.
Parent
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.
Parent
Re:OK, this is just ridiculous. (Score:5, Interesting)
Patents, therefore, are a tradeoff. They protect the inventor while encouraging them to disclose their techniques. Thus, the inventor gets something (a government protected monopoly for a limited period), and society gets something (access to the details of the technology).
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.
Parent
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.
Parent
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.
Parent
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?
Parent
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.
Parent
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).
Parent
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.
Parent
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.
Parent
Re: (Score:3, Funny)
Object-oriented kittens have no ->microwave() method, but real world microwave ovens use a procedural model.
Your object model is screwed - microwave isn't intrinsic to kittens - microwaves have a method called nuke (thing t) (throws Sparks)
Re:OK, this is just ridiculous. (Score:5, Funny)
Parent
Re:OK, this is just ridiculous. (Score:4, Funny)
Learn to code instead of whining ya damn kids!
Parent
Re: (Score:3, Funny)
Re:OK, this is just ridiculous. (Score:5, Funny)
Because "nuke" is 3 times shorter than "microwave," and approximately 5 times more fun to say.
Parent
Re: (Score:3, Insightful)
Re:OK, this is just ridiculous. (Score:4, Interesting)
Parent
Re:OK, this is just ridiculous. (Score:5, Insightful)
That's because being ambiguous and self-contradictory is its purpose. [fsf.org]
Parent
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.
I Agree (Score:5, Funny)
Until that day comes along, I guess we just have to see Parent [slashdot.org] and ensure we keep patenting appropriately.
Oops, I now have a doubly-linked post. I suppose I should expect a call from LSI soon.
Parent
Well, duh (Score:5, Funny)
Patent reform anyone? (Score:5, Insightful)
Re: (Score:3, Interesting)
I think it's high time for a "demilitarization" of the corporate world, then - don't you? The collateral damage of these corporate battles is, as always - the little guy. The open source projects. It's the weak that needs to be protected - not the strong. Now any open source program can be sued if it uses a linked list? What's next - the for/next loop or the do/while loo
Re:Patent reform anyone? (Score:5, Interesting)
What you need is legal reform.
And not what has passed as tort "reform" in our political debate. Freedom of the press was once said to belong to the man who owns one. Now justice is the right of every man to the degree he can pay for it.
What passed as tort reform was about restricting access of individuals to the legal system. Such a restriction would limit abuse by individuals, it is true; it would also limit legitimate uss of the legal system by the little guy, leaving the wealthy in full possession of the tools of legal extortion.
Patent reform would take away one tool of legal extortion by parties with deep pockets, so as far as it goes it is good. Also, the existing legal tools against filing false patent claims should be enforced vigorously.
I think that extortion by frivolous legal threat should be a felony. People who use this should be face criminal and civil penalties. Companies that use this tactic should be treated as racketeers. Lawyers who abet this should be disbarred and jailed.
Conceptualy, what could be simpler? Naturally, you want to said the bar for frivolity very high. But once a few bugs have been squashed against that windshield, the rest will learn to avoid it.
Parent
WTF? (Score:5, Interesting)
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.
Probably because LSI have only just discovered it (Score:5, Funny)
I'd like to make a suggestion... (Score:5, Interesting)
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...
Re: (Score:3, Interesting)
BTW, it should be required that the patent applicant should prove it made a reasonable effort to find about prior art and demonstrate it found none.
This patent, obviously, would fail in that regard.
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.
Re: (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
Re:Not exactly (Score:4, Insightful)
Parent
Re:Not exactly (Score:4, Interesting)
The absurd part about this patent is that it is incredibly obvious, and unlike the one-click patent which is arguably obvious but also because of the age of the 'net possible that Amazon was the first ones to do it, multiply linked lists have undoubtedly been done since we've had pointers in computer architectures.
Parent
Fifth Normal Form. (Score:3, Insightful)
That's it. (Score:4, Funny)
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.
Regarding an old comment on slashdot... (Score:4, Funny)
"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...
USPTO is a joke... (Score:5, Informative)
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).
Parent
Recent technologies LSI had patented include : (Score:3, Funny)
"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.
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: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.
Parent
So go kill it! (Score:3, Interesting)
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!
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:What's next? Patent on "Arrays that self grow"? (Score:5, Funny)
That patent is already owned by Microsoft, and is in use in their operating systems and device drivers. Most people call it "bloat"
Parent
Re: (Score:3, Informative)