OpenRaiser/Intern-Atlas huggingface dataset:
Distributed Private Data Analysis: On Simultaneously Solving How and What
Venue: arXiv cs.CR 2011
Year: 2011

We examine the combination of two directions in the field of privacy concerning computations over distributed private inputs - secure function evaluation (SFE) and differential privacy. While in both the goal is to privately evaluate some function of the individual inputs, the privacy requirements are significantly different. The general feasibility results for SFE suggest a natural paradigm for implementing differentially private analyses distributively: First choose what to compute, i.e., a differentially private analysis; Then decide how to compute it, i.e., construct an SFE protocol for this analysis. We initiate an examination whether there are advantages to a paradigm where both decisions are made simultaneously. In particular, we investigate under which accuracy requirements it is beneficial to adapt this paradigm for computing a collection of functions including binary sum, gap threshold, and approximate median queries. Our results imply that when computing the binary sum of $n$ distributed inputs then: * When we require that the error is $o(\sqrt{n})$ and the number of rounds is constant, there is no benefit in the new paradigm. * When we allow an error of $O(\sqrt{n})$, the new paradigm yields more efficient protocols when we consider protocols that compute symmetric functions. Our results also yield new separations between the local and global models of computations for private data analysis.
Cost Analysis of Redundancy Schemes for Distributed Storage Systems
Venue: arXiv cs.DC 2011
Year: 2011

Distributed storage infrastructures require the use of data redundancy to achieve high data reliability. Unfortunately, the use of redundancy introduces storage and communication overheads, which can either reduce the overall storage capacity of the system or increase its costs. To mitigate the storage and communication overhead, different redundancy schemes have been proposed. However, due to the great variety of underlaying storage infrastructures and the different application needs, optimizing these redundancy schemes for each storage infrastructure is cumbersome. The lack of rules to determine the optimal level of redundancy for each storage configuration leads developers in industry to often choose simpler redundancy schemes, which are usually not the optimal ones. In this paper we analyze the cost of different redundancy schemes and derive a set of rules to determine which redundancy scheme minimizes the storage and the communication costs for a given system configuration. Additionally, we use simulation to show that theoretically-optimal schemes may not be viable in a realistic setting where nodes can go off-line and repairs may be delayed. In these cases, we identify which are the trade-offs between the storage and communication overheads of the redundancy scheme and its data reliability.
On Computational Power of Quantum Read-Once Branching Programs
Venue: arXiv cs.CC 2011
Year: 2011

In this paper we review our current results concerning the computational power of quantum read-once branching programs. First of all, based on the circuit presentation of quantum branching programs and our variant of quantum fingerprinting technique, we show that any Boolean function with linear polynomial presentation can be computed by a quantum read-once branching program using a relatively small (usually logarithmic in the size of input) number of qubits. Then we show that the described class of Boolean functions is closed under the polynomial projections.
Predicting User Preferences
Venue: arXiv cs.IR 2011
Year: 2011

The many metrics employed for the evaluation of search engine results have not themselves been conclusively evaluated. We propose a new measure for a metric's ability to identify user preference of result lists. Using this measure, we evaluate the metrics Discounted Cumulated Gain, Mean Average Precision and classical precision, finding that the former performs best. We also show that considering more results for a given query can impair rather than improve a metric's ability to predict user preferences.
A Characterization of all Stable Minimal Separator Graphs
Venue: arXiv cs.DM 2011
Year: 2011

In this paper, our goal is to characterize two graph classes based on the properties of minimal vertex (edge) separators. We first present a structural characterization of graphs in which every minimal vertex separator is a stable set. We show that such graphs are precisely those in which the induced subgraph, namely, a cycle with exactly one chord is forbidden. We also show that deciding maximum such forbidden subgraph is NP-complete by establishing a polynomial time reduction from maximum induced cycle problem [1]. This result is of independent interest and can be used in other combinatorial problems. Secondly, we prove that a graph has the following property: every minimal edge separator induces a matching (that is no two edges share a vertex in common) if and only if it is a tree.
On the Capacity of Memoryless Finite-State Multiple Access Channels with Asymmetric Noisy State Information at the Encoders
Venue: arXiv cs.IT 2011
Year: 2011

