OpenRaiser/Intern-Atlas huggingface dataset:
Multirobot rendezvous with visibility sensors in nonconvex environments
Venue: arXiv cs.RO 2006
Year: 2006

This paper presents a coordination algorithm for mobile autonomous robots. Relying upon distributed sensing the robots achieve rendezvous, that is, they move to a common location. Each robot is a point mass moving in a nonconvex environment according to an omnidirectional kinematic model. Each robot is equipped with line-of-sight limited-range sensors, i.e., a robot can measure the relative position of any object (robots or environment boundary) if and only if the object is within a given distance and there are no obstacles in-between. The algorithm is designed using the notions of robust visibility, connectivity-preserving constraint sets, and proximity graphs. Simulations illustrate the theoretical results on the correctness of the proposed algorithm, and its performance in asynchronous setups and with sensor measurement and control errors.
A Logical Approach to Efficient Max-SAT solving
Venue: arXiv cs.AI 2006
Year: 2006

Weighted Max-SAT is the optimization version of SAT and many important problems can be naturally encoded as such. Solving weighted Max-SAT is an important problem from both a theoretical and a practical point of view. In recent years, there has been considerable interest in finding efficient solving techniques. Most of this work focus on the computation of good quality lower bounds to be used within a branch and bound DPLL-like algorithm. Most often, these lower bounds are described in a procedural way. Because of that, it is difficult to realize the {\em logic} that is behind. In this paper we introduce an original framework for Max-SAT that stresses the parallelism with classical SAT. Then, we extend the two basic SAT solving techniques: {\em search} and {\em inference}. We show that many algorithmic {\em tricks} used in state-of-the-art Max-SAT solvers are easily expressable in {\em logic} terms with our framework in a unified manner. Besides, we introduce an original search algorithm that performs a restricted amount of {\em weighted resolution} at each visited node. We empirically compare our algorithm with a variety of solving alternatives on several benchmarks. Our experiments, which constitute to the best of our knowledge the most comprehensive Max-sat evaluation ever reported, show that our algorithm is generally orders of magnitude faster than any competitor.
Intra-site Level Cultural Heritage Documentation: Combination of Survey, Modeling and Imagery Data in a Web Information System
Venue: arXiv cs.DL 2006
Year: 2006

Cultural heritage documentation induces the use of computerized techniques to manage and preserve the information produced. Geographical information systems have proved their potentialities in this scope, but they are not always adapted for the management of features at the scale of a particular archaeological site. Moreover, computer applications in archaeology are often technology driven and software constrained. Thus, we propose a tool that tries to avoid these difficulties. We are developing an information system that works over the Internet and that is joined with a web site. Aims are to assist the work of archaeological sites managers and to be a documentation tool about these sites, dedicated to everyone. We devote therefore our system both to the professionals who are in charge of the site, and to the general public who visits it or who wants to have information on it. The system permits to do exploratory analyses of the data, especially at spatial and temporal levels. We propose to record metadata about the archaeological features in XML and to access these features through interactive 2D and 3D representations, and through queries systems (keywords and images). The 2D images, photos, or vectors are generated in SVG, while 3D models are generated in X3D. Archaeological features are also automatically integrated in a MySQL database. The web site is an exchange platform with the information system and is written in PHP. Our first application case is the medieval castle of Vianden, Luxembourg.
Protection of the information in a complex CAD system of renovation of industrial firms
Venue: arXiv cs.CE 2006
Year: 2006

The threats to security of the information originating owing to involuntary operations of the users of a CAD, and methods of its protection implemented in a complex CAD system of renovation of firms are considered: rollback, autosave, automatic backup copying and electronic subscript. The specificity of a complex CAD is reflected in necessity of rollback and autosave both of the draw and the parametric representations of its parts, which are the information models of the problem-oriented extensions of the CAD
How Random is a Coin Toss? Bayesian Inference and the Symbolic Dynamics of Deterministic Chaos
Venue: arXiv cs.LG 2006
Year: 2006

Symbolic dynamics has proven to be an invaluable tool in analyzing the mechanisms that lead to unpredictability and random behavior in nonlinear dynamical systems. Surprisingly, a discrete partition of continuous state space can produce a coarse-grained description of the behavior that accurately describes the invariant properties of an underlying chaotic attractor. In particular, measures of the rate of information production--the topological and metric entropy rates--can be estimated from the outputs of Markov or generating partitions. Here we develop Bayesian inference for k-th order Markov chains as a method to finding generating partitions and estimating entropy rates from finite samples of discretized data produced by coarse-grained dynamical systems.
The effect of 'Open Access' upon citation impact: An analysis of ArXiv's Condensed Matter Section
Venue: arXiv cs.DL 2006
Year: 2006

This article statistically analyses how the citation impact of articles deposited in the Condensed Matter section of the preprint server ArXiv (hosted by Cornell University), and subsequently published in a scientific journal, compares to that of articles in the same journal that were not deposited in that archive. Its principal aim is to further illustrate and roughly estimate the effect of two factors, 'early view' and 'quality bias', upon differences in citation impact between these two sets of papers, using citation data from Thomson Scientific's Web of Science. It presents estimates for a number of journals in the field of condensed matter physics. In order to discriminate between an 'open access' effect and an early view effect, longitudinal citation data was analysed covering a time period as long as 7 years. Quality bias was measured by calculating ArXiv citation impact differentials at the level of individual authors publishing in a journal, taking into account co-authorship. The analysis provided evidence of a strong quality bias and early view effect. Correcting for these effects, there is in a sample of 6 condensed matter physics journals studied in detail, no sign of a general 'open access advantage' of papers deposited in ArXiv. The study does provide evidence that ArXiv accelerates citation, due to the fact that that ArXiv makes papers earlier available rather than that it makes papers freely available.
Characterizing Optimal Adword Auctions
Venue: arXiv cs.GT 2006
Year: 2006

We present a number of models for the adword auctions used for pricing advertising slots on search engines such as Google, Yahoo! etc. We begin with a general problem formulation which allows the privately known valuation per click to be a function of both the identity of the advertiser and the slot. We present a compact characterization of the set of all deterministic incentive compatible direct mechanisms for this model. This new characterization allows us to conclude that there are incentive compatible mechanisms for this auction with a multi-dimensional type-space that are {\em not} affine maximizers. Next, we discuss two interesting special cases: slot independent valuation and slot independent valuation up to a privately known slot and zero thereafter. For both of these special cases, we characterize revenue maximizing and efficiency maximizing mechanisms and show that these mechanisms can be computed with a worst case computational complexity $O(n^2m^2)$ and $O(n^2m^3)$ respectively, where $n$ is number of bidders and $m$ is number of slots. Next, we characterize optimal rank based allocation rules and propose a new mechanism that we call the customized rank based allocation. We report the results of a numerical study that compare the revenue and efficiency of the proposed mechanisms. The numerical results suggest that customized rank-based allocation rule is significantly superior to the rank-based allocation rules.
Wikipedia: organisation from a bottom-up approach
Venue: arXiv cs.DL 2006
Year: 2006

Wikipedia can be considered as an extreme form of a self-managing team, as a means of labour division. One could expect that this bottom-up approach, with the absense of top-down organisational control, would lead to a chaos, but our analysis shows that this is not the case. In the Dutch Wikipedia, an integrated and coherent data structure is created, while at the same time users succeed in distributing roles by self-selection. Some users focus on an area of expertise, while others edit over the whole encyclopedic range. This constitutes our conclusion that Wikipedia, in general, is a successful example of a self-managing team.
Lossy Bulk Synchronous Parallel Processing Model for Very Large Scale Grids
Venue: arXiv cs.DC 2006
Year: 2006

The performance of a parallel algorithm in a very large scale grid is significantly influenced by the underlying Internet protocols and inter-connectivity. Many grid programming platforms use TCP due to its reliability, usually with some optimizations to reduce its costs. However, TCP does not perform well in a high bandwidth and high delay network environment. On the other hand, UDP is the fastest protocol available because it omits connection setup process, acknowledgments and retransmissions sacrificing reliable transfer. Many new bulk data transfer schemes using UDP for data transmission such as RBUDP, Tsunami, and SABUL have been introduced and shown to have better performance compared to TCP. In this paper, we consider the use of UDP and examine the relationship between packet loss and speedup with respect to the number of grid nodes. Our measurement suggests that packet loss rates between 5%-15% on average are not uncommon between PlanetLab nodes that are widely distributed over the Internet. We show that transmitting multiple copies of same packet produces higher speedup. We show the minimum number of packet duplication required to maximize the possible speedup for a given number of nodes using a BSP based model. Our work demonstrates that by using an appropriate number of packet copies, we can increase performance of parallel program.
Clustering and Sharing Incentives in BitTorrent Systems
Venue: arXiv cs.NI 2006
Year: 2006

Peer-to-peer protocols play an increasingly instrumental role in Internet content distribution. Consequently, it is important to gain a full understanding of how these protocols behave in practice and how their parameters impact overall performance. We present the first experimental investigation of the peer selection strategy of the popular BitTorrent protocol in an instrumented private torrent. By observing the decisions of more than 40 nodes, we validate three BitTorrent properties that, though widely believed to hold, have not been demonstrated experimentally. These include the clustering of similar-bandwidth peers, the effectiveness of BitTorrent's sharing incentives, and the peers' high average upload utilization. In addition, our results show that BitTorrent's new choking algorithm in seed state provides uniform service to all peers, and that an underprovisioned initial seed leads to the absence of peer clustering and less effective sharing incentives. Based on our observations, we provide guidelines for seed provisioning by content providers, and discuss a tracker protocol extension that addresses an identified limitation of the protocol.
2FACE: Bi-Directional Face Traversal for Efficient Geometric Routing
Venue: arXiv cs.DC 2006
Year: 2006

We propose bi-directional face traversal algorithm $2FACE$ to shorten the path the message takes to reach the destination in geometric routing. Our algorithm combines the practicality of the best single-direction traversal algorithms with the worst case message complexity of $O(|E|)$, where $E$ is the number of network edges. We apply $2FACE$ to a variety of geometric routing algorithms. Our simulation results indicate that bi-directional face traversal decreases the latency of message delivery two to three times compared to single direction face traversal. The thus selected path approaches the shortest possible route. This gain in speed comes with a similar message overhead increase. We describe an algorithm which compensates for this message overhead by recording the preferable face traversal direction. Thus, if a source has several messages to send to the destination, the subsequent messages follow the shortest route. Our simulation results show that with most geometric routing algorithms the message overhead of finding the short route by bi-directional face traversal is compensated within two to four repeat messages.
Wireless Information-Theoretic Security - Part I: Theoretical Aspects
Venue: arXiv cs.IT 2006
Year: 2006

In this two-part paper, we consider the transmission of confidential data over wireless wiretap channels. The first part presents an information-theoretic problem formulation in which two legitimate partners communicate over a quasi-static fading channel and an eavesdropper observes their transmissions through another independent quasi-static fading channel. We define the secrecy capacity in terms of outage probability and provide a complete characterization of the maximum transmission rate at which the eavesdropper is unable to decode any information. In sharp contrast with known results for Gaussian wiretap channels (without feedback), our contribution shows that in the presence of fading information-theoretic security is achievable even when the eavesdropper has a better average signal-to-noise ratio (SNR) than the legitimate receiver - fading thus turns out to be a friend and not a foe. The issue of imperfect channel state information is also addressed. Practical schemes for wireless information-theoretic security are presented in Part II, which in some cases comes close to the secrecy capacity limits given in this paper.
Scale-Free Overlay Topologies with Hard Cutoffs for Unstructured Peer-to-Peer Networks
Venue: arXiv cs.NI 2006
Year: 2006

In unstructured peer-to-peer (P2P) networks, the overlay topology (or connectivity graph) among peers is a crucial component in addition to the peer/data organization and search. Topological characteristics have profound impact on the efficiency of search on such unstructured P2P networks as well as other networks. It has been well-known that search on small-world topologies of N nodes can be as efficient as O(ln N), while scale-free (power-law) topologies offer even better search efficiencies like as good as O(lnln N) for a range of degree distribution exponents. However, generation and maintenance of such scale-free topologies are hard to realize in a distributed and potentially uncooperative environments as in the P2P networks. A key limitation of scale-free topologies is the high load (i.e. high degree) on very few number of hub nodes. In a typical unstructured P2P network, peers are not willing to maintain high degrees/loads as they may not want to store large number of entries for construction of the overlay topology. So, to achieve fairness and practicality among all peers, hard cutoffs on the number of entries are imposed by the individual peers, which limits scale-freeness of the overall topology. Thus, efficiency of the flooding search reduces as the size of the hard cutoff does. We investigate construction of scale-free topologies with hard cutoffs (i.e. there are not any major hubs) and effect of these hard cutoffs on the search efficiency. Interestingly, we observe that the efficiency of normalized flooding and random walk search algorithms increases as the hard cutoff decreases.
The specifications making in complex CAD-system of renovation of the enterprises on the basis of modules in the drawing and electronic catalogues
Venue: arXiv cs.CE 2006
Year: 2006

The experience of automation of the specifications making of the projects of renovation of the industrial enterprises is described, being based on the special modules in the drawing containing the visible image and additional parameters, and electronic catalogues
The modelling of the automation schemes of technological processes in CAD-system of renovation of the enterprises
Venue: arXiv cs.CE 2006
Year: 2006

According to the requirements of the Russian standards, the automation schemes are necessary practically in each project of renovation of industrial buildings and facilities, in which any technological processes are realized. The model representations of the automation schemes in CAD-system TechnoCAD GlassX are described. The models follow a principle "to exclude a repeated input operations"
Experimental Information and Statistical Modeling of Physical Laws
Venue: arXiv cs.IT 2006
Year: 2006

