OpenRaiser/Intern-Atlas huggingface dataset:
Priority Based Dynamic Round Robin (PBDRR) Algorithm with Intelligent Time Slice for Soft Real Time Systems
Venue: arXiv cs.OS 2011
Year: 2011

In this paper, a new variant of Round Robin (RR) algorithm is proposed which is suitable for soft real time systems. RR algorithm performs optimally in timeshared systems, but it is not suitable for soft real time systems. Because it gives more number of context switches, larger waiting time and larger response time. We have proposed a novel algorithm, known as Priority Based Dynamic Round Robin Algorithm(PBDRR),which calculates intelligent time slice for individual processes and changes after every round of execution. The proposed scheduling algorithm is developed by taking dynamic time quantum concept into account. Our experimental results show that our proposed algorithm performs better than algorithm in [8] in terms of reducing the number of context switches, average waiting time and average turnaround time.
User Mode Memory Page Allocation: A Silver Bullet For Memory Allocation?
Venue: arXiv cs.OS 2011
Year: 2011

This paper proposes a novel solution: the elimination of paged virtual memory and partial outsourcing of memory page allocation and manipulation from the operating system kernel into the individual process' user space - a user mode page allocator - which allows an application to have direct, bare metal access to the page mappings used by the hardware Memory Management Unit (MMU) for its part of the overall address space. A user mode page allocator based emulation of the mmap() abstraction layer of dlmalloc is then benchmarked against the traditional kernel mode implemented mmap() in a series of synthetic Monte-Carlo and real world application settings. Given the superb synthetic and positive real world results from the profiling conducted, this paper proposes that with proper operating system and API support one could gain a further order higher performance again while keeping allocator performance invariant to the amount of memory being allocated or freed i.e. a 100x performance improvement or more in some common use cases. It is rare that through a simple and easy to implement API and operating system structure change one can gain a Silver Bullet with the potential for a second one.
Securing The Kernel via Static Binary Rewriting and Program Shepherding
Venue: arXiv cs.CR 2011
Year: 2011

Recent Microsoft security bulletins show that kernel vulnerabilities are becoming more and more important security threats. Despite the pretty extensive security mitigations many of the kernel vulnerabilities are still exploitable. Successful kernel exploitation typically grants the attacker maximum privilege level and results in total machine compromise. To protect against kernel exploitation, we have developed a tool which statically rewrites the Microsoft Windows kernel as well as other kernel level modules. Such rewritten binary files allow us to monitor control flow transfers during operating system execution. At this point we are able to detect whether selected control transfer flow is valid or should be considered as an attack attempt. Our solution is especially directed towards preventing remote kernel exploitation attempts. Additionally, many of the local privilege escalation attacks are also blocked (also due to additional mitigation techniques we have implemented). Our tool was tested with Microsoft Windows XP, Windows Vista and Windows 7 (under both virtual and physical machines) on IA-32 compatible processors. Our apparatus is also completely standalone and does not require any third party software.
Convergence Analysis of Differential Evolution Variants on Unconstrained Global Optimization Functions
Venue: arXiv cs.NE 2011
Year: 2011

In this paper, we present an empirical study on convergence nature of Differential Evolution (DE) variants to solve unconstrained global optimization problems. The aim is to identify the competitive nature of DE variants in solving the problem at their hand and compare. We have chosen fourteen benchmark functions grouped by feature: unimodal and separable, unimodal and nonseparable, multimodal and separable, and multimodal and nonseparable. Fourteen variants of DE were implemented and tested on fourteen benchmark problems for dimensions of 30. The competitiveness of the variants are identified by the Mean Objective Function value, they achieved in 100 runs. The convergence nature of the best and worst performing variants are analyzed by measuring their Convergence Speed (Cs) and Quality Measure (Qm).
A Step-indexed Semantic Model of Types for the Call-by-Name Lambda Calculus
Venue: arXiv cs.PL 2011
Year: 2011

