Multistage and Multihash
해당 포스팅은 스탠포드의 Jeff Ullman 교수님의 강의 와 Mining of Massive Datasets(Jure Leskovec, Anand Rajaraman, Jeff Ullman) 책 을 참고하였습니다.
The Multistage Algorithm
Multistage 알고리즘은 PCY 기반으로 몇개의 연속적인(successive) 해시 테이블을 사용해 후보 pair의 수를 더 줄이는 알고리즘입니다.
여기서 tradeoff 는 Multistage가 frequent pair을 찾기 위해 2개 패스 이상이 필요하다는 것입니다.
대략적인 도식도는 다음과 같습니다.
Multistage의 첫번째 패스는 PCY 와 같습니다.
해시테이블을 만들어 빈도 버킷은 비트맵으로 요약합니다.
Multistage에서 두번째 패스에서는, 후보 pair를 세지 않습니다.
대신, 남은 메모리를 다른 해시 함수를 사용한 해시 테이블을 위한 공간으로 사용합니다.
첫번째 해시 테이블의 비트맵이 가용 메모리의 1/32 을 사용하기 때문에, 두번째 해시 테이블도 거의 첫번째와 유사한 크기를 갖습니다.
Multistage의 두번째 패스에서, 다시 바스켓을 읽습니다.
첫번째 패스서 아이템을 카운트 했기 때문에, 아이템을 다시 카운트 할 필요는 없습니다.
기존 카운트 정보는 유지해야하는데, 두번째와 세번째 패스 모두에 필요하기 때문입니다.
두번째 패스에서, 아이템들의 특정 pair들을 해시해서 두번째 해시 테이블의 버킷에 담습니다.
여기서의 pair는 PCY 의 C2에 해당하는 pair 들입니다.
( 아이템 i,j 가 둘다 빈번한 경우 / pair가 frequent bucket 해시된 경우 )
그래서, 두번째 해시 테이블의 카운트의 합은 첫번째 패스에서 보다 매우 적습니다.
여기서 두번째 해시 테이블이 첫번째 버킷의 수의 31/32 만 갖고 있더라도, 첫번째 보다 두번째가 훨씬 더 적다는 것을 기대할 수 있습니다.
두번째 패스 후에는, 두번째 해시 테이블은 비트맵으로 요약되고, 그 비트맵은 메모리 새로운 공간에 저장됩니다.
두 비트맵의 합은 가용 메모리의 1/16 보다 적게 차지합니다. 그래서 3번째 패스에서 후보 pair 을 저장하기 위한 공간은 충분합니다.
여기서 C2 안의 pair {i,j} 는 다음과 같습니다.
- i,j 모두 frequent items 이다
- {i,j}가 첫번째 해시테이블에서 frequent bucket 으로 해시되었다.
- {i,j}가 두번째 해시테이블에서 frequent busket 으로 해시되었다.
여기서 3번째 조건이 Multistage와 PCY 의 구별점입니다.
여기서는 3번의 패스만 사용했지만, 이 Multistage 알고리즘은 첫번째와 마지막 패스 사이를 더 길게 늘려서 사용할 수 있습니다.
stage 를 늘릴수록, 이전 패스들의 각각으로부터의 비트맵이 각각의 패스에 저장되어야하므로,
비트맵을 위한 메모리가 늘어나, 가용 메모리 공간이 줄어들게 되는 것이 제약조건 입니다.
The Multihash Alogrithm
때때로, 단일 패스만으로도 Multistage 알고리즘의 이점의 얻을 수 있습니다. 이를 Multihash algorithm 이라고 합니다.
두개의 연속된 패스에서 두개의 다른 해시테이블을 사용하는 대신, 두개의 해시 함수와 분리된 두개의 해시테이블을 사용합니다. 6.7 처럼
한 번에 두 개의 해시 테이블을 사용하는 경우, 각 해시 테이블이 PCY의 하나의 큰 해시 테이블에 비해 절반의 버킷을 가지고 있어 정확도가 떨어질 수 있습니다.
PCY 에 버킷의 평균 카운터가 임계값보다 훨씬 낮은 한, 두개의 절반 크기의 해시 테이블을 사용할 수 있고, 두 해시 테이블의 버킷의 대부분이 빈번하지 않을 것이라는 것을 기대할 수 있습니다.
그래서 이 상황에서 우리는 Multihash 알고리즘을 사용할 수 있습니다.
Multihash에서 두번째 패스에서, 각 해시테이블은 비트맵으로 바뀝니다. 두개의 비트맵은, 정확히 하나의 비트맵의 크기를 차지합니다. (PCY에서 단일 비트맵 크기의)
C2 개 되기 위한 조건, 두번째 패스에서 필요한 카운트 요구는, Multistage에서 세번째 패스에서와 동일합니다. ( 아이템 둘다 빈번하고, 그 pair가 두개의 해시 테이블에 따른 빈도 버킷으로 해시된 pair )
Multistage가 패스를 여러개 사용할 수 있는것 처럼,
Multihash 에서는 첫번째 패스에서 여러개의 해시테이블로 나눌 수 있습니다.
Multihash에서 해시 테이블을 너무 많이 사용하는 경우, 버킷의 수가 임계값을 초과 할 수 있습니다.
이런 경우에는, 해시테이블에서 infrequent bucket이 매우 적어지고,
대부분의 pair 가 frequent bucket 에 들어가게되어
infrequent pair 가 후보가 될 가능성이 높아질 가능성이 생깁니다.
Comments