bluuebunny/crossref_metadata_2025 huggingface dataset:
System development methodology or system research methodology?
Authors: Coughlin Donald T.
Published: January 2007

A future data processing historian may someday point to the 1970s as the deoade when business application systems began their adolescent growth period. We entered the 1970s with few truly on-line business systems, and many application designers did not fully appreciate the capabilities and limitation of index sequential file structures. Many of the larger companies were busy writing their own tp monitors and file handling systems, and it is very possible that more professional hours were being devoted to the development of control program software than to applications software.

The last decade did provide the application programmer with new control program tools such as data base management systems and on-line terminal control software. It also generated a continuing demand for computer performance software specialists to tune application systems immediately after initial implementation. These performance tuning efforts often required substantial changes to the application system - not just program code but also basic redesign. Therefore were these really system development projects or were they system research projects?
An alchemical approach to brokerage
Authors: Earle Dennis M.
Published: January 2007

The essence of the commodities business is the ability to react quickly to evolving market conditions. Mocatta, a N.Y. based bullion dealer, is a firm which uses its Data Processing to provide both front office (trading) flexibility and back-office capacity to handle large volume days. The business is characterized by the constant trade-off of time against money. Corporate philosophy is to spend money to react quickly rather than to react slowly but perhaps at lower costs.

The life cycle of a system in this environment normally begins with a marketing report reflecting a new market nitch which the firm can take advantage of. Data Processing is involved almost from the inception of the idea to provide an indication of what existing systems can do for this new opportunity. Because of the nature of the business, each new product offered is usually so unique as to make it impossible for existing systems to support a new product from a trading point of view. Back-office applications are somewhat more common across products, so existing systems can usually provide some support. The key point is that all we really know is that we want to market the new product. Some idea of the time frame in which the product is to be offered is also obtained. The exact workings of defining the product and determining the parameters under which it will be traded usually remain to be worked out prior to the offering date. This therefore means that we have, at the point of commitment, the necessity for evolving data processing support in the same time frame in which the definition is evolving about what it is that we are to support.
Specification of a regression test for a mini computer operating system
Authors: Cox Patricia R.
Published: January 2007

In this paper I describe the practical problems of designing a regression test set for an existing mini-computer operating system. The ideal regression test would test each function with all possible combinations of the options for each variation of the operating system. This is impractical if not impossible so the alternative is to choose the individual cases for maximum coverage. To do that the system is viewed both functionally and structurally and cases are selected for inclusion in the test set. The method of selecting the tests is described along with the tools that will be needed to measure the coverage and to maintain the test set.
Evaluating and comparing software metrics in the software engineering laboratory
Authors: Basili Victor R. , Phillips Tsai-Yun
Published: January 2007

There has appeared in the literature a great number of metrics that attempt to measure the effort or complexity in developing and understanding software(1). There have also been several attempts to independently validate these measures on data from different organizations gathered by different people(2). These metrics have many purposes. They can be used to evaluate the software development process or the software product. They can be used to estimate the cost and quality of the product. They can also be used during development and evolution of the software to monitor the stability and quality of the product.

Among the most popular metrics have been the software science metrics of Halstead, and the cyclomatic complexity metric of McCabe. One question is whether these metrics actually measure such things as effort and complexity. One measure of effort may be the time required to produce a product. One measure of complexity might be the number of errors made during the development of a product. A second question is how these metrics compare with standard size measures, such as the number of source lines or the number of executable statements, i.e., do they do a better job of predicting the effort or the number of errors? Lastly, how do these metrics relate to each other?
Optimal testing policies for software systems
Authors: Goel Amrit L.
Published: January 2007

An important problem of practical concern is to determine how much testing should be done before a system is considered ready for release. This decision, of course, depends on the model for the software failure phenomenon and the criterion used for evaluating system readiness.

In this paper, we first develop a cost model based on the time dependent failure rate function of Goel and Okumoto. Next, we derive policies that yeild the optimal values of the level of test effort (b*) and software release time (T*). The sensitivity of the optimal solution is also numerically evaluated.
Software defects - a software science perspective
Authors: Ottenstein Linda M.
Published: January 2007

This paper gives a model for computing the programming time. The results of tests with programs in APL, BASIC, and FORTRAN are also given and discussed.
The application development process
Authors: Crowley John D.
Published: January 2007

This paper will examine the process used in the development of computer applications. The claim is made that the current methodology has serious deficiencies, but that a software development approach is becoming available to help address these problems.
A method for adaptive performance improvement of operating systems
Authors: Reiner David , Pinkerton Tad
Published: January 2007

