Tech Notes of Yi Wang

在Web页面里渲染Dot图形（Make Apache a GraphiViz Server）

2011-07-24T16:47:00.000-07:00

在Web页面里渲染Dot图形（Make Apache a GraphiViz Server）

Gibbs Sampling of Latent Dirichlet Allocation Model in Go

2011-03-25T10:23:00.000-07:00

As my first exercise on Google’s Go programming language, I wrote a Gibbs sampling training program of LDA using Go. This open source project is hosted on: http://code.google.com/p/lda-go, as a sister project of my previous LDA training and inference project in C++: http://code.google.com/p/ompi-lda/.

作为我学习Go语言的第一个练习，我用Go重写了LDA的Gibbs sampling训练程序：http://code.google.com/p/lda-go/。这个程序就作为我之前用C++写的并行LDA训练和推演程序（http://code.google.com/p/ompi-lda/）的姐妹项目吧。

Parallel LDA Gibbs Sampling Using OpenMP and MPI

2010-08-17T17:33:00.001-07:00

I created an open source project, ompi-lda, on Google Code. This project is inspired by another LDA project which I initialized at Google and a recent parallel programming effort using OpenMP by xlvector.

I Moved My Blog to Wordpress

2010-06-28T19:50:00.000-07:00

Since I found it is convenient to insert code and LaTeX math into my posts using Wordpress, I moved this blog to

http://cxwangyi.wordpress.com/

I may no longer update this blog.

Google Protocol Buffers 实用技术：解析.proto文件和任意数据文件

2010-06-21T02:03:00.000-07:00

Google Protocol Buffers 是一种非常方便高效的数据编码方式（data serialization），几乎在Google的每个产品中都用到了。本文介绍 protocol buffers 的一种高级使用方法（在Google Protocol Buffer的主页上没有的）。

Protocol Buffers 通常的使用方式如下：我们的程序只依赖于有限的几个 protocol messages。我们把这几个 message 定义在一个或者多个 .proto 文件里，然后用编译器 protoc 把 .proto 文件翻译成 C++ 语言（.h和.cc文件）。这个翻译过程把每个 message 翻译成了一个 C++ class。这样我们的程序就可以使用这些 protocol classes 了。

但是还有一种不那么常见的使用方式：我们有一批数据文件（或者网络数据流），其中包含了一些 protocol messages 内容。我们也有定义这些 protocol messages 的 .proto 文件。我们希望解析数据文件中的内容，但是不能使用 protoc 编译器。

一个例子是 codex。codex是Google内最常用的一个工具程序。它可以解析任意文件中的 protocol message 内容，并且把这些内容打印成人能方便的阅读的格式。为了能正确解析和打印数据文件内容，codex 需要定义 protocol message 的 .proto 文件。

为了实现 codex 的功能，一种ad hoc的方法是：
1 把 codex 的基本功能（比如读取数据文件，打印文件内容等）实现在一个 .cc 文件里（比如叫做 codex-base.cc)
1 对给定的 .proto 文件，调用 protoc，得到对应的 .pb.h 和 .pb.cc 文件。
1 把 codex-base.cc 和 protoc 的结果一起编译，生成一个专门解析某一个 protocol message 内容的 codex 程序。
这个办法太ad hoc了。它为每个 .protoc 文件编写一个 codex 程序。

另一个办法是，如果我们有世界上所有的 .proto 文件，那么我们把它们都预先用 protoc 编译了，链接进 codex。显然这个搞法也是不现实的。

那么codex到底是怎么实现的呢？其实它利用了 protocol buffers 没有写入文档的一些 API。闲话少说，我们来看一段用这些“神秘的API“写的代码。这段代码用于解析任意给定的 .proto 文件：

#include <google/protobuf/descriptor.h>
#include <google/protobuf/dynamic_message.h>
#include <google/protobuf/io/zero_copy_stream_impl.h>
#include <google/protobuf/io/tokenizer.h>
#include <google/protobuf/compiler/parser.h>

//-----------------------------------------------------------------------------
// Parsing given .proto file for Descriptor of the given message (by
// name).  The returned message descriptor can be used with a
// DynamicMessageFactory in order to create prototype message and
// mutable messages.  For example:
/*
DynamicMessageFactory factory;
const Message* prototype_msg = factory.GetPrototype(message_descriptor);
const Message* mutable_msg = prototype_msg->New();
*/
//-----------------------------------------------------------------------------
void GetMessageTypeFromProtoFile(const string& proto_filename,
                              FileDescriptorProto* file_desc_proto) {
using namespace google::protobuf;
using namespace google::protobuf::io;
using namespace google::protobuf::compiler;

FILE* proto_file = fopen(proto_filename.c_str(), "r");
{
 if (proto_file == NULL) {
   LOG(FATAL) << "Cannot open .proto file: " << proto_filename;
 }

 FileInputStream proto_input_stream(fileno(proto_file));
 Tokenizer tokenizer(&proto_input_stream, NULL);
 Parser parser;
 if (!parser.Parse(&tokenizer, file_desc_proto)) {
   LOG(FATAL) << "Cannot parse .proto file:" << proto_filename;
 }
}
fclose(proto_file);

// Here we walk around a bug in protocol buffers that
  // |Parser::Parse| does not set name (.proto filename) in
  // file_desc_proto.
  if (!file_desc_proto->has_name()) {
 file_desc_proto->set_name(proto_filename);
}
}

这个函数的输入是一个 .proto 文件的文件名。输出是一个 FileDescriptorProto 对象。这个对象里存储着对 .proto 文件解析之后的结果。我们接下来用这些结果动态生成某个 protocol message 的 instance（或者用C++术语叫做object）。然后可以调用这个 instance 自己的 ParseFromArray/String 成员函数，来解析数据文件中的每一条记录的内容。请看如下代码：

//-----------------------------------------------------------------------------
// Print contents of a record file with following format:
//
//   { <int record_size> <KeyValuePair> }
//
// where KeyValuePair is a proto message defined in mpimr.proto, and
// consists of two string fields: key and value, where key will be
// printed as a text string, and value will be parsed into a proto
// message given as |message_descriptor|.
//-----------------------------------------------------------------------------
void PrintDataFile(const string& data_filename,
                const FileDescriptorProto& file_desc_proto,
                const string& message_name) {
const int kMaxRecieveBufferSize = 32 * 1024 * 1024;  // 32MB
  static char buffer[kMaxRecieveBufferSize];

ifstream input_stream(data_filename.c_str());
if (!input_stream.is_open()) {
 LOG(FATAL) << "Cannot open data file: " << data_filename;
}

google::protobuf::DescriptorPool pool;
const google::protobuf::FileDescriptor* file_desc =
 pool.BuildFile(file_desc_proto);
if (file_desc == NULL) {
 LOG(FATAL) << "Cannot get file descriptor from file descriptor"
            << file_desc_proto.DebugString();
}

const google::protobuf::Descriptor* message_desc =
 file_desc->FindMessageTypeByName(message_name);
if (message_desc == NULL) {
 LOG(FATAL) << "Cannot get message descriptor of message: " << message_name;
}

google::protobuf::DynamicMessageFactory factory;
const google::protobuf::Message* prototype_msg =
 factory.GetPrototype(message_desc);
if (prototype_msg == NULL) {
 LOG(FATAL) << "Cannot create prototype message from message descriptor";
}
google::protobuf::Message* mutable_msg = prototype_msg->New();
if (mutable_msg == NULL) {
 LOG(FATAL) << "Failed in prototype_msg->New(); to create mutable message";
}

uint32 proto_msg_size; // uint32 is the type used in reocrd files.
  for (;;) {
 input_stream.read((char*)&proto_msg_size, sizeof(proto_msg_size));

 if (proto_msg_size > kMaxRecieveBufferSize) {
   LOG(FATAL) << "Failed to read a proto message with size = "
              << proto_msg_size
              << ", which is larger than kMaxRecieveBufferSize ("
              << kMaxRecieveBufferSize << ")."
              << "You can modify kMaxRecieveBufferSize defined in "
              << __FILE__;
 }

 input_stream.read(buffer, proto_msg_size);
 if (!input_stream)
   break;

 if (!mutable_msg->ParseFromArray(buffer, proto_msg_size)) {
   LOG(FATAL) << "Failed to parse value in KeyValuePair:" << pair.value();
 }

 cout << mutable_msg->DebugString();
}

delete mutable_msg;
}

这个函数需要三个输入：1）数据文件的文件名，2）之前GetMessageTypeFromProtoFile函数返回的FileDescriptorProto对象，3）数据文件中每条记录的对应的protocol message 的名字（注意，一个 .proto 文件里可以定义多个 protocol messages，所以我们需要知道数据记录对应的具体是哪一个 message）。

以上代码中利用了 DescriptorPool 从 FileDescriptorProto 解析出 FileDescriptor（描述 .proto 文件中所有的 messages）。然后用 DynamicMessageFactory 从 FileDescriptor 里找到我们关注的那个 message 的 MessageDescriptor。接下来，我们利用 DynamicMessageFactory 根据 MessageDescriptor 得到一个 prototype message instance。注意，这个 instance 是不能往里面写内容的（immutable）。我们需要调用其 New 成员函数，来生成一个 mutable 的 instance。

有了一个对应数据记录的 message instance，接下来就好办了。我们读取数据文件中的每条记录。注意：此处我们假设数据文件中以此存放了一条记录的长度，然后是记录内容，接下来是第二条记录的长度和内容，以此类推。所以在上述函数中，我们循环的读取记录长度，然后解析记录内容。值得注意的是，解析内容利用的是 mutable message instance 的 ParseFromArrary 函数；它需要知道记录的长度。因此我们必须在数据文件中存储每条记录的长度。

接下来这段程序演示如何调用 GetMessageTypeFromProtoFile 和 PrintDataFile：

int main(int argc, char** argv) {
string proto_filename, message_name;
vector<string> data_filenames;
FileDescriptorProto file_desc_proto;

ParseCmdLine(argc, argv, &proto_filename, &message_name, &data_filenames);
GetMessageTypeFromProtoFile(proto_filename, &file_desc_proto);

for (int i = 0; i < data_filenames.size(); ++i) {
 PrintDataFile(data_filenames[i], file_desc_proto, message_name);
}

return 0;
}

Intel’s Single-chip Cluster Computer

2010-06-10T00:49:00.000-07:00

I just read a post on Intel's single-chip cluster computer. This is really a unique thing: multiple cores in a chip, each core has its own private-and-fast memory: cache. Main memory becomes more like the NFS. Programmers write programs for this chip using MPI.

So, this chip is a cluster with super-fast network connection (64GB/s) and very limited memory (because they are implemented as cache).

How to Install Dropbox in Ubuntu Using SOCKS Proxy

2010-06-05T05:35:00.000-07:00

As a Chinese, I live behind the G.F.W. and have to get access Internet through an SSH tunnel. However, the Dropbox installation procedure do not support either SOCKS5 or http proxy. (Yes, the document says it works with http_proxy environment variable, but seems it does not.) Thanks to two great tools: proxychains and tsocks, which can launch any application and handle their network communication request through a pre-configured proxy. With the help of these tools, I can install Dropbox on a brand new Ubuntu machine behind the G.F.W. Here follows the steps:

Install tsocks (or proxychains) under Ubuntu using synaptic. Thanks to Ubuntu, who made these tools standard packages.
Get a SSH tunnel (in any way you like). I paid for an account. So I can setup a proxy tunnel by the following command line on my computer:
```
ssh -D 7070 my-username@my-service-provider-url
```
Configure your Web browser to use the tunnel. In Firefox, select to use SOCKS5 proxy: localhost:7070. This enables you access to Dropbox's homepage and download the Ubuntu package.
Install the package by clicking it in Nautilus. To check the installation, in a shell, type the command
```
dropbox start -i
```
If you can see some error messages complaining network access restriction, you made it.
Add the following lines to /etc/tsocks.conf:
```
server = 127.0.0.1
server_type = 5
server_port = 7070
```
If you are using proxychains, you need to modify /etc/proxychains.conf or make your own ~/.proxychains.conf.
This time, using tsocks to launch the Dropbox online install procedure:
```
tsocks dropbox start -i
```
Cross your fingers and wait for it to download and install Dropbox, until you see Dropbox icon appears on the top-right corner of your screen.
Right-click Dropbox icon, select "Preferences", and set SOCKS5 proxy like you did for Firefox. Hopefully, Dropbox starts to sync files you need now.

Good luck!

Building Distributed Programs Using GCC

2010-06-04T06:07:00.000-07:00

In the case of distributed computing, a program is build (into a binary) and distributed on multiple computers for running. It is often that we do not want to install libraries depended by our program on every working computers. Instead, we can instruct GCC to link static libraries by setting the environment variable:

LDFLAGS=-static -static-libgcc

I have tried this method under Cygwin and Ubuntu Linux. However, if I do this under Darwin (Mac OS X 10.6 Snow Leopard), the linker complains that

ld: library not found for -lcrt0.o

In this Technical Q&A, Apple explains that they want to make Mac OS X upgrading easier, so they do not provide crt0.o to encourage dynamic linking.

Uint64 Constants

2010-06-03T22:51:00.000-07:00

If we write uint64 a = 0xffffffffffffffff;, the compiler often complains:

error: integer constant is too large for ‘long’ type

What we need is to add the LLU suffix: uint64 a = 0xffffffffffffffffLLU;

Launch a Series of Hadoop Pipes Task

2010-06-02T19:32:00.000-07:00

It is OK to call runTask multiple times from within main() in a Hadoop Pipes program to launch a series of MapReduce tasks. However, one thing to remember: MapReduce tasks must not have conflicts output directory, because Hadoop runtime does not start a MapReduce task whose output directory exists.

Incremental Parsing Using Boost Program Options Library

2010-06-02T01:06:00.000-07:00

I have to say I fell in love with boost::program_options since the first time I use it in developing my own C++ MapReduce implementation. It can parse command line parameters as well as configuration files. This makes it convenient for programs which supports and expects a bunch of options, where a MapReduce program is a typical example.

A special use-case of a command line parser is that a function need to parse some options out from the command line parameters, and then the rest parameters are passed to another function, which parse other options. For example, the MapReduce runtime requires to get options like "num_map_workers", "num_reduce_workers", etc, and the rest of the program (user customized map and reduce functions) need to parse application-specific options like "topic_dirichlet_prior", "num_lda_topics", etc. boost::program_options supports such kind of multi-round parsing, where the key is boost::program_options::allow_unregistered(). Here attaches a sample program: (For more explanation on this program, please refer to the official document of boost::program_options.)


#include <iostream>
#include <string>
#include <vector>

#include <boost/program_options/option.hpp>
#include <boost/program_options/options_description.hpp>
#include <boost/program_options/variables_map.hpp>
#include <boost/program_options/parsers.hpp>

using namespace std;
namespace po = boost::program_options;

int g_num_map_workers;
int g_num_reduce_workers;

vector<string> foo(int argc, char** argv) {
 po::options_description desc("Supported options");
 desc.add_options()
   ("num_map_workers", po::value<int>(&g_num_map_workers), "# map workers")
   ("num_reduce_workers", po::value<int>(&g_num_reduce_workers), "# reduce workers")
   ;
 po::variables_map vm;
 po::parsed_options parsed =
   po::command_line_parser(argc, argv).options(desc).allow_unregistered().run();
 po::store(parsed, vm);
 po::notify(vm);

 cout << "The following options were parsed by foo:\n";
 if (vm.count("num_map_workers")) {
   cout << "num_map_workers = " << g_num_map_workers << "\n";
 }
 if (vm.count("num_reduce_workers")) {
   cout << "num_reduce_workers = " << g_num_reduce_workers << "\n";
 }

 return po::collect_unrecognized(parsed.options, po::include_positional);
}

void bar(vector<string>& rest_args) {
 po::options_description desc("Supported options");
 desc.add_options()
   ("apple", po::value<int>(), "# apples")
   ;
 po::variables_map vm;
 po::parsed_options parsed =
   po::command_line_parser(rest_args).options(desc).allow_unregistered().run();
 po::store(parsed, vm);
 po::notify(vm);

 cout << "The following options were parsed by bar:\n";
 if (vm.count("apple")) {
   cout << "apple = " << vm["apple"].as<int>() << "\n";
 }
}

int main(int argc, char** argv) {
 vector<string> rest_options = foo(argc, argv);

 cout << "The following cmd args cannot not be recognized by foo:\n";
 for (int i = 0; i < rest_options.size(); ++i) {
   cout << rest_options[i] << "\n";
 }

 bar(rest_options);
}

Finally I have to tell that early boost version (e.g., 1.33.1 packed in Cygwin) has bugs in program_options, which leads to core dump in case of unknown options. The solution to download and build your own boost libraries. I just built 1.43.0 on Cygwin on my Windows computer.

The Efficiency of AWK Associative Array

2010-05-23T07:22:00.000-07:00

I did a little experiment comparing C++ STL map with AWK associative array in counting word frequency of large text files. The result is astonishing: AWK associative array is about 6 times faster than the C++ code!

At first, I put my eyes on the C++ code that splits a line into words. I tried STL istringstream, C strtok_r, and a string splitting trick that I learned in Google. However, these choices do not affect the efficiency saliently.

Then I realized the lesson I learned from parallel LDA (a machine learning method, which has been a key part of my research for over three years) --- map is about 10 times slower than map. I found that this issue has been thoroughly explained by Lev Kochubeevsky, principle engineer at Netscape, in 2003. Unfortunately, seems no improvement to STL string emerged since then.

On the other hand, I highly suspect that AWK, an interpreted language, implements a trie-based data structure for maps with string-keys.

SSHFS, Poor Guys' Network File-system

2010-05-23T07:18:00.000-07:00

SSHFS is good: as long as one has SSH access, he can mount remote directories, even if he does not have administrative accesses required by traditional network filesystems like NFS or Samba.

Install and Configure MPICH2 on Ubuntu

2010-05-22T20:56:00.000-07:00

The general procedure is described in
http://developer.amd.com/documentation/articles/pages/HPCHighPerformanceLinpack.aspx#four

I have encountered two cases where MPD on multiple nodes cannot communicate with each other:

The firewall prevents such communication, and
There are ambiguity in /etc/hosts.

For 1., we can disable iptables (the firewall commonly used in various Linux versions) and ufw (Ubuntu firewall) by the following commands:
sudo iptables -P INPUT ACCEPT
sudo iptables -P OUTPUT ACCEPT
sudo ufw disable

For 2., I just re-edit /etc/hosts to ensure all nodes are referred by their real IP addresses, instead of loop-back style addresses.

Hadoop Pipes Is Incompatible with Protocol Buffers

2010-05-18T00:22:00.000-07:00

I just found another reason that I do not like Hadoop Pipes --- I cannot use a serialization of Google protocol buffer as map output key or value.

For those who are scratching your heads for weird bugs from your Hadoop Pipes programs using Google protocol buffers, please have a look at the following sample program:


#include <string>
#include <hadoop/Pipes.hh>
#include <hadoop/TemplateFactory.hh>
#include <hadoop/StringUtils.hh>

using namespace std;

class LearnMapOutputMapper: public HadoopPipes::Mapper {
public:
LearnMapOutputMapper(HadoopPipes::TaskContext& context){}
void map(HadoopPipes::MapContext& context) {
  context.emit("", "apple\norange\0banana\tpapaya");
}
};

class LearnMapOutputReducer: public HadoopPipes::Reducer {
public:
LearnMapOutputReducer(HadoopPipes::TaskContext& context){}
void reduce(HadoopPipes::ReduceContext& context) {
while (context.nextValue()) {
  string value = context.getInputValue(); // Copy content
      context.emit(context.getInputKey(), HadoopUtils::toString(value.size()));
}
}
};

int main(int argc, char *argv[]) {
return HadoopPipes::runTask(HadoopPipes::TemplateFactory<LearnMapOutputMapper,
                          LearnMapOutputReducer>());
}

The reducer outputs the size of the map output values, which contains special characters: new-line, null-term and tab. If Hadoop Pipes allows such special characters, then we should see reduce outputs 26, the length of string

"apple\norange\0banana\tpapaya".

However, unfortunately, we see 12 in the output, which is the length of string

"apple\norange"

This shows that map outputs in Hadoop Pipes cannot contain the null-term character, which, however, may appear in a serialization of protocol buffer, as explained in the protocol buffers encoding scheme at:

http://code.google.com/apis/protocolbuffers/docs/encoding.html

I hate Hadoop Pipes, a totally incomplete but released MapReduce API.

MPI-based MapReduce Implementation

2010-05-16T18:53:00.000-07:00

离开Google之后就没有那么好用的MapReduce实现了。在拼命寻找替代品的时候，发现已经有人在用 MPI 实现 MapReduce。一个 open source 实现是：
http://www.sandia.gov/~sjplimp/mapreduce/doc/Manual.html

下载之后用了一下，发现对 MapReduce API 的封装很不到位。因此编程方法根本不是在Google 使用 MapReduce 时候的那一套。相比较而言，Hadoop Pipes 对 MapReduce API 的封装更便于使用。

这就牵扯到一个问题：MapReduce 到底强在哪儿？为什么用过 Google MapReduce 的人都会喜欢它？

MapReduce 的很多优势在论文里和论坛里都有人强调过了 —— 它可以处理海量的数据，可以支持 auto fault-recovery。但是我觉得最重要的一点是 MapReduce 的 API 很简单 —— 它容许程序员通过定义一个 map 函数和一个 reduce 函数就搞定一个并行程序。所有的 distributed IO、communications、task synchronization、load balancing、fault recovery都不用用户操心。

很多人在骂 Hadoop 慢。作为一个 Java implementation，Hadoop 确实是我见过的诸多 MapReduce 实现中最慢的（实际使用起来往往比 Last.fm 的 Bash MapReduce 还要慢），但是用Hadoop的人很多。难不成原因之一就是 API 好用？

我的感觉是：如果一个 MapReduce implementation 失去了 MapReduce 给程序员带来的便利，它的其他各种优势恐怕都要大打折扣了。(离开Google一个多月，我已经记不得我写过哪些不是用 MapReduce 的程序了。)

