OpenRaiser/Intern-Atlas huggingface dataset:
Faster estimation of the correlation fractal dimension using box-counting
Venue: arXiv cs.DB 2009
Year: 2009

Fractal dimension is widely adopted in spatial databases and data mining, among others as a measure of dataset skewness. State-of-the-art algorithms for estimating the fractal dimension exhibit linear runtime complexity whether based on box-counting or approximation schemes. In this paper, we revisit a correlation fractal dimension estimation algorithm that redundantly rescans the dataset and, extending that work, we propose another linear, yet faster and as accurate method, which completes in a single pass.
Cyclic Codes over Some Finite Rings
Venue: arXiv cs.IT 2009
Year: 2009

In this paper cyclic codes are established with respect to the Mannheim metric over some finite rings by using Gaussian integers and the decoding algorithm for these codes is given.
Variable binding, symmetric monoidal closed theories, and bigraphs
Venue: arXiv cs.LO 2009
Year: 2009

This paper investigates the use of symmetric monoidal closed (SMC) structure for representing syntax with variable binding, in particular for languages with linear aspects. In our setting, one first specifies an SMC theory T, which may express binding operations, in a way reminiscent from higher-order abstract syntax. This theory generates an SMC category S(T) whose morphisms are, in a sense, terms in the desired syntax. We apply our approach to Jensen and Milner's (abstract binding) bigraphs, which are linear w.r.t. processes. This leads to an alternative category of bigraphs, which we compare to the original.
The Usefulness of Multilevel Hash Tables with Multiple Hash Functions in Large Databases
Venue: arXiv cs.DS 2009
Year: 2009

In this work, attempt is made to select three good hash functions which uniformly distribute hash values that permute their internal states and allow the input bits to generate different output bits. These functions are used in different levels of hash tables that are coded in Java Programming Language and a quite number of data records serve as primary data for testing the performances. The result shows that the two-level hash tables with three different hash functions give a superior performance over one-level hash table with two hash functions or zero-level hash table with one function in term of reducing the conflict keys and quick lookup for a particular element. The result assists to reduce the complexity of join operation in query language from O(n2) to O(1) by placing larger query result, if any, in multilevel hash tables with multiple hash functions and generate shorter query result.
Development and Optimization of a Multimedia Product
Venue: arXiv cs.MM 2009
Year: 2009

This article presents a new concept of a multimedia interactive product. It is a multiuser versatile platform that can be used for different purposes. The first implementation of the platform is a multiplayer game called Texas Hold 'em, which is a very popular community card game. The paper shows the product's multimedia structure where Hardware and Software work together in creating a realistic feeling for the users.
Execution Time of lambda-Terms via Denotational Semantics and Intersection Types
Venue: arXiv cs.LO 2009
Year: 2009

The multiset based relational model of linear logic induces a semantics of the type free lambda-calculus, which corresponds to a non-idempotent intersection type system, System R. We prove that, in System R, the size of the type derivations and the size of the types are closely related to the execution time of lambda-terms in a particular environment machine, Krivine's machine.
Information Modeling for a Dynamic Representation of an Emergency Situation
Venue: arXiv cs.AI 2009
Year: 2009

In this paper we propose an approach to build a decision support system that can help emergency planners and responders to detect and manage emergency situations. The internal mechanism of the system is independent from the treated application. Therefore, we think the system may be used or adapted easily to different case studies. We focus here on a first step in the decision-support process which concerns the modeling of information issued from the perceived environment and their representation dynamically using a multiagent system. This modeling was applied on the RoboCupRescue Simulation System. An implementation and some results are presented here.
Bounding the Sum of Square Roots via Lattice Reduction
Venue: arXiv cs.CG 2009
Year: 2009

