text: Since 2/dαs+1 < g and we ensure that our construction of EJ satisﬁes the hypotheses of s+1 (cid:96)s ∞ Lemma 6, this sum is an upper bound on µ (B , , α ). Thus, we have ensured that J ds+1 (cid:96)s+1 ∞ µ (E ) µ (B , , α ) < J· ks , J ds+1 (cid:96)s+1 4 2s+1 which is analogous to how we chose d in the proof of Theorem 1. s+1 Let m be greater than f((cid:96) , m ) and suﬃciently large so that a binary sequence of (cid:96)s+1 − s (cid:96)s length log(m )a(b β ) can describe these parameters together with the ﬁrst s steps of (cid:96)s+1 s+1 the construction. Subrecursion: substage (cid:96). Proceed by recursion on substages (cid:96) starting with initial value (cid:96) +1. Suppose that the termination condition for stage s+1 was not realized during substage s− − − (cid:96) 1. Deﬁne a to be equal to α and deﬁne b to be equal β + (cid:15) (1 1/2(cid:96) (cid:96)s). (cid:96) s+1 (cid:96)+2 s+1 s+1 If (cid:96) = (cid:96) + 1, then value of m was assigned in the previous paragraph. Otherwise, let m s (cid:96)s+1 (cid:96) be larger than f((cid:96), m − ). Note that f is deﬁned in terms the values of (cid:126)q and (cid:126)a up to (cid:96) and (cid:96) 1 that the values of (cid:126)q are deﬁned in terms of (cid:126)a and m(cid:126) up to (cid:96) and (cid:126)b up to (cid:96) + 2, all of which have been determined before the evaluation of f. Termination of the subrecursion. Note that µ (E ) is determined at the end of step s, J ks since it is equal to the number of level-k intervals in E divided by the number of level-(k ) s ks s intervals in EJ. We say that step (cid:96) satisﬁes the termination condition for stage s + 1 when E there is a k between (cid:96) and (cid:96) such that there is an S in the level k of ((cid:126)q, m(cid:126) , a) satisfying the s following conditions. • ∗ There is a d in (d , d + (cid:96)) such that the µ -measure of the set of intervals in EJ which have non-empty in(cid:88)sterssection with B(d , d∗,Jα ) ∩ S is less than (cid:96) s s · µ (S) − j J 4 . 2s ≥ ∗ (2j)αs+1 j d • ∗ There is a d in (d , d + (cid:96)) such that the µ -measure of the set of intervals in EJ which have non-em(cid:88)sp+t1y ins+te1rsection with B(d ,Jd∗, α ) is less than (cid:96) s+1 s+1 · µ (S) − j J 4 . 2s+1 ≥ ∗ (2j)αs+1 j d • The µ measure of the union of the set of intervals in S which contain at least one J endpoint of an interval in B(d , d , α ) is less than s s+1 s+1 µ (S) J . 2s+1 If the termination condition is realized for (cid:96), then we set (cid:96) equal to (cid:96), and set k and s+1 s+1 E to have values equal to those in the least pair k and S which satisfy the termination ks+1 condition. 17 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Since

text: g

text: and

text: we

text: ensure

text: that

text: our

text: construction

text: of

text: EJ

text: satisﬁes

text: the

text: hypotheses

text: of

text: Lemma

text: this

text: sum

text: is

text: an

text: upper

text: bound

text: on

text: µ

