摘要
P2P中基于DHT的路由算法不支持范围查询,因此对高维数据查询的支持不是很好。当前P2P处理高维数据的主流方法是降维和空间填充技术,但两者均有很明显的缺点。针对这些问题,提出一种将树型结构——Baton树应用于高维数据检索的方法,操作简单,无须降维,且支持范围查询。经过实验证明,查询的时间复杂度达到O(log2n),与Baton树在检索一维数据时的效率相同。树型结构可以增加子节点数量,通过增加扇出的方式,减少时间开销,理论上可以使时间复杂度降低为O(logmn)。
The routing algorithms based on DHT couldn＇t support range query in P2P system, so they were hard to support high dimensional data query. At present the conlmon method to handle high dimensional data were dimensionality reduction and space-filling,but both of them had obvious disadvantage. This paper proposed a method based on Baton tree structure to handle these problems, easy operation, without dimensionality reduction, and support range query. Prove by experiment, the time complexity cost on querying is O（ log2 n） , same as the Baton tree handle linear data. At last, the tree structure can increase it＇ s children nodes to increase fan-out,make the time complexity down to O（log,,,n） in theory,will be researched next.
出处
《计算机应用研究》
CSCD
北大核心
2015年第3期842-845,共4页
Application Research of Computers
关键词
树型结构
高维数据
检索
范围查询
tree structure
high dimensional data
search
range query
