USPTO Grants Google a Patent On MapReduce

theodp writes "Two years ago, David DeWitt and Michael Stonebraker deemed MapReduce a major step backwards (here are the original paper and a defense of it) that 'represents a specific implementation of well known techniques developed nearly 25 years ago.' A year later, the pair teamed up with other academics and eBay to slam MapReduce again. But the very public complaints didn't stop Google from demanding a patent for MapReduce; nor did it stop the USPTO from granting Google's request (after four rejections). On Tuesday, the USPTO issued U.S. Patent No. 7,650,331 to Google for inventing Efficient Large-Scale Data Processing."

Comments

google is getting evil

[Anonymous Coward]

Just the other day I couldn't sign up for a gmail account without google demanding my mobile telephone number!

Re:google is getting evil

[Dr. Spork]

Nah, they got this patent so that an evil company can't swoop in and patent the stuff, and prevent others from implementing it without charging crippling royalties. Right? Right??

Re:google is getting evil

[wizardforce]

Behold: the one true undeniable positive trait of the current broken patent system. Keeping horrible ideas expensive.

Re:google is getting evil

[Ethanol-fueled]

They've always done that, haven't they? You sign up, then they text you a validation code.

I'm all for it as long as it keeps people from abusing Gmail accounts. Google's heuristics are so sharp that they could probably figure out your number even if you don't directly hand it to them.

Re:!do no evil

[sakdoctor]

They already burned their karma adding the "fade-in" menu bar.

Re:!do no evil

[astrashe]

This sounds more stupid than evil, which is interesting, because Google doesn't do obviously stupid things very often.

The patent won't do them any good, because it won't stand up in court. They could use it to attack someone small -- an open source developer who would have to back down because they couldn't handle teh legal fees -- but they don't have much of a history of that sort of thing, and there's no reason to think they would in this case, either.

It won't do them any good at all against someone big -- MS and Bing, for example -- because MS would have good lawyers who could demonstrate prior art to a court.

So what's the point?

will be interesting to see if they use it

[Trepidity]

A somewhat optimistic guess is that they'll be restricted to using this defensively. Are they really going to sue Hadoop, the open-source implementation of MapReduce? Hadoop not only implements a version of MapReduce, it even uses its name, so is not at all coy about being a direct infringement of this patent. And yet, I would be surprised if Google sued them, or the many people using it. They certainly haven't said anything yet, as far as I can find--- when things like Amazon Elastic MapReduce were launched, I can't find record of Google saying, "hey, you're stealing our tech!"

Re:will be interesting to see if they use it

[msuarezalvarez]

MapReduce (and variants like Map/Reduce...) are standard nomenclature.

Re:will be interesting to see if they use it

[Razalhague]

Considering that another name for reduce is fold, I think you might be onto something there.

Re:will be interesting to see if they use it

[laughingskeptic]

If they don't enforce their patents, they effectively become public domain. They will probably not sue Hadop, but will try to arrange for some official acknowledgment from Hadop of Google's patent rights and grant them some sort of license explicitly for open source projects. This will strengthen Google's claim. They did not fight their way through 4 rejections and hundreds of thousands of dollars of attorney fees to not enforce this patent.

One of Many, Many Google Patents

[Grond]

Google has at least 173 issued patents as well as over two hundred pending applications. That doesn't include the various patents (such as the PageRank patent) that it is the exclusive licensee for but does not actually own (Stanford owns it). Google's software patent strategy dates back to at least 1997, when it filed this application, which actually predates the PageRank application.

Re:!do no evil

[astrashe]

Isn't that awful? I can't understand why they did it.

Moving stuff on web pages sucks. Especially on that web page.

The bad thing isn't the fade in itself. It's that Google used to be run by people who knew what sucked and what didn't. Now it seems like there are people who don't know in positions to call some shots. It's a bad omen.

They're probably about 10 years away from their own version of Microsoft's "Bob".

