Dissertations / Theses on the topic 'Segment trees'

Neste trabalho estudamos problemas relacionados com a busca de pontos e segmentos em janelas retangulares com os lados paralelos aos eixos. É dado um conjunto de segmentos (ou pontos) no plano. Em uma primeira fase estes segmentos são organizados em estruturas de dados de tal forma a tornar buscas por aqueles que estão contidos em janelas retangulares mais eficiente. Na segunda fase são dadas as janelas de maneira online. Várias destas estruturas de dados são baseadas em árvores balanceadas, tais como, árvore limite, árvore de busca com prioridade, árvore de intervalos e árvore de segmentos. Na dissertação mostramos detalhadamente estas estruturas de dados e os algoritmos para resolver este problema para conjuntos de pontos (versão unidimensional do problema) e para segmentos no plano, tanto horizontais e verticais como com qualquer orientação (sem cruzamentos). Os algoritmos são analisados de forma rigorosa quanto ao seu uso de espaço e de tempo. Implementamos também os vários algoritmos estudados, construindo uma biblioteca destas estruturas de dados. Apresentamos, finalmente os resultados de experimentos computacionais com instâncias do problema.
In this work we study problems about point and segment query in rectangular windows whose edges are parallel to the axis. Given a set of segments (or points) in the plane. In a first phase these segments are organized in data structures such that queries for segments in windows are done more efficiently. In the second phase windows are given online. The data structures are balanced trees as range tree, priority search tree, interval tree and segment tree. In this master\'s thesis we show in details data structures and algorithms for solving windowing queries to sets of points (unidimensional version of the problem) and of segments in the plane, as horizontal and vertical as any orientation (without crossings). The algorithms are analysed rigorously regarding their space and time used. We implement the algorithms studied, building a library of these data structures. Finally, we present, the results of computational experiments with instances of the problem.

We describe a data structure and algorithms based on segment trees. They are used to manage different versions of a document and to reconstruct the version which was valid at a given time in the past or to get the most recent version. Difficulties arise because it is not known when a version will be replaced by a newer one. Thus unbounded time intervals are to be handled. The data structure also supports the retrieval of the history of a document.

The accurate automated extraction of arterial and venous (AV) trees in fundus images subserves investigation into the correlation of global features of the retinal vasculature with retinal abnormalities. The accurate extraction of AV trees also provides the opportunity to analyse the physiology and hemodynamic of blood flow in retinal vessel trees. A number of common diseases, including Diabetic Retinopathy, Cardiovascular and Cerebrovascular diseases, directly affect the morphology of the retinal vasculature. Early detection of these pathologies may prevent vision loss and reduce the risk of other life-threatening diseases. Automated extraction of AV trees requires complete segmentation and accurate classification of retinal vessels. Unfortunately, the available segmentation techniques are susceptible to a number of complications including vessel contrast, fuzzy edges, variable image quality, media opacities, and vessel overlaps. Due to these sources of errors, the available segmentation techniques produce partially segmented vascular networks. Thus, extracting AV trees by accurately connecting and classifying the disconnected segments is extremely complex. This thesis provides a novel graph-based technique for accurate extraction of AV trees from a network of disconnected and unclassified vessel segments in fundus viii images. The proposed technique performs three major tasks: junction identification, local configuration, and global configuration. A probabilistic approach is adopted that rigorously identifies junctions by examining the mutual associations of segment ends. These associations are determined by dynamically specifying regions at both ends of all segments. A supervised Naïve Bayes inference model is developed that estimates the probability of each possible configuration at a junction. The system enumerates all possible configurations and estimates posterior probability of each configuration. The likelihood function estimates the conditional probability of the configuration using the statistical parameters of distribution of colour and geometrical features of joints. The parameters of feature distributions and priors of configuration are obtained through supervised learning phases. A second Naïve Bayes classifier estimates class probabilities of each vessel segment utilizing colour and spatial properties of segments. The global configuration works by translating the segment network into an STgraph (a specialized form of dependency graph) representing the segments and their possible connective associations. The unary and pairwise potentials for ST-graph are estimated using the class and configuration probabilities obtained earlier. This translates the classification and configuration problems into a general binary labelling graph problem. The ST-graph is interpreted as a flow network for energy minimization a minimum ST-graph cut is obtained using the Ford-Fulkerson algorithm, from which the estimated AV trees are extracted. The performance is evaluated by implementing the system on test images of DRIVE dataset and comparing the obtained results with the ground truth data. The ground truth data is obtained by establishing a new dataset for DRIVE images with manually classified vessels. The system outperformed benchmark methods and produced excellent results.

