[ https://issues.apache.org/jira/browse/MAHOUT-1286?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13736992#comment-13736992 ]
Peng Cheng commented on MAHOUT-1286: ------------------------------------ Here is my final solution after numerous experiments: A combination of double hashing for storing user/item IDs and 2d hopscotch hashing (http://mcg.cs.tau.ac.il/papers/disc2008-hopscotch.pdf) for storing preferences as a map from user/item indices in the double hashing table. Hopscotch hashing maintains strong locality and high load factor, and each dimension uses an independent hash function. As a result, it can quickly extract a submatrix or single row or column. This is the smallest implementation I can think of, apparently only bloom map can achieve smaller memory footage. But it has many other problems. > Memory-efficient DataModel, supporting fast online updates and element-wise > iteration > ------------------------------------------------------------------------------------- > > Key: MAHOUT-1286 > URL: https://issues.apache.org/jira/browse/MAHOUT-1286 > Project: Mahout > Issue Type: Improvement > Components: Collaborative Filtering > Affects Versions: 0.9 > Reporter: Peng Cheng > Assignee: Sean Owen > Attachments: InMemoryDataModel.java, InMemoryDataModelTest.java > > Original Estimate: 336h > Remaining Estimate: 336h > > Most DataModel implementation in current CF component use hash map to enable > fast 2d indexing and update. This is not memory-efficient for big data set. > e.g. Netflix prize dataset takes 11G heap space as a FileDataModel. > Improved implementation of DataModel should use more compact data structure > (like arrays), this can trade a little of time complexity in 2d indexing for > vast improvement in memory efficiency. In addition, any online recommender or > online-to-batch converted recommender will not be affected by this in > training process. -- This message is automatically generated by JIRA. If you think it was sent incorrectly, please contact your JIRA administrators For more information on JIRA, see: http://www.atlassian.com/software/jira