bluuebunny/crossref_metadata_2025 huggingface dataset:
Exploring the similarity space
Authors: Zobel Justin , Moffat Alistair
Published: January 2007

Ranked queries are used to locate relevant documents in text databases. In a ranked query a list of terms is specified, then the documents that most closely match the query are returned---in decreasing order of similarity---as answers. Crucial to the efficacy of ranked querying is the use of a similarity heuristic, a mechanism that assigns a numeric score indicating how closely a document and the query match. In this note we explore and categorise a range of similarity heuristics described in the literature. We have implemented all of these measures in a structured way, and have carried out retrieval experiments with a substantial subset of these measures.Our purpose with this work is threefold: first, in enumerating the various measures in an orthogonal framework we make it straightforward for other researchers to describe and discuss similarity measures; second, by experimenting with a wide range of the measures, we hope to observe which features yield good retrieval behaviour in a variety of retrieval environments; and third, by describing our results so far, to gather feedback on the issues we have uncovered. We demonstrate that it is surprisingly difficult to identify which techniques work best, and comment on the experimental methodology required to support any claims as to the superiority of one method over another.
Coporate IT skill needs
Authors: Sawyer Steve , Eschenfelder Kristin R. , Diekema Andrew , McClure Charles R.
Published: January 2007

This paper reports on a case study of the IT skills and needs at one site. The data is organized by assessing the members of BigCo's Corporate IT group regarding their present IT skill levels and the perception of skill needs both now and three years in the future. This work relies on a categorization drawn from both academic and professional literature regarding skill needs for IT professionals. In doing this work we draw on surveys, interviews, focus groups and archival documents to build a rich and detailed perspective on skill needs for the IT professionals at BigCo's Corporate IT group. Findings show that there is an implicit set of conceptual IT skills that IT professionals are expected to have. Further, the non-IT skill needs are presently very important and are expected to become even more important. Finally, there are important department-level, experience, and gender variations in the responses suggesting that IT roles are growing both more numerous and more specialized.
Book review: Neural Networks for Pattern Recognition By Christopher M. Bishop (Clarendon Press, 1995)
Authors: Van Dyke Parunak H.
Published: January 2007

Technical textbooks tend to be encyclopedic omnibus volumes, since the market rewards authors whose books can be used by teachers in many different classes. Pedagogically, this tendency is unfortunate, since it tends to homogenize the unique approaches and presentations that make great teachers truly effective. Bishop's textbook on neural nets is a welcome exception to the rule. It specifically limits its focus to feed-forward nets with explicit training. Much important work has been done in domains such as self-organizing nets, or nets with feedback, or fuzzy algorithms, but this volume avoids them to focus on the most basic network architecture. With this sharp focus, Bishop uses several excellent pedagogical techniques.
Coordinating autonomous entities with STL
Authors: Krone Oliver , Chantemargue Fabrice , Dagaeff Thierry , Schumacher Michael
Published: January 2007

This paper describes ECM, a new coordination model and STL its corresponding language. STL's power and expressiveness are shown through a distributed implementation of a generic autonomy-based multi-agent system, which is applied to a collective robotics simulation, thus demonstrating the appropriateness of STL for developing a generic coordination platform for autonomous agents.
Disk scheduling in System V
Authors: Geist Robert , Reynolds Robert , Pittard Eve
Published: January 2007

A variety of disk scheduling algorithms, including some newly defined ones, are compared both in simulation and in tests on a real machine running UNIX
*
System V. In the real system tests, first-come first-served (FCFS), shortest seek time first (SSTF), and the standard System V algorithm (SVS) are all seen to yield relatively poor mean waiting time performance when compared to the VSCAN(0.2) algorithm and modifications thereof suggested by Coffman. Nevertheless, each is seen to excel along a particular performance dimension. The adequacy of open, Poisson arrival simulation models in predicting disk scheduling performance is questioned, and an alternative arrival model is suggested which offers improved predictions in the System V environment.
A unified operational treatment of RPS reconnect delays
Authors: Buzen Jeffrey P. , Shum Annie W.
Published: January 2007

Expressions are presented for RPS reconnect delays in three basic cases: single path, multiple path with static reconnect, multiple path with dynamic reconnect. The assumption of homogeneous reconnects, which is introduced in the analysis, is shown to be implicit in many prior analyses. This assumption simplifies the resulting equations, but more general equations are also presented for the case where homogeneous reconnects are not assumed. These general results have not appeared previously. This paper also uses the assumption of constrained independence to derive a result for static reconnect which has only been derived previously using the maximum entropy principle. In the case of dynamic reconnect, constrained independence yields an entirely new closed form result. In addition to being a consistent extension of the static reconnect case, this new result is the only closed form expression for dynamic reconnect that yields a correct solution in certain saturated cases. Constrained independence can provide a useful alternative assumption in many other cases where complete independence is known to be only approximately correct.
Queueing delays in buffered multistage interconnection networks
Authors: Bouras Christos , Garofalakis John
Published: January 2007

