面向大数据库正则表达式查询的有效算法

针对大数据库中正则表达式查询,提出了一种基于索引的有效算法。首先,构造索引。该索引结构在前缀树基础上加以改进,为每个节点创建二维数组存放该节点所辖子树各层的首次关键节点,并对每个节点附加关键节点指针以指向同层的下一关键节点。然后,通过所提出的索引结构进行查询。最后,分析了所提出算法的时间和空间复杂度,并进行了实验。实验结果证明:随着数据集的增加,其查询时间和输入/输出(I/O)时间增长速度较缓慢,说明其可扩展性较好,适合于大数据库中正则表达式查询。并且,随着查询字串的增加,查询时间与I/O时间均呈递减趋势,证明了该算法的效率和有效性。     

基于数据广播的空间关键字查询处理

为了解决无线广播环境下空间关键字查询的问题,研究广播环境下空间关键字k近邻查询处理(BkSKQ),设计了一种结合kd树、倒排位图和(1,m)索引机制的空间关键字索引(ISKW)结构,以有效地组织对象的关键字信息、位置信息以及索引信息.该索引结构为客户的查询处理提供有效的指导,使得他们尽可能只下载查询处理所必须的数据信息.在ISKW索引结构的基础上,提出了BkSKQ查询处理算法.最后,通过模拟实验验证了提出的索引结构和算法的性能,实验结果表明所提出方法在访问时间和调谐时间上明显优于基于IR树的方法(BIRM).     

大数据环境下Lucene性能优化方法研究

为提高大数据环境下的数据查询分析效率,该文结合内存计算技术和批量更新技术提出一种优化倒排索引方法——内存磁盘索引(RFDirectory)。基于Lucene实现内存和磁盘相结合的倒排表管理技术。将新增数据写入缓存中,并周期性地写入磁盘索引结构中,从而提升倒排索引的写入性能。通过整合磁盘和内存的多分块倒排结构,为用户提供高效的数据查询分析结果。实验结果表明:在大数据环境下,RFDirectory方法的索引构建时间缩短为磁盘索引(FSDirectory)、内存索引(RAMDirectory)方法索引构建时间的50%,返回1个关键字的检索结果耗时缩短了近15%。     

并行查询中的索引并行化技术

提出一种新的索引并行化技术，利用多处理机来提高建立在B树结构上的索引性能，并提出了一种改进的B树结构－FALNB树，基于该树结构，以大结点B树方式在多个处理机上分布索引数据，通过动态调整算法快速进行调整，取得很好的负载平衡效果，给出了时间分析模型，实验结果显示FALNB树能加快查询响应速度，对海量数据的索引有良好性能。     

用于RFID中间件的主存数据库索引结构

根据EPC Global标准,提出了基于RFID数据特征的网格索引结构.该索引结构针对RFID应用场景设计,不仅能实现高效的插入、查询以满足实时性的需求,还能够提高内存的利用率,节省内存.与传统索引相比,提出的索引结构能够完全适用于真实的RFID应用场景,实现条件查询、范围查询等其他传统索引很难实现的操作.可以减少内存消耗,提升条件查询,范围查询的速度.实验结果证明基于RFID数据特征的网格索引不但在插入效率上不亚于传统索引,而且在条件查询,范围查询的效率远远高于其他传统索引结构,并且内存占用率也具有一定优势.     

基于大页内存的学习索引内存分配策略

大数据时代,数据信息的不断膨胀给数据的快速存取带来了巨大挑战.因此,设计一种高效的索引结构具有重要意义. ALEX (updatable adaptive learned index)是一种利用机器学习模型代替传统B-树索引结构的学习索引,具有较好的时间、空间性能,但存在频繁的缺页中断问题.为解决此问题,进一步提升ALEX性能,在ALEX基础上提出了一种基于大页内存的内存预分配策略,较好地降低了内存缺页中断率,提升了ALEX性能.在内存分配阶段,采用预分配策略;在内存回收阶段,则采用延迟释放策略.在Longitudes数据集上的实验表明,该策略具有良好的效果.     

XML文档结构索引的更新维护

