OpenRaiser/Intern-Atlas huggingface dataset:
An Empirical Study of UDP (CBR) Packet Performance over AODV Single & Multi-Channel Parallel Transmission in MANET
Venue: arXiv cs.NI 2011
Year: 2011

Mobile Ad-hoc Network is a temporary network which is the cooperative engagement of a collection of standalone mobile nodes that are not connected to any external network. It is a decentralized network where mobile nodes can be easily deployed in almost any environment without sophisticated infrastructure support. An empirical study has been done for AODV routing protocol under single channel and multi channel environment using the tool NS2. To compare the performance of AODV in the two environments, the simulation results have been analyzed by graphical manner and trace file based on QoS metrics such as throughput, packet drop, delay and jitter. The simulation result analysis verifies the AODV routing protocol performances for single channel and multi channel. After the analysis of the simulation scenario we suggest that use of Parallel MAC (P-MAC) may enhance the performance for multi channel.
Outsourcing Competence
Venue: arXiv cs.OH 2011
Year: 2011

The topic of this paper, competences needed for outsourcing, is organized by first providing a generic competence scheme, which is subsequently instantiated to the area of sourcing and outsourcing. Sourcing and outsourcing are positioned as different areas of activity, neither one of which is subsumed under the other one. It is argued that competences relevant for outsourcing are mainly community based rather than evidence based. Subjective ability and objective ability are distinguished as categories, together making up ability, which are distinct but not necessarily disjoint from competence. Conjectural ability is introduced as a form of subjective ability. A person's competence profile includes competences as well as abilities, including subjective ones. Competence assessment and acquisition as well as the impact of assessed competence on practical work is described. The analysis of competence and ability thus developed is used as standpoint from which to extract a specification of an audience for a theory of outsourcing, yet to be written. Moreover, it allows to formulate requirements for and in preparation of the development of an outsourcing theory. Formulating these requirements is done under the assumption that a person's awareness of a theory of outsourcing is expected to strengthen that person's outsourcing competence profile.
Multiple-Goal Heuristic Search
Venue: arXiv cs.AI 2011
Year: 2011

This paper presents a new framework for anytime heuristic search where the task is to achieve as many goals as possible within the allocated resources. We show the inadequacy of traditional distance-estimation heuristics for tasks of this type and present alternative heuristics that are more appropriate for multiple-goal search. In particular, we introduce the marginal-utility heuristic, which estimates the cost and the benefit of exploring a subtree below a search node. We developed two methods for online learning of the marginal-utility heuristic. One is based on local similarity of the partial marginal utility of sibling nodes, and the other generalizes marginal-utility over the state feature space. We apply our adaptive and non-adaptive multiple-goal search algorithms to several problems, including focused crawling, and show their superiority over existing methods.
FluCaP: A Heuristic Search Planner for First-Order MDPs
Venue: arXiv cs.AI 2011
Year: 2011

We present a heuristic search algorithm for solving first-order Markov Decision Processes (FOMDPs). Our approach combines first-order state abstraction that avoids evaluating states individually, and heuristic search that avoids evaluating all states. Firstly, in contrast to existing systems, which start with propositionalizing the FOMDP and then perform state abstraction on its propositionalized version we apply state abstraction directly on the FOMDP avoiding propositionalization. This kind of abstraction is referred to as first-order state abstraction. Secondly, guided by an admissible heuristic, the search is restricted to those states that are reachable from the initial state. We demonstrate the usefulness of the above techniques for solving FOMDPs with a system, referred to as FluCaP (formerly, FCPlanner), that entered the probabilistic track of the 2004 International Planning Competition (IPC2004) and demonstrated an advantage over other planners on the problems represented in first-order terms.
Sound Analysis and Synthesis Adaptive in Time and Two Frequency Bands
Venue: arXiv cs.SD 2011
Year: 2011

We present an algorithm for sound analysis and resynthesis with local automatic adaptation of time-frequency resolution. There exists several algorithms allowing to adapt the analysis window depending on its time or frequency location; in what follows we propose a method which select the optimal resolution depending on both time and frequency. We consider an approach that we denote as analysis-weighting, from the point of view of Gabor frame theory. We analyze in particular the case of different adaptive time-varying resolutions within two complementary frequency bands; this is a typical case where perfect signal reconstruction cannot in general be achieved with fast algorithms, causing a certain error to be minimized. We provide examples of adaptive analyses of a music sound, and outline several possibilities that this work opens.
Do Software Languages Engineers Evaluate their Languages?
Venue: arXiv cs.SE 2011
Year: 2011

