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."
I would show the prior art, but I can't read the reel-to-reel tapes.
"No matter where you go, there you are." -- Buckaroo Banzai
what a genius. he deserves millions over millions for that. and chicks for free.
People are immediatly shouting "prior art!" I don't care about prior art as much as I care about the fact that it's another software patent and unworthy of being patented.
I read the claims... somebody submit a patent for insertion and deletion operations.
The US patent office has proved its incompetence in this area time and time again.
If you must have software patents, why not a specialist software patent office to deal with them?
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!
OK, so where do I go to submit prior art?
I've got personal programming I've done that uses linked lists. I've got an instructor who's been teaching them in a 200-level C++ course for god knows how long. Hell, Herb Schildt's "C++: The Complete Reference" was published before this patent was filed in 2002.
tasks(723) drafts(105) languages(484) examples(29106)
thats not a reference, thats a pointer!!
;)
*smack*
Go back to Algorithms and Data Structures, Do not pass go, Do no increment the Counter by 200
$_="Slashdotter";$syn="OTT";s;..;;;sub _{print shift||$_};s!ash!Perl !;s=$syn=ack=i;tr+LLEd+BLAH+;_"Just Another ";_
These, were the examiners. I wonder what it takes to be an examiner, surely you must have a little knowledge in that particular area?
Do they get a bonus at the end of the week, for the number of patents they have past.
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.
What am I doing this morning? Why, furiously working on my patent on all types of sort! First year Computer Science students will BOW to my will (assuming they want to pass that radix sort assignment!)! Muwhahahaha!
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.
See this is the sort of thing that should be penalized. How about ban LSI from filing patents for a year. See how they like them apples.
This doesn't really surprise me. Most likely this is the work of an over zealous marketing droid looking through some slides and thought, my god, we have invented perfection!
I'd like to think the engineers at LSI aren't going around thinking they invented computer science...
Tom
Someday, I'll have a real sig.
I read about this technique about 23 years ago. What is going on here? This looks like material for a slashdot poll, viz:-
Why do you think that the latest LSI is bogus?
What about it, guys?
--E.
I've got so much code modifying to do.
You know, there is a difference between trolling and pointing out the flaws in your reasoning. Just saying.
People are immediatly shouting "prior art!" I don't care about prior art as much as I care about the fact that it's another software patent and unworthy of being patented.
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?
I realize that software has seen more bad patents than it should, but that suggests that the system should be cleaned up, not tossed. And software patents aren't nearly as bad as the nebulous "business model" patents or "natural discovery" patents.
Note that the worst offender usually offered up as the problem child of software patents - "one-click" - was not a software patent, rather a business model patent.
...essential part of the Process of Innovation.
This is a backdoor way to shut you down as your code uses 'em a-plenty!
Huh? A pointer is a reference (but not necessarily vice versa).
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."
The same patent was mentioned in this Slashdot article. What is new since then?
Then LSI would sue and say they implicitly covered that and you'd counter sue for prior art, and that patent office wouldn't care either way. Now if every time someone challenged an approved patent for prior art or that it conflicts with an existing patent, the patent office had to put up the defense in court and spend the money, then things might change. They were the ones that said it was novel, let them defend their decision.
refactor the law, its bloated, confusing and unmaintainable.
Look here
0 0.misc/msg/205bb134a5ab9982
http://groups.google.co.uk/group/comp.sys.ibm.as4
What I describe, doccumented on the usenet, Is a multple linked list. I dont claim that I invented this method by any means - I'm sure someone must have come up with this b4 me as it is the next logical progression from a single linked list. BUT, At least I posted the method on the internet way back then, so prior art can definatly be proven.
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".
"Do they get a bonus at the end of the week, for the number of patents they have past."
Where's the motivation? If USPTO approves a few more patents, I don't see another dime!
There is no US patent #10260471. It looks like a patent application number.
Check out the result of a search at the USPTO on that number.
Currently we are in the low seven millions in US patent numbers.
For all of that, this is the stupidest patent application I have ever seen.
Blasphemy is a human right. Blasphemophobia kills.
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.
LSI Logic's patent lawyer should be barred from practice for a month, required to take a patent law refresher class on research, and do another month pro-bono (preferably for a "public domain IP" org). His law firm should pay a fine to a public domain IP org equal to triple the fees they received.
And if either of them have done this before, they should be barred from patent practice permanently. If they practice after the bar, they should be slammed with all the "practicing law without a license" remedies, starting with losing their licenses and corporate entities.
Those lawyers are sworn gatekeepers to keep out frivolous and invalid legal cases. They're up against underpaid, undereducated, nonmotivated PTO dupes, then slightly (legally) more clueful initial courts, only after years facing expertise in an appeal. By which time real inventors, supposedly protected from better funded competitors by the Constitutionally mandated IP protection system, are usually too broke to keep slogging down the road towards appeals, with investors breathing down their necks and jumping ship. The lawyers who are part of the problem, not the solution, should be fired. Taxpayers are paying to subsidize the entire rotten IP registration and court system: we should use it to eliminate its inside attackers.
--
make install -not war
Employee Evaluations have never been so easy at LSI :-)
Maybe so, but it's also damn insightful!
Would B-Trees fall into the category of multiply-linked lists? I mean depending on what you are looking for you would go a different way down the tree. Good ol' prior art.
The following references are relevant prior art and show a more sophisticated approach than a simple single or doubly linked list.
Pugh, Skip Lists: A Probabilistic Alternative to Balanced Trees, Communications of the ACM 1990
Munro, et. al., Deterministic Skip Lists, ACM-SIAM Symposium on Discrete Algorithms 1992
Because Macs weren't designed for people with one-track minds.
You've still got it wrong. It's an abstracted class.
You cannot dereference the pointer; that's impossible. You must first realize that there is no pointer, and that you're only dereferencing yourself.
110100 1101000 1101000 1100110 0 1101111 1101000 1100011 1
Another perfectly good /. 2007/04/01 post wasted.
If Hemos had waited there would have been some real funny comments from all US and EU.
If Ming-Jen Wang and LSI Logic Corporation had waited to file, then the date would
have clued US and EU all in on the tasteless joke of the few, on the many of US and EU.
DAMN, Hemos "PLEASE" next time save it for April 1,
because IPR/PO are so dang dumb-funny, we could all
be brought to tears and have a good cynical laugh.
Unaccountable leaders are masters, and unrepresented people are slaves. How do US and EU fare?
Does this apply to completely unbalanced binary trees?
-1 not first post
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
It's lawyers in general. Lawyers, and IP firms. They do nothing but exploit what was originally a very good system. Liberal courts don't help either. Wild interpretations of patents and patent law are more to blame than anything else. If the courts were more firm, and lawyers knew they weren't so wishy-washy, we'd never have to go through this.
Blame the John Edwards of the world. Spineless, slimy lawyers are the root of all that is evil. They will do anything to make money. They chase ambulances and they write double-speak patent applications that judges can't interpret. Get rid of all of the lawyers, and we won't have these problems.
Prior art for this story.
real Mac Users don't browse at full screen - and since the menu bar (for example) is not part of the movable window, it's not neccessary... Exposé and the overall design makes it more powerful and productive to use like "square"-formed windows and not the full 1280x1024 or whatever... I miss those nice and handy space-saving windows always when I'm under Windows!
I think it's good that these are getting patented; maybe people will stop using them now. Multiply linked lists are a maintenance headache, and often a performance bottleneck, too.
Texture mapping.
How about slocate?
Or rsync?
Oh and data muxing.
Fantastic!
Someday, I'll have a real sig.
Ok, perhaps no patent existed on this before, and he got it through, but what chance is there that it can be enforced?
There could be so many potential infringer's and so many more entities with money that would see it as worthwhile to halt any attempt that he'd be a fool to do anything with this but frame it and stick it on the wall.
I'd love to get a pointless patent, so I could publish a paper on how stupid it is that I got it, and get my 15 minutes of dubious fame before dedicating it.
I think this is a global conspiracy to undermine the patent system by submitting totally invalid patents. Once it's found they're unenforcable they'll kill off the patent system that is broken. Yay for that. Congratulations to that law firm and whatever!?
:) concept. But AmigaOS gave you a linked list for nearly everything, stored all it's windows and objects and tasks in them, and expected you to traverse it with exec.library and utility.library.
Actually I'm curious, when was your first experience of a linked list implemented in a highly exposed manner? As far as I recall it was in AmigaOS (but then I am only just young enough to remember that as my first OS and the first OS I cared coding for). A lot of systems do use linked lists, it's a very old (1960's?
Along with tags (tagitems, taglists) and ReadArgs they're things I miss in modern operating systems which seem too 'hidden' and trying to feel too unixy. It's all pipes and sockets and syscalls, blagghhh.. I'm glad QNX puts message passing right in your face, and DragonFly is bringing it all back to me again. I can't wait until someone patents one of those again!
The site displaying the patent must use linked lists somewhere in the code. The menu at the top says "Browse by Inventor", "Browse by Date" etc...
Presumably the patent site existed before the patent was submitted.
America, Home of the Brave.
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.
Will it be when the corporations own people?
Or, at the very least, Google. For god's sake, the patent's TITLE is 'Linked List'.
No, there's never been nothin' called a 'Linked List' before. All that stuff you find on the internet is hogwash.
110100 1101000 1101000 1100110 0 1101111 1101000 1100011 1
You need A) some kind of college degree and B) a pulse.
I know some people who applied to the patent office very recently. They were hired after only a phone interview, and given a very short time table to make a decision (something like a week). They also try and rope you in for three years with a signing bonus. So it looks like they're desperate for warm bodies.
Once you start though, the first 6+ weeks are training. But given the joys of government bureaucracy, who knows how much of that is actual training in patent law versus pro-life indoctrination.
Either:
1) the "inventor" will hold it strictly for bragging rights, or
2) he will attempt to litigate and the patent will be found invalid and thus will be issued a trip to the shredder.
The original generic sig.
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.
This is actually great and should server as a reminder to us all.
We should continue to submit rediculous patents just to show how counter productive software patents in general actually are. Anyone still have their first year CS course notes? There should be plenty of material to patent!
I don't mind they patent a hammer but not how it's actually used.
Views expressed do not necessarily reflect those of the author.
its nice that drug companies each invested $100m and more drug research, got their patents, and they are now selling the drugs for reasonable prices to public and drugs are accessible anywhere in the world. not only that, but they are also making discounts and providing easy access, and even giving out drugs in most poor and needy countries so that things like aids or other dangerous diseases do not spread out.
oh wait - none of these are valid in this universe - all these are happening in alternate universes.
Read radical news here
Pfft! No imagination. Why settle for a doubly or triply linked list?
I'm off to file a patent for a MILLION-links linked list.
This is really funny, for me I don't care, I live in EU and there are not soft-patents :P
I've been meaning to patent breathing.
Oh, man, I can't wait to serve up the "cease and desist" orders once I get it!
As another poster said, the green plus is really more of a zoom button. Which browser are you using? Using Safari, the zoom button expands to encompass the width of the page you are viewing up to the width of the screen. Firefox may have different behavior, but I don't use it on the mac any more.
Applications that have sensible full-screen behavior generally have a full-screen menu option.
This works ok for most apps, but zoom in Preview is pretty useless. The newest Adobe reader has better behavior and have defaulted to that for PDF viewing.
I'm very glad to know that your personal computing habits are to be considered the forced norm for all users.
I love my sig.
Actually, I've heard tell they do have a sort of quota. It's based on quantity, not quality. So, they don't really care if it's going to get contested later, so long that it's out of their hands.
"... result of digestive operations, nutrition intake is processed into a soft pulp that has unpleasant smelly properties and color that is brown in appearance" .... "resulting brown color is the distinct property and identifier of this soft smelly pulp"
Each time you go to loo, you will be infringing upon my intellectual property. Im open to rational amounts of out-of-court settlements. So cover your ass now, or be sorry.
That includes online shitting too.
Read radical news here
This is simple legal welfare for US marginally employed
politicians waiting for the next election funds infusion
from corporate supporters. Anyone with a law degree can
attack or defend a patent to make a living.
Unaccountable leaders are masters, and unrepresented people are slaves. How do US and EU fare?
if your solution doesn't infringe leaf nodes in the tree of claims, it doesn't infringe.
... software algorithms are discovered, not invented ... just like mathematics.
You solution only has to infringe on one of the key nodes, not all of them.
Learn more about the patent law before spreading misinformation.
And this particular patent is as stupid as it gets, and it is exactly the reason why software patents should be invalid
"real Mac Users don't browse at full screen"
And real scotsmen don't use macs. Please drop that stupid 'tude.
"and since the menu bar (for example) is not part of the movable window, it's not neccessary"
I don't get your logic. Because the menubar, a 20pixel row of space, is not part of the movable window, it's not necessary to maximize the window to get the maximum available browsing area?
"Exposé and the overall design makes it more powerful and productive to use like 'square'-formed windows"
You'd think Exposé would make it a simple thing to use ALL fullscreen windows. Meanwhile, I can only think of a couple apps I wouldn't want to run full-screen. But then, I'm kind of adept at using keyboard shortcuts. I can see how you could be unproductive if no one ever told you about 'alt-tab'.
"and not the full 1280x1024 or whatever... I miss those nice and handy space-saving windows always when I'm under Windows!"
Hm. I suppose the rumor that "there's no cure for religion" is more or less true, especially for Mac zealots.
110100 1101000 1101000 1100110 0 1101111 1101000 1100011 1
One button minds, on the other hand...
Actually I'm curious, when was your first experience of a linked list...
Intro to Data Structures class at Carnegie Mellon University in 1977.
And yes, the programming language was indeed COBOL.
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!
Everyone knows that "getting anywhere" at the PTO is impossible and would be rejected out of hand. The PTO employees are up on the current literature and the proofs of Zeno of Elea are fresh in their mind.
This issue is a bit more complicated than you think.
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
Once in a while I find myself at a Windows machine. Oh why do they force me to maximize my windows when all I want is to zoom them?
Linked-lists is a basic concept taught all computer science students in "Data Structures" classes.
There are hundreds to thousands of books that cover the basic fundamental topic.
To allow a patent to be granted on such a basic fundamental computing concept will lead to NO software patents in the future.
Microsoft, IBM, SUN, every IT company, and every CS book seller should all get together and sue the patent holder to keep their patents and distribution rights valid.
s/past/passed/
S.D.Rycroft http://www.simon.rycroft.name
it was appointed by the white house. You just need to have the right politician in your pocket and then you can get lots of patents.
The original unix block i/o system used multiply linked buffers, as documented in the Lions (1976) book.
See in particlar page 76 -- "Buffer headers may be linked simultaneously into two lists", "Both the...lists are doubly linked to facilitate insertion and deletion at any point."
--
Roger
Sure you can dereference a pointer. That value has to live somewhere in memory... Otherwise pointers to pointers to pointers couldn't exist. Not that it's a good idea, but it can be done.
make cast? I've done make, make install, make clean, make menuconfig, make xconfig, make modules make modules install, but I've never done make cast...
But obviously I've never compiled anything with a linked list in it anyhow, since this dude just barely invented them.
My regime would require this for patents that are blatantly obvious or have as much published prior art as linked lists do. You can be there'd be a lot fewer frivolous patents issued if the examiner and the applicant were forced to eat the printouts if the patent turned out to be retarded.
I'm trying to teach myself to set people on fire with my mind... Is it hot in here?
meh... I accidentally modded you something you don't deserve. The easiest way to cancel that is to reply!
I'm guessing OS X doesn't maximise (as Windows users understand it) because somewhere back in the user-guidelines-were-followed-days, it was noticed that users were confused or slowed down when they could see the other application open, and had to hunt for the minimise button.
Not in C++.
/.)
(In C++, reference pointers you! No, that doesn't make any sense, except possibly on
I'd be quite embarrassed to have filed for a patent for this "invention"...
However, he does finish up with "A binary tree can be seen as a type of linked list where the elements are themselves linked lists of the same nature. The result is that each node may include a reference to the first node of one or two other linked lists, which, together with their contents, form the subtrees below that node."
I'm not sure that any of that addresses what the patent addresses. OTOH, I'd be hard put to guess what a triply linked list might be good for. Additional links intended to speed up access to the list clearly have prior art.
You can't see ANYTHING from a car, You've got to get out of the goddamned contraption and walk...Edward Abbey
I had a friend who was an EE and worked for the USPTO for a while. They were very aggressive in recruiting her, but after six months she was desperate to get out.
As a few nearby posts have said, they are apparently desperate for bodies. They seem to be in a chicken-and-egg situation - while they are understaffed, the reputation for stress and being underpaid makes it hard for them to hire/retain examiners. Inability to hire/retain examiners results in the existing examiners being overstressed.
Sadly, for a LONG time, the USPTO was one of the government's biggest moneymakers but was also one of the most underfunded, as all of their income went to what was basically a "generic" fund allocation pool. I've heard efforts are being made to rectify this (i.e. let the USPTO use the majority of what they bring in rather than sending it elsewhere), which should help make things a bit saner.
retrorocket.o not found, launch anyway?
http://www.safarix.com/0131409093/ch11lev1sec5
You mention that academia "does a good job", but are you sure that would continue to be true if those phD candidates can't count on high paying jobs once they graduate?
This appears to more closely resemble a table index in a database.
An unsorted list (records) with many sorted lists of pointers (say, a list of pointers sorted by last name, then a list of pointers to records sorted by some other field).
Oh, a database index. What a novel, patentable, concept.
...couldn't see the other applications... "couldn't"
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
Macs have shipped with wide screens for years. The zoom behavior exists for the same reason that LaTeX defaults to using large margins. Most web sites will expand to fill the width of of the window. On a screen that is 16" wide, a page full of prose will have lines that are way too long to read smoothly. The designers of the software are fully willing to set the defaults to sensible values, even if the users are not sensible.
For pretty much every other app, the zoom button will only expand the window as much as is useful. However, with web browsers (especially with tabbed browsing) this behavior can be annying. Still, it works for most pages. If it weren't for tabbed browsing, the OS X zoom button would exhibit pretty much optimal behavior.
I tried that, but they all just ran away screaming when I clicked.
Maybe I need to click with something heavier next time.
SYS 64738
I'm filing an applicaiton for "Process and method for posting an article on an a patent when it is issued, then posting the substantially same article a year later, and calling it news both times." Your ass is mine, /.
It's not because of prior art. And definitely it's not because it's obvious. It's invalid because it infinges on my patent on parts of memory used not to store data, but to store the address of another place in memory. I call this invention "iPointer", and fear that many many big software companies are infringing.
Rome taught me patience and assiduous application to detail. Virtues which temper the boldness of great, general views.
Reminds me of...
C: You shoot yourself in the foot.
C++: You accidently create a dozen instances of yourself and shoot them all in the foot. Providing emergency medical assistance is impossible since you can't tell which are bitwise copies and which are just pointing at others and saying "That's me, over there."
Oolite: Elite-like game. For Mac, Linux and Windows
well... I DO know Alt-Tab and use it.
It's just that there are a lot of windows that actually run good and productive enough not at full screen mode (of course there are those who really should be run at full screen)... a browser, a ftp-client, terminals, IM windows, players, editors, etc don't need to be run in full screen.
usually a good website will also look good without using the full screen, while others need a lot of space.
I think of course it's a personal opinion... but I'm sure more of the mac users will have their apps not in full screen while Windows users prolly have like basically every window maximized.
you don't need to flame so much just about that unimportant off-topic...
Programmers and are going to need protection from software patents like these. I say we need a GPL patent office ans start putting in every public-domain algorithm / methodology / GUI into it (asking permissions from the author(s) of course). That way we play by the rules of the game (use patents through USPTO), protect programmers (using a patent that has no strings attached / no royalties), and undercut every son-of-a-gun hack / corporation (and associated lawyer(s)) from profiting from what should be free.
Just an idea. I think the framework is already in place (a la GPL for source code) just need to extend it.
I'd hate if someone tried to patent the way I hold my pencil or tie my shoe or tie my tie or any of my handy macros.
I suspect that the institutional problem with a current office that issues patents is that it is procedurally easier to assign a new software-related patent, than reject it. Is that true?
I do not believe in karma. "Funny"=-6. Do good and forbid evil. Yours, Oft-Offtopic Flamebaiting Troll.
I sure the hell am glad that patenting software wasn't in vogue when Dr. Codd published relational theory. Or even for that matter file systems, GUI's, ASCII, keyboards, mice, you name it. Even command prompts.
Table-ized A.I.
Here's looking forward to more news from LAST YEAR.
Patrick Doyle
I mod down every jackass who puts his moderation policy in his sig. Oh, wait a sec....
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.
I wrote code using linked lists back in the early '90's.
I saw other code with linked lists as far back as the
late '70's at D.E.C. (digital).
Why doesn't this A.O. try an patent the wheel barrow?
Everything old is new... LSI Patents the Doubly-Linked List
I'm just glad somebody patented it. I mean, I've been using prior art like this for 25 years, just hoping someone would come along and try to squeeze money out of it. Thank goodness there are still companies out there with more money than sense. It really brightens my day.
This is a perfect example for anyone isn't interested in government, particularly in voting. The reasoning seems to be that government isn't interesting because it doesn't directly effect you. Yet, it clearly does effect all of us in the tech. community as this example clearly shows.
What this is, is corporatism. Dwight Eisenhower warned of this when he warned of the rise of the "military industrial complex." Folks, this is it.
There is no reason for the current sorry state of IP in the USA, other than this is what the corporations want. They bought seats in congress, and grateful representatives (I use that in the loosest possible way, because it's the corporations who bought the seat that is being represented, not the voters) enacted the laws that the corporations wanted.
That's how we got software patents. The whole concept of software patents goes against the patent system. The idea was to patent real, physical things -- products and machines. Until software patents, you couldn't patent ideas. The reason behind patents is to encourage R&D of new and innovative products - to give the inventor improved prospects of being able to recover the R&D costs, which in turn encourages further R&D. This was when developing a new widget could take years of work. Not the few hours that developing a triply linked list did -- it only took me a couple of days to develop my six pointer linked list to compete with a b-tree (hey, it got me out of the exam so don't knock it).
If you think this patent is a scam, you are right. It's a scam that we not only allowed, but encouraged. Because we, as a group, aren't really engaged in the political scene. Because we seem to think that it doesn't matter, when clearly it does matter a great deal.
There's no method shown, just a description of what the effect is.
Taking a double linked list, the effect is:
there is one list where you can scan linearly forwards (in ascending order, for example). there is one list (separate pointers) where you can scan linearly (in descending order, for example).
That the links are kept with the nodes is an implementation detail (which doesn't affect the effect) and the patent doesn't HAVE implementation details, so it cannot matter as to whether the implementation of doubly-linked lists infringes the patent or not.
Ergo, it must be prior art: you cannot patent something that covers a product that existed more than a year before filing.
Punch cards? Jeez you kids are spoiled.
... And the sparks! Why back on February 12, -20,000,018, we lost 7 office huts in one week to fires!
In my day, we had to use Punch Stone Tablets and Chisels. Coding was really slow because it was hard to punch holes through the stone without breaking the tablets. And you want to talk blisters?
Back in the day, programming Real Mens's Work(tm). Well, except for Ethyl and Tessie, but we were never sure about them
On Mac, only windows deemed worth of having a maximize feature have one. On PCs, only windows deemed not worthy of having a maximize feature don't have one. Clearly, PCs offer more flexibility in this regard; you do not *have* to click the maximize button on any given PC window; whereas you *can't* click it on many Mac windows.
Any window with a scrollbar in it is worth maximizing as far as I'm concerned.
This is Inter-format-ful
All you who state there is ample prior art for this, you are absolutely correct. This arrangement exists in several data structures text books. In fact this is a prime example. I'm stunned that this ever got through, though I shouldn't be so surprised anymore.
IANAL... But I play one on
Doesn't Donald Knuth have the patent on those?
"I'm a Laver, not a Phyto[plankton]"
Call me crazy, but I prefer that an OS gives you at least the option to change things so they work the way you want them; default behaviour should be chosen wisely, as well, but should not be the only choice. Or maybe I'm just spoiled by KDE, I don't know...
if you're so upset give him a call, from the uspto.gov web site: 571.272.4107
For all my school work in the late 1970's and early 1980's using linked lists? And doubly-linked lists?
I'd like it in silver dollars, please.
-- Tigger warning: This post may contain tiggers! --
someone needs to watch the matrix again...
I think the only solution to stupid patents like this will be repeated class-action lawsuits against the USPTO for utter failure to do their job. Then they can go back and sue the stupid patent lawyers that didn't do their job.
The failure is in the system, not the stupid schmucks that try to patent simple things that have been around for ever. Fighting the individual applicants or patents will go on forever and get us nowhere. The USPTO has to be fixed or nothing will ever change.
What probably happened, is this guy came up with a method of implementing a novel data structure. He wrote it in a notebook along with various other things he invented.
Then lawyers etc. distill those inventions down to patent-speak, which tend to be rather general, and describe the operation of an invention in somewhat general terms-- you need wiggle room to allow for small variations in implementation (e.g. if it was a machine you would say "a rod connects a gear", not "a 3cm diameter brass rod connects a 10cm diameter steel gear", just in case you need to adjust the details like dimension and materials").
Especially where software is concerned, they tend to go overboard. This is partly due to the nature of software, which is to take pretty abstract ideas and implement them using a ridiculously baroque combination of a zillion weird details.
So the defining characteristic of Mac vs Windows has come down to if there is a Maximize button or not? Good luck getting many people to switch if that's the case . . .
:).
If there had been some other benefits I certainly would have liked to have tried it. Guess I'll just stick with Linux since it has lots of advantages over Windows AND (usually, depending on wm) a maximize button
"People who think they know everything are very annoying to those of us who do."-Mark Twain
Why can't these computer people stop infringing on our patents? http://www.patentstorm.us/patents/5905990.html >"A computer file system, particularly adapted to UNIX operating systems, for transparently allowing access to and modification of >snapshot objects, i.e., files, directories, and symbolic links. The file system creates a mountpoint directory and dynamically >searches the computer system to find a requested file object, manifesting a representation of the requested file object in the >mountpoint directory if it is found. If an earlier representation of the requested file object already exists (in the mountpoint >directory), then any further requests for the file object are directed to the earlier representation. Searching can be performed >along a viewpath having two or more independent search paths, including those based on an object name, or based on an object name >extension. The binding file translation is done entirely within the kernel to speed up processing, as well as minimize the overhead >required to establish mountpoints across different machines. "
Flamebait? The mods are fucking mac apologists huh? Get over it. The original poster are bashing other computer users because they have a MAXIMIZE button and you mod this flamebait because he's saying the truth.
REPEAT AFTER ME:
It's JUST a computer. It's just a music player. It's just a company.
Mac users are a salesman's wet dream.
O.K. I'm patenting a method to cirulate air within an organism allowing metabolism and continued homeostasis. And I'm gonna hold my breath 'til they grant it!
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.
It is not the first and probably won't be the last patent describing some trivial use of linked lists (TFP actually lists at least four other patents featuring linked lists).
What really amazes me is the name of the patent: "Linked list" (!)
. . . linked lists patent you.
I'm guessing that you are trying to be funny, but I wrote linked lists before I ever got to college, and CS freshmen in a halfway-decent curriculum are writing linked lists by the end of their freshman year (though not necessarily their first semester). Come to think of it, I had to write a binary tree made of structs containing 3 pointers in High School- so I would have been annoyed by this patent back then as well.
You are reading a copy of my copyrighted post.
...the purpose for which I can only fathom.
Times like this, you have to be pretty glad Slashcode didn't include a Clippy-style input assistant:
It looks like you're trying to inflate your appearance of sophistication by substituting a more impressive-sounding word for "guess". Did you mean "speculate"?
[Yes] [No] [Cancel]
SIERRA TANGO FOXTROT UNIFORM
"We should also give praise to the extensive patent review performed by Cochran Freund & Young LLP."
Cochran Freund & Young LLP is the inventor's law firm, not the examiner. The inventor's attorney is not responsible for examining the patent but rather for representing the inventor in the prosecution of the patent application. The examination is handled by government employees, in this case employees of the United States Trademark and Patent Office, and are known as patent examiners; their name or names are listed next to the word "Examiner" on the front matter of the published patent.
Also, the poster referenced the application number rather than the patent number which is more appropriate since the patent has been allowed.
You mean like a B-Tree with a parent back-link for reverse traversal (available just about everywhere programs are written)? Or a 3-D data cube structured as a sextuple link to allow back and forward traversal in any of the 3 dimensions? I believe the early 3-D spreadsheets like QubeCalc used this type of structure.
Once you've done it in 1,2 and 3 dimensions, there's no justification for issuing a patent for n-dimensional generalization. Unless there is something novel in the way the data structure is being used (i.e., he is patenting a combination of data structure + algorithm), the feds should sue this guy. There is so much prior art that is so widely available for this that it's a complete failure of his obligations under the patent application process to disclose prior art.
We are the 198 proof..
Well, they needed proof positive that the current patent system is useless -- causing more harm than good. I must admit that I'm a bit shocked to see that it has regressed so far as to allow someone to patent something that will infringe on a huge majority of currently existing and new software like this though. Frankly, this is proof that even the "prior art" argument that kept the patent system from going quite too far (though still allowing quite a bit that should not be allowed) is not enough to save it at all anymore.
I think I'll patent the Sun. Anyone who wishes to use it must pay me to do so.
Well, I guess it does no good to complain about the fact that this has screwed us all. Rather I should be asking, just what is the extent of the damage? Now that such a fundamental part of programming has been patented -- something which they know many programs will likely require as there aren't really viable alternatives for many purposes (and which can be massively inefficient anyway) -- how much is this going to screw up future programs?
FORTRAN: You get your work done. Your foot remains fine and there is no multiple personality disorder.
"Those who don't believe in magic will never find it." - Roald Dahl
This really is best piece I've ever found on the patents lunacy: http://philsalin.com/patents.html
Hey, go easy on them. I only got modded flamebait because I made a parallel between Mac users and religious zealots.
That was very mean to the religious zealots.
110100 1101000 1101000 1100110 0 1101111 1101000 1100011 1
All true, but then, Windows doesn't give you a way to zoom a window to an appropriate size. You have to grab the tiny (tinier than a Mac's, even!) handle on the corner of the window, etc.
FWIW, I believe the zoom button in Excel does, in fact, blow up the window to fill the screen. In Photoshop, I just hit the "F" key or click the fullscreen button in the palette.
comma
See my linked lists of triads:
http://www.kurtz-fernhout.com/pointrel/
http://pointrel.sourceforge.net/
SourceForge downloads going back to at least 2001:
http://sourceforge.net/projects/pointrel/
My own work on it goes back about thirty years.
You can think of a triad a like a relationship for an object A with an attribute B and a value C.
One of the reasons I first decided to put it on SourceForge was in case someone later tried to patent the idea. Glad I did.
Essentially, and while there are variants of this, for speedy lookup of triads, I have data items which link via extra pointers. So, for example, for the triad A, B, C, there is the record structure:
Triad# A B C PreviousA PreviousB PreviousC LastA LastB LastC
To, if you have a triad number, you can fetch the last user of that triad, and then work back from there to find all the triads which contain that object in the A, B, or C slot. These links are all built or updated as new triads are added.
I have other variants of this as well -- quads where the first item represents a "space" of triads (though you can easily generalize this to arbitrary length tuples). And most recently where each object reference is two parts defining a Unicode name for a space and a binary string of data to be interpreted in the context of the standard for that space. This is a little like RDF and namespaces.
A 21st century issue: the irony of technologies of abundance in the hands of those still thinking in terms of scarcity.
The following hyperlink shows a program source code that was part of the Decsysten-20 Pascal compiler suite which was distributed by the Digital Equipment Corporation Users Society as Decus 20-0003. That program is a Pascal debugger, written in Pascal, written in 1975, and uses both single and double-linked lists. Linked lists are also used in the source code listing shown in the following link of the Decus Decsystem 20/PDP 10 Pascal Compiler, written in December, 1974, and part of the same distribution.
I knew this technique was old, I didn't realize it's more than 32 years old! And that's just what can be proved; it might be even older.
The lessons of history teach us - if they teach us anything - that nobody learns the lessons that history teaches us.
The usual patent structure looks like this
- Abstract: a general description of what it's about.
- Claim 1: Existence of roundness
- Claim 2: The aforementioned roundness being attached to a device made of various materials
- Claim 3: Vulcanization of Rubber as a technique for specific materials production
- Claim 4: A specific configuration of vulcanized rubber applied in a configuration of roundness as illustrated in Figure 12, below,
- Claim 5: PROFIT!!! (Sorry, had to say that here
:-) - really only applies to Business Model patents. - Description: Some text in something resembling English about what's really been done here.
The standard way to misread this is to look at the abstract or first couple of claims and post to Slashdot that Oh, no, he's actually patented the wheel! when in fact the patent is really about some particular water-repelling tread design down in Claim 4.On the other hand, the standard way to abuse such a patent, especially a business method patent, is to get the patent issued because the tread design in Claim 4 was actual valuable and novel work, and then threaten to sue anybody who violated Claims 2 and 5 by using a wheel in a profit-making transportation business. Sharks especially like this technique when the claims sound confusing and technical and it's not obvious to a typical court that the claims they're basing the suit on are the parts that *are* obvious to anyone skilled in the trade.
In this case, though, I don't think there's anything left out of most of the rants - the claims appear to describe storing a bunch of data, using a linked list to access the data in one order, and using a second linked list to access the data in a different order, and really not much else. Sure, it's patenting the data set with two linked lists instead of just a data set with one linked list, but that's still well covered in Computer Science 202, if not necessarily CS101.
Bill Stewart
New Fast-Compression-only CPR http://preview.tinyurl.com/dy575ks
Computer Science, An Overview. 2nd Ed., J Glenn Brookshear, published 1988.
Section 7-2, p.283. Linked Links.
TFOAE
Why are idiots running the patent desk? Someone didn't do their job. Fire them!
Here are some sample questions.
What percent of software patents applications are eventually granted?
How many examiners have to approve each patent before it is granted?
If a patent is rejected, modified, and resubmitted, does the same examiner review it?
Do the submitters know who you are?
What are some of the patents that you approved?
What are some that you rejected?
Is there a file or data base of rejected US patent submissions?
Is there a file or data base of submissions rejected by other countries?
Do the examiners search them?
Can the public search them?
Are you allowed to take into account a submitters prior history of questionable submissions?
I have not read the patent or the link. But even from the slashdot article it is clear that the invention is not about classical linked lists.
If you have a linked list, but need some other "order" in the list, you can add a second pointer along that other "order". For example, if you have records that you can order by "name" or "employee number", you can use a "next_by_name" and a "next_by_Enumber" pointer.
Slightly more messy when you add/delete an item on the list, but speeds up things if you have to walk the list along both orders regularly....
Now the reason that I need only a few words in the abstract to understand what this is all about is that I used this technique as a student in a lab assignment back in '86.
(i.e. a reasonably competent engineer given the same problem to solve would likely find the same solution. If that's the case, the solution is not innovative, and the patent should be denied.)
I'll answer what I think I can :).
I am not sure on the percentage of applications granted, but if you take into account that the applications are in the 10M range and that patent grants are in the 7M, I guess that would be your answer. However, I don't think this is necessarily true (that 70% of applications are accepted). Definitely not in their original form, variances of claims may eventually make this percentage true (just to have something patented, a 100 claim application might be dropped to one that no one will further argue). My guess is that a renumbering occured somewhere, and that's why it appears 70% make it.
Being that I'm 4 years out, some of the processes elude me, but I believe it if you are a junior examiner, your approval and a senior examiner's approval are all that is needed to grant. I do think that they go through a couple of audit boards, and perhaps randomly get chosen for a re-examination, but beyond that I don't think a lot happens once it leaves the junior/senior examiners.
If the examiner is still available, anything having to do with the case is still owned by him. Rejection, modification, resubmission, all are handled by the same examiner, because it would be a 'waste' of other peoples time to have to read the case, search prior art, etc.
Submitters are aware of who is examining their patents.
I approved no patents. It is actually "surprisingly" made difficult to approve a patent. It is more worth your time to just reject everything. Everytime a case like this is shown in the media I am surprised that it makes it out, because as a junior examiner your work is very scrutinized. It more likely was a senior examiner who had to make his quota, left this case up in his rafters for too long, gave it a really crappy prior art search and said it was patentable.
I rejected things like the 3D web-browser, multiple store-front GUIs, some educational GUI's, and a bunch of other stuff. Nothing amazing. I did like doing searches on weird patent apps though.
There is a database containing ALL patent applications (however I think only back to a certain app #, before that the database did not exist). You can have flags just like other popular searches on whether an app was accepted, rejected, etc. The database is combined with Japan's and Europe's, but those are hard to match up due to language differences.
I don't believe they are publicly searchable. I know the USPTO maintains a website of accepted patents, perhaps they do of applications, I haven't bothered to look.
With that searchable database, you could look up the prior history of cases, but you're supposed to give each one the same fair shake. When you are given your docket of applications for the time period you're working, they try to give you all cases that are related, or you are encouraged to go find related applications to do at the same time, so that you don't waste your/another examiner's time.
OMG I am so sorry, I thought that the post was formatted as I typed, but I guess not, probably what the freakin preview button is for, let me repost here: I'll answer what I think I can :).
I am not sure on the percentage of applications granted, but if you take into account that the applications are in the 10M range and that patent grants are in the 7M, I guess that would be your answer. However, I don't think this is necessarily true (that 70% of applications are accepted). Definitely not in their original form, variances of claims may eventually make this percentage true (just to have something patented, a 100 claim application might be dropped to one that no one will further argue). My guess is that a renumbering occured somewhere, and that's why it appears 70% make it.
Being that I'm 4 years out, some of the processes elude me, but I believe it if you are a junior examiner, your approval and a senior examiner's approval are all that is needed to grant. I do think that they go through a couple of audit boards, and perhaps randomly get chosen for a re-examination, but beyond that I don't think a lot happens once it leaves the junior/senior examiners.
If the examiner is still available, anything having to do with the case is still owned by him. Rejection, modification, resubmission, all are handled by the same examiner, because it would be a 'waste' of other peoples time to have to read the case, search prior art, etc.
Submitters are aware of who is examining their patents.
I approved no patents. It is actually "surprisingly" made difficult to approve a patent. It is more worth your time to just reject everything. Everytime a case like this is shown in the media I am surprised that it makes it out, because as a junior examiner your work is very scrutinized. It more likely was a senior examiner who had to make his quota, left this case up in his rafters for too long, gave it a really crappy prior art search and said it was patentable.
I rejected things like the 3D web-browser, multiple store-front GUIs, some educational GUI's, and a bunch of other stuff. Nothing amazing. I did like doing searches on weird patent apps though.
There is a database containing ALL patent applications (however I think only back to a certain app #, before that the database did not exist). You can have flags just like other popular searches on whether an app was accepted, rejected, etc.
The database is combined with Japan's and Europe's, but those are hard to match up due to language differences.
I don't believe they are publicly searchable. I know the USPTO maintains a website of accepted patents, perhaps they do of applications, I haven't bothered to look.
With that searchable database, you could look up the prior history of cases, but you're supposed to give each one the same fair shake. When you are given your docket of applications for the time period you're working, they try to give you all cases that are related, or you are encouraged to go find related applications to do at the same time, so that you don't waste your/another examiner's time.
Fullscreen apps: Browser, Office App, and basically nothing else.
In Windows, the FTP client is an explorer window; you just drag from one to another. No need to maximize. iTunes needs to be maximized, but only because its fur is matted with UI clutter compared to a small-window player like Winamp. Text editors don't generally need put in fullscreen, but sometimes it helps to be able to get there so you can overview a large chunk of code.
A good website will scale to whatever size your browser will, within limits. That said, how many 'good' websites are out there? Five? The rest expect you to browse at FS at a resolution of at least 1024x768.
Flaming, by the way, would be if I started throwing out insults. I know the religious community is deeply offended by my comments likening them to Mac zealots, but the parallel exists. I just pointed it out.
110100 1101000 1101000 1100110 0 1101111 1101000 1100011 1
The patent was issued in April. Did it issue on April first, on internet cleaning day?
"Apparently you're an illiterate clod.
I did say that clean water wouldn't help you if you're already sick."
Touche my good man. Now if you'll kindly quote where I claimed you DID say that, I'll kindly apologize.
OH WAIT I DIDN'T. Physician, heal thyself and LEARN TO FUCKING READ before you decide to run off about others not being able to read. I guess my previous suggestion was above your head. God damn bitch, how could you give me so much ammunition? What the fuck is wrong with you? Aside from being an imbecile I mean?
And you made it so easy by being SO stupid too. I'm all aglow with satisfaction at S-ing You TFU.
As an aside, how does it feel to get owned? I'd like to know really, and since I just did it to you, I figure you're finally able to talk about something you really do understand.
I never claimed you claimed that. (Rinse, repeat.)
This is fun, isn't it?
Now, since you didn't claim that I said that, and I didn't claim that you claimed I said that (although your flaming has been of nothing more than that), where exactly are we at?
Owned? What does that mean? Is that where you jump up and down, screaming and throwing your own shit all over like an uncivilized fucktard until you slip, fall and crack your head open? Man, you really pwned me. And it's totally righteous.
Or were you trying to split hairs between "sick" and "infected"? Yeah. I get it now. You are SO right. I'm such an imbecile. Even though the original message I replied to had to do with having a "soar throat", which is a sickness, not necessarily an infection.
Go another round?
[Y/N] >
Please wait for just a bit to get any more attention for this, at least until I finish the patent applications for math in bases of powers of two, two's-complement math, overflow, underflow, context switching, mutexes (aka muticies ;-), dirty bits, and garbage collecting.
btw, I'm still a little miffed that some beaux eaux in Washington state beat me to patenting the general protection fault, although they clearly put an immense amount of work into furthering its development.
Don't tell anyone, but tomorrow I'm going to copyright all terms ending in "-oriented".
-- Mr. Creative
"You know democracy is broken when you can't guarantee your candidate will get elected."
"Life would have been different if the Supreme Court had ruled in favor of Gore, thus throwing out Florida's votes and using only the electoral votes of the other 49 states. But nooooooo . . . , they had to use them from all 50. Oh, those right wing fanatics!"