We consider the capacity of memoryless finite-state multiple access channel (FS-MAC) with causal asymmetric noisy state information available at both transmitters and complete state information available at the receiver. Single letter inner and outer bounds are provided for the capacity of such channels when the state process is independent and identically distributed. The outer bound is attained by observing that the proposed inner bound is tight for the sum-rate capacity.
Exploiting Interference Alignment in Multi-Cell Cooperative OFDMA Resource Allocation
Venue: arXiv cs.IT 2011
Year: 2011

This paper studies interference alignment (IA) based multi-cell cooperative resource allocation for the downlink OFDMA with universal frequency reuse. Unlike the traditional scheme that treats subcarriers as separate dimensions for resource allocation, the IA technique is utilized to enable frequency-domain precoding over parallel subcarriers. In this paper, the joint optimization of frequency-domain precoding via IA, subcarrier user selection and power allocation is investigated for a cooperative three-cell OFDMA system to maximize the downlink throughput. Numerical results for a simplified symmetric channel setup reveal that the IA-based scheme achieves notable throughput gains over the traditional scheme only when the inter-cell interference link has a comparable strength as the direct link, and the receiver SNR is sufficiently large. Motivated by this observation, a practical hybrid scheme is proposed for cellular systems with heterogenous channel conditions, where the total spectrum is divided into two subbands, over which the IAbased scheme and the traditional scheme are applied for resource allocation to users located in the cell-intersection region and cellnon- intersection region, respectively. It is shown that this hybrid resource allocation scheme flexibly exploits the downlink IA gains for OFDMA-based cellular systems.
Deterministic Bounds for Restricted Isometry of Compressed Sensing Matrices
Venue: arXiv cs.IT 2011
Year: 2011

Compressed Sensing (CS) is an emerging field that enables reconstruction of a sparse signal $x \in {\mathbb R} ^n$ that has only $k \ll n$ non-zero coefficients from a small number $m \ll n$ of linear projections. The projections are obtained by multiplying $x$ by a matrix $Φ\in {\mathbb R}^{m \times n}$ --- called a CS matrix --- where $k < m \ll n$. In this work, we ask the following question: given the triplet $\{k, m, n \}$ that defines the CS problem size, what are the deterministic limits on the performance of the best CS matrix in ${\mathbb R}^{m \times n}$? We select Restricted Isometry as the performance metric. We derive two deterministic converse bounds and one deterministic achievable bound on the Restricted Isometry for matrices in ${\mathbb R}^{m \times n}$ in terms of $n$, $m$ and $k$. The first converse bound (structural bound) is derived by exploiting the intricate relationships between the singular values of sub-matrices and the complete matrix. The second converse bound (packing bound) and the achievable bound (covering bound) are derived by recognizing the equivalence of CS matrices to codes on Grassmannian spaces. Simulations reveal that random Gaussian $Φ$ provide far from optimal performance. The derivation of the three bounds offers several new geometric insights that relate optimal CS matrices to equi-angular tight frames, the Welch bound, codes on Grassmannian spaces, and the Generalized Pythagorean Theorem (GPT).
Transient Stability Assessment of Smart Power System using Complex Networks Framework
Venue: arXiv cs.OH 2011
Year: 2011

In this paper, a new methodology for stability assessment of a smart power system is proposed. The key to this assessment is an index called betweenness index which is based on ideas from complex network theory. The proposed betweenness index is an improvement of previous works since it considers the actual real power flow through the transmission lines along the network. Furthermore, this work initiates a new area for complex system research to assess the stability of the power system.
An Integer Linear Programming Model for the Radiotherapy Treatment Scheduling Problem
Venue: arXiv cs.CE 2011
Year: 2011

