Open Access. Powered by Scholars. Published by Universities.®

Computer Sciences Commons™

Open Access. Powered by Scholars. Published by Universities.®

Dartmouth College

Discipline
Keyword
Publication Year
Publication
Publication Type
File Type

Articles 571 - 600 of 1103

Full-Text Articles in Computer Sciences

Fast-Converging Tatonnement Algorithms For The Market Problem, R Cole, L Fleischer Aug 2007

Fast-Converging Tatonnement Algorithms For The Market Problem, R Cole, L Fleischer

Computer Science Technical Reports

Why might markets tend toward and remain near equilibrium prices? In an effort to shed light on this question from an algorithmic perspective, this paper defines and analyzes two simple tatonnement algorithms that differ from previous algorithms that have been subject to asymptotic analysis in three significant respects: the price update for a good depends only on the price, demand, and supply for that good, and on no other information; the price update for each good occurs distributively and asynchronously; the algorithms work (and the analyses hold) from an arbitrary starting point. Our algorithm introduces a new and natural update …

Go to article

Periodic Properties Of User Mobility And Access-Point Popularity, Minkyong Kim, David Kotz Aug 2007

Periodic Properties Of User Mobility And Access-Point Popularity, Minkyong Kim, David Kotz

Dartmouth Scholarship

Understanding user mobility and its effect on access points (APs) is important in designing location-aware systems and wireless networks. Although various studies of wireless networks have provided useful insights, it is hard to apply them to other situations. Here we present a general methodology for extracting mobility information from wireless network traces, and for classifying mobile users and APs. We used the Fourier transform to reveal important periods and chose the two strongest periods to serve as parameters to a classification system based on Bayes' theory. Analysis of 1-month traces shows that while a daily pattern is common among both …

Go to article

Secure Cryptographic Precomputation With Insecure Memory, Patrick P. Tsang, Sean W. Smith Jul 2007

Secure Cryptographic Precomputation With Insecure Memory, Patrick P. Tsang, Sean W. Smith

Computer Science Technical Reports

Precomputation dramatically reduces the execution latency of many cryptographic algorithms. To sustain the reduced latency over time during which these algorithms are routinely invoked, however, a pool of precomputation results must be stored and be readily available. While precomputation is an old and well-known technique, how to securely and yet efficiently store these precomputation results has largely been ignored. For instance, requiring tamper-proof memory would be too expensive, if not unrealistic, for precomputation to be cost-effective. In this paper, we propose an architecture that provides secure storage for cryptographic precomputation using only insecure memory, which may be eavesdropped or even …

Go to article

Light-Based Sample Reduction Methods For Interactive Relighting Of Scenes With Minute Geometric Scale, William B. Kerr, Fabio Pellacini Jul 2007

Light-Based Sample Reduction Methods For Interactive Relighting Of Scenes With Minute Geometric Scale, William B. Kerr, Fabio Pellacini

Computer Science Technical Reports

Rendering production-quality cinematic scenes requires high computational and temporal costs. From an artist's perspective, one must wait for several hours for feedback on even minute changes of light positions and parameters. Previous work approximates scenes so that adjustments on lights may be carried out with interactive feedback, so long as geometry and materials remain constant. We build on these methods by proposing means by which objects with high geometric complexity at the subpixel level, such as hair and foliage, can be approximated for real-time cinematic relighting. Our methods make no assumptions about the geometry or shaders in a scene, and …

Go to article

A Security Assessment Of Trusted Platform Modules, Evan R. Sparks Jun 2007

A Security Assessment Of Trusted Platform Modules, Evan R. Sparks

Dartmouth College Undergraduate Theses

Trusted Platform Modules (TPMs) are becoming ubiquitous devices included in newly released personal computers. Broadly speaking, the aim of this technology is to provide a facility for authenticating the platform on which they are running: they are able to measure attest to the authenticity of a hardware and software configuration. Designed to be cheap, commodity devices which motherboard and processor vendors can include in their products with minimal marginal cost, these devices have a good theoretical design. Unfortunately, there exist several practical constraints on the effectiveness of TPMs and the architectures which employ them which leave them open to attack. …

Go to article

Closest And Farthest-Line Voronoi Diagrams In The Plane, Mark C. Henle Jun 2007

Closest And Farthest-Line Voronoi Diagrams In The Plane, Mark C. Henle

Dartmouth College Undergraduate Theses

Voronoi diagrams are a geometric structure containing proximity information useful in efficiently answering a number of common geometric problems associated with a set of points in the plane.. They have applications in fields ranging from crystallography to biology. Diagrams of sites other than points and with different distance metrics have been studied. This paper examines the Voronoi diagram of a set of lines, which has escaped study in the computational geometry literature. The combinatorial and topological properties of the closest and farthest Voronoi diagrams are analyzed and O(n^2) and O(n log n) algorithms are presented for their computation respectively.

