OpenRaiser/Intern-Atlas huggingface dataset:
Optimal Linear Precoding Strategies for Wideband Non-Cooperative Systems based on Game Theory-Part II: Algorithms
Venue: arXiv cs.IT 2007
Year: 2007

In this two-part paper, we address the problem of finding the optimal precoding/multiplexing scheme for a set of non-cooperative links sharing the same physical resources, e.g., time and bandwidth. We consider two alternative optimization problems: P.1) the maximization of mutual information on each link, given constraints on the transmit power and spectral mask; and P.2) the maximization of the transmission rate on each link, using finite order constellations, under the same constraints as in P.1, plus a constraint on the maximum average error probability on each link. Aiming at finding decentralized strategies, we adopted as optimality criterion the achievement of a Nash equilibrium and thus we formulated both problems P.1 and P.2 as strategic noncooperative (matrix-valued) games. In Part I of this two-part paper, after deriving the optimal structure of the linear transceivers for both games, we provided a unified set of sufficient conditions that guarantee the uniqueness of the Nash equilibrium. In this Part II, we focus on the achievement of the equilibrium and propose alternative distributed iterative algorithms that solve both games. Specifically, the new proposed algorithms are the following: 1) the sequential and simultaneous iterative waterfilling based algorithms, incorporating spectral mask constraints; 2) the sequential and simultaneous gradient projection based algorithms, establishing an interesting link with variational inequality problems. Our main contribution is to provide sufficient conditions for the global convergence of all the proposed algorithms which, although derived under stronger constraints, incorporating for example spectral mask constraints, have a broader validity than the convergence conditions known in the current literature for the sequential iterative waterfilling algorithm.
Segmentation and Context of Literary and Musical Sequences
Venue: arXiv cs.CL 2007
Year: 2007

We test a segmentation algorithm, based on the calculation of the Jensen-Shannon divergence between probability distributions, to two symbolic sequences of literary and musical origin. The first sequence represents the successive appearance of characters in a theatrical play, and the second represents the succession of tones from the twelve-tone scale in a keyboard sonata. The algorithm divides the sequences into segments of maximal compositional divergence between them. For the play, these segments are related to changes in the frequency of appearance of different characters and in the geographical setting of the action. For the sonata, the segments correspond to tonal domains and reveal in detail the characteristic tonal progression of such kind of musical composition.
Exploration via design and the cost of uncertainty in keyword auctions
Venue: arXiv cs.GT 2007
Year: 2007

We present a deterministic exploration mechanism for sponsored search auctions, which enables the auctioneer to learn the relevance scores of advertisers, and allows advertisers to estimate the true value of clicks generated at the auction site. This exploratory mechanism deviates only minimally from the mechanism being currently used by Google and Yahoo! in the sense that it retains the same pricing rule, similar ranking scheme, as well as, similar mathematical structure of payoffs. In particular, the estimations of the relevance scores and true-values are achieved by providing a chance to lower ranked advertisers to obtain better slots. This allows the search engine to potentially test a new pool of advertisers, and correspondingly, enables new advertisers to estimate the value of clicks/leads generated via the auction. Both these quantities are unknown a priori, and their knowledge is necessary for the auction to operate efficiently. We show that such an exploration policy can be incorporated without any significant loss in revenue for the auctioneer. We compare the revenue of the new mechanism to that of the standard mechanism at their corresponding symmetric Nash equilibria and compute the cost of uncertainty, which is defined as the relative loss in expected revenue per impression. We also bound the loss in efficiency, as well as, in user experience due to exploration, under the same solution concept (i.e. SNE). Thus the proposed exploration mechanism learns the relevance scores while incorporating the incentive constraints from the advertisers who are selfish and are trying to maximize their own profits, and therefore, the exploration is essentially achieved via mechanism design. We also discuss variations of the new mechanism such as truthful implementations.
For-profit mediators in sponsored search advertising
Venue: arXiv cs.GT 2007
Year: 2007

