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."
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!
What he actually invented was a linked list with two or three pointers, an therefore sort orders, in the same list. Doubly linked lists demonstrate his concept, though are more complicated (since they allow backwards traversals of the same list) and useful.
Robert Endre Tarjan, Data Structures and Network Algorithms, SIAM, 1983:
Endogenous structures are more space-efficient than exogenous ones, but they require that a given element be in only one *** or a fixed number of structures *** at a time.
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."
You can click on an examiner to see what patents he/she has examined.
Try that on these guys, i think i can yell "prior art" on almost all of these "inventions".
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.
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
Prior art for this story.
What you are saying is simply wrong! You can infrige on every claim, not only on 'leaf nodes'. However, what have to be taken into account is that dependant claims inherit all features of their parent claims. Dependant claims are therefore narrower, and harder to infrige, claims higher up on the hierarchy are broader, therfore easier to infrige but also easier to be invalidated by prior art.
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.
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...
Skip lists have more than one forward pointer in each node, and are an extremely well-known data structure. Wikipedia says they were invented (Wikipedia's word is "discovered", which seems inaccurate to me) by William Pugh in 1990 and published then.
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.
Normally I'm a bit skeptical when Slashdot interprets these patents, and s per usual, the summary does so. The patent does not cover doubly linked lists. It covers a generalisation of the idea that may or may not include doubly linked lists. Inthis patent, the list can be transferred in a number of predefined sequences. Doubly linked lists typically only allow traversal forwards and backwards.
But, this is a well known data type, known as a multiply linked list. A couple of minutes with google code search gave me an example in the form of the "engine" structure in GIST, which can be traversed in order of Active Engines.
Oh, and also - Dupe!
Most of the open patent examiner positions are low wage with no degree required. http://jobsearch.usajobs.opm.gov/jobsearch.asp?re= 9&vw=b&pg=1&jbf571=13&fn=4537&FedEmp=N&jbf574=CM56 &brd=3876&ss=0&FedPub=Y&caller=%2Fa9pto.asp
Indeed, and you can get even more general with implementing a general graph with adjacency lists, of which your example and the patent are special cases. Prior art indeed!
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'?
http://www.safarix.com/0131409093/ch11lev1sec5
The claims would seem to cover something like a skiplist.
Although in application and detail, I cannot see ever using this, as multiple orderings of a list sound painful and expensive to update and maintain. I suspect this is spaghetti code in the form of a patent, as I can construct the example out of three lists, and the additional headache would only be worth it if the reduction of half the total space used (approximately) would be significant (this is based on the assumption that the list items are pointers to the real objects elsewhere.) It should also be noted that that is just a reduction in the list size which does not include data (which I would expect to be far larger). It also would reduce the constant factors in item deletion (delete and (while increasing them for item creation), both netting zero change. I suppose it would allow for some features such as dynamic ordering changes (changing sequence while reading back the list (abcde read as abcba or something)).
I have to say that I feel a great deal of sympathy for the examiner who was responsible for dealing with this patent, as it was horrible (the horror...)
If people can connect to one another even the smallest of voices will grow loud.
--Serial Experiments Lain
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.
We use skip lists in our software. Like b-trees, they're more useful in persistent situations where getting data in blocks is an important consideration than in memory-only applications.
The patent may claim triply-linked lists (see claim 2), but it also makes a claim on doubly linked lists.
The real "Libtards" are the Libertarians!
A slashdotter who didn't build his own computer is like a Jedi who didn't build his own lightsaber.
It's really unfair to suggest that the patent examiner responsible for allowing this patent should respond to criticisms given that the examiner's reasoning is already publicly available. Just go to the USPTO Patent Application Information Retrieval system and search for patent number 7028023. You can see what the patent examiner reviewed, what was argued, what the response was, etc.
After reading through these documents, then it is fair to argue that there was a better approach to analyzing the patent application. For example, the examiner relied heavily on the argument that this patent anticipated the claimed invention when rejecting the claims. This patent was not closely related to the claimed invention (it involves a linked list paired with an array pointing into various places in the list). A sorted double-linked list may very well have formed a better basis for an argument because it is at least more closely related. Also, the examiner did not make any obviousness claim. Perhaps it was too difficult to find some teaching or suggestion that would have made the claimed invention obvious in light of the prior art, but perhaps the examiner would have been able to find something had the examiner spent less time writing out an argument that the claimed invention was not patentable art (not because of obviousness or novelty, but because of subject matter).