Meaning for Hadoop?

[harmonica]

Does this endanger the Hadoop project, or projects using Hadoop? Its MapReduce implementation is a rather crucial part.

Defensive patent

[istartedi]

Before you go acusing Google of doing Evil (TM), think. If they don't do this, some troll will. The troll will lose, but Google will waste a lot more money defending against it.

This is why IBM takes out so many patents too. Most of them are "defensive" patents.

We (that being everybody except the USPTO) could agree not to take out any more software patents, and the industry would breathe a collective sigh of relief. Trouble is, it only takes a few bad apples to spoil that approach. It's the same reason Communism didn't work.

Re:Defensive patent

[blee37]

It is not true that if Google doesn't patent it, a troll will. A technique that is well known, such as MapReduce, is the property of the general public and is unpatentable. Any technology that has been sold or in use for over a year is unpatentable.

Re:Defensive patent

[Target Practice]

"A technique that is well known, such as MapReduce, is the property of the general public and is unpatentable."

Someone should really let the patent clerks in on that secret...

Re:Defensive patent

[schon]

It is not true that if Google doesn't patent it, a troll will.

Really? Why?

MapReduce, is the property of the general public and is unpatentable

.. and yet it just got patented somehow!

I find it hard to believe that the PTO decided "Well, this isn't patentable, but we'll allow Google to patent it just because they're Google."

If Google was granted a patent on it, then a patent troll could have done the same.

Re:Defensive patent

[Jeng]

Considering how much that section has been ignored I would not count on that section preventing a patent troll from trying to patent the process that Google just patented had Google not patented it.

Re:Defensive patent

[Dachannien]

We're called examiners, rather than clerks, and the issue with the vast majority of patents reported on Slashdot isn't that the examiners are clueless concerning the prior art, but that Slashdotters are ignorant of how patent law and patent examining actually works.

For example, in this case, the claims are extremely long - so long, in fact, that the patent is probably worthless for its offensive capacity. The more limitations that a claim has, the narrower the invention has.

In order to anticipate the claim - and thereby reject it under 35 USC 102 - a single prior art reference has to disclose every single limitation of the claim. The longer the claim is, the more likely it is that there's something in there that the prior art doesn't disclose.

In order to render the claim obvious under 35 USC 103, a combination of prior art references has to teach every single limitation of the claim. No single reference has to teach any particular limitation; instead, it can arise through a combination of the references. But it has to be there. What's more, there has to be a proper rationale for combining the references. That is, a "person having ordinary skill in the art" has to have some reason why they would modify what one reference teaches by incorporating the teachings of a second reference. This can be anything from one of the references providing a motivating reason why the teachings of the second reference would be advantageous to include, to a simple finding that one could perform a simple substitution of the secondary reference for a part of the primary reference with predictable results. (See the Supreme Court's KSR Int'l v. Teleflex for a fuller discussion of obviousness.)

Finally, a determination that a patent should be issued is not a 100% guarantee that there is no prior art anywhere that could render a claim anticipated or obvious. Examiners only have a certain amount of time to get the job done, and eventually they have to make a judgment call that a claim properly represents the scope to which the applicant is entitled. The point is to help reduce the number of unnecessary lawsuits resulting from patents whose claims are too broad.

It's not perfect, but we do what we can. And if you don't think that's good enough and you're a US citizen, then eventually, when we start hiring again, you might consider joining the ranks and improving things yourself, within the bounds of the law, one application at a time.

Re:Defensive patent

[VortexCortex]

Just because something can be patented doesn't mean it should be patented. The patent system is supposed to keep things that shouldn't be patented from being patented, but it doesn't -- It's broken. Saying: "Let's see you do better!" isn't the answer.

It's not that I think patent examiners are ignorant, it's just that I find the entire patent system ridiculously flawed...

