SBS: An Efficient R-Tree Query Algorithm Exploiting the Internal Parallelism of SSDs
-
摘要: 由于闪存固态盘逐渐取代机械硬盘成为主流存储，与此同时，随着闪存固态盘技术的进步，越来越多的存储芯片和硬件资源被植入，使得它拥有丰富的内部并行性，而传统的外存算法和数据结构优化工作往往没有考虑固态盘的内部并行性. 范围查询作为R-树索引的基础操作，它的性能对于地理信息系统非常重要. 但是由于R-树索引父子结点之间加载的依赖问题，使得它很难能够有效地去利用固态盘内部并行性去加速. 因此，为了克服该困难，提出一种基于栈结构的范围查询算法SBS(stack batch search). 它能在有效地利用固态盘内部并行性的同时，最多只需要O(B log N)内存空间. 最后，通过真实数据实验来验证SBS算法的性能. 实验结果表明，SBS在可接受的内存消耗情况下，在2款不同的固态盘上，范围查询的性能加速比可达3.4和4.5.Abstract: The flash-based SSD has become the mainstream storage device for its excellent features. At the same time, with the magnificent improvement of internal design of SSD architecture, more and more storage chips and hardware resources are integrated into SSDs which makes them full of internal parallelism, while traditional external memory algorithm and data structure optimization rarely take the internal parallelism of SSDs into consideration. Range query is one of the most important basic operations of R-tree. R-tree is the engine index data structure of many geographic information systems. Therefore, the efficiency of range query plays an important role in the performance of the entire geographic information system. Almost all the tree index structures are difficult to effectively utilize the feature of internal parallelism due to the data loading dependency problem. Therefore, a new range query algorithm SBS(stack batch search) based on stack is proposed, which can effectively utilize the internal parallelism of the SSD with memory usage of O(B log N). Finally, we verify the performance of the SBS algorithm through real data experiments. Experimental results show that SBS has the best performance in range query under acceptable memory consumption. On two different solid-state drives, the speed up ratio of SBS can reach 3.4 and 4.5 separately.
-
Keywords:
- R-tree /
- range query /
- internal parallelism /
- solid state drives /
- speed up
-
-
期刊类型引用(9)
1. 杨海龙，靳新华. 基于ECC复合加密的医院网络隐私信息安全保护方法. 自动化技术与应用. 2024(08): 140-143+166 . 
百度学术
2. 贾卉楠，王斌. 基于移动群智感知的隐私保护研究. 佳木斯大学学报(自然科学版). 2024(09): 16-18+69 . 百度学术
3. 杨小琴，朱玉全. 网络加密数据跨平台迁移自适应决策模型构建. 计算机仿真. 2023(01): 437-440+516 . 百度学术
4. 蒋沥泉，秦志光. 基于属性隐藏的高效去中心化的移动群智数据共享方案. 电子科技大学学报. 2023(06): 915-924 . 百度学术
5. 蔡波. 马尔可夫预测的移动群智感知网络日志信息收集. 西安工程大学学报. 2022(01): 115-120 . 百度学术
6. 佘晓萌 ，杜洋 ，马文静 ，殷赵霞 . 基于像素预测和块标记的图像密文可逆信息隐藏. 计算机研究与发展. 2022(09): 2089-2100 . 本站查看
7. 王磊，陈磊，张明儒，魏敏，李晋先. 面向数据库查询的非结构化数据融合存储系统. 电子设计工程. 2022(24): 148-152 . 百度学术
8. 李卓，宋子晖，沈鑫，陈昕. 边缘计算支持下的移动群智感知本地差分隐私保护机制. 计算机应用. 2021(09): 2678-2686 . 百度学术
9. 熊金波，毕仁万，田有亮，刘西蒙，马建峰. 移动群智感知安全与隐私:模型、进展与趋势. 计算机学报. 2021(09): 1949-1966 . 百度学术
其他类型引用(13)
计量
- 文章访问数: 694
- HTML全文浏览量: 1
- PDF下载量: 275
- 被引次数: 22
下载:
