OpenRaiser/Intern-Atlas huggingface dataset:
A Simple Test on 2-Vertex- and 2-Edge-Connectivity
Venue: arXiv cs.DS 2012
Year: 2012

Testing a graph on 2-vertex- and 2-edge-connectivity are two fundamental algorithmic graph problems. For both problems, different linear-time algorithms with simple implementations are known. Here, an even simpler linear-time algorithm is presented that computes a structure from which both the 2-vertex- and 2-edge-connectivity of a graph can be easily "read off". The algorithm computes all bridges and cut vertices of the input graph in the same time.
A Universal Scheme for Transforming Binary Algorithms to Generate Random Bits from Loaded Dice
Venue: arXiv cs.IT 2012
Year: 2012

In this paper, we present a universal scheme for transforming an arbitrary algorithm for biased 2-face coins to generate random bits from the general source of an m-sided die, hence enabling the application of existing algorithms to general sources. In addition, we study approaches of efficiently generating a prescribed number of random bits from an arbitrary biased coin. This contrasts with most existing works, which typically assume that the number of coin tosses is fixed, and they generate a variable number of random bits.
Some modifications to the SNIP journal impact indicator
Venue: arXiv cs.DL 2012
Year: 2012

The SNIP (source normalized impact per paper) indicator is an indicator of the citation impact of scientific journals. The indicator, introduced by Henk Moed in 2010, is included in Elsevier's Scopus database. The SNIP indicator uses a source normalized approach to correct for differences in citation practices between scientific fields. The strength of this approach is that it does not require a field classification system in which the boundaries of fields are explicitly defined. In this paper, a number of modifications that will be made to the SNIP indicator are explained, and the advantages of the resulting revised SNIP indicator are pointed out. It is argued that the original SNIP indicator has some counterintuitive properties, and it is shown mathematically that the revised SNIP indicator does not have these properties. Empirically, the differences between the original SNIP indicator and the revised one turn out to be relatively small, although some systematic differences can be observed. Relations with other source normalized indicators proposed in the literature are discussed as well.
Coopetitive Ad Auctions
Venue: arXiv cs.GT 2012
Year: 2012

A single advertisement often benefits many parties, for example, an ad for a Samsung laptop benefits Microsoft. We study this phenomenon in search advertising auctions and show that standard solutions, including the status quo ignorance of mutual benefit and a benefit-aware Vickrey-Clarke-Groves mechanism, perform poorly. In contrast, we show that an appropriate first-price auction has nice equilibria in a single-slot ad auction --- all equilibria that satisfy a natural cooperative envy-freeness condition select the welfare-maximizing ad and satisfy an intuitive lower-bound on revenue.
KeyAuth: Bringing Public-key Authentication to the Masses
Venue: arXiv cs.CR 2012
Year: 2012

Passwords are a fragile, inadequate, and insecure tool for authenticating users, and are especially fraught with problems when used to secure access to network resources and services. In many cases, passwords provide a false sense of security. Creating passwords which are both secure (i.e., hard for attackers to guess) and easy for humans to remember is, at best, a paradoxical task because these two criteria are diametrically opposed. Fortunately, a far more secure and user-friendly alternative is available. Public-key cryptography provides a means of both identifying and authenticating users without the need for passwords. KeyAuth is a generic and universal implementation of public-key authentication aimed at supplanting password-based authentication and significantly improving the security of network accessible resources by enhancing the usability of frequently used authentication mechanisms. KeyAuth is an application-, language-, operating system-, and protocol-independent public-key authentication service.
Kleisli Database Instances
Venue: arXiv cs.DB 2012
Year: 2012

We use monads to relax the atomicity requirement for data in a database. Depending on the choice of monad, the database fields may contain generalized values such as lists or sets of values, or they may contain exceptions such as various types of nulls. The return operation for monads ensures that any ordinary database instance will count as one of these generalized instances, and the bind operation ensures that generalized values behave well under joins of foreign key sequences. Different monads allow for vastly different types of information to be stored in the database. For example, we show that classical concepts like Markov chains, graphs, and finite state automata are each perfectly captured by a different monad on the same schema.
Video Data Visualization System: Semantic Classification And Personalization
Venue: arXiv cs.IR 2012
Year: 2012

We present in this paper an intelligent video data visualization tool, based on semantic classification, for retrieving and exploring a large scale corpus of videos. Our work is based on semantic classification resulting from semantic analysis of video. The obtained classes will be projected in the visualization space. The graph is represented by nodes and edges, the nodes are the keyframes of video documents and the edges are the relation between documents and the classes of documents. Finally, we construct the user's profile, based on the interaction with the system, to render the system more adequate to its references.
Distributed Optimal Beamformers for Cognitive Radios Robust to Channel Uncertainties
Venue: arXiv cs.IT 2012
Year: 2012

