OpenRaiser/Intern-Atlas huggingface dataset:
Pipage Rounding, Pessimistic Estimators and Matrix Concentration
Venue: arXiv cs.DS 2013
Year: 2013

Pipage rounding is a dependent random sampling technique that has several interesting properties and diverse applications. One property that has been particularly useful is negative correlation of the resulting vector. Unfortunately negative correlation has its limitations, and there are some further desirable properties that do not seem to follow from existing techniques. In particular, recent concentration results for sums of independent random matrices are not known to extend to a negatively dependent setting. We introduce a simple but useful technique called concavity of pessimistic estimators. This technique allows us to show concentration of submodular functions and concentration of matrix sums under pipage rounding. The former result answers a question of Chekuri et al. (2009). To prove the latter result, we derive a new variant of Lieb's celebrated concavity theorem in matrix analysis. We provide numerous applications of these results. One is to spectrally-thin trees, a spectral analog of the thin trees that played a crucial role in the recent breakthrough on the asymmetric traveling salesman problem. We show a polynomial time algorithm that, given a graph where every edge has effective conductance at least $κ$, returns an $O(κ^{-1} \cdot \log n / \log \log n)$-spectrally-thin tree. There are further applications to rounding of semidefinite programs, to the column subset selection problem, and to a geometric question of extracting a nearly-orthonormal basis from an isotropic distribution.
The Irreducible Spine(s) of Undirected Networks
Venue: arXiv cs.DM 2013
Year: 2013

Using closure concepts, we show that within every undirected network, or graph, there is a unique irreducible subgraph which we call its "spine". The chordless cycles which comprise this irreducible core effectively characterize the connectivity structure of the network as a whole. In particular, it is shown that the center of the network, whether defined by distance or betweenness centrality, is effectively contained in this spine. By counting the number of cycles of length 3 <= k <= max_length, we can also create a kind of signature that can be used to identify the network. Performance is analyzed, and the concepts we develop are illurstrated by means of a relatively small running sample network of about 400 nodes.
Les index pour les entrepôts de données : comparaison entre index arbre-B et Bitmap
Venue: arXiv cs.DB 2013
Year: 2013

With the development of decision systems and specially data warehouses, the visibility of the data warehouse design before its creation has become essential, and that because of data warehouse importance as considered as the unique data source giving meaning to the decision. In a decision system the proper functioning of a data warehouse resides in the smooth running of the middleware tools ETC step one hand, and the restitution step through the data mining, reporting solutions, dashboards... etc other. The large volume of data that passes through these stages require an optimal design for a highly efficient decision system, without disregarding the choice of technologies that are introduced for the data warehouse implementation such as: database management system, the type of server operating systems, physical server architecture (64-bit, for example) that can be a benefit performance of this system. The designer of the data warehouse should consider the effectiveness of data query, this depends on the selection of relevant indexes and their combination with the materialized views, note that the index selection is a NPcomplete problem, because the number of indexes is exponential in the total number of attributes in the database, So, it is necessary to provide, while the data warehouse design, the suitable type of index for this data warehouse. This paper presents a comparative study between the index B-tree type and type Bitmap, their advantages and disadvantages, with a real experiment showing that its index of type Bitmap more advantageous than the index B-tree type.
Text Categorization via Similarity Search: An Efficient and Effective Novel Algorithm
Venue: arXiv cs.IR 2013
Year: 2013

