论文部分内容阅读
随着RFID、无线网络等物联网技术的快速发展,产生了大量的移动对象数据。移动对象一般都具有多维属性和时空特征,移动对象之间进行通信形成了移动对象网络。如何处理和有效利用移动对象产生的海量数据,以及如何对移动对象网络进行仓库化和联机分析处理成为当前的研究热点。在移动对象网络中找出包含特定信息的子结构是非常有价值的,对图进行结构数据查询,现存的查询分析算法已经很多,但是这些算法大部分是为静态数据所设计的,而对于类似移动对象产生的移动数据来说,这些算法很难发挥作用。因此本文在移动对象网络上对结构数据联机分析处理进行了深入的研究。另一个重要的问题是在构建移动对象图立方体的过程中产生的大量浓缩图,这些浓缩图不同于传统的数值数据,它们包含大量节点且具有复杂的结构,需要大量的存储空间。对这些浓缩图数据进行分析和处理需要花费较多的时间。如何对这些浓缩图数据进行压缩成了急需解决的问题,本文对移动对象网络的浓缩图数据做了深入的研究,高效地压缩了浓缩图的节点和边,为用户对移动对象数据进行分析处理提供了有效的帮助。论文的主要贡献和创新点如下:1)针对移动对象产生的大量图结构数据,我们提出了一种新型的图立方体模型,来有效地在移动对象网络上进行OLAP查询。同时考虑到顶点属性的聚集和网络结构的概化,图立方体超越了只包括基于分组的传统的数值数据立方体模型,从而产生了许多有意义的结构丰富的浓缩网络。2)与传统的立方体查询不同,本文采用一种新的OLAP查询,叫做muti-boid查询,这种查询可以应用在移动对象网络中。我们通过结合移动对象网络的特点和现存的研究数据立方体技术实现了图立方体的穿立方查询。3)针对大规模移动对象网络在构建图立方体的过程中产生的大量浓缩图,引入了图压缩的思想,提出了进一步压缩浓缩图的算法MC-compress,用来合并浓缩图中顶点及其相对应的边。通过将图中相邻的两个顶点进行合并,再比较两条边合并后权重的最大差异度,从而找出最优的合并顶点对,最终产生构建压缩图的超级顶点和超级边。通过压缩图结构,加快了在图立方体上查询图结构的显示过程,减少了构建图立方体过程中存储大量浓缩图的空间。4)针对多维对象网络在用户不同的兴趣维度上产生的大量浓缩图。引入了图索引的思想,提出了结构化数据查询算法MCPath,用来解决用户在某个维度上对感兴趣的结构数据进行查询的问题。MCPath算法通过将图分解成最短路径集,再将这些候选路径进行进一步连接,最终构建为需要查询的结构数据。从而将原来每次只对一个节点进行一次查询的方法,变成更为有效的一次查询一个路径的方法,减少了对结构数据进行查询的次数,加快了对结构数据进行查询的速度。