Linked list patent

http://www.google.com/patents?id=Szh4AAAAEBAJ&printsec=abstract

by tlrobinson • 16 years ago

117 75 16 years ago

google.com

colinprince• 16 years ago

My first reaction is, oh no, Google has patented the linked list, forsooth.

Instead, it's a company called LSI Logic Corporation.

fnid212• 16 years ago

Every time the patent debate comes up, someone links to this patent as the summit of absurdity. Why not link to this one: http://www.freepatentsonline.com/6368227.pdf

It's just as absurd as lots of software patents -- that doesn't mean all software patents are absurd. Some are genuinely novel, unobvious, and valuable.

I still don't understand why someone could patent a physical machine that computes instructions, but not software that does the same thing.

It seems like we are throwing the baby out with the bath water. I know patents cause trouble, but what about the case where a patent helps an entrepreneur get the value out of an invention when big corporations steal it, market it, and make money without giving the inventor a dime?

There's good and there's bad, but it seems like around here there's only mud slung at software patents. Some inventors of software algorithms are every bit as clever as inventors of anything else that may get patented. Why shouldn't they be treated the same under the law?

Equal rights under the law. That's the way it should be.

nkassis• 16 years ago

This one is even cooler, patenting patent trolling:

http://appft1.uspto.gov/netacgi/nph-Parser?Sect1=PTO2&Se...

fnid212• 16 years ago

Absurdity is ubiquitous. Computer science is no exception. I know we think we are above it, but we aren't. We're just like everyone else. People don't have to be mechanical engineers to pattent something physical. They don't have to be computer scientists to patent an algorithm either.

Maybe that person who patented the method of swinging really thought the idea was great and could save the world. I don't know. But really, patenting inventions is almost a right.

We argue for copyright protection, or the abolishment of it in the same mind. If there are no patents for software and no copyrights period, what is there to protect the risk innovators take to make the world better?

It's true of corporations as well, because they spend a lot of money on Research and Developmennt. R&D budgets are in the billions. If a company, like Apple in the current debate, can't protect that investment, a lot of people who participate at Hacker News wouldn't have jobs. They'd have to go do something in some mundane role that has negligible impact compared to something, like the iPhone.

We all cheered when it arrived and now that Steve Jobs wants to get his money for it, his investors money for it, and his employees satisfaction for a job well done, he has to fight for that value.

If, in fact, HTC did steal some ideas from the iPhone, why shouldn't Apple get compensated for the lost value? Those are phones Apple could have sold and why shouldn't Apple have every bit as much right to make a positive return on their investment in the R&D for the iPhone and the parts of the iPhone that make it special to Apple, to Jobs, and for consumers?

clofresh• 16 years ago

Assignee Name and Address: Halliburton Energy Services Inc.

Wow, Halliburton is just synonymous with evil.

jcromartie• 16 years ago

I can hardly believe that this exists... but there it is. I think this is the only evidence needed to establish the fact that our patent system is hopelessly and irreparably broken.

ebneter• 16 years ago

That's an application, though, not a patent.

runT1ME• 16 years ago

Do you think you should be able to patent a sentence? Even if its a good one? If not, why?

fnid212• 16 years ago

It depends on the sentence. And I know where you are going.

timtadh• 16 years ago

patents apply only to things that are: anything made by man new non-obvious commercially useful

i think a sentence, even Shakespeare, fail one or more of those qualifications. which is why we have copyright for sentences.

tlrobinson2• 16 years ago

True, it doesn't mean all software patents are absurd, but it does mean something is wrong with the system.

baddox2• 16 years ago

These two patents don't mean that all software patents are absurb, but it means that the current notion of software patents itself is absurd.

fnid212• 16 years ago

No, I don't think it does and I don't think simply stating that it is without providing any evidence for your case is going to change my mind or anyone's mind who agrees with me, but it looks like I'm the only one. Anyway....

The legal system is there to figure out if a patent is absurd and if you read the whole patent for the swing, at the end, it was ruled out. At least claims A, B, C and D. That same review process exists for software patents too. The patent office is taking steps to fix some of the problems, at least it is being pragmatic about pre-approval review processes that still protect the inventor.

Lots of arguments all the way to the echelon of the judicial system have taken place over software patents and it was ruled they are valid, so if a claim is to be made that they should be abolished -- it better be a very good one.

alanthonyc• 16 years ago

Perhaps you can provide a counter example that shows the usefulness of software patents.

I personally think they are absurd, as demonstrated by the OP, but am open to changing my thinking if proven wrong.

The internet has leveled the playing field for everyone. But one of the few ways that big corporations can take advantage of their size against smaller, more innovative entities is by throwing money into a legal battle which the smaller entity can't afford to fight.

