Particle simulation has become an important research technique in many scientific and engineering fields in latest years. However, these simulations will generate countless data, and database they required would therefore deal with very challenging tasks in terms of data management, storage, and query processing. The two-body correlation function (2-BCFs), a statistical learning measurement to evaluate the datasets, has been mainly utilized to measure the spatial distance histogram (SDH). By using a straightforward method, the process of SDH query takes quadratic time. Recently, a novel algorithm has been proposed to compute the SDH based on the concept of density map (DM), and it reduces the running time to ϴ(N(3/2)) for two-dimensional data and ϴ (N(5/3) ) for three-dimensional data, respectively. In the DM-SDH algorithm, there are two types of DMs that can be plugged in for computation: Quad-tree (Oct-tree for three-dimensional data) and k-d tree data structure. In this thesis paper, by using the geometric method, we prove the unre- solvable ratios on the k-d tree. Further, we analyze and compare the difference in the performance in each potential case generated by these DM-SDH algorithms. Experimental results confirm our analysis and show that the k-d tree structure has better performance in terms of time complexity in all cases. However, our qualitative analysis shows that the Quad-tree (Oct-tree) has an advantage over the k-d tree on aspect of space complexity.

Tree-based methods are a nice add-on to traditional statistical methods when solving classification and regression problems. The aim of this master thesis is not to judge which approach is better but rather bring the overview of these methods and apply them on the real data using R. Focus is made especially on the basic methodology of tree-based models and the application in specific software in order to provide wide range of tool for reader to be able to use these methods. One part of the thesis touches the advanced tree-based methods to provide full picture of possibilities.

In the forestry industry tree trunks are currently classified manually. The object of this thesis is to answer whether it is possible to automate this using modern computer hardware and image-classification of tree-trunks using machine learning algorithms. The report concludes, based on results from controlled experiments that it is possible to achieve an accuracy above 90% across the genuses Birch, Pine and Spruce with a classification-time per tree shorter than 500 milli seconds. The report further compares these results against previous research and concludes that better results are probable.

京都大学 / 0048 / 新制・課程博士 / 博士(情報学) / 甲第19336号 / 情博第588号 / 新制||情||103(附属図書館) / 32338 / 京都大学大学院情報学研究科知能情報学専攻 / (主査)教授 阿久津 達也, 教授 山本 章博, 教授 岡部 寿男 / 学位規則第4条第1項該当 / Doctor of Informatics / Kyoto University / DFAM

Various forms of staking, guying, and root ball anchoring are used to prevent post-transplant tree destabilization in the landscape, but little scientific evidence exists to support this practice. This experiment tested the efficacy of three generic tree stabilization systems (TSS) and their effect on tree growth and establishment. In spring 2006, 48 balled and burlapped, 6.4 cm (2.5 inch) diameter, white ash (Fraxinus americana L. Autumn Purpleâ ) were transplanted to a field site in Blacksburg, VA. At planting, one of four TSS treatments (staking, guying, root ball anchoring, or non-stabilized) was installed on each tree. After five weeks, tree pulling tests were conducted on 24 trees to simulate a strong wind load using a cable winch mounted to a skid-steer loader. After one growing season, change in tree height, trunk diameter, and trunk taper were compared among the 24 remaining trees. Soil cores were taken and the length, diameter, and dry weight of roots within the cores were analyzed. TSS were then removed and tree pulling tests were conducted using the same method. The five week tests showed that destabilization was significantly greater for non-stabilized trees (mean of 16 degrees from vertical) than for trees with TSS (all means less than 3 degrees from vertical). Yet after one growing season, there were no significant differences among any treatments in tree stability. We conclude that in locations with high wind speeds, TSS may be necessary for trees similar to those in our study, but only for a very short period of time. Results also indicated that staking, guying, and root ball anchoring were equally effective, very robust, very durable, caused no tree injuries, and did not impact tree growth or establishment after one growing season. Practical considerations may therefore play a more important role when choosing which TSS to use. Although the time required for TSS installation was similar for each system, staking was more than twice as expensive as guying or root ball anchoring. / Master of Science

Tree series transformations computed by bottom-up and top-down tree series transducers are called bottom-up and top-down tree series transformations, respectively. (Functional) compositions of such transformations are investigated. It turns out that the class of bottomup tree series transformations over a commutative and complete semiring is closed under left-composition with linear bottom-up tree series transformations and right-composition with boolean deterministic bottom-up tree series transformations. Moreover, it is shown that the class of top-down tree series transformations over a commutative and complete semiring is closed under right-composition with linear, nondeleting top-down tree series transformations. Finally, the composition of a boolean, deterministic, total top-down tree series transformation with a linear top-down tree series transformation is shown to be a top-down tree series transformation.