A mediator is a well-known construct in game theory, and is an entity that plays on behalf of some of the agents who choose to use its services, while the rest of the agents participate in the game directly. We initiate a game theoretic study of sponsored search auctions, such as those used by Google and Yahoo!, involving {\em incentive driven} mediators. We refer to such mediators as {\em for-profit} mediators, so as to distinguish them from mediators introduced in prior work, who have no monetary incentives, and are driven by the altruistic goal of implementing certain desired outcomes. We show that in our model, (i) players/advertisers can improve their payoffs by choosing to use the services of the mediator, compared to directly participating in the auction; (ii) the mediator can obtain monetary benefit by managing the advertising burden of its group of advertisers; and (iii) the payoffs of the mediator and the advertisers it plays for are compatible with the incentive constraints from the advertisers who do dot use its services. A simple intuition behind the above result comes from the observation that the mediator has more information about and more control over the bid profile than any individual advertiser, allowing her to reduce the payments made to the auctioneer, while still maintaining incentive constraints. Further, our results indicate that there are significant opportunities for diversification in the internet economy and we should expect it to continue to develop richer structure, with room for different types of agents to coexist.
Worst-Case Interactive Communication and Enhancing Sensor Network Lifetime
Venue: arXiv cs.IT 2007
Year: 2007

We are concerned with the problem of maximizing the worst-case lifetime of a data-gathering wireless sensor network consisting of a set of sensor nodes directly communicating with a base-station.We propose to solve this problem by modeling sensor node and base-station communication as the interactive communication between multiple correlated informants (sensor nodes) and a recipient (base-station). We provide practical and scalable interactive communication protocols for data gathering in sensor networks and demonstrate their efficiency compared to traditional approaches. In this paper, we first develop a formalism to address the problem of worst-case interactive communication between a set of multiple correlated informants and a recipient. We realize that there can be different objectives to achieve in such a communication scenario and compute the optimal number of messages and bits exchanged to realize these objectives. Then, we propose to adapt these results in the context of single-hop data-gathering sensor networks. Finally, based on this proposed formalism, we propose a clustering based communication protocol for large sensor networks and demonstrate its superiority over a traditional clustering protocol.
Logic, Design & Organization of PTVD-SHAM; A Parallel Time Varying & Data Super-helical Access Memory
Venue: arXiv cs.AR 2007
Year: 2007

This paper encompasses a super helical memory system's design, 'Boolean logic & image-logic' as a theoretical concept of an invention-model to 'store time-data' in terms of anticipating the best memory location ever for data/time. A waterfall effect is deemed to assist the process of potential-difference output-switch into diverse logic states in quantum dot computational methods via utilizing coiled carbon nanotubes (CCNTs) and carbon nanotube field effect transistors (CNFETs). A 'quantum confinement' is thus derived for a flow of particles in a categorized quantum well substrate with a normalized capacitance rectifying high B-field flux into electromagnetic induction. Multi-access of coherent sequences of 'qubit addressing' is gained in any magnitude as pre-defined for the orientation of array displacement. Briefly, Gaussian curvature of k<0 is debated in aim of specifying the 2D electron gas characteristics in scenarios where data is stored in short intervals versus long ones e.g. when k'>(k<0) for greater CCNT diameters, space-time continuum is folded by chance for the particle. This benefits from Maxwell-Lorentz theory in Minkowski's space-time viewpoint alike to crystal oscillators for precise data timing purposes and radar systems e.g., time varying self-clocking devices in diverse geographic locations. This application could also be optional for data depository versus extraction, in the best supercomputer system's locations, autonomously. For best performance in minimizing current limiting mechanisms including electromigration, a multilevel metallization and implant process forming elevated sources/drains for the circuit's staircase pyramidal construction, is discussed accordingly.
Singular curves and cusp points in the joint space of 3-RPR parallel manipulators
Venue: arXiv cs.RO 2007
Year: 2007

