bluuebunny/crossref_metadata_2025 huggingface dataset:
Structural analysis of network traffic flows
Authors: Lakhina Anukool , Papagiannaki Konstantina , Crovella Mark , Diot Christophe , Kolaczyk Eric D. , Taft Nina
Published: January 2007

Network traffic arises from the superposition of Origin-Destination (OD) flows. Hence, a thorough understanding of OD flows is essential for modeling network traffic, and for addressing a wide variety of problems including traffic engineering, traffic matrix estimation, capacity planning, forecasting and anomaly detection. However, to date, OD flows have not been closely studied, and there is very little known about their properties.We present the first analysis of complete sets of OD flow time-series, taken from two different backbone networks (Abilene and Sprint-Europe). Using Principal Component Analysis (PCA), we find that the set of OD flows has small intrinsic dimension. In fact, even in a network with over a hundred OD flows, these flows can be accurately modeled in time using a small number (10 or less) of independent components or dimensions.We also show how to use PCA to systematically decompose the structure of OD flow timeseries into three main constituents: common periodic trends, short-lived bursts, and noise. We provide insight into how the various constitutents contribute to the overall structure of OD flows and explore the extent to which this decomposition varies over time.
Flow sampling under hard resource constraints
Authors: Duffield Nick , Lund Carsten , Thorup Mikkel
Published: January 2007

Many network management applications use as their data traffic volumes differentiated by attributes such as IP address or port number. IP flow records are commonly collected for this purpose: these enable determination of fine-grained usage of network resources. However, the increasingly large volumes of flow statistics incur concomitant costs in the resources of the measurement infrastructure. This motivates sampling of flow records.This paper addresses sampling strategy for flow records. Recent work has shown that non-uniform sampling is necessary in order to control estimation variance arising from the observed heavy-tailed distribution of flow lengths. However, while this approach controls estimator variance, it does not place hard limits on the number of flows sampled. Such limits are often required during arbitrary downstream sampling, resampling and aggregation operations employed in analysis of the data.This paper proposes a correlated sampling strategy that is able to select an arbitrarily small number of the "best" representatives of a set of flows. We show that usage estimates arising from such selection are unbiased, and show how to estimate their variance, both offline for modeling purposes, and online during the sampling itself. The selection algorithm can be implemented in a queue-like data structure in which memory usage is uniformly bounded during measurement. Finally, we compare the complexity and performance of our scheme with other potential approaches.
A fast simulation framework for IEEE 802.11-operated wireless LANs
Authors: Kim Hwangnam , Hou Jennifer C.
Published: January 2007

In this paper, we develop a fast simulation framework for IEEE 802.11-operated wireless LANs (WLANs), in which a large number of packets are abstracted as a single fluid chunk, and their behaviors are approximated with analytic fluid models and figured into the simulation. We first derive the analytical model that characterizes data transmission activities in IEEE 802.11-operated WLANs with/without the RTS/CTS mechanism. All the control overhead incurred in the physical and MAC layers, as well as system parameters specified in IEEE 802.11 [12] are faithfully figured in. We validate the model with simulation in cases in which the network is and is not saturated. We then implement, with the use of the time stepping technique [21], the fast simulation framework for WLANs in
ns-2
[2], and conduct a comprehensive simulation study to evaluate the framework in terms of speed-up and errors incurred under a variety of network configurations.The simulation results indicate that the proposed framework is indeed effective in simulating IEEE 802.11-operated WLANs. It achieves as much as two orders of magnitude improvement in terms of execution time as compared to packet-level simulation. The performance improvement is more pronounced when the number of wireless nodes, the number of applications running on each wireless node, or the number of WLANs increases. The relative error, on the other hand, falls within 2% in all cases, as long as the value of the time step is appropriately determined.
VPC3
Authors: Burtscher Martin
Published: January 2007

Trace files are widely used in research and academia to study the behavior of programs. They are simple to process and guarantee repeatability. Unfortunately, they tend to be very large. This paper describes
vpc3
, a fundamentally new approach to compressing program traces.
Vpc3
employs value predictors to bring out and amplify patterns in the traces so that conventional compressors can compress them more effectively. In fact, our approach not only results in much higher compression rates but also provides faster compression and decompression. For example, compared to
bzip2
,
vpc3
's geometric mean compression rate on SPECcpu2000 store address traces is 18.4 times higher, compression is ten times faster, and decompression is three times faster.
Characterization of queue fluctuations in probabilistic AQM mechanisms
Authors: Tinnakornsrisuphap Peerapol , La Richard J.
Published: January 2007

