不确定Skyline查询技术研究
摘要：当前不确定数据广泛存在于诸如传感器网络、RFID网络、基于位置服务、移动对象管理网上购物和市场监控等各种实际应用中．不确定Skyline查询作为不确定数据管理的一个重要方面，由于其在决策制定、市场分析、环境监控和数据挖掘等方面的重要作用，近年来在数据库和网络计算领域受到广泛关注．首先，概述了各种不确定数据类型上的Skyline查询定义，包括离散、连续概率分布模型以及不完全数据上的Skyline查询定义；其次，分析了不确定Skyline查询的特点，并在此基础上综述了现有的各种不确定数据集上的集中式和分布式Skyline查询方法，重点分析了各种算法的原理和优缺点；再次，介绍了不确定数据流上的Skyline查询定义并综述了各种不确定数据流上的Skyline查询方法；最后，基于最新研究动态指出了未来不确定Skyline查询研究的趋势．实时复杂事件处理的最坏响应时间估算
摘要：实时复杂事件处理系统（CEP系统）用于从原子事件流中检测出复杂事件，需要确保事件处理任务在截止期内完成。确保实时性的关键问题是如何估算系统中复杂事件处理程序（CEP程序）的最坏响应时间．现有针对一般程序的估算方法需要标注对象程序中子程序执行次数的取值范围．然而，CEP程序较为复杂，难以直接获知子程序执行次数的取值范围．虽然执行次数间存在关联关系，可以间接求解出取值范围，但这样得到取值范围不够严格，使估算精度较低，因此现有估算方法难以直接使用．提出一种CEP程序的最坏响应时间估算方法．采用新标注方式，通过对CEP程序的检测结构进行分析，归纳出子程序执行次数间的关联约束，并使用关联约束进行标注，替代了标注其取值范围，避免了标注困难．实验表明方法具有较高估算精度．基于划分的集合相似连接
摘要：集合相似连接（setsimilarityjoin）是指在给定的数据集中，按照基于集合间覆盖关系的相似度计算方法来衡量数据之间的相似度、并找出所有相似度不小于给定阈值的数据对的操作．集合相似连接作为一种新的基本操作在很多领域中有重要应用．随着社会网络、移动应用以及在线服务的发展，使得数据收集的效率和规模得到了很大的提高，同时给相似连接操作带来新的挑战．根据集合相似的必要条件，提出了相似集合之间的差异度．利用差异度和鸽巢原理，提出了一种新颖的基于数据划分的集合相似连接计算方法，该方法对集合进行自适应的均衡划分，并利用基于划分块的过滤方法来提高过滤的效率．为了进一步提高过滤的效果和相似连接的效率，利用划分块的位置信息提出了增强的过滤方法．针对提出的方法，在不同的环境下进行了实验，实验结果表明，该方法与已有的方法相比可以有效地提高相似连接的效率．追加型数据库外包中的查询结果验证
摘要：数据库外包是将数据库管理工作外包给专业第三方，而数据库外包中需要解决的关键问题之一是查询结果的验证．提出了外包追加型数据库的问题．根据外包追加型数据库的特点，在现有验证数据结构的基础上，提出了一种新型验证数据结构Min—MaxHashTree，可以有效地解决客户对查询结果进行验证的问题．对于数据所有者端，给出了基本的数据发送算法；对于服务提供商端，分别给出了一次性查询和连续查询的查询算法和查询结果验证算法．最后，对数据所有者端的验证数据结构的存储、数据发送和服务提供商端的连续查询进行了优化处理，大大节省了数据所有者端的存储空间，提高了数据的整体处理效率．实验表明，MinMaxHashTree能够有效完成追加型数据库外包的查询结果验证，并且能够高效率处理大规模数据．VPM：列存储系统中基于带值路径的物化技术
摘要：物化是列存储数据仓库查询中必不可少的操作，物化策略和物化技术直接影响到查询执行的性能，因此设计一种适应于列存储系统的物化策略和相关技术尤为重要．针对延迟物化可能重复读取数据块的缺陷，提出了基于带值路径的物化技术，简称VPM．首先，定义了一个描述物理执行中间结果的结构一传递块，该结构将用于重构的位置信息与实际列值相分离．在此基础上，对于给定的物理查询树，根据其操作节点是否需要某一列的值进行路径标记，生成自扫描节点或抽值节点到最终需要这些节点的引用列的祖先节点之间的路径，即带值路径．将起始节点引用列的列值保存在传递块的列值区中，并在向查询树的上层操作节点传榆过程中不断对其过滤．对带值路径中的其他列仅保存其位置信息．在查询执行时，除了路径起始节点要从磁盘读取数据外，其他节点直接从传递块中获得相应的列值，有效地减少了查询处理过程的I／0开销，提高了查询的执行性能．最后在DWMS上使用TPC—H中针对数据仓库的基准数据集SSBM进行实验，验证了基于带值路径物化技术的有效性．研发动态 科学家首次绘制出电子的＂华尔兹＂轨迹
摘要：据物理学家组织网报道，一个来自IBM研究团队和瑞士联邦理工学院（ETH）的联合小组，首次直接绘制出电子怎样形成一个持续自旋螺旋的过程图，揭示了电子在半导体中跳“华尔兹”舞的情景．这一新进展有助于科学家更有效控制设备内部磁性运动，带来更加节能高效的电子设备．目前的计算机技术是利用电子所带电荷来编码和处理数据．随着半导体元件越来越小，到了无法控制电流的临界点，就开始显出局限性，而电子自旋能突破这种障碍．研究人员利用一种时间分辨扫描显微技术，监控了数千个电子自旋的演变，这些自旋是在一个很小区域内同时生成，属于随机旋转并会很快改变方向．英特尔和惠普联手打造世界最高效超级计算机
摘要：惠普和英特尔联手为美国国家能源部可再生能源实验室（NREL）N：计和建造了一个新的超级计算机系统，该系统将是世界上最高效的系统之一．新系统将采用目前的32纳米XeonE5处理器和未来的22纳米IvyBridge处理器的组合，再加上约600个XeonPhi协同处理器（基于英特尔的MIC架构），在惠普ProLiant第8代服务器内运行．英特尔服务器芯片将为云和HPC集成fabric
摘要：英特尔正在开发高性能服务器芯片．这种芯片未来将更快地提供云服务的结果或者分析等数据密集型应用的结果，同时减少数据中心的电费账单．英特尔将在未来的服务器芯片中集成一个融合的架构控制器．英特尔架构事业部副总裁拉杰．哈扎拉（RajHazra）称，这个架构控制器将提高服务器通信速度，同时帮助数据中心以最高的效率运行．这个架构虚拟化输入／输出（I／O），把数据中心中的存储和网络结合起来．集成的控制器将提供一个更宽的通道以提高分布式计算环境的性能．BTreeU-Topk：基于二叉树的不确定数据上的Top-k查询算法
摘要：应用需求的发展衍生各种查询类型，Top—k查询是交互环境下一种重要查询类型．由于数据的不确定性，传统数据上的Top—k查询技术和方法不能直接应用于不确定数据查询．在已有不确定数据上Top-k查询算法的基础上，提出基于二叉树的不确定数据上Top—k查询算法BTreeU—Topk；为了提高算法执行效率，对二叉树进行修剪操作进而提出BTreeOPTU—Topk和BTreePU—Topk算法．实验结果表明，BTreeU—Topk，BTreeOPTU—Topk以及BTreePU—Topk算法在不同数据分布以及k值增长时均优于现有算法．基于视图树的实视图动态选择
摘要：为用户缓存实视图可以有效提高其OLAP查询的性能．但是，已有的缓存管理策略由于没有考虑用户在进行OLAP分析时的数据访问特性，在处理实视图动态选择问题时无法获得好的性能．提出了视图路径和视图树的概念，并以视图树作为客户端缓存中的实视图组织方式．提出了“逆路径增长法”来快速计算新到达查询的视图路径，提高了查询的响应速度．对于视图树的动态调整问题，以“保留路径”为参照，设计了合理有效的视图替换策略．实验证明，该方法能够比已有的动态选择方法取得更好的性能．基于分配空间自学习的在线动态索引混合更新机制
摘要：针对索引维护时间和空间效率低的问题，提出了一种基于分配空间自学习的在线动态索引混合更新机制（on—linedynamicindexhybridupdate，0DIHU）．ODIHU根据Zipf分布原理对长短列表数量分布进行估计，并采用基于历史分配空间的自适应学习机制对长短列表空间进行有效管理，然后对短列表采用立即合并更新方式，长列表采用上限Y相邻多路合并的更新方式维护，实现索引更新与查询性能的有效折中．理论分析及实验结果表明，ODIHU能有效地提高索引维护与更新过程中的空间效率、索引合并与查询时间效率．高可扩展的RDF数据存储系统
摘要：由于资源描述框架（resourcedescriptionframework，RDF）具有表达灵活、简洁等优点，已被接受为表达元数据及万维网上数据互联的规范．近年来，其数据量在以飞快的速度增长．相应地，要求存储RDF数据的系统应具有高扩展性．介绍了一个高可扩展的RDF数据存储系统TripleBit．为尽可能降低存储空间消耗，采用了增量压缩和变长整数编码方法．并采用了数据分块的存储方法，既使得存储管理方便又使得存储结构紧凑，加速了数据读取．系统提供了基于启发式规则的动态查询计划生成方法，所产生的查询计划在执行过程中根据中间结果会相应作调整，以保持最优的执行顺序．对于多变量的查询，使用二步执行策略以减少查询过程中产生的中间结果．与目前流行RDF数据存储系统相比较，在存储空间上RDF-3X比TripleBit至少多40％；在查询性能上，比RDF一3X和MonetDB获得数倍的提升．RB树：一种支持空间近似关键字查询的外存索引
摘要：空间近似关键字查询包含一个空间条件和一组关键字相似性条件，这种查询在空间数据库中返回同时满足以下条件的对象：1）对象的位置信息满足查询中的空间条件；2）对于查询中的任何一个关键字，对象中至少包含一个关键字与其相似度大于给定阂值．随着当前数据的爆炸性增长，空间数据库无法完整地存放在内存中，因此空间数据库需要支持空间近似关键字查询的外存索引．目前，还没有在外存中支持精确的空间近似关键字查询的索引结构．设计了一种新型的外存索引RB树，在外存中支持精确的空间近似关键字查询．RB树支持的空间近似关键字查询包括多种空间条件，如范围查询、NN查询，同时支持多种关键字相似性度量，包括编辑距离、规范化编辑距离等．通过真实数据中的性能测试验证了RB树的效率．基于轨迹时空关联语义和时态熵的移动对象社会角色发现
摘要：现有轨迹相似性度量缺乏对时空语义和时间随机性的考虑，不能有效地区分移动对象的社会角色．为解决这一问题，做了如下工作：1）提出了时空关联语义（spatial—temporalassociatedsemantics，STAS）的概念，解释了轨迹的语义相似性规律，即两条轨迹的语义相似性与其在某时段内经过同类型区域的概率正相关；2）提出了时态熵（temporalentropy）的概念，度量了轨迹经过同一类型区域的时间随机性；3）基于STAS和时态熵，给出轨迹语义相似性度量（trajectorysemanticsimilarity，TSS），刻画了轨迹所属移动对象的社会角色的时空特征；4）提出了移动对象社会角色发现算法（socialrolesdiscoveringalgorithm，SRDA），该算法基于TSS实现轨迹聚类，其中一个聚簇代表一种社会角色．真实数据和仿真数据上的实验表明，SRDA在准确率上比现有方法平均提高了18％，同时具有线性时间复杂度，从而验证了算法的有效性和性能．不确定移动对象的模糊时空范围查询
摘要：指出不确定性和模糊性在时空语义上的区别；提出不确定移动对象的模糊时空范围查询问题，即查询条件中时间、空间范围的外延是模糊的，无清晰的边界，而目标对象的位置不确定；用模糊集表示模糊查询条件，概率密度函数表示移动对象在各自不确定区域内的可能位置分布；给出了不确定对象关于模糊查询条件匹配度的计算方法；设计了基于a截集的无效对象排除和有效对象确认规则及查询算法．算法规则适用于任意概率密度分布．现有的确定或不确定范围查询可以看成是模糊时空范围查询的特例．通过实验验证了算法的效率，在各种参数设置下，约有30％～90％的查询结果可在不计算匹配度的情况下获得．2013年《计算机研究与发展》专题（正刊）征文通知——“物联网的基础理论与新技术方向”
摘要：近年来，针对物联网的基础理论、核心技术、系统应用及产业化的研究与深入发展一直是国际国内学术与产业界集中关注的热点．传感网物联网在国内受到极大的重视，近几年在全国各地开展的物联网建设实践活动也方兴未艾，并有越来越多的学者和学生参与到这个领域的研究中。人们对物联网的认识以及对其技术和理论方面尚存问题的认识也不断深入．与此同时，各类新型电子产品的不断涌现（比如智能手机等），也为物联网的应用提供了新的技术依托手段和日新月异的可能性，展现了更广阔更引人人胜的服务模式和未来商业模式，也极大地扩展和丰富了物联网研究领域的学术及技术范畴．空间数据库中主题相关区域查询
摘要：空间查询处理已经广泛地应用于基于位置的服务、设施选址等领域．提出一种新的空间查询：主题相关区域查询（topic—relevantregionqueries，T2R），该查询可以用于位置选址等空间决策分析．给定一个由空间特征对象集合R定义的主题丁、查询窗口q，T2R查询返回不交叠的k个与主题最相关的区域，区域与主题的相关程度由区域内特征对象的数量结合其重要性进行计算．为了有效处理T2R查询，提出BSL，FR和SHR3种算法，其中SHR算法将高相关程度区域先聚类、再收缩以获得更优的剪枝效果．所提出的算法解决了给定查询窗口下对数据空间任意位置按主题相关程度进行排序的问题．利用真实与人工数据集进行了充分实验，评估了所提出算法在不同参数设置下的查询效率，通过针对实际主题的查询验证了T2R查询的有效性．基于阈值的社交网络影响力最大化算法
摘要：对于社交网络影响力最大化问题，Kemple和Kleinberg提出了有较好影响范围的贪心算法，但是KK算法的复杂度非常高，并不实用．利用线性阈值模型提出了一种基于节点激活阈值的启发式算法．它综合考虑了节点之间的影响力和节点的激活阈值，根据每个节点在激活过程中动态变化的阈值来计算PIN值，启发过程中，每一次都选取PIN最大的节点作为种子节点进行激活，贪心阶段中再贪心地挑选那些具有最大影响范围增量的节点作为种子节点．通过实验表明，即使在完全不采用贪心阶段，该算法的激活范围与KK算法都非常接近，而算法的复杂度则相对非常小．实验还表明该算法相对于HPG算法在相同启发因子c的情况下具有更大的激活范围．
