OpenRaiser/Intern-Atlas huggingface dataset:
Bit-Interleaved Coded Modulation Revisited: A Mismatched Decoding Perspective
Venue: arXiv cs.IT 2008
Year: 2008

We revisit the information-theoretic analysis of bit-interleaved coded modulation (BICM) by modeling the BICM decoder as a mismatched decoder. The mismatched decoding model is well-defined for finite, yet arbitrary, block lengths, and naturally captures the channel memory among the bits belonging to the same symbol. We give two independent proofs of the achievability of the BICM capacity calculated by Caire et al. where BICM was modeled as a set of independent parallel binary-input channels whose output is the bitwise log-likelihood ratio. Our first achievability proof uses typical sequences, and shows that due to the random coding construction, the interleaver is not required. The second proof is based on the random coding error exponents with mismatched decoding, where the largest achievable rate is the generalized mutual information. We show that the generalized mutual information of the mismatched decoder coincides with the infinite-interleaver BICM capacity. We also show that the error exponent -and hence the cutoff rate- of the BICM mismatched decoder is upper bounded by that of coded modulation and may thus be lower than in the infinite-interleaved model. We also consider the mutual information appearing in the analysis of iterative decoding of BICM with EXIT charts. We show that the corresponding symbol metric has knowledge of the transmitted symbol and the EXIT mutual information admits a representation as a pseudo-generalized mutual information, which is in general not achievable. A different symbol decoding metric, for which the extrinsic side information refers to the hypothesized symbol, induces a generalized mutual information lower than the coded modulation capacity.
A Time Efficient Indexing Scheme for Complex Spatiotemporal Retrieval
Venue: arXiv cs.DB 2008
Year: 2008

The paper is concerned with the time efficient processing of spatiotemporal predicates, i.e. spatial predicates associated with an exact temporal constraint. A set of such predicates forms a buffer query or a Spatio-temporal Pattern (STP) Query with time. In the more general case of an STP query, the temporal dimension is introduced via the relative order of the spatial predicates (STP queries with order). Therefore, the efficient processing of a spatiotemporal predicate is crucial for the efficient implementation of more complex queries of practical interest. We propose an extension of a known approach, suitable for processing spatial predicates, which has been used for the efficient manipulation of STP queries with order. The extended method is supported by efficient indexing structures. We also provide experimental results that show the efficiency of the technique.
Algorithmic Methods for Sponsored Search Advertising
Venue: arXiv cs.GT 2008
Year: 2008

Modern commercial Internet search engines display advertisements along side the search results in response to user queries. Such sponsored search relies on market mechanisms to elicit prices for these advertisements, making use of an auction among advertisers who bid in order to have their ads shown for specific keywords. We present an overview of the current systems for such auctions and also describe the underlying game-theoretic aspects. The game involves three parties--advertisers, the search engine, and search users--and we present example research directions that emphasize the role of each. The algorithms for bidding and pricing in these games use techniques from three mathematical areas: mechanism design, optimization, and statistical estimation. Finally, we present some challenges in sponsored search advertising.
Tuplix Calculus Specifications of Financial Transfer Networks
Venue: arXiv cs.CE 2008
Year: 2008

We study the application of Tuplix Calculus in modular financial budget design. We formalize organizational structure using financial transfer networks. We consider the notion of flux of money over a network, and a way to enforce the matching of influx and outflux for parts of a network. We exploit so-called signed attribute notation to make internal streams visible through encapsulations. Finally, we propose a Tuplix Calculus construct for the definition of data functions.
The Gaussian Many-Help-One Distributed Source Coding Problem
Venue: arXiv cs.IT 2008
Year: 2008

