A K Choudhury School

A K Choudhury

Materialized View Construction Based on Clustering Techniques

Keywords: Materialized View, Clustering, Jaccard Index, Attribute Similarity Matrix, Weighted graphs

Materialized view is important to any data intensive system where answering queries at runtime is subject of interest. Users are not aware about the presence of materialized views in the system but the presence of these results in fast access to data and therefore optimized execution of queries. Many techniques have evolved over the period to construct materialized views. However the survey work reveals a few attempts to construct materialized views based on attribute similarity measure by statistical similarity function and thereafter applying the clustering techniques. In this paper we have proposed materialized view construction methodology at first by analyzing the attribute similarity based on Jaccard Index then clustering methodology is applied using similarity based weighted connected graph. Further the clusters are validated to check the correctness of the materialized views.

Introduction

The motivation to create materialized view is to ensure the availability of frequently accessed data such that the query execution takes place faster. A key measure to quantify the merit of materialized view is to compute the hit ratio. It is defined as the ratio of hit to the materialized view divided by the total numbers of requests/queries to the database system. Hit means in this context, availability of data in the materialized views to successfully answer the queries. Over the time numbers of researches have been carried out to form the materialized views based on different methodologies. In this section we focus on some of the useful techniques to form materialized views. Materialized view formation is often employed in database system as well as data warehouse and OLAP systems.

Query rewriting [START_REF] Hu | Research and Application of Query Rewriting Based on Materialized Views[END_REF] is way to optimize query execution in materialized views. Extended query rewriting algorithm [START_REF] Hu | Research and Application of Query Rewriting Based on Materialized Views[END_REF] on join relation with foreign key, studied query system based on materialized views has been performed. However [START_REF] Hu | Research and Application of Query Rewriting Based on Materialized Views[END_REF] work fine with small databases. Regarding query writing, group-by plays an important role both in database and data warehouse based applications. Group-by returns a modified, abstract view of the existing database. It is very much in data warehouse applications as it corresponds to roll-up operations. Group query based on Materialized View Santanu Roy Ranak Ghosh Soumya Sen (GQMV) [START_REF] Guodong | A modifying strategy of group query based on materialized view[END_REF] accelerate the searching process making full use of the star schema and the materialized view technology, and combining the concerns of group bond and the technology of materialized view. Different traditional methodologies like genetic algorithm, simulated annealing are applied to form materialized views. M.Lee et. al.

proposed an efficient solution towards speeding up query execution using genetic algorithm [START_REF] Lee | Speeding up materialized view selection in data warehouses using a randomized algorithm[END_REF]. This genetic algorithm [START_REF] Lee | Speeding up materialized view selection in data warehouses using a randomized algorithm[END_REF] based approach explores the maintenancecost view selection problem in the context of OR view graphs. It performs better over the existing heuristic approaches. The problems with the greedy or heuristic approach fail are that, those fail to select good quality of materialized views in high dimensional data set. Simulated annealing based randomized view selection approach [START_REF] Vijay Kumar | Materialized View Selection Using Simulated Annealing[END_REF] select top-k views from multidimensional lattice which is useful in cube based data warehouse applications. Furthermore the simulated annealing approach has been upgraded further to incorporate parallel simulated annealing (PSA) to select views from an input Multiple View Processing Plan (MVPP) [START_REF] Derakhshan | Parallel Simulated Annealing for Materialized View Selection in Data Warehousing Environments[END_REF]. The extended scheme of parallelism [START_REF] Derakhshan | Parallel Simulated Annealing for Materialized View Selection in Data Warehousing Environments[END_REF] helps to work with multiple views and thousands of queries. As the numbers of queries grow into a system often the dynamic creation and modification of materialized views are high in demand. A dynamic cost model [START_REF] Bazlur Rashid | Dynamic Materialized View Selection Approach for Improving Query Performance[END_REF] was proposed based on threshold level incorporating the factors like view complexity, query access frequency, execution time and update frequency of the base table to select a subset of views from a large set of views to be materialized. Another work on dynamic materialized view [START_REF] Phan | Dynamic Materialization of Query Views for Data Warehouse Workloads[END_REF] finds the workload permutation that produces the overall highest net benefit. A genetic algorithm [START_REF] Phan | Dynamic Materialization of Query Views for Data Warehouse Workloads[END_REF] based approach was used to search the N! solution space, and to avoid materializing seldom-used Materialized Query Tables (MQT), those are pruned. The methodology dynamically manages the workload to get benefit over existing methods.

In some of research work on materialized views it focus on certain application areas.

Here we consider few XML applications as XML is widely used in web applications. Answering XPATH queries using multiple materialized views is relatively a new problem, traditional methods work with one materialized view in XML applications.

An NFA based approach called VFILTER [START_REF] Tang | Multiple Materialized View Selection for XPath Query Rewriting[END_REF] to filter views that cannot be used to answer a given query. Furthermore based on the output of VFILTER a heuristic method was proposed to identify a minimal view set that can answer a given query. An interesting problem in XML domain is to handle keyword queries. Materialized views could be used to solve the problem. The concept of Smallest Lowest Common Ancestor (SLCA) [START_REF] Liu | Answering Keyword Queries on XML Using Materialized Views[END_REF] was adopted for query result definition. It [START_REF] Liu | Answering Keyword Queries on XML Using Materialized Views[END_REF] identifies the relevant materialized views for a given query and develops an algorithm to find a small set of relevant views that can answer a query. Materialized views are often needs to be defined over data cubes in OLAP applications. Exact and appropriate functional dependencies and conditional functional dependencies (CFD) are redefined over previous summarization techniques such as condensed and quotient cubes [START_REF] Garnaud | Functional dependencies are helpful for partial materialization of data cubes[END_REF]. This results in storage reduction however ensuring query performance. This also takes care whenever data is inserted or deleted from fact table (corresponds to base cuboid) materialized views are accordingly maintained. In another approach, materialization of cuboids is experimented on QC-tree which is most commonly used structure for data cubes in MOLAP. Though QC-tree achieves high compression ratio, still it is a fully materialized data cube. An algorithm was proposed in [START_REF] Li | PMC: Select Materialized Cells in Data Cubes[END_REF] to select and materialize some of the cells where as traditional methods require all the cells. Modern day database system majorly run on relational databases and the corresponding OLAP application is called ROLAP. In relational model data is represented in the form of table and every table consists of attributes. The attributes within the table are functionally co-related. The analysis on the attribute affinity gives an idea of relationship among them. An analysis on attribute relationship is depicted in [START_REF] Sen | A New Scale for Attribute Dependency in Large Database Systems[END_REF] where a numeric scale is constructed to enumerate the strength of associations between independent data attributes. However [START_REF] Sen | A New Scale for Attribute Dependency in Large Database Systems[END_REF] don't propose any methodology to construct materialized view. In another research work linear regression [START_REF] Ghosh | Materialized View Construction Using Linear Regression on Attributes[END_REF] is used to measure the inter-association among attributes and this knowledge is used to form materialized view. The drawback of [START_REF] Sen | A New Scale for Attribute Dependency in Large Database Systems[END_REF] and [START_REF] Ghosh | Materialized View Construction Using Linear Regression on Attributes[END_REF] is that both compute attribute relationship as a pair (two attributes) and this knowledge is guiding materialized view construction process. In this research work this drawback is identified and thus, after computing the pair wise relationship among attributes, materialized views are formed as cluster after analyzing the association among all the attributes. The different clusters are treated as different views, but however these views are further tested for validity. Among the created clusters, the clusters which are found to be valid by statistical analysis represent the final set of materialized views.

Proposed Methodology

In previous section a survey work was carried out to describe different methodologies of constructing materialized views and identifying the drawback, a new technique of materialized view creation is proposed here based on attribute similarity and formation of clusters using weighted connected graphs.

The similarity function that is used to measure similarity between attributes is the Jaccard Index. Here the set of attributes along with the set of queries form a categorical data set in which each attribute can be treated as a categorical variable. There are few well established similarity functions to compare the similarity .between categorical variables. Here the Jaccard Index [START_REF] Satu | Survey on Graph Clustering[END_REF] is used to measure the similarity between the attributes. Based on the similarity between attributes a novel weighted graph based clustering algorithm is proposed to construct the views. Similar attributes are grouped together to form every cluster. To form the cluster pair wise attribute similarity is considered but each of these clusters is not considered as materialized views immediately. The validity of is these clusters is checked by considering the similarity of every cluster member with all other members within a particular cluster. Only the valid clusters represent materialized views. At first based on m queries and the participating n attributes in the m queries, Attribute Usage Matrix (m× n) is formed. From the Attribute Usage Matrix the attribute similarity is carried out here using Jaccard Index. After the similarity calculation between attributes the n× n Attribute Similarity Matrix is formed. In the Attribute Similarity Matrix all the values which are greater or equal to a cut-off aver-age similarity value are considered for the construction of graphs to form the clusters.

For each of these similarity values a set of weighted connected graphs are constructed. Every graph represents a cluster where the intra cluster members are tied together by a particular similarity function value. After the creation of the clusters they are tested for validation process. Here the similarity between each possible pairs of attributes within a cluster is calculated and accordingly the average similarity measure for each cluster centroid is calculated. After this step only the valid clusters are considered to be the materialized views.

Definition of Jaccard Index

The Jaccard Index measures similarity between two attributes expressed in vector form and is defined as the size of the intersection divided by the size of the union of the two vectors. So, if A i and A j be two attributes then similarity between them is calculated as J (Ai , Aj ) = ( A i ∩ A j ) / (A i ∪ A j ) (Equation 1) A i ∩ A j = Total number of occurrences where both (A i ) n and (A j ) n = 1, A i ∪ A j = Total number of occurrences where either any one or both (A i ) n or (A j ) n = 1; [(i ≠ j) are the attribute indexes and n is the query index]

Relevance of Using Jaccard Index for Attribute Similarity Calculation

Measuring similarity or distance between two data points is a core requirement for several data mining and knowledge discovery tasks that involve distance computation.

