2004 Technical Reports | SCS | UW
[Please remove <h1>]
| CS-2004-01 |
| Title |
A Study on Skin Optics |
| Authors |
Aravind Krishnaswamy and Gladimir V. G. Baranoski |
| Abstract |
Despite the notable progress in physically-based rendering, there is still a long way to go before we can automatically generate predictable images of biological materials. In this report, we address an open problem in this area, namely the spectral simulation of light interaction with human skin. Initially, we present an overview of fundamental skin optics concepts which is followed by the description of a novel biophysically-based model that accounts for all components of light propagation in skin tissues, namely surface reflectance, subsurface reflectance and transmittance, and the biological mechanisms of light absorption by pigments in these tissues. The model is controlled by biologically meaningful parameters, and its formulation, based on standard Monte Carlo techniques, enables its straightforward incorporation into realistic image synthesis frameworks. Besides its iophysically-based nature,the key difference between the proposed model and the existing skin models is its comprehensiveness, i.e., it computes both spectral (reflectance and transmittance) and scattering (bidirectional surface-scattering distribution function) quantities for skin specimens. In order to assess the predictability of our simulations, we evaluate their accuracy by comparing results from the model with actual skin measured data. We also present computer generated images to illustrate the flexibility of the proposed model with respect to variations in the biological input data, and its applicability not only in the predictive image synthesis of different skin tones, but also in the spectral
simulation of medical conditions. |
| Date |
January 2004
|
| Comments |
|
| Report |
Latex |
PostScript |
Adobe PDF |
Compressed PostScript
|
| CS-2004-06 |
| Title |
Finding Frequent Items in Sliding Windows with Multinomially-Distributed
Item Frequencies |
| Authors |
Lukasz Golab, David DeHaan, Alejandro Lopez-Ortiz, and Erik D. Demaine |
| Abstract |
This paper presents algorithms for identifying frequent items within a
sliding window in the
data stream computational model, assuming that item types conform to a
multinomial distribution.
We begin by introducing the drifting data distribution model, which assumes
that item type
frequencies approximately follow the same distribution in every instance of
the sliding window,
but gradual changes in the parameters of the distribution are allowed across
the lifetime of the
stream. Under this model and given the assumption of
multinomially-distributed item frequencies,
we show how to determine the true frequencies of items using space that is
only a fraction of the
sliding window size. We then use these approximate frequencies to identify
items that exceed a given
frequency threshold. Our algorithms are shown to outperform classical
inference based on random
sampling from the sliding window.
|
| Date |
January 2004
|
| Comments |
*Note that this is updated from CS-2003-06 |
| Report |
Latex |
PostScript |
Adobe PDF |
Compressed PostScript
|
| CS-2004-08 |
| Title |
Mobility Impact on Data
Service Performance in GPRS Systems |
| Authors |
Majid Ghaderi and Raouf
Boutaba |
| Abstract |
In this paper we describe
an analytical approach to derive the packet delay distribution in a cell
of a wireless network operating based on the general packet radio service
(GPRS) standard. Based on that, the average packet delay and packet loss
probability are also computed. Our approach is based on a decomposition
of system behavior into short-term and long-term behaviors to simplify
the analytical modeling thanks to the quasi-stationary behavior of the
data packet queueing process. In addition to the effect of voice call
handoffs, the impact of packet forwarding and dedicated data channels
on data service performance is also taken into consideration. The performance
estimates produced by the analytical approach are compared with those
generated by simulation experiments which confirms the relative accuracy
of the analytical approach.
|
| Date |
January 2004 |
| Comments |
|
| Report |
Latex |
PostScript |
Adobe
PDF |
Compressed
PostScript
|
| CS-2004-25 |
| Title |
A Rewriting Algorithm for Multi-Block Aggregation
Queries and Views using Prerequisites and Compensations |
| Authors |
David DeHaan |
| Abstract |
This paper presents an extension to previously proposed bottom-up
compensation-based algorithms for calculating the usability of a view to
answer a database query, where both query and view definition are
multi-block SQL queries containing aggregation. The goal of our extension
is to increase the recall of previous algorithms. The main idea of
approach is to improve recall by deferring certain view pruning decisions
through the introduction of pseudo-algebraic operators that we call
prerequisites. We present a set of transformation rules for manipulating
query expressions containing prerequisite operators, as well as a modified
matching algorithm that utilizes the prerequisite operators and associated
transforms. Finally, we discuss the effect that prerequisite operators
have on efficiency of the algorithm, and propose a combination of
heuristics and normal forms to limit the introduction of prerequisites to
scenarios in which they are likely to be helpful. |
| Date |
May 2004
|
| Comments |
|
| Report |
Latex |
PostScript |
Adobe PDF |
Compressed PostScript
|
| CS-2004-30 |
| Title |
Theory of Deterministic
Trace-Assertion Specifications
|
| Authors |
Janusz Brzozowski
School of Computer Science, University of Waterloo, Waterloo, ON, Canada N2L
3G1
Helmut Jurgensen
Department of Computer Science, The University of Western Ontario, London,
ON, Canada N6A 5B7
and
Institut f. Informatik, Univers. Potsdam, August-Bebel-Str. 89, 14482 Potsdam,
Germany |
| Abstract |
Abstract. A software module is an abstraction of a program: it has a well defined functionality, operations by which the environment accesses the program, and outputs. Traces are sequences of operations. Trace assertions constitute a particular formalism for abstract speciation of software modules. Certain traces are identified as canonical, and all traces are grouped in equivalence classes, each of which is represented by a unique canonical trace. Trace equivalencecaptures the observational indistinguishability of traces. A rewriting systemtransforms any trace to its canonical equivalent
A module can often be conveniently described by a (finite or infinite) automaton. In this paper we consider only deterministic connected automata. We show that any such automaton can be specified by canonical traces and trace equivalence; conversely, any set of canonical traces together with a trace equivalence uniquely defines an automaton. For each state of an automaton, we select an arbitrary trace leading to that state as its canonical trace. Constructing trace equivalence amounts to finding a set of generators for state-equivalence, where two traces are state-equivalent if they lead to the same state. We present a simple algorithm for finding such a set of generators. Directly from these generators, we derive a rewriting system which yields a deterministic algorithm for transforming any trace to its canonical representative. This system is always confluent, and it is Noetherian (has only finite derivations) if and only if the set of canonical traces is prefix-continuous (a set is prefix-continuous if whenever a word w and a prefix u of w are in the set, then all the prefixes of w longer than u are also in the set). Each prefix continuous set corresponds to a spanning forest of the automaton and vice versa. We apply our algorithms to specify several commonly used modules.
|
| Date |
May 2004 |
| Comments |
This report was posted in May 2004, and revised in August 2004. Part of the material from the May version has appeared in [5].
|
| Report |
Latex |
PostScript |
Adobe PDF |
Compressed PostScript
|
| CS-2004-35 |
| Title |
Enabling Chaotic Ubiquitous Computing
|
| Authors |
O. Andrei Dragoi and James P. Black
|
| Abstract |
Today, ubiquitous computing is possible only in handcrafted environments, and not across administrative and technological domains. For this to happen, a middleware "ecology" will need to emerge, so that users can exploit a chaotic environment of competing communication and service providers, and overlapping administrative authorities. Although key elements of the ecology exist today, simple exploitation of unfamiliar (or familiar) ubiquitous environments remains a challenge for users. They need simple tools that open the way to this increasingly rich ecology of devices, services, and information. This paper describes how such tools can be provided through a software abstraction called a frame.
Keywords: ubiquitous computing, software abstractions, services, service access, middleware, web proxy
|
| Date |
August 2004
|
| Comments |
|
| Report |
Latex |
PostScript |
Adobe PDF |
Compressed PostScript
|
| CS-2004-36 |
| Title |
Discovering Services is not Enough
|
| Authors |
O. Andrei Dragoi and James P. Black
|
| Abstract |
In the future, mobile users will find themselves in unfamiliar and "chaotic" environments with multiple providers of electronic devices or services, and competing internet-service providers. Users need to discover what services are available, how to apply them to the task at hand, and how to acquire the appropriate rights to use them successfully. The key contribution of this paper is linking service discovery with the acquisition of role-based credentials for services, and showing how the combination can be exploited easily and effectively by users of ubiquitous-computing environments. Our design facilitates flexible authorisation and access control, requires no special-purpose client devices or software, and enables an open market where all participants have a niche that they perceive as bringing value to them. The design has been refined, implemented, and validated as part of a larger prototype implementation, parts of which are described. Middleware, running in a web proxy, transforms web objects by adding specific software tools for the user to discover and invoke the currently relevant services.
Keywords: ubiquitous computing, role-based access control, service discovery, middleware, web proxy
|
| Date |
August 2004
|
| Comments |
|
| Report |
Latex |
PostScript |
Adobe PDF |
Compressed PostScript
|
| CS-2004-37 |
| Title |
A Graphical XQuery Language Using Nested Windows
|
| Authors |
Zheng Qin, Benjamin Bin Yao, Yingbin Liu, and Michael McCool
|
| Abstract |
A graphical XQuery-based language using nested windows,
GXQL, is presented. Definitions of both syntax and semantics are
provided.
Expressions in GXQL can be directly translated into corresponding
XQuery expressions. GXQL supports for, let, where, order by and
return clauses (FLWOR expressions) and also supports predicates and
quantifiers. This graphical language provides a powerful and
user-friendly environment for non-technical users to perform queries. |
| Date |
August 2004
|
| Comments |
|
| Report |
Latex |
PostScript |
Adobe PDF |
Compressed Post Script
|
| CS-2004-45 |
| Title |
A Data Locating Mechanism for Distributed XML Data over P2P Networks
Technical report CS-2004-45 |
| Authors |
Qiang Wang and M. Tamer Ozsu , University of Waterloo |
| Abstract |
Many emerging applications that use XML are distributed, usually over the Internet or over large Peer-to-Peer (P2P) networks. A fundamental problem for distributed XML query processing in these systems is how to locate the data relevant to the queries so that only useful data are involved in the query evaluation. In this paper, we address this problem within the context of structured P2P networks, and propose a novel data locating mechanism for query shipping systems. Our approach follows the multi-hop style of the structured P2P file sharing systems, but is quite different in that we encode the hierarchical information of the XML data into the overlay network, so that routing keys can be hierarchical XML path expressions. Furthermore, our data locating mechanism does not employ any centralized catalogs. To avoid flooding with XML queries, we use a technique that propagates queries within a limited sub-network to improve the performance. We report comprehensive experiments to demonstrate the scalability and effectiveness of the data locating mechanism. |
| Date |
September 2004
|
| Comments |
|
| Report |
Latex |
PostScript |
Adobe PDF |
Compressed Post Script
|
| CS-2004-47 |
| Title |
Similarity Search in Metric Spaces |
| Authors |
Yuhui Wen |
| Abstract |
Similarity search refers to any searching problem which retrieves objects from a set that are close to a given query object as reflected by some similarity criterion. It has a vast number of applications in many branches of computer science, from pattern recognition to textual and multimedia information retrieval.
In this thesis, we examine algorithms designed for similarity search over arbitrary metric spaces rather than restricting ourselves to vector spaces. The contributions in this paper include the following:
First, after defining pivot sharing and pivot localization, we prove probabilistically that pivot sharing level should be increased for scattered data while pivot localization level should be increased for clustered data. This conclusion is supported by extensive experiments. Moreover, we proposed two new algorithms, RLAESA and NGH-tree. RLAESA, using high pivot sharing level and low pivot localization level, outperforms the fastest algorithm in the same category, MVP-tree. NGH-tree is used as a framework to show the effect of increasing pivot sharing level on search efficiency. It provides a way to improve the search efficiency in almost all algorithms. The experiments with RLAESA and NGH-tree not only show their performance, but also support the first conclusion we mentioned above.
Second, we analyzed the issue of disk I/O on similarity search and proposed a new algorithm SLAESA to improve the search efficiency by switching random I/O access to sequential I/O access. |
| Date |
September 2004
|
| Comments |
|
| Report |
Latex |
PostScript |
Adobe PDF |
Compressed Post Script
|
| CS-2004-58 |
| Title |
BlossomTree: Evaluating XPaths in FLWOR Expressions |
| Authors |
Ning Zhang (Waterloo), Shishir K. Agrawal (IIT, Bombay), and M. Tamer Ozsu (Waterloo) |
| Abstract |
Efficient evaluation of path expressions has been studied extensively. However, evaluating more complex FLWOR expressions that contain multiple path expressions has not been well studied. In this paper, we propose a novel pattern matching approach, called Blossom Tree, to evaluate a FLWOR expression that contains correlated path expressions. \BlossomTree is a formalism to capture the semantics of the path expressions and their correlations. These correlations include variable referencing, structural relationship, value-based relationship, or a mixture of structural and value-based relationship. We propose a general algebraic framework (abstract data types and logical operators) to evaluate BlossomTree pattern matching that facilitates efficient evaluation and experimentation. We design efficient data structures and algorithms to implement the abstract data types and logical operators. Our experimental studies demonstrate that the BlossomTree pattern matching approach can generate highly efficient query plans
|
| Date |
December 2004
|
| Comments |
|
| Report |
Latex |
PostScript |
Adobe PDF |
|
| CS-2004-60 |
| Title |
Stochastic Admission Control for Quality of Service in Wireless Packet Networks |
| Authors |
Majid Ghadei and Raouf Boutaba (University of Waterloo), Gary W. Kenward (Nortel Networks) |
| Abstract |
Call admission control is a key element for providing quality of service (QoS) in mobile wireless networks. Traditional admission control schemes only address call-level QoS guarantee because of the underlying circuit-based network architecture. In contrast, emerging wireless technologies such as 3G and 4G tend to be packet-switched rather than circuit-switched because the packet-based architecture allows better sharing of the scarce wireless resources. This paper introduces a novel distributed call admission control scheme called PFG, which maximizes the wireless channel utilization subject to a redetermined bound on the call dropping and packet loss probabilities for variable-bit-rate traffic in a packet-switched wireless cellular network. In particular, we show that in wireless packet networks, the undesired event of dropping an ongoing call can be completely eliminated without sacrificing the bandwidth utilization. The proposed control algorithm is stochastic and dynamic, hence it is able to adapt to a wide range of traffic fluctuations and mobility patterns. Extensive simulation results show that our scheme satisfies the hard constraint on call dropping and packet loss probabilities while maintaining a high bandwidth utilization.
|
| Date |
November 2004
|
| Comments |
|
| Report |
Latex |
PostScript |
Adobe PDF |
Compressed Post Script |
| CS-2004-61 |
| Title |
Mobile Effective Bandwidth and Its Application to Admission Control in Cellular Packet Networks |
| Authors |
Majid Ghaderi and Raouf Boutaba |
| Abstract |
Admission control is a key element for providing quality of service in a mobile cellular network. The problem of admission control in packet-switched cellular networks is more challenging compared to their circuit-switched counterparts due to packet-level network interactions. Although packet-based architectures allow for more efficient sharing of scarce radio resources, admission of new connections into the network is more complicated. The concept known as effective bandwidth is a simple yet efficient approach for admission control and resource allocation in wireline networks. This paper introduces the notion of mobile effective bandwidth which extends the classical effective bandwidth concept introduced for wireline networks to cellular packet networks. The main idea is to consider the spacial multiplexing due to user mobility in computing an effective bandwidth for variable-bit-rate connections. Based on this concept, an admission control algorithm is proposed which guarantees a prespecified packet loss probability while achieving zero connection dropping probability. This is a sharp diversion from the existing admission control schemes which can not completely eliminate connection dropping because of the underlying circuit-based architecture.
|
| Date |
December 2004
|
| Comments |
|
| Report |
Latex |
PostScript |
Adobe PDF |
Compressed Post Script |