@article {14953,
	title = {Constructing Inverted Files: To MapReduce or Not Revisited},
	volume = {UMIACS-TR-2012-03},
	year = {2012},
	month = {2012/01/26/},
	institution = {Instititue for Advanced Computer Studies, Univ of Maryland, College Park},
	abstract = {Current high-throughput algorithms for constructing inverted files allfollow the MapReduce framework, which presents a high-level programming
model that hides the complexities of parallel programming. In this
paper, we take an alternative approach and develop a novel strategy that
exploits the current and emerging architectures of multicore processors.
Our algorithm is based on a high-throughput pipelined strategy that
produces parallel parsed streams, which are immediately consumed at the
same rate by parallel indexers. We have performed extensive tests of our
algorithm on a cluster of 32 nodes, and were able to achieve a
throughput close to the peak throughput of the I/O system: a throughput
of 280 MB/s on a single node and a throughput that ranges between 5.15
GB/s (1 Gb/s Ethernet interconnect) and 6.12GB/s (10Gb/s InfiniBand
interconnect) on a cluster with 32 nodes for processing the ClueWeb09
dataset. Such a performance represents a substantial gain over the best
known MapReduce algorithms even when comparing the single node
performance of our algorithm to MapReduce algorithms running on large
clusters.  Our results shed a light on the extent of the performance
cost that may be incurred by using the simpler, higher-level MapReduce
programming model for large scale applications.
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/12171},
	author = {Wei, Zheng and JaJa, Joseph F.}
}
@article {13738,
	title = {Citation Handling for Improved Summarization of Scientific Documents},
	year = {2011},
	month = {2011/07/25/},
	institution = {Instititue for Advanced Computer Studies, Univ of Maryland, College Park},
	abstract = {In this paper we present the first steps toward improving summarizationof scientific documents through citation analysis and parsing. Prior
work (Mohammad et al., 2009) argues that citation texts (sentences that
cite other papers) play a crucial role in automatic summarization of a
topical area, but did not take into account the noise introduced by the
citations themselves. We demonstrate that it is possible to improve
summarization output through careful handling of these citations. We
base our experiments on the application of an improved trimming approach
to summarization of citation texts extracted from Question-Answering and
Dependency-Parsing documents. We demonstrate that confidence scores from
the Stanford NLP Parser (Klein and Manning, 2003) are significantly
improved, and that Trimmer (Zajic et al., 2007), a sentence-compression
tool, is able to generate higher-quality candidates. Our summarization
output is currently used as part of a larger system, Action Science
Explorer (ASE) (Gove, 2011).
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/11822},
	author = {Whidby,Michael and Zajic, David and Dorr, Bonnie J}
}
@article {14952,
	title = {Constructing Inverted Files on a Cluster of Multicore Processors Near Peak I/O Throughput},
	volume = {UMIACS-TR-2011-03},
	year = {2011},
	month = {2011/03/03/},
	institution = {Instititue for Advanced Computer Studies, Univ of Maryland, College Park},
	abstract = {We develop a new strategy for processing a collection of documents on a cluster of multicore processors to build the inverted files at almost the peak I/O throughput of the underlying system. Our algorithm is based on a number of novel techniques including: (i) a high-throughput pipelined strategy that produces parallel parsed streams that are consumed at the same rate by parallel indexers; (ii) a hybrid trie and B-tree dictionary data structure that enables efficient parallel construction of the global dictionary; and (iii) a partitioning strategy of the work of the indexers using random sampling, which achieve extremely good load balancing with minimal communication overhead. We have performed extensive tests of our algorithm on a cluster of 32 nodes, each consisting of two Intel Xeon X5560 Quad-core, and were able to achieve a throughput close to the peak throughput of the I/O system. In particular, we achieve a throughput of 280 MB/s on a single node and a throughput of 6.12GB/s on a cluster with 32 nodes for processing the ClueWeb09 dataset. Similar results were obtained for widely different datasets. The throughput of our algorithm is superior to the best known algorithms reported in the literature even when compared to those running on much larger clusters.},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/11311},
	author = {Wei, Zheng and JaJa, Joseph F.}
}
@article {19266,
	title = {Dataflow-based Design and Implementation of Image Processing Applications},
	year = {2011},
	month = {2011},
	abstract = {Dataflow is a well known computational model and is widely used forexpressing the functionality of digital signal processing (DSP)
applications, such as audio and video data stream processing, digital
communications, and image processing.  These applications usually
require real-time processing capabilities and have critical performance
constraints. Dataflow provides a formal mechanism for describing
specifications of DSP applications, imposes minimal data-dependency
constraints in specifications, and is effective in exposing and
exploiting task or data level parallelism for achieving high performance
implementations.
To demonstrate dataflow-based design methods in a manner that is
concrete and easily adapted to different platforms and back-end design
tools, we present in this report a number of case studies based on the
lightweight dataflow (LWDF) programming methodology. LWDF is designed as
a "minimalistic" approach for integrating coarse grain dataflow
programming structures into arbitrary simulation- or platform-oriented
languages, such as C, C++, CUDA, MATLAB, SystemC, Verilog, and VHDL. In
particular, LWDF requires minimal dependence on specialized tools or
libraries.  This feature --- together with the rigorous adherence to
dataflow principles throughout the LWDF design framework --- allows
designers to integrate and experiment with dataflow modeling approaches
relatively quickly and flexibly into existing design methodologies and
processes.
},
	keywords = {Technical Report},
	isbn = {UMIACS-TR-2011-11},
	doi = {Technical Report},
	url = {http://drum.lib.umd.edu//handle/1903/11403},
	author = {Chung-Ching Shen and Plishker,William and Bhattacharyya, Shuvra S.}
}
@article {19257,
	title = {The DSPCAD Lightweight Dataflow Environment: Introduction to LIDE Version 0.1},
	year = {2011},
	month = {2011},
	abstract = {LIDE (the DSPCAD Lightweight Dataflow Environment) is a flexible,lightweight design environment that allows designers to experiment with
dataflow-based approaches for design and implementation of digital
signal processing (DSP) systems.  
LIDE contains libraries of dataflow graph elements  (primitive actors,
hierarchical actors, and edges) and utilities that assist designers in
modeling, simulating, and implementing DSP systems using formal dataflow
techniques.  The libraries of dataflow graph elements (mainly actors)
contained in LIDE provide useful building blocks that can be used to
construct signal processing applications, and that can be used as
examples that designers can adapt to create their own, customized LIDE
actors.  Furthermore, by using LIDE along with the DSPCAD Integrative
Command Line Environment (DICE), designers can efficiently create and
execute unit tests for user-designed actors. 
This report provides an introduction to LIDE. The report includes
details on the process for setting up the LIDE environment, and covers
methods for using pre-designed libraries of graph elements, as well as
creating user-designed libraries and associated utilities using the C
language. The report also gives an introduction to the C language
plug-in for dicelang. This plug-in, called dicelang-C, provides features
for efficient C-based project development and maintenance that are
useful to apply when working with LIDE.
},
	keywords = {Technical Report},
	isbn = {UMIACS-TR-2011-17},
	doi = {Technical Report},
	url = {http://drum.lib.umd.edu//handle/1903/12147},
	author = {Chung-Ching Shen and Wang, Lai-Huei and Cho, Inkeun and Kim, Scott and Won, Stephen and Plishker,William and Bhattacharyya, Shuvra S.}
}
@article {13942,
	title = {A Hierarchical Algorithm for Fast Debye Summation with Applications to Small Angle Scattering},
	journal = {Technical Reports from UMIACS},
	year = {2011},
	month = {2011/09/01/},
	abstract = {Debye summation, which involves the summation of sinc functions of distances between all pair of atoms in three dimensional space, arises in computations performed in crystallography, small/wide angle X-ray scattering (SAXS/WAXS) and small angle neutron scattering (SANS). Direct evaluation of Debye summation has quadratic complexity, which results in computational bottleneck when determining crystal properties, or running structure refinement protocols that involve SAXS or SANS, even for moderately sized molecules. We present a fast approximation algorithm that efficiently computes the summation to any prescribed accuracy epsilon in linear time. The algorithm is similar to the fast multipole method (FMM), and is based on a hierarchical spatial decomposition of the molecule coupled with local harmonic expansions and translation of these expansions. An even more efficient implementation is possible when the scattering profile is all that is required, as in small angle scattering reconstruction (SAS) of macromolecules. We examine the relationship of the proposed algorithm to existing approximate methods for profile computations, and provide detailed description of the algorithm, including error bounds and algorithms for stable computation of the translation operators. Our theoretical and computational results show orders of magnitude improvement in computation complexity over existing methods, while maintaining prescribed accuracy.},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/11857},
	author = {Gumerov, Nail A. and Berlin,Konstantin and Fushman, David and Duraiswami, Ramani}
}
@article {13941,
	title = {Kernelized Renyi distance for subset selection and similarity scoring},
	journal = {Technical Reports of the Computer Science Department},
	year = {2011},
	month = {2011/10/12/},
	abstract = {Renyi entropy refers to a generalized class of entropies that have beenused in several applications. In this work, we derive a non-parametric
distance between distributions based on the quadratic Renyi entropy. The
distributions are estimated via Parzen density estimates. The quadratic
complexity of the distance evaluation is mitigated with GPU-based
parallelization. This results in an efficiently evaluated non-parametric
entropic distance - the kernelized Renyi distance or the KRD. We adapt
the KRD into a similarity measure and show its application to speaker
recognition. We further extend KRD to measure dissimilarities between
distributions and illustrate its applications to statistical subset
selection and dictionary learning for object recognition and pose
estimation.
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/12132},
	author = {Srinivasan,Balaji Vasan and Duraiswami, Ramani}
}
@article {19264,
	title = {Using the DSPCAD Integrative Command-Line Environment: User{\textquoteright}s Guide for DICE Version 1.1},
	year = {2011},
	month = {2011},
	abstract = {This document provides instructions on setting up, starting up, andbuilding DICE and its key companion packages, dicemin and dicelang. This
installation process is based on a general set of conventions, which we
refer to as the DICE organizational conventions, for software packages.
The DICE organizational conventions are specified in this report. These
conventions are applied in DICE, dicemin, and dicelang, and also to
other software packages that are developed in the Maryland DSPCAD
Research Group.
},
	keywords = {Technical Report},
	isbn = {UMIACS-TR-2011-13},
	doi = {Technical Report},
	url = {http://drum.lib.umd.edu//handle/1903/11804},
	author = {Bhattacharyya, Shuvra S. and Chung-Ching Shen and Plishker,William and Sane, Nimish and Zaki, George}
}
@article {17970,
	title = {Global Contours},
	volume = {CS-TR-4957},
	year = {2010},
	month = {2010/05/05/},
	institution = {Department of Computer Science, University of Maryland, College Park},
	abstract = {We present a multi-scale approach that uses Laplacian eigenvectorsto extract globally significant contours from an image. The
input images are mapped into the Laplacian space by using Laplacian
eigenvectors. This mapping causes globally significant pixels
along the contours to expand in the Laplacian space. The measure
of the expansion is used to compute the Global Contours. We apply
our scheme to real color images and compare it with several other
methods that compute image and color saliency. The contours calculated
by our method reflect global properties of the image and are
complementary to classic center-surround image saliency methods.
We believe that hybrid image saliency algorithms that combine our
method of Global Contours with center-surround image saliency
algorithms will be able to better characterize the most important
regions of images than those from just using contours calculated
using bottom-up approaches.
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/10072},
	author = {Bista, Sujal and Varshney, Amitabh}
}
@article {13085,
	title = {Partial least squares on graphical processor for efficient pattern recognition},
	journal = {Technical Reports of the Computer Science Department},
	year = {2010},
	month = {2010/10/18/},
	abstract = {Partial least squares (PLS) methods have recently been used for many patternrecognition problems in computer vision. Here, PLS is primarily used as a
supervised dimensionality reduction tool to obtain effective feature
combinations for better learning. However, application of PLS to large datasets
is hindered by its higher computational cost. We propose an approach to
accelerate the classical PLS algorithm on graphical processors to obtain the
same performance at a reduced cost. Although, PLS modeling is practically an
offline training process, accelerating it helps large scale modeling. The
proposed acceleration is shown to perform well and it yields upto ~30X speedup,
It is applied on standard datasets in human detection and face recognition.
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/10975},
	author = {Srinivasan,Balaji Vasan and Schwartz,William Robson and Duraiswami, Ramani and Davis, Larry S.}
}
@article {13950,
	title = {Random sampling for estimating the performance of fast summations},
	journal = {Technical Reports of the Computer Science Department},
	year = {2010},
	month = {2010/10/18/},
	abstract = {Summation of functions of N source points evaluated at M target pointsoccurs commonly in many applications. To scale these approaches for large
datasets, many fast algorithms have been proposed. In this technical report, we
propose a Chernoff bound based efficient approach to test the performance of a
fast summation algorithms providing a probabilistic accuracy. We further
validate and use our approach in separate comparisons.
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/10976},
	author = {Srinivasan,Balaji Vasan and Duraiswami, Ramani}
}
@article {15667,
	title = {Realistic Compression of Kinetic Sensor Data},
	volume = {CS-TR-4959},
	year = {2010},
	month = {2010/06/06/},
	institution = {Department of Computer Science, University of Maryland, College Park},
	abstract = {We introduce a realistic analysis for a framework for storing andprocessing kinetic data observed by sensor networks. The massive data
sets generated by these networks motivates a significant need for
compression. We are interested in the kinetic data generated by a finite
set of objects moving through space. Our previously introduced framework
and accompanying compression algorithm assumed a given set of sensors,
each of which continuously observes these moving objects in its
surrounding region. The model relies purely on sensor observations; it
allows points to move freely and requires no advance notification of
motion plans. Here, we extend the initial theoretical analysis of this
framework and compression scheme to a more realistic setting. We extend
the current understanding of empirical entropy to introduce definitions
for joint empirical entropy, conditional empirical entropy, and
empirical independence. We also introduce a notion of limited
independence between the outputs of the sensors in the system. We show
that, even with this notion of limited independence and in both the
statistical and empirical settings, the previously introduced
compression algorithm achieves an encoding size on the order of the
optimal.
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu//handle/1903/10114},
	author = {Friedler,Sorelle A. and Mount, Dave}
}
@article {13968,
	title = {Computation of the head-related transfer function via the boundary element method and representation via the spherical harmonic spectrum},
	journal = {Technical Reports from UMIACS UMIACS-TR-2009-06},
	year = {2009},
	month = {2009/05/15/},
	abstract = {The head-related transfer function (HRTF) is computed using the fast multipole accelerated boundary element method. For efficiency, the HRTF is computed using the reciprocity principle, by placing a source at the ear and computing its field. Analysis is presented to modify the boundary value problem accordingly. To compute the HRTF corresponding to different ranges via a single computation, a compact and accurate representation of the HRTF, termed the spherical spectrum, is developed. Computations are reduced to a two stage process, the computation of the spherical spectrum and a subsequent evaluation of the HRTF. This representation allows easy interpolation and range extrapolation of HRTFs.HRTF computations are performed for the range of audible frequencies up to 20 kHz for several models including a sphere, human head models (for the {\textquotedblleft}Fritz{\textquotedblright} and {\textquotedblleft}Kemar{\textquotedblright}), and head and torso model (the Kemar manikin). Comparisons between the different cases and analysis of limiting cases is provided. Comparisons with the computational data of other authors and available experimental data are conducted and show satisfactory agreement for the frequencies for which reliable experimental data is available. Our results show that, given a good mesh it is feasible to compute the HRTF over the full audible range on a regular personal computer.
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/9085},
	author = {Gumerov, Nail A. and O{\textquoteright}donovan,Adam and Duraiswami, Ramani and Zotkin,Dmitry N}
}
@article {14949,
	title = {Archiving Temporal Web Information: Organization of Web Contents for Fast Access and Compact Storage},
	volume = {UMIACS-TR-2008-08},
	year = {2008},
	month = {2008/04/07/},
	institution = {Instititue for Advanced Computer Studies, Univ of Maryland, College Park},
	abstract = {We address the problem of archiving dynamic web contents oversignificant time spans. Current schemes crawl the web contents at
regular time intervals and archive the contents after each crawl
regardless of whether or not the contents have changed between
consecutive crawls. Our goal is to store newly crawled web contents
only when they are different than the previous crawl, while ensuring
accurate and quick retrieval of archived contents based on arbitrary
temporal queries over the archived time period. In this paper, we
develop a scheme that stores unique temporal web contents in
containers following the widely used ARC/WARC format, and that
provides quick access to the archived contents for arbitrary temporal
queries. A novel component of our scheme is the use of a new indexing
structure based on the concept of persistent or multi-version data
structures. Our scheme can be shown to be asymptotically optimal both
in storage utilization and insert/retrieval time. We illustrate the
performance of our method on two very different data sets from the
Stanford WebBase project, the first reflecting very dynamic web
contents and the second relatively static web contents. The
experimental results clearly illustrate the substantial storage
savings achieved by eliminating duplicate contents detected between
consecutive crawls, as well as the speed at which our method can find
the archived contents specified through arbitrary temporal queries.
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/7569},
	author = {Song,Sangchul and JaJa, Joseph F.}
}
@article {13985,
	title = {Fast Multipole Accelerated Boundary Element Methods for the 3D Helmholtz Equation},
	journal = {Technical Reports from UMIACS UMIACS-TR-2008-03},
	year = {2008},
	month = {2008/01/02/},
	abstract = {The development of a fast multipole method accelerated iterativesolution of the boundary element equations for large problems involving
hundreds of thousands elements for the Helmholtz equations in 3D is
described. The BEM requires several approximate computations (numerical
quadrature, approximations of the boundary shapes using elements) and
the convergence criterion for iterative computation. When accelerated
using the FMM, these different errors must all be chosen in a way that
on the one hand excess work is not done and on the other that the error
achieved by the overall computation is acceptable. Details of
translation operators used, choices of representations, and boundary
element integration consistent with these approximations are described.
A novel preconditioner for accelerating convergence, using a low
accuracy FMM accelerated solver as a right preconditioner is also
described. Results of the developed and tested solvers for boundary
value problems for the Helmholtz equations using the solver are
presented for the number of unknowns N <= 106 and product of wavenumber
k times domain size D, kD <= 200 and show good performance close to
theoretical expectations.
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/7504},
	author = {Gumerov, Nail A. and Duraiswami, Ramani}
}
@article {14514,
	title = {How friendship links and group memberships affect the privacy of individuals in social networks},
	volume = {UMIACS-TR-2008-16},
	year = {2008},
	month = {2008/07/01/},
	institution = {Instititue for Advanced Computer Studies, Univ of Maryland, College Park},
	abstract = {In order to address privacy concerns, many social media websites allow users to hide their personal profiles from the public. In this work, we show how an adversary can exploit a social network with a mixture of public and private user profiles to predict the private attributes of users. We map this problem to a relational classification problem and we propose a simple yet powerful model that uses group features and group memberships of users to perform multi-value classification. We compare its efficacy against several other classification approaches. Our results show that even in the case when there is an option for making profile attributes private, if links and group affiliations are known, users{\textquoteright} privacy in social networks may be compromised. On a dataset from a well-known social-media website, we could easily recover the sensitive attributes for half of the private-profile users with a high accuracy when as much as half of the profiles are private. To the best of our knowledge, this is the first work that uses link-based and group-based classification to study privacy implications in social networks. We conclude with a discussion of our findings and the broader applicability of our proposed model.},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/8691},
	author = {Zheleva,Elena and Getoor, Lise}
}
@article {18484,
	title = {A spherical microphone array based system for immersive audio scene rendering},
	volume = {UMIACS-TR-2008-09},
	year = {2008},
	month = {2008/03/25/},
	institution = {Instititue for Advanced Computer Studies, Univ of Maryland, College Park},
	abstract = {For many applications it is necessary to capture an acoustic field and present it for human listeners, creating the same acoustic perception for them as if they were actually present in the scene. Possible applications of this technique include entertainment, education, military training, remote telepresence, surveillance, and others. Recently, there is much interest on the use of spherical microphone arrays in acoustic scene capture and reproduction application. We describe a 32-microphone spherical array based system implemented for spatial audio capture and reproduction. The array embeds hardware that is traditionally external, such as preamplifiers, filters, digital-to-analog converters, and USB interface adapter, resulting in a portable lightweight solution and requiring no hardware on PC side whatsoever other than a high-speed USB port. We provide capability analysis of the array and describe software suite developed for the application.},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu//handle/1903/7556},
	author = {O{\textquoteright}donovan,Adam and Zotkin,Dmitry N and Duraiswami, Ramani}
}
@article {14937,
	title = {ACE: A Novel Software Platform to Ensure the Integrity of Long Term Archives},
	volume = {UMIACS-TR-2007-07},
	year = {2007},
	month = {2007/01/31/},
	institution = {Instititue for Advanced Computer Studies, Univ of Maryland, College Park},
	abstract = {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.},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/4047},
	author = {Song,Sangchul and JaJa, Joseph F.}
}
@article {17690,
	title = {Analysis of the Residual Arnoldi Method},
	volume = {UMIACS-TR-2007-45},
	year = {2007},
	month = {2007/10/15/},
	institution = {Instititue for Advanced Computer Studies, Univ of Maryland, College Park},
	abstract = {The Arnoldi method generates a nested squences of orthonormal bases$U_{1},U_{2}, \ldots$ by orthonormalizing $Au_{k}$ against $U_{k}$.
Frequently these bases contain increasingly accurate approximations of
eigenparis from the periphery of the spectrum of $A$.  However, the
convergence of these approximations stagnates if $u_{k}$ is
contaminated by error.  It has been observed that if one chooses a
Rayleigh--Ritz approximation $(\mu_{k}, z_{k})$ to a chosen target
eigenpair $(\lambda, x)$ and orthonormalizes the residual $Az_{k -
}\mu_{k} z_{k}$, the approximations to $x$ (but not the other
eigenvectors) continue to converge, even when the residual is
contaminated by error.  The same is true of the shift-invert variant
of Arnoldi{\textquoteright}s method.  In this paper we give a mathematical analysis
of these new methods.
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/7428},
	author = {Lee,Che-Rung and Stewart, G.W.}
}
@article {13997,
	title = {Fast weighted summation of erfc functions},
	journal = {Technical Reports from UMIACS UMIACS-TR-2007-03},
	year = {2007},
	month = {2007/01/08/},
	abstract = {Abstract: Direct computation of the weighted sum of N complementaryerror functions at M points scales as O(MN). We present a O(M + N)
$\epsilon$-exact approximation algorithm to compute the same.
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/7535},
	author = {Raykar,Vikas C. and Duraiswami, Ramani and Krishnapuram,B.}
}
@article {14512,
	title = {Link-based Classification},
	volume = {UMIACS-TR-2007-11},
	year = {2007},
	month = {2007/02/19/},
	institution = {Instititue for Advanced Computer Studies, Univ of Maryland, College Park},
	abstract = {Over the past few years, a number of approximate inference algorithms fornetworked data have been put forth. We empirically compare the performance
of three of the popular algorithms: loopy belief propagation, mean field
relaxation labeling and iterative classification. We rate each algorithm
in terms of its robustness to noise, both in attribute values and
correlations across links. We also compare them across varying types of
correlations across links.
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/4298},
	author = {Sen,Prithviraj and Getoor, Lise}
}
@article {14508,
	title = {Predicting Protein-Protein Interactions Using Relational Features},
	volume = {CS-TR-4909},
	year = {2007},
	month = {2007/01/07/},
	institution = {Department of Computer Science, University of Maryland, College Park},
	abstract = {Proteins play a fundamental role in ever y process within the cell.Understanding how proteins interact, and the functional units they are
par t of, is important to furthering our knowledge of the entire
biological process. There has been a growing amount of work, both
experimental and computational, on determining the protein-protein
interaction network. Recently researchers have had success looking at
this as a relational learning problem. In this work, we further this
investigation, proposing several novel relational features for
predicting protein-protein interaction. These features can be used in
any classifier. Our approach allows large and complex networks to be
analyzed and is an alternative to using more expensive relational
methods. We show that we are able to get an accuracy of 81.7\% when
predicting new links from noisy high throughput data.
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/7555},
	author = {Licamele,Louis and Getoor, Lise}
}
@article {17678,
	title = {A Residual Inverse Power Method},
	volume = {UMIACS-TR-2007-09},
	year = {2007},
	month = {2007/02//},
	institution = {Instititue for Advanced Computer Studies, Univ of Maryland, College Park},
	abstract = {The inverse power method involves solving shifted equations of theform $(A -\sigma I)v = u$.  This paper describes a variant method in
which shifted equations may be solved to a fixed reduced accuracy
without affecting convergence.  The idea is to alter the right-hand
side to produce a correction step to be added to the current
approximations.  The digits of this step divide into two parts:
leading digits that correct the solution and trailing garbage.  Hence
the step can be be evaluated to a reduced accuracy corresponding to
the correcting digits.  The cost is an additional multiplication by
$A$ at each step to generate the right-hand side.  Analysis and
experiments show that the method is suitable for normal and mildly
nonnormal problems.
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/4260},
	author = {Stewart, G.W.}
}
@article {12248,
	title = {A Secure DHT via the Pigeonhole Principle},
	journal = {Technical Reports of the Computer Science Department, CS-TR-4884},
	year = {2007},
	month = {2007/09/24/},
	abstract = {The standard Byzantine attack model assumes no more than some fixedfraction of the participants are faulty. This assumption does not
accurately apply to peer-to-peer settings, where Sybil attacks and botnets
are realistic threats. We propose an attack model that permits an
arbitrary number of malicious nodes under the assumption that each node
can be classified based on some of its attributes, such as autonomous
system number or operating system, and that the number of classes with
malicious nodes is bounded (e.g., an attacker may exploit at most a few
operating systems at a time). In this model, we present a secure DHT,
evilTwin, which replaces a single, large DHT with sufficiently many
smaller instances such that it is impossible for an adversary to corrupt
every instance. Our system ensures high availability and low-latency
lookups, is easy to implement, does not require a complex Byzantine
agreement protocol, and its proof of security is a straightforward
application of the pigeonhole principle. The cost of security comes in the
form of increased storage and bandwidth overhead; we show how to reduce
these costs by replicating data and adaptively querying participants who
historically perform well. We use implementation and simulation to show
that evilTwin imposes a relatively small additional cost compared to
conventional DHTs.
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/7136},
	author = {Baden,Randy and Bender,Adam and Levin,Dave and Sherwood,Rob and Spring, Neil and Bhattacharjee, Bobby}
}
@article {16807,
	title = {System for 802.11 connectivity at high speed},
	volume = {UMIACS-TR-2007-27},
	year = {2007},
	month = {2007/05/13/},
	institution = {Instititue for Advanced Computer Studies, Univ of Maryland, College Park},
	abstract = {Measurements and ongoing research have shown that WLANconnection for moving vehicles is feasible. However none of the previous
work suggests a solution addressing a complete array of the challenges
in vehicular WLAN communications. To amend this we designed a system
that provides wireless connection roaming at high
velocities transparent to user level applications, and does not impose
additional requirements to existing infrastructures. It offers simple
deployment, security, and scalability. It remains efficient under -
intermittent connectivity conditions and supports heterogeneous network
mediums for increased robustness.
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu//handle/1903/4374},
	author = {Frangiadakis,Nikolaos and Kuklov,Danila and Roussopoulos, Nick}
}
@article {13338,
	title = {Topological Decompositions for 3D Non-manifold Simplicial Shapes},
	volume = {CS-TR-4855},
	year = {2007},
	month = {2007/02/06/},
	institution = {Department of Computer Science, University of Maryland, College Park},
	abstract = {Modeling and understanding complex non-manifold shapes is a key issue in several applications including form-feature identification in CAD/CAE, and shape recognition for Web searching. Geometric shapes are commonly discretized as simplicial 2- or 3-complexes embedded in the 3D Euclidean space. The topological structure of a non-manifold  simplicial shape can be analyzed through its decomposition into a collection of components with simpler topology. The granularity of the decomposition depends on the combinatorial complexity of the components. In this paper, we present topological tools for structural analysis of three-dimensional non-manifold shapes. This analysis is based on a topological decomposition at two different levels. We discuss the topological properties of the components at each level, and we present algorithms for computing such decompositions. We investigate the relations among the components, and propose a graph-based representation for such relations.},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/7429},
	author = {Hui,Annie and De Floriani, Leila}
}
@article {17893,
	title = {Using Content-Addressable Networks for Load Balancing in Desktop Grids},
	volume = {UMIACS-TR-2007-16},
	year = {2007},
	month = {2007/03/29/},
	institution = {Instititue for Advanced Computer Studies, Univ of Maryland, College Park},
	abstract = {Desktop grids combine Peer-to-Peer and Grid computing techniques to improvethe robustness, reliability and scalability of job execution
infrastructures.
However, efficiently matching incoming jobs to available system resources
and achieving good load balance in a fully decentralized and heterogeneous
computing environment is a challenging problem.
In this paper, we extend our prior work with a new decentralized algorithm
for maintaining approximate global load information, and a job pushing
mechanism that uses the global information to push jobs towards
underutilized portions of the system.
The resulting system more effectively balances load and improves overall
system throughput.
Through a comparative analysis of experimental results across different
system configurations and job profiles, performed via simulation, we show
that our system can reliably execute Grid applications on a distributed set
of resources both with low cost and with good load balance.
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu//handle/1903/4355},
	author = {Kim,Jik-Soo and Keleher,Peter and Marsh,Michael and Bhattacharjee, Bobby and Sussman, Alan}
}
@article {15051,
	title = {Web Archiving: Organizing Web Objects into Web Containers to Optimize Access},
	volume = {UMIACS-TR-2007-42},
	year = {2007},
	month = {2007/10/09/},
	institution = {Instititue for Advanced Computer Studies, Univ of Maryland, College Park},
	abstract = {The web is becoming the preferred medium for communicating and storinginformation pertaining to almost any human activity. However it is an
ephemeral medium whose contents are constantly changing, resulting in
a permanent loss of part of our cultural and scientific heritage on a
regular basis. Archiving important web contents is a very challenging
technical problem due to its tremendous scale and complex structure,
extremely dynamic nature, and its rich heterogeneous and deep
contents. In this paper, we consider the problem of archiving a linked
set of web objects into web containers in such a way as to minimize
the number of containers accessed during a typical browsing session.
We develop a method that makes use of the notion of PageRank and
optimized graph partitioning to enable faster browsing of archived web
contents. We include simulation results that illustrate the
performance of our scheme and compare it to the common scheme
currently used to organize web objects into web containers.
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/7426},
	author = {Song,Sangchul and JaJa, Joseph F.}
}
@article {14922,
	title = {Development of a Large-Scale Integrated Neurocognitive Architecture Part 1: Conceptual Framework},
	volume = {UMIACS-TR-2006-33},
	year = {2006},
	month = {2006/06/15/},
	institution = {Instititue for Advanced Computer Studies, Univ of Maryland, College Park},
	abstract = {The idea of creating a general purpose machine intelligence that capturesmany of the features of human cognition goes back at least to the earliest days
of artificial intelligence and neural computation. In spite of more than a
half-century of research on this issue, there is currently no existing approach
to machine intelligence that comes close to providing a powerful, general-purpose
human-level intelligence. However, substantial progress made during recent years
in neural computation, high performance computing, neuroscience and cognitive
science suggests that a renewed effort to produce a general purpose and adaptive
machine intelligence is timely, likely to yield qualitatively more powerful
approaches to machine intelligence than those currently existing, and certain
to lead to substantial progress in cognitive science, AI and neural computation.
In this report, we outline a conceptual framework for the long-term development
of a large-scale machine intelligence that is based on the modular organization,
dynamics and plasticity of the human brain. Some basic design principles are
presented along with a review of some of the relevant existing knowledge about
the neurobiological basis of cognition.  Three intermediate-scale prototypes for
parts of a larger system are successfully implemented, providing support for the
effectiveness of several of the principles in our framework. We conclude that a
human-competitive neuromorphic system for machine intelligence is a viable long-
term goal, but that for the short term, substantial integration with more
standard symbolic methods as well as substantial research will be needed to make
this goal achievable.
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu//handle/1903/3665},
	author = {Reggia, James A. and Tagamets,Malle and Contreras-Vidal,Jose and Weems,Scott and Jacobs, David W. and Winder,Ransom and Chabuk,Timur}
}
@article {14920,
	title = {Development of a Large-Scale Integrated Neurocognitive Architecture - Part 2: Design and Architecture},
	volume = {UMIACS-TR-2006-43},
	year = {2006},
	month = {2006/10//},
	institution = {Instititue for Advanced Computer Studies, Univ of Maryland, College Park},
	abstract = {In Part 1 of this report, we outlined a framework for creating an intelligent agentbased upon modeling the large-scale functionality of the human brain. Building on
those results, we begin Part 2 by specifying the behavioral requirements of a
large-scale neurocognitive architecture. The core of our long-term approach remains
focused on creating a network of neuromorphic regions that provide the mechanisms
needed to meet these requirements. However, for the short term of the next few years,
it is likely that optimal results will be obtained by using a hybrid design that
also includes symbolic methods from AI/cognitive science and control processes from the
field of artificial life. We accordingly propose a three-tiered architecture that
integrates these different methods, and describe an ongoing computational study of a
prototype {\textquoteright}mini-Roboscout{\textquoteright} based on this architecture. We also examine the implications
of some non-standard computational methods for developing a neurocognitive agent.
This examination included computational experiments assessing the effectiveness of
genetic programming as a design tool for recurrent neural networks for sequence
processing, and experiments measuring the speed-up obtained for adaptive neural
networks when they are executed on a graphical processing unit (GPU) rather than a
conventional CPU. We conclude that the implementation of a large-scale neurocognitive
architecture is feasible, and outline a roadmap for achieving this goal.
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu//handle/1903/3957},
	author = {Reggia, James A. and Tagamets,M. and Contreras-Vidal,J. and Jacobs, David W. and Weems,S. and Naqvi,W. and Winder,R. and Chabuk,T. and Jung,J. and Yang,C.}
}
@article {13261,
	title = {A dimension-independent simplicial data structure for non-manifold shapes},
	volume = {CS-TR-4794},
	year = {2006},
	month = {2006/04/07/},
	institution = {Department of Computer Science, University of Maryland, College Park},
	abstract = {We consider the problem of representing and manipulating non-manifoldmulti-dimensional shapes, discretized as $d$-dimensional simplicial
Euclidean complexes, for modeling finite element meshes derived from CAD
models. We propose a dimension-independent data structure for  simplicial
complexes, that we call the {\em Incidence Simplicial (IS)} data
structure. The IS data structure is scalable to manifold complexes, and
supports efficient traversal and update algorithms for performing
topological modifications, such as hole removal or dimension reduction. It
has the same expressive power and performances as the incidence graph,
commonly used for dimension-independent representation of simplicial and
cell complexes, but it is much more compact.  We present efficient
algorithms for traversing, generating and updating a simplicial complex
described as an IS data structure. We compare the IS data structure with
dimension-independent and dimension-specific representations for
simplicial complexes.  Finally, we briefly  discuss two applications that
the IS data structure supports, namely decomposition of non-manifold
objects for effective geometric reasoning, and multi-resolution modeling
of non-manifold multi-dimensional shapes.
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/7427},
	author = {Hui,Annie and De Floriani, Leila}
}
@article {14959,
	title = {Efficient Isosurface Extraction for Large Scale Time-Varying Data Using the Persistent Hyperoctree (PHOT)},
	volume = {UMIACS-TR-2006-01},
	year = {2006},
	month = {2006/01/13/T20:3},
	institution = {Instititue for Advanced Computer Studies, Univ of Maryland, College Park},
	abstract = {We introduce the Persistent HyperOcTree (PHOT) to handle the4D 		isocontouring problem for large scale time-varying data
sets. 			This novel data structure is provably space
efficient and 			optimal in retrieving active cells. More
importantly, the set of 		active cells for any possible
isovalue are already organized in 		a Compact Hyperoctree, which
enables very efficient slicing of 		the isocontour along spatial
and temporal dimensions. 			Experimental results based
on the very large Richtmyer-Meshkov 		instability data set
demonstrate the effectiveness of our 			approach. This
technique can also be used for other isosurfacing 		schemes such
as view-dependent isosurfacing and ray-tracing,
which will benefit from the inherent hierarchical structure
associated with the active cells.
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/3035},
	author = {Shi,Qingmin and JaJa, Joseph F.}
}
@article {17696,
	title = {EIGENTEST: A Test Matrix Generator for Large-Scale Eigenproblems},
	volume = {UMIACS-TR-2006-07},
	year = {2006},
	month = {2006/02/13/T19:4},
	institution = {Instititue for Advanced Computer Studies, Univ of Maryland, College Park},
	abstract = {Eigentest is a package that produces real test matrices with knowneigensystems.  A test matrix, called an eigenmat, is generated in a
factored form, in which the user can specify the eigenvalues and has
some control over the condition of the eigenvalues and eigenvectors.
An eigenmat A of order n requires only O(n) storage for its
representation.  Auxiliary programs permit the computation of
(A - sI)*b, (A - sI){\textquoteright}*b, inv(A - sI)*b, and inv(A - sI)*b in O(n)
operations.  A special routine computes specified eigenvectors of an
eigenmat and the condition of its eigenvalue.  Thus eigenmats are
suitable for testing algorithms based on Krylov sequences, as well as
others based on matrix-vector products.  This paper introduces the
eigenmat and describes implementations in Fortran~77, Fortran~95, C,
and Matlab.
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/3328},
	author = {Lee,Che Rung and Stewart, G.W.}
}
@article {17736,
	title = {The Gram-Schmidt Algorithm and Its Variations},
	volume = {UMIACS-TR-2004-84},
	year = {2006},
	month = {2006/01/13/},
	institution = {Instititue for Advanced Computer Studies, Univ of Maryland, College Park},
	abstract = {The Gram--Schmidt algorithm is a widely used method fororthogonalizing a sequence of vectors.  It comes in two forms:
classical Gram--Schmidt and modified Gram--Schmidt, each of whose
operations can be ordered in different ways.  This expository paper
gives a systematic treatment of this confusing variety of algorithms.
It also treats the numerical issue of loss of orthogonality and
reorthogonalization as well as the implementation of column pivoting.
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/3036},
	author = {Stewart, G.W.}
}
@article {12269,
	title = {KeyChains: A Decentralized Public-Key Infrastructure},
	journal = {Technical Reports from UMIACS, UMIACS-TR-2006-12},
	year = {2006},
	month = {2006/03/02/},
	abstract = {A Certification Authority (CA) can be used to certify keys and build apublic-key infrastructure (PKI) when all users trust the same CA.  A
decentralized PKI trades off absolute assurance on keys for
independence from central control and improved scalability and
robustness.  The PGP {\textquoteleft}{\textquoteleft}web of trust{\textquoteright}{\textquoteright} model has been suggested as a
decentralized certification system, and has been used with great
success for secure email.  Although the PGP web of trust model allows
anyone to issue certificates which can be used to form certificate
chains, the discovery and construction of certificate chains relies on
centralized keyservers to store certificates and respond to queries.
In this paper, we design and implement KeyChains, a peer-to-peer
system which incorporates a novel lookup mechanism specifically
tailored to the task of generating and retrieving certificate chains
in completely unstructured networks. By layering our system on top of
the web of trust model, we thus obtain the first PKI which is truly
decentralized in all respects.  Our analysis and simulations show that
the resulting system is both efficient and secure.
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/3332},
	author = {Morselli,Ruggero and Bhattacharjee, Bobby and Katz, Jonathan and Marsh,Michael A}
}
@article {12266,
	title = {Matching Jobs to Resources in Distributed Desktop Grid Environments},
	journal = {Technical Reports from UMIACS, UMIACS-TR-2006-15},
	year = {2006},
	month = {2006/04//},
	abstract = {Desktop grids use opportunistic sharing to exploit large collectionsof personal computers and workstations across the Internet and can
achieve tremendous computing power with low cost.
However, current systems are typically based on a traditional client-server
architecture, which has inherent shortcomings with respect to robustness,
reliability and scalability.  In this paper, we propose a decentralized,
robust, highly available, and scalable infrastructure to match incoming
jobs to available resources.  The key idea behind our proposed system is to
leverage information provided by an underlying peer-to-peer system to
create a hierarchical Rendezvous Node Tree, which performs the matching
efficiently.  Our experimental results obtained via simulation show that we
can effectively match jobs with varying levels of resource constraints to
available nodes and maintain good load balance in a fully decentralized
heterogeneous computational environment.
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/3669},
	author = {Kim,Jik-Soo and Bhattacharjee, Bobby and Keleher, Peter J. and Sussman, Alan}
}
@article {18010,
	title = {Mesh-of-Trees and Alternative Interconnection Networks for Single Chip Parallel Processing (Extended Abstract)},
	year = {2006},
	month = {2006/06//},
	abstract = {Many applications have stimulated the recent surge of interest single-chip parallel processing. In such machines, it is crucial to implement a high-throughput low-latency interconnection network to connect the on-chip components, especially the processing units and the memory units. In this paper, we propose a new mesh of trees (MoT) implementation of the interconnection network and evaluate it relative to metrics such as wire area, register count, total switch delay, maximum throughput, latency-throughput relation and delay effects of long wires. We show that on-chip interconnection networks can facilitate higher bandwidth between processors and shared first-level cache than previously considered possible. This has significant impact for chip multiprocessing. MoT is also compared, both analytically and experimentally, to some other traditional network topologies, such as hypercube, butterfly, fat trees and butterfly fat trees. When we evaluate a 64-terminal MoT network at 65nm technology, concrete results show that MoT provides higher throughput and lower latency especially when the input traffic (or the on-chip parallelism) is high, at the cost of larger area. A recurring problem in networking and communication is that of achieving good sustained throughput in contrast to just high theoretical peak performance that does not materialize for typical work loads. Our quantitative results demonstrate a clear advantage of the proposed MoT network in the context of single-chip parallel processing.},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/3678},
	author = {Balkan,Aydin O. and Gang Qu and Vishkin, Uzi}
}
@article {18011,
	title = {Models for Advancing PRAM and Other Algorithms into Parallel Programs for a PRAM-On-Chip Platform},
	year = {2006},
	month = {2006/05/18/},
	abstract = {A bold vision that guided this work is as follows: (i) a parallel algorithms and programming course could become a standard course in every undergraduate computer science program, and (ii) this course could be coupled with a so-called PRAM-On-Chip architecture --- a commodity high-end multi-core computer architecture.In fact, the current paper is a tutorial on how to convert PRAM algorithms into efficient PRAM-On-Chip programs. Coupled with a text on PRAM algorithms as well as an available PRAM-On-Chip tool-chain, comprising a compiler and a simulator, the paper provides the missing link for upgrading a standard theoretical PRAM algorithms class to a parallel algorithms and programming class. Having demonstrated that such a course could cover similar programming projects and material to what is covered by a typical first serial algorithms and programming course, the paper suggests that parallel programming in the emerging multi-core era does not need to be more difficult than serial programming. If true, a powerful answer to the so-called parallel programming open problem is being provided. This open problem is currently the main stumbling block for the industry in getting the upcoming generation of multi-core architectures to improve single task completion time using easy-to-program application programmer interfaces. Known constraints of this open problem, such as backwards compatibility on serial code, are also addressed by the overall approach. 
More concretely, a widely used methodology for advancing parallel algorithmic thinking into parallel algorithms is revisited, and is extended into a methodology for advancing parallel algorithms to PRAM-On-Chip programs.  A performance cost model for the PRAM-On-Chip is also presented. It uses as complexity metrics the length of sequence of round trips to memory (LSRTM) and queuing delay (QD) from memory access queues, in addition to standard PRAM computation costs.  Highlighting the importance of LSRTM in determining performance is another contribution of the paper. Finally, some alternatives to PRAM algorithms, which, on one hand, are easier-to-think, but, on the other hand, suppress more architecture details, are also discussed.
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/3338},
	author = {Vishkin, Uzi and Caragea,George C. and Lee,Bryant}
}
@article {14933,
	title = {A Novel Information-Aware Octree for the Visualization of Large Scale Time-Varying Data},
	volume = {UMIACS-TR-2006-03},
	year = {2006},
	month = {2006/04/20/T16:3},
	institution = {Instititue for Advanced Computer Studies, Univ of Maryland, College Park},
	abstract = {Large scale scientific simulations are increasingly generatingvery large data sets that present substantial challenges to
current visualization systems. In this paper, we develop a new
scalable and efficient scheme for the visual exploration of 4-D
isosurfaces of time varying data by rendering the 3-D isosurfaces
obtained through an arbitrary axis-parallel hyperplane cut. The
new scheme is based on: (i) a new 4-D hierarchical indexing
structure, called  Information-Aware Octree; (ii) a
controllable delayed fetching technique; and (iii) an optimized
data layout. Together, these techniques enable efficient and
scalable out-of-core visualization of large scale time varying
data sets. We introduce an entropy-based dimension integration
technique by which the relative resolutions of the spatial and
temporal dimensions are established, and use this information to
design a compact size 4-D hierarchical indexing structure. We also
present scalable and efficient techniques for out-of-core
rendering. Compared with previous algorithms for constructing 4-D
isosurfaces, our scheme is substantially faster and requires much
less memory. Compared to the Temporal Branch-On-Need octree
(T-BON), which can only handle a subset of our queries, our
indexing structure is an order of magnitude smaller and is at
least as effective in dealing with the queries that the T-BON can
handle. We have tested our scheme on two large time-varying data
sets and obtained very good performance for a wide range of
isosurface extraction queries using an order of magnitude smaller
indexing structures than previous techniques. In particular, we
can generate isosurfaces at intermediate time steps very quickly.
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/3335},
	author = {Kim,Jusub and JaJa, Joseph F.}
}
@article {13166,
	title = {A One-Threshold Algorithm for Detecting Abandoned Packages Under Severe Occlusions Using a Single Camera},
	journal = {Technical Reports from UMIACS},
	year = {2006},
	month = {2006/02/13/T21:4},
	abstract = {We describe a single-camera system capable of detecting abandoned packages under severe occlusions, which leads to complications on several levels. The first arises when frames containing only background pixels are unavailable for initializing the background model - a problem for which we apply a novel discriminative measure. The proposed measure is essentially the probability of observing a particular pixel value, conditioned on the probability that no motion is detected, with the pdf on which the latter is based being estimated as a zero-mean and unimodal Gaussian distribution from observing the difference values between successive frames. We will show that such a measure is a powerful discriminant even under severe occlusions, and can deal robustly with the foreground aperture effect - a problem inherently caused by differencing successive frames. The detection of abandoned packages then follows at both the pixel and region level. At the pixel-level, an {\textquoteleft}{\textquoteleft}abandoned pixel{\textquoteright}{\textquoteright} is detected as a foreground pixel, at which no motion is observed. At the region-level, abandoned pixels are ascertained in a Markov Random Field (MRF), after which they are clustered. These clusters are only finally classified as abandoned packages, if they display temporal persistency in their size, shape, position and color properties, which is determined using conditional probabilities of these attributes. The algorithm is also carefully designed to avoid any thresholding, which is the pitfall of many vision systems, and which significantly improves the robustness of our system. Experimental results from real-life train station sequences demonstrate the robustness and applicability of our algorithm.},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/3329},
	author = {Lim,Ser-Nam and Davis, Larry S.}
}
@article {18009,
	title = {Programmer{\textquoteright}s Manual for XMTC Language, XMTC Compiler and XMT Simulator},
	journal = {Technical Reports from UMIACS, UMIACS-TR-2005-45},
	year = {2006},
	month = {2006/06//},
	abstract = {Explicit Multi-Threading (XMT) is a computing framework developed at the University of Maryland as part of a PRAM-on-chip vision (http://www.umiacs.umd.edu/users/vishkin/XMT). Much in the same way that performance programming of standard computers relies on C language, XMT performance programming is done using an extension of C called XMTC. This manual presents the second generation of XMTCprogramming paradigm. It is intended to be used by an
application programmer, who is new to XMTC. In the first part
of this technical report (UMIACS-TR 2005-45 Part 1 of 2), we
define and describe key concepts, list the limitations and restrictions,
and give examples. The second part (UMIACS-TR
2005-45 Part 2 of 2) is a brief tutorial, and it demonstrates the
basic programming concepts of XMTC language with examples and exercises.
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/3673},
	author = {Balkan,Aydin O. and Vishkin, Uzi}
}
@article {15695,
	title = {Routing in Delay Tolerant Networks Using Storage Domains},
	volume = {UMIACS-TR-2007-01},
	year = {2006},
	month = {2006/11/20/},
	institution = {Instititue for Advanced Computer Studies, Univ of Maryland, College Park},
	abstract = {In this paper, we present a routing algorithm for a class ofdynamic networks called the Delay Tolerant Networks (DTNs). The proposed
algorithm takes into account the quintessential DTN characteristic namely,
intermittent link connectivity. We modify the breadth first search (BFS)
algorithm to take into account link state changes and find the quickest
route between source and destination nodes. We adopt a message drop policy
at intermediate nodes to incorporate storage constraint. We also introduce
the idea of time-varying storage domains where all nodes connected for a
length of time act as a single storage unit by sharing the aggregated
storage capacity of the nodes. We evaluate the routing algorithm with and
without storage domain in an extensive simulation. We analyze the
performance using metrics such as delivery ratio, incomplete transfers
with no routes and dropped messages. The DTN topology dynamics are
analyzed by varying: number of nodes generating traffic, link probability,
link availability through combinations of downtime/uptime values, storage
per node, message size, and traffic. The delay performance of the proposed
algorithms is conceptually the same as flooding-based algorithms but
without the penalty of multiple copies. More significantly, we show that
the Quickest Storage Domain (Quickest SD) algorithm distributes the
storage demand across many nodes in the network topology, enabling
balanced load and higher network utilization. In fact, we show that for
the same level of performance, we can actually cut the storage requirement
in half using the Quickest SD algorithm.
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu//handle/1903/4024},
	author = {Mundur, Padma and Lee,Sookyoung and Seligman,Matthew}
}
@article {13167,
	title = {Task-Driven Video Collection},
	journal = {Technical Reports from UMIACS},
	year = {2006},
	month = {2006/01/23/T17:1},
	abstract = {Vision systems are increasingly being deployed to perform complexsurveillance tasks. While improved algorithms are being developed to perform
these tasks, it is also important that data suitable for these algorithms be acquired
- a non-trivial task in a dynamic and crowded scene viewed by multiple PTZ
cameras. In this paper, we describe a multi-camera system that collects images
and videos of moving objects in such scenes, subject to task constraints. The system
constructs "task visibility intervals" that contain information about what can
be sensed in future time intervals. Constructing these intervals requires prediction
of future object motion and consideration of several factors such as object
occlusion and camera control parameters. Using a plane-sweep algorithm, these
atomic intervals can be combined to form multi-task intervals, during which a
single camera can collect videos suitable for multiple tasks simultaneously. Although
cameras can then be scheduled based on the constructed intervals, finding
an optimal schedule is a typical NP-hard problem. Due to this, and the lack of
exact future information in a dynamic environment, we propose several methods
for fast camera scheduling that yield solutions within a small constant factor of
optimal. Experimental results illustrate system capabilities for both real and more
complicated simulated scenarios.
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/3042},
	author = {Lim,Ser-Nam and Mittal,Anuarg and Davis, Larry S.}
}
@article {16961,
	title = {An Augmented Visual Query Mechanism for Finding Patterns in Time Series Data (2002)},
	journal = {Institute for Systems Research Technical Reports},
	year = {2005},
	month = {2005///},
	abstract = {Relatively few query tools exist for data exploration and pattern identification in time series data sets. In previous work we introduced Timeboxes. Timeboxes are rectangular, direct-manipulation queries for studying time-series datasets. We demonstrated how Timeboxes can be used to support interactive exploration via dynamic queries, along with overviews of query results and drag-and-drop support for query-by-example. In this paper, we extend our work by introducing Variable Time Timeboxes (VTT). VTTs are a natural generalization of Timeboxes, which permit the specification of queries that allow a degree of uncertainty in the time axis. We carefully motivate the need for these more expressive queries, and demonstrate the utility of our approach on several data sets.},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/6495},
	author = {Keogh,Eamonn and Hochheiser,Harry and Shneiderman, Ben}
}
@article {16995,
	title = {Bridging the Digital Divide with Universal Usability (2001)},
	journal = {Institute for Systems Research Technical Reports},
	year = {2005},
	month = {2005///},
	abstract = {How do you explain a trashcan to a culture that doesn have one? How do you describe a top loss limit orderto retirees managing their funds? Can you design a text-only interface that conveys the contents and experience of an animated Flash presentation? <p>These puzzles emerged during the first ACM Conference on Universal Usability (http://www.acm.org/sigchi/cuu/), held on November 15-17, 2000 near Washington, DC. The international group of organizers, presenters, and attendees of this conference shared an unusual commitment and passion for making information and communications services accessible, usable, and useful. They want to see effective healthcare services and appealing distance education. They want to create successful e-commerce and accessible government services for all. Realizing these possibilities requires more than low-cost hardware or broadband networks. These mass- market services are often too complex, unusable, or irrelevant for too many users; usability and design become the keys to success. <p>The source of these problems was often attributed to designers who make incorrect assumptions about user knowledge. This leads to difficulties with technical terminology and advanced concepts that are not balanced by adequate online help or live assistance. Unfortunately, most designers never see the pain they inflict on novice and even expert users. These problems have contributed to the growing digital divide in internet technology adoption levels between lowincome poorly-educated and high-income well-educated users [2]. Even as the gap between men and women internet users has been eliminated and the gap between young and old is shrinking, the slow adoption rates by poor and poorly educated users remains a problem. Low-cost equipment is needed, but progress in design will help make internet services more accessible to more people.},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/6478},
	author = {Shneiderman, Ben}
}
@article {16100,
	title = {Broadening Access to Large Online Databases by Generalizing Query Previews (2000)},
	journal = {Institute for Systems Research Technical Reports},
	year = {2005},
	month = {2005///},
	abstract = {Companies, government agencies, and other types of organizations are making their large databases available to the world over the Internet. Current database front-ends do not give users information about the distribution of data. This leads many users to waste time and network resources posing queries that have either zero-hit or mega-hit result sets. Query previews form a novel visual approach for browsing large databases. Query previews supply data distribution information about the database that is being searched and give continuous feedback about the size of the result set for the query as it is being formed. On the other hand, query previews use only a few pre-selected attributes of the database. The distribution information is displayed only on these attributes. Unfortunately, many databases are formed of numerous relations and attributes. This paper introduces a generalization of query previews. We allow users to browse all of the relations and attributes of a database using a hierarchical browser. Any of the attributes can be used to display the distribution information, making query previews applicable to many public online databases.},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/6474},
	author = {Tanin,Egemen and Plaisant, Catherine and Shneiderman, Ben}
}
@article {16999,
	title = {Browsing Large Online Data Tables Using Generalized Query Previews (2001)},
	journal = {Institute for Systems Research Technical Reports},
	year = {2005},
	month = {2005///},
	abstract = {Companies, government agencies, and other organizations are making their data available to the world over the Internet. They often use large online relational tables for this purpose. Users query such tables with front-ends that typically use menus or form fillin interfaces, but these interfaces rarely give users information about the contents and distribution of the data. Such a situation leads users to waste time and network resources posing queries that have zero-hit or mega-hit results. Generalized query previews enable efficient browsing of large online databases by supplying data distribution information to the users. The data distribution information provides continuous feedback about the size of the result set as the query is being formed. Our paper presents a user interface architecture and discusses recent experimental findings. Our prototype system, ExpO, provides a flexible user interface for research and testing. The user study shows that for exploratory querying tasks, generalized query previews speed user performance and reduce network load.},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/6483},
	author = {Tanin,Egemen and Shneiderman, Ben}
}
@article {17002,
	title = {Building a Coherent Data Pipeline in Microarray Data Analyses: Optimization of Signal/Noise Ratios Using an Interactive Visualization Tool and a Novel Noise Filtering Method (2003)},
	journal = {Institute for Systems Research Technical Reports},
	year = {2005},
	month = {2005///},
	abstract = {Motivation: Sources of uncontrolled noise strongly influence data analysis in microarray studies, yet signal/noise ratios are rarely considered in microarray data analyses. We hypothesized that different research projects would have different sources and levels of confounding noise, and built an interactive visual analysis tool to test and define parameters in Affymetrix analyses that optimize the ratio of signal (desired biological variable) versus noise (confounding uncontrolled variables). Results: Five probe set algorithms were studied with and without statistical weighting of probe sets using Microarray Suite (MAS) 5.0 probe set detection p values. The signal/noise optimization method was tested in two large novel microarray datasets with different levels of confounding noise; a 105 sample U133A human muscle biopsy data set (11 groups) (extensive noise), and a 40 sample U74A inbred mouse lung data set (8 groups) (little noise). Success was measured using F-measure value of success of unsupervised clustering into appropriate biological groups (signal). We show that both probe set signal algorithm and probe set detection p-value weighting have a strong effect on signal/noise ratios, and that the different methods performed quite differently in the two data sets. Among the signal algorithms tested, dChip difference model with p-value weighting was the most consistent at maximizing the effect of the target biological variables on data interpretation of the two data sets. Availability: The Hierarchical Clustering Explorer 2.0 is [url=http://www.cs.umd.edu/hcil/hce/]available[/url] online and the improved version of the Hierarchical Clustering Explorer 2.0 with p-value weighting and Fmeasure is available upon request to the first author. Murine arrays (40 samples) are publicly available at the [url=http://microarray.cnmcresearch.org/pgadatatable.asp]PEPR resource.[/url] (Chen et al., 2004).},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/6511},
	author = {Seo,Jinwook and Bakay,Marina and Chen,Yi-Wen and Hilmer,Sara and Shneiderman, Ben and Hoffman,Eric P}
}
@article {16920,
	title = {A Comparison of Voice Controlled and Mouse Controlled Web Browsing (2000)},
	journal = {Institute for Systems Research Technical Reports},
	year = {2005},
	month = {2005///},
	abstract = {Voice controlled web browsers allow users to navigate by speaking the text of a link or an associated number instead of clicking with a mouse. One such browser is Conversa, by Conversational Computing. This within subjects study with 18 subjects compared voice browsing with traditional mouse-based browsing. It attempted to identify which of three common hypertext forms (linear slide show, grid/tiled map, and hierarchical menu) are well suited to voice navigation, and whether voice navigation is helped by numbering links. The study shows that voice control adds approximately 50 percent to the performance time for certain types of tasks. Subjective satisfaction measures indicate that for voice browsing, textual links are preferable to numbered links.},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/6475},
	author = {Christian,Kevin and Kules,Bill and Shneiderman, Ben and Youssef,Adel}
}
@article {17033,
	title = {Coordinating Overviews and Detail Views of WWW Log Data (2000)},
	journal = {Institute for Systems Research Technical Reports},
	year = {2005},
	month = {2005///},
	abstract = {Web server log analysis tools provide site operators with useful information regarding the visitors to their sites. Unfortunately, the utility of these tools is often limited by the use of aggregate summaries that hide the information associated with individual requests, and by the absence of contextual data that might help users interpret those summaries. Building upon earlier work in the use of starfield visualizations to display web site requests as individual data points [8], this paper describes the use of multiple-coordinated visualizations of web log data at varying granularities, and alongside additional related displays of appropriate contextual information.},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/6476},
	author = {Hochheiser,Harry and Shneiderman, Ben}
}
@article {17062,
	title = {Designing a Metadata-Driven Visual Information Browser for Federal Statistics (2003)},
	journal = {Institute for Systems Research Technical Reports},
	year = {2005},
	month = {2005///},
	abstract = {When looking for federal statistics, finding the right table, chart or report can be a daunting task for anyone not thoroughly familiar with the federal statistical system. Search tools help, but differing terminologies within the statistical agencies and a lack of familiarity of terms by information seekers limit their effectiveness. The FedStats Browser is a design for visually browsing federal agency statistical products and publications, using techniques that allow users to reformulate queries and iteratively refine results via simple, reversible actions with immediate feedback. This paper also discusses the characteristics of metadata needed for such a browser and the challenges inherent in acquiring that metadata.},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/6500},
	author = {Kules,Bill and Shneiderman, Ben}
}
@article {17065,
	title = {Designing for Fun: Can we design user interfaces to be more fun? (2004)},
	journal = {Institute for Systems Research Technical Reports},
	year = {2005},
	month = {2005///},
	abstract = {User interfaces are taking their place in the world of fashion and style, which is great news. Just as dining out is more than getting a balanced diet and wearing clothes is more than staying warm, using interfaces is becoming a personal statement. It great that designers are turning attention to fun, as a separate design space, distinct from functionality, usability, and reliability. Did anyone notice that fun is part of functionality?},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/6520},
	author = {Shneiderman, Ben}
}
@article {17079,
	title = {Determining Causes and Severity of End-User Frustration (2002)},
	year = {2005},
	month = {2005///},
	abstract = {While computers are beneficial to individuals and society, frequently, users encounter frustrating experiences when using computers. This study attempts to measure, through 111 participants, the frequency, cause, and the level of severity of frustrating experiences. The data showed that frustrating experiences happen on a frequent basis. The applications in which the frustrating experiences happened most frequently were web browsing, e-mail, and word processing. The most-cited causes of frustrating experiences were error messages, dropped network connections, long download times, and hard-to-find features. The time lost due to frustrating experiences ranged from 47-53\% of time spent on a computer depending on the location and study method. After discarding extreme cases the time lost was still above 38\%. These disturbing results should be a basis for future study.},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/6493},
	author = {Ceaparu,Irina and Lazar,Jonathan and Bessiere,Katie and Robinson,John and Shneiderman, Ben}
}
@article {17082,
	title = {Direct Annotation: A Drag-and-Drop Strategy for Labeling Photos (2000)},
	journal = {Institute for Systems Research Technical Reports},
	year = {2005},
	month = {2005///},
	abstract = {Annotating photos is such a time-consuming, tedious and error-prone data entry task that it discourages most owners of personal photo libraries. By allowing users to drag labels such as personal names from a scrolling list and drop them on a photo, we believe we can make the task faster, easier and more appealing. Since the names are entered in a database, searching for all photos of a friend or family member is dramatically simplified. We describe the user interface design and the database schema to support direct annotation, as implemented in our PhotoFinder prototype.},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/6471},
	author = {Shneiderman, Ben and Kang,Hyunmo}
}
@article {17097,
	title = {Dynamic Aggregation to Support Pattern Discovery: A Case Study with Web Logs (2001)},
	year = {2005},
	month = {2005///},
	abstract = {Rapid growth of digital data collections is overwhelming the capabilities of humans to comprehend them without aid. The extraction of useful data from large raw data sets is something that humans do poorly because of the overwhelming amount of information. Aggregation is a technique that extracts important aspect from groups of data thus reducing the amount that the user has to deal with at one time, thereby enabling them to discover patterns, outliers, gaps, and clusters. Previous mechanisms for interactive exploration with aggregated data was either too complex to use or too limited in scope. This paper proposes a new technique for dynamic aggregation that can combine with dynamic queries to support most of the tasks involved in data manipulation.},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/6487},
	author = {Tang,Lida and Shneiderman, Ben}
}
@article {17099,
	title = {Dynamic Layout Management in a Multimedia Bulletin Board (2002)},
	year = {2005},
	month = {2005///},
	abstract = {This paper proposes a novel user interface to manage the dynamic layout of multimedia objects in the Multimedia Bulletin Board (MBB) system. The MBB has been designed and implemented as a prototype of an asynchronous communication system that enables rich communication and collaboration among users of multimedia objects such as text, image, moving picture, sound, voice, web, office document, and other files. The layout properties of the multimedia objects on a board (e.g. x-y position, size, z-order, partial occlusion, explicit and implicit links, etc.) show important and useful information on the user dynamics occurring within a board. However, a fixed layout created and edited by multiple users may prevent users from recognizing and identifying useful information. This paper resolves this problem with a novel user-controlled layout strategy made visible with dynamic layout templates (DLT). Users can reorganize the objects to extract meaningful information related to time, source, geographic location, or topic.},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/6489},
	author = {Kang,Hyunmo and Shneiderman, Ben and Wolff,Gregory J}
}
@article {17102,
	title = {Dynamic Queries and Brushing on Choropleth Maps (2001)},
	year = {2005},
	month = {2005///},
	abstract = {Users who must combine demographic, economic or other data in a geographic context are often hampered by the integration of tabular and map representations. Static, paper-based solutions limit the amount of data that can be placed on a single map or table. By providing an effective user interface, we believe that researchers, journalists, teachers, and students can explore complex data sets more rapidly and effectively. This paper presents Dynamaps, a generalized map-based information-visualization tool for dynamic queries and brushing on choropleth maps. Users can use color coding to show a variable on each geographic region, and then filter out areas that do not meet the desired criteria. In addition, a scattergram view and a detailson- demand window support overviews and specific fact finding.},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/6481},
	author = {Dang,Gunjan and North,Chris and Shneiderman, Ben}
}
@article {17107,
	title = {Dynamic Query Chloropleth Maps for Information Seeking and Decision Making (2003)},
	year = {2005},
	month = {2005///},
	abstract = {Information retrieval and visualization can be combined in dynamic query systems that allow users unparalleled access to information for decision making. In this paper, we report on the development and evaluation of a dynamic query system (YMap) that displays information on a chloropleth map using double thumb sliders to select ranges of query variables. The YMap prototype is a Java-Applet that supports panning and zooming. Several usability studies were conducted on early prototypes that resulted in the current version. Applications of YMap for decision making tasks are discussed.},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/6505},
	author = {Norman,Kent L and Zhao,Haixia and Shneiderman, Ben and Golub,Evan}
}
@article {17110,
	title = {Dynamic query tools for time series data sets: Timebox widgets for interactive exploration (2004)},
	year = {2005},
	month = {2005///},
	abstract = {Timeboxes are rectangular widgets that can be used in direct-manipulation graphical user interfaces (GUIs) to specify query constraints on time series data sets. Timeboxes are used to specify simultaneously two sets of constraints: given a set of N time series profiles, a timebox covering time periods x1...x2 (x1rx2) and values y1...y2 (y1ry2) will retrieve only those nAN that have values y1ryry2 during all times x1rxrx2. TimeSearcher is an information visualization tool that combines timebox queries with overview displays, query-byexample facilities, and support for queries over multiple time-varying attributes. Query manipulation tools including pattern inversion and eaders \& laggards graphical bookmarks provide additional support for interactive exploration of data sets. Extensions to the basic timebox model that provide additional expressivity include variable time timeboxes, which can be used to express queries with variability in the time interval, and angular queries, which search for ranges of differentials, rather than absolute values. Analysis of the algorithmic requirements for providing dynamic query performance for timebox queries showed that a sequential search outperformed searches based on geometric indices. Design studies helped identify the strengths and weaknesses of the query tools. Extended case studies involving the analysis of two different types of data from molecular biology experiments provided valuable feedback and validated the utility of both the timebox model and the TimeSearcher tool. <p>Timesearcher is available [url=http://www.cs.umd.edu/hcil/ timesearcher]online.[/url]},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/6521},
	author = {Hochheiser,Harry and Shneiderman, Ben}
}
@article {17112,
	title = {Dynamic Query Visualizations on World Wide Web Clients: A DHTML Solution for Maps and Scattergrams (2002)},
	year = {2005},
	month = {2005///},
	abstract = {Dynamic queries are gaining popularity as a method for interactive information visualization. Many implementations have been made on personal computers, and there is increasing interest in web-based designs. While Java and Flash strategies have been developed, we believe that a Dynamic HTML implementation could help promote more widespread use. We implemented double-box range sliders with choropleth maps and scattergrams, which are two popular visualizations, using HTML layers and tables. This paper describes our methods for slider control, visual presentation, and displaying/updating results for these visualizations. Visual design issues innovations and performance enhancements were necessary to create viable designs.},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/6491},
	author = {Golub,Evan and Shneiderman, Ben}
}
@article {17114,
	title = {Dynamic Querying for Pattern Identification in Microarray and Genomic Data (2003)},
	year = {2005},
	month = {2005///},
	abstract = {Data sets involving linear ordered sequences are a recurring theme in bioinformatics. Dynamic query tools that support exploration of these data sets can be useful for identifying patterns of interest. This paper describes the use of one such tool TimeSearcher - to interactively explore linear sequence data sets taken from two bioinformatics problems. Microarray time course data sets involve expression levels for large numbers of genes over multiple time points. TimeSearcher can be used to interactively search these data sets for genes with expression profiles of interest. The occurrence frequencies of short sequences of DNA in aligned exons can be used to identify sequences that play a role in the pre-mRNA splicing. TimeSearcher can be used to search these data sets for candidate splicing signals.},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/6503},
	author = {Hochheiser,Harry and Baehrecke,Eric H and Mount, Stephen M. and Shneiderman, Ben}
}
@article {17154,
	title = {Exploring Personal Media: A Spatial Interface Supporting User-Defined Semantic Regions (2004)},
	year = {2005},
	month = {2005///},
	abstract = {Graphical mechanisms for spatially organizing personal media data could enable users to fruitfully apply their mental models. This paper introduces Semantic Regions, an innovative way for users to construct mental models by drawing regions on 2D space and specifying the semantics for each region. Then users can apply personal ontologies to personal media data using the fling-and-flock metaphor. This allows photos (or other personal media) to be dragged to the display and automatically grouped according to time, geography, family trees, groups of friends, or other conceptual maps. The prototype implementation for Semantic Regions, MediaFinder, was validated with two usability tests for usage and construction of user-defined mental models. Applications and extensions are discussed.},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/6513},
	author = {Kang,Hyunmo and Shneiderman, Ben}
}
@article {16111,
	title = {Extending the Utility of Treemaps with Flexible Hierarchy (2004)},
	year = {2005},
	month = {2005///},
	abstract = {Treemaps is a visualization technique for presenting hierarchical information on two dimensional displays. Prior implementations limit the visualization to pre-defined static hierarchies. Flexible hierarchy, a new capability of Treemap 4.0, enables users to define various hierarchies through dynamically selecting a series of data attributes so that they can discover patterns, clusters and outliers. This paper describes the design and implementation issues of flexible hierarchy. It then reports on a usability study which led to enhancements to the interface.},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/6514},
	author = {Chintalapani,Gouthami and Plaisant, Catherine and Shneiderman, Ben}
}
@article {17157,
	title = {Extending User Understanding of Federal Statistics in Tables (2000)},
	journal = {Institute for Systems Research Technical Reports},
	year = {2005},
	month = {2005///},
	abstract = {This paper describes progress toward improving user interfaces for US Federal government statistics that are presented in tables. Based on studies of user behaviors and needs related to statistical tables, we describe interfaces to assist diverse users with a range of statistical literacy to explore, find, understand, and use US Federal government statistics.},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/6473},
	author = {Marchionini,Gary and Hert,Carol and Liddy,Liz and Shneiderman, Ben}
}
@article {14018,
	title = {Fast Computation of Sums of Gaussians in High Dimensions},
	journal = {Technical Reports from UMIACS UMIACS-TR-2005-69},
	year = {2005},
	month = {2005/11/15/T19:2},
	abstract = {Evaluating sums of multivariate Gaussian kernels is a key computational task in many problems in computational statistics andmachine learning. The computational cost of the direct evaluation of such sums scales as the product of the number of kernel
functions and the evaluation points. The fast Gauss transform proposed by Greengard and Strain (1991) is a $\epsilon$-exact
approximation algorithm that reduces the computational complexity of the evaluation of the sum of $N$ Gaussians at $M$ points
in $d$ dimensions from $\mathcal{O}(MN)$ to $\mathcal{O}(M+N)$. However, the constant factor in $\mathcal{O}(M+N)$ grows
exponentially with increasing dimensionality $d$, which makes the algorithm impractical for dimensions greater than three. In
this paper we present a new algorithm where the constant factor is reduced to asymptotically polynomial order. The reduction
is based on a new multivariate Taylor{\textquoteright}s series expansion (which can act both as a local as well as a far field expansion)
scheme combined with the efficient space subdivision using the $k$-center algorithm. The proposed method differs from the
original fast Gauss transform in terms of a different factorization, efficient space subdivision, and the use of point-wise
error bounds. Algorithm details, error bounds, procedure to choose the parameters and numerical experiments  are presented.
As an example we shows how the proposed method can be used for very fast $\epsilon$-exact multivariate kernel density
estimation.
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/3020},
	author = {Raykar,Vikas Chandrakant and Yang,Changjaing and Duraiswami, Ramani and Gumerov, Nail A.}
}
@article {14540,
	title = {Fast Multipole Method for the Biharmonic Equation},
	volume = {UMIACS-TR-2005-29},
	year = {2005},
	month = {2005/09/29/},
	institution = {Instititue for Advanced Computer Studies, Univ of Maryland, College Park},
	abstract = {The evaluation of sums (matrix-vector products) of the solutions ofthe
three-dimensional biharmonic equation can be accelerated using the
fast
multipole method, while memory requirements can also be significantly
reduced. We develop a complete translation theory for these equations.
It is shown that translations of elementary solutions of the
biharmonic
equation can be achieved by considering the translation of a pair of
elementary solutions of the Laplace equations. Compared to previous
methods that required the translation of five Laplace elementary
solutions for the biharmonic Green{\textquoteright}s function, and much larger numbers
for higher order multipoles, our method is significantly more
efficient.
The theory is implemented and numerical tests presented that
demonstrate
the performance of the method for varying problem sizes and accuracy
requirements. In our implementation the FMM\ is faster than direct
solution for a matrix size of $550$ for an accuracy of $10^{-3},$ 950
for an accuracy of $10^{-6} and $N=3550$ for an accuracy of
$10^{-9}$.
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu//handle/1903/2813},
	author = {Gumerov, Nail A. and Duraiswami, Ramani}
}
@article {17167,
	title = {Finding Governmental Statistical Data on the Web: Three Empirical Studies of the FedStats Topics Page (2003)},
	year = {2005},
	month = {2005///},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/6509},
	author = {Ceaparu,Irina and Shneiderman, Ben}
}
@article {17177,
	title = {Generating and Querying Semantic Web Environments for Photo Libraries (2005)},
	journal = {Institute for Systems Research Technical Reports},
	year = {2005},
	month = {2005///},
	abstract = {Online photo libraries require a method to efficiently search a collection of photographs, and retrieve photos with similar attributes. Our motivation was to incorporate an existing collection of over 250 photographs of over 200 faculty members and events spanning 7 decades into a library called CS PhotoHistory that is available in hypertext and on the Semantic Web. In this paper, we identify challenges related to making this repository available on the Semantic Web, including issues of automation, modeling, and expressivity. Using CS PhotoHistory as a case study, we describe the process of creating an ontology and a querying interface for interacting with a digital photo library on the Semantic Web.},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/6538},
	author = {Axelrod,Adam and Golbeck,Jennifer and Shneiderman, Ben}
}
@article {17187,
	title = {Help! I{\textquoteright}m Lost: User Frustration in Web Navigation (2003)},
	journal = {Institute for Systems Research Technical Reports},
	year = {2005},
	month = {2005///},
	abstract = {Computers can be valuable tools, and networked resources via the Internet can be beneficial to many different populations and communities. Unfortunately, when people are unable to reach their task goals due to frustrating experiences, this can hinder the effectiveness of technology. This research summary provides information about the user frustration research that has been performed at the University of Maryland and Towson University. Causes of user frustration are discussed in this research summary, along with the surprising finding that nearly one-third to one-half of the time spent in front of the computer is wasted due to frustrating experiences. Furthermore, when interfaces are planned to be deceptive and confusing, this},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/6508},
	author = {Lazar,Jonathan and Bessiere,Katie and Ceaparu,Irina and Robinson,John and Shneiderman, Ben}
}
@article {17221,
	title = {Image-Based Highly Interactive Web Mapping for Geo-Referenced Data Publishing (2002)},
	journal = {Institute for Systems Research Technical Reports},
	year = {2005},
	month = {2005///},
	abstract = {This paper describes an image-based technique that enables highly interactive Web choropleth maps for geo-referenced data publishing and visual exploration. Geographic knowledge is encoded into raster images and delivered to the client, instead of in vector formats. Differing from traditional raster-imagebased approaches that are static and allow very little user interaction, it allows varieties of sub-second fine-grained interface controls such as dynamic query, dynamic classification, geographic object data identification, user setting adjusting, as well as turning on/off layers, panning and zooming, with no or minimum server support. Compared to Web GIS approaches that are based on vector geographic data, this technique has the features of short initial download time, near-constant performance scalability for larger numbers of geographic objects, and download-map-segment-only-when-necessary which potentially reduces the overall data transfer over the network. As a result, it accommodates general public users with slow modem network connections and low-end machines, as well as users with fast T-1 connections and fast machines. The client-side (browser) is implemented as light-weight Java applets. YMap, an easy-to-use, user-task-oriented highly interactive mapping tool prototype for visual georeferenced data exploration is implemented using this technique.},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/6498},
	author = {Zhao,Haixia and Shneiderman, Ben}
}
@article {16107,
	title = {Immediate Usability: A Case Study of Public Access Design for a Community Photo Library (2003)},
	year = {2005},
	month = {2005///},
	abstract = {This paper describes a novel instantiation of a digital photo library in a public access system. It demonstrates how designers can utilize characteristics of a target user community (social constraints, trust, and a lack of anonymity) to provide capabilities that would be impractical in other types of public access systems. It also presents a compact set of design principles and guidelines for ensuring the immediate usability of public access information systems. These principles and guidelines were derived from our experience developing PhotoFinder Kiosk, a community photo library. Attendees of a major HCI conference (CHI 2001 Conference on Human Factors in Computing Systems) successfully used the tool to browse and annotate collections of photographs spanning 20 years of HCI-related conferences, producing a richly annotated photo history of the field of human-computer interaction. Observations and log data were used to evaluate the tool and develop the guidelines. They provide specific guidance for practitioners, as well as a useful framework for additional research in public access interfaces.},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/6504},
	author = {Kules,Bill and Kang,Hyunmo and Plaisant, Catherine and Rose,Anne and Shneiderman, Ben}
}
@article {16106,
	title = {Immediate Usability: Kiosk design principles from the CHI 2001 Photo Library (2001)},
	year = {2005},
	month = {2005///},
	abstract = {This paper describes a novel set of design principles and guidelines for ensuring the immediate usability of public access systems. These principles and guidelines were formulated while developing PhotoFinder Kiosk, a community photo library. Attendees of CHI 2001 successfully used the tool to browse and annotate collections of photographs spanning 20 years of CHI and related conferences, producing a richly annotated photo history of the field of human-computer interaction. We used observations and log data to evaluate the tool and refine the guidelines. They provide specific guidance for practitioners, as well as a useful framework for additional research in public access interfaces.},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/6488},
	author = {Kules,Bill and Kang,Hyunmo and Plaisant, Catherine and Rose,Anne and Shneiderman, Ben}
}
@article {17223,
	title = {Improving Accessibility and Usability of Geo-referenced Statistical Data (2003)},
	year = {2005},
	month = {2005///},
	abstract = {Several technology breakthroughs are needed to achieve the goals of universal accessibility and usability. These goals are especially challenging in the case of geo-referenced statistical data that many U.S. government agencies supply. We present technical and user-interface design challenges in accommodating users with low-end technology (slow network connection and low-end machine) and users who are blind or vision-impaired. Our solutions are presented and future work is discussed.},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/6502},
	author = {Zhao,Haixia and Plaisant, Catherine and Shneiderman, Ben}
}
@article {17228,
	title = {Improving Web-based Civic Information Access: A Case Study of the 50 US States (2002)},
	year = {2005},
	month = {2005///},
	abstract = {An analysis of the home pages of all fifty U. S. states reveals great variety in key design features that influence efficacy. Some states had excessively large byte counts that would slow users connected by commonly-used 56K modems. Many web sites had low numbers of or poorly organized links that would make it hard for citizens to find what they were interested in. Features such as search boxes, privacy policies, online help, or contact information need to be added by several states. Our analysis concludes with ten recommendations and finds many further opportunities for individual states to improve their websites. However still greater benefits will come through collaboration among the states that would lead to consistency, appropriate tagging, and common tools.},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/6494},
	author = {Ceaparu,Irina and Shneiderman, Ben}
}
@article {17247,
	title = {Interactive Color Mosaic and Dendogram Displays for Signal/Noise Optimization in Microarray Data Analysis (2003)},
	journal = {Institute for Systems Research Technical Reports},
	year = {2005},
	month = {2005///},
	abstract = {Data analysis and visualization is strongly influenced by noise and noise filters. There are multiple sources of oisein microarray data analysis, but signal/noise ratios are rarely optimized, or even considered. Here, we report a noise analysis of a novel 13 million oligonucleotide dataset - 25 human U133A (~500,000 features) profiles of patient muscle biposies. We use our recently described interactive visualization tool, the Hierarchical Clustering Explorer (HCE) to systemically address the effect of different noise filters on resolution of arrays into orrectbiological groups (unsupervised clustering into three patient groups of known diagnosis). We varied probe set interpretation methods (MAS 5.0, RMA), resent callfilters, and clustering linkage methods, and investigated the results in HCE. HCE interactive features enabled us to quickly see the impact of these three variables. Dendrogram displays showed the clustering results systematically, and color mosaic displays provided a visual support for the results. We show that each of these three variables has a strong effect on unsupervised clustering. For this dataset, the strength of the biological variable was maximized, and noise minimized, using MAS 5.0, 10\% present call filter, and Average Group Linkage. We propose a general method of using interactive tools to identify the optimal signal/noise balance or the optimal combination of these three variables to maximize the effect of the desired biological variable on data interpretation.},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/6506},
	author = {Seo,Jinwook and Bakay,Marina and Zhao,Po and Chen,Yi-Wen and Clarkson,Priscilla and Shneiderman, Ben and Hoffman,Eric P}
}
@article {17251,
	title = {Interactive Exploration of Multidimensional Microarray Data: Scatterplot Ordering, Gene Ontology Browser, and Profile Search (2003)},
	journal = {Institute for Systems Research Technical Reports},
	year = {2005},
	month = {2005///},
	abstract = {Multidimensional data sets are common in many research areas, including microarray experiment data sets. Genome researchers are using cluster analysis to find meaningful groups in microarray data. However, the high dimensionality of the data sets hinders users from finding interesting patterns, clusters, and outliers. Determining the biological significance of such features remains problematic due to the difficulties of integrating biological knowledge. In addition, it is not efficient to perform a cluster analysis over the whole data set in cases where researchers know the approximate temporal pattern of the gene expression that they are seeking. <p>To address these problems, we add three new features to the Hierarchical Clustering Explorer (HCE): (1) scatterplot ordering methods so that all 2D projections of a high dimensional data set can be ordered according to relevant criteria, (2) a gene ontology browser, coupled with clustering results so that known gene functions within a cluster can be easily studied, (3) a profile search so that genes with a certain temporal pattern can be easily identified.},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/6528},
	author = {Seo,Jinwook and Shneiderman, Ben}
}
@article {17256,
	title = {Interactive Pattern Search in Time Series (2004)},
	year = {2005},
	month = {2005///},
	abstract = {The need for pattern discovery in long time series data led researchers to develop algorithms for similarity search. Most of the literature about time series focuses on algorithms that index time series and bring the data into the main storage, thus providing fast information retrieval on large time series. This paper reviews the state of the art in visualizing time series, and focuses on techniques that enable users to interactively query time series. Then it presents TimeSearcher 2, a tool that enables users to explore multidimensional data using coordinated tables and graphs with overview+detail, filter the time series data to reduce the scope of the search, select an existing pattern to find similar occurrences, and interactively adjust similarity parameters to narrow the result set. This tool is an extension of previous work, TimeSearcher 1, which uses graphical timeboxes to interactively query time series data.},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/6519},
	author = {Buono,Paolo and Aris,Aleks and Plaisant, Catherine and Khella,Amir and Shneiderman, Ben}
}
@article {17266,
	title = {Inventing Discovery Tools: Combining Information Visualization with Data Mining (2001)},
	year = {2005},
	month = {2005///},
	abstract = {The growing use of information visualization tools and data mining algorithms stems from two separate lines of research. Information visualization researchers believe in the importance of giving users an overview and insight into the data distributions, while data mining researchers believe that statistical algorithms and machine learning can be relied on to find the interesting patterns. This paper discusses two issues that influence design of discovery tools: statistical algorithms vs. visual data presentation, and hypothesis testing vs. exploratory data analysis. I claim that a combined approach could lead to novel discovery tools that preserve user control, enable more effective exploration, and promote responsibility.},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/6484},
	author = {Shneiderman, Ben}
}
@article {16932,
	title = {A Knowledge Integration Framework for Information Visualization (2004)},
	journal = {Institute for Systems Research Technical Reports},
	year = {2005},
	month = {2005///},
	abstract = {Users can better understand complex data sets by combining insights from multiple coordinated visual displays that include relevant domain knowl-edge. When dealing with multidimensional data and clustering results, the most familiar displays and comprehensible are 1- and 2-dimensional projections (his-tograms, and scatterplots). Other easily understood displays of domain knowl-edge are tabular and hierarchical information for the same or related data sets. The novel parallel coordinates view [6] powered by a direct-manipulation search, offers strong advantages, but requires some training for most users. We provide a review of related work in the area of information visualization, and introduce new tools and interaction examples on how to incorporate usersdo-main knowledge for understanding clustering results. Our examples present hi-erarchical clustering of gene expression data, coordinated with a parallel coor-dinates view and with the gene annotation and gene ontology.},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/6525},
	author = {Seo,Jinwook and Shneiderman, Ben}
}
@article {17418,
	title = {The limits of speech recognition: Understanding acoustic memory and appreciating prosody (2000)},
	journal = {Institute for Systems Research Technical Reports},
	year = {2005},
	month = {2005///},
	abstract = {Human-human relationships are rarely a good model for the design of effective user interfaces. Spoken language is effective for human-human interaction (HHI), but it often has severe limitations when applied to human-computer interaction (HCI). Speech is slow for presenting information, it is difficult to review or edit, and it interferes with other cognitive tasks. However speech has proven to be useful for store-and-forward messages, alerts in busy environments, and input-output for blind or motor-impaired users. Speech recognition for control is helpful for hands-busy, eyes-busy, mobilityrequired, or hostile environments and it shows promise for use in telephone-based services. Dictation input is increasingly accurate, but adoption outside the disabled users community has been slow compared to visual interfaces. Obvious physical problems include fatigue from speaking continuously and the disruption in an office filled with people speaking. <p>By understanding the cognitive processes surrounding human acoustic memory and processing, interface designers may be able to integrate speech more effectively and guide users more successfully. Then by appreciating the differences between HHI and HCI designers may be able to choose appropriate applications for human use of speech with computers. The key distinction may be the rich emotional content conveyed by prosody -- the pacing, intonation, and amplitude in spoken language. Prosody is potent for HHI, but may be disruptive for HCI.},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/6532},
	author = {Shneiderman, Ben}
}
@article {17282,
	title = {Listening to Maps: User Evaluation of Interactive Sonifications of Geo-Referenced Data (2004)},
	journal = {Institute for Systems Research Technical Reports},
	year = {2005},
	month = {2005///},
	abstract = {In this paper, we summarize the Auditory Information Seeking Principle (AISP) (gist, navigate, filter, and details-ondemand). To improve blind access to geo-referenced statistical data, we developed several interactive sonifications, adhering to the above AISP. Two user studies are presented. In the first user study with nine sighted subjects, a preliminary map design is compared with an enhanced table design. The study shows subjects can recognize geographic data distribution patterns on a real map with 51 geographic regions, in both designs. The map-based design was strongly preferred. The study also shows evidence that AISP conforms to people information seeking strategies. Based on the observations from the first user study, a second user study was conducted with forty-eight sighted subjects comparing four map designs. The effects of using sound to encode vertical geographic positions and two map navigation methods were compared. The result is presented and future work is discussed.},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/6518},
	author = {Zhao,Haixia and Smith,Benjamin K and Norman,Kent L and Plaisant, Catherine and Shneiderman, Ben}
}
@article {16096,
	title = {Listening to Maps: User Evaluation of Interactive Sonifications of Geo-Referenced Data},
	journal = {Institute for Systems Research Technical Reports},
	year = {2005},
	month = {2005///},
	abstract = {In this paper, we summarize the Auditory Information Seeking Principle (AISP) (gist, navigate, filter, and details-ondemand). To improve blind access to geo-referenced statistical data, we developed several interactive sonifications, adhering to the above AISP. Two user studies are presented. In the first user study with nine sighted subjects, a preliminary map design is compared with an enhanced table design. The study shows subjects can recognize geographic data distribution patterns on a real map with 51 geographic regions, in both designs. The map-based design was strongly preferred. The study also shows evidence that AISP conforms to people information seeking strategies. Based on the observations from the first user study, a second user study was conducted with forty-eight sighted subjects comparing four map designs. The effects of using sound to encode vertical geographic positions and two map navigation methods were compared. The result is presented and future work is discussed.},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/6518},
	author = {Zhao,Haixia and Smith,Benjamin K and Norman,Kent L and Plaisant, Catherine and Shneiderman, Ben}
}
@article {17287,
	title = {Making Computer and Internet Usability a Priority (2000)},
	year = {2005},
	month = {2005///},
	abstract = {As usability professionals, we are all too aware of the productivity losses, frustration, and lost business that results from poorly designed user interfaces. And we are uncomfortable with the risks created by poorly designed computer systems in life-critical applications such as air travel, medical care, and military applications. Yet despite the common sense of our approach, we still find it difficult to convince the technical and managerial communities that usability is a critical business parameter. While senior managers may support the concept of usability, project mangers and developers, coping with too tight schedules, often see it as a nicety that can be eliminated.},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/6527},
	author = {Kreitzberg,Charles B and Shneiderman, Ben}
}
@article {17292,
	title = {MediaFinder: An Interface for Dynamic Personal Media Management with Semantic Regions (2003)},
	year = {2005},
	month = {2005///},
	abstract = {Computer users deal with large amounts of personal media often face problems in managing and exploring it. This paper presents Semantic Regions, rectangular regions that enable users to specify their semantics or mental models, and the MediaFinder application, which uses Semantic Regions as the basis of a personal media management tool.},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/6499},
	author = {Kang,Hyunmo and Shneiderman, Ben}
}
@article {17313,
	title = {Ordered and Quantum Treemaps: Making Effective Use of 2D Space to Display Hierarchies (2001)},
	year = {2005},
	month = {2005///},
	abstract = {Treemaps, a space- filling method of visualizing large hierarchical data sets, are receiving increasing attention. Several algorithms have been proposed to create more useful displays by controlling the aspect ratios of the rectangles that make up a treemap. While these algorithms do improve visibility of small items in a single layout, they introduce instability over time in the display of dynamically changing data, fail to preserve order of the underlying data, and create layouts that are difficult to visually search. In addition, continuous treemap algorithms are not suitable for displaying quantum-sized objects within them, such as images. This paper introduces several new treemap algorithms, which address these shortcomings. In addition, we show a new application of these treemaps, using them to present groups of images. The ordered treemap algorithms ensure that items near each other in the given order will be near each other in the treemap layout. Using experimental evidence from Monte Carlo trials, we show that compared to other layout algorithms ordered treemaps are more stable while maintaining relatively favorable aspect ratios of the constituent rectangles. A second test set uses stock market data. The quantum treemap algorithms modify the layout of the continuous treemap algorithms to generate rectangles that are integral multiples of an input object size. The quantum treemap algorithm has been applied to PhotoMesa, an application that supports browsing of large numbers of images.},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/6486},
	author = {Bederson, Benjamin B. and Shneiderman, Ben and Wattenberg,Martin}
}
@article {17315,
	title = {Ordered Treemap Layouts (2001)},
	journal = {Institute for Systems Research Technical Reports},
	year = {2005},
	month = {2005///},
	abstract = {Treemaps, a space-filling method of visualizing large hierarchical data sets, are receiving increasing attention. Several algorithms have been proposed to create more useful displays by controlling the aspect ratios of the rectangles that make up a treemap. While these algorithms do improve visibility of small items in a single layout, they introduce instability over time in the display of dynamically changing data, and fail to preserve an ordering of the underlying data. This paper introduces the ordered treemap, which addresses these two shortcomings. The ordered treemap algorithm ensures that items near each other in the given order will be near each other in the treemap layout. Using experimental evidence from Monte Carlo trials, we show that compared to other layout algorithms ordered treemaps are more stable while maintaining relatively low aspect ratios of the constituent rectangles. A second test set uses stock market data.},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/6480},
	author = {Shneiderman, Ben and Wattenberg,Martin}
}
@article {16941,
	title = {A Photo History of SIGCHI: Evolution of Design from Personal to Public (2002)},
	journal = {Institute for Systems Research Technical Reports},
	year = {2005},
	month = {2005///},
	abstract = {For 20 years I have been photographing personalities and events in the emerging discipline of humanomputer interaction. Until now, only a few of these photos were published in newsletters or were shown to visitors who sought them out. Now this photo history is going from a personal record to a public archive. This archive should be interesting for professional members of this community who want to reminisce, as well as for historians and journalists who want to understand what happened. Students and Web surfers may also want to look at the people who created better interfaces and more satisfying user experiences.},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/6529},
	author = {Shneiderman, Ben}
}
@article {17331,
	title = {Promoting Universal Usability with Multi-Layer Interface Design (2003)},
	year = {2005},
	month = {2005///},
	abstract = {Increased interest in universal usability is causing some researchers to study advanced strategies for satisfying first-time as well as intermittent and expert users. This paper promotes the idea of multi-layer interface designs that enable first-time and novice users to begin with a limited set of features at layer 1. They can remain at layer 1, then move up to higher layers when needed or when they have time to learn further features. The arguments for and against multi-layer interfaces are presented with two example systems: a word processor with 8 layers and an interactive map with 3 layers. New research methods and directions are proposed.},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/6510},
	author = {Shneiderman, Ben}
}
@article {16943,
	title = {A Rank-by-Feature Framework for Interactive Exploration of Multidimensional Data (2004)},
	journal = {Institute for Systems Research Technical Reports},
	year = {2005},
	month = {2005///},
	abstract = {Interactive exploration of multidimensional data sets is challenging because: (1) it is difficult to comprehend patterns in more than three dimensions, and (2) current systems often are a patchwork of graphical and statistical methods leaving many researchers uncertain about how to explore their data in an orderly manner. We offer a set of principles and a novel rank-by-feature framework that could enable users to better understand distributions in one (1D) or two dimensions (2D), and then discover relationships, clusters, gaps, outliers, and other features. Users of our framework can view graphical presentations (histograms, boxplots, and scatterplots), and then choose a feature detection criterion to rank 1D or 2D axis-parallel projections. By combining information visualization techniques (overview, coordination, and dynamic query) with summaries and statistical methods users can systematically examine the most important 1D and 2D axis-parallel projections. We summarize our Graphics, Ranking, and Interaction for Discovery (GRID) principles as: (1) 1D, 2D, then features (2) graphics, ranking, summaries, then statistics. We implemented the rank-by-feature framework in the Hierarchical Clustering Explorer, but the same data exploration principles could enable users to organize their discovery process so as to produce more thorough analyses and extract deeper insights in any multidimensional data application, such as spreadsheets, statistical packages, or information visualization tools.},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/6524},
	author = {Seo,Jinwook and Shneiderman, Ben}
}
@article {16113,
	title = {Representing Unevenly-Spaced Time Series Data for Visualization and Interactive Exploration (2005)},
	journal = {Institute for Systems Research Technical Reports},
	year = {2005},
	month = {2005///},
	abstract = {Visualizing time series data is useful to support discovery of relations and patterns in financial, genomic, medical and other applications. In most time series, measurements are equally spaced over time. This paper discusses the challenges for unevenly-spaced time series data and presents four methods to represent them: sampled events, aggregated sampled events, event index and interleaved event index. We developed these methods while studying eBay auction data with TimeSearcher. We describe the advantages, disadvantages, choices for algorithms and parameters, and compare the different methods. Since each method has its advantages, this paper provides guidance for choosing the right combination of methods, algorithms, and parameters to solve a given problem for unevenly-spaced time series. Interaction issues such as screen resolution, response time for dynamic queries, and meaning of the visual display are governed by these decisions.},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/6537},
	author = {Aris,Aleks and Shneiderman, Ben and Plaisant, Catherine and Shmueli,Galit and Jank,Wolfgang}
}
@article {17357,
	title = {Severity and Impact of Computer User Frustration: A Comparison of Student and Workplace Users (2002)},
	year = {2005},
	month = {2005///},
	abstract = {User frustration with information and computing technology is a pervasive and persistent problem. When computers crash, network congestion causes delays, and poor user interfaces trigger confusion there are dramatic consequences for individuals, organizations, and society. These frustrations not only cause personal dissatisfaction and loss of self-efficacy, but may disrupt workplaces, slow learning, and reduce participation in local and national communities. Our study of 107 student computer users and 50 workplace computer users shows high levels of frustration and loss of 1/3 to 1/2 of time spent. This paper reports on the incident-specific and user-specific causes of frustration, and they raise frustration severity. It examines the frustration impacts on the daily interactions of the users. The time lost and time to fix problem, and importance of task, strongly correlate with frustration levels for both student and workplace users. Differences between students and workplace users are discussed in the paper.},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/6496},
	author = {Lazar,Jonathan and Jones,Adam and Hackley,Mary and Shneiderman, Ben}
}
@article {16102,
	title = {Show Me! Guidelines for Producing Recorded Demonstrations (2005)},
	year = {2005},
	month = {2005///},
	abstract = {Although recorded demonstrations (screen capture animations with narration) have become a popular form of instruction for user interfaces, little work has been done to describe guidelines for their design. Based on our experience in several projects, we offer a starting set of guidelines for the design of recorded demonstrations. Technical guidelines encourage users to keep file sizes small, strive for universal usability, and ensure user control etc. and provide tips to achieve those goals. Content guidelines include: create short demonstrations that focus on tasks, highlight each step with auditory and visual cues, synchronize narration and animation carefully, and create demonstrations with a clear beginning, middle, and end.},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/6533},
	author = {Plaisant, Catherine and Shneiderman, Ben}
}
@article {17362,
	title = {Snap-Together Visualization: A User Interface for Coordinating Visualizations via Relational Schemata (2000)},
	year = {2005},
	month = {2005///},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/6470},
	author = {North,Chris and Shneiderman, Ben}
}
@article {17368,
	title = {Social and Psychological Influences on Computer User Frustration (Newhagen book chapter, 2002)},
	journal = {Institute for Systems Research Technical Reports},
	year = {2005},
	month = {2005///},
	abstract = {As computer usage has proliferated, so has user frustration. Even devoted and knowledgeable users encounter annoying delays, incomprehensible messages, incompatible files, and indecipherable menus. The frustration generated by these problems can be personally disturbing and socially disruptive. Psychological and social perspectives on frustration may clarify the relationships among variables such as personality types, cultural factors, goal attainment, workplace anger, and computer anxiety. These perspectives may also help designers, managers, and users understand the range of responses to frustration, which could lead to effective interventions such as redesign of software, improved training, better online help, user discipline, and even resetting of national research priorities.},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/6497},
	author = {Bessiere,Katie and Ceaparu,Irina and Lazar,Jonathan and Robinson,John and Shneiderman, Ben}
}
@article {16104,
	title = {Toward a Statistical Knowledge Network (2004)},
	journal = {Institute for Systems Research Technical Reports},
	year = {2005},
	month = {2005///},
	abstract = {Statistics support planning and decision making and enormous efforts are made to collect data and produce statistics at all levels of governance. An important principle of democratic societies is that government statistics should be accessible to the broadest possible constituencies to empower better plans and decisions in all aspects of life. Given the potential of near-ubiquitous Internet access in homes and workplaces and efforts by government agencies to mount websites, physical access to large volumes of government is close to a fait accompli. What remains a significant challenge is enabling access to the right statistical information at the right time and in the right form.},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/6522},
	author = {Marchionini,Gary and Haas,Stephanie and Plaisant, Catherine and Shneiderman, Ben and Hert,Carol}
}
@article {17448,
	title = {Understanding Clusters in Multidimensional Spaces: Making Meaning by Combining Insights from Coordinated Views of Domain Knowledge (2004)},
	journal = {Institute for Systems Research Technical Reports},
	year = {2005},
	month = {2005///},
	abstract = {Cluster analysis of multidimensional data is widely used in many research areas including financial, economical, sociological, and biological analyses. Finding natural subclasses in a data set not only reveals interesting patterns but also serves as a basis for further analyses. One of the troubles with cluster analysis is that evaluating how interesting a clustering result is to researchers is subjective, application-dependent, and even difficult to measure. This problem generally gets worse as dimensionality and the number of items grows. The remedy is to enable researchers to apply domain knowledge to facilitate insight about the significance of the clustering result. This article presents a way to better understand a clustering result by combining insights from two interactively coordinated visual displays of domain knowledge. The first is a parallel coordinates view powered by a direct-manipulation search. The second is a domain knowledge view containing a well-understood and meaningful tabular or hierarchical information for the same data set. Our examples depend on hierarchical clustering of gene expression data, coordinated with a parallel coordinates view and with the gene annotation and gene ontology.},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/6512},
	author = {Seo,Jinwook and Shneiderman, Ben}
}
@article {17456,
	title = {Universal Usability as a Stimulus to Advanced Interface Design (2001)},
	year = {2005},
	month = {2005///},
	abstract = {The desire to make computing available to broader populations has historically been a motivation for research and innovation that led to new breakthroughs in usability. Menus, graphical user interfaces, and the World-Wide Web, are examples of innovative technological solutions that have arisen out of the challenge of bringing larger and more diverse groups of users into the world of computing. Universal usability is the latest such challenge: In order to build systems that are universally usable, designers must account for technology variety, user diversity, and gaps in user knowledge. These issues are particularly challenging and important in the context of increasing the usability of the World-Wide-Web. To raise awareness, we urge web designers to provide universal usability statements, to provide users with useful information about the usability of their sites. These statements can inform users and thereby reduce frustration and confusion. Further steps toward universal usability might be achieved through research aimed at developing tools that would encourage or promote usability. We close with five proposals for future research.},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/6485},
	author = {Shneiderman, Ben and Hochheiser,Harry}
}
@article {17465,
	title = {User Frustration with Technology in the Workplace (2004)},
	journal = {Institute for Systems Research Technical Reports},
	year = {2005},
	month = {2005///},
	abstract = {When hard to use computers cause users to become frustrated, it can affect workplace productivity, user mood, and interactions with other co-workers. Previous research has examined the frustration that graduate students and their families face in using computers. To learn more about the causes and effects of user frustration with computers in the workplace, we collected modified time diaries from 50 workplace users, who spent an average of 5.1 hours on the computer. In this experiment, users reported wasting on average, 42-43\% of their time on the computer due to frustrating experiences. The causes of the frustrating experiences, the time lost due to the frustrating experiences, and the effects of the frustrating experiences on the mood of the users are discussed in this paper. Implications for designers, managers, users, information technology staff, and policymakers are discussed.},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/6515},
	author = {Lazar,Jonathan and Jones,Adam and Bessiere,Katie and Ceaparu,Irina and Shneiderman, Ben}
}
@article {12431,
	title = {Using Iterative Strategies for Aligning Attributed Points in Space},
	volume = {ISR-TR-2005-2},
	year = {2005},
	month = {2005///},
	institution = {Institute for Systems Research, University of Maryland, College Park},
	abstract = {Signatures based on shape features are expected to be useful for several similarity assessment applications. Such signatures can extract the relevant shape information needed for similarity assessment and ignore the shape information not needed for a particular application. <p> Since different feature-based models are created in different coordinate systems, in order to compute distance between two sets of features, one needs to include geometric transformations for aligning features. Optimal alignment is the alignment that results in the minimum distance between two sets of features. In general, features can be viewed as attributed points in space. Hence, we need to develop techniques for aligning attributed points in space. <p> This report introduces iterative strategies for optimally aligning attributed points in space. Iterative strategies presented in this report involve successively applying algorithms that perform alignment under restricted rigid body transformations (e.g., rotations only or translations only) to solve point alignment problems that require higher dimension transformations (e.g., combinations rotations and translations). Our preliminary experimental results show that the idea of using of iterative strategies to solve higher dimension attributed point alignment problems is promising and can be used to perform feature-based shape similarity assessment.},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu//handle/1903/6467},
	author = {Cardone, Antonio and Gupta, Satyandra K. and Mount, Dave}
}
@article {17494,
	title = {Visual Specification of Queries for Finding Patterns in Time-Series Data (2001)},
	year = {2005},
	month = {2005///},
	abstract = {Widespread interest in discovering features and trends in time- series has generated a need for tools that support interactive exploration.This paper introduces timeboxes: a powerful graphical, directmanipulation metaphor for the specification of queries over time-series datasets. Our TimeFinder implementation of timeboxes supports interactive formulation and modification of queries, thus speeding the process of exploring time-series data sets and guiding data mining. TimeFinder includes windows for timebox queries, individual time-series, and details-on-demand. Other features include drag-and-drop support for query-by-example and graphical envelopes for displaying the extent of the entire data set and result set from a given query. Extensions involving increased expressive power and general temporal data sets are discussed.},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/6479},
	author = {Hochheiser,Harry and Shneiderman, Ben}
}
@article {17499,
	title = {Visualization Methods for Personal Photo Collections: Browsing and Searching in the PhotoFinder (2000)},
	year = {2005},
	month = {2005///},
	abstract = {Software tools for personal photo collection management are proliferating, but they usually have limited searching and browsing functions. We implemented the PhotoFinder prototype to enable non-technical users of personal photo collections to search and browse easily. PhotoFinder provides a set of visual Boolean query interfaces, coupled with dynamic query and query preview features. It gives users powerful search capabilities. Using a scatter plot thumbnail display and drag-and-drop interface, PhotoFinder is designed to be easy to use for searching and browsing photos.},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/6472},
	author = {Kang,Hyunmo and Shneiderman, Ben}
}
@article {17509,
	title = {Why Not Make Interfaces Better than 3D Reality? (2004)},
	year = {2005},
	month = {2005///},
	abstract = {Some designers dream about building interfaces that approach the richness of 3D reality. They believe that the closer an interface resembles the real world, the easier the usage. They strive for resolution that matches filmith rapid camera movement and lively animated objects. This is a dubious proposition since user studies show that disorienting navigation, complex user actions, and annoying occlusions can slow performance in the real world as well as 3D interfaces.},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/6523},
	author = {Shneiderman, Ben}
}
@article {17697,
	title = {Error Analysis of the Quasi-Gram--Schmidt Algorithm},
	volume = {UMIACS-TR-2004-17},
	year = {2004},
	month = {2004/04/19/},
	institution = {Instititue for Advanced Computer Studies, Univ of Maryland, College Park},
	abstract = {Let the $n{\times}p$ $(n\geq p)$ matrix $X$ have the QR~factorization$X = QR$, where $R$ is an upper triangular matrix of order $p$ and $Q$
is orthonormal.  This widely used decomposition has the drawback that
$Q$ is not generally sparse even when $X$ is.  One cure is to discard
$Q$ retaining only $X$ and $R$.  Products like $a = Q\trp y = R\itp
X\trp y$ can then be formed by computing $b = X\trp y$ and solving the
system $R\trp a = b$.  This approach can be used to modify the
Gram--Schmidt algorithm for computing $Q$ and $R$ to compute $R$
without forming $Q$ or altering $X$.  Unfortunately, this
quasi-Gram--Schmidt algorithm can produce inaccurate results.  In this
paper it is shown that with reorthogonalization the inaccuracies are 
bounded under certain natural conditions.
(UMIACS-TR-2004-17)
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/1346},
	author = {Stewart, G.W.}
}
@article {14037,
	title = {FAST ALGORITHMS TO COMPUTE MATRIX-VECTOR PRODUCTS FOR PASCAL MATRICES},
	journal = {Technical Reports from UMIACS UMIACS-TR-2004-08},
	year = {2004},
	month = {2004/03/25/},
	abstract = {The Pascal matrix arises in a number of applications. We present a few waysto decompose the Pascal matrices of size $n \times n$ into products of
matrices with structure. Based on these decompositions, we propose fast
algorithms to compute the product of a Pascal matrix and a vector with
omplexity $O(n\log n)$. We also present a strategy to stabilize the proposed
algorithms. Finally, we also present some interesting properties of the
Pascal matrices that help us to compute fast the product of the inverse of a
Pascal matrix and a vector, and fast algorithms for generalized Pascal
Matrices.
UMIACS-TR-2004-08
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/1338},
	author = {Tang,Zhihui and Duraiswami, Ramani and Gumerov, Nail A.}
}
@article {13221,
	title = {Real-Time Kernel-Based Tracking in Joint Feature-Spatial Spaces},
	year = {2004},
	month = {2004/04/19/},
	abstract = {An object tracking algorithm that uses a novel simple symmetric similarityfunction between spatially-smoothed kernel-density estimates of the model   
and target distributions is proposed and tested. The similarity measure is
based on the expectation of the density estimates over the model or target
images. The density is estimated using radial-basis kernel functions which
measure the affinity between points and provide a better outlier rejection
property. The mean-shift algorithm is used to track objects by iteratively
maximizing this similarity function. To alleviate the quadratic complexity
of the density estimation, we employ Gaussian kernels and the fast Gauss
transform to reduce the computations to linear order. This leads to a very
efficient and robust nonparametric tracking algorithm. The proposed
algorithm is tested with several image sequences and shown to achieve robust
and reliable real-time tracking.
(UMIACS-TR-2004-12)
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/1341},
	author = {Yang,Changjiang and Duraiswami, Ramani and Elgammal,Ahmed and Davis, Larry S.}
}
@article {13222,
	title = {Visibility Planning: Predicting Continuous Period of Unobstructed Views},
	journal = {Technical Reports from UMIACS},
	year = {2004},
	month = {2004/04/19/},
	abstract = {To perform surveillance tasks effectively, unobstructed views ofobjects are required e.g. unobstructed video of objects are often
needed for gait recognition. As a result, we need to determine 
intervals for video collection during which a desired object is
visible w.r.t. a given sensor. In addition, these intervals are in   
the future so that the system can effectively plan and schedule  
sensors for collecting these videos. We describe an approach to 
determine these visibility intervals. A Kalman filter is first
used to predict the trajectories of the objects. The trajectories 
are converted to polar coordinate representations w.r.t. a given
sensor. Trajectories with the same angular displacement w.r.t. the
sensor over time can be found by determining intersection points 
of functions representing these trajectories. Intervals between
these intersection points are suitable for video collection. We
also address the efficiency issue of finding these intersection      
points. An obvious brute force approach of $O(N^2)$ exists, where
$N$ is the number of objects. This approach suffices when $N$ is
small. When $N$ is large, we introduce an optimal segment
intersection algorithm of $O(N\log^2N+I)$, $I$ being the number of
intersection points. Finally, we model the prediction errors
associated with the Kalman filter using a circular object
representation. Experimental results that compare the performance
of the brute force and the optimal segment intersection algorithms
are shown.
(UMIACS-TR-2004-22)
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/1349},
	author = {Lim,Ser-Nam and Davis, Larry S. and Wan,Yung-Chun (Justin)}
}
@article {17694,
	title = {Building an Old-Fashioned Sparse Solver},
	volume = {UMIACS-TR-2003-95},
	year = {2003},
	month = {2003/09/25/},
	institution = {Instititue for Advanced Computer Studies, Univ of Maryland, College Park},
	abstract = {A sparse matrix is a matrix with very few nonzero elements.  Manyapplications in diverse fields give rise to linear systems of the form
$Ax = b$, where $A$ is sparse.  The problem in solving these systems
is to take advantage of the preponderance of zero elements to reduce
both memory use and comutation time.  The purpose of this paper is to
introduce students (and perhaps their teachers) to sparse matrix
technology.  It is impossible to treat all the techniques developed
since the subject started in the 1960{\textquoteright}s.  Instead, this paper
constructs a sparse solver for positive definite systems that would
have been state of the art around 1980, emphasizing equally theory and
computational practice.  It is hoped that a mastery of this material
will allow the reader to study the subject independently.
(UMIACS-TR-2003-95)
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/1312},
	author = {Stewart, G.W.}
}
@article {14056,
	title = {Data Structures, Optimal Choice of Parameters, and Complexity Results for Generalized Multilevel Fast Multipole Methods in $d$ Dimensions},
	journal = {Technical Reports from UMIACS UMIACS-TR-2003-28},
	year = {2003},
	month = {2003/04/04/},
	abstract = {We present an overview of the Fast Multipole Method, explain the use ofoptimal data structures and present complexity results for the algorithm.
We explain how octree structures and bit interleaving can be simply used
to create efficient versions of the multipole algorithm in $d$ dimensions.
We then present simulations that demonstrate various aspects of the
algorithm, including optimal selection of the clustering parameter, the
influence of the error bound on the complexity, and others. The use of
these optimal parameters results in a many-fold speed-up of the FMM, and
prove very useful in practice.
UMIACS-TR-2003-28
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/1270},
	author = {Gumerov, Nail A. and Duraiswami, Ramani and Borovikov,Eugene A.}
}
@article {16126,
	title = {Family Calendar Survey},
	journal = {Technical Reports from UMIACS},
	year = {2003},
	month = {2003/01/21/},
	abstract = {Beginning in late July 2002, we conducted a survey about people{\textquoteright}s personal andfamily calendaring habits. By the end of September, we had over 400 responses,
which are summarized below. The survey was conducted to help inform our work in
designing new technologies for families, motivated in part by our work on the
interLiving project. InterLiving is a 3 year, European Union-funded project
where we work with distributed, multi-generational families as design partners
to create new technologies (see http://www.cs.umd.edu/hcil/interliving for
details).
The survey was administered from a web page
(https://www.cs.umd.edu/users/hilary/survey/survey.htm), and participants were
solicited via a "chain-mail" email approach. We began by sending a request to 
fill out a survey to our friends, families, and colleagues. We asked that they
forward the request on to their friends, family and colleagues as well.
While we realize that this was an imperfect approach, we believed that the   
respondents would be representative of the users we are initially targeting in
our research on family calendaring and coordination - individuals who are
already making relatively heavy use of computers at home and/or work. The results seem to validate this assumption.
Many of our respondents likely come from the HCI community as the mailing went
to our large lab mailing list. We may have some pollution in the data as a
result of people in the same household (e.g. husband and wife) both filling out
the survey. Despite these issues, the results we got were helpful in eliciting a
number of important findings, namely that people rely on multiple calendars,
many of which are still paper.
(UMIACS-TR-2002-92)
(HCIL-TR-2002-21)
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/1236},
	author = {Hutchinson,Hilary and Bederson, Benjamin B. and Plaisant, Catherine and Druin, Allison}
}
@article {14964,
	title = {Fast Algorithms for 3-D Dominance Reporting and Counting},
	volume = {UMIACS-TR-2003-06},
	year = {2003},
	month = {2003/02/05/},
	institution = {Instititue for Advanced Computer Studies, Univ of Maryland, College Park},
	abstract = {We present in this paper fast algorithms for the 3-D dominance reportingand counting problems, and generalize the results to the d-dimensional
case. Our 3-D dominance reporting algorithm achieves $O(\log n/\log\log n
+f)$ query time using $O(n\log^{\epsilon}n)$ space, where $f$ is the
number of points satisfying the query and $\epsilon>0$ is an arbitrary
small constant. For the 3-D dominance counting problem (which is
equivalent to the 3-D range counting problem), our algorithm runs in
$O((\log n/\log\log n)^2)$ time using $O(nlog^{1+\epsilon}n/\log\log n)$
space. 
Also UMIACS-TR-2003-06
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/1253},
	author = {Shi,Qingmin and JaJa, Joseph F.}
}
@article {14969,
	title = {Fast Fractional Cascading and Its Applications},
	volume = {UMIACS-TR-2003-71},
	year = {2003},
	month = {2003/08/01/},
	institution = {Instititue for Advanced Computer Studies, Univ of Maryland, College Park},
	abstract = {Using the notions of Q-heaps and fusion trees developed by Fredman andWillard, we develop a faster version of the fractional cascading technique
while maintaining the linear space structure. The new version enables
sublogarithmic iterative search in the case when we have a search tree and
the degree of each node is bounded by $O(\log^{\epsilon}n)$, for some
constant $\epsilon >0$, where $n$ is the total size of all the lists
stored in the tree. The fast fractional cascading technique is used in
combination with other techniques to derive sublogarithmic time algorithms
for the geometric retrieval problems: orthogonal segment intersection and
rectangular point enclosure. The new algorithms use $O(n)$ space and
achieve a query time of $O(\log n/\log\log n + f)$, where $f$ is the number of objects satisfying the query. All our algorithms assume the
version of the RAM model used by Fredman and Willard.
(UMIACS-TR-2003-71)
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/1296},
	author = {Shi,Qingmin and JaJa, Joseph F.}
}
@article {17674,
	title = {A Fortran 95 Matrix Wrapper},
	volume = {UMIACS-TR-2003-89},
	year = {2003},
	month = {2003/09/02/},
	institution = {Instititue for Advanced Computer Studies, Univ of Maryland, College Park},
	abstract = {{\Matran} is an wrapper written in Fortran~95 that implements matrixoperations and computes matrix decompositions using {\lapack} and the
{\blas}.  This document describes a preliminary release of {\matran},
which treats only real matrices.  Its purpose is to get outside
comments and suggestions before the package jells.  Consequently, this
documentation is slanted toward the experienced programmer familiar
with both matrix computations and Fortran~90/95.  User oriented
documentation will accompany the final release.
(UMIACS-TR-2003-89)
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/1308},
	author = {Stewart, G.W.}
}
@article {17220,
	title = {Image-based highly interactive Web mapping for geo-referenced data publishing},
	journal = {Technical Reports from UMIACS},
	year = {2003},
	month = {2003/01/21/},
	abstract = {This paper describes an image-based technique that enables highly interactiveWeb choropleth maps for geo-referenced data publishing and visual exploration.
Geographic knowledge is encoded into raster images and delivered to the client,
instead of in vector formats. Differing from traditional raster-image-based
approaches that are static and allow very little user interaction, it allows
varieties of sub-second fine-grained interface controls such as dynamic query,
dynamic classification, geographic object data identification, user setting
adjusting, as well as turning on/off layers, panning and zooming, with no or
minimum server support. Compared to Web GIS approaches that are based on vector
geographic data, this technique has the features of short initial download time,
near-constant performance scalability for larger numbers of geographic objects,
and download-map-segment-only-when-necessary which potentially reduces the
overall data transfer over the network. As a result, it accommodates general   
public users with slow modem network connections and low-end machines, as well
as users with fast T-1 connections and fast machines. The client-side (browser)
is implemented as light-weight Java applets. YMap, an easy-to-use,
user-task-oriented highly interactive mapping tool prototype for visual
geo-referenced data exploration is implemented using this technique.
(UMIACS-TR-2003-02)
(HCIL-TR-2002-26)
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/1248},
	author = {Zhao,Haixia and Shneiderman, Ben}
}
@article {16125,
	title = {Immediate Usability: Kiosk design principles from the CHI 2001 Photo Library},
	journal = {Technical Reports from UMIACS},
	year = {2003},
	month = {2003/01/21/},
	abstract = {This paper describes a novel set of design principles and guidelines forensuring the immediate usability of public access systems. These principles and 
guidelines were formulated while developing PhotoFinder Kiosk, a community photo
library. Attendees of CHI 2001 successfully used the tool to browse and annotate
collections of photographs spanning 20 years of CHI and related conferences,
producing a richly annotated photo history of the field of human-computer
interaction. We used observations and log data to evaluate the tool and refine
the guidelines. They provide specific guidance for practitioners, as well as a
useful framework for additional research in public access interfaces.
Keywords
Photo collection, community photo library, group annotation, public access 
system, direct annotation, direct manipulation, drag-and-drop, immediate
usability, zero-trial learning, walk-up-and-use, casual use.
(UMIACS-TR-2001-71)
(HCIL-TR-2001-23)
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/1155},
	author = {Kules,Bill and Kang,Hyunmo and Plaisant, Catherine and Rose,Anne and Shneiderman, Ben}
}
@article {16124,
	title = {Improving Accessibility and Usability of Geo-referenced Statistical Data},
	year = {2003},
	month = {2003/06/04/},
	abstract = {Several technology breakthroughs are needed to achieve the goals ofuniversal accessibility and usability. These goals are especially
challenging in the case of geo-referenced statistical data that many U.S.
government agencies supply. We present technical and user-interface design
challenges in accommodating users with low-end technology (slow network
connection and low-end machine) and users who are blind or
vision-impaired. Our solutions are presented and future work is discussed.
(UMIACS-TR-2003-37)
(HCIL-2003-11)
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/1277},
	author = {Zhao,Haixia and Plaisant, Catherine and Shneiderman, Ben}
}
@article {12300,
	title = {Intradomain Overlays: Architecture and Applications},
	journal = {Technical Reports from UMIACS, UMIACS-TR-2003-70},
	year = {2003},
	month = {2003/08/01/},
	abstract = {We introduce an architecture for {\textquoteleft}{\textquoteleft}Intradomain Overlays{\textquoteright}{\textquoteright}, where a  subset of routers within a domain is augmented with a dedicated
  host.  These strategically placed hosts form an overlay network, and
  we describe a number of applications for such
  overlays.  These applications include efficient network  
  monitoring, policy- and load-based packet re-routing, and network
  resource accounting.
         
  In this paper, we elaborate on the network monitoring application
  and describe a distributed protocol for monitoring routers within an
  AS which has been augmented with a few overlay nodes.  The routers
  and other infrastructure are unaware of the overlay nodes, and the
monitoring of individual elements is conducted using plain SNMP.  We
  describe techniques for efficiently synthesizing and transporting
  the monitored SNMP data, and present results using trace data
  collected from an AS with 400+ routers.  Our results show that the
  overlay-based monitoring reduces overheads by 2--4 orders of
  magnitude, and thus enables much finer grained monitoring and
  traffic engineering than is otherwise possible.
(UMIACS-TR-2003-70)
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/1295},
	author = {Kommareddy,Christopher and Guven,Tuna and Bhattacharjee, Bobby and La,Richard and Shayman,Mark}
}
@article {14943,
	title = {An O(n)-Space O(log n/log log n + f)-Query Time Algorithm for 3-D Dominance Reporting},
	volume = {UMIACS-TR-2003-77},
	year = {2003},
	month = {2003/08/01/},
	institution = {Instititue for Advanced Computer Studies, Univ of Maryland, College Park},
	abstract = {We present a linear-space algorithm for handling the {\emthree-dimensional dominance reporting problem}: given a set $S$ of $n$
three-dimensional points, design a data structure for $S$ so that the
points in $S$ which dominate a given query point can be reported quickly.
Under the variation of the RAM model introduced by Fredman and
Willard~\cite{Fredman94}, our algorithm achieves $O(\log n/\log\log n+f)$
query time, where $f$ is the number of points reported. Extensions to
higher dimensions are also reported.
(UMIACS-TR-2003-77)
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/1301},
	author = {Shi,Qingmin and JaJa, Joseph F.}
}
@article {15019,
	title = {Recovery of a Digital Image Collection Through the SDSC/UMD/NARA Prototype Persistent Archive},
	volume = {UMIACS-TR-2003-105},
	year = {2003},
	month = {2003/11/25/},
	institution = {Instititue for Advanced Computer Studies, Univ of Maryland, College Park},
	abstract = {The San Diego Supercomputer Center (SDSC), the University of Maryland, and theNational Archives and Records Administration (NARA) are collaborating on
building a pilot persistent archive using and extending data grid and digital
library technologies. The current prototype consists of node servers at SDSC,
University of Maryland, and NARA, connected through the Storage Request Broker
(SRB) data grid middleware, and currently holds several terabytes of NARA
selected collections. In particular, a historically important image collection
that was on the verge of becoming inaccessible was fully restored and ingested
into our pilot system. In this report, we describe the methodology behind our
approach to fully restore this image collection and the process used to ingest
it into the prototype persistent archive.
(UMIACS-TR-2003-105)
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/1321},
	author = {Smorul,Mike and JaJa, Joseph F. and McCall,Fritz and Brown,Susan Fitch and Moore,Reagan and Marciano,Richard and Chen,Sheau-Yen and Lopez,Rick and Chadduck,Robert}
}
@article {13249,
	title = {A Simple and Optimal Energy Surface Reconstruction Algorithm from Volumetric Data},
	journal = {Technical Reports from UMIACS},
	year = {2003},
	month = {2003/02/05/},
	abstract = {We describe a new method for building 3D surface meshes from volumetricimages, as are created in Magnetic Resonance Imaging (MRI). The method works
by first extracting the contours from the MRI data, and then using modified
polygon boolean operations to find difference polygons. The last step is
performed by applying a Constrained Delauny Triangulation (CDT) algorithm to
build a surface mesh. Since it is based on CDT, the mesh quality is usually
 very good. Moreover, the resulting triangular surface mesh is the optimal
one for surface interpolation. In case of undersampled images, the mesh
quality can be improved dramatically by inserting new Steiner points in to
the mesh. Thus the mesh can be made suitable for use in scientific
computation. Our method has the advantages of combining the generation and
optimization of the mesh in one step compared with other methods. These advantages are illustrated.
Also UMIACS-TR-2003-11
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/1256},
	author = {Liu,Kexue and Duraiswami, Ramani and Davis, Larry S.}
}
@article {15027,
	title = {Space-Efficient and Fast Algorithms for Multidimensional Dominance Reporting and Range Counting},
	volume = {UMIACS-TR-2003-101},
	year = {2003},
	month = {2003/11/25/},
	institution = {Instititue for Advanced Computer Studies, Univ of Maryland, College Park},
	abstract = {We present linear-space sublogarithmic algorithms for handling the {\emthree-dimensional dominance reporting problem} and the {\em
two-dimensional range counting problem}. Under the RAM model as described
in~[M.~L. Fredman and D.~E. Willard. {\textquoteleft}{\textquoteleft}Surpassing the information
theoretic bound with fusion trees{\textquoteright}{\textquoteright}, {\em Journal of Computer and System
Sciences}, 47:424--436, 1993], our algorithms achieve $O(\log n/\log\log
n+f)$ query time for 3-D dominance reporting, where $f$ is the number of
points reported, and $O(\log n/\log\log n)$ query time for 2-D range
counting case. We extend these results to any constant dimension $d$
achieving $O(n(\log n/\log\log n)^{d-3})$-space and $O((\log n/\log\log
)^{d-2}+f)$-query time for the reporting case and $O(n(\log n/\log\log 
n)^{d-2})$-space and $O((\log n/\log\log n)^{d-1})$ query time for the
counting case.
(UMIACS-TR-2003-101)
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/1318},
	author = {Shi,Qingmin and JaJa, Joseph F. and Mortensen,Christian}
}
@article {17449,
	title = {Understanding Computer User Frustration: Measuring and Modeling the Disruption from Poor Designs},
	journal = {Technical Reports from UMIACS},
	year = {2003},
	month = {2003/01/21/},
	abstract = {User frustration in the use of information and computing technology is apervasive and persistent problem.  When computers crash, network congestion
causes delays, and poor user interfaces trigger confusion there are dramatic
consequences for individuals, organizations, and society. These frustrations not
only cause personal dissatisfaction and loss of self-efficacy, but may disrupt
workplaces, slow learning, and reduce participation in local and national
communities. We propose a Computing Frustration Model with incident specific and
individual variables to guide research. Our study of 108 computer users shows
high levels of frustration and loss of 1/3 to 1/2 of time spent.   The
importance of the users{\textquoteright} goals and the severity of the disruption were
correlated with frustration. Those who had strong self-efficacy, indicated by a
willingness to stick to solving the problem, reported lower levels of
frustration.  Implications for users, software developers, managers, and
policymakers are discussed.
Keywords: user frustration, user interface design, training, helpdesk, computer
experience, computer anxiety
(UMIACS-TR-2002-89)
(HCIL-TR-2002-18)
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/1233},
	author = {Bessiere,Katie and Ceaparu,Irina and Lazar,Jonathan and Robinson,John and Shneiderman, Ben}
}
@article {17450,
	title = {Understanding Hierarchical Clustering Results by Interactive Exploration of Dendrograms: A Case Study with Genomic Microarray Data},
	journal = {Technical Reports from UMIACS},
	year = {2003},
	month = {2003/01/21/},
	abstract = {Abstract: Hierarchical clustering is widely used to find patterns inmulti-dimensional datasets, especially for genomic microarray data.  Finding
groups of genes with similar expression patterns can lead to better
understanding of the functions of genes.  Early software tools produced only
printed results, while newer ones enabled some online exploration.  We describe
four general techniques that could be used in interactive explorations of
clustering algorithms: (1) overview of the entire dataset, coupled with a detail
view so that high-level patterns and hot spots can be easily found and examined,
(2) dynamic query controls so that users can restrict the number of clusters
they view at a time and show those clusters more clearly, (3) coordinated
displays: the overview mosaic has a bi-directional link to 2-dimensional
scattergrams, (4) cluster comparisons to allow researchers to see how different
clustering algorithms group the genes.
(UMIACS-TR-2002-50)
(HCIL-TR-2002-10)
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/1203},
	author = {Seo,Jinwook and Shneiderman, Ben}
}
@article {11915,
	title = {AD (Attacker Defender) Game},
	journal = {Technical Reports from UMIACS, UMIACS-TR-2001-45},
	year = {2002},
	month = {2002/01/31/},
	abstract = {Information Dynamics is a framework for agent-based systems that givesa 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{\textquoteright}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)
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/1142},
	author = {Kochut,Andrzej and Agrawala, Ashok K. and Larsen,Ronald L and A. Udaya Shankar}
}
@article {17680,
	title = {Addendum to "A Krylov--Schur Algorithm for Large Eigenproblems"},
	volume = {UMIACS-TR-2001-90},
	year = {2002},
	month = {2002/01/31/},
	institution = {Instititue for Advanced Computer Studies, Univ of Maryland, College Park},
	abstract = {In this addendum to an earlier paper by the author, it is shown how tocompute a Krylov decomposition corresponding to an arbitrary
Rayleigh-Quotient.  This decomposition can be used to restart an
Arnoldi process, with a selection of the Ritz vectors corresponding to
the Rayleigh quotient.
(Also UMIACS-TR-2001-90)
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/1171},
	author = {Stewart, G.W.}
}
@article {12308,
	title = {Analysis of the NICE Application Layer Multicast Protocol},
	journal = {Technical Reports from UMIACS, UMIACS-TR-2002-60},
	year = {2002},
	month = {2002/08/01/},
	abstract = {Application layer multicast protocols organize a set of hosts intoan overlay tree for data delivery.  Each host
on the overlay peers with a subset of other hosts. Since
application layer multicast relies only on an underlying
unicast architecture, multiple copies of the same packet 
can be carried by a single physical link or node on the
overlay. The stress at a link or node is defined as the
number of identical copies of a packet carried by that
link or node. Stretch is another important metric in
application layer multicast, which measures the relative
increase in delay incurred by the overlay path between
pairs of members with respect to the direct unicast path.
In this paper we study the NICE application layer multicast
protocol to quantify and study the tradeoff between these
two important metrics --- stress and stretch in scalably building application layer multicast paths.
Also UMIACS-TR-2002-60
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/1212},
	author = {Banerjee,Suman and Bhattacharjee, Bobby}
}
@article {11912,
	title = {Efficient Data Processing using Cross Layer Hints},
	journal = {Technical Reports from UMIACS, UMIACS-TR-2002-59},
	year = {2002},
	month = {2002/12/19/},
	abstract = {Conventional network stacks define a layered architecture, whereeach layer implements a set of services and exports a well-defined
interface to be used by its immediate upper layer.
A key design choice of the layered architecture has been to
provide isolation between the functional modules of distinct layers.
While such an architecture provides an useful abstraction for
system development, the strict isolation
of this layered architecture limits the flexibility of tailoring
the behavior of the lower layers of the stack to the needs of the
application.
In this paper we define a new architecture, called X-Tags,
which allows flexible interaction between layers for cooperative  
data processing without impacting the isolation property.
In this architecture, applications use special tags to provide
semantic hints for data processing to lower layers.
We motivate the usefulness of this architecture by describing
ts applicability to some emerging applications.
UMIACS-TR-2002-59
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/1211},
	author = {Banerjee,Suman and Agrawala, Ashok K. and Kramer,Michael J}
}
@article {18906,
	title = {HTN Planning in Answer Set Programming},
	volume = {UMIACS-TR-2002-18},
	year = {2002},
	month = {2002/05/22/},
	institution = {Instititue for Advanced Computer Studies, Univ of Maryland, College Park},
	abstract = {In this paper we introduce a formalism for solving Hierarchical Task NEtwork(HTN)
Planning using Answer Set Programming (ASP). The ASP paradigm evolved out of
the
stable semantics for logic programs in recent years and is strongly related
to nonmonotonic
logics. We consider the formulation of HTM planning as described in the SHOP
planning
system and define a systematic translation method from SHOP{\textquoteright}s representation
of the planning
problems into logic programs with negation. We show that our translation is
sound and complete:
answer sets of the logic programs obtained by our translation correspond exactly to the solutions
of the planning problems.
Our approach does not rly on a particular system for computing answer sets. 
It can therefore
serve as a means to evaluate ASP systems by using well-established
benchmarks from the planning community. We tested our method on various such
benchmarks and used smodels and DLV for computing answer sets.
We compared our method to (1) similar approaches based on non-HTN planning
and (2) SHOP, a dedicated planning system. We show that our approach
outperforms non-HTN methods and
that its performance is closer to that of SHOP, when we are using ASP
systems which allow
for nonground programs.
(Also UMIACS-TR-2002-18)
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu//handle/1903/1182},
	author = {Dix,Jurgen and Kuter,Ugur and Nau, Dana S.}
}
@article {17290,
	title = {Media Conversion from Visual to Audio: Voice Browsers},
	journal = {Technical Reports of the Computer Science Department},
	year = {2002},
	month = {2002/12/19/},
	abstract = {There is a large amount of information on the World Wide Web that is atthe fingertips of anyone with access to the internet. However, so far
this information has primarily been used by people who connect to the
web via traditional computer. This is about to change. Recent advances
in wireless communication, speech recognition, and speech synthesis
technologies have made it possible to access this information from any
place, and at any time. In this paper, we discuss voice browsers as
compared to current web browsers. Some of the primary techniques of
universal accessible design are listed with their relation to voice
browsers and some ideas are offered to help authors implementing these
considerations when designing web pages. The new voice markup language 
is briefly discussed.
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/534},
	author = {Youssef,Adel and Shneiderman, Ben}
}
@article {18913,
	title = {M-Translog-2: A Planning Domain Designed for AIPS-2002},
	volume = {UMIACS-TR-2002-82},
	year = {2002},
	month = {2002/10/03/},
	institution = {Instititue for Advanced Computer Studies, Univ of Maryland, College Park},
	abstract = {This document describes UM-Translog-2, which is an extended version of theUM Translog planning domain.  The extensions include some
numerical-computation features to make the domain a more realistic model of
transportation-logistics problems. We are proposing UM- Translog-2 as a
candidate domain for AIPS-2002 planning competition.
(Also UMIACS-TR-2002-82)
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu//handle/1903/1228},
	author = {Wu,Dan and Nau, Dana S.}
}
@article {14163,
	title = {A Parallel Block Multi-level Preconditioner for the 3D Incompressible Navier--Stokes Equations},
	volume = {UMIACS-TR-2002-95},
	year = {2002},
	month = {2002/10/25/},
	institution = {Instititue for Advanced Computer Studies, Univ of Maryland, College Park},
	abstract = {The development of robust and efficient algorithms for both steady-statesimulations and fully-implicit time integration of the Navier--Stokes
equations is an active research topic. To be effective, the linear
subproblems generated by these methods require solution techniques that
exhibit robust and rapid convergence. In particular, they should be
insensitive to parameters in the problem such as mesh size, time step, and
Reynolds number. In this context, we explore a parallel preconditioner
based on a block factorization of the coefficient matrix generated in an
Oseen nonlinear iteration for the primitive variable formulation of the
system. The key to this preconditioner is the approximation of a certain Schur complement operator by a technique first proposed by Kay, Loghin, 
and Wathen [25] and Silvester, Elman, Kay, and Wathen [45]. The resulting
operator entails subsidiary computations (solutions of pressure Poisson
and convection--diffusion subproblems) that are similar to those required
for decoupled solution methods; however, in this case these solutions are
applied as preconditioners to the coupled Oseen system. One important
aspect of this approach is that the convection--diffusion and Poisson 
subproblems are significantly easier to solve than the entire coupled   
system, and a solver can be built using tools developed for the
subproblems. In this paper, we apply smoothed aggregation algebraic
multigrid to both subproblems. Previous work has focused on demonstrating
the optimality of these preconditioners with respect to mesh size on
serial, two-dimensional, steady-state computations employing geometric 
multi-grid methods; we focus on extending these methods to large-scale,  
parallel, three-dimensional, transient and steady-state simulations
employing algebraic multigrid (AMG) methods. Our results display nearly
optimal convergence rates for steady-state solutions as well as for   
transient solutions over a wide range of CFL numbers on the
two-dimensional and three-dimensional lid-driven cavity problem.
Also UMIACS-TR-2002-95
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu//handle/1903/1239},
	author = {Elman, Howard and Howle, V. E and Shadid,John and Tuminaro,Ray}
}
@article {11914,
	title = {A Probabilistic Clustering-Based Indoor Location Determination System},
	journal = {Technical Reports from UMIACS, UMIACS-TR-2002-30},
	year = {2002},
	month = {2002/04/04/},
	abstract = {We present an indoor location determination system based on signalstrength probability distributions for tackling the noisy wireless
channel and clustering to reduce computation requirements. We provide
two implementation techniques, namely, Joint Clustering and Incremental
Triangulation and describe their tradeoffs in terms of location
determination accuracy and computation requirement. Both techniques have
been incorporated in two implemented context-aware systems: User
Positioning System and the Rover System, both running on Compaq iPAQ
Pocket PC{\textquoteright}s with Familiar distribution of Linux for PDA{\textquoteright}s. The results
obtained show that both techniques give the user location with over 90\%
accuracy to within 7 feet with very low computation requirements, hence
enabling a set of context-aware applications.
Also UMIACS-TR-2002-30
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/1192},
	author = {Youssef,Moustafa A and Agrawala, Ashok K. and A. Udaya Shankar and Noh,Sam H}
}
@article {17681,
	title = {Adjusting the Rayleigh Quotient in Semiorthogonal Lanczos Methods},
	volume = {UMIACS-TR-2001-31},
	year = {2001},
	month = {2001/05/10/},
	institution = {Instititue for Advanced Computer Studies, Univ of Maryland, College Park},
	abstract = {In a semiorthogonal Lanczos algorithm, the orthogonality of theLanczos vectors is allowed to deteriorate to roughly the square root
of the rounding unit, after which the current vectors are
reorthogonalized.  A theorem of Simon \cite{simo:84} shows that the
Rayleigh quotient\,---\,i.e., the tridiagonal matrix produced by the
Lanczos recursion\,---\,contains fully accurate approximations to the
Ritz values in spite of the lack of orthogonality.  Unfortunately, the
same lack of orthogonality can cause the Ritz vectors to fail to
converge.  It also makes the classical estimate for the residual norm
misleadingly small.  In this note we show how to adjust the Rayleigh
quotient to overcome this problem.
(Cross-referenced as UMIACS-TR-2001-31)
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/1132},
	author = {Stewart, G.W.}
}
@article {17691,
	title = {Backward Error Bounds for Approximate Krylov Subspaces},
	volume = {UMIACS-TR-2001-32},
	year = {2001},
	month = {2001/05/10/},
	institution = {Instititue for Advanced Computer Studies, Univ of Maryland, College Park},
	abstract = {Let $A$ be a matrix of order $n$ and let $\clu\subset\comp^{n}$ be asubspace of dimension $k$.  In this note we determine a matrix $E$ of
minimal norm such that $\clu$ is a Krylov subspace of $A+E$.
(Cross-referenced as UMIACS-TR-2001-32)
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/1133},
	author = {Stewart, G.W.}
}
@article {12314,
	title = {The Design of TerraDir},
	journal = {Technical Reports from UMIACS, UMIACS-TR-2001-4299},
	year = {2001},
	month = {2001/12/17/},
	abstract = {We present the design and initial evaluation of TerraDir: an approach forimplementing customizable, distributed, peer-to-peer directories over
which a broad range of wide-area resource discovery applications can
be implemented. TerraDir{\textquoteright}s structure is two-tiered, consisting of a base
protocol for providing arbitrary application-layer connectivity, and
dynamic view materializations that efficiently realize different
user-specified views of  application-layer resources. TerraDir is
specifically
designed for data that can be arranged in a rooted hierarchy, and provides
very efficient and robust lookups over such data while still being able
to allow efficient searching.
(Also referenced as UMIACS-TR-2001-4299)
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/1161},
	author = {Bhattacharjee, Bobby and Keleher,Pete and Silaghi,Bujor}
}
@article {16154,
	title = {Designing an Interactive Message Board as a Technology Probe for Family Communication},
	journal = {Technical Reports of the Computer Science Department},
	year = {2001},
	month = {2001/10/10/},
	abstract = {In this paper, we describe the design issues and technical implementation of aninteractive Family Message Board. The Family Message Board enables members of a
distributed family to communicate with one another both synchronously and
asynchronously via simple, pen-based, digital notes. Each household running thi$
Java-based software can view, create, and manipulate notes in a zoomable space.
The Family Message Board will be used as a technology probe to help us unders$
the communication needs of distributed families, and to help us design new devi$
to meet those needs.
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/526},
	author = {Browne,Hilary and Bederson, Benjamin B. and Plaisant, Catherine and Druin, Allison}
}
@article {14164,
	title = {Preconditioners for Saddle Point Problems Arising in Computational Fluid Dynamics},
	volume = {UMIACS-TR-2001-88},
	year = {2001},
	month = {2001/12/03/},
	institution = {Instititue for Advanced Computer Studies, Univ of Maryland, College Park},
	abstract = {Discretization and linearization of the incompressible Navier-Stokesequations leads to linear algebraic systems in which the coefficient
matrix has the form of a saddle point problem
    ( F   B^T ) (u) = (f)                                          (1)
    ( B   0   ) (p)   (g)
In this paper, we describe the development of efficient and general   
iterative solution algorithms for this class of problems. We review the
case where (1) arises from the steady-state Stokes equations and show that
solution methods such as the Uzawa algorithm lead naturally to a focus on
the Schur complement operator BF^{-1}B^T together with efficient
strategies of applying the action of F^{-1} to a vector. We then discuss
the advantages of explicitly working with the coupled form of the block
system (1).  Using this point of view, we describe some new algorithms
derived by developing efficient methods for the Schur complement systems
arising from the Navier-Stokes equations, and we demonstrate their
effectiveness for solving both steady-state and evolutionary problems.
(Also referenced as UMIACS-TR-2001-88)
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu//handle/1903/1170},
	author = {Elman, Howard}
}
@article {17686,
	title = {An Arnoldi--Schur Algorithm for Large Eigenproblems},
	volume = {UMIACS-TR-2000-21},
	year = {2000},
	month = {2000/04/25/},
	institution = {Instititue for Advanced Computer Studies, Univ of Maryland, College Park},
	abstract = {Sorensen{\textquoteright}s iteratively restarted Arnoldi algorithm is one of the mostsuccessful and flexible methods for finding a few eigenpairs of a
large matrix.  However, the need to preserve structure of the Arnoldi
decomposition, on which the algorithm is based, restricts the range of
transformations that can be performed on it.  In consequence, it is
difficult to deflate converged Ritz vectors from the decomposition.
Moreover, the potential forward instability of the implicit QR
algorithm can cause unwanted Ritz vectors to persist in the
computation.  In this paper we introduce a generalized Arnoldi
decomposition that solves both problems in a natural and efficient
manner.
(Also cross-referenced as UMIACS-TR-2000-21)
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/1066},
	author = {Stewart, G.W.}
}
@article {17675,
	title = {A Generalization of Saad{\textquoteright}s Theorem on Rayleigh-Ritz Approximations},
	volume = {UMIACS-TR-99-78},
	year = {2000},
	month = {2000/02/04/},
	institution = {Instititue for Advanced Computer Studies, Univ of Maryland, College Park},
	abstract = {Let $(\lambda,x)$ be an eigenpair of the Hermitian matrix $A$ of order$n$ and let $(\mu,u)$ be a Ritz pair from a subspace $\clk$ of
$\comp^{2}$.  Saad has given a simple inequality bounding
$\sin\angle(x,u)$ in terms of $\sin\angle(x,\clk)$.  In this note we
show that this inequality can be extended to an equally simple
inequality for eigenspaces of non-Hermitian matrices.
(Also cross-referenced as UMIACS-TR-99-78)
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/1050},
	author = {Stewart, G.W.}
}
@article {17286,
	title = {Making Computer and Internet Usability a Priority},
	year = {2000},
	month = {2000/10/04/},
	abstract = {A management oriented essay on how to promote usability inorganizations.  It begins with crafting the message (Good usability is
good
business).  Then it deals with creating a cultural shift in information
technology and software engineering departments, so that the impact of
poor
design and the benefits of improvements are widely understood.  It closes
with an eight-step call to action.
Keywords: usability, technology fluency, user-centered design, software
engineering
(Also cross-referenced as UMIACS-TR-2000-70)
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/1106},
	author = {Kreitzberg,Charles B and Shneiderman, Ben}
}
@article {16651,
	title = {A SIMULATION ENVIRONMENT FOR EVOLVING MULTIAGENT COMMUNICATION},
	volume = {UMIACS-TR-2000-64},
	year = {2000},
	month = {2000/09/15/},
	institution = {Instititue for Advanced Computer Studies, Univ of Maryland, College Park},
	abstract = {A simulation environment has been created to support study of emergentcommunication.  Multiple agents exist in a two-dimensional world where they 
must find food and avoid predators.  While non-communicating agents may 
survive, the world is configured so that survival and fitness can be enhanced 
through the use of inter-agent communication.  The goal with this version of 
the simulator is to determine conditions under which simple communication 
(signaling) emerges and persists during an evolutionary process.
(Also cross-referenced as UMIACS-TR-2000-64)
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu//handle/1903/1101},
	author = {Reggia, James A. and Schultz,Reiner and Uriagereka,Juan and Wilkinson,Jerry}
}
@article {16159,
	title = {Vehicle Speed Information Displays for Public Websites A Survey of User Preferences},
	journal = {Technical Reports from UMIACS},
	year = {2000},
	month = {2000/10/09/},
	abstract = {The paper reports on a study comparing alternative presentations offreeway speed data on maps.  The goal of the study was to inform the
design of displays of real time speed data over the Internet to the
general public.  Subjects were presented with a series of displays and
asked to rate their preferences.  We looked at different choices of color
(3 colors, 6 colors or a continuous range), and proposed line, sensor,
and segment representations of the speed data.  We also collected
feedback on more complex displays such as comparison between current and
"normal" speeds, and a chart of speed variation over a period of time at
given locations. 
(Also cross-referenced as HCIL-TR-2000-23)
(Also cross-referenced as UMIACS-TR-2000-73)
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/1109},
	author = {Plaisant, Catherine and Bhamidipati,Phanikumar}
}
@article {17035,
	title = {Creating Creativity for Everyone: User Interfaces for Supporting Innovation},
	journal = {Institute for Systems Research Technical Reports},
	year = {1999},
	month = {1999///},
	abstract = {A challenge for human-computer interaction researchers and user interface designers is to construct information technologies that support creativity.This ambitious goal can be attained by building on an adequate understand-ing of creative processes. This paper offers the four-phase genex frame-work for generating excellence: - Collect: learn from previous works stored in digital libraries- Relate: consult with peers and mentors at early, middle and late stages- Create: explore, compose, and evaluate possible solutions - Donate: disseminate the results and contribute to the digital libraries Within this integrated framework, this paper proposes eight activities that require human-computer interaction research and advanced user inter-face design. A scenario about an architect illustrates the process of creative work within a genex environment.},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/6010},
	author = {Shneiderman, Ben}
}
@article {17715,
	title = {On Orthogonalization in the Inverse Power Method},
	volume = {UMIACS-TR-99-64},
	year = {1999},
	month = {1999/10/13/},
	institution = {Instititue for Advanced Computer Studies, Univ of Maryland, College Park},
	abstract = {When the inverse power method is used to compute eigenvectors of asymmetric matrix corresponding to close eigenvalues, the computed 
eigenvectors may not be orthogonal.  The cure for the problem is to 
orthogonalize the vectors using the Gram--Schmidt algorithm.  In this note
it is shown that the orthogonalization process does not cause the quality
of the eigenvectors to deteriorate.
Also cross-referenced as UMIACS-TR-99-64
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/1038},
	author = {Stewart, G.W.}
}
@article {18409,
	title = {OSMA Software Program: Domain Analysis Guidebook},
	journal = {Technical Reports from UMIACS, UMIACS-TR-99-16},
	year = {1999},
	month = {1999/03/31/},
	abstract = {Domain analysis is the process of identifying and organizing knowledge abouta class of problems. This guidebook presents a method of performing
experience domain analysis in software development organizations. The
purpose of the guidebook is to facilitate the reader in characterizing two
given development environments, applying domain analysis to model each, and
then applying an evaluation process, based upon the Goal/Metric/Paradigm, to
transfer a given development technology from one of the environments to the
other. This guidebook describes this process and gives an example of its use
within NASA.
Also cross-referenced as UMIACS-TR-99-16
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/1000},
	author = {Basili, Victor R. and Seaman,Carolyn and Tesoriero,Roseanne and Zelkowitz, Marvin V}
}
@article {17324,
	title = {Pixel Data Access for End-User Programming and Graphical Macros},
	journal = {Technical Reports from UMIACS},
	year = {1999},
	month = {1999/05/25/},
	abstract = {Pixel Data Access is an interprocess communication technique that enablesusers of graphical user interfaces to automate certain tasks.  By accessing 
the contents of the display buffer, users can search for pixel representations 
of interface elements, and then initiate actions such as mouse clicks and 
keyboard entries.   While this technique has limitations it offers users of 
current systems some unusually powerful features that are especially appealing 
in the area of end-user programming.
Also cross-referenced as UMIACS-TR-99-27
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/1009},
	author = {Potter,Richard and Shneiderman, Ben}
}
@article {17364,
	title = {Snap-Together Visualization: Coordinating Multiple Views to Explore Information},
	journal = {Technical Reports from UMIACS},
	year = {1999},
	month = {1999/06/08/},
	abstract = {Information visualizations with multiple coordinated views enable users torapidly explore complex data and discover relationships.  However, it is 
usually difficult for users to find or create the coordinated visualizations 
they need.  Snap-Together Visualization allows users to coordinate multiple 
views that are customized to their needs. Users query their relational 
database and load results into desired visualizations. Then they specify 
coordinations between visualizations for selecting, navigating, or re-querying.
Developers can make independent visualization tools {\textquoteright}snap-able{\textquoteright} by including a 
few hooks.
Also cross-referenced as UMIACS-TR-99-28
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/1010},
	author = {North,Chris and Shneiderman, Ben}
}
@article {18149,
	title = {XMT-M: A Scalable Decentralized Processor},
	volume = {UMIACS-TR-99-55},
	year = {1999},
	month = {1999/10/09/},
	institution = {Instititue for Advanced Computer Studies, Univ of Maryland, College Park},
	abstract = {A defining challenge for research in computer science and engineering hasbeen the ongoing quest for reducing the completion time of a single
computation task. Even outside the parallel processing communities, there
is little doubt that the key to further progress in this quest is to do
parallel processing of some kind. A recently proposed parallel processing
framework that spans the entire spectrum from (parallel) algorithms to
architecture to implementation is the explicit multi-threading (XMT)
framework. This framework provides:
(i) simple and natural parallel algorithms for essentially every 
general-purpose application, including notoriously difficult irregular 
integer applications, and
(ii) a multi-threaded programming model for these algorithms which
allows an {\textquoteleft}{\textquoteleft}independence-of-order{\textquoteright}{\textquoteright} semantics: every thread can proceed at
its own speed, independent of other concurrent threads. To the extent
possible, the XMT framework uses established ideas in parallel processing.
This paper presents XMT-M, a microarchitecture implementation of the XMT
model that is possible with current technology. XMT-M offers an
engineering design point that addresses four concerns: buildability,
programmability, performance, and scalability. The XMT-M hardware is
geared to execute multiple threads in parallel on a single chip: relying
on very few new gadgets, it can execute parallel threads without
busy-waits! Existing code can be run on XMT-M as a single thread without
any modifications, thereby providing backward compatibility for commercial
acceptance. Simulation-based studies of XMT-M demonstrate considerable
improvements in performance relative to the best serial processor even for
small, and therefore practical, input sizes.
(Also cross-referenced as UMIACS-TR-99-55)
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu//handle/1903/1030},
	author = {Berkovich,Efraim and Nuzman,Joseph and Franklin,Manoj and Jacob,Bruce and Vishkin, Uzi}
}
@article {15675,
	title = {On the Area of Overlap of Translated Polygons},
	volume = {CS-TR-3201},
	year = {1998},
	month = {1998/10/15/},
	institution = {Department of Computer Science, University of Maryland, College Park},
	abstract = {(Also cross-referenced as CAR-TR-699)	Given two simple polygons P and Q in the plane and a translation
vector t E R2, the area-oJ-overlap function of P and Q is the function
Ar(t) = Area(P n (t + Q)), where t + Q denotes Q translated by t. This
function has a number of applications in areas such as motion planning and
object recognition. We present a number of mathematical results regarding
this function. We also provide efficient algorithms for computing a
representation of this function, and for tracing contour curves of
constant area of o verlap.
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu//handle/1903/403},
	author = {Mount, Dave and Silverman,Ruth and Wu,Angela Y.}
}
@article {16979,
	title = {Assessing users{\textquoteright} subjective satisfaction with the Information System for Youth Services (ISYS)},
	journal = {Institute for Systems Research Technical Reports},
	year = {1998},
	month = {1998/10/15/},
	abstract = {In this investigation, the Questionnaire for User Interaction Satisfaction(QUIS 5.5), a tool for assessing users{\textquoteright} subjective satisfaction with
specific aspects of the human/computer interface was used to assess the
strengths and weaknesses of the Info rmation System for Youth Services
(ISYS). ISYS is used by over 600 employees of the Maryland State
Department of Juvenile Services (DJS) as a tracking device for juvenile
offenders. Ratings and comments were collected from 254 DJS employees who
use ISYS.  The overall mean rating across all questions was 5.1 on a one
to nine scale. The ten highest and lowest rated questions were identified.
The QUIS allowed us to isolate subgroups which were compared with mean
ratings from four measures of specific interfac e factors. The comments
obtained from users provided suggestions, complaints and endorsements of
the system. 
Also cross-referenced as CAR-TR-768
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/431},
	author = {Slaughter,Laura and Norman,Kent L and Shneiderman, Ben}
}
@article {13731,
	title = {Bilingual Lexicon Construction Using Large Corpora},
	year = {1998},
	month = {1998/10/15/},
	institution = {Instititue for Advanced Computer Studies, Univ of Maryland, College Park},
	abstract = {This paper introduces a method for learning bilingual term and sentencelevel alignments for the purpose of building lexicons.  Combining
statistical techniques with linguistic knowledge, a general algorithm
is developed for learning term and sentence alignments from large
bilingual corpora with high accuracy.  This is achieved through the
use of filtered linguistic feedback between term and sentence alignment
processes.  An implementation of this algorithm, TAG-ALIGN, is evaluated
against approaches similar to [Brown et al. 1993] that apply Bayesian
techniques for term alignment, and [Gale and Church 1991] a dynamic
programming method for aligning sentences.  The ultimate goal is to
produce large bilingual lexicons with a high degree of accuracy from
potentially noisy corpora.
(Also cross-referenced as UMIACS-TR-97-50)
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/832},
	author = {Shen,Wade and Dorr, Bonnie J}
}
@article {17001,
	title = {Browsing Unix Directories With Dynamic Queries: An Evaluation of Three Information Display Techniques},
	journal = {Technical Reports of the Computer Science Department},
	year = {1998},
	month = {1998/10/15/},
	abstract = {We designed, implemented, and evaluated an innovative concept fordynamic queries which involves the direct manipulation of small databases.  
Our domain was directories in a Unix file system.  Dynamic queries 
allow users to formulate queries and explore the databases with 
graphical widgets, such as sliders and buttons, without requiring them 
to have any knowledge about the underlying structure of the database 
query languages, or command language syntax.  Three interfaces for 
presenting directories were developed and tested with eighteen subjects in a 
within-subject design.  The results of the formative evaluation yielded 
some useful guidelines for software designers.
(Also cross-referenced as CAR-TR-605)
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/379},
	author = {Liao,Holmes and Osada,Masakazu and Shneiderman, Ben}
}
@article {17005,
	title = {Buttons vs. menus: An exploratory study of pull-down menu selection as compared to button bars},
	journal = {Technical Reports of the Computer Science Department},
	year = {1998},
	month = {1998/10/15/},
	abstract = {Button bars are a relatively new interaction method intended to speedup application use as compared to pull-down menus.  This exploratory study
compares three command selection methods: pull-down menus, button bars,
and user choice of pull-down menus or button bars.  Effectiveness was
measured in two ways: speed of selection and error rate.  15 participants
performed 15 word processor related tasks.  Results show that in
frequently used functions, such as character attribute selection (bold,
italic, u nderline, etc.), button bars are faster.  There were no
statistically significant differences in error rates between the three
interaction methods. 
(Also cross-referenced as CAR-TR-764)
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/428},
	author = {Ellis,Jason and Tran,Chi and Ryoo,Jake and Shneiderman, Ben}
}
@article {16029,
	title = {Conversational Adequacy: Mistakes are the Essence},
	volume = {UMIACS-TR-96-41},
	year = {1998},
	month = {1998/10/15/},
	institution = {Instititue for Advanced Computer Studies, Univ of Maryland, College Park},
	abstract = {We argue that meta-dialog and meta-reasoning, far from beingof only occasional use, are the very essence of conversation
and communication between agents. We give four paradigm examples
of massive use of meta-dialog where only limited base dialog
may be present, and use these to bolster our claim of centrality
for meta-dialog. We further illustrate this with related work
in active logics. We argue moreover that there may be a core
set of meta-dialog principles that is in some sense complete.
If we are right, then implementing such a set would be of
considerable interest. We give examples of existing computer
programs that converse inadequately according to our guidelines.
(Also cross-referenced as UMIACS-TR-96-41)
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu//handle/1903/824},
	author = {Perlis, Don and Purang,Khemdut}
}
@article {16026,
	title = {Defaults Denied},
	volume = {UMIACS-TR-96-61},
	year = {1998},
	month = {1998/10/15/},
	institution = {Instititue for Advanced Computer Studies, Univ of Maryland, College Park},
	abstract = {We take a tour of various themes in default reasoning, examining new ideasas well as those of Brachman, Delgrande, Poole, and Schlechta. An
underlying issue is that of stating that a potential default principle is
not appropriate.  We see this arise most dramatically as a problem in an
attempt to formalize what are often loosely called "prototypes", although
it also arises in other formal approaches to default reasoning. Some
formalisms in the literature provide solutions but not without costs.  We
propose a formalism that appears to avoid these costs; it can be seen as a
step toward a population-based set-theoretic modification of these
approaches, that may ultimately provide a closer tie to recent work on
statistical (quantitative) foundations of (qualitative) defaults([1]). 
Our analysis in particular indicates the need to resolve a conflation
between use and mention in many default formalisms. Our treatment proposes
such a resolution, and also explores the use of sets toward a more
population-based notion of default. 
(Also cross-referenced as UMIACS-TR-96-61)
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu//handle/1903/841},
	author = {Miller,Michael and Perlis, Don and Purang,Khemdut}
}
@article {16183,
	title = {The Design of a Telepathology Workstation: Exploring Remote Images},
	journal = {Technical Reports of the Computer Science Department},
	year = {1998},
	month = {1998/10/15/},
	abstract = {Dynamic telepathology uses a tele-operated microscope to allowpathologists to view samples at a remote location.  However, time delays
introduced by remote operation have made use of a commercial dynamic
telepathology system difficult and frustrating.  This paper describes
experiments to evaluate and redesign the user interface.  We also make
recomendations for further automation to support the pathology process
and increase the usefulness of the system.
Copyright, 1994, by David Carr, Catherine Plaisant, and Hiroaki Hasegawa
All rights reserved
(Also cross-referenced as CAR-TR-708)
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/408},
	author = {Carr,David and Plaisant, Catherine and Hasegawa,Hiroaki}
}
@article {17076,
	title = {Designing to facilitate browsing: A look back at the Hyperties workstation browser},
	year = {1998},
	month = {1998/10/15/},
	abstract = {Since browsing hypertext can present a formidable cognitivechallenge, user interface design plays a major role in determining 
acceptability.  In the Unix workstation version of Hyperties, a 
research-oriented prototype, we focussed on design features that 
facilitate browsing.  We first give a general overview of Hyperties 
and its markup language.  Customizable documents can be 
generated by the conditional text feature that enables dynamic and 
selective display of text and graphics.  In addition we present:	
- an innovative solution to link identification: pop-out graphical 
buttons of arbitrary shape.	
- application of pie menus to permit low cognitive load actions that 
reduce the distraction of common actions, such as page turning 
or window selection.	
- multiple window selection strategies that reduce clutter and 
housekeeping effort.  We preferred piles-of-tiles, in which 
standard-sized windows were arranged in a consistent pattern on 
the display and actions could be done rapidly, allowing users to 
concentrate on the contents.
(Also cross-referenced as CAR-TR-494)
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/362},
	author = {Shneiderman, Ben and Plaisant, Catherine and Botafogo,Rodrigo and Hopkins,Don and Weiland,William}
}
@article {17695,
	title = {Direction of Arrival and the Rank-Revealing URV Decomposition},
	volume = {UMIACS-TR-91-166},
	year = {1998},
	month = {1998/10/15/},
	institution = {Instititue for Advanced Computer Studies, Univ of Maryland, College Park},
	abstract = {In many practical direction-of-arrival (DOA) problems the numberof sources and their directions from an antenna array do not remain
stationary.  Hence a practical DOA algorithm must be able to track
changes with a minimal number of snapshots.  In this paper we describe
DOA algorithms, based on a new decomposition, that are not expensive
to compute or difficult to update.  The algorithms are compared with
algorithms based on the singular value decomposition (SVD).
(Also cross-referenced as UMIACS-TR-91-166)
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/561},
	author = {Boman,E. C and Griffen,M. F and Stewart, G.W.}
}
@article {16181,
	title = {Exploring LifeLines to Visualize Patient Records},
	journal = {Technical Reports of the Computer Science Department},
	year = {1998},
	month = {1998/10/15/},
	abstract = {LifeLines provide a general visualization environment for personalhistories.  We explored its use for medical patient records.  A one
screen overview of the record using timelines provides direct access to
the data.  Problems, hospitalization and medications can be represented
as horizontal lines, while icons represent discrete events such as
physician consultations (and progress notes) or tests. Line color and
thickness can illustrate relationships or significance.  Techniques are
described to display large records.  Rescaling tools and filters allow
users to focus on part of the information, revealing more details.
Computerized medical records pose tremendous problems to system
developers.  Infrastructure and privacy issues need to be resolved
before physicians can even start using the records.  Non-intrusive
hardware is required for physicians to do their work (i.e. interview
patients) away from their desk and cumbersome workstations.  But all
the efforts to solve those problems will only succeed if appropriate
attention is also given to the user interface design [1][8].  Long
lists to scroll, clumsy search, endless menus and lengthy dialogs will
lead to user rejection.  But techniques are being developed to
summarize, filter and present large amount of information, leading us
to believe that rapid access to needed data is possible with careful
design.
While more attention is now put on developing standards for gathering
medical records we found that very little effort had been made to
design appropriate visualization and navigation techniques to present
and explore personal history records.  An intuitive approach to
visualizing histories is to use graphical time series.  The consistent,
linear time scale allows comparisons and relations between the
quantities displayed. Data can be graphed on the timeline to show time
series of quantitative data.  Highly interactive interfaces turn the
display into a meaningfully structured menu with direct access to the
data needed to review a problem or conduct the diagnosis.
Also cross-referenced as CAR-TR-819
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/455},
	author = {Plaisant, Catherine and Rose,Anne}
}
@article {16178,
	title = {Facilitating Network Data Exploration with Query Previews: A Study of User Performance and Preference},
	journal = {Technical Reports of the Computer Science Department},
	year = {1998},
	month = {1998/10/15/},
	abstract = {Current network data exploration systems which use command languages (e.g.SQL) or form fill-in interfaces fail to give users an indication of the
distribution of data items.  This leads many users to waste time posing
queries which have zero-hit or mega-hit result sets.  Query previewing is
a novel visual approach for browsing huge networked information
warehouses.  Query previews supply data distribution information about the
database that is being searched and give continuous feedback about the
size of the result set for the query as it is being formed.  Our
within-subjects empirical comparison studied 12 subjects using a form
fill-in interface with and without query previews.  We found statistically
significant differences showing that query previews sped up performance
1.6 to 2.1 times and led to higher subjective satisfaction.
(Also cross-referenced as UMIACS-98-14)
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/488},
	author = {Tanin,Egemen and Lotem,Amnon and Haddadin,Ihab and Shneiderman, Ben and Plaisant, Catherine and Slaughter,Laura}
}
@article {18832,
	title = {Feature Recognition for Interactive Applications: Exploiting Distributed Resources},
	volume = {UMIACS-TR-94-126.1},
	year = {1998},
	month = {1998/10/15/},
	institution = {Instititue for Advanced Computer Studies, Univ of Maryland, College Park},
	abstract = {The availability of low-cost computational power is a drivingforce behind the growing sophistication of CAD software. Tools designed 
to reduce time-consuming build-test-redesign iterations are essential 
for increasing engineering quality and productivity. However, automation 
of the design process poses many difficult computational problems. As 
more downstream engineering activities are being considered during the
design phase, guaranteeing reasonable response times within design 
systems becomes problematic. Design is an interactive process and speed 
is a critical factor in systems that enable designers to explore and 
experiment with alternative ideas during the design phase. Achieving 
interactivity requires an increasingly sophisticated allocation
of computational resources in order to perform realistic design analyses 
and generate feedback in real time.
	This paper presents our initial efforts to develop techniques to 
apply distributed algorithms to the problem of recognizing machining 
features from solid models. Existing work on recognition of features has 
focused exclusively on serial computer architectures. Our objective is to 
show that distributed algorithms can be employed on realistic parts
with large numbers of features and many geometric and topological 
entities to obtain significant improvements in computation time using 
existing hardware and software tools. Migrating solid modeling applications 
toward a distributed computing framework enables interconnection of many of 
the autonomous and geographically diverse software tools used in the 
modern manufacturing enterprise.
(Also cross-referenced as UMIACS-TR-94-126.1)
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu//handle/1903/675},
	author = {Regli,William C. and Gupta, Satyandra K. and Nau, Dana S.}
}
@article {17702,
	title = {Gaussian Elimination, Perturbation Theory and Markov Chains},
	volume = {UMIACS-TR-92-23},
	year = {1998},
	month = {1998/10/15/},
	institution = {Instititue for Advanced Computer Studies, Univ of Maryland, College Park},
	abstract = {The purpose of this paper is to describe the special problems thatemerge when Gaussian elimination is used to determinin the
steady-state vector of a Markov chain.
(Also cross-referenced as UMIACS-TR-92-23)
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/564},
	author = {Stewart, G.W.}
}
@article {17703,
	title = {Implementing an Algorithm for Solving Block Hessenberg Systems},
	volume = {UMIACS-TR-94-70},
	year = {1998},
	month = {1998/10/15/},
	institution = {Instititue for Advanced Computer Studies, Univ of Maryland, College Park},
	abstract = {This paper describes the implementation of a recursive descent methodfor solving block Hessenberg systems.  Although the algorithm is
conceptually simple, its implementation in C (a natural choice of
language given the recursive nature of the algorithm and its data) is
nontrivial.  Particularly important is the balance between ease of
use, computational efficiency, and flexibility.
(Also cross-referenced as UMIACS-TR-94-70)
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/642},
	author = {Stewart, G.W.}
}
@article {16182,
	title = {Incorporating String Search in a Hypertext System:User Interface and Signature File Design Issues},
	journal = {Technical Reports of the Computer Science Department},
	year = {1998},
	month = {1998/10/15/},
	abstract = {Hypertext systems provide an appealing mechanism forinformally browsing databases by traversing selectable links.  
However, in many fact finding situations string search is an 
effective complement to browsing.  This paper describes the 
application of the signature file method to achieve rapid and 
convenient string search in small personal computer hypertext 
environments. The method has been implemented in a prototype, 
as well as in a commercial product. Performance data for search 
times and storage space are presented from a commercial 
hypertext database. User interface issues are then discussed.  
Experience with the string search interface indicates that it was 
used sucessfully by novice users.
(Also cross-referenced as CAR-TR-448)
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/359},
	author = {Faloutsos,Christos and Lee,Raymond and Plaisant, Catherine and Shneiderman, Ben}
}
@article {17704,
	title = {Incremental Condition Calculation and Column Selection},
	volume = {UMIACS-TR-90-87},
	year = {1998},
	month = {1998/10/15/},
	institution = {Instititue for Advanced Computer Studies, Univ of Maryland, College Park},
	abstract = {This paper describes a method for calculating the condition number ofa matrix in the Frobenius norm that can be used to select columns in
the course of computing a QR decomposition.  When the number of rows
of the matrix is much greater than the number of columns, the
additional overhead is negligible.  Limited numerical experiments
suggest that the method is quite good at finding gaps in the singular
values of the matrix.
Additional files are available via anonymous ftp at: 
thales.cs.umd.edu in the directory pub/reports
(Also cross-referenced as UMIACS-TR-90-87)
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/550},
	author = {Stewart, G.W.}
}
@article {17710,
	title = {On an Inexpensive Triangular Approximation to the Singular Value Decomposition},
	volume = {UMIACS-TR-97-75},
	year = {1998},
	month = {1998/10/15/},
	institution = {Instititue for Advanced Computer Studies, Univ of Maryland, College Park},
	abstract = {In this paper we introduce a new decomposition called the pivotedQLP~decomposition.  It is computed by applying pivoted orthogonal
triangularization to the columns of the matrix $X$ in question to get
an upper triangular factor $R$ and then applying the same procedure to
the rows of $R$ to get a lower triangular matrix $L$.  The diagonal
elements of $R$ are called the R-values of $X$; those of $L$ are
called the L-values.  Numerical examples show that the L-values track
the singular values of $X$ with considerable fidelity\,---\,far better
than the R-values.  At a gap in the L-values the decomposition
provides orthonormal bases of analogues of row, column, and null
spaces provided of $X$.  The decomposition requires no more than twice
the work required for a pivoted QR~decomposition.  The computation of
$R$ and $L$ can be interleaved, so that the computation can be
the rows of $R$ to get a lower triangular matrix $L$.  The diagonal
elements of $R$ are called the R-values of $X$; those of $L$ are
called the L-values.  Numerical examples show that the L-values track
the singular values of $X$ with considerable fidelity\,---\,far better
than the R-values.  At a gap in the L-values the decomposition
provides orthonormal bases of analogues of row, column, and null
spaces provided of $X$.  The decomposition requires no more than twice
the work required for a pivoted QR~decomposition.  The computation of
$R$ and $L$ can be interleaved, so that the computation can be
terminated at any suitable point, which makes the decomposition
especially suitable for low-rank determination problems.  The
interleaved algorithm also suggests a new, efficient 2-norm estimator.
(Also cross-referenced as UMIACS-TR-97-75)
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/920},
	author = {Stewart, G.W.}
}
@article {17713,
	title = {On Infinitely Many Algorithms for Solving Equations},
	volume = {UMIACS-TR-92-121},
	year = {1998},
	month = {1998/10/15/},
	institution = {Instititue for Advanced Computer Studies, Univ of Maryland, College Park},
	abstract = {Translated by G. W. StewartThis report contains a translation of {\textquoteleft}{\textquoteleft}Ueber unendlich viele
Algorithmen zur Aufl\"osung der Gleichungen,{\textquoteright}{\textquoteright} a paper by E.
Schr\"oder which appeared in {\it Mathematische Annalen\/} in 1870.
(Also cross-referenced as UMIACS-TR-92-121)
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/577},
	author = {Schroeder,E. and Stewart, G.W.}
}
@article {17257,
	title = {Interactive Smooth Zoomming in a Starfield Information Visualization},
	journal = {Technical Reports of the Computer Science Department},
	year = {1998},
	month = {1998/10/15/},
	abstract = {This paper discusses the design and implementation of interactivesmooth zooming of a starfield display. A starfield display is a two
dimensional scatterplot of a multidimensional database where every item
from the database is represented as a small colored glyph whose position
is determined by its ranking along ordinal attributes of the items laid out
on the axes. One way of navigating this visual information is by using a
zooming tool to incrementally zoom in on the items by varying the
attribute range on either axis independently - such zooming causes the
glyphs to move continuously and to grow or shrink.
To get a feeling of flying through the data, users should be able to
track the motion of each glyph without getting distracted by flicker or
large jumps - conditions that necessitate high display refresh rates and
closely spaced glyphs on successive frames. Although the use of
high-speed hardware can achieve the required visual effect for small
databases, the twin software bottlenecks of rapidly accessing display
items and constructing a new display image fundamentally retard the
refresh rate. Our work explores several methods to overcome these
bottlenecks, presents a taxonomy of various zooming methods and
introduces a new widget, the zoom bar, that facilitates zooming.
(Also cross-referenced as CAR-TR-714)
(Also cross-referenced as ISR-TR-94-46)
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/411},
	author = {Jog,Ninad and Shneiderman, Ben}
}
@article {16180,
	title = {Life cycle of user interface techniques: The DJJ information system design Process},
	journal = {Technical Reports of the Computer Science Department},
	year = {1998},
	month = {1998/10/15/},
	abstract = {To take advantage of todays technology, many organizations are migrating fromtheir legacy systems.  With help from the Human-Computer Interaction Laboratory 
(HCIL) and Cognetics Corporation, the Maryland Department of Juvenile Justice (DJJ) 
is currently undergoing an effort to redesign their information system to take advantage 
of graphical user interfaces.  As a research lab, HCIL identifies interesting research 
problems and then prototypes solutions.  As a project matures, the exploratory 
prototypes are adapted to suit the end product requirements.  This case study 
describes the life cycle of three DJJ prototypes: (1) LifeLines, which uses time lines to 
display an overview of a youth in one screen, (2) the DJJ Navigator, which helps 
manage individual workloads by displaying different user views, and (3) the 
ProgramFinder, a tool for selecting the best program for a youth.
(Also cross-referenced as CAR-TR-826)
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/458},
	author = {Rose,Anne and Ellis,Jason and Plaisant, Catherine and Greene,Stephan}
}
@article {18147,
	title = {Looking to Parallel Algorithms for ILP and Decentralization},
	volume = {CS-TR-3921},
	year = {1998},
	month = {1998/10/15/},
	institution = {Department of Computer Science, University of Maryland, College Park},
	abstract = {We introduce explicit multi-threading (XMT), a decentralized architecturethat exploits fine-grained SPMD-style programming; a SPMD program can
translate directly to MIPS assembly language using three additional
instruction primitives. The motivation for XMT is: (i) to define an
inherently decentralizable architecture, taking into account that the
performance of future integrated circuits will be dominated by wire costs,
(ii) to increase available instruction-level parallelism (ILP) by
leveraging expertise in the world of parallel algorithms, and (iii) to
reduce hardware complexity by alleviating the need to detect ILP at
run-time: if parallel algorithms can give us an overabundance of work to
do in the form of thread-level parallelism, one can extract
instruction-level parallelism with greatly simplified dependence-checking.
We show that implementations of such an architecture tend towards
decentralization and that, when global communication is necessary, overall
performance is relatively insensitive to large on-chip delays. We compare
the performance of the design to more traditional parallel architectures
and to a high-performance superscalar implementation, but the intent is
merely to illustrate the performance behavior of the organization and to
stimulate debate on the viability of introducing SPMD to the single-chip
processor domain. We cannot offer at this stage hard comparisons with
well-researched models of execution.
When programming for the SPMD model, the total number of operations that
the processor has to perform is often slightly higher. To counter this, we
have observed that the length of the critical path through the dynamic
execution graph is smaller than in the serial domain, and the amount of
ILP is correspondingly larger. Fine-grained SPMD programming connects with
a broad knowledge base in parallel algorithms and scales down to provide
good performance relative to high-performance superscalar designs even
with small input sizes and small numbers of functional units.
Keywords: Fine-grained SPMD, parallel algorithms. spawn-join, prefix-sum,
instruction-level parallelism, decentralized architecture. 
(Also cross-referenced as UMIACS-TR- 98-40)
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu//handle/1903/496},
	author = {Berkovich,Efraim and Jacob,Bruce and Nuzman,Joseph and Vishkin, Uzi}
}
@article {15227,
	title = {Low Degree Spanning Trees of Small Weight},
	volume = {UMIACS-TR-94-1},
	year = {1998},
	month = {1998/10/15/},
	institution = {Instititue for Advanced Computer Studies, Univ of Maryland, College Park},
	abstract = {Given n points in the plane, the degree-K spanning tree problemasks for a spanning tree of minimum weight in which the degree of each
vertex is at most K. This paper addresses the problem of computing 
low-weight degree-K spanning trees for K>2. It is shown that for an arbitrary
collection of n points in the plane, there exists a spanning tree of
degree three whose weight is at most 1.5 times the weight of a minimum
spanning tree. It is shown that there exists a spanning tree of
degree four whose weight is at most 1.25 times the weight of a minimum
spanning tree. These results solve open problems posed by Papadimitriou
and Vazirani.  Moreover, if a minimum spanning tree is given as part
of the input, the trees can be computed in O(n) time.
The results are generalized to points in higher dimensions. It is
shown that for any d [greater than or equal to] 3, an arbitrary 
collection of points in DimD contains a spanning tree of degree three, 
whose weight is at most 5/3 times the weight of a minimum spanning 
tree. This is the first paper that  achieves factors better than two for 
these problems.
(Also cross-referenced as UMIACS-TR-94-1)
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu//handle/1903/611},
	author = {Khuller, Samir and Raghavachari,Balaji and Young,Neal}
}
@article {15674,
	title = {Minimum Enclosures with Specified Angles},
	volume = {CS-TR-3219},
	year = {1998},
	month = {1998/10/15/},
	institution = {Department of Computer Science, University of Maryland, College Park},
	abstract = {Given a convex polygon P, an m-envelope is a convex m-sidedpolygon that contains P. Given any convex polygon P, and any sequence of m
> 3 angles A = ((11Xct2X@..ckm) we consider the problem of computing
the minimum area m-envelope for P whose counte rclockwise sequence of
exterior angles is given by A. We show that such envelopes can be computed
in O(nm log m) time. The main result on which the correctness of the
algorithm rests is a flushness condition stating that for any locally
minimum enclosure with specified angles, one of its sides must be
collinear with one of the sides of P. 
(Also cross-referenced as CAR-TR-701)
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu//handle/1903/405},
	author = {Mount, Dave and Silverman,Ruth}
}
@article {14944,
	title = {An On-line Variable Length Binary Encoding},
	volume = {UMIACS-TR-95-39},
	year = {1998},
	month = {1998/10/15/},
	institution = {Instititue for Advanced Computer Studies, Univ of Maryland, College Park},
	abstract = {We present a methodology of an on-line variable-length binaryencoding of a set of integers. The basic principle of this methodology is
to maintain the prefix property amongst the codes assigned on-line to a
set of integers growing dynamically. The prefix property enables unique
decoding of a string of elements from this set. To show the utility of
this on-line variable length binary encoding, we apply this methodology to
encode the LZW codes. Application of this encoding scheme significantly
improves the compression achieved by the standard LZW scheme. This
encoding can be applied in other compression schemes to encode the
pointers using variable-length binary codes. 
(Also cross-referenced as UMIACS-TR-95-39)
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/714},
	author = {Acharya,Tinku and JaJa, Joseph F.}
}
@article {15008,
	title = {Parallel Algorithms for Image Histogramming and Connected Components with an Experimental Study},
	volume = {UMIACS-TR-94-133},
	year = {1998},
	month = {1998/10/15/},
	institution = {Instititue for Advanced Computer Studies, Univ of Maryland, College Park},
	abstract = {This paper presents efficient and portable implementations of two   useful primitives in image processing algorithms, histogramming and
   connected components.  Our general framework is a single-address
   space, distributed memory programming model.  We use efficient
   techniques for distributing and coalescing data as well as efficient
   combinations of task and data parallelism.  Our connected components
   algorithm uses a novel approach for parallel merging which performs
   drastically limited updating during iterative steps, and concludes
   with a total consistency update at the final step. The algorithms have
   been coded in Split-C and run on a variety of platforms.  Our
   experimental results are consistent with the theoretical analysis and
   provide the best known execution times for these two primitives, even
   when compared with machine specific implementations.  More efficient
   implementations of Split-C will likely result in even faster
   execution times. 
(Also cross-referenced as UMIACS-TR-94-133.)
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/681},
	author = {Bader,David A. and JaJa, Joseph F.}
}
@article {14934,
	title = {A Parallel Sorting Algorithm With an Experimental Study},
	volume = {UMIACS-TR-95-102},
	year = {1998},
	month = {1998/10/15/},
	institution = {Instititue for Advanced Computer Studies, Univ of Maryland, College Park},
	abstract = {Previous schemes for sorting on general-purpose parallel machineshave had to choose between poor load balancing and irregular
communication or multiple rounds of all-to-all personalized
communication. In this paper, we introduce a novel variation on sample
sort which uses only two rounds of regular all-to-all personalized
communication in a scheme that yields very good load balancing with
virtually no overhead. This algorithm was implemented in Split-C and
run on a variety of platforms, including the Thinking Machines CM-5,
the IBM SP-2, and the Cray Research T3D. We ran our code using widely
different benchmarks to examine the dependence of our algorithm on the
input distribution. Our experimental results are consistent with the
theoretical analysis and illustrate the efficiency and scalability of
our algorithm across different platforms. In fact, it seems to
outperform all similar algorithms known to the authors on these
platforms, and its performance is invariant over the set of input
distributions unlike previous efficient algorithms. Our results also
compare favorably with those reported for the simpler ranking problem
posed by the NAS Integer Sorting (IS) Benchmark.
(Also cross-referenced as UMIACS-TR-95-102)
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/768},
	author = {Helman,David R. and Bader,David A. and JaJa, Joseph F.}
}
@article {17722,
	title = {On the Perturbation of LU, Cholesky, and QR Factorizations},
	volume = {UMIACS-TR-92-24},
	year = {1998},
	month = {1998/10/15/},
	institution = {Instititue for Advanced Computer Studies, Univ of Maryland, College Park},
	abstract = {To appear in SIMAXIn this paper error bounds are derived for a first order expansion of
the LU factorization of a perturbation of the identity.  The results
are applied to obtain perturbation expansions of the LU, Cholesky, and
QR factorizations.
(Also cross-referenced as UMIACS-TR-92-24)
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/565},
	author = {Stewart, G.W.}
}
@article {17730,
	title = {Perturbation Theory for the Singular Value Decomposition},
	volume = {UMIACS-TR-90-124},
	year = {1998},
	month = {1998/10/15/},
	institution = {Instititue for Advanced Computer Studies, Univ of Maryland, College Park},
	abstract = {The singular value decomposition has a number of applications in digitalsignal processing.  However, the the decomposition must be computed from a
matrix consisting of both signal and noise.  It is therefore important to
be able to assess the effects of the noise on the singular values and
singular vectors\,---\,a problem in classical perturbation theory.  In
this paper we survey the perturbation theory of the singular value
decomposition. 
(Also cross-referenced as UMIACS-TR-90-124)
Appeared in SVD and Signal Processing, II, R. J. Vacarro ed., 
Elsevier, Amsterdam, 1991.
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/552},
	author = {Stewart, G.W.}
}
@article {18148,
	title = {Project for Developing Computer Science Agenda(s) for High-Performance Computing: An Organizer{\textquoteright}s Summary},
	volume = {UMIACS-TR-94-129},
	year = {1998},
	month = {1998/10/15/},
	institution = {Instititue for Advanced Computer Studies, Univ of Maryland, College Park},
	abstract = {Designing a coherent agenda for the implementation of the HighPerformance Computing (HPC) program is a nontrivial technical challenge. 
Many computer science and engineering researchers in the area of HPC, who 
are affiliated with U.S. institutions, have been invited to contribute 
their agendas. We have made a considerable effort to give many in that 
research community the opportunity to write a position paper. This 
explains why we view the project as placing a mirror in front of the 
community, and hope that the mirror indeed reflects many of the opinions 
on the topic. 
	The current paper is an organizer{\textquoteright}s summary and represents his reading 
of the position papers. This summary is his sole responsibility. It is 
respectfully submitted to the NSF.
(Also cross-referenced as UMIACS-TR-94-129)
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu//handle/1903/677},
	author = {Vishkin, Uzi}
}
@article {17333,
	title = {Providing Advisory Notices for UNIX Command Users: Design, Implementation, and Empirical Evaluations},
	journal = {Technical Reports of the Computer Science Department},
	year = {1998},
	month = {1998/10/15/},
	abstract = {UNIX Notices (UN) was developed to study the problems in providing advice tousers of complex systems.  The issues studied were: what, when, and how 
to present the advice.  
The first experiment with 24 subjects examined how different presentation 
styles affect the 
effectiveness of UNs advice. The three presentation styles studied were: 
notice appears in separate window; notice appears only on request; 
notice appears in users window immediately.  The results 
showed that the third style was significantly more effective than the first style.  Furthermore, the 
results indicated that the most effective presentation method is also the most disruptive.
The second experiment with 29 subjects studied how delay in the advice feedback affects the 
performance of UN.  The treatments were: immediate feedback, feedback at end of session, and no 
feedback.  Over a period of 6 weeks, the commands entered by the subjects were logged and 
studied.  The results showed that immediate feedback caused subjects to repeat significantly fewer 
inefficient command sequences.  However, immediate feedback and feedback at end of session 
may have given subjects a negative feeling towards UNIX.
(Also cross-referenced as CAR-TR-651)
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/387},
	author = {Kuah,Boon-Teck and Shneiderman, Ben}
}
@article {17731,
	title = {QR Sometimes Beats Jacobi},
	volume = {UMIACS-TR-95-32},
	year = {1998},
	month = {1998/10/15/},
	institution = {Instititue for Advanced Computer Studies, Univ of Maryland, College Park},
	abstract = {This note exhibits a symmetric matrix having a small eigenvalue that iscomputed accurately by the QR algorithm but not by Jacobi{\textquoteright}s method.
(Also cross-referenced as UMIACS-TR-95-32)
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/709},
	author = {Stewart, G.W.}
}
@article {17342,
	title = {Reflections on authoring, editing and managing hypertex},
	journal = {Technical Reports of the Computer Science Department},
	year = {1998},
	month = {1998/10/15/},
	abstract = {This chapter offers recommendations for potential authors of hypertextdocuments based on the experience of designing a hypertext system and 
of creating a series of substantial hypertext databases on personal 
computers and larger workstations.  Advice on choosing  projects, 
identifying useful author tool features, and structuring knowledge is 
presented.  Additional issues such as the design of the root document, 
article size, and conversion from existing databases are covered.  While 
hypertext has exciting potentials, the dangers of poor design must 
be overcome to create attractive and effective products.
(Also cross-referenced as CAR-TR-410)
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/357},
	author = {Shneiderman, Ben}
}
@article {17733,
	title = {Rounding Errors in Solving Block Hessenberg Systems},
	volume = {UMIACS-TR-94-105},
	year = {1998},
	month = {1998/10/15/},
	institution = {Instititue for Advanced Computer Studies, Univ of Maryland, College Park},
	abstract = {A rounding error analysis is presented for a divide-and-conquer   algorithm to solve linear systems with block Hessenberg matrices.
   Conditions are derived under which the algorithm computes a
   backward stable solution.  The algorithm is shown to be stable for
   diagonally dominant matrices and for M-matrices.
(Also cross-referenced as UMIACS-TR-94-105)
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/661},
	author = {Von Matt,Urs and Stewart, G.W.}
}
@article {15021,
	title = {Scalable Data Parallel Algorithms for Texture Synthesis and Compression using Gibbs Random Fields},
	volume = {UMIACS-TR-93-80},
	year = {1998},
	month = {1998/10/15/},
	institution = {Instititue for Advanced Computer Studies, Univ of Maryland, College Park},
	abstract = {This paper introduces scalable data parallel algorithms for image    processing.  Focusing on Gibbs and Markov Random Field model
    representation for textures, we present parallel algorithms for
    texture synthesis, compression, and maximum likelihood parameter
    estimation, currently implemented on Thinking Machines CM-2 and CM-5.
    Use of fine-grained, data parallel processing techniques yields
    real-time algorithms for texture synthesis and compression that are
    substantially faster than the previously known sequential
    implementations.  Although current implementations are on Connection
    Machines, the methodology presented here enables machine independent
    scalable algorithms for a number of problems in image processing and
    analysis.
(Also cross-referenced as UMIACS-TR-93-80.)
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/596},
	author = {Bader,David A. and JaJa, Joseph F. and Chellapa, Rama}
}
@article {11919,
	title = {Scheduling Aperiodic and Sporadic Tasks in Hard Real-Time Systems},
	journal = {Technical Reports from UMIACS, UMIACS-TR-97-44},
	year = {1998},
	month = {1998/10/15/},
	abstract = {The stringent timing constraints as well as the functional correctnessare essential requirements of hard real-time systems. In such systems,
scheduling plays a very important role in satisfying these constraints.
The priority based scheduling schemes have been used commonly  
due to the simplicity of the scheduling algorithm. However, in the presence
of task interdependencies and complex timing constraints, such
scheduling schemes may not be appropriate due to the lack
of an efficient mechanism to schedule them and to
carry out the schedulability analysis. In contrast, 
the time based scheduling scheme may be used to schedule a set of tasks
with greater degree of schedulability
achieved at a cost of higher complexity of off-line scheduling.
One of the drawbacks of currently available scheduling schemes, 
however, is known to be their
inflexibility in dynamic environments where dynamic processes
exist, such as aperiodic and sporadic processes.
We develop and analyze scheduling schemes which efficiently provide
the flexibility required in real-time systems
for scheduling processes arriving dynamically. 
This enables static hard periodic processes and dynamic processes(aperiodic
or sporadic) to be jointly scheduled.
(Also cross-referenced as UMIACS-TR-97-44)
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/900},
	author = {Choi,Seonho and Agrawala, Ashok K.}
}
@article {17734,
	title = {SRRIT--A FORTRAN Subroutine to Calculate the Dominant Invariant Subspace of a Nonsymmetric Matrix},
	volume = {UMIACS-TR-92-61},
	year = {1998},
	month = {1998/10/15/},
	institution = {Instititue for Advanced Computer Studies, Univ of Maryland, College Park},
	abstract = {SRRIT is a FORTRAN program to calculate an approximateorthonormal basis for a dominant invariant subspace of a real matrix
$A$ by the method of simultaneous iteration \cite{stewart76a}.
Specifically, given an integer $m$, {\sl SRRIT} attempts to compute a
matrix $Q$ with $m$ orthonormal columns and real quasi-triangular
matrix $T$ of order $m$ such that the equation
\[
AQ = QT
\]
is satisfied up to a tolerance specified by the user.  The
eigenvalues of $T$ are approximations to the $m$ largest eigenvalues
of $A$, and the columns of $Q$ span the invariant subspace
corresponding to those eigenvalues.  {\sl SRRIT} references $A$ only
through a user provided subroutine to form the product $AQ$; hence it
is suitable for large sparse problems.
(Also cross-referenced as UMIACS-TR-92-61)
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/572},
	author = {Bai,Z. and Stewart, G.W.}
}
@article {15673,
	title = {Stabbing Orthogonal Objects in 3-Space},
	volume = {UMIACS-TR-96-71},
	year = {1998},
	month = {1998/10/15/},
	institution = {Instititue for Advanced Computer Studies, Univ of Maryland, College Park},
	abstract = {We consider a problem that arises in the design of data structuresfor answering {\em visibility range queries}, that is, given a
$3$-dimensional scene defined by a set of polygonal patches, 
we wish to preprocess the scene to answer queries involving the set of
patches of the scene that are visible from a given range of points
over a given range of viewing directions.  These data structures 
recursively subdivide space into cells until some criterion is satisfied.  
One of the important problems that arise in the construction of
such data structures is that of determining whether a cell represents
a nonempty region of space, and more generally computing the size of
a cell.
In this paper we introduce a measure of the {\em size} of the subset
of lines in 3-space that stab a given set of $n$ polygonal patches,
based on the maximum angle and distance between any two lines in the set.
Although the best known algorithm for computing this size measure runs
in $O(n^2)$ time, we show that if the polygonal patches are orthogonal
rectangles, then this measure can be approximated to within a constant
factor in $O(n)$ time.
(Also cross-referenced as UMIACS-TR-96-71)
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu//handle/1903/850},
	author = {Mount, Dave and Pu,Fan-Tao}
}
@article {17716,
	title = {On Sublinear Convergence},
	volume = {UMIACS-TR-95-92},
	year = {1998},
	month = {1998/10/15/},
	institution = {Instititue for Advanced Computer Studies, Univ of Maryland, College Park},
	abstract = {This note develops a theory of sublinearly convergingsequences, including a categorization of the rates of convergence and a 
method for determining the rate from an iteration function.
(Also cross-referenced as UMIACS-TR-95-92)
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/760},
	author = {Stewart, G.W.}
}
@article {13717,
	title = {A Survey of Multilingual Text Retrieval},
	year = {1998},
	month = {1998/10/15/},
	institution = {Instititue for Advanced Computer Studies, Univ of Maryland, College Park},
	abstract = {This report reviews the present state of the artin selection of texts in one language based on queries in another, a
problem we refer to as {\textquoteleft}{\textquoteleft}multilingual{\textquoteright}{\textquoteright} text retrieval.  Present
applications of multilingual text retrieval systems are limited by the
cost and complexity of developing and using the multilingual thesauri
on which they are based and by the level of user training that is
required to achieve satisfactory search effectiveness.  A general
model for multilingual text retrieval is used to review the
development of the field and to describe modern production and
experimental systems.  The report concludes with some observations on
the present state of the art and an extensive bibliography of the
technical literature on multilingual text retrieval.  The research 
reported herein was supported, in part, by Army Research
Office contract DAAL03-91-C-0034 through Battelle Corporation, NSF NYI
IRI-9357731, Alfred P.  Sloan Research Fellow Award BR3336, and a
General Research Board Semester Award. 
(Also cross-referenced as UMIACS-TR-96-19)
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/807},
	author = {Oard, Douglas and Dorr, Bonnie J}
}
@article {17741,
	title = {Time-Domain Extraction of Broad-Band Sources by Tikhonov-Phillips Regularization of Triangular Toeplitz Kernels*},
	volume = {UMIACS-TR-95-87},
	year = {1998},
	month = {1998/10/15/},
	institution = {Instititue for Advanced Computer Studies, Univ of Maryland, College Park},
	abstract = {Single receiver source deconvolution in a shallow waterenvironment is an ill-posed problem whose difficulty is compounded by the
multipath nature of the propagation operator. If only sources that are
quiescent prior to some initial time to are considered, the result of
discretizatizing the problem in the time domain is an ill-conditioned
triangular Toeplitz system. In this paper we show how an algorithm of
Elden can be used to implement Tikhonov-Phillips regularization for this
system. Unlike the multichannel deconvolution techniques used in
underwater acoustics, this method can extract source signatures using the
outputs of a single sensor. In addition, when the propagation is multipath
and source signature extraction is performed as part of an optimization
procedure for environmental inversion, we can work with shorter time
windows so that the process becomes computationally more efficient than
frequency domain deconvolution. A number of examples of the use of the
Tikhonov-Philips regularization method for source series extraction are
provided. 
(Also cross-referenced as UMIACS-TR-95-87)
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/755},
	author = {Roginsky,Jacob and Stewart, G.W.}
}
@article {17739,
	title = {The Triangular Matrices of Gaussian Elimination and Related Decompositions},
	volume = {UMIACS-TR-95-91},
	year = {1998},
	month = {1998/10/15/},
	institution = {Instititue for Advanced Computer Studies, Univ of Maryland, College Park},
	abstract = {It has become a commonplace that triangular systems are solved tohigher accuracy than their condition would warrant. This observation is
not true in general, and counterexamples are easy to construct. However,
it is often true of the triangular matrices from pivoted LU or QR
decompositions. It is shown that this fact is closely connected with the
rank-revealing character of these decompositions. 
(Also cross-referenced as UMIACS-TR-95-91)
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/759},
	author = {Stewart, G.W.}
}
@article {17742,
	title = {Two Algorithms for the The Efficient Computation of Truncated Pivoted QR Approximations to a Sparse Matrix},
	volume = {UMIACS-TR-98-12},
	year = {1998},
	month = {1998/10/15/},
	institution = {Instititue for Advanced Computer Studies, Univ of Maryland, College Park},
	abstract = {In this note we propose two algorithms to compute truncated pivoted QRapproximations to a sparse matrix.  One is based on the Gram--Schmidt
algorithm, and the other on Householder triangularization.  Both
algorithms leave the original matrix unchanged, and the only
additional storage requirements are arrays to contain the
factorization itself.  Thus, the algorithms are particularly suited to
determining low-rank approximations to a sparse matrix.
(Also cross-referenced as UMIACS-TR-98-12)
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/941},
	author = {Stewart, G.W.}
}
@article {17743,
	title = {Two Simple Residual Bounds for the Eigenvalues of Hermitian Matrices},
	volume = {UMIACS-TR-89-123},
	year = {1998},
	month = {1998/10/15/},
	institution = {Instititue for Advanced Computer Studies, Univ of Maryland, College Park},
	abstract = {Let $A$ be Hermitian and let the orthonormal columns of $X$ span anapproximate invariant subspace of $X$.  Then the residual $R = AX-XM$
$(M=X\ctp AX)$ will be small.  The theorems of this paper bound the
distance of the spectrum of $M$ from the spectrum of $A$ in terms of
appropriate norms of $R$.
Appeared in SIAM J. Mat. Anal. Appl. 12 (1991) 205--208.
(Also cross-referenced as UMIACS-TR-89-123)
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/545},
	author = {Stewart, G.W.}
}
@article {16175,
	title = {Understanding Transportation Management Systems Performance with a Simulation-Based Learning Environment},
	journal = {Technical Reports of the Computer Science Department},
	year = {1998},
	month = {1998/12/05/},
	abstract = {We have developed a simulation-based learning environment to provide systemdesigners and operators with an appreciation of the impact of incidents on 
traffic delay.  We used an application framework developed at the University 
of Maryland for constructing simulation-based learning environments called 
SimPLE (Simulated Processes in a Learning Environment).  Environments 
developed with SimPLE use dynamic simulations and visualizations to represent 
realistic time-dependent behavior and are coupled with guidance material and 
other software aids that facilitate learning.  The simulation allows learners 
to close freeway lanes and divert traffic to an arterial road.  Users can see 
the effect of the detour on freeway and arterial delay.  Users can then
adjust signal timing interactively on a time space diagram and watch the 
effect of their adjustment on green band changes and on arterial delays and 
total delays.
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/500},
	author = {Plaisant, Catherine and Tarnoff,Phil and Saraf,Aditya and Rose,Anne}
}
@article {16024,
	title = {Updating Discourse Context with Active Logic},
	volume = {UMIACS-TR-96-62},
	year = {1998},
	month = {1998/10/15/},
	institution = {Instititue for Advanced Computer Studies, Univ of Maryland, College Park},
	abstract = {In this paper we present our implementation of a system of active logicthat processes natural language discourses. We focus on problems that
involve presupposition and the associated well-known problems of the
projection of presupposition. We discuss Heim{\textquoteright}s largely successful theory
of presupposition and point out certain limitations. We then use these
observations to build our discourse processor based on active logic. Our
main contributions are the handling of problems that go beyond the scope
of Heim{\textquoteright}s theory , especially discourses the involve cancellation of
presupposition. Ongoing work suggests that conversational implicature and
the cancellation of implicature can also be treated by our methods. Key
words: presupposition, discourse, con text, accommodation, active logic,
implicature. 
(Also cross-referenced as UMIACS-TR-96-62)
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu//handle/1903/842},
	author = {Gurney,John and Purang,Khemdut and Perlis, Don}
}
@article {16177,
	title = {User Interface Reengineering: A Diagnostic Approach},
	journal = {Technical Reports of the Computer Science Department},
	year = {1998},
	month = {1998/10/15/},
	abstract = {User interface technology has advanced rapidly in recent years.Incorporating new developments in existing systems could result in
substantial improvements in usability, thereby improving performance and
user satisfaction, while shortening training an d reducing error rates. 
Our focus is on low-effort high-payoff improvements to aspects such as
data display and entry, consistency, messages, documentation, and system
access.  This paper provides guidelines for managers and designers
responsible for use r interface reengineering, based on the experience we
gained from six projects, and compiles our observations, recommendations
and outcomes. 
(Also cross-referenced as CAR-TR-767)
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/430},
	author = {Vanniamparampil,Ajit J and Shneiderman, Ben and Plaisant, Catherine and Rose,Anne}
}
@article {17495,
	title = {Visual User Interfaces for Information Exploration},
	journal = {Technical Reports of the Computer Science Department},
	year = {1998},
	month = {1998/10/15/},
	abstract = {The next generation of database management, directory browsing,information retrieval, hypermedia, scientific data management, and library
systems can enable convenient exploration of growing information spaces by
a wider range of users.  User interface designers can provide more
powerful search techniques, more comprehensible query facilities, better
presentation methods, and smoother integration of technology with task. 
This paper offers novel graphical and direct manipulation approaches to
query formulation and information presentation/manipulation.  These
approaches include a graphical approach to restricted boolean query
formulation based on generalization/aggregation hierarchies, a filter/flow
metaphor for complete boolean expressions, dynamic query methods with
continuous visual presentation of results as the query is changed
(possibly employing parallel computation), and color-coded 2-dimensional
space-filling tree-maps that present multiple-level hierarchies in a
single display (hundreds of directories and more than a thousand files can
be seen at once). 
(Also cross-referenced as CAR-TR-577)
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/373},
	author = {Shneiderman, Ben}
}
@article {17688,
	title = {An Iterative Method for Solving Linear Inequalities},
	volume = {CS-TR-1833},
	year = {1995},
	month = {1995/02/06/},
	institution = {Department of Computer Science, University of Maryland, College Park},
	abstract = {This paper describes and analyzes a method for finding nontrivialsolutions of the inequality $Ax \geq 0$, where $A$ is an $m \times n$
matrix of rank $n$.  The method is based on the observation that a
certain function $f$ has a unique minimum if and only if the
inequality {\it fails to have} a nontrivial solution.  Moreover, if
there is a solution, an attempt to minimize $f$ will produce a
sequence that will diverge in a direction that converges to a
solution of the inequality.  The technique can also be used to solve
inhomogeneous inequalities and hence linear programming problems,
although no claims are made about competitiveness with existing
methods.
},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/355},
	author = {Stewart, G.W.}
}
@article {15002,
	title = {Optimal Architectures for Multidimensional Transforms},
	volume = {ISR-TR-1988-39},
	year = {1988},
	month = {1988///},
	institution = {Institute for Systems Research, University of Maryland, College Park},
	abstract = {Multidimensional transforms have widespread applications in computer vision, pattern analysis and image processing. The only existing optimal architecture for computing multidimensional DFT on data of size n = Nd requires very large rotator units of area O(n^2) and pipeline-time O(log n). In this paper we propose a family of optimal architectures with areatime trade-offs for computing multidimensional transforms. The large rotator unit is replaced by a combination of a small rotator unit, a transpose unit and a block rotator unit. The combination has an area of O(N^(d+2a)) and a pipeline time of O(N^(d/2-a)log n), for 0 < a < d/2. We apply this scheme to design optimal architectures for two-dimensional DFT, DHT and DCT. The computation is made efficient by mapping each of the one-dimensional transforms involved into two dimensions.},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/4770},
	author = {Chakrabarti,Chaitali and JaJa, Joseph F.}
}
@article {16809,
	title = {On Cost-effectiveness of a Semijoin in Distributed Query Processing.},
	volume = {ISR-TR-1987-38},
	year = {1987},
	month = {1987///},
	institution = {Institute for Systems Research, University of Maryland, College Park},
	abstract = {The cost-effective reduction of relations by semijoins is the basis of the heuristic approach to distributed query processing. The cost-effectiveness of a semijoin was simply determined in the literature assuming that the local processing cost is negligible compared to the data transmission cost in distributed query processing. However, recently questions have been raised about the validity of the assumption, and some experimental works revealed that the local processing cost is also significant in distributed query processing. In this paper, we are concerned with the cost-effectiveness of a semijoin considering the local processing cost as well as the data transmission cost. To measure the effectiveness of a semijoin in terms of the local processing cost, we introduce the join sequence in which the relations are joined at the result site to answer the query. A dynamic programming algorithm is developed to generate the optimal join sequence for a given query. A simple heuristic algorithm is also developed to generate a join sequence for a given query.},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu//handle/1903/4547},
	author = {Kang,Hyunmo and Roussopoulos, Nick}
}
@article {16811,
	title = {Meta-Data Management.},
	volume = {ISR-TR-1987-31},
	year = {1987},
	month = {1987///},
	institution = {Institute for Systems Research, University of Maryland, College Park},
	abstract = {A database system should support a rich variety of meta-data describing and controlling the management and use of data. Few present database systems provide even rudimentary integrated meta-data management facilities.},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu//handle/1903/4540},
	author = {Mark,Leo and Roussopoulos, Nick}
}
@article {16808,
	title = {Using 2-way Semijoins in Distributed Query Processing.},
	volume = {ISR-TR-1987-35},
	year = {1987},
	month = {1987///},
	institution = {Institute for Systems Research, University of Maryland, College Park},
	abstract = {In distributed query processing, the semijoin has been used as an effective operator in reducing relations referenced in the query to reduce the total amount of data transmission. In this paper, we propose a new relational algebra operator, 2-way semijoin, which is an extended version of the semijoin, for more cost- effective distributed query processing. The 2-way semijoin is compared to the semijoin in terms of the reduction power and the propagation of reduction effects. We show that the 2-way semijoin has more reduction power than the semijoin and that the propagation of reduction effects by the 2-way semijoin is further than by the semijoin.},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu//handle/1903/4544},
	author = {Kang,Hyunmo and Roussopoulos, Nick}
}
@article {14928,
	title = {A High-Level Interactive System for Designing VLSI Signal Processors},
	volume = {ISR-TR-1985-7},
	year = {1985},
	month = {1985///},
	institution = {Institute for Systems Research, University of Maryland, College Park},
	abstract = {This paper describes a high-level interactive system that can be used to generate VLSI designs for various operations in signal processing such as filtering, convolution and computing the discrete Fourier transform. The overall process is fully automated and requires that the user specifies only a few parameters such as operation, precision, size and architecture type. The built-in architectures are new digit-on-line bit-serial architectures that are based on recently derived fast algorithms for the above operations. The basic elements are compact and have a very small gate delay. We feel that our system will offer a flexible and easy to use tool that can produce practical designs which are easy to test, efficient and fast.},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/4383},
	author = {Owens,R. M. and JaJa, Joseph F.}
}
@article {14929,
	title = {A New Approach for Compiling Boolean Functions},
	volume = {ISR; TR 1985-39},
	year = {1985},
	month = {1985///},
	institution = {Institute for Systems Research, University of Maryland, College Park},
	abstract = {We propose a new approach for laying out Boolean functions which is based on extracting the symmetries of a given set of functions and applying optimization procedures especially tailored to exploit these symmetries. This paper establishes a rigorous foundation for this approach and shows that it will outperform existing methods for many classes of the functions. The different components of a newly developed system, SYMBL, will be briefly described.},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/4412},
	author = {JaJa, Joseph F. and Wu,S. M.}
}
@article {15046,
	title = {VLSI Architectures Based on the Small N Algorithms},
	volume = {ISR-TR-1985-8},
	year = {1985},
	month = {1985///},
	institution = {Institute for Systems Research, University of Maryland, College Park},
	abstract = {Digital convolution and the discrete Fourier transform are basic operations whose computational requirements are of great importance in many applications. In this paper, we propose new types of VLSI architectures which are shown to be quite suitable to handle these operations. These architectures will result in fully pipelined bit-serial arrays which require no control units. Some preliminary implementations indicate a substantial speed-up gain over other existing designs.},
	keywords = {Technical Report},
	url = {http://drum.lib.umd.edu/handle/1903/4384},
	author = {JaJa, Joseph F. and Owens,R. M.}
}