Our work deals with the analysis of the queueing delays of buffered multistage Banyan networks of multiprocessors. We provide tight upper bounds on the mean delays of the second stage and beyond, in the case of infinite buffers. Our results are validated by simulations performed on a network simulator constructed by us. The analytic work for network stages beyond the first, provides a partial answer to open problems posed by previous research.
A statistical approach to computer performance modeling
Authors: Salsburg Michael A.
Published: January 2007

Models of discrete systems are often utilized to assist in computer engineering and procurement. The tools for modeling have been traditionally developed using either analytic methods or discrete event simulation. The research presented here explores the use of statistical techniques to augment and assist this basic set of tools.
Monit: a performance monitoring tool for parallel and pseudo-parallel programs
Authors: Kerola Teemu , Schwetman Herb
Published: January 2007

This paper describes a performance monitoring system, Monit, developed for performance evaluation of parallel systems. Monit uses trace files that are generated during the execution of parallel programs. Monit analyzes these trace files and produces time-oriented graphs of resource usage and system queues. Users interactively select the displayed items, resolution, and time intervals of interest. The current implementation of Monit is for SUN-3 workstation, but the program is easily adaptable to other devices.

We also introduce a parallel programming environment, PPL, implemented as a superset of C for the Sequent Balance 8000 multi-processor system. Parallel programs written in PPL can produce the trace files for Monit.

Monit is also integrated into a process-oriented simulation language CSIM. CSIM allows the creation of simulation models based on multiple processes competing for resources. The similarity between parallel processes in PPL and pseudo-parallel processes in CSIM facilitates this combined use of Monit.
Modeling the software architecture of a prototype parallel machine
Authors: Marsan M. Ajmone , Balbo G. , Chiola G. , Conte G.
Published: January 2007

A high-level Petri net model of the software architecture of an experimental MIMD multiprocessor system for Artificial Intelligence applications is derived by direct translation of the code corresponding to the assumed workload. Hardware architectural constraints are then easily added, and formal reduction rules are used to simplify the model, which is then further approximated to obtain a performance model of the system based on generalized stochastic Petri nets. From the latter model it is possible to estimate the optimal multiprogramming level of each processor so as to achieve the maximum performance in terms of overall throughput (number of tasks completed per unit time).
A workload characterization pipeline for models of parallel systems
Authors: Alexander William , Keller Tom W. , Boughter Ellen E.
Published: January 2007

The same application implemented on different systems will necessarily present different workloads to the systems. Characterizations of workloads intended to represent the same application, but input to models of different systems, must also differ in analogous ways. We present a hierarchical method for characterizing a workload at increasing levels of detail such that every characterization at a lower level still accurately represents the workload at higher levels.

We discuss our experience in using the method to feed the same application through a workload characterization “pipeline” to two different models of two different systems, a conventional relational database system and a logic-based distributed database system. We have developed programs that partially automate the characterization changes that are required when the system to be modeled changes.
Delay analysis of a window tree conflict resolution algorithm in a local area network environment
Authors: Polyzos George C. , Molle Mart L.
Published: January 2007

Expressions are found for the throughput and delay performance of a Tree Conflict Resolution Algorithm that is used in a Local Area Network with carrier sensing (and possibly also collision detection). We assume that Massey's constant size window algorithm is used to control access to the channel, and that the resulting conflicts (if any) are resolved using a Capetanakis-like preorder traversal tree algorithm with
d
-ary splitting. We develop and solve functional equations for various performance metrics of the system and apply the “Moving Server” technique to calculate the main component of the delay. Our results compare very favorably with those for CSMA protocols, which are commonly used in Local Area Networks that support sensing.
Phrase processing methods for Japanese text retrieval
Authors: Kando Noriko , Kageura Kyo , Yoshioka Masaharu , Oyama Keizo
Published: January 2007

This paper examines the effectiveness of different phrase identification and weighting methods for Japanese text retrieval in an operational information retrieval (IR) system, called
NACSIS-IR
. Based on our previous experiments, we used character-based indexing with positional information and word-or phrase-based query processing, which allowed us to implement sophisticated linguistic analysis on large-scale databases while maintaining adequate efficiency. The results of retrieval experiments on a large-scale Japanese test collection showed that the combination of enhanced phrase identification using patterns defined over part-of-speech tags and our algorithms
Phrase2
and
Phrase5
made a significant positive contribution to retrieval effectiveness. The paper also discusses indexing and phrase processing of Japanese or East Asian languages.
Web proxy caching
Authors: Cáceres Ramón , Douglis Fred , Feldmann Anja , Glass Gideon , Rabinovich Michael
Published: January 2007

