bluuebunny/crossref_metadata_2025 huggingface dataset:
Status report on the ROBOT natural language query processor
Authors: Harris Larry R.
Published: January 2007

This is the first in a series of reports to acquaint the AI community with the first commercially available natural language processor for data base query. The system, called ROBOT, is being marketed by the Artificial Intelligence Corporation of Kensington, Maryland, and is currently installed in three commercial sites. In this report we trace the origins of the system, the installation and acceptance testing performed by the user sites, and the impact the system has had on the trade media's view of AI.
Workshop on social plans and language
Authors: Cohen Phil , Bruce Chip
Published: January 2007

We are reporting on an Informal workshop, held April 10 and 11 at BBN, that focused on the relationship between speech acts, plans, and plan-recognition.
Plan recognition and language
Authors: Allen James F.
Published: January 2007

This talk described a computer system that exploits a simple fact: language is intentional behavior. People speak in order to attain effects on specific listeners, and in so doing, achieve goals for themselves.
Toward an ethnolinguistic account of conversation
Authors: Dore John
Published: January 2007

The purpose of this paper is to propose an analysis of linguistic form and social frames such that we can arrive at an account of how speakers recognize each other's utterances as acts of conversation. The specific goals are to show how utterance forms can be construed as
acts of conversation;
how these acts are coherently related within
conversational sequences
across turns at speaking; how such sequences accomplish the
speech events
the speakers are co-constructing; how conversational acts co-define, along with the speakers' postural configurations, their events; and how such descriptions meet the criteria for a genuinely
ethnolinguistic
(as distinct from a formal or psycholinguistic) theory of conversation.
Making subsequent references
Authors: McDonald Dave
Published: January 2007

Unlike the case of an initial reference, where the choice of description is solely a matter of the speaker's intentions and his/her model of the audience, deciding how to make subsequent references to an object is a hybrid process wherein syntactic context and grammatical convention play a dominant part. This is because the expression of co-reference in discourse is highly grammaticsed. Very specialized phrases can (and often must) be used: personal, reflexive, and possessive pronouns, special determiners - "this", "my", class nouns like "thing" and "one" and so on. We would like to know the conditions that govern the appropriate use of these phrases - how do grammatical constraints interact with a speaker's goals?
Correlating summarization of multi-source news with k-way graph bi-clustering
Authors: Zhang Ya , Chu Chao-Hsien , Ji Xiang , Zha Hongyuan
Published: January 2007

With the emergence of enormous amount of online news, it is desirable to construct text mining methods that can extract, compare and highlight similarities of them. In this paper, we explore the research issue and methodology of correlated summarization for a pair of news articles. The algorithm aligns the (sub)topics of the two news articles and summarizes their correlation by sentence extraction. A pair of news articles are modelled with a weighted bipartite graph. A mutual reinforcement principle is applied to identify a dense subgraph of the weighted bipartite graph. Sentences corresponding to the subgraph are correlated well in textual content and convey the dominant shared topic of the pair of news articles. As a further enhancement for lengthy articles, ak-way bi-clustering algorithm can first be used to partition the bipartite graph into several clusters, each containing sentences from the two news reports. These clusters correspond to shared subtopics, and the above mutual reinforcement principle can then be applied to extract topic sentences within each subtopic group.
KDD-Cup 2004
Authors: Caruana Rich , Joachims Thorsten , Backstrom Lars
Published: January 2007

This paper summarizes and analyzes the results of the 2004 KDD-Cup. The competition consisted of two tasks from the areas of particle physics and protein homology detection. It focused on the problem of optimizing supervised learning to different performance measures (accuracy, cross-entropy, ROC area, SLAC-Q, squared error, average precision, top 1, and rank of last). A total of 102 groups participated in the competition, 6 of which received awards or honorable mentions. Their approaches are described in other papers in this issue of SIGKDD Explorations. In this paper we do not analyze any particular approach, but give insight into the performance of the field of competitors as a whole. We study what fraction of the participants found good solutions, how well participants were able to optimize to different performance measures, how homogeneous their submitted predictions are, and if the best submissions represent the maximal performances that could reasonably be achieved. We are keeping the KDD-Cup 2004 WWW site open and have added an automatic scoring system for new submissions in order to encourage further research in this area.
Anti-matter detection
Authors: Vogel David S. , Gottschalk Eric , Wang Morgan C.
Published: January 2007