Domain Specific Languages (DSLs) can contribute to increment productivity, while reducing the required maintenance and programming expertise. We hypothesize that Software Languages Engineering (SLE) developers consistently skip, or relax, Language Evaluation. Based on the experience of engineering other types of software products, we assume that this may potentially lead to the deployment of inadequate languages. The fact that the languages already deal with concepts from the problem domain, and not the solution domain, is not enough to validate several issues at stake, such as its expressiveness, usability, effectiveness, maintainability, or even the domain expert's productivity while using them. We present a systematic review on articles published in top ranked venues, from 2001 to 2008, which report DSLs' construction, to characterize the common practice. This work confirms our initial hypothesis and lays the ground for the discussion on how to include a systematic approach to DSL evaluation in the SLE process.
Distributed Air Traffic Control : A Human Safety Perspective
Venue: arXiv cs.MA 2011
Year: 2011

The issues in air traffic control have so far been addressed with the intent to improve resource utilization and achieve an optimized solution with respect to fuel comsumption of aircrafts, efficient usage of the available airspace with minimal congestion related losses under various dynamic constraints. So the focus has almost always been more on smarter management of traffic to increase profits while human safety, though achieved in the process, we believe, has remained less seriously attended. This has become all the more important given that we have overburdened and overstressed air traffic controllers managing hundreds of airports and thousands of aircrafts per day. We propose a multiagent system based distributed approach to handle air traffic ensuring complete human (passenger) safety without removing any humans (ground controllers) from the loop thereby also retaining the earlier advantages in the new solution. The detailed design of the agent system, which will be easily interfacable with the existing environment, is described. Based on our initial findings from simulations, we strongly believe the system to be capable of handling the nuances involved, to be extendable and customizable at any later point in time.
Video OCR for Video Indexing
Venue: arXiv cs.IR 2011
Year: 2011

Video OCR is a technique that can greatly help to locate the topics of interest in video via the automatic extraction and reading of captions and annotations. Text in video can provide key indexing information. Recognizing such text for search application is critical. Major difficult problem for character recognition for videos is degraded and deformated characters, low resolution characters or very complex background. To tackle the problem preprocessing on text image plays vital role. Most of the OCR engines are working on the binary image so to find a better binarization procedure for image to get a desired result is important.Accurate binarization process minimizes the error rate of video OCR.
Verifying Computations with Streaming Interactive Proofs
Venue: arXiv cs.DB 2011
Year: 2011

When computation is outsourced, the data owner would like to be assured that the desired computation has been performed correctly by the service provider. In theory, proof systems can give the necessary assurance, but prior work is not sufficiently scalable or practical. In this paper, we develop new proof protocols for verifying computations which are streaming in nature: the verifier (data owner) needs only logarithmic space and a single pass over the input, and after observing the input follows a simple protocol with a prover (service provider) that takes logarithmic communication spread over a logarithmic number of rounds. These ensure that the computation is performed correctly: that the service provider has not made any errors or missed out some data. The guarantee is very strong: even if the service provider deliberately tries to cheat, there is only vanishingly small probability of doing so undetected, while a correct computation is always accepted. We first observe that some theoretical results can be modified to work with streaming verifiers, showing that there are efficient protocols for problems in the complexity classes NP and NC. Our main results then seek to bridge the gap between theory and practice by developing usable protocols for a variety of problems of central importance in streaming and database processing. All these problems require linear space in the traditional streaming model, and therefore our protocols demonstrate that adding a prover can exponentially reduce the effort needed by the verifier. Our experimental results show that our protocols are practical and scalable.
A MovingObject Index for Efficient Query Processing with Peer-Wise Location Privacy
Venue: arXiv cs.DB 2011
Year: 2011

With the growing use of location-based services, location privacy attracts increasing attention from users, industry, and the research community. While considerable effort has been devoted to inventing techniques that prevent service providers from knowing a user's exact location, relatively little attention has been paid to enabling so-called peer-wise privacy--the protection of a user's location from unauthorized peer users. This paper identifies an important efficiency problem in existing peer-privacy approaches that simply apply a filtering step to identify users that are located in a query range, but that do not want to disclose their location to the querying peer. To solve this problem, we propose a novel, privacy-policy enabled index called the PEB-tree that seamlessly integrates location proximity and policy compatibility. We propose efficient algorithms that use the PEB-tree for processing privacy-aware range and kNN queries. Extensive experiments suggest that the PEB-tree enables efficient query processing.
ERA: Efficient Serial and Parallel Suffix Tree Construction for Very Long Strings
Venue: arXiv cs.DB 2011
Year: 2011

