Extra Space during Initialization of Succinct Data Structures and Dynamical Initializable Arrays
Frank Kammer Andrej Sajenko




On shrinking horizon move-blocking predictive control
    Hafsa Farooqi, Lorenzo Fagiano, Patrizio ColaneriThe authors are with the Dipartimento di Elettronica, Informazione e Bioingegneria, Politecnico di Milano, Milano, Italy. E-mail addresses:
			{hafsa.farooqi| lorenzo.fagiano|lorenzo.fagiano| }@polimi.it 
    
=================================================================================================================================================================================================================================================================




  
Many succinct data structures on the word RAM require precomputed tables to
start operating. 
Usually, the tables can be constructed in sublinear time.

In this time, most
of a data structure is not initialized, i.e., there is plenty of
unused space allocated for the data structure.

We present a general framework 
 to store 
temporarily extra buffers between the real data 
so that the data can be processed immediately, stored first in the buffers, 
and then moved into the real data structure after finishing the tables.
As an application, we apply our framework to 
Dodis, Pǎtraşcu, and
               Thorup's
data structure (STOC 2010) that emulates c-ary memory and to 


Farzan and Munro's 
succinct encoding of arbitrary graphs (TCS 2013).


We also use our framework to 


present an
in-place dynamical initializable array.




§ INTRODUCTION

Small mobile devices, embedded systems, and big data 
draw the attention to space- and 
time-efficient 
algorithms,

e.g., for sorting <cit.>, geometry <cit.> 
or graph algorithms
<cit.>.
<cit.>. 
Moreover, there has been also an increased
interest in
succinct (encoding) data
structures <cit.>.

On a word RAM, succinct 
data structures 
often 
require precomputed tables to
start operating, e.g., 
Dodis, Pǎtraşcu, and
               Thorup's
data structure <cit.>. It 
 emulates
c-ary memory, for an arbitrary c≥ 2,
on standard binary memory almost without
losing space. Before we can store any information in the data structure,
suitable lookup tables have to be computed. Hagerup and
Kammer <cit.> showed
a 
solution that
allows us to store the incoming information in an extra buffer and
 read and write values immediately.
However, their solution scrambles the data so that extra mapping tables
have to be built and used forever to access the data, even after the lookup tables are built.


Moreover, Farzan and Munro <cit.> described a succinct
encoding of arbitrary graphs. To store a dense graph, an adjacency matrix
is stored in a compact form by decomposing the matrix in tiny submatrices.
Each submatrix is represented by an index and the mapping is done via a lookup table. 
Assume that the tables 
are not ready, but the information of the graph
already arrives in a stream. One then can use an extra buffer and
store the small matrices
in a non-compact way and operate on these matrices until the tables are
ready. At the end, the data can be moved from the buffers to the real data
structure.

Usually, the tables can be constructed in sublinear time.

In this time, most
of the data structure is not initialized, leaving plenty of
allocated space unused.

We present a general framework to store a
temporarily extra buffer between the real data during a short startup time
and the buffer has the standard access operations of an array.

In particular, 
if the buffer is not needed any more and thus is removed,
our implementation ”leaves” the data structure as 
if the extra buffer has never existed.


As another application of our framework, we show that 
in-place initializable arrays can be made dynamic and with every increase
of the array size, the new space is always 
initialized.


Our model of computation 
is the word RAM model with a word length w 

that allows us to access all input words in O(1) 
time. Thus, to operate on a dynamic initializable array of maximum size 
n_max we require that the word size w = Ω( log n_max).

To obtain a dynamic initializable array, 
we additionally assume that we can expand and shrink an already allocated memory. 
The memory can come from an operating system or can be user controlled,
i.e., the user can shrink an initializable array temporarily, use the space for  
some other purpose, and can increase it
again if it is needed later.







 §.§ Previous Array Implementation

The folklore algorithm <cit.>, which uses 
two arrays with pointers pointing to each other and one array storing
the data, uses O(nw) bits of extra space.
Navarro <cit.> showed an implementation that requires n + o(n) bits
of extra space. Recently, Hagerup and Kammer <cit.> 
showed that ⌈(n(t/(2 
w))^t)⌉ extra bits for an arbitrary constant t suffice 
if one wants to support access to the array in O(t) time. In particular,
by choosing t=O(log n), the extra space is only one bit.
Very recently, Katoh and Goto <cit.> showed that 
also constant access time is possible with 
one extra bit. All these array implementations are designed 
for static array 
sizes.



 §.§ Our Contributions

First, we present our framework to 
extend a data structure by 
an extra buffer.


We then apply the framework to two known algorithms <cit.>.
Finally, we 
make Katoh and Goto's in-place initializable arrays dynamic.
For this purpose, we identify problems that happen 
by a simple increase of the memory used for the array and 
stepwise improve the 
implementation to make the array 
dynamic. 
Our best solution supports 

operations read, write, and increase in 
constant time and an operation shrink in amortized constant time.

Why do we support the shrink operation only in amortized time?  
The rest of this paragraph is not a precise proof, 
but gives some intuition what the problems are 
if the goal is to support 
constant non-amortized time for initialization, writing and shrinking.


To support constant-time initialization of an array
we must have knowledge of the regions 
that are completely written by the user and these regions must store the
information which words are written. 



