1(哈尔滨工业大学计算机科学与技术学院 哈尔滨 150001);2(佐治亚州立大学计算机科学与技术学院 美国佐治亚州亚特兰大 30303) (chenyubiao@hit.edu.cn)
出版日期: 2020-11-01基金资助:国家自然科学基金项目(U1811461,61832003,61732003)；美国国家科学基金项目(1741277,1829674)SBS: An Efficient R-Tree Query Algorithm Exploiting the Internal Parallelism of SSDs
Chen Yubiao1, Li Jianzhong1, Li Yingshu1,21(College of Computer Science and Technology, Harbin Institute of Technology, Harbin 150001);2(College of Computer Science and Technology, Georgia State University, Atlanta, GA, USA 30303)
Online: 2020-11-01Supported by:This work was supported by the National Natural Science Foundation of China (U1811461, 61832003, 61732003) and the National Science Foundation of USA (1741277, 1829674).摘要/Abstract
摘要： 由于闪存固态盘逐渐取代机械硬盘成为主流存储，与此同时，随着闪存固态盘技术的进步，越来越多的存储芯片和硬件资源被植入，使得它拥有丰富的内部并行性，而传统的外存算法和数据结构优化工作往往没有考虑固态盘的内部并行性. 范围查询作为R-树索引的基础操作，它的性能对于地理信息系统非常重要. 但是由于R-树索引父子结点之间加载的依赖问题，使得它很难能够有效地去利用固态盘内部并行性去加速. 因此，为了克服该困难，提出一种基于栈结构的范围查询算法SBS(stack batch search). 它能在有效地利用固态盘内部并行性的同时，最多只需要O(B log N)内存空间. 最后，通过真实数据实验来验证SBS算法的性能. 实验结果表明，SBS在可接受的内存消耗情况下，在2款不同的固态盘上，范围查询的性能加速比可达3.4和4.5.
参考文献
相关文章 15
| [1] | 张啸剑, 付楠, 孟小峰. 基于本地差分隐私的空间范围查询方法[J]. 计算机研究与发展, 2020, 57(4): 847-858. |
| [2] | 王飞,钱铁云,刘斌,彭智勇. 支持范围查询的低冗余知识图谱管理[J]. 计算机研究与发展, 2019, 56(8): 1758-1771. |
| [3] | 赵馨逸,黄向东,乔嘉林,康荣,李娜,王建民. 基于不均匀空间划分和R树的时空索引[J]. 计算机研究与发展, 2019, 56(3): 666-676. |
| [4] | 陈玉标,李建中,李英姝,李发明,高宏. 基于闪存固态硬盘内部并行机制的R-树优化方法[J]. 计算机研究与发展, 2018, 55(9): 2066-2082. |
| [5] | 李楚，冯丹，王芳. 一种高性能高可靠的混合客户端缓存系统[J]. 计算机研究与发展, 2017, 54(11): 2497-2507. |
| [6] | 李祥楠,张广艳,李强,郑纬民. 固态盘阵列构建方法研究综述[J]. 计算机研究与发展, 2016, 53(9): 1893-1905. |
| [7] | 李勇,王冉,冯丹,施展. 一种适用于异构存储系统的缓存管理算法[J]. 计算机研究与发展, 2016, 53(9): 1953-1963. |
| [8] | 贲婷婷，秦小麟，许建秋. 支持多种查询的室内移动对象索引[J]. 计算机研究与发展, 2015, 52(9): 2002-2013. |
| [9] | 周维,路劲,周可人,王世普,姚绍文. 基于并发跳表的云数据处理双层索引架构研究[J]. 计算机研究与发展, 2015, 52(7): 1531-1545. |
| [10] | 戴华, 杨庚, 肖甫, 周强, 何瑞良. 两层传感网中能量高效的隐私保护范围查询方法[J]. 计算机研究与发展, 2015, 52(4): 983-993. |
| [11] | 赵 辉 杨树强 陈志坤 尹 洪 金松昌. 基于MapReduce模型的范围查询分析优化技术研究[J]. 计算机研究与发展, 2014, 51(3): 606-617. |
| [12] | 窦 轶, 黄海平, 王汝传, 秦小麟,. 两层无线传感器网络安全范围查询协议[J]. 计算机研究与发展, 2013, 50(6): 1253-1266. |
| [13] | 李晔锋 乐嘉锦 王 梅. 适用于范围查询的列存储数据桶划分算法[J]. , 2013, 50(3): 594-601. |
| [14] | 吴素贞, 陈晓熹, 毛 波,. GC-RAIS：一种基于垃圾回收感知的固态盘阵列[J]. 计算机研究与发展, 2013, 50(1): 60-68. |
| [15] | 陈志广 肖 侬 刘 芳 杜溢墨. 一种用磁盘备份SSD的高性能可靠存储系统[J]. 计算机研究与发展, 2013, 50(1): 80-89. |
PDF全文下载地址:
https://crad.ict.ac.cn/CN/article/downloadArticleFile.do?attachType=PDF&id=4297