The suffix tree is a data structure for indexing strings. It is used in a variety of applications such as bioinformatics, time series analysis, clustering, text editing and data compression. However, when the string and the resulting suffix tree are too large to fit into the main memory, most existing construction algorithms become very inefficient. This paper presents a disk-based suffix tree construction method, called Elastic Range (ERa), which works efficiently with very long strings that are much larger than the available memory. ERa partitions the tree construction process horizontally and vertically and minimizes I/Os by dynamically adjusting the horizontal partitions independently for each vertical partition, based on the evolving shape of the tree and the available memory. Where appropriate, ERa also groups vertical partitions together to amortize the I/O cost. We developed a serial version; a parallel version for shared-memory and shared-disk multi-core systems; and a parallel version for shared-nothing architectures. ERa indexes the entire human genome in 19 minutes on an ordinary desktop computer. For comparison, the fastest existing method needs 15 minutes using 1024 CPUs on an IBM BlueGene supercomputer.
Fast Updates on Read-Optimized Databases Using Multi-Core CPUs
Venue: arXiv cs.DB 2011
Year: 2011

Read-optimized columnar databases use differential updates to handle writes by maintaining a separate write-optimized delta partition which is periodically merged with the read-optimized and compressed main partition. This merge process introduces significant overheads and unacceptable downtimes in update intensive systems, aspiring to combine transactional and analytical workloads into one system. In the first part of the paper, we report data analyses of 12 SAP Business Suite customer systems. In the second half, we present an optimized merge process reducing the merge overhead of current systems by a factor of 30. Our linear-time merge algorithm exploits the underlying high compute and bandwidth resources of modern multi-core CPUs with architecture-aware optimizations and efficient parallelization. This enables compressed in-memory column stores to handle the transactional update rate required by enterprise applications, while keeping properties of read-optimized databases for analytic-style queries.
Parameterized complexity in multiple-interval graphs: domination, partition, separation, irredundancy
Venue: arXiv cs.CC 2011
Year: 2011

We show that the problem k-Dominating Set and its several variants including k-Connected Dominating Set, k-Independent Dominating Set, and k-Dominating Clique, when parameterized by the solution size k, are W[1]-hard in either multiple-interval graphs or their complements or both. On the other hand, we show that these problems belong to W[1] when restricted to multiple-interval graphs and their complements. This answers an open question of Fellows et al. In sharp contrast, we show that d-Distance k-Dominating Set for d >= 2 is W[2]-complete in multiple-interval graphs and their complements. We also show that k-Perfect Code and d-Distance k-Perfect Code for d >= 2 are W[1]-complete even in unit 2-track interval graphs. In addition, we present various new results on the parameterized complexities of k-Vertex Clique Partition and k-Separating Vertices in multiple-interval graphs and their complements, and present a very simple alternative proof of the W[1]-hardness of k-Irredundant Set in general graphs.
Analysing complexity of XML Schemas in geospatial web services
Venue: arXiv cs.DB 2011
Year: 2011

XML Schema is the language used to define the structure of messages exchanged between OGC-based web service clients and providers. The size of these schemas has been growing with time, reaching a state that makes its understanding and effective application a hard task. A first step to cope with this situation is to provide different ways to measure the complexity of the schemas. In this regard, we present in this paper an analysis of the complexity of XML schemas in OGC web services. We use a group of metrics found in the literature and introduce new metrics to measure size and/or complexity of these schemas. The use of adequate metrics allows us to quantify the complexity, quality and other properties of the schemas, which can be very useful in different scenarios.
Face Recognition using Optimal Representation Ensemble
Venue: arXiv cs.CV 2011
Year: 2011

Recently, the face recognizers based on linear representations have been shown to deliver state-of-the-art performance. In real-world applications, however, face images usually suffer from expressions, disguises and random occlusions. The problematic facial parts undermine the validity of the linear-subspace assumption and thus the recognition performance deteriorates significantly. In this work, we address the problem in a learning-inference-mixed fashion. By observing that the linear-subspace assumption is more reliable on certain face patches rather than on the holistic face, some Bayesian Patch Representations (BPRs) are randomly generated and interpreted according to the Bayes' theory. We then train an ensemble model over the patch-representations by minimizing the empirical risk w.r.t the "leave-one-out margins". The obtained model is termed Optimal Representation Ensemble (ORE), since it guarantees the optimality from the perspective of Empirical Risk Minimization. To handle the unknown patterns in test faces, a robust version of BPR is proposed by taking the non-face category into consideration. Equipped with the Robust-BPRs, the inference ability of ORE is increased dramatically and several record-breaking accuracies (99.9% on Yale-B and 99.5% on AR) and desirable efficiencies (below 20 ms per face in Matlab) are achieved. It also overwhelms other modular heuristics on the faces with random occlusions, extreme expressions and disguises. Furthermore, to accommodate immense BPRs sets, a boosting-like algorithm is also derived. The boosted model, a.k.a Boosted-ORE, obtains similar performance to its prototype. Besides the empirical superiorities, two desirable features of the proposed methods, namely, the training-determined model-selection and the data-weight-free boosting procedure, are also theoretically verified.
The firefighter problem with more than one firefighter on trees
Venue: arXiv cs.DM 2011
Year: 2011

