A Distributed Algorithm on the Computation of All

ON THE COMPUTATIONALCOMPLEXITY OF ALGORITHMSBYJ. HARTMANIS AND R. E. STEARNSI. Introduction. In his celebrated paper [1], A. M. Turing investigated the computability of sequences (functions) by mechanical procedures and showed that the setofsequencescanbe partitioned into computable and noncomputable sequences. One finds, however, that some computable sequences are very easy to compute whereas other computable sequences seem to have an inherent complexity that makes them difficult to compute. In this paper, we investigate a scheme of classifying sequences according to how hard they are to compute. This scheme puts a rich structure on the computable sequences and a variety of theorems are established. Furthermore, this scheme can be generalized to classify numbers, functions, or recognition problems according to their compu-tational complexity.The computational complexity of a sequence is to be measured by how fast a multitape Turing machine can print out the terms of the sequence. This particular abstract model of a computing device is chosen because much of the work in this area is stimulated by the rapidly growing importance of computation through the use of digital computers, and all digital computers in a slightly idealized form belong to the class of multitape Turing machines. More specifically, if Tin) is a computable, monotone increasing function of positive integers into positive integers and if a is a (binary) sequence, then we say that a is in complexity class ST or that a is T-computable if and only if there is a multitape Turing machine 3~ such that 3~ computes the nth term of a. within Tin) operations. Each set ST is recursively enumerable and so no class ST contains all computable sequences. On the other hand, every computable a is contained in some com-plexity class ST. Thus a hierarchy of complexity classes is assured. Furthermore, the classes are independent of time scale or of the speed of the components from which the machines could be built, as there is a "speed-up" theorem which states that ST = SkT f or positive numbers k.As corollaries to the speed-up theorem, there are several limit conditions which establish containment between two complexity classes. This is contrasted later with the theorem which gives a limit condition for noncontainment. One form of this result states that if (with minor restrictions)Received by the editors April 2, 1963 and, in revised form, August 30, 1963.285286J. HARTMANIS AND R. E. STEARNS[May»*«, U(n)then S,; properly contains ST. The intersection of two classes is again a class. The general containment problem, however, is recursively unsolvable.One section is devoted to an investigation as to how a change in the abstract machine model might affect the complexity classes. Some of these are related by a "square law," including the one-tape-multitape relationship: that is if a is T-computable by a multitape Turing machine, then it is T2-computable by a single tape Turing machine. It is gratifying, however, that some of the more obvious variations do not change the classes.The complexity of rational, algebraic, and transcendental numbers is studied in another section. There seems to be a good agreement with our intuitive notions, but there are several questions still to be settled.There is a section in which generalizations to recognition problems and functions are discussed. This section also provides the first explicit "impossibility" proof, by describing a language whose "words" cannot be recognized in real-time [T(n) = n] .The final section is devoted to open questions and problem areas. It is our conviction that numbers and functions have an intrinsic computational nature according to which they can be classified, as shown in this paper, and that there is a good opportunity here for further research.For background information about Turing machines, computability and related topics, the reader should consult [2]. "Real-time" computations (i.e., T(n) = n) were first defined and studied in [3]. Other ways of classifying the complexity of a computation have been studied in [4] and [5], where the complexity is defined in terms of the amount of tape used.II. Time limited computations. In this section, we define our version of a multitape Turing machine, define our complexity classes with respect to this type of machine, and then work out some fundamental properties of these classes.First, we give an English description of our machine (Figure 1) since one must have a firm picture of the device in order to follow our paper. We imagine a computing device that has a finite automaton as a control unit. Attached to this control unit is a fixed number of tapes which are linear, unbounded at both ends, and ruled into an infinite sequence of squares. The control unit has one reading head assigned to each tape, and each head rests on a single square of the assigned tape. There are a finite number of distinct symbols which can appear on the tape squares. Each combination of symbols under the reading heads together with the state of the control unit determines a unique machine operation. A machine operation consists of overprinting a symbol on each tape square under the heads, shifting the tapes independently either one square left, one square1965]ON THE COMPUTATIONAL COMPLEXITY OF ALGORITHMS287ti 1111 i n cm U I I i I I I ID mm.Tn T| in i i i i i i i m-m Î2II I I I I I I I I m II I I I I I I IIP TnTAPESFINITE STATECOMPUTEROUTPUT TAPEFigure 1. An «-tape Turing machineright, or no squares, and then changing the state of the control unit. The machine is then ready to perform its next operation as determined by the tapes and control state. The machine operation is our basic unit of time. One tape is signaled out and called the output tape. The motion of this tape is restricted to one way move-ment, it moves either one or no squares right. What is printed on the output tape and moved from under the head is therefore irrevocable, and is divorced from further calculations.As Turing defined his machine, it had one tape and if someone put k successive ones on the tape and started the machine, it would print some f(k) ones on the tape and stop. Our machine is expected to print successively /(l),/(2), ••• on its output tape. Turing showed that such innovations as adding tapes or tape symbols does not increase the set of functions that can be computed by machines. Since the techniques for establishing such equivalences are common knowledge, we take it as obvious that the functions computable by Turing's model are the same as those computable by our version of a Turing machine. The reason we have chosen this particular model is that it closely resembles the operation of a present day computer; and being interested in how fast a machine can compute, the extra tapes make a difference.To clear up any misconceptions about our model, we now give a formal definition.Definition 1. An n-tape Turing machine, &~, is a set of (3n + 4)-tuples, {(q¡; Stl, Sh, — , Sin ; Sjo, Sjl, — , Sh ; m0, mx, —, m… ; qf)},where each component can take on a finite set of values, and such that for every possible combination of the first n + 1 entries, there exists a unique (3zi-t-4)-tupIe in this set. The first entry, q¡, designates the present state; the next n entries, S(l,-",S,B, designate the present symbols scanned on tapes Tx, •■•, T…,respectively; the next n + 1 symbols SJa, ••-, Sjn, designate the new symbols to be printed on288J. HARTMANIS AND R. E. STEARNS[May tapes T0, •■», T…, respectively; the next n entries describe the tape motions (left, right, no move) of the n + 1 tapes with the restriction m0 # left ; and the last entry gives the new internal state. Tape T0 is called the output tape. One tuple with S¡. = blank symbol for 1 = j = n is designated as starting symbol.Note that we are not counting the output tape when we figure n. Thus a zero-tape machine is a finite automaton whose outputs are written on a tape. We assume without loss of generality that our machine starts with blank tapes.For brevity and clarity, our proofs will usually appeal to the English description and will technically be only sketches of proofs. Indeed, we will not even give a formal definition of a machine operation. A formal definition of this concept can be found in [2].For the sake of simplicity, we shall talk about binary sequences, the general-ization being obvious. We use the notation a = axa2 ••• .Definition 2. Let Tin) be a computable function from integers into integers such that Tin) ^ Tin + 1) and, for some integer k, Tin) ^ n/ k for all n. Then we shall say that the sequence a is T-computable if and only if there exists a multitape Turing machine, 3~, which prints the first n digits of the sequence a on its output tape in no more than Tin) operations, n = 1,2, ••», allowing for the possibility of printing a bounded number of digits on one square. The class of all T-computable binary sequences shall be denoted by ST, and we shall refer to T(n) as a time-function. Sr will be called a complexity class.When several symbols are printed on one square, we regard them as components of a single symbol. Since these are bounded, we are dealing with a finite set of output symbols. As long as the output comes pouring out of the machine in a readily understood form, we do not regard it as unnatural that the output not be strictly binary. Furthermore, we shall see in Corollaries 2.5, 2.7, and 2.8 that if we insist that Tin) ^ n and that only (single) binary outputs be used, then the theory would be within an e of the theory we are adopting.The reason for the condition Tin) ^ n/fc is that we do not wish to regard the empty set as a complexity class. For if a is in ST and F is the machine which prints it, there is a bound k on the number of digits per square of output tape and T can print at most fcn0 d igits in n0 operations. By assumption, Tikn0) ^ n0 or (substituting n0 = n/ k) Tin) à n/ k . On the other hand, Tin) ^ n/ k implies that the sequence of all zeros is in ST because we can print k zeros in each operation and thus ST is not void.Next we shall derive some fundamental properties of our classes.Theorem 1. TAe set of all T-computable binary sequences, ST, is recursively enumerable.Proof. By methods similar to the enumeration of all Turing machines [2] one can first enumerate all multitape Turing machines which print binary sequences. This is just a matter of enumerating all the sets satisfying Definition 1 with the1965] ON THE COMPUTATIONAL C OMPLEXITY O F ALGORITHMS 289 added requirement that Sjo is always a finite sequence of binary digits (regarded as one symbol). Let such an enumeration be &~x, 3~2, ••• . Because T(n) is comput-able, it is possible to systematically modify each ^"¡ to a machine &"'t w ith the following properties : As long as y¡ prints its nth digit within T(n) operations (and this can be verified by first computing T(n) and then looking at the first T(n) operations of ^"¡), then the nth digit of &~'t will be the nth output of &~¡. If &~¡ s hould ever fail to print the nth digit after T(n) operations, then ^"¡'will print out a zero for each successive operation. Thus we can derive a new enumeration •^"'u &~2> "•• If' &\ operates within time T(n), then ^", and ^"¡'compute the same T-computable sequence <x¡. O therwise, &~{ c omputes an ultimately constant sequence a¡ and this can be printed, k bits at a time [where T(n) — n / fc] by a zero tape machine. In either case, a¡ is T-computable and we conclude that {«,} = ST.Corollary 1.1. There does not exist a time-function T such that ST is the set of all computable binary sequences.Proof. Since ST is recursively enumerable, we can design a machine !T which, in order to compute its ith output, computes the z'th bit of sequence a, and prints out its complement. Clearly 3~ produces a sequence a different from all <Xj in ST.Corollary 1.2. For any time-function T, there exists a time-function U such that ST is strictly contained in Sv. Therefore, there are infinitely long chainsSTl cr STl cz •••of distinct complexity classes.Proof. Let &" compute a sequence a not in ST (Corollary 1.1). Let V(n) equal the number of operations required by ^"to compute the nth digit of a. Clearly V is computable and a e Sr. Lett/(n) = max [Tin), V(n)] ,then Vin) is a time-function and clearlyOrí ^3 Oj1 *Since a in Sv and a not in ST, we haveCorollary 1.3. The set of all complexity classes is countable.Proof. The set of enumerable sets is countable.Our next theorem asserts that linear changes in a time-function do not change the complexity class. // r is a real number, we write [r] to represent the smallest integer m such that m = r.290J. HARTMANIS AND R. E. STEARNS[MayTheorem 2. If the sequence cc is T-computable and k is a computable, positive real number, then a is [kT~\-computable; that is,ST = S[kTX.Proof. We shall show that the theorem is true for k = 1/2 and it will be true for fc = 1/ 2m b y induction, and hence for all other computable k since, given k, k ^ 1 /2'" for some m. (Note that if k is computable, then \kT~\ is a computable function satisfying Definition 2.)Let ¡F be a machine which computes a in time T. If the control state, the tape symbols read, and the tape symbols adjacent to those read are all known, then the state and tape changes resulting from the next two operations of &~ are determined and can therefore be computed in a single operation. If we can devise a scheme so that this information is always available to a machine 5~', then &' can perform in one operation what ST does in two operations. We shall next show how, by combining pairs of tape symbols into single symbols and adding extra memory to the control, we can make the information available.In Figure 2(a), we show a typical tape of S" with its head on the square marked 0. In Figure 2(b), we show the two ways we store this information in &~'. Each square of the ^"'-tape contains the information in two squares of the ^-tape. Two of the ^"-tape symbols are stored internally in 3r' and 3~' must also remember which piece of information is being read by 9~. In our figures, this is indicated by an arrow pointed to the storage spot. In two operations of &~, t he heads must move to one of the five squares labeled 2, 1,0, — l,or —2. The corresponding next position of our ^"'-tape is indicated in Figures 2(c)-(g). It is easily verified that in each case, &"' can print or store the necessary changes. In the event that the present symbol read by IT is stored on the right in ¡T' as in Figure 2(f), then the analogous changes are made. Thus we know that ST' can do in one operation what 9~ does in two and the theorem is proved.Corollary 2.1. If U and T are time-functions such that«-.«> Vin)then Svçz ST.Proof. Because the limit is greater than zero, Win) ^ Tin) for some k > 0, and thus Sv = SlkVj çz sT.Corollary 2.2. If U and T are time-functions such thatTin)sup-TTT-r- < 00 ,n-»a> O(n)then SV^ST.Proof. This is the reciprocal of Corollary 2.1.1965] ON THE COMPUTATIONAL COMPLEXITY OF ALGORITHMSE37291/HO W2|3l4[5l(/ZEEI33OÏÏT2Ï31/L-2_-iJ(c]¿m W\2I3I4I5K/(b)ZBE o2|3|4l5|\r2Vi!¿En on2l3l4l5|/l-T-i](d)¿BE2 34[5|6|7ir\10 l|(f)¿m2 34|5l6l7l /L<Dj(g)Figure 2. (a) Tape of ^" with head on 0. (b) Corresponding configurations of 9"'. (c) 9~' if F moves two left, (d) 9~> i f amoves to -1. (e) 9~' if ^~ moves to 0. (f)^"' if amoves to 1.(g) 9~' if 3~ moves two rightCorollary 2.3. If U and T are time-functions such thatTin)0 < hm ) ; < oo ,H-.« Uin)then Srj = ST .Proof. This follows from Corollaries 2.1 and 2.2.Corollary 2.4. // Tin) is a time-function, then Sn^ST . Therefore, Tin) = n is the most severe time restriction.Proof. Because T is a time-function, Tin) = n/ k for some positive k by Definition 2; hence292j. hartmanis and r. e. stearns[Maymf m à 1 > O…-»o, n kand S… çz s T by Corollary 2.1.Corollary 2.5. For any time-function T, Sr=Sv where t/(n)=max \T(n),n\. Therefore, any complexity class may be defined by a function U(n) ^ n. Proof. Clearly inf (T/ Í7) > min (1,1/ k) and sup (T/ U) < 1 .Corollary 2.6. If T is a time-function satisfyingTin) > n and inf -^ > 1 ,…-co nthen for any a in ST, there is a multitape Turing machined with a binary (i.e., two symbol) output which prints the nth digit of a in Tin) or fewer operations. Proof. The inf condition implies that, for some rational e > 0, and integer N, (1 - e) Tin) > n or Tin) > eTin) + n for all n > N. By the theorem, there is a machine 9' which prints a in time \zT(ri)\. 9' can be modified to a machine 9" which behaves like 9' except that it suspends its calculation while it prints the output one digit per square. Obviously, 9" computes within time \i.T(ri)\ + n (which is less than Tin) for n > N). $~" can be modified to the desired machine9~ by adding enough memory to the control of 9~" to print out the nth digit of a on the nth operation for n ^ N.Corollary 2.7. IfT(n)^nandoieST,thenforanys >0, there exists a binary output multitape Turing machine 9 which prints out the nth digit of a in [(1 + e) T(n)J or fewer operations.Proof. Observe that. [(1 + e) T(n)]inf —--——■— — 1 + enand apply Corollary 2.6.Corollary 2.8. // T(n)^n is a time-function and oteST, then for any real numbers r and e, r > e > 0, /Aere is a binary output multitape Turing machine ¡F which, if run at one operation per r—e seconds, prints out the nth digit of a within rT(n) seconds. Ifcc$ ST, there are no such r and e. Thus, when considering time-functions greater or equal to n, the slightest increase in operation speed wipes out the distinction between binary and nonbinary output machines.Proof. This is a consequence of the theorem and Corollary 2.7.Theorem 3. // Tx and T2 are time-functions, then T(n) = min [T^n), T2(n)~] is a time-function and STí O ST2 = ST.1965] ON THE COMPUTATIONAL COMPLEXITY OF ALGORITHMS 293 Proof. T is obviously a time-function. If 9~x is a machine that computes a in time T, and 9~2 computes a in time T2, then it is an easy matter to construct a third device &~ i ncorporating both y, and 3T2 which computes a both ways simul-taneously and prints the nth digit of a as soon as it is computed by either J~x or 9~2. Clearly this machine operates inTin) = min \Txin), T2(n)] .Theorem 4. If sequences a and ß differ in at most a finite number of places, then for any time-function T, cceST if and only if ße ST.Proof. Let ,T print a in time T. Then by adding some finite memory to the control unit of 3", we can obviously build a machine 3~' which computes ß in time T.Theorem 5. Given a time-function T, there is no decision procedure to decide whether a sequence a is in ST.Proof. Let 9~ be any Turing machine in the classical sense and let 3Tx be a multitape Turing machine which prints a sequence ß not in ST. Such a 9~x exists by Theorem 1. Let 9~2 be a multitape Turing machine which prints a zero for each operation $~ makes before stopping. If $~ should stop after k operations, then 3~2 prints the /cth and all subsequent output digits of &x. Let a be the sequence printed by 9"2, Because of Theorem 4, a.eST if and only if 9~ does not stop. Therefore, a decision procedure for oceST would solve the stopping problem which is known to be unsolvable (see [2]).Corollary 5.1. There is no decision procedure to determine if SV=ST or Sv c STfor arbitrary time-functions U and T.Proof. Similar methods to those used in the previous proof link this with the stopping problem.It should be pointed out that these unsolvability aspects are not peculiar to our classification scheme but hold for any nontrivial classification satisfying Theorem 4.III. Other devices. The purpose of this section is to compare the speed of our multitape Turing machine with the speed of other variants of a Turing machine. Most important is the first result because it has an application in a later section.Theorem 6. If the sequence a is T-computable by multitape Turing machine, !T, then a is T2-computable by a one-tape Turing machine 3~x .Proof. Assume that an n-tape Turing machine, 3~, is given. We shall now describe a one-tape Turing machine Px that simulates 9~, and show that if &" is a T-computer, then S~x is at most a T2-computer.294j. hartmanis and r. e. stearns[May The S~ computation is simulated on S'y as follows : On the tape of & y will be stored in n consecutive squares the n symbols read by S on its n tapes. The symbols on the squares to the right of those symbols which are read by S~ on its n tapes are stored in the next section to the right on the S'y tape, etc., as indicated in Figure 3, where the corresponding position places are shown. The1 TAPE T|A 1 TAPE T2I?TAPE Tn(a)J-"lo(b)Figure 3. (a) The n tapes of S. (b) The tape of S~\machine Tx operates as follows: Internally is stored the behavioral description of the machine S", so that after scanning the n squares [J], [o], ■■■, [5]»-^"îdetermines to what new state S~ will go, what new symbols will be printed by it on its n tapes and in which direction each of these tapes will be shifted. First,¡Fy prints the new symbols in the corresponding entries of the 0 block. Then it shifts the tape to the right until the end of printed symbols is reached. (We can print a special symbol indicating the end of printed symbols.) Now the machine shifts the tape back, erases all those entries in each block of n squares which correspond to tapes of S~ which are shifted to the left, and prints them in the corresponding places in the next block. Thus all those entries whose corresponding S~ tapes are shifted left are moved one block to the left. At the other end of the tape, the process is reversed and returning on the tape 9y transfers all those entries whose corresponding S~ tapes are shifted to the right one block to the right on the S'y tape. When the machine S', reaches the rigAz most printed symbol on its tape, it returns to the specially marked (0) block which now contains1965] ON THE COMPUTATIONAL COMPLEXITY OF ALGORITHMS 295 the n symbols which are read by &~ o n its next operation, and #", has completed the simulation of one operation of 9~. It can be seen that the number of operations of Tx is proportional to s, the number of symbols printed on the tape of &"¡. This number increases at most by 2(n + 1) squares during each operation of &. Thus, after T(fc) operations of the machine J~, the one-tape machine S"t will perform at most7(*)T,(fc) =C0+ T Cxii = loperations, where C0 and C, are constants. But thenr,(fe) g C2 £ i^C [T(fc)]2 .¡ =iSince C is a constant, using Theorem 2, we conclude that there exists a one tape machine printing its fcth output symbol in less than T(fc)2 tape shifts as was to be shown.Corollary 6.1. The best computation time improvement that can be gained in going from n-tape machines to in + l)-tape machines is the square root of the computation time.Next we investigate what happens if we allow the possibility of having several heads on each tape with some appropriate rule to prevent two heads from occupy-ing the same square and giving conflicting instructions. We call such a device a multihead Turing machine. Our next result states that the use of such a model would not change the complexity classes.Theorem 7. Let a. be computable by a multihead Turing machine 3T which prints the nth digit in Tin) or less operations where T is a time-function; then a is in ST .Proof. We shall show it for a one-tape two-head machine, the other cases following by induction. Our object is to build a multitape machine Jr' which computes a within time 4T which will establish our result by Theorem 2. The one tape of !T will be replaced by three tapes in 9"'. Tape a contains the left-hand information from 9", tape b contains the right-hand information of 9~, and tape c keeps count, two at a time, of the number of tape squares of ST which are stored on both tapes a and b_. A check mark is always on some square of tape a to indicate the rightmost square not stored on tape b_ and tape b has a check to indicate the leftmost square not stored on tape a.When all the information between the heads is on both tapes a and b. then we have a "clean" position as shown in Figure 4(a). As &" operates, then tape296j. hartmanis and r. e. stearns [May7/Fio TTzTTR" 5 "6Ï7M I 4T5T6" 7 8TT77' ^f(a) rT-Tô:TT2l3l4l?l \J ¿Kh.1y(b) J I l?IM2!3|4 5.6T7 /I |?|4,|5|6 7 8TT7(c) f\7~ /\V\/\A7\7M J M/l/yTITTTTTTJ(a) (b)Figure 4. (a) .^"' in clean position, (b) S' in dirty positiona performs like the left head of S~, tape A behaves like the right head, and tape c reduces the count each time a check mark is moved. Head a must carry the check right whenever it moves right from a checked square, since the new symbol it prints will not be stored on tape A; and similarly head A moves its check left.After some m operations of S~' corresponding to m operations of S~, a "dirty"position such as Figure 4(b) is reached where there is no overlapping information.The information (if any) between the heads of S~ must be on only one tape of S~',say tape A as in Figure 4(b). Head A then moves to the check mark, the between head information is copied over onto tape a, and head amoves back into position.A clean position has been achieved and S~' is ready to resume imitating S~. The time lost is 3/ where I is the distance between the heads. But / ^ m since headA has moved / squares from the check mark it left. Therefore 4m is enough time to imitate m operations of S~ and restore a clean position. Thusas was to be shown.This theorem suggests that our model can tolerate some large deviations without changing the complexity classes. The same techniques can be applied to other changes in the model. For example, consider multitape Turing ma-chines which have a fixed number of special tape symbols such that each symbol can appear in at most one square at any given time and such that the reading head can be shifted in one operation to the place where the special symbol is printed, no matter how far it is on the tape. Turing machines with such "jump instructions^ are similarly shown to leave the classes unchanged.Changes in the structure of the tape tend to lead to "square laws." For example,consider the following :Definition 3. A two-dimensional tape is an unbounded plane which is sub-divided into squares by equidistant sets of vertical and horizontal lines as shown in Figure 5. The reading head of the Turing machine with this two-dimensional tape can move either one square up or down, or one square left or right on each operation. This definition extends naturally to higher-dimensional tapes.。