Jointly Gaussian memoryless sources are observed at N distinct terminals. The goal is to efficiently encode the observations in a distributed fashion so as to enable reconstruction of any one of the observations, say the first one, at the decoder subject to a quadratic fidelity criterion. Our main result is a precise characterization of the rate-distortion region when the covariance matrix of the sources satisfies a "tree-structure" condition. In this situation, a natural analog-digital separation scheme optimally trades off the distributed quantization rate tuples and the distortion in the reconstruction: each encoder consists of a point-to-point Gaussian vector quantizer followed by a Slepian-Wolf binning encoder. We also provide a partial converse that suggests that the tree structure condition is fundamental.
Heavy-Tailed Limits for Medium Size Jobs and Comparison Scheduling
Venue: arXiv cs.PF 2008
Year: 2008

We study the conditional sojourn time distributions of processor sharing (PS), foreground background processor sharing (FBPS) and shortest remaining processing time first (SRPT) scheduling disciplines on an event where the job size of a customer arriving in stationarity is smaller than exactly k>=0 out of the preceding m>=k arrivals. Then, conditioning on the preceding event, the sojourn time distribution of this newly arriving customer behaves asymptotically the same as if the customer were served in isolation with a server of rate (1-ρ)/(k+1) for PS/FBPS, and (1-ρ) for SRPT, respectively, where ρis the traffic intensity. Hence, the introduced notion of conditional limits allows us to distinguish the asymptotic performance of the studied schedulers by showing that SRPT exhibits considerably better asymptotic behavior for relatively smaller jobs than PS/FBPS. Inspired by the preceding results, we propose an approximation to the SRPT discipline based on a novel adaptive job grouping mechanism that uses relative size comparison of a newly arriving job to the preceding m arrivals. Specifically, if the newly arriving job is smaller than k and larger than m-k of the previous m jobs, it is routed into class k. Then, the classes of smaller jobs are served with higher priorities using the static priority scheduling. The good performance of this mechanism, even for a small number of classes m+1, is demonstrated using the asymptotic queueing analysis under the heavy-tailed job requirements. We also discuss refinements of the comparison grouping mechanism that improve the accuracy of job classification at the expense of a small additional complexity.
Semantic Analysis of Tag Similarity Measures in Collaborative Tagging Systems
Venue: arXiv cs.DL 2008
Year: 2008

Social bookmarking systems allow users to organise collections of resources on the Web in a collaborative fashion. The increasing popularity of these systems as well as first insights into their emergent semantics have made them relevant to disciplines like knowledge extraction and ontology learning. The problem of devising methods to measure the semantic relatedness between tags and characterizing it semantically is still largely open. Here we analyze three measures of tag relatedness: tag co-occurrence, cosine similarity of co-occurrence distributions, and FolkRank, an adaptation of the PageRank algorithm to folksonomies. Each measure is computed on tags from a large-scale dataset crawled from the social bookmarking system del.icio.us. To provide a semantic grounding of our findings, a connection to WordNet (a semantic lexicon for the English language) is established by mapping tags into synonym sets of WordNet, and applying there well-known metrics of semantic similarity. Our results clearly expose different characteristics of the selected measures of relatedness, making them applicable to different subtasks of knowledge extraction such as synonym detection or discovery of concept hierarchies.
Replication via Invalidating the Applicability of the Fixed Point Theorem
Venue: arXiv cs.LO 2008
Year: 2008

We present a construction of a certain infinite complete partial order (CPO) that differs from the standard construction used in Scott's denotational semantics. In addition, we construct several other infinite CPO's. For some of those, we apply the usual Fixed Point Theorem (FPT) to yield a fixed point for every continuous function $μ:2\to 2$ (where 2 denotes the set $\{0,1\}$), while for the other CPO's we cannot invoke that theorem to yield such fixed points. Every element of each of these CPO's is a binary string in the monotypic form and we show that invalidation of the applicability of the FPT to the CPO that Scott's constructed yields the concept of replication.
Path Diversity over Packet Switched Networks: Performance Analysis and Rate Allocation
Venue: arXiv cs.NI 2008
Year: 2008

