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."

OK, this is just ridiculous.

[Josh Lindenmuth]

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.

Re:

[robogun]

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".

Since LSI actually produces something (unlike SCO) hopefully we won't be seeing the "all your database are belong to us" letters anytime soon. But that doesn't change the fact that they can do it.

Re:OK, this is just ridiculous.

[Dachannien]

All LSI really produces nowadays is intellectual property. They got rid of their last fabrication facility a year or so ago, and subcontract all their fabrication needs to other companies now.

Re:

[grcumb]

All LSI really produces nowadays is intellectual property.

Could someone please explain what that term means? Honestly, it get (ab)used all the time, and, for the life of me, I can't see any way of creating a definition that would have a chance in hell of ever being anything but ambiguous and self-contradictory.

Intellectual - Of the mind. That's pretty clear, taken alone.

Property - Something that belongs to one person, entity or group, and to them alone.

How in tarnation, I would like to know, can s

Re:OK, this is just ridiculous.

[Knuckles]

I can't see any way of creating a definition that would have a chance in hell of ever being anything but ambiguous and self-contradictory.

That's because being ambiguous and self-contradictory is its purpose. [fsf.org]

Re:OK, this is just ridiculous.

[billsoxs]

This patent was first submitted in 2002, which probably means it was turned down and appealed at least twice.

Ah no this is not necessarily the case. Sometimes it takes longer then this without having to go through appeal.

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.

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.)

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".

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.'

Re:

[shario]

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.

Re:OK, this is just ridiculous.

[Mark_MF-WN]

It's probably worth it if you're a CEO for a corporation. After all, CEOs don't spend their own money, they spend the company's money. It would hurt the shareholders, but if it makes the shareholders think that the CEO is doing something awesome (what could be more awesome than synergizing an IP portfolio?) that will make money, then they'll keep paying the CEO.

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:

[NMerriam]

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.'

Most research groups and companies use patents as a metric for success. It's something they point to when searching for investors, when reporting progress, when evaluating raises and promotions. Spending a few thousand dollars of corporate money on a useless patent is a bargain if it gains your company, division, or personal salary a boost.

Re:

[ajs318]

Perhaps the solution is non-discriminatory licencing of all patents. In other words, if X owns a patent, and they licence it to Y, then they should also be bound to licence it to anyone else upon exactlythe same terms -- or not licence it at all.

Re:

[Fulcrum of Evil]

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.

[I Like Pudding]

Not enterprise enough. You should set it up so that the ThingImpl superclass implements INukable, then update the XML mappings in 6 different places.

Re:OK, this is just ridiculous.

[grimJester]

You realize you've been in the business too long when you actually find these jokes offensive...

Learn to code instead of whining ya damn kids!

Re:

[tehshen]

you named your kitten Sparks?

Re:OK, this is just ridiculous.

[wirelessbuzzers]

Why do people persist in the "nuke" and microwave myth?

Because "nuke" is 3 times shorter than "microwave," and approximately 5 times more fun to say.

Re:

[gmack]

I don't think that would help. This is a patent on a linked list with two sets of pointers. This contstruct is COMMON and If I had to send everyone with a patent on some common data structure for every user I shipped the costs would very quickly outstrip any revenue generated. The only way your idea can work is if we go back to charging $1000+ for software.

Re:OK, this is just ridiculous.

[Dunbal]

Our government needs to more clearly delineate what software can and cannot be patented in order to prevent more ridiculous patents.

      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:OK, this is just ridiculous.

[Josh Lindenmuth]

For argument's sake, tell me the difference between these two scenarios:

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.

Re:OK, this is just ridiculous.

[Dunbal]

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.

      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:

[Josh Lindenmuth]

They are trying to "protect" tiny parts of programs. This essentially stops anyone else from creating a program that does roughly the same thing

You hit the nail on the head. The smaller the software component, the more ridiculous it becomes to patent. Patenting the doubly linked list just takes this to the extreme.

Re:OK, this is just ridiculous.

[Kuciwalker]

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".

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.

[Abcd1234]

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.

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.

Re:OK, this is just ridiculous.

[Anonymous Coward]

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).

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.

[Jah-Wren Ryel]

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.

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.

evidence, please

[oohshiny]

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) th

Re:

[DamnStupidElf]

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.

I don't know about that. Most of the most famous inventions were generally unprotected by patents or heavily overpatented. Printing presses, sc

Re:

[asuffield]

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.

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

Re:

[Loconut1389]

Surely, for the good of humanity, everyone -should- reveal their greatest creations and it would be greedy not to.. but it is the way the world works. Patents are a fair compromise as you point out- but I don't see any huge problem with duplication of research. If I independently come up with the same formula you did (even perhaps without awareness of the existence of you at all), patent and copyright law say I can't use it, since there's no real way to prove I didn't steal it. But say we did abolish patent