The "many fragments curse," a special case of the segment length curse, occurs in den- drochronology when time series are broken into fragments, either because of missing part of a sample (e.g., a rot pocket) or when a section of ring growth cannot be crossdated (e.g., a section with extremely suppressed growth and/or many rings absent). We exorcise this curse by inserting values to connect fragments of measurements. This technique permits fitting a single detrending curve to the connected series and thus preserves the low-frequency variance contained in the entire series. Inserted values are discarded after detrending and do not otherwise affect calculations of final corn- posite chronologies. As an example from junipers sampled at a site in Qinghai Province, China, 66 of 117 increment cores have nondatable sections of wood and one core has a gap of rotten wood between dated fragments. After connecting fragments by inserting values and then detrending, the chronology constructed from connected fragments has stronger century to multicentury scale variation than the chronology constructed from separate fragments. This approach is adapted to the library of computer programs developed for dendrochronological research under the auspices of the International Tree-Ring Data Bank.

This dissertation concerns the development of an interactive machine learning method for refinement and analysis of segmented computed tomography (CT) images. This method uses higher-level domain-dependent knowledge to improve initial image segmentation results. A knowledge-based refinement and analysis system requires the formulation of domain knowledge. A serious problem faced by knowledge-based system designers is the knowledge acquisition bottleneck. Knowledge acquisition is very challenging and an active research topic in the field of machine learning and artificial intelligence. Commonly, a knowledge engineer needs to have a domain expert to formulate acquired knowledge for use in an expert system. That process is rather tedious and error-prone. The domain expert's verbal description can be inaccurate or incomplete, and the knowledge engineer may not correctly interpret the expert's intent. In many cases, the domain experts prefer to do actions instead of explaining their expertise. These problems motivate us to find another solution to make the knowledge acquisition process less challenging. Instead of trying to acquire expertise from a domain expert verbally, we can ask him/her to show expertise through actions that can be observed by the system. If the system can learn from those actions, this approach is called learning by demonstration. We have developed a system that can learn region refinement rules automatically. The system observes the steps taken as a human user interactively edits a processed image, and then infers rules from those actions. During the system's learn mode, the user views labeled images and makes refinements through the use of a keyboard and mouse. As the user manipulates the images, the system stores information related to those manual operations, and develops internal rules that can be used later for automatic postprocessing of other images. After one or more training sessions, the user places the system into its run mode. The system then accepts new images, and uses its rule set to apply postprocessing operations automatically in a manner that is modeled after those learned from the human user. At any time, the user can return to learn mode to introduce new training information, and this will be used by the system to updates its internal rule set. The system does not simply memorize a particular sequence of postprocessing steps during a training session, but instead generalizes from the image data and from the actions of the human user so that new CT images can be refined appropriately. Experimental results have shown that IntelliPost improves the segmentation accuracy of the overall system by applying postprocessing rules. In tests two different CT datasets of hardwood logs, the use of IntelliPost resulted in improvements of 1.92% and 9.45%, respectively. For two different medical datasets, the use of IntelliPost resulted in improvements of 4.22% and 0.33%, respectively.
Ph. D.

