OpenRaiser/Intern-Atlas huggingface dataset:
Graphic processors to speed-up simulations for the design of high performance solar receptors
Venue: arXiv cs.DC 2007
Year: 2007

Graphics Processing Units (GPUs) are now powerful and flexible systems adapted and used for other purposes than graphics calculations (General Purpose computation on GPU -- GPGPU). We present here a prototype to be integrated into simulation codes that estimate temperature, velocity and pressure to design next generations of solar receptors. Such codes will delegate to our contribution on GPUs the computation of heat transfers due to radiations. We use Monte-Carlo line-by-line ray-tracing through finite volumes. This means data-parallel arithmetic transformations on large data structures. Our prototype is inspired on the source code of GPUBench. Our performances on two recent graphics cards (Nvidia 7800GTX and ATI RX1800XL) show some speed-up higher than 400 compared to CPU implementations leaving most of CPU computing resources available. As there were some questions pending about the accuracy of the operators implemented in GPUs, we start this report with a survey and some contributed tests on the various floating point units available on GPUs.
An Efficient Local Approach to Convexity Testing of Piecewise-Linear Hypersurfaces
Venue: arXiv cs.CG 2007
Year: 2007

We show that a closed piecewise-linear hypersurface immersed in $R^n$ ($n\ge 3$) is the boundary of a convex body if and only if every point in the interior of each $(n-3)$-face has a neighborhood that lies on the boundary of some convex body; no assumptions about the hypersurface's topology are needed. We derive this criterion from our generalization of Van Heijenoort's (1952) theorem on locally convex hypersurfaces in $R^n$ to spherical spaces. We also give an easy-to-implement convexity testing algorithm, which is based on our criterion. For $R^3$ the number of arithmetic operations used by the algorithm is at most linear in the number of vertices, while in general it is at most linear in the number of incidences between the $(n-2)$-faces and $(n-3)$-faces. When the dimension $n$ is not fixed and only ring arithmetic is allowed, the algorithm still remains polynomial. Our method works in more general situations than the convexity verification algorithms developed by Mehlhorn et al. (1996) and Devillers et al. (1998) -- for example, our method does not require the input surface to be orientable, nor it requires the input data to include normal vectors to the facets that are oriented "in a coherent way". For $R^3$ the complexity of our algorithm is the same as that of previous algorithms; for higher dimensions there seems to be no clear winner, but our approach is the only one that easily handles inputs in which the facet normals are not known to be coherently oriented or are not given at all. Furthermore, our method can be extended to piecewise-polynomial surfaces of small degree.
Constructing Optimal Highways
Venue: arXiv cs.CG 2007
Year: 2007

For two points $p$ and $q$ in the plane, a straight line $h$, called a highway, and a real $v>1$, we define the \emph{travel time} (also known as the \emph{city distance}) from $p$ and $q$ to be the time needed to traverse a quickest path from $p$ to $q$, where the distance is measured with speed $v$ on $h$ and with speed 1 in the underlying metric elsewhere. Given a set $S$ of $n$ points in the plane and a highway speed $v$, we consider the problem of finding a \emph{highway} that minimizes the maximum travel time over all pairs of points in $S$. If the orientation of the highway is fixed, the optimal highway can be computed in linear time, both for the $L_1$- and the Euclidean metric as the underlying metric. If arbitrary orientations are allowed, then the optimal highway can be computed in $O(n^{2} \log n)$ time. We also consider the problem of computing an optimal pair of highways, one being horizontal, one vertical.
A Comparison of On-Line Computer Science Citation Databases
Venue: arXiv cs.DL 2007
Year: 2007

