범위 조회(데이터 구조)
Range query (data structures)![]() |
데이터 구조에서 범위 쿼리는 일부 입력 데이터를 데이터 구조로 사전 처리하여 입력 부분 집합에 대한 임의 수의 쿼리에 효율적으로 응답하는 것으로 구성된다.특히 입력이 정렬되지 않은 숫자의 배열이고 쿼리는 배열의 특정 범위에서 최소값과 같은 일부 기능을 계산하는 것으로 구성되는 경우 광범위하게 연구된 문제 그룹이 있다.
정의
A range query on an array of n elements of some set S, denoted , takes two indices , a function f defS 및 출력 A[ , )의 배열 위에 삽입됨 f(, … , j ) {\(A ,a_
For example, for and an array of numbers, the range query computes , for any n 쿼리는 일정한 시간에 그리고 A의 첫 번째 i 요소의 합계를 계산하여 보조 배열 B에 저장함으로써 O () 의 여분의 공간을 사용하여 응답할 수 있다. B[ 는 매 0 i i 의 합계를 포함한다 따라서 모든 질의는a [ , = [ - [ - ]{\A[를 수행하여 응답할 수 있다.
전략은 f- 의 개념이 잘 정의되어 있고 쉽게 계산할 수 있는 모든 그룹 운영자에 대해 확장될 수 있다.[1]마지막으로 이 솔루션은 유사한 사전 처리를 통해 2차원 배열로 확장할 수 있다.[2]
예
세미그룹 연산자
범위 조회에 대한 관심 함수가 세미그룹 사업자일 경우, - f의 개념이 항상 정의되는 것은 아니므로, 앞 절의 전략은 효과가 없다.앤드류 야오는 세미그룹 사업자와 관련된 범위 쿼리를 위한 효율적인 해결책이 존재한다는 것을 보여주었다[3].He proved that for any constant c, a preprocessing of time and space allows to answer range queries on lists where f is a semigroup operator in time, where is a certain functional inv아커만 함수의 오류
약간 더 나은 해결책을 인정하는 몇몇 세미그룹 사업자들이 있다.예를 들어, {, 이(가) 이(가) [ 이라고 가정해 보십시오 ) 은(는) [의 최소 요소 인덱스를 반환한다. 그러면 i, ( A) 은 해당하는 최소 범위 쿼리를 나타낸다.시간과 공간의 () O의 사전 처리를 사용하여 ( O(시간의 범위 최소 조회에 응답할 수 있는 여러 데이터 구조가 있다 이러한 해결책 중 하나는 이 문제와 가장 낮은 공통 조상 문제 사이의 동등성에 기초한다.
The Cartesian tree of an array has as root and as left and right subtrees the Cartesian tree of and the Ca A[ i+ 1, 1,의 rtesian 트리.A range minimum query is the lowest common ancestor in of and . Because the lowest common ancestor can be solved in constant time using a preprocessing of time and space ) 범위 최소 쿼리도 가능하다.= 일 때의 해결책은 유사하다.데카르트 나무는 선형적으로 건설될 수 있다.
모드
배열 A의 모드는 A에 가장 많이 나타나는 요소다.예를 들어 =[ ,5,, 의 모드는 4이다 .동점일 경우 가장 빈번한 요소 중 하나를 모드로 선택할 수 있다.범위 모드 쿼리는 [ , 의 어떤 범위에서도 모드를 찾을 수 있도록 사전 처리로 구성된다 이 문제를 해결하기 위해 여러 데이터 구조가 고안되었으며, 다음 표에 몇 가지 결과를 요약한다.[1]
공간 | 쿼리 시간 | 제한사항 |
---|---|---|
최근 Jörgensen 외 연구진은 S 셀을 사용하는 데이터 구조에 대해 ( w/ n n}\rigrig)의 셀프로브 모델에서 하한을 입증했다.[4]
중앙값
중위수를 찾는 데는 여러 가지 용도가 있으므로 이 특별한 경우가 특히 중요하다.[5]반면 선택 문제의 특수한 경우인 중위수 문제는 중위수 알고리즘을 사용하여 O(n)로 해결할 수 있다.[6]그러나 범위 중위수 쿼리를 통한 일반화는 최근이다.[7]A range median query where A,i and j have the usual meanings returns the median element of . Equivalently, should return the element of - 범위 중위수 쿼리는 세미그룹 운영자에 대한 야오(Yao)의 접근법을 포함하여 위에서 논의한 이전 방법 중 하나로 해결할 수 없다[8]
이 문제의 두 가지 변형인 모든 k 쿼리가 일괄적으로 주어지는 오프라인 버전과 모든 사전 처리가 전면적으로 이루어지는 버전이 연구되어 왔다.오프라인 버전은 k+ k ) O시간과 ) k공간으로 해결할 수 있다.
의 퀵 선택 알고리즘의 유사 코드는 A[ i, 별개의 요소의 정렬되지 않은 에서 r등급 요소를 찾는 방법을 보여주며, = - r {2[7]
RangeMedian(A, 나는, j, r){만약 A.low 정의되어 있지 않습니다 만약 A.length()1반환 A[1]== 다음 인류 = median(A)A.low)[Ae에 e^m]A.high)[Ae을에서 e,입니다 나이]를 계산하 옆 A[나는, j]의 만약 r<>는 A.low에 속하는 요소의 개수^t 다음 돌아오rangeMedian(A.low, 나는, j, r)그 밖의 다른 복귀 다양하다.메디안(Ahigh, i, j, r-t) }
절차rangeMedian
칸막이A
사용.A
의 중위수, 두 개의 배열로 나뉜다.A.low
그리고A.high
, 전자가 의 요소를 포함하는 경우A
중위수보다 작거나 같은 값m
그리고 후자의 나머지 요소들A
. [ , 의 요소 수가 다음과 같은 결과를 가져온다는 것을 알게 되면A.low
이다t
그리고 이 숫자는 보다 크다.r
그러면 우리는 계속 계급의 요소를 찾아야 한다.r
에A.low
; 그렇지 않으면, 우리는 순위- ) 의 요소를 찾아야 한다.A.high
. t를 찾으려면 이 들어갈 정도의 최대 인덱스 m -1 을(를) 찾으면 충분하다.A.low
{\이 (가 들어 있는 최대 l j jA.high
. 그러면 = - m 대부분의 재귀 호출이 수행되고 각 쿼리마다 일정한 수의 작업만 수행되므로(tfractal cascading 값을 얻기 위해) 쿼리의 총 비용은 파티셔닝 부분을 고려하지 않고 이다.중위수를 찾는 선형 알고리즘을 사용하는 경우 k 범위 중위수 쿼리의 총 사전 처리 비용은 ∆ k 이다알고리즘은 또한 문제의 온라인 버전을 해결하기 위해 수정될 수 있다.[7]
다수
주어진 항목 집합에서 빈번한 요소를 찾는 것은 데이터 마이닝에서 가장 중요한 작업 중 하나이다.빈번한 요소를 찾는 것은 대부분의 항목들이 유사한 주파수를 가지고 있을 때 달성하기 어려운 작업일 수 있다.따라서 그러한 항목을 탐지하는 데 유의적인 임계값을 사용한다면 더 유익할 수 있다.대부분의 어레이를 찾는 가장 유명한 알고리즘 중 하나는 보이어와 무어에 의해 제안되었는데 보이어와 무어는 보이어-무어 다수결 알고리즘으로도 알려져 있다.보이어와 무어는 () 시간에서 O( O공간을 사용하여 문자열의 다수 요소(있는 경우)를 찾는 알고리즘을 제안했다.보이어와 무어의 작업과 일반적으로 말해서, 항목 집합의 다수 요소(예: 문자열 또는 배열)는 인스턴스 수가 그 집합의 절반 이상인 요소다.몇년이 지나고, Misra과 그리스[10]보이어와 무어의 알고리즘이 상대적인 주파수 일부 한계 0<>보다 훨씬 더 많다는 점을 배열에 모든 항목을 찾을 O(n로그 (1τ)){\displaystyle O\left(n\log \left({\frac{1}{\tau}}\right)\right)}비교를 사용하여;τ<1{\displaysty의 더 일반적인 버전을 제안했다.;\tau 0< 르<1}. 다양한 τ{\displaystyle \tau}-majority 쿼리는 주어진 서브 레인지의 데이터 구조(예를 들어 배열)의 크기 R{R\displaystyle}를 반환합니다는 세트의 모든 독특한 아이템들 나타나는 이상(또는 일부 간행물과 동일한)τ R{\displaystyle \tau R}번에 얘기하는 범위.. ▼ - 주요 조회를 지원하는 다른 구조에서 ▼ 은(는) 정적(사전 처리 중에 지정됨)이거나 동적(쿼리 시간에 지정됨)일 수 있다.그러한 접근법의 대부분은 범위 크기에 관계없이 주어진 에 대해 상대적 주파수를 적어도 의 구별되는 후보가 있을 수 있다는 사실에 기초한다 이러한 후보들을 각각 일정한 시간에 검증함으로써,( / ) 쿼리 시간을 달성함양쪽 R1{\d에 다양한 점에서 τ{\displaystyle \tau}-majority 쿼리는 분해할 수 있는[11]파티션 또한 범위에 있는τ{\displaystyle \tau}-majority R{R\displaystyle}R1{\displaystyle R_{1}}와 R2{\displaystyle R_{2}}가 되어야 한다τ{\displaystyle \tau}-majority.isp} 또는 2 이러한 분해능 때문에 일부 데이터 구조는 범위 트리에서 쿼리 범위의 끝점에 대한 최하위 공통 조상을 찾고 (크기 /)) 두 후보군을 검증하여 1차원 어레이에 대한 주요조회를 한다.각 끝점에서 한 시간 내에 가장 낮은 공통 조상으로 /) O 쿼리 시간을 생성한다
2차원 배열
Gagie(알.각 쿼리 Q이 데이터 구조에)(R, τ){\displaystyle \operatorname{Q}=(\operatorname{R},\tau)}문턱 0<>τ<1{\displays[12]. τ m×n{\displaystyle m\times의 스녀}에{\displaystyle \tau}-majority 쿼리 배열 한{A\displaystyle}는 범위를 지원하는 데이터 구조를 제시했습니다.1및 직사각형 R 이(가) 지정되었으며, frequencies 보다 크거나 같은 상대적인 주파수를 갖는 모든 요소의 집합이 출력으로 반환된다.이 데이터 구조는 생성되는 동적 임계값(쿼리 시간에 지정)과 사전 처리 임계값 을(를) 지원한다.사전 처리 중에 일련의 수직 및 수평 간격은 n 배열에 구축된다.수직 구간과 수평 구간이 함께 블록을 형성한다.각 블록은 자체보다 9배 큰 수퍼 블록(블록의 가로 간격의 3배, 세로 블록의 3배 크기)의 일부다.각 블록에 대해 후보 집합(최대 }{\이 저장되며, 각 블록에는 상대 주파수가 적어도 9 위에서 언급한 바와 같이 사전 처리 임계값)가 있는 요소로 구성된다.이러한 요소는 주파수에 따라 증가하지 않는 순서로 저장되며, 블록에 상대 주파수가 적어도 인 요소는 후보 집합으로 나타나야 한다는 것을 쉽게 알 수 있다.각 -주요 질의는 먼저 조회 블록 또는 제공된 조회 사각형에 포함된 가장 큰 블록을 ( O(1)내에 찾아 응답한다.획득한 쿼리 블록의 경우 처음 9 { 후보가 O / 번 만에 반환되므로 이 프로세스는 일부 잘못된 긍정을 반환할 수 있다.많은 다른 데이터 구조(아래에서 논의한 바와 같이)는 각 후보를 일정한 시간 내에 검증하여 O /no ){\ 쿼리 시간을 유지하면서 잘못된 긍정은 반환하지 않는 방법을 제안하였다.쿼리 블록이 / }보다 작은 경우는 다음과 같은 형식의 이 데이터 구조의 서로 다른 (instance) ( ) 를 저장하여 처리한다.
여기서 은 (는) -th 인스턴스의 사전 처리 임계값이다.따라서 / }보다 작은 쿼리 블록의 경우 (/ ) -th 인스턴스가 쿼리된다.As mentioned above, this data structure has query time and requires bits of space by storing a Huffman-encoded copy of it (note the 요인 및 Huffman 코딩도 참조하십시오.
1차원 배열
성룡(알.[13]는 1차원 배열 한{A\displaystyle}, A{A\displaystyle}(질문 응답 시간에 지정된)과 문턱 τ{\displaystyle \tau}(질문 응답 시간에 지정된)의 부분 범위 R{R\displaystyle}지정된 데이터 구조, -majorities{\displaystyle \tau}모든 τ의 목록을 반환할 수 있는 것을 제안했다 i.N ( /) O 시간 소요 ( ) n 단어 공간. 질의에 답변하기 위해 Chan 등은 [13]O () 개의 범위에서 가장 한 항목을 O( n) 개의 단어가 필요한 범위에서 반환할 수 있는 데이터 구조가 존재한다는 점을 주목하는 것으로 시작한다.1차원 배열 [ .. . , -1 , 의 경우 단측 상위 k 범위 쿼리를 [ 0] 형식으로 허용하십시오 범위 의 최대 범위[ 은(는) A 의 요소 e {\의 주파수가 변경되지 않고 과 동일한 경우 수평선 세그먼트가 생성된다.이 라인 세그먼트의 - interval은[, 에 해당하며, -값이 f 과 동일하다 각 요소를 에 추가하면 의 고유 요소의 주파수가 변경되기 때문에 앞에서 설명한 프로세스가 생성됨( ) 줄 세그먼트.또한 수직선 = 에 대해 교차하는 모든 수평선 세그먼트는 주파수에 따라 정렬된다. - interval[, r ,이(가) 있는 각 수평선 세그먼트는 에서 정확히 하나의 고유한 e 에 해당하므로 [ =] = {\\ ]=을(으)를 촬영하여 상단-k 쿼리에 응답할 수 있다= 과 (와 하는 첫번째 k {\ k} 세그먼트를 O) {\ O시간 내에 보고하십시오.
Chan 등.[13]은 먼저 각 분기 노드가 단측 범위 상위 k 쿼리에 대해 위에서 설명한 데이터 구조의 복사본 하나를 저장하고 각 리프(leaf)는 의 요소를 나타내는 범위 트리를 생성한다각 노드의 top-k 데이터 구조는 해당 노드의 하위 트리에 존재하는 값을 기반으로 구성되며, 단측 범위 top-k 쿼리에 응답하기 위한 것이다.1차원 어레이 의 경우 을(를) 두 부분으로 나누고 두 부분으로 재귀하여 범위 트리를 구성할 수 있으므로, 결과 범위 트리의 각 노드는 범위를 나타낸다. Olog levelsn 레벨이 있고 각 are에는 의 노드가 있기 때문에 이 범위 트리에 log displaystystylease O {n}단어가 필요함을 알 수 있다.더욱이 범위 트리의 각 수준 에서 모든 노드는 하위 트리에 의 요소를 가지며, ) n 수준이 있기 때문에 이 범위 트리의 공간 은 n이다 n.
이 구조를 사용하여 범위 - majority A[ 에 있는 j- 0 i≤ 은 (는) 다음과 같이 대답한다., 리프 i 및 j 의 가장 낮은 공통 조상(LCA)이 일정한 시간에 발견된다.( ) 비트의 공간을 필요로 하는 데이터 구조가 존재하므로 LCA 쿼리에 O( ) {\회 응답할 수 있다.[14] 은는) 을 (를) 사용하는 displaystyle z} 및\의 LCA를 나타내며, - maj의 분해능성에 따라 양면 범위 A[ 를 은(는) 두 개의 단측 범위 상위 k 쿼리로 변환할 수 있다( 에서 j 두 개의 단측 범위 상위 k 쿼리는 각 범위에서 가장 빈번한 요소를 / 1 시간 내에 이러한 빈번한 요소들은 [.. \}의 주요 후보들을 구성한다 후보가 O( / ) O 인 경우 일부는 잘못된 긍정일 수 있다.각 후보는 그때 상수 시간에{O(1)\displaystyle}시간(1){A\displaystyle}특정한 요소 e.의 적어도q{\displaystyle q}인스턴스가 들어 있는 배열 중 주어진 서브 레인지는 결정하기 위해 O에 수 있는linear-space 데이터 구조(로 Limma3에서[15]에서 설명한)를 활용하여 평가된다 {) 스타일 .
트리 경로
Gagie(알.[16]은 쿼리를 지원하는 데이터 구조를 제시했습니다와 같이 주어진 두 노드 u{\displaystyle u}그리고 v{\displaystyle v}에서는 나무를, 할 수 있는 요소의 목록을 가지고 있는 더 큰 상대 도수보다τ{\displaystyle \tau}에 길에서 u{\displaystyle u}에 v{\displaystyle v}.. More formally, let be a labelled tree in which each node has a label from an alphabet of size . Let denote the label of node in . Let 는 중간 노드가 한 대로나열되는 T {\에서 {\displaystyle 에서 까지의 고유한 경로를 나타낸다.감안할 때 T{T\displaystyle}, 및 고정된('연속 예비 처리'중에 지정한)임계값 0<>τ<1{\displaystyle 0<, \tau<1}, 쿼리를 Q(u, v){Q(u,v)\displaystyle}는τ P너'v'{\displaystyle\tau P_{uv}보다}P너의 v{\displaysty번 더 있는 모든 레이블의 집합을 반환해야 합니다.르 P_{uv}}.
이 데이터 구조를 구성하려면 첫 O ) n노드가 표시된다.This can be done by marking any node that has distance at least from the bottom of the three (height) and whose depth is divisible by . After doing this, it can be observed that the distance between each node and its nearest marked ancestor is less than . For a marked node , different sequences (paths towards the root) are stored,
for where returns the label of the direct parent of node . Put another way, for each marked node, the set of all paths with a power of two length (plus one for the node itself) towards 뿌리가 저장된다.또한 각 ( x) 에 대해 모든 다수 후보 C ( x )의 집합이 저장된다More specifically, contains the set of all -majorities in or labels that appear more than P에서(2^{나는}+1)}번 나는{\displaystyle P_{나는}())())}입니다. 그것은 후보자들의 집합을 나는{\displaystyle C_{나는}())())C를 보러}대부분의 2/τ{2/\tau\displaystyle} 뚜렷한 표지에 나는{\displaystyle 나는}을 위해 가질 수 있다. Gagie(알 쉽다.[16]그 다음 모든 τ{\displaystyle \tau}의 집합 -ma에 주목한다.어떤 표시 노드에서 길)에 Jorities 하나가 조상들의 z{z\displaystyle}일부 C나는()){\displaystyle C_{나는}())}(Limma2[16]에서)P의 나는}{\displaystyle P_{나는}())())은 길이부터(나는 12및)와 같은지{\displaystyle(2^{나는}+1)} 있exi에 포함되어 있는{\displaystyle)}.stsa for whose length is between where is the distance between x and z.The existence of such implies that a -majority in the path from to must be a -majority in , and thus must appear in ( ) 위의 구성 단계 n) 노드가 표시되고 각 표시 노드에 대해 일부 후보 세트가 저장되기 때문에 이 데이터 에는O log n){\displaystystylease n)가 필요한 것으로 쉽게 알 수 있다.정의상, 표시된 각 노드 O) 에 대해 이러한 집합은 스토어이며, 각 세트에는 (1/)개의 후보가 포함되어 있다.따라서 이 데이터 구조에는 log ( 1/ ) × × )= O n) n개의 공간이 필요하다.각 노드 은 (는)x {\displaystyle 에서 루트까지의 경로에 l ( ) 의 인스턴스 수와 동일한 n 를 저장하므로 공간 복잡성이 증가되지 않는다노드당 일정한 수의 단어만 추가된다.
두 노드 과 ( v {\ 사이의 쿼리는 {\displaystyle -주요 쿼리 범위의 분해성 속성(위에서 설명한 대로)을 사용하고 과 사이의 쿼리 경로를 4개의 하위 경로로 구분하여 응답할 수 있다. 을를) 과 ( v {\ v의 가장 낮은 공통 조상이 하고 y {\은 u {\}과 의 가장 가까운 조상이 되도록 한다. 에서 v 까지의 경로는 각각 및 y 의 경로로 분해된다(이 경로의 크기가 / 정의( 후보로 간주됨) 및 y 에서 까지의 경로(위에서 설명한 대로 적합한 를 찾고 레이블을 후보자로 고려함).경계 노드는 그에 따라 처리되어야 이러한 모든 하위 경로가 분리되고 그 모든 경로에서 /) 후보 집합이 파생된다는 점에 유의하십시오.그런 다음 이러한 후보 각각은 노드의 필드가 x 의 가장 낮은 상위 항목을 반환하는 (x , 쿼리의 조합을 사용하여 검증한다.On a -bit RAM and an alphabet of size , the query can be answered in time whilst having linear space requirements.[17]Therefore, verifying each of the candidates in time results in total query time for returning the s 의 모든 all중 - u {\ 에서 v {\displaystyle 까지의 경로에 대한 주요 사항
관련 문제
위에서 설명한 모든 문제는 동적 버전뿐만 아니라 더 높은 차원에서도 연구되었다.반면에 범위 쿼리는 수준 조상 문제와 [8]같은 나무와 같은 다른 데이터 구조로 확장될 수 있다.유사한 문제군은 직교 범위 쿼리로, 카운트 쿼리라고도 한다.
참고 항목
참조
- ^ a b Krizanc, Danny; Morin, Pat; Smid, Michiel H. M. (2003). "Range Mode and Range Median Queries on Lists and Trees". ISAAC: 517–526. arXiv:cs/0307034.
- ^ Meng, He; Munro, J. Ian; Nicholson, Patrick K. (2011). "Dynamic Range Selection in Linear Space". ISAAC: 160–169.
- ^ Yao, A. C (1982). "Space-Time Tradeoff for Answering Range Queries". E 14th Annual ACM Symposium on the Theory of Computing: 128–136.
- ^ Greve, M; J{\o}rgensen, A.; Larsen, K.; Truelsen, J. (2010). "Cell probe lower bounds and approximations for range mode". Automata, Languages and Programming: 605–616.
- ^ Har-Peled, Sariel; Muthukrishnan, S. (2008). "Range Medians". ESA: 503–514.
- ^ Blum, M.; Floyd, R. W.; Pratt, V. R.; Rivest, R. L.; Tarjan, R. E. (August 1973). "Time bounds for selection" (PDF). Journal of Computer and System Sciences. 7 (4): 448–461. doi:10.1016/S0022-0000(73)80033-9.
- ^ a b c Beat, Gfeller; Sanders, Peter (2009). "Towards Optimal Range Medians". Icalp (1): 475–486.
- ^ a b Bose, P; Kranakis, E.; Morin, P.; Tang, Y. (2005). "Approximate range mode and range median queries". In Proceedings of the 22nd Symposium on Theoretical Aspects of Computer Science (STACS 2005), Volume 3404 of Lecture Notes in ComputerScience: 377–388.
- ^ Boyer, Robert S.; Moore, J. Strother (1991), "MJRTY—A Fast Majority Vote Algorithm", Automated Reasoning Series, Dordrecht: Springer Netherlands, pp. 105–117, retrieved 2021-12-18
- ^ Misra, J.; Gries, David (November 1982). "Finding repeated elements". Science of Computer Programming. 2 (2): 143–152. doi:10.1016/0167-6423(82)90012-0. ISSN 0167-6423.
- ^ a b Verfasser, Karpiński, Marek 1948-. Searching for frequent colors in rectangles. OCLC 277046650.
{{cite book}}
:last=
일반 이름 포함(도움말) - ^ Gagie, Travis; He, Meng; Munro, J. Ian; Nicholson, Patrick K. (2011), "Finding Frequent Elements in Compressed 2D Arrays and Strings", String Processing and Information Retrieval, Berlin, Heidelberg: Springer Berlin Heidelberg, pp. 295–300, ISBN 978-3-642-24582-4, retrieved 2021-12-18
- ^ a b c Chan, Timothy M.; Durocher, Stephane; Skala, Matthew; Wilkinson, Bryan T. (2012), "Linear-Space Data Structures for Range Minority Query in Arrays", Algorithm Theory – SWAT 2012, Berlin, Heidelberg: Springer Berlin Heidelberg, pp. 295–306, ISBN 978-3-642-31154-3, retrieved 2021-12-20
- ^ Sadakane, Kunihiko; Navarro, Gonzalo (2010-01-17). "Fully-Functional Succinct Trees". Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms. Philadelphia, PA: Society for Industrial and Applied Mathematics. doi:10.1137/1.9781611973075.13.
- ^ Chan, Timothy M.; Durocher, Stephane; Larsen, Kasper Green; Morrison, Jason; Wilkinson, Bryan T. (2013-03-08). "Linear-Space Data Structures for Range Mode Query in Arrays". Theory of Computing Systems. 55 (4): 719–741. doi:10.1007/s00224-013-9455-2. ISSN 1432-4350.
- ^ a b c Gagie, Travis; He, Meng; Navarro, Gonzalo; Ochoa, Carlos (September 2020). "Tree path majority data structures". Theoretical Computer Science. 833: 107–119. doi:10.1016/j.tcs.2020.05.039. ISSN 0304-3975.
- ^ He, Meng; Munro, J. Ian; Zhou, Gelin (2014-07-08). "A Framework for Succinct Labeled Ordinal Trees over Large Alphabets". Algorithmica. 70 (4): 696–717. doi:10.1007/s00453-014-9894-4. ISSN 0178-4617.