4 ms·

Didn't Google actually introduce mapreduce into the mainstream and thus Hadoop is just an open-source clone of Google's system ? Given that patents are a way o

Didn't Google actually introduce mapreduce into the mainstream and thus Hadoop is just an open-source clone of Google's system ? Given that patents are a way of live in the US, why wouldn't Google patent this ? Would you prefer someone else instead ? On a related note -- how many patents does the Apache Foundation own ?

jacquesm 17y ago
Mapping and reducing have been part and parcel of programming for the longest time. Packaging the concept in a framework and patenting it should not have been possible.
- jbooth 17y ago
  It's not like they just patented the method signatures map(sequence) and reduce(sequence) -- there's a global-scale distributed filesystem, the method of dispatching tasks so they have high odds of node-locality or rack-locality to the data they're operating over, all sorts of redundancy and failover necessary to run clusters where machines fail every minute by virtue of having so many of them.. I mean I'm as against software patents as the next guy but this isn't the most trivial one I've seen. Glad they licensed it to ASF.
  - jacquesm 17y ago
    In their original map reduce documentation they explicitly state they were inspired by programming languages containing map/reduce functionality. Adding all kinds of bells and whistles to it does not make it 'novel'. Redundancy, failover, node locality and rack locality have all been done many times over in the past, maybe not in that context but that is just a combining of concepts. To be awarded a patent you should at least do something original.
    - jbooth 17y ago
      "Inspired by", what's that mean? Even the most novel and patentable innovation surely has inspirations. I already said I'm against software patents -- but this is one of the worse cases to back up the viewpoint, they actually invent something here.
      - jacquesm 17y ago
        That's prior art. Even the names are the same. 'on a network' or 'on a cluster' or 'more reliable' or 'much larger' are not worthy of patenting, they are incremental extensions and not inventions. The first time someone did map/reduce, the first time someone did quicksort, that was invention. Doing it larger or through some other variation does not make it an invention. Anyway, you seem to be set on your position that they invented something, I really think they didn't. Map/Reduce to me is actually a poster child for a very bad software patent.
        jbooth 17y ago
        Well, just to explain my point of view better, you could rephrase aviation as just moving stuff "through the air" and "faster" -- hey we've had transportation for thousands of years! And we had combustion engines before they were ever used to power an airplane. I'll admit that it's a fuzzy line and you can make a case for this particular thing to be on either side of it -- but having components that are previously established isn't enough IMO to definitively say "nothing was invented".
        jacquesm 17y ago
        On a multi-processor system: cat somefile.txt | grep sometext | cut -d ' ' -f 1 | sort | uniq -c | wc Is technically in violation of the map reduce patent, it is that broad. Go read the thing, seriously it is very interesting reading. The meat is this section: "A large-scale data processing system and method includes one or more application-independent map modules configured to read input data and to apply at least one application-specific map operation to the input data to produce intermediate data values, wherein the map operation is automatically parallelized across multiple processors in the parallel processing environment. A plurality of intermediate data structures are used to store the intermediate data values. One or more application-independent reduce modules are configured to retrieve the intermediate data values and to apply at least one application-specific reduce operation to the intermediate data values to provide output data."
    - tghw 17y ago
      If someone builds a better mousetrap, it's patentable. And it's still a mousetrap. Combining a bunch of existing concepts in a new way is the basis for the patent system. It's the only way to progress: iteration. Putting that aside, what Google did with MapReduce was original. There are a number of challenges that each of the individual concepts never had to overcome, which required new, unique concepts to be introduced to make the system work.
      - jacquesm 17y ago
        > If someone builds a better mousetrap, it's patentable. Only if the mechanism is novel. And that's the problem here, the mechanism is identical, just larger. Running map/reduce on an array or on a petabyte data set does not change the fundamental method at all. There are just countless implementation details to be taken care of, but any competent programmer could extend the original concept of map/reduce to that level.
        anamax 17y ago
        > > If someone builds a better mousetrap, it's patentable. >Only if the mechanism is novel. Actually, no. It's perfectly reasonable to patent using old mechanisms to do new things or to do old things differently. For example, appropriate to patent using a lever to do something that no one had thought to do with a lever before, despite the fact that levers are one of the oldest mechanisms. Note that new mechanisms don't come along very often. Much of what we get are new uses or new applications.
        tghw 17y ago
        Running map/reduce on an array or on a petabyte data set does not change the fundamental method at all. It very much changes the fundamental method. It takes something that was once impossible given all existing techniques and technologies, and makes it possible. The new techniques and technologies are at the core of the patent. any competent programmer could extend the original concept of map/reduce to that level. Patently false. At the very least, you need a decent sized team of very competent programmers, DBAs, and system administrators to architect and build the system, and another programming test team to ensure that it is reliable. And then you'd only have a working prototype. This isn't nearly as trivial as you make it out to be. Hadoop is evidence of that, it's going on 4 years and four thousand changesets, with changes by over 50 people from Apache, Yahoo! and the general public. Its source directory (for only the common project, not including the HDFS) clocks in at 328 KLOC. MapReduce wasn't some little side project hack-job. But then again, you could probably code up Stack Overflow in a weekend, couldn't you?