A volume equation for predicting individual tree volume, and a taper function for describing a stem profile were developed for a little known species, Styrax tonkinensis (Siam benzoin) in northern Laos. The species has high potential commercial value and can make an important contribution to the local economy. It can provide two different types of products, a non-wood product (benzoin resin) and timber. In Laos, the most important product is currently resin, and the use of timber for commercial purposes is rare. One reason is that information about the timber is not available. In Vietnam, on the other hand, the species is an import pulpwood species. Data used in this study came from 73 trees. Trees were purposely selected to ensure coverage of a full range of tree sizes. Measurement was undertaken only on over-bark diameters due to some constraints, limitations and problems during the field data collection. However, due to the importance of under-bark volume for this species, a small available dataset was used to build a bark model as an interim guide to the errors associated with using over-bark models for estimating under-bark volumes. From this bark model, errors in estimating under-bark volumes of trees with diameters at breast height between 10cm and 17 cm were approximately 18%. Nineteen individual volume models, and 7 individual taper functions were compared for bias and precision. Collective names for the volume equations tested include single-entry, double-entry, logarithmic, combined variables. Most volume models had similar bias but a few were clearly biased. The models with similar bias were further evaluated by four common statistics including bias, standard error of estimates, standard deviation of residuals and mean absolute deviation. The results showed that a five parameter model was ranked first, and was the most precise model. However, the magnitudes of difference in prediction errors between this model and other models, particularly the three parameter model were not significant. For practical purposes, the simpler model was preferred. Seven taper functions tested here belong to three different groups including single taper equations, compatible taper equations and segmented taper equations. Evaluation of taper equations used the same residual analysis procedures and criteria as those applied with volume equations. Graphical residual analysis showed that most taper models had similar precision with their errors in diameter predictions being similar in range. However, some models showed obvious bias. The most highly ranked taper model was a compatible taper model of polynomial form. It was the least biased model. The second ranked model was a single, simple model. This latter model is relatively simple to apply, but it is not compatible with the volume model, yielding slightly different estimates of volume if it is integrated and rotated around the longitudinal axis of a tree. However, if the sole purpose is to describe tree taper, it is the best model to use.

Les courbes frontières définissent les régions ou les formes du plan de manière compacte et descriptive. Il est bien connu que les formes doivent être étudiées à différentes échelles. Ceci a conduit au développement des pyramides régulières et irrégulières pour l'analyse des formes et la compréhension des scènes. Cependant, il n'existe pas une description analytique de la multi-résolution d'une forme numérique, contrairement au célèbre espace-échelle (scale-space) dans le monde continu. En outre, les primitives géométriques telles que les lignes, les cercles ou les polynômes ont une grande importance dans le contexte de la géométrie numérique. Les morceaux des droites numériques sont un bon moyen pour estimer les tangentes et les arcs discrets approchent la courbure. Il est donc nécessaire de les garder dans l'analyse multi-échelle des frontières numériques. Un des objectifs de cette thèse est de donner des nouveaux résultats analytiques sur la multi-résolution des droites 4-connexes et des segments de droites 4-connexes. Figueiredo est le premier qui a étudié le comportement des droites 8-connexes lors du changement de la résolution de la grille. Dans le présent travail, nous considérons une droite 4-connexe pour laquelle une description analytique est fournie lorsque la résolution de la grille est modifiée par un facteur arbitraire. En plus, nous montrons que leurs couvertures sont des droites 4-connexes. Comme les formules analytiques des segments de droite sont un problème beaucoup plus difficile, nous proposons un parcours indirect pour la multi-résolution d'un DSS en utilisant le fait qu'un segment est un morceau fin d'une droite discrète. Etant donné un DSS, nous construisons deux droites dont l'intersection le contient et dont la partie connexe principale a les mêmes caractéristiques arithmétiques, ainsi que le même nombre de motifs. Notons que nous proposons de nouveaux résultats combinatoires des intersections de droites. Nous déterminons la multi-résolution du segment en examinant la multi-résolution de l'intersection de ces deux droites. Nous donnons une nouvelle description analytique de cet ensemble avec des inégalités arithmétiques. Nous abordons également le problème du calcul des caractéristiques exactes d'un sous-segment d'une droite 4-connexe qui a des caractéristiques connues. Nous présentons deux nouveaux algorithmes SmartDSS et ReversedSmartDSS qui résolvent ce problème. Leur principe est de se déplacer dans l'arbre de Stern-Brocot de la fraction soit de manière haut-bas ou bas-haut. Dans le pire cas, leur complexité est meilleure que l'algorithme de reconnaissance DSS classique. Les deux algorithmes peuvent dès lors servir à calculer efficacement la multi-résolution d'un segment. Les bruits tout au long des contours numériques ne sont pas vraiment détectés, mais plutôt annulés par l'épaississement des segments de droites 4-connexes. De plus, l'épaisseur est réglée par un utilisateur et aussi définie globalement pour le contour. Pour surmonter ce problème, nous proposons une stratégie originale pour détecter localement à la fois la quantité de bruit et les épaisseurs significatives de chaque point de contour. Ce travail se base sur les propriétés asymptotiques de segments flous d'épaisseurs différentes, et forme une alternative à l'approche multi-résolution de la détection du bruit
Boundary curves are compact and descriptive means for defining regions or shapes in the plane. It is well known that shapes should be studied at different scales. This has led to the development of regular and irregular pyramids for shape analysis and scene understanding. However there exists no analytical description of the multiresolution of a digital shape, contrary to the famous scale-space analysis in the continuous world. Moreover, in the context of digital geometry, geometric primitives such as lines, circles or polynomials are of a great importance. For instance, pieces of digital lines are excellent tangent estimators, circular arcs estimate curvature. It is thus fundamental to keep them in the multiscale analysis of digital boundaries. One of the contribution of this thesis is to give new analytical results on the multiresolution of Digital Straight Line (DSL) and Digital Straight Segment (DSS). Figueiredo is the first one who studied the behavior of 8-connected lines when changing the resolution of the grid [41]. In this work, we consider a standard digital line. The objective is to provide an analytic description of digital straight line DSL when the resolution of the grid is changed by an arbitrary factor. We also prove that their subsampling is a standard digital line. As analytical formulae for DSS appear to be a much harder problem and DSS are finite parts of DSL, we propose an indirect path to DSS multiresolution. Given a DSS, we build two DSL whose intersection contains it and whose main connected part has the same arithmetic characteristics as well as the same number of patterns. We note here that we propose new results about the combinatorics of such digital line intersections. We determine the multiresolution of DSS by examining the multiresolution of the intersection of these two DSL. We give a new analytical description of this set with arithmetic inequalities. We also address the problem of computing the exact characteristics of any subsegment of digital straight line with known characteristics. We present two new algorithms SmartDSS and ReversedSmartDSS that solve this problem. Their principle is to climb the Stern-Brocot tree of fraction either in a top-down or bottom-up way. Their worst-time complexity are better than the classical DSS recognition algorithm. Both algorithms are useful to compute efficiently the multiresolution of a DSS. The noise along digital contours is not really detected but is rather canceled out by thickening digital straight segments. The thickness is tuned by a user and set globally for the contour. To overcome this issue, we propose an original strategy to detect locally both the amount of noise and the meaningful thickness of each point of a digital contour. This work is based on the asymptotic properties of blurred segments with different thicknesses and forms an alternative to the multiscale approach to noise detection

