云环境下一种隐私保护的高效密文排序查询方法
摘要：数据前端加密是保护云环境下外包数据隐私的一种有效手段，但却给数据查询等操作带来挑战．针对云环境下多数据拥有者数据外包及选择性访问授权特征，为支持大规模加密云数据上高效且隐私保护的用户个性化密文查询，文中提出了一种隐私保护的高效密文排序查询方法RQED．通过设计无证书认证的PKES（支持关键词检索的公钥加密），并构建RQED框架来实现强隐私保护的密文查询．基于该框架，设计了更合理的多属性多关键词密文查询排序函数，并提出了基于层次动态布隆过滤器的RQED索引机制，提高密文查询时空效率．理论分析和实验性能对比证明：RQED在确保查询强隐私保护和高准确性的同时，具有较明显的时空效率优势．基于LSH的时间子序列查询算法
摘要：子序列的相似性查询是时间序列数据集中的一种重要操作，包括范围查询和k近邻查询．现有的大多算法是基于欧几里德距离或者DTW距离的，缺点在于查询效率低下．文中提出了一种新的基于LSH的距离度量方法，可以在保证查询结果质量的前提下，极大提高相似性查询的效率；在此基础上，给出一种DS—Index索引结构，利用距离下界进行剪枝，进而还提出了两种优化的OLSH—Range和OLSH—kNN算法．实验是在真实的股票序列集上进行的，数据结果表明算法能快速精确地找出相似性查询结果．空间数据上Top—k关键词模糊查询算法
摘要：基于位置的服务（LBS）变得日益普及，越来越多的研究开始关注如何对空间中的兴趣点（POD做有效的检索．现有的方法提出了空间数据上的关键词检索，研究如何根据查询的位置和关键词找到相关的POI点．然而，现有方法主要对查询关键词进行精确匹配，不能支持模糊查询：当查询关键词与底层数据存在微小差异的时候，LBS系统不能返回相关的结果．为了满足移动用户的模糊查询需求，文中对空间数据上的Top—k关键词模糊查询问题进行研究：给定一组POI点，检索与查询关键词近似匹配且空间上距离相近的Top—k个结果．为了提供高效的模糊查询，文中首先定义了一种新型的相关性函数，综合考虑了文本相似性和空间距离，进而提出了一种有效的索引结构RegionTrie，并基于RegionTrie设计了高效的Top—k算法．真实数据集上的实验结果表明，文中提出的Top一^算法十分高效，性能远好于对比方法．时间依赖代价函数下的最优路径查询问题研究
摘要：作者研究了时间依赖图下，具有时间限制的费用代价最优路径的查询问题．目前有关时间依赖图上的最短路径查询的研究工作解决的是最短旅行时间问题（TDSP），这些工作都利用了以下性质：到达某个顶点的最早时刻可以通过到达其邻居的最早时刻计算得出．然而，在计算具有时间限制的费用代价最优路径时，该性质并不成立．因此，目前解决TDSP问题的方法均不能解决文中面对的问题．对此作者提出一个新的算法用于计算时间依赖图模型上的满足时间限制的费用代价最优路径．该算法适用于有向图和无向图．作者证明了算法的时间复杂度和空间复杂度分别为O（knlogn＋mk^2logk）和O（（n＋m）k）．最后，作者通过真实数据集上的实验，验证了该算法的有效性．图数据中Top—k属性差异q-clique查询
摘要：紧密子图发现在许多现实世界网络应用中具有重要的研究意义．提出一种新的紧密子图发现问题——Top—k属性差异q—clique查询，找出图中k个节点间属性具有最大差异的q—clique．属性差异q-clique是一种结合图的结构特征和节点属性的紧密子图，在作者合作关系图数据中，该查询可以发现属性（如研究领域或所属单位）上不同的具有紧密合作关系的团队．给出了q-clique的属性差异度量，证明了该问题为NP难问题．采用分支限界策略，提出一种有效求解问题的算法AD—Qclique，同时依照best-first排序思想优化节点访问次序进一步提高算法性能．ACM作者信息数据集上的实验表明，算法AD—Qelique效率远优于基本算法BSL，并且结果中作者皆具有较高的Hindex值及广泛的研究领域．一种面向聚类的对数螺线数据扰动方法
摘要：面向挖掘应用的隐私保护数据要求对数据集进行隐藏的同时维持数据的挖掘可用性，数据扰动是解决该问题的有效方法．现有的面向聚类的数据扰动方法难以兼顾原始数据个体隐私和维持数据聚类可用性，对此提出了一种基于对数螺线的隐私保护数据干扰方法．通过构建面向聚类的隐私保护数据扰动模型，利用对数螺线对原始数据进行扰动隐藏，维持原始数据的k邻域关系稳定，实现数据集聚类可用性的有效维护；进一步提出多重对数螺线扰动的策略，提高隐私保护强度．理论分析和实验结果表明：文中方法能够有效地避免数据隐私泄露，同时维持数据的聚类可用性．时间敏感数据流上的频繁项集挖掘算法
摘要：数据流中的数据分布随着时间动态变化，但传统基于事务的滑动窗口模型难以体现该特征，因此挖掘结果并不精确．首先提出时间敏感数据流处理中存在的问题，然后建立基于时间戳的滑动窗口模型，并转换为基于事务的可变滑动窗口进行处理，提出了频繁项集的挖掘算法FIMoTs．该算法引入了类型变化界限的概念，将项集进行动态分类，根据滑动窗口大小的变化对项集进行延迟处理，仅当项集的类型变化界限超出一定阈值的时候才进行支持度的重新计算，能够达到剪枝的目的．在4种不同密度的数据集上完成的实验结果显示，该算法能够在保证内存开销基本不变的情况下显著提高计算效率．一种时间敏感的SSD和HDD高效混合存储模型
摘要：基于闪存的固态硬盘（Solid State Driver，SSD）已成为目前广泛使用的一种持久存储设备．但是由于闪存不对称的I／O特性以及价格因素，SSD还不能完全取代传统硬盘（Hard Disk Driver，HDD）．因此，由SSD和HDD组成的混合存储系统逐步成为目前研究的重点．文中针对SSD和HDD混合存储问题，提出了一个时间敏感的混合存储模型用来有效地利用SSD．该模型把SSD和HDD作为同级的存储设备，结合数据页的访问次数以及访问热度实现对页面的准确分类和分配，即将读倾向负载的hot页面分配到SSD存储，写倾向负载的页面或者cold页面分配到HDD存储，从而利用SSD和HDD不对称的I／O特性来降低系统总的I／O延迟．作者分别在基于高端SSD和中端SSD的混合存储系统上实现了提出的混合存储模型，并进行了性能评测．实验结果显示，作者提出的模型可以实现对数据页更准确的分类，可以有效地降低页面迁移代价，在较少的SSD存储条件下取得了显著的性能提升．分片位图索引：一种适用于云数据管理的辅助索引机制
摘要：云计算技术的快速发展为海量数据的存储和管理提供了可能．然而，由于存储模型的根本改变，传统关系数据库管理系统中成熟的索引技术既不能直接应用于海量数据的处理，也无法被简单地迁移到云计算环境中．通过分析对比辅助索引在云环境中的两种截然不同的基本逻辑结构，即集中式方案与分布式方案，在吸收两者的优势并规避其弱点的基础上，提出了具有良好可扩展性的分片位图索引机制，从而对云环境中海量数据的检索任务提供高效的支持．通过充分利用云环境中的并行计算资源，使单条查询的响应速度得到提升；与此同时，局部节点根据其所掌握的全局信息规避了不必要的检索开销从而使大量请求并发到达时的查询吞吐量得以保证．在真实数据上进行实验的结果表明，分片位图索引的查询性能大大优于其它方法．路网环境下访问序列受限的多标签路线查询算法
摘要：随着移动互联网、地理定位技术和智能终端设备的迅速普及，产生了大量的位置信息和其对应的标签（tag）描述信息．路线搜索是人们出行时经常进行的活动，但面临多个任务需求时，寻找最佳路线是一项极为耗时的工作．此外空间对象本身的访问权限和用户指定的限制一定程度上制约了对象的访问次序．针对上述情况，文中提出了一种路网环境下访问序列受限的多标签路线（MTROC）查询，该查询的目标是找出一条从源点到目标点、经由与查询中给定的tag相匹配的空间对象且满足序列约束的最短线路．文中证明了MTROC查询问题是NP—hard，并基于增强的路线叠置一关联目录（EROAD）索引提出了3种近似算法．路线扩展RE-Greedy算法和路线渐增插入RII—Greedy算法通过局部更新获得满足需求的路线，而全局路线优化算法GROA为MTROC查询提供一个全局近似最优解．使用真实和合成数据集对文中提出的算法的有效性和可扩展性进行分析评估，实验结果表明3种算法都能有效地完成MTROC查询，其中GROA算法可扩展性最好，而RII—Greedy算法返回的路线质量最高．基于固态硬盘内部并行的数据库表扫描与聚集
摘要：随着基于闪存的固态硬盘在个人计算机和企业服务器上的广泛应用，固态硬盘受到学术界和工业界越来越多的关注．除了具有闪存存储器的优良特性之外，固态硬盘内部还具有丰富的并行特性．传统数据库系统的物理操作表扫描和上层聚集操作是针对磁盘的机械特性和对称读写特性而设计的，并不能发挥固态硬盘内部并行特性的优势．文中首先将固态硬盘作为一个黑盒进行探测以了解其内部的并行特性．在此基础上，对传统数据库表扫描操作进行相应的改进，提出一种并行表扫描模型ParaSSDScan以充分利用固态硬盘内部丰富的并行特性．其次，基于并行表扫描模型，文中还提出一种高效的并行聚集操作模型ParaSSDAggr，并利用该聚集操作模型实现几种常见聚集操作．最后，通过实验表明并行表扫描和并行聚集操作的性能较之传统数据库表扫描和聚集操作的性能分别提高了3倍和4倍，同时实验结果还表明并行聚集操作对内存的需求不大．并行表扫描和并行聚集操作大大提高了表扫描和聚集操作的性能，充分说明了固态硬盘内部并行特性的优越性．面向热点话题时间序列的有效聚类算法研究
摘要：聚类热度时间序列是揭示和建模网络热点话题形成与发展的重要过程．Leskovec等人在2010年提出面向话题时间序列的K_SC聚类算法，其精确度较高且能较好地刻画话题内在发展趋势特征．但K_SC算法具有对初始类矩阵中心高度敏感、高时间复杂度等特性，使其难以在实际高维大数据集上应用．文中结合小波变换技术，提出一个新的迭代式聚类算法WKSC，主要提出两个创新：（1）用Haar小波变换将原始时间序列进行压缩，降低原始时间序列的维度，从而降低了算法的时间复杂度；（2）在Haar反小波变换中，将低维聚类返回得到的矩阵中心作为高维聚类的初始矩阵中心，在迭代聚类过程中优化了对初始矩阵中心高敏感性的问题，提高了聚类的效果．文中分别采用国内外3个数据集作为测试样本，进行了大量的实验．实验结果表明WKSC算法能显著降低聚类的时间复杂度，同时改进聚类效果．WKSC算法可很好的应用于大量高维热点话题的模式分析．数据时效性判定问题的求解算法
摘要：数据的时效性问题是影响数据质量的重要因素之一．时效性差的数据会对企业决策和人们的日常生活带来许多不利影响，这使得判定数据的时效性成为必要．许多应用数据库中都没有完整、清洁、可用的时间戳，从而导致数据时效性的判定非常困难．冗余记录和时效约束能够在时间戳缺失的情况下有效地辅助恢复数据的时序关系，因而能够帮助数据时效性的判定．文中研究包含冗余记录的集合在给定时效约束下的时效性判定问题，并首次提出了时效性判定问题的求解算法．首先，文中定义了查询相关时效性和用户相关时效性．在判定查询相关时效性时，文中将查询归结为最新值查询和时效序列查询两类，并分别根据两类查询的特点，对每类查询定义了查询结果时效性和平均时效性．然后，文中提出了时效图的概念．利用时效图，文中给出了查询相关时效性和用户相关时效性判定问题的求解算法．最后给出了真实数据和虚拟数据上的实验结果，验证了文中算法较高的执行效率，并分析了各个参数对算法的影响．WSR：一种基于维基百科结构信息的语义关联度计算算法
摘要：该文提出了一种基于维基百科结构信息的语义关联度的计算方法——wikiStruRel（wSR）．维基百科作为目前规模最大和增长最快的在线百科系统，其典型包括两个网状结构：文章网络和分类树（以树为主体的图），这两个网状结构包括了丰富的、明确定义的语义知识．WSR充分分析维基百科的文章网络和分类树，进而计算词语间的语义关联度．该方法没有涉及文本处理，算法开销较小，在3个数据集上的实验，取得了较好的准确率和覆盖度．不确定图最可靠最大流算法研究
摘要：文中首先基于可能世界模型提出了不确定图的最可靠最大流问题和可靠性计算模型，这对于构建可靠性网络、可靠传输路径选择以及系统薄弱环节分析等一系列实际问题具有重要意义；然后基于简单路径组合思想提出了一种求解最可靠最大流的算法SPCA，通过简单路径流量的组合，在无需求得所有最大流分布的情况下获得最可靠最大流，并在组合过程中引入概率剪枝与约束剪枝策略，对无效组合进行过滤，从而显著地提高了算法效率；接着文中针对SPCA算法易受路径数量及瓶颈容量影响的问题，又提出一种基于状态空间划分的最可靠最大流算法SDBA，该算法的主要思想是将不确定图所蕴含的子图空间划分为互不相交且满足最大流值的闭合区间集合，进而寻找所有闭合区间中概率最大的下界状态，经证明这个下界状态对应子图中的最大流分布为最可靠最大流；最后通过实验，比较了两种算法的性能．实验结果表明SDBA算法相对于SPCA算法其空间复杂度有一定的增加，但时间复杂度方面具有较大的优势，能够很好地解决SPCA算法性能受制于容量的问题，具有更好的性能与适用性．一种基于用户偏好自动分类的社会媒体共享和推荐方法
摘要：社会媒体应用已成为Web应用的主流，以用户为中心并且海量媒体数据由用户自生成是社会媒体Web应用的重要特征．应对目前社会媒体环境中信息过载的问题，信息的共享和推荐机制发挥着重要的作用．文中分析了目前主流社会媒体网站基于用户自建组的信息共享机制所存在的问题以及传统推荐技术在效率上的问题，提出了一种新的基于用户偏好自动分类的社会媒体数据共享和推荐方法．直观上讲，该方法的本质是把用户对具体媒体对象的偏好转化成用户对媒体对象所蕴含兴趣元素的偏好，然后把具有相同偏好的用户，即对若干兴趣元素上的兴趣度都相同，自动聚合成为一个“共同偏好组（CPG）”．文中提出了基于CPG的社会媒体信息共享和推荐的架构，设计实现了CPG的自动生成算法，通过随机生成模拟数据集实验详细分析了算法性能的影响因素，并与现有类似功能算法进行了效率对比，实验结果表明算法可适用于具有海量用户的社会媒体应用．基于数据源依赖关系的信息评价方法研究
摘要：当前很多的数据管理应用都需要从多个数据源集成数据，每个数据源都会提供一组值，并且不同的数据源常常提供相互冲突的数据值．为了提供给用户高质量的数据值，关键是数据集成系统能够解决数据冲突问题，提取出正确的数据值．文中对已有的真值发现算法进行了分析与总结，通过考虑处理同一个值的不同表现形式和改进的选票算法，作者对现有方法给出了改进，改进后的方法可以更有效地在众多冲突数据中找出正确的数据值．Multi—Radio无线传感器网络中基于缓存和信道切换的数据查询算法的研究
摘要：针对Multi—Radio Multi—Channel传感器网络中链路服务质量和信道冲突等问题，提出并证明了基于缓存和信道切换的数据查询问题是一个NP完全问题．根据数据流守恒和链路一信道等约束条件，建立线性规划方程，得到该问题的最优解模型，并提出了一个多项式时间的近似算法——贪心新覆盖数据算法．该算法采用动态规划策略最小化缓存节点将单位数据包传输到查询节点所需要的路径时延，再贪心选择其具有最小路径时延的缓存节点，收集其新覆盖数据．理论分析和实验结果表明，提出的方案能有效地减少数据收集时延，提高数据查询效率．