-
매트로이드에서의 Submodular Maximization에 대한 Deterministic algorithms
이 글에서는 매트로이드 상에서의 submodular maximization과 관련한 여러 연구의 결과들을 소개합니다. 보다 구체적으로는, 매트로이드와 submodular function 등 여러 개념의 정의를 소개하고, 매트로이드 상에서 submodular function을 최적화 하는 것이 실생활의 어떤 문제에 관련이 있는지 먼저 살펴봅니다. 그 후, 이 문제와 관련한 여러 연구 결과들을 살펴봅니다. 특히, 그 중에서도 (이 글에서는) 결정론적인 알고리즘들을 다룹니다. 1. 여러 개념 및 정의 먼저, submodular function 및 그에 대한 marginal gain을 정의합니다. 정의 1. 유한집합 $\mathcal{N}$에 대해 함수 $f : 2^\mathcal{N}...
-
LSM Tree
안녕하세요? 오늘은 데이터베이스 시스템에서, key-value 형태의 데이터를 저장할 때 좋은 성능을 내는 LSM Tree(Log-Structured Merge Tree)에 대해 알아보겠습니다. 보통 key-value 형태의 데이터를 저장할 때는 B-Tree를 많이 사용합니다. 하지만 만약 저장되는 매체가 disk라면, B-Tree는 많은 random access를 발생시켜 저조한 성능을 내게 됩니다. 하지만 이 때 LSM Tree를 사용하면, write를 할 때 append only 방식으로 저장을 하기때문에, write를 sequential하게 처리하여 성능을 향상시킬 수 있습니다. LSM Tree의 기본 구조 LSM Tree는 1996년 Patrick O’Neil의 논문 The Log-Structured Merge-Tree...
-
Gröbner basis
서론 최근 다변수 Coppersmith Method와 관련해 살펴보면서 Gröbner basis, 한국어로는 그뢰브너 기저에 대해서 접하게 되었습니다. 다변수 Coppersmith Method의 과정을 간략하게 설명하자면 다음과 같습니다. 변수 $x_1, x_2, \dots, x_k$에 대한 어떤 modular equation $f(x_1, x_2, \dots, x_k) \equiv 0 \pmod n$을 풀고 싶다. 단, $x_1, x_2, \dots, x_k$는 $n$에 비해서 매우 작다. Howgrave-Graham Theorem과 LLL algorithm을 적용해 $g_1(x_1, x_2, \dots, x_k) = 0, g_2(x_1, x_2, \dots, x_k) = 0, \cdots, g_l(x_1, x_2, \dots, x_k) = 0$...
-
Multi-Party Computation 1
1. Introduction 두 부자 Alice와 Bob이 있다. 두 명은 상대방에게 자신의 재산이 얼마인지 공개하지 않고 누구의 재산이 더 많은지 비교하고 싶다. 라는 문제를 생각해봅시다. 사실 이 문제를 해결하는 방법은 굉장히 간단합니다. Alice와 Bob이 모두 신뢰할 수 있는 Charlie가 있다면 Alice와 Bob이 Charlie에게 자신의 재산을 알려주고 Charlie가 비교를 한 후 누가 더 재산이 많은지를 두 사람에게 알려주면 됩니다. 하지만 두 사람이 모두 신뢰할 수 있는 제 3자가 없다면 상황이 많이 복잡해집니다. 결국 대소를 비교하려면 양쪽의 값을...
-
접미사 트리 (파트 1: 정의와 응용)
이 글은 트라이(trie) 자료구조에 대한 배경지식을 전제로 합니다. 부분문자열에 대한 다양한 문제를 선형 시간에 해결할 수 있는 접미사 트리 자료구조를 소개합니다. 이론 및 구현은 쉽지 않지만, 여러 문자열 문제들을 자명하게 만들거나 더 어려운 문자열 문제들을 해결하는 데 유용하게 쓸 수 있습니다. 문자열 $S$의 길이를 $m$이라고 하고, $i$번째부터 $j$번째까지 글자로 이루어진 부분문자열을 $S[i..j]$로 표기하겠습니다. 접미사 트라이 먼저, $S$의 모든 접미사로 이루어진 트라이를 생각해 봅시다. 이를 접미사 트라이(suffix trie)라고 합니다. 예를 들어 아래는 문자열 banana에 대한 접미사...