Succinct Data Structures

(1)

Succinct Data Structures

Auto-completion as our target application

Rossano Venturini

[email protected]

(2)

(3)

(4)

(5)

(6)

(7)

(8)

Dataset?

(9)

Dataset? All the past queries

(10)

Dataset?

Searches?

All the past queries

(11)

Dataset?

Prefix search Searches?

All the past queries

(12)

Dataset?

Prefix search Searches?

All the past queries

Data structure?

(13)

Dataset?

Prefix search Searches?

All the past queries

Data structure? Trie

(14)

Dataset?

Prefix search Searches?

All the past queries Data structure? Trie

How to find top-k efficiently?

(15)

Trie

(16)

D = { ab (7), bab (2), bca (1), cab (4), cac (1), cbac (6), cbba (2) }

Trie

(17)

D = { ab (7), bab (2), bca (1), cab (4), cac (1), cbac (6), cbba (2) } n = |D|, m total length of strings in D

Trie

(18)

D = { ab (7), bab (2), bca (1), cab (4), cac (1), cbac (6), cbba (2) } n = |D|, m total length of strings in D

7

2 1

4 1 6 2

ab b

ab ca

c

a b

ba ac

b c

Trie

(19)

D = { ab (7), bab (2), bca (1), cab (4), cac (1), cbac (6), cbba (2) } n = |D|, m total length of strings in D

7

2 1

4 1 6 2

ab b

ab ca

c

a b

ba ac

b c

Trie

O(n) nodes

O(n log n + m log σ) bits of space

(20)

D = { ab (7), bab (2), bca (1), cab (4), cac (1), cbac (6), cbba (2) } n = |D|, m total length of strings in D

7

2 1

4 1 6 2

ab b

ab ca

c

a b

ba ac

b c

Trie

O(n) nodes

O(n log n + m log σ) bits of space Find all the strings prefixed by

any pattern P in O(|P|) time

(21)

D = { ab (7), bab (2), bca (1), cab (4), cac (1), cbac (6), cbba (2) } n = |D|, m total length of strings in D

7

2 1

4 1 6 2

ab b

ab ca

c

a b

ba ac

b c

P = c

Trie

O(n) nodes

(22)

D = { ab (7), bab (2), bca (1), cab (4), cac (1), cbac (6), cbba (2) } n = |D|, m total length of strings in D

7

2 1

4 1 6 2

ab b

ab ca

c

a b

ba ac

b c

P = c

Trie

O(n) nodes

(23)

D = { ab (7), bab (2), bca (1), cab (4), cac (1), cbac (6), cbba (2) } n = |D|, m total length of strings in D

7

2 1

4 1 6 2

ab b

ab ca

c

a b

ba ac

b c

P = c

Finding Top-1

(24)

D = { ab (7), bab (2), bca (1), cab (4), cac (1), cbac (6), cbba (2) } n = |D|, m total length of strings in D

7

2 1

4 1 6 2

ab b

ab ca

c

a b

ba ac

b c

P = c

How to find Top-1?

Finding Top-1

(25)

D = { ab (7), bab (2), bca (1), cab (4), cac (1), cbac (6), cbba (2) } n = |D|, m total length of strings in D

7

2 1

4 1 6 2

ab b

ab ca

c

a b

ba ac

b c

P = c

How to find Top-1?

Finding Top-1

(26)

D = { ab (7), bab (2), bca (1), cab (4), cac (1), cbac (6), cbba (2) } n = |D|, m total length of strings in D

7

2 1

4 1 6 2

ab b

ab ca

c

a b

ba ac

b c

P = c

How to find Top-1?

Scan to find the maximum!

Finding Top-1

(27)

D = { ab (7), bab (2), bca (1), cab (4), cac (1), cbac (6), cbba (2) } n = |D|, m total length of strings in D

7

2 1

4 1 6 2

ab b

ab ca

c

a b

ba ac

b c

P = c

How to find Top-1?

Finding Top-1

(28)

D = { ab (7), bab (2), bca (1), cab (4), cac (1), cbac (6), cbba (2) } n = |D|, m total length of strings in D

7

2 1

4 1 6 2

ab b

ab ca

c

a b

ba ac

b c

P = c

How to find Top-1?

Finding Top-1

(29)

D = { ab (7), bab (2), bca (1), cab (4), cac (1), cbac (6), cbba (2) } n = |D|, m total length of strings in D