What is the difference between matter and anti-matter? A. I. Insight's winning solution on the Particle Physics Task for the 2004 KDD Cup demonstrates how an accurate predictive model can be formulated without knowledge of the content of the data. Information on the data was not available for the modeling, including a description on the outcome to be predicted. In other words, an 80 x 150,000 grid of numbers with the header "Particle Physics" was all that was given to the 500+ registrants of this competition. Key steps in creating the winning model were interactive analysis of the variables, detection of interactions, a powerful self-organizing neural network, and customization of the 4 different error criteria.
KDD-2004 workshop report link analysis and group detection (LinkKDD-2004)
Authors: Adibi Jafar , Chalupsky Hans , Grobelnik Marko , Mladenic Dunja , Milic-Frayling Natasa
Published: January 2007

In this paper we provide a summary of the workshop on Link Analysis and Group Detection (LinkKDD-2004) held in conjunction with ACM SIGKDD 2004, on August 22, Seattle, Washington, USA. We report in details about the research issues addressed in the talks and the workshop.
The third SIGKDD workshop on mining temporal and sequential data (KDD/TDM 2004)
Authors: Unnikrishnan K. P. , Uthurusamy Ramasamy , Han Jiawei
Published: January 2007

In this short report, we provide a summary of the results, issues, and research directions on mining temporal and sequential data, discussed in TDM-2004, held in conjunction with the 10-th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2004) on August 22, 2004 in Seattle, Washington, U.S.A.
Towards a model of user mobility and registration patterns
Authors: Jain Ravi , Shivaprasad Anupama , Lelescu Dan , He Xiaoning
Published: January 2007

The evaluation of a great deal of research on ad hoc networks, as well as cellular networks, depends on models of user mobility. Many models have been developed and utilized, such as the random walk and random waypoint models. These are simple to implement and analyze but unlikely to be realistic. We develop a model based on extensive experimental data from a campus Wi-Fi LAN installation, representing traces from about 6000 users over a period of about 2 years. This data does not enable us to develop a user mobility model directly. However, as a first step, we develop a model of the time and sequence of locations at which user devices register. Note that this can be very useful, for instance to evaluate protocols that attempt to manage routing or resource allocations at different nodes. This paper reports work in progress on developing a user registration model. It shows the key time domain as well as space domain features we have extracted from the data. In particular, we show that the time features indicate heavy-tailed, although not power-law, distributions. The spatial features strongly indicate registration localization and hierarchy. The model itself can be represented as a set of probability distributions for various parameters. The modeler, for example a protocol designer, can then generate traces that conform to these distributions while varying the scale of the model in terms of the number of users. We close with a brief discussion of further work to refine and extend the model.
SimFlex
Authors: Hardavellas Nikolaos , Somogyi Stephen , Wenisch Thomas F. , Wunderlich Roland E. , Chen Shelley , Kim Jangwoo , Falsafi Babak , Hoe James C. , Nowatzyk Andreas G.
Published: January 2007

The new focus on commercial workloads in simulation studies of server systems has caused a drastic increase in the complexity and decrease in the speed of simulation tools. The complexity of a large-scale full-system model makes development of a monolithic simulation tool a prohibitively difficult task. Furthermore, detailed full-system models simulate so slowly that experimental results must be based on simulations of only fractions of a second of execution of the modelled system.This paper presents SIMFLEX, a simulation framework which uses component-based design and rigorous statistical sampling to enable development of complex models and ensure representative measurement results with fast simulation turnaround. The novelty of SIMFLEX lies in its combination of a unique, compile-time approach to component interconnection and a methodology for obtaining accurate results from sampled simulations on a platform capable of evaluating unmodified commercial workloads.
Geographic routing in city scenarios
Authors: Lochert Christian , Mauve Martin , Füßler Holger , Hartenstein Hannes
Published: January 2007

Position-based routing, as it is used by protocols like Greedy Perimeter Stateless Routing (GPSR) [5], is very well suited for highly dynamic environments such as inter-vehicle communication on highways. However, it has been discussed that radio obstacles [4], as they are found in urban areas, have a significant negative impact on the performance of position-based routing. In prior work [6] we presented a position-based approach which alleviates this problem and is able to find robust routes within city environments. It is related to the idea of position-based source routing as proposed in [1] for terminode routing. The algorithm needs global knowledge of the city topology as it is provided by a static street map. Given this information the sender determines the junctions that have to be traversed by the packet using the Dijkstra shortest path algorithm. Forwarding between junctions is then done in a position-based fashion. In this short paper we show how position-based routing can be aplied to a city scenario without assuming that nodes have access to a static street map and without using source routing.
Lambda machine overview
Authors: Creeger Mache
Published: January 2007

LMI will be introducing its next generation LISP Machine, the Lambda, for market in the spring. The major design philosophy of the Lambda machine is the concept of modularity. The system is designed so that it can exist in a large number of configurations centered around a 32 bit high performance bus.
Review of "Computational Grammar by Graeme D. Ritchie"; Sussex: The Harvester Press, 1980
Authors: Tomayko James E.
Published: January 2007