This paper examines the difference and similarities between the two on-line computer science citation databases DBLP and CiteSeer. The database entries in DBLP are inserted manually while the CiteSeer entries are obtained autonomously via a crawl of the Web and automatic processing of user submissions. CiteSeer's autonomous citation database can be considered a form of self-selected on-line survey. It is important to understand the limitations of such databases, particularly when citation information is used to assess the performance of authors, institutions and funding bodies. We show that the CiteSeer database contains considerably fewer single author papers. This bias can be modeled by an exponential process with intuitive explanation. The model permits us to predict that the DBLP database covers approximately 24% of the entire literature of Computer Science. CiteSeer is also biased against low-cited papers. Despite their difference, both databases exhibit similar and significantly different citation distributions compared with previous analysis of the Physics community. In both databases, we also observe that the number of authors per paper has been increasing over time.
BrlAPI: Simple, Portable, Concurrent, Application-level Control of Braille Terminals
Venue: arXiv cs.HC 2007
Year: 2007

Screen readers can drive braille devices for allowing visually impaired users to access computer environments, by providing them the same information as sighted users. But in some cases, this view is not easy to use on a braille device. In such cases, it would be much more useful to let applications provide their own braille feedback, specially adapted to visually impaired users. Such applications would then need the ability to output braille ; however, allowing both screen readers and applications access a wide panel of braille devices is not a trivial task. We present an abstraction layer that applications may use to communicate with braille devices. They do not need to deal with the specificities of each device, but can do so if necessary. We show how several applications can communicate with one braille device concurrently, with BrlAPI making sensible choices about which application eventually gets access to the device. The description of a widely used implementation of BrlAPI is included.
Linear time algorithms for Clobber
Venue: arXiv cs.GT 2007
Year: 2007

We prove that the single-player game clobber is solvable in linear time when played on a line or on a cycle. For this purpose, we show that this game is equivalent to an optimization problem on a set of words defined by seven classes of forbidden patterns. We also prove that, playing on the cycle, it is always possible to remove at least 2n/3 pawns, and we give a conformation for which it is not possible to do better, answering questions recently asked by Faria et al.
Bandit Algorithms for Tree Search
Venue: arXiv cs.LG 2007
Year: 2007

Bandit based methods for tree search have recently gained popularity when applied to huge trees, e.g. in the game of go (Gelly et al., 2006). The UCT algorithm (Kocsis and Szepesvari, 2006), a tree search method based on Upper Confidence Bounds (UCB) (Auer et al., 2002), is believed to adapt locally to the effective smoothness of the tree. However, we show that UCT is too ``optimistic'' in some cases, leading to a regret O(exp(exp(D))) where D is the depth of the tree. We propose alternative bandit algorithms for tree search. First, a modification of UCT using a confidence sequence that scales exponentially with the horizon depth is proven to have a regret O(2^D \sqrt{n}), but does not adapt to possible smoothness in the tree. We then analyze Flat-UCB performed on the leaves and provide a finite regret bound with high probability. Then, we introduce a UCB-based Bandit Algorithm for Smooth Trees which takes into account actual smoothness of the rewards for performing efficient ``cuts'' of sub-optimal branches with high confidence. Finally, we present an incremental tree search version which applies when the full tree is too big (possibly infinite) to be entirely represented and show that with high probability, essentially only the optimal branches is indefinitely developed. We illustrate these methods on a global optimization problem of a Lipschitz function, given noisy data.
Discriminating and Identifying Codes in the Binary Hamming Space
Venue: arXiv cs.DM 2007
Year: 2007

Let $F^n$ be the binary $n$-cube, or binary Hamming space of dimension $n$, endowed with the Hamming distance, and ${\cal E}^n$ (respectively, ${\cal O}^n$) the set of vectors with even (respectively, odd) weight. For $r\geq 1$ and $x\in F^n$, we denote by $B_r(x)$ the ball of radius $r$ and centre $x$. A code $C\subseteq F^n$ is said to be $r$-identifying if the sets $B_r(x) \cap C$, $x\in F^n$, are all nonempty and distinct. A code $C\subseteq {\cal E}^n$ is said to be $r$-discriminating if the sets $B_r(x) \cap C$, $x\in {\cal O}^n$, are all nonempty and distinct. We show that the two definitions, which were given for general graphs, are equivalent in the case of the Hamming space, in the following sense: for any odd $r$, there is a bijection between the set of $r$-identifying codes in $F^n$ and the set of $r$-discriminating codes in $F^{n+1}$. We then extend previous studies on constructive upper bounds for the minimum cardinalities of identifying codes in the Hamming space.
Flexible Audio Streams
Venue: arXiv cs.HC 2007
Year: 2007