Here too the similarity between the pair of attributes is needed to be measured. The more similar or lesser distanced attributes are said to have greater affinity between themselves. For continuous data sets, the Minkowski Distance is a general method used to compute distance between two multivariate points. In particular, the Minkowski Distance of order 1 (Manhattan) and order 2 (Euclidean) are the two most widely used distance measures for continuous data. However it is not possible to directly compare two different categorical values where the values are not inherently ordered. In this scenario one way to compare the variables is to express each of these categorical variables in the form of vectors with multiple dimensions. Jaccard similarity is particularly used in positive space, where the outcome is neatly bounded in [0,1]. Here in the Attribute Usage Matrix output is either 1 or 0. Moreover in the attribute usage matrix every attribute is treated as a vector. Here the different queries form the dimensions and the attribute usage values of different queries are the value of each dimension corresponding to any attribute. Say, Q= {Q 1 ,Q 2 ,Q 3 } be the set of queries. The attribute usage values corresponding to A i is say, [1,0,1]. So in the attribute usage matrix A i is represented as [1,0,1] which forms a vector suitable for comparison with other attributes using Jaccard Index.

2.3

Components of Proposed Methodology

Attribute Usage Matrix: An m×n binary valued matrix in which the value of each entry denoted by use (Aj, Qi ) is either 0 or 1. Let Q = {Q1,Q2,….Qn}be the set of user queries (applications) that will run on relation R(A1,A2,…An). Then, for each query Qi and attribute Aj, Attribute Usage Value, denoted by use(Aj , Qi) is defined as use (Aj , Qi )=1 if attribute Aj is referenced by query qi , else use (Aj , Qi )=0.

Attribute Similarity Matrix: Attribute Similarity matrix is an n×n matrix, each element of which is the similarity measure J (Ai, Aj) between any two attributes Ai and Aj according to equation 1. The diagonal elements in this matrix are similarity between the same attributes as i = j. So in the diagonal elements' #' is placed.

Cut-off Average Similarity:

The similarity values between any pair of attributes range between [0, 1]. The average similarity value is 0.5. In this paper this value is chosen as the cut-off similarity value between any pair of attributes. This cut-off similarity is to be considered as an important parameter for the cluster formation and validation process. This cut-off value actually regulates the number of possible clusters and also number of attributes present as the members in a cluster. The value could be fixed to any value between 0 and 1, based on application.

Construction of Connected Graphs From Attribute Similarity Matrix:

A set of disjoint connected weighted graphs are constructed from the Attribute Similarity Matrix. In each of these graphs G i , the attributes represent the nodes and for any pair of attributes (A i , A j ) which are expressed as node A i and A j in the graph, the Jaccard Index Value J (A i , A j ) between them is the weight of the edge connecting them. The method of construction of connected graphs is stated as below: a) At first all the similarity values which are greater or equal to Cut-off Average Similarity are identified. If no such value is found then graph construction process fails and therefore no views can be constructed whereas if some values are found they are inserted in a list L in descending order. So each element in L is a similarity measure value.

b) The number of elements in L is stored into a variable count. Starting from the first element (The highest Similarity value between any pair of attributes) each element is popped out until the list L is empty and for each element step c is repeated. c) All the attribute pairs that have the similarity value equal to the currently popped out value from L are identified in the Attribute Similarity Matrix. After that each pair of the identified attributes are included as nodes in graph G i (1≤ i ≤ count). Graph G i is a connected weighted graph where every edge has the same weight values and is equal to the currently popped out similarity value from L. For example let the popped out similarity value form L is x (0 ≤ x ≤ 1) which is the similarity measure between A i and A j . Then an edge of weight x is inserted between A i and A j in graph G i. Similarly if the similarity between A j and A k is x, an edge is inserted between A j and A k . As A j is a common node for similarity value x, so A i , A j & A k form a connected weighted graph G i.

d) If there are n number of similarity values in the Attribute Similarity Matrix which are greater or equal to the cut-off value then n number of connected disjoint graphs will be formed where each G i (1≤ i ≤ n) represents a graph for a particular similarity value.

Formation of Clusters From Connected Graph:

Each connected graph G i is treated as a cluster C i , where the nodes (attributes) of graph G i are the cluster members. If there are n numbers of graphs then n number of clusters will be formed.

Average Similarity Value For Each of the Cluster Centroid:

a) The Average Similarity Value is a measure of similarity of every attribute with all other attributes present in a particular cluster. If there are n number of attributes present in a particular cluster, then for any cluster C i the Average Similarity Value for its centroid

(C i ) avg = ∑ J(A i ,A j ) � n 2 � i=1 � n 2 �
where i≠j (Equation 2)

The numerator of equation 2 gives the total similarity value for all possible pair of attributes inside cluster C i and the denominator gives the number of possible combinations that can be made by taking 2 attributes together (Attribute-pair) from n number of attributes. So, equation 2 actually gives a measure of average similarity between all pairs of attributes inside a cluster, which is the average similarity value for that cluster centroid.

Importance of Average Similarity Value for Cluster Centroid:

The Jaccard Index J (A i , A j ) gives the measure between any two attributes. Say from the Attribute Similarity Matrix it is found that J (A i , A j ) = J (A j , A k ) ≥ cut-off. So according to the graph construction method A i , A j & A k belong to a cluster C i .The graph construction method considers similarities between the pair A i , A j and A j , A k but does not consider similarity between A i and A k . A i and A k might be very dissimilar yet they are present in a single cluster. Hence the similarity between A i and A k should also be considered.

If the cluster centroid average similarity is calculated then it gives the measure of association of any attribute with all other attributes present in that cluster. So if A i and A k are very dissimilar their similarity measure J (A i , A k ) will be very small. This value will make a very small contribution to the overall value of (C i ) avg . Obviously the value of (C i ) avg will be less for this. If the cluster centroid average similarity is less then it means the intra cluster members don't have higher association between themselves. Therefore C i will not be a valid cluster. (A 4 ,A 6 ),(A 4 ,A 5 ),(A 5 ,A 9 ),(A 5 ,A 11 ) ,(A 6 ,A 11 ) and (A 9 ,A 11 ) were not drawn and hence their weights were not considered in the graph construction method. Since each weight between the pair of nodes is the measure of association or similarity between the attributes. This fact is taken care of in this step.

If complete graph with all the possible edges and their weights is drawn it would look like Fig 2. Step 2) for relevant data] We find that only for cluster C 5 the cluster centroid average similarity is less than cutoff .So, C 5 is rejected and the valid clusters are C 1 , C 2 , C 3 and C 4 . Since every valid cluster is treated as a materialized view, so finally we have 4 materialized views created for the given database: View-1 (A 5 , A 10 ), View-2 (A 9 , A 11 ), View-3 (A 6 , A 12 ) and View-4 (A 4 , A 5, A 6 , A 9 , A 11 ). In the proposed clustering algorithm the numbers of desired clusters is unknown at the beginning. There is no need to predefine the desired number of clusters. Secondly, the validation process of each cluster considers the cluster centroid similarity measure only and does not require any shifting between inter cluster members. After validation either a cluster is considered to be valid or is rejected. The valid clusters form the materialized views. In this way the proposed weighted graph based clustering algorithm outperforms k-means algorithm.

Performance of the Proposed Clustering Algorithm

Conclusion & Future Work

The paper contributes to the formation of materialized views using clustering technique. The existing techniques worked with pair wise attribute association only and at no stage considered the association or similarity of multiple attributes at a time. This research gap is identified in this paper and a method is introduced which measures the similarity function of every attribute with all other attributes present and this knowledge guides the construction of materialized views in the forms of cluster. Further a method is introduced which measures the quality of the materialized views in terms of intra attribute association. Only those views which have a predefined intra attribute association are therefore considered as the final materialized views. This clustering based methodology may be further extended in distributed environment where the data servers are physically located in different geographical location. The proposed methodology need to be upgraded to consider access frequency of different queries at different sites, network bandwidth etc. to address the constraints of distributed systems. Apart from using the Jaccard Index the formation of distributed materialized views can also be done using other established similarity functions like Cosine Based Similarity and Tanimoto Coefficient. A comparative study of these methods and simulation in distributed environment would help to choose the appropriate methods for constructing materialized views.

Fig. 1 . 4 :

 14 Fig. 1. Graph G 4 where the weight value of each edge is 0.571428571According to the algorithm, each graph is treated as a cluster. As 5 graphs are constructed so, 5 clusters (C 1 , C 2 , C 3 , C 4 and C 5 ) are formed from them. Hence after step 3, the set of materialized view C contains:C = {C 1 = (A 5 , A 10 ), C 2 = (A 9 , A 11 ), C 3 = (A 6 , A 12 ), C 4 = (A 4 , A 5, A 6 , A 9 , A 11 ), C 5 = (A 2 , A 5 , A 6 , A 7 , A 8 , A 9 , A 10 , A 11 )}.Step 4: The average similarity value (C i ) avg for each of the cluster centroid is calculated as: (C 1 ) avg = 0.833333, (C 2 ) avg =0.714285714, (C 3 ) avg = 0.666667, (C 4 ) avg = 0.5011905 and (C 5 ) avg =0.411918 (Calculated according to equation 2)Explanation of cluster centroid average similarity calculation: Let's consider the calculation of cluster centroid average similarity for cluster C 4 . In fig.1only the edges which had weights 0.571428571 were drawn and a connected graph G 4 was formed between the nodes A 4 , A 5, A 6 , A 9 and A 11 . The edges between

Fig. 2 . 2 � = � 5 2 �

 222 Fig. 2. Modified graph G 4 with all possible pair of nodes connected Cluster C 4 has 5 attributes (n=5), hence � n 2 � = � 5 2 � =10. The similarity values between all pair of attributes inside cluster C 4 are taken from section (4.Step 2) and rewritten below: (A 4 ,A 5 )=0.375,(A 4 ,A 6 )=0.428571429,(A 4 ,A 9 )=0.571428571,(A 4 ,A 11 )=0.571428571,( A 5 ,A 6 )=0.571428571,(A 5 ,A 9 )=0.5,(A 5 ,A 11 )=0.333333,(A 6 ,A 9 )=0.571428571,(A 6 ,A 11 ) =0.375,(A 9 ,A 11 )=0.714285714. The Total (∑ J(A i , A j ) (10) i=1 ) of the above values = 5.011905. The average (C 4 ) avg = (5.011905 /10) = 0.5011905 (From equation 2). Similarly for cluster C 5 (n=8), (C 5 ) avg can be calculated as (C 5 ) avg = Total /� 8 2 � = (11.53371 / 28) =0.411918. [Refer to section (4.Step 2) for relevant data] We find that only for cluster C 5 the cluster centroid average similarity is less than cutoff .So, C 5 is rejected and the valid clusters are C 1 , C 2 , C 3 and C 4 . Since every valid cluster is treated as a materialized view, so finally we have 4 materialized views created for the given database: View-1 (A 5 , A 10 ), View-2 (A 9 , A 11 ), View-3 (A 6 , A 12 ) and View-4 (A 4 , A 5, A 6 , A 9 , A 11 ).

