ART2 Clustering of Multiple Web Objects for Qualitative Web Prefetching

ABSTRACT

The web resources in the World Wide Web are rising, to large extent due to the services and applications provided by it. Because web traffic is large, gaining access to these resources incurs user-perceived latency. Although the latency can never be avoided, it can be minimized to a larger extent. Web prefetching is identified as a technique that anticipates the user’s future requests and fetches them into the cache prior to an explicit request made. Because web objects are of various types, a new algorithm is proposed that concentrates on prefetching embedded objects, including audio and video files. Further, clustering is employed using adaptive resonance theory (ART)2 in order to prefetch embedded objects as clusters. For comparative study, the web objects are clustered using ART2, ART1, and other statistical techniques. The clustering results confirm the supremacy of ART2 and, thereby, prefetching web objects in clusters is observed to produce a high hit rate.

Introduction

The advance in Internet technologies has increased the number of web resources to a greater extent. To utilize the web resources effectively, quick web search in addition to response for user request is decisive. User-perceived latency occurs due to overloading of individual servers and network congestion. Much research has been done in this area to minimize the user-perceived delay. Domenech et al. (2010) says web prefetching is a technique that enables faster web search by proactively fetching content before users actually request it. It predicts the user’s future requests for web objects by using various methods and brings them into the cache prior to an explicit request for them. From the perspective of a server, web access patterns frequently exhibit strong temporal locality.

Various web prefetching methods are proposed and reported in the literature. Web prefetching can be client based (Balamash, Krunz, and Nain 2007), server based (Marquez, Domenech, and Pont 2008) or proxy-server based (Wu and Kshemkalyani 2006). Prefetching based on semantics, Markov models, dynamic web pages, and graphs have been suggested. Gracia and Sudha (2013) suggest storage models that rely on Markov- model-based approaches for effective prediction. However, they cannot include new patterns because the predictions are solely based on the history accessed during the last time period. Lam and Ngan (2006) studied the effectiveness of using prefetching to resolve problems in handling dynamic web pages; however, only the temporal properties of the dynamic web pages are explored.

Dependency-graph-based prefetching (Padmanabhan and Mogul 1996) suggest the construction of a dependency graph for predicting the next page. This approach predicts and prefetches the nodes whose arcs connect to the currently accessed node and with weights higher than a threshold. However, the prediction accuracy is low because only pair dependencies between two web pages are examined. Gu, Wang, and Jiang (2010) present metadata prefetching based on relationship graphs with a significantly lower hit rate of 70%. Venketesh, Venkatesan, and Arunprakash (2010) investigate semantic-based prefetching that relies on predicting the future requests based on semantics. The semantic preferences are exploited by analyzing the keywords in the URL anchor text or the documents that were previously accessed.

Clustering, an unsupervised learning task, is effective when there is a large similarity in the dataset. The data is organized into clusters such that intradata instances within a cluster are similar to each other and the interdata instances between clusters are much dissimilar. Clustering is effective because related instances can be grouped so that the retrieval of data is faster. As pointed out (Vakali, Pokorny, and Dalamagas 2004), a wide range of web-data clustering schemes is present in the literature. These focus mainly on clustering of intersite and intrasite web pages. Safronov and Parashar (2003) used the page ranking concept to determine the pages to be prefetched. Here, the high-rank pages are prefetched, replacing pages of low ranks in cache. Clustering can be based on statistical and evolutionary algorithms. Kumar et al. (2014) says that the convergence of hierarchical clustering is based on the inconsistency criteria. Variant of the k-means algorithm and the fuzzy c-means are discussed by Sueli A. Mingoti et al. (2006). The variant k-means is applied with a prior knowledge of the number of clusters and the initial cluster centroids. Further, the fuzzy c-means is similar to k-means but has poorer boundaries separating the clusters, because the observations are classified in such way that some clusters are very close together.

