$$ \newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor} \newcommand{\ceil}[1]{\left\lceil #1 \right\rceil} \newcommand{\N}{\mathbb{N}} \newcommand{\R}{\mathbb{R}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\C}{\mathbb{C}} \renewcommand{\L}{\mathcal{L}} \newcommand{\x}{\times} \newcommand{\contra}{\scalebox{1.5}{$\lightning$}} \newcommand{\inner}[2]{\left\langle #1 , #2 \right\rangle} \newcommand{\st}{\text{ such that }} \newcommand{\for}{\text{ for }} \newcommand{\Setcond}[2]{ \left\{\, #1 \mid #2 \, \right\}} \newcommand{\setcond}[2]{\Setcond{#1}{#2}} \newcommand{\seq}[1]{ \left\langle #1 \right\rangle} \newcommand{\Set}[1]{ \left\{ #1 \right\}} \newcommand{\set}[1]{ \set{#1} } \newcommand{\sgn}{\text{sign}} \newcommand{\halfline}{\vspace{0.5em}} \newcommand{\diag}{\text{diag}} \newcommand{\legn}[2]{\left(\frac{#1}{#2}\right)} \newcommand{\ord}{\text{ord}} \newcommand{\di}{\mathrel{|}} \newcommand{\gen}[1] \newcommand{\irr}{\mathrm{irr }} \renewcommand{\deg}{\mathrm{deg }} \newcommand{\nsgeq}{\trianglelefteq} \newcommand{\nsg}{\triangleleft} \newcommand{\argmin}{\mathrm{argmin}} \newcommand{\argmax}{\mathrm{argmax}} \newcommand{\minimize}{\mathrm{minimize}} \newcommand{\maximize}{\mathrm{maximize}} \newcommand{\subto}{\mathrm{subject\ to}} \newcommand{\DKL}[2]{D_{\mathrm{KL}}\left(#1 \di\di #2\right)} \newcommand{\ReLU}{\mathrm{ReLU}} \newcommand{\E}{\mathbb{E}} \newcommand{\expect}[1]{\E\left[#1\right]} \newcommand{\expectwith}[2]{\E_{#1}\left[#2\right]} \renewcommand{\P}{\mathbb{P}} \newcommand{\uniform}[2]{\mathrm{Uniform}\left(#1 \dots #2\right)} \newcommand{\gdist}[2]{\mathcal{N}\left(#1, #2\right)} $$

CS Adventure

๊ณต๋ถ€ํ•œ ๋…ผ๋ฌธ ์ •๋ฆฌ / ๋ฆฌ๋ทฐ

Total views

What is This?

๋‚˜๋ฆ„ CS Research๋ฅผ ๊ฟˆ๊พธ๋Š”๋ฐ๋„ ์ „ํ˜€ ๊ทธ๋Ÿฐ์ชฝ์œผ๋กœ๋Š” ์ค€๋น„๊ฐ€ ์•ˆ ๋œ๊ฑฐ ๊ฐ™์•„์„œ, ์ง€๊ธˆ๋ถ€ํ„ฐ๋ผ๋„ ๋…ผ๋ฌธ์ฝ๊ธฐ๋‚˜ ์„ธ๋ฏธ๋‚˜ ์ฐธ์„ํ•˜๊ณ  ์ •๋ฆฌํ•˜๊ธฐ๋ฅผ ์กฐ๊ธˆ์”ฉ ํ•ด ๋ณด๋ ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค. ์žฌ๋ฐŒ์–ด ๋ณด์ด๋Š” ๊ฒƒ๋“ค / ์ถ”์ฒœ๋ฐ›์€ ๊ฒƒ๋“ค ๋“ฑ๋“ฑโ€ฆ ์„ ์ฝ์–ด๋ณด๊ณ  ์žฌ๋ฐŒ๋Š” ์ฃผ์ œ๋“ค์ด ์žˆ์œผ๋ฉด ์—ฌ๊ธฐ์— ์ •๋ฆฌํ•  ๊ณ„ํš์ž…๋‹ˆ๋‹ค. ๊ฐœ์ธ์ ์ธ ํฅ๋ฏธ๊ฐ€ ์ตœ์šฐ์„ ์ด๋‹ค๋ณด๋‹ˆ ๋ง‰ ์„ธ์„ธํ•œ ๊ฒฐ๊ณผ๊ฐ™์€๊ฒƒ๋ณด๋‹จโ€ฆ ํ•ต์‹ฌ์ ์ธ ์•„์ด๋””์–ด๊ฐ€ ์žฌ๋ฐŒ๋Š”๊ฐ€? ๊ฐ€ ๊ฐ€์žฅ ์ค‘์š”ํ•œ๊ฒƒ ๊ฐ™์Šต๋‹ˆ๋‹ค.

์ œ๊ฐ€ ์ด ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๊ฒŒ์‹œ๊ธ€์„ ์ž‘์„ฑํ•˜๋Š” ๊ธฐ๋ณธ ํ‹€์€ ๋‹ค์Œ๊ณผ ๊ฐ™์Šต๋‹ˆ๋‹ค.

  1. Introduction : ์†Œ๊ฐœ, ์ด ๋…ผ๋ฌธ์„ ์ฝ๊ฒŒ๋œ ๊ณ„๊ธฐ, Historically ์–ด๋–ค ์œ„์น˜์— ์žˆ๋Š”์ง€.
  2. Key ideas : ๋ณธ๋ฌธ์˜ Key idea๋ฅผ ์ ๋‹นํžˆ ์ œ๊ฐ€ ์ดํ•ดํ•œ ๋ฐฉ์‹๋Œ€๋กœ ์ •๋ฆฌํ•ฉ๋‹ˆ๋‹ค.
  3. Conclusion : ๋…ผ๋ฌธ์˜ ๊ฒฐ๋ก 
  4. Thoughts : ์ฝ์œผ๋ฉด์„œ ๋“ค์—ˆ๋˜ ์งง์€ ์ƒ๊ฐ๋“ค์„ ์ •๋ฆฌํ•ฉ๋‹ˆ๋‹ค. ์งง์€ ์ƒ๊ฐ๋“ค์€ ์ •๋ง ๋Š๋‚Œ์ผ์ˆ˜๋„ ์žˆ๊ณ , ๋ญ”๊ฐ€ ์˜ค ์ด๋Ÿฐ๊ฑด ์™œ ์•ˆ ๋‹ค๋ฃจ์ง€? ํ•˜๋Š” ๊ฑธ์ˆ˜๋„ ์žˆ์„ํ…๋ฐ ํ•™๋ถ€์ƒ์˜ ๋ฒ•์น™ ์— ๋”ฐ๋ผ, ์ง€๊ธˆ์˜ ์ œ๊ฐ€ ๋…ผ๋ฌธ์„ ์ฝ๊ณ  ๋ญ”๊ฐ€ ๋– ์˜ค๋ฅธ๊ฒŒ ์žˆ๋‹ค๋ฉด 100% ๋‘˜ ์ค‘ ํ•˜๋‚˜์ž…๋‹ˆ๋‹ค. ๋ˆ„๊ตฐ๊ฐ€ ์ด๋ฏธ ํ•ด ๋†จ๊ฑฐ๋‚˜, ์•ˆ ๋˜๋Š” ๊ฑฐ๊ฑฐ๋‚˜โ€ฆ ํ•˜์ง€๋งŒ ์—ฌ์ „ํžˆ ์ด๋Ÿฐ ์ƒ๊ฐ์„ ํ•ด๋ณด๋Š” ๊ฒƒ๋“ค์€ ์˜๋ฏธ์žˆ์ง€ ์•Š์„๊นŒ ์‹ถ์Šต๋‹ˆ๋‹ค. ๊ถ๊ธˆํ–ˆ๋˜ ์ ์„ ๋‹ค๋ฅธ ๋…ผ๋ฌธ์„ ์ฐพ์•„๋ณด๋Š” ๊ณ„๊ธฐ๋กœ ์‚ผ์œผ๋ ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค.

๊ฒฝ์šฐ์— ๋”ฐ๋ผ, ์–ด๋–ค ๋…ผ๋ฌธ A์™€ ๊ทธ ํ›„์†์—ฐ๊ตฌ B, C, D๋ฅผ ํ•œ๋ฒˆ์— ๋‹ค๋ฃจ๊ธฐ๋„ ํ•  ์˜ˆ์ •์ž…๋‹ˆ๋‹ค.

Topic (๋ถ„์•ผ) ๋Š”, ์ผ๋ฐ˜์ ์œผ๋กœ๋Š” Arxiv์˜ ๊ธฐ์ค€์„ ๋”ฐ๋ฆ…๋‹ˆ๋‹ค. Arxiv์— ์˜ฌ๋ผ์™€์žˆ์ง€ ์•Š์€ ๋…ผ๋ฌธ์€ ์ฝ์€ํ›„์— ์ œ๊ฐ€ ์ตœ๋Œ€ํ•œ ๋น„์Šทํ•˜๊ฒŒ ๋ถ„๋ฅ˜ํ•ด ๋„ฃ์—ˆ์Šต๋‹ˆ๋‹ค. (์•„๋งˆ๋„) Arxiv ๋ถ„๋ฅ˜ ์ฝ”๋“œ ์ค‘ ์ œ๊ฐ€ ๋ณด๊ฒŒ๋  ๋…ผ๋ฌธ๋“ค์€ ์ด์ •๋„๊ฐ€ ๋ฉ”์ธ์ผ๋“ฏ ํ•ฉ๋‹ˆ๋‹ค. ํŠนํžˆ ์žฅ๊ธฐ์ ์œผ๋กœ๋Š” CC, DM, DS.

  • AI : Artificial Intelligence
  • CC : Computational Complexity
  • DM : Discrete Mathematics
  • DS : Data structures / Algortihms
  • NA : Numerical Analysis

๊ทธ๋ž˜ํ”„์— ๊ด€ํ•œ ๋งŽ์€ ๋…ผ๋ฌธ๋“ค (์ €๋Š” DM์ด๋‚˜ DS์ฒ˜๋Ÿผ ๋ฐ›์•„๋“ค์ด๊ฒŒ ๋˜๋Š”) ์€ ์‹ค์ œ๋กœ๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™์€ Topic์œผ๋กœ ๋งŽ์ด ์˜ฌ๋ผ์˜ต๋‹ˆ๋‹ค. ์ œ๊ฐ€ (์•„๋งˆ๋„) DB management์— ๊ด€ํ•œ ๋ญ”๊ฐ€๋ฅผ ์ฝ์„ ์ผ์€ ์—†์„ ๊ฒƒ์ด๋ฏ€๋กœ, ์—ฌ๊ธฐ ๋‚ด์šฉ๋“ค์€ ๊ฑฐ์˜ 100% ๊ทธ๋ž˜ํ”„์— ๊ด€ํ•œ ๋‚ด์šฉ์ž…๋‹ˆ๋‹ค.

  • DB : Databases
  • SI : Social and Information Networks

๋‹น๋ถ„๊ฐ„์€ ์ˆ˜๋ฆฌ๊ณผํ•™๋ถ€ ์กธ์—…๋…ผ๋ฌธ์„ ์œ„ํ•ด CV, AI ์ชฝ๋„ ๋งŽ์ด ๋ณด๊ฒŒ ๋  ์˜ˆ์ •์ž…๋‹ˆ๋‹ค.

  • CV : Computer Vision

์–ด๋–ค ํ•œ ์ฃผ์ œ๊ฐ€ ์žˆ๊ณ , ์ด ์ฃผ์ œ์— ๊ด€ํ•œ ์—ฌ๋Ÿฌ ๋…ผ๋ฌธ์ด ์žˆ๋Š” ๊ฒฝ์šฐ, ๊ทธ ์ฃผ์ œ์— ๋Œ€ํ•œ ๊ฐœ์š”๋ฅผ ์ ๋Š” ํฌ์ŠคํŒ…์„ ํ•˜๋‚˜์”ฉ ๋” ์“ฐ๊ธฐ๋„ ํ•  ๊ฒƒ ๊ฐ™์Šต๋‹ˆ๋‹ค. ์ด ํฌ์ŠคํŒ…์€ ์•„๋ž˜ ๋ฆฌ๋ทฐ ๊ธ€์—์„œ ๋…ผ๋ฌธ ๋ฆฌ๋ทฐ ์™ธ์˜ ์ผ๋ฐ˜์ ์ธ ๊ฐœ๋…์— ๋Œ€ํ•œ ์†Œ๊ฐœ๋ฅผ ์ตœ์†Œํ™”ํ•˜๊ธฐ ์œ„ํ•ด ์ฃผ๋กœ ์ž‘์„ฑํ•ฉ๋‹ˆ๋‹ค.

Title (Link to post) Topic Published
Active Contours Without Edges NA, CV IEEE TIP1, 2001
DELTACON: A Principled Massive-Graph Similarity Function SI SDM2, 2013
In-Memory Subgraph Matching: An In-depth Study3 DS, DB SIGMOD4, 2020
Versatile Equivalences : Speeding up Subgraph Query Processing and Subgraph Matching DS, DB FOCS[^focs], 1996
All Pairs Almost Shortest Paths DS SIGMOD4, 2021
  1. Transactions on Image Processingย โ†ฉ

  2. SIAM International Conference on Data Miningย โ†ฉ

  3. Subgraph Isomorphism ๋ฐฉ๋ฒ•๋“ค์„ ๋น„๊ตํ•˜๊ณ , ์ด๋“ค์„ ๋ชจ๋‘ ๊ตฌํ˜„ํ•˜์—ฌ ํ†ต์ผ๋œ ํ”„๋ ˆ์ž„์›Œํฌ ์œ„์—์„œ ์‹คํ—˜ํ•œ ๋…ผ๋ฌธ์ด๋ผ์„œ ๋ณ„๋„๋กœ ํฌ์ŠคํŒ…์„ ์ •๋ฆฌํ•˜์ง€๋Š” ์•Š์•˜์Šต๋‹ˆ๋‹ค.ย โ†ฉ

  4. Proceedings of the ACM SIGMOD International Conference on Management of Dataย โ†ฉย โ†ฉ2