bluuebunny/crossref_metadata_2025 huggingface dataset:
Using visual tags to bypass Bluetooth device discovery
Authors: Scott David , Sharp Richard , Madhavapeddy Anil , Upton Eben
Published: January 2007

One factor that has limited the use of Bluetooth as a networking technology for publicly accessible mobile services is the way in which it handles Device Discovery. Establishing a Bluetooth connection between two devices that have not seen each other before is slow and, from a usability perspective, often awkward. In this paper we present the implementation of an end-to-end Bluetooth-based mobile service framework designed specifically to address this issue. Rather than using the standard Bluetooth Device Discovery model to detect nearby mobile services, our system relies on machine-readable visual tags for out-of-band device and service selection. Our work is motivated by the recent proliferation of cameraphones and PDAs with built-in cameras. We have implemented the described framework completely for Nokia Series 60 cameraphones and demonstrated that our tag-based connection-establishment technique (i) offers
order of magnitude
time improvements over the standard Bluetooth Device Discovery model; and (ii) is significantly easier to use in a variety of realistic scenarios. Our implementation is available for free download.
The role of time in information processing
Authors: Bolour A. , Anderson T. L. , Dekeyser L. J. , Wong H. K. T.
Published: January 2007

Numerous researchers in a handful of disciplines have been concerned, in recent years, with the special role (or roles) that time seems to play in information processing. Designers of computerized information systems have had to deal with the fact that when an information item becomes outdated, it need not be forgotten. Researchers in artificial intelligence have pointed to the need for a realistic world model to include representations not only for snapshot descriptions of the real world, but also for histories, or the evolution of such descriptions over time. Many logicians have regarded classical logic as an awkward tool for capturing the relationships and the meaning of statements involving temporal reference, and have proposed special "temporal logics" for this purpose. Finally, the analysis of tensed statements in natural language is a principal concern of researchers in linguistics.
Playing Mastermind more logically or writing Prolog more efficiently
Authors: Powers David M. W.
Published: January 2007

