Minne Li

Dongsheng Li
email: dsli@nudt.edu.cn

Siqi Shen

Zhaoning Zhang

Xicheng Lu

DSS: A Scalable and Efficient Stratified Sampling Algorithm for Large-Scale Datasets

Keywords: stratified sampling, aggregation, distributed processing, Spark

Statistical analysis of aggregated records is widely used in various domains such as market research, sociological investigation and network analysis, etc. Stratified sampling (SS), which samples the population divided into distinct groups separately, is preferred in the practice for its high effectiveness and accuracy. In this paper, we propose a scalable and efficient algorithm named DSS, for SS to process large datasets. DSS executes all the sampling operations in parallel by calculating the exact subsample size for each partition according to the data distribution. We implement DSS on Spark, a big-data processing system, and we show through large-scale experiments that it can achieve lower data-transmission cost and higher efficiency than state-of-the-art methods with high sample representativeness.

Introduction

With the rapid advancement in the data collection and storage technology, burgeoning data size has brought both opportunities and challenges to driving business decisions. Valuable information and knowledge could be extracted from the ever-increasing datasets. To gain knowledge from the dataset, various computing techniques such as cloud computing [START_REF] Lu | Internet-based virtual computing environment: beyond the data center as a computer[END_REF][START_REF] Zhang | Large-scale virtual machines provisioning in clouds: challenges and approaches[END_REF] and big-data processing [START_REF] Dean | Mapreduce: simplified data processing on large clusters[END_REF][START_REF] Zaharia | Resilient distributed datasets: A fault-tolerant abstraction for in-memory cluster computing[END_REF] have been proposed, which provide us the computing platform to process the data. However, it is time-consuming to process the ever-increasing and massive-scale data. Data sampling techniques can be used to gain statistical results, estimation and approximation of data in short time with slightly reduced accuracy. They are playing critical roles in areas such as social network analysis [START_REF] Gjoka | A walk in facebook: Uniform sampling of users in online social networks[END_REF][START_REF] Papagelis | Sampling online social networks[END_REF] and business market research [START_REF] Cooper | Business research methods[END_REF]. In this work, we focus on stratified sampling (SS), a widely adopted sampling technique [START_REF] Thompson | Stratified Sampling[END_REF] with high efficiency and accuracy. We implement a Distributed Stratified Sampling (DSS) algorithm, and the experimental results show that our algorithm can be 65% faster than a well-known distributed SS algorithm [START_REF] Levin | Stratified-sampling over social networks using mapreduce[END_REF] with high-accuracy and high-scalability.

Basic steps of sampling consist of extracting a representative subset of the population, performing the estimation and experiment, and extrapolating the results back in order to understand characteristics of the overall population. Specifically, stratified sampling is a sampling method involving the division of a population into distinct groups known as strata (homogeneous subgroups, in which the inner items are similar to each other). It assigns individuals of the surveyed population to strata, and then applies normal sampling methods (e.g., simple random sampling (SRS) or systematic sampling) without replacement to each stratum independently. Compared to SRS, stratified sampling is able to get higher statistical precision because the variability within subgroups sharing the same properties is lower than that of the entire population [START_REF] Thompson | Stratified Sampling[END_REF]. Thus stratified sampling improves the representativeness by reducing sampling error. In addition, having a higher statistical precision enables stratified sampling to tolerate smaller sample size than other methods, which helps to save time and effort of researchers. Consequently, stratified sampling outperforms other sampling methods both in efficiency and accuracy. Traditional implementation of stratified sampling, e.g., reservoir sampling, is not designed for distributed computing environment. Although several distributed implementations [START_REF] Levin | Stratified-sampling over social networks using mapreduce[END_REF][START_REF] Zaharia | Resilient distributed datasets: A fault-tolerant abstraction for in-memory cluster computing[END_REF] have been proposed, they are either not able to generate a statistical satisfied answer under certain conditions or not able to fully utilize the computing resources. We will further discuss this point in Section 2 and Section 4.

In this work, we propose a distributed algorithm for SS which is scalable and efficient. It has four main steps: (1) conducts a modified reservoir sampling with rough sampling size inside each data partition, (2) gathers the meta-data of intermediate results, (3) computes the exact sampling size for each partition and (4) performs a modified reservoir sampling in parallel to generate the final sampling results. Different from the method Spark Single Query Evaluator (Spark-SQE) proposed in [START_REF] Levin | Stratified-sampling over social networks using mapreduce[END_REF], DSS reduces significantly the computational cost by conducting sampling process in a distributed manner. Moreover, the data transfer cost is reduced considerably because the computation phases are conducted in distributed nodes instead of in a master node, meaning that the volume of data transferred is much reduced.

The remainder of this paper is structured as follows. In Section 2, we compare our work with related research with a focus on scalable sampling techniques. In Section 3, we further discuss the definition and provide the syntax and semantics of stratified sampling queries, and present the sequential stand-alone algorithm of answering a single stratified sampling query. In Section 4, we describe the design of the algorithm. In Section 5, we show the experimental results, and in Section 6, we conclude this work.

Related Work

A lot of research effort has been made to design scalable algorithms for processing large-scale datasets. Boyd et al. [START_REF] Boyd | Distributed optimization and statistical learning via the alternating direction method of multipliers[END_REF] have investigated the alternating direction method of multipliers to solve distributed convex optimization problem, and Owen et al. [START_REF] Owen | Mahout in action[END_REF] have introduced Mahout to apply machine learning algorithm against large datasets. However, many of these algorithms cannot generate results within an acceptable range of time without reducing data size [START_REF] Meng | Scalable simple random sampling and stratified sampling[END_REF].

In order to reduce the storage and computational cost as well as keep important statistical properties of the original data, researchers have proposed various data sampling algorithms. Gjoka et al. [START_REF] Gjoka | Multigraph sampling of online social networks. Selected Areas in Communications[END_REF] have implemented a multi-graph sampling method for online social network datasets to generate representative samples for highly clustered individual social graphs. Kurant et al. [START_REF] Kurant | Walking on a graph with a magnifying glass: stratified sampling via weighted random walks[END_REF] have utilized stratification to generate weighted graphs for efficient data crawling and metric estimation. However, these works are not designed for distributed computing environment [START_REF] Levin | Stratified-sampling over social networks using mapreduce[END_REF].

In terms of stratified sampling, numbers of previous works have been proposed for the stand-alone environment. One of the many classical methods is the reservoir sampling algorithm [START_REF] Vitter | Random sampling with a reservoir[END_REF], which requires a single pass over the whole dataset to generate representative results. However, the original reservoir sampling algorithm is not designed for distributed computing environments: data shuffling among clusters for a single query is required because the partition of data into clusters is mostly different to the partition of the population into strata. However, conducting data shuffling is unbearable in the big data environment. In order to design a scalable sampling algorithm and implement it on top of the data stored on distributed machines, the sampling process should be conducted in a parallel and distributed manner. Spark [START_REF] Zaharia | Resilient distributed datasets: A fault-tolerant abstraction for in-memory cluster computing[END_REF], a platform for large-scale datasets processing, provides the distributed stratified sampling API as one of its basic statistic functions, namely sampleByKey and sampleByKeyExact. These functions conduct sampling with given sampling probability. However, in order to draw a stratified sampling set by sample size in Spark, users need to provide the total count of records satisfied the stratum constraint, which is not possible in the practical, distributed computing environment. Even if the actual count is provided, the existing function could still fail the statistical requirement if the product of sampling fraction and total record count is not an integer. Levin et al. [START_REF] Levin | Stratified-sampling over social networks using mapreduce[END_REF] have proposed a framework for stratified sampling queries, which will be further discussed in Section 3.

Stratified Sampling Queries

In this section we will provide the definition, syntax and semantics of stratified sampling queries, as well as present the sequential stand-alone algorithm (the modified reservoir sampling algorithm) of answering a single stratified sampling query. We will further discuss in Section 4 that our sequential algorithm can be conducted in a parallel and distributed manner effortlessly.

A Single Stratified Sampling Query

The notations used in this work is defined as follows. A single stratified sampling query in this paper is defined as a set of stratum constraints s k , denoted by Q = (s 1 , s 2 , . . . , s m ). Each stratum constraint s k is denoted by s k = (p k , f k ), where p k is a propositional formula and f k is the required sample size. It is worth noting that for a qualified stratified sampling query, the strata must be non-overlapping, in other words every individual should be assigned to only one stratum. Joint strata will result in nonprobability sampling since some individuals may have greater chances of being chosen. For example, if we define two stratum constraints s 1 and s 2 for a group of students, where p 1 = (male) and p 2 = (age > 10), conducting two simple random sampling separately in stratum defined by s 1 and s 2 will give males over 10 years old greater chances of being selected.

Sequential Answering Process

A valid answer to a query Q = (s 1 , s 2 , . . . , s m ) is the union of m disjoint sample sets where (1) every single individual in subset k (k = 1, 2, 3, . . . , m) satisfies the propositional formula p k and (2) there are exactly f k individuals in subset k. In addition, a statistically representative answer set should guarantee that each subset k is a simple random sample of all the individuals in the population that satisfy p k . We will further discuss this point in Section 4 and Section 5.

