[GPG 2 글 1.20] GPG2의 블룸필터에 대한 2가지 의문

GPG 시리즈 관련 질답, 논의 공간.

Moderator: 류광

Gamza
Posts: 610
Joined: 2001-10-11 09:00
Contact:

Post by Gamza »

안녕하세요?

감자 성수입니다.

GPG2의 블룸필터를 보다가 두가지 풀리지 않는 의문이 있어서

질문을 올립니다.

이곳이 먹통이라 하이텔에 올렸었는데...아무런 리플이 없더군요

읽어보시고 혹시나 생각나는거 있으시면 리플 부탁드립니다.

--------------------------------------------------------------
1. Page204의 예제 2에서...

9000개의 입력에 대한 95%의 정확도를 갖는 블룸필터를 만들려면 64Kbit가

필요하다고 했는데요...그냥 9000bit짜리 100%정확도를 갖는

결과값 배열을 사용하는게 낳지 않을까요?

array_bits = nphases * max_inputs * 약 1.44

이 공식만 봐도 블룸필터의 배열크기는 결과배열보다 무조건 커진다는

말이 되는데...

제가 어데를 잘못 이해한걸까요?

--------------------------------------------------------------
2. Page198의 작동방식 바로 윗줄...

100%정확도가 필요하면 블룸필터가 true를 돌려주었을때 원래 비싼함수를 써라

라고 되어있는데요...

원래 블룸필터라는게 false를 돌려주면 어차피 비싼함수를 돌려야하니...

결국 100%정확도가 필요하면 무조건 비싼함수를 돌려라...가 되지않을까요?

그림 1.20.3도 실제로 그렇게 구현이 되어있네요.

(결국 블룸필터는 동적으로 구성하면 안된다는 말인지...)
--------------------------------------------------------------

보아하니 검증된지도 한참된 공신력있는 알고리즘 같은데..

무었을 잘못이해했길래 이런 오해가 생기는지 궁금합니다.

부디 저의 딸리는 이해력을 보충해 주셨으면...

감자 성수올림...@~

MAIL: [email protected]
HOME: http://www.Gamza.net
류광
Posts: 3805
Joined: 2001-07-25 09:00
Location: GPGstudy
Contact:

Post by 류광 »

어렵네요...
우선 드는 생각은... 일반적인 공간적 색인(연관 배열)의 조회 속도(해시 충돌에 관련된)에 비한 블룸 필터의 조회 속도 이득은 어느 정도인가..

메모리 낭비를 상쇄할 만큼 이득이 크다면 블룸 필터를 사용할 수 있을 것이고, 그렇게 크지 않다면, 블룸 필터를 일종의 참-거짓 학습 능력을 가진 구조라고 간주하고, 테스트 기간동안 블룸 필터를 충분히 채우고 그 결과를 저장한 후 릴리즈 버전에서는 일반적인 공간적 색인을 사용할 수도 있지 않을까요. (그런데 그렇게 하려면.. 해시 키에서 원래 입력값들을 복원하는 것은 불가능할 것이니... 입력값들도 일일이 저장해 두어야 할 것 같네요).

2번 문제는 허용할 수 있는 오차를 어느 정도로 할 것인가의 문제가 될 수도 있겠습니다... 예를 들어 실내 엔진을 위한 가시성 판정에 블룸 필터를 적용한다면 오차율을 1% 대로 잡아도 좋지 않을까요? 어쨌든 가양성 경우를 무시하고 블룸필터의 결과를 무조건 신뢰한다면 충분히 이득이 있을 것 같습니다...