Go to article

When One Pipeline Is Not Enough, Thomas H. Cormen, Priya Natarajan, Elena Riccio Davidson Jun 2007

When One Pipeline Is Not Enough, Thomas H. Cormen, Priya Natarajan, Elena Riccio Davidson

Computer Science Technical Reports

Pipelines that operate on buffers often work well to mitigate the high latency inherent in interprocessor communication and in accessing data on disk. Running a single pipeline on each node works well when each pipeline stage consumes and produces data at the same rate. If a stage might consume data faster or slower than it produces data, a single pipeline becomes unwieldy. We describe how we have extended the FG programming environment to support multiple pipelines in two forms. When a node might send and receive data at different rates during interprocessor communication, we use disjoint pipelines that send and …

Go to article

A Combined Routing Method For Wireless Ad Hoc Networks, Soumendra Nanda, Zhenhui Jiang, David Kotz Jun 2007

A Combined Routing Method For Wireless Ad Hoc Networks, Soumendra Nanda, Zhenhui Jiang, David Kotz

Computer Science Technical Reports

To make ad hoc wireless networks adaptive to different mobility and traffic patterns, this paper proposes an approach to swap from one protocol to another protocol dynamically, while routing continues. By the insertion of a thin new layer, we were able to make each node in the ad hoc wireless network notify each other about the protocol swap. To ensure that routing works efficiently after the protocol swap, we initialized the destination routing protocol's data structures and reused the previous routing information to build the new routing table. We also tested our approach under different network topologies and traffic patterns …

Go to article

Exploring The Integration Of Memory Management And Trusted Computing, Nihal A. D'Cunha May 2007

Exploring The Integration Of Memory Management And Trusted Computing, Nihal A. D'Cunha

Dartmouth College Master’s Theses

This thesis addresses vulnerabilities in current Trusted Computing architecture by exploring a design for a better Trusted Platform Module (TPM); one that integrates more closely with the CPU's Memory Management Unit (MMU). We establish that software-based attacks on trusted memory can be carried out undetectably by an adversary on current TCG/TPM implementations. We demonstrate that an attacker with sufficient privileges can compromise the integrity of a TPM-protected system by modifying critical loaded code and static data after measurement has taken place. More specifically, these attacks illustrate the Time Of Check vs. Time of Use (TOCTOU) class of attacks. We propose …

Go to article

Scml: A Structural Representation For Chinese Characters, Daniel G. Peebles May 2007

Scml: A Structural Representation For Chinese Characters, Daniel G. Peebles

Dartmouth College Undergraduate Theses

