교차로 오라클 설정

SIO(Set Intersection Oracle)는 집합의 집합을 나타내는 데이터 구조이며 지정된 두 집합의 집합 교차가 비어 있지 않은지 여부에 대한 쿼리에 신속하게 응답할 수 있습니다.

문제에 대한 입력은 유한 집합입니다.모든 집합의 크기의 합은 N(최대 N개의 개별 요소가 있음을 의미함)입니다.SIO는 다음과 같은 양식에 대한 모든 질문에 신속하게 답변해야 합니다.

"집합_i S가 집합_k S와 교차합니까?"

최소 메모리, 최대 쿼리 시간

사전 처리 없이 S의 요소를_i 임시 해시 테이블에 삽입한 다음 S의_k 각 요소가 해시 테이블에 있는지 확인하여 쿼리에 응답할 수 있습니다.쿼리 $O(|S_{i}|+|S_{j}|)=O(N)$ 은 O $O(|S_{i}|+|S_{j}|)=O(N)$ $O(|S_{i}|+|S_{j}|)=O(N)$ $O(|S_{i}|+|S_{j}|)=O(N)$ $O(|S_{i}|+|S_{j}|)=O(N)$ $=$ $)$ {\ $displaystyle$ O $(S_{i}$ + $S_{j}$ )= $O(N$ 입니다.

최대 메모리, 최소 쿼리 시간

또는 집합을 사전 처리하고 교차로 정보가 이미 입력된 n-by-n 테이블을 만들 수 있습니다.그러면 쿼리 시간은 O $)$ {{ $displaystyle$ O $(1$ $O(1)$ 이지만 필요한 메모리는 $O(n^{2})$ 2 $)$ { $n^{2$ 입니다.

타협안

큰 집합을 ${\sqrt {N}}$ N개 ${\sqrt {N}}$ 의 $\sqrt{N}$ 요소가 포함된 집합으로 정의합니다({ $displaystyle {sqrt {N}}).$ 분명히 ${\sqrt {N}}$ N개의 $디스플레이$ 스타일({ $sqrt {N}}$ 개)이 ${\sqrt {N}}$ 있습니다.모든 대형 집합과 다른 대형 집합 사이에 교차로 데이터 표를 만듭니다.여기에는 O $)$ {{ $displaystyle$ O( $N)}$ 메모리가 $O(N)$ $O(N)$ 합니다.또한 각 큰 집합에 대해 모든 요소의 해시 테이블을 유지합니다.이를 위해서는 $O(N^{3/2})$ O $O(N^{3/2})$ / 2 $O(N^{3/2})$ ) $O(N^{3/2})$ { $displaystyle$ O $(N^{3/2})$ 메모리가 $O(N^{3/2})$ 필요합니다.

두 집합이 주어지면 다음과 같은 세 가지 경우가 있을 수 있습니다.

두 세트 모두 큽니다.그런 다음 O $){displaystyle$ O( $1$ $O(1)$ 내에 교차로 쿼리에 대한 답을 표에서 읽으십시오.
두 세트 모두 작습니다.그런 다음 이들 중 하나의 요소를 해시 테이블에 삽입하고 다른 요소의 요소를 확인합니다. 세트가 작기 때문에 필요한 $O({\sqrt {N}})$ 은 O $){displaystyle$ O $({\sqrt {N$ 입니다.
한 세트는 크고 한 세트는 작습니다.작은 집합의 모든 요소를 루프하고 큰 집합의 해시 테이블과 비교하여 확인합니다.필요한 시간은 $O({\sqrt {N}})$ O $)$ {\ $displaystyle$ O $({\sqrt$ { $N$ 입니다.

일반적으로 "큰 집합"을 $N^{c}$ 적어도 $N^{c}$ 의 $N^{c}$ 의 요소가 있는 집합으로 정의하면 큰 집합의 수는 $N^{1-c}$ $N^{1-c}$ - $N^{1-c}$ { $1-c}$ 개이므로 $N^{1-c}$ 필요한 $O(N^{2-c})$ 는 O $O(N^{2-c})$ $O(N^{2-c})$ ) { $displaystyle$ O $(N$ $^{2-c$ 이고 쿼리 $O(N^{c})$ 은 O $)$ { $n^{c$ 입니다.

대략적인 거리 오라클로 감소

SIO 문제는 다음과 같은 ^[1]방법으로 대략적인 거리 오라클(DO) 문제로 줄일 수 있습니다.

한 부분에는 n개의 세트 각각에 대한 노드가 포함되어 있고 다른 부분에는 세트에 포함된 (최대) N개의 요소 각각에 대한 노드가 포함되어 있는 방향이 지정되지 않은 이분 그래프를 작성합니다.
집합에 요소가 포함된 경우 집합과 요소 사이에 가장자리가 있습니다.

이 그래프의 속성은 다음과 같습니다.

두 집합이 교차하는 경우 두 집합 사이의 거리는 2입니다(한 집합에서 교차점의 요소까지, 다른 집합까지).
두 집합이 교차하지 않으면 두 집합 사이의 거리는 4 이상입니다.

따라서 근사 계수가 2 미만인 DO로 SIO 문제를 해결할 수 있습니다.

SIO 문제는 사소한 해결책이 없는 것으로 여겨집니다.즉, 시간 $O(1)$ ( $1)$ \ $displaystyle$ O ( $1)$ 에서 쿼리에 응답하려면 $\Omega (n^{2})$ ( $)$ \ $Displaystyle$ \ $Omega (n^{2$ $O(1)$ 공간이 $\Omega (n^{2})$ 필요합니다. 이 추측이 사실이라면 근사 계수가 2 미만이고 쿼리 ^[1]시간이 일정한 DO가 없음을 의미합니다.

레퍼런스

^ ^a ^b Patrascu, M.; Roditty, L. (2010). Distance Oracles beyond the Thorup–Zwick Bound. 2010 IEEE 51st Annual Symposium on Foundations of Computer Science (FOCS). p. 815. doi:10.1109/FOCS.2010.83. ISBN 978-1-4244-8525-3.

[pr10-1] Patrascu, M.; Roditty, L. (2010). Distance Oracles beyond the Thorup–Zwick Bound. 2010 IEEE 51st Annual Symposium on Foundations of Computer Science (FOCS). p. 815. doi:10.1109/FOCS.2010.83. ISBN 978-1-4244-8525-3.

[1]

Search

교차로 오라클 설정

네임스페이스

더

목차

최소 메모리, 최대 쿼리 시간

최대 메모리, 최소 쿼리 시간

타협안

대략적인 거리 오라클로 감소

레퍼런스