Organizing XML Data in a Wireless Broadcast System by Exploiting Structural Similarity

The following scenario can be used to show potential applications of XML data broadcast in real life.

Consider a live basketball game. Information about the game and the players on the court is usually the interest of a large number of audience. When the game progresses, the volume of such information is expected to increase, which means the information content is dynamic. Normally, a basketball stadium can accommodate 10,000 to 60,000 audience at the same time. This large number of audience are likely to be interested in similar game information. They may even want to access the game information at the same time (suppose most of them are with mobile devices). In this context, data broadcast is a preferable way of delivering latest information to the audience. Then thousands of audience in the stadium can access game information simultaneously by just “listening” to the broadcast channel. Audience do not need to contend limited bandwidth (i.e., the use of the uplink channel) and other system resources (i.e. the server processing capacity) with each other.

In this scenario, it is assumed that (1) the audience are not only interested in the real-time information about the basketball game, but also interested in some historical records/statistics information about the players, the basketball teams or the coach teams, etc; (2) the audience may want more statistics information about the current basketball game than the limited live statistics information shown on the large screens inside the stadium. Therefore, a broadcast service would be very helpful for the audience to obtain more desired information about the game.

Meanwhile, audience could be outside of the stadium, such as basketball fans who are watching live text information about the game via the Internet at their homes. Therefore, the game information could also be delivered via the Internet to online audience and other Web service providers who have subscribed this basketball game. Using XML format to represent game information can satisfy all these needs and realize simplicity, generality, and usability of game information at the same time.

Figure 1 shows a wireless XML data broadcast system. The system includes an XML Data Center (the broadcast server), a broadcast program scheduler, broadcast listeners (mobile clients) and a downlink channel (the server broadcasts information to mobile clients via it). If mobile clients are interested in some data on the server, they can listen to the downlink channel and download data that they need. Note that, downloading the data from the downlink channel does not mean each mobile client would need to set up a different downlink connection. All mobile clients only need to tune in the downlink channel and listen to it for the desired information. Thus this downlink channel can be shared by all mobile clients. Mobile clients cannot send their individual queries to the server in this model as no uplink channel is available.

There are several notable advantages of such a system model. Firstly, it can serve an arbitrary large number of mobile clients simultaneously. Secondly, extra energy cost at the client side for using an uplink channel can be avoided. Further, after applying air indexing techniques [8, 19], mobile clients will also be able to determine when the desired data will be broadcasted on the wireless channel (for more details about air indexing, please refer to Sect. 4.3). Before the desired data is available, they can switch to energy saving mode to reduce power consumption. As a result, the battery life of mobile clients can be extended.

From the figure, it can be seen that the XML Data Center could be connected to the Internet and deliver information to online users, Web service providers and Publish/Subscribe systems, etc. With the use of XML data, these different applications can be integrated seamlessly with the wireless data broadcast system for the purpose of sharing and delivering the same information to different users.

The goal of this work is to place XML documents on the broadcast channel based on the information at the server side. This work proposes to explore structural sharing between different XML documents and place documents according to the structural sharing results. Here, structural sharing refers to overlaps of path sets (defined in the below) of XML documents.

Some existing work on measuring structural sharing between XML documents can be found in [20, 21]. The main idea of their work is based on the concept of path sets. Here, a path set of an XML document contains all full paths (paths that are from the root element to the leaves) and their subpaths. A simple example is depicted in Fig. 2. The path set of this example is: {/player/name, /player/position, /player/nationality, /player/ college, /player, /name, /position, /nationality, /college}. A path set of an XML document d is denoted as PS(d), while |PS(d)| denotes the number of paths in PS(d).

Different types of metric can be adopted, such as Jaccard metric [22, 23], Dice’s coefficient [24] and Lian’s metric [25], to measure the structural sharing or similarity between two XML documents \(d_i\) and \(d_j\). The exact forms of these metrics based on PS are as follows (Jaccard metric is denoted as \(J(d_i,d_j)\), Dice’s coefficient is denoted as \(D(d_i,d_j)\) and Lian’s metric is denoted as \(L(d_i,d_j)\)):

