Forgot your password?

Linked List Patented in 2006 477

Posted by Hemos
from the good-thing-that's-protected-now-as-well dept.
An anonymous reader writes "Congratulations are in order to Ming-Jen Wang of LSI Logic Corporation who, in patent #10260471 managed to invent the linked list. From the abstract, "A computerized list is provided with auxiliary pointers for traversing the list in different sequences. One or more auxiliary pointers enable a fast, sequential traversal of the list with a minimum of computational time. Such lists may be used in any application where lists may be reordered for various purposes." Good-bye doubly linked list. We should also give praise to the extensive patent review performed by Cochran Freund & Young LLP."
This discussion has been archived. No new comments can be posted.

Linked List Patented in 2006

Comments Filter:
  • by erroneus (253617) on Monday March 19, 2007 @08:15AM (#18400059) Homepage
    People are immediatly shouting "prior art!" I don't care about prior art as much as I care about the fact that it's another software patent and unworthy of being patented.
  • by Short Circuit (52384) * <> on Monday March 19, 2007 @08:18AM (#18400077) Homepage Journal
    OK, so where do I go to submit prior art?

    I've got personal programming I've done that uses linked lists. I've got an instructor who's been teaching them in a 200-level C++ course for god knows how long. Hell, Herb Schildt's "C++: The Complete Reference" was published before this patent was filed in 2002.
  • by Doc Ri (900300) on Monday March 19, 2007 @08:30AM (#18400141)
    How exactly is backwards traversal more complicated than multiple sort orders? Backwards is just another sort order.
  • by Angostura (703910) on Monday March 19, 2007 @08:31AM (#18400147)
    Ah, but you should care. This is good news since it is another excellent piece of ammunition in the battle to show that the system is broken.
  • by malsdavis (542216) on Monday March 19, 2007 @08:36AM (#18400181)
    It's news like this which makes me glad I don't live in the USA!

  • by tepples (727027) <tepples&gmail,com> on Monday March 19, 2007 @08:41AM (#18400219) Homepage Journal
    The same patent was mentioned in this Slashdot article []. What is new since then?
  • Prior Art (Score:3, Insightful)

    by tonywestonuk (261622) on Monday March 19, 2007 @08:42AM (#18400239)
    Look here 0.misc/msg/205bb134a5ab9982 []

    What I describe, doccumented on the usenet, Is a multple linked list. I dont claim that I invented this method by any means - I'm sure someone must have come up with this b4 me as it is the next logical progression from a single linked list. BUT, At least I posted the method on the internet way back then, so prior art can definatly be proven.
  • by Mr. Underbridge (666784) on Monday March 19, 2007 @08:46AM (#18400273)

    All patents need to be abolished. They do nothing but hold back progress.

    Sure hippie. Just as soon as you explain to me how, without patents, a drug company would invest $100M in R&D for a drug that will take comptetitors $1M to copy, driving the price down to the point that they never recover their initial investment. And if your answer is "the government will do it!" look at the fantastic job they do running US public schools.

    Patents are a necessary part of scientific development. Doesn't mean I'll defend the current system, but pretty much any scientist will admit that some form of patent protection is abolutely necessary for many forms of research. This is particularly true for fields in which the barrier to market entry is low compared to the one-time research required to invent a product - like drug development.

  • by kwikrick (755625) on Monday March 19, 2007 @08:47AM (#18400283) Homepage Journal
    This is completely trivial, and any programmer could easily come up with this idea, if the application he is working on happens to needs to store objects in several sequences. I would not be surprised if thousands of computer programs use this structure but don't actually have a name for it. It's just a bunch of pointers after all.

    Luckely, the data structure descibed by the patent has very limited use. A more generic version would allow any number of pointers per item, and is typically called a graph. Still it is a terrible shame that the US patent office grants such patents.
  • by ThePiMan2003 (676665) on Monday March 19, 2007 @08:51AM (#18400315)
    Patenting y=mx+b as a method of drawing a line is wrong. Patenting a device that uses this to draw a line, that is different. Algorithms that describe basic ways of doing things are not novel. The biggest difference though is that with a device, if someone discovers some neat effect they can patent a certain way of doing it, but others can come an innovate on that device, inventing something that has the same effect but does it differently and is therefore not covered under the original patent. In software they are patenting the effect, here we have a mutli-way linked linked list, something that CS students have to do in freshman level classes. But now, we can't use it in any way without having to worry about defending ourselves. As someone who writes software for a living I would rather give up on ever getting a patent than having to worry for the rest of my life about implementing something someone else came up with and patented.

    The there is the issue that computer science moves along at such a clip that one company having a monopoly on an idea for the standard patent term could seriously stifle innovation in the field, which is directly against what the entire point of patents are.
  • Re:Prior Art? (Score:5, Insightful)

    by Fordiman (689627) <fordiman AT gmail DOT com> on Monday March 19, 2007 @08:57AM (#18400381) Homepage Journal
    Well, if your read the patent, it's for triply-linked lists, the purpose for which I can only fathom. Possibly, it's easier to sequence them for block encryption or somesuch. Though, I also imagine that the patent will get killed for its obviousness; adding a tertiary pointer when you need to access a list via another sequence is pretty damned obvious.
  • by tomstdenis (446163) <tomstdenis AT gmail DOT com> on Monday March 19, 2007 @09:07AM (#18400461) Homepage
    Texture mapping [].

    How about slocate []?

    Or rsync []?

    Oh and data muxing [].

  • by physicsboy500 (645835) on Monday March 19, 2007 @09:15AM (#18400511)


    1) the "inventor" will hold it strictly for bragging rights, or

    2) he will attempt to litigate and the patent will be found invalid and thus will be issued a trip to the shredder.

  • by Mr. Underbridge (666784) on Monday March 19, 2007 @09:16AM (#18400515)

    Serious question: How well would academia do?

    Well, they often do the basic research now, before selling the results to companies The problem is the very expensive development - the clinical trials, and all that. We'd be in the position of having colleges do all that, but it's really not what they're set up for. And of course the gov. would have to subsidize it.

    And look at it this way too - let's say we have the government spend $100M per drug developed (even if academics do it, the gov pays). Now companies come in and take the result and sell it on the cheap. Basically, what we've just said is "Hello, Merck, Phizer. Would you like the US government to take over your R&D? Oh, we'll do it for free." Seems like the US taxpayer gets screwed (at least, more directly than he is now). Also realize that since drugs are used internationally, we'd basically be doing free R&D for the entire world, where even rich European nations would be able to take our results - unless the patent-free zone applied domestically only.

    At the end of the day, it's a problem of game theory. Assuming all people do what's in their best interests (which doesn't always apply, but still), drug development will basically stop without patents, or under your case the US taxpayer ends up footing the bill for worldwide drug development, which we can't realistically do.

  • Let's keep this up (Score:3, Insightful)

    by dimeglio (456244) on Monday March 19, 2007 @09:20AM (#18400551)
    This is actually great and should server as a reminder to us all.

    We should continue to submit rediculous patents just to show how counter productive software patents in general actually are. Anyone still have their first year CS course notes? There should be plenty of material to patent!

    I don't mind they patent a hammer but not how it's actually used.
  • by SwiftOne (11497) on Monday March 19, 2007 @09:21AM (#18400559)
    I have yet to hear a convincing argument why Babbage's engine, which uses physical mechanical gears to implement an algorithm, is inherently more patentable than the same algorithm in software.

    First, when discussing patents (or copyright), everyone must agree that this is an artificial concept developed to try and achieve a purpose. The purpose in the U.S. is (arguably) to promote innovation. There's no natural or inherent quality of such concepts beyond an inconsistent and ill-defined sense of possessiveness.

    Second, with that in mind, if we look at your question, there are a few ways to approach it. "more patentable" could mean a few different things. I'll argue the discussion about "should be more patentable" i.e. I'll be arguing achieving the purpose, not the current letter of the law legality, of which I'm not fully clear (patents aren't copyright, and that's where the bulk of my limited legal knowledge is).

    When a device is patented, there are a few areas of benefit:

    1) The industry benefits, because the patent is (theoretically) detailed and recorded, meaning that the knowledge will not be lost, and that knowledge will eventually become public domain.

    2) The inventor benefits, because his/her device is recorded, and for a time, no one can use that device or claim credit for it without getting permission.

    3) Licensees benefit, because they can develop new inventions that improve upon or use or otherwise rely upon the patented device.

    4) Competitors benefit, because there is new idea introduced, and though they can't copy that implementation, they can try their own ways of achieving that idea. (knock-offs) In some cases, these prove to have some benefit over the original (a better method, cheaper production, etc)

    I would argue that #4 is why algorithms, business processes, and the like shouldn't be patented. Patenting Babbage's engine doesn't prevent the next guy from trying his luck at building a better mousetrap, so long as he doesn't actually copy Babbage. Patenting the algorithm (effectively the concept) does. Less competition means less benefit, and if I build a better mousetrap that doesn't rely on anything from your mousetrap, I'm not violating your work.

    That's a "should" argument from my personal views. It could well be that patents expressly try to protect ideas and concepts, though I suspect otherwise.

  • by darjen (879890) on Monday March 19, 2007 @09:22AM (#18400573)
    Can you show me why it is necessary for drug companies to invest this huge sum of money in order to ensure the survival of the human race? Or why we the taxpayers should be forced to subsidize the profits of big pharma via the government enforcement of intellectual property? Do you honestly propose to tell me that humans would cease to be interested in scientific development and research without these government enforced patents? Your case for patents are seriously not as slam dunk as you make it out to be.
  • Yeaaaaaaaa (Score:4, Insightful)

    by unity100 (970058) on Monday March 19, 2007 @09:23AM (#18400583) Homepage Journal
    its nice that drug companies each invested $100m and more drug research, got their patents, and they are now selling the drugs for reasonable prices to public and drugs are accessible anywhere in the world. not only that, but they are also making discounts and providing easy access, and even giving out drugs in most poor and needy countries so that things like aids or other dangerous diseases do not spread out.

    oh wait - none of these are valid in this universe - all these are happening in alternate universes.
  • by ady1 (873490) on Monday March 19, 2007 @09:28AM (#18400613)
    I agree. Patents ARE a good thing. However the current method/duration/prior art checking/etc of patents (especially of software patents) need to be reviewed and reformed.
  • Re:Prior Art? (Score:5, Insightful)

    by kripkenstein (913150) on Monday March 19, 2007 @09:45AM (#18400787) Homepage
    Well, if your read the patent, it's for triply-linked lists

    True. So it is just slightly less ridiculous than the headline makes it out to be. For crying out loud, I implemented various sorting methods on my linked lists by adding multiple pointers to them two decades ago as a teenager, and I don't believe for a second that I was doing anything remarkable at all. Once you have heard of linked lists then doubly-linked lists, triply-linked lists or whatever-linked lists are pretty much obvious.

    Anyhow, what is really missing in all of this discussion is a response from the patent submitter or the persons in charge of accepting the patent; we never get this on Slashdot nor the stories referred to. Since the patent appears to be so unbelievable, I am very curious as to what their official response would be. Perhaps some IT journalist can get one?
  • by Fnkmaster (89084) on Monday March 19, 2007 @09:45AM (#18400797)
    Finding compounds that are potentially active against some disease, especially compounds with relatively new mechanisms of action, is considered "basic research" - academia does a good job in this area, because it makes for good papers, PhD dissertations and academic plaudits.

    Taking those compounds and ensuring they are safe to administer in humans (rather than just animal models), and that they are as efficacious or more efficacious than other existing treatments is a costly, time-consuming process that requires managing a huge staff, coordinating clinics and hospitals, managing information systems, etc. This is not something universities or most research labs are set up to do properly.

    If you eliminated patents, you clearly wouldn't stop the scientists, but you'd put a huge damper on industry and financiers wanting to back the latter part of this process. This would result in far fewer drugs getting through the FDA approval process.

    It may be the case that there is a more societally efficient way to do this than the current system, but I'm not sure what it is. One problem with the current system is that one effect of it is that the US effectively subsidizes other countries drug availability, because drug companies expect to earn a large portion of their profits here, and have to deal with centrally negotiated pricing and other issues in foreign markets. But I don't see how you'd think that eliminating patents entirely would help the situation.
  • There are countries outside the US, with public healthcare, and in those countries enormous amounts of money are spend by the government on drugs. By eliminating patents, the Prices on drugs would be as low as 20% (happens already when after 20 years patent-lifespan competition kicks in). Also you should notice how little of the Budget is spend on R&D in the Pharma industry.
    That's an interesting theory -- but all that's really happening is that the time of expenditure is getting shifted. Instead of paying $100 at the pharmacy, you're paying $20 -- but you're still paying the other $80 in taxes. Government money doesn't come from the ether...
  • by LaminatorX (410794) <> on Monday March 19, 2007 @10:21AM (#18401117) Homepage
    The key difference is that Merk, Phizer, et al would all be able to sell the drug. There would be competition rather than monopoly rents in drug pricing. The money may need to come from taxes, but the people will get that back on the back end by paying less for drugs.

    Sure, the R&D bill needs to be paid. Right now, a ton of it is going into researching new lifestyle medicines that can be marketed via tv adds to affluent aging baby-boomers. That's where the big money is, not curing diseases. Academics are less inclined to pour $100M into researching a new arthritis medication simply because their old (though highly effective) one has gone out of patent.

  • by ericlondaits (32714) on Monday March 19, 2007 @10:29AM (#18401201) Homepage

    4) Competitors benefit, because there is new idea introduced, and though they can't copy that implementation, they can try their own ways of achieving that idea. (knock-offs) In some cases, these prove to have some benefit over the original (a better method, cheaper production, etc)

    I would argue that #4 is why algorithms, business processes, and the like shouldn't be patented. Patenting Babbage's engine doesn't prevent the next guy from trying his luck at building a better mousetrap, so long as he doesn't actually copy Babbage. Patenting the algorithm (effectively the concept) does. Less competition means less benefit, and if I build a better mousetrap that doesn't rely on anything from your mousetrap, I'm not violating your work.

    You have a good point. I would add a second situation that for me is the worst with algorithms:

    A patent shouldn't be granted if there's a good chance that someone will come across the same exact solution with no knowledge from the patent. By "good chance" I mean probability... in Information Theory terms this would mean that an algorithm should yield some amount of information before being patentable.

    IMHO the n-linked lists don't meet the "amount of information" quota because it's very likely someone comes across this solution on his own when faced with certain types of problems. The same way that many people with no knowledge on sorting come across their own versions of bubble sort... or the same way you can "build" (i.e. emerge) quicksort out of some sorting theory.
  • by UbuntuDupe (970646) * on Monday March 19, 2007 @11:05AM (#18401561) Journal
    Good post. I think, in a similar way, this is why patents should only apply to a *means* and not to and end. That is, you should be able to patent *how* a problem is solved, but not *that* a problem is solved, so you can allow people to explore other ways to solve it. Case in point: the one-click patent. Patents *shouldn't* prevent others from figuring out how to streamline online purchases to one click, and so that end (being able to buy with one click) shouldn't be patentable.
  • 1970 (Score:2, Insightful)

    by Tablizer (95088) on Monday March 19, 2007 @11:18AM (#18401717) Homepage Journal
    I sure the hell am glad that patenting software wasn't in vogue when Dr. Codd published relational theory. Or even for that matter file systems, GUI's, ASCII, keyboards, mice, you name it. Even command prompts.
  • by bokmann (323771) on Monday March 19, 2007 @11:40AM (#18401949) Homepage
    I think the poster's original point is that it is not enough that there is prior art - these things shouldn't get to the point where prior art defense is necessary. We know the system is broken because a patent like this should never have been granted, while someone who is part of the system could say, "you see? the system worked! People Identified prior art and shot down the patent".

    Prior art is a defense if they try to enforce the patent on you. They never should have been given the ability to enforce the patent in the first place.

    Just to be clear, for people who might read this and have no idea what all this linked-list business is about, this ia a data structure that is taught in every 200-level com sci "algorithms and data structures" class, and is so ubituitous that it would certainly be on any exam based on that material. Put in terms in another domain, this would be like patenting "the use of horse hair for the application of water, oil, or acrylic-based substances in an effort to produce a visually aesthetic experience" - that is, a paint brush. Linked lists are in the basic toolset that software engineers use every day. If you are reading this post electronically, then there are probably hundreds of them swirling around inside your computers memory at this very second.

  • by Anonymous Coward on Monday March 19, 2007 @12:06PM (#18402295)
    This is a perfect example for anyone isn't interested in government, particularly in voting. The reasoning seems to be that government isn't interesting because it doesn't directly effect you. Yet, it clearly does effect all of us in the tech. community as this example clearly shows.

    What this is, is corporatism. Dwight Eisenhower warned of this when he warned of the rise of the "military industrial complex." Folks, this is it.

    There is no reason for the current sorry state of IP in the USA, other than this is what the corporations want. They bought seats in congress, and grateful representatives (I use that in the loosest possible way, because it's the corporations who bought the seat that is being represented, not the voters) enacted the laws that the corporations wanted.

    That's how we got software patents. The whole concept of software patents goes against the patent system. The idea was to patent real, physical things -- products and machines. Until software patents, you couldn't patent ideas. The reason behind patents is to encourage R&D of new and innovative products - to give the inventor improved prospects of being able to recover the R&D costs, which in turn encourages further R&D. This was when developing a new widget could take years of work. Not the few hours that developing a triply linked list did -- it only took me a couple of days to develop my six pointer linked list to compete with a b-tree (hey, it got me out of the exam so don't knock it).

    If you think this patent is a scam, you are right. It's a scam that we not only allowed, but encouraged. Because we, as a group, aren't really engaged in the political scene. Because we seem to think that it doesn't matter, when clearly it does matter a great deal.
  • Re:Prior Art? (Score:2, Insightful)

    by mindwhip (894744) on Monday March 19, 2007 @01:00PM (#18402975)
    I'm going to re-patent this but when used 'over the internet'.
  • Re:Prior Art? (Score:3, Insightful)

    by Russ Nelson (33911) <> on Monday March 19, 2007 @01:51PM (#18403615) Homepage
    Everything is patentable because nothing is obvious.
  • by jamesshuang (598784) on Monday March 19, 2007 @02:00PM (#18403731) Homepage
    Except Merck and Pfizer would not EXIST if it weren't for the patents. Have you heard of Andrx or Ivax? They are generic drug companies. They do exactly what you say should happen - they sell drugs that are out of patent, and they have equal access over any (old) compounds. They do little or no research of their own, because they don't have the money to do so.

    The actual COST of a pill is almost nothing - no more than the cost of generic acetaminophen in your local grocery store. Any organic chem graduate could take almost any of the major drugs on the market and design a workable and mostly efficient synthesis method. Any chemical engineering graduate could probably take one of these methods and upscale it to million-pill quantities. Ensuring that these drugs are safe is where most of the cost is.
  • by curunir (98273) * on Monday March 19, 2007 @06:57PM (#18407569) Homepage Journal
    The problem isn't with software patents per se, it's that the PTO doesn't have the expertise necessary to understand what is and isn't novel in the software field. There's no doubt in my mind that there are software patents that deserve patent protection. Off the top of my head, I'd say MP3, JPEG, MD5, DES(ede) would all be examples of things that should be patentable (though I believe only MP3 and parts of JPEG are patented). All four of those are non-obvious algorithms for accomplishing a certain task and all four have competing algorithms to accomplish the same task.

    The problem is that in software its too easy to confuse a method and a concept. Even experienced developers will sometimes have problems. Where the PTO understands that patents on physical objects represent only the means of accomplishing the task and not accomplishing the task by any means, they haven't figured it out when it comes to software. Too many patents are granted for accomplishing a task rather than accomplishing a task using a given algorithm.

    This doesn't mean that we should scrap the patent system entirely (for software, at least). What it means is that we need to push for education and reforms that reduce the abuse that we're currently seeing. For one, patent examiners need to be better educated, perhaps to the point where no examiner is not a specialist in the field of the patent. There are a ton of other things that would help too, but that's beyond the scope of this post.

A Fortran compiler is the hobgoblin of little minis.