Statistical modeling of physical laws connects experiments with mathematical descriptions of natural phenomena. The modeling is based on the probability density of measured variables expressed by experimental data via a kernel estimator. As an objective kernel the scattering function determined by calibration of the instrument is introduced. This function provides for a new definition of experimental information and redundancy of experimentation in terms of information entropy. The redundancy increases with the number of experiments, while the experimental information converges to a value that describes the complexity of the data. The difference between the redundancy and the experimental information is proposed as the model cost function. From its minimum, a proper number of data in the model is estimated. As an optimal, nonparametric estimator of the relation between measured variables the conditional average extracted from the kernel estimator is proposed. The modeling is demonstrated on noisy chaotic data.
Loop corrections for approximate inference
Venue: arXiv cs.AI 2006
Year: 2006

We propose a method for improving approximate inference methods that corrects for the influence of loops in the graphical model. The method is applicable to arbitrary factor graphs, provided that the size of the Markov blankets is not too large. It is an alternative implementation of an idea introduced recently by Montanari and Rizzo (2005). In its simplest form, which amounts to the assumption that no loops are present, the method reduces to the minimal Cluster Variation Method approximation (which uses maximal factors as outer clusters). On the other hand, using estimates of the effect of loops (obtained by some approximate inference algorithm) and applying the Loop Correcting (LC) method usually gives significantly better results than applying the approximate inference algorithm directly without loop corrections. Indeed, we often observe that the loop corrected error is approximately the square of the error of the approximate inference method used to estimate the effect of loops. We compare different variants of the Loop Correcting method with other approximate inference methods on a variety of graphical models, including "real world" networks, and conclude that the LC approach generally obtains the most accurate results.
Decentralized Maximum Likelihood Estimation for Sensor Networks Composed of Nonlinearly Coupled Dynamical Systems
Venue: arXiv cs.DC 2006
Year: 2006

In this paper we propose a decentralized sensor network scheme capable to reach a globally optimum maximum likelihood (ML) estimate through self-synchronization of nonlinearly coupled dynamical systems. Each node of the network is composed of a sensor and a first-order dynamical system initialized with the local measurements. Nearby nodes interact with each other exchanging their state value and the final estimate is associated to the state derivative of each dynamical system. We derive the conditions on the coupling mechanism guaranteeing that, if the network observes one common phenomenon, each node converges to the globally optimal ML estimate. We prove that the synchronized state is globally asymptotically stable if the coupling strength exceeds a given threshold. Acting on a single parameter, the coupling strength, we show how, in the case of nonlinear coupling, the network behavior can switch from a global consensus system to a spatial clustering system. Finally, we show the effect of the network topology on the scalability properties of the network and we validate our theoretical findings with simulation results.
Social Browsing on Flickr
Venue: arXiv cs.HC 2006
Year: 2006

The new social media sites - blogs, wikis, del.icio.us and Flickr, among others - underscore the transformation of the Web to a participatory medium in which users are actively creating, evaluating and distributing information. The photo-sharing site Flickr, for example, allows users to upload photographs, view photos created by others, comment on those photos, etc. As is common to other social media sites, Flickr allows users to designate others as ``contacts'' and to track their activities in real time. The contacts (or friends) lists form the social network backbone of social media sites. We claim that these social networks facilitate new ways of interacting with information, e.g., through what we call social browsing. The contacts interface on Flickr enables users to see latest images submitted by their friends. Through an extensive analysis of Flickr data, we show that social browsing through the contacts' photo streams is one of the primary methods by which users find new images on Flickr. This finding has implications for creating personalized recommendation systems based on the user's declared contacts lists.
Budget Optimization in Search-Based Advertising Auctions
Venue: arXiv cs.DS 2006
Year: 2006

Internet search companies sell advertisement slots based on users' search queries via an auction. While there has been a lot of attention on the auction process and its game-theoretic aspects, our focus is on the advertisers. In particular, the advertisers have to solve a complex optimization problem of how to place bids on the keywords of their interest so that they can maximize their return (the number of user clicks on their ads) for a given budget. We model the entire process and study this budget optimization problem. While most variants are NP hard, we show, perhaps surprisingly, that simply randomizing between two uniform strategies that bid equally on all the keywords works well. More precisely, this strategy gets at least 1-1/e fraction of the maximum clicks possible. Such uniform strategies are likely to be practical. We also present inapproximability results, and optimal algorithms for variants of the budget optimization problem.
Deriving Schrodinger Equation From A Soft-Decision Iterative Decoding Algorithm
Venue: arXiv cs.IT 2006
Year: 2006

The belief propagation algorithm has been recognized in the information theory community as a soft-decision iterative decoding algorithm. It is the most powerful algorithm found so far for attacking hard optimization problems in channel decoding. Quantum mechanics is the foundation of modern physics with the time-independent Schrodinger equation being one of the most important equations. This paper shows that the equation can be derived from a generalized belief propagation algorithm. Such a connection on a mathematical basis might shed new insights into the foundations of quantum mechanics and quantum computing.