If we now allow arbitrary shrink operations, then we do not have the space 
to keep all information. Instead, we must clean the information, but keep
this information of the written words that still belong to the dynamic array.
If we want to run the shrink operation in non-amortized constant time, the
information must be sorted in such a way that the cleaning can be done by
simply cutting away a last part of the information. 
This means the writing operation must take care that the information is stored in some sense
“sorted”. Since

we can not sort a stream of elements 
in O(1) time per element in general, 
it seems plausible that 

the writing operation takes ω(1) time.

The remainder of this paper is structured as follows.
We begin with summarizing the important parts of Katoh and Goto's algorithm 


in Section <ref>.
In Section <ref> we present 
our framework

to implement the extra buffer 
stored 
inside the unused space of a data structure 
without using extra space.
In Section <ref>, we extend our framework to 
dynamic arrays.
As an application, 
we show in
Section <ref> how to increase the array size 
in constant 
time.








In Sections <ref> and <ref>, we present the final implementation 
that also allows us to decrease the array size.
Some proofs in Section <ref> are omitted, but can be found in the appendix and
in a full version of the paper <cit.>.



§ IN-PLACE INITIALIZABLE ARRAY

Katoh and Goto <cit.> introduced 
the data structure below 



and gave an implementation that uses nw + 1 bits and supports all operations 

in constant time. 


	An initializable array 𝒟 is a data structure that 
        stores n ∈ elements of the universe Z ⊆
	and provides the following operations: 
	
	
		
  * read(i) (i ∈): Returns the i-th element of 𝒟.
		
  * write(i, x) (i ∈, x ∈ Z): Sets the i-th element of 𝒟 to 
		x.
		
  * init(x) (x ∈ Z): Sets all elements of 𝒟 to initv :=x.
	


Let
D[0,…,n] be an array storing 𝒟. 
D[0] is used only to store one bit 
to check if the array 𝒟 is fully initialized. If D[0] = 1,
𝒟
is a normal array, otherwise the following rules apply.

The idea is to split a standard array into blocks of b = 2 words
and group the blocks into two areas: The blocks before some threshold
 t∈ are in the written area, the remaining in the unwritten
 area. 
Moreover, they call two blocks chained 
if the values of their first words point at each others
position and if they belong to different areas. In the following, we denote by
d(B)
the block chained with a block B. Note that d(d(B)) = B.

In our paper, we also use chains. Therefore, we shortly describe the meaning of a
(un)chained block B in <cit.>. 




Compare the following description with Figure <ref>.
If B is in the written area and chained,
then B is used to store a value of another initialized block and is therefore defined as 
uninitialized. 


If
B is in the unwritten area and chained, 



B contains
user written values and the words of B are divided among B and d(B).
In this case d(B) was not written by the user. 
In detail, the second word of B is stored in this word of B,
 but the first word is stored in the
second word of d(B) since the first word is used to store a pointer.  


If B is in the written area and unchained,
B contains user written (or initial) values. 


If B is in the unwritten area and unchained, 


B has never been

written by the user.

Every time the user writes into a block for the first time, i.e., 
into a word of an (un)chained block in the (un)written area, 

the written area increases by moving the first block of the unwritten area into the
written area and by possibly building or correcting chains.






§ EXTRA SPACE DURING INITIALIZATION OF SUCCINCT DATA STRUCTURES


We now consider an arbitrary data structure 𝒟^*. 
The only assumption that we make is that
𝒟^* accesses the memory via a data structure 𝒟 realizing
an n-word array.
For the time being, assume 𝒟 is the data structure 
as described in Section <ref> with D[0,…,n] being an
 array storing 𝒟.


We define |U| as the number of blocks of the unwritten area.
As long as 𝒟 is not fully initialized, and only m ∈ with m < n words are written in 𝒟, Theorem <ref> shows that 
the unused storage allocated for 
𝒟 allows us to store information of an extra array E inside D by increasing 
the block size to b > 2 (Figure <ref>).
The size of E depends on |U| and thus on the current grade of 
initialization of 𝒟.
In contrast to 𝒟, E is an uninitialized array.
Clearly, we can build an initialized array on top of E.


The array size n is not always a multiple of the block size b.
By decreasing n and handling less than b words of 𝒟
separately, we assume in this paper that n is a multiple of b.




	We can store an extra array E of (n/b - m)(b - 2) ≤ |U|(b - 2) words inside 
	the unused space of 𝒟. E dynamically shrinks from the
 end whenever m increases.

 
        Let us consider a block B inside the unwritten area.


        B and d(B) together provide 
	space for 2b words, but the chain between them exists only because the user wrote inside
	one block (block B, but not in d(B)), and thus we need to store b words
        of user data. 
        
	
        Furthermore, B and d(B) each needs one word to store a pointer that represents 
	the chain. 
        By storing as much user data as possible of B in d(B), we have b - 2
	unused 	words in B—say, words 2 to b-1 are unused. 


        Note that, if a block B is unchained, then it contains no user values
	at all and we have even b unused words.
	If the user wrote m different words in 𝒟, then the threshold t of 𝒟 (t 
	is the number of blocks in the written area) is expanded at most 
	m-times.


        The written area consists of at most m blocks of a total of n / b
	blocks. Consequently, the unwritten area has (n/b - m) ≤ |U| blocks with each having (b - 2) unused 
	words.

If we start to store E[0], E[1], ... in the unwritten area strictly behind t, 
the indices of E will shift 
every time 
the unwritten area 
shrinks.
Therefore, we store E in reverse and E loses with every shrink the last b - 2 words, but get 
static 
indices.




