We present a supervised learning algorithm for text categorization which has brought the team of authors the 2nd place in the text categorization division of the 2012 Cybersecurity Data Mining Competition (CDMC'2012) and a 3rd prize overall. The algorithm is quite different from existing approaches in that it is based on similarity search in the metric space of measure distributions on the dictionary. At the preprocessing stage, given a labeled learning sample of texts, we associate to every class label (document category) a point in the space of question. Unlike it is usual in clustering, this point is not a centroid of the category but rather an outlier, a uniform measure distribution on a selection of domain-specific words. At the execution stage, an unlabeled text is assigned a text category as defined by the closest labeled neighbour to the point representing the frequency distribution of the words in the text. The algorithm is both effective and efficient, as further confirmed by experiments on the Reuters 21578 dataset.
BGP Security in Partial Deployment: Is the Juice Worth the Squeeze?
Venue: arXiv cs.NI 2013
Year: 2013

As the rollout of secure route origin authentication with the RPKI slowly gains traction among network operators, there is a push to standardize secure path validation for BGP (i.e., S*BGP: S-BGP, soBGP, BGPSEC, etc.). Origin authentication already does much to improve routing security. Moreover, the transition to S*BGP is expected to be long and slow, with S*BGP coexisting in "partial deployment" alongside BGP for a long time. We therefore use theoretical and experimental approach to study the security benefits provided by partially-deployed S*BGP, vis-a-vis those already provided by origin authentication. Because routing policies have a profound impact on routing security, we use a survey of 100 network operators to find the policies that are likely to be most popular during partial S*BGP deployment. We find that S*BGP provides only meagre benefits over origin authentication when these popular policies are used. We also study the security benefits of other routing policies, provide prescriptive guidelines for partially-deployed S*BGP, and show how interactions between S*BGP and BGP can introduce new vulnerabilities into the routing system.
Kinetic Data Structures for the Semi-Yao Graph and All Nearest Neighbors in R^d
Venue: arXiv cs.CG 2013
Year: 2013

This paper presents a simple kinetic data structure for maintaining all the nearest neighbors of a set of $n$ moving points in $\mathbb{R}^d$, where the trajectory of each point is an algebraic function of at most constant degree $s$. The approach is based on maintaining the edges of the Semi-Yao graph, a sparse graph whose edge set includes the pairs of nearest neighbors as a subset. Our kinetic data structure (KDS) for maintaining all the nearest neighbors is deterministic. It processes $O(n^2β_{2s+2}^2(n)\log n)$ events with a total cost of $O(n^2β_{2s+2}(n)\log^{d+1} n)$. Here, $β_s(n)$ is an extremely slow-growing function. The best previous KDS for all the nearest neighbors in $ \mathbb{R}^d$ is by Agarwal, Kaplan, and Sharir (TALG 2008). It is a randomized result. Our structure and analysis are simpler than theirs. Also, we improve their result by a factor of $\log^d n$ in the number of events and by a $\log n$ factor in the total cost. This paper generalizes and improves the 2013 work of Rahmati, King and Whitesides (SoCG 2013) on maintaining the Semi-Yao graph in $\mathbb{R}^2$; its new technique provides the first KDS for the Semi-Yao graph in $\mathbb{R}^d$. Our KDS is local in the worst case, meaning that only a constant number of events is associated with any one point at any time. For maintaining all the nearest neighbors, neither our KDS nor the KDS by Agarwal~\etal~is local, and furthermore, each event in our KDS and in their KDS is handled in polylogarithmic time in an amortized sense. Finally, in this paper, we also give a KDS for maintenance of all the $(1+ε)$-nearest neighbors which is local and each event can be handled in a polylogarithmic worst-case time.
The technique of in-place associative sorting
Venue: arXiv cs.DS 2013
Year: 2013

In the first place, a novel, yet straightforward in-place integer value-sorting algorithm is presented. It sorts in linear time using constant amount of additional memory for storing counters and indices beside the input array. The technique is inspired from the principal idea behind one of the ordinal theories of "serial order in behavior" and explained by the analogy with the three main stages in the formation and retrieval of memory in cognitive neuroscience: (i) practicing, (ii) storage and (iii) retrieval. It is further improved in terms of time complexity as well as specialized for distinct integers, though still improper for rank-sorting. Afterwards, another novel, yet straightforward technique is introduced which makes this efficient value-sorting technique proper for rank-sorting. Hence, given an array of n elements each have an integer key, the technique sorts the elements according to their integer keys in linear time using only constant amount of additional memory. The devised technique is very practical and efficient outperforming bucket sort, distribution counting sort and address calculation sort family of algorithms making it attractive in almost every case even when space is not a critical resource.
Cake Cutting Algorithms for Piecewise Constant and Piecewise Uniform Valuations
Venue: arXiv cs.GT 2013
Year: 2013

Cake cutting is one of the most fundamental settings in fair division and mechanism design without money. In this paper, we consider different levels of three fundamental goals in cake cutting: fairness, Pareto optimality, and strategyproofness. In particular, we present robust versions of envy-freeness and proportionality that are not only stronger than their standard counter-parts but also have less information requirements. We then focus on cake cutting with piecewise constant valuations and present three desirable algorithms: CCEA (Controlled Cake Eating Algorithm), MEA (Market Equilibrium Algorithm) and CSD (Constrained Serial Dictatorship). CCEA is polynomial-time, robust envy-free, and non-wasteful. It relies on parametric network flows and recent generalizations of the probabilistic serial algorithm. For the subdomain of piecewise uniform valuations, we show that it is also group-strategyproof. Then, we show that there exists an algorithm (MEA) that is polynomial-time, envy-free, proportional, and Pareto optimal. MEA is based on computing a market-based equilibrium via a convex program and relies on the results of Reijnierse and Potters [24] and Devanur et al. [15]. Moreover, we show that MEA and CCEA are equivalent to mechanism 1 of Chen et. al. [12] for piecewise uniform valuations. We then present an algorithm CSD and a way to implement it via randomization that satisfies strategyproofness in expectation, robust proportionality, and unanimity for piecewise constant valuations. For the case of two agents, it is robust envy-free, robust proportional, strategyproof, and polynomial-time. Many of our results extend to more general settings in cake cutting that allow for variable claims and initial endowments. We also show a few impossibility results to complement our algorithms.
Generating Stack-based Access Control Policies
Venue: arXiv cs.CR 2013
Year: 2013

The stack-based access control mechanism plays a fundamental role in the security architecture of Java and Microsoft CLR (common language runtime). It is enforced at runtime by inspecting methods in the current call stack for granted permissions before the program performs safety-critical operations. Although stack inspection is well studied, there is relatively little work on automated generation of access control policies, and most existing work on inferring security policies assume the permissions to be checked at stack inspection points are known beforehand. Practiced approaches to generating access control policies are still manually done by developers based on domain-specific knowledges and trial-and-error testing. In this paper, we present a systematic approach to automated generation of access control policies for Java programs that necessarily ensure the program to pass stack inspection. The techniques are abstract interpretation based context-sensitive static program analyses. Our analysis models the program by combining a context-sensitive call graph with a dependency graph. We are hereby able to precisely identify permission requirements at stack inspection points, which are usually ignored in previous study.
Accuracy of MAP segmentation with hidden Potts and Markov mesh prior models via Path Constrained Viterbi Training, Iterated Conditional Modes and Graph Cut based algorithms
Venue: arXiv cs.LG 2013
Year: 2013

In this paper, we study statistical classification accuracy of two different Markov field environments for pixelwise image segmentation, considering the labels of the image as hidden states and solving the estimation of such labels as a solution of the MAP equation. The emission distribution is assumed the same in all models, and the difference lays in the Markovian prior hypothesis made over the labeling random field. The a priori labeling knowledge will be modeled with a) a second order anisotropic Markov Mesh and b) a classical isotropic Potts model. Under such models, we will consider three different segmentation procedures, 2D Path Constrained Viterbi training for the Hidden Markov Mesh, a Graph Cut based segmentation for the first order isotropic Potts model, and ICM (Iterated Conditional Modes) for the second order isotropic Potts model. We provide a unified view of all three methods, and investigate goodness of fit for classification, studying the influence of parameter estimation, computational gain, and extent of automation in the statistical measures Overall Accuracy, Relative Improvement and Kappa coefficient, allowing robust and accurate statistical analysis on synthetic and real-life experimental data coming from the field of Dental Diagnostic Radiography. All algorithms, using the learned parameters, generate good segmentations with little interaction when the images have a clear multimodal histogram. Suboptimal learning proves to be frail in the case of non-distinctive modes, which limits the complexity of usable models, and hence the achievable error rate as well. All Matlab code written is provided in a toolbox available for download from our website, following the Reproducible Research Paradigm.
Integrity Verification for Outsourcing Uncertain Frequent Itemset Mining
Venue: arXiv cs.DB 2013
Year: 2013