Re:OK, this is just ridiculous.

[FireFury03]

What you propose just results is massive duplication of research.

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:

[compro01]

In 20 years, that software will very likely be next to worthless and out of date anyways. Application software just doesn't stand the test of time like physical products do.

the problem being that they aren't patenting applications, but rather that they are patenting concepts, which often are timeless.

Re:

[sulam]

If you've done any medical software, you'd know you're forced to reveal algorithms there, too.

Applying for the patent in fact _forces_ you to reveal the algorithm to the entire world. That's the entire point of the patent process. You reveal it to the world instead of hiding it, and as a result you get exclusivity for a period of time. If you don't want to reveal it, you have no leg to stand on if someone else manages to also invent it. There are very good historical reasons for this system, the most signif

Re:

[E++99]

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". ...I think most of burden of protecting trade secrets should fall on the industry that has the secret.

That's what patents were invented to avoid. They offer the best of both worlds -- the company reveals their innovation for the benefit of the world, and in return the government grants them the right to license the use of the invention f

Re:OK, this is just ridiculous.

[joto]

The investment and results are the same in either case, the only difference is that we're talking about something physical instead of software.

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.

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

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.

[Znork]

"If we remove all software patents, we also remove part of the incentive for large corporations to invest in software."

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).

Re:

[msobkow]

the only difference is that we're talking about something physical instead of software.

I disagree completely.

The robot is a complete assembly designed for a purpose.

Most software "patents" are on the reuse of existing techniques, algorithms, data structures, and approaches. The only thing "special" is that they identify a specific data attribute or business use.

Can you patent the use of a wrench to tighten bolts on a wheel? No. You can only patent the overall design of the wrench.

"Business proc

Strawman!

[raehl]

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.

Re:

[Scarblac]

A large oil company spends $1 Billion developing software that takes existing geological maps and analyzes it in a novel way.

Great! They deserve protection, of all that work - that's what copyright is for.

As for patents, they're for the idea. Some people have an idea, and use a few weeks to draft a good patent application. Then, they can sue one of the companies who had the same idea and that actually did all the work of building it for a billion and making it profitable.

The thing is, in software, ide

Re:

[gid13]

Hell, I'm in the "no patents at all" camp. I don't care how many people say it will, innovation is simply not going to die just because we remove a temporary exclusive right to profit from inventions.

Re:

[morgan_greywolf]

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.

No software should be patentable.

Per the USPTO, "a patent for an invention is the grant of a property right to the inventor, issued by the United States Patent and Trademark Office." The USPTO goes on further to say that there are thr

Software Patents

[Morosoph]

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.

You simply cannot change the nature of the beast. Peer review would be the only way, but that's not going to happen: it would be extremely expensive, and the system of patents helps politicans to get some kind of handle upon crea

Re:OK, this is just ridiculous.

[N Monkey]

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.

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.

Actually, not so ridiculous.

[Great_Geek]

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

Re:

[turbidostato]

"Our government needs to more clearly delineate what software can and cannot be patented"

The only clear (and positive) way is, in fact, very easy: "noone".

Re:

[protomala]

That's why the law here in Brazil says that you can't register, patent or have any rights over programming methods (as double linked lists, that I use a lot anyway).

