OpenRaiser/Intern-Atlas huggingface dataset:
A Cognitive Mind-map Framework to Foster Trust
Venue: arXiv cs.AI 2009
Year: 2009

The explorative mind-map is a dynamic framework, that emerges automatically from the input, it gets. It is unlike a verificative modeling system where existing (human) thoughts are placed and connected together. In this regard, explorative mind-maps change their size continuously, being adaptive with connectionist cells inside; mind-maps process data input incrementally and offer lots of possibilities to interact with the user through an appropriate communication interface. With respect to a cognitive motivated situation like a conversation between partners, mind-maps become interesting as they are able to process stimulating signals whenever they occur. If these signals are close to an own understanding of the world, then the conversational partner becomes automatically more trustful than if the signals do not or less match the own knowledge scheme. In this (position) paper, we therefore motivate explorative mind-maps as a cognitive engine and propose these as a decision support engine to foster trust.
Optimal Geometric Partitions, Covers and K-Centers
Venue: arXiv cs.DS 2009
Year: 2009

In this paper we present some new, practical, geometric optimization techniques for computing polygon partitions, 1D and 2D point, interval, square and rectangle covers, as well as 1D and 2D interval and rectangle K-centers. All the techniques we present have immediate applications to several cost optimization and facility location problems which are quite common in practice. The main technique employed is dynamic programming, but we also make use of efficient data structures and fast greedy algorithms.
Bit-Interleaved Coded Multiple Beamforming with Constellation Precoding
Venue: arXiv cs.IT 2009
Year: 2009

In this paper, we present the diversity order analysis of bit-interleaved coded multiple beamforming (BICMB) combined with the constellation precoding scheme. Multiple beamforming is realized by singular value decomposition of the channel matrix which is assumed to be perfectly known to the transmitter as well as the receiver. Previously, BICMB is known to have a diversity order bound related with the product of the code rate and the number of parallel subchannels, losing the full diversity order in some cases. In this paper, we show that BICMB combined with the constellation precoder and maximum likelihood detection achieves the full diversity order. We also provide simulation results that match the analysis.
Overlapping Multi-hop Clustering for Wireless Sensor Networks
Venue: arXiv cs.NI 2009
Year: 2009

Clustering is a standard approach for achieving efficient and scalable performance in wireless sensor networks. Traditionally, clustering algorithms aim at generating a number of disjoint clusters that satisfy some criteria. In this paper, we formulate a novel clustering problem that aims at generating overlapping multi-hop clusters. Overlapping clusters are useful in many sensor network applications, including inter-cluster routing, node localization, and time synchronization protocols. We also propose a randomized, distributed multi-hop clustering algorithm (KOCA) for solving the overlapping clustering problem. KOCA aims at generating connected overlapping clusters that cover the entire sensor network with a specific average overlapping degree. Through analysis and simulation experiments we show how to select the different values of the parameters to achieve the clustering process objectives. Moreover, the results show that KOCA produces approximately equal-sized clusters, which allows distributing the load evenly over different clusters. In addition, KOCA is scalable; the clustering formation terminates in a constant time regardless of the network size.
Diagrammatic logic applied to a parameterization process
Venue: arXiv cs.LO 2009
Year: 2009

This paper provides an abstract definition of some kinds of logics, called diagrammatic logics, together with a definition of morphisms and of 2-morphisms between diagrammatic logics. The definition of the 2-category of diagrammatic logics rely on category theory, mainly on adjunction, categories of fractions and limit sketches. This framework is applied to the formalization of a parameterization process. This process, which consists in adding a formal parameter to some operations in a given specification, is presented as a morphism of logics. Then the parameter passing process, for recovering a model of the given specification from a model of the parameterized specification and an actual parameter, is seen as a 2-morphism of logics.
An improved axiomatic definition of information granulation
Venue: arXiv cs.AI 2009
Year: 2009

To capture the uncertainty of information or knowledge in information systems, various information granulations, also known as knowledge granulations, have been proposed. Recently, several axiomatic definitions of information granulation have been introduced. In this paper, we try to improve these axiomatic definitions and give a universal construction of information granulation by relating information granulations with a class of functions of multiple variables. We show that the improved axiomatic definition has some concrete information granulations in the literature as instances.
Performance Analysis over Slow Fading Channels of a Half-Duplex Single-Relay Protocol: Decode or Quantize and Forward
Venue: arXiv cs.IT 2009
Year: 2009