In recent years, due to the wide applications of uncertain data (e.g., noisy data), uncertain frequent itemsets (UFI) mining over uncertain databases has attracted much attention, which differs from the corresponding deterministic problem from the generalized definition and resolutions. As the most costly task in association rule mining process, it has been shown that outsourcing this task to a service provider (e.g.,the third cloud party) brings several benefits to the data owner such as cost relief and a less commitment to storage and computational resources. However, the correctness integrity of mining results can be corrupted if the service provider is with random fault or not honest (e.g., lazy, malicious, etc). Therefore, in this paper, we focus on the integrity and verification issue in UFI mining problem during outsourcing process, i.e., how the data owner verifies the mining results. Specifically, we explore and extend the existing work on deterministic FI outsourcing verification to uncertain scenario. For this purpose, We extend the existing outsourcing FI mining work to uncertain area w.r.t. the two popular UFI definition criteria and the approximate UFI mining methods. Specifically, We construct and improve the basic/enhanced verification scheme with such different UFI definition respectively. After that, we further discuss the scenario of existing approximation UFP mining, where we can see that our technique can provide good probabilistic guarantees about the correctness of the verification. Finally, we present the comparisons and analysis on the schemes proposed in this paper.
CMOS Low Power Cell Library For Digital Design
Venue: arXiv cs.OH 2013
Year: 2013

