[Algorithm] What is PCY Algorithm ?

1. PCY Algorithm 이란 ?

PCY Algorithm은 A-Priori Algorithm과 비슷하지만 그보다 메모리 공간을 더 효율적으로 활용하는 Algorithm이라고 할 수 있다.

- Pass 1

Pass 1 에서는 각 item을 count 하여 저장하고 모든 pair를 생성해준다. 이때 생성해준 pair에 대해 hash값을 만들어 주어 해시 해시된 버킷으로 count 와 함께 bucket에 저장해줍니다. 우리는 이때 어떤 pair가 support(s)보다 높은지 낮은지만 따지면 되기때문에 pair의 구체적인 값은 알 필요가 없습니다.

 

- Pass 2

이후 Pass 2에서는 오직 frequent bucket에만 있는 pair만 count 해준다. 즉, 버킷이 s이하로 카운트 되면 그 버킷은 frequent한 pair가 아니다라고 할 수 있다. 그러므로 pair 가 {i, j}라 한다면 두가지 조건을 만족 하게되는데 첫번째는 두 item 모두 frequent item 이고 두번째는 pair {i , j}가 frequent bucket에 hash 되어 있다는 것이다. 

 

이렇게 원래 4-byte의 정수가 bits로 대체되었기 때문에(A-Priori와 다르게) 기존의 공간의 1/32만 차지하게되어서 메모리 효율이 훨씬 좋아집니다. Pass 2에서는 triples(item, item, count)를 사용해야만 하는데 그렇기 때문에 frequent pair가 많다면 비효율적이게 됩니다. 그래서 PCY는 pair의 2/3이상 줄여주어야만 A-priori보다 효율적으로 쓸 수 있게됩니다.