text: (cid:48) · · · denoted by c c. The preference orders and approval counts of voters w and w{ }, where ∈ V ∈ V ∈ E a a,b ν i, ν j, (ν , ν ) , and a < b, are given below (to simplify notation, we assume a ∈ { b} a b i, j / 1, k ; it is easy to modify the construction for the case i = 1 or j = k). In what follows, the order of the non-approved candidates not shown in the preference lists can be (cid:67) deﬁned in any way that results in preferences that are single-peaked with respect to . · · · − | · · · (cid:31) − · · · w : succ(ck) prec2k2 5k+6(p) ck c1 prec2k2 5k+5(p) p a a · · · (cid:31) (cid:31) a(cid:31) a (cid:31) | w{ }: succ(cj ) prec(ci) cj ci prec(cj ) succ(ci) a,b a b a b a b ∈ ∪ { } We will now add extra votes to ensure that each candidate c CV q receives L − approvals, each dummy receives fewer than L approvals, while p receives L k approvals in (C, V ) for some suﬃciently large integer L. To do so, we ﬁrst make sure that all candidates in CV have the same number of approvals. ∈ To this end, if some candidate c CV has fewer approvals than another candidate in CV, · · · | · · · − | we add a vote c precB(c2) and a vote c succB(ck 1) to V . These two votes provide 1 \ { }N one extra approval point to each candidate in CV c and two extra approval points to c. Thus, by adding such pairs of votes iteratively, we can ensure that each candidate in CV has the same score. After equalizing the scores of all candidates in CV in this manner, we |V| |E| ∈ introduce + + B + 1 additional pairs of such votes for each c CV; this ensures that at this point each dummy receives strictly fewer approvals than candidates in CV. Let the resulting score of the candidates in CV be L; note that L > 2B + k. To obtain the required − scores for p and q, we add L k voters approving p only and L voters with preferences of · · · | the form q succB(q) . We denote by V the set of voters added to adjust the initial ∪ ∪ init scores; we let V = WV WE V . init This completes the construction, which is clearly polynomial in size. Note that the total approval score of each candidate is as required. Also, it is straightforward to check that the (cid:67) preferences of all voters are single-peaked with respect to the linear order . It remains to show the correctness of the reduction. Note that the total number of voters − in V is at least 3L k, while every candidate has at most L approvals. As L > k, it follows that no candidate is approved by a strict majority of voters in (C, V ). Moreover, since − L > 2B + k = 4k3 k, after any bribery that does not exceed the budget the score of each − (cid:98)| | (cid:99) candidate is at most L+B < (3L k)/2 < V /2 +1, and hence no candidate is approved by a majority of voters after any such bribery. Thus p can be made a winner under each of SP-AV, Fallback, and simpliﬁed Fallback if and only if p obtains the maximum number of approvals after some bribery. Thus, from now on, when we speak of a score of a candidate or a candidate’s number of points, we refer to this candidate’s number of approvals. To follow our arguments, the reader may ﬁnd it useful to keep Figure 2 in mind. First, suppose that there is a minimal successful support bribery t of cost at most B. · · · | Observe that lowering the approval counts in any of the votes q succB(q) in order to decrease q’s score would have a cost of B + 1. Thus, t cannot decrease q’s score, and hence (cid:67) it must increase p’s score by at least k points. Since p is preceded by B dummies in , it follows that in t the bribed voters form a subset of WV. 23

text: denoted

text: by

text: c

text: c.

text: The

text: preference

text: orders

text: and

text: approval

text: counts

text: of

text: voters

text: w

text: and