In this work, a new static relaying protocol is introduced for half duplex single-relay networks, and its performance is studied in the context of communications over slow fading wireless channels. The proposed protocol is based on a Decode or Quantize and Forward (DoQF) approach. In slow fading scenarios, two performance metrics are relevant and complementary, namely the outage probability gain and the Diversity-Multiplexing Tradeoff (DMT). First, we analyze the behavior of the outage probability P_o associated with the proposed protocol as the SNR tends to infinity. In this case, we prove that SNR^2 P_o converges to a constant. We refer to this constant as the outage gain and we derive its closed-form expression for a general class of wireless channels that includes the Rayleigh and the Rice channels as particular cases. We furthermore prove that the DoQF protocol has the best achievable outage gain in the wide class of half-duplex static relaying protocols. A method for minimizing the outage gain with respect to the power distribution between the source and the relay, and with respect to the durations of the slots is also provided. Next, we focus on Rayleigh distributed fading channels to derive the DMT associated with the proposed DoQF protocol. Our results show that the DMT of DoQF achieves the 2 by 1 MISO upper-bound for multiplexing gains r < 0.25.
Experimental Performances Analysis of Load Balancing Algorithms in IEEE 802.11
Venue: arXiv cs.PF 2009
Year: 2009

In IEEE 802.11, load balancing algorithms (LBA) consider only the associated stations to balance the load of the available access points (APs). However, although the APs are balanced, it causes a bad situation if the AP has a lower signal length (SNR) less than the neighbor APs. So, balance the load and associate one mobile station to an access point without care about the signal to noise ratio (SNR) of the AP cause possibly an unforeseen QoS, such as the bit rate, the end to end delay, the packet loss. In this way, we study an improvement load balancing algorithm with SNR integration at the selection policy.
Automated Composition of Security Protocols
Venue: arXiv cs.CR 2009
Year: 2009

Determining if two protocols can be securely composed requires analyzing not only their additive properties but also their destructive properties. In this paper we propose a new composition method for constructing protocols based on existing ones found in the literature that can be fully automatized. The additive properties of the composed protocols are ensured by the composition of protocol preconditions and effects, denoting, respectively, the conditions that must hold for protocols to be executed and the conditions that hold after executing the protocols. The non-destructive property of the final composed protocol is verified by analyzing the independence of the involved protocols, a method proposed by the authors in their previous work. The fully automatized property is ensured by constructing a rich protocol model that contains explicit description of protocol preconditions, effects, generated terms and exchanged messages. The proposed method is validated by composing 17 protocol pairs and by verifying the correctness of the composed protocols with an existing tool.
Additivity of on-line decision complexity is violated by a linear term in the length of a binary string
Venue: arXiv cs.IT 2009
Year: 2009

We show that there are infinitely many binary strings z, such that the sum of the on-line decision complexity of predicting the even bits of z given the previous uneven bits, and the decision complexity of predicting the uneven bits given the previous event bits, exceeds the Kolmogorov complexity of z by a linear term in the length of z.
Constraint Minimum Vertex Cover in K Partite Graph, Approximation Algorithm and Complexity Analysis
Venue: arXiv cs.DS 2009
Year: 2009

Generally, a graph G, an independent set is a subset S of vertices in G such that no two vertices in S are adjacent (connected by an edge) and a vertex cover is a subset S of vertices such that each edge of G has at least one of its endpoints in S. Again, the minimum vertex cover problem is to find a vertex cover with the smallest number of vertices. This study shows that the constrained minimum vertex cover problem in k-partite graph (MIN CVCK) is NP-Complete which is an important property of k partite graph. Many combinatorial problems on general graphs are NP-complete, but when restricted to k partite graph with at most k vertices then many of these problems can be solved in polynomial time. This paper also illustrates an approximation algorithm for MIN CVCK and analyzes its complexity. In future work section, we specified a number of dimensions which may be interesting for the researchers such as developing algorithm for maximum matching and polynomial algorithm for constructing k-partite graph from general graph.
Is the crowd's wisdom biased? A quantitative asessment of three online communities
Venue: arXiv cs.HC 2009
Year: 2009

This paper presents a study of user voting on three websites: Imdb, Amazon and BookCrossings. It reports on an expert evaluation of the voting mechanisms of each website and a quantitative data analysis of users' aggregate voting behavior. The results suggest that voting follows different patterns across the websites, with higher barrier to vote introducing a more of one-off voters and attracting mostly experts. The results also show that that one-off voters tend to vote on popular items, while experts mostly vote for obscure, low-rated items. The study concludes with design suggestions to address the "wisdom of the crowd" bias.
Computational Complexities and Breaches in Authentication Frameworks of Broadband Wireless Access
Venue: arXiv cs.CR 2009
Year: 2009