The patent system is obviously designed to have the least efficient method for discovering prior art. The entire world of prior art simply won't fit through a patent examiner's sieve in the time they are given to decide over a patent. This flaw in the system worsens with time as more patents are granted -- the whole system should be scrapped.

The initial secrecy granted to patent applications is the problem. If the goal is to deem a technology as patentable or not patentable then secrecy should not be required. The solution is to provide a public forum where "persons having ordinary skill in the art" can come to you (the examiners) and show you our previous art.

To put it plainly: Help us Help You! Instead of employing a small group of patent examiners to filter through the entire world's catalog of information, let the entire world direct you to the prior art information you are trying to find.

A quick idea for patent reform

[Daniel Dvorkin]

We're probably never going to get rid of software patents, odious as they are; at this point there are too many enormous players, of which Google is not at all the worst offender, with way too much invested in them. But it occurs to me that one change to patent law that might be politically feasible, and which would really help cut down on clearly frivolous patents like this one:

If any claim in the patent is held to be invalid, the entire patent is invalid.

Claim 1 of the patent is simply an arcane, legalistic description of the operation of pretty much every parallel processing algorithm ever. Some of the subsequent claims actually do describe novel, non-obvious, and useful ways of handling large data sets across multiple processors. If the patent were restricted to these claims, well, it would still be a software patent and therefore Evil, but it might at least have some claim to promoting "the progress of science and the useful arts."

In general, it seems like this would make both patent trolling, and big companies like Google lawyering small independent developers to death, a little more difficult.

Re:A quick idea for patent reform

[samkass]

