US Patent #7,650,331: System & method for efficient large-scale data processing
patft.uspto.gov
patft.uspto.gov
I think that all patents should have to go through the peer review process, unless there is some kind of extra-ordinary reason that it can't be made public:
Bullshit. Here are the two independent claims:
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.
9. A method of performing a large-scale data processing job, comprising: executing a plurality of processes on a plurality of interconnected processors, the plurality of processes including a master process for coordinating the large-scale data processing job for processing a set of input data, and worker processes; in the master process, in response to a request to perform the large-scale data processing job, assigning input data blocks of the set of input data to respective ones of the worker processes; in each of a first plurality of the worker processes, executing an application-independent map module to retrieve a respective input data block assigned to the worker process by the master process and to apply 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; using a partition operator to process 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 in each of a second plurality of the worker processes, executing an application-independent reduce module to retrieve 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.
This very clearly only covers computations distributed over multiple systems (a plurality of processes executing on a plurality of interconnected processors) and is narrow enough that there are lots of parallel systems which don't fall under those claims.
It's bullshit.
http://code.google.com/p/thrust/
does basically those two "claims", just on a GPU (which falls under your definition).
In any case, my complaint is more about the wording than the actual technology that the patent covers. Patents are granted for such generic technology these days, that it's going to scare away people from trying to create new things (lest it already be covered under a generic patent that really doesn't relate to the new product.)
map :: (a -> b) -> [a] -> b
fold :: (a -> a -> a) -> a -> [a] -> a -- the first argument must be associative if you want a parallel fold.
mapReduce :: (a -> b) -> (b -> b -> b) -> b -> [a] -> b
mapReduce f g e l = fold g e (map f l) -- conceptually. You have to write an actually parallel version.
If the patent isn't more specific than this (by being limited to MapReduce, for instance), I bet it can be overruled by prior art. Now, I admit I don't have the courage to check.As someone mentioned: the Glasgow Haskell Compiler and its RTS is such a system...
I read the first half of the book and found it enlightening.
I think you mean Claim #1: A painful punishment; Claim #2: Claim #1 wherein the punishment includes physical force; Claim #3: Claim #2 wherein the physical force comprises multiple punches; Claim #4: Claim #3 wherein the punches are directed at the face of the patent attorney.
I do agree though, the way these are written is almost completely unreadable. Almost like how we use English words in programming languages, but without the domain knowledge, it is meaningless.
However, it's not so applicable to the claims of the patent. This part is for lawyers to use to determine the exact extent of the legal protection conferred by the patent. The description is of just one embodiment of the invention; it is natural that slight variations from that embodiment should also be covered - but exactly how much variation is covered? How general (or how abstract) is the coverage? Especially when you consider that the given embodiment isn't necessarily the "center" of the inventions - it is not the embodiment, just an embodiment. This extent is difficult to specify, and special language is needed.
To use jordyhoyt's analogy, it would be like expecting Erlang to be readable by a layman. Of course, we can do better. The point is that it's hard to serve many masters.
If lawyerese for a formally-defined language with a compiler and everything, I'd have less problems with it. But from whetre I'm standing, it just looks like obfuscated English.
For example, you will see numbers written out longhand in patents - eg, 'two hundred and fifty six', because that is supposed to be more understandable than 256.
:(
Of course, the necessity for defensive patenting itself just goes to show how silly the current patent system is.
This was filed June 18, 2004, so given the one year grace allowed under US law, if Google made commercial use of this system before June 18, 2003, then they cannot patent it.
I'm pretty sure Google used distributed map-reduce from the beginning... so I'm thinking that this patent must cover a refined method that differs in some way from their initial approach.
It's a lot of work to read and understand a patent (I spent a couple of days on one this week), so if anyone else wants to do so and let us know what the patented algorithm actually is...
Incorrect. IANAL, so I will not attempt to correct you. I suspect YANAL either.
"If the invention has been described in a printed publication anywhere, or has been in public use or on sale in this country more than one year before the date on which an application for patent is filed in this country, a patent cannot be obtained."
http://www.uspto.gov/web/offices/pac/doc/general/index.html#...
"if it was known or used by others in this country before the date that the applicant made his/her invention, a patent cannot be obtained".
Mind you, they don't seem to apply this very consistently.
I was originally pointing out a fact lest others be led astray, but I'm not going to reply further.
However, 10ren's statement seems to be backed up pretty well by the USPTO site - if you have already gone public or sold your invention, no patent for you. I'm not sure why you think it is incorrect.
Cheers
Otherwise patenting map reduce - which is practically one of the foundations of functional data processing - is down right silly
The patent is about parallelizing M and R operators for large-scale data analysis; I think that the relevant prior art would include 1980s work on parallel database systems (e.g. Gamma, Bubba).