Technical Reports from UMIACS

Permanent URI for this collectionhttp://hdl.handle.net/1903/7

Browse

Now showing 1 - 20 of 950

Accurate Anchor-Free Node Localization in Wireless Sensor Networks
(2006-02-10T16:51:23Z) Youssef, Adel; Younis, Mohamed; Agrawala, Ashok
There has been a growing interest in the applications of wireless sensor networks in unattended environments. In such applications, sensor nodes are usually deployed randomly in an area of interest. Knowledge of accurate node location is essential in such network setups in order to correlate the reported data to the origin of the sensed phenomena. In addition, awareness of the nodes’ positions can enable employing efficient management strategies such as geographic routing and conducting important analysis such as node coverage properties. In this paper, we present an efficient anchor-free protocol for localization in wireless sensor networks. Each node discovers its neighbors that are within its transmission range and estimates their ranges. Our algorithm fuses local range measurements in order to form a network wide unified coordinate systems while minimizing the overhead incurred at the deployed sensors. Scalability is achieved through grouping sensors into clusters. Simulation results show that the proposed protocol achieves precise localization of sensors and maintains consistent error margins. In addition, we capture the effect of error accumulation of the node’s range estimates and network’s size and connectivity on the overall accuracy of the unified coordinate system.
Accurate computation of Galerkin double surface integrals in the 3-D boundary element method
(2015-05-29) Adelman, Ross; Gumerov, Nail A.; Duraiswami, Ramani
Many boundary element integral equation kernels are based on the Green’s functions of the Laplace and Helmholtz equations in three dimensions. These include, for example, the Laplace, Helmholtz, elasticity, Stokes, and Maxwell equations. Integral equation formulations lead to more compact, but dense linear systems. These dense systems are often solved iteratively via Krylov subspace methods, which may be accelerated via the fast multipole method. There are advantages to Galerkin formulations for such integral equations, as they treat problems associated with kernel singularity, and lead to symmetric and better conditioned matrices. However, the Galerkin method requires each entry in the system matrix to be created via the computation of a double surface integral over one or more pairs of triangles. There are a number of semi-analytical methods to treat these integrals, which all have some issues, and are discussed in this paper. We present novel methods to compute all the integrals that arise in Galerkin formulations involving kernels based on the Laplace and Helmholtz Green’s functions to any specified accuracy. Integrals involving completely geometrically separated triangles are non-singular and are computed using a technique based on spherical harmonics and multipole expansions and translations, which results in the integration of polynomial functions over the triangles. Integrals involving cases where the triangles have common vertices, edges, or are coincident are treated via scaling and symmetry arguments, combined with automatic recursive geometric decomposition of the integrals. Example results are presented, and the developed software is available as open source.
An Accurate Time-Management Unit for Real-Time Processors
(1998-10-15) Kailas, Krishnan K.; Agrawala, Ashok K.
Time management is an important aspect of real-time computation. Traditional high performance processors provide little or no support for management of time. In this report, we propose a time-management unit which can greatly help improve the performance of a real-time system. The proposed unit can be added to any processor architecture without affecting its performance. We also explain how the unit helps to solve the clock synchronization problems in a real-time network. (Also cross-referenced as UMIACS-TR-97-28)
ACE: A Novel Software Platform to Ensure the Integrity of Long Term Archives
(2007-01-31) Song, Sangchul; JaJa, Joseph
We develop a new methodology to address the integrity of long term archives using rigorous cryptographic techniques. A prototype system called ACE (Auditing Control Environment) was designed and developed based on this methodology. ACE creates a small-size integrity token for each digital object and some cryptographic summary information based on all the objects handled within a dynamic time period. ACE continuously audits the contents of the various objects according to the policy set by the archive, and provides mechanisms for an independent third-party auditor to certify the integrity of any object. In fact, our approach will allow an independent auditor to verify the integrity of every version of an archived digital object as well as link the current version to the original form of the object when it was ingested into the archive. We show that ACE is very cost effective and scalable while making no assumptions about the archive architecture. We include in this paper some preliminary results on the validation and performance of ACE on a large image collection.
Active Harmony: Towards Automated Performance Tuning
(2002-08-01) Tapus, Cristian; Chung, I-Hsin; Hollingsworth, Jeffrey K.
In this paper we present the Active Harmony automated runtime tuning system. We describe the interface used by programs to make applications tunable. We present the Library Specification Layer which helps program library developers expose multiple variations of the same API using different algorithms. The Library Specification Language helps to select the most appropriate program library to tune the overall performance. We also present the optimization algorithm that we used to adjust parameters in the application and the libraries. Finally, we present results that show how the system is able to tune several real applications. The automated tuning system is able to tune the application parameters to within a few percent of the best value after evaluating only 11 configurations out of over 1,700 possible combinations. Also UMIACS-TR-2002-54
Active Logic and Heim's Rules for Updating Discourse Context
(1998-10-15) Gurney, John; Perlis, Don; Purang, Khemdut
Discourse unfolds in time, giving rise to a cascade of belief changes in the listener. Yet this temporal evolution of discourse and belief is typically ignored in theoretical treatments of discourse. It has been claimed (see Soames~\cite{soames:presuppositions}) that Heim's~\cite{heim:projection_problem} theory of discourse context accounts for non-implicative discourse updating. We will present a new non-implicative discourse that cannot be accounted for with Heim's use of global or local accommodation and which appears to require attention to \emph{evolution} of discourse. We use this example to motivate remaking Heim's update function, aimed toward a unified approach to discourse---one in which Heim's rules for discourse updating can account for more of the problem cases for the theory of discourse context. These rules and the revised update function can then serve as principles that constrain the building of representations for discourse context (such as the Discourse Representation Structures, of Discourse Representation Theory, ~\cite{kamp:reyle}). We propose \emph{active logic} as a convenient tool for executing the required inferences (as called for by our revised version of Heim's update function) as the discourse evolves through time. (Also cross-referenced as UMIACS-TR-96-43)
Active Logic Applied to Cancellation of Gricean Implicture
(1998-10-15) Purang, Khemdut; Perlis, Don; Gurney, John
Dialog proceeds over time, during which inferred beliefs come and go in the listener. Yet this temporal aspect of dialog and belief is typically ignored in theoretical treatments of dialog. Using a simple example of a dialog with an implicature that arises partway through and then is later retracted, we discuss how Gricean maxims and nonmonotonicity may relate to each other and to a computational treatment of implicature. In effect we seek to track reasoning along Gricean lines over time. We present our own computational approach to this, giving an implementation in the formalism of active logics. (Also cross-referenced as UMIACS-TR-96-42)
Active Logics: A Unified Formal Approach to Episodic Reasoning
(1999-10-14) Elgot-Drapkin, Jennifer; Kraus, Sarit; Miller, Michael; Nirkhe, Madhura; Perlis, Donald
Artificial intelligence research falls roughly into two categories: formal and implementational. This division is not completely firm: there are implementational studies based on (formal or informal) theories (e.g., CYC, SOAR, OSCAR), and there are theories framed with an eye toward implementability (e.g., predicate circumscription). Nevertheless, formal/theoretical work tends to focus on very narrow problems (and even on very special cases of very narrow problems) while trying to get them ``right'' in a very strict sense, while implementational work tends to aim at fairly broad ranges of behavior but often at the expense of any kind of overall conceptually unifying framework that informs understanding. It is sometimes urged that this gap is intrinsic to the topic: intelligence is not a unitary thing for which there will be a unifying theory, but rather a ``society'' of subintelligences whose overall behavior cannot be reduced to useful characterizing and predictive principles. Here we describe a formal architecture that is more closely tied to implementational constraints than is usual for formalisms, and which has been used to solve a number of commonsense problems in a unified manner. In particular, we address the issue of formal, integrated, and longitudinal reasoning: inferentially-modeled behavior that incorporates a fairly wide variety of types of commonsense reasoning within the context of a single extended episode of activity requiring keeping track of ongoing progress, and altering plans and beliefs accordingly. Instead of aiming at optimal solutions to isolated, well-specified and temporally narrow problems, we focus on satisficing solutions to under-specified and temporally-extended problems, much closer to real-world needs. We believe that such a focus is required for AI to arrive at truly intelligent mechanisms with the ability to behave effectively over considerably longer time periods and range of circumstances than is common in AI today. While this will surely lead to less elegant formalisms, it also surely is requisite if AI is to get fully out of the blocks-world and into the real world. (Also cross-referenced as UMIACS-TR-99-65)
Active Proxy-G: Optimizing the Query Execution Process in the Grid
(2002-05-22) Andrade, Henrique; Kurc, Tahsin; Sussman, Alan; Saltz, Joel
The Grid environment facilitates collaborative work and allows many users to query and process data over geographically dispersed data repositories. Over the past several years, there has been a growing interest in developing applications that interactively analyze datasets, potentially in a collaborative setting. We describe an Active Proxy-G service that is able to cache query results, use those results for answering new incoming queries, generate subqueries for the parts of a query that cannot be produced from the cache, and submit the subqueries for final processing at application servers that store the raw datasets. We present an experimental evaluation to illustrate the effects of various design tradeoffs. We also show the benefits that two real applications gain from using the middleware. (Also UMIACS-TR-2002-41)
AD (Attacker Defender) Game
(2002-01-31) Kochut, Andrzej; Agrawala, Ashok K.; Larsen, Ronald L.; Shankar, A. Udaya
Information Dynamics is a framework for agent-based systems that gives a central position to the role of information, time, and the value of information. We illustrate system design in the Information Dynamics Framework by developing an intelligence game called AD involving attackers, defenders and targets operating in some space of locations. The goal of the attackers is to destroy all targets. Target destruction takes place when the number of attackers in the target's neighborhood exceeds the number of defenders in this neighborhood by a value WINNING_DIFFERENCE. The goal of defenders is to prevent attackers from achieving their goal. (Also UMIACS-TR-2001-45)
Adapting to Route-demand and Mobility (ARM) in Ad hoc Network Routing
(2001-05-10) Ahn, Sungjoon; Shankar, A. Udaya
We present ARM (Adapting to Route-demand and Mobility), a control mechanism that allows any proactive routing protocol to dynamically adapt in a totally distributed manner to changes in node mobility and workload route-demands. Each node independently maintains a {\it mobility metric} indicating how fast its neighborhood is currently changing, and a {\it route-demand metric} indicating which destinations are currently involved in data forwarding. Control functions use these metrics to dynamically adjust the period and the content of routing updates. We apply ARM to the DSDV protocol, coming up with ARM-DSDV. For various mobility and workload scenarios, ARM-DSDV typically achieves the same data delivery as DSDV with update period optimized for the scenario, while saving up to 60\% in routing cost. Lower cost gives data traffic more available bandwidth. (Cross-referenced as UMIACS-TR-2001-08)
Adaptive Cost Estimation for Client-Server based Heterogeneous Database Systems
(1998-10-15) Yao, Zhaohui; Chen, Chungmin Melvin; Roussopoulos, Nick
In this paper, we propose a new method for estimating query cost in client-server based heterogeneous database management system. The cost estimation parameters are adjusted by an Adaptive Cost Estimation (ACE) module which uses query execution feedback yielding more and more accurate cost estimates. The most important features of ACE are its detailed cost model which accounts for all costs incurred, its rapid convergence to the actual parameter values, and its low overhead which permits continuous adaptation during the run time of the system. ACE has been implemented and tested with Oracle 6, Oracle 7, Ingres, and ADMS. Extensive experiments performed on these systems show that the ACE's time estimates are within 20% of the real wall-clock time for more than 92% of the queries. This percentage surpasses 98% for queries over 20 seconds. (Also cross-referenced as UMIACS-TR-96-37)
Adaptive Database Buffer Allocation Using Query Feedback
(1998-10-15) Chen, Chungmin Melvin; Roussopoulos, Nick
In this paper, we propose the concept of using query execution feedback for improving database buffer management. A query feedback model which adaptively quantifies the page fault characteristics of all query access patterns including sequential, looping and most importantly random, is defined. Based on this model, a load control and a marginal gain ratio buffer allocation scheme are developed. Simulation experiments show that the proposed method is consistently better than the previous methods and in most cases, it significantly outperforms all other methods for random access reference patterns. (Also cross-referenced as UMIACS-TR-93-49)
Adaptive Hindi OCR Using Generalized Hausdorff Image Comparison
(2003-09-25) Ma, Huanfeng; Doermann, David
In this paper, we present an adaptive Hindi OCR using generalized Hausdor image comparison implemented as part of a rapidly retargetable language tool reort. The system includes: script identification, character segmentation, training sample creation and character recognition. The OCR design (completed in one month) was applied to a complete Hindi-English bilingual dictionary (with 1083 pages) and a collection of ideal images extracted from Hindi documents in PDF format. Experimental results show the recognition accuracy can reach 88% for noisy images and 95% for ideal images, both at the character level. The presented method can also be extended to design OCR systems for different scripts. (LAMP-TR-105) (CAR-TR-987) (UMIACS-TR-2003-87)
Adaptive Probabilistic Search (APS) for Peer-to-Peer Networks
(2003-02-27) Tsoumakos, Dimitrios; Roussopoulos, Nick
Peer-to-Peer networks are gaining increasing attention from both the scientific and the large Internet user community. Popular applications utilizing this new technology offer many attractive features to a growing number of users. At the heart of such networks lies the data retrieval algorithm. Proposed methods either depend on the network-disastrous flooding and its variations or utilize various indices too expensive to maintain. In this report we describe an adaptive, bandwidth-efficient and easy to deploy search algorithm for unstructured Peer-to-Peer networks, the Adaptive Probabilistic Search method (APS). Our scheme utilizes feedback from previous searches to probabilistically guide future ones. Extensive simulation results show that APS achieves high success rates, increased number of discovered objects, very low bandwidth consumption and adaptation to changing topologies. UMIACS-TR-2003-21
Adaptive Pull-Based Data Freshness Policies for Diverse Update Patterns
(2004-01-29) Bright, Laura; Gal, Avigdor; Raschid, Louiqa
An important challenge to effective data delivery in wide area environments is maintaining the data freshness of objects using solutions that can scale to a large number of clients without incurring significant server overhead. Policies for maintaining data freshness are traditionally either push-based or pull-based. Push-based policies involve pushing data updates by servers; they may not scale to a large number of clients. Pull-based policies require clients to contact servers to check for updates; their effectiveness is limited by the difficulty of predicting updates. Models to predict updates generally rely on some knowledge of past updates. Their accuracy of prediction may vary and determining the most appropriate model is non-trivial. In this paper, we present an adaptive pull-based solution to this challenge. We first present several techniques that use update history to estimate the freshness of cached objects, and identify update patterns for which each technique is most effective. We then introduce adaptive policies that can (automatically) choose a policy for an object based on its observed update patterns. Our proposed policies improve the freshness of cached data and reduce costly contacts with remote servers without incurring the large server overhead of push-based policies, and can scale to a large number of clients. Using trace data from a data-intensive website as well as two email logs, we show that our adaptive policies can adapt to diverse update patterns and provide significant improvement compared to a single policy. (UMIACS-TR-2004-01)
Adaptive Replication in Peer-to-Peer Systems
(2003-08-01) Gopalakrishnan, Vijay; Silaghi, Bujor; Bhattacharjee, Bobby; Keleher, Pete
Recent work on peer-to-peer systems has demonstrated the ability to deliver low latencies and good load balance when demand for data items is relatively uniform. We describe a lightweight, adaptive, and system-neutral replication protocol, LAR, that delivers low latencies and good load balance even when demand is heavily skewed. Simulation of LAR in combination with both the Chord and TerraDir systems shows that LAR quickly adapts to non-uniformity in both the underlying system topology and in the input stream. Further, we demonstrate better performance than functionally similar application-layer protocols, using an order of magnitude less network bandwidth. (UMIACS-TR-2003-83)
Adaptive Runtime Support for Direct Simulation Monte Carlo Methods on Distributed Memory Architectures
(1998-10-15) Moon, Bongki; Saltz, Joel
In highly adaptive irregular problems such as many Particle-In-Cell (PICJ codes and Dimet Simulation Monte Carlo (DSMCJ codes, data access patterns may vary from time step to time step. This fluctuation may hinder efficient utilization of distributed memory parallel computers because of the resulting overhead for data redistribution and dynamic load balancing. To efficiently parallelize such adaptive irregular problems on distributed memory parallel computers, several issues such as effective methods for domain partitioning and fast data transportation must be addressed. This paper presents efficient runtime support methods for such problems. A simple one-dimensional domain partitioning method is implemented and compared with unstructured mesh partitioners such as recursive coordinate bisection and recursive inertial bisection. A remapping decision policy has been investigated for dynamic load balancing on S-dimensional DSMC codes. Performance results are presented (Also cross-referenced as UMIACS-TR-95-27)
Adaptive Use of Iterative Methods in Interior Point Methods for Linear Programming
(1998-10-15) Wang, Weichung; O'Leary, Dianne P.
In this work we devise efficient algorithms for finding the search directions for interior point methods applied to linear programming problems. There are two innovations. The first is the use of updating of preconditioners computed for previous barrier parameters. The second is an adaptive automated procedure for determining whether to use a direct or iterative solver, whether to reinitialize or update the preconditioner, and how many updates to apply. These decisions are based on predictions of the cost of using the different solvers to determine the next search direction, given costs in determining earlier directions. These ideas are tested by applying a modified version of the OB1-R code of Lustig, Marsten, and Shanno to a variety of problems from the NETLIB and other collections. If a direct method is appropriate for the problem, then our procedure chooses it, but when an iterative procedure is helpful, substantial gains in efficiency can be obtained. (Also cross-referenced as UMIACS-TR-95-111)
Adaptive Use of Iterative Methods in Predictor-Corrector Interior Point Methods for Linear Programming
(1999-04-06) Wang, Weichung; O'Leary, Dianne P.
In this work we devise efficient algorithms for finding the search directions for interior point methods applied to linear programming problems. There are two innovations. The first is the use of updating of preconditioners computed for previous barrier parameters. The second is an adaptive automated procedure for determining whether to use a direct or iterative solver, whether to reinitialize or update the preconditioner, and how many updates to apply. These decisions are based on predictions of the cost of using the different solvers to determine the next search direction, given costs in determining earlier directions. We summarize earlier results using a modified version of the OB1-R code of Lustig, Marsten, and Shanno, and we present results from a predictor-corrector code PCx modified to use adaptive iteration. If a direct method is appropriate for the problem, then our procedure chooses it, but when an iterative procedure is helpful, substantial gains in efficiency can be obtained. (Also cross-referenced as UMIACS-TR-99-21)