Software patents are inherently wrong. It doesn't matter if you invent an algorithm or not, because algorithms are just mathematical expressions, and you can't (or shouldn't be able to) patent math. And algorithms are usually implemented, not in physical (patentable) devices, but in software programs, for which the appropriate protection is copyright, not patent.

So you're asserting that you should be able to copyright math?

The whole "software is math" argument is old and debunked. Anything which requires creativity and careful analysis, and the investment therein, is a potentially valuable addition to human knowledge. In exchange for investing in such a thing, there should be the potential to protect your investment from copycats without resorting to keeping it a secret.

I don't see any difference between patenting a physical machine and a computer model of a machine if they follow identical rules and required the same amount of thought and work to produce.

Re:A quick idea for patent reform

[Theaetetus]

Yes, but you are assuming software isn't considered a method. It SHOULD be a method, because it doesn't inherintly change anything within a computer, and if I'm not mistaken there are fights going on right now to define it as such...it is a method by which a computer is told to operate, but doesn't actually modify the computer in any way.

First, software absolutely changes things within a computer. Different switches get flipped, electrons grow in places where they never grew before, etc. Computers are deterministic machines - if software didn't "actually modify the computer in any way" then the software wouldn't be executing and the output would not change in any matter from before the software was applied.

Second, the current test for patentable subject matter in method patents is that it's either transformative (turning iron into steel, for example), or tied to a specific machine. The reason for the latter test is that the CAFC was trying to exempt from patentability algorithms and mathematics that a person could do in their head, or with a pen and paper... This would apply to diagnostic patents (with steps like "noticing, by the physician, that the patient is coughing; diagnosing, by the physician, that the patient has a bacterial infection, responsive to a lab culture") and to mathematical algorithms, including Bilski's derivatives management through market risk balancing ("identifying a first derivative; identifying a second derivative with an opposite risk profile; purchasing enough of the second to counter the first").
By saying "no, you need a machine", what the CAFC was trying to do was say that software that executes on a computer is patentable, but software you do in your head is not patentable. This is a policy argument - we don't want to make people liable for infringement for thinking, but since people's heads don't include silicon processors and network cards, then methods that involve encrypting network packets by a NIC, for example, can't be infringed by a person thinking. Even if they were to sit with a slide rule and manually calculate each RSA-128 bit of a network packet, they wouldn't infringe, because they don't have a NIC.

Now, let's take a look at your analogy in the above framework:

Analogy: making a choose your own adventure book doesn't change the fact that it is a book...it merely changes the way you obtain and utilize the data (words) on its pages. You wouldn't expect to get a patent on reading every other page in a book, would you?

And you couldn't - it's done by a person, and not tied to a specific machine. But, you could patent a decision tree performed by a specific computing device having specific hardware or software functionality for performing the method... if decision trees weren't already known, mind you, but novelty and obviousness is a different argument altogether.

I don't have any links handy on me with this subject but Bilski vs. Kappos could have a major ripple effect on software patents depending on what happens with their definition.

Yes, but the Supreme Court absolutely will not invalidate all software patents. They probably won't even invalidate diagnostic patents. Two reasons: first, it would require completely reversing not just the CAFC Bilski decision, but also State Street, AT&T, Mayo v. Prometheus, and even Diamond v. Chakrabarty. Basically, 30 years of Supreme Court decisions on the topic. Second, software and diagnostic patents are worth a lot of money in our economy, and the Supreme Court, first and foremost, is a political body. They won't crash the economy when there are alternate interpretations of the law available that won't have that side effect.

My guess: Bilski's application is denied, for any one of several reasons. The CAFC's machine-or-transformation test is discarded as being too vague, particularly on the "machine" side, because no one really knows what is meant by "tied to

resume builders

[MillionthMonkey]

I wrote a parallel application to process scientific data on multiple servers at a previous place I worked, using just SQL statements with a mod function on a primary key. The resume builders there then hired a consultant to help them rewrite the whole thing (excluding the core atomic algorithm part) using Hadoop and MapReduce, because the previous one didn't use Hadoop and MapReduce. They made a total mess and it's so hard to configure and deploy that IT still uses the version I wrote a year before.

need awareness of the "old" algorithms

[peter303]

The greybeards have a point there. In my branch of signal processing where have gone through cycles several times as computer hardware evolves. In my experience we've been through minicomputers, array processors, workstations, clusters, stream processors, multi-cores etc. Each configuration as different balance of CPU speed, memory size, memory bandwidth, and so on. So we've gone through the difference algorithms, the integral algorithms, the spectral, the local-transform, cyclic matrices, etc. back and forth several times. Sometimes each new generation of grad students feels it has invented something new if sloppy work by their faculty advisor doesnt correct them.

The usual /. patent question -

[Janthkin]

- did the submitter actually read the claims, before asserting that it was obvious and/or anticipated?
Here's claim 1 (it's a monster): 1. A system for large-scale processing of data, comprising:
a plurality of processes executing on a plurality of interconnected processors;
the plurality of processes including a master process, for coordinating a data processing job for processing a set of input data, and worker processes;
the master process, in response to a request to perform the data processing job, assigning input data blocks of the set of input data to respective ones of the worker processes;
each of a first plurality of the worker processes including an application-independent map module for retrieving a respective input data block assigned to the worker process by the master process and applying an application-specific map operation to the respective input data block to produce intermediate data values, wherein at least a subset of the intermediate data values each comprises a key/value pair, and wherein at least two of the first plurality of the worker processes operate simultaneously so as to perform the application-specific map operation in parallel on distinct, respective input data blocks; a partition operator for processing the produced intermediate data values to produce a plurality of intermediate data sets, wherein each respective intermediate data set includes all key/value pairs for a distinct set of respective keys, and wherein at least one of the respective intermediate data sets includes respective ones of the key/value pairs produced by a plurality of the first plurality of the worker processes; and
each of a second plurality of the worker processes including an application-independent reduce module for retrieving data, the retrieved data comprising at least a subset of the key/value pairs from a respective intermediate data set of the plurality of intermediate data sets and applying an application-specific reduce operation to the retrieved data to produce final output data corresponding to the distinct set of respective keys in the respective intermediate data set of the plurality of intermediate data sets, and wherein at least two of the second plurality of the worker processes operate simultaneously so as to perform the application-specific reduce operation in parallel on multiple respective subsets of the produced intermediate data values.

