Efficient continuous skyline computation

In a number of emerging streaming applications, the data values that are produced have an associated time interval for which they are valid. A useful computation over such streaming data is to produce a continuous and valid skyline summary. Previous work on skyline algorithms have only focused on evaluating skylines over static data sets, and there are no known algorithms for skyline computation in the continuous setting. In this paper, we introduce the continuous time-interval skyline operator, which continuously computes the current skyline over a data stream. We present a new algorithm called LookOut for evaluating such queries efficiently, and empirically demonstrate the scalability of this algorithm. In addition, we also examine the effect of the underlying spatial index structure when evaluating skylines. Whereas previous work on skyline computations have only considered using the R^∗-tree index structure, we show that for skyline computations using an underlying quadtree has significant performance benefits over an R^∗-tree index.     

Efficient group-by reverse skyline computation

The reverse skyline query is very useful in many decision making applications. Given a multi-dimensional dataset P and a query point q, the reverse skyline query returns all the points in P whose dynamic skyline contains q. Although the reverse skyline retrieval has been well-studied in the literature, there is, to the best of our knowledge, no prior work on one of the most intuitive and practical types of reverse skyline queries, namely, group-by reverse skyline (GRS) query, which retrieves the reverse skyline for each group in a specified dataset. We formalize the GRS query including monochromatic and bichromatic versions, and identify its properties, and then propose a set of efficient algorithms for computing the group-by reverse skyline. Extensive experimental evaluation using both real and synthetic datasets demonstrates the performance of our proposed algorithms in terms of effectiveness and efficiency under a variety of experimental settings.     

Efficient general spatial skyline computation

With the emergence of location-aware mobile device technologies, communication technologies and GPS systems, the location based queries have attracted great attentions in the database literature. In many user recommendation web services, the spatial preference query is used to suggest the objects based on their spatial proximity with the facilities. In this paper, we study the problem of general spatial skyline (GSSKY) which can provide the minimal candidate set of the optimal solutions for any monotonic distance based spatial preference query. Efficient progressive algorithm called P-GSSKY is proposed to significantly reduce the number of non-promising objects in the computation. Moreover, we also propose spatial join based algorithm, called J-GSSKY, which can compute GSSKY efficiently in terms of I/O cost. The paper conducts a comprehensive performance study of the proposed techniques based on both real and synthetic data.     

Faster output-sensitive skyline computation algorithm

We present the second output-sensitive skyline computation algorithm which is faster than the only existing output-sensitive skyline computation algorithm [1] in worst case because our algorithm does not rely on the existence of a linear time procedure for finding medians.     

Efficient computation of combinatorial skyline queries

Current skyline evaluation techniques are mainly to find the outstanding tuples from a large dataset. In this paper, we generalize the concept of skyline query and introduce a novel type of query, the combinatorial skyline query, which is to find the outstanding combinations from all combinations of the given tuples. The past skyline query is a special case of the combinatorial skyline query. This generalized concept is semantically more abundant when used in decision making, market analysis, business planning, and quantitative economics research. In this paper, we first introduce the concept of the combinatorial skyline query (CSQ) and explain the difficulty in resolving this type of query. Then, we propose two algorithms to solve the problem. The experiments manifest the effectiveness and efficiency of the proposed algorithms.     

Parallel skyline computation on multicore architectures

With the advent of multicore processors, it has become imperative to write parallel programs if one wishes to exploit the next generation of processors. This paper deals with skyline computation as a case study of parallelizing database operations on multicore architectures. First we parallelize three sequential skyline algorithms, BBS, SFS, and SSkyline, to see if the design principles of sequential skyline computation also extend to parallel skyline computation. Then we develop a new parallel skyline algorithm PSkyline based on the divide-and-conquer strategy. Experimental results show that all the algorithms successfully utilize multiple cores to achieve a reasonable speedup. In particular, PSkyline achieves a speedup approximately proportional to the number of cores when it needs a parallel computation the most.     