This paper presents a method for dynamic modification of operating system control parameters to improve system performance. Improved parameter settings are learned by experimenting on the system. The experiments compare the performance of alternative parameter settings in each region of a partitioned load-performance space associated with the system. The results are used to modify important control parameters periodically, responding to fluctuations in system load and performance. The method can be used to implement adaptive tuning, to choose between alternative algorithms and policies, or to select the best fixed settings for parameters which are not modified.

The method was validated and proved practical by an investigation of two parameters governing core quantum allocation on a Sperry Univac 1100 system. This experiment yielded significant results, which are presented and discussed. Directions for future research include automating the method, determining the effect of simultaneous modifications to unrelated control parameters, and detecting dominant control parameters.
On the VAX/VMS time-critical process scheduling
Authors: Wang Y. T.
Published: January 2007

The VAX/VMS process schedule is briefly described. A simple priority-driven round-robin queuing model is then constructed to analyze the behavior of the time-critical processes of VAX/VMS under such a schedule.

Mean and variance of the conditional response time of a process at a given priority are derived, conditioned on the amount of service time required by that process. Numerical results are given with comparisons to the ordinary priority queuing systems.
Balanced job bound analysis of queueing networks
Authors: Zahorjan J. , Sevcik K. C. , Eager D. L. , Galler B. I.
Published: January 2007

Applications of queueing network models to computer system performance prediction typically involve the computation of their equilibrium solution. When numerous alternative systems are to be examined and the numbers of devices and customers are large, however, the expense of computing the exact solutions may not be warranted by the accuracy required. In such situations, it is desirable to be able to obtain bounds on the system solution with very little computation. Asymptotic bound analysis (ABA) is one technique for obtaining such bounds. In this paper, we introduce another bounding technique, called balanced job bounds (BJB), which is based on the analysis of systems in which all devices are equally utilized. These bounds are tighter than ABA bounds in many cases, but they are based on more restrictive assumptions (namely, those that lead to separable queueing network models).
Computer system models
Authors: Schwetman Herb
Published: January 2007

A system model is a tool used to predict system performance under changing conditions. There are two widely used modeling techniques: one based on discrete event simulation and one based on queuing theory models. Because queueing theory models are so much cheaper to implement and use, as compared to simulation models, there is growing interest in them. Users are developing and using queuing theory models to project system performance, project capacity, analyze bottlenecks and configure systems.

This talk uses an operational analysis approach to develop system models. This approach, as presented in Denning and Buzen [1], provides an intuitive basis for analyzing system performance and constructing system models. Very simple calculations lead to estimates of bounds on performance - maximum job throughput rates and minimum message response times. The emphasis is on gaining an understanding of system models which reenforces intuition, not on mathematical formulae.

Several examples are included. References to other works and publications are provided. Application areas and limitations of modeling techniques are discussed.
Virtual machine-based simulation of distributed computing and network computing
Authors: Wang Richard T. , Browne J. C.
Published: January 2007

This paper proposes the use of virtual machine architectures as a means of modeling and analyzing networks and distributed computing systems. The requirements for such modeling and analysis are explored and defined along with an illustrative study of an X.25 link-level protocol performance under normal execution conditions. The virtualizable architecture used in this work is the Data General Nova 3/D.
The method of surrogate delays
Authors: Jacobson Patricia A. , Lazowska Edward D.
Published: January 2007

This paper presents a new approach to modelling the simultaneous or overlapped possession of resources in queueing networks. The key concept is that of iteration between two models, each of which includes an explicit representation of one of the simultaneously held resources and a delay server (an infinite server, with service time but no queueing) acting as a surrogate for queueing delay due to congestion at the other simultaneously held resource. Because of this, we refer to our approximation technique as the “method of surrogate delays”.
A queueing network approach to the module allocation problem in distributed systems
Authors: Bryant R. M. , Agre J. R.
Published: January 2007

Given a collection of distributed programs and the modules they use, the module allocation problem is to determine an assignment of modules to processors that minimizes the total execution cost of the programs. Standard approaches to this problem are based on solving either a network flow problem or a constrained 0-1 integer programming problem.

In this paper we discuss an alternative approach to the module allocation problem where a closed, multiclass queueing network is solved to determine the cost of a particular module allocation. The advantage of this approach is that the execution cost can be expressed in terms of performance measures of the system such as response time. An interchange heuristic is proposed as a method of searching for a good module allocation using this model and empirical evidence for the success of the heuristic is given. The heuristic normally finds module allocations with costs within 10 percent of the optimal module allocation.

Fast, approximate queueing network solution techniques based on mean-value-analysis allow each heuristic search to be completed in a few seconds of CPU time. The computational complexity of each search is O (M K (K + N) C) where M is the number of modules, K is the number of sites in the network, N is the number of communications processors, and C is the number of distributed program types. It appears that substantial problems of this type could be solved using the methods we describe.
Optimal control of a M/M/m queue
Authors: Lazar Aurel A.
Published: January 2007

The problem of optimal control of a M/M/m queueing system is investigated. As in the M/M/l case the optimum control is shown to be a window type mechanism. The window size
L
depends on the maximum allowable time delay
T
and can be explicitly computed. The throughput time delay function of the M/M/m system is briefly discussed.
Concentrator modeling with pipelining arrivals compensation
Authors: McGregor Patrick V.
Published: January 2007

A general model of Intelligent Communications Concentrating Devices (ICCD) is presented and analyzed for delay and overflow performance with compensation for the pipelining effect of message arrivals extending over time. The results of the analysis indicate that, for the same trunk utilization, the trend towards buffered terminals with longer messages requires substantially greater buffering in the ICCD. The nominal environment analyzed consisted of 10-40 medium speed terminals (1200 b/s - 9600 b/s) operating over a medium speed trunk (9600 b/s) with trunk utilizations from 20 percent to 80 percent and average message lengths up to 1000 characters. This is a substantially different environment than that typically served by current implementations of ICCDs, which are frequently reported to have throughput improvements of 2-3 times the nominal originating terminal bandwidths, as opposed to the typical factor of 5 for the analyzed environment. This does not reflect on the appropriateness of the ICCDs in serving the new environment, but rather is simply stating that in the new environment the same character volume of traffic may be appearing with different traffic characteristics over higher speed access lines.

If the new environment shows only a difference in traffic characteristics and originating line speed, without change in the traffic control scheme (or lack of scheme), the results indicate essentially reproduction of a large part of the terminal buffering in the ICCD for adequate overflow performance. Alternatively, with smarter terminals, traffic control schemes (flow control) may enable the ICCD to be reduced to an essentially unbuffered “traffic cop,” with the terminal buffering also serving as the shared facility buffering. Several practical implementations of ICCDs have provision for flow control, but require cooperating terminals and hosts. This suggests that ICCD design and application will become more sensitive to the practical operating features of the target environment than has been generally the case to date.

The analysis presented in this paper involves many simplifications to the actual problem. Additional work to accommodate non-exponential message length distributions and heterogeneous terminal configurations are perhaps two of the more immediate problems that may be effectively dealt with.
Performance analysis of local communication loops
Authors: Roehr Kuno M. , Sadlowski Horst
Published: January 2007

The communication loops analyzed here provide an economic way of attaching many different terminals which may be some kilometers away from a host processor. Main potential bottlenecks were found to be the loop transmission speed, the loop adapter processing rate, and the buffering capability, all of which are analyzed in detail. The buffer overrun probabilities are found by convolving individual buffer usage densities and by summing over the tail-end of the obtained overall density function. Examples of analysis results are given.
Performance analysis of local communication loops
Authors: Roehr Kuno M. , Sadlowski Horst
Published: January 2007

The communication loops analyzed here provide an economical way of attaching many different terminals to a IBM 4331 host processor which may be several kilometers away.

As a first step of the investigation protocol overhead is derived. It consists of request and transmission headers and the associated acknowledgements as defined by the System Network Architecture. Additional overhead is due to the physical layer protocols of the Synchronous Data Link Control including lower level confirmation frames.

The next step is to describe the performance characteristics of the loop attachment hardware, primarily consisting of the external loop station adapters for local and teleprocessing connections and the loop adapter processor.
Data, definition, deduction
Authors: Cox Springer
Published: January 2007

The theoretical aspects of operational analysis have been considered more extensively than matters of its application in practical situations. Since its relationships differ in their applicability, they must be considered separately when they are applied. In order to do this, the foundations of three such relationships are examined from an empirical point of view.

To further demonstrate the intimate connection between data, definitions, and performance models, the problem of measurement artifact is considered.
Hermite canonical form and Smith canonical form of a matrix over a principal ideal domain
Authors: Conti Pasqualina
Published: January 2007

