基于数据映射算法的近邻存储方法研究

随着互联网的高速发展，如何有效地存储海量数据以提供高效的查询效率是一项亟待解决的关键问题。

随着互联网的发展越来越快，海量数据指数级增长的时代已经到来。海量资源的爆炸式的增长，对于现有的存储系统是一个极大的考验。面对高维、海量的数据，如何有效地存储海量数据同时能够高效的查询到有效的数据信息是一个值得研究的问题。

为了更高效的解决海量数据下存储问题，分布式存储应运而生。主流的分布式存储技术是P2P 系统[1]。根据P2P 技术的点对点和分布式特点，将其加入到云存储系统中，有效地解决集中式云存储系统的中心服务器瓶颈问题。将数据分布式的存放在各个节点服务器上，减轻了节点服务器的负载，实现了云存储系统的负载均衡，从而提高了系统硬件的使用率，大大提高了系统的存储性能。在主流的P2P 存储网络中，存储数据在DHT 中的哈希值Key 由相应的哈希函数获得，然而哈希函数为了保持网络的负载均衡会破坏资源的语义相关性[2]信息，如MD5，因此大部分P2P 系统只支持单关键字的精确查询[3]， 不能支持语义相关性查询[4]。面对海量数据时，查全率低，节点切换开销变大，导致网络拥堵，造成系统的存储效率和查询效率会大大降低。为了解决分布式存储系统中存储数据语义相关性低和查询效率低等问题，本文提出了基于数据映射算法的近邻存储方法[5]。

2. 相似性度量方式 无论在原始欧式空间还是在汉明空间都需要去衡量两个数据之间的相似性[6]。数据间的相似性需要通过一定的方法进行度量，相似度是衡量两个对象之间相似性的指标[7]，取值在[0,1]之间，目前常用的相似性度量方法主要有余弦相似度、海明距离、Jaccard 相似度、Minkowski 距离、马氏距离、负指数法及正切值法： 假定有一些点组成的集合称为空间(space)，该空间下的距离测度(similarity measure)是一个函数(), d x y ，以空间两个点, x y 作为参数，输出是一个实数值。该函数必须满足如下准则： (1) (), 0d x y ≥ (距离非负)； (2) (), 0d x y =当且仅当xy= (只有点到自身的距离为0，其他距离都大于0)； (3) ()(), , d x yd y x= (距离具有对称性)； (4) ()()(), , , d x yd x zd z y≤+ (三角不等式)。

三角不等式是上述条件中最复杂的条件。它的直观意义是，如果从x 点行进到y 点，那么一定不存在第三点z 使得途径z 的距离更近。三角不等式准则使得所有的距离测度表现如同其描述，为从一个点到另一个点的最短路径长度。

(1) 海明距离 海明距离(Hamming Distance)， 是一种衡量两个二进制编码序列之间的相似度的指标。

给定12, bbvv两个长度为L 且是任意的二进制向量，其海明距离定义为两者对应位置上的不同编码值的个数，即式(2.1)：