一种全新的R树节点选择算法

在 R树插入算法中采用全新的节点选择算法 ,一改传统的从根节点开始自上而下的节点选择方案 ,而是从叶节点层开始 ,先自下而上再自上而下地选择叶节点 ,较好地解决了同层节点重叠所导致的查询效率低下的问题。实验证明 ,提出的 R树空间索引方法 ,不仅在查询效率上明显优于 R*树,而且 R树生成的时间开销也减少了 50%左右 ,综合性能超过了 R*树 ,便于扩展到三维甚至多维空间中 ,以实现对空间数据和时空数据的高效查询功能。     

一种支持多维区间查询的云对等网络索引架构*

针对用户在大规模云对等网络环境下多维区间查询问题,将基于m叉平衡树的索引架构引入到云对等网络环境下,在该架构上实现集中式环境下支持多维数据索引的层次化树结构,例如R树,QR树等。多维区间查询算法保证查询从树的任意位置开始,避免了根节点引起的系统性能瓶颈问题。通过计算和实验验证,对于N个节点的网络,多维区间查询效率为O(logmN)(m>2)(m表示扇出),由此可见,查询效率和维数d无关,查询效率不会随着维数d的增加而降低。最后建立基于扇出m的代价模型,并且计算出了最优的m值。     

基于KDB树的RFID事件聚合过滤算法

分析RFID中间件查询数据的特点,提出一种对查询数据聚合转换的方法,减少查询索引的存储空间和数据插入时间。分析和比较已有多维查询索引的各方面性能,将多维索引KDB-tree应用到RFID中间件中。实验结果表明,KDB树索引在存储空间成本、数据插入成本和查询时间成本3个方面的综合性能最佳,在点查询上,KDB-tree只须单路径遍历索引树,数据查询时间少于其他方法。     

三维激光点云数据的可视化研究

大量的点云数据是通过三维激光扫描得到的,而点云数据的显示快慢受到了数据索引的直接影响,这是一个基础性问题。经过研究,八叉树与叶节点KD树相结合的混合空间索引结构以及LOD构建的层次细节模型是用来解决点云数据管理与可视化效率不高的问题的有效方法。在局部,通过在叶子节点中构建的KD树实现高效的查询和显示;在全局,为了实现快速检索与调度使用了八叉树模型。采用这种混合数据模型进行点云组织,建立空间索引,并对点云数据进行LOD构建,实现了点云数据的高效检索以及可视化。     

基于Spark的3D点云数据空间索引技术

针对Spark引擎不支持多维空间查询的问题,提出基于R树的二级空间索引,即在每个Worker节点上创建R子树,并将这些子树作为孩子,在Master节点上创建R树。针对LRU算法内存替换粒度粗、结果不够精确的问题,提出基于数据使用权重的内存替换方法。该方法将每次实际使用数据量与其总量的比值作为替换权重,将热点场景数据以RDD形式持久化至内存中,提高了基于内存查询的效率。根据远粗近细的视觉原理提出细节层次查询,该方法 将最能代表物体特征的点云数据先传输给客户端,或者仅把简化模型点数据传给客户端,以解决网络带宽不足和数据加载延迟的问题。实验证明,文中方法能有效解决Spark多维空间的查询问题,查询效率得到了明显提高。     

KDT树:一种多维空间数据索引结构

通过扩展KD树索引结构,提出了一种新的多维空间数据索引结构——KDT树,给出了数据结构和算法描述,并通过与当前流行的空间数据索引结构——R树的对比,对其性能进行了测试与评估。实验表明,作为一种主存索引结构,KDT树在时间效率方面明显优于R树,并且此种优势随着索引记录数量的增多而越加明显。此外,KDT树亦能较好地解决常规KD树在索引占据一定空间范围的空间对象(如:线、面、体等)时存在的问题。     

基于CURE聚类算法的静态R树构建方法

R树索引结构在空间对象查询和复杂空间关系查询方面具有重要作用。传统空间索引结构R树是动态生成的,树的结构是根据连续插入算法实现的,通过分裂子节点直至生成R树的根节点。动态生成算法会导致R树节点最小外包矩形之间的大量重叠,影响空间查询效率,且空间利用率不高。为了弥补动态生成R树的不足,提出了基于CURE算法的静态R树生成方法,给出CU_RHbuilt建树算法,该算法不仅能有效地处理海量数据,识别任何形状的簇,减少矩形重叠度,而且采用划分技术可较大程度地减小计算代价,空间利用率较高。进一步提出了基于CURE算法的R树节点分裂方法。理论研究与实验表明,所提方法具有较高的查询效率。     