Algorithm 1 Reservoir sampling for stratum constraint s k 1: Store the first f k individuals satisfied p k into a reservoir R k 2: for j from f k + 1 to n do 3:
With probability f k /j, randomly choose an individual from R k and replace it with individual j 4: end for 5: return Individuals in R k After providing the definition of a single stratified sampling query, we present a sequential stand-alone algorithm for generating the subset satisfying a stratum constraint, which is listed in Algorithm 1. Algorithm 1 is derived from the reservoir algorithm [START_REF] Vitter | Random sampling with a reservoir[END_REF] with almost the same procedure. The algorithm creates a reservoir array of size f k with the first f k items satisfied p k from the population containing n individuals. Then the algorithm iterates through the remaining population. At the j th iteration, the algorithm randomly chooses an individual from the reservoir and replace it by individual j with probability f k /j. It can be proved that at the end of the iteration, every individual has equal probability (i.e. f k /n) of being chosen for the reservoir.

Thanks to the disjoint property of strata, answering a query Q = (s 1 , s 2 , . . . , s m ) requires only single pass over the population set sequentially if we maintain m reservoirs R k and m element indexes j k . Each reservoir contains f k individuals satisfied p k respectively and thus holds a simple random sample of the processed individuals at any step during the execution.

Distributed Sampling Design

This section commences by focusing on the detailed design of our algorithm Distributed Stratified Sampling DSS. We first present the algorithm which reduces significantly the data transmission cost among distributed nodes by sending the abstract of intermediate result rather than the result itself. In addition, DSS considerately reduces the computational cost compared to existing alternatives by conducting all the sampling phases in a distributed manner. The experimental comparison will be covered in Section 5.

Sampling Representativeness in Distributed Environment

We now give the definition of representativeness in distributed environment can be seen as a cluster of connected computers (the nodes) or virtual machines provided by cloud computing services including Amazon EC2, Microsoft Azure, etc. Note that in the production environment, data is already stored in the file system and distributed separately to nodes. We are required to answer the sampling query without changing the original position of data. To generate a statistically representative answer set to a single stratified sampling query, the sample result should be unbiased in the first place. Because the partition of the population into strata is always different to the partition of data into clusters, data shuffling is required to response a sampling query. However, this is unrealistic in industrial and practical environment. Consequently, the proportion of satisfied elements in each data partition must be taken into account.

For example, we are asked to generate a sample of 10 male students playing basketball from a population of 50 students. The satisfied population (all the male students playing basketball in the population) data is distributed among two separate nodes, 20 in node O 1 and 30 in node O 2 . A simple solution is to generate an intermediate sample of 10 male students playing basketball for both of nodes, and then conduct a unification process to produce the final answer set. However, this approach will trigger a biased, statistically invalid sample. The above approach produces a male student playing basketball selected for intermediate a probability of 1/2 and 1/3, for O 1 and O 2 respectively. After conducting a simple random sampling to select 10 individuals among intermediate results, the probability of individuals from O 1 and O 2 appearing in the final answer set will be 1/4 and 1/6 respectively. This answer, however, is biased and statistically invalid since each individual should have a chance of 1/5 to be selected for the query. Consequently, in order to have a uniform and unbiased sample, the proportion of satisfied elements in each data partition located in each node must be taken into account for deciding the selection ratio from each intermediate sample. In this case specifically, the intermediate results from O 1 and O 2 should be selected with probability of 1/2 and 1/3 respectively.

Distributed Algorithm Spark-SQE

In Section 3.2, we present the modified reservoir algorithm (Algorithm 1) for answering sequentially a single stratified sampling query. By combining this algorithm with the sampling method discussed in Section 4.1, we further describe a distributed version of Algorithm 1, namely Spark Single Query Evaluator (Spark-SQE), derived from the Map Reduce Single Query Evaluator provided by [START_REF] Levin | Stratified-sampling over social networks using mapreduce[END_REF]. The procedure of Spark-SQE is depicted in Figure 1. In each data partition, similar process as Algorithm 1 is conducted to generate local intermediate result, of the form [(s k , t)] which is a list of tuple (s k , t) if individual t satisfies s k . A parallel execution of Algorithm 1 can be seen as a map phase specified by Spark, which deals with key-value pairs to generate a set of intermediate key-value pairs of the form [(s k , t)].

To gather the intermediate results, one of the naive implementations will copy all the satisfied individuals from the whole cluster to the master node. However, this procedure cannot fully utilize the computing resources.

Instead of the naive method above, during the local phase of Spark-SQE, we can merely collect a certain amount of intermediate sample. For example, we can construct a simple random selection of f l k individuals for each data partition l before passing them to the weighted sampler (f l k could be less than f k if not enough satisfied individuals exist in some certain data partitions). The local phase generates the local sample set satisfied s k , the sampling size f l k and N l , the total number of individuals satisfied s k in this partition. This approach could considerably reduce the data sent over the network and increase concurrency.

Lastly, a weighted sampler merges all intermediate results, which are already shrunk by the local process in each data node, and conducts a weighted random selection of size f k . This approach will generate a representative answer because the final sampling size is proportional to N l of each intermediate result as we described in Section 4.1.

Improved Distributed Algorithm DSS

By sending the meta-data rather than original data to the reduce function after conducting the local phase in Spark-SQE, we can further reduce the amount of data transmitted over the network. Figure 2 illustrates the process of Distributed Stratified Sampling (DSS) which is an improved version of Spark-SQE. The map phase of DSS is derived from Spark-SQE and generates the same result. In the local phase I, DSS has already generated an intermediate sample of f l k from N l individuals satisfied p k in data partition l as the Spark-SQE. To reduce the data transfer cost, we can simply send f l k and N l instead of the whole intermediate result to the master node which will execute the gatherscatter function. Then in the gather-scatter phase, DSS computes the required sampling frequency f l k of s k for each data partition using weighted sampling.

These required sampling frequency f l k of each partition is delivered to each data node separately. Thirdly, a local simple random selection shown as the local phase II in DSS is conducted to generate local parts of the final answer set. Compared to Spark-SQE, the computational cost is reduced considerately as well since we conduct the weighted sampling phase in different nodes separately rather than running a sequential process in a single reduce node. Finally, the reduce phase in DSS gathers every part of the final result from each data node together to compose a correct, unbiased and uniform answer to the single stratified sampling query.

The gather-scatter algorithm listed in Algorithm 2 receives L meta-data tuples of intermediate samples for s k from L data partitions. Each tuple consists of the actual intermediate sample size f l k and N l , the total number of satisfied individuals in data partition l. At first, the algorithm checks if the sum of intermediate sample size is enough for the required sample size f k (Line 1). If not, the algorithm simply returns f l k as the weighted sample size for each data partition l to generate the final answer (Line 2). Otherwise, the algorithm continues by iterating over 1 through L to compute an index list for determining the exact sample size of each data partition (Line 8 to 13). Because the index list is constructed based on the count of satisfied individuals N l in data partition l, it is thus probabilistically proportional to N l .

