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."
While one could at least make a somewhat intelligent argument why software that costed companies like Apple or Microsoft Millions (or even Billions) of dollars to create should be patented, there's no logical argument for patenting data structures. This patent was first submitted in 2002, which probably means it was turned down and appealed at least twice. As anyone who has gone through the patent process knows, if you appeal enough times eventually you might find an examiner who is clueless enough to grant the patent.
I couldn't imagine LSI ever intends to protect the patent (since it obviously would never stand up in court). Most likely, they are just seeking bragging rights "Hey look, we had 30 patents approved this year".
Our government needs to more clearly delineate what software can and cannot be patented in order to prevent more ridiculous patents. I'm more in the 'No Software Patents' camp, but I think there are exceptions, particularly for very specialized software in specific industries.
Huh? Don't mind me, I'm just the new guy.
1. Take a fundamental concept
2. Describe it as complicated as possible
3. Put the result through a patent-lawyers office in order to make sure the claims get even more obfuscated
4. Apply successfully for a patent
5. Profit!
CC.
TaijiQuan (Huang, 5 loosenings)
The author seems to think that rational thought, logic and common sense plays some part in the patent granting process in the USA.
AT&ROFLMAO
I can just see it now - a patent on "An array data structure that automatically grows itself when it's current size is exceeded"...
really, I do
Patents do not have to be meaningful, or even have a remote chance of standing up in court. They are weapons in corporate world and you use them mostly to cause damage. If your public company is sued you lose money in legal fees, might lose investor confidence in a critical moment and overall end up in a loss even if you easily won it. Just look at Research In Motion if you need to see how much damage can frivolous patent deal.
I wrote a computer program back in 1988 that does exactly this kind of thing. Uses a forward-X and forward-Y links for the purposes of spatial ordering.
The program was a "mapping program" for a oldold mainframe computer game called "Space Empires". It was a turn-based exploration and combat system that generated it's output in a textual listing. Each "world" had a number, and listed the "worlds" that had appeared in the Up, Down, Left and Right directions. Very hard to get an idea of how things related unless you fed the data through a mapping program.
A previous version of the program used a big-ass 2D array. Which was fine, until we started playing with universes that had thousands of worlds. There wasn't enough memory for our processes, so I concocted a way to use 2D linked lists to minimise memory usage.
I report, you decide:
u rl=http%3A%2F%2Fpatft1.uspto.gov%2Fnetacgi%2Fnph-P arser%3FSect1%3DPTO2%2526Sect2%3DHITOFF%2526p%3D1% 2526u%3D%25252Fnetahtml%25252FPTO%25252Fsearch-boo l.html%2526r%3D35%2526f%3DG%2526l%3D50%2526co1%3DO R%2526d%3DPTXT%2526s1%3D%252522colorado%252Bspring s%252522.INCI.%2526s2%3D%252522colorado%252Bspring s%252522.ASCI.%2526OS%3DIC%2F%2526RS%3D&PageNum=&R type=&SectionNum=&idkey=NONE&Input=View+first+page
http://patimg1.uspto.gov/.piw?Docid=07117447&home
How about a patent on people who can't tell ITS from IT IS?
Prior art right here
What are the patent trolls doing now -- reading computer science textbooks and language tutorial books and trying to figure out clever redefinitions of these techniques because they can't be bothered to create product (e.g., new wealth) to offer in the marketplace?
This is:
- prior art
- obvious use of technology
- using existing technology exactly as intended AND documented
- merely a clever rewording of existing techniques
America really, REALLY needs to eliminate software patents, and the USPTO should issue a statement saying "to protect your software innovations, refer to the Copyright Act." But of course, patent application fees keep the USPTO running and provide job security, so we won't see that common sense rule come into place in the foreseeable future.
The Christian Right is Neither (Christian nor right). See: Matthew 23, Matthew 25, Ezekiel 16:48-50
As someone that's currently working on some of LSI's driver code (as a customer, bought in), I wouldn't be at all surprised if they think its something new. Their code is terribly unstructured, uncommented, makes use of dynamically changing function pointers, has random inline assembler and has little in the way of API layering to make it understandable. Its a nightmare from a developers point of view. They probably think its a new and exciting breakthrough. :(
They'd have a decent revenue stream from high quality patents and an incentive NOT to just push things through a past a rubber stamp...
They'd have to employ real talent then for patent examiners...
Donald 'Duck' Dunn: We had a band powerful enough to turn goat piss into gasoline.
a patent on "An array data structure that automatically grows itself when it's current size is exceeded"...
:)
That patent is already owned by Microsoft, and is in use in their operating systems and device drivers. Most people call it "bloat"
Seven puppies were harmed during the making of this post.
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.
...in 1992.
Actually ours was a 4-way linked list to keep the list sorted by two different keys, with pointers to the next and previous element.
Unfortunately I cannot pull out the code (lost it a couple years ago), but it was part of an assignment to keep sorting times down in lists when sorted by multiple keys. Inserting a new item way O(n), but sorting by one of the pre-defined keys was then zero time.
Help! I'm a slashdot refugee.
This is Lisp's big break!s ts.html
http://web.onetel.com/~hibou/Doubly%20Linked%20Li
slashdottagsshorterthanhaikunewartform
Fuck, I'm patenting the binary search tree. What do mean prior art? Who do you think you are, Donald Knuth?
For every table in an SQL database, you can create a number of indices. A singly linked list is like a table with one index. A double linked list is like a table with two indices, with the invariant that they're in reversed order of each other. In general, an n-ary linked list is like a table with a number of indices.
However, why settle for linear linked lists when a database can have better data structures like balanced trees and hash table?
I once had a signature.
See Linux Kernel Linked List Explained. Note on the page where it says "You can have multiple lists!". That was baked into the kernel by good, smart engineers.
The world will not get better through technology. We must seek to be better people.
From an old slashdot comment by ShadyG (written before this patent was submitted btw) http://yro.slashdot.org/comments.pl?sid=11208&cid= 350375 :
:)
"The example of one-click shopping is even more illustrative. Something that is obvious will have no prior art, for the very reason that it's not worth publishing. What am I going to do, publish a solution for a doubly-linked list just to prevent a patent from getting issued on it? "
Indeed, I guess you should have
Those of you with a cynical nerve will probably claim that we will soon see a patent that deals with NUL termination of a string of characters...
I claim prior art as well. And my prior art is documented in the Library of Congress, where I put it. I built a database of my very own. It was completed in 1989 (or at least that was the copyright date).
Of course, my CS teacher for Data Structures might also be worried, as he was teaching patented material on this very subject in 1980.
Tiem to write the congress critters again.
What about the pre-computer standard secretarial practice of photocopying documents so as to be able to file them in multiple folders in different orders, or multiple database indeces on the same table for that matter, not to mention a zillion programs that use structures with nextBiggest, nextClosest, etc links.
Maintaining multiple pre-sorted orders is blindinly obvious to everyone (and thus, in theory at least unpatentable) and has been since before computers even existed. It hard to know what's more pathetic - that LSI thought this innovative and patentable, or that the patent office did.
The patent is either some sort of joke (like the guy who patented the wheel), or the computer science skill level at LSI must be incredible low.
This very same examiner (John Breene) has also granted patents #6944634 (file caching) and #6745181 (query based search).
You mean like the master key in a fifth normal form database (binary normalized) data base.
Undetectable Steganography? Yep, there's an app fo
If you describe something in a complicated enough manner then it is quite possible to pwnfuse someone into accepting it. Now if there was only some way to demonstrate prior art or the fact that it is an obvious function..
Until that day comes along, I guess we just have to see Parent and ensure we keep patenting appropriately.
Oops, I now have a doubly-linked post. I suppose I should expect a call from LSI soon.
Proof by very large bribes. QED.
The USPTO smokes all the best USPOT!
Silly this patent is different, it is being done with a Computer.
Undetectable Steganography? Yep, there's an app fo
The entire patenting system is basically a joke. Patents have become a way for companies to bully other companies or to defraud them of their own innovations.
Seriously, who is granting these patents? 100-year old great grandmothers who skim through technical proposals between quilting sessions? "Oh that sounds NEAT. What smart young boys and girls you all are..."
"Method of using the method of strongly straining the waist muscles in order to help turd excretion"
"Method of dissolving a solid dissolvable material in water utilizing the method of mixing the fluid and solid with a tool"
"Method of moving a finger back and forth and applying limited pressure, thereby removing an itch in a body part which has been itching"
and so on.
Read radical news here
I'd like to patent a construct for analysing a logical value to ascertain it's veracity and upon discovering it to be true and correct to execute predefined sets of instructions.
It might be implemented in a high level language in terms of
IfTrue (value)
Execute (statement)
Further that a predefined set of instructions would be executed in the case of the logical value being untrue.
It might be implemented in a high level language in terms of
IfTrue (value)
Execute (statement)
Else (statement)
What do you reckon ?
http://davesboat.blogspot.com/
It simply isn't enough to hypothesise an ideal system; the really hard problem is to fix the system to yield dynamics which, though they'll never be perfect, will in fact do more good than harm. The fact that acedemics don't look at this problem properly is a large part of the reason why people think of government as wasteful incompetance. Economic libertarianism would have less support in the face of competance, but politicans and acedemics don't even try. Making system dynamics work with (varied) human nature would seem to be an obvious problem to attempt to solve, but few people even realise that that is the real issue.
Wikileaks, no DNS
Of course, this has been used since the beginning of (computer) time in the form of doubly-linked lists.
A doubly linked list just means previous and next pointers. That's traversing one sequence in either direction.
What the patent says is may be traversed in at least two sequences.
Which I remember drawing pictures of in my data structures class in about '86- and it was certainly nothing new.
I'm in the no Software Patents camp, but there is one good argument for software patents.
Say this was a truly novel datastructure and it was only used inhouse by the company, without software patents no one would ever know about the invention and eventually the knowlage could be lost.
thank God the internet isn't a human right.
If the submitter and editor had bothered to RTFP (read the f*cking patent), they would see it is covering avery specific implementation of a linked list. The patent covers the idea of having a linked list of pointers with *two ancillary linkakges*. What this allows essentially, is for you to have a list sorted in two totally different orders at the same time... if you traverse linkage A, you get one order, if you traverse linkage B, you get the other.
Now, I don't know if there's prior art on this, and the idea seems pretty obvious to me, but it is certainly *NOT* a simple doubly-linked-list.
I can't build a LEGO model of the Empire State Building without say-so from Shreve, Lamb and Harmon. I'm not sure whether my letter opener (which has a primary purpose of circumventing a technological measure that controls access to a copyrighted work) should be turned into the police (and whether I'd be arrested for doing so). I can't swing from side to side. Now I can't multiply link my data without paying royalties. "Land of the Free" - HA!
I have an idea. Let's hold Patent examiners legally and financially responsible for issuing trivial or frivolous patents.
When our name is on the back of your car, we're behind you all the way!
Profit comes only if the companies you sue think or the judge decides your patant holds.
In the Netherlands, where I live, patents are given without any checks on the claims. When you apply you should do the checks yourself or try to convince a judge afterwards.
I was working at a site once and had to fix a program that kept blowing up. It was reading data into an array with 1000 elements defined, and over the years the input file exceeded 1000 elements, this overflowing the array. I always used linked lists in coding situations like this because I knew that an array would eventually blow up. When I asked a consultant from Anderson Consulting, (who wrote the program) why it was written like this and didn't use linked lists, he said that Anderson Consulting had an official standard which forbade using linked lists because they were too complicated. Maybe all the code at LSI was written by Anderson Consulting and some new person thought they invented something new with these "linked list mysterions".
If anyone deserves a patent, it would be one of the computer scientists of antiquity and not a company now. How is it possible for them to get a patent? If they "invented" the doubly-linked list, they may have a claim, but this is ridiculous
Would somebody please straighten me out on this? It seems to me that there is no patented software that doesn't have previous art in it (in a "nothing new under the sun" kind of way). So why all this fuss about prior art? Does that even apply in software patents?
Heard any good sigs lately?
on CIS students. Next time I get an assignment that requires me to use doubly-linked lists I'll simply have to claim that implementing it would violate the IP of LSI. That is, unless it's for the course "Working around the DMCA and US Patent System with Obfuscated Code." I really look forward to taking that class.
A large oil company spends $1 Billion developing software that takes existing geological maps and analyzes it in a novel way. This robot is so effective at what it does that they patent it to ensure they protect their investment.
For argument's sake, tell me the difference between these two scenarios:
The difference is, nobody spends $1 billion developing a basic software algorithm. It's telling that the example you are trying to use to justify software patents is fictional.
paintball
I am not a computer science programming guy, so I wouldn't know how to find prior art on this. I am not a lawyer, so I don't quite know how to make an Amicus Brief that would be useful in court against any suit.
However, it appears that a bunch of the posters are, and do know of possible prior art.
So how about creating a little space on Sourceforge, or Groklaw, that is a repository for anti-patent prior art. We (community) use this example as a nugget for action. Use this patent's number as an index, and make a searchable repository of information, like "I saw the prior art against this in 'Introduction to Database Design by Ewe Eediot, published by Killatree, 1978'. Even better to include the ISBN number of the book. Then we just need a lawyer to convert it into a usable amicus brief. Leave it all open information so that anyone can use this to kill this dumb patent. Lather rinse repeat for any other patent.
Oh, and maybe a link to donate to the owner of the repository for their costs. You know, for when a $billion$ dollar lawsuit is filed, and this repository saves someone's corporate donkey. And the lawyer (or company owner) realizes that this has been a help, and wants to play nice. It'd be cool for Groklaw to suddenly be fully funded due to having solved the patent mess.
If this has been taught in computer science, it has been published, right? Even the obvious stuff has to be shown to a beginner.
Oh, does referencing code that Does This Action count? Can we reference a block of MySql that shows in 1997 this was already possible, and obvious? Doesn't the release date of Open Source material count as 'publishing'? It is being released for replication, and viewing by multiple people. And it does carry a copyright with certain restrictions.
This would be a good disincentive for the pursuit of these patents, and if done right (searchable) might create a way for the (clueless) patent examiners to more easily find prior art. We could work with the patent exaiminers instead of complaining about them.
I'm serious here. Sorry to only be an idea guy. Please reply to this with why it will/won't work. Or better off, go implement this. Happy Thanksgiving!
Would it be possible to sue the patent office for damages over bad patents? I mean, negligence, politics, etc all play a roll in the approval process. I suspect that a company sued of out existance over a questionable patent, should be able to sue the patent office. I bet that, would stop bad patents.
Next thing you know some bonehead lawyer thought of patenting the use of 0 and 1 and binary structure.
I agree that this examiner is awful. The face of the patent lists all the prior art that he considered. In this case the examiner only found 13 issued patents that were relevant to the claimed invention. Importantly, the examiner did not search for or locate any non-patent prior art (such as the dozens of examples posted on this thread). This is a hallmark of crappy patent examination.
Even more astounding, this application was allowed after only one rejection by the USPTO, which means LSI didn't really even have to argue about the prior art (software applications are typically rejected at least two times).
IBM's VSAM implemented this almost 40 years ago. The idea was that there was one set of pointers for sequential access of records, and another set for "indexed" access. In fact, IIRC, you could have multiple keys indexing a VSAM dataset - the canonical example being that you could access records by last name order, ssn order, or whatever else you chose. You didn't have separate lists - the pointers to the next block were on the block itself. So given any starting index, you could traverse in whatever order you chose.
Now that I think about it, almost every relational database implements some form of prior art for this patent.
The society for a thought-free internet welcomes you.
There's one claim for a list where the nodes have two pointers, and another where the nodes have three pointers. A double-linked list is a specific implementation of the first claim, where the two sort orders happen to be forward and backward. His claim is broader than that, since his two sort orders can be unrelated to each other, but since a double-linked list falls into his definition, his first claim is certainly not novel. And, of course, nothing he claims would be non-obvious to a programmer, but I have no idea how one goes about showing that in court.
A table with an index is not a linked list.
Patrick Doyle
I mod down every jackass who puts his moderation policy in his sig. Oh, wait a sec....
How are they planning to make money on this??? Are they going to pour through plublicly available source code, looking for someone else using "their" data structure, so they can sue??? Seems unlikely. The only other possibility is to license the technology to someone. So what do they do, go around door-to-door saying, "hey do want to write some code with a list with multiple pointers in it? It's really fun, but you'll have to pay us."??????
Wow, Lear Siegler sure has come a long way since the ADM3A!
Serously, unless it's a well known TLA company like AMD or IBM, a few words about the company itself would be nice.
#naabhaprzrag, #sverubfr-000, #agi-fcbafberq, negvpyr[pynff*=' negvpyr-ary-'] { qvfcynl: abar !vzcbegnag; }
I have this pet theory that Pepsi and Coke are ultimately owned by the same corporation and the whole cola wars thing is a clever marketing ploy. Probably not true, but I do like the idea of some Barnamesque old codger chuckling away to himself at a whole worldful of fools.
When our name is on the back of your car, we're behind you all the way!
It looks like no one has bothered to read the patent (even the original poster who kindly included a link to it).
The patent is NOT for a "doubly linked list". It is for multiple links to access the list in multiple orders. Note that a doubly linked list allows you to traverse the list forwards and backwards; whilc this patent claims to allow multiple different orders.
This is a non-trivial problem that comes up frequently enough that a general solution would be useful. I have not read the patent in enough to see how they handle insertions and deletions, so I have no way to know if it actually works, and is fast, etc.
An outright "No Software Patents" stance would say that any company could then duplicate the oil company's unique software, leaving them no protection for their massive investment and intellectual property.
Sure: they can keep it a trade secret. In fact, that's what they're going to be doing anyway, while only disclosing patents that are so vague as to be useless when the patent protection runs out.
If we remove all software patents, we also remove part of the incentive for large corporations to invest in software.
Most of the great software inventions we use today were developed long before software patents even existed. And most software today would be developed whether or not it is patentable, including the oil company software you mention above, because companies don't have a choice.
Your argument is as stupid as if you were trying to argue that companies wouldn't have customer service or send invoices or pay bill unless they can patent the methods to do so. Of course they'd do all those things, simply because they have to do in order to do business.
Give the man a cookie. Finally, someone who actually understands the purpose of patents. The whole deal, here, is that, in the past, people just kept their inventions secret if they could. The end result? Techniques could die with their inventor (read about Damascus steel for a great example of this). And, as you say, meanwhile people have to duplicate the effort.
And where is the evidence that the system is working? In practice, it looks like companies are primarily using software patents to protect (1) things they have to disclose anyway as part of doing business, (2) application areas without actually disclosing how to do anything, and (3) ideas that are basically just straightforward engineering.
Patent protection keeps other people from using their own ideas and the results of their own labor. That is something extraordinary, and it should require extraordinary evidence to keep it in place. So far, software patent proponents have provided not a shred of evidence that software patents are beneficial.
Because this is extactly what software patents are. They are just mathmatical algorithms that the machine does rather than the human with ordinary math using a cooking like recipe syntax to tell the computer exactly how to calculate it.
Copyrights I can see as needing protection since they are the work of many people and alot of investment.
What if someone spent years finding the perfect algorithm or set of algorithms? Should they then be patented?
If the answer is the same as cooking recipes and mathmatical equations it should apply to software as well.
http://saveie6.com/
Paragraph 2.2.6
I think US should KEEP software patents rolling because patents are on their way to absurdity.
Your right about the owner, but I think it is the memory management function you describe... all of it
IIRC (someone help me out here), as a third party you can have a patent re-examined. You need to pay the appropriate fee and show a solid reason why it needs to be re-examined. Also, while an application is still pending, you can send in a list of prior art to the patent office, but this also costs money and has to be in some specific format. So, my question is, is it not possible to set up some kind of technology non-profit that accepts donations and uses its money to file prior art for questionable applications and pay for re-exams of questionably granted patents, especially in the computer area?
I feel like death on a soda cracker.
``Their code is terribly unstructured, uncommented, makes use of dynamically changing function pointers, has random inline assembler and has little in the way of API layering to make it understandable. Its a nightmare from a developers point of view.''
What you're saying is it's not very different from other companies' driver code.
Please correct me if I got my facts wrong.
1- "Invent" a method of making a patent application
2- Somehow get this past USPTO
3- Licence the method of patent application to those who want to get a patent
4- Profit!!
Contrary to what some have automatically assumed and asserted, the claims here are actually unusually clearly written, without obfuscation. You can actually read this one in a few minutes and understand it.
I think there is a more parsimonious explanation for the initiation of this farce than that Ming-Jen Wang and LSI's lawyers are dishonourable scoundrels. Wang is obviously a fairly new programmer with no CS theory background. He has the flash of insight, as have so many of us before him, that one can employ the simple technique described in the patent to advantage. He's proud of it, and takes it to Legal, who eagerly file it.
We can fault Wang for not bothering to buy a book or two, or search with Google, before getting all excited. We can fault LSI for not having CS-savvy laywers handling this sort of thing. And we can fault the PTO for using ignorant examiners like John Breene. But the lion's share of the blame goes to the US Congress for extending patent law to software, creating a situation wherein no programmer can simply apply logic to a problem without unwittingly violating some patent.
The doubly linked list *IS* the prior art. The claim is for "a primary pointer" and "one or more auxiliary pointers". Well, in a doubly linked list, the primary pointer links the data in one order, and the auxiliary pointer links the data in a second order that just happens to be the reverse of the first order.
Also, since it is unclear from the Fancy Article whether "A computerized list is provided with auxiliary pointers for traversing the list in different sequences" means that the list element structure contains the pointers, or whether the auxiliary pointers are managed in a parallel data structure, one could argue that a database with multiple indexes constitutes prior art as well. A spreadsheet stores its cells in a multiply linked structure (row, column, page). Again, prior art. The patent is bogus.
When our name is on the back of your car, we're behind you all the way!
In commemoration of ditsy patents, I am patenting horse feathers.
Table-ized A.I.
It's likely that the "treap" data structure is prior art. And it's more interesting than the linked lists case.
See a brief description here: Paul E. Black, "treap", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 12 September 2005. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/treap.html
Treaps were introduced by Seidel and Aragon at the FOCS conference in 1989.
as I read the patent it's simply a patent for list elements that are in more than one list at the same time - prior art up the wazoo of course (Unix V6 from the late '70s for a start)
..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?
My master thesis contains a prior art :)
According to the transaction history of the patent (Sorry for the long url – http://portal.uspto.gov/external/portal/!ut/p/_s.7 _0_A/7_0_CH/.cmd/ad/.ar/sa.getBib/.ps/N/.c/6_0_69/ .ce/7_0_3AB/.p/5_0_341/.d/5?selectedTab=fileHistor ytab&isSubmitted=isSubmitted&dosnum=10260471#7_0_3 AB), the patent was rejected only once. The main cause was (not surprisingly) that "a method of traversing a list... is an abstract idea or the mere manipulation of an abstract idea." However, some other claims were rejected as prior art according to US Patent 5,950,191 (See http://www.pat2pdf.org/pat2pdf/foo.pl?number=59501 91).
Saying that, the mentioned patent may not be so obvious as seems at first sight. The idea is not a simple linked-list or doubly-linked-list, but somewhat more sophisticated linked-list with auxiliary pointers.
It appears to be a patent on having two list pointers in a structure (auxulary pointer so you can sort the list in a diferent order). Funny even the linux kernel has a really fancy (arguably patentable) way of doing this using very simple macros. Though yes this could also cover doubly linked lists.
/usr/src/Linux/include/scsi/scsi_cmnd.h - struct scsi_cmnd: Belongs to two doubly linked lists, though not for storing in diferent orders, it's because that structure happens to have mutiple systems tracking it.
For prior art I'd give
This is probably a patent from some engineer who's been pushed by his boss to come up with things to patent because he's not done one recently. Personally I'm accredited on a couple of software patents, but being UK ones, there is a fairly heavy ammount of proof that this is a concept of tangable value, eg you can't patent a linked list because it's not going to do anything, but you could patent an application of it which makes the thing your product does do it better/faster/etc.
Oy vey.
NeXTSTEP event system. 1989. Key structures linked into a hash table, scancode lists, character code lists, and hotkey lists. Traversing each linkage gives one the appropriate ordering.
FDOS disk management. 1973. 8008 assembly language code for managing disk blocks on an 8" floppy. A primary linkage and two secondary linkages.
Prior art on this goes back so far that if it were patented, the patent would have expired and the method would have lapsed into the public domain.
As for software patents, I have no problem with them on the surface (well, except for those that are obvious, but that's a problem with the patent office, not patents in general). However, I think software patents should have a more limited lifespan. After all, 20 years is a *very* long time in the world of computing (just think how different things were in 1986). Something like 4 or 5 years makes far more sense.
What you obviously don't understand about software patents is that a patent is supposed to protect a specific way of doing something. Which in the case of software is already protected by copyright. This provides people the will for innovation, I can look at some software that really works and think "hey I can do this better", and do so.
However, Software Patents currently allow people to patent a broad concept of what software could do. Now, I can't look at a concept and think "hey I can do this better" because someone can patent that idea. If movie companies could patent concepts, there wouldn't be any new movies for 20 years.
Prior art would include my AS-level computing course. That's pre-university.
I wish to patent sorting in general, can I do that ?
Yes, and make sure that you use Spring to actually instantiate your ThingImpl because "new ThingImpl()" isn't good enough. Oh, and throw a design pattern or two in there. Definitely a good enterprise design, there.
My thoughts were along those lines, too. It's not too much of a stretch to imagine the programmer is so inexperienced and/or has so little background in software that really did think his idea was new and original. Add to that the likelihood that having a patent portfolio is key to promotions in some companies. I've been around long enough I've seen self-proclaimed experts reveal 'new and unique' solutions to which I can immediately comment, "Oh, that's just *foo*, like they used to do in *dinosaur-age technology*".
Why you people don't stop that patent madness for good?
No, No, NO. You just do not understand. It is not that the programmer did not know that it was an old idea. It was that the old idea never got written up in Hindi, so he was clueless. Where do you think LSI drivers, (and everyone elses) get written these days?
wake up and hold your nose
Links in a list are an implementation of an index. Lists are a special case of a tree.
I once had a signature.
As far as I know, skip lists have no patent on them, and they'd be a use of linked lists like this.
Patent applications such as this one make my blood boil, and the fact that they get approved is even worse
I thought Microsoft's version was for an array that does not grow when its size is exceeded, thus resulting in buffer overflow exploits.
I would have loved to tell my Data Structures professor a year ago that I couldn't do my homework because it would infringe on a patent.
At first, I looked at the examples and thought I hadn't done anything similar. But no, just last week I wrote a script. Keeps some metadata about some files. Each file is represented by a Perl hash, that is stored inside another hash, which is indexed by a cryptographic hash of the file. Since this is Perl, each element in the parent hash is a reference to the child hash, so this makes it trivial to store the same reference in other hashes -- I also have a hash indexed by filename. There's a third hash that doesn't directly reference these objects, but contains the cryptographic hashes of them, making it trivial to look them up.
In other words, I thought of it, all by myself, without finishing college or taking a data structures class. And this is getting really fucking absurd when I invent something obvious before I learn of the patent and the decades of prior art.
Don't thank God, thank a doctor!
Adaptec don't provide documentation OpenBSD Clashes with Adaptec In Quest for Docs and LSI abuse the patent system.
So who's left?
The data structure is obvious - if you want to save time looking for stuff, you file it in the first place you're going to look.
There's no algorithm listed in the patent, nor are there any rules for maintaining the multiply linked data structure. That is, the patent describes what the filing system looks like, but doesn't provide the novel element of how to file stuff properly in the first place, or how to decide where to look.
Sets of data that are multiply linked into meaningful lists? Not novel. Incredibly smart way of deciding where to link this item into each list that shaves O(N) down to O(log N)? Priceless.
It's really past time to move to New Zealand, isn't it?
Ok, to summarize said claims and said summary:
... It would therefore be advantageous to provide a system and method for quickly traversing a sequential list in a second sequence."
1) A data structure where each item has two (or three) pointers, and specifically it has to be done so that there are exactly two (or three) ways of traversing the list.
This is not a doubly linked list, nor does it resemble one: doubly linked lists have ONE ordering, each item using two pointers to point forwards or backwards with respect to the ordering. The point is that this patent presents a completely and utterly useless data structure. A linked list is not made for searching quickly. But yet, the patent claims:
"The conventional method of searching a list is sequential. This involves traversing the list to locate a specific item in the list. [...] The conventional method is time consuming and may require many computational cycles to find the necessary items in the proper sequence."
This method is not conventional. It's the only method. That's the whole point of linked lists. Then it continues:
"Lists may be sorted so that the items may be accessed sequentially. Once the list is sorted into a particular sequence, the individual items may be accessed in order very quickly. However, there is substantial overhead in the reordering of the items into the desired order."
If it means accessing an individual item randomly, this cannot be done, unless the list is first sorted into an array and use binary search, which breaks away from the linked-list structure. If it means accessing all items in order, then no, there is no substantial overhead in the reordering of the items.... it's the same overhead as accessing the items in order.
Then the conclusion sums up these fallacious arguments into its climax:
"In some cases, there is a need for the list to be presented in more than one order.
Indeed it would be nice to quickly traverse the list in a different order. But first this does now allow us to search better (as suggested in the first paragraph), nor is the new data structure more efficient than other data structures out there (you CANNOT do better than linear time sorting if you need to traverse the list!).
This is like a classic example of a "bad, horrible" data structure that undergraduates are asked to analyze in a homework question, like "here's a data structure. Write a paragraph showing why it isn't a good idea. Can you come up with something better?"
Notice that this structure does NOT allow constant time insertion/deletion, which is the whole point of linked lists (the tradeoff for not being able to search quickly). Without a tree structure, there is no way of knowing where to insert a random element, except to prepend or append it to the list. So when insertion/deletion is frequent, binary search trees are better, as they still allow linear time traversal. If search time is critical, use hash tables. If one needs multiple orderings, then use multiple index trees (aka database). When the data is fixed and never changes, then multiple arrays storing values and pointers to the items are better, because they not only allow linear time traversal, but also fast search. I can go on and on here... to put it bluntly, the said data structure is a new idea, in the sense that it's so stupid no one would actually use it (and thus would never mention it).
Don't worry guys. This patent managed to dig so low technically that it is worse than obvious data structures. And if anyone is dumb enough to pay them for such patent... well, natural selection.
I was a teaching assistant at a technical University in 2003 - 2005. One of the homeworks I assigned to students in the OOP class every year was to build a dynamic structure of Person(Name, Age) objects that can be traversed to display the persons in alphabetical Name order or in ascending Age order...
Another homework consisted of building a spreadsheet-like application with theoretically unlimited rows and columns. In this application, each Cell was linked both by column and by row, to allow some operations to be easily applied to an entire Row or to an entire Column.
I guess me and all my students are liable...
The early bird may get the worm, but the second mouse gets the cheese.
The summary is not inaccurate. A doubly-linked list is a specialized example of the method patented. This also means it is indeed prior art.
Moreover, imagine an object which is then outfitted with the programmer with a singly linked list to represent some ordering. Next it is outfitted with a different singly-linked list to represent some other ordering. We now have an infringing case but we did do nothing but apply the well known concept of singly-linked lists twice.
Btw., even if something is new as in first to patent office it does not mean that it should receive a patent because it might be obvious enough. If first to patent office was the only criterium, I suggest next time your country changes tax laws, that you apply for a patent for correctly filling out tax forms.
Hey don't blame me, IANAB
Having the Patent Office associated and incentivized by the revenue stream of patent generation is part of the reforms that are needed.
- Inventors must specify the royalty rate they wish to charge for use of their patent (different classifications of use with different rates are acceptable, so long as they are measurable and enforceable)
- Patent Office performs more detailed 'prior art' and 'non obviousness' searches (which they are able to do with the increased revenue, and incentivized to do by taking a financial hit when they get it wrong)
- Patent Office acts like the music collections agencies, bringing together manufacturers and inventors ensuring they get charged and paid (taking a small cut off the top)
- The organization which made the invention, still has to pay itself royalties on the use of the invention
The intention of this is to return patents being something which fosters innovation and technical progress. The ability to use patents to prevent competition is completely removed, a company must license their patent uniformly including to themselves.There is now greater incentive to work on R+D, as your R+D work can fairly be licensed out and become its own revenue stream. As the innovator you will always have the most intimate knowledge of the field you've innovated in, at least for the first few years, and have a natural technical advantage in that period for your completed product. As the innovation gets to be more mature, then others may find different ways of exploiting your innovation. This will return royalty to you, and fair compensation for your past efforts. Of course if you have continued to innovate in the meantime, you will have invented new methods and have both a new income stream starting up, as well as a new competitive advantage for being able to bring that to market.
Relational database indexes usually use a B-tree data structure, though it it sometimes an R-tree or a GiST. Putting a sequence of items into a table and then creating an index on them does not make them a linked list, and it certainly isn't anywhere close to prior art for this particular patent.
Patrick Doyle
I mod down every jackass who puts his moderation policy in his sig. Oh, wait a sec....
I did this back in the early 90s. The code is probably no longer in use. I needed objects to be navigable in two different orders so implemented a quadrupally linked list - up, down, left, right.
The real problem is that things like this can be patented in the first place.
Amusingly, the website referenced by the original article could be prior art. Scroll down to the bottom and note the links for "Browse by Inventor" and "Browse by Date". Looks like a "computerized list that may be traversed in at least two sequences" to me.
Reduce, reuse, cycle
This one is truly sad. I know that the Patent office feels compelled to demonstrate weekly that its examiners incompetent in the area of software and the process is hopelessly broken, but this one is bad even for them. But armed with this patent, LSI is likely to try to extort money from small fry who can't afford the $$ to defend themselves in court.
One wonders what it will take to get this reformed. Perhaps when someone gets a patent on the business process for getting a Congressman to get you an earmark??? Those Congressmen will be outraged when someone demands a fee from them for taking public money and diverting it to useless projects. They scream "Someone ought to pass a law".
I actually am a firm believer in patents and intellectual property protection, but the US Patent Office is working overtime to change my mind.
Your argument might hold water if it actually cost $1 billion to invent this technique. It didn't.
Even if it had never been done before it would have taken a decent programmer only five minutes to "invent" it.
No sig today...
Did you know that the XOR function was patented and earned the Patent Holder countless millions until it recently expired? are also patented!? This patent was actually enforced in 1994 to stop the sale of the Amiga Computer in the USA after Commodore stopped paying royalties on the patent. The XOR function was used to move the cursor around the screen.
Patents on algorithms and software should be disallowed.. as these types of patents are ripe for abuse!
Yahma
ProxyStorm - An anonymous, free, apache based proxy server.
Am I missing something? Where's the "breaking news" part of this? Don't get me wrong, honestly I mean no offsense, just they say this happened back in April, and thus we should have heard about it in April. So I'm wondering if there's something new, such as maybe a first case in court or something?
between copyright and patent.
http://www.imdb.com/title/tt0023027/
Yes, I am joking.
The Kruger Dunning explains most post on
Comparing a patent to a trademark is like comparing apples to oranges. Use of the term "intellectual property" tends to cover up the following facts about patent, copyright, trademark, and trade secret laws:
Does this make Mr. Stallman's point any clearer? What's wrong with saying "patent", "copyright", "trademark", or "trade secret" as appropriate in place of "intellectual property"?
Software and business-method patents have a long delay to first examination. An application in one of these fields, filed today, may not be examined for four years, maybe longer.
Because the patent has issued, the U.S. Patent Office's file for the corresponding patent application is available to the public and can be seen online. I took a look and, as a practicing patent lawyer, I was stunned. The PTO rejected the application only once, and allowed the claims after a trivial amendment and argument.
The patent examiner's search strategy is part of the file. The examiner appears to have looked only in databases of patent documents and only for a couple of combinations of buzzwords. The search would have missed the substance entirely because the examiner used only the terms chosen by the applicant.
If someone started waving this patent at one of my clients, I would go right to the ACM and IEEE digital libraries, and possibly drop dead of a heart attack if I didn't find anticipating prior art in less than an hour.
When I read this story, I thought of Lear Siegler, Inc. -- the manufacturer of the old ADM series computer terminals. I haven't seen one of those for over 25 years....
Right, a traditional doubly-linked list is a specific case of what is claimed in Claim 1 (probably the most generally useful), where one sort order happens to be the inverse of the other.
It might be easiest to illustrate that by showing that it is a special case of something widely used an understood: that is, in this case, that it's nothing more than a traditional linked list, used in the exact way that traditionally one uses a linked list: to impose a sort order on a set of ADTs. That is, suppose you have a set of unlinked data structures and convert them into a linked list by adding a new data element to each of the structures which is a pointer to create an ordering, putting a special null pointer value in the last element, and creating a special external pointer to the "head" element. Suppose you then want to create a new ordering on the same set of data structures. Anyone familiar with the process used to create the first ordering would do the same thing: take the data structures as they exist now, and add a new data element to each structure containing a pointer to the next element on the new ordering, put a null pointer in the last element with the new ordering, and keep a pointer to the "head" of the new ordering. Now, suppose I want to impose a third ordering on the same set of data structures? Well, I add another pointer to each data structure...
Imposing an order on a set of data structures by appending a pointer to each structure pointing to the next is creating a single linked list, which is clearly well-established and familiar to anyone even remotely skilled in the field. The output of that operation is a new set of data structures (they can, of course, be used now as a linked list, that's the point, but they are still just another set of data structures). Imposing an order on that new set of data structures by appending a pointer on each structure pointing to the next to create a new single linked list with a distinct order is exactly the same as the operation to create the first single linked list.
I read the application, it's just an array (2 wide) of double-linked lists. As this wasn't explicitly specified, can I now not create a patent for a 3 double-linked lists. This is kindergarten stuff. Any examiner who had a clue would laugh and reach for the DENIED FOREVER stamp.
It would seem to me unreasonable to be able to patent *anything* that is in common usage.
Unisys will kill LSI if they notice the patent. Their DMS database has been around at least 20 years.