Online dynamic reordering

We present a pipelining, dynamically tunable reorder operator for providing user control during long running, data- intensive operations. Users can see partial results and accordingly direct the processing by specifying preferences for various data items; data of interest is prioritized for early processing. The reordering mechanism is efficient and non-blocking and can be used over arbitrary data streams from files and indexes, as well as continuous data feeds. We also investigate several policies for the reordering based on the performance goals of various typical applications. We present performance results for reordering in the context of an online aggregation implementation in Informix and in the context of sorting and scrolling in a large-scale spreadsheet. Our experiments demonstrate that for a variety of data distributions and applications, reordering is responsive to dynamic preference changes, imposes minimal overheads in overall completion time, and provides dramatic improvements in the quality of the feedback over time. Surprisingly, preliminary experiments indicate that online reordering can also be useful in traditional batch query processing, because it can serve as a form of pipelined, approximate sorting. Received April 28, 2000 / Accepted June 23, 2000     

Progressive evaluation of nested aggregate queries

In many decision-making scenarios, decision makers require rapid feedback to their queries, which typically involve aggregates. The traditional blocking execution model can no longer meet the demands of these users. One promising approach in the literature, called online aggregation, evaluates an aggregation query progressively as follows: as soon as certain data have been evaluated, approximate answers are produced with their respective running confidence intervals; as more data are examined, the answers and their corresponding running confidence intervals are refined. In this paper, we extend this approach to handle nested queries with aggregates (i.e., at least one inner query block is an aggregate query) by providing users with (approximate) answers progressively as the inner aggregation query blocks are evaluated. We address the new issues pose by nested queries. In particular, the answer space begins with a superset of the final answers and is refined as the aggregates from the inner query blocks are refined. For the intermediary answers to be meaningful, they have to be interpreted with the aggregates from the inner queries. We also propose a multi-threaded model in evaluating such queries: each query block is assigned to a thread, and the threads can be evaluated concurrently and independently. The time slice across the threads is nondeterministic in the sense that the user controls the relative rate at which these subqueries are being evaluated. For enumerative nested queries, we propose a priority-based evaluation strategy to present answers that are certainly in the final answer space first, before presenting those whose validity may be affected as the inner query aggregates are refined. We implemented a prototype system using Java and evaluated our system. Results for nested queries with a level and multiple levels of nesting are reported. Our results show the effectiveness of the proposed mechanisms in providing progressive feedback that reduces the initial waiting time of users significantly without sacrificing the quality of the answers. Received April 25, 2000 / Accepted June 27, 2000     

Diacritical processing for unconstrained online handwriting recognition using a forward search

Out-of-order diacriticals introduce significant complexity to the design of an online handwriting recognizer, because they require some reordering of the time domain information. It is common in cursive writing to write the body of an `i' or `t' during the writing of the word, and then to return and dot or cross the letter once the word is complete. The difficulty arises because we have to look ahead, when scoring one of these letters, to find the mark occurring later in the writing stream that completes the letter. We should also remember that we have used this mark, so that we don't use it again for a different letter, and we should also penalize a word if there are some marks that look like diacriticals that are not used. One approach to this problem is to scan the writing some distance into the future to identify candidate diacriticals, remove them in a preprocessing step, and associate them with the matching letters earlier in the word. If done as a preliminary operation, this approach is error-prone: marks that are not diacriticals may be incorrectly identified and removed, and true diacriticals may be skipped. This paper describes a novel extension to a forward search algorithm that provides a natural mechanism for considering alternative treatments of potential diacriticals, to see whether it is better to treat a given mark as a diacritical or not, and directly compare the two outcomes by score. Received October 30, 1998 / Revised January 25, 1999     

Engineering Methods from Method Requirements Specifications

By analogy with a Software Requirements Specification (SRS), it is argued that a Method Requirements Specification (MRS) should be introduced in method engineering. It shares with the SRS the property of implementation-independence. This means that an MRS must be an instance of an abstract metamodel and not of a technical metamodel like GOPRR (Graph, Object, Property, Relationship, and Role). The MRS is then translated to be an instantiation of a technical metamodel. We develop a representation system for an MRS and describe an automated process for instantiating a technical metamodel with an MRS. This instantiation is used to produce the actual method which is then given to a metaCASE to produce a CASE tool. Thus, we propose a method engineering approach rooted in the MRS.     

Online handwriting recognition: the NPen++ recognizer

This paper presents the online handwriting recognition system NPen++ developed at the University of Karlsruhe and Carnegie Mellon University. The NPen++ recognition engine is based on a multi-state time delay neural network and yields recognition rates from 96% for a 5,000 word dictionary to 93.4% on a 20,000 word dictionary and 91.2% for a 50,000 word dictionary. The proposed tree search and pruning technique reduces the search space considerably without losing too much recognition performance compared to an exhaustive search. This enables the NPen++ recognizer to be run in real-time with large dictionaries. Initial recognition rates for whole sentences are promising and show that the MS-TDNN architecture is suited to recognizing handwritten data ranging from single characters to whole sentences. Received September 3, 2000 / Revised October 9, 2000     

RAV (reparameterized angle variations) algorithm for online handwriting recognition

A new algorithm RAV (reparameterized angle variations) is proposed which makes explicit use of trajectory information where the time evolution of the pen coordinates plays a crucial role. The algorithm is robust against stroke connections/abbreviations as well as shape distortions, while maintaining reasonable robustness against stroke-order variations. Preliminary experiments are reported on tests against the Kuchibue_d-96-02 database from the Tokyo University of Agriculture and Technology. Received July 24, 2000 / Revised October 6, 2000     