Path diversity works by setting up multiple parallel connections between the end points using the topological path redundancy of the network. In this paper, \textit{Forward Error Correction} (FEC) is applied across multiple independent paths to enhance the end-to-end reliability. Network paths are modeled as erasure Gilbert-Elliot channels. It is known that over any erasure channel, \textit{Maximum Distance Separable} (MDS) codes achieve the minimum probability of irrecoverable loss among all block codes of the same size. Based on the adopted model for the error behavior, we prove that the probability of irrecoverable loss for MDS codes decays exponentially for an asymptotically large number of paths. Then, optimal rate allocation problem is solved for the asymptotic case where the number of paths is large. Moreover, it is shown that in such asymptotically optimal rate allocation, each path is assigned a positive rate \textit{iff} its quality is above a certain threshold. The quality of a path is defined as the percentage of the time it spends in the bad state. Finally, using dynamic programming, a heuristic suboptimal algorithm with polynomial runtime is proposed for rate allocation over a finite number of paths. This algorithm converges to the asymptotically optimal rate allocation when the number of paths is large. The simulation results show that the proposed algorithm approximates the optimal rate allocation (found by exhaustive search) very closely for practical number of paths, and provides significant performance improvement compared to the alternative schemes of rate allocation.
Secure Network Coding Against the Contamination and Eavesdropping Adversaries
Venue: arXiv cs.CR 2008
Year: 2008

In this paper, we propose an algorithm that targets contamination and eavesdropping adversaries. We consider the case when the number of independent packets available to the eavesdropper is less than the multicast capacity of the network. By means of our algorithm every node can verify the integrity of the received packets easily and an eavesdropper is unable to get any meaningful information about the source. We call it practical security if an eavesdropper is unable to get any meaningful information about the source.We show that, by giving up a small amount of overall capacity, our algorithm achieves achieves the practically secure condition at a probability of one. Furthermore, the communication overhead of our algorithm are negligible compared with previous works, since the transmission of the hash values and the code coefficients are both avoided.
Unirational fields of transcendence degree one and functional decomposition
Venue: arXiv cs.SC 2008
Year: 2008

In this paper we present an algorithm to compute all unirational fields of transcendence degree one containing a given finite set of multivariate rational functions. In particular, we provide an algorithm to decompose a multivariate rational function f of the form f=g(h), where g is a univariate rational function and h a multivariate one.
Transceiver Pair Designs for Multiple Access Channels under Fixed Sum Mutual Information using MMSE Decision Feedback Detection
Venue: arXiv cs.IT 2008
Year: 2008

In this paper, we consider the joint design of the transceivers for a multiple access Multiple Input and Multiple Output (MIMO) system having Inter-Symbol Interference (ISI) channels. The system we consider is equipped with the Minimum Mean Square Error (MMSE) Decision-Feedback (DF) detector. Traditionally, transmitter designs for this system have been based on constraints of either the transmission power or the signal-to-interference-and-noise ratio (SINR) for each user. Here, we explore a novel perspective and examine a transceiver design which is based on a fixed sum mutual information constraint and minimizes the arithmetic average of mean square error of MMSE-decision feedback detection. For this optimization problem, a closed-form solution is obtained and is achieved if and only if the averaged sum mutual information is uniformly distributed over each active subchannel. Meanwhile, the mutual information of the currently detected user is uniformly distributed over each individual symbol within the block signal of the user, assuming all the previous user signals have been perfectly detected.
On Full Diversity Space-Time Block Codes with Partial Interference Cancellation Group Decoding
Venue: arXiv cs.IT 2008
Year: 2008