Step-indexed semantic models of types were proposed as an alternative to purely syntactic safety proofs using subject-reduction. Building upon the work by Appel and others, we introduce a generalized step-indexed model for the call-by-name lambda calculus. We also show how to prove type safety of general recursion in our call-by-name model.
Potential Games for Energy-Efficient Resource Allocation in Multipoint-to-Multipoint CDMA Wireless Data Networks
Venue: arXiv cs.IT 2011
Year: 2011

The problem of noncooperative resource allocation in a multipoint-to-multipoint cellular network is considered in this paper. The considered scenario is general enough to represent several key instances of modern wireless networks such as a multicellular network, a peer-to-peer network (interference channel), and a wireless network equipped with femtocells. In particular, the problem of joint transmit waveforms adaptation, linear receiver design, and transmit power control is examined. Several utility functions to be maximized are considered, and, among them, we cite the received SINR, and the transmitter energy efficiency, which is measured in bit/Joule, and represents the number of successfully delivered bits for each energy unit used for transmission. Resorting to the theory of potential games, noncooperative games admitting Nash equilibria in multipoint-to-multipoint cellular networks regardless of the channel coefficient realizations are designed. Computer simulations confirm that the considered games are convergent, and show the huge benefits that resource allocation schemes can bring to the performance of wireless data networks.
Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time
Venue: arXiv cs.DM 2011
Year: 2011

We give an O(n log^3 n) algorithm that, given an n-node directed planar graph with arc capacities, a set of source nodes, and a set of sink nodes, finds a maximum flow from the sources to the sinks. Previously, the fastest algorithms known for this problem were those for general graphs.
Learning content similarity for music recommendation
Venue: arXiv cs.MM 2011
Year: 2011

Many tasks in music information retrieval, such as recommendation, and playlist generation for online radio, fall naturally into the query-by-example setting, wherein a user queries the system by providing a song, and the system responds with a list of relevant or similar song recommendations. Such applications ultimately depend on the notion of similarity between items to produce high-quality results. Current state-of-the-art systems employ collaborative filter methods to represent musical items, effectively comparing items in terms of their constituent users. While collaborative filter techniques perform well when historical data is available for each item, their reliance on historical data impedes performance on novel or unpopular items. To combat this problem, practitioners rely on content-based similarity, which naturally extends to novel items, but is typically out-performed by collaborative filter methods. In this article, we propose a method for optimizing contentbased similarity by learning from a sample of collaborative filter data. The optimized content-based similarity metric can then be applied to answer queries on novel and unpopular items, while still maintaining high recommendation accuracy. The proposed system yields accurate and efficient representations of audio content, and experimental results show significant improvements in accuracy over competing content-based recommendation techniques.
A standard form for generator matrices with respect to the Niederreiter-Rosenbloom-Tsfasman metric
Venue: arXiv cs.IT 2011
Year: 2011

In this note, we present an analogue for codes in vector spaces with a Rosenbloom-Tsfasman metric of the well-known standard form of generator matrices for codes in spaces with the Hamming metric.
Workload Classification & Software Energy Measurement for Efficient Scheduling on Private Cloud Platforms
Venue: arXiv cs.DC 2011
Year: 2011

At present there are a number of barriers to creating an energy efficient workload scheduler for a Private Cloud based data center. Firstly, the relationship between different workloads and power consumption must be investigated. Secondly, current hardware-based solutions to providing energy usage statistics are unsuitable in warehouse scale data centers where low cost and scalability are desirable properties. In this paper we discuss the effect of different workloads on server power consumption in a Private Cloud platform. We display a noticeable difference in energy consumption when servers are given tasks that dominate various resources (CPU, Memory, Hard Disk and Network). We then use this insight to develop CloudMonitor, a software utility that is capable of >95% accurate power predictions from monitoring resource consumption of workloads, after a "training phase" in which a dynamic power model is developed.
Optimal Upper and Lower Bounds for Boolean Expressions by Dissociation
Venue: arXiv cs.AI 2011
Year: 2011