Much work in the analysis of proxy caching has focused on high-level metrics such as hit rates, and has approximated actual reference patterns by ignoring exceptional cases such as connection aborts. Several of these low-level details have a strong impact on performance, particularly in heterogeneous bandwidth environments such as modem pools connected to faster networks. Trace-driven simulation of the modem pool of a large ISP suggests that "cookies" dramatically affect the cachability of resources; wasted bandwidth due to aborted connections can more than offset the savings from cached documents; and using a proxy to keep from repeatedly opening new TCP connections can reduce latency more than simply caching data.
Structural analysis of verbal data
Authors: Bailey Wayne A. , Kay Edwin J.
Published: January 2007

Current methods of analyzing verbal reports (Protocol Analysis) from human-computer interactions fall short of their potential. Although there are systematic methods for collecting complete and objective verbal reports applicable to a broad range of problem-solving tasks, currently available analyses of verbal reports are ad hoc and apply only to well constrained tasks. Structural Analysis is a systematic method, currently under development, for analyzing real-world tasks involving human-computer interaction. Starting with a rule that assigns utterances to two dichotomous categories related to a behavior of interest, rules are generated that expose the goal building and evaluation underlying that behavior. The resulting data yield time distributions that characterize subjects' goal-directed behavior and that allow comparisons among tasks or among subjects.
Evolution of an organizational interface
Authors: Clement Andrew , Gotlieb C. C.
Published: January 2007

This paper describes how the work organization and computer system of the New Business Department at a large life insurance firm have interacted and evolved over time. The dynamics of interaction are explained largely in terms of the economic incentive to reduce the length of transaction processing chains and the more political goal of extending managerial control. It is argued that examining the interaction of organizations and computer systems Can contribute to a better theoretical understanding of the development of large computer systems and offer guidance to designers of user-computer interfaces. A graphical technique for depicting organizational interfaces is presented.
Predicting the time to recall computer command abbreviations
Authors: John Bonnie E. , Newell Allen
Published: January 2007

A GOMS theory of stimulus-response compatibility is shown to predict response-time performance on a command/abbreviation encoding task. Working with parameters that were set by an earlier study and which have rational, task-meaningful interpretations as mapping, motor, perception and retrieval operators, zero-parameter predictions were made that fit the observed performance with r
2
= 0.776 (p<0.05). The reasonableness of the parameters, the algorithms used to generate the predictions, and the weighting assumption used to combine algorithms into a single prediction are discussed.
The elusive goal of workload characterization
Authors: Downey Allen B. , Feitelson Dror G.
Published: January 2007

The study and design of computer systems requires good models of the workload to which these systems are subjected. Until recently, the data necessary to build these models---observations from production installations---were not available, especially for parallel computers. Instead, most models were based on assumptions and mathematical attributes that facilitate analysis. Recently a number of supercomputer sites have made accounting data available that make it possible to build realistic workload models. It is not clear, however, how to generalize from specific observations to an abstract model of the workload. This paper presents observations of workloads from several parallel supercomputers and discusses modeling issues that have caused problems for researchers in this area.
War on the workspace!
Authors: Shaw Edward J.
Published: January 2007

We describe a relatively simple but effective set of techniques that is used to support a commercial computer application maintained by several developers and used by several thousand businesses. The techniques allow for complete control over a system that is in a continuous state of maintenance and enhancement. All functions and data are controlled by a proprietary relational database written in APL with almost no reliance on the contents of the workspace. The workspace contains only the few functions required to initialize the application and utility functions that are there simply to avoid defining them at load time. All other functions are defined as they are needed by specific user commands and erased thereafter.
Performance analysis of multiprocessor cache consistency protocols using generalized timed Petri nets
Authors: Vernon Mary K. , Holliday Mark A.
Published: January 2007

We use an exact analytical technique, based on Generalized Timed Petri Nets (GTPNs), to study the performance of
shared bus cache consistency protocols
for multiprocessors. We develop a general framework within which the key characteristics of the Write-Once protocol and four enhancements that have been combined in various ways in the literature can be identified and evaluated. We then quantitatively assess the performance gains for each of the four enhancements. We consider three levels of data sharing in our workload models. One of the enhancements substantially improves system performance in all cases. Two enhancements are shown to have negligible effect over the range of workloads analyzed. The fourth enhancement shows a small improvement for low levels of sharing, but shows more substantial improvement as sharing is increased, if we assume a “good access pattern”. The effects of two architectural parameters, the
blocksize and the main memory cycle time
are also considered.
Load-balancing heuristics and process behavior
Authors: Leland Will , Ott Teunis J.
Published: January 2007

Dynamic load balancing in a system of loosely-coupled homogeneous processors may employ both judicious initial placement of processes and migration of existing processes to processors with fewer resident processes. In order to predict the possible benefits of these dynamic assignment techniques, we analyzed the behavior (CPU, disk, and memory use) of 9.5 million Unix* processes during normal use. The observed process behavior was then used to drive simulation studies of particular dynamic assignment heuristics.

Let
F
(·) be the probability distribution of the amount of CPU time used by an arbitrary process. In the environment studied we found:

(1-
F
(
x
)) ≉
rx

-
c

, 1.05<
c
<1.25.

F
(·) is far enough from exponential to make exponential models of little use.

With a foreground-background process scheduling policy in each processor, simple heuristics for initial placement and processor migration can significantly improve the response ratios of processes that demand exceptional amounts of CPU, without harming the response ratios of ordinary processes.
An efficient algorithm for semi-homogeneous queueing network models
Authors: Conway A. E. , Georganas N. D.
Published: January 2007

The class of product-form semi-homogeneous queueing networks is introduced as a generalization of the class of homogeneous networks, which has been considered by Balbo et al for the performance modeling of local area networks. In semi-homogeneous networks, the relative traffic intensity at the various shared resources may depend on the routing chain to which a customer belongs. We develop an efficient algorithm for the exact analysis of this class of networks. It is based on the equations which form the foundation of RECAL, a general purpose exact algorithm for multiple-chain closed queueing networks. The complexity of the algorithm is shown to be of order less than exponential in (P-1)
1/2
, where P is the number of processors (workstations) in the network. It is therefore, in general, more efficient than a direct application of either convolution, MVA or RECAL to the class of semi-homogeneous queueing networks. The algorithm presented here may be situated between the algorithms of Balbo et al and the general purpose algorithms, both in terms of its generality and efficiency.
Optimal multiplexing of heterogeneous traffic with hard constraint
Authors: Nain Philippe , Ross Keith
Published: January 2007

Considered are optimal dynamic policies for multiplexing
Κ
+ 1 heterogeneous traffic types onto a single communication channel. The packet types arrive to the channel according to independent Poisson processes. The service requirements are exponential with type dependent means. The optimization criterion is to minimize a linear combination of the average delays for packet types 1 to
Κ
, while simultaneously subjecting the average delay of type-0 packets to a hard constraint. The optimal multiplexing policy is shown to be a randomized modification of the “
μc
rule”. The optimization problem is thereby reduced to a problem of finding the optimal randomization factor; an algorithm, which can be implemented in real time, is given to do this for two particular cases.
Cycle time properties of the FDDI token ring protocol (extended abstract)
Authors: Sevcik Kenneth , Johnson Marjory J.
Published: January 2007

Communication technology now makes it possible to support high data transmission rates at relatively low cost. In particular, optical fiber can be used as the medium in local area networks with data rates in the range of 100 megabits per second. Unfortunately, local area network topologies and communication protocols that work well with lower speed media are not necessarily appropriate when the data transmission rate is scaled up by approximately an order of magnitude. Recognizing this fact, an ANSI sub-committee (ANSIX3T9) has been working for the past two years on a proposed standard for a token ring protocol tailored to a transmission medium with transmission rate in the 100 megabits per second range. The protocol is referred to as the FDDI (Fiber Distributed Data Interface) Token Ring protocol. The proposal for the standard is now quite mature and nearly stable.
Approximate disaggregation and performance bounds for queueing networks with multiple-server stations
Authors: Dallery Yves , Suri Rajan
Published: January 2007

We introduce the concept of approximate disaggregation which enables us to replace a station by a subnetwork, i.e. a set of stations, such that the performance of the derived network is close to the performance of the initial network. We use this concept to disaggregate any multiple-server station into a set single-server stations. Using two different disaggregations, we are able to bound the performance of the initial network by the performance of a “lower” and an “upper” network each consisting of single-server stations, whose performance can in turn be bounded by the Balanced Job Bounds (or other known bounds). Several examples show the useful information provided by these bounds at a very low cost: for
Κ
stations and
Ν
customers, the computational complexity here is
Ο
(
Κ
) which is significantly less than the
Ο
(
ΚΝ
2
) operations required for exact solution. Indeed, despite the multiple server stations, the computational complexity of our bounds is the same as that of Balanced Job Bounds.
A probabilistic analysis of a database system
Authors: Massey William A.
Published: January 2007

In Gray, Homan, Obermarck, and Korth [GHOK], the authors give many conjectures based on simulation for the probabilistic analysis of transaction lock-waits and transaction deadlocks. In this paper, we introduce a probabilistic model to explain their observations.
Performance evaluation of multiversion with the Oracle synchronization
Authors: Witkowski Andrew
Published: January 2007

In this paper we present a new analytical model for performance measurements of timestamp driven databases. The model is based on two-dimensional Poisson processes where one coordinate represents the real arrival time and the other the timestamp of an arriving messages. The notion of
preemption
is defined which serves as a model for synchronization. Preemption naturally implies such performance measures as response time and amount of abortion in the system. The concept of oracle is introduced which allows evaluation of a lower bound on the synchronization cost. Preemption and the oracle are then used to evaluate performance of the Multiversion synchronization. We present the distribution and the expectation of the synchronization cost. The analysis is then applied to a database with exponential communication delays (α) and the intensity of transaction λ. It is shown that for Multiversion, this cost depends linearly on l/α and logarithmically on λ.
Measurement and analysis of locality phases in file referencing behaviour
Authors: Majumdar Shikharesh , Bunt Richard B.
Published: January 2007

Recent research has demonstrated the existence of locality in short-term file referencing behaviour. A detailed study of the dynamic characteristics of file referencing is presented in this paper. The concept of Bounded Locality Intervals from the field of program behaviour has been used to model the locality phases of file referencing behaviour. The model is found to be powerful both from a descriptive point of view and from the perspective of understanding the performance implications of locality properties of file referencing behaviour on file system management.
A maximum entropy queue length distribution for the G/G/1 finite capacity queue
Authors: Kouvatsos Demetres D.
Published: January 2007

A new “hybrid” analytic framework, based on the principle of maximum entropy, is used to approximate the queue length distribution of a G/G/1 finite buffer queue. Robust recursive relations are derived and asymptotic connections to the infinite capacity queue are established. Furthermore, “equivalence” principles are applied to analyse two-stage cyclic queues with general service times and favourable comparisons with global balance solutions are made. Numerical examples provide useful information on how critically system behaviour is affected by the distributional form of interarrival and service patterns. It is shown that the maximum entropy solution predicts the bottleneck “anomaly” and also it defines bounds on system performance. Comments on the implication of the work to the analysis and aggregation of computer systems are included.
Workload characterization (tutorial)
Authors: Ferrari Domenico
Published: January 2007

Workload characterization is that branch of performance evaluation which concerns itself with the measurement and modeling of the workloads to be processed by the system being evaluated. Since all performance indices of interest are workload-dependent, there is no evaluation study that does not require the characterization of one or more workloads. In spite of the importance of the problem, our knowledge in this area leaves much to be desired.

The tutorial addresses the main issues, both resolved and unresolved, in the field, and surveys the major approaches that have been proposed and are in use. Modern methods for designing executable artificial workloads, as well as the applications of these techniques in system procurement, system tuning, and capacity planning are emphasized.
On the availability of a distributed computer system with failing components
Authors: Gelenbe Erol , Finkel David , Tripathi Satish K.
Published: January 2007

We present a model for distributed systems with failing components. Each node may fail and during its recovery the load is distributed to other nodes that are operational. The model assumes periodic checkpointing for error recovery and testing of the status of other nodes for the distribution of load.

We consider the availability of a node, which is the proportion of time a node is available for processing, as the performance measure. A methodology for optimizing the availability of a node with respect to the checkpointing and testing intervals is given. A decomposition approach that uses the steady-state flow balance condition to estimate the load at a node is proposed. Numerical examples are presented to demonstrate the usefulness of the technique. For the case in which all nodes are identical, closed form solutions are obtained.
RECAL—a new efficient algorithm for the exact analysis of multiple-chain closed queueing networks (abstract)
Authors: Conway A. E. , Georganas N. D.
Published: January 2007

RECAL, a Recursion by Chain Algorithm for computing the mean performance measures of product-form multiple-chain closed queueing networks, is presented. It is based on a new recursive expression which relates the normalization constant of a network with r closed routing chains to those of a set of networks having (r-l) chains. It relies on the artifice of breaking down each chain into constituent sub-chains that each have a population of one. The time and space requirements of the algorithm are shown to be polynomial in the number of chains. When the network contains many routing chains the proposed algorithm is substantially more efficient than the convolution or mean value analysis algorithms. The algorithm therefore extends the range of queueing networks which can be analyzed efficiently by exact means. A numerical example is given.
Modeling priority schemes
Authors: Balbo G. , Bruell S. C. , Ghanta S.
Published: January 2007

We develop Generalized Stochastic Petri Net models for several priority queueing disciplines. The building blocks of these models are explained and many variants are easily derivable from them. We then combine these building blocks with product-form queueing network models. Numerical results are provided that illustrate the effectiveness of the method.
The local disk controller
Authors: Houtekamer Gilbert E.
Published: January 2007

The performance of the I/O subsystem in the 370-XA architecture has been improved considerably with the introduction of the new channel subsystem, as compared to the System/370 architecture. The emphasis in the 370-XA architecture is on reducing the CPU load associated with I/O, and on reducing the congestion in multi-CPU, shared systems, by redesigning the channel system.

In this paper we will show that a reallocation of the control unit logic may triple the channel subsystem's capacity, while still using the same disk drives. The performance gain is achieved by adding control-unit like intelligence and local buffer memory to each disk drive, creating a Local Disk Controller (LDC), and thus eliminating the performance degradation caused by reconnect failures at a high channel utilization. The system proposed remains fully software compatible with the current 370-XA architecture. A simpler approach, requiring only a slight modification to the disk drives, is also discussed.
On defining application-specific high-level array operations by means of shape-invariant programming facilities
Authors: Scholz Sven-Bodo
Published: January 2007

Most of the existing high-level array-processing languages support a fixed set of pre-defined array
operations
and a few higher-order functions for constructing new array operations from existing ones. In this paper, we discuss a more general approach made feasible by S
AC
(for Single Assignement C), a functional variant of C.S
AC
provides a meta-level language construct called
WITH
-loop which may be considered a sophisticated variant of the
FORALL
-loops in H
PF
or of array comprehensions in functional languages. It allows for the element-wise specification of high-level operations on arrays of any dimensionality: any set of high-level array operations can be specified by means of
WITH
-loops and be made available in a library. This not only improves the flexibility of specifications, but also simplifies the compilation process.By means of a few examples it is shown that the high-level operations that are typically available in array processing languages such as A
PL
or F
ORTRAN
90 can be easily specified as
WITH
-loops in S
AC
. Furthermore, we briefly outline the most important optimization techniques used in the current S
AC
compiler for achieving efficiently executable code.The paper finally presents a performance comparison between a high-level specification for the multigrid relaxation kernel of the NAS benchmarks in S
AC
on the one hand and low-level specifications in S
ISAL
and in F
ORTRAN
77 on the other hand. It shows that the S
AC
implementation, despite its higher level of abstraction, is competitive with the other two both in terms of program runtimes and memory consumption.
Reducing computational complexity with array predicates
Authors: Bernecky Robert
Published: January 2007

This article describes how
array predicates
were used to reduce the computational complexity of four APL primitive functions when one of their arguments is a permutation vector. The search primitives,
indexof
and set membership, and the sorting
primitives,
upgrade and downgrade, execute in linear time on such arguments. Our contribution, a method for static determination of array properties, lets us generate code that is optimized for special cases of primitives. Our approach eliminates runtime checks which would otherwise slow down the execution of all cases of the effected primitives. We use the same analysis technique to reduce the type complexity of certain array primitives.
Simplifying array processing languages
Authors: Holmes Neville
Published: January 2007

A language like APL was a masterpiece of simplification when seen through the eyes of a computer user of the seventies. The virtues of simplicity are usually held to be many.This paper firstly discusses simplicity in general, reviews some of the writing on simplicity coming from the computing world, and briefly construes the development of APL, and the later J, as being essentially efforts in simplification. Possibilities for further simplification are then canvassed.Firstly, simplification of the usually accepted but unfortunate naming conventions adopted by array processing languages is proposed. Secondly, simplification of the arithmetic is very briefly outlined, more detailed treatment of this topic being available elsewhere. Thirdly, syntactic means for having all functions and operations dyadic are treated, and the advantages of adopting such means evaluated. Fourthly, the possibilities for a newly distinctive kind of function (called extractions) are described. These are considered as a kind of systematic renaming to supply arguments to functions. Fifthly, and in the context of J's simplifications, the need for hyperoperators is asserted. Finally, the nature of interpreters for array processing languages is reviewed, and suggestions made for facilities to be provided by such interpreters to aid the process of developing array processing code.
Object oriented spatial positioning systems
Authors: Kádár István , Papp Erik
Published: January 2007

The domains of a structured spatial positioning systems are extended to a single 2D or 3D boundary rectangle (MBR - Minimal axes-parallel Boundary Rectangle) domain. We try to encapsulate the domains strictly for the inside and/or the boundary (surface) of the object during our attempts. In ease of such domains it is impossible to use traditional coordinates because of boundary irregularity. Therefore we applied 2D and 3D versions of subrange type data structure for spatial indexing, which are well known in dynamic program languages. The two important methods of combinatorics namely
enumeration
and
ranking
were also applied to the spatial index used by us, derived from rank which should not be confused with concept of 'rank' used in the APL and J programming languages. During development we had to partly modify and extend the traditional concepts of circumference and area, as well surface and volume. With the creation of nested superclasses and subclasses, it is possible for positioning systems belonging to different classes to inherit transformation parameters (translation, orientation, etc.). Polymorphism allows development of hidden virtual systems which may perform transformations between any kind of coordinates and linear indices. Thus our positioning systems can be rightly called object oriented including every advantage and disadvantage of it.
AxE
Authors: Pedullá Francesco , Salerno Giorgio
Published: January 2007

This paper presents AxE, a package designed to help transport networks analysis and design.AxE was born in 1995. It stems from the experience of Prof. G. Salerno in both teaching transportation theory at an Italian University and consulting with large institutions and companies on transportation modeling and planning. In his work Prof. Salerno has been extensively using APL for years. He regularly teaches his students an introduction to APL (using IBM's TryAPL2) and uses APL to code the major algorithms related to transportation theory. He also uses APL for his professional work as a consultant and to perform management tasks.The implementation of AxE has been a joint effort led by Prof. Salerno with help from other professionals (namely, the speaker, Francesco Pedulla and Michele Marrone, then both at IBM, and Marco Pascucci, a freelance consultant). The AxE package currently runs on Apple Macintosh systems and has been coded entirely using APL.68000. A porting to Dyalog APL for MS Windows95 currently is under evaluation.First, the article briefly presents the package and its features. The body of the article is devoted to a discussion of the advantages (and, sometimes, limitations) that the use of APL in general and APL.68000 in particular has provided in the following areas during the design and implementation phases of AxE:1. algorithm coding;2. user interface generation;3. management of a relatively large and complex application.AxE is currently available from Prof. G. Salerno (mc2800@mclink.it). Francesco Pedulla can be contacted at md3547@mclink.it.AxE is currently available from Prof. G. Salerno (mc2800@mclink.it). Francesco Pedulla can be contacted at md3547@mclink.it.
A Web-interfaced array-based mathematics course
Authors: Spunde Walter , de Voil Peter
Published: January 2007

The fascinating, often complex, often context-sensitive, classical mathematical notation presents a host of problems for machine interpretation. For those who forsee an educational environment in which interactive course material is delivered world-wide across the Web, the demand of universities (the accrediting agencies) for mastery of the classical notation is somewhat frustrating. Computer-based notations, on the other hand, can also sometimes be clumsy, confusing, inelegant and aesthetically displeasing. A solution to this impasse might seem to be yet some way off. Nevertheless, as students, rather than instructors, increasingly come to determine the choice of purchase in educational products, it might prove to be possible to acquire mastery of classical notation by routes other than the traditional ones.The USQ web-interfaced array-based first course in mathematics provides a rather different approach to the introduction of calculus. Because it is numerically based, the course largely avoids classical notation and lends itself well to distribution over the Internet. Linking the computations done in the course activities with classical notation is left to printed materials.We will briefly outline the numerical approach to the teaching of calculus, and describe how the program is delivered over the Web.
APL design of graphic displays for motivation in distance education
Authors: Surkan Alvin J.
Published: January 2007

APL is used in the experimental design of graphic displays to be applied in real-time, on-line education. These graphic displays are to be integrated in instructional dialogs. Our aim is to discover displays that will motivate students while they take computer mediated and distance learning courses. During the learning process, it is especially important for a student to receive feedback about his/her progress, continually and within a few tens of seconds of the most recent interaction. This feedback may indicate student performance relative to the recent past and also relative to their peers who have interacted with the same learning items. Compact and easy-to-interpret graphical or quantitative (partly numeric) displays of student progress are designed as character arrays. The rules for constructing these arrays are described conveniently in APL functions. Such functions specify a template each display and establish design correctness. The functions also allow flexible testing that reveals how easy it is to understand each display.
Optimization with dynamic functions
Authors: Mansour Stephen M.
Published: January 2007

Many optimization methods are iterative in nature and require users to specify constraints and objectives. The normal way to handle this type of problem would be to create a loop with an execute statement inside the body of the loop. The loop is necessary because of the iterative nature of the algorithm and the execute statement is necessary because the objective function is user-defined."Execute" can be costly inside a loop. While there are existing ways to remove "execute" from the loop, they are awkward. However, dynamic functions can be built ahead of time and called inside the loop. Defined operators allow an arbitrary optimization function to be passed to the looping function.The method of simulated annealing can deal with large-scale optimization problems without getting trapped in local minima. Constraints can be treated as objectives with a high penalty for violations. Hence we can eliminate constraints and deal only with objectives. A series of objectives is combined into a single objective function. Since the objectives are defined by the user, a dynamic function is created. The goal is to reduce the result of the dynamic function to zero (negative values are not permitted). The function is called iteratively until a specific tolerance is reached.This paper will use an example from the mortgage industry to demonstrate the use of dynamic functions in iterative optimization methods.
Neural network for partitionable variational inequalities
Authors: Rotondo Giulia
Published: January 2007

Often in recent times industries have asked mathematicians to determine their "true" utility functions directly from the available data about used resources and about the corresponding profits in order to optimize the latter with respect to the former. The possibility of determining the utility function directly from the data is very important because in this way the exact situation of the company is described. Moreover, the biggest companies divide their investments into several activities. The optimization of their utility function can lead to problems that involve separable or partitionable functions. Two-layered feed-forward neural networks are able to approximate any separable function while fitting the data mantaining the separable structure with the desired approximation error. Thus the theory of partitionable variational inequalities can be used in order to find the optimum of the utility function, subject to some constraints. The presence of the partitionable structure is important because it simplifies the resolution algorithms and makes them more efficient. Moreover, with stronger assumptions about the function, the above results can be generalized to a larger class of utility functions: one problem of dimension n can be split into n problems of dimension one.
The computer for the 21
st
century
Authors: Weiser Mark
Published: January 2007

Specialized elements of hardware and software, connected by wires, radio waves and infrared, will be so ubiquitous that no one will notice their presence.
Analysis of a very large web search engine query log
Authors: Silverstein Craig , Marais Hannes , Henzinger Monika , Moricz Michael
Published: January 2007

In this paper we present an analysis of an AltaVista Search Engine query log consisting of approximately 1 billion entries for search requests over a period of six weeks. This represents almost 285 million user sessions, each an attempt to fill a single information need. We present an analysis of individual queries, query duplication, and query sessions. We also present results of a correlation analysis of the log entries, studying the interaction of terms within queries. Our data supports the conjecture that web users differ significantly from the user assumed in the standard information retrieval literature. Specifically, we show that web users type in short queries, mostly look at the first 10 results only, and seldom modify the query. This suggests that traditional information retrieval techniques may not work well for answering web search requests. The correlation analysis showed that the most highly correlated items are constituents of phrases. This result indicates it may be useful for search engines to consider search terms as parts of phrases even if the user did not explicitly specify them as such.
BMIR-J2
Authors: Sakai Tetsuya , Kitani Tsuyoshi , Ogawa Yasushi , Ishikawa Tetsuya , Kimoto Haruo , Keshi Ikuo , Toyoura Jun , Fukushima Toshikazu , Matsui Kunio , Ueda Yoshihiro , Tokunaga Takenobu , Tsuruoka Hiroshi , Nakawatase Hidekazu , Agata Teru , Kando Noriko
Published: January 2007

BMIR-J2 is the first complete test collection generally available for evaluating Japanese information retrieval systems. BMIR-J2 features include a novel division of search requests based on various functions required to perform successful retrieval. BMIR-J2 and its smaller predecessor BMIR-J1 were constructed by a volunteer-based working group under the Information Processing Society of Japan. We hope that BMIR-J2 will come into wide use and that it will foster the development of Japanese IR systems.
Workload characterization of a Web proxy in a cable modem environment
Authors: Arlitt Martin , Friedrich Rich , Jin Tai
Published: January 2007

This paper presents a detailed workload characterization study of a World-Wide Web proxy. Measurements from a proxy within an Internet Service Provider (ISP) environment were collected. This ISP allows clients to access the Web using high-speed cable modems rather than traditional dialup modems. By examining this site we are able to evaluate the effects that cable modems have on proxy workloads.This paper focuses on workload characteristics such as file type distribution, file size distribution, file referencing behaviour and turnover in the active set of files. We find that when presented with faster access speeds users are willing to download extremely large files. A widespread increase in the transfer of these large files would have a significant impact on the Web. This behaviour increases the importance of caching for ensuring the scalability of the Web.
A discussion of cybersickness in virtual environments
Authors: LaViola Joseph J.
Published: January 2007

An important and troublesome problem with current virtual environment (VE) technology is the tendency for some users to exhibit symptoms that parallel symptoms of classical motion sickness both during and after the VE experience. This type of sickness, cybersickness, is distinct from motion sickness in that the user is often stationary but has a compelling sense of self motion through moving visual imagery. Unfortunately, there are many factors that can cause cybersickness and there is no foolproof method for eliminating the problem. In this paper, I discuss a number of the primary factors that contribute to the cause of cybersickness, describe three conflicting cybersickness theories that have been postulated, and discuss some possible methods for reducing cybersickness in VEs.