text: Karin Schnass (cid:26) (cid:27) (cid:91) − − |(cid:104) (cid:105)| ≥ c c |(cid:104) (cid:105)| ≥ c c S S+1 S S+1 R := r s.t. φ , r or ψ , r , i i 3 6 i ∈ ∈ we see that both maxima are attained at I as long as σ / Σ and r / R. Using p p Hoeﬀding’s inequality we get that   (cid:32) (cid:33) (cid:12) (cid:88) (cid:12) (cid:18) (cid:19) (cid:12) (cid:12) (cid:12) (cid:12)  (cid:80) − − P (cid:104) (cid:105) ≤ t2 ≤ t2 σ c φ , φ > t 2 exp |(cid:104) (cid:105)| 2 exp , j(cid:54)=i j p(j) i j 2 j(cid:54)=i c2p(j) φi, φj 2 2µ2 (cid:16) (cid:17) (cid:54) P |(cid:104) (cid:105)| ≥ while from the proof of Proposition 6 we know that for ε = 0 we have (ω z , Φc i i i p,σ ≤ − − − − s) 2 exp s2 . Setting t = (c c )/6, s = (c c 3ε2 )/6 and using a union 2ε2 S S+1 S S+1 2 i bound then leads to (cid:32) (cid:0) (cid:1) (cid:33) (cid:18) (cid:19) − − − − P(Σ ) ≤ 2K exp − cS cS+1 32ε2 2 + 2K exp (cS cS+1)2 . (21) p 72ε2 72µ2 (cid:16) (cid:17) Since the r(i) are subgaussian with parameter ρ we have for any v = (v . . . v ) and 1 d t ≥ 0, P(|(cid:104)v, r(cid:105)| ≥ t) ≤ exp − t(cid:107)2 (cid:107) , see e.g. Vershynin (2012). Taking a union bound 2ρ2 v 2 2 over all φ , ψ with the corresponding choice for t then leads to the estimate i i (cid:32) (cid:0) (cid:1) (cid:33) (cid:32) (cid:0) (cid:1) (cid:33) − − 2 2 P ≤ − cS cS+1 − cS cS+1 (R) 2K exp + 2K exp . (22) 72ρ2 18ρ2 We now split the expectations over the sign and noise patterns for a ﬁxed p to get (cid:18)(cid:90) (cid:19) (cid:18)(cid:90) (cid:19) (cid:90) (cid:90) E E E(cid:88) E (cid:88) (∆ ) = ∆ dν + ∆ dν σ r p,σ,r σ ∈ p,σ,r r σ ∈ p,σ,r r r/R r R P P (cid:18)(cid:90) (cid:19) = (σ) ∆ dν + (σ) ∆ dν ∈ p,σ,r r ∈ p,σ,r r ∈ r/R ∈ r/R σ/Σp σ Σp E + ∆ dν . (23) σ ∈ p,σ,r r r R ± ∈ Next note that Σ is symmetric in the sense that we either have (σ , . . . , σ , . . . , σ ) ± p ∈ 1 i K Σ or (σ , . . . , σ , . . . , σ ) / Σ . Thus we get for the ﬁrst term in (23), p 1 i K p 26 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Karin

text: Schnass

text: c

text: c

text: c

text: c

text: S

text: S

text: R

text: r

text: s.t.

text: φ

text: r

text: or

text: ψ

text: r

text: i

text: i

text: i

text: we

text: see

text: that

text: both

text: maxima

text: are

text: attained

text: at

text: I

text: as

text: long

text: as

text: σ

text: Σ

text: and

text: r

text: R.

text: Using

text: p

text: p

text: Hoeﬀding’s

text: inequality

text: we

text: get

text: that

text: P

text: σ

text: c

text: φ

text: φ

text: t

text: exp

text: exp

text: j

text: p(j)

text: i

text: j

text: φi,

text: φj

text: P

text: while

text: from

text: the

text: proof

text: of

text: Proposition

text: we

text: know

text: that

text: for

text: ε

text: we

text: have

text: (ω

text: z

text: Φc

text: i

text: i

text: i

text: p,σ

text: s)

text: exp

text: Setting

text: t