Through spatial multiplexing and diversity, multi-input multi-output (MIMO) cognitive radio (CR) networks can markedly increase transmission rates and reliability, while controlling the interference inflicted to peer nodes and primary users (PUs) via beamforming. The present paper optimizes the design of transmit- and receive-beamformers for ad hoc CR networks when CR-to-CR channels are known, but CR-to-PU channels cannot be estimated accurately. Capitalizing on a norm-bounded channel uncertainty model, the optimal beamforming design is formulated to minimize the overall mean-square error (MSE) from all data streams, while enforcing protection of the PU system when the CR-to-PU channels are uncertain. Even though the resultant optimization problem is non-convex, algorithms with provable convergence to stationary points are developed by resorting to block coordinate ascent iterations, along with suitable convex approximation techniques. Enticingly, the novel schemes also lend themselves naturally to distributed implementations. Numerical tests are reported to corroborate the analytical findings.
On Byzantine Broadcast in Loosely Connected Networks
Venue: arXiv cs.DC 2012
Year: 2012

We consider the problem of reliably broadcasting information in a multihop asynchronous network that is subject to Byzantine failures. Most existing approaches give conditions for perfect reliable broadcast (all correct nodes deliver the authentic message and nothing else), but they require a highly connected network. An approach giving only probabilistic guarantees (correct nodes deliver the authentic message with high probability) was recently proposed for loosely connected networks, such as grids and tori. Yet, the proposed solution requires a specific initialization (that includes global knowledge) of each node, which may be difficult or impossible to guarantee in self-organizing networks - for instance, a wireless sensor network, especially if they are prone to Byzantine failures. In this paper, we propose a new protocol offering guarantees for loosely connected networks that does not require such global knowledge dependent initialization. In more details, we give a methodology to determine whether a set of nodes will always deliver the authentic message, in any execution. Then, we give conditions for perfect reliable broadcast in a torus network. Finally, we provide experimental evaluation for our solution, and determine the number of randomly distributed Byzantine failures than can be tolerated, for a given correct broadcast probability.
The End of an Architectural Era for Analytical Databases
Venue: arXiv cs.DB 2012
Year: 2012

Traditional enterprise warehouse solutions center around an analytical database system that is monolithic and inflexible: data needs to be extracted, transformed, and loaded into the rigid relational form before analysis. It takes years of sophisticated planning to provision and deploy a warehouse; adding new hardware resources to an existing warehouse is an equally lengthy and daunting task. Additionally, modern data analysis employs statistical methods that go well beyond the typical roll-up and drill-down capabilities provided by warehouse systems. Although it is possible to implement such methods using a combination of SQL and UDFs, query engines in relational databases are ill-suited for these. The Hadoop ecosystem introduces a suite of tools for data analytics that overcome some of the problems of traditional solutions. These systems, however, forgo years of warehouse research. Memory is significantly underutilized in Hadoop clusters, and execution engine is naive compared with its relational counterparts. It is time to rethink the design of data warehouse systems and take the best from both worlds. The new generation of warehouse systems should be modular, high performance, fault-tolerant, easy to provision, and designed to support both SQL query processing and machine learning applications. This paper references the Shark system developed at Berkeley as an initial attempt.
Unilateral Antidotes to DNS Cache Poisoning
Venue: arXiv cs.CR 2012
Year: 2012

We investigate defenses against DNS cache poisoning focusing on mechanisms that can be readily deployed unilaterally by the resolving organisation, preferably in a single gateway or a proxy. DNS poisoning is (still) a major threat to Internet security; determined spoofing attackers are often able to circumvent currently deployed antidotes such as port randomisation. The adoption of DNSSEC, which would foil DNS poisoning, remains a long-term challenge. We discuss limitations of the prominent resolver-only defenses, mainly port and IP randomisation, 0x20 encoding and birthday protection. We then present two new (unilateral) defenses: the sandwich antidote and the NAT antidote. The defenses are simple, effective and efficient, and can be implemented in a gateway connecting the resolver to the Internet. The sandwich antidote is composed of two phases: poisoning-attack detection and then prevention. The NAT antidote adds entropy to DNS requests by switching the resolver's IP address to a random address (belonging to the same autonomous system). Finally, we show how to implement the birthday protection mechanism in the gateway, thus allowing to restrict the number of DNS requests with the same query to 1 even when the resolver does not support this.
Wavelet Based QRS Complex Detection of ECG Signal
Venue: arXiv cs.CV 2012
Year: 2012

