University of Waterloo

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