$$ \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}{\mathsf{E}} \newcommand{\V}{\mathsf{Var}} \newcommand{\Corr}{\mathsf{Corr}} \newcommand{\Cov}{\mathsf{Cov}} \newcommand{\covariance}[1]{\Cov\left(#1\right)} \newcommand{\variance}[1]{\V\left[#1\right]} \newcommand{\variancewith}[1]{\V\left[#1\right]} \newcommand{\expect}[1]{\E\left[#1\right]} \newcommand{\expectwith}[2]{\E_{#1}\left[#2\right]} \renewcommand{\P}{\mathsf{P}} \newcommand{\uniform}[2]{\mathrm{Uniform}\left(#1 \dots #2\right)} \newcommand{\gdist}[2]{\mathcal{N}\left(#1, #2\right)} \DeclarePairedDelimiter{\norm}{\lVert}{\rVert} $$ \everymath{\displaystyle}

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 SIGMOD4, 2021
All Pairs Almost Shortest Paths DS FOCS5, 1996
  1. Transactions on Image Processingย โ†ฉ

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

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

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

  5. Annual Symposium on Foundations of Computer Scienceย โ†ฉ