한 가지 걱정되는 것은.. 다이제스트 기반의 신뢰성 있는 해시 함수들은 수백바이트의 값 중 단 1 비트만 틀려도 전혀 다른 해시 값을 산출하잖아요. 문자열의 경우 'A'와 'B'는 단 1 비트 차이지만 의미는 전혀 다르다는 점에서 의미가 있겠지만... 3D 엔진의 어떤 함수라고 한다면 매개변수들이 주로 실수 값을 쓰는데 0.000001과 0.000002의 차이는 사실 별 의미가 없죠.. 그래서 예를 들어 게임 내에서 단 1 미터 정도 또는 5도 정도 회전하는 데에 수천개의 서로 다른 입력값들이 생겨버릴 수도있겠고.. 결국 블룸 필터가 너무 깐깐해질 것 같습니다. 실수를 위한 어떠한 해시 함수를 만들어야 할 것인지...


.. 좀 더 생각해 볼께요...
Zho
Posts: 328
Joined: 2001-08-02 09:00
Location: 취미게임개발자
Contact:

Post by Zho »

제가 생각하기에는...
아래에 저의 답변은 편의상 "아마도" 라는 전제를 모두 생략했습니다. ^^
1. Page204의 예제 2에서...

9000개의 입력에 대한 95%의 정확도를 갖는 블룸필터를 만들려면 64Kbit가

필요하다고 했는데요...그냥 9000bit짜리 100%정확도를 갖는

결과값 배열을 사용하는게 낳지 않을까요?

array_bits = nphases * max_inputs * 약 1.44

이 공식만 봐도 블룸필터의 배열크기는 결과배열보다 무조건 커진다는

말이 되는데...

제가 어데를 잘못 이해한걸까요?
만약, 입력값이 단순히 1 부터 9,000 까지의 정수로 된 데이터라면 9,000 비트짜리
100 퍼센트 정확도를 갖는 결과값 배열을 사용할 수 있을 것입니다. 하지만,
일반적으로는 그러한 경우는 드믈 것입니다. 예를 들면, 1부터 9,000,000 까지의
정수로 된 데이터 중에서 9,000 개의 데이터만을 입력으로 받는다고 했을 때에, 각
정수를 9,000개의 배열에 딱 떨어지도록 해싱하는 함수가 존재한다면 모르지만,
그렇지 않을 경우에는 각 데이터마다 하나씩 하나씩 매핑하는 테이블이 별도로
필요한 상황이 될 수도 있습니다.
2. Page198의 작동방식 바로 윗줄...

100%정확도가 필요하면 블룸필터가 true를 돌려주었을때 원래 비싼함수를 써라

라고 되어있는데요...

원래 블룸필터라는게 false를 돌려주면 어차피 비싼함수를 돌려야하니...

결국 100%정확도가 필요하면 무조건 비싼함수를 돌려라...가 되지않을까요?

그림 1.20.3도 실제로 그렇게 구현이 되어있네요.

(결국 블룸필터는 동적으로 구성하면 안된다는 말인지...)
블룸 필터는 원초적인 전제가 "허용가능한 오차"이기 때문에, 100% 정확도가
전제가 된다면, 이 블룸필터를 쓸 필요가 없을 듯 합니다. 오히려 성능이 더 떨어지
지 않을까요?
Gamza
Posts: 610
Joined: 2001-10-11 09:00
Contact:

Post by Gamza »

아...그렇군요...
유한개의 입력을 간단하게 해싱할수 없는경우에 사용할수 있겠군요...

100%정확도를 가져야 하는경우엔 블룸필터가 의미가 없다...는

좀...생각해 봐야 할것 같네요.

답변 감사합니다.

...

참...블룸필터가 주로 false를 리턴하는 함수에 주로 사용되는것처럼

쓰여있는데요...원래(비싼)함수가 false를 주로 리턴한다면...

블룸필터도 상당히 많은경우 false를 리턴할테고...그러면...

원래함수가 상당히 많이 호출될지도 모른다는 결론이 나오는데요.

그렇다면...

블룸필터는 런타임으로 사용하기전에 실제 사용할 입력값들을 사용해서

충분히 채워넣는 작업을 해야한다는 말이겠군요.

런타임에는 블룸필터가 false를 돌려주었을때 무조건 false로 단정지어버리고

말이죠...

Page205 에 있는 동적계산이란...이런 사전계산을 말하는거겠죠?

맞남...???