text: (B

text: α

text: Thus,

text: we

text: have

text: ensured

text: that

text: J

text: µ

text: (E

text: µ

text: (B

text: α

text: J·

text: ks

text: J

text: which

text: is

text: analogous

text: to

text: how

text: we

text: chose

text: d

text: in

text: the

text: proof

text: of

text: Theorem

text: Let

text: m

text: be

text: greater

text: than

text: m

text: and

text: suﬃciently

text: large

text: so

text: that

text: a

text: binary

text: sequence

text: of

text: s

text: length

text: log(m

text: )a(b

text: β

text: can

text: describe

text: these

text: parameters

text: together

text: with

text: the

text: ﬁrst

text: s

text: steps

text: of

text: the

text: construction.

text: Subrecursion:

text: substage

text: Proceed

text: by

text: recursion

text: on

text: substages

text: starting

text: with

text: initial

text: value

text: Suppose

text: that

text: the

text: termination

text: condition

text: for

text: stage

text: was

text: not

text: realized

text: during

text: substage

text: s−

text: Deﬁne

text: a

text: to

text: be

text: equal

text: to

text: α

text: and

text: deﬁne

text: b

text: to

text: be

text: equal

text: β

text: If

text: then

text: value

text: of

text: m

text: was

text: assigned

text: in

text: the

text: previous

text: paragraph.

text: Otherwise,

text: let

text: m

text: s

text: be

text: larger

text: than

text: m

text: Note

text: that

text: f

text: is

text: deﬁned

text: in

text: terms

text: the

text: values

text: of

text: and

text: up

text: to

text: and

text: that

text: the

text: values

text: of

text: are

text: deﬁned

text: in

text: terms

text: of

text: and

text: up

text: to

text: and

text: up

text: to

text: all

text: of

text: which

text: have

text: been

text: determined

text: before

text: the

text: evaluation

text: of

text: f.

text: Termination

text: of

text: the

text: subrecursion.

text: Note

text: that

text: µ

text: (E

text: is

text: determined

text: at

text: the

text: end

text: of

text: step

text: s,

text: J

text: ks

text: since

text: it

text: is

text: equal

text: to

text: the

text: number

text: of

text: level-k

text: intervals

text: in

text: E

text: divided

text: by

text: the

text: number

text: of

text: level-(k

text: s

text: ks

text: s

text: intervals

text: in

text: EJ.

text: We

text: say

text: that

text: step

text: satisﬁes

text: the

text: termination

text: condition

text: for

text: stage

text: s

text: when

text: E

text: there

text: is

text: a

text: k

text: between

text: and

text: such

text: that

text: there

text: is

text: an

text: S

text: in

text: the

text: level

text: k

text: of

text: a)

text: satisfying

text: the

text: s

text: following

text: conditions.

text: There

text: is

text: a

text: d

text: in

text: (d

text: d

text: such

text: that

text: the

text: µ

text: -measure

text: of

text: the

text: set

text: of

text: intervals

text: in

text: EJ

text: which

text: have

text: non-empty

text: with

text: B(d

text: d∗,Jα

text: S

text: is

text: less

text: than

text: s

text: s

text: µ

text: (S)

text: j

text: J

text: j

text: d

text: There

text: is

text: a

text: d

text: in

text: (d

text: d

text: such

text: that

text: the

text: µ

text: -measure

text: of

text: the

text: set

text: of

text: intervals

text: in

text: EJ

text: which

text: have

text: with

text: B(d

text: ,Jd∗,

text: α

text: is

text: less

text: than

text: µ

text: (S)

text: j

text: J

text: j

text: d

text: The

text: µ

text: measure

text: of

text: the

text: union

text: of

text: the

text: set

text: of

text: intervals

text: in

text: S

text: which

text: contain

text: at

text: least

text: one

text: J

text: endpoint

text: of

text: an

text: interval

text: in

text: B(d

text: d

text: α

text: is

text: less

text: than

text: s

text: µ

text: (S)

text: J

text: If

text: the

text: termination

text: condition

text: is

text: realized

text: for

text: then

text: we

text: set

text: equal

text: to

text: and

text: set

text: k

text: and

text: E

text: to

text: have

text: values

text: equal

text: to

text: those

text: in

text: the

text: least

text: pair

text: k

text: and

text: S

text: which

text: satisfy

text: the

text: termination

text: condition.

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: [17] J. H. Lutz. Gales and the constructive dimension of individual sequences. In Automata, languages and programming (Geneva, 2000), volume 1853 of Lecture Notes in Comput. Sci., pages 902–913. Springer, Berlin, 2000. [18] J. Reimann and F. Stephan. Eﬀective Hausdorﬀ dimension. In Logic Colloquium ’01, volume 20 of Lect. Notes Log., pages 369–385. Assoc. Symbol. Logic, Urbana, IL, 2005. [19] L. Staiger. The Kolmogorov complexity of real numbers. Theoretical Computer Science, 284(2):455–466, 2002. Verónica Becher Departamento de Computación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires. Pabellón I, Ciudad Universitaria, (1428) Buenos Aires, Argentina. Also, CONICET Argentina. Email: vbecher@dc.uba.ar Jan Reimann Department of Mathematics Penn State University. 318B McAllister, University Park, PA 16802 Email: jan.reimann@psu.edu Theodore A. Slaman The University of California, Berkeley, Department of Mathematics. 719 Evans Hall #3840, Berkeley, CA 94720-3840 USA Email: slaman@math.berkeley.edu 20

label: reference

text: J.

text: H.

text: Lutz.

text: Gales

text: and

text: the

text: constructive

text: dimension

text: of

text: individual

text: sequences.

text: In

text: Automata,

text: languages

text: and

text: programming

text: (Geneva,

text: volume

text: of

text: Lecture

text: Notes

text: in

text: Comput.

text: Sci.,

text: pages

text: Springer,

text: Berlin,

text: J.

text: Reimann

text: and

text: F.

text: Stephan.

text: Eﬀective

text: Hausdorﬀ

text: dimension.

text: In

text: Logic

text: Colloquium

text: volume

text: of

text: Lect.

text: Notes

text: Log.,

text: pages

text: Assoc.

text: Symbol.

text: Logic,

text: Urbana,

text: IL,

text: L.

text: Staiger.

text: The

text: Kolmogorov

text: complexity

text: of

text: real

text: numbers.

text: Theoretical

text: Computer

text: Science,

text: Verónica

label: paragraph

text: Becher

text: Departamento

text: de

text: Computación,

text: Facultad

text: de

text: Ciencias

text: Exactas

text: y

text: Naturales,

text: Universidad

text: de

text: Buenos

text: Aires.

text: Pabellón

text: I,

text: Ciudad

text: Universitaria,

text: Buenos

text: Aires,

text: Argentina.

text: Also,

text: CONICET

text: Argentina.

text: Email:

text: vbecher@dc.uba.ar

text: Jan

text: Reimann

text: Department

text: of

text: Mathematics

text: Penn

text: State

text: University.

text: McAllister,

text: University

text: Park,

text: PA

text: Email:

text: jan.reimann@psu.edu

text: Theodore

text: A.

text: Slaman

text: The

text: University

text: of

text: California,

text: Berkeley,

text: Department

text: of

text: Mathematics.

text: Evans

text: Hall

text: Berkeley,

text: CA

text: USA

text: Email:

text: slaman@math.berkeley.edu


text: mod q . Thus, the intervals of E are of length 2/mak and are separated by gaps of length at k k k least q − 2 k g = . k m mak k k Let i be the number of intervals of E contained in a single interval of E − . By construction k k k 1 i = m /q and for every k > 1, 1 1 1 ≥ 1 2 1 m i m = k , (1) k 2 (mk−1)ak−1 qk k (mk−1)ak−1qk which represents half of the product of the length of an interval in E − and the number of k 1 intervals with centers p/m , where p is an integer with ﬁxed residue modulo q . This estimate k k applies provided that q is less than m and m is suﬃciently large with respect to the value k k k of m − . k 1 | | ≤ Now, we suppose that S is a subinterval of [0, 1] of length S g and we estimate µ(S). ≤ | | 1 Let k be the integer such that g S < g − . The number of k-level intervals that k k 1 intersect S is • − at most i , since S intersects at most one (k 1)-level interval, k • | | ≤ | | at most 2 + S m /q 4 S m /q , by an estimate similar to that for the lower bound k k k k on i . k × × Each k-level interval has measure 1/(i . . . i ). We have that 1 k | | ≤ min(4 S m /q , i ) µ(S) × k× k k (2) i . . . i 1 k | | − ≤ (4 S m×k/qk)×bk i1k bk (as b ∈ [0, 1]) k i . . . i 1 k 4bkmbk | | = × × k S bk (i . . . i − ) ibkqbk 1 k 1 k k ≤ 1ma11q2 ma22q3 . . . makk−−22qk−1 (cid:32)4bkmbkk |S(cid:33)|bk (by (1)) m2 m3 mk−1 ibkqbk k k ≤ ma11q2 ma22(cid:0)q3 . . . makk−−22qk−1 m(cid:1)akk−−11qk bk mbkk 4bk |S|bk m2 m3 mk−1 mk qbk k · · · − − − | | = (q q − ) ma1ma2 1 . . . mak−−2 1 4bkmak−−1bk 1 S bk. (3) 2 k 1 1 2 k 2 k 1 | | We want to ensure that for all such S, µ(S) < S bk, from which we may infer that | | µ(S) < S s for all s in [0, b ]. Thus, it suﬃces to show that there is a suitable growth function (cid:0) k (cid:1) f for the sequence m(cid:126) , and there is a suitable sequence of values for (cid:126)q such that · · · − − − (q q − q − ) ma1ma2 1 . . . mak−−2 1 4bkmak−−1bk 1 < 1. 2 k 2 k 1 1 2 k 2 k 1 7 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: mod

text: q

text: Thus,

text: the

text: intervals

text: of

text: E

text: are

text: of

text: length

text: and

text: are

text: separated

text: by

text: gaps

text: of

text: length

text: at

text: k

text: k

text: k

text: least

text: q

text: k

text: g

text: k

text: m

text: mak

text: k

text: k

text: Let

text: i

text: be

text: the

text: number

text: of

text: intervals

text: of

text: E

text: contained

text: in

text: a

text: single

text: interval

text: of

text: E

text: By

text: construction

text: k

text: k

text: k

text: i

text: m

text: /q

text: and

text: for

text: every

text: k

label: equation

text: m

text: i

text: m

text: k

text: k

text: qk

text: k

text: which

text: represents

text: half

text: of

text: the

text: product

text: of

text: the

text: length

text: of

text: an

text: interval

text: in

text: E

text: and

text: the

text: number

text: of

text: k

text: intervals

text: with

text: centers

text: p/m

text: where

text: p

text: is

text: an

text: integer

text: with

text: ﬁxed

text: residue

text: modulo

text: q

text: This

text: estimate

text: k

text: k

text: applies

text: provided

text: that

text: q

text: is

text: less

text: than

text: m

text: and

text: m

text: is

text: suﬃciently

text: large

text: with

text: respect

text: to

text: the

text: value

text: k

text: k

text: k

text: of

text: m

text: k

text: Now,

text: we

text: suppose

text: that

text: S

text: is

text: a

text: subinterval

text: of

text: of

text: length

text: S

text: g

text: and

text: we

text: estimate

text: µ(S).

text: Let

text: k

text: be

text: the

text: integer

text: such

text: that

text: g

text: S

text: g

text: The

text: number

text: of

text: k-level

text: intervals

text: that

text: k

text: k

text: intersect

text: S

text: is

text: at

text: most

text: i

text: since

text: S

text: intersects

text: at

text: most

text: one

text: (k

text: interval,

text: k

text: at

text: most

text: S

text: m

text: /q

text: S

text: m

text: /q

text: by

text: an

text: estimate

text: similar

text: to

text: that

text: for

text: the

text: lower

text: bound

text: k

text: k

text: k

text: k

text: on

text: i

text: k

text: Each

text: k-level

text: interval

text: has

text: measure

text: i

text: We

text: have

text: that

text: k

text: S

text: m

text: /q

text: i

text: µ(S)

text: k×

text: k

text: k

text: i

text: i

text: k

text: S

text: m×k/qk)×bk

text: bk

text: (as

text: b

text: k

text: i

text: i

text: k

text: k

text: S

text: bk

text: (i

text: i

text: ibkqbk

text: k

text: k

text: k

text: (by

text: ibkqbk

text: k

text: k

text: bk

text: mbkk

text: |S|bk

text: mk

text: qbk

text: k

text: (q

text: q

text: S

text: bk.

text: k

text: k

text: k

text: We

text: want

text: to

text: ensure

text: that

text: for

text: all

text: such

text: S,

text: µ(S)

text: S

text: bk,

text: from

text: which

text: we

text: may

text: infer

text: that

text: µ(S)

text: S

text: s

text: for

text: all

text: s

text: in

text: b

text: Thus,

text: it

text: suﬃces

text: to

text: show

text: that

text: there

text: is

text: a

text: suitable

text: growth

text: function

text: k

text: f

text: for

text: the

text: sequence

text: and

text: there

text: is

text: a

text: suitable

text: sequence

text: of

text: values

text: for

text: such

text: that

text: (q

text: q

text: q

text: k

text: k

text: k

text: k

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: Theory of noise suppression in Λ-type quantum memories by means of a cavity J. Nunn1, S. Thomas1,2, J. H. D. Munns1,2, K. T. Kaczmarek1, C. Qiu1,3, A. Feizpour1, E. Poem1, B. Brecht1, D. J. Saunders1, P. M. Ledingham1, Dileep V. Reddy4, M. G. Raymer4, I. A. Walmsley1 1Clarendon Laboratory, University of Oxford, Parks Road, Oxford OX1 3PU, United Kingdom 2 QOLS, Blackett Laboratory, Imperial College London, London SW7 2BW, UK 3Department of Physics, Quantum Institute for Light and Atoms, State Key Laboratory of Precision Spectroscopy, East China Normal University, Shanghai 200062, People’s Republic of China 4Oregon Center for Optics, Department of Physics, University of Oregon, Eugene, Oregon 97403, USA Quantum memories, capable of storing single photons or other quantum states of light, to be retrieved on-demand, oﬀer a route to large-scale quantum information processing with light. A promising class of memories is based on far-oﬀ-resonant Raman absorption in ensembles of Λ-type atoms. However at room temperature these systems exhibit unwanted four-wave mixing, which is prohibitive for applications at the single-photon level. Here we show how this noise can be suppressed by placing the storage medium inside a moderate-ﬁnesse optical cavity, thereby removing the main roadblock hindering this approach to quantum memory. PACS numbers: 42.50.Ex, 42.50.Ct, 42.50.-p I. INTRODUCTION that four-wave mixing can be suppressed by placing the memory storage medium inside an optical cavity [31]. In this paper we present a theoretical analysis of this The need for low-loss active switching or synchronisa- method of noise suppression. We show that a moderate- tion of non-deterministic operations in a linear-optical ﬁnesse cavity can, under realistic conditions, suppress quantum information processor has emerged over the four-wave mixing noise to a negligible level, while at the past few years as a sine qua non for the development same time dramatically reducing the footprint and en- of large-scale photonics-based quantum technologies [1– ergy requirements of the memory compared to free-space 5]. Experiments with optical switches are making rapid implementations, and maintaining broadband operation. progress [6–9]. Quantum memories based on the coher- We also point out that the cavity-enhanced memory is ent and reversible absorption of photons in an atomic nearly perfectly-temporal-mode-selective [32], making it ensemble are being developed by many groups as an al- an appealing system for chronocyclic encodings of quan- ternative to optical switching [10–14], with impressive tum information [33]. demonstrations of the preservation of quantum correla- II. FOUR WAVE MIXING IN Λ-MEMORIES tions and of temporal synchronisation of photons, using cold atoms [15] and cold doped crystals [16]. An impor- tant class of memory protocol is based on stimulated two- Although the detailed dynamics in Λ-memories diﬀer photon transitions in a Λ-type atomic ensemble, where depending on the protocol employed (EIT, Raman, Λ- a bright control laser ﬁeld couples the incident signal GEM), all such memories share the same kinematical photons to a ground-state coherence in the atoms [17]. description, shown in Fig. 1. That is, an ensemble of Memories based on electromagnetically-induced trans- Λ-type atoms are prepared in one of their two ground parency (EIT) [18–20] and on far-oﬀ-resonant Raman states, and then an incident signal ﬁeld is coupled to the absorption [21–23] both fall into this category, and in empty storage state by a strong control ﬁeld tuned into the following we will refer to all such memories as Λ- two-photon resonance with the signal. Four-wave mixing memories. Λ-memories in cold atoms have successfully arises in this system when the strong control ﬁeld couples stored single photons, but at room-temperature it was to the ground state and drives oﬀ-resonant spontaneous found that ﬂuorescence noise [24] and four-wave mix- Raman scattering (in the diagram this is anti-Stokes scat- ing [25] became problematic. Our group recently in- tering because we have chosen to pump the atoms into terfaced a single-photon source with a Raman memory the higher of the two ground state levels). The scattered and measured the photon number statistics of the re- anti-Stokes ﬁeld is at a diﬀerent frequency from the sig- trieved ﬁelds [26]. There it was found that while ﬂuo- nal ﬁeld and does not directly contribute any noise. But rescence noise was negligible for oﬀ-resonant storage of each scattering event is accompanied by one of the atoms | (cid:105) | (cid:105) short pulses, the thermal noise contributed by four-wave switching state from 1 to 3 . That is, the scattering mixing destroyed the anti-bunching characteristic of sin- spontaneously generates excitations of the ground-state gle photons. Four-wave mixing noise is therefore the key coherence that are indistinguishable from the excitations roadblock preventing the implementation of Λ-memories produced by successful storage of the signal ﬁeld. When at room temperature [27, 28]. A number of solutions the memory is read-out, these excitations are retrieved have been suggested [29, 30]. We recently demonstrated as noise. The nomenclature ‘four-wave mixing’ applies

text: Theory

label: title

text: of

text: noise

text: suppression

text: in

text: Λ-type

text: quantum

text: memories

text: by

text: means

text: of

text: a

text: cavity

text: J.

label: author

text: S.

text: J.

text: H.

text: D.

text: K.

text: T.

text: C.

text: A.

text: E.

text: B.

text: D.

text: J.

text: P.

text: M.

text: Dileep

text: V.

text: M.

text: G.

text: I.

text: A.

text: Laboratory,

text: University

text: of

text: Oxford,

text: Parks

text: Road,

text: Oxford

text: United

text: Kingdom

text: QOLS,

text: Blackett

text: Laboratory,

text: Imperial

text: College

text: London,

text: London

text: UK

text: of

text: Physics,

text: Quantum

text: Institute

text: for

text: Light

text: and

text: Atoms,

text: State

text: Key

text: Laboratory

text: of

text: Precision

text: Spectroscopy,

text: East

text: China

text: Normal

text: University,

text: Shanghai

text: People’s

text: Republic

text: of

text: China

text: Center

text: for

text: Optics,

text: Department

text: of

text: Physics,

text: University

text: of

text: Oregon,

text: Eugene,

text: Oregon

text: USA

text: Quantum

text: memories,

text: capable

text: of

text: storing

text: single

text: photons

text: or

text: other

text: quantum

text: states

text: of

text: light,

text: to

text: be

text: retrieved

text: on-demand,

text: oﬀer

text: a

text: route

text: to

text: large-scale

text: quantum

text: information

text: processing

text: with

text: light.

text: A

text: promising

text: class

text: of

text: memories

text: is

text: based

text: on

text: far-oﬀ-resonant

text: Raman

text: absorption

text: in

text: ensembles

text: of

text: Λ-type

text: atoms.

text: However

text: at

text: room

text: temperature

text: these

text: systems

text: exhibit

text: unwanted

text: four-wave

text: mixing,

text: which

text: is

text: prohibitive

text: for

text: applications

text: at

text: the

text: single-photon

text: level.

text: Here

text: we

text: show

text: how

text: this

text: noise

text: can

text: be

text: suppressed

text: by

text: placing

text: the

text: storage

text: medium

text: inside

text: a

text: moderate-ﬁnesse

text: optical

text: cavity,

text: thereby

text: removing

text: the

text: main

text: roadblock

text: hindering

text: this

text: approach

text: to

text: quantum

text: memory.

text: PACS

text: numbers:

text: I.

text: INTRODUCTION

text: that

text: four-wave

text: mixing

text: can

text: be

text: suppressed

text: by

text: placing

text: the

text: memory

text: storage

text: medium

text: inside

text: an

text: optical

text: cavity

text: In

text: this

text: paper

text: we

text: present

text: a

text: theoretical

text: analysis

text: of

text: this

text: The

text: need

text: for

text: low-loss

text: active

text: switching

text: or

text: synchronisa-

text: method

text: of

text: noise

text: suppression.

text: We

text: show

text: that

text: a

text: moderate-

text: tion

text: of

text: non-deterministic

text: operations

text: in

text: a

text: linear-optical

text: ﬁnesse

text: cavity

text: can,

text: under

text: realistic

text: conditions,

text: suppress

text: quantum

text: information

text: processor

text: has

text: emerged

text: over

text: the

text: four-wave

text: mixing

text: noise

text: to

text: a

text: negligible

text: level,

text: while

text: at

text: the

text: past

text: few

text: years

text: as

text: a

text: sine

text: qua

text: non

text: for

text: the

text: development

text: same

text: time

text: dramatically

text: reducing

text: the

text: footprint

text: and

text: en-

text: of

text: large-scale

text: photonics-based

text: quantum

text: technologies

text: ergy

text: requirements

text: of

text: the

text: memory

text: compared

text: to

text: free-space

text: Experiments

text: with

text: optical

text: switches

text: are

text: making

text: rapid

text: implementations,

text: and

text: maintaining

text: broadband

text: operation.

text: progress

text: Quantum

text: memories

text: based

text: on

text: the

text: coher-

text: We

text: also

text: point

text: out

text: that

text: the

text: cavity-enhanced

text: memory

text: is

text: ent

text: and

text: reversible

text: absorption

text: of

text: photons

text: in

text: an

text: atomic

text: nearly

text: perfectly-temporal-mode-selective

text: making

text: it

text: ensemble

text: are

text: being

text: developed

text: by

text: many

text: groups

text: as

text: an

text: al-

text: an

text: appealing

text: system

text: for

text: chronocyclic

text: encodings

text: of

text: quan-

text: ternative

text: to

text: optical

text: switching

text: with

text: impressive

text: tum

text: information

text: demonstrations

text: of

text: the

text: preservation

text: of

text: quantum

text: correla-

text: II.

text: FOUR

text: WAVE

text: MIXING

text: IN

text: Λ-MEMORIES

text: tions

text: and

text: of

text: temporal

text: synchronisation

text: of

text: photons,

text: using

text: cold

text: atoms

text: and

text: cold

text: doped

text: crystals

text: An

text: impor-

text: tant

text: class

text: of

text: memory

text: protocol

text: is

text: based

text: on

text: stimulated

text: two-

text: Although

text: the

text: detailed

text: dynamics

text: in

text: Λ-memories

text: diﬀer

text: photon

text: transitions

text: in

text: a

text: Λ-type

text: atomic

text: ensemble,

text: where

text: depending

text: on

text: the

text: protocol

text: employed

text: (EIT,

text: Raman,

text: Λ-

text: a

text: bright

text: control

text: laser

text: ﬁeld

text: couples

text: the

text: incident

text: signal

text: GEM),

text: all

text: such

text: memories

text: share

text: the

text: same

text: kinematical

text: photons

text: to

text: a

text: ground-state

text: coherence

text: in

text: the

text: atoms

text: description,

text: shown

text: in

text: Fig.

text: That

text: is,

text: an

text: ensemble

text: of

text: Memories

text: based

text: on

text: electromagnetically-induced

text: trans-

text: Λ-type

text: atoms

text: are

text: prepared

text: in

text: one

text: of

text: their

text: two

text: ground

text: parency

text: (EIT)

text: and

text: on

text: far-oﬀ-resonant

text: Raman

text: states,

text: and

text: then

text: an

text: incident

text: signal

text: ﬁeld

text: is

text: coupled

text: to

text: the

text: absorption

text: both

text: fall

text: into

text: this

text: category,

text: and

text: in

text: empty

text: storage

text: state

text: by

text: a

text: strong

text: control

text: ﬁeld

text: tuned

text: into

text: the

text: following

text: we

text: will

text: refer

text: to

text: all

text: such

text: memories

text: as

text: Λ-

text: two-photon

text: resonance

text: with

text: the

text: signal.

text: Four-wave

text: mixing

text: memories.

text: Λ-memories

text: in

text: cold

text: atoms

text: have

text: successfully

text: arises

text: in

text: this

text: system

text: when

text: the

text: strong

text: control

text: ﬁeld

text: couples

text: stored

text: single

text: photons,

text: but

text: at

text: room-temperature

text: it

text: was

text: to

text: the

text: ground

text: state

text: and

text: drives

text: oﬀ-resonant

text: spontaneous

text: found

text: that

text: ﬂuorescence

text: noise

text: and

text: four-wave

text: mix-

text: Raman

text: scattering

text: (in

text: the

text: diagram

text: this

text: is

text: anti-Stokes

text: scat-

text: ing

text: became

text: problematic.

text: Our

text: group

text: recently

text: in-

text: tering

text: because

text: we

text: have

text: chosen

text: to

text: pump

text: the

text: atoms

text: into

text: terfaced

text: a

text: single-photon

text: source

text: with

text: a

text: Raman

text: memory

text: the

text: higher

text: of

text: the

text: two

text: ground

text: state

text: levels).

text: The

text: scattered

text: and

text: measured

text: the

text: photon

text: number

text: statistics

text: of

text: the

text: re-

text: anti-Stokes

text: ﬁeld

text: is

text: at

text: a

text: diﬀerent

text: frequency

text: from

text: the

text: sig-

text: trieved

text: ﬁelds

text: There

text: it

text: was

text: found

text: that

text: while

text: ﬂuo-

text: nal

text: ﬁeld

text: and

text: does

text: not

text: directly

text: contribute

text: any

text: noise.

text: But

text: rescence

text: noise

text: was

text: negligible

text: for

text: oﬀ-resonant

text: storage

text: of

text: each

text: scattering

text: event

text: is

text: accompanied

text: by

text: one

text: of

text: the

text: atoms

text: short

text: pulses,

text: the

text: thermal

text: noise

text: contributed

text: by

text: four-wave

text: switching

text: state

text: from

text: to

text: That

text: is,

text: the

text: scattering

text: mixing

text: destroyed

text: the

text: anti-bunching

text: characteristic

text: of

text: sin-

text: spontaneously

text: generates

text: excitations

text: of

text: the

text: ground-state

text: gle

text: photons.

text: Four-wave

text: mixing

text: noise

text: is

text: therefore

text: the

text: key

text: coherence

text: that

text: are

text: indistinguishable

text: from

text: the

text: excitations

text: roadblock

text: preventing

text: the

text: implementation

text: of

text: Λ-memories

text: produced

text: by

text: successful

text: storage

text: of

text: the

text: signal

text: ﬁeld.

text: When

text: at

text: room

text: temperature

text: A

text: number

text: of

text: solutions

text: the

text: memory

text: is

text: read-out,

text: these

text: excitations

text: are

text: retrieved

text: have

text: been

text: suggested

text: We

text: recently

text: demonstrated

text: as

text: noise.

text: The

text: nomenclature

text: ‘four-wave

text: mixing’

text: applies


text: 7 (cid:18) (cid:19) (cid:12) (cid:12) control pulse, which, after some rather lengthy calcula- and the signal-to-noise ratio (cid:12) (cid:12) (cid:12) (cid:12) tions ca(cid:104)n be writt(cid:105)en as, (cid:26) (cid:104) (cid:105) (cid:12) (cid:12) 2 − 4 | | Γ 2 1 SNR = ζ N κ 2 a | | . 3 27 in,1 Γ x 2 − | | − | | s N2 g(2) 1 = rχC 4 g(2) 1 N2 C Eκ 4 out,2 out,2 s in,1 in(cid:27),1 s The autocorrelation (again for incident single photons in +|C x|4h(ζ) (27) the high noise-suppress(cid:18)ion regime)(cid:19)is found to be a | | (cid:48) +2N C C xκ 2h (ζ) , in,1 s a 34 − 14 1 g(2) = ζ . (30) out,2 9 81 SNR where we deﬁned the functions In general the control ﬁeld Ω(t) can be shaped so as | | − to achieve κ = 1 and maximise the SNR. In the weak 1 E − E Σ − coupling limit the requirement to shape the signal and h(ζ) = 4 2 + E4 + (2ζE 1), | | (cid:28) ζ3 ζ2 ζ4 control pulses is relaxed, because when f 1 the opti- ∗ (cid:48) EΣ mal input mode ef (cid:15) is approximately ﬂat. If the signal h (ζ) = E4 + . (28) and control pulse shapes derive from a common source, ζ3 ∝ so that ψ (t) Ω(t) and ψ ((cid:15)) = 1, we then achieve − in − ∗ ≈ in κ = 1 3f 1f 1. Of particular interest is the case of storing single pho- 2 X4. STRONG COUPLING ton Fock states, for which g(2) = 0, and we obtain (cid:8) in,1 On the other hand it is also instructive to consider the (cid:2) (cid:3)(cid:9) (cid:29) go(2u)t,2 = 2|(cid:2)Nin,1||κCsCax|2[E2g(ζ) + h(cid:3)(cid:48)(ζ)] chaa(cid:48)sveeoE→f v→ery1s/tζr,ogn(gζc)o→upl1i/nζg,, wΣh→en1ζ, h(ζ1). →In 2th(ζat−ca1s)e/ζw4e, + C x 4 g(ζ)2 + h(ζ) h (ζ) 2/ζ4, and the mem(cid:12) ory eﬃ(cid:12)ciency tends to a (cid:12) (cid:12) × | | | | − (cid:12) (cid:12) N κC E 2 + C x 2g(ζ) 2 . (cid:12) (cid:12) in,1 s a → rχC2κ 2 η s ≤ tot ζ Note that for incident single photons, N 1 is to be | | in,1 | | C 4 interpreted as the average number of photons per pulse, = rχκ 2 s . (31) ζ2 including any losses prior to the memory. For a heralded photon source [49], Nin,1 is therefore the heralding eﬃ- −→ ciency of the source. For very strong coupling, we ﬁnd g(2) 1, indepen- | | (cid:28) out,2 If we achieve strong noise suppression, so that x 2 dent of the noise suppression factor x. In this case the Nin,1, then the autocor(cid:20)relation can b(cid:21)e written as four-wave mixing gain dominates and the system has ef- fectively become a Raman laser. To remain in the regime where the cavity suppresses the four-wave mixing, we (cid:48) | | (cid:28) g(2) = 2 1 + h (ζ) 1 . (29) should have x Nin,1(cid:12)(cid:12)/ζ, (cid:12)(cid:12)in which case from (29) we out,2 E2g(ζ) SNR obtain (cid:12) (cid:12) (cid:12) (cid:12) | | Γ 2 2 x 2ζ IX. WEAK COUPLING LIMIT g(2) = s | | . out,2 Γ N κ 2 a in,1 The expressions for the eﬃciency, signal-to-noise ratio Here the autocorrelation rises linearly with the coupling and autocorrelation simplify in the limit of weak cou- parameter ζ. To achieve low-noise operation of the mem- | | (cid:28) (cid:28) pling, when C 1, so that ζ 1. In this limit we ory we therefore seek the smallest coupling strength ζ for s,a (cid:46) → − obtain, to ﬁrst order in ζ (valid for ζ 0.2), E 1 1ζ, which the eﬃciency saturates. → − → − → − 2 Σ 1ζ3 1ζ4, g(ζ) 3 7ζ, h(ζ) 11 13ζ, XI. COMPARISON WITH PREVIOUS RESULTS (cid:48) →3 −3 2 6 6 5 h (ζ) 4 5ζ(cid:20). The number of ret(cid:18)rieved ph(cid:19)otons is(cid:21) 3 2 then given by Cavity-enhanced Λ-memories have been analysed pre- viously [35, 50, 51]. To compare with those works, | | − | | 3 − 7 | | we consider the case that there is no four-wave mixing N = rχC 2 N (1 ζ) C κ 2 + ζ C x 2 , → ∞ out,2 s in,1 s 2 6 a (equivalent to the limit δ so that Ca = 0), and we assume the signal ﬁeld to be tuned to the empty- with the eﬃciency given by cavity resonance with k L = 0 mod(2π). Finally we as- s sume that there are no interface or scattering losses inside − | | η = (1 ζ) rχC2κ 2, the cavity, other than atomic absorption contained in κ . tot s s ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: control

text: pulse,

text: which,

text: after

text: some

text: rather

text: lengthy

text: calcula-

text: and

text: the

text: signal-to-noise

text: ratio

text: tions

text: be

text: as,

text: Γ

text: SNR

text: ζ

text: N

text: κ

text: a

text: Γ

text: x

text: s

text: rχC

text: C

text: Eκ

text: s

text: s

text: The

text: autocorrelation

text: (again

text: for

text: incident

text: single

text: photons

text: in

text: +|C

text: the

text: high

text: found

text: to

text: be

text: a

text: C

text: C

text: xκ

text: (ζ)

text: s

text: a

text: ζ

text: SNR

text: where

text: we

text: deﬁned

text: the

text: functions

text: In

text: general

text: the

text: control

text: ﬁeld

text: Ω(t)

text: can

text: be

text: shaped

text: so

text: as

text: to

text: achieve

text: κ

text: and

text: maximise

text: the

text: SNR.

text: In

text: the

text: weak

text: E

text: E

text: Σ

text: coupling

text: limit

text: the

text: requirement

text: to

text: shape

text: the

text: signal

text: and

text: h(ζ)

text: ζ3

text: ζ2

text: ζ4

text: control

text: pulses

text: is

text: relaxed,

text: because

text: when

text: f

text: the

text: opti-

text: EΣ

text: mal

text: input

text: mode

text: ef

text: is

text: approximately

text: ﬂat.

text: If

text: the

text: signal

text: h

text: (ζ)

text: and

text: control

text: pulse

text: shapes

text: derive

text: from

text: a

text: common

text: source,

text: ζ3

text: so

text: that

text: ψ

text: (t)

text: Ω(t)

text: and

text: ψ

text: we

text: then

text: achieve

text: in

text: in

text: κ

text: Of

text: particular

text: interest

text: is

text: the

text: case

text: of

text: storing

text: single

text: pho-

text: STRONG

text: COUPLING

text: ton

text: Fock

text: states,

text: for

text: which

text: and

text: we

text: obtain

text: On

text: the

text: other

text: hand

text: it

text: is

text: also

text: instructive

text: to

text: consider

text: the

text: →In

text: C

text: x

text: h(ζ)

text: h

text: (ζ)

text: and

text: the

text: ory

text: tends

text: to

text: a

text: N

text: κC

text: E

text: C

text: x

text: s

text: a

text: η

text: s

text: tot

text: ζ

text: Note

text: that

text: for

text: incident

text: single

text: photons,

text: N

text: is

text: to

text: be

text: C

text: interpreted

text: as

text: the

text: average

text: number

text: of

text: photons

text: per

text: pulse,

text: rχκ

text: s

text: ζ2

text: including

text: any

text: losses

text: prior

text: to

text: the

text: memory.

text: For

text: a

text: heralded

text: photon

text: source

text: is

text: therefore

text: the

text: heralding

text: eﬃ-

text: ciency

text: of

text: the

text: source.

text: For

text: very

text: strong

text: coupling,

text: we

text: ﬁnd

text: indepen-

text: If

text: we

text: achieve

text: strong

text: noise

text: suppression,

text: so

text: that

text: x

text: dent

text: of

text: the

text: noise

text: suppression

text: factor

text: x.

text: In

text: this

text: case

text: the

text: then

text: the

text: can

text: written

text: as

text: four-wave

text: mixing

text: gain

text: dominates

text: and

text: the

text: system

text: has

text: ef-

text: fectively

text: become

text: a

text: Raman

text: laser.

text: To

text: remain

text: in

text: the

text: regime

text: where

text: the

text: cavity

text: suppresses

text: the

text: four-wave

text: mixing,

text: we

text: h

text: (ζ)

text: should

text: have

text: x

text: which

text: case

text: from

text: we

text: SNR

text: obtain

text: Γ

text: x

text: 2ζ

text: IX.

text: WEAK

text: COUPLING

text: LIMIT

text: s

text: Γ

text: N

text: κ

text: a

text: The

text: expressions

text: for

text: the

text: eﬃciency,

text: signal-to-noise

text: ratio

text: Here

text: the

text: autocorrelation

text: rises

text: linearly

text: with

text: the

text: coupling

text: and

text: autocorrelation

text: simplify

text: in

text: the

text: limit

text: of

text: weak

text: cou-

text: parameter

text: ζ.

text: To

text: achieve

text: low-noise

text: operation

text: of

text: the

text: mem-

text: pling,

text: when

text: C

text: so

text: that

text: ζ

text: In

text: this

text: limit

text: we

text: ory

text: we

text: therefore

text: seek

text: the

text: smallest

text: coupling

text: strength

text: ζ

text: for

text: s,a

text: obtain,

text: to

text: ﬁrst

text: order

text: in

text: ζ

text: (valid

text: for

text: ζ

text: E

text: which

text: the

text: eﬃciency

text: saturates.

text: Σ

text: g(ζ)

text: h(ζ)

text: XI.

text: COMPARISON

text: WITH

text: PREVIOUS

text: RESULTS

text: →3

text: −3

text: h

text: (ζ)

text: The

text: number

text: of

text: then

text: given

text: by

text: Cavity-enhanced

text: Λ-memories

text: have

text: been

text: analysed

text: pre-

text: viously

text: To

text: compare

text: with

text: those

text: works,

text: we

text: consider

text: the

text: case

text: that

text: there

text: is

text: no

text: four-wave

text: mixing

text: N

text: rχC

text: N

text: ζ)

text: C

text: κ

text: ζ

text: C

text: x

text: s

text: s

text: a

text: (equivalent

text: to

text: the

text: limit

text: δ

text: so

text: that

text: Ca

text: and

text: we

text: assume

text: the

text: signal

text: ﬁeld

text: to

text: be

text: tuned

text: to

text: the

text: empty-

text: with

text: the

text: eﬃciency

text: given

text: by

text: cavity

text: resonance

text: with

text: k

text: L

text: Finally

text: we

text: as-

text: s

text: sume

text: that

text: there

text: are

text: no

text: interface

text: or

text: scattering

text: losses

text: inside

text: η

text: ζ)

text: the

text: cavity,

text: other

text: than

text: atomic

text: absorption

text: contained

text: in

text: κ

text: tot

text: s

text: s

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: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 70 50 40 PI_insert PI_insert PI_insert M queries/sec) 456000 PMMIaa_sssssettarreerceeh__isnesaerrcth M queries/sec) 3400 PMMIaa_sssssettarreerceeh__isnesaerrcth M queries/sec) 22330505 PMMIaa_sssssettarreerceeh__isnesaerrcth Throughput ( 123000 Throughput ( 1200 Throughput ( 11 505 0 0 0 0 1 2 4 8 16 32 0 1 2 4 8 16 32 0 1 2 4 8 16 32 # of Threads # of Threads # of Threads (a) dataset size = 2M (b) dataset size = 16M (c) dataset size = 128M Figure 8: Query throughput vs thread number 40 processing with respect to query skewness and update ra- PI(2M) MassTree(2M) 35 PI(16M) MassTree(16M) tio in query workloads. By comparing this ﬁgure with Fig- es/sec) 30 PI(128M) MassTree(128M) uimrepa9c,twoenctahneopbesrefrovremtahnacte qoufePryI isnketwernmesssohf aqsueornylypraolcietstsle- eri 25 ing. We attribute this resistance to query skewness of PI u q M 20 to the self-adjusted threading mechanism presented in Sec- ut ( tion 20, which dynamically allocates computing resources p 15 h ug among NUMA nodes based on the query load on each node. Thro 10 In fact, for the query workload with zipﬁan probability pa- 5 rameter θ = 0.5, the numbers of threads spawned at four 0 NUMA nodes are 3, 2, 2 and 1, respectively, and for the 0 20 40 60 80 100 other query workload with θ = 0.9, these numbers become Write Ratio(%) 4, 2, 1 and 1, respectively. For comparison purposes, the corresponding result measured with the threading mecha- Figure 9: Query throughput of mixed workloads nism disabled is shown in Figure 11, from which one can see that the threading mechanism does signiﬁcantly enhance the throughput. ones. It should also be noted that the skewness in query work- 6.4 Mixed Query Workload load does not always exert a negative impact on the through- put. When fed with a workload consisting of pure search In order to thoroughly proﬁle the performance of PI, we queries against keys following a zipﬁan distribution with study how it behaves in the presence of query workload con- θ = 0.5, PI is able to achieve a throughput that is even sisting of various types of queries. As before, we conduct higher than what is achieved in the case of no query skew- this experiment over three default datasets (2M, 16M and ness, as shown in Figure 9 and 10(a). This is probably be- 128M). The query workload consists of keys following a uni- cause in the NUMA node with the most amount of query form distribution, and the entire index layer is rebuilt once load, each of the three spawned thread accesses only an even a speciﬁed number (15% of dataset size) of data nodes have restricted portion of the index, and hence can utilize the been inserted into the index. cache more eﬃciently. Figure 9 shows the result when the ratio of insert queries increases from 0% to 100%. For each ratio, the number of 6.6 Details on YCSB Workload queries issued to the index is such that the index layer is rebuilt for the same number as for other ratios. As shown Figure 12 shows the variance of skewness in the key distri- in Figure 9, with the increase of updates in the query work- bution of the three YCSB workloads for the experiment of load, the throughput of PI undergoes a slight decrease as a Section 20. In this ﬁgure, each circle consists of 100 sectors result of more data nodes in storage layer being traversed, separating the whole key space into 100 disjoint ranges with demonstrating PI’s capability in processing uniform query equal coverage, and the color of a sector represents how fre- workload. Masstree also experiences a similar variance trend quently the keys within the relative range are queried. Since in the query throughput. the keys in each YCSB workload follow a zipﬁan distribu- tion, the workload becomes more skewed with the increase 6.5 Resistance to Skewness of probability parameter θ. However, as shown in Figure 10, the skewness in the query workload rarely aﬀects the perfor- In this section, PI’s performance of query processing is mance of PI (as well as Masstree) , which is also validated in explored in the presence of query skewness. As before, there Figure 13, where the zipﬁan parameter in three YCSB query are eight threads running over the four NUMA nodes, and workloads, each with a diﬀerent update ratio (0.5, 0.05 and three datasets with default sizes (2M, 16M and 128M) are 0, respectively), are varied from 0 to 0.9 to investigate how used. The skewness in query workload is realized via vary- PI can adapt to query skewness. ing the probability parameter, θ, of zipﬁan distribution for workload generation. An intuitive impression on the skew- 6.7 Range Queries ness of the query workloads used in this section is given in Appendix 20 . Figure 14 describes how the performance of range queries Figure 10 exhibits the variation in the throughput query varies with granularity, by which we mean the average num- ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

font: default

text: M

text: queries/sec)

text: M

text: queries/sec)

text: M

text: queries/sec)

text: Throughput

text: Throughput

text: Throughput

text: of

text: Threads

text: of

text: Threads

text: of

text: Threads

text: (a)

text: dataset

text: size

text: (b)

text: dataset

text: size

text: (c)

text: dataset

text: size

text: Figure

text: Query

text: throughput

text: vs

text: thread

text: number

text: processing

text: with

text: respect

text: to

text: query

text: skewness

text: and

text: update

text: ra-

text: tio

text: in

text: query

text: workloads.

text: By

text: comparing

text: this

text: ﬁgure

text: with

text: Fig-

text: es/sec)

text: qoufePryI

text: isnketwernmesssohf

text: aqsueornylypraolcietstsle-

text: eri

text: ing.

text: We

text: attribute

text: this

text: resistance

text: to

text: query

text: skewness

text: of

text: PI

text: u

text: q

text: M

text: to

text: the

text: self-adjusted

text: threading

text: mechanism

text: presented

text: in

text: Sec-

text: ut

text: tion

text: which

text: dynamically

text: allocates

text: computing

text: resources

text: p

text: h

text: ug

text: among

text: NUMA

text: nodes

text: based

text: on

text: the

text: query

text: load

text: on

text: each

text: node.

text: Thro

text: In

text: fact,

text: for

text: the

text: query

text: workload

text: with

text: zipﬁan

text: probability

text: pa-

text: rameter

text: θ

text: the

text: numbers

text: of

text: threads

text: spawned

text: at

text: four

text: NUMA

text: nodes

text: are

text: and

text: respectively,

text: and

text: for

text: the

text: other

text: query

text: workload

text: with

text: θ

text: these

text: numbers

text: become

text: Write

text: Ratio(%)

text: and

text: respectively.

text: For

text: comparison

text: purposes,

text: the

text: corresponding

text: result

text: measured

text: with

text: the

text: threading

text: mecha-

text: Figure

text: Query

text: throughput

text: of

text: mixed

text: workloads

text: nism

text: disabled

text: is

text: shown

text: in

text: Figure

text: from

text: which

text: one

text: can

text: see

text: that

text: the

text: threading

text: mechanism

text: does

text: signiﬁcantly

text: enhance

text: the

text: throughput.

text: ones.

text: It

text: should

text: also

text: be

text: noted

text: that

text: the

text: skewness

text: in

text: query

text: work-

text: Mixed

text: Query

text: Workload

text: load

text: does

text: not

text: always

text: exert

text: a

text: negative

text: impact

text: on

text: the

text: through-

text: put.

text: When

text: fed

text: with

text: a

text: workload

text: consisting

text: of

text: pure

text: search

text: In

text: order

text: to

text: thoroughly

text: proﬁle

text: the

text: performance

text: of

text: PI,

text: we

text: queries

text: against

text: keys

text: following

text: a

text: zipﬁan

text: distribution

text: with

text: study

text: how

text: it

text: behaves

text: in

text: the

text: presence

text: of

text: query

text: workload

text: con-

text: θ

text: PI

text: is

text: able

text: to

text: achieve

text: a

text: throughput

text: that

text: is

text: even

text: sisting

text: of

text: various

text: types

text: of

text: queries.

text: As

text: before,

text: we

text: conduct

text: higher

text: than

text: what

text: is

text: achieved

text: in

text: the

text: case

text: of

text: no

text: query

text: skew-

text: this

text: experiment

text: over

text: three

text: default

text: datasets

text: and

text: ness,

text: as

text: shown

text: in

text: Figure

text: and

text: This

text: is

text: probably

text: be-

text: The

text: query

text: workload

text: consists

text: of

text: keys

text: following

text: a

text: uni-

text: cause

text: in

text: the

text: NUMA

text: node

text: with

text: the

text: most

text: amount

text: of

text: query

text: form

text: distribution,

text: and

text: the

text: entire

text: index

text: layer

text: is

text: rebuilt

text: once

text: load,

text: each

text: of

text: the

text: three

text: spawned

text: thread

text: accesses

text: only

text: an

text: even

text: a

text: speciﬁed

text: number

text: of

text: dataset

text: size)

text: of

text: data

text: nodes

text: have

text: restricted

text: portion

text: of

text: the

text: index,

text: and

text: hence

text: can

text: utilize

text: the

text: been

text: inserted

text: into

text: the

text: index.

text: cache

text: more

text: eﬃciently.

text: Figure

text: shows

text: the

text: result

text: when

text: the

text: ratio

text: of

text: insert

text: queries

text: increases

text: from

text: to

text: For

text: each

text: ratio,

text: the

text: number

text: of

text: Details

text: on

text: YCSB

text: Workload

text: queries

text: issued

text: to

text: the

text: index

text: is

text: such

text: that

text: the

text: index

text: layer

text: is

text: rebuilt

text: for

text: the

text: same

text: number

text: as

text: for

text: other

text: ratios.

text: As

text: shown

text: Figure

text: shows

text: the

text: variance

text: of

text: skewness

text: in

text: the

text: key

text: distri-

text: in

text: Figure

text: with

text: the

text: increase

text: of

text: updates

text: in

text: the

text: query

text: work-

text: bution

text: of

text: the

text: three

text: YCSB

text: workloads

text: for

text: the

text: experiment

text: of

text: load,

text: the

text: throughput

text: of

text: PI

text: undergoes

text: a

text: slight

text: decrease

text: as

text: a

text: Section

text: In

text: this

text: ﬁgure,

text: each

text: circle

text: consists

text: of

text: sectors

text: result

text: of

text: more

text: data

text: nodes

text: in

text: storage

text: layer

text: being

text: traversed,

text: separating

text: the

text: whole

text: key

text: space

text: into

text: disjoint

text: ranges

text: with

text: demonstrating

text: PI’s

text: capability

text: in

text: processing

text: uniform

text: query

text: equal

text: coverage,

text: and

text: the

text: color

text: of

text: a

text: sector

text: represents

text: how

text: fre-

text: workload.

text: Masstree

text: also

text: experiences

text: a

text: similar

text: variance

text: trend

text: quently

text: the

text: keys

text: within

text: the

text: relative

text: range

text: are

text: queried.

text: Since

text: in

text: the

text: query

text: throughput.

text: the

text: keys

text: in

text: each

text: YCSB

text: workload

text: follow

text: a

text: zipﬁan

text: distribu-

text: tion,

text: the

text: workload

text: becomes

text: more

text: skewed

text: with

text: the

text: increase

text: Resistance

text: to

text: Skewness

text: of

text: probability

text: parameter

text: θ.

text: However,

text: as

text: shown

text: in

text: Figure

text: the

text: skewness

text: in

text: the

text: query

text: workload

text: rarely

text: aﬀects

text: the

text: perfor-

text: In

text: this

text: section,

text: PI’s

text: performance

text: of

text: query

text: processing

text: is

text: mance

text: of

text: PI

text: (as

text: well

text: as

text: Masstree)

text: which

text: is

text: also

text: validated

text: in

text: explored

text: in

text: the

text: presence

text: of

text: query

text: skewness.

text: As

text: before,

text: there

text: Figure

text: where

text: the

text: zipﬁan

text: parameter

text: in

text: three

text: YCSB

text: query

text: are

text: eight

text: threads

text: running

text: over

text: the

text: four

text: NUMA

text: nodes,

text: and

text: workloads,

text: each

text: with

text: a

text: diﬀerent

text: update

text: ratio

text: and

text: three

text: datasets

text: with

text: default

text: sizes

text: and

text: are

text: respectively),

text: are

text: varied

text: from

text: to

text: to

text: investigate

text: how

text: used.

text: The

text: skewness

text: in

text: query

text: workload

text: is

text: realized

text: via

text: vary-

text: PI

text: can

text: adapt

text: to

text: query

text: skewness.

text: ing

text: the

text: probability

text: parameter,

text: θ,

text: of

text: zipﬁan

text: distribution

text: for

text: workload

text: generation.

text: An

text: intuitive

text: impression

text: on

text: the

text: skew-

text: Range

text: Queries

text: ness

text: of

text: the

text: query

text: workloads

text: used

text: in

text: this

text: section

text: is

text: given

text: in

text: Appendix

text: Figure

text: describes

text: how

text: the

text: performance

text: of

text: range

text: queries

text: Figure

text: exhibits

text: the

text: variation

text: in

text: the

text: throughput

text: query

text: varies

text: with

text: granularity,

text: by

text: which

text: we

text: mean

text: the

text: average

text: num-

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

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: ##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: ##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: ##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: ##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: ##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: ##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: ##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: 100 8 2M origin Throughput (M queries/sec) 1 01 1162M8M Speedup Factor 234567 ++++sngpiurrmoemufdeaptch 1 0.1 1 10 100 1000 0 Granularity search insert Figure 14: Query throughput of range query Figure 15: Eﬀects of optimizations 7. CONCLUSION AND FUTURE WORK ber of results (data nodes) returned for a given range query. In this experiment, only the performance of search queries In this paper, we argue that skip list, due to its high par- is explored, and the same number of query batches, each allezability, is a better candidate for in-memory index than with 8192 range queries, are issued for each dataset. For B+-tree in concurrent environment. Based on this argu- comparison, the result for point query (granularity = 1) is ment, we propose PI, a cache-friendly, latch-free index that also shown in this ﬁgure. supports both point query and range query. PI consists of It can be observed from Figure 14 that query throughput an index layer, which is in charge of key search, and a stor- decreases with the granularity of range query at a constant age layer responsible for data retrieval, and the layout of the rate for each dataset. Due to the better cache utilization of index layer is carefully designed such that SIMD processing the index built from smaller datasets, the query throughput can be applied to accelerate key search. The experimental decreases a little more slowly for smaller datasets than for results show that PI is three times faster than Masstree in larger datasets. For the granularity of 1000, the processing terms of query throughput. of each query batch accesses almost 8M of data nodes, which For future work, we seek to implement a ﬁner-grained means there are many data nodes being accessed multiple mechanism for the rebuilding of the index layer, which is times for the small and medium datasets with 2M and 16M currently conducted against the whole index layer and thus keys, respectively. Hence, the number of slow memory ac- not necessary in the presence of skewed queries which only cesses incurred by reading entries and data nodes is further update a small portion of the index layer. In addition, we reduced by a larger amount for these two datasets than for are also exploring applying several other optimizations to the large dataset, and this is the reason to that the search PI. For instance, cache locality can be further enhanced by throughput for the large dataset drops much faster than that pinning the high levels of the index layer in the cache to for the other two datasets when the granularity varies from prevent them from being evicted in the case of insuﬃcient 100 to 1000. cache space, and a large memory page size can reduce the number of TLB misses incurred by memory accesses. 6.8 Effects of Optimizations 8. REFERENCES We now explore how the optimization techniques such as SIMD processing, NUMA-aware index partitioning, prefetch- [1] https://github.com/kohler/masstree-beta. ing and group query processing, aﬀect the performance of PI. [2] I. Abraham, J. Aspnes, and J. Yuan. Skip B-trees. In The impact of organizing queries into batches has already OPODIS, pages 366–380. 2006. been studied in Section 20, and hence is not discussed here. [3] M.-C. Albutiu, A. Kemper, and T. Neumann. The dataset used for this experiment contains 16M keys, and Massively parallel sort-merge joins in main memory the other parameters are set to the default sizes. multi-core database systems. PVLDB, Figure 15 shows the breakdown of the gap between the 5(10):1064–1075, 2012. query performance of PI and a typical skip list with none of [4] J. Aspnes and G. Shah. Skip Graphs. TALG, 3(4):37, the optimizations enabled. By grouping the keys appearing 2007. at higher layers into entries, and leveraging SIMD to sig- [5] C. Balkesen, G. Alonso, J. Teubner, and M. T. O¨zsu. niﬁcantly reduce the number of key comparisons and hence Multi-Core, Main-Memory Joins: Sort vs. Hash memory/cache accesses, the throughput of PI can be im- Revisited. PVLDB, 7(1):85–96, 2013. proved by 1.3x and 1x for search and insert queries, re- spectively. NUMA-aware operation leads to another huge [6] C. Balkesen, J. Teubner, G. Alonso, and M. T. O¨zsu. performance gain, improving the query throughput by 1.2x Main-Memory Hash Joins on Multi-Core CPUs: for both kinds of queries. This performance gain is because Tuning to the Underlying Hardware. In ICDE, pages our NUMA-aware optimization largely eliminates accessing 362–373, 2013. the memory of remote NUMA nodes, which is several times [7] S. Blagodurov, S. Zhuravlev, A. Fedorova, and slower than accessing local memory. Group query processing A. Kamali. A case for NUMA-aware contention brings in a slight improvement of 0.05x in query throughput, management on multicore systems. In PACT, 2010. and prefetching contributes to the ﬁnal performance gain [8] A. Braginsky and E. Petrank. A lock-free b+ tree. In of 0.2x and 0.14x in the throughput of search and insert SPAA, pages 58–67, 2012. queries, respectively. [9] T. Brown, F. Ellen, and E. Ruppert. Pragmatic ##LTFigure## ##LTFigure## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: origin

text: Throughput

text: (M

text: queries/sec)

text: Speedup

text: Factor

text: ++++sngpiurrmoemufdeaptch

text: Granularity

text: search

text: insert

text: Figure

text: Query

label: caption

text: throughput

text: of

text: range

text: query

text: Figure

text: Eﬀects

text: of

text: optimizations

label: section

text: CONCLUSION

text: AND

text: FUTURE

text: WORK

text: ber

text: of

text: results

text: (data

text: nodes)

text: returned

text: for

text: a

text: given

text: range

text: query.

text: In

text: this

text: experiment,

text: only

text: the

text: performance

text: of

text: search

text: queries

text: In

text: this

text: paper,

text: we

text: argue

text: that

text: skip

text: list,

text: due

text: to

text: its

text: high

text: par-

text: is

text: explored,

text: and

text: the

text: same

text: number

text: of

text: query

text: batches,

text: each

text: allezability,

text: is

text: a

text: better

text: candidate

text: for

text: in-memory

text: index

text: than

text: with

text: range

text: queries,

text: are

text: issued

text: for

text: each

text: dataset.

text: For

text: B+-tree

text: in

text: concurrent

text: environment.

text: Based

text: on

text: this

text: argu-

text: comparison,

text: the

text: result

text: for

text: point

text: query

text: (granularity

text: is

text: ment,

text: we

text: propose

text: PI,

text: a

text: cache-friendly,

text: latch-free

text: index

text: that

text: also

text: shown

text: in

text: this

text: ﬁgure.

text: supports

text: both

text: point

text: query

text: and

text: range

text: query.

text: PI

text: consists

text: of

text: It

text: can

text: be

text: observed

text: from

text: Figure

text: that

text: query

text: throughput

text: an

text: index

text: layer,

text: which

text: is

text: in

text: charge

text: of

text: key

text: search,

text: and

text: a

text: stor-

text: decreases

text: with

text: the

text: granularity

text: of

text: range

text: query

text: at

text: a

text: constant

text: age

text: layer

text: responsible

text: for

text: data

text: retrieval,

text: and

text: the

text: layout

text: of

text: the

text: rate

text: for

text: each

text: dataset.

text: Due

text: to

text: the

text: better

text: cache

text: utilization

text: of

text: index

text: layer

text: is

text: carefully

text: designed

text: such

text: that

text: SIMD

text: processing

text: the

text: index

text: built

text: from

text: smaller

text: datasets,

text: the

text: query

text: throughput

text: can

text: be

text: applied

text: to

text: accelerate

text: key

text: search.

text: The

text: experimental

text: decreases

text: a

text: little

text: more

text: slowly

text: for

text: smaller

text: datasets

text: than

text: for

text: results

text: show

text: that

text: PI

text: is

text: three

text: times

text: faster

text: than

text: Masstree

text: in

text: larger

text: datasets.

text: For

text: the

text: granularity

text: of

text: the

text: processing

text: terms

text: of

text: query

text: throughput.

text: of

text: each

text: query

text: batch

text: accesses

text: almost

text: of

text: data

text: nodes,

text: which

text: For

text: future

text: work,

text: we

text: seek

text: to

text: implement

text: a

text: ﬁner-grained

text: means

text: there

text: are

text: many

text: data

text: nodes

text: being

text: accessed

text: multiple

text: mechanism

text: for

text: the

text: rebuilding

text: of

text: the

text: index

text: layer,

text: which

text: is

text: times

text: for

text: the

text: small

text: and

text: medium

text: datasets

text: with

text: and

text: currently

text: conducted

text: against

text: the

text: whole

text: index

text: layer

text: and

text: thus

text: keys,

text: respectively.

text: Hence,

text: the

text: number

text: of

text: slow

text: memory

text: ac-

text: not

text: necessary

text: in

text: the

text: presence

text: of

text: skewed

text: queries

text: which

text: only

text: cesses

text: incurred

text: by

text: reading

text: entries

text: and

text: data

text: nodes

text: is

text: further

text: update

text: a

text: small

text: portion

text: of

text: the

text: index

text: layer.

text: In

text: addition,

text: we

text: reduced

text: by

text: a

text: larger

text: amount

text: for

text: these

text: two

text: datasets

text: than

text: for

text: are

text: also

text: exploring

text: applying

text: several

text: other

text: optimizations

text: to

text: the

text: large

text: dataset,

text: and

text: this

text: is

text: the

text: reason

text: to

text: that

text: the

text: search

text: PI.

text: For

text: instance,

text: cache

text: locality

text: can

text: be

text: further

text: enhanced

text: by

text: throughput

text: for

text: the

text: large

text: dataset

text: drops

text: much

text: faster

text: than

text: that

text: pinning

text: the

text: high

text: levels

text: of

text: the

text: index

text: layer

text: in

text: the

text: cache

text: to

text: for

text: the

text: other

text: two

text: datasets

text: when

text: the

text: granularity

text: varies

text: from

text: prevent

text: them

text: from

text: being

text: evicted

text: in

text: the

text: case

text: of

text: insuﬃcient

text: to

text: cache

text: space,

text: and

text: a

text: large

text: memory

text: page

text: size

text: can

text: reduce

text: the

text: number

text: of

text: TLB

text: misses

text: incurred

text: by

text: memory

text: accesses.

text: Effects

text: of

text: Optimizations

text: REFERENCES

text: We

text: now

text: explore

text: how

text: the

text: optimization

text: techniques

text: such

text: as

text: SIMD

text: processing,

text: NUMA-aware

text: index

text: partitioning,

text: prefetch-

text: ing

text: and

text: group

text: query

text: processing,

text: aﬀect

text: the

text: performance

text: of

text: PI.

text: I.

text: Abraham,

text: J.

text: Aspnes,

text: and

text: J.

text: Yuan.

text: Skip

text: B-trees.

text: In

text: The

text: impact

text: of

text: organizing

text: queries

text: into

text: batches

text: has

text: already

text: OPODIS,

text: pages

text: been

text: studied

text: in

text: Section

text: and

text: hence

text: is

text: not

text: discussed

text: here.

text: M.-C.

text: Albutiu,

text: A.

text: Kemper,

text: and

text: T.

text: Neumann.

text: The

text: dataset

text: used

text: for

text: this

text: experiment

text: contains

text: keys,

text: and

text: Massively

text: parallel

text: sort-merge

text: joins

text: in

text: main

text: memory

text: the

text: other

text: parameters

text: are

text: set

text: to

text: the

text: default

text: sizes.

text: multi-core

text: database

text: systems.

text: PVLDB,

text: Figure

text: shows

text: the

text: breakdown

text: of

text: the

text: gap

text: between

text: the

text: query

text: performance

text: of

text: PI

text: and

text: a

text: typical

text: skip

text: list

text: with

text: of

text: J.

text: Aspnes

text: and

text: G.

text: Shah.

text: Skip

text: Graphs.

text: TALG,

text: the

text: optimizations

text: enabled.

text: By

text: grouping

text: the

text: keys

text: appearing

text: at

text: higher

text: layers

text: into

text: entries,

text: and

text: leveraging

text: SIMD

text: to

text: sig-

text: C.

text: Balkesen,

text: G.

text: Alonso,

text: J.

text: Teubner,

text: and

text: M.

text: T.

text: O¨zsu.

text: niﬁcantly

text: reduce

text: the

text: number

text: of

text: key

text: comparisons

text: and

text: hence

text: Multi-Core,

text: Main-Memory

text: Joins:

text: Sort

text: vs.

text: Hash

text: memory/cache

text: accesses,

text: the

text: throughput

text: of

text: PI

text: can

text: be

text: im-

text: Revisited.

text: PVLDB,

text: proved

text: by

text: and

text: for

text: search

text: and

text: insert

text: queries,

text: re-

text: spectively.

text: NUMA-aware

text: operation

text: leads

text: to

text: another

text: huge

text: C.

text: Balkesen,

text: J.

text: Teubner,

text: G.

text: Alonso,

text: and

text: M.

text: T.

text: O¨zsu.

text: performance

text: gain,

text: improving

text: the

text: query

text: throughput

text: by

text: Main-Memory

text: Hash

text: Joins

text: on

text: Multi-Core

text: CPUs:

text: for

text: both

text: kinds

text: of

text: queries.

text: This

text: performance

text: gain

text: is

text: because

text: Tuning

text: to

text: the

text: Underlying

text: Hardware.

text: In

text: ICDE,

text: pages

text: our

text: NUMA-aware

text: optimization

text: largely

text: eliminates

text: accessing

text: the

text: memory

text: of

text: remote

text: NUMA

text: nodes,

text: which

text: is

text: several

text: times

text: S.

text: Blagodurov,

text: S.

text: Zhuravlev,

text: A.

text: Fedorova,

text: and

text: slower

text: than

text: accessing

text: local

text: memory.

text: Group

text: query

text: processing

text: A.

text: Kamali.

text: A

text: case

text: for

text: NUMA-aware

text: contention

text: brings

text: in

text: a

text: slight

text: improvement

text: of

text: in

text: query

text: throughput,

text: management

text: on

text: multicore

text: systems.

text: In

text: PACT,

text: and

text: prefetching

text: contributes

text: to

text: the

text: ﬁnal

text: performance

text: gain

text: A.

text: Braginsky

text: and

text: E.

text: Petrank.

text: A

text: lock-free

text: b+

text: tree.

text: In

text: of

text: and

text: in

text: the

text: throughput

text: of

text: search

text: and

text: insert

text: SPAA,

text: pages

text: queries,

text: respectively.

text: T.

text: Brown,

text: F.

text: Ellen,

text: and

text: E.

text: Ruppert.

text: Pragmatic

text: ##LTFigure##

text: ##LTFigure##

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: ##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: ##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: ##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: ##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: The branching operation gives a recurrence relation ≤ − · − − · − − · − − C(k) (d 1)2 C(k 2) + (d 1) C(k 2) + (d 1) C(k 2) + C(k 2) · − = d2 C(k 2), the branching factor of which is d < d + 1. Step 7 (Proper triples of degree-(d + 1) vertices) { } A set of three degree-(d + 1) vertices v , v , v is called a proper triple if { } 1 2 3{ } v , v , v induces a path and no pair of vertices in v , v , v is close or similar. 1 2 3 1 2 3 Lemma 6. Let G be a graph of maximum degree d + 1 for any integer d > 0. If G has no proper dominations, good pairs, close triples, type-I close quadruples or type-II close quadruples, then G has some proper triples. A proof of this lemma can be found in the full version. { } For a proper triple v , v , v in a graph having none of dominated vertices, 1 2 3 good pairs, close triples, type-I close quadruples and type-II close quadruples, ∩ ∅ ∩ ∅ we have the following properties: N(v ) N(v ) = , N(v ) N(v ) = and ≤ | ∩ | ≤ 1 2 2 3 1 N(v ) N(v ) d. 1− 3 ∩ \ { } − \ − \ Let N = N(v ) N(v ) v , N = N(v ) N(v ), N = N(v ) N(v ), − 13 \ { 1 } 3 2| −|1 {1 } 3 3 3 1 N = N(v ) v , v and x = N . Since v , v is not a similar pair, we 2 2 ≤ ≤1 3− (cid:48) 13 1 3 know that 0 x d 1. Let S be a d-deletion set. To design our branching rule, we consider the following diﬀerent cases. ∈ (cid:48) Case 1. v S : We simply include v to the solution set and the parameter 2 2 (cid:54)∈ (cid:48) k decreases by 1. For all the remaining cases, we assume that v S . (cid:54)∈ (cid:48) ∈ (cid:48) 2 Case 2. v S and v , v S : We simply include v and v to the solution 2 1 3 1 3 set and the parameter k decreases by 2. (cid:54)∈ (cid:48) ∈ (cid:48) (cid:48) ∩ \ { } (cid:54) ∅ Case 3. v , v S and v S : For the case, S (N(v ) v = . We | \1{ 2}| 3 1 2 \{ } create N(v ) v = d branches by including v and each vertex in N(v ) v 1 2 3 1 2 to the solution set and the parameter k in each branch decreases by 2. (cid:54)∈ (cid:48) ∈ (cid:48) (cid:48) ∩ \ { } (cid:54) ∅ Case 4. v , v S and v S : For the case, S (N(v ) v = . We | \2{ 3}| 1 3 2 \{ } create N(v ) v = d branches by including v and each vertex in N(v ) v 3 2 1 3 2 to the solution set and the parameter k in each branch decreases by 2. (cid:54)∈ (cid:48) (cid:48) − Case 5. v , v , v S : Then S must contains (i) a vertex in N and 1 2 3 − − − 2 (ii) either a vertex in N or two vertices from N and N respectively. Our | −1|3| −| | −||| −|| −| 1 − 3 − − algorithm generates N N + N N N = (d 1)x + (d 1)(d x)2 2 13 − 2 1 3 − branches. Each of the ﬁrst (d 1)x branches includes a vertex in N and a − 2 vertex in N to the solution set and the parameter k decreases by 2. The last − − 13 { ∈ − ∈ (d 1)(d x)2 branches are generated by including each triple w N , w − ∈ −} 1 2 2 N , w N to the solution set, where the parameter k decreases by 3. 1 3 3 The above branching operation gives a recurrence relation ≤ − − · − · − C(k) C(k 1) + C(k 2) + d C(k 2) + d C(k 2)+ − · − − − · − (d 1)x C(k 2) + (d 1)(d x)2 C(k 3) (4) − − · − − − · − = C(k 1) + ((2d + 1) + (d 1)x) C(k 2) + (d 1)(d x)2 C(k 3), ≤ ≤ − where 0 x d 1. 11

text: The

text: branching

text: operation

text: gives

text: a

text: recurrence

text: relation

text: C(k)

text: (d

text: C(k

text: (d

text: C(k

text: (d

text: C(k

text: C(k

text: C(k

text: the

text: branching

text: factor

text: of

text: which

text: is

text: d

text: d

text: Step

text: (Proper

text: triples

text: of

text: degree-(d

text: vertices)

text: A

text: set

text: of

text: three

text: degree-(d

text: vertices

text: v

text: v

text: v

text: is

text: called

text: a

text: proper

text: triple

text: if

text: v

text: v

text: v

text: induces

text: a

text: path

text: and

text: no

text: pair

text: of

text: vertices

text: in

text: v

text: v

text: v

text: is

text: close

text: or

text: similar.

text: Lemma

text: Let

text: G

text: be

text: a

text: graph

text: of

text: maximum

text: degree

text: d

text: for

text: any

text: integer

text: d

text: If

text: G

text: has

text: no

text: proper

text: dominations,

text: good

text: pairs,

text: close

text: triples,

text: type-I

text: close

text: quadruples

text: or

text: type-II

text: close

text: quadruples,

text: then

text: G

text: has

text: some

text: proper

text: triples.

text: A

text: proof

text: of

text: this

text: lemma

text: can

text: be

text: found

text: in

text: the

text: full

text: version.

text: For

text: a

text: proper

text: triple

text: v

text: v

text: v

text: in

text: a

text: graph

text: having

text: of

text: dominated

text: vertices,

text: good

text: pairs,

text: close

text: triples,

text: type-I

text: close

text: quadruples

text: and

text: type-II

text: close

text: quadruples,

text: we

text: have

text: the

text: following

text: properties:

text: N(v

text: N(v

text: N(v

text: N(v

text: and

text: N(v

text: N(v

text: d.

text: 1−

text: Let

text: N

text: N(v

text: N(v

text: v

text: N

text: N(v

text: N(v

text: N

text: N(v

text: N(v

text: N

text: N(v

text: v

text: v

text: and

text: x

text: N

text: Since

text: v

text: v

text: is

text: not

text: a

text: similar

text: pair,

text: we

text: ≤1

text: 3−

text: know

text: that

text: x

text: d

text: Let

text: S

text: be

text: a

text: d-deletion

text: set.

text: To

text: design

text: our

text: branching

text: rule,

text: we

text: consider

text: the

text: following

text: diﬀerent

text: cases.

text: Case

text: v

text: S

text: We

text: simply

text: include

text: v

text: to

text: the

text: solution

text: set

text: and

text: the

text: parameter

text: k

text: decreases

text: by

text: For

text: all

text: the

text: remaining

text: cases,

text: we

text: assume

text: that

text: v

text: S

text: Case

text: v

text: S

text: and

text: v

text: v

text: S

text: We

text: simply

text: include

text: v

text: and

text: v

text: to

text: the

text: solution

text: set

text: and

text: the

text: parameter

text: k

text: decreases

text: by

text: Case

text: v

text: v

text: S

text: and

text: v

text: S

text: For

text: the

text: case,

text: S

text: (N(v

text: v

text: We

text: create

text: N(v

text: v

text: d

text: branches

text: by

text: including

text: v

text: and

text: each

text: vertex

text: in

text: N(v

text: v

text: to

text: the

text: solution

text: set

text: and

text: the

text: parameter

text: k

text: in

text: each

text: branch

text: decreases

text: by

text: Case

text: v

text: v

text: S

text: and

text: v

text: S

text: For

text: the

text: case,

text: S

text: (N(v

text: v

text: We

text: create

text: N(v

text: v

text: d

text: branches

text: by

text: including

text: v

text: and

text: each

text: vertex

text: in

text: N(v

text: v

text: to

text: the

text: solution

text: set

text: and

text: the

text: parameter

text: k

text: in

text: each

text: branch

text: decreases

text: by

text: Case

text: v

text: v

text: v

text: S

text: Then

text: S

text: must

text: contains

text: (i)

text: a

text: vertex

text: in

text: N

text: and

text: (ii)

text: either

text: a

text: vertex

text: in

text: N

text: or

text: two

text: vertices

text: from

text: N

text: and

text: N

text: respectively.

text: Our

text: algorithm

text: generates

text: N

text: N

text: N

text: N

text: N

text: (d

text: (d

text: branches.

text: Each

text: of

text: the

text: ﬁrst

text: (d

text: branches

text: includes

text: a

text: vertex

text: in

text: N

text: and

text: a

text: vertex

text: in

text: N

text: to

text: the

text: solution

text: set

text: and

text: the

text: parameter

text: k

text: decreases

text: by

text: The

text: last

text: (d

text: branches

text: are

text: generated

text: by

text: including

text: each

text: triple

text: w

text: N

text: w

text: N

text: w

text: N

text: to

text: the

text: solution

text: set,

text: where

text: the

text: parameter

text: k

text: decreases

text: by

text: The

text: above

text: branching

text: operation

text: gives

text: a

text: recurrence

text: relation

text: C(k)

text: C(k

text: C(k

text: d

text: C(k

text: d

text: C(k

text: (d

text: C(k

text: (d

text: C(k

text: C(k

text: (d

text: C(k

text: (d

text: C(k

text: where

text: x

text: d


text: 3. J. Chen, I.A. Kanj, G. Xia: Improved upper bounds for vertex cover, Theoretical Computer Science 411 (2010) 3736–3756. 4. Z.-Z. Chen, M. Fellows, B. Fu, H. Jiang, Y. Liu, L. Wang, B. Zhu: A linear kernel for co-path/cycle packing, in: Proceedings of the 6th International Conference on Algorithmic Aspects in Information and Management (AAIM 10), LNCS 6124, Springer, (2010) 90–102. 5. M. R. Fellows, J. Guo, H. Moser, and R. Niedermeier: A generalization of Nemhauser and Trotter’s local optimization theorem. Journal of Computer and System Sciences 77(2011) 1141–1158. 6. Q. Feng, J. Wang, S. Li, J. Chen: Randomized parameterized algorithms for P - 2 Packing and Co-Path Packing problems. J. Comb. Optim. 29(1) (2015) 125–140. 7. H. Fernau: A top-down approach to search-trees: Improved algorithmics for 3- Hitting Set, Algorithmica 57 (2010) 97–118. 8. H. Fernau: Parameterized algorithms for d-HITTING SET: The weighted case, Theor. Comput. Sci. 411(16–18) (2010) 1698–1713. 9. H. Fernau: Parameterized algorithmics for d-Hitting Set, International Journal of Computer Mathematics 87(14) (2010) 3157–3174. 10. F. V. Fomin and D. Kratsch: Exact Exponential Algorithms, Springer (2010) 11. J.Katreniˇc: A faster FPT algorithm for 3-path vertex cover. Information Processing Letters. 116(4): 273–278(2016) 12. I. Newnan and C. Sohler: Every proerty of hyperﬁnite graphs is testable, SIAM Journal on Computing 42(3) (2013) 1095–1112. 13. R. Niedermeier and P. Rossmanith: An eﬃcient ﬁxed-parameter algorithm for 3- Hitting Set, J. Discrete Algorithms 1 (2003) 89–102. 14. S. B. Seidman and B. L. Foster: A graph-theoretic generalization of the clique concept. Journal of Mathematical Sociology 6 (1978) 139–154. 15. J. Tu: A ﬁxed-parameter algorithm for the vertex cover P3 problem, Information Processing Letters 115 (2015) 96–99. 16. B. Wu: A Measure and Conquer Approach for the Parameterized Bounded Degree- One Vertex Deletion, In: COCOON 2015, LNCS 9198, (2015) 469–480. 17. M. Xiao: On a generalization of Nemhauser and Trotter’s local optimization theo- rem. In: ISAAC 2015, LNCS 9472, (2015) 442–452. 13

text: J.

text: Chen,

text: I.A.

text: Kanj,

text: G.

text: Xia:

text: Improved

text: upper

text: bounds

text: for

text: vertex

text: cover,

text: Theoretical

text: Computer

text: Science

text: Z.-Z.

text: Chen,

text: M.

text: Fellows,

text: B.

text: Fu,

text: H.

text: Jiang,

text: Y.

text: Liu,

text: L.

text: Wang,

text: B.

text: Zhu:

text: A

text: linear

text: kernel

text: for

text: co-path/cycle

text: packing,

text: in:

text: Proceedings

text: of

text: the

text: International

text: Conference

text: on

text: Algorithmic

text: Aspects

text: in

text: Information

text: and

text: Management

text: (AAIM

text: LNCS

text: Springer,

text: M.

text: R.

text: Fellows,

text: J.

text: Guo,

text: H.

text: Moser,

text: and

text: R.

text: Niedermeier:

text: A

text: generalization

text: of

text: Nemhauser

text: and

text: Trotter’s

text: local

text: optimization

text: theorem.

text: Journal

text: of

text: Computer

text: and

text: System

text: Sciences

text: Q.

text: Feng,

text: J.

text: Wang,

text: S.

text: Li,

text: J.

text: Chen:

text: Randomized

text: parameterized

text: algorithms

text: for

text: P

text: Packing

text: and

text: Co-Path

text: Packing

text: problems.

text: J.

text: Comb.

text: Optim.

text: H.

text: Fernau:

text: A

text: top-down

text: approach

text: to

text: search-trees:

text: Improved

text: algorithmics

text: for

text: Hitting

text: Set,

text: Algorithmica

text: H.

text: Fernau:

text: Parameterized

text: algorithms

text: for

text: d-HITTING

text: SET:

text: The

text: weighted

text: case,

text: Theor.

text: Comput.

text: Sci.

text: H.

text: Fernau:

text: Parameterized

text: algorithmics

text: for

text: d-Hitting

text: Set,

text: International

text: Journal

text: of

text: Computer

text: Mathematics

text: F.

text: V.

text: Fomin

text: and

text: D.

text: Kratsch:

text: Exact

text: Exponential

text: Algorithms,

text: Springer

text: J.Katreniˇc:

text: A

text: faster

text: FPT

text: algorithm

text: for

text: vertex

text: cover.

text: Information

text: Processing

text: Letters.

text: I.

text: Newnan

text: and

text: C.

text: Sohler:

text: Every

text: proerty

text: of

text: hyperﬁnite

text: graphs

text: is

text: testable,

text: SIAM

text: Journal

text: on

text: Computing

text: R.

text: Niedermeier

text: and

text: P.

text: Rossmanith:

text: An

text: eﬃcient

text: ﬁxed-parameter

text: algorithm

text: for

text: Hitting

text: Set,

text: J.

text: Discrete

text: Algorithms

text: S.

text: B.

text: Seidman

text: and

text: B.

text: L.

text: Foster:

text: A

text: graph-theoretic

text: generalization

text: of

text: the

text: clique

text: concept.

text: Journal

text: of

text: Mathematical

text: Sociology

text: J.

text: Tu:

text: A

text: ﬁxed-parameter

text: algorithm

text: for

text: the

text: vertex

text: cover

text: problem,

text: Information

text: Processing

text: Letters

text: B.

text: Wu:

text: A

text: Measure

text: and

text: Conquer

text: Approach

text: for

text: the

text: Parameterized

text: Bounded

text: Degree-

text: One

text: Vertex

text: Deletion,

text: In:

text: COCOON

text: LNCS

text: M.

text: Xiao:

text: On

text: a

text: generalization

text: of

text: Nemhauser

text: and

text: Trotter’s

text: local

text: optimization

text: theo-

text: rem.

text: In:

text: ISAAC

text: LNCS