In this paper we study the complexity of the firefighter problem and related problems on trees when more than one firefighter is available at each time step, and answer several open questions of Finbow and MacGillivray 2009. More precisely, when $b \geq 2$ firefighters are allowed at each time step, the problem is NP-complete for trees of maximum degree $b+2$ and polynomial-time solvable for trees of maximum degree $b+2$ when the fire breaks out at a vertex of degree at most $b+1$. Moreover we present a polynomial-time algorithm for a subclass of trees, namely $k$-caterpillars.
Hybrid Codes Needed for Coordination over the Point-to-Point Channel
Venue: arXiv cs.IT 2011
Year: 2011

We consider a new fundamental question regarding the point-to-point memoryless channel. The source-channel separation theorem indicates that random codebook construction for lossy source compression and channel coding can be independently constructed and paired to achieve optimal performance for coordinating a source sequence with a reconstruction sequence. But what if we want the channel input to also be coordinated with the source and reconstruction? Such situations arise in network communication problems, where the correlation inherent in the information sources can be used to correlate channel inputs. Hybrid codes have been shown to be useful in a number of network communication problems. In this work we highlight their advantages over purely digital codebook construction by applying them to the point-to-point setting, coordinating both the channel input and the reconstruction with the source.
A binary noisy channel to model errors in printing process
Venue: arXiv cs.OH 2011
Year: 2011

To model printing noise a binary noisy channel and a set of controlled gates are introduced. The channel input is an image created by a halftoning algorithm and its output is the printed picture. Using this channel robustness to noise between halftoning algorithms can be studied. We introduced relative entropy to describe immunity of the algorithm to noise and tested several halftoning algorithms.
Distance Preserving Graph Simplification
Venue: arXiv cs.SI 2011
Year: 2011

Large graphs are difficult to represent, visualize, and understand. In this paper, we introduce "gate graph" - a new approach to perform graph simplification. A gate graph provides a simplified topological view of the original graph. Specifically, we construct a gate graph from a large graph so that for any "non-local" vertex pair (distance higher than some threshold) in the original graph, their shortest-path distance can be recovered by consecutive "local" walks through the gate vertices in the gate graph. We perform a theoretical investigation on the gate-vertex set discovery problem. We characterize its computational complexity and reveal the upper bound of minimum gate-vertex set using VC-dimension theory. We propose an efficient mining algorithm to discover a gate-vertex set with guaranteed logarithmic bound. We further present a fast technique for pruning redundant edges in a gate graph. The detailed experimental results using both real and synthetic graphs demonstrate the effectiveness and efficiency of our approach.
Boolean Satisfiability using Noise Based Logic
Venue: arXiv cs.CC 2011
Year: 2011

In this paper, we present a novel algorithm to solve the Boolean Satisfiability (SAT) problem, using noise-based logic (NBL). Contrary to what the name may suggest, NBL is not a random/fuzzy logic system. In fact, it is a completely deterministic logic system. A key property of NBL is that it allows us to apply a superposition of many input vectors to a SAT instance at the same time, circumventing a key restriction and assumption in the traditional approach to solving SAT. By exploiting the superposition property of NBL, our NBL-based SAT algorithm can determine whether an instance is SAT or not in a single operation. A satisfying solution can be found by iteratively performing SAT check operations up to n times, where n is the number of variables in the SAT instance. Although this paper does not focus on the realization of an NBL-based SAT engine, such an engine can be conceived using analog circuits (wide-band amplifiers, adders and multipliers), FPGAs or ASICs. Additionally, we also discus scalability of our approach, which can apply to NBL in general. The NBL-based SAT engine described in this paper has been simulated in software for validation purposes.
A Modulus-Squared Dirichlet Boundary Condition for Time-Dependent Complex Partial Differential Equations and its Application to the Nonlinear Schrödinger Equation
Venue: arXiv cs.NA 2011
Year: 2011

An easy to implement modulus-squared Dirichlet (MSD) boundary condition is formulated for numerical simulations of time-dependent complex partial differential equations in multidimensional settings. The MSD boundary condition approximates a constant modulus-square value of the solution at the boundaries. Application of the MSD boundary condition to the nonlinear Schrödinger equation is shown, and numerical simulations are performed to demonstrate its usefulness and advantages over other simple boundary conditions.