Secure access of communication networks has become an increasingly important area of consideration for the communication service providers of present day. Broadband Wireless Access (BWA) networks are proving to be an efficient and cost effective solution for the provisioning of high rate wireless traffic links in static and mobile domains. The secure access of these networks is necessary to ensure their superior operation and revenue efficacy. Although authentication process is a key to secure access in BWA networks, the breaches present in them limit the networks performance. In this paper, the vulnerabilities in the authentication frameworks of BWA networks have been unveiled. Moreover, this paper also describes the limitations of these protocols and of the solutions proposed to them due to the involved computational complexities and overheads. The possible attacks on privacy and performance of BWA networks have been discussed and explained in detail.
Receding horizon decoding of convolutional codes
Venue: arXiv cs.IT 2009
Year: 2009

Decoding of convolutional codes poses a significant challenge for coding theory. Classical methods, based on e.g. Viterbi decoding, suffer from being computationally expensive and are restricted therefore to codes of small complexity. Based on analogies with model predictive optimal control, we propose a new iterative method for convolutional decoding that is cheaper to implement than established algorithms, while still offering significant error correction capabilities. The algorithm is particularly well-suited for decoding special types of convolutional codes, such as e.g. cyclic convolutional codes.
Statistical End-to-end Performance Bounds for Networks under Long Memory FBM Cross Traffic
Venue: arXiv cs.NI 2009
Year: 2009

Fractional Brownian motion (fBm) emerged as a useful model for self-similar and long-range dependent Internet traffic. Approximate performance measures are known from large deviations theory for single queuing systems with fBm through traffic. In this paper we derive end-to-end performance bounds for a through flow in a network of tandem queues under fBm cross traffic. To this end, we prove a rigorous sample path envelope for fBm that complements previous approximate results. We find that both approaches agree in their outcome that overflow probabilities for fBm traffic have a Weibullian tail. We employ the sample path envelope and the concept of leftover service curves to model the remaining service after scheduling fBm cross traffic at a system. Using composition results for tandem systems from the stochastic network calculus we derive end-to-end statistical performance bounds for individual flows in networks under fBm cross traffic. We discover that these bounds grow in O(n (log n)^(1/(2-2H))) for n systems in series where H is the Hurst parameter of the fBm cross traffic. We show numerical results on the impact of the variability and the correlation of fBm traffic on network performance.
The Euler Path to Static Level-Ancestors
Venue: arXiv cs.DS 2009
Year: 2009

Suppose that a rooted tree T is given for preprocessing. The Level-Ancestor Problem is to answer quickly queries of the following form. Given a vertex v and an integer i > 0, find the i-th vertex on the path from the root to v. Algorithms that achieve a linear time bound for preprocessing and a constant time bound for a query have been published by Dietz (1991), Alstrup and Holm (2000), and Bender and Farach (2002). The first two algorithms address dynamic versions of the problem; the last addresses the static version only and is the simplest so far. The purpose of this note is to expose another simple algorithm, derived from a complicated PRAM algorithm by Berkman and Vishkin (1990,1994). We further show some easy extensions of its functionality, adding queries for descendants and level successors as well as ancestors, extensions for which the formerly known algorithms are less suitable.
Statechart Verification with iState
Venue: arXiv cs.SE 2009
Year: 2009

This paper is the longer version of the extended abstract with the same name published in FM 06. We describe in detail the algorithm to generate verification conditions from statechart structures implemented in the iState tool. This approach also suggests us a novel method to define a version of predicate semantics for statecharts analogous to how we assign predicate semantics to programming languages.
High level architecture evolved modular federation object model
Venue: arXiv cs.SE 2009
Year: 2009

To improve the agility, dynamics, composability, reusability, and development efficiency restricted by monolithic Federation Object Model (FOM), a modular FOM was proposed by High Level Architecture (HLA) Evolved product development group. This paper reviews the state-of-the-art of HLA Evolved modular FOM. In particular, related concepts, the overall impact on HLA standards, extension principles, and merging processes are discussed. Also permitted and restricted combinations, and merging rules are provided, and the influence on HLA interface specification is given. The comparison between modular FOM and Base Object Model (BOM) is performed to illustrate the importance of their combination. The applications of modular FOM are summarized. Finally, the significance to facilitate composable simulation both in academia and practice is presented and future directions are pointed out.
Kernel Spectral Curvature Clustering (KSCC)
Venue: arXiv cs.CV 2009
Year: 2009