That's one heck of a detailed claim. Infringement would require some effort; anticipation (every limitation appearing in a single document, arranged in the same manner as the claim) is unlikely.

Re:The usual /. patent question -

[Theaetetus]

Anticipation is narrow. Infringement, however, is broad. A slight difference between the purported prior art and the claim means the prior art doesn't invalidate the claim.

... under 35 USC 102, but it could well under 35 USC 103(a). Infringement is broad due to the doctrine of equivalents... Obviousness is similarly broad due to the KSR factors.

Re:Awarded?

[blee37]

All documents at http://patft.uspto.gov/ are issued patents.

MapReduce

[decipher_saint]

I didn't know what MapReduce was so I looked it up:

MapReduce is a software framework introduced by Google to support distributed computing on large data sets on clusters of computers.

Re:!do no evil

[m.ducharme]

The point is probably to create and keep a nice big portfolio of patents to be used the next time Google gets sued for patent infringement. It's common practice for big tech firms (and others, of course) to hold a reserve of patents at the ready in the event that they need to defend against a patent suit. The aggressor company sues for infringement, the defender digs up a few patents that the aggressor is violating, and they settle out of court for a mutual licensing agreement.

Of course it's ridiculous, and sounds stupid, but it's a symptom of the broken patent system, not a peculiarity of Google.

How it's suppose to work... Take 2.

[v(*_*)vvvv]

A patent is only worth it's strength in court. The USPTO has clearly given up trying to judge if a patent is truly worthy on their own, relying on the courts to decide afterwards when a patent is put to use and put to the test - in court.

What bothers me the most is the fact that anyone can get a patent for anything as long as they keep revising their application.

At the end of the day, those with the biggest wallets will get their patents, and they will also have their guns to fight and win in court.

US patent office workers should be ashamed...

[BuddaLicious]

how do you get a patent awarded on something that has already been released as "open source" (Hadoop)

This does not add up, either Hadoop is not really open source, or US patent office are as FCKING stupid as EVERYONE seems to think they are.

Come on people, don't you get tired of the shame of working for such an organization....don't you want to see freedom and democracy restored to the world..?>?>

Re:US patent office workers should be ashamed...

[Dan Ost]

Previous post seems to indicate that this patent application was filed in 2004, before Hadoop was created. If true, and if Google decides to use this patent against Hadoop, and if the patent withstands the scrutiny of a court battle, then Hadoop, at least as Open Source, would be dead.

Don't jump to conclusions yet, however. It'll take some time to digest the patent and decide what it's really attempting to cover.

Re:!do no evil

[Animaether]

The fade-in is nice. Not so much because it's a fade-in (which is just visually more pleasant than an instant-display), but because you can visit www.google.com and get a very clean page (google logo, search field, and currently a Haiti relief notice), and just type away (as focus is set to the search field) and be done with it. This is very much like how google.com -was- in the very early days.

If you want to access any of the other services that google have started to offer since then, you can move your mouse anywhere within the screen and hey presto those options become available to you. If you don't need them - why clutter up the screen with them?

You can always customize your own google page and set that as your bookmark/start page/whatever and display exact what you want to have displayed from the get-go.

If anything, the change from direct URLs to google redirects at some point is what I find most annoying. I guess it's what enables them to track clicks better / present "We believe this page is dangerous for your health"-warnings, etc. and I can see how that can be good for them as a business, and for users who go clickhappy on fluffy little bunnies promising them cash. But it annoys me that I can't just 1. google for something, 2. recognize the right place, 3. right-click the result and get the basic URL out of it anymore. Now, I just get this (for slashdot):
http://www.google.com/url?sa=t&source=web&ct=res&cd=1&ved=0CBgQFkAA&url=http%3A%2F%2Fslashdot.org%2F&rct=j&q=slashdot&ei=KAtXS8CCLeLMQAeSx8CbDg&usg=AFQjClHLEL_tF-6ZxylM44KJH54-gaJRnQ&s1g2=U223qDAEXHFbHyOw_p2PzQ