Note that values like 
the threshold t and the initial value can be easily stored at the beginning of E. 
However, we require the size of 𝒟 to determine the beginning of E.
To store the size we therefore move D[1]
also into E and store the size of the array in D[1].
During the usage of D we have to take this into account, 
but for simplicity we ignore this fact.
If the array is fully initialized and thus D[0] = 1, we can not store the size
anymore, but in this case we do not need to know it.



 §.§ Application: c-ary Memory





To use Dodis et al.'s dictionary <cit.> on n elements, a lookup
table Y with O(log n) entries consisting of O(log n) bits each must
be constructed, which can be done in O(log n) time.  Using tables of the
same kind to store powers of c, we can assume that c=Ω(n) by
combining consecutive elements of the input into one element.

Hagerup and Kammer extended Dodis et al.'s dictionary 
to support constant-time initialization by storing the 
k=Θ(log n)
elements that are added first to the dictionary in a trie D^T 
of constant depth d≥
4 and out degree 
n^1/d using O(n^ϵ+1/d+log n log c) bits for any ϵ>0. Interleaved with
the first k operations on the dictionary, first the table Y is built and afterwards, 
the elements in D^T
are moved to the dictionary.





Since D^T is required only
temporarily, it is stored within the memory allocated for the 
dictionary—say in the last part of the memory.  



The problem that arises is that 
the
last part of the memory can not be used as long as it is still used by D^T. 
This problem is solved by partitioning the memory allocated for the 
dictionary into sectors and using a complicated mapping function that 
scrambles
the elements to avoid the usage of the last part of the memory. Unfortunately,
even after computing the table Y and moving all elements from
D^T over to the dictionary, the data is still scrambled and 
each access to the dictionary has to start evaluating the mapping function.

With Theorem <ref> as an underlying data structure it is
easily possible to implement the dictionary with constant initialization time.



Use
the extra array E to store temporarily the table D^T. 



Even if we use block size b = 3, 
E has enough space (at least (n (log c) - k log n)/3 ≥ (n-k)(log n)/3 
bits at the end of the construction
of Y) to store
D^T. 



The mapping
function becomes superfluous because the data is not scrambled by the usage of 
Theorem <ref>.







Furthermore, working on a copied and slightly modified algorithm after
the full initialization of 𝒟, 
we can avoid checking the extra bit in D[0].




 §.§ Application: Succinct Encoding of Dense Graphs

Farzan and Munro <cit.> showed a succinct
encoding of an n × n-matrix that represents an arbitrary graph with n vertices and m 
edges. 
Knowing the number of edges they distinguish between five cases: 
An almost full case, where the matrix consists of almost only one entries, an extremely dense case, a dense 
case, a 
moderate case and an extremely sparse case. 
For each case, they present a succinct encoding that supports the query 
operations for adjacency and degree in constant time and iteration over neighbors of a 
vertex in constant time per neighbor.

