블룸 필터의 반대?

블룸 필터의 반대?

---

기본적으로 수백만 개의 테스트를 실행하는 소프트웨어를 최적화하려고합니다. 이러한 테스트는 일부 반복이있을 수있는 방식으로 생성됩니다. 물론 효율적으로 피할 수 있다면 이미 실행 한 테스트를 실행하는 데 시간을 소비하고 싶지 않습니다.

그래서 이미 실행 된 테스트를 저장하기 위해 Bloom 필터를 사용할 생각입니다. 그러나 Bloom 필터는 안전하지 않은쪽에 오류가 있습니다. 오 탐지를 제공합니다. 즉, 내가하지 않은 테스트를 실행했다고보고 할 수 있습니다. 이것이 내가 작업중인 시나리오에서 수용 가능할 수 있지만, Bloom 필터와 동등한 것이 있는지 궁금했지만 반대편에서 잘못되었습니다. 즉, 거짓 부정 만 제공합니다.

나는 운없이 문헌을 훑어 보았다.

---

예, 손실이있는 해시 테이블 또는 LRUCache는 거짓 부정 만 제공하는 빠른 O (1) 조회가있는 데이터 구조입니다. "Have I run test X"인지 묻는 경우 "Yes, you sure 있다 "또는"기억할 수 없습니다 ".

매우 조잡한 의사 코드를 용서하십시오.

setup_test_table():
    create test_table( some large number of entries )
    clear each entry( test_table, NEVER )
    return test_table

has_test_been_run_before( new_test_details, test_table ):
    index = hash( test_details , test_table.length )
    old_details = test_table[index].detail
    // unconditionally overwrite old details with new details, LRU fashion.
    // perhaps some other collision resolution technique might be better.
    test_table[index].details = new_test_details
    if ( old_details === test_details ) return YES
    else if ( old_details === NEVER ) return NEVER
    else return PERHAPS    

main()
    test_table = setup_test_table();
    loop
        test_details = generate_random_test()
        status = has_test_been_run_before( test_details, test_table )
        case status of
           YES: do nothing;
           NEVER: run test (test_details);
           PERHAPS: if( rand()&1 ) run test (test_details);
    next loop
end.

---

이 작업을 수행하는 정확한 데이터 구조는 직접 매핑 된 캐시 이며 CPU에서 일반적으로 사용됩니다.

function set_member(set, item)
    set[hash(item) % set.length] = item

function is_member(set, item)
    return set[hash(item) % set.length] == item

---

실행 하지 않은 테스트를 저장할 수 있습니까? 이것은 필터의 동작을 역전시켜야합니다.

---

1. 위에서 언급 한대로 비트 세트를 사용하십시오. 당신이 아니오를 안다면. 사전에 실행할 테스트의 경우 데이터 구조에서 항상 올바른 결과 (존재 여부)를 얻을 수 있습니다.
2. 해싱 할 키를 알고 있습니까? 그렇다면 BloomFilter에서 키 분포를 확인하기 위해 실험을 실행해야합니다. 그래야 오 탐지를 재현하도록 미세 조정할 수 있습니다.
3. HyperLogLog도 확인할 수 있습니다.

---

아니요, 생각해 보면별로 유용하지 않을 것입니다. 귀하의 경우에는 항상 '거짓 음성'이 있으면 항상 실행해야 할 테스트가 있기 때문에 테스트 실행이 중지 될 것이라고 확신 할 수 없습니다.

나는 당신이 해시를 사용해야한다고 말할 것입니다.

---

LRUCache는 어떻습니까?

---

별로 도움이되지 않아서 미안합니다. 가능하지 않다고 생각합니다. 테스트 실행을 주문할 수없는 경우 압축 된 형식 (바이트 당 8 개 테스트!) 또는 결과를 메모리에 저장하기위한 좋은 희소 배열 라이브러리를 사용할 수 있습니다.

---

나는 당신이 해결책의 일부를 생략하고 있다고 생각합니다. 오탐을 완전히 피하려면 어떤 것이 실행되었는지 추적해야하며 기본적으로 블룸 필터를 바로 가기로 사용하여 테스트가 확실히 실행되지 않았는지 확인합니다.

즉, 테스트 수를 미리 알고 있으므로 잘 알려진 공식을 사용하여 허용 가능한 오류율을 제공하는 방식으로 필터의 크기를 조정할 수 있습니다. 1 % 확률로 오탐을 반환하려면 ~ 9.5 비트 / 엔트리가 필요하므로 1 백만 항목의 경우 1.2MB이면 충분합니다. 허용 가능한 오류율을 0.1 %로 줄이면 1.8MB로만 증가합니다.

Wikipedia 기사 Bloom Filters 는 훌륭한 분석과 관련된 수학에 대한 흥미로운 개요를 제공합니다.

---

The data structure you expect does not exist. Because such data structure must be a many-to-one mapping, or say, a limited state set. There must be at least two different inputs mapping to the same internal state. So you can't tell whether both (or more) of them are in the set, only knowing at least one of such input exists.

EDIT This statement is true only when you are looking for a memory efficient data structure. If memory is unlimited, you can always get a data structure to give 100% accurate results, by storing every member item.

ReferenceURL : https://stackoverflow.com/questions/635728/opposite-of-bloom-filter