16388639
Cardinality-based inference control in OLAP systems: an information theoretic approach
We address the inference control problem in data cubes with some data known to users through external knowledge. The goal of inference controls is to prevent exact values of sensitive data from being inferred through answers to online analytical processing (OLAP) queries. We present an information theoretic approach for cardinality-based inference control, which simply counts the number of cells that all queries have covered thus far to determine whether a new query should be answered. Compared to previous approaches in sum-only data cubes, our new approach has a more general framework (applies to MIN, MAX and SUM) and is more effective.
16331940
Optimal Parallel Routing in Star Networks
Star networks have recently been proposed as attractive alternatives to the popular hypercube for interconnecting processors on a parallel computer. In this paper, we present an efficient algorithm that constructs an optimal parallel routing in star networks. Our result improves previous results for the problem.
5242879
Interactive rind modeling
In this paper, we describe a technique, with roots in topological graph theory, that we call rind modeling. It provides for the easy creation of surfaces resembling peeled and punctured rinds. We show how the method's two main steps of: 1) creation of a shell or crust like the rind of an orange, and 2) opening holes in the crust by punching or peeling can be encapsulated into a real time semi-automatic interactive algorithm. We include a number of worked examples, some by students in a first modeling course, that demonstrate the ease with which a large variety of intricate rind shapes can be created.
1021255
A minimal and complete set of operators for the development of robust manifold mesh modelers
In this paper, we identify a minimal and complete set of fundamental operators, which is necessary and sufficient for performing all homeomorphic and topological operations on 2- manifold mesh structures. Efficient algorithms are developed for the implementation of these operators. We also developed a set of powerful, user-friendly, and effective operators at the level of user-interface. Using these operators, we have developed a prototype system for robust, interactive, and user-friendly modeling of orientable 2-manifold meshes. Users of our system can perform a large set of homeomorphic and topological changes with these user-interface level operators. Our system is topologically robust in the sense that users will never create invalid 2-manifold mesh structure with these operators. In our system, the homeomorphic and topological surgery operations can be applied alternatively on 2-manifold meshes. With our system, users can blend surfaces, construct rinds, and open holes on these rind shapes. With our system, the shapes that look like solid, non-manifold, or 2-manifold with boundary can be manipulated. The system also provides automatic texture mapping during topology changes.
2261180
Graph Ear Decompositions and Graph Embeddings
Ear decomposition of a graph has been extensively studied in relation to graph connectivity. In this paper, a connection of ear decomposition to graph embeddings is exhibited. It is shown that constructing a maximum-paired ear decomposition of a graph and constructing a maximum-genus embedding of the graph are polynomial-time equivalent. Applications of this connection are discussed.
31382426
Strong Fault-Tolerance: Parallel Routing in Networks with Faults
A d-regular network G is strongly fault-tolerant if for any copy Gf of G with at most d - 2 faulty nodes, every pair of nonfaulty nodes u and v in Gf admits min{df(u), df (v)} node-disjoint paths in Gf from u to v, where df(u) and df(v) are the degrees of the nodes u and v in Gf. We show that popular network structures, such as hypercube and star networks, are strongly fault-tolerant. We develop efficient algorithms that construct the maximum number of node-disjoint paths of optimal or nearly optimal length in these networks with faulty nodes. Our algorithms are optimal in terms of their running time.
987186
Implementing Minimized Multivariate PKC on Low-Resource Embedded Systems
Multivariate (or $\mathcal{MQ}$) public-key cryptosystems (PKC) are alternatives to traditional PKCs based on large algebraic structures (e.g., RSA and ECC); they usually execute much faster than traditional PKCs on the same hardware. However, one major challenge in implementing multivariates in embedded systems is that the key size can be prohibitively large for applications with stringent resource constraints such as low-cost smart cards, sensor networks (e.g., Berkeley motes), and radio-frequency identification (RFID). In this paper, we investigate strategies for shortening the key of a multivariate PKC. We apply these strategies to the Tame Transformation Signatures (TTS) as an example and quantify the improvement in key size and running speed, both theoretically and via implementation. We also investigate ways to save die space and energy consumption in hardware, reporting on our ASIC implementation of TTS on a TSMC 0.25μm process. Even without any key shortening, the current consumption of TTS is only 21 μA for computing a signature, using 22,000 gate equivalents and 16,000 100-kHz cycles (160 ms). With circulant-matrix key shortening, the numbers go down to 17,000 gates and 4,400 cycles (44 ms). We therefore conclude: besides representing a future-proofing investment against the emerging quantum computers, multivariates can be immediately useful in niches.
7457791
Choosing Among Alternative Futures
Non-determinism is a serious impediment to testing and debugging concurrent programs. Such programs do not execute the same way each time they are run, which can hide the presence of errors. Existing techniques use a variety of mechanisms that attempt to increase the probability of uncovering error conditions by altering the execution sequence of a concurrent program, but do not test for specific errors. This paper presents some preliminary work in deterministically executing a multithreaded program using a combination of an intermediate compiler form that identifies the set of writes of a shared variable by other threads are visible at a given read of that variable and aspect-oriented programming to control program execution. Specifically, the aspects allow a read of a shared variable to return any of the reaching definitions, where the desired definition can be selected before the program is run. As a result, we can deterministically run test cases. This work is preliminary and many issues have yet to be resolved, but we believe this idea shows some promise.
1250825
Enhancing Training Set for Face Detection
We present a novel method to enhance training set for face detection with nonlinearly generated examples from the original data. The motivation is from support vector machines (SVM) that, for classification problems, examples lying close to class boundary usually have more influence and thus are more informative than those far from the boundary. We utilize a nonlinear technique - reduced set (RS) method and a new image distance metric to generate new examples, and then add them to the original collected database to enhance it. Extensive experiments show that the proposed approach has an encouraging performance
44387886
Fuzzy logic or Lukasiewicz logic: A clarification
Abstract We discuss some issues on fuzzy logic developed by Pavelka [Z. Math. Logic 25 (1979) 45–52, 119–134, 447–464] vs. the many-valued Lukasiewicz's logic. The focus is on the proper choice of fuzzy implication operations, a question which has been addressed many times in the fuzzy research literature. Pavelka had shown in 1979 that the only natural way of formalizing fuzzy logic for truth values in the unit interval [0, 1] is by using Lukasiewicz's implication operator a → b = min {1, 1 - a + b } or some isomorphic form of it. Many other papers around the same time had attempted to formulate alternative definitions for a → b by giving intuitive justifications. There continues to be some confusion, however, even today about the right notion of fuzzy logic. Much of this confusion lies in the use of improper “an” (“or”) and the “not” operations and a misunderstanding of some of the key differences between “proofs” or inferencing in fuzzy logic and those in Lukasiewicz's logic. We point out the need for defining the strong conjunction operator “⊗” in connection with fuzzy Modus-ponens rule and why we do not need the fuzzy Syllogism inference rule. We formulate two requirements of the fuzzy implication operator, which are satisfied by Lukasiewicz's a → b , but which fail for many of the alternative definitions for “→”.
12280706
A distributed multi-agent system for collaborative information management and sharing
In this paper, we present DIAMS, a system of distributed, collaborative agents to help users access, manage, share and exchange information. A DIAMS personal agent helps its owner find information most relevant to current needs. It provides tools and utilities for users to manage their information repositories with dynamic organization and virtual views. Flexible hierarchical display is integrated with indexed query search to support effective information access. Automatic indexing methods are employed to support user queries and communication between agents.