OpenRaiser/Intern-Atlas huggingface dataset:
Set K-Cover Algorithms for Energy Efficient Monitoring in Wireless Sensor Networks
Venue: arXiv cs.DS 2003
Year: 2003

Wireless sensor networks (WSNs) are emerging as an effective means for environment monitoring. This paper investigates a strategy for energy efficient monitoring in WSNs that partitions the sensors into covers, and then activates the covers iteratively in a round-robin fashion. This approach takes advantage of the overlap created when many sensors monitor a single area. Our work builds upon previous work in "Power Efficient Organization of Wireless Sensor Networks" by Slijepcevic and Potkonjak, where the model is first formulated. We have designed three approximation algorithms for a variation of the SET K-COVER problem, where the objective is to partition the sensors into covers such that the number of covers that include an area, summed over all areas, is maximized. The first algorithm is randomized and partitions the sensors, in expectation, within a fraction 1 - 1/e (~.63) of the optimum. We present two other deterministic approximation algorithms. One is a distributed greedy algorithm with a 1/2 approximation ratio and the other is a centralized greedy algorithm with a 1 - 1/e approximation ratio. We show that it is NP-Complete to guarantee better than 15/16 of the optimal coverage, indicating that all three algorithms perform well with respect to the best approximation algorithm possible. Simulations indicate that in practice, the deterministic algorithms perform far above their worst case bounds, consistently covering more than 72% of what is covered by an optimum solution. Simulations also indicate that the increase in longevity is proportional to the amount of overlap amongst the sensors. The algorithms are fast, easy to use, and according to simulations, significantly increase the longevity of sensor networks. The randomized algorithm in particular seems quite practical.
Improving TCP/IP Performance over Wireless IEEE 802.11 Link
Venue: arXiv cs.NI 2003
Year: 2003

Cellular phones, wireless laptops, personal portable devices that supports both voice and data access are all examples of communicating devices that uses wireless communication. Sine TCP/IP (and UDP) is the dominant technology in use in the internet, it is expected that they will be used (and they are currently) over wireless connections. In this paper, we investigate the performance of the TCP (and UDP) over IEEE802.11 wireless MAC protocol. We investigate the performance of the TCP and UDP assuming three different traffic patterns. First bulk transmission where the main concern is the throughput. Second real-time audio (using UDP) in the existence of bulk TCP transmission where the main concern is the packet loss for audio traffic. Finally web traffic where the main concern is the response time. We also investigate the effect of using forward Error Correction (FEC) technique and the MAC sublayer parameters on the throughput and response time.
DUCT: An Interactive Define-Use Chain Navigation Tool for Relative Debugging
Venue: arXiv cs.SE 2003
Year: 2003

This paper describes an interactive tool that facilitates following define-use chains in large codes. The motivation for the work is to support relative debugging, where it is necessary to iteratively refine a set of asser-tions between different versions of a program. DUCT is novel because it exploits the Microsoft Intermediate Language (MSIL) that underpins the .NET Framework. Accordingly, it works on a wide range of programming languages without any modification. The paper describes the design and implementation of DUCT, and then illustrates its use with a small case study.
Unsupervised Grammar Induction in a Framework of Information Compression by Multiple Alignment, Unification and Search
Venue: arXiv cs.AI 2003
Year: 2003

This paper describes a novel approach to grammar induction that has been developed within a framework designed to integrate learning with other aspects of computing, AI, mathematics and logic. This framework, called "information compression by multiple alignment, unification and search" (ICMAUS), is founded on principles of Minimum Length Encoding pioneered by Solomonoff and others. Most of the paper describes SP70, a computer model of the ICMAUS framework that incorporates processes for unsupervised learning of grammars. An example is presented to show how the model can infer a plausible grammar from appropriate input. Limitations of the current model and how they may be overcome are briefly discussed.
I know what you mean: semantic issues in Internet-scale publish/subscribe systems
Venue: arXiv cs.DC 2003
Year: 2003