Researchers are presently exploring clustering with evolutionary or soft computing methods such as artificial neural networks (ANN). Self-organizing map (SOM) and adaptive resonance theory (ART) networks are two well-known networks for clustering. The SOM competitive network self-organizes and provides a topology-preserving mapping from the input space to the clusters. Phoha, Iyengar, and Kannan (2002) studied and report that the competitive neural network learning approach maps the self-similar nature of web traffic to the self-organizing property of the neural network model to schedule the requests for a cluster of servers. Grossberg (2013) reports unlike neural nets such as backpropagation and multilayer perceptron (MLP); ART models exhibit plasticity in addition to stability. They are cognitive and are able to grow additional neurons if a new input cannot be categorized appropriately with the existing neurons. Vieira and Lee (2007) say that ART is developed to solve the learning instability problem suffered by standard feed forward networks. Thomas, Karl-Friedrich, and Torsten (1998) state that ART networks do not have the difficulty in determining the number of clusters.

According to Toufiq Hossain (Kazi, Feng, and Gongzhu 2010), clustering-based prefetching is classified into four categories: graph-based clustering, prefetching candidate mining, Support Vector Machine, and neural network.Pallis, Vakali, and Pokorny (2008) propose an algorithm called ClustWeb that generates clusters by partitioning the web navigational graph, using an association-rule mining technique, but it results in overaggressive prefetching when the cluster contains a large number of objects. Moreover, grouping of IPs according to their domains might fail when the IP changes dynamically. Rangarajan et al. (2004) uses the ART1 network to group users and then prefetches the users’ requests based on the prototype vector of each group. Yet, the hit rate is observed to be close to 82% and further, clustering is based on the users rather than their URLs. Gopalakrishnan and Jayarekha (2011) concentrate on clustering Video on Demand (VoD) files by ART2 and prefetching them in clusters and reported a hit rate of 97%. Moreover, clustering is specific to VoD files rather than generalized. On the Internet, actually prefetching based on a specific type of file is impractical.

Hence, with an intention to prefetch all types of web objects that account for actual Internet traffic, clustering of web objects is proposed. Clustering web objects based on users’/clients’ URLs through ART2 is proposed here. The stability and plasticity nature of the ART2 network has forced us to go for implementation of clustering using ART2. A code for locating the clusters based on the request and prefetching them after filtering the least popular web objects of the clusters (groups) is proposed in order to minimize latency.

Architecture of ART2 Network

Laurence (2004) describes the architecture of the ART2 neural network as in Figure1. Hourali, M. and Montazer, G. A (2012) explains the ART2 network has two layers, F1 and F2. The F1 and F2 layers form the attentional subsystem and the reset and vigilance (ρ) parameters form the orienting subsystem. In the attentional subsystem, an input pattern is presented to the F1 layer with six units or nodes: w, x, u, v, p, and q. In F1 there exists a supplemental unit that receives the signal from its respective nodes, calculates its norm, and sends it to its corresponding next node. All the units in F1 are calculated using Equations (2)–(7) of Appendix B. The calculation of “w” and “p,” “x,” and “q” is, rather, performed in parallel. The “u” and “p” units form the input and the interface unit, respectively. The “p” unit of the F1 layer is connected to the F2 layer through top-down and bottom-up weights. When the processed signal in p unit reaches equilibrium, the signal is passed to the F2 layer for subsequent processing. The nodes of the F2 layer compete with each other to produce a winning unit.

Figure 1. Architecture of ART2 network.

The units of F2 compete in a winner-take-all mode and choose the unit that matches the input. The similarity between the unit from the F2 layer and the input (original pattern) from F1 is computed by the ρ value. If the matching value “r” is greater than the vigilance value, then the corresponding bottom-up and top-down weights, respectively, of the present input are updated. Otherwise, the reset signal is sent to the F2 layer and the winning unit is inhibited. After inhibition, the other winning unit will be selected from the F2 layer and the process repeats. Once all F2 layer nodes are inhibited, the F2 layer produces a new node and generates the initial corresponding weights to the new node. The Appendix A gives the description of units used in ART2 network.

Proposed System

The main components of the proposed system are the clustering and prefetching block, as shown in Figure 2. The overall implementation of the proposed system is divided into five phases as follows.

