OpenRaiser/Intern-Atlas huggingface dataset:
GROTESQUE: Noisy Group Testing (Quick and Efficient)
Venue: arXiv cs.IT 2013
Year: 2013

Group-testing refers to the problem of identifying (with high probability) a (small) subset of $D$ defectives from a (large) set of $N$ items via a "small" number of "pooled" tests. For ease of presentation in this work we focus on the regime when $D = \cO{N^{1-\gap}}$ for some $\gap > 0$. The tests may be noiseless or noisy, and the testing procedure may be adaptive (the pool defining a test may depend on the outcome of a previous test), or non-adaptive (each test is performed independent of the outcome of other tests). A rich body of literature demonstrates that $Θ(D\log(N))$ tests are information-theoretically necessary and sufficient for the group-testing problem, and provides algorithms that achieve this performance. However, it is only recently that reconstruction algorithms with computational complexity that is sub-linear in $N$ have started being investigated (recent work by \cite{GurI:04,IndN:10, NgoP:11} gave some of the first such algorithms). In the scenario with adaptive tests with noisy outcomes, we present the first scheme that is simultaneously order-optimal (up to small constant factors) in both the number of tests and the decoding complexity ($\cO{D\log(N)}$ in both the performance metrics). The total number of stages of our adaptive algorithm is "small" ($\cO{\log(D)}$). Similarly, in the scenario with non-adaptive tests with noisy outcomes, we present the first scheme that is simultaneously near-optimal in both the number of tests and the decoding complexity (via an algorithm that requires $\cO{D\log(D)\log(N)}$ tests and has a decoding complexity of {${\cal O}(D(\log N+\log^{2}D))$}. Finally, we present an adaptive algorithm that only requires 2 stages, and for which both the number of tests and the decoding complexity scale as {${\cal O}(D(\log N+\log^{2}D))$}. For all three settings the probability of error of our algorithms scales as $\cO{1/(poly(D)}$.
Design of One-Dimensional Linear Phase Digital IIR Filters Using Orthogonal Polynomials
Venue: arXiv cs.OH 2013
Year: 2013

In the present paper, we discuss a method to design a linear phase 1-dimensional Infinite Impulse Response (IIR) filter using orthogonal polynomials. The filter is designed using a set of object functions. These object functions are realized using a set of orthogonal polynomials. The method includes placement of zeros and poles in such a way that the amplitude characteristics are not changed while we change the phase characteristics of the resulting IIR filter.
Tractable Combinations of Global Constraints
Venue: arXiv cs.AI 2013
Year: 2013

We study the complexity of constraint satisfaction problems involving global constraints, i.e., special-purpose constraints provided by a solver and represented implicitly by a parametrised algorithm. Such constraints are widely used; indeed, they are one of the key reasons for the success of constraint programming in solving real-world problems. Previous work has focused on the development of efficient propagators for individual constraints. In this paper, we identify a new tractable class of constraint problems involving global constraints of unbounded arity. To do so, we combine structural restrictions with the observation that some important types of global constraint do not distinguish between large classes of equivalent solutions.
Conversion of Braille to Text in English, Hindi and Tamil Languages
Venue: arXiv cs.CV 2013
Year: 2013

The Braille system has been used by the visually impaired for reading and writing. Due to limited availability of the Braille text books an efficient usage of the books becomes a necessity. This paper proposes a method to convert a scanned Braille document to text which can be read out to many through the computer. The Braille documents are pre processed to enhance the dots and reduce the noise. The Braille cells are segmented and the dots from each cell is extracted and converted in to a number sequence. These are mapped to the appropriate alphabets of the language. The converted text is spoken out through a speech synthesizer. The paper also provides a mechanism to type the Braille characters through the number pad of the keyboard. The typed Braille character is mapped to the alphabet and spoken out. The Braille cell has a standard representation but the mapping differs for each language. In this paper mapping of English, Hindi and Tamil are considered.
Routing in Wireless Mesh Networks: Two Soft Computing Based Approaches
Venue: arXiv cs.NI 2013
Year: 2013

Due to dynamic network conditions, routing is the most critical part in WMNs and needs to be optimised. The routing strategies developed for WMNs must be efficient to make it an operationally self configurable network. Thus we need to resort to near shortest path evaluation. This lays down the requirement of some soft computing approaches such that a near shortest path is available in an affordable computing time. This paper proposes a Fuzzy Logic based integrated cost measure in terms of delay, throughput and jitter. Based upon this distance (cost) between two adjacent nodes we evaluate minimal shortest path that updates routing tables. We apply two recent soft computing approaches namely Big Bang Big Crunch (BB-BC) and Biogeography Based Optimization (BBO) approaches to enumerate shortest or near short paths. BB-BC theory is related with the evolution of the universe whereas BBO is inspired by dynamical equilibrium in the number of species on an island. Both the algorithms have low computational time and high convergence speed. Simulation results show that the proposed routing algorithms find the optimal shortest path taking into account three most important parameters of network dynamics. It has been further observed that for the shortest path problem BB-BC outperforms BBO in terms of speed and percent error between the evaluated minimal path and the actual shortest path.
Context-based Barrier Notification Service Toward Outdoor Support for the Elderly
Venue: arXiv cs.CY 2013
Year: 2013

Aging society has been becoming a global problem not only in advanced countries. Under such circumstances, it is said that participation of elderly people in social activities is highly desirable from various perspectives including decrease of social welfare costs. Thus, we propose a mobile service that notifies barrier information nearby users outside to lowers the anxiety of elderly people and promote their social activities. There are barrier free maps in some areas, but those are static and updated annually at the earliest. However, there exist temporary barriers like road repairing and parked bicycles, and also every barrier is not for every elder person. That is, the elder people are under several conditions and wills to go out, so that a barrier for an elder person is not necessarily the one for the other. Therefore, we first collect the barrier information in the user participatory manner and select the ones the user need to know, then timely provide them via a mobile phone equipped with GPS. This paper shows the public experiment that we conducted in Tokyo, and confirms the usability and the accuracy of the information filtering.
Designing a Network Based System for Delivery of Remote Mine Services
Venue: arXiv cs.HC 2013
Year: 2013

There is a great body of work in the areas of tele-assistance/tele-collaboration offering novel and effective ways to improve collaboration between personnel located at a remote mine site and off-site personnel located in major metropolitan areas. Much of this work involves the use of high-bandwidth communications or targeted sensory experiences using large format displays. There are also existing remote access technologies but these suffer from limited functionality (providing text, voice, video or one-way desktop sharing), are often poorly supported in the security-conscious corporate environment and require complicated set up processes. There is currently no singular piece of remote collaboration technology that is suitable for the delivery of high-quality planning and scheduling services to clients at a mining site from a remote operating centre. In response to this issue, as part of a research and technology development effort between CSIRO and a mining engineering firm, we have developed a concept of remote mining engineer (RME) and conducted a functional requirements analysis for delivering mining engineering services to mine sites remotely. Based on the obtained requirements, a further study was performed to characterise existing technologies and to identify the scope for future work in designing and prototyping a network based system for RME. We report on the method and findings of this study in this paper.
Design and Implementation of Car Parking System on FPGA
Venue: arXiv cs.OH 2013
Year: 2013

As, the number of vehicles are increased day by day in rapid manner. It causes the problem of traffic congestion, pollution (noise and air). To overcome this problem A FPGA based parking system has been proposed. In this paper, parking system is implemented using Finite State Machine modelling. The system has two main modules i.e. identification module and slot checking module. Identification module identifies the visitor. Slot checking module checks the slot status. These modules are modeled in HDL and implemented on FPGA. A prototype of parking system is designed with various interfaces like sensor interfacing, stepper motor and LCD.
Towards a Good ABS Design for more Reliable Vehicles on the Roads
Venue: arXiv cs.SE 2013
Year: 2013

Nowadays, better driving also means better braking. To this end, vehicle designers must find all failures during the design phase of antilock braking systems which play an important role in automobiles safety. However, mechatronic systems are so complex and failures can be badly identified. So it is necessary to propose a design approach of an antilock braking system which will be able to avoid wheels locking during braking and maintain vehicle stability. This paper describes this approach, in which we model the functional and the dysfunctional behavior of an antilock braking system using stopwatch Petri nets.
Artificial Intelligence MArkup Language: A Brief Tutorial
Venue: arXiv cs.AI 2013
Year: 2013

The purpose of this paper is to serve as a reference guide for the development of chatterbots implemented with the AIML language. In order to achieve this, the main concepts in Pattern Recognition area are described because the AIML uses such theoretical framework in their syntactic and semantic structures. After that, AIML language is described and each AIML command/tag is followed by an application example. Also, the usage of AIML embedded tags for the handling of sequence dialogue limitations between humans and machines is shown. Finally, computer systems that assist in the design of chatterbots with the AIML language are classified and described.
Minimizing Base Station Power Consumption
Venue: arXiv cs.IT 2013
Year: 2013

We propose a new radio resource management algorithm which aims at minimizing the base station supply power consumption for multi-user MIMO-OFDM. Given a base station power model that establishes a relation between the RF transmit power and the supply power consumption, the algorithm optimizes the trade-off between three basic power-saving mechanisms: antenna adaptation, power control and discontinuous transmission. The algorithm comprises two steps: a) the first step estimates sleep mode duration, resource shares and antenna configuration based on average channel conditions and b) the second step exploits instantaneous channel knowledge at the transmitter for frequency selective time-variant channels. The proposed algorithm finds the number of transmit antennas, the RF transmission power per resource unit and spatial channel, the number of discontinuous transmission time slots, and the multi-user resource allocation, such that supply power consumption is minimized. Simulation results indicate that the proposed algorithm is capable of reducing the supply power consumption by between 25% and 40%, dependend on the system load.
Online Independent Set Beyond the Worst-Case: Secretaries, Prophets, and Periods
Venue: arXiv cs.DS 2013
Year: 2013