Toward efficient multidimensional subspace skyline computation

Skyline queries have attracted considerable attention to assist multicriteria analysis of large-scale datasets. In this paper, we focus on multidimensional subspace skyline computation that has been actively studied for two approaches. First, to narrow down a full-space skyline, users may consider multiple subspace skylines reflecting their interest. For this purpose, we tackle the concept of a skycube, which consists of all possible non-empty subspace skylines in a given full space. Second, to understand diverse semantics of subspace skylines, we address skyline groups in which a skyline point (or a set of skyline points) is annotated with decisive subspaces. Our primary contributions are to identify common building blocks of the two approaches and to develop orthogonal optimization principles that benefit both approaches. Our experimental results show the efficiency of proposed algorithms by comparing them with state-of-the-art algorithms in both synthetic and real-life datasets.     

Parallel computation of probabilistic skyline queries using MapReduce

The Journal of Supercomputing - In recent years, numerous applications have been continuously generating large amounts of uncertain data. The advanced analysis queries such as skyline operators are...     

Efficient and privacy-preserving skyline computation framework across domains

Skyline computation, which returns a set of interesting points from a potentially huge data space, has attracted considerable interest in big data era. However, the flourish of skyline computation still faces many challenges including information security and privacy-preserving concerns. In this paper, we propose a new efficient and privacy-preserving skyline computation framework across multiple domains, called EPSC. Within EPSC framework, a skyline result from multiple service providers will be securely computed to provide better services for the client. Meanwhile, minimum privacy disclosure will be elicited from one service provider to another during skyline computation. Specifically, to leverage the service provider’s privacy disclosure and achieve almost real-time skyline processing and transmission, we introduce an efficient secure vector comparison protocol (ESVC) to construct EPSC, which is exclusively based on two novel techniques: fast secure permutation protocol (FSPP) and fast secure integer comparison protocol (FSIC). Both protocols allow multiple service providers to calculate skyline result interactively in a privacy-preserving way. Detailed security analysis shows that the proposed EPSC framework can achieve multi-domain skyline computation without leaking sensitive information to each other. In addition, performance evaluations via extensive simulations also demonstrate the EPSC’s efficiency in terms of providing skyline computation and transmission while minimizing the privacy disclosure across different domains.     

Efficient distributed skyline computation using dependency-based data partitioning

Skyline queries, together with other advanced query operators, are essential in order to help identify sets of interesting data points buried within huge amount of data readily available these days. A skyline query retrieves sets of non-dominated data points in a multi-dimensional dataset. As computing infrastructures become increasingly pervasive, connected by readily available network services, data storage and management have become inevitably more distributed. Under these distributed environments, designing efficient skyline querying with desirable quick response time and progressive returning of answers faces new challenges. To address this, in this paper, we propose a novel skyline query scheme termed MpSky. MpSky is based on a novel space partitioning scheme, employing the dependency relationships among data points on different servers. By grouping points of each server using dependencies, we are able to qualify a skyline point by only comparing it with data on dependent servers, and parallelize the skyline computation among non-dependent partitions that are from different servers or individual servers. By controlling the query propagation among partitions, we are able to generate skyline results progressively and prune partitions and points efficiently. Analytical and extensive simulation results show the effectiveness of the proposed scheme.     

Efficient distance-based representative skyline computation in 2D space

Representative skyline computation is a fundamental issue in database area, which has attracted much attention in recent years. A notable definition of representative skyline is the distance-based representative skyline (DBRS). Given an integer k, a DBRS includes k representative skyline points that aims at minimizing the maximal distance between a non-representative skyline point and its nearest representative. In the 2D space, the state-of-the-art algorithm to compute the DBRS is based on dynamic programming (DP) which takes O(k m ²) time complexity, where m is the number of skyline points. Clearly, such a DP-based algorithm cannot be used for handling large scale datasets due to the quadratic time cost. To overcome this problem, in this paper, we propose a new approximate algorithm called ARS, and a new exact algorithm named PSRS, based on a carefully-designed parametric search technique. We show that the ARS algorithm can guarantee a solution that is at most ?? larger than the optimal solution. The proposed ARS and PSRS algorithms run in O(klog2mlog(T/??)) and O(k ² log3m) time respectively, where T is no more than the maximal distance between any two skyline points. We also propose an improved exact algorithm, called PSRS+, based on an effective lower and upper bounding technique. We conduct extensive experimental studies over both synthetic and real-world datasets, and the results demonstrate the efficiency and effectiveness of the proposed algorithms.     