Let $k$ and $n$ be positive integers. Define $R(n,k)$ to be the minimum positive value of $$ | e_i \sqrt{s_1} + e_2 \sqrt{s_2} + ... + e_k \sqrt{s_k} -t | $$ where $ s_1, s_2, ..., s_k$ are positive integers no larger than $n$, $t$ is an integer and $e_i\in \{1,0, -1\}$ for all $1\leq i\leq k$. It is important in computational geometry to determine a good lower and upper bound of $ R(n,k)$. In this paper we show that this problem is closely related to the shortest vector problem in certain integral lattices and present an algorithm to find lower bounds based on lattice reduction algorithms. Although we can only prove an exponential time upper bound for the algorithm, it is efficient for large $k$ when an exhaustive search for the minimum value is clearly infeasible. It produces lower bounds much better than the root separation technique does. Based on numerical data, we formulate a conjecture on the length of the shortest nonzero vector in the lattice, whose validation implies that our algorithm runs in polynomial time and the problem of comparing two sums of square roots of small integers can be solved in polynomial time. As a side result, we obtain constructive upper bounds for $R(n,k)$ when $ n$ is much smaller than $2^{2k}$.
Confluence Results for a Quantum Lambda Calculus with Measurements
Venue: arXiv cs.LO 2009
Year: 2009

A strong confluence result for Q*, a quantum lambda-calculus with measurements, is proved. More precisely, confluence is shown to hold both for finite and infinite computations. The technique used in the confluence proof is syntactical but innovative. This makes Q* different from similar quantum lambda calculi, which are either measurement-free or provided with a reduction strategy.
About raising and handling exceptions
Venue: arXiv cs.PL 2009
Year: 2009

This paper presents a unified framework for dealing with a deduction system and a denotational semantics of exceptions. It is based on the fact that handling exceptions can be seen as a kind of generalized case distinction. This point of view on exceptions has been introduced in 2004, it is based on the notion of diagrammatic logic, which assumes some familiarity with category theory. Extensive sums of types can be used for dealing with case distinctions. The aim of this new paper is to focus on the role of generalized extensivity property for dealing with exceptions. Moreover, the presentation of this paper makes only a restricted use of category theory.
XML Technologies in Computer Assisted Learning and Testing Systems
Venue: arXiv cs.OH 2009
Year: 2009

The learning and assessment activities have undergone major changes due to the development of modern technologies. The computer-assisted learning and testing has proven a number of advantages in the development of modern educational system. The paper suggests a solution for the computer-assisted testing, which uses XML technologies, a solution that could make the basis for developing a learning computer-assisted system.
Optimizing XML Compression
Venue: arXiv cs.DB 2009
Year: 2009

The eXtensible Markup Language (XML) provides a powerful and flexible means of encoding and exchanging data. As it turns out, its main advantage as an encoding format (namely, its requirement that all open and close markup tags are present and properly balanced) yield also one of its main disadvantages: verbosity. XML-conscious compression techniques seek to overcome this drawback. Many of these techniques first separate XML structure from the document content, and then compress each independently. Further compression gains can be realized by identifying and compressing together document content that is highly similar, thereby amortizing the storage costs of auxiliary information required by the chosen compression algorithm. Additionally, the proper choice of compression algorithm is an important factor not only for the achievable compression gain, but also for access performance. Hence, choosing a compression configuration that optimizes compression gain requires one to determine (1) a partitioning strategy for document content, and (2) the best available compression algorithm to apply to each set within this partition. In this paper, we show that finding an optimal compression configuration with respect to compression gain is an NP-hard optimization problem. This problem remains intractable even if one considers a single compression algorithm for all content. We also describe an approximation algorithm for selecting a partitioning strategy for document content based on the branch-and-bound paradigm.
Representations of Stream Processors Using Nested Fixed Points
Venue: arXiv cs.DS 2009
Year: 2009