In the last few issues of SIGART there have appeared (#82, 83 & 85) three articles on Mastermind programmes, the latest of which, by Ehud Shapiro [1], presents a PROLOG version of the best known algorithm for the oldest form of the game-Bull-cow. This paper presents some improvements to this programme and uses it as an example in making some general points about PROLOG. Shapiro's programme is simple and demonstrates the power of PROLOG for implementing a quick solution using a well understood algorithm. My comments concern some changes to assist readability, to improve generality, and to develop a different, more efficient derivative of the algorithm.
Review of "From Images to Surfaces: A Computational Study of the Human Early Visual System by William Eric Leifur Grimson"; MIT Press, 1981
Authors: Blicher Peter
Published: January 2007

This book describes what must be today's most widely known stereoscopic correspondence system --- one based on the Marr-Poggio theory of stereopsis ([Marr 1977]).
Directions for AI in the eighties
Authors: Hart Peter E.
Published: January 2007

The 1980's will be an exciting decade for artificial intelligence, one in which we can expect to see considerable progress on scientific questions, widespread application of Al techniques to problems of practical significance, and major changes in the social, political and economic structure of the field. In this article, I will attempt to identify some of the commercial, scientific and sociological considerations that I think will be important in coming years. In particular, I will introduce the metaphor of deep versus surface systems, and pose some challenges arising from the recognition of this distinction.
Machine learning research
Authors: Carbonell Jaime G.
Published: January 2007

META is a Natural Language learning project whose specific objective is to acquire new word definitions and new concepts from contextual information in interactive dialogues. It is an instance of a learning-from-examples method, with a difference: learning proceeds in a reactive, knowledge-rich environment. Our initial research indicates that the interactive nature of the environment ought to be a crucial component of any general learning system. In brief, our investigations have led us to formulate the following hypotheses, which we intend to test and pursue further in the immediate future:1. Learning requires progressive refinement -- It is unreasonable to expect that a computer system (or a human) learn a concept or a skill without error, in its full embellished form, in one brief learning session. It must undergo a sequence of progressive test-and-update stages. In other words, a concept can be learned by first inducing a rough approximation of its final form and successively correcting this approximation with more accurate, more detailed information.2. Interaction with a reactive environment -- Interaction is the engine that drives learning processes. A learner must be able to direct queries to its teacher or perform experiments on its environment. It must be able test out new concepts and skills as it learns them.3. Reasoning by Analogy -- The more a system can learn by relating new concepts to old, by modifying existing concepts, or using chunks of existing concepts as building blocks, the more robust and general its learning mechanisms will be.
Correction to "A Formal Basis for the Heuristic Determination of Minimum Cost Paths"
Authors: Hart Peter E. , Nilsson Nils J. , Raphael Bertram
Published: January 2007

Our paper on the use of heuristic information in graph searching defined a path-finding algorithm, A*, and proved that it had two important properties. In the notation of the paper, we proved that if the heuristic function ñ (n) is a lower bound on the true minimal cost from node n to a goal node, then A* is admissible; i.e., it would find a minimal cost path if any path to a goal node existed. Further, we proved that if the heuristic function also satisfied something called the consistency assumption, then A* was optimal; i.e., it expanded no more nodes than any other admissible algorithm A no more informed than A*. These results were summarized in a book by one of us.
Abstraction and refinement in probabilistic systems
Authors: McIver Annabelle , Morgan Carroll
Published: January 2007

We summarise a verification method for probabilistic systems that is based on abstraction and refinement, and extends traditional assertional styles of verification.The approach makes extensive use of the
expectation transformers of pGCL
[17, 16, 13], a compact probabilistic programming language with an associated logic of real-valued functions. Analysis of large systems is made tractable by abstraction which, together with algebraic and logical reasoning, results in strong and general guarantees about probabilistic-system properties.Although our examples are specific (to
pGCL
), our overall goal in this note is to advocate the hierarchical development of probabilistic programs via levels of abstraction, connected by refinement, and to illustrate the proof obligations incurred by such an approach.
PS language definition
Authors: Isaacson Portia
Published: January 2007

The last few years has brought a number of changes to the digital system designer's parts inventory - mainly the addition of large scale integration components such as memories and processors. The solution of an information processing problem involves making the right choices from the variety of components offered and designing the hardware/software interface mechanisms between the components. Methods of simulating this new generation of digital systems are needed as tools. The demands placed on such a tool are great: it must (1) facilitate modeling of a digital system at various levels of architectural detail; (2) allow within a single model two components at quite different specification levels; (3) as a design progresses, allow replacement of models by more detailed models; (4) facilitate modeling of all types of components - hardware, firmware, and software; and (5) have a readily changeable parts library. PS is a tool for simulation of digital systems which meets these demands. In addition PS is designed to case the problem of communicating hardware/software mechanisms between people by automatically producing pictures of a system in its various states. These pictures can be used as a means of describing the system. The models produced by PS are called picture-system models [1, 2, 3].
Effective web crawling
Authors: Castillo Carlos
Published: January 2007

The key factors for the success of the World Wide Web are its large size and the lack of a centralized control over its contents. Both issues are also the most important source of problems for locating information. The Web is a context in which traditional Information Retrieval methods are challenged, and given the volume of the Web and its speed of change, the coverage of modern search engines is relatively small. Moreover, the distribution of quality is very skewed, and interesting pages are scarce in comparison with the rest of the content.
Google
Authors: Hoelzle Urs
Published: January 2007

Search is one of the most important applications used on the internet, but it also poses some of the most interesting challenges in computer science. Providing high-quality search requires understanding across a wide range of computer science disciplines, from lower-level systems issues like computer architecture and distributed systems to applied areas like information retrieval, machine learning, data mining, and user interface design.In this talk I'll share some interesting observations and measurements obtained at Google, and will illustrate the behind-the-scenes pieces of infrastructure (both hardware and software) that we've built in order to extract this information from many terabytes of data.
Low traffic overlay networks with large routing tables
Authors: Tang Chunqiang , Buco Melissa J. , Chang Rong N. , Dwarkadas Sandhya , Luan Laura Z. , So Edward , Ward Christopher
Published: January 2007

The routing tables of Distributed Hash Tables (DHTs) can vary from size
O
(1) to
O
(
n
). Currently, what is lacking is an analytic framework to suggest the optimal routing table size for a given workload. This paper (1) compares DHTs with
O
(1) to
O
(
n
) routing tables and identifies some good design points; and (2) proposes protocols to realize the potential of those good design points.We use total traffic as the uniform metric to compare heterogeneous DHTs and emphasize the balance between maintenance cost and lookup cost. Assuming a node on average processes 1,000 or more lookups during its entire lifetime, our analysis shows that large routing tables actually lead to both low traffic and low lookup hops. These good design points translate into one-hop routing for systems of medium size and two-hop routing for large systems.Existing one-hop or two-hop protocols are based on a hierarchy. We instead demonstrate that it is possible to achieve completely decentralized one-hop or two-hop routing, i.e., without giving up being peer-to-peer. We propose 1h-Calot for one-hop routing and 2h-Calot for two-hop routing. Assuming a moderate lookup rate, compared with DHTs that use
O
(log
n
) routing tables, 1h-Calot and 2h-Calot save traffic by up to 70% while resolving lookups in one or two hops as opposed to
O
(log
n
) hops.
A robust system for accurate real-time summaries of internet traffic
Authors: Keys Ken , Moore David , Estan Cristian
Published: January 2007

Good performance under extreme workloads and isolation between the resource consumption of concurrent jobs are perennial design goals of computer systems ranging from multitasking servers to network routers. In this paper we present a specialized system that computes multiple summaries of IP traffic in real time and achieves robustness and isolation between tasks in a novel way: by automatically adapting the parameters of the summarization algorithms. In traditional systems, anomalous network behavior such as denial of service attacks or worms can overwhelm the memory or CPU, making the system produce meaningless results exactly when measurement is needed most. In contrast, our measurement system reacts by gracefully degrading the accuracy of the affected summaries.The types of summaries we compute are widely used by network administrators monitoring the workloads of their networks: the ports sending the most traffic, the IP addresses sending or receiving the most traffic or opening the most connections, etc. We evaluate and compare many existing algorithmic solutions for computing these summaries, as well as two new solutions we propose here: "flow sample and hold" and "Bloom filter tuple set counting". Compared to previous solutions, these new solutions offer better memory versus accuracy tradeoffs and have more predictable resource consumption. Finally, we evaluate the actual implementation of a complete system that combines the best of these algorithms.
Algorithmic aspects of capacity in wireless networks
Authors: Kumar V. S. Anil , Marathe Madhav V. , Parthasarathy Srinivasan , Srinivasan Aravind
Published: January 2007

This paper considers two inter-related questions: (i) Given a wireless ad-hoc network and a collection of source-destination pairs {(

s
i
,t
i

)}, what is the maximum throughput capacity of the network, i.e. the rate at which data from the sources to their corresponding destinations can be transferred in the network? (ii) Can network protocols be designed that jointly route the packets and schedule transmissions at rates close to the maximum throughput capacity? Much of the earlier work focused on random instances and proved analytical lower and upper bounds on the maximum throughput capacity. Here, in contrast, we consider arbitrary wireless networks. Further, we study the algorithmic aspects of the above questions: the goal is to design provably good algorithms for arbitrary instances. We develop analytical performance evaluation models and distributed algorithms for routing and scheduling which incorporate fairness, energy and dilation (path-length) requirements and provide a unified framework for utilizing the network close to its maximum throughput capacity.Motivated by certain popular wireless protocols used in practice, we also explore "shortest-path like" path selection strategies which maximize the network throughput. The theoretical results naturally suggest an interesting class of congestion aware link metrics which can be directly
plugged into
several existing routing protocols such as AODV, DSR, etc. We complement the theoretical analysis with extensive simulations. The results indicate that routes obtained using our congestion aware link metrics consistently yield higher throughput than hop-count based shortest path metrics.
Nearly insensitive bounds on SMART scheduling
Authors: Wierman Adam , Harchol-Balter Mor , Osogami Takayuki
Published: January 2007

We define the class of SMART scheduling policies. These are policies that bias towards jobs with small remaining service times, jobs with small original sizes, or both, with the motivation of minimizing mean response time and/or mean slowdown. Examples of SMART policies include PSJF, SRPT, and hybrid policies such as RS (which biases according to the product of the remaining size and the original size of a job).For many policies in the SMART class, the mean response time and mean slowdown are not known or have complex representations involving multiple nested integrals, making evaluation difficult. In this work, we prove three main results. First, for all policies in the SMART class, we prove simple upper and lower bounds on mean response time. Second, we show that all policies in the SMART class, surprisingly, have very similar mean response times. Third, we show that the response times of SMART policies are largely insensitive to the variability of the job size distribution. In particular, we focus on the SRPT and PSJF policies and prove insensitive bounds in these cases.
Joint pricing-network design and stochastic traffic engineering to manage demand uncertainty
Authors: Mitra Debasis
Published: January 2007

I will describe two networking models, together with their optimization techniques, that span several time scales. In the longest time scale, where the goal is capacity planning, I will describe the work of Bienstock, Raskina, Saniee and Wang that considers joint pricing and network design of optical transport networks. Technological innovations are yielding sharply decreasing unit costs. There is also empirical evidence that suggests that the elasticity of bandwidth demand to price is high. Integrating these features in a unified profit-maximizing model leads to a large- scale nonlinear optimization problem. In this work, efficient solution techniques are developed to maximize the carrier's net present value with respect to pricing strategies and investment decisions for technology acquisitions. In the work of Mitra and Wang the time scale is shorter, the network infrastructure is fixed, and a model for stochastic traffic engineering is given in which the optimization is with respect to bandwidth provisioning and route selection. Traffic demands are uncertain, and the objective is to maximize a risk-adjusted measure of network revenue that is generated by serving demands. Considerable attention is given to the appropriate measure of risk in the network model. Risk-mitigation strategies are also advanced. The optimization model, which is based on mean-risk analysis, enables a service provider to maximize a combined measure of mean revenue and revenue risk. The conditions under which the optimization problem is an instance of convex programming are obtained. The solution is shown to satisfy the stochastic efficiency criterion asymptotically. The efficient frontier, which is the set of Pareto optimal pairs of mean revenue and revenue risk, is obtained.
Evaluating the impact of simultaneous multithreading on network servers using real hardware
Authors: Ruan Yaoping , Pai Vivek S. , Nahum Erich , Tracey John M.
Published: January 2007

This paper examines the performance of simultaneous multithreading (SMT) for network servers using actual hardware, multiple network server applications, and several workloads. Using three versions of the Intel Xeon processor with Hyper-Threading, we perform macroscopic analysis as well as microarchitectural measurements to understand the origins of the performance bottlenecks for SMT processors in these environments. The results of our evaluation suggest that the current SMT support in the Xeon is application and workload sensitive, and may not yield significant benefits for network servers.In general, we find that enabling SMT on real hardware usually produces only slight performance gains, and can sometimes lead to performance loss. In the uniprocessor case, previous studies appear to have neglected the OS overhead in switching from a uniprocessor kernel to an SMT-enabled kernel. The performance loss associated with such support is comparable to the gains provided by SMT. In the 2-way multiprocessor case, the higher number of memory references from SMT often causes the memory system to become the bottleneck, offsetting any processor utilization gains. This effect is compounded by the growing gap between processor speeds and memory latency. In trying to understand the large gains shown by simulation studies, we find that while the general trends for microarchitectural behavior agree with real hardware, differences in sizing assumptions and performance models yield much more optimistic benefits for SMT than we observe.
On AS-level path inference
Authors: Mao Z. Morley , Qiu Lili , Wang Jia , Zhang Yin
Published: January 2007

The ability to discover the AS-level path between two end-points is valuable for network diagnosis, performance optimization, and reliability enhancement. Virtually all existing techniques and tools for path discovery require direct access to the source. However, the uncooperative nature of the Internet makes it difficult to get direct access to any remote end-point. Path inference becomes challenging when we have no access to the source or the destination. Moveover even when we have access to the source and know the forward path, it is nontrivial to infer the reverse path, since the Internet routing is often asymmetric.In this paper, we explore the feasibility of AS-level path inference without direct access to either end-points. We describe
RouteScope
-a tool for inferring AS-level paths by finding the shortest policy paths in an AS graph obtained from BGP tables collected from multiple vantage points. We identify two main factors that affect the path inference accuracy: the accuracy of AS relationship inference and the ability to determine the first AS hop. To address the issues, we propose two novel techniques: a new AS relation-ship inference algorithm, and a novel scheme to infer the first AS hop by exploiting the TTL information in IP packets. We evaluate the effectiveness of
RouteScope
using both BGP tables and the AS paths collected from public BGP gateways. Our results show that it achieves 70% - 88% accuracy in path inference.
A statistical framework for efficient monitoring of end-to-end network properties
Authors: Chua David , Kolaczyk Eric D. , Crovella Mark
Published: January 2007

Network service providers and customers are often concerned with aggregate performance measures that span multiple network paths. Unfortunately, forming such network-wide measures can be difficult, due to the issues of scale involved. As a result, it is of interest to explore the feasibility of methods that dramatically reduce the number of paths measured in such situations while maintaining acceptable accuracy.In previous work [4] we have proposed a statistical framework for efficiently addressing this problem. The key to our method lies in the observation and exploitation of the fact that network paths show significant redundancy (sharing of common links).We now make three contributions in [3]: (1) we generalize the framework to make it more immediately applicable to network measurements encountered in practice; (2) we demonstrate that the observed path redundancy upon which our method is based is robust to variation in key network conditions and characteristics, including the presence of link failures; and (3) we show how the framework may be applied to address three practical problems of interest to network providers and customers, using data from an operating network.
On the use of anycast in DNS
Authors: Sarat Sandeep , Pappas Vasileios , Terzis Andreas
Published: January 2007

We present the initial results from our evaluation study on the performance implications of anycast in DNS, using four anycast servers deployed at top-level DNS zones. Our results show that 15% to 55% of the queries sent to an anycast group, are answered by the topologically closest server and at least 10% of the queries experience an additional delay in the order of 100ms. While increased availability is one of the supposed advantages of anycast, we found that outages can last up to multiple minutes, mainly due to slow BGP convergence. On the other hand, the number of outages observed was fairly small, suggesting that anycast provides a generally stable service.
Managing memory access latency in packet processing
Authors: Mudigonda Jayaram , Vin Harrick M. , Yavatkar Raj
Published: January 2007

In this study, we refute the popular belief [1,2] that packet processing does not benefit from data-caching. We show that a small data-cache of 8KB can bring down the packet processing time by much as 50-90%, while reducing the off-chip memory bandwidth usage by about 60-95%. We also show that, unlike general-purpose computing, packet processing, due to its memory-intensive nature, cannot rely exclusively on data-caching to eliminate the memory bottleneck completely.
Access and mobility of wireless PDA users
Authors: McNett Marvin , Voelker Geoffrey M.
Published: January 2007

In this paper, we analyze the mobility patterns of users of wireless hand-held PDAs in a campus wireless network using an eleven week trace of wireless network activity. Our study has two goals. First, we characterize the high-level mobility and access patterns of hand-held PDA users and compare these characteristics to previous workload mobility studies focused on laptop users. Second, we develop two wireless network topology models for use in wireless mobility studies: anevolutionary topology modelbased on user proximity and acampus waypoint modelthat serves as a trace-based complement to the random waypoint model. We use our evolutionary topology model as a case study for preliminary evaluation of three ad hoc routing algorithms on the network topologies created by the access and mobility patterns of users of modern wireless PDAs. Based upon the mobility characteristics of our trace-based campus waypoint model, we find that commonly parameterized synthetic mobility models have overly aggressive mobility characteristics for scenarios where user movement is limited to walking. Mobility characteristics based on realistic models can have significant implications for evaluating systems designed for mobility. When evaluated using our evolutionary topology model, for example, popular ad hoc routing protocols were very successful at adapting to user mobility, and user mobility was not a key factor in their performance.
Experience with mean value analysis model for evaluating shared bus, throughput-oriented multiprocessors
Authors: Chiang Mee-Chow , Sohi Gurindar S.
Published: January 2007

We report on our experience with the accuracy of mean value analysis analytical models for evaluating shared bus multiprocessors operating in a throughput-oriented environment. Having developed separate models for multiprocessors with circuit switched and split transaction, pipelined (packet switched) buses, wc compare the results of the models with those of an actual trace-driven simulation for 5,376 multiprocessor configurations.We find that the analytical models are accurate in predicting the individual processor throughputs and partial bus utilizations. For processor throughput, the difference between the results of the models and simulation are within 1% for 75% of the cases and within 3% in 94% of all cases. For partial bus utilization the model results are with 1% of simulation results in 70% of all cases and within 3% in 92% of all cases. The models are less accurate in predicting cache miss latency.
The impact of operating system scheduling policies and synchronization methods of performance of parallel applications
Authors: Gupta Anoop , Tucker Andrew , Urushibara Shigeru
Published: January 2007

Shared-memory multiprocessors are frequently used as compute servers with multiple parallel applications executing at the same time. In such environments, the efficiency of a parallel application can be significantly affected by the operating system scheduling policy. In this paper, we use detailed simulation studies to evaluate the performance of several different scheduling strategies, These include regular priority scheduling, coscheduling or gang scheduling, process control with processor partitioning, handoff scheduling, and affinity-based scheduling. We also explore tradeoffs between the use of busy-waiting and blocking synchronization primitives and their interactions with the scheduling strategies. Since effective use of caches is essential to achieving high performance, a key focus is on the impact of the scheduling strategies on the caching behavior of the applications.Our results show that in situations where the number of processes exceeds the number of processors, regular priority-based scheduling in conjunction with busy-waiting synchronization primitives results in extremely poor processor utilization. In such situations, use of blocking synchronization primitives can significantly improve performance. Process control and gang scheduling strategies are shown to offer the highest performance, and their performance is relatively independent of the synchronization method used. However, for applications that have sizable working sets that fit into the cache, process control performs better than gang scheduling. For the applications considered, the performance gains due to handoff scheduling and processor affinity are shown to be small.
Processor-pool-based scheduling for large-scale NUMA multiprocessors
Authors: Zhou Songnian , Brecht Timothy
Published: January 2007

Large-scale Non-Uniform Memory Access (NUMA) multiprocessors are gaining increased attention due to their potential for achieving high performance through the replication of relatively simple components. Because of the complexity of such systems, scheduling algorithms for parallel applications are crucial in realizing the performance potential of these systems. In particular, scheduling methods must consider the scale of the system, with the increased likelihood of creating bottlenecks, along with the NUMA characteristics of the system, and the benefits to be gained by placing threads close to their code and data.We propose a class of scheduling algorithms based on
processor pools
. A processor pool is a software construct for organizing and managing a large number of processors by dividing them into groups called pools. The parallel threads of a job are run in a single processor pool, unless there are performance advantages for a job to span multiple pools. Several jobs may share one pool. Our simulation experiments show that processor pool-based scheduling may effectively reduce the average job response time. The performance improvements attained by using processor pools increase with the average parallelism of the jobs, the load level of the system, the differentials in memory access costs, and the likelihood of having system bottlenecks. As the system size increasesr, while maintaining the workload composition and intensity, we observed that processor pools can be used to provide significant performance improvements. We therefore conclude that processor pool-based scheduling may be an effective and efficient technique for scalable systems.
Implementing stack simulation for highly-associative memories
Authors: Kim Yul H. , Hill Mark D. , Wood David A.
Published: January 2007

Prior to this work, all implementations of stack simulation [MGS70] required more than linear time to process an address trace. In particular these implementations are often slow for highly-associative memories and traces with poor locality, as can be found in simulations of tile systems. We describe a new implementation of stack simulation where the refrrenced block and its stack distance are found using a hash table rather than by traversing the stack. The key to this implementation is that designers are rarely interested in a continuum of memory sizes, but instead desire metrics for only a discrete set of alternatives (e.g., powers of two). Our experimental evaluation shows the run-time of the new implementation to be linear in address trace length and independent of trace locality. Kim, et al., [KHW91] present the results of this research in more detail.
A static and dynamic workload characterization study of the San Diego Supercomputer center Cray X-MP
Authors: Pasquale Joseph , Bittel Barbara , Kraiman Daniel
Published: January 2007

The San Diego Supercomputer Center is one of four NSF sponsored national supercomputer centers. Up until January of 1990, its workhorse was a Cray X-MP, which served 2700 researchers from 170 institutions, spanning 44 states. In order to better understand how this supercomputer was utilized by its diverse community of users, we undertook a workload characterization study of the Cray X-MP. The goals of our study were twofold. First, we wished to characterize the workload at both the functional and resource levels. The functional level represents the user point of view: what types of programs users are running on the system. The resource level represents the system point of view: how the systems resources (CPU, memory, I/O bandwidth) are being used. Second, we wanted to see how the workload changed over an average weekday. Thus, we conducted a static characterization to understand its global attributes over the entire measurement period, as well as a dynamic workload characterization to understand the time behavior of the workload over a weekday cycle.
Co-arrays in the next Fortran Standard
Authors: Numrich Robert W. , Reid John
Published: January 2007

The WG5 committee, at its meeting in Delft, May 2005, decided to include co-arrays in the next Fortran Standard. A special issue of Fortran Forum in August 1998 explained the feature, but since many of the details of the version adopted by WG5 differ from the 1998 version, it seems appropriate to describe it afresh in a self-contained article.A Fortran program containing co-arrays is interpreted as if it were replicated a fixed number of times and all copies were executed asynchronously. Each copy has its own set of data objects and is called an image. The array syntax of Fortran is extended with additional trailing subscripts in square brackets to give a clear and straightforward representation of access to data on other images.References without square brackets are to local data, so code that can run independently is uncluttered. Only where there are square brackets, or where there is a procedure call and the procedure contains square brackets, is communication between images involved.The additional syntax requires support in the compiler, but it has been designed to be easy to implement and to give the compiler scope both to apply its optimizations within each image and to optimize the communication between images.The extension includes intrinsic procedures to synchronize images, to return the number of images, to return the index of the current image, and to perform collective actions.
On computing with factored rational expressions
Authors: Brown W. S.
Published: January 2007

This paper discusses the extension of an efficient polynomial manipulation system to deal with rational expressions. The proposed system is intended for a wide range of practical computations, including problems involving sparse expressions in many indeterminates.
Sparse polynomial arithmetic
Authors: Johnson Stephen C.
Published: January 2007

Sparse polynomial representations are used in a number of algebraic manipulation systems, including Altran. This paper discusses the arithmetic operations with sparsely represented polynomials; we give particular attention to multiplication and division. We give new algorithms for multiplying two polynomials, with
n
and
m
terms, in time
mn
log
m
;, these algorithms have the property that, in the usual univariate dense case, the algorithm is bounded by
mn.
Division algorithms are discussed which run in comparable time.
Quantifier elimination for real closed fields by cylindrical algebraic decomposition--preliminary report
Authors: Collins George E.
Published: January 2007

Tarski in 1948, [18] published a quantifier elimination method for the elementary theory of real closed fields (which he had discovered in 1930). As noted by Tarski, any quantifier elimination method for this theory also provides a decision method, which enables one to decide whether any sentence of the theory is true or false. Since many important and difficult mathematical problems can be expressed in this theory, any computationally feasible quantifier elimination algorithm would be of utmost significance.
Compact storage for computations involving partitions
Authors: Campbell J. A.
Published: January 2007

If a symbolic problem is sufficiently respectable or well-behaved, it may be possible to compute the solution in a purely numerical language, in terms of arrays of powers, coefficients and numerical codes or labels. The obvious example of good behaviour is the problem in which input, intermediate results and output are all known to be sums of no more than N terms of the form c
i
T
i
, where all symbols T
i
are also known in advance and only coefficients c
i
remain to be determined. The example is "obvious" because the size of storage for intermediate results is fixed.
A note on the complexity of algebraic differentiation
Authors: Caviness B. F. , Epstein H. I.
Published: January 2007

It is a well-known empirical result that differentiation, especially higher order differentiation, of simple expressions can lead to long and complex expressions. In this paper we give some theoretical results that help to explain this phenomenon. In particular we show that in certain representations there exist expressions whose representations require σ(n) space but whose (k+1)-th order derivatives require σ(n(n+k-1/k)) space and hence require at least σ(n(n+k-1/k)) time to compute.
Is a LISP machine different from a fortran machine?
Authors: Fateman Richard J.
Published: January 2007

Over the past ten years or more a question repeatedly asked of algebraic manipulation buffs is "Can you give me a deck to load on my computer center machine?" When the machine is a CDC 6600, 7600, or similar "number cruncher," the answer I give is a conditional "yes." There are a number of systems (SYMBAL, SCHOONSCHIP, ALTRAN, SAC-I, to name a few) which run on these machines; but no, the most interesting of the interactive general systems (I admit my biases: MACSYMA, SCRATCHPAD, REDUCE-2) do not run on these machines. I add my opinion that a software conversion effort to produce a MACSYMA (the most ambitious of the systems) for a CDC 7600 would be money wasted: one can more cheaply buy appropriate hardware than re-program.
Problem #8
Authors: Fitch John
Published: January 2007

This problem was brought to my attention by Professor Violet Cane of Manchester University, and derives from correlated random walks, in statistics. It turned out to be more difficult than I thought, causing difficulties to a number of algebra systems.
Computing real zeros of polynomials with SAC-1
Authors: Verbaeten P.
Published: January 2007

SAC-1 contains a subsystem for computing real zeros of univariate polynomials over the integers. Here we present an engineering approach to the improvement of this subsystem. We will show that a considerable amount of computing time can be saved by replacing just one subroutine.
Son of seminumerical algorithms
Authors: Knuth D. E.
Published: January 2007

During the last fifteen months or so, I have been preparing the second edition of my book, Seminumerical Algorithms (The Art of Computer Programming, vol. 2, published by Addison-Wesley), and Prof. Loos has kindly suggested that the readers of SIGSAM Bulletin may want to know something about this new version.
A short survey on the state of the art in matching and unification problems
Authors: Raulefs P. , Siekmann J. , Szabó P. , Unvericht E.
Published: January 2007

1. Motivations There is a wide variety of areas where matching and unification problems arise: (1.1)
Databases
The user of a
(relational) database
[22] may logically AND the properties she wants to retrieve or else she may be interested in the NATURAL JOIN [17] of two stored relations. In neither case, she would appreciate if she constantly had to take into account that AND is an associative and commutative operation, or that NATURAL JOIN obeys an associative axiom, which may distribute over some other operation [68].
The EEZ-GCD algorithm
Authors: Wang Paul S.
Published: January 2007

An enhanced gcd algorithm based on the EZ-GCD algorithm is described. Implementational aspects are emphasized. It is generally faster and is particularly suited for computing gcd of sparse multivariate polynomials. The EEZ-GCD algorithm is characterized by the following features:(1) avoiding unlucky evaluations,(2) predetermining the correct leading coefficient of the desired gcd,(3) using the sparsity of the given polynomials to determine terms in the gcd and(4) direct methods for dealing with the "common divisor problem." The common divisor problem occurs when the gcd has a different common divisor with each of the cofactors. The EZ-GCD algorithm does a square-free decomposition in this case. It can be avoided resulting in increased speed. One method is to use parallel p-adic construction of more than two factors. Machine examples with timing data are included.
A simplified proof of the characterization theorem for Gröbner-bases
Authors: Bachmair L. , Buchberger B.
Published: January 2007

In /2/ a certain type of bases ("Gröbner-Bases") for polynomial ideals has been introduced whose usefulness stems from the fact that a number of important computability problems in the theory of polynomial ideals are reducible to the construction of bases of this type. The key to an algorithmic construction of Gröbner-bases is a characterization theorem for Gröbner-bases whose proof in /2/is rather complex.In this paper a simplified proof is given. The simplification is based on two new lemmas that are of some interest in themselves. The first lemma characterizes the congruence relation modulo a polynomial ideal as the reflexive-transitive closure of a particular reduction relation ("M-reduction") used in the definition of Gröbner-bases and its inverse. The second lemma is a lemma on general reduction relations, which allows to guarantee the Church-Rosser property under very weak assumptions.
On the computation of lattice vectors of minimal length, successive minima and reduced bases with applications
Authors: Pohst Michael
Published: January 2007

The problem of determining shortest vectors and reduced bases or successive minima of lattices often occurs in algebra and number theory. Nevertheless, computational methods for the solution hardly exist in the literature. It is the aim of this paper to develop efficient algorithms for this purpose.
ORTOCARTAN
Authors: Krasiński Andrzej
Published: January 2007

The supply of computer programs for algebraic calculation seems at present sufficient to satisfy the needs of any potential user (1). It would thus seem natural for a future user to ask for a copy of one of the existing programs. However, it turns out to be quite difficult in practice. Some algebraic systems are not distributed at all (MACSYMA (2) was until recently an example). Some others (e.g. SHEEP (3, 4)) exist only for definite types of computers, and adapting such a program to another computer is, for an inexperienced programmer, a task comparable in difficulty to writing a program from scratch. Several specialized programs will not be suited to the particular application intended. Finally, establishing a local group of experts in algebraic programming in a place where this activity was not represented before is an obvious (*) convenience for the users. Therefore we decided in 1977 to write our own program.
Of integration by man and machine
Authors: Smith Paul , Sterling Leon
Published: January 2007

We describe a symbolic integration problem arising from an application in engineering. A solution is given and compared with the solution generated by the REDUCE integration package running at Cambridge. Nontrivial symbol manipulation, particularly simplification, is necessary to reconcile the answers.
On improving approximate results of Buchberger's algorithm by Newton's method
Authors: Trinks W.
Published: January 2007

In some applications of Buchberger's algorithm it is possible to avoid the use of multiple precision arithmetics in the main part of the calculations, even if the results are large numbers.
Differentiation of unknown functions in MACSYMA
Authors: Golden Jeffrey P.
Published: January 2007

Code which handles the differentiation of unknown functions in MACSYMA in a clean way has been written. In this paper we describe this implementation.
A remark on factorisation
Authors: Abbott J. A. , Bradford R. J. , Davenport J. H.
Published: January 2007

We are concerned with factoring polynomials over algebraic extensions of the rationals, and have implemented a variant of Trager's [1976] algorithm, which reduces this problem to that of factoring polynomials over the integers, for which we use Wang's [1978] algorithm (as implemented in REDUCE [Hearn 82] by Moore and Norman [1981]). However, Trager's method often produces a norm polynomial which factors profusely modulo every prime, leading to a combinatorial explosion of trial divisions in Wang's algorithm. We present some simple divisibility tests for polynomials to help combat the cost of this explosion.
REDUCE as a lisp benchmark
Authors: Marti Jed B. , Hearn Anthony C.
Published: January 2007

A number of different machine architectures and Lisp systems are compared through execution times of the REDUCE test program. The results show a reasonable correlation between manufacturers' claims of processor performance and the collected execution times.
Text mining and natural language processing
Authors: Kao Anne , Poteet Steve
Published: January 2007

This paper provides an introduction to this special issue of SIGKDD Explorations devoted to Natural Language Processing and Text Mining.
Chinese named entity recognition using lexicalized HMMs
Authors: Fu Guohong , Luke Kang-Kwong
Published: January 2007

This paper presents a lexicalized HMM-based approach to Chinese named entity recognition (NER). To tackle the problem of unknown words, we unify unknown word identification and NER as a single tagging task on a sequence of known words. To do this, we first employ a known-word bigram-based model to segment a sentence into a sequence of known words, and then apply the uniformly lexicalized HMMs to assign each known word a proper hybrid tag that indicates its pattern in forming an entity and the category of the formed entity. Our system is able to integrate both the internal formation patterns and the surrounding contextual clues for NER under the framework of HMMs. As a result, the performance of the system can be improved without losing its efficiency in training and tagging. We have tested our system using different public corpora. The results show that lexicalized HMMs can substantially improve NER performance over standard HMMs. The results also indicate that character-based tagging (viz. the tagging based on pure single-character words) is comparable to and can even outperform the relevant known-word based tagging when a lexicalization technique is applied.
Mining logs files for data-driven system management
Authors: Peng Wei , Li Tao , Ma Sheng
Published: January 2007

With advancement in science and technology, computing systems are becoming increasingly more complex with an increasing variety of heterogeneous software and hardware components. They are thus becoming increasingly more difficult to monitor, manage and maintain. Traditional approaches to system management have been largely based on domain experts through a knowledge acquisition process that translates domain knowledge into operating rules and policies. This has been well known and experienced as a cumber-some, labor intensive, and error prone process. In addition, this process is difficult to keep up with the rapidly changing environments. There is thus a pressing need for automatic and efficient approaches to monitor and manage complex computing systems.A popular approach to system management is based on analyzing system log files. However, some new aspects of the log files have been less emphasized in existing methods from data mining and machine learning community. The various formats and relatively short text messages of log files, and temporal characteristics in data representation pose new challenges. In this paper, we will describe our research efforts on mining system log files for automatic management. In particular, we apply text mining techniques to categorize messages in log files into common situations, improve categorization accuracy by considering the temporal characteristics of log messages, and utilize visualization tools to evaluate and validate the interesting temporal patterns for system management.