We develop a framework for studying the interaction of a probabilistic active queue management (AQM) algorithm with a generic end-user congestion-control mechanism. We show that as the number of flows in the network increases, the queue dynamics can be accurately approximated by a simple deterministic process. In addition, we investigate the sources of queue fluctuations in this setup. We characterize two distinct sources of queue fluctuations; one is the deterministic oscillations which can be captured through the aforementioned deterministic process. The other source is the random fluctuations introduced by the probabilistic nature of the marking schemes. We discuss the relationship between these two types of fluctuations and provide insights into how to control them. Concrete examples in this framework are given for several popular algorithms such as Random Early Detection, Random Early Marking and Transmission Control Protocol.
The output of a cache under the independent reference model
Authors: Vanichpun Sarut , Makowski Armand M.
Published: January 2007

We consider a cache operating under a demand-driven replacement policy when document requests are modeled according to the Independent Reference Model (IRM). We characterize the popularity pmf of the stream of misses from the cache, the so-called output of the cache, for a large class of demand-driven cache replacement policies. We measure strength of locality of reference in a stream of requests through the skewness of its popularity distribution. Using the notion of majorization to capture this degree of skewness, we show that for the policy

A
0

and the random policy, the output always has less locality of reference than the input. However, we show by counterexamples that this is not always the case under the LRU and CLIMB policies when the input is selected according to a Zipf-like pmf. In that case, conjectures are offered (and supported by simulations) as to when LRU or CLIMB caching indeed reduces locality of reference.
A mean-field analysis of short lived interacting TCP flows
Authors: Baccelli François , Chaintreau Augustin , De Vleeschauwer Danny , McDonald David
Published: January 2007

In this paper, we consider a set of HTTP flows using TCP over a common drop-tail link to download files. After each download, a flow waits for a random think time before requesting the download of another file, whose size is also random. When a flow is active its throughput is increasing with time according to the additive increase rule, but if it suffers losses created when the total transmission rate of the flows exceeds the link rate, its transmission rate is decreased. The throughput obtained by a flow, and the consecutive time to download one file are then given as the consequence of the interaction of all the flows through their total transmission rate and the link's behavior.We study the mean-field model obtained by letting the number of flows go to infinity. This mean-field limit may have two stable regimes : one without congestion in the link, in which the density of transmission rate can be explicitly described, the other one with periodic congestion epochs, where the inter-congestion time can be characterized as the solution of a fixed point equation, that we compute numerically, leading to a density of transmission rate given by as the solution of a Fredholm equation. It is shown that for certain values of the parameters (more precisely when the link capacity per user is not significantly larger than the load per user), each of these two stable regimes can be reached depending on the initial condition. This phenomenon can be seen as an analogue of turbulence in fluid dynamics: for some initial conditions, the transfers progress in a fluid and interaction-less way; for others, the connections interact and slow down because of the resulting fluctuations, which in turn perpetuates interaction forever, in spite of the fact that the load per user is less than the capacity per user. We prove that this phenomenon is present in the Tahoe case and both the numerical method that we develop and simulations suggest that it is present in the Reno case too. It translates into a bi-stability phenomenon for the finite population model within this range of parameters.
Storage device performance prediction with CART models
Authors: Wang Mengzhi , Au Kinman , Ailamaki Anastassia , Brockwell Anthony , Faloutsos Christos , Ganger Gregory R.
Published: January 2007

This work explores the application of a machine learning tool, CART modeling, to storage devices. We have developed approaches to predict a device's performance as a function of input workloads, requiring no knowledge of the device internals. Two uses of CART models are considered: one that predicts per-request response times (and then derives aggregate values) and one that predicts aggregate values directly from workload characteristics. After training on the device in question, both provide reasonably-accurate black box models across a range of test traces from real environments. An expanded version of this paper is available as a technical report [1].
Another stemmer
Authors: Paice Chris D.
Published: January 2007

In natural language processing,
conflation
is the process of merging or lumping together nonidentical words which refer to the same principal concept. This can relate both to words which are entirely different in form (e.g., "group" and "collection"), and to words which share some common root (e.g., "group", "grouping", "subgroups"). In the former case the words can only be mapped by referring to a dictionary or thesaurus, but in the latter case use can be made of the orthographic similarities between the forms. One popular approach is to remove affixes from the input words, thus reducing them to a
stem
; if this could be done correctly, all the variant forms of a word would be converted to the same standard form. Since the process is aimed at mapping for retrieval purposes, the stem need not be a linguistically correct lemma or root (see also Frakes 1982).
Book review: Language and Representation in Information Retrieval by D.C. Blair. Elsevier Science Publishers 1990
Authors: Bruza P. D.
Published: January 2007