The Electrocardiogram (ECG) is a sensitive diagnostic tool that is used to detect various cardiovascular diseases by measuring and recording the electrical activity of the heart in exquisite detail. A wide range of heart condition is determined by thorough examination of the features of the ECG report. Automatic extraction of time plane features is important for identification of vital cardiac diseases. This paper presents a multi-resolution wavelet transform based system for detection 'P', 'Q', 'R', 'S', 'T' peaks complex from original ECG signal. 'R-R' time lapse is an important minutia of the ECG signal that corresponds to the heartbeat of the concerned person. Abrupt increase in height of the 'R' wave or changes in the measurement of the 'R-R' denote various anomalies of human heart. Similarly 'P-P', 'Q-Q', 'S-S', 'T-T' also corresponds to different anomalies of heart and their peak amplitude also envisages other cardiac diseases. In this proposed method the 'PQRST' peaks are marked and stored over the entire signal and the time interval between two consecutive 'R' peaks and other peaks interval are measured to detect anomalies in behavior of heart, if any. The peaks are achieved by the composition of Daubeheissub bands wavelet of original ECG signal. The accuracy of the 'PQRST' complex detection and interval measurement is achieved up to 100% with high exactitude by processing and thresholding the original ECG signal.
Power-laws and the Conservation of Information in discrete token systems: Part 2 The role of defect
Venue: arXiv cs.IT 2012
Year: 2012

In a matching paper (arXiv:1207.5027), I proved that Conservation of Size and Information in a discrete token based system is overwhelmingly likely to lead to a power-law component size distribution with respect to the size of its unique alphabet. This was substantiated to a very high level of significance using some 55 million lines of source code of mixed provenance. The principle was also applied to show that average gene length should be constant in an animal kingdom where the same constraints appear to hold, the implication being that Conservation of Information plays a similar role in discrete token-based systems as the Conservation of Energy does in physical systems. In this part 2, the role of defect will be explored and a functional behaviour for defect derived to be consistent with the power-law behaviour substantiated above. This will be supported by further experimental data and the implications explored.
Recovering Missing Coefficients in DCT-Transformed Images
Venue: arXiv cs.MM 2012
Year: 2012

A general method for recovering missing DCT coefficients in DCT-transformed images is presented in this work. We model the DCT coefficients recovery problem as an optimization problem and recover all missing DCT coefficients via linear programming. The visual quality of the recovered image gradually decreases as the number of missing DCT coefficients increases. For some images, the quality is surprisingly good even when more than 10 most significant DCT coefficients are missing. When only the DC coefficient is missing, the proposed algorithm outperforms existing methods according to experimental results conducted on 200 test images. The proposed recovery method can be used for cryptanalysis of DCT based selective encryption schemes and other applications.
Model Checking the Quantitative mu-Calculus on Linear Hybrid Systems
Venue: arXiv cs.LO 2012
Year: 2012

We study the model-checking problem for a quantitative extension of the modal mu-calculus on a class of hybrid systems. Qualitative model checking has been proved decidable and implemented for several classes of systems, but this is not the case for quantitative questions that arise naturally in this context. Recently, quantitative formalisms that subsume classical temporal logics and allow the measurement of interesting quantitative phenomena were introduced. We show how a powerful quantitative logic, the quantitative mu-calculus, can be model checked with arbitrary precision on initialised linear hybrid systems. To this end, we develop new techniques for the discretisation of continuous state spaces based on a special class of strategies in model-checking games and present a reduction to a class of counter parity games.
Difference of Normals as a Multi-Scale Operator in Unorganized Point Clouds
Venue: arXiv cs.CV 2012
Year: 2012

A novel multi-scale operator for unorganized 3D point clouds is introduced. The Difference of Normals (DoN) provides a computationally efficient, multi-scale approach to processing large unorganized 3D point clouds. The application of DoN in the multi-scale filtering of two different real-world outdoor urban LIDAR scene datasets is quantitatively and qualitatively demonstrated. In both datasets the DoN operator is shown to segment large 3D point clouds into scale-salient clusters, such as cars, people, and lamp posts towards applications in semi-automatic annotation, and as a pre-processing step in automatic object recognition. The application of the operator to segmentation is evaluated on a large public dataset of outdoor LIDAR scenes with ground truth annotations.
On the Use of Lee's Protocol for Speckle-Reducing Techniques
Venue: arXiv cs.CV 2012
Year: 2012

This paper presents two new MAP (Maximum a Posteriori) filters for speckle noise reduction and a Monte Carlo procedure for the assessment of their performance. In order to quantitatively evaluate the results obtained using these new filters, with respect to classical ones, a Monte Carlo extension of Lee's protocol is proposed. This extension of the protocol shows that its original version leads to inconsistencies that hamper its use as a general procedure for filter assessment. Some solutions for these inconsistencies are proposed, and a consistent comparison of speckle-reducing filters is provided.
Evaluating the SiteStory Transactional Web Archive With the ApacheBench Tool
Venue: arXiv cs.PF 2012
Year: 2012

