| CS-2003-01 | ||||
|---|---|---|---|---|
| Title | Processing Sliding Window Multi-Joins in Continuous Queries | |||
| Authors | Lukasz Golab and M. Tamer Ozsu | |||
| Abstract | We study sliding window multi-join processing in continuous queries over data streams. Several algorithms are reported for performing continuous, incremental joins, under assumption that all the sliding windows fit in main memory. The algorithms include multi way incremental nested loop joins (NLJs) and multi-way incremental hash joins. We also propose join ordering heuristics to minimize the processing cost per unit time. We test a possible implementation of these algorithms and show that as expected, has joins are faster than NLJs for performing equi-joins, and that the overall processing cost is influenced by the strategies used to remove expired tuples from the sliding windows | |||
| Date | February 2003 | |||
| Report | Processing Sliding Window Multi-Joins in Continuous Queries (PDF) | |||
| CS-2003-04 | ||||
|---|---|---|---|---|
| Title | A Roadmap to a Medeling Language for Multi-Agent Systems Engineering | |||
| Authors | Viviane Silva, Carlos Lucena, Paulo Alencar and Donald Cowan | |||
| Abstract | In this paper we present a conceptual framework called TAO that organizes the core concepts related to multi-agent systems and assumes that agents and objects co-exist as independent and unique abstractions. We then use the TAO framework to create the multi-agent system modelling language MAS-ML, which extends UML (Unified Modelling Language). MAS-ML is defined as a conservative extension of the UML metamodel, and includes agent-related notions that are part of the TAO conceptual framework while preserving all object-related concepts, which constitute the UML metamodel. Creating a modelling language for multi-agent systems is a complex task and we should consider following a process or roadmap similar to the one that led to the development of the UML and its various sub-models and supporting facilities. | |||
| Date | February 2003 | |||
| Report | A Roadmap to a Medeling Language for Multi-Agent Systems Engineering (PDF) | |||
| CS-2003-06 | ||||
|---|---|---|---|---|
| Title | Towards Identifying Frequent Items in Sliding Windows | |||
| Authors | David DeHaan, Erik D. Demaine, Lukasz Golab, Alejandro Lopez-Ortiz and J. Ian Munro | |||
| Abstract | Queries that return a list of frequently occurring items are popular in the analysis of data streams such as real-time Internet traffic logs. While several resultsexist for computing frequent item queries using limited memory in the infinite stream model, none have been extended to the limited-memory sliding window model, which considers only the last N items that have arrived at any given time and forbids the storage of the entire window in memory. We present several algorithms for identifying frequent items in sliding windows, both under arbitrary distributions and assuming that each window conforms to a multinomial distribution. The former is a straightforward extension of existing algorithms and is shown to work well when tested on real-life TCP traffic logs. Our algorithms for the multinomial distribution are shown to outperform classical inference based on random sampling from the sliding window, but lose their accuracy as predictors of item frequencies when the underlying distribution is not multinomial. | |||
| Date | March 2003 | |||
| Report | Towards Identifying Frequent Items in Sliding Windows (PDF) | |||
| CS-2003-10 | ||||
|---|---|---|---|---|
| Title | An Efficient Bounds Consistency Algorithm for the Global Cardinality Constraint | |||
| Authors | Claude-Guy Quimper, Peter van Beek, Alejandro Lopez-Ortiz, Alexander Golynski and Sayyed Bashir Sadjad | |||
| Abstract | Previous studies have demonstrated that designing special purpose constraint propagators can significantly improve the efficiency of a constraint programming approach. In this paper we present an efficient algorithm for bounds consistency propagation of the generalized cardinality constraint "gcc". Using a variety of benchmark and random problems, we show that our bounds consistency algorithm is competitive with and can dramatically outperform existing state-of-the-art commercial implementations of constraint propagators for the gcc. We also present a new algorithm for domain consistency propagation of the gcc which improves on the worst-case performance of the best previous algorithm for problems that occur often in applications. | |||
| Date | February 2003 | |||
| Report | An Efficient Bounds Consistency Algorithm for the Global Cardinality Constraint (PS) | An Efficient Bounds Consistency Algorithm for the Global Cardinality Constraint (PDF) | ||
| CS-2003-21 | ||||
|---|---|---|---|---|
| Title | A Geometric B-Spline Over the Triangular Domain | |||
| Authors | Christopher K. Ingram | |||
| Abstract | For modelling curves, B-splines [3] are among the most versatile control schemes. However, scaling this technique to surface patches has proven to be a non-trivial endeavor. While a suitable scheme exists for rectangular patches in the form of tensor product B-splines, techniques involving the triangular domain are much less spectacular. The current cutting edge in triangular B-splines is the DMS-spline [2]. While the resulting surfaces possess high degrees of continuity, the control scheme is awkward and the evaluation is computationally expensive. A more fundamental problem is the construction bears little resemblance to the construction used for the B-Spline. This deciency leads to the central idea of the thesis; what happens if the simple blending functions found at the heart of the B-Spline construction are used over higher dimension domains? In this thesis I develop a geometric generalization of B-Spline curves over the triangular domain. This construction mimics the control point blending that occurs with uniform B-Splines. The construction preserves the simple control scheme and evaluation of B-Splines, without the immense computational requirements of DMSsplines. The result is a new patch control scheme, the G-Patch, possessing C0 continuity between adjacent patches. |
|||
| Date | June 2003 | |||
| Report | A Geometric B-Spline Over the Triangular Domain (PDF) | |||
| CS-2003-22 | ||||
|---|---|---|---|---|
| Title | Offset Surface Light Fields | |||
| Authors | Jason Ang | |||
| Abstract | For producing realistic images, reflection is an important visual effect. Reflections of the environment are important not only for highly reflective objects, such as mirrors, but also for more common objects such as brushed metals and glossy plastics. Generating these reflections accurately at real-time rates for interactive applications, however, is a difficult problem. Previous works in this area have made assumptions that sacrifice accuracy in order to preserve interactivity. I will present an algorithm that tries to handle reflection accurately in the general case for real-time rendering. The algorithm uses a database of prerendered environment maps to render both the original object itself and an additional bidirectional reflection distribution function (BRDF). The algorithm performs image-based rendering in reflection space in order to achieve accurate results. It also uses graphics processing unit (GPU) features to accelerate rendering. | |||
| Date | August 2003 | |||
| Report | Offset Surface Light Fields (PDF) | |||
| CS-2003-24 | ||||
|---|---|---|---|---|
| Title | Evaluation of DBMSs Using XBench Benchmark | |||
| Authors | M. Tamer Ozsu and Benjamin B. Yao | |||
| Abstract | XML support is being added to existing database management systems (DBMSs) and native XML systems are being developed both in industry and in academia. The individual performance characteristics of these approaches as well as the relative performance of various systems is an ongoing concern.
XBench is a family of XML benchmarks which recognizes that the XML data that DBMSs manage are quite varied and no one database schema and workload can properly capture this variety. Thus, the members of this benchmark family have been defined for capturing diverse application domains. In this report we briefly discuss the XBench XML benchmark and report on the relative performance of three commercial DBMSs: X-Hive, DB2 and SQL Server. We also describe the potential issues when storing XML documents into relational DBMSs. |
|||
| Date | August 2003 | |||
| Report | Evaluation of DBMSs Using XBench Benchmark (PDF) | |||
| CS-2003-25 | ||||
|---|---|---|---|---|
| Title | Investigations in Tree Locking for Compiled Database Applications | |||
| Authors | Heng YU and Grant Weddell | |||
| Abstract | We report on initial experiments in tree locking schemes for compiled database applications. Such applications have a repository style of architecture in which a collection of software modules or subsystems operate on a common database in terms of a predefined set of transaction types, and are very often at the core of embedded systems. Since the tree locking protocol is deadlock free, it becomes possible to decouple recovery mechanisms from concurrency control, a property that we believe is critical to the successful deployment of database technology to this new application area. Our experiments show that the performance of tree locking can compete with two phase locking for cases such asmthe above in which a great deal can be known at the time of system generation about workloads. | |||
| Date | September 2003 | |||
| Report | Investigations in Tree Locking for Compiled Database Applications (PDF) | |||
| CS-2003-26 | ||||
|---|---|---|---|---|
| Title | A Study on Atmospheric Halo Visualization | |||
| Authors | Sung Min Hong and Gladimir Baranoski | |||
| Abstract | In this report, the atmospheric halo phenomena have been explained and current trends of the halo simulation have been described. Then A ray tracer based on the Monte Carlo method has been presented and demonstrated. The comparison of the simulation results with the photos taken for the same phenomena has shown that the ray tracer gives reasonable results. This ray tracer provides a very useful tool for simulating the halo phenomena and identifying atmospheric data like proportions of ice crystals and orientations. With some enhancements of the ray tracer, which are future works, the ray tracer is expected to give physically correct realistic halo images. | |||
| Date | September 2003 | |||
| Report | A Study on Atmospheric Halo Visualization (PDF) | |||
| CS-2003-27 | ||||
|---|---|---|---|---|
| Title | Supporting Set-at-a-time Extensions for XML through DOM | |||
| Authors | Hai (Helena) Chen, Frank Tompa | |||
| Abstract | With the rapid growth of the web and e-commerce, W3C produced a new standard, XML, as a universal data representation format to facilitate information interchange and integration from heterogeneous systems. In order to process XML, documents need to be parsed and then users can access, manipulate, and retrieve the XML data easily. DOM is one of the major application programming interfaces, which provides the abstract, logical tree structure of an XML document. Though it is a very promising initiative in defining the standard interface for XML documents to access all data required by applications, significant benefit can result if some functions are extended.
In this thesis, we want to support set-at-a-time extensions for XML through DOM. Through extending some powerful functions to get summary information from different groups of related document elements, and filter, extract and transform this information as a sequence of nodes, the extended DOM can reduce the communications overhead and response time between the client and the server and therefore provide applications |
|||
| Date | September 2003 | |||
| Report | Supporting Set-at-a-time Extensions for XML through DOM (PDF) | |||
| CS-2003-28 | ||||
|---|---|---|---|---|
| Title | On the Relevance of Self-Similarity in Network Traffic Prediction | |||
| Authors | Majid Ghaderi | |||
| Abstract | Self-similarity is an important characteristic of traffic in high speed networks which can not be captured by traditional traffic models. Traffic predictors based on non-traditional long-memory models are computationally more complex than traditional predictors based on short-memory models. Even online estimation of their parameters for actual traffic traces is not trivial work. Based on the observation that the Hurst parameter of real traffic traces rarely exceeds 0.85, which means that real traffic does not exhibit strong long-range dependence, and the fact that infinite history is not possible in practice, we propose to use a simple non-model-based minimum mean square error predictor.
In this paper, we look at the problem of traffic prediction in the presence of self-similarity. We briefly describe a number of short-memory and long-memory stochastic traffic models and talk about non-model-based predictors, particularly minimum mean square error and its normalized version. Numerical results of our experimental comparison between the so-called fractional predictors and the simple minimum mean square error predictor show that this simple method can achieve accuracy within $5\%$ of the best fractional predictor while it is much simpler than any model-based predictor and is easily used in an on-line fashion. |
|||
| Date | October 2003 | |||
| Report | On the Relevance of Self-Similarity in Network Traffic Prediction (PS) | On the Relevance of Self-Similarity in Network Traffic Prediction (PDF) | Compressed PostScript: On the Relevance of Self-Similarity in Network Traffic Prediction (GZIP) |
|
| CS-2003-29 | ||||
|---|---|---|---|---|
| Title | On Indexing Sliding Windows over On-line Data Streams | |||
| Authors | Lukasz Golab,Shaveen Garg and M. Tamer Ozsu | |||
| Abstract | We consider indexing sliding windows in main memory over on-line data streams. Our proposed data structures and query semantics are based on a division of the sliding window into sub-windows. When a new sub-window fills up with newly arrived tuples, the oldest sub-window is evicted, indices are refreshed, and continuous queries are re-evaluated to reflect the new state of the window. By classifying relational operators according to their method of execution in the windowed scenario, we show that many useful operators require access to the entire window, motivating the need for two types of indices: those which provide a list of attribute values and their counts for answering set-valued queries, and those which provide direct access to tuples for answering attribute-valued queries. For the former, we evaluate the performance of linked lists, search trees, and hash tables as indexing structures, showing that the high costs of maintaining such structures over rapidly changing data are offset by the savings in query processing costs. For the latter, we propose novel ways of maintaining windowed ring indices, which we show to be much faster than conventional ring indices and more efficient than executing windowed queries without an index. | |||
| Date | September 2003 | |||
| Report | On Indexing Sliding Windows over On-line Data Streams (PDF) | |||
| CS-2003-30 | ||||
|---|---|---|---|---|
| Title | Symbolic Representation and Retrieval of Moving Object Trajectories | |||
| Authors | Lei Chen, Vincent Oria, and M. Tamer Ozsu | |||
| Abstract | Similarity-based retrieval of moving object trajectory is useful to many applications, such as GPS system, sport and surveillance video analysis. However, due to sensor failures, errors in detection techniques, or different sampling rates, noises, local shifts and scales may appear in the trajectory records. Hence, it is difficult to design a robust and fast similarity measure for similarity-based retrieval in a large database. In this paper, we propose a normalized edit distance (NED) to measure the similarity between two trajectories. Compared to Euclidean distance, Dynamic Time Warping (DTW), and Longest Common Subsequences (LCSS), NED is more robust and accurate for trajectories contain noise and local time shifting. In order to improve the retrieval efficiency, we further convert the trajectories into a symbolic representation, called movement pattern strings, which encode both the movement direction and the movement distance information of the trajectories. The distances that are computed in a symbolic space are lower bounds of the distances of original trajectory data, which guarantees that no false dismissals will be introduced using movement pattern strings to retrieve trajectories. Furthermore, we define a modified frequency distance for frequency vectors that are obtained from movement pattern strings to reduce the dimensionality of movement pattern strings and computation cost of NED. The tests that we conducted indicate that the normalized edit distance is effective and the matching techniques are efficient. | |||
| Date | September 2003 | |||
| Report | Symbolic Representation and Retrieval of Moving Object Trajectories (PDF) | |||
| CS-2003-33 | ||||
|---|---|---|---|---|
| Title | Generalized Infinite Undo and Speculative User Interfaces | |||
| Authors | Alexjandro Lopez-Ortiz | |||
| Abstract | We study the potential benefits of a computations model supporting an unlimited number of undo-like operations. We argue that, when implemented to its full generality this result s in a novel mode of human-computer interaction in which the user session is not linear in time. The model proposed is also more resilient in the presence of user or computer error. This resiliency can be exploited by a speculative user interface (SUI) which guesses user intentions. If the prediction is incorrect, the generalized infinite undo facility provides the ability to extemporaneously roll back the misprediction. We observe that this model is only now becoming a realistic possibility due to the current surplus of available CPU cycles on a modern desktop. | |||
| Date | September 2003 | |||
| Report | Generalized Infinite Undo and Speculative User Interfaces (PS) | Generalized Infinite Undo and Speculative User Interfaces (PDF) | ||
| CS-2003-34 | ||||
|---|---|---|---|---|
| Title | Exploiting Statistics of Web Traces to Improve Caching Algorithms | |||
| Authors | Alexander Golynski, Alejandro L´opez-Ortiz and Ray Sweidan | |||
| Abstract | Web caching plays an important role in reducing network traffic, user delays, and server load. One important factor in describingthe stream of requests made to a given server is the popularity oflinks between accessed pages. For example, the probability of requesting page A increases if a user makes a request to a page which contains a link to page A. Furthermore, this probability depends on the amount of time elapsed since the request was made to the page containing the link and on popularity of the link. In this project we (1) analyze web access logs and determine the frequency distribution of access and mean life expectancy of correlations, (2) propose two new cache replacement policies that use the above distribution, and (3) evaluate the effectiveness of the new policies by comparing them to widely-used algorithms such as Greedy Dual-Size (GDS) and Greedy Dual-Frequency (GDSF). | |||
| Date | October 2003 | |||
| Report | Exploiting Statistics of Web Traces to Improve Caching Algorithms (PS) | Exploiting Statistics of Web Traces to Improve Caching Algorithms (PDF) | Compressed PostScript: Exploiting Statistics of Web Traces to Improve Caching Algorithms (GZIP) |
|
| CS-2003-36 | ||||
|---|---|---|---|---|
| Title | Using Word Position in Documents for Topic Characterization | |||
| Authors | Authors: Reem K. Al-Halimi, Frank W. Tompa | |||
| Abstract | In this report we show how to use the position of words in a text for characterizing the topic of the text, and compare our method to measures that use frequency statistics that are independent of word position. We show that word position information produces words that are more suited for characterizing topics and at the same time relies on a vocabulary size that is as little as 10\%$ of the size used by the other measures. | |||
| Date | October 2003 | |||
| Report | Using Word Position in Documents for Topic Characterization (PDF) | |||
| CS-2003-39 | ||||
|---|---|---|---|---|
| Title | Enforcing Domain Consistency on the extended Global Cardinality Constraint is NP- Hard | |||
| Authors | Claude-Guy Quimper | |||
| Abstract | In a global cardinality constraint, there is a set of variables X = {x_1, ... x_n} and a set of values D. Each variable x_i is associated to a domain dom(x_i) contained in D and each value v in D is associated to a cardinality set K(v). An assignment satisfies the extended global cardinality constraint (extended-GCC) if each variable x_i is instantiated to a value in its domain dom(x_i) and if each value v in D is assigned to k variables for some k in K(v). Extended-GCC differs from normal GCC in the fact that its sets of cardinality K(v) can be any set of values. In normal GCC these cardinality sets are restricted to intervals. We prove that enforcing domain consistency on the extended-GCC is NP-hard. | |||
| Date | November 2003 | |||
| Report | Enforcing Domain Consistency on the extended Global Cardinality Constraint is NP- Hard (PS) | Enforcing Domain Consistency on the extended Global Cardinality Constraint is NP- Hard (PDF) | ||
| CS-2003-41 | ||||
|---|---|---|---|---|
| Title | Call Admission Control for Voice/Data Integration in Broadband Wireless Networks | |||
| Authors | Majid Ghaderi and Raouf Boutaba | |||
| Abstract | This paper addresses bandwidth allocation for an integrated voice/data broadband mobile wireless network. Specifically, we propose a new admission control scheme called EFGC, which is an extension of the well-known fractional guard channel scheme proposed for cellular networks supporting voice traffic. The main idea is to use two acceptance ratios, one for voice calls and the other for data calls in order to maintain the proportional service quality for voice and data traffic while guaranteeing a target handoff failure probability for voice calls. We describe two variations of the proposed scheme: EFGC-REST, a conservative approach which aims at preserving the proportional service quality by sacrificing the bandwidth utilization; and EFGC-UTIL, a greedy approach which achieves higher bandwidth utilization at the expense of increasing the handoff failure probability for voice calls. Extensive simulation results show that our schemes satisfy the hard constraints on handoff failure probability and service differentiation while maintaining a high bandwidth utilization. | |||
| Date | November 2003 | |||
| Report | Call Admission Control for Voice/Data Integration in Broadband Wireless Networks (PS) | Call Admission Control for Voice/Data Integration in Broadband Wireless Networks (PDF) | Compressed PostScript: Call Admission Control for Voice/Data Integration in Broadband Wireless Networks (GZIP) |
|
| CS-2003-45 | ||||
|---|---|---|---|---|
| Title | Revisiting the Foundations of Subsurface Scattering | |||
| Authors | Gladimir V. G. Baranoski, Aravind Krishnaswamy and Bradley Kimmel | |||
| Abstract | Despite the significant advances in rendering, we are far from being able to automatically generate realistic and predictable images of organic materials such as plant and human tissues. Creating convincing pictures of these materials is usually accomplished by carefully adjusting rendering parameters. A key issue in this context is the simulation of subsurface scattering. Current algorithmic models usually rely on scattering approximations based on the use of phase functions, notably the Henyey-Greenstein phase function and its variations, which were not derived from biophysical principles of any organic material, and whose parameters have no biological meaning. In this report, we challenge the validity of this approach for organic materials. Initially, we present an original chronology of the use of these phase functions in tissue optics simulations, which highlights the pitfalls of this approach. We then demonstrate that a significant step toward predictive subsurface scattering simulations can be given by replacing it by a more efficient and accurate data oriented approach. Our investigation is supported by comparisons involving the original measured data that motivated the application of phase functions in tissue subsurface scattering simulations. We hope that the results of our investigation will help strengthen the biophysical basis required for the predictive rendering of organic materials. | |||
| Date | December 2003 | |||
| Report | Revisiting the Foundations of Subsurface Scattering (PDF) | |||
