-
题名用于建立三维GIS的八叉树编码压缩算法
被引量：14
- 1
-
-
作者
曹彤
刘臻
-
机构
北京联合大学应用文理学院信息科学系
北京师范大学计算中心
-
出处
《中国图象图形学报（A辑）》
CSCD
北大核心
2002年第1期50-54,共5页
-
文摘
复杂的空间数据结构在三维 GIS领域中占有突出的地位 ,它直接关系到 GIS的功能和效率 .为了有效地进行三维 GIS大量数据的存储和管理 ,重点讨论了三维 GIS栅格数据结构中的八叉树编码压缩技术 .由于 Morton码值的排序是实现八叉树编码压缩的基础 ,为此 ,根据 Morton码排序的特殊性 ,提出了采用时间复杂度为 O(n)的计数排序算法 ,使排序速度大为提高 ,在此基础上进行压缩处理 ,并对算法的时间及空间复杂度进行了分析 .在 PC机上进行的模拟实验结果表明 ,在目标复杂度一定的前提下 ,八叉树存储数据占用空间小 (当分割阶次为 9阶时 ,八叉树存储量只占栅格存储量的 4 .32 % ) 。
-
关键词
三维地理信息系统
八叉树
计数排序
压缩算法
图象编码
存储空间
GIS
复杂度
-
Keywords
3D GIS, Octree, counting sort, Compression algorithm
-
分类号
TN919.81
[电子电信—通信与信息系统]
P208
[电子电信—信息与通信工程]
-
-
题名基于数组的桶排序算法
被引量：13
- 2
-
-
作者
杨磊
宋涛
-
机构
清华大学计算机科学与技术系
-
出处
《计算机研究与发展》
EI
CSCD
北大核心
2007年第2期341-347,共7页
-
基金
国家"九七三"重点基础研究发展规划基金项目(2004CB318108)
国家自然科学基金项目(60223004
+3 种基金
60321002
60303005
60503064)
教育部科学技术研究重点项目(104236)
-
文摘
经典桶排序算法以链表形式实现“桶”,处理均匀数据效率很高,是O(N)算法.但对极不均匀数据则退化成低效的O(N2)插入排序.讨论了记录携带附加数据的计数排序算法,将“桶”实现为顺序数组,避免链表的动态内存分配直接提高算法效率,并允许快排等O(NlogN)算法处理桶内数据.对均匀数据仍然保持O(N)时间复杂度,对极端不均匀数据则只退化为O(NlogN)的原算法.对一般非均匀数据,证明数组桶排序算法总体性能高于经典算法.均匀数据实验表明,桶排序算法明显优于Lin-ux下标准qsort系统调用,且数组桶排序算法效率更高.而在非均匀的正态数据实验中数组桶算法性能下降明显小于经典桶排序,总体效率仍然优于qsort的直接应用.
-
关键词
复杂度
排序算法
计数排序
桶排序
快速排序
Pennysort
-
Keywords
complexity
sorting algorithm
counting sort
bucket sort
quicksort
Pennysort
-
分类号
TP301.6
[自动化与计算机技术—计算机系统结构]
-
-
题名计算排序算法设计与分析
被引量：7
- 3
-
-
作者
杨绣丞
李彤
赵娜
梁利刚
李超
-
机构
北京大学地球与空间科学学院
云南大学软件学院
北京大学软件与微电子学院
-
出处
《计算机应用研究》
CSCD
北大核心
2014年第3期658-662,695,共6页
-
基金
云南省自然科学基金资助项目(2010CD026
2011FB036)
+3 种基金
云南省教育厅科学研究基金资助项目(2012Y250
2011Y388)
云南省软件工程重点实验室开放基金资助项目(2011SE05
2012SE308)
-
文摘
针对大多数排序算法只考虑了记录本身的大小和记录相对位置,而忽略了记录内部特征,提出一种计算排序算法。通过分析记录本身的特征,快速计算出记录在目标数组中的索引值,从而达到排序的目的。该算法既减少了数据范围对数组排序的影响,又适应了有限小数的排序。实验结果表明,对于密度高、范围宽、特征位数多的大数组排序问题,该算法的性能优于基数排序、计数排序、静态排序等算法。
-
关键词
排序算法
复杂度
基数排序
计数排序
记录内部特征
数组特征
-
Keywords
sort algorithm
complexity
radix sort
counting sort
internal features
array characteristics
-
分类号
TP301.6
[自动化与计算机技术—计算机系统结构]
-
-
题名一种改进的计数排序算法
被引量：5
- 4
-
-
作者
秦玉平
马靖善
-
机构
渤海大学信息科学与工程学院
渤海大学文理学院
-
出处
《渤海大学学报（自然科学版）》
CAS
2010年第2期174-176,共3页
-
基金
辽宁省教育厅青年基金项目(20040022)
-
文摘
提出了一种改进的计数排序算法。首先找到待排序记录应该存放的位置,然后在原数组空间上进行交换。与传统的计数排序算法相比,在不改变时间复杂度的同时,降低了空间复杂度,提高了算法性能。
-
关键词
计数排序
时间复杂度
空间复杂度
-
Keywords
counting sort
time complexity of time
complexity of space
-
分类号
TP301.6
[自动化与计算机技术—计算机系统结构]
-
-
题名用于时态聚合范围查询的分布式时态索引
- 5
-
-
作者
孟繁珺
韩斌
黄树成
梅向东
-
机构
江苏科技大学计算机学院
江苏赞奇科技股份有限公司
-
出处
《计算机应用》
CSCD
北大核心
2024年第6期1848-1854,共7页
-
基金
深海技术科学太湖实验室船舶总体性能创新研究开放基金资助项目(25422217)。
-
文摘
在大数据与云计算时代,时态大数据的查询分析面临许多重要挑战。针对其中时态聚合范围查询性能不佳和不能有效利用索引等问题,提出一种用于时态聚合范围查询的分布式时态索引(DTI)。首先,采用随机或轮询策略对时态数据分区;其次,采用基于时间位数组前缀的分区内索引构造算法建立索引,同时记录包括时间跨度在内的分区统计信息;再次,利用谓词下推筛选时间跨度与查询时间区间重叠的数据分区,扫描索引进行预聚合;最后,将各分区得到的预聚合值按时间归并并聚合。实验结果表明,索引的分区内构造算法处理时间密度2400条每单位时间和0.001条每单位时间的数据的执行时间相近。索引的聚合查询算法相较于ParTime算法:在查询时间线前75%的数据时,每一步用时都至少减少22%;执行选择型聚合函数时,每一步用时都至少减少11%。因此,索引在多数时态聚合范围查询任务中具有更高的速度,它的分区内构造算法能解决数据稀疏问题且执行效率高。
-
关键词
时态索引
时态数据
分布式
时态聚合
计数排序
-
Keywords
temporal index
temporal data
distributed
temporal aggregation
counting sort
-
分类号
TP311
[自动化与计算机技术—计算机软件与理论]
-
-
题名基于计数排序的最小种子集贪心算法
- 6
-
-
作者
赵学锋
陈祥恩
-
机构
西北师范大学计算机科学与工程学院
西北师范大学数学与统计学院
-
出处
《计算机工程与科学》
CSCD
北大核心
2014年第6期1057-1063,共7页
-
基金
国家自然科学基金资助项目(61163037)
-
文摘
网络最小种子集问题与网络影响最大化问题相关,研究的是对于具有节点阈值的网络,构造网络的最小节点子集,使得如果这个子集中的节点是活的,则在给定的影响传播模型下整个网络都受到影响。为此提出了新的贪心算法,以节点的度与阈值的差为关键值对网络节点进行计数排序,然后取值最小的节点进行处理。新算法在时间复杂度上改进了基于最小堆的种子点选取算法。在简单多数阈值模型上针对经典的无标度网络得到了所构造的种子集规模上界。实验在随机生成网络和一些实际网络数据集上进行,结果表明所提方法的有效性,特别在无标度网络上生成的种子集具有比相关算法更小的规模。
-
关键词
网络影响最大化
最小种子集
简单多数阈值
计数排序
Barabasi-Albert网络
-
Keywords
network influence maximization
minimum seed set
simple majority threshold
counting sort
Barabasi-Albert network
-
分类号
TP393
[自动化与计算机技术—计算机应用技术]
-
-
题名基于串行计算的排序算法实证分析
被引量：1
- 7
-
-
作者
陈根方
张立印
-
机构
杭州师范大学信息科学与工程学院
-
出处
《杭州师范大学学报（自然科学版）》
CAS
2010年第2期135-138,共4页
-
文摘
文章简述了排序算法的研究现状,着重分析地址映射计数排序的基本思想,提出了相异密度因子的概念,以快速排序为参照系,通过理论分析和实验数据的实证分析验证,表明相异密度因子是应用领域选择合适的排序算法的重要参考因素,最后指出了排序算法的研究新趋势.
-
关键词
相异密度因子
排序算法
快速排序
地址映射计数排序
-
Keywords
dissimilarity density factor
sort algorithm
quick sort
address mapping counting sort
-
分类号
TP301
[自动化与计算机技术—计算机系统结构]
-
-
题名按位段计数排序法
- 8
-
-
作者
唐开山
-
机构
绍兴文理学院计算机系
-
出处
《计算机应用与软件》
CSCD
北大核心
2004年第3期86-87,122,共3页
-
文摘
本文提出一种按位段计数的排序方法。讨论了该排序法几个关键问题的解决方法 ,给出了算法思想、算法描述、算法分析和实验结果。其理论意义是该排序法的时间复杂度达到O(N) ,其实用价值是该排序法具有较高的排序效率以及与数据类型、分布。
-
关键词
计算机
时间复杂度
排序算法
空间复杂度
按位段计数排序法
-
Keywords
Bit field counting sort counting sort
-
分类号
TP301.6
[自动化与计算机技术—计算机系统结构]
-