In this paper, we propose a partial interference cancellation (PIC) group decoding for linear dispersive space-time block codes (STBC) and a design criterion for the codes to achieve full diversity when the PIC group decoding is used at the receiver. A PIC group decoding decodes the symbols embedded in an STBC by dividing them into several groups and decoding each group separately after a linear PIC operation is implemented. It can be viewed as an intermediate decoding between the maximum likelihood (ML) receiver that decodes all the embedded symbols together, i.e., all the embedded symbols are in a single group, and the zero-forcing (ZF) receiver that decodes all the embedded symbols separately and independently, i.e., each group has and only has one embedded symbol, after the ZF operation is implemented. Our proposed design criterion for the PIC group decoding to achieve full diversity is an intermediate condition between the loosest ML full rank criterion of codewords and the strongest ZF linear independence condition of the column vectors in the equivalent channel matrix. We also propose asymptotically optimal (AO) group decoding algorithm, which is an intermediate decoding between the MMSE decoding algorithm and the ML decoding algorithm. The design criterion for the PIC group decoding applies to the AO group decoding algorithm. It is well-known that the symbol rate for a full rank linear STBC can be full, i.e., n_t for n_t transmit antennas. It has been recently shown that its rate is upper bounded by 1 if a code achieves full diversity with a linear receiver. The intermediate criterion proposed in this paper provides the possibility for codes of rates between n_t and 1 that achieve full diversity with a PIC group decoding. This therefore provides a complexity-performance-rate tradeoff.
Lossy Source Transmission over the Relay Channel
Venue: arXiv cs.IT 2008
Year: 2008

Lossy transmission over a relay channel in which the relay has access to correlated side information is considered. First, a joint source-channel decode-and-forward scheme is proposed for general discrete memoryless sources and channels. Then the Gaussian relay channel where the source and the side information are jointly Gaussian is analyzed. For this Gaussian model, several new source-channel cooperation schemes are introduced and analyzed in terms of the squared-error distortion at the destination. A comparison of the proposed upper bounds with the cut-set lower bound is given, and it is seen that joint source-channel cooperation improves the reconstruction quality significantly. Moreover, the performance of the joint code is close to the lower bound on distortion for a wide range of source and channel parameters.
To Code or Not To Code in Multi-Hop Relay Channels
Venue: arXiv cs.IT 2008
Year: 2008

Multi-hop relay channels use multiple relay stages, each with multiple relay nodes, to facilitate communication between a source and destination. Previously, distributed space-time coding was used to maximize diversity gain. Assuming a low-rate feedback link from the destination to each relay stage and the source, this paper proposes end-to-end antenna selection strategies as an alternative to distributed space-time coding. One-way (where only the source has data for destination) and two-way (where the destination also has data for the source) multi-hop relay channels are considered with both the full-duplex and half duplex relay nodes. End-to-end antenna selection strategies are designed and proven to achieve maximum diversity gain by using a single antenna path (using single antenna of the source, each relay stage and the destination) with the maximum signal-to-noise ratio at the destination. For the half-duplex case, two single antenna paths with the two best signal-to-noise ratios in alternate time slots are used to overcome the rate loss with half-duplex nodes, with a small diversity gain penalty. Finally to answer the question, whether to code (distributed space-time code) or not (the proposed end-to-end antenna selection strategy) in a multi-hop relay channel, end-to-end antenna selection strategy and distributed space-time coding is compared with respect to several important performance metrics.
Tri de la table de faits et compression des index bitmaps avec alignement sur les mots
Venue: arXiv cs.DB 2008
Year: 2008

Bitmap indexes are frequently used to index multidimensional data. They rely mostly on sequential input/output. Bitmaps can be compressed to reduce input/output costs and minimize CPU usage. The most efficient compression techniques are based on run-length encoding (RLE), such as Word-Aligned Hybrid (WAH) compression. This type of compression accelerates logical operations (AND, OR) over the bitmaps. However, run-length encoding is sensitive to the order of the facts. Thus, we propose to sort the fact tables. We review lexicographic, Gray-code, and block-wise sorting. We found that a lexicographic sort improves compression--sometimes generating indexes twice as small--and make indexes several times faster. While sorting takes time, this is partially offset by the fact that it is faster to index a sorted table. Column order is significant: it is generally preferable to put the columns having more distinct values at the beginning. A block-wise sort is much less efficient than a full sort. Moreover, we found that Gray-code sorting is not better than lexicographic sorting when using word-aligned compression.
Logic programming with social features
Venue: arXiv cs.AI 2008
Year: 2008