We consider only the dense case where table lookup is used. Dense means that
∃δ > 0 : n^2 / log^1-δ n ≤ m ≤ n^2 (1 - 1/(log^1 -
δ n).  
As shown in <cit.>, a representation in that case requires logn^2  m + 
O(n^2(log^1-δ n)) = 
logn^2  m +
o(logn^2  m) bits of memory. 
To encode the matrix of a graph Farzan and Munro
first divide the matrix into small submatrices of size log^1 - δ
n ×log^1 - δ n for a constant 0 < δ≤ 1.  
For each row and column of
this smaller submatrices they calculate a summary bit that is 1 if the row and column, 
respectively, of the submatrix contains at least one 1.
The summary bits of a row and column, respectively, of the whole matrix is used to create a  summary vector.
On top of each summary vector they build a rank-select data structure <cit.> that supports 
queries on 0's and 1's in constant time.
They also build a lookup table to map between possible submatrices and
indices as well as to answer all queries of interest in the submatrix in O(1) time.
In a further step, they replace each submatrix by its index.




By guaranteeing that the number of possible submatrices is o(log n), the construction of the 
lookup table
can be done in O(n) time.

To simply guarantee this, we restrict δ to be larger than 1/2.
We generalize the result for δ > 1/2 to dynamic
dense graphs by replacing the rank-select data structures with choice
dictionaries <cit.> as follows.

We assume that the graph has initially no edges and that 
there is a stream that consists of edge updates and query operations.

With each edge update, the index of the submatrix with the edge changes.
To realize the index transition we use a translation table that maps 
both, the current index of the
submatrix and the edge update made, to the new index.
We store for each summary vector an edge counter, i.e., the number of 1's that was used 
to calculate each summary bit of it.
Whenever an edge is created between two nodes we set the corresponding bit of the row and column, 
respectively, inside the summary vector to 1 and increment the edge counter.
If an edge is removed we decrement the edge counter and determine, using a lookup table, if the 
submatrix containing this edge has still 1's in the updated row and column, respectively.
If it does not, we set the corresponding summary bit inside the summary vector to 0.

If the lookup tables for the submatrices are computed, we can easily 
answer queries to the current graph similar to <cit.> since we still use the summary vectors.
We can ask for membership to answer adjacency queries. To iterate over 
the 
neighbors of a vertex (i.e., over the 1's in the summary vector), we can use the iterator function of 
the 
choice dictionary 
instead of using the select function of the rank-select data structure.
The degree query is answered by returning the edge counter.

In the rest of this subsection, the goal is to extend the data structure such that it supports the queries 
without a delay for the construction of the lookup tables. The idea is to store a submatrix with a 1 
entry
in the usual, non-compact way in the extra buffer and to add a pointer 
from the submatrix to a place in the buffer
where it is stored.
To reduce the space used for the
pointers, we group log^δ n submatrices together to get a group matrix 
of size log^1 - δ n ×log n.
Moreover, we use an array A in
which we store a pointer of O(log n) bits for each group. 
With the first writing operation to one submatrix in a
group, the group matrix is stored in the usual, non-compact way in 
an initialized array, which is stored in 
the extra
buffer (Theorem <ref>).
In the array A, we update the pointer for the group.
In addition, we build a choice dictionary on top of each 
non-empty column and
each non-empty row of the group matrix. 
With each choice dictionary, we also count the number of 1 entries. 

Using the counts we can update the summary vectors and 





the non-compact submatrix allows us to answer adjacency queries. Both can
be done in constant time without using lookup tables.
To support the neighborhood query, we use choice dictionaries on top of the
group matrices. 



In detail, whenever updating an edge, update the summary vector, add or follow the
pointer to the non-compact representation, update it including the choice dictionary 
and the degree counter.


After O(n) operations the 
lookup table is computed and, in the same time, the entries in the non-compact matrices are
moved to the compact submatrices. 







The array A requires n^2 (log n) /((log^1-δ n)(log n)) = O(n^2/log^1-δ
n) bits, which is negligible.  Moreover, a group matrix with the choice
dictionaries requires O(log^2 n) bits to be stored.  Thus, after
O(n) operations, the total extra space usage is O(n log^2 n) bits, which
easily fits in the extra buffers of size

Ω(logn^2  m  - nlog n) = Ω(n^2/log^1-δ n -  nlog
n) 


bits after O(n) 
operations.


A graph with n vertices can be stored with log_2 nm+O(n^2/log^1-δ n) bits
supporting edge updates as well as adjacency and degree queries
in constant time and iteration over
neighbors of a
vertex in constant time per neighbor where m=n^2/log_2^1-δ n and
δ>1/2. A

startup time for constructing tables is not necessary.


Note that the space bound is succinct if the graph is dense. Moreover, if 
the whole memory of a graph representation must be allocated in the
beginning, i.e., if we
do not allow a change of the space bound during the edge updates, 
then our
representation of the dynamical graph (with possibly n^2/log_2^1-δ
n edges) is also succinct.




§ EXTRA SPACE FOR DYNAMIC ARRAYS

We now extend our framework to dynamic arrays.





Then the unused space inside 𝒟 may grow or shrink and with it the size of
the array E. 

Since we start to index the words belonging to E from the end of 𝒟, 
changing the size of 𝒟 will change the index of the words 
in E.  If we start to index E from the beginning of the unwritten area,
all indices change every time the unwritten area shrinks.


To realize an indexed array we introduce a fixed-length array F.  To handle the
shrink operation, we store F strictly behind the written area so that there
is nothing to do if we shrink or expand the size of 𝒟.  If the
written area grows, we lose b - 2 unused words of the unwritten area and
therefore b - 2 used words in F.  As long as there are unused words in
the unwritten area behind F we move the b-2 words that we would lose to the
first unused words behind F.  This will rotate F inside the unwritten area of D.  





	We can store a fixed-length array F consisting of ℓ words in the unused space of 
	𝒟 
	as long as ℓ≤ (n/b -m - 1)(b - 2) ≤ (|U| - 1)(b-2). If the condition is violated, then F is 
	destroyed.


	Let the size of F be smaller than the unused space of 𝒟.  Whenever the user writes an additional word in 𝒟,
	m increases and the number of the unused words becomes less. 
	Therefore, before extending the written area by one block, we move
	the b - 2 words in that block to the unused space of 𝒟
	behind F.  We use the last block in the unwritten area to store the
	size and a counter to calculate the rotation.  Thus, we have one
	block less in contrast to Theorem <ref>.  F can be of size ℓ≤ (n/b -m - 1)(b - 2) ≤ (|U| - 1)(b-2).


For some applications it is interesting to have a dynamic extra storage even if 𝒟 is dynamic.
We introduce a dynamic set in Lemma <ref> that can be stored inside the 
unwritten area of 𝒟 and supports the operations 
add, remove, and 
iterate. The last operation returns a list of 
all elements in the data structure.
The size of L is dynamically upper bounded by |U|.


	We can store a dynamic (multi-)set of maximal ℓ≤ (|U| - 1)(b - 2) 
        elements
        in the unused space of 
	𝒟. If the condition is violated by 
	write operations of 𝒟, elements of the set are removed
        until the condition holds again.


	We store a dynamic list strictly behind the written area and shift it cyclically 
        as in the proof of 
	Lemma <ref>. The difference here is that 
        we have no fixed order so that we 
        can store new elements simply at the beginning of the 
	unused words of 𝒟 and increase the size ℓ. The
	removal of an element may create 
	a gap that can be filled by moving an element and decreasing ℓ.


For our implementation described in Section <ref> we require a (multi-)set with 
direct access to the elements. 
We can use the position in D as an address for direct access,
but this requires that the user 
implements
a notification function. The function is called by 
our data structure whenever an 
element in the list changes its position to inform the user of the new position of the element.


	Having two chained blocks B and d(B) and a suitable block size b,
	we can rearrange the user data in the two blocks such that we can 
	store O(1) extra words (information as, e.g., pointers) in both B and in d(B).


An algorithm often uses several data
structures in parallel, which all can be stored in the uninitialized space
of 𝒟.





  For a b ≥ 2, 𝒟 can have k∈ extra data structures in parallel
 where each is of size

  at most
  |U|⌊ (b - 2)/k ⌋. 


	Every block of the unwritten area has b - 2 unused words and every unused word can be 
	used for another data structure.


As we see later, it is useful to have several dynamic sets of elements that are all the same
size.  
The sets can also be (multi-)sets.


	For b>2, 𝒟 can store a dynamic family ℱ consisting of 
	dynamic sets where the sets have in total 
        at most ⌊ (|U| - 3)(b - 2)/(s + 3)-1⌋ elements each 
	of size s.


	
	We use the unused words in the unwritten area of 𝒟
	
	
	and 
	partition it into sections of
	s + 3 words.
	Every first word of a section is used for an array I and 
	the last s + 2 words for an array S.
	S is 
	used to store the elements of the sets where the elements of each
	set are connected in   
	a doubly linked list. 
	
	I[i] points to an element of the ith set. 
	The unused words in the last 3 blocks (possibly, fewer blocks suffice) 
        of the unwritten area 
	are used to store some constants: the size t
	of the written area, the initial value of 𝒟, some 
	parameter p∈, the 
	number of sets in 𝒮, and 
	the total number q of items over all sets.
	
	
	
	
	
	
	Using q we can simply find the section of a new element.
	
	If the written area of 𝒟 increases, 
	we have to start moving the first section to a new unused section. We store
	the position of the new section in p. 
	By knowing t we know how much of the first section has been
	already moved and where to find the information of the first section.
	




§ DYNAMICAL INITIALIZABLE ARRAY


In the next three subsections, we provide implementations to make the in-place initializable array 
dynamic. Therefore, we extend the initializable array 𝒟 by the following two functions to 
change the current size of the array.


	
  * increase(n_old, n_new, initv) (n_old, 
	n_new∈): Sets the size of 𝒟 from n_old to 
	n_new.
	All the elements behind the n_oldth element in 𝒟 are initialized with initv,
	the initial value of 𝒟 defined by the last call of init.
	
  * shrink(n_old, n_new) (n_old, n_new∈): Sets the size of 𝒟 from n_old to n_new.


In our implementation we handle the array 𝒟 differently, according to its size.
Recall that w is the word size.
As long as 𝒟 consists of n'=O(w) elements, we use
a bit vector stored in
O(1) words to know which words are initialized.
On the word RAM we can manipulate it in constant time.
To have immediate access to the bit vector we store it 
in the beginning of the array and move the data located there 
to the first unused words.
If we increase the size of 𝒟 
to more than ω(w) elements, we keep the bit vector in some
unused words until the first n' words of
𝒟 are completely initialized. 
Having such a bit vector we assume 
that this is taken into account whenever there is a reading
or writing operation, but do not mention it explicitly in the rest of the paper.


If the array 𝒟 consists of at least ω(w)
elements, we can not use the solution with the bit vector. Instead, 
we use chains 


so that we can distinguish between initialized and
uninitialized blocks, even after several shrink and increase operations. 




We assume in the following that 𝒟 consists of 
ω(w) elements.



 §.§ Increasing the size of 𝒟

An increase of the size of 𝒟 means allocating additional memory that gives us several new blocks inside the unwritten area. 
These blocks may contain arbitrary values and these values can point at each other such that they 
create a so-called unintended chain between a block B_w 
(written area) and a block B_u (unwritten area). 






Katoh and Goto break such unintended chains by creating a self-chain (pointer at its own 
position) with B_u whenever they write a value to a block of the written area.
Because the increase of 𝒟 may be arbitrary, we can not destroy such chains in 
constant time.

To support large increases of 𝒟, we eliminate the possibility of unintended chains by 
introducing 
another 
kind of chain, called verification chain.
To distinguish the two kinds of chains we name the chain introduced in 
Section <ref> a data chain. We define a chain between two 
blocks B_w and B_u as intended exactly if B_w has also a verification
chain, otherwise as
unintended. 

To use the verification chain, we first distribute  
the user data among two chained 
blocks such that each block 
of the written area has an unused word 
(Fact <ref>).
Let L be a dynamic list with direct access stored in 𝒟 (Lemma <ref>).
Whenever the block B in the written area has a data chain with a block d(B), we additionally 
require that it also must 
have a verification chain with an element of the list L (Figure <ref>).
We denote by v(B) a pointer to the element in L chained with B 
and use an unused word of B to store v(B).
Recall that, whenever the unwritten area shrinks, some elements in L change their position in D. 
To ensure the validity of the verification chains, we use the notification function of L to update the 
pointer k ∈ in the effected blocks.
The verification pointers in L, stored behind the written area, are not affected by increasing the size of 
𝒟. 






Finally, note that L has enough space to store all verification pointers 
since only one verification chain is required for 
each block in the unwritten area, i.e, L is of size O(|U|).







































































 §.§ Shrinking the Size of 𝒟 at most O(w) Times


Shrinking the size of 𝒟 means to free some memory that may be used
to store information.  We distinguish between two cases.  In the first case
we shrink the size of 𝒟 so much that L is destroyed.  In
this case we make a full initialization of 𝒟 as
follows.

Since we lose the ability to check for
unintended data chains, we first destroy them
by iterating over the verification list L, following its pointer to a block B_w, checking if
the block B_u = d(B_w) is behind the new size of 𝒟.
If it is, we initialize B_w with the initial value.
Writing the initial value into B_w may created an unintended data chain, which we break.

Now the verification list is superfluous and we can 
iterate over the unwritten area and check for a data chain. 
If there is one, we move the user values from d(B) into B and
initialize d(B), otherwise we initialize B.  
After the iteration, we set D[0] = 1. 

Since L will be
destroyed by the shrinking operation, the size |U| of the unwritten area
behind the shrinking is 
bounded by |L|.
  Thus, by using the potential function ψ = (c
 ·length of L) for some constant c≥ 2, the amortized cost of the write operation 
increases by at most c=O(1) 
and we can easily pay
for the full initialization.

In the second case, we reduce the size of 𝒟 such that the
verification list L is still completely present in 𝒟.  In this
case, all blocks of the written area remain and they still have a
verification chain.  However, the data chain can point outside of 𝒟.  If we subsequently re-increase 𝒟, some blocks may still have
a data chain and also a verification chain.  This violates our definition of
the increase operation. 

To resolve this problem 









we invalidate the data chains of all blocks outside 𝒟 as follows.
As long as there is no shrinking operation, 
we store the same version number v ∈ to all data chains.
More exactly, let B be a block in the unwritten area chained with a block
d(B) in the   
written area. Then we store the version
 inside an unused word of d(B)
using Fact <ref>.


Before we execute a shrink operation, we set n_v to the current size of
𝒟 and remember it as the size for the current version v. 
With the shrink operation, we increment the version number by one. 






Let v' be the version of the chain between B and d(B).
We call the chain valid if B is before 

the boundary n^*_v'=min{n_v|v≥ v'}.
Note that n^*_v' is the 


minimal boundary 
that 
𝒟 ever had after introducing version
number v'. 


We obtain the 
boundaries n^*_v 
from a data structure M that provides an 
operation to 
add the new size of 𝒟 after a shrink operation and another operation minbound to
check if a chain is valid, i.e., if one endpoint of the chain is or was outside of 𝒟.
For later usage, M also supports an operation remove. 

	
  * add(n) (n ∈): Increments an internal version counter v by one 
	and set the boundary n^*_v = n. All boundaries 
	n^*_i (i 
	∈{1 … v - 1}) larger than n are overwritten by n.
	
  * remove(j) (0 ≤ j ≤ v): 
	
	
        Decrements v  by j
	and removes the boundaries of the largest j versions.
	
  * minbound(v) (0 ≤ v < w): Returns n^*_v, the minimal 
	boundary for v.





	M can be implemented such that it uses O(w) words, 
        add runs in amortized constant time, and 
	minbound and remove run in constant 
	time as long as there are only O(w) versions.




        We have a version counter v^* and a table T where we store the
        initial boundary for each version.
        Moreover, we use a stack S that additionally allows us to access the elements of the 
	stack directly and the data structure R from Pǎtraşcu and 
	Thorup <cit.>. All three data structures can be implemented using a fixed size array
        and stored in extra buffers
        (Lemmas <ref> and <ref>).
        R consists of all versions v with n_v=n^*_v.
		
        
       
        The stack S store the boundaries of the versions in R in ascending 
        order from the bottom to the top.
        For a technical reason, S stores also the version with each boundary.

        To answer the minbound operation for a version v, we first determine
        the successor v' of v in R and then return n^*_v=T[v'].

	Assume that a new boundary n_v = n is added to M for a next version v.
	Set T[v] = n. 
	Before adding a new boundary n_v to S we remove all boundaries from S
	as long as the top of S is larger than n_v. Whenever removing
	such a boundary, we remove the corresponding version from R.
        Finally, we add the new boundary to S and to R.

	By doing this, we remove all boundaries that are larger than n_v. 
	Now all the versions of these boundaries get n_v as their new boundary. 
	
	Finally, it remains to check the running time. 
	We use the potential function ϕ = |S| with |S| ≤ w
        being the current size of S. 


	Determining the boundary for a specific version requires looking into R
	and to check one word in S and T. This does not change ϕ and runs in O(1) time.
        If the  running time for adding or removing versions is not
	constant, then in all except a last iteration, we remove an element
	from the stack. Thus, the decrease of ϕ pays for this.
	
	
	
	
	





 For every data chain, we can check in constant time if it is valid or not.


