Communications of the ACM

The skip quadtree: a simple dynamic data structure for multidimensional data

We present a new multi-dimensional data structure, which we call the skip quadtree (for point data in R²) or the skip octree (for point data in R^d, with constant d > 2). Our data structure combines the best features of two well-known data structures, in that it has the well-defined "box"-shaped regions of region quadtrees and the logarithmic-height search and update hierarchical structure of skip lists. Indeed, the bottom level of our structure is exactly a region quadtree (or octree for higher dimensional data). We describe efficient algorithms for inserting and deleting points in a skip quadtree, as well as fast methods for performing point location, approximate range, and approximate nearest neighbor queries.

Meeting central: making distributed meetings more effective

The Meeting Central prototype is a suite of collaboration tools designed to support distributed meetings. The tools' minimalist design provides only those features that have the most impact on distributed meeting effectiveness. The collaboration suite is built on top of a distributed, extensible, and scalable framework.

Implicit java array bounds checking on 64-bit architecture

Interest in using Java for high-performance parallel computing has increased in recent years. One obstacle that has inhibited Java from widespread acceptance in the scientific community is the language requirement that all array accesses must be checked to ensure they are within bounds. In practice, array bounds checking in scientific applications may increase execution time by more than a factor of 2. Previous research has explored optimizations to statically eliminate bounds checks, but the dynamic nature of many scientific codes makes this difficult or impossible.Our approach is instead to create a new Java implementation that does not generate explicit bounds checks. It instead places arrays inside of Index Confinement Regions (ICRs), which are large, isolated, mostly unmapped virtual memory regions. Any array reference outside of its bounds will cause a protection violation; this provides implicit bounds checking. Our results show that our new Java implementation reduces the overhead of bounds checking from an average of 63% to an average of 9% on our benchmarks.

Verification: what works and what doesn't

Today's leading chip and system companies are faced with ever increasing design verification challenges; industry studies reveal that as much as 50% of the total schedule is being spent in verification. Large companies, with almost infinite resources, have shown that throwing CPU cycles and people at the simulation problem still doesn't guarantee a level of coverage desired by the design team.

Personalizing shared ubiquitous devices

Marketing computer support services through relationship and training strategies

In 2002, Harvard University's Division of Continuing Education (DCE) expanded its computer lab facility. This expansion allowed DCE to change its previous policy of restricting computer services to a small percentage of students to its current policy of extending these services to all DCE students.This flexibility enabled DCE's Institute for English Language (IEL) to change its previous position of assuming that all students did not have access to computer technology to its new position of assuming all students have access to computer technology. This new position has expanded the way IEL courses can be taught and managed. Church Street Staff initiated the building of relationships with IEL instructors to empower them with the skills and knowledge to infuse more technology into their courses.Church Street Staff organized and hosted a colloquium for IEL instructors in which they showcased services focused on a Harvard-developed instructional development Instructor's Toolkit. Main contacts for future support constituted the colloquium organization team. Team members conducted various parts of the colloquium to begin the process of building relationships with the instructors.The lab staff arranged bi-monthly follow-up training in the Instructor's Toolkit to a targeted cohort of IEL instructors. These instructors would then serve as peer mentors to their colleagues. The bi-monthly training culminated in a launch week in which the lab staff focused their attention on one-on-one help for the IEL instructors to launch their course websites.The success of the campaign was determined by the percentage of full-time instructors using email, website, bulletin board, and announcement tool as management and pedagogical tools complementing the classroom instruction.

From desktop to phonetop: a UI for web interaction on very small devices

While it is generally accepted that new Internet terminals should leverage the installed base of Web content and services, the differences between desktop computers and very small devices makes this challenging. Indeed, the browser interaction model has evolved on desktop computers having a unique combination of user interface (large display, keyboard, pointing device), hardware, and networking capabilities. In contrast, Internet enabled cell phones, typically with 3-10 lines of text, sacrifice usability as Web terminals in favor of portability and other functions. Based on our earlier experiences building and using a Web browser for small devices we propose a new UI that splits apart the integrated activities of link following and reading into separate modes: navigating to; and acting on web content. This interaction technique for very small devices is both simpler for navigating and allows users to do more than just read. The M-Links system incorporates modal browsing interaction and addresses a number of associated problems. We have built our system with an emphasis on simplicity and user extensibility and describe the design, implementation and evolution of the user interface.

Biased dictionaries with fast insert/deletes

A dictionary data structure supports efficient search, insert, and delete operations on n keys from a totally ordered universe. Red-black trees, 2-3 trees, AVL trees, skip lists and other classic data structures facilitate O(logn) time search, insert and deletes, matching the information theoretic lower bound when access probabilities are uniform i.i.d. If access probabilities are non-uniform but still i.i.d., there are other weighted data structures such as D-trees, biased search trees, splay trees and treaps which can achieve optimality.In many applications, however, the source of nonuniformity in access probabilities is locality of reference: examples include memory, cache, disk and buffer management and emerging applications in internetwork traffic management. In such applications, the access probability of any given key is not i.i.d., but decreases with idle time since the last access to the key.It is possible to adjust the weighted dictionaries to achieve optimal search time even under time dependent distributions; however insert/delete times will be suboptimal at O(logn). In this paper, we present a lazy updating scheme which can be applied to weighted dictionaries to improve their amortized insert/delete performance when access probabilities decrease with time; optimality of search time is preserved. More speci%cally, let r(k) be the number of distinct keys accessed since the last access to key k- that is r(k) is the move-to-front rank of k. Let rmax(k) be the maximum rank of k during its lifetime. Then our lazy update scheme enables the abovementioned data structures to perform search in O(log r(k)) time and insert/delete in O(log rmax(k)) time. We illustrate our lazy update scheme in the context of a new Biased Skip List data structure and show that our bounds are optimal.

A programming model for active documents

Getting some perspective: using process descriptions to index document history

Process descriptions are used in workflow and related systems to describe the flow of work and organisational responsibility in business processes, and to aid in coordination. However, the division of a working process into a sequence of steps provides only a partial view of the work involved. In many cases, the performance of individual tasks in a larger process may depend on interpretations and understandings of how other aspects of the work were conducted.We present an example from an ethnographic investigation of one particular organisation, and introduce a mechanism, which we call “Perspectives,” for dealing with it. A “Perspective” uses the process description to provide an index into the history of a document moving through a process. Perspectives allow workflow systems to manage and present information about the execution of specific process instances within the general frame of abstract process descriptions.