Conflict Resolution Using Weighted Rules in HFST-TWOLC

In this article we demonstrate a novel way to resolve conicts in two-level grammars by weighting the rules. The rules are transformed into probabilistic constraints, which are allowed to compete with each other. We demonstrate a method to automatically assign weights to the rules. It acts in a similar way as traditional conict resolution, except that traditionally unresolvable left-arrow rule conicts do not cause lexical forms to be ltered out. The two-level lexicon and probabilistic twolevel grammar are combined using the new transducer operation weighted intersecting composition. The result is a weighted lexical transducer. To the best of our knowledge, this is the rst time probabilistic rules have been used to solve two-level rule conicts. The possible applications of probabilistic lexical transducers range from debugging a wed two-level grammars to computer-assisted language learning. We test our method using a twolevel lexicon and grammar compiled with the open source tools HFST-LEXC and HFST-TWOLC.

Introduction
In a two-level phonological grammar the rules are parallel constraints whose joint effect determines the surface realizations for lexical analyses. A valid correspondence between a lexical string and its surface realization has to be accepted by all of the rules, otherwise it is filtered out (Koskenniemi, 1983).
Situations where correspondences are filtered out because two rules require a lexical form to be realized in two different ways are called rule conflicts. In the worst case, all surface forms corre-sponding to a lexical analysis are lost and the analysis is filtered out by the grammar.
Conflict resolution is an automated mechanism in two-level rule compilers, which attempts to find conflicting rules and modify them so that no lexical analyses are lost. Traditional conflict resolution can resolve arbitrary conflicts between rightarrow rules, but it is limited to special cases in the case of left-arrow rule conflicts as we explain in section 2.1.
Instead of traditional conflict resolution we propose a method, which builds on making the whole two-level grammar probabilistic in section 2.2. The rules become weighted violable constraints, which are allowed to compete against each other.
Weighting rules is not a new idea. All statistical parser use the idea. However, casting conflict resolution in probabilistic terms is new. We are not aware, of other systems, which use probabilistic rules for conflict resolution. In finite-state syntax, weighted parallel constraints have been considered by Voutilainen (Voutilainen, 1994). Voutilainen considered the use of weighting to order sentence parses by typicality. The weights could be assigned by a linguist or corpus data could be used. The method he proposes is based on penalty weights like our method.
In section 3 we propose a general method for assigning weights to rules. In section 4 we use this method to weight rules in a way, that parallels traditional conflict resolution, when all rule conflicts are solvable. The difference between traditional conflict resolution and our method is, that our method preserves lexical analyses for surface forms even in conflict situations, although these might not have a preferred order, since their weight may be the same. The rule writer may choose to refine the weighting we propose either according to her intuition or by using corpus-data.
The applications of the new kind of conflict resolution might include identifying typical gram-matical errors made by children and language learners or in information retrieval, since the grammar becomes violable and some erroneous forms are retained, although these are less probable, than their correct counterparts. A very significant use is for debugging two-level grammars. Since forms are not filtered out in a conflict situation, the linguist, who is writing the two-level grammar gets a clearer picture of the way the grammar is broken.
In section 5 we use a new transducer operation, weighted intersecting composition to combine a two-level lexicon and a two-level grammar. Weighted intersecting composition allows the weights in the rules to be passed to the resulting lexical transducer. The operation has been modelled on unweighted intersecting composition, which was introduced by Karttunen (Karttunen, 1994).
We test our method using an example lexicon and grammar in sections 6 and 7. The example concerns gradation of stops in Finnish. The example lexicon was compiled using the open source two-level lexicon compiler HFST-LEXC 1 and the example grammar was compiled using the open source two-level grammar compiler HFST-TWOLC 2 . Both compilers belong to the finite-state morphology toolkit HFST Morphology Tools 3 .

Rule Conflicts
Rule conflicts occur when two-level rules require, that a lexical symbol is realized in two different ways in the same context. Conflict resolution is a process, which aims to modify the two-level grammar in such a way, that rule conflicts vanish. Traditionally it has been restricted to conflicts between several right-arrow rules or two leftarrow rules. We shall make the same restriction, although conflicts occur in other types of rulesets as well (Yli-Jyrä and Koskenniemi, 2006). languages. E.g. the right-arrow rules a:b ⇒ c ; and a:b ⇒ d ; are in conflict. Since the first one limits the realization of lexical a as surface b into contexts where c precedes and the second one into contexts, where d precedes, the result is that a can't be realized as b anywhere. The reasonable way to interpret the two rules, is that a:b should occur either in context c or context d because we may assume, that the grammar writer intends all rules to be true. Similar considerations apply to other right-arrow rule conflicts as well. Such conflicts may therefore be resolved by joining the conflicting rules into one rule whose context is the union of the contexts of the conflicting rules. Our example becomes

Traditional Conflict Resolution
Obviously right-arrow conflicts may always be resolved.
In contrast to right-arrow rule conflicts, leftarrow conflicts may not always be resolved. Two left-arrow rules concerning the same lexical symbol are in conflict if they require the symbol to be realized in two different ways in the same context. Consider the rules a:b ⇐ X ; and a:c ⇐ x x ; where X = {x, y, z}. In the context x x the rules have conflicting requirements.
Here the context of the second rule is subsumed by the context of the first rule, so the second rule may be considered a special case of the first rule (Karttunen et al., 1987). The first rule applies everywhere in the context X except in the context x x. This means that the rule conflict is resolved by modifying the first rule by subtracting the more specific context x x from the more general X . This kind of left-arrow conflicts reflect the fact, that linguists tend to split rules into general tendencies and absolute laws, which are exceptions to those tendencies.
We use the general restriction (later GR) operation introduced by Yli-Jyrä (Yli-Jyrä and Koskenniemi, 2004) to compile two-level rules. Rule contexts are compiled into regular expressions, which allows us to operate on them with regular expression operations. Hence, it is possible to resolve a left-arrow conflict by subtracting the context of a sub case rule from the context of a more general rule. It is also possible to resolve right-arrow conflicts simply by uniting them into one rule. Its context is the union of the contexts of the conflicting rules.
Left-arrow conflicts between rules neither of which is a sub case of the other were not resolved in the first two-level rule compiler (Karttunen et al., 1987). Nor are they resolved by the current Xerox two-level compiler (Karttunen, 1992). The result is that lexical forms are filtered out by the grammar.

A Probabilistic Interpretation of Rule Conflicts
Consider a grammar, which has two left-arrow rules R 1 and R 2 concerning the lexical symbol x.
The rules are defined x:y ⇐ C 1 and x:z ⇐ C 2 respectively. If the set C 1 ∩ C 2 is nonempty, the rules are conflicting. 4 Clearly rule R 1 should hold vacuously in the set C 1 \ C 2 and so should R 2 in the set C 2 \ C 1 . We may interpret the situation probabilistically. The rule R 1 should apply with probability 1 in the context C 1 \ C 2 . Similarly rule R 2 should apply with probability 1 in context C 2 \ C 1 . Since we have no information concerning the relative importance of R 1 and R 2 , it is reasonable to assume, that the rules have equally high probability p of applying in the context C 1 ∩ C 2 . Traditional conflict resolution corresponds to assigning p the value 0, but one could equally well argue, that p should have the value 0.5. In a situation where the rule R 1 is stronger than the rule R 2 it may be given higher probability than R 2 , which means that surface realizations derived using rule R 2 are more likely than realizations, which are derived using rule R 1 .
Generalizing the idea of rules as tendencies and absolute laws, we get a range of rules with different probabilities of applying, from laws which always hold to less certain tendencies. Compiling a lexical transducer becomes the equivalent of letting the different rules compete with each other, which results in an ordering of possible analyses for lexical forms.

Conflict Resolution Using Weights
We propose a new method of resolving conflicts, which is based on the idea of making the two-level rules probabilistic. Instead of giving a probability for each rule, we assign a penalty weight for breaking a rule. The principle is, that breaking a more likely rule should always result in a higher penalty, than breaking a less likely one.
The rule R x:y ⇐ C is combined with a penalty weight transducer using weighted union of transducers (Allauzen et al., 2007), so after conflict resolution it becomes the weighted rule R WEIGHT denotes the language of all strings of feasible pairs, where every string receives weight WEIGHT.
In the transducer R , correspondences which break the rule R receive weight WEIGHT and correspondences which do not break the rule R receive weight 0. This happens, because we use the tropical semi-ring to represent weights, as we will see in section 5. In the tropical semi-ring addition of weights, performed by the weighted union, corresponds to taking the least of the weights.
The two-level grammar is equivalent to the intersection of the weighted rule transducers. The best paths corresponding to a surface realization for a lexical string are those for which the sum of the weight given by each rule transducer is the lowest.
When two rules compete, the correspondences which break the rule whose penalty weight is lower get a lower penalty than the ones that break a rule with a higher penalty. Conflict resolution thus becomes the task of finding suitable weights for the rules in a grammar.

