【作者】 刘宇；

【导师】 宋宝燕；

【作者基本信息】 辽宁大学 ， 计算机软件与理论， 2016， 硕士

【摘要】 在大数据和互联网的飞速发展下,国民经济中各行各业积累了呈现指数级增长态势的数据,特别是如网络交易数据、用户评论数据等具有高维特征的高维大数据,这些数据不仅数据量大,而且结构复杂。高维大数据兼具高维数据和大数据的典型特征,传统的高维数据存储和索引技术难以满足数据量扩展的需求,而传统的大数据存储和索引技术难以应对维度过高时出现的“维度灾难”。针对高维大数据的特点,提出了一种适合于高维大数据的存储结构和索引结构,并在索引结构之上提出了相应的查询处理算法,进而构建Hadoop平台上测试算法的性能。首先,针对高维大数据的存储结构,通过使用US-ELM-FC聚类算法使得相关性较强的维度被聚类在一起,从每个聚簇中选出关键维,使用关键维来代表整个聚簇,相当于降低高维大数据的维度,同时减少数据之间的相关性和冗余,即在保持数据本身特性的前提下减少数据的维度和冗余；并对关键维和非关键维进行垂直划分,将关键维存储在HBase中,将非关键维存储在HDFS中,按照HDFS块的大小对其进行水平划分和压缩存储,构建出本文提出的高维大数据的存储结构(HB-File).其次,依据US-ELM-FC算法的聚类结果,将聚类划分出的高维大数据关键维构建索引,通过可变网格单元对数据空间进行划分,划分后对整个数据空间进行子空间合并,使每个子空间上的数据元素相对平均,在合并后的子空间上构建M-Tree形成局部索引,再通过子空间之间的位置关系构建全局索引,形成一个基于可变网格的分布式二级索引结构(VGHI).然后,在这个索引结构上,提出了相应的查询处理算法,通过全局索引中的位置信息对查询请求进行定位,判断出查询涉及的子空间所在的节点,然后在各个节点上并行进行查询处理,并返回最终结果。最后,通过在不同数据量和不同维度的数据集上的大量实验结果表明,该存储模型和索引结构适合于高维大数据的存储和索引,能够对高维大数据进行更有效,更具拓展能力的存储和索引。更多还原

【Abstract】 With the rapid development of big data and Internet, the economy in all walks of life gained exponential growth of data, such as network transactions, user reviews, and other high-dimensional data having a large high-dimensional feature data, which not only are huge but also have complex structure. High-dimensional big data have both typical characteristics of high-dimensional data and big data. The traditional high-dimensional data storage and indexing technology can not meet the needs of data expansion, while the traditional big data storage and indexing technology do have difficult to deal with excessive dimensions that is called "curse of dimensions".According to the characteristics of high-dimensional big data, we proposed a suitable storage and indexing techniques for high-dimensional big data, and proposed corresponding query algorithms over the index structure. All the implements are built on Hadoop platform.Firstly, According to the US-ELM-FC clustering algorithm,the dimensions with strong correlation are clustered together. The key dimensions are selected from each cluster. Using a key dimension to represent the corresponding cluster, which can be seen as reducing dimensions and reducing data redundancy/correlation between dimensions but maintaining the characteristics of the data itself. After that, we divided the key dimension and non-key dimension vertically; the key dimensions are stored in HBase, and the non-key dimensions are stored in HDFS. According to the HDFS block size, we horizontal partitioned the data and stored the data after compression. Then it has been built the storagestructure for high-dimensional big data called HB-File.Secondly, we construct a index structure based the cluster result of US-ELM-FC algorithm. We divided the data space by variable grid, and merged the data grid into a data subspace. After the division and merge, the data elements of each subspace are relative to the average, then built M-Tree index on each subspace and formed the local index, and built the global index by the positional relationship between different subspaces, then the local index and the global index formed a variable gird based distribution two layer index structure called VGHI.Then, on the above index structure, we proposed the corresponding query algorithms. The core idea of all the algorithms is to locate the query by the position information of global index and to determine which subspaces are the query-related, then forward the query to each related node and execute the query on each node and return the final result.Finally, a large number of experiments on experiment data set with different data size and different dimensions show that the storage model HB-File and the index structure VGHI are suitable for high-dimensional big data storage and indexing respectively. HB-File and VGHI are both efficient and scalable for high-dimensional big data.更多还原