Historically, VLSI designers have focused on increasing the speed and reducing the area of digital systems. However, the evolution of portable systems and advanced Deep Sub-Micron fabrication technologies have brought power dissipation as another critical design factor. Low power design reduces cooling cost and increases reliability especially for high density systems. Moreover, it reduces the weight and size of portable devices. The power dissipation in CMOS circuits consists of static and dynamic components. Since dynamic power is proportional to V2 dd and static power is proportional to Vdd, lowering the supply voltage and device dimensions, the transistor threshold voltage also has to be scaled down to achieve the required performance. In case of static power, the power is consumed during the steady state condition i.e when there are no input/output transitions. Static power has two sources: DC power and Leakage power. Consecutively to facilitate voltage scaling without disturbing the performance, threshold voltage has to be minimized. Furthermore it leads to better noise margins and helps to avoid the hot carrier effects in short channel devices. In this paper we have been proposed the new CMOS library for the complex digital design using scaling the supply voltage and device dimensions and also suggest the methods to control the leakage current to obtain the minimum power dissipation at optimum value of supply voltage and transistor threshold. In this paper CMOS Cell library has been implemented using TSMC (0.18um) and TSMC (90nm) technology using HEP2 tool of IC designing from Mentor Graphics for various analysis and simulations.
Comparison of secure and high capacity color image steganography techniques in RGB and YCbCr domains
Venue: arXiv cs.MM 2013
Year: 2013

Steganography is one of the methods used for secret communication. Steganography attempts to hide the existence of the information. The object used to hide the secret information is called as cover object. Images are the most popular cover objects used for steganography. Different techniques have to be used for color image steganography and grey scale image steganography since they are stored in different ways. Color image are normally stored with 24 bit depth and grey scale images are stored with 8 bit depth. Color images can hold large amount of secret information since they have three color components. Different color spaces namely RGB (Red Green Blue), HSV (Hue, Saturation, Value), YUV, YIQ, YCbCr (Luminance, Chrominance) etc. are used to represent color images. Color image steganography can be done in any color space domain. In this paper color image steganography in RGB and YCbCr domain are compared. The secret information considered is grey scale image. Since RGB is the common method of representation, hiding secret information in this format is not secure.
Contrast Enhancement And Brightness Preservation Using Multi- Decomposition Histogram Equalization
Venue: arXiv cs.CV 2013
Year: 2013

