Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
- Keyword
- Publication
- Publication Type
Articles 1 - 23 of 23
Full-Text Articles in Physical Sciences and Mathematics
Cheating To Get Better Roommates In A Random Stable Matching, Chien-Chung Huang
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 …
Evaluating Next Cell Predictors With Extensive Wi-Fi Mobility Data, Libo Song, David Kotz, Ravi Jain, Xiaoning He
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 …
Mobicom Poster Abstract: Bandwidth Reservation Using Wlan Handoff Prediction, Libo Song, Udayan Deshpande, Ulaş C. Kozat, David Kotz, Ravi Jain
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.
Digital Image Ballistics From Jpeg Quantization, Hany Farid
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.
Tools And Algorithms To Advance Interactive Intrusion Analysis Via Machine Learning And Information Retrieval, Javed Aslam, Sergey Bratus, Virgil Pavlu
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 …
Metric Measurements On A Plane From A Single Image, Micah K. Johnson, Hany Farid
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.
Sampled: Shared Anonymous Music Playback Using Wireless Devices, Constantinos Neophytou
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.
Wait-Free And Obstruction-Free Snapshot, Khanh Do Ba
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, …
Computation Reuse In Statics And Dynamics Problems For Assemblies Of Rigid Bodies, Anne Loomis
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 …
Limited Delegation (Without Sharing Secrets) In Web Applications, Nicholas J. Santos
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 …
Scalability In A Secure Distributed Proof System, Kazuhiro Minami, David Kotz
Scalability In A Secure Distributed Proof System, Kazuhiro Minami, David Kotz
Dartmouth Scholarship
A logic-based language is often adopted in systems for pervasive computing, because it provides a convenient way to define rules that change the behavior of the systems dynamically. Those systems might define rules that refer to the users' context information to provide context-aware services. For example, a smart-home application could define rules referring to the location of a user to control the light of a house automatically. In general, the context information is maintained in different administrative domains, and it is, therefore, desirable to construct a proof in a distributed way while preserving each domain's confidentiality policies. In this paper, …
Risks Of Using Ap Locations Discovered Through War Driving, Minkyong Kim, Jeffrey J. Fielding, David Kotz
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 …
Visualizing Paths In Context, Fabio Pellacini, Lori Lorigo, Geri Gay
Visualizing Paths In Context, Fabio Pellacini, Lori Lorigo, Geri Gay
Computer Science Technical Reports
Data about movement through a space is increasingly becoming available for capture and analysis. In many applications, this data is captured or modeled as transitions between a small number of areas of interests, or a finite set of states, and these transitions constitute paths in the space. Similarities and differences between paths are of great importance to such analyses, but can be difficult to assess. In this work we present a visualization approach for representing paths in context, where individual paths can be compared to other paths or to a group of paths. Our approach summarizes path behavior using a …
Channel Sampling Strategies For Monitoring Wireless Networks, Udayan Deshpande, Tristan Henderson, David Kotz
Channel Sampling Strategies For Monitoring Wireless Networks, Udayan Deshpande, Tristan Henderson, David Kotz
Dartmouth Scholarship
Monitoring the activity on an IEEE 802.11 network is useful for many applications, such as network management, optimizing deployment, or detecting network attacks. Deploying wireless sniffers to monitor every access point in an enterprise network, however, may be expensive or impractical. Moreover, some applications may require the deployment of multiple sniffers to monitor the numerous channels in an 802.11 network. In this paper, we explore sampling strategies for monitoring multiple channels in 802.11b/g networks. We describe a simple sampling strategy, where each channel is observed for an equal, predetermined length of time, and consider applications where such a strategy might …
Extracting A Mobility Model From Real User Traces, Minkyong Kim, David Kotz, Songkuk Kim
Extracting A Mobility Model From Real User Traces, Minkyong Kim, David Kotz, Songkuk Kim
Dartmouth Scholarship
Understanding user mobility is critical for simulations of mobile devices in a wireless network, but current mobility models often do not reflect real user movements. In this paper, we provide a foundation for such work by exploring mobility characteristics in traces of mobile users. We present a method to estimate the physical location of users from a large trace of mobile devices associating with access points in a wireless network. Using this method, we extracted tracks of always-on Wi-Fi devices from a 13-month trace. We discovered that the speed and pause time each follow a log-normal distribution and that the …
Predictability Of Wlan Mobility And Its Effects On Bandwidth Provisioning, Libo Song, Udayan Deshpande, Ulaş C. Kozat, David Kotz, Ravi Jain
Predictability Of Wlan Mobility And Its Effects On Bandwidth Provisioning, Libo Song, Udayan Deshpande, Ulaş C. Kozat, David Kotz, Ravi Jain
Dartmouth Scholarship
Wireless local area networks (WLANs) are emerging as a popular technology for access to the Internet and enterprise networks. In the long term, the success of WLANs depends on services that support mobile network clients. \par Although other researchers have explored mobility prediction in hypothetical scenarios, evaluating their predictors analytically or with synthetic data, few studies have been able to evaluate their predictors with real user mobility data. As a first step towards filling this fundamental gap, we work with a large data set collected from the Dartmouth College campus-wide wireless network that hosts more than 500 access points and …
Crawdad: A Community Resource For Archiving Wireless Data At Dartmouth, Jihwang Yeo, David Kotz, Tristan Henderson
Crawdad: A Community Resource For Archiving Wireless Data At Dartmouth, Jihwang Yeo, David Kotz, Tristan Henderson
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, a Community Resource for Archiving Wireless Data at Dartmouth, is a new NSF-funded project to build 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 identify and evaluate real and interesting problems in mobile and pervasive computing. This report outlines the CRAWDAD project, the kick-off workshop that was held …
A Simple Computational Method For The Identification Of Disease-Associated Loci In Complex, Incomplete Pedigrees, Gregory Leibon, Dan Rockmore, Martin R. Pollak
A Simple Computational Method For The Identification Of Disease-Associated Loci In Complex, Incomplete Pedigrees, Gregory Leibon, Dan Rockmore, Martin R. Pollak
Computer Science Technical Reports
We present an approach, called the Shadow Method, for the identification of disease loci from dense genetic marker maps in complex, potentially incomplete pedigrees. Shadow is a simple method based on an analysis of the patterns of obligate meiotic recombination events in genotypic data. This method can be applied to any high density marker map and was specifically designed to explore the fact that extremely dense marker maps are becoming more readily available. We also describe how to interpret and associated meaningful P-Values to the results. Shadow has significant advantages over traditional parametric linkage analysis methods in that it can …
Secure Context-Sensitive Authorization, Kazuhiro Minami
Secure Context-Sensitive Authorization, Kazuhiro Minami
Dartmouth College Ph.D Dissertations
Pervasive computing leads to an increased integration between the real world and the computational world, and many applications in pervasive computing adapt to the user's context, such as the location of the user and relevant devices, the presence of other people, light or sound conditions, or available network bandwidth, to meet a user's continuously changing requirements without taking explicit input from the users. We consider a class of applications that wish to consider a user's context when deciding whether to authorize a user's access to important physical or information resources. Such a context-sensitive authorization scheme is necessary when a mobile …
Path Planning Algorithms Under The Link-Distance Metric, David Phillip Wagner
Path Planning Algorithms Under The Link-Distance Metric, David Phillip Wagner
Dartmouth College Ph.D Dissertations
The Traveling Salesman Problem and the Shortest Path Problem are famous problems in computer science which have been well studied when the objective is measured using the Euclidean distance. Here we examine these geometric problems under a different set of optimization criteria. Rather than considering the total distance traversed by a path, this thesis looks at reducing the number of times a turn is made along that path, or equivalently, at reducing the number of straight lines in the path. Minimizing this objective value, known as the link-distance, is useful in situations where continuing in a given direction is cheap, …
A Novel Minimized Dead-End Elimination Criterion And Its Application To Protein Redesign In A Hybrid Scoring And Search Algorithm For Computing Partition Functions Over Molecular Ensembles, Ivelin Georgiev, Ryan H. Lilien, Bruce R. Donald
A Novel Minimized Dead-End Elimination Criterion And Its Application To Protein Redesign In A Hybrid Scoring And Search Algorithm For Computing Partition Functions Over Molecular Ensembles, Ivelin Georgiev, Ryan H. Lilien, Bruce R. Donald
Computer Science Technical Reports
Novel molecular function can be achieved by redesigning an enzyme's active site so that it will perform its chemical reaction on a novel substrate. One of the main challenges for protein redesign is the efficient evaluation of a combinatorial number of candidate structures. The modeling of protein flexibility, typically by using a rotamer library of commonly-observed low-energy side-chain conformations, further increases the complexity of the redesign problem. A dominant algorithm for protein redesign is Dead-End Elimination (DEE), which prunes the majority of candidate conformations by eliminating rigid rotamers that provably are not part of the Global Minimum Energy Conformation (GMEC). …
On Improving Wireless Broadcast Reliability Of Sensor Networks Using Erasure Codes, Rajnish Kumar, Arnab Paul, Umakishore Ramachandran, David Kotz
On Improving Wireless Broadcast Reliability Of Sensor Networks Using Erasure Codes, Rajnish Kumar, Arnab Paul, Umakishore Ramachandran, David Kotz
Dartmouth Scholarship
Efficient and reliable dissemination of information over a large area is a critical ability of a sensor network for various reasons such as software updates and transferring large data objects (e.g., surveillance images). Thus efficiency of wireless broadcast is an important aspect of sensor network deployment. In this paper, we study FBcast, a new broadcast protocol based on the principles of modern erasure codes. We show that our approach provides high reliability, often considered critical for disseminating codes. In addition FBcast offers limited data confidentiality. For a large network, where every node may not be reachable by the source, we …
Improving Data Access For Computational Grid Applications, Ron Oldfield, David Kotz
Improving Data Access For Computational Grid Applications, Ron Oldfield, David Kotz
Dartmouth Scholarship
High-performance computing increasingly occurs on “computational grids” composed of heterogeneous and geographically distributed systems of computers, networks, and storage devices that collectively act as a single “virtual” computer. A key challenge in this environment is to provide efficient access to data distributed across remote data servers. Our parallel I/O framework, called Armada, allows application and data-set providers to flexibly compose graphs of processing modules that describe the distribution, application interfaces, and processing required of the dataset before computation. Although the framework provides a simple programming model for the application programmer and the data-set provider, the resulting graph may contain bottlenecks …