BTW：说到这里，顺便说一下， Sphere/Sector (http://sector.sourceforge.net/doc.html) 的 API 也不是 MapReduce API 。从 Sphere Sector 的 tutorial slides 里贴一下一个demo program：

Sector::init(); Sector::login(…)
SphereStream input;
SphereStream output;
SphereProcess myProc;
myProc.loadOperator(“func.so”);
myProc.run(input, output, func, 0);
myProc.read(result)
myProc.close();
Sector::logout(); Sector::close();

可以看到各种initialization、finalization、operator-loading 之类的操作都是需要用户来写的。其实把这些封装成 MapReduce API 并没有技术难度。而封装一下可以给用户省去很多麻烦。

Running Hadoop on Mac OS X (Single Node)

2010-04-19T08:26:00.000-07:00

I installed Hadoop, built its C++ components, and built and ran Pipes programs on my iMac running Snow Leopard.

Installation and Configuration

Basically, I followed Michael G. Noll's guide, Running Hadoop On Ubuntu Linux (Single-Node Cluster), with two things different from the guide.

In Mac OS X, we need to choose to use Sun's JVM. This can be done using System Preference. Then In both .bash_profile and $HADOOP_HOME/conf/hadoop-env.sh, set the JAVA_HOME environment variable:
export JAVA_HOME=/System/Library/Frameworks/JavaVM.framework/Versions/1.6.0/Home

I did not create special account for running Hadoop. (I should, for security reasons, but I am lazy and my iMac is only for personal development, but not real computing...) So, I need to chmod a+rwx /tmp/hadoop-yiwang, where yiwang is my account name, as well what ${user.name} refers to in core-site.xml.

After finishing installation and configuration, we should be able to start all Hadoop services, build and run Hadoop Java programs, and monitor their activities.

Building C++ Components

Because I do nothing about Java, I write Hadoop programs using Pipes. The following steps build Pipes C++ library in Mac OS X:

Install XCode and open a terminal window
cd $HADOOP_HOME/src/c++/utils
./configure
make install
cd $HADOOP_HOME/src/c++/pipes
./configure
make install

Note that you must build utils before pipes.

Build and Run Pipes Programs

The following command shows how to link to Pipes libraries:

g++ -o wordcount wordcount.cc \
-I${HADOOP_HOME}/src/c++/install/include \
-L${HADOOP_HOME}/src/c++/install/lib \
-lhadooputils -lhadooppipes -lpthread

To run the program, we need a configuration file, as shown by Apache Hadoop Wiki page.

Build libHDFS

There are some bugs in libHDFS of Apache Hadoop 0.20.2, but it is easy to fix them:

cd hadoop-0.20.2/src/c++/libhdfs
./configure
Remove #include "error.h" from hdfsJniHelper.c
Remove -Dsize_t=unsigned int from Makefile
make
cp hdfs.h ../install/include/hadoop
cp libhdfs.so ../install/lib

Since Mac OS X uses DYLD to mange shared libraries, you need to specify the directory holding libhdfs.so using environment variable DYLD_LIBRARY_PATH. (LD_LIBRARY_PATH does not work.):

export DYLD_LIBRARY_PATH=$HADOOP_HOME/src/c++/install/lib:$DYLD_LIBRARY_PATH

You might want to add above line into your shell configure file (e.g., ~/.bash_profile).

Get Through GFW on Mac OS X Using IPv6

2010-04-11T03:09:00.000-07:00

In my previous post, I explained how to get through the GFW on Mac OS X using Tor. Unfortunately, it seems that Tor has been banned by GFW in recently months. However, some blog posts and mailing list claims that GFW has not been able to filter IPv6 packets. So I resorted to the IPv6 tunneling protocol, Teredo. A well known software implementation of Teredo on Linux and BSD is Miredo. Thanks to darco, who recently ported Miredo to Mac OS X, in particular, 10.4, 10.5 and 10.6 with 32-bit kernel. You can drop by darco's Miredo for Mac OS X page or just download the universal installer directly. After download, click to install, and IPv6 tunneling via IPv4 is setup on your Mac.

Before you can use IPv6 to get through the GFW, you need to know IPv6 addresses of the sites you want to visit. You must add these addresses into your /etc/hosts file, so the Web browser has no need to resolve the addresses via IPv4 (which is under monitoring by GFW). This Google Doc contains IPv6 addresses to most Google services (including Youtube).

Customizing Mac OS X 10.6 For a Linux User

2010-03-27T18:38:00.000-07:00

I have been a Linux user for years, and changed to Mac OS X 10.6 Snow Leopard in recent months. Here follows things I've done for Snow Leopard to make it suit for my work habits.

Emacs.
I prefer Aquamacs version 20.1preview5 than the stable version 19.x when I wrote this post. Aquamacs has many useful Emacs plugins packed already, including AUCTeX for LaTeX editing.
PdfTk.
Under Unix, Emacs/AUCTeX invokes pdf2dsc (a component in the pdftk package) to do inline preview in PDFLaTeX mode. Under Mac OS X, thanks to Frédéric Wenzel, who created a DMG of PdfTk for us.
LaTeX/PDF Preview.
There is a free PDF viewer, Skim, under Mac OS X, which works like the ActiveDVI Viewer under Linux, but displays PDF files instead of DVI. Whenever you edit your LaTeX source and recompile, Skim will update automatically what it is displaying.
Terminal.
As many others, I use iTerm. To support bash shortcut keys like Alt-f/b/d, you need to customize iTerm as suggested by many Google search results. In particular, remember to select "High interception priority" when you do such customization for iTerm under Snow Leopard.

Chrome 的安全机制

2010-03-27T00:18:00.000-07:00

今天看到多篇新闻报道：在 Pwn2Own 2010 黑客大赛上，针对各种浏览器的攻击中，只有 Google Chrome 屹立不倒。随便 Google 一下，会发现很多黑客把 Chrome 的安全性归结于 Chrome 的 sandbox（沙箱）机制。我因此好奇的看了看 Chromium（Google Chrome 的 open source project）的文档,

大概了解了一下 Chrome sandbox 的基本原理。

Chrome 会启动两类进程：target 和 broker：

Target 进程执行那些容易被黑客影响并做坏事的工作；主要包括（1）Javascript 程序的解释，和（2）HTML rendering。Target 进程是由 broker 进程创建的。创建之初，broker 就把 target 进程的各种访问权限都剥夺了。也就是说虽然 target 进程可以像所有用户态进程那样通过操作系统调用，请操作系统内核做事，但是操作系统内核会认为 target 进程没有权限，因而拒绝之。【注：在现代操作系统中，用户进程对任何系统资源的访问都得通过“请操作系统内核帮忙”来完成。】所以 target 实际上只能通过进程间调用，请 broker 进程来帮忙做事。
Broker 进程扮演着操作系统内核的角色 —— 因为 broker 进程执行的代码是浏览器的作者写的，并且不易被坏人注入坏代码，所以我们可以依赖它检查 target 进程请它做的事情是不是靠谱。如果不靠谱，则拒绝之。

简单的说，Chrome 的 sandbox 机制复制了操作系统的两层安全概念 —— 用户进程（target 进程）没实权，实权由操作系统内核（broker 进程）把持。实际上是装了第二把锁 —— 当用户和第三方软件对操作系统的错误配置导致操作系统安全机制失效的时候，第二把锁的作用就显示出来了。

Data-Intensive Text Processing with MapReduce

2010-03-26T18:50:00.000-07:00

A book draft, Data-Intensive Text Processing with MapReduce, on parallel text algorithms with MapReduce can be found here. This book has chapters covering graph algorithms (breath-first traversal and PageRank) and learning HMM using EM. The authors work great on presenting concepts using figures, which are comprehensive and intuitive.

Indeed, there are many other interesting stuff you can put into a book on MapReducing text processing algorithms. For example, parallel latent topic models like latent Dirichlet allocation, and tree pruning/learning algorithms for various purposes.

Stochastic Gradient Tree Boosting

2010-03-26T08:47:00.000-07:00

The basic idea of boosting as functional gradient descent and stages/steps as trees, known by gradient boosting, is presented by a Stanford paper:

Jerome Friedman. Greedy Function Approximation: A Gradient Boosting Machine. The Annuals of Statistics. 2001

The same author wrote a note on extending gradient boosting into its stochastic version, stochastic gradient boosting:

Jerome Friedman. Stochastic Gradient Boosting. 1999.

The (stochastic) gradient boosting use regression/classification trees as base learners, and needs to learn trees in the procedure of training. If you are interesting with distributed learning of trees using MapReduce, you might want to refer to a recent Google paper:

PLANET: Massively Parallel Learning of Tree Ensembles with MapReduce. VLDB 2009

A recent Yahoo paper shows implementing stochastic boosted decision trees using MPI and Hadoop:

Stochastic Gradient Boosted Distributed Decision Trees. CIKM 2009

Fwd: Ten Commands Every Linux Developer Should Know

2010-03-24T19:38:00.000-07:00

I like this article in Linux Journal, which reveals some very useful Linux commands that I have never used in my years experience with Unix's.

Some Interesting Data Sets

2010-03-15T20:40:00.000-07:00

The ArXiv data set, including full text, abstract/title and citations:
http://www.cs.cornell.edu/projects/kddcup/datasets.html
The CiteSeer dataset, including Dublin core standard fields and citations:
http://citeseer.ist.psu.edu/oai.html

Could Latent Dirichlet Allocation Hanlde Documents with Various Length?

2010-02-27T07:17:00.001-08:00

I heart some of my colleagues who are working on another latent topic model, which is different from LDA, complains that LDA like documents with similar lengths. I agree with this. But I feel that can be fixed easily. Here follows what I think.

The Gibbs sampling algorithm of LDA samples latent topic assignments from as follows

where V is the vocabulary size and L_d is the length of document d.

The second term is dependent with the document length. Just consider an example document is about two topics, A, and B, and half of its words are assigned topic A, the other half are assigned topic B. So the P(z|d) distribution should have two high bins (height proportional to L/2 + alpha), and all elsewhere are short bins (height proportional to alpha). So, you see, if the document has 1000 words, alpha has trivial effect to the shape of P(z|d); but if the document contains only 2 words, alpha would have more effects on building the shape of P(z|d).

An intuitive solution to above problem is to use small alpha for short document (and vice versa). But would this break the math assumptions under LDA? No. Because this is equivalent to use different symmetric Dirichlet prior on documents with different lengths. This does not break the Dirichlet-multinomial conjugacy required by LDA's Gibbs sampling algorithm, but just express a little more prior knowledge than using a symmetric prior for all documents. Let us set

for each document. And users need to specify parameter k as they need to specify alpha before.

S-shaped Functions

2010-02-21T23:33:00.000-08:00

The logit (logistic sigmoid) function:

The tanh function:

The probit function:

where

For more on this approximation, look at Figure 4.9 of Pattern Recognition and Machine Learning.

Cavendish Experiment and Modern Machine Learning

2010-02-20T01:23:00.000-08:00

This is just a joke, so do not follow it seriously...

The very usual case in modern machine learning is as follows:

design a model to describe the data, for example, suppose some kind of 2D points are generated along a quadratic curve y = a*x^2 + b*x + c, and
design an algorithm that estimates the model parameters, in our case, a, b, and c, given a set of data (observations), x_1,y_1,x_2,y_2,...x_n,y_n.
The model parameters can be used in some way, say, given a new x and predict its corresponding y.

So, when I was reading Prof. Feynman's lecture notes, which mentions Cavendish experiment, I thought this experiment is some kind of "learning using machines" --- using the specially designed equipment (machine), Cavendish measured the gravitational constant G in Newton's law of universal gravitation:

F = G * m1 * m2 / r^2

And, using the estimated model parameter G, we can do somethings interesting. For example, measure the weight of the earth (by measuring the weight/gravity F of a known small ball m1, and put them back into the equation to get m2, the mass of earth).

However, this is a joke as I said so you cannot use it in your lecture notes on machine learning. The fact was that Cavendish did not measure G as stated in many textbooks. Instead, he measures the earth directly by comparing (1) the force that a big ball with known mass attracts a small ball with (2) the force that the earth attracts the small ball. If the ratio (2)/(1) is N, then the earth is N times weight of the big ball.

Highlights in LaTeX

2010-02-14T18:29:00.000-08:00

To make part of the text highlighted in LaTeX, use the following two packages

\usepackage{color}
\usepackage{soul}

And in the text, use macro \hl:

The authors use \hl{$x=100$ in their demonstration}.

Note that if you use only soul without color, \hl just fails to underlines.

A Tutorial on Network Traffic Analysis

2010-02-08T02:27:00.000-08:00

http://www.chrissanders.org/?p=47

Google Puts New Focus on Outside Research

2010-02-04T19:35:00.000-08:00

It is recently reported that Google is stepping up its funding to support the research following four areas:

machine learning
the use of cellphones as data collection devices in science
energy efficiency
privacy

Among these four areas, machine learning is on the top. "Three years ago, three of the four research areas would not have been on the company’s priority list", Mr. Spector said. "The only one that was a priority then and now is machine learning, a vital ingredient in search technology."

Reduce Data Correlation by Recenter and Rescale

2010-02-03T23:31:00.000-08:00

In the MATLAB statistics demo document, the training data (a set of car weights) are recentered and rescaled as follows:

% A set of car weights
weight = [2100 2300 2500 2700 2900 3100 3300 3500 3700 3900 4100 4300]';
weight = (weight-2800)/1000;     % recenter and rescale

And the document explains the reason of recenter and rescale as

The data include observations of weight, number of cars tested, and number failed. We will work with a transformed version of the weights to reduce the correlation in our estimates of the regression parameters.

Could anyone tell me why the recenter and rescale can reduce the correlation?

Using aMule with VeryCD

2010-02-02T19:27:00.001-08:00

http://hi.baidu.com/linsir/blog/item/c4b54839805a9af73a87cea2.html

Making Videos Playable on Android and iPhone

2010-02-02T00:45:00.000-08:00

You might want to convert you home-made video (no pirated video :-!) into a format that your Android phone can play. The video formats that Android support are listed in Android developers' site:

http://developer.android.com/guide/appendix/media-formats.html

Among the listed formats, H.264 (as a realization of the MPEG-4 standard) has been well accepted by the industry. Companies including Apple has switched to it. In the following, I will show you that using open source software on a Linux box can convert your video into H.264 with AVC video and AAC audio. I took the following post as a reference, but with updates.

First of all, you need to install the following software packages:

mplayer: a multimedia player
mencoder: MPlayers's movie encoder
faac: an AAC audio encoder
gpac: a small and flexible implementaiton of the MPEG-4 system standard
x264: video encoder for the H.264/MPEG-4 AVC standard

Then we do the following steps to convert the video.avi into a .mp4 file in H.264 format.

Extract the audio information from video.avi using MPlayer:
```
mplayer -ao pcm -vc null -vo null video.avi
```
This will generate a audiodump.wav file.

Encode audiodump.wav into AAC format
```
faac --mpeg-vers 4 audiodump.wav
```
This generates a audiodump.aac file.

Use mencoder to convert the video content of video.avi into YUV 4:2:0 format, and use x264 to encode the output into AVC format
```
mkfifo tmp.fifo.yuv
mencoder -vf scale=800:450,format=i420 \
 -nosound -ovc raw -of rawvideo \
 -ofps 23.976 -o tmp.fifo.yuv video.mp4 2>&1 > /dev/null &
x264 -o max-video.mp4 --fps 23.976 --bframes 2 \
 --progress --crf 26 --subme 6 \
 --analyse p8x8,b8x8,i4x4,p4x4 \
 --no-psnr tmp.fifo.yuv 800x450
rm tmp.fifo.yuv
```
We created a named pipe to buffer between mencoder and x264. These command lines generate both Quicktime-compatible and H.264-compatible content. This is because Apple Quicktime can now hold H.264 content. Be aware to specify the same video size to mencoder and x264. In above example, the size is 800x450.

Merge the AAC audio and AVC video into a .mp4 file using gpac
```
MP4Box -add max-video.mp4 -add audiodump.aac \
  -fps 23.976 max-x264.mp4
```
MP4Box is a tool in the gpac package.

如何在Mac OS X上配置一个Web服务器

2010-02-02T00:38:00.001-08:00

最近在我的imac上配置了一个Web服务器，用于管理我自己的技术笔记。和很多朋友们一样，我的机器通过连接ADSL的无线路由器上网，所以遇到的问题应该比较典型，因此我把配置流程记录下来，和大家共享。

启动Mac OS X上的Apache

Mac OS X自带了Apache。要启动它很容易。如下图所示：启动System Preference，在Internet & Wireless类别里选择Sharing。然后勾上Web Sharing。这样Apache就启动了。

现在可以在Web浏览器的地址栏里输入http://localhost/~wangyi访问到自己的主页了。【注意wangyi是我在我的imac上的用户名，你得使用你自己的用户名取代它。】这个页面对应的HTML文件就是/Users/wangyi/Sites/index.html。可以通过编辑它来定制你自己的主页。

让大家能访问我的主页

我家是通过电信的ADSL服务上网的。为了让家里的几台电脑都能上网，我在ADSL modem上接了一个无线路由器。这样，家里的电脑启动的时候，是由无线路由器动态分配IP地址。而无线路由器的外部IP地址是电信通过ADSL服务给分配的。为了让Internet上的用户都能通过我的外部IP访问到我的Web服务，我需要在无线路由器上做一些设置【端口转发，port forwarding】，使得无线路由器能把Internet用户的访问请求转发到我的imac电脑的Web服务器程序。

我使用的是TP-LINK的TL-WR541G+无线路由器。为了访问它的配置界面，只需要在浏览器里输入http://192.168.1.1。【192.168.1.1是我的无线路由器的内部IP地址；我的imac的内部IP地址是192.168.1.100。这些是TP-LINK无线路由器的默认设置。】如下图所示：

通过在“转发规则”的“虚拟应用程序”项目中，把“触发端口”和“开放端口”都设置成80（HTTP协议的标准端口号），Internet用户就可以在浏览器里输入我的外部IP来访问我的Web服务了。

设置域名

但是现在的问题是，大家通常不知道我的外部IP，因为这是我的ISP（中国电信）分配给我的无线路由器的。但是没问题，我知道我的外部IP，所以我只要注册一个域名指向我的外部IP，然后向大家公开我的域名就可以了。

通常来说，注册域名都是要花钱的。国内只有一家叫做3322.org的公司提供免费域名注册服务。为了图个便宜，我就用3322.org了。为此，需要访问www.3322.org：

在www.3322.org的首页上，免费注册一个用户。我的用户名是cxwangyi

到“我的控制台”页面，在“动态域名”一栏下，点击“新建”。然后选择一个域名后缀。3322.org提供了几个选择。我选了7766.org。我的域名是我在3322.org的用户名加上我选择的域名后缀，也就是cxwangyi.7766.org。这个配置页面能自动检测我们的外部IP地址，所以不用我们手工输入。其他选项也都选择默认值就行了。抓图如下：

更新外部IP地址

绝大多数ISP(包括中国电信）使用DHCP协议分配IP地址。这就意味着每隔一段时间，我们的IP地址就变了。所以上一步中和cxwangyi.7766.org绑定的IP地址，过了一段时间之后可能就分配给别人的机器了。为此，我们需要时不时的通知3322.org，报告我们最新的IP地址。一个笨办法是每隔一段时间时间访问上图中的设置界面，手工更新我们的IP地址。一个聪明一些的办法是下载3322.org客户端程序，它在运行期间，会自动向3322.org汇报我们的IP地址。第三个办法是用一些标准的工具程序，访问3322.org预留的一个URL，这样我们的IP地址就自然的随着HTTP协议，发给了3322.org，并且被记录下来。3322.org的页面上建议大家使用lynx；对应的命令行是：

lynx -mime_header -auth=cxwangyi:123456 \
"http://www.3322.org/dyndns/update?system=dyndns&hostname=cxwangyi.7766.org"

其中cxwangyi是我在3322.org上注册的用户名，123456是对应的口令。cxwangyi.7766.org是上一步里我们在3322.org上注册的域名。这些你都得用你自己的。

很多系统（包括Mac OS X）没有自带lynx，但是附带了一个更简单的标准程序叫curl。用curl向3322.org汇报IP地址的命令行是：

curl -u cxwangyi:123456 \"http://www.3322.org/dyndns/update?system=dyndns&hostname=cxwangyi.7766.org"

利用curl或者lynx，以下这个非常简单的Bash脚本每隔10秒钟，就向3322.org汇报一次当时的IP地址：

while [ true ]; \
sleep 10000; \
curl -u cxwangyi:123456 \
"http://www.3322.org/dyndns/update?system=dyndns&hostname=myhost.3322.org"; \
done

用Emacs Muse创建技术内容

有了Web服务，还得有内容。有无数的工具软件用于帮助制作网页。我用的是Emacs Muse，一个Emacs插件，允许用户用一种简单的wiki语法书写内容（包括插图甚至复杂的数学公式），并且可以把结果输出成HTML（或者PDF等格式）。Emacs Muse的下载和安装可以参考其主页上的说明。安装之后，我在我的.emacs文件里加入了如下设置：

(add-to-list 'load-path "~/.emacs.d/lisp/muse")
(require 'muse-mode) ; load authoring mode
(require 'muse-html) ; load publishing styles I use
(require 'muse-latex)
(require 'muse-texinfo)
(require 'muse-docbook)
(require 'muse-latex2png) ; display LaTeX math equations
(setq muse-latex2png-scale-factor 1.4) ; the scaling of equation images.
(require 'muse-project) ; publish files in projects
(muse-derive-style
"technotes-html" "html"
:style-sheet "<link rel=\"stylesheet\" type=\"text/css\" media=\"all\" href=\"../css/wangyi.css\" />")
(setq muse-project-alist
'(("technotes" ("~/TechNotes" :default "index")
(:base "technotes-html" :path "~/Sites/TechNotes"))))

其中，~/.emacs.d/lisp/muse是我的Muse的安装目录。~/TechNotes是存储我的技术文档的目录。我的每一篇技术文档是这个目录下的一个后缀为.muse的文本文件（比如HowToSetup.muse）。当我用Emacs编辑这个文件时，只要按组合键control-c control-p，Emacs Muse就自动将这个文档输出成HTML格式，存放在~/Sites/TechNotes目录下（HowToSetup.html）。

Unix Philosophy

2010-01-20T00:28:00.000-08:00

It had been a difficult problem to compare Windows and Linux. I had been holding the idea that in the Unix world, people write small and simple programs which work together via standard linkages like pipe and other inter-process communication mechanisms. However, under Windows, people tend to write a huge program which can do everything.

An example is word processing. In the Windows world, we have Microsoft Word, which has a huge number of functions: editing, rendering (WYSIWYG), spell checking, printing, and much more. However, in the Unix world, we use the TeX system, consisting of many programs, each does one simple thing -- TeX macro defines basic typesetting functions, LaTeX defines more, Emacs (or any other editor) edits, pdfLaTeX (and other converters) converts sources into PDF or other formats, AUCTeX or Lyx implements WYSIWYG, and etc.

Well, by mentioning above, I think I am not so bad as I see at least the Separation and Composition philosophy of the Unix world. However, there are many more that I have not been able to summarize. Anyway, the lucky thing is a master had summarized them for us, so, please refer to the great book The Art of Unix Programming.

Hierarchical Classification

2010-01-19T19:18:00.000-08:00

A 2005 paper, Learning Classifiers Using Hierarchically Structured Class Taxonomies, discussed classification into a taxonomy. My general understand is that this problem can be solved by training a set of binary classifiers as the multi-label classification problem. More details delivered by this paper:

Types of Classification:

Traditional: classify instances into mutually exclusive class labels,
Multi-label: an instance may have more than one labels,
Taxonomic: multi-label and labels are from a hierarchical taxonomy.

Solutions Proposed:

Binarized: train a set of binary classifiers, each for a label in the taxonomy. In classification time, if an instance does not belongs to class C, then no need to check it with classifiers belonging to descendants of C.
Split-based: need to read more to understand this solution.

From the experiment results, it seems that above two solutions have similar performance. And both differs from the bottom-up solution that I saw in Google.

Something New about LDA and HDP

2010-01-19T19:05:00.000-08:00

The UC Irvin team have updated their work and published a JMLR 2009 paper: Distributed Algorithms for Topic Models. For HDP, they proposed a greedy approach to matching of new topics. I also like their ways to visualize the training process.

Diane Hu, a PhD student working on latent topic models for musical analysis, recently wrote a tutorial/survey on LDA, Latent Dirichlet Allocation for Text, Images, and Music, which introduced LDA basics as well its extension models for images and music.

SSH on Mac OS X

2010-01-19T17:03:00.000-08:00

This article shows how to start an SSH server on Mac OS X, how to set up loginless, and how to tunnelling unsecure protocols over SSH.

The article explains how to change the port number of SSH on Mac OS X. Note that from Mac OS X 10.4, the mechanism for launching sshd changed from using xinetd to launchd, so changing the port number becomes a little harder.

Get Across GFW Using Tor and Bridges

2010-01-18T07:55:00.000-08:00

在这个技术博客上，我很少用中文写文章。但是此文似乎只有中国用户需要看到。

作为一个中国网络用户，为了访问我的这个技术博客，我不得不翻墙。在我的iMac和MacBook Pro上，Tor是个很不错的工具。可惜最近不好用了。今晚稍微研究了一下，发现可以通过加入网桥来解决这个问题。

具体的做法是：

给bridges@torproject.org写信，内容无所谓；稍后，对方会回复一封邮件，其中有几个可用的网桥。
在Vidalia的界面中选择Settings；在Settings对话框里切换到Network页；选中“My ISP blocks connections to the Tor network”；然后通过“Add a Bridge”输入框一条一条加入邮件中的网桥。可以参见以下抓图：

Maximum Entropy Modeling

2010-01-11T06:58:00.001-08:00

http://homepages.inf.ed.ac.uk/lzhang10/maxent.html

Generate Core Dump Files

2010-01-08T07:22:00.001-08:00

If you want your program generates core dump files (including stack trace) when it encounters a segmentation fault, remember to set the following shell option

ulimit -c unlimited

Before running your program.

Once the core file is generated (say core), we can check the stack trace using GDB:

gdb program_file core

Then type GDB command

where

which will show you the stack trace.

Special Notes for Cygwin

When a process (i.e. foo.exe) cores, a default stackdump foo.exe.stackdump is generated. This stackdump contains (among other things) stack frames and functions addresses. You can make some sense of it by using the `addr2line' utility, but it's not as convenient as using a debugger.

Which takes me to the actual useful bit on information in this post. You can instruct Cygwin to start your gdb debugger just in time when an fault occurs or have Cygwin generate a real core dump.

To achieve this, add `error_start=action' to the Cygwin environment variable:

# start gdb
export CYGWIN="$CYGWIN error_start=gdb -nw %1 %2"

# generate core dump
export CYGWIN="$CYGWIN error_start=dumper -d %1 %2"

A Step-by-Step Tutorial on Autotools

2010-01-08T07:09:00.000-08:00

Autotools are so complicated for new users, however, I am lucky this evening and found an excellent step-by-step tutorial. By following it, I packed my Hadoop Streaming wrapper for C++ in few minutes! I would like to donate to the author if s/he wants. :-)

A C++ MapReduce "Implementation" Basing on Hadoop Streaming

2010-01-07T21:45:00.000-08:00

Hadoop has two mechanisms to support using languages other than Java:

Hadoop Pipes, which provides a C++ library pair to support Hadoop programs in C/C++ only, and
Hadoop Streamining, which languages any executable files in map/reduce worker processes, and thus support any languages.

However, in Hadoop 0.20.1, the support to Pipes, known as Java code in package org.apache.hadoop.mapred.pipes have been marked deprecated. So I guess Hadoop 0.20.1 has not port to fully support Pipes. Some other posts in forums also discussed this issue.

So, I would like to turn to use Streaming and C++. Michael G. Noll wrote an excellent tutorial on Streaming using Python, which shows that Streaming is equivalent to invoke your map and reduce program using the following shell command:

cat input_file | map_program | sort | reduce_program

Of couse, as you know, Hadoop runs the shell pipes on a computing cluster in parallel.

hadoop jar $HADOOP_HOME/contrib/streaming/hadoop-0.20.1-streaming.jar \
-file ./word_count_mapper -mapper ./word_count_mapper \
-file ./word_count_reducer -reducer ./word_count_reducer \
-input ./input/*.txt -output

Basing on Hadoop Streamming, I wrote a C++ MapReduce wrapper (more precisely, it should be called a MapReduce implementation, but the code is simple when built on Hadoop Streaming, that I feel embarrassed to call it an "implementation"). Anyway, I found it is interesting that this simple wrapper support secondary keys, whereas org.apache.hadoop.mapreduce does not yet. :-)

I have created a Google Code project to host this simple implementation: Hadoop Streaming MapReduce, and imported the code using the following command line:

svn import hadoop-streaming-mapreduce/ https://hadoop-stream-mapreduce.googlecode.com/svn/trunk -m 'Initial import'

. So you should be able to checkout the code now.

Map-Reduce-Merge for Join Operation

2010-01-06T00:58:00.001-08:00

In this SIGMOD 2007 paper: Map-reduce-merge: simplified relational data processing on large clusters, the authors add to Map-Reduce a Merge phase that can efficiently merge data already partitioned and sorted (or hashed) by map and reduce modules, and demonstrate that this new model can express relational algebra operators as well as implement several join algorithms.

However, I think the newly added merge stage could be implemented using another MapReduce job -- the mapper scans over key-value pairs of all lineage and output them identically; the shuffling stage will merge values of different lineage but the same key into reduce inputs; finally, the reducer can do whatever supposed to be done by merger.

Other people told me that there are more ways to do merge using MapReduce model. But above simple solution seems one of the most scalable. In short, if I am going to implement a parallel programming model given the objective to support joining of relational data, I would just implement MapReduce, rather than MapReduce-Merge.

Compare GNU GCJ with Sun's JVM

2010-01-02T23:13:00.000-08:00

On this Wikipedia page, there is a link to Alex Ramos's experiment, which compares the performance of native binary generated by GNU's GCJ from Java program and bytecode binary generated by Sun's JDK and runs on JIT JVM. As Alex did the comparison on AMD CPU, I did more additional ones. Here are the results.

System	Java version	Sum Mflops	Sqrt Mflops	Exp Mflops
2x AMD 64 5000+, Ubuntu	JIT 1.6.0_14	99	43	10
	GCJ 4.3.2	64	65	13

2x Intel Core2 2.4GHz, Ubuntu	JIT 1.6.0_0	87.4	36.9	16.6
	GCJ 4.2.4	150.6	39.3	30

Intel T2600 2.16GHz, Cygwin	JIT 1.6.0_17	45.4	34.8	10.4
	GCJ 3.4.4	84.1	23.7	12.1

The first comparison was done by Alex; I just copy-n-pasted his results. The second was done on my workstation. The third on my IBM T60p notebook computer. I also tried to do the comparison on my MacBook Pro, but MacPorts cannot build and install GCJ correctly.

Generally, GCJ beats JIT on numerical computing. However, I have to mention that it takes a lot more time to start the binary generated by GCJ. (I do not know why...)

Here attaches the Java source code (VectorMultiplication.java), which is almost identical to Alex's, but use much shorter vectors (1M v.s. 20M), so more computer can run it.


import java.util.Random;

public class VectorMultiplication {

  public static double vector_mul(double a[], double b[], int n, double c[]) {
    double s = 0;
    for (int i = 0; i < n; ++i)
      s += c[i] = a[i] * b[i];
    return s;
  }

  public static void vector_sqrt(double a[], double b[], int n) {
    for (int i = 0; i < n; ++i)
      b[i] = Math.sqrt(a[i]);
  }

  public static void vector_exp(double a[], double b[], int n) {
    for (int i = 0; i < n; ++i) 
      b[i] = Math.exp(a[i]);
  }

  public static void main(String[] args) {
    final int MEGA = 1000 * 1000;
    Random r = new Random(0);
    double a[], b[], c[];
    int n = 1 * MEGA;
    a = new double[n];
    b = new double[n];
    c = new double[n];

    for (int i = 0; i < n; ++i) {
      a[i] = r.nextDouble();
      b[i] = r.nextDouble();
      c[i] = r.nextDouble();
    }

    long start = System.currentTimeMillis();
    vector_mul(a, b, n, c);
    System.out.println("MULT MFLOPS: " +
                       n/((System.currentTimeMillis() - start)/1000.0)/MEGA);

    start = System.currentTimeMillis();
    vector_sqrt(c, a, n);
    System.out.println("SQRT MFLOPS: " +
                       n/((System.currentTimeMillis() - start)/1000.0)/MEGA);

    start = System.currentTimeMillis();
    vector_exp(c, a, n);
    System.out.println("EXP MFLOPS: " +
                       n/((System.currentTimeMillis() - start)/1000.0)/MEGA);
  }
}

On my Core2 workstation, the way I invoked GCJ is identical to that used in Alex's experiment:

gcj -O3 -fno-bounds-check -mfpmath=sse -ffast-math -march=native \
 --main=VectorMultiplication -o vec-mult VectorMultiplication.java

On my notebooks, I use

gcj -O3 -fno-bounds-check -ffast-math \
 --main=VectorMultiplication -o vec-mult VectorMultiplication.java

Learning Java as a C++ Programmer

2010-01-01T17:11:00.000-08:00

Primitive Data Types

char is 16-bit. byte is 8-bit. boolean corresponds to bool in C++.

All Java primitive types are signed.Why?

Casting

Java is more strongly typed than C++. No way to convert between boolean and integer types.

Operators

Java has two new operators, >>> and >>>=. Each of these performs a right shift with zero fill.

Java operators cannot be overloaded, in order to prevent unnecessary bugs

Struct and union

No struct or union.Arrays

Arrays are objects, defined by Type [].

Out of index accessing causes ArrayIndexOutOfBoundsException exception.

Classes

Can set default value of class data members

Comparing Technologies Inside and Outside Google

2009-12-29T00:35:00.000-08:00

Leading positions in some key technological fields have nominated Google the giant in the Internet industry. Now, the open source community and other companies are keeping up with Google in these fields. Here follows a comparison of published Google technologies and those developed outside of Google. I will update this list as I know more.

Development Tools	Inside Google	Outside Google	Remark
Code review	Mondrian	Rietveld	Both Mondrian and Rietveld are written by the inventor of Python
Infrastructure	Inside Google	Outside Google	Remark
Distributed File System	GFS	HDFS	Hadoop's distributed file system
		CloudStore	Formally known as Kosmos file system
File Format	SSTable	String Table	Hadoop's file format of entries of key-value pairs
Distributed Storage	Bigtable	Hypertable	Baidu is a main sponsor of Hypertable.
		HBase	A Hadoop sub-project as an alternative of Bigtable.
Parallel Computing	MapReduce	Hadoop	Hadoop was initiated by guys formally work in Google's MapReduce team.
Remote Procedure Call	Protocol Buffer	Thrift	Thrift was developed by Facebook and is now an Apache project.
Data Warehouse	Dremel	Hive	Hive was developed by Facebook and is now an Apache Hadoop project.
API	Inside Google	Outside Google	Remark
Networking	(I do not know)	boost.asio	boost.asio provides an C++ abstraction to network programming

Learning Boosting

2009-12-28T22:26:00.000-08:00

References

The Boosting Approach to Machine Learning An Overview, RE Schapire, 2001.
Schapire is one of the inventor of AdaBoost. This article starts with the pseudo code of AdaBoost, which is helpful to understand the basic procedure of boosting algorithms.

What is Boosting?
Boosting is a machine learning meta-algorithm for performing supervised learning. Boosting is based on the question posed by Kearns: can a set of weak learners create a single strong learner? (From Wikipedia)

Boosting Algorithms
Most boosting algorithms consist of iteratively learning weak classifiers with respect to a distribution and adding them to a final strong classifier. When they are added, they are typically weighted in some way that is usually related to the weak learners' accuracy. After a weak learner is added, the data is reweighted: examples that are misclassified gain weight and examples that are classified correctly lose weight (some boosting algorithms actually decrease the weight of repeatedly misclassified examples, e.g., boost by majority and BrownBoost). Thus, future weak learners focus more on the examples that previous weak learners misclassified.

AdaBoost
The pseudo code of AdaBoost is as follows
As we can see from this algorithm:

The weight distribution over training examples changes in each iteration, and the change ratio is determined by alpha.
The choose of alpha is not arbitrary, insteads, it is based on the error of weak learner. Reer to [1] for details.
The aggregation of weak learners uses alpha to weight each learner.

Emacs Moves to Bazaar

2009-12-28T19:34:00.000-08:00

Noticed at Solidot that Emacs has moved their version control to Bazaar, a version control system that can work in traditional centralized way or a brand new distributed way. After going over Bazaar's users guide, I feel that the distributed way is suitable for developers all over the world and working on the same project, because each developer submit code into his local repository (the reason that Bazaar is called distributed) to record his own work, and publish his work via email and SFTP. It is then becomes the responsibility of the maintainer of the main repository to merge individual's work back into the main branch. I may need to read more about this, but anyway, it is interesting.

A Small Computing Cluster on Board

2009-12-28T18:37:00.000-08:00

In my previous post, I mentioned a newly developed GPU-based parallel Gibbs sampling algorithm for inference of LDA. Of course, as you know, there are many other GPU-based parallel algorithms that can solve many interesting applications efficiently using NVidia's CUDA programming framework.

More over, by Googling "CUDA MapReduce", you will find MapReduce implementations based on CUDA and GPU, developed by researchers at UC Berkeley, U Texas, Hong Kong Univ. of Sci.&Tech, and etc.

About the supporting hardware, I recently noticed NVidia's Tesla processor board, which contains a 240-core Tesla 10 GPU and 4GB on-board memory. This card can be installed on workstations like Dell Precision T7500. At the time when this essay is written, the price of such a system is about RMB 43,000.

Last but not least, there are significant differences between GPU-clusters and relatively traditionally computer-clusters. Few listed here:

There is no mature load-balancing mechanism on GPU-clusters. Currently, GPU-based parallel computing is in the early stage of CPU-based parallel computing, which I mean, no automatic balancing over processors used by a task, and no scheduling and balancing over tasks. This prevents multiple projects from sharing a GPU-cluster.
GPU-cluster is based on shared-memory architecture, so it is suitable only for the class of computing-intensive but data-sparse tasks. I do not see more than a few problems in real world that fit in this class.

But anyway, it is not smart to compare GPU-based parallel computing directly with multi-core CPU based solutions, because the latter can be naturally incorporated into multi-computer parallel computing and achieve naturally much higher scalability.

Using Facebook Thrift

2009-12-28T02:24:00.001-08:00

While I am looking for a general RPC solution, Thrift comes to my eyes. It is now an Apache project although developed at Facebook. Thrift is very similar to Google's protocol buffer, which was open sourced and hosted on Google Code. For me, Thrift seems support more languages and deployed with a whole set of surrounding support, including thread manager and server/client stubs. More interestingly, Thrift supports exception, that is, exceptions thrown by remote methods can be caught by client code. (I do not remember that Google protocol buffer support this ....)

However, Thrift does not yet have an official tutorial, so, here is a very brief one. (I would resort to an official one once it is published.)

Download Thrift from http://incubator.apache.org/thrift
Unpack the .tar.gz file to create /tmp/thrift-0.2.0

Configure, build and install

./configure --prefix=~/wyi/thrift-0.2.0 CXXFLAGS='-g -O2'
make
make install

Generate source code from tutorial.thrift
```
cd tutorial
~wyi/thrift/bin/thrift -r --gen cpp tutorial
```
Note that the -r flag indicates generating also include files. The result source code will be placed into a sub-directory named gen-cpp.
Compile example C++ server and client programs in tutorial/cpp
```
cd cpp
make
```
Note that you might want to change the Makefile to tell the lib and include directories where Thrift was installed.

A WordCount Tutorial for Hadoop 0.20.1

2009-12-27T08:35:00.000-08:00

Because the document of Hadoop 0.20.1 describes a tutorial program which uses out-of-date APIs, I decided to write the following tutorial for Hadoop 0.20.1. It is notable that in 0.20.1, org.apache.hadoop.mapred.* are deprecated and it is recommended to use org.apache.hadoop.mapreduce.*. This tutorial is based on the new API.

For how to install and configure Hadoop, you might want to refer to my previous post. After Hadoop is installed, let us create a source code directory and put the following Java source file:

package org.sogou;

import java.io.IOException;
import java.lang.InterruptedException;
import java.util.StringTokenizer;

import org.apache.hadoop.io.IntWritable;
import org.apache.hadoop.io.Text;
import org.apache.hadoop.conf.Configuration;
import org.apache.hadoop.fs.Path;
import org.apache.hadoop.mapreduce.Job;
import org.apache.hadoop.mapreduce.Mapper;
import org.apache.hadoop.mapreduce.Reducer;
import org.apache.hadoop.mapreduce.lib.input.FileInputFormat;
import org.apache.hadoop.mapreduce.lib.output.FileOutputFormat;
import org.apache.hadoop.util.GenericOptionsParser;

public class WordCount {
/**
 * The map class of WordCount.
 */
public static class TokenCounterMapper
    extends Mapper<Object, Text, Text, IntWritable> {
        
    private final static IntWritable one = new IntWritable(1);
    private Text word = new Text();

    public void map(Object key, Text value, Context context)
        throws IOException, InterruptedException {
        StringTokenizer itr = new StringTokenizer(value.toString());
        while (itr.hasMoreTokens()) {
            word.set(itr.nextToken());
            context.write(word, one);
        }
    }
}
/**
 * The reducer class of WordCount
 */
public static class TokenCounterReducer
    extends Reducer<Text, IntWritable, Text, IntWritable> {
    public void reduce(Text key, Iterable<IntWritable> values, Context context)
        throws IOException, InterruptedException {
        int sum = 0;
        for (IntWritable value : values) {
            sum += value.get();
        }
        context.write(key, new IntWritable(sum));
    }
}
/**
 * The main entry point.
 */
public static void main(String[] args) throws Exception {
    Configuration conf = new Configuration();
    String[] otherArgs = new GenericOptionsParser(conf, args).getRemainingArgs();
    Job job = new Job(conf, "Example Hadoop 0.20.1 WordCount");
    job.setJarByClass(WordCount.class);
    job.setMapperClass(TokenCounterMapper.class);
    job.setReducerClass(TokenCounterReducer.class);
    job.setOutputKeyClass(Text.class);
    job.setOutputValueClass(IntWritable.class);
    FileInputFormat.addInputPath(job, new Path(otherArgs[0]));
    FileOutputFormat.setOutputPath(job, new Path(otherArgs[1]));
    System.exit(job.waitForCompletion(true) ? 0 : 1);
}
}

Then, we build this file and pack the result into a jar file:

mkdir classes
javac -classpath /Users/wyi/hadoop-0.20.1/hadoop-0.20.1-core.jar:/Users/wyi/hadoop-0.20.1//lib/commons-cli-1.2.jar -d classes WordCount.java && jar -cvf wordcount.jar -C classes/ .

Finally, we run the jar file in standalone mode of Hadoop

echo "hello world bye world" > /Users/wyi/tmp/in/0.txt
echo "hello hadoop goodebye hadoop" > /Users/wyi/tmp/in/1.txt
hadoop jar wordcount.jar org.sogou.WordCount /Users/wyi/tmp/in /Users/wyi/tmp/out

Install and Configure Hadoop on Mac OS X

2009-12-27T04:56:00.001-08:00

Download and Install

Download Hadoop (at the time of writing this essay, it is version 0.20.1) and unpack it into, say, ~wyi/hadoop-0.20.1.
Install JDK 1.6 for Mac OS X.

Edit your ~/.bash_profile to add the following lines

export JAVA_HOME=/System/Library/Frameworks/JavaVM.framework/Versions/1.6.0/Home
export HADOOP_HOME=~wyi/hadoop-0.20.1
export PATH=$HADOOP_HOME/bin:$PATH

Edit ~wyi/hadoop-0.20.1/conf/hadoop-env.sh to define JAVA_HOME varialbe as

export JAVA_HOME=/System/Library/Frameworks/JavaVM.framework/Versions/1.6.0/Home

Try to run the command hadoop

Run An Example Program
By default, Hadoop is configured to run in a non-distributed mode, as a single Java process. This is useful for debugging. The following example copies the unpacked conf directory to use as input and then finds and displays every match of the given regular expression. Output is written to the given output directory.

cd ~/wyi/hadoop-0.20.1
mkdir input
cp conf/*.xml input
bin/hadoop jar hadoop-*-examples.jar grep input output 'dfs[a-z.]+'
cat output/*

Note that before you re-run this example, you need to delete directory output, otherwise, Hadoop will complain that directory exists.

Some Interesting Ant External Tools/Tasks

2009-12-27T03:29:00.000-08:00

AntPrettyBuild

Ant Pretty Build is a tool to easily show and run Ant buildfiles directly from within a browser window. It consists of a single XSL file that will generate, on the fly, in the browser, from the .xml buildfile, a pretty interface showing project name, description, properties and targets, etc. sorted or unsorted, allowing to load/modify/add properties, run the whole project, or run selected set of targets in a specific order, with the ability to modify logger/logfile, mode and add more libs or command line arguments.

Checkstyle

Checkstyle is a development tool to help programmers write Java code that adheres to a coding standard. Its purpose is to automate the process of checking Java code, and to spare humans of this boring (but important) task.

Checkstyle can be run via an Ant task or a command line utility.

Hammurapi

Java code review tool. Performs automated code review. Contains 111 inspectors which check different aspects of code quality including coding standards, EJB, threading, ...

ProGuard

ProGuard is a free Java class file shrinker and obfuscator. It can detect and remove unused classes, fields, methods, and attributes. It can then rename the remaining classes, fields, and methods using short meaningless names.

CleanImports

Removes unneeded imports. Formats your import sections. Flags ambiguous imports.

High-dimensional Data Processing

2009-12-24T05:32:00.000-08:00

The three top performing classes of algorithms for high-dimensional data sets are

logistic regression,
Random Forests and
SVMs.

Although logistic regression can be inferior to non-linear algorithms, e.g. kernel SVMs, for low-dimensional data sets, it often performs equally well in high-dimensions, when the number of features goes over 10000, because most data sets become linearly separable when the numbers of features become very large.

Given the fact that logistic regression is often faster to train than more complex models like Random Forests and SVMs, in many situations it is the preferable method to deal with high dimensional data sets.

Native Multitouch for Linux

2009-12-22T22:41:00.000-08:00

A research institute in France coworked with Linux kernel developers and created a Linux native muti-point touch tech. I like the following demo video on Youtube:

http://www.youtube.com/watch?v=DTeUbx_nnM4

More details can be found at:

http://lii-enac.fr/en/projects/shareit/linux.html

Skyfire: Mobile Web Browsing over GFW

2009-12-22T18:36:00.001-08:00

Just tried Skyfire on my Nokia E71 mobile phone. It is not only able to get over GFW but also able to play Youtube videos (E71 does not have a fully functional Flash player). A colleague told me that Skyfire renders Web pages (including embedded video) on the sever and sends result images to my mobile phone. It is really thin-client, but I will pay a lot for communication to network carrier.

Collapsed Gibbs Sampling of LDA on GPU

2009-12-20T21:56:00.000-08:00

Thanks to Feng Yan who sent me his newly published work on parallel inference of LDA on GPU.

The basic motivation is that in the circumstances of GPU, display card memory has too small capacity to maintain a copy of nwk matrix for each core in GPU. So the very basic requirement is to keep a global nwk matrix for all cores. This brings a new requirement that when multiple cores work together in sampling, they should not update the same element of nwk simultaneously. Feng gave a solution to partition the training data by not only documents but also words. This is viable due to the observation that:

for word w1 in document j1 and word w2 in document j2, if w1!=w2 and j1!=j2, simultaneious updates of topic assignment have no read/write conflicts on document-topic matrix njk nor wor-topic matrix nwk.

Feng also presents a preprocess algorithm which computes an optimal data partition under the goal of load balancing.

A Nice Introduction to Logistic Regression

2009-12-20T18:52:00.001-08:00

http://luna.cas.usf.edu/~mbrannic/files/regression/Logistic.html

Among the many text books and tutorials on logistic regression, the very preliminary one given by above link explains how the logistic regression model comes:

In the binary classification problem, it is intuitive to determine whether an instance x belongs to class 0 or class 1 by the ratio P(c=1|x) / P(c=0|x). Denoting P = P(c=1|x) and 1-P = P(c=0|x), the ratio becomes odds P/(1-P).

However, a bad property of odds is that it is asymmetric w.r.t. P. For example, swapping the values of P and 1-P does not negates the value of P/(1-P). However, the swapping does negates the logit ln P/(1-P). So, it becomes reasonable to make logit instead of odds our dependent variable.

By modeling the dependent variable by a linear form, we get:

ln P/(1-P) = a + bx

which is equivalent to

P = e^a+bx / (1 + e^a+bx)

Above tutorial also compares linear regression with logistic regression:

"If you use linear regression, the predicted values will become greater than one and less than zero if you move far enough on the X-axis. Such values are theoretically inadmissible."

This explains that logistic regression does not estimate the relation between x and c, instead it estimates x and P(c|x), and uses P(c|x) to determine whether x is in c=1 or c=0. So logistic regression is not regression, it is a classifier.

Additional information:

A C++ implementation of large-scale logistic regression (together with a tech-report) can be found at:
http://stat.rutgers.edu/~madigan/BBR
A Mahout slides show that they have received a proposal to implement logistic regression in Hadoop from Google Summer school of Code, but I have not seen the result yet.
Two papers on large-scale logistic regression was published in 2009:
1. Parallel Large-scale Feature Selection for Logistic Regression, and
2. Large-scale Sparse Logistic Regression

Clouding Computing Using GPUs

2009-11-23T19:15:00.000-08:00

It seems that cloud computing and supercomputing have been in the conversion from massive CPUs to massive GPUs.

In the most recent Top500 Supercomputer list, although most supercomputers still use CPU and Linux, but one of them, the #5, uses ATI RadeonTM RV770 GPUs instead of x86 CPUs.

In a well-known blog post, How Will We Keep Supercomputing Super?, the author claims that due to the limitations stated by the Moore's law, the complexity of CPU makes it costly (in frontend complexity and power consumption) to combine more of them to achieve better performance. On the contrast, it is more technologically reasonable to combine GPUs, which contains more and simpler cores than CPUs.

It is also noticeable that the biggest GPU producer, Nvidia, recently launched their cloud computing product, RealityServer, on Amazon's cloud computing platform.

How to Write a Spelling Correction Program

2009-11-02T02:12:00.000-08:00

This is an excellent article by Peter Norvig, a research director of Google.

Emacs — Tab vs. Space

2009-11-01T18:30:00.000-08:00

To force Emacs to insert spaces instead of tabs when you press the TAB key:

M-x set-variable indent-tabs-mode nil

Or in your .emacs file:

(setq-default indent-tabs-mode nil)

C++ digraphs and additional keywords

2009-10-20T03:39:00.000-07:00

[Original post]

A digraph is a keyword or combination of keys that lets you produce a character that is not available on all keyboards.

The digraph key combinations are:

Key Combination Character Produced
<% {
%> }
<: [
:> ]
%% #

Key Combination	Character Produced
<%	{
%>	}
<:	[
:>	]
%%	#

Additional keywords, valid in C++ programs only, are:

Keyword Character Produced
bitand &
and &&
bitor |
or ||
xor ^
compl ~
and_eq &=
or_eq |=
xor_eq ^=
not !
not_eq !=

Keyword	Character Produced
`bitand`	&
`and`	&&
`bitor`	\|
`or`	\|\|
`xor`	^
`compl`	~
`and_eq`	&=
`or_eq`	\|=
`xor_eq`	^=
`not`	!
`not_eq`	!=

To Make Firefox Display PDF on Mac OS X

2009-10-01T23:01:00.000-07:00

On Windows, we can simply install Adobe Reader and Firefox will be able to find PDF plugin. However, on Mac OS X, we need to install the PDF Browser Plugin from Schubert|it.

VLHMM for Web Applications

2009-09-29T05:39:00.000-07:00

It is glad to find that a WWW'09 paper cited my work on VLHMM (variable-length hidden Markov model). In this paper, Towards Context-Aware Search by Learning a Very Large Variable Length Hidden Markov Model from Search Logs, the authors propose to learn a very-large VLHMM for Web user behavior modeling. I also re-visited my old Web page on VLHMM.

Merge columns from two text files

2009-09-27T19:47:00.000-07:00

pr -m -t -s\ file1 file2

Posting Code into Blogger Posts

2009-08-31T03:46:00.001-07:00

A concise article describes how to use SyntaxHighLighter to insert program code snippets into Blogger posts.

Bloom Filter

2009-08-31T03:34:00.000-07:00

The Bloom filter is a space-efficient probabilistic data structure that is used to test whether an element is a member of a set. False positives are possible, but false negatives are not. Elements can be added to the set, but not removed (though this can be addressed with a counting filter). The more elements that are added to the set, the larger the probability of false positives.

Practical applicaitons of Bloom filter including fast test that whether a request could be handled by a server instance, whether a data element is in a replicate in a redundent system.

Be Careful with stl::accumulate

2009-08-12T02:17:00.000-07:00

If we are to accumulate a vector of doubles, use the following code snippet:

accumulate(timbre_topic_dist.begin(), timbre_topic_dist.end(), 0.0);

You do not want to be lazy and write 0.0 as 0, which will be interpreted by the compiler as an integer, which is used to infer the type of intermediate and final result of accumulate. For your reference, here attaches one of the multiple prototypes of accumulate:

      template < typename _InputIterator, typename _Tp >
    _Tp accumulate(_InputIterator __first, _InputIterator __last, _Tp __init) {
      for (; __first != __last; ++__first)
        __init = __init + *__first;
      return __init;
    }

Note that the partial result is stored in _Tp __init, which means even we explicitly use plus as the accumulator, the result will still be truncated.

accumulate(timbre_topic_dist.begin(), timbre_topic_dist.end(), 0, // Wrong
plus()); // No effect to correct the mistake.

A Paper on ISMIR 2008

2009-07-21T19:52:00.000-07:00

In the following paper published on ISMIR 2008:

Oh Oh Oh Whoah! Towards Automatic Topic Detection In Song Lyrics, Florian Kleedorfer et al.

the authors present their work using NMF (Non-negative Matrix Factorization) to analyze semantic topics from song lyrics. In Section 3.4:

"We decide to use NMF for automatic topic detection as it is a clustering technique that results in additive representation of items (e.g., song X is represented as 10% topci A, 30% topic B and 60% topic C), a property that distinguishes it from most other clustering techniques."

However, "most other techniques" including pLSA, LDA and Mix-Noisy-OR models all have the "distinguishing property" stated by the authors. In addition, the equivalence between NMF and pLSA has been well studied in the following papers:

Relation between PLSA and NMF and implications, SIGIR 2006.
On the equivalence between Non-negative Matrix Factorization and Probabilistic Latent Semantic Indexing. Computational Statistics and Data Analysis 52 (2008) 3913–3927.

The authors also criticize that LSA cannot process large sparse matrices. However, LSA is in fact applying SVD on term-document-matrix (TDM), and there are many SVD algorithms that can decompose large sparse matrices.

A Non-Sense Braille Translator

2009-07-15T08:21:00.000-07:00

An apple everyday, keeps doctor away.

I recently wrote a Braille translator, which converts English text into Braille rendered using pretty dots --- only people with well eye-sight can percieve.

Lock Screen in Mac OS X

2009-07-08T04:09:00.001-07:00

To enable the "Lock Screen" function of Mac OS X, open your Keychain Access utility in the Applications / Utility folder. In the preference dialog, select "Show Status in Menu Bar." A black padlock will appear in your taskbar in the upper right-hand corner. Close Keychain Access. Now when you click on the padlock, you have a "Lock Screen" option in the drop-down.

Lock Screen in Mac OS X

2009-07-08T04:09:00.000-07:00

解决英文版Windows的中文乱码问题

2009-06-29T20:09:00.000-07:00

Open "Control Panel"
Switch to "Category View"
Open "Regional and Language Options"
Switch to "Languages" tab
Click "Install files for East Asian languages", and click "Apply".
Switch to "Advanced" tab
In the combo box "Language for non-Unicode programs", select "Chinese（PRC）"
Switch to "Regional Options" tab
Select "Chinese(PRC)" and "China" respectively for each of the two combo boxes.
Click "OK"

Tips: 如果原有的中文软件还是有乱码问题，可以重新安装程序。

Learning OpenCV, the E-book

2009-06-29T00:10:00.000-07:00

Learning OpenCV, the E-book

DocView Mode for Emacs

2009-06-28T20:42:00.000-07:00

The wiki page.
Shift-+ to enlarge the displaying (.pdf)
C-c C-c to switch between docview mode and text mode

Make Emacs Warns for Long Lines

2009-06-23T02:46:00.000-07:00

On Linux, we can use function font-lock-set-up-width-warning to tell Emacs warning for too long lines in source code:

(add-hook 'c++-mode-hook
      '(lambda () (font-lock-set-up-width-warning 80)))
(add-hook 'java-mode-hook
      '(lambda () (font-lock-set-up-width-warning 80)))
(add-hook 'python-mode-hook
      '(lambda () (font-lock-set-up-width-warning 80)))

On Mac OS X, above method fails. However, With Carbon Emacs or Aquamacs, we can do as follows:

; for CarbonEmacs (MacOSX)
(defun font-lock-width-keyword (width)
"Return a font-lock style keyword for a string beyond width WIDTH
thatuses 'font-lock-warning-face'."
`((,(format "^%s\\(.+\\)" (make-string width ?.))
 (1 font-lock-warning-face t))))

(font-lock-add-keywords 'c++-mode (font-lock-width-keyword 80))
(font-lock-add-keywords 'objc-mode (font-lock-width-keyword 80))
(font-lock-add-keywords 'python-mode (font-lock-width-keyword 80))
(font-lock-add-keywords 'java-mode (font-lock-width-keyword 80))

An easier solution for 80-column-rule is lineker. The usage is pretty simple (tested on my IBM T60p, Emacs for Windows): add the following into your .emacs file.

(require 'lineker)
(add-hook 'c-mode-hook 'lineker-mode)
(add-hook 'c++-mode-hook 'lineker-mode)

GCC Does Not Support Mutable Set/MultiSet Iterator

2009-06-23T00:10:00.000-07:00

Although C++ STL standard requires that std::set and set::multiset supports both constant iterator and mutable iterator, but libstdc++ supports only the constant one. In /usr/include/c++/4.0.0/bits/stl_set.h (as well stl_multiset.h), we can see the following iterator typedefs:

// _GLIBCXX_RESOLVE_LIB_DEFECTS
// DR 103. set::iterator is required to be modifiable,
// but this allows modification of keys.
typedef typename _Rep_type::const_iterator iterator;
typedef typename _Rep_type::const_iterator const_iterator;

This would lead many STL algorithms incompatible with set and multiset. For example, the following code does not compile in GCC 4.0.x:

set myset;             // or multiset myset;
*myset.begin() = 100;  // fails due to begin() returns const_iterator
remove_if(myset.begin(), myset.end(), Is71()); // remove_if invokes remove_copy_if, which requires mutable myset.begin().

It is notable that Microsoft Visual C++ 7.0 and later versions are more restrictive to the STL standard on above issue. Above code works with Visual C++.

Fast Approximate of 2D Water Ripples

2009-06-22T08:35:00.000-07:00

Here is a very fast approximation algorithm. The author is really good at observing and finding highly effective approximations, in this case, the value of sine(x+o) is proportional to sine(x), where o is a small phase offset.

Useful Documents for CUDA Development

2009-06-21T07:41:00.000-07:00

Official Programming Guide from NVidia.
CUDA Programming, a slides from Johan Seland.

Make CUDA Works on MacBook Pro

2009-06-21T06:40:00.001-07:00

Download and install CUDA toolkit and CUDA SDK.
When installing the CUDA toolkit, click the Customize button on the Installation Type panel of the installer. Then be sure that CUDAKext is selected for installation. If we do not do this, CUDA applications will complain "no CUDA capable device".

After installing add the following to .bash_profile.

export PATH=/usr/local/cuda/bin:$PATH
export DYLD_LIBRARY_PATH=/usr/local/cuda/lib:$DYLD_LIBRARY_PATH

After installing the CUDA SDK,
```
cd /Developer/CUDA/lib
ranlib *.lib
```
Otherwise, we will get the following linker error when building CUDA applications:
ld: in ../../lib/libcutil.a, archive has no table of contents
Build CUDA sample applications:
```
cd /Developer/CUDA
make
```
The result application binaries will be installed to /Developer/CUDA/bin/darwin/release.

A useful reference for installation and system requirement is a PDF file named CUDA_Getting_Started_2.2_MacOS.pdf.

A Good Xcode/C++/QuickDraw Tutorial

2009-06-21T06:25:00.000-07:00

Xcode C++ Tutorials is a C++ tutorial using Xcode as the development tool and QuickDraw (the 2D graphics engine of Carbon under Mac OS X) as the basic framework. It is good for C++ beginners using Mac OS X, as well developers with experience with other platforms.

Mix Intel IPP with OpenCV

2009-06-20T21:49:00.001-07:00

http://software.intel.com/en-us/articles/intel-integrated-performance-primitives-intel-ipp-open-source-computer-vision-library-opencv-faq/

Build OpenCV under Mac OS X

2009-06-20T19:44:00.000-07:00

Install OpenCV on Mac OS X

Install Xcode on Mac OS X computer.
Download OpenCV source package (for Linux) from SourceForge.
Unpack the source package
Generate Makefile.in/am
autoreconf -i --force
Configure
./configure --prefix=/usr/local --with-python --with-swig
Build and test building result
make
make check
Install
make install
Building applications
g++ -o capcam main.cc -I /usr/local/include/opencv -L/usr/local/lib -lcxcore -lcv -lcvaux -lhighgui -lml

Other sources of information:

Introduction to programming with OpenCV

Package Management under Mac OS X

2009-06-20T18:48:00.000-07:00

Under Windows, we can use Cygwin to manage software packages. Under Mac OS X, we can use Macports. Download and install the Macports dmg file, open a terminal window, and type commands like:

sudo port install cmake

Macports will download the source package and compile it for you.

Note: To make Macports knows the most recent package list, type the following commands regularly:

sudo port -v selfupdate

Note: After installing Macports, open a new terminal windows (program), which will use the system environment variables newly updated by the installation program. Using a terminal window which had been opened before Macports installation will leads to an error complaining cannot find 'port'.

ActionScript 3.0 Mode for Emacs

2009-06-18T22:28:00.000-07:00

EmacsWiki suggests an actionscript mode which can be downloaded from a post at PetTomato. After download the .el file, I added the following lines into my .emacs configuration file. This works for my Aquaemacs for Mac OS X.

(load-file "~/.emacs.d/actionscript-mode.el")
(autoload 'actionscript-mode "javascript" nil t)
(add-to-list 'auto-mode-alist '("\\.as\\'" . actionscript-mode))

Gmsh: a three-dimensional finite element mesh generator

2009-06-14T19:46:00.000-07:00

Gmsh is an automatic 3D finite element grid generator with a built-in CAD engine and post-processor. Its design goal is to provide a simple meshing tool for academic problems with parametric input and advanced visualization capabilities.

Fullscreen Mode of Aquamacs

2009-06-13T20:19:00.000-07:00

We can type Command-Shift-Return to invoke the function aquamacs-toggle-full-frame, which switches between fullscreen mode. For your customization skills for Aquamacs, refer to http://www.emacswiki.org/emacs/CustomizeAquamacs.

Robust Ray Intersect with Triangle Test

2009-06-13T20:12:00.000-07:00

Tomas Moller and Ben Trumbore proposed a robust algorithm in their paper, Fast, Minimum Storage Ray/Triangle Intersection. A reference implementation of this algorithm can be referred to as http://www.lighthouse3d.com/opengl/maths/index.php?raytriint, which implements the non-culling branch presented in that paper.

Alt and Meta in Aquamacs

2009-06-13T20:06:00.000-07:00

The default Meta key in the Aquamacs distribution is Option (and also Esc). If this is unusable for you (your fingers are too well trained on other platforms), you can either press Apple-; (Options → Option Key → Option Key for Meta) to switch to Esc only.

For other interesting things about Aquamacs, refer to Aquamacs FAQ.

Point inside Polyhedron

2009-06-10T09:42:00.000-07:00

From the book, Real-time Collision Detection.

Password-less Login Using SSH

2009-06-09T19:37:00.000-07:00

Consider we want to login from a MacBook Pro (mbp) to a remote Linux machine (tsingyi), where both computers have OpenSSH installed. In order to make tsingyi trust mbp, we use RSA cryptographic method to generate a public and a private key for mbp, which will be used to identify mbp during login.

To generate the pair of keys, on mbp, type

ssh-keygen -t rsa

Accept all default answers, and we get two files:

~/.ssh/id_rsa     --- the private key
~/.ssh/id_rsa.pub --- the public key

Now, copy the public key file to tsingyi by typing following command on mbp:

scp ~/.ssh/id_rsa.pub wyi@tsingyi:/home/wyi/.ssh/id_rsa-mbp.pub

and add the public key of mbp to ~/.ssh/authorized_keys of tsingyi by typing following command on tsingyi:

cat ~/.ssh/id_rsa-mbp.pub >> ~/.ssh/authorized_keys

Here we are. We should be able to ssh to tsingyi from mbp without typing password now.

Buld OpenGL/GLUT Applications under Mac OS X

2009-06-09T18:50:00.000-07:00

Xcode comes with all what we need to build a Cocoa application with OpenGL and GLUT and GCC. So, first of all, we need to install Xcode.

Writing Code

An GLUT C/C++ program for Mac OS X should include three header files:

#include   // Header File For The OpenGL32 Library
#include   // Header File For The GLu32 Library
#include   // Header File For The GLut Library

Note that the locations of these header files in Mac OS X differs from where they are in Linux and Windows (e.g., GL/glut.h)

Building Using GCC

The command line using GCC to build a program main.c is as follows:

gcc -framework GLUT -framework OpenGL -framework Cocoa main.c -o learning

It is notable here that MacOSX uses the concept of so called frameworks. Instead of adding include paths and library names yourself, you add a framework to your compiler call. This is a MacOSX specific extension to gcc.

Building Using Xcode IDE

We can also manage our OpenGL/GLUT projects using Xcode IDE. To create a project, select the project type of "Cocoa Application". To add/edit the code, remove the auto-generated main.m, add a new main.c, and write our code into main.c. To specify the frameworks in IDE, right click the project and choose "Add Exisiting Frameworks" to add OpenGL and GLUT.

Open Source Software on Mac OS X

2009-06-08T22:50:00.000-07:00

http://www.opensourcemac.org/
http://www.freemacware.com/
http://www.linuxbeacon.com/doku.php?id=opensourcemac

Simulation of Cracks

2009-06-07T08:42:00.001-07:00

The paper: Simulation of the typical Poisson-Voronoi-Cox-Voronoi cell

Multivariate Poisson Models

2009-06-07T08:16:00.001-07:00

The slides on Multivariate Poisson Models.
The paper: An Algorithm for Fast Generation of Bivariate Poisson Random Vectors

Crystalization

2009-06-07T08:11:00.000-07:00

Stochastic and Deterministic Simulation of Nonisothermal Crystalization of Polymers
The Structure of Crystals.

To Get Forward (Alt-f), Backward (Alt-b) and Delete (Alt-d) Word Works for iTerm

2009-05-27T18:53:00.000-07:00

Open iTerm.
Go to Bookmarks > Manage Profiles
Choose Keyboard Profiles on the left and edit the Global Profile
Next to Mapping, click the + sign.
For Key, choose hex code.
In the text box next to hex code, enter 0x62 for b, 0x64 for d or 0x66 for f.
Note that 0x62, 0x64 and 0x66 are ASCII codes for characters b, d, and f respectively.
For Modifier, check the Option Box
For Action, choose send escape sequence.
Write b, d or f in the input field.

Now Alt-f will jump forward a word, Alt-b jumps backwards a word, and Alt-d deletes a word.

Insert Google Maps and Google Picasa Album into Blog Posts

2009-05-14T06:31:00.001-07:00

查看大图

妈妈做的绢花

MATLAB code for Sampling Gaussian distribution

2009-03-18T05:36:00.001-07:00

function M = sample_gaussian(mu, Sigma, N)
mu = mu(:);
n=length(mu);
[U,D,V] = svd(Sigma);
M = randn(n,N);
M = (U*sqrt(D))*M + mu*ones(1,N);
M = M';