text: (c

text: c

text: s

text: (c

text: c

text: and

text: using

text: a

text: union

text: S

text: S

text: i

text: bound

text: then

text: leads

text: to

text: P(Σ

text: exp

text: cS

text: exp

text: (cS

text: p

text: Since

text: the

text: r(i)

text: are

text: subgaussian

text: with

text: parameter

text: ρ

text: we

text: have

text: for

text: any

text: v

text: (v

text: v

text: and

text: d

text: t

text: t)

text: exp

text: see

text: e.g.

text: Vershynin

text: Taking

text: a

text: union

text: bound

text: v

text: over

text: all

text: φ

text: ψ

text: with

text: the

text: corresponding

text: choice

text: for

text: t

text: then

text: leads

text: to

text: the

text: estimate

text: i

text: i

text: P

text: cS

text: cS

text: (R)

text: exp

text: exp

text: We

text: now

text: split

text: the

text: expectations

text: over

text: the

text: sign

text: and

text: noise

text: patterns

text: for

text: a

text: ﬁxed

text: p

text: to

text: get

text: E

text: E

text: E

text: dν

text: dν

text: σ

text: r

text: p,σ,r

text: σ

text: p,σ,r

text: r

text: σ

text: p,σ,r

text: r

text: r/R

text: r

text: R

text: P

text: P

text: (σ)

text: dν

text: (σ)

text: dν

text: p,σ,r

text: r

text: p,σ,r

text: r

text: r/R

text: r/R

text: σ/Σp

text: σ

text: Σp

text: E

text: dν

text: σ

text: p,σ,r

text: r

text: r

text: R

text: Next

text: note

text: that

text: Σ

text: is

text: symmetric

text: in

text: the

text: sense

text: that

text: we

text: either

text: have

text: (σ

text: σ

text: σ

text: p

text: i

text: K

text: Σ

text: or

text: (σ

text: σ

text: σ

text: Σ

text: Thus

text: we

text: get

text: for

text: the

text: ﬁrst

text: term

text: in

text: p

text: i

text: K

text: p

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: Karin Schnass (cid:0) (cid:1) √ √ (cid:0) (cid:1) Note that for the noise-free signal model we can replace B + 1 by B in the last √ √ expression. By averaging over n we get that the mapping in question is Lipschitz with constant S (cid:12) B + 1 in the noisy and S B in the noise(cid:12)-free case, that is (cid:12)(cid:12) (cid:88) (cid:88) (cid:12)(cid:12) (cid:0) (cid:1) (cid:12) (cid:12) (cid:12) (cid:12) √ N N 1 (cid:107) (cid:107) − 1 (cid:107) (cid:107) ≤ max Ψ(cid:63)y max Ψ¯ (cid:63)y d(Ψ, Ψ¯ )S B + 1 . N |I|=S I n 1 N |I|=S I n 1 n=1 n=1 (cid:0) (cid:1) To show that the averaged sums concentrate around their expectations we use our (cid:107) (cid:107) − (cid:107) (cid:107) favourite tool Hoeﬀd√ing’s inequality. Set X √= max| | Φ(cid:63)y max| | Ψ(cid:63)y , then | | ≤ | | ≤ n I =S I n 1 I =S I n 1 we (cid:32)ha(cid:12)(cid:12)ve (cid:88)Xn (cid:18) εS B+1 , resp. Xn εS(cid:19) B in(cid:18)the noise-free case, and get th(cid:19)e(cid:12)(cid:12)estim(cid:33)ate (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) N P 1 (cid:107) (cid:107) − (cid:107) (cid:107) − E (cid:107)(cid:32) (cid:107) − (cid:107) (cid:33) (cid:107) ≥ max Φ(cid:63)y max Ψ(cid:63)y max Φ(cid:63)y max Ψ(cid:63)y 2t N n=1 |I|=S I n 1 |I|=S I n 1 |I|=S I 1 1(cid:0) |I|=S (cid:1) I 1 1 − ≤ √2Nt2 2 exp . ε2S2 B + 1 2 ≤ Next we need to choose a δ-net for all perturbations Ψ with d(Φ, Ψ) ε , that is a N ∈ N max ≤ ﬁnite set of perturbations such that for every Ψ we can ﬁnd Ψ¯ with d(Ψ, Ψ¯ ) δ. Recalling the parametrisation of all ε-perturbations from the proof of Proposition 6, we see (cid:0) (cid:1) that the space we need to cover is included in the product of K balls with radius ε in max dimension d. From e.g. Lemma 2 in Vershynin (2012) we know that for the d dimensional N N ≤ ball of radius ε we can ﬁnd a δ-net satisfying (cid:93) ε + 2εmax d, so for our space max Nd d max δ of ε-perturbations we can ﬁnd (cid:18)a δ-net satis(cid:19)fying (cid:18) (cid:19) N ≤ 2ε Kd ≤ 3ε Kd max max (cid:93) ε + . max δ δ Taking a union bound we can now estimate the probability that we have concentration for(cid:32)all perturba(cid:12)tions in the net as (cid:12) (cid:88) (cid:18) (cid:19) (cid:12) (cid:12) (cid:12) N P ∃ ∈ N 1 (cid:107) (cid:107) − (cid:107) (cid:107) (cid:12) (cid:33) Ψ : max Φ(cid:63)y max Ψ(cid:63)y (cid:18) (cid:19)(cid:12) N |I|=S I n 1 |I|=S I n 1 (cid:12) n=1 (cid:12) (cid:12) (cid:18) (cid:19) − E m(cid:32)ax (cid:107)Φ(cid:63)y (cid:107) − max (cid:107)(cid:33)Ψ(cid:63)y (cid:107) ≥ 2t | | I 1 1 | | I 1 1 I =S (cid:0) I =S(cid:1) − ≤ 3ε Kd 2√Nt2 max 2 exp . δ ε2 S2 B + 1 2 max 30 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Karin

label: paragraph

text: Schnass

text: Note

text: that

text: for

text: the

text: noise-free

text: signal

text: model

text: we

text: can

text: replace

text: B

text: by

text: B

text: in

text: the

text: last

text: expression.

text: By

text: averaging

text: over

text: n

text: we

text: get

text: that

text: the

text: mapping

text: in

text: question

text: is

text: Lipschitz

text: with

text: constant

text: S

label: equation

text: B

text: in

text: the

text: noisy

text: and

text: S

text: B

text: in

text: the

text: case,

text: that

text: is

text: N

text: N

text: max

text: max

text: Ψ¯

text: d(Ψ,

text: Ψ¯

text: )S

text: B

text: N

text: |I|=S

text: I

text: n

text: N

text: |I|=S

text: I

text: n

text: To

text: show

text: that

text: the

text: averaged

text: sums

text: concentrate

text: around

text: their

text: expectations

text: we

text: use

text: our

text: favourite

text: tool

text: Hoeﬀd√ing’s

text: inequality.

text: Set

text: X

text: max|

text: max|

text: then

text: n

text: I

text: =S

text: I

text: n

text: I

text: =S

text: I

text: n

text: we

text: εS

text: resp.

text: Xn

text: B

text: noise-free

text: case,

text: and

text: get

text: N

text: P

text: E

text: max

text: max

text: max

text: max

text: N

text: |I|=S

text: I

text: n

text: |I|=S

text: I

text: n

text: |I|=S

text: I

text: |I|=S

text: I

text: exp

text: B

text: Next

text: we

text: need

text: to

text: choose

text: a

text: δ-net

text: for

text: all

text: perturbations

text: Ψ

text: with

text: d(Φ,

text: Ψ)

text: ε

text: that

text: is

text: a

text: N

text: N

text: max

text: ﬁnite

text: set

text: of

text: perturbations

text: such

text: that

text: for

text: every

text: Ψ

text: we

text: can

text: ﬁnd

text: Ψ¯

text: with

text: d(Ψ,

text: Ψ¯

text: δ.

text: Recalling

text: the

text: parametrisation

text: of

text: all

text: ε-perturbations

text: from

text: the

text: proof

text: of

text: Proposition

text: we

text: see

text: that

text: the

text: space

text: we

text: need

text: to

text: cover

text: is

text: included

text: in

text: the

text: product

text: of

text: K

text: balls

text: with

text: radius

text: ε

text: in

text: max

text: dimension

text: d.

text: From

text: e.g.

text: Lemma

text: in

text: Vershynin

text: we

text: know

text: that

text: for

text: the

text: d

text: dimensional

text: N

text: N

text: ball

text: of

text: radius

text: ε

text: we

text: can

text: ﬁnd

text: a

text: δ-net

text: satisfying

text: ε

text: d,

text: so

text: for

text: our

text: space

text: max

text: Nd

text: d

text: max

text: δ

text: of

text: ε-perturbations

text: we

text: can

text: ﬁnd

text: δ-net

text: N

text: 2ε

text: Kd

text: 3ε

text: Kd

text: max

text: max

text: ε

text: max

text: δ

text: δ

text: Taking

text: a

text: union

text: bound

text: we

text: can

text: now

text: estimate

text: the

text: probability

text: that

text: we

text: have

text: concentration

text: in

text: the

text: net

text: as

text: N

text: P

text: N

text: Ψ

text: max

text: max

text: N

text: |I|=S

text: I

text: n

text: |I|=S

text: I

text: n

text: E

text: max

text: I

text: I

text: I

text: =S

text: I

text: 3ε

text: Kd

text: max

text: exp

text: δ

text: ε2

text: B

text: max

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: Karin Schnass with parameter ρ and assume that the signals are generated according to the noisy signal ≥ ≥ ≥ ≥ model in (9). If there exists β > 0 such that for c (x) c (x) . . . c (x) 0 1 2 K the non-increasing rearrangement of the absolute values of the components of x we have − ≥ c (x) c (x) β almost surely and S S+1 (cid:112) √ { } ≤ β 112K2S( B + 1) max µ,(cid:0)ρ (cid:1) for a = , (10) 72(log a + log log a) Crβ(c¯1 + . . . + c¯S) E (cid:107) (cid:107) − E where C = (1 + r 2) 1/2 and c¯ := (c (x)), then there is a local maximum of r r 2 i x i (5) at Ψ˜ satisfying, (cid:18) (cid:19) √ − ≤ 12SK2 B β2 d(Ψ˜ , Φ) exp { } . (11) C (c¯ + . . . + c¯ ) 72 max µ2, ρ2 r 1 S Proof idea As outlined at the beginning of the section the main ingredient we have to add to the proof idea of Theorem 2 is a probabilistic argument to substitute the condition guaranteeing that the S largest responses of the generating dictionary are I . Due to p concentration of measure we get that for most sign sequences, and therefore most signals, the maximum is still attained at I . Moreover the gap to the remaining responses is actually p large enough to accommodate relatively high levels of noise and/or perturbations. The detailed proof can be found in Appendix . (cid:0) (cid:1) Let us make some observations about the last result. First, we want to point out that for sub-gaussian noise with parameter ρ, the quantity E (cid:107) (cid:107) − C = (1 + r 2) 1/2 in the statement above is well behaved. If for example the r(i) r r 2 ± − are iid Bernoulli-variables, that is P (r(i) = ρ) = 1, we have C = (1+dρ2) 1/2. In general 2 r we have the following estimate due for instance to Theorem 1 in Hsu et al. (2012). Since we have (cid:16) (cid:17) √ P (cid:107) (cid:107) ≥ ≤ − (cid:0) x 2 ρ2(cid:1)(d + 2 dt + 2t e t, 2 P (cid:107) (cid:107) ≥ ≤ − setting t = d, we get x 2(cid:32) 5dρ2 e(cid:33)d, which leads to 2 (cid:112) (cid:112) − − E 1 ≥ (1 e d) r (cid:107) (cid:107) . 1 + r 2 1 + 5dρ2 2 Also to illustrate the result we again specialise it to the most favourable case of exactly − S-sparse signals with balanced coeﬃcients, that is c (x) = S 1/2. Assuming white Gaussian S noise with variance ρ2 we see that identiﬁcation is possible even for expected signal to noise G ratios of the order O(S ), that is d E (cid:107) (cid:107) ( Φx 2) (cid:38) S E (cid:107) (cid:107) 2 . ( r 2) d 2 10 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Karin

text: Schnass

text: with

text: parameter

text: ρ

text: and

text: assume

text: that

text: the

text: signals

text: are

text: generated

text: according

text: to

text: the

text: noisy

text: signal

text: model

text: in

text: If

text: there

text: exists

text: β

text: such

text: that

text: for

text: c

text: (x)

text: c

text: (x)

text: c

text: (x)

text: K

text: the

text: non-increasing

text: rearrangement

text: of

text: the

text: absolute

text: values

text: of

text: the

text: components

text: of

text: x

text: we

text: have

text: c

text: (x)

text: c

text: (x)

text: β

text: almost

text: surely

text: and

text: S

text: β

text: B

text: max

text: for

text: a

text: a

text: log

text: log

text: a)

text: c¯S)

text: E

text: E

text: where

text: C

text: r

text: and

text: c¯

text: (c

text: (x)),

text: then

text: there

text: is

text: a

text: local

text: maximum

text: of

text: r

text: r

text: i

text: x

text: i

text: at

text: Ψ˜

text: satisfying,

text: B

text: β2

text: d(Ψ˜

text: Φ)

text: exp

text: C

text: (c¯

text: c¯

text: max

text: ρ2

text: r

text: S

text: Proof

text: idea

text: As

text: outlined

text: at

text: the

text: beginning

text: of

text: the

text: section

text: the

text: main

text: ingredient

text: we

text: have

text: to

text: add

text: to

text: the

text: proof

text: idea

text: of

text: Theorem

text: is

text: a

text: probabilistic

text: argument

text: to

text: substitute

text: the

text: condition

text: guaranteeing

text: that

text: the

text: S

text: largest

text: responses

text: of

text: the

text: generating

text: dictionary

text: are

text: I

text: Due

text: to

text: p

text: concentration

text: of

text: measure

text: we

text: get

text: that

text: for

text: most

text: sign

text: sequences,

text: and

text: therefore

text: most

text: signals,

text: the

text: maximum

text: is

text: still

text: attained

text: at

text: I

text: Moreover

text: the

text: gap

text: to

text: the

text: remaining

text: responses

text: is

text: actually

text: p

text: large

text: enough

text: to

text: accommodate

text: relatively

text: high

text: levels

text: of

text: noise

text: and/or

text: perturbations.

text: The

text: detailed

text: proof

text: can

text: be

text: found

text: in

text: Appendix

text: Let

text: us

text: make

text: some

text: observations

text: about

text: the

text: last

text: result.

text: First,

text: we

text: want

text: to

text: point

text: out

text: that

text: for

text: sub-gaussian

text: noise

text: with

text: parameter

text: ρ,

text: the

text: quantity

text: E

text: C

text: r

text: in

text: the

text: statement

text: above

text: is

text: well

text: behaved.

text: If

text: for

text: example

text: the

text: r(i)

text: r

text: r

text: are

text: iid

text: Bernoulli-variables,

text: that

text: is

text: P

text: (r(i)

text: ρ)

text: we

text: have

text: C

text: In

text: general

text: r

text: we

text: have

text: the

text: following

text: estimate

text: due

text: for

text: instance

text: to

text: Theorem

text: in

text: Hsu

text: et

text: al.

text: Since

text: we

text: have

text: P

text: x

text: dt

text: e

text: t,

text: P

text: setting

text: t

text: d,

text: we

text: get

text: x

text: which

text: leads

text: to

text: E

text: e

text: d)

text: r

text: r

text: Also

text: to

text: illustrate

text: the

text: result

text: we

text: again

text: specialise

text: it

text: to

text: the

text: most

text: favourable

text: case

text: of

text: exactly

text: S-sparse

text: signals

text: with

text: balanced

text: coeﬃcients,

text: that

text: is

text: c

text: (x)

text: S

text: Assuming

text: white

text: Gaussian

text: S

text: noise

text: with

text: variance

text: ρ2

text: we

text: see

text: that

text: identiﬁcation

text: is

text: possible

text: even

text: for

text: expected

text: signal

text: to

text: noise

text: G

text: ratios

text: of

text: the

text: order

text: O(S

text: that

text: is

text: d

text: E

text: Φx

text: S

text: E

text: r

text: d

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: Gor´ın and Schr¨oder 17 is essentially the extension of coalition logic with ﬁxpoint operators (its actual notation is slightly diﬀerent) [2]. The conjunctive fragment of the AMC can by ∨ ¬ deﬁned in the obvious way excluding , , and µ. In this fragment, we can still express ‘always’ formulas from alternating-time temporal logic (ATL) such as (cid:104)(cid:104) (cid:105)(cid:105) C (cid:50)φ, which is read ‘coalition C can maintain φ forever’, and is equivalent ∧ to the ﬁxpoint formula νx. (φ [C]x). We proceed to show that if Λ admits one-step wsi models, we also obtain wsi models for conjunctive Λ-ν-formulas. We exploit the fact that any such sentence can be put, in polynomial time, in a shallow normal form, i.e. without nested occurrences of ν (using Bekiˇc’s law [3]) and without nesting of modal operators (using abbreviations for subformulas in analogy to standard TBox normalizations [4]). Thus, let φ = ν(x ; x , . . . , x )(φ ; φ , . . . , φ ) be a shallow sentence. We 0 1 n 0 1 n shall assume, for each conjunctive one-step Λ-formula ψ over V = ∆, a ﬁxed one-step wsi model (X , τ , t ) which we then call the one-step wsi model ψ ψ ψ ⊆ P for ψ. We assume w.l.o.g. that X (V (ψ)), where V (ψ) is the set of ψ { ∈ (cid:86) ∈ } variables mentioned in ψ, and τ (x) = A X : x A (Remark 4.9). We ψ ψ P ⊆ then construct the carrier X of C as a subset of (V ). For A V , we let φ φ φ A denote the conjunctive one-step formula given by ∈ φ . Then, X is the P { } xi A i ⊆ φ smallest subset of (V ) containing r = x such that X X , for each ∈ φ 0 φA φ A X . We deﬁne a T-coalgebra structure ξ on X by ξ (A) = T(i )t , φ → φ φ φ A φA where i is the inclusion X (cid:44) X . A φA φ Theorem 6.5 If Λ admits one-step wsi models, then for every shallow Lν(Λ)- sentence φ, (C , r ) as constructed above is a wsi model. φ φ Proof (Sketch) Let φ have the form ν(x ; x , . . . x ).(φ ; φ , . . . , φ ), so V = { } |0 1 n 0 1 | n x , . . . x . We have to show that (i) r = φ and (ii) that if d = φ, then 0 n → φ Cφ D r Sd for some simulation S : C D (Remark 4.2). φ (cid:74) (cid:75) φ V { ∈ ∈ } (i): By coinduction – taking (x ) = A X : x A , one shows that V(cid:74) (cid:75) ⊆ ∈ i φ i V ⊆ (x ) φ V for all x V . The gfp property of φ then implies (x ) i i Cφ, ∈ V i 0 φ , and clearly r (x ). φ 0 (ii): For i = 0, . . . n, let φ(i) denote the formula obtained by projecting the i-th component of φ: φ(i) =ν(x ; x . . . x − , x . . . x ).(φ ; φ . . . φ − , φ . . .), i 0 i 1 i+1 n i 0 i 1 i+1 | so in particular φ(0⊆) = φ×. Assume d =D φ(cid:94)for some coalgebra D = (Y, ζ). Deﬁne a relation S X Y by φ ⇐⇒ | ASy y = φ(i). D ∈ xi A { } Then clearly r Sd, for by deﬁnition r = x and φ(0) = φ. One can show φ φ 0 that S is a Λ-simulation. (cid:50) Clearly, all conjunctive logics listed as having one-step wsi models in the ex- amples of Sec. have wsi models when extended with greatest ﬁxpoints, in

text: Gor´ın

text: and

text: Schr¨oder

text: is

text: essentially

text: the

text: extension

text: of

text: coalition

text: logic

text: with

text: ﬁxpoint

text: operators

text: (its

text: actual

text: notation

text: is

text: slightly

text: diﬀerent)

text: The

text: conjunctive

text: fragment

text: of

text: the

text: AMC

text: can

text: by

text: deﬁned

text: in

text: the

text: obvious

text: way

text: excluding

text: and

text: µ.

text: In

text: this

text: fragment,

text: we

text: can

text: still

text: express

text: ‘always’

text: formulas

text: from

text: alternating-time

text: temporal

text: logic

text: (ATL)

text: such

text: as

text: C

text: which

text: is

text: read

text: ‘coalition

text: C

text: can

text: maintain

text: φ

text: forever’,

text: and

text: is

text: equivalent

text: to

text: the

text: ﬁxpoint

text: formula

text: νx.

text: (φ

text: [C]x).

text: We

text: proceed

text: to

text: show

text: that

text: if

text: Λ

text: admits

text: one-step

text: wsi

text: models,

text: we

text: also

text: obtain

text: wsi

text: models

text: for

text: conjunctive

text: Λ-ν-formulas.

text: We

text: exploit

text: the

text: fact

text: that

text: any

text: such

text: sentence

text: can

text: be

text: put,

text: in

text: polynomial

text: time,

text: in

text: a

text: shallow

text: normal

text: form,

text: i.e.

text: without

text: nested

text: occurrences

text: of

text: ν

text: (using

text: Bekiˇc’s

text: law

text: and

text: without

text: nesting

text: of

text: modal

text: operators

text: (using

text: abbreviations

text: for

text: subformulas

text: in

text: analogy

text: to

text: standard

text: TBox

text: normalizations

text: Thus,

text: let

text: φ

text: ν(x

text: x

text: x

text: )(φ

text: φ

text: φ

text: be

text: a

text: shallow

text: sentence.

text: We

text: n

text: n

text: shall

text: assume,

text: for

text: each

text: conjunctive

text: one-step

text: Λ-formula

text: ψ

text: over

text: V

text: a

text: ﬁxed

text: one-step

text: wsi

text: model

text: (X

text: τ

text: t

text: which

text: we

text: then

text: call

text: the

text: one-step

text: wsi

text: model

text: ψ

text: ψ

text: ψ

text: P

text: for

text: ψ.

text: We

text: assume

text: w.l.o.g.

text: that

text: X

text: (V

text: (ψ)),

text: where

text: V

text: (ψ)

text: is

text: the

text: set

text: of

text: ψ

text: variables

text: mentioned

text: in

text: ψ,

text: and

text: τ

text: (x)

text: A

text: X

text: x

text: A

text: (Remark

text: We

text: ψ

text: ψ

text: P

text: then

text: construct

text: the

text: carrier

text: X

text: of

text: C

text: as

text: a

text: subset

text: of

text: (V

text: For

text: A

text: V

text: we

text: let

text: φ

text: φ

text: φ

text: A

text: denote

text: the

text: conjunctive

text: one-step

text: formula

text: given

text: by

text: φ

text: Then,

text: X

text: is

text: the

text: P

text: xi

text: A

text: i

text: φ

text: smallest

text: subset

text: of

text: (V

text: containing

text: r

text: x

text: such

text: that

text: X

text: X

text: for

text: each

text: φ

text: φA

text: φ

text: A

text: X

text: We

text: deﬁne

text: a

text: T-coalgebra

text: structure

text: ξ

text: on

text: X

text: by

text: ξ

text: (A)

text: T(i

text: )t

text: φ

text: φ

text: φ

text: φ

text: A

text: φA

text: where

text: i

text: is

text: the

text: inclusion

text: X

text: X

text: A

text: φA

text: φ

text: Theorem

text: If

text: Λ

text: admits

text: one-step

text: wsi

text: models,

text: then

text: for

text: every

text: shallow

text: Lν(Λ)-

text: sentence

text: φ,

text: (C

text: r

text: as

text: constructed

text: above

text: is

text: a

text: wsi

text: model.

text: φ

text: φ

text: Proof

text: (Sketch)

text: Let

text: φ

text: have

text: the

text: form

text: ν(x

text: x

text: x

text: ).(φ

text: φ

text: φ

text: so

text: V

text: n

text: n

text: x

text: x

text: We

text: have

text: to

text: show

text: that

text: (i)

text: r

text: φ

text: and

text: (ii)

text: that

text: if

text: d

text: φ,

text: then

text: n

text: φ

text: Cφ

text: D

text: r

text: Sd

text: for

text: some

text: simulation

text: S

text: C

text: D

text: (Remark

text: φ

text: φ

text: V

text: (i):

text: By

text: coinduction

text: taking

text: (x

text: A

text: X

text: x

text: A

text: one

text: shows

text: that

text: i

text: φ

text: i

text: V

text: (x

text: φ

text: V

text: for

text: all

text: x

text: V

text: The

text: gfp

text: property

text: of

text: φ

text: then

text: implies

text: (x

text: i

text: i

text: Cφ,

text: V

text: i

text: φ

text: and

text: clearly

text: r

text: (x

text: φ

text: (ii):

text: For

text: i

text: n,

text: let

text: φ(i)

text: denote

text: the

text: formula

text: obtained

text: by

text: projecting

text: the

text: i-th

text: component

text: of

text: φ:

text: φ(i)

text: =ν(x

text: x

text: x

text: x

text: x

text: ).(φ

text: φ

text: φ

text: φ

text: i

text: i

text: n

text: i

text: i

text: so

text: in

text: particular

text: φ×.

text: Assume

text: d

text: =D

text: some

text: coalgebra

text: D

text: (Y,

text: ζ).

text: Deﬁne

text: a

text: relation

text: S

text: X

text: Y

text: by

text: φ

text: ASy

text: y

text: φ(i).

text: D

text: xi

text: A

text: Then

text: clearly

text: r

text: Sd,

text: for

text: by

text: deﬁnition

text: r

text: x

text: and

text: φ.

text: One

text: can

text: show

text: φ

text: φ

text: that

text: S

text: is

text: a

text: Λ-simulation.

text: Clearly,

text: all

text: conjunctive

text: logics

text: listed

text: as

text: having

text: one-step

text: wsi

text: models

text: in

text: the

text: ex-

text: amples

text: of

text: Sec.

text: have

text: wsi

text: models

text: when

text: extended

text: with

text: greatest

text: ﬁxpoints,

text: in


text: 1 [12] A. Yedla, Y.-Y. Jian, P. S. Nguyen, and H. D. Pﬁster, “A simple A=0.5 proof of threshold saturation for coupled scalar recursions,” in 7th 0.95 A=0 International Symposium on Turbo Codes and Iterative Information A=-0.2 Processing (ISTC). IEEE, 2012, pp. 51–55. 0.9 A=-0.5 [13] D. L. Donoho, A. Maleki, and A. Montanari, “Message-passing algo- 0.85 rithms for compressed sensing,” Proc. Natl. Acad. Sci., vol. 106, no. 45, pp. 18914–18919, 2009. 0.8 [14] S. Rangan, “Generalized approximate message passing for estimation (cid:95)s 0.75 with random linear mixing,” in IEEE International Symposium on Information Theory Proceedings (ISIT), 2011, pp. 2168 –2172. 0.7 [15] M. Bayati, M. Lelarge, and A. Montanari, “Universality in polytope phase transitions and message passing algorithms,” arXiv preprint 0.65 arXiv:1207.7321, 2012. 0.6 [16] S. Kudekar, T. Richardson, and R. Urbanke, “Wave-like solutions of general one-dimensional spatially coupled systems,” arXiv preprint 0.55 arXiv:1208.5273, 2012. 2 4 6 8 10 12 14 16 18 20 [17] D. L. Donoho and J. Tanner, “Sparse nonnegative solution of underde- w /w termined linear equations by linear programming,” Proceedings of the s National Academy of Sciences of the United States of America, vol. 102, no. 27, pp. 9446–9451, 2005. [18] S. H. Hassani, N. Macris, and R. Urbanke, “Chains of mean-ﬁeld Fig. 6. The propagation phase diagram as a function of the seed features models,” Journal of Statistical Mechanics: Theory and Experiment, vol. for different values of t−he angular coefﬁcient in the interaction function g(x), 2012, no. 02, p. P02011, 2012. with ρ = 0.4, ∆ = 10 12, αb = 0.5, w = 1 and L = 400. [19] F. Caltagirone, S. Franz, R. Morris, and L. Zdeborova´, “Dynam- ics and termination cost of spatially coupled mean-ﬁeld models,” arXiv:1310.2121v1, 2013. ACKNOWLEDGMENT This work has been supported in part by the ERC under the European Union’s 7th Framework Programme Grant Agree- ment 307087-SPARCS, and by the project TASC of the Labex “PALM.” REFERENCES [1] A. Jimenez Felstrom and K. Zigangirov, “Time-varying periodic convo- lutional codes with low-density parity-check matrix,” IEEE Transactions on Information Theory, vol. 45, no. 6, pp. 2181 –2191, 1999. [2] M. Lentmaier, A. Sridharan, K. S. Zigangirov, and D. Costello, “Ter- minated ldpc convolutional codes with thresholds close to capacity,” in Information Theory, 2005. ISIT 2005. Proceedings. International Symposium on. IEEE, 2005, pp. 1372–1376. [3] M. Lentmaier, A. Sridharan, D. J. Costello, and K. S. Zigangirov, “Iterative decoding threshold analysis for ldpc convolutional codes,” IEEE Transactions on Information Theory, vol. 56, no. 10, pp. 5274– 5289, 2010. [4] S. Kudekar, T. J. Richardson, and R. L. Urbanke, “Threshold saturation via spatial coupling: Why convolutional ldpc ensembles perform so well over the bec,” IEEE Transactions on Information Theory, vol. 57, no. 2, pp. 803–834, 2011. [5] S. Kudekar, T. Richardson, and R. Urbanke, “Spatially coupled ensem- bles universally achieve capacity under belief propagation,” in Informa- tion Theory Proceedings (ISIT), 2012 IEEE International Symposium on. IEEE, 2012, pp. 453–457. [6] D. L. Donoho, “Compressed sensing,” IEEE Trans. Inform. Theory, vol. 52, p. 1289, 2006. [7] E. J. Cande`s and M. B. Wakin, “An introduction to compressive sampling,” IEEE Signal Processing Magazine, vol. 25, no. 2, pp. 21–30, Mar. 2008. [8] S. Kudekar and H. Pﬁster, “The effect of spatial coupling on compressive sensing,” in Communication, Control, and Computing (Allerton), 2010, pp. 347–353. [9] F. Krzakala, M. Me´zard, F. Sausset, Y. Sun, and L. Zdeborova´, “Sta- tistical physics-based reconstruction in compressed sensing,” Phys. Rev. X, vol. 2, p. 021005, 2012. [10] F. Krzakala, M. Me´zard, F. Sausset, Y. Sun, and L. Zdeborova´, “Probabilistic reconstruction in compressed sensing: Algorithms, phase diagrams, and threshold achieving matrices,” J. Stat. Mech., p. P08009, 2012. [11] D. L. Donoho, A. Javanmard, and A. Montanari, “Information- theoretically optimal compressed sensing via spatial coupling and ap- proximate message passing,” in Proc. of the IEEE Int. Symposium on Information Theory (ISIT), 2012. ##LTFigure##

font: default

label: reference

text: A.

text: Yedla,

text: Y.-Y.

text: Jian,

text: P.

text: S.

text: Nguyen,

text: and

text: H.

text: D.

text: Pﬁster,

text: “A

text: simple

text: proof

text: of

text: threshold

text: saturation

text: for

text: coupled

text: scalar

text: recursions,”

text: in

text: International

text: Symposium

text: on

text: Turbo

text: Codes

text: and

text: Iterative

text: Information

text: Processing

text: (ISTC).

text: IEEE,

text: pp.

text: D.

text: L.

text: Donoho,

text: A.

text: Maleki,

text: and

text: A.

text: Montanari,

text: “Message-passing

text: algo-

text: rithms

text: for

text: compressed

text: sensing,”

text: Proc.

text: Natl.

text: Acad.

text: Sci.,

text: vol.

text: no.

text: pp.

text: S.

text: Rangan,

text: “Generalized

text: approximate

text: message

text: passing

text: for

text: estimation

text: with

text: random

text: linear

text: mixing,”

text: in

text: IEEE

text: International

text: Symposium

text: on

text: Information

text: Theory

text: Proceedings

text: (ISIT),

text: pp.

text: M.

text: Bayati,

text: M.

text: Lelarge,

text: and

text: A.

text: Montanari,

text: “Universality

text: in

text: polytope

text: phase

text: transitions

text: and

text: message

text: passing

text: algorithms,”

text: arXiv

text: preprint

text: S.

text: Kudekar,

text: T.

text: Richardson,

text: and

text: R.

text: Urbanke,

text: “Wave-like

text: solutions

text: of

text: general

text: one-dimensional

text: spatially

text: coupled

text: systems,”

text: arXiv

text: preprint

text: D.

text: L.

text: Donoho

text: and

text: J.

text: Tanner,

text: “Sparse

text: nonnegative

text: solution

text: of

text: underde-

text: w

text: /w

text: termined

text: linear

text: equations

text: by

text: linear

text: programming,”

text: Proceedings

text: of

text: the

text: s

text: National

text: Academy

text: of

text: Sciences

text: of

text: the

text: United

text: States

text: of

text: America,

text: vol.

text: no.

text: pp.

text: S.

text: H.

text: Hassani,

text: N.

text: Macris,

text: and

text: R.

text: Urbanke,

text: “Chains

text: of

text: mean-ﬁeld

text: Fig.

text: The

text: propagation

text: phase

text: diagram

text: as

text: a

text: function

text: of

text: the

text: seed

text: features

text: models,”

text: Journal

text: of

text: Statistical

text: Mechanics:

text: Theory

text: and

text: Experiment,

text: vol.

text: for

text: different

text: values

text: of

text: t−he

text: angular

text: coefﬁcient

text: in

text: the

text: interaction

text: function

text: g(x),

text: no.

text: p.

text: with

text: ρ

text: αb

text: w

text: and

text: L

text: F.

text: Caltagirone,

text: S.

text: Franz,

text: R.

text: Morris,

text: and

text: L.

text: Zdeborova´,

text: “Dynam-

text: ics

text: and

text: termination

text: cost

text: of

text: spatially

text: coupled

text: mean-ﬁeld

text: models,”

text: ACKNOWLEDGMENT

text: This

text: work

text: has

text: been

text: supported

text: in

text: part

text: by

text: the

text: ERC

text: under

text: the

text: European

text: Union’s

text: Framework

text: Programme

text: Grant

text: Agree-

text: ment

text: and

text: by

text: the

text: project

text: TASC

text: of

text: the

text: Labex

text: “PALM.”

text: REFERENCES

text: A.

text: Jimenez

text: Felstrom

text: and

text: K.

text: Zigangirov,

text: “Time-varying

text: periodic

text: convo-

text: lutional

text: codes

text: with

text: low-density

text: parity-check

text: matrix,”

text: IEEE

text: Transactions

text: on

text: Information

text: Theory,

text: vol.

text: no.

text: pp.

text: M.

text: Lentmaier,

text: A.

text: Sridharan,

text: K.

text: S.

text: Zigangirov,

text: and

text: D.

text: Costello,

text: “Ter-

text: minated

text: ldpc

text: convolutional

text: codes

text: with

text: thresholds

text: close

text: to

text: capacity,”

text: in

text: Information

text: Theory,

text: ISIT

text: Proceedings.

text: International

text: Symposium

text: on.

text: IEEE,

text: pp.

text: M.

text: Lentmaier,

text: A.

text: Sridharan,

text: D.

text: J.

text: Costello,

text: and

text: K.

text: S.

text: Zigangirov,

text: “Iterative

text: decoding

text: threshold

text: analysis

text: for

text: ldpc

text: convolutional

text: codes,”

text: IEEE

text: Transactions

text: on

text: Information

text: Theory,

text: vol.

text: no.

text: pp.

text: S.

text: Kudekar,

text: T.

text: J.

text: Richardson,

text: and

text: R.

text: L.

text: Urbanke,

text: “Threshold

text: saturation

text: via

text: spatial

text: coupling:

text: Why

text: convolutional

text: ldpc

text: ensembles

text: perform

text: so

text: well

text: over

text: the

text: bec,”

text: IEEE

text: Transactions

text: on

text: Information

text: Theory,

text: vol.

text: no.

text: pp.

text: S.

text: Kudekar,

text: T.

text: Richardson,

text: and

text: R.

text: Urbanke,

text: “Spatially

text: coupled

text: ensem-

text: bles

text: universally

text: achieve

text: capacity

text: under

text: belief

text: propagation,”

text: in

text: Informa-

text: tion

text: Theory

text: Proceedings

text: (ISIT),

text: IEEE

text: International

text: Symposium

text: on.

text: IEEE,

text: pp.

text: D.

text: L.

text: Donoho,

text: “Compressed

text: sensing,”

text: IEEE

text: Trans.

text: Inform.

text: Theory,

text: vol.

text: p.

text: E.

text: J.

text: Cande`s

text: and

text: M.

text: B.

text: Wakin,

text: “An

text: introduction

text: to

text: compressive

text: sampling,”

text: IEEE

text: Signal

text: Processing

text: Magazine,

text: vol.

text: no.

text: pp.

text: Mar.

text: S.

text: Kudekar

text: and

text: H.

text: Pﬁster,

text: “The

text: effect

text: of

text: spatial

text: coupling

text: on

text: compressive

text: sensing,”

text: in

text: Communication,

text: Control,

text: and

text: Computing

text: (Allerton),

text: pp.

text: F.

text: Krzakala,

text: M.

text: Me´zard,

text: F.

text: Sausset,

text: Y.

text: Sun,

text: and

text: L.

text: Zdeborova´,

text: “Sta-

text: tistical

text: physics-based

text: reconstruction

text: in

text: compressed

text: sensing,”

text: Phys.

text: Rev.

text: X,

text: vol.

text: p.

text: F.

text: Krzakala,

text: M.

text: Me´zard,

text: F.

text: Sausset,

text: Y.

text: Sun,

text: and

text: L.

text: Zdeborova´,

text: “Probabilistic

text: reconstruction

text: in

text: compressed

text: sensing:

text: Algorithms,

text: phase

text: diagrams,

text: and

text: threshold

text: achieving

text: matrices,”

text: J.

text: Stat.

text: Mech.,

text: p.

text: D.

text: L.

text: Donoho,

text: A.

text: Javanmard,

text: and

text: A.

text: Montanari,

text: “Information-

text: theoretically

text: optimal

text: compressed

text: sensing

text: via

text: spatial

text: coupling

text: and

text: ap-

text: proximate

text: message

text: passing,”

text: in

text: Proc.

text: of

text: the

text: IEEE

text: Int.

text: Symposium

text: on

text: Information

text: Theory

text: (ISIT),

text: ##LTFigure##


text: correct predictions for all the mixing angles. A solution with inverted hierarchy is also found in this case with the BM values of θ and θ but with sin2 θ = 0.21. 13 23 12 Alternative ways to modify or avoid the unsatisfactory prediction of the solar angle are also discussed brieﬂy. These include relaxing assumption of leptons transforming as a 3- dimensional irreducible representation and allowing more complicated residual symmetries. One can avoid wrong prediction for the solar angle in the former case but it remains unpredicted. In this case, an inverted hierarchy solution with µ-τ symmetry pattern can ≥ be obtained from the groups like Σ(2N2) with N 3 or even from their subgroups if N is suﬃciently large. In the latter case, one can obtain all the mixing angles correctly as 〚 〛 shown through two examples based on the group 162,10 and S (2). 4 Acknowledgments A.S.J. thanks the Department of Science and Technology, Government of India for support under the J. C. Bose National Fellowship programme, grant no. SR/S2/JCB-31/2010. K.M.P. thanks the Department of Physics and Astronomy of the University of Padova for its support. He also acknowledges partial support from the European Union network FP7 ITN INVISIBLES (Marie Curie Actions, PITN-GA-2011-289442). References [1] G. Altarelli and F. Feruglio, Rev. Mod. Phys. 82, 2701 (2010) [arXiv:1002.0211 [hep-ph]]; G. Altarelli, F. Feruglio and L. Merlo, Fortsch. Phys. 61, 507 (2013) [arXiv:1205.5133 [hep-ph]]; A. Yu. Smirnov, J. Phys. Conf. Ser. 335, 012006 (2011) [arXiv:1103.3461 [hep-ph]]; S. F. King and C. Luhn, Rept. Prog. Phys. 76, 056201 (2013) [arXiv:1301.1340 [hep-ph]]. [2] H. Ishimori, T. Kobayashi, H. Ohki, Y. Shimizu, H. Okada and M. Tanimoto, Prog. Theor. Phys. Suppl. 183, 1 (2010) [arXiv:1003.3552 [hep-th]]. [3] C. S. Lam, Phys. Lett. B 656, 193 (2007) [arXiv:0708.3665 [hep-ph]]; C. S. Lam, Phys. Rev. Lett. 101, 121602 (2008) [arXiv:0804.2622 [hep-ph]]; C. S. Lam, Phys. Rev. D 78, 073015 (2008) [arXiv:0809.1185 [hep-ph]]; C. S. Lam, Phys. Rev. D 87, 013001 (2013) [arXiv:1208.5527 [hep-ph]]; C. S. Lam, arXiv:0907.2206 [hep-ph]; R. d. A. Toorop, F. Feruglio and C. Hagedorn, Phys. Lett. B 703, 447 (2011) [arXiv:1107.3486 [hep-ph]]; R. de Adelhart Toorop, F. Feruglio and C. Hagedorn, Nucl. Phys. B 858, 437 (2012) [arXiv:1112.1340 [hep-ph]]; D. Hernandez and A. Yu. Smirnov, Phys. Rev. D 86, 053014 (2012) [arXiv:1204.0445 [hep-ph]]; D. Hernandez and A. Yu. Smirnov, Phys. Rev. D 87, no. 5, 053005 (2013) [arXiv:1212.2149 [hep-ph]]; I. d. M. Varzielas and L. Lavoura, arXiv:1312.0215 [hep-ph]; L. Lavoura and P. O. Ludl, arXiv:1401.5036 [hep-ph]. [4] C. S. Lam, Phys. Rev. D 83, 113002 (2011) [arXiv:1104.0055 [hep-ph]]. [5] M. Holthausen, K. S. Lim and M. Lindner, Phys. Lett. B 721, 61 (2013) [arXiv:1212.2411 [hep-ph]]. [6] D. Hernandez and A. Yu. Smirnov, Phys. Rev. D 88, 093007 (2013) [arXiv:1304.7738 [hep-ph]]. – 20 –

text: correct

text: predictions

text: for

text: all

text: the

text: mixing

text: angles.

text: A

text: solution

text: with

text: inverted

text: hierarchy

text: is

text: also

text: found

text: in

text: this

text: case

text: with

text: the

text: BM

text: values

text: of

text: θ

text: and

text: θ

text: but

text: with

text: θ

text: Alternative

text: ways

text: to

text: modify

text: or

text: avoid

text: the

text: unsatisfactory

text: prediction

text: of

text: the

text: solar

text: angle

text: are

text: also

text: discussed

text: brieﬂy.

text: These

text: include

text: relaxing

text: assumption

text: of

text: leptons

text: transforming

text: as

text: a

text: dimensional

text: irreducible

text: representation

text: and

text: allowing

text: more

text: complicated

text: residual

text: symmetries.

text: One

text: can

text: avoid

text: wrong

text: prediction

text: for

text: the

text: solar

text: angle

text: in

text: the

text: former

text: case

text: but

text: it

text: remains

text: unpredicted.

text: In

text: this

text: case,

text: an

text: inverted

text: hierarchy

text: solution

text: with

text: µ-τ

text: symmetry

text: pattern

text: can

text: be

text: obtained

text: from

text: the

text: groups

text: like

text: with

text: N

text: or

text: even

text: from

text: their

text: subgroups

text: if

text: N

text: is

text: suﬃciently

text: large.

text: In

text: the

text: latter

text: case,

text: one

text: can

text: obtain

text: all

text: the

text: mixing

text: angles

text: correctly

text: as

text: shown

text: through

text: two

text: examples

text: based

text: on

text: the

text: group

text: and

text: S

text: Acknowledgments

text: A.S.J.

text: thanks

text: the

text: Department

text: of

text: Science

text: and

text: Technology,

text: Government

text: of

text: India

text: for

text: support

text: under

text: the

text: J.

text: C.

text: Bose

text: National

text: Fellowship

text: programme,

text: grant

text: no.

text: K.M.P.

text: thanks

text: the

text: Department

text: of

text: Physics

text: and

text: Astronomy

text: of

text: the

text: University

text: of

text: Padova

text: for

text: its

text: support.

text: He

text: also

text: acknowledges

text: partial

text: support

text: from

text: the

text: European

text: Union

text: network

text: ITN

text: INVISIBLES

text: (Marie

text: Curie

text: Actions,

text: References

text: G.

text: Altarelli

text: and

text: F.

text: Feruglio,

text: Rev.

text: Mod.

text: Phys.

text: [hep-ph]];

text: G.

text: Altarelli,

text: F.

text: Feruglio

text: and

text: L.

text: Merlo,

text: Fortsch.

text: Phys.

text: [hep-ph]];

text: A.

text: Yu.

text: Smirnov,

text: J.

text: Phys.

text: Conf.

text: Ser.

text: [hep-ph]];

text: S.

text: F.

text: King

text: and

text: C.

text: Luhn,

text: Rept.

text: Prog.

text: Phys.

text: [hep-ph]].

text: H.

text: Ishimori,

text: T.

text: Kobayashi,

text: H.

text: Ohki,

text: Y.

text: Shimizu,

text: H.

text: Okada

text: and

text: M.

text: Tanimoto,

text: Prog.

text: Theor.

text: Phys.

text: Suppl.

text: [hep-th]].

text: C.

text: S.

text: Lam,

text: Phys.

text: Lett.

text: B

text: [hep-ph]];

text: C.

text: S.

text: Lam,

text: Phys.

text: Rev.

text: Lett.

text: [hep-ph]];

text: C.

text: S.

text: Lam,

text: Phys.

text: Rev.

text: D

text: [hep-ph]];

text: C.

text: S.

text: Lam,

text: Phys.

text: Rev.

text: D

text: [hep-ph]];

text: C.

text: S.

text: Lam,

text: [hep-ph];

text: R.

text: d.

text: A.

text: Toorop,

text: F.

text: Feruglio

text: and

text: C.

text: Hagedorn,

text: Phys.

text: Lett.

text: B

text: [hep-ph]];

text: R.

text: de

text: Adelhart

text: Toorop,

text: F.

text: Feruglio

text: and

text: C.

text: Hagedorn,

text: Nucl.

text: Phys.

text: B

text: [hep-ph]];

text: D.

text: Hernandez

text: and

text: A.

text: Yu.

text: Smirnov,

text: Phys.

text: Rev.

text: D

text: [hep-ph]];

text: D.

text: Hernandez

text: and

text: A.

text: Yu.

text: Smirnov,

text: Phys.

text: Rev.

text: D

text: no.

text: [hep-ph]];

text: I.

text: d.

text: M.

text: Varzielas

text: and

text: L.

text: Lavoura,

text: [hep-ph];

text: L.

text: Lavoura

text: and

text: P.

text: O.

text: Ludl,

text: [hep-ph].

text: C.

text: S.

text: Lam,

text: Phys.

text: Rev.

text: D

text: [hep-ph]].

text: M.

text: Holthausen,

text: K.

text: S.

text: Lim

text: and

text: M.

text: Lindner,

text: Phys.

text: Lett.

text: B

text: [hep-ph]].

text: D.

text: Hernandez

text: and

text: A.

text: Yu.

text: Smirnov,

text: Phys.

text: Rev.

text: D

text: [hep-ph]].


text: SIMD Compression and the Intersection of Sorted Integers ∗ D. Lemire1 , L. Boytsov2, N. Kurz3 1LICEF Research Center, TELUQ, Montreal, QC, Canada 2Carnegie Mellon University, Pittsburgh, PA USA 3Verse Communications, Orinda, CA USA SUMMARY Sorted lists of integers are commonly used in inverted indexes and database systems. They are often compressed in memory. We can use the SIMD instructions available in common processors to boost the speed of integer compression schemes. Our S4-BP128-D4 scheme uses as little as 0.7 CPU cycles per decoded 32-bit integer while still providing state-of-the-art compression. However, if the subsequent processing of the integers is slow, the effort spent on optimizing decompression speed can be wasted. To show that it does not have to be so, we (1) vectorize and optimize the intersection of posting lists; (2) introduce the SIMD GALLOPING algorithm. We exploit the fact that one SIMD instruction can compare 4 pairs of 32-bit integers at once. We experiment with two TREC text collections, GOV2 and ClueWeb09 (Category B), using logs from the TREC million-query track. We show that using only the SIMD instructions ubiquitous in all modern CPUs, our techniques for conjunctive queries can double the speed of a state-of-the-art approach. KEY WORDS: performance; measurement; index compression; vector processing 1. INTRODUCTION An inverted index maps terms to lists of document identiﬁers. A column index in a database might, similarly, map attribute values to row identiﬁers. Storing all these lists on disk can limit the performance since the latency of the fastest drives is several orders of magnitude higher than the latency of memory. Fast compression can reduce query response times [1, 2]. We assume that identiﬁers can be represented using 32-bit integers and that they are stored in sorted order. In this context, one can achieve good compression ratios and high decompression speed, by employing differential coding. We exploit the fact that the lists are sorted and instead of storing the integers themselves, we store the differences between successive integers, sometimes called the deltas. Additional improvements arise from using the single instruction, multiple data (SIMD) instructions available on practically all server and desktop processors produced in the last decade (Streaming SIMD Extensions 2 or SSE2). A SIMD instruction performs the same operation on multiple pieces of data: this is also known as vector processing. Previous research [3] showed that we can decode compressed 32-bit integers using less than 1.5 CPU cycles per integer in a realistic ∗ Correspondence to: LICEF Research Center, TELUQ, Universite´ du Que´bec, 5800 Saint-Denis, Montreal (Quebec) H2S 3L5 Canada. Contract/grant sponsor: Natural Sciences and Engineering Research Council of Canada; contract/grant number: 261437 ##LTLine##

text: SIMD

label: title

text: Compression

text: and

text: the

text: Intersection

text: of

text: Sorted

text: Integers

label: author

text: D.

text: L.

text: N.

text: Research

text: Center,

text: TELUQ,

text: Montreal,

text: QC,

text: Canada

text: Mellon

text: University,

text: Pittsburgh,

text: PA

text: USA

text: Communications,

text: Orinda,

text: CA

text: USA

text: SUMMARY

text: Sorted

label: abstract

text: lists

text: of

text: integers

text: are

text: commonly

text: used

text: in

text: inverted

text: indexes

text: and

text: database

text: systems.

text: They

text: are

text: often

text: compressed

text: in

text: memory.

text: We

text: can

text: use

text: the

text: SIMD

text: instructions

text: available

text: in

text: common

text: processors

text: to

text: boost

text: the

text: speed

text: of

text: integer

text: compression

text: schemes.

text: Our

text: scheme

text: uses

text: as

text: little

text: as

text: CPU

text: cycles

text: per

text: decoded

text: integer

text: while

text: still

text: providing

text: state-of-the-art

text: compression.

text: However,

text: if

text: the

text: subsequent

text: processing

text: of

text: the

text: integers

text: is

text: slow,

text: the

text: effort

text: spent

text: on

text: optimizing

text: decompression

text: speed

text: can

text: be

text: wasted.

text: To

text: show

text: that

text: it

text: does

text: not

text: have

text: to

text: be

text: so,

text: we

text: vectorize

text: and

text: optimize

text: the

text: intersection

text: of

text: posting

text: lists;

text: introduce

text: the

text: SIMD

text: GALLOPING

text: algorithm.

text: We

text: exploit

text: the

text: fact

text: that

text: one

text: SIMD

text: instruction

text: can

text: compare

text: pairs

text: of

text: integers

text: at

text: once.

text: We

text: experiment

text: with

text: two

text: TREC

text: text

text: collections,

text: and

text: (Category

text: B),

text: using

text: logs

text: from

text: the

text: TREC

text: million-query

text: track.

text: We

text: show

text: that

text: using

text: only

text: the

text: SIMD

text: instructions

text: ubiquitous

text: in

text: all

text: modern

text: CPUs,

text: our

text: techniques

text: for

text: conjunctive

text: queries

text: can

text: double

text: the

text: speed

text: of

text: a

text: state-of-the-art

text: approach.

text: KEY

text: WORDS:

text: performance;

text: measurement;

text: index

text: compression;

text: vector

text: processing

text: INTRODUCTION

text: An

text: inverted

text: index

text: maps

text: terms

text: to

text: lists

text: of

text: document

text: identiﬁers.

text: A

text: column

text: index

text: in

text: a

text: database

text: might,

text: similarly,

text: map

text: attribute

text: values

text: to

text: row

text: identiﬁers.

text: Storing

text: all

text: these

text: lists

text: on

text: disk

text: can

text: limit

text: the

text: performance

text: since

text: the

text: latency

text: of

text: the

text: fastest

text: drives

text: is

text: several

text: orders

text: of

text: magnitude

text: higher

text: than

text: the

text: latency

text: of

text: memory.

text: Fast

text: compression

text: can

text: reduce

text: query

text: response

text: times

text: We

text: assume

text: that

text: identiﬁers

text: can

text: be

text: represented

text: using

text: integers

text: and

text: that

text: they

text: are

text: stored

text: in

text: sorted

text: order.

text: In

text: this

text: context,

text: one

text: can

text: achieve

text: good

text: compression

text: ratios

text: and

text: high

text: decompression

text: speed,

text: by

text: employing

text: differential

text: coding.

text: We

text: exploit

text: the

text: fact

text: that

text: the

text: lists

text: are

text: sorted

text: and

text: instead

text: of

text: storing

text: the

text: integers

text: themselves,

text: we

text: store

text: the

text: differences

text: between

text: successive

text: integers,

text: sometimes

text: called

text: the

text: deltas.

text: Additional

text: improvements

text: arise

text: from

text: using

text: the

text: single

text: instruction,

text: multiple

text: data

text: (SIMD)

text: instructions

text: available

text: on

text: practically

text: all

text: server

text: and

text: desktop

text: processors

text: produced

text: in

text: the

text: last

text: decade

text: (Streaming

text: SIMD

text: Extensions

text: or

text: A

text: SIMD

text: instruction

text: performs

text: the

text: same

text: operation

text: on

text: multiple

text: pieces

text: of

text: data:

text: this

text: is

text: also

text: known

text: as

text: vector

text: processing.

text: Previous

text: research

text: showed

text: that

text: we

text: can

text: decode

text: compressed

text: integers

text: using

text: less

text: than

text: CPU

text: cycles

text: per

text: integer

text: in

text: a

text: realistic

text: Correspondence

text: to:

text: LICEF

text: Research

text: Center,

text: TELUQ,

text: Universite´

text: du

text: Que´bec,

text: Saint-Denis,

text: Montreal

text: (Quebec)

text: Canada.

text: Contract/grant

text: sponsor:

text: Natural

text: Sciences

text: and

text: Engineering

text: Research

text: Council

text: of

text: Canada;

text: contract/grant

text: number:

text: ##LTLine##


text: SIMD COMPRESSION AND THE INTERSECTION OF SORTED INTEGERS 11 Table III. Comparison between the 4 vectorized differential coding techniques with 4-integer SIMD instructions size of deltas instructions/int × D1 1.0 1.5 × D2 2.0 1 × DM 2.5 0.5 × D4 4.0 0.25 to the original integers. Though the decompression requires two passes over the same small block of integers, it is unlikely to cause many expensive cache misses. Maybe surprisingly, we can do substantially better, at least for schemes such as S4-BP128. Instead of using two passes, we can use a single pass where we do both the bit unpacking and the computation of the preﬁx sum. In some cases, the one-pass approach is almost twice as fast as the two-pass approach. Indeed, when unpacking a block of 128 integers, we store 32 SSE registers in memory. Such store operations have a limited throughput of one per cycle on recent Intel processors [21]. However, if the preﬁx sum computation is a separate step, we need to reload the recently unpacked data, compute the preﬁx sum and then store the data again. In effect, we end up having to store 64 SSE registers per block of 128 integers. Hence, we need at least 0.5 cycles to unpack an integer if the preﬁx sum computation is separate. These store operations can become a bottleneck. A two-step unpacking has a theoretical speed limit of 7.2 billion 32-bit integers per second on a 3.60 GHz processor. Yet we § can nearly reach 9 billion 32-bit integers per second with a one-step unpacking (see ). Henceforth we use the term unpacking to also refer to the process where we both unpack and compute the preﬁx sum. Algorithm 1 illustrates the bit unpacking routine for a block of 128 integers. It takes as a parameter a SIMD preﬁx-sum function P used at lines 10 and 16: for D4, we have P(t, v) = t + v (an element-wise addition of two vectors). Omitting lines 10 and 16 disables differential coding. In practice, we generate one such function for each bit width b and for each preﬁx-sum function P. The preﬁx sum always starts from an initial vector (v). We set v = (0, 0, 0, 0) initially and then, after decompressing each block of 128 integers, v is set to the last 4 integers decoded. Beside the integration of differential coding with the bit unpacking, we have also improved over Lemire and Boytsov’s bit unpacking [3, Fig. 7] in another way: whereas each of their procedures may require several masks, our implementation uses a single mask per procedure (see line 4 in Algorithm 1). Given that we only have 16 SIMD registers on our Intel processors, attempting to keep several of them occupied with constant masks can be wasteful. Unfortunately, for S4-FASTPFOR, it is not clear how to integrate bit unpacking and computation of the preﬁx sum. Indeed, S4-FASTPFOR requires three separate operations in sequence: bit unpacking, patching and computing the preﬁx sum. Patching must happen after bit unpacking, but before the preﬁx sum. This makes tight integration between patching and the preﬁx sum difﬁcult: we tried various approaches but they did not result in performance improvement. 6. FAST INTERSECTIONS Consider lists of uncompressed integers. To compute the intersection between several sorted lists quickly, a competitive approach is Set-vs-Set (SvS): we sort the lists in the order of non-decreasing cardinality and intersect them two-by-two, starting with the smallest. A textbook intersection algorithm between two lists (akin to the merge sort algorithm) runs in time O(m + n) where the lists have length m and n (henceforth we call it SCALAR). Though it is competitive when m and (cid:29) n are similar, there are better alternatives when n m. Such alternative algorithms assume that we intersect a small list r with a large list f. They iterate over the small list: for each element r , i they seek a match f in the second list using some search procedure. Whether there is a match or j ##LTLine##

text: SIMD

text: COMPRESSION

text: AND

text: THE

text: INTERSECTION

text: OF

text: SORTED

text: INTEGERS

text: Table

text: III.

text: Comparison

label: caption

text: between

text: the

text: vectorized

text: differential

text: coding

text: techniques

text: with

text: SIMD

text: instructions

text: size

label: table

text: of

text: deltas

text: instructions/int

text: DM

text: to

text: the

text: original

text: integers.

text: Though

text: the

text: decompression

text: requires

text: two

text: passes

text: over

text: the

text: same

text: small

text: block

text: of

text: integers,

text: it

text: is

text: unlikely

text: to

text: cause

text: many

text: expensive

text: cache

text: misses.

text: Maybe

text: surprisingly,

text: we

text: can

text: do

text: substantially

text: better,

text: at

text: least

text: for

text: schemes

text: such

text: as

text: Instead

text: of

text: using

text: two

text: passes,

text: we

text: can

text: use

text: a

text: single

text: pass

text: where

text: we

text: do

text: both

text: the

text: bit

text: unpacking

text: and

text: the

text: computation

text: of

text: the

text: preﬁx

text: sum.

text: In

text: some

text: cases,

text: the

text: one-pass

text: approach

text: is

text: almost

text: twice

text: as

text: fast

text: as

text: the

text: two-pass

text: approach.

text: Indeed,

text: when

text: unpacking

text: a

text: block

text: of

text: integers,

text: we

text: store

text: SSE

text: registers

text: in

text: memory.

text: Such

text: store

text: operations

text: have

text: a

text: limited

text: throughput

text: of

text: one

text: per

text: cycle

text: on

text: recent

text: Intel

text: processors

text: However,

text: if

text: the

text: preﬁx

text: sum

text: computation

text: is

text: a

text: separate

text: step,

text: we

text: need

text: to

text: reload

text: the

text: recently

text: unpacked

text: data,

text: compute

text: the

text: preﬁx

text: sum

text: and

text: then

text: store

text: the

text: data

text: again.

text: In

text: effect,

text: we

text: end

text: up

text: having

text: to

text: store

text: SSE

text: registers

text: per

text: block

text: of

text: integers.

text: Hence,

text: we

text: need

text: at

text: least

text: cycles

text: to

text: unpack

text: an

text: integer

text: if

text: the

text: preﬁx

text: sum

text: computation

text: is

text: separate.

text: These

text: store

text: operations

text: can

text: become

text: a

text: bottleneck.

text: A

text: two-step

text: unpacking

text: has

text: a

text: theoretical

text: speed

text: limit

text: of

text: billion

text: integers

text: per

text: second

text: on

text: a

text: GHz

text: processor.

text: Yet

text: we

text: can

text: nearly

text: reach

text: billion

text: integers

text: per

text: second

text: with

text: a

text: one-step

text: unpacking

text: (see

text: Henceforth

text: we

text: use

text: the

text: term

text: unpacking

text: to

text: also

text: refer

text: to

text: the

text: process

text: where

text: we

text: both

text: unpack

text: and

text: compute

text: the

text: preﬁx

text: sum.

text: Algorithm

text: illustrates

text: the

text: bit

text: unpacking

text: routine

text: for

text: a

text: block

text: of

text: integers.

text: It

text: takes

text: as

text: a

text: parameter

text: a

text: SIMD

text: preﬁx-sum

text: function

text: P

text: used

text: at

text: lines

text: and

text: for

text: we

text: have

text: P(t,

text: v)

text: t

text: v

text: (an

text: element-wise

text: addition

text: of

text: two

text: vectors).

text: Omitting

text: lines

text: and

text: disables

text: differential

text: coding.

text: In

text: practice,

text: we

text: generate

text: one

text: such

text: function

text: for

text: each

text: bit

text: width

text: b

text: and

text: for

text: each

text: preﬁx-sum

text: function

text: P.

text: The

text: preﬁx

text: sum

text: always

text: starts

text: from

text: an

text: initial

text: vector

text: (v).

text: We

text: set

text: v

text: initially

text: and

text: then,

text: after

text: decompressing

text: each

text: block

text: of

text: integers,

text: v

text: is

text: set

text: to

text: the

text: last

text: integers

text: decoded.

text: Beside

text: the

text: integration

text: of

text: differential

text: coding

text: with

text: the

text: bit

text: unpacking,

text: we

text: have

text: also

text: improved

text: over

text: Lemire

text: and

text: Boytsov’s

text: bit

text: unpacking

text: Fig.

text: in

text: another

text: way:

text: whereas

text: each

text: of

text: their

text: procedures

text: may

text: require

text: several

text: masks,

text: our

text: implementation

text: uses

text: a

text: single

text: mask

text: per

text: procedure

text: (see

text: line

text: in

text: Algorithm

text: Given

text: that

text: we

text: only

text: have

text: SIMD

text: registers

text: on

text: our

text: Intel

text: processors,

text: attempting

text: to

text: keep

text: several

text: of

text: them

text: occupied

text: with

text: constant

text: masks

text: can

text: be

text: wasteful.

text: Unfortunately,

text: for

text: it

text: is

text: not

text: clear

text: how

text: to

text: integrate

text: bit

text: unpacking

text: and

text: computation

text: of

text: the

text: preﬁx

text: sum.

text: Indeed,

text: requires

text: three

text: separate

text: operations

text: in

text: sequence:

text: bit

text: unpacking,

text: patching

text: and

text: computing

text: the

text: preﬁx

text: sum.

text: Patching

text: must

text: happen

text: after

text: bit

text: unpacking,

text: but

text: before

text: the

text: preﬁx

text: sum.

text: This

text: makes

text: tight

text: integration

text: between

text: patching

text: and

text: the

text: preﬁx

text: sum

text: difﬁcult:

text: we

text: tried

text: various

text: approaches

text: but

text: they

text: did

text: not

text: result

text: in

text: performance

text: improvement.

text: FAST

text: INTERSECTIONS

text: Consider

text: lists

text: of

text: uncompressed

text: integers.

text: To

text: compute

text: the

text: intersection

text: between

text: several

text: sorted

text: lists

text: quickly,

text: a

text: competitive

text: approach

text: is

text: Set-vs-Set

text: (SvS):

text: we

text: sort

text: the

text: lists

text: in

text: the

text: order

text: of

text: non-decreasing

text: cardinality

text: and

text: intersect

text: them

text: two-by-two,

text: starting

text: with

text: the

text: smallest.

text: A

text: textbook

text: intersection

text: algorithm

text: between

text: two

text: lists

text: (akin

text: to

text: the

text: merge

text: sort

text: algorithm)

text: runs

text: in

text: time

text: O(m

text: n)

text: where

text: the

text: lists

text: have

text: length

text: m

text: and

text: n

text: (henceforth

text: we

text: call

text: it

text: SCALAR).

text: Though

text: it

text: is

text: competitive

text: when

text: m

text: and

text: n

text: are

text: similar,

text: there

text: are

text: better

text: alternatives

text: when

text: n

text: m.

text: Such

text: alternative

text: algorithms

text: assume

text: that

text: we

text: intersect

text: a

text: small

text: list

text: r

text: with

text: a

text: large

text: list

text: f.

text: They

text: iterate

text: over

text: the

text: small

text: list:

text: for

text: each

text: element

text: r

text: i

text: they

text: seek

text: a

text: match

text: f

text: in

text: the

text: second

text: list

text: using

text: some

text: search

text: procedure.

text: Whether

text: there

text: is

text: a

text: match

text: or

text: j

text: ##LTLine##


text: SIMD COMPRESSION AND THE INTERSECTION OF SORTED INTEGERS 13 of the intersection with the few remaining integers and process these integers using a more traditional intersection algorithm. The intersection algorithm can be seen as a generalization of the textbook intersection algorithm (akin to the merge sort algorithm). There are two block pointers (one for each sub-array) originally pointing to the ﬁrst blocks. Using SIMD instructions, it is possible to carry out an all-against-all comparison of 16-bit integers between these two blocks and extract matching integers. Schlegel et al. exploit the fact that such a comparison can quickly § be done using the SSE 4.1 string-comparison instruction pcmpestrm. (See .) Recall that this instruction takes strings of up to eight 16-bit integers and returns an 8-bit mask indicating which 16-bit integers are present in both strings. The number of 1s in the resulting mask (computed quickly with the popcnt instruction) indicates the number of matching integers. Schlegel et al. apply this instruction to two blocks of eight integers (one from the ﬁrst list and another from the second list). To obtain matching integers, they use the shufﬂe SSSE3 instruction pshufb. This instruction extracts and juxtaposes matching integers so that they follow each other without gaps. This requires a lookup table to convert 8-bit masks produced by pcmpestrm (and extracted using pextrd) to the shufﬂe mask for pshufb. The lookup table contains 256 128-bit shufﬂe masks. The matching integers are written out and the output pointer is advanced by the number of matching integers. Afterwards, the highest values of the two blocks are compared. If the highest value in the ﬁrst block is smaller than the highest value of the second block, the ﬁrst block pointer is advanced. If the second block contains a smaller highest value, its pointer is advanced in a similar fashion. If the highest values are equal, the block pointers of both lists are advanced. When the blocks in one of the lists are exhausted, the intersection has been computed. We slightly improved Schlegel et al.’s implementation by replacing the pcmpestrm instruction with the similar pcmpistrm instruction. The latter is faster. Its only downside is that it assumes that the two strings of 16-bit characters are either null terminated or have a length of 8 characters. However, because the integers are sorted (even in 16-bit packed blocks), we can easily check for the presence of a zero 16-bit integer as a special case. Schlegel et al. only validated their results on the intersection of arrays that have identical lengths. In contrast, we work on arrays of 32-bit integers having differing lengths. 2. Katsov [31] proposed an approach similar to Schlegel et al. except that it works on arrays of 32-bit integers. We process the input arrays by considering blocks of four 32-bit integers. (cid:48) (cid:48) (cid:48) (cid:48) Given two blocks (a, b, c, d) and (a , b , c , d ), we execute four comparisons: • (cid:48) (cid:48) (cid:48) (cid:48) (a, b, c, d) = (a , b , c , d ), • (cid:48) (cid:48) (cid:48) (cid:48) (a, b, c, d) = (b , c , d , a ), • (cid:48) (cid:48) (cid:48) (cid:48) (a, b, c, d) = (c , d , a , b ), • (cid:48) (cid:48) (cid:48) (cid:48) (a, b, c, d) = (d , a , b , c ). For each comparison, the pcmpeqd instruction generates four integers with value 0xFFFFFFFF or 0 depending on whether the corresponding pairs of integers are equal. By computing the bitwise OR of the 4 resulting masks, we know whether each value in (a, b, c, d) (cid:48) (cid:48) (cid:48) (cid:48) matches one value in (a , b , c , d ). We can extract the corresponding 4-bit mask with the movmskps instruction. The rest is similar to Schlegel et al.’s algorithm. There has been extensive work to accelerate sort or search algorithms by using SIMD instructions [32, 33], among others. Nevertheless, we are not aware of other algorithms practically relevant to the intersection of sorted lists of integers using SIMD instructions. 6.2. Our intersection algorithms Both the SvS and textbook algorithms involve checking whether an element from one list is in the other list. When one list is substantially shorter than the other, we typically compare a single integer

text: SIMD

text: COMPRESSION

text: AND

text: THE

text: INTERSECTION

text: OF

text: SORTED

text: INTEGERS

text: of

label: list

text: the

text: intersection

text: with

text: the

text: few

text: remaining

text: integers

text: and

text: process

text: these

text: integers

text: using

text: a

text: more

text: traditional

text: intersection

text: algorithm.

text: The

text: intersection

text: algorithm

text: can

text: be

text: seen

text: as

text: a

text: generalization

text: of

text: the

text: textbook

text: intersection

text: algorithm

text: (akin

text: to

text: the

text: merge

text: sort

text: algorithm).

text: There

text: are

text: two

text: block

text: pointers

text: (one

text: for

text: each

text: sub-array)

text: originally

text: pointing

text: to

text: the

text: ﬁrst

text: blocks.

text: Using

text: SIMD

text: instructions,

text: it

text: is

text: possible

text: to

text: carry

text: out

text: an

text: all-against-all

text: comparison

text: of

text: integers

text: between

text: these

text: two

text: blocks

text: and

text: extract

text: matching

text: integers.

text: Schlegel

text: et

text: al.

text: exploit

text: the

text: fact

text: that

text: such

text: a

text: comparison

text: can

text: quickly

text: be

text: done

text: using

text: the

text: SSE

text: string-comparison

text: instruction

text: pcmpestrm.

text: (See

text: Recall

text: that

text: this

text: instruction

text: takes

text: strings

text: of

text: up

text: to

text: eight

text: integers

text: and

text: returns

text: an

text: mask

text: indicating

text: which

text: integers

text: are

text: present

text: in

text: both

text: strings.

text: The

text: number

text: of

text: in

text: the

text: resulting

text: mask

text: (computed

text: quickly

text: with

text: the

text: popcnt

text: instruction)

text: indicates

text: the

text: number

text: of

text: matching

text: integers.

text: Schlegel

text: et

text: al.

text: apply

text: this

text: instruction

text: to

text: two

text: blocks

text: of

text: eight

text: integers

text: (one

text: from

text: the

text: ﬁrst

text: list

text: and

text: another

text: from

text: the

text: second

text: list).

text: To

text: obtain

text: matching

text: integers,

text: they

text: use

text: the

text: shufﬂe

text: instruction

text: pshufb.

text: This

text: instruction

text: extracts

text: and

text: juxtaposes

text: matching

text: integers

text: so

text: that

text: they

text: follow

text: each

text: other

text: without

text: gaps.

text: This

text: requires

text: a

text: lookup

text: table

text: to

text: convert

text: masks

text: produced

text: by

text: pcmpestrm

text: (and

text: extracted

text: using

text: pextrd)

text: to

text: the

text: shufﬂe

text: mask

text: for

text: pshufb.

text: The

text: lookup

text: table

text: contains

text: shufﬂe

text: masks.

text: The

text: matching

text: integers

text: are

text: written

text: out

text: and

text: the

text: output

text: pointer

text: is

text: advanced

text: by

text: the

text: number

text: of

text: matching

text: integers.

text: Afterwards,

text: the

text: highest

text: values

text: of

text: the

text: two

text: blocks

text: are

text: compared.

text: If

text: the

text: highest

text: value

text: in

text: the

text: ﬁrst

text: block

text: is

text: smaller

text: than

text: the

text: highest

text: value

text: of

text: the

text: second

text: block,

text: the

text: ﬁrst

text: block

text: pointer

text: is

text: advanced.

text: If

text: the

text: second

text: block

text: contains

text: a

text: smaller

text: highest

text: value,

text: its

text: pointer

text: is

text: advanced

text: in

text: a

text: similar

text: fashion.

text: If

text: the

text: highest

text: values

text: are

text: equal,

text: the

text: block

text: pointers

text: of

text: both

text: lists

text: are

text: advanced.

text: When

text: the

text: blocks

text: in

text: one

text: of

text: the

text: lists

text: are

text: exhausted,

text: the

text: intersection

text: has

text: been

text: computed.

text: We

text: slightly

text: improved

text: Schlegel

text: et

text: al.’s

text: implementation

text: by

text: replacing

text: the

text: pcmpestrm

text: instruction

text: with

text: the

text: similar

text: pcmpistrm

text: instruction.

text: The

text: latter

text: is

text: faster.

text: Its

text: only

text: downside

text: is

text: that

text: it

text: assumes

text: that

text: the

text: two

text: strings

text: of

text: characters

text: are

text: either

text: terminated

text: or

text: have

text: a

text: length

text: of

text: characters.

text: However,

text: because

text: the

text: integers

text: are

text: sorted

text: (even

text: in

text: packed

text: blocks),

text: we

text: can

text: easily

text: check

text: for

text: the

text: presence

text: of

text: a

text: zero

text: integer

text: as

text: a

text: special

text: case.

text: Schlegel

text: et

text: al.

text: only

text: validated

text: their

text: results

text: on

text: the

text: intersection

text: of

text: arrays

text: that

text: have

text: identical

text: lengths.

text: In

text: contrast,

text: we

text: work

text: on

text: arrays

text: of

text: integers

text: having

text: differing

text: lengths.

text: Katsov

text: proposed

text: an

text: approach

text: similar

text: to

text: Schlegel

text: et

text: al.

text: except

text: that

text: it

text: works

text: on

text: arrays

text: of

text: integers.

text: We

text: process

text: the

text: input

text: arrays

text: by

text: considering

text: blocks

text: of

text: four

text: integers.

text: Given

text: two

text: blocks

text: (a,

text: b,

text: c,

text: d)

text: and

text: (a

text: b

text: c

text: d

text: we

text: execute

text: four

text: comparisons:

text: (a,

text: b,

text: c,

text: d)

text: (a

text: b

text: c

text: d

text: (a,

text: b,

text: c,

text: d)

text: (b

text: c

text: d

text: a

text: (a,

text: b,

text: c,

text: d)

text: (c

text: d

text: a

text: b

text: (a,

text: b,

text: c,

text: d)

text: (d

text: a

text: b

text: c

text: For

text: each

text: comparison,

text: the

text: pcmpeqd

text: instruction

text: generates

text: four

text: integers

text: with

text: value

text: or

text: depending

text: on

text: whether

text: the

text: corresponding

text: pairs

text: of

text: integers

text: are

text: equal.

text: By

text: computing

text: the

text: bitwise

text: OR

text: of

text: the

text: resulting

text: masks,

text: we

text: know

text: whether

text: each

text: value

text: in

text: (a,

text: b,

text: c,

text: d)

text: matches

text: one

text: value

text: in

text: (a

text: b

text: c

text: d

text: We

text: can

text: extract

text: the

text: corresponding

text: mask

text: with

text: the

text: movmskps

text: instruction.

text: The

text: rest

text: is

text: similar

text: to

text: Schlegel

text: et

text: al.’s

text: algorithm.

text: There

text: has

text: been

text: extensive

text: work

text: to

text: accelerate

text: sort

text: or

text: search

text: algorithms

text: by

text: using

text: SIMD

text: instructions

text: among

text: others.

text: Nevertheless,

text: we

text: are

text: not

text: aware

text: of

text: other

text: algorithms

text: practically

text: relevant

text: to

text: the

text: intersection

text: of

text: sorted

text: lists

text: of

text: integers

text: using

text: SIMD

text: instructions.

text: Our

text: intersection

text: algorithms

text: Both

text: the

text: SvS

text: and

text: textbook

text: algorithms

text: involve

text: checking

text: whether

text: an

text: element

text: from

text: one

text: list

text: is

text: in

text: the

text: other

text: list.

text: When

text: one

text: list

text: is

text: substantially

text: shorter

text: than

text: the

text: other,

text: we

text: typically

text: compare

text: a

text: single

text: integer


text: SIMD COMPRESSION AND THE INTERSECTION OF SORTED INTEGERS 17 Algorithm 4 The SIMD GALLOPING algorithm Require: SIMD architecture with T-integer vectors 1: input: two non-empty sorted arrays of integers r, f 2: assume: length(f) is divisible by T 3: x initially empty dynamic array (our answer) ← 4: j 1 ∈ { } 5: for i 1, 2, . . . , length(r) do ← 6: R (r , r , . . . , r ) i i i ≥ 7: ﬁnd by sequential search the smallest δ such that f − r for δ = − j+δ 1+T i 0, 1T, 2T, 4T, . . . , length(f) 1 + T, if none return x (cid:98) (cid:99) ≥ 8: ﬁnd by binary search the smallest δ in [ δ/2 , δ] divisible by T such that f − r min j+δmin 1+T i ← 9: j j + δ ← min 10: F (f , f , . . . , f − ) j j+1 j∈1{+T } 11: if R = F for some i 1, 2, . . . , T then i i 12: append r to x i 13: return x 7. EXPERIMENTAL RESULTS § We assess experimentally the unpacking speed with integrated differential coding ( ), the § decompression speed of the corresponding schemes ( ), the beneﬁts of our SIMD-based intersection § § schemes ( ), and, SIMD-accelerated bitmap-list hybrids ( ) with realistic query logs and inverted indexes. 7.1. Software ‡ All our software is freely available online under the Apache Software License 2.0. The code is written in C++ using the C++11 standard. Our code builds using several compilers such as clang++ 3.2 and Intel icpc 13. However, we use GNU GCC 4.7 on a Linux PC for our tests. All code was compiled using the -O3 ﬂag. We implemented scalar schemes (FASTPFOR and VARINT) without using SIMD instructions and with the scalar equivalent of D1 differential coding. 7.2. Hardware We ran all our experiments on an Intel Xeon CPU (E5-1620, Sandy Bridge) running at 3.60 GHz. This CPU also has 10 MB of L3 cache as well as 32 kB and 256 kB of L1 and L2 data cache per core. We have 32 GB of RAM (DDR3-1600) running quad-channel. We estimate that we can read from RAM at a speed of 4 billion 32-bit integers per second and from L3 cache at a speed of 8 billion 32-bit integers per second. All data is stored in RAM so that disk performance is irrelevant. 7.3. Real data To fully assess our results, we need realistic data sets. For this purpose, we use posting lists extracted from the TREC collections ClueWeb09 (Category B) and GOV2. Collections GOV2 and ClueWeb09 (Category B) contain roughly 25 and 50 million HTML documents, respectively. These documents were crawled from the web. In the case of GOV2 almost all pages were collected from websites in either the .gov or .us domains, but the ClueWeb09 crawl was not limited to any speciﬁc domain. ClueWeb09 is a partially sorted collection: on average it has runs of 3.7 thousand documents sorted by URLs. In GOV2, the average length of the sorted run is almost one. Thus, we use two ‡ https://github.com/lemire/SIMDCompressionAndIntersection. ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: SIMD

text: COMPRESSION

text: AND

text: THE

text: INTERSECTION

text: OF

text: SORTED

text: INTEGERS

text: Algorithm

text: The

text: SIMD

text: GALLOPING

text: algorithm

text: Require:

text: SIMD

text: architecture

text: with

text: T-integer

text: vectors

text: input:

text: two

text: non-empty

text: sorted

text: arrays

text: of

text: integers

text: r,

text: f

text: assume:

text: length(f)

text: is

text: divisible

text: by

text: T

text: x

text: initially

text: empty

text: dynamic

text: array

text: (our

text: answer)

text: j

text: for

text: i

text: length(r)

text: do

text: R

text: (r

text: r

text: r

text: i

text: i

text: i

text: ﬁnd

text: by

text: sequential

text: search

text: the

text: smallest

text: δ

text: such

text: that

text: f

text: r

text: for

text: δ

text: j+δ

text: i

text: length(f)

text: T,

text: if

text: return

text: x

text: ﬁnd

text: by

text: binary

text: search

text: the

text: smallest

text: δ

text: in

text: δ]

text: divisible

text: by

text: T

text: such

text: that

text: f

text: r

text: min

text: j+δmin

text: i

text: j

text: j

text: δ

text: min

text: F

text: (f

text: f

text: f

text: j

text: if

text: R

text: F

text: for

text: some

text: i

text: T

text: then

text: i

text: i

text: append

text: r

text: to

text: x

text: i

text: return

text: x

text: EXPERIMENTAL

text: RESULTS

text: We

text: assess

text: experimentally

text: the

text: unpacking

text: speed

text: with

text: integrated

text: differential

text: coding

text: the

text: decompression

text: speed

text: of

text: the

text: corresponding

text: schemes

text: the

text: beneﬁts

text: of

text: our

text: SIMD-based

text: intersection

text: schemes

text: and,

text: SIMD-accelerated

text: bitmap-list

text: hybrids

text: with

text: realistic

text: query

text: logs

text: and

text: inverted

text: indexes.

text: Software

text: All

text: our

text: software

text: is

text: freely

text: available

text: online

text: under

text: the

text: Apache

text: Software

text: License

text: The

text: code

text: is

text: written

text: in

text: C++

text: using

text: the

text: standard.

text: Our

text: code

text: builds

text: using

text: several

text: compilers

text: such

text: as

text: clang++

text: and

text: Intel

text: icpc

text: However,

text: we

text: use

text: GNU

text: GCC

text: on

text: a

text: Linux

text: PC

text: for

text: our

text: tests.

text: All

text: code

text: was

text: compiled

text: using

text: the

text: ﬂag.

text: We

text: implemented

text: scalar

text: schemes

text: (FASTPFOR

text: and

text: VARINT)

text: without

text: using

text: SIMD

text: instructions

text: and

text: with

text: the

text: scalar

text: equivalent

text: of

text: differential

text: coding.

text: Hardware

text: We

text: ran

text: all

text: our

text: experiments

text: on

text: an

text: Intel

text: Xeon

text: CPU

text: Sandy

text: Bridge)

text: running

text: at

text: GHz.

text: This

text: CPU

text: also

text: has

text: MB

text: of

text: cache

text: as

text: well

text: as

text: kB

text: and

text: kB

text: of

text: and

text: data

text: cache

text: per

text: core.

text: We

text: have

text: GB

text: of

text: RAM

text: running

text: quad-channel.

text: We

text: estimate

text: that

text: we

text: can

text: read

text: from

text: RAM

text: at

text: a

text: speed

text: of

text: billion

text: integers

text: per

text: second

text: and

text: from

text: cache

text: at

text: a

text: speed

text: of

text: billion

text: integers

text: per

text: second.

text: All

text: data

text: is

text: stored

text: in

text: RAM

text: so

text: that

text: disk

text: performance

text: is

text: irrelevant.

text: Real

text: data

text: To

text: fully

text: assess

text: our

text: results,

text: we

text: need

text: realistic

text: data

text: sets.

text: For

text: this

text: purpose,

text: we

text: use

text: posting

text: lists

text: extracted

text: from

text: the

text: TREC

text: collections

text: (Category

text: B)

text: and

text: Collections

text: and

text: (Category

text: B)

text: contain

text: roughly

text: and

text: million

text: HTML

text: documents,

text: respectively.

text: These

text: documents

text: were

text: crawled

text: from

text: the

text: web.

text: In

text: the

text: case

text: of

text: almost

text: all

text: pages

text: were

text: collected

text: from

text: websites

text: in

text: either

text: the

text: .gov

text: or

text: .us

text: domains,

text: but

text: the

text: crawl

text: was

text: not

text: limited

text: to

text: any

text: speciﬁc

text: domain.

text: is

text: a

text: partially

text: sorted

text: collection:

text: on

text: average

text: it

text: has

text: runs

text: of

text: thousand

text: documents

text: sorted

text: by

text: URLs.

text: In

text: the

text: average

text: length

text: of

text: the

text: sorted

text: run

text: is

text: almost

text: one.

text: Thus,

text: we

text: use

text: two

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##