In recent years, the amount of information on the Internet has increased exponentially developing great interest in selective information dissemination systems. The publish/subscribe paradigm is particularly suited for designing systems for routing information and requests according to their content throughout wide-area network of brokers. Current publish/subscribe systems use limited syntax-based content routing but since publishers and subscribers are anonymous and decoupled in time, space and location, often over wide-area network boundary, they do not necessarily speak the same language. Consequently, adding semantics to current publish/subscribe systems is important. In this paper we identify and examine the issues in developing semantic-based content routing for publish/subscribe broker networks.
Performance of TCP/UDP under Ad Hoc IEEE802.11
Venue: arXiv cs.NI 2003
Year: 2003

TCP is the De facto standard for connection oriented transport layer protocol, while UDP is the De facto standard for transport layer protocol, which is used with real time traffic for audio and video. Although there have been many attempts to measure and analyze the performance of the TCP protocol in wireless networks, very few research was done on the UDP or the interaction between TCP and UDP traffic over the wireless link. In this paper, we tudy the performance of TCP and UDP over IEEE802.11 ad hoc network. We used two topologies, a string and a mesh topology. Our work indicates that IEEE802.11 as a ad-hoc network is not very suitable for bulk transfer using TCP. It also indicates that it is much better for real-time audio. Although one has to be careful here since real-time audio does require much less bandwidth than the wireless link bandwidth. Careful and detailed studies are needed to further clarify that issue.
Minimal founded semantics for disjunctive logic programs and deductive databases
Venue: arXiv cs.LO 2003
Year: 2003

In this paper, we propose a variant of stable model semantics for disjunctive logic programming and deductive databases. The semantics, called minimal founded, generalizes stable model semantics for normal (i.e. non disjunctive) programs but differs from disjunctive stable model semantics (the extension of stable model semantics for disjunctive programs). Compared with disjunctive stable model semantics, minimal founded semantics seems to be more intuitive, it gives meaning to programs which are meaningless under stable model semantics and is no harder to compute. More specifically, minimal founded semantics differs from stable model semantics only for disjunctive programs having constraint rules or rules working as constraints. We study the expressive power of the semantics and show that for general disjunctive datalog programs it has the same power as disjunctive stable model semantics.
Diagnostic reasoning with A-Prolog
Venue: arXiv cs.AI 2003
Year: 2003

In this paper we suggest an architecture for a software agent which operates a physical device and is capable of making observations and of testing and repairing the device's components. We present simplified definitions of the notions of symptom, candidate diagnosis, and diagnosis which are based on the theory of action language ${\cal AL}$. The definitions allow one to give a simple account of the agent's behavior in which many of the agent's tasks are reduced to computing stable models of logic programs.
Randomized selection with quintary partitions
Venue: arXiv cs.DS 2003
Year: 2003

We show that several versions of Floyd and Rivest's algorithm Select for finding the $k$th smallest of $n$ elements require at most $n+\min\{k,n-k\}+o(n)$ comparisons on average and with high probability. This rectifies the analysis of Floyd and Rivest, and extends it to the case of nondistinct elements. Our computational results confirm that Select may be the best algorithm in practice.
Acquiring Lexical Paraphrases from a Single Corpus
Venue: arXiv cs.CL 2003
Year: 2003

This paper studies the potential of identifying lexical paraphrases within a single corpus, focusing on the extraction of verb paraphrases. Most previous approaches detect individual paraphrase instances within a pair (or set) of comparable corpora, each of them containing roughly the same information, and rely on the substantial level of correspondence of such corpora. We present a novel method that successfully detects isolated paraphrase instances within a single corpus without relying on any a-priori structure and information. A comparison suggests that an instance-based approach may be combined with a vector based approach in order to assess better the paraphrase likelihood for many verb pairs.
Part-of-Speech Tagging with Minimal Lexicalization
Venue: arXiv cs.CL 2003
Year: 2003

We use a Dynamic Bayesian Network to represent compactly a variety of sublexical and contextual features relevant to Part-of-Speech (PoS) tagging. The outcome is a flexible tagger (LegoTag) with state-of-the-art performance (3.6% error on a benchmark corpus). We explore the effect of eliminating redundancy and radically reducing the size of feature vocabularies. We find that a small but linguistically motivated set of suffixes results in improved cross-corpora generalization. We also show that a minimal lexicon limited to function words is sufficient to ensure reasonable performance.
The traveling salesman problem for cubic graphs
Venue: arXiv cs.DS 2004
Year: 2004

We show how to find a Hamiltonian cycle in a graph of degree at most three with n vertices, in time O(2^{n/3}) ~= 1.260^n and linear space. Our algorithm can find the minimum weight Hamiltonian cycle (traveling salesman problem), in the same time bound. We can also count or list all Hamiltonian cycles in a degree three graph in time O(2^{3n/8}) ~= 1.297^n. We also solve the traveling salesman problem in graphs of degree at most four, by randomized and deterministic algorithms with runtime O((27/4)^{n/3}) ~= 1.890^n and O((27/4+epsilon)^{n/3}) respectively. Our algorithms allow the input to specify a set of forced edges which must be part of any generated cycle. Our cycle listing algorithm shows that every degree three graph has O(2^{3n/8}) Hamiltonian cycles; we also exhibit a family of graphs with 2^{n/3} Hamiltonian cycles per graph.
Quantifying and Visualizing Attribute Interactions
Venue: arXiv cs.AI 2004
Year: 2004

Interactions are patterns between several attributes in data that cannot be inferred from any subset of these attributes. While mutual information is a well-established approach to evaluating the interactions between two attributes, we surveyed its generalizations as to quantify interactions between several attributes. We have chosen McGill's interaction information, which has been independently rediscovered a number of times under various names in various disciplines, because of its many intuitively appealing properties. We apply interaction information to visually present the most important interactions of the data. Visualization of interactions has provided insight into the structure of data on a number of domains, identifying redundant attributes and opportunities for constructing new features, discovering unexpected regularities in data, and have helped during construction of predictive models; we illustrate the methods on numerous examples. A machine learning method that disregards interactions may get caught in two traps: myopia is caused by learning algorithms assuming independence in spite of interactions, whereas fragmentation arises from assuming an interaction in spite of independence.
Clustering by compression
Venue: arXiv cs.CV 2004
Year: 2004

We present a new method for clustering based on compression. The method doesn't use subject-specific features or background knowledge, and works as follows: First, we determine a universal similarity distance, the normalized compression distance or NCD, computed from the lengths of compressed data files (singly and in pairwise concatenation). Second, we apply a hierarchical clustering method. The NCD is universal in that it is not restricted to a specific application area, and works across application area boundaries. A theoretical precursor, the normalized information distance, co-developed by one of the authors, is provably optimal but uses the non-computable notion of Kolmogorov complexity. We propose precise notions of similarity metric, normal compressor, and show that the NCD based on a normal compressor is a similarity metric that approximates universality. To extract a hierarchy of clusters from the distance matrix, we determine a dendrogram (binary tree) by a new quartet method and a fast heuristic to implement it. The method is implemented and available as public software, and is robust under choice of different compressors. To substantiate our claims of universality and robustness, we report evidence of successful application in areas as diverse as genomics, virology, languages, literature, music, handwritten digits, astronomy, and combinations of objects from completely different domains, using statistical, dictionary, and block sorting compressors. In genomics we presented new evidence for major questions in Mammalian evolution, based on whole-mitochondrial genomic analysis: the Eutherian orders and the Marsupionta hypothesis against the Theria hypothesis.
Algorithm xxx: Modified Bessel functions of imaginary order and positive argument
Venue: arXiv cs.MS 2004
Year: 2004