El presente trabajo de suficiencia profesional se enfoca en el establecimiento de una propuesta de mejora en la segmentación comercial de clientes del segmento Grandes Empresas de tres de los principales bancos del Perú y para desarrollarla se realizó una investigación cualitativa exhaustiva en base a fuentes primarias y secundarias (principalmente entrevistas a gerentes expertos en la materia). Mediante el presente trabajo se concluye que muchos productos o servicios ofrecidos por tres de los principales bancos del Perú no tienen el impacto deseado en los clientes, pese a que dichos bancos utilizan tecnología de vanguardia en su desarrollo e implementación. Ello debido a que la segmentación comercial actual realizada por dichos bancos no necesariamente es la correcta, pues solo considera variables demográficas en el proceso. Por ello, se propone realizar una segmentación demográfica a priori y una segmentación psicográfica post – hoc que se enfoque en el íntegro de los clientes.

Trabajo de Investigación Requisito para optar al Título de Cirujano Dentista
Autor no autoriza el acceso a texto completo de su documento
Los cementos de resina compuesta autoadhesivos se desarrollaron con el fin de simplificar la técnica de aplicación manteniendo la misma eficacia de los cementos que requieren de acondicionamiento previo. Si bien algunos estudios demuestran un mejor comportamiento en cuanto a la fuerza adhesiva en dentina coronaria lograda con los cementos tradicionales como RelyX ARC con su sistema adhesivo, respecto al cemento RelyX U100 autoadhesivo, no existen estudios similares que demuestren este comportamiento en dentina radicular. Objetivo: Establecer las diferencias en el grado de resistencia adhesiva lograda en el segmento cervical, medio y apical de dentina radicular que presentan dos sistemas de cemento de resina compuesta diferentes. Material y Método: 30 piezas dentarias humanas unirradiculadas sanas, recientemente extraídas, fueron seccionadas a nivel del límite amelocementario. La raíz fue dividida en dos hemirraíces, las que a su vez, fueron seccionadas en tres segmentos: cervical, medio y apical. Se obtuvieron 180 muestras de dentina radicular separadas en 6 grupos de 30 muestras cada uno, a las que se les adhirió un cilindro de resina compuesta de 2 mm de diámetro con el cemento y sistema adhesivo correspondiente: Grupo A1: Segmento cervical/ RelyX U100; A2: Segmento medio/ RelyX U100; A3: Segmento apical/ RelyX U100; B1: Segmento cervical/ RelyX ARC+ SingleBond2; B2: Segmento medio/ RelyX ARC+ SingleBond2; B3: Segmento apical/ RelyX ARC+ SingleBond2. Los cuerpos de prueba fueron testeados en la máquina de ensayos universales Instron, que aplicó fuerzas de cizallamiento a una velocidad de 2 mm/min. Se realizó análisis estadístico descriptivo e inferencial, con un nivel de significancia de 0,05. Resultados: Los promedios de resistencia adhesiva expresados en megapascales fueron: A1=26,24; A2=24,61; A3=22,50; B1=30,07; B2=25,98; B3=22,17. 5 Conclusión: RelyX ARC+ SingleBond2, presentó mayores valores de adhesión que RelyX U100 en el segmento cervical y medio, no así en el segmento apical. Estas diferencias no fueron estadísticamente significativas (p>0,05). En ambos sistemas adhesivos, el mayor grado de resistencia adhesiva se presentó en el segmento cervical, seguido del segmento medio y apical, encontrándose sólo diferencias significativas en el sistema RelyX ARC+ SingleBond2 entre el segmento cervical y apical (p=0,014) a través del test de Tukey.