One of the remarkable things about the book
Language and Representation in Information Retrieval
is the large number of references to philosophers. Wittgenstein is quoted at the beginning of each chapter and there are also references to Hegel, Heiddegger and even to Nietsche. This naturally raises the question as to what these philosophers have to do with Information Retrieval. The answer is that the author considers several issues through the premises of a particular philosophy.
Article review: A message-based approach to discrete event simulation by R. L. Bagrodia, K. M. Chandy, and J. Misra. IEEE Trans. Softw. Eng. SE-13, 6 (June 1987)
Authors: Vance R. E.
Published: January 2007

As a service to our readers, PER has reached an agreement to reprint reviews of books and papers on simulation and modeling that originally appeared in ACM
Computing Reviews
. CR is a monthly journal that publishes critical reviews on a broad range of computing subjects including simulation and modeling. As an ACM member, you can subscribe to CR by writing to ACM Headquarters.
A comparison of search term weighting
Authors: Wu Harry , Salton Gerard
Published: January 2007

The term relevance weighting method has been shown to produce optimal information retrieval queries under well-defined conditions. The parameters needed to generate the term relevance factors cannot unfortunately be estimated accurately in practice; futhermore, in realistic test situations, it appears difficult to obtain improved retrieval results using the term relevance weights over much simpler term weighting systems such as, for example, the inverse document frequency weights.It is shown in this study that the inverse document frequency weights and the term relevance weights are closely related over a wide range of the frequency spectrum. Methods are introduced for estimating the term relevance weights, and experimental results are given comparing the inverse document frequency with the estimated term relevance weights.
Incorporating different search models into one document retrieval system
Authors: Croft W. Bruce
Published: January 2007

Many effective search strategies derived from different models are available for document retrieval systems. However, it does not appear that there is a single most effective strategy. Instead, different strategies perform optimally under different conditions. This paper outlines the design of an adaptive document retrieval system that chooses the best search strategy for a particular situation and user. In order to be able to support a variety of search strategies, a general network representation of the documents and terms in the database is proposed. This network representation leads to efficient methods of generating and using document and term classifications.One of the most desirable features of an adaptive system would be the ability to learn from experience. A method of incorporating this learning ability into the system is described. The adaptive control strategy for choosing search strategies enables the system to base its actions on a number of factors, including a model of the current user.Finally, some ideas for a flexible interface for casual users are suggested. Part of this interface is the heuristic search, which is used when searches based on formal models have failed. The heuristic search provides a browsing capability for the user.
Simulation of user judgments in bibliographic retrieval systems
Authors: Tague Jean M. , Nelson Michael J.
Published: January 2007

The general model and simulation algorithms for bibliographic retrieval systems presented in an earlier paper are expanded. The new model integrates the physical as well as the logical and semantic elements of these systems. A modified algorithm is developed for the simulation of user relevance judgments, and is validated, by means of recall-precision curves and a Kolmogorov-Smirnov test of recall, for two test collections. Other approaches to goodness-of-fit testing are suggested.
Representation issues in information retrieval system design
Authors: Smith Linda C.
Published: January 2007

The representation problem confronting information retrieval system designers is outlined in terms of three issues: what to represent, forms of representation, and functions of representation. Questions raised by each of these issues are identified and selected research projects which have begun to explore these questions are described.
Document Contents Representation model of sentence retrieval system SCAT-IR
Authors: Nikkuni Michiyo , Tanaka Hajime
Published: January 2007

A "Document Contents Representation" (DCR) model is introduced from a formal viewpoint to deal with the entire contents of a document such as individual sentences of a text, bibliography, references, etc. in a scientific information system. A "Mapping Definition Language" (MDL) is proposed to map directly and naturally the document contents into the DCR model. An application of the DCR model and MDL to scientific documents is shown. Some examples of advanced retrieval by SCAT-IR system implemented on the basis of the DCR model and MDL are illustrated.
Outline of a dynamic self-tuning and adaptive information retrieval system
Authors: Hausen Hans-Ludwig
Published: January 2007