Radiotherapy represents an important phase of treatment for a large number of cancer patients. It is essential that resources used to deliver this treatment are employed effectively. This paper presents a new integer linear programming model for real-world radiotherapy treatment scheduling and analyses the effectiveness of using this model on a daily basis in a hospital. Experiments are conducted varying the days on which schedules can be created. Results obtained using real-world data from the Nottingham University Hospitals NHS Trust, UK, are presented and show how the proposed model can be used with different policies in order to achieve good quality schedules.
Extraction of handwritten areas from colored image of bank checks by an hybrid method
Venue: arXiv cs.AI 2011
Year: 2011

One of the first step in the realization of an automatic system of check recognition is the extraction of the handwritten area. We propose in this paper an hybrid method to extract these areas. This method is based on digit recognition by Fourier descriptors and different steps of colored image processing . It requires the bank recognition of its code which is located in the check marking band as well as the handwritten color recognition by the method of difference of histograms. The areas extraction is then carried out by the use of some mathematical morphology tools.
Degrees of Freedom of a Communication Channel and Kolmogorov numbers
Venue: arXiv cs.IT 2011
Year: 2011

In this note, we show that the operator theoretic concept of Kolmogorov numbers and the number of degrees of freedom at level $ε$ of a communication channel are closely related. Linear communication channels may be modeled using linear compact operators on Banach or Hilbert spaces and the number of degrees of freedom of such channels is defined to be the number of linearly independent signals that may be communicated over this channel, where the channel is restricted by a threshold noise level. Kolmogorov numbers are a particular example of $s$-numbers, which are defined over the class of bounded operators between Banach spaces. We demonstrate that these two concepts are closely related, namely that the Kolmogorov numbers correspond to the "jump points" in the function relating numbers of degrees of freedom with the noise level $ε$. We also establish a useful numerical computation result for evaluating Kolmogorov numbers of compact operators.
Easy Impossibility Proofs for k-Set Agreement in Message Passing Systems
Venue: arXiv cs.DC 2011
Year: 2011

Despite of being quite similar agreement problems, consensus and general k-set agreement require surprisingly different techniques for proving the impossibility in asynchronous systems with crash failures: Rather than relatively simple bivalence arguments as in the impossibility proof for consensus (= 1-set agreement) in the presence of a single crash failure, known proofs for the impossibility of k-set agreement in systems with at least k>1 crash failures use algebraic topology or a variant of Sperner's Lemma. In this paper, we present a generic theorem for proving the impossibility of k-set agreement in various message passing settings, which is based on a simple reduction to the consensus impossibility in a certain subsystem. We demonstrate the broad applicability of our result by exploring the possibility/impossibility border of k-set agreement in several message-passing system models: (i) asynchronous systems with crash failures, (ii) partially synchronous processes with (initial) crash failures, and (iii) asynchronous systems augmented with failure detectors. In (i) and (ii), the impossibility part is just an instantiation of our main theorem, whereas the possibility of achieving k-set agreement in (ii) follows by generalizing the consensus algorithm for initial crashes by Fisher, Lynch and Patterson. In (iii), applying our technique yields the exact border for the parameter k where k-set agreement is solvable with the failure detector class (Sigma_k,Omega_k), for (1<= k<= n-1), of Bonnet and Raynal. Considering that Sigma_k was shown to be necessary for solving k-set agreement, this result yields new insights on the quest for the weakest failure detector.
Subclasses of Normal Helly Circular-Arc Graphs
Venue: arXiv cs.DM 2011
Year: 2011