A chain between some blocks B and d(B) is valid exactly if d(B) ≤minbound(v) is true, 
where v is the
version of the chain and d(B) is the position of the block that belongs to the unwritten area. 


Whenever a block in the unwritten area has an invalid chain (caused by
shrinking and re-increasing 𝒟; determined by minbound), we return 
the initial 
value for
all words of the block.

We want to remark that the structure M can maintain only O(w) versions since it uses a 
dictionary from Pǎtraşcu and 
Thorup <cit.>. 
The dictionary is dynamic and supports modification and access in constant time, but only for O(w) 
entries.

We have to make sure that we have only
O(|U|) chains (counting both valid and invalid chains) so that we are able to store them. 
The problem is that a
shrink can invalidate many chains. 
Therefore, we have to clean-up our data structure
𝒟 as follows:

Whenever we add a chain, we check 
the validness of three old chains, i.e., chains with an old version number that are stored at the beginning of 
the unwritten 
area  in L. 
Invalid chains are removed whereas
valid chains are assigned to the current version.
To have the time for the clean-up, we also modify the shrink operation such
that, 
after each shrink operation, we make sure that we store at most |U| / 2
chains. 
If this is not the case, we run a full initialization. 
By assuming that every insert into 𝒟 pays a

coin, 
this can be done in amortized constant time since the number of chains that
we have is bounded by the number of insert operations.



 §.§ The General Case