This paper presents computational aspects of Smith and Hermite normal forms for matrices over general principal ideal domains. After reviewing the standard definitions and properties of Hermite and Smith normal forms, we ask when there is an effective algorithm which will find a unique canonical form for all matrices in the same equivalence class. We show that the ability to compute canonical members of an associate class and canonical representatives of a residue class in the underlying ring are necessary and sufficient conditions for an effective procedure to find unique Hermite and Smith forms. We then present a uniform technique for reducing intermediate expression swell during the computation of Smith and Hermite normal forms for matrices over general principal ideal domains. This generalizes previous work by handling non-square matrices which are not of full column rank. We also present examples which show that the heuristic of directly computing modulo the determinant as proposed by some can yield the wrong answer. We instead compute with the matrix augmented by the determinant times the identity matrix. This always yields the correct result and has the desired effect of allowing one to keep all elements which occur during the computation bounded by the determinant.
Human computer interaction: an operational definition
Authors: Marsh Shaun
Published: January 2007

This paper poses an operational definition for the term Human-Computer Interaction and distinguishes it from the term User Interface. Human-Computer Interaction includes several separate communication paths between the human and the computer's natural environment, the computer's own ergonomics, an operating environment, and an application environment. Each of these paths occur in parallel and have both a dialog and an interface component. A distinction is made between those dialog stages which allow multiple interpretations of symbols (soft-dialog) and those which allow only one interpretation for each symbol (hard-dialog). The term User Dialog includes only the soft-dialog stages, and the User Interface consists of the mechanisms for communicating the User Dialog.
Interposed proportional sharing for a storage service utility
Authors: Jin Wei , Chase Jeffrey S. , Kaur Jasleen
Published: January 2007

This paper develops and evaluates new share-based scheduling algorithms for differentiated service quality in network services, such as network storage servers. This form of resource control makes it possible to share a server among multiple request flows with probabilistic assurance that each flow receives a specified minimum share of a server's capacity to serve requests. This assurance is important for safe outsourcing of services to shared utilities such as Storage Service Providers.Our approach interposes share-based request dispatching on the network path between the server and its clients. Two new scheduling algorithms are designed to run within an intermediary (e.g., a network switch), where they enforce fair sharing by throttling request flows and reordering requests; these algorithms are adaptations of Start-time Fair Queuing (SFQ) for servers with a configurable degree of internal concurrency. A third algorithm, Request Windows (RW), bounds the outstanding requests for each flow independently; it is amenable to a decentralized implementation, but may restrict concurrency under light load. The analysis and experimental results show that these new algorithms can enforce shares effectively when the shares are not saturated, and that they provide acceptable performance isolation under saturation. Although the evaluation uses a storage service as an example, interposed request scheduling is non-intrusive and views the server as a black box, so it is useful for complex services with no internal support for differentiated service quality.
Emulating low-priority transport at the application layer
Authors: Key Peter , Massoulié Laurent , Wang Bing
Published: January 2007

Low priority data transfer across the wide area is useful in several contexts, for example for the dissemination of large files such as OS updates, content distribution or prefetching. Although the design of such a service is reasonably easy when the underlying network supports service differentiation, it becomes more challenging without such network support. We describe an application level approach to designing a low priority service -- one that is 'lower than best-effort' in the context of the current Internet. We require neither network support nor changes to TCP. Instead, we use a receive window control to limit the transfer rate of the application, and the optimal rate is determined by detecting a change-point. We motivate this joint control-estimation problem by considering a fluid-based optimisation framework, and describe practical solutions, based on stochastic approximation and binary search techniques. Simulation results demonstrate the effectiveness of the approach.
Data streaming algorithms for efficient and accurate estimation of flow size distribution
Authors: Kumar Abhishek , Sung Minho , Xu Jun (Jim) , Wang Jia
Published: January 2007

Knowing the distribution of the sizes of traffic flows passing through a network link helps a network operator to characterize network resource usage, infer traffic demands, detect traffic anomalies, and accommodate new traffic demands through better traffic engineering. Previous work on estimating the flow size distribution has been focused on making inferences from sampled network traffic. Its accuracy is limited by the (typically) low sampling rate required to make the sampling operation affordable. In this paper we present a novel data streaming algorithm to provide much more accurate estimates of flow distribution, using a "lossy data structure" which consists of an array of counters fitted well into SRAM. For each incoming packet, our algorithm only needs to increment one underlying counter, making the algorithm fast enough even for 40 Gbps (OC-768) links. The data structure is lossy in the sense that sizes of multiple flows may collide into the same counter. Our algorithm uses Bayesian statistical methods such as Expectation Maximization to infer the most likely flow size distribution that results in the observed counter values after collision. Evaluations of this algorithm on large Internet traces obtained from several sources (including a tier-1 ISP) demonstrate that it has very high measurement accuracy (within 2%). Our algorithm not only dramatically improves the accuracy of flow distribution measurement, but also contributes to the field of data streaming by formalizing an existing methodology and applying it to the context of estimating the flow-distribution.
Failure recovery for structured P2P networks
Authors: Lam Simon S. , Liu Huaiyu
Published: January 2007