Fortran 77 programs for the computation of modified Bessel functions of purely imaginary order are presented. The codes compute the functions $K_{ia}(x)$, $L_{ia}(x)$ and their derivatives for real $a$ and positive $x$; these functions are independent solutions of the differential equation $x^2 w'' +x w' +(a^2 -x^2)w=0$. The code also computes exponentially scaled functions. The range of computation is $(x,a)\in (0,1500]\times [-1500,1500]$ when scaled functions are considered and it is larger than $(0,500]\times [-400,400]$ for standard IEEE double precision arithmetic. The relative accuracy is better than $10^{-13}$ in the range $(0,200]\times [-200,200]$ and close to $10^{-12}$ in $(0,1500]\times [-1500,1500]$.
Query Answering in Peer-to-Peer Data Exchange Systems
Venue: arXiv cs.DB 2004
Year: 2004

The problem of answering queries posed to a peer who is a member of a peer-to-peer data exchange system is studied. The answers have to be consistent wrt to both the local semantic constraints and the data exchange constraints with other peers; and must also respect certain trust relationships between peers. A semantics for peer consistent answers under exchange constraints and trust relationships is introduced and some techniques for obtaining those answers are presented.
Better Foreground Segmentation Through Graph Cuts
Venue: arXiv cs.CV 2004
Year: 2004

For many tracking and surveillance applications, background subtraction provides an effective means of segmenting objects moving in front of a static background. Researchers have traditionally used combinations of morphological operations to remove the noise inherent in the background-subtracted result. Such techniques can effectively isolate foreground objects, but tend to lose fidelity around the borders of the segmentation, especially for noisy input. This paper explores the use of a minimum graph cut algorithm to segment the foreground, resulting in qualitatively and quantitiatively cleaner segmentations. Experiments on both artificial and real data show that the graph-based method reduces the error around segmented foreground objects. A MATLAB code implementation is available at http://www.cs.smith.edu/~nhowe/research/code/#fgseg
Presynaptic modulation as fast synaptic switching: state-dependent modulation of task performance
Venue: arXiv cs.NE 2004
Year: 2004

Neuromodulatory receptors in presynaptic position have the ability to suppress synaptic transmission for seconds to minutes when fully engaged. This effectively alters the synaptic strength of a connection. Much work on neuromodulation has rested on the assumption that these effects are uniform at every neuron. However, there is considerable evidence to suggest that presynaptic regulation may be in effect synapse-specific. This would define a second "weight modulation" matrix, which reflects presynaptic receptor efficacy at a given site. Here we explore functional consequences of this hypothesis. By analyzing and comparing the weight matrices of networks trained on different aspects of a task, we identify the potential for a low complexity "modulation matrix", which allows to switch between differently trained subtasks while retaining general performance characteristics for the task. This means that a given network can adapt itself to different task demands by regulating its release of neuromodulators. Specifically, we suggest that (a) a network can provide optimized responses for related classification tasks without the need to train entirely separate networks and (b) a network can blend a "memory mode" which aims at reproducing memorized patterns and a "novelty mode" which aims to facilitate classification of new patterns. We relate this work to the known effects of neuromodulators on brain-state dependent processing.
Running C++ models undet the Swarm environment
Venue: arXiv cs.MA 2004
Year: 2004

Objective-C is still the language of choice if users want to run their simulation efficiently under the Swarm environment since the Swarm environment itself was written in Objective-C. The language is a fast, object-oriented and easy to learn. However, the language is less well known than, less expressive than, and lacks support for many important features of C++ (eg. OpenMP for high performance computing application). In this paper, we present a methodology and software tools that we have developed for auto generating an Objective-C object template (and all the necessary interfacing functions) from a given C++ model, utilising the Classdesc's object description technology, so that the C++ model can both be run and accessed under the Objective-C and C++ environments. We also present a methodology for modifying an existing Swarm application to make part of the model (eg. the heatbug's step method) run under the C++ environment.
ClassdescMP: Easy MPI programming in C++
Venue: arXiv cs.DC 2004
Year: 2004

ClassdescMP is a distributed memory parallel programming system for use with C++ and MPI. It uses the Classdesc reflection system to ease the task of building complicated messages to be sent between processes. It doesn't hide the underlying MPI API, so it is an augmentation of MPI capabilities. Users can still call standard MPI function calls if needed for performance reasons.
Mobile Re-Finding of Web Information Using a Voice Interface
Venue: arXiv cs.HC 2004
Year: 2004