Figure 2. Proposed system.

Collection of Access Patterns

The accesses made by several clients are collected from the server access log file.

Data Preprocessing and Preparation

The log file is subjected to preprocessing for clustering. The steps carried out in preprocessing are as follows:

• Parsing: Involves identification of the boundaries between the successive records in logs as well as the distinct fields within each record.

• Filtering: Involves the elimination of irrelevant entries (i.e., incomplete requests) and unsuccessful HTTP status codes entries. That is, only the successful entries with status code 200 are considered for study.

• Finalizing: Finally, the IP addresses of the clients and their URL requests are extracted for subsequent processing.

Extraction of Feature Vectors

The reduced log obtained after preprocessing is fed to the feature extractor in order to obtain the feature vectors corresponding to the clients. The feature vector of a client corresponds to the access counts of its requested URLs. Because the ART2 network supports continuous in Equation (1).

(1)

where N_ij is the normalized access count corresponding to the jth URL of the ith client, Val_i,j is the original access count of the ith client for the jth URL, d_min(i) and d_max(i) are the minimum and maximum access counts corresponding to the ith client.

A sample of a feature vector with the actual and normalized access counts for 7 URLs is shown below in Table 1.

Table 1. Representation of sample feature vectors.

Access Counts/URL’s	URL1	URL2	URL3	URL4	URL5	URL6	URL7
Original URL Access Counts	16	15	14	10	9	8	17
Min-Max Normalized Values	0.8889	0.7778	0.6667	0.2222	0.1111	0.000	1.0000

Cluster Block

The feature vector thus obtained forms the input pattern (training data) of the cluster block. The input patterns corresponding to different clients are fed as input to this block, which clusters them. The clustering algorithm for ART2 is presented in Appendix B. The output of this block is the clusters of different web objects.

Prefetcher

Depending on the input pattern of the test data, this block identifies the corresponding cluster (candidate cluster) and prefetches all the URLs of this cluster. Prefetching is initiated whenever the system is idle. The algorithm for identifying the cluster and prefetching the URLs of the identified cluster is presented in Appendix C. In this algorithm, the candidate cluster selection is based on the highest bottom-up weight. The average of the minimum and the maximum weight of the candidate cluster is used as a selection index for the web objects to be prefetched from the candidate cluster. By doing this, prefetching of all the web objects corresponding to the candidate cluster is avoided. This reduces the number of web objects prefetched because this extracted set belongs to the frequently accessed web objects within the selected cluster. Therefore, higher hit rates are achievable.

Evaluation Metrics

Evaluation metrics tests the efficacy of the techniques. The metric used for evaluating the performance of clustering is as follows.

Silhouette Index (S_P)

For each data point p in a cluster, it is the ratio of the differences between the measure of separation and the measure of cohesion to the maximum of separation or cohesion. The average distance between p and all other points in the same cluster is the measure of cohesion, and let it be A. The average distance between p and all points in the nearest cluster is a measure of separation, and let it be B.

The metrics used for evaluating the prefetching performance are as follows.

Hit Rate (HR)

The hit rate is the ratio of the total cache hits to the total client requests made. The greater the hit rate, the greater is the efficiency of the system.

Precision (P_C)

Precision is the positive predictive value that gives the ratio of the good prefetch hits to the total number of prefetches or predictions made. This measure gives the exactness or the quality. It is the fraction of retrieved instances that are relevant.

Recall (R_C)

This measure gives the percentage of requested objects that were previously prefetched. This is almost similar to the hit rate obtained by the system. This measure gives the completeness or the quantity. It is the fraction of relevant instances that are retrieved.

F-measure (F)

The weighted average of precision and recall, referred to as F-measure, is given as follows. A higher value of F indicates higher accuracy of the system and vice versa.

Simulation Results

