PH 트리

PH 트리
PH 트리
유형	트리, 지도
발명된	2014
빅 O 표기의 시간 복잡도
알고리즘.
알고리즘.
공간
서치
삽입
삭제

PH-트리는^[1] 지리 좌표, 점, 특징 벡터, 직사각형 또는 경계 상자 등 다차원 데이터(키)의 공간 인덱싱에 사용되는 트리 데이터 구조입니다.PH 트리는 쿼드 트리 ^[3]또는 옥트리와 유사한 구조를 가진 공간 분할^[2] 인덱스입니다.단, 쿼드리와는 달리 시도 기반 분할 정책을 사용하며 키의 비트 표현을 기반으로 하는 Crit 비트 트리와 유사합니다.비트 기반 분할 정책은 노드에 대해 서로 다른 내부 표현을 사용할 때 고차원 데이터에 대한 확장성을 제공합니다.비트 표현 분할 정책도 최대 깊이를 요구하므로 트리 퇴화와 재조정 필요성을 ^[1]피할 수 있습니다.

개요

기본 PH 트리는 정수를 가진 d차원 벡터인 키를 사용자 정의 값에 매핑하는 공간 인덱스입니다.PH 트리는 Crit $비트트리$ 가 1차원 키를 $가진$ $PH$ 트리와 동등하다는 점에서 Crit 비트트리를 다차원적으로 일반화한 것입니다.Crit 비트 트리와 마찬가지로 다른 대부분의 공간 인덱스와 달리 PH 트리는 멀티맵이 ^[1]^[4]아닌 맵입니다.

d차원 PH-tree는 각 노드를 $(\$ 2 $^{d})$ 사분면으로 $2^{d}$ $2^{d}$ 하여 공간을 분할하는 노드의 트리입니다(아래 참조).각 사분면에는 키-값 쌍(리프 사분면) 또는 키-서브노드 쌍 중 하나의 항목이 포함됩니다.키와 서브노드 쌍의 경우 키는 서브노드의 중심을 나타냅니다.키는 서브노드와 그 자 서브노드의 모든 키의 공통 프리픽스(비트 표현)이기도 합니다.각 노드에는 적어도2개의 엔트리가 있습니다.그렇지 않으면 부모 ^[1]노드와 Marge 됩니다.

PH-Tree의 다른 구조적 특성은 다음과 같다.^[1]

$($ })-나무입니다 $2^{n}$ .
이러한 키는 본질적으로 불균형하지만 깊이가 키의 비트 폭(예를 들어 32비트 정수의 $\displaystyle$ d $)$ 으로 $d$ 제한되기 때문에 불균형이 제한됩니다.
삽입 또는 삭제 조작에 의해 정확히1개의 노드가 변경되어 두 번째 노드가 추가 또는 삭제될 가능성이 있습니다.이는 동시 구현에 유용합니다.이는 또한 수정 비용의 변동이 거의 없음을 의미합니다.
이들 구조는 삽입/제거 순서와는 무관합니다.

분할 전략

대부분의 쿼드리와 마찬가지로 PH 트리는 모든 노드가 $모든$ ^[1]d차원으로 공간을 분할하는 노드의 계층입니다.따라서 노드에는 최대 $2^{d}$ 의 $2^{d}$ d(\ $displaystyle$ 2 $^{d})$ 의 $2^{d}$ 서브노드를 사용할 수 있습니다(각 사분면에 1개).

비트 문자열을 사용한 하이퍼큐브 어드레싱

사분면 번호부여부

PH 트리는 다차원 키의 비트를 사용하여 트리에서 해당 비트의 위치를 결정합니다.선두 비트가 같은 키는 모두 ^[1]트리의 같은 분기에 저장됩니다.

예를 들어 $레벨$ L의 노드에서는 키를 삽입(또는 삭제 또는 조회)할 필요가 있는 쿼드런트를 결정하기 위해 키의 각 치수의 L $비트$ 를 조사합니다.8개의 사분면이 있는 3D 노드의 경우(입방체를 형성함) 키의 첫 번째 차원 L의 $비트$ 는 큐브의 왼쪽 또는 오른쪽에 있는지, 두 번째 $차원$ 의 L의 비트는 큐브의 앞 또는 뒤에 있는지, 세 $번째$ 차원의 L의 비트는 아래 vs 위를 결정합니다.

3개의 키가 추가된 PH 트리의 예이며, 그 결과 2개의 노드가 생성됩니다.루트 노드(빨간색)와 서브 노드(파란색)입니다.

1D 예시