The goal in this section is to limit the number of versions to O(w)
such that the data structure M from Lemma <ref>
can be always
used.  We achieve this goal by purifying the chain
information, i.e., for some old version v', we iterate through the chains
with a version larger than 
v', remove invalid data chains and store the
remaining chains under v'. Finally,  we take v' as the current version.
We so
remove all versions larger than v', 

Since we have no data structure to find invalid chains out of
a large amount of all chains, we partition the chains of each version into small subgroups 


and use also here the dictionary from Pǎtraşcu
and Thorup <cit.> to index the block positions B and d(B) that
represent the chain.  The dictionary from the subgroup with a version v allows us to find a block 
that lies
behind a boundary n^*_v in constant time as long as such a block exists.  




In detail, a subgroup always has space for Θ(w) chains (block
positions), the version v, and a data structure from Pǎtraşcu and
Thorup <cit.> (Figure <ref>).  To organize the subgroups
we use a dynamic family S from Corollary <ref>.  For each
version v, we create a dynamic set in S.  Each set consists of all subgroups of the same version.  

Instead of having a verification chain with a list L,

each chained block in the written area has now
a pointer to its subgroup. If the block is indexed in the subgroup, then its chain is verified.

As 
in the previous section we
use the data structure M to store and check
the boundaries.  Additionally, we store the version v and a table T. The
table is
used to store, for each version, the number of chains that are currently used.  
The updates of T
are not described below explicitly.  Based on the information in
T we determine how many versions we can purify.
The details of the purify operation are described on the next page.


