Understanding the meaning of a shifted sky: a general framework on extending skyline query

Skyline queries are often used on data sets in multi-dimensional space for many decision-making applications. Traditionally, an object p is said to dominate another object q if, for all dimensions, it is no worse than q and is better on at least one dimension. Therefore, the skyline of a data set consists of all objects not dominated by any other object. To better cater to application requirements such as controlling the size of the skyline or handling data sets that are not well-structured, various works have been proposed to extend the definition of skyline based on variants of the dominance relationship. In view of the proliferation of variants, in this paper, a generalized framework is proposed to guide the extension of skyline query from conventional definition to different variants. Our framework explicitly and carefully examines the various properties that should be preserved in a variant of the dominance relationship so that: (1) maintaining original advantages, while extending adaptivity to application semantics, and (2) keeping computational complexity almost unaffected. We prove that traditional dominance is the only relationship satisfying all desirable properties, and present some new dominance relationships by relaxing some of the properties. These relationships are general enough for us to design new top-k skyline queries that return robust results of a controllable size. We analyze the existing skyline algorithms based on their minimum requirements on dominance properties. We also extend our analysis to data sets with missing values, and present extensive experimental results on the combinations of new dominance relationships and skyline algorithms.     

Dynamic reordering of alternatives for definite logic programs

Due to their highly declarative nature and efficiency, tabled logic programming systems have been applied to solving many complex problems. Tabled logic programming is essential for extending traditional logic programming with tabled resolution. In this paper, we propose a new tabled resolution scheme, called dynamic reordering of alternatives (DRA) resolution, for definite logic programs. The scheme keeps track of the type of the subgoals during resolution; if the subgoal in the current resolvent is a variant of a former tabled subgoal, tabled answers are used to resolve the subgoal; otherwise, program clauses are used similar to SLD resolution. Program clauses leading to variant subgoals at runtime are dynamically reordered for further computation until the subgoals are completely evaluated. DRA resolution allows query evaluation to be performed in a depth-first, left-to-right traversal order similar to Prolog-typed SLD resolution, thus yielding a simple technique for incorporating tabled resolution in traditional logic programming systems. We show the correctness of DRA resolution.     

Solving Failing Queries through Cooperation and Collaboration

Sometime Query Answering Systems (QAS) for a Distributed Autonomous Information System (DAIS) may fail by returning the empty set of objects as an answer for a query q. Systems in DAIS can be incomplete, have hierarchical attributes, and the semantics of attributes and their values may differ between sites. Also, if there are no objects in S matching q, the query may fail when submitted to S. Alternatively, QAS for S may try to relax the query q as it was proposed in T. Gaasterland (IEEE Expert, 12(5), 1997, 48–59), P. Godfrey (International Journal of Cooperative Information Systems, 6(2), 1997, 95–149) and W. Chu et al. (Journal of Intelligent Information Systems, 6(2/3), 1996, 223–259). It means that q can be replaced by a new more general query. Clearly, the goal is to find possibly the smallest generalization of q which will not fail in S. Smaller generalizations guarantee higher confidence in objects returned by QAS. Such QAS is called cooperative (only one site is involved). Queries may also fail in S when some of the attributes listed in q are outside the domain of S. To resolve this type of queries, assuming that S is a part of DAIS, we may extract definitions of such attributes from information systems residing at some of the remote sites for S and next use them to approximate q in S. In order to do that successfully, we assume that all involved systems have to agree on the ontology of some of their common attributes Z.W. Raś and A. Dardzińska (Information Systems International Journal, 29(1), 2004, 47–58; Proceedings of FQAS 2004 Conference, LNCS/LNAI No. 3055, 2004, pp. 125–136); Z.W. Raś and S. Joshi, Fundamenta Informaticae Journal, 30(3/4), 1997, 313–324. QAS based on the above strategy is called collaborative (minimum two sites are involved). Similarly, a query may fail in S when the granularity of an attribute used in q is finer than the granularity of the same attribute in S. This paper shows how to use collaboration and cooperation approach to solve failing queries in DAIS assuming that attributes are hierarchical. Some aspects of a collaboration strategy dealing with failing query problem for non-hierarchical attributes have been presented in Z.W. Raś and A. Dardzińska (Information Systems International Journal, 29(1), 2004, 47–58; Proceedings of FQAS 2004 Conference, LNCS/LNAI No. 3055, 2004, pp. 125–136).     

A comparative analysis of algorithms for fast computation of Zernike moments