Conventional Web archives are created by periodically crawling a web site and archiving the responses from the Web server. Although easy to implement and common deployed, this form of archiving typically misses updates and may not be suitable for all preservation scenarios, for example a site that is required (perhaps for records compliance) to keep a copy of all pages it has served. In contrast, transactional archives work in conjunction with a Web server to record all pages that have been served. Los Alamos National Laboratory has developed SiteSory, an open-source transactional archive written in Java solution that runs on Apache Web servers, provides a Memento compatible access interface, and WARC file export features. We used the ApacheBench utility on a pre-release version of to measure response time and content delivery time in different environments and on different machines. The performance tests were designed to determine the feasibility of SiteStory as a production-level solution for high fidelity automatic Web archiving. We found that SiteStory does not significantly affect content server performance when it is performing transactional archiving. Content server performance slows from 0.076 seconds to 0.086 seconds per Web page access when the content server is under load, and from 0.15 seconds to 0.21 seconds when the resource has many embedded and changing resources.
Ten times eighteen
Venue: arXiv cs.DM 2012
Year: 2012

We consider the following simple game: We are given a table with ten slots indexed one to ten. In each of the ten rounds of the game, three dice are rolled and the numbers are added. We then put this number into any free slot. For each slot, we multiply the slot index with the number in this slot, and add up the products. The goal of the game is to maximize this score. In more detail, we play the game many times, and try to maximize the sum of scores or, equivalently, the expected score. We present a strategy to optimally play this game with respect to the expected score. We then modify our strategy so that we need only polynomial time and space. Finally, we show that knowing all ten rolls in advance, results in a relatively small increase in score. Although the game has a random component and requires a non-trivial strategy to be solved optimally, this strategy needs only polynomial time and space.
Safe and Stabilizing Distributed Multi-Path Cellular Flows
Venue: arXiv cs.RO 2012
Year: 2012

We study the problem of distributed traffic control in the partitioned plane, where the movement of all entities (robots, vehicles, etc.) within each partition (cell) is coupled. Establishing liveness in such systems is challenging, but such analysis will be necessary to apply such distributed traffic control algorithms in applications like coordinating robot swarms and the intelligent highway system. We present a formal model of a distributed traffic control protocol that guarantees minimum separation between entities, even as some cells fail. Once new failures cease occurring, in the case of a single target, the protocol is guaranteed to self-stabilize and the entities with feasible paths to the target cell make progress towards it. For multiple targets, failures may cause deadlocks in the system, so we identify a class of non-deadlocking failures where all entities are able to make progress to their respective targets. The algorithm relies on two general principles: temporary blocking for maintenance of safety and local geographical routing for guaranteeing progress. Our assertional proofs may serve as a template for the analysis of other distributed traffic control protocols. We present simulation results that provide estimates of throughput as a function of entity velocity, safety separation, single-target path complexity, failure-recovery rates, and multi-target path complexity.
A single-photon sampling architecture for solid-state imaging
Venue: arXiv cs.IT 2012
Year: 2012

Advances in solid-state technology have enabled the development of silicon photomultiplier sensor arrays capable of sensing individual photons. Combined with high-frequency time-to-digital converters (TDCs), this technology opens up the prospect of sensors capable of recording with high accuracy both the time and location of each detected photon. Such a capability could lead to significant improvements in imaging accuracy, especially for applications operating with low photon fluxes such as LiDAR and positron emission tomography. The demands placed on on-chip readout circuitry imposes stringent trade-offs between fill factor and spatio-temporal resolution, causing many contemporary designs to severely underutilize the technology's full potential. Concentrating on the low photon flux setting, this paper leverages results from group testing and proposes an architecture for a highly efficient readout of pixels using only a small number of TDCs, thereby also reducing both cost and power consumption. The design relies on a multiplexing technique based on binary interconnection matrices. We provide optimized instances of these matrices for various sensor parameters and give explicit upper and lower bounds on the number of TDCs required to uniquely decode a given maximum number of simultaneous photon arrivals. To illustrate the strength of the proposed architecture, we note a typical digitization result of a 120x120 photodiode sensor on a 30um x 30um pitch with a 40ps time resolution and an estimated fill factor of approximately 70%, using only 161 TDCs. The design guarantees registration and unique recovery of up to 4 simultaneous photon arrivals using a fast decoding algorithm. In a series of realistic simulations of scintillation events in clinical positron emission tomography the design was able to recover the spatio-temporal location of 98.6% of all photons that caused pixel firings.
Identification of Fertile Translations in Medical Comparable Corpora: a Morpho-Compositional Approach
Venue: arXiv cs.CL 2012
Year: 2012

This paper defines a method for lexicon in the biomedical domain from comparable corpora. The method is based on compositional translation and exploits morpheme-level translation equivalences. It can generate translations for a large variety of morphologically constructed words and can also generate 'fertile' translations. We show that fertile translations increase the overall quality of the extracted lexicon for English to French translation.