Hamburg, a graph computing framework on Hadoop

As mentioned ago, I've been forming up the Hamburg project with Hyunsik Choi. Let's see more detail in the diagram of computing method of Hamburg based on BSP model.




Each worker will process the data fragments stored locally. And then, We can do bulk synchronization using collected communication data. The 'Computation' and 'Bulk synchronization' can be performed iteratively, Data for synchronization can be compressed to reduce network usage.

Plainly, It aims to improve the performance of traverse operations in Graph computing. For example, to explores all the neighboring nodes from the root node using Map/Reduce (FYI, Breadth-First Search (BFS) & MapReduce), We need a lot of iterations to get next vertex per-hop time.

If (same condition as before) do BFS using Hamburg, It will cause a lowering the cost of iterations. Let's assume the graph looks like presented below:




The graph was stored in Hbase on distributed system as above. The root is 1. Then, we need only one 'Bulk synchronization' between server2 and server3 with Hamburg. Rests will be calculated on local machine.




Almost graph algorithms are similar with this case.

Updated - 26 August, 2009 : See also, Inference anatomy of the Google Pregel

Comments

  1. Server2 needs to tell Server3 that the vertex 6 distance is 2 so that Server3 can assign distance 3 for vertex 7.

    Since Server2 can only see partial view for vertex 2 neighbors, I think Server2 also has to tell Server1 about the distance of vertex 2 (which is 2). Then Server1 decides the final distance of vertex 2 (which is 1).

    Or the other way around: Server1 already decides the distance of vertex 2 is 1 and needs to tell Server2 about it (since from Server2 point of view, the disntance of vertex 2 is 2).

    Eitherway, Server1 and Server2 has to communicate, isn't it?

    ReplyDelete

  2. The start node assumed as a vertext 1. Hence, Server1's processing will be locally done w/o any communicate. There is one communication between Server2 and Server3.

    ReplyDelete

  3. Nice info regarind graph computing framework on Hadoop my sincere thanks for sharing please continue to share this post
    Hadoop Training in Chennai

    ReplyDelete

  4. Hello admin, I have read your blog, it was very nice to read & I am getting useful information’s through your blog. Keep update your blog. AWS Training in Bangalore | Big Data Hadoop Training in Bangalore

    ReplyDelete

  5. The share you really give us excitement. Thanks for your sharing. If you feel tired at work or study try to participate in our games to bring the most exciting feeling. Thank you!
    Python Online Training | Learn Python Online

    ReplyDelete

Post a Comment

Popular posts from this blog

일본만화 추천 100선

1.군계 (액션,격투)

격투만화 중에서는 아주 유명하고 열광적으로 좋아하는 사람이 많은 만화입니다. 전체적으로 만화의 분위기는 어둡고요... 줄거리를 소개하죠. 주인공인 료는 모범생이었습니다. 그러나 부모님의 강압적인 통제... 그에 대한 무의식적 반발로 부모님을 살해하게 되고 맙니다. 그리고 교도소에서 많은 변화를 겪게되죠..그리고 악의 화신같은 존재가 되고 말죠..... 또 그에 대항하는 인물이 나타나고.... 만화에 대한 소개가 만화의 질을 못 따라가네요. 이 만화는 선과 악에 대해 생각해볼 수있는 만화입니다. 그리고 싸움이란 인간에게 어떤 의미가 있는것일까? 하는 생각도요. 아..군계는 싸움닭이란 뜻입니다. 네이밍센스가 좋죠.


2. 생추어리(해적판제목:빛과 그림자) (액션,정치)

일본 최고의 극화체 만화가인 이케가미 료이치님의 작품입니다. 캄보디아에서 일본 외교관의 아들로 태어난 두 남자 이야기를 그리고 있습니다. 캄보디아의 킬링필드(대학살..실존사건입니다.)와중에서 살아남아 돌아온 두 주인공..한명은 암흑계 보스로 다른 한 명은 정치계 거물로 성장해갑니다. 두 남자의 목숨과도 같은 우정....그들의 관계는 어떻게 될까? 뛰어난 스토리작가와 항상 작업하여 재미는 보장이 되는 작품입니다. 단 남성우월주의가 작품전반에 깔려있어서 여성이 보기엔 거부감을 느낄수도 있는 작품..남자분인거 같아 추천합니다.


3.수라의 각 (역사,무협)

해황기의 작가가 쓴 매우 흥미진진한 역사 무협물입니다. 일본 역사속의 많은 실존인물들의 얘기를 기둥줄거리로 하여 거기에 허구를 작가의 능수능란한 솜씨로 섞어냅니다. 이 작품은 코믹 만화인 수험의 제왕에도 등장하는 데요....그 만화에 이런 말이 있지요. "역사 공부를 하려거든 수라의 각을 읽어라" 이 만화작가의 다른 작품인 해황기도 매우 흥미진진하답니다.