This book was developed from the author's doctoral dissertation, in which he wrote a program that conducted natural language conversations in order to study the impact that computational linguistics has on developing descriptive grammar. Ritchie does much to show how difficult it is to develop a proper grammar, and thus gives an accurate reflection of the problems of computational linguistics by describing the state of descriptive linguistics and his application of it.
Review of "The Cybernetic Imagination in Science Fiction by Patricia S. Warrick"; Cambridge, MA: The Mit Press, 1980
Authors: Tomayko James E.
Published: January 2007

This book is an exhaustive analysis of the depiction of artificial intelligence in science fiction during the period 1930--1977. It is a book of literary criticism that has importance for those involved in AI research as well as students of the SF genre and of literature in general. It is important for technologists because it is through the medium of science fiction, both in its printed and audio-visual forms, that the public receives its information and forms its impressions of AI and the potential contributions or complications that it can make. Therefore, what Ms. Warrick has to say about those impressions is worth consideration in view of creating a positive image for AI. A second area in which her book makes a contribution is in the discussion of the concept of consciousness as it applies to machine intelligence. Is the quality of consciousness necessary before an AI device can be considered truly "intelligent," or is the need to imbue the machine with consciousness simply an SF convention to make stories more real to readers who have little contact with computers? Unfortunately, no conclusions are reached regarding this question.
Selected AI-related dissertations
Authors: Humphrey Susanne M. , Krovetz Bob
Published: January 2007

The following are citations selected by title and abstract as being related to AI, resulting from a computer search, using the BRS information Technologies retrieval service, of the Dissertation Abstracts International (DAI) database produced by University Microfilms International.
Note on the KPK-table size
Authors: Messerschmidt H. J.
Published: January 2007

Ever since Clark's memorable work on perfect chess endgames, (Clark, 1977) considerable attention has been given to constructing tables to play various basic endgames perfectly. Since these tables are quite large, it is obviously important to keep the size to the absolute practical minimum without complicating the construction or usage.
The prolog phenomenon
Authors: McDermott Drew
Published: January 2007

In 1968, Carl Hewitt introduce PLANNER, a "procedural deductive system." [Hewitt 72] It featured some very innovative concepts for the theorem-proving community of that time: the procedural interpretation of deduction, pattern-directed procedure invocation, an indexed data base of assertions and programs, and nondeterminism (backtracking). A simple version was implemented by Sussman, Winograd and Charniak [Sussman 71] and used by Winograd in his exciting work on natural language. [Winograd 72] A very similar language, QA4, was implemented on the West Coast. [Rulifson 72] These languages, known by the ambitious term "AI languages," were widely perceived as providing built-in facilities that everyone would need for the next generation of AI systems, the way LISP had provided facilities for the previous one.
Review of "Artificial Intelligence Programming by Eugene Charniak, Christopher Riesback, and Drew McDermott" Lawrence Erlbaum Associates, Hillsdale, N.J.
Authors: Price Keith
Published: January 2007

Here is a volume that offers concrete examples and exercise to illustrate a wide variety of recently developed techniques used in implementing modern Artificial Intelligence programs, and describes sophisticated LISP concepts and applied them to real AI problems.
Machine translation of natural languages
Authors: Nirenburg Sergei
Published: January 2007

The field of machine translation has recently entered a new, third period in its evolution. In its early period, for roughly fifteen years from 1950 MT was an expanding field of study in which both research and development efforts were undertaken. It is well-known and well documented (Bar Hillel, 1960; ALPAC, 1966) that this early MT paradigm could not and did not produce fully automated high quality translation systems. In fact, the practical results were quite negligible for such a high-scale effort. This period also witnessed an engineering-oriented trend which considered MT primarily an engineering problem. In the positive sense, it helped promote the idea of nonnumerical computation. As another consequence, the engineering, nontheoretical attitude to MT has been inherited by the next period in MT history. A more significant and lasting influence was exerted by the less "practical" aspect of early MT research: it helped achieve advances in theoretical and computational linguistics as well as artificial intelligence.
Biologically motivated machine intelligence
Authors: Hastings Harold M. , Waner Stefan
Published: January 2007

Biological systems routinely solve problems involving pattern recognition and feature extraction. Such problems do not appear to admit similarly routine algorithmic solutions; the power of biological systems in this regard apparently arises from nonalgorithmic dynamics. It is our intention to explore, and to develop principles of, functional characteristics of natural (biological) intelligence with a view to their realization through an appropriate automation model.
Automatic indexing of natural language texts
Authors: Salton G.
Published: January 2007

