셀프로브 모형

컴퓨터 과학에서 셀프로브 모델은 메모리 액세스를 제외한 모든 조작이 자유롭다는 점을 제외하고는 랜덤 액세스 기계와 유사한 연산 모델이다.이 모델은 데이터 구조 문제에 대한 알고리즘의 하한을 입증하는 데 유용하다.

개요

cell-probe 모델은 랜덤-액세스 머신 모델의 사소한 수정이며, 그 자체가 카운터 머신 모델의 사소한 수정이며, 계산 비용은 cell이라고 불리는 메모리의 단위에만 할당된다.

이 모델에서는, 연산이 일련의 메모리 셀을 쿼리하는 문제로서 틀이 잡힌다.문제는 사전 처리 단계와 쿼리 단계라는 두 가지 단계가 있다.첫 번째 단계인 사전 처리 단계에 대한 입력은 메모리 셀로부터 어떤 구조를 구축하기 위한 데이터 집합이다.두 번째 단계인 쿼리 단계에 대한 입력은 쿼리 기준점이다.문제는 조회 기준점이 원래 입력 데이터 세트에 포함됐는지를 파악하는 것이다.메모리 셀에 접근하는 것 외에는 운영이 무료다.

이 모델은 데이터 구조 분석에 유용하다.특히 모델은 우리가 약간의 쿼리를 실행하고자 하는 저장된 데이터가 있는 문제를 해결하기 위해 최소의 메모리 액세스 수를 명확하게 보여준다.그러한 문제의 예는 동적 부분 합계 문제다.^[1][2]

역사

앤드류 야오(Andrew Yao)의 1981년 논문 "테이블을 정렬해야 하는가?"^[3]에서 야오(Yao)는 셀프로브(cell-probe) 모델을 설명하여 메모리에 저장된 테이블 내에 주어진 쿼리 기준점이 존재하는지 판단하는 데 필요한 최소한의 메모리 셀 "프로브(probe)"를 주거나 액세스에 사용했다.

형식 정의

데이터 $S{\displaystyle }$ ${\displaystyle$ S$}$이(가) 주어진 경우 각각 $w{\displaystyle }$ ${\displaystyle w}$비트를$$ 저장할 수 있는 $c{\displaystyle }$ ${\displaystyle c}$ 메모리$$ 셀로 구성된 구조를 생성한다$$.그런$$ 다음 쿼리 $요소{\displaystyle }$ s ${\$$displaystyle s$$}$이(가) $주어졌을{\displaystyle }$ 때 t {\$displaystyle$ t$}$ 메모리$$ 셀에 액세스하여$$ $s{\displaystyle }$$1{\displaystyle \mathrm{}}$ S ${\displaystyle 1-\varepsilon }$ 정확도$$ 1 -${\displaystyle \epsilon }$$}$을(를) 가지는지 여부를 $결정$한다.이러한 알고리즘은 단어 크기가 $w{\displaystyle }${\$displaystyle w$}인 c$${\$displaystyle c}$ 셀을 $사용$하여 {$${\$displaystyle t}$$$-probe$$ 알고리즘이라고 한다$.$

주목할 만한 결과

동적 부분 합계

동적 부분 합계 문제는 두 가지 작업을 정의한다.개념적으로 연산하는 업데이트(k,v)는 인덱스 k에서 배열 A의 값을 v로 설정하고, 인덱스 0 ~ k에서 A의 값의 합을 반환하는 합계(k)를 설정한다.이러한 구현은 업데이트에 $O{\displaystyle }$( 1${\displaystyle }$) ${\displaystyle$ O$(1)}$시간$$, Sum에 $O{\displaystyle }$(${\displaystyle n}$) ${\displaystyle O(n)}$시간이$$ 소요될 것이다.^[5]

대신 값이 트리에 잎으로 저장되고 내부 노드가 해당 노드에 루트된 하위 트리의 값을 저장하는 경우.이 구조에서 업데이트는 리프에 있는 각 노드를 루트 경로로 업데이트하는 $데{\displaystyle }$ O${\displaystyle (\log }$ ${\displaystyle n}$) ${\displaystyle$ O$(\log$ n$)}$시간이$$ 필요하며, 마찬가지로 Summ은 트리들을 리프에서 쿼리 인덱스에 남아 있는 모든 하위 트리의 값을 루트로 이동시키는 데 $O{\displaystyle (\log }$ $){\displaystystystyle O(\log$ n$)$ 시간이$$ 필요하다.

Mihai Pătraşcu는 부분 합계 문제가 연산당 $\Omega {\displaystyle \mathrm{}(\log }$ ${\displaystyle n}$) ${\$번$$ 필요하다는 것을 보여주기 위해 셀프로브 모델과 정보 전송 인수를 사용했다.^[1][2]

근사치 가장 가까운 이웃 찾기

정확히 가장 가까운 이웃 검색 문제는 주어진 쿼리 포인트에 대한 입력 포인트 집합에서 가장 가까운 점을 결정하는 것이다.이 문제의 많은 적용이 매우 높은 차원 공간에 있고 높은 차원에서 문제를 해결하려면 차원에 관한 기하급수적인 시간이나 공간이 필요하기 때문에 이 문제의 대략적인 버전을 종종 고려한다.^[4]

Chakrabarti and Regev proved that the approximate nearest neighbor search problem on the Hamming cube using polynomial storage and ${\displaystyle d^{O(1)}}$ word size requires a worst-case query time of ${\displaystyle \Omega \left({\frac {\log \log d}{\log \log \log d}}\ri$$ght)}$.이 증거는 통신 복잡성을 위해 세포-프로브 모델과 정보 이론 기법을 사용했다.

외부 링크

• 셀프로브 모델에 대한 NIST의 알고리즘 및 데이터 구조 사전 항목

참조