Tremendous research effort was invested in audio browsers and machine learning techniques to decode the structure of Web pages in order to put them into an audio format. In this paper, we address a simpler and efficient solution for the creation of an audio browser of VOICEXML generated from RSS/Atom stream feeds. We developed a multimodal (audio and graphical) portal application that offers RSS/Atom feeds. By utilizing sing our system, the user can interact using voice or graphic commands, listen and watch digital content, such as news, blogs feeds, podcasts, and even access email and personal schedules. The portal system permits the use of security credentials (user/password authentication) to collect secure RSS/Atom stream in the multimodal browser to connect the user to specific personal services. A series experiments have been conducted to evaluate the performance of the RSS reader and navigator. Our system is extremely beneficial for a wide range of applications, from interfaces for the visual impaired users to browsers for mobile telephonic interfaces.
Field-Sensitive Value Analysis of Embedded C Programs with Union Types and Pointer Arithmetics
Venue: arXiv cs.PL 2007
Year: 2007

We propose a memory abstraction able to lift existing numerical static analyses to C programs containing union types, pointer casts, and arbitrary pointer arithmetics. Our framework is that of a combined points-to and data-value analysis. We abstract the contents of compound variables in a field-sensitive way, whether these fields contain numeric or pointer values, and use stock numerical abstract domains to find an overapproximation of all possible memory states--with the ability to discover relationships between variables. A main novelty of our approach is the dynamic mapping scheme we use to associate a flat collection of abstract cells of scalar type to the set of accessed memory locations, while taking care of byte-level aliases - i.e., C variables with incompatible types allocated in overlapping memory locations. We do not rely on static type information which can be misleading in C programs as it does not account for all the uses a memory zone may be put to. Our work was incorporated within the Astrée static analyzer that checks for the absence of run-time-errors in embedded, safety-critical, numerical-intensive software. It replaces the former memory domain limited to well-typed, union-free, pointer-cast free data-structures. Early results demonstrate that this abstraction allows analyzing a larger class of C programs, without much cost overhead.
Relational Abstract Domains for the Detection of Floating-Point Run-Time Errors
Venue: arXiv cs.PL 2007
Year: 2007

We present a new idea to adapt relational abstract domains to the analysis of IEEE 754-compliant floating-point numbers in order to statically detect, through abstract Interpretation-based static analyses, potential floating-point run-time exceptions such as overflows or invalid operations. In order to take the non-linearity of rounding into account, expressions are modeled as linear forms with interval coefficients. We show how to extend already existing numerical abstract domains, such as the octagon abstract domain, to efficiently abstract transfer functions based on interval linear forms. We discuss specific fixpoint stabilization techniques and give some experimental results.
A Systematic Approach to Web-Application Development
Venue: arXiv cs.SE 2007
Year: 2007

Designing a web-application from a specification involves a series of well-planned and well executed steps leading to the final product. This often involves critical changes in design while testing the application, which itself is slow and cumbersome. Traditional approaches either fully automate the web-application development process, or let developers write everything from scratch. Our approach is based on a middle-ground, with precise control on the workflow and usage of a set of custom-made software tools to automate a significant part of code generation.
Randomized Computations on Large Data Sets: Tight Lower Bounds
Venue: arXiv cs.DB 2007
Year: 2007