海量3D点云数据压缩与空间索引技术

针对3D模型中海量点云数据压缩与空间索引低效问题和漫游过程中相邻两次查询窗口重叠是大概率事件问题,提出邻点差值渐进压缩和基于裁剪重叠区域进行冗余处理的R树空间索引方法。首先,利用八叉树对3D模型进行空间剖分,借助Morton码对每个叶节点管理的点云数据排序,按照R树叶节点的外接立方体大小对数据进行分块,计算块内相邻点数据差值,以块为单位渐进压缩差值,批量读取这些数据块创建R树;其次,借助上次查询窗口范围计算本次查询有效范围;最后,给出基于R树索引的点云数据查询方法。该方法使点云数据压缩率提高了26.61个百分点,并能实现流式传输,同时减少了I/O开销,使其查询性能提高了35.44%,数据冗余减少了16.49个百分点。实验结果表明,所提方法在3D虚拟旅游、数字城市等系统具中有明显优势。     

基于HBase的支持频繁更新与多用户并发的R树

基于位置服务的应用已经进入大数据时代,传统基于位置服务的技术面临系统扩展性、性能等方面的挑战。云计算技术是大数据处理的基础,索引是优化查询的重要手段。尽管目前已存在大量的研究成果,但尚未有HBase上的支持频繁更新与多用户并发的R树索引。针对移动对象索引的频繁更新与多用户并发的需求,文中提出了基于HBase的支持频繁更新与多用户并发的R树索引,它只索引包含移动对象的网格,避免了频繁更新问题;进一步基于HBase的数据行与数据分区的组织与读写特性,对R树的节点进行重组,并对网格Z-order编码,从而减少了对HBase的读写操作,提高了查询效率;最后提出了基于ZooKeeper分布式读写锁的优化策略,提高了索引的吞吐量。实验结果表明,与网格索引相比,在数据非均匀的情况下,所提策略的查询吞吐量提高了25%～50%,更新吞吐量约在同一数量级;与分布式共享锁索引相比,分布式读写锁索引的吞吐量提高了近40%。     

基于双层索引结构的起源图查询方法

为解决现有的起源图查询效率低和资源占用率高的问题,考虑起源信息和数据本身之间的关联关系以及起源信息内部结构特点,提出了一种基于双层索引结构的起源图查询方法。首先,面向起源图查询,提出了一种包括基于词典表全局索引和基于位图局部索引的双层索引结构,全局索引用于查询起源图所存储的服务器节点,局部索引用于对全局索引查询到的服务器节点细化查询;然后,基于双层索引结构,设计了一种起源图查询方法,针对6种选择索引和3种join链接索引实现了查询算法。实验结果表明,所提方法既提高了查询效率,又降低了内存资源的浪费。     

基于云模型的实数编码量子进化算法

针对量子进化算法易陷入局部最优和求解精度不高的缺点,利用云模型具有随机性和稳定倾向性的特点,提出了一种基于云模型的实数编码量子进化算法。该算法利用单维云变异进行全局快速搜索,利用多维云进化增强算法局部搜索能力,探索全局最优解。依据算法的进化过程动态调整搜索范围并复位染色体,可以加提高敛速度,并防止陷入局部最优。仿真结果表明,该算法搜索精度和效率得到提高,适合求解复杂函数优化问题。     

一种散乱分层点云的有序化精简方法

针对激光扫描仪所得点云散乱分层的特点,提出一种有序化的精简方法。首先基 于已知标记点建立三维R-tree 和八叉树集成的空间索引,快速准确地获取局部点云数据,保证 良好的数据检索效率。然后根据局部点云数据的参考平面法向量信息,选取工件坐标系中的一 个坐标轴作为参数化的方向,对局部点云数据进行参数化并拟合二次曲面。最后对R-tree 叶节 点内的二次曲面进行有序化采样,使散乱分层的点云变为单层,得到整个型面的有序参考点集。 应用实例表明,该方法适用于大规模的、具有复杂几何特征且存在一定程度散乱分层的点云, 可以有效地提高数据点的整体精确度,且不会丢失点云的细节特征,具有较强的实用性。     

多关键字云资源搜索算法