Note that M and T are of O(w) words and the size of S is linear
in the size of the number of chains and thus bounded by O(|U|). Choosing
the block size b large enough, but still b=O(1), we can guarantee that
all data structures fit into |U| unless |U|=O(w).
By running the clean-up of the last section, M and T can be removed 
if to many writing operations shrink the unwritten area of 𝒟 so much that |U|=O(w).







	
  * initialize(n, initv)
	Allocate nw + 1 bits.
		Partition the array into blocks of size b = 6. If n is not a multiple of b, initialize
                less than b
		words and treat them separately.
	
        Use the last block(s) to store the threshold t = 0, initv, and v=1 in the unused words.
	Initialize the data structure M and S, store their internally required single words
	also in the last block(s) and their sets and lists in parallel (Lemma <ref>).
	
	
	
	
	
	
  * read(i):
	If D[0] = 1, return D[i].
	Else, check to which area B = ⌊ i/b ⌋ belongs.
	If B is inside the written area,
	check if B is verified. 
	If it is, return initv, otherwise D[i].
	
	If B is inside the unwritten area, check if B is chained with a block d(B).
	If it is not, return initv, otherwise proceed with checking if d(B) is verified.
	If it is not, return initv, otherwise follow the verification pointer and read
	the version v out of the subgroup.
	Call M.minbound(v) and return initv if it returned a boundary that is 
        larger 
	than the block position B, 
	otherwise return the right word out of B and d(B).
	
	
	
  * write(i, x):
	If D[0] = 1, write at D[i]. Otherwise, clean-up three chains as described in the last subsection. 
	Then check to which area B = ⌊ i/b ⌋ belongs.
	If B is inside the written area, check if B is verified.
	If it is not, write at D[i] directly. 
	Otherwise, the block may have a data chain with a block d(B). If so, unchain it (like in 
	<cit.>) by expanding the written area that gives us a new unused block that
	we use to relocate all values and chains from B. Correct also the chains in the subgroups.
	If not, just remove B and d(B) from its subgroup.
	In both cases, B becomes an unused block afterwards. We initialize it and write at D[i] directly.
	 If B is inside the unwritten area, check if B is chained with a block d(B).
	 If it is, check if d(B) is verified and if its chain belonging to a version v is valid 

(test ).
	 If all is true, then write x at the right position of B and d(B).

	 If the chain is invalid, delete it from its subgroup and move it into the latest subgroup of 
	 the current version.
	 Finally, initialize B and write x as described above.
	 
	 But if B is not chained, expand the written area and chain it with the new block.
	 Write both blocks inside the latest subgroup of the current version. 
	 Set a verification pointer to the subgroup where the chain is stored.
	 As before, initialize B and write 
	 
	 In all cases, whenever the unwritten area disappears, set  D[0] = 1.
	 
	 
  * increase(n_old, n_new, initv):
	 If D[0] = 0, then copy the words of the last block(s) into the new last block(s).
	 Otherwise, initialize the required data structures as described in initialize,
	 but set the initial values for the threshold t to t = ⌊ n_old / b ⌋.
	 
	 If |U| = O(w), use the bit vector solution described in the beginning of 
	 Section <ref>.
	 
  * purify(n_new):	
