7 ms·

US Patent #7,650,331: System & method for efficient large-scale data processing

73 points by mattyb 17y ago

siculars 17y ago
Don't be Evil. Indeed. Well, you know, someone needs to keep IBM from a C&D against Hadoop.
- coderdude 17y ago
  Has Hadoop been out since 2004?
  - abscondment 17y ago
    No; it seems to have been inspired by Google papers as a solution to Nutch's scaling issues. See http://research.yahoo.com/files/cutting.pdf http://research.yahoo.com/files/cutting.pdf [pdf] :(
- lmkg 17y ago
  While I'm normally the first to pile on and complain about Google, in this case I'm going to hold off unless/until they try to enforce their patent. The big companies like Google and Microsoft need to preemptively patent everything they can, in order to stave off the real patent trolls. Of course, the necessity for defensive patenting itself just goes to show how silly the current patent system is.
  - houseabsolute 17y ago
    Well, it's not a very good defense against patent trolls, because those guys typically don't exercise their own patents or anyone else's. However, it does help somewhat against companies like Apple or Nokia who are fine with litigating against anyone who tries to compete on an even footing. For example, if Yahoo or Microsoft sued Google for some search related patent, probably Google could use this patent against them.
  - siculars 17y ago
    I agree. The defensive patent is becoming perhaps more important than the offensive patent, re trolls. Being able to use a patent in one area to not only defend against competitors locking you out of your own technology but also counter a potential patent suit in another technology is becoming all too common, re apple v nokia.
profquail 17y ago
The software patent situation is getting more and more ridiculous by the day. This patent is so general, it describes basically any data-mining software (that may or may not be distributed over multiple computers.) 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: http://www.peertopatent.org/ http://www.peertopatent.org/
- cperciva 17y ago
  This patent is so general, it describes basically any data-mining software (that may or may not be distributed over multiple computers.) 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.
alttab 17y ago
Even if they wanted to enforce it they'd have to prove it. Otherwise patenting map reduce - which is practically one of the foundations of functional data processing - is down right silly
- bitdiddle 17y ago
  I agree completely. I would think there is enormous prior art in this area that makes this patent absurd.