Equation (1) computes the proportion of common paths over the union of all paths in two given XML documents \(d_i\) and \(d_j\), Eq. (2) computes the result of twice of the number of common paths over the total number of all paths in the two given XML documents, and Eq. (3) computes the proportion of common paths over all the paths in the larger path set of the two given XML documents. From the above definitions, it can be seen that both Jaccard metric and Dice’s coefficient give more weights on the total structural information of two comparing documents while Lian’s metric emphasizes on the difference of these documents. All three metrics can vary in the interval [0, 1]. If \(PS(d_i)=PS(d_j)\), then \(J(d_i,d_j)=D(d_i,d_j)=L(d_i,d_j)=1\). Clearly, the larger the values of these metrics are, the more structural sharing the two comparing XML documents have. From these equations, we can have a better understanding about what kind of structural information a specific metric emphasizes on. Further, on top of these metrics, we will introduce a new metric that is more suitable for assisting data placement of XML data in wireless broadcast later in this paper.

Intuitively, for any two given XML documents, the system can utilize one of the three structural similarity metrics described in Sect. 2.3 to calculate the similarity between them and the similarity results can be used to approximate the probability that a specific query is matched with both documents at the same time. For example, if two XML elements are under structurally similar paths, then it is more likely that that either both elements satisfy, or none satisfies, a given query [20]. Therefore, if two XML documents are with larger structural similarity, i.e. \(d_1\) and \(d_2\), then they would have a higher probability to be required simultaneously. However, there are still three other cases to be considered, such as requiring \(d_1\) but not \(d_2\), requiring \(d_2\) but not \(d_1\) and requiring neither of \(d_1\) and \(d_2\). Therefore, the above similarity metrics consider only successful match probabilities of both XML documents and do not consider unsuccessful match probabilities.

Nonetheless, unsuccessful match cases have effects on the expected access time as well. According to Propositions 1 and 2, in order to have better access efficiency, the gaps between any two required documents by a single query should be as less uniform as possible. Based on this, it can be inferred that in the above example, cases of required \(d_1\) but not \(d_2\) and required \(d_2\) but not \(d_1\) are likely to generate more uniform gaps while other two cases (required both documents or neither) are likely to have less uniform gaps. Observing this, a new similarity metric called Cohesion is defined to give a more accurate estimation of access patterns of mobile clients in the following.

Note that, for any query q requiring at least one of the documents in \({\mathcal {D}}\), q must match some paths in \(PS({\mathcal {D}})\) and it has a probability of \(\frac{|PS(d)|}{|PS({\mathcal {D}})|}\) to match d. If a query q fails to match any document in \({\mathcal {D}}\), the issuer of q only needs to locate and download air index³ to confirm that his/her query does not match any document. Then he/she can stop waiting for the result to be broadcasted. All these queries only need to access the index information on air and therefore, their expected access time depends heavily on the index distribution, which is not the focus of this work. To estimate their expected access time, interested readers are referred to [19] for more details. Hence, this work only considers successful queries. This is because the access time of unsuccessful queries will depend on the indexing method but not on the data placement results. That means data placement algorithms will not affect the access time of unsuccessful queries.

Now suppose there is a set of n XML documents \({\mathcal {D}}=\{d_1, d_2, \ldots , d_n\}\) on the server, the access probability of any document d for queries which successfully match at least one document in the set \({\mathcal {D}}\) can be approximated as follows:and for any i, j (\(1\le i,j\le n\))

Here, \(PS({\mathcal {D}})=\bigcup _{i=1}^{n}{PS(d_i)}\). According to this equation, \(Pr(d_i-d_j)\) refers to the probability of a given query matching \(d_i\) but not matching \(d_j\).

There would be many different matching cases for a given set \({\mathcal {D}}\). Take two XML documents \(d_1\) and \(d_2\) in \({\mathcal {D}}\) as an example. As mentioned previously, there would be four cases of matching of them and the probability of each case is shown in Table 2. This table also includes positive and negative effects on the expected access time (\(AT_{exp}\)) for each case. Positive effects refer to the situation that, if we put the two documents with high probability \(Pr(d_1\bigcap d_2)\) or \(1-Pr(d_1\bigcup d_2)\) together, according to our previous analysis, we should expect to achieve smaller \(AT_{exp}\). In terms of negative effects, it means if we put the two documents with high probability \(Pr(d_1-d_2)\) or \(Pr(d_2-d_1)\), we would expect to achieve larger \(AT_{exp}\).