Multi-manifold modeling is increasingly used in segmentation and data representation tasks in computer vision and related fields. While the general problem, modeling data by mixtures of manifolds, is very challenging, several approaches exist for modeling data by mixtures of affine subspaces (which is often referred to as hybrid linear modeling). We translate some important instances of multi-manifold modeling to hybrid linear modeling in embedded spaces, without explicitly performing the embedding but applying the kernel trick. The resulting algorithm, Kernel Spectral Curvature Clustering, uses kernels at two levels - both as an implicit embedding method to linearize nonflat manifolds and as a principled method to convert a multiway affinity problem into a spectral clustering one. We demonstrate the effectiveness of the method by comparing it with other state-of-the-art methods on both synthetic data and a real-world problem of segmenting multiple motions from two perspective camera views.
Motion Segmentation by SCC on the Hopkins 155 Database
Venue: arXiv cs.CV 2009
Year: 2009

We apply the Spectral Curvature Clustering (SCC) algorithm to a benchmark database of 155 motion sequences, and show that it outperforms all other state-of-the-art methods. The average misclassification rate by SCC is 1.41% for sequences having two motions and 4.85% for three motions.
Certificate-based Single Sign-On Mechanism for Multi-Platform Distributed Systems
Venue: arXiv cs.CR 2009
Year: 2009

We propose a certificate-based single sign-on mechanism in distributed systems. The proposed security protocols and authentication mechanisms are integrated in a middleware. The novelty of our middleware lies on the use of XPCOM components, this way we provide a different services that can be used on every platform where Mozilla is available. The componen based architecture of the implemented services allows using the authentication components separately.
Interactive Data Integration through Smart Copy & Paste
Venue: arXiv cs.DB 2009
Year: 2009

In many scenarios, such as emergency response or ad hoc collaboration, it is critical to reduce the overhead in integrating data. Ideally, one could perform the entire process interactively under one unified interface: defining extractors and wrappers for sources, creating a mediated schema, and adding schema mappings ? while seeing how these impact the integrated view of the data, and refining the design accordingly. We propose a novel smart copy and paste (SCP) model and architecture for seamlessly combining the design-time and run-time aspects of data integration, and we describe an initial prototype, the CopyCat system. In CopyCat, the user does not need special tools for the different stages of integration: instead, the system watches as the user copies data from applications (including the Web browser) and pastes them into CopyCat?s spreadsheet-like workspace. CopyCat generalizes these actions and presents proposed auto-completions, each with an explanation in the form of provenance. The user provides feedback on these suggestions ? through either direct interactions or further copy-and-paste operations ? and the system learns from this feedback. This paper provides an overview of our prototype system, and identifies key research challenges in achieving SCP in its full generality.
From Declarative Languages to Declarative Processing in Computer Games
Venue: arXiv cs.DB 2009
Year: 2009

Recent work has shown that we can dramatically improve the performance of computer games and simulations through declarative processing: Character AI can be written in an imperative scripting language which is then compiled to relational algebra and executed by a special games engine with features similar to a main memory database system. In this paper we lay out a challenging research agenda built on these ideas. We discuss several research ideas for novel language features to support atomic actions and reactive programming. We also explore challenges for main-memory query processing in games and simulations including adaptive query plan selection, support for parallel architectures, debugging simulation scripts, and extensions for multi-player games and virtual worlds. We believe that these research challenges will result in a dramatic change in the design of game engines over the next decade.
The Role of Schema Matching in Large Enterprises
Venue: arXiv cs.DB 2009
Year: 2009

To date, the principal use case for schema matching research has been as a precursor for code generation, i.e., constructing mappings between schema elements with the end goal of data transfer. In this paper, we argue that schema matching plays valuable roles independent of mapping construction, especially as schemata grow to industrial scales. Specifically, in large enterprises human decision makers and planners are often the immediate consumer of information derived from schema matchers, instead of schema mapping tools. We list a set of real application areas illustrating this role for schema matching, and then present our experiences tackling a customer problem in one of these areas. We describe the matcher used, where the tool was effective, where it fell short, and our lessons learned about how well current schema matching technology is suited for use in large enterprises. Finally, we suggest a new agenda for schema matching research based on these experiences.
SCADS: Scale-Independent Storage for Social Computing Applications
Venue: arXiv cs.DB 2009
Year: 2009

Collaborative web applications such as Facebook, Flickr and Yelp present new challenges for storing and querying large amounts of data. As users and developers are focused more on performance than single copy consistency or the ability to perform ad-hoc queries, there exists an opportunity for a highly-scalable system tailored specifically for relaxed consistency and pre-computed queries. The Web 2.0 development model demands the ability to both rapidly deploy new features and automatically scale with the number of users. There have been many successful distributed key-value stores, but so far none provide as rich a query language as SQL. We propose a new architecture, SCADS, that allows the developer to declaratively state application specific consistency requirements, takes advantage of utility computing to provide cost effective scale-up and scale-down, and will use machine learning models to introspectively anticipate performance problems and predict the resource requirements of new queries before execution.