Equal rights under the law. But currently, the more money you have, the equaler you get.

fnid212• 16 years ago

Okay, then the problem is not software patents, or patents in general, but that they unfairly tip the scales in favor of the big corporations.

How do we fix that problem? That problem exists outside the world of patents and software. Monsanto patents seeds and those are just strings of DNA which are essentially just four characters repeated in a seemingly random order. And yet farmers lose their farms over those strings of four letters. Not because they were even choosing to use the seeds, corn is just pollinated by the air and some of that code got into their crop as it blew in from the neighbors' field -- a farmer who did use Monsanto's DNA. It's absurd, I know.

One case on the not absurd side of the spectrum, is, as it turns out, the original case that ruled software could be patented in the first place. It was by a guy who had to fight, iirc, all the way to the supreme court to protect his right to patent his software invention. I'll try to find a link, but is a true story indeed.

kmavm• 16 years ago

When working correctly, patents allow information that would be a corporate secret to be more openly disclosed. In my career, I've been able to discuss technical details more frankly in blog posts and academic publications because we know that our large, well-funded competitors would not be able to abuse that disclosure to harm our business.

The public good here is hard to measure from the other side, as a reader of those blog posts and papers; if it were not for IP protection, I would not willingly endanger my job or business to discuss the technology so openly.

anamax2• 16 years ago

> Perhaps you can provide a counter example that shows the usefulness of software patents.

There are some interesting optimization methods that probably wouldn't have been made public if it weren't for patents.

I want all useful algorithms to become publically known. Patents help accomplish that.

How do you propose to get people to forego trade secret protection?

GrandMasterBirt• 16 years ago

For example: I come up with a system where basically I define 1 xml file which is then read by 3 different mechanisms to generate the m/v/c of a web application. the definition significantly saves times on web development when using the system.

Now look the argument is "oh its just a few algorithms used in a certain way, that should not be patented". however how is that any different than creating a ammo holder for .45mm bullets which can be put into any gun that can use .45mm bullets? Its just taking some metal and springs and putting them together in some novel way which has not yet been done before.

Remember once you see the invention that is TRULY innovative AND simple but nobody quite thought of using it that way before, it becomes a no-brainer. You start to think "yea given a few hrs I can make one of these myself without any special training or anything, without even looking at schematics, or even taking the one I have apart" but the fact is that nobody thought of it before.

The fact is, it was mentioned in a '96 letter, we must decide what part of programming is the "words" and what part is the "innovation" so that people can't do the equivalent of copyrighting words, but they can copyright books (the end product). (yes I am aware that patent != copyright, but try to see the analogy)

nostrademons3• 16 years ago

"I know patents cause trouble, but what about the case where a patent helps an entrepreneur get the value out of an invention when big corporations steal it, market it, and make money without giving the inventor a dime?"

Patents don't protect against that. Problem is, filing a patent takes time, money, and attention that are in very short supply in a startup. You can file to protect your inventions - but if you do, that takes time away from more important things like getting the money you need to stay in business. And patents generally need to be filed before the invention becomes public (you have a year grace period in the U.S, but no such boon in the EU). If you gate your launch process on the speed of the patent process, you won't be launching much.

That's why Google's first patent wasn't filed until 2003 (http://www.google.com/patents?vid=USPAT6526440 - the PageRank patent is actually owned by Stanford, since they were Page & Brin's employers when it was invented). And many of the initial EBay inventions - online auctions and reputation, for example - were never patented, because the 1 year grace period had expired by the time they got around to it. Patents are something you get once you become big and have extra money lying around, not something you can afford as a startup.

fnid212• 16 years ago

I don't think that is exactly true. A good patent from a very good firm in L.A. will run you about $20k. Yes, it's a lot, but I a computer engineer could sock that much away in a year. Work on the software at home at night, patent it, sell the patent to Apple or Microsoft or another big company for a couple million dollars. The corporation makes $100 Million of the device. Great, the inventor got $2M and can innovate for the rest of his or her life.

That's a good story in my opinion. Is that any better or worse than a social media site that gets 1,000,000 users and sells itself to google or whatever? How is that better?

Seriously, and with all due respect, a lot of the social media sites that do that add little value to anyone but the investors. Sometimes they take money from their customers in nefarious ways that maybe the world would be better off without -- especially right now.

So I'm a staunch supporter of software patents, because I see them as a path to freedom and a mechanism to publish ideas into the population and allow them to be built upon and improve the quality of life in the world.

I think the world could use a little improvement in its quality right now. There are probably millions of people who will agree with me.

When it comes down to it -- you gotta make money. That's what it comes down to and patents, any kind of patent, whether it is for wind shield wipers or for a software revolutionizes the solar energy system.

