## 3 Methodology
### uCLUST
#### 3.2.1 Algorithm of uCLUST  
The clustering algorithm _uCLUST_ does two tasks: (1) Formation of linked list, (2) Clustering by traversing the linked list. (A) **Formation of the Linked List**  
_uCLUST_ clusters each record in JSON document based on the categorical attribute present in it, and uses the concept of linked lists to cluster the objects. The _uCLUST_ algorithm gets the clustering attributes as input from the user, and searches the value of the clustering attributes in each record. For each record, it creates a node with fields _recordID_ and the value of the clustering attributes. For example, if image metadata in JSON format is given as input with clustering attributes _type (ANIMAL/ BIRD/ VEHICLE/OTHERS)_ and _format (PNG/ JPEG)_, the node for each record created is shown in Figure 3, which represents a record in the JSON document of the image metadata. In Figure 3, the node holds the unique ID of the record (Image1), the type of the image (ANIMAL) and the format of the image (PNG). If the clustering attribute of a record holds multiple values, then for each value a separate node is created for the same record. After extracting the values of the clustering attributes from each record, the nodes formed is appended together to form a single linked list. Figure 4 shows the linked list for the JSON document of the image metadata. Algorithm 1 details the step for the formation of the linked list in _uCLUST_. (B) **Traversal of the Linked List**  
After the formation of the linked list, the clustering process is done by traversing the list. For each clustering attribute specified, traverse all the nodes in the created list. The first distinct value of the clustering attribute is retained as such in the linked list. Whenever a new distinct value for the clustering attribute is found, the corresponding node is deleted from the original list, and a new linked list is formed for that attribute value. If a value in the node does not occur for the very first time, then append the node to the linked list representing the corresponding attribute value. Each linked list formed after the traversal represents a distinct value of the clustering attribute thus forming the clusters. These clusters group the records with similar metadata. The steps carried out during the traversal of the linked list is shown in Algorithm 2. Figure 4: Linked list formed for the records in JSON document by uCLUST. Figure 3: Node Representation of a record in uCLUST```
Input: JSON document with records; clustering attributes Output: linked list formed with nodes representing each record
1. Create an empty linked list
2.whilenot end of the JSON documentdo  read each record in the JSON document and extract the unique record key;  create a node with the record key field whilenot end of the clustering attributes listdo  extract the value of the clustering attribute ifattribute is single-valuedthen  append the attribute value as the next field to the node created  end if ifattribute is multi-valuedthen  replicate the created node according to the number of values present in the attribute;  append each attribute value to the corresponding node  end if  Append each created node to the linked list  end if  end while
```

**Algorithm 1**Formation of the linked list. ```
Input: created linked list Output: clustered linked list
1.whilenot end of the linked listdo  retain the first distinct node value in the original linked list itself ifnode with next distinct value is foundthen ifthe distinct value occurs for the first timethen  create a new linked list representing the value in the node else  append the node to the linked list representing the value present in it  end if  delete the node from the original linked list end Output all the linked lists created end
```

**Algorithm 2**Clustering by traversing the linked list.