Subspace methods for recovering rigid motion I: Algorithm and implementation

As an observer moves and explores the environment, the visual stimulation in his/her eye is constantly changing. Somehow he/she is able to perceive the spatial layout of the scene, and to discern his/her movement through space. Computational vision researchers have been trying to solve this problem for a number of years with only limited success. It is a difficult problem to solve because the optical flow field is nonlinearly related to the 3D motion and depth parameters.Here, we show that the nonlinear equation describing the optical flow field can be split by an exact algebraic manipulation to form three sets of equations. The first set relates the flow field to only the translational component of 3D motion. Thus, depth and rotation need not be known or estimated prior to solving for translation. Once the translation has been recovered, the second set of equations can be used to solve for rotation. Finally, depth can be estimated with the third set of equations, given the recovered translation and rotation.The algorithm applies to the general case of arbitrary motion with respect to an arbitrary scene. It is simple to compute, and it is plausible biologically. The results reported in this article demonstrate the potential of our new approach, and show that it performs favorably when compared with two other well-known algorithms.     

CBAR: an efficient method for mining association rules

The discovery of association rules is an important data-mining task for which many algorithms have been proposed. However, the efficiency of these algorithms needs to be improved to handle real-world large datasets. In this paper, we present an efficient algorithm named cluster-based association rule (CBAR). The CBAR method is to create cluster tables by scanning the database once, and then clustering the transaction records to the k-th cluster table, where the length of a record is k. Moreover, the large itemsets are generated by contrasts with the partial cluster tables. This not only prunes considerable amounts of data reducing the time needed to perform data scans and requiring less contrast, but also ensures the correctness of the mined results. Experiments with the FoodMart transaction database provided by Microsoft SQL Server show that CBAR outperforms Apriori, a well-known and widely used association rule.     

CAR-Miner: An efficient algorithm for mining class-association rules

Building a high accuracy classifier for classification is a problem in real applications. One high accuracy classifier used for this purpose is based on association rules. In the past, some researches showed that classification based on association rules (or class-association rules – CARs) has higher accuracy than that of other rule-based methods such as ILA and C4.5. However, mining CARs consumes more time because it mines a complete rule set. Therefore, improving the execution time for mining CARs is one of the main problems with this method that needs to be solved. In this paper, we propose a new method for mining class-association rule. Firstly, we design a tree structure for the storage frequent itemsets of datasets. Some theorems for pruning nodes and computing information in the tree are developed after that, and then, based on the theorems, we propose an efficient algorithm for mining CARs. Experimental results show that our approach is more efficient than those used previously.     

OWL rules: A proposal and prototype implementation

Although the OWL Web Ontology Language adds considerable expressive power to the Semantic Web it does have expressive limitations, particularly with respect to what can be said about properties. We present the Semantic Web Rule Language (SWRL), a Horn clause rules extension to OWL that overcomes many of these limitations. SWRL extends OWL in a syntactically and semantically coherent manner: the basic syntax for SWRL rules is an extension of the abstract syntax for OWL DL and OWL Lite; SWRL rules are given formal meaning via an extension of the OWL DL model-theoretic semantics; SWRL rules are given an XML syntax based on the OWL XML presentation syntax; and a mapping from SWRL rules to RDF graphs is given based on the OWL RDF/XML exchange syntax. We discuss the expressive power of SWRL, showing that the ontology consistency problem is undecidable, provide several examples of SWRL usage, and discuss a prototype implementation of reasoning support for SWRL.     

有效的矩阵加权正负关联规则挖掘算法——MWARM-SRCCCI