Algorithm 2 Gather-scatter ([(f l k , N l )], f k ) → [(l, f l k )] 1: if L l=1 f l k < f k then 2: return [(l, f l k )], l ∈ [1, L] 3: end if 4: N ← L l=1 N l 5: I ← Randomly select n indexes from [0, N ] 6: low bound ← 0 7: up bound ← N 1 8: f l k ← 0, l ∈ [1, L] 9: for l from 1 to L do 10: f l k ← |I ∩ [
[(l, f l k )], l ∈ [1, L]
The weighted sampler phase in Spark-SQE is similar as the gather-scatter algorithm. Instead of the meta-data, it receives the intermediate sample and then generates the final result, thus it requires significantly larger amount of data transfer compared to the gather-scatter algorithm.

It is trivial to prove the correctness (a simple random sample) of the gatherscatter algorithm by induction. The proof can be drawn inductively over the size n of the final sample. Basically, we need to prove that every subset of the population of size n has equal probability of selection, for every n.

Experimental Evaluation

In this section, we conduct large-scale and systematic experiments to evaluate the proposed DSS and compare it with Spark-SQE, which is the Spark implementation of a well-known stratified method provided in [START_REF] Levin | Stratified-sampling over social networks using mapreduce[END_REF]. We describe the experimental setup in Section 5.1, and demonstrate the efficiency and scalability of the algorithms by examining the running times and transmitted data size. We also discuss how the sampled data generated by DSS precisely represent the original data.

Experimental Setup

Dataset. In this experiment, we use two real-world datasets and one synthetic dataset shown in Table 1. The two real-world datasets are the LiveJournal social network dataset [START_REF] Leskovec | SNAP Datasets: Stanford large network dataset collection[END_REF] and the Twitter-2010 social network dataset [START_REF] Boldi | The webgraph framework i: compression techniques[END_REF]. These datasets are natural graphs following the power-law [START_REF] Faloutsos | On power-law relationships of the internet topology[END_REF] distribution, where only a few vertices have large numbers of neighbors while most of the vertices have relatively few neighbors. We pre-process the datasets by changing the graph storage structure from edge list to adjacency list. The synthetic graph dataset is generated through Power Graph API [START_REF] Gonzalez | Powergraph: Distributed graph-parallel computation on natural graphs[END_REF]. By adjusting the power-law exponent constant α we can control the skewness of the degree distribution, where a lower α implies a higher graph density and larger number of high-degree vertices. Because the adjacency list stores all neighbors of a vertex in a single record, a lower α will result in a larger storage size of high degree vertices records.

Stratified Sampling Query. We generate the sampling query by considering the out-degree of vertices. The strata are created by partitioning the out-degree of vertices into sub-ranges, which are represented by propositional formulas, e.g., (out-degree < 20). We generate valid sampling query by randomly selecting nonoverlapping degree ranges. For example, Q = (s 1 , s 2 ) where s 1 = (out-degree < 20, 2000) and s 2 = (out-degree > 50, 1000) represents a query with two distinct strata where the out-degree of vertices is lower than 20 and higher than 50.

Environment. We have implemented the algorithms in Apache Spark framework. The Spark environment is built on top of a cluster consisting four nodes, with one serving as the master and three as worker. Each node is configured with Ubuntu 14.04 LTS, 47 GB RAM, 8 Intel Xeon E5-1620 CPUs, and 2.7TB storage. All the data is stored in HDFS.

Results

In the experiment, we evaluate the efficiency and scalability of the algorithms in terms of the runtime and transmitted data size, respectively. The runtime is counted from receiving a query to generating a final result. The transmitted data size is measured by calculating the data received in weighted sampler phase for Spark-SQE and gather-scatter phase for DSS. The result has eliminated the time of loading the raw data into memory from HDFS. Moreover, we perform experiments to evaluate the representativeness and quality of the stratified sampled data generated by DSS. For the social network datasets, we calculate their degree distributions and check if the sampled data have the same degree distribution as the original data.

Efficiency. Figure 3 illustrates the relative runtime of the algorithms grouped by different datasets. The type of query has been classified by different scales, which is the total number of records satisfied the stratum constraint. We generate the query by defining the large group as p large = (out-degree < 50) and the small group as p small = (out-degree > 200) and use the same sampling frequency as 2000. The small group indicates the "long tail" of the power-law graph, which represents vertices with many neighbors. On the contrary, vertices with few neighbors comprise the large group. According to the power-law we discussed in Section 5.1, the number of records in large group is significantly bigger than the small group.

As is shown in Figure 3, the runtime of DSS can be only 35% of Spark-SQE in the best case. Even in the worst case, the runtime of DSS is about 65% of that of Spark-SQE. This achievement is mostly attributed to our distributed sampling process in the weighted sampling phase. The enhancement is not directly related to the data size. The most time-consuming phases of the two algorithms are the local phase and the reduce phase (weighted sampler phase for Spark-SQE). For the local and map phase both algorithms are totally conducted in parallel. For the reduce phase, only DSS runs in parallel and the time used in this phase is directly related to the sampling frequency. Because we use the same sampling frequency and a growing data size, according to the result shown in Figure 3, we can conclude that the local and map phase contributes more to the running time. This conclusion is theoretically explainable as the local and map phase needs to conduct an iteration over all records while the reduce phase only needs an iteration of 2000 records in our experiment. Scalability. As we mentioned above, the enhancement of our algorithm is directly related to the sampling frequency. To evaluate the scalability of our algorithm, we create a group of stratum constraints, which ask for sampling sizes ranging from 1000 to 4000. The running time for these groups of stratum constraints is shown in Figure 4. 2 shows the comparison of network transmission cost for the two algorithms. We focus on the intermediate data collection phase and use the LiveJournal dataset. As is depicted in Table 2, the size of the trans- mitted data of DSS is much smaller than that of Spark-SQE. The reason is that the data transfer cost of Spark-SQE is proportional to sampling frequency, while that of DSS remains the same across different frequencies. This is due to the fact that DSS only transmits the metadata (a tuple of two integers per partition), whose size increases linearly with the number of partitions in clusters. In contrast to DSS, Spark-SQE sends an array of all intermediate records for each partition, thus performs poorly when the sampling size increases.

Sample Representativeness. Degree distribution is an important property of social network and has frequently been analyzed in much social network research [START_REF] Clauset | Power-law distributions in empirical data[END_REF][START_REF] Jia | Socializing by gaming: Revealing social relationships in multiplayer online games[END_REF]. We evaluate the representativeness of the sampled datasets through evaluating the difference between the degree distributions of the stratified sampled datasets and that of the original datasets using Kolmogorov-Smirnov test (K-S test) [START_REF] Kolmogorov | Sulla determinazione empirica di una legge di distribuzione[END_REF][START_REF] Smirnov | Table for estimating the goodness of fit of empirical distributions[END_REF]. The K-S test works as follows. It firstly generates cumulative probability plots for the two data and calculate each vertical distance for a given x values between the two curves. Then the maximum distance (called K-S statistic) is searched from all the vertical distances. In the end, the probability value (p-value) is calculated by plugging this maximum distance into K-S probability function. The closer to 1 the p-value is the more likely the two distributions are similar, and vice versa. As is shown in Table 3, the p-values of all the datasets are high (79.9%, 92.5%, 95.4%), thus we cannot reject the null hypothesis that the degree distributions of stratified sampled data by DSS and that of original data are the same. In other words, the degree distributions of sampled data and original data share great similarities, which means the sampled data precisely represent the original data.

Conclusion

This paper proposed a distributed algorithm DSS for applying stratified sampling to large-scale, distributed datasets. DSS significantly reduces the computational cost of selecting stratified sample by implementing a modified reservoir algorithm inside each stratum in a distributed manner. Moreover, the data transfer cost is reduced significantly as well, by transmitting the meta-data instead of the data records. We implement DSS on Spark, a big-data processing platform, and evaluate the algorithm using two large-scale real-world datasets. The experiment results show that DSS performs well in terms of efficiency, scalability and representativity. Compared to Spark-SQE, which is a Spark implementation of state-of-the-art method, DSS reaches a relative enhancement of 65%. In addition, DSS requires extremely smaller amount (less than 0.05% in our experiment) of network resources in clusters than that of Spark-SQE.

Fig. 1 .

 1 Fig. 1. Process of Spark-SQE, including the map phase (Algorithm 1 ), the local phase and the weighted sampler. The symbolic tuples besides the arrow in each phase represents input and output for this phase respectively. The local transformation and computation between the raw data and the intermediate sample is connected by dotted line. Data transmission among clusters is represented by solid lines. Thick lines indicate large data-transmission while the thin ones indicate the opposite. Each D, M and S stands for data partition, intermediate sample, and final result respectively.

Fig. 2 .

 2 Fig. 2. Process of DSS, including the map phase (Algorithm 1 ), the local phase I, the gather scatter phase, the local phase II and the reduce phase. The dotted lines represent local transformation and computation between the raw data and the intermediate sample. In addition, the data and meta-data transmission among clusters are represented by solid lines and dashed lines respectively. Each D, M, L, S' and S stands for data partition, intermediate sample, required sampling frequency list, local weighted result and final result respectively.

Fig. 3 .

 3 Fig. 3. The running time of DSS divided by Spark-SQE for different query group: (left) large group and (right) small group.

Fig. 4 .

 4 Fig. 4. The running time of Spark-SQE and DSS under different sampling frequencies for the LiveJournal dataset.

Figure 4

 4 Figure 4 illustrates the runtime of DSS under different sampling frequencies can reach a linear improvement. Compared to Spark-SQE, a relative enhancement of 65% is drawn in the best case. Note that we almost touch the upper bound of optimization in our experiment environment since we have only three executors.

Table 1 .

 1 Properties of the dataset.

	Dataset	|V |	|E|	Size
	LiveJournal	4,847,571	68,993,773	514M
	alpha1.8	9,999,999	641,383,778	4.6G
	Twitter-2010 41,652,230 1,468,365,182 13G

Table 2 .

 2 The size of data transmitted in bytes during the intermediate data collection phase of the algorithms using LiveJournal dataset under different workloads, which represents by a stratum constraint s k = (p k , f k ) as described in Section 3.1.

	Workload	Spark-SQE	DSS
	s1 = (out-degree < 10, 1000)	2,017,416	112
	s2 = (out-degree < 10, 2000)	4,028,816	112
	s3 = (out-degree < 10, 3000)	6,048,232	112
	s4 = (out-degree < 10, 4000)	8,064,840	112

Table 3 .

 3 The K-S statistic and p-values of K-S tests for the three datasets used in this work. The stratum constraint is defined as s k = (out-degree < 50, 1000).

	Dataset	K-S statistic	p-value
	LiveJournal	0.020336	0.798941
	alpha1.8	0.017253	0.925117
	Twitter-2010	0.016218	0.953649

Acknowledgments. This work is sponsored in part by the National Basic Research Program of China (973) under Grant No. 2014CB340303, the National Natural Science Foundation of China under Grant No. 61222205, the Program for New Century Excellent Talents in University, and the Fok Ying-Tong Education Foundation under Grant No. 141066.


Dan Jia

Rui Wang

Chengzhong Xu

Zhibin Yu

QIM: Quantifying Hyperparameter Importance for Deep Learning

Keywords: Deep Learning, Plackett-Burman Design, Hyperparameter

Recently, Deep Learning (DL) has become super hot because it achieves breakthroughs in many areas such as image processing and face identification. The performance of DL models critically depend on hyperparameter settings. However, existing approaches that quantify the importance of these hyperparameters are time-consuming. In this paper, we propose a fast approach to quantify the importance of the DL hyperparameters, called QIM. It leverages Plackett-Burman design to collect as few as possible data but can still correctly quantify the hyperparameter importance. We conducted experiments on the popular deep learning framework -Caffe -with different datasets to evaluate QIM. The results show that QIM can rank the importance of the DL hyperparameters correctly with very low cost.

INTRODUCTION

Deep learning (DL) is a sub-field of machine learning (ML) that focuses on extracting features from data through multiple layers of abstraction. While DL algorithms usually behave very differently with variant models such as deep belief networks [START_REF] Hinton | A fast learning algorithm for deep belief nets[END_REF], convolutional networks [START_REF] Lecun | Gradient-based learning applied to document recognition[END_REF], and stacked denoising autoencoders [START_REF] Vincent | Stacked denoising autoencoders: Learning useful representations in a deep network with a local denoising criterion[END_REF], all of which have up to hundreds of hyperparameters which significantly affect the performance of DL algorithms.

Due to the inability for any one network to best generalize for all datasets, a necessary step before applying DL algorithm to a new dataset is to select an appropriate set of hyperparameters. To address this issue, a number of approaches are developed and the most popular three ones are (1) manual search, (2) grid search, and (3) random search [START_REF] Bergstra | Random search for hyper-parameter optimization[END_REF]. These approaches have their respective advantages and disadvantages. However, how to optimize the hyperparameter settings for DL algorithms is still an open question.

There has been a recent surge of interest in more sophisticated hyperparameter optimization methods [START_REF] Bardenet | Collaborative hyperparameter tuning[END_REF] [START_REF] Hutter | Sequential model-based optimization for general algorithm configuration[END_REF] [3] [START_REF] Snoek | Practical bayesian optimization of machine learning algorithms[END_REF]. For example, [START_REF] Bergstra | Random search for hyper-parameter optimization[END_REF] has applied Bayesian optimization techniques for designing convolutional vision architectures by learning a probabilistic model over the hyperparameter search space. However, all these approaches have not provide scientists with answers to questions like the following: how important is each of the hyperparameters, and how do their values affect performance? The answer to such questions is the key to scientific discoveries. However, not much work has been done on quantifying the relative importance of the hyperparameters that does matter. In this paper, we propose to quantify the importance of hyperparameters of DL using PB design [START_REF] Plackett | The design of optimum multifactorial experiments[END_REF], called QIM. To evaluate QIM, we employ Caffe [START_REF] Jia | Caffe: Convolutional architecture for fast feature embedding[END_REF] to implement the DL algorithm with the lenet [START_REF] Lecun | Gradient-based learning applied to document recognition[END_REF] and auto-encoder [START_REF] Bourlard | Auto-association by multilayer perceptrons and singular value decomposition[END_REF] model. The results show that QIM is able to assess the importance of the five hyperparameters consistently with the assessments of ANOVA in both models. On the other hand, we demonstrate that QIM is 3× faster than ANOVA on average. In particular, we make the following contributions in this paper:

-We propose a PB design based approach to quantify the importance of hyperparameters of DL algorithms, called QIM. -We leverage Cafe to implement two versions of the DL algorithm to evaluate QIM. The results show that QIM is able to correctly assess the importance of the hyperparameters of DL but is 3× faster than other approaches.

This paper is organized as follows. Section 2 describes the background of the DL and the PB design approach. Section 3 introduces our QIM. Section 4 describes the experimental setup for evaluating QIM. Section 5 presents the results and analysis. Section 6 describes the related work and Section 7 concludes the paper.

Background

Deep Learning (DL)

Generally, DL is a type of machine learning (ML) but is much more powerful than traditional ML. The great power of DL are obtained by learning to represent the world as a nested hierarchy of concepts, with each concept defined in relation to simpler concepts, as shown in Figure 1. Each DL algorithm generally includes two sub-algorithms: forward-propagation and back-propagation. Most DL algorithms come with many hyperparameters that control many aspects of the learning algorithm behavior. Generally, properly setting the values of the hyperparameters is utter important but it is also difficult. The hyperparameters assessed in this paper include learning rate, momentum, weight decay, gamma, power, and stepsize.

1 +1 +1 +1 -1 +1 -1 -1 2 -1 +1 +1 +1 -1 +1 -1 3 -1 -1 +1 +1 +1 -1 +1 4 +1 -1 -1 +1 +1 +1 -1 5 -1 +1 -1 -1 +1 +1 +1 6 +1 -1 +1 -1 -1 +1 +1 7 +1 +1 -1 +1 -1 -1 +1 8 -1 -1 -1 -1 -1 -1 -1
Learning rate is a crucial hyperparameter for stochastic gradient descent(SGD) algorithm [START_REF] Bengio | Deep learning. An MIT Press book in preparation[END_REF] which is used in the back-propagation algorithm. Momentum is designed to accelerate the learning process. Weight decay is designed to prevent the 'overfitting'. In other words, it governs the regularization term of the neural net which is added to the network's loss . The other hyperparameters, gamma, power, and stepsize are used to adjust the value of learning rate.

PB Design

The Plackett-Burman (PB) design [START_REF] Plackett | The design of optimum multifactorial experiments[END_REF] approach is one of the fractional factorial designs. PB design utilizes two values for each parameter: the high value is denoted as '+1' and the low value is denoted as '-1'. The '+1' and '-1' signs for the individual trial experiments are assigned in a cyclical manner. It involves 4k experiments, where k = 1, 2, 3..., n. In each case the maximum number of parameters that can be studied is 4k -1. For example, an 8-experiment PB design can study no more than 7 parameters.

We employ an example to describe how PB design works. Suppose that we want to quantify the parameter importance of a system with five parameters. The complete design is shown in Table 1. The importance of parameter x 1 is computed as:

m 1 = [r 1 + r 4 + r 6 + r 7 -r 2 -r 3 -r 5 -r 8 ] (1)
where r i is the performance measurement on experiment i.The importance of m 2 , m 3 , m 4 , m 5 can be computed similarly. Note that we want to quantify the importance of only 5 parameters but we construct a matrix with rows of 7 parameters; this is required by the PB design approach. However, we can use the quantities of the dummy parameters (m 6 and m 7 ) to represent experimental errors.

QIM

Overview

Figure 2 shows an overview of QIM. As can be seen, step 1 determines the value range of each hyperparameter by random search. The upper bound is For each row in PB matrix (eg. Line 1)

H H H L H L L
'+1' represents high level, '-1' for low.

An assembly

Model training

Radom search

Step 1

Step 2

Effects of model (eg. loss,accuracy) Step 3 H4 Fig. 2. Overview of QIM used as the high value (+1) and the lower bound is used as the low value (-1) for each parameter. Step 2 employs the PB deign approach to quantify the importance of each hyperparameter of DL. This step contains several sub-steps which will be elaborated later. Step 3 validates whether the results obtained by QIM are correct or not. We use ANOVA in this paper because many studies use ANOVA as a golden reference. To demonstrate the efficacy of QIM, we employ two learning models: lenet and auto-encoder, each with two data sets: CIFAR10 and MNIST. We form four types of experiments:Lenet-cifar10, Lenetmnist, Auto-cifar10 and Auto-mnist.

Identifying the Value Range for each Hyperparameter

In order to use QIM correctly, we need to know the value range of each hyperparameter for a certain DL algorithm. We propose a way named tentatively search(TS) to decide the value ranges of the hyperparameters. As shown in Figure 3, we iteratively decrease or increase the value of a parameter by a certain step-size while keep the values of all other parameters fixed and measure the performance. When we increase the value of the hyperparameter again and again until the gradient between the last two points achieves zero like CD shows, we choose the value of the hyperparameter corresponds to point C as the upper bound of the parameter. Another case is that DL algorithm fails to run successfully when we increase or decrease the value of the parameter further. It indicates that we already find the upper or lower bound of the hyperparameter in the previous try. In summary, we can find the bounds of the hyperparameters in either case.

QIM

We now turn to describe QIM in detail. We first describe the hyperparameters used in this study. The common hyperparameters used for all four types experiments include base lr, momentum, weight decay and gamma. The hyperparameter power is only used for lenet-cifar10 and lenet-mnist, and stepsize only for auto-cifar10 and auto-mnist. Since 4 × 1 < 5 < 4 × 2, we use the N = 8 PB design as showed in Table 1 and we have two dummy parameters. To improve the confidence of QIM, we design 16-run trails instead of the 8-run one proposed by PB design. This is achieved by adding a mirroring line for each line in Table 1. For each type of experiment, we run 16 trails with different hyperparamenters settings corresponding to PB matrix. Then the importance of each hyperparameter is computed by using equation (1).

EXPERIMENTAL SETUP

We conduct our experiments on two Intel 8-core Xeon(R) E5-2650, 2.60 GHz CPUs equipped with one Nvidia Tesla K20Xm GPU card. Caffe is used to implement the deep learning networks in our experiment. We use two versions of deep learning networks which are Lenet and Auto-encoder. The datasets used for these learning algorithms are mnist and CIFAR10 respectively. The mnist [START_REF] Lecun | Backpropagation applied to handwritten zip code recognition[END_REF]has 28 × 28 pixel grey-scale images of digits, each belonging to one of ten handwritten digit classes. The CIFAR10 [START_REF] Krizhevsky | Learning multiple layers of features from tiny images[END_REF] consists of 60000 32 × 32 colour images in 10 classes, with 6000 images per class.

EVALUATION

We first report the results with supervised learning and then with unsupervised learning algorithm.

Supervised Learning

The supervised learning algorithm used in this DL study is lenet. We feed lenet with data set CIFAR10 and MNIST respectively.

Results on CIFAR10 -case 1 Figure 4 shows the importance obtained by QIM and ANOVA on CIFAR10. The importance rank given by QIM, from the most important to least important,is base lr, weight decay, power, gamma and momentum. On the other hand, ANOVA gives the similar rank except the importance of the hyperparameter In this experiment, QIM introduces an error of 10.52%. This indicates that the importance rank obtained by QIM is generally correct and we can use it in practice. Moreover, we find the importance of base lr is much higher than those of other hyperparameters, which implies that the base lr dominates the performance of DL with lenet on CIFAR10.

Results on MNIST -case 2

The task is to classify the images into 10 digit classes. Figure 5 compares the results of hyperparameter importance with QIM and ANOVA. As can be seen, both methods rank the weight decay as the most important parameter and the power as the least important one. QIM treats the base lr less important than ANOVA does while the two approaches give the similar importance for both momentum and gamma. In this experiment, QIM introduces an error of 5.12% ,which is smaller than the error obtained in the first case. This indicates that the the importance rank of the hyperparameters obtained by QIM is more convincible than the first case.

Unsupervised Pre-training

As a unsupervised pre-training model, deep auto-encoder [START_REF] Vincent | Stacked denoising autoencoders: Learning useful representations in a deep network with a local denoising criterion[END_REF] is trained on CIFAR10 and MNIST respectively.

Results on CIFAR10 -case 3 QIM gives the top two importance to base lr and momentum, which are consistent with the results of ANOVA. The error rate of QIM in this experiment is 5.4%. For the less important hyperparameters such as weight decay, gamma, power, stepsize assessed by ANOVA, QIM also gives the similar importance rank but with different absolute importance values. Comparing to the case 1,we find that the learning algorithm used in DL significantly affects the importance of its hyperparameters as well.

Results on MNIST -case 4 QIM and ANOVA rank the same top three important hyperparameters including base lr, momentum, and weight decay as shown in Figure 7. In this experiment, the error of QIM is 14.32% which seems high. However, QIM assesses the importance of hyperparameters consistently with ANOVA but with less iterations.

Time Cost

Figure 8 compares the time used by QIM and ANOVA to rank the importance of hyperparameters of DL. As can be seen, the time used by QIM is 3× less than that used by ANOVA on average. As evaluated above, QIM can correctly rank the hyperparameter importance. This indicates that QIM is indeed a fast and efficient approach for quantifying the importance of hyperparameters.

RELATED WORK

There are a lot of studies focusing on optimizing hyperparameters of DL algorithm [START_REF] Hutter | Sequential model-based optimization for general algorithm configuration[END_REF] [3] [4] [START_REF] Bardenet | Collaborative hyperparameter tuning[END_REF]. In low-dimensional problems with numerical hyperparameters, the best available hyperparameter optimization methods use Bayesian optimization [START_REF] Brochu | A tutorial on bayesian optimization of expensive cost functions, with application to active user modeling and hierarchical reinforcement learning[END_REF] based on Gaussian process models, whereas in high-dimensional and discrete spaces, tree-based models [START_REF] Bergstra | Algorithms for hyperparameter optimization[END_REF], and in particular random forests [START_REF] Hutter | Sequential model-based optimization for general algorithm configuration[END_REF] [START_REF] Thornton | Auto-weka: Combined selection and hyperparameter optimization of classification algorithms[END_REF], are more successful [START_REF] Eggensperger | Towards an empirical foundation for assessing bayesian optimization of hyperparameters[END_REF]. Such modern hyperparameter optimization methods have achieved considerable recent success. For example, Bayesian optimization found a better instantiation of nine convolutional network hyperparameters than a domain expert, thereby achieving the lowest error reported on the CIFAR-10 benchmark at the time [START_REF] Snoek | Practical bayesian optimization of machine learning algorithms[END_REF]. However, these studies do not quantify the importance of the hyperparameters while QIM does.

CONCLUSIONS

In this work, we propose an efficient PB design based approach to quantify the importance of the hyperparameters of DL algorithms named QIM.With 5 15% of error, QIM can effectively assesses the importance of each hyperparameter with much smaller number of computation iterations. We empirically validate QIM with two deep models on two data sets. The results show that QIM can rank the importance of hyperparameters of DL algorithms correctly in four cases.

Fig. 1 .

 1 Fig. 1. Deep learning architecture

Fig. 3 .Fig. 4 .Fig. 5 .Fig. 6 .Fig. 7 .Fig. 8 .

 345678 Fig. 3. Determining the value range of each hyperparameter.

Table 1 .

 1 The PB design matrix with 8 experiments.

	Parameters or factors
	Assembly x1 x2 x3 x4 x5 x6 x7

Acknowledgements

We thank the reviewers for their thoughtful comments and suggestions. This work is supported by national key research and development program under No.2016YFB1000204, the major scientific and technological project of Guangdong province (2014B010115003), Shenzhen Technology Research Project (JSG-G20160510154636747), Shenzhen Peacock Project (KQCX20140521115045448), outstanding technical talent program of CAS, and NSFC under grant no U1401258.


Tyler L Hobbs
email: thobbs@cs.utexas.edu

William H Winsborough
email: wwinsborough@acm.org

Implementation and Performance Analysis of the Role-based Trust Management System

We present representations and algorithms for the implementation of , a role-based trust management language, and announce an open-source implementation available to the public. We also design and perform large-scale performance tests on policies closely modeled after possible applications of in the real world. These tests aim to determine the viability of as an authorization solution for large and potentially complex policies in a decentralized environment; the results of the tests are analyzed to identify what policy characteristics most strongly affect the performance of and develop strategies to achieve the rapid response times required in real-world authorization systems.

Introduction

The term "trust management" (TM) has been used in a variety of ways over the years. Today it is often taken to refer to semi-automated techniques for estimating the likely trustworthiness of individuals, organizations, and software agents. This paper focuses instead on the classical notion of TM introduced by Blaze, Feigenbaum and Lacy [START_REF] Blaze | Decentralized trust management[END_REF], which focuses on placing into the hands of individuals and organizations security management decisions that are appropriate to their expertise and to their exposure as stakeholders. This has the effect of decentralizing authority, which serves to place decisions in the hands of experts and interested parties.

Several TM systems have received a great deal of attention in the literature [START_REF] Blaze | Decentralized trust management[END_REF][START_REF] Blaze | The KeyNote trustmanagement system, version 2[END_REF][START_REF] Clarke | Certificate chain discovery in SPKI/SDSI[END_REF][START_REF] Gunter | Policy-directed certificate retrieval[END_REF][START_REF] Jim | SD3: A trust management system with certified evaluation[END_REF][START_REF] Li | RT: A role-based trust-management framework[END_REF][START_REF] Becker | Cassandra: Distributed access control policies with tunable expressiveness[END_REF][START_REF] Czenko | Nonmonotonic trust management for p2p applications[END_REF]. The aim of the current work is not to advance the underlying theory of TM, but rather to analyze the adequacy of one rich TM system as an authorization framework in highly decentralized and distributed environments. We have developed a Java-based system implementing , a modern TM system. uses a variant of the classical notion of role in which roles are owned by principals that have control over how the membership of their roles are defined. These roles can be used to express any property or characteristic of principals that role membership is intended by the role owner to assert. In particular, the roles can take parameters, such as the members date of birth or the path to a subdirectory to which the member has authorized access.

In , extensive use of delegation of authority is used, so that, for instance, experts on one characteristic of principals are not expected to be experts on all characteristics. For instance, a university might own roles that capture the characteristic of being enrolled as a student, while an accrediting board might own roles that capture the characteristic of being an accredited university. Someone wishing to define a role of their own such that the role's members are students at an accredited university might delegate to the accrediting board authority to define which principals are universities and to those universities, authority to define which principals are students.

is a member of the family of languages [START_REF] Li | RT: A role-based trust-management framework[END_REF][START_REF] Li | Distributed credential chain discovery in trust management[END_REF][START_REF] Li | Design of a role-based trust management framework[END_REF]. These languages introduce authority management abstractions that are given precise semantics via translation to the well understood subset of first-order predicate calculus, Datalog.

in particular is translated into Datalog with constraint systems that admit efficient evaluation [START_REF] Li | Datalog with constraints: A foundation for trust management languages[END_REF]. Constraints are logical formulas that serve to specify valuations over variables appearing as parameters in roles. For instance, constraints would be helpful in our university student example if the aim is to define a role whose members graduated in the last 10 years.

The current paper introduces techniques for the implementation of , including constraint representation and sketch an algorithm that performs the most interesting operation on them, namely conjunction. We have validated these techniques by building a distributed implementation, which is available to the public under the open source BSD license; all code and related documentation is available for public use at http://sourceforge.net/projects/rtcredential. This represents the first of the two present contributions.

The second contribution is a comprehensive investigation of the performance of our implementation. We investigate scenarios in which large numbers of credentials must be retrieved from widely distributed repositories, as well as assess the considerable improvements that can be obtained when credential caching is exploited. We do this in a variety of scenarios that we believe are representative of environments in which would be most helpful. The thesis we aim to support is that TM languages such as represent an important component in security solutions in the ever-widening need for decentralized authorization policy management.

The remainder of the paper is organized as follows: Section 2 gives a brief summary of [START_REF] Li | Distributed credential chain discovery in trust management[END_REF][START_REF] Mao | Distributed credential chain discovery in trust management with parameterized roles and constraints[END_REF]. Section 3 describes the RT Credential Toolkit. Section 4 presents and analyzes performance results for on large, real world scenarios and analyzes the results, and Section 5 concludes.

Brief Overview of

A main feature of is its ability to use parameterized roles with constraints [START_REF] Mao | Distributed credential chain discovery in trust management with parameterized roles and constraints[END_REF]. Parameters allow us to convey information about principals that could not be easily represented by role membership alone, such as values in a large domain. This in turn enables policy to define authorization with much finer granularity than when constraints are not supported. For instance, in the university student example, constraints easily capture the requirement that graduation must have occurred within the last 10 years. Without constraints, each of the 10 years has to be treated as a separate case. In general, constraints greatly facilitate giving concise definitions of roles that involve parameters that range over large sets of possible values.

The aim of an [START_REF] Li | Distributed credential chain discovery in trust management[END_REF][START_REF] Mao | Distributed credential chain discovery in trust management with parameterized roles and constraints[END_REF] policy is to assign principals (also called entities) to roles. A principal may be a user, an organization, a virtual organization (VO), or a software or hardware agent. A role takes the form . ( 1 , ⋅ ⋅ ⋅ , ) in which is an principal, ( 1 , ⋅ ⋅ ⋅ , ) is called a rolename, and 1 , ⋅ ⋅ ⋅ , are sorted3 variables. We call a role identifier, and intuitively it resembles a predicate over the owner, role member, and 1 , ⋅ ⋅ ⋅ , . We use capital roman letters , , to range over principals and , possibly with subscripts, to range over role identifiers.

A policy in is given by a set of statements, which are described just below. We index variables occurring in a statement so that indicates the role the variable occurs in and indicates the parameter position with that role. We denote vectors of variables by using bold face, so denotes the vector of variables appearing as parameters to the th role in the statement. All variables occurring in a given statement are distinct from one another.

A valuation is a mapping from variables to values in the carrier appropriate to their sort. In the treatment given here, primitive constraints are predicates applied to variables that are given an intended interpretation over the specified carriers. For instance, if two distinct variables and ℓ are intended to assume the same value, a primitive constraint = ℓ is used to express this. Different constraint systems include different carriers and different primitive constraints (interpreted predicates). A constraint is a conjunction of primitive constraints, possibly with existential quantifiers. A constraint is satisfiable if there exists a valuation that makes each primitive constraint true. A constraint is said to be over any set of variables that includes the variables that occur free in it.

There are four types of policy statements in , each of which includes a constraint, denoted by ( ), in which is the list of variables occurring in the remainder of the statement:

-Type-1: . ( 0 ) ←-; ( 0 )
This statement defines to be a member of 's role ( 0 ) under all valuations that satisfy ( 0 ).

-Type-2: . 1 ( 0 ) ←-. 2 ( 1 ); ( 0 , 1 )
This statement defines . 1 ( 0 ) to include all members of . 2 ( 1 ) -Type-3:

. ( 0 ) ←-. 1 ( 1 ). 2 ( 2 ); ( 0 , 1 , 2 )
The body of this statement is referred to as a linked role. Under each valuation that satisfies ( 0 , 1 , 2 ), the statement says that for each in .

1 ( 1 ), . 2 ( 2 ) is a subset of . ( 0 ). -Type-4: . ( 0 ) ←-. 2 ( 1 ) ∩ . 3 ( 2 ); ( 0 , 1 , 2 )
The body of this statement is referred to as an intersection. Under each valuation that satisfies ( 0 , 1 , 2 ), the statement defines . ( 0 ) to include principals that are members of both roles, . 2 ( 1 ) and . 3 ( 2 ).

Each of these statements is said to define . ( 0 ). is called the owner of the role and the issuer of these statements, and has sole authority to define such statements in the policy. The body of a statement consists of the right-hand-side, to the right of the arrow. We abuse the terminology by saying that a constraint over the variables that occur in a statement (resp., role) is a constraint over that statement (role).

Semantics and Supported Constraint Domains. Extending work by Li et al. [START_REF] Li | Design of a role-based trust management framework[END_REF], Li and Mitchell [START_REF] Li | RT: A role-based trust-management framework[END_REF] define the semantics of by translating policy statements into clauses in Datalog with constraints [START_REF] Li | Datalog with constraints: A foundation for trust management languages[END_REF]. In this context, queries about role membership are given a standard semantics based on logical entailment. Li and Mitchell [START_REF] Li | Datalog with constraints: A foundation for trust management languages[END_REF] identify some classes of constraint domains that efficiently support all the operations that are necessary for evaluating queries under Datalog with constraints. Our implementation techniques and the implementation itself support several such constraint domains. In them, all primitive constraints involve only a single variable, with the single exception of equality. (An equality = is satisfied by a valuation only if that valuation assigns both variables the same value.) Other primitive constraints we consider require variable values to belong either to a set identified through enumeration, a numerical range, which may be unbounded on one or both ends, or to bear a hierarchical relation to a node in a tree.

In , a query asks about role membership. There are three kinds of queries. An all-members query is given by a constrained role, which takes the form . ( ); ( ). A principal solution to an all-members query is the set of all principal/constraint pairs, ⟨ , ( )⟩, such that the Datalog translation logically entails that is in . ( ) under all valuations that satisfy ( ), ( ) is satisfiable, and ( ) ⇒ ( ). An all-roles query is given by a principal and determines a set of constrained roles . ( ); ( ) that the Datalog semantics makes a member of under all valuations satisfying ( ); these constrained roles are referred to as role solutions. A membership-decision query, given a constrained role . ( ); ( ) and a principal , determines the set of constraints ( ) under which is a member of . ( ) for all valuations of satisfying ( ) and such that such that ( ) ⇒ ( ) [START_REF] Mao | Distributed credential chain discovery in trust management with parameterized roles and constraints[END_REF].

The Credential Chain Discovery Algorithm

Our query evaluation engine implements the algorithm introduced by Mao et al. [START_REF] Mao | Distributed credential chain discovery in trust management with parameterized roles and constraints[END_REF], which in turn is based on the algorithm for 0 introduced by Li et al. [START_REF] Li | Distributed credential chain discovery in trust management[END_REF]. ( 0 has no role parameters or constraints.) We now briefly summarize that algorithm.

Queries are answered by creating a portion of a directed graph called a credential graph. Each node in the graph represents either a role or a principal. The graph contains several types of edges, which correspond to statements in the policy. For instance, when the policy contains a statement of the form . ( 0 ) ←-. 2 ( 1 ); 2 ( 0 , 1 ), the credential graph contains an implication edge from the node representing . 2 ( 1 ); ( 1) to the node representing . ( 0 ); 1 ( 0 ), in which the constraints ( 1 ) and 1 ( 0 ) depend on the manner (direction) in which the (partial) credential graph is constructed. To deal with Type 3 and 4 credentials (and other special cases), other types of edges are created which perform actions in concordance with their type; for example, an intersection edge requires principals to be members of both roles in the intersection before it may become a member of the role to which the edge leads.

Search Algorithms. The all-members query is answered through a backward search algorithm, which constructs the credential graph by creating a node representing the constrained role given by the query and expanding the constructed graph by traversing edges in a backward direction. Constructing and traversing edges requires the algorithm to access (possibly remote) repositories to retrieve the credentials that define those edges. Backward searches create only role nodes; principals are mentioned only in solutions and do not receive their own node. The forward search algorithm answers the all-roles query. It begins by creating a principal node, and expanding the graph by traversing edges in a forward direction. To handle linked roles in the forward search, principal nodes must also be used in addition to role nodes. Although the membership-decision query may be answered by either forward or backward search, a third algorithm referred to as the bidirectional search may also be used. A bidirectional search involves both a backward search on the query role and a forward search on the query principal simultaneously; these terminate as soon as the query principal is shown to be a member of the query role under the given constraint.

When a query is evaluated, the graph may be reused for any other queries thereafter (maintaining the graph through multiple queries is referred to as graph caching in later portions of this paper).

RT Credential Toolkit

The RT Credential Toolkit was designed to supply most of the components necessary for an authorization solution. The toolkit is composed of three main components: the credential authoring tool, the query engine, and the credential repository. Each of these components are detailed below.

Implementation Design Decisions

Representation of Constraints. The representation must support several operations: construction of internal representation from the representation given in credentials; conjunction of constraints; existential quantifier elimination; subsumption of one constraint by another; and duplication of representation. As mentioned above, the only primitive constraints we support that involve more than one variable are equalities, which leads to their having special treatment: all variables that are constrained to be equal refer to a single object representing the constraint on values they can assume. Due to the simplicity of the constraint domains we consider, any consistent conjunction of non-equality primitive constraints can be reduced to a single primitive constraint. This enables a simple representation, illustrated in Figure 1. The representation of a constraint over a statement (or a role) has an entry for each role in the statement. Each role entry has an entry for each parameter of that role and each of these parameter entries is associated with an object representing a primitive constraint, which may be shared with other parameter entries. The special primitive-constraint object (PCO), unconstrained, indicates that all values of the corresponding carrier satisfy the constraint. Among the operations that must be supported, providing an algorithm to implement conjunction is the least straightforward. We outline the conjunction algorithm in the next section.

Conjunction Algorithm. Our algorithm implementing conjunction needs to handle only the case in which one conjunct, 1 , is over some statement, and the other, 2 , is over a single role from that statement. The result, 3 , must be constructed without modifying 1 or 2 . The algorithm begins by duplicating 1 . To maintain equality constraints from 1 , the duplication procedure uses a table that associates PCOs in 1 with PCOs in the duplicate. (Note that this association is between objects, not the primitive constraints they represent.) Processing each role parameter in turn, when the PCO for that parameter in [START_REF] Blaze | Decentralized trust management[END_REF] does not yet have an associated object in the duplicate, a new copy of that PCO is created and entered into the table as well as into the duplicate's parameter entry. When the table already contains an associated object in the duplicate, a reference to that PCO is entered in the duplicate's parameter entry. Thus, the sharing of PCOs in the duplicate is made to correspond precisely to that in 1 .

Next, we modify the duplicate, generating the result 3 , by conjoining the PCOs in 2 with the corresponding PCOs in (the data structure that will become) 3 . Recall that 2 is a constraint over some role in the statement that (the duplicate of) 1 is over. The procedure considers each parameter of that role in turn, constructing a new PCO that represents the conjunction of those in 2 and in the duplicate. This new PCO then replaces the old one in the duplicate. To preserve the equality constraints in the duplicate coming from 1 while introducing the equality constraints from

Repository Locations and Credential

Typing. An acknowledged limitation of the currently available system is that it does not support credential typing of the type described by Li et al. [START_REF] Li | Distributed credential chain discovery in trust management[END_REF]. This type discipline enables credentials to be stored with either their issuers or their subjects in a manner that ensures credential chains, if they exist, can be found. However, as a means of supporting distributed sets of credentials, each credential optionally contains the location of one or more credential repositories where other credentials relevant to the issuer, defined role, and body of that credential may be found. The engine is able to use this information during proof construction to find other credentials as needed. Extending the current system to support full credential typing is a possible future activity.

Components of the Toolkit

Credential Authoring Tool. The credential authoring tool enables users to create RT credentials easily by using a special-purpose graphical user interface. Technical activities such as public key creation, credential signing, and distributing credential to repositories are easy to perform.

Credentials are stored in an XML format with elements for the defined role, body, the credential validity period, and relevant credential repositories; the credentials are cryptographically signed by the issuer of the credential. To support the use of within an organization, public keys, role names, credentials, and repository locations may be imported along with their metadata from a local or online repositories. This allows one to start with a working set of useful objects, such as public keys for company employees or commonly used role names. The metadata associated with each object allows them to be referred to by short local names instead of their globally unique identifiers and also provides a way to attach and display easy to read descriptions of each object.

The ability to import and search existing credentials allows one to view a policy set that the user may wish to modify or extend; this feature may also help to present a simple or small portion of the overall policy set to organizational members who need to write only a limited set of new policy statements.

Additionally, test queries may be run from the authoring tool to ensure that new policies have the desired effect.

Engine. The engine is responsible for evaluating credentials to answer queries. Forward, backward, and bidirectional searches are supported. The engine has both Java API and command line interfaces which may be used to pose queries and read results. The engine automatically fetches relevant credentials from the appropriate repositories for processing.

Credential Repository. The credential repository is a relatively simple application which hosts, indexes, and serves credentials to engines. Credentials may be added to a repository remotely or locally. The repository also maintains information about what credentials have been served to an engine during the current connection to avoid sending credentials multiple times.

Performance Evaluation

Although other query evaluation programs have been developed, there has been little investigation into the costs of an system which is usable by the public, stores credentials in a distributed manner, or deals with policies approaching the size and complexity expected in real world scenarios.

The costs of using in terms of latency, throughput, network usage, and computational power required need to be assessed. It also must be determined whether is efficient under certain usage scenarios but performs poorly under others and what factors primarily determine this difference. If performance is poor, new strategies may be necessary to maintain the low latency required for a useful authorization system.

Policy Benchmarks

Large scale authorization policies used in practice are difficult to obtain. Instead, we base our analysis on automatically generated policies designed to have characteristics likely to arise in realistic scenarios. To this end, we have constructed a policy generator that uses pseudo-random methods to generate policies based on a collection of parameters that can be tuned to yield policies likely to be representative of policies that would be used in a variety of scenarios. We begin by describing the policy generator and its parameters. We then describe scenarios that seem appropriate candidates for application of .

Policy Set Generator. The policy set generator creates all of the credentials necessary to define a rough hierarchy of roles based on a set of input parameters described below. At a high level, the generator creates the policy set for the hierarchy one level at a time, beginning at the base, and takes the following steps to do so:

1. The generator begins by defining the base roles. The base roles are the roles at the bottom level of the hierarchy which directly include the main body of principals and are generally defined by Type-1 policies only.

2. A new level of roles are created above the previous level. The set of policies created in step 3 will define these new roles and will include roles from the previous level in the body. The number of roles defined at each level must be at least one fewer than the level below it. 3. For each of the roles in the previous level, we will create a statement whose type is randomly selected based on the given parameters. If we select Type-2, the role itself is used as the body of the new statement. If we select Type-4, the role appears in an intersection in the body of the statement along with another role randomly chosen from the set of already defined roles. If we select Type-1, we create two policies: a Type-1 with a randomly selected principal as the body and a Type-2 with the role as the body. For Type-3, we do the following: (a) Create a linked role of the form . 1 . 2 where is a randomly selected principal and 2 is the role name from the role we are currently working with. This linked role will appear in the body of the new statement. (b) Create ( -1) Type-1 policies of the form . 1 ←-where is a randomly selected principal and is the parameter described below. (c) Create one Type-1 statement of the form . 1 ←-where is the principal from the role we are currently working with. For each statement statement written, we advance use the next available role from the new level as the defined role. When we reach the end of the list of new roles, we start again from the beginning. 4. Repeat from step 2 until we arrive at a level with only one defined role.

Parameters for the Policy Set Generator.

1. Number of principals, : the number of principals that are eligible to be members of the base roles. Principles defining roles within the tree are also randomly drawn from this range. 2. Number of base roles, : the number of base roles for the hierarchy. 3. Principal inclusion percentage, : the probability that any given principal is a member of any given base role. This results in an approximately normal distribution of the number of principals in any base role with mean and variance (1 -). 4. Level-to-level reduction percentage, : the reduction in the number of roles defined from one level to the level above it. This governs how quickly the hierarchy narrows, controlling the number of levels and correspondingly the maximum height of any credential chain. 5. Chain die-off percentage, : the percentage of roles at each level which will not appear in the body of any credentials defining the next level of roles. This controls the variability of chain height; a value of 0.0 will result in all chains reaching the maximum height while a value of 0.5 will result in approximately half of the remaining chains ending at each level. 6. Type-1 percentage within the hierarchy, 1 : the percentage of credentials defining roles within the hierarchy that are Type-1. Note that this percentage does not include Type-1 credentials that define the base roles. This parameter can be used to account for management or other special principals who may be included directly in a mid to high level role. 7. Type-3 percentage within the hierarchy, 3 : the percentage of credentials defining roles within the hierarchy that have linked roles as their body. 8. Number of principals in the intermediate role of every linked role, : whenever a linked role is created, this many principals are randomly picked from existing roles in the hierarchy and are added to the intermediate role of the linked role. There is no guarantee that one of these principals will define a role whose role name matches the second role name from the linked role. 9. Type-4 percentage within the hierarchy, 4 : the percentage of credentials defining roles within the hierarchy that have intersections as their body.

All credentials within the hierarchy that are not Types 1, 3, or 4 are Type-2.

Scenarios. The following scenarios are possible real world examples which might require policies that is well suited for describing. These policies may rely heavily on delegation of authority, which is relatively flexible and straightforward in . Credentials storage is likely to be distributed in two of the scenarios, which is designed for, while the other two may have more centralized storage. Parameters and constraints were not used in these scenarios due to the complexity involved their generation. However, our benchmarks show that the performance impact of using parameters throughout a set of policies similar to the government department scenario described below is minimal, generally resulting in less than a 10% increase in time to complete a query, including the retrieval of credentials from remote repositories.

Grid Scenario. Several virtual organizations (VOs) collaborate to create a grid infrastructure. Each VO has a separate internal policy. A small set of policy statements is created to govern access to the various grid tools by VO members; these policies reference one or two top level roles from each VO. Additionally, some principals are members of more than one VO.

Policy sets for five VOs of different sizes were generated, with ranging from 100 to 500, ranging from 10 to 20, ranging from .25 to .4, ranging from .35 to .25, ranging from 3 to 5, 1 equal to .1, 3 equal to .05, 4 equal to .15, and equal to .1. The sets of principals used for the different VOs were nearly disjoint, with an overlap of 20 or fewer principals.

The parameters which vary depending on the size of the VO follow these expectations: first, while the average group size will increase, the overall number of groups will not increase as quickly. Second, as the size of an organization grows, specialization is likely to occur, causing the average number of roles a single principal is a member of to grow more slowly than the total number of roles available. Third, the hierarchy is likely to increase in width more quickly than height.

Credentials representing grid authorization roles were written by hand. These defined a single top level role and three roles below it, each of which included roles from the top and middle of the hierarchies for three of the five VOs.

Government Department Scenario. A large government department creates a policy that roughly resembles a single hierarchy with many management roles. Credential storage is mostly centralized.

The following parameters were used: = 10000, = .1, = 100, = .5, E-Bookstore. An electronic bookstore wishes to offer discounts to students of all small accredited universities nearby. Each university maintains its own simple policy which groups students by department and describes membership for several of the larger extra-curricular roles. Policy sets for 13 universities were generated, each with the following parameters: = 5000, = .1, = 10, = .6, 1 = 0, 3 = .02, = 3, 4 = .1, and = .1. These create very simple policies with a maximum chain height of three. The top level role for each university was University .student(), where 1 ≤ ≤ 13. The following credentials were created by hand for the E-bookstore:

1. E-Bookstore.discount() ←-AccredBoard.university().student() 2. AccredBoard.university() ←-University Social Network. A new social network is created. Every principal defines a set of friends, and each principal can see their extended network, which includes friends of friends, and their 2nd extended network, which includes friends of extended friends.

Policy sets for 10000 principals were created. Each principal randomly added principals to their friends() role from a range of 1000 principals, with each principal having a 10% chance of inclusion in the role. The range of principals that friends were selected from was occasionally shifted to give the effect that principals nearby are likely to share many friends, while principals far apart share few or no friends. Each principal, , also created the following credentials:

1. P.extendedFriends() ←-P.friends().friends() 2. P.secondExtendedFriends() ←-P.extendedFriends().friends() Repository Distribution. The repositories were spread between the University of Texas at Austin the University of Texas at San Antonio. The bandwidth available to the repositories was great enough to not be a significant limiting factor during performance testing.

For the grid and E-bookstore scenarios, all credentials for each VO or university were stored in a single repository, with all repositories being used. This simulates what one is likely to find in real world scenarios where credentials are likely to be stored centrally per organization, but the organizations themselves are likely to be distributed.

For the government department and social networking scenario, all credentials were split evenly between two repositories near the engine. For these scenarios, we felt that centralized storage of the credentials was more likely in real world examples. Users of such facilities seem unlikely to avail themselves of repositories not operated by the sites in questions.

Results

The credential repositories were run on machines of varying hardware, including a 2.13GHz Core2 with 2GB of RAM, a 4-core 2.66GHz Xeon with 16GB of RAM, an 8-core 2.0GHz Xeon with 8GB of RAM, and 8-core 3.0GHz Xeon with 32GB of RAM that was also used for the engine. All results shown below are for searches with no portion of the graph cached unless stated otherwise. With a fully cached graph (meaning all nodes have been processed), the time to execute any query, regardless of query type or which roles and principals the query was performed on, was less than 10ms.

Grid Scenario. As seen in Fig. 2, the total time required to evaluate a query by using backward search in the Grid Scenario was linearly proportional to the number of credentials processed. Because of the hierarchical nature of the policies used in this scenario, the number of credentials processed increased exponentially with respect to the maximum chain height of the query role. The average time required per credential processed was 4.25ms. The time required to perform a forward search was also approximately linearly proportional to the number of credentials processed, but the average time required per credential processed was much higher, at 250ms.

Like the backward and forward search, bidirectional search exhibited a linear increase in time proportional to the number of credentials processed. The number of credentials processed with respect to the length of the chain between the query role and principal was far fewer than backward search: anywhere from .2 to .06 the number of credentials processed during a backward search of the same height. The average time required per credential processed was in between that of backward and forward search, at 88ms. Backward search in the grid scenario generated a maximum of 400 KB/s of download traffic and 200 KB/s of upload traffic for the engine, while for- ward search generated only 45 KB/s down and 80 KB/s up. Bidirectional search generated 80 KB/s of download traffic and 80 KB/s up. CPU utilization on the engine remained at or above 90% during backward search. During forward search it was much lower: usually less than 10%; CPU utilization during forward search also had a downward trend as a search progressed. Although bidirectional searches initially showed greater CPU utilization than forward searches, they progressed more slowly as the search continued and CPU utilization became only slightly better than that of forward search.

Government Department Scenario. As seen in Fig. 2, backward search performance in the Government Department Scenario was similar to that of the Grid Scenario, but with a slightly lower time required per credential processed at 4ms. CPU utilization and network traffic was similar to that of the Grid Scenario. Bidirectional searches took an extremely long time to complete. In the case that the query principal was not a member of the query role, a single search took about 90 minutes and processed about 90000 credentials, averaging about 60ms per credential processed. E-Bookstore Scenario. Backward searches in the E-Bookstore scenario completed in 9 seconds on average when performed on University.student() roles with an average of 3ms required per credential processed; when the query role was E-Bookstore.discount(), the time required per credential increased to 6ms. Forward and search performed more poorly than in the grid and government department scenarios, requiring 275ms per credential processed. Bidirectional search was slightly better than the government dept. scenario, at 50ms per credential processed.

Social Networking Scenario. For backward search, queries on friend(), ex-tendedFriend(), and secondExtendedFriend() queries took .5, 28, and 490 seconds on average, and average time per credential processed was was 5.6, 3.5, and 2.8ms, respectively. CPU and network utilization remained extremely high, similar to the other scenarios.

Forward search performed extremely slowly, with low CPU utilization and network usage. The completion time for a single query was roughly two hours. After extended periods of time, the forward search slowed to a rate of three credentials processed per second.

Bidirectional search performed moderately in the case that the query principal was a member of the query role; for friend() and extendedFriend() roles, queries completed in about 10 seconds, while secondExtendedFriends() queries completed in about 20. When the query principal was not a member of the query role, bidirectional searches initially had moderate CPU utilization and network traffic before degenerating into performance slightly better than forward search.

Analysis

As the results from the performance tests show, the difference in response times for queries with and without graph caching is staggering. At the scale of these tests, it is clear that caching all or most of the credential graph makes an enormous difference to the expected query response time. When the graph is fully cached, query response times are consistently extremely low. We suggest techniques for maintaining such a cache in the next section.

The amount of time required to complete a query increased nearly linearly with respect to the number of credentials processed for all three types of queries across all scenarios. The average processing time per credential did decrease slowly for backward search as the number of credentials grew, while the average time per credential increased slowly for forward and bidirectional searches.

Backward search performed very similarly regardless of the scenario. Its performance appears to be almost entirely CPU bound, although network traffic could become a limiting factor in some cases. The primary factor which affected backward search performance was the number of roles overall; the percentage of Type-3 and Type-4 credentials also impacted performance to a lesser degree.

The differences in performance between forward and backward search were unexpected and quite large. There are two primary differences which may account for the disparity:

First, backward searches create only role nodes, while forward searches create both principal nodes and role nodes. In these scenarios, the number of principals greatly exceeds the number of roles. The large increase in the number of nodes requires much more memory and substantially increases the rate of cache misses, which results in the extremely low CPU utilization seen during forward searches.

Second, backward searches need to perform extra work only to deal with linked roles and intersections when a Type-3 or Type-4 credential is encountered while processing a role node. By contrast, to handle linked roles a forward search must create new nodes and perform several actions for each node processed.

For these reasons, forward search is unable to effectively utilize the CPU or generate network traffic; memory access time is the limiting factor.

Because bidirectional search runs both a forward and a backward search, it suffers from the same performance problems as forward search. Although the number of credentials processed are often low when the query is a success, the average time per credential processed is still high. Therefore, it cannot be depended upon as a means of graph creation.

The average processing time per credential grows faster with the number of credentials in the forward search than in the backward search. This is because Type-1 credentials tend to constitute above 90% of the number of credentials in a policy, processing a greater number credentials in a forward search generally results in the creation of many additional principal nodes, and consequently, poorer performance. On the other hand, an increase in the number of credentials processed in a backward search results in the creation of relatively few role nodes whose performance impact does not outweigh the loss of performance overhead during earlier portions of graph construction.

Optimizations

Because the performance of an system is largely dependent on fully caching the graph, optimizations should concentrate on caching the graph quickly and efficiently. Due to the performance differences between forward, backward, and bidirectional search, the quickest way to build a complete graph is through backward searches on all roles that are used for authorization purposes. By avoiding forward and bidirectional searches entirely, performance is significantly enhanced. However, for this strategy to work, all credentials chains must be backward-traversable [START_REF] Li | Distributed credential chain discovery in trust management[END_REF]. This requirement is not particularly onerous, but may be difficult to maintain in loosely organized, widely distributed scenarios. Without this guarantee, designing an efficient caching strategy is more complex.

Additionally, because backward search is primarily CPU bound, converting the currently single-threaded engine to a multi-threaded model is expected to improve performance significantly.

Multiple Engines. Because revocation and expiration become frequent for large policies, their effect on query response times must be minimized. Currently, when a credential expires or is revoked, our only available strategy is to rebuild the entire graph without that credential. An engine that is busy constantly rebuilding the graph will have no way to respond to queries in a timely manner. Although one possible solution to this problem is to devise a way to alter the graph so that the work required to handle credential invalidation is lessened, the frequency of these events and the expected time to deal with them still prevents the engine from responding to queries quickly.

An alternative strategy runs multiple engines simultaneously. One engine is dedicated to answering all queries with the latest complete version of the graph. For each credential invalidation, a separate engine constructs a new version of the graph in the background; when the new graph is complete, that engine assumes the role of servicing queries while the engine it replaces waits to build a new version of the graph after the next credential invalidation. The number of engines running concurrently could grow to accommodate increased workloads.

Conclusion

In this paper, we announced the availability of an open source implementation of and used it to test and analyze the performance of systems in a large, distributed environment. The results of these tests show that low response times for role membership queries may only be achieved through thorough caching of the graph. Furthermore, the characteristics of the backward search algorithm make it a much better candidate for graph creation than either forward or bidirectional search due to more efficient memory usage. Utilizing this knowledge, we have proposed strategies for cached-graph management that will allow to achieve the query evaluation-response times necessary to make it a viable authorization solution in distributed environments that benefit from easy delegation of authority.

4 Fig. 1 .

 41 Fig. 1. Depiction of a constraint created for the credential shown

Fig. 2 .

 2 Fig. 2. Total Query Processing Time for: Backward Search in the Government Scenario; Backward and Bidirectional in the Grid Scenario.

Fig. 3 .

 3 Fig. 3. Average processing time per credential among the three query types.

  2 , an association table is used to associate PCOs in 2 with PCOs in 3 . When processing a parameter, the table is used as follows. Let us call the PCO in the parameter's 2 entry 2 and that in the parameter's 3 entry 3 . When the table does not contain an association for 2 , the (simplified) conjunction of 3 and 2 is computed, entered into the table in association with 2 , and is used to replace 3 in the constraint being constructed ( 3 ). (Note that when conjunctions are unsatisfiable, this is detected and handled at a higher level in the algorithm as this leads to greater efficiency.) When the table does contain an associated PCO, call it

				′ 3 , we check to see whether	′ 3 and
	3 are one and the same object. If so, no further action is required. Otherwise,
	the (simplified) conjunction of	2 ,	′ 3 , and	3 is computed, entered into the
	table in association with	2 , and used to replace	3 in the constraint being
	constructed ( 3 ).

Sorts resemble a very simple notion of variable types; each variable is assigned to exactly one sort, which defines the set of values over which it can range. This set is called the carrier of the sort.

= .2, 3 = .1, = 10, 4 = .15, and = .1. These represent a more complex policy, with a greater number of linked roles and intersections. The maximum chain height was seven.