Scenario Analysis in an Automated Tool for Requirements Engineering

 This paper presents an automated tool for scenario-driven requirements engineering where scenario analysis plays the central role. It is shown that a scenario can be described by three views of data flow, entity relationship and state transition models by slight extensions of classic data flow, entity relationship and state transition diagrams. The notions of consistency and completeness of a set of scenarios are formally defined in graph theory terminology and automatically checked by the tool. The tool supports automatic validation of requirements definitions by analysing the consistency between a set of scenarios and requirements models. It also supports automatic synthesis of requirements models from a set of scenarios. Its utility and usefulness are demonstrated by a non-trivial example in the paper. Case studies of the tools are also presented.     

Mechanized result verification: an industrial application

We present part of an industrial project where mechanized theorem proving is used for the validation of a translator which generates safety critical software. In this project, the mechanized proof is decomposed in two parts: one is done “online”, at each run of the translator, by a custom prover which checks automatically that the result of each translation meets some verification conditions; the other is done “offline”, once for all, interactively with a general purpose prover; the offline proof shows that the verification conditions checked by the online prover are sufficient to guarantee the correctness of each translation. The provably correct verification conditions can thus be seen as specifications for the online prover. This approach is called mechanized result verification. This paper describes the project requirements and explains the motivations to formal validation by mechanized result verification, provides an overview of the formalization of the specifications for the online prover and discusses in detail some issues we have addressed in the mechanized offline proof.     

Incorporating local consistency information into the online signature verification process

This paper describes a fully operational online signature verification system. Its heart is the SmartPen™, a special input device enabling the perception of force and angle signals. The main key for the success of the approach is the decoupling of the time-alignment stage, based on the dynamic time warping algorithm, and the actual feature-extraction process, in which the wavelet transform plays a central role. This separation allows taking into account information about the relative stability of different phenomena present in a specific person's handwriting. The usefulness of the approach is illustrated by presenting the results of a full-scale field-test. Received November 2, 1997 / Revised April 21, 1998     

Experiments with adaptation strategies for a prototype-based recognition system for isolated handwritten characters

This paper describes an adaptive recognition system for isolated handwritten characters and the experiments carried out with it. The characters used in our experiments are alphanumeric characters, including both the upper- and lower-case versions of the Latin alphabets and three Scandinavian diacriticals. The writers are allowed to use their own natural style of writing. The recognition system is based on the k-nearest neighbor rule. The six character similarity measures applied by the system are all based on dynamic time warping. The aim of the first experiments is to choose the best combination of the simple preprocessing and normalization operations and the dissimilarity measure for a multi-writer system. However, the main focus of the work is on online adaptation. The purpose of the adaptations is to turn a writer-independent system into writer-dependent and increase recognition performance. The adaptation is carried out by modifying the prototype set of the classifier according to its recognition performance and the user's writing style. The ways of adaptation include: (1) adding new prototypes; (2) inactivating confusing prototypes; and (3) reshaping existing prototypes. The reshaping algorithm is based on the Learning Vector Quantization. Four different adaptation strategies, according to which the modifications of the prototype set are performed, have been studied both offline and online. Adaptation is carried out in a self-supervised fashion during normal use and thus remains unnoticed by the user. Received June 30, 1999 / Revised September 29, 2000     

Integrating E-Commerce and Games

This paper investigates how many users of commercial interactive systems are not properly agents within the interactive narrative, largely due to the dynamics of branding in cyberspace. Parallels are drawn between the dynamic personalization of e-CRM engines and context aware computing systems. Several seminal games are discussed as examples of systems in which very different relationships exist between users and the system. Arguments are made for designing e-commerce interactive systems that install into games, inside the game narrative. Correspondence to: Ms N. Cummins, Preject Brand Communications Consultancy, Unit P, Carlton Works Studios, Asylum Road, London SE15 2SB, UK. Email: nizami@preject.com     

Rain-Dancing with Pseudo-Science

In this polemical essay the authors ask whether computerisation has become the neurosis of our age. By comparing the application of IT methodologies with ritual behaviour within human social institutions, they propose that the so-called rationality of management science, with its tidy benchmarking, auditing, categorisation and performance measurements etc., is actually a pseudo-science. They show that from the position of Nietzschean epistemology, this rationality is merely a false claim to the instrumental efficacy of data modelling, that is indistinguishable from the rain-dancing of primitive tribes.     

Knowledge Networking in Cross-Cultural Settings

Knowledge networking in the cross-cultural setting here focuses on promoting a culture of shared communication, values and knowledge, seeking cooperation through valorisation of diversity. The process is seen here in terms of creating new alliances of creators, users, mediators and facilitators of knowledge. At the global level, knowledge networking is seen as a symbiotic relationship between local and global knowledge resources. This focus is informed by the human-centred vision of the information society, which seeks a symbiotic relationship between technology and society. It explores the nature of the knowledge in transition, raising issues of technology and knowledge transfer in the local–global context. The notions of human–machine symbiosis and of diversity and coherence provide a handle to explore the role of technology for sustainable development. The centrality of knowledge in stimulating knowledge networking for cross-cultural collaboration is illustrated through an exemplar of an EU–India Cross-Cultural Innovation Network project, a collaboration between European and Indian universities and institutes.     

Taxonomy of interpolation constraints on recursive subdivision surfaces

Published online: 14 May 2002