OpenRaiser/Intern-Atlas huggingface dataset:
Variational local structure estimation for image super-resolution
Venue: arXiv cs.CV 2007
Year: 2007

Super-resolution is an important but difficult problem in image/video processing. If a video sequence or some training set other than the given low-resolution image is available, this kind of extra information can greatly aid in the reconstruction of the high-resolution image. The problem is substantially more difficult with only a single low-resolution image on hand. The image reconstruction methods designed primarily for denoising is insufficient for super-resolution problem in the sense that it tends to oversmooth images with essentially no noise. We propose a new adaptive linear interpolation method based on variational method and inspired by local linear embedding (LLE). The experimental result shows that our method avoids the problem of oversmoothing and preserves image structures well.
Connecting Polygonizations via Stretches and Twangs
Venue: arXiv cs.CG 2007
Year: 2007

We show that the space of polygonizations of a fixed planar point set S of n points is connected by O(n^2) ``moves'' between simple polygons. Each move is composed of a sequence of atomic moves called ``stretches'' and ``twangs''. These atomic moves walk between weakly simple ``polygonal wraps'' of S. These moves show promise to serve as a basis for generating random polygons.
Otiy: Loactors tracking nodes
Venue: arXiv cs.NI 2007
Year: 2007

We propose Otiy, a node-centric location service that limits the impact of location updates generate by mobile nodes in IEEE802.11-based wireless mesh networks. Existing location services use node identifiers to determine the locator (aka anchor) that is responsible for keeping track of a node's location. Such a strategy can be inefficient because: (i) identifiers give no clue on the node's mobility and (ii) locators can be far from the source/destination shortest path, which increases both location delays and bandwidth consumption. To solve these issues, Otiy introduces a new strategy that identifies nodes to play the role of locators based on the likelihood of a destination to be close to these nodes- i.e., locators are identified depending on the mobility pattern of nodes. Otiy relies on the cyclic mobility patterns of nodes and creates a slotted agenda composed of a set of predicted locations, defined according to the past and present patterns of mobility. Correspondent nodes fetch this agenda only once and use it as a reference for identifying which locators are responsible for the node at different points in time. Over a period of about one year, the weekly proportion of nodes having at least 50% of exact location predictions is in average about 75%. This proportion increases by 10% when nodes also consider their closeness to the locator from only what they know about the network.
Bootstrapping Deep Lexical Resources: Resources for Courses
Venue: arXiv cs.CL 2007
Year: 2007

We propose a range of deep lexical acquisition methods which make use of morphological, syntactic and ontological language resources to model word similarity and bootstrap from a seed lexicon. The different methods are deployed in learning lexical items for a precision grammar, and shown to each have strengths and weaknesses over different word classes. A particular focus of this paper is the relative accessibility of different language resource types, and predicted ``bang for the buck'' associated with each in deep lexical acquisition applications.
On the 3/4-Conjecture for Fix-Free Codes -- A Survey
Venue: arXiv cs.IT 2007
Year: 2007

In this survey we concern ourself with the question, wether there exists a fix-free code for a given sequence of codeword lengths. For a given alphabet, we obtain the {\em Kraftsum} of a code, if we divide for every length the number of codewords of this length in the code by the total number of all possible words of this length and then take summation over all codeword lengths which appears in the code. The same way the Kraftsum of a lengths sequence $(l_1,..., l_n) $ is given by $\sum_{i=1}^n q^{-l_i} $, where $q$ is the numbers of letters in the alphabet. Kraft and McMillan have shown in \cite{kraft} (1956), that there exists a prefix-free code with codeword lengths of a certain lengths sequence, if the Kraftsum of the lengths sequence is smaller than or equal to one. Furthermore they have shown, that the converse also holds for all (uniquely decipherable) codes.\footnote{In this survey a code means a set of words, such that any message which is encoded with these words can be uniquely decoded. Therefore we omit in future the "uniquely decipherable" and write only "code".} The question rises, if Kraft's and McMillan's result can be generalized to other types of codes? Throughout, we try to give an answer on this question for the class of fix-free codes. Since any code has Kraftsum smaller than or equal to one, this answers the question for the second implication of Kraft-McMillan's theorem. Therefore we pay attention mainly to the first implication.
Design of moveable and resizable graphics
Venue: arXiv cs.GR 2007
Year: 2007

We are communicating with computers on two different levels. On upper level we have a very flexible system of windows: we can move them, resize, overlap or put side by side. At any moment we decide what would be the best view and reorganize the whole view easily. Then we start any application, go to the inner level, and everything changes. Here we are stripped of all the flexibility and can work only inside the scenario, developed by the designer of the program. Interface will allow us to change some tiny details, but in general everything is fixed: graphics is neither moveable, nor resizable, and the same with controls. Author designed an extremely powerful mechanism of turning graphical objects and controls into moveable and resizable. This can not only significantly improve the existing applications, but this will bring the applications to another level. (To estimate the possible difference, try to imagine the Windows system without its flexibility and compare it with the current one.) This article explains in details the construction and use of moveable and resizable graphical objects.
A New Lower Bound on Guard Placement for Wireless Localization
Venue: arXiv cs.CG 2007
Year: 2007