This paper develops upper and lower bounds for the probability of Boolean expressions by treating multiple occurrences of variables as independent and assigning them new individual probabilities. Our technique generalizes and extends the underlying idea of a number of recent approaches which are varyingly called node splitting, variable renaming, variable splitting, or dissociation for probabilistic databases. We prove that the probabilities we assign to new variables are the best possible in some sense.
Improving Usability of Interactive Graphics Specification and Implementation with Picking Views and Inverse Transformations
Venue: arXiv cs.HC 2011
Year: 2011

Specifying and programming graphical interactions are difficult tasks, notably because designers have difficulties to express the dynamics of the interaction. This paper shows how the MDPC architecture improves the usability of the specification and the implementation of graphical interaction. The architecture is based on the use of picking views and inverse transforms from the graphics to the data. With three examples of graphical interaction, we show how to express them with the architecture, how to implement them, and how this improves programming usability. Moreover, we show that it enables implementing graphical interaction without a scene graph. This kind of code prevents from errors due to cache consistency management.
Interactive Overlays: A New Method for Generating Global Journal Maps from Web-of-Science Data
Venue: arXiv cs.DL 2011
Year: 2011

Recent advances in methods and techniques enable us to develop an interactive overlay to the global map of science based on aggregated citation relations among the 9,162 journals contained in the Science Citation Index and Social Science Citation Index 2009 combined. The resulting mapping is provided by VOSViewer. We first discuss the pros and cons of the various options: cited versus citing, multidimensional scaling versus spring-embedded algorithms, VOSViewer versus Gephi, and the various clustering algorithms and similarity criteria. Our approach focuses on the positions of journals in the multidimensional space spanned by the aggregated journal-journal citations. A number of choices can be left to the user, but we provide default options reflecting our preferences. Some examples are also provided; for example, the potential of using this technique to assess the interdisciplinarity of organizations and/or document sets.
Universality of citation distributions revisited
Venue: arXiv cs.DL 2011
Year: 2011

Radicchi, Fortunato, and Castellano [arXiv:0806.0974, PNAS 105(45), 17268] claim that, apart from a scaling factor, all fields of science are characterized by the same citation distribution. We present a large-scale validation study of this universality-of-citation-distributions claim. Our analysis shows that claiming citation distributions to be universal for all fields of science is not warranted. Although many fields indeed seem to have fairly similar citation distributions, there are quite some exceptions as well. We also briefly discuss the consequences of our findings for the measurement of scientific impact using citation-based bibliometric indicators.
Invitation to Algorithmic Uses of Inclusion-Exclusion
Venue: arXiv cs.DS 2011
Year: 2011

I give an introduction to algorithmic uses of the principle of inclusion-exclusion. The presentation is intended to be be concrete and accessible, at the expense of generality and comprehensiveness.
Graphical model approximations of random finite set filters
Venue: arXiv cs.SY 2011
Year: 2011

Random finite sets (RFSs) has been a fruitful area of research in recent years, yielding new approximate filters such as the probability hypothesis density (PHD), cardinalised PHD (CPHD), and multiple target multi-Bernoulli (MeMBer). These new methods have largely been based on approximations that side-step the need for measurement-to-track association. Comparably, RFS methods that incorporate data association, such as Morelande and Challa's (M-C) method, have received little attention. This paper provides a RFS algorithm that incorporates data association similarly to the M-C method, but retains computational tractability via a recently developed approximation of marginal association weights. We describe an efficient method for resolving the track coalescence phenomenon which is problematic for joint probabilistic data association (JPDA) and related methods (including M-C). The method utilises a network flow optimisation, and thus is tractable for large numbers of targets. Finally, our derivation also shows that it is natural for the multi-target density to incorporate both a Poisson point process (PPP) component (representing targets that have never been detected) and a multi-Bernoulli component (representing targets under track). We describe a method of recycling, in which tracks with a low probability existence are transferred from the multi-Bernoulli component to the PPP component, effectively yielding a hybrid of M-C and PHD.
Visibility-preserving convexifications using single-vertex moves
Venue: arXiv cs.CG 2011
Year: 2011

