A Brief Summary of Independent Set in Graph Theory

Graph Basics

Let G be a undirected graph. G=(V,E), where V is a set of vertices and E is a set of edges.  Every edge e in E consists of two vertices in V of G. It is said to connect, join, or link the two vertices (or end points).

Independent Set

An independent set S is a subset of V in G such that no two vertices in S are adjacent. I suppose that its name is meaning that vertices in an independent set S is independent on a set of edges in a graph G. Like other vertex sets in graph theory, independent set has maximal and maximum sets as follows:

The independent set S is maximal if S is not a proper subset of any independent set of G.

The independent set S is maximum if there is no other independent set has more vertices than S.

That is, a largest maximal independent set is called a maximum independent set. The maximum independent set problem is an NP-hard optimization problem.

All graphs has independent sets. For a graph G having a maximum independent set, the independence number α(G) is determined by the cardinality of a maximum independent set.

Relations to Dominating Sets

  • A dominating set in a graph G is a subset D of V such that every vertex not in D is joined to at least one member of D by some edge.
  • In other words, a vertex set D is a dominating set in G if and if only every vertex in a graph G is contained in (or is adjacent to) a vertex in D.
  • Every maximal independent set S of vertices in a simple graph G has the property that every vertex of the graph either is contained in S or is adjacent to a vertex in S.
    • That is, an independent set is a dominating set if and if only it is a maximal independent set.

Relations to Graph Coloring

  • Independent set problem is related to coloring problem since vertices in an independent set can have the same color.

References

Advertisements

Data-Intensive Text Processing with MapReduce Draft Available in Online

Data-Intensive Text Processing with MapReduce, Jimmy Lin and Chris Dyer

Actually, there have never been books that directly deal with MapReduce programming and algorithms. This book addresses from MapReduce algorithm design to EM Algorithms for Text Processing. Although this book is still draft, it seems well-organized and very interesting. In addition, the book contains some basic graph algorithms using MapReduce.


How to Create A Table in HBase for Beginners

I have accumulated some knowledge and know-how about MapReduce, Hadoop, and HBase since I participated in some projects. From hence, I’ll post the know-how of HBase by period. Today, I’m going to introduce a way to make a hbase table in java.

HBase provides two ways to allow a Hbase client to connect HBase master. One is to use a instance of HBaseAdmin class. HBaseAdmin provides some methods for creating, modifying, and deleting tables and column families. Another way is to use an instance of HTable class. This class almost provides some methods to manipulate data like inserting, modifying, and deleting rows and cells.

Thus, in order to make a hbase table, we need to connect a HBase master by initializing a instance of HBaseAdmin like line 4. HBaseAdmin requires an instance of HBaseConfiguration. If necessary, you may set some configurations like line 2.

In order to describe HBase schema, we make an instances of HColumnDescriptor for each column family. In addition to column family names, HColumnDescriptor enables you to set various parameters, such as maxVersions, compression type, timeToLive, and bloomFilter. Then, we can create a HBase table by invoking createTable like line 10.

HBaseConfiguration conf = new HBaseConfiguration();
conf.set("hbase.master","localhost:60000");

HBaseAdmin hbase = new HBaseAdmin(conf);
HTableDescriptor desc = new HTableDescriptor("TEST");
HColumnDescriptor meta = new HColumnDescriptor("personal".getBytes());
HColumnDescriptor prefix = new HColumnDescriptor("account".getBytes());
desc.addFamily(meta);
desc.addFamily(prefix);
hbase.createTable(desc);

Finally, you can check your hbase table as the following commands.

c0d3h4ck@code:~/Development/hbase$ bin/hbase shell
HBase Shell; enter 'help<RETURN>' for list of supported commands.
Version: 0.20.1, r822817, Wed Oct  7 11:55:42 PDT 2009
hbase(main):001:0> list
TEST

1 row(s) in 0.0940 seconds

ACM SIGMOD 2010 Programming Contest

