arXiv
(422,153 recursos)
This is one of the most extensive subject based repositories in the world in the field of physics, mathematics, astronomy, computer sciences and quantitative biology. This is the principal site with almost 20 mirror versions around the globe. The site is supported by an extensive collection of information and background documentation. An RSS feed is available for anyone interested in keeping up-to-date with newly added materials.
Mostrando recursos 101 - 120 de 9,277
101.
Sequential File Programming Patterns and Performance with .NET - Kukol, Peter; Gray, Jim
Programming patterns for sequential file access in the .NET Framework are
described and the performance is measured. The default behavior provides
excellent performance on a single disk - 50 MBps both reading and writing.
Using large request sizes and doing file pre-allocation when possible have
quantifiable benefits. When one considers disk arrays, .NET unbuffered IO
delivers 800 MBps on a 16-disk array, but buffered IO delivers about 12% of
that performance. Consequently, high-performance file and database utilities
are still forced to use unbuffered IO for maximum sequential performance. The
report is accompanied by downloadable source code that demonstrates the
concepts and code that was used to obtain these measurements.
102.
Stability Analysis for Regularized Least Squares Regression - Rudin, Cynthia
We discuss stability for a class of learning algorithms with respect to noisy
labels. The algorithms we consider are for regression, and they involve the
minimization of regularized risk functionals, such as L(f) := 1/N sum_i
(f(x_i)-y_i)^2+ lambda ||f||_H^2. We shall call the algorithm `stable' if, when
y_i is a noisy version of f*(x_i) for some function f* in H, the output of the
algorithm converges to f* as the regularization term and noise simultaneously
vanish. We consider two flavors of this problem, one where a data set of N
points remains fixed, and the other where N -> infinity. For the case where N
-> infinity, we...
103.
Sub-structural Niching in Estimation of Distribution Algorithms - Sastry, K.; Abbass, H. A.; Goldberg, D. E.; Johnson, D. D.
We propose a sub-structural niching method that fully exploits the problem
decomposition capability of linkage-learning methods such as the estimation of
distribution algorithms and concentrate on maintaining diversity at the
sub-structural level. The proposed method consists of three key components: (1)
Problem decomposition and sub-structure identification, (2) sub-structure
fitness estimation, and (3) sub-structural niche preservation. The
sub-structural niching method is compared to restricted tournament selection
(RTS)--a niching method used in hierarchical Bayesian optimization
algorithm--with special emphasis on sustained preservation of multiple global
solutions of a class of boundedly-difficult, additively-separable multimodal
problems. The results show that sub-structural niching successfully maintains
multiple global optima over large number of generations and does so with
significantly...
104.
Idempotents, Mattson-Solomon Polynomials and Binary LDPC codes - Horan, R.; Tjhai, C.; Tomlinson, M.; Ambroze, M.; Ahmed, M.
We show how to construct an algorithm to search for binary idempotents which
may be used to construct binary LDPC codes. The algorithm, which allows control
of the key properties of sparseness, code rate and minimum distance, is
constructed in the Mattson-Solomon domain. Some of the new codes, found by
using this technique, are displayed.
105.
EPspectra: A Formal Toolkit for Developing DSP Software Applications - Kim, Hahnsang; Turletti, Theirry; Bouali, Amar
The software approach to developing Digital Signal Processing (DSP)
applications brings some great features such as flexibility, re-usability of
resources and easy upgrading of applications. However, it requires long and
tedious tests and verification phases because of the increasing complexity of
the software. This implies the need of a software programming environment
capable of putting together DSP modules and providing facilities to debug,
verify and validate the code. The objective of the work is to provide such
facilities as simulation and verification for developing DSP software
applications. This led us to develop an extension toolkit, Epspectra, built
upon Pspectra, one of the first toolkits available to design basic software
radio...
106.
Markets are Dead, Long Live Markets - Lai, Kevin
Researchers have long proposed using economic approaches to resource
allocation in computer systems. However, few of these proposals became
operational, let alone commercial. Questions persist about the economic
approach regarding its assumptions, value, applicability, and relevance to
system design. The goal of this paper is to answer these questions. We find
that market-based resource allocation is useful, and more importantly, that
mechanism design and system design should be integrated to produce systems that
are both economically and computationally efficient.
107.
Logic Column 11: The Finite and the Infinite in Temporal Logic - Pucella, Riccardo
This article examines the interpretation of the LTL temporal operators over
finite and infinite sequences. This is used as the basis for deriving a sound
and complete axiomatization for Caret, a recent temporal logic for reasoning
about programs with nested procedure calls and returns.
108.
On Dynamic Range Reporting in One Dimension - Mortensen, Christian Worm; Pagh, Rasmus; Patrascu, Mihai
We consider the problem of maintaining a dynamic set of integers and
answering queries of the form: report a point (equivalently, all points) in a
given interval. Range searching is a natural and fundamental variant of integer
search, and can be solved using predecessor search. However, for a RAM with
w-bit words, we show how to perform updates in O(lg w) time and answer queries
in O(lglg w) time. The update time is identical to the van Emde Boas structure,
but the query time is exponentially faster. Existing lower bounds show that
achieving our query time for predecessor search requires doubly-exponentially
slower updates. We present some arguments supporting...
109.
Pseudo-Codewords of Cycle Codes via Zeta Functions - Koetter, Ralf; Li, Wen-Ching W.; Vontobel, Pascal O.; Walker, Judy L.
Cycle codes are a special case of low-density parity-check (LDPC) codes and
as such can be decoded using an iterative message-passing decoding algorithm on
the associated Tanner graph. The existence of pseudo-codewords is known to
cause the decoding algorithm to fail in certain instances. In this paper, we
draw a connection between pseudo-codewords of cycle codes and the so-called
edge zeta function of the associated normal graph and show how the Newton
polyhedron of the zeta function equals the fundamental cone of the code, which
plays a crucial role in characterizing the performance of iterative decoding
algorithms.
110.
Improved Iterative Decoding for Perpendicular Magnetic Recording - Papagiannis, E.; Tjhai, C.; Ahmed, M.; Ambroze, M.; Tomlinson, M.
An algorithm of improving the performance of iterative decoding on
perpendicular magnetic recording is presented. This algorithm follows on the
authors' previous works on the parallel and serial concatenated turbo codes and
low-density parity-check codes. The application of this algorithm with
signal-to-noise ratio mismatch technique shows promising results in the
presence of media noise. We also show that, compare to the standard iterative
decoding algorithm, an improvement of within one order of magnitude can be
achieved.
111.
GF(2^m) Low-Density Parity-Check Codes Derived from Cyclotomic Cosets - Tjhai, C.; Tomlinson, M.; Horan, R.; Ambroze, M.; Ahmed, M.
Based on the ideas of cyclotomic cosets, idempotents and Mattson-Solomon
polynomials, we present a new method to construct GF(2^m), where m>0 cyclic
low-density parity-check codes. The construction method produces the dual code
idempotent which is used to define the parity-check matrix of the low-density
parity-check code. An interesting feature of this construction method is the
ability to increment the code dimension by adding more idempotents and so
steadily decrease the sparseness of the parity-check matrix. We show that the
constructed codes can achieve performance very close to the
sphere-packing-bound constrained for binary transmission.
112.
The Number of Spanning Trees in Kn-complements of Quasi-threshold Graphs - Nikolopoulos, Stavros D.; Papadopoulos, Charis
In this paper we examine the classes of graphs whose $K_n$-complements are
trees and quasi-threshold graphs and derive formulas for their number of
spanning trees; for a subgraph $H$ of $K_n$, the $K_n$-complement of $H$ is the
graph $K_n-H$ which is obtained from $K_n$ by removing the edges of $H$. Our
proofs are based on the complement spanning-tree matrix theorem, which
expresses the number of spanning trees of a graph as a function of the
determinant of a matrix that can be easily constructed from the adjacency
relation of the graph. Our results generalize previous results and extend the
family of graphs of the form $K_n-H$ admitting formulas...
113.
Generalised Bent Criteria for Boolean Functions (I) - Riera, Constanza; Parker, Matthew G.
Generalisations of the bent property of a boolean function are presented, by
proposing spectral analysis with respect to a well-chosen set of local unitary
transforms. Quadratic boolean functions are related to simple graphs and it is
shown that the orbit generated by successive Local Complementations on a graph
can be found within the transform spectra under investigation. The flat spectra
of a quadratic boolean function are related to modified versions of its
associated adjacency matrix.
114.
Generalised Bent Criteria for Boolean Functions (II) - Riera, Constanza; Petrides, George; Parker, Matthew G.
In the first part of this paper [16], some results on how to compute the flat
spectra of Boolean constructions w.r.t. the transforms {I,H}^n, {H,N}^n and
{I,H,N}^n were presented, and the relevance of Local Complementation to the
quadratic case was indicated. In this second part, the results are applied to
develop recursive formulae for the numbers of flat spectra of some structural
quadratics. Observations are made as to the generalised Bent properties of
boolean functions of algebraic degree greater than two, and the number of flat
spectra w.r.t. {I,H,N}^n are computed for some of them.
115.
Log Analysis Case Study Using LoGS - Mogilevsky, Dmitry
A very useful technique a network administrator can use to identify
problematic network behavior is careful analysis of logs of incoming and
outgoing network flows. The challenge one faces when attempting to undertake
this course of action, though, is that large networks tend to generate an
extremely large quantity of network traffic in a very short period of time,
resulting in very large traffic logs which must be analyzed post-generation
with an eye for contextual information which may reveal symptoms of problematic
traffic. A better technique is to perform real-time log analysis using a
real-time context-generating tool such as LoGS.
116.
Improved Tag Set Design and Multiplexing Algorithms for Universal Arrays - Mandoiu, Ion I.; Prajescu, Claudia; Trinca, Dragos
In this paper we address two optimization problems arising in the design of
genomic assays based on universal tag arrays. First, we address the universal
array tag set design problem. For this problem, we extend previous formulations
to incorporate antitag-to-antitag hybridization constraints in addition to
constraints on antitag-to-tag hybridization specificity, establish a
constructive upper bound on the maximum number of tags satisfying the extended
constraints, and propose a simple greedy tag selection algorithm. Second, we
give methods for improving the multiplexing rate in large-scale genomic assays
by combining primer selection with tag assignment. Experimental results on
simulated data show that this integrated optimization leads to reductions of up
to 50%...
117.
Co-Authorship Networks in the Digital Library Research Community - Liu, Xiaoming; Bollen, Johan; Nelson, Michael L.; Van de Sompel, Herbert
The field of digital libraries (DLs) coalesced in 1994: the first digital
library conferences were held that year, awareness of the World Wide Web was
accelerating, and the National Science Foundation awarded $24 Million (U.S.)
for the Digital Library Initiative (DLI). In this paper we examine the state of
the DL domain after a decade of activity by applying social network analysis to
the co-authorship network of the past ACM, IEEE, and joint ACM/IEEE digital
library conferences. We base our analysis on a common binary undirectional
network model to represent the co-authorship network, and from it we extract
several established network measures. We also introduce a weighted directional
network...
118.
The Complexity of Computing the Size of an Interval - Hemaspaandra, Lane A.; Homan, Christopher M.; Kosub, Sven; Wagner, Klaus W.
Given a p-order A over a universe of strings (i.e., a transitive, reflexive,
antisymmetric relation such that if (x, y) is an element of A then |x| is
polynomially bounded by |y|), an interval size function of A returns, for each
string x in the universe, the number of strings in the interval between strings
b(x) and t(x) (with respect to A), where b(x) and t(x) are functions that are
polynomial-time computable in the length of x.
By choosing sets of interval size functions based on feasibility requirements
for their underlying p-orders, we obtain new characterizations of complexity
classes. We prove that the set of all interval...
119.
A Geographic Directed Preferential Internet Topology Model - Bar, Sagy; Gonen, Mira; Wool, Avishai
The goal of this work is to model the peering arrangements between Autonomous
Systems (ASes). Most existing models of the AS-graph assume an undirected
graph. However, peering arrangements are mostly asymmetric Customer-Provider
arrangements, which are better modeled as directed edges. Furthermore, it is
well known that the AS-graph, and in particular its clustering structure, is
influenced by geography.
We introduce a new model that describes the AS-graph as a directed graph,
with an edge going from the customer to the provider, but also models symmetric
peer-to-peer arrangements, and takes geography into account. We are able to
mathematically analyze its power-law exponent and number of leaves. Beyond the
analysis we...
120.
Highly Scalable Algorithms for Robust String Barcoding - DasGupta, Bhaskar; Konwar, Kishori M.; Mandoiu, Ion I.; Shvartsman, Alex A.
String barcoding is a recently introduced technique for genomic-based
identification of microorganisms. In this paper we describe the engineering of
highly scalable algorithms for robust string barcoding. Our methods enable
distinguisher selection based on whole genomic sequences of hundreds of
microorganisms of up to bacterial size on a well-equipped workstation, and can
be easily parallelized to further extend the applicability range to thousands
of bacterial size genomes. Experimental results on both randomly generated and
NCBI genomic data show that whole-genome based selection results in a number of
distinguishers nearly matching the information theoretic lower bounds for the
problem.
101.