Devadoss asked: (1) can every polygon be convexified so that no internal visibility (between vertices) is lost in the process? Moreover, (2) does such a convexification exist, in which exactly one vertex is moved at a time (that is, using {\em single-vertex moves})? We prove the redundancy of the "single-vertex moves" condition: an affirmative answer to (1) implies an affirmative answer to (2). Since Aichholzer et al. recently proved (1), this settles (2).
Book review: Katy Börner, Atlas of Science: Visualizing What We Know. Cambridge, MA/ London UK: The MIT Press, 2010
Venue: arXiv cs.OH 2011
Year: 2011

Katy Börner has written a wonderful book about visualization that makes our field of scientometrics accessible to much larger audiences. The book is to be read in relation to the ongoing series of exhibitions entitled "Places & Spaces: Mapping Science" currently touring the world. The book also provides the scholarly background to the exhibitions. It celebrates scientometrics as the discipline in the background that enables us to visualize the evolution of knowledge as the acumen of human civilization.
Behavior of Graph Laplacians on Manifolds with Boundary
Venue: arXiv cs.LG 2011
Year: 2011

In manifold learning, algorithms based on graph Laplacians constructed from data have received considerable attention both in practical applications and theoretical analysis. In particular, the convergence of graph Laplacians obtained from sampled data to certain continuous operators has become an active research topic recently. Most of the existing work has been done under the assumption that the data is sampled from a manifold without boundary or that the functions of interests are evaluated at a point away from the boundary. However, the question of boundary behavior is of considerable practical and theoretical interest. In this paper we provide an analysis of the behavior of graph Laplacians at a point near or on the boundary, discuss their convergence rates and their implications and provide some numerical results. It turns out that while points near the boundary occupy only a small part of the total volume of a manifold, the behavior of graph Laplacian there has different scaling properties from its behavior elsewhere on the manifold, with global effects on the whole manifold, an observation with potentially important implications for the general problem of learning on manifolds.
Human Identity Verification based on Heart Sounds: Recent Advances and Future Directions
Venue: arXiv cs.CV 2011
Year: 2011

Identity verification is an increasingly important process in our daily lives, and biometric recognition is a natural solution to the authentication problem. One of the most important research directions in the field of biometrics is the characterization of novel biometric traits that can be used in conjunction with other traits, to limit their shortcomings or to enhance their performance. The aim of this work is to introduce the reader to the usage of heart sounds for biometric recognition, describing the strengths and the weaknesses of this novel trait and analyzing in detail the methods developed so far by different research groups and their performance.
On A Semi-Automatic Method for Generating Composition Tables
Venue: arXiv cs.AI 2011
Year: 2011

Originating from Allen's Interval Algebra, composition-based reasoning has been widely acknowledged as the most popular reasoning technique in qualitative spatial and temporal reasoning. Given a qualitative calculus (i.e. a relation model), the first thing we should do is to establish its composition table (CT). In the past three decades, such work is usually done manually. This is undesirable and error-prone, given that the calculus may contain tens or hundreds of basic relations. Computing the correct CT has been identified by Tony Cohn as a challenge for computer scientists in 1995. This paper addresses this problem and introduces a semi-automatic method to compute the CT by randomly generating triples of elements. For several important qualitative calculi, our method can establish the correct CT in a reasonable short time. This is illustrated by applications to the Interval Algebra, the Region Connection Calculus RCC-8, the INDU calculus, and the Oriented Point Relation Algebras. Our method can also be used to generate CTs for customised qualitative calculi defined on restricted domains.
Approximating subset $k$-connectivity problems
Venue: arXiv cs.DS 2011
Year: 2011