K

  -means algorithm is most widely used clustering algorithm in different applications. The major drawbacks of the k-means clustering algorithm are: a) Number of desired clusters are predefined. However in this problem domain the numbers of clusters or materialized views can't be fixed. b) There is a continuous shifting of cluster members to form the final valid clusters. This increases the time and computational complexity of the algorithm.

Proposed Algorithm

Input: R(A 1 ,A 2 ,…A m ) : The relation; Q ={Q 1 ,Q 2 ,…Q n } : The set of user queries that will run on R; cut-off: Cut-off Average Similarity. Output: C: The set of materialized views.

Step 1: Construct the m×n Attribute Usage Matrix where m is the number of attributes and n is the number of queries.

Step 2: Construct the n×n Attribute Similarity Matrix from the Attribute Usage Matrix. /* In step 3 the Graphs & the corresponding clusters are constructed*/ Step 3: ∀ (A i , A j ) ∈ Attribute Similarity Matrix, identify the attribute pair similarity values so that J (A i , A j ) ≥ cut-off. Store these values in a list L in descending order. Store the number of elements in L into a variable count. a) If count=0 then go to step 5. /* The algorithm fails to draw any graph. Therefore no materialized view can be constructed */ b) If count > 0 then Repeat until list L is empty i) Pop the i th (1≤ i ≤ count) element from L. Store the value of the element into a variable x ( 0

Illustration by Example

Let us consider a small example set of queries. This is only for the sake of a lucid explanation of the steps to be followed in the proposed algorithm Say, there are ten queries (Q 1 , Q 2 , …. ,Q 10 ) in the set which use 12 different attributes namely (A 1 , A 2 ,…….,A 12 ). The queries are not given here due to space constraint, the example is shown starting from Attribute Usage Matrix.

Step 1: The use of these 12 attributes, by these 10 queries is shown in the Attribute Usage Matrix (Table 1) .If Attribute A 1 is considered we can say A 1 is used by query Q 2 ,Q 4 and Q 7 .So in vector from A 1 can be expressed as A 1 =[0,1,0,1,0,0,1,0,0,0].

Step 2: The similarities J (A i , A j ) between each pair of attributes If the similarity between A1 and A2 is considered we find the value is 0.166667. Explanation: From the Attribute usage Matrix we find that A 1 = =[0,1,0,1,0,0,1,0,0,0] and A 2 = [0,0,1,0,1,0,1,0,1,0]. This connected weighted graph is constructed for similarity value 0.571428571, where the nodes are A 4 , A 5, A 6 , A 9 and A 11. The edge weights between (A 4 , A 9 ), (A 4 , A 11 ), (A 5 , A 6 ) and (A 6 , A 9 ) are all 0.571428571.


Paramita Sarkar

Ditipriya Sinha
email: ditipriyasinha87@gmail.com

An Approach to Continuous Pervasive Care of Remote Patients based on Priority Based Assignment of Nurse

Keywords: pervasive, context data, fuzzy rules, dynamicity, wearable sensor, hash key

Remote care of patient is now becoming a subject of major concern in healthcare services. Proposed work describes a pervasive system to assist continuously the patients who are at remote place from the connected hospital using a priority based classification and assignment of nurses to the high risk patients. The challenge lies in storage and management of the vast amount of real-time data originating from heterogeneous sources under dynamic situations. This paper attempts to design a new system consisting of several modules for managing real-time heterogeneous data. The overwhelming data could cause difficulty to decide over numerous patients to whom the care should be given first and then onwards. To solve this, the proposed system attempts to derive fuzzy rules to make decision based on priority among selected groups in a dynamic environment. This proposed model formulates an indexed hash key for high risk patients and proper nurse relatively.

Introduction

Pervasive Computing is nowadays a growing research topic to improve the quality of remote healthcare service. It integrates seamlessly different heterogeneous technologies without user"s awareness and intervention for the sake of user"s benefit. Emerging ubiquitous or pervasive computing technologies offer "anytime, anywhere, anyone" computing by decoupling users from devices. Context information used in pervasive environment provides adequate information regarding the changes occurred in any characteristics of users, place, and any event. This paper involves remote patient monitoring integrating body sensor network devices [START_REF] Ullah | A Study of Implanted and Wearable Body Sensor Networks[END_REF][START_REF] Lo | Body sensor network -A wireless sensor platform for pervasive healthcare monitoring[END_REF] that can upload a patient"s real time contextual physiological information through a wrist worn wearable sensor device and a personal Smartphone for triggering risk alarm and dissemination to professional caregivers. Dynamic context are handled here by measuring automatic changes during a prolonged time and by mapping them into a predefined group. Some context data changes every second, and some every hour due to their dynamic nature.

Recent advancement of pervasive computing has led increased accessibility to health-care providers, centralized database storage, telemedicine services. Due to the growth in the number of chronically ill and weak people, it is becoming more difficult to take care of the patients in a central place. Therefore continuous monitoring of a remote patient in a pervasive way avoids the presence of a number of medical staff all-time at the patient"s place. When the numbers of victims overwhelm the number of medical staff in a hospital in any emergency event, there are many challenges issues need to ration the medical staffs with proper assignment to patients [START_REF] Jacobson | Priority Assignment in Emergency Response[END_REF]. Here this works attempts to search an appropriate nurse based on the computed hash key [section 4 .3]. Continuous monitoring of patients from a remote hospital is highly desirable to take care of patients and providing suitable guidelines with proper medicine [START_REF] Mirkovic | Framework for the development of ubiquitous patient support systems[END_REF]. This paper includes heart rate variability as a new vital sign [START_REF] Malik | Heart Rate Variability, Standards of Measurement, Physiological Interpretation, and Clinical Use[END_REF][START_REF] Norton | Cardiovascular Risk Factors and Heart Rate Variability in an Older Cohort[END_REF] with other existing parameters. The design of proposed model inherits different existing real time systems for continuous monitoring [START_REF] Boano | Accurate Temperature Measurements for Medical Research using Body Sensor Networks[END_REF], [START_REF] Anliker | AMON: A Wearable Multiparameter Medical Monitoring and Alert System[END_REF]. On the other hand, it develops a prioritised decision making using fuzzy inference and assignment of appropriate nurse to remote patient.

Related Work

In recent years lots of research, work and study in the related field have been carried out. A study of the review in this field revealed that several context aware pervasive system have been used regarding the services in emergency responses in rescue system, public healthcare system, other patient monitoring and alarm system, etc. This section is categorised into following subsection on the basis of real time implementation of pervasive computing.

Priority Assignment

Prioritized emergency operation plays an important role in remote healthcare services and evacuation system a lot. "Priority Assignment in Emergency Response" [START_REF] Jacobson | Priority Assignment in Emergency Response[END_REF] is one of the application of priority assignment in pervasive environment. It formulated the priority assignment problem for each patient in triage system where each patient is evacuated from the mass casualty site to the hospital according to the priority set to them. This paper analysed the state dependent partial optimized policy and proposed a number of heuristic policies. Another "User-driven design of a context-aware application: an ambient-intelligent nurse call system" [START_REF] Ongenae | User-driven design of a context-aware application: an ambient-intelligent nurse call system[END_REF] focuses on the reasoning context data by the caregivers from various ambient sensors in the patient"s room to answer a call from the patient. This paper describes the priority based of the proper nurse to the patient on the basis of the relation with patient.

Knowledge Representation in Cloud Database

It becomes crucial to store such huge and heterogeneous sensor real time data in a large database with proper representation and semantics of huge knowledge. Cloud computing is an obvious solution to access this large database from anyplace anytime in pervasive domain. "An approach for pervasive homecare environments focused on care of patients with dementia" [START_REF] Bastiania | An approach for pervasive homecare environments focused on care of patients with dementia[END_REF] uses the ontology OWL [START_REF] Bechhofer | Owl web ontology language reference[END_REF] for homecare environment in pervasive system to represent the various relationships among domains and knowledge in the database implementing Semantic Web Rule Language (SWRL) and Semantic Query-Web Enhanced Language [START_REF] Horrocks | SWRL: a semantic web rule language combining OWL and ruleML[END_REF]. "Ontology for Context-Aware Pervasive Computing Environments" [START_REF] Chen | An Ontology for Context-Aware Pervasive Computing Environments[END_REF] discussed the solution to the limitation of that problem using the architecture of the centralized pervasive context aware distributed system named as Context Broker architecture (CoBrA) which is a collection of different ontology (COBRA-ONT).

Continuous Monitoring in Pervasive environment

For continuous monitoring of disable/older people and other patients in pervasive environment it is desirable to detect whether they have any risk factor or not. Several researches and designing approaches were performed to detect fall in recent few years [START_REF] Dı´az | Preliminary evaluation of a full-time falling monitor for the elderly[END_REF][START_REF] Hwang | Development of Novel algorithm and realtime monitoring ambulatory system using Bluetooth module for fall detection in the elderly[END_REF]. "Evaluation of a threshold-based tri-axial accelerometer fall detection algorithm" [START_REF] Bourke | Evaluation of a threshold-based tri-axial accelerometer fall detection algorithm[END_REF] derives the threshold level for the fall detection. Different Body Sensors were developed for collecting and transmitting patient"s physiological data for vital sign and activity recognition. "Human Activity Surveillance based on Wearable Body Sensor Network" [START_REF] Kantoch | Human Activity Surveillance based on Wearable Body Sensor Network[END_REF] has proposed the advantages of a Body Sensor Network based architecture for wearable wireless monitoring system using an algorithm optimized for real time computing. To measure the impact of temperature as sleep deprivation in a human body "Accurate Temperature Measurements for Medical Research using Body Sensor Networks" [START_REF] Boano | Accurate Temperature Measurements for Medical Research using Body Sensor Networks[END_REF] proposes a prototype of a body sensor network. Another vital sign of human body is heart rate/pulse rate. "Designing Heart Rate, Blood Pressure and Body Temperature Sensors for Mobile On-Call System" [START_REF]Designing Heart Rate, Blood Pressure and Body Temperature Sensors for Mobile On-Call System[END_REF] paper describes the comparative study between different techniques and design issues for measuring heart rate, blood pressure and temperature. This paper focuses the different parameter used in measuring the vital signs of human body using ECG sensors and the Photoplethysmography (PPG). An unobtrusive method in "AMON: A Wearable Multiparameter Medical Monitoring and Alert System" [START_REF] Anliker | AMON: A Wearable Multiparameter Medical Monitoring and Alert System[END_REF] proposes the architecture and design of a miniature system for measuring heart rate using ECG, blood pressure, activity recognition and SpO2 for continuous monitoring high risk of cardiac and respiration patients. This system is optimized to collect vital signs of human body and evaluate these parameters continuously for communication through a gateway to the external database.

Scope of the work

To implement pervasive environment in the system, heterogeneous data are needed to be stored in remote server. The state of the art study leads to the observation that not much attention has been paid to any mechanism to maintain heterogeneous real time dynamic data in the database. This proposed protocol describes a pervasive system to assist continuously the patients who are at remote place from the connected hospital using a priority based classification and assignment of nurses to the high risk patients.

Proposed Work

The proposed work is to design a system on the pervasive care environment for remote patient. This system emphasizes on the allotment of a caregiver to the remote patients according to the condition of the patients.

Assumption

 The wearable device analyses and processes every sensor signal in such a way that after every 5 minutes it can send data to the patient"s Smartphone.  Threshold value has been determined for Heart Rate, Blood Pressure, Temperature, Accelerometer (for Activity Recognition, Fall Detection) and Heart Rate Variability [START_REF] Malik | Heart Rate Variability, Standards of Measurement, Physiological Interpretation, and Clinical Use[END_REF][START_REF] Norton | Cardiovascular Risk Factors and Heart Rate Variability in an Older Cohort[END_REF] and [START_REF] Bourke | Evaluation of a threshold-based tri-axial accelerometer fall detection algorithm[END_REF][START_REF] Kantoch | Human Activity Surveillance based on Wearable Body Sensor Network[END_REF][START_REF] Boano | Accurate Temperature Measurements for Medical Research using Body Sensor Networks[END_REF][START_REF]Designing Heart Rate, Blood Pressure and Body Temperature Sensors for Mobile On-Call System[END_REF][START_REF] Anliker | AMON: A Wearable Multiparameter Medical Monitoring and Alert System[END_REF].  The continuous monitoring is attempted as long as the patient"s wearable 4-array sensor wrist band is connected with server through the Bluetooth.  Only the dynamic context data are considered for classification in every 30 minutes.  The priority of a patient is classified into five groups Urgent, High, Medium, and Low, and Very Low depending on the severity of the context data coming from the Smartphone.  Work Constraints: The following work constraints should not be violated during the allotment of the nurse to patients. They are as follows:

1) No nurses will have workload more than 8 hours in a whole day.