针对现有加权关联规则挖掘算法不能适用于矩阵加权数据的缺陷,给出一种新的矩阵加权项集剪枝策略,构建矩阵加权正负关联模式评价框架SRCCCI,提出一种新的基于SRCCCI评价框架的矩阵加权正负关联规则挖掘算法MWARM-SRCCCI。该算法克服了现有挖掘技术的缺陷,采用新的剪枝技术和模式评价方法,挖掘有效的矩阵加权正负关联规则,避免一些无效和无趣的模式产生。以中文Web测试集CWT200g为实验数据,与现有无加权正负关联规则挖掘算法比较,MWARM-SRCCCI算法的挖掘时间减幅最大可达74.74%。理论分析和实验结果表明,MWARM-SRCCCI算法具有较好的剪枝效果,候选项集数量和挖掘时间明显减少,挖掘效率得到极大提高,其关联模式可为信息检索提供可靠的查询扩展词来源。     

StatApriori: an efficient algorithm for searching statistically significant association rules

Searching statistically significant association rules is an important but neglected problem. Traditional association rules do not capture the idea of statistical dependence and the resulting rules can be spurious, while the most significant rules may be missing. This leads to erroneous models and predictions which often become expensive. The problem is computationally very difficult, because the significance is not a monotonic property. However, in this paper, we prove several other properties, which can be used for pruning the search space. The properties are implemented in the StatApriori algorithm, which searches statistically significant, non-redundant association rules. Empirical experiments have shown that StatApriori is very efficient, but in the same time it finds good quality rules.     

Decision-making coordination and efficient reasoning techniques for feature-based configuration

Software Product Lines is a contemporary approach to software development that exploits the similarities and differences within a family of systems in a particular domain of interest in order to provide a common infrastructure for deriving members of this family in a timely fashion, with high-quality standards, and at lower costs.In Software Product Lines, feature-based product configuration is the process of selecting the desired features for a given software product from a repository of features called a feature model. This process is usually carried out collaboratively by people with distinct skills and interests called stakeholders. Collaboration benefits stakeholders by allowing them to directly intervene in the configuration process. However, collaboration also raises an important side effect, i.e., the need of stakeholders to cope with decision conflicts. Conflicts arise when decisions that are locally consistent cannot be applied globally because they violate one or more constraints in the feature model.Unfortunately, current product configuration systems are typically single-user-based in the sense that they do not provide means to coordinate concurrent decision-making on the feature model. As a consequence, configuration is carried out by a single person that is in charge of representing the interests of all stakeholders and managing decision conflicts on their own. This results in an error-prone and time-consuming process that requires past decisions to be revisited continuously either to correct misinterpreted stakeholder requirements or to handle decision conflicts. Yet another challenging issue related to configuration problems is the typically high computational cost of configuration algorithms. In fact, these algorithms frequently fall into the category of NP-hard and thus can become intractable in practice.In this paper, our goal is two-fold. First, we revisit our work on Collaborative Product Configuration (CPC) in which we proposed an approach to describe and validate collaborative configuration scenarios. We discuss how collaborative configuration can be described in terms of a workflow-like plan that safely guides stakeholders during the configuration process. Second, we propose a preliminary set of reasoning algorithms tailored to the feature modelling domain that can be used to provide automated support for product configuration. In addition, we compare empirically the performance of the proposed algorithms to that of a general-purpose solution. We hope that the insights provided in this paper will encourage other researchers to develop new algorithms in the near future.     

Learning decision rules for energy efficient building control

While rule based control (RBC) is current practice in most building automation systems that issue discrete control signals, recent simulation studies suggest that advanced, optimization based control methods such as hybrid model predictive control (HMPC) can potentially outperform RBC in terms of energy efficiency and occupancy comfort. However, HMPC requires a more complex IT infrastructure and numerical optimization in the loop, which makes commissioning, operation of the building, and error handling significantly more involved than in the rule based setting. In this paper, we suggest an automated RBC synthesis procedure for binary decisions that extracts prevalent information from simulation data with HMPC controllers. The result is a set of simple decision rules that preserves much of the control performance of HMPC. The methods are based on standard machine learning algorithms, in particular support vector machines (SVMs) and adaptive boosting (AdaBoost). We consider also the ranking and selection of measurements which are used for a decision and show that this feature selection is useful in both complexity reduction and reduction of investment costs by pruning unnecessary sensors. The suggested methods are evaluated in simulation for six different case studies and shown to maintain the performance of HMPC despite a tremendous reduction in complexity.     

