Slashdot Mirror
Linked List Patented in 2006
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."
I would show the prior art, but I can't read the reel-to-reel tapes.
"No matter where you go, there you are." -- Buckaroo Banzai
what a genius. he deserves millions over millions for that. and chicks for free.
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.
I read the claims... somebody submit a patent for insertion and deletion operations.
The US patent office has proved its incompetence in this area time and time again.
If you must have software patents, why not a specialist software patent office to deal with them?
If you RTFP, what's actually being patented is the idea of using multiple pointers so that the same item can be in more than one linked list at a time. This idea is also a long way from being novel, but it's slightly different from patenting the linked list. Arguably a doubly-linked list is prior art...
Xenu loves you!
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.
tasks(723) drafts(105) languages(484) examples(29106)
thats not a reference, thats a pointer!!
;)
*smack*
Go back to Algorithms and Data Structures, Do not pass go, Do no increment the Counter by 200
$_="Slashdotter";$syn="OTT";s;..;;;sub _{print shift||$_};s!ash!Perl !;s=$syn=ack=i;tr+LLEd+BLAH+;_"Just Another ";_
These, were the examiners. I wonder what it takes to be an examiner, surely you must have a little knowledge in that particular area?
Do they get a bonus at the end of the week, for the number of patents they have past.
I read about this technique about 23 years ago. What is going on here? This looks like material for a slashdot poll, viz:-
Why do you think that the latest LSI is bogus?
What about it, guys?
--E.
I've got so much code modifying to do.
You know, there is a difference between trolling and pointing out the flaws in your reasoning. Just saying.
How exactly is backwards traversal more complicated than multiple sort orders? Backwards is just another sort order.
617B3B7F7E7C7D7F00EOF
To be fair ... the first patent that the examiner cited is PRIOR ART (I'd argue it too is invalid) for this patent.
What's worse? LibTomCrypt uses quad-lists (prev/next, parent/child) so it seems that I violate this patent. Gotta go cut a cheque to LSI.
Tom
Someday, I'll have a real sig.
The patent # is actually 7028023. The summary quoted number is the application number. Also, this is OLD, issued almost a full year ago. I actually think we had an argument about this long before now. I am starting to wonder if some of these anonymous submissions for these are actually coming from examiners with a clue. (Trust me there are some.) And look, I found it.
"Some days you just can't get rid of a bomb."
The same patent was mentioned in this Slashdot article. What is new since then?
You are all suffering from hindsight bias, you all think you've used linked and double links and n-linked lists before but in reality you were using vectors and this is a genuine innovation. ;)
c tions_Rapporteur_fails_to_protect_European_industr y
Here in the EU, JURI is trying to criminalize all IP infringements again:
http://press.ffii.org/Press_releases/Criminal_San
The vote is expected 20th March (tomorrow) with the aim of making minor copyright, trademark and patent infringement into a criminal offense. There is no fair use in Europe either.
This has little to do with the real world, EU has no jurisdiction in European criminal law, but if it can make a trade issue into a criminal law issue it can expand EU control in that direction. So JURI has cooked up this trick whereby IP rights are claimed as a trade issue and pumped it up to claim infringement needs criminal prosecutions.
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.
You've still got it wrong. It's an abstracted class.
You cannot dereference the pointer; that's impossible. You must first realize that there is no pointer, and that you're only dereferencing yourself.
110100 1101000 1101000 1100110 0 1101111 1101000 1100011 1
http://www.uspto.gov/web/offices/com/iip/complaint s.htm
Complaints should be mailed to the following address:
Mail Stop 24
Director of the U.S. Patent and Trademark Office
P.O. Box 1450
Alexandria, VA 22313-1450
"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. How about if I use an FPGA instead? Is it patentable then?"
Easy: Babbage had to design the gears, switches, etc, and the arrangement thereof to get the effect of calculation. That's patentable. The algorithm he intended to use it to accomplish is not; it's just an artifact of math, and subject to the natural laws clause.
If you used an FPGA, you could patent the arrangement of gate-feilds, possibly, but the algorithm you're trying to achieve would (should) still not be patentable.
110100 1101000 1101000 1100110 0 1101111 1101000 1100011 1
Texture mapping.
How about slocate?
Or rsync?
Oh and data muxing.
Fantastic!
Someday, I'll have a real sig.
I think this is a global conspiracy to undermine the patent system by submitting totally invalid patents. Once it's found they're unenforcable they'll kill off the patent system that is broken. Yay for that. Congratulations to that law firm and whatever!?
:) concept. But AmigaOS gave you a linked list for nearly everything, stored all it's windows and objects and tasks in them, and expected you to traverse it with exec.library and utility.library.
Actually I'm curious, when was your first experience of a linked list implemented in a highly exposed manner? As far as I recall it was in AmigaOS (but then I am only just young enough to remember that as my first OS and the first OS I cared coding for). A lot of systems do use linked lists, it's a very old (1960's?
Along with tags (tagitems, taglists) and ReadArgs they're things I miss in modern operating systems which seem too 'hidden' and trying to feel too unixy. It's all pipes and sockets and syscalls, blagghhh.. I'm glad QNX puts message passing right in your face, and DragonFly is bringing it all back to me again. I can't wait until someone patents one of those again!
The site displaying the patent must use linked lists somewhere in the code. The menu at the top says "Browse by Inventor", "Browse by Date" etc...
Presumably the patent site existed before the patent was submitted.
America, Home of the Brave.
I was an examiner for awhile. Got out after 9 months because I saw the path. A lot of $, but a lot of OCD people, and stress due to quotas.
I had a B.S. in C.S. and I was simply working on GUI patent apps. They wouldn't hire someone with a degree in an outside area (like Business or something) to do C.S. work, although there were a lot of EE's doing C.S. work (although I see that in the commercial realm a lot too, not always to great success, but sometimes).
Wouldn't recommend it for anyone other than an anti-social who wants to make bank and doesn't mind a boring, high-stress job.
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.
Views expressed do not necessarily reflect those of the author.
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.
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.
Read radical news here
'' 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. ''
In German law, this would be very simple: You would sue your competitor for "unfair competition". That was for example the way to handle software pirates in the years before it was established that you could have copyright on software. Worked quite well. It is still used to protect phonebooks on CD, or maps, which are not the kind of material that can be protected by copyright: Copying phonebooks and selling the copies is "unfair competition" unless you hired a bunch of people who typed the material in themselves, using a scanner and OCR software to read them or just copying someone else's CDs is "unfair competition" and therefore illegal.
Under section 9.5 (Other Multiply-Linked Lists), there is a description of "Multiply-Ordered Lists" which is identical to what is in the patent.
An excerpt from the text:
"In some applications however, it is necessary to maintain a collection ordered in two or more different ways... One way to accomplish such multiple orderings is to maintain separate ordered linked lists, one for each of the desired orders... A better approach is to use a single list in which multiple links are used to link the nodes together in the different orders."
The same section of a newer edition is available for viewing online here.
Now the more likely scenario is that the drug companies are mainly working on chemical solutions to psychological conditions like depression which were often previously treated with counselling. Those 100 million dollar drugs aren't curing anything, they're alleviating symptoms marginally better than the previous patent-protected drug did.
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.
make cast? I've done make, make install, make clean, make menuconfig, make xconfig, make modules make modules install, but I've never done make cast...
But obviously I've never compiled anything with a linked list in it anyhow, since this dude just barely invented them.
My regime would require this for patents that are blatantly obvious or have as much published prior art as linked lists do. You can be there'd be a lot fewer frivolous patents issued if the examiner and the applicant were forced to eat the printouts if the patent turned out to be retarded.
I'm trying to teach myself to set people on fire with my mind... Is it hot in here?
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.
It is a patent. The submitter is just dumb.
linky
Help me take back Slashdot. When did 'News for Nerds' become 'FUD and Conspiracy Theories for Extremist Nutjobs'?
I had a friend who was an EE and worked for the USPTO for a while. They were very aggressive in recruiting her, but after six months she was desperate to get out.
As a few nearby posts have said, they are apparently desperate for bodies. They seem to be in a chicken-and-egg situation - while they are understaffed, the reputation for stress and being underpaid makes it hard for them to hire/retain examiners. Inability to hire/retain examiners results in the existing examiners being overstressed.
Sadly, for a LONG time, the USPTO was one of the government's biggest moneymakers but was also one of the most underfunded, as all of their income went to what was basically a "generic" fund allocation pool. I've heard efforts are being made to rectify this (i.e. let the USPTO use the majority of what they bring in rather than sending it elsewhere), which should help make things a bit saner.
retrorocket.o not found, launch anyway?
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.
As a Slashdot discussion grows longer, the probability of an analogy involving cars approaches one.
Reminds me of...
C: You shoot yourself in the foot.
C++: You accidently create a dozen instances of yourself and shoot them all in the foot. Providing emergency medical assistance is impossible since you can't tell which are bitwise copies and which are just pointing at others and saying "That's me, over there."
Oolite: Elite-like game. For Mac, Linux and Windows
I'll make a couple of quick comments:
First, claim 1 may be invalid under 35 U.S.C. 101 as claiming unpatentable subject matter. It has been my experience that a 35 U.S.C. 101 rejection will issue against a "software patent" where the claim is not directed to something that produces a "useful, tangible, and concrete" result (see, State Street Bank v. Signature). More often, this type of rejection will issue against a claim (not an application), where the claim is directed to purely mathematical operations with no tie-in to hardware to perform that operation. In reading claim 1, there appears to be no claimed hardware that performs the algorithm recited, and hence, I would argue that the claim is invalid. For a more thorough discussion of patentable subject-matter, please see Section 2106.1 of the Manual of Patent Examination and Procedure. However, without looking at the image file wrapper, I don't know what rejections were applied to this application to determine whether claim 1 was amended to overcome this specific rejection.
Now, that being said, if you are concerned about invalidating this patent (which I'll note issued in April 2006, almost one year ago), you should first find "prior art" before the earliest filing date of the application. In this case, that date appears to be September 26, 2002. I say "appears to be" because the application does not claim priority to an earlier filed foreign application or U.S. provisional application. Next, after gathering your pre-September 26, 2002, you should follow the re-examination procedures for submission. See Section 2200 of the MPEP. Keep in mind, that when a third-party submits prior art for a re-examination proceeding, the prior art should present a new question of patentability. After submission of the "prior art," that third-party is generally not allowed to make comments during the re-examination proceeding. Hence, if the USPTO finds that the "prior art" does not present a new question of patentability, you may have inadvertently made the patent "stronger" and less likely to be invalidated during litigation. Accordingly, you should consider whether infringing this patent may be better procedure, and thus filing a motion that the patent is, in fact, invalid.
This views represent my own and are in no way affiliated with any government organization or private entity.