Oluwole Ajala
email: [oluwole.ajala@kcl.ac.uk

Hayam Alamro
email: hayam.alamro@kcl.ac.uk

Costas Iliopoulos
email: costas.iliopoulos@kcl.ac.uk

Grigorios Loukides
email: grigorios.loukides]@kcl.ac.uk

Towards String Sanitization

Keywords: string, sanitization, data privacy

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Data that are used in a number of applications such as mining and web analysis often come in the form a long sequence of events. In many of these applications, such as biomedical informatics, network analysis, and marketing, the patterns of interest in analysis come in the form of consecutive symbols, i.e., substrings of the long sequence (string). At the same time, the data also contains patterns (substrings) that represent confidential information that must be protected before the data are published (released) for analysis. Examples of such information are medical knowledge (diagnosis and medications) and business secrets.

In this work, we study the general problem of sanitizing a string. The problem deviates from existing works, which focus on the sanitization of event sequences, or relational tables (i.e., collections of records). We formalize the problem of protecting a string by sanitizing (i.e., concealing) a given set of sensitive patterns that represent confidential information. To achieve this, we replace selected symbols in all occurrences of the sensitive patterns in the string with a symbol " * ". That is, we inject uncertainty in the string. This clearly reduces the usefulness of the protected string in applications.

Thus, in our problem, we aim to conceal the sensitive patterns while preserving the utility of the string as much as possible. As we show, the problem is NP-hard. To address the problem, we propose an algorithm, called SSA (String Sanitization Algorithm) that first efficiently detects occurrences of the sensitive patterns in the string and then sanitizes these sensitive patterns. The detection of the sensitive patterns is performed by the Aho-Corasick algorithm [START_REF] Aho | Efficient string matching: An aid to bibliographic search[END_REF], which takes linear time in the length of the string. The sanitization of the sensitive patterns is performed by a greedy algorithm that is inspired by the well-known greedy algorithm for the Set Cover (SC) problem [START_REF] Cormode | Set cover algorithms for very large datasets[END_REF]. This algorithm is called SanitizeClusters, and it works by iteratively replacing the symbol that is contained in the largest number of currently unprotected sensitive patterns with the special symbol " * ".

We also present a preliminary set of experiments to demonstrate the effectiveness and efficiency of our algorithm. In our experiments, we apply the algorithm to a commonly used sequential dataset and study empirically its effectiveness in terms of preserving data utility, as well as its efficiency. Our results show that the algorithm can sanitize the dataset in less than 10 milliseconds and produce a sanitized dataset with a small number of occurrences of the symbol " * ".

The organization of the rest of the paper is as follows. Section 2 summarizes the related work and state of art of this current research. In Section 3, we present our preliminaries containing formal definitions and an overview of the problem statement. We highlight our approach in Section 4, where we present our algorithms, their implementation and examples. We present a preliminary experimental evaluation of our approach in Section 5. Finally, we conclude and discuss future work in Section 6.

Related Work

Data sanitization is an important methodology to protect data, by means of concealing confidential knowledge in the form of user-specified patterns. Most existing sanitization approaches are applied to a collection (multi-set) of transactions [START_REF] Oliveira | Protecting sensitive knowledge by data sanitization[END_REF][START_REF] Sun | A border-based approach for hiding sensitive frequent itemsets[END_REF][START_REF] Verykios | Association rule hiding[END_REF], sequences [START_REF] Abul | Hiding sequential and spatiotemporal patterns[END_REF][START_REF] Gkoulalas-Divanis | Revisiting sequential pattern hiding to enhance utility[END_REF][START_REF] Gwadera | Permutation-based sequential pattern hiding[END_REF], or trajectories [START_REF] Abul | Hiding sequential and spatiotemporal patterns[END_REF] and prevent the mining of frequent sensitive patterns [START_REF] Abul | Hiding sequential and spatiotemporal patterns[END_REF][START_REF] Gkoulalas-Divanis | Revisiting sequential pattern hiding to enhance utility[END_REF][START_REF] Sun | A border-based approach for hiding sensitive frequent itemsets[END_REF] or association rules [START_REF] Oliveira | Protecting sensitive knowledge by data sanitization[END_REF][START_REF] Verykios | Association rule hiding[END_REF], by applying deletion. To preserve utility, these approaches attempt to minimize the total number of deleted items (events) [START_REF] Gkoulalas-Divanis | Revisiting sequential pattern hiding to enhance utility[END_REF] and/or changes in the frequency of nonsensitive patterns [START_REF] Abul | Hiding sequential and spatiotemporal patterns[END_REF], as well as in the output of frequent pattern [START_REF] Gkoulalas-Divanis | Revisiting sequential pattern hiding to enhance utility[END_REF][START_REF] Gwadera | Permutation-based sequential pattern hiding[END_REF][START_REF] Sun | A border-based approach for hiding sensitive frequent itemsets[END_REF] or association rule [START_REF] Oliveira | Protecting sensitive knowledge by data sanitization[END_REF][START_REF] Verykios | Association rule hiding[END_REF] mining. We share the utility goal of [START_REF] Gkoulalas-Divanis | Revisiting sequential pattern hiding to enhance utility[END_REF], but contrary to all these approaches, we consider a long string of events. This is somewhat similar to the work of [START_REF] Loukides | Optimal event sequence sanitization[END_REF], which considered a sequence of events that are associated with time points. However, our work differs from that of [START_REF] Loukides | Optimal event sequence sanitization[END_REF] along two important dimensions. The first dimension is related to the type of data considered. Specificailly, we consider a string (sequence of symbols), whereas the work of [START_REF] Loukides | Optimal event sequence sanitization[END_REF] considers a sequence of multisets of symbols, where each multiset is associated with a time point. The second dimension is related to the problem considered. Specifically, the problem we aim to solve requires concealing sensitive strings (i.e., sequences of consecutive symbols that can potentially contain gaps), while minimizing the total number of deleted events. On the ontrary, the problem of [START_REF] Loukides | Optimal event sequence sanitization[END_REF] requires concealing single events (symbols), while preserving the distribution of event in the entire sequence. Also, we consider a sensitive string concealed when it does not appear in the entire string (i.e., has frequency zero), whereas the work of [START_REF] Loukides | Optimal event sequence sanitization[END_REF] considers a sensitive event concealed when its frequency in the event sequence is below a given threshold in any prefix of the sequence. The two problems also belong to different complexity classes; our problem is strongly NP-hard, as we show, and thus cannot be solved optimally in polynomial time, whereas the problem in [START_REF] Loukides | Optimal event sequence sanitization[END_REF] is weakly NP-hard and thus admits a pseudopolynomial time optimal algorithm. Anonymization is a different methodology to protect data, whose goal is not to conceal given sensitive patterns but to preserve the privacy of individuals, whose information is contained in the data, by preventing inferences of the identity and/or sensitive information of these individuals. Most anonymization approaches are applicable to a collection of transactions [START_REF] Chen | Publishing set-valued data via differential privacy[END_REF][START_REF] Gkoulalas-Divanis | Utility-guided clustering-based transaction data anonymization[END_REF], trajectories [START_REF] Abul | Never walk alone: Uncertainty for anonymity in moving objects databases[END_REF][START_REF] Poulis | Apriori-based algorithms for km-anonymizing trajectory data[END_REF], or sequences (with [START_REF] Sherkat | Efficient time-stamped event sequence anonymization[END_REF] or without [START_REF] Monreale | Anonymity preserving sequential pattern mining[END_REF] time points), each of which is associated with a different individual. Another category of approaches anonymizes an individual's time-series [START_REF] Rastogi | Differentially private aggregation of distributed time-series with transformation and encryption[END_REF] or event sequence [START_REF] Götz | Maskit: Privately releasing user context streams for personalized mobile applications[END_REF], using differential privacy [START_REF] Dwork | Differential privacy[END_REF]. Anonymization approaches guard against the disclosure of an individual's identity [START_REF] Abul | Never walk alone: Uncertainty for anonymity in moving objects databases[END_REF][START_REF] Monreale | Anonymity preserving sequential pattern mining[END_REF] and/or sensitive information [START_REF] Abul | Never walk alone: Uncertainty for anonymity in moving objects databases[END_REF][START_REF] Chen | Publishing set-valued data via differential privacy[END_REF][START_REF] Götz | Maskit: Privately releasing user context streams for personalized mobile applications[END_REF][START_REF] Rastogi | Differentially private aggregation of distributed time-series with transformation and encryption[END_REF][START_REF] Sherkat | Efficient time-stamped event sequence anonymization[END_REF]. However, they cannot be applied to our problem, because their privacy models do not conceal the sensitive patterns in a long string, which we require to preserve privacy. Suppressing sensitive patterns from an infinite event sequence has been studied in [START_REF] He | On the complexity of privacy-preserving complex event processing[END_REF][START_REF] Wang | Utility-maximizing event stream suppression[END_REF]. These works aim to achieve privacy by minimizing the number of occurrences of sensitive patterns, while preserving the occurrences of certain nonsensitive patterns that are specified by data owners. Both types of patterns are sets of events. Thus, these works are not applicable to our problem, because they consider different type of data and have different utility goals.

