Permission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies are notmade or distributed for profit or commercial advantage and that copies bearthis notice and the full citation on the first page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a fee.UIST ’98. San Francisco, CA 1998 ACM 0-58113-034-1/98/11... $5.00195A Dynamic Grouping Technique for Ink and Audio NotesPatrick ChiuFX Palo Alto Laboratory3400 Hillview Avenue, Bldg. 4Palo Alto, CA 94304,USATel: 1-650-813-7498E-mail: [email protected] WilcoxFX Palo Alto Laboratory3400 Hillview Avenue, Bldg. 4Palo Alto, CA 94304, USATel: 1-650-813-7574E-mail: [email protected] this paper, we describe a technique for dynamicallygrouping digital ink and audio to support user interaction infreeform note-taking systems. For ink, groups of strokesmight correspond to words, lines, or paragraphs ofhandwritten text. For audio, groups might be a completespoken phrase or a speaker turn in a conversation. Ink andaudio grouping is important for editing operations such asdeleting or moving chunks of ink and audio notes. Thegrouping technique is based on hierarchical agglomerativeclustering. This clustering algorithm yields groups of inkor audio in a range of sizes, depending on the level in thehierarchy, and thus provides structure for simple interactiveselection and rapid non-linear expansion of a selection. Inkand audio grouping is also important for marking portionsof notes for subsequent browsing and retrieval. Integrationof the ink and audio clusters provides a flexible way tobrowse the notes by selecting the ink cluster and playingthe corresponding audio cluster.KEYWORDS: Ink, audio, note-taking, grouping, clusteringmultimedia, marking, informal systems, freeforminteraction, implicit structure, emergent structure.INTRODUCTIONIn multimedia note-taking systems, interacting with datasuch as digital ink and audio is challenging. Due to thenature of note-taking activity, which requires informal andrapid interaction, users must be allowed to write and torecord audio with minimal attention devoted to structuringdata. Freeform systems have been designed to support thisstyle of interaction for note-taking, in which the user maywrite ink strokes of any shape anywhere on the page, andrecord audio as unstructured streams. Typically, the inkand audio are correlated by time so that “playing” aselected ink stroke will play from the corresponding pointin audio. Examples of such ink and audio note-takingsystems are NoTime [7], Filochat [19], Dynomite [20] andAudio Notebook [17]. When the user wishes to edit orbrowse the ink or audio data, the lack of structure becomeslimiting. The challenge is to provide computational supportto dynamically group the ink and audio data into units thatare useful for user interaction.For digital ink and audio, these computations are far morecomplicated than the ones for online text, where theunderlying string data structure readily parses intomeaningful groups of words, lines and paragraphs. In text,selection of a particular word or line is easy. For example,in many systems the user mouse clicks once to select aword, twice to select a line, and three times to select aparagraph. On the other hand, selection of handwritten inkcorresponding to a word or line is difficult. This is becausedigital ink is composed of strokes which are graphicalobjects in a freeform space and not automatically mappedinto meaningful units. Audio poses analogous problems.Even when it is mapped onto a timeline, it is difficult toselect a segment of audio corresponding to a phrase or aturn in a conversation. These characteristics of ink andaudio make it tedious for the user to manipulate multimediadata; for example, to delete a word in handwritten text or tomark a spoken sentence in audio.In this paper, we describe a novel technique for dynamicgrouping of ink and audio data for user interaction. It hasbeen implemented in the current generation of theDynomite [20] ink and audio note-taking system.Dynomite runs on a pen-based notebook computer withWindows 95. In addition to providing time synchronizedink and audio notes, the Dynomite system allowsproperties, or data types, to be added to specific ink for thepurpose of indexing. Dynomite also allows segments ofaudio to be marked, or “highlighted”, for subsequentretrieval.The grouping technique described here provides structurethat facilitates selection of specific portions ink and audio.It is non-linear and gives rapid expansion of selections, thusproviding users with control over the amount of groupingof the media. For ink, grouping levels correspond roughlyto words, lines, or paragraphs of text. For audio, the levelscorrespond to phrases, turns in the conversations, or topicchanges. The technique is based on hierarchical196agglomerative clustering of ink strokes and audiosegments. Grouping is performed on ink and audioseparately, and integration of these media can beaccomplished by matching the resulting groups from eachmedium. Leveraging this tight integration of ink and audiodata gives a new way to browse through multimedia notesby playing the audio groups corresponding to ink groupsselected by the user.In the following, we first describe related work, theclustering algorithm, and provide examples to demonstrateits operation. We discuss applications of this technique toselection and marking. We then show how integrating theink and audio groups can be applied to browsing notes. Weillustrate how these techniques work in practice with a realexample taken from a Japanese language class. Finally, wediscuss further directions for research. In the appendix, wedescribe an object-oriented implementation of thealgorithm.RELATED WORKStructuring and interacting with data in freeform systems isan active area of research (e.g. see [4], [16]), andunderstanding some of the general principles is helpful indesigning a system for ink and audio note-taking. Infreeform systems, flexibility in the organization of data isimportant. The data should not be structured prematurely;perceived structures as seen or heard by each individualuser may emerge in interesting and unexpected ways, andmay be subjected to multiple interpretations. When thedomain of application is known, a more robust system canbe achieved by designing it