text: w{

text: where

text: V

text: V

text: E

text: a

text: a,b

text: ν

text: i,

text: ν

text: j,

text: (ν

text: ν

text: and

text: a

text: b,

text: are

text: given

text: below

text: (to

text: simplify

text: notation,

text: we

text: assume

text: a

text: b}

text: a

text: b

text: i,

text: j

text: k

text: it

text: is

text: easy

text: to

text: modify

text: the

text: construction

text: for

text: the

text: case

text: i

text: or

text: j

text: k).

text: In

text: what

text: follows,

text: the

text: order

text: of

text: the

text: non-approved

text: candidates

text: not

text: shown

text: in

text: the

text: preference

text: lists

text: can

text: be

text: deﬁned

text: in

text: any

text: way

text: that

text: results

text: in

text: preferences

text: that

text: are

text: single-peaked

text: with

text: respect

text: to

text: w

text: succ(ck)

text: ck

text: p

text: a

text: a

text: a

text: w{

text: succ(cj

text: prec(ci)

text: cj

text: ci

text: prec(cj

text: succ(ci)

text: a,b

text: a

text: b

text: a

text: b

text: a

text: b

text: We

text: will

text: now

text: add

text: extra

text: votes

text: to

text: ensure

text: that

text: each

text: candidate

text: c

text: CV

text: q

text: receives

text: L

text: approvals,

text: each

text: dummy

text: receives

text: fewer

text: than

text: L

text: approvals,

text: while

text: p

text: receives

text: L

text: k

text: approvals

text: in

text: (C,

text: V

text: for

text: some

text: suﬃciently

text: large

text: integer

text: L.

text: To

text: do

text: so,

text: we

text: ﬁrst

text: make

text: sure

text: that

text: all

text: candidates

text: in

text: CV

text: have

text: the

text: same

text: number

text: of

text: approvals.

text: To

text: this

text: end,

text: if

text: some

text: candidate

text: c

text: CV

text: has

text: fewer

text: approvals

text: than

text: another

text: candidate

text: in

text: CV,

text: we

text: add

text: a

text: vote

text: c

text: and

text: a

text: vote

text: c

text: succB(ck

text: to

text: V

text: These

text: two

text: votes

text: provide

text: }N

text: one

text: extra

text: approval

text: point

text: to

text: each

text: candidate

text: in

text: CV

text: c

text: and

text: two

text: extra

text: approval

text: points

text: to

text: c.

text: Thus,

text: by

text: adding

text: such

text: pairs

text: of

text: votes

text: iteratively,

text: we

text: can

text: ensure

text: that

text: each

text: candidate

text: in

text: CV

text: has

text: the

text: same

text: score.

text: After

text: equalizing

text: the

text: scores

text: of

text: all

text: candidates

text: in

text: CV

text: in

text: this

text: manner,

text: we

text: |V|

text: |E|

text: introduce

text: B

text: additional

text: pairs

text: of

text: such

text: votes

text: for

text: each

text: c

text: CV;

text: this

text: ensures

text: that

text: at

text: this

text: point

text: each

text: dummy

text: receives

text: strictly

text: fewer

text: approvals

text: than

text: candidates

text: in

text: CV.

text: Let

text: the

text: resulting

text: score

text: of

text: the

text: candidates

text: in

text: CV

text: be

text: L;

text: note

text: that

text: L

text: k.

text: To

text: obtain

text: the

text: required

text: scores

text: for

text: p

text: and

text: q,

text: we

text: add

text: L

text: k

text: voters

text: approving

text: p

text: only

text: and

text: L

text: voters

text: with

text: preferences

text: of

text: the

text: form

text: q

text: succB(q)

text: We

text: denote

text: by

text: V

text: the

text: set

text: of

text: voters

text: added

text: to

text: adjust

text: the

text: initial

text: init

text: scores;

text: we

text: let

text: V

text: WV

text: WE

text: V

text: init

text: This

text: completes

text: the

text: construction,

text: which

text: is

text: clearly

text: polynomial

text: in

text: size.

text: Note

text: that

text: the

text: total

text: approval

text: score

text: of

text: each

text: candidate

text: is

text: as

text: required.

text: Also,

text: it

text: is

text: straightforward

text: to

text: check

text: that

text: the

text: preferences

text: of

text: all

text: voters

text: are

text: single-peaked

text: with

text: respect

text: to

text: the

text: linear

text: order

text: It

text: remains

text: to

text: show

text: the

text: correctness

text: of

text: the

text: reduction.

text: Note

text: that

text: the

text: total

text: number

text: of

text: voters

text: in

text: V

text: is

text: at

text: least

text: k,

text: while

text: every

text: candidate

text: has

text: at

text: most

text: L

text: approvals.

text: As

text: L

text: k,

text: it

text: follows

text: that

text: no

text: candidate

text: is

text: approved

text: by

text: a

text: strict

text: majority

text: of

text: voters

text: in

text: (C,

text: V

text: Moreover,

text: since

text: L

text: k

text: k,

text: after

text: any

text: bribery

text: that

text: does

text: not

text: exceed

text: the

text: budget

text: the

text: score

text: of

text: each

text: candidate

text: is

text: at

text: most

text: L+B

text: V

text: and

text: hence

text: no

text: candidate

text: is

text: approved

text: by

text: a

text: majority

text: of

text: voters

text: after

text: any

text: such

text: bribery.

text: Thus

text: p

text: can

text: be

text: made

text: a

text: winner

text: under

text: each

text: of

text: SP-AV,

text: Fallback,

text: and

text: simpliﬁed

text: Fallback

text: if

text: and

text: only

text: if

text: p

text: obtains

text: the

text: maximum

text: number

text: of

text: approvals

text: after

text: some

text: bribery.

text: Thus,

text: from

text: now

text: on,

text: when

text: we

text: speak

text: of

text: a

text: score

text: of

text: a

text: candidate

text: or

text: a

text: candidate’s

text: number

text: of

text: points,

text: we

text: refer

text: to

text: this

text: candidate’s

text: number

text: of

text: approvals.

text: To

text: follow

text: our

text: arguments,

text: the

text: reader

text: may

text: ﬁnd

text: it

text: useful

text: to

text: keep

text: Figure

text: in

text: mind.

text: First,

text: suppose

text: that

text: there

text: is

text: a

text: minimal

text: successful

text: support

text: bribery

text: t

text: of

text: cost

text: at

text: most

text: B.

text: Observe

text: that

text: lowering

text: the

text: approval

text: counts

text: in

text: any

text: of

text: the

text: votes

text: q

text: succB(q)

text: in

text: order

text: to

text: decrease

text: q’s

text: score

text: would

text: have

text: a

text: cost

text: of

text: B

text: Thus,

text: t

text: cannot

text: decrease

text: q’s

text: score,

text: and

text: hence

text: it

text: must

text: increase

text: p’s

text: score

text: by

text: at

text: least

text: k

text: points.

text: Since

text: p

text: is

text: preceded

text: by

text: B

text: dummies

text: in

text: it

text: follows

text: that

text: in

text: t

text: the

text: bribed

text: voters

text: form

text: a

text: subset

text: of

text: WV.


text: Proof. For of each of SP-AV, simpliﬁed Fallback voting, and Fallback voting, we use the same strategy and compute certain functions deﬁned below using dynamic programming. { } Let E = (C, V ) be an election, where C = d, c , . . . , c − and V = (v1, . . . , vn) is a 1 (cid:31) m 1 collection of voters (each voter vi has preference order i and approval count (cid:96)i). We are also given support bribery cost functions Σ = (σ1, . . . , σn) for all voters. The outline of our algorithm, same for each of our voting rules, is as follows: ∈ \ { } 1. For each candidate c C d compute the lowest cost of ensuring that c prevents d from being a winner. 2. Output the minimum of the costs computed in the previous step. Naturally, the exact meaning of “c prevents d from being a winner” is diﬀerent for each of our voting rules. For SP-AV it means that (a) c has more approvals in total than d has. For (cid:48) simpliﬁed Fallback voting it means that either (a ) c has more approvals in total than d and d does not win in any round, or (b) c wins in some round t and d does not win in round (cid:48) (cid:48) t. In case of Fallback voting, we need either (a ) or (b ) c wins in some round t, d does not − win in round t 1, and c has more t-approval points than d. ∈ \ { } Let us ﬁx a candidate c C d . To describe algorithms computing a lowest-cost { } support bribery for each of the above conditions, for each k, i, j in 0, . . . , n and for each t { } in 1, . . . , m we deﬁne f (k, i, j) to be the cost of a minimum-cost support bribery ensuring t { } that exactly i voters in V = v1, . . . , vk approve c and rank her in top t positions and k exactly j voters in V approve d and rank her in top t positions. It is easy to verify that k for each t and each k, i, j in this range we can easily compute f (k, i, j) in polynomial time t using standard dynamic programming techniques. (cid:4) (cid:5) Now, it is easy to see that the lowest cost of ensuring that c has more approvals than d { | } (condition (a)) is exactly min f (n, i, j) i > j . Similarly, the minimum cost of ensuring (cid:48) {m | } that condition (a ) holds is min f (n, i, j) i > j, j < n + 1 . The lowest cost of ensuring m 2 that either c wins in(cid:110)an earlier roun(cid:106)d t(cid:107)han d or (cid:106)c w(cid:107)ins in some rou(cid:111)nd but d does not (condition (b)) is | ≥ n n ≤ ≤ min f (n, i, j) i + 1, j < + 1, 1 t m . t 2 2 To deal with the case of classic Fallback voting and compute the lowest cost of ensuring (cid:48) condition (b ), we have to modify our family of functions f a little. For each k, i, j, r { } { } (cid:48) t in 0, . . . , n and each t in 1, . . . , m , let f (k, i, j, r) be the cost of a lowest-cost support t { } bribery ensuring that exactly i voters in V = v1, . . . , vk approve c and rank her in top k t positions, exactly j voters in V approve d and rank her in top t positions, and exactly k − (cid:48) r voters in V approve d and rank her in top t 1 positions. Clearly, each function f is k t computable in polynomial time using standard dynamic programming techniques. Using these functions, we can compute the lowest cost of making c win in some round where she has more approval(cid:110)s than d does, whi(cid:106)le a(cid:107)lso making sure(cid:106)tha(cid:107)t d does not win(cid:111)in the previous (cid:48) round (condition (b )): (cid:48) | ≥ n n ≤ ≤ min f (n, i, j, r) i + 1, i > j, r < + 1, 1 t m . t 2 2 33 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Proof.

label: paragraph

text: For

text: of

text: each

text: of

text: SP-AV,

text: simpliﬁed

text: Fallback

text: voting,

text: and

text: Fallback

text: voting,

text: we

text: use

text: the

text: same

text: strategy

text: and

text: compute

text: certain

text: functions

text: deﬁned

text: below

text: using

text: dynamic

text: programming.

text: Let

text: E

text: (C,

text: V

text: be

text: an

text: election,

text: where

text: C

text: d,

text: c

text: c

text: and

text: V

text: vn)

text: is

text: a

text: m

text: collection

text: of

text: voters

text: (each

text: voter

text: vi

text: has

text: preference

text: order

text: i

text: and

text: approval

text: count

text: We

text: are

text: also

text: given

text: support

text: bribery

text: cost

text: functions

text: Σ

text: σn)

text: for

text: all

text: voters.

text: The

text: outline

text: of

text: our

text: algorithm,

text: same

text: for

text: each

text: of

text: our

text: voting

text: rules,

text: is

text: as

text: follows:

text: For

text: each

text: candidate

text: c

text: C

text: d

text: compute

text: the

text: lowest

text: cost

text: of

text: ensuring

text: that

text: c

text: prevents

text: d

text: from

text: being

text: a

text: winner.

text: Output

text: the

text: minimum

text: of

text: the

text: costs

text: computed

text: in

text: the

text: previous

text: step.

text: Naturally,

text: the

text: exact

text: meaning

text: of

text: “c

text: prevents

text: d

text: from

text: being

text: a

text: winner”

text: is

text: diﬀerent

text: for

text: each

text: of

text: our

text: voting

text: rules.

text: For

text: SP-AV

text: it

text: means

text: that

text: (a)

text: c

text: has

text: more

text: approvals

text: in

text: total

text: than

text: d

text: has.

text: For

text: simpliﬁed

text: Fallback

text: voting

text: it

text: means

text: that

text: either

text: (a

text: c

text: has

text: more

text: approvals

text: in

text: total

text: than

text: d

text: and

text: d

text: does

text: not

text: win

text: in

text: any

text: round,

text: or

text: (b)

text: c

text: wins

text: in

text: some

text: round

text: t

text: and

text: d

text: does

text: not

text: win

text: in

text: round

text: t.

text: In

text: case

text: of

text: Fallback

text: voting,

text: we

text: need

text: either

text: (a

text: or

text: (b

text: c

text: wins

text: in

text: some

text: round

text: t,

text: d

text: does

text: not

text: win

text: in

text: round

text: t

text: and

text: c

text: has

text: more

text: t-approval

text: points

text: than

text: d.

text: Let

text: us

text: ﬁx

text: a

text: candidate

text: c

text: C

text: d

text: To

text: describe

text: algorithms

text: computing

text: a

text: lowest-cost

text: support

text: bribery

text: for

text: each

text: of

text: the

text: above

text: conditions,

text: for

text: each

text: k,

text: i,

text: j

text: in

text: n

text: and

text: for

text: each

text: t

text: in

text: m

text: we

text: deﬁne

text: f

text: (k,

text: i,

text: j)

text: to

text: be

text: the

text: cost

text: of

text: a

text: minimum-cost

text: support

text: bribery

text: ensuring

text: t

text: that

text: exactly

text: i

text: voters

text: in

text: V

text: vk

text: approve

text: c

text: and

text: rank

text: her

text: in

text: top

text: t

text: positions

text: and

text: k

text: exactly

text: j

text: voters

text: in

text: V

text: approve

text: d

text: and

text: rank

text: her

text: in

text: top

text: t

text: positions.

text: It

text: is

text: easy

text: to

text: verify

text: that

text: k

text: for

text: each

text: t

text: and

text: each

text: k,

text: i,

text: j

text: in

text: this

text: range

text: we

text: can

text: easily

text: compute

text: f

text: (k,

text: i,

text: j)

text: in

text: polynomial

text: time

text: t

text: using

text: standard

text: dynamic

text: programming

text: techniques.

text: Now,

text: it

text: is

text: easy

text: to

text: see

text: that

text: the

text: lowest

text: cost

text: of

text: ensuring

text: that

text: c

text: has

text: more

text: approvals

text: than

text: d

text: (condition

text: (a))

text: is

text: exactly

text: min

text: f

text: (n,

text: i,

text: j)

text: i

text: j

text: Similarly,

text: the

text: minimum

text: cost

text: of

text: ensuring

text: {m

text: that

text: condition

text: (a

text: holds

text: is

text: min

text: f

text: (n,

text: i,

text: j)

text: i

text: j,

text: j

text: n

text: The

text: lowest

text: cost

text: of

text: ensuring

text: m

text: that

text: either

text: c

text: wins

text: earlier

text: d

text: or

text: in

text: some

text: but

text: d

text: does

text: not

text: (condition

text: (b))

text: is

text: n

text: n

text: min

text: f

text: (n,

text: i,

text: j)

text: i

text: j

text: t

text: m

text: t

text: To

text: deal

text: with

text: the

text: case

text: of

text: classic

text: Fallback

text: voting

text: and

text: compute

text: the

text: lowest

text: cost

text: of

text: ensuring

text: condition

text: (b

text: we

text: have

text: to

text: modify

text: our

text: family

text: of

text: functions

text: f

text: a

text: little.

text: For

text: each

text: k,

text: i,

text: j,

text: r

text: t

text: in

text: n

text: and

text: each

text: t

text: in

text: m

text: let

text: f

text: (k,

text: i,

text: j,

text: r)

text: be

text: the

text: cost

text: of

text: a

text: lowest-cost

text: support

text: t

text: bribery

text: ensuring

text: that

text: exactly

text: i

text: voters

text: in

text: V

text: vk

text: approve

text: c

text: and

text: rank

text: her

text: in

text: top

text: k

text: t

text: positions,

text: exactly

text: j

text: voters

text: in

text: V

text: approve

text: d

text: and

text: rank

text: her

text: in

text: top

text: t

text: positions,

text: and

text: exactly

text: k

text: r

text: voters

text: in

text: V

text: approve

text: d

text: and

text: rank

text: her

text: in

text: top

text: t

text: positions.

text: Clearly,

text: each

text: function

text: f

text: is

text: k

text: t

text: computable

text: in

text: polynomial

text: time

text: using

text: standard

text: dynamic

text: programming

text: techniques.

text: Using

text: these

text: functions,

text: we

text: can

text: compute

text: the

text: lowest

text: cost

text: of

text: making

text: c

text: win

text: in

text: some

text: round

text: where

text: she

text: has

text: more

text: than

text: d

text: does,

text: making

text: d

text: does

text: not

text: the

text: previous

text: round

text: (condition

text: (b

text: n

text: n

text: min

text: f

text: (n,

text: i,

text: j,

text: r)

text: i

text: i

text: j,

text: r

text: t

text: m

text: t

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: ﬁrst h voters in A to shift p into position k. Similarly, we can compute b(c, i, j, 0) for all ≤ ≤ ≤ | | c 0 i j B by bribing the ﬁrst i voters in B to shift p into position k + 1. For all the c  c remaining cases, we computeb(c, i, j, h) using the following formula: − − −  b(c, i 1, j 1, h) + πj(rank(p, vj) (k + 1)), − − − − b(c, i, j, h) = min b(c, i 1, j 1, h 1) + πj(rank(p, vj) k), (1) − b(c, i, j 1, h). The ﬁrst two lines of this formula correspond to the cases where the j-th voter in B c is bribed to shift candidate p into positions k + 1 and k, respectively. The third line deals with the case where this voter is not bribed. It is immediate that this method correctly | | computes the desired values. By deﬁnition, we have b(c, i) = b(c, i, B , n(c)). For each ∈ \ { } | | c candidate c C p and each i = 0, . . . , B , we deﬁne r(c, i) to be the shift action c (cid:83) corresponding to the value b(c, i); this shift action can be extracted from the dynamic programming computation of b(c, i) using standard techniques. \ Let V = V ∈ \ V ; the set V consists of all voters who rank p in top k positions. Note p c C p c p − that in any minimal shift action, voters in V are not bribed. Now, for every j = 1, . . . , m 1 (cid:98) (cid:99) − p and every i = 0, . . . , n + 1 s (p), let β(j, i) be the minimum cost of a shift action 2 ∪k+1 that (i) only involves voters in j V , (ii) ensures that candidates c , . . . , c do not win (cid:96)=1 cj 1 j in round k and (iii) ensures that p’s (k + 1)-Approval score is at least s (p) + i; we ∞ k+1 − set β(j, i) = + if no such shift action exists. The numbers β(j, i), j = 1, . . . , m 1, (cid:98) (cid:99) − (cid:40) i = 0, . . . , n + 1 s (p), can be computed by dynamic programming as follows. We 2 k+1 have b(c , i) for i = 0, . . . , n(c ), 1 1 β(1, i) = ∞ (cid:98) (cid:99) − + for i = n(c ) + 1, . . . , n + 1 s (p). 1 2 k+1 (cid:98) (cid:99) − Further, for every j > 1 and all i = 0, . . . , n + 1 s (p) we have 2 k+1 { − − | } β(j, i) = min β(j 1, i (cid:96)) + b(c , (cid:96)) (cid:96) = 0, . . . , min(i, n(c )) . j j − (cid:98) (cid:99) − By construction, β(m 1, n + 1 s (p)) is the minimum cost of a shift action ensuring 2 k+1 that p wins in round k +1 and no other candidate wins in round k. A shift action r that has − (cid:98) (cid:99) − this cost can be extracted from the dynamic programming computation of β(m 1, n +1 { } 2 s (p)); it is the sum of shift actions r(c , i ) ∈ \ for appropriate values of i , . . . , i − . k+1 j j cj C p 1 m 1 We output the cheaper of s and r. This algorithm clearly runs in polynomial time, and our argument shows that it produces an optimal shift action for I. Theorem 6. Simpliﬁed Fallback-shift bribery is in P. | | Proof. Given an instance I = (C, V, Π, p) of Simpliﬁed Fallback-shift bribery, let m = C | | (cid:31) and n = V . Further, let i be the preference order of voter vi, and let (cid:96)i be her approval count. Set L = max (cid:96)i. i=1,...,n Our algorithm proceeds in two stages. First, it computes a shift action s of minimum cost that (after deleting the non-approved candidates from each voter’s preference list) ensures 9 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: ﬁrst

text: h

text: voters

text: in

text: A

text: to

text: shift

text: p

text: into

text: position

text: k.

text: Similarly,

text: we

text: can

text: compute

text: b(c,

text: i,

text: j,

text: for

text: all

text: c

text: i

text: j

text: B

text: by

text: bribing

text: the

text: ﬁrst

text: i

text: voters

text: in

text: B

text: to

text: shift

text: p

text: into

text: position

text: k

text: For

text: all

text: the

text: c

label: equation

text: c

text: remaining

text: cases,

text: we

text: computeb(c,

text: i,

text: j,

text: h)

text: using

text: the

text: following

text: formula:

text: b(c,

text: i

text: j

text: h)

text: πj(rank(p,

text: vj)

text: (k

text: b(c,

text: i,

text: j,

text: h)

text: min

text: b(c,

text: i

text: j

text: h

text: πj(rank(p,

text: vj)

text: k),

text: b(c,

text: i,

text: j

text: h).

text: The

text: ﬁrst

text: two

text: lines

text: of

text: this

text: formula

text: correspond

text: to

text: the

text: cases

text: where

text: the

text: j-th

text: voter

text: in

text: B

text: c

text: is

text: bribed

text: to

text: shift

text: candidate

text: p

text: into

text: positions

text: k

text: and

text: k,

text: respectively.

text: The

text: third

text: line

text: deals

text: with

text: the

text: case

text: where

text: this

text: voter

text: is

text: not

text: bribed.

text: It

text: is

text: immediate

text: that

text: this

text: method

text: correctly

text: computes

text: the

text: desired

text: values.

text: By

text: deﬁnition,

text: we

text: have

text: b(c,

text: i)

text: b(c,

text: i,

text: B

text: n(c)).

text: For

text: each

text: c

text: candidate

text: c

text: C

text: p

text: and

text: each

text: i

text: B

text: we

text: deﬁne

text: r(c,

text: i)

text: to

text: be

text: the

text: shift

text: action

text: c

text: corresponding

text: to

text: the

text: value

text: b(c,

text: i);

text: this

text: shift

text: action

text: can

text: be

text: extracted

text: from

text: the

text: dynamic

text: programming

text: computation

text: of

text: b(c,

text: i)

text: using

text: standard

text: techniques.

text: Let

text: V

text: V

text: V

text: the

text: set

text: V

text: consists

text: of

text: all

text: voters

text: who

text: rank

text: p

text: in

text: top

text: k

text: positions.

text: Note

text: p

text: c

text: C

text: p

text: c

text: p

text: that

text: in

text: any

text: minimal

text: shift

text: action,

text: voters

text: in

text: V

text: are

text: not

text: bribed.

text: Now,

text: for

text: every

text: j

text: m

text: p

text: and

text: every

text: i

text: n

text: s

text: (p),

text: let

text: β(j,

text: i)

text: be

text: the

text: minimum

text: cost

text: of

text: a

text: shift

text: action

text: that

text: (i)

text: only

text: involves

text: voters

text: in

text: j

text: V

text: (ii)

text: ensures

text: that

text: candidates

text: c

text: c

text: do

text: not

text: win

text: cj

text: j

text: in

text: round

text: k

text: and

text: (iii)

text: ensures

text: that

text: p’s

text: (k

text: score

text: is

text: at

text: least

text: s

text: (p)

text: i;

text: we

text: set

text: β(j,

text: i)

text: if

text: no

text: such

text: shift

text: action

text: exists.

text: The

text: numbers

text: β(j,

text: i),

text: j

text: m

text: i

text: n

text: s

text: (p),

text: can

text: be

text: computed

text: by

text: dynamic

text: programming

text: as

text: follows.

text: We

text: have

text: b(c

text: i)

text: for

text: i

text: n(c

text: i)

text: for

text: i

text: n(c

text: n

text: s

text: (p).

text: Further,

text: for

text: every

text: j

text: and

text: all

text: i

text: n

text: s

text: (p)

text: we

text: have

text: β(j,

text: i)

text: min

text: β(j

text: i

text: b(c

text: min(i,

text: n(c

text: j

text: j

text: By

text: construction,

text: β(m

text: n

text: s

text: (p))

text: is

text: the

text: minimum

text: cost

text: of

text: a

text: shift

text: action

text: ensuring

text: that

text: p

text: wins

text: in

text: round

text: k

text: and

text: no

text: other

text: candidate

text: wins

text: in

text: round

text: k.

text: A

text: shift

text: action

text: r

text: that

text: has

text: this

text: cost

text: can

text: be

text: extracted

text: from

text: the

text: dynamic

text: programming

text: computation

text: of

text: β(m

text: n

text: s

text: (p));

text: it

text: is

text: the

text: sum

text: of

text: shift

text: actions

text: r(c

text: i

text: for

text: appropriate

text: values

text: of

text: i

text: i

text: j

text: j

text: cj

text: C

text: p

text: m

text: We

text: output

text: the

text: cheaper

text: of

text: s

text: and

text: r.

text: This

text: algorithm

text: clearly

text: runs

text: in

text: polynomial

text: time,

text: and

text: our

text: argument

text: shows

text: that

text: it

text: produces

text: an

text: optimal

text: shift

text: action

text: for

text: I.

text: Theorem

text: Simpliﬁed

text: Fallback-shift

text: bribery

text: is

text: in

text: P.

text: Proof.

text: Given

text: an

text: instance

text: I

text: (C,

text: V,

text: Π,

text: p)

text: of

text: Simpliﬁed

text: Fallback-shift

text: bribery,

text: let

text: m

text: C

text: and

text: n

text: V

text: Further,

text: let

text: i

text: be

text: the

text: preference

text: order

text: of

text: voter

text: vi,

text: and

text: let

text: be

text: her

text: approval

text: count.

text: Set

text: L

text: max

text: Our

text: algorithm

text: proceeds

text: in

text: two

text: stages.

text: First,

text: it

text: computes

text: a

text: shift

text: action

text: s

text: of

text: minimum

text: cost

text: that

text: (after

text: deleting

text: the

text: non-approved

text: candidates

text: from

text: each

text: voter’s

text: preference

text: list)

text: ensures

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: I. INTRODUCTION Just like the energy bands of an electron moving in a crystal, Floquet (quasi-energy) bands capture almost all aspects of a periodically driven system with translational symme- try. As shown by recent theoretical and experimental studies [1–26], Floquet bands may possess many intriguing topological phases that are absent in static systems. It is impor- tant to connect Floquet band topology with observables and identify clear signatures of the associated topological phase transitions. To that end one fruitful topic is topologically protected edge states, but the issue of bulk-edge correspondence in driven systems is still under development [12, 13, 22, 23]. Thouless’s adiabatic pumping shares the same topological origin as the 2-dimensional integer quantum Hall eﬀect [27–30]. There the sum of the Chern numbers of all ﬁlled en- ergy bands below the Fermi surface determines the number of pumped charges [27] (though not relevant to this work, we mention that Thouless’s seminal result is also applicable to many-body systems [28]). In non-equilibrium situations such as driven closed systems, there is no longer a Fermi surface to guarantee either ﬁlled or empty Floquet bands. Neverthe- less, an analogous link between Floquet band topology and adiabatic transport was also found in driven systems [9, 24]. Indeed, for a closed system (here we do not consider a system attached to leads as in a traditional transport problem), Thouless’s result may be re-interpreted as the quantized displacement of a band Wannier state over one adiabatic cycle [31], an interpretation fully consistent with the modern polarization theory [32]. In parallel to this, the displacement of the position expectation value of a coherent wavepacket, prepared initially as a Wannier state of one Floquet band, can also be connected with the Floquet-band Chern number [9, 24]. However, this result is still of limited use in detecting topological phase transitions, because the initial-state preparation already needs the full knowledge of a Floquet band (which is often unavailable) and the initial state has yet to be re-prepared when a system parameter changes. This work considers a type of adiabatic dynamics in periodically driven systems for gen- eral initial states. To be as simple as possible our calculations are based on single-particle wavepacket dynamics, though the extension to many non-interacting particles initially oc- cupying many diﬀerent Floquet states can be also done without diﬃculty. One of our motivations is to address more realistic situations, where the dynamics emanates from an 2

text: I.

label: section

text: INTRODUCTION

text: Just

text: like

text: the

text: energy

text: bands

text: of

text: an

text: electron

text: moving

text: in

text: a

text: crystal,

text: Floquet

text: (quasi-energy)

text: bands

text: capture

text: almost

text: all

text: aspects

text: of

text: a

text: periodically

text: driven

text: system

text: with

text: translational

text: symme-

text: try.

text: As

text: shown

text: by

text: recent

text: theoretical

text: and

text: experimental

text: studies

text: Floquet

text: bands

text: may

text: possess

text: many

text: intriguing

text: topological

text: phases

text: that

text: are

text: absent

text: in

text: static

text: systems.

text: It

text: is

text: impor-

text: tant

text: to

text: connect

text: Floquet

text: band

text: topology

text: with

text: observables

text: and

text: identify

text: clear

text: signatures

text: of

text: the

text: associated

text: topological

text: phase

text: transitions.

text: To

text: that

text: end

text: one

text: fruitful

text: topic

text: is

text: topologically

text: protected

text: edge

text: states,

text: but

text: the

text: issue

text: of

text: bulk-edge

text: correspondence

text: in

text: driven

text: systems

text: is

text: still

text: under

text: development

text: Thouless’s

text: adiabatic

text: pumping

text: shares

text: the

text: same

text: topological

text: origin

text: as

text: the

text: integer

text: quantum

text: Hall

text: eﬀect

text: There

text: the

text: sum

text: of

text: the

text: Chern

text: numbers

text: of

text: all

text: ﬁlled

text: en-

text: ergy

text: bands

text: below

text: the

text: Fermi

text: surface

text: determines

text: the

text: number

text: of

text: pumped

text: charges

text: (though

text: not

text: relevant

text: to

text: this

text: work,

text: we

text: mention

text: that

text: Thouless’s

text: seminal

text: result

text: is

text: also

text: applicable

text: to

text: many-body

text: systems

text: In

text: non-equilibrium

text: situations

text: such

text: as

text: driven

text: closed

text: systems,

text: there

text: is

text: no

text: longer

text: a

text: Fermi

text: surface

text: to

text: guarantee

text: either

text: ﬁlled

text: or

text: empty

text: Floquet

text: bands.

text: Neverthe-

text: less,

text: an

text: analogous

text: link

text: between

text: Floquet

text: band

text: topology

text: and

text: adiabatic

text: transport

text: was

text: also

text: found

text: in

text: driven

text: systems

text: Indeed,

text: for

text: a

text: closed

text: system

text: (here

text: we

text: do

text: not

text: consider

text: a

text: system

text: attached

text: to

text: leads

text: as

text: in

text: a

text: traditional

text: transport

text: problem),

text: Thouless’s

text: result

text: may

text: be

text: re-interpreted

text: as

text: the

text: quantized

text: displacement

text: of

text: a

text: band

text: Wannier

text: state

text: over

text: one

text: adiabatic

text: cycle

text: an

text: interpretation

text: fully

text: consistent

text: with

text: the

text: modern

text: polarization

text: theory

text: In

text: parallel

text: to

text: this,

text: the

text: displacement

text: of

text: the

text: position

text: expectation

text: value

text: of

text: a

text: coherent

text: wavepacket,

text: prepared

text: initially

text: as

text: a

text: Wannier

text: state

text: of

text: one

text: Floquet

text: band,

text: can

text: also

text: be

text: connected

text: with

text: the

text: Floquet-band

text: Chern

text: number

text: However,

text: this

text: result

text: is

text: still

text: of

text: limited

text: use

text: in

text: detecting

text: topological

text: phase

text: transitions,

text: because

text: the

text: initial-state

text: preparation

text: already

text: needs

text: the

text: full

text: knowledge

text: of

text: a

text: Floquet

text: band

text: (which

text: is

text: often

text: unavailable)

text: and

text: the

text: initial

text: state

text: has

text: yet

text: to

text: be

text: re-prepared

text: when

text: a

text: system

text: parameter

text: changes.

text: This

text: work

text: considers

text: a

text: type

text: of

text: adiabatic

text: dynamics

text: in

text: periodically

text: driven

text: systems

text: for

text: gen-

text: eral

text: initial

text: states.

text: To

text: be

text: as

text: simple

text: as

text: possible

text: our

text: calculations

text: are

text: based

text: on

text: single-particle

text: wavepacket

text: dynamics,

text: though

text: the

text: extension

text: to

text: many

text: non-interacting

text: particles

text: initially

text: oc-

text: cupying

text: many

text: diﬀerent

text: Floquet

text: states

text: can

text: be

text: also

text: done

text: without

text: diﬃculty.

text: One

text: of

text: our

text: motivations

text: is

text: to

text: address

text: more

text: realistic

text: situations,

text: where

text: the

text: dynamics

text: emanates

text: from

text: an


text: (cid:3) (cid:2) x Δ 20 15 10 5 0 5.0 5.1 5.2 5.3 J FIG. 4: Detection of a topological phase transition in CDHM with J = K. The actual wavepacket displacement (empty circles, for T = 2560) agrees with our theory (ﬁlled circles) except for a window around J = 5.15. Triangles are the results excluding the IBC induced correction. ior is expected because there the Floquet bands are almost touching each other, yielding more nonadiabatic eﬀects for a protocol of a ﬁnite duration. We stress that the successful detection of a topological phase transition illustrated here is achieved using a very simple initial state regardless of system parameters. Note also that the sole term of the weighted Berry curvature integral (triangles in Fig. 4) is far away from the actual displacement of the wavepacket center. V. SUMMARY Under one symmetry assumption, a type of adiabatic wavepacket dynamics in a closed and periodically driven system is studied. The associated displacement of wavepacket center over one adiabatic cycle is found to be comprised by two components independent of the duration of an adiabatic protocol. In addition to a weighted integral of the Berry curvature, there is an IBC induced correction. This correction survives in the adiabatic limit, making it an important ingredient in an improved understanding of the quantum adiabatic theorem. The explicit expression of the found correction also indicates that it depends sensitively upon how fast an adiabatic protocol is switched on in the very beginning. If we regard the adiabatic protocol as a result of a very slow driving ﬁeld, then the observation that how an adiabatic protocol is switched on can aﬀect the dynamics over an adiabatic cycle is 11 ##LTFigure## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

font: default

text: x

text: Δ

text: J

text: FIG.

text: Detection

label: caption

text: of

text: a

text: topological

text: phase

text: transition

text: in

text: CDHM

text: with

text: J

text: K.

text: The

text: actual

text: wavepacket

text: displacement

text: (empty

text: circles,

text: for

text: T

text: agrees

text: with

text: our

text: theory

text: (ﬁlled

text: circles)

text: except

text: for

text: a

text: window

text: around

text: J

text: Triangles

text: are

text: the

text: results

text: excluding

text: the

text: IBC

text: induced

text: correction.

text: ior

text: is

text: expected

text: because

text: there

text: the

text: Floquet

text: bands

text: are

text: almost

text: touching

text: each

text: other,

text: yielding

text: more

text: nonadiabatic

text: eﬀects

text: for

text: a

text: protocol

text: of

text: a

text: ﬁnite

text: duration.

text: We

text: stress

text: that

text: the

text: successful

text: detection

text: of

text: a

text: topological

text: phase

text: transition

text: illustrated

text: here

text: is

text: achieved

text: using

text: a

text: very

text: simple

text: initial

text: state

text: regardless

text: of

text: system

text: parameters.

text: Note

text: also

text: that

text: the

text: sole

text: term

text: of

text: the

text: weighted

text: Berry

text: curvature

text: integral

text: (triangles

text: in

text: Fig.

text: is

text: far

text: away

text: from

text: the

text: actual

text: displacement

text: of

text: the

text: wavepacket

text: center.

text: V.

text: SUMMARY

text: Under

text: one

text: symmetry

text: assumption,

text: a

text: type

text: of

text: adiabatic

text: wavepacket

text: dynamics

text: in

text: a

text: closed

text: and

text: periodically

text: driven

text: system

text: is

text: studied.

text: The

text: associated

text: displacement

text: of

text: wavepacket

text: center

text: over

text: one

text: adiabatic

text: cycle

text: is

text: found

text: to

text: be

text: comprised

text: by

text: two

text: components

text: independent

text: of

text: the

text: duration

text: of

text: an

text: adiabatic

text: protocol.

text: In

text: addition

text: to

text: a

text: weighted

text: integral

text: of

text: the

text: Berry

text: curvature,

text: there

text: is

text: an

text: IBC

text: induced

text: correction.

text: This

text: correction

text: survives

text: in

text: the

text: adiabatic

text: limit,

text: making

text: it

text: an

text: important

text: ingredient

text: in

text: an

text: improved

text: understanding

text: of

text: the

text: quantum

text: adiabatic

text: theorem.

text: The

text: explicit

text: expression

text: of

text: the

text: found

text: correction

text: also

text: indicates

text: that

text: it

text: depends

text: sensitively

text: upon

text: how

text: fast

text: an

text: adiabatic

text: protocol

text: is

text: switched

text: on

text: in

text: the

text: very

text: beginning.

text: If

text: we

text: regard

text: the

text: adiabatic

text: protocol

text: as

text: a

text: result

text: of

text: a

text: very

text: slow

text: driving

text: ﬁeld,

text: then

text: the

text: observation

text: that

text: how

text: an

text: adiabatic

text: protocol

text: is

text: switched

text: on

text: can

text: aﬀect

text: the

text: dynamics

text: over

text: an

text: adiabatic

text: cycle

text: is

text: ##LTFigure##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: This is to say, (cid:2) (cid:3) − 1/T − e iΩn,k(s)ds = − − d e iΩn,k(s) . (A6) e iωn,k[β(s+ds)] 1 Via the same reasoning, we have (cid:2) (cid:3) − 1/T − ei[Ωn,k(s) Ωm,k(s)]ds = { − } − d ei[Ωn,k(s) Ωm,k(s)] . (A7) ei ωn,k[β(s+ds)] ωm,k[β(s+ds)] 1 We are now ready to integrate Eq. (A4) by parts via the relation in Eq. (A7). We hence obtain (cid:32) (cid:33) (cid:12) (cid:88) (cid:12) (cid:12) (cid:12) (cid:48) (cid:104) (cid:48) | (cid:48) (cid:105) (cid:12)s(cid:48)=s Cn,k(s) = Cn,k(0) + 1 (cid:88) (cid:90) ei[Ωn,k(s(cid:48))−Ωm,k(s(cid:48))] Cm,k(s−) (cid:32)ψn{,k [β(s (cid:48))]−dds(cid:48) ψm,k(cid:48)[β}(s )] (cid:33) T (cid:54) 1 ei ωn,k[β(s )] ωm,k[β(s )] (cid:48) m=n s =0 (cid:48) (cid:104) (cid:48) | (cid:48) (cid:105) − 1 s ds(cid:48) ei[Ωn,k(s(cid:48))−Ωm,k(s(cid:48))] d(cid:48) Cm,k(s−) ψn{,k [β(s (cid:48))]−dds(cid:48) ψm,k(cid:48)[β}(s )] . T (cid:54) 0 ds 1 ei ωn,k[β(s )] ωm,k[β(s )] m=n (A8) The third term on the right hand side o(cid:32)f Eq. (A8) is at least of order 1/T 2, (cid:33)that is: (cid:90) (cid:88) (cid:48) (cid:104) (cid:48) | (cid:48) (cid:105) − T1(cid:88)(cid:54) (cid:34) 0s ds(cid:48) ei[Ωn,k(s(cid:48))−Ωm,k(s(cid:48))] dds(cid:48) (cid:32)Cm,k(1s−) eψin{,ωkn[,βk[(βs(s(cid:48)))]]−dωdsm(cid:48),ψk[mβ(,sk(cid:48))[]β}(s )] (cid:33)(cid:35) (cid:12)(cid:12)(cid:12) m=n (cid:12) = 1 (cid:90)− ei{[Ωn,k(s(cid:48))−(cid:48) Ω−m,k(s(cid:48))] (cid:48) } d(cid:16)(cid:48) Cm,k(s−(cid:48))(cid:104)ψn{,k [β(s(cid:48)(cid:48))]−|dds(cid:48) ψm(cid:17),k(cid:48)[β}(s(cid:48))](cid:105) (cid:12)s(cid:48)=s T 2 m(cid:54)=n(cid:88)1 ei ωn,k[β(s )] ωm,k[β(s )] ds 1 ei ωn,k[β(s )] ωm,k[β(s)] s(cid:48)=0   (cid:48) (cid:104) (cid:48) | (cid:48) (cid:105) − 1 s ei[Ωn,k(s(cid:48))−Ωm,k(s(cid:48))]d dds(cid:48) C−m,1k−(se{)i{ψωnn,,kk[[ββ((s(cid:48)s(cid:48))−)]−] ωddms(cid:48),ψkm[β,(ks(cid:48)[(cid:48))β]}(}s )] . T 2 (cid:54) 0 1 ei ωn,k[β(s )] ωm,k[β(s )] m=n (A9) Ignoring this term of the order of 1/T 2, we ﬁnd that up to order 1/T , the amplitude on the nth band with quasimomentum k at sc(cid:88)aled time s is given by:(cid:12) (cid:12) 1 (cid:48) (cid:48) s =s Cn,k(s) = Cn,k(0) + T Cm,k(0) [Wnm,k(s )] s(cid:48)=0, (A10) (cid:54) m=n 14 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: This

text: is

text: to

text: say,

text: e

text: iΩn,k(s)ds

text: d

text: e

text: iΩn,k(s)

text: e

text: iωn,k[β(s+ds)]

text: Via

text: the

text: same

text: reasoning,

text: we

text: have

text: ei[Ωn,k(s)

text: Ωm,k(s)]ds

text: d

text: ei[Ωn,k(s)

text: Ωm,k(s)]

text: ei

text: ωn,k[β(s+ds)]

text: ωm,k[β(s+ds)]

text: We

text: are

text: now

text: ready

text: to

text: integrate

text: Eq.

text: by

text: parts

text: via

text: the

text: relation

text: in

text: Eq.

text: We

text: hence

text: obtain

text: Cn,k(s)

text: Cm,k(s−)

text: [β(s

text: T

text: ei

text: ωn,k[β(s

text: ωm,k[β(s

text: m=n

text: s

text: s

text: Cm,k(s−)

text: ψn{,k

text: [β(s

text: T

text: ds

text: ei

text: ωn,k[β(s

text: ωm,k[β(s

text: m=n

text: The

text: third

text: term

text: on

text: the

text: right

text: hand

text: side

text: Eq.

text: is

text: at

text: least

text: of

text: order

text: is:

text: m=n

text: T

text: ei

text: ωn,k[β(s

text: ωm,k[β(s

text: ds

text: ei

text: ωn,k[β(s

text: ωm,k[β(s)]

text: s

text: T

text: ei

text: ωn,k[β(s

text: ωm,k[β(s

text: m=n

text: Ignoring

text: this

text: term

text: of

text: the

text: order

text: of

text: we

text: ﬁnd

text: that

text: up

text: to

text: order

text: the

text: amplitude

text: on

text: the

text: nth

text: band

text: with

text: quasimomentum

text: k

text: at

text: time

text: s

text: is

text: given

text: s

text: =s

text: Cn,k(s)

text: T

text: [Wnm,k(s

text: m=n

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: Technical Report TR-DAIF-2015-1 (Note that out of many temporally overlapping subsequences in a frequent motif Deﬁnition 2.1 identiﬁes those that are most similar to that other non-overlapping instances of the motif.) 3 Spherical Clustering for Discovering Frequent Motifs Clustering time-series subsequences has been studied extensively [3, 4, 5, 6, 15, 18, 20, 22]. In particular Keogh et al. [10] have claimed that subsequence clustering gives meaningless results. One of the causes for this non-intuitive conclusion has been rightly identiﬁed [3, 4] to be the fact that time-series subsequences are highly correlated: Consecutive subsequences in the subsequence-matrix are similar to each other since neighboring values vary slowly in a smooth time-series. Consequently, subsequence clustering results in ‘trivial matches’ [6, 10] that need to be identiﬁed and removed after clusters are found [5]. Further, highly correlated subsequences eﬀectively lie along a long lower dimensional manifold in w-space. As we traverse the length of this manifold, the succes- sive pairs of points (subsequences) we encounter are actually close to each other, which also results in tradi- tional clustering algorithms behaving poorly in segre- gating true frequent motifs that form tighter clusters, as we illustrate in Figure 1. For instance, k-means might identify large diameter clusters K and K sep- 1 2 arated by a boundary, and density-based clustering (such as DBSCAN) often results in elongated clusters such as D and D . In each case pairs of subsequences 1 2 within a cluster are not within a small δ distance of Figure 1: Clustering Techniques each other. So, while the true frequent motifs M and 1 M may get separated into separate clusters, many extraneous points also naturally accumulate in each cluster due to the 2 trivial-match problem, eﬀectively obfuscating the true motifs. Chen also observed the same issue [3, 4]. If on the other hand we use spherical clustering with a hard bound on radius (what we term below as COIN clustering), we tend to ﬁnd bounded clusters such as C and C . Of course, the other, extraneous points are also covered by similar spherical 1 2 clusters, shown with lighter outlines; however, these are usually dropped as insigniﬁcant based on their lower support (i.e., while there are many such spheres, each has but a few elements). Figure 2 shows the result of clustering subsequences using k-means versus one of our COIN techniques and illustrates the above phenomenon. While the mo- tif identiﬁed by COIN shows a tight pat- tern, the corresponding k-means cluster includes many extraneous points. Note that while clustering is performed on the normalized subsequences, the COIN mo- tif’s distinctive shape is visible even in the original sequence (i.e., before mean- shifting), while it is completely obscured by noise when k-means is used. Also, the COIN cluster centroid is indeed a rep- resentative shape for the actual pattern while this is not the case using k-means (as also observed by Keogh et al. in [10] Figure 2: k-means vs spherical COIN clustering, showing time on x-axis, and and Chen in [3, 4]). sensor value on y-axis. Exact values on the axes are not important. Another important point is that tech- niques such as k-means become increasingly ineﬃcient for large k. In our practical application with vehicular sensor data, time-series often contain thousands if not tens of thousands of clusters that need to be discovered, even if only a few hundred are signiﬁcant in terms of support. Thus the number of clusters that need to be sought to ﬁnd tight motifs is large and also varies greatly from sensor to sensor. In such situations techniques such as k-means appear inappropriate, both due to time complexity as well as the diﬃculty in choosing the right value of k eﬃciently. Last but not least, it is important to note that spherical clustering of time-series subsequences can and usually does result in overlaps, i.e., many subsequences end up close to more than one cluster center. This is a natural consequence of the nature (cid:13) Copyright c 2015 Tata Consultancy Services Ltd. 3 Patent # 772 / MUM / 2014, TCS Research ##LTFigure## ##LTFigure## ##LTLine##

text: Technical

text: Report

text: (Note

text: that

text: out

text: of

text: many

text: temporally

text: overlapping

text: subsequences

text: in

text: a

text: frequent

text: motif

text: Deﬁnition

text: identiﬁes

text: those

text: that

text: are

text: most

text: similar

text: to

text: that

text: other

text: non-overlapping

text: instances

text: of

text: the

text: motif.)

text: Spherical

text: Clustering

text: for

text: Discovering

text: Frequent

text: Motifs

text: Clustering

text: time-series

text: subsequences

text: has

text: been

text: studied

text: extensively

text: In

text: particular

text: Keogh

text: et

text: al.

text: have

text: claimed

text: that

text: subsequence

text: clustering

text: gives

text: meaningless

text: results.

text: One

text: of

text: the

text: causes

text: for

text: this

text: non-intuitive

text: conclusion

text: has

text: been

text: rightly

text: identiﬁed

text: to

text: be

text: the

text: fact

text: that

text: time-series

text: subsequences

text: are

text: highly

text: correlated:

text: Consecutive

text: subsequences

text: in

text: the

text: subsequence-matrix

text: are

text: similar

text: to

text: each

text: other

text: since

text: neighboring

text: values

text: vary

text: slowly

text: in

text: a

text: smooth

text: time-series.

text: Consequently,

text: subsequence

text: clustering

text: results

text: in

text: ‘trivial

text: matches’

text: that

text: need

text: to

text: be

text: identiﬁed

text: and

text: removed

text: after

text: clusters

text: are

text: found

text: Further,

text: highly

text: correlated

text: subsequences

text: eﬀectively

text: lie

text: along

text: a

text: long

text: lower

text: dimensional

text: manifold

text: in

text: w-space.

text: As

text: we

text: traverse

text: the

text: length

text: of

text: this

text: manifold,

text: the

text: succes-

text: sive

text: pairs

text: of

text: points

text: (subsequences)

text: we

text: encounter

text: are

text: actually

text: close

text: to

text: each

text: other,

text: which

text: also

text: results

text: in

text: tradi-

text: tional

text: clustering

text: algorithms

text: behaving

text: poorly

text: in

text: segre-

text: gating

text: true

text: frequent

text: motifs

text: that

text: form

text: tighter

text: clusters,

text: as

text: we

text: illustrate

text: in

text: Figure

text: For

text: instance,

text: k-means

text: might

text: identify

text: large

text: diameter

text: clusters

text: K

text: and

text: K

text: sep-

text: arated

text: by

text: a

text: boundary,

text: and

text: density-based

text: clustering

text: (such

text: as

text: DBSCAN)

text: often

text: results

text: in

text: elongated

text: clusters

text: such

text: as

text: D

text: and

text: D

text: In

text: each

text: case

text: pairs

text: of

text: subsequences

text: within

text: a

text: cluster

text: are

text: not

text: within

text: a

text: small

text: δ

text: distance

text: of

text: Figure

text: Clustering

text: Techniques

text: each

text: other.

text: So,

text: while

text: the

text: true

text: frequent

text: motifs

text: M

text: and

text: M

text: may

text: get

text: separated

text: into

text: separate

text: clusters,

text: many

text: extraneous

text: points

text: also

text: naturally

text: accumulate

text: in

text: each

text: cluster

text: due

text: to

text: the

text: trivial-match

text: problem,

text: eﬀectively

text: obfuscating

text: the

text: true

text: motifs.

text: Chen

text: also

text: observed

text: the

text: same

text: issue

text: If

text: on

text: the

text: other

text: hand

text: we

text: use

text: spherical

text: clustering

text: with

text: a

text: hard

text: bound

text: on

text: radius

text: (what

text: we

text: term

text: below

text: as

text: COIN

text: clustering),

text: we

text: tend

text: to

text: ﬁnd

text: bounded

text: clusters

text: such

text: as

text: C

text: and

text: C

text: Of

text: course,

text: the

text: other,

text: extraneous

text: points

text: are

text: also

text: covered

text: by

text: similar

text: spherical

text: clusters,

text: shown

text: with

text: lighter

text: outlines;

text: however,

text: these

text: are

text: usually

text: dropped

text: as

text: insigniﬁcant

text: based

text: on

text: their

text: lower

text: support

text: (i.e.,

text: while

text: there

text: are

text: many

text: such

text: spheres,

text: each

text: has

text: but

text: a

text: few

text: elements).

text: Figure

text: shows

text: the

text: result

text: of

text: clustering

text: subsequences

text: using

text: k-means

text: versus

text: one

text: of

text: our

text: COIN

text: techniques

text: and

text: illustrates

text: the

text: above

text: phenomenon.

text: While

text: the

text: mo-

text: tif

text: identiﬁed

text: by

text: COIN

text: shows

text: a

text: tight

text: pat-

text: tern,

text: the

text: corresponding

text: k-means

text: cluster

text: includes

text: many

text: extraneous

text: points.

text: Note

text: that

text: while

text: clustering

text: is

text: performed

text: on

text: the

text: normalized

text: subsequences,

text: the

text: COIN

text: mo-

text: tif’s

text: distinctive

text: shape

text: is

text: visible

text: even

text: in

text: the

text: original

text: sequence

text: (i.e.,

text: before

text: mean-

text: shifting),

text: while

text: it

text: is

text: completely

text: obscured

text: by

text: noise

text: when

text: k-means

text: is

text: used.

text: Also,

text: the

text: COIN

text: cluster

text: centroid

text: is

text: indeed

text: a

text: rep-

text: resentative

text: shape

text: for

text: the

text: actual

text: pattern

text: while

text: this

text: is

text: not

text: the

text: case

text: using

text: k-means

text: (as

text: also

text: observed

text: by

text: Keogh

text: et

text: al.

text: in

text: Figure

text: k-means

text: vs

text: spherical

text: COIN

text: clustering,

text: showing

text: time

text: on

text: x-axis,

text: and

text: and

text: Chen

text: in

text: sensor

text: value

text: on

text: y-axis.

text: Exact

text: values

text: on

text: the

text: axes

text: are

text: not

text: important.

text: Another

text: important

text: point

text: is

text: that

text: tech-

text: niques

text: such

text: as

text: k-means

text: become

text: increasingly

text: ineﬃcient

text: for

text: large

text: k.

text: In

text: our

text: practical

text: application

text: with

text: vehicular

text: sensor

text: data,

text: time-series

text: often

text: contain

text: thousands

text: if

text: not

text: tens

text: of

text: thousands

text: of

text: clusters

text: that

text: need

text: to

text: be

text: discovered,

text: even

text: if

text: only

text: a

text: few

text: hundred

text: are

text: signiﬁcant

text: in

text: terms

text: of

text: support.

text: Thus

text: the

text: number

text: of

text: clusters

text: that

text: need

text: to

text: be

text: sought

text: to

text: ﬁnd

text: tight

text: motifs

text: is

text: large

text: and

text: also

text: varies

text: greatly

text: from

text: sensor

text: to

text: sensor.

text: In

text: such

text: situations

text: techniques

text: such

text: as

text: k-means

text: appear

text: inappropriate,

text: both

text: due

text: to

text: time

text: complexity

text: as

text: well

text: as

text: the

text: diﬃculty

text: in

text: choosing

text: the

text: right

text: value

text: of

text: k

text: eﬃciently.

text: Last

text: but

text: not

text: least,

text: it

text: is

text: important

text: to

text: note

text: that

text: spherical

text: clustering

text: of

text: time-series

text: subsequences

text: can

text: and

text: usually

text: does

text: result

text: in

text: overlaps,

text: i.e.,

text: many

text: subsequences

text: end

text: up

text: close

text: to

text: more

text: than

text: one

text: cluster

text: center.

text: This

text: is

text: a

text: natural

text: consequence

text: of

text: the

text: nature

text: Copyright

text: c

text: Tata

text: Consultancy

text: Services

text: Ltd.

text: Patent

text: MUM

text: TCS

text: Research

text: ##LTFigure##

text: ##LTFigure##

text: ##LTLine##


text: Technical Report TR-DAIF-2015-1 of the space of time-series subsequences rather than any reﬂection on the clustering technique. The important point is that spherical clustering manages to ﬁnd the true frequent motifs, as we shall demonstrate via experimental results on real-life data, as well as on public datasets where ground truth is known. We have used a well known COIN clustering technique called BIRCH [27] that has been shown to outperform standard clustering techniques on large data sets [2]. As we shall show in Section , using BIRCH is also signiﬁcantly more eﬃcient than techniques such as Epenthesis [18] for discovering frequent time-series motifs. Additionally, we also present another equally eﬃcient COIN clustering technique, based on locality-sensitive hashing that is better amenable for parallel implementation. Finally, even after trivial matches have been removed from each potential true motif discovered as a high-support spherical cluster, it is still possible that a single frequent motif (usually one with rather high support) ﬁnds itself split into multiple spherical clusters: Multiple such spherical clusters capture shifted versions of the true motif. So we ﬁnally detect and remove such duplicates by comparing the starting points of subsequences in pairs of high-support clusters. | | ≤ | | Deﬁnition 3.1 Two clusters of subsequences C , C (where C C ) are deemed to be shifted versions of each other if 1 2 1 2 at-least p% of the subsequences of C1 match trivially with the subsequences of the cluster C . 2 As a result of these multiple steps, viz. subsequence clustering, duplicate elimination and ﬁnally removing trivial matches, we manage to ﬁnd largely unique frequent motifs. At the same time, it is important to note that multiple runs of the same process can result in diﬀerent patterns modulo shifts. So, in terms of the measures described by Keogh et al. in [10], the motifs are non-repeatable, which was also one of the reasons for their being called meaningless. However, the fact is that we are able to ﬁnd true frequent motifs, albeit modulo shifts, does indeed suﬃce for all practical purposes for vehicular sensor data. 4 COIN Clustering We introduce the term COIN clustering to describe techniques that result in spherical clusters that bound the maximum distance between any two members of a single cluster to be less than a ﬁxed cluster diameter, 2R. COIN clustering uses the pictorial analogy of a ‘coin’ to perform clustering (though ‘sphere’ would be more correct), with the radius of the coin being the distance threshold R. Our goal is to ensure that a) the clusters are spherical in shape with bounded diameter, while b) the time-complexity is less than O(n2). According to Deﬁnition 2.1, two time-series subsequences are considered similar if the distance between them is less than δ; so in COIN with threshold R, δ = 2R. As a result, all subsequences within a cluster are guaranteed to be similar in that they are at most 2R apart according to the distance measure used. Note that R can be taken to be a function of the variance of the un-normalized time-series and window length, thus obviating the need to set R as a parameter. However, we shall assume that the entire series is normalized to have zero mean and variance one. Therefore, after normalization we shall take R to be a function of the window length alone, as explained in Section . Further, recall that we use the Euclidean distance measure between subsequences after each is individually normalized to have zero mean. This normalization is required so as to detect multiple occurrences of the same waveform shape, albeit occurring at diﬀerent levels. We shall recover multiple levels within a discovered frequent motif in Section . For the moment we concern ourselves with clustering a set of subsequences Sc obtained from the original series after series normalization (and also re-normalizing subsequences to zero mean before comparing them). Algorithm 1 shows the pseudo-code of a basic COIN Clustering algorithm, which is a variation of 1-NN (1-nearest neighbor) clustering where we compare every point with all the points clustered so far and ﬁnd the nearest point. If the distance from the nearest point is less than a prior threshold bound, the new point joins the cluster of the nearest point, otherwise a new cluster is created. The COIN Algorithm 1 takes coinRadius R, and Sc the set of (normalized) subsequences to be clustered, as input. (The diﬀerence between S and Sc will be made clear in Section .) It picks a point (i.e., subsequence) s from the set Sc, clusters i it, and then picks the next point s , and continues this until all of the points are clustered. To cluster a point s , it needs i+1 i to ﬁnd the target cluster for the point, eﬃciently. For this, it ﬁrst determines a set of clusters that are potentially near this (cid:48) point, such that the target cluster is almost sure to be in this set (line # 9). We call this the Candidate Cluster Set C ; note (cid:48) ⊆ i that C C (clusters found so far). i (cid:48) Next the algorithm compares s with the centroid of every cluster in Candidate cluster set C , and ﬁnds the nearest i i cluster-centroid p (line # 10-16). If the distance between p and the point s is less than R, the point s becomes a member i i i i of this cluster and the centroid is updated, otherwise a new cluster is created for the point s (line # 17-23). i From this description it seems that the properties (a) and (b) as mentioned above, are not completely achieved: The centroid of a cluster is updated every time a point joins the cluster; consequently some of the points in the cluster may ﬁnally end up more than R away from their centroids. (cid:13) Copyright c 2015 Tata Consultancy Services Ltd. 4 Patent # 772 / MUM / 2014, TCS Research ##LTLine##

text: Technical

text: Report

text: of

text: the

text: space

text: of

text: time-series

text: subsequences

text: rather

text: than

text: any

text: reﬂection

text: on

text: the

text: clustering

text: technique.

text: The

text: important

text: point

text: is

text: that

text: spherical

text: clustering

text: manages

text: to

text: ﬁnd

text: the

text: true

text: frequent

text: motifs,

text: as

text: we

text: shall

text: demonstrate

text: via

text: experimental

text: results

text: on

text: real-life

text: data,

text: as

text: well

text: as

text: on

text: public

text: datasets

text: where

text: ground

text: truth

text: is

text: known.

text: We

text: have

text: used

text: a

text: well

text: known

text: COIN

text: clustering

text: technique

text: called

text: BIRCH

text: that

text: has

text: been

text: shown

text: to

text: outperform

text: standard

text: clustering

text: techniques

text: on

text: large

text: data

text: sets

text: As

text: we

text: shall

text: show

text: in

text: Section

text: using

text: BIRCH

text: is

text: also

text: signiﬁcantly

text: more

text: eﬃcient

text: than

text: techniques

text: such

text: as

text: Epenthesis

text: for

text: discovering

text: frequent

text: time-series

text: motifs.

text: Additionally,

text: we

text: also

text: present

text: another

text: equally

text: eﬃcient

text: COIN

text: clustering

text: technique,

text: based

text: on

text: locality-sensitive

text: hashing

text: that

text: is

text: better

text: amenable

text: for

text: parallel

text: implementation.

text: Finally,

text: even

text: after

text: trivial

text: matches

text: have

text: been

text: removed

text: from

text: each

text: potential

text: true

text: motif

text: discovered

text: as

text: a

text: high-support

text: spherical

text: cluster,

text: it

text: is

text: still

text: possible

text: that

text: a

text: single

text: frequent

text: motif

text: (usually

text: one

text: with

text: rather

text: high

text: support)

text: ﬁnds

text: itself

text: split

text: into

text: multiple

text: spherical

text: clusters:

text: Multiple

text: such

text: spherical

text: clusters

text: capture

text: shifted

text: versions

text: of

text: the

text: true

text: motif.

text: So

text: we

text: ﬁnally

text: detect

text: and

text: remove

text: such

text: duplicates

text: by

text: comparing

text: the

text: starting

text: points

text: of

text: subsequences

text: in

text: pairs

text: of

text: high-support

text: clusters.

text: Deﬁnition

text: Two

text: clusters

text: of

text: subsequences

text: C

text: C

text: (where

text: C

text: C

text: are

text: deemed

text: to

text: be

text: shifted

text: versions

text: of

text: each

text: other

text: if

text: at-least

text: p%

text: of

text: the

text: subsequences

text: of

text: match

text: trivially

text: with

text: the

text: subsequences

text: of

text: the

text: cluster

text: C

text: As

text: a

text: result

text: of

text: these

text: multiple

text: steps,

text: viz.

text: subsequence

text: clustering,

text: duplicate

text: elimination

text: and

text: ﬁnally

text: removing

text: trivial

text: matches,

text: we

text: manage

text: to

text: ﬁnd

text: largely

text: unique

text: frequent

text: motifs.

text: At

text: the

text: same

text: time,

text: it

text: is

text: important

text: to

text: note

text: that

text: multiple

text: runs

text: of

text: the

text: same

text: process

text: can

text: result

text: in

text: diﬀerent

text: patterns

text: modulo

text: shifts.

text: So,

text: in

text: terms

text: of

text: the

text: measures

text: described

text: by

text: Keogh

text: et

text: al.

text: in

text: the

text: motifs

text: are

text: non-repeatable,

text: which

text: was

text: also

text: one

text: of

text: the

text: reasons

text: for

text: their

text: being

text: called

text: meaningless.

text: However,

text: the

text: fact

text: is

text: that

text: we

text: are

text: able

text: to

text: ﬁnd

text: true

text: frequent

text: motifs,

text: albeit

text: modulo

text: shifts,

text: does

text: indeed

text: suﬃce

text: for

text: all

text: practical

text: purposes

text: for

text: vehicular

text: sensor

text: data.

text: COIN

text: Clustering

text: We

text: introduce

text: the

text: term

text: COIN

text: clustering

text: to

text: describe

text: techniques

text: that

text: result

text: in

text: spherical

text: clusters

text: that

text: bound

text: the

text: maximum

text: distance

text: between

text: any

text: two

text: members

text: of

text: a

text: single

text: cluster

text: to

text: be

text: less

text: than

text: a

text: ﬁxed

text: cluster

text: diameter,

text: COIN

text: clustering

text: uses

text: the

text: pictorial

text: analogy

text: of

text: a

text: ‘coin’

text: to

text: perform

text: clustering

text: (though

text: ‘sphere’

text: would

text: be

text: more

text: correct),

text: with

text: the

text: radius

text: of

text: the

text: coin

text: being

text: the

text: distance

text: threshold

text: R.

text: Our

text: goal

text: is

text: to

text: ensure

text: that

text: a)

text: the

text: clusters

text: are

text: spherical

text: in

text: shape

text: with

text: bounded

text: diameter,

text: while

text: b)

text: the

text: time-complexity

text: is

text: less

text: than

text: According

text: to

text: Deﬁnition

text: two

text: time-series

text: subsequences

text: are

text: considered

text: similar

text: if

text: the

text: distance

text: between

text: them

text: is

text: less

text: than

text: δ;

text: so

text: in

text: COIN

text: with

text: threshold

text: R,

text: δ

text: As

text: a

text: result,

text: all

text: subsequences

text: within

text: a

text: cluster

text: are

text: guaranteed

text: to

text: be

text: similar

text: in

text: that

text: they

text: are

text: at

text: most

text: apart

text: according

text: to

text: the

text: distance

text: measure

text: used.

text: Note

text: that

text: R

text: can

text: be

text: taken

text: to

text: be

text: a

text: function

text: of

text: the

text: variance

text: of

text: the

text: un-normalized

text: time-series

text: and

text: window

text: length,

text: thus

text: obviating

text: the

text: need

text: to

text: set

text: R

text: as

text: a

text: parameter.

text: However,

text: we

text: shall

text: assume

text: that

text: the

text: entire

text: series

text: is

text: normalized

text: to

text: have

text: zero

text: mean

text: and

text: variance

text: one.

text: Therefore,

text: after

text: normalization

text: we

text: shall

text: take

text: R

text: to

text: be

text: a

text: function

text: of

text: the

text: window

text: length

text: alone,

text: as

text: explained

text: in

text: Section

text: Further,

text: recall

text: that

text: we

text: use

text: the

text: Euclidean

text: distance

text: measure

text: between

text: subsequences

text: after

text: each

text: is

text: individually

text: normalized

text: to

text: have

text: zero

text: mean.

text: This

text: normalization

text: is

text: required

text: so

text: as

text: to

text: detect

text: multiple

text: occurrences

text: of

text: the

text: same

text: waveform

text: shape,

text: albeit

text: occurring

text: at

text: diﬀerent

text: levels.

text: We

text: shall

text: recover

text: multiple

text: levels

text: within

text: a

text: discovered

text: frequent

text: motif

text: in

text: Section

text: For

text: the

text: moment

text: we

text: concern

text: ourselves

text: with

text: clustering

text: a

text: set

text: of

text: subsequences

text: Sc

text: obtained

text: from

text: the

text: original

text: series

text: after

text: series

text: normalization

text: (and

text: also

text: re-normalizing

text: subsequences

text: to

text: zero

text: mean

text: before

text: comparing

text: them).

text: Algorithm

text: shows

text: the

text: pseudo-code

text: of

text: a

text: basic

text: COIN

text: Clustering

text: algorithm,

text: which

text: is

text: a

text: variation

text: of

text: neighbor)

text: clustering

text: where

text: we

text: compare

text: every

text: point

text: with

text: all

text: the

text: points

text: clustered

text: so

text: far

text: and

text: ﬁnd

text: the

text: nearest

text: point.

text: If

text: the

text: distance

text: from

text: the

text: nearest

text: point

text: is

text: less

text: than

text: a

text: prior

text: threshold

text: bound,

text: the

text: new

text: point

text: joins

text: the

text: cluster

text: of

text: the

text: nearest

text: point,

text: otherwise

text: a

text: new

text: cluster

text: is

text: created.

text: The

text: COIN

text: Algorithm

text: takes

text: coinRadius

text: R,

text: and

text: Sc

text: the

text: set

text: of

text: (normalized)

text: subsequences

text: to

text: be

text: clustered,

text: as

text: input.

text: (The

text: diﬀerence

text: between

text: S

text: and

text: Sc

text: will

text: be

text: made

text: clear

text: in

text: Section

text: It

text: picks

text: a

text: point

text: (i.e.,

text: subsequence)

text: s

text: from

text: the

text: set

text: Sc,

text: clusters

text: i

text: it,

text: and

text: then

text: picks

text: the

text: next

text: point

text: s

text: and

text: continues

text: this

text: until

text: all

text: of

text: the

text: points

text: are

text: clustered.

text: To

text: cluster

text: a

text: point

text: s

text: it

text: needs

text: i

text: to

text: ﬁnd

text: the

text: target

text: cluster

text: for

text: the

text: point,

text: eﬃciently.

text: For

text: this,

text: it

text: ﬁrst

text: determines

text: a

text: set

text: of

text: clusters

text: that

text: are

text: potentially

text: near

text: this

text: point,

text: such

text: that

text: the

text: target

text: cluster

text: is

text: almost

text: sure

text: to

text: be

text: in

text: this

text: set

text: (line

text: We

text: call

text: this

text: the

text: Candidate

text: Cluster

text: Set

text: C

text: note

text: i

text: that

text: C

text: C

text: (clusters

text: found

text: so

text: far).

text: i

text: Next

text: the

text: algorithm

text: compares

text: s

text: with

text: the

text: centroid

text: of

text: every

text: cluster

text: in

text: Candidate

text: cluster

text: set

text: C

text: and

text: ﬁnds

text: the

text: nearest

text: i

text: i

text: cluster-centroid

text: p

text: (line

text: If

text: the

text: distance

text: between

text: p

text: and

text: the

text: point

text: s

text: is

text: less

text: than

text: R,

text: the

text: point

text: s

text: becomes

text: a

text: member

text: i

text: i

text: i

text: i

text: of

text: this

text: cluster

text: and

text: the

text: centroid

text: is

text: updated,

text: otherwise

text: a

text: new

text: cluster

text: is

text: created

text: for

text: the

text: point

text: s

text: (line

text: i

text: From

text: this

text: description

text: it

text: seems

text: that

text: the

text: properties

text: (a)

text: and

text: (b)

text: as

text: mentioned

text: above,

text: are

text: not

text: completely

text: achieved:

text: The

text: centroid

text: of

text: a

text: cluster

text: is

text: updated

text: every

text: time

text: a

text: point

text: joins

text: the

text: cluster;

text: consequently

text: some

text: of

text: the

text: points

text: in

text: the

text: cluster

text: may

text: ﬁnally

text: end

text: up

text: more

text: than

text: R

text: away

text: from

text: their

text: centroids.

text: Copyright

text: c

text: Tata

text: Consultancy

text: Services

text: Ltd.

text: Patent

text: MUM

text: TCS

text: Research

text: ##LTLine##


text: 6.3 Results Technical Report TR-DAIF-2015-1 Figure 7: Motifs on public datasets, pictures marked by “Epenthesis” taken from [18, 19] ≈ × of our subsequence matrix was 650k 20. After piecewise averaging, the dimension was reduced to d = 10, i.e., the matrix ≈ × size 650k 10. The size of the candidate subsequence matrix Sc obtained after pre-processing(F1-F5) varied from almost 600 to 170k, for diﬀerent sensors, since some subsequences are removed either because they show little deviation or represent trivial-matches. The number of clusters found varied from almost 350 to 170k. However, only 0 to 400 of these clusters pass the minimum- ∼ support condition. Further, on an average 25% of the clusters were dropped when we removed shifted versions of the clusters, ∼ and we obtained about 1 to 250 clusters. Next, during the removal of trivial subsequences, 17% of the subsequences got dropped. Figure 6 shows the running time of COIN-BIRCH as well as the Epenthesis algorithm for time-series of diﬀerent lengths. As evident from the plot on the left, COIN-BIRCH is signiﬁcantly more eﬃcient than Epenthesis, which iteratively ﬁnds pair-motifs to create clusters instead of subsequence clustering. Further, the plot on the right of Figure 6 shows that COIN- BIRCH works eﬃciently even as the number of subsequences grows well beyond the capacity of techniques such as Epenthesis, as was the case for our vehicular sensor data. Motifs discovered from our sample vehicle sensor data, which has been shared at [1], are shown in Figure 8. We also tested our algorithm on public datasets, e.g., Electrocardiogram(ECG), BirdCalls, and Temperature datasets [19]. These experiments took less than 2 sec to run, and some of the motifs discovered on these datasets are shown in Figure 7, demonstrating that our techniques discover the same motifs as Epenthesis [18] on public datasets. On BirdCalls data our algorithm also discovers the similar motifs as done by Epenthesis. Note that while COIN-LSH did discover the heart-beats in the ECG data, it missed some of the instances of the motifs and the COIN-BIRCH did ﬁnd all of the instances of the motif. Further, on Temperature data for motif width 80, we used a COIN radius R = 2. COIN-BIRCH in this case also found all the motifs as discovered by Epenthesis, while COIN-LSH found 6 more motifs for window length of w = 14. All of these actually are the real motifs according to our deﬁnition, 3 of these are shown below the Epenthesis image on the right hand side in Figure 7. Results on other public datasets are also very similar and can be veriﬁed through our code available at [1]. In COIN-LSH we used r = 3 and b = 5. We found both COIN-BIRCH and COIN-LSH give similar performance, although COIN-BIRCH was usually faster (of course COIN-LSH is more amenable to parallel implementation, as mentioned earlier). The above experiments were also tried for diﬀerent window lengths and random order of clustering of subsequences in Sc, (cid:13) Copyright c 2015 Tata Consultancy Services Ltd. 9 Patent # 772 / MUM / 2014, TCS Research ##LTFigure## ##LTLine##

text: Results

text: Technical

text: Report

text: Figure

text: Motifs

text: on

text: public

text: datasets,

text: pictures

text: marked

text: by

text: “Epenthesis”

text: taken

text: from

text: of

text: our

text: subsequence

text: matrix

text: was

text: After

text: piecewise

text: averaging,

text: the

text: dimension

text: was

text: reduced

text: to

text: d

text: i.e.,

text: the

text: matrix

text: size

text: The

text: size

text: of

text: the

text: candidate

text: subsequence

text: matrix

text: Sc

text: obtained

text: after

text: varied

text: from

text: almost

text: to

text: for

text: diﬀerent

text: sensors,

text: since

text: some

text: subsequences

text: are

text: removed

text: either

text: because

text: they

text: show

text: little

text: deviation

text: or

text: represent

text: trivial-matches.

text: The

text: number

text: of

text: clusters

text: found

text: varied

text: from

text: almost

text: to

text: However,

text: only

text: to

text: of

text: these

text: clusters

text: pass

text: the

text: minimum-

text: support

text: condition.

text: Further,

text: on

text: an

text: average

text: of

text: the

text: clusters

text: were

text: dropped

text: when

text: we

text: removed

text: shifted

text: versions

text: of

text: the

text: clusters,

text: and

text: we

text: obtained

text: about

text: to

text: clusters.

text: Next,

text: during

text: the

text: removal

text: of

text: trivial

text: subsequences,

text: of

text: the

text: subsequences

text: got

text: dropped.

text: Figure

text: shows

text: the

text: running

text: time

text: of

text: COIN-BIRCH

text: as

text: well

text: as

text: the

text: Epenthesis

text: algorithm

text: for

text: time-series

text: of

text: diﬀerent

text: lengths.

text: As

text: evident

text: from

text: the

text: plot

text: on

text: the

text: left,

text: COIN-BIRCH

text: is

text: signiﬁcantly

text: more

text: eﬃcient

text: than

text: Epenthesis,

text: which

text: iteratively

text: ﬁnds

text: pair-motifs

text: to

text: create

text: clusters

text: instead

text: of

text: subsequence

text: clustering.

text: Further,

text: the

text: plot

text: on

text: the

text: right

text: of

text: Figure

text: shows

text: that

text: COIN-

text: BIRCH

text: works

text: eﬃciently

text: even

text: as

text: the

text: number

text: of

text: subsequences

text: grows

text: well

text: beyond

text: the

text: capacity

text: of

text: techniques

text: such

text: as

text: Epenthesis,

text: as

text: was

text: the

text: case

text: for

text: our

text: vehicular

text: sensor

text: data.

text: Motifs

text: discovered

text: from

text: our

text: sample

text: vehicle

text: sensor

text: data,

text: which

text: has

text: been

text: shared

text: at

text: are

text: shown

text: in

text: Figure

text: We

text: also

text: tested

text: our

text: algorithm

text: on

text: public

text: datasets,

text: e.g.,

text: Electrocardiogram(ECG),

text: BirdCalls,

text: and

text: Temperature

text: datasets

text: These

text: experiments

text: took

text: less

text: than

text: sec

text: to

text: run,

text: and

text: some

text: of

text: the

text: motifs

text: discovered

text: on

text: these

text: datasets

text: are

text: shown

text: in

text: Figure

text: demonstrating

text: that

text: our

text: techniques

text: discover

text: the

text: same

text: motifs

text: as

text: Epenthesis

text: on

text: public

text: datasets.

text: On

text: BirdCalls

text: data

text: our

text: algorithm

text: also

text: discovers

text: the

text: similar

text: motifs

text: as

text: done

text: by

text: Epenthesis.

text: Note

text: that

text: while

text: COIN-LSH

text: did

text: discover

text: the

text: heart-beats

text: in

text: the

text: ECG

text: data,

text: it

text: missed

text: some

text: of

text: the

text: instances

text: of

text: the

text: motifs

text: and

text: the

text: COIN-BIRCH

text: did

text: ﬁnd

text: all

text: of

text: the

text: instances

text: of

text: the

text: motif.

text: Further,

text: on

text: Temperature

text: data

text: for

text: motif

text: width

text: we

text: used

text: a

text: COIN

text: radius

text: R

text: COIN-BIRCH

text: in

text: this

text: case

text: also

text: found

text: all

text: the

text: motifs

text: as

text: discovered

text: by

text: Epenthesis,

text: while

text: COIN-LSH

text: found

text: more

text: motifs

text: for

text: window

text: length

text: of

text: w

text: All

text: of

text: these

text: actually

text: are

text: the

text: real

text: motifs

text: according

text: to

text: our

text: deﬁnition,

text: of

text: these

text: are

text: shown

text: below

text: the

text: Epenthesis

text: image

text: on

text: the

text: right

text: hand

text: side

text: in

text: Figure

text: Results

text: on

text: other

text: public

text: datasets

text: are

text: also

text: very

text: similar

text: and

text: can

text: be

text: veriﬁed

text: through

text: our

text: code

text: available

text: at

text: In

text: COIN-LSH

text: we

text: used

text: r

text: and

text: b

text: We

text: found

text: both

text: COIN-BIRCH

text: and

text: COIN-LSH

text: give

text: similar

text: performance,

text: although

text: COIN-BIRCH

text: was

text: usually

text: faster

text: (of

text: course

text: COIN-LSH

text: is

text: more

text: amenable

text: to

text: parallel

text: implementation,

text: as

text: mentioned

text: earlier).

text: The

text: above

text: experiments

text: were

text: also

text: tried

text: for

text: diﬀerent

text: window

text: lengths

text: and

text: random

text: order

text: of

text: clustering

text: of

text: subsequences

text: in

text: Sc,

text: Copyright

text: c

text: Tata

text: Consultancy

text: Services

text: Ltd.

text: Patent

text: MUM

text: TCS

text: Research

text: ##LTFigure##

text: ##LTLine##