Measurement studies indicate a high rate of node dynamics in p2p systems. In this paper, we address the question of how high a rate of node dynamics can be supported by
structured
p2p networks. We confine our study to the hypercube routing scheme used by several structured p2p systems. To improve system robustness and facilitate failure recovery, we introduce the property of K-
consistency
,
K
≥ 1, which generalizes consistency defined previously. (Consistency guarantees connectivity from any node to any other node.) We design and evaluate a failure recovery protocol based upon local information for K-consistent networks. The failure recovery protocol is then integrated with a join protocol that has been proved to construct K-consistent neighbor tables for concurrent joins. The integrated protocols were evaluated by a set of simulation experiments in which nodes joined a 2000-node network and nodes (both old and new) were randomly selected to fail concurrently over 10,000 seconds of simulated time. In each such "churn" experiment, we took a "snapshot" of neighbor tables in the network once every 50 seconds and evaluated connectivity and consistency measures over time as a function of the churn rate, timeout value in failure recovery, and
K
. Storage and communication overheads were also evaluated. We found our protocols to be effective, efficient, and stable for an average node lifetime as low as 8.3 minutes (the median lifetime measured for Napster and Gnutella was 60 minutes [10]).
Performance aware tasking for environmentally powered sensor networks
Authors: Kansal Aman , Potter Dunny , Srivastava Mani B.
Published: January 2007

The use of environmental energy is now emerging as a feasible energy source for embedded and wireless computing systems such as sensor networks where manual recharging or replacement of batteries is not practical. However, energy supply from environmental sources is highly variable with time. Further, for a distributed system, the energy available at its various locations will be different. These variations strongly influence the way in which environmental energy is used. We present a harvesting theory for determining performance in such systems. First we present a model for characterizing environmental sources. Second, we state and prove two harvesting theorems that help determine the sustainable performance level from a particular source. This theory leads to practical techniques for scheduling processes in energy harvesting systems. Third, we present our implementation of a real embedded system that runs on solar energy and uses our harvesting techniques. The system adjusts its performance level in response to available resources. Fourth, we propose a localized algorithm for increasing the performance of a distributed system by adapting the process scheduling to the spatio-temporal characteristics of the environmental energy in the distributed system. While our theoretical intuition is based on certain abstractions, all the scheduling methods we present are motivated solely from the experimental behavior and resource constraints of practical sensor networking systems.
Rate-based versus queue-based models of congestion control
Authors: Deb Supratim , Srikant R.
Published: January 2007

Mathematical models of congestion control capture the congestion indication mechanism at the router in two different ways: rate-based models, where the queue-length at the router does not explicitly appear in the model, and queue-based models, where the queue length at the router is explicitly a part of the model. Even though most congestion indication mechanisms use the queue length to compute the packet marking or dropping probability to indicate congestion, we argue that, depending upon the choice of the parameters of the AQM scheme, one would obtain a rate-based model or a rate-and-queue-based model as the deterministic limit of a stochastic system with a large number of users. We also consider the impact of implementing AQM schemes in the real queue or a virtual queue. If an AQM scheme is implemented in a real queue, we show that, to ensure that the queuing delays are negligible compared to RTTs, one is forced to choose the parameters of a AQM scheme in a manner which yields a rate-based deterministic model. On the other hand, if the AQM scheme is implemented in a virtual queue, small-queue operation is achieved independent of the choice of the parameters, thus showing a robustness property of virtual queue-based schemes.
Dynamics of hot-potato routing in IP networks
Authors: Teixeira Renata , Shaikh Aman , Griffin Tim , Rexford Jennifer
Published: January 2007