감자 성수올림...@~
Zho
Posts: 328
Joined: 2001-08-02 09:00
Location: 취미게임개발자
Contact:

Post by Zho »

음..
블룸필터는 런타임으로 사용하기전에 실제 사용할 입력값들을 사용해서

충분히 채워넣는 작업을 해야한다는 말이겠군요.
런타임으로 사용한다는 것은 사전에 충분히 채워넣는 작업이 필요없다는 말이 아닌가요?
Page205 에 있는 동적계산이란...이런 사전계산을 말하는거겠죠?
그러한 사전 계산에 반대되는 개념이 아닌가 합니다.

205 페이지에 보면,
블룸 필터 배열을 동적으로 구축하면, 1)자주 판정되는 비싼 함수 매개변수가 한 번만 호출되어도 되며, 2)판정되지 않은 함수 매개변수가 비트 배열 안에서 자리를 차지하는 일도 생기지 않는다.
라고 되어 있는데, 이는 사전에 배열을 채워넣지 않았기 때문에

1). 비싼 함수 매개변수가 처음 호출될 때 배열에 채워 넣어져서, 그 다음 번에는 배열을 참조하는 것이 아닐까요? 만약, 사전에 미리 채워 넣기만 하고 동적으로 추가하지 않는다면, 미리 저장하지 못한 비싼 함수 매개변수가 운나쁘게 자주 불리게 되는 경우가 발생할 수도 있기 때문이죠.

2). 만약, 사전에 미리 채워 넣는다면, 실제로는 불리지도 않을 함수 매개변수도 비트 배열 안에서 자리를 차지하게 되겠죠. 하지만, 동적으로 추가한다면, 실제 호출되는 매개변수만 비트 배열을 차지하게 되어 더욱 효율적일 수가 있다는 말인것 같습니다.

p.s) 다시 생각해 보니 예외목록을 사용한다면, 블룸필터도 100%의 신뢰성을 필요로 하는 경우에 써도 효율적이겠구나라는 생각이 듭니다.
Gamza
Posts: 610
Joined: 2001-10-11 09:00
Contact:

Post by Gamza »

블룸필터의 동적갱신
<PRE>
만약 실시간으로 블룸필터를 채운다고 생각하면...
(아래는 책에 나온 소스 를 한글로 재구성 한것입니다. - Page204 그림1.20.3)

if( 블룸필터 )
{
// 참일수도 있지만 거짓일수도 있다.
// 예외(가양성)목록에 없으면 비싼함수 호출.
// 가양성의 확률은 매우 낮기때문에
// 사실상 거의 모든 경우에 비싼함수 호출.
if( 예외목록에 있으면 ) return 거짓;
***************************************
진짜결과 = 비싼함수 호출
***************************************
if( ! 진짜결과 ) 예외목록갱신
return 진짜결과;
}
else
{
// 정말로 거짓이거나 처음들어오는 입력
// 처음들어오는 입력인지 아닌지를 알수 없기때문에
// 비싼함수 호출...
***************************************
진짜결과 = 비싼함수 호출
***************************************
if( 진짜결과 ) 블룸필터 갱신
return 진짜결과;
}

블룸필터의 리턴값(true/false)에 상관없이 거의 항상 비싼함수가

호출되는것 처럼 보이는데요......음...

또 무언가 오해가 있는걸까요?

감자 성수올림...@~

PS 만약 100 % 정확도를 요구하는 경우가 아니라면 예외목록을 사용하지 않고
블룸필터가 true를 반환했을때 곧바로 return true; 라고 쓸수도 있겠습니다.
하지만 이전글에 말씀드렸듯이...비싼함수가 대부분의 경우 false를 리턴하는
성격의 함수라면....상당히 많은경우 false에 의해 계속해서 비싼함수가
호출되리라 생각됩니다.
...
요는...실시간으로 블룸필터를 채우려면...
블룸필터가 false를 반환했을때(-상당히 많은경우-)
비싼함수를 호출해야 한다는것이 문제라는...
</PRE>