Based on Table 2 and the previous analysis, it can be seen that, given two documents, if both documents are matched against the same query or neither of the documents is matched, the two documents will tend to be more similar to each other, i.e., \(Pr(d_1\bigcap d_2)\) or \(1-Pr(d_1\bigcup d_2)\) is higher. On the other hand, if only one of the two documents is matched against a given query, the similarity between them tends to be smaller, i.e., \(1/Pr(d_1-d_2)\) or \(1/Pr(d_2-d_1)\) is smaller. Based on this observation, Cohesion \(C(d_i, d_j)\) of XML documents \(d_i\) and \(d_j\) is defined as follows:

Here \(d_i\) and \(d_j\) are both in set \({\mathcal {D}}\). It is easy to see that \(C(d_i, d_j)=C(d_j, d_i)\). According to Eqs. (9), (10) and (11), \(C(d_i, d_j)\) can be calculated after finding path sets of \(d_i\), \(d_j\) in \({\mathcal {D}}\). Cohesion values can vary in a wide range which exceeds interval [0, 1]. Strictly speaking, Cohesion values only vary in interval \([0, \frac{|PS({\mathcal {D}})|}{4}]\) if we define that \(C(d_i, d_j)=\frac{|PS({\mathcal {D}})|}{4}\) when \(PS(d_i)=PS(d_j)\). The reason of doing so is: if \(PS(d_i)\ne PS(d_j)\), the upper bound should be \(\frac{|PS({\mathcal {D}})|}{4}\) as shown in the following. The lower bound 0 is trivial. In order to obtain the upper bound, this work only considers cases that have \(PS(d_i)\ne PS(d_j)\), from which it can be inferred that \(max\{|PS(d_i-d_j)|, |PS(d_j-d_i)|\}\ge 1\), and thus, we have \(max\{Pr(d_i-d_j), Pr(d_j-d_i)\} \ge \frac{1}{|PS({\mathcal {D}})|}\). Without loss of generality, let \(|PS(d_i)|\ge |PS(d_j)|\), according to Eqs. (9) and (10), (11) can be rewritten as follows:

Then the above result gives the upper bound of Cohesion \(C(d_i, d_j)\). From this upper bound, we can infer that Cohesion \(C(d_i, d_j)\) may reach \(\frac{|PS({\mathcal {D}})|}{4}\) when (1) \(d_j\) is very small and has little structural overlapping with \(d_i\), and (2) \(d_i\) is big and contains half of the paths of all documents. Now Cohesion values can be normalized to interval [0, 1] in the following

It can also be inferred that \(C^\prime (d_i, d_j)=1\) if and only if \(PS(d_i)=PS(d_j)\). Similar to the other three similarity metrics, the larger the value of Cohesion is, the more structural sharing the two comparing XML documents have.

Based on the discussions of structural sharing between XML documents, it becomes feasible to generate a broadcast program for periodic data broadcasts in a greedy way. From previous discussions, if more structural sharing of two XML documents is observed, the probability to match both XML documents simultaneously will become larger. As a result, the Greedy Data Placement Algorithm (GDPA) places XML documents with most structural sharing together first as an initial broadcast program. Then it progressively appends other XML documents to the broadcast program in a descendant order of structural sharing. Detailed steps of GDPA are shown in Algorithms 1 and 2.

Algorithm 1 initializes a structural sharing matrix S[n][n] for n XML documents on the broadcast server. Note that, all four similarity metrics defined in Sects. 2.3 and 4.1 can be used in Algorithm 1 to compute structural sharing between two documents (Line 6). All of them are symmetric which means for any one of these metrics, it must be true that \(S[j][i]=S[i][j]\). Also it is true that \(J(d_i,d_j)=D(d_i,d_j)=L(d_i,d_j)=C^\prime (d_i, d_j)=1\) if \(i=j\). Therefore, the algorithm only needs to calculate matrix S for entries S[i][j] where \(i<j\).

Algorithm 2 adds the most similar XML document to the broadcast program at each time. It finds the most similar document based on structure similarity to the head and rear documents in the current broadcast program. That means, it will compare documents with the head and rear documents and then select the document with maximum similarity value. To be specific, based on matrix S, Algorithm 2 finds the pair of XML documents with maximum structural sharing value and adds them into the initial empty broadcast program \(\sigma\) (Line 2). As discussed in Sect. 3, the expected access time is determined by the gaps between the required documents but not by the sequence of them. Therefore, the sequence of the first pair of XML documents can be simply placed according to the ascendant order of document lengths (Line 3 to 7). Then from Line 9 to Line 21, Algorithm 2 appends the XML document with the maximum structural sharing to the head document \(d_{head}\) or the rear document \(d_{rear}\) of \(\sigma\). If the maximum structural sharing is derived between document d and document \(d_{head}\), d will be appended into \(\sigma\) from head; otherwise, d will be appended into \(\sigma\) from rear. Once the selected document is added to \(\sigma\), that document will be removed from \(D^\prime\). Then a similar process on \(D^\prime\) will be repeated until all XML documents are placed into \(\sigma\) in order.