In everyday life it happens that a person has to reason about what other people think and how they behave, in order to achieve his goals. In other words, an individual may be required to adapt his behaviour by reasoning about the others' mental state. In this paper we focus on a knowledge representation language derived from logic programming which both supports the representation of mental states of individual communities and provides each with the capability of reasoning about others' mental states and acting accordingly. The proposed semantics is shown to be translatable into stable model semantics of logic programs with aggregates.
Overlay Cognitive Radio in Wireless Mesh Networks
Venue: arXiv cs.IT 2008
Year: 2008

In this paper we apply the concept of overlay cognitive radio to the communication between nodes in a wireless mesh network. Based on the overlay cognitive radio model, it is possible to have two concurrent transmissions in a given interference region, where usually only one communication takes place at a given time. We analyze the cases of wireless mesh networks with regular and random topologies. Numerical results show that considerable network capacity gains can be achieved.
The Structure of Narrative: the Case of Film Scripts
Venue: arXiv cs.AI 2008
Year: 2008

We analyze the style and structure of story narrative using the case of film scripts. The practical importance of this is noted, especially the need to have support tools for television movie writing. We use the Casablanca film script, and scripts from six episodes of CSI (Crime Scene Investigation). For analysis of style and structure, we quantify various central perspectives discussed in McKee's book, "Story: Substance, Structure, Style, and the Principles of Screenwriting". Film scripts offer a useful point of departure for exploration of the analysis of more general narratives. Our methodology, using Correspondence Analysis, and hierarchical clustering, is innovative in a range of areas that we discuss. In particular this work is groundbreaking in taking the qualitative analysis of McKee and grounding this analysis in a quantitative and algorithmic framework.
SPARK00: A Benchmark Package for the Compiler Evaluation of Irregular/Sparse Codes
Venue: arXiv cs.PF 2008
Year: 2008

We propose a set of benchmarks that specifically targets a major cause of performance degradation in high performance computing platforms: irregular access patterns. These benchmarks are meant to be used to asses the performance of optimizing compilers on codes with a varying degree of irregular access. The irregularity caused by the use of pointers and indirection arrays are a major challenge for optimizing compilers. Codes containing such patterns are notoriously hard to optimize but they have a huge impact on the performance of modern architectures, which are under-utilized when encountering irregular memory accesses. In this paper, a set of benchmarks is described that explicitly measures the performance of kernels containing a variety of different access patterns found in real world applications. By offering a varying degree of complexity, we provide a platform for measuring the effectiveness of transformations. The difference in complexity stems from a difference in traversal patterns, the use of multiple indirections and control flow statements. The kernels used cover a variety of different access patterns, namely pointer traversals, indirection arrays, dynamic loop bounds and run-time dependent if-conditions. The kernels are small enough to be fully understood which makes this benchmark set very suitable for the evaluation of restructuring transformations.
Fusion for Evaluation of Image Classification in Uncertain Environments
Venue: arXiv cs.AI 2008
Year: 2008

We present in this article a new evaluation method for classification and segmentation of textured images in uncertain environments. In uncertain environments, real classes and boundaries are known with only a partial certainty given by the experts. Most of the time, in many presented papers, only classification or only segmentation are considered and evaluated. Here, we propose to take into account both the classification and segmentation results according to the certainty given by the experts. We present the results of this method on a fusion of classifiers of sonar images for a seabed characterization.
Source Coding for a Simple Network with Receiver Side Information
Venue: arXiv cs.IT 2008
Year: 2008

We consider the problem of source coding with receiver side information for the simple network proposed by R. Gray and A. Wyner in 1974. In this network, a transmitter must reliably transport the output of two correlated information sources to two receivers using three noiseless channels: a public channel which connects the transmitter to both receivers, and two private channels which connect the transmitter directly to each receiver. We extend Gray and Wyner's original problem by permitting side information to be present at each receiver. We derive inner and outer bounds for the achievable rate region and, for three special cases, we show that the outer bound is tight.