<font size=-1>[ 이 게시물 는(은) 수정됨 by : Gamza 수정 시간: 2002-04-04 14:23 ]</font>
Zho
Posts: 328
Joined: 2001-08-02 09:00
Location: 취미게임개발자
Contact:

Post by Zho »

블룸필터의 리턴값(true/false)에 상관없이 거의 항상 비싼함수가
호출되는것 처럼 보이는데요......음...
또 무언가 오해가 있는걸까요?
코드에 의하면 블룸필터의 리턴값이 true 이며, 예외목록에 있을 때에만 비싼함수를
호출하지 않는군요. 매개변수가 항상 다르다면, 매번 비싼 함수만 불릴 것 같습니다.
대신, 결과가 true 인 어떤 매개변수가 자주 쓰인다면, 비싼 함수가 많이
안 불리겠죠. 어디에 적용하는가에 따라 다를 것 같습니다. 잘못 적용하면 거의 항상
비싼함수만 불리게 되어 블룸필터를 안쓰는 거랑 별반 다를게 없을 수도 있지 않을
까요? 암튼, 결론은 100%의 신뢰도를 가지며, 동적으로 구성했을 때에는,
비싼 함수가 많이 호출될 것 같다 라는 것입니다.
하지만 이전글에 말씀드렸듯이...비싼함수가 대부분의 경우 false를 리턴하는
성격의 함수라면....상당히 많은경우 false에 의해 계속해서 비싼함수가
호출되리라 생각됩니다.
...
요는...실시간으로 블룸필터를 채우려면...
블룸필터가 false를 반환했을때(-상당히 많은경우-)
비싼함수를 호출해야 한다는것이 문제라는...
false 일 때 계속해서 비싼함수가 호출되는 것이 문제라면, true와 false 를 바꾸어
해석하는 방법도 있을 것 같긴 한데요. 즉, true 와 false 의 개념을 뒤바꿔 생각하
는 거죠. 하지만, 블룸필터라는 것이 근본적으로 true 와 false 의 값을 갖는 비싼
함수의 어느 한쪽(true 혹은 false)에 대하여 기록을 남기는 것이라고 생각한다면,
그것이 true 가 되었건 false 가 되었건 어느 한쪽은 기록이 남아 있지 않기 때문에,
매번 비싼 함수를 호출해야 하는 것이 아닐까요? 다시 말해서, 비싼함수가 많이 호출되도 어쩔 수 없다라는 생각이 듭니다.
Gamza
Posts: 610
Joined: 2001-10-11 09:00
Contact:

Post by Gamza »

블룸필터가 true를 반환하면...
코드에 의하면 블룸필터의 리턴값이 true 이며, 예외목록에 있을 때에만 비싼함수를
호출하지 않는군요. 매개변수가 항상 다르다면, 매번 비싼 함수만 불릴 것 같습니다.
대신, 결과가 true 인 어떤 매개변수가 자주 쓰인다면, 비싼 함수가 많이
안 불리겠죠.
문제는 '블룸필터의 리턴값이 true 이며, 예외목록에 있을 때'가 바로 '가양성'을

의미 한다는 거죠.

즉...비싼 함수가 호출되지 않을일이 거의 없다는 겁니다.

따라서 결과가 true인 매개변수가 자주 호출되더라도 비싼함수가 자주호출되긴

마찬가지죠...
류광
Posts: 3805
Joined: 2001-07-25 09:00
Location: GPGstudy
Contact:

Post by 류광 »

참고자료를 보면..
좀 의심스러운 구석이 보입니다. (게임에서의 활용 측면에서요)

http://beachsoftware.com/bloom/white_paper.html 를 보면 쇼핑몰의 장바구니를 예로 들면서 다음과 같은 구절이 나옵니다.