This paper details a comparative analysis on time taken by the present and proposed methods to compute the Zernike moments, Z_pq. The present method comprises of Direct, Belkasim's, Prata's, Kintner's and Coefficient methods. We propose a new technique, denoted as q-recursive method, specifically for fast computation of Zernike moments. It uses radial polynomials of fixed order p with a varying index q to compute Zernike moments. Fast computation is achieved because it uses polynomials of higher index q to derive the polynomials of lower index q and it does not use any factorial terms. Individual order of moments can be calculated independently without employing lower- or higher-order moments. This is especially useful in cases where only selected orders of Zernike moments are needed as pattern features. The performance of the present and proposed methods are experimentally analyzed by calculating Zernike moments of orders 0 to p and specific order p using binary and grayscale images. In both the cases, the q-recursive method takes the shortest time to compute Zernike moments.     

Some q‐Rung Orthopai Fuzzy Bonferroni Mean Operators and Their Application to Multi‐Attribute Group Decision Making

In the real multi‐attribute group decision making (MAGDM), there will be a mutual relationship between different attributes. As we all know, the Bonferroni mean (BM) operator has the advantage of considering interrelationships between parameters. In addition, in describing uncertain information, the eminent characteristic of q‐rung orthopair fuzzy sets (q‐ROFs) is that the sum of the qth power of the membership degree and the qth power of the degrees of non‐membership is equal to or less than 1, so the space of uncertain information they can describe is broader. In this paper, we combine the BM operator with q‐rung orthopair fuzzy numbers (q‐ROFNs) to propose the q‐rung orthopair fuzzy BM (q‐ROFBM) operator, the q‐rung orthopair fuzzy weighted BM (q‐ROFWBM) operator, the q‐rung orthopair fuzzy geometric BM (q‐ROFGBM) operator, and the q‐rung orthopair fuzzy weighted geometric BM (q‐ROFWGBM) operator, then the MAGDM methods are developed based on these operators. Finally, we use an example to illustrate the MAGDM process of the proposed methods. The proposed methods based on q‐ROFWBM and q‐ROFWGBM operators are very useful to deal with MAGDM problems.     

Efficiently preconditioned inexact Newton methods for large symmetric eigenvalue problems

In this paper, we propose an efficiently preconditioned Newton method for the computation of the leftmost eigenpairs of large and sparse symmetric positive definite matrices. A sequence of preconditioners based on the BFGS update formula is proposed, for the preconditioned conjugate gradient solution of the linearized Newton system to solve Au=q(u) u, q(u) being the Rayleigh quotient. We give theoretical evidence that the sequence of preconditioned Jacobians remains close to the identity matrix if the initial preconditioned Jacobian is so. Numerical results onto matrices arising from various realistic problems with size up to one million unknowns account for the efficiency of the proposed algorithm which reveals competitive with the Jacobi–Davidson method on all the test problems.     

A hybrid data envelopment analysis and multi-attribute decision making approach to sustainability assessment

The concept of sustainability consists of three main dimensions: environmental, techno-economic, and social. Measuring the sustainability status of a system or technology is a significant challenge, especially when it needs to consider a large number of attributes in each dimension of sustainability. In this study, we first propose a hybrid approach, involving data envelopment analysis (DEA) and a multi-attribute decision making (MADM) methodologies, for computing an index for each dimension of sustainability, and then we define the overall sustainability index as the mean of the three measured indexes. Towards this end, we define new concepts of efficiency and cross-efficiency of order (p, q) where p and q are the number of inputs and outputs, respectively. For a given (p, q) , we address the problem of finding efficiency of order (p, q) by developing a novel DEA-based selecting method. Finally, we define the sustainability index as a weighted sum of all possible cross-efficiencies of order (p, q) . Form a computational viewpoint, the proposed selecting model significantly decreases the computational burden in comparison with the successive solving of traditional DEA models. A case study of the electricity-generation technologies in the United Kingdom is taken as a real-world example to illustrate the potential application of our method.     

q-Rung orthopair fuzzy sets-based decision-theoretic rough sets for three-way decisions under group decision making

