OpenRaiser/Intern-Atlas huggingface dataset:
Transceiver Design with Low-Precision Analog-to-Digital Conversion : An Information-Theoretic Perspective
Venue: arXiv cs.IT 2008
Year: 2008

Modern communication receiver architectures center around digital signal processing (DSP), with the bulk of the receiver processing being performed on digital signals obtained after analog-to-digital conversion (ADC). In this paper, we explore Shannon-theoretic performance limits when ADC precision is drastically reduced, from typical values of 8-12 bits used in current communication transceivers, to 1-3 bits. The goal is to obtain insight on whether DSP-centric transceiver architectures are feasible as communication bandwidths scale up, recognizing that high-precision ADC at high sampling rates is either unavailable, or too costly or power-hungry. Specifically, we evaluate the communication limits imposed by low-precision ADC for the ideal real discrete-time Additive White Gaussian Noise (AWGN) channel, under an average power constraint on the input. For an ADC with K quantization bins (i.e., a precision of log2 K bits), we show that the Shannon capacity is achievable by a discrete input distribution with at most K + 1 mass points. For 2-bin (1-bit) symmetric ADC, this result is tightened to show that binary antipodal signaling is optimum for any signal-to-noise ratio (SNR). For multi-bit ADC, the capacity is computed numerically, and the results obtained are used to make the following encouraging observations regarding system design with low-precision ADC : (a) even at moderately high SNR of up to 20 dB, 2-3 bit quantization results in only 10-20% reduction of spectral efficiency, which is acceptable for large communication bandwidths, (b) standard equiprobable pulse amplitude modulation with ADC thresholds set to implement maximum likelihood hard decisions is asymptotically optimum at high SNR, and works well at low to moderate SNRs as well.
Securing U-Healthcare Sensor Networks using Public Key Based Scheme
Venue: arXiv cs.CR 2008
Year: 2008

Recent emergence of electronic culture uplifts healthcare facilities to a new era with the aid of wireless sensor network (WSN) technology. Due to the sensitiveness of medical data, austere privacy and security are inevitable for all parts of healthcare systems. However, the constantly evolving nature and constrained resources of sensors in WSN inflict unavailability of a lucid line of defense to ensure perfect security. In order to provide holistic security, protections must be incorporated in every component of healthcare sensor networks. This paper proposes an efficient security scheme for healthcare applications of WSN which uses the notion of public key cryptosystem. Our entire security scheme comprises basically of two parts; a key handshaking scheme based on simple linear operations and the derivation of decryption key by a receiver node for a particular sender in the network. Our architecture allows both base station to node or node to base station secure communications, and node-to-node secure communications. We consider both the issues of stringent security and network performance to propose our security scheme.
New Lower Bounds for the Maximum Number of Runs in a String
Venue: arXiv cs.DM 2008
Year: 2008

We show a new lower bound for the maximum number of runs in a string. We prove that for any e > 0, (a -- e)n is an asymptotic lower bound, where a = 56733/60064 = 0.944542. It is superior to the previous bound 0.927 given by Franek et al. Moreover, our construction of the strings and the proof is much simpler than theirs.
The quest for rings on bipolar scales
Venue: arXiv cs.DM 2008
Year: 2008