In the server, a webpage with multiple web objects (images, video, audio, and text documents) is designed to carry out the simulation. The neural network models ART2 and ART1 are implemented using MATLAB R2013a version and supported by Internet Information Server (IIS). The experiment is carried out by creating a test bed comprising the server with multiple clients. All the clients are connected with a bandwidth connectivity of 1 Gbps under a standard Gigabit Ethernet environment. The dataset is of 102 MB in size comprising 50 clients and 100 URLs. The size of cache memory used is 512 MB. The client’s request (dataset) over for a long span (roughly around 10,000 requests) was collected from the web server access logs. The log file is preprocessed and the feature vector for 50 clients is obtained.

Clustering

The input patterns thus obtained are fed to the input layer of ART1 and ART2 with ρ = 0.9 for clustering. The number of clusters and the top-down weights of the URLs in each cluster obtained through ART2 and ART1 are displayed in Figures 3 and 4, respectively.

Figure 3. Cluster formation through ART2 network.

Figure 4. Cluster formation through ART1 network.

The rows and the columns of the tables in Figure 3 and 4 represent the URLs and the resulting clusters correspondingly. ART2 clustered these input patterns into 45 clusters and ART1 clustered into 50. However, due to space complexity, only 17 clusters corresponding to 21 URLs are displayed. The cluster results prove that clustering through ART2 is superior to that of ART1. This is because the discrete input to ART1 trains the network and clusters them almost equal to the number of clients (input patterns). However, in the case of ART2, because the normalized continuous values are fed as input, the network is trained to cluster them based on the client’s access count rather than the number of clients.

Figure 5 and Figure 6 depict the data points of the various clusters with their weights for ART2 and ART1, respectively. The x-axis represents the input pattern and the y-axis represents the top-down weights. The different colors refer to various clusters. In Figure 5 and Figure 6, the different colors correspond to different clusters. In Figure 5, the variation in top-down weights is obvious, but in the case of Figure 6, there is no variation in the top-down weights because of the discrete weights. This leads to inefficient clustering in comparison with that of ART2. This helps us to conclude the superiority of ART2 over that of ART1.

Figure 5. Plot of the top-down weights vs. clusters using ART2.

Figure 6. Plot of the top-down weights vs. clusters using ART1.

Validation of ART2

To substantiate the selection of ART2 for clustering, validation of the various clustering techniques is carried out. The standard Fishers iris dataset from the UCI repository is used for validating ART2. It consists of three species of iris: Iris Setosa, Iris Virginica and Iris Versicolor with 50 specimens of each. The Silhouette Index is used to study and compare the clustering performance of ART2 and other statistical algorithms such as k-means, hierarchical single and hierarchical complete. Figure 7 depicts the optimal number of clusters formed by various algorithms such as k-means, hierarchical single and hierarchical complete, and ART2 algorithms. The Silhouette Index is highest at two clusters for hierarchical single and hierarchical complete, but for k-means and ART2 it is three clusters. Because iris data consist of three well-identified labels, three clusters should be formed. K-means and ART2 were able to produce the same three clusters. Further, from Figure 5, it is clear that the Silhouette Index of ART2 is higher than other techniques always, confirming the supremacy of ART2. The stability and plasticity of all the data are maintained during experimentation.

Figure 7. Plot of the optimal number of clusters by various algorithms.

Prefetching

For effective prefetching, prefetching in clusters is the aim, and the following cases are studied.

Scenario 1

To study the performance of prefetching, training and testing for different ratios of the dataset (input pattern) using k-fold validation with ρ = 0.9 for ART2 and ART1 is carried out. Their corresponding results are tabulated in Table 2.

Table 2. Training 3: for ρ = 0.9 and number of epochs = 100.

Training (%)	Testing(%)	Hit rate (%)		Number of clusters formed by ART2	Number of clusters formed by ART1
		ART 2	ART 1
10	90	88.9264	86.1170	45	50
20	80	88.9242	86.9399	43	50
30	70	90.5663	86.0123	43	50
40	60	93.5233	89.7321	41	49
50	50	95.1299	89.7411	41	49
60	40	95.1211	90.4808	40	49
70	30	97.1476	93.9944	40	49
80	20	98.1983	95.8529	40	49
90	10	99.9912	96.9790	39	48