2)

More experienced resources in a particular department should be allocated to high priority job.

3)

Expertise of a resource in a particular department should be given preferred most.

4)

Minimum number of working days in a week is 5.

5)

Minimum gap between two shifts is 12 hours.

6)

Maximum number of consecutive days of duties in a week will be 3.

 At the server site, the schedule of nurses for each department and for each day of a week stored in its database. The existing schedule of nurses is updated every 30 minutes inside the server to calculate the remaining duty hours and key value of a nurse.  Weights are provided to represent for the level of importance for each constraint.  The allotment of the nurses is prioritized according to the lower value of the key c.  Two different priority queues are needed for prioritizing the patients and the nurses.

Data Dictionary

 E di = number of experience in years of i th nurse of a particular department say d  H i = total duty hours of i th nurse in a day.  D i = highest qualification of i th nurse in a particular domain related to the particular department  nw i = Minimum number of working day (w) of i th in a week  ng i = minimum gap (g) between two successive shift of duty of i th nurse.  xcd i = Maximum number of consecutive duties (c) of i th nurse in days of a week.  w i = weight factors for i th indices where i=1,2,3,4,5,6.  p_id i = i th patient"s id given by the hospital  threshold ni = corresponding threshold value of n th feature and i th patient  feature_value ni = value of the n th context data of i th patient  num_gr_f ni = associating group numbers to which n th feature of i th patient belongs to.  cnt_gr_f ni = total number of groups to which n th feature of i th patient belongs to.  feature_priority ni = priority of n th feature of i th patient  gr_id i = group id of i th feature  gr_mem i = feature_name of n th patient in the i th gr_id  p_hr i =Heart Rate of i th patient, p_bp i = Blood Pressure of i th patient,p_acc i = of accelerometer data i th patient, p_temp = temperature of i th patient, p_hrv i = Heart Rate Variability of i th patient.  p_arr_time i = arrival time of a sensor data of i th patient

Table 1. Database Record Table

Record

Field Name Patient"s record {p_id i, p_name i, p_age i, p_gen i, p_dept i, , p_date i , p_temp i, p_bp i, p_hr i, p_acc i, p_hrv i , p_curr_medicine i, p_pri i , p_arr_time i , p_allot_status i , n_p i ,p_rel1 i ,p_rel2 i ,p_med i ,p_app_dr i } Nurse"s Record {n_department i , n_id i , n_name i , n_age i , n_exp i , n_prof_degree i , n_date_duty i , n_dhalf i , n_totalhr i , n_allot_status

Definition

Definition 1. Indexed Key defines-the minimum key is defined to search the appropriate nurse from the database without avoiding all work constraints is defined as the total cost function:

C = E di × w 1 + H i × w 2 + D i × w 3 + nw i × w 4 + ng i × w 5 + xcd i × w 6 (1)
w i [Section 4.2] is in the range from 1 to 6 according to the value of six indices, such that if a nurse has highest experience in a particular department (E di ), the weight factor w i for that constraint will be 1. This minimum cost function will be treated as the key for index in the hash function.

Definition 2. The hash function is required to search proper nurse_id from the hash table . A hash function of key is hash(key) = key % hash table size

(2

)
where key is defined as total cost function C. Searching will be performed based on the indexed key such that the hash function of that key would probably returns the location of the key value of the corresponding nurse.

Definition 3.The difference_f ni is defined as the difference between the threshold of a particular feature n of i th patient.

difference_f ni = |(threshold ni -feature_value ni )| (3)
This value will be computed in the computation module inside the server at the time of arrival of every context data.

Proposed Pervasive remote patient care with proper nurse Assignment model

In order to assist this work, a proposed model of the system"s architecture is implemented at the server of the particular hospital. The server communicates with the Smartphone of the patient and the nurse through GSM. The proposed model can finally generate an assignment of appropriate nurses to high risk remote patients on the basis of the proposed priority inside the classification model. Figure 1 shows architecture of the proposed model inside the server. The proposed system has four connected parts labelled here as COMPUTATION MODULE, DATA MODULE, CLASSIFICATION MODULE,SCHEDULING MODULE, and UPDATATION MODULE.

Table 2. List of Abbreviation used in the Figure 1. if difference_f ni ≠ 0 [Equation ( 3)] then, difference_f ni will be inserted in the patient"s record [Section 4.2]and will be updated in the data module. Otherwise, the context data of i th patient will be discarded. Thus the Computation module reduces the size of the database. Finally it sends the updated records to the classification module for further processing.

No. Abbreviation Meaning

Module II: Data Module.

Inside the server there will be separate database to store records of all patients, nurses, doctors, context features, their group, nurse"s schedule and for key with hash function for every nurse. A database of fuzzy inference mechanism is attached in this Data Module.

 Fuzzy rules are stored in the separate database of this module. From this database classification module will be able to infer the priority of the patient.  For this architecture there is also a record of five contextual health data [Section 4.2]. These are the most vital sign to decide the health risk of a patient.

Module III: Classification Module.

Phase 1: Checking dynamicity of realtime contextual data. In every 5 minutes patients" record at the hospital will be updated by the coming data. then Set feature_status i = "dynamic" send feature_value i in data module 4. Else save the old feature_value i Fuzzy Sets for "priority". In the proposed system, "priority" is defined as a linguistic variable to x. Linguistic variable are termed as x, F(x), U and M. F(x) is termed as the set of x, the set of names or linguistic values assigned to x, with each value is a fuzzy variable defined in U. M is membership where semantic rules are associate with each variable [START_REF]Artificial Intelligence Application in Construction[END_REF]. T(priority) = {low, very low, high, medium, urgent}.U = {-α, + α}. M defines the membership function of each fuzzy variable for example, M(very low)= fuzzy set priority below 20% with membership of µ very low . The M (low) and M (high) are expressed as µ low and µ high respectively.

𝜇 𝑙𝑜𝑤 (𝑥) = 1/ 1 + (𝑥/20) 4 (4)

𝜇 ℎ𝑖𝑔ℎ (𝑥) = 1 1 + 𝑥 -+𝛼 /20 6 (5)
Concentration and Dilation of fuzzy membership function. M (Urgent) = µ urgent (x).

Not low not high means M (medium) = µ medium (x). Low but not too low means M (medium) = µ medium (x).

𝜇 𝑢𝑟𝑔𝑒𝑛𝑡 𝑥 = 1 1 + 𝑥 -+𝛼 /20 6 0.5

(5)

𝜇 𝑚𝑒𝑑𝑖𝑢𝑚 (𝑥) = 𝑚𝑖𝑛 1 1-1 1+ x 20 4 ; 1 - 1 [1 + x-+α 20 6 ] (7)
𝜇 𝑚𝑒𝑑𝑖𝑢𝑚 𝑥 = 𝑚𝑖𝑛 1. After the allotment of the available nurses, Set p_alott_status i : = "yes" and n_alott_status i : = "yes"

2. The patient will receive a NOTI_MSG_p from the remote server about the allotment, and updated n_id i , n_time i . At the same time, the corresponding nurse will also receive the same alert message N_MSG with updated p_id i and p_add i and updated schedule record. 3. If no available nurse is found then Set p_alott_status i : = "wait". It sends a list of prescribed p_curr_medicine i and app_dr i [Section 4.2] to patient"s Smartphone. 4. N_MSG [Section 4.4.1] are also sent to relatives" smartphone with the same updating for providing better support of this mechanism.

Conclusion

This paper designs the pervasive system to alert the healthcare providers for allotting a suitable nurse to the high risk patients. Some vital signs have been used as contextual sensor data which are continuously gathered and updated at the remote server at a regular interval. The focus of this work is to meet the challenges of existing work in the related field. A priority based classification using fuzzy logic is devised for alerting the health risk of the registered patients of a particular hospital. This work needs to be compared with other prioritized nurse assignment protocol in future so that this work can be validated. A scheduling plan will be generated in dynamic real time environment as well as a proper knowledge representation mechanism will be implemented using Semantic Web Rule Language (SWRL) [START_REF] Bechhofer | Owl web ontology language reference[END_REF] and Semantic Query-Web Enhanced Language [START_REF] Horrocks | SWRL: a semantic web rule language combining OWL and ruleML[END_REF] for generating updated knowledge and rules in huge database. Intelligent and a faster method for group assignment of the context data in the server will also a challenging task for future work.

Fig. 1 .

 1 Fig. 1. Architecture of the Proposed Pervasive care Environment of remote patients

Fig. 2 . 4 . 4 . 5 .

 2445 Fig. 2. Decision Tree architecture for priority assignment for group2 with Heart rate, Blood pressure, and temperature

  Phase 2: Priority Based Classification Algorithm. Group Assignment of specific feature in one or more than one group of clinically related context data has been done. At this phase a priority based classification algorithm is derived using Fuzzy memebership is computed according to the different range and that are assigned to each patient.1) Compute the difference between the received feature_value ni and the threshold ni [Section 4.2] in percentage and that will be stored. 2) Set x ni : = |(difference_f ni / 100)| [Equation (3) ] 3) Set gr_no 1 := [p_h ri , p_b pi , p_ac ci ] in 1 st group. gr_no 2 := [p_h ri , p_b pi , p_tem pi ] in 2 nd group. gr_no 3 := [p_ac ci , p_tem pi ] in 3 rd group. gr_no 4 :=[p_hr vi ] in 4 th group

	1 1+ x 20	4 ;	1 [1 + x-+α 20	6 ]	0.5		(8)
	𝜇 𝑣𝑒𝑟𝑦 𝑙𝑜𝑤 𝑥 = 𝑚𝑖𝑛 1/ 1 + (𝑥/20) 4 ; 1 [1 + x -+α 20	6 ]	0.5	(9)
	[Section 4.1]
	4) if (feature_name i != NULL) then
	a) search its group members using num_gr_f i and cnt_gr_f ni [Section 4.2]
	b) [Initialize counter count for checking in all groups] Set c:= 1
	c) Repeat the following step while c <= cnt_gr_f ni for n th feature in i th group.
	a) Make decision for priority assignment according to the following Decision
	Tree based on the value of x ni .
	b) if |20|<=x ni <=|80| of feature_value ni then, Set feature_priority automatically
	according to the following decision.
	5) Repeat the following steps until the final priority assignment is completed
	and the communication link is active. Let x i is any sensor data of i th patient
	6) if M[x ni ]= µ urgent (x) [Equation (6)] then, Set feature_priority i : = "urgent" and
	p_pri i := 5 Else
	7) if M[x ni ]= µ high (x) [Equation (5)] then Set feature_priority i : = "High" and
	p_pri i := 4 and if ( num_gr_f n !=NULL) then
	a) if all feature_values ni of gr_mem i have x ni is in the range {|50%-80%|} then,
	Set feature_priority i : = urgent | high | medium| low according to the relative group
	b) Else Set feature_priority i : =high | medium | low according to the relative
	group
	8) Else Set feature_priority i : = "High" and p_pri i := 4
	9) Repeat the above steps for all group and for all ranges according to the
	following decision structure.