xml作为一种数据表示方式,越来越为人们所接受.最近,基于xml/半结构化数据的索引的查询引起了人们的广泛关注.有人提出来用结构索引来支持基于xml/半结构化数据的查询.由于xml/半结构化数据的结构不严格、不规则,结构索引会随着数据的增加或删除而变化,维护结构索引就成了首要问题.本文研究了在xml文档集合上增加多个文档和删除一个文档时结构索引的更新,提出了在这两种情况下的索引维护算法,这两种算法比现在已知的其它算法的性能要更优秀.     

LBS大数据中基于固定网格划分四叉树索引的查询验证

基于位置的服务(LBS)进行数据发布时,数据拥有者委派第三方服务商来发布数据,服务提供商代表数据拥有者向用户提供服务。但是LBS中的服务提供商可能是不可信的,这样会在LBS大数据的查询中形成由于商业目的而篡改的不准确的结果。LBS大数据中移动对象的位置随时间而变化,因此数据的动态性导致了索引结构大量的更新操作。该文提出了一种基于固定网格划分四叉树索引机制的空间范围查询验证技术,该技术采用网格划分的方法对空间数据进行划分,并采用四叉树对划分后的网格进行索引。该空间索引结构更新代价低,方便了数据的管理,缩短了检索的时间,四叉树索引对于范围查询具有较高的查询验证效率。该方法确保了用户查询结果的真实性、完整性和正确性。通过实验验证了该方法是有效的。     

时态XML索引Txmlsindex

时态XML数据操作的基本途径是相应时态索引模式,而时间信息与结构信息的整合协同是涉及索引效率的关键技术.该文研究了一种基于时态拟序和时态编码协调的时态XML快照索引Txmlsindex,实现了“一次一集合”的时态数据查询和基于Tcodes编码的结构信息重置;比较评估Txmlsindex的可行性与有效性;提出的技术框架和索引模式还可拓展到时态XML的一般查询过程当中.     

GICDBS:一种支持动态图结构数据更新的索引方式

提出一种基于CDBS编码的索引方式-GICDBS,并详细阐述了其对图结构数据动态更新的支持.实验证明,GICDBS索引结构不仅可以实现线性的可达性查询时间效率和索引空间复杂度,而且能够有效地支持数据的动态更新.     

一种基于DTD的不完全值索引结构

索引结构是影响查询性能的一个重要因素,目前出现的索引结构主要存在以下几个问题:1)不能有效支持带有谓词约束条件的分支查询;2)只能在小文档上进行测试或者建立的索引文件比较大.为了解决这些问题,提出了一种基于DTD结构的不完全值索引方法——DBPVI(DTD-based Partly-Value XML Indexing).实验证明,该索引方法能在不影响查询性能的前提下,很好地解决上述问题.     

基于小波和动态时间弯曲的时间序列相似匹配

提出了一种基于小波和动态时间弯曲(DTW)距离的时间序列索引和相似匹配方法. 该方法采用小波变换进行数据降维,利用R·-tree建立多维索引结构. 给出了查询序列的DTW距离边界和其在小波空间的查询超矩形的计算方法,从而将原始空间的基于DTW距离的相似匹配转换为小波空间基于欧氏距离的相似匹配. 证明了此匹配方法不会产生漏报,给出了基于DTW距离的范围查询算法和近邻查询算法. 实验结果表明该方法具有较高匹配精度和其较低的计算代价.     

PR-tree:P2P环境下一种多维数据的分布式索引结构

提出了一种基于R-tree的更适用于P2P环境的新型多维空间索引结构———PR-tree,并且在这种新型的索引结构下进行了高维数据的查询操作.这种新型的空间索引结构有两个主要的特点:对需要查询的数据空间进行层次划分;并且对结点的插入、删除等操作具有高度的灵活性.实验表明这种新型的空间索引结构在查询效率等方面都优于其他的索引形式.     

分布式时态索引DTindex

研究基于线序划分（LOP）分布式时态索引技术DTindex．首先,建立DTindex所需数据结构和算法,并讨论分布式时态数据索引DTindex;其次,针对时间数据LOP结构提出基于查询期望的数据分布算,依据DTindex两层索引架构提出P2P部署以减少系统的通信开销．另外,完成仿真以表明索引可行性和有效性．     

基于Spark/Shark的电力用采大数据OLAP分析系统