Despite the architectural separation between intradomain and interdomain routing in the Internet, intradomain protocols do influence the path-selection process in the Border Gateway Protocol (BGP). When choosing between multiple equally-good BGP routes, a router selects the one with the
closest
egress point, based on the intradomain path cost. Under such
hot-potato
routing, an intradomain event can trigger BGP routing changes. To characterize the influence of hot-potato routing, we conduct controlled experiments with a commercial router. Then, we propose a technique for associating BGP routing changes with events visible in the intradomain protocol, and apply our algorithm to AT&T's backbone network. We show that (i) hot-potato routing can be a significant source of BGP updates, (ii) BGP updates can lag
60
seconds or more behind the intradomain event, (iii) the number of BGP path changes triggered by hot-potato routing has a nearly uniform distribution across destination prefixes, and (iv) the fraction of BGP messages triggered by intradomain changes varies significantly across time and router locations. We show that hot-potato routing changes lead to longer delays in forwarding-plane convergence, shifts in the flow of traffic to neighboring domains, extra externally-visible BGP update messages, and inaccuracies in Internet performance measurements.
Spatio-temporal available bandwidth estimation with STAB
Authors: Ribeiro Vinay J. , Riedi Rudolf H. , Baraniuk Richard G.
Published: January 2007

We study the problem of locating in space and over time a network path's
tight
link, that is the link with the least available bandwidth on the path. Tight link localization benefits network-aware applications, provides insight into the causes of network congestion and ways to circumvent it, and aids network operations. We present
STAB
, a light-weight probing tool to locate tight links. STAB combines the probing concepts of self-induced congestion, tailgating, and packet chirps in a novel fashion. We demonstrate its capabilities through experiments on the Internet and verify our results using router MRTG data.
Locating the tightest link of a network path
Authors: Zhang Dalu , Huang Weili , Lin Chen
Published: January 2007

The tightest link of a network path is the link where the end-to-end available bandwidth is limited. We propose a new probe technique, called Dual Rate Periodic Streams (DRPS), for finding the location of the tightest link. A DRPS probe is a periodic stream with two rates. Initially, it goes through the path at a comparatively high rate. When arrived at a particular link, the probe shifts its rate to a lower level and keeps the rate. If proper rates are set to the probe, we can control whether the probe is congested or not by adjusting the shift time. When the point of rate shift is in front of the tightest link, the probe can go through the path without congestion, otherwise congestion occurs. Thus, we can find the location of the tightest link by congestion detection at the receiver.
Proteus: a software reuse library system
Authors: Frakes W. B. , Pole T. P.
Published: January 2007

Many methods for representing software components for reuse have been proposed. These include traditional library and information science methods, knowledge based methods, and hypertext. There has been no empirical evaluation of these methods, and consequently there is no data about their relative costs and effectiveness. Proteus is an experimental reuse library system that will be used to help gather such data. Reuse library systems are usually tied to one method---Proteus supports multiple methods.
An approach to probabilistic retrieval
Authors: Yu C. T. , Lam K.
Published: January 2007

The objective is to relate the effectiveness of retrieval, the fuzzy set concept and the processing of Boolean query. The use of a probabilistic retrieval scheme is motivated. It is found that there is a correspondence between probabilistic retrieval schmes and fuzzy sets. A fuzzy set corresponding to a potentially optimal probabilistic retrieval scheme is obtained. Then the retrieval scheme for the fuzzy set is constructed.
Statistical models for unformatted text
Authors: Landauer Christopher
Published: January 2007

In this note, we will describe some of the outstanding problems concerning statistical information retrieval models, and the underlying stochastic language production models they assume. The problems can be separated into classes according to the underlying language model, which can be either a sequence model or a grammar model. Both kinds of model are based on a stochastic process, but there is a different filter for the realization. The grammar models use a stochastic context sensitive grammar, and the sequence models use a high order Markov chain.Most of these problems cannot be solved without experimentation with information retrieval concepts and systems. Most information retrieval systems that currently exist have had to make operational assumptions about the answers to these questions. It is expected that more precise knowledge of solutions for these problems will simplify the design and improve the effectiveness of statistical information retrieval systems.
Artificial intelligence implications for information retrieval
Authors: DeJong Gerald
Published: January 2007

Overall, the field of information retrieval is already more aware than many other fields of the relevance of artificial intelligence (AI) [1-6]. Nonetheless there remain exciting applications of artificial intelligence that have been so far overlooked. In this paper we will point out some of the ways artificial intelligence might influence the field of information retrieval. We will then examine one application in more detail to discover the kind of technical problems involved in its fruitful exploitation.Before proceeding, it is important to interject a note of caution. While the promise of artificial intelligence is indeed bright, the time of complete fulfillment of its promise is a long way off. Of course, some of the expected contributions are shorter term than others. However, the more difficult problems will fall only after a good deal of basic research is accomplished. Artificial intelligence researchers have, in the past, been culpable of what can most charitably be described as over-optimism [7,8]. This naivete on the part of even the most respected of researchers stemmed from the profound subtleties underlying intelligent behavior. The problem is compounded by the fact that some of the most difficult of intelligent behavior (i.e. common sense) seems intuitively easy.
Evaluation of the 2-Poisson model as a basis for using term frequency data in searching
Authors: Raghavan Vijay V. , Shi Hong-pao , Yu C. T.
Published: January 2007