We investigate online algorithms for maximum (weight) independent set on graph classes with bounded inductive independence number like, e.g., interval and disk graphs with applications to, e.g., task scheduling and spectrum allocation. In the online setting, it is assumed that nodes of an unknown graph arrive one by one over time. An online algorithm has to decide whether an arriving node should be included into the independent set. Unfortunately, this natural and practically relevant online problem cannot be studied in a meaningful way within a classical competitive analysis as the competitive ratio on worst-case input sequences is lower bounded by $Ω(n)$. As a worst-case analysis is pointless, we study online independent set in a stochastic analysis. Instead of focussing on a particular stochastic input model, we present a generic sampling approach that enables us to devise online algorithms achieving performance guarantees for a variety of input models. In particular, our analysis covers stochastic input models like the secretary model, in which an adversarial graph is presented in random order, and the prophet-inequality model, in which a randomly generated graph is presented in adversarial order. Our sampling approach bridges thus between stochastic input models of quite different nature. In addition, we show that our approach can be applied to a practically motivated admission control setting. Our sampling approach yields an online algorithm for maximum independent set with competitive ratio $O(ρ^2)$ with respect to all of the mentioned stochastic input models. for graph classes with inductive independence number $ρ$. The approach can be extended towards maximum-weight independent set by losing only a factor of $O(\log n)$ in the competitive ratio with $n$ denoting the (expected) number of nodes.
Indexed Induction and Coinduction, Fibrationally
Venue: arXiv cs.LO 2013
Year: 2013