Seiji Sugiyama
email: seijisan@hr.ci.ritsumei.ac.jp

Daisuke Yokozawa
email: dyokozawa@gmail.com

Atsushi Ikuta
email: a.ikuta@sch.otani.ac.jp

Satoshi Hiratsuka
email: hiratsuka@spice.ci.ritsumei.ac.jp

Susumu Saito

Miyuki Shibata

Tohru Matsuura

Abbreviation Method for Some Jointed Relations in Displaying Genealogy

Keywords: Family Trees, Pedigrees, GEDCOM, WHIteBasE

Introduction

In genealogy on paper media, it is natural to write one individual only once using segment intersections even if there are complex relations that include multiple remarriages with children. This simple rule makes easy to understand all of complex relations at a glance. In contrast, almost all of existing genealogy display software often display one individual in multiple places when complex relations are inputted [START_REF] Sugito | Alliance. news letter of Oceania conference[END_REF]- [START_REF] Naito | Topic Map for Displaying Genealogy[END_REF]. The displaying results cause confusion to understand the correct relations. They consider only simple family trees and have no idea to display complex relations because GEDCOM [22], a de facto standard for recording genealogy data exchange format, considers no layout information.

To cope with this difficulty, new genealogy display software has already been constructed on our previous research by using the WHIteBasE (Widespread Hands to InTErconnect BASic Elements) method [START_REF] Sugiyama | A Study of An Event Oriented Data Management Method for Displaying Genealogy: Widespread Hands to InTErconnect BASic Elements (WHIteBasE)[END_REF]- [START_REF] Sugiyama | Displaying Genealogy with Adoptions and Multiple Remarriages Using the WHIteBasE[END_REF]. The WHIteBasE is a hidden node for integrating relations that include not only a married couple and their children but also information of those positions. As a result, one individual have been displayed only once using segment intersections easily. In addition, not only various layouts such as paper media have been displayed but also intuitive inputs and inspections such as map display systems have been realized.

On the other hand, there is a requirement to abbreviate some jointed relations in genealogy on restrictions of displaying area, or the convenience of explanation. In this case, it is needed that not only the inputted information of relations is maintained but also the users can always find which relations are abbreviated. No software realizes this requirement.

New algorithm for abbreviating a part of relations in genealogy is necessary because all of inputted layouts are always displayed on the WHIteBasE method. In this research, a new method, "Joint ABBReviation for Organizing WHIteBasE (JaBBRoW)", is proposed so that it can solve this problem. The JaBBRoW is a hidden boundary that can organize information of some positions using a square area that is set by user's requirements to abbreviate. Not only the area is movable but also its scale can be compacted and recovered seamlessly by only mouse operations. As a result, arbitrary relations with horizontal and vertical connections in genealogy can be abbreviated easily. Our software that can display genealogy with abbreviation is presented.

WHIteBasE

In this section, the WHIteBasE method that is our previous proposal [START_REF] Sugiyama | A Study of An Event Oriented Data Management Method for Displaying Genealogy: Widespread Hands to InTErconnect BASic Elements (WHIteBasE)[END_REF]- [START_REF] Sugiyama | Displaying Genealogy with Adoptions and Multiple Remarriages Using the WHIteBasE[END_REF] is briefly introduced. A regular family relation between a married couple and their child is managed as an event by a Hidden Node, WHIteBasE as shown in Fig. 1. The connection model of WHIteBasE is shown in Fig. 2. WHIteBasE has three keyholes, S L , S R (Substance) and D (Descendant). Individuals have two keys, A (Ascendant) and M (Marriage). A can connect with D, and M can connect with S L or S R , where denote one family.

For brothers and sisters, D is extended to multiple keyholes D j as shown in Fig. 3. For multiple remarriages, M is extended to multiple keys M k and plural WHIteBasEs are used as shown in Fig. 4. For adoptions, A is extended to multiple keys A l as shown in Fig. 5 where A p , one of A l , denotes ID for handling the biological parents, and the others denote IDs for handling social parents. Fig. 6 shows the regular Japanese layout style. It includes a double horizontal segment MS (Marriage Segment), a vertical segment TS (Trunk Segment), a horizontal segment BSS (Brothers and Sisters Segment), and a vertical segment BS (Branch Segment). The ' ' denotes a male, and the ' ' denotes a female that are a couple connected by using MS. For various layouts, MS is extended to MS, MS v , and MS h named DB (Double Bend), and BSS is extended to BSS h , BSS v , and BSS l named HS (Hooked Segment), as shown in Fig. 7.

A set of W i that defines WHIteBasEs and a set of I j that defines Individual Nodes are represented by

W i = {S L , S R , D j , Q} I j = {M k , A l }        i = 0, 1, • • • , i max j = 0, 1, • • • , j max k = 0, 1, • • • , k max l = 0, 1, • • • , p, • • • , l max (1)
where i, j, k, l and i max , j max , k max , l max denote the IDs and their maximum values on the data table respectively, p denotes the ID for handling a biological parents, S L and S R denote the IDs for handling a couple, D j denote the IDs for handling descendants, M k denote the IDs for handling marriages, and A l denote the IDs for handling ascendants. Individuals are managed by using data table including names and annotation data. WHIteBasEs are managed by using data table separated from Individuals.

A set of Q that defines coordinate values for each position managed by a WHIteBasE measured from the origin in the displaying area is represented by Q = {q b , q L , q R , q d , q cj , q aj , q vl , q vh , q m , q e , q tl , q rb } (2)

where q b denotes the WHIteBasE's position, q L , q R denote the parents' positions, q d denotes a junction's position between MS and TS, q cj denotes children's positions, q aj denotes junctions' positions between BSS and BS, q vl , q vh denote the corners on DB, q m , q e denote the corners on HS, q tl , q rb denote positions of top-left and bottom-right of all area managed by a WHIteBasE, as shown in Fig. 7 and Fig. 8. There are only four kinds of horizontal segments and four kinds of vertical segments in the WHIteBasE method. The positions of segment intersections can be calculated by using only 16 patterns of line crossing as shown in Figs. 9(a)-(p). The half arcs are displayed on the positions of segment intersections. The detailed information has already been written in our previous research [START_REF] Sugiyama | Displaying Genealogy with Adoptions and Multiple Remarriages Using the WHIteBasE[END_REF].

(a) (b) (c) (d) (e) (f) (g) (h) (i) (j) (k) (l) (m) (n) (o) (p)
This algorithm is very fast because it skips when two WHIteBasEs' areas do not overlap. In addition, when adoptions are set, the segment style changes to the dashed segments named AS (Adopted Segment) and the arcs are not used.

One of advantages using WHIteBasE is the decreased reference volume. If the existing software is used, all of individuals connect with other individuals as shown in Fig. 10(a). In contrast, if the WHIteBasE is used, two reference links per a child decrease as shown in Fig. 10(b). Moreover, the users can understand the complex relations intuitively and can input and inspect them easily.