Time Complexity Suppose there are totally n documents on the server and each document contains p elements (or in other words, p paths) on average. Then in Algorithm 1, the for loop from Line 2 to Line 4 takes \(O(np\log p )\) time (it is proposed to use sorted sets here in order to speed up the set operations in the following lines). Note that intersections or differences between two sorted sets take linear time, which meas Line 6 in Algorithm 1 takes O(p) time. Therefore, the for loop from Line 5 to Line 8 takes \(O(n^2p)\) time since there are \(O(n^2)\) pairs of documents. Finally, in Algorithm 2, Line 2 takes \(O(n^2)\) times and the while loop from Line 9 to Line 21 takes \(O(n^2)\) time as well. Putting all the times together, the total time complexity of both Algorithms 1 and 2 is \(O(np\log p + n^2p)\).

Now consider the scenarios of adding a new document or removing an existing document from the document set on the server. For adding a new document, the update time complexity would be \(O(p\log p+np+n^2)\). This is because it takes \(O(p\log p)\) time to compute the sorted path set for the new document, O(np) time to intersect with the n existing documents on the server and finally, it takes \(O(n^2)\) to recompute the whole data placement. For removing an existing document from the server, the update time complexity would be just \(O(n^2)\) as the algorithm only needs to recompute the data placement for the rest \(n-1\) documents.

In order to improve energy conservation, smart mobile devices can switch between two operation modes: active mode and doze mode. In the active mode, a device can listen, compare, and download the required data; while in the doze mode, it turns off antennas and some processes to save energy. The energy consumed in active mode can be up to 100 times of that in doze mode [28]. However, after a broadcast program \(\sigma\) is generated, mobile clients cannot locate information of their interests as there is no auxiliary information to assist them, which means mobile clients would need to stay in active mode all the time. Air indexing can help to solve this problem.

Air index is a small amount of auxiliary information of the broadcast program \(\sigma\) and is used to assist mobile clients to calculate the arrival time of information that they are interested in [19]. As mentioned, without air index, mobile clients would have to download all XML documents on air to examine which ones satisfy their requests. Therefore, the system needs to apply air indexing technique to the generated broadcast program \(\sigma\). With the technique, mobile clients can avoid to examine documents on air one by one. Instead, they can switch to doze mode when uninterested documents are broadcasted and switch to active mode only when interested documents arrive. After the interested documents have been retrieved, they can switch back to doze mode again. In this way, energy can be significantly saved for mobile clients.

This work adopts Compact Index (CI) [8] as the index structure and (1, m) index scheme [19] as the index distribution strategy.

CI provides a two-tier air index scheme [8]. The basic structure of CI is the combination of all the DataGuides (containing structural information only and supporting simple XPath queries, while branching queries are not supported) of XML documents in \(\sigma\), which utilizes RoXSum [29] technique to integrate these DataGuides, where common structural information amongst different XML documents can be combined to form much smaller structural representations about the original XML document set. In this basic index structure, every unique-label path (with only structural information) of a document appears exactly once for supporting simple XPath queries. Thus it contains the entire unique-label paths in all of the XML documents. CI also includes a two-tier structure which enables efficient access protocol at the client which facilitates the index access. Normally, CI is only 1.5% of the original XML data in terms of size. More details can be found in [8].

The idea of (1, m) index scheme [19] is shown in Figure 4. From the figure, it can be seen that the generated broadcast program \(\sigma\) is divided into m data segments and before broadcasting each data segment, an index segment will be broadcasted first. The optimal value m is given by \(\sqrt{\frac{{\mathcal {L}}_{data}}{{\mathcal {L}}_{index}}}\). Here, \({\mathcal {L}}_{data}\) refers to the total length of the raw broadcast program \(\sigma\) without any index information and \({\mathcal {L}}_{index}\) refers to the length of index, which is CI in this work. (1, m) index scheme can best balance access time and tuning time of mobile clients. More details can be found in [19].