A self-tuning adaptive information retrieval system as an extension of the concept of a "classical" document retrieval system, is outlined. This system accepts documents and search requests in natural language, as well as the system-proposals previously produced by the system itself or prepared by the system operator. It produces a system-proposal that consists of a list of documents ranked according to their relevance to the query.Incorporated into the system is a system valuation subsystem that uses weighted relevance judgements. This subsystem gives as output an effectiveness value and an efficiency value: both together measure the quality of an information retrieval system.The computation of the quality values and the values themselves are independent of a specific implementation. The retrieval process in this system consists of two parts, namely a query-document match and a query-query match.
Expert/consultation system for a retrieval data-base with semantic network of concepts
Authors: Shoval Peretz
Published: January 2007

This paper describes a development and implementation of an expert/consultation system for a retrieval data-base, that interfaces between the user and a retrieval system. The system's objective is to perform the information consultant's job in assisting a user to select the right vocabulary terms for his query. It is particularly useful for a novice user of a controlled-vocabulary, index-based retrieval system, who is not familiar with the vocabulary and the system Thesaurus. The user will enter his terms/keywords, that represent his information need, and the system will apply search procedures on its knowledge-base, and will find relevant concepts to be used as query-terms. The system is interactive; it can explain to the user why/how a concept was discovered/suggested, and it can back-track and try to find alternatives in case the user rejects a suggested concept. Two versions of the system were developed, utilizing two search and interaction strategies. Experiments will be conducted with the two alternatives in order to find out user preference and to compare performance. Performance will also be compard with an alternative "conventional" approach, which is an On-Line-Thesarus - developed as part of this study.
Hardware systems for text information retrieval
Authors: Hollaar Lee A.
Published: January 2007

As databases become very large, conventional digital computers cannot provide satisfactory response time. This is particularly true for text databases, which must often be several orders of magnitude larger than formatted databases to store a useful amount of information. Even the standard techniques for improving system performance (such as inverted files) may not be sufficient to give the desired performance, and the use of an unconventional hardware organization may become necessary.A variety of different organizations has been proposed to enhance processing of text retrieval operations. Most of these have concentrated on the design of fast, efficient search engines. These can be divided into three classes: associative memories, cellular pattern matchers, and finite state automata. The advantages and disadvantages inherent in each of these approaches are discussed, along with a number of proposed implementations. Finally, the text retrieval system under development at the University of Utah is discussed in more detail.
Intelligent information systems
Authors: Lebowitz Michael
Published: January 2007

Natural language processing techniques developed for Artificial Intelligence programs can aid in constructing powerful information retrieval systems in at least two areas. Automatic construction of new concepts allows a large body of information to be organized compactly and in a manner that allows a wide range of queries to be answered. Also, using natural language processing techniques to conceptually analyze the documents being stored in a system greatly expands the effectiveness of queries about given pieces of text. However, only robust conceptual analysis methods are adequate for such systems. This paper will discuss approaches to both concept learning, in the form of
Generalization-Based Memory,
and powerful, robust text processing achieved by
Memory-Based Understanding.
These techniques have been implemented in the computer systems IPP, a program that reads, remembers and generalizes from news stories about terrorism, and RESEARCHER, currently in the prototype stage, that operates in a very different domain (technical texts, patent abstracts in particular).
Natural language grammars for an information system
Authors: de Sopeña Luis
Published: January 2007

The User Specialty Languages (USL) System is an applications independent natural language interface to a Relational Database System. It provides non DP-trained people with a tool to introduce, query, manipulate and analyse the data stored in a Relational Database via natural language. USL interfaces with different languages; in the present paper the grammar developed for Spanish is presented, and compared with the German grammar which was previously implemented and upon which it is based. Their main differences are pointed out, and the generality of the system to deal with other natural languages shown.
Information retrieval using a transportable natural language interface
Authors: Bates Madeleine , Bobrow Robert J.
Published: January 2007

