Generalized triangular norm and conorm aggregation operators on ordinal spaces

We describe the basic features of the t-norm operator and then introduce a family of t-norm operators that are defined on an ordinal space. We then do the same for the t-conorms. We note the strong limitation that the requirement of associativity places on the t-norm and t-conorm operators. We particularly note how it limits our ability to model different types of reinforcement. We then define a generalization of the t-conorm aggregation operator, which relaxes the requirement of associativity, we denote these operators as GENOR operators. We show that these operators have the same functionality as the t-conorm. We provide some examples of GENOR operators which allow us to control the reinforcement process. We define a related extension for the t-norm, the GENAND operator and provide some examples.     

关于无个人公钥的群认证

群认证是一种多方认证机制,研究动态群的成员们如何确认每个成员身份的真实性。这里,群组成员没有个人公钥。本文首先分析了Harn的群认证方案,证明他的方案在有意义的参数下是不安全的。我们还研究了群认证和几个多方签名之间的关系。我们证明基于身份的多重签名可以转换为安全群认证协议,而门限签名方案没有这种特性。我们还证明,如果去掉签名消息的话,Bellare和Neven的基于ID的多重签名方案实际上就是一个安全的群认证协议。     

MIQP‐based Layout Design for Building Interiors

We propose a hierarchical framework for the generation of building interiors. Our solution is based on a mixed integer quadratic programming (MIQP) formulation. We parametrize a layout by polygons that are further decomposed into small rectangles. We identify important high‐level constraints, such as room size, room position, room adjacency, and the outline of the building, and formulate them in a way that is compatible with MIQP and the problem parametrization. We also propose a hierarchical framework to improve the scalability of the approach. We demonstrate that our algorithm can be used for residential building layouts and can be scaled up to large layouts such as office buildings, shopping malls, and supermarkets. We show that our method is faster by multiple orders of magnitude than previous methods.     

Success rate of interpolation in subsegment prediction

We consider the accuracy of linear interpolation in predicting which subsegment contains a random key, given that the key is contained in a particular segment consisting of a fixed number of subsegments. We assume that keys are stored in a file in sorted order, that the file is divided into fixed-size segments, and that the first key in the segment containing the desired key is known, as is the first key of the next segment. We present empirical results for real files in which keys are social security numbers, names and telephone numbers, and for files of keys generated randomly from the uniform and from the exponential distributions. We present a theoretical analysis of the average success rate for the case in which keys are uniformly distributed. We show that the success rate depends on the number of subsegments in a segment, the size of a subsegment, and the distribution of keys, and that it is much higher than for random guessing. We describe practical applications in which this technique can be efficiently used.     

Scalable pattern mining with Bayesian networks as background knowledge

We study a discovery framework in which background knowledge on variables and their relations within a discourse area is available in the form of a graphical model. Starting from an initial, hand-crafted or possibly empty graphical model, the network evolves in an interactive process of discovery. We focus on the central step of this process: given a graphical model and a database, we address the problem of finding the most interesting attribute sets. We formalize the concept of interestingness of attribute sets as the divergence between their behavior as observed in the data, and the behavior that can be explained given the current model. We derive an exact algorithm that finds all attribute sets whose interestingness exceeds a given threshold. We then consider the case of a very large network that renders exact inference unfeasible, and a very large database or data stream. We devise an algorithm that efficiently finds the most interesting attribute sets with prescribed approximation bound and confidence probability, even for very large networks and infinite streams. We study the scalability of the methods in controlled experiments; a case-study sheds light on the practical usefulness of the approach.     

A reindexing based approach towards mapping of DAG with affine schedules onto parallel embedded systems

We address the problem of optimally mapping uniform DAGs to systolic arrays, given an affine timing function. We introduce an automatic allocation method based on a preprocessing by reindexing that transforms the initial DAG into a new one that enables the well known projection method to minimize the number of processors along a number of directions. We demonstrate its superiority to other methods, and establish the space-optimality of the proposed method. We also show an upper bound on the number of processors that corresponds to the best space complexity that both the projection method, and the so-called grouping method can give for the initial DAG. We also describe how the new allocation method can be implemented in tools.     

Automatic interpretation of loosely encoded input

Knowledge-based systems are often brittle when given unanticipated input, i.e. assertions or queries that misalign with the ontology of the knowledge base. We call such misalignments “loose speak”. We found that loose speak occurs frequently in interactions with knowledge-based systems, but with such regularity that it often can be interpreted and corrected algorithmically. We also found that the common types of loose speak, such as metonymy and noun-noun compounds, have a common root cause. We created a Loose-Speak Interpreter and evaluated it with a variety of empirical studies in different domains and tasks. We found that a single, parsimonious algorithm successfully interpreted numerous manifestations of loose speak with an average precision of 98% and an average recall of 90%.     

Collaborative Robot Exploration and Rendezvous: Algorithms, Performance Bounds and Observations

We consider the problem of how two heterogeneous robots can arrange to meet in an unknown environment from unknown starting locations: that is, the problem of arranging a robot rendezvous. We are interested, in particular, in allowing two robots to rendezvous so that they can collaboratively explore an unknown environment. Specifically, we address the problem of how a pair of exploring agents that cannot communicate with one another over long distances can meet if they start exploring at different unknown locations in an unknown environment.We propose several alternative algorithms that robots could use in attempting to rendezvous quickly while continuing to explore. These algorithms exemplify different classes of strategy whose relative suitability depends on characteristics of the problem definition. We consider the performance of our proposed algorithms analytically with respect to both expected- and worst-case behavior. We then examine their behavior under a wider set of conditions using both numerical analysis and also a simulation of multi-agent exploration and rendezvous. We examine the exploration speed, and show that a multi-robot system can explore an unknown environment faster than a single-agent system, even with the constraint of performing rendezvous to allow communication.We conclude with a demonstration of rendezvous implemented on a pair of actual robots.     

On visualizing large multidimensional datasets with a multi-threaded radial approach

In this paper, we study how to visualize large amounts of multidimensional data with a radial visualization. For such a visualization, we study a multi-threaded implementation on the CPU and the GPU. We start by reviewing the approaches that have visualized the largest multidimensional datasets and we focus on the approaches that have used CPU or GPU parallelization. We consider the radial visualizations and we describe our approach (called POIViz) that uses points of interest to determine a layout of a large dataset. We detail its parallelization on the CPU and the GPU. We study the efficiency of this approach with different configurations and for large datasets. We show that it can visualize, in less than one second, millions of data with tens of dimensions, and that it can support “real-time” interactions even for large datasets. We conclude on the advantages and limits of the proposed visualization.