A Helly circular-arc model M = (C,A) is a circle C together with a Helly family \A of arcs of C. If no arc is contained in any other, then M is a proper Helly circular-arc model, if every arc has the same length, then M is a unit Helly circular-arc model, and if there are no two arcs covering the circle, then M is a normal Helly circular-arc model. A Helly (resp. proper Helly, unit Helly, normal Helly) circular-arc graph is the intersection graph of the arcs of a Helly (resp. proper Helly, unit Helly, normal Helly) circular-arc model. In this article we study these subclasses of Helly circular-arc graphs. We show natural generalizations of several properties of (proper) interval graphs that hold for some of these Helly circular-arc subclasses. Next, we describe characterizations for the subclasses of Helly circular-arc graphs, including forbidden induced subgraphs characterizations. These characterizations lead to efficient algorithms for recognizing graphs within these classes. Finally, we show how do these classes of graphs relate with straight and round digraphs.
Refining Recency Search Results with User Click Feedback
Venue: arXiv cs.IR 2011
Year: 2011

Traditional machine-learned ranking systems for web search are often trained to capture stationary relevance of documents to queries, which has limited ability to track non-stationary user intention in a timely manner. In recency search, for instance, the relevance of documents to a query on breaking news often changes significantly over time, requiring effective adaptation to user intention. In this paper, we focus on recency search and study a number of algorithms to improve ranking results by leveraging user click feedback. Our contributions are three-fold. First, we use real search sessions collected in a random exploration bucket for \emph{reliable} offline evaluation of these algorithms, which provides an unbiased comparison across algorithms without online bucket tests. Second, we propose a re-ranking approach to improve search results for recency queries using user clicks. Third, our empirical comparison of a dozen algorithms on real-life search data suggests importance of a few algorithmic choices in these applications, including generalization across different query-document pairs, specialization to popular queries, and real-time adaptation of user clicks.
On the Scalability of Multidimensional Databases
Venue: arXiv cs.DB 2011
Year: 2011

It is commonly accepted in the practice of on-line analytical processing of databases that the multidimensional database organization is less scalable than the relational one. It is easy to see that the size of the multidimensional organization may increase very quickly. For example, if we introduce one additional dimension, then the total number of possible cells will be at least doubled. However, this reasoning does not takethe fact into account that the multidimensional organization can be compressed. There are compression techniques, which can remove all or at least a part of the empty cells from the multidimensional organization, while maintaining a good retrieval performance. Relational databases often use B-tree indices to speed up the access to given rows of tables. It can be proven, under some reasonable assumptions, that the total size of the table and the B-tree index is bigger than a compressed multidimensional representation. This implies that the compressed array results in a smaller database and faster access at the same time. This paper compares several compression techniques and shows when we should and should not apply compressed arrays instead of relational tables.
SafeZone: A Hierarchical Inter-Domain Authenticated Source Address Validation Solution
Venue: arXiv cs.NI 2011
Year: 2011

Next generation Internet is highly concerned about the issue of reliability. Principally, the foundation of reliability is authentication of the source IP address. With the signature-and-verification based defense mechanisms available today, unfortunately, there is a lack of hierarchical architecture, which makes the structure of the trust alliance excessively flat and single. Moreover, with the increasing scale of the trust alliance, costs of validation grow so quickly that they do not adapt to incremental deployment. Via comparison with traditional solutions, this article proposes a hierarchical, inter-domain authenticated source address validation solution named SafeZone. SafeZone employs two intelligent designs, lightweight tag replacement and a hierarchical partitioning scheme, each of which helps to ensure that SafeZone can construct trustworthy and hierarchical trust alliances without the negative influences and complex operations on de facto networks. Extensive experiments also indicate that SafeZone can effectively obtain the design goals of a hierarchical architecture, along with lightweight, loose coupling and "multi-fence support" and as well as an incremental deployment scheme.
Composition of Management System for Smart Homes
Venue: arXiv cs.SE 2011
Year: 2011

