Slashdot Mirror
LSI Patents the Doubly-Linked List
An anonymous reader writes "Back in April, LSI was granted patent number 7028023. This is a patent on a stunning new technique in data structures ... the concept that a linked list can in fact have multiple orderings. Of course, this has been used since the beginning of (computer) time in the form of doubly-linked lists. Even if LSI wants to (somehow) claim that the doubly-linked list doesn't count as prior art, maintaining linked lists of graphical objects sorted by both x and y co-ordinates for collision detection has been done since "graphical objects" meant ASCII characters on a green-on-black screen, and has probably been widespread in databases for probably even longer."
A double linked list implies reverse pointers allowing forward and backward traversal of a list. The patent in question is more broad than that. It is talking about multiple links allowing different orderings at the same time for the same elements. So you could have a list of, say, files with links giving alphabetical order, and links giving size order, and thirdly links giving file types without having to resort the list. You might use this in a file-list screen.
The patent is still absurd, but the summary is (as usual) inaccurate.
Sometimes it's best to just let stupid people be stupid.
This very same examiner (John Breene) has also granted patents #6944634 (file caching) and #6745181 (query based search).
..holy sh*t, this is incredible (Well, sadly not). For convenience, here's the PTO's version of the patent, better to use because it has links to some of the cited prior art patents. Additionally, consider looking at the prosecution of the application. You can download a pdf of the "image file wrapper" which includes the examiner's action and applicant's response.
..." Now Porter goes on to add an auxiliary array of
pointers (but for a more refined use than just an index) but the basic
concept of a doubly linked list is here. Even the examiner very briefly
acknowledged in passing that Porter showed a doubly linked list, but
obviously failed to recognize that this fully meets claim 1 (including
the redrafted version); she obviously did not understand what the
applicant was showing. If there are any doubts about what arrangement
of data are being disclosed and claimed here then just look a Figure
one in the drawings (You have to use the "Images" link at the top which
will take you to a clumsy page that displays the sheets of the actual
patent specification using some specific tiff format, so your browser
must be capable of displaying these images).
There was a nominal rejection under 35 USC 101 as covering non-statutory subject matter, which applicant easily overcame by typical claim redrafting used in software patents. There was also a rejection under 35 USC 102 as being anticipated by the patent to Schwartz. The latter patent discloses a singly linked list and an separate array of pointers to individual items (kind of like an index?). Clearly, this is not the same as the doubly linked list of the application, and the applicant responded by pointing this out. The application was then allowed and issued.
What was clearly missed here was the patent to Porter which discloses a "...doubly-linked list search and management method
I'm sure there are lots of other prior art showing this plus the use of more than two lists (like Fig. 3). In any event I can't see claim 1 surviving even a cursory challenge. Anyone have $ 2,520.00 free to file a reexamination request?