이번 글에서는, 3가지 graph-processing algorithm(search, path, connectivity)에 대해 살펴볼 것이다. Why learning graph-processsing algorithm(s)? 그래프는 "광범위하게 사용되는 추상화(=abstraction) 모델"이다. (매우) 복잡한 구조를 가진 수 많은 객체(e.g., Internet, Seoul Metro)를 그래프로 추출(=abstract)할 수 있다. 그래프로 추상화되는 객체가 갖고 있는 problem(s)를 graph-processing problem(s)라 하며, graph-processing problem(s)의 algorithm(s)을 graph-processing algorithm(s)이라고 한다. grap..

이전 글에서는, 균형 검색 트리(balanced search tree)로 symbol table을 만들어 $\lg N$ 성능 보장을 보였다. 이번 글에서는, symbol table의 또 다른 설계 방식인 hash table에 대해 살펴볼 것이다. Hash table은 ordered ops(e.g., range search)를 지원하지 않는 대신 보다 좋은 성능을 보여준다. Definition of Hash Table key-indexed table(=array)에 item을 저장한다. 이때, hash function(=key를 array index로 반환해주는 함수)를 이용해 저장 위치를 찾는다. 이전 tree기반의 symbol table과 다르게, hash table기반의 symbol table은 eq..

저번 글에서는, 다차원 데이터의 range 연산을 효율적으로 처리해주는 kd 트리에 대해 살펴봤다. 일차원 $x_1$ 데이터와 $(x_1, y_1)$ 다차원 데이터의 차이는 차원의 개수다. 하지만 $x_1$ 데이터와 $[x_1, x_2]$ 구간 데이터의 차이는 차원의 개수가 아니라, 데이터의 개수다. 즉, 데이터는 데이터가 한 개지만, 구간 $[x_1, x_2]$ 데이터는 $x_1$부터 $x_2$까지의 데이터들을 포함하고 있다. 이번 글에서는, 구간 (=interval) 데이터의 range 연산 즉, interval intersection query를 효율적으로 처리해주는 interval search tree에 대해 살펴볼 것이다. 더보기 interval intersection query: given a..

BST를 이용하면, range search, range count 연산을 평균적으로 $\log N$시간 안에 수행할 수 있다. 하지만, 이는 1차원 데이터일 때만 가능했다. 다차원 데이터의 range 연산을 수행하는 방법에는 여러 가지가 있다. Scan: 모든 데이터를 비교해 한다. (연산 비용이 비싸다.) Grid: 벡터 공간을 $M^2$개 작은 공간으로 나누고, 탐색 범위와 겹치는 공간만 비교한다. (clustering된 데이터에 취약) 이번 글에서는, 다차원 데이터의 range search (or count) 연산을 효율적으로 처리해주는 kd 트리에 대해 살펴볼 것이다. kd 트리는 (BST를 확장한 개념으로) 자료 구조(data structure)는 같지만, 노드에 다른 제약 조건(or 의미 부여..

이번 글에서는, 2-3 트리를 일반화한 B-트리에 대해 살펴볼 것이다. 빅 데이터는 메모리 용량으로 부족하기 때문에, 외부 저장소(e.g., 하드 디스크)에 저장한다. 때문에, 빅 데이터의 특정 데이터(=instance)를 사용(read/write)하기 위해서는, 그 데이터가 속해 있는 page를 외부 저장소에서 메모리로 가져와야 한다. 여기서 발생하는 대부분의 비용은 해당 page를 메모리로 가져올 때까지 발생하는 page I/O 횟수이다. B-트리는 page I/O 횟수 획기적으로 줄여준다. Definition of B-Tree B-tree는 2가지 종류의 노드(=page)를 가지고 있는 트리다. external node(=leaf node): (정렬 순서를 유지한) M-1개의 실제 데이터 key(c..

저번 글에서 살펴본, BST는 무작위 삽입 순서일 경우에만, $\lg N$ 성능을 보여줄 뿐, 모든 삽입 순서에 대해 $\lg N$ 성능을 보장해주지 않는다. 이번 글에서는, 모든 삽입 순서에 대해 $\lg N$ 성능을 보장해주는 Balanced Search Tree에 대해 살펴볼 것이다. Balanced Search Tree에는 대표적으로 2-3 트리와 b-트리가 있다. 1. 2-3 Tree Definition 2-3 트리는 2가지 종류의 노드를 가지고 있는 트리다. 2-node: 1 key, 2 children 3-node: 2 key, 3 children 왼쪽 서브 트리의 모든 key는 부모 노드의 key보다 작다. 가운데 서브 트리의 모든 key는 부모 노드의 key 사이에 있다. 오른쪽 서브 트..