This paper extends the fibrational approach to induction and coinduction pioneered by Hermida and Jacobs, and developed by the current authors, in two key directions. First, we present a dual to the sound induction rule for inductive types that we developed previously. That is, we present a sound coinduction rule for any data type arising as the carrier of the final coalgebra of a functor, thus relaxing Hermida and Jacobs' restriction to polynomial functors. To achieve this we introduce the notion of a quotient category with equality (QCE) that i) abstracts the standard notion of a fibration of relations constructed from a given fibration; and ii) plays a role in the theory of coinduction dual to that played by a comprehension category with unit (CCU) in the theory of induction. Secondly, we show that inductive and coinductive indexed types also admit sound induction and coinduction rules. Indexed data types often arise as carriers of initial algebras and final coalgebras of functors on slice categories, so we give sufficient conditions under which we can construct, from a CCU (QCE) U:E \rightarrow B, a fibration with base B/I that models indexing by I and is also a CCU (resp., QCE). We finish the paper by considering the more general case of sound induction and coinduction rules for indexed data types when the indexing is itself given by a fibration.
An imporved decentralized approach for tracking multiple mobile targets through ZigBee WSNs
Venue: arXiv cs.NI 2013
Year: 2013

Target localization and tracking problems in WSNs have received considerable attention recently, driven by the requirement to achieve high localization accuracy, with the minimum cost possible. In WSN based tracking applications, it is critical to know the current location of any sensor node with the minimum energy consumed. This paper focuses on the energy consumption issue in terms of communication between nodes whenever the localization information is transmitted to a sink node. Tracking through WSNs can be categorized into centralized and decentralized systems. Decentralized systems offer low power consumption when deployed to track a small number of mobile targets compared to the centralized tracking systems. However, in several applications, it is essential to position a large number of mobile targets. In such applications, decentralized systems offer high power consumption, since the location of each mobile target is required to be transmitted to a sink node, and this increases the power consumption for the whole WSN. In this paper, we propose a power efficient decentralized approach for tracking a large number of mobile targets while offering reasonable localization accuracy through ZigBee network.
Challenges of Critical and Emancipatory Design Science Research: The Design of 'Possible Worlds' as Response
Venue: arXiv cs.CY 2013
Year: 2013

Popper's (1967) 'piecemeal social change' is an approach manifesting itself in science as critical and emancipatory (C&E) research. It is concerned with incrementally removing manifested inequalities to achieve a 'better' world. Although design science research in information systems seems to be a prime candidate for such endeavors, respective projects are clearly underrepresented. This position paper argues that this is due to the demand of justifying research ex post by an evaluation in practical settings. From the perspective of C&E research it is questionable if powerful actors grant access to their organization and support projects which ultimately challenge their position. It is suggested that theory development based on a synthesis of justificatory knowledge is a complementary approach that allows designing realizable responses to C&E issues---the design of 'possible worlds' (Lewis, 1986) as basis for C&E design science research.
Opinion Mining and Analysis: A survey
Venue: arXiv cs.CL 2013
Year: 2013