4.베르세르크 (판타지)

말이 필요없는 판타지의 최고 걸작.... 뛰어난 작화에 철학적인 사유까지 배어든 최고의 작품. 안 읽으셨다면 부디 읽어보시길..


5.…
Read more

구글링하는(googling) 방법

1) 연속된 문자열 검색하기: 검색 중 White-Space(공백)는 or 연산 역할을 합니다. 공백 분할 키워드가 하나라도 매치되면 검색된다는거죠. 때문에 연속된 문자열을 검색할때 사용합니다. 노래가사 일부를 찾을 때 유용하지요. 예를 들어, 노래 중 "I gotta feeling" 이란 구절을 들으면 아래와 같이 검색합니다.
["I gotta feeling" lyrics] 개인적으로는 문법이 잘 맞는건지 확인할때도 사용합니다. 내가 생각한 영문이 맞는거라면 전세계 웹에서 어느 한 구절에 포함될 확률이 있으니까요.

2) 특정 사이트만 검색하기: 말그대로 특정 사이트 내 컨텐트에서만 검색합니다.
제 블로그에서 breadth first search 관련 내용만 찾습니다. [site:blog.udanax.org breadth first search]
3) 특정 파일 포맷에서만 검색하기: 구글이 검색하는 대상은 웹 문서 뿐만아니라 PDF, PPT 등등을 모두 검색합니다. 주로 PDF는 논문 검색할때 사용할 수 있고, 프리젠테이션 내용 역시 찾아볼 수 있습니다.
PDF 파일로 된 문서중에 social network 이 포함된 문서들만 검색 [filetype:pdf social network]
마지막으로 검색 탭 아래 "Show options"라는 버튼을 활용하면 최근 문서, 혹은 최근 이미지, 이미지 사이즈 별로 조건을 더 줄 수 있습니다. 자 이정도 스킬이면 원하는 정보는 충분히 찾지 않겠습니까?
Read more

AWS re:Invent 2017 참관기

Image
바로 지난 주, 나와 클라우드플랫폼팀장 제임스 동행으로 여기어때 R&D센터에서 AWS 2017 행사를 참관했다. 덴버/샌프란시스코와는 전혀 다른 라스베가스 스트립의 좌우로 초대형 호텔과 카지노가 즐비한 풍경에 한번 놀랬고, Registration Booth 부터 그 큰 규모에서 두번 놀랬다. 참고로 라스베가스는 이렇게 사람이 많이 모일수 있는 환경을 가지고 있어 대형 세미나가 지속적으로 열린다고 한다 (CES도 동시에 개최된 걸로 안다). 4만 명이 넘는 참가자가 라스베가스 전역에 있는 호텔 행사장에 모였고, 우버 드라이버들은 AWS 컨퍼런스 왔냐고 자연스레 안부 인사를 묻더라. 뭐 이미 잘 알려져 있듯이 한국에 많은 기업이 AWS를 사용하고 있다. 나는 참고로 re:Play 행사에서 오다가다 과거 네이버 동료도 거의 10년만에 만나기도 하였다. :-)

기술 세션들에 대한 리뷰는 모두 참석하지 못했기 때문에 내 눈이 정확하다 말할 순 없지만, 두 가지로 요약된다. Serverless 그리고 AI 다.


Serverless는 프로그래밍 패러다임을 송두리째 바꾸고 있으며, 더 이상 풀스택 엔지니어, 그들의 인프라 노하우와 경험적 스킬은 (희박한 오픈소스 해커 수준 아니고서야) 대우받기 힘든 세상이 되었다.

AI 분야도 마찬가지인데, 이미 학습능력이 클라우드 안으로 들어가기 시작했다.


넷플릭스의 데이터 엔지니어로 유명한 배재현님의 글도 읽어볼 필요가 있음  https://www.facebook.com/jaehb/posts/10214839335118339?pnref=story 

 내 눈에 들어온 슬라이드 한장 … 내가 가장 열성적으로 들었던 딥 러닝 서밋은 장장 4시간 연짱 세션이었고, 그중에 눈에 너무 꽃힌 장표 한장이 있으니 … 주로 내가 많이 얘기하던 내용과 비슷한 면이 있어 그럴수도 있는데, 사용자 경험은 OS에서 웹으로, 웹에서 모바일, 그리고 이제 AI로 넘어가는 과정이라고 볼 수 있다. 우리 IT 기술은 현재 어디에 머물고 있는가? :-)


 여러…
Read more