We define representations of continuous functions on infinite streams of discrete values, both in the case of discrete-valued functions, and in the case of stream-valued functions. We define also an operation on the representations of two continuous functions between streams that yields a representation of their composite. In the case of discrete-valued functions, the representatives are well-founded (finite-path) trees of a certain kind. The underlying idea can be traced back to Brouwer's justification of bar-induction, or to Kreisel and Troelstra's elimination of choice-sequences. In the case of stream-valued functions, the representatives are non-wellfounded trees pieced together in a coinductive fashion from well-founded trees. The definition requires an alternating fixpoint construction of some ubiquity.
On Node Density -- Outage Probability Tradeoff in Wireless Networks
Venue: arXiv cs.IT 2009
Year: 2009

A statistical model of interference in wireless networks is considered, which is based on the traditional propagation channel model and a Poisson model of random spatial distribution of nodes in 1-D, 2-D and 3-D spaces with both uniform and non-uniform densities. The power of nearest interferer is used as a major performance indicator, instead of a traditionally-used total interference power, since at the low outage region, they have the same statistics so that the former is an accurate approximation of the latter. This simplifies the problem significantly and allows one to develop a unified framework for the outage probability analysis, including the impacts of complete/partial interference cancelation, of different types of fading and of linear filtering, either alone or in combination with each other. When a given number of nearest interferers are completely canceled, the outage probability is shown to scale down exponentially in this number. Three different models of partial cancelation are considered and compared via their outage probabilities. The partial cancelation level required to eliminate the impact of an interferer is quantified. The effect of a broad class of fading processes (including all popular fading models) is included in the analysis in a straightforward way, which can be positive or negative depending on a particular model and propagation/system parameters. The positive effect of linear filtering (e.g. by directional antennas) is quantified via a new statistical selectivity parameter. The analysis results in formulation of a tradeoff relationship between the network density and the outage probability, which is a result of the interplay between random geometry of node locations, the propagation path loss and the distortion effects at the victim receiver.
Coded Modulation with Mismatched CSIT over Block-Fading Channels
Venue: arXiv cs.IT 2009
Year: 2009

Reliable communication over delay-constrained block-fading channels with discrete inputs and mismatched (imperfect) channel state information at the transmitter (CSIT) is studied. The CSIT mismatch is modeled as Gaussian random variables, whose variances decay as a power of the signal-to-noise ratio (SNR). A special focus is placed on the large-SNR decay of the outage probability when power control with long-term power constraints is used. Without explicitly characterizing the corresponding power allocation algorithms, we derive the outage exponent as a function of the system parameters, including the CSIT noise variance exponent and the exponent of the peak power constraint. It is shown that CSIT, even if noisy, is always beneficial and leads to important gains in terms of exponents. It is also shown that when multidimensional rotations or precoders are used at the transmitter, further exponent gains can be attained, but at the expense of larger decoding complexity.
Total Variation, Adaptive Total Variation and Nonconvex Smoothly Clipped Absolute Deviation Penalty for Denoising Blocky Images
Venue: arXiv cs.CV 2009
Year: 2009

The total variation-based image denoising model has been generalized and extended in numerous ways, improving its performance in different contexts. We propose a new penalty function motivated by the recent progress in the statistical literature on high-dimensional variable selection. Using a particular instantiation of the majorization-minimization algorithm, the optimization problem can be efficiently solved and the computational procedure realized is similar to the spatially adaptive total variation model. Our two-pixel image model shows theoretically that the new penalty function solves the bias problem inherent in the total variation model. The superior performance of the new penalty is demonstrated through several experiments. Our investigation is limited to "blocky" images which have small total variation.
Soft-Input Soft-Output Single Tree-Search Sphere Decoding
Venue: arXiv cs.IT 2009
Year: 2009

