Selecting skyline stars over uncertain databases: Semantics and refining methods in the evidence theory setting

In recent years, a great attention has been paid to skyline computation over uncertain data. In this paper, we study how to conduct advanced skyline analysis over uncertain databases where uncertainty is modeled thanks to the evidence theory (a.k.a., belief functions theory). We particularly tackle an important issue, namely the skyline stars (denoted by SKY²) over the evidential data. This kind of skyline aims at retrieving the best evidential skyline objects (or the stars). Efficient algorithms have been developed to compute the SKY². Extensive experiments have demonstrated the efficiency and effectiveness of our proposed approaches that considerably refine the huge skyline. In addition, the conducted experiments have shown that our algorithms significantly outperform the basic skyline algorithms in terms of CPU and memory costs.     

基于MapReduce的预处理高效Skyline算法

现有基于MapReduce的算法不能高效地解决大数据的Skyline查询问题。针对这种情况,提出一种高效的预处理Skyline查询算法MRFS(MapReduce based Filter Skyline),对大数据集进行预处理,提取支配能力较强的小点集组成比较点集,在算法开始前用比较点集对原始数据集进行过滤,排除掉一大部分不能成为Skyline结果集的数据对象;再对过滤后的数据集在Map阶段并行计算出局部Skyline集;最后合并到一个Reduce任务,得到最终的Skyline结果集。在不同数据分布下对该算法进行系统实验,结果表明算法比现有的算法在时间效率上提高了20%~30%。     

传感器网络中自顶向下的轮廓监控算法

根据无线传感器网络的特殊性质,提出了自顶向下的轮廓监控算法.利用为节点分配的超立方,可以有效地对轮廓监控过程中的数据进行过滤,从而高效地完成轮廓的维护工作.仿真实验结果表明,该算法能有效地避免无用的数据传输.减少节点的能量消耗,从而延长传感器网络的使用寿命.     

MapReduce框架下的Skyline结果优化算法

随着大数据时代的到来,数据量和数据复杂度急剧提高,Skyline查询结果集规模巨大,无法为用户提供精确的信息.MapReduce作为并行计算框架,已广泛应用于大数据处理中.本文提出了MapReduce框架下基于支配个数的结果优化算法(MR-DMN),解决了大数据环境下的Skyline结果集优化问题.大量的实验表明:算法具有良好的时间和空间效率.     

基于网格索引的连续Skyline计算方法

考虑按任意顺序随机增删的数据流场景下连续Skyline计算问题,首先基于已有工作提出了一个基本算法BCSC;然后基于"影响区域"的观察,提出了一个基于网格索引数据结构的算法GICSC,其基本思想为:(1)将数据空间划分为若干大小相等的网格,采用网格索引方法对数据点进行组织和管理;(2)用网格将数据空间表示为自由区域和影响区域两部分,发生在自由区域中的数据变化可以从理论上保证不影响计算结果,因此仅需对落于影响区域的数据增删进行运算,从而降低数据规模;(3)算法的计算模块通过逐步扩展的方法,无需遍历全部数据便可获得初始的Skyline集合及影响区域,维护模块通过类似方法计算数据变化对Skyline集合的影响,同时动态更新影响区域的大小.由于没有对数据流特性进行假设限制,因此BCSC和GICSC算法具有更广泛的适应性.理论分析和实验结果均验证了上述方法的有效性.     

SkyGraph: an algorithm for important subgraph discovery in relational graphs

A significant number of applications require effective and efficient manipulation of relational graphs, towards discovering important patterns. Some example applications are: (i) analysis of microarray data in bioinformatics, (ii) pattern discovery in a large graph representing a social network, (iii) analysis of transportation networks, (iv) community discovery in Web data. The basic approach followed by existing methods is to apply mining techniques on graph data to discover important patterns, such as subgraphs that are likely to be useful. However, in some cases the number of mined patterns is large, posing difficulties in selecting the most important ones. For example, applying frequent subgraph mining on a set of graphs the system returns all connected subgraphs whose frequency is above a specified (usually user-defined) threshold. The number of discovered patterns may be large, and this number depends on the data characteristics and the frequency threshold specified. It would be more convenient for the user if “goodness” criteria could be set to evaluate the usefulness of these patterns, and if the user could provide preferences to the system regarding the characteristics of the discovered patterns. In this paper, we propose a methodology to support such preferences by applying subgraph discovery in relational graphs towards retrieving important connected subgraphs. The importance of a subgraph is determined by: (i) the order of the subgraph (the number of vertices) and (ii) the subgraph edge connectivity. The performance of the proposed technique is evaluated by using real-life as well as synthetically generated data sets.     

Probabilistic skyline operator over sliding windows

Skyline computation has many applications including multi-criteria decision making. In this paper, we study the problem of efficiently computing the skyline over sliding windows on uncertain data elements against probability thresholds. Firstly, we characterize the properties of elements to be kept in our computation. Then, we show the size of dynamically maintained candidate set and the size of skyline. Novel, efficient techniques are developed to process continuous probabilistic skyline queries over sliding windows. Finally, we extend our techniques to cover the applications where multiple probability thresholds are given, “top-k” skyline data objects are retrieved, or elements have individual life-spans. Our extensive experiments demonstrate that the proposed techniques are very efficient and can handle a high-speed data stream in real time.     

The Farthest Spatial Skyline Queries

Pareto-optimal objects are favored as each of such objects has at least one competitive edge against all other objects, or “not dominated”. Recently, in the database literature, skyline queries have gained attention as an effective way to identify such pareto-optimal objects. In particular, this paper studies the pareto-optimal objects in perspective of facility or business locations. More specifically, given data points P and query points Q in two-dimensional space, our goal is to retrieve data points that are farther from at least one query point than all the other data points. Such queries are helpful in identifying spatial locations far away from undesirable locations, e.g., unpleasant facilities or business competitors. To solve this problem, we first study a baseline Algorithm TFSS and propose an efficient progressive Algorithm BBFS, which significantly outperforms TFSS by exploiting spatial locality. We also develop an efficient approximation algorithm to trade accuracy for efficiency. We validate our proposed algorithms using extensive evaluations over synthetic and real datasets.     

基于Skyline的三维数字校园系统

介绍了基于Skyline的三维数字校园建设的理论与方法,并实现了对西南科技大学三维数字校园的模拟,可让用户通过网络实现校园的自由漫游,并结合一定的交互操作实现地物的分析与测量、地物查询等功能。     

A study on numerical solution method for efficient dynamic analysis of constrained multibody systems

A new and efficient computational method for constrained multibody systems is proposed. In the proposed method, local parametrization method is employed to apply the same solution method for position, velocity, and acceleration analyses since the coefficient matrices for each analysis have an identical matrix pattern. The skyline solution method is used to overcome numerical inefficiency when solving large scaled equations. Also, subsystem mpartitioning method is derived systematically to perform parallel processing for real time simulation. To show the numerical accuracy and efficiency of the proposed method, three numerical problems are solved.