云计算的核心是在虚拟化技术的基础上,通过互联网技术为用户提供动态易扩展的计算资源。利用中心服务器的计算模式来管控网络上大量云资源使得中心服务器成为整个系统的瓶颈,不利于云计算的大规模应用,因此提出使用对等网络技术构建分布式的云资源索引存储和查询系统,但是结构化拓扑系统维护比较复杂,一般不支持复杂搜索条件查询。本文提出了一种多关键字云资源搜索算法。在基于分层超级节点的云资源搜索算法基础上进行路由算法改进,希望实现多关键字的精确查询。对多关键字的生成、分割及存储做出了详细说明,提出一种有效的基于数据集的索引搜索策略,实现了包含三个或三个以上的关键字高效、准确查询。分析实验结果证明了算法明显提高了资源搜索的命中率,尤其是随着关键字数目的增多,不仅保证了资源搜索的命中率,同时大大增加了资源的召回率。     

基于安全性能接口的调度和管理模型研究

以云计算效能提高为目的, 以研究Job调度和资源管理两大决定云计算环境能效的最重要因素为基础, 使用调度和管理对象对作为系统统计信息的参考指标进行采集的方式展开研究。性能代理和服务接口模式(PASI)已经从云环境中采集了原始数据, 通常情况下应用于云的安全技术属于被动防御模式, 如实时动态监控或者深度包检测模式(DPI), 其主要目的是实现动态检测和防御。提出了一个有效的框架以提高云计算中心的综合性能指标, 该架构的建立是基于PASI与DPI相结合的方式, 并且提出了一个基于安全PASI的Job调度和资源管理模型(JDRMSP)。实验结果表明, 该模型有效地提升了云环境的整体运作效能。     

虚拟旅游中海量3D点云数据的细节层次索引技术研究

虚拟旅游中的3D点云数据特别庞大,批量索引成为了当今的研究热点。许多索引树存在兄弟结点空间区域重叠、不能实现细节层次索引、索引效率低等问题。为此,将点数据反射强度和细节层次技术引入R树,在改进R树的基础上提出LODR树。建树前,将点云数据进行排序、分组、去除空间重叠等预处理。树的每层设有不同反射强度阈值,把叶结点中满足阈值条件的索引记录沿父-祖父-曾祖父的家谱关系上移,并插入对应的非叶结点,利用该方法创建细节层次索引树。利用反射强度控制数据冗余,棱锥裁剪技术实现查询优化。实验结果表明,LODR树在细节层次索引、查询效率等方面具有明显优势。     

Verifiable searchable symmetric encryption for conjunctive keyword queries in cloud storage

Searchable symmetric encryption (SSE) has been introduced for secure outsourcing the encrypted database to cloud storage, while maintaining searchable features. Of various SSE schemes, most of them assume the server is honest but curious, while the server may be trustless in the real world. Considering a malicious server not honestly performing the queries, verifiable SSE (VSSE) schemes are constructed to ensure the verifiability of the search results. However, existing VSSE constructions only focus on single-keyword search or incur heavy computational cost during verification. To address this challenge, we present an efficient VSSE scheme, built on OXT protocol (Cash et al., CRYPTO 2013), for conjunctive keyword queries with sublinear search overhead. The proposed VSSE scheme is based on a privacy-preserving hash-based accumulator, by leveraging a well-established cryptographic primitive, Symmetric Hidden Vector Encryption (SHVE). Our VSSE scheme enables both correctness and completeness verifiability for the result without pairing operations, thus greatly reducing the computational cost in the verification process. Besides, the proposed VSSE scheme can still provide a proof when the search result is empty. Finally, the security analysis and experimental evaluation are given to demonstrate the security and practicality of the proposed scheme.     

Android智能手机的云服务应用研究

云计算的应用目标并不仅局限于PC,随着移动互联网的蓬勃发展,基于手机等移动终端的云服务已成为IT行业炙手可热的新业务发展模式。本文基于Openmobster搭建移动云计算环境,并利用Android智能手机作为终端来访问云端服务器资源,以数据传输的事务处理为应用背景,采用c／s模式和B／S模式相结合的方式,建立了云服务下移动智能终端信息采集和处理的基础架构,并根据此架构初步实现了追踪定位的功能。该方法通过无线网络连接,利用服务器端与手机客户端的即时通信,实现了为Android智能手机提供云推送和云同步的服务。     

云框架下的WMS服务实现研究

传统WMS服务基于集中或者离散分布B/S模式,单台服务器既要承担地图发布的任务,也要承担地图绘制的任务,当大量客户端并发访问服务器时,服务器响应速度明显降低甚至宕机。针对传统WMS服务模式的不足,将WMS服务构建于自主开发的云平台之上,详细阐述了实现的关键技术,包括WMS云服务框架的设计、空间数据的组织方法和任务调度策略。并且对B/S模式和云模式下的WMS服务性能进行了测试,证明了在同等服务器硬件环境下,云模式的WMS服务具有相对较高的处理效率,其研究具有十分重要的实践应用价值。