Notes #BrainDump
그래프 알고리즘

그래프 알고리즘

2022-04-11 Note algorithm cs graph notes

Julian Shun

[2023-11-06 Mon 16:00]

6.827 Algorithm Engineering Spring 2022

  • https://people.csail.mit.edu/jshun/6827-s22/

    This is a research-oriented course on algorithm engineering, which will cover both the theory and practice of algorithms and data structures. Students will learn about models of computation, algorithm design and analysis, and performance engineering of algorithm implementations. *We will study the design and implementation of sequential, parallel, cache-efficient, external-memory, and write-efficient algorithms for fundamental problem*s in computing. Many of the principles of algorithm engineering will be illustrated in the context of parallel algorithms and graph problems. Students will read and present research papers, write paper reviews, complete problem sets, participate in classroom discussions, and complete a semester-long research project. Class time will consist of lectures, student presentations, and group project meetings. This course is suitable for graduate students or advanced undergraduates who have taken 6.046 and 6.172. Mathematical maturity and familiarity with algorithm analysis and performance engineering will be assumed. Lectures will consist of instructor and student presentations. Lecture attendance is required and participation counts toward the grade.

    알고리즘과 데이터 구조의 이론과 실무를 모두 다루는 알고리즘 엔지니어링에 대한 연구 중심 과정입니다. 학생들은 계산 모델, 알고리즘 설계 및 분석, 알고리즘 구현의 성능 엔지니어링에 대해 배우게 됩니다. *컴퓨팅의 근본적인 문제*를 해결하기 위한 순차적, 병렬, 캐시 효율적, 외부 메모리 및 쓰기 효율적 알고리즘의 설계 및 구현에 대해 공부합니다. 알고리즘 공학의 많은 원리는 병렬 알고리즘과 그래프 문제의 맥락에서 설명됩니다. 학생들은 연구 논문을 읽고 발표하고, 논문 리뷰를 작성하고, 문제 세트를 완성하고, 강의실 토론에 참여하고, 한 학기 동안의 연구 프로젝트를 완료하게 됩니다. 수업 시간은 강의, 학생 프레젠테이션, 그룹 프로젝트 회의로 구성됩니다. 이 과정은 6.046 및 6.172 를 수강한 대학원생 또는 고급 학부생에게 적합합니다. 수학적 성숙도와 알고리즘 분석 및 성능 공학에 대한 친숙함이 전제됩니다. 강의는 강사와 학생의 프레젠테이션으로 구성됩니다. 강의 출석은 필수이며 참여도는 성적에 반영됩니다

  • TextBook

  • 와! 이 수업은 알고 있는 다른 알고리즘 수업과 다르다. 바로 병렬 머신으로 시작해서 그래프 알고리즘 최적화 이슈로 들어간다. 대학원 수업이라서 그렇게 볼 수 있다. 여기에는 NVRAM Graph Frameworks 강의가 있는데, 논문 2 개를 다루고 있다. , 이며 Sage 는 교수님이 참여한 논문이고, 오픈소스이니 활용하기가 좋아 보인다.

그래프 알고리즘 최적화 이론

데이터베이스에서 어떻게 지식 그래프를 저장하고, 질의하는지에 대한 전반적인 연구흐름을 소개한다. 특히, 시스템 관점에서 핫이슈인 병렬 그래프 프로세싱을 중심으로 IT 공룡들이 대량의 지식 데이터를 처리하고 있는지 연구와 더불어 실용적인 활용 방법을 소개한다.

  • 레퍼런스 5 개만 뽑아보자면?
    • [1]A. Verma, L. Pedrosa, M. Korupolu, D. Oppenheimer, E. Tune, and J. Wilkes, “Large-Scale Cluster Management at Google with Borg,” in Proceedings of the Tenth European Conference on Computer Systems, Bordeaux France, Apr.2015, pp.1–17. doi: 10.1145/2741948.2741964.
    • [2]L. Dhulipala et al., “Sage: Parallel Semi-Asymmetric Graph Algorithms for NVRAMs,” Proc. VLDB Endow., vol.13, no. 9, pp.1598–1613, May 2020, doi: 10.14778/3397230.3397251.
    • [3]S. Heidari, Y. Simmhan, R. N. Calheiros, and R. Buyya, “Scalable Graph Processing Frameworks: A Taxonomy and Open Challenges,” ACM Comput. Surv., vol.51, no. 3, pp.1–53, May 2019, doi: 10.1145/3199523.
    • [4]G. Gill, R. Dathathri, L. Hoang, R. Peri, and K. Pingali, “Single Machine Graph Analytics on Massive Datasets using Intel Optane DC Persistent Memory,” in Proceedings of the VLDB Endowment, Apr.2020, vol.13, pp.1304–1318. doi: 10.14778/3389133.3389145.
    • [5]R. Angles and C. Gutierrez, “Survey of Graph Database Models,” ACM Comput. Surv., vol.40, no. 1, pp.1–39, Feb.2008, doi: 10.1145/1322432.1322433.
    • [6]N. Bronson et al., “TAO: Facebook’s Distributed Data Store for the Social Graph,” 2013, p.12.
    • [7]J. Fan, A. Gerald, S. Raj, and J. M. Patel, “The Case against Specialized Graph Analytics Engines,” 2015, p.10.