Computers have revolutionized the way we live and work,and their uses are incredibly diverse and widespread.Here are some of the most common and impactful applications of computers in our daily lives:munication:Computers have transformed the way we communicate.Email, instant messaging,and social media platforms allow us to stay in touch with friends, family,and colleagues across the globe instantly.cation:In the educational sector,computers are used for research,online learning, and digital classrooms.They provide access to a wealth of information and enable interactive learning experiences.3.Business and Finance:Computers are integral to business operations,from managing inventory to processing transactions.They are also used in financial modeling,stock trading,and accounting.4.Entertainment:Computers have revolutionized the entertainment industry.They are used for gaming,streaming movies and music,and creating digital art and animations.5.Healthcare:In healthcare,computers are used for managing patient records,conducting research,and aiding in diagnostics and treatment plans.6.Data Analysis:Computers are essential for data collection,storage,and analysis.They help in making informed decisions in various fields such as science,marketing,and policymaking.7.Manufacturing:Computers are used to control machinery and automate processes in manufacturing,leading to increased efficiency and reduced human error.8.Transportation:Computers are used in transportation systems for navigation,traffic management,and vehicle control,including autonomous vehicles.9.Science and Research:Computers are used for complex calculations,simulations,and modeling in scientific research,helping to push the boundaries of knowledge in fields such as physics,chemistry,and biology.10.Home Automation:Computers are at the heart of smart homes,controlling lighting, heating,security systems,and appliances.11.Creative Industries:In the creative industries,computers are used for graphic design,music production,film editing,and3D modeling.12.Ecommerce:Computers have enabled the growth of online shopping,making it easier for consumers to purchase goods and services from anywhere.ernment and Public Services:Governments use computers for managing public records,providing services to citizens,and ensuring national security.14.Agriculture:Computers are used in precision farming to monitor crop health, optimize irrigation,and increase yield.15.Space Exploration:In space exploration,computers are used to control spacecraft, analyze data from space missions,and simulate space environments.In conclusion,the versatility of computers is astounding,and their influence on modern society is profound.As technology continues to advance,the applications of computers are likely to expand even further,offering new opportunities and challenges for the future.。