Mobile access to information is a considerable problem for many users, especially to information found on the Web. In this paper, we explore how a voice-controlled service, accessible by telephone, could support mobile users' needs for refinding specific information previously found on the Web. We outline challenges in creating such a service and describe architectural and user interfaces issues discovered in an exploratory prototype we built called WebContext. We also present the results of a study, motivated by our experience with WebContext, to explore what people remember about information that they are trying to refind and how they express information refinding requests in a collaborative conversation. As part of the study, we examine how end-usercreated Web page annotations can be used to help support mobile information re-finding. We observed the use of URLs, page titles, and descriptions of page contents to help identify waypoints in the search process. Furthermore, we observed that the annotations were utilized extensively, indicating that explicitly added context by the user can play an important role in re-finding.
Deciding Disjunctive Linear Arithmetic with SAT
Venue: arXiv cs.LO 2004
Year: 2004

Disjunctive Linear Arithmetic (DLA) is a major decidable theory that is supported by almost all existing theorem provers. The theory consists of Boolean combinations of predicates of the form $Σ_{j=1}^{n}a_j\cdot x_j \le b$, where the coefficients $a_j$, the bound $b$ and the variables $x_1 >... x_n$ are of type Real ($\mathbb{R}$). We show a reduction to propositional logic from disjunctive linear arithmetic based on Fourier-Motzkin elimination. While the complexity of this procedure is not better than competing techniques, it has practical advantages in solving verification problems. It also promotes the option of deciding a combination of theories by reducing them to this logic. Results from experiments show that this method has a strong advantage over existing techniques when there are many disjunctions in the formula.
Improved randomized selection
Venue: arXiv cs.DS 2004
Year: 2004

We show that several versions of Floyd and Rivest's improved algorithm Select for finding the $k$th smallest of $n$ elements require at most $n+\min\{k,n-k\}+O(n^{1/2}\ln^{1/2}n)$ comparisons on average and with high probability. This rectifies the analysis of Floyd and Rivest, and extends it to the case of nondistinct elements. Encouraging computational results on large median-finding problems are reported.
Corollaries on the fixpoint completion: studying the stable semantics by means of the Clark completion
Venue: arXiv cs.AI 2004
Year: 2004

The fixpoint completion fix(P) of a normal logic program P is a program transformation such that the stable models of P are exactly the models of the Clark completion of fix(P). This is well-known and was studied by Dung and Kanchanasut (1989). The correspondence, however, goes much further: The Gelfond-Lifschitz operator of P coincides with the immediate consequence operator of fix(P), as shown by Wendt (2002), and even carries over to standard operators used for characterizing the well-founded and the Kripke-Kleene semantics. We will apply this knowledge to the study of the stable semantics, and this will allow us to almost effortlessly derive new results concerning fixed-point and metric-based semantics, and neural-symbolic integration.
P2P Networks for Content Sharing
Venue: arXiv cs.DC 2004
Year: 2004

Peer-to-peer (P2P) technologies have been widely used for content sharing, popularly called "file-swapping" networks. This chapter gives a broad overview of content sharing P2P technologies. It starts with the fundamental concept of P2P computing followed by the analysis of network topologies used in peer-to-peer systems. Next, three milestone peer-to-peer technologies: Napster, Gnutella, and Fasttrack are explored in details, and they are finally concluded with the comparison table in the last section.
The lattice dimension of a graph
Venue: arXiv cs.DS 2004
Year: 2004

We describe a polynomial time algorithm for, given an undirected graph G, finding the minimum dimension d such that G may be isometrically embedded into the d-dimensional integer lattice Z^d.
Towards a Model-Based Framework for Integrating Usability and Software Engineering Life Cycles
Venue: arXiv cs.HC 2004
Year: 2004

In this position paper we propose a process model that provides a development infrastructure in which the usability engineering and software engineering life cycles co-exist in complementary roles. We describe the motivation, hurdles, rationale, arguments, and implementation plan for the need, specification, and the usefulness of such a model.