3 Background and problem definition

Background

We begin with basic definitions and notation from [START_REF] Crochemore | Algorithm on strings[END_REF].

Let x = x[0]x[1] . . . x[n -1]
be a string of length |x| = n over a finite ordered alphabet. We consider the case of strings over an integer alphabet: each letter is replaced by its lexicographical rank in such a way that the resulting string consists of integers in the range {1, . . . , n}. For two positions i and j on x, we denote by x[i . . . j] = x[i] . . . x[j] the factor (sometimes called substring) of x that starts at position i and ends at position j (it is of length 0 if j < i), and by ε the empty string of length 0. We recall that a prefix of x is a factor that starts at position 0 (x[0 . . . j]) and a suffix of x is a factor that ends at position n -1 (x[i . . . n -1]). A prefix (resp.suffix) is said to be proper if it is any prefix (resp. suffix) of the string other than the string itself. For example, any of the strings in {a,ac, acc, accg} (respectively, {ccgt, cgt, gt, t}) is a proper prefix (respectively, suffix) of the string accgt.

We denote with S a string that we aim to protect and with S the set of symbols contained in S. To protect the string S, we conceal a set of substrings, SP = {sp 1 , . . . , sp n }, of S. We refer to the substrings of SP as sensitive patterns, and we denote the set of symbols ∪ i∈ [1,n] sp i with SP. To conceal a sensitive pattern sp i , we replace at least one symbol in it with a symbol * ̸ = ε. This process constructs a sanitized sensitive pattern sp ′ i corresponding to sp i . If sp i occurs multiple times in the string S, we replace each occurrence of sp i with sp ′ i . Doing this for every sensitive pattern in SP constructs a sanitized string S ′ corresponding to S. Clearly, we cannot be certain about the symbols that were replaced by the symbol " * " in the sanitized string S ′ . This helps preserving privacy, because a recipient of S ′ interprets " * " as any symbol of S (assuming that S is public knowledge and contains more than one symbol).

Problem definition

In this section, we formally define the probem we study and show that it is NP-hard.

Problem 1 (Optimal String Sanitization (OSS))

. Given a string S and a set of sensitive patterns SP = {sp 1 , . . . , sp n }, construct a sanitized string S ′ from S, such that: (I) S ′ contains no sp i ∈ SP , i ∈ [1, n], as a substring, (II) S ′ contains each sanitized pattern,

sp ′ i , i ∈ [1, n]
, that is constructed from sp i by replacing at least one symbol in sp i with the symbol * , as a substring, and (III) the number of occurrences (multiplicity) of the symbol * in S ′ is minimum.

Theorem 1. The OSS problem is NP-hard.
Proof. The proof is by reducing the NP-hard Set Cover (SC) problem to OSS. The SC problem is defined as follows. Given a universe of elements U = {u 1 , . . . , u n } and a collection L = {L 1 , . . . , L m } such that each L j ∈ L is a subset of U , find a subcollection L ′ ⊆ L, such that: (I) L ′ covers all elements of U (i.e., ∪ Lj ∈L ′ L j = U ), and (II) the number of subsets in L ′ is minimum.

We map a given instance I SC of SC to an instance I OSS of the OSS problem, in polynomial time, as follows: I Each element u i ∈ U is mapped to a sensitive pattern sp i ∈ SP , so that covering the element u i corresponds to constructing a santized pattern sp ′ i from sp i . II Each subset L j = {u 1 , . . . , u r } ∈ L is mapped to a set SP j = {sp 1 , . . . , sp r } ⊆ SP of sensitive patterns which have a common symbol s j ∈ S, so that selecting L j corresponds to constructing a set of sanitized patterns {sp ′ 1 , . . . , sp ′ r } by replacing the common symbol s j of the patterns in SP j with the symbol * .

In the following, we prove the correspondence between a solution L ′ to the given instance I SC of SC and a solution S ′ to the instance I OSS .

We first prove that, if L ′ is a solution to I SC , then S ′ is a solution to I OSS . Since ∪ Lj ∈L ′ = U = {u 1 , . . . , u n }, a sanitized sensitive pattern sp ′ i is constructed for each sensitive pattern sp i in SP . Thus, S ′ contains no sensitive pattern in SP as a substring, and it contains each sanitized sensitive pattern sp ′ i that corresponds to a sensitive pattern sp i , i ∈ [1, n], as a substring. Since the number of subsets in L ′ is minimum and each L j ∈ L ′ leads to the replacement of the common symbol s j of the patterns in SP j with * , the sensitive patterns in SP are sanitized with the minimum number of occurrences of the symbol * . Furthermore, all occurences of a sensitive pattern sp i must be replaced with its corresponding sensitive pattern sp ′ i . Thus, the number of occurrences of the symbol * contained in the sanitized string S ′ is minimum, and S ′ is a solution to I OSS .

We now prove that, if S ′ is a solution to I OSS , then L ′ is a solution to I SC . Since S ′ is a solution to I OSS , each sensitive pattern in SP is sanitized, which implies that L ′ covers all elements of U . In addition, the number of occurrences of the symbol * in S ′ is minimum. This implies that the sensitive patterns in SP are sanitized with the minimum number of occurrences of the symbol * and hence the number of selected subsets in L ′ is minimum. Thus, L ′ is a solution to I SC .

⊓ ⊔

String Sanitization Algorithm

This section discusses the String Sanitization Algorithm (SSA), which aims to solve the OSS problem. The algorithm is based on: (i) the Aho-Corasick string matching algorithm whose objective is to efficiently detect the occurrences of all sensitive patterns in the string, (ii) the SetIntersection algorithm whose objective is to organize sensitive patterns into clusters based on the symbols they share, and (iii) the SanitizeClusters algorithm whose objective is to perform the sanitization of the sensitive patterns in each cluster by replacing selected symbols in the patterns by the symbol " * ".

Aho-Corasick algorithm

The Aho-Corasick algorithm [START_REF] Aho | Efficient string matching: An aid to bibliographic search[END_REF] is a well-known, efficient algorithm for detecting all occurrences of a finite set of patterns P = {p 1 , . . . , p k } in a given text T . Both patterns and T are strings. The algorithm constructs a finite state machine (FSM) automaton for the set of patterns P , which is used to perform pattern matching on the text T (i.e., find the symbol of T at which each occurrence of each pattern in P occurs in T ). The benefit of the Aho-Corasick algorithm is that it works in linear time (when the string is independent of the number of patterns, as in our case). Specifically, the worst-case time complexity of the algorithm is

O(|T | + ∑ i∈[1,k] |p i | + M P,T )
, where |T | denotes the length of T , ∑ i∈ [1,k] |p i | denotes the the total length of the patterns in P , and M P,T denotes the number of occurrences of patterns in P in the text T . This is typically much faster than the naive solution of detecting the occurrences of each pattern in P independnetly, which takes O( ∑ i∈ [1,k]

|p i | • |T |) time.
In this work, we use the Aho-Corasick algorithm to detect all occurrences of sensitive patterns {sp 1 , . . . , sp n } in the string S, which is needed to before sanitizing the sensitive patterns (i.e., replacing at least one symbol in each sensitive pattern with * , in all occurrences of the sensitive pattern in the string). Thus, the worst-case time complexity of the Aho-Corasick algorithm in our case is