This paper describes work in progress to develop a facility for natural language access to a variety of computer databases and database systems. This facility, called IRUS for Information Retrieval using the RUS parsing system, allows users who are unfamiliar with the technical characteristics of the underlying database system to query databases using typed English input. This system can be thought of as a stand-alone query system or as part of a management information system (MIS) or a decision support system (DSS).Many systems boast of having a "user-friendly" or "English-like" or even "English" interface so that users require a minimum of special training to use the system, but most such systems use shallow, relatively ad hoc techniques that are not robust or linguistically sound. We are using a large, well-tested, theoretically-based, general parser of English that has been developed and extended in a variety of research projects for over a decade.One of the primary emphases of IRUS is transportability, which includes three types of changes: (1) changing the domain, (2) changing data bases within the same domain, and (3) changing data base systems. The use of a general parser for English is an important part of the solution to the transportability problem, but there are other parts as well, since portions of the system beyond the parser must know the conceptual content of the domain, the way in which this is reflected in a collection of datasets, and the operating characteristics of the dbms being used to access these datasets.Other researchers have investigated similar issues [8, 5, 6, 12]. We have attacked this problem by building a knowledge-based system, with procedural components independent of domain and data base structure, directed by domain and database dependent knowledge structures. We are also building tools for conveniently creating and maintaining these knowledge structures, with an eventual goal of allowing end-users to extend and modify these knowledge structures to suit their own needs. Given this set of goals, and these tools, we consider the current implementation, which uses the System 1022 dbms on the DEC KL-2060, to be only one of a set of possible implementations, and are not constraining IRUS on the basis of 1022's strengths and weaknesses.This paper presents an overview of the IRUS system, emphasizing those aspects of the design that are critical to transportability. We describe the parsing system, which is a completely independent module that has been interfaced to a variety of different applications, and then discuss the other modules which bridge the gap between the parser and the dbms.
A clustering scheme
Authors: Can Fazli , Ozkarahan Esen A.
Published: January 2007

In this paper, a new clustering algorithm has been described. The algorithm proposed determines both the number of clusters in a collection, and the number of elements in each cluster before beginning the final clustering process. The complexity assessment of the algorithm and the implementation issues are also emphasized.
User interfaces to information systems
Authors: Geller V. J. , Lesk M. E.
Published: January 2007

Do users prefer selection from a menu or specification of keywords to retrieve documents? We tried two experiments, one using an on-line library catalog and the other an on-line news wire. In the first, library users could either issue keyword commands to see book catalog entries, or choose categories from a menu following the Dewey Decimal classification of the books. In the second, news wire users could read Associated Press news stories either by posting a keyword profile against which all stories were matched, or by selecting them from a menu of current news items. For the library users, keyword searches were clearly preferred, by votes of 3 and 4 to 1; for the news stories, retrieval by keyword search is 50% less common than menu choice.We suggest that the difference is based on the degree of user foreknowledge of the data base and its organization. Menu-type interfaces tell the user what is available. If the user already knows, as in the library where a majority of the users have a particular book in mind, then the menu is merely time-consuming. But when the user does not know what is available (almost the definition of "news" is that it is new, and unpredictable), the menu is valuable because it displays the choice.
End user touch searching for cancer therapy literature
Authors: Pollitt A. S.
Published: January 2007

This paper reviews work towards building an expert system for searching the cancer therapy literature on MEDLINE. A modified subset of the Medical Subject Headings (MeSH) has been stored on a micro-computer and accessed via a touch terminal. Searches, previously requested of the Oncology Information Service at the University of Leeds, have been used to test out the principle of end user searching and the results compared with the searching expertise of a MEDLARS indexer. Original program development was in PASCAL, but a rule-based approach, which is independent of a particular programming language, has been developed for search term and frame selection adopting a 'blackboard' philosophy in tracing the process of selection. Work is progressing on an implementation using the expert systems programming language PROLOG, which has been found a very suitable language for representing rules and provides a ready made rule interpreter. It is suggested that this approach is superior in terms of retrieval performance compared with alternative approaches to end-user searching which fail to exhibit detailed knowledge regarding the subject matter of the search.
Transaction log analysis online catalogs
Authors: Tolle John E.
Published: January 2007

From November 1981 to April 1983, OCLC's Office of Research has been conducting research into online public access catalogs (OPACs). This project has been funded in part by the Council on Library Resources, Inc. as an attempt to provide new insight into the use of online catalogs by obtaining information which may serve as input for better system design of OPACs, utilizing not only desired user features but also more effective searching.The overall study is concerned with the patron and the system and consists of three major parts. The first is the study of current use of online catalogs, i.e., the actual use - what is really happening. The second element is concerned with the perceived patron use of the catalogs and involves the use of questionnaires and focus group interviews at the participating institutions. The third part is an application of the findings from the first two parts.This paper focuses on the current utilization of OPACs. The methodology chosen to employ is to obtain machine-readable transaction logs, via tapes, from the online catalogs and subsequently analyzing these transactions by stochastic search pattern development and mathematical models utilizing Markov chain analysis and the development of transition probability matrices.
A network organization used for document retrieval
Authors: Croft W. B. , Wolf R. , Thompson R.
Published: January 2007