Iterate from the current version v = ⌈ w ⌉ in S down and add up the number of chains
stored under a version. Stop at the first version v' that has fewer chains as twice the total number 
of chains of 
all 
versions visited before.
Consider versions v' + 1 to v and iterate over all subgroups with that version.
In each subgroup, check for an invalid chain (B, d(B)) by using M,
remove it from the subgroup, from the index of the subgroup, and initialize B with initv and repeat this on the 
subgroup until it has no invalid chains.
In the special case where the subgroup has less than w chains, 
clear the subgroup by moving all chains into 
the latest subgroup of the version v'.

Then, change the version number of this subgroup to v',
unlink it from its old set and link it into the set of v'.
When finished, set the current version number v to v'.
	 
  * shrink(n_old, n_new):
	 If the new size of 𝒟 either cuts the space used to store 
         the data structures S or M or 
	 leaves less than 
	 Θ(w) unused words in the unwritten area, run the full initialization.
	 
	 If we do not fully initialize 𝒟, we proceed as follows:
	 If we have ⌈ w ⌉ versions, call purify.
         Otherwise, create a new set inside S and increment the current version 
	 number v by one and
	 check if the last used subgroup has less than w entries. 
         If so, we reuse this subgroup by removing all invalid chains. (In purify we already described the 
         removal.)




Who pays for the purification? The idea is to give 
a gold coin to each previous set in S, whenever we insert an element.
Whenever a set of size x has at least x/2 coins, we clean up the set
and all sets with a larger version number. 
Algorithmically we can not check fast enough if a set already has enough coins. 
Therefore, we wait with the purification until we have ⌈ w ⌉ versions and check
then the condition for 
every version
from the largest version to the smallest until we found the first version with enough coins.




 There is a dynamic array that works in-place and supports
 the operations initialize, read,
 write as well as increase in constant time and shrink in amortized
 constant time.



 It remains to show the running times of the operations.
Take ψ as the total number of verification chains similar to Subsection <ref>,
c_i as the number of chains with the version 
i∈{0,…,v-1} and g = ∑_i=0^v - 16i · c_i/w. 
Moreover, choose τ as the total number of missing elements such that all subgroups 
are full and 
We use the following potential function ϕ = ψ + v  + g+ τ + f.
Note that 
g corresponds to the 
usage of the gold coins 

and f is non-zero only if there are very few blocks in the unwritten area U, but 𝒟 is not completely initialized.


	
  * initialize:
	We have to set the threshold t and the current version in O(1) time. Thus,
	ϕ = v = 1—note that f=0 by using the bit-vector solution if necessary.
	
	
  * read:
	Checking chains, 
        reading the version number
	and calling the minbound function of M
	can be done in constant time and ϕ does not change.
	
  * write:
	
        We possibly have to check if a block is chained, verified and valid.


	We also may create a chain, a verification and insert it into S.
	All these operations require O(1) time. 
	In total, the number of chains may increase by one Δψ = O(1), Δ g =
	6v/w with v 
	being the current version. Thus, Δϕ=O(1).
	
  * increase:
	Copying a few blocks of constant size 
        
        runs in O(1)) time and Δϕ=0 since Δ f=0. 

	
  * purify:	
	Whenever we run purify we remove the last v-i versions for the largest i with
	v_i/2 ≤ y := ∑_i+1^v - 1c_i is valid. 
	
	Thus, we first have to search for version i, i.e, we consider v-i versions.
	Moreover, we then have to iterate over 3y chains in 6y/w subgroups—a subgroup is always 
	at least half full.
	In each subgroup we spend 1 + d time, where d is the number of deleted chains in
	each subgroup.
	This can be done in at most (v-i)+6y/w + d^* time units where
	d^* is the total number of deleted chains.
	In addition, we may have deleted half empty subgroups and moved their chains to the latest subgroup. This 
	can be done in O(m) time if m is the number of moved chains.
	

	We can pay for the running time since the value of the potential function decreases as follows.
	By deleting versions larger than i, Δ v = -(v-i).
	Since we change the version of all subgroups with a version larger
	than
        i to i, i.e.,
	we shrink the version of y chains by at least one, Δ g = -6y/w.
	In addition, Δ(ψ + τ) ≤ -2d^*+(d^*-m) = -d^*-m where the -m 
        comes from the fact that half empty subgroups disappear, i.e,
	are not taken into account in τ.
	
	To sum up, the amortized running time is O(1).

	
  * shrink: In Subsection <ref>, we already analyzed the 
         case that 𝒟 is fully initialized—the only change is that
 we have further parts in the potential function, but their change is either zero or
 negative. 

        Otherwise, we have to delete invalid chains in the latest subgroup
        and update it to the new version, which can be done 
        in O(1) amortized time since Δψ drops linear in the number of
        deleted chains. Moreover, we have to add a new version to M
        and possibly delete several older versions. All this can be done in O(1)
        amortized time. And finally, we may run a purify; again in O(1)     
        amortized time.	

We thus have shown all running times as promised in the theorem.










§ ACKNOWLEDGMENTS

Andrej Sajenko acknowledges the support
of the Deutsche Forschungsgemeinschaft (DFG), project SpaceeffGA
(KA 4663/1-1). 






tocchapterBibliography





tocchapterAppendix




§ APPENDIX


The purpose of this appendix is to present the missing proofs. The
corresponding
lemma and theorem are repeated for the reader's convenience.



 
        M can be implemented such that it uses O(w) words, 
        add runs in amortized constant time, and 
        minbound and remove run in constant
        time as long as there are only O(w) versions.






 There is a dynamic array that works in-place and supports
the operations initialize, read,
write as well as increase in constant time and shrink in amortized
constant time.




