Taxonomies are a useful and ubiquitous way of organizing information. However, creating organizational hierarchies is difficult because the process requires a global understanding of the objects to be categorized. Usually one is created by an individual or a small group of people working together for hours or even days. Unfortunately, this centralized approach does not work well for the large, quickly changing datasets found on the web. Cascade is an automated workflow that allows crowd workers to spend as little at 20 seconds each while collectively making a taxonomy. We evaluate Cascade and show that on three datasets its quality is 80-90% of that of experts. Cascade has a competitive cost to expert information architects, despite taking six times more human labor. Fortunately, this labor can be parallelized such that Cascade will run in as fast as four minutes instead of hours or days.

This paper describes Collabode, a web-based Java integrated development environment designed to support close, synchronous collaboration between programmers. We examine the problem of collaborative coding in the face of program compilation errors introduced by other users which make collaboration more difficult, and describe an algorithm for error-mediated integration of program code. Concurrent editors see the text of changes made by collaborators, but the errors reported in their view are based only on their own changes. Editors may run the program at any time, using only error-free edits supplied so far, and ignoring incomplete or otherwise error-generating changes. We evaluate this algorithm and interface on recorded data from previous pilot experiments with Collabode, and via a user study with student and professional programmers. We conclude that it offers appreciable benefits over naive continuous synchronization without regard to errors and over manual version control.

This paper introduces architectural and interaction patterns for integrating crowdsourced human contributions directly into user interfaces. We focus on writing and editing, complex endeavors that span many levels of conceptual and pragmatic activity. Authoring tools offer help with pragmatics, but for higher-level help, writers commonly turn to other people. We thus present Soylent, a word processing interface that enables writers to call on Mechanical Turk workers to shorten, proofread, and otherwise edit parts of their documents on demand. To improve worker quality, we introduce the Find-Fix-Verify crowd programming pattern, which splits tasks into a series of generation and review stages. Evaluation studies demonstrate the feasibility of crowdsourced editing and investigate questions of reliability, cost, wait time, and work time for edits.

The lack of access to visual information like text labels, icons, and colors can cause frustration and decrease independence for blind people. Current access technology uses automatic approaches to address some problems in this space, but the technology is error-prone, limited in scope, and quite expensive. In this paper, we introduce VizWiz, a talking application for mobile phones that offers a new alternative to answering visual questions in nearly real-time - asking multiple people on the web. To support answering questions quickly, we introduce a general approach for intelligently recruiting human workers in advance called quikTurkit so that workers are available when new questions arrive. A field deployment with 11 blind participants illustrates that blind people can effectively use VizWiz to cheaply answer questions in their everyday lives, highlighting issues that automatic approaches will need to address to be useful. Finally, we illustrate the potential of using VizWiz as part of the participatory design of advanced tools by using it to build and evaluate VizWiz::LocateIt, an interactive mobile tool that helps blind people solve general visual search problems.

Mechanical Turk (MTurk) provides an on-demand source of human computation. This provides a tremendous opportunity to explore algorithms which incorporate human computation as a function call. However, various systems challenges make this difficult in practice, and most uses of MTurk post large numbers of independent tasks. TurKit is a toolkit for prototyping and exploring algorithmic human computation, while maintaining a straight-forward imperative programming style. We present the crash-and-rerun programming model that makes TurKit possible, along with a variety of applications for human computation algorithms. We also present case studies of TurKit used for real experiments across different fields.

Mechanical Turk (MTurk) is an increasingly popular web service for paying people small rewards to do human computation tasks. Current uses of MTurk typically post independent parallel tasks. I am exploring an alternative iterative paradigm, in which workers build on or evaluate each other's work. Part of my proposal is a toolkit called TurKit which facilitates deployment of iterative tasks on MTurk. I want to explore using this technology as a new form of end-user programming, where end-users are writing ldquoprogramsrdquo that are really instructions executed by humans on MTurk.

For a graph ( V , E ), existing compact linear formulations for the minimum cut problem require Θ(| V || E |) variables and constraints and can be interpreted as a composition of | V | − 1 polyhedra for minimum s - t cuts in much the same way as early approaches to finding globally minimum cuts relied on | V | − 1 calls to a minimum s - t cut algorithm. We present the first formulation to beat this bound, one that uses O (| V | 2 ) variables and O (| V | 3 ) constraints. An immediate consequence of our result is a compact linear relaxation with O (| V | 2 ) constraints and O (| V | 3 ) variables for enforcing global connectivity constraints. This relaxation is as strong as standard cut-based relaxations and has applications in solving traveling salesman problems by integer programming as well as finding approximate solutions for survivable network design problems using Jain's iterative rounding method. Another application is a polynomial-time verifiable certificate of size n for for the NP-complete problem of l 1 -embeddability of a rational metric on an n -set (as opposed to a certificate of size n 2 known previously).

We present Inky, a command line for shortcut access to common web tasks.Inky aims to capture the efficiency benefits of typed commands while mitigating their usability problems.Inky commands have little or no new syntax to learn, and the system displays rich visual feedback while the user is typing, including missing parameters and contextual information automatically clipped from the target web site.Inky is an example of a new kind of hybrid between a command line and a GUI interface.We describe the design and implementation of two prototypes of this idea, and report the results of a field study.