Soft-input soft-output (SISO) detection algorithms form the basis for iterative decoding. The computational complexity of SISO detection often poses significant challenges for practical receiver implementations, in particular in the context of multiple-input multiple-output (MIMO) wireless communication systems. In this paper, we present a low-complexity SISO sphere-decoding algorithm, based on the single tree-search paradigm proposed originally for soft-output MIMO detection in Studer, et al., IEEE J-SAC, 2008. The new algorithm incorporates clipping of the extrinsic log-likelihood ratios (LLRs) into the tree-search, which results in significant complexity savings and allows to cover a large performance/complexity tradeoff region by adjusting a single parameter. Furthermore, we propose a new method for correcting approximate LLRs --resulting from sub-optimal detectors-- which (often significantly) improves detection performance at low additional computational complexity.
PayPal in Romania
Venue: arXiv cs.OH 2009
Year: 2009

The present paper refers to the usefulness of online payment through PayPal and to the development of this payment manner in Romania. PayPal is an example of a payment intermediary service that facilitates worldwide e-commerce.
Efficiency of (Revenue-)Optimal Mechanisms
Venue: arXiv cs.GT 2009
Year: 2009

We compare the expected efficiency of revenue maximizing (or {\em optimal}) mechanisms with that of efficiency maximizing ones. We show that the efficiency of the revenue maximizing mechanism for selling a single item with k + log_{e/(e-1)} k + 1 bidders is at least as much as the efficiency of the efficiency maximizing mechanism with k bidders, when bidder valuations are drawn i.i.d. from a Monotone Hazard Rate distribution. Surprisingly, we also show that this bound is tight within a small additive constant of 5.7. In other words, Theta(log k) extra bidders suffice for the revenue maximizing mechanism to match the efficiency of the efficiency maximizing mechanism, while o(log k) do not. This is in contrast to the result of Bulow and Klemperer comparing the revenue of the two mechanisms, where only one extra bidder suffices. More precisely, they show that the revenue of the efficiency maximizing mechanism with k+1 bidders is no less than the revenue of the revenue maximizing mechanism with k bidders. We extend our result for the case of selling t identical items and show that 2.2 log k + t Theta(log log k) extra bidders suffice for the revenue maximizing mechanism to match the efficiency of the efficiency maximizing mechanism. In order to prove our results, we do a classification of Monotone Hazard Rate (MHR) distributions and identify a family of MHR distributions, such that for each class in our classification, there is a member of this family that is pointwise lower than every distribution in that class. This lets us prove interesting structural theorems about distributions with Monotone Hazard Rate.
Pipelined Algorithms to Detect Cheating in Long-Term Grid Computations
Venue: arXiv cs.CR 2009
Year: 2009

This paper studies pipelined algorithms for protecting distributed grid computations from cheating participants, who wish to be rewarded for tasks they receive but don't perform. We present improved cheater detection algorithms that utilize natural delays that exist in long-term grid computations. In particular, we partition the sequence of grid tasks into two interleaved sequences of task rounds, and we show how to use those rounds to devise the first general-purpose scheme that can catch all cheaters, even when cheaters collude. The main idea of this algorithm might at first seem counter-intuitive--we have the participants check each other's work. A naive implementation of this approach would, of course, be susceptible to collusion attacks, but we show that by, adapting efficient solutions to the parallel processor diagnosis problem, we can tolerate collusions of lazy cheaters, even if the number of such cheaters is a fraction of the total number of participants. We also include a simple economic analysis of cheaters in grid computations and a parameterization of the main deterrent that can be used against them--the probability of being caught.
Efficient Algorithms for Several Constrained Resource Allocation, Management and Discovery Problems
Venue: arXiv cs.DS 2009
Year: 2009

In this paper we present efficient algorithmic solutions for several constrained resource allocation, management and discovery problems. We consider new types of resource allocation models and constraints, and we present new geometric techniques which are useful when the resources are mapped to points into a multidimensional feature space. We also consider a resource discovery problem for which we present a guessing game theoretical model.
Knowledge Management in Economic Intelligence with Reasoning on Temporal Attributes
Venue: arXiv cs.AI 2009
Year: 2009