This paper investigates the singular curves in two-dimensional slices of the joint space of a family of planar parallel manipulators. It focuses on special points, referred to as cusp points, which may appear on these curves. Cusp points play an important role in the kinematic behavior of parallel manipulators since they make possible a nonsingular change of assembly mode. The purpose of this study is twofold. First, it reviews an important previous work, which, to the authors' knowledge, has never been exploited yet. Second, it determines the cusp points in any two-dimensional slice of the joint space. First results show that the number of cusp points may vary from zero to eight. This work finds applications in both design and trajectory planning.
Building Decision Procedures in the Calculus of Inductive Constructions
Venue: arXiv cs.LO 2007
Year: 2007

It is commonly agreed that the success of future proof assistants will rely on their ability to incorporate computations within deduction in order to mimic the mathematician when replacing the proof of a proposition P by the proof of an equivalent proposition P' obtained from P thanks to possibly complex calculations. In this paper, we investigate a new version of the calculus of inductive constructions which incorporates arbitrary decision procedures into deduction via the conversion rule of the calculus. The novelty of the problem in the context of the calculus of inductive constructions lies in the fact that the computation mechanism varies along proof-checking: goals are sent to the decision procedure together with the set of user hypotheses available from the current context. Our main result shows that this extension of the calculus of constructions does not compromise its main properties: confluence, subject reduction, strong normalization and consistency are all preserved.
Data Mining-based Materialized View and Index Selection in Data Warehouses
Venue: arXiv cs.DB 2007
Year: 2007

Materialized views and indexes are physical structures for accelerating data access that are casually used in data warehouses. However, these data structures generate some maintenance overhead. They also share the same storage space. Most existing studies about materialized view and index selection consider these structures separately. In this paper, we adopt the opposite stance and couple materialized view and index selection to take view-index interactions into account and achieve efficient storage space sharing. Candidate materialized views and indexes are selected through a data mining process. We also exploit cost models that evaluate the respective benefit of indexing and view materialization, and help select a relevant configuration of indexes and materialized views among the candidates. Experimental results show that our strategy performs better than an independent selection of materialized views and indexes.
Fast and Simple Relational Processing of Uncertain Data
Venue: arXiv cs.DB 2007
Year: 2007

This paper introduces U-relations, a succinct and purely relational representation system for uncertain databases. U-relations support attribute-level uncertainty using vertical partitioning. If we consider positive relational algebra extended by an operation for computing possible answers, a query on the logical level can be translated into, and evaluated as, a single relational algebra query on the U-relation representation. The translation scheme essentially preserves the size of the query in terms of number of operations and, in particular, number of joins. Standard techniques employed in off-the-shelf relational database management systems are effective for optimizing and processing queries on U-relations. In our experiments we show that query evaluation on U-relations scales to large amounts of data with high degrees of uncertainty.
Understanding the Properties of the BitTorrent Overlay
Venue: arXiv cs.NI 2007
Year: 2007

In this paper, we conduct extensive simulations to understand the properties of the overlay generated by BitTorrent. We start by analyzing how the overlay properties impact the efficiency of BitTorrent. We focus on the average peer set size (i.e., average number of neighbors), the time for a peer to reach its maximum peer set size, and the diameter of the overlay. In particular, we show that the later a peer arrives in a torrent, the longer it takes to reach its maximum peer set size. Then, we evaluate the impact of the maximum peer set size, the maximum number of outgoing connections per peer, and the number of NATed peers on the overlay properties. We show that BitTorrent generates a robust overlay, but that this overlay is not a random graph. In particular, the connectivity of a peer to its neighbors depends on its arriving order in the torrent. We also show that a large number of NATed peers significantly compromise the robustness of the overlay to attacks. Finally, we evaluate the impact of peer exchange on the overlay properties, and we show that it generates a chain-like overlay with a large diameter, which will adversely impact the efficiency of large torrents.
Throughput Scaling Laws for Wireless Networks with Fading Channels
Venue: arXiv cs.IT 2007
Year: 2007