We study the randomized version of a computation model (introduced by Grohe, Koch, and Schweikardt (ICALP'05); Grohe and Schweikardt (PODS'05)) that restricts random access to external memory and internal memory space. Essentially, this model can be viewed as a powerful version of a data stream model that puts no cost on sequential scans of external memory (as other models for data streams) and, in addition, (like other external memory models, but unlike streaming models), admits several large external memory devices that can be read and written to in parallel. We obtain tight lower bounds for the decision problems set equality, multiset equality, and checksort. More precisely, we show that any randomized one-sided-error bounded Monte Carlo algorithm for these problems must perform Omega(log N) random accesses to external memory devices, provided that the internal memory size is at most O(N^(1/4)/log N), where N denotes the size of the input data. From the lower bound on the set equality problem we can infer lower bounds on the worst case data complexity of query evaluation for the languages XQuery, XPath, and relational algebra on streaming data. More precisely, we show that there exist queries in XQuery, XPath, and relational algebra, such that any (randomized) Las Vegas algorithm that evaluates these queries must perform Omega(log N) random accesses to external memory devices, provided that the internal memory size is at most O(N^(1/4)/log N).
Characterization of Search Engine Caches
Venue: arXiv cs.DL 2007
Year: 2007

Search engines provide cached copies of indexed content so users will have something to "click on" if the remote resource is temporarily or permanently unavailable. Depending on their proprietary caching strategies, search engines will purge their indexes and caches of resources that exceed a threshold of unavailability. Although search engine caches are provided only as an aid to the interactive user, we are interested in building reliable preservation services from the aggregate of these limited caching services. But first, we must understand the contents of search engine caches. In this paper, we have examined the cached contents of Ask, Google, MSN and Yahoo to profile such things as overlap between index and cache, size, MIME type and "staleness" of the cached resources. We also examined the overlap of the various caches with the holdings of the Internet Archive.
Encoding via Gröbner bases and discrete Fourier transforms for several types of algebraic codes
Venue: arXiv cs.IT 2007
Year: 2007

We propose a novel encoding scheme for algebraic codes such as codes on algebraic curves, multidimensional cyclic codes, and hyperbolic cascaded Reed-Solomon codes and present numerical examples. We employ the recurrence from the Gröbner basis of the locator ideal for a set of rational points and the two-dimensional inverse discrete Fourier transform. We generalize the functioning of the generator polynomial for Reed-Solomon codes and develop systematic encoding for various algebraic codes.
User-level DSM System for Modern High-Performance Interconnection Networks
Venue: arXiv cs.DC 2007
Year: 2007

In this paper, we introduce a new user-level DSM system which has the ability to directly interact with underlying interconnection networks. The DSM system provides the application programmer a flexible API to program parallel applications either using shared memory semantics over physically distributed memory or to use an efficient remote memory demand paging technique. We also introduce a new time slice based memory consistency protocol which is used by the DSM system. We present preliminary results from our implementation on a small Opteron Linux cluster interconnected over Myrinet.
Automatic Selection of Bitmap Join Indexes in Data Warehouses
Venue: arXiv cs.DB 2007
Year: 2007

The queries defined on data warehouses are complex and use several join operations that induce an expensive computational cost. This cost becomes even more prohibitive when queries access very large volumes of data. To improve response time, data warehouse administrators generally use indexing techniques such as star join indexes or bitmap join indexes. This task is nevertheless complex and fastidious. Our solution lies in the field of data warehouse auto-administration. In this framework, we propose an automatic index selection strategy. We exploit a data mining technique ; more precisely frequent itemset mining, in order to determine a set of candidate indexes from a given workload. Then, we propose several cost models allowing to create an index configuration composed by the indexes providing the best profit. These models evaluate the cost of accessing data using bitmap join indexes, and the cost of updating and storing these indexes.
Intrinsic dimension of a dataset: what properties does one expect?
Venue: arXiv cs.LG 2007
Year: 2007