In information retrieval, the stored documents and records are normally identified by sets of terms or keywords that are collectively used to represent the document content. The task of assigning the terms to the individual documents is known as indexing. Automatic indexing procedures have been developed in recent years that outperform the conventional methods based either on a manual term assignment or on a full-text indexing where the words occurring in document texts are used as index terms.
The Erlangen speech understanding project
Authors: Niemann Heinrich , Brietzmann Astrid , Hein Hans-Werner , Regel Peter
Published: January 2007

Since 1979 a project about the automatic understanding of normally spoken German sentences has been running at Erlangen /1-4/. The evolved speech understanding system should be able to speaker-independently process signals of telephone bandwidth quality. It should not be a one-purpose solution but an experimental tool to aid the development of optimized and specialized future speech understanders for many applications. This requires the ability of modular and easy exchange of its vocabulary, grammar and task specific knowledge. The vocabulary should at least include 1000 wordforms and the language accepted be as natural as possible.
Intelligent fact retrieval
Authors: Kolodner Janet , Simpson Bob , Sharpe Danny , McGreggor Brina K.
Published: January 2007

Project Support: NSF (IST division) Sept., 1981 - Sept, 1983; NIH (through Georgia Tech's Biological Research Support Group) June, 1981 - April, 1982; UPI DataNews High Speed News Wire pending: AFOSR July, 1981 - June, 1985
The EPISTLE project
Authors: Miller Lance A. , Byrd Roy , Heidon George , Jensen Karen
Published: January 2007

The experimental EPISTLE system is ultimately intended to provide intelligent applications for the processing of natural language text. Potential applications are of two types: (1) processing of alreadygenerated text, and (2) assisting in the generation of new text.
The processing of Portuguese based upon logic
Authors: Coelho Helder
Published: January 2007

The objective of this research program, under progress, is the development of feasible methods for consulting and creating databases
Research at the U. of Massachusetts at Amherst
Authors: McDonald David D.
Published: January 2007

Computational linguistics is a central area of research at in cognitive science at UMass, involving eight professors and nine graduate students with thesis work in this area across three departments. Interdisciplinary cooperation is our hallmark, with contributions from the perspectives of linguistics, artificial intelligence, and brain theory. Our work is broken down into five major projects:
Research on natural-language processing
Authors: Grosz Barbara
Published: January 2007

Research on natural-language processing at SRI spans a broad spectrum of activity. Two of our major current efforts are a pair of research projects under the sponsorship of the Defense Advanced Research Projects Agency. The TEAM project is intended to provide natural-language access to large databases via systems that are easily adaptable to a wide range of new application domains. The KLAUS project is a longer-range effort to address basic research problems in natural-language semantics, commonsense reasoning, and the pragmatics of natural-language communication. These two projects share a common core-language-processing system called DIALOGIC.
Computational realization of a generalized phrase structure grammar
Authors: Gazdar Gerald , Klein Ewan , Pullum Geoffrey , Sag Ivan , Thompson Henry
Published: January 2007

The aim of this project, due to begin in January 1982 under the auspices of Grant HR 7829/1 from the SSRC (UK), is to design, evaluate, and debug a computer realization of a generalized phrase structure grammar for a very large fragment of English. The realization will be in a form which is neutral with respect to parsing or generating sentences, and which is capable of being used with a variety of programs. Programs written in POP2 and PROLOG will be used to test the grammar.
Text knowledge bases
Authors: Simmons Robt F.
Published: January 2007

Our research is concentrated in two primary natural language research programs, one aimed at understanding expository text and the other at automated translation for technical text from German to English. (This latter project is described separately - see section from "Linguistics Research Center" above. -Ed.)
Research at Texas Instruments, Inc.
Authors: Fisher William M. , Hendler James A. , Kehler Tom P. , Michaelis Paul R. , Miller James R. , Phillips Brian , Ross Kenneth M. , Steele Shirley , Tennant Harry R. , Thompson Craig
Published: January 2007

We are developing a pseudo-parallel, message-passing control structure to allow syntactic, semantic, discourse, and pragmatic information to be accessed at any point in the analysis. The advantages of this approach are two-fold. Firstly, partial results can be exchanged among components in a timely manner to be used to constrain the search space of the components. Secondly, the control structure will permit the nature and context of errors in ill-formed input to be broadcast to other components to find ways to circumvent the error but still comprehend the input. The system is being applied to an analysis of TI's patent descriptions.
Toward computational description of written Polish
Authors: Bien Janusz S. , Szpakowicz Stanislaw
Published: January 2007

We present briefly the activity of the Warsaw University. computational linguistics team. The team is an informal group that consolidates around a seminar at the Institute of Informatics, coordinated by Prof. Zygmunt Saloni. The group adheres to a "bootstrapping methodology": we focus on developing surface linguistic descriptions which should allow the creation of efficient tools for low-level processing of natural language texts, in the hope that it will pay when more sophisticated problems are attacked.
NLP research at the Yale AI Project
Authors: Dehn Natalie
Published: January 2007

The Yale Al Project is an interdisciplinary research effort, made up primarily of computer scientists and psychologists, but also including, over the last several years, researchers trained in linguistics, philosophy, and anthropology. Current graduate students are officially affiliated with either the Computer Science or Psychology departments, but are educated, beyond general departmental requirements as Cognitive Scientists.
European AISB summer school on knowledge systems
Authors: Oatley Keith
Published: January 2007

A most successful meeting was held by the Study Group on Artificial Intelligence and Simulation of Behavior at Oxford University this summer. It took the form of a number of Britain's more distinguished workers in AI, Dr. M. B. Clowes, Mr. P. Hayes, Professor H. C. Longuet-Higgins, Mr. A. Mackworth, and Professor D. Michie each giving a series of lectures and leading discussions on the problems of how human and artificial intelligence organize and use knowledge.
Have a second look at XML files
Authors: Markus Arjen
Published: January 2007

In the December issue of the Fortran Forum (Markus, 2004) I described the format of XML files and ways to handle them in Fortran. The present paper is meant to elaborate on a few aspects of XML that were not considered then but which are at least as important to appreciate what XML is all about. Most notably: the advantages of using a strict format and internationalisation. I wish to thank Rolf Ade for his valuable comments that led to this second paper.
Performance and verification
Authors: Haverkort Boudewijn R. , Katoen Joost-Pieter
Published: January 2007

Some twentyfive years ago, the field of computer-communication system performance evaluation and the field of formal specification and verification were regarded as completely disjunct. The former field focussed on the quantitative aspects of system behaviour, expressed in measures such as delays, throughputs and loss probabilities, whereas the latter field focussed on the qualitative aspects of system behaviour, expressed in measures (or, properties) such as system liveness, deadlock freeness and safety. Over the years, however, this distinction has shown to be not always useful. In fact, we see a large variety of systems for which the qualitative behaviour cannot be decoupled from the quantitative aspect. Think for instance of communication protocols in an embedded system setting: the qualitative correctness of a protocol, without considering (absolute) timing aspects, is not enough for classifying a protocol as correct. Indeed, only when the protocol behaves as it should, and does so
in a timely manner,
the protocol can be regarded as correct. Observations of this kind have lead to a variety of integrated approaches toward performance evaluation and verification.
Probabilistic model checking in practice
Authors: Kwiatkowska Marta , Norman Gethin , Parker David
Published: January 2007

In this paper, we describe some practical applications of
probabilistic model checking,
a technique for the formal analysis of systems which exhibit stochastic behaviour. We give an overview of a selection of case studies carried out using the probabilistic model checking tool PRISM, demonstrating the wide range of application domains to which these methods are applicable. We also illustrate several benefits of using formal verification techniques to analyse probabilistic systems, including: (i) that they allow a wide range of numerical properties to be computed accurately; and (ii) that they perform a complete and exhaustive analysis enabling, for example, a study of best- and worst-case scenarios.
ProbMela and verification of Markov decision processes
Authors: Baier Christel , Ciesinski Frank , Größer Marcus
Published: January 2007

Markov decision processes (MDP) can serve as operational model for probabilistic distributed systems and yield the basis for model checking algorithms against qualitative or quantitative properties. In this paper, we summarize the main steps of a quantitative analysis for a given MDP and formula of linear temporal logic, give an introduction to the modelling language ProbMela which provides a simple and intuitive way to describe complex systems with a MDP-semantics and present the basic features of the MDP model checker LiQuor.
The existence of kernel functions for logical wire connections
Authors: Soong Norman L.
Published: January 2007

In an automated chip design environment, the designer is responsible for writing down the functional design and specifying the type of technology to be used. This is the starting point for an automated chip design system. If the design is too large, then it is partitioned into smaller designs, so that the reduced design can be processed by the system. The first phase of such a system is a placement phase. During which the cells or circuits are geometrically placed on a chip, often in terms of rows and columes.
GDOC
Authors: Ferrara Fabrizio Massimo , Batini Carlo
Published: January 2007

Release 2.0 of GDOC, a tool for computer aided design of data base applications, is described.GDOC allows interactive specification of the conceptual schema of the application, expressed in an enriched Entity-Relationship Model, produces the relevant documentation by means of traditional printouts, as well as allowing a graphical definition of the conceptual schema. Moreover GDOC automatically generates the operating programs for accessing the concepts in the schema.Experiences of use of GDOC are discussed and further research directions are outlined.
A multi-contouring algorithm
Authors: Dobes Ivan R.
Published: January 2007

This paper discusses a new line routing algorithm. The algorithm uses a line searching scheme based on topological properties of objects in a continuous plane. It is believed to have the speed, accuracy and low memory performance properties of Hightower's router. It is shown that this router has the added features that it can guarantee a connection, when possible, without resorting to an exhaustive search and it can handle "preferential" routing.
Petri-net based description, analysis and simulation of concurrent processes
Authors: Ramming Franz J.
Published: January 2007

1.1 The language CAPWhile there are a couple of programming languages which allow the representation of parallelism /1,2,5/ there is a lack for languages which allow in an as well disciplined as general manner the description of concurrency.A well defined mathematical description method for concurrent processes is given by the Petri net model /3,7,9/. It fulfils the above requirements and in addition is widely used and extremely easy to understand.This concept is integrated into the language CAP in a very elegant way: Lables are used as places, where one has in mind that a labelled statement puts a token into its label(s) after it has been processed. On the other hand the processability of a statement is controlld by "On-conditions" on labels. Every statement is processed if and only if its "On-condition" has become true. At this time, in accordance with the firing-rule (="On-condition"), "tokens" are withdrawn from certain labels used within the "On-condition" and placed into the labels of the statement.In addition various parameters may be associated to transitions thus offering a description power similar to the Macro-E-Nets /8/. On the other hand there are a lot of language-constructs to support structured programming.1.2 The analysis of CAP-programs at compile-timeSince a couple of years Petri nets are object of research. For some rather restricted subclasses of Petri nets sufficiant an necessary conditions for the topology of a net to be well-formed are known /3,4,7/. Under a well-formed net we understand a net without dead-locks being safe (no loss of information) and residue-free (independent from a certain history). Related to results by Herzog an Yoeli /4/ for a subclass of Petri nets we prove that there are six conditions for the topology of a net of the subclass of Petrinets which are used to describe the control-structure of CAP-programs so that the net is well-formed.By this we can decide at compile-time without simulation whether a CAP-program describes a life, safe and residue-free system (i. e. a useful one) or not. After having defined, what we mean ba a "Structured CAP-program" we will have the fine result that every structured CAP-program is well-formed.1.3 The simulation of systems described in CAPAs CAP allows the description of systems down to a level of specification which is comparable with the bit-level of digital systems inclusive the detailled description of the real-time-behaviour, for the processing of CAP one needs a system similar to a simulator for digital circuits. On the other hand also very global descriptions on a high level of abstraction are possible.This implies that the run-time system for CAP must be extremely adaptive. We tried to solve this problem by a very flexible and powerful table driven and event oriented simulator with the event-mechanism being directly adopted from the Petri net concept of CAP.
An approach to ECL module placement
Authors: Pluimer Mike
Published: January 2007

Placement algorithms for general logic graphs or interconnected modules exist in many forms with the acceptability of a given algorithm being dependent upon the set of design constraints imposed. This paper outlines an approach for the placement of ECL modules on a printed circuit board combining existing placement concepts and an evaluational technique called sequential netting. The primary design constraints are assumed to be in the form of rigid wiring rules.
An integrated computer-aided design system for custom LSI circuits
Authors: Barnes Donald E.
Published: January 2007

An integrated computer aided design system for the design, layout and layout verification of integrated circuits is described. The imagery required for photofabrication of an integrated circuit is created by computer from a place and interconnect data base and a design library system. The imagery created by the computer is analyzed to verify conformance to design rules and proper interconnections. Simulation files are produced for additional verification of interconnects and circuit design.
Storage declaration in the hardware description language ERES
Authors: Gardill Rudolf , Klar Rainer
Published: January 2007

The CHDL ERES is a register-transfer-language providing a nonprocedural description of hardware. This paper presents a short introduction to ERES and the description of registers, transfers and timing constraints. A global method for declaring storages is shown, which allows the modelling of multiple access as well as horizontal or vertical access.
Report on the 6th ACM international workshop on web information and data management (WIDM 2004) held at CIKM 2004
Authors: Laender Alberto H. F. , Lee Dongwon
Published: January 2007

The 6th ACM International Workshop on Web Information and Data Management (WIDM 2004) was held at the Hyatt Arlington Hotel, in Washington DC, on November 12-13, 2004, in conjunction with the 13th ACM International Conference on Information and Knowledge Management (CIKM 2004). The main objective of the workshop was to bring together researchers, industrial practitioners, and developers to discuss how Web information can be extracted, stored, analyzed, and processed to provide useful knowledge to the end users for various advanced database and Web applications. As for previous years, WIDM 2004 was sponsored by ACM SIGIR.
Workshop on the evaluation of multimedia retrieval
Authors: Westerveld Thijs , de Vries Arjen P. , de Jong Franciska M. G.
Published: January 2007

The evaluation of multimedia retrieval is a subject that has gained momentum in the last couple of years. CWI, the National Research Institute for Mathematics and Computer Science in the Netherlands, organised a workshop organised on the subject on 24 November 2004. The main aim of the workshop was to bring together researchers and practitioners in the field of multimedia retrieval to discuss the area of multimedia in general and methodology for evaluation within this area in particular. The workshop, organised by Franciska de Jong (Utwente/TNO, NL), Arjen de Vries (CWI, NL) and Thijs Westerveld (CWI, NL) was an informal half-day meeting without papers or proceedings. Because the workshop was co-located with Thijs Westerveld's PhD defence, we were able to invite Alex Hauptmann (CMU, PA, USA) to give a talk. In total six speakers were invited to present their work related to the evaluation of multimedia retrieval. The workshop started with a talk presenting multimedia retrieval in practise. Then, three talks discussed experiments in the laboratory context of the TRECVID video retrieval benchmark. The afternoon ended with a presentation of a study of interactive experiments and a talk discussing metrics for measuring multimedia retrieval effectiveness.
Variations on language modeling for information retrieval
Authors: Kraaij Wessel
Published: January 2007

Search engine technology builds on theoretical and empirical research results in the area of information retrieval (IR). This dissertation makes a contribution to the field of language modeling (LM) for IR, which views both queries and documents as instances of a unigram language model and defines the matching function between a query and each document as the probability that the query terms are generated by the document language model. The work described is concerned with three research issues.
A relational vector-space model of information retrieval adapted to images
Authors: Martinet Jean
Published: January 2007

The increase of digital image acquisition devices, combined to the growth of the Web, requires the definition of Information Retrieval (IR) models and systems providing fast access to images searched by users among large amounts of data.
Automatic summarization focusing on document genre and text structure
Authors: Seki Yohei
Published: January 2007

This dissertation proposes a new automatic summarization method focusing on
document genre
and
text structure
, and verifies its effectiveness.
"Document genre"
refers to the type of document, such as a diary or a report.
"Text structure"
refers to the functional aspects of the text and divides the text into sentence units or components, according to their functional roles. This type of structure includes both the components and their organization within the text of a specific document genre. We used text structure and document genre to extract important sentences from source documents and to generate output summaries.
Coupon replication systems
Authors: Massoulié Laurent , VojnoviĆ Milan
Published: January 2007

Motivated by the study of peer-to-peer file swarming systems à la BitTorrent, we introduce a probabilistic model of
coupon replication systems
. These systems consist of users, aiming to complete a collection of distinct coupons. Users are characterised by their current collection of coupons, and leave the system once they complete their coupon collection. The system evolution is then specified by describing how users of distinct types meet, and which coupons get replicated upon such encounters.For open systems, with exogenous user arrivals, we derive necessary and sufficient stability conditions in a layered scenario, where encounters are between users holding the same number of coupons. We also consider a system where encounters are between users chosen uniformly at random from the whole population. We show that performance, captured by sojourn time, is asymptotically optimal in both systems as the number of coupon types becomes large.We also consider closed systems with no exogenous user arrivals. In a special scenario where users have only one missing coupon, we evaluate the size of the population ultimately remaining in the system, as the initial number of users,
N
, goes to infinity. We show that this decreases geometrically with the number of coupons,
K
. In particular, when the ratio
K
/log(
N
) is above a critical threshold, we prove that this number of left-overs is of order log(log(
N
)).These results suggest that performance of file swarming systems does not depend critically on either altruistic user behavior, or on load balancing strategies such as
rarest first
.
On lifetime-based node failure and stochastic resilience of decentralized peer-to-peer networks
Authors: Leonard Derek , Rai Vivek , Loguinov Dmitri
Published: January 2007

To understand how high rates of churn and random departure decisions of end-users affect connectivity of P2P networks, this paper investigates resilience of random graphs to lifetime-based node failure and derives the expected delay before a user is forcefully isolated from the graph and the probability that this occurs within his/her lifetime. Our results indicate that systems with heavy-tailed lifetime distributions are more resilient than those with light-tailed (e.g., exponential) distributions and that for a given average degree,
k
-regular graphs exhibit the highest resilience. As a practical illustration of our results, each user in a system with
n
= 100 billion peers, 30-minute average lifetime, and 1-minute node-replacement delay can stay connected to the graph with probability 1 - 1
n
using only 9 neighbors. This is in contrast to 37 neighbors required under previous modeling efforts. We finish the paper by showing that many P2P networks are
almost surely
(i.e., with probability 1-
o
(1)) connected if they have no isolated nodes and derive a simple model for the probability that a P2P system partitions under churn.
Internet traffic classification using bayesian analysis techniques
Authors: Moore Andrew W. , Zuev Denis
Published: January 2007

Accurate traffic classification is of fundamental importance to numerous other network activities, from security monitoring to accounting, and from Quality of Service to providing operators with useful forecasts for long-term provisioning. We apply a Naïve Bayes estimator to categorize traffic by application. Uniquely, our work capitalizes on hand-classified network data, using it as input to a supervised Naïve Bayes estimator. In this paper we illustrate the high level of accuracy achievable with the \Naive Bayes estimator. We further illustrate the improved accuracy of refined variants of this estimator.Our results indicate that with the simplest of Naïve Bayes estimator we are able to achieve about 65% accuracy on per-flow classification and with two powerful refinements we can improve this value to better than 95%; this is a vast improvement over traditional techniques that achieve 50--70%. While our technique uses training data, with categories derived from packet-content, all of our training and testing was done using header-derived discriminators. We emphasize this as a powerful aspect of our approach: using samples of well-known traffic to allow the categorization of traffic using commonly available information alone.
Packet classification in large ISPs
Authors: Cohen Edith , Lund Carsten
Published: January 2007

Packet classification, although extensively studied, is an evolving problem. Growing and changing needs necessitate the use of larger filters with more complex rules. The increased complexity and size pose implementation challenges on current hardware solutions and drive the development of software classifiers, in particular, decision-tree based classifiers. Important performance measures for these classifiers are time and memory due to required high throughput and use of limited fast memory.We analyze Tier 1 ISP data that includes filters and corresponding traffic from over a hundred edge routers and thousands of interfaces. We provide a comprehensive view on packet classification in an operational network and glean insights that help us design more effective classification algorithms.We propose and evaluate decision tree classifiers with
common branches
. These classifiers have linear worst-case memory bounds and require much less memory than standard decision tree classifiers, but nonetheless, we show that on our data have similar average and worst-case time performance. We argue that common-branches exploit structure that is present in real-life data sets.We observe a strong Zipf-like pattern in the usage of rules in a classifier, where a very small number of rules resolves the bulk of traffic and most rules are essentially never used. Inspired by this observation, we propose
traffic-aware
classifiers that obtain superior average-case and bounded worst-case performance. Good average-case can boost performance of software classifiers that can be used in small to medium sized routers and are also important for traffic analysis and traffic engineering.
Achieving fair rates with ingress policing
Authors: Musacchio John , Walrand Jean
Published: January 2007

We study a simple ingress policing scheme for a stochastic queuing network that uses a round-robin service discipline, and derive conditions under which the flow rates approach a max-min fair share allocation. The scheme works as follows: Whenever any of a flow's queues exceeds a policing threshold, the network discards that flow's arriving packets at the network ingress, and does so until all of that flow's queues fall below their thresholds. To prove our results, we use previously known results relating the stability of a queuing system to the stability of its fluid limit and extend these results to relate the flow rates of the stochastic system to those of a corresponding fluid model. In particular, we consider the fluid limit of a sequence of queuing networks with increasing thresholds. Using a Lyapunov function derived from the fluid limits, we find that as the policing thresholds are increased the state of the stochastic system is attracted to a relatively smaller and smaller neighborhood surrounding the equilibrium of the fluid model. We then show how this property implies that the achieved flow rates approach the max-min rates predicted by the fluid model.
Managing server energy and operational costs in hosting centers
Authors: Chen Yiyu , Das Amitayu , Qin Wubi , Sivasubramaniam Anand , Wang Qian , Gautam Natarajan
Published: January 2007

The growing cost of tuning and managing computer systems is leading to out-sourcing of commercial services to hosting centers. These centers provision thousands of dense servers within a relatively small real-estate in order to host the applications/services of different customers who may have been assured by a service-level agreement (SLA). Power consumption of these servers is becoming a serious concern in the design and operation of the hosting centers. The effects of high power consumption manifest not only in the costs spent in designing effective cooling systems to ward off the generated heat, but in the cost of electricity consumption itself. It is crucial to deploy power management strategies in these hosting centers to lower these costs towards enhancing profitability. At the same time, techniques for power management that include shutting down these servers and/or modulating their operational speed, can impact the ability of the hosting center to meet SLAs. In addition, repeated on-off cycles can increase the wear-and-tear of server components, incurring costs for their procurement and replacement. This paper presents a formalism to this problem, and proposes three new online solution strategies based on steady state queuing analysis, feedback control theory, and a hybrid mechanism borrowing ideas from these two. Using real web server traces, we show that these solutions are more adaptive to workload behavior when performing server provisioning and speed control than earlier heuristics towards minimizing operational costs while meeting the SLAs.