OpenRaiser/Intern-Atlas huggingface dataset:
Finding top-k similar pairs of objects annotated with terms from an ontology
Venue: arXiv cs.DB 2010
Year: 2010

With the growing focus on semantic searches and interpretations, an increasing number of standardized vocabularies and ontologies are being designed and used to describe data. We investigate the querying of objects described by a tree-structured ontology. Specifically, we consider the case of finding the top-k best pairs of objects that have been annotated with terms from such an ontology when the object descriptions are available only at runtime. We consider three distance measures. The first one defines the object distance as the minimum pairwise distance between the sets of terms describing them, and the second one defines the distance as the average pairwise term distance. The third and most useful distance measure, earth mover's distance, finds the best way of matching the terms and computes the distance corresponding to this best matching. We develop lower bounds that can be aggregated progressively and utilize them to speed up the search for top-k object pairs when the earth mover's distance is used. For the minimum pairwise distance, we devise an algorithm that runs in O(D + Tk log k) time, where D is the total information size and T is the total number of terms in the ontology. We also develop a novel best-first search strategy for the average pairwise distance that utilizes lower bounds generated in an ordered manner. Experiments on real and synthetic datasets demonstrate the practicality and scalability of our algorithms.
Channel Polarization on q-ary Discrete Memoryless Channels by Arbitrary Kernels
Venue: arXiv cs.IT 2010
Year: 2010

A method of channel polarization, proposed by Arikan, allows us to construct efficient capacity-achieving channel codes. In the original work, binary input discrete memoryless channels are considered. A special case of $q$-ary channel polarization is considered by Sasoglu, Telatar, and Arikan. In this paper, we consider more general channel polarization on $q$-ary channels. We further show explicit constructions using Reed-Solomon codes, on which asymptotically fast channel polarization is induced.
Planar Visibility: Testing and Counting
Venue: arXiv cs.CG 2010
Year: 2010

In this paper we consider query versions of visibility testing and visibility counting. Let $S$ be a set of $n$ disjoint line segments in $\R^2$ and let $s$ be an element of $S$. Visibility testing is to preprocess $S$ so that we can quickly determine if $s$ is visible from a query point $q$. Visibility counting involves preprocessing $S$ so that one can quickly estimate the number of segments in $S$ visible from a query point $q$. We present several data structures for the two query problems. The structures build upon a result by O'Rourke and Suri (1984) who showed that the subset, $V_S(s)$, of $\R^2$ that is weakly visible from a segment $s$ can be represented as the union of a set, $C_S(s)$, of $O(n^2)$ triangles, even though the complexity of $V_S(s)$ can be $Ω(n^4)$. We define a variant of their covering, give efficient output-sensitive algorithms for computing it, and prove additional properties needed to obtain approximation bounds. Some of our bounds rely on a new combinatorial result that relates the number of segments of $S$ visible from a point $p$ to the number of triangles in $\bigcup_{s\in S} C_S(s)$ that contain $p$.
Universally Optimal Privacy Mechanisms for Minimax Agents
Venue: arXiv cs.CR 2010
Year: 2010

A scheme that publishes aggregate information about sensitive data must resolve the trade-off between utility to information consumers and privacy of the database participants. Differential privacy is a well-established definition of privacy--this is a universal guarantee against all attackers, whatever their side-information or intent. In this paper, we present a universal treatment of utility based on the standard minimax rule from decision theory (in contrast to the utility model in, which is Bayesian). In our model, information consumers are minimax (risk-averse) agents, each possessing some side-information about the query, and each endowed with a loss-function which models their tolerance to inaccuracies. Further, information consumers are rational in the sense that they actively combine information from the mechanism with their side-information in a way that minimizes their loss. Under this assumption of rational behavior, we show that for every fixed count query, a certain geometric mechanism is universally optimal for all minimax information consumers. Additionally, our solution makes it possible to release query results at multiple levels of privacy in a collusion-resistant manner.
A General Coding Scheme for Two-User Fading Interference Channels
Venue: arXiv cs.IT 2010
Year: 2010

A Han-Kobayashi based achievable scheme is presented for ergodic fading two-user Gaussian interference channels (IFCs) with perfect channel state information at all nodes and Gaussian codebooks with no time-sharing. Using max-min optimization techniques, it is shown that jointly coding across all states performs at least as well as separable coding for the sub-classes of uniformly weak (every sub-channel is weak) and hybrid (mix of strong and weak sub-channels that do not achieve the interference-free sum-capacity) IFCs. For the uniformly weak IFCs, sufficient conditions are obtained for which the sum-rate is maximized when interference is ignored at both receivers.
Towards Transactional Load over XtreemFS
Venue: arXiv cs.DC 2010
Year: 2010