A network of n communication links, operating over a shared wireless channel, is considered. Fading is assumed to be the dominant factor affecting the strength of the channels between transmitter and receiver terminals. It is assumed that each link can be active and transmit with a constant power P or remain silent. The objective is to maximize the throughput over the selection of active links. By deriving an upper bound and a lower bound, it is shown that in the case of Rayleigh fading (i) the maximum throughput scales like $\log n$ (ii) the maximum throughput is achievable in a distributed fashion. The upper bound is obtained using probabilistic methods, where the key point is to upper bound the throughput of any random set of active links by a chi-squared random variable. To obtain the lower bound, a decentralized link activation strategy is proposed and analyzed.
Working Modes and Aspects in Fully-Parallel Manipulator
Venue: arXiv cs.RO 2007
Year: 2007

The aim of this paper is to characterize the notion of aspect in the workspace and in the joint space for parallel manipulators. In opposite to the serial manipulators, the parallel manipulators can admit not only multiple inverse kinematic solutions, but also multiple direct kinematic solutions. The notion of aspect introduced for serial manipulators in [Borrel 86], and redefined for parallel manipulators with only one inverse kinematic solution in [Wenger 1997], is redefined for general fully parallel manipulators. Two Jacobian matrices appear in the kinematic relations between the joint-rate and the Cartesian-velocity vectors, which are called the "inverse kinematics" and the "direct kinematics" matrices. The study of these matrices allow to respectively define the parallel and the serial singularities. The notion of working modes is introduced to separate inverse kinematic solutions. Thus, we can find out domains of the workspace and the joint space exempt of singularity. Application of this study is the moveability analysis in the workspace of the manipulator as well as path-planing and control. This study is illustrated in this paper with a RR-RRR planar parallel manipulator.
On complexity of special maximum matchings constructing
Venue: arXiv cs.DM 2007
Year: 2007

For bipartite graphs the NP-completeness is proved for the problem of existence of maximum matching which removal leads to a graph with given lower(upper)bound for the cardinality of its maximum matching.
Passive Control Architecture for Virtual Humans
Venue: arXiv cs.RO 2007
Year: 2007

In the present paper, we introduce a new control architecture aimed at driving virtual humans in interaction with virtual environments, by motion capture. It brings decoupling of functionalities, and also of stability thanks to passivity. We show projections can break passivity, and thus must be used carefully. Our control scheme enables task space and internal control, contact, and joint limits management. Thanks to passivity, it can be easily extended. Besides, we introduce a new tool as for manikin's control, which makes it able to build passive projections, so as to guide the virtual manikin when sharp movements are needed.
Faster exon assembly by sparse spliced alignment
Venue: arXiv cs.DS 2007
Year: 2007

Assembling a gene from candidate exons is an important problem in computational biology. Among the most successful approaches to this problem is \emph{spliced alignment}, proposed by Gelfand et al., which scores different candidate exon chains within a DNA sequence of length $m$ by comparing them to a known related gene sequence of length n, $m = Θ(n)$. Gelfand et al.\ gave an algorithm for spliced alignment running in time O(n^3). Kent et al.\ considered sparse spliced alignment, where the number of candidate exons is O(n), and proposed an algorithm for this problem running in time O(n^{2.5}). We improve on this result, by proposing an algorithm for sparse spliced alignment running in time O(n^{2.25}). Our approach is based on a new framework of \emph{quasi-local string comparison}.
Zero-automatic queues and product form
Venue: arXiv cs.DM 2007
Year: 2007

We introduce and study a new model: 0-automatic queues. Roughly, 0-automatic queues are characterized by a special buffering mechanism evolving like a random walk on some infinite group or monoid. The salient result is that all stable 0-automatic queues have a product form stationary distribution and a Poisson output process. When considering the two simplest and extremal cases of 0-automatic queues, we recover the simple M/M/1 queue, and Gelenbe's G-queue with positive and negative customers.
Analyse Comparative des Manipulateurs 3R à Axes Orthogonaux
Venue: arXiv cs.RO 2007
Year: 2007