The current research is focusing on the area of Opinion Mining also called as sentiment analysis due to sheer volume of opinion rich web resources such as discussion forums, review sites and blogs are available in digital form. One important problem in sentiment analysis of product reviews is to produce summary of opinions based on product features. We have surveyed and analyzed in this paper, various techniques that have been developed for the key tasks of opinion mining. We have provided an overall picture of what is involved in developing a software system for opinion mining on the basis of our survey and analysis.
Social Networking Site For Self Portfolio
Venue: arXiv cs.SI 2013
Year: 2013

Online social networking concept is a global phenomenon and there are millions of sites which help in being connected with friends and family. This project focuses on creating self-portfolios for the users which makes the users engaging with their skills. The users follow the other users to interact and communicate with them. Users can encourage the other users blogs and videos by clicking the hit button. The functionality of this site is designed to focus on both professional as well as academics. Each user is given a dashboard for uploading videos and writing blogs.
Genetic approach for arabic part of speech tagging
Venue: arXiv cs.CL 2013
Year: 2013

With the growing number of textual resources available, the ability to understand them becomes critical. An essential first step in understanding these sources is the ability to identify the part of speech in each sentence. Arabic is a morphologically rich language, wich presents a challenge for part of speech tagging. In this paper, our goal is to propose, improve and implement a part of speech tagger based on a genetic alorithm. The accuracy obtained with this method is comparable to that of other probabilistic approaches.
Improving MUC extraction thanks to local search
Venue: arXiv cs.AI 2013
Year: 2013

ExtractingMUCs(MinimalUnsatisfiableCores)fromanunsatisfiable constraint network is a useful process when causes of unsatisfiability must be understood so that the network can be re-engineered and relaxed to become sat- isfiable. Despite bad worst-case computational complexity results, various MUC- finding approaches that appear tractable for many real-life instances have been proposed. Many of them are based on the successive identification of so-called transition constraints. In this respect, we show how local search can be used to possibly extract additional transition constraints at each main iteration step. The approach is shown to outperform a technique based on a form of model rotation imported from the SAT-related technology and that also exhibits additional transi- tion constraints. Our extensive computational experimentations show that this en- hancement also boosts the performance of state-of-the-art DC(WCORE)-like MUC extractors.
Statistically-secure ORAM with $\tilde{O}(\log^2 n)$ Overhead
Venue: arXiv cs.CR 2013
Year: 2013

We demonstrate a simple, statistically secure, ORAM with computational overhead $\tilde{O}(\log^2 n)$; previous ORAM protocols achieve only computational security (under computational assumptions) or require $\tildeΩ(\log^3 n)$ overheard. An additional benefit of our ORAM is its conceptual simplicity, which makes it easy to implement in both software and (commercially available) hardware. Our construction is based on recent ORAM constructions due to Shi, Chan, Stefanov, and Li (Asiacrypt 2011) and Stefanov and Shi (ArXiv 2012), but with some crucial modifications in the algorithm that simplifies the ORAM and enable our analysis. A central component in our analysis is reducing the analysis of our algorithm to a "supermarket" problem; of independent interest (and of importance to our analysis,) we provide an upper bound on the rate of "upset" customers in the "supermarket" problem.
Exploiting Spatial Interference Alignment and Opportunistic Scheduling in the Downlink of Interference Limited Systems
Venue: arXiv cs.IT 2013
Year: 2013

In this paper we analyze the performance of single stream and multi-stream spatial multiplexing (SM) systems employing opportunistic scheduling in the presence of interference. In the proposed downlink framework, every active user reports the post-processing signal-to-interference-plus-noise-power-ratio (post-SINR) or the receiver specific mutual information (MI) to its own transmitter using a feedback channel. The combination of scheduling and multi-antenna receiver processing leads to substantial interference suppression gain. Specifically, we show that opportunistic scheduling exploits spatial interference alignment (SIA) property inherent to a multi-user system for effective interference mitigation. We obtain bounds for the outage probability and the sum outage capacity for single stream and multi stream SM employing real or complex encoding for a symmetric interference channel model. The techniques considered in this paper are optimal in different operating regimes. We show that the sum outage capacity can be maximized by reducing the SM rate to a value less than the maximum allowed value. The optimum SM rate depends on the number of interferers and the number of available active users. In particular, we show that the generalized multi-user SM (MU SM) method employing real-valued encoding provides a performance that is either comparable, or significantly higher than that of MU SM employing complex encoding. A combination of analysis and simulation is used to describe the trade-off between the multiplexing rate and sum outage capacity for different antenna configurations.