一种有效的基于图的关联规则挖掘算法

基于图的关联规则挖掘算法是一种通过构建关联图并直接生成候选频繁项集,进而验证得到所有频繁项集的算法。在该算法中,对候选项集的验证操作占用了大量的时间,为此提出了改进算法。改进主要体现在两个方面：按支持度降序对频繁1项重新编号再构建关联图;利用Apriori性质删减用来生成候选项集的冗余扩展项节点。实验结果表明,在最小支持度阈值较小时,改进算法有效减少了冗余的候选频繁项集,提高了算法的性能。     

Wavelet domain association rules for efficient texture classification

The wavelet domain association rules method is proposed for efficient texture characterization. The concept of association rules to capture the frequently occurring local intensity variation in textures. The frequency of occurrence of these local patterns within a region is used as texture features. Since texture is basically a multi-scale phenomenon, multi-resolution approaches such as wavelets, are expected to perform efficiently for texture analysis. Thus, this study proposes a new algorithm which uses the wavelet domain association rules for texture classification. Essentially, this work is an extension version of an early work of the Rushing et al. [10], [11], where the generation of intensity domain association rules generation was proposed for efficient texture characterization. The wavelet domain and the intensity domain (gray scale) association rules were generated for performance comparison purposes. As a result, Rushing et al. [10], [11] demonstrated that intensity domain association rules performs much more accurate results than those of the methods which were compared in the Rushing et al. work. Moreover, the performed experimental studies showed the effectiveness of the wavelet domain association rules than the intensity domain association rules for texture classification problem. The overall success rate is about 97%.     

Partial state observability recovering for linear systems by additional sensor implementation

This paper deals with the problem of additional sensor location in order to recover the observability of any given part of the state for structured linear systems. The proposed method is based on a graph-theoretic approach and assumes only the knowledge of the system’s structure. We first provide new graphical necessary and sufficient conditions for the generic partial observability. Then, we study the location of additional sensors in order to satisfy the latter conditions. We provide necessary and sufficient requirements to be satisfied by these additional sensors and all their possible locations. The proposed solution is simple to implement because it is based on well-known algorithms, usually used for finding successors and predecessors of vertex subsets or on computation of maximal linkings in a digraph. All the used algorithms have polynomial complexity orders.     

State and input observability recovering by additional sensor implementation: A graph-theoretic approach

This paper deals with the problem of additional sensor location in order to recover the state and input observability for structured linear systems. The proposed method is based on a graph-theoretic approach and assumes only the knowledge of the system’s structure. It allows one to provide the minimal number of the required sensors and either their pertinent location or a necessary and sufficient condition which allows one to check if a sensor location is adequate or not. We obtain a sensor placement procedure based on classical and well-known graph theory algorithms, which have polynomial complexity orders.     

Web service的事务协调框架研究与实现

提出并实现了一种Web服务的事务协调框架,DTCF（Distributed Transaction Coordination Framework）。该模型基于嵌套事务模型和协调思想,将局部事务的实现细节进行封装,不同局部事务可采用不同的并发控制和恢复技术,而对全局事务则采用完全分布的管理机制进行管理。DTCF是一种可重用的框架,实验结果表明其可用性。     

An efficient cluster and decomposition algorithm for mining association rules

Conventional algorithms for mining association rules operate in a combination of smaller large itemsets. This paper presents a new efficient which combines both the cluster concept and decomposition of larger candidate itemsets, while proceeds from mining the maximal large itemsets down to large 1-itemsets, named cluster-decomposition association rule (CDAR). First, the CDAR method creates some clusters by reading the database only once, and then clustering the transaction records to the kth cluster, where the length of a record is k. Then, the large k-itemsets are generated by contrasts with the kth cluster only, unlike the combination concept that contrasts with the entire database. Experiments with real-life databases show that CDAR outperforms Apriori, a well-known and widely used association rule.     

