在多元连接数据查询中最小生成树法的改进应用

本文对最小生成树法在分布式数据库多元连接中的应用进行了阐述和分析,并利用分布式数据库数据的分布性对最小生成树法进行了改进。提出了基于最小生成树法的连接图划分方法将连接图划分成多个子连接图,提高连接操作的并行性,从而使得响应时间得到减少。     

多目标优化问题的连续域蚁群算法仿真研究

本文研究了一种用于求解带有多个约束条件(multi-objective optimization problem,MOP)的连续域蚁群算法。该算法定义了连续域中信息量的留存方式和蚂蚁的行走策略,并将信息素交流和基于全局最优经验指导两种寻优方式相结合,将当前发现的所有的非支配解保存起来,进而用这些解来指导蚂蚁朝着散布较为稀疏的区域寻优,以保证解的分布性能,并提高了蚁群算法的收敛速度,同时维持了群体的多样性。     

High Performance GPU‐based Proximity Queries using Distance Fields

Proximity queries such as closest point computation and collision detection have many applications in computer graphics, including computer animation, physics‐based modelling, augmented and virtual reality. We present efficient algorithms for proximity queries between a closed rigid object and an arbitrary, possibly deformable, polygonal mesh. Using graphics hardware to densely sample the distance field of the rigid object over the arbitrary mesh, we compute minimal proximity and collision response information on the graphics processing unit (GPU) using blending and depth buffering, as well as parallel reduction techniques, thus minimizing the readback bottleneck. Although limited to image‐space resolution, our algorithm provides high and steady performance when compared with other similar algorithms. Proximity queries between arbitrary meshes with hundreds of thousands of triangles and detailed distance fields of rigid objects are computed in a few milliseconds at high‐sampling resolution, even in situations with large overlap.     

在线RFID多复杂事件查询处理技术

在线无线射频识别(radio frequency identification,RFID)数据流上的复杂事件处理技术是一个新的课题。现有研究工作仅是针对单一的复杂事件查询,没有考虑多复杂事件同时查询的处理策略。在复杂事件语言SASE(stream-based and shared event processing)的基础上设计了专门针对多查询的自动机及相关的优化技术,解决了RFID数据流上多复杂事件查询的问题。实验结果表明,算法在查询数量较大时,时间与空间上较传统算法有更好的表现。     

基于不确定时态信息的索引技术

索引技术是时态数据库查询优化的重要方法之一。分析了时态数据库中的不确定时态信息以及基于不确定时态信息的索引技术,并详细讨论了能处理时间变元的改进的4R-tree索引技术的建立过程。     

基于CB+-tree的时态XML索引

针对时态查询与时间属性紧密相关的特点,利用时间区间作为改进后B+-tree的索引关键字建立索引,改进后的B+-tree命名为Changing B+-tree(CB+-tree)。实验证明,在CB+-tree上进行时态查询比B+-tree及基于DOM的XML文档的查询效率有所提高。     

一种最大向量平均个数的估计方法

提出一种估计n个d维向量中最大向量平均个数的方法。该方法通过分析单个向量与其他向量子集的支配关系,求出最大向量平均个数的解析式。证明解析式满足已知的递归关系,得到最大向量平均个数的近似估计。与已有方法相比,该方法可应用到估计k个其他向量支配的平均个数问题。     

Skyline and mapping aware join query evaluation

Growing interests in multi-criteria decision support applications have resulted in a flurry of efficient skyline algorithms. In practice, real-world decision support applications require to access data from disparate sources. Existing techniques define the skyline operation to work on a single set, and therefore, treat skylines as an “add-on” on top of a traditional Select-Project-Join query plan. In many real-world applications, the skyline dimensions can be anti-correlated such as the attribute pair {price, mileage} for cars and {price, distance} for hotels. Anti-correlated data are particularly challenging for skyline evaluation and therefore have commonly been ignored by existing techniques. In this work, we propose a robust execution framework called SKIN to evaluate skyline over joins. The salient features of SKIN are: (a) effective in reducing the two primary costs, namely the cost of generating the join results and the cost of dominance comparisons to compute the final skyline of join results, (b) shown to be robust for both skyline-friendly (independent and correlated) as well as skyline-unfriendly (anti-correlated) data distributions. SKIN is effective in exploiting the skyline knowledge in both local within individual data sources and across disparate sources—to significantly reduce the above-mentioned costs incurred during the evaluation of skyline over join. Our experimental study demonstrates the superiority of our proposed approach over state-of-the-art techniques to handle a wide variety of data distributions.     

Best position algorithms for efficient top-k query processing

The general problem of answering top-k queries can be modeled using lists of data items sorted by their local scores. The main algorithm proposed so far for answering top-k queries over sorted lists is the Threshold Algorithm (TA). However, TA may still incur a lot of useless accesses to the lists. In this paper, we propose two algorithms that are much more efficient than TA. First, we propose the best position algorithm (BPA). For any database instance (i.e. set of sorted lists), we prove that BPA stops as early as TA, and that its execution cost is never higher than TA. We show that there are databases over which BPA executes top-k queries O(m) times faster than that of TA, where m is the number of lists. We also show that the execution cost of our algorithm can be (m−1) times lower than that of TA. Second, we propose the BPA2 algorithm, which is much more efficient than BPA. We show that the number of accesses to the lists done by BPA2 can be about (m−1) times lower than that of BPA. We evaluated the performance of our algorithms through extensive experimental tests. The results show that over our test databases, BPA and BPA2 achieve significant performance gains in comparison with TA.     

Maintaining consistent results of continuous queries under diverse window specifications

Continuous queries applied over nonterminating data streams usually specify windows in order to obtain an evolving–yet restricted–set of tuples and thus provide timely and incremental results. Although sliding windows get frequently employed in many user requests, additional types like partitioned or landmark windows are also available in stream processing engines. In this paper, we set out to study the existence of monotonic-related semantics for a rich set of windowing constructs in order to facilitate a more efficient maintenance of their changing contents. After laying out a formal foundation for expressing windowed queries, we investigate update patterns observed in most common window variants as well as their impact on adaptations of typical operators (like windowed join, union or aggregation), thus offering more insight towards design and implementation of stream processing mechanisms. Furthermore, we identify syntactic equivalences in algebraic expressions involving windows, to the potential benefit of query optimizations. Finally, this framework is validated for several windowed operations against streaming datasets with simulations at diverse arrival rates and window specifications, providing concrete evidence of its significance.