From the Table 2, the hit rate obtained through ART2 is higher than that of ART1. This further confirms the supremacy of clustered prefetching using ART2. Further, the number of clusters formed through ART2 is fewer than ART1. ART1 roughly clusters the input pattern into approximately 50 clusters, almost equal to the number of clients. From this, it is inferred that ART2 clustering is dominant over ART1.

Further, to study the impact of the vigilance parameter (ρ), clustering for different values of ρ (ρ = 0.4 and 0.7) is carried out, and their corresponding hit rate due to prefetching is depicted in Tables 3 and 4. The hit rate and the number of clusters formed for various ρ values are plotted in Figures 8–9, respectively. From the Tables 3 and 4, the hit rate through ART2 is observed to be higher than ART1. Thus, it is concluded that ART2 is well suited for clustering the unsupervised data and thereby supports efficient prefetching.

Table 3. Training 1: for ρ = 0.4 and number of epochs = 100.

Training (%)	Testing (%)	Hit rate (%)		Number of clusters formed by ART2	Number of clusters formed by ART1
		ART 2	ART 1
10	90	87.5290	86.0001	40	48
20	80	88.9067	86.0323	40	48
30	70	89.3434	86.0135	39	47
40	60	94.6520	89.7217	37	45
50	50	94.6845	89.3402	35	45
60	40	96.2322	90.8008	32	41
70	30	98.1769	93.8590	30	41
80	20	98.1983	94.7247	28	38
90	10	98.0922	96.8719	28	38

Table 4. Training 2: for ρ = 0.7 and number of epochs = 100.

Training (%)	Testing (%)	Hit rate (%)		Number of clusters formed by ART2	Number of clusters formed by ART1
		ART 2	ART 1
10	90	87.2960	85.1170	35	45
20	80	88.9271	85.9399	32	45
30	70	90.7163	87.0123	32	43
40	60	93.5209	90.7321	31	43
50	50	94.1177	92.7411	30	43
60	40	95.2012	93.8078	30	40
70	30	97.739	93.9901	28	40
80	20	98.0023	93.5297	25	39
90	10	98.1293	95.7900	20	38

Figure 8. Plot of the hit rate vs. vigilance value.

Figure 9. Plot of number of clusters vs. vigilance value.

From Figure 8, the hit rate is found to increase with increase in the vigilance parameter ρ. Moreover, from Figure 9, the number of clusters formed is also observed to increase as ρ increases. When the vigilance parameter is lower, fewer clusters are found to be formed. Hence, for effective prefetching, the vigilance parameter should be set high.

Also, from the Tables 2–4, a hit rate of 98% to 100% in case of ART2 is observed when the page requested has links to only text files. However, a hit rate of 91%–97% is observed when the page requested contains all types of files (i.e., audio, video, and text). This is because the sizes of audio and video files are larger, and cache memory occupation is high, leading to a slight reduction in hit rate. A hit rate of less than 90% is observed at lower percentages of training data and low vigilance values. Hence, for effectual prefetching, the percentage of training data should be large in addition to a high vigilance parameter. A large training dataset helps in adapting the network to better cluster formation.

Scenario 2

To examine the prefetching performance, tests for various volumes of cache and the corresponding results are plotted in Figure 10.

Figure 10. Plot of the hit rate vs. cache size.

From the plot, the hit rates by ART2 are found to be higher than those of ART1. Thus, prefetching using ART2 clustering is superior to prefetching using ART1.

Scenario 3

The recall, precision and F-measure obtained for the different requests made by clients is depicted in Figure 11.

Figure 11. Plot of the number of requests vs. performance measures.

From Figure 11, the recall, precision and F-measure of ART2 are higher than those of ART1. This is because of the achievement of higher hit rates by ART2 than ART1. This proves that prefetching through ART2 is more efficient than prefetching through ART1.

Thus, from all the test cases, it is evident that prefetching in clusters using ART2 outperforms that of ART1. This elucidates the fact that clustering is enhanced using the ART2 network and, thereby, prefetching is also enhanced.

