OpenRaiser/Intern-Atlas huggingface dataset:
Data-Oblivious External-Memory Algorithms for the Compaction, Selection, and Sorting of Outsourced Data
Venue: arXiv cs.DS 2011
Year: 2011

We present data-oblivious algorithms in the external-memory model for compaction, selection, and sorting. Motivation for such problems comes from clients who use outsourced data storage services and wish to mask their data access patterns. We show that compaction and selection can be done data-obliviously using $O(N/B)$ I/Os, and sorting can be done, with a high probability of success, using $O((N/B)\log_{M/B} (N/B))$ I/Os. Our methods use a number of new algorithmic techniques, including data-oblivious uses of invertible Bloom lookup tables, a butterfly-like compression network, randomized data thinning, and "shuffle-and-deal" data perturbation. In addition, since data-oblivious sorting is the bottleneck in the "inner loop" in existing oblivious RAM simulations, our sorting result improves the amortized time overhead to do oblivious RAM simulation by a logarithmic factor in the external-memory model.
Analysis of Equilibria and Strategic Interaction in Complex Networks
Venue: arXiv cs.GT 2011
Year: 2011

This paper studies $n$-person simultaneous-move games with linear best response function, where individuals interact within a given network structure. This class of games have been used to model various settings, such as, public goods, belief formation, peer effects, and oligopoly. The purpose of this paper is to study the effect of the network structure on Nash equilibrium outcomes of this class of games. Bramoullé et al. derived conditions for uniqueness and stability of a Nash equilibrium in terms of the smallest eigenvalue of the adjacency matrix representing the network of interactions. Motivated by this result, we study how local structural properties of the network of interactions affect this eigenvalue, influencing game equilibria. In particular, we use algebraic graph theory and convex optimization to derive new bounds on the smallest eigenvalue in terms of the distribution of degrees, cycles, and other relevant substructures. We illustrate our results with numerical simulations involving online social networks.
Encipher of information on the basis of geometrical presentations
Venue: arXiv cs.CR 2011
Year: 2011

In this paper, we examine a ciphertext on the basis of using geometrical objects. Each symbol normative alphabet is determined as a point on the plane. We consider possible ways for presentation of these points.
Upper Bounds on the Probability of Error in terms of Mean Divergence Measures
Venue: arXiv cs.IT 2011
Year: 2011

In this paper we shall consider some famous means such as arithmetic, harmonic, geometric, root square mean, etc. Considering the difference of these means, we can establish. some inequalities among them. Interestingly, the difference of mean considered is convex functions. Applying some properties, upper bounds on the probability of error are established in this paper. It is also shown that the results obtained are sharper than obtained directly applying known inequalities.
Integrated Impact Indicators (I3) compared with Impact Factors (IFs): An alternative research design with policy implications
Venue: arXiv cs.DL 2011
Year: 2011

In bibliometrics, the association of "impact" with central-tendency statistics is mistaken. Impacts add up, and citation curves should therefore be integrated instead of averaged. For example, the journals MIS Quarterly and JASIST differ by a factor of two in terms of their respective impact factors (IF), but the journal with the lower IF has the higher impact. Using percentile ranks (e.g., top-1%, top-10%, etc.), an integrated impact indicator (I3) can be based on integration of the citation curves, but after normalization of the citation curves to the same scale. The results across document sets can be compared as percentages of the total impact of a reference set. Total number of citations, however, should not be used instead because the shape of the citation curves is then not appreciated. I3 can be applied to any document set and any citation window. The results of the integration (summation) are fully decomposable in terms of journals or instititutional units such as nations, universities, etc., because percentile ranks are determined at the paper level. In this study, we first compare I3 with IFs for the journals in two ISI Subject Categories ("Information Science & Library Science" and "Multidisciplinary Sciences"). The LIS set is additionally decomposed in terms of nations. Policy implications of this possible paradigm shift in citation impact analysis are specified.
Network Estimation and Packet Delivery Prediction for Control over Wireless Mesh Networks
Venue: arXiv cs.SY 2011
Year: 2011