- neilc 17y ago
  The relevant prior art is not the idea of a "map" or "reduce" function as such (that isn't what is significant about MR, anyway). 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).
fexl 17y ago
μολον λαβε
- zandorg 17y ago
  Is that APL?
  - deleted 17y ago
    [deleted]
  - profquail 17y ago
    Probably.
- jcl 17y ago
  For the curious: http://en.wikipedia.org/wiki/Molon_labe http://en.wikipedia.org/wiki/Molon_labe
  - fexl 17y ago
    Ah, I should have used omega there instead of omicron. I'm sure I got dinged for the defiant sentiment though.
cabalamat 17y ago
I think patent attorneys should be required to write patents in understandable English, on pain of receiving a plurality of punches in the face.
- notaddicted 17y ago
  This book has 2 chapters on patents: http://oreilly.com/catalog/9780596517960 http://oreilly.com/catalog/9780596517960 I read the first half of the book and found it enlightening.
- cperciva 17y ago
  on pain of receiving a plurality of punches in the face 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.
  - astrodust 17y ago
    I'm pretty sure you could patent that!
- jordyhoyt 17y ago
  They are very aware of how they are speaking, and in person, they are the most precise people you will ever meet. I recently had occasion to speak with a patent attorney, and not only did he explain the patent in plain English, but I was floored at how unambiguous he was. We spoke over the phone and he was able to guide several people through the details of the patent quickly and clearly. 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.
  - cabalamat 17y ago
    Ptents in theory are meant to blanace a public bad (a monopoly) with a public good (teaching practitioners how to do something). I am a programmer, and I do not understand software patents. I'm sure I'm not the oonly one. If a typical practitioner of an art, when seeing a patent, says its hard to understand or confusingly worded, the patent should be void.
mark_l_watson 17y ago
Google could make themselves look better right now by quickly granting a free perpetual nonexclusive patent license to the Apache Hadoop project.
sjunkin 17y ago
I wonder what AbInitio, Informatica, et al think about this patent, is the HN community aware of their claims to similar IP?
10ren 17y ago
You can't patent something that has been publicly disclosed, including disclosure by yourself. Commercial use counts as disclosure. 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...
- WalterGR 17y ago
  > You can't patent something that has been publicly disclosed, including disclosure by yourself. Commercial use counts as disclosure. Incorrect. IANAL, so I will not attempt to correct you. I suspect YANAL either.
  - cromulent 17y ago
    It seems to be true in the US. "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#novelty http://www.uspto.gov/web/offices/pac/doc/general/index.html#...
    - WalterGR 17y ago
      Year-to-file is obviously different than cannot-file.
      - cromulent 17y ago
        It's in the same section. "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.
blueag 17y ago
Google is the evil empire.

73 points by mattyb 17y ago

siculars 17y ago

Don't be Evil. Indeed. Well, you know, someone needs to keep IBM from a C&D against Hadoop.

coderdude 17y ago
Has Hadoop been out since 2004?
- abscondment 17y ago
  No; it seems to have been inspired by Google papers as a solution to Nutch's scaling issues. See http://research.yahoo.com/files/cutting.pdf http://research.yahoo.com/files/cutting.pdf [pdf] :(
lmkg 17y ago
While I'm normally the first to pile on and complain about Google, in this case I'm going to hold off unless/until they try to enforce their patent. The big companies like Google and Microsoft need to preemptively patent everything they can, in order to stave off the real patent trolls. Of course, the necessity for defensive patenting itself just goes to show how silly the current patent system is.
- houseabsolute 17y ago
  Well, it's not a very good defense against patent trolls, because those guys typically don't exercise their own patents or anyone else's. However, it does help somewhat against companies like Apple or Nokia who are fine with litigating against anyone who tries to compete on an even footing. For example, if Yahoo or Microsoft sued Google for some search related patent, probably Google could use this patent against them.
- siculars 17y ago
  I agree. The defensive patent is becoming perhaps more important than the offensive patent, re trolls. Being able to use a patent in one area to not only defend against competitors locking you out of your own technology but also counter a potential patent suit in another technology is becoming all too common, re apple v nokia.

profquail 17y ago

The software patent situation is getting more and more ridiculous by the day. This patent is so general, it describes basically any data-mining software (that may or may not be distributed over multiple computers.) 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: http://www.peertopatent.org/ http://www.peertopatent.org/

cperciva 17y ago
This patent is so general, it describes basically any data-mining software (that may or may not be distributed over multiple computers.) 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.

alttab 17y ago

Even if they wanted to enforce it they'd have to prove it. Otherwise patenting map reduce - which is practically one of the foundations of functional data processing - is down right silly

bitdiddle 17y ago
I agree completely. I would think there is enormous prior art in this area that makes this patent absurd.
neilc 17y ago
The relevant prior art is not the idea of a "map" or "reduce" function as such (that isn't what is significant about MR, anyway). 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).

fexl 17y ago

μολον λαβε

zandorg 17y ago
Is that APL?
- deleted 17y ago
  [deleted]
- profquail 17y ago
  Probably.
jcl 17y ago
For the curious: http://en.wikipedia.org/wiki/Molon_labe http://en.wikipedia.org/wiki/Molon_labe
- fexl 17y ago
  Ah, I should have used omega there instead of omicron. I'm sure I got dinged for the defiant sentiment though.

cabalamat 17y ago

I think patent attorneys should be required to write patents in understandable English, on pain of receiving a plurality of punches in the face.

notaddicted 17y ago
This book has 2 chapters on patents: http://oreilly.com/catalog/9780596517960 http://oreilly.com/catalog/9780596517960 I read the first half of the book and found it enlightening.
cperciva 17y ago
on pain of receiving a plurality of punches in the face 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.
- astrodust 17y ago
  I'm pretty sure you could patent that!
jordyhoyt 17y ago
They are very aware of how they are speaking, and in person, they are the most precise people you will ever meet. I recently had occasion to speak with a patent attorney, and not only did he explain the patent in plain English, but I was floored at how unambiguous he was. We spoke over the phone and he was able to guide several people through the details of the patent quickly and clearly. 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.
- cabalamat 17y ago
  Ptents in theory are meant to blanace a public bad (a monopoly) with a public good (teaching practitioners how to do something). I am a programmer, and I do not understand software patents. I'm sure I'm not the oonly one. If a typical practitioner of an art, when seeing a patent, says its hard to understand or confusingly worded, the patent should be void.

mark_l_watson 17y ago

Google could make themselves look better right now by quickly granting a free perpetual nonexclusive patent license to the Apache Hadoop project.

sjunkin 17y ago

I wonder what AbInitio, Informatica, et al think about this patent, is the HN community aware of their claims to similar IP?

10ren 17y ago

You can't patent something that has been publicly disclosed, including disclosure by yourself. Commercial use counts as disclosure. 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...

WalterGR 17y ago
> You can't patent something that has been publicly disclosed, including disclosure by yourself. Commercial use counts as disclosure. Incorrect. IANAL, so I will not attempt to correct you. I suspect YANAL either.
- cromulent 17y ago
  It seems to be true in the US. "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#novelty http://www.uspto.gov/web/offices/pac/doc/general/index.html#...
  - WalterGR 17y ago
    Year-to-file is obviously different than cannot-file.
    - cromulent 17y ago
      It's in the same section. "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.

blueag 17y ago

Google is the evil empire.