We propose using trace-based assessment of the performance of distributed file systems (DFS) under transactional IO load. The assessment includes simulations and experiments using the IO traces. Our experiments suggest that DFS, and specifically XtreemFS have a good potential to support transactional IO load in distributed environments: they demonstrate good performance, high availability and scalability, while at the same time opening the way to TCO reduction.
Design and Analysis of Multi-User SDMA Systems with Noisy Limited CSIT Feedback
Venue: arXiv cs.IT 2010
Year: 2010

In this paper, we consider spatial-division multiple-access (SDMA) systems with one base station with multiple antennae and a number of single antenna mobiles under noisy limited CSIT feedback. We propose a robust noisy limited feedback design for SDMA systems. The solution consists of a real-time robust SDMA precoding, user selection and rate adaptation as well as an offline feedback index assignment algorithm. The index assignment problem is cast into a Traveling Sales Man problem (TSP). Based on the specific structure of the feedback constellation and the precoder, we derive a low complex but asymptotically optimal solution. Simulation results show that the proposed framework has significant goodput gain compared to the traditional naive designs under noisy limited feedback channel. Furthermore, we show that despite the noisy feedback channel, the average SDMA system goodput grows with the number of feedback bits in the interference limited regime while in noise limited regime increases linearly with the number of transmit antenna and the forward channel SNR.
Feature Extraction for Universal Hypothesis Testing via Rank-constrained Optimization
Venue: arXiv cs.IT 2010
Year: 2010

This paper concerns the construction of tests for universal hypothesis testing problems, in which the alternate hypothesis is poorly modeled and the observation space is large. The mismatched universal test is a feature-based technique for this purpose. In prior work it is shown that its finite-observation performance can be much better than the (optimal) Hoeffding test, and good performance depends crucially on the choice of features. The contributions of this paper include: 1) We obtain bounds on the number of εdistinguishable distributions in an exponential family. 2) This motivates a new framework for feature extraction, cast as a rank-constrained optimization problem. 3) We obtain a gradient-based algorithm to solve the rank-constrained optimization problem and prove its local convergence.
A Practical Dirty Paper Coding Applicable for Broadcast Channel
Venue: arXiv cs.IT 2010
Year: 2010

In this paper, we present a practical dirty paper coding scheme using trellis coded modulation for the dirty paper channel $Y=X+S+W,$ $\mathbb{E}\{X^2\} \leq P$, where $W$ is white Gaussian noise with power $σ_w ^2$, $P$ is the average transmit power and $S$ is the Gaussian interference with power $σ_s ^2$ that is non-causally known at the transmitter. We ensure that the dirt in our scheme remains distinguishable to the receiver and thus, our designed scheme is applicable to broadcast channel. Following Costa's idea, we recognize the criteria that the transmit signal must be as orthogonal to the dirt as possible. Finite constellation codes are constructed using trellis coded modulation and by using a Viterbi algorithm at the encoder so that the code satisfies the design criteria and simulation results are presented with codes constructed via trellis coded modulation using QAM signal sets to illustrate our results.
Recursive Secret Sharing for Distributed Storage and Information Hiding
Venue: arXiv cs.CR 2010
Year: 2010

This paper presents a recursive computational multi-secret sharing technique that hides k-2 secrets of size b each into n shares of a single secret S of size b, such that any k of the n shares suffice to recreate the secret S as well as all the hidden secrets. This may act as a steganographic channel to transmit hidden information or used for authentication and verification of shares and the secret itself. Further, such a recursive technique may be used as a computational secret sharing technique that has potential applications in secure and reliable storage of information on the Web, in sensor networks and information dispersal schemes. The presented technique, unlike previous computational techniques, does not require the use of any encryption key or storage of public information.
Adaptive resource allocation at the cell border using cooperative technique
Venue: arXiv cs.NI 2010
Year: 2010

The technique of cooperative communication has recently gained momentum in the research community; this technique utilizes the notion of relay, as an intermediate node between the source and the destination, to enhance the overall system performance. In this paper we ex-plored the benefits of adaptive cooperation, in which the relay adapts its relaying process in response to channel conditions and data priorities. We are particularly interested in applying this concept to the cell border situation, in which two mobile nodes acting as destinations com-municate with base stations (sources) through a relay. The adaptive cooperation is proposed here since the transmission channel conditions (Packet Error Rate for example) and data priori-ties are not the same for both mobiles. We show that using the adaptive resource allocation technique in combination with the cross layer design techniques, we can achieve Real-Time data constraints with no additional overhead.
Dirty Paper Coding using Sign-bit Shaping and LDPC Codes
Venue: arXiv cs.IT 2010
Year: 2010

