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

Comments

Patent is on multiply-linked lists

[Paul Crowley]

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

Re:Patent is on multiply-linked lists

[nickovs]

... if your solution doesn't infringe leaf nodes in the tree of claims, it doesn't infringe.

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.

Re:To be fair, he invented a doubly linked list

[tomstdenis]

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

Two things...

[thebdj]

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.

Hindsight Bias + EU Criminal infringement

[Anonymous Coward]

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

Here in the EU, JURI is trying to criminalize all IP infringements again:
http://press.ffii.org/Press_releases/Criminal_Sanc tions_Rapporteur_fails_to_protect_European_industr y

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.

Where and How to Complain

[22_9_3_11_25]

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

Re:Software vs hardware?

[Fordiman]

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

Re:Thanks go to John Breene and Cheryl Lewis

[larryboymi]

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.

Re:Prior Art?

[ReverendHoss]

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

Re:Prior Art

[SethHoyt]

I've got a better one. Check out "C++: An Introduction to Data Structures" by Larry Nyhoff, copyright 1999.

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.

Re:It is not a patent

[TrappedByMyself]

It is a patent. The submitter is just dumb.

linky

35 U.S.C. 101 and Reexamination Procedures

[blckbllr]

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.

Re:35 U.S.C. 101 and Reexamination Procedures

[blckbllr]

One last follow-up that I realized I forgot to discuss:

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). 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 of the MPEP. However, I will note that you can combine references under 35 U.S.C. 103, 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.