Fig. 11 shows the sample demonstrations by using our previous genealogy display software that can display complex relations with segment intersections automatically and seamlessly by only mouse operation [START_REF]Nerva-Antonine dynasty[END_REF].

Genealogy with Abbreviation

First of all, it is considered what is abbreviation in genealogy. Genealogy with abbreviation has three types as the following:

(A) There is no individual's data to input. (B) Some names and/or generation numbers have to abbreviate. (C) Some relations are abbreviated temporarily after inputting data.

In the case (A), no abbreviation layout is necessary because of no individual's data. In the case (B), intermediate relations are skipped but abbreviation layouts are used because of ambiguous information. In the case (C), abbreviation layouts are used temporarily by user's requirement, and this case is the abbreviation in our research. Note that the cases (A) and (B) are lack of data.

Abbreviation of only individuals' names

Figs. 12(a) and 13(a) show the samples of genealogy with abbreviation of only individuals' names. In these cases, three ' 's in 12(a) and four ' 's in 13(a) are used instead of individuals' names. These abbreviation layouts are the cases that unknown names are displayed by using only ' ' or ' ', and all of existing individuals are displayed. As a result, numbers of the individuals can be found.

To display these abbreviation layouts are very simple. If a switching function between names and symbols such as ' ' or ' ' on the individual's text-box is available, these abbreviation layouts can be displayed easily.

Abbreviation both of generations and brothers and sisters

In the cases of Figs. 12(a) and 13(a), large displaying area is required according to increasing individuals, because all of the existing individuals are displayed. To cope with this difficulty, there is a case that abbreviation layouts of plural individuals are set to one. Figs. 12(b) and 13(b) show the samples of genealogy with abbreviation both of generations and brothers and sisters. ' by using the Japanese Kanji characters that means '(Abbreviation)' or '(Skip)'. Similarly, comparing Fig. 13(a) with Fig. 13(b), it can also be found that four ' 's are changed to the same abbreviation symbol ' (略) '. In these cases, the abbreviation symbols do not display the abbreviated numbers of individuals. As a result, the numbers both of generations, and brothers and sisters cannot be found. In contrast, the space of Figs. 12(b) and 13(b) is wider than Figs. 12(a) and 13(a).

To display these abbreviation layouts are not simple. If the switching function in 3.1 is used, displaying the abbreviation symbol can only be realized. However, two or more than three inputted individuals text-box can not be combined to abbreviate because this function can be used in only one individual.

Abbreviation of Marriages

Fig. 14(b) shows the abbreviation result in the case that the individual with a rectangle as shown in Fig. 14(a) is only abbreviated using the same symbol ' (略) '.

However, seven individuals that are her brothers and sisters and their children and a partner are also abbreviated to one symbol simultaneously. Because this layout around the abbreviated individual has a lot of horizontal relations and vertical relations. As a result, the space becomes wider, however, the number of abbreviated individuals cannot be found.

Problem of the abbreviated symbol

Figs. 15(a)-(c) show the abbreviated patterns for generations. (a), (b), and (c) denote abbreviation of one generation, two generations and three generations respectively. In these cases, all of layouts become the same style using the same abbreviation symbol. It is difficult to find the number of abbreviated generations. If paper media is used, these problems do not occur. On the other hand, if genealogy display software is used, it has to avoid to input the same individual twice. It is necessary that abbreviated individuals can be found continually.

Displaying rule for abbreviation

Genealogy with abbreviation is very difficult because it has not only generations vertically but also marriages and/or brothers and sisters horizontally. To cope with the difficulty, a scale compaction method is proposed to display individuals and segments. The target to abbreviate the individuals' sizes and positions is only compacted. Figs. 18(a)-(c) show the displaying rule for abbreviation. As a result, not only these layout styles look like almost abbreviation display but also information of relations can always be found. In addition, all texts of abbreviated individuals should be non-display because it is not necessary to display texts while abbreviating. The size of compaction should be set freely by user's requirements.

JaBBRoW

Hidden Boundary

This is a new data management method for adding the abbreviation method to the WHIteBasE model. A selected area of genealogy with abbreviation is managed as an event by a Hidden Boundary as shown in Fig. 19(a). The Hidden Boundary can be displayed on the genealogy display area, and it can also be nondisplayed as user's requirements. An arbitrary shape for the Hidden boundary is allowed, but a dotted rectangle is used in this research for convenience of mouse operations, and when the area is compacted, the rectangle becomes solid line as shown in Fig. 19(b). This Hidden Boundary is not the normal selecting area in mouse operation. Once the Hidden Boundary is set, it can be kept until deleting it. As a result, the compacted and recovered operation can always be performed. In addition, all of relations in genealogy can be maintained while compacting, and all of relations in the Hidden Boundary can be scale down to the very small area. The model using the hidden boundary is named "Joint ABBReviation for Organizing WHIteBasE (JaBBRoW)".

Coordinate System in JaBBRoW

Positions of each node managed by one WHIteBasE is measured from the origin in the displaying area using the absolute coordinate system world as shown in Fig. 8. On the other hand, the JaBBRoW is represented by using the moving coordinate system J different from world . They have different scales. The scale of J can be changed to increase/decrease according to the mouse wheel count by mouse operation on the inside of JaBBRoW rectangle. This means that if the mouse position is on the outside of JaBBRoW rectangle, the scale of all genealogy area is changed. e J is defined as the moving coordinate system after scale changing by one count of mouse wheel. This scale changing is set that the increasing rate is 1 0.9 , and the decreasing rate is 0.9 in this research. The compaction using JaBBRoW is defined as the coordinate transformation from J to e J of each node in the JaBBRoW. Fig. 20 shows the coordinate system in JaBBRoW where XY-coordinate system from the left-top origin denotes world , the rectangle 'Before' denotes J , the rectangle 'After' denotes e J . The left-top position on 'Before' is (x c , y c ), its width and height are w, h respectively, the mouse point is (x m , y m ). If the left-top position on 'After' ( x c , y c ) is represented by

x c = x m -(x m -x c ) w w , y c = y m -(y m -y c ) h h , (3)
the JaBBRoW rectangle can be scaled as center on the mouse position, where w, h denote the width and height of 'After' rectangle. In addition, an arbitrary point inside the rectangle 'Before' is (x p , y p ). If the position of the rectangle 'After' ( x p , y p ) is represented by

x p = x c + (x p -x c ) w w , y p = y c + (y p -y c ) h h , (4)
the JaBBRoW rectangle can be scaled in maintaining all of the position relations of each node inside the rectangle. As a result, each node on the JaBBRoW is compacted to the mouse point when compacting, and each node keeps away when recovering. Finally, the position's values of each node can be updated to the next position data in world and the previous WHIteBasE calculation method can be used without changing.

Definition of JaBBRoW Model

The information to manage in the JaBBRoW is a set of coordinate values of each node inside the JaBBRoW. Because the range of JaBBRoW rectangle is set arbitrarily, there is a case that a WHIteBasE is included in the JaBBRoW, and, there is no case. Basically, if the WHIteBasE position q b is not included in the JaBBRoW, the q b is not managed by the JaBBRoW. In contrast, if the q b is included, the coordinate values Q managed by the WHIteBasE is searched whether all of Q is included in the JaBBRoW or not. As a result, computational time can be reduced. JaBBRoW is defined using a set of hyper-graph G represented by

G = ( V, ) (5)
where denotes a hyper-edge given by

= { J 0 , J 1 , J 2 , • • • ∈ V | J i ∩ J j = 0, i = j } ( 6
)
where J k (k = 0, 1, 2, • • •) denote a Hidden Boundary JaBBRoW, each JaBBRoW is a disjoint set, and one node is not managed by plural JaBBRoW. On the other hand, V denotes a set of each node inside the JaBBRoW represented by

V = { V 0 , V 1 } (7)
where V 0 and V 1 denote a set of Individuals and a set of WHIteBasE respectively represented by

V 0 = { I 0 , I 1 , I 2 , • • • , | I j / ∈ J k then I j / ∈ V 0 , k = 0, 1, 2, • • • } (8) V 1 = { W 0 , W 1 , W 2 , • • • , | W i / ∈ J k then W i / ∈ V 1 , k = 0, 1, 2, • • • } (9)
where I j are coordinate values on the world , and W i are coordinate values of only corner points in the WHIteBasE as shown in Fig. 21 represented by W i = {q b , q d , q vl , q vh , q m , q e |q b / ∈ J k then q d , q vl , q vh , q m , q e / ∈ W i , k = 0, 1, 2, • • •} .

(10) As a result, a set of each node inside the JaBBRoW is scaled in each J k . Note that q vl , q vh , q m , q e are not calculated when various layouts are not used.

Registration Procedure to the JaBBRoW

Each node to manage by the JaBBRoW can be given by the following:

1. Add a new JaBBRoW rectangle from the menu of the WHIteBasE software. 2. Select the area to abbreviate by changing the size and position of JaBBRoW. 3. Spin the mouse wheel once to compact on the JaBBRoW rectangle. 4. Register all nodes inside the JaBBRoW rectangle. 5. Change the scale to all registered nodes for compaction. 6. Register the JaBBRoW ID to the all registered nodes. 7. All registered nodes are maintained until the JaBBRoW is recovered. As a result, to register a node twice can be avoided. shows some individuals are approached and genealogy scale is changed to large. In addition, even if JaBBRoW is used, the result of our previous research such as segment intersections and various layouts can be used as user's requirements.

Conclusion

In this research, a new method, "Joint ABBReviation for Organizing WHIteBasE (JaBBRoW)" have been proposed. Genealogy with Abbreviation could be constructed by using the JaBBRoW on our previous WHIteBasE method.

Using the JaBBRoW, an arbitrary area in genealogy can be compacted and recovered seamlessly by only mouse operations maintaining horizontal and vertical connections. It is possible to display a lot of genealogy information in a narrow displaying area because some relations can be abbreviated temporarily after inputting data. Understanding a whole genealogy with both a bird's-eye view in its totality and a detailed view can be easy. This method can give us the legibility of genealogy. Moreover, this idea is applicable also to another displaying matter that relations information has horizontal and vertical connections.

Future research will be conducted to construct automated layouts, generation search, grid layouts, improving GUI, etc.

Fig. 1 . 2 .

 12 Fig. 1. A regular family layout in genealogy Fig. 2. Connection model of WHIteBasE