Much of the current theory of networked control systems uses simple point-to-point communication models as an abstraction of the underlying network. As a result, the controller has very limited information on the network conditions and performs suboptimally. This work models the underlying wireless multihop mesh network as a graph of links with transmission success probabilities, and uses a recursive Bayesian estimator to provide packet delivery predictions to the controller. The predictions are a joint probability distribution on future packet delivery sequences, and thus capture correlations between successive packet deliveries. We look at finite horizon LQG control over a lossy actuation channel and a perfect sensing channel, both without delay, to study how the controller can compensate for predicted network outages.
A Lattice Compress-and-Forward Scheme
Venue: arXiv cs.IT 2011
Year: 2011

We present a nested lattice-code-based strategy that achieves the random-coding based Compress-and-Forward (CF) rate for the three node Gaussian relay channel. To do so, we first outline a lattice-based strategy for the $(X+Z_1,X+Z_2)$ Wyner-Ziv lossy source-coding with side-information problem in Gaussian noise, a re-interpretation of the nested lattice-code-based Gaussian Wyner-Ziv scheme presented by Zamir, Shamai, and Erez. We use the notation $(X+Z_1,X+Z_2)$ Wyner-Ziv to mean that the source is of the form $X+ Z_1$ and the side-information at the receiver is of the form $X+ Z_2$, for independent Gaussian $X, Z_1$ and $Z_2$. We next use this $(X+Z_1,X+Z_2)$ Wyner-Ziv scheme to implement a "structured" or lattice-code-based CF scheme which achieves the classic CF rate for Gaussian relay channels. This suggests that lattice codes may not only be useful in point-to-point single-hop source and channel coding, in multiple access and broadcast channels, but that they may also be useful in larger relay networks. The usage of lattice codes in larger networks is motivated by their structured nature (possibly leading to rate gains) and decoding (relatively simple) being more practically realizable than their random coding based counterparts. We furthermore expect the proposed lattice-based CF scheme to constitute a first step towards a generic structured achievability scheme for networks such as a structured version of the recently introduced "noisy network coding".
On the Complexity of Edge Packing and Vertex Packing
Venue: arXiv cs.CC 2011
Year: 2011

This paper studies the computational complexity of the Edge Packing problem and the Vertex Packing problem. The edge packing problem (denoted by $\bar{EDS}$) and the vertex packing problem (denoted by $\bar{DS} $) are linear programming duals of the edge dominating set problem and the dominating set problem respectively. It is shown that these two problems are equivalent to the set packing problem with respect to hardness of approximation and parametric complexity. It follows that $\bar{EDS}$ and $\bar{DS}$ cannot be approximated asymptotically within a factor of $O(N^{1/2-ε})$ for any $ε>0$ unless $NP=ZPP$ where, $N$ is the number of vertices in the given graph. This is in contrast with the fact that the edge dominating set problem is 2-approximable where as the dominating set problem is known to have an $O(\log$ $|V|)$ approximation algorithm. It also follows from our proof that $\bar{EDS}$ and $\bar{DS}$ are $W[1]$-complete.
Designing a Miniature Wheel Arrangement for Mobile Robot Platforms
Venue: arXiv cs.RO 2011
Year: 2011

In this research report details of design of a miniature wheel arrangement are presented. This miniature wheel arrangement is essentially a direction control mechanism intended for use on a mobile robot platform or base. The design is a specific one employing a stepper motor as actuator and as described can only be used on a certain type of wheeled robots. However, as a basic steering control element, more than one of these miniature wheel arrangements can be grouped together to implement more elaborate and intelligent direction control schemes on varying configurations of wheeled mobile robot platforms.
Application of Threshold Techniques for Readability Improvement of Jawi Historical Manuscript Images
Venue: arXiv cs.CV 2011
Year: 2011