As you know, SIGMOD is ACM’s Special Interest Group on Management of Data. SIGMOD holds the annual conference that is regarded as one of the best conference in computer science. Besides, SIGMOD organizes a programming contest in parallel with the ACM SIGMOD conference. Below description is the call for the programming contest of this year. The programming contest’s subject of this year seems very interesting! The task is to implement a simple distributed query executor built on top of last year’s main-memory index. The environment on which contestants will test their implementation may be provided by Amazon. If you are interested in this programming contest, try that. You can get further information from here (http://dbweb.enst.fr/events/sigmod10contest).

A programming contest is organized in parallel with the ACM SIGMOD 2010 conference, following the success of the first annual SIGMOD programming contest organized last year. Student teams from degree-granting institutions are invited to compete to develop a distributed query engine over relational data. Submissions will be judged on the overall performance of the system on a variety of workloads. A shortlist of finalists will be invited to present their implementation at the SIGMOD conference in June 2010 in Indianapolis, USA. The winning team, to be selected during the conference, will be awarded a prize of 5,000 USD and will be invited to a one-week research visit in Paris. The winning system, released in open source, will form a building block of a complete distributed database system which will be built over the years, throughout the programming contests.


CIKM 2009 in Hong Kong

With Min Kyoung Sung who is a coauthor of  ‘SPIDER : A System for Scalable, Parallel / Distributed Evaluation of large-scale RDF Data‘, I participated in 18th ACM CIKM 2009 (Conference on Information and Knowledge Management) held in Hong Kong. We stayed in Marriott Hotel near the Asia World-Expo at which CIKM 2009 held. At this conference, I got along with several Korean researchers (Kyong-Ha Lee, Jinoh Oh, and Sangchul Kim) and I discussed about SPIDER with some researchers who are interested in RDF data processing during the demonstration session.

At CIKM 2009, I felt that the recent trend of web data management are being changed to information extraction and semantic or structured web data rather then unstructured data. Many papers and posters addressed these issues. In addition, the subject of the panel was ‘ Information extraction meets relational databases: Where are we heading?’ One of the panel said that the hot spot of web data management research changes from crawling, indexing, and searching to information extraction and semantic data. These changes lead to new various data and knowledge management issues. Besides information extraction, graph data mining was one of the main hot issues in CIKM 2009.

At the main keynote, Kyu-Young Hwang (KAIST, Korea) spoke ‘DB-IR Integration and Its Application to a Massively-Parallel Search Engine.’ Its key subject is that DB-IR integration is becoming one of major challenges in the database area, so it is leading to new DBMS architecture applicable to DB-IR integration. In addition, Edward Chang (Google Research China) and Clement Yu (University of Illinois at Chicago) spoke ‘Confucius and its intelligent Disciples‘ and ‘Advanced Metasearch Engines respectively.

Coffee Break at CIKM 2009SPIDER in Demo Session

Tian Tan Buddha Statue in Hong KongThe lunch time in CIKM 2009

This conference was a really nice experience for me. I enjoyed the conference, reception, and banquet. However, I have an unsatisfied feeling because I didn’t participate in the 1st Workshop CloudDB 2009 in conjunction in CIKM 2009.

Anyway, this conference inspired Min Kyoung Sung and me. It may be kept in our mind for long time.


MapReduce Online Comes Out!

MapReduce has been gaining much attention in data intensive computing field. As you know, it is well known as a very popular framework for batch-processing.

Recently, however, Tyson Condie who is a Ph.D student in UC Berkeley accomplishes MapReduce Online. Today, I heard this news from Data Beta. Actually, It is amazing works since the original MapReduce is specialized and designed for only batch-processing. In addition, most people believe that MapReduce will remain a batch-processing.

The essential of MapReduce online is that it tries to hold the fault-tolerance model of the original MapReduce, whereas it provides the the pipelining of results across tasks and jobs instead of materializing the output of each MapReduce task and job into disk. Consequently, MapReduce online enables the program to return the result earlier from a big job.

You can get further information from MapReduce Online.


BSP Library on Hadoop?

Recently, I started to participate in the Hama project (a distributed scientific package on Hadoop for massive matrix and graph data), and I have taken the times to develop the bulk synchronization parallel (BSP) library on Hadoop (HAMA-195); I’m getting help from Edword Yoon, a founder of Hama project. The motivation of BSP lib is definitely clear.

The hadoop platforms are installed in cloud computing service providers and many companies as you can see in http://wiki.apache.org/hadoop/PoweredBy. However, most of them may use only MapReduce programs. As you know although MapReduce is very scalability, but it provides only the simple programming model. Many programmers want to use more various programming model without changing the platform (i.e., Hadoop). This BSP lib will be the beginning for their desires. However, like MapReduce, BSP may also be not swiss army knife. When we find appropriate applications, BSP lib on Hadoop will be valued for its scalability and ability.

Sooner, I’ll post articles about the progress of BSP library and Angrapa (the graph package on Hama).