그래프 알고리즘-그래프 분석-그래프 데이터베이스 사이의 상관 관계

2022-05-11 작성

그래프 알고리즘, 그래프 분석, 그래프 데이터베이스, 지식 그래프 각각이 무엇이며 이들의 상관 관계는 어떠한가? Julian Shun 교수의 코스웍을 보면서 전체적인 맥락을 이해해보도록하자.

  • Julian Shun 교수의 대학원 코스웍을 보면서 문득, 그래프 알고리즘, 그래프 분석, 그래프 데이터베이스/스토어, 지식 그래프, 그래프 쿼리 언어 등 번잡한 모든 키워드들이 머리속에 맴돌았다. Papers on Graph Analytics 엄청나게 정리되어 있는 논문 리스트를 보자니 그래프의 혼돈으로 가라앉는 기분이 들었다. 그래서 전체적인 맥락에서 각각의 관계를 들여다 보고자 하였다.
  • 그래프 알고리즘은 그래프 형태로 표현하는 데이터 표현 방법을 다룬다. 여기에서는 데이터가 무엇인가에 대해서는 관심이 없다. 캐시, 메모리 구조, 병렬성, 압축 등 알고리즘의 효율성을 다룬다. 외부 메모리 주제로는 로 한 꼭지로 최근 다루어지고 있다.
  • 그래프 분석으로 들어가보면 알고리즘에서 더 나아가 프레임워크, 데이터베이스, 쿼리 등의 주제를 포괄한다. 물론 그래프 분석도 분석 나름이겠지만 줄리안 교수의 접근은 다분히 시스템 연구자로서 성능 개선을 중심에 둔다.
  • 그래프 데이터베이스/스토어를 보자면 현재 엄청나게 많은 종류의 솔루션이 있다. 각각은 알고리즘, 쿼리 언어, 프로그래밍 언어 등을 각각의 목적에 맞게 설계했을 것이다.
  • 그렇다면 지식 그래프는 어떻게 보아야 하는가? 그래프 데이터베이스가 다루는 데이터 타입 중에 하나 일 뿐이다. 지식 그래프를 전문적으로 다루는 사람은 사실 그래프 알고리즘, 그래프 데이터베이스에 필요한 시스템 프로그래밍 지식을 꼭 가지고 있을 필요는 없다. 오히려 대상 데이터를 보다 더 그래프 이론에 맞게 저장하고, 질의하는데에만 집중하면 된다. 각각의 독립된 연구 분야라는 것이다. 그렇기에 산업경영학과에서 지식 그래프를 연구하는 것이다. 이런 분들은 예컨데 를 그냥 쓰면 된다. 성능은 당장의 고려 대상이 아닐 것이다.
  • 그렇다면 을 스스로 해봐야 한다. 를 만들기 위해서 그래프 XX 의 무엇에 집중해야 하는가? 시점에서는 형태소 분석을 통해서 을 어떻게 설계 할 것인지가 중요하다. 필요한 그래프 관련 지식은 에서 다루는 정도면 충분하지 않을까싶다.

Related-Notes

References

마지막 수정일자
#원어민:에게 #린터 #역할창의적 인간의 시대 - 미래 인간상