Tree series transformations computed by bottom-up and top-down tree series transducers are called bottom-up and top-down tree series transformations, respectively. (Functional) compositions of such transformations are investigated. It turns out that the class of bottomup tree series transformations over a commutative and complete semiring is closed under left-composition with linear bottom-up tree series transformations and right-composition with boolean deterministic bottom-up tree series transformations. Moreover, it is shown that the class of top-down tree series transformations over a commutative and complete semiring is closed under right-composition with linear, nondeleting top-down tree series transformations. Finally, the composition of a boolean, deterministic, total top-down tree series transformation with a linear top-down tree series transformation is shown to be a top-down tree series transformation.

This large body of work is entirely centered around dual-tree algorithms, a class of algorithm based on spatial indexing structures that often provide large amounts of acceleration for various problems. This work focuses on understanding dual-tree algorithms using a new, tree-independent abstraction, and using this abstraction to develop new algorithms. Stated more clearly, the thesis of this entire work is that we may improve and expand the class of dual-tree algorithms by focusing on and providing improvements for each of the three independent components of a dual-tree algorithm: the type of space tree, the type of pruning dual-tree traversal, and the problem-specific BaseCase() and Score() functions. This is demonstrated by expressing many existing dual-tree algorithms in the tree-independent framework, and focusing on improving each of these three pieces. The result is a formidable set of generic components that can be used to assemble dual-tree algorithms, including faster traversals, improved tree theory, and new algorithms to solve the problems of max-kernel search and k-means clustering.

Sequential pattern mining constitutes a basis for solution of problems in various domains like bio-informatics and web usage mining. Research on this field continues seeking faster algorithms. WAP-Tree based algorithms that emerged from web usage mining literature have shown a remarkable performance on single-item sequence databases. In this study, we investigated application of WAP-Tree based mining to multi-item sequential pattern mining and we designed an extension of WAP-Tree data structure for multi-item sequence databases, the MULTI-WAP-Tree. In addition, we propose a new mining strategy on WAP-Tree which involves a hybrid traversal strategy in possible sequences search space and a new early prunning idea called Sibling Principle on Pattern Tree. Two algorithms, FOF-PT and MULTI-FOF-PT, applying this strategy on WAP-Tree and MULTI-WAP-Tree respectively, are developed. Experiments showed that FOF-PT outperforms both other WAP-Tree based algorithms and PrefixSpan in terms of execution time. Moreover, experimental results revealed MULTI-FOF-PT finds patterns faster than PrefixSpan on dense multi-item sequence databases with small alphabets.

Evolutionary relationships between a group of organisms are commonly summarized in a phylogenetic (or evolutionary) tree. The goal of phylogenetic inference is to infer the best tree structure that represents the relationships between a group of organisms, given a set of observations (e.g. molecular sequences). However, popular heuristics for inferring phylogenies output tens to hundreds of thousands of equally weighted candidate trees. Biologists summarize these trees into a single structure called the consensus tree. The central assumption is that the information discarded has less value than the information retained. But, what if this assumption is not true? In this dissertation, we demonstrate the value of retaining and studying tree collections. We also conduct an extensive literature search that highlights the rapid growth of trees produced by phylogenetic analysis. Thus, high performance algorithms are needed to accommodate this increasing production of data. We created several efficient algorithms that allow biologists to easily compare, store and share tree collections over tens to hundreds of thousands of phylogenetic trees. Universal hashing is central to all these approaches, allowing us to quickly identify the shared evolutionary relationships contained in tree collections. Our algorithms MrsRF and Phlash are the fastest in the field for comparing large collections of trees. Our algorithm TreeZip is the most efficient way to store large tree collections. Lastly, we developed Noria, a novel version control system that allows biologists to seamlessly manage and share their phylogenetic analyses. Our work has far-reaching implications for both the biological and computer science communities. We tested our algorithms on four large biological datasets, each consisting of 20; 000 to 150; 000 trees over 150 to 525 taxa. Our experimental results on these datasets indicate the long-term applicability of our algorithms to modern phylogenetic analysis, and underscore their ability to help scientists easily exchange and analyze their large tree collections. In addition to contributing to the reproducibility of phylogenetic analysis, our work enables the creation of test beds for improving phylogenetic heuristics and applications. Lastly, our data structures and algorithms can be applied to managing other tree-like data (e.g. XML).