We present Koala, a system that enables users to capture, share, automate, and personalize business processes on the web. Koala is a collaborative programming-by-demonstration system that records, edits, and plays back user interactions as pseudo-natural language scripts that are both human- and machine-interpretable. Unlike previous programming by demonstration systems, Koala leverages sloppy programming that interprets pseudo-natural language instructions (as opposed to formal syntactic statements) in the context of a given web page's elements and actions. Koala scripts are automatically stored in the Koalescence wiki, where a community of users can share, run, and collaboratively develop their "how-to" knowledge. Koala also takes advantage of corporate and personal data stores to automatically generalize and instantiate user-specific data, so that scripts created by one user are automatically personalized for others. Our initial experiences suggest that Koala is surprisingly effective at interpreting instructions originally written for people.

Keyword programming is a novel technique for reducing the need to remember details of programming language syntax and APIs, by translating a small number of keywords provided by the user into a valid expression. Prior work has demonstrated the feasibility and merit of this approach in limited domains. This paper presents a new algorithm that scales to the much larger domain of general-purpose Java programming. We tested the algorithm by extracting keywords from method calls in open source projects, and found that it could accurately reconstruct over 90% of the original expressions. We also conducted a study using keywords generated by users, whose results suggest that users can obtain correct Java code using keyword queries as accurately as they can write the correct Java code themselves

Unicode is becoming a dominant character representation format for information processing. This presents a very dangerous usability and security problem for many applications. The problem arises because many characters in the UCS (Universal Character Set) are visually and/or semantically similar to each other. This presents a mechanism for malicious people to carry out Unicode Attacks, which include spam attacks, phishing attacks, and web identity attacks. In this paper, we address the potential attacks, and propose a methodology for countering them. To evaluate the feasibility of our methodology, we construct a Unicode Character Similarity List (UC-SimList). We then implement a visual and semantic based edit distance (VSED), as well as a visual and semantic based Knuth-Morris-Pratt algorithm (VSKMP), to detect Unicode attacks. We develop a prototype Unicode attack detection tool, IDN-SecuChecker, which detects phishing weblinks and fake user name (account) attacks. We also introduce the possible practical use of Unicode attack detectors.

We introduce a new anti-phishing solution, the Web Wallet. The Web Wallet is a browser sidebar which users can use to submit their sensitive information online. It detects phishing attacks by determining where users intend to submit their information and suggests an alternative safe path to their intended site if the current site does not match it. It integrates security questions into the user's workflow so that its protection cannot be ignored by the user. We conducted a user study on the Web Wallet prototype and found that the Web Wallet is a promising approach. In the study, it significantly decreased the spoof rate of typical phishing attacks from 63% to 7%, and it effectively prevented all phishing attacks as long as it was used. A majority of the subjects successfully learned to depend on the Web Wallet to submit their login information. However, the study also found that spoofing the Web Wallet interface itself was an effective attack. Moreover, it was not easy to completely stop all subjects from typing sensitive information directly into web forms.

Modern applications provide interfaces for scripting, but many users do not know how to write script commands. However, many users are familiar with the idea of entering keywords into a web search engine. Hence, if a user is familiar with the vocabulary of an application domain, we anticipate that they could write a set of keywords expressing a command in that domain. For instance, in the web browsing domain, a user might enter click search button. We call expressions of this form keyword commands, and we present a novel approach for translating keyword commands directly into executable code. Our prototype of this system in the web browsing domain translates click search button into the Chickenfoot code click(findButton("search")). This code is then executed in the context of a web browser to carry out the effect. We also present an implementation of this system in the domain of Microsoft Word. A user study revealed that subjects could use keyword commands to successfully complete 90% of the web browsing tasks in our study without instructions or training. Conversely, we would expect users to complete close to 0% of the tasks if they had to guess the underlying JavaScript commands with no instructions or training.

This paper describes the iCare Interaction Assistant, an assistive device for helping the individuals who are visually impaired during social interactions. The research presented here addresses the problems encountered in implementing real-time face recognition algorithms on a wearable device. Face recognition is the initial step towards building a comprehensive social interaction assistant that will identify and interpret facial expressions, emotions and gestures. Experiments conducted for selecting a face recognition algorithm that works despite changes in facial pose and illumination angle are reported. Performance details of the face recognition algorithms tested on the device are presented along with the overall performance of the system. The specifics of the hardware components used in the wearable device are mentioned and the block diagram of the wearable system is explained in detail.

This presentation demonstrates a working prototype of the iCare Interaction Assistant, a wearable assistive device based on research aimed at facilitating the social interactions of people who are blind or visually impaired. Using a tiny unobtrusive camera mounted inside the nose bridge of a pair of eyeglasses, this prototype is able to learn and recognize faces at a distances up to 10 feet, thus allowing the user to initiate conversations with persons in their vicinity, without waiting for others to approach them. Ongoing work is aimed at facilitating the subsequent verbal interaction by recognizing and interpreting non-verbal communication, including eye contact, facial expressions, emotions, and gestures.