Dirty paper coding (DPC) refers to methods for pre-subtraction of known interference at the transmitter of a multiuser communication system. There are numerous applications for DPC, including coding for broadcast channels. Recently, lattice-based coding techniques have provided several designs for DPC. In lattice-based DPC, there are two codes - a convolutional code that defines a lattice used for shaping and an error correction code used for channel coding. Several specific designs have been reported in the recent literature using convolutional and graph-based codes for capacity-approaching shaping and coding gains. In most of the reported designs, either the encoder works on a joint trellis of shaping and channel codes or the decoder requires iterations between the shaping and channel decoders. This results in high complexity of implementation. In this work, we present a lattice-based DPC scheme that provides good shaping and coding gains with moderate complexity at both the encoder and the decoder. We use a convolutional code for sign-bit shaping, and a low-density parity check (LDPC) code for channel coding. The crucial idea is the introduction of a one-codeword delay and careful parsing of the bits at the transmitter, which enable an LDPC decoder to be run first at the receiver. This provides gains without the need for iterations between the shaping and channel decoders. Simulation results confirm that at high rates the proposed DPC method performs close to capacity with moderate complexity. As an application of the proposed DPC method, we show a design for superposition coding that provides rates better than time-sharing over a Gaussian broadcast channel.
Mapping of SOA and RUP: DOA as Case Study
Venue: arXiv cs.SE 2010
Year: 2010

SOA (Service Oriented Architecture) is a new trend towards increasing the profit margins in an organization due to incorporating business services to business practices. Rational Unified Process (RUP) is a unified method planning form for large business applications that provides a language for describing method content and processes. The well defined mapping of SOA and RUP leads to successful completion of RUP software projects to provide services to their users. DOA (Digital Office Assistant) is a multi user SOA type application that provides appropriate viewer for each user to assist him through services. In this paper authors proposed the mapping strategy of SOA with RUP by considering DOA as case study.
Multicore Applications in Real Time Systems
Venue: arXiv cs.SE 2010
Year: 2010

Microprocessor roadmaps clearly show a trend towards multiple core CPUs. Modern operating systems already make use of these CPU architectures by distributing tasks between processing cores thereby increasing system performance. This review article highlights a brief introduction of what a multicore system is, the various methods adopted to program these systems and also the industrial application of these high speed systems.
Type-Safe Feature-Oriented Product Lines
Venue: arXiv cs.SE 2010
Year: 2010

A feature-oriented product line is a family of programs that share a common set of features. A feature implements a stakeholder's requirement, represents a design decision and configuration option and, when added to a program, involves the introduction of new structures, such as classes and methods, and the refinement of existing ones, such as extending methods. With feature-oriented decomposition, programs can be generated, solely on the basis of a user's selection of features, by the composition of the corresponding feature code. A key challenge of feature-oriented product line engineering is how to guarantee the correctness of an entire feature-oriented product line, i.e., of all of the member programs generated from different combinations of features. As the number of valid feature combinations grows progressively with the number of features, it is not feasible to check all individual programs. The only feasible approach is to have a type system check the entire code base of the feature-oriented product line. We have developed such a type system on the basis of a formal model of a feature-oriented Java-like language. We demonstrate that the type system ensures that every valid program of a feature-oriented product line is well-typed and that the type system is complete.
A Multicore Processor based Real-Time System for Automobile management application
Venue: arXiv cs.AR 2010
Year: 2010

In this paper we propose an Intelligent Management System which is capable of managing the automobile functions using the rigorous real-time principles and a multicore processor in order to realize higher efficiency and safety for the vehicle. It depicts how various automobile functionalities can be fine grained and treated to fit in real time concepts. It also shows how the modern multicore processors can be of good use in organizing vast amounts of correlated functions to be executed in real-time with excellent time commitments. The modeling of the automobile tasks with real time commitments, organizing appropriate scheduling for various real time tasks and the usage of a multicore processor enables the system to realize higher efficiency and offer better safety levels to the vehicle. The industry available real time operating system is used for scheduling various tasks and jobs on the multicore processor.
The effect of discrete vs. continuous-valued ratings on reputation and ranking systems
Venue: arXiv cs.IR 2010
Year: 2010