A network organization for implementing a document retrieval system is proposed. This organization has significant advantages in terms of the range of searches that can be used when compared to either inverted or clustered file organizations. Algorithms for generating and maintaining the network are described together with experiments designed to test their efficiency and effectiveness.
Knowledge-Based Report Generation
Authors: Kukich Karen
Published: January 2007

Knowledge-Based Report Generation is a technique for automatically generating natural language summaries from databases. It is so named because it applies the tools of knowledge-based expert systems design to the problem of text generation. The technique is currently being applied to the design of an automatic natural language stock report generator. Examples drawn from the implementation of the stock report generator are used to describe the components of a knowledge-based report generator.
Some research problems in automatic information retrieval
Authors: Salton G.
Published: January 2007

Information retrieval components are currently incorporated in several types of information systems, including bibliographic retrieval systems, data base management systems and question-answering systems. Some of the problems arising in the real-time environment in which these systems operate are briefly discussed. Certain recent advances in information retrieval research are then mentioned, including the formulation of new probabilistic retrieval models, and the development of automatic document analysis and Boolean query processing techniques.
Automated monitoring to support the analysis and evaluation of information systems
Authors: Dominick W. D. , Penniman W. D.
Published: January 2007

This paper is based on, and extracted in part from, a much more expanded and detailed manuscript entitled "Monitoring and Evaluation of On-Line Information System Usage", accepted for publication in Information Processing and Management.
Productivity, information technology and the office
Authors: Landau Robert M.
Published: January 2007

It is well known that American productivity has advanced very little in the last ten years in contrast to many other countries' rapidly rising productivity. It is becoming evident that major productivity gains can be made, particularly in the office workforce, which constitutes the majority of the American workforce today. Rapidly developing information technologies are making it possible to achieve radically increased productivity in the office. This paper will discuss the specific technologies; the specific major office functions; how they interrelate; and how they are making such radical productivity increases possible. "The Paperless Office", created by Micronet, Inc. in Washington, D.C., will be described. The current project to automate the office activities of the American Productivity Center in Houston, Texas, will be described. Some projections of the significance of these projects will be given.
On the implementation of some models of document retrieval
Authors: Croft W. Bruce
Published: January 2007

Recently several models of the search process in a document retrieval system have been proposed and retrieval experiments have shown that they will improve system performance. These include models which use relevance judgements to rank documents in order of probability of relevance and models of retrieval from clusters of documents. In this paper various models are compared in terms of the ease with which they could be implemented. An important consideration is how this implementation would be affected by the introduction of new hardware such as content-addressable memories. The main conclusion is that models which concentrate on improving the effectiveness of the search process are not rendered redundant by the availability of new hardware. However, the efficiency of their implementation would be improved.
Augmented Transition Networks as a design tool for personalized database systems
Authors: Tharp Alan L.
Published: January 2007

This paper illustrates the use of Augmented Transition Networks (ATNs) as a design tool for constructing document retrieval systems for those personalized applications which are too small or specialized to attract a commercial vendor. ATNs, which are explained in the context of this application, are used
not only
to improve the human/computer interface with the retrieval system
but also
to conceptually organize its structure.
Mediator
Authors: Slonim Jacob , Maryanski Fred J. , Fisher Paul S.
Published: January 2007

Mediator: An Integrated Approach to Information Retrieval

The
Mediator
is a pseudo intelligent software controller which accomplishes two ends. First, it “mediates” between an Information Retrieval System and its end-user. On the assumption that the user of such a system will have at best a minimal knowledge of the operations of computers, it hides from him the internal complexities of the system, and presents to him a simplified “abstract” of the operations of the system. The Mediator allows the end-user to communicate with any application program in his own terms and to carry out operations of any degree of complexity which can be defined within those terms. Secondly, the controller enables a single system to extract unified information from data-banks of both data base management and textual environments. The Mediator is driven by a combination of hierarchically structured internal and external tables. The external tables contain a vocabulary selected by the user for his personal communication with the system; the internal tables contain directives which determine the appropriate path to be followed by the retrieval system in accomplishing the user's request.
A file organization for cluster-based retrieval
Authors: Croft W. Bruce
Published: January 2007