We consider the interval $]{-1},1[$ and intend to endow it with an algebraic structure like a ring. The motivation lies in decision making, where scales that are symmetric w.r.t. 0 are needed in order to represent a kind of symmetry in the behaviour of the decision maker. A former proposal due to Grabisch was based on maximum and minimum. In this paper, we propose to build our structure on t-conorms and t-norms, and we relate this construction to uninorms. We show that the only way to build a group is to use strict t-norms, and that there is no way to build a ring. Lastly, we show that the main result of this paper is connected to the theory of ordered Abelian groups.
Data Reduction in Intrusion Alert Correlation
Venue: arXiv cs.CR 2008
Year: 2008

Network intrusion detection sensors are usually built around low level models of network traffic. This means that their output is of a similarly low level and as a consequence, is difficult to analyze. Intrusion alert correlation is the task of automating some of this analysis by grouping related alerts together. Attack graphs provide an intuitive model for such analysis. Unfortunately alert flooding attacks can still cause a loss of service on sensors, and when performing attack graph correlation, there can be a large number of extraneous alerts included in the output graph. This obscures the fine structure of genuine attacks and makes them more difficult for human operators to discern. This paper explores modified correlation algorithms which attempt to minimize the impact of this attack.
Discovering More Accurate Frequent Web Usage Patterns
Venue: arXiv cs.DB 2008
Year: 2008

Web usage mining is a type of web mining, which exploits data mining techniques to discover valuable information from navigation behavior of World Wide Web users. As in classical data mining, data preparation and pattern discovery are the main issues in web usage mining. The first phase of web usage mining is the data processing phase, which includes the session reconstruction operation from server logs. Session reconstruction success directly affects the quality of the frequent patterns discovered in the next phase. In reactive web usage mining techniques, the source data is web server logs and the topology of the web pages served by the web server domain. Other kinds of information collected during the interactive browsing of web site by user, such as cookies or web logs containing similar information, are not used. The next phase of web usage mining is discovering frequent user navigation patterns. In this phase, pattern discovery methods are applied on the reconstructed sessions obtained in the first phase in order to discover frequent user patterns. In this paper, we propose a frequent web usage pattern discovery method that can be applied after session reconstruction phase. In order to compare accuracy performance of session reconstruction phase and pattern discovery phase, we have used an agent simulator, which models behavior of web users and generates web user navigation as well as the log data kept by the web server.
Noncoherent Capacity of Underspread Fading Channels
Venue: arXiv cs.IT 2008
Year: 2008

We derive bounds on the noncoherent capacity of wide-sense stationary uncorrelated scattering (WSSUS) channels that are selective both in time and frequency, and are underspread, i.e., the product of the channel's delay spread and Doppler spread is small. For input signals that are peak constrained in time and frequency, we obtain upper and lower bounds on capacity that are explicit in the channel's scattering function, are accurate for a large range of bandwidth and allow to coarsely identify the capacity-optimal bandwidth as a function of the peak power and the channel's scattering function. We also obtain a closed-form expression for the first-order Taylor series expansion of capacity in the limit of large bandwidth, and show that our bounds are tight in the wideband regime. For input signals that are peak constrained in time only (and, hence, allowed to be peaky in frequency), we provide upper and lower bounds on the infinite-bandwidth capacity and find cases when the bounds coincide and the infinite-bandwidth capacity is characterized exactly. Our lower bound is closely related to a result by Viterbi (1967). The analysis in this paper is based on a discrete-time discrete-frequency approximation of WSSUS time- and frequency-selective channels. This discretization explicitly takes into account the underspread property, which is satisfied by virtually all wireless communication channels.
An Optimal Bloom Filter Replacement Based on Matrix Solving
Venue: arXiv cs.DS 2008
Year: 2008

We suggest a method for holding a dictionary data structure, which maps keys to values, in the spirit of Bloom Filters. The space requirements of the dictionary we suggest are much smaller than those of a hashtable. We allow storing n keys, each mapped to value which is a string of k bits. Our suggested method requires nk + o(n) bits space to store the dictionary, and O(n) time to produce the data structure, and allows answering a membership query in O(1) memory probes. The dictionary size does not depend on the size of the keys. However, reducing the space requirements of the data structure comes at a certain cost. Our dictionary has a small probability of a one sided error. When attempting to obtain the value for a key that is stored in the dictionary we always get the correct answer. However, when testing for membership of an element that is not stored in the dictionary, we may get an incorrect answer, and when requesting the value of such an element we may get a certain random value. Our method is based on solving equations in GF(2^k) and using several hash functions. Another significant advantage of our suggested method is that we do not require using sophisticated hash functions. We only require pairwise independent hash functions. We also suggest a data structure that requires only nk bits space, has O(n2) preprocessing time, and has a O(log n) query time. However, this data structures requires a uniform hash functions. In order replace a Bloom Filter of n elements with an error proability of 2^{-k}, we require nk + o(n) memory bits, O(1) query time, O(n) preprocessing time, and only pairwise independent hash function. Even the most advanced previously known Bloom Filter would require nk+O(n) space, and a uniform hash functions, so our method is significantly less space consuming especially when k is small.
On the Extension of Pseudo-Boolean Functions for the Aggregation of Interacting Criteria
Venue: arXiv cs.DM 2008
Year: 2008

The paper presents an analysis on the use of integrals defined for non-additive measures (or capacities) as the Choquet and the \Sipos{} integral, and the multilinear model, all seen as extensions of pseudo-Boolean functions, and used as a means to model interaction between criteria in a multicriteria decision making problem. The emphasis is put on the use, besides classical comparative information, of information about difference of attractiveness between acts, and on the existence, for each point of view, of a ``neutral level'', allowing to introduce the absolute notion of attractive or repulsive act. It is shown that in this case, the Sipos integral is a suitable solution, although not unique. Properties of the Sipos integral as a new way of aggregating criteria are shown, with emphasis on the interaction among criteria.
Characterizing User Mobility in Second Life
Venue: arXiv cs.CY 2008
Year: 2008

In this work we present a measurement study of user mobility in Second Life. We first discuss different techniques to collect user traces and then focus on results obtained using a crawler that we built. Tempted by the question whether our methodology could provide similar results to those obtained in real-world experiments, we study the statistical distribution of user contacts and show that from a qualitative point of view user mobility in Second Life presents similar traits to those of real humans. We further push our analysis to line of sight networks that emerge from user interaction and show that they are highly clustered. Lastly, we focus on the spatial properties of user movements and observe that users in Second Life revolve around several point of interests traveling in general short distances. Besides our findings, the traces collected in this work can be very useful for trace-driven simulations of communication schemes in delay tolerant networks and their performance evaluation.
The non-anticipation of the asynchronous systems
Venue: arXiv cs.GL 2008
Year: 2008

The asynchronous systems are the models of the asynchronous circuits from the digital electrical engineering and non-anticipation is one of the most important properties in systems theory. Our present purpose is to introduce several concepts of non-anticipation of the asynchronous systems.
Some properties of the regular asynchronous systems
Venue: arXiv cs.OH 2008
Year: 2008

The asynchronous systems are the models of the asynchronous circuits from the digital electrical engineering. An asynchronous system f is a multi-valued function that assigns to each admissible input u a set f(u) of possible states x in f(u). A special case of asynchronous system consists in the existence of a Boolean function Υsuch that for any u and any x in f(u), a certain equation involving Υis fulfilled. Then Υis called the generator function of f (Moisil used the terminology of network function) and we say that f is generated by Υ. The systems that have a generator function are called regular. Our purpose is to continue the study of the generation of the asynchronous systems that was started in [2], [3].
Comparing and Combining Methods for Automatic Query Expansion
Venue: arXiv cs.IR 2008
Year: 2008

Query expansion is a well known method to improve the performance of information retrieval systems. In this work we have tested different approaches to extract the candidate query terms from the top ranked documents returned by the first-pass retrieval. One of them is the cooccurrence approach, based on measures of cooccurrence of the candidate and the query terms in the retrieved documents. The other one, the probabilistic approach, is based on the probability distribution of terms in the collection and in the top ranked set. We compare the retrieval improvement achieved by expanding the query with terms obtained with different methods belonging to both approaches. Besides, we have developed a naïve combination of both kinds of method, with which we have obtained results that improve those obtained with any of them separately. This result confirms that the information provided by each approach is of a different nature and, therefore, can be used in a combined manner.
The Secrecy Graph and Some of its Properties
Venue: arXiv cs.IT 2008
Year: 2008

A new random geometric graph model, the so-called secrecy graph, is introduced and studied. The graph represents a wireless network and includes only edges over which secure communication in the presence of eavesdroppers is possible. The underlying point process models considered are lattices and Poisson point processes. In the lattice case, analogies to standard bond and site percolation can be exploited to determine percolation thresholds. In the Poisson case, the node degrees are determined and percolation is studied using analytical bounds and simulations. It turns out that a small density of eavesdroppers already has a drastic impact on the connectivity of the secrecy graph.
Power Series Composition and Change of Basis
Venue: arXiv cs.SC 2008
Year: 2008

Efficient algorithms are known for many operations on truncated power series (multiplication, powering, exponential, ...). Composition is a more complex task. We isolate a large class of power series for which composition can be performed efficiently. We deduce fast algorithms for converting polynomials between various bases, including Euler, Bernoulli, Fibonacci, and the orthogonal Laguerre, Hermite, Jacobi, Krawtchouk, Meixner and Meixner-Pollaczek.
Theory and Applications of Two-dimensional, Null-boundary, Nine-Neighborhood, Cellular Automata Linear rules
Venue: arXiv cs.DM 2008
Year: 2008

This paper deals with the theory and application of 2-Dimensional, nine-neighborhood, null- boundary, uniform as well as hybrid Cellular Automata (2D CA) linear rules in image processing. These rules are classified into nine groups depending upon the number of neighboring cells influences the cell under consideration. All the Uniform rules have been found to be rendering multiple copies of a given image depending on the groups to which they belong where as Hybrid rules are also shown to be characterizing the phenomena of zooming in, zooming out, thickening and thinning of a given image. Further, using hybrid CA rules a new searching algorithm is developed called Sweepers algorithm which is found to be applicable to simulate many inter disciplinary research areas like migration of organisms towards a single point destination, Single Attractor and Multiple Attractor Cellular Automata Theory, Pattern Classification and Clustering Problem, Image compression, Encryption and Decryption problems, Density Classification problem etc.
Secure Remote Voting Using Paper Ballots
Venue: arXiv cs.CR 2008
Year: 2008

Internet voting will probably be one of the most significant achievements of the future information society. It will have an enormous impact on the election process making it fast, reliable and inexpensive. Nonetheless, so far remote voting is considered to be very difficult, as one has to take into account susceptibility of the voter's PC to various cyber-attacks. As a result, most the research effort is put into developing protocols and machines for poll-site electronic voting. Although these solutions yield promising results, they cannot be directly adopted to Internet voting because of secure platform problem. However, the cryptographic components they utilize may be very useful. This paper presents a scheme based on combination of mixnets and homomorphic encryption borrowed from robust poll-site voting, along with techniques recommended for remote voting -- code sheets and test ballots. The protocol tries to minimize the trust put in voter's PC by making the voter responsible for manual encryption of his vote. To achieve this, the voter obtains a paper ballot that allows him to scramble the vote by performing simple operations (lookup in a table). Creation of paper ballots, as well as decryption of votes, is performed by a group of cooperating trusted servers. As a result, the scheme is characterized by strong asymmetry -- all computations are carried out on the server side. In consequence it does not require any additional hardware on the voter's side, and offers distributed trust, receipt-freeness and verifiability.
Information filtering based on wiki index database
Venue: arXiv cs.IR 2008
Year: 2008

In this paper we present a profile-based approach to information filtering by an analysis of the content of text documents. The Wikipedia index database is created and used to automatically generate the user profile from the user document collection. The problem-oriented Wikipedia subcorpora are created (using knowledge extracted from the user profile) for each topic of user interests. The index databases of these subcorpora are applied to filtering information flow (e.g., mails, news). Thus, the analyzed texts are classified into several topics explicitly presented in the user profile. The paper concentrates on the indexing part of the approach. The architecture of an application implementing the Wikipedia indexing is described. The indexing method is evaluated using the Russian and Simple English Wikipedia.
Universal Quantum Circuits
Venue: arXiv cs.CC 2008
Year: 2008

We define and construct efficient depth-universal and almost-size-universal quantum circuits. Such circuits can be viewed as general-purpose simulators for central classes of quantum circuits and can be used to capture the computational power of the circuit class being simulated. For depth we construct universal circuits whose depth is the same order as the circuits being simulated. For size, there is a log factor blow-up in the universal circuits constructed here. We prove that this construction is nearly optimal.
Short proofs of strong normalization
Venue: arXiv cs.LO 2008
Year: 2008

This paper presents simple, syntactic strong normalization proofs for the simply-typed lambda-calculus and the polymorphic lambda-calculus (system F) with the full set of logical connectives, and all the permutative reductions. The normalization proofs use translations of terms and types to systems, for which strong normalization property is known.
Robust Precoder for Multiuser MISO Downlink with SINR Constraints
Venue: arXiv cs.IT 2008
Year: 2008

In this paper, we consider linear precoding with SINR constraints for the downlink of a multiuser MISO (multiple-input single-output) communication system in the presence of imperfect channel state information (CSI). The base station is equipped with multiple transmit antennas and each user terminal is equipped with a single receive antenna. We propose a robust design of linear precoder which transmits minimum power to provide the required SINR at the user terminals when the true channel state lies in a region of a given size around the channel state available at the transmitter. We show that this design problem can be formulated as a Second Order Cone Program (SOCP) which can be solved efficiently. We compare the performance of the proposed design with some of the robust designs reported in the literature. Simulation results show that the proposed robust design provides better performance with reduced complexity.
Bipolarization of posets and natural interpolation
Venue: arXiv cs.DM 2008
Year: 2008

The Choquet integral w.r.t. a capacity can be seen in the finite case as a parsimonious linear interpolator between vertices of $[0,1]^n$. We take this basic fact as a starting point to define the Choquet integral in a very general way, using the geometric realization of lattices and their natural triangulation, as in the work of Koshevoy. A second aim of the paper is to define a general mechanism for the bipolarization of ordered structures. Bisets (or signed sets), as well as bisubmodular functions, bicapacities, bicooperative games, as well as the Choquet integral defined for them can be seen as particular instances of this scheme. Lastly, an application to multicriteria aggregation with multiple reference levels illustrates all the results presented in the paper.
An Analysis of Key Factors for the Success of the Communal Management of Knowledge
Venue: arXiv cs.HC 2008
Year: 2008

This paper explores the links between Knowledge Management and new community-based models of the organization from both a theoretical and an empirical perspective. From a theoretical standpoint, we look at Communities of Practice (CoPs) and Knowledge Management (KM) and explore the links between the two as they relate to the use of information systems to manage knowledge. We begin by reviewing technologically supported approaches to KM and introduce the idea of "Systemes d'Aide a la Gestion des Connaissances" SAGC (Systems to aid the Management of Knowledge). Following this we examine the contribution that communal structures such as CoPs can make to intraorganizational KM and highlight some of 'success factors' for this approach to KM that are found in the literature. From an empirical standpoint, we present the results of a survey involving the Chief Knowledge Officers (CKOs) of twelve large French businesses; the objective of this study was to identify the factors that might influence the success of such approaches. The survey was analysed using thematic content analysis and the results are presented here with some short illustrative quotes from the CKOs. Finally, the paper concludes with some brief reflections on what can be learnt from looking at this problem from these two perspectives.