text: Set-Similarity Joins Using MapReduce. In SIGMOD, pp. 495–506, New York, New York, USA, 2010. ACM. [25] D. Wang, D. Irani, and C. Pu. Evolutionary study of web spam: Webb spam corpus 2011 versus webb spam corpus 2006. In CollaborateCom, pp. 40–49, 2012. [26] S. Wang and E. Rundensteiner. Scalable Stream Join Processing with Expensive Predicates: Workload Distribution and Adaptation by Time-Slicing. In EDBT, pp. 299–310. ACM, 2009. [27] C. Xiao, W. Wang, X. Lin, and J. X. Yu. Eﬃcient Similarity Joins for Near Duplicate Detection. In WWW, pp. 131–140. ACM, 2008. [28] C. Xiao, W. Wang, X. Lin, J. X. Yu, and G. Wang. Eﬃcient similarity joins for near-duplicate detection. TODS, 36(3):15, 2011. [29] J. Yang and J. Leskovec. Patterns of temporal variation in online media. In WSDM, pp. 177–186, 2011. APPENDIX A. CORRECTNESS It is clear that our algorithms do not produce any false positive, as there is always a ﬁnal check of the actual simi- larity threshold before the ﬁnal output of any pair. For false negatives, proof of correctness follows from the deﬁnition of time-based similarity and the Cauchy-Schwarz inequality. Theorem 1. CG phase is safe, i.e., pruning does not miss any similar pair. Proof. − | − | ≤ || || || || − ≤ − sim (x, y) = dot(x, y) e λ t(x) t(y) x y e λ∆txy e λ∆txy ∆t The ﬁrst inequality supports the pruning rules at Algo- rithm 7 Lines 10-12, and Algorithm 8 Lines 3 and 6 (green code). The second inequality supports the pruning rule at Algorithm 7 Line 7 (green code). ∈ In particular, for any index j [1, d], we have ≤ || (cid:48) || || (cid:48) || || (cid:48)(cid:48)|| || (cid:48)(cid:48)|| − sim (x, y) ( x y + x y ) e λ∆txy. ∆t j j j j In the algorithm, the coordinate j corresponds to any of the indexed dimensions. The proof of correctness relies on the Cauchy-Schwarz in- equality, and the fact that the time-based similarity adds a forgetting factor. Therefore, the factor can be carried to- gether with the proof. The forgetting factor actually makes − ≤ the bound tighter for the streaming setting, as e λ∆txy 1. 13 ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Set-Similarity

text: Joins

text: Using

text: MapReduce.

text: In

text: SIGMOD,

text: pp.

text: New

text: York,

text: New

text: York,

text: USA,

text: ACM.

text: D.

text: Wang,

text: D.

text: Irani,

text: and

text: C.

text: Pu.

text: Evolutionary

text: study

text: of

text: web

text: spam:

text: Webb

text: spam

text: corpus

text: versus

text: webb

text: spam

text: corpus

text: In

text: CollaborateCom,

text: pp.

text: S.

text: Wang

text: and

text: E.

text: Rundensteiner.

text: Scalable

text: Stream

text: Join

text: Processing

text: with

text: Expensive

text: Predicates:

text: Workload

text: Distribution

text: and

text: Adaptation

text: by

text: Time-Slicing.

text: In

text: EDBT,

text: pp.

text: ACM,

text: C.

text: Xiao,

text: W.

text: Wang,

text: X.

text: Lin,

text: and

text: J.

text: X.

text: Yu.

text: Eﬃcient

text: Similarity

text: Joins

text: for

text: Near

text: Duplicate

text: Detection.

text: In

text: WWW,

text: pp.

text: ACM,

text: C.

text: Xiao,

text: W.

text: Wang,

text: X.

text: Lin,

text: J.

text: X.

text: Yu,

text: and

text: G.

text: Wang.

text: Eﬃcient

text: similarity

text: joins

text: for

text: near-duplicate

text: detection.

text: TODS,

text: J.

text: Yang

text: and

text: J.

text: Leskovec.

text: Patterns

text: of

text: temporal

text: variation

text: in

text: online

text: media.

text: In

text: WSDM,

text: pp.

text: APPENDIX

text: A.

text: CORRECTNESS

text: It

text: is

text: clear

text: that

text: our

text: algorithms

text: do

text: not

text: produce

text: any

text: false

text: positive,

text: as

text: there

text: is

text: always

text: a

text: ﬁnal

text: check

text: of

text: the

text: actual

text: simi-

text: larity

text: threshold

text: before

text: the

text: ﬁnal

text: output

text: of

text: any

text: pair.

text: For

text: false

text: negatives,

text: proof

text: of

text: correctness

text: follows

text: from

text: the

text: deﬁnition

text: of

text: time-based

text: similarity

text: and

text: the

text: Cauchy-Schwarz

text: inequality.

text: Theorem

text: CG

text: phase

text: is

text: safe,

text: i.e.,

text: pruning

text: does

text: not

text: miss

text: any

text: similar

text: pair.

text: Proof.

text: sim

text: (x,

text: y)

text: dot(x,

text: y)

text: e

text: λ

text: t(x)

text: t(y)

text: x

text: y

text: e

text: λ∆txy

text: e

text: λ∆txy

text: ∆t

text: The

text: ﬁrst

text: inequality

text: supports

text: the

text: pruning

text: rules

text: at

text: Algo-

text: rithm

text: Lines

text: and

text: Algorithm

text: Lines

text: and

text: (green

text: code).

text: The

text: second

text: inequality

text: supports

text: the

text: pruning

text: rule

text: at

text: Algorithm

text: Line

text: (green

text: code).

text: In

text: particular,

text: for

text: any

text: index

text: j

text: d],

text: we

text: have

text: sim

text: (x,

text: y)

text: x

text: y

text: x

text: y

text: e

text: λ∆txy.

text: ∆t

text: j

text: j

text: j

text: j

text: In

text: the

text: algorithm,

text: the

text: coordinate

text: j

text: corresponds

text: to

text: any

text: of

text: the

text: indexed

text: dimensions.

text: The

text: proof

text: of

text: correctness

text: relies

text: on

text: the

text: Cauchy-Schwarz

text: in-

text: equality,

text: and

text: the

text: fact

text: that

text: the

text: time-based

text: similarity

text: adds

text: a

text: forgetting

text: factor.

text: Therefore,

text: the

text: factor

text: can

text: be

text: carried

text: to-

text: gether

text: with

text: the

text: proof.

text: The

text: forgetting

text: factor

text: actually

text: makes

text: the

text: bound

text: tighter

text: for

text: the

text: streaming

text: setting,

text: as

text: e