Orientador : Margareth Brandini Park
Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Educação
Made available in DSpace on 2018-08-08T13:40:21Z (GMT). No. of bitstreams: 1 Santos_KatiaRiccidos_M.pdf: 11656933 bytes, checksum: 8307e7658767469ee7bb2eb3adac834d (MD5) Previous issue date: 2007
Resumo: A fim de contribuir para a melhoria das instituições de longa permanência, essa pesquisa tem como objetivo analisar como três segmentos distintos ? asilados, voluntários e gestores ? constroem e ressignificam a história de um asilo e as suas histórias de vida a partir dos vínculos institucionais. A pesquisa foi desenvolvida numa instituição de longa permanência, a Vila São Vicente de Paulo, fundada em Atibaia - SP em 1924. A metodologia usada foi a pesquisaação, utilizando-se no processo de reconstrução da história institucional e da história dos sujeitos imagens fotográficas do acervo oficial associadas à história oral. A análise dos dados foi composta: a) da visão panorâmica das narrativas individuais produzidas da seleção de imagens; b) discussão dos principais temas levantados em cada segmento associando-os aos conceitos encontrados na literatura: afetividade na velhice asilada, declínio físico e finitude (asilados), valorização das atividades e dos relacionamentos sociais (voluntários) e visão administrativa do cuidar de velhos (gestores); c) interpretação das fotografias excluídas. A afetividade e a sexualidade dentro do asilo são vividas de forma emblemática, ou seja, há estratégias do cotidiano, como as festas, para poder expressá-las. A finitude é um tema constantemente presente no discurso. Os voluntários pretendem ser o vínculo com o mundo externo e proporcionar atividades sociais consideradas fundamentais. Existe a preocupação dos gestores em administrar a instituição oferecendo mais do que alimentação, cuidados de saúde e habitação, mas a maioria sente que não tem formação gerontológica para fazê-lo
Abstract: Intending to improve the long-term care institutions, this study aims to analyze how three distinguished groups - dwellers, volunteers and managers - affect na institution's history and the new significance of their own lives concerning their relationship with it. The research was developed in Vila São Vicente de Paulo, a long-term care institution in Atibaia, SP, founded in 1924. The methodology used was action-search using photographs from the institution?s collection, and oral history throughout the history reconstruction. Data analysis involved three steps: A) overview of the individual narratives, recorded from the chosen photographs, b) discussion of the themes considered the most important ones for each group na linking them with concepts of the literature: affect in the old age in an institution (for the elderly), bodily decay and finitude (dwellers), valorization of activities and social relationship (volunteers) and perceptions of caring for older persons (managers); c) interpretation of the photographs which were not chosen. Affection and sexuality in the institution are dealt with in symbolic ways, with daily strategies like parties and events. The theme finitude is frequently mentioned somehow. The volunteers intend to link institution and extramural community, and provide activities considered (by them) fundamental. the managers concern about caring for the institution and offering more than only proper alimentation, health caring and homes, but many consider themselves insufficiently prepared concerned knowledge
Mestrado
Gerontologia
Mestre em Gerontologia