As an extension of Pythagorean fuzzy sets, the q-rung orthopair fuzzy sets (q-ROFSs) can easily solve uncertain information in a broader perspective. Considering the fine property of q-ROFSs, we introduce q-ROFSs into decision-theoretic rough sets (DTRSs) and use it to portray the loss function. According to the Bayesian decision procedure, we further construct a basic model of q-rung orthopair fuzzy decision-theoretic rough sets (q-ROFDTRSs) under the q-rung orthopair fuzzy environment. At the same time, we design the corresponding method for the deduction of three-way decisions by utilizing projection-based distance measures and TOPSIS. Then, we extend q-ROFDTRSs to adapt the group decision-making (GDM) scenario. To fuse different experts’ evaluation results, we propose some new aggregation operators of q-ROFSs by utilizing power average (PA) and power geometric (PG) operators, that is, q-rung orthopair fuzzy power average, q-rung orthopair fuzzy power weighted average (q-ROFPWA), q-rung orthopair fuzzy power geometric, and q-rung orthopair fuzzy power weighted geometric (q-ROFPWG). In addition, with the aid of q-ROFPWA and q-ROFPWG, we investigate three-way decisions with q-ROFDTRSs under the GDM situation. Finally, we give the example of a rural e-commence GDM problem to illustrate the application of our proposed method and verify our results by conducting two comparative experiments.     

A new approach for preference-based argumentation frameworks

Dung’s argumentation framework consists of a set of arguments and an attack relation among them. Arguments are evaluated and acceptable sets of them, called extensions, are computed using a given semantics. Each extension represents a coherent position. In the literature, several proposals have extended this framework in order to take into account the strength of arguments. The basic idea is to ignore an attack if the attacked argument is stronger than (or preferred to) its attacker. Semantics are then applied using only the remaining attacks. In this paper, we show that those proposals behave correctly when the attack relation is symmetric. However, when it is asymmetric, conflicting extensions may be computed leading to unintended conclusions. We propose an approach that guarantees conflict-free extensions. This approach presents two novelties: the first one is that it takes into account preferences at the semantics level rather than the attack level. The idea is to extend existing semantics with preferences. In case preferences are not available or do not conflict with the attacks, the extensions of the new semantics coincide with those of the basic ones. The second novelty of our approach is that a semantics is defined as a dominance relation on the powerset of the set of arguments. The extensions (under a semantics) are the maximal elements of the dominance relation. Such an approach makes it possible not only to compute the extensions of a framework but also to compare its non-extensions. We start by proposing three dominance relations that generalize respectively stable, preferred and grounded semantics with preferences. Then, we focus on stable semantics and provide full characterizations of its dominance relations and those of its generalized versions. Complexity results are provided. Finally, we show that an instance of the proposed framework retrieves the preferred sub-theories which were proposed in the context of handling inconsistency in weighted knowledge bases.     

How should Prolog computation Be represented for practical use?

We propose a visual computation model called theBox and Plane Model (BPM), which visually clarifies the semantics of backtracking, the cut operator, and side-effects, thus allowing the procedural features of Prolog to be grasped. On the bases of the BPM, we developed a visual debugger for Prolog, PROEDIT2, which has proved that this kind of pragmatic computation model for Prolog increases the efficiency of the debugging work.     

Parameterized real-time moment computation on gray images using block techniques

Moments constitute a well-known tool in the field of image analysis and pattern recognition, but they suffer from the drawback of high computational cost. Efforts for the reduction of the required computational complexity have been reported, mainly focused on binary images, but recently some approaches for gray images have been also presented. In this study, we propose a simple but effective approach for the computation of gray image moments. The gray image is decomposed in a set of binary images. Some of these binary images are substituted by an ideal image, which is called “half-intensity” image. The remaining binary images are represented using the image block representation concept and their moments are computed fast using block techniques. The proposed method computes approximated moment values with an error of 2–3% from the exact values and operates in real time (i.e., video rate). The procedure is parameterized by the number m of “half-intensity” images used, which controls the approximation error and the speed gain of the method. The computational complexity is O(kL ²), where k is the number of blocks and L is the moment order.     

Re-examination of interestingness measures in pattern mining: a unified framework

Numerous interestingness measures have been proposed in statistics and data mining to assess object relationships. This is especially important in recent studies of association or correlation pattern mining. However, it is still not clear whether there is any intrinsic relationship among many proposed measures, and which one is truly effective at gauging object relationships in large data sets. Recent studies have identified a critical property, null-(transaction) invariance, for measuring associations among events in large data sets, but many measures do not have this property. In this study, we re-examine a set of null-invariant interestingness measures and find that they can be expressed as the generalized mathematical mean, leading to a total ordering of them. Such a unified framework provides insights into the underlying philosophy of the measures and helps us understand and select the proper measure for different applications. Moreover, we propose a new measure called Imbalance Ratio to gauge the degree of skewness of a data set. We also discuss the efficient computation of interesting patterns of different null-invariant interestingness measures by proposing an algorithm, GAMiner, which complements previous studies. Experimental evaluation verifies the effectiveness of the unified framework and shows that GAMiner speeds up the state-of-the-art algorithm by an order of magnitude.     