Historical documents such as old books and manuscripts have a high aesthetic value and highly appreciated. Unfortunately, there are some documents cannot be read due to quality problems like faded paper, ink expand, uneven colour tone, torn paper and other elements disruption such as the existence of small spots. The study aims to produce a copy of manuscript that shows clear wordings so they can easily be read and the copy can also be displayed for visitors. 16 samples of Jawi historical manuscript with different quality problems were obtained from The Royal Museum of Pahang, Malaysia. We applied three binarization techniques; Otsu's method represents global threshold technique; Sauvola and Niblack method which are categorized as local threshold techniques. We compared the binarized images with the original manuscript to be visually inspected by the museum's curator. The unclear features were marked and analyzed. Most of the examined images show that with optimal parameters and effective pre processing technique, local thresholding methods are work well compare with the other one. Niblack's and Sauvola's techniques seem to be the suitable approaches for these types of images. Most of binarized images with these two methods show improvement for readability and character recognition. For this research, even the differences of image result were hard to be distinguished by human capabilities, after comparing the time cost and overall achievement rate of recognized symbols, Niblack's method is performing better than Sauvola's. We could improve the post processing step by adding edge detection techniques and further enhanced by an innovative image refinement technique and a formulation of a class proper method.
Poster Abstract: If You Have Time, Save Energy with Pull
Venue: arXiv cs.NI 2011
Year: 2011

We analyze push and pull for data collection in wireless sensor networks. Most applications to date use the traditional push approach, where nodes transmit sensed data immedi- ately to the sink. Using a pull approach, nodes store the data in their local flash memory, and only engage in commu- nication during dedicated collection phases. We show how one can transform an existing push-based collection protocol into a pull-based one, and compare the power consumption of both approaches on a 35-node testbed. Our results show that substantial energy gains are possible with pull, provided that the application can tolerate a long latency.
Key Management in Wireless Sensor Networks Using a Modified Blom Scheme
Venue: arXiv cs.CR 2011
Year: 2011

Key establishment between any pair of nodes is an essential requirement for providing secure services in wireless sensor networks. Blom's scheme is a prominent key management scheme but its shortcomings include large computation overhead and memory cost. We propose a new scheme in this paper that modifies Blom's scheme in a manner that reduces memory and computation costs. This paper also provides the value for secure parameter t such that the network is resilient.
Generating and Searching Families of FFT Algorithms
Venue: arXiv cs.IT 2011
Year: 2011

A fundamental question of longstanding theoretical interest is to prove the lowest exact count of real additions and multiplications required to compute a power-of-two discrete Fourier transform (DFT). For 35 years the split-radix algorithm held the record by requiring just 4n log n - 6n + 8 arithmetic operations on real numbers for a size-n DFT, and was widely believed to be the best possible. Recent work by Van Buskirk et al. demonstrated improvements to the split-radix operation count by using multiplier coefficients or "twiddle factors" that are not n-th roots of unity for a size-n DFT. This paper presents a Boolean Satisfiability-based proof of the lowest operation count for certain classes of DFT algorithms. First, we present a novel way to choose new yet valid twiddle factors for the nodes in flowgraphs generated by common power-of-two fast Fourier transform algorithms, FFTs. With this new technique, we can generate a large family of FFTs realizable by a fixed flowgraph. This solution space of FFTs is cast as a Boolean Satisfiability problem, and a modern Satisfiability Modulo Theory solver is applied to search for FFTs requiring the fewest arithmetic operations. Surprisingly, we find that there are FFTs requiring fewer operations than the split-radix even when all twiddle factors are n-th roots of unity.
Heuristic Algorithm for Interpretation of Non-Atomic Categorical Attributes in Similarity-based Fuzzy Databases - Scalability Evaluation
Venue: arXiv cs.DB 2011
Year: 2011

In this work we are analyzing scalability of the heuristic algorithm we used in the past to discover knowledge from multi-valued symbolic attributes in fuzzy databases. The non-atomic descriptors, characterizing a single attribute of a database record, are commonly used in fuzzy databases to reflect uncertainty about the recorded observation. In this paper, we present implementation details and scalability tests of the algorithm, which we developed to precisely interpret such non-atomic values and to transfer (i.e. defuzzify) the fuzzy tuples to the forms acceptable for many regular (i.e. atomic values based) data mining algorithms. Important advantages of our approach are: (1) its linear scalability, and (2) its unique capability of incorporating background knowledge, implicitly stored in the fuzzy database models in the form of fuzzy similarity hierarchy, into the interpretation/defuzzification process.
Improved Edge Awareness in Discontinuity Preserving Smoothing
Venue: arXiv cs.CV 2011
Year: 2011