Fig. 3 .Fig. 5 .Fig. 6 .

 356 Fig. 3. Brothers and sisters Fig. 4. Multiple Remarriages

Fig. 9 .Fig. 10 . 11 .

 91011 Fig. 9. Search pattern of segment intersections for various layouts

Fig. 12 .Fig. 13 .

 1213 Fig. 12. Abbreviation of Generations

Fig. 14 .

 14 Fig. 14. Abbreviation of Marriages

Fig. 15 .Fig. 16 .Fig. 17 .Fig. 18 .

 15161718 Fig. 15. Abbreviation of Generations

Fig. 19 .

 19 Fig. 19. Compacted and Recovered Operation by using the Hidden Node, JaBBRoW

Fig. 20 .

 20 Fig. 20. Coordinate system in JaBBRoW Fig. 21. Managed nodes by JaBBRoW

Fig. 22 .

 22 Fig. 22. Sample of Genealogy with Abbreviation using JaBBRoW

Acknowledgement

This research has received the assistance of the "Shin Buddhist Comprehensive Research Institute, Otani University, JAPAN".


Adrija Bhattacharya
email: adrija.bhattacharya@gmail.com

Avirup Das
email: avirup0310@gmail.com

Sankhayan Choudhury
email: sankhayan@gmail.com

Nabendu Chaki
email: nabendu@ieee.org

Agent-Based Context Management for Service-Oriented Environments

Keywords: context, service discovery, agent programming, search time

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Context plays a very important role in service engineering. The relevance of discovered services is highly dependent on the context from which the service is being searched. Context is described as collection of some parameters {Context Parameter (CP)}, either qualitative or behavioral parameters, and their specific values. The context of a service actually answers some 'wh' questions (Who, Where, Which, etc) and also hold some additional information. In this paper, each context is described as a tuple that represents a specific instance of those parameters. Any change in any of the parameter values indicates the change of context. There are two types of contexts; service context and user's context. Service context is declared at the time of service creation. It is included within the description of services and generally static in nature.

In other words, the services have fixed answers with respect to the 'wh' questions. A single service can have multiple service contexts; i.e., that service can be invoked in multiple specified contexts. Similarly, user's context is about the circumstance under which the user queried or the services would be consumed. User context may be dynamic in nature. However, at a single point of time same service can satisfy multiple user queries with different context requirements.

A service can only be invoked if its service context matches the user's context of the query. Alternatively a service's performance varies over the different user contexts. Thus, to serve users more efficiently (by returning more relevant set of services), there is a need of new context management system. The importance of the system is both in terms of speed of searching and relevance of search results.

There has been some works [8, 9 and 10] that aim to grab the user's context and match with service context. In [START_REF] Mokhtar | Easy: efficient se-mantic service discovery in pervasive computing environments with qos and context sup-port[END_REF] EASY has been proposed which considers only QoS (Quality of Service) parameters as key factor to judge at the time of service discovery and selection. This is held incomplete in the sense of searching more appropriate service according to user's context. The context has more parameters compared to only quality parameters. A graph matching based context aware system is also developed in [START_REF] Kirsch-Pinheiro | Context-aware service selection using graph matching 2nd Non Functional Properties and Service Level Agreements in Service Oriented Computing Workshop[END_REF] that use non functional information to match service and user's context by developing concept graph and their matching. These two methods neither consider all service contexts that can be queried for, nor these methods can identify relations among contexts that could be used further to make searching better. In [START_REF] Rasch | Context-driven personalized service discovery in pervasive environments[END_REF], services are structured by hyperspace analogue to context (HAC) information for identifying the changes in user context and adapt accordingly. This method also failed to consider all valid service context and according user context. This approach [START_REF] Rasch | Context-driven personalized service discovery in pervasive environments[END_REF] is also very application-specific, where changes in contexts are more emphasized.

Agent is an entity which has the property of autonomy, social adeptness, reactivity, pro-activity, mobility and learning capability [START_REF] Nicholas | Applications of intelligent agents[END_REF]. An agent perceives from the environment and act on the environment autonomously as well as independently. Sensing (i.e. perceiving some information from the environment), Reasoning (after perceiving, the reasoning ability of agent takes decisions) and Action (is about actions on the environment to interact autonomously) are basic features of agent [START_REF] Getchell | Agent-based modeling[END_REF]. An agent senses its environments by its sensor. Sensors basically collect information in any form from the environment. An agent determines the current state of the environment based on sensor provided information and takes decision about suitable actions by the reasoning ability. The environment from the perspective of an agent changes continuously. Even the environment may change within the running time of an agent. However, an intelligent agent must have the flexibility to interact with the environment at run time also [START_REF] Wiebe Van Der Hoek | An integrated modal approach to rational agents[END_REF][START_REF] Wiebe Van Der Hoek | Towards a logic of rational agency[END_REF]. Agents can form a community and interoperability among the members of the community leads to achieve a collective goal.

In this paper, a novel framework is proposed for efficient context management and service provisioning. This framework contains a model in the form of a hierarchical structure with some special properties for holding context information. Autonomous feature and the reasoning ability of an agent is exploited and used in the framework for service discovery. Agents generally communicate among them by message passing. This feature helps in finding appropriate matches according to user query by method of backtracking. Sharing of each combination's information within the hierarchical structure at run time is actually needed. Thus, the adaptability feature of agent is also needed in the proposed hierarchical model implementation.

Theory behind the hierarchical structure is discussed in brief in section 2 of this work for the sake of completeness. Section 3 presents a comparative study on agent based architectures. An emphasis is given to justify the selection of BDI (Belief-Desire-Intention architecture) for agent based implementation of the framework discussed in section 2. Section 4 describes the detailed implementation. Section 5 illustrates the performance and finally section 6 concludes.

Proposed Framework for Context Management

In this section we will discuss the proposed mechanism for context management in brief. The motivation behind the research work is discussed in previous section. The framework consists of a model that is nothing but a hierarchical structure. The framework consists of multiple levels. It holds the contexts information in a structured way. Each level contains multiple 'context-node'. Each node may have one or more parents adjacent to the next level. It helps in searching the all options across the levels. Here comes some sense of hierarchy with respect to contexts. Services within a closed domain can be arranged according to their described context within the unique structure. At the time of matching user's context with that of the service; this structure is explored. This is to note that the structure is constructed previously at design time. However, it is explored at runtime, i.e., according to user's query. Figure 1 the structure for three goal levels (1, 2, and 3) and three intermediate levels (0.5, 1.5, and 2.5). It can be populated further. At level-0.5, the contexts are specified by only one context parameter. These nodes are ORed at level-1. There are 3 context-nodes in level-1 and each node has some service and their context information integrated at a point. After that level-1.5 contains three nodes that are basically produced by ANDing level 0.5 nodes. Again level-2 has three context nodes and that are related with the level-1.5 nodes by OR. In each node the contexts are derived by generating combinations of the level 1.5 nodes. Level 2.5 again contains one intermediate node that is produced by ANDing level-2 nodes. Similarly, level-3 has by default only one node i.e. produced by ORing with only one previous level node; this node contains all the common contexts of all previous nodes. This way each level of the hierarchical structure is developed.

The offline formed hierarchical structure is searched based on the context information present in the users query online. Thus the structure of the services formed according to service context information, must be able to match service and user contexts in lesser time. The goal contexts are only at levels (1, 2 and 3). In figure 1context goals are defined by C1 to C7.The efficiency of the service hierarchical structure is that the valid service contexts are readily available in the structure and the hierarchy between consecutive level nodes provisions for switching among levels in case of context mismatch. The structure actually helps to decrease search time and fine tune the search results with various over varying subsets of contexts.

Different Agent Architectures

Reactive, Deliberative, BDI are three broad types of classifications of agent based architectures. Reactive agents only can sense the environment and respond accordingly. It can be easily modeled by if-then-else [START_REF] Wooldridge | Intelligent agents: Theory and practice[END_REF]. It can be called as a lower level abstraction and gives fast response. Deliberative agent architecture consists of deliberative agent sensing the environment and then to decide the next action using logical reasoning and pattern matching [START_REF] Castelfranchi | Deliberative normative agents: Principles and architecture[END_REF]. Actually this act of adaptively is called deliberation and it helps to design complex systems. A very powerful high level abstraction tool for designing and implementing a complex multi-agent system is BDI. It uses practical reasoning to achieve its desired goal. There are three different modules with respect to agents; that are Beliefs, Desires and Intentions. This architecture supports deliberation with means-end reasoning [START_REF] Anand | BDI agents: From theory to practice[END_REF]. Among all of three plans a comparative study has been made to judge the most suitable architecture for implementing hierarchical structure with agent based programming. Table 1 contains the comparisons among three basic agent architectures.

Table 1 clearly states the superiority of BDI architecture with respect to reactive and deliberative agent architecture. The most important factor of BDI is that it enables the multi agent architecture and thus to build a complex structured system like hierarchical structure it held indispensible. At each level of the hierarchical structure there exists an agent. It will not be possible to design with Reactive or Deliberative agent architecture. The plan selection and execution process of an agent is completely sepa-rated and independent which makes it time efficient. The need of hierarchical structure also lies in optimizing the search time that can be possible through BDI. BDI is an event-driven architecture and maintains an even queue. Thus, the user query and each combination search are treated as a new event. All valid contexts are generated. Message passing is another essential feature of agents. Through messages an agent can shares its beliefs, goals and can ask about the situation of another agents which helps to implement hierarchical structure; as in the hierarchical structure if match at one level agent fails then it communicate to its previous level agent. BDI architecture has flexibility to dynamically update its intentions. That helps in implementing the backtracking in match algorithm in hierarchical structure. Due to the important rule that enables BDI agents to derive knowledge from existing knowledge, the Search mechanism is claimed to be efficient enough. There exists a set of BDI languages that supports different internal actions. All of the external features for construction of hierarchical structure as well as exploiting the hierarchical structure based on user query more or less can be mapped by the internal actions of the BDI language actions.

Implementation and Mapping to BDI agents