The experiments are run on three data sets (DS1, DS2, DS3) each with 250 XML documents and two more data sets (DS4, DS5) with 500 and 1000 XML documents, respectively. All generated documents are defined by News Industry Text Format (NITF) DTD [30]. This DTD is published for news copy production, press releases, and Web-based news organizations. The average depth of all five document sets is between 6 and 8 while the maximum depth is 22.

The details of these data sets are shown in Table 3. Data in DS1 can be well clustered into 6 clusters. Moreover, for any two documents \(d_i, d_j\) in two different clusters of DS1, the minimum similarity values, the maximum similarity values and the average similarity values of all four metrics (normalized Cohesion is adopted here) are shown in Table 4. It can be seen that all clusters are quite different from each other and share very little structural information. Data in DS2 are miscellaneous. Documents in DS2 cannot be classified into fine clusters. Data in DS3 are a mix of well-clustered data and miscellaneous data, which include 125 XML documents from DS1 and 125 XML documents from DS2. Similar to DS2, data in DS4, DS5 are miscellaneous as well.

In the experiments, XPath queries are generated using the generator developed by [31]. Queries are allowed to repeat. The generator provides several parameters to generate different types of XPath queries, such as query depth, probability of * and // and so on. The probability of * and // appearing in each query’s step is between 5% and 30% (denoted PROB, and the default value is 10%). Here, * operator will match any element node in the document while // operator will select nodes in the document from the current node that match the selection no matter where they are. Query Incoming Rate (denoted QIR) means the number of newly issued queries from mobile clients in a unit of time. This unit of time is measured by the time that mobile wireless system takes to broadcast a block of 1024-byte XML data. The maximum depth of generated XPath queries (denoted MQD) is between 5 and 8. Table 5 shows the value range of parameters in the experiments. It should be noted that the user queries are assumed to follow a uniform distribution.

The random data placement algorithm (denoted RDPA) is compared with GDPA [implemented using all four similarity metrics defined in Equations (1), (2), (3) and (12)]. In RDPA, the server broadcasts XML documents in a random order. This random order is implemented by a Java class Random. When applying a series of pseudorandom numbers on the order of XML documents in a broadcast program, there would be conflicts. For example, suppose there are totally N documents to be broadcasted. It is needed to generate pseudorandom numbers between 1 and N. After k out of N documents having been randomly placed, the next chosen document may be one of the first k documents. If such case happens, it is simply ignored and Random class is used to generate pseudorandom numbers between 1 and \(N-k\) for the rest \(N-k\) documents. In this way, a random order of N documents can be simulated.

Both RDPA and GDPA are implemented on Java Platform Standard Edition 6 running on Windows 7 Enterprise, 64-bit Operating System. All the experimental results are obtained by running 30 consecutive broadcast cycles. When varying PROB, QIR and MQD are set to their default values. When varying QIR, PROB and MQD are set to their default values. Similarly, when varying MQD, PROB and QIR are set to their default values.

Regarding air indexing and index distribution strategy, as mentioned in Sect. 4, in the experiments, Compact Index (CI) [8] is adopted as the index structure and (1, m) index scheme [19] is adopted as the index distribution strategy. This is because CI is the state-of-the-art indexing technique for XML data broadcast and (1, m) index scheme is the most popular index distribution strategy for traditional periodic data broadcast. More details can be found in [8, 19].

The experimental results are shown in Figs. 5, 6, 7, 8 and 9. Average access time (AAT) is the performance metric. Also only AAT is considered for all successful matched queries and abandon unsuccessful matched queries. The main reason for this is that, AAT of unsuccessful queries is determined by index distribution but not by data placement results (more details about this can be found in [19]). Note that, GDPA can be implemented with four different similarity metrics defined in Sect. 4, which are Jaccard metric, Dice’s coefficient, Lian’s metric and the proposed Cohesion. Through the experiments, Jaccard metric and Dice’s coefficient always yield the same results. Therefore, GDPA implemented with them is denoted as J/D method in all figures. Meanwhile, GDPA implemented with Lian’s metric is denoted as Lian method and GDPA implemented with Cohesion is denoted as Cohesion method.