Scalable skyline computation using a balanced pivot selection technique

Skyline queries have recently received considerable attention as an alternative decision-making operator in the database community. The conventional skyline algorithms have primarily focused on optimizing the dominance of points in order to remove non-skyline points as efficiently as possible, but have neglected to take into account the incomparability of points in order to bypass unnecessary comparisons. To design a scalable skyline algorithm, we first analyze a cost model that copes with both dominance and incomparability, and develop a novel technique to select a cost-optimal point, called a pivot point, that minimizes the number of comparisons in point-based space partitioning. We then implement the proposed pivot point selection technique in the existing sorting- and partitioning-based algorithms. For point insertions/deletions, we also discuss how to maintain the current skyline using a skytree, derived from recursive point-based space partitioning. Furthermore, we design an efficient greedy algorithm for the k representative skyline using the skytree. Experimental results demonstrate that the proposed algorithms are significantly faster than the state-of-the-art algorithms.     

A fast and progressive algorithm for skyline queries with totally- and partially-ordered domains

We devise a skyline algorithm that can efficiently mitigate the enormous overhead of processing millions of tuples on totally- and partially-ordered domains (henceforth, TODs and PODs). With massive datasets, existing techniques spend a significant amount of time on a dominance comparison because of both a large number of skyline points and the unprogressive method of skyline computing with PODs. (If data has high dimensionality, the situation is undoubtedly aggravated.) The progressiveness property turns out to be the key feature for solving all remaining problems. This article presents a FAST-SKY algorithm that deals successfully with these two obstacles and improves skyline query processing time strikingly, even with high-dimensional data. Progressive skyline evaluation with PODs is guaranteed by new index structures and topological sorting order. A stratification technique is adopted to index data on PODs, and we propose two new index structures: stratified R-trees (SR-trees) for low-dimensional data and stratified MinMax treaps (SM-treaps) for high-dimensional data. A fast dominance comparison is achieved by using a reporting query instead of a dominance query, and a dimensionality reduction technique. Experimental results suggest that in general cases (anti-correlated and uniform distributions) FAST-SKY is orders of magnitude faster than existing algorithms.     

Neural skyline filter for accelerating skyline search algorithms

The skyline search problem has been identified as one of the key problems in database research. None of the developed skyline search algorithms include the use of a filter to facilitate the search process. This paper proposes a novel modification involving the use of skyline filters to reduce the search space of a skyline problem by removing data points that cannot provide a viable skyline result. Three filters based on the concept of neural networks are proposed in this paper. The result is a reduction in execution time achieved through the reduction of the input tuples. The proposed filters may be used in conjunction with any existing skyline search algorithm. This is the first study to apply neural network technology to the skyline problem. Comprehensive simulation results demonstrate the effectiveness of the proposed skyline filtering system.     

A fast hybrid computation model for rectum deformation

It is a challenging task to realistically reproduce the complex deformation of soft bio-tissues in a surgical operation, especially when large deformations and movements exist. A hybrid model which we call the beads-on-string model is presented to handle the deformation and collision of the rectum in a virtual surgery simulation system. Specially tailored for this purpose, our model takes multiple layers to capture the dynamics of the rectum in an efficient manner. Inspired by the shape similarity between a rectum with regular bulges and a string of beads, we use a Cosserat rod model, coinciding with the centreline of the rectum, to calculate its deformation subject to external forces. We introduce rigid spheres, analogy to beads, moving along with the rod to approximate the shape of the rectum in handling collision. In addition, the beads (rigid spheres) provide a natural interlayer to map the deformation of the centreline to the associated mesh which presents detailed geometry of the rectum. Our approach is carefully crafted to achieve high computational efficiency and its multi-layer structure is designed to reproduce the physics of the deformation of the rectum.     