Compiling Two-Level Rules and Weighting them
We now demonstrate a way to weight the rules in a two-level grammar, which will give the same results as ordinary conflict resolution, when all rule conflicts are solvable. The process may be completely automated. The right-arrow rules will be compiled in the same way as usual, but we need to find penalty weights associated with the left-arrow rules in the grammar.
We precompile the contexts of all x:y ⇐ L R ; into context expressions L Σ * R, where Σ is the alphabet of the two-level grammar. We define a relation context-inclusion in the grammar. We say that context-inclusion holds between two rules R 1 and R 2 ,whose centers have the same lexical symbol, x:y ⇐ Cl 1 Cr 1 ; and x:z ⇐ Cl 2 Cr 2 ; iff Context-inclusion is a partial ordering, so we use the symbol < for it and write R 1 < R 2 .
Let {X 1 , ..., X n } be a set of rules in the twolevel grammar. The set is a chain beginning at X 1 , iff X 1 < ... < X n . Specifically any set of size 1 is a chain.
We now give each rule R a penalty weight according to the length of the longest chain beginning at R.
Suppose there is a conflict between the rules R and S. If the conflict is resolvable and R is a sub case of S, then R < S. Since every chain beginning at S may be extended to a chain beginning at R, breaking the rule R will result in a greater penalty weight than breaking the rule S.
Conflicts, which couldn't be solved using traditional conflict resolution will not result in filtered out lexical forms using our conflict resolution, even though there might not be a preferred order for realizations of a lexical form. This happens because all left-arrow rules are violable.
Other ways of assigning weights for rules might be conceivable, e.g. using corpus data to extract probabilistic two-level rules or to extract lexical contexts in the form of n-grams. This could also be used to fine-tune a grammar obtained using our method. In addition the linguist writing the two-level grammar could assign penalty weights for breaking the rule. The penalty weight v preassigned by the linguist and the weight w given by our conflict resolution may be combined. The actual penalty weight received for breaking the compiled rule becomes v ⊗ w, where ⊗ is the multiplication of the weight semi-ring.
A limitation of our system is, that a correspondence violating a rule receives the same weight surface form 1 ay 1 az 1 bz 2 by Table 1: surface forms corresponding to ax.
penalty weight regardless of how many positions in the correspondence violate the rule, since equal penalty weights are assigned for all correspondences violating a rule. This might not be a problem in practice, since correspondences exhibiting the same rule conflict multiple times may be rather rare.
Other possible limitations stem from complex rule-interferences. E.g. let the alphabet Σ be Σ = {a, a:b, x:y, x:z} and consider the somewhat strange rules x:y ⇐ a: ; and x:z ⇐ a:b ; of a two-level grammar with alphabet Σ.
The second rule is a sub case of the first one, so our method of weighting the rules will give it a higher penalty weight. If these are the only rules for the lexical symbol x, then the first rule gets penalty weight 1 and the second gets penalty weight 2. Now, consider the rule a:b ⇐ x:y ; If it is the only rule concerning the lexical symbol a, it will get the penalty weight 1.
The conceivable realizations for the lexical string ax ordered by weight are given in Table 1.
Among the three best correspondences, there is one, which breaks the third rule, which was not in a left-arrow or a right-arrow conflict with either of the other rules. This example is rather contrived and we are not sure, whether actual phonologies contain these kinds of phenomena.
A further limitation of our system is that, it is possible that surface forms which would not have received any analyses, if they would have been compiled in the normal way, receive analyses. Since our system deals with relative weights, it is not possible to see, if a form is likely to be a good surface form for a lexical form, without generating the best surface forms corresponding to the lexical analysis. We will see an example of this in section 7

Combining a Two-Level lexicon and a Probabilistic Two-Level Grammar
As usual, we combine the two-level lexicon and rules to form a lexical transducer. Traditionally this can be done using the operation intersecting composition introduced by Karttunen (Karttunen, 1994). Since our rules are weighted, we need to modify the operation slightly. We call the modified operation weighted intersecting composition. The result of unweighted intersecting composition is equivalent to composing the two-level lexicon with the intersection of the two-level rules. The operation was developed, since sequential intersection followed by composition could be rather slow, as computing the intersection of the rule transducers is a resource demanding operation. In intersecting composition the composition and intersections are carried out simultaneously. This allows both the lexicon and the rules to limit the size of the result of the operation without large intermediate results.
Weighted intersecting composition is a modification of intersecting composition for weighted lexicons and rules. The result of the operation is equivalent to weighted composition of the lexicon and the weighted intersection of the rules as defined in (Allauzen et al., 2007).
A probability p can be interpreted as a penalty weight w, using the standard conversion w = − log (p). This means that high probabilities corresponds to low penalty weights.
We use the tropical semi-ring T = (R + ,0,1, ⊕, ⊗) to represent penalty weights. Here R + are the reals,0 = ∞,1 = 0 and the binary operations and x ⊗ y = x + y respectively. The operation + is the regular addition of the reals.
A weighted transducer has one initial state The weight of the string x:y is w(P x:y,T ).
Let L be a weighted two-level lexicon and R 1 , ..., R m weighted two-level rules. We mark their intersecting composition by L •∩(R 1 , ..., R m ).

It contains paths corresponding to a pair-string
x:z = x 1 :z 1 , ..., x n :z n , if there are pair-strings x:y = x 1 :y 1 , ..., x n :y n , and y:z = y 1 :z 1 , ..., y n :z n , s.t. P x:y,L = ∅ and P y:z,R i = ∅ for each i. Following from the definitions of weighted composition and intersection, the weight for x:z is w(P x:y,L ) ⊗ i w(P y:z,R i ).
The weighted rule transducers are more complex, than unweighted ones, so the role of intersecting composition is even bigger in the weighted situation. It might not even be feasible to compute the intersection of weighted rule transducers.

A Test Grammar: Gradation of k in Finnish
We tested weighted conflict resolution using a small two-level lexicon and grammar. The grammar consists of three rules governing the gradation of k in Finnish. The grammar we used is a part of a two-level grammar for Finnish gradation of k, p and t, which appeared in (Karttunen et al., 1987). Gradation is an alternation in the stems of a number of Finnish words. The quality of the final stop k, p or t depends on, whether it is in an open (CV) or closed syllable (CVC). The lenited form of the stop may be a fricative, or the stop may vanish. This is determined by the phonological context.
We use K to mark the morphophoneme participating in k-gradation. In surface forms, it may be realized as 0, j, k, or v. The correspondence K:k is the default correspondence. Our rules govern the realization of K as 0, j and v.
The compiler we use is HFST-TWOLC, an open source two-level rule.compiler, whose syntax is very similar to Xerox TwolC. The sets we use in the rules are We also use the named regular where ClosedCoda is the coda of a closed syllable.
The grammar has three rules All the rules are double-arrow rules and will be split down into a left-arrow rule and a right-arrow rule (this is usually done when two-level rules are compiled).
E.g. the rule Gradation of K to 0 will be broken down into two sub-rules We call the left-arrow rules, which are formed, L 0 , L j and L v and the right-arrow rules R 0 , R j and R v according to the surface symbol in their center. Our grammar now has six rules.
The two-level lexicon we use is defined by the HFST-LEXC file. It covers the singular nominative and singular genitive cases of three words arki (workday), arka (timid) and luku (number) exhibiting different kinds of gradation of k. The surface forms, which correspond to the cases, are given by Table  2.

Weighting the rules and Compiling the Test Grammar
We proceed to identifying conflicts. There are no right-arrow conflicts, since all of the rules have different centers. There are two left-arrow conflicts, however. One occurs between the rules L 0 and L j and the other between L 0 and L v . There is no conflict between the rules L j and L v , since their contexts are disjoint.
To begin resolving the conflicts in the grammar, we first order the left-arrow rules according to context-inclusion L j < L 0 and L v < L 0 We can see that the longest chain starting at L 0 has length 1, since the context of rule L 0 is not included in any other rules. The longest chains beginning at L j and L v have length two, since both of the rules are sub cases of the rule L 0 .
We now compile the rules using the GR operation and and weight the rule transducer. Weighting the three left-rule transducers, we obtain the weighted transducers Let the transducer obtained by compiling the HFST-LexC file in the example be L. The lexicon L and the unweighted rules R 0 , R j and R v may be converted into weighted transducers, following the principle that all transitions get weight1, all final states get final weight1 and all other states get final weight0. Since all states in a weighted transducer get a final weight and only those states, whose final weight is infinite are non-final, we must give the non-final states weight0.
We now compile the lexical transducer using weighted intersecting composition. It is given by the expression The result is a weighted acyclic transducer. The pair-strings it accepts, together with their weights are shown below as pair-strings 5 .
As might be expected, the correspondences with weight 0.0 are those, that adhere to of all the rules.
The pair-strings with weight 1.0 are those, that violate the general rule L 0 , but don't violate either of the more specific rules L j and L v . One of these is arka+NOUN:0+SG:n+GEN:0 which is erroneous, but there is a better correspondence ark:0a+NOUN:0+SG:n+GEN:0 with weight 0.0. Lexical forms, which occur in a rule conflict, have no unweighted surface realizations. This is because rule conflicts are situations, where it isn't possible to avoid breaking some rule.
The form arka+NOUN:0+SG:n+GEN:0 demonstrates, that we can get slightly erroneous forms with larger weight, than the best forms. This might be useful e.g. for finding and identifying common errors in the writing of a child or a language learner.
All paths with weight 2.0 or 3.0 are erroneous. The paths with weight 2.0 violate the specific rules, but keep the more general rule. The paths with weight 3.0 violate both a specific rule and the general one. The weight 3.0 is a maximum. There are no paths with weight 5.0, although such paths might be conceivable. This is a consequence of the fact that the rules L j and L v never apply at the same time, so a correspondence can't violate both of them.
Note, that the surface form lujun of luku+NOUN+SG+GEN is not possible, since the right-arrow rule R j limits the distribution of the pair K:j. The right-arrow rules R 0 , R j and R v hold vacuously.