The problem of wireless localization asks to place and orient stations in the plane, each of which broadcasts a unique key within a fixed angular range, so that each point in the plane can determine whether it is inside or outside a given polygonal region. The primary goal is to minimize the number of stations. In this paper we establish a lower bound of 2n/3 - 1 stations for polygons in general position, for the case in which the placement of stations is restricted to polygon vertices, improving upon the existing n/2 lower bound.
On Successive Refinement of Diversity for Fading ISI Channels
Venue: arXiv cs.IT 2007
Year: 2007

Rate and diversity impose a fundamental tradeoff in communications. This tradeoff was investigated for Intersymbol Interference (ISI) channels in [4]. A different point of view was explored in [1] where high-rate codes were designed so that they have a high-diversity code embedded within them. Such diversity embedded codes were investigated for flat fading channels and in this paper we explore its application to ISI channels. In particular, we investigate the rate tuples achievable for diversity embedded codes for scalar ISI channels through particular coding strategies. The main result of this paper is that the diversity multiplexing tradeoff for fading ISI channels is indeed successively refinable. This implies that for fading single input single output (SISO) ISI channels one can embed a high diversity code within a high rate code without any performance loss (asymptotically). This is related to a deterministic structural observation about the asymptotic behavior of frequency response of channel with respect to fading strength of time domain taps.
A Symphony Conducted by Brunet
Venue: arXiv cs.DC 2007
Year: 2007

We introduce BruNet, a general P2P software framework which we use to produce the first implementation of Symphony, a 1-D Kleinberg small-world architecture. Our framework is designed to easily implement and measure different P2P protocols over different transport layers such as TCP or UDP. This paper discusses our implementation of the Symphony network, which allows each node to keep $k \le \log N$ shortcut connections and to route to any other node with a short average delay of $O(\frac{1}{k}\log^2 N)$. %This provides a continuous trade-off between node degree and routing latency. We present experimental results taken from several PlanetLab deployments of size up to 1060 nodes. These succes sful deployments represent some of the largest PlanetLab deployments of P2P overlays found in the literature, and show our implementation's robustness to massive node dynamics in a WAN environment.
Mining for trees in a graph is NP-complete
Venue: arXiv cs.DB 2007
Year: 2007

Mining for trees in a graph is shown to be NP-complete.
On Outage Behavior of Wideband Slow-Fading Channels
Venue: arXiv cs.IT 2007
Year: 2007

This paper investigates point-to-point information transmission over a wideband slow-fading channel, modeled as an (asymptotically) large number of independent identically distributed parallel channels, with the random channel fading realizations remaining constant over the entire coding block. On the one hand, in the wideband limit the minimum achievable energy per nat required for reliable transmission, as a random variable, converges in probability to certain deterministic quantity. On the other hand, the exponential decay rate of the outage probability, termed as the wideband outage exponent, characterizes how the number of parallel channels, {\it i.e.}, the ``bandwidth'', should asymptotically scale in order to achieve a targeted outage probability at a targeted energy per nat. We examine two scenarios: when the transmitter has no channel state information and adopts uniform transmit power allocation among parallel channels; and when the transmitter is endowed with an one-bit channel state feedback for each parallel channel and accordingly allocates its transmit power. For both scenarios, we evaluate the wideband minimum energy per nat and the wideband outage exponent, and discuss their implication for system performance.
Systèmes interactifs sensibles aux émotions : architecture logicielle
Venue: arXiv cs.HC 2007
Year: 2007

We propose a software architecture for interactive systems which allows integrating the user's emotion. Emotion can be involved in interaction at several levels. In our application case - ballet dance - emotions is explicitely manipulated by the interactive system to produce emotion-wise output. Our architecture model to develop emotion-wise applications is based on the PAC-Amodeus model. We add a branch to this model, divided into three components: Data capture, analysis and cue extraction, and finally interpretation of those cues. We show the different data flows between this architecture's components depending on the entry point of the emotion branch within the system. We then illustrate our model by describing our application case: capturing a ballet dancer's movement to extract the emotions he expresses and use these emotions to generate graphical content that is displayed on stage.
Assistance orale à la recherche visuelle - étude expérimentale de l'apport d'indications spatiales à la détection de cibles
Venue: arXiv cs.HC 2007
Year: 2007

This paper describes an experimental study that aims at assessing the actual contribution of voice system messages to visual search efficiency and comfort. Messages which include spatial information on the target location are meant to support search for familiar targets in collections of photographs (30 per display). 24 participants carried out 240 visual search tasks in two conditions differing from each other in initial target presentation only. The isolated target was presented either simultaneously with an oral message (multimodal presentation, MP), or without any message (visual presentation, VP). Averaged target selection times were thrice longer and errors almost twice more frequent in the VP condition than in the MP condition. In addition, the contribution of spatial messages to visual search rapidity and accuracy was influenced by display layout and task difficulty. Most results are statistically significant. Besides, subjective judgments indicate that oral messages were well accepted.
Low-Density Parity-Check Codes for Nonergodic Block-Fading Channels
Venue: arXiv cs.IT 2007
Year: 2007

We solve the problem of designing powerful low-density parity-check (LDPC) codes with iterative decoding for the block-fading channel. We first study the case of maximum-likelihood decoding, and show that the design criterion is rather straightforward. Unfortunately, optimal constructions for maximum-likelihood decoding do not perform well under iterative decoding. To overcome this limitation, we then introduce a new family of full-diversity LDPC codes that exhibit near-outage-limit performance under iterative decoding for all block-lengths. This family competes with multiplexed parallel turbo codes suitable for nonergodic channels and recently reported in the literature.
Cognitive Medium Access: Exploration, Exploitation and Competition
Venue: arXiv cs.IT 2007
Year: 2007

This paper establishes the equivalence between cognitive medium access and the competitive multi-armed bandit problem. First, the scenario in which a single cognitive user wishes to opportunistically exploit the availability of empty frequency bands in the spectrum with multiple bands is considered. In this scenario, the availability probability of each channel is unknown to the cognitive user a priori. Hence efficient medium access strategies must strike a balance between exploring the availability of other free channels and exploiting the opportunities identified thus far. By adopting a Bayesian approach for this classical bandit problem, the optimal medium access strategy is derived and its underlying recursive structure is illustrated via examples. To avoid the prohibitive computational complexity of the optimal strategy, a low complexity asymptotically optimal strategy is developed. The proposed strategy does not require any prior statistical knowledge about the traffic pattern on the different channels. Next, the multi-cognitive user scenario is considered and low complexity medium access protocols, which strike the optimal balance between exploration and exploitation in such competitive environments, are developed. Finally, this formalism is extended to the case in which each cognitive user is capable of sensing and using multiple channels simultaneously.
Performance Comparison of Persistence Frameworks
Venue: arXiv cs.DB 2007
Year: 2007

One of the essential and most complex components in the software development process is the database. The complexity increases when the "orientation" of the interacting components differs. A persistence framework moves the program data in its most natural form to and from a permanent data store, the database. Thus a persistence framework manages the database and the mapping between the database and the objects. This paper compares the performance of two persistence frameworks ? Hibernate and iBatis?s SQLMaps using a banking database. The performance of both of these tools in single and multi-user environments are evaluated.
The structure and modeling results of the parallel spatial switching system
Venue: arXiv cs.NI 2007
Year: 2007

Problems of the switching parallel system designing provided spatial switching of packets from random time are discussed. Results of modeling of switching system as systems of mass service are resulted.
A Heuristic Routing Mechanism Using a New Addressing Scheme
Venue: arXiv cs.NI 2007
Year: 2007

Current methods of routing are based on network information in the form of routing tables, in which routing protocols determine how to update the tables according to the network changes. Despite the variability of data in routing tables, node addresses are constant. In this paper, we first introduce the new concept of variable addresses, which results in a novel framework to cope with routing problems using heuristic solutions. Then we propose a heuristic routing mechanism based on the application of genes for determination of network addresses in a variable address network and describe how this method flexibly solves different problems and induces new ideas in providing integral solutions for variety of problems. The case of ad-hoc networks is where simulation results are more supportive and original solutions have been proposed for issues like mobility.
Association Rules in the Relational Calculus
Venue: arXiv cs.DB 2007
Year: 2007

One of the most utilized data mining tasks is the search for association rules. Association rules represent significant relationships between items in transactions. We extend the concept of association rule to represent a much broader class of associations, which we refer to as \emph{entity-relationship rules.} Semantically, entity-relationship rules express associations between properties of related objects. Syntactically, these rules are based on a broad subclass of safe domain relational calculus queries. We propose a new definition of support and confidence for entity-relationship rules and for the frequency of entity-relationship queries. We prove that the definition of frequency satisfies standard probability axioms and the Apriori property.
Approximation algorithms and hardness for domination with propagation
Venue: arXiv cs.CC 2007
Year: 2007

The power dominating set (PDS) problem is the following extension of the well-known dominating set problem: find a smallest-size set of nodes $S$ that power dominates all the nodes, where a node $v$ is power dominated if (1) $v$ is in $S$ or $v$ has a neighbor in $S$, or (2) $v$ has a neighbor $w$ such that $w$ and all of its neighbors except $v$ are power dominated. We show a hardness of approximation threshold of $2^{\log^{1-ε}{n}}$ in contrast to the logarithmic hardness for the dominating set problem. We give an $O(\sqrt{n})$ approximation algorithm for planar graphs, and show that our methods cannot improve on this approximation guarantee. Finally, we initiate the study of PDS on directed graphs, and show the same hardness threshold of $2^{\log^{1-ε}{n}}$ for directed \emph{acyclic} graphs. Also we show that the directed PDS problem can be solved optimally in linear time if the underlying undirected graph has bounded tree-width.
Capacity of Linear Two-hop Mesh Networks with Rate Splitting, Decode-and-forward Relaying and Cooperation
Venue: arXiv cs.IT 2007
Year: 2007

A linear mesh network is considered in which a single user per cell communicates to a local base station via a dedicated relay (two-hop communication). Exploiting the possibly relevant inter-cell channel gains, rate splitting with successive cancellation in both hops is investigated as a promising solution to improve the rate of basic single-rate communications. Then, an alternative solution is proposed that attempts to improve the performance of the second hop (from the relays to base stations) by cooperative transmission among the relay stations. The cooperative scheme leverages the common information obtained by the relays as a by-product of the use of rate splitting in the first hop. Numerical results bring insight into the conditions (network topology and power constraints) under which rate splitting, with possible relay cooperation, is beneficial. Multi-cell processing (joint decoding at the base stations) is also considered for reference.
Cost and Effects of Pinning Control for Network Synchronization
Venue: arXiv cs.NI 2007
Year: 2007

In this paper, the problem of pinning control for synchronization of complex dynamical networks is discussed. A cost function of the controlled network is defined by the feedback gain and the coupling strength of the network. An interesting result is that lower cost is achieved by the control scheme of pinning nodes with smaller degrees. Some rigorous mathematical analysis is presented for achieving lower cost in the synchronization of different star-shaped networks. Numerical simulations on some non-regular complex networks generated by the Barabasi-Albert model and various star-shaped networks are shown for verification and illustration.
Generating models for temporal representations
Venue: arXiv cs.CL 2007
Year: 2007

We discuss the use of model building for temporal representations. We chose Polish to illustrate our discussion because it has an interesting aspectual system, but the points we wish to make are not language specific. Rather, our goal is to develop theoretical and computational tools for temporal model building tasks in computational semantics. To this end, we present a first-order theory of time and events which is rich enough to capture interesting semantic distinctions, and an algorithm which takes minimal models for first-order theories and systematically attempts to ``perturb'' their temporal component to provide non-minimal, but semantically significant, models.
Using Description Logics for Recognising Textual Entailment
Venue: arXiv cs.CL 2007
Year: 2007

The aim of this paper is to show how we can handle the Recognising Textual Entailment (RTE) task by using Description Logics (DLs). To do this, we propose a representation of natural language semantics in DLs inspired by existing representations in first-order logic. But our most significant contribution is the definition of two novel inference tasks: A-Box saturation and subgraph detection which are crucial for our approach to RTE.
Bloom maps
Venue: arXiv cs.DS 2007
Year: 2007

We consider the problem of succinctly encoding a static map to support approximate queries. We derive upper and lower bounds on the space requirements in terms of the error rate and the entropy of the distribution of values over keys: our bounds differ by a factor log e. For the upper bound we introduce a novel data structure, the Bloom map, generalising the Bloom filter to this problem. The lower bound follows from an information theoretic argument.
A Posteriori Equivalence: A New Perspective for Design of Optimal Channel Shortening Equalizers
Venue: arXiv cs.IT 2007
Year: 2007

The problem of channel shortening equalization for optimal detection in ISI channels is considered. The problem is to choose a linear equalizer and a partial response target filter such that the combination produces the best detection performance. Instead of using the traditional approach of MMSE equalization, we directly seek all equalizer and target pairs that yield optimal detection performance in terms of the sequence or symbol error rate. This leads to a new notion of a posteriori equivalence between the equalized and target channels with a simple characterization in terms of their underlying probability distributions. Using this characterization we show the surprising existence an infinite family of equalizer and target pairs for which any maximum a posteriori (MAP) based detector designed for the target channel is simultaneously MAP optimal for the equalized channel. For channels whose input symbols have equal energy, such as q-PSK, the MMSE equalizer designed with a monic target constraint yields a solution belonging to this optimal family of designs. Although, these designs produce IIR target filters, the ideas are extended to design good FIR targets. For an arbitrary choice of target and equalizer, we derive an expression for the probability of sequence detection error. This expression is used to design optimal FIR targets and IIR equalizers and to quantify the FIR approximation penalty.