Bloom Filter (=Parallel Join Filter)
- 확률적으로 멤버쉽을 테스트하는 자료 구조, 실시간 탐지에 유용
hashing기법을 사용해서, 많은 block들의 miss, hit여부를 비교적 작은 data structure를 이용하여 저장
False positive 가능
Dancing Link
- NP-Complete 문제의 하나인 exact cover (subset의 collection이 다시 set을 정확하게 구성하는 조합)를 풀기 위해 알고리
즘 x의 기반이 되는 자료구조
즘 x의 기반이 되는 자료구조
Trie
- prefix가 일치하는 인덱스를 통해 빠르게 값을 찾을 수 있는 자료구조로서, 동적인 해시 트리라고 할 수 있다.
Suffix Tree
- suffix가 일치하는 인덱스 자료구조로서, 특정 문자열의 패턴을 검출하는 도구로 사용
Splay Tree
- 최근에 접근했던 데이터를 다시 빠르게 접근할 수 있는 자료구조로써 균형잡힌 이진 탐색 트리 구조(AVL)
Rope
- string 타입의 확장 자료형, STL rope container 참조
R-tree
- 2차원 공간 데이터의 포함 관계를 나타내기에 적합한 자료구조
KD-tree
- 다차원 공간 데이터의 구간 탐색이나 이웃 탐색에 유리한 자료구조
Bit array
- 비트맵 자료구조
QuadTree
- sparse한 2차원 데이터의 공간적인 관계를 표시하거나 이미지 표현에 유용한 자료구조
Inverted Index
- 문서에 포함된 키워드가 문서를 가리키도록 만들어진 인덱스 자료구조, full text search에 가장 쉽게 사용되는 자료 구조
Disjoint-Set data structure
- 집합을 partition 하거나 MST를 찾는 알고리즘을 지원하는 자료구조
Binary space partitioning
- 복잡한 구조의 객체를 단순한 볼록 다각형으로 partition 하는 알고리즘, 3D 객체를 2D 화면에 렌더링 하면서 색칠할 때 복
잡한 색칠 순서를 결정하는 데 도움을 주는 방법
잡한 색칠 순서를 결정하는 데 도움을 주는 방법
Van Emde Boas tree
- 기본 연산의 수행 시간이 O(log log n)인 트리 자료 구조. 한정된 2^n 비트 키 공간에서 특정 키를 이진 탐색으로 찾아내기
에 유리한 트리들의 트리 구조
Huffman coding
- 무손실 압축 알고리즘에 이용되는 기본 코딩 방식
Binomial heap
- 주로 두 개의 heap을 합치는 데 사용되는 binary heap
Fibonacci heap
Pairing heap
Spiral Storage
- 점진적으로 커지는 해시 기반의 저장소
Judy array
- Hash table 보다 빠른 해시 자료구조. 빠르고 공간 사용량이 적어서 주로 cache 알고리즘에 이용
Cuckoo hashing
- 해시 충돌 해소 알고리즘. 새로운 키를 놓을 때 같은 자리에 이미 놓여있던 기존 키를 다른 위치로 옮기고 새로운 키를 그
자리에 놓는 방법
자리에 놓는 방법
Circular buffer
- 링 버퍼
Counted B-tree
- 중앙값이나 백분위수를 빠르게 찾을 수 있는 b-tree 변형
Suffix array
- 부분 문자열을 빠르게 찾을 수 있는 인덱스 자료구조
Binary decision diagram
- binary decision tree를 효율적으로 재배치한 자료구조로서 회로 설계에서 주로 사용
Skiplist
- 계층적인 구조로 만들어진 리스트, 일반 linked list와는 달리 random access에 유리. 이진 탐색 트리의 장점을 도입한 list
출처 : http://terzeron.net/wp/