Discussion and Further Work
The test, which we conducted in sections 6 and 7 shows that our method of conflict resolution works. However, a more extensive test should be conducted to ascertain, that the method is practical even when used on complete two-level lexicons and grammars. There is some worry, that the lexical transducer may become rather large, because it contains both grammatical and ungrammatical forms with different weights. Complex grammars with more intricate interplay between the rules should also be tested. Since the rules are weighted, standard look up will have to be replaced by an n-best algorithm, which will slow down the parsing process.
Previously improvements to conflict-resolution have been considered by Yli-Jyrä, who proposes an unweighted method for resolving general rule conflicts (Yli-Jyrä and Koskenniemi, 2006). In addition to left-arrow conflicts and right-arrow conflicts, the method also resolves other kinds of rule conflicts, but it diverges from traditional conflict resolution, since it does not prefer rules, which are sub cases of more general rules. Still, it would be interesting to compare our method to the one Yli-Jyrä proposes especially in regard to conflicts, which represent other types of conflicts than rightarrow or left-arrow conflicts.
The uses of our method, without modifications, are probably limited by the fact, that ungrammatical surface forms may receive analyses (as was seen in section 7). It is possible to check the best surface forms matching an analysis, but this means that every surface string for which the best analysis receives a penalty greater than 0.0 requires an extra look up in the lexical transducer. This is feasible for diagnostics purposes e.g. in applications related to computer assisted language learning.
Applications, which require error tolerance could still benefit from our method. Our method might be used both in applications, which test twolevel grammars and in computer assisted language learning applications. Increasing recall in information retrieval systems, through error tolerant analysis of queries, is also a possible area of applications. Related to information retrieval is the task of finding corrections for forms, which have been tagged as ungrammatical by a speller.


s2fieldsofstudy:
Computer Science
Business

text:
On building Information Warehouses

One of the most important goals of information management (IM) is supporting the knowledge workers in performing their works. In this paper we examine issues of relevance, linkage and provenance of information, as accessed and used by the knowledge workers. These are usually not adequately addressed in most of the IT based solutions for IM. Here we propose a non-conventional approach for building information systems for supporting the knowledge workers which addresses these issues. The approach leads to the ideas of building Information Warehouses (IW) and Knowledge work Support Systems (KwSS). Such systems can open up potential for building innovative applications of significant impact, including those capable of helping organizations in implementing processes for double-loop learning.

Introduction
Effective "information management", as the means of capture and processing of information as well as accruing maximum benefit out of the available information, has become one of the greatest concerns in modern organizations. However, "information management" or IM, being an umbrella term, has many facets. One major aspect of IM involves capture and processing of "structured information" or "data". Data, representing "facts" captured or generated in the course of various operational activities, is the life-blood of an organization. Though their main utilization is in enabling the operational activities, they can also form basis of strategic activities, where the data is processed and analyzed by means various sophisticated tools to provide insights to the decision-makers. Computer-based information technology (IT) provides powerful tools and techniques in this area, including DBMS, data warehousing, OLAP, data mining, many other specialized analytic tools and various web-based technologies.
However, the data or structured information is not the only kind of information available in an organization. The other kind of information, often amounting much greater in volume as well as importance than data, is consisted of unstructured information, also called unstructured data, typically contained textual documents of various kinds. Henceforth, unless otherwise indicated, we shall call it simply information. Information is a vital class of resource to the organizations for enabling their knowledge workers [1] to perform efficiently. Information, in the stated sense, is very closely related to the knowledge possessed by individual human beings. According to Alavi and Leidner [2], "...information is converted to knowledge once it is processed in the mind of individuals and knowledge becomes information once it is articulated and presented in the form of text, graphics, words, or other symbolic forms".
Naturally, effective management of information, for supporting the knowledge workers in their tasks, is a complicated problem, which can not be dealt with information technology alone. This problem has given rise to a very active field of study, known as Knowledge Management or KM, an area of multidisciplinary study, straddling major disciplines of information systems, management, organizational learning and strategy [3], economics, philosophy and epistemology, computer science and sociology [4].
The researchers in disciplines like organizational study and management usually attempt to provide a holistic view of KM in organizations. For example, Nonaka [5] and Markus [6] proposed characterization of various activities and processes related to the knowledge-intensive works in organizations. Though, the above works do not explicitly demand use of IT-based tools rather they suggest areas where IT can contribute. The issue of using information systems (IS) for KM was more extensively discussed by Alavi and Leidner [2] from the perspective of organizational studies. They discussed the possible roles of IS with respect to helping the knowledge workers in performing effectively in four categories of knowledge processes knowledge creation, knowledge storage/retrieval, knowledge transfer and knowledge application. Unfortunately, in IT/IS community the KM-related issues seldom receive attention from such holistic viewpoint. Despite a glut of IT-based KM tools/solutions in the market, each of them typically cater some narrowlyfocused areas of activities. Even in academia, the term "knowledge" tends to be used rather indiscriminately and thus often obstruct us to address the core issues. An excellent account of such practices can be found in Wilson's article "The nonsense of knowledge management" [7] and some other articles published in the same issue.
In the following, first we examine the relationships among information, knowledge and information systems. Then we highlight some crucial requirements of the knowledge workers with respect to the access and usage of information. The following section outlines a novel scheme of information re-organization and archival, called "Information Warehouse" (IW) to facilitate the users' requirement. In the next section we outline a framework called "Knowledge work Support System" (KwSS) for building comprehensive IS environments based on IW.

Building IS for supporting knowledge work
The knowledge-intensive tasks or knowledge works (KW) are defined by Mack et al. [8] as "...solving problems and accomplishing goals by gathering, organizing, analyzing, creating, and synthesizing information and expertise".
It can be easily seen that for an organization the crucial issue is to build and maintain the capability of getting required knowledge works performed. To do so, it must engage workers with relevant knowledge and expertise. Further, it needs to provide the workers with environment and resources to carry out their works. KM is the means to achieve them effectively. As noted earlier, the scope of the problem is much diverse and broader than what can be addressed by information systems alone. Nevertheless, IS plays a crucial role of enabler for coping with the requirements of speed and scale of the activities. Here we attempt to identify possible role of IS and the essence of its link to the people and their knowledge.

"Information Systems" and "Knowledge"
As noted earlier, "knowledge" is different from "information". Knowledge, defined in Oxford dictionary as "the sum of what is known", is possessed by individual human beings. It is a tacit entity, consisted of our experience, skills, expertise, mental belief and many more components. To perform a work one needs to exercise his/her cognitive faculties, which involves application of the knowledge possessed by the individual. Performing the work, in turn, adds new knowledge and/or update the knowledge of the worker. One can convey some portion of knowledge in his/her possession by act of Articulation (which itself is a complicated exercise of cognitive abilities). The articulated or potentially articulable portion of knowledge is often called the explicit knowledge. The explicit knowledge, as Polanyi [9] famously surmised "we know more than we can tell", is usually a small portion of the full knowledge possessed by the knower.
Sharing or communication of "knowledge" among people is an indirect process. The possessor of knowledge articulates some parts of his/her knowledge, potentially useful to others. The "articulated knowledge" is "information" [2]. A recipient can receive the information and process (again using cognitive abilities) it to gain new knowledge, depending on his/her state of existing knowledge. Gain of knowledge by the recipient is manifested in his/her improved capability of performing works, where the knowledge is required. Thus, in true sense, information, rather than knowledge, is the entity amenable to sharing or communication. Recording of the information (i.e., articulated knowledge) in persistent media facilitate sharing of information beyond the boundary of spatial and temporal locality of the act of articulation.
Information Systems, as the name suggests, capable of dealing with information, actually the information (subset of the larger gamut) which are (or can be) recorded and encoded using some digital format. We must remember that the information systems have nothing to do with knowledge by themselves, unless some human possessor of knowledge uses them in their quest for information. Even so-called knowledge-based or intelligent systems, when in operation on their own, work with information and data only. For accomplishing any knowledge work of even moderate complexity, it is imperative that human workers with requisite expertise participate actively and substantially in the process. Such tasks typically fall in the categories of semi-structured and unstruc-tured decision making tasks [10] and not amenable to automation. Therefore, providing effective IS support for such tasks turns essentially into creating an environment where IS and knowledge worker can complement each others' capability in a symbiotic relationship, as envisaged by Licklider [11] back in 1960s.