8비트 값을 가진 3개의 1D 키가 있는 예: $k_{0}=\{1\}_{base\ 10}=\{00000001\}_{base\ 2}$ $k_{0}=\{1\}_{base\ 10}=\{00000001\}_{base\ 2}$ $k_{0}=\{1\}_{base\ 10}=\{00000001\}_{base\ 2}$ { $k_{0}=\{1\}_{base\ 10}=\{00000001\}_{base\ 2}$ $k_{0}=\{1\}_{base\ 10}=\{00000001\}_{base\ 2}$ $k_{0}=\{1\}_{base\ 10}=\{00000001\}_{base\ 2}$ $k_{0}=\{1\}_{base\ 10}=\{00000001\}_{base\ 2}$ $k_{0}=\{1\}_{base\ 10}=\{00000001\}_{base\ 2}$ 10 $k_{0}=\{1\}_{base\ 10}=\{00000001\}_{base\ 2}$ { $00000001$ } $k_{0}=\{1\}_{base\ 10}=\{00000001\}_{base\ 2}$ $k_{0}=\{1\}_{base\ 10}=\{00000001\}_{base\ 2}$ { $display$ $k$ _ { 0 } $k_{0}=\{1\}_{base\ 10}=\{00000001\}_{base\ 2}$ = \ { $1$ \ } $_ {$ base \ 2 $k_{1}=\{1\}_{10}=\{00000100\}_{2}$ } , $k_{1}=\{1\}_{10}=\{00000100\}_{2}$ $k_{1}=\{1\}_{10}=\{00000100\}_{2}$ 1 = $k_{1}=\{1\}_{10}=\{00000100\}_{2}$ $k_{1}=\{1\}_{10}=\{00000100\}_{2}$ 10 $k_{1}=\{1\}_{10}=\{00000100\}_{2}$ $_$ { $k_{1}=\{1\}_{10}=\{00000100\}_{2}$ $100$ $k_{1}=\{1\}_{10}=\{00000100\}_{2}$ $kstyle$ $e k_{2}=$ \{ $35\}_{10$ }=\{ $00100011\}_{2$ k $k_{0}$ (\ $k_{1}$ k_{ $0}) 및$ k $k_{0}$ $(\$ {1 $})을$ 빈 트리에 추가하면 $k_{0}$ 노드가 됩니다.두 키는 먼저 6번째 비트에서 다르므로 노드의 $L=5$ 은 L $L=5$ ({ $디스플레이 스타일$ L $=5}($ 0부터 시작))입니다.노드에는 양쪽 키의 공통 5비트를 나타내는5비트 프리픽스가 있습니다.노드에는 2개의 사분면이 있으며 각 키는 1개의 사분면에 저장됩니다.세 번째 $k_{3}$ $({$ 를 $k_{3}$ 추가하면 L $L=2$ ({ $displaystyle$ L $=2})$ 에서 $L=2$ 노드 하나가 추가되며, 하나는 원래 노드를 서브노드로 포함하고 다른 하나는 새 키 $({$ ^{[citation needed]}를 포함합니다.

1개의 노드에 2개의 2D 키가 있는 PH 트리의 예

2D 예시

2D 키를 사용하는 경우 모든 $2^{d}=4$ 에는 $=$ 4{디스플레이 $2^{d}=4$ $스타일$ 2^{d}=4 $}개$ 의 사분면이 $있습니다.$ 키가 저장되는 사분면의 위치는 키의 각 비트에서, 각 치수에서 1비트를 추출합니다.노드의 4개 사분면은 2D 하이퍼 큐브를 형성합니다(사분면은 비어 있을 수 있습니다).키에서 추출된 비트는 hypercube $주소$ h(k 0= h { 00 $h$ $k_{0}\rightarrow h=\{00\}_{2}$ $k_{0}\rightarrow h=\{00\}_{2}$ { $displaystyle$ k $_$ { $0$ \ $rightarrow$ h $=$ \ { $00$ $k_{0}\rightarrow h=\{00\}_{2}$ \ } $_ {2$ } 및 $k_{0}\rightarrow h=\{00\}_{2}$ $k_{1}\rightarrow h=\{01\}_{2}$ $k_{1}\rightarrow h=\{01\}_{2}$ { $k_{1}\rightarrow h=\{01\}_{2}$ $k_{1}\rightarrow h=\{01\}_{2}$ \ $displaystyle h =$ { $01$ \ 01 \ displaystyle h } { \ 01 } ) { \ { \ $display style$ h $k_{1}\rightarrow h=\{01\}_{2}$ } h } { \ 02 $k_{1}\rightarrow h=\{01\}_{2}$ { \ tyle h } { display $style$ h } { display h} {노드의 ^{[citation needed]}하이퍼큐브입니다

노드 구조

노드의 엔트리의 순서는 항상 Z 순서 뒤에 있습니다.예를 들어 노드의 엔트리는 크기가 $2^{d}$ 인 $2^{d}$ 크기 $2^{d}$ 배열에 저장할 수 있습니다 $2^{d}$ $h$ 는 실질적으로 쿼드런트의 $배열$ 인덱스가 됩니다.따라서 O $)$ { $displaystyle$ O( $1)}$ 를 $O(1)$ $O(1)$ 하여 조회, 삽입 및 제거할 수 있으며 h를 $저장$ 할 필요가 없습니다. 공간 복잡도는 노드당 $O(2^{d})$ O( $O(2^{d})$ $)$ { $displaystyle$ O( $2^{d})}$ 이므로 $O(2^d)$ 고차원 ^[1]데이터에는 적합하지 않습니다.

또 다른 솔루션은 동적 배열 및/또는 B-트리와 같은 정렬된 컬렉션에 엔트리를 저장하는 것입니다.이것에 의해, O $O(\log {n_{node\_entries}})$ 「 $O(\log {n_{node\_entries}})$ $o$ $O(\log {n_{node\_entries}})$ e _ $O(\log {n_{node\_entries}})$ $O(\log {n_{node\_entries}})$ t $O(\log {n_{node\_entries}})$ $O(\log {n_{node\_entries}})$ $O(\log {n_{node\_entries}})$ ）（ \ $O(n_{node\_entries})$ $style$ O （ \ $log$ { n _ $n$ _ node \ _ $entries$ $O(\log {n_{node\_entries}})$ } ） $O(\log {n_{node\_entries}})$ o oper oper oper oper oper oper oper oper oper oper this this this this this this this （ n $O(n_{node\_entries})$ d e _ $O(n_{node\_entries})$ n $O(n_{node\_entries})$ $O(n_{node\_entries})$ $O(n_{node\_entries})$ $O(n_{node\_entries})$ $O(n_{node\_entries})$ s $O(n_{node\_entries})$ ^[1] $ostylestylestylestyle$ o o o o o o o o o o o o o o o o o o o o o o o o o $)$ 로 메모리 소비량이 $감소$ 합니다.

최초의 실장에서는,^[1] 어느 쪽이 메모리를 적게 사용하는지에 따라, 고정 어레이 표시와 동적 어레이 표시로 전환해, 메모리 소비를 최소한으로 억제하는 것을 목적으로 하고 있었습니다.기타 실장 [1][2]에서는 $동적$ 으로 전환되지 않지만 d use $d\lesssim 4$ 의 $경우$ 고정 $어레이$ d $d\lesssim 8$ 동적 $어레이$ 및 고차원 데이터의 경우 $B-tree$ 를 사용합니다.

운용

룩업, 삽입 및 삭제 조작은 모두 매우 비슷하게 동작합니다.올바른 노드를 찾아 해당 노드에서 조작을 수행합니다.윈도우 쿼리와 k-neighbor 검색은 더 복잡합니다.

찾다

조회 작업은 트리에 키가 있는지 여부를 확인합니다.트리를 내려가서 후보 서브노드 또는 ^[1]키에 일치하는 사용자 값이 포함되어 있는지 모든 노드를 체크합니다.

function lookup(key)은 entry = get_root_entry() // 트리가 비어 있지 않은 경우 루트 엔트리에 루트 노드가 포함되어 있습니다.한편 do node ← entry ← node.get_node(key) repeat return ent entry // 엔트리는 NIL일 수 있습니다.

함수 get_entry(key)는 노드 ← 현재 노드 h ← extract_bits_at_depth(key, node.get_depth() entry ← node.get_entry_at(h) return entry // 엔트리는 NIL일 수 있습니다.

삽입

키가 아직 존재하지 않는 한 삽입 작업은 새 키와 값 쌍을 트리에 삽입합니다.이 조작은 Lookup 함수처럼 트리를 통과하여 노드에 키를 삽입합니다.고려해야 ^[1]할 몇 가지 사례가 있습니다.

쿼드런트가 비어 있으므로 쿼드런트에 새 엔트리를 삽입하고 반환하기만 하면 됩니다.
쿼드런트에는 새 엔트리와 동일한 키를 가진 사용자 엔트리가 포함됩니다.이러한 충돌에 대처하는 방법 중 하나는 삽입에 실패했음을 나타내는 플래그를 반환하는 것입니다.트리가 노드의 엔트리로 컬렉션을 포함하는 멀티맵으로 구현될 경우 새 값이 해당 컬렉션에 추가됩니다.
쿼드런트에 다른 키를 가진 엔트리(사용자 엔트리 또는 서브노드 엔트리)가 포함됩니다.이 경우 기존 엔트리를 오래된 엔트리와 새로운 엔트리를 유지하는 새로운 서브노드로 교체해야 합니다.

함수 insert(노드, 키, 값) ← node.get_level() // root h ← extract_bits_at_level(키, 수준) ← node.get_entry(h) ← node == NIL 그 다음 // entry_new ← create_entry(키, 값) 노드의 경우 레벨이 0입니다.set_entry(h, entry_new) 그렇지 않으면 !entry.is_subnode() & & entry.get_key() == 키를 누른 후 // 케이스 2를 누릅니다.충돌, 이미 항목 반환 ← failed_diff else // case 3. level_diff ← get_level_of_relence(key, entry). entry_new ← 기존 엔트리와 새 엔트리가 있는 새 서브노드 ← create_node(level_diff, entry)node.set_entry(h, subnode_new)가 반환되면 종료됩니다.

제거한다.

삭제는 삽입과 반대로 동작하며, 엔트리가 2개 미만인 경우 서브노드를 삭제해야 한다는 추가 제약이 있습니다.나머지 엔트리는 부모 ^[1]노드로 이동합니다.

윈도 쿼리

Windows 쿼리는 직사각형 축으로 정렬된 하이퍼박스 내에 있는 모든 키를 반환하는 쿼리입니다.쿼리 상자의 "왼쪽 하단" 및 "오른쪽 상단" 모서리를 나타내는 2개의 d차원 $포인트$ $(디스플레이 스타일$ 최소 $)$ $max$ m $(디스플레이 스타일$ 최대 $)$ 로 $max$ 정의할 수 있습니다.간단한 실장은 노드 내의 모든 엔트리를 통과합니다(루트노드부터 시작). 엔트리가 일치하면 결과 목록에 추가하거나(사용자 엔트리인 경우), 재귀적으로 통과합니다(서브노드인 ^[1]경우).

기능 cm는foreach 진입 ← node.get_entries()더라도 entry.is_subnode()다면 entry.get_prefix()>)분, entry.get_prefix()<>)max 다음 query(entry.get_subnode(),분, max, result_list) 끝나면 다른 만약 entry.get_key()>)분, entry.get_key()<>)max.               result_list.add(엔트리) end if end if repeat return if

$n_{node\_entries}$ 시간의 복잡성을 정확하게 추정하기 위해 분석에는 치수 $\$ $n_{node\_entries}$ d $\$ $n_{node\_entries}$ d $d$ $displaystyle$ $d\$ $n_{node\_entries}$ ${node\$ $entries}$ $n_{node\_entries}$ 를 $n_{node\_entries}$ 트래버스 및 비교할 필요가 있습니다 $노드$ 의 $O(d*n_{node\_entries})$ $O(d*n_{node\_entries})$ 는 $(displaystyle$ d $)$ 입니다 $.$ entries $}}$ 은 $O(d*n_{node\_entries})$ d $(displaystyle$ d $O(d)$ 차원 $d$ 키를 $min/max$ n/ $min/max$ 과 $min/max$ 할 $min/max$ 마다 $min/max$ ( $displaystyle$ min $/max)$ $O(d)$ 이 $O(d)$ 소요되기 $때문$ 입니다 $min/max$ $.$ 노드에는 $2^{d}$ $2^{d}$ 의 d $\$ 2 $^{d$ $d$ 개의 $2^{d}$ 엔트리를 포함할 수 있으므로 $dimensionality의 증가$ 에 따라 적절히 확장되지 않습니다 $.$ 하이퍼큐브 $주소$ ^[4]h를 사용함으로써 이 접근 방식을 개선할 수 있는 방법은 다양합니다.

$최소$ 시간 및 $최대$ 시간

쿼드런트의 주소 $h$ 의 최소값과 $최대값을 검색$ 하여 $h$ 쿼드런트가 쿼리 박스와 겹치지 않도록 합니다 $.$ C $({displaystyle$ C $})$ 를 $C$ 노드의 중심(노드의 프리픽스와 동일)으로 $h_{min}$ $h_{min}$ n({ $displaystyle h_{$ $h_{max}$ })과 $h_{max}$ m a x $({$ 를 $h_{max}$ 각각 d ${displaystyle$ d $}$ 의 $d$ 2비트 문자열로 $합니다$ .또한, 첨자 ii< 0≤과{\displaystyle 나는}, d{\displaystyle 0\leq i<, d}ih의{\displaystyle 나는}좀 나는}과 h m x{\displaystyle h_{맥스}}이고, mi{\displaystyle 나는}'th 차원{\displaystyle분}의{\displaystyle h_{분}의 스녀 m, m x{\disp을 나타낸다.layst $yle$ max $와$ C {\ $displaystyle$ C $C$ 입니다 $max$ .

$h_{min,i}=(min_{i}\leq C_{i})$ $h_{min,i}=(min_{i}\leq C_{i})$ n $h_{min,i}=(min_{i}\leq C_{i})$ $h_{min,i}=(min_{i}\leq C_{i})$ $h_{min,i}=(min_{i}\leq C_{i})$ ( $h_{min,i}=(min_{i}\leq C_{i})$ n $h_{min,i}=(min_{i}\leq C_{i})$ ) ( $h_{min,i}=(min_{i}\leq C_{i})$ { $displaystyle$ h _ { $min , i$ } = ( $min$ _ { $i$ $h_{max,i}=(max_{i}\geq C_{i})$ \ $leq$ C _ { $i$ } ) $h_{max,i}=(max_{i}\geq C_{i})$ h $h_{max,i}=(max_{i}\geq C_{i})$ $h_{max,i}=(max_{i}\geq C_{i})$ a $h_{max,i}=(max_{i}\geq C_{i})$ , $h_{max,i}=(max_{i}\geq C_{i})$ $h_{max,i}=(max_{i}\geq C_{i})$ ( $max$ $h_{max,i}=(max_{i}\geq C_{i})$ i = $h_{max,i}=(max_{i}\geq C_{i})$ $)$ ( $misplay$ style h $h_{min}$ $h_{max,i}=(max_{i}\geq C_{i})$ { $max$ , i } \ = ( $max _$ i } \ ）（ max _ i ）\ ） $h_{min}$ c c c m $C_{$ $h_{min}$ ） $h_{max,i}=(max_{i}\geq C_{i})$ ）。ll 사분원이 쿼리 상자와 겹치지 않습니다.마찬가지로 h $h_{min}$ n $h_{min}$ { $displaystyle$ h $_$ { $min$ } $h_{min}$ 、「 """ does does does does does 」의 반쪽이 쿼리 박스와 겹치지 않는 모든 치수에 $대해0$ { $displaystyle$ 0 $0$ }이 표시됩니다.

$h_{min}$ 으로 h $h_{min}$ (\ $displaystyle h_{$ min $h_{min}$ }) $h_{max}$ $h_{max}$ m $h_{max}$ $h_{max}$ $(\displaystyle$ $h_$ ${$ $max})$ 를 $h_{max}$ $h$ 합니다 $h$ . $h<h_{min}$ < $h<h_{min}$ $h<h_{min}$ $h<h_{min}$ $\$ $display style$ h < h $_$ { $min$ } $h>h_{max}$ > $h>h_{max}$ > $h>h_{max}$ { $display h >h_{$ max} 의 $h>h_{max}$ 사분원은 쿼리 박스와 교차하지 않습니다.증명은 ^[4]다음에서 입수할 수 있습니다.이를 통해 위의 쿼리 기능을 다음과 같이 개선할 수 있습니다.

함수 쿼리(node, min, max, result_list)는 h_min ← 계산h_min h_max ← 각 엔트리에 대해 계산h_max ← 계산h_max ← node.get_min_range(h_min, h_max) do [...] 반복 반환

$h_{max}$ $h_{min}$ n $h_{min}$ (\ $displaystyle h_{min$ $h_{max}$ h $h_{max}$ $h_{max}$ x $h_{max}$ (\ $displaystyle h_{max})$ 의 $h_{max}$ $h_{min}$ 은 $O(2*d)=O(d)$ O ( $O(2*d)=O(d)$ $=$ ( $)$ (\ $displaystyle$ O ( $2*d$ )=O $(d$ 입니다.이 접근방식은 노드 내에서 점유된 사분면의 분포에 따라 거의 모든 키 비교를 피할 수 있습니다.이렇게 하면 평균 트래버설 시간이 단축되지만 복잡도는 $O(d+d*n_{node\_entries})$ + d $O(d+d*n_{node\_entries})$ $O(d+d*n_{node\_entries})$ $O(d+d*n_{node\_entries})$ d $O(d+d*n_{node\_entries})$ $O(d+d*n_{node\_entries})$ $O(d+d*n_{node\_entries})$ $O(d+d*n_{node\_entries})$ $O(d+d*n_{node\_entries})$ $O(d+d*n_{node\_entries})$ $O(d+d*n_{node\_entries})$ $)(displaystyle$ O $(d+d*n_{node\_entries$ ^[4]가 됩니다.

쿼드런트가 쿼리 상자와 겹치는지 확인합니다.

$h_{min}$ $h_{min}$ n $h_{min}$ ({ $displaystyle h_{min}}$ ~ $h_{max}$ m $h_{max}$ ({ $displaystyle h_{max})$ $h_{min}$ 에는 $h_{max}$ 쿼리 박스와 겹치지 않는 사분면이 존재할 수 있습니다.Idea: $h_{min}$ and $h_{max}$ each have one bit for every dimensions that indicates whether the query box overlaps with the lower/upper half of a node in that dimension.이 기능을 사용하여 $쿼드런트h와 쿼드런트h$ 의 $h$ 중복 여부를 빠르게 확인할 수 있습니다 $.$ 차원 $d$ 키를 $d$ 할 필요가 없습니다. $h$ 는쿼드런트h와 중복됩니다.예를 들어 $h$ 의 각 $0$ 에 대응하는 값이 0 $({$ $displaystyle$ 0 $0$ 일 $h$ $h$ 경우 쿼드런트h와 중복됩니다. $h_{min}$ $(\displaystyle$ 0 $0$ 비트 $h_{min}$ $h_{min}$ h $h_{min}$ n(\ $displaystyle h_{min})$ 및 h $(\displaystyle$ h $)$ 비트에 $h$ $h$ 하는 $1$ (\ $displaystyle$ 1) $1$ 비트가 $h_{max}$ x(\ $displaystyle h_{max$ 에 있습니다.따라서 64비트 레지스터를 가진 CPU에서는 오버랩을 체크할 수 있습니다. $({displaystyle$ 64 $})$ 치수 $64$ 키 $O(1)$ $O(1)$ ) $O(1)$ { $displaystyle$ O( $1$ ^[4]

함수 is_subrant(h, h_min, h_max)는 반환(h h_min) & h_max == h // 사분면과 쿼리가 겹치면 'true'로 평가됩니다.

함수 쿼리(node, min, max, result_list)는 h_min ← calculate h_min h_max ← calculate h_max ← calculate h_max ← node.get_max (h_min, h_max) do h ← entry.get_h() 입니다. (h)의 경우 쿼리와 오버랩이 반환되는 경우 true로 평가됩니다.

그 결과 시간의 $O(d*n_{node\_entries})$ 은 O $O(d*n_{node\_entries})$ + $O(d+n_{node\_entries})$ $O(d*n_{node\_entries})$ $O(d+n_{node\_entries})$ e $O(d+n_{node\_entries})$ $O(d+n_{node\_entries})$ n t $O(d+n_{node\_entries})$ $O(d+n_{node\_entries})$ $)(displaystyle$ O $(d+n_{node\entries})$ 와 $O(d+n_{node\_entries})$ 전체 ^[4]반복의 O $O(d*n_{node\_entries})$ d style $O(d*n_{node\_entries})$ $O(d*n_{node\_entries})$ $O(d*n_{node\_entries})$ _ $O(d*n_{node\_entries})$ $O(d*n_{node\_entries})$ $O(d*n_{node\_entries})$ $O(d*n_{node\_entries})$ s $)(displaystyle$ O $(d*n_{node\entries}))$ 와 $O(d*n_{node\_entries})$ $O(d+n_{node\_entries})$ 됩니다.

쿼리 상자와 겹치는 사분원 이동

노드가 큰 고차원의 경우 모든 $(표시 스타일$ h $)$ 에서 $h$ 반복되지 않고 쿼리 상자와 겹치는 다음 $(표시 스타일$ h $)$ 를 $h$ 직접 계산할 수도 있습니다.첫 번째 단계에서는 쿼리 박스와 겹치지 않는 모든 사분면에 $대해$ $h_{input}$ $({displaystyle$ 1}) $1$ 비트를 지정된 $h_{input}$ n $h_{input}$ t({ $displaystyle h_{input$ })에 $h_{input}$ 넣습니다.두 번째 단계는 $h$ 된 $h$ 와 $h$ 추가된 $($ 1) 비트를 증가시켜 오버랩되지 않는 사분원을 건너뛸 수 있도록 오버플로를 트리거합니다.마지막 단계에서는 오버플로우 트리거에 사용되는 모든 바람직하지 않은 비트를 제거합니다.로직은 ^[4]에 자세히 설명되어 있습니다.계산은 다음과 같이 이루어집니다.

함수 increment_h(h_input, h_min, h_max)는 h_out = h_input (~h_max ) // pre - mask h_out + = 1 // increment h_out = ( h_out & h_max ) // post - mask returnut h_out

d $d\leq 64$ 64 $d\leq 64$ { $displaystyle$ d $\leq$ 64 $d\leq 64$ }의 $d\leq 64$ 경우 O $O(1)$ ( $O(1)$ ) $O(1)$ { $displaystyle$ O (1 $)$ 의 대부분의 CPU에서 이 작업을 수행할 수 있습니다.노드를 통과하는 시간의 복잡도는 O $O(d+n_{overlapping\_quadrants})$ $O(d+n_{overlapping\_quadrants})$ + $O(d+n_{overlapping\_quadrants})$ $O(d+n_{overlapping\_quadrants})$ e $O(d+n_{overlapping\_quadrants})$ $O(d+n_{overlapping\_quadrants})$ $O(d+n_{overlapping\_quadrants})$ $O(d+n_{overlapping\_quadrants})$ $O(d+n_{overlapping\_quadrants})$ $O(d+n_{overlapping\_quadrants})$ $O(d+n_{overlapping\_quadrants})$ $O(d+n_{overlapping\_quadrants})$ $O(d+n_{overlapping\_quadrants})$ $O(d+n_{overlapping\_quadrants})$ a $O(d+n_{overlapping\_quadrants})$ $O(d+n_{overlapping\_quadrants})$ s $){$ $displaystyle$ O $(d+n_{overlaping\_quadants$ ^[4]입니다.쿼리 상자와 겹치는 사분면의 대부분이 엔트리에 점유되어 있는 경우에 가장 적합합니다.

k-param 네이버

k 가장 가까운 네이버 검색은 표준 ^[5]알고리즘을 사용하여 구현할 수 있다.

부동 소수점 키

PH 트리는 정수 값만 저장할 수 있습니다.부동소수점 값은 정수로 저장할 수 있습니다.그러나 의 저자들은 정밀도 ^[1]^[4]손실 없이 접근법도 제안한다.

무손실 전환

부동소수점 값의 32비트 또는 64비트를 단순히 정수(32비트 또는 64비트)로 해석함으로써 정밀도를 달성할 수 있는 경우 부동소수점 값을 무손실(및 백)으로 변환합니다.IEEE 754가 부동소수점 값을 인코딩하는 방식에 따라 적어도 양의 값에 대해 결과 정수 값은 원래의 부동소수점 값과 동일한 순서를 가집니다.비부호 ^[1]^[4]비트를 반전시킴으로써 음수 값의 순서를 설정할 수 있습니다.

Java에서의 구현 예:

long encode(이중값) { long r = Double.ToRawLongBits(값); return (r > = 0) ?r : r ^ 0x7FFFFFFFFFF; }

C++에서의 실장 예:

std::int64_t encode(이중값) { std::int64_t r; memcpy(&r, &value, sizeof(r)), r >= 0 ?r : r ^ 0x7FFFFFFFF;}를 반환합니다.

부호화(및 역디코딩)는 모든 부동소수점 값에 대해 무손실입니다.이 순서는 ± ${\(\displaystyle \pm$ \infty $)$ $-0.0$ 및 $\pm \infty$ $.$ 0(\ $displaystyle$ $-0.0$ $\pm \infty$ 등 실제로는 잘 작동하지만 정수 표현은 $N$ 을 N $(\displaystyle$ NaN $)$ 으로 $NaN$ $NaN$ 하고 무한대는 서로 비교 가능하며 $(\displaystyle$ -0.0 $)$ 은 $0.0$ 더 큽니다. $-0.0$ 0. $(\displaystyle -0.$ 0 $-0.0$ ^[6]보다 작습니다.즉, 예를 들어 쿼리 $[0.0,10.0]$ 범위 [ $[0.0,10.0]$ $-0.0$ 0 $,$ $]({$ $displaystyle$ $[$ 0 $.0, 10.$ 0 $[0.0,10.0]$ ])는 -0.0 $({$ $displaystyle -0.$ 0 $-0.0$ 의 $-0.0$ 과 일치하지 않습니다 $.$ ({ $displaystyle -0.0$ $})$ 을 $-0.0$ $-0.0$ 일치시키려면 쿼리 범위가 $[-0.0,10.0]$ [- $[-0.0,10.0]$ 0, $10.$ 0 $[-0.0,10.0]$ ^{[citation needed]}이어야 합니다.

하이퍼박스 키

로 건반, 구현 일반적으로-dimensional 최소 점 수 및 상자의 최대의 모서리{\displaystyle d}2∗ d와 치수{2*d\displaystyle}예를 들어 단일 키로 끼워 넣기로써 두 d로 변환합니다 코너 representation[7]을 사용하기 위해 저장하기 위해 볼륨:k={m나의 0,인데 m(axis-aligned hyper-boxes)0 $k=\{min_{0},max_{0},min_{1},max_{1},...,min_{d-1},max_{d-1}\}$ $k=\{min_{0},max_{0},min_{1},max_{1},...,min_{d-1},max_{d-1}\}$ $k=\{min_{0},max_{0},min_{1},max_{1},...,min_{d-1},max_{d-1}\}$ $k=\{min_{0},max_{0},min_{1},max_{1},...,min_{d-1},max_{d-1}\}$ , $k=\{min_{0},max_{0},min_{1},max_{1},...,min_{d-1},max_{d-1}\}$ $k=\{min_{0},max_{0},min_{1},max_{1},...,min_{d-1},max_{d-1}\}$ x $k=\{min_{0},max_{0},min_{1},max_{1},...,min_{d-1},max_{d-1}\}$ 1 , $k=\{min_{0},max_{0},min_{1},max_{1},...,min_{d-1},max_{d-1}\}$ . $k=\{min_{0},max_{0},min_{1},max_{1},...,min_{d-1},max_{d-1}\}$ , m $k=\{min_{0},max_{0},min_{1},max_{1},...,min_{d-1},max_{d-1}\}$ n $k=\{min_{0},max_{0},min_{1},max_{1},...,min_{d-1},max_{d-1}\}$ - $k=\{min_{0},max_{0},min_{1},max_{1},...,min_{d-1},max_{d-1}\}$ , $k=\{min_{0},max_{0},min_{1},max_{1},...,min_{d-1},max_{d-1}\}$ $k=\{min_{0},max_{0},min_{1},max_{1},...,min_{d-1},max_{d-1}\}$ $k=\{min_{0},max_{0},min_{1},max_{1},...,min_{d-1},max_{d-1}\}$ $k=\{min_{0},max_{0},min_{1},max_{1},...,min_{d-1},max_{d-1}\}$ - $1$ } $k=\{min_{0},max_{0},min_{1},max_{1},...,min_{d-1},max_{d-1}\}$ displaystyle k $k=\{min_{0},max_{0},min_{1},max_{1},...,min_{d-1},max_{d-1}\}$ = \ { $min _$ { $0 }$ , $max$ _ { 1 } $, max$ _ { { $1$ } , $max$ _ { d $k=\{min_{0},max_{0},min_{1},max_{1},...,min_{d-1},max_{d-1}\}$ - 1 $}$ ) 。

이것은 조회, 삽입 및 제거 작업에 대해 세 가지 방법으로 작동합니다.윈도우 쿼리는 d $\displaystyle$ d-dimensional $d$ $d$ 에서 2 $d_displaystyle 2*$ d_-dimensional $2*d$ $2*d$ 로 변환해야 합니다.예를 들어 조회 상자 안에 완전히 있는 모든 상자에 일치하는 창 조회의 경우 조회 키는 다음과 같습니다.^[7]^[8]

$k_{min}=\{0},min_{0},min_{1},min_{1},...,min_{d-1},min_{d-1}\$

$({displaystyle k_{max}=\{0},max_{0},max_{1},max_{1},...,max_{d-1},max_{d-1}\})$

쿼리 상자와 교차하는 모든 상자에 일치하는 창 쿼리 작업의 경우 쿼리 키는 다음과 같습니다.^[8]

$\displaystyle k_{min}=\{-\infty,min_{0},-\infty,min_{1},...,\infty,min_{d-1}\}$

$\displaystyle k_{max}=\{0},+\infty,max_{1},+\infty,...,max_{d-1},+\infty \}$

확장성

엔트리가 $2^{d}$ 인 $2^{d}$ 고차원에서는 PH 트리에 노드가1개밖에 없어 사실상 Z차 곡선의 B-Tree로 '전락 $'$ 할 수 있습니다.추가/삭제/조회 조작은 O $)$ 인 $O(\log {n})$ 로(\ $displaystyle O(\log$ { $n})$ 윈도우 $O(\log {n})$ 쿼리는 쿼드런트필터를 사용할 수 있습니다.그러나 d $d=50$ $d=50$ ${displaystyle$ d $=50}$ $d=100$ d $d=100$ $d=100$ { $displaystyle$ d $=100}$ 인 $d=100$ 고차원 데이터의 경우 PH 트리가 전체 ^[9]스캔보다 약간만 우수합니다.

사용하다

연구 결과,^[10] 크고 빠르게 변화하는 데이터셋에 대한 빠른 추가/제거/정확한 일치 작업이 보고되었습니다.창 쿼리는 특히 작은^[11] 창 또는 큰 데이터^[12] 세트에 잘 작동하는 것으로 나타났습니다.

PH 트리는 주로 메모리 내 ^[10]^[13]^[14]사용에 적합합니다.노드의 크기(엔트리 수)는 고정되어 있지만 영속적인 스토리지는 구성 가능한 노드 크기를 가진 인덱스의 이점을 활용하여 노드의 크기를 디스크의 페이지 크기에 맞추는 경향이 있습니다.이것은 R-Tree와 같은 다른 공간 인덱스를 사용하면 더 쉽습니다.

실장

「」를 참조해 주세요.

레퍼런스

^ ^a ^b ^c ^d ^e ^f ^g ^h ⁱ ^j ^k ^l ^m ⁿ ^o ^p Zäschke, Tilmann; Zimmerli, Christoph; Norrie, Moira C. (June 2014). "The PH-tree: a space-efficient storage structure and multi-dimensional index". Proc. 2014 ACM SIGMOD International Conference on Management of Data: 397–408. doi:10.1145/2588555.2588564. ISBN 9781450323765. S2CID 6862850. Retrieved 10 February 2022.
^ Kouahla, Z.; Benrazek, A.-E.; Ferrag, M. A.; Farou, B.; Seridi, H.; Kurulay, M.; Anjum, A.; Asheralieva, A. (2022). "Survey on Big IoT Data Indexing: Potential Solutions, Recent Advancements, and Open Issues". Future Internet. 14 (1): 19. doi:10.3390/fi14010019.
^ Mahmood, A. R.; Punni, S.; Aref, W. G. (2018). "Spatio-temporal access methods: a survey (2010 – 2017)". Geoinformatica. 23 (1): 1–36. doi:10.1007/s10707-018-0329-2. S2CID 106407322.
^ ^a ^b ^c ^d ^e ^f ^g ^h ⁱ ^j Zäschke, Tilmann; Norrie, Moira (2017). "Efficient Z-Ordered Traversal of Hypercube Indexes". Lecture Notes in Informatics (LNI). P-265 (Datenbanksysteme für Business, Technologie und Web (BTW 2017)): 465–484. doi:10.3929/ethz-a-010802003.
^ Hjaltason, Gísli R.; Samet, Hanan (June 1999). "Distance browsing in spatial databases". ACM Transactions on Database Systems. 24 (2): 265–318. doi:10.1145/320248.320255. S2CID 10881319. Retrieved 12 February 2022.
^ IEEE 754 2019
^ ^a ^b Seeger, B.; Kriegel, H. P. (1988). "Techniques for Design and Implementation of Efficient Spatial Access Methods". Proceedings 1988 VLDB Conference: 14th International Conference on Very Large Data Bases. 14: 360.
^ ^a ^b Samet, Hanan (2006). Foundations of multidimensional and metric data structures. San Francisco: Elsevier/Morgan-Kaufmann. pp. 440–441, 453–457. ISBN 0-12-369446-9.
^ Li, Yan; Ge, Tingjian; Chen, Cindy (2020). "Online Indices for Predictive Top-k Entity and Aggregate Queries on Knowledge Graphs". 2020 IEEE 36th International Conference on Data Engineering (ICDE): 1057–1068. doi:10.1109/ICDE48307.2020.00096. ISBN 978-1-7281-2903-7. S2CID 218907333.
^ ^a ^b Sprenger, Stefan (2019). "Efficient Processing of Range Queries in Main Memory". doi:10.18452/19786. {{cite journal}}:Cite 저널 요구 사항 journal=(도움말)
^ Khatibi, A.; Porto, F.; Rittmeyer, J. G.; Ogasawara, E.; Valduriez, P.; Shasha, D. (August 2017). "Pre-processing and indexing techniques for constellation queries in big data" (PDF). International Conference on Big Data Analytics and Knowledge Discovery. Lecture Notes in Computer Science. 10440: 164–172. doi:10.1007/978-3-319-64283-3_12. ISBN 978-3-319-64282-6. S2CID 3857469.
^ Winter, C.; Kipf, A.; Anneser, C.; Zacharatou, E. T.; Neumann, T.; Kemper, A. (2020). "GeoBlocks: A Query-Cache Accelerated Data Structure for Spatial Aggregation over Polygons". EDBT. 23: 169–180. doi:10.5441/002/edbt.2021.16.
^ Wang, S.; Maier, D.; Ooi, B. (2016). "Fast and Adaptive Indexing of Multi-Dimensional Observational Data". Proceedings of the VLDB Endowment. 9 (14): 1683. doi:10.14778/3007328.3007334.
^ Herrera, Stiw; da Silva, Larissa Miguez; Reis, Paulo Ricardo; Silva, Anderson; Porto, Fabio (2021). "Managing Sparse Spatio-Temporal Data in SAVIME: an Evaluation of the PH-tree Index". Anais do XXXVI Simpósio Brasileiro de Bancos de Dados: 337–342. doi:10.5753/sbbd.2021.17895. S2CID 245185935.

[PH-tree-2014-1] ^ ^a ^b ^c ^d ^e ^f ^g ^h ⁱ ^j ^k ^l ^m ⁿ ^o ^p Zäschke, Tilmann; Zimmerli, Christoph; Norrie, Moira C. (June 2014). "The PH-tree: a space-efficient storage structure and multi-dimensional index". Proc. 2014 ACM SIGMOD International Conference on Management of Data: 397–408. doi:10.1145/2588555.2588564. ISBN 9781450323765. S2CID 6862850. Retrieved 10 February 2022.

[Kouahla-2022-2] Kouahla, Z.; Benrazek, A.-E.; Ferrag, M. A.; Farou, B.; Seridi, H.; Kurulay, M.; Anjum, A.; Asheralieva, A. (2022). "Survey on Big IoT Data Indexing: Potential Solutions, Recent Advancements, and Open Issues". Future Internet. 14 (1): 19. doi:10.3390/fi14010019.

[Mahmood-2018-3] Mahmood, A. R.; Punni, S.; Aref, W. G. (2018). "Spatio-temporal access methods: a survey (2010 – 2017)". Geoinformatica. 23 (1): 1–36. doi:10.1007/s10707-018-0329-2. S2CID 106407322.

[z-ordered-traversal-2017-4] ^ ^a ^b ^c ^d ^e ^f ^g ^h ⁱ ^j Zäschke, Tilmann; Norrie, Moira (2017). "Efficient Z-Ordered Traversal of Hypercube Indexes". Lecture Notes in Informatics (LNI). P-265 (Datenbanksysteme für Business, Technologie und Web (BTW 2017)): 465–484. doi:10.3929/ethz-a-010802003.

[kNN-5] Hjaltason, Gísli R.; Samet, Hanan (June 1999). "Distance browsing in spatial databases". ACM Transactions on Database Systems. 24 (2): 265–318. doi:10.1145/320248.320255. S2CID 10881319. Retrieved 12 February 2022.

[IEEE-754-2019-6] IEEE 754 2019

[Seeger-1988-corner-representation-7] Seeger, B.; Kriegel, H. P. (1988). "Techniques for Design and Implementation of Efficient Spatial Access Methods". Proceedings 1988 VLDB Conference: 14th International Conference on Very Large Data Bases. 14: 360.

[Samet-foundations-2006-8] Samet, Hanan (2006). Foundations of multidimensional and metric data structures. San Francisco: Elsevier/Morgan-Kaufmann. pp. 440–441, 453–457. ISBN 0-12-369446-9.

[Li-2020-9] Li, Yan; Ge, Tingjian; Chen, Cindy (2020). "Online Indices for Predictive Top-k Entity and Aggregate Queries on Knowledge Graphs". 2020 IEEE 36th International Conference on Data Engineering (ICDE): 1057–1068. doi:10.1109/ICDE48307.2020.00096. ISBN 978-1-7281-2903-7. S2CID 218907333.

[Spengler-thesis-10] Sprenger, Stefan (2019). "Efficient Processing of Range Queries in Main Memory". doi:10.18452/19786. {{cite journal}}:Cite 저널 요구 사항 journal=(도움말)

[Khatibi-2017-11] Khatibi, A.; Porto, F.; Rittmeyer, J. G.; Ogasawara, E.; Valduriez, P.; Shasha, D. (August 2017). "Pre-processing and indexing techniques for constellation queries in big data" (PDF). International Conference on Big Data Analytics and Knowledge Discovery. Lecture Notes in Computer Science. 10440: 164–172. doi:10.1007/978-3-319-64283-3_12. ISBN 978-3-319-64282-6. S2CID 3857469.

[Kipf-2020-12] Winter, C.; Kipf, A.; Anneser, C.; Zacharatou, E. T.; Neumann, T.; Kemper, A. (2020). "GeoBlocks: A Query-Cache Accelerated Data Structure for Spatial Aggregation over Polygons". EDBT. 23: 169–180. doi:10.5441/002/edbt.2021.16.

[Wang-2016-13] Wang, S.; Maier, D.; Ooi, B. (2016). "Fast and Adaptive Indexing of Multi-Dimensional Observational Data". Proceedings of the VLDB Endowment. 9 (14): 1683. doi:10.14778/3007328.3007334.

[Herrera-2021-14] Herrera, Stiw; da Silva, Larissa Miguez; Reis, Paulo Ricardo; Silva, Anderson; Porto, Fabio (2021). "Managing Sparse Spatio-Temporal Data in SAVIME: an Evaluation of the PH-tree Index". Anais do XXXVI Simpósio Brasileiro de Bancos de Dados: 337–342. doi:10.5753/sbbd.2021.17895. S2CID 245185935.

[1]

[3]

[2]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

v t 트리 데이터 구조
트리 검색 (다이나믹 세트/어소시에이션 어레이)	2–3 2–3–4 AA (a, b) AVL B B+ B* B^x. (최적) 바이너리 검색 춤추다 HTree 간격 주문통계 (좌향) 레드-블랙 희생양 스플라이 T 나무 UB 무게 밸런스
수북이	바이너리 이항 브로달 피보나치 좌파 페어링 스큐 판 엠데 보아스 약한
시도하다	Ctrie C-trie(압축 ADT) 해시 기수 서픽스 삼진수 검색 X-Fast 고속
공간 데이터 파티션 트리	공 BK BSP 데카르트어 힐베르트 R k-d(표준 k-d) M 미터법 MVP 옥트리 PH 우선 순위 R 쿼드 R R+ R* 부분 부사장 X
기타 트리	덮다 지수 펜윅 손가락. 프랙탈 트리 인덱스 퓨전 해시 캘린더 i디스턴스 K-ary 좌측자녀 우측자매 링크/컷 로그 구조화 결합 머클 p q. 범위 SPQR 정상

Search

PH 트리

네임스페이스

더

목차

개요

분할 전략

사분면 번호부여부

1D 예시

2D 예시

노드 구조

운용

찾다

삽입

제거한다.

윈도 쿼리

$최소$ 시간 및 $최대$ 시간

쿼드런트가 쿼리 상자와 겹치는지 확인합니다.

쿼리 상자와 겹치는 사분원 이동

k-param 네이버

부동 소수점 키

무손실 전환

하이퍼박스 키

확장성

사용하다

실장

「」를 참조해 주세요.

레퍼런스

Search

PH 트리

개요

분할 전략

사분면 번호부여부

1D 예시

2D 예시

노드 구조

운용

찾다

삽입

제거한다.

윈도 쿼리

최소 시간 및 최대 시간

쿼드런트가 쿼리 상자와 겹치는지 확인합니다.

쿼리 상자와 겹치는 사분원 이동

k-param 네이버

부동 소수점 키

무손실 전환

하이퍼박스 키

확장성

사용하다

실장

「 」를 참조해 주세요.

레퍼런스

$최소$ 시간 및 $최대$ 시간

「」를 참조해 주세요.