Discontinuity preserving smoothing is a fundamentally important procedure that is useful in a wide variety of image processing contexts. It is directly useful for noise reduction, and frequently used as an intermediate step in higher level algorithms. For example, it can be particularly useful in edge detection and segmentation. Three well known algorithms for discontinuity preserving smoothing are nonlinear anisotropic diffusion, bilateral filtering, and mean shift filtering. Although slight differences make them each better suited to different tasks, all are designed to preserve discontinuities while smoothing. However, none of them satisfy this goal perfectly: they each have exception cases in which smoothing may occur across hard edges. The principal contribution of this paper is the identification of a property we call edge awareness that should be satisfied by any discontinuity preserving smoothing algorithm. This constraint can be incorporated into existing algorithms to improve quality, and usually has negligible changes in runtime performance and/or complexity. We present modifications necessary to augment diffusion and mean shift, as well as a new formulation of the bilateral filter that unifies the spatial and range spaces to achieve edge awareness.
The FEM approach to the 3D electrodiffusion on 'meshes' optimized with the Metropolis algorithm
Venue: arXiv cs.CG 2011
Year: 2011

The presented article contains a 3D mesh generation routine optimized with the Metropolis algorithm. The procedure enables to produce meshes of a prescribed volume V_0 of elements. The finite volume meshes are used with the Finite Element approach. The FEM analysis enables to deal with a set of coupled nonlinear differential equations that describes the electrodiffusional problem. Mesh quality and accuracy of FEM solutions are also examined. High quality of FEM type space-dependent approximation and correctness of discrete approximation in time are ensured by finding solutions to the 3D Laplace problem and to the 3D diffusion equation, respectively. Their comparison with analytical solutions confirms accuracy of obtained approximations.
On Empirical Entropy
Venue: arXiv cs.IT 2011
Year: 2011

We propose a compression-based version of the empirical entropy of a finite string over a finite alphabet. Whereas previously one considers the naked entropy of (possibly higher order) Markov processes, we consider the sum of the description of the random variable involved plus the entropy it induces. We assume only that the distribution involved is computable. To test the new notion we compare the Normalized Information Distance (the similarity metric) with a related measure based on Mutual Information in Shannon's framework. This way the similarities and differences of the last two concepts are exposed.
Colorful Triangle Counting and a MapReduce Implementation
Venue: arXiv cs.DS 2011
Year: 2011

In this note we introduce a new randomized algorithm for counting triangles in graphs. We show that under mild conditions, the estimate of our algorithm is strongly concentrated around the true number of triangles. Specifically, if $p \geq \max{(\frac{Δ\log{n}}{t}, \frac{\log{n}}{\sqrt{t}})}$, where $n$, $t$, $Δ$ denote the number of vertices in $G$, the number of triangles in $G$, the maximum number of triangles an edge of $G$ is contained, then for any constant $ε>0$ our unbiased estimate $T$ is concentrated around its expectation, i.e., $ \Prob{|T - \Mean{T}| \geq ε\Mean{T}} = o(1)$. Finally, we present a \textsc{MapReduce} implementation of our algorithm.
Finding a smallest odd hole in a claw-free graph using global structure
Venue: arXiv cs.DM 2011
Year: 2011

