Experimental and Theoretical Approaches for Efficient Tree Distance Algorithms

高效树距离算法的实验和理论方法

• 批准号: 0811002
• 负责人: Sean Cleary
• 金额: $ 12.1万
• 依托单位: CUNY City College
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2008
• 资助国家: 美国
• 起止时间: 2008-07-01 至 2012-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0811002&HistoricalAwards=false
• 关键词: Experimental; Theoretical; Approaches; Efficient; Tree

This project has involves research on several fronts in binary trees and algorithms for their efficient use. Rotations are small changes to binary tree structures used in balancing and optimizing search trees for efficient searching. The rotation distance between two trees is the minimal number of such small changes required to transform one tree into another. There are no known algorithms for computing rotation distances effectively, and even precise bounds on rotation distance are difficult to obtain. This project develops methods for improving understanding of rotation distances and algorithms for computing or estimating them. This research involves experiments to understand the general properties of rotation distances, as well as developing abstract methods for describing rotation distances based upon connections between rotation distances and geometric methods in group theory.This project seeks to improve methods and understanding of binary trees and relevant algorithms. Binary trees are a fundamental structure, underlying efficient storage of data sets for quick retrieval of items. The amount of data routinely used in modern scientific and engineering settings is often staggeringly large. Biological data sets, for example, are often gigabytes of data. When working with large data sets, the efficiency of methods used to analyze the data is of crucial importance- many questions which are immediate for small data sets are far beyond the capability of even today's most powerful computers for even moderate-sized data sets. Careful organization of large data sets is essential for productive investigation

该项目涉及二叉树及其有效使用算法的多个前沿研究。旋转是对二叉树结构的微小更改，用于平衡和优化搜索树以实现高效搜索。两棵树之间的旋转距离是将一棵树转变为另一棵树所需的此类小变化的最小数量。没有已知的算法可以有效地计算旋转距离，甚至很难获得旋转距离的精确界限。 该项目开发了提高对旋转距离的理解的方法以及计算或估计旋转距离的算法。这项研究涉及通过实验来了解旋转距离的一般性质，以及基于旋转距离和群论中的几何方法之间的联系开发描述旋转距离的抽象方法。该项目旨在改进对二叉树和相关算法的方法和理解。二叉树是一种基本结构，是数据集有效存储的基础，用于快速检索项目。现代科学和工程环境中常规使用的数据量通常大得惊人。例如，生物数据集通常有千兆字节的数据。 在处理大型数据集时，用于分析数据的方法的效率至关重要——对于小型数据集来说，许多直接的问题远远超出了当今最强大的计算机处理中等大小数据集的能力。仔细组织大型数据集对于富有成效的调查至关重要