| 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 | |||
| Report | A Study on Skin Optics (PDF) | |||
| 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 | Finding Frequent Items in Sliding Windows with Multinomially-Distributed Item Frequencies (PDF) | |||
| 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 behaviour into short-term and long-term behaviours to simplify the analytical modeling thanks to the quasi-stationary behaviour 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 | |||
| Report | Mobility Impact on Data Service Performance in GPRS Systems (PS) | Mobility Impact on Data Service Performance in GPRS Systems (PDF) |
Compressed
PostScript: Mobility Impact on Data Service Performance in GPRS Systems (GZIP) | |
| 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 | |||
| Report | A Rewriting Algorithm for Multi-Block Aggregation Queries and Views using Prerequisites and Compensations (PDF) | |||
| CS-2004-30 | ||||
|---|---|---|---|---|
| Title | Theory of Deterministic Trace-Assertion Specifications | |||
| Authors |
Janusz
Brzozowski
Helmut
Jurgensen | |||
| 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
equivalence
captures
the
observational
indistinguishability
of
traces.
A
rewriting
system
transforms
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 | Theory of Deterministic Trace-Assertion Specifications (PS) | Theory of Deterministic Trace-Assertion Specifications (PDF) | ||
| 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 | |||
| Report | Enabling Chaotic Ubiquitous Computing (PDF) | |||
| 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 | |||
| Report | Discovering Services is not Enough (PDF) | |||
| 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 | |||
| Report | A Graphical XQuery Language Using Nested Windows (PDF) | |||
| 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 | |||
| Report | A Data Locating Mechanism for Distributed XML Data over P2P Networks (PDF) | |||
| 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 | |||
| Report | Similarity Search in Metric Spaces (PDF) | |||
| 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 | |||
| Report | BlossomTree: Evaluating XPaths in FLWOR Expressions (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 | |||
| Report | Stochastic Admission Control for Quality of Service in Wireless Packet Networks (PS) | Stochastic Admission Control for Quality of Service in Wireless Packet Networks (PDF) |
Compressed
PostScript: Stochastic Admission Control for Quality of Service in Wireless Packet Networks (GZIP) | |
| 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 | |||
| Report | Mobile Effective Bandwidth and Its Application to Admission Control in Cellular Packet Networks (PS) | Mobile Effective Bandwidth and Its Application to Admission Control in Cellular Packet Networks (PDF) |
Compressed
PostScript: Mobile Effective Bandwidth and Its Application to Admission Control in Cellular Packet Networks (GZIP) | |