Scope of IS support
The knowledge workers use information systems to deal with information, i.e., for accessing information and manipulating information for easy processing and consumption. Let us try to analyze the requirements with respect to the former. To access information, firstly they have to exist in accessible form. Some of the available information may exist only in peoples' minds, where accessing them requires interacting with the possessors. For the time being, we let us focus on the part of available information which is archived and accessible by computer-based information systems. Usefulness to the knowledge worker, of information retrieved from archive(s), crucially depends on three attributes of the retrieved information. They are (1) relevance, (2) linkage and (3) provenance. We discuss each of them below.

Relevance
The information requirement of a knowledge worker depends on various type-specific and instance-specific characteristics of the current knowledge work instance or task instance (TI). Further, the knowledge-intensive tasks are never monolithic or atomic in nature. They are consisted of a set of interrelated activities, often fairly diverse in nature. At any given time, the worker is typically engaged in performing an activity as part of a larger KW instance and his/her information requirement, both content-wise as well as patternwise, is influenced heavily by the nature of the current activity. However, the documents containing the information, whether distributed across various systems or archived and managed with state-of-the-art Content Management Systems (CMS), usually have information relevant to the current activity embedded in small portions of each of a set of documents. With the advanced search technologies of recent time, we can identify fairly precisely the set of documents. But it is still left to the human worker to peruse each (or as many as humanly possible!) document, find out the relevant piece of information, understand, interpret and synthesize it with other pieces of information. Without doubt this process of information gathering and processing makes a huge demand on the time and cognitive ability of the worker.
The challenge, the IS researchers should address in this front, is to present to the worker, based on the query and activity context, not a set of whole documents within which useful pieces of information are distributed, but relevant information extracted from the containing documents. As we shall see later there are several conceptual as well as technological issues to be addressed to realize this capability.

Linkage
The value or usefulness of a piece of information increases manyfold when it can be associated other related pieces of information and studied together. Let us consider an example: A worker is tasked to prepare a plan of a marketing campaign of a set of products. While preparing the plan, at one stage she is trying to work out the feasibility of offering some incentive to customers for boosting the sale of some products. The incentive can be of several kind, e.g., a discount scheme, an easy installment scheme etc. While studying the problem, she accesses archived information on other discount schemes offered by the company as part of earlier marketing initiatives of similar nature. However, the information that during that campaign so and so products were sold at x% discount is of little value to her. She would like to know the other pieces of related information, such as what were the sales and profit targets from the discount sales, whether the implementations of the schemes met the targets, if not what were the reasons, is there some interrelations among sales of different products and many other pieces of related information.
An effective information system must offer the ability to the user the to find and navigate the links between related pieces of information. The system, along with the information, must be able to provide the linkage among the pieces of information based on various types of relationships. One of the technological challenges towards providing the linkage is one of information integration. The state-of-the-art in this area is reviewed by Bernstein and Haas [13]. Though they are able to identify several potentially important technologies, these technologies are usually applied in specialized applications. To achieve the level of integration support required for providing effective linkage information, we need to build a systematic approach to guide us on the application of the individual technologies.

Provenance
Provenance of a piece of information encompasses related information on how, where, what, when, why, which and by whom the information has come into being. It form the basis of validation of the information. Its importance in the domains like scientific research [12], law enforcement etc. are well-established. However, in other domains also increasing importance of provenance can be related to the various compliance requirements. Apart from such legal/regulatory requirements, easy access to provenance can be of great value to the knowledge workers. Ability to check the provenance of information assures a worker of the quality of the information. Further, in scenario of collaborative works, the information, containing some crucial arguments, prepared by a co-worker can be examined much rigorously using the provenance and linkage facilities to go beyond the upfront information, into other pieces of information those form the premises of the arguments. Thus the contributions of the workers will be much more effective in their exchange of information and collaboration.
Incorporating facilities for supporting provenance in the information system is fairly complex task. It requires ability of the system to be aware of other systems, including databases, data analysis systems, ERP, Internet etc. in the organizational environment, as well as ability to communicate to many of them. Further, identity of the workers, working on various systems and responsible for development of a piece of information, also need to be associated with the information itself.

The Information Warehouse
To the best of the authors's knowledge there are no published work focusing on the above aspects of information access together. To address the above issues together we need to look at the problem of information archival and usage from a different perspective. In the following we attempt to analyze the problem and propose a new systematic approach to reorganization and archival of the information originally available in textual documents. Let us call the proposed approach and its potential implementations, borrowing in spirit from Data Warehouse, the Information Warehouse or IW.
We are mainly interested in the information contained in textual documents which are typically produced as the end products (strategy, plan, policy, manual etc.) as well as intermediate products (reports, notes, memos, minutes of meetings, consultation papers etc.). These documents are prepared by human workers for consumption of other human workers. Typically, each of them strive for completeness, so that the content gives a coherent picture of the issue under consideration. They refer to other sources of information which are used as premises for the arguments made in the document. Overall, the content of a document can be seen as an intellectual aggregation of many pieces of information and result of articulation of knowledge by the author of the document. Let us identify the organization of information in documents as the Articulation View of Information (AVI).
In light of the requirements laid above, it can be easily seen that the AVI is hardly optimal in satisfying the need of the workers as outlined in previous section. Let us call the view of information capable of satisfying the users' requirements the Exploration View of Information (EVI). It is evident that there are significant differences between these two views. So, the problem is essentially one of computing the EVI, in response to user requirements, from the information originally available in AVI. Figure 1 depicts the situation. However, creating required EVI on-the-fly from AVI is, if not impossible, extremely difficult. One feasible solution is to build an archive, the Information Warehouse, where the original information is re-organized to form an intermediate Bridge View of Information (BVI). The bridge view should be designed such a way that the various EVI can be easily computed on-demand from it. Further, it should be easy to devise means and methods to convert information in articulation view to corresponding bridge view. Let us call this process of conversion as the Transcription process. In the following we expand the characteristics of the Bridge View and the Transcription process.

Bridge View of Information (BVI)
Though there is no unique approach to build a bridge view of information, here we propose a bridge view in form of a network of Information Elements (IE). The IEs are objects, specialized to serve as containers of various types information developed in the course of performance of knowledge work instances. The IEs are interconnected through two types of links, the creational links and the reference links, and we call the organization as the "Creational and Reference Network" or CaRN view in short. A creational link joins two IEs when the information content of one is created to satisfy the need of creating the content of the other. On the other hand, a reference link exists between two IEs when the content of one is used, but not explicitly created to cater the need of the other. It is clear that the creational links reflect also the relationships between pieces of information developed by activities performed as part of the same KW instance. This allows us to define macro elements of the CaRN as the Task Instances or TIs which contain all information developed during performance of a KW instance. The structure of CaRN is depicted in Figure 2. It can be noticed that as consequence of above definitions, the creational links are allowed to form between IEs who belong to the same TI. On the other hand the reference links are free to cross the TI boundaries to associate IEs belonging to different TIs.
Implementations of the archival of information in CaRN view can be accomplished with relational databases, XML databases, content management systems or some hybrid of them (we are currently involved in testing several options). However, irrespective of implementation technology adopted, it can be easily perceived that in this scheme, access to the the content of IEs and their interconnections can provide the user with information with high relevance along with capability of navigation to other contextual information using the edges of the IE network. Further, IEs being objects, they have fields along with one containing the principal content, other fields containing various provenance information. While creating the IEs, the provenance information can be easily stored in related fields. Thus provenance information can also be accessed by the user in the similar way as other parts of information. One more important advantage of this scheme is the possibility of using various search and analysis techniques developed in the field of graph/network analysis to analyze the the content and structure of the archived information.

The Transcription process
As pointed out earlier, the information is originally available in form of text documents (AVI) developed in the course of and as results of performance of knowledge work instances. To reorganize the information in the bridge view, the first step is to identifying sets of documents corresponding to individual KW instances. Next, the transcription process aims to build TIs in the bridge view for the KW instances from corresponding sets of documents. The task involves isolating pieces of information from the documents, discovering their interrelationships and map them into appropriate types of IEs and their linkage patterns. Undoubtedly this is a non-trivial task. To accomplish this we need to understand the characteristic of the knowledge work types in terms of their constituent actions, their information requirements and interdependencies. Given this understanding it is possible to build KW type-specific templates or maps and other artifacts. These can be used in several ways. In the scenario where an IW based system is already in operation, methods and processes can be established, where the workers using user-friendly interfaces, customized with help of the relevant artifacts, can easily articulate and resulting information is organized and archived in IW. The other scenario emerges when we want to transfer information from already existing documents to the IW. Here the artifacts can be used to build tools for transcription performed by the human transcribers manually or by partially automated Natural Language Processing based Text Analysis techniques. Depending on the particulars of the environment, a mix of both scenario may emerge.
Implementations of the transcription processes have several organizational/managerial aspects. One of them is when to convert the information to into bridge view. The choice can be anything between "as soon as the original document(s) become available" and "when the information embedded in the documents is asked for first time". Further, the quality/accuracy of the information accessed is of crucial importance for their usability. Hence, to ensure the quality of the the information in bridge view it is essential to embed proper controls and practices for oversight within the process.