O(|S| + ∑ i∈[1,m] |sp i | + M SP,S
), where |s| is the length of the string S, ∑ i∈ [1,m] |sp i | is the total length of the sensitive patterns in SP , and M SP,S is the number of occurrenses of sensitive patterns in SP in S. Since the sensitive patterns have generally a small number of occurrences (since they model confidential knowledge), the Aho-Corasick algorithm is a good choice for detecting the occurrences of sensitive patterns in the OSS problem.

SetsIntersection algorithm

After applying the Aho-Corasick algorithm to the string S, all occurrences of each sensitive pattern sp i ∈ SP are contained in Occ(SP ). We denote the j-th occurrence of sensitive pattern sp i in the string S with Occ(sp i , j). If the sensitive pattern sp i is a substring sp i [l . . . l ′ ] of S, we denote its occurence with the positions l and l ′ . Given Occ(SP ) and SP , the SetsIntersection algorithm begins by creating an empty twodimensional array A. Then, it fills A by iterating over each sensitive pattern sp i and creating a cluster C that contains sp i together with all other sensitive patterns that share a position with sp i . The set of sensitive patterns in C is added into the first element of A. The second element of A contains either the first position of each occurrence of a sensitive pattern, if the cluster contains only one sensitive pattern (i.e., no other sensitive pattern shares symbols with the sensitive pattern in the cluster), or the common positions of all occurrences of the sensitive patterns in C otherwise. After considering all sensitive patterns, the algorithm returns the array A. Add into Cj all sensitive patterns that share a position with spi 7:

A[j][0] ← Cj 8:
if Cj contains one sensitive pattern then 9:

A[j] [START_REF] Abul | Never walk alone: Uncertainty for anonymity in moving objects databases[END_REF] ← first position of each occurrence of the sensitive pattern 10: else 11:

A[j] [START_REF] Abul | Never walk alone: Uncertainty for anonymity in moving objects databases[END_REF] ← all common positions of each occurrence of the sensitive patterns in Cj and the first position of each occurrence of a sensitive pattern in Cj 12:

end if 13: return A

SanitizeClusters algorithm

This algorithm gets as input the array A created by the SetsItersection algorithm, together with the string S. First, it initializes the sanitized string S ′ with the original string S. Then, in the for loop, it iteratives over each cluster (set of sensitive patterns contained in the first element of each record in the array A), and it sanitizes the sensitive patterns in the cluster. The sanitization of the sensitive patterns in the cluster (see do while loop) is performed until every sensitive pattern in the cluster has at least one symbol replaced by * . To sanitize the sensitive patterns in the cluster, the algorithm finds the most frequent position p corresponding to the sensitive patterns in the cluster and replaces the position with * in S ′ . If there are more than one most frequent positions, the algorithm selects the last position, for efficiency. After all clusters are sanitized, the algorithm returns the sanitized string S ′ . p ← most frequent position in C (break ties with last most frequent position) 7:

Replace p with * in S ′ 8:

while a sensitive pattern in C does not have at least one symbol replaced with * in S ′ 9: return S ′

SSA algorithm

We are now ready to present the SSA algorithm. The algorithm gets as input the string S and the set of specified sensitive patterns SP , and it begins by calling the Aho-Corasick algorithm, to obtain a set of positions Occ(SP ), for each sensitive pattern in SP . Then, SSA calls the SetsIntersection algorithm using Occ(SP ) and SP , to create the array A that organizes the sensitive patterns into clusters that are associated with their corresponding positions. Next, the array A together with the string S is given as input to the SanitizeClusters algorithm, which produces the sanitized string S ′ . Last, the SSA algorithm returns S ′ . The SSA algorithm will first execute the Aho-Corasick algorithm to obtain Occ(SP ), as shown in Fig. 2. After that, the SetsIntersection will be executed to create clusters of sensitive patterns and find the common positions of all occurrences of the sensitive patterns in each cluster (i.e., positions in S that are shared by all patterns in the cluster), if the cluster contains more than one sensitive patterns, or the first position of all occurrences of the sensitive pattern, otherwise. The 5 clusters, together with their corresponding positions in the string S are returned as an array A, as illustrated in Fig. 3. After that, the SanitizeClusters algorithm will consider each cluster and replace the most frequenct of its corresponding positions in the string S with * , until all occurrences of all sensitive patterns in the cluster are sanitized (i.e., they have at least one of their positions replaced with * ). The positionts that will be replaed with * are shown in bold in Fig. 3. Then, the SanitizeClusters algorithm will return the sanitized string S ′ , which is produced by replacing the selected positions with * . The sanitized string S ′ is shown in Fig. 4. Last, S ′ is output by the SSA algorithm. As can be seen from Figures 5,6, and 7, the algorithm is reasonably efficient, requiring no more than 10 miliseconds to sanitize the set of sensitive patterns, which contains no more than 15 patterns. Furthermore, as expected, the runtime generally increases with the number of sensitive patterns, because, the more sensitive patterns we have, the larger their sum of lengths are (shown as total length of sensitive patterns in the tables).

In addition, the algorithm does not replace a large number of symbols with * . Specifically, the number of symbols that were replaced was no more than 895. As expected, the number of symbols that were replaced generally increases with the number of specified sensitive patterns. For example, it increases from 607 to 895 in Figure 7. However, this was not true in Figure 5, because in this experiment the sensitive patterns that were added as the number of sensitive patterns increased from 5 to 15 did not have many of their symbols selected for replacement by the algorithm.

Conclusion and Future Work

String sanitization is a necessary task in applications that feature sequences containing confidential information. This paper studied the problem of how to efficiently sanitize a string by replacing a small number of selected symbols contained in sensitive patterns with a special character " * ". To deal with the problem, we proposed an algorithm SSA that fuses two sub-algorithms, one for detecting occurrences of sensitive patterns in the string, and another for sanitizing the sensitive patterns. The proposed algorithm was implemented and evaluated using the ADL dataset. Our results demonstrate the efficiency and effectiveness of our approach. Being the first work on addressing the problem of sanitizing a string, this work opens up a number of interesting avenues for future investigation. These include: (i) examining how to preserve the utility of the sanitized string in analytics or mining applications, (ii) developing algorithms for sanitizing strings that do not fit into the main memory, and (iii) performing an evaluation of the algorithm using sensitive patterns that are specified by experts and model their privacy requirements (e.g., as in [START_REF] Gkoulalas-Divanis | Utility-guided clustering-based transaction data anonymization[END_REF][START_REF] Poulis | Apriori-based algorithms for km-anonymizing trajectory data[END_REF]).

Algorithm 1 1 :

 11 SetsIntersection Input: sensitive patterns SP , Occ(SP ) containing all occurrences of each sensitive pattern in the string S. 2: Output: 2D array A. The i-th record of A contains two elements: the first is the cluster i (set of sensitive patterns), and the second is the positions of S that these sensitive patterns share. 3: Create empty 2D array A 4: for each sensitive pattern spi ∈ SP 5: create new cluster Cj that contains spi 6:

Algorithm 2 1 :

 21 SanitizeClusters Input: Array A created by Algorithm 1, string S 2: Output: Sanitized string S ′ 3: S ′ ← S 4: for each cluster C contained in the first column of A 5: do 6:

Algorithm 3 1 :Fig. 1 .

 311 Fig. 1. Occurrences of sensitive patterns sp1, . . . , sp5 in the string S.

Fig. 2 .

 2 Fig.2. Occ(SP ) constructed by output of the Aho-Corasick algorithm. Occ(spi, j) refers to the j-th occurrence of the sensitive pattern spi in the string S and corresponds to a a pair of positions denoting the positions at which the occurrence of spi starts and ends in S.