Orientador: Fernando Augusto Silva Marins
Resumo: Em diferentes aspectos da vida cotidiana, o ser humano é forçado a escolher entre várias opções, esse processo é conhecido como tomada de decisão. No nível do negócio, a tomada de decisões desempenha um papel muito importante, porque dessas decisões depende o sucesso ou o fracasso das organizações. No entanto, em muitos casos, tomar decisões erradas pode gerar grandes custos. Desta forma, alguns dos problemas de tomada de decisão que um gerente enfrenta comumente são, por exemplo, a decisão para determinar um preço, a decisão de comprar ou fabricar, em problemas de logística, problemas de armazenamento, etc. Por outro lado, a coleta de dados tornou-se uma vantagem competitiva, pois pode ser utilizada para análise e extração de resultados significativos por meio da aplicação de diversas técnicas, como estatística, simulação, matemática, econometria e técnicas atuais, como aprendizagem de máquina para a criação de modelos preditivos. Além disso, há evidências na literatura de que a criação de modelos com técnicas de aprendizagem de máquina têm um impacto positivo na indústria e em diferentes áreas de pesquisa. Nesse contexto, o presente trabalho propõe o desenvolvimento de um modelo preditivo para tomada de decisão, usando as técnicas supervisionadas de aprendizado de máquina, e combinando o modelo gerado com as restrições pertencentes ao processo de otimização. O objetivo da proposta é treinar um modelo matemático com dados históricos de um processo decisório e obter os predit... (Resumo completo, clicar acesso eletrônico abaixo)
Mestre

碩士
國立成功大學
資訊工程學系碩博士班
97
Packet classification has received much attention and continued to be an important topic in recent years. Each incoming packet needs to determine both the output port it should be sent to and what action should be taken. Several high performance approaches for solving packet classification has been proposed. In general, these approaches can be roughly divided into two categories: algorithmic and architectural. Grid-of-tries is one of the traditional algorithmic schemes for solving 2-dimensional packet classification problem, however, the data structure of gird-of-tries is based on binary tries which is not suitable for the port range fields. By using the concepts of switch pointers and extended pointers, grid-of-tries can find best matching filter or multiple matching filters without backtracking during search and save lots of search cost. In this thesis, we replace the binary tries by an efficient data structure, called segment trees to modify and improve the original grid-of-tries and we proposed two data structures, which are called the DGST (Dynamic Grid of Segment Trees) and DGMST (Dynamic Grid of Multiway Segment Trees) respectively. The DGST is a multidimensional balanced binary search tree structure while the DGMST is a multidimensional B-tree structure. Our proposed schemes combine the advantage of grid-of-tries and segment trees and support incremental updates. For each dimension contains N elements, the search procedure can be accomplished in O(logN) time. Experiments using three kinds of rule tables which are generate from ClassBench [12], our proposed schemes can have a better performance than traditional schemes, such as hierarchical trie, grid-of-tries and Hypercut.

碩士
國立成功大學
資訊工程學系碩博士班
93
The problem of IP address lookup has received much attention recently and several high performance algorithms and data structures have been proposed. Current IP lookup algorithms can be broadly classified into two categories: those focus on improving the lookup speeds and reducing the memory requirement by using precomputation (these schemes usually prohibit doing updates), and those can support the dynamic update without any precomputation. Although precomputation can simplify the data structures built by routing lookup algorithms and thus improve the performance of the lookup speed and memory requirement, the entire data structure may need to be rebuilt when a single prefix is added or deleted. Besides, since instabilities in the backbone protocols [12] can lead to rapid insertion and deletion of prefixes, algorithms that can support fast updates are desirable. 　In this thesis, we focus on efficient data structures that can support the dynamic update. We propose two data structures, which are called the DST (Dynamic Segment Tree) and MDST (Multiway Dynamic Segment Tree) respectively, based on segment trees for dynamic routing tables. The DST is a balanced binary search tree structure while the MDST is a B-tree structure. For a routing table of n prefixes, all dynamic routing table operations (query, insertion, and deletion) can be accomplished in O(logn) time and each prefix is stored in O(1) nodes per tree level both for our proposed data structures. Experiments using five real IPv4 routing tables indicate that, our proposed MDST outperforms the other two B-tree structural schemes PIBT [17] and MRT [32] in all aspects, and the query operation of our DST is considerably faster than a fast update data structure PBOB [16].