In general, in BDI architecture an agent consist with four data structures i.e. Be-liefs, Goals, Plans and Intentions. Beliefs are represented the informative part of an agent that defines what an agent knows about the environment and itself. Goals or desires are represented the motivational part of an agent. It defines what an agent wants to achieve. Plans are represented as set of procedural knowledge and decide how an agent can achieve a desired goal. Each agent has a plan library that stores all the plans related to different situations. The plan library is consulted for a specific goal and a set of plan related to the goal is selected. Then the context part of a plan is checked using some expression evaluation and depending on beliefs. A specific plan among the selected set is chosen through the necessary matching of the context part of the plans and it becomes an Intention. If goal is a new arrived goal then the selected intention creates a new intention stack. But for a sub-goal, the selected intention is pushed at the top of the existing intention stack. Only then the Intention stack is selected and executed. It is an event-driven architecture since it maintains an event queue. This queue stores events which are perceived from the environment and subgoals which are generated by executing another Goal as an event. A plan is represented as an event with two parts, a context part and the action part. In this particular agent paradigm the beliefs are basically the constraints of context parameters.

Collectively some beliefs determine a typical context instance. The rest part of an event is singleton; that is an action or subgoal. It looks like,

Event: belief1 & belief2 & …. & beliefn ← actions / sub-goals

Using means-end reasoning an agent decides how to achieve a desired goal and the output of this reasoning are intentions. Here in the implementation of hierarchical structure by BDI agent based architecture, each goal level of the hierarchical structure is considered as agents. The information on context of services is stored in service database. It is mapped into an agent's beliefs and the user query into a goal of an agent. There exists a plan library consisting of different service records with context specifications, based on which the hierarchical structure is constructed offline (i.e., at design time). Now by means-end reasoning (incorporated within BDI) a most suitable step to response the user query is selected. The hierarchical relations among the different values of the same context parameter (CP) are expressed by derived knowledge of the BDI agents. Such as location parameter can take both the values 'Kolkata' and 'Westbengal'. But there exists a relationship among these two: Kolkata is a city in west Bengal. Thus, if a service has location context parameter as 'Westbengal'; it can be invoked from Kolkata also, but the reverse is not true. Again, it helps in backtracking at the time of searching services matching the user context in a query. BDI languages (such as AgentSpeak) give some internal actions like .print, .send, .broadcast which helps us to manipulate the output and messaging. In this implementation .print internal function is used to show the output and .send internal function to send a message from one agent to another agent and .broadcast internal function sends one message to all of the agents at a time. Construction of the hierarchical structure is done mainly based on the two basic operations AND and OR. Agents at each level have information about the context combinations and their details service containment. Each agent is working as a level of abstraction for whole service data registry. In the implementation of the structure, all services in the service repository are represented as a belief of the agents. A service is represented in the belief base with N+2 fields (i.e. Id of the service, Context parameter1, Context parameter2, Context parameter3,…, Context parameter N, Functionality of the service) where N is the no. of context parameters as follows:

ID CP1 CP2 CP3 … CPn Functionality
The following sub section illustrates the design details for service hierarchical structure and search procedures with the help of agent based programming using BDI. Each goal node of the structure contains the services which have the same context parameters as the node have. Services in each node are arranged context wise; this helps in fast context matching and relevant service retrieval.

Basic layout of agent based architecture

The proposed framework is implemented with Multi-agent programming. Here define N+ 1 agent, when the number of context parameters is N. For example, if there are 3 CPs, then 4 agents are defined to handle the whole structure. For the hierarchical structure consisting of 3 CPs (A,B and C) the agents with their functions are depicted in figure 2. Different context parameter combinations generated are A, B, C, AB, AC, BC, ABC. At level-3 all context parameters are present (ABC) altogether. i.e. in this level context is defined by three CPs. In level-2, the responsible agent has information about the nodes in that levee specifies on CP combination. Here context is declared by two parameters at time. In this level there are three nodes (AB, AC and BC). Similarly at level 1 only (A, B and C) three nodes are there representing corresponding context (specified by one parameter at a time). The following subsection detailed out the agent's working algorithms.

Discussion on algorithm for different agents

The algorithm for manager agent and other level agents are described in this subsection. In figure 3 the flow chart for a manager agent is described. When a user query arrives then, at first, the Agent-manager is initialized with the input parameters of the query. Then number of context parameters was declared as variable N. In case of searching at level N, the corresponding agent algorithm differs and becomes complex. An agent at Level N executes for user requested services at that level only. As shown in figure 2, if it fails then the search procedure is routed towards the next lower leve and so on. Similarly in figure 3 the flow of information and how it is all managed by manager agent is described.

In the manager algorithm, at first each of the CPs supplied by user's query is checked. The algorithm goes forward for only the valid CPs. After that the manager agent routes the search to appropriate level agent depending on the number of parameters specified in the query.

Fig. 3. Algorithm for Manager Agent

When the manager agent routes to a particular level agent; the search procedure starts. At first, the dedicated level agent searches according to the values of CP specified in the query. If it fails to find out any services matching user's requirement; it routs the search information to the next lower level agent. Then that agent also searches in the same way and so on. Algorithm for a any level agent is described in figure 4. It works in a generalized way for all level agents. In this algorithm the query CPs are collected and calculated that how many CPs are involved within the query. Then it collects all the services from the required node and checks individual CP specification of services. If the specification is same as in the user's query then the service is chosen as a relevant one. After successful completion of all level agents; the set of retrieved rele- vant services goes to the manager agent. Manager agent then decides and sends the relevant set of service to the user. A few methods and objects are declared in the figure for the sake of easy understanding of the complex algorithm. The definitions of those methods and variables are defined as follows: CP_num: This is an integer value that denotes total number of CPs CP_ sum: This is an integer value. It generates unique sum for each set of CP combination CP_val: This may be any string. It denotes value of each CP. i.e. CP1="c1" CP2="c2" CP3="c3",…, CPk="ck" here all ci's are considered as CP_val CP_com: This is a particular cp combination, i.e., CP1 CP2 CPk-1 Node(X): Node whose CP_sum is X Level (X): It denotes the Level -X Match(X): Here X is a set of CP_val. This method matches each CP_val of query with that of services stored previously. Subcomb(X): X is a CP_com. Subcomb generates all possible sub components having CP_num-1 elements at a time from X. As for example, if X is ABCD then Subcomb will generate ABC, ABD, ACD, and BCD.

Performance analysis

The construction of the hierarchical structure is done offline. Thus the overhead of construction is little. The structure is used for context matching and corresponding set of relevant services for dynamic user query. Complexity of the search mechanism is reduced by generating unique sum of CPs, i.e., in case of searching a particular CP the search procedure instantly finds out the CP combination that is matching with the combination provided in user query. This involves O(n) time complexity where n is the number of NFPs specified in user query.

A multi agent implementation of hierarchical structure is done with the notion of Belief-Desire-Intension architecture. The corresponding language used is AgentSpeak and complied in JASON 1.3.8 [START_REF] Rafael | Programming Multi-Agent System in AgentSpeak using Jason[END_REF]. Each level of the hierarchical structure is managed A multi agent implementation of hierarchical structure is done with the notion of Belief-Desire-Intension architecture. The corresponding language used is AgentSpeak and complied in JASON 1.3.8. Each level of the hierarchical structure is managed by individual agents. An additional agent is responsible for coordinating among different level agents. Table 2 describes the system specifications. This experiment has been worked on almost 3000 Health care services. A portion of the list typically looks like figure 5, which is a snapshot of the partial belief base used in the agent based system. 3). Here each column contains context parameter and corresponding value (from second to eighth column). Each tuple in the table is a query. The functional need of each query is specified by the value at column 1 and the rest is specified as the context. Randomly selected queries were run and a comparative study has been made between usual process and proposed hierarchical match model performances.

Table 3.Sample query set

A comparison between the two has been done in two manners. In first case, the queries are selected randomly from a wide varying query set. In any case our proposed mechanism works better with respect relevance of result. Another side of the comparison is time based. With the increasing size of service population; our proposed mechanism takes less amount of time. Thus the proposed mechanism works in an optimized way with respect to size of service population, wide varying context scenarios and off course for search time. The comparison graph is shown in figure 6. --------------------------------------------------------------Neonatal care "yes" "no" "leg" "high" 1700 1hrs W. Bengal General Medicine "yes" "yes" "leg" "high" 1700 25mins Kolkata Oldcare "yes" "high" 12000 Chennai General Medicine "yes" "high" 9000 1 hrs W. Bengal represent all possible service contexts within its hierarchical structure is proposed. The offered hierarchical structure is built offline and is utilized for finding the most relevant services in terms of user context. The performance of the proposed framework is verified by an exhaustive simulation through agent based approach. As for experiment, the hierarchical structure is populated with service size 3500 and returns results within a feasible amount of time with respect to the existing alternative solutions. The most important contribution of this paper is that it delivers results considering all possible sub sets of CPs supplied in query and that will be beneficiary for the user as it offers the nearest match (may not be the exact match) based on his(her) choice. Thus the proposed framework should be considered to work in more flexible way, compared to their counterparts.

Fig. 1 .

 1 Fig. 1. Hierarchical Context Structure

Fig. 2 .

 2 Fig. 2. Agent architecture and components

Find

Fig. 4 .

 4 Fig. 4. Flow diagram for searching by any level agent

Fig. 5 .

 5 Fig. 5. Snapshot of the Belief-Base

Fig. 6 . 6 Conclusions

 66 Fig. 6. Comparative Performance Analysis

Table 1 .

 1 Comparative study among popular agent architectures

		Agent
		Architectures	Reactive Deliberative BDI
	Features…	…………………………
	Building Complex System	N	Y	Y
	Plan library exists		N	N	Y
	Separation between plan selection and execution	N	N	Y
	Event-driven		N	N	Y
	Simple Communication	N	N	Y
	Supports Multi-agent system	N	N	Y
	Supports Deliberation	N	Y	Y
	Supports Means-end reasoning	N	N	Y
	Supports Deliberation & Means-end reasoning	N	N	Y
	Dynamically changes intentions	N	N	Y
	Multiple desires active simultaneously	N	N	Y
	Strong Negation		N	N	Y
	Rules		N	N	Y
	Failure Handling		N	N	Y
	Internal Actions		N	N	Y

Table 2 .

 2 Specifications of the agent based system

	Specifications	Used components
	Agent architecture	Belief-Desire-intention
	Language used for agent programming	AgentSpeak language
	Complier	JASON ver 1.3.8
	Supported codes written	JAVA with JDK 7
	Form Design	VB 6.0
	Operating System	Windows XP
	RAM size (minimum)	512 MB
	Disk space required (minimum)	40 GB