A file organization for cluster-based retrieval is presented and tested. This file organization is based on the bottom-up search which, in contrast to the more usual top-down search, starts at the lowest level of a cluster hierarchy (the documents) and looks at progressively larger clusters. This approach enables most of the efficiency problems previously associated with clustered file organizations to be avoided. There are two parts to this file organization - a compact cluster hierarchy representation which does not store cluster representatives and a compact inverted file which is used to provide a starting point for the bottom-up search.

Retrieval experiments show that the bottom-up search using this file organization can be more effective than a serial search, especially if high precision results are required.
A tree algorithm for nearest neighbor searching in document retrieval systems
Authors: Eastman Caroline M. , Weiss Stephen F.
Published: January 2007

The problem of finding nearest neighbors to a query in a document collection is a special case of associative retrieval, in which searches are performed using more than one key. A nearest neighbors associative retrieval algorithm, suitable for document retrieval using similarity matching, is described. The basic structure used is a binary tree, at each node a set of keys (concepts) is tested to select the most promising branch. Backtracking to initially rejected branches is allowed and often necessary.

Under certain conditions, the search time required by this algorithm is 0(log
2
N)
k
. N is the number of documents, and k is a system-dependent parameter. A series of experiments with a small collection confirm the predictions made using the analytic model; k is approximately 4 in this situation.

This algorithm is compared with two other searching algorithms; sequential search and clustered search. For large collections, the average search time for this algorithm is less than that for a sequential search and greater than that for a clustered search. However, the clustered search, unlike the sequential search and this algorithm, does not guarantee that the near neighbors found are actually the nearest neighbors.
Experiments on the determination of the relationships between terms
Authors: Raghavan Vijay V. , Yu C. T.
Published: January 2007

The retrieval effectiveness of an automatic method that uses relevance judgements for the determination of positive as well as negative relationships between terms is evaluated. The term relationships are incorporated into the retrieval process by using a generalized similarity function that has a term match component, a positive term relationship component, and a negative term relationship component. Two strategies, query partitioning and query clustering, for the evaluation of the effectiveness of the term relationships are investigated. The latter appears to be more attractive from linguistic as well as economic points of view. The positive and the negative relationships are verified to be effective both when used individually, and in combination. The importance attached to the term relationship components relative to that of term match component is found to have a substantial effect on the retrieval performance. The usefulness of discriminant analysis as a technique for determining the relative importance of these components is investigated.
A polynomial time algorithm for the N-Queens problem
Authors: Sosic Rok , Gu Jun
Published: January 2007

The
n
-queens problem is a classical combinatorial problem in the artificial intelligence (AI) area. Since the problem has a simple and regular structure, it has been widely used as a testbed to develop and benchmark new AI search problem-solving strategies. Recently, this problem has found practical applications in VLSI testing and traffic control. Due to its inherent complexity, currently even very efficient AI search algorithms developed so far can only find a solution for the
n
-queens problem with
n
up to about 100. In this paper we present a new, probabilistic local search algorithm which is based on a gradient-based heuristic. This efficient algorithm is capable of finding a solution for extremely large size
n
-queens problems. We give the execution statistics for this algorithm with
n
up to 500,000.
Book review: An Introduction to Neural and Electronic Networks. Edited by Steven E Zornetzer, Joel L. Davis, and Clifford Lau (Academic Press)
Authors: Reggia James A.
Published: January 2007

The volume is a collection of papers on neural networks (real and artificial) edited by staff members of the Office of Naval Research (ONR). ONR has been a major supporter of research in this area for many years and the editors have directly overseen some of the work described in this book, making them especially qualified to organize this collection. The chapters themselves are authored by talented individuals in neuroscience, engineering, physics, psychology, computer science and mathematics, making the book genuinely multidisciplinary in nature. Most of the papers are original, although a few are reprints of material previously published elsewhere.
Performance simulation as a tool in central processing unit design
Authors: Wiecek Cheryl A. , Steely Simon C.
Published: January 2007

Performance analysis has always been considered important in computer design work. The area of central processing unit (CPU) design is no exception, where the successful development of performance evaluation tools provides valuable information in the analysis of design tradeoffs. Increasing integration of hardware is producing more complicated processor modules which add to the number of alternatives and decisions to be made in the design process. It is important that these modules work together as a balanced unit with no hidden bottlenecks. This paper describes a project to develop performance simulation as an analysis tool in CPU design. The methodology is first detailed as a three part process in which a performance simulation program is realized that executes an instruction trace using command file directions. Discussion follows on the software implemented, applications of this tool in CPU design, and future goals.
A technique for integrating simulation and system design
Authors: Sanguinetti John
Published: January 2007