wtf.

I'd much prefer they put the actual URL in the link, and let their redirect flow through an onClick.. yeah, they'd lose the javascript-disabled lot.. tough.

Re:!do no evil

[afidel]

The backdoor to that system as we've seen is to sell of a patent to a investment firm which stands up a patent troll company (or buys a small company in the field and turns it into a patent troll) and have them abuse it, the MAD strategy then no longer works as the opponent only exists to spend their cash reserves on the lawsuit and to turn over any profits to the investors.

Re:!do no evil

[GIL_Dude]

I agree about the Google redirects. I know they have been there for awhile now, but I first actually "noticed" them (as in they caused me a problem) just the other day when I was trying to get some links to "further reading" to go into some technical document I was writing. I sure didn't want Google redirect links in my document so I actually ended up going to Bing and doing the same search. That worked better as Bing apparently doesn't do the redirect thing and the links are actually links to the site you searched for. Bing doesn't do anything else better, but Google made their links useless for that function.

Re:!do no evil

[kripkenstein]

Why do you think the recent Google-China issue is either all about Google having a conscience or all about Google acting in their own self interest? It's both, and it's complicated.

For one thing, having a conscience is in Google's best self interest. Public image is crucial for a company like that.

For another, companies Google's size (or any size, if they are competent) don't make decisions based on 1 factor. They take into account many, many factors, including conflicting ones, and they arrive at a decision. In this case, clearly both the conscience issue was a factor as well as the self interest factor.

Re:!do no evil

[MechaStreisand]

I've noticed that when you do a google search and mouseover the links, it shows the direct link in the status bar, but that is a lie. If you look at the actual URL in the link properties, you'll see that it redirects through google. Sneaky.

Re:!do no evil

[patman600]

I did look at the url properties. It was the plain url. A search for "houston chronicle" returns this Houston Chronicle right clicking and copying the link location copies "http://www.chron.com"

Defensive Patent Portfolio?

[shentino]

I'll reserve judgement until this patent is involved, offensively, defensively or otherwise, in litigation.

Google has got a good reputation so I'm not as quick to condemn them as I am to condemn Microsoft which has a PROVEN track record of evil.

It's entirely plausible that this patent is part of a defensive patent portfolio whose sole purpose is to protect Google.

And considering the zany IP landscape, if anyone's going to have a patent on this, I'd rather it be Google than anyone else. If Microsoft had this club in their arsenal you can bet your bottom dollar they'd make their assault on Tom-Tom look like a puny peashooter.

redirects

[xant]

If you hate the redirects (and I sure do.. copying URLs is the best), then push for HTML5. Specifically this feature: the ping attribute.

It takes what Google (and many, many another site) is doing and makes it possible to implement the ping separately from the target URL. Seems trivial; could make a huge difference.

Of course, the danger is that it gives extension authors an easy target. It's much easier to develop a privacy-enhancing extension that filters out all ping attributes, than it is to perform the same service on a single URL which conflates the ping with the target.

We'll see; I hold out high hopes for it.

Re:!do no evil

[domatic]

So why not follow the money and retaliate against the investors? An attack is an attack regardless of whether it is done by proxy. That is in line with MAD thinking too where an attack by or on an ally is escalated against the parent aggressor.

Re:!do no evil

[Petrushka]

I did look at the url properties. It was the plain url

Yes, the a href=... bit is a plaintext url. But what do you think the onmousedown="return clk( ... bit does?

Answer: it calls a "window.clk" function, which sends a message to Google to tell them that you clicked on such-and-such a link.

It's not a redirect; it's sneakier. Bing and Ask do exactly the same.