People have to make important decisions within a time frame. Hence, it is imperative to employ means or strategy to aid effective decision making. Consequently, Economic Intelligence (EI) has emerged as a field to aid strategic and timely decision making in an organization. In the course of attaining this goal: it is indispensable to be more optimistic towards provision for conservation of intellectual resource invested into the process of decision making. This intellectual resource is nothing else but the knowledge of the actors as well as that of the various processes for effecting decision making. Knowledge has been recognized as a strategic economic resource for enhancing productivity and a key for innovation in any organization or community. Thus, its adequate management with cognizance of its temporal properties is highly indispensable. Temporal properties of knowledge refer to the date and time (known as timestamp) such knowledge is created as well as the duration or interval between related knowledge. This paper focuses on the needs for a user-centered knowledge management approach as well as exploitation of associated temporal properties. Our perspective of knowledge is with respect to decision-problems projects in EI. Our hypothesis is that the possibility of reasoning about temporal properties in exploitation of knowledge in EI projects should foster timely decision making through generation of useful inferences from available and reusable knowledge for a new project.
Outage Behavior of Discrete Memoryless Channels (DMCs) Under Channel Estimation Errors
Venue: arXiv cs.IT 2009
Year: 2009

Communication systems are usually designed by assuming perfect channel state information (CSI). However, in many practical scenarios, only a noisy estimate of the channel is available, which may strongly differ from the true channel. This imperfect CSI scenario is addressed by introducing the notion of estimation-induced outage (EIO) capacity. We derive a single-letter characterization of the maximal EIO rate and prove an associated coding theorem and its strong converse for discrete memoryless channels (DMCs). The transmitter and the receiver rely on the channel estimate and the statistics of the estimate to construct codes that guarantee reliable communication with a certain outage probability. This ensures that in the non-outage case the transmission meets the target rate with small error probability, irrespective of the quality of the channel estimate. Applications of the EIO capacity to a single-antenna (non-ergodic) Ricean fading channel are considered. The EIO capacity for this case is compared to the EIO rates of a communication system in which the receiver decodes by using a mismatched ML decoder. The effects of rate-limited feedback to provide the transmitter with quantized CSI are also investigated.
Methodology for assessing system performance loss within a proactive maintenance framework
Venue: arXiv cs.PF 2009
Year: 2009

Maintenance plays now a critical role in manufacturing for achieving important cost savings and competitive advantage while preserving product conditions. It suggests moving from conventional maintenance practices to predictive strategy. Indeed the maintenance action has to be done at the right time based on the system performance and component Remaining Useful Life (RUL) assessed by a prognostic process. In that way, this paper proposes a methodology in order to evaluate the performance loss of the system according to the degradation of component and the deviations of system input flows. This methodology is supported by the neuro-fuzzy tool ANFIS (Adaptive Neuro-Fuzzy Inference Systems) that allows to integrate knowledge from two different sources: expertise and real data. The feasibility and added value of such methodology is then highlighted through an application case extracted from the TELMA platform used for education and research.
How deals with discrete data for the reduction of simulation models using neural network
Venue: arXiv cs.NE 2009
Year: 2009

Simulation is useful for the evaluation of a Master Production/distribution Schedule (MPS). Also, the goal of this paper is the study of the design of a simulation model by reducing its complexity. According to theory of constraints, we want to build reduced models composed exclusively by bottlenecks and a neural network. Particularly a multilayer perceptron, is used. The structure of the network is determined by using a pruning procedure. This work focuses on the impact of discrete data on the results and compares different approaches to deal with these data. This approach is applied to sawmill internal supply chain
Evading network-level emulation
Venue: arXiv cs.CR 2009
Year: 2009

Recently more and more attention has been paid to the intrusion detection systems (IDS) which don't rely on signature based detection approach. Such solutions try to increase their defense level by using heuristics detection methods like network-level emulation. This technique allows the intrusion detection systems to stop unknown threats, which normally couldn't be stopped by standard signature detection techniques. In this article author will describe general concepts of network-level emulation technique including its advantages and disadvantages (weak sides) together with providing potential countermeasures against this type of detection method.