The early work on the probabilistic models of retrieval assumed that the document representation is binary, indicating only the presence or absence of index terms. The 2-Poisson (TP) model which was proposed as a model of how the occurrence frequency of specialty words in a collection is distributed, has since been used to develop retrieval strategies that incorporate term frequency information. This work investigates the use of the TP model, in this context, further. It is shown that the search effectiveness, when no relevance information is assumed, can be further enhanced by using this model. Furthermore, when the term weights proposed in this work are used in conjunction with weights known as term significance weights, the results are very encouraging.
A discrimination gain hypothesis
Authors: van Rijsbergen C. J.
Published: January 2007

Underlying many of the probabilistic models for information retrieval are assumptions of stochastic dependence or independence of varying degrees of severity for the index terms describing the documents. These models generally specify a matching function, that is a function which compares a query with each document. The form of that function is to a large extent determined by the particular dependence/independence assumption. For example, if the index terms are assumed to be independently distributed over both the set of relevant and non-relevant documents then the matching function will in general be linear, whereas an assumption of dependence will lead to a non-linear function.Irrespective of the form that the matching function may take it is always assumed that the search terms in the query are known. In this paper I wish to address the problem of the choice of search terms and how this choice may be affected by an independence assumption.
The user view of file management
Authors: Somers Patricia
Published: January 2007

The structures in which users store their files facilitate retrieval by enabling users to deduce a file's contents from its place in the organization. This study examined structures created by UNIX users to organize their files within a hierarchical directory scheme, and examined the relation between structure and command usage. Users' difficulties in managing the complexity of a hierarchical structure limited the amount of information about files that these structures contained. Tree complexity increased in a negatively accelerating function with the number of files. Users who grouped their files into few directories arranged in shallow trees could navigate through the tree easily, but they sacrificed information: directory names were less specific, and users made more command errors. More sophisticated users created deeper trees. They were able to manage more files but also made extensive use of navigation aids.
Record block allocation for retrieval on secondary keys
Authors: Yang Chung-Shu
Published: January 2007

Query retrieval based on secondary keys is an important operation in retrieval systems. Such a query generally retrieves more than one data record which satisfies the query criterion. This paper studies the problem of record address allocation in disk-like devices so as to facilitate the fast retrieval of a set of records which are jointly accessed by a query. A heuristic scheme, using the proposed minimal access retrieval property, is designed to assign records to blocks. Some experimental results are also presented.
SIRE
Authors: Noreault Terry , Mcgill Michael
Published: January 2007

SIRE (Syracuse Information Retrieval Experiment) is an interactive bibliographic retrieval system. It was developed at the School of Information Studies at Syracuse University. It is implemented in SAIL (Stanford Artificial Intelligence Language), an ALGOL like language, on a DEC KL-10. SIRE presently has two data bases; 1) one issue of Physics Abstracts with 7146 documents; and 2) a sign language linguistics data base from Gallaudet College with 490 documents.
WEIRD
Authors: Koll Matthew B.
Published: January 2007

WEIRD is an automatic document retrieval system designed and implemented at Syracuse University, which attempts to advance the art of computerized retrieval from word-matching to judging conceptual similarity. WEIRD uses a vector space model to represent the relations among terms and documents. Items in the space are located according to their “meaning”, which is their proximity to all other items in the data base as measured by co-occurrence frequencies. This is done without manipulating large matrices. The dimensions of the space are not used to define relations; items are defined solely by their position relative to the other items. Retrieval is determined by Euclidean distance from the plotted query. In the first section of the paper the basic characteristics of WEIRD are described. Second, the results of a preliminary evaluation are reported. Alternatives for further development of WEIRD are then considered.
Analytic modelling of “working set like” replacement algorithms
Authors: Marshall William T. , Nute C. Thomas
Published: January 2007

Although a large amount of theoretical work has been performed in the analysis of the pure working set replacement algorithm, little has been done applying these results to the approximations that have been implemented. This paper presents a general technique for the analysis of these implementations by analytic methods. Extensive simulations are reported which validate the analytic model and show significant simplifications that can be made with little loss of accuracy. The problem of choosing memory policy parameter values is examined and related in a simple way to the choice of a working set window size.
System characterization of a Retail Business System
Authors: Huff Robert W.
Published: January 2007