Single variable differential calculus under q-rung orthopair fuzzy environment: Limit,derivative, chain rules,and its application

The q-rung orthopair fuzzy set ( q-ROFS) that the sum of the qth power of the membership degree and the qth power of the nonmembership degree is restricted to one is a generalization of fuzzy set (FS). Recently, many researchers have given a series of aggregation operators to fuse q-rung orthopair fuzzy discrete information. Subsequently, although some scholars have also focused on studying q-rung orthopair fuzzy continuous information and give its continuity, derivative, differential, and integral, those studies are only considered from the perspective of multivariable fuzzy functions. Thus, the main aim of the paper is to study the q-rung orthopair fuzzy continuous single variable information. In this paper, we first define the concept of q-rung orthopair single variable fuzzy function ( q-ROSVFF) to describe the fuzzy continuous information, and give its domain to make sure that this kind of function is meaningful. Afterward, we propose the limits, continuities, and infinitesimal of q-ROSVFFs, and offer the relationship between the limit of q-ROSVFF and that of q-ROSVFF infinitesimal. On the basis of the definition of derivative in mathematical analysis, we define the subtraction and division derivatives and basic operational rules, and offer the simpler proofs for the derivatives of q-ROSVFFs. What is more, we propose the subtraction and division differential invariances, and give the approximate calculation formulas of q-ROSVFFs when the value of independent variable is changed small enough. In the real situation, fundamental functions cannot be used to express more complicated functions, thus we define the compound q-ROSVFFs and give their chain rules of subtraction and division derivatives. Finally, we use numerical examples by simulation to verify the feasibility and veracity of the approximate calculation on q-ROSVFFs.     

Modelling relational statistics with Bayes Nets

Class-level models capture relational statistics over object attributes and their connecting links, answering questions such as “what is the percentage of friendship pairs where both friends are women?” Class-level relationships are important in themselves, and they support applications like policy making, strategic planning, and query optimization. We represent class statistics using Parametrized Bayes Nets (PBNs), a first-order logic extension of Bayes nets. Queries about classes require a new semantics for PBNs, as the standard grounding semantics is only appropriate for answering queries about specific ground facts. We propose a novel random selection semantics for PBNs, which does not make reference to a ground model, and supports class-level queries. The parameters for this semantics can be learned using the recent pseudo-likelihood measure (Schulte in SIAM SDM, pp. 462–473, 2011) as the objective function. This objective function is maximized by taking the empirical frequencies in the relational data as the parameter settings. We render the computation of these empirical frequencies tractable in the presence of negated relations by the inverse Möbius transform. Evaluation of our method on four benchmark datasets shows that maximum pseudo-likelihood provides fast and accurate estimates at different sample sizes.     

Some q-rung orthopair uncertain linguistic aggregation operators and their application to multiple attribute group decision making

q-Rung orthopair fuzzy sets (q-ROFSs), originally presented by Yager, are a powerful fuzzy information representation model, which generalize the classical intuitionistic fuzzy sets and Pythagorean fuzzy sets and provide more freedom and choice for decision makers (DMs) by allowing the sum of the $q\mathrm{t}\mathrm{h}$ power of the membership and the $q\mathrm{t}\mathrm{h}$ power of the nonmembership to be less than or equal to 1. In this paper, a new class of fuzzy sets called q-rung orthopair uncertain linguistic sets (q-ROULSs) based on the q-ROFSs and uncertain linguistic variables (ULVs) is proposed, and this can describe the qualitative assessment of DMs and provide them more freedom in reflecting their belief about allowable membership grades. On the basis of the proposed operational rules and comparison method of q-ROULSs, several q-rung orthopair uncertain linguistic aggregation operators are developed, including the q-rung orthopair uncertain linguistic weighted arithmetic average operator, the q-rung orthopair uncertain linguistic ordered weighted average operator, the q-rung orthopair uncertain linguistic hybrid weighted average operator, the q-rung orthopair uncertain linguistic weighted geometric average operator, the q-rung orthopair uncertain linguistic ordered weighted geometric operator, and the q-rung orthopair uncertain linguistic hybrid weighted geometric operator. Then, some desirable properties and special cases of these new operators are also investigated and studied, in particular, some existing intuitionistic fuzzy aggregation operators and Pythagorean fuzzy aggregation operators are proved to be special cases of these new operators. Furthermore, based on these proposed operators, we develop an approach to solve the multiple attribute group decision making problems, in which the evaluation information is expressed as q-rung orthopair ULVs. Finally, we provide several examples to illustrate the specific decision-making steps and explain the validity and feasibility of two methods by comparing with other methods.     