Information Systems based on IW
The information warehouse raises possibilities of developing many exciting IT applications, including those addressing various aspects of complex information integration problems. However, here we concentrate on the bigger picture and outline the idea of a new class of information systems, the Knowledge work Support Systems or KwSS, based on IW. As the name suggests, the systems' design can facilitate the workers on the basis of KW types (e.g., decision-making, planning, research, policy-making etc.) to be performed in their respective domains (e.g., finance, retail, healthcare etc.). This approach offers us the scope to modularize the system design process by concentrating on each of the KW types to be supported separately. This involves including KWspecific information, such as various activities and their interrelationships in context of the respective KW types, in the system. We can also include the "domain vocabulary" in form of thesauri or ontology. Use of these information enable us to annotate the archived information and present the retrieved information in easily understandable way to the end-user. Further, we can use these information to provide means for building powerful semantic-based search and processing capabilities of the archived information.
The KwSS approach of building information systems can facilitate solution of many crucial problems currently faced by organizations. For example, such systems can provide opportunity of building efficient expertise locator [15] applications within large organizations. The information in the IW can be used by the application to analyze the workhistory/performance of the workers and build their accurate expertise profiles. There are numerous other possibilities. The core strengths of these systems stem from two sources. Firstly, the proposed scheme of organization of information in IW allows us to archive and retrieve information with high relevance, contextual linkage and verifiable provenance. Secondly, the KwSS provides a framework of systematically (and incrementally, if required) implementing the IW and information delivery infrastructure, where a higher level of organization of archived information along with related explanatory and semantic information is realized.
To highlight the above points, here we discuss another possibility of far-reaching impact. Organizations frame their guiding principles in forms of artifacts like policies, best practices, manuals etc., which form the basis of how the businesses are conducted. Preparation of such guiding artifacts are extremely knowledge-intensive works and depend on the expertise and information available at the time of their formulation. However, in today's dynamic world, the validity of the information and their interpretations, which form premises of those guiding principles do not remain same over the time. Thus, there is a crucial need to periodically examine them and updating them to suit the current environment. Without doubt, this is an extremely difficult task, often associated with the double-loop learning [14] capabilities of the organizations. In the KwSS approach, preparation of these important artifacts are treated as KW types and sophisticated support for performing them can be built into the system. This will allow the workers to easily access the archived information of earlier instances of similar tasks available in IW and analyze in light of the new information.

Conclusion
In this paper we have attempted to examine the problem of information access and usage by knowledge workers in organizational setups from a different perspective and provide a outline of information systems capable of addressing several issued currently not addressed adequately. We proposed the scheme of building Information Warehouse, embodying a new approach for archival and accessing information originally available in textual documents. The capabilities of IWs can form the basis of various integrated information management platforms. Further, we have proposed the KwSS framework of building IW based systems, which can exploit full power of the IWs as well as extend it into developing comprehensive support for myriad types of knowledge works across domains. They also give rise to many exciting possibilities of building systems with deep impacts in the organizational scenario. Currently I am working with a team researchers and engineers in implementing and enhancing a IW and KwSS prototype.


extfieldsofstudy:
Computer Science
Medicine

text:
Sector and Sphere: the design and implementation of a high-performance data cloud

Cloud computing has demonstrated that processing very large datasets over commodity clusters can be done simply, given the right programming model and infrastructure. In this paper, we describe the design and implementation of the Sector storage cloud and the Sphere compute cloud. By contrast with the existing storage and compute clouds, Sector can manage data not only within a data centre, but also across geographically distributed data centres. Similarly, the Sphere compute cloud supports user-defined functions (UDFs) over data both within and across data centres. As a special case, MapReduce-style programming can be implemented in Sphere by using a Map UDF followed by a Reduce UDF. We describe some experimental studies comparing Sector/Sphere and Hadoop using the Terasort benchmark. In these studies, Sector is approximately twice as fast as Hadoop. Sector/Sphere is open source.

Introduction
By a cloud, we mean an infrastructure that provides on-demand resources or services over the Internet, usually at the scale and reliability of a data centre. A storage cloud provides storage services (block or file-based services); a data cloud provides data management services (record-based, column-based or object-based services); and a compute cloud provides computational services. Often these are stacked together to serve as a computing platform for developing cloud-based applications.
The implicit assumption with most high-performance computing systems is that the processors are the scarce resource, and hence shared. When processors become available, the data are moved to the processors. To simplify, this is the supercomputing model. An alternative approach is to store the data and to co-locate the computation with the data when possible. To simplify, this is the data centre model.
Cloud computing platforms (GFS/MapReduce/BigTable and Hadoop) that have been developed thus far have been designed with two important restrictions. First, clouds have assumed that all the nodes in the cloud are co-located, i.e. within one data centre, or that there is relatively small bandwidth available between the geographically distributed clusters containing the data. Second, these clouds have assumed that individual inputs and outputs to the cloud are relatively small, although the aggregate data managed and processed are very large. This makes sense since most clouds to date have targeted Web applications in which large numbers of relatively small Web pages are collected and processed as inputs, and outputs consist of search queries that return relatively small lists of relevant pages. Although some e-Science applications have these characteristics, others must ingest relatively large datasets and process them. In addition, queries for certain e-Science applications also result in relatively large datasets being returned.
By contrast, our assumption is that there are high-speed networks (10 Gb s K1 or higher) connecting various geographically distributed clusters and that the cloud must support both the ingestion and the return of relatively large datasets.
In this paper, we describe a storage cloud that we have developed called Sector and a compute cloud that we have developed called Sphere. Both of them are available as open source software programs from http://sector. sourceforge.net.
Sector is a distributed storage system that can be deployed over a wide area and allows users to ingest and download large datasets from any location with a high-speed network connection to the system. In addition, Sector automatically replicates files for better reliability, availability and access throughout. Sector has been used to support the distributing Sloan Digital Sky Survey (SDSS) data releases to astronomers around the world (Gu et al. 2006).
Sphere is a compute service built on top of Sector and provides a set of simple programming interfaces for users to write distributed data-intensive applications. Sphere implements the stream-processing paradigm, which is usually used in programming graphics processing unit (GPU; Owens et al. 2005) and multi-core processors. The stream-processing paradigm can be used to implement any MapReduce-supported applications.
The rest of this paper will describe the details of Sector and Sphere in § §2 and 3, respectively. Section 4 describes some experimental studies. Section 5 describes related work and §6 is the summary and conclusion. This is an expanded version of a conference paper (Grossman & Gu 2008). This paper: (i) describes a later version of Sector that includes security, (ii) includes additional information about how Sector works, including how security and scheduling are designed, and (iii) describes new experimental studies.