When users rate objects, a sophisticated algorithm that takes into account ability or reputation may produce a fairer or more accurate aggregation of ratings than the straightforward arithmetic average. Recently a number of authors have proposed different co-determination algorithms where estimates of user and object reputation are refined iteratively together, permitting accurate measures of both to be derived directly from the rating data. However, simulations demonstrating these methods' efficacy assumed a continuum of rating values, consistent with typical physical modelling practice, whereas in most actual rating systems only a limited range of discrete values (such as a 5-star system) is employed. We perform a comparative test of several co-determination algorithms with different scales of discrete ratings and show that this seemingly minor modification in fact has a significant impact on algorithms' performance. Paradoxically, where rating resolution is low, increased noise in users' ratings may even improve the overall performance of the system.
Enhancing Fine Motor Skills of Wards with Special Needs Using Cluster Model of Cognition
Venue: arXiv cs.CY 2010
Year: 2010

Technology offers great potential to overcome physical barriers of human race. This paper presents the methods of enhanced learning applicable to children having special needs using better human-computer interaction. The Audio-Visual (AV) effects that the graphic tools or animations help in achieving better learning, understanding, remembering and performance from such students. The 3L-R Cluster Program Model enable them to look into pictures and animated objects while listening to the related audio. It also motivates them to do the FMS development activities like drawing, coloring, tracing etc., certain types of games in the clustered model will help the children to improve concentration, thinking, reasoning, cognitive skills and the eye-to hand co-ordination. Here we introduced a novel cluster model along with the methodology described which provides an ample exposure to the effectiveness of the training. Classify the students with similar problems or disability and the associated curriculum of modified teaching methodology to meet their special needs is met through the specialized IT tool which form a part of the cluster model. It ensures effective learning in wards by enhancing multifaceted interaction. The main objective of this paper is to support the development of Fine Motor Skills (FMS) of wards with special needs.
Two-phase algorithms for the parametric shortest path problem
Venue: arXiv cs.CC 2010
Year: 2010

A {\em parametric weighted graph} is a graph whose edges are labeled with continuous real functions of a single common variable. For any instantiation of the variable, one obtains a standard edge-weighted graph. Parametric weighted graph problems are generalizations of weighted graph problems, and arise in various natural scenarios. Parametric weighted graph algorithms consist of two phases. A {\em preprocessing phase} whose input is a parametric weighted graph, and whose output is a data structure, the advice, that is later used by the {\em instantiation phase}, where a specific value for the variable is given. The instantiation phase outputs the solution to the (standard) weighted graph problem that arises from the instantiation. The goal is to have the running time of the instantiation phase supersede the running time of any algorithm that solves the weighted graph problem from scratch, by taking advantage of the advice. In this paper we construct several parametric algorithms for the shortest path problem. For the case of linear function weights we present an algorithm for the single source shortest path problem.
Improved Source Coding Exponents via Witsenhausen's Rate
Venue: arXiv cs.IT 2010
Year: 2010

We provide a novel upper-bound on Witsenhausen's rate, the rate required in the zero-error analogue of the Slepian-Wolf problem; our bound is given in terms of a new information-theoretic functional defined on a certain graph. We then use the functional to give a single letter lower-bound on the error exponent for the Slepian-Wolf problem under the vanishing error probability criterion, where the decoder has full (i.e. unencoded) side information. Our exponent stems from our new encoding scheme which makes use of source distribution only through the positions of the zeros in the `channel' matrix connecting the source with the side information, and in this sense is `semi-universal'. We demonstrate that our error exponent can beat the `expurgated' source-coding exponent of Csiszár and Körner, achievability of which requires the use of a non-universal maximum-likelihood decoder. An extension of our scheme to the lossy case (i.e. Wyner-Ziv) is given. For the case when the side information is a deterministic function of the source, the exponent of our improved scheme agrees with the sphere-packing bound exactly (thus determining the reliability function). An application of our functional to zero-error channel capacity is also given.
Approaches to Curriculum and Teaching Materials to Bring Out Better Skilled Software Engineers-An Indian Perspective
Venue: arXiv cs.CY 2010
Year: 2010

Development of Curriculum and delivery materials has undergone changes over a period of time, in undergraduate engineering degree system in Indian universities. However, there exists a gap between industry expectations in IT field and skills and knowledge that the graduating engineers possess and this continues to grow. A similar situation has been seen in the developed countries like USA, UK and Australia. Several researchers and practitioners have discussed and tried to come up with innovative approaches to teaching software engineering and IT as a whole. In India, it is of vital importance that steps be taken to address this issue seriously. This paper discusses some of the measures that have been implemented so that this gap is reduced and software engineers with better skills are produced. Changes to curriculum, industry-academia collaboration through conferences, sabbaticals etc., industry internships and live projects for final year students are some of the measures that have been discussed in this paper. The implementation of these measures may lead to fulfilling the growing requirement for skilled software engineers who can handle the industry challenges.