碩士
國立成功大學
資訊工程學系碩博士班
101
Recently, research community has drawn lots of attentions in the router virtualization that allows multiple virtual router instances running on the same physical router platform. Thus, the virtualized router should be able to handle packets from different virtual networks. Once the multiple virtual routing tables are merged, memory requirement can be reduced due to the common entries among virtual routing tables. Many previous works use trie-based methods to merge the virtual routing tables. In this thesis, we propose two range-based merging methods. The data structures are based on the dynamic multiway segment tree (DMST) that is implemented with standard B-tree structure. As our experimental results show, the two proposed methods perform much better than the trie-based ones in lookup speed, update performance, scalability, and have similar memory consumption.

博士
國立臺灣海洋大學
航運管理學系
106
This study employs classification and regression tree (CART) to segment customer retention for container shipping carriers to divide their customer groups. From the integrated marketing perspective, both methods of decision tree and beta regression tree are used to segment this market by exploring the relationships between the shipping service attributes and the Likelihood of a customer not churning to a new service provider (LNC) which is used as a proxy of customer retention. After using the above two methods to analyze the empirical data, some results are discovered as the following: (1) service quality, as a partitioned variable, separates the overall market into five groups with different functional relationships between LNC and various marketing activities; (2) the average LNC of the highest customer retention group is about 60% which reflects that the customer retention and then customer loyalty are low in this industry; (3) the attributes of price and discount, personal selling and customer relationship have significant impact on likelihood of customer retention in descending order; (4) satisfactory price and discounts are the most important attribute to support the likelihood of customer retention; and (5) attributes of word of mouth, advertising, and switching cost have little importance for increasing LNC. The results provide container shipping managers the clues to understand the different reasons for types of relationship with the five customer groups. This information is very important to determine which relationships prove the most valuable, and in turn, to form an adequate customer portfolio. By managing different portfolios for different segments of the customers, sales representatives who have high relational intelligent ability in container shipping companies could then convert data into profit for themselves.

碩士
國立成功大學
資訊工程學系碩博士班
96
Packet classification is extensively applied to a variety of Internet applications including network security, quality of service, multimedia communications and so on. Thus, packet classification is gaining more and more concerns nowadays. Traditionally, we consider using standard Ternary Content Addressable Memory (TCAM) as a hardware classification engine. However, this approach is inefficient to store classification tables because the port range fields of a packet have to be broken into prefixes before stored in TCAM. To solve the question, has been proposed, which a novel multifield classification scheme [2]. To reduce the cost, we don’t want waste too much TCAM space when we store the classification tables in TCAM since the port fields of the classification tables are arbitrary ranges. Thus, we adopt the -encoding schemes for the ranges can greatly reduce the usage of TCAM space. We noticed that these encoding schemes are time consuming when updating. This is because these schemes need to pre-compute results and encode the ranges in classification tables. In this thesis, we improve these encoding schemes which can map the ranges into TCAM with incremental update by using dynamic segment tree (DST), where DST is a segment tree data structure for solving dynamic table lookup problems. And we develop these schemes which can update dynamically, partially update the TCAM entries but not all the ones.