A subset $T \subseteq V$ of terminals is $k$-connected to a root $s$ in a directed/undirected graph $J$ if $J$ has $k$ internally-disjoint $vs$-paths for every $v \in T$; $T$ is $k$-connected in $J$ if $T$ is $k$-connected to every $s \in T$. We consider the {\sf Subset $k$-Connectivity Augmentation} problem: given a graph $G=(V,E)$ with edge/node-costs, node subset $T \subseteq V$, and a subgraph $J=(V,E_J)$ of $G$ such that $T$ is $k$-connected in $J$, find a minimum-cost augmenting edge-set $F \subseteq E \setminus E_J$ such that $T$ is $(k+1)$-connected in $J \cup F$. The problem admits trivial ratio $O(|T|^2)$. We consider the case $|T|>k$ and prove that for directed/undirected graphs and edge/node-costs, a $ρ$-approximation for {\sf Rooted Subset $k$-Connectivity Augmentation} implies the following ratios for {\sf Subset $k$-Connectivity Augmentation}: (i) $b(ρ+k) + {(\frac{3|T|}{|T|-k})}^2 H(\frac{3|T|}{|T|-k})$; (ii) $ρ\cdot O(\frac{|T|}{|T|-k} \log k)$, where b=1 for undirected graphs and b=2 for directed graphs, and $H(k)$ is the $k$th harmonic number. The best known values of $ρ$ on undirected graphs are $\min\{|T|,O(k)\}$ for edge-costs and $\min\{|T|,O(k \log |T|)\}$ for node-costs; for directed graphs $ρ=|T|$ for both versions. Our results imply that unless $k=|T|-o(|T|)$, {\sf Subset $k$-Connectivity Augmentation} admits the same ratios as the best known ones for the rooted version. This improves the ratios in \cite{N-focs,L}.
Synthesizing Products for Online Catalogs
Venue: arXiv cs.DB 2011
Year: 2011

A high-quality, comprehensive product catalog is essential to the success of Product Search engines and shopping sites such as Yahoo! Shopping, Google Product Search or Bing Shopping. But keeping catalogs up-to-date becomes a challenging task, calling for the need of automated techniques. In this paper, we introduce the problem of product synthesis, a key component of catalog creation and maintenance. Given a set of offers advertised by merchants, the goal is to identify new products and add them to the catalog together with their (structured) attributes. A fundamental challenge is the scale of the problem: a Product Search engine receives data from thousands of merchants and millions of products; the product taxonomy contains thousands of categories, where each category comes in a different schema; and merchants use representations for products that are different from the ones used in the catalog of the Product Search engine. We propose a system that provides an end-to-end solution to the product synthesis problem, and includes components for extraction, and addresses issues involved in data extraction from offers, schema reconciliation, and data fusion. We developed a novel and scalable technique for schema matching which leverages knowledge about previously-known instance-level associations between offers and products; and it is trained using automatically created training sets (no manually-labeled data is needed). We present an experimental evaluation of our system using data from Bing Shopping for more than 800K offers, a thousand merchants, and 400 categories. The evaluation confirms that our approach is able to automatically generate a large number of accurate product specifications, and that our schema reconciliation component outperforms state-of-the-art schema matching techniques in terms of precision and recall.
Social content matching in MapReduce
Venue: arXiv cs.SI 2011
Year: 2011

Matching problems are ubiquitous. They occur in economic markets, labor markets, internet advertising, and elsewhere. In this paper we focus on an application of matching for social media. Our goal is to distribute content from information suppliers to information consumers. We seek to maximize the overall relevance of the matched content from suppliers to consumers while regulating the overall activity, e.g., ensuring that no consumer is overwhelmed with data and that all suppliers have chances to deliver their content. We propose two matching algorithms, GreedyMR and StackMR, geared for the MapReduce paradigm. Both algorithms have provable approximation guarantees, and in practice they produce high-quality solutions. While both algorithms scale extremely well, we can show that StackMR requires only a poly-logarithmic number of MapReduce steps, making it an attractive option for applications with very large datasets. We experimentally show the trade-offs between quality and efficiency of our solutions on two large datasets coming from real-world social-media web sites.