US PTO, Again
Well, I was really hoping to be able to leave the US Patent & Trademark Office (US PTO) alone for a while. In retrospect, I guess I have. It may seem like only yesterday that I penned PTO Has Got To Go, but it was more than six months back. Amazingly enough, things have gotten, if anything, even stupider [sic] than they were then!

It appears that on 11 April 2006, the US PTO, in its infinite (?!) wisdom, issued US Patent number 7,028,023 to one Ming-Jen Wang, who thereupon assigned it to LSI Logic Corporation. The law firm of Cochran Freund & Young LLP entered US Patent application number 10,260,471 on 26 September 2002 to kick the process for this Patent. John Breene provided primary examination and Cheryl Lewis acted as Mr. Breene's assistant in the examination.

This application describes a technique of adding extra pointers to the records stored in a linked list, so that the list might be traversed in any of several different orders. It's a good idea. One that hundreds of software developers have had over the last forty or fifty years. One so well known that it's an integral part of dozens of equally well known algorithms, including several variants of the B-Tree data structure.

In fact, it's so well know that it's described in exquisite detail in Donald Knuth's seminal The Art of Computer Programming series of volumes, first published in the 1970's or before. These volumes represent probably the seminal work in practical computer science.

However, it's obvious that no copies of them reside within any reasonable distance of US Patent Examiner Mr. John Breen, or Assistant Cheryl Lewis. Notwithstanding the fact that they're tasked with examining patent applications for software entities, they obviously have only a passing acquaintance with the most basic parts of the written and oral histories of software development.

The law firm of Cochran Freund & Young LLP entered the application for this patent, as noted above. Their web site describes them as “hav[ing] educational degrees and experience in engineering, electronics, chemistry, biochemistry, physics, computer hardware and software, and mechanics”. It further indicates that they provide “world class intellectual property services”. They, also, apparently remain blissfully unaware of the existence of Donald Knuth and his tomes.

The Patent Storm records refer to SEVEN previous patents:

• 5,263,160: Issued 16 November 1993: Augmented doubly-linked list search and management method … [references 5,043,885]: This is your basic, run of the mill linked list, with a couple of trivial performance optimizations.
• 5,446,889: Issued 29 August 1995: Computer-based methods for determining the head of a linked list. Oh my God! This is nothing more than walking backwards through a list until you hit the head node!
• 5,644,784: Issued 1 July 1997: Linear list based DMA control structure. Johnny implements a linked list in silicon!
• 5,671,406: Issued 23 September, 1997: Data structure enhancements for in-place sorting of a singly-linked list. A pretty basic implementation of singly-linked list insertion and removal, wrapped in a pretty simplistic insertion sort. Which is a pretty damned piss poor sort method anyway, being O(n²). That means that if you double the size of the list, the time it takes to sort quadruples. Any decent algorithm, that a pro would actually use in their production code, ought to be able to manage O( n log( n ) ).
• 5,893,162: Issued 6 April 1999: Method and apparatus for allocation and management of shared memory with data in memory as multiple linked lists. Only six days late. That's pretty damned for a federal bureaucracy. Johnny implements a linked list in silicon, reprise.
• 5,905,990: Issued 18 May 1999: File system viewpath mechanism. Johnny uses linked lists to implement a file system. Good lord, how many file systems have there been that didn't use linked lists at some point?
• 5,950,191: Issued 7 September 1999: Method and system for assigning an item in a linked list using an auxiliary array. The actual predecssor to the misbegotten patent we started with. This is a linked list with a single set of parallel index values, so you can only have one alternate order, rather than several.

The bottom line is that over at least the last fifteen years or so, the US PTO has issued quite a wad of patents on a data structure that is so ingrained into most Comp Sci grads, and most of the rest of the programmer corps, that they don't even need their brain to write the code. They've written it so many times that their hands and spine can spew out the code without intervention by their brains. They don't have to anymore, though, because damned near every programmer's support library, including the standard libraries for most of the major (and minor) languages include them natively.

These patents effictively ban every commercial program offered for sale or developed and used internally, anywhere in the US, by anyone, at any time, for any purpose. All for using one of the most basic constructions, one of the most pervasive idioms, in the programming community.

Links

• US Patent 7,028,023
• US Patent 7,028,023
• Patent Storm
• Linked List Patented in 2006
• Cochran Freund & Young LLP
• United States Patent and Trademark Office