A family of 3R orthogonal manipulators without offset on the third body can be divided into exactly nine workspace topologies. The workspace is characterized in a half-cross section by the singular curves. The workspace topology is defined by the number of cusps and nodes that appear on these singular curves. Based on this classification, we evaluate theses manipulators by the condition number related to the joint space and the proportion of the region with four inverse kinematic solutions compared to a sphere containing all the workspace. This second performance number is in relation with the workspace. We determine finally le topology of workspace to which belong manipulators having the best performance number values.
Integration of a Balanced Virtual Manikin in a Virtual Reality Platform aimed at Virtual Prototyping
Venue: arXiv cs.RO 2007
Year: 2007

The work presented here is aimed at introducing a virtual human controller in a virtual prototyping framework. After a brief introduction describing the problem solved in the paper, we describe the interest as for digital humans in the context of concurrent engineering. This leads us to draw a control architecture enabling to drive virtual humans in a real-time immersed way, and to interact with the product, through motion capture. Unfortunately, we show this control scheme can lead to unfeasible movements because of the lack of balance control. Introducing such a controller is a problem that was never addressed in the context of real-time. We propose an implementation of a balance controller, that we insert into the previously described control scheme. Next section is dedicated to show the results we obtained. Finally, we propose a virtual reality platform into which the digital character controller is integrated.
The Review and Analysis of Human Computer Interaction (HCI) Principles
Venue: arXiv cs.HC 2007
Year: 2007

The History of HCI is briefly reviewed together with three HCI models and structure including CSCW, CSCL and CSCR. It is shown that a number of authorities consider HCI to be a fragmented discipline with no agreed set of unifying design principles. An analysis of usability criteria based upon citation frequency of authors is performed in order to discover the eight most recognised HCI principles.
Kinematic Analysis of a New Parallel Machine Tool: the Orthoglide
Venue: arXiv cs.RO 2007
Year: 2007

This paper describes a new parallel kinematic architecture for machining applications: the orthoglide. This machine features three fixed parallel linear joints which are mounted orthogonally and a mobile platform which moves in the Cartesian x-y-z space with fixed orientation. The main interest of the orthoglide is that it takes benefit from the advantages of the popular PPP serial machines (regular Cartesian workspace shape and uniform performances) as well as from the parallel kinematic arrangement of the links (less inertia and better dynamic performances), which makes the orthoglide well suited to high-speed machining applications. Possible extension of the orthoglide to 5-axis machining is also investigated.
Products of irreducible random matrices in the (Max,+) Algebra
Venue: arXiv cs.OH 2007
Year: 2007

We consider the recursive equation ``x(n+1)=A(n)x(n)'' where x(n+1) and x(n) are column vectors of size k and where A(n) is an irreducible random matrix of size k x k. The matrix-vector multiplication in the (max,+) algebra is defined by (A(n)x(n))_i= max_j [ A(n)_{ij} +x(n)_j ]. This type of equation can be used to represent the evolution of Stochastic Event Graphs which include cyclic Jackson Networks, some manufacturing models and models with general blocking (such as Kanban). Let us assume that the sequence (A(n))_n is i.i.d or more generally stationary and ergodic. The main result of the paper states that the system couples in finite time with a unique stationary regime if and only if there exists a set of matrices C such that P {A(0) in C} > 0, and the matrices in C have a unique periodic regime.
Learning Probabilistic Models of Word Sense Disambiguation
Venue: arXiv cs.CL 2007
Year: 2007

This dissertation presents several new methods of supervised and unsupervised learning of word sense disambiguation models. The supervised methods focus on performing model searches through a space of probabilistic models, and the unsupervised methods rely on the use of Gibbs Sampling and the Expectation Maximization (EM) algorithm. In both the supervised and unsupervised case, the Naive Bayesian model is found to perform well. An explanation for this success is presented in terms of learning rates and bias-variance decompositions.