碩士
國立中山大學
資訊工程學系研究所
95
A Peer-to-Peer system is a distributed system whose component nodes participate in similar roles. Every user node (the peer) can exchange and contribute its resources to another one in the system. Similar to the case that peers may dynamically join and leave the system, the data will also be inserted into and removed from the system dynamically. Given a certain range, a range query will find any data item whose value within the range. For example, a range query can find all the Beatle''s works between 1961 and 1968 for us. However, once the range data is distributed over a P2P system through the hash function which has been used largely in many P2P systems, the continuity of the range data is not guaranteed to exist. Therefore, finding the scattered data whose value within a certain range costs much in a P2P system. The Distributed Segment Tree method (DST) preserves the local continuity of the range data at each node by using a segment tree and can break any given range into minimum number of node intervals whose union constitutes the whole requested range. The DST method works based on the Distributed Hash Table (DHT) logic; therefore, it can be applied in any DHT-based P2P system. However, data distribution of the DST method may cause overlapping. When searching a data range, the DST method sends more number of requests than what is really needed. Although the DST method designs the Downward Load Stripping Mechanism, the load on peers still may not be balanced. The main reason of these problems is that the DST method applies the DHT logic to the P2P systems. Therefore, in this thesis, we propose a method called Structured Segment Tree (SST) that does not use the DHT logic but embeds the structure of the segment tree into the P2P systems. In fact, the P2P network topology of an SST is the structure of a segment tree. Unlike a DST, an SST can fully reflect the properties of the original segment tree. Each peer in our proposed P2P system represents a node of a segment tree. Data intervals at the same level are continuous and will not overlap with each other. The union of data intervals at a level with full nodes is totally the whole data range which the P2P system can support. When searching a data range, the SST method sends as many number of requests as needed. In addition, we add sibling links to preserve the spatial locality and speed up the search efficiency. For the issue of load balance, our SST method also performs better than the DST method. From our simulation, we show that the SST method routes less number of peers to locate the requested range data than the DST method. We also show that the load based on our method is more balanced than that based on the DST method.

碩士
東海大學
資訊工程學系
103
In the wafer production process, cost is an important factor. Due to the requirement of experimental or special purpose chips, for a lower cost consideration, multi-specification dice arrangements are needed to generate these chips. This study proposes a placement and cut algorithm suitable for the dicing plan. Besides the best locations, this study considers the best cut to decrease production cost by decreasing the slicing collision problem in a dicing plan. A hierarchical algorithm is used for placement and cut algorithm. Firstly, initialize the location for different chips to simplify the input. Secondly, use slicing tree for the arrangement of the chip placement with the minimum cut. A simulated annealing algorithm combined with a vertical and horizontal conflict and coloring theorem are used to optimize the placement and cut for wafer floorplan. In the cutting conflict decision period of coloring algorithm (used as an objective function of the SA algorithm), two different methods are compared. The first one considers enumeration of the width and height of each chip to decide if they conflict with each other. The other uses the segment tree data structure to decrease the computation time. The second method is expected to outperform the first one in run time.

This thesis presents a collection of studies on the topic of survivable transparent optical networks. As backbone networks increase in capacity, the issue of their survivability grows correspondingly in importance. The transparent optical network offers many advantages as the optical backbone network of the future, but also faces several challenges with regards to network protection. The fundamental question addressed by this thesis is therefore “How can we achieve high availability and failure resiliency in transparent optical transport networks?” We cover the design, characterization, and comparison of several protection architectures, many of them novel, that share the property of pre-cross-connection, a property that is important for protection of transparent networks. The architectures studied include span p-trees, PXTs, path p-trees, p-cycles, FIPP p-cycles, and UPSR-like p-cycles. We first present detailed studies of the PXT, span p-tree, and path p-tree architectures. This includes the development of efficient design algorithms and structural analysis of efficient designs. The results indicate a clear hierarchy of efficiency, with cycles being the most efficient, followed by trails, and then trees. However, we discover that architectures with lower average efficiency can be used to complement more efficient structures in rare cases. We also present a new design method for PXTs that is as capacity-efficient as the prior established method, but produces designs with greatly improved structural characteristics. We then move on to address PXT protection under a collection of real-world design constraints. The results show that PXTs strike a balance between efficiency and flexibility under these constraints. A further study on the problem of failure localization in transparent p-cycle networks demonstrates the possibility of integrating low cost failure localization capabilities into p-cycle network designs. Finally, we propose UPSR-like p-cycles as a way to combine the simplicity and speed of dedicated protection with the flexibility of mesh-based approaches. The results from our design experiments show that this architecture is able to take advantage of mesh topologies in a way that traditional ring-based approaches cannot. We also demonstrate methods by which UPSR-like p-cycle networks can deliver superior dual failure restorability to a select class of high priority services.
Communications