An implementation base for efficient data structuring

The specification of data structure in higher-level languages is isolated from the related specifications of data allocation and binding of names. Structure specification is claimed to be the definition of the accessing (addressing) function for items having the structure. Conventional techniques for data structure isolation in higher-level languages are examined and are found to suffer from a lack of clarity and efficiency. The means by which data structure accessors may be defined in Bliss, the specification of their association with named, allocated storage, and their automatic invocation by reference to the named storage only, are discussed. An example is presented which illustrates their efficient implementation and their utility for separating the activities, of data structure programming and algorithmic programming.This work was supported by the Advanced Research Projects Agency of the Office of the Secretary of Defense (F44620-70-C-0107) and is monitored by the Air Force Office of Scientific Research.     

Post-quantum signature schemes for efficient hardware implementation

Post-quantum cryptosystems have attracted a great interest, from researchers, latest. This work introduces two new forms of the hidden discrete logarithm problem and three new post-quantum signature schemes. The finite non-commutative associative algebras of two types are used as the algebraic support of the proposed cryptoschemes: i) containing a global two-sided unit and ii) containing a large set of global left-sided units. The illustrated FPGA implementation results, show the efficiency of the proposed cryptographic schemes, in hardware approaches. Detailed comparisons, with other security hardware implementations, are also presented.     

高效的关联规则挖掘算法研究

目前已经提出了许多用于高效地发现大规模数据库中的关联规则的算法,但都是对关联规则中满足最小支持度的频繁项集的研究,没有对频繁项集中如何高效地计算得到满足最小置信度的关联规则进行研究.针对这种情况,提出了一种高效关联规则的挖掘算法EA,解决了在挖掘关联规则过程中如何高效挖掘满足最小置信度的关联规则问题.     

XML-based genetic programming framework: design philosophy, implementation, and applications

We present the design philosophy, implementation, and various applications of an XML-based genetic programming (GP) framework (XGP). The key feature of XGP is the distinct representation of genetic programs as DOM parsing trees featuring corresponding flat XML text. XGP contributes to the achievements of: (i) fast prototyping of GP by using the standard built-in API of DOM parsers for manipulating the genetic programs, (ii) human readability and modifiability of the genetic representations, (iii) generic support for the representation of the grammar of a strongly typed GP using W3C-standardized XML schema; (iv) inherent inter-machine migratability of the text-based genetic representation (i.e., the XML text) in the distributed implementations of GP.     

一种高效的关联规则增量更新算法

对挖掘关联规则中FUP算法的关键思想以及性能进行了研究,提出了改进的FUP算法SFUP。该算法充分利用原有挖掘结果中候选频繁项集的支持数,能有效减少对数据库的重复扫描次数,并通过实验对这两种算法进行比较,结果充分说明了SFUP算法的效率要明显优于FUP算法。     

Regular and almost universal hashing: an efficient implementation

Random hashing can provide guarantees regarding the performance of data structures such as hash tables – even in an adversarial setting. Many existing families of hash functions are universal: given two data objects, the probability that they have the same hash value is low given that we pick hash functions at random. However, universality fails to ensure that all hash functions are well behaved. We might further require regularity: when picking data objects at random they should have a low probability of having the same hash value, for any fixed hash function. We present the efficient implementation of a family of non‐cryptographic hash functions (PM+) offering good running times, good memory usage, and distinguishing theoretical guarantees: almost universality and component‐wise regularity. On a variety of platforms, our implementations are comparable with the state of the art in performance. On recent Intel processors, PM+ achieves a speed of 4.7 bytes per cycle for 32‐bit outputs and 3.3 bytes per cycle for 64‐bit outputs. We review vectorization through Single Instruction on Multiple Data instructions (e.g., AVX2) and optimizations for superscalar execution. Copyright © 2016 John Wiley & Sons, Ltd.