text: λ∆txy

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: diﬀerent indexing techniques need to be applied; e.g., nodes arrived more than can never be pruned. 1 1 τ = log λ θ 3. PROBLEM STATEMENT time units earlier. Consequently, we can safely prune vectors We consider data items represented as vectors in a d- that are older than τ. We call τ the time horizon. R dimensional Euclidean space d. In real-world applications, Parameter setting. The sssj problem, deﬁned in Prob- the dimensionality d is typically high, while the data items (cid:104) (cid:105) lem 1, requires two parameters: a similarity threshold θ and are sparse vectors. Given two vectors x = x . . . x and (cid:104) (cid:105) 1 d a time-decay factor λ. The time-ﬁltering property suggests (cid:88) y = y . . . y , their similarity sim(x, y) is the dot-product 1 d a simple methodology to set these two parameters: · d 1. Select θ as the lowest value of the similarity between two sim(x, y) = dot(x, y) = x y = xj yj. simultaneously-arriving vectors that are deemed similar. j=1 2. Select τ as the smallest diﬀerence in arrival times be- We assume that all vectors x are normalized to unit length, tween two identical vectors that are deemed dissimilar. || || i.e., x 2 = 1, which implies that the dot-product of two 3. Set λ = τ−1 log θ−1. vectors is equal to their cosine similarity; cos(x, y) = dot(x, y). In the standard all-pairs similarity search problem (apss), Setting θ and τ in steps 1 and 2 depends on the application. also known as similarity self-join, we are given a set of vec- Additional notation. When referring to the non-streaming D { } tors and a similarity threshold θ, and the ≥goal is to ﬁnd all setting, we conRsider a dataset = x1, . . . , xn consisting pairs of vectors (x, y) for which sim(x, y) θ. of n vectors in d. In this paper we assume that the input items arrive as a Following Anastasiu and Karypis, we use the notation (cid:48) (cid:48) (cid:104) (cid:80) (cid:105) data stream. Each vector x in the input stream is times- x = xp = x1, .., xp−1, 0, .., 0 and to denote the preﬁx of tamped withS the(cid:104) time of its arrival t(x), and the(cid:105)stream is a vector x. For a vector x, we denote by vmx its maximum denoted by = . . . , (xi, t(xi)), (xi+1, t(xi+1), . . . . coo|rd|inate, by Σx = j xj the sum of its coordinates, and We deﬁne the similarity of two vectors x and y by con- by x the number of its non-zero coordinates. D sidering not only their coordinates (xj, yj), but also the dif- Given a static dataset we use mj to refer to the maxDi- f|erenc−e in t|heir arrival times in the input stream ∆txy = mum value along the j-th coordinate over all vectors in . t(x) t(y) . For ﬁxed coordinates, the larger the arrival All values of m together compos(cid:98)e the vector m. Our meth- j time diﬀerence of two vectors, the smaller their similarity. ods use indexing schemes which build an index incremen- In particular, given two timestamped vectors x and y we tally, v(cid:98)ector-by-vector. We use m to refer to the vector (cid:98)m, deﬁne their time-dependent similarity sim∆t(x, y) as restric(cid:98)ted to the dataset that is already indexed, and we sim∆t(x, y) = dot(x, y) e−λ|t(x)−t(y)|, w(arnitde mmλj ffoo(cid:98)rr iittss jj--tthh ccoooorrddiinnaattee). tFoudrtehneortmeoaret,imwee-duesceaymedλ j variant of m, whose precise deﬁnition is given in Section 10. where λ is a time-decay parameter. This time-dependent similarity reverts to the standard 4. OVERVIEW OF THE APPROACH dot-product (or cosine) similarity when ∆t = 0 or λ = 0, xy and it goes to zero as ∆t approaches inﬁnity, at an ex- xy In this section we present a high-level overview of our main ponential rate modulated by λ. As in the standard apss algorithms for the sssj problem. problem, given a similarity threshold θ, two vectors x and y We present two diﬀerent algorithmic frameworks: MB-IDX are called similar if their time-dependent similarity is above ≥ (MiniBatch-IDX) and STR-IDX (Streaming-IDX), where IDX the threshold, i.e., sim∆t(x, y) θ. is an indexing method for the apss problem on static data. We can now deﬁne the streaming version of the apss prob- To make the presentation of our algorithms more clear, we lem, called the streaming similarity self-join problem (sssj). ﬁrst give an overview of the indexing methods for the static apss problem, as introduced in earlier papers [3, 7, 10]. Problem 1 (sssj). Given a stream of timestamped vec- S All indexing schemes are based on building an inverted tors , a similarity threshold θ, and a time-decay factor λ, I index. The index is a collection of d posting lists, = output all pairs of vectors (x, y) in the stream such that { } ≥ I , . . . , I , where the list I contains all pairs (ι(x), x ) sim (x, y) θ. 1 d j j ∆t such that the j-th coordinate of vector x is non-zero, i.e., (cid:54) x = 0. Here ι(x) denotes a reference to vector x. j Time ﬁltering. The main challenge of computing a self- Some methods optimize computation by not indexing the join in a data stream is that, in principle, unbounded mem- whole dataset. In these cases, the un-indexed part is still ory is required, as an item can be similar with any other item needed in order to compute exact similarities. Thus, we I that will arrive arbitrarily far in the future. By adopting assume that a separate part of the index contains the un- R the time-dependent similarity measure sim∆t, we introduce indexed part of the dataset, called residual direct index . a forgetting mechanism, which not only is intuitive from an All schemes build the index incrementally, while also com- application point-of-view, but also allows to overcome the puting similar pairs. In particular, we start with an empty D unbounded-memory requirement. In particular, since for ≤ index, and we iteratively process the vectors in . For each (cid:96) -normalized vectors dot(x, y) 1, we have 2 newly-processed vector x, we compute similar pairs (x, y) sim (x, y) = dot(x, y) e−λ∆txy ≤ e−λ∆txy. for all vectors y that are already in the index. Thereafter, ∆t we add (some of) the non-zero coordinates of x to the index. − − Thus, ∆t > λ 1 log θ 1 implies sim (x, y) < θ, and as Building the index and computing similar pairs can be xy ∆t a result a given vector cannot be similar to any vector that seen as a three-phase process: 3 ##LTLine## ##LTLine##

text: diﬀerent

label: paragraph

text: indexing

text: techniques

text: need

text: to

text: be

text: applied;

text: e.g.,

text: nodes

text: arrived

text: more

text: than

text: can

text: never

text: be

text: pruned.

text: τ

text: log

text: λ

text: θ

label: section

text: PROBLEM

text: STATEMENT

text: time

text: units

text: earlier.

text: Consequently,

text: we

text: can

text: safely

text: prune

text: vectors

text: We

text: consider

text: data

text: items

text: represented

text: as

text: vectors

text: in

text: a

text: d-

text: that

text: are

text: older

text: than

text: τ.

text: We

text: call

text: τ

text: the

text: time

text: horizon.

text: R

text: dimensional

text: Euclidean

text: space

text: d.

text: In

text: real-world

text: applications,

text: Parameter

text: setting.

text: The

text: sssj

text: problem,

text: deﬁned

text: in

text: Prob-

text: the

text: dimensionality

text: d

text: is

text: typically

text: high,

text: while

text: the

text: data

text: items

text: lem

text: requires

text: two

text: parameters:

text: a

text: similarity

text: threshold

text: θ

text: and

text: are

text: sparse

text: vectors.

text: Given

text: two

text: vectors

text: x

text: x

text: x

text: and

text: d

text: a

text: time-decay

text: factor

text: λ.

text: The

text: time-ﬁltering

text: property

text: suggests

text: y

text: y

text: y

text: their

text: similarity

text: sim(x,

text: y)

text: is

text: the

text: dot-product

text: d

text: a

text: simple

text: methodology

text: to

text: set

text: these

text: two

text: parameters:

text: d

text: Select

text: θ

text: as

text: the

text: lowest

text: value

text: of

text: the

text: similarity

text: between

text: two

text: sim(x,

text: y)

text: dot(x,

text: y)

text: x

text: y

text: xj

text: yj.

text: simultaneously-arriving

text: vectors

text: that

text: are

text: deemed

text: similar.

text: Select

text: τ

text: as

text: the

text: smallest

text: diﬀerence

text: in

text: arrival

text: times

text: be-

text: We

text: assume

text: that

text: all

text: vectors

text: x

text: are

text: normalized

text: to

text: unit

text: length,

text: tween

text: two

text: identical

text: vectors

text: that

text: are

text: deemed

text: dissimilar.

text: i.e.,

text: x

text: which

text: implies

text: that

text: the

text: dot-product

text: of

text: two

text: Set

text: λ

text: τ−1

text: log

text: θ−1.

text: vectors

text: is

text: equal

text: to

text: their

text: cosine

text: similarity;

text: cos(x,

text: y)

text: dot(x,

text: y).

text: In

text: the

text: standard

text: all-pairs

text: similarity

text: search

text: problem

text: (apss),

text: Setting

text: θ

text: and

text: τ

text: in

text: steps

text: and

text: depends

text: on

text: the

text: application.

text: also

text: known

text: as

text: similarity

text: self-join,

text: we

text: are

text: given

text: a

text: set

text: of

text: vec-

text: Additional

text: notation.

text: When

text: referring

text: to

text: the

text: non-streaming

text: D

text: tors

text: and

text: a

text: similarity

text: threshold

text: θ,

text: and

text: the

text: ≥goal

text: is

text: to

text: ﬁnd

text: all

text: setting,

text: we

text: conRsider

text: a

text: dataset

text: xn

text: consisting

text: pairs

text: of

text: vectors

text: (x,

text: y)

text: for

text: which

text: sim(x,

text: y)

text: θ.

text: of

text: n

text: vectors

text: in

text: d.

text: In

text: this

text: paper

text: we

text: assume

text: that

text: the

text: input

text: items

text: arrive

text: as

text: a

text: Following

text: Anastasiu

text: and

text: Karypis,

text: we

text: use

text: the

text: notation

text: data

text: stream.

text: Each

text: vector

text: x

text: in

text: the

text: input

text: stream

text: is

text: times-

text: x

text: xp

text: and

text: to

text: denote

text: the

text: preﬁx

text: of

text: tamped

text: withS

text: time

text: of

text: its

text: arrival

text: t(x),

text: and

text: is

text: a

text: vector

text: x.

text: For

text: a

text: vector

text: x,

text: we

text: denote

text: by

text: vmx

text: its

text: maximum

text: denoted

text: by

text: (xi,

text: t(xi)),

text: coo|rd|inate,

text: by

text: Σx

text: j

text: xj

text: the

text: sum

text: of

text: its

text: coordinates,

text: and

text: We

text: deﬁne

text: the

text: similarity

text: of

text: two

text: vectors

text: x

text: and

text: y

text: by

text: con-

text: by

text: x

text: the

text: number

text: of

text: its

text: non-zero

text: coordinates.

text: D

text: sidering

text: not

text: only

text: their

text: coordinates

text: (xj,

text: yj),

text: but

text: also

text: the

text: dif-

text: Given

text: a

text: static

text: dataset

text: we

text: use

text: mj

text: to

text: refer

text: to

text: the

text: maxDi-

text: f|erenc−e

text: in

text: t|heir

text: arrival

text: times

text: in

text: the

text: input

text: stream

text: ∆txy

text: mum

text: value

text: along

text: the

text: j-th

text: coordinate

text: over

text: all

text: vectors

text: in

text: t(x)

text: t(y)

text: For

text: ﬁxed

text: coordinates,

text: the

text: larger

text: the

text: arrival

text: All

text: values

text: of

text: m

text: together

text: the

text: vector

text: m.

text: Our

text: meth-

text: j

text: time

text: diﬀerence

text: of

text: two

text: vectors,

text: the

text: smaller

text: their

text: similarity.

text: ods

text: use

text: indexing

text: schemes

text: which

text: build

text: an

text: index

text: incremen-

text: In

text: particular,

text: given

text: two

text: timestamped

text: vectors

text: x

text: and

text: y

text: we

text: tally,

text: We

text: use

text: m

text: to

text: refer

text: to

text: the

text: vector

text: deﬁne

text: their

text: time-dependent

text: similarity

text: sim∆t(x,

text: y)

text: as

text: to

text: the

text: dataset

text: that

text: is

text: already

text: indexed,

text: and

text: we

text: sim∆t(x,

text: y)

text: dot(x,

text: y)

text: e−λ|t(x)−t(y)|,

text: w(arnitde

text: mmλj

text: iittss

text: jj--tthh

text: ccoooorrddiinnaattee).

text: j

text: variant

text: of

text: m,

text: whose

text: precise

text: deﬁnition

text: is

text: given

text: in

text: Section

text: where

text: λ

text: is

text: a

text: time-decay

text: parameter.

text: This

text: time-dependent

text: similarity

text: reverts

text: to

text: the

text: standard

text: OVERVIEW

text: OF

text: THE

text: APPROACH

text: dot-product

text: (or

text: cosine)

text: similarity

text: when

text: ∆t

text: or

text: λ

text: xy

text: and

text: it

text: goes

text: to

text: zero

text: as

text: ∆t

text: approaches

text: inﬁnity,

text: at

text: an

text: ex-

text: xy

text: In

text: this

text: section

text: we

text: present

text: a

text: high-level

text: overview

text: of

text: our

text: main

text: ponential

text: rate

text: modulated

text: by

text: λ.

text: As

text: in

text: the

text: standard

text: apss

text: algorithms

text: for

text: the

text: sssj

text: problem.

text: problem,

text: given

text: a

text: similarity

text: threshold

text: θ,

text: two

text: vectors

text: x

text: and

text: y

text: We

text: present

text: two

text: diﬀerent

text: algorithmic

text: frameworks:

text: MB-IDX

text: are

text: called

text: similar

text: if

text: their

text: time-dependent

text: similarity

text: is

text: above

text: (MiniBatch-IDX)

text: and

text: STR-IDX

text: (Streaming-IDX),

text: where

text: IDX

text: the

text: threshold,

text: i.e.,

text: sim∆t(x,

text: y)

text: θ.

text: is

text: an

text: indexing

text: method

text: for

text: the

text: apss

text: problem

text: on

text: static

text: data.

text: We

text: can

text: now

text: deﬁne

text: the

text: streaming

text: version

text: of

text: the

text: apss

text: prob-

text: To

text: make

text: the

text: presentation

text: of

text: our

text: algorithms

text: more

text: clear,

text: we

text: lem,

text: called

text: the

text: streaming

text: similarity

text: self-join

text: problem

text: (sssj).

text: ﬁrst

text: give

text: an

text: overview

text: of

text: the

text: indexing

text: methods

text: for

text: the

text: static

text: apss

text: problem,

text: as

text: introduced

text: in

text: earlier

text: papers

text: Problem

text: (sssj).

text: Given

text: a

text: stream

text: of

text: timestamped

text: vec-

text: S

text: All

text: indexing

text: schemes

text: are

text: based

text: on

text: building

text: an

text: inverted

text: tors

text: a

text: similarity

text: threshold

text: θ,

text: and

text: a

text: time-decay

text: factor

text: λ,

text: I

text: index.

text: The

text: index

text: is

text: a

text: collection

text: of

text: d

text: posting

text: lists,

text: output

text: all

text: pairs

text: of

text: vectors

text: (x,

text: y)

text: in

text: the

text: stream

text: such

text: that

text: I

text: I

text: where

text: the

text: list

text: I

text: contains

text: all

text: pairs

text: (ι(x),

text: x

text: sim

text: (x,

text: y)

text: θ.

text: d

text: j

text: j

text: ∆t

text: such

text: that

text: the

text: j-th

text: coordinate

text: of

text: vector

text: x

text: is

text: non-zero,

text: i.e.,

text: x

text: Here

text: ι(x)

text: denotes

text: a

text: reference

text: to

text: vector

text: x.

text: j

text: Time

text: ﬁltering.

text: The

text: main

text: challenge

text: of

text: computing

text: a

text: self-

text: Some

text: methods

text: optimize

text: computation

text: by

text: not

text: indexing

text: the

text: join

text: in

text: a

text: data

text: stream

text: is

text: that,

text: in

text: principle,

text: unbounded

text: mem-

text: whole

text: dataset.

text: In

text: these

text: cases,

text: the

text: un-indexed

text: part

text: is

text: still

text: ory

text: is

text: required,

text: as

text: an

text: item

text: can

text: be

text: similar

text: with

text: any

text: other

text: item

text: needed

text: in

text: order

text: to

text: compute

text: exact

text: similarities.

text: Thus,

text: we

text: I

text: that

text: will

text: arrive

text: arbitrarily

text: far

text: in

text: the

text: future.

text: By

text: adopting

text: assume

text: that

text: a

text: separate

text: part

text: of

text: the

text: index

text: contains

text: the

text: un-

text: R

text: the

text: time-dependent

text: similarity

text: measure

text: sim∆t,

text: we

text: introduce

text: indexed

text: part

text: of

text: the

text: dataset,

text: called

text: residual

text: direct

text: index

text: a

text: forgetting

text: mechanism,

text: which

text: not

text: only

text: is

text: intuitive

text: from

text: an

text: All

text: schemes

text: build

text: the

text: index

text: incrementally,

text: while

text: also

text: com-

text: application

text: point-of-view,

text: but

text: also

text: allows

text: to

text: overcome

text: the

text: puting

text: similar

text: pairs.

text: In

text: particular,

text: we

text: start

text: with

text: an

text: empty

text: D

text: unbounded-memory

text: requirement.

text: In

text: particular,

text: since

text: for

text: index,

text: and

text: we

text: iteratively

text: process

text: the

text: vectors

text: in

text: For

text: each

text: -normalized

text: vectors

text: dot(x,

text: y)

text: we

text: have

text: newly-processed

text: vector

text: x,

text: we

text: compute

text: similar

text: pairs

text: (x,

text: y)

text: sim

text: (x,

text: y)

text: dot(x,

text: y)

text: e−λ∆txy

text: e−λ∆txy.

text: for

text: all

text: vectors

text: y

text: that

text: are

text: already

text: in

text: the

text: index.

text: Thereafter,

text: ∆t

text: we

text: add

text: (some

text: of)

text: the

text: non-zero

text: coordinates

text: of

text: x

text: to

text: the

text: index.

text: Thus,

text: ∆t

text: λ

text: log

text: θ

text: implies

text: sim

text: (x,

text: y)

text: θ,

text: and

text: as

text: Building

text: the

text: index

text: and

text: computing

text: similar

text: pairs

text: can

text: be

text: xy

text: ∆t

text: a

text: result

text: a

text: given

text: vector

text: cannot

text: be

text: similar

text: to

text: any

text: vector

text: that

text: seen

text: as

text: a

text: three-phase

text: process:

text: ##LTLine##

text: ##LTLine##


text: Algorithm 6: IndConstr-L2AP-STR Algorithm 7: CandGen-L2AP-STR I I input : Index , vector x, threshold θ, decay λ input : Index , vector x, threshold θ, decay λ I output: Updated similarity index including x, and output: Accum. score array C for candidate vectors { | ≥ } { ∈ D | } set of pairs P = (x, y) sim (x, y) θ (candidate set is C = y C[ι(y)] > 0 ) ← ∞ ← ∞ ∆t ← ∅ 1 b1 ← + ; b2 + 1 C ← ∞ (cid:98) ← ∞ 2 b1 ← 0 ← 2 rs1 ← + ; rs2 + 3 b2← 0; bt 0 I 3 rs1 ← dot(x←, mλ) 4 C ← CandGen-L2AP-STR( I, x, θ, λ) 4 rs2 1; rst 1 5 P CandVer-L2AP-STR(( , x, C, θ, λ) 5 foreach j = d . . . 1 s.t|.| x(cid:48)j||>∈0 do //revers≤e order 6 foreach j =←1 . . . d{ s.t. x}j > 0 do 6 foreach (ι(y)←, yj, y{j ) Ij −s.t. ∆t}xy τ do 78 pbs1c←←orbe1 + mxjinmibn1←{,mb√2j, vmx} 78 rifem(Csc[oι(rye)] ←>m0inorrrse1,mrssc2oereλ≥∆txθy) then 9 bt b{t + xj2}; b≥2 bt 9 C[ι(y)] ←C[ι(y)] + x|j|y(cid:48)j|| || (cid:48) || − 10 if minRb1, b2 ∅θ then 10 l2bound C[ι(y)] + xj yj e λ∆txy 11 if R[ι(x)] =← (cid:48)then 11 if l2bou(cid:98)nd←< θ then 12 [ι(x)]← xj 12 C[ι(y)] 0 1143 IjI←QI[ιj(∪x){](ι(xp)s,cxojr,e||x(cid:48)j||)} 1134 rrss1t ←←rrsst1−−xxjj2m; rλjs2 ← √rst 15 return ( , P) 15 return C; ≤ (cid:48) to index those coordinates y (cid:48) < y y , where p is the p j p Algorithm 8: CandVer-L2AP-STR newly computed boundary. I input : Index , vector x, candidate vector array C, Given that the similarity can increase only for vectors threshold θ, decay λ that have non-zero value in the dimensions of m that got up- { | ≥ } R output: Set of pairs P = (x, y) sim (x, y) θ dated, we can keep an inverted index of to avoid scanning ← ∅ ∆t every vector. We use the updated dimensions of the max 1 P vanecdtotrhemnjsctoanseolneclyt tthhoespeofsrsoimblethceanredsiiddautaels ifnodrerxe-Rin.dexing, 23 forepasc1h←←y(Cs.[tι.(yC)][ι+(yQ)][ι>({y0)]d)oe−λ∆txy } − Note that re-indexing inserts older vectors in the index. 4 ds1← (C[ι(y)] + min{|vm| x| Σ(cid:48)|y}(cid:48), vmy(cid:48) Σx ) e− λ∆txy As the lists always append items at the end, re-indexing 5 sz2 (≥C[ι(y)] + min≥ x , y vm≥x vmy(cid:48)) e λ∆txy introduces out-of-order items in the list. As explained in 6 if ps1← θ and ds1 θ an(cid:48) d sz2 θ) then Section 10, the loss of the time-ordered property hinders 7 s C≥[ι(y)] + dot(x, y ) one of the optimizations in pruning the index based on time 8 if s ←θ th∪en{ } ﬁltering (explained next). 9 P P (x, y, s) 10 return P Time ﬁltering (CG). To avoid continuously scanning the index, we adopt a lazy approach. The posting lists I are j (partially) sorted by time, i.e., newest items are always ap- We have observed that in general the (cid:96) -based bounds are pended to the tail of the lists. Thus, a simple linear scan 2 more eﬀective than the AP-based bounds. In almost all cases from the head of the lists is able to prune the lists lazily while the (cid:96) -based bounds are the ones that trigger. This observa- accumulating the similarity in the CG phase. More speciﬁ- 2 tion is also veriﬁed by the results of Anastasiu and Karypis cally, when a new vector x arrives, we scan all the posting (cid:54) [3]. Furthermore, as can be easily seen (by inspecting the lists I such that x = 0, in order to generate its candidates. j j || (cid:48) || red and green lines of Algorithms 2, 3, and 4), while the AP While scanning the lists, we drop any item (ι(y), y , y ) | − | j j bounds use statistics of the data in the index, the (cid:96) -based such that t(x) t(y) > τ. 2 bounds depend only on the vector being index. This im- The main loop of STR-L2AP is shown in Algorithm 5. The plies that by using only the (cid:96) -based bounds, one does not algorithm simply reads each item x in the stream, adds x 2 need to maintain the worst case vector m(t), and thus, no to the index, and computes the vectors that are similar to re-indexing is required. it, by calling IndConstr-L2AP-STR (Algorithm 6, including both red and green lines). Thus, the L2 index uses only the (cid:96)2-based bounds and discards the AP-based bounds. The static version of L2 (used 5.4 Improved L2-based indexing scheme in MB) is shown at Algorithms 2, 3, and 4, including the green lines and excluding the red ones. The main loop for the The last indexing scheme we present, L2, is an adaptation streaming case is IndConstr-L2-STR, shown as Algorithm 6, of L2AP, optimized for stream data. including the green lines and excluding the red ones. The idea for the improved index is based on the obser- vation that L2AP combines a number of diﬀerent bounds: 6. IMPLEMENTATION the bounds inherited from the AP scheme (e.g., b1 for in- dex construction, and rs for candidate generation) and the This section presents additional details and optimizations 1 new (cid:96) -based bounds introduced by Anastasiu and Karypis for both of our algorithmic frameworks, MB and STR. 2 [3] (e.g., b2 for index construction, and rs2 and l2bound for 6.1 Minibatch candidate generation). 7 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Algorithm

text: Algorithm

text: I

text: I

text: input

text: Index

text: vector

text: x,

text: threshold

text: θ,

text: decay

text: λ

text: input

text: Index

text: vector

text: x,

text: threshold

text: θ,

text: decay

text: λ

text: I

text: output:

text: Updated

text: similarity

text: index

text: including

text: x,

text: and

text: output:

text: Accum.

text: score

text: array

text: C

text: for

text: candidate

text: vectors

text: D

text: set

text: of

text: pairs

text: P

text: (x,

text: y)

text: sim

text: (x,

text: y)

text: θ

text: (candidate

text: set

text: is

text: C

text: y

text: C[ι(y)]

text: ∆t

text: C

text: bt

text: I

text: dot(x←,

text: mλ)

text: C

text: I,

text: x,

text: θ,

text: λ)

text: rst

text: P

text: x,

text: C,

text: θ,

text: λ)

text: foreach

text: j

text: d

text: s.t|.|

text: do

text: //revers≤e

text: order

text: foreach

text: j

text: d{

text: s.t.

text: x}j

text: do

text: foreach

text: (ι(y)←,

text: yj,

text: y{j

text: Ij

text: −s.t.

text: ∆t}xy

text: τ

text: do

text: vmx}

text: rifem(Csc[oι(rye)]

text: then

text: bt

text: b{t

text: bt

text: C[ι(y)]

text: ←C[ι(y)]

text: if

text: ∅θ

text: then

text: C[ι(y)]

text: xj

text: yj

text: e

text: λ∆txy

text: if

text: R[ι(x)]

text: if

text: θ

text: then

text: [ι(x)]←

text: xj

text: C[ι(y)]

text: √rst

text: return

text: P)

text: return

text: C;

text: to

text: index

text: those

text: coordinates

text: y

text: y

text: y

text: where

text: p

text: is

text: the

text: p

text: j

text: p

text: Algorithm

text: newly

text: computed

text: boundary.

text: I

text: input

text: Index

text: vector

text: x,

text: candidate

text: vector

text: array

text: C,

text: Given

text: that

text: the

text: similarity

text: can

text: increase

text: only

text: for

text: vectors

text: threshold

text: θ,

text: decay

text: λ

text: that

text: have

text: non-zero

text: value

text: in

text: the

text: dimensions

text: of

text: m

text: that

text: got

text: up-

text: R

text: output:

text: Set

text: of

text: pairs

text: P

text: (x,

text: y)

text: sim

text: (x,

text: y)

text: θ

text: dated,

text: we

text: can

text: keep

text: an

text: inverted

text: index

text: of

text: to

text: avoid

text: scanning

text: ∆t

text: every

text: vector.

text: We

text: use

text: the

text: updated

text: dimensions

text: of

text: the

text: max

text: P

text: vanecdtotrhemnjsctoanseolneclyt

text: ifnodrerxe-Rin.dexing,

text: Note

text: that

text: re-indexing

text: inserts

text: older

text: vectors

text: in

text: the

text: index.

text: (C[ι(y)]

text: min{|vm|

text: x|

text: Σx

text: e−

text: λ∆txy

text: As

text: the

text: lists

text: always

text: append

text: items

text: at

text: the

text: end,

text: re-indexing

text: (≥C[ι(y)]

text: min≥

text: x

text: y

text: vm≥x

text: e

text: λ∆txy

text: introduces

text: out-of-order

text: items

text: in

text: the

text: list.

text: As

text: explained

text: in

text: if

text: θ

text: and

text: θ

text: d

text: θ)

text: then

text: Section

text: the

text: loss

text: of

text: the

text: time-ordered

text: property

text: hinders

text: s

text: C≥[ι(y)]

text: dot(x,

text: y

text: one

text: of

text: the

text: optimizations

text: in

text: pruning

text: the

text: index

text: based

text: on

text: time

text: if

text: s

text: ←θ

text: th∪en{

text: ﬁltering

text: (explained

text: next).

text: P

text: P

text: (x,

text: y,

text: s)

text: return

text: P

text: Time

text: ﬁltering

text: (CG).

text: To

text: avoid

text: continuously

text: scanning

text: the

text: index,

text: we

text: adopt

text: a

text: lazy

text: approach.

text: The

text: posting

text: lists

text: I

text: are

text: j

text: (partially)

text: sorted

text: by

text: time,

text: i.e.,

text: newest

text: items

text: are

text: always

text: ap-

text: We

text: have

text: observed

text: that

text: in

text: general

text: the

text: -based

text: bounds

text: are

text: pended

text: to

text: the

text: tail

text: of

text: the

text: lists.

text: Thus,

text: a

text: simple

text: linear

text: scan

text: more

text: eﬀective

text: than

text: the

text: AP-based

text: bounds.

text: In

text: almost

text: all

text: cases

text: from

text: the

text: head

text: of

text: the

text: lists

text: is

text: able

text: to

text: prune

text: the

text: lists

text: lazily

text: while

text: the

text: -based

text: bounds

text: are

text: the

text: ones

text: that

text: trigger.

text: This

text: observa-

text: accumulating

text: the

text: similarity

text: in

text: the

text: CG

text: phase.

text: More

text: speciﬁ-

text: tion

text: is

text: also

text: veriﬁed

text: by

text: the

text: results

text: of

text: Anastasiu

text: and

text: Karypis

text: cally,

text: when

text: a

text: new

text: vector

text: x

text: arrives,

text: we

text: scan

text: all

text: the

text: posting

text: Furthermore,

text: as

text: can

text: be

text: easily

text: seen

text: (by

text: inspecting

text: the

text: lists

text: I

text: such

text: that

text: x

text: in

text: order

text: to

text: generate

text: its

text: candidates.

text: j

text: j

text: red

text: and

text: green

text: lines

text: of

text: Algorithms

text: and

text: while

text: the

text: AP

text: While

text: scanning

text: the

text: lists,

text: we

text: drop

text: any

text: item

text: (ι(y),

text: y

text: y

text: j

text: j

text: bounds

text: use

text: statistics

text: of

text: the

text: data

text: in

text: the

text: index,

text: the

text: -based

text: such

text: that

text: t(x)

text: t(y)

text: τ.

text: bounds

text: depend

text: only

text: on

text: the

text: vector

text: being

text: index.

text: This

text: im-

text: The

text: main

text: loop

text: of

text: is

text: shown

text: in

text: Algorithm

text: The

text: plies

text: that

text: by

text: using

text: only

text: the

text: -based

text: bounds,

text: one

text: does

text: not

text: algorithm

text: simply

text: reads

text: each

text: item

text: x

text: in

text: the

text: stream,

text: adds

text: x

text: need

text: to

text: maintain

text: the

text: worst

text: case

text: vector

text: m(t),

text: and

text: thus,

text: no

text: to

text: the

text: index,

text: and

text: computes

text: the

text: vectors

text: that

text: are

text: similar

text: to

text: re-indexing

text: is

text: required.

text: it,

text: by

text: calling

text: (Algorithm

text: including

text: both

text: red

text: and

text: green

text: lines).

text: Thus,

text: the

text: index

text: uses

text: only

text: the

text: bounds

text: and

text: discards

text: the

text: AP-based

text: bounds.

text: The

text: static

text: version

text: of

text: (used

text: Improved

text: indexing

text: scheme

text: in

text: MB)

text: is

text: shown

text: at

text: Algorithms

text: and

text: including

text: the

text: green

text: lines

text: and

text: excluding

text: the

text: red

text: ones.

text: The

text: main

text: loop

text: for

text: the

text: The

text: last

text: indexing

text: scheme

text: we

text: present,

text: is

text: an

text: adaptation

text: streaming

text: case

text: is

text: shown

text: as

text: Algorithm

text: of

text: optimized

text: for

text: stream

text: data.

text: including

text: the

text: green

text: lines

text: and

text: excluding

text: the

text: red

text: ones.

text: The

text: idea

text: for

text: the

text: improved

text: index

text: is

text: based

text: on

text: the

text: obser-

text: vation

text: that

text: combines

text: a

text: number

text: of

text: diﬀerent

text: bounds:

text: IMPLEMENTATION

text: the

text: bounds

text: inherited

text: from

text: the

text: AP

text: scheme

text: (e.g.,

text: for

text: in-

text: dex

text: construction,

text: and

text: rs

text: for

text: candidate

text: generation)

text: and

text: the

text: This

text: section

text: presents

text: additional

text: details

text: and

text: optimizations

text: new

text: -based

text: bounds

text: introduced

text: by

text: Anastasiu

text: and

text: Karypis

text: for

text: both

text: of

text: our

text: algorithmic

text: frameworks,

text: MB

text: and

text: STR.

text: (e.g.,

text: for

text: index

text: construction,

text: and

text: and

text: for

text: Minibatch

text: candidate

text: generation).

text: ##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: TETRISATION OF MESHES 3 3. AS-RIGID-AS-POSSIBLE DEFORMATION FRAMEWORK In this section, we recall the ARAP framework by describing an algorithm for shape blending. Note that although we discuss shape blending as the primary application, the framework and our improve- ment is not limited to it. Indeed, after being introduced in [1] initially as a morphing algorithm, the ARAP technique has been serving as one of the fundamental frameworks for various kinds of shape deformation applications (see, for example, [3, 7, 14, 15, 16]). ≤ ≤Our problem setting is as follows. We are given a rest shape V0 and m≤its≤deformations Vj (1 j m). That is, a vertex correspondence between V0 and e(cid:40)ach of Vj (1 j m) is{as}sumed. We would like to compute the def{orm∈atiRon| V (≤w1,.≤..,w}m) by blending the given shapes Vj according to the user speciﬁed weights w 1 j m . We insist that it interpolates the given shapes, j 1 ( j = k) i.e., V (0,...,0) = V0, and V (w1,...,wm) = Vk when wj = (cid:54) . Notice we allow negative 0 ( j = k) weights and weights greater than one so that the system can not only interpolate but also extrapolate. Remark 3.1. A basic shape blending is achieved by simply taking the linear combination of the co- ordinates of the vertices. This method is very fast and widely used to produce variations of shapes, in particular, facial expressions. However, since the geometry of shapes is disregarded, it does not always produce plausible outputs (Fig. 2). The ARAP based method which we will describe below FIGURE 2. Interpolation between yellow shapes. Left: linear method, Right: our method takes geometry into account to obtain better results. We assume t§hat the rest shape is equipped with a non-degenerate tetrahedral structure (V0,T ). We will discuss in a method to associate one to a triangular mesh. Deﬁnition 3.2. A tetrahedral structure is a pair (V,T ), where the vertex set V consists of three { | ≤ ≤ } dimensional vectors and the set of tetrahedra T = Ti 1 i n consists of ordered tuples of four distinct vertices Ti = (vi ,vi ,vi ,vi ). Each vertex in V must be contained in at least one tetrahedron. 1 2 3 4 A tetrahedral structure is said to be non-degenerate when the vertices of each tetrahedron are not co-planar. We emphasise that a triangle can be shared by three or more tetrahedra, and for this reason, we use the terminology “tetrahedral structure” rather than tetrahedral mesh. × The information of a tetrahedral structure (V,T ) can be packed into a collection of 4 4-matrices: ##LTFigure## ##LTFigure##

text: TETRISATION

text: OF

text: MESHES

text: AS-RIGID-AS-POSSIBLE

text: DEFORMATION

text: FRAMEWORK

text: In

text: this

text: section,

text: we

text: recall

text: the

text: ARAP

text: framework

text: by

text: describing

text: an

text: algorithm

text: for

text: shape

text: blending.

text: Note

text: that

text: although

text: we

text: discuss

text: shape

text: blending

text: as

text: the

text: primary

text: application,

text: the

text: framework

text: and

text: our

text: improve-

text: ment

text: is

text: not

text: limited

text: to

text: it.

text: Indeed,

text: after

text: being

text: introduced

text: in

text: initially

text: as

text: a

text: morphing

text: algorithm,

text: the

text: ARAP

text: technique

text: has

text: been

text: serving

text: as

text: one

text: of

text: the

text: fundamental

text: frameworks

text: for

text: various

text: kinds

text: of

text: shape

text: deformation

text: applications

text: (see,

text: for

text: example,

text: ≤Our

text: problem

text: setting

text: is

text: as

text: follows.

text: We

text: are

text: given

text: a

text: rest

text: shape

text: and

text: m≤its≤deformations

text: Vj

text: j

text: m).

text: That

text: is,

text: a

text: vertex

text: correspondence

text: between

text: and

text: of

text: Vj

text: j

text: m)

text: is{as}sumed.

text: We

text: would

text: like

text: to

text: compute

text: the

text: def{orm∈atiRon|

text: V

text: by

text: blending

text: the

text: given

text: shapes

text: Vj

text: according

text: to

text: the

text: user

text: speciﬁed

text: weights

text: w

text: j

text: m

text: We

text: insist

text: that

text: it

text: interpolates

text: the

text: given

text: shapes,

text: j

text: j

text: k)

text: i.e.,

text: V

text: and

text: V

text: Vk

text: when

text: wj

text: Notice

text: we

text: allow

text: negative

text: j

text: k)

text: weights

text: and

text: weights

text: greater

text: than

text: one

text: so

text: that

text: the

text: system

text: can

text: not

text: only

text: interpolate

text: but

text: also

text: extrapolate.

text: Remark

text: A

text: basic

text: shape

text: blending

text: is

text: achieved

text: by

text: simply

text: taking

text: the

text: linear

text: combination

text: of

text: the

text: co-

text: ordinates

text: of

text: the

text: vertices.

text: This

text: method

text: is

text: very

text: fast

text: and

text: widely

text: used

text: to

text: produce

text: variations

text: of

text: shapes,

text: in

text: particular,

text: facial

text: expressions.

text: However,

text: since

text: the

text: geometry

text: of

text: shapes

text: is

text: disregarded,

text: it

text: does

text: not

text: always

text: produce

text: plausible

text: outputs

text: (Fig.

text: The

text: ARAP

text: based

text: method

text: which

text: we

text: will

text: describe

text: below

text: FIGURE

text: Interpolation

text: between

text: yellow

text: shapes.

text: Left:

text: linear

text: method,

text: Right:

text: our

text: method

text: takes

text: geometry

text: into

text: account

text: to

text: obtain

text: better

text: results.

text: We

text: assume

text: t§hat

text: the

text: rest

text: shape

text: is

text: equipped

text: with

text: a

text: non-degenerate

text: tetrahedral

text: structure

text: We

text: will

text: discuss

text: in

text: a

text: method

text: to

text: associate

text: one

text: to

text: a

text: triangular

text: mesh.

text: Deﬁnition

text: A

text: tetrahedral

text: structure

text: is

text: a

text: pair

text: (V,T

text: where

text: the

text: vertex

text: set

text: V

text: consists

text: of

text: three

text: dimensional

text: vectors

text: and

text: the

text: set

text: of

text: tetrahedra

text: T

text: Ti

text: i

text: n

text: consists

text: of

text: ordered

text: tuples

text: of

text: four

text: distinct

text: vertices

text: Ti

text: (vi

text: ,vi

text: ,vi

text: ,vi

text: Each

text: vertex

text: in

text: V

text: must

text: be

text: contained

text: in

text: at

text: least

text: one

text: tetrahedron.

text: A

text: tetrahedral

text: structure

text: is

text: said

text: to

text: be

text: non-degenerate

text: when

text: the

text: vertices

text: of

text: each

text: tetrahedron

text: are

text: not

text: co-planar.

text: We

text: emphasise

text: that

text: a

text: triangle

text: can

text: be

text: shared

text: by

text: three

text: or

text: more

text: tetrahedra,

text: and

text: for

text: this

text: reason,

text: we

text: use

text: the

text: terminology

text: “tetrahedral

text: structure”

text: rather

text: than

text: tetrahedral

text: mesh.

text: The

text: information

text: of

text: a

text: tetrahedral

text: structure

text: (V,T

text: can

text: be

text: packed

text: into

text: a

text: collection

text: of

text: ##LTFigure##

text: ##LTFigure##


text: TETRISATION OF MESHES 5 Deﬁnition 4.2. Given a non-degenerate triangular mesh (V,F ). A tetrisation of (V,F ) is a tetrahe- dral structure which consists of the vertex set V¯ and the set of tetrahedra T . We require (V¯ ,T ) to satisfy the following conditions: ⊂ (1) V V¯ . That is, V¯ is obtained by adding ghost vertices to V . (2) Each triangle in F has to be contained in at least one tetrahedron in T . (3) Each tetrahedron is non-degenerate, that is, the four vertices are not co-planar. These conditions are exactly what are required in the ARAP framework. We give three methods to produce tetrisation in the following. Recall that the unit normal vector − × − (v2 v1) (v3 v1) n(F) of a triangle F = (v1,v2,v3) is computed by | − × − |, where the denominator | − × − | (v2 v1) (v3 v1) (v2 v1) (v3 v1) is twice the area 2Area(F) of F. We begin with a simple method which has been commonly used in various applications. For each triangle F = (v1,v2,v3) in F , add the ghost verte(cid:112)x − × − (v1 + v2 + v3) (v2 v1) (v3 v1) v0 = + | − × − | 3 (v2 v1) (v3 v1) and form a tetrahedron (v0,v1,v2,v3). The resulting tetrahedral structure has #T = #F and #V¯ = #V + #T . FIGURE 3. Left: the original surface, Right: its face-normal tetrisation. Ghost vertices are marked with a red circle. A problem with this tetrisation when applied to the ARAP framework is that this does not capture the relation between adjacent triangles. For example, consider two triangles sharing an edge as in Fig. § 3. Any rotation invariant error function (see ) with C1 = C2 = Id will be minimised regardless of the angle between the two triangles. In other words, folds do not cause any penalty in the error function. We assume each oriented edge appears only once among all the triangles. In other words, an unoriented edge should be contained at most two triangles with opposite orientations. Also, we assume all the triangles have at least one shared edge, that is, there is no “lone” triangle. (We can remove this assumption by adding ghost vertices not only for shared edges but also for all edges. However, this is inefﬁcient and makes no sense.) For each shared edge v1v2, denote by F1 = (v1,v2,v3) and F2 = (v1,v4,v2) the two triangles adjacent to it. Add a ghost vertex v1 + v2 | − | n(F1) + n(F2) v0 = + v1 v2 | | 2 n(F1) + n(F2) ##LTFigure## ##LTFigure## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: TETRISATION

text: OF

text: MESHES

text: Deﬁnition

text: Given

text: a

text: non-degenerate

text: triangular

text: mesh

text: (V,F

text: A

text: tetrisation

text: of

text: (V,F

text: is

text: a

text: tetrahe-

text: dral

text: structure

text: which

text: consists

text: of

text: the

text: vertex

text: set

text: V¯

text: and

text: the

text: set

text: of

text: tetrahedra

text: T

text: We

text: require

text: (V¯

text: ,T

text: to

text: satisfy

text: the

text: following

text: conditions:

label: list

text: V

text: V¯

text: That

text: is,

text: V¯

text: is

text: obtained

text: by

text: adding

text: ghost

text: vertices

text: to

text: V

text: Each

text: triangle

text: in

text: F

text: has

text: to

text: be

text: contained

text: in

text: at

text: least

text: one

text: tetrahedron

text: in

text: T

text: Each

text: tetrahedron

text: is

text: non-degenerate,

text: that

text: is,

text: the

text: four

text: vertices

text: are

text: not

text: co-planar.

text: These

text: conditions

text: are

text: exactly

text: what

text: are

text: required

text: in

text: the

text: ARAP

text: framework.

text: We

text: give

text: three

text: methods

text: to

text: produce

text: tetrisation

text: in

text: the

text: following.

text: Recall

text: that

text: the

text: unit

text: normal

text: vector

text: n(F)

text: of

text: a

text: triangle

text: F

text: is

text: computed

text: by

text: where

text: the

text: denominator

text: is

text: twice

text: the

text: area

text: of

text: F.

text: We

text: begin

text: with

text: a

text: simple

text: method

text: which

text: has

text: been

text: commonly

text: used

text: in

text: various

text: applications.

text: For

text: each

text: triangle

text: F

text: in

text: F

text: add

text: the

text: ghost

text: and

text: form

text: a

text: tetrahedron

text: The

text: resulting

text: tetrahedral

text: structure

text: has

text: #T

text: #F

text: and

text: #V¯

text: #V

text: #T

text: FIGURE

text: Left:

text: the

text: original

text: surface,

text: Right:

text: its

text: face-normal

text: tetrisation.

text: Ghost

text: vertices

text: are

text: marked

text: with

text: a

text: red

text: circle.

text: A

text: problem

text: with

text: this

text: tetrisation

text: when

text: applied

text: to

text: the

text: ARAP

text: framework

text: is

text: that

text: this

text: does

text: not

text: capture

text: the

text: relation

text: between

text: adjacent

text: triangles.

text: For

text: example,

text: consider

text: two

text: triangles

text: sharing

text: an

text: edge

text: as

text: in

text: Fig.

text: Any

text: rotation

text: invariant

text: error

text: function

text: (see

text: with

text: Id

text: will

text: be

text: minimised

text: regardless

text: of

text: the

text: angle

text: between

text: the

text: two

text: triangles.

text: In

text: other

text: words,

text: folds

text: do

text: not

text: cause

text: any

text: penalty

text: in

text: the

text: error

text: function.

text: We

text: assume

text: each

text: oriented

text: edge

text: appears

text: only

text: once

text: among

text: all

text: the

text: triangles.

text: In

text: other

text: words,

text: an

text: unoriented

text: edge

text: should

text: be

text: contained

text: at

text: most

text: two

text: triangles

text: with

text: opposite

text: orientations.

text: Also,

text: we

text: assume

text: all

text: the

text: triangles

text: have

text: at

text: least

text: one

text: shared

text: edge,

text: that

text: is,

text: there

text: is

text: no

text: “lone”

text: triangle.

text: (We

text: can

text: remove

text: this

text: assumption

text: by

text: adding

text: ghost

text: vertices

text: not

text: only

text: for

text: shared

text: edges

text: but

text: also

text: for

text: all

text: edges.

text: However,

text: this

text: is

text: inefﬁcient

text: and

text: makes

text: no

text: sense.)

text: For

text: each

text: shared

text: edge

text: denote

text: by

text: and

text: the

text: two

text: triangles

text: adjacent

text: to

text: it.

text: Add

text: a

text: ghost

text: vertex

text: ##LTFigure##

text: ##LTFigure##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 10 SHIZUO KAJI FIGURE 9. Top row from left to right: rest shape V0 and its two deformations V1 and V2 to be blended with weights w1 = 1.0 and w2 = 1.5. Second row from left to right: results obtained by face-normal, edge-normal, and vertex-normal tetrisation with E , T Third row: same as the second row but with E . S Initialisation part involves the Cholesky decomposition of the space matrix necessary to solve the minimiser of the error functions. This is computed only once in the initialisation process. Note that the matrix is dependent on the tetrahedral structure but independent of the choice of the error function. Runtime part consists of ﬁnding the minimiser of the error functions and the computation of Blend functions. TABLE 1. Timing comparison face E edge E vertex E face E edge E vertex E T T T S S S Initialisation (sec) 0.1976 0.3080 0.3556 0.1976 0.3080 0.3556 Runtime with Blend 45.45 fps 27.43 fps 30.86 fps 11.66 fps 4.132 fps 4.762 fps P Runtime with Blend 48.46 fps 29.31 fps 31.46 fps 12.19 fps 4.576 fps 5.037 fps C This work was partially supported by the Core Research for Evolutional Science and Technology (CREST) Program titled “Mathematics for Computer Graphics” of the Japan Science and Technol- ogy Agency (JST), by KAKENHI Grant-in-Aid for Young Scientists (B) 26800043, and by JSPS Postdoctoral Fellowships for Research Abroad. ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: SHIZUO

text: KAJI

text: FIGURE

text: Top

label: caption

text: row

text: from

text: left

text: to

text: right:

text: rest

text: shape

text: and

text: its

text: two

text: deformations

text: and

text: to

text: be

text: blended

text: with

text: weights

text: and

text: Second

text: row

text: from

text: left

text: to

text: right:

text: results

text: obtained

text: by

text: face-normal,

text: edge-normal,

text: and

text: vertex-normal

text: tetrisation

text: with

text: E

text: T

text: Third

text: row:

text: same

text: as

text: the

text: second

text: row

text: but

text: with

text: E

text: S

text: Initialisation

text: part

text: involves

text: the

text: Cholesky

text: decomposition

text: of

text: the

text: space

text: matrix

text: necessary

text: to

text: solve

text: the

text: minimiser

text: of

text: the

text: error

text: functions.

text: This

text: is

text: computed

text: only

text: once

text: in

text: the

text: initialisation

text: process.

text: Note

text: that

text: the

text: matrix

text: is

text: dependent

text: on

text: the

text: tetrahedral

text: structure

text: but

text: independent

text: of

text: the

text: choice

text: of

text: the

text: error

text: function.

text: Runtime

text: part

text: consists

text: of

text: ﬁnding

text: the

text: minimiser

text: of

text: the

text: error

text: functions

text: and

text: the

text: computation

text: of

text: Blend

text: functions.

text: TABLE

text: Timing

text: comparison

text: face

text: E

text: edge

text: E

text: vertex

text: E

text: face

text: E

text: edge

text: E

text: vertex

text: E

text: T

text: T

text: T

text: S

text: S

text: S

text: Initialisation

text: (sec)

text: Runtime

text: with

text: Blend

text: fps

text: fps

text: fps

text: fps

text: fps

text: fps

text: P

text: Runtime

text: with

text: Blend

text: fps

text: fps

text: fps

text: fps

text: fps

text: fps

text: C

text: This

text: work

text: was

text: partially

text: supported

text: by

text: the

text: Core

text: Research

text: for

text: Evolutional

text: Science

text: and

text: Technology

text: (CREST)

text: Program

text: titled

text: “Mathematics

text: for

text: Computer

text: Graphics”

text: of

text: the

text: Japan

text: Science

text: and

text: Technol-

text: ogy

text: Agency

text: (JST),

text: by

text: KAKENHI

text: Grant-in-Aid

text: for

text: Young

text: Scientists

text: (B)

text: and

text: by

text: JSPS

text: Postdoctoral

text: Fellowships

text: for

text: Research

text: Abroad.

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

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: 1 Introduction Since Sumer time [7], and –much later– Turing’s machine tape [13], read/write objects are certainly the most basic memory-based communication objects. Such an object, usually called a register, provides its users (processes) with a write operation which deﬁnes the new value of the register, and a read operation which returns the value of the register. When considering sequential computing, registers are universal in the sense that they allow to solve any problem that can be solved [13]. Register in message-passing systems In a message-passing system, the computing entities communi- cate only by sending and receiving messages transmitted through a communication network. Hence, in such a system, a register is not a communication object given for free, but constitutes a communication abstraction which must be built with the help of the communication network and the local memories of the processes. Several types of registers can be deﬁned according to which processes are allowed to read or write it, and the quality (semantics) of the value returned by each read operation. We consider here registers which are single-writer multi-reader (SWMR), and atomic. Atomicity means that (a) each read or write operation appears as if it had been executed instantaneously at a single point of the time line, between is start event and its end event, (b) no two operations appear at the same point of the time line, and (c) a read returns the value written by the closest preceding write operation (or the initial value of the register if there is no preceding write) [8]. Algorithms building multi-writer multi-reader (MWMR) atomic registers from single-writer single-reader (SWSR) registers with a weaker semantics (safe or regular registers) are described in several textbooks (e.g., [3, 9, 12]). Many distributed algorithms have been proposed, which build a register on top of a message-passing system, be it failure-free or failure-prone. In the failure-prone case, the addressed failure models are the process crash failure model, or the Byzantine process failure model (see, the textbooks [3, 9, 10, 11]). The most famous of these algorithms was proposed by H. Attiya, A. Bar-Noy, and D. Dolev in [2]. This algorithm, which is usually called ABD according to the names its authors, considers an n-process asynchronous system in which up to t < n/2 processes may crash (it is also shown in [2] that t < n/2 is an upper bound of the number of process crashes which can be tolerated). This simple and elegant algorithm, relies on (a) quorums [14], and (b) a simple broadcast/reply communication pattern. ABD uses this pattern once in a write operation, and twice in a read operation implementing an SWMR register. Fast operation To our knowledge, the notion of a fast implementation of an atomic register operation, in failure-prone asynchronous message-passing systems, was introduced in [5] for process crash failures, and in [6] for Byzantine process failures. These papers consider a three-component model, namely there are three different types of processes: a set of writers W , a set of readers R, and a set of servers S which implements the register. Moreover, a client (a writer or a reader) can communicate only with the servers, and the servers do not communicate among themselves. In these papers, fast means that a read or write operation must entail exactly one communication round-trip delay between a client (the writer or a reader) and the servers. When considering the process | | crash failure model (the one we are interested in in this paper), it is shown in [5] that, when ( W = ∧ ≥ ∧ | | ≥ | | | | − (cid:0) (cid:1) 1) (t 1) ( R 2), the condition ( R < S 2) is necessary and sufﬁcient to have fast read t and write operations (as deﬁned above), which implement an atomic register. It is also shown in [5] that | | ≥ ∧ | | ≥ ∧ ≥ there is no fast implementation of an MWMR atomic register if ( W 2) ( R 2) (t 1) . Content of the paper The work described in [5, 6] is mainly on the limits of the three-component model (writers, readers, and servers constitute three independent sets of processes) in the presence of process crash failures, or Byzantine process failures. These limits are captured by predicates involving the set of writers (W ), the set of readers (R), the set of servers (S), and the maximal number of servers 2 ##LTLine##

text: Introduction

text: Since

text: Sumer

text: time

text: and

text: –much

text: later–

text: Turing’s

text: machine

text: tape

text: read/write

text: objects

text: are

text: certainly

text: the

text: most

text: basic

text: memory-based

text: communication

text: objects.

text: Such

text: an

text: object,

text: usually

text: called

text: a

text: register,

text: provides

text: its

text: users

text: (processes)

text: with

text: a

text: write

text: operation

text: which

text: deﬁnes

text: the

text: new

text: value

text: of

text: the

text: register,

text: and

text: a

text: read

text: operation

text: which

text: returns

text: the

text: value

text: of

text: the

text: register.

text: When

text: considering

text: sequential

text: computing,

text: registers

text: are

text: universal

text: in

text: the

text: sense

text: that

text: they

text: allow

text: to

text: solve

text: any

text: problem

text: that

text: can

text: be

text: solved

text: Register

text: in

text: message-passing

text: systems

text: In

text: a

text: message-passing

text: system,

text: the

text: computing

text: entities

text: communi-

text: cate

text: only

text: by

text: sending

text: and

text: receiving

text: messages

text: transmitted

text: through

text: a

text: communication

text: network.

text: Hence,

text: in

text: such

text: a

text: system,

text: a

text: register

text: is

text: not

text: a

text: communication

text: object

text: given

text: for

text: free,

text: but

text: constitutes

text: a

text: communication

text: abstraction

text: which

text: must

text: be

text: built

text: with

text: the

text: help

text: of

text: the

text: communication

text: network

text: and

text: the

text: local

text: memories

text: of

text: the

text: processes.

text: Several

text: types

text: of

text: registers

text: can

text: be

text: deﬁned

text: according

text: to

text: which

text: processes

text: are

text: allowed

text: to

text: read

text: or

text: write

text: it,

text: and

text: the

text: quality

text: (semantics)

text: of

text: the

text: value

text: returned

text: by

text: each

text: read

text: operation.

text: We

text: consider

text: here

text: registers

text: which

text: are

text: single-writer

text: multi-reader

text: (SWMR),

text: and

text: atomic.

text: Atomicity

text: means

text: that

text: (a)

text: each

text: read

text: or

text: write

text: operation

text: appears

text: as

text: if

text: it

text: had

text: been

text: executed

text: instantaneously

text: at

text: a

text: single

text: point

text: of

text: the

text: time

text: line,

text: between

text: is

text: start

text: event

text: and

text: its

text: end

text: event,

text: (b)

text: no

text: two

text: operations

text: appear

text: at

text: the

text: same

text: point

text: of

text: the

text: time

text: line,

text: and

text: (c)

text: a

text: read

text: returns

text: the

text: value

text: written

text: by

text: the

text: closest

text: preceding

text: write

text: operation

text: (or

text: the

text: initial

text: value

text: of

text: the

text: register

text: if

text: there

text: is

text: no

text: preceding

text: write)

text: Algorithms

text: building

text: multi-writer

text: multi-reader

text: (MWMR)

text: atomic

text: registers

text: from

text: single-writer

text: single-reader

text: (SWSR)

text: registers

text: with

text: a

text: weaker

text: semantics

text: (safe

text: or

text: regular

text: registers)

text: are

text: described

text: in

text: several

text: textbooks

text: (e.g.,

text: Many

text: distributed

text: algorithms

text: have

text: been

text: proposed,

text: which

text: build

text: a

text: register

text: on

text: top

text: of

text: a

text: message-passing

text: system,

text: be

text: it

text: failure-free

text: or

text: failure-prone.

text: In

text: the

text: failure-prone

text: case,

text: the

text: addressed

text: failure

text: models

text: are

text: the

text: process

text: crash

text: failure

text: model,

text: or

text: the

text: Byzantine

text: process

text: failure

text: model

text: (see,

text: the

text: textbooks

text: The

text: most

text: famous

text: of

text: these

text: algorithms

text: was

text: proposed

text: by

text: H.

text: Attiya,

text: A.

text: Bar-Noy,

text: and

text: D.

text: Dolev

text: in

text: This

text: algorithm,

text: which

text: is

text: usually

text: called

text: ABD

text: according

text: to

text: the

text: names

text: its

text: authors,

text: considers

text: an

text: n-process

text: asynchronous

text: system

text: in

text: which

text: up

text: to

text: t

text: processes

text: may

text: crash

text: (it

text: is

text: also

text: shown

text: in

text: that

text: t

text: is

text: an

text: upper

text: bound

text: of

text: the

text: number

text: of

text: process

text: crashes

text: which

text: can

text: be

text: tolerated).

text: This

text: simple

text: and

text: elegant

text: algorithm,

text: relies

text: on

text: (a)

text: quorums

text: and

text: (b)

text: a

text: simple

text: broadcast/reply

text: communication

text: pattern.

text: ABD

text: uses

text: this

text: pattern

text: once

text: in

text: a

text: write

text: operation,

text: and

text: twice

text: in

text: a

text: read

text: operation

text: implementing

text: an

text: SWMR

text: register.

text: Fast

text: operation

text: To

text: our

text: knowledge,

text: the

text: notion

text: of

text: a

text: fast

text: implementation

text: of

text: an

text: atomic

text: register

text: operation,

text: in

text: failure-prone

text: asynchronous

text: message-passing

text: systems,

text: was

text: introduced

text: in

text: for

text: process

text: crash

text: failures,

text: and

text: in

text: for

text: Byzantine

text: process

text: failures.

text: These

text: papers

text: consider

text: a

text: three-component

text: model,

text: namely

text: there

text: are

text: three

text: different

text: types

text: of

text: processes:

text: a

text: set

text: of

text: writers

text: W

text: a

text: set

text: of

text: readers

text: R,

text: and

text: a

text: set

text: of

text: servers

text: S

text: which

text: implements

text: the

text: register.

text: Moreover,

text: a

text: client

text: (a

text: writer

text: or

text: a

text: reader)

text: can

text: communicate

text: only

text: with

text: the

text: servers,

text: and

text: the

text: servers

text: do

text: not

text: communicate

text: among

text: themselves.

text: In

text: these

text: papers,

text: fast

text: means

text: that

text: a

text: read

text: or

text: write

text: operation

text: must

text: entail

text: exactly

text: one

text: communication

text: round-trip

text: delay

text: between

text: a

text: client

text: (the

text: writer

text: or

text: a

text: reader)

text: and

text: the

text: servers.

text: When

text: considering

text: the

text: process

text: crash

text: failure

text: model

text: (the

text: one

text: we

text: are

text: interested

text: in

text: in

text: this

text: paper),

text: it

text: is

text: shown

text: in

text: that,

text: when

text: W

text: (t

text: R

text: the

text: condition

text: R

text: S

text: is

text: necessary

text: and

text: sufﬁcient

text: to

text: have

text: fast

text: read

text: t

text: and

text: write

text: operations

text: (as

text: deﬁned

text: above),

text: which

text: implement

text: an

text: atomic

text: register.

text: It

text: is

text: also

text: shown

text: in

text: that

text: there

text: is

text: no

text: fast

text: implementation

text: of

text: an

text: MWMR

text: atomic

text: register

text: if

text: W

text: R

text: (t

text: Content

text: of

text: the

text: paper

text: The

text: work

text: described

text: in

text: is

text: mainly

text: on

text: the

text: limits

text: of

text: the

text: three-component

text: model

text: (writers,

text: readers,

text: and

text: servers

text: constitute

text: three

text: independent

text: sets

text: of

text: processes)

text: in

text: the

text: presence

text: of

text: process

text: crash

text: failures,

text: or

text: Byzantine

text: process

text: failures.

text: These

text: limits

text: are

text: captured

text: by

text: predicates

text: involving

text: the

text: set

text: of

text: writers

text: (W

text: the

text: set

text: of

text: readers

text: (R),

text: the

text: set

text: of

text: servers

text: (S),

text: and

text: the

text: maximal

text: number

text: of

text: servers

text: ##LTLine##


text: Figure 2 presents a simple modiﬁcation of Algorithm 1, which allows a fast implementation of read operations whose executions are concurrent with a write operation during which the writer crashes. The modiﬁcations are underlined. When a process p receives a message READ(), it now returns a message STATE() containing an i additional ﬁeld, namely the current value of reg , its local copy of REG (line 12). i − When a process p receives from a process p a message STATE( , wsn, v), it uses it in the waiting i j predicate of line 5, but executes before the lines 7-11, as if this message was WRITE(wsn, v). According to the values of the predicates of lines 7, 9, and 10, this allows p to expedite the update of its local i variables wsn , reg , swsn , and res , thereby favoring fast termination. i i i i The reader can check that these modiﬁcations do not alter the proofs of Lemma 1 (termination) and Lemma 2 (atomicity). Hence, the proof of Theorem 1 is still correct. Lemma 6 A read operation which is not write-latency-free, and during which the writer crashes during the interfering write operation, takes at most 4∆ time units. Proof Let τ be the time at which the read operation starts. As in the proof of Lemma 4, the mes- r − − sages STATE(rsn, , ) received p by time τ + 2∆ can be such that some carry the sequence number i r wsn = x (due to last previous write) while some others carry the sequence number wsn = x + 1 (due to the concurrent write during which the writer crashes). If all these messages carry wsn = x, the − read terminates by time τ + 2∆. If at least one of these messages is STATE(rsn, x + 1, ), we have r ≥ maxwsn = x + 1, and p waits until the predicate swsn maxwsn (= x + 1) becomes true (line 5). i − i When it received STATE(rsn, x + 1, ), if not yet done, p broadcast the message WRITE(rsn, x + − i 1, ), (line 8 of Figure 2), which is received by the other processes within ∆ time units. If not yet done, − this entails the broadcast by each correct process of the same message WRITE(rsn, x + 1, ). Hence, at − most ∆ time units later, p has received the message WRITE(rsn, x + 1) from (n t) processes, which i entails the update of swsn to (x + 1). Consequently the predicate of line 5 becomes satisﬁed, and p i i terminates its read operation. When counting the number of consecutive communication steps, we have: The message READ(rsn) − by p , followed by a message STATE(rsn, x+1, ) sent by some process and received by p , followed by i i the message WRITE(rsn, x + 1) broadcast by p , followed by the message WRITE(rsn, x + 1) broadcast i by each non-crashed process (if not yet done). Hence, when the writer crashes during a concurrent read, the read returns within at most τ + 4∆ time units. (cid:50) r Lemma 6 CAMP Theorem 2 Algorithm 1 modiﬁed as indicated in Figure 2 implements in [t < n/2] an n,t SWMR atomic register with time-efﬁcient operations (where the time-efﬁciency notion is based on the bounded delay assumption). Proof The proof follows from Theorem 1 (termination and atomicity), Lemma 3, Lemma 4, Lemma 5, and Lemma 6 (time-efﬁciency). (cid:50) Theorem 2 5.3 Time-efﬁcient implementation: the round-based synchrony assumption As already indicated, this notion of a time-efﬁcient implementation assumes an underlying round- based synchronous communication system, where the duration of a round (duration of all message trans- fer delays) is δ. Lemma 7 The duration of write operation is 2δ. Proof The proof follows directly from the observation that the write operation terminates after a round- trip delay, whose duration is 2δ. (cid:50) Lemma 7 11

text: Figure

text: presents

text: a

text: simple

text: modiﬁcation

text: of

text: Algorithm

text: which

text: allows

text: a

text: fast

text: implementation

text: of

text: read

text: operations

text: whose

text: executions

text: are

text: concurrent

text: with

text: a

text: write

text: operation

text: during

text: which

text: the

text: writer

text: crashes.

text: The

text: modiﬁcations

text: are

text: underlined.

text: When

text: a

text: process

text: p

text: receives

text: a

text: message

text: READ(),

text: it

text: now

text: returns

text: a

text: message

text: STATE()

text: containing

text: an

text: i

text: additional

text: ﬁeld,

text: namely

text: the

text: current

text: value

text: of

text: reg

text: its

text: local

text: copy

text: of

text: REG

text: (line

text: i

text: When

text: a

text: process

text: p

text: receives

text: from

text: a

text: process

text: p

text: a

text: message

text: STATE(

text: wsn,

text: v),

text: it

text: uses

text: it

text: in

text: the

text: waiting

text: i

text: j

text: predicate

text: of

text: line

text: but

text: executes

text: before

text: the

text: lines

text: as

text: if

text: this

text: message

text: was

text: WRITE(wsn,

text: v).

text: According

text: to

text: the

text: values

text: of

text: the

text: predicates

text: of

text: lines

text: and

text: this

text: allows

text: p

text: to

text: expedite

text: the

text: update

text: of

text: its

text: local

text: i

text: variables

text: wsn

text: reg

text: swsn

text: and

text: res

text: thereby

text: favoring

text: fast

text: termination.

text: i

text: i

text: i

text: i

text: The

text: reader

text: can

text: check

text: that

text: these

text: modiﬁcations

text: do

text: not

text: alter

text: the

text: proofs

text: of

text: Lemma

text: (termination)

text: and

text: Lemma

text: (atomicity).

text: Hence,

text: the

text: proof

text: of

text: Theorem

text: is

text: still

text: correct.

text: Lemma

text: A

text: read

text: operation

text: which

text: is

text: not

text: write-latency-free,

text: and

text: during

text: which

text: the

text: writer

text: crashes

text: during

text: the

text: interfering

text: write

text: operation,

text: takes

text: at

text: most

text: 4∆

text: time

text: units.

text: Proof

text: Let

text: τ

text: be

text: the

text: time

text: at

text: which

text: the

text: read

text: operation

text: starts.

text: As

text: in

text: the

text: proof

text: of

text: Lemma

text: the

text: mes-

text: r

text: sages

text: STATE(rsn,

text: received

text: p

text: by

text: time

text: τ

text: 2∆

text: can

text: be

text: such

text: that

text: some

text: carry

text: the

text: sequence

text: number

text: i

text: r

text: wsn

text: x

text: (due

text: to

text: last

text: previous

text: write)

text: while

text: some

text: others

text: carry

text: the

text: sequence

text: number

text: wsn

text: x

text: (due

text: to

text: the

text: concurrent

text: write

text: during

text: which

text: the

text: writer

text: crashes).

text: If

text: all

text: these

text: messages

text: carry

text: wsn

text: x,

text: the

text: read

text: terminates

text: by

text: time

text: τ

text: If

text: at

text: least

text: one

text: of

text: these

text: messages

text: is

text: STATE(rsn,

text: x

text: we

text: have

text: r

text: maxwsn

text: x

text: and

text: p

text: waits

text: until

text: the

text: predicate

text: swsn

text: maxwsn

text: x

text: becomes

text: true

text: (line

text: i

text: i

text: When

text: it

text: received

text: STATE(rsn,

text: x

text: if

text: not

text: yet

text: done,

text: p

text: broadcast

text: the

text: message

text: WRITE(rsn,

text: x

text: i

text: (line

text: of

text: Figure

text: which

text: is

text: received

text: by

text: the

text: other

text: processes

text: within

text: time

text: units.

text: If

text: not

text: yet

text: done,

text: this

text: entails

text: the

text: broadcast

text: by

text: each

text: correct

text: process

text: of

text: the

text: same

text: message

text: WRITE(rsn,

text: x

text: Hence,

text: at

text: most

text: time

text: units

text: later,

text: p

text: has

text: received

text: the

text: message

text: WRITE(rsn,

text: x

text: from

text: (n

text: t)

text: processes,

text: which

text: i

text: entails

text: the

text: update

text: of

text: swsn

text: to

text: (x

text: Consequently

text: the

text: predicate

text: of

text: line

text: becomes

text: satisﬁed,

text: and

text: p

text: i

text: i

text: terminates

text: its

text: read

text: operation.

text: When

text: counting

text: the

text: number

text: of

text: consecutive

text: communication

text: steps,

text: we

text: have:

text: The

text: message

text: READ(rsn)

text: by

text: p

text: followed

text: by

text: a

text: message

text: STATE(rsn,

text: sent

text: by

text: some

text: process

text: and

text: received

text: by

text: p

text: followed

text: by

text: i

text: i

text: the

text: message

text: WRITE(rsn,

text: x

text: broadcast

text: by

text: p

text: followed

text: by

text: the

text: message

text: WRITE(rsn,

text: x

text: broadcast

text: i

text: by

text: each

text: non-crashed

text: process

text: (if

text: not

text: yet

text: done).

text: Hence,

text: when

text: the

text: writer

text: crashes

text: during

text: a

text: concurrent

text: read,

text: the

text: read

text: returns

text: within

text: at

text: most

text: τ

text: 4∆

text: time

text: units.

text: r

text: Lemma

text: CAMP

text: Theorem

text: Algorithm

text: modiﬁed

text: as

text: indicated

text: in

text: Figure

text: implements

text: in

text: [t

text: an

text: n,t

text: SWMR

text: atomic

text: register

text: with

text: time-efﬁcient

text: operations

text: (where

text: the

text: time-efﬁciency

text: notion

text: is

text: based

text: on

text: the

text: bounded

text: delay

text: assumption).

text: Proof

text: The

text: proof

text: follows

text: from

text: Theorem

text: (termination

text: and

text: atomicity),

text: Lemma

text: Lemma

text: Lemma

text: and

text: Lemma

text: (time-efﬁciency).

text: Theorem

text: Time-efﬁcient

text: implementation:

text: the

text: round-based

text: synchrony

text: assumption

text: As

text: already

text: indicated,

text: this

text: notion

text: of

text: a

text: time-efﬁcient

text: implementation

text: assumes

text: an

text: underlying

text: round-

text: based

text: synchronous

text: communication

text: system,

text: where

text: the

text: duration

text: of

text: a

text: round

text: (duration

text: of

text: all

text: message

text: trans-

text: fer

text: delays)

text: is

text: δ.

text: Lemma

text: The

text: duration

text: of

text: write

text: operation

text: is

text: Proof

text: The

text: proof

text: follows

text: directly

text: from

text: the

text: observation

text: that

text: the

text: write

text: operation

text: terminates

text: after

text: a

text: round-

text: trip

text: delay,

text: whose

text: duration

text: is

text: Lemma


text: It is important to remind that the proposed algorithm remains correct in the presence of any asyn- chrony pattern. Its time-efﬁciency features are particularly interesting when the system has long syn- chrony periods. Differently from the proposed algorithm, the ABD algorithm does not display different behaviors in different concurrency and failure patterns. In ABD, the duration of all write operations is upper bounded by 2∆ time units (or equal to 2δ), and the duration of all read operations is upper bounded by 4∆ time units (or equal to 4δ). The trade-off between ABD and our algorithm lies the message complexity, which is O(n) in ABD for both read and write operations, while it is O(n2) for a write operation and O(n) for a read operation in the proposed algorithm. Hence our algorithm is particularly interesting for registers used in read-dominated applications. Moreover, it helps us better understand the impact of the adversary pair “writer concurrency + writer failure” on the efﬁciency of the read operations. Acknowledgments This work has been partially supported by the Franco-German DFG-ANR Project 40300781 DIS- CMAT devoted to connections between mathematics and distributed computing, and the French ANR project DISPLEXITY devoted to the study of computability and complexity in distributed computing. References [1] Aguilera M.K., Chen W. and Toueg S., On quiescent reliable communication. SIAM Journal of Computing, 29(6):2040-2073, 2000. [2] Attiya H., Bar-Noy A. and Dolev D., Sharing memory robustly in message passing systems. Journal of the ACM, 42(1):121-132, 1995. [3] Attiya H. and Welch J., Distributed computing: fundamentals, simulations and advanced topics, (2d Edi- tion), Wiley-Interscience, 414 pages, 2004. [4] Herlihy M.P. and Wing J.M, Linearizability: a correctness condition for concurrent objects. ACM Transac- tions on Programming Languages and Systems, 12(3):463-492, 1990. [5] Dutta P., Guerraoui R., Levy R., and Chakraborty A., How fast can a distributed atomic read be? Proc. 23rd ACM Symposium on Principles of distributed computing (PODC’04 ), ACM Press, pp. 236-245, 2004. [6] Dutta P., Guerraoui R., Levy R., and Vukolic M., Fast access to distributed atomic memory. SIAM Journal of Computing, 39(8):3752-3783, 2010. [7] Kramer S.N., History Begins at Sumer: Thirty-Nine Firsts in Man’s Recorded History. University of Penn- sylvania Press, 416 pages, 1956 (ISBN 978-0-8122-1276-1). [8] Lamport L., On interprocess communication, Part I: basic formalism. Distributed Computing, 1(2):77-85, 1986. [9] Lynch N.A., Distributed algorithms. Morgan Kaufmann Pub., San Francisco (CA), 872 pages, 1996 (ISBN 1-55860-384-4). [10] Raynal M., Communication and agreement abstractions for fault-tolerant asynchronous distributed systems. Morgan & Claypool Publishers, 251 pages, 2010 (ISBN 978-1-60845-293-4). [11] Raynal M., Distributed algorithms for message-passing systems. Springer, 510 pages, 2013 (ISBN: 978-3- 642-38122-5). [12] Raynal M., Concurrent programming: algorithms, principles and foundations. Springer, 515 pages, 2013 (ISBN 978-3-642-32026-2). [13] Turing A.M., On computable numbers with an application to the Entscheidungsproblem. Proc. of the London Mathematical Society, 42:230-265, 1936. 13

text: It

text: is

text: important

text: to

text: remind

text: that

text: the

text: proposed

text: algorithm

text: remains

text: correct

text: in

text: the

text: presence

text: of

text: any

text: asyn-

text: chrony

text: pattern.

text: Its

text: time-efﬁciency

text: features

text: are

text: particularly

text: interesting

text: when

text: the

text: system

text: has

text: long

text: syn-

text: chrony

text: periods.

text: Differently

text: from

text: the

text: proposed

text: algorithm,

text: the

text: ABD

text: algorithm

text: does

text: not

text: display

text: different

text: behaviors

text: in

text: different

text: concurrency

text: and

text: failure

text: patterns.

text: In

text: ABD,

text: the

text: duration

text: of

text: all

text: write

text: operations

text: is

text: upper

text: bounded

text: by

text: 2∆

text: time

text: units

text: (or

text: equal

text: to

text: and

text: the

text: duration

text: of

text: all

text: read

text: operations

text: is

text: upper

text: bounded

text: by

text: 4∆

text: time

text: units

text: (or

text: equal

text: to

text: The

text: trade-off

text: between

text: ABD

text: and

text: our

text: algorithm

text: lies

text: the

text: message

text: complexity,

text: which

text: is

text: O(n)

text: in

text: ABD

text: for

text: both

text: read

text: and

text: write

text: operations,

text: while

text: it

text: is

text: for

text: a

text: write

text: operation

text: and

text: O(n)

text: for

text: a

text: read

text: operation

text: in

text: the

text: proposed

text: algorithm.

text: Hence

text: our

text: algorithm

text: is

text: particularly

text: interesting

text: for

text: registers

text: used

text: in

text: read-dominated

text: applications.

text: Moreover,

text: it

text: helps

text: us

text: better

text: understand

text: the

text: impact

text: of

text: the

text: adversary

text: pair

text: “writer

text: concurrency

text: writer

text: failure”

text: on

text: the

text: efﬁciency

text: of

text: the

text: read

text: operations.

text: Acknowledgments

text: This

text: work

text: has

text: been

text: partially

text: supported

text: by

text: the

text: Franco-German

text: DFG-ANR

text: Project

text: DIS-

text: CMAT

text: devoted

text: to

text: connections

text: between

text: mathematics

text: and

text: distributed

text: computing,

text: and

text: the

text: French

text: ANR

text: project

text: DISPLEXITY

text: devoted

text: to

text: the

text: study

text: of

text: computability

text: and

text: complexity

text: in

text: distributed

text: computing.

text: References

text: Aguilera

text: M.K.,

text: Chen

text: W.

text: and

text: Toueg

text: S.,

text: On

text: quiescent

text: reliable

text: communication.

text: SIAM

text: Journal

text: of

text: Computing,

text: Attiya

text: H.,

text: Bar-Noy

text: A.

text: and

text: Dolev

text: D.,

text: Sharing

text: memory

text: robustly

text: in

text: message

text: passing

text: systems.

text: Journal

text: of

text: the

text: ACM,

text: Attiya

text: H.

text: and

text: Welch

text: J.,

text: Distributed

text: computing:

text: fundamentals,

text: simulations

text: and

text: advanced

text: topics,

text: Edi-

text: tion),

text: Wiley-Interscience,

text: pages,

text: Herlihy

text: M.P.

text: and

text: Wing

text: J.M,

text: Linearizability:

text: a

text: correctness

text: condition

text: for

text: concurrent

text: objects.

text: ACM

text: Transac-

text: tions

text: on

text: Programming

text: Languages

text: and

text: Systems,

text: Dutta

text: P.,

text: Guerraoui

text: R.,

text: Levy

text: R.,

text: and

text: Chakraborty

text: A.,

text: How

text: fast

text: can

text: a

text: distributed

text: atomic

text: read

text: be?

text: Proc.

text: ACM

text: Symposium

text: on

text: Principles

text: of

text: distributed

text: computing

text: ACM

text: Press,

text: pp.

text: Dutta

text: P.,

text: Guerraoui

text: R.,

text: Levy

text: R.,

text: and

text: Vukolic

text: M.,

text: Fast

text: access

text: to

text: distributed

text: atomic

text: memory.

text: SIAM

text: Journal

text: of

text: Computing,

text: Kramer

text: S.N.,

text: History

text: Begins

text: at

text: Sumer:

text: Thirty-Nine

text: Firsts

text: in

text: Man’s

text: Recorded

text: History.

text: University

text: of

text: Penn-

text: sylvania

text: Press,

text: pages,

text: (ISBN

text: Lamport

text: L.,

text: On

text: interprocess

text: communication,

text: Part

text: I:

text: basic

text: formalism.

text: Distributed

text: Computing,

text: Lynch

text: N.A.,

text: Distributed

text: algorithms.

text: Morgan

text: Kaufmann

text: Pub.,

text: San

text: Francisco

text: (CA),

text: pages,

text: (ISBN

text: Raynal

text: M.,

text: Communication

text: and

text: agreement

text: abstractions

text: for

text: fault-tolerant

text: asynchronous

text: distributed

text: systems.

text: Morgan

text: Claypool

text: Publishers,

text: pages,

text: (ISBN

text: Raynal

text: M.,

text: Distributed

text: algorithms

text: for

text: message-passing

text: systems.

text: Springer,

text: pages,

text: (ISBN:

text: Raynal

text: M.,

text: Concurrent

text: programming:

text: algorithms,

text: principles

text: and

text: foundations.

text: Springer,

text: pages,

text: (ISBN

text: Turing

text: A.M.,

text: On

text: computable

text: numbers

text: with

text: an

text: application

text: to

text: the

text: Entscheidungsproblem.

text: Proc.

text: of

text: the

text: London

text: Mathematical

text: Society,


text: [14] Vukolic M., Quorum systems, with applications to storage and consensus. Morgan & Claypool Publishers, 132 pages, 2012 (ISBN 978-1-60845-683-3). 14

label: reference

text: Vukolic

text: M.,

text: Quorum

text: systems,

text: with

text: applications

text: to

text: storage

text: and

text: consensus.

text: Morgan

text: Claypool

text: Publishers,

text: pages,

text: (ISBN


text: restricting the points c to be of the form e in (2.2) is typically not one-to-one. Therefore, m J we need more general choices of the points c in the deﬁnition of the estimator. m In Gissibl and Klu¨ppelberg (2015), a link is established between max-linear models and structural equation models, from which graphical models based on directed acyclic graphs (DAGs) can be constructed. A max-linear structural equation model is deﬁned via ∨ Y = max u Y u Z , j = 1, . . . , d, j ∈ kj k j j k pa(j) ⊂ { } where pa(j) 1, . . . , d denotes the set of parents of node j in the graph, u > 0 for all ∈ ∪ { } ∈ { } kj k pa(j) j and u > 0 for all j 1, . . . , d . We let Z , . . . , Z be independent unit j 1 d Fr´echet random variables. A max-linear structural equation model can then be written as a max-linear model with parameters determined by the paths of the corresponding graph. We focus on the four-dimensional model corresponding to the following directed acyclic graph (Gissibl and Klu¨ppelberg, 2015, Example 2.1): Y1 u12 u13 Y = u Z , 1 1 1 ∨ ∨ Y = u Y u Z = u u Z u Z , 2 12 1 2 2 12 1 1 2 2 ∨ ∨ Y2 Y3 Y3 = u13Y1 u3Z3 = u13u1Z1 u3Z3, ∨ ∨ Y = u Y u Y u Z 4 24 2 34 3 4 4 ∨ ∨ ∨ ∨ u24 u34 = (u24u12u1 u34u13u1)Z1 u24u2Z2 u34u3Z3 u4Z4. Y4   If we require Y , . . . , Y to be unit Fr´echet, the matrix of factor loadings becomes 1 4      1 0 0 0  u u 0 0 B = 12 2 , u 0 u 0 ∨13 3 u u u u u u u u u 12 24 13 34 2 24 3 34 4 ∈ { } where the diagonal elements u for j 2, 3, 4 are such that the row sums are equal to one. j The parameter vector is then given by θ = (u , u , u , u ). 12 13 24 34 We conduct a simulation study based on 300 samples of size n = 1000 from the four- dimensional model with tail dependence function (3.3) and B as above, with parameter vector | | θ = (0.3, 0.8, 0.4, 0.55). As before, we put X = Y + (cid:15) , with (Y , . . . , Y ) as above and N ij ij ij i1 id (cid:15) independent (0, 1/4) random variables. The estimators are based on the q = 72 points ij { } c on the grid 0, 1/2, 1 4 having at least two positive coordinates. m Figure 3 shows the bias, standard deviation and RMSE for the estimator based on the − empirical tail dependence function with Ω(θ) = Σ(θ) 1 (solid lines), the estimator based − on the bias-corrected tail dependence function with Ω(θ) = Σ(θ) 1 (dotted lines) and the pairwise M-estimator from Einmahl et al. (2016) (dashed lines). The diﬀerence between the pairwise M-estimator and our estimators based on the empirical tail dependence function is 14 ##LTFigure##

text: restricting

text: the

text: points

text: c

text: to

text: be

text: of

text: the

text: form

text: e

text: in

text: is

text: typically

text: not

text: one-to-one.

text: Therefore,

text: m

text: J

text: we

text: need

text: more

text: general

text: choices

text: of

text: the

text: points

text: c

text: in

text: the

text: deﬁnition

text: of

text: the

text: estimator.

text: m

text: In

text: Gissibl

text: and

text: Klu¨ppelberg

text: a

text: link

text: is

text: established

text: between

text: max-linear

text: models

text: and

text: structural

text: equation

text: models,

text: from

text: which

text: graphical

text: models

text: based

text: on

text: directed

text: acyclic

text: graphs

text: (DAGs)

text: can

text: be

text: constructed.

text: A

text: max-linear

text: structural

text: equation

text: model

text: is

text: deﬁned

text: via

text: Y

text: max

text: u

text: Y

text: u

text: Z

text: j

text: d,

text: j

text: kj

text: k

text: j

text: j

text: k

text: pa(j)

text: where

text: pa(j)

text: d

text: denotes

text: the

text: set

text: of

text: parents

text: of

text: node

text: j

text: in

text: the

text: graph,

text: u

text: for

text: all

text: kj

text: k

text: pa(j)

text: j

text: and

text: u

text: for

text: all

text: j

text: d

text: We

text: let

text: Z

text: Z

text: be

text: independent

text: unit

text: j

text: d

text: Fr´echet

text: random

text: variables.

text: A

text: max-linear

text: structural

text: equation

text: model

text: can

text: then

text: be

text: written

text: as

text: a

text: max-linear

text: model

text: with

text: parameters

text: determined

text: by

text: the

text: paths

text: of

text: the

text: corresponding

text: graph.

text: We

text: focus

text: on

text: the

text: four-dimensional

text: model

text: corresponding

text: to

text: the

text: following

text: directed

text: acyclic

text: graph

text: (Gissibl

text: and

text: Klu¨ppelberg,

text: Example

text: Y

text: u

text: Z

text: Y

text: u

text: Y

text: u

text: Z

text: u

text: u

text: Z

text: u

text: Z

text: Y

text: u

text: Y

text: u

text: Y

text: u

text: Z

text: If

text: we

text: require

text: Y

text: Y

text: to

text: be

text: unit

text: Fr´echet,

text: the

text: matrix

text: of

text: factor

text: loadings

text: becomes

text: u

text: u

text: B

text: u

text: u

text: u

text: u

text: u

text: u

text: u

text: u

text: u

text: u

text: u

text: where

text: the

text: diagonal

text: elements

text: u

text: for

text: j

text: are

text: such

text: that

text: the

text: row

text: sums

text: are

text: equal

text: to

text: one.

text: j

text: The

text: parameter

text: vector

text: is

text: then

text: given

text: by

text: θ

text: (u

text: u

text: u

text: u

text: We

text: conduct

text: a

text: simulation

text: study

text: based

text: on

text: samples

text: of

text: size

text: n

text: from

text: the

text: four-

text: dimensional

text: model

text: with

text: tail

text: dependence

text: function

text: and

text: B

text: as

text: above,

text: with

text: parameter

text: vector

text: θ

text: As

text: before,

text: we

text: put

text: X

text: Y

text: with

text: (Y

text: Y

text: as

text: above

text: and

text: N

text: ij

text: ij

text: ij

text: id

text: independent

text: random

text: variables.

text: The

text: estimators

text: are

text: based

text: on

text: the

text: q

text: points

text: ij

text: c

text: on

text: the

text: grid

text: having

text: at

text: least

text: two

text: positive

text: coordinates.

text: m

text: Figure

text: shows

text: the

text: bias,

text: standard

text: deviation

text: and

text: RMSE

text: for

text: the

text: estimator

text: based

text: on

text: the

text: empirical

text: tail

text: dependence

text: function

text: with

text: Ω(θ)

text: Σ(θ)

text: (solid

text: lines),

text: the

text: estimator

text: based

text: on

text: the

text: bias-corrected

text: tail

text: dependence

text: function

text: with

text: Ω(θ)

text: Σ(θ)

text: (dotted

text: lines)

text: and

text: the

text: pairwise

text: M-estimator

text: from

text: Einmahl

text: et

text: al.

text: (dashed

text: lines).

text: The

text: diﬀerence

text: between

text: the

text: pairwise

text: M-estimator

text: and

text: our

text: estimators

text: based

text: on

text: the

text: empirical

text: tail

text: dependence

text: function

text: is

text: ##LTFigure##