Histogram Equalization (HE) has been an essential addition to the Image Enhancement world. Enhancement techniques like Classical Histogram Equalization (CHE), Adaptive Histogram Equalization (ADHE), Bi-Histogram Equalization (BHE) and Recursive Mean Separate Histogram Equalization (RMSHE) methods enhance contrast, however, brightness is not well preserved with these methods, which gives an unpleasant look to the final image obtained. Thus, we introduce a novel technique Multi-Decomposition Histogram Equalization (MDHE) to eliminate the drawbacks of the earlier methods. In MDHE, we have decomposed the input sixty-four parts, applied CHE in each of the sub-images and then finally interpolated them in correct order. The final image after MDHE results in contrast enhanced and brightness preserved image compared to all other techniques mentioned above. We have calculated the various parameters like PSNR, SNR, RMSE, MSE, etc. for every technique. Our results are well supported by bar graphs, histograms and the parameter calculations at the end.
On Minimizing Base Station Power Consumption
Venue: arXiv cs.IT 2013
Year: 2013

We consider resource allocation over a wireless downlink where Base Station (BS) power consumption is minimized while upholding a set of required link rates. A Power and Resource Allocation Including Sleep (PRAIS) method is proposed that combines resource sharing, Power Control (PC), and Discontinuous Transmission (DTX), such that downlink power consumption is minimized, which can be formed into a convex optimization problem. Unlike conventional approaches that aim at minimizing transmit power, in this work the BS mains supply power is chosen as the relevant metric. Based on a linear power model, which maps a certain transmit power to the necessary mains supply power, we quantify the fundamental limits of PRAIS in terms of achievable BS power savings. The fundamental limits are numerically evaluated on link level for four sets of BS power model parameters representative of envisaged future hardware developments. We establish an expected lower limit for PRAIS of 27W to 68W depending on load per link for BSs installed in 2014, which provides a 61% to 34% gain over conventional resource allocation schemes.
Perfect Codes in the Discrete Simplex
Venue: arXiv cs.IT 2013
Year: 2013

We study the problem of existence of (nontrivial) perfect codes in the discrete $ n $-simplex $ Δ_{\ell}^n := \left\{ \begin{pmatrix} x_0, \ldots, x_n \end{pmatrix} : x_i \in \mathbb{Z}_{+}, \sum_i x_i = \ell \right\} $ under $ \ell_1 $ metric. The problem is motivated by the so-called multiset codes, which have recently been introduced by the authors as appropriate constructs for error correction in the permutation channels. It is shown that $ e $-perfect codes in the $ 1 $-simplex $ Δ_{\ell}^1 $ exist for any $ \ell \geq 2e + 1 $, the $ 2 $-simplex $ Δ_{\ell}^2 $ admits an $ e $-perfect code if and only if $ \ell = 3e + 1 $, while there are no perfect codes in higher-dimensional simplices. In other words, perfect multiset codes exist only over binary and ternary alphabets.
Supporting Therapeutic Relationships and Communication about Mental Health
Venue: arXiv cs.HC 2013
Year: 2013

Effective communication and strong therapeutic relationships are critical to successful mental health interventions. For example, in 1957 Carl Rogers, a pioneer of person-centred therapy, proposed that an empowering relationship could, in and of itself, create the necessary and sufficient conditions for positive therapeutic outcomes [1]. Whilst modern psychological theories no longer favour an exclusive focus on relationships, positive relationships and the dynamics of client-therapist communication remain cornerstones of mental health intervention theories. A more recent meta-review concluded that across all interventions models, irrespective of the theoretical approach, the quality of the relationship between therapists and clients is the second leading determinant of successful clinical outcomes [2]. Over the past ten years we (David Coyle and Gavin Doherty) have designed and evaluated a wide range to systems that provide support for psychological (or talk- based) mental health interventions [3]. Here we briefly consider two recent examples. In each case our aim was to enhance communication and reshape clinical practice in a manner that empowers patients. gNats Island is a computer game that supports face-to-face interventions for adolescents [4]. MindBalance is an online treatment programme for adults experiencing difficulties with depression [5].