Big Data Computing

184 Big Data Computing

where C is a hypercube resulting from a space tiling and

ω

∈ Ω. Figure 5.4

shows an example of such indices for p = 2 with

α

= 2 (Figure 5.4a) and

α

= 4

(Figure 5.4b).

Note that the highlighted square with index 0 contains the reference point

ω

. Also note that our indexing scheme is symmetric with respect to C(

ω

).

Thus, it is sufcient to prove the subsequent lemmas for hypercubes C such

that c

i

> c(

ω

)

i

. In Figure 5.4, it is the upper right portion of the indexed space

with the gray background. Finally, note that the maximal index that a hyper-

cube can achieve is n(

α

− 1)

p

as max|c

i

− c

i

(

ω

)| =

α

per construction of H(

ω

,

θ

).

The indexing scheme proposed above guarantees the following:

Lemma 1

Index C x s C t C s t x

p p

(