If something like that saves the world, I don't see a problem with an inventor getting a little bling out of it.

When it comes down to it, I just don't see the difference between gears spinning in the real world and gears spinning in a 3d model. That's every bit as much software as the algorithms and hardware behind some of what the iPhone does.

Some little company patented a film that goes over glass to make it much much stronger, but still transparent with UV protection and over a decade later, a car company used that material in its windshields without ever compensating this small individual owned business. It just turned out that when the material was invented, there was no market for it. No one could figure out what to do with it.

But it was within the 20 year period for the invention, which is essentially an arrangement of atoms in space, which could all be described by software. But I digress.

scotty79• 16 years ago

Wow. That method of swinging on the swing actually is innovative. At least for me. I never did that by pulling one chain and the the other. I always sort of balanced my whole body to start and keep swinging.

I'm eager to try this new method. Should I apply for some kind of licence to that guy? I don't live in US is that patent valid in other countries?

huhtenberg• 16 years ago

> Why not link to this one: http://www.freepatentsonline.com/6368227.pdf

This is a mock patent. It was obtained by an IP lawyer for the exact purpose of demonstrating the absurdity of the state of the patent system in the US.

The legal counsel person in one my previous companies was a close friend of this patent author. That's why I know.

nandemo• 16 years ago

Well, yes, of course it is a mock patent. The point is that it was even accepted in the first place.

lutorm5• 16 years ago

Do you think mathematicians should be able to patent formulas too? Some are novel, unobvious and valuable.