We propose an axiomatic approach to the concept of an intrinsic dimension of a dataset, based on a viewpoint of geometry of high-dimensional structures. Our first axiom postulates that high values of dimension be indicative of the presence of the curse of dimensionality (in a certain precise mathematical sense). The second axiom requires the dimension to depend smoothly on a distance between datasets (so that the dimension of a dataset and that of an approximating principal manifold would be close to each other). The third axiom is a normalization condition: the dimension of the Euclidean $n$-sphere $\s^n$ is $Θ(n)$. We give an example of a dimension function satisfying our axioms, even though it is in general computationally unfeasible, and discuss a computationally cheap function satisfying most but not all of our axioms (the ``intrinsic dimensionality'' of Chávez et al.)
Isochronous Data Transmission With Rates Close to Channel Capacity
Venue: arXiv cs.IT 2007
Year: 2007

The existing ARQ schemes (including a hybrid ARQ) have a throughput depending on packet error probability. In this paper we describe a strategy for delay tolerant applications which provide a constant throughput until the algorithm robustness criterion is not failed. The algorithm robustness criterion is applied to find the optimum size of the retransmission block in the assumption of the small changes of coding rate within the rate compatible codes family.
Open Access Scientometrics and the UK Research Assessment Exercise
Venue: arXiv cs.IR 2007
Year: 2007

Scientometric predictors of research performance need to be validated by showing that they have a high correlation with the external criterion they are trying to predict. The UK Research Assessment Exercise (RAE), together with the growing movement toward making the full-texts of research articles freely available on the web -- offer a unique opportunity to test and validate a wealth of old and new scientometric predictors, through multiple regression analysis: Publications, journal impact factors, citations, co-citations, citation chronometrics (age, growth, latency to peak, decay rate), hub/authority scores, h-index, prior funding, student counts, co-authorship scores, endogamy/exogamy, textual proximity, download/co-downloads and their chronometrics, etc. can all be tested and validated jointly, discipline by discipline, against their RAE panel rankings in the forthcoming parallel panel-based and metric RAE in 2008. The weights of each predictor can be calibrated to maximize the joint correlation with the rankings. Open Access Scientometrics will provide powerful new means of navigating, evaluating, predicting and analyzing the growing Open Access database, as well as powerful incentives for making it grow faster. ~
Structure induction by lossless graph compression
Venue: arXiv cs.DS 2007
Year: 2007

This work is motivated by the necessity to automate the discovery of structure in vast and evergrowing collection of relational data commonly represented as graphs, for example genomic networks. A novel algorithm, dubbed Graphitour, for structure induction by lossless graph compression is presented and illustrated by a clear and broadly known case of nested structure in a DNA molecule. This work extends to graphs some well established approaches to grammatical inference previously applied only to strings. The bottom-up graph compression problem is related to the maximum cardinality (non-bipartite) maximum cardinality matching problem. The algorithm accepts a variety of graph types including directed graphs and graphs with labeled nodes and arcs. The resulting structure could be used for representation and classification of graphs.
A Hot Channel
Venue: arXiv cs.IT 2007
Year: 2007

This paper studies on-chip communication with non-ideal heat sinks. A channel model is proposed where the variance of the additive noise depends on the weighted sum of the past channel input powers. It is shown that, depending on the weights, the capacity can be either bounded or unbounded in the input power. A necessary condition and a sufficient condition for the capacity to be bounded are presented.
Unicast and Multicast Qos Routing with Soft Constraint Logic Programming
Venue: arXiv cs.LO 2008
Year: 2008

We present a formal model to represent and solve the unicast/multicast routing problem in networks with Quality of Service (QoS) requirements. To attain this, first we translate the network adapting it to a weighted graph (unicast) or and-or graph (multicast), where the weight on a connector corresponds to the multidimensional cost of sending a packet on the related network link: each component of the weights vector represents a different QoS metric value (e.g. bandwidth, cost, delay, packet loss). The second step consists in writing this graph as a program in Soft Constraint Logic Programming (SCLP): the engine of this framework is then able to find the best paths/trees by optimizing their costs and solving the constraints imposed on them (e.g. delay < 40msec), thus finding a solution to QoS routing problems. Moreover, c-semiring structures are a convenient tool to model QoS metrics. At last, we provide an implementation of the framework over scale-free networks and we suggest how the performance can be improved.