The paper addresses modular hierarchical design (composition) of a management system for smart homes. The management system consists of security subsystem (access control, alarm control), comfort subsystem (temperature, etc.), intelligence subsystem (multimedia, houseware). The design solving process is based on Hierarchical Morphological Multicriteria Design (HMMD) approach: (1) design of a tree-like system model, (2) generation of design alternatives for leaf nodes of the system model, (3) Bottom-Up process: (i) multicriteria selection of design alternatives for system parts/components and (ii) composing the selected alternatives into a resultant combination (while taking into account ordinal quality of the alternatives above and their compatibility). A realistic numerical example illustrates the design process of a management system for smart homes.
Product Constructions for Perfect Lee Codes
Venue: arXiv cs.IT 2011
Year: 2011

A well known conjecture of Golomb and Welch is that the only nontrivial perfect codes in the Lee and Manhattan metrics have length two or minimum distance three. This problem and related topics were subject for extensive research in the last forty years. In this paper two product constructions for perfect Lee codes and diameter perfect Lee codes are presented. These constructions yield a large number of nonlinear perfect codes and nonlinear diameter perfect codes in the Lee and Manhattan metrics. A short survey and other related problems on perfect codes in the Lee and the Manhattan metrics are also discussed.
Non-Price Equilibria in Markets of Discrete Goods
Venue: arXiv cs.GT 2011
Year: 2011

We study markets of indivisible items in which price-based (Walrasian) equilibria often do not exist due to the discrete non-convex setting. Instead we consider Nash equilibria of the market viewed as a game, where players bid for items, and where the highest bidder on an item wins it and pays his bid. We first observe that pure Nash-equilibria of this game excatly correspond to price-based equilibiria (and thus need not exist), but that mixed-Nash equilibria always do exist, and we analyze their structure in several simple cases where no price-based equilibrium exists. We also undertake an analysis of the welfare properties of these equilibria showing that while pure equilibria are always perfectly efficient ("first welfare theorem"), mixed equilibria need not be, and we provide upper and lower bounds on their amount of inefficiency.
Efficient Resource Oblivious Algorithms for Multicores
Venue: arXiv cs.DC 2011
Year: 2011

We consider the design of efficient algorithms for a multicore computing environment with a global shared memory and p cores, each having a cache of size M, and with data organized in blocks of size B. We characterize the class of `Hierarchical Balanced Parallel (HBP)' multithreaded computations for multicores. HBP computations are similar to the hierarchical divide & conquer algorithms considered in recent work, but have some additional features that guarantee good performance even when accounting for the cache misses due to false sharing. Most of our HBP algorithms are derived from known cache-oblivious algorithms with high parallelism, however we incorporate new techniques that reduce the effect of false-sharing. Our approach to addressing false sharing costs (or more generally, block misses) is to ensure that any task that can be stolen shares O(1) blocks with other tasks. We use a gapping technique for computations that have larger than O(1) block sharing. We also incorporate the property of limited access writes analyzed in a companion paper, and we bound the cost of accessing shared blocks on the execution stacks of tasks. We present the Priority Work Stealing (PWS) scheduler, and we establish that, given a sufficiently `tall' cache, PWS deterministically schedules several highly parallel HBP algorithms, including those for scans, matrix computations and FFT, with cache misses bounded by the sequential complexity, when accounting for both traditional cache misses and for false sharing. We also present a list ranking algorithm with almost optimal bounds. PWS schedules without using cache or block size information, and uses knowledge of processors only to the extent of determining the available locations from which tasks may be stolen; thus it schedules resource-obliviously.
Universal Metadata Standard
Venue: arXiv cs.DL 2011
Year: 2011

The creation of a next generation internet (semantic web) is impossible without attributes, allowing the semantic association of documents and their integration into information context. To achieve these goals, the Universal Metadata Standard (ums) may be an ultimative tool, which could serve as a basis for documentography, and is functionally required for interpretation of documents by the automatic operating systems.
Multiply-Recursive Upper Bounds with Higman's Lemma
Venue: arXiv cs.LO 2011
Year: 2011

We develop a new analysis for the length of controlled bad sequences in well-quasi-orderings based on Higman's Lemma. This leads to tight multiply-recursive upper bounds that readily apply to several verification algorithms for well-structured systems.