Figure 5 shows the results on DS1. From the figure it can be seen that all GDPA methods outperform RDPA significantly. Specifically, J/D method achieves the best results while Lian method and Cohesion method provides similar results. This indicates that J/D method better fits well-clustered data. Also, the reason for Lian method and Cohesion method showing similar results is that both methods emphasize on the common structure of both comparing XML documents against the larger document [see also Eqs. (3) and (11)]. Further, since DS1 is well-clustered, from the definitions of Lian and Cohesion metrics, it can also be inferred that the partial order of similarity results using these two methods are similar to each other. Note that, according to the data placement algorithm described in Sect. 4, the data placement results are determined by the partial order of the similarity results. Hence, for DS1, Lian method and Cohesion method yield similar results.

In Fig. 5a, GDPA methods become slightly worse when PROB increases. Since DS1 is well-clustered, most queries only require documents in the same clusters. Thus PROB has less effect on AAT. In Fig. 5b, when QIR increases, J/D method becomes slightly better. This indicates that J/D method can achieve better scalability than other methods when accessing well-clustered data. Figure 5c shows that all GDPA methods remain stable as MQD increases. It is interesting to note that for RDPA, AAT always remains stable.

Figure 6 shows the results on DS2. From the figure it can be seen that all GDPA methods achieve better performance when compared with RDPA. Specifically, Cohesion method achieves the best results while J/D method achieves the worst results among GDPA methods. This indicates that Cohesion method better fits miscellaneous data. In Fig. 6a, both GDPA methods and RDPA become worse when PROB increases. It is clear that PROB has more effect on AAT for miscellaneous data. In Fig. 6b, when QIR increases from 0.1 to 0.5, GDPA methods J/D and Lian together with RDPA become worse while Cohesion method still becomes better. After that, when QIR increases, all methods become slightly better. This shows that Cohesion method can achieve best scalability when accessing miscellaneous data. Note that, we have seen some intersecting lines when the QIR is very small. The main reason for this is that when QIR is very small, the average (or the expected) access time is unstable as the total number of queries is too small. Fig. 6c shows that all methods achieve better AAT as MQD increases since selectivity of queries drops with the increase of MQD.

Figure 7 shows the results on DS3. Similarly, all GDPA methods achieve better performance when compared with RDPA. Specifically, Lian method achieves the best results while J/D method provides the worst results among GDPA methods. This shows that Lian method better fits hybrid data. However, Cohesion method achieves very similar performance of Lian method. In Fig. 7a, both GDPA methods and RDPA become worse when PROB increases. PROB has more effect on AAT for hybrid data. In Fig. 7b, when QIR increases, all GDPA methods become slightly better and still Lian method provides the best results. Figure 7c shows that all methods achieve better AAT as MQD increases since selectivity of queries drops with the increase of MQD.

Similar experiments were also conducted using larger data sets (including 500 and 1000 XML documents respectively). The results of experiments are shown in Figs. 8 and 9. From these figures, similar trends can be observed in Fig. 6.

Query selectivity and document coverage rate were also investigated in the experiments. Here, query selectivity refers to the average proportion of documents matched with a user query and document coverage rate refers to the proportion of documents in the entire document set on the server required by at least one user query. The results are obtained using all workload parameters at default values. As can be seen from Table 6, the query selectivity is ranging from around 32 to 45%. The main reason for this is that the probability of * and // is 10% by default. Further, for all data sets. the document coverage rate is 100%, which is mainly due to the same reason of query selectivity. This shows that all documents on the server are covered in all the experiments.

Finally, the maintenance cost of the data placement algorithms is studied. The maintenance cost is measured when adding a new document to the server or removing an existing document from the server. The maintenance results are shown in Table 7. From the table it can be seen that, when adding a new document in a document set with 250 documents on the server, the time cost to calculate the similarity between the new document and all the existing documents (shown as “Similarity Time” in the table) is ranging from 209 to 238 ms on average for the Dice, Jaccard and Lian metrics. For the Cohesion metric, it takes a bit longer which is 378 ms on average due to fact that the Cohesion metric requires more set operations that the other three metrics. Meanwhile, the time cost to readjust the data placement (shown as “Placement Time” in the table) is quite similar among all four metrics, which is ranging from 168 to 181 ms. A similar pattern is observed when adding a new document to a larger document set.

On the other hand, when removing an existing document from the server, only Placement Time will be incurred. From the table it can be seen that, similarly, the Placement Time costs for four metrics are quite similar to each other. For example, when removing an existing document from a document set with 250 documents, the Placement Time is ranging from 165 to 185 ms. Again, a similar pattern is observed when removing an existing document from a larger document set.