A technique for simulating incomplete systems is given which allows performance prediction during system design. This technique, called integrated simulation, allows the system design to itself be a simulation model, thus avoiding the overhead of maintaining a separate, valid simulation model for the system. The paper presents integrated simulation in the framework of a system modeling language called the Program Process Modeling Language, PPML. This language provides a means for describing systems of concurrent processes in both abstract and explicit terms, thus lending itself well to a top-down design method. In the design process, any PPML representation of the system can be simulated directly, from the most abstract design to the completely elaborated system. Simulation of the completely elaborated system is, in fact, simply the system in execution. The paper defines PPML and describes the techniques required to simulate PPML systems given various underlying machines. It concludes with a discussion of the limitations of the integrated simulation method.
Benchmarking interactive systems
Authors: Spooner Christopher R.
Published: January 2007

The author has recently developed a new methodology of benchmarking, which is being applied to a procurement in which (a) a single integrated interactive application is to span a distributed configuration of computing hardware, (b) the configuration is unknown when the benchmark is being developed, and (c) the application software will be written after the benchmark has been run. The buyer prepares a simulation model of the intended application in the form of programs that will run on the hardware being benchmarked. Each competing vendor is expected to tune the performance of this model to the hardware configuration that he has proposed, so he will require several versions of the model. This presents the buyer with a formidable software-production problem, which is further complicated by a requirement for extreme flexibility and reliability. The paper addresses the software-production problem and describes its solution. The solution was to develop an automated code-production system based on two principal design features. First, the model and its translator are both written in the same language; secondly, the common language is selected on the basis of readability and extensibility. The paper examines why this approach to the code-production problem was successful. Though the code-production system was developed to support a particular benchmarking approach, it should also be useful in other modeling situations. Indeed it might be of interest in any field where readability, reliability, ease of maintenance, and economy of programming effort are considered important.
Small business system performance analysis
Authors: Dyal James O. , DeWald William
Published: January 2007

This paper presents results from the performance simulation study of a small business-oriented computer system. The system, SPERRY UNIVAC BC/7-700, is commercially available in the configuration modeled and in other higher performance models. All BC/7 systems modeled are supported with highly interactive applications software systems.

The model is parameterized to select one or more workstations and one or more cartridge disks. File allocations are by cylinder. Seek times are computed by remembering the position of each movable arm. References are randomized within each file, but the sequence in which files are accessed is controlled by the application logic, in conjunction with the number of line items/order. Most event times are not constant, but the result of drawing randomly against empirical distributions with specified mean and standard deviation.

For this study, the system simulated is composed of a single work-station running the highly interactive on-line version of a sophisticated order entry application package. Principal performance measures are system throughput and response time, including operator action times.

It is found that, in the single workstation environment, performance is very cost effective in this highly competitive part of the information system market.
Optical mass storage technology
Authors: Laub Leonard J.
Published: January 2007

This paper describes some of the history, general principles and current embodiments of the technology of data storage and retrieval by optical means. It also discusses the utility of some of these embodiments in certain classes of application.
Data base processor mage
Authors: Sabbatel G. Berger
Published: January 2007

In this paper, we present the design of data base processor MAGE. This DBP is based on a hierarchical DB access method. It is composed of two microprocessors, a disk processor and a moving head disk. The processor requirements, design decisions, and architecture are discussed.

We start with an overview of DBP framework. The MAGE DB access method is then summarized. Finally, we present the design and implementation of the DBP, with a particular emphasis on the disk processor.
APCAM (A Practical Cellular Associative Memory)
Authors: Kibler Tom R.
Published: January 2007

This paper discusses about APCAM. APCAM was designed as a practical intelligent parallel search disk for support of relational data base systems. The aim was not to provide a complete relational engine but to provide a machine which would search large volumes of data and perform projections and restrictions along with helping with sorting.
A general multi-microprocessor interconnection mechanism for non-numeric processing
Authors: Toong Hoo-min D. , Strommen Svein O. , Goodrich Earl R.
Published: January 2007

MMPS interconnection problems are discussed in terms of a single time-shared bus. The performance drawbacks usually associated with the single bus alternative are attributed to the high bus utilization at the basic building block level. The Pended Transaction Bus protocol is presented as a general solution to such utilizations. Such a bus is developed to support more than 50 processors without severe contention. The basic protocol of the MC68000 as a current generation microprocessor is investigated, and shown ineffective for true multi-microprocessor systems.