You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@hama.apache.org by ed...@apache.org on 2009/04/21 06:15:01 UTC
svn commit: r766968 - in /incubator/hama/trunk: ./ src/java/org/apache/hama/
src/java/org/apache/hama/algebra/ src/java/org/apache/hama/io/
src/test/org/apache/hama/
Author: edwardyoon
Date: Tue Apr 21 04:14:59 2009
New Revision: 766968
URL: http://svn.apache.org/viewvc?rev=766968&view=rev
Log:
Compute the transpose of a matrix
Added:
incubator/hama/trunk/src/java/org/apache/hama/algebra/TransposeMap.java
incubator/hama/trunk/src/java/org/apache/hama/algebra/TransposeReduce.java
Modified:
incubator/hama/trunk/CHANGES.txt
incubator/hama/trunk/src/java/org/apache/hama/AbstractMatrix.java
incubator/hama/trunk/src/java/org/apache/hama/Constants.java
incubator/hama/trunk/src/java/org/apache/hama/DenseVector.java
incubator/hama/trunk/src/java/org/apache/hama/Matrix.java
incubator/hama/trunk/src/java/org/apache/hama/algebra/DenseMatrixVectorMultMap.java
incubator/hama/trunk/src/java/org/apache/hama/algebra/DenseMatrixVectorMultReduce.java
incubator/hama/trunk/src/java/org/apache/hama/io/DoubleEntry.java
incubator/hama/trunk/src/test/org/apache/hama/TestDenseMatrix.java
incubator/hama/trunk/src/test/org/apache/hama/TestSparseMatrix.java
Modified: incubator/hama/trunk/CHANGES.txt
URL: http://svn.apache.org/viewvc/incubator/hama/trunk/CHANGES.txt?rev=766968&r1=766967&r2=766968&view=diff
==============================================================================
--- incubator/hama/trunk/CHANGES.txt (original)
+++ incubator/hama/trunk/CHANGES.txt Tue Apr 21 04:14:59 2009
@@ -3,7 +3,8 @@
Trunk (unreleased changes)
NEW FEATURES
-
+
+ HAMA-174: Compute the transpose of a matrix (edwardyoon)
HAMA-162: Add Graph using Sparse Matrix (edwardyoon)
HAMA-151: Add multiplication example of file matrices (edwardyoon)
HAMA-145: Add privacy policy page (edwardyoon)
Modified: incubator/hama/trunk/src/java/org/apache/hama/AbstractMatrix.java
URL: http://svn.apache.org/viewvc/incubator/hama/trunk/src/java/org/apache/hama/AbstractMatrix.java?rev=766968&r1=766967&r2=766968&view=diff
==============================================================================
--- incubator/hama/trunk/src/java/org/apache/hama/AbstractMatrix.java (original)
+++ incubator/hama/trunk/src/java/org/apache/hama/AbstractMatrix.java Tue Apr 21 04:14:59 2009
@@ -40,10 +40,14 @@
import org.apache.hadoop.hbase.mapred.TableMap;
import org.apache.hadoop.hbase.mapred.TableMapReduceUtil;
import org.apache.hadoop.hbase.util.Bytes;
+import org.apache.hadoop.io.IntWritable;
+import org.apache.hadoop.io.MapWritable;
import org.apache.hadoop.mapred.JobConf;
import org.apache.hadoop.mapred.MapReduceBase;
import org.apache.hadoop.mapred.OutputCollector;
import org.apache.hadoop.mapred.Reporter;
+import org.apache.hama.algebra.TransposeMap;
+import org.apache.hama.algebra.TransposeReduce;
import org.apache.hama.io.VectorUpdate;
import org.apache.hama.util.BytesUtil;
import org.apache.hama.util.JobManager;
@@ -371,6 +375,30 @@
closed = true;
}
+ public Matrix transpose() throws IOException {
+ Matrix result;
+ if(this.getType().equals("SparseMatrix")) {
+ result = new SparseMatrix(config);
+ } else {
+ result = new DenseMatrix(config);
+ }
+
+ JobConf jobConf = new JobConf(config);
+ jobConf.setJobName("transpose MR job" + result.getPath());
+
+ jobConf.setNumMapTasks(config.getNumMapTasks());
+ jobConf.setNumReduceTasks(config.getNumReduceTasks());
+
+ TransposeMap.initJob(this.getPath(), TransposeMap.class, IntWritable.class,
+ MapWritable.class, jobConf);
+ TransposeReduce.initJob(result.getPath(),
+ TransposeReduce.class, jobConf);
+
+ JobManager.execute(jobConf);
+ result.setDimension(this.getRows(), this.getColumns());
+ return result;
+ }
+
public boolean save(String aliasename) throws IOException {
// mark & update the aliase name in "alise:name" meta column.
// ! one matrix has only one aliasename now.
Modified: incubator/hama/trunk/src/java/org/apache/hama/Constants.java
URL: http://svn.apache.org/viewvc/incubator/hama/trunk/src/java/org/apache/hama/Constants.java?rev=766968&r1=766967&r2=766968&view=diff
==============================================================================
--- incubator/hama/trunk/src/java/org/apache/hama/Constants.java (original)
+++ incubator/hama/trunk/src/java/org/apache/hama/Constants.java Tue Apr 21 04:14:59 2009
@@ -19,6 +19,8 @@
*/
package org.apache.hama;
+import org.apache.hadoop.io.Text;
+
/**
* Some constants used in the Hama
*/
@@ -89,4 +91,6 @@
/** block data column */
public static final String BLOCK = "block:";
+
+ public static final Text ROWCOUNT= new Text("row");
}
Modified: incubator/hama/trunk/src/java/org/apache/hama/DenseVector.java
URL: http://svn.apache.org/viewvc/incubator/hama/trunk/src/java/org/apache/hama/DenseVector.java?rev=766968&r1=766967&r2=766968&view=diff
==============================================================================
--- incubator/hama/trunk/src/java/org/apache/hama/DenseVector.java (original)
+++ incubator/hama/trunk/src/java/org/apache/hama/DenseVector.java Tue Apr 21 04:14:59 2009
@@ -27,7 +27,6 @@
import org.apache.hadoop.hbase.io.RowResult;
import org.apache.hadoop.io.IntWritable;
import org.apache.hadoop.io.MapWritable;
-import org.apache.hadoop.io.Text;
import org.apache.hadoop.io.Writable;
import org.apache.hama.io.DoubleEntry;
import org.apache.log4j.Logger;
@@ -52,7 +51,7 @@
public DenseVector(int row, MapWritable m) {
this.entries = m;
- this.entries.put(new Text("row"), new IntWritable(row));
+ this.entries.put(Constants.ROWCOUNT, new IntWritable(row));
}
/**
@@ -99,7 +98,7 @@
}
public void setRow(int row) {
- this.entries.put(new Text("row"), new IntWritable(row));
+ this.entries.put(Constants.ROWCOUNT, new IntWritable(row));
}
/**
@@ -122,7 +121,7 @@
}
public int getRow() {
- return ((IntWritable) this.entries.get(new Text("row"))).get();
+ return ((IntWritable) this.entries.get(Constants.ROWCOUNT)).get();
}
/**
@@ -293,7 +292,7 @@
*/
public DenseVector subVector(int i0, int i1) {
DenseVector res = new DenseVector();
- if (this.entries.containsKey(new Text("row")))
+ if (this.entries.containsKey(Constants.ROWCOUNT))
res.setRow(this.getRow());
for (int i = i0; i <= i1; i++) {
Modified: incubator/hama/trunk/src/java/org/apache/hama/Matrix.java
URL: http://svn.apache.org/viewvc/incubator/hama/trunk/src/java/org/apache/hama/Matrix.java?rev=766968&r1=766967&r2=766968&view=diff
==============================================================================
--- incubator/hama/trunk/src/java/org/apache/hama/Matrix.java (original)
+++ incubator/hama/trunk/src/java/org/apache/hama/Matrix.java Tue Apr 21 04:14:59 2009
@@ -242,6 +242,14 @@
}
/**
+ * Transposes the matrix. In most cases, the matrix must be square
+ * for this to work.
+ *
+ * @return the transposed matrix
+ */
+ public Matrix transpose() throws IOException;
+
+ /**
* Save to a table or file
*
* @param path
Modified: incubator/hama/trunk/src/java/org/apache/hama/algebra/DenseMatrixVectorMultMap.java
URL: http://svn.apache.org/viewvc/incubator/hama/trunk/src/java/org/apache/hama/algebra/DenseMatrixVectorMultMap.java?rev=766968&r1=766967&r2=766968&view=diff
==============================================================================
--- incubator/hama/trunk/src/java/org/apache/hama/algebra/DenseMatrixVectorMultMap.java (original)
+++ incubator/hama/trunk/src/java/org/apache/hama/algebra/DenseMatrixVectorMultMap.java Tue Apr 21 04:14:59 2009
@@ -1,3 +1,22 @@
+/**
+ * Copyright 2007 The Apache Software Foundation
+ *
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
package org.apache.hama.algebra;
import java.io.IOException;
Modified: incubator/hama/trunk/src/java/org/apache/hama/algebra/DenseMatrixVectorMultReduce.java
URL: http://svn.apache.org/viewvc/incubator/hama/trunk/src/java/org/apache/hama/algebra/DenseMatrixVectorMultReduce.java?rev=766968&r1=766967&r2=766968&view=diff
==============================================================================
--- incubator/hama/trunk/src/java/org/apache/hama/algebra/DenseMatrixVectorMultReduce.java (original)
+++ incubator/hama/trunk/src/java/org/apache/hama/algebra/DenseMatrixVectorMultReduce.java Tue Apr 21 04:14:59 2009
@@ -1,3 +1,22 @@
+/**
+ * Copyright 2007 The Apache Software Foundation
+ *
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
package org.apache.hama.algebra;
import java.io.IOException;
Added: incubator/hama/trunk/src/java/org/apache/hama/algebra/TransposeMap.java
URL: http://svn.apache.org/viewvc/incubator/hama/trunk/src/java/org/apache/hama/algebra/TransposeMap.java?rev=766968&view=auto
==============================================================================
--- incubator/hama/trunk/src/java/org/apache/hama/algebra/TransposeMap.java (added)
+++ incubator/hama/trunk/src/java/org/apache/hama/algebra/TransposeMap.java Tue Apr 21 04:14:59 2009
@@ -0,0 +1,68 @@
+/**
+ * Copyright 2007 The Apache Software Foundation
+ *
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.hama.algebra;
+
+import java.io.IOException;
+import java.util.Map;
+
+import org.apache.hadoop.io.IntWritable;
+import org.apache.hadoop.io.MapWritable;
+import org.apache.hadoop.io.Writable;
+import org.apache.hadoop.mapred.FileInputFormat;
+import org.apache.hadoop.mapred.JobConf;
+import org.apache.hadoop.mapred.MapReduceBase;
+import org.apache.hadoop.mapred.Mapper;
+import org.apache.hadoop.mapred.OutputCollector;
+import org.apache.hadoop.mapred.Reporter;
+import org.apache.hama.Constants;
+import org.apache.hama.mapred.VectorInputFormat;
+
+public class TransposeMap extends MapReduceBase implements
+ Mapper<IntWritable, MapWritable, IntWritable, MapWritable> {
+ private IntWritable nKey = new IntWritable();
+
+ public static void initJob(String path, Class<TransposeMap> map,
+ Class<IntWritable> outputKeyClass, Class<MapWritable> outputValueClass,
+ JobConf jobConf) {
+
+ jobConf.setMapOutputValueClass(outputValueClass);
+ jobConf.setMapOutputKeyClass(outputKeyClass);
+ jobConf.setMapperClass(map);
+
+ jobConf.setInputFormat(VectorInputFormat.class);
+ FileInputFormat.addInputPaths(jobConf, path);
+ jobConf.set(VectorInputFormat.COLUMN_LIST, Constants.COLUMN);
+ }
+
+ @Override
+ public void map(IntWritable key, MapWritable value,
+ OutputCollector<IntWritable, MapWritable> output, Reporter reporter)
+ throws IOException {
+
+ for(Map.Entry<Writable, Writable> e : value.entrySet()) {
+ MapWritable val = new MapWritable();
+ nKey.set(((IntWritable) e.getKey()).get());
+ val.put(key, e.getValue());
+ output.collect(nKey, val);
+ val.clear();
+ }
+
+ }
+}
Added: incubator/hama/trunk/src/java/org/apache/hama/algebra/TransposeReduce.java
URL: http://svn.apache.org/viewvc/incubator/hama/trunk/src/java/org/apache/hama/algebra/TransposeReduce.java?rev=766968&view=auto
==============================================================================
--- incubator/hama/trunk/src/java/org/apache/hama/algebra/TransposeReduce.java (added)
+++ incubator/hama/trunk/src/java/org/apache/hama/algebra/TransposeReduce.java Tue Apr 21 04:14:59 2009
@@ -0,0 +1,66 @@
+/**
+ * Copyright 2007 The Apache Software Foundation
+ *
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.hama.algebra;
+
+import java.io.IOException;
+import java.util.Iterator;
+import java.util.Map;
+
+import org.apache.hadoop.hbase.io.BatchUpdate;
+import org.apache.hadoop.io.IntWritable;
+import org.apache.hadoop.io.MapWritable;
+import org.apache.hadoop.io.Writable;
+import org.apache.hadoop.mapred.JobConf;
+import org.apache.hadoop.mapred.MapReduceBase;
+import org.apache.hadoop.mapred.OutputCollector;
+import org.apache.hadoop.mapred.Reducer;
+import org.apache.hadoop.mapred.Reporter;
+import org.apache.hama.io.VectorUpdate;
+import org.apache.hama.mapred.VectorOutputFormat;
+
+public class TransposeReduce extends MapReduceBase implements
+Reducer<IntWritable, MapWritable, IntWritable, VectorUpdate> {
+
+ public static void initJob(String path, Class<TransposeReduce> reducer,
+ JobConf jobConf) {
+ jobConf.setOutputFormat(VectorOutputFormat.class);
+ jobConf.setReducerClass(reducer);
+ jobConf.set(VectorOutputFormat.OUTPUT_TABLE, path);
+ jobConf.setOutputKeyClass(IntWritable.class);
+ jobConf.setOutputValueClass(BatchUpdate.class);
+ }
+
+ @Override
+ public void reduce(IntWritable key, Iterator<MapWritable> values,
+ OutputCollector<IntWritable, VectorUpdate> output, Reporter reporter)
+ throws IOException {
+
+ MapWritable sum = new MapWritable();
+ while (values.hasNext()) {
+ for(Map.Entry<Writable, Writable> e: values.next().entrySet()) {
+ sum.put(e.getKey(), e.getValue());
+ }
+ }
+
+ VectorUpdate update = new VectorUpdate(key.get());
+ update.putAll(sum);
+ output.collect(key, update);
+ }
+}
Modified: incubator/hama/trunk/src/java/org/apache/hama/io/DoubleEntry.java
URL: http://svn.apache.org/viewvc/incubator/hama/trunk/src/java/org/apache/hama/io/DoubleEntry.java?rev=766968&r1=766967&r2=766968&view=diff
==============================================================================
--- incubator/hama/trunk/src/java/org/apache/hama/io/DoubleEntry.java (original)
+++ incubator/hama/trunk/src/java/org/apache/hama/io/DoubleEntry.java Tue Apr 21 04:14:59 2009
@@ -33,9 +33,6 @@
public class DoubleEntry implements Writable, Iterable<DoubleEntry> {
static final Logger LOG = Logger.getLogger(DoubleEntry.class);
protected byte[][] values;
-
- // We don't need this.
- @Deprecated
protected long[] timestamps;
/** For Writable compatibility */
Modified: incubator/hama/trunk/src/test/org/apache/hama/TestDenseMatrix.java
URL: http://svn.apache.org/viewvc/incubator/hama/trunk/src/test/org/apache/hama/TestDenseMatrix.java?rev=766968&r1=766967&r2=766968&view=diff
==============================================================================
--- incubator/hama/trunk/src/test/org/apache/hama/TestDenseMatrix.java (original)
+++ incubator/hama/trunk/src/test/org/apache/hama/TestDenseMatrix.java Tue Apr 21 04:14:59 2009
@@ -97,6 +97,15 @@
assertTrue(m1.get(0, 0) > 0);
}
+ public void testTranspose() throws IOException {
+ DenseMatrix trans = (DenseMatrix) m1.transpose();
+ for(int i = 0; i < trans.getRows(); i++) {
+ for(int j = 0; j < trans.getColumns(); j++) {
+ assertEquals(trans.get(i, j), m1.get(j, i));
+ }
+ }
+ }
+
/**
* Column vector test.
*
@@ -272,7 +281,6 @@
LOG.info(e.toString());
}
}
-
public void testEnsureForMultiplication() {
try {
Modified: incubator/hama/trunk/src/test/org/apache/hama/TestSparseMatrix.java
URL: http://svn.apache.org/viewvc/incubator/hama/trunk/src/test/org/apache/hama/TestSparseMatrix.java?rev=766968&r1=766967&r2=766968&view=diff
==============================================================================
--- incubator/hama/trunk/src/test/org/apache/hama/TestSparseMatrix.java (original)
+++ incubator/hama/trunk/src/test/org/apache/hama/TestSparseMatrix.java Tue Apr 21 04:14:59 2009
@@ -60,6 +60,15 @@
m2.close();
}
+ public void testTranspose() throws IOException {
+ SparseMatrix trans = (SparseMatrix) m1.transpose();
+ for(int i = 0; i < trans.getRows(); i++) {
+ for(int j = 0; j < trans.getColumns(); j++) {
+ assertEquals(trans.get(i, j), m1.get(j, i));
+ }
+ }
+ }
+
public void testSparsity() throws IOException {
boolean appeared = false;
for (int i = 0; i < m1.getRows(); i++) {