A lemma of Fouquet implies that a claw-free graph contains an induced $C_5$, contains no odd hole, or is quasi-line. In this paper we use this result to give an improved shortest-odd-hole algorithm for claw-free graphs by exploiting the structural relationship between line graphs and quasi-line graphs suggested by Chudnovsky and Seymour's structure theorem for quasi-line graphs. Our approach involves reducing the problem to that of finding a shortest odd cycle of length $\geq 5$ in a graph. Our algorithm runs in $O(m^2+n^2\log n)$ time, improving upon Shrem, Stern, and Golumbic's recent $O(nm^2)$ algorithm, which uses a local approach. The best known recognition algorithms for claw-free graphs run in $O(m^{1.69}) \cap O(n^{3.5})$ time, or $O(m^2) \cap O(n^{3.5})$ without fast matrix multiplication.
Bayesian Mechanism Design for Budget-Constrained Agents
Venue: arXiv cs.GT 2011
Year: 2011

We study Bayesian mechanism design problems in settings where agents have budgets. Specifically, an agent's utility for an outcome is given by his value for the outcome minus any payment he makes to the mechanism, as long as the payment is below his budget, and is negative infinity otherwise. This discontinuity in the utility function presents a significant challenge in the design of good mechanisms, and classical "unconstrained" mechanisms fail to work in settings with budgets. The goal of this paper is to develop general reductions from budget-constrained Bayesian MD to unconstrained Bayesian MD with small loss in performance. We consider this question in the context of the two most well-studied objectives in mechanism design---social welfare and revenue---and present constant factor approximations in a number of settings. Some of our results extend to settings where budgets are private and agents need to be incentivized to reveal them truthfully.
Peer Effects and Stability in Matching Markets
Venue: arXiv cs.SI 2011
Year: 2011

Many-to-one matching markets exist in numerous different forms, such as college admissions, matching medical interns to hospitals for residencies, assigning housing to college students, and the classic firms and workers market. In all these markets, externalities such as complementarities and peer effects severely complicate the preference ordering of each agent. Further, research has shown that externalities lead to serious problems for market stability and for developing efficient algorithms to find stable matchings. In this paper we make the observation that peer effects are often the result of underlying social connections, and we explore a formulation of the many-to-one matching market where peer effects are derived from an underlying social network. The key feature of our model is that it captures peer effects and complementarities using utility functions, rather than traditional preference ordering. With this model and considering a weaker notion of stability, namely two-sided exchange stability, we prove that stable matchings always exist and characterize the set of stable matchings in terms of social welfare. We also give distributed algorithms that are guaranteed to converge to a two-sided exchange stable matching. To assess the competitive ratio of these algorithms and to more generally characterize the efficiency of matching markets with externalities, we provide general bounds on how far the welfare of the worst-case stable matching can be from the welfare of the optimal matching, and find that the structure of the social network (e.g. how well clustered the network is) plays a large role.
Optimisations for quadrature representations of finite element tensors through automated code generation
Venue: arXiv cs.MS 2011
Year: 2011

We examine aspects of the computation of finite element matrices and vectors which are made possible by automated code generation. Given a variational form in a syntax which resembles standard mathematical notation, the low-level computer code for building finite element tensors, typically matrices, vectors and scalars, can be generated automatically via a form compiler. In particular, the generation of code for computing finite element matrices using a quadrature approach is addressed. For quadrature representations, a number of optimisation strategies which are made possible by automated code generation are presented. The relative performance of two different automatically generated representations of finite element matrices is examined, with a particular emphasis on complicated variational forms. It is shown that approaches which perform best for simple forms are not tractable for more complicated problems in terms of run time performance, the time required to generate the code or the size of the generated code. The approach and optimisations elaborated here are effective for a range of variational forms.
Unstructured Geometric Multigrid in Two and Three Dimensions on Complex and Graded Meshes
Venue: arXiv cs.NA 2011
Year: 2011

The use of multigrid and related preconditioners with the finite element method is often limited by the difficulty of applying the algorithm effectively to a problem, especially when the domain has a complex shape or adaptive refinement. We introduce a simplification of a general topologically-motivated mesh coarsening algorithm for use in creating hierarchies of meshes for geometric unstructured multigrid methods. The connections between the guarantees of this technique and the quality criteria necessary for multigrid methods for non-quasi-uniform problems are noted. The implementation details, in particular those related to coarsening, remeshing, and interpolation, are discussed. Computational tests on pathological test cases from adaptive finite element methods show the performance of the technique.