|
Computer Science Papers and Proposals
|
| 2001 | 2002 | 2003 | 2004 | 2005 | 2006 | 2007 | 2008 |
| 2007-2008 Computer Science Papers and Proposals |
Real-time Photon Mapping
Derek Alexander
ABSTRACT: Ray tracing is a method of digital image synthesis used to create realistic images. The Cell Broadband Engine is a modern processor with enough processing power to run ray tracing in real time. Implementing fast ray tracing for the Cell Broadband Engine (CBE) is more of an exercise in implementing normal ray tracing optimizations than optimizations specifically for the CBE. Specifically, creating a bounding volume hierarchy (BVH) dramatically improves performance of the
system. Re-working the ray-triangle intersection method to use single instruction multiple data (SIMD) instructions also improves performance, but not as dramatically as the BVH.
|
Database Replication Techniques
Adriano Caloiaro
ABSTRACT: Many large database systems significantly suffer from replication lag due to the
database management systems' inability to efficiently propagate transactions to a large number of replicas (slave servers). This replication lag can result in inaccurate, irrelevant, or simply aged data when queries are executed on lagged servers. Replication lag is commonly the results of lazy replication. The idea of lazy replication is that transactions are propagated asynchronously to other nodes after a transaction has been committed. What this essentially means is that one or more slaves in a cluster may or may not have the most recent version of missioncritical data. On the other hand there exists eager replication. Eager replication utilizes an atomic propagation technique which means that a
transaction must be applied to all or none of the replicas to ensure that data remains consistent after every transaction. The problem with eager replication is that it provides excellent consistency but poor performance. The purpose of this research is to examine the various components which make up a replication protocol and test different replication methods in order to find or devise the most efficient and reliable replication technique.
|
Simulation of Graph Layout Algorithms for Sensor Networks
Chris Hogg
ABSTRACT:
The purpose of this project is to determine and study a distributed algorithm that allows the nodes to locate themselves in relation to all other nodes of a sensor network in 3-dimensional space. The reason behind the project is that knowing relative locations would often aid in performance of the primary function of
the network. However since sensor networks are often setup in a randomized manner we need to test the algorithm for what scenarios are prone to yielding inaccurate results. The algorithm used to determine the layout was the 3D Graph Layout, 3DGL, algorithm, in which the nodes attempt to find their locations
through power iteration on a matrix based off adjacencies. From there a stress minimization procedure is used to get more accurate results. What this produces is a network layout that is theoretically correct up to global translations and rotations. However the solution was not always correct because of the phenomenon
known as a fold over.
|
Agent-based Simulation of Civil Unrest
John Palmer
ABSTRACT: Though the exact functioning of human beings in a specific political or
socioeconomic situation is far too complex to model directly, some shortcuts may be taken to achieve a fairly accurate simulation of the idea of civil unrest in general, even if recreating exact situations remains impossible for the time being. This paper explores the use of autonomous agents to represent citizens that may become dissatisfied with their current situation and attempt to show dissent publicly, as opposed by other agents
representing to keep public order by arresting those dissenting agents. Civilian agents decide whether or not to show dissent based on a combination of internal states and external situation, while suppressing agents coordinate efforts to quell rebellion where necessary.
|
A Neural Network Cache Replacement Implementation in the Squid Cache
Sam Romano
ABSTRACT: The Web has become the single most important source of information and communication for the world. Proxy servers utilize the process of caching, storing data temporarily to decrease network bandwidth, reduce user (client) perceived lag, and reduce loads on the origin servers.There are several decisions that must be made such as cache placement and replacement. Many proposals are covered in the literature regarding these web cache decision processes. Our main focus will be the cache replacement problem, the process of evicting objects in the cache to make room for new objects, implemented in an existing piece of software, the Squid cache proxy. There are many replacement strategies to consider when designing a proxy server. The most commonly known cache replacement strategies are Least Frequently Used (LFU) and Least Recently Used (LRU). Until 2003, there had been no survey of known web cache replacement strategies. However, Podlipnig et al. has done well to not only list well-known strategies, but also categorize the strategies into five groups: Frequency Based, Recency Based, Frequency/Recency Based, Function-Based, and Randomized.
As we will demonstrate later in this paper, many strategies suffer from being able to adapt dynamically to ever changing levels of request stream characteristics such as temporal and spatial locality. Temporal locality is the measure of how likely an object is to appear again in a request stream after being requested within a time span, while spatial locality is the likelihood that an object will appear again based on how often it%u2019s been seen before.
Neural networks were recently introduced as a novel cache replacement strategy by Jake Cobb and Hala ElAarag and named Neural Network Proxy Cache Replacement (NNPCR). While consistently outperforming LRU and LFU, it is unknown how well NNPCR fairs against more advanced, equivalent strategies. In fact, comparisons of these advanced techniques amongst 3 each other are scarce. In order to do a proper implementation of NNPCR and demonstrate that it is effective, we performed simulations to gather and access information about the cache replacement problem and following solutions.
|
Non-negative Matrix Factorization Techniques and Optimizations
Brandon Ross
ABSTRACT: In recent years, Non-Negative Matrix Factorization (NMF) has proven to be a powerful means of factoring composite data into its individual components. Originally used to decompose facial images into collections of facial features, NMF has since been applied to such diverse applications as document clustering by themes, music transcription of signal source to musical scores, and media categorization. Its strength is derived from its constraints on the data, factoring an original matrix comprised of only non-negative data into two matrices also comprised of only non-negative data. By imposing the restriction that any update algorithm maintain non-negativity of all components, the two derived matrices result in one being a collection of basis vectors and the other being mixing coefficients. In this paper, we will examine and compare the various algorithms published in the literature with the intention of optimizing either the performance or precision of the obtained solutions. As we continue to review the literature, we intend to improve on the present state-of-
the-art methods presently in use by exploring a mixture of models, such as estimating the initial basis functions to improve the rate of convergence or possibly find better solutions. As the NMF is non-convex, a global minimum is not guaranteed when iteratively searching for a solution. We will therefore also explore the possibility of augmenting the algorithm to include evolutionary
strategies to converge to better solutions. Finally, if time permits, we hope to implement the various algorithms on parallel architectures.
|
Stream Localization Aware Cooperation in Bittorrent Networks to Minimize Delay and Jitter in Video-on-Demand Systems
Sean Salmon
ABSTRACT: Video-on-Demand is, just as its name suggests, in high demand. No matter what medium is being discussed, consumers desire the ability to choose what they watch and when. Comcast claims that its viewers watched more than 1.4 billion On-Demand videos in 2005, which was nearly a 150% jump over the previous year. YouTube, the poster-child for online on-demand video, reportedly serves over 100 million videos a day. Due to the nature of VoD, content providers aren't able to broadcast their video the way they traditionally have; the on-demand nature dictates that each user needs a different part of the content stream at a different time. This leads to a huge surge in the bandwidth needed to address
subscribers' needs, as video is one of the most bandwidth-intensive applications for a network, and with VoD it is used on a per-subscriber rate.
This paper will discuss potential solutions to the colossal needs of VoD by using a modified version of the popular file-sharing protocol BitTorrent. It proposes using self-adjusting peer groups, called alliances, to cluster peers together that need similar parts of a video. In doing so, it ensure that peers receive the necessary video segments in a timely manner, and that
bandwidth utilization is optimized. The performance of this paper's strategy will then be compared to some of the other popular strategies, using the objective metrics of delay, delay jitter, and uplink utilization. These comparisons will be performed on a simulator created specifically for this simulation.
|
|
