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."

One of Many, Many Google Patents

[Grond]

Google has at least 173 issued patents [google.com] as well as over two hundred pending applications [google.com]. 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 [google.com], which actually predates the PageRank application.

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:Awarded?

[blee37]

All documents at http://patft.uspto.gov/ [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:will be interesting to see if they use it

[msuarezalvarez]

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

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: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:!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 <a href="http://www.chron.com/" class=l onmousedown="return clk(this.href,'','','res','1','','0CAcQFjAA')"><em>Houston Chronicle</em></a> right clicking and copying the link location copies "http://www.chron.com"

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 [mozillazine.org].

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

[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.

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.