OpenRaiser/Intern-Atlas huggingface dataset:
On the impact of TCP and per-flow scheduling on Internet performance (extended version)
Venue: arXiv cs.NI 2009
Year: 2009

Internet performance is tightly related to the properties of TCP and UDP protocols, jointly responsible for the delivery of the great majority of Internet traffic. It is well understood how these protocols behave under FIFO queuing and what the network congestion effects. However, no comprehensive analysis is available when flow-aware mechanisms such as per-flow scheduling and dropping policies are deployed. Previous simulation and experimental results leave a number of unanswered questions. In the paper, we tackle this issue by modeling via a set of fluid non-linear ODEs the instantaneous throughput and the buffer occupancy of N long-lived TCP sources under three per-flow scheduling disciplines (Fair Queuing, Longest Queue First, Shortest Queue First) and with longest queue drop buffer management. We study the system evolution and analytically characterize the stationary regime: closed-form expressions are derived for the stationary throughput/sending rate and buffer occupancy which give thorough understanding of short/long-term fairness for TCP traffic. Similarly, we provide the characterization of the loss rate experienced by UDP flows in presence of TCP traffic.
On Revenue Maximization in Second-Price Ad Auctions
Venue: arXiv cs.DS 2009
Year: 2009

Most recent papers addressing the algorithmic problem of allocating advertisement space for keywords in sponsored search auctions assume that pricing is done via a first-price auction, which does not realistically model the Generalized Second Price (GSP) auction used in practice. Towards the goal of more realistically modeling these auctions, we introduce the Second-Price Ad Auctions problem, in which bidders' payments are determined by the GSP mechanism. We show that the complexity of the Second-Price Ad Auctions problem is quite different than that of the more studied First-Price Ad Auctions problem. First, unlike the first-price variant, for which small constant-factor approximations are known, it is NP-hard to approximate the Second-Price Ad Auctions problem to any non-trivial factor. Second, this discrepancy extends even to the 0-1 special case that we call the Second-Price Matching problem (2PM). In particular, offline 2PM is APX-hard, and for online 2PM there is no deterministic algorithm achieving a non-trivial competitive ratio and no randomized algorithm achieving a competitive ratio better than 2. This stands in contrast to the results for the analogous special case in the first-price model, the standard bipartite matching problem, which is solvable in polynomial time and which has deterministic and randomized online algorithms achieving better competitive ratios. On the positive side, we provide a 2-approximation for offline 2PM and a 5.083-competitive randomized algorithm for online 2PM. The latter result makes use of a new generalization of a classic result on the performance of the "Ranking" algorithm for online bipartite matching.
An approach for the automated risk assessment of structural differences between spreadsheets (DiffXL)
Venue: arXiv cs.HC 2009
Year: 2009

This paper outlines an approach to manage and quantify the risks associated with changes made to spreadsheets. The methodology focuses on structural differences between spreadsheets and suggests a technique by which a risk analysis can be achieved in an automated environment. The paper offers an example that demonstrates how contiguous ranges of data can be mapped into a generic list of formulae, data and metadata. The example then shows that comparison of these generic lists can establish the structural differences between spreadsheets and quantify the level of risk that each change has introduced. Lastly the benefits, drawbacks and limitations of the technique are discussed in a commercial context.
Asymptotically Optimal Assignments In Ordinal Evaluations of Proposals
Venue: arXiv cs.DM 2009
Year: 2009

In ordinal evaluations of proposals in peer review systems, a set of proposals is assigned to a fixed set of referees so as to maximize the number of pairwise comparisons of proposals under certain referee capacity and proposal subject constraints. In this paper, the following two related problems are considered: (1) Assuming that each referee has a capacity to review k out of n proposals, 2 < k < n, determine the minimum number of referees needed to ensure that each pair of proposals is reviewed by at least one referee, (2) Find an assignment that meets the lower bound determined in (1). It is easy to see that one referee is both necessary and sufficient when k = n, and n(n-1)/2 referees are both necessary and sufficient when k = 2. We show that 6 referees are both necessary and sufficient when k = n/2. We further show that 11 referees are necessary and 12 are sufficient when k = n/3, and 18 referees are necessary and 20 referees are sufficient when k = n/4. A more general lower bound of n(n-1)/k(k-1) referees is also given for any k, 2 < k < n, and an assignment asymptotically matching this lower bound within a factor of 2 is presented. These results are not only theoretically interesting but they also provide practical methods for efficient assignments of proposals to referees.
The Function of Gesture in an Architectural Design Meeting
Venue: arXiv cs.HC 2009
Year: 2009

