본문 바로가기
HOME> 논문 > 논문 검색상세

학위논문 상세정보

Efficient Triangulation in Massaive Graphs 원문보기

  • 저자

    Md Mostofa Kamal Rasel

  • 학위수여기관

    경희대학교

  • 학위구분

    국내석사

  • 학과

    컴퓨터공학과

  • 지도교수

    Young-Koo Lee

  • 발행년도

    2014

  • 총페이지

  • 키워드

    Massive Graph Triangle Listing Graph Indexing I/O-efficient Algorithm CPU Parallelism Bit Vector Compressed Bit Vector;

  • 언어

    eng

  • 원문 URL

    http://www.riss.kr/link?id=T13536623&outLink=K  

  • 초록

    Triangle listing is a basic operator in dealing with many graph problems. In-memory algorithms don't work well in recent massive graphs such as social networks since these graphs cannot fit into the memory. Thus recently external memory based algorithms have been proposed. However, the existing studies still suffer from frequent multiple scans of the whole graph on the disk and tremendous calculation coming from involving the whole graph in every iteration. This paper presents a novel index-based method for listing triangles in massive graphs. We first present the new notions of vertex range index and potential cone vertex index. Then we propose an index join based triangle listing algorithm. We access indexed data asynchronously and join them to list triangles using a multi-threaded parallel processing technique. We experimentally show that index join based triangulation algorithm outperforms the state-of-the-art solution by 3 to 8 times in terms of wall clock time. We devise another different triangulation algorithm based on summarized bit batch vector that utilizes the hardware properties for joining two adjacency lists. This summarized bit batch vector algorithm outperforms MGT by more than an order of magnitude and index join based algorithm by 2 times.


 활용도 분석

  • 상세보기

    amChart 영역
  • 원문보기

    amChart 영역