hadoop-mapreduce-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Luke Lu (JIRA)" <j...@apache.org>
Subject [jira] Commented: (MAPREDUCE-1639) Grouping using hashing instead of sorting
Date Sun, 28 Mar 2010 17:13:27 GMT

    [ https://issues.apache.org/jira/browse/MAPREDUCE-1639?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12850693#action_12850693
] 

Luke Lu commented on MAPREDUCE-1639:
------------------------------------

IMHO, it'd be easier to implement such grouping using a special group record reader (inputformat)
and mapper (that uses a hash map to group things and walk the map to emit grouped key value
pairs, where values can be counts or lists, at the end of the map method) than rearchitecting
the current data path.

> Grouping using hashing instead of sorting
> -----------------------------------------
>
>                 Key: MAPREDUCE-1639
>                 URL: https://issues.apache.org/jira/browse/MAPREDUCE-1639
>             Project: Hadoop Map/Reduce
>          Issue Type: New Feature
>            Reporter: Joydeep Sen Sarma
>
> most applications of map-reduce care about grouping and not sorting. Sorting is a (relatively
expensive) way to achieve grouping. In order to achieve just grouping - one can:
> - replace the sort on the Mappers with a HashTable - and maintain lists of key-values
against each hash-bucket.
> - key-value tuples inside each hash bucket are sorted - before spilling or sending to
Reducer. Anytime this is done - Combiner can be invoked.
> - HashTable is serialized by hash-bucketid. So merges (of either spills or Map Outputs)
works similar to today (at least there's no change in overall compute complexity of merge)
> Of course this hashtable has nothing to do with partitioning. it's just a replacement
for map-side sort.
> --
> this is (pretty much) straight from the MARS project paper: http://www.cse.ust.hk/catalac/papers/mars_pact08.pdf.
They report a 45% speedup in inverted index calculation using hashing instead of sorting (reference
implementation is NOT against Hadoop though).

-- 
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.


Mime
View raw message