Geometric Computing with CGAL and LEDAKurt Mehlhorn and Stefan SchirraAbstract.LEDA and CGAL are platforms for combinatorial and geo-metric computing.We discuss the use of LEDA and CGAL for geometriccomputing and show that they provide a unique framework for exact,ef-ficient and convenient geometric computing.§1.IntroductionLEDA(Library of Efficient Data Structures and Algorithms)[16,17]and CGAL (Computational Geometry Algorithms Library)[8,26]are platforms for com-binatorial and geometric computing developed in the ESPRIT-projects AL-COM II,ALCOM-IT,CGAL,and GALIA.Concerning geometric computing, the systems provide number types,geometry kernels,geometric algorithms, and visualization.They by now provide a significant fraction of the algorithms and data structures described in the computational geometry literature,where in this context computational geometry subsumes thefield covered by the an-nual ACM Symposia on Computational Geometry.The systems are designed such that it is easy to build programs on top of them.The computations in LEDA and CGAL are exact,i.e.,behave according to their mathematical specifications.This is a strong point of both systems,distinguishing them form many other geometric software.Based on the insight that algorithm design must include implementa-tion to have maximal impact,Kurt Mehlhorn and Stefan N¨a her started the development of the LEDA software library of efficient data structures and al-gorithms in Saarbr¨u cken in’89using C++as programming language.LEDA is now developed at Max-Planck-Institut f¨u r Informatik,Saarbr¨u cken(Ger-many),and Martin-Luther-Universit¨a t Halle-Wittenberg(Germany).The idea of CGAL was conceived in fall of’94,inspired by the success of LEDA and in order to bundle forces previously put into predecessors of CGAL[2,11,20]. Development of CGAL was started in fall’96in the CGAL-project and isSaint-Malo Proceedings1 Pierre-Jean Laurent,Paul Sablonni`e re,and Larry L.Schumaker(eds.),pp.277–286. Copyright o c2000by Vanderbilt University Press,Nashville,TN.ISBN0-8265-1356-6.All rights of reproduction in any form reserved.2K.Mehlhorn and S.Schirranow continued in the GALIA-project.GALIA is carried out by Max-Planck-Institut f¨u r Informatik,Saarbr¨u cken,ETH Z¨u rich(Switzerland),Freie Uni-versit¨a t Berlin(Germany),INRIA Sophia-Antipolis(France),Martin-Luther-Universit¨a t Halle-Wittenberg,Tel-Aviv University(Israel),and Utrecht Uni-versity(The Netherlands).The goal is to make the most important of the so-lutions and methods developed in computational geometry available to users in industry and academia in a C++library.§2.The Need for a Geometry Software LibraryReusing code that already exists and is used and thereby tested rather than implementing everything from scratch saves development time and hence re-duces cost[5].It also eases maintenance of code.Software libraries also ease the transfer of state-of-the-art algorithmic knowledge into application areas. Since geometric computing is a wide area,many application areas can bene-fit from the availability of the re-usable code of a geometry software library. The importance of libraries of software components in subject area domains is clearly stated in a recent report of the information technology advisory committee of the president of the US[22].In geometric computing,software libraries consisting of reliable compo-nents are particularly useful,since implementors of geometric algorithms are faced with notoriously difficult problems[18],especially the problems of ro-bustness and degeneracies.RobustnessTheory usually assumes exact computation with arbitrary real numbers,while the standard substitution for real numbers in scientific computing in practice,floating-point arithmetic,is inherently imprecise.In practice,implementa-tions of geometric algorithms compute garbage or completely fail more or less occasionally,because rounding errors lead to wrong and contradictory deci-sions,see[14,25,27].Withfloating-point arithmetic,basic laws of arithmetic, on which the correctness proof of geometric algorithms is based,of course, don’t hold anymore.We invite the reader to carry out the following simple experiment:Compute the point of intersection of the two lines with built-in floating point arithmetic.Then,again using built-infloating point arithmetic, check whether the computed intersection point lies on the intersecting lines.Figure1shows an incorrect result of a computation due to rounding errors.The task is to compute the extreme points of intersection points of a set of line segments,where a point is called extreme with respect to a set of points if its removal from the set changes the convex hull of the point set.The line segments have randomly chosen endpoints lying on a circle.In afirst step the intersection points of the line segments are computed,then a convex hull algorithm is run on the points computed in thefirst step.Withfloating-point arithmetic,some collinearities are not detected and too many extreme points are reported.Extreme points are shown as small disks in Figure1.The points surrounded by a circle are actually not extreme.In the problem consideredCGAL and LEDA3Fig.1.Extreme points among intersection points of30line segments. here,the computed output might still be useful;for many other geometric problems,however,failures of purefloating-point based implementations are much more drastically.They just crash.Adding epsilons by trial and error to equality tests used to be common practice in implementations of geometric algorithms,but it in no way leads to a reliable correct implementations.Two main approaches to solving the precision-caused robustness problem can be identified.Thefirst is re-designing algorithms such that they can deal with imprecision,pute a good ap-proximate solution,but never crash.This approach has been applied success-fully to only very few basic problems in computational geometry so far,see [14,25,27].The second approach is exact geometric computation[28],which means computing with such a precision that an implementation behaves like its theoretical counterpart,and therefore according to its mathematical speci-fication.This is possible for many geometric problems,at least,theoretically. Note that in practice,the input does not involve arbitrary real numbers.Of course,exact geometric computation slows down computation,but thanks to clever adaptive computation usingfloating-point arithmetic whenever known to produce the correct result[10,15],it is now much closer to the speed of floating-point computation than it used to be a decade ago.Since libraries must be reliable in order to be usable in general,the exact geometric compu-tation approach is taken in LEDA and in CGAL.DegeneraciesRobustness problems caused by rounding errors are closely related to degen-eracies,i.e.“exceptional”input configurations.Theory often neglects degen-4K.Mehlhorn and S.Schirra eracies for the sake of a cleaner exposition of an algorithm,and also because they are rare from a theoretical point of view:they have measure zero in the set of all possible inputs over the real numbers.In practice,however,they occur frequently.Since theory papers often leave handling degenerate cases as an exercise to the reader,implementors are often left alone with the burden of investigating the details of handling degeneracies.Furthermore,this leads to treating degeneracies as an afterthought,which is,according to our expe-rience[3],not the most suitable way to think about them,since it leads to unnecessarily complicated and blown-up code.Considering degeneracies right from the beginning seems to be a much better approach.Symbolic perturbation schemes have been proposed as a general approach to removing degeneracies,for an overview see[24].With this approach,the input is perturbed symbolically such that no degeneracies arise anymore.The perturbed input can then be processed by an algorithm assuming general position.The computed output,however,does not correspond to the actual input,but to the perturbed input.Therefore,the complexity of the output might be much larger than the output for the actual input[3].For some problems,the symbolic perturbation approach works outfine;for others,a postprocessing step is required to deduce the actual output from the output computed for the perturbed input.In many cases,this is a non-trivial task, as hard as dealing with degeneracies directly.Algorithms and data structures in CGAL and LEDA handle all possi-ble degenerate case by default.So a user need not to worry about all the degenerate cases.If an algorithm or data structure should not handle a de-generate case,this is clearly stated in the documentation and this precondition is checked in the implementation.However,mainly to support rapid proto-typing,CGAL also provides tools for symbolic perturbation.A general ran-domized symbolic perturbation scheme is available for the CGAL kernels[6].A new promising approach that has been started within the CGAL project, is controlled perturbation[23].Here the input is perturbed numerically,such that general position is guaranteed.§3.Number TypesThe lowest level in geometric computing is the arithmetic level.LEDA and CGAL provide various number types to support exact geometric computation. LEDA provides ledarational,a number type for arbitrary precision rational arithmetic,based on leda bigfloat, a number type forfloating point arithmetic with extended precision.A user can choose the mantissa length of the ledareal[4].This number types models a subset of algebraic numbers:All integers are leda real s are closed under the operations+,−,·,/,and k√real s record the computa-tion history in an expression dag,and use adaptive evaluation to guaranteeCGAL and LEDA5that all comparison operations give the correct results.They use bigfloat s internally.LEDA and CGAL also provide interval arithmetic.Furthermore, CGAL provides somefixed point arithmetic based on built-in float s,as well as wrappers for the gnu multiple precision integer arithmetic[12]and the number types provided by CLN[13].§4.Geometry KernelsThe kernel of a geometry library contains the basic geometric objects and basic operations on them like points,lines,planes,sideness test,intersection and distance computations.LEDA provides an exact geometry kernel for rational computations.In-ternally,it usesfloating-pointfilters[10,15]to speed up exact computation. Withfloating-pointfilters,an expression whose sign has to be computed is first evaluated usingfloating-point arithmetic.Moreover,an upper bound on the error of thefloating-point computation is computed as well.By compari-son of the absolute computedfloating-point value with this error bound,it is checked whether thefloating-point computation is guaranteed to be reliable. If the sign can not be deduced withfloating-point arithmetic,the expression is re-evaluated with a more reliable arithmetic.In case of the rational geometry kernel in LEDA,arbitrary precision integer arithmetic is used.The rational geometry kernel of LEDA uses homogeneous coordinates and is coupled to the number types leda integer.CGAL provides two families of geometry kernels,one based on Cartesian coordinates and one based on homogeneous coordinates[9].Both kernels are parameterized by a number type.All number types fulfilling a very small list of requirements can be used with the CGAL kernels.For example,the user might choose the Cartesian kernel with rational arithmetic or the ho-mogeneous kernel with integer arithmetic.In particular,for computations involving k-th root operations,the number type ledareal is certainly the most convenient way to get reliable computation.LEDA also provides a kernel that uses double precisionfloating-point arithmetic internally.Similarly,the CGAL kernels can be used with built-infloating point number types as well.This might be sufficient for some problems,but since correctness can not be guaranteed,the use of these kernels is not recommended in general.§5.Geometric Algorithms and Data StructuresCGAL and LEDA by now provide a significant fraction of the algorithms and data structures described in the computational geometry literature.They pro-6K.Mehlhorn and S.Schirra vide several algorithms to compute convex hulls in low and higher dimensions. They provide algorithms and data structures for triangulations,constrained triangulations,Delaunay triangulations,regular triangulations,and Voronoi diagrams in two-dimensional space and Delaunay triangulations and regular triangulations in three-dimensional space.Furthermore they provide several algorithms for line segment intersection and regularizing Boolean operations on polygons.CGAL and LEDA also provide a number of query data struc-tures.For example,there are range-and segment trees,kd-trees,as well as a data structure for range and nearest neighbor queries based on Delaunay triangulations.CGAL provides data structures for polyhedral surfaces based on a half-edge data structure,it provides a topological map data type and a planar map data structure,and a data structure for arrangements.The libraries also contain algorithms for curve reconstruction in the plane.CGAL and LEDA provide algorithms for a number of geometric opti-mization problems.There are algorithms computing smallest enclosing circles, smallest enclosing ellipses,and smallest enclosing spheres,the latter in any dimension.Furthermore,there are a number of algorithms based on matrix search like computing extremal polygons and rectangular p-centers.LEDA also contains algorithms for computing smallest enclosing annuli with respect to area and width,and algorithms to compute minimum spanning trees for a set of points.The geometric algorithms of LEDA come in two versions,one using the exact rational geometry kernel and one using the unreliablefloating-point kernel.CGAL’s algorithms and data structures are even moreflexible with respect to the geometry kernel used.All algorithms and data structures of CGAL are parameterized by a template parameter called traits class.This traits class provides an algorithm or data structure with all the type infor-mation it needs.It tells the algorithm on which types it should operate and which types it should use to do that.The parameterization and the resulting genericity of CGAL’s algorithms and data structures is best illustrated by a simple,but instructive example. Computing the convex hull of a set of points in the plane is an intensively studied problems in computational geometry.The input is a set of points in the plane,the output is the counterclockwise sequence of extreme points. Andrew’s variant[1]of the Graham scan algorithm can be formulated in such a way that it needs only two primitive operations on the points,namely a primitive to compare two points in order to sort the points lexicographically by their Cartesian coordinates,and a primitive to check the order type of a triple of points,more precisely,to check whether a sequence of three points forms a left turn.The CGAL implementation of Andrew’s algorithm is parameterized by a point type and the two required primitive operations.The latter two are passed as function object types and need to correspond to the point type. We call the parameter types of an algorithm or data structure the traits types. To avoid long lists of template parameters,the traits types are collected in the traits class.Note that the parameterization is on the level of data types, not on the level of objects.In order to use the CGAL implementation ofCGAL and LEDA7 Andrew’s algorithm with a point type from a CGAL kernel,no traits class needs to be specified.CGAL adds an appropriate one.If a user wants to run the algorithm on a different point type,for example,a point type from some other C++library or system,for example from LEDA or from some Geographical Information System,an appropriate traits class for this point type must be passed to the function in order to tell it which operations it should use.That’s it.Given such a traits class,the algorithm now works with non-CGAL types as well.CGAL provides traits classes for both LEDA kernels.The parameterization by a traits class can be used to avoid explicit trans-formation of the data.Assume that we have points in three dimensional space. Using a traits class that provides a comparison primitive and an order type predicate that both operate on x and y coordinates of the points only,the CGAL implementation of Andrew’s algorithm can be used to compute the se-quence of three-dimensional points whose projections onto the xy-plane form the convex hull of the projections of all points onto that plane.There is no need to explicitly transform the points into two-dimensional points.With an appropriate traits class,the algorithm can directly operate on the three-dimensional points.This saves time and space.This feature is most likely even more interesting for Delaunay triangula-tions.Assume we have a triangulated irregular network(TIN),and we want to make a TIN with the same set of vertices without long and skinny triangles. This is usually accomplished by computing the two-dimensional Delaunay tri-angulation of the projections of the vertices of the TIN and lifting the vertices and triangles again.CGAL allows you to do this without explicit projection using an appropriate traits class.There are further examples where traits classes can be used nicely in the context of geometric transformations.§6.VisualizationIn LEDA,there is a data type ledascene maintains a container with geometric objects.The GeoWin data type can be used for the construction and display of geometric objects and data structures,the visualization of geometric algorithms,writing interactive demos for geometric algorithms and debugging geometric algorithms.8K.Mehlhorn and S.Schirra§7.ConclusionsReliability means that software behaves as specified.Unfortunately,there are many exceptions to this rule for geometric software,mainly due to the issues discussed in Section2.Correctness and reliability are even more important for the components of a software library.You might be willing to accept shortcomings of a program designed for a special purpose,if problematic input instances never arise in your context.Since library component need to be generally applicable,any such shortcomings are not acceptable.CGAL(if used with a number type for exact geometric computation)and LEDA(with the rational kernel)provide geometric software that behaves according to its mathematical specification.That makes it easy to combine components form these libraries,and to build larger entities out of these components.The use of exact computation alone can not guarantee correctness.CGAL and LEDA also use program checking[19]to increase reliability of its compo-nents.A program checker need not compute the output for a given input.It already gets both input and output,and then has to verify that the output is the correct output for the given input.While a program gets x and has to compute f(x),a checker gets x and y and must only check whether y=f(x). The latter step should be computationally simpler,such that it is less likely that its implementation is buggy.At present,LEDA and CGAL consists of more than100,000lines of C++ code each.Neither library provides class libraries in the sense of Smalltalk,but both provide fairly small class hierarchies if any.CGAL uses the generic pro-gramming paradigm that became known with the Standard Template Library (STL),which is now part of Standard C++.This makes CGAL veryflexible, moreflexible than LEDA.On the other hand,LEDA is a more complete, closed programming framework that also contains very useful components for combinatorial computing.Due to its generic design,CGAL is more open.It often relies on other sources for basic non-geometric data structures,mainly on the STL.Due to its generic design,it works well together with LEDA. Since CGAL has a more modern design and is developed by a larger group of people,the future will certainly be with CGAL.However,LEDA’s com-ponents for geometric computing will continue to be useful,especially within CGAL.For more information and to download LEDA,seehttp://www.mpi-sb.mpg.de/LEDAFor more information and to download CGAL,seehttp://www.cs.uu.nl/CGAL Acknowledgments.Work on this paper has been supported by ESPRIT-IV LTR project28155(GALIA).CGAL and LEDA9References1.A.M.Andrew,Another efficient algorithm for convex hulls in two dimen-rm.Process.Lett.9(1979),216–219.2.F.Avnaim,C++GAL:A C++Library for geometric algorithms,INRIASophia-Antipolis,1994.3.C.Burnikel,K.Mehlhorn,and S.Schirra,On degeneracy in geometriccomputations,Proc.of the5th ACM-SIAM Symp.on Discrete Algo-rithms,1994,16–23.4.C.Burnikel,R.Fleischer,K.Mehlhorn,and S.Schirra,Efficient exactgeometric computation made easy,in Proc.15th Annu.ACM Sympos.Comput.Geom.,1999,341–350.5.M.D.Carroll,M.A.Ellis,Designing and Coding Reusable C++,Addison-Wesley,1995.es and M.Ziegelmann,An easy to use implementation of linearperturbations within CGAL,in Algorithm Engineering,WAE99,Lect.Notes in Comp.Science vol.1668,Springer Verlag,1999,169–182.7.P.Epstein,J.Kavanagh,A.Knight,J.May,T.Nguyen,and J.-R.Sack,A workbench for computational geometry,Algorithmica,11(1994),404–428.8.A.Fabri,G.-J.Giezeman,L.Kettner,S.Schirra,and S.Sch¨o nherr,On thedesign of CGAL,a computational geometry algorithms library.Software –Practice&Experience,special issue on Algorithm Engineering9.A.Fabri,G.-J.Giezeman,L.Kettner,S.Schirra,and S.Sch¨o nherr.TheCGAL Kernel:A basis for geometric computation.In Workshop on Ap-plied Computational Geometry(WACG’96),Lect.Notes in Comp.Sci-ence vol.1148,1996,191–202.10.S.Fortune and C.van Wyk.Static analysis yields efficient exact integerarithmetic for computational geometry.ACM Transactions on Graphics, 15(1996),223–248.11.G.-J.Giezeman,PlaGeo,a library for planar geometry,and SpaGeo,alibrary for spatial geometry,Utrecht University,1994.12.T.Granlund,GNU MP,The GNU multiple precision arithmetic library,2.0.2edition,June1996.13.B.Haible,CLN,The class library for numbers,1.0.1edition,June1999./~haible/packages-cln.html.14.C.Hoffmann,The problem of accuracy and robustness in geometric com-putation.IEEE Computer,March1989,31–41.15.M.Karasick,D.Lieber,and L.Nackman,Efficient Delaunay triangulationusing rational arithmetic.ACM Transactions on Graphics,10(1991), 71–91.16.K.Mehlhorn,S.N¨a her,M.Seel,and C.Uhrig,The LEDA user manual,version4.0,1999.10K.Mehlhorn and S.Schirra 17.K.Mehlhorn and S.N¨a her.The LEDA Platform for Combinatorial andGeometric Computing.Cambridge University Press,1999.18.K.Mehlhorn and S.N¨a her,The implementation of geometric algorithms,13th World Computer Congress IFIP94,volume1.Elsevier Science B.V.North-Holland,Amsterdam,1994,223–231.19.K.Mehlhorn,S.N¨a her,T.Schilz,S.Schirra,M.Seel,R.Seidel,andC.Uhrig.Checking Geometric Programs or Verification of GeometricStructures Computational Geometry:Theory and Applications12(1999), 85-103.20.J.Nievergelt,P.Schorn,M.de Lorenzi,C.Ammann,and A.Br¨u ngger,XYZ:A project in experimental geometric computation,Computational Geometry:Methods,Algorithms and Applications,Lect.Notes in Comp.Science vol.553.Springer-Verlag,1991,171–186.21.M.Overmars,Designing the computational geometry algorithms libraryCGAL,in M.C.Lin and D.Manocha,editors,Applied Computational Geometry:Towards Geometric Engineering(WACG96),53–58.Lect.Notes in Comp.Science vol.1148,1996.22.Presidents Information Technology Advisory Committee,Interim Reportto the President,sect.3.1.2,/ac/interim/,1998.23.S.Raab.Controlled perturbation for arrangements of polyhedral surfaceswith application to swept volumes,in Proc.15th ACM symposium on Computational Geometry,1999,163–172.24.R.Seidel.The nature and meaning of perturbations in geometric com-puting.Proc.11th Sympos.Theoret.Aspects Comput.Sci.,Lect.Notes Comp.Science vol.775,Springer Verlag,1994.25.S.Schirra,Precision and robustness issues in geometric computation,Handbook on Computational Geometry,Elsevier Science Publishers,Am-sterdam,The Netherlands,1999.26.S.Schirra,R.Veltkamp,M.Yvinec(Eds.),CGAL reference manuals,version2.1,1999.27.C.K.Yap,Robust geometric computation.In J.E.Goodman and J.O’Rourke,editors,CRC Handbook on Discrete and Computational Ge-ometry,CRC Press,1997,653–668.28.C.K.Yap and T.Dub´e,The exact computation paradigm.In D.Du andF.Hwang,editors,Computing in Euclidean Geometry,452–492.WorldScientific Press,1995.2nd edition.Kurt Mehlhorn and Stefan SchirraMax-Planck-Institut f¨u r Informatik66123Saarbr¨u ckenGermanymehlhorn@mpi-sb.mpg.destschirr@mpi-sb.mpg.de。

distributed by hash (id)语法Distributed By Hash (ID) SyntaxIn computer science, the distribution of data plays a critical role in achieving efficient and scalable systems. One popular method for distributing data is through the use of a hash function. This article will explore the concept of distributing data by hash (ID) syntax and examine its application in various scenarios.1. IntroductionDistributed systems often face challenges in balancing workload and ensuring optimal resource utilization. To achieve this, data partitioning techniques are employed, and one of the most widely used methods is distributing data by hash (ID) syntax. This approach evenly distributes data across a distributed system based on the hash value of a unique identifier (ID).2. Hash FunctionsBefore delving into distributed data by hash (ID) syntax, let's first understand hash functions. A hash function is an algorithm that takes an input (such as a data item or an ID) and produces a fixed-size output, typically a hash value or hash code. The output is deterministic, meaning the same input will always produce the same output. Hash functions are designed to provide uniform distribution of values, preventing collision and enabling efficient data retrieval.3. Distributed Data by Hash (ID) SyntaxDistributing data by hash (ID) syntax involves the following steps:3.1 Identifying the Hash KeyIn the context of distributed systems, the hash key refers to the attribute or field that will be hashed to determine data distribution. Typically, this key is an ID or a unique identifier associated with each data item.3.2 Applying the Hash FunctionOnce the hash key is identified, the hash function is applied to it. The output of the hash function will be a hash value, which is essentially a transformed representation of the original ID. This hash value will be used to determine the data's distribution in the system.3.3 Determining Data PlacementThe hash value obtained from the previous step is used to determine the placement of data within the distributed system. A common approach is to divide the hash value by the total number of available nodes or partitions. The resulting remainder is then used to determine the specific node or partition where the data will reside.4. Advantages of Distributed Data by Hash (ID) SyntaxDistributing data by hash (ID) syntax offers several advantages:4.1 Load BalancingBy using a hash function to evenly distribute data across nodes or partitions, distributed systems can achieve load balancing. Each node or partition will handle a similar amount of data, ensuring optimal resource utilization and preventing bottlenecks.4.2 ScalabilityAs the system grows, new nodes or partitions can be added without requiring significant data migration. In distributed data by hash (ID) syntax, each node or partition is responsible for a specific range of hash values. Therefore, the addition of new nodes only affects the distribution of future data, rather than requiring the redistribution of existing data.4.3 Data LocalityDistributed data by hash (ID) syntax ensures that related data items are likely to be stored on the same node or partition. This improves data locality, reducing network latency and improving query performance when accessing related data.5. Use CasesThe distributed data by hash (ID) syntax finds applications in various scenarios, such as:5.1 Distributed DatabasesHash-based data distribution is commonly used in distributed database systems. It allows for efficient parallel processing of queries since related data is often stored on the same node, reducing the need for expensive cross-node communication.5.2 Content Distribution Networks (CDNs)CDNs leverage distributed data by hash (ID) syntax to cache content across multiple edge servers. The hash value determines which server willstore and serve the requested content, improving content delivery speed and reducing the load on individual servers.6. ConclusionDistributing data by hash (ID) syntax offers an effective and scalable approach to data partitioning in distributed systems. By leveraging hash functions and utilizing hash values to determine data placement, load balancing, scalability, and data locality can be achieved. Whether in distributed databases or content distribution networks, the use of this syntax enhances system performance and efficiency.。

级联稀疏卷积与决策树集成的病理图像细胞核分割方法宋 杰 1, 2 肖 亮 2, 3 练智超 2摘要 数字病理图像分析对于乳腺癌、肾癌等良恶性分级诊断具有重要意义, 其中细胞核的形态测量是病理量化分析的关键. 然而, 由于病理图像背景复杂, 细胞核高密度分布、细胞粘连等, 个体细胞核精准分割是一个挑战性问题. 本文提出一个级联稀疏卷积与决策树集成学习的细胞核分割模型. 该模型由稀疏可分离卷积模块和集成决策树学习的正则化回归模块堆叠级联组成, 其中: 前者采取秩-1张量分解学习机制, 可分层抽取细胞核的多尺度方向分布式抽象特征; 而后者采取随机采样、树剪枝以及正则化回归机制提升逐像素回归分类能力. 相比于现有深度学习模型, 该模型无需非线性激活和后向传播计算, 参数规模较小, 可实现端到端的学习. 通过乳腺、前列腺、肾脏、胃和膀胱等多组病理图像的分割实验表明: 该模型能够实现复杂数字病理图像中的高密度细胞核的快速个体目标检测和分割, 在Jaccard相似性系数、F1分数和平均边缘距离三个指标上均优于目前CNN2、CNN3和U-Net等深度学习方法, 具有较好应用前景.关键词 数字病理, 细胞核分割, 级联稀疏可分离卷积, 集成决策树, 正则化回归, 深层表征学习引用格式 宋杰, 肖亮, 练智超. 级联稀疏卷积与决策树集成的病理图像细胞核分割方法. 自动化学报, 2021, 47(2): 378−390 DOI 10.16383/j.aas.c190672Cascade Sparse Convolution and Decision Tree Ensemble Model for NuclearSegmentation in Pathology ImagesSONG Jie1, 2 XIAO Liang2, 3 LIAN Zhi-Chao2Abstract The quantitative analysis of digital pathology images plays a significant role in the diagnosis of benign and malignant diseases such as breast and prostate cancer, in which nuclear morphology measurement serve as a basis of quantitative analyses. However, due to the complex background of pathology images, dense distributions of nuclei, and nucleus adhesions, accurate segmentation of individual nuclei remains a challenging problem. In this pa-per, we propose a new method to automatically segment nuclei from digital pathology images with cascade sparse convolution and decision tree ensemble (CscDTE) model. In particular, the sparse separable convolution learning module and the decision tree ensemble learning module are stacked in a cascaded manner to form the CscDTE mod-el. The former adopts rank-one tensor decomposition learning mechanism that can extract multiscale and multi-dir-ectional distributed abstract features; while the latter employs random sampling, pruning, and regularized regres-sion mechanism to boost per-pixel regression and/or classification performance. Compared with the popular deep neural networks, the proposed CscDTE model does not require nonlinear activation and backpropagation computa-tion, and depends on fewer parameters. Our CscDTE model is trained in a layer-wise manner that can achieve an end-to-end pixelwise learning and fast nuclear detection and segmentation in high-throughput imagery. We demon-strated the superiority of our method in terms of Jaccard index, F1 score, and average boundary distance by evalu-ating it on the multi-disease state and multi-organ dataset where consistently higher performance was obtained as compared to convolutional neural networks and fully convolutional networks.Key words Digital pathology, nuclear segmentation, cascade sparse separable convolution, decision tree ensembles, regularized regression, deep representation learningCitation Song Jie, Xiao Liang, Lian Zhi-Chao. Cascade sparse convolution and decision tree ensemble model for nuclear segmentation in pathology images. Acta Automatica Sinica, 2021, 47(2): 378−390收稿日期 2019-09-23 录用日期 2020-03-12Manuscript received September 23, 2019; accepted March 12, 2020国家自然科学基金(61871226, 62001247), 国家重点研发计划(2016YFF0103604), 中央高校基本科研专项资金(30918011104),江苏省社会发展重点研发计划(BE2018727), 南京邮电大学引进人才科研启动基金(NY219152), 江苏省高等学校自然科学研究面上项目(20KJB520005)资助Supported by National Natural Science Foundation of China (61871226, 62001247), National Major Research Plan of China (2016YFF0103604), Fundamental Research Funds for the Cent-ral Universities (30918011104), Jiangsu Provincial Social Develo-ping Project(BE2018727), NUPTSF (NY219152), Natural Science Foundation for Colleges and Universities in Jiangsu Province (20KJB520005)本文责任编委 张道强Recommended by Associate Editor ZHANG Dao-Qiang1. 南京邮电大学自动化学院、人工智能学院 南京 2100232. 南京理工大学计算机科学与工程学院 南京 2100943. 高维信息智能感知与系统教育部重点实验室 南京 2100941. College of Automation & College of Artificial Intelligence, Nanjing University of Posts and Telecommunications, Nanjing 2100232. School of Computer Science and Engineering, Nanjing University of Science and Technology, Nanjing 2100943. Key La-boratory of Intelligent Perception and Systems for High-Dimen-sional Information of Ministry of Education, Nanjing 210094第 47 卷 第 2 期自 动 化 学 报Vol. 47, No. 2 2021 年 2 月ACTA AUTOMATICA SINICA February, 2021复杂背景病理图像个体细胞分割是在成千上万个体细胞汇集的图像中逐个分割出具有相对完整边界的细胞, 为后续细胞形态计算和病理特征提供定量分析. 传统的病理切片分割方法, 需要经过专门训练的病理医师在图像中逐个寻找感兴趣区域(Regions of interest, RoI), 而后根据专业知识分析诊断. 一张病理切片通常包含成百上千个细胞或细胞核, 这给医师带来很大的工作负担, 疲劳阅片现象时有发生[1]. 虽然目前已有很多病理细胞图像处理方法, 但这些方法大多只关注于特定类型或单一器官的细胞或细胞核分割. 因此, 临床和医学研究迫切需要能够进行多个器官和疾病状态的细胞核病理图像高精度分割方法[2]. 然而, 如图1所示, 个体分割具有如下挑战: 一方面, 对于病理状态(例如增生或某种癌症亚型)图像而言, 由于细胞核增大, 并呈现染质浓集贴边, 即核內染质较浅, 而边缘附近染质较深; 而着色较深的核仁也大量出现在核内.另一方面, 由于病理图像中往往细胞密度高、细胞间出现重叠和成团等突出问题, 加剧了个体细胞分割的难度. 目前方法体系主要分两类: 传统基于人工特征的图像分割方法和基于表示特征学习的图像分割方法.(a)(b)(c)(d)(e)(f)图 1 病理细胞核图像分割的挑战与人工分割结果Fig. 1 Challenges in nuclear segmentation andassociated ground truth传统图像分割方法包括: 水平集方法、图论方法和分水岭方法等. 水平集算法是目前比较流行的分割方法. 其基本模型包括两类: 基于边缘的水平集模型[3]和基于区域的水平集模型[4]. 近年来, 基于后者, 很多改进的方法[5]被提出来广泛应用于病理图像的细胞分割中. 在现有方法中, 基于图论的分割方法是病理图像分析中应用最为广泛的技术之一. 最常用算法是最小割算法[6], 除了主流的图割方法, 其他类型的图模型也已经应用到个体细胞核的分割, 例如属性关系图模型[7]. 另一类基于图像分析的代表性方法是分水岭算法, 分水岭算法通常期望目标细胞核内灰度分布均匀, 并且目标与背景具有明显灰度或颜色差异. 图像中的噪声、目标内部灰度变化, 都会产生过度分割的现象. 为此, 人们提出若干标记控制的分水岭及其变种算法[8−10]. 传统图像分割方法为了得到精确的个体分割结果, 通常需要分析RoI 特有属性来设计额外的后处理步骤, 从而导致算法可迁移性较差.虽然深度学习方法能较好地处理病理图像细胞核表观多样性的分割问题, 但由于网络架构、网络复杂性以及超参数的影响, 使其分割性能受到限制.针对病理图像细胞核表观多样性的分割问题及深度神经网络的局限性, 国内外研究者提出了系列具有较小参数规模的快速浅层分割学习模型. 与现有深度学习模型相比, 浅层学习模型无需非线性激活和后向传播计算, 且学习模型参数规模较小. 传统浅层分割学习方法[11−12]为了得到密集预测结果, 通常使用像素周围的一个图像块作为模型的输入用于训练和预测. 由于只能提取一些局部的特征, 从而导致分割的性能受到限制. 而基于卷积操作的浅层学习模型[13−18]则是从抽象的特征中恢复出每个像素所属的类别, 从而可以实现比传统模型更加精确的分割结果. 然而, 这类浅层分割学习模型没有充分考虑像素间的局部依赖关系, 因此对图像细节特征快速捕获和紧致表达能力有待加强. 此外, 在传统集成决策树学习算法中最先学习得到的一两棵树对预测结果的影响最为显著, 这使得整个模块对这些树所做出的决策过于敏感, 容易产生过拟合现象.为了解决这些问题, 本文的主要贡献是:1) 提出了级联稀疏卷积与决策树集成(Cas-cade sparse convolution and decision tree en-semble, CscDTE)学习模型, 该模型没有非线性激活和后向传播计算, 且学习模型参数规模较小, 其特征学习过程具有一种替代深度神经网络的新型学习机制;2) 采取多层稀疏可分离卷积特征学习捕获图像上下文特征; 采取秩-1张量分解[19]的可分离卷积加速特征学习过程;3) 建立集成决策树学习的正则化回归模型, 采取局部二阶近似逼近优化决策树, 提高分类回归泛化性能;4) 在乳腺、前列腺、肾脏、胃和膀胱等多组病理图像的分割实验表明该模型优于目前CNN2、CNN3和U-Net 等深度学习方法, 对于病理图像分割具有较好应用前景.2 期宋杰等: 级联稀疏卷积与决策树集成的病理图像细胞核分割方法3791 相关工作1.1 浅层特征学习方法J f ={f j }J j =1浅层特征学习分割方法中代表性方法包括稀疏编码方法[11, 13]以及多层稀疏卷积特征学习方法[15−18].相比标准的卷积滤波器组来说, 稀疏可分离卷积滤波器组能够在不影响其性能的情况下大大降低计算复杂度. 例如Sironi 等[13−15]通过学习一组可分离卷积滤波器有效提取图像中曲线状奇异边缘结构. 具体地, 稀疏卷积滤波器学习方法是利用一组样本,通过利用稀疏编码方法[20−21]学习 个卷积滤波器 : =f j ∈R d ×d ,a i j I iβa i j f j {f j }J j =1{f j }Jj =1I m ={m j }J j =1,m j =f j ∗I,∗其中, 是输入图像 的稀疏编码, 是正则化参数. 模型(1)可通过交替方向法[22]迭代优化更新 和 进行求解. 当得到一组卷积滤波器 之后, 则可以采取 对图像 进行卷积生成一组卷积特征图 其中, 符号 表示卷积运算. 受稀疏编码方法的启发, Song 等[16]通过在线学习稀疏卷积特征并在模型更深层引入上下文信息实现了鲁棒的显微颗粒目标联立检测和分割. 进一步, Song 等[17]通过结合分层稀疏特征学习和人工特征, 设计了Boosting 判别概率二叉决策树分类方法.1.2 深层特征学习方法随着深度学习的兴起, 研究者提出了系列深层特征表示学习的病理图像分割方法[23−27]. 代表性网络包括卷积神经网络(Convolutional neural net-works, CNN)[24−25] 和全卷积网络(Fully convolu-tional network, FCN)[26−27]. 深度学习方法为解决细胞核表观多样性的图像分割问题提供了有效途径.通常, CNN 网络在卷积层之后会接上若干个全连接层, 将卷积层产生的特征图映射成一个固定长度的特征向量, 以实现图像级的分割任务[28] (见图2).例如, Xing 等[24]针对组织病理细胞核图像, 构建了两个卷积—池化层对和两个全连接层构成的CNN2模型, 实现了端到端的模型训练, 进而对测试图像的细胞核进行分割. 在此基础上, Kumar 等[25]提出了更深的CNN3模型, 实现了更广泛病理图像的分割. 与CNN 不同, FCN 可以接受任意尺寸的输入图像, 采用反卷积层对最后卷积层的特征图进行上采样, 使它恢复到输入图像相同的尺寸, 从而可实现逐像素预测, 并可保留原始输入图像的空间信息,最后在上采样的特征图上进行逐像素分类[29], 完成像素级的分割. 例如, Zhang 等[26]通过结合FCN 和基于图论的方法, 提出了一种宫颈癌细胞核分割新方法. 最近, Ronneberger 等训练了一种特殊的U-Net 网络结构[27] (见图3), 通过在收缩路径上捕获全局特征和在扩展路径上实现精确定位, 较好解决了卷积最大池化卷积最大池化全连接全连接全连接分类图 2 用于病理图像分割的CNN 体系结构Fig. 2 The CNN-style architecture for pathology image segmentation卷积反卷积图 3 用于病理图像分割的U-Net 体系结构Fig. 3 The U-Net-style architecture for pathology image segmentation380自 动 化 学 报47 卷复杂神经元结构的分割问题. 然而, 深度学习方法需要较大规模的训练数据集以经验拟合深层网络参数.目前, Zhou 等提出了一种多粒度级联森林方法, 称为gcForest [12]. 这是一种采取非神经网络, 而采取决策树集成的方法, 性能较之深度神经网络有很强的竞争力. 深度神经网络需要花大力气调参,相比之下, gcForest 方法更容易训练得多. 实际上,在几乎完全一样的超参数设置下, gcForest 在处理不同领域的不同数据时, 也能达到极佳的性能.2 本文方法(m ,y )m ={f 1,j ∗I }J 1j =1I f 1y φh (m )h 针对病理图像细胞核表观多样性的分割问题以及深度神经网络的局限性, 本文提出了一种复杂病理细胞核分割的级联稀疏卷积与决策树集成(CscDTE)学习模型, 如图4 所示. 假设 表示训练样本集, 其中, 是从输入图像 提取的特征图集, 是第一层学习得到的卷积滤波器组, 是尝试预测的目标. CscDTE 框架旨在渐进地提供一种非线性模型 拟合数据样本, 其中, 表示模型参数.2.1 稀疏可分离卷积特征学习f j {f j }J j =1Z ∈R d ×d ×J Z j j f j Z R f j {k r }R r =1一般而言, 是满秩的, 当卷积较大图像时,计算耗时. 如果将这些卷积滤波器 堆叠成一个三维张量 , 其中, 的第 个切片对应第 个卷积滤波器 , 可发现该张量存在大量冗余特征. 为此, 为了学习可分离核, 本文进一步引入低秩张量分解技术[19], 利用一组秩为1 (秩-1)张量的线性组合来近似 , 从而实现可分离卷积核,加速特征计算. 该方法基于如下假设: 一个秩为 的滤波器 总能由一组秩-1可分离核: 线f j =∑Rr =1c r j k r c rj f j {k r }R r =1c r j f j R <JR 性表示: , 其中, 为标量权重. 此时所有的 共享同一组秩-1可分离核 , 只有权重系数 因不同的 而改变, 且 . 因此,为了得到上式中的分解形式, 本文利用低秩张量分a r b r d c r J ◦k r a r b r k r =a r ◦b r f j c r j c r j k r m {k r }R r =1I R J J 1×1其中, 和 均是长度为 的向量, 是一个长度为 的向量, 符号 表示张量积. 式(2)的求解可通过使用共轭梯度下降法[30]来实现. 如图5所示, 可分离核 可由典范多元分解(Canonical polyadic decomposition, CPD) 成分 和 给出, 即 . 用于重构卷积滤波器 的权重 则由向量 的第 个成分给出. 为了捕获不同类型的图像特征, 本文相应学习多个可分离核组. 归于可分离卷积核的学习机制, 每个 都能分解成一个水平滤波器和一个垂直滤波器. 因此, 为了获得 , 首先使用 对图像 进行快速卷积, 生成一组可分离特征图. 然后, 针对每个像素位置, 将这些 维向量映射到一个 维向量. 这等价于在可分离特征图上应用 个空间维度为 的滤波器[31].这样, 基于秩-1张量分解学习机制, 本文实现了病理细胞核的多尺度方向分布式抽象特征的分层抽取. 模型的每层始于稀疏可分离卷积核组的训练及相应卷积特征图的计算. 然后以卷积特征作为样本输入, 通过集成决策树学习的正则化回归模块生成得分图预测结果, 如图4所示.2.2 集成决策树学习的正则化回归模型f i =f (x i ,I )∈R J I 令 表示输入图像 中像素点第一层第二层j 1j 2输入图像可分离滤波器学习d 1×d 1可分离滤波器学习线性组合集成学习稀疏可分离卷积模块1×1d 2×d 21×1集成决策树模块R 1个可分离特征图J 1个卷积特征图稀疏可分离卷积模块R 2个可分离特征图J 1+J 2个级联卷积特征图集成决策树模块线性组合集成学习图 4 两层CscDTE 学习模型示例Fig. 4 Example of two-layer CscDTE architecture2 期宋杰等: 级联稀疏卷积与决策树集成的病理图像细胞核分割方法381x i (m ,y )N {(f i ,y i )}N i =1,y i ∈R .M {h m l (·)}M m =1:RJ l→R ,M 对应的特征向量, 则从给定的样本集 中随机采样 对训练样本集 CscDTE框架中的集成决策树学习模块的目标是学习 棵既有预测能力又相对简单的决策树(见图6):并使用这 棵决策树的组合来预测每层的输出:l m h m l (·)其中, 第层第 棵决策树 定义如下:s m l (·):RJ l→{1,2,···,C m l }C m l =|h m l (·)|w s m ℓ(·)=[w 1,···,w C m l ]T ∈R C mℓ其中, 为决策树结构,表示将一个样本映射到相应的叶节点索引. 为当前决策树中叶节点的数目. 为所有叶节点的响应值向量.这样, 每棵决策树对应一个独立的结构和一组叶节点响应值. 那么, 给定一个输入样本, 就可以利用不同决策树的结构将其划分到叶节点中, 然后对相应叶节点的响应值进行累加求和来计算最终输出. 为M 了学习模块中的 棵决策树, 本文以贪婪加性方式[32−33]定义如下代价函数:y =[y 1,···,y N ]T ;ℓ2 w s m l (f )h m l (·)λγ其中, 第一项为数据拟合项, 该项中 第二项对应 正则化, 第三项 表示决策树 上叶节点的个数, 第二项和第三项将起到决策树剪枝作用[32], 用于控制决策树的复杂度来避免过拟合, 参数 为正则化系数, 参数 表示引入额外叶节点复杂度成本. 直观地, 最小化上述代价函数有利于算法选择既有预测能力又相对简单的决策树.2.3 局部二阶近似优化s m l (·)L c ˆw c =G m l,c/(H ml,c +λ2),G m l,c H ml,c ˆw c ˆL ˆs m l (·)为降低计算复杂度, 本文采用代价函数的一个局部二阶近似来对式(5)进行优化. 集成决策树学习的正则化回归算法通过计算损失函数的二阶导数, 有利于梯度下降的更快更准[34]. 这样, 对于一个固定的决策树结构 , 则可通过 的局部二阶近似计算第 个叶节点的最优响应值, 即 其中, 和 分别对应一阶梯度和海森(Hessian)值. 一旦得到 , 就可以通过计算最优 来选择最优决策树结构 . 算法终止条件为: 可预先设置决策树的最大深度值, 使得当决策树的生长到达该深度时, 算法停止继续分裂. 重复上述加性训练过程直至最后一棵决策树.zc 1jc 1c 2a 2a 1b 1b 2c Ra Rb Rc 2jc R j图 5 基于张量分解技术学习一组秩-1可分离核Fig. 5 Tensor decomposition for learning rank-1separable kernelsh l1(·)hl1a l 1hl1a l1a l m h lma l m hlmh l2(·)hl2a l2hlM −1a lM h lM (·)j l =f 1m =12m 1m 2y ∑m =1M −1∑a l m h lm m =1M∑m Jy 1随机采样加权加权加权随机采样随机采样图 6 CscDTE 框架中的集成决策树学习模块的训练过程Fig. 6 Flowchart of the training procedure for the decision tree ensemble learning module of CscDTE framework382自 动 化 学 报47 卷ˆh m l(·)αml φm l =φm −1l +αm l ·ˆh m l αm l αm l =1/M 需要注意的是, 每次迭代学习得到最优决策树 之后, 可利用线搜索算法[16]计算其相应的贡献权重 . 然后, 将当前模块更新为 . 当然, 我们也可以取平均来赋值每个权重 的值, 即 .ˆs m l (·)ˆw c 在测试阶段, 基于所学的决策树结构 , 每个新的特征样本被独立地推送到各棵训练好的决策树中. 当该特征样本到达叶节点时, 通过累加求和不同决策树最优 值来确定此测试样本的预测响应.2.4 CscDTE 学习模型L −11l φl =[φl,1,φl,2,···,φl,n ]T ,n h l ,所构建的CscDTE 框架由 个隐层和 个最终输出层构成, 且每层包含一个稀疏可分离卷积模块和一个集成决策树学习的正则化回归模块. 不妨将第 层的输出定义为 其中, 为图像的像素个数. CscDTE 模型将模块对进行堆叠, 这样上层集成决策树学习模块的得分图输出为下层稀疏可分离卷积模块的输入. 对于给定参数集合 CscDTE 模型的前向生成过程为:n l l φl l +1φl +1(·)其中, 表示从第 层输出结果 提取的特征图集, 且作为第 层集成决策树学习模块 的输入.n l [m ,n l ]n l L 如图7所示, 由于低级图像表观特征占主导作用, 较浅层对背景杂斑和细胞核内不均匀的染质较为敏感. 因此, 本文进一步引入高级上下文特征[35].具体地, 从得分图中训练一组新的稀疏可分离卷积核并获取新的上下文卷积特征图集 . 为了实现更好的预测, 采用级联卷积特征 代替 作为新层集成决策树学习模块的样本输入. 重复这一过程 次, 最终获得一个最大程度近似目标区域的输出(见图7(c)). 同时, 由于卷积特征的级联将产生分布式冗余特征, 为此, 本文采取了如下两个策略: 1)在每层训练之前, 从输入样本中随机采样新的像素位置以构建新的训练集; 2) 随机采样这些像素对应的卷积特征.(a) 得分图 j 1(a)Score map j 1(b) 得分图 j 2(b)Score map j 2(c) 得分图 j L(c)Score map j L图 7 基于本文提出的CscDTE 模型的分割改进Fig. 7 Improvement obtained by our CscDTE model3 实验结果及分析本节首先介绍用于测试分割方法的病理图像数据集, 并在此基础上, 给出所提出的CscDTE 模型的最优超参数设置. 然后, 我们描述评估指标, 并对比标记控制的分水岭分割方法[10]、C N N 2[24]、CNN3[25]、U-Net 技术[27]以及CscDTE 模型的分割性能及参数规模.3.1 数据集与最优超参数设置1000×1000癌症基因组图谱(The cancer genome atlas,TCGA)是被广泛用于细胞核分割的病理数据集,因为它覆盖了多家医院、多位病人、不同器官以及疾病状态信息. 为了最大化细胞核表观多样性, 本文使用Kumar 等采集并标注的TCGA 全切片图像(Whole slide images, WSIs)集[25] 作为算法的验证和比较. 其中, 每张图像大小为 . 为了便于算法的验证和比较, 采用Kumar 等的方法将整个数据集拆分成三个部分. 第一部分用于训练和验证, 对应12位病人, 3个器官, 包括4张乳腺病理细胞核图像、4张前列腺病理细胞核以及4张肾脏病理细胞核图像, 总共有11 460个细胞核. 因此, 不管是基于图像块级分类的分割方法还是基于像素级分类的分割方法, 即使不对数据进行扩充,这个数目也足以使它们训练出相应的学习系统, 并产生预测的分割结果. 第二部分用于相同器官的测试, 对应不同病人, 相同三个器官, 图像总数为6幅. 大多数已有的细胞核分割学习算法只局限于同一器官的训练与测试, 因此, 这一部分能够对模型的泛化能力进行有效的评估. 第三部分用于更具挑战性的不同器官的测试, 对应2个器官, 包括2张胃病理细胞核图像和2张膀胱病理细胞核图像.为了进一步验证本文方法的有效性, 本文也采用肾细胞癌(KIdney renal cell carcinoma, KIRC)2 期宋杰等: 级联稀疏卷积与决策树集成的病理图像细胞核分割方法383400×400病理数据集[36]来训练相应CscDTE 模型, 并分析分割性能. 来自TCGA 数据门户网站的KIRC 病理数据集包含了不同类型的WSIs, 涵盖了一定范围的KIRC 病理分级. 实验中, 18幅图像用于训练, 20幅图像用于测试, 且平均每幅图像具有96个细胞核,大小为 .αml 基于验证集中的样本, 采用留一交叉验证方法[37]来确定CscDTE 模型关键超参数的最优值, 包括训练样本数量、集成决策树学习模块尺寸、CscDTE 模型尺寸以及稀疏可分离卷积滤波器尺寸和数目.表1列出了在TCGA WSIs 病理数据集上所提出CscDTE 模型的最优超参数值. 在训练过程中, 随机采样四分之一的像素位置用于集成决策树学习模块的训练, 在计算每棵树的响应之后, 进而使用所有的位置样本来学习式(3)中的权重 .3.2 分割比较为了与深度学习技术进行对比, 本文研究了三种不同的网络体系: CNN2[24]、CNN3[25]和U-Net [27],并在NVIDIA GeForce GTX 1080 Ti ® 图形处理单元上使用Tensorflow 框架训练所有的网络模型.2×21×11×1表2和表3分别给出了用于复杂TCGA WS-Is 病理图像分割的CNN2和CNN3体系结构, 包括连续的卷积—池化层对以及若干个全连接层. 最后一层是Softmax 层, 旨在基于学习到的特征预测输入图像块属于每一类的概率. Xing 等[24]采取两个卷积层和两个全连接层, 而Kumar 等[25]则采取三个卷积层和两个全连接层, 因为加入更多的层并不会显著提高网络的分割精确度, 反而会增加计算时间. 为了获得最好的分割性能, 经验设置其他的超参数值, 包括卷积层中的滤波器尺寸和数量、隐层节点数目、以及输入输出尺寸等. 图3给出了用于复杂TCGA WSIs 病理图像分割的U-Net 体系结构[27]. 该体系结构由编码器和解码器组成. 编码器包含由修正线性单元(Rectified linear unit,ReLU)实现的填充卷积操作, 共两层. 每两个卷积层之后, 有一个步长为2的最大池化操作. 每次最大池化层下采样之后, 特征通道数加倍. 在解码器中, 每两个卷积层之前, 有一个 的上采样操作,且其输出与来自相应编码器部分的特征相结合. 最后两层分别是 卷积操作和像素级Softmax 输出, 其中, 卷积层用于将特征图的通道数降至所需的类别数. 在本文的U-Net 网络实现中, 代替数据扩充, 只是随机提取了图像块, 不过仍然实现了令人满意的分割性能. 本文使用Tensorflow 深度学习框架在TCGA WSIs 病理数据集的所有样本上对CNN2、CNN3和U-Net 网络均训练了95次(Epochs). 针对每个网络, 分别从12幅训练图像和3幅验证图像中提取了158 400个图像块和32 000个图像块用于训练和验证, 其中包括相等数目的以细胞核像素为中心的正样本块和以非细胞核像素为中心的负样本块. 另外, 基于TCGA WSIs 病理数据集, 比较实验分析了标记控制的分水岭分割方法[10].图8和图9显示了在5个器官和疾病状态下,病理细胞核图像的分割算法对比. 图8和图9中第(a) ~ (g)列分别是原始图像、人工分割结果、CscDTE 模型分割结果、U-Net 网络分割结果、CNN3网络分割结果、CNN2网络分割结果和标记控制的分水岭分割结果. 需要注意的是, 考虑到不同类型病理图像颜色的异质性, 在分割模型训练之前, 将原始图像从RGB 颜色空间转换到CIE LUV 均匀颜色空间并作线性归一化. 可以看出, 所提出CscDTE 模型能有效应对细胞核大小、形状和方向的变化, 并最大程度地检测正确细胞核的数目. 另外, 针对存在染色质稀疏、重叠和复杂背景杂斑的情形, 例如,部分前列腺病理图像和膀胱病理图像, CscDTE 模型也表现出了良好的鲁棒性(见图10). 相比之下,虽然U-Net 通过融入上下文信息能较好地避免复杂背景杂斑的干扰, 但由于网络深度的影响, 仍然对染色质稀疏的细胞核内细节不够敏感. CNN2利用各向同性区域生长从网络输出中获取细胞核种子标记, 因而易受细胞核形状的影响, 尤其是带分割目标存在重叠和成团的情况, 产生欠分割的现象.CNN3使用各向异性区域生长代替CNN2中的各向同行区域生长, 虽然增加了对重叠、成团分割的鲁棒性, 但其受限于图像块级的分类. 由于只能提取局部特征, 导致其分割精度相比于CscDTE 模型较低. 作为传统图像分析的方法, 分水岭在分割灰度均匀的孤立细胞核时, 表现得相当优异, 例如图8中的肾脏细胞核分割. 然而, 对于Kumar 病理数据中复杂背景图像, 其分割性能遭受大幅度的下降. 提出的CscDTE 模型在训练和预测时间上也优于基于CNN 和FCN 的体系结构, 训练所有的细胞核仅花费了两个小时左右.表 1 提出的CscDTE 模型的最优参数值. 像素位置样本总数为800 000Table 1 The optimal hyper-parameter values of our CscDTE model. The total number of pixel samples is 800 000数据集N L d 2(R )1st 2nd ∼L th ( layer; layers)M TCGA WSIs200 0005112172212292432112212432 (25), (8), (72), (8), (44); (25), (36), (36)50384自 动 化 学 报47 卷。

国际会议通报691.会议名称: 2009 11th International Conference on Advanced Communication Technology (ICACT)会议时间: 15 Feb - 18 Feb 2009会议地点: Gangwon-Do, Korea (South)会议网址: /重要时间:Abstract Submission Deadline: 10 Oct 2008Final Paper Submission Deadline: 31 Dec 20082.会议名称: 2009 43rd Annual Conference on Information Sciences and Syst ems (CISS)会议时间: 18 Mar - 20 Mar 2009会议地点: Baltimore, MD, USA会议网址: 重要时间: Abstract Submission Deadline: 05 Jan 2009Final Paper Submission Deadline: 27 Feb 20093.会议名称: 2009 10th International Confer ence on Ultimate Integration o n Silicon (ULIS)会议时间: 19 Mar - 20 Mar 2009会议地点: Aachen, Germany会议网址: /重要时间：Abstract Submission Deadline: 23 Jan 2009Final Paper Submission Deadline: 23 Jan 20094.会议名称:2009 IEEE Symposium on Computa tional Intelligence for Financ ial Engineering (CIFEr 2009)会议时间: 30 Mar - 02 Apr 2009会议地点: Nashville, TN, USA会议网址: 重要时间：Abstract Submission Deadline: 31 Oct 2008Final Paper Submission Deadline: 15 Jan 20095 . 会议名称: 2009 IEEE Workshop on Computat ional Intelligence in Virtual Environments (CIVE 2009)会议时间: 30 Mar - 02 Apr 2009会议地点: Nashville, TN, USA会议网址: 重要时间：Abstract Submission Deadline: 31 Oct 2008Final Paper Submission Deadline: 15 Jan 20096.会议名称: 2009 IEEE Workshop on Computat ional Intelligence in Aerospac e Applications (CIAA 2009)会议时间: 30 Mar - 02 Apr 2009会议地点: Nashville, TN, USA会议网址: 重要时间：Abstract Submission Deadline: 31 Oct 2008Final Paper Submission Deadline: 15 Jan 20097 .会议名称: 2009 IEEE Symposium on Computa tional Intelligence in Multi-C riteria Decision-Making (MCDM)会议时间: 30 Mar - 02 Apr 2009会议地点:Nashville, TN, USA会议网址: 重要时间:Abstract Submission Deadline: 31 Oct 2008Final Paper Submission Deadline: 15 Jan 20098.会议名称: 2009 Second International Conf erence on Robot Communication and Coordination (ROBOCOMM) 会议时间:31 Mar - 02 Apr 2009会议地点: Odense, Denmark会议网址: 重要时间：Abstract Submission Deadline: 15 Nov 2008Final Paper Submission Deadline: 15 Feb 20099 . 会议名称: 2009 International Conference on Multimedia Computing and Sy stems (ICMCS)会议时间: 02 Apr - 04 Apr 2009会议地点: Ouarzazate, Morocco会议网址: /重要时间：Abstract Submission Deadline: 09 Nov 2008Final Paper Submission Deadline: 31 Jan 200910 .会议名称: 2009 1st International Confere nce on Sustainable Power Gener ation and Supply (SUPERGEN)会议时间: 06 Apr - 07 Apr 2009会议地点: Nanjing, China会议网址: /UK-China%20Network_conference.html重要时间：Abstract Submission Deadline: 31 Oct 2008Final Paper Submission Deadline: 31 Dec 200811.会议名称: 2009 International Conference on Intelligent Engineering Sys tems (INES)会议时间: 16 Apr - 18 Apr 2009会议地点: Barbados, Barbados会议网址: 重要时间：Abstract Submission Deadline: 01 Nov 2008Final Paper Submission Deadline: 15 Feb 200912.会议名称: 2009 Joint Meeting of the Euro pean Frequency and Time Forum (EFTF) and the IEEE Internatio nal Frequency Control Symposium会议时间:20 Apr - 24 Apr 2009会议地点: Besancon, France会议网址: null重要时间：Abstract Submission Deadline: 15 Dec 2008国际会议预报701.会议名称:2009 IEEE International Advance Computing Conference (IACC 2 009)会议时间: 06 Mar - 07 Mar 2009会议地点: Patiala, India会议网址：重要时间:Abstract Submission Deadline: 30 Dec 2008Final Paper Submission Deadline: 30 Jan 20092.会议名称:2009 International Siberian Conference on Control and Communications (SIBCON 2009)会议地点: Tomsk, Russia会议网址：/tomsk重要时间:Abstract Submission Deadline: 10 Dec 20083.会议名称:2009 IEEE International Reliability Physics Symposium (IRPS)会议时间:26 Apr - 30 Apr 2009会议地点: Montreal, QC, Canada会议网址：/重要时间:Abstract Submission Deadline: 19 Jan 2009Final Paper Submission Deadline: 19 Mar 20094.会议名称:2009 7th International Workshop on Multi-Carrier Systems & Solutions (MC-SS 2009)会议时间:05 May - 06 May 2009会议地点: Herrsching, Germany会议网址：重要时间:Abstract Submission Deadline: 09 Nov 2008Final Paper Submission Deadline: 08 Feb 20095.会议名称:2009 6th International Conference on Electrical Engineering /Electronics, Computer, Telecommunications and Information会议时间:06 May - 09 May 2009会议地点: Chonburi, Thailand会议网址：/home/重要时间:Abstract Submission Deadline: 15 Dec 2008Final Paper Submission Deadline: 01 Mar 20096.会议名称:2009 IEEE Conference on Technologies for Homeland Security ( HST)会议时间:11 May - 12 May 2009会议地点: Waltham, MA, USA会议网址：重要时间:Abstract Submission Deadline: 01 Dec 2008Final Paper Submission Deadline: 01 Mar 20097.会议名称:2009 IEEE International Worksh op Technical Committee on Communications Quality and Reliability (CQR 2009)会议地点: Conference Location: Naples, FL, USA会议网址：/重要时间:Abstract Submission Deadline: 15 Dec 2008Final Paper Submission Deadline: 16 Mar 20098.会议名称:2009 IEEE International Conference on IC Design & Technology (ICICDT)会议时间:18 May - 20 May 2009会议地点: Austin, TX, USA会议网址：/重要时间:Abstract Submission Deadline: 16 Feb 20099.会议名称:2009 International Conference on E-Business and Information System Security (EBISS)会议时间:23 May - 24 May 2009会议地点: Wuhan, China会议网址：/重要时间:Abstract Submission Deadline: 30 Nov 2008Final Paper Submission Deadline: 30 Jan 200910.会议名称:2009 International Conference on Telecommunications (ICT)会议时间:25 May - 27 May 2009会议地点: Marrakech, Morroco会议网址：重要时间:Abstract Submission Deadline: 19 Dec 2008Final Paper Submission Deadline: 13 Mar 200911.会议名称:2009 XII International Symposium on Problems of Redundancy in Information and Control Systems 会议时间:25 May - 30 May 2009会议地点: St. Petersburg, Russia会议网址：/redundancy2009/重要时间:Abstract Submission Deadline: 01 Mar 2009Final Paper Submission Deadline: 16 Apr 200912.会议名称:2009 13th International Workshop on Computational Electronics (IWCE-13)会议时间:27 May - 29 May 2009会议地点: Beijing, China会议网址：/重要时间:Abstract Submission Deadline: 15 Jan 2009Final Paper Submission Deadline: 15 Apr 2009国际会议预报711.会议名称:2009 IEEE 10th W orkshop on Signal Processing Advances in Wireless Communications (SPAWC 2009) 会议时间: 21 Jun - 24 Jun 2009会议地点: Perugia, Italy会议网址：/go/spawc09重要时间:Abstract Submission Deadline: 30 Jan 2009Final Paper Submission Deadline: 10 Apr 20092.会议名称:2009 ACM/IEEE/SCS 23rd Workshop on Principles of Advanced and Distributed Simulation (PADS )会议时间:22 Jun - 25 Jun 2009会议地点: Lake Placid, NY, USA会议网址：/pads2009/重要时间:Final Paper Submission Deadline:January 5, 20093.会议名称:2009 31st International Conference on Information T echnology Interfaces (ITI)会议时间:22 Jun - 25 Jun 2009会议地点: Cavtat/Dubrovnik, Croatia会议网址：http://iti.srce.hr/重要时间:Final Paper Submission Deadline:2009.1.194.会议名称:2009 Robotics: Science & Sy stems (RSS)会议时间:28 Jun - 01 Jul 2009会议地点: Seattle, WA, USA会议网址：/重要时间:Abstract Submission Deadline: 15 Jan 2009Final Paper Submission Deadline: 01 Aug 20095.会议名称:2009 IEEE Pulsed Power Conference (PPC)会议时间:28 Jun - 02 Jul 2009会议地点: Washington, DC, USA会议网址：/ppc2009重要时间:6.会议名称:IFAC Symposium:Identification and Sy stem Parameter Estimation - SYSID'09 (15th) 会议时间:2009.7.6--2009.7.8会议地点: St. Malo,FRANCE会议网址：/重要时间:Deadline to Submit Abstracts: 2009-3-6Deadline to Submit Papers: 2009-4-67.会议名称:IFAC Symposium:Advanced Control of Chemical Processes - ADCHEM会议时间: 2009.7.12--2009.7.15会议地点: Istanbul ,T urkey会议网址：.tr/main.php重要时间:Deadline to Submit Abstracts: 2009-4-12Deadline to Submit Papers: 2009-5-128.会议名称:ICSOFT 2009-4th International Conference on Software and Data T echnologies会议时间:2009.7.26--2008.7.29会议地点: Sofia , Bulgaria会议网址：重要时间:Deadline to Submit Papers: 2009-3-179.会议名称:10th International Conference on Document Analy sis and Recognition会议时间:2009.7.26--2009.7.29会议地点: Barcelona , Spain会议网址：http://www.cvc.uab.es/icdar2009/重要时间:Deadline to Submit Papers: 2009-1-1210.会议名称:第三届国际科学发展研究学会国际会议会议时间:2009.7.24--2009.7-.26会议地点:北京市东城区会议网址：issi2009@(邮箱)重要时间:摘要截稿日期：2008-12-31全文截稿日期：2009-4-1511.会议名称:The 2009 IEEE International Conference on Mechatronics and Automation (ICMA 2009)会议时间:2009.8.9--2009.8.12会议地点:吉林省长春市会议网址：/重要时间:全文截稿日期：2009-3-2012.会议名称:第十三届制造技术国际会议会议时间:2009.9.21--2009-9-23会议地点:辽宁省大连市会议网址：/cmes/ftp/2007xinwen/2008/13jiezhi.html重要时间:全文截稿日期：2009-2-15国际会议预报721.会议名称:2009 10th International Conference on Ultimate Integration on Silicon (ULIS)会议时间:19 Mar - 20 Mar 2009会议地点: Aachen, Germany会议网址：/重要时间:Abstract Submission Deadline:23 Jan 2009Final Paper Submission Deadline: 23 Jan 20092.会议名称:2009 12th International Symposium on Design and Diagnostics of Electronic Circuits & Sy stems (DDECS) 会议时间:15 Apr - 17 Apr 2009会议地点: Liberec, Czech Republic会议网址：http://ddecs2009.tul.cz/index.php重要时间:Abstract Submission Deadline: 20 Jan 2009Final Paper Submission Deadline:14 Mar 20093.会议名称:2009 IFIP International Conference on Wireless and Optical Communications Networks - (WOCN )会议时间:28 Apr - 30 Apr 2009会议地点: Cairo, Egypt会议网址：/重要时间:Abstract Submission Deadline: 05 Feb 2009Final Paper Submission Deadline:15 Mar 20094.会议名称:2009 XII International Symposium on Problems of Redundancy in Information and Control Sy stems会议时间:25 May - 30 May 2009会议地点: St. Petersburg, Russia会议网址：/redundancy2009/重要时间:Abstract Submission Deadline: 01 Mar 2009Final Paper Submission Deadline: 16 Apr 20095.会议名称:2009 IEEE International Conference on Electro/Information T echnology (eit2009)会议时间:07 Jun - 09 Jun 2009会议地点: Windsor, ON, Canada会议网址：/eit2009重要时间:Abstract Submission Deadline: 01 Mar 2009Final Paper Submission Deadline: 01 Apr 20096.会议名称:2009 IEEE International Symposium on Industrial Electronics (ISIE 2009)会议时间:05 Jul - 08 Jul 2009会议地点: Seoul, Korea会议网址：/重要时间:Deadline to Submit Abstracts: 28 Feb 2009Deadline to Submit Papers: 30 Apr 20097.会议名称:2009 7th IEEE/ACM International Conference on Formal Methods and Models for Codesign (MEMO CODE 2009)会议时间: 13 Jul - 15 Jul 2009会议地点: Cambridge, MA, USA会议网址：/重要时间:Deadline to Submit Abstracts: 20 Feb 2009Deadline to Submit Papers: 29 May 20098.会议名称:2009 IEEE International Conference on Automation and Logistics (ICAL)会议时间:05 Aug - 07 Aug 2009会议地点: Sheny ang, China会议网址：重要时间:Abstract Submission Deadline: 01 Mar 2009Final Paper Submission Deadline: 01 Jun 20099.会议名称:2009 IEEE W orkshop on Microele ctronics and Electron Devices (WMED)会议时间:03 Apr - 03 Apr 2009会议地点: Boise, ID, USA会议网址：/r6/boise/wmed2009/WMED2009.html重要时间:Abstract Submission Deadline: 26 Jan 2009Final Paper Submission Deadline: 20 Feb 200910.会议名称:2009 3rd ACM/IEEE International Symposium on Networks-on-Chips (NoCS) 会议时间:10 May - 13 May 2009会议地点: La Jolla, CA, USA会议网址：http://www.nocsy 重要时间:Abstract Submission Deadline: 23 Jan 2009Final Paper Submission Deadline: 06 Apr 200911.会议名称:2009 IEEE International Workshop on Imaging Sy stems and T echniques (IST) 会议时间:11 May - 12 May 2009会议地点: Shenzhen, China会议网址：/重要时间:Abstract Submission Deadline: 15 Jan 2009Final Paper Submission Deadline: 30 Mar 200912.会议名称:2009 IEEE W orkshop on Signal Propagation on Interconnects (SPI)会议时间:2009.9.21--2009-9-23会议地点:Strasbourg, France会议网址：http://spi.univ-brest.fr重要时间:Abstract Submission Deadline: 07 Feb 2009Final Paper Submission Deadline: 07 Feb 2009国际会议预报731.会议名称:2009 16th IEEE-NPSS RealTime Conference (RT 2009)会议时间:10 May - 15 May 2009会议地点: Beijing, China会议网址：/english/conference/rt2009/papers.htm重要时间:Abstract Submission Deadline: 06 Feb 2009Final Paper Submission Deadline: 15 Jun 20092.会议名称:2009 IEEE International Conference on Electro/Information T echnology (eit2009)会议时间:07 Jun - 09 Jun 2009会议地点: Windsor, ON, Canada会议网址：/eit2009重要时间:Abstract Submission Deadline: 01 Mar 2009Final Paper Submission Deadline: 01 Apr 20093.会议名称:2009 IEEE 14th International W orkshop on Computer Aided Modeling and Design of Communicati on Links and Networks (CAMAD)会议时间:12 Jun - 12 Jun 2009会议地点: Pisa, Italy会议网址：http://netgroup.iet.unipi.it/camad2009重要时间:Abstract Submission Deadline: 31 Jan 2009Final Paper Submission Deadline: 31 Jan 20094.会议名称:2009 73rd ARFTG Microwave Measurement Conference会议时间:12 Jun - 12 Jun 2009会议地点:Conference Location: Boston, MA, USA会议网址：重要时间:Abstract Submission Deadline: 13 Feb 2009Final Paper Submission Deadline: 03 Apr 20095.会议名称:2009 Silicon Nanoelectronics Workshop (SNW)会议时间:13 Jun - 14 Jun 2009会议地点:Conference Location: Ky oto, Japan会议网址：http://diana.pe.titech.ac.jp/~snw2009/重要时间:Abstract Submission Deadline: 15 Feb 20096.会议名称:2009 IEEE International Conference on Automation and Logistics (ICAL)会议时间:05 Aug - 07 Aug 2009会议时间: Sheny ang, China会议网址：重要时间:Abstract Submission Deadline: 01 Mar 2009Final Paper Submission Deadline: 01 Jun 20097.会议名称:2009 4th International Conference on Computer Science & Education (ICCSE 2009)会议时间:25 Jul - 28 Jul 2009会议地点: Nanning, China会议网址：重要时间:Abstract Submission Deadline: 20 Mar 2009Final Paper Submission Deadline: 30 May 20098.会议名称:2009 IEEE Symposium on Computational Intelligence for Security and Defense Applications (C ISDA)会议时间:08 Jul - 10 Jul 2009会议地点:Conference Location: Ottawa, ON, Canada会议网址：重要时间:Abstract Submission Deadline: 15 Mar 2009Final Paper Submission Deadline: 15 May 20099.会议名称:2009 International Symposium on Performance Evaluation of Computer & T elecommunication Systems (SPECTS)会议时间:13 Jul - 16 Jul 2009会议地点:Conference Location: Istambul, T urkey会议网址：/SPECTS2009/重要时间:Abstract Submission Deadline: 23 Feb 2009Final Paper Submission Deadline: 22 May 200910.会议名称:2009 Advances in Computational T ools for Engineering Applications (ACTEA) 会议时间:15 Jul - 17 Jul 2009会议地点: Conference Location: Beirut, Lebanon会议网址：.lb/actea09重要时间:Abstract Submission Deadline: 01 Mar 2009Final Paper Submission Deadline: 15 May 200911.会议名称:2009 22nd International V acuum Nanoelectronics Conference (I VNC)会议时间:20 Jul - 24 Jul 2009会议地点: Conference Location: Hamamatsu, Japan会议网址：http://ny7084.rie.shizuoka.a.jp/ivnc2009/重要时间:Abstract Submission Deadline: 15 Mar 2009Final Paper Submission Deadline: 24 Jul 200912.会议名称:2009 International Conference on Mechatronics and Automation (ICMA)会议时间:09 Aug - 12 Aug 2009会议地点: Conference Location: Changchun, China会议网址：重要时间:Abstract Submission Deadline: 20 Mar 2009Final Paper Submission Deadline: 01 Jun 2009国际会议预报741.会议名称:2009 IEEE Symposium on Computational Intelligence for Security and Defense Applications (CISDA) 会议时间: 08 Jul - 10 Jul 2009会议地点: Ottawa, ON, Canada会议网址：Ottawa, ON, Canada重要时间:Abstract Submission Deadline: 15 Mar 2009Final Paper Submission Deadline: 15 May 20092.会议名称:NAECON 2009 - IEEE National Aerospace and Electronics Conference会议时间:21 Jul - 23 Jul 2009会议地点: Dayton, OH, USA会议网址：重要时间:Abstract Submission Deadline: 04 May 2009Final Paper Submission Deadline: 19 Jun 20093.会议名称:2009 4th International Conference on Computer Science & Education (ICCSE 2009)会议时间:25 Jul - 28 Jul 2009会议地点: Nanning, China会议网址：Nanning, China重要时间:Abstract Submission Deadline: 20 Mar 2009Final Paper Submission Deadline: 30 May 20094.会议名称:2009 9th International Conference on Electronic Measurement & Instruments (ICEMI 2009)会议时间:16 Aug - 19 Aug 2009会议地点: Beijing, China会议网址：重要时间:Abstract Submission Deadline: 30 Apr 2009Final Paper Submission Deadline: 15 Jun 20095.会议名称:2009 IEEE International Symposium on the Applications of Ferroelectrics (ISAF)会议时间:23 Aug - 27 Aug 2009会议地点: Xian, China会议网址：重要时间:Abstract Submission Deadline: 31 Mar 2009Final Paper Submission Deadline: 24 Aug 20096.会议名称:2009 European Conference on Circuit Theory and Design (ECCTD 2009)会议时间:23 Aug - 27 Aug 2009会议地点: Antaly a, Turkey会议网址：.tr/重要时间:Abstract Submission Deadline: 30 Mar 2009Final Paper Submission Deadline: 06 Jul 20097.会议名称:2009 1st IEEE Symposium on Web Society (SWS2009)会议时间:23 Aug - 24 Aug 2009会议地点: Lanzhou, China会议网址：/SWS2009重要时间:Abstract Submission Deadline: 10 May 2009Final Paper Submission Deadline: 20 Jun 20098.会议名称:2009 IEEE International Conference on Intelligent Computer Communication and Processing (ICCP)会议时间:27 Aug - 29 Aug 2009会议地点: Cluj-Napoca, Romania会议网址：http://cv.utcluj.ro/iccp2009重要时间:Abstract Submission Deadline: 01 May 2009Final Paper Submission Deadline:01 Jul 20099.会议名称:2009 1st Eastern Regional Conference on the Engineering of Computer Based Sy stems (ECBS-EE RC 2009)会议时间:07 Sep - 08 Sep 2009会议地点: Novi Sad, Serbia会议网址：/index.php重要时间:Abstract Submission Deadline:14 Apr 2009Final Paper Submission Deadline:12 Jun 200910.会议名称:2009 2nd International Symposium on Logisti cs and Industrial Informatics (LINDI 2009)会议时间:10 Sep - 12 Sep 2009会议地点: Linz, Austria会议网址：重要时间:Abstract Submission Deadline: 30 Apr 2009Final Paper Submission Deadline: 30 Jun 200911.会议名称:2009 IEEE Custom Integrated Circuits Conference -CICC 2009会议时间:13 Sep - 16 Sep 2009会议地点: San Jose, CA, USA会议网址：重要时间:Abstract Submission Deadline: 09 Apr 200912.会议名称:2009 Fifth International Conference on Intelligent Computing (ICIC 2009)会议时间:16 Sep - 19 Sep 2009会议地点: Ulsan, Korea (South)会议网址：/2009/index.htm重要时间:Abstract Submission Deadline: 10 Apr 2009Final Paper Submission Deadline: 15 Jun 20091会议名称：2009 Conference on Innovative Technologies in Intelligent Systems and Industrial Applications (CITISIA)会议时间：25 Jul - 26 Jul 2009会议地点: Kuala Lumpur, Malaysia会议网址: 重要时间：Abstract Submission Deadline: 01 Apr 2009Final Paper Submission Deadline: 20 Jun 20092会议名称：2009 IFAC Workshop on Networked Robotics (NetRob 2009)会议时间：06 Oct - 08 Oct 2009会议地点: Golden, CO, USA会议网址：/netrob09重要时间：Abstract Submission Deadline: 01 Apr 2009Final Paper Submission Deadline: 01 Aug 20093会议名称：2009 IEEE International Conference on Control and Automation (ICCA)会议时间：09 Dec - 11 Dec 2009会议地点: Christchurch, New Zealand会议网址：/重要时间：Abstract Submission Deadline: 01 Apr 2009Final Paper Submission Deadline: 01 Sep 20094会议名称：2009 IEEE International Workshop on Machine Learning for Signal Processing (MLSP) (Formerly known as NNSP)会议时间：01 Sep - 04 Sep 2009会议地点: Grenoble, France会议网址：http://mlsp2009.conwiz.dk/重要时间：Abstract Submission Deadline: 03 Apr 2009Final Paper Submission Deadline: 29 May 20095会议名称：ESSCIRC 2009 - 35th European Solid State Circuits Conference会议时间：14 Sep - 18 Sa会议地点: Athens, Greece会议网址：重要时间：Abstract Submission Deadline: 04 Apr 2009Final Paper Submission Deadline: 04 Apr 20096会议名称：ESSDERC 2009 - 39th European Solid State Device Research Conference会议时间：14 Sep - 18 Sep 2009会议地点：Athens, Greece会议网址：重要时间：Abstract Submission Deadline: 04 Apr 2009Final Paper Submission Deadline: 04 Apr 20097会议名称：2009 International Conference on Power Electronics and Drive Systems (PEDS 2009)会议时间：02 Nov - 05 Nov 2009会议地点: Taipei, Taiwan会议网址：.tw重要时间：Abstract Submission Deadline: 10 Apr 2009Final Paper Submission Deadline: 14 Aug 20098会议名称：2009 International Workshop on Local and Non-Local Approximation in Image Processing (LNLA 2009)会议时间：19 Aug - 21 Aug 2009会议地点: Tuusula, Finland会议网址：http://sp.cs.tut.fi/ticsp/lnla09/重要时间：Abstract Submission Deadline: 12 Apr 2009Final Paper Submission Deadline: 05 Jul 20099会议名称：2009 IEEE International Conference on Cluster Computing (CLUSTER)会议时间：31 Aug - 04 Sep 2009会议地点: New Orleans, LA, USA会议网址：/重要时间Abstract Submission Deadline: 14 Apr 2009Final Paper Submission Deadline: 31 Jul 200910会议名称2009 International Conference on Cyberworlds (CW)会议时间：07 Sep - 11 Sep 2009会议地点: Bradford, United Kingdom会议网址：/cw09/重要时间：Abstract Submission Deadline: 15 Apr 2009Final Paper Submission Deadline: 30 Jun 200911会议名称：2009 3rd International Conference on Anti-counterfeiting, Security, and Identification in Communication (2009 ASID)会议时间：20 Aug - 22 Aug 2009会议地点: Hong Kong, China会议网址：.hk/asid2009/重要时间：Abstract Submission Deadline: 15 Apr 2009Final Paper Submission Deadline: 20 Jun 200912会议名称：2009 6th International Symposium on Image and Signal Processing and Analysis (ISPA 2009)会议时间：16 Sep - 18 Sep 2009会议地点: Salzburg, Austria会议网址：重要时间：Abstract Submission Deadline: 15 Apr 2009Final Paper Submission Deadline: 15 Jun 200913会议名称：2009 IEEE Symposium on Security and Privacy (SP)会议时间：17 May - 20 May 2009会议地点: Oakland, CA, USA会议网址：/重要时间：Abstract Submission Deadline: 15 Apr 2009Final Paper Submission Deadline: 15 May 200914会议名称：2009 IEEE 11th International Workshop on Multimedia Signal Processing (MMSP)会议时间：05 Oct - 07 Oct 2009会议地点: Rio de Janeiro, Brazil会议网址：/en-us/um/redmond/events/mmsp09/重要时间：Abstract Submission Deadline: 17 Apr 2009Final Paper Submission Deadline: 06 Jul 200915会议名称：2009 14th International OFDM Workshop (InOWo)会议时间：02 Sep - 03 Sep 2009会议地点: Hamburg, Germany会议网址：http://www.ofdm.tu-harburg.de/重要时间：Abstract Submission Deadline: 17 Apr 2009Final Paper Submission Deadline: 19 Jul 200916会议名称：2009 IEEE Magnetic Recording Conference - TMRC 2009会议时间：05 Oct - 07 Oct 2009会议地点: Tuscaloosa, AL, USA会议网址：/tmrc2009/重要时间：Abstract Submission Deadline: 17 Apr 2009Final Paper Submission Deadline: 30 Oct 200917会议名称：2009 IEEE/SP 15th Workshop on Statistical Signal Processing (SSP)会议时间：31 Aug - 03 Sep 2009会议地点: Cardiff, United Kingdom会议网址：/重要时间：Abstract Submission Deadline: 27 Apr 2009Final Paper Submission Deadline: 12 Jul 200918会议名称：2009 4th International Conference for Internet Technology and Secured Transactions (ICITST )会议时间：09 Nov - 12 Nov 2009会议地点: London, United Kingdom会议网址：/重要时间：Abstract Submission Deadline: 30 Apr 2009Final Paper Submission Deadline: 17 Jul 200919会议名称：2009 IEEE International SOI Conference会议时间：05 Oct - 08 Oct 2009会议地点: Foster City, CA, USA会议网址：/重要时间：Abstract Submission Deadline: 01 May 2009Final Paper Submission Deadline: 28 Sep 200920会议名称：2009 IEEE Nuclear Science Symposium and Medical Imaging Conference (2009 NSS/MIC)会议时间：24 Oct - 01 Nov 2009会议地点: Orlando, FL, USA会议网址：/重要时间：Abstract Submission Deadline: 09 May 200921会议名称：2009 Fourth International Conference on Bio-Inspired Computing: Theories and Applications (BIC-TA 2009)会议时间：16 Oct - 19 Oct 2009会议地点: Beijing, China会议网址：重要时间：Abstract Submission Deadline: 10 May 2009Final Paper Submission Deadline: 30 Jul 200922会议名称：2009 International Multiconference on Computer Science and Information Technology (IMCSIT)会议时间：12 Oct - 14 Oct 2009会议地点: Mragowo, Poland会议网址：重要时间：Abstract Submission Deadline: 10 May 2009Final Paper Submission Deadline: 15 Aug 200923会议名称：2009 International Conference on Web Information Systems and Mining (WISM)会议时间：07 Nov - 08 Nov 2009会议地点: Shanghai, China会议网址：/重要时间：Abstract Submission Deadline: 10 May 2009Final Paper Submission Deadline: 20 Jul 200924会议名称：2009 International Conference on Artificial Intelligence and Computational Intelligence (AICI) 会议时间：07 Nov - 08 Nov 2009会议地点: Shanghai, China会议网址：/重要时间：Abstract Submission Deadline: 10 May 2009Final Paper Submission Deadline: 20 Jul 200925会议名称：2009 9th International Conference on Numerical Simulation of Optoelectronic Devices (NUSOD) 会议时间：31 Aug - 04 Sep 2009会议地点: Gwangju, Korea (South)会议网址：/2009/重要时间：Abstract Submission Deadline: 11 May 200926会议名称：2009 International Symposium on Optomechatronic Technologies (ISOT 2009)会议时间：21 Sep - 23 Sep 2009会议地点: Istanbul, Turkey会议网址：重要时间：Abstract Submission Deadline: 15 May 2009Final Paper Submission Deadline: 15 Jul 200927会议名称：2009 IEEE/CPMT TC-7 Workshop on Accelerated Stress Testing & Reliability (ASTR)会议时间：07 Oct - 09 Oct 2009会议地点: Jersey City, NJ, USA会议网址：/soc/cpmt/tc7/ast2009/重要时间：Abstract Submission Deadline: 15 May 2009Final Paper Submission Deadline: 13 Jun 200928会议名称：2009 IEEE International Conference on Technologies for Practical Robot Applications (TePRA ) 会议时间：09 Nov - 10 Nov 2009会议地点: Woburn, MA, USA会议网址：重要时间：Abstract Submission Deadline: 15 May 2009Final Paper Submission Deadline: 01 Sep 20091会议名称：2009 IEEE Avionics, Fiber- Optics and Photonics Technology Conference (A VFOP)会议时间：22 Sep - 24 Sep 2009会议地点：San Antonio, TX, USA会议网址：重要时间：Abstract Submission Deadline: 20 May 20092会议名称：2009 Eighth International Symposium on Natural Language Processing (SNLP 2009)会议时间：20 Oct - 22 Oct 2009会议地点：Bangkok, Thailand会议网址：http://snlp2009.dpu.ac.th重要时间：Abstract Submission Deadline: 20 May 2009Final Paper Submission Deadline: 30 Jul 20093会议名称：2009 First IEEE International Workshop on Information Forensics and Security (WIFS)会议时间：07 Dec - 09 Dec 2009会议地点：London, United Kingdom会议网址：重要时间：Abstract Submission Deadline: 21 May 2009Final Paper Submission Deadline: 18 Sep 20094会议名称：2009 International Conference on Electrical and Electronics Engineering (ELECO)会议时间：05 Nov - 08 Nov 2009会议地点：Bursa, Turkey会议网址：.tr/重要时间：Abstract Submission Deadline: 29 May 2009Final Paper Submission Deadline: 02 Oct 20095会议名称：2009 Loughborough Antennas & Propagation Conference (LAPC)会议时间：16 Nov - 17 Nov 2009会议地点：Loughborough, United Kingdom会议网址：重要时间：Abstract Submission Deadline: 29 May 2009Final Paper Submission Deadline: 29 May 20096会议名称：2009 International Workshop Terahertz and Mid Infrared Radiation: Basic Research and Practical Applications (TERA-MIR 20)会议时间：03 Nov - 06 Nov 2009会议地点：Marmaris, Mugla, Turkey会议网址：/TERA-MIR2009重要时间：Abstract Submission Deadline: 30 May 2009Final Paper Submission Deadline: 15 Sep 20097会议名称：2009 International Conference on Power Systems (ICPS)会议时间：27 Dec - 29 Dec 2009会议地点：Kharagpur, India会议网址：http://conf05.iitkgp.ac.in/icps09/重要时间：Abstract Submission Deadline: 30 May 2009Final Paper Submission Deadline: 30 Sep 20098会议名称：2009 International Topical Meeting on Microwave Photonics (MWP 2009)会议时间：14 Oct - 16 Oct 2009会议地点：V alencia, Spain会议网址：/重要时间：Abstract Submission Deadline: 31 May 2009Final Paper Submission Deadline: 31 May 20099会议名称：2009 IEEE 8th International Conference on ASIC (ASICON 2009)会议时间：20 Oct - 23 Oct 2009会议地点：Changsha, Hunan, China会议网址：重要时间：Abstract Submission Deadline: 31 May 2009Final Paper Submission Deadline: 30 Jun 200910会议名称：2009 Fourth International Conference on Digital Information Management (ICDIM)会议时间：01 Nov - 04 Nov 2009会议地点：Ann Arbor, MI, USA会议网址：重要时间：Abstract Submission Deadline: 31 May 2009Final Paper Submission Deadline: 31 Jul 200911会议名称：2009 2nd Asian-Pacific Conference on Synthetic Aperture Radar (APSAR)会议时间：26 Oct - 30 Oct 2009会议地点：Xian, Shanxi, China会议网址：重要时间：Abstract Submission Deadline: 01 Jun 200912会议名称：2009 IEEE International Conference on Industrial Engineering and Engineering Management (I EEM) 会议时间：08 Dec - 11 Dec 2009会议地点：Hong Kong, Hong Kong会议网址：重要时间：Abstract Submission Deadline: 01 Jun 2009Final Paper Submission Deadline: 01 Sep 200913会议名称：2009 XXII International Symposium on Information, Communication and Automation Technologies (ICAT)会议时间：29 Oct - 31 Oct 2009会议地点：Sarajevo, Bosnia and Herzegovina会议网址：http://icat.etf.unsa.ba重要时间：Abstract Submission Deadline: 01 Jun 2009Final Paper Submission Deadline: 01 Aug 200914会议名称：2009 IEEE 16th International Conference on Industrial Engineering and Engineering Management。

1+x大数据试题+参考答案一、单选题（共80题，每题1分，共80分）1、关于Sqoop数据的导入导出描述不正确的是？（）A、实现从MySQL到Hive的导入导出B、实现从MySQL到Oracle的导入导出C、实现从HDFS到Oracle的导入导出D、实现从HDFS到MySQL的导入导出正确答案：B2、关于ZooKeeper临时节点的说法正确的是？（）A、创建临时节点的命令为：create -s /tmp myvalueB、临时节点允许有子节点C、一旦会话结束，临时节点将被自动删除D、临时节点不能手动删除正确答案：C3、下列关于调度器的描述不正确的是？（）A、先进先出调度器可以是多队列B、容器调度器其实是多个FIFO队列C、公平调度器不允许管理员为每个队列单独设置调度策略D、先进先出调度器以集群资源独占的方式运行作业正确答案：A4、Hive 适合（）环境A、Hive 适合关系型数据环境B、Hive 适合用于联机(online)事务处理C、适合应用在大量不可变数据的批处理作业D、提供实时查询功能正确答案：C5、下列哪些不是 ZooKeeper 的特点（）A、可靠性B、顺序一致性C、多样系统映像D、原子性正确答案：C6、tar 命令用于对文件进行打包压缩或解压，-t 参数含义（）A、查看压缩包内有哪些文件B、创建压缩文件C、向压缩归档末尾追加文件D、解开压缩文件正确答案：A7、下列哪些不是 HBase 的特点（）A、高可靠性B、高性能C、面向列D、紧密性正确答案：D8、把公钥追加到授权文件的命令是？（）A、ssh-addB、ssh-copy-idC、ssh-keygenD、ssh正确答案：B9、HDFS有一个gzip文件大小75MB，客户端设置Block大小为64MB。

当运行mapreduce任务读取该文件时input split大小为？A、64MBB、75MBC、一个map读取64MB，另外一个map读取11MB正确答案：B10、大数据平台实施方案流程中,建议整个项目过程顺序是（）。

OBCA练习题51. 系统管理员可以根据业务需要创建不同的租户租户具有哪些特性? *A、可以创建自己的用户(正确答案)B、可以创建数据库、表等所有对象(正确答案)C、有独立的information_ schema等系统数据库(正确答案)D、有自己独立的系统变量(正确答案)2. 租户扩容的方法有哪几种? *A、诵过增加系统可用性（如:三副本扩容至五副本）B、通过增大资源池Unit Num(正确答案)C、涌过向集群中增加新的OBServer3. OB支持多种级别的高可用和容灾可以进行如下哪些高可用和容灾部署形式? *A、两地三中心(正确答案)B、同城两机房C、同城三机房(正确答案)D、三地五中心(正确答案)4. 关于OceanBase 的负载均以下说法正确的是? *A、负载均衡i的调度单元是数据库（database）B、负载均衡的调度单元是分区（Partition）(正确答案)C、系统根据一定的策略通过动态调整UNIT的位置和UNIT内副本的位置使得1个Zone(正确答案)D、OceanBase自动完成负载均衡,无法关闭E、负载均衡的调度单元是资源单元（Unit）F、负载均衡的调度单元是租户5. OceanBase租户支持的事务隔离级别包括以下哪些？ *A、读已提交（read-committed）(正确答案)B、可重复读（repeatable-read）(正确答案)C、串行（Serializable）(正确答案)D、不可重复读（non repeatable-read）6. OceanBase数据库支持动态调整租户容量，可以调整单节点的服务能力，也可以调节服务器节点个数。

前者对应... [判断题] *对(正确答案)错7. 分区是OceanBase数据架构的基本单元，是传统数据库的分区表在分布式系统上的实现 [判断题] *对(正确答案)错8. 以下关于变量描述不正确的是？ [单选题] *A、用来控制租户全局（global）级别或者会话（session）级别的属性B、大部分动态生效,少部分需要重建连接C、可以通过show variables;查看变量D、修改全局变量之后不需要重新建立会话,在当前会话即可生效(正确答案)9. “major_freeze_duty_ime”设置为“02:00”意味着什么? [单选题] *A、每日凌晨2点,系统自动发起一次内存冻结操作B、每日凌晨2点,系统自动发起一次备份恢复操作C、每日凌晨2点,系统自动发起一次合并操作(正确答案)D、每日凌晨2点系统自动发起一次转储操作10. 下列有关变量设置描述正确的是？ [单选题] *A、设置 Session级别的变量对当前 Session有效，对其他 Session无效(正确答案)B、设置Global级别和Session级别的变量效果是一样的C、设置Global级别的变量对当前Session有效D、设置Session级别的变量，对所有的Session都有效11. 应用通过OBProxy连接到OceanBase集群，比直连主副本所在的OBServer性能更好？ [判断题] *对错(正确答案)12. 关于OceanBase的负载均衡，以下说法正确的是 *A、系统根据一定的策略，通过动态调整UNIT的位置和UNIT内副本的位置，使得一个Zone内所有Server的资源使用率达到均衡的过程(正确答案)B、OceanBase自动完成负载均衡，无法关闭C、负载均衡的调度单元是租户D、负载均衡的调度单元是数据库（database）(正确答案)E、负载均衡的调度单元是资源单元（Unit）F、负载均衡的调度单元是分区（Partition）13. 假如OBServer进程异常终止，会通过server_permanentoffline time参数值来判断后续的处理策略，以下描述正确的有哪些？ *A、当进程异常终止持续时间<server_permanent_offline_time,此时已缺失部分副本，虽然依然满足多数派，可以保证RPO=0,但存在一定的风险(正确答案)B、当进程异常终止持续时间>server_permanent_ofline_time,会将机器做"临时下线"处理，从其它zone的主副本中，将缺失的数据复制到本zone内剩余的机器上（需要有足够的资源），以维持副本个数(正确答案)C、当进程异常终止持续时间>server_permanent_offline_time,异常终止的observer进程恢复后会自动加入集群，如果已经做过"临时下线"处理，需要从本zone内其它机器上（或者其它zone内）将unit迁移过来D、当进程异常终止持续时间< server_permanent_offline_time,OceanBase暂时不做补副本的处理，以避免频繁的数据迁移14. 普通租户只能设置自己租户的参数，系统租户可以查看和设置所有租户的参数（包括系统租户和普通租户）。

扇形订正分区算法英文English:The Fan-in-Fan-out Partitioning (FFP) algorithm is a widely used technique for partitioning data in distributed databases. It is based on the concept of dividing the data into multiple partitions, where each partition has a fan-in (number of nodes that send data to it) and a fan-out (number of nodes that receive data from it). The algorithm aims to balance the workload across different partitions by considering both the fan-in and fan-out values. By doing so, it helps to minimize the communication cost and improve the parallelism in the distributed system. The FFP algorithm also takes into account the data skewness and the potential hotspots in the data distribution, so that it can make intelligent decisions on how to partition the data in a way that maximizes the overall performance of the system. This makes it a robust and efficient algorithm for partitioning data in distributed databases.中文翻译:扇形订正分区算法（FFP）是分布式数据库中广泛使用的分区数据的技术。

A Distributed Algorithm for Constructing a Generalization of de Bruijn GraphsNikhil Swamy∗,Nikolaos Frangiadakis∗,Konstantinos Bitsakos∗{nswamy,ntg,kbits}@∗Department of Computer ScienceUniversity of Maryland,College Park,MD20742AbstractDe Bruijn graphs possess many characteristics that make them a suitable choice for the topology of an overlay network.These include constant degree at each node, logarithmic diameter and a highly-regular topology that permits nodes to make strong assumptions about the global structure of the network.We propose a distributed protocol that constructs an approximation of a de Bruijn graph in the presence of an arbitrary number of nodes.We show that the degree of each node is constant and that the diameter of the network is no worse than2logN,where N is the number of nodes.The cost of the join and the departure procedures are O(logN) in the worst case.To the best of our knowledge,this is the first distributed protocol that provides such deterministic guarantees.I.IntroductionDe Bruijn graphs are a class of directed graphs that have been proposed as a near-optimal topology for a DHT[5]. The reasons for this include constant degree at each node of the graph which indicates low control overhead per node;a deep structure that allows each node to make strong assumptions about the behavior of other nodes;and a large bisection width when compared to other constant degree graphs.There have been attempts to construct peer-to-peer overlay networks according to a de Bruijn topology ([4],[3]),but these proposals provide only high probability guarantees of performance.Our principal contribution is a distributed protocol to construct de Bruijn-like graphs. Our protocol comes with the following deterministic guar-antees:(1)the number of neighbors for each node in the network is no more than a constant;and(2)the diameter of the network is logarithmic in the number of nodes.Pure de Bruijn graphs are defined over nodes that num-ber d k for some integers d and k.Each node in such graphs is assigned a unique identifier from the set of possible k-words from an alphabet of size d(typically,a binary alphabet is used;i.e d=2.)The connectivity of a de Bruijn graph is determined by the identifier assigned to each node. Consider a node n with identifier b1b2...b k,b i∈{0,1}. n has an out-edge to the nodes with identifier b2...b k0 and b2...b k1.This adjacency scheme,based on shifting the identifier strings associated with a node yields a simple prefix based routing policy.The result is a a log(N)bound on the diameter of the graph.By construction,the degree of each node is constant.The requirement that the number of nodes is precisely 2k has made it difficult to use de Bruijn graphs in a practical setting.Our protocol,H ALO,provides a gener-alization of the de Bruijn graph to the case where the number of nodes is not a power of two.We achieve this by partitioning the whole graph into regions that locally exhibit precise de Bruijn connectivity.The boundaries of these regions are populated by nodes that emulate the behavior of more than one node.This enables us to“glue together”each of the regions that together constitute the entire graph.The graph constructed retains the degree and diameter bounds as well as the routing scheme of de Bruijn graphs in the presence of an arbitrary number of nodes.The paper is organized as follows.In Section II we present a high-level summary of our protocol,H ALO. In Section III we describe the connectivity structure of the network and show how packets are routed through it.Section IV describes the procedure by which new nodes enter the network.Techniques for maintaining im-portant network invariants are described in Section V.The preservation of these invariants suggests a procedure for permitting nodes to leave the network.This is described in Section VI.In Section VII we state and prove the theorems that provide deterministic guarantees on the behavior of the network.We conclude with a discussion of related work.II.OverviewOur approach takes the view of the overlay network as a distributed hash table.We consider the space of hash-keys to be all binary strings of length exactly k.Each node in the network is assigned one or more labels from this space.The scheme for assigning labels to nodes maintains the invariant that the labels of all the nodes in the network forms an universal prefix set;that is,for every k-length binary string s there exists a unique node n such that a label associated with n shares a common prefix with s. We say that the label associated with n covers the string s.This invariant suggests a simple prefix-based scheme for routing packets across the network.We use n and subscripted/superscripted varieties to denote network nodes.We use N to refer to the set of all nodes,or the size of that set depending on the context. The set of labels of a node n is denoted lab(n).Each label is a binary string s of length k.A node n is addressed by the prefix of each label in lab(n).That is,a node can have more than one address.Each node n is assigned a level,such that level(n)≤k,that specifies the length of the prefix used to address n.For instance,given a node nwith level(n)=ℓand lab(n)={b1b2...b k,b′1b′2...b′k }for some binary digits b i and b′i,then n is addressed by thestrings{b1...bℓ,b′1...b′ℓ}.We write b1b2...bℓ·∗to referto the set of all binary strings that begin with b1b2...bℓ. Since the set of node labels forms a universal prefix set, we use write b1b2...bℓ·∗to refer to a label associated with a particular node as well as the set of labels in the hash-space covered by the label.If the number of nodes in the network is2ℓthen it is straightforward to construct a pure de Bruijn graph by ensuring that the level of all nodes in the network isℓ.To handle the more general setting of an arbitrary number of nodes we allow the level of nodes in network to vary.We attempt to maintain the invariant that nodes at a similar level remain adjacent to each other.For instance,given nodes n1,n2and n3at levelsℓ,ℓ+1andℓ+2respectively, we may permit n1and n2to be adjacent and n2and n3to be adjacent,but n1and n3may not be adjacent. Nodes at the same level can also be adjacent.This pattern of connectivity permits the network to be structured into regions of nodes that are of similar level.The local view of the network to a node at levelℓis as if it were a de Bruijn graph of levelℓ.Piecing together different regions of the network that are locally de Bruijn connected requires some care.To achieve this,certain nodes in the network have more than one label.By doing so,these nodes emulate the behavior of as many nodes as they have labels.For instance,a node might have labels s1=b1...bℓ0·∗and s2=b1...bℓ1·∗and emulates the behavior of two nodes at levelℓ+1that would have labels s1and s2.Note however that in this case s1and s2share a common prefix of lengthℓ.Together s1 and s2cover a set of hash-identifiers that is identical to that covered by the common prefix of s1and s2.We use this insight to place nodes that emulate the behavior of more than one node on the boundary between regions of the network that are at levels that differ by one.When a request to join the network is received at a node it is typically forwarded to the nearest node that is emulat-ing the behavior of more than one node.Since emulation of a node’s behavior is costly,this makes intuitive sense in that the nodes with the heaviest burden are permitted to reduce their load by sharing it with the joining node.It also has the effect of distributing the introduction of new nodes in the network and ensuring that the difference in levels across the entire network is kept small.Forwarding join requests in this manner requires that a node in the network keep track of the state of its neighbors.In the next section,we define precisely the state of a node and the structure of connectivity in the network.III.States and AdjacenciesThe state of a node n in the H ALO network is a pair S(n)=(ST,l)and is denoted ST l where l is the level of the node v.The state identifier ST is taken from the set{IN,EM,AT}.The state of a node is a function of both its own internal state as well as the state of its immediate neighbors in the network.The states(and their relation to node identifiers)are enumerated below.1)IN0A node that wishes to join the H ALO networkis initially at level0.It issues a join request to abootstrap node.2)EM l A node n in this state emulates the behaviorof two nodes.Specifically,lab(n)={b1...bℓ−10·∗,b1...bℓ−11·∗}.Note that the length of both labelsin lab(n)isℓand both labels share a common prefixof lengthℓ−13)AT l A node n the state AT l is said to be atomic—it has only a single b(n)={b1...bℓ·∗}.The state of a node n is in part determined by the state of nodes n i that are adjacent to n.The adjacencies themselves are defined purely in terms of the identifiers of a node.We define two types of adjacencies that are maintained at n—SUCC(n)and SIB(n).SUCC(n)≡{n′∈N| b2...bℓ0·∗∈lab(n′)b2...bℓ1·∗∈lab(n′)} where b1...bℓ·∗∈lab(n)SUCC(n)are the normal de Bruijn successors of a node n at levelℓ.These are the edges that are used to route packets in the network using a prefix-based routing procedure.For instance,the path taken in the network from a node withlabel b 1...b k to a node with label b ′1...b ′k is through the nodes with the labels below 1:b 2...b k b ′1,b 3...b k b ′1b ′2,...,b k b ′1...b ′k −1The other type of edges maintained at a node are usedto handle node failures.The structure of the connectivity of “sibling”edges is given below.SIB (n )≡{n ′∈N |b 1...¯bl 0·∗∈lab (n ′)}where¯0≡1¯1≡0lab (n )={s }⇒s =b 1...b l ·∗lab (n )={s 1,s 2}⇒s 1=b 1...b l 0·∗s 2=b 1...b l 1·∗The manner in which SIB (n )is used to handle node failures will be presented in Section VI.It is worth noting that the SIB ()relation is not necessarily symmetric.If n is not at the same level as SIB (n )then SIB (SIB (n ))=n .In determining the state of a node we often consider the entire neighborhood of the node.We use NBRS (n )to refer to the set of nodes that n refers to,as well as nodes that refer to n using both SUCC (n )and SIB (n )edges.IV .The Join ProcedureWe make use of join redirections to ensure than a new node joins at an “appropriate”part of the graph.Typically the redirection is limited to a radius of two hops from the site of the original join request,but in the worst case this might require upto log N hops.A node n IN that wishes to join the network uses an out-of-band method to contact an arbitrary node n in the network.Initially,S (n IN )=IN 0.The node n that receives the request may chose to satisfy the request itself,or it may forward to join request to some other node in its neighborhood.The rules that determine the manner in which a join request is forwarded are presented in Table I.Here S t (n )represents the state of the node that receives the join request at time t 2;lab t (n )represents its labels at that time.If the condition in the third column is satisfied for some node in the neighborhood of n then the join is forwarded to that node and the state of n remains unchanged.In case the join is not forwarded,the node n computes a fresh pair of identifiers and adjacencies for itself and for n IN .At the next time step,the node n1Itis possible to optimize the routing scheme to take advantage of similarities between the labels of the source and destination nodes.We exclude this to keep the presentation simple.2For the purpose of describing our protocol an informal treatment of time is sufficient.We adopt a discrete approach,where a single time unit passes when a node receives or sends a control message.With this definition time is a local (i.e.node-specific)property i.e.,each node keeps track of its own time.then enters into state S t +1(u )and presents n IN with its identifier,adjacencies,and state S t +1(n IN ).It is straightforward for n to compute the new identifiers and adjacencies for itself and n IN .If S t (n )=EM ℓthen n already emulates the behavior of two nodes;in this case n simply hands over half of its state to the new node.If S t (n )=AT l and lab t (n )={b 1b 2...b l ·∗}then n gives itself the new identifier b 1b 2...b ℓ0·∗and gives n IN b 1b 2...b l 1·∗thereby splitting the space of hash identifiers exactly in half.We show in Section VII that the resulting SUCC (·)sets for both n and n IN is contained in the original SUCC (n ).After the join SIB (n )=n IN and SIB (n IN )=n .V .State ConsistencyTo be able to guarantee logarithmic diameter with constant degree at each node we require certain state invariants to be maintained.These invariants are listed below.(A1)If an edge (n 1,n 2)is in the network then|level (n 1)−level (n 2)|≤1.(A2)An EM ℓnode has at least one neighbor n such thatS (n )∈{AT ℓ,EM ℓ+1}.The reasons for the exact choice of these invariants will become evident in Section VII.Intuitively,(A1)maintains the property that the local view of the network to any particular node is de Bruijn like by ensuring that only nodes of a similar level are adjacent.Invariant (A2)ensures that nodes do not unnecessarily emulate the behavior of more than one node.To enforce these invariants,we require a node n to no-tify all its neighbors each time its state changes.Consider the case where a node n ′receives a notification from a node n of a change in the state of n .The node n ′responds to this notification in two steps.First,in an attempt to maintain invariant (A1),the state of n ′may change due to the change in n ’s state alone.Next,to maintain (A2)n ′may examine the state of all its neighbors and,if necessary,change its state accordingly.If n ′state changes it issues a notification to all its neighbors.We show that this chain of state change notifications does not extend beyond a radius of two hops from the node that started the notification.The rule below indicates the action taken at node n ′if it receives a notification from node n .(R1)S t (n )=AT ℓ∧S t (n ′)=AT l −1∧lab t (n ′)={b 1...b ℓ−1·∗})⇒S t +1(n )=AT ℓ∧(S t +1(n ′)=EM ℓ∧lab t +1(n ′)={b 1...b l −10·∗,b 1...b l −11·∗})For all other combinations of states of n and n ′no action is taken at n ′.This rule handles the following situation.At time t −1,nodes n and n ′are at the same level ℓ−1.At time t the level of n increases,due to say the arrivalFwd if∃n′∈NBRS(n)s.t ElseS t(n)lab t(n)S t+1(n)lab t+1(n)S t+1(n IN)lab t+1(n IN) ATℓb1...bℓ·∗S(n′)=EMℓAT l+1b1...bℓ0·∗AT l+1b1...bℓ1·∗EMℓb1...bℓ·∗b1...¯bℓ·∗S(n′)=EMℓ−1AT l b1...bℓ·∗AT l b1...¯bℓ·∗TABLE I.The Join Procedureof a new node in the proximity of n.The change in level causes the region of adjacent nodes at levelℓ−1to be split.At this point,the node n′responds by emulating two nodes so as to“glue”the two regions together.In order to satisfy the invariant(A2)we require that a node n periodically examine the state of all its neighbors and apply the rule below.As previously,if the state of n changes as a result of this rule,n notifies its neighbors of the change.(R2)S t(n)=EMℓ∧lab t(n)={b1...bℓ·∗,b1...¯bℓ·∗}∀n′∈NBRS(n).S t(n′)∈{EMℓ,ATℓ−1}⇒S t+1(n)=ATℓ−1lab t+1(n)={b1...bℓ−1·∗}In Section VII we show that this procedure for main-taining state consistency prevents the network from ever entering an erroneous state,and is sufficient to guarantee the two invariants stated at the start of this section.−→EM l−1EM l EM l+1AT l−1AT l AT l+1AT l X R S X S XEM l R S S S S XTABLE II.The valid states at the two nodes ofan edge in the network.The result of this state maintenance procedures,namely the permitted states of interconnected nodes,are sum-marized in Table II.For a directed edge(n1,n2)in the network,the table shows the possible states of n1and n2. The state of n1,the starting point of the edge,appears in the left-most column.The state of n2appears in the top row.A table entry“X”indicates that such an edge is not permitted in the network;an“R”indicates that(n1,n2) can only be a successor or“routing”edge;an“S”indicates that(n1,n2)may be either a successor or a sibling edge. VI.The Departure ProcedureWhen a node n wishes to leave the network we must find another node n1that can take its place.If such a node n1is identified we are faced with the obvious problem of finding,in turn,a node to take the place of n1,since it will fulfill the role of the departed node.The task of the departure protocol then,is to identify a node n1that has a sibling n2such that n2can take over the hash-space assigned to n1thus freeing n1to take over the hash-space of n,the departing node.The inductive nature of this problem is captured by the recursive rules that define the node departure algorithm in Table III.The presentation of this algorithm assumes that the node n departs from the network gracefully.In the event of a catastrophic failure the sibling of n detects the failure and executes the departure procedure on behalf of n.The correctness of this protocol depends on the follow-ing partial order defined over the states of nodes.EMℓ<ATℓ<EMℓ+1In(case1a)of Table III the search for the node has arrived at a node n1in state ATℓwhich has a sibling n2 which is also in state ATℓ.n1⊓n2is the node that covers the label obtained by computing the maximum common prefix of lab(n1)and lab(n2).This operation is well defined since both nodes are in state ATℓand thus have only a single identifier each.Node n3represents the sibling of the node thus computed.If it can be ensured that n3is at the same level as n1and n2,then we can cause n2to emulate the behavior of both n1and n2without introducing any pointers that violate the invariants of Section V.If n3 happens to be at a deeper level,thus exceeding n1in the partial order,we forward the search procedure to n3.In cases1b,2a,and2b n2already exceeds n1in the partial order.In each of these cases we immediately forward the search to node n2.Finally,in case2c,even though the sibling of n1 precedes n1in the partial order,we are guaranteed by invariant(A2)of Section V that a node n3must exist in the neighborhood of n1that succeeds it in the partial order. We forward the search to any such node.Note that in each case the search is forwarded to a node that is further along in the partial order.This guarantees the termination of this process.VII.Properties of H ALOAn important property of the H ALO network is illus-trated in Figure1.Thisfigure is a schematic illustration of the H ALO graph–hence the name.The graph is partitioned such that all edges in the graph are onlyS (n 1)S (n 2=SIB (n 1))ActionAT ℓAT ℓ(case 1a)let n 3=SIB (n 1⊓n 2)if level (n 3)≤ℓthenid (n 2):=lab (n 1)∪lab (n 2);S (n 2)=EM ℓfound n 1else forward to n 3(case 1or 2)EM ℓ(case 1b)forward to n 2(case 2)EM ℓEM ℓ+1(case 2a)forward to n 2(case 2)AT ℓ(case 2b)forward to n 2(case 1)EM ℓ(case 2c)AT ℓ−1∃n 3∈NBRS (n 1)|S (n 3)∈{AT ℓ,EM ℓ+1}forward to n 3(case 1or 2)where n 1⊓n 2is a node nwith the lab (n)contains the maximum common prefix of lab (n 1)and lab (n 2).TABLE III.The Departure Procedurebetween nodes of a similar level.The states in the network are maintained such that nodes in the EM ℓstate act as a buffer area between nodes at level ℓand those at levels ℓ−1.The following lemma shows that with sequential joins and departures the difference in levels between the endpoints of an edge is at most 1.Or,that edges in the H ALO graph do not extend across adjacent levels in Figure 1.AT 9AT 9AT 10AT 10EM 10EM 10EM 9Fig.1.A schematic illustration of a H ALO net-work.Nodes of various levels are arranged in “concentric”rings.This figure shows two local regions with AT 10nodes surrounded by EM 10and AT 9nodes.All these regions occur within a region of EM 9nodes.The arrowed line segments indicate edges between nodes that reside in each of the regions.Lemma 7.1(No Steep Edges):If (n 1,n 2)is an edge in the H ALO graph,then either level (n 1)=level (n 2),or S (n 1)=EM ℓand S (n 2)∈{AT ℓ−1,EM l +1,EM l −1}.Proof:The proof is by induction on the number of vertices in the graph.Clearly with a single node in the graph there is no edge that violates the above constraint.Let us assume the property holds for a graph with N nodes.From this state the graph can go to a new state only if a new node joins the network or an existing node leaves it.We examine the two cases separately.Case 1:A node n new joins the networkWhen a node n new joins the graph its request is received by an existing node of the network.The request might beforwarded to other nodes,until it at time t reaches node n ∈N which processes it.1)S t (n )=EM ℓ:If n had a neighbor n ′in state EM ℓ−1the join request would be forwarded to n ′.Thus we are guaranteed that all EM neighbors of u are at a level no less than ℓ.Let lab t (n )={b 1...b ℓ−10·∗,b 1...b ℓ−11·∗}.After the join lab t +1(n )={b 1...b ℓ−10·∗}and lab t +1(n new )={b 1...b l −11·∗}.Since no new ids have been introduced by the join,we trivially have that the set of the successor edges of n before the join is equal to the union of the sets of the successor edges of n and n new after the join.After the join S t +1(n )=S t +1(n new )=AT ℓ.It re-mains to be shown that none of the edges introduced violate the property.We handle each of the cases for nodes n ′adjacent to n and n new using SUCC (·)edges only —i.e {(n ′,n ),(n ′,n new )}⊆SUCC (n ′)or {(n,n ′),(n new ,n ′)}⊆SUCC (n )∪SUCC (n new ).a)S t +1(n ′)=AT ℓ:Since S t +1(n )=S t +1(n new )=S t +1(n ′)the property is satisfied.b)S t +1(n ′)=EM ℓSince the level of n ′is the same as the level of n and n new the property is satisfied.c)S t +1(n ′)=EM ℓ+1The level of n ′is only one greater than the level of n and n new and n ′is in the state EM ;thus the property is satisfied.d)S t +1(n ′)=AT ℓ−1The node n ′receives a noti-fication from either n or n new and,according to rule (R1),transitions to state S t +2′(n ′)=EM ℓthus confining the edge to a single level.2)S t(n )=AT ℓ:If ∃n ′∈NBRS (n )s.t.S (n ′)=EM ℓthen the join request is forwarded to n ′.Thus we need only consider the case when all neighbors of n are either AT ℓor EM ℓ+1.If lab (n )={b 1...b l ·∗}after the join we have lab t +1(n )={b 1...b l 0·∗}and (·∗n new )={b 1...b l 1·∗}.The neighbors of n according to the SUCC (·)relation at time t are nodes with labels inL={b2...b l0·∗,b2...b l1·∗,0b1...b l−1·∗,1b1...b l−1·∗}As in the previous case,after the join,the neighborsof n and n new according to the SUCC(·)relation afterjoin are those with labels belonging to the set Labove.Thus,we need only consider nodes that werein the original neighborhood of n.S t+1(n new)=S t+1(n)=ATℓ+1.All the nodesn′∈NBRS()t+1n∪NBRS()t+1(n new)must haveS(n′)∈{ATℓ,EMℓ+1}.For nodes in state EM l+1theedges to n and n new no longer cross a level boundary.Nodes in state n′such that S t(n′)=ATℓreceivea notification that by rule(R1)causes a transitionto S t+1(EM l+1)which then causes the edge to becontained within a level.In both cases we need to also consider sibling edges.After the join procedure we have SIB()t+1n= SIB()t+1n new and level(n)=level(n new);so the newly introduced sibling edges do not violate the hypothesis.A node n′∈NBRS()t+1n|n=SIB()t+1n′(recall that the SIB(·)relation is not always symmetric)receives a state change notification just as any other node in NBRS()t+1n and will make the necessary state transition using rule(R1).Finally,it is worth noting that the state change notifications are confined to a radius of2from the location of the join.This can be seen by noting that a notification from an EMℓnode causes no state change in the recipient of the message.Case2:A node n d departs the networkWhen a node n d leaves the network,the departure protocol discovers at time t a node n that will take the place of n d in the network.The state of n at time t, S t(n)is always ATℓ,and n has a sibling n′that is also in state ATℓ.On completion of the departure procedure, the state of n′is S t+1(n′)=EMℓ.We consider the newly introduced successor and sibling edges separately.Since n takes the place of n d,it adjacencies at the end of the departure protocol are the same as those of n d prior to the departure.Hence all adjacencies of n after the departure protocol is complete are legal.After the departure is complete,n′takes on all adjacen-cies of n that were present prior to the departure of n d.The set of non-sibling adjacencies of n′after the departure are the non-sibling edges in NBRS()t(n)∪NBRS()t(n′).Since the level of n′did not change no new edge violates the property.For sibling edges,the new sibling of n′,n′′= SIB()t+1(n′)is precisely the node computed by SIB(()u v),and its level is is checked to ensure that it is no greater thanℓ.level(n′′)can in fact be no less than ℓ−1,since otherwise lab n′′would contain a label that with a prefix of lengthℓ−1that was also a prefix of a label in lab(n′).Corollary7.2(Degree Bound):The degree of a node is,in the worst case,8.Proof:Clearly,nodes n in state EMℓare the only nodes with degree greater than4.We proceed by induction on the number of nodes.If the node n makes the state transition EXTℓ−1→EMℓ,then there must have been a join of the node n new at n′∈NBRS(n).After the join n is at worst adjacent to both n′and n new,thus at most increasing its degree to5.If,however,n is already in the state EMℓand a join occurs at n′∈NBRS(n).The node n′must be in state S(n′)=EMℓor EMℓ−1.n′cannot be in state ATℓsince otherwise the join would have been forwarded to n,nor can n′be in state EMℓ+1since once again the join would have been forwarded to n.By the hypothesis,the degree of n is at most8,implying lab(n)={b0...bℓ−10·∗,b0...bℓ−11·∗}.Thus, NBRS(n)={b1...bℓ−100·∗,b1...bℓ−101·∗,b1...bℓ−110·∗,b1...bℓ−111·∗,0b1...bℓ−10·∗,0b1...bℓ−11·∗,1b1...bℓ−10·∗,1b1...bℓ−11·∗}But since n′∈NBRS(()n)and S(n′)=EMℓthen id(n′) is a prefix cover of at least2elements of NBRS(()n).Thus the degree of n can be no more than7.After the join n can at worst become adjacent to both n′and n new,further increasing its degree only by1,to8.In other words,in the worst case,a node emulates no more than two nodes.Lemma7.3(Level Inequality):Letℓmin andℓmax de-note the lowest and highest level of a node in the graph.ℓmin−1≤logN≤ℓmax,where N is the number of nodes.Proof:Wefirst note that theℓmin≤logN.This can be observed as follows:Letλdenote the maximum length of a identifier.Since the set of nodes in the H ALO graph form a universal prefix set we require that the entire space of identifiers2λbe covered by the identifiers of all the nodes in the graph.A node at levelℓcovers2λ−l elements of the identifier space.Therefore,a conservative upper bound3on the proportion of the space covered by a single node is2λ−ℓmin+1.Thus we require N·2λ−ℓmin+1=2λto satisfy the universal prefix property. Or,ℓmin≤logN+1.To boundℓmax,we note that2λ−ℓmax is a lower bound on the number of identifiers covered by a node.Since there is no redundancy in the universal prefix set,we require N·2λ−ℓmax≤2λ.Thus logN≤ℓmax.This argument also shows thatℓmax=logN impliesℓmax=l min.3Nodes in state EMℓcover q2·2λ−l identifiersLemma 7.4(Tree Edges):The out-degree of all but two internal nodes in the shortest path tree 4is at least 2.Proof:Let the root of the shortest path tree be n r and r 1...r ℓ1·∗∈lab (n r ).Consider a node n with b 1...b ℓ2·∗∈lab (n ).First of all,there can be no path from r to n of length less than |ℓ1−ℓ2|.This follows directly from the No Steep Edge lemma.Without loss of generality,assume the successors of n are n 1and n 2with labels that cover b 2...b ℓ20·∗and b 2...b ℓ21·∗,respectively.The node n 1need not be at the same level as n 2but by the No Steep Edges lemma,and since both n 1and n 2are adjacent to n ,the levels of n 1and n 2may differ by at most 2.We will demonstrate that either both edges {(n,n 1),(n,n 2)}are tree edges,or neither edge is a tree edge.We define overlap (s 1,s 2)be the length of the longest prefix of of the string s 1that is also a suffix of the string s 2.For instance,if s 1=111000and s 2=000111,then overlap (s 1,s 2)=3.Let l r ,l,l 1,l 2denote the labels of r ,n ,n 1and n 2respectively.Since l 1and l 2are identical up to bit position ℓ2,and the level of n 1is at most two greater than the length of n 2,i =overlap (l 1,l )and j =overlap (l 2,l )differ by at most 3.The edge (n,n 1)is a tree edge iff b 1=b ℓ1−i 5.Similarly for (n,n 2).Without loss of generality let’s assume that i ≥j .If we want only one edge in the set {(n,n 1),(n,n 2)}to be a tree edge,we require the following:(T1)r l 1−i =r l q −j .This is necessary since we want b 1tomatch only one of these values,and hence contribute only a single edge to the tree.(T2)overlap (l 2,l r )=ℓ2−1.Since n 1and n 2share thefirst ℓ2−1bits,for condition (T1)to be satisfied at least ℓ2−1bits must be in the overlap for both l 1and l 2with l r .(T3)r ℓ1−j ...r ℓ1to be a prefix of r ℓ1−i ...r ℓ1.This isrequired since the l 1and l 2differ only in bit position ℓ2,therefore the matched suffixes of l r must also be prefixes of each other.This condition also implies that the last i bits of l r are identical.For these conditions to be true simultaneously,the suffix of l r that is i +1bits long must either be 100...or 011....For any value of i ,there is exactly one possible pair of nodes n 1and n 2that satisfy the remainder of the properties.In particular,for some i ,pick i ≥j ≥i −2;then l 2=0j 1and l 1is any one element from L ={0j 0,0j 00,0j 01,0j 000,0j 001,0j 010,0j 011},where 0j represents a string of j zeroes).A similar case exists for l 2=1j 0.This is true by the No Steep Edges lemma which guarantees that nodes two hops from each other can at most4Weonly consider successor edges in the shortest path tree5This statement follows directly from the de Bruijn routing algorithm.For instance,if the label of the root node l r =000111·∗,and the label of n ,l =111000·∗,then for (n,n 1)to be a tree edge,we must have l 1=011100be two levels apart;and by the universal prefix property which disallows l 2to be a prefix of l 1.Furthermore,if there exists more than one node with labels from L adjacent to n then by the above argument it is guaranteed that both those edges will be tree edges.Thus,in the entire graph,there exists only a single pair of nodes that have out-degree of 1in the shortest path tree.All other internal nodes have out-degree 2.Lemma 7.5(Tree Depth):Let r be a node at the deep-est level ℓmax ,with r 1...r ℓmax ·∗∈lab (r ).The maximum depth of the shortest path tree rooted at r is O (logN ),where N is the number of nodes.Proof:First,if ℓmax =logN ,by Lemma 7.3we trivially have that there is only one level,and the H ALO graph is a pure De Bruijn graph.The diameter of a De Bruijn graph is logN and the depth of the shortest path tree is bounded by the diameter.We consider below the case where ℓmax >logN .Consider a node n with b 1...b ℓ·∗∈lab (n )with successors n 1and n 2with labels b 2...b ℓ0·∗and b 2...b ℓ1·∗,respectively.By the Lemma 7.4we have that either (n,n 1)and (n,n 2)are both tree edges,or neither.We refine the conditions under which (n,n 1)and (n,n 2)are tree edges.Once again,let l r ,l,l 1,l 2denote the labels of r,n,n 1,n 2respectively.If the i =overlap (l,l r )≥2then l 2=r 1...b 1b 2...u i ·∗.Thus overlap (l 1,l r )and overlap (l 2,l r )are both precisely i −16Both edges (n,n 1)and (n,n 2)are tree edges since l has a greater overlap with l r ,and b 1matches r ℓmax −i ,the necessary bit position in l r .We also have that the distance from r to u is ℓmax −i .Since logN <ℓmax ,we have all nodes within (logN −1)distance from the root r are internal nodes in the tree.Since the degree of internal nodes in the tree is 2,and with logN −1levels of the tree as internal nodes,the shallowest leaf may only be at distance logN .Since we have at least N 2internal nodes,this bounds the depth of the deepest leaf to be less than logN +3.Lemma 7.6(Level Bound):The number of levels in the H ALO graph is O (logN )in the worst case,where N is number of nodes in the graph.Proof:We have from the Tree Depth lemma that the depth of the shortest path tree rooted at the deepest node is O (logN ).From the No Steep Edges lemma,even if we assume conservatively that every tree edge crosses a level boundary,ℓmax −ℓmin =O (logN ).Theorem 7.7(Diameter Bound):The diameter of the H ALO graph with N nodes is O (logN ).Proof:We trivially have that the diameter of the network is at most ℓmax .This can be observed by recalling the procedure used for routing in the De Bruijn network –it is always6Thereare exactly two nodes in the graph for which this is not true.When r ends with the sequence 101010or 01010,and u,v begin with the same sequence.By an argument identical to that in the Tree Edge lemma these cases are rendered irrelevant.。