Conclusion

Clustering is grouping data into clusters such that the intradata instances are similar to each other and the interdata instances are very much dissimilar. Clustering is performed by ART2 for comparison with ART1 and other statistical techniques. On comparison, the Silhouette Index of ART2 clustering is found to be higher than that of other techniques, confirming its supremacy. Exploiting the concept of ART2 clustering, prefetching of web objects in clusters is proposed. Because ART1 neural networks support only discrete values, exact clustering and further prediction is not found to be accurate. Because ART2 supports continuous values, clustering and, subsequently, prefetching are found to be enhanced. The clustering algorithms and prefetching codes are implemented in MATLAB and their results are presented. The experimental results prove clustered prefetch using ART2 to be superior to ART1. Further, attempts are being planned to boost the cache performance through improved cache replacement strategies to augment the system performance. Prefetching web objects with machine learning algorithms is the aim of the future scope this work.

Appendix A

Nomenclature for Appendices B and C

Table

Symbols	Description
a, b	Fixed weights in F1 layer
c	Fixed weight to test for reset
d	Winning unit of F2
e	Parameter to prevent division by zero
θ	Noise suppression parameter
α	Learning rate
ρ	Vigilance parameter
n	Number of URLs in ART2
m	Number of clients in ART2
t[n,m]	An array of top-down weights
b[m,n]	An array of bottom-up weights
s[i,j]	input pattern of jth URL for ith client (1D array of URLs)
w[m],x[m],u[m],	A 1_D array of nodes/units in F1 layer
v[m],p[m],q[m]

Appendix B

Algorithm for clustering, using ART2

The step-by-step procedure for adaptation of the network to the input for clustering is illustrated following.

Step 1: Initialize the parameters (a, b, c, d, e, ρ, θ, α), the top-down weights (t_iJ) and the bottom-up weights (b_Ji).

(Initially a = b = 10, c = 0.1 and d = 0.9 in order to satisfy the equation).

Let e = 0, , α = ρ = 0.1, t_0i = 0 and .

Step 2: For each input pattern, do Steps 3–10.

Step 3: Update the F1 layer activation. Calculate w_i, x_i, and v_i as follows while others are set to zero.

Table

Step 4: Update the F1 layer activation again and calculate the following parameters using Equations (B.1)–(B.6).

(B.1)

(B.2)

(B.3)

(B.4)

(B.5)

(B.6)

Here,

Step 5: Calculate the F2 layer activation.

(B.7)

Find if reset condition ≥ ρ-e is true, perform Steps 6 and 7 where

Step 6: Find the maximum activation unit J in the second layer (F2).

Step 7: Check for reset. Perform Equations (B.1) and (B.3) and,

if < ρ-e, then y_J = −1 and inhibit the unit J. Then return to Step 5.

Else,

if ≥ ρ-e, then calculate Equations (B.2), (B.4), (B.5), (B.6) and go to Step 8.

Step 8: Update the weight of winning unit J.

(B.8)

Step 9: Update the F1 layer activation. Perform Equations (B.1)–(B.6).

Step 10: Test stopping condition for weight updates.

Step 11: Test if the number of stop epochs is reached, if true, stop, else proceed to Step 2.

Now, the block has trained the network and finally clustered the input pattern into clusters with URLs as members.

Appendix C

Proposed Algorithm for Prefetching URLs

Input: x, a requested URL

Output: X, a set of prefetched URLs

CC_k – is the kth cluster corresponding to the highest bottom-up weight.

begin

Initialize X as empty set

//selection of bottom-up weights

if x is in cache, then prefetching not required

else Find J such that b_Ji > v for all nodes j of URL_i, where

Find CC_k that is connected to x with b_Ji weights

For each u_j є URL connected to CC_k do

//selection of top-down weights

Get the cluster number (CC_k) corresponding to the weight selected from b_Ji

Get the maximum and minimum values from t_kj (clust_max and clust_min)

Find

if u_j > C, then

if u_j is not in cache, then X←X U u_j

end

return X

end