Continuous lossless compression of streams of high-frequency multivariate financial market data

(1)

NTNU Norwegian University of Science and Technology Faculty of Information Technology and Electrical Engineering Department of Computer Science

Master ’s thesis

Olav Kaada

Continuous lossless compression of streams of high-frequency multivariate financial market data

Master’s thesis in Computer Science Supervisor: Svein Erik Bratsberg June 2020

(2)

(3)

Olav Kaada

Continuous lossless compression of streams of high-frequency

multivariate financial market data

Norwegian University of Science and Technology

Faculty of Information Technology and Electrical Engineering Department of Computer Science

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(15)

(16)

(17)

64

(18)

(19)

(20)

(21)

◦

D D = 1

D >1

N D

(22)

(23)

0 200 400 600 800 1000 1200 1400

N = 273793

(24)

(25)

(26)

N D > 0

Ar,c c r Ar,1

r D Ar,2, ..., Ar,D+1

A1,1, ..., A1,D+1, ..., AN,1, ..., AN,D+1

A1,1, ..., AN,1, ..., A1,D+1, ..., AN,D+1

(27)

δ_i =x_i−x_i−1

[x1,δ2 =x2−x1, ...,δN =xN −x_N−1]

xi =x1+

!i

j=2

δj

(28)

δ_i² =δi −δ_i−1 = (xi−x_i−1)−(x_i−1−x_i−2)

[δ1,δ²₂ =δ2−δ1, ...,δ_N² =δN −δN−1]

x_i =x_ref +iδ₁+

!i

j=2

(i−j+ 1)δ_j²

x_i =ax_i−1+bx_i−2+...+"

a b "

(29)

[0−15]

log2(16) = 4

32 log2(32) = 5

n >0

1 +log2(E) +"log2(n)#=b, E

b → E

(30)

log2(E) =N

(31)

64

(32)

−1

(33)

t₋1 t0

t1, ..., tn

96

(34)

(35)

(36)

(37)

(38)

(39)

−2⁸ 2⁸ −2¹⁶ 2¹⁶ −2³² 2³² −2⁶⁴ 2⁶⁴ 0.0

0.2 0.4 0.6 0.8 1.0

N = 1633158

64

(40)

−2² 2² −2⁴ 2⁴ −2⁸ 2⁸ −2¹⁶ 2¹⁶ 0.0

0.2 0.4 0.6 0.8 1.0

N = 3266316

(41)

−2¹ 2¹ −2² 2² −2⁴ 2⁴ −2⁸ 2⁸ 0.0

0.1 0.2 0.3 0.4

N = 3266316

(42)

(43)

T ime|Bid P rice|Bid Size|Of f er P rice|Of f er Size,

(44)

log2(64) = 6

(45)

log2(32) = 5

N N

N + 1

(46)

2, ..., N N

(47)

1.1M

(48)

(49)

10³ 1

2 3

10³

103

10³

103

64/2.7≈24

1/4 1/2 2.7

1 + 6 = 7

(50)

10³ 1

2 3

10³

103

10³

103

64/3.0 ≈ 21

1.5

(51)

10³ 2

4 6

10³

103

10³

103

32/6.6≈5

10³ 5

10

10³

103

10³

103

32/11.5≈3

(52)

10³ 2

4 6

10³

103

10³

103

32/5.0≈6

1.7

5 4

(53)

10³ 5

10

10³

103

10³

103

32/4.2 ≈ 8

(54)

10³ 1

2 3 4 5

10³

103

10³

103

192/4.1≈47

(55)

10³ 1

2 3 4 5

10³

103

10³

103

192/4.4≈ 44

(56)

85×10³

(57)

10³ 3.0

3.5 4.0 4.5 5.0

10³

103

10³

103

25×10³ 100×10³

4.4

Nblocks >1

(58)

10³ 3.0

3.5 4.0 4.5 5.0

10³

103

10³

103

(59)

D

(60)

(61)

(62)

(63)

(64)

(65)

(66)

x₁ =x₀+δ₁, x0

x1

x₂ =x₁ + (δ₁+δ₂²).

x3 =x2+ (δ1+δ²₂+δ₃²).

xi δ1+"i

j=2δ_j² xi−1

xi = (x0+δ1) + (δ1+δ₂²) + (δ1+δ₂²+δ²₃) +...+ (δ1+δ₂²+δ₃²+...+δ²_i),

xi =x0+iδ1+ (i−1)δ₂²+ (i−2)δ²₃+...+δ_i².

xi =x0+iδ1+

!i

j=2

(i−j+ 1)δ_j².

(67)

NTNU Norwegian University of Science and Technology Faculty of Information Technology and Electrical Engineering Department of Computer Science