A communication-reduced and computation-balanced framework for fast graph computation

The bulk synchronous parallel (BSP) model is very user friendly for coding and debugging parallel graph algorithms. However, existing BSP-based distributed graph-processing frameworks, such as Pregel, GPS and Giraph, routinely suffer from high communication costs. These high communication costs mainly stem from the fine-grained message-passing communication model. In order to address this problem, we propose a new computation model with low communication costs, called LCC-BSP. We use this model to design and implement a high-performance distributed graph-processing framework called LCC-Graph. This framework eliminates high communication costs in existing distributed graph-processing frameworks. Moreover, LCC-Graph also balances the computation workloads among all compute nodes by optimizing graph partitioning, significantly reducing the computation time for each superstep. Evaluation of LCC-Graph on a 32-node cluster, driven by real-world graph datasets, shows that it significantly outperforms existing distributed graph-processing frameworks in terms of runtime, particularly when the system is supported by a high-bandwidth network. For example, LCC-Graph achieves an order of magnitude performance improvement over GPS and GraphLab.     

A novel algorithm for fast computation of Zernike moments

Zernike moments (ZMs) have been successfully used in pattern recognition and image analysis due to their good properties of orthogonality and rotation invariance. However, their computation by a direct method is too expensive, which limits the application of ZMs. In this paper, we present a novel algorithm for fast computation of Zernike moments. By using the recursive property of Zernike polynomials, the inter-relationship of the Zernike moments can be established. As a result, the Zernike moment of order n with repetition m, Z_nm, can be expressed as a combination of Z_n−2,m and Z_n−4,m. Based on this relationship, the Zernike moment Z_nm, for n>m, can be deduced from Z_mm. To reduce the computational complexity, we adopt an algorithm known as systolic array for computing these latter moments. Using such a strategy, the multiplication number required in the moment calculation of Z_mm can be decreased significantly. Comparison with known methods shows that our algorithm is as accurate as the existing methods, but is more efficient.     

图像中值滤波快速计算的符号检验法

在研究图像中值滤波及其快速算法的基础上,设计并实现了一种新的基于符号检验改进算法的中值滤波快速算法。该算法不需要对邻域内的像素值进行排序,消除了耗时的数据移动操作,从而提高了图像处理速度;同时,符号检验改进算法使用相对值作为统计量,考虑了两个总体样本完全一致的情况,解决了符号检验法的不足之处;最后将改进的符号检验法应用于图像中值滤波。算法分析与大量实验结果表明,该算法不仅大幅度提高了图像中值滤波速度,并且比其他几种快速算法更大程度地保留了图像的边缘、轮廓及纹理等各种信息。     

Practical fast computation of Zernike moments

The fast computation of Zernike moments from normalized gometric moments has been developed in this paper,The computation is multiplication free and only additions are needed to generate Zernike moments .Geometric moments are generated using Hataming‘s filter up to high orders by a very simple and straightforward computaion scheme.Other kings of monents(e.g.,Legendre,pseudo Zernike)can be computed using the same algorithm after giving the proper transformaitons that state their relations to geometric moments.Proper normaliztions of geometric moments are necessary so that the method can be used in the efficient computation of Zernike moments.To ensure fair comparisons,recursive algorithms are used to generate Zernike polynoials and other coefficients.The computaional complexity model and test programs show that the speed-up factor of the proposed algorithm is superior with respect ot other fast and /or direct computations It perhaps is the first time that Zernike moments can be computed in real time rates,which encourages the use of Zernike moment features in different image retrieval systems that support huge databases such as the XM experimental model stated for the MPEG-7 experimental core.It is concluded that choosing direct copmutation would be impractical.