Direct dominance of points

Several transitive relations of geometrical objects (like inclusion of intervals on a line or polygons in the plain), which are important in VLSI design applications, can be translated into the dominance relation a dominates b iff (a ≠ b and a _j ≧ b _j for j = 1,…d) of points a = (a ₁,...,a _d ),b = (b ₁,…b _d ) in R ^d by representing the objects as points in a suitable way. If only the transitive reduction (see [7]) of the given relation is required and not all the implications by transitivity, one can restrict oneself to the direct dominances in the corresponding point set N; here a dominates b directly means that a dominates b and there is no—with respect to dominance—intermediate c in N (see [5]). To estimate the advantage of this restriction, information about the numbers of dominant and directly dominant pairs in a set of n points is required, both numbers essentially depending upon how the points are distributed in R ^d . In this paper we assume the n points in question to be identically and independently distributed; then we can expect q·n·(n–1) dominance pairs. For a certain class of distributions including the uniform distribution we prove the theorem, that the expected number of direct dominance pairs is asymptotically equal to 1/(d?1)! · n1n ^{d ? 1}(n). Hence algorithms which compute only the direct dominances instead of all dominances are worth to be considered.     

A dual‐band dual‐polarized cubical DRA coupled with new modified cross‐shaped slot for ISM (2.4 GHz) and Wi‐MAX (3.3‐3.6 GHz) band applications

In this article, a new modified cross‐shaped coupled cubical dielectric resonator antenna (DRA) has been investigated for dual‐band dual‐polarized applications. The linearly polarized (LP) fields in DRA has been generated by using a single slot in the ground plane and kept at either 45° (S_L1) or ?45° (S_L2) from the microstrip feed line. Combining these two slots (S_L1 and S_L2) in the modified ground plane, the proposed structure able to generate circularly polarized (CP) field in DRA. But the generated CP field is not enough to cover ISM 2400 band. To achieve CP in ISM 2400 band, an extra slot (S_L3) to the existing slots and an extra strip (S_T) in the circular ring feed line have been included. This modified final antenna arrangement has been able to produce LP (due to loading effect, ie, slot and DRA) and CP fields (orthogonal modes have been generated, ie, TE ^x₁₁₁ and TE ^y₁₁₁), simultaneously. The measured CP and LP, ?10 dB impedance bandwidths are 11.85% (2.38‐2.68 GHz) and 9.11% (3.25‐3.56 GHz) in combination with the 3‐dB axial ratio bandwidth of 4.11% (2.38‐2.48 GHz). The generated CP and LP fields are used for different wireless communication bands such as ISM 2400 and Wi‐MAX (3.3‐3.7 GHz) bands.     

Efficient parallel edge-centric approach for relaxed graph pattern matching

Prior algorithms on graph simulation for distributed graphs are not scalable enough as they exhibit heavy message passing. Moreover, they are dependent on the graph partitioning quality that can be a bottleneck due to the natural skew present in real-world data. As a result, their degree of parallelism becomes limited. In this paper, we propose an efficient parallel edge-centric approach for distributed graph pattern matching. We design a novel distributed data structure called ST that allows a fine-grain parallelism, and hence guarantees linear scalability. Based on ST, we develop a parallel graph simulation algorithm called PGSim. Furthermore, we propose PDSim, an edge-centric algorithm that efficiently evaluates dual simulation in parallel. PDSim combines ST and PGSim in a Split-and-Combine approach to accelerate the computation stages. We prove the effectiveness and efficiency of these propositions through theoretical guarantees and extensive experiments on massive graphs. The achieved results confirm that our approach outperforms existing algorithms by more than an order of magnitude.

     

基于谱回归判别分析的LPP算法

判别局部保持投影DLPP算法在计算过程中需要解决稠密矩阵特征分解问题,这使得该算法在时间和内存上消耗都非常高。谱回归判别分析SRDA算法可以有效的节省时间和内存的消耗。基于SRDA,提出一种改进的局部保持投影LPP算法——谱回归判别局部保持投影算法SRDLPP。实验结果表明,该算法可以提高识别率,同时降低时间和内存消耗。