(a ) Overview
Sector is a storage cloud as defined above. Specifically, Sector provides storage services over the Internet with the scalability and reliability of a data centre. Sector makes three assumptions.
(i) Sector assumes that it has access to a large number of commodity computers (which we sometimes call nodes). The nodes may be located either within or across data centres. (ii) Sector assumes that high-speed networks connect the various nodes in the system. For example, in the experimental studies described below, the nodes within a rack are connected by 1 Gb s K1 networks, two racks within a data centre are connected by 10 Gb s K1 networks and two different data centres are connected by 10 Gb s K1 networks. (iii) Sector assumes that the datasets it stores are divided into one or more separate files, which are called Sector slices. The different files comprising a dataset are replicated and distributed over the various nodes managed by Sector. For example, one of the datasets managed by Sector in the experimental studies described below is a 1.3 TB dataset consisting of 64 files, each approximately 20.3 GB in size. Figure 1 shows the overall architecture of the Sector system. The security server maintains user accounts, user passwords and file access information. It also maintains lists of internetwork protocol (IP) addresses of the authorized slave nodes, so that illicit computers cannot join the system or send messages to interrupt the system.
The master server maintains the metadata of the files stored in the system, controls the running of all slave nodes and responds to users' requests. The master server communicates with the security server to verify the slaves, the clients and the users. The slaves are the nodes that store the files managed by the system and process the data upon the request of a Sector client. The slaves are usually running on racks of computers that are located in one or more data centres.
(b ) File system management Sector is not a native file system; instead, it relies on the native file system on each slave node to store Sector slices. A critical element in the design of Sector is that each Sector slice is stored as one single file in the native file system. That is, Sector does not split Sector slices into smaller chunks. This design decision greatly simplifies the Sector system and provides several advantages. First, with this approach, Sector can recover all the metadata it requires by simply scanning the data directories on each slave. Second, a Sector user can connect to a single slave node to upload or download a file. By contrast, if a storage cloud manages data at the block level, then a user will generally need to connect to many slaves to access all the blocks in a file. The Hadoop system is an example of a storage cloud that manages files at the block level (Hadoop, http://hadoop.apache.org/ core). Third, Sector can interoperate with native file systems if necessary.
A disadvantage of this approach is that it does require the user to break up large datasets into multiple files or to use a utility to accomplish this. Sector assumes that any user sophisticated enough to develop code for working with large datasets is sophisticated enough to split a large dataset into multiple files if required.
The master maintains the metadata index required by Sector and supports file system queries, such as file lookup and directory services. The master also maintains the information about all slaves (e.g. available disk space) and the system topology, in order to choose slaves for better performance and resource usage.
The current implementation assumes that Sector will be installed on a hierarchical topology, e.g. computer nodes on racks within multiple data centres. The topology is manually specified by a configuration file on the master server.
The master checks the number of copies of each file periodically. If the number is below a threshold (the current default is 3), the master chooses a slave to make a new copy of the file. The new location of the file copy is based on the topology of the slaves' network. When a client requests a file, the master can choose a slave (that contains a copy of the file) that is close to the client and is not busy with other services.
The Sector client supports standard file access application programming interfaces (APIs), such as open( ), read( ) and write( ). These APIs can be wrapped to support other standards, such as Simple API for Grid Applications.

(c ) Security
Sector runs an independent security server. This design allows different security service providers to be deployed (e.g. lightweight directory access protocol and Kerberos). In addition, multiple Sector masters (for better reliability and availability) can use the same security service.
A client logs onto the master server via a secure sockets layer (SSL) connection. The user name and the password are sent to the master. The master then sets up an SSL connection to the security server and asks to verify the credibility of the client. The security server checks its user database and sends the result back to the master, along with a unique session ID and the client's file access privileges (for example its I/O permissions for different directories). In addition to the password, the client IP address is checked against an access control list defined for the user. Both SSL connections require the use of public certificates for verification.
If the client requests access to a file, the master will check whether the user has access privileges for that file. If granted, the master chooses a slave node to serve the client. The slave and the client then set up an exclusive data connection that is coordinated by the master. Currently, the data connection is not encrypted, but we expect to add encryption in a future release.
Sector slave nodes only accept commands from the Sector master. Neither Sector clients nor other slave nodes can send commands directly to a slave. All client-slave and slave-slave data transfer must be coordinated by the master node.
Finally, the security server controls whether a slave can be added to the system. The security server maintains an IP list and/or an IP range so that only computers on this list can join as slaves.

(d ) Message and data transfer
Sector uses user datagram protocol (UDP) for message passing and user defined type (UDT; Gu & Grossman 2007) for data transfer. UDP is faster than transmission control protocol (TCP) for message passing because it does not require connection set-up. We developed a reliable message passing library called group messaging protocol to use in Sector. For data transfer, a Sector slave will set up a UDT connection directly with the client. This UDT connection is set up using a rendezvous connection mode and is coordinated by the master. UDT is a high-performance data transfer protocol and significantly outperforms TCP over long-distance high-bandwidth links (Gu & Grossman 2007).
A single UDP port is used for messaging and another single UDP port is used for all the data connections. A limited number of threads process the UDP packets, independently of the number of connections, which make the communication mechanism scale nicely as the number of nodes in the system increases.

(a ) Overview
Recall that Sphere is a compute cloud that is layered over Sector. To introduce Sphere, consider the following example application. Assume we have 1 billion astronomical images of the Universe from the SDSS and the goal is to find brown dwarfs (stellar objects) in these images. Suppose the average size of an image is 1 MB so that the total data size is 1 TB. The SDSS dataset is stored in 64 files, named SDSS1.dat, ., SDSS64.dat, each containing one or more images.
In order to access an image randomly in the dataset (consisting of 64 files), we built an index file for each file. The index file indicates the start and end positions (i.e. offset and size) of each record (in this case, an image) in the data file. The index files are named by adding an '.idx' postfix to the data file name: SDSS1.dat.idx, ., SDSS60.dat.idx.
To use Sphere, the user writes a function 'findBrownDwarf' to find brown dwarfs from each image. In this function, the input is an image, while the output indicates the brown dwarfs.

findBrownDwarf (input, output);
A standard serial program might look similar to this: for each file F in (SDSS slices) for each image I in F findBrownDwarf (I, .); Using the Sphere client API, the corresponding pseudo code looks similar to this: SphereStream sdss; sdss.init(/ Ã list of SDSS slices Ã /); SphereProcess myproc; Myproc.run (sdss, 'findBrownDwarf'); Myproc.read (result); In the pseudocode fragment above, 'sdss' is a Sector stream data structure that stores the metadata of the Sector slice files. The application can initialize the stream by giving it a list of file names. Sphere automatically retrieves the metadata from the Sector network. The last three lines will simply start the job and wait for the result using a small number of Sphere APIs. The users neither need to explicitly locate and move data, nor do they need to take care of message passing, scheduling and fault tolerance.
(b ) The computing paradigm As illustrated in the example above, Sphere uses a stream-processing computing paradigm. Stream processing is one of the most common ways in which GPU and multi-core processors are programmed. In Sphere, each slave processor is regarded as an arithmetic logic unit (ALU) in a GPU, or a processing core in a CPU. In the stream-processing paradigm, each element in the input data array is processed independently by the same processing function using multiple computing units. This paradigm is also called Single Program, Multiple Data, a term derived from Flynn's taxonomy of Single Instruction, Multiple Data (SIMD) for CPU design.
We begin by explaining the key abstractions used in Sphere. Recall that a Sector dataset consists of one or more physical files. A stream is an abstraction in Sphere and it represents either a dataset or a part of a dataset. Sphere takes streams as inputs and produces streams as outputs. A Sphere stream consists of multiple data segments and the segments are processed by Sphere Processing Engines (SPEs) using slaves. An SPE can process a single data record from a segment, a group of data records or the complete segment. Figure 2 illustrates how Sphere processes the segments in a stream. Usually there are many more segments other than SPEs, which provides a simple mechanism for load balancing, since a slow SPE simply processes fewer segments. Each SPE takes a segment from a stream as an input and produces a segment of a stream as output.
These output segments can in turn be the input segments to another Sphere process. For example, a sample function can be applied to the input stream and the resulting sample can be processed by another Sphere process. Figure 2 illustrates the basic model that Sphere supports. Sphere also supports some extensions of this model, which occur quite frequently.
(i) Processing multiple input streams First, multiple input streams can be processed at the same time (for example, the operation A[ ]CB[ ] is supported). Note that this is not a straightforward extension, because it can be complex to split input streams and to assign segments to SPEs.
(ii) Shuffling input streams Second, the output can be sent to multiple locations, rather than being just written to local disk. Sometimes this is called shuffling. For example, a user-defined function (UDF) can specify a bucket ID (that refers to a destination file on either a local or a remote node) for each record in the output, and Sphere will send this record to the specified destination. At the destination, Sphere receives results from many SPEs and writes them into a file, in the same order that they arrive. It is in this way that Sphere supports MapReduce-style computations (Dean & Ghemawat 2004). Figure 3 shows an example that uses two Sphere processes (each process is called a stage) to implement distributed sorting. The first stage hashes the input data into multiple buckets. The hashing function scans the complete stream and places each element in a proper bucket. For example, if the data to be sorted are a collection of integers, the hashing function can place all data less than T 0 in bucket B 0 , data between T 0 and T 1 in bucket B 1 , and so on.  In stage 2, each bucket (which is a data segment) is sorted by an SPE. Note that after stage 2, the entire dataset (stream) is now sorted. This is because all elements in a bucket are smaller than all the elements in any buckets further along in the stream.
Note that in stage 2, the SPE sorts the whole data segment and does not just process each record individually.
(iii) SPE can process records or collections of records This is the third expansion to the basic model. In Sphere, an SPE can process a single record, multiple records, the whole segment or a complete file at one time.
(c ) Sphere processing engine Once the master accepts the client's request for Sphere data processing, it sends a list of available slave nodes to the client. The client then chooses some or all the slaves and requests that an SPE starts on these nodes. The client then sets up a UDT connection (for both control and data) with the SPE. The stream-processing functions, in the form of dynamic libraries, are sent to each SPE and stored locally on the slave node. The SPE then opens the dynamic libraries and obtains the various processing functions. Then it runs in a loop that consists of the following four steps.
First, the SPE accepts a new data segment from the client containing the file name, offset, number of rows to be processed and various additional parameters.
Next, the SPE reads the data segment (and the corresponding portion of the idx index file if it is available) from either the local disk or from another slave node.  As required, the stream-processing function processes either a single data record, a group of data records or the entire segment, and writes the result to the proper destinations. In addition, the SPE periodically sends acknowledgments to the client about the progress of the current processing.
When the data segment is completely processed, the SPE sends an acknowledgement to the client to conclude the processing of the current data segment.
If there are no more data segments to be processed, the client closes the connection to the SPE, and the SPE is released. The SPE may also timeout if the client is interrupted.

(d ) Sphere client
The Sphere client provides a set of APIs that developers can use to write distributed applications. Developers can use these APIs to initialize input streams, upload processing function libraries, start Sphere processes and read the processing results.
The client splits the input stream into multiple data segments, so that each can be processed independently by an SPE. The SPE can either write the result to the local disk and return the status of the processing, or it can return the result of the processing itself. The client tracks the status of each segment (for example, whether the segment has been processed) and holds the results.
The client is responsible for orchestrating the complete running of each Sphere process. One of the design principles of the Sector/Sphere system is to leave most of the decision making to the client, so that the Sector master can be quite simple. In Sphere, the client is responsible for the control and scheduling of the program execution.

(i) Data segmentation and SPE initialization
The client first locates the data files in the input stream from Sector. If the input stream is the output stream of a previous stage, then this information is already within the Sector stream structure and no further segmentation is needed.
Both the total data size and the total number of records are calculated in order to split the data into segments. This is based on the metadata of the data files retrieved from Sector.
The client tries to uniformly distribute the input stream to the available SPEs by calculating the average data size per SPE. However, in consideration of the physical memory available per SPE and the data communication overhead per transaction, Sphere limits the data segment size between size boundaries S min and S max (the default values are 8 MB and 128 MB, respectively, but user-defined values are supported). In addition, the scheduler rounds the segment size to a whole number of records since a record cannot be split. The scheduler also requires that a data segment only contains records from a single data file.
As a special case, the application may request that each data file be processed as a single segment. This would be the case, for example, if an existing application were designed to only process files. This is also the way the scheduler works when there is no record index associated with the data files.

(ii) SPE scheduling
Once the input stream is segmented, the client assigns each segment to an SPE. The following rules are applied: (i) each data segment is assigned to an SPE on the same node if there is one available, (ii) segments from the same file are processed at the same time unless following this rule leaves SPEs idle, and (iii) if there are still idle SPEs available after rule (i) and rule (ii) are applied, assign them parts of data segments to process in the same order as they occur in the input stream.
The first rule tries to run an SPE on the same node on which the data reside (in other words, to exploit data locality). This reduces the network traffic and yields better throughput. The second rule improves data access concurrency, because SPEs can read data from multiple files independently at the same time.
As mentioned in §3c, SPEs periodically provide feedback about the progress of the processing. If an SPE does not provide any feedback about the progress of the processing before a timeout occurs, then the client discards the SPE. The segment being processed by the discarded SPE is assigned to another SPE, if one is available, or placed back into the pool of unassigned segments. This is the mechanism that Sphere uses to provide fault tolerance. Sphere does not use any check pointing in an SPE; when the processing of a data segment fails, it is completely reprocessed by another SPE.
Fault tolerance is more complicated when SPEs write results to multiple destinations (as happens when using buckets for example). Each SPE dumps the result to a local disk before attempting to send the results to buckets on other nodes. In this way, if one node is down, the result can be sent to the same buckets on other nodes. Each bucket handler also records the status of incoming results from each data segment; thus, if one SPE is down, the bucket handler can continue to accept data in the correct order from another SPE that processes the same data segment again.
If errors occur during the processing of a data segment due to problems with the input data or bugs in UDFs, the data segment will not be processed by any other SPE. Instead, an error report is sent back to the client, so that the application can take the appropriate action.
In most cases, the number of data segments is significantly greater than the number of SPEs. For example, hundreds of machines might be used to process terabytes of data. As a consequence, the system is naturally load balanced, because all SPEs are kept busy during the majority of the runtime. Imbalances occur only towards the end of the computation when there are fewer and fewer data segments to process, causing some SPEs to be idle. Different SPEs can require different times to process data segments. There are several reasons for this, including: the slave nodes may not be dedicated; the slaves may have different hardware configurations (Sector systems can be heterogeneous); and different data segments may require different processing times. Near the end of the computation, when there are idle SPEs but incomplete data segments, each idle SPE is assigned one of the incomplete segments. That is, the remaining segments are run on more than one SPE and the client collects results from whichever SPE finishes first. In this way, Sphere avoids waiting for the slow SPEs while the faster ones are idle. After processing is complete, the Sphere client can reorder the segments to correspond to the original order in the input stream.

(f ) Comparison with MapReduce
Both the stream-processing framework used by Sphere and the MapReduce framework can be viewed as ways to simplify parallel programming. The approach of applying UDFs to segments managed by a storage cloud is more general than the MapReduce approach, in the sense that with Sphere it is easy to specify a map UDF and to follow it with a reduce UDF. We now describe how to do this in more detail.
A MapReduce map process can be expressed directly by a Sphere process that writes the output stream to local storage. A MapReduce reduce process can be simulated by the hashing/bucket process of Sphere. In MapReduce, there is no data exchange between slave nodes in the map phase, while each reducer in the reduce phase reads data from all the slaves. In Sphere's version, the first stage hashes (key, value) pairs to buckets on other slave nodes, while in the second stage all data are processed locally at the slave by the reduce function.
We illustrate this by showing how MapReduce and Sphere compute an inverted index for a collection of Web pages. Recall that the input is a collection of Web pages containing terms (words) and the output is a sorted list of pairs (w, !pagesO), where w is a word that occurs in the collection and !pagesO is a list of Web pages that contain the word w. The list is sorted on the first component.
Computing an inverted index using Sphere requires two stages. In the first stage, each Web page is read, the terms are extracted and each term is hashed into a different bucket. Sphere automatically assigns each bucket to a separate slave for processing. Think of this as the hashing or shuffling stage. To be more concrete, all words starting with the letter 'a' can be assigned to the bucket 0, those beginning with the letter 'b' to the bucket 1, and so on. A more advanced hashing technique that would distribute the words more evenly could also be used. In the second stage, each bucket is processed independently by the slave node, which generates a portion of the inverted index. The inverted index consists of multiple files managed by Sector.
For example, assume that there are two Web pages (each is a separate file): w1.html and w2.html. Assume that w1 contains the words bee and cow and that w2 contains the words bee and camel. In the first stage of Sphere, bucket 1 will contain (bee, w1) and (bee, w2), and bucket 2 will contain (cow, w1) and (camel, w2). In the second stage, each bucket is processed separately. Bucket 1 becomes (bee, (w1, w2)) and bucket 2 remains unchanged. In this way, the inverted index is computed and the result is stored in multiple files (bucket files).

Experimental studies
We have released Sector/Sphere as open source software and used it in a variety of applications. We have also analysed its performance using the Terasort benchmark (Govindaraju et al. 2006;Borthaku 2007). In this section, we describe two Sector/Sphere applications and discuss their performance.

(a ) SDSS data distribution
Sector is currently used to distribute the data products from the SDSS over the Teraflow Testbed (Gu et al. 2006; Teraflow Testbed, http://www.teraflowtestbed. net). We set up multiple Sector servers on the Teraflow Testbed that we use to store the SDSS data. We stored the 13 TB SDSS Data Release 5 (DR5), which contains 60 catalogue files, 64 catalogue files in EFG format and 257 raw image data collection files. We also stored the 14 TB SDSS Data Release 6 (DR6), which contains 60 catalogue files, 60 Segue files and 268 raw image collection files. The size of each of these files varies between 5 and 100 GB.
We uploaded the SDSS files to several specific locations in order to better cover North America, Asia Pacific and Europe. We then set up a website (sdss.ncdm.uic. edu), so that the users could easily obtain a Sector client application and the list of SDSS files to download. The MD5 checksum for each file is also posted on the website, so that users can check the integrity of the files.
The system has been online since July 2006. During the last 2 years, we have had approximately 6000 system accesses and a total of 250 TB of data that were transferred to the end users. Approximately 80 per cent of the users are just interested in the catalogue files, which contain files that range in size between 20 and 25 GB each. Figure 4 shows the file downloading performance in an experiment of our own, where the clients are also connected to the Teraflow Testbed by 10 Gb s K1 links. In this experiment, the bottleneck is the disk IO speed. Figure 5 shows a distribution of the data transfer throughput of actual transfers to the end users during the last 18 months. In most of the SDSS downloads, the bottleneck is the network connecting the Teraflow Testbed to the end user and simply using multiple parallel downloads will not help. The SDSS downloads are currently distributed as follows: 31 per cent are from the USA; 37.5 per cent are from Europe; 18.8 per cent are from Asia; and 12.5 per cent are from Australia. The transfer throughput to users varies from 8 Mb s K1 (to India) to 900 Mb s K1 (to Pasadena, CA), all via public networks. More records can be found on sdss. ncdm.uic.edu/records.html.

(b ) Terasort
We implemented the Terasort benchmark to evaluate the performance of Sphere (Govindaraju et al. 2006; Sort Benchmark, http://www.hpl.hp.com/ hosted/sortbenchmark/). Suppose there are N nodes in the system, the benchmark generates a 10 GB file on each node and sorts the total N!10 GB data. Each record contains a 10-byte key and a 90-byte value. The Sphere implementation follows the bucket sorting algorithm depicted in figure 3.
The experimental studies summarized in table 1 were done using the Open Cloud Testbed (http://www.opencloudconsortium.org). Currently, the testbed consists of four racks. Each rack has 32 nodes, including 1 NFS server, 1 head node and 30 compute/slave nodes. The head node is a Dell 1950, dual dual-core Xeon 3.0 GHz and 16 GB RAM. The compute nodes are Dell 1435s, single dual-core AMD Opteron 2.0 GHz, 4 GB RAM and 1 TB single disk. The four racks are located in JHU (Baltimore), StarLight (Chicago), UIC (Chicago) and Calit2 (San Diego).
The nodes on each rack are connected by two Cisco 3750E switches, but only a 1 Gb s K1 connection is enabled at this time (a maximum of 2 Gb s K1 can be enabled in/out each node). The bandwidth between racks is 10 Gb s K1 . The wide area links are provided by Cisco's C-Wave, which uses resources from the National Lambda Rail. Links from regional 10 GE research networks are used to connect the C-Wave to the racks in the testbed.
Both Sector (http://sector.sourceforge.net) and Hadoop (http://hadoop. apache.org/core) are deployed over the 120-node (240-core) wide area system. The master server for Sector and the name node/job tracker of Hadoop are installed on one or more of the four head nodes. Both the Sphere client and the Hadoop client submit the job from a node in the system. This does not affect the performance since the traffic to/from the clients is negligible. Table 1 lists the performance for the Terasort benchmark for both Sphere and Hadoop. The time is in seconds and time to generate the data is not included. Note that it is normal to see longer processing time for more nodes, because the total amount of data also increases proportionally.
In this experiment, we sort 300, 600, 900 GB and 1.2 TB data over 30, 60, 90 and 120 nodes, respectively. For example, in the last case, the 1.2 TB data are distributed on four racks located in four data centres across the USA. All 120 nodes participated in the sorting process and essentially all of the 1.2 TB data are moved across the testbed during the sort. Both Sector and Hadoop replicate data for safety. The default replication strategy for both is to generate three replicas. Their replication strategies are different though. Hadoop replicates data during the initial writing, while Sector checks periodically, and, if there are not a sufficient number of replicas, it creates them. For this reason, table 1 reports results for Hadoop with the replication sent to a replication factor of 1 (no replication) as well as the default replication factor of 3.
The results show that Sphere is about twice as fast as Hadoop (when Hadoop's replication factor is set to 1). Moreover, Sphere scales better as the number of racks increases (1526/1265Z1.2 for Sphere versus 3702/2252Z1.6 for Hadoop).

Related work
In this section, we describe some work related to Sector and Sphere. Sector provides some of the functionality of distributed file systems (DFSs), such as General Parallel File System, Lustre and Parallel Virtual File System (Kramer et al. 2004). DFSs provide the functionality of a file system on clusters of computers, sometimes, although rarely, over geographically distributed locations. While DFS may be suitable for a single organization with dedicated hardware and management, it is challenging to deploy and operate a regular DFS on a loosely coupled infrastructure consisting of commodity computers, such as those used for the experimental studies described here.
On the other hand, the GFS (Ghemawat et al. 2003), the HDFS (Borthaku 2007) and Sector are special purpose file systems. They are particularly optimized for large files, for large scanning reads and for short random reads. By contrast with Sector, neither GFS nor HDFS was designed for nodes distributed over a wide area network.
The Sector servers that are deployed over the Teraflow Testbed and used for distributing the SDSS data provide the functionality of a content distribution network, such as Akamai (Dilley et al. 2002). Akamai is designed to distribute large numbers of relatively small files and keeps a cache at most edge nodes of its network. In contrast to Akamai, Sector is designed to distribute relatively small numbers of large files and maintains copies at several, but not all, edge nodes.
The stream-processing paradigm in Sphere is currently quite popular in the general-purpose GPU programming (GPGPU) community (Owens et al. 2005). The approach with GPGPU programming is to define a special 'kernel function' that is applied to each element in the input data by the GPU's vector computing units. This can be viewed as an example of an SIMD style of programming. Many GPU programming libraries and programming languages (e.g. Cg, sh and Brook) have been developed. Similar ideas have also been applied to multi-core processors, including the Cell processor. For example, specialized parallel sorting algorithms have been developed for both GPU processors (Govindaraju et al. 2006) and the Cell processor (Gedik et al. 2007). Sphere uses the same basic idea, but extends this paradigm to wide-area distributed computing. Many of the GPGPU algorithms and applications can be adapted and run in a distributed fashion using Sphere. In fact, it is this analogue to GPGPU which inspired our work on Sphere.
There are some important differences though: Sphere uses heterogeneous distributed computers connected by high-speed, wide-area networks instead of the identical ALUs integrated in a GPU; Sphere supports more flexible movement of data, but also requires load balancing and fault tolerance; finally, the bandwidth between Sphere's SPEs, although it may be up to 10 Gb s K1 , is not even close to the bandwidth within a GPU. Owing to these differences, Sphere runs a complete processing function or program on each SPE, rather than one instruction.
One way of viewing GPGPU style programming is as a parallel programming style that gains simplicity by restricting the type of application that it is targeting. By contrast, message passing systems such as message-passing interface (Gropp et al. 1999) are designed for very general classes of applications but are usually harder to program. Google's MapReduce (Dean & Ghemawat 2004) is one of the most well-known examples of a system that targets a limited class of applications, but is relatively simple to program. As shown above, the Sphere system is similar to but more general than MapReduce. Sphere is a generalization of MapReduce, in the sense that it provides a simple mechanism to execute UDFs over data managed by Sector. Sphere can implement a MapReduce by using a UDF map followed by a UDF reduce.  See table 2 for a summary of some of the differences between Sector/Sphere and other systems for cloud computing.
Sector/Sphere is similar to grid computing in that it aggregates distributed computing resources, but its approach is quite different. Traditional grid systems such as the Globus TOOLKIT (Foster 2005) and Condor (Thain et al. 2005) allow users to submit multiple tasks and to run these tasks in parallel. Grid job schedulers such as Swift (Zhao et al. 2007) and the Condor Directed Acyclic Graph Manager (http://www.cs.wisc.edu/condor/dagman) provide workflow services to support the scheduling of user tasks. Grid systems manage relationships among many tasks. By contrast, the Sphere client scheduler exploits data parallelism within one task. In this sense, grid computing is task oriented (multiple tasks processing one or more datasets), while Sphere is data oriented (single program processing a single dataset).
In addition, a grid application submits a user's tasks to computing resources and moves data to these resources for computation, whereas Sector provides long-term persistent storage for data and Sphere is designed to start operations as close to the data as possible. In the Sphere-targeted scenarios, datasets are usually very large and moving them is considerably expensive. To summarize, grid systems are designed to manage scarce specialized computing resources, while storage clouds, such as Sector, are designed to manage large datasets and compute clouds, such as Sphere, are designed to support computation over this data.
Finally, note that Sphere is very different from systems that process streaming data such as GATES (Chen et al. 2004) and DataCutter (Beynon et al. 2000) or event stream-processing systems such as STREAM, Borealis, and TelegraphCQ (Babcock et al. 2002). While Sphere is designed to support large datasets, the data being processed are still treated as finite and static and are processed in a dataparallel model. By contrast, event stream-processing systems regard the input as infinite and process the data with a windowed model, sometimes with filters incorporating timing restraints in order to guarantee real-time processing.

Conclusions
For several years now, commodity clusters have been quite common. Over the next several years, wide-area, high-performance networks (10 Gb s K1 and higher) will begin to connect these clusters. At the risk of oversimplifying, it is useful to think of high-performance computing today as an era in which cycles are the scarce resource, and (relatively small) datasets are scattered to large pools of nodes when their wait in the queue is over. By contrast, we are moving to an era in which there are large distributed datasets that must be persisted on disk for long periods of time, and high-performance computing must be accomplished in a manner that moves the data as little as possible, due to the costs incurred when transporting large datasets.
Sector and Sphere are designed for these types of applications involving large, geographically distributed datasets in which the data can be naturally processed in parallel. Sector manages the large distributed datasets with high reliability, highperformance IO and a uniform access. Sphere makes use of the Sector-distributed storage system to simplify data access, increase data IO bandwidth and to exploit wide-area, high-performance networks. Sphere presents a very simple programming interface by hiding data movement, load balancing and fault tolerance.