Recentlly Bush administration, in coordination with their effort to combat piracy tryied to get brazilian government to adopt patents for software togheter with enforcing piracy combat, otherwise we would be in a black list and loss millions on tax reduction for products like orange juice (yeah, buying computers and selling juice is stupid, bu

How to obtain a U.S.-patent:

[foobsr]

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.

Re:

[$pearhead]

Put the result through a patent-lawyers office in order to make sure the claims get even more obfuscated

Essentially, use the words "comprising" and "embodiment" extensively.

I Agree

[slashbob22]

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 [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.

Re:

[ScrewMaster]

Some years ago I received a patent on an industrial data acquisition system. I spent about two weeks on my part of the patent submission, including (gagh!) flow charts and a very clear, concise description of the software, and the subsystems it controlled. It was then submitted in a batch with several related patent applications from the company for whom I was consulting at the time.

Their patent attorney actually called me long distance just to say how pleased he was with the clarity of the write-up ...

Well, duh

[Linker3000]

The author seems to think that rational thought, logic and common sense plays some part in the patent granting process in the USA.

Re:

[kimvette]

Oh but it does, but in a skeevy way:

This is likely on the mind of every patent clerk at the USPTO: "If we accept these software patents, we collect patent application fees and keep our jobs. Let the courts sort it out since we don't understand this stuff, it's all greek to me anyhow."

Patent reform anyone?

[sinij]

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.

Re:

[Dunbal]

Patents do not have to be meaningful... They are weapons in corporate world and you use them mostly to cause damage.

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?

[hey!]

What you need is not just patent reform.

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.

My own prior art!

[Chmarr]

I wrote a computer program back in 1988 that does exactly this kind of thing. Uses a forward-X and forward-Y links for the purposes of spatial ordering.

The program was a "mapping program" for a oldold mainframe computer game called "Space Empires". It was a turn-based exploration and combat system that generated it's output in a textual listing. Each "world" had a number, and listed the "worlds" that had appeared in the Up, Down, Left and Right directions. Very hard to get an idea of how things related unle

Prior art

[Salsaman]

Prior art right here [gnome.org]

Re:

[gmack]

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.

Re:

[timeOday]

How about the b-tree [helenos.eu]? Note the doubly-linked leaf nodes in addition to tree structure.

WTF?

[kimvette]

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.

Re:

[hey!]

I think this patent falls into the category of extensions to basic techniques so trivial and obvious that they are widely used but not widely documented.

They haven't patented the linked list. They've patented putting two links per node allowing different traversal orders. This doesn't necessarily appear in computer science texts because it doesn't really add anything new to the basic technique. Nor is it ever discussed because it's too obvious to merit discussion.

Back in the day, when database managemen

Re:

[GeckoX]

Google hits for "Linked List": ~1030000
Google hits for "Doubly Linked List": ~202000

5:1 ratio for something like this implies to me that it indeed is well documented. I was tought these in my 2nd semester C++ course in college.

It's well known, well documented, well used, completely obvious, and completely and utterly non-patentable...other than the fact that a patent was actually issued on it that is...

Re:

[GeckoX]

Come now, sure it's not your standard text book doubly linked list (each node linked to 2 nodes, the next and the previous), but how could one possibly consider arbitrary multiple linking within a list to be new and non-obvious?

I use linked lists of all kinds of various forms all the time. I also have absolutely zero dillusions that this is in any way unique or novel. I _know_ I didn't do it first, and I also know it doesn't matter who did. It is simply an extension to known internal linking structures. How

Probably because LSI have only just discovered it

[Anonymous Coward]

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. :(

I'd like to make a suggestion...

[advocate_one]

that the patent office get a small percentage of the royalties that a patent earns... and that the patent office bears the costs of the winning side when a patent gets invalidated... they would have an incentive to get things done right then...

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:

[rbanffy]

The royalties part may not work, but, certainly, bearing the costs of an invalidation and, eventually, having to pay damages for a bad patent would be quite an interesting change.

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.

Re:

[PeterHammer]

Yeah right, and make me, you and Joe Taxpayer pay for their imbecility.

No thanks.

Not exactly

[Reality Master 101]

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:

[Dunbal]

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

Re:

[matvei]

Read the rest of the summary:

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."

Re:Not exactly

[Per Abrahamsen]

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.

Re:Not exactly

[w3woody]

I've been using the technique in C of using two list pointers: one to keep my objects in a single-linked list, and another to store objects in a hash map, which uses a second series of singly-linked lists to track the objects in a hash bucket. And I've been using this technique since the 80's, easily.

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.

Fifth Normal Form.

[arthurpaliden]

You mean like the master key in a fifth normal form database (binary normalized) data base.

Re:

[beej]

I agree. Sounds more like a multiply linked list [safarix.com] to me.

To be fair, I learned about these in school about 15 years ago. So I've probably already forgotten all about it.

Re:

[timeOday]

Wow, that sounds precisely like the patent.

You're right

[taniwha]

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)

I had the same discussion in my SDL class...

[MMC Monster]

...in 1992.

Actually ours was a 4-way linked list to keep the list sorted by two different keys, with pointers to the next and previous element.

Unfortunately I cannot pull out the code (lost it a couple years ago), but it was part of an assignment to keep sorting times down in lists when sorted by multiple keys. Inserting a new item way O(n), but sorting by one of the pre-defined keys was then zero time.

Re:

[Ungrounded Lightning]

Unfortunately I cannot pull out the code (lost it a couple years ago), but it was part of an assignment ...

Contact the university for a list of classmates and/or the prof. At least one of the classmates may have kept a copy his solution and the prof will have the class notes.

Also: If the files were kept on a server farm (or a mainframe) the computing center may still have a backup. Digging it out would cost - but if a legal team is engaged in breaking the patent and is going to court the cost would be tr

That's it.

[Criffer]

Fuck, I'm patenting the binary search tree. What do mean prior art? Who do you think you are, Donald Knuth [wikipedia.org]?

consider SQL databases as prior art

[pikine]

For every table in an SQL database, you can create a number of indices. A singly linked list is like a table with one index. A double linked list is like a table with two indices, with the invariant that they're in reversed order of each other. In general, an n-ary linked list is like a table with a number of indices.

However, why settle for linear linked lists when a database can have better data structures like balanced trees and hash table?

Linux Kernel Supports Multiple Linked Lists

[Doug Dante]

The macro implementation of linked lists in the Linux kernel supports multiple linked lists per structure. It probably goes back to the late 1990s.

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...

[tamyrlin]

From an old slashdot comment by ShadyG (written before this patent was submitted btw) http://yro.slashdot.org/comments.pl?sid=11208&cid= 350375 [slashdot.org] :
"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...

Well, I'll throw my .02$ in here

[Mycroft_514]

I claim prior art as well. And my prior art is documented in the Library of Congress, where I put it. I built a database of my very own. It was completed in 1989 (or at least that was the copyright date).

Of course, my CS teacher for Data Structures might also be worried, as he was teaching patented material on this very subject in 1980.

Tiem to write the congress critters again.

Prior art

[SpinyNorman]

What about the pre-computer standard secretarial practice of photocopying documents so as to be able to file them in multiple folders in different orders, or multiple database indeces on the same table for that matter, not to mention a zillion programs that use structures with nextBiggest, nextClosest, etc links.

Maintaining multiple pre-sorted orders is blindinly obvious to everyone (and thus, in theory at least unpatentable) and has been since before computers even existed. It hard to know what's more path

Re:

[belmolis]

The usual Unix-type file system (in the sense of the mapping between paths and inodes, not the low-level sense of, say, ext3 vs. Reiser) is another example of this type, arguably closer since no copying of objects is involved. Due to the possibility of multiple links to the same inode you have potentially many pathnames for the same inode and, by assigning names appropriately, you can store multiple orderings.

Two possibilities...

[Per Abrahamsen]

The patent is either some sort of joke (like the guy who patented the wheel), or the computer science skill level at LSI must be incredible low.

USPTO is a joke...

[gustgr]

This very same examiner (John Breene [patentstorm.us]) has also granted patents #6944634 [patentstorm.us] (file caching) and #6745181 [patentstorm.us] (query based search).

Re: Examiner is a joke...

[kansas1051]

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).

Re:

[denis-The-menace]

For the highest briber, of course.

Gee, I wonder how many homes/cars he owns?

Recent technologies LSI had patented include :

[unity100]

"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.

Not doubly linked list- multiply linked list

[wk633]

Of course, this has been used since the beginning of (computer) time in the form of doubly-linked lists.

A doubly linked list just means previous and next pointers. That's traversing one sequence in either direction.

What the patent says is may be traversed in at least two sequences.

Which I remember drawing pictures of in my data structures class in about '86- and it was certainly nothing new.

Re:

[CarnivorousCoder]

What the patent says is may be traversed in at least two sequences.

You mean like forward and backward???

NOT doubly-linked list. It's a triple linked list

[brunes69]

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.

Re:NOT doubly-linked list. It's a triple linked li

[E++99]

it is certainly *NOT* a simple doubly-linked-list.

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.

Broken Laws

[camperdave]

I can't build a LEGO model of the Empire State Building without say-so from Shreve, Lamb and Harmon. I'm not sure whether my letter opener (which has a primary purpose of circumventing a technological measure that controls access to a copyrighted work) should be turned into the police (and whether I'd be arrested for doing so). I can't swing from side to side. Now I can't multiply link my data without paying royalties. "Land of the Free" - HA!

I have an idea. Let's hold Patent examiners legally and fi

So go kill it!

[Anonymous Coward]

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 don't know but...

[SQLz]

Would it be possible to sue the patent office for damages over bad patents? I mean, negligence, politics, etc all play a roll in the approval process. I suspect that a company sued of out existance over a questionable patent, should be able to sue the patent office. I bet that, would stop bad patents.

This is not even funny...

[grumpyman]

Next thing you know some bonehead lawyer thought of patenting the use of 0 and 1 and binary structure.

Prior art, circa IBM 1965-70

[gillbates]

IBM's VSAM implemented this almost 40 years ago. The idea was that there was one set of pointers for sequential access of records, and another set for "indexed" access. In fact, IIRC, you could have multiple keys indexing a VSAM dataset - the canonical example being that you could access records by last name order, ssn order, or whatever else you chose. You didn't have separate lists - the pointers to the next block were on the block itself. So given any starting index, you could traverse in whatever o

All I can say is...

[mavenguy]

..holy sh*t, this is incredible (Well, sadly not). For convenience, here's [uspto.gov] 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 [uspto.gov]. You can download a pdf of the "image file wrapper" which includes the examiner's action and applicant's response.

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 ..." 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).

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"?

[Dunbal]

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" :)

Re:

[hey!]

I've thought a stunning protest to absurd sofware patents.

I'm going to change my name to "Art Prior". Then I'm going to submit patent applications for all kinds of stuff that's alreay invented. Every time a patent examiner looks at one of my applications, it will be filed under "Prior, Art".