Chinese characters are used daily by well over a billion people. They constitute the main writing system of China and Taiwan, form a major part of written Japanese, and are also used in South Korea. Anything more than a cursory glance at these characters will reveal a high degree of structure to them, but computing systems do not currently have a means to operate on this structure. Existing character databases and dictionaries treat them as numerical code points, and associate with them additional `hand-computed' data, such as stroke count, stroke order, and other information to aid in specific searches. Searching …

Go to article

Dumbots: Unexpected Botnets Through Networked Embedded Devices, Kwang-Hyun Baek, Sergey Bratus, Sara Sinclair May 2007

Dumbots: Unexpected Botnets Through Networked Embedded Devices, Kwang-Hyun Baek, Sergey Bratus, Sara Sinclair

Computer Science Technical Reports

Currently, work on botnets focuses primarily on PCs. However, as lightweight computing devices with embedded operating systems become more ubiquitous, they present a new and very disturbing target for botnet developers. In this paper, we present both an empirical demonstration on a widely deployed multimedia box, as well as an evaluation of the deeper potential of these dumbots.

Go to article

Lighting With Sketches, Alexander Wakefield Steinberg May 2007

Lighting With Sketches, Alexander Wakefield Steinberg

Dartmouth College Undergraduate Theses

Lighting design is a fundamental aspect of computer cinematography, where it is used to support storytelling by affecting the mood, style, and believability of a scene. Traditionally, lighting has requred the tedious adjustment of large set parameters that describe complex lighting setups, including lights positions, colors, shapes, etc. This work presents an interactive user interface that facilitates lighting workflow by using a sketching paradigm for light creation. Lights are specified by a series of strokes that define various properties of illumination such as shape of the light and position of illuminated and shadowed areass. The system will them perform a …

Go to article

Virtual Walls: Protecting Digital Privacy In Pervasive Environments, Apu Kapadia, Tristan Henderson, Jeffrey Fielding, David Kotz May 2007

Virtual Walls: Protecting Digital Privacy In Pervasive Environments, Apu Kapadia, Tristan Henderson, Jeffrey Fielding, David Kotz

Dartmouth Scholarship

As pervasive environments become more commonplace, the privacy of users is placed at an increased risk. The numerous and diverse sensors in these environments can record contextual information about users, leading to users unwittingly leaving “digital footprints.” Users must therefore be allowed to control how their digital footprints are reported to third parties. While a significant amount of prior work has focused on location privacy, location is only one specific type of footprint, and we expect most users to be incapable of specifying fine-grained policies for a multitude of footprints. In this paper we present a policy language based on …

Go to article

Experiment Planning For Protein Structure Elucidation And Site-Directed Protein Recombination, Xiaoduan Ye May 2007

Experiment Planning For Protein Structure Elucidation And Site-Directed Protein Recombination, Xiaoduan Ye

Dartmouth College Ph.D Dissertations

In order to most effectively investigate protein structure and improve protein function, it is necessary to carefully plan appropriate experiments. The combinatorial number of possible experiment plans demands effective criteria and efficient algorithms to choose the one that is in some sense optimal. This thesis addresses experiment planning challenges in two significant applications. The first part of this thesis develops an integrated computational-experimental approach for rapid discrimination of predicted protein structure models by quantifying their consistency with relatively cheap and easy experiments (cross-linking and site-directed mutagenesis followed by stability measurement). In order to obtain the most information from noisy and …

Go to article

The Quality Of Open Source Production: Zealots And Good Samaritans In The Case Of Wikipedia, Denise Anthony, Sean W. Smith, Tim Williamson Apr 2007

The Quality Of Open Source Production: Zealots And Good Samaritans In The Case Of Wikipedia, Denise Anthony, Sean W. Smith, Tim Williamson

Computer Science Technical Reports

New forms of production based in electronic technology, such as open-source and open-content production, convert private commodities (typically software) into essentially public goods. A number of studies find that, like in other collective goods, incentives for reputation and group identity motivate contributions to open source goods, thereby overcoming the social dilemma inherent in producing such goods. In this paper we examine how contributor motivations affect the quality of contributions to the open-content online encyclopedia Wikipedia. We find that quality is associated with contributor motivations, but in a surprisingly inconsistent way. Registered users' quality increases with more contributions, consistent with the …

Go to article

Protein Design By Mining And Sampling An Undirected Graphical Model Of Evolutionary Constraints, John Thomas, Naren Ramakrishnan, Chris Bailey-Kellogg Mar 2007

Protein Design By Mining And Sampling An Undirected Graphical Model Of Evolutionary Constraints, John Thomas, Naren Ramakrishnan, Chris Bailey-Kellogg

Computer Science Technical Reports

Evolutionary pressures on proteins to maintain structure and function have constrained their sequences over time and across species. The sequence record thus contains valuable information regarding the acceptable variation and covariation of amino acids in members of a protein family. When designing new members of a protein family, with an eye toward modified or improved stability or functionality, it is incumbent upon a protein engineer to uncover such constraints and design conforming sequences. This paper develops such an approach for protein design: we first mine an undirected probabilistic graphical model of a given protein family, and then use the model …

Go to article

Complete Configuration Space Analysis For Structure Determination Of Symmetric Homo-Oligomers By Nmr, Shobha Potluri Mar 2007

Complete Configuration Space Analysis For Structure Determination Of Symmetric Homo-Oligomers By Nmr, Shobha Potluri

Dartmouth College Ph.D Dissertations

Symmetric homo-oligomers (protein complexes with similar subunits arranged symmetrically) play pivotal roles in complex biological processes such as ion transport and cellular regulation. Structure determination of these complexes is necessary in order to gain valuable insights into their mechanisms. Nuclear Magnetic Resonance (NMR) spectroscopy is an experimental technique used for structural studies of such complexes. The data available for structure determination of symmetric homo-oligomers by NMR is often sparse and ambiguous in nature, raising concerns about existing heuristic approaches for structure determination. We have developed an approach that is complete in that it identifies all consistent conformations, data-driven in that …

Go to article

People-Centric Urban Sensing: Security Challenges For The New Paradigm, Peter Johnson, Apu Kapadia, David Kotz, Nikos Triandopoulos Feb 2007

People-Centric Urban Sensing: Security Challenges For The New Paradigm, Peter Johnson, Apu Kapadia, David Kotz, Nikos Triandopoulos

Computer Science Technical Reports

We study the security challenges that arise in \emph{people-centric urban sensing}, a new sensor-networking paradigm that leverages humans as part of the sensing infrastructure. Most prior work on sensor networks has focused on collecting and processing ephemeral data about the environment using a static topology and an application-aware infrastructure. People-centric urban sensing, however, involves collecting, storing, processing and fusing large volumes of data related to every-day human activities. Sensing is performed in a highly dynamic and mobile environment, and supports (among other things) pervasive computing applications that are focused on enhancing the user's experience. In such a setting, where humans …

Go to article

Workshop Report — Crawdad Workshop 2006, Jihwang Yeo, Tristan Henderson, David Kotz Jan 2007

Workshop Report — Crawdad Workshop 2006, Jihwang Yeo, Tristan Henderson, David Kotz

Dartmouth Scholarship

Wireless network researchers are seriously starved for data about how real users, applications, and devices use real networks under real network conditions. CRAWDAD, the Community Resource for Archiving Wireless Data at Dartmouth, is an NSF-funded project that is building a wireless network data archive for the research community. We host wireless data, and provide tools and documents to make it easy to collect and use wireless network data. We hope that this resource will help researchers to identify and evaluate real and interesting problems in mobile and pervasive computing. This report outlines the CRAWDAD project and summarizes the second CRAWDAD …

Go to article

Cheating To Get Better Roommates In A Random Stable Matching, Chien-Chung Huang Dec 2006

Cheating To Get Better Roommates In A Random Stable Matching, Chien-Chung Huang

Computer Science Technical Reports

This paper addresses strategies for the stable roommates problem, assuming that a stable matching is chosen at random. We investigate how a cheating man should permute his preference list so that he has a higher-ranking roommate probabilistically. In the first part of the paper, we identify a necessary condition for creating a new stable roommate for the cheating man. This condition precludes any possibility of his getting a new roommate ranking higher than all his stable roommates when everyone is truthful. Generalizing to the case that multiple men collude, we derive another impossibility result: given any stable matching in which …

Go to article

Evaluating Next Cell Predictors With Extensive Wi-Fi Mobility Data, Libo Song, David Kotz, Ravi Jain, Xiaoning He Dec 2006

Evaluating Next Cell Predictors With Extensive Wi-Fi Mobility Data, Libo Song, David Kotz, Ravi Jain, Xiaoning He

Dartmouth Scholarship

Location is an important feature for many applications, and wireless networks can better serve their clients by anticipating client mobility. As a result, many location predictors have been proposed in the literature, though few have been evaluated with empirical evidence. This paper reports on the results of the first extensive empirical evaluation of location predictors, using a two-year trace of the mobility patterns of over 6,000 users on Dartmouth's campus-wide Wi-Fi wireless network. The surprising results provide critical evidence for anyone designing or using mobility predictors. \par We implemented and compared the prediction accuracy of several location predictors drawn from …

Go to article

Mobicom Poster Abstract: Bandwidth Reservation Using Wlan Handoff Prediction, Libo Song, Udayan Deshpande, Ulaş C. Kozat, David Kotz, Ravi Jain Oct 2006

Mobicom Poster Abstract: Bandwidth Reservation Using Wlan Handoff Prediction, Libo Song, Udayan Deshpande, Ulaş C. Kozat, David Kotz, Ravi Jain

Dartmouth Scholarship

Many network services may be improved or enabled by successful predictions of users' future mobility. The success of predictions depend on how much accuracy can be achieved on real data and on the sensitivity of particular applications to this achievable accuracy. We investigate these issues for the case of advanced bandwidth reservation using real WLAN traces collected on the Dartmouth College campus.

Go to article

Tools And Algorithms To Advance Interactive Intrusion Analysis Via Machine Learning And Information Retrieval, Javed Aslam, Sergey Bratus, Virgil Pavlu Sep 2006

Tools And Algorithms To Advance Interactive Intrusion Analysis Via Machine Learning And Information Retrieval, Javed Aslam, Sergey Bratus, Virgil Pavlu

Computer Science Technical Reports

We consider typical tasks that arise in the intrusion analysis of log data from the perspectives of Machine Learning and Information Retrieval, and we study a number of data organization and interactive learning techniques to improve the analyst's efficiency. In doing so, we attempt to translate intrusion analysis problems into the language of the abovementioned disciplines and to offer metrics to evaluate the effect of proposed techniques. The Kerf toolkit contains prototype implementations of these techniques, as well as data transformation tools that help bridge the gap between the real world log data formats and the ML and IR data …

Go to article

Digital Image Ballistics From Jpeg Quantization, Hany Farid Sep 2006

Digital Image Ballistics From Jpeg Quantization, Hany Farid

Computer Science Technical Reports

Most digital cameras export images in the JPEG file format. This lossy compression scheme employs a quantization table that controls the amount of compression achieved. Different cameras typically employ different tables. A comparison of an image's quantization scheme to a database of known cameras affords a simple technique for confirming or denying an image's source. Similarly, comparison to a database of photo-editing software can be used in a forensic setting to determine if an image was edited after its original recording.

Go to article

Metric Measurements On A Plane From A Single Image, Micah K. Johnson, Hany Farid Aug 2006

Metric Measurements On A Plane From A Single Image, Micah K. Johnson, Hany Farid

Computer Science Technical Reports

The past decade has seen considerable advances in the application of principles from projective geometry to problems in image analysis and computer vision. In this paper, we review a subset of this work, and leverage these results for the purpose of forensic analysis. Specifically, we review three techniques for making metric measurements on planar surfaces from a single image. The resulting techniques should prove useful in forensic settings where real-world measurements are required.

Go to article

Sampled: Shared Anonymous Music Playback Using Wireless Devices, Constantinos Neophytou Jun 2006

Sampled: Shared Anonymous Music Playback Using Wireless Devices, Constantinos Neophytou

Computer Science Technical Reports

Recent advances in mobile computing enable many new applications, yet at the same time create privacy implications caused by the increasing amount of data that becomes available. This thesis will explore the possibilities of wireless-enabled portable devices and their attending privacy implications. We will describe how such a device containing personal information about the musical preferences of its user can help improve the user's experience in a social setting where music is played for all, and at the same time preserve each user's privacy.

Go to article

Wait-Free And Obstruction-Free Snapshot, Khanh Do Ba Jun 2006

Wait-Free And Obstruction-Free Snapshot, Khanh Do Ba

Dartmouth College Undergraduate Theses

The snapshot problem was first proposed over a decade ago and has since been well-studied in the distributed algorithms community. The challenge is to design a data structure consisting of $m$ components, shared by upto $n$ concurrent processes, that supports two operations. The first, $Update(i,v)$, atomically writes $v$ to the $i$th component. The second, $Scan()$, returns an atomic snapshot of all $m$ components. We consider two termination properties: wait-freedom, which requires a process to always terminate in a bounded number of its own steps, and the weaker obstruction-freedom, which requires such termination only for processes that eventually execute uninterrupted. First, …

Go to article

Computation Reuse In Statics And Dynamics Problems For Assemblies Of Rigid Bodies, Anne Loomis Jun 2006

Computation Reuse In Statics And Dynamics Problems For Assemblies Of Rigid Bodies, Anne Loomis

Dartmouth College Master’s Theses

The problem of determining the forces among contacting rigid bodies is fundamental to many areas of robotics, including manipulation planning, control, and dynamic simulation. For example, consider the question of how to unstack an assembly, or how to find stable regions of a rubble pile. In considering problems of this type over discrete or continuous time, we often encounter a sequence of problems with similar substructure. The primary contribution of our work is the observation that in many cases, common physical structure can be exploited to solve a sequence of related problems more efficiently than if each problem were considered …

Go to article

Limited Delegation (Without Sharing Secrets) In Web Applications, Nicholas J. Santos May 2006

Limited Delegation (Without Sharing Secrets) In Web Applications, Nicholas J. Santos

Dartmouth College Undergraduate Theses

Delegation is the process wherein an entity Alice designates an entity Bob to speak on her behalf. In password-based security systems, delegation is easy: Alice gives Bob her password. This is a useful feature, and is used often in the real world. But it's also problematic. When Alice shares her password, she must delegate all her permissions, but she may wish to delegate a limited set. Also, as we move towards PKI-based systems, secret-sharing becomes impractical. This thesis explores one solution to these problems. We use proxy certificates in a non-standard way so that user Alice can delegate a subset …

Go to article

Risks Of Using Ap Locations Discovered Through War Driving, Minkyong Kim, Jeffrey J. Fielding, David Kotz May 2006

Risks Of Using Ap Locations Discovered Through War Driving, Minkyong Kim, Jeffrey J. Fielding, David Kotz

Dartmouth Scholarship

Many pervasive-computing applications depend on knowledge of user location. Because most current location-sensing techniques work only either indoors or outdoors, researchers have started using 802.11 beacon frames from access points (APs) to provide broader coverage. To use 802.11 beacons, they need to know AP locations. Because the actual locations are often unavailable, they use estimated locations from \em war driving. But these estimated locations may be different from actual locations. In this paper, we analyzed the errors in these estimates and the effect of these errors on other applications that depend on them. We found that the estimated AP locations …

Go to article

First Prev Next Last