用电信息大数据上的OLAP查询涉及数据量大,具有多表连接操作频繁、SQL结构复杂等特点,传统关系型数据库面对该类应用,表现出可扩展性弱、数据写入吞吐量低与查询效率低等问题.为此设计了一套基于Spark/Shark的电力大数据OLAP分析系统,该系统采用分布式文件系统HDFS保存电力用电信息采集系统的大数据,通过Shark进行前端SQL解析,Spark进行查询计算;然而,原生Shark只支持粗粒度分区,不支持细粒度的索引技术,难以高效地过滤无关数据,影响了查询性能.为克服这一不足,该系统设计了一种基于前缀树的细粒度索引结构TrieIndex,并通过数据重组技术优化了数据在HDFS的分布,提升了Shark的数据过滤能力以及用电信息大数据OLAP分析的性能.真实用电信息采集系统数据与查询的实验结果表明,该系统比关系型数据库的写入速度提升了12倍,比原生Shark的查询效率提升了10倍以上.     

一种社交网络环境下并行短文本查询算法

随着移动社交网络的迅速发展,如何从海量带有时间属性和地理位置属性的短文本信息中快速查询到有效信息具有重要意义.社交网络环境下传统短文本查询算法忽略时间维度,并且在海量数据下无法满足用户快速响应的需求.针对以上问题,提出一种社交网络环境下并行短文本查询算法.提出的算法设计了基于MapReduce模型下的查询框架,该框架使用了基于滑动窗口下的多版本时空索引(MVSTR-tree),保证了查询过程中融合了时间和空间属性,实现了对海量数据高效查询的目标.最后,通过真实数据集的实验证明该算法能有效缩短查询时间.     

QGrid:一种空间移动对象并行索引结构

为提高空间移动对象数据更新效率和查询准确率,提出了一种空间移动对象并行索引结构.利用主索引和辅助索引支持对空间对象进行基于范围的查询和基于对象标识的查询,还通过查询索引将更新操作和可能受其影响的查询操作相连接,在满足并行操作时间片语义的同时,避免了传统方法进行范围查询时对查询范围内相关对象及相关索引结构全部进行锁定的需求.实验结果表明:高负载环境下,该索引结构不但能保证查询准确率,其处理能力也明显优于传统索引结构.该索引通过提高系统并行度,使同一范围内的更新和查询操作可以并行执行,提升了系统整体运行效率.     

基于分布式平台Spark的空间文本查询分析

随着基于位置服务应用的不断推广,空间文本数据查询的应用价值(例如结合地理位置和用户标签的社交推荐)也在不断提高.但是,随着数据规模的迅速增长,传统的基于单机环境实现的技术难以为用户提供低延时和高吞吐量的服务.为此,本文基于Spark平台对分布式环境下的空间文本查询算法进行了探究.采用了面向海量空间文本数据的两层索引框架(包括全局索引和局部索引),该框架利用了分阶段过滤的策略来处理分布式下的布尔范围查询问题.同时,针对空间文本相似连接提出了Prefix-RI结构并提出了相应的分布式算法.基于Spark平台实现了所提出的分布式算法,并通过大量的实验对比验证了所提出方法的优越性.     

基于用户偏好的最优路径搜索

本文研究基于用户偏好的最优路径搜索,在预算约束下寻找一条满足用户偏好即关键字和权重偏好的最优路径.此研究问题是NP-hard.为了高效地解决这类查询问题,本文提出新的索引建立方法,在查询阶段利用索引结构过滤出候选节点集.另外,提出基于A*的路径搜索算法来做路径查询,并利用几个有效的剪枝策略加快算法的执行速度.在两个真实的签到数据集上的实验结果证明了本文提出方法的有效性.当预算时间设置为4～7h时,与已有最好的PACER算法相比,本文的路径搜索算法消耗的查询时间更短.     

数据库系统中一种更安全的加密机制

针对数据库中数据的保密性问题,分析了目前已有的一些加密机制,提出了一种基于密文索引的新的查询方法.此方法在查询速度上比全表或属性段脱密的方法快,在保密性上解决了基于密文索引的查询方法所存在的信息泄漏问题,并指出了基于密文索引的数据库加密机制需要进一步研究和解决的若干问题.