Slashdot Log In
Linked List Patented in 2006
Posted by
Hemos
on Mon Mar 19, 2007 07:11 AM
from the good-thing-that's-protected-now-as-well dept.
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.
The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.
Full
Abbreviated
Hidden
Loading... please wait.
Prior Art? (Score:5, Funny)
Re:Prior Art? (Score:4, Funny)
Parent
Re:Prior Art? (Score:4, Funny)
Parent
Re:Prior Art? (Score:5, Insightful)
Parent
Re:Prior Art? (Score:4, Informative)
I'm not going to take the time to read the patent itself, but just an FYI on your comment, multi-list cells can be considered triply-linked lists. Useful for replacing sparsely populated two-dimensional arrays. Or skip lists, which are rather nifty, though I've never had a real-world application for them beyond job-interview brainteasers.
Hrm, I wonder if there's anything else patentable in my old Data Structures and Algorithms class notes...
Parent
Re:Prior Art? (Score:5, Insightful)
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?
Parent
Re:Prior Art? (Score:4, Funny)
Parent
make cast? (Score:5, Funny)
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.
Parent
Re:Prior Art? (Score:5, Funny)
Parent
Re:Prior Art? (Score:5, Funny)
I think you misunderstood. To make the links, you take about 5-6 inches of reel-to-reel tape, wrap it around to form a loop, and then seal it with a bit of sticky tape. Then you take the next piece of reel-to-reel, and loop it through the first before sealing it, thus forming the link. The prior art the GPP mentioned is found in every school for five-year-olds in the country, around 15 December every year, and has been since long before your new-fangled punch cards were invented! :-)
Parent
wow. (Score:4, Funny)
This is a good thing? (Score:5, Insightful)
Re:This is a good thing? (Score:5, Funny)
Parent
Re:This is a good thing? (Score:4, Insightful)
Parent
Re:This is a good thing? (Score:5, Insightful)
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.
Parent
Re:Software vs hardware? (Score:5, Insightful)
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.
Parent
Re:Software vs hardware? (Score:4, Informative)
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.
Parent
Re:Software vs hardware? (Score:4, Insightful)
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.
Parent
Re:Software vs hardware? (Score:4, Insightful)
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.
Parent
Yeaaaaaaaa (Score:4, Insightful)
oh wait - none of these are valid in this universe - all these are happening in alternate universes.
Parent
Re:Software vs hardware? (Score:4, Interesting)
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.
Parent
Re:Software vs hardware? (Score:5, Interesting)
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.
Parent
Re:Software vs hardware? (Score:5, Insightful)
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.
Parent
Re:Software vs hardware? (Score:4, Insightful)
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.
Parent
Re:This is a good thing? (Score:4, Funny)
Parent
Re:This is a good thing? (Score:4, Funny)
The next time you're in the USA, dude, pay up.....
I own the patent: Process and/or Method of NOT Living in the United States
Parent
Doesn't patent insertion and deletion (Score:5, Funny)
Re:Doesn't patent insertion and deletion (Score:4, Funny)
1 : something that is inserted : as a : the part of a muscle that inserts b : the mode or place of attachment of an organ or part c : embroidery or needlework inserted as ornament between two pieces of fabric d : a section of genetic material that is inserted into an existing gene sequence
2 a : the act or process of inserting b : the mutational process producing a genetic insertion
Parent
Seperate software patent office (Score:4, Interesting)
If you must have software patents, why not a specialist software patent office to deal with them?
Patent is on multiply-linked lists (Score:5, Informative)
Previous Slashdot discussion of this patent (Score:5, Insightful)
Parent
Re:Previous Slashdot discussion of this patent (Score:5, Funny)
Parent
Re:Patent is on multiply-linked lists (Score:5, Interesting)
Back in lat 70s when I was a junior programmer, I did some hacking in SNOBOL to produce a list of thinkgs that had to be sorted two different ways. I had nodes that were in two separate list at the same time. Had I known I would have patented it (unfortunately I lost the card deck with the source).
Parent
Re:Patent is on multiply-linked lists (Score:5, Informative)
That's simply not true. Patent claims are frequently built upon prior claims in the same patent; if a later claim is built on an earlier claim (e.g. in this case where claim 2 cites claim 1) then you need to infringe both parts in order to fall fowl of the later claim. That said, infringing a stand-alone claim (like claim 1 here) is sufficient in itself.
As far as I can tell claim 1 really does hit a standard doubly-linked list; you have the plurality of data items, a primary order of traversal and an auxiliary order (e.g. reverse traversal). There is obvious prior art for this and the claim should be invalid. Claim 2 is therefor also invalid, irrespective of it's novelty, since it cites an invalid claim. Claims 3 and 4 also have obvious prior art.
Personally I think that patents like this are great, since they add substantial support to the argument that the USPTO are, despite their avowed best efforts, incapable of assessing the novelty of software patents, and that they should stop trying.
Parent
Thanks go to John Breene and Cheryl Lewis (Score:4, Interesting)
Do they get a bonus at the end of the week, for the number of patents they have past.
Re:Thanks go to John Breene and Cheryl Lewis (Score:5, Informative)
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.
Parent
Re:Thanks go to John Breene and Cheryl Lewis (Score:4, Interesting)
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.
Parent
Oh yeah (Score:5, Funny)
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.
Aww Shoot... (Score:5, Funny)
Two things... (Score:5, Informative)
Hindsight Bias + EU Criminal infringement (Score:4, Informative)
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.
Other patents from this examiner (Score:5, Insightful)
How about slocate [google.com]?
Or rsync [google.com]?
Oh and data muxing [google.com].
Fantastic!
Conspiracy (Score:4, Interesting)
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 Patent Examiner (Score:5, Funny)
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.
Re:oh dear (Score:5, Funny)
*smack*
Go back to Algorithms and Data Structures, Do not pass go, Do no increment the Counter by 200
Parent
Re:oh dear (Score:5, Funny)
You cannot dereference the pointer; that's impossible. You must first realize that there is no pointer, and that you're only dereferencing yourself.
Parent
Re:oh dear (Score:4, Funny)
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."
Parent
Re:To be fair, he invented a doubly linked list (Score:5, Informative)
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
Parent
Re:It is not a patent (Score:4, Informative)
linky [uspto.gov]
Parent
Re:35 U.S.C. 101 and Reexamination Procedures (Score:5, Informative)
In submitting your pre-September 26, 2002 "prior art," you should also make sure that the "prior art" is at least "prior art" under 35 U.S.C. Section 102(b) [uspto.gov]. For the unfamiliar, this is "102(b)" prior art. "Prior art" that falls under the rubric of 35 U.S.C. Section 102(b) generally cannot be challenged by the Applicant of the application for patent. For example, with "102(a)" prior art, the Applicant for patent can "swear behind" the prior art to show that the the Applicant's "date of invention" is before the "prior art's" earliest effective date.
As an example, I note that the filing date of application is September 26, 2002. In this example, if you were to submit "102(a)" prior art with an earliest effective date of September 27, 2001, the Applicant of the patent may be able to demonstrate that he/she was working on the invention as of September 20, 2001, hence, overcoming the application of this art (there are some legal concerns regarding what constitutes "working on," but I'll save that discussion for a later time). Now, suppose you submit "prior art" with an earliest effective date of September 25, 2001. This is "102(b) prior art" because it's earliest effective date is at least one year prior to the earliest effective filing date of the application (there are some issues when the application claims priority to an earlier filed application, but this is not the case). In this scenario, where the "prior art" applied is "102(b) prior art," the Applicant cannot swear behind the applied "prior art," even if the Applicant was working on the invention before the earliest effective date of the "102(b) prior art."
That being said, you should also consider whether your "102(b) prior art" discloses each and every limitation of all of the claims, not simply the independent claims (in this case claims 1, 3 and 4.) (For a discussion of "what is a limitation," see the various sub-sections of Section 608.01 [uspto.gov] of the MPEP. However, I will note that you can combine references under 35 U.S.C. 103 [uspto.gov], but again, that's a discussion for another topic.
So, to recap:
1) Make sure that your reference is before the earliest, effective filing date of the application for patent (i.e. that it is "prior art");
2) Make sure that your "prior art" is "102(b) prior art"; and,
3) Make sure that each and every limitation of each and every claim is disclosed in the application.
These views represent my own and are in no way associated with any government organization or private entity.
Parent