We can optimize this by building a 'Bloom filter' that will hold the status of web shoppers baskets. The Bloom filter will accurately tell us if the basket is empty and with a high degree of accuracy if it has content. This false positive case is acceptable as long as the rate is low, because for each TRUE case we get back from the Bloom filter, we will hit the database to get the actual basket content.
쇼핑몰의 경우에는 말이 됩니다. 바구니가 비었다는 것은 특정한 사용자 ID로 바구니 저장 함수를 호출한 적이 없었다는 뜻이구요. 따라서 "바구니 안에 뭐가 들었나"의 질문에는 답할 수 없지만, "바구니가 (안)비었나?"라는 질문에는 항상 100% 확실한 답을 알 수 있는 것이지요... (또한 대부분의 쇼핑몰의 경우 바구니가 비어 있을 경우가 압도적으로 많을 것이구요) 이런 상황이라면 비싼 함수 호출(DB 조회)를 엄청나게 절약할 수 있을 것입니다.

이 이야기는 "특정한 매개변수 조합이 저장된 적이 없었음"이라는 사실 자체가 중요한 정보가 될 수 있을 때에만 블룸 필터가 의미가 있다는 이야기가 아닐까요?

게임에서는... 비싼 함수의 진짜 결과 자체보다, "그런 매개변수들로 비싼 함수가 호출된 적이 없었다"라는 사실이 더 유용한 경우가 어떤 것일지... 좀 막막하네요.



<font size=-1>[ 이 게시물 는(은) 수정됨 by : 류광 수정 시간: 2002-04-06 22:47 ]</font>
류광
Posts: 3805
Joined: 2001-07-25 09:00
Location: GPGstudy
Contact:

Post by 류광 »

또한...
This false positive case is acceptable as long as the rate is low, because for each TRUE case we get back from the Bloom filter, we will hit the database to get the actual basket content.

대충 번역하면 "가양성이 존재해도 상관없다.. TRUE이면 어차피 비싼 함수를 호출할 것이니까..."라는 말이네요.. 따라서 감자님의 의심은 아주 정확한 것 같습니다... 결국 필터가 false를 돌려주는 것 자체에서 뭔가를 얻을 수 있어야 한다는 이야기인 것 같은데요...

그렇다면 198p에 동그라미 목록으로 나온 세 가지 사례는 좀 잘못된 것 같네요. 차라리 대규모 온라인 RPG에서 현재 플레이어가 특정 퀘스트를 수행한 적이 '없는가'를 밝힌다던가..(퀘스트를 수행할 때 그 플레이어의 ID와 퀘스트 ID 등으로 특정한 비싼 함수를 호출한다고 하구요) 그런 쪽이 더 좋지 않을까요..



<font size=-1>[ 이 게시물 는(은) 수정됨 by : 류광 수정 시간: 2002-04-06 22:59 ]</font>

<font size=-1>[ 이 게시물 는(은) 수정됨 by : 류광 수정 시간: 2002-04-06 23:00 ]</font>
Gamza
Posts: 610
Joined: 2001-10-11 09:00
Contact:

Post by Gamza »

오호...false가 중요하다....
(감탄...감탄....)

전혀 생각지 못했던 사항이로군요...

본능적으로 true가 중요한 정보라고만 생각하다보니...

새로운 시각으로 다시한번 공부해야겠네요...
Zho
Posts: 328
Joined: 2001-08-02 09:00
Location: 취미게임개발자
Contact:

Post by Zho »

false 를 돌려 주었을 때
만약,

1) 필터배열이 동적으로 구성되지 않고 정적으로 이미 구성되어 있다고 치면,
: false 가 아주 유용한 값이 되겠죠. 비싼 함수를 호출하지 않고 바로 결과가 false 인지 알 수 있으니 말요.

2) 하지만, 필터배열을 동적으로 구성한다고 하면,
: 블룸필터의 값이 false 라는 것은 값이 false 라는 의미가 아닌, 아직 저장된 적이 없다라는 의미가 되어 버립니다. 따라서 동적인 경우에는 false 의 경우에도 비싼 함수를 호출해야 하죠.

