tem*_*def 11
这真的取决于你对"最近"的定义.CLRS包含大量的数据结构,但就其本质而言,它不能涵盖多年来开发的所有伟大的想法和技术.
许多现代研究都是关于缓存不经意的数据结构,这些结构是在某些合理的假设下获得存储器层次结构的最佳优势的结构.Brodal是该领域的一位研究人员,他已经创造了许多这种优秀的结构.
简洁的数据结构 - 旨在尽可能使用最少位数同时仍具有良好时间限制的数据结构 - 也是一个活跃的研究领域.例如,查看小波树.
纯函数式数据结构可用于函数式语言(或用于命令式语言以保证持久性),也是一个活跃的研究课题.例如,Chris Okasaki在这个领域的工作导致了新树和优先队列的发展.
如今,分布式数据结构非常重要.谷歌的BigTable就是一个很好的例子.类似地,并发或无锁数据结构已经进入许多编程语言(例如,参见Java的ConcurrentHashMap或CopyOnWriteArrayList).
基于摊销的数据结构在CLRS中被切向提及,其确实关注于斐波那契堆.然而,并没有提到大约在同一时间发展的展开树和倾斜堆结构,尽管它们今天非常重要.关于splay树的主题,现在正在进行大量的工作以寻找动态最优的BST - 单个二叉搜索树在给定的数据流上也与该流的任何手动调整的BST一样渐近地行为.探戈树和多重显示树是这个领域的有趣读物.
像treap和skip list这样的概率结构已经有很多研究活动,并且是一个继续探索的好地方.相反,像cuckoo哈希表或动态完美哈希表这样强大的哈希表当然值得研究.它们的变体,如布谷鸟过滤器和商过滤器,也非常成功.
过去几年,计算几何的数据结构已经引起了人们的关注,但令人遗憾的是,我对它们的了解还不足以暗示任何特定的结构.
字符串处理的数据结构,即后缀树,在生物计算和网络搜索中极为相关.我不认为CLRS甚至提到它们的存在.但是,你应该仔细研究它们,因为它们负责基因组学的许多新工作.后缀阵列构造算法最近有一些很酷的发展,像SA-IS这样的算法弥合了理论上和实际上快速算法之间的差距.
许多研究人员致力于构建数据结构,利用现代机器可以并行运行多个位的事实.诸如融合树,指数树或y快速树之类的一些结构利用这些属性来对整数数组进行排序和搜索,而不是在天真的比较模型中强加的O(n lg n)障碍.融合树及其后代(指数树等)已经表明,通过词级并行性,您可以获得一些非常令人印象深刻的理论加速,尽管这些结构在实践中并不是非常快.
在摘要,草图绘制和概要数据结构方面还有很多工作要做,这些结构试图回答有关数据集的问题而不显式存储整个数据集.该计数民草图是这些数据结构的一个很好的例子,由于是HyperLogLog基数估计.
这只是新的和酷的结构的一小部分.我希望这是一个很好的起点!
一些相对较新的数据结构（如最近30年）是概率性的，例如Skip Lists。我发现这些特别有趣，但是我不跟进研究。阅读有关算法的最新ACM事务可能会帮助您找到一些有趣且前沿的研究。
但是，大多数“新”事物都将高度专业化。在很长的时间内只有一次创建了一个新的但从根本上来说很重要的算法/结构（如列表，树等）。
| 归档时间： |
|
| 查看次数： |
3179 次 |
| 最近记录： |