一种基于树型结构的P2P系统高维数据检索方法

被引：7

作者：

彭良睿

李学明

机构：

[1] 重庆大学计算机学院

来源：

计算机应用研究 | 2015年 / 32卷 / 03期

关键词：

树型结构; 高维数据; 检索; 范围查询;

D O I：

暂无

中图分类号：

TP391.3 [检索机]; TP311.12 [];

学科分类号：

摘要：

P2P中基于DHT的路由算法不支持范围查询,因此对高维数据查询的支持不是很好。当前P2P处理高维数据的主流方法是降维和空间填充技术,但两者均有很明显的缺点。针对这些问题,提出一种将树型结构——Baton树应用于高维数据检索的方法,操作简单,无须降维,且支持范围查询。经过实验证明,查询的时间复杂度达到O(log2n),与Baton树在检索一维数据时的效率相同。树型结构可以增加子节点数量,通过增加扇出的方式,减少时间开销,理论上可以使时间复杂度降低为O(logmn)。

引用

页码：842 / 845

页数：4

共 14 条

[1] 一种支持高维数据查询的并行索引机制
王寅峰
刘昊
狄盛
胡昊宇
[J]. 华中科技大学学报(自然科学版), 2011, 39 (S1) : 156 - 160
[2] PD-Tree:一种映射空间上的高维数据索引结构
李仲生
李仁发
禹亮
[J]. 小型微型计算机系统, 2011, 32 (12) : 2471 - 2476
[3] HD Tree: A novel data structure to support multi-dimensional range query for P2P networks[J] . Yunfeng Gu,Azzedine Boukerche. &nbspJournal of Parallel and Distributed Computing . 2011 (8)
[4] Chord[J] . Ion Stoica,Robert Morris,David Karger,M. Frans Kaashoek,Hari Balakrishnan. &nbspACM SIGCOMM Computer Communication Review . 2001 (4)
[5] Speeding up Search in Peer-to-peer Networks with a Multi-way Tree Structure. Jagadish HV,Ooi B C,Tan K L. Proceedings of the SIGMOD International Conference on Management of Data . 2006
[6] Querying peer-topeer networks using P-trees. Crainiceanu A,Linga P,Gehrke J, et al. Proceedings of the 7th International Workshop on the Web and Databases: colocated with ACM SIGMOD/PODS 2004 . 2004
[7] Tapestry: A resilient global-scale overlay for service deployment. Zhao BY,Huang L,Stribling J,et al. IEEE Journal on Selected Areas in Communications . 2004
[8] Load balancing and locality in range-queriable data structures. ASPNES J,KIRSCH J,KRISHNAMURTHY A. Proc of the 23rd Annual ACM Symposium on Principles of Distributed Computing . 2004
[9] 空间数据库索引技术[M]. 上海交通大学出版社 , 郭薇,郭菁,胡志勇编著, 2006
[10] Baton:a balanced tree struc-ture for peer-to-peer networks. Jagadish H V,Ooi B C,Vu Q H. Proc of the 31st interna-tional conference on Very large data bases (VLDB 2005) . 2005

← 1 2 →