The complexities of Retail Business Systems today require a thorough understanding of how functional requirements impact desired system performance. It is no longer feasible to discretely test and evaluate individual system components without considering their inter-relationship. The techniques described in this presentation will define the method of system characterization of products prior to customer delivery. Three techniques are utilized to characterize system performance - simulation, stimulation, and performance measurement. Simulation involves writing a mathematical model which is enhanced from a product feasibility model to a system configuration tool as a result of stimulation and measurement activities. Stimulation consists of using emulators to load the system component under test as if the actual system is inter-connected. The emulators are programmed to produce a processing volume which can exceed the peak benchmark of the potential user. Performance measurement is accomplished during the stimulation activity using hardware/ software probes to monitor specific system parameters. These monitors provide vital information to determine total system capacity and the expected system performance for a given configuration. The information derived from system characterization is invaluable in providing the customer with a realistic expectation of system capability to perform its present functions and in projecting future growth potential.
A dynamic clustering strategy in a demand paging environment
Authors: Pooch Udo W.
Published: January 2007

An algorithm is presented which dynamically clusters pages of a problem program based on its past program behavior (i.e. reference string patterns) in a demand paged virtual memory environment. The objective of this algorithm is to minimize the number of page faults during execution, while at the same time use memory page frames efficiently. Dynamic clusters of time and reference related pages are built during a program's execution time.

Whenever a page fault for the i-th page occurs in this time evolving environment, the pages of the cluster associated with the i-th page is compared to the pages currently in real (physical) memory. Thus during this current page fault, the demanded page, and any associated clustered pages not currently in physical memory are placed into memory. Page frames holding pages not in the current cluster are returned to the memory management system. Thus the physical amount of memory allocated to a processing program is dependent upon the size of the associated cluster
at that time
.

Simulation results of program behavior operating under this dynamic clustering strategy indicates that significant improvements in page faults and in the space time product may be achieved. The algorithm requires fewer real page frames per executed instruction than most currently implemented algorithms that utilize a fixed number of page frames per problem programs (i.e. fixed allocated partition or region).

The algorithm, MLMM (Modified Locality Matrix Model), an extension of work by Hedges and Pooch [12] is used to determine inherent program locality to predict independent dynamic program behavior, separating instruction from data references. Furthermore, strength coefficients between weakly or loosely coupled clusters are used to refine the cluster population, identify cluster transitions, as well as indicate the behavior of the cluster formations.
Data structuring and indexing for data base machines
Authors: Banerjee Jayanta
Published: January 2007

Our focus in this paper is not the design of new and improved hardware for data base management. Instead, our main interest is to document the results of our investigation on the data structuring and indexing requirements of the class of data base machines that contain partitioned content-addressable memory (PCAM).
The access control mechanism of a database computer (DBC)
Authors: Menon M. Jaishankar , Hsiao David K.
Published: January 2007

The database computer (DBC) is a specialized back-end computer which is capable of managing data 10
10
bytes in size and supporting known data models such as relational, network, hierarchical and attribute-based models. It is also perhaps the first database machine to have a built-in security mechanism for access control.

At the outset, the security mechanism was made an integral part of the DBC design. This design philosophy not only allowed us to construct a system that has no “backdoors”, but also ensured that all access requests are, in fact, controlled by DBC's security mechanism. The DBC security mechanism is based on the concept of security atoms, aggregates of data units being definable by the user in terms of conjunctions of query predicates. The fundamental gain in utilizing query conjunctions for the purpose of access control is that any data that is accessible or updateable is also protectable.

It is believed that the DBC security mechanism is less cumbersome than the view mechanism of some database systems and more efficient than the query modification mechanism used by some other systems. This is demonstrated at three levels of access control, namely the subfile, record and field (attribute) levels.
A relational database machine architecture
Authors: Shaw David Elliot
Published: January 2007

Algorithms are described and analyzed for the efficient evaluation of the
project
and
join
operators of a relational algebra on a proposed non-von Neumann machine based on a hierarchy of associative storage devices. This architecture permits an
O
(log
n
) decrease in time complexity over the best known evaluation methods on a conventional computer system, without the use of redundant storage, and using currently available and potentially competitive technology. In many cases of practical import, the proposed architecture may also permit a significant improvement (by a factor roughly proportional to the capacity of the primary associative storage device) over the performance of previously implemented or proposed database machine architectures based on associative secondary storage devices.