jfoutz 17y ago
C* and zeta lisp both supported parallel map reduce at the language level.
- tghw 17y ago
  At the language level, yes. At the on-computers-all-over-the-world-on-petabyte-datasets level? No. That was Google.
  - jacquesm 17y ago
    That's like those 'on the internet' patents then. Only this time it is the 'on a cluster' variation. Take an existing scheme, implement it on a cluster, instant market lock.
    - tghw 17y ago
      Yeah, it's not that simple. You're talking about one of the biggest scaling problems ever addressed. You have to figure out how to shard the data, how to deal with failures and inconsistencies, how to return results from terabytes of data, and how to make it all fast enough that your search results come back in less than a second.
      - gsmaverick 17y ago
        Map-reduce isn't used in search queries only for indexing.
brainlounge 17y ago
Apache owns zero patents.
- fierarul 17y ago
  Then they aren't doing a great job given they did choose to create the foundation in the US. When in Rome...
  - brainlounge 17y ago
    On the other hand, ASF is receiving major tax-reducable donations from US companies. The ASF is not in the patent business.

jacquesm 17y ago

Mapping and reducing have been part and parcel of programming for the longest time. Packaging the concept in a framework and patenting it should not have been possible.

jbooth 17y ago
It's not like they just patented the method signatures map(sequence) and reduce(sequence) -- there's a global-scale distributed filesystem, the method of dispatching tasks so they have high odds of node-locality or rack-locality to the data they're operating over, all sorts of redundancy and failover necessary to run clusters where machines fail every minute by virtue of having so many of them.. I mean I'm as against software patents as the next guy but this isn't the most trivial one I've seen. Glad they licensed it to ASF.
- jacquesm 17y ago
  In their original map reduce documentation they explicitly state they were inspired by programming languages containing map/reduce functionality. Adding all kinds of bells and whistles to it does not make it 'novel'. Redundancy, failover, node locality and rack locality have all been done many times over in the past, maybe not in that context but that is just a combining of concepts. To be awarded a patent you should at least do something original.
  - jbooth 17y ago
    "Inspired by", what's that mean? Even the most novel and patentable innovation surely has inspirations. I already said I'm against software patents -- but this is one of the worse cases to back up the viewpoint, they actually invent something here.
    - jacquesm 17y ago
      That's prior art. Even the names are the same. 'on a network' or 'on a cluster' or 'more reliable' or 'much larger' are not worthy of patenting, they are incremental extensions and not inventions. The first time someone did map/reduce, the first time someone did quicksort, that was invention. Doing it larger or through some other variation does not make it an invention. Anyway, you seem to be set on your position that they invented something, I really think they didn't. Map/Reduce to me is actually a poster child for a very bad software patent.
      - jbooth 17y ago
        Well, just to explain my point of view better, you could rephrase aviation as just moving stuff "through the air" and "faster" -- hey we've had transportation for thousands of years! And we had combustion engines before they were ever used to power an airplane. I'll admit that it's a fuzzy line and you can make a case for this particular thing to be on either side of it -- but having components that are previously established isn't enough IMO to definitively say "nothing was invented".
        jacquesm 17y ago
        On a multi-processor system: cat somefile.txt | grep sometext | cut -d ' ' -f 1 | sort | uniq -c | wc Is technically in violation of the map reduce patent, it is that broad. Go read the thing, seriously it is very interesting reading. The meat is this section: "A large-scale data processing system and method includes one or more application-independent map modules configured to read input data and to apply at least one application-specific map operation to the input data to produce intermediate data values, wherein the map operation is automatically parallelized across multiple processors in the parallel processing environment. A plurality of intermediate data structures are used to store the intermediate data values. One or more application-independent reduce modules are configured to retrieve the intermediate data values and to apply at least one application-specific reduce operation to the intermediate data values to provide output data."
  - tghw 17y ago
    If someone builds a better mousetrap, it's patentable. And it's still a mousetrap. Combining a bunch of existing concepts in a new way is the basis for the patent system. It's the only way to progress: iteration. Putting that aside, what Google did with MapReduce was original. There are a number of challenges that each of the individual concepts never had to overcome, which required new, unique concepts to be introduced to make the system work.
    - jacquesm 17y ago
      > If someone builds a better mousetrap, it's patentable. Only if the mechanism is novel. And that's the problem here, the mechanism is identical, just larger. Running map/reduce on an array or on a petabyte data set does not change the fundamental method at all. There are just countless implementation details to be taken care of, but any competent programmer could extend the original concept of map/reduce to that level.
      - anamax 17y ago
        > > If someone builds a better mousetrap, it's patentable. >Only if the mechanism is novel. Actually, no. It's perfectly reasonable to patent using old mechanisms to do new things or to do old things differently. For example, appropriate to patent using a lever to do something that no one had thought to do with a lever before, despite the fact that levers are one of the oldest mechanisms. Note that new mechanisms don't come along very often. Much of what we get are new uses or new applications.
      - tghw 17y ago
        Running map/reduce on an array or on a petabyte data set does not change the fundamental method at all. It very much changes the fundamental method. It takes something that was once impossible given all existing techniques and technologies, and makes it possible. The new techniques and technologies are at the core of the patent. any competent programmer could extend the original concept of map/reduce to that level. Patently false. At the very least, you need a decent sized team of very competent programmers, DBAs, and system administrators to architect and build the system, and another programming test team to ensure that it is reliable. And then you'd only have a working prototype. This isn't nearly as trivial as you make it out to be. Hadoop is evidence of that, it's going on 4 years and four thousand changesets, with changes by over 50 people from Apache, Yahoo! and the general public. Its source directory (for only the common project, not including the HDFS) clocks in at 328 KLOC. MapReduce wasn't some little side project hack-job. But then again, you could probably code up Stack Overflow in a weekend, couldn't you?

jfoutz 17y ago

C* and zeta lisp both supported parallel map reduce at the language level.

tghw 17y ago
At the language level, yes. At the on-computers-all-over-the-world-on-petabyte-datasets level? No. That was Google.
- jacquesm 17y ago
  That's like those 'on the internet' patents then. Only this time it is the 'on a cluster' variation. Take an existing scheme, implement it on a cluster, instant market lock.
  - tghw 17y ago
    Yeah, it's not that simple. You're talking about one of the biggest scaling problems ever addressed. You have to figure out how to shard the data, how to deal with failures and inconsistencies, how to return results from terabytes of data, and how to make it all fast enough that your search results come back in less than a second.
    - gsmaverick 17y ago
      Map-reduce isn't used in search queries only for indexing.

brainlounge 17y ago

Apache owns zero patents.

fierarul 17y ago
Then they aren't doing a great job given they did choose to create the foundation in the US. When in Rome...
- brainlounge 17y ago
  On the other hand, ASF is receiving major tax-reducable donations from US companies. The ASF is not in the patent business.