The argument, I believe, is that formulas aren't invented, they're discovered. That's why I think it's totally, unequivocally absurd that you can patent genomes. Who invented the human (or any other naturally occurring life form's) genome?

Just because something's not obvious or novel doesn't mean you can patent it. You can't patent music or poetry, no matter how obvious, novel or valuable it is.

At least this example is an implementation detail. That seems more reasonable to me than, for example, UI patents. If someone patents a way to make steel, you are free to make steel any other way you can figure out. The same seems to apply with the implementation detail patents, but with the "multitouch" patent Apple's suing over, it seems that the question of how HTC has implemented the functionality doesn't matter because the patent covers the user interaction. And that makes no sense to me. If it's so genuinely difficult to make, then they can patent the implementation. But patents were meant to cover "the process P which accomplishes B from A", not "any means of accomplishing B starting with A even if totally unrelated to P."

fnid212• 16 years ago

I've heard the discovery vs. invention argument, and there is something too it, but personally, I'm still not clear on how to distinguish between invention and discovery. Wasn't steel a discovery, elements, or quantum theory?

Music and poetry are covered by copyright, currently. But the same problem exists there and Larry Lessig has done a lot to protect culture in an environment of copyright litigation.

Re: Mathematics and formulas. A lot of the discoveries or inventions in mathematics are patented. Three dimensional protein folding is a huge industry in pharmaceuticals and math is almost 100% of that knowledge. It's applied math, but nonetheless, still patentable mathematics and a lot of it too.

I think one differentiator here is that the multi-touch and the one click amazon patent as another example are something that seems obvious to try to achieve given the current environment. There are other ways as well, like a space elevator or gloves to help protect astronauts in space.

Is math a fact? I don't know if facts can be patented or copyrighted, though collections of facts surely can.

bartl2• 16 years ago

I think your assertion of patenting a way to do something vs. just patenting doing something is really the core of the problem.

jfoutz3• 16 years ago

The problem isn't "is it a good idea?"

The problem is, "Is math part of the structure of the universe?" Is pi a discovery that is fundamental to the existence of reality, or is it just a useful shorthand for thinking about things we don't understand?

If math is discovered, and algorithms are math, then algorithms can't be patented. You may reject the notion that math is discovered, or that algorithms are math, I disagree.

I'm fine with patenting a specific sequence of instructions on a particular chip, because they're extra fast or something. that's an invention.

You can't patent an electron, or the idea of an electron. You can patent a device for moving an electron around.

lutorm5• 16 years ago

By the way, you forget that the purpose of patents is not to allow you to get rich, it is to "promote the Progress of Science and useful Arts". The relevant question is if you think progress of science is promoted by the current system, or if progress is hampered because software patent litigation puts a damper on it?

The multitouch patent, for example: Do you think Apple wouldn't have bothered with the iPhone if they couldn't patent their "invention" (which wasn't theirs either, but that's a different issue)? In that case, the patent has promoted progress. But it's sure standing in the way for ubiquitous competition and rollout of touch devices now.

dutchflyboy• 16 years ago

Well, actually the purpose of patents IS to allow you to get rich. Why? Well, by protecting the invention, you allow the inventor to make money with it for some time. This means that if you put millions in R&D, you have a guarantee that if there's a result, you can also win back the investment. Do you really think pharmaceutical companies would pour so much money into research if whatever they invented was immediatly copied by another company which doesn't put any money in R&D.

But I agree that patents are sometimes absurd, software patents are quite absurd most of the time.

stonemetal• 16 years ago

When did anyone bring up inventors? It would be nice if they had rights, under the current system there is no inventor protection. Any idiot who can imagine something can get a patent, and then turn around and sue the hard working engineer who puts together a practical product.

dbz• 16 years ago

Nah. This is easy to beat. Hang the swing set from anything besides a horizontal tree branch.

swixmix• 16 years ago

The patent was canceled according to page 8.

The patent system worked in this case.

philwelch• 16 years ago

Duplicate: http://news.ycombinator.com/item?id=1165089

tlrobinson2• 16 years ago

Oops. I saw it on Twitter (likely by someone who saw it here or on Reddit...) and posted it not knowing it was already posted. Sorry.

lutorm5• 16 years ago

To be fair, it's not just a linked list. It's a triply linked list. Must be at least 3 times as hard to figure out as a singly linked one...

kiba• 16 years ago

In the interest of advancing the level of debate regarding intellectual property, once again as countless time before, I beg everyone to read Against Intellectual Monopoly at http://levine.sscnet.ucla.edu/general/intellectual/againstfi...

It is common to argue that intellectual property in the form of copyright and patent is necessary for the innovation and creation of ideas and inventions such as machines, drugs, computer software, books, music, literature and movies. In fact intellectual property is a government grant of a costly and dangerous private monopoly over ideas. We show through theory and example that intellectual monopoly is not necessary for innovation and as a practical matter is damaging to growth, prosperity and liberty. -- David K. Levine and Michelle Boldrin in Against Intellectual Monopoly

This book has absolutely change my thought about how economic progress are made, who is the real good guys and bad guys of civilization, and everything else. I never quite look at innovation and entrepreneurs quite the same way ever again.

Please, everyone, read it. It's free to download!

Estragon• 16 years ago

I haven't read the book, but the interview with the author on Econtalk was great: http://www.econtalk.org/archives/2009/05/boldrin_on_inte.htm...

jacoblyles• 16 years ago

I love Econ Talk but I haven't listened to that episode yet. Thanks for the pointer!

bediger• 16 years ago

Oh no! Now that I've read the patent all the software I've written that uses linked lists (and that's rather a lot) is now in violation of the patent, and I'm liable for treble damages, right?

Damn you, Hacker News!

anigbrowl• 16 years ago

Ridiculous. I have books older than that patent application containing the same diagrams, and so do most programmers.

char• 16 years ago

I'm really too tired to read this, but is someone seriously trying to patent a linked list? This is really a "palm to the forehead" moment for me.

bartl2• 16 years ago

"Trying"?

>Date of Patent: Apr. 11, 2006

kelnos• 16 years ago

It's not exactly what you'd think when someone says "linked list." The "next" pointers are there, but there's also an "aux" pointer that the patent suggests can point to any other element in the list, not just next or previous, and can be used for any purpose to form any kind of sequence desired.

I think it's "new" and "novel" because really there's no use for it.

(Ok, I jest... I expended barely 30 seconds worth of thought and couldn't come up with anything. Maybe there is a use for it, but the patent's still pretty lame.)

mone• 16 years ago

Not patenting a linked list, but an enhancement to it, as a reader suggests. Not that the idea is bad, but doesn't seem ingenious enough to be patentable. Node(Value, Node next, Node auxNext, ...) is just unnecessary complication of the simple concept of a linked list, and seems useful only for very specialized needs.

daveungerer• 16 years ago

Just to be clear, this is not a patent on a plain vanilla linked list. It's a patent on a linked list where each node in the list has 1 or more extra next pointers, to facilitate different orderings.

Now, if the US is serious about innovation and economic recovery, they will employ software patent evaluators who are actually aware of the state of the art in software engineering / computer science and who can judge the obviousness of an invention. Their failure to do so has resulted in a lot of extra friction that prevents economic growth. Every frivolous patent suit filed, every agreement to give in and pay up, is another bit of economic growth lost to friction.

Good luck with the recession.

GFischer• 16 years ago

Amen to that. I love your analogy, I've always thought of the government as "friction"

arethuza• 16 years ago

The only "novel" part of this appears to be the use of the aux pointer to make navigation more efficient in some circumstances.

Which sounds awfully like skip lists to me:

http://en.wikipedia.org/wiki/Skip_list

Linked list patent

Related Stories