위의 사항으로 추측컨대, 류광님 말씀처럼 198 페이지의 블룸필터가 쓰일만한 세 가지 경우는 온라인 기반의 게임상에서 게임 상태 정보를 서버에 저장하고 수많은 클라이언트들이 중복되는 요구들을 자주 요청하는 상황에서는 요긴할 것 같습니다. 즉, 서버에 씬그래프를 저장하고 충돌검사나 컬링테스트를 서버에서 한다는 조건이 있다면,어느정도 이해가 갑니다. 그렇지 않고 클라이언트에서 충돌검사를 하는 목적이라면, 어차피, 모든 객체에 대해서 한번씩만 검사한다고 하면, 큰 효과는 없을듯 합니다만......
류광
Posts: 3805
Joined: 2001-07-25 09:00
Location: GPGstudy
Contact:

Post by 류광 »

flipCode의 글에 있는 사례는 충분히 설득력이 있네요..
같은 저자가 쓴 http://www.flipcode.com/tutorials/tut_bloomfilter.shtml 의 "Enter The Game Designer" 섹션에 나온 사례를 보면 수긍이 갑니다.

여기서 몇 가지 생각해 볼 것은...

1. 비싼 함수가 반드시 bool 값을 반환할 필요는 없을 것 같습니다. 다른 말로 하면 블룸필터의 반환값이 비싼 함수의 반환값과 연관될 필요가 없다는 뜻도 되구요... 이는 블룸필터는 단지 특정한 매개변수 조합이 '언급된 적이 있는지'를 가리는 용도로 쓰인다고 할 때의 이야기입니다.

flipCode 글의 예라면, 위치 (10, 20, 30)이라는 좌표들가 언급된 적이 있다면 그 위치에 트리거가 존재할 가능성이 있는 것이고, 언급된 적이 없다면(블룸 필터가 false를 반환) 트리거가 확실히 존재하지 않는 것이고...

반면 비싼 함수 자체는 단지 트리거가 있다 없다가 아니라 트리거에 대한 정보를 돌려주는 것일 수도 있겠죠.(NULL이면 없는 것, 그 외에는 트리거 정보를 담은 구조체 등으로 해서 있다 없다를 구분할 수도 있겠지만, 어쨌든 블룸 필터의 반환값과 직접적인 연관이 존재할 필요는 없을 것입니다)

2. 일반적인 공간적 색인 또는 연관 배열과의 차별성은, 오차를 허용함으로써 저장 공간을 크게 줄일 수 있다는 것이 아닐지.... 해시 키가 128 비트라면 2의 128 승의 해상도를 가지는 것이고, 저장공간도 적어도 2의 128승 비트가 되어야 하겠지만 가양성 확률과 위상 분할에 의해 그보다 훨씬 적은 비트들로도 가능하다는 게 특징이 아닐까요...(수학적인 검토가 필요하겠지만요).

이에 관련해서
예를 들면, 1부터 9,000,000 까지의
정수로 된 데이터 중에서 9,000 개의 데이터만을 입력으로 받는다고 했을 때에, 각
정수를 9,000개의 배열에 딱 떨어지도록 해싱하는 함수가 존재한다면 모르지만,
그렇지 않을 경우에는 각 데이터마다 하나씩 하나씩 매핑하는 테이블이 별도로
필요한 상황이 될 수도 있습니다.
이 부분은 좀 오해의 소지가 있을 것 같아요.. 1부터 9,000,000 까지의 정수에 대해 14 비트의 해시 키를 생성하는 것이 가능하다면(유일성을 강제하지만 않는다면 가능하겠죠..) 크기 16384의 배열에 9000 개의 결과들을 저장할 수 있습니다. 14비트는 2^13 = 8192 < 9000 < 2^14 = 16384 에서 비롯된 것이구요. 매핑 테이블이 필요하겠지만 하나씩 매핑하는 용도라기보다는 해시 충돌을 해소하기 위한 테이블일 것입니다...(9,000,000 대 16384이니 충돌 가능성은 상당히 클 것입니다).




Post Reply