Fig. 7 .

 7 Fig. 7. Results for dataset for activity climbing stairs.

  In this section, we evaluate SSA in terms of efficiency (running time) and utility (total number of deleted symbols). We did not compare against existing sanitization methods, as they cannot address the OSS problem. The dataset used was the Activities of Daily Living (ADL) dataset. This dataset is available from the UCI repository (https://archive.ics.uci.edu/ml/), and it has beeen used in prior works on data sanitization[START_REF] Loukides | Optimal event sequence sanitization[END_REF]. Based on this dataset, the following results were obtained:Num. of sens. patterns Total length of sens. patterns Num. of * s Time (in ms)

	0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
	a a t c c * g c a * c t * g a a t t g c a * g c c t * a a a a * t
	Fig. 4. Sanitizing sensitive patterns in a given text string after applying SSA
	5 Experimental Evaluation
	5	9		694	5.25
	10	17		694	5.75
	15	33		447	5.87
	Fig. 5. Results for dataset for activity brushing of teeth.
	Num. of sens. patterns Total length of sens. patterns Num. of * s Time (in ms)
	5	11		134	5.60
	10	17		219	5.75
	15	33		220	5.82
	Fig. 6. Results for dataset for activity drinking glass.
	Num. of sens. patterns Total length of sens. patterns Num. of * s Time (in ms)
	5	9		607	5.5
	10	cluster 17	positions	682	5.77
	15	{sp1} 33	5, 12	895	5.82
		{sp2, sp3, sp4}	8, 9
		{sp2, sp5, sp1} 20, 21
		sp2	26
		sp3, sp4	29, 30, 31
	Fig. 3. Array A constructed by the SetIntersection algorithm. The position deleted by the Sani-
	tizeClusters appears in bold.


Stefanos Stavrotheodoros
email: stavrotheodoros@iti.gr

Nikolaos Kaklanis

Konstantinos Votis
email: kvotis@iti.gr

Dimitrios Tzovaras
email: tzovaras@iti.gr

A smart-home IoT infrastructure for the support of independent living of older adults

Keywords: Telemedicine, Internet of Things, Elderly monitoring

Although the healthcare sector has been hugely benefited from the advantages made in the Information and Communication Technology (ICT) domain in the recent years, the emerging technology breakthrough of the Internet-of-Things (IoT), in which all devices and services are collaborating while reducing human intervention, promises new solutions that will enable users to have a more home-centric healthcare, and a sustainable active and healthy ageing. This paper is proposing a smart-home IoT infrastructure for the support and extension of the independent living of older adults in their living environments that responds also to real needs of caregivers and public authorities. The proposed infrastructure seamlessly utilizes health and monitoring devices for the provision of a safe environment for an elderly, the mitigation of frailty and the preservation of quality of life and autonomy. It also provides a mechanism for easy setup and testing of the installed equipment and a decision support system that offers advanced data analytics and visual analytics mechanisms to the formal and informal caregivers of the elderly for the efficient monitoring of their health and activity status.

Introduction

Most of the countries are encountering a shift in the distribution of their population towards older ages, caused by rising life expectancy, declining birth rates, or a combination of both.

Although the current health caring model is hospital-centric, it is expected to gradually be transformed to a more hospital-home-balanced by 2020 [START_REF] Koop | Future delivery of health care: Cybercare[END_REF], and eventually to home-centric. Ageing in place does not only reflects the preferences of the elderly who wish to stay in their own homes as they age [START_REF] Wiles | Home as a new site of health care consumption[END_REF], yet in addition of the policymakers, who are attracted by the possibility of keeping the health care expenditures within the bounds of economic possibility [START_REF] Grabowski | The cost-effectiveness of long-term care services: review and synthesis of the most recent evidence[END_REF].

The effort made in this health caring model transformation is primarily based on the use Ambient Assisted Living (AAL) solutions. Typically, AAL refers to the use of ICT, assistive devices and smart home technologies in a person's daily living to enable individuals living in their place in a convenient and safe manner. It ensures greater autonomy and provides supportive home environments by means of integrating sensors, actuators, smart interfaces, and artificial intelligence [START_REF] Sixsmith | A user-driven approach to developing ambient assisted living systems for older people: the SOPRANO project[END_REF].

IoT emerged as one of the major communication advantages in recent years and is defined as the ability of everyday life objects to connect and communicate with each other [START_REF] Dohr | The Internet of Things for Ambient Assisted Living[END_REF]. These devices, objects or things are identifiable, readable, recognizable and even controllable via the Internet. With the use of IoT, AAL systems are enhanced and able to consist of medical sensors, wireless sensors, computer hardware, computer networks, software applications, and databases, which can be interconnected to exchange data and provide services in an Ambient Assisted environment [START_REF] Memon | Ambient assisted living healthcare frameworks, platforms, standards, and quality attributes[END_REF].

One of the main problems with the IoT is that it is so vast and such a broad concept that there is no proposed, uniform architecture. In order for the idea of IoT to work, it must consist of an assortment of the sensors, network, communications and computing technologies, amongst others [START_REF] Gigli | Internet of Things, Services and Applications Categorization[END_REF]. Creating an IoT health system that will ensure the monitoring and independent living of an elderly at his home has many challenges that must be faced. An efficient topology must be selected, and devices produced to different specification and using different communication protocols must be integrated. All vital private information such as personal healthcare information must also be protected by providing confidentiality, integrity, authentication and authorization.

Although several IoT platforms have been developed to support cognitively impaired individuals, a major challenge is to provide a solution that combines efficiently health and behavioural monitoring, thus addressing a large variety of daily needs of the elderly.

This paper presents a smart-home IoT infrastructure for the support of independent living of the elderly developed in the context of the ACTIVAGE H2020 EU project. Specifically, the architecture developed for the Greek deployment site, where a largescale pilot will take place in three different regions with 500 beneficiaries, is presented. The proposed architecture includes a wireless sensor network consisted of devices and sensors of different communication protocols and provides tools for easy installation of the equipment by the personnel. The platform aggregates information gathered by sensors and health devices and integrates them to support the delivery of telehealth services. The collected data are stored in cloud infrastructure and can be accessed only by authorized informal and formal caregivers for monitoring of the health and activity status of the elderly.

The rest of the paper is structured as follows: Section 2 describes several solutions that have been implemented for monitoring and supporting the independent living of elderly people, whereas Section 3 describes the architecture and the layers of the proposed solution along with an in-detail analysis of all used devices/sensors and protocols. Finally, Section 4 concludes the paper.

Related work

The technological advances in microelectromechanical systems have made available efficient, low cost, low power miniature devices for use in remote monitoring applica-tions. Several platforms have been implemented in order to monitor and support the independent living of elderly adults. For example, the IN LIFE system [START_REF] Stavrotheodoros | A Personalized Cloud-Based Platform for AAL Support to Cognitively Impaired Elderly People[END_REF] is a cloudbased platform that provides AAL support to cognitively impaired elderly people, through numerous provided tools and services. The MyLife project [START_REF]MyLife project[END_REF] supports independence for older people with reduced cognitive function by giving them access to simple and intuitive services that adapt to their individual needs and wishes. Although both platforms, meet several needs posed by cognitive decline, they do not utilize the capabilities provided by the IoT infrastructure. On the other hand, numerous solutions adopt the IoT paradigm for the indoor support of elderly people and mainly focus on human activity recognition (HAR) and health monitoring.

The goal of the human activity recognition is to recognize common human activities in real life settings by extracting knowledge from the data acquired by smart sensors [START_REF] Kim | Human activity recognition and pattern discovery[END_REF].

There are HAR solutions that utilize sensors that are placed in various locations within a smart home, acting as non-intrusive monitoring devices for identifying human behaviors. In particular, Kasteren et al. [START_REF] Van Kasteren | An activity monitoring system for elderly care using generative and discriminative models[END_REF] designed a system for recognizing various living activities in a smart home deploying door sensors, pressure-sensitive mats, float sensor, and temperature sensor. For the TAFETA project [START_REF] Arcelus | Integration of smart home technologies in a health monitoring system for the elderly[END_REF], a homebased automated system has been implemented that monitors the health and wellbeing of an elderly while remaining unobtrusive by using various types of intelligent sensors in the elderly's home. Chen et al. [START_REF] Chen | A knowledge-driven approach to activity recognition in smart homes[END_REF] designed a system for recognizing complex living activities in a smart home deploying contact, motion, tilt and pressure sensors, while Zhang et al. [START_REF] Zhang | Assisting an elderly with early dementia using wireless sensors data in smarter safer home[END_REF] also describe a similar system named "Smarter and Safer Home" that deploys sensors in homes, acting as non-intrusive monitoring devices for human behavior of elderly people. The aggregated data of the aforementioned systems are used in order to identify "abnormal" situations.

Other HAR solutions provide activity-monitoring functionalities by using wearable devices for indoor localization. Komai et al. [START_REF] Komai | Beaconbased multi-person activity monitoring system for day care center[END_REF] describe an activity monitoring system that utilizes a wearable BLE beacon device for indoor localization. Popleteev [START_REF] Popleteev | Activity tracking and indoor positioning with a wearable magnet[END_REF] presented an activity tracking and indoor positioning system with a wearable magnet and similarly, Belmonte-Fernández et al. [START_REF] Belmonte-Fernández | An Indoor Positioning System Based on Wearables for Ambient-Assisted Living[END_REF] by using a Smart-watch wearable device that acquires the Wi-Fi strength signals of surrounding installed Wireless Access Points. Finally, [START_REF] Santos | Internet of things and smart objects for M-health monitoring and control[END_REF] Santos et al., has proposed an RFID based M-health care system using IoT based connected devices, that identifies the position of an m-health related item (e.g. elderly) carrying an RFID tag.

Regarding the health monitoring, its goal is to allow an individual to closely monitor his/her vital signs, provide feedback for maintaining an optimal health status and create alerts when vital measurements are below or over a predefined threshold [START_REF] Yap | Design and implementation of ubiquitous ECG monitoring system by using android tablet[END_REF].

Several health-monitoring systems utilize devices that are placed in the living environment of the elderly and are used by him/her periodically during the day for measuring vital signs. Specifically, the system presented by [START_REF] Wang | Smart Blood Pressure Monitoring System Based on Internet of Things[END_REF] utilizes an electronic blood pressure device that transmits the measured data (i.e., pulse wave) to the data processing center, from where they are accessible in real-time by a doctor. In a similar way, Cao et al. [START_REF] Cao | An IoT Application: Health Care System with Android Devices[END_REF] developed an IoT system that measures saturation peripheral oxygen and pulse rate, and transmits them to a cloud-side server.

Other solutions use wearable bio-signal sensors that monitor human vital signs continuously. Menychtas et al. [START_REF] Menychtas | Automated integration of wireless biosignal collection devices for patient-centred decision-making in point-of-care systems[END_REF] introduced a mechanism for uniform biosignals collection from wearables and biosignal sensors, and decision support modules for patient monitoring. In [START_REF] Menychtas | On the integration of wearable sensors in IoT enabled mHealth and quantified-self applications[END_REF] a holistic solution for communication and management of Bluetooth biosignal sensors and activity trackers promoting mHealth and self-care is proposed. A glucose monitoring system based on an implantable unit that utilizes Bluetooth low energy, to transmit the measured glucose data to patients' mobile phone or PDA is presented by Ali et al. [START_REF] Ali | A bluetooth low energy implantable glucose monitoring system[END_REF]. Pinto et al. [START_REF] Pinto | We-care: An IoT-based health care system for elderly people[END_REF] demonstrated a platform for monitoring and registering patients' vital information as well as providing mechanisms to trigger alarms in emergency situations by using a wristband equipped with numerous sensors.

The infrastructure proposed in this paper supports the efficient monitoring of the elderly through a combination of heterogeneous devices that provide both human behavior monitoring and measurement of vital signs of the elderly in his/her living environment in a non-intrusive way. It also supports a mechanism that enables the easy installation and testing of the equipment. The collected data are securely forwarded to a cloud infrastructure offering also decision support functionalities to the formal and informal caregivers of the elderly through advanced data analytics and visual analytics.

Proposed solution

Before describing the proposed solution, it is essential to present the end-users of the platform and their needs:

 Assisted person: Elderly people, from 65 year and above, with chronic health problems or with frailty due to physical, cognitive or emotional problems, who need formal or informal support when staying at home or in their daily living environment for safety and security.  Informal caregiver: responsible for providing support on a daily basis to a relative that suffers from a chronic condition and cannot live alone and yet be safe. The service will allow him/her to monitor the relative remotely and respond immediately and effectively in case of an emergency.  Formal caregiver: responsible for providing systematic daily assistant at home or at a daycare center. The service will allow the formal caregiver to coordinate different care recipients at the same time more efficiently as well as respond to different emergency cases faster.

In order to meet the needs of the aforementioned user groups, an IoT infrastructure was designed and implemented, as it is depicted in Fig. 1, which enables devices with sensing, processing and communication capabilities to be connected to the Internet. It is an extension of the three-layered architecture proposed by [START_REF] Azimi | Internet of things for remote elderly monitoring: a study from user-centered perspective[END_REF] where each layer is equivalent to the most basic features of an IoT-based platform: data collection, transmission, and analysis [START_REF] Touati | u-Healthcare system: state-of-the-art review and challenges[END_REF]. The installed devices are connected to the Internet through a gateway, forming a Machine-to-Machine (M2M) network.

A lab-based pilot was used as a reference site to test the proposed infrastructure. Specifically, the smart home of CERTH/ITI was used for living lab testing, providing a fully controllable environment similar to the real cases. The assessment was based on gathering data from different sensors, in which CERTH/ITI employees and a limited number of elderly performed activities of daily living in standardized scenarios. Based on the aforementioned lab-based pilot, the proposed solution produced promising preliminary feedback and results. Fig. 1. The adopted three-layered system architecture

The Perception Layer

The first layer that is named Perception Layer (Fig. 2) is responsible for and collecting information of devices for a user and integrating them into the next layers. It includes a number of heterogeneous, wireless sensors and health devices that create a Wireless Sensor Network (WSN) and a central node is in charge of gathering the sensed data. The central node that is referred as an Aggregation Point in this paper is part of the second layer and is described in detail in the following section. The used devices are using common communication protocols that are featured by low power consumption, short-range communication, and lightweight protocol stack.

The selection of the devices and protocols was made after an in detail examination of the necessities and requirements of the user groups. In particular, these are the protocols used by the selected devices:  Bluetooth standard [START_REF]Bluetooth Standard[END_REF]  Z-Wave [START_REF] Alliance | [END_REF]  ZigBee [START_REF]ZigBee Alliance[END_REF]  RF (869.2-869.25 MHz) All devices are battery operated. Consequently, the sensor placement is not constrained by the availability of a nearby power socket, enabling this way an easy installation phase.

Fig. 2. The Perception Layer that contains all integrated devices

According to [START_REF] Azimi | Internet of things for remote elderly monitoring: a study from user-centered perspective[END_REF], the devices in the Perception Layer can be summarized in two main categories: (1) Body Area Network (BAN) devices, which are on-body devices usually for obtaining user health/activity status, and (2) fixed context devices that are generally installed in the home. In a manner corresponding to this categorization, these are the devices used in the implemented system:  Body Area Network (BAN) devices (transmit on demand) o Wearable panic button: for emergency cases, a panic button is utilized. It is a small, wearable device, which the elderly has on him. Its activation results in the device automatically transmitting an emergency alarm notification to the carers of the elderly. o Health device for vital signs: this device is able to measure the vital signs of the elderly, such as the blood pressure and pulses or the blood glucose levels  Fixed context devices (transmit data on an event basis or as periodic reports)

o Passive InfraRed (PIR) sensors: by installing Passive Infrared (PIR) sensors in each room, it is possible to track the presence and motion of an elderly in the home and trace occupancy habits. o Magnetic contact sensors: the central entrance of the home is equipped with a magnetic contact sensor that transmits a signal that indicates the binary state of "open" or "closed". o Sensor for measuring hazardous levels of CO: one of the most common symptoms that patients with early stages of Alzheimer's or dementia have is the frequent and progressive memory loss [START_REF] Small | What we need to know about age related memory loss[END_REF].

Forgetting to turn off one of the devices that are usually located in the kitchen may turn hazardous for the elderly. By installing this sensor, it is able to determine if there are dangerous levels of CO in the home.

The Gateway Layer

The second tier is the Gateway layer (Fig. 3), which receives all sensor data and measurements of the perception layer and then transmits them to the third layer. For this layer, a smart device named Aggregation Point is used that undertakes the data aggregator role in the home environment and enables the communication/connection between all installed devices/sensors. It is equipped with a variety of transceiver modules that enable the communication with the devices through the aforementioned protocols, and it features an IoT platform that is responsible for their integration and orchestration. The supported IoT platforms are:

 universAAL [START_REF] Hanke | universAAL -An Open and Consolidated AAL Platform[END_REF], which is an open source platform that enables seamless interoperability of devices, services and applications on an unprecedented scale.  IoTivity [START_REF] Subash | IoTivity -Connecting Things in IoT[END_REF], which is an open source software framework enabling seamless device-to-device connectivity.

All data collected by the end-devices are forwarded to the Internet, and specifically to the Cloud Layer described in the next section. This is accomplished through an ADSL router or a mobile router (3G/4G) in cases of homes that do not have an ADSL connection.

The communication protocol used for the transmission of the sensed data to the next layer is the message queuing telemetry transport (MQTT) connectivity protocol and its selection was based on the work produced by Campo et al. [START_REF] Campo | MQTT in AAL systems for home monitoring of people with dementia[END_REF]. Its simplicity and the fact that it does not need high CPU and memory usage make this protocol ideal for the interconnection between the Gateway Layer and the Cloud Layer. Moreover, it supports an extensive variety of different devices and mobile platforms, and it provides TSL/SSL security at transport layer [START_REF] Asim | A Survey on Application Layer Protocols for Internet of Things (IoT)[END_REF].

Additionally, a mechanism for easy setup and testing of the installed equipment in the smart home by the installer is provided through a web-based application supported by each Aggregation Point. In particular, the aforementioned web-based application supports the configuration of the Aggregation Point for the communication with the Cloud Layer and provides forms for describing and registering the devices/sensors. It communicates with the IoT platform installed on the Aggregation Point via RESTful services exposed for identifying the communication protocol to be used, and handling the pairing and the communication with the devices. The following main functionalities are supported by this application:

 Device registration for adding and describing a new sensor/health device.  Device removal for removing a sensor/health device from the smart home ecosystem  Device discovery by querying the registered devices, along with details regarding their capabilities.  Device update for updating information related to a device, e.g. change device password.

Fig. 3. The Gateway Layer that is responsible for the aggregation of the sensed data

The Cloud Layer

The third layer is the Cloud Layer (Fig. 4) that incorporates a cloud-based software architecture that collects the information gathered from the sensors installed in each home and provides the two following functionalities: (1) storing collected information and (2) analyzing this information and providing a decision support mechanism through advanced data analytics & visual analytics to the end-users.

For example, the motion sensors are stored in the various rooms of the elderly home and automatically recognize the traceability of each home space. The information transmitted is properly analyzed in order to automatically recognize user habits within a home (e.g. how often he/she visits the bathroom, when he/she visits the kitchen, and for how long, etc.). Recognizing the habits of the elderly contributes to the automatic detection of risk-bearing situations (e.g. the elderly has not visited the bathroom during the day) as well as changes in habits that may be related to health problems (e.g. while the elderly used to be in the kitchen for one hour every noon to prepare his/her daily meal, this custom has changed).

Moreover, the door opening and closing detector that is placed in the central entrance of each home automatically identifies the entrance / exit of the elderly from the house. This information, combined with the information provided by the home-based motion detectors, is properly analysed to identify the user's habits (e.g., how often he/she exits the house, for how long, etc.) and consequently contribute to the automat-ic detection of risk situations (e.g. the elderly has not exited home for a long time) as well as changes in habits (for example, a change in the number of the weekly exits and the duration).

The special panic button, which the elderly always has on him, can be used in an emergency case (e.g. fall, severe dizziness, sickness, etc.). At the click of the panic button, the person (s) indicated by the elderly (e.g. relatives, health personnel, etc.) is informed in order to contact with him/her and take appropriate action for help provision. Similarly, an alarm notification will be created in case the blood pressure or blood glucose levels indicate abnormal vital signs.

Regarding the security of the accumulated data, anonymization and encryption techniques are applied. Data anonymization preserves privacy by eliminating identifiability from the dataset, i.e., the link between sensitive information and people, while encryption protects the confidentiality of the data and prevents unauthorized third parties or threat actors from accessing them. Finally, further research is currently made in order to make the platform compliant with the new General Data Protection Regulation (GDPR) [START_REF]General Data Protection Regulation (GDPR[END_REF], which will come into force on May 2018.

The data accumulated is accessible to two different types of users, for whom the following applications have been implemented:  Application for helping carers (both formal and informal) monitor the health status/activity of the corresponding elderly through advanced data analytics  Application for offering monitoring and decision support to the administrator of the infrastructure through advanced data analytics.

Conclusion

There is a major researching movement that explores various ICT arrangements in order to enhance healthcare provision by mobilizing the potential of IoT. In this paper, we exhibited a smart-home IoT infrastructure created for monitoring the health and activity status of elderly individuals in their living environments. For supporting the independent living of older adults in their living environments and providing perceived safety, a set of heterogeneous sensors, able to provide behavioural and environmental condition information, was utilized in addition to health devices, used for vital sign measurement. The installation and the efficient set up of these devices are feasible through a web-based application implemented for the corresponding personnel. All the aggregated data are collected in a transparent way by the IoT infrastructure deployed in the home and stored securely in a cloud-based infrastructure, where they analysed. The outcome of the analysis is advanced data analytics & visual analytics presented to the formal and informal caregivers, thus providing them with a decision support mechanism. The platform will be additionally tested and evaluated through large-scale pilots that will take place in three different regions of Greece, in the context of the ACTIVAGE project. In these pilots, the platform will be deployed in 500 homes and it will provide activity and health status monitoring of elderly people living autonomously in real life scenarios. Inputs from these pilot sites will enable the further evaluation and refinement of the platform.

Fig. 4 .

 4 Fig. 4. The Cloud Layer that is responsible for the storing of the information collected from all sites

Acknowledgement

This work is supported by the EU funded project ACTIVAGE (H2020 -732679)


Panagiotis Gourgaris
email: gourgaris@ceid.upatras.gr

Andreas Kanavos
email: kanavos@ceid.upatras.gr

Nikos Karacapilidis

Vassilis Tampakas
email: vtampakas@teimes.gr

Argumentative Discourse Concepts as revealed by Traversing a Graph

Keywords: Argumentation, Collaborative Decision Making, Graph Database, Knowledge Graph, NoSQL

Recent advances in computing and Internet technologies, together with the advent of the Web 2.0 era have resulted in the development of a plethora of online tools, such as forums and social networking applications, which offer people an unprecedented level of flexibility and convenience to participate in complex argumentative discourses of diverse interest. However, these tools do not enable an intelligent analysis of the related content. Aiming to address this issue, this paper presents preliminary work on the exploitation of Neo4j graph platform for managing well-established argumentation elements. The proposed high level and scalable approach facilitates the discovery of latent and arbitrarily long and complex argumentation in argument graphs, as well as its meaningful exploitation towards gaining insights.

Introduction

Argumentation is ubiquitous in our everyday life. It might be argued, that every action can be modeled, up to an extent, as an argumentative discourse [START_REF] Perelman | The new rhetoric[END_REF]. An array of examples of various importance and complexity can be pointed out: political and rhetoric argumentation, business negotiations, as well as questions such as "which movie shall we watch tonight", "which car should I buy", and so forth. All these are manifestations of an argumentation discourse.

This paper presents preliminary work on the exploitation of Neo4j for managing argumentation related data. Neo4j, a NoSQL graph database, stores data physically as a graph. Starting here from the notions portrayed in Dung's works [START_REF] Bondarenko | An abstract, argumentation-theoretic approach to default reasoning[END_REF], [START_REF] Dung | On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games[END_REF], [START_REF] Dung | Dialectic proof procedures for assumptionbased, admissible argumentation[END_REF], [START_REF] Dung | Computing ideal sceptical argumentation[END_REF], we try to map the various argumentation elements and their relations to a graph which is dynamically constructed during a discourse. Taking into account diverse argumentation concepts and approaches, our formalization elements are those described in the Hermes system [START_REF] Karacapilidis | Computer supported argumentation and collaborative decision making: the HERMES system[END_REF]. Although here, instead of a tree, we loosen up the architecture and consider the whole issue formulation problem as a continuously expanding graph, following the generally accepted notions in argumentation. Given a knowledge graph formulated as an argumentation framework, we examine the possibility of a graph theoretic route that would yield some quantitative results.

Neo4j supports Cypher, a declarative, ASCII art, and pattern based query language for handling conceptual graphs. We try and relax the restrictions imposed by Dung's model for argument sets, in hope of finding a way to quantitatively assess the process of collaboratively formulating the understanding of an issue and reaching consensus. We aim to check whether the relaxed argumentation forms that we will use give a more probabilistic nature to argumentation acceptance and the assent of any issue considered. By including the human factor, our approach by design engulfs notions that we see in the value-based argumentation frameworks propositions and the labeling process for examining argument attacks.

Motivation & Contribution

Although the overall argumentation process does not necessarily consider large data sets, the rapid development of web technologies and social networks have resulted in the creation of a big volume of content. Opinions, emotions, ideas and thoughts can be extracted in order to explain, assist, and even predict human decision making. The Big data challenge lies in the efficient implementation of a framework for extracting large amount of data from the social media and adopt appropriate methodologies to process them. We can succeed in this by employing a Neo4j server and populating a graph database. The need for new database approaches, that goes beyond the relational one, was highlighted with the advent of Web 2.0, which is dominated by high volumes of unstructured or semi-structured and high order data. Those data can provide the knowledge on which computer formulated notions from argumentation theory like dialogues, value-based argumentation frameworks, argument schemes etc. can rely and give solutions.

The most commonly used tools for knowledge sharing cannot be considered deliberation tools. The problems they face are systemic, like signal-to-noise ratio, redundancy, repetition and balkanization. The main result is not having any debate and low quality of knowledge being spread, although one could contend that this was not their initial goal.

The remaining of this paper is organized as follows. Section 2 presents existing research and background topics on argumentation notions. Section 3 provides a description of Neo4j's basic elements. Section 4 discusses the proposed approach about how the knowledge graph should be created during the deliberation. Section 5 gives a road-map of challenges and comments on limitations of deliberation systems and Graph Databases. Finally, Section 6 provides concluding remarks and sketches our future work directions.

Argumentation Concepts

In this section we provide a description of some basic argumentation notions which sparked our study. Their direct relation with graph databases is what made us try and devise a deliberation schema based on a graph database backend.

To start with, an argumentation discourse as a process towards reaching consent over a difference of opinions, has four discussion stages as portrayed in [START_REF] Van Eemeren | A Systematic Theory of Argumentation: The Pragma-Dialectical Approach[END_REF] Although these stages seem to have a logical ordering, a discourse need not pass through all of them -at least not explicitly-and not in this particular order. These stages could be easily matched with the diverse processes of deliberation systems; for example, threads in internet forums.

A finer structuring of the elements making up argumentation is enabled through Pollock's theory [START_REF] Pollock | Defeasible reasoning[END_REF] for defeasible reasoning. Reasons -called arguments, by argumentation theorists -can be attacked by others, hence the use of the adjective defeasible. The main issue risen is when the argument is attacked. Or, in other words, in which way is it attacked? Pollock argues that two types of defeaters exist, namely rebutting and undercutting.

1. Undercutting argument: those attacking the connection of an argument and its conclusion. This is knowledge obtained that attacks the acceptance of the reason supporting a conclusion. 2. Rebutted: a reason supporting the opposite conclusion.

The work done by Dung [START_REF] Dung | On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games[END_REF] is where argumentation relates most with graph theory. Notions as argumentation framework, conflict, relation are explained in his paper. Specifically:

An argumentation framework is a pair

AF = A, attacks
where A is a set of arguments and attacks is a binary relation defined on A. A framework can be represented as a directed graph G = (V, E). A graph G consists of a set of vertices V and a set of edges E. Just like in an argumentation framework, the set of edges correspond to a set of pairs of vertices by means of a relation. Hence, for a set A = {a, b, c}, (a, b) denotes a attacks b.

As a starting point for a deliberation system in which a discourse can be unravelled, we use notions from Hermes [START_REF] Karacapilidis | Computer supported argumentation and collaborative decision making: the HERMES system[END_REF]. Its framework is based on IBIS (Issue-Based Information System) . The argument diagramming takes form through a framework consisting of issues, alternatives, positions, and constraints.

1. Issues: the problem to be solved. 2. Alternatives: the possible solutions to the problem. 3. Positions: the arguments as seen in Dung; they support or attack an alternative. 4. Constraints: a way to quantitatively weigh reasons; they have the form of a rule (position 1 , pref erence relation, position 2 ) with relations taking a value of "more(less) important than" or "equally important".

Neo4j Graph Database

Our work aims to build innovative tools that give an overall view of dataintensive and cognitively-complex discourses, while also efficiently handle the diversity of requirements concerning their analysis and meaningful interpretation. By having such a roadmap, one can assess all dialectical rules and constructs. Fallacies and impediments which contradict the whole process can be more evident; and in the end, reaching a solution regarding the issues at hand [START_REF] Toulmin | The Uses of Argument[END_REF], hopefully could become a lot easier. By using a graph database, one can store relationships between data. This unique characteristic makes them ideal for our purposes.

To our knowledge, Neo4j has not been used for such an endeavor. Examples of use cases include real-time recommendation systems, social network analysis, network and IT operations. It provides production grade front-or back-end social graph storage. Moreover, it offers graph analytics similar to link prediction, shortest paths, clustering coefficient, and minimum spanning trees, bolstering the potential of graph tools including NetworkX, machine learning frameworks like Graphlab, and distributed processing systems such as Spark [START_REF] Panzarino | Learning Cypher[END_REF], [START_REF] Robinson | Graph Databases[END_REF]. In a context where (i) data are highly connected amongst them, (ii) relationships are often created, erased and updated, and (iii) relationships are the elements that actually trigger insights, graph databases are the solution to handling the big data as well as the real-time aspect of today's deliberation systems.

The fundamental units that form a graph are nodes and relationships. In Neo4j, both can have properties. Entities of a domain are represented by nodes, albeit relationships can be used too, depending on the formulation and domain of the problem. In addition, multiple labels can be attached to nodes. The nature of the questions we want to answer, based on our data, will define the various structures of our graph.

Neo4j's data model is similar to the entity relationship diagram. Concretely, nodes can be considered as the entities in the graph. So, for example in the statement "Panos and Andreas are friends and Panos owns a Brand1 car with plate number AF-101 and Andreas owns a Brand2 car with plate number BD-101", Panos, Andreas and the cars are all distinct entities, hence will be distinct nodes in our graph.

Labels state the role of a node making them essentially the entity type identifiers. As an excellent paradigm for the statement above, we can locate two labels for nodes, person and car.

Relationships are any interactions between nodes, usually identified as verbs. They are considered to be directed and have a start node and an end node. In our example statement, those would be friend of and owns.

Properties are attributes of nodes and relationships. They are key-value pairs attached to them, helping us to quantitatively answer questions regarding our database. In these settings, the "Panos" node which is labeled as a person, can have a set of properties like name : P anos, age : 35. Also the relationship friend of can have a pair of since:MM/DD/YYYY as its property.

Again, we can easily see that depending on the problem (or domain), the same statement might yield a different data model. For example, although in our previous analysis the plate numbers could simply be a property of nodes labeled as car, in another approach specific license plates could be nodes themselves.

The way we put all this to use is through the Cypher language, which was built grounded on the simple SQL clauses and has lots of graph domain additional ones. A simple occurence for our little dataset above could be: match (p:Person)-[:FRIEND]->(f:Person) where p.name='Panos' return f.name which would return all names of nodes that the Panos node has a relationship of F RIEN D. The basic idea is that initially one forms a math statement which will return a subgraph and then applies an action on it. Another example is: match ()-[:FRIEND]->()<-[:FRIEND]-(f) return f.name which would return the names of all nodes that have a relationship of type F RIEN D with some common node. Considering this from an argumentative perspective, these could be two arguments a,c attacking the same argument b, which could constitute an "accrual of reasons".

Proposed Schema

In this section, we present our approach for a schema that could work as a knowledge graph for a Collaborative Decision Making system. We will be using argumentation elements based on those of Hermes [START_REF] Karacapilidis | Computer supported argumentation and collaborative decision making: the HERMES system[END_REF], in following put them in a Neo4j's context, and finally try to address the problem formulation task. We will be presenting the elements and notions using graph lingo.

Our scheme has three types of nodes and four types of relationships. All relationships (edges) in Neo4j are directed. Incidentally, if a node u points to a node v, then u is a child of v and v is a parent of u.

Nodes

The types of nodes used in the present schema are issues, alternatives and arguments.

Issues, here noted as S j , are equivalent to standpoints (the problem being debated). In Hermes [START_REF] Karacapilidis | Computer supported argumentation and collaborative decision making: the HERMES system[END_REF], they refer to decisions to be made; in this paper, we prefer keeping a more argumentative perspective for notations, as this mental disposition helps with the rest of our descriptions. Issues can also be parents for other issues.

Alternatives, here noted as C i , are children nodes of issues. An alternative is a proposition, considered to be a potential solution to the parent issue.

Arguments can be children of both alternatives and issues. Depending on the relationship between two arguments, a new issue can be automatically raised.

Relationships

We have four types of relationships depending on their start and end node.

Relationship H between an alternative C i and an issue S j :

C i H S j , with H {ALT ERN AT IV E T O}
Relationship Ω between an argument a or an issue S k and an issue S j :

{a, S i } ΩS j , with Ω {RAISES} Relationship Υ between an argument a and another one b: a Y b, with Υ {REBU T S, U N DERCU T S} Relationship X between an argument a and an alternative C i : a X C j , with X {AT T ACK, SU P P ORT } Some characteristics of the above relationships are:

1. All relationships are non symmetric. 2. A rebuttal automatically raises a new issue. We consider it to be a new issue and view it as a new dispute that needs to be resolved through negotiations. 3. Also, when an argument a rebuts another b, then the two must have opposing relationships with their common alternative parent. So:

if (a, AT T ACK, Ci)and(a, REBU T S, b), thenwemusthave(b, SU P P ORT, Ci).

4. Upon the creation of a rebutting relationship, a new issue S j concerning it as well as the relationship (a, RAISES, S j ) is created.

Example

Figure 1 illustrates the main Neo4j web interface. The graph depicted in Figure 1 is more clearly shown in following Figure 2. There, a draft example of a simple argumentation over the question "Should I buy car Model1 of Brand1?" is considered.

In addition, two alternatives are presented, namely "Yes" and "No". These two alternatives often correspond to two different opinions. Another user supports "Yes" with an argument "Low price compared to others". After that, an argument rebutting it ("Very expensive for what is provides") is expressed and a new issue with the title "Price comparison" is created. Likewise, we see that the argument "Engines of Model1 from Brand1 burn oil" supports "No", while another, arguing "Engines of Model1 since 2008 are fixed", undercuts it. While not fully visible in this simple example, we will be forming our argumentation map with the dialectic systems in mind. Although the time aspect of time-centric systems might be considered by others to generate non-structured data, it is the authors' opinions that it could be an asset, adding to the knowledge that can be obtained from the graph.

Roadmap

Towards implementing a deliberation system having Neo4j as its backbone, numerous problems and issues need to be addressed. In such systems, one has to bear in mind the human factor as well as the mechanics of how data are produced. The World Wide Web can be seen as an ideal platform for enhancing argumentative communication and collaboration, due to its ubiquity and openness. Personal blogs and unstructured or semi-structured online discussion forums can provide a medium for such communication.

Notwithstanding opinions and discussions may be identified by their topics, time, or participants, there is a lack of fine-grained structure that captures the way that different facts, opinions, and arguments relate to one another and, as such, contribute to the overall picture. An example is considered in [START_REF] Davies | An online environment for democratic deliberation: Motivations, principles, and design[END_REF], where Deme is specifically designed for supporting democratic, small to medium-sized group deliberation.

By far, the most used systems are those that formulate the deliberation process via sharing content also known as time-centric systems, e.g. wikis, blogs, forums and emails. Data is most commonly in the form of free text and the way people create content does not give a structured result. The size and creation processes of data are the main reasons of problems such as duplication, balkanization as well as the very low signal-to-noise ratio. Also, the only two valid ways of handling the plethora of data and any redundancy as a result, is to either impose restrictions prior to making any post publicly available -perhaps if designated members moderate discussions, or to manually assess all data after the knowledge database is created; in either way, the amount of human labor can become enormous.

A number of highly-structured argument-based deliberation support systems (ADSS) have been already proposed. These suffer from two key limitations: first, they usually support a small number of participants; in addition, most of them target specific domains, such as education, or academic research. Moreover, highly-structured ADSSs based on client-server architectures, are usually designed for small to medium-sized groups and are therefore not easily scalable [START_REF] Gordon | An open, scalable and distributed platform for public discourse[END_REF].

Another limitation of existing structured ADSSs is that they subscribe to specific theories of argumentation and decision-making. While the majority of these systems may be suitable for specific domains, an outstandingly truly globalscale argumentation infrastructure must allow for a variety of reasoning patterns to spark interaction. Such reasoning patterns are known in argumentation theory as argumentation schemes [START_REF] Walton | Argumentation Schemes[END_REF]. By incorporating such methodologies, the noncollaborativeness problem with large scale tools [START_REF] Klein | Enabling large-scale deliberation using attention-mediation metrics[END_REF] can be efficiently addressed.

Authors in [START_REF] Rahwan | Laying the foundations for a world wide argument web[END_REF] present theoretical and software foundations for a World Wide Argument Web (WWAW). Concretely, WWAW can be considered as a largescale Web of inter-connected arguments posted by individuals to express their opinions in a rather structured manner. ArgDF, a pilot Semantic Web-based system is presented, through which users can create arguments using different argumentation schemes and can query arguments using a Semantic Web query language.

Conclusions & Future Work

We have presented preliminary work on the exploitation of Neo4j for managing argumentation related data. As future work, we intend to enhance the framework in order to perform meaningful numeric evaluations. More specifically, we will examine whether all types of nodes can have such capabilities. Furthermore, we will try to address several issues that deliberation systems face; heavy dependency on manual moderating work -either during or after the system launch -has to be thoroughly tackled. A very good example regarding this issue is the user incentives of Stack Overflow 1 . In addition to reputation votes, there are about 90 badges a user wins for completing milestones.

Another addition to our framework concerns the argumentation structures [START_REF] Craven | Argument graphs and assumption-based argumentation[END_REF]. This could help arguments being posted in order to be regarded more as evidence rather than as simple bias, thus adding to the overall credibility of the system. The ultimate goal after dealing with these issues would be the development of an online argumentation platform for generic, large-scale deliberating purposes [START_REF] Gürkan | Mediating debate through on-line large-scale argumentation: Evidence from the field[END_REF].

Fig. 1 .

 1 Fig. 1. The web interface of Neo4j administrator panel.

Fig. 2 .

 2 Fig. 2. A simple example of deliberation.

1

  https://stackoverflow.com/