7

2 1

4 1 6 2

ab b

ab ca

c

a b

ba ac

b c

P = c

How to find Top-1?

O(n) query time :-(

Finding Top-1

(30)

D = { ab (7), bab (2), bca (1), cab (4), cac (1), cbac (6), cbba (2) } n = |D|, m total length of strings in D

7

2 1

4 1 6 2

ab b

ab ca

c

a b

ba ac

b c

P = c

How to find Top-1?

O(n) query time :-(

Better ideas?

Finding Top-1

(31)

D = { ab (7), bab (2), bca (1), cab (4), cac (1), cbac (6), cbba (2) } n = |D|, m total length of strings in D

7

2 1

4 1 6 2

ab b

ab ca

c

a b

ba ac

b c

P = c

How to find Top-1?

Finding Top-1

(32)

D = { ab (7), bab (2), bca (1), cab (4), cac (1), cbac (6), cbba (2) } n = |D|, m total length of strings in D

7

2 1

4 1 6 2

ab b

ab ca

c

a b

ba ac

b c

P = c

How to find Top-1?

Augment each node with the max (and string id )

within its subtree!

Finding Top-1

(33)

D = { ab (7), bab (2), bca (1), cab (4), cac (1), cbac (6), cbba (2) } n = |D|, m total length of strings in D

7

2 1

4 1 6 2

ab b

ab ca

c

a b

ba ac

b c

P = c

How to find Top-1?

within its subtree!

4,3

Finding Top-1

(34)

D = { ab (7), bab (2), bca (1), cab (4), cac (1), cbac (6), cbba (2) } n = |D|, m total length of strings in D

7

2 1

4 1 6 2

ab b

ab ca

c

a b

ba ac

b c

P = c

How to find Top-1?

within its subtree!

4,3 6,5

Finding Top-1

(35)

D = { ab (7), bab (2), bca (1), cab (4), cac (1), cbac (6), cbba (2) } n = |D|, m total length of strings in D

7

2 1

4 1 6 2

ab b

ab ca

c

a b

ba ac

b c

P = c

How to find Top-1?

within its subtree!

4,3 6,5

6,5

Finding Top-1

(36)

D = { ab (7), bab (2), bca (1), cab (4), cac (1), cbac (6), cbba (2) } n = |D|, m total length of strings in D

7

2 1

4 1 6 2

ab b

ab ca

c

a b

ba ac

b c

P = c

How to find Top-1?

within its subtree!

4,3 6,5

6,5 2,1

Finding Top-1

(37)

D = { ab (7), bab (2), bca (1), cab (4), cac (1), cbac (6), cbba (2) } n = |D|, m total length of strings in D

7

2 1

4 1 6 2

ab b

ab ca

c

a b

ba ac

b c

P = c

How to find Top-1?

within its subtree!

4,3 6,5

6,5 2,1

7,0

Finding Top-1

(38)

D = { ab (7), bab (2), bca (1), cab (4), cac (1), cbac (6), cbba (2) } n = |D|, m total length of strings in D

7

2 1

4 1 6 2

ab b

ab ca

c

a b

ba ac

b c

P = c

How to find Top-1?

within its subtree!

4,3 6,5

6,5 2,1

7,0

Preprocessing time: O(n)

!

Extra space: O(n log n) bits

!

Query time: O(1)

Finding Top-1

(39)

D = { ab (7), bab (2), bca (1), cab (4), cac (1), cbac (6), cbba (2) } n = |D|, m total length of strings in D

7

2 1

4 1 6 2

ab b

ab ca

c

a b

ba ac

b c

P = c

How to find Top-1?

within its subtree!

4,3 6,5

6,5 2,1

7,0

!

Query time: O(1)

Solving Top-k?

!

Finding Top-1

(40)

D = { ab (7), bab (2), bca (1), cab (4), cac (1), cbac (6), cbba (2) } n = |D|, m total length of strings in D

7

2 1

4 1 6 2

ab b

ab ca

c

a b

ba ac

b c

P = c

How to find Top-1?

within its subtree!

4,3 6,5

6,5 2,1

7,0

!

Query time: O(1)

Solving Top-k?

!

Finding Top-1

Solving Top-k?

!

- Extra space: O(k*n*log n) bits :-(

- You must know k at building time! :-(

(41)

n = |D|, m total length of strings in D

7

2 1

4 1 6 2

ab b

ab ca

c

a b

ba ac

b c

P = c

How to find Top-1?

Finding Top-1

D = { ab (7), bab (2), bca (1), cab (4), cac (1), cbac (6), cbba (2) }

(42)

n = |D|, m total length of strings in D

7

2 1

4 1 6 2

ab b

ab ca

c

a b

ba ac

b c

P = c

How to find Top-1?

7 2 1 4 1 6 2

S

Finding Top-1

D = { ab (7), bab (2), bca (1), cab (4), cac (1), cbac (6), cbba (2) }

(43)

n = |D|, m total length of strings in D

7

2 1

4 1 6 2

ab b

ab ca

c

a b

ba ac

b c

P = c

How to find Top-1?

Assume you have a Data Structure on top of S answering in O(1) by using O(n) bits

!

RMQ(i,j) = position of the maximum in the

range S[i,j]

S

7 2 1 4 1 6 2

Finding Top-1

D = { ab (7), bab (2), bca (1), cab (4), cac (1), cbac (6), cbba (2) }

(44)

n = |D|, m total length of strings in D

7

2 1

4 1 6 2

ab b

ab ca

c

a b

ba ac

b c

P = c

How to find Top-1?

!

range S[i,j]

S

7 2 1 4 1 6 2

Finding Top-1

D = { ab (7), bab (2), bca (1), cab (4), cac (1), cbac (6), cbba (2) }

(45)

n = |D|, m total length of strings in D

7

2 1

4 1 6 2

ab b

ab ca

c

a b

ba ac

b c

P = c

How to find Top-1?

!

range S[i,j]

S

7 2 1 4 1 6 2

RMQ(3,6) = 5

Finding Top-1

D = { ab (7), bab (2), bca (1), cab (4), cac (1), cbac (6), cbba (2) }

(46)

n = |D|, m total length of strings in D

7

2 1

4 1 6 2

ab b

ab ca

c

a b

ba ac

b c

P = c

How to find Top-1?

!

range S[i,j]

S

7 2 1 4 1 6 2

RMQ(3,6) = 5 Can you solve Top-2?

Finding Top-1

D = { ab (7), bab (2), bca (1), cab (4), cac (1), cbac (6), cbba (2) }

(47)

n = |D|, m total length of strings in D

7

2 1

4 1 6 2

ab b

ab ca

c

a b

ba ac

b c

P = c

How to find Top-1?

!

range S[i,j] Can you solve Top-2?

S

7 2 1 4 1 6 2

Finding Top-1

D = { ab (7), bab (2), bca (1), cab (4), cac (1), cbac (6), cbba (2) }

(48)

n = |D|, m total length of strings in D

7

2 1

4 1 6 2

ab b

ab ca

c

a b

ba ac

b c

P = c

How to find Top-1?

!

range S[i,j] Can you solve Top-2?

S

7 2 1 4 1 6 2

Finding Top-1

D = { ab (7), bab (2), bca (1), cab (4), cac (1), cbac (6), cbba (2) }

(49)

Finding Top-k

(50)

Finding Top-k

3 5 1 7 1 6 10

S

^… ⁹ ⁸ ⁷ ¹ ⁴ ² ^…

(51)

Finding Top-k

3 5 1 7 1 6 10

S

^… ⁹ ⁸ ⁷ ¹ ⁴ ² ^…

10

(52)

Finding Top-k

3 5 1 7 1 6 10

S

^… ⁹ ⁸ ⁷ ¹ ⁴ ² ^…

10

7

(53)

Finding Top-k

3 5 1 7 1 6 10

S

^… ⁹ ⁸ ⁷ ¹ ⁴ ² ^…

10

7 9

(54)

Finding Top-k

3 5 1 7 1 6 10

S

^… ⁹ ⁸ ⁷ ¹ ⁴ ² ^…

10

7 9

5

3

6

1 1

(55)

Finding Top-k

3 5 1 7 1 6 10

S

^… ⁹ ⁸ ⁷ ¹ ⁴ ² ^…

10

7 9

8 5

3

6

1 7

4

1 2

1

(56)

Finding Top-k

3 5 1 7 1 6 10

S

^… ⁹ ⁸ ⁷ ¹ ⁴ ² ^…

10

7 9

8 5

3

6

1 7

4

1 2

Cartesian Tree

It can be built top-down with RMQ

1

(57)

Finding Top-k

3 5 1 7 1 6 10

S

^… ⁹ ⁸ ⁷ ¹ ⁴ ² ^…

10

7 9

8 5

3

6

1 7

4

1 2

Cartesian Tree

How to find Top-k?

1

(58)

Finding Top-k

3 5 1 7 1 6 10

S

^… ⁹ ⁸ ⁷ ¹ ⁴ ² ^…

10

7 9

8 5

3

6

1 7

4

1 2

Cartesian Tree

How to find Top-k?

Visit the node starting from the root and try to insert each visited node in a

max-Heap storing at most k elements.

!

Extract (and report) the maximum from the heap and visit its children.

1

(59)

Finding Top-k

3 5 1 7 1 6 10

S

^… ⁹ ⁸ ⁷ ¹ ⁴ ² ^…

10

7 9

8 5

3

6

1 7

4

1 2

Cartesian Tree

How to find Top-k?

!

max-Heap k=4

1

(60)

Finding Top-k

3 5 1 7 1 6 10

S

^… ⁹ ⁸ ⁷ ¹ ⁴ ² ^…

10

7 9

8 5

3

6

1 7

4

1 2

Cartesian Tree

How to find Top-k?

!

Results 1

(61)

Finding Top-k

3 5 1 7 1 6 10

S

^… ⁹ ⁸ ⁷ ¹ ⁴ ² ^…

10

7 9

8 5

3

6

1 7

4

1 2

Cartesian Tree

How to find Top-k?

!

Results 1

(62)

Finding Top-k

3 5 1 7 1 6 10

S

^… ⁹ ⁸ ⁷ ¹ ⁴ ² ^…

10

7 9

8 5

3

6

1 7

4

1 2

Cartesian Tree

How to find Top-k?

!

10

Results 1

(63)

Finding Top-k

3 5 1 7 1 6 10

S

^… ⁹ ⁸ ⁷ ¹ ⁴ ² ^…

10

7 9

8 5

3

6

1 7

4

1 2

Cartesian Tree

How to find Top-k?

!

Results 1

(64)

Finding Top-k

3 5 1 7 1 6 10

S

^… ⁹ ⁸ ⁷ ¹ ⁴ ² ^…

10

7 9

8 5

3

6

1 7

4

1 2

Cartesian Tree

How to find Top-k?

!

Results

10

1

(65)

Finding Top-k

3 5 1 7 1 6 10

S

^… ⁹ ⁸ ⁷ ¹ ⁴ ² ^…

10

7 9

8 5

3

6

1 7

4

1 2

Cartesian Tree

How to find Top-k?

!

Results

10

1

(66)

Finding Top-k

3 5 1 7 1 6 10

S

^… ⁹ ⁸ ⁷ ¹ ⁴ ² ^…

10

7 9

8 5

3

6

1 7

4

1 2

Cartesian Tree

How to find Top-k?

!

9 7

Results

10

1

(67)

Finding Top-k

3 5 1 7 1 6 10

S

^… ⁹ ⁸ ⁷ ¹ ⁴ ² ^…

10

7 9

8 5

3

6

1 7

4

1 2

Cartesian Tree

How to find Top-k?

!

9 7

Results

7 10

1

(68)

Finding Top-k

3 5 1 7 1 6 10

S

^… ⁹ ⁸ ⁷ ¹ ⁴ ² ^…

10

7 9

8 5

3

6

1 7

4

1 2

Cartesian Tree

How to find Top-k?

!

9 7

Results

7 10

9

1

(69)

Finding Top-k

3 5 1 7 1 6 10

S

^… ⁹ ⁸ ⁷ ¹ ⁴ ² ^…

10

7 9

8 5

3

6

1 7

4

1 2

Cartesian Tree

How to find Top-k?

!

9 7

Results

7 10

9 8

7

1

(70)

Finding Top-k

3 5 1 7 1 6 10

S

^… ⁹ ⁸ ⁷ ¹ ⁴ ² ^…

10

7 9

8 5

3

6

1 7

4

1 2

Cartesian Tree

How to find Top-k?

!

9 7

Results

7 10

9 8

7 7

1

(71)

Finding Top-k

3 5 1 7 1 6 10

S

^… ⁹ ⁸ ⁷ ¹ ⁴ ² ^…

10

7 9

8 5

3

6

1 7

4

1 2

Cartesian Tree

How to find Top-k?

!

9 7

Results

7 10

9 8

7

8 7

1

(72)

Finding Top-k

3 5 1 7 1 6 10

S

^… ⁹ ⁸ ⁷ ¹ ⁴ ² ^…

10

7 9

8 5

3

6

1 7

4

1 2

Cartesian Tree

How to find Top-k?

!

9 7

Results

7 10

9 8

7

8 77

7

1

(73)

Finding Top-k

3 5 1 7 1 6 10

S

^… ⁹ ⁸ ⁷ ¹ ⁴ ² ^…

10

7 9

8 5

3

6

1 7

4

1 2

Cartesian Tree

How to find Top-k?

!

9 7

Results

7 10

9 8

7

8 77

7 7

7

1

(74)

Finding Top-k

3 5 1 7 1 6 10

S

^… ⁹ ⁸ ⁷ ¹ ⁴ ² ^…

10

7 9

8 5

3

6

1 7

4

1 2

Cartesian Tree

How to find Top-k?

!

9 7

Results

7 10

9 8

7

8 77

7 7

7

Claim: we “touch” at most 2k nodes.

Query time O(k log k) 1

(75)

Finding Top-k

3 5 1 7 1 6 10

S

^… ⁹ ⁸ ⁷ ¹ ⁴ ² ^…

10

7 9

8 5

3

6

1 7

4

1 2

Cartesian Tree

How to find Top-k?

!

9 7

Results

7 10

9 8

7

8 77

7 7

7

Query time O(k log k)

Important: the cartesian tree is not built!

1

(76)

Finding Top-k

3 5 1 7 1 6 10

S

^… ⁹ ⁸ ⁷ ¹ ⁴ ² ^…

10

7 9

8 5

3

6

1 7

4

1 2

Cartesian Tree

How to find Top-k?

!

9 7

Results

7 10

9 8

7

8 77

7 7

7

Query time O(k log k)

Important: the cartesian tree is not built!

1 Assume you have a Data Structure on top of S answering in O(1) by using O(n) bits

!

RMQ(i,j) = position of the maximum in the range S[i,j]

(77)

Range Maximum Query (1)

3 5 1 7 1 6 10

S

⁹ ⁸ ⁷ ¹ ⁴

0 1 2 3 4 5 6 7 8 9 10 11

(78)

Range Maximum Query (1)

3 5 1 7 1 6 10

S

⁹ ⁸ ⁷ ¹ ⁴

0 1 2 3 4 5 6 7 8 9 10 11

Space: O(n² log n) bits Query time: O(1)

(79)

Range Maximum Query (1)

3 5 1 7 1 6 10

S

⁹ ⁸ ⁷ ¹ ⁴

0 1 2 3 4 5 6 7 8 9 10 11

Precompute the answer to any possible query.

!

There are O(n²) distinct queries!

(80)

Range Maximum Query (1)

3 5 1 7 1 6 10

S

⁹ ⁸ ⁷ ¹ ⁴

0 1 2 3 4 5 6 7 8 9 10 11

Space: O(n² log n) bits

Query time: O(1)

M[i,j] = RMQ(i,j)

!

(81)

Range Maximum Query (1)

3 5 1 7 1 6 10

S

⁹ ⁸ ⁷ ¹ ⁴

0 1 2 3 4 5 6 7 8 9 10 11

M

⁰ ¹ ² ³ ⁴ ⁵ ⁶ ⁷ ⁸ ^{9 10 11}

0 1

5 2 3 4

6 7 8 9 10 11

M[i,j] = RMQ(i,j)

!

(82)

Range Maximum Query (1)

3 5 1 7 1 6 10

S

⁹ ⁸ ⁷ ¹ ⁴

0 1 2 3 4 5 6 7 8 9 10 11

M

⁰ ¹ ² ³ ⁴ ⁵ ⁶ ⁷ ⁸ ^{9 10 11}

0 1

5 2 3 4

6 7 8 9 10 11

M[i,j] = RMQ(i,j)

!

3

(83)

Range Maximum Query (2)

3 5 1 7 1 6 10

S

⁹ ⁸ ⁷ ¹ ⁴

0 1 2 3 4 5 6 7 8 9 10 11

(84)

Range Maximum Query (2)

3 5 1 7 1 6 10

S

⁹ ⁸ ⁷ ¹ ⁴

0 1 2 3 4 5 6 7 8 9 10 11

Space: O(n log² n) bits Query time: O(1)

(85)

Range Maximum Query (2)

3 5 1 7 1 6 10

S

⁹ ⁸ ⁷ ¹ ⁴

0 1 2 3 4 5 6 7 8 9 10 11

Maximum in a interval is the

max between the maxima of any its subintervals

(86)

Range Maximum Query (2)

3 5 1 7 1 6 10

S

⁹ ⁸ ⁷ ¹ ⁴

0 1 2 3 4 5 6 7 8 9 10 11

Precompute the answer to every interval of size a power of 2.

!

There are O(log n) possible

intervals starting at any position i.

(87)

Range Maximum Query (2)

3 5 1 7 1 6 10

S

⁹ ⁸ ⁷ ¹ ⁴

0 1 2 3 4 5 6 7 8 9 10 11

Space: O(n log² n) bits

Query time: O(1)

M[i,j] = RMQ(i,i+2

^j

)

!

M

⁰ ¹ ² ³ ⁴

0 1

5 2 3 4

6 7 8 9 10 11

(88)

Range Maximum Query (2)

3 5 1 7 1 6 10

S

⁹ ⁸ ⁷ ¹ ⁴

0 1 2 3 4 5 6 7 8 9 10 11

Query time: O(1)

M[i,j] = RMQ(i,i+2

^j

)

!

M

⁰ ¹ ² ³ ⁴

0 1

5 2 3 4

6 7 8 9 10 11

?

(89)

Range Maximum Query (2)

3 5 1 7 1 6 10

S

⁹ ⁸ ⁷ ¹ ⁴

0 1 2 3 4 5 6 7 8 9 10 11

Query time: O(1)

M[i,j] = RMQ(i,i+2

^j

)

!

M

⁰ ¹ ² ³ ⁴

0 1

5 2 3 4

6 7 8 9 10 11

?

9=1+2³

(90)

Range Maximum Query (2)

3 5 1 7 1 6 10

S

⁹ ⁸ ⁷ ¹ ⁴

0 1 2 3 4 5 6 7 8 9 10 11

Query time: O(1)

M[i,j] = RMQ(i,i+2

^j

)

!

M

⁰ ¹ ² ³ ⁴

0 1

5 2 3 4

6 7 8 9 10 11

?

9=1+2³

6

(91)

Range Maximum Query (2)

3 5 1 7 1 6 10

S

⁹ ⁸ ⁷ ¹ ⁴

0 1 2 3 4 5 6 7 8 9 10 11

Query time: O(1)

M[i,j] = RMQ(i,i+2

^j

)

!

M

⁰ ¹ ² ³ ⁴

0 1

5 2 3 4

6 7 8 9 10 11

Maximum of a interval is the

(92)

Range Maximum Query (2)

3 5 1 7 1 6 10

S

⁹ ⁸ ⁷ ¹ ⁴

0 1 2 3 4 5 6 7 8 9 10 11

Query time: O(1)

M[i,j] = RMQ(i,i+2

^j

)

!

M

⁰ ¹ ² ³ ⁴

0 1

5 2 3 4

6 7 8 9 10 11

RMQ(1,7) =

(93)

Range Maximum Query (2)

3 5 1 7 1 6 10

S

⁹ ⁸ ⁷ ¹ ⁴

0 1 2 3 4 5 6 7 8 9 10 11

Query time: O(1)

M[i,j] = RMQ(i,i+2

^j

)

!

M

⁰ ¹ ² ³ ⁴

0 1

5 2 3 4

6 7 8 9 10 11

argmax(S[M[1,1+2²]], S[M[7-2²,7]]) = 6 RMQ(1,7) =

(94)

Range Maximum Query (2)

3 5 1 7 1 6 10

S

⁹ ⁸ ⁷ ¹ ⁴

0 1 2 3 4 5 6 7 8 9 10 11

Query time: O(1)

M[i,j] = RMQ(i,i+2

^j

)

!

M

⁰ ¹ ² ³ ⁴

0 1

5 2 3 4

6 7 8 9 10 11

argmax(S[M[1,1+2²]], S[M[7-2²,7]]) = 6 RMQ(1,7) =

(95)

Range Maximum Query (2)

3 5 1 7 1 6 10

S

⁹ ⁸ ⁷ ¹ ⁴

0 1 2 3 4 5 6 7 8 9 10 11

Query time: O(1)

M[i,j] = RMQ(i,i+2

^j

)

!

M

⁰ ¹ ² ³ ⁴

0 1

5 2 3 4

6 7 8 9 10 11

3

argmax(S[M[1,1+2²]], S[M[7-2²,7]]) = 6 RMQ(1,7) =

(96)

Range Maximum Query (2)

3 5 1 7 1 6 10

S

⁹ ⁸ ⁷ ¹ ⁴

0 1 2 3 4 5 6 7 8 9 10 11

Query time: O(1)

M[i,j] = RMQ(i,i+2

^j

)

!

M

⁰ ¹ ² ³ ⁴

0 1

5 2 3 4

6 7 8 9 10 11

3

argmax(S[M[1,1+2²]], S[M[7-2²,7]]) = 6 RMQ(1,7) =

(97)

Range Maximum Query (2)

3 5 1 7 1 6 10

S

⁹ ⁸ ⁷ ¹ ⁴

0 1 2 3 4 5 6 7 8 9 10 11

Query time: O(1)

M[i,j] = RMQ(i,i+2

^j

)

!

M

⁰ ¹ ² ³ ⁴

0 1

5 2 3 4

6 7 8 9 10 11

3

argmax(S[M[1,1+2²]], S[M[7-2²,7]]) = 6 RMQ(1,7) =

6

(98)

Range Maximum Query (2)

3 5 1 7 1 6 10

S

⁹ ⁸ ⁷ ¹ ⁴

0 1 2 3 4 5 6 7 8 9 10 11

Query time: O(1)

M[i,j] = RMQ(i,i+2

^j

)

!

M

⁰ ¹ ² ³ ⁴

0 1

5 2 3 4

6 7 8 9 10 11

3

argmax(S[M[1,1+2²]], S[M[7-2²,7]]) = 6 RMQ(1,7) =

where len = log (j-i+1)

RMQ(i,j) = argmax(S[M[i,i+2^len]], S[M[j-2^len,j]])

6

(99)

Range Maximum Query (3)

3 5 1 7 1 6 10

S

⁹ ⁸ ⁷ ¹ ⁴

0 1 2 3 4 5 6 7 8 9 10 11

(100)

Range Maximum Query (3)

Space: O(n log n) bits Query time: O(log n)

3 5 1 7 1 6 10

S

⁹ ⁸ ⁷ ¹ ⁴

0 1 2 3 4 5 6 7 8 9 10 11

(101)

Range Maximum Query (3)

3 5 1 7 1 6 10

S

⁹ ⁸ ⁷ ¹ ⁴

0 1 2 3 4 5 6 7 8 9 10 11

log n

(102)

Range Maximum Query (3)

3 5 1 7 1 6 10

S

⁹ ⁸ ⁷ ¹ ⁴

0 1 2 3 4 5 6 7 8 9 10 11

log n

(103)

Range Maximum Query (3)

3 5 1 7 1 6 10

S

⁹ ⁸ ⁷ ¹ ⁴

0 1 2 3 4 5 6 7 8 9 10 11

log n

R

(104)

Range Maximum Query (3)

3 5 1 7 1 6 10

S

⁹ ⁸ ⁷ ¹ ⁴

0 1 2 3 4 5 6 7 8 9 10 11

log n

R

⁵

(105)

Range Maximum Query (3)

3 5 1 7 1 6 10

S

⁹ ⁸ ⁷ ¹ ⁴

0 1 2 3 4 5 6 7 8 9 10 11

log n

R

⁵ ⁷ ¹⁰ ⁷

(106)

Range Maximum Query (3)

3 5 1 7 1 6 10

S

⁹ ⁸ ⁷ ¹ ⁴

0 1 2 3 4 5 6 7 8 9 10 11

log n

R

⁵ ⁷ ¹⁰ ⁷

Use the previous solution on R!

Space: ? bits Query time: O(1)

(107)

Range Maximum Query (3)

3 5 1 7 1 6 10

S

⁹ ⁸ ⁷ ¹ ⁴

0 1 2 3 4 5 6 7 8 9 10 11

log n

R

⁵ ⁷ ¹⁰ ⁷

Space: O(n log n) bits Query time: O(1)

(108)

Range Maximum Query (3)

3 5 1 7 1 6 10

S

⁹ ⁸ ⁷ ¹ ⁴

0 1 2 3 4 5 6 7 8 9 10 11

log n

R

⁵ ⁷ ¹⁰ ⁷

RMQ(1,10) = ?

(109)

Range Maximum Query (3)

3 5 1 7 1 6 10

S

⁹ ⁸ ⁷ ¹ ⁴

0 1 2 3 4 5 6 7 8 9 10 11

log n

R

⁵ ⁷ ¹⁰ ⁷

RMQ(1,10) = ?

(110)

Range Maximum Query (3)

3 5 1 7 1 6 10

S

⁹ ⁸ ⁷ ¹ ⁴

0 1 2 3 4 5 6 7 8 9 10 11

log n

R

⁵ ⁷ ¹⁰ ⁷

RMQ(1,10) = ?

(111)

Range Maximum Query (3)

3 5 1 7 1 6 10

S

⁹ ⁸ ⁷ ¹ ⁴

0 1 2 3 4 5 6 7 8 9 10 11

log n

R

⁵ ⁷ ¹⁰ ⁷

RMQ(1,10) = ?

(112)

Range Maximum Query (3)

3 5 1 7 1 6 10

S

⁹ ⁸ ⁷ ¹ ⁴

0 1 2 3 4 5 6 7 8 9 10 11

log n

R

⁵ ⁷ ¹⁰ ⁷

RMQ(1,10) = ?

O(1) time

(113)

Range Maximum Query (3)

3 5 1 7 1 6 10

S

⁹ ⁸ ⁷ ¹ ⁴

0 1 2 3 4 5 6 7 8 9 10 11

log n

R

⁵ ⁷ ¹⁰ ⁷

RMQ(1,10) = ?

O(1) time

O(log n) time O(log n) time

(114)

Range Maximum Query (3)

3 5 1 7 1 6 10

S

⁹ ⁸ ⁷ ¹ ⁴

0 1 2 3 4 5 6 7 8 9 10 11

log n

R

⁵ ⁷ ¹⁰ ⁷

RMQ(1,10) = ?

O(1) time

(115)

Range Maximum Query (3)

3 5 1 7 1 6 10

S

⁹ ⁸ ⁷ ¹ ⁴

0 1 2 3 4 5 6 7 8 9 10 11

log n

R

⁵ ⁷ ¹⁰ ⁷

RMQ(1,10) = ?

O(1) time

O(1) time O(1) time

(116)

Range Maximum Query (3)

3 5 1 7 1 6 10

S

⁹ ⁸ ⁷ ¹ ⁴

0 1 2 3 4 5 6 7 8 9 10 11

log n

R

⁵ ⁷ ¹⁰ ⁷

RMQ(1,10) = ?

O(1) time

O(1) time O(1) time

(117)

D = { ab (7), bab (2), bca (1), cab (4), cac (1), cbac (6), cbba (2) } n = |D|, m total length of strings in D

7

2 1

4 1 6 2

ab b

ab ca

c

a b

ba ac

b c

Summary

(118)

D = { ab (7), bab (2), bca (1), cab (4), cac (1), cbac (6), cbba (2) } n = |D|, m total length of strings in D

7

2 1

4 1 6 2

ab b

ab ca

c

a b

ba ac

b c

Summary

Find the node “prefixed” by P

(119)

D = { ab (7), bab (2), bca (1), cab (4), cac (1), cbac (6), cbba (2) } n = |D|, m total length of strings in D

7

2 1

4 1 6 2

ab b

ab ca

c

a b

ba ac

b c

Summary

Find the node “prefixed” by P O(|P|) time

(120)

D = { ab (7), bab (2), bca (1), cab (4), cac (1), cbac (6), cbba (2) } n = |D|, m total length of strings in D

7

2 1

4 1 6 2

ab b

ab ca

c

a b

ba ac

b c

Summary

Find the node “prefixed” by P O(|P|) time O(m log σ + n log m) bits

(121)

D = { ab (7), bab (2), bca (1), cab (4), cac (1), cbac (6), cbba (2) } n = |D|, m total length of strings in D

7

2 1

4 1 6 2

ab b

ab ca

c

a b

ba ac

b c

Summary

Compute the top-k strings

(122)