This text presents a cognitive-psychology analysis of spontaneous, co-speech gestures in a face-to-face architectural design meeting (A1 in DTRS7). The long-term objective is to formulate specifications for remote collaborative-design systems, especially for supporting the use of different semiotic modalities (multi-modal interaction). According to their function for design, interaction, and collaboration, we distinguish different gesture families: representational (entity designating or specifying), organisational (management of discourse, interaction, or functional design actions), focalising, discourse and interaction modulating, and disambiguating gestures. Discussion and conclusion concern the following points. It is impossible to attribute fixed functions to particular gesture forms. "Designating" gestures may also have a design function. The gestures identified in A1 possess a certain generic character. The gestures identified are neither systematically irreplaceable, nor optional accessories to speech or drawing. We discuss the possibilities for gesture in computer-supported collaborative software systems. The paper closes on our contribution to gesture studies and cognitive design research.
Algorithmic Aspects of Several Data Transfer Service Optimization Problems
Venue: arXiv cs.DS 2009
Year: 2009

Optimized data transfer services are highly demanded nowadays, due to the large amounts of data which are frequently being produced and accessed. In this paper we consider several data transfer service optimization problems (optimal server location in path networks, optimal packet sequencing and minimum makespan packet scheduling), for which we provide novel algorithmic solutions.
An Algorithmic Perspective on Some Network Design, Construction and Analysis Problems
Venue: arXiv cs.DS 2009
Year: 2009

Efficient network design, construction and analysis are important topics, considering the highly dynamic environment in which data communication occurs nowadays. In this paper we address several problems concerning these topics from an algorithmic point of view.
An Accurate Approximation to the Distribution of the Sum of Equally Correlated Nakagami-m Envelopes and its Application in Equal Gain Diversity Receivers
Venue: arXiv cs.IT 2009
Year: 2009

We present a novel and accurate approximation for the distribution of the sum of equally correlated Nakagami-m variates. Ascertaining on this result we study the performance of Equal Gain Combining (EGC) receivers, operating over equally correlating fading channels. Numerical results and simulations show the accuracy of the proposed approximation and the validity of the mathematical analysis.
Another Look at the Physics of Large Deviations With Application to Rate-Distortion Theory
Venue: arXiv cs.IT 2009
Year: 2009

We revisit and extend the physical interpretation recently given to a certain identity between large--deviations rate--functions (as well as applications of this identity to Information Theory), as an instance of thermal equilibrium between several physical systems that are brought into contact. Our new interpretation, of mechanical equilibrium between these systems, is shown to have several advantages relative to that of thermal equilibrium. This physical point of view also provides a trigger to the development of certain alternative representations of the rate--distortion function and channel capacity, which are new to the best knowledge of the author.
Lazy mixin modules and disciplined effects
Venue: arXiv cs.PL 2009
Year: 2009

Programming languages are expected to support programmer's effort to structure program code. The ML module system, object systems and mixins are good examples of language constructs promoting modular programming. Among the three, mixins can be thought of as a generalization of the two others in the sense that mixins can incorporate features of ML modules and objects with a set of primitive operators with clean semantics. Much work has been devoted to build mixin-based module systems for practical programming languages. In respect of the operational semantics, previous work notably investigated mixin calculi in call-by-name and call-by-value evaluation settings. In this paper we examine a mixin calculus in a call-by-need, or lazy, evaluation setting. We demonstrate how lazy mixins can be interesting in practice with a series of examples, and formalize the operational semantics by adapting Ancona and Zucca's concise formalization of call-by-name mixins. We then extend the semantics with constraints to control the evaluation order of components of mixins in several ways. The main motivation for considering the constraints is to produce side effects in a more explicit order than in a purely lazy, demand-driven setting. We explore the design space of possibly interesting constraints and consider two examples in detail.
Randomization for Security in Half-Duplex Two-Way Gaussian Channels
Venue: arXiv cs.IT 2009
Year: 2009

This paper develops a new physical layer framework for secure two-way wireless communication in the presence of a passive eavesdropper, i.e., Eve. Our approach achieves perfect information theoretic secrecy via a novel randomized scheduling and power allocation scheme. The key idea is to allow Alice and Bob to send symbols at random time instants. While Alice will be able to determine the symbols transmitted by Bob, Eve will suffer from ambiguity regarding the source of any particular symbol. This desirable ambiguity is enhanced, in our approach, by randomizing the transmit power level. Our theoretical analysis, in a 2-D geometry, reveals the ability of the proposed approach to achieve relatively high secure data rates under mild conditions on the spatial location of Eve. These theoretical claims are then validated by experimental results using IEEE 802.15.4-enabled sensor boards in different configurations, motivated by the spatial characteristics of Wireless Body Area Networks (WBAN).
Gabor wavelet analysis and the fractional Hilbert transform
Venue: arXiv cs.IT 2009
Year: 2009

We propose an amplitude-phase representation of the dual-tree complex wavelet transform (DT-CWT) which provides an intuitive interpretation of the associated complex wavelet coefficients. The representation, in particular, is based on the shifting action of the group of fractional Hilbert transforms (fHT) which allow us to extend the notion of arbitrary phase-shifts beyond pure sinusoids. We explicitly characterize this shifting action for a particular family of Gabor-like wavelets which, in effect, links the corresponding dual-tree transform with the framework of windowed-Fourier analysis. We then extend these ideas to the bivariate DT-CWT based on certain directional extensions of the fHT. In particular, we derive a signal representation involving the superposition of direction-selective wavelets affected with appropriate phase-shifts.
The Structure of First-Order Causality
Venue: arXiv cs.LO 2009
Year: 2009

Game semantics describe the interactive behavior of proofs by interpreting formulas as games on which proofs induce strategies. Such a semantics is introduced here for capturing dependencies induced by quantifications in first-order propositional logic. One of the main difficulties that has to be faced during the elaboration of this kind of semantics is to characterize definable strategies, that is strategies which actually behave like a proof. This is usually done by restricting the model to strategies satisfying subtle combinatorial conditions, whose preservation under composition is often difficult to show. Here, we present an original methodology to achieve this task, which requires to combine advanced tools from game semantics, rewriting theory and categorical algebra. We introduce a diagrammatic presentation of the monoidal category of definable strategies of our model, by the means of generators and relations: those strategies can be generated from a finite set of atomic strategies and the equality between strategies admits a finite axiomatization, this equational structure corresponding to a polarized variation of the notion of bialgebra. This work thus bridges algebra and denotational semantics in order to reveal the structure of dependencies induced by first-order quantifiers, and lays the foundations for a mechanized analysis of causality in programming languages.
jYang : A YANG parser in java
Venue: arXiv cs.PL 2009
Year: 2009

The NETCONF configuration protocol of the IETF Network Work- ing Group provides mechanisms to manipulate the configuration of network devices. YANG is the language currently under consideration within the IETF to specify the data models to be used in NETCONF . This report describes the design and development of a syntax and semantics parser for YANG in java.
Multiple Retrieval Models and Regression Models for Prior Art Search
Venue: arXiv cs.CL 2009
Year: 2009

This paper presents the system called PATATRAS (PATent and Article Tracking, Retrieval and AnalysiS) realized for the IP track of CLEF 2009. Our approach presents three main characteristics: 1. The usage of multiple retrieval models (KL, Okapi) and term index definitions (lemma, phrase, concept) for the three languages considered in the present track (English, French, German) producing ten different sets of ranked results. 2. The merging of the different results based on multiple regression models using an additional validation set created from the patent collection. 3. The exploitation of patent metadata and of the citation structures for creating restricted initial working sets of patents and for producing a final re-ranking regression model. As we exploit specific metadata of the patent documents and the citation relations only at the creation of initial working sets and during the final post ranking step, our architecture remains generic and easy to extend.
Mesh Algorithms for PDE with Sieve I: Mesh Distribution
Venue: arXiv cs.CE 2009
Year: 2009

We have developed a new programming framework, called Sieve, to support parallel numerical PDE algorithms operating over distributed meshes. We have also developed a reference implementation of Sieve in C++ as a library of generic algorithms operating on distributed containers conforming to the Sieve interface. Sieve makes instances of the incidence relation, or \emph{arrows}, the conceptual first-class objects represented in the containers. Further, generic algorithms acting on this arrow container are systematically used to provide natural geometric operations on the topology and also, through duality, on the data. Finally, coverings and duality are used to encode not only individual meshes, but all types of hierarchies underlying PDE data structures, including multigrid and mesh partitions. In order to demonstrate the usefulness of the framework, we show how the mesh partition data can be represented and manipulated using the same fundamental mechanisms used to represent meshes. We present the complete description of an algorithm to encode a mesh partition and then distribute a mesh, which is independent of the mesh dimension, element shape, or embedding. Moreover, data associated with the mesh can be similarly distributed with exactly the same algorithm. The use of a high level of abstraction within the Sieve leads to several benefits in terms of code reuse, simplicity, and extensibility. We discuss these benefits and compare our approach to other existing mesh libraries.
An OLAC Extension for Dravidian Languages
Venue: arXiv cs.CL 2009
Year: 2009

OLAC was founded in 2000 for creating online databases of language resources. This paper intends to review the bottom-up distributed character of the project and proposes an extension of the architecture for Dravidian languages. An ontological structure is considered for effective natural language processing (NLP) and its advantages over statistical methods are reviewed
Energy Efficient Location Aided Routing Protocol for Wireless MANETs
Venue: arXiv cs.NI 2009
Year: 2009

A Mobile Ad-Hoc Network (MANET) is a collection of wireless mobile nodes forming a temporary network without using any centralized access point, infrastructure, or centralized administration. In this paper we introduce an Energy Efficient Location Aided Routing (EELAR) Protocol for MANETs that is based on the Location Aided Routing (LAR). EELAR makes significant reduction in the energy consumption of the mobile nodes batteries by limiting the area of discovering a new route to a smaller zone. Thus, control packets overhead is significantly reduced. In EELAR a reference wireless base station is used and the network's circular area centered at the base station is divided into six equal sub-areas. At route discovery instead of flooding control packets to the whole network area, they are flooded to only the sub-area of the destination mobile node. The base station stores locations of the mobile nodes in a position table. To show the efficiency of the proposed protocol we present simulations using NS-2. Simulation results show that EELAR protocol makes an improvement in control packet overhead and delivery ratio compared to AODV, LAR, and DSR protocols.
Dynamic Multimedia Content Retrieval System in Distributed Environment
Venue: arXiv cs.MM 2009
Year: 2009

WiCoM enables remote management of web resources. Our application Mobile reporter is aimed at Journalist, who will be able to capture the events in real-time using their mobile phones and update their web server on the latest event. WiCoM has been developed using J2ME technology on the client side and PHP on the server side. The communication between the client and the server is established through GPRS. Mobile reporter will be able to upload, edit and remove both textual as well as multimedia contents in the server.
Normal Elliptic Bases and Torus-Based Cryptography
Venue: arXiv cs.CR 2009
Year: 2009

We consider representations of algebraic tori $T_n(F_q)$ over finite fields. We make use of normal elliptic bases to show that, for infinitely many squarefree integers $n$ and infinitely many values of $q$, we can encode $m$ torus elements, to a small fixed overhead and to $m$ $ϕ(n)$-tuples of $F_q$ elements, in quasi-linear time in $\log q$. This improves upon previously known algorithms, which all have a quasi-quadratic complexity. As a result, the cost of the encoding phase is now negligible in Diffie-Hellman cryptographic schemes.
An Enhanced Static Data Compression Scheme Of Bengali Short Message
Venue: arXiv cs.IT 2009
Year: 2009

This paper concerns a modified approach of compressing Short Bengali Text Message for small devices. The prime objective of this research technique is to establish a low complexity compression scheme suitable for small devices having small memory and relatively lower processing speed. The basic aim is not to compress text of any size up to its maximum level without having any constraint on space and time, rather than the main target is to compress short messages up to an optimal level which needs minimum space, consume less time and the processor requirement is lower. We have implemented Character Masking, Dictionary Matching, Associative rule of data mining and Hyphenation algorithm for syllable based compression in hierarchical steps to achieve low complexity lossless compression of text message for any mobile devices. The scheme to choose the diagrams are performed on the basis of extensive statistical model and the static Huffman coding is done through the same context.
Scale-Based Gaussian Coverings: Combining Intra and Inter Mixture Models in Image Segmentation
Venue: arXiv cs.CV 2009
Year: 2009

By a "covering" we mean a Gaussian mixture model fit to observed data. Approximations of the Bayes factor can be availed of to judge model fit to the data within a given Gaussian mixture model. Between families of Gaussian mixture models, we propose the Rényi quadratic entropy as an excellent and tractable model comparison framework. We exemplify this using the segmentation of an MRI image volume, based (1) on a direct Gaussian mixture model applied to the marginal distribution function, and (2) Gaussian model fit through k-means applied to the 4D multivalued image volume furnished by the wavelet transform. Visual preference for one model over another is not immediate. The Rényi quadratic entropy allows us to show clearly that one of these modelings is superior to the other.
On the Set Multi-Cover Problem in Geometric Settings
Venue: arXiv cs.CG 2009
Year: 2009

We consider the set multi-cover problem in geometric settings. Given a set of points P and a collection of geometric shapes (or sets) F, we wish to find a minimum cardinality subset of F such that each point p in P is covered by (contained in) at least d(p) sets. Here d(p) is an integer demand (requirement) for p. When the demands d(p)=1 for all p, this is the standard set cover problem. The set cover problem in geometric settings admits an approximation ratio that is better than that for the general version. In this paper, we show that similar improvements can be obtained for the multi-cover problem as well. In particular, we obtain an O(log Opt) approximation for set systems of bounded VC-dimension, where Opt is the cardinality of an optimal solution, and an O(1) approximation for covering points by half-spaces in three dimensions and for some other classes of shapes.