bluuebunny/crossref_metadata_2025 huggingface dataset:
Adaptive inter-piconet scheduling in small scatternets
Authors: Mišić Vojislav B. , Mišić Jelena
Published: January 2007

Inter-piconet scheduling in a Bluetooth scatternet may be performed in an adaptive manner, so as to minimize end-to-end packet delays. Using the theory of queues with vacations, we analyze the impact of different values of scatternet parameters on end-to-end delays, and then investigate the possibility of minimization of the aforementioned delays. We show that such minimization is possible for scatternets with both Slave/Slave and Master/Slave bridges, and that it should be based on inter-piconet traffic. We also describe simple algorithms that enable the scatternet to achieve near minimum delays in a wide range of traffic parameter values.
Facilitating cooperative learning in hypermedia systems
Authors: Haake Jörg M. , Pfister Hans-Rüdiger , Wessner Martin
Published: January 2007

Distributed organizations as well as virtual universities need support for cooperative learning processes. This led to the new major research area computer-supported cooperative (or collaborative) learning. We propose an approach to hypermedia-based collaborative learning environments which supports a wide range of synchronous and asynchronous types of cooperative learning as well as smooth transitions between these learning modes. A framework for building such environments consisting of virtual learning rooms, learning nets, and learning protocol is presented. These concepts are implemented in the CROCODILE prototype developed at GMDIPSI.
Openness in shared hypermedia workspaces
Authors: Haake Jörg M. , Wiil Uffe K. , Nürnberg Peter J.
Published: January 2007

Group work requires much flexibility regarding both the organization of shared workspaces and the organization of collaborative work. Shared hypermedia workspaces can provide this flexibility. However, this requires the provision of openness with respect to both the hypermedia workspace and the collaboration support offered in such a collaborative open hypermedia system. In this paper we address the issue of how to identify key requirements of open collaborative hypermedia systems. We start with a scenario in order to come up with a preliminary set of requirements. We then apply a regular schema to generate a more comprehensive set of requirements for open collaborative hypermedia systems.
A framework for medical information science
Authors: Blum Bruce
Published: January 2007

A one day workshop on the topic "A Framework for Medical Information Science" was held in October. Three issues were considered: what is Medical Information Science, what are the key research issues, and what are the educational needs. Because of the brevity of the workshop and scope of the topic, no summary conclusions were developed. Individual papers and position statements will be published. This paper reviews the workshop and some of the principal issues discussed.
Microprocessor controlled functional stimulator utilizing myoelectric inputs
Authors: Stutman P. S.
Published: January 2007

A self-contained, user-worn, electrical stimulator, incorporating a C/MOS micro-processor as the controller is described. The prototype is aimed at restoring function in upper extremities such as elbow and digit flexors, to those with upper motor neuron lesions. EMGs from user controllable muscles are input to control the micro-processor and effect stimulation. Device characteristics are a function of the internal program which may be changed to accomodate different clinical situations. The processor has also been used to attempt to minimize the effect of change at the electrode tissue interface. Emphasis has been placed on designing a producible, reasonably priced system. Tests with normal subjects are reported. Additional uses are discussed.
A microcomputer-based control and communication system for the severely disabled
Authors: Doubler James A. , Childress Dudley S. , Strysik John S.
Published: January 2007

A microcomputer-based environmental control and communication system for the severely disabled has been developed. By puffing and sipping on a tube the user can store messages in computer memory and control a number of peripheral devices. A scanning method of operation is employed in which characters are selected for message building or control purposes from lists displayed on a CRT. An interface system is presently being developed to allow the computer to control peripheral devices by transmitting coded signals over the power mains.
An adaptable communications and control system for motor- and sensory-handicapped people
Authors: Spector David
Published: January 2007

This paper describes, in general terms, a proposed portable device to aid people with significant impairment of motor and/or sensory functions. The emphasis is on a flexible microprocessor-based system composed of input modules, output modules, and an internal semantic representation. This system organization is easily expandable to accommodate new hardware, easily customizable to meet the needs of a particular user, and made of standard components for ease of manufacturing.
Geriatric applications of Bayesian networks and survival analysis
Authors: Marshall Adele
Published: January 2007

The overall aim of this project is to combine the approach of Bayesian belief networks with that of survival analysis. The analysis can take advantage of the benefits of continuous data and censoring from survival analysis but still have the ability to represent causal relationships by using Bayesian belief networks. We wish to apply the methodology to data from the medical domain, in particular data for lengths and outcomes of spells in geriatric departments. This application of the model to include dynamic aspects of geriatric data is likely to lead to a greater understanding of how diseases are caused and what factors affect duration of an illness or length of spell in hospital. Such factors are clearly of interest to hospital administrators and health care managers.
Classification and feature selection applied to breast cancer diagnosis
Authors: Managasarian Olvi
Published: January 2007

Mathematical programming techniques are applied to the problems of classification, feature selection and clustering. The resulting classification and feature selection algorithms have been applied to the problem of breast cancer diagnosis. The clustering algorithms have been applied to the problem of grouping breast cancer patients with similar prognosis, as determined by survival curves (Kaplan-Meier).
Classification of protein structure motif conformations
Authors: Glasgow Janice
Published: January 2007

Similar to the concept of scene analysis in vision, molecular scene analysis is concerned with the processes of reconstruction and classification of complex molecular images. Such analyses rely on the availability of a priori information in the form of protein structure motifs. Research in this project has involved the study, development and implementation of data mining tools for obtaining such structural motifs. The rapid growth of protein databases has created a demand for novel and efficient techniques for the classification of motif conformations which can be used to anticipate or predict potential substructures in protein images based on primary sequence information.
Multistrategic data mining in a clinical meningoencephalitis database
Authors: Tsumoto Shusaku
Published: January 2007

This project aims at inducing as much information as possible from clinical databases. Until now, the following six methods are applied to a clinical database (meningoencephalitis):1. association rule induction,2. decision trees with genetic algorithm based feature selection,3. decision tree induction with random sampling,4. rough set based rule induction,5. logit analysis6. linear discriminant analysis.Experimental results show that knowledge which medical experts did not expect was extracted by different methods. The research will be extended to other methods and databases.
An asymptotically optimal greedy algorithm for large optical burst switching systems
Authors: Andrew Lachlan L. H. , Baryshnikov Yuliy , Coffman E. G. , Hanly Stephen V. , White Jolyon
Published: January 2007

As the number of wavelengths in OBS systems increases, the utilization achievable for a given blocking probability can be made to approach 100%. This paper shows that this property applies to a wavelength allocation algorithm of greedy type. Another property of this rule, one shared by most other wavelength assignment algorithms, is that, since lost traffic tends to occur near destinations, where the resource usage wasted by such traffic is large, very low blocking probabilities are important for efficient operation. To help identify regions of low blocking probability, we derive an asymptotically exact condition for zero blocking probabilities; it has a form reminiscent of the stability condition of the M/G/1 queue.
Hard deadline queueing system with application to unified messaging service
Authors: Lin Wuqin , Liu Zhen , Stavropoulos Harry , Xia Cathy H.
Published: January 2007

We consider a queueing system with jobs having hard deadlines. This is motivated by recent emerging unified messaging service applications. The service time of a job is assumed to be known upon arrival. A job will be lost if not being served by its deadline. For the single-server system, we propose an on-line ED-Push algorithm that is easy to implement and can achieve near-optimal performance in terms of minimizing the loss probability. Performance analyses for the underlying M/M/l+D and G/D/1+D systems are then provided. We also give approximation on the loss probability for the system with multiple servers under least workload routing scheme. The numerical results show that ED-Push algorithm performs well.
Scalability and efficiency in multi-relational data mining
Authors: Blockeel Hendrik , Sebag Michèle
Published: January 2007

Efficiency and Scalability have always been important concerns in the field of data mining, and are even more so in the multi-relational context, which is inherently more complex. The issue has been receiving an increasing amount of attention during the last few years, and quite a number of theoretical results, algorithms and implementations have been presented that explicitly aim at improving the efficiency and Scalability of multi-relational data mining approaches. With this article we attempt to present a structured overview.
State of the art of graph-based data mining
Authors: Washio Takashi , Motoda Hiroshi
Published: January 2007

The need for mining structured data has increased in the past few years. One of the best studied data structures in computer science and discrete mathematics are graphs. It can therefore be no surprise that graph based data mining has become quite popular in the last few years.This article introduces the theoretical basis of graph based data mining and surveys the state of the art of graph-based data mining. Brief descriptions of some representative approaches are provided as well.
Graph-based relational learning
Authors: Holder Lawrence B. , Cook Diane J.
Published: January 2007

Graph-based relational learning (GBRL) differs from logic-based relational learning, as addressed by inductive logic programming techniques, and differs from frequent subgraph discovery, as addressed by many graph-based data mining techniques. Learning from graphs, rather than logic, presents representational issues both in input data preparation and output pattern language. While a form of graph-based data mining, GBRL focuses on identifying novel, not necessarily most frequent, patterns in a graph-theoretic representation of data. This approach to graph-based data mining provides both simplifications and challenges over frequency-based approaches. In this paper we discuss these issues and future directions of graph-based relational learning.
Detecting context-differentiating terms using competitive learning
Authors: Bauer Travis L. , Leake David B.
Published: January 2007

Personal information agents monitor ongoing user information accesses in order to provide users with context-relevant information. Providing the needed information requires effective methods for identifying the user's task context, based on available information. For user browsing tasks, one approach to context identification is to extract context-determining terms from the documents that the user consults. The thesis of this article is (1) that term extraction for personal information agents can be done by learning terms whose occurrence frequencies have a large variance over time, (2) that indexing and retrieval based on these terms can be at least as effective as standard information retrieval techniques, and (3) that this information can be learned without comprehensive corpus analysis, making it suitable for use in personal information retrieval.We have developed an unsupervised term extraction algorithm, WordSieve, that learns individualized context-differentiating terms for document indexing and retrieval. This article presents a new version of WordSieve, compares its design and performance to our initial approach, and assesses its effectiveness for a controlled personal information retrieval task, compared to three common indexing techniques requiring statistics about the global corpus. In the experiments, the new version of WordSieve generates task-relevant indices of comparable or better quality to common indexing techniques, using only local information.
Design studies for a financial management system for micro-credit groups in rural india
Authors: Parikh Tapan , Ghosh Kaushik , Chavan Apala
Published: January 2007

In this paper we describe the design process, results and observations obtained in designing a user interface for managing community-based financial institutions in rural India. The primary users are semi-literate village women from local communities. We present detailed observations from our field visits and the resulting evolution in our design vision. We describe a successful design artifact that is the result of this process, and list several important features that contributed to its success. We conclude with the current state of our work and our plans for the future.
Applying heuristics to perform a rigorous accessibility inspection in a commercial context
Authors: Paddison Claire , Englefield Paul
Published: January 2007

Accessibility heuristics have been developed to compliment the accessibility guidelines. The use of Web accessibility heuristics in heuristic evaluations can ensure that a greater range of special needs will be considered, from visual to cognitive impairments. Key advantages of heuristics are conciseness, memorablity, meaningfulness and insight. The heuristics can be used effectively to understand which areas of a site have accessibility issues and can provide useful insight into how to create a solution. However, the heuristics will not tell evaluators whether a Web site conforms to legislation. Studies have confirmed the common belief that heuristics should not replace knowledge but act to cue the deeper body of knowledge defined by the guidelines; it is essential that evaluators be given accessibility education before completing a heuristic evaluation using the accessibility heuristics.
Probabilistic routing in intermittently connected networks
Authors: Lindgren Anders , Doria Avri , Schelén Olov
Published: January 2007

We consider the problem of routing in intermittently connected networks. In such networks there is no guarantee that a fully connected path between source and destination exist at any time, rendering traditional routing protocols unable to deliver messages between hosts. We propose a probabilistic routing protocol for such networks.
Low-power DoS attacks in data wireless LANs and countermeasures
Authors: Noubir Guevara , Lin Guolong
Published: January 2007

In this paper we investigate the resiliency to jamming of data protocols, such as IP, over WLAN. We show that, on existing WLAN, an adversary can successfully jam data packets at a very low energy cost. Such attacks allow a set of adversary nodes disseminated over an area to prevent communication, partition an ad hoc network, or force packets to be routed over adversary chosen paths. The ratio of the jamming pulses duration to the transmission duration can be as low as 10--4. We investigate and analyze the performance of using various coding schemes to improve the robustness of wireless LANs for IP packets transmission. A concatenated code that is simple to decode and can maintain a low Frame Error Rate (FER) under a jamming effort ratio of 15%. We argue that LDPC codes will be very suitable to prevent this type of jamming. We investigate the theoretical limits by analyzing the performance derived from upper bounds on binary error-control codes. We also propose an efficient anti-jamming technique for IEEE802.11b.
Power efficient gathering of correlated data: optimization, NP-completeness and heuristics
Authors: Cristescu Răzvan , Vetterli Martin
Published: January 2007

This paper studies the interaction between the communication costs in a sensor network and the structure of the data that it measures. We formulate an optimization problem for power efficient data gathering and show that the problem is NP-complete. We propose scalable, distributed and efficient heuristics for solving this problem and show by numerical simulations that the power consumption can be significantly improved over direct transmission or the shortest path tree. Our algorithms provide solutions close to a computationally heavy heuristic used as benchmark, simulated annealing, which is provably optimal in the limit.
Optimum transmit range and capacity of mobile infostation networks
Authors: Yuen Wing Ho , Yates Roy D.
Published: January 2007

A mobile infostation network stipulates all transmissions to occur when nodes are in proximity. In this paper, the effect of transmit range on the capacity of four transmission strategies is studied. We show that a stipulated transmit range improves the capacity relative to the reference strategy with an unconstrained transmit range. This indicates an optimal trade-off exists between spatial transmission concurrency and spectral efficiency on individual links. The optimal number of neighbors is invariant to node density, and is between 0.6 to 1.2 for our transmission strategies. This result should be contrasted to a magic number of 6 to 8 neighbors for multihop networks, where the expected forward progress per hop is maximized. This reflects the different optimization criteria of mobile infostation and multihop ad hoc networks. In addition, the capacity per unit area increases linearly with node density. This is counter-intuitive but can be explained using a rescaling argument drawn from percolation theory.
Microprocessors for non-numeric processing
Authors: Zaky S. G.
Published: January 2007

The problem of processing of non-numeric data has received considerable attention in the last few years. This is primarily motivate by the pressing needs in the are a of data base management. It has long been recognized that the parallel processing capabilities of an associative processor are fundamentally well suited to this environment. However, the complexity and cost of truely associative memories make this approach impractical. In this paper, the demands that non-numeric processing place on memory and processor hardware are discussed. Some emerging trends are presented, and a suggestion is given regarding the development of a “general purpose” microprocessor that is suited to this environment.

Basically, the microprocessor discussed here is capable of performing simple search and update functions on a high speed, serial data stream. Therefore, it is suited to any application where such a situation is encountered, such as in digital communications.
Graph notation for arrays
Authors: Ehrbar Hans G.
Published: January 2007

A graph-theoretical notation for array concatenation represents arrays as bubbles with arms sticking out, each arm with a specified number of "'fingers". Bubbles with one arm are vectors, with two arms matrices, etc. Arrays can only hold hands, i.e., "contract" along a given pair of arms, if the arms have the same number of fingers. There are three array concatenations: outer product, contraction, and direct sum. Special arrays are the unit vectors and the diagonal array, which is the branching point of several arms. Outer products and contractions are independent of the order in which they are performed and distributive with respect to the direct sum. Examples are given where this notation clarifies mathematical proofs.
A symmetry-based formalism for array subtyping
Authors: Shafarenko A.
Published: January 2007

This paper presents an array algebra based on the concept of symmetry. The symmetries taken into account are translational, affine and polyhedral symmetry as well as the access symmetry inherent in distributed arrays. The full set of data-parallel array operations is represented in terms of four fundamental skeletons: Map, Juxtapose, Select, and Concatenate; which are strongly typed and overloaded for all combinations of operand symmetries. A hierarchy of three further skeletons are used as parameters to Map in order to express reductions: commutative-associative, associative but not commutative, and neither associative nor commutative. Any user-defined part of the computation is represented in the form of scalar functions as skeleton parameters, without any loss of generality. Successful type inference in the presence of subtyping is enabled by a homomorphism restriction imposed on all overloadings of the skeletons. As a result, we are able to infer the most symmetric type of any well-formed term, which is usually the cheapest one to compute.
A surgical Virtual Environment for navigating experience
Authors: Luursema Jan-Maarten , Kommers Piet
Published: January 2007

A computer generated pre-surgical planning and teaching environment is proposed for training and evaluating novice surgeons. Although this environment is generic and can be put into practice in any medical specialisation where such 3D imaging techniques are in use, in this project we specifically focus on vascular surgery. This environment will be developed as part of the DIME project (Distributed Interactive Medical Exploratory). We are building this Virtual Environment (VE) using a new navigational metaphor, which includes modelling the learning process, rather than the operating room.
Design and analysis of Hybrid Indirect Transmissions (HIT) for data gathering in wireless micro sensor networks
Authors: Culpepper Benjamin J. , Dung Lan , Moh Melody
Published: January 2007

Sensor networks have many potential applications in biology, physics, medicine, and the military. One major challenge in sensor networks is to maximize network life under the constraint of limited power supply. The paper addresses energy-efficiency in the context of routing and data gathering. A new protocol is proposed: Hybrid Indirect Transmission (HIT). HIT is based on a hybrid architecture that consists of one or more clusters, each of which is based on multiple, multi-hop indirect transmissions. In order to minimize both energy consumption and network delay, parallel transmissions are used both among multiple clusters and within a cluster. This is made possible by having each sensor independently compute a medium access controlling TDMA schedule. The computation within each sensor is intelligent yet simple. Formal analysis shows that it requires O(n) space and O(n x logn) time complexities, and O(1) setup messages prior to the computation, where n is the total number of sensors. HIT does not require sensor nodes with CDMA capability, or the remote base station to compute a data gathering schedule. Performance is evaluated by simulating and comparing HIT with three other existing protocols, including Low Energy Adaptive Clustering Hierarchy (LEACH), Power Efficient Gathering for Sensor Information System (PEGASIS), and Direct Transmission. Results have shown that HIT greatly reduces both energy consumption and network delay; it also maintains longer network life compared to these three existing protocols. Security issues and a potential application of HIT in biomedical sensing technology are also rigorously discussed. This work is significant to the advancement of energy-efficient micro sensor networks; the proposed protocol is promising and would contribute to the use of wireless micro sensor networks in future biomedical sensing technologies.
Greedy algorithms for optimizing multivariate Horner schemes
Authors: Ceberio Martine , Kreinovich Vladik
Published: January 2007

For univariate polynomials
f
(
x
1
), Horner's scheme provides the fastest way to compute a value. For multivariate polynomials, several different version of Horner's scheme are possible; it is not clear which of them is optimal. In this paper, we propose a greedy algorithm, which it is hoped will lead to good computation times.The univariate Horner scheme has another advantage: if the value
x
1
is known with uncertainty, and we are interested in the resulting uncertainty in
f
(
x
1
), then Horner scheme leads to a better estimate for this uncertainty that many other ways of computing
f
(
x
1
). The second greedy algorithm that we propose tries to find the multivariate Horner scheme that leads to the best estimate for the uncertainty in
f
(
x
1
,...,
x
n
).
The TOP-C parallel model and symbolic algebra
Authors: Cooperman Gene
Published: January 2007

The TOP-C parallel model was specifically designed to be optimal for many symbolic algebra algorithms. Symbolic algebra problems are irregular and differ from typical problems of numerical analysis in two respects.1. They have large amounts of intermediate swell.2. They are usually not able to make good use of data parallelism.The TOP-C model was developed on the basis of experience over ten years. The model was first implemented for distributed memory for GCL (GNU Common LISP), and is currently available as ParGCL [1]. That work was extended to ParGAP [3], a binding to the interactive language GAP (Groups, Algorithms and Programming). Finally, a C/C++ version, Task Oriented Parallel C/C++, lent its acronym to the TOP-C model [2].A sign of the maturity of TOP-C is the parallelization of Geant4 (Geometry and Tracking) [4]. Geant4 is a million-line program for the simulation of particle-matter interaction used in the design of collider experiments at CERN. Current issues facing parallelization include the slowness of RAM [5] and the need for semi-automated marshalling (serialization of objects) [6].
Improving classification of microarray data using prototype-based feature selection
Authors: Hanczar Blaise , Courtine Mélanie , Benis Arriel , Hennegar Corneliu , Clément Karine , Zucker Jean-Daniel
Published: January 2007

This paper addresses the problem of improving accuracy in the machine-learning task of classification from microarray data. One of the known issues specifically related to microarray data is the large number of inputs (genes) versus the small number of available samples (conditions). A promising direction of research to decrease the generalization error of classification algorithms is to perform gene selection so as to identify those genes which are potentially most relevant for the classification. Classical feature selection methods are based on direct statistical methods. We present a reduction algorithm based on the notion of prototypegene. Each prototype represents a set of similar gene according to a given clustering method. We present experimental evidence of the usefulness of combining prototype-based feature selection with statistical gene selection methods for the task of classifying adenocarcinoma from gene expressions.
Differential expression, class discovery and class prediction using S-PLUS and S+ArrayAnalyzer
Authors: O'Connell Michael
Published: January 2007

Microarrays are a powerful experimental platform, allowing simultaneous studies of gene expression for thousands of genes under different experimental conditions. However there is much biological variability induced throughout the experimental process that can obscure the biological signals of interest. As such, the need for experimental design, replication and statistical rigor are now widely recognized. Statistical hypothesis testing has become the accepted differential expression analysis approach and many classification and prediction methods used in class discovery and class prediction now incorporate stochastic modeling components.This paper provides a review of statistical analysis approaches to the analysis of data from microarray experiments. This includes discussion of experimental design, data management, preprocessing, differential expression, clustering and class prediction, reporting and annotation. The review is illustrated with the analysis of an experiment with 3 experimental conditions using the Affymetrix murine chip mgu 74av2; and with descriptions of available functionality in the statistical analysis software S-PLUS and its associated module for microarray analysis, S+ArrayAnalyzer.
Loss-based estimation with cross-validation
Authors: Dudoit Sandrine , van der Laan Mark J. , Keleş Sündüz , Molinaro Annette M. , Sinisi Sandra E. , Teng Siew Leng
Published: January 2007

Current statistical inference problems in genomic data analysis involve parameter estimation for high-dimensional multivariate distributions, with typically unknown and intricate correlation patterns among variables. Addressing these inference questions satisfactorily requires: (i) an intensive and thorough search of the parameter space to generate good candidate estimators; (ii) an approach for selecting an optimal estimator among these candidates; and (iii) a method for reliably assessing the performance of the resulting estimator. We propose a unified loss-based methodology for estimator construction, selection, and performance assessment with cross-validation. In this approach, the parameter of interest is defined as the risk minimizer for a suitable loss function and candidate estimators are generated using this (or possibly another) loss function. Cross-validation is applied to select an optimal estimator among the candidates and to assess the overall performance of the resulting estimator. This general estimation framework encompasses a number of problems which have traditionally been treated separately in the statistical literature, including multivariate outcome prediction and density estimation based on either uncensored or censored data. This article provides an overview of the methodology and describes its application to the prediction of biological and clinical outcomes (possibly censored) using microarray gene expression measures.
Meta-clustering of gene expression data and literature-based information
Authors: Glenisson Patrick , Mathys Janick , De Moor Bart
Published: January 2007

The current tendency in the life sciences to spawn ever growing amounts of high-throughput assays has led to a situation where the interpretation of data and the formulation of hypotheses lag the pace at which information is produced. Although the first generation of statistical algorithms scrutinizing single, large-scale data sets found their way into the biological community, the great challenge to connect their results to existing knowledge still remains. Despite the fairly large number of biological databases that is currently available, a lot of relevant information is found in free-text format (such as textual annotations, scientific abstracts and full publications). In this paper we explore how an
integrated
analysis of expression data and literature-extracted information can reveal biologically meaningful clusters not identified when using microarray information alone. The joint analysis is validated in terms of transcriptional regulation.
Statistical methods for joint data mining of gene expression and DNA sequence database
Authors: Curran Marla D. , Liu Hong , Long Fan , Ge Nanxiang
Published: January 2007

One of the purposes of microarray gene expression experiments is to identify genes regulated under specific cellular conditions. With the availability of putative transcription factor binding motifs, it is now possible to relate gene expression pattern to the pattern of transcription factor binding sites (TFBS), as well as study how TFBS interact with each other to control gene expression. The objectives of this study are to develop a systematic approach for combining data from microarray gene expression experiments and the corresponding regulatory motif patterns in order to delineate gene regulation mechanisms. A secondary goal is to develop a predictive model for finding similarly regulated genes. Three consecutive procedures are proposed for such data mining activities. First, a linear mixed-effect model is fit to data from microarray gene expression experiments and potential regulated (positive) genes are identified based on a specific biological hypothesis. Putative TFBS are then retrieved for the identified positive genes and randomly selected controls. Second, a cluster analysis is conducted to reduce collinearity among the binding sites. In the third step, logistic regression is applied to choose the best model to predict gene type (positive, control) based on the numerous TFBS predictors. The above approach was applied to an internal example and a model was developed to predict up-regulated genes in activated
T
-helper (
Th
) cells. Using a leave-one-out cross- validation scheme, the model has an 18.9% false positive rate and a 41.7% false negative rate.
Machine learning in low-level microarray analysis
Authors: Rubinstein Benjamin I. P. , McAuliffe Jon , Cawley Simon , Palaniswami Marimuthu , Ramamohanarao Kotagiri , Speed Terence P.
Published: January 2007

Machine learning and data mining have found a multitude of successful applications in microarray analysis, with gene clustering and classification of tissue samples being widely cited examples. Low-level microarray analysis -- often associated with the pre-processing stage within the microarray life-cycle -- has increasingly become an area of active research, traditionally involving techniques from classical statistics. This paper explores opportunities for the application of machine learning and data mining methods to several important low-level microarray analysis problems: monitoring gene expression, transcript discovery, genotyping and resequencing. Relevant methods and ideas from the machine learning community include semi-supervised learning, learning from heterogeneous data, and incremental learning.
Overview of the 2003 KDD Cup
Authors: Gehrke Johannes , Ginsparg Paul , Kleinberg Jon
Published: January 2007

This paper surveys the 2003 KDD Cup, a competition held in conjunction with the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD) in August 2003. The competition focused on mining the complex real-life social network inherent in the e-print arXiv (arXiv.org). We describe the four KDD Cup tasks: citation prediction, download prediction, data cleaning, and an open task.
Exploiting relational structure to understand publication patterns in high-energy physics
Authors: McGovern Amy , Friedland Lisa , Hay Michael , Gallagher Brian , Fast Andrew , Neville Jennifer , Jensen David
Published: January 2007

We analyze publication patterns in theoretical high-energy physics using a relational learning approach. We focus on four related areas: understanding and identifying patterns of citations, examining publication patterns at the author level, predicting whether a paper will be accepted by specific journals, and identifying research communities from the citation patterns and paper text. Each of these analyses contributes to an overall understanding of theoretical high-energy physics.
Multirelational data mining 2003
Authors: Dzeroski Saso , De Raedt Luc , Wrobel Stefan
Published: January 2007

In this report, we briefly review the second International Workshop on Multi-Relational Data Mining (MRDM-03), which was organized by the authors and held in Washington, D.C. on August 27th, 2003 as part of the workshop program of the ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-03). the goal of the workshop was to bring together researchers and practitioners of Data Mining and interested in methods and applications of finding patterns in expressive languages from multi-relational, complex and/or structured data.
String storage and searching for data base applications
Authors: Copeland George P.
Published: January 2007

User and hardware cost trends dictate that data base systems should provide more complete functionality, simplicity of use, and reliability by increasing the amount of hardware present in the system. These goals are accomplished with a simple hardware arrangement within a one-dimensional cellular storage system called INDY. The INDY backend kernel is intended as a powerful tool for implementing all data models. The INDY cellular storage array is intended to provide functionality that is difficult to implement efficiently using a conventional hardware arrangement. It allows a simple implementation of improved data independence at high speeds. INDY simultaneously satisfies the time windows of future hardware technologies and user requirements.The importance of strings as a mechanism for defining abstract data types for data base languages is discussed in more detail in another paper. In that paper, a language called STRING is introduced which allows names of data objects to be semantically defined as variable-length strings and compared based on string pattern membership. This paper is concerned with the implementation of string storage and searching required by the STRING language. Implementation of higher level structures and searching requirements (such as sets, rows, tables and hierarchies) on the INDY kernel is treated elsewhere.
Text file inversion
Authors: Bird R. M. , Newsbaum J. B. , Trefftzs J. L.
Published: January 2007

This paper compares inversion of text files with inversion of more structured records. The unique characteristics of textual data which restrict the utility of inversion are identified and discussed. Inversion is shown to be useful only for small, static data bases, and when full text search is not required.
Unboundedly parallel simulations via recurrence relations
Authors: Greenberg Albert G. , Lubachevsky Boris D. , Mitrani Isi
Published: January 2007

New methods are presented for parallel simulation of discrete event systems that, when applicable, can usefully employ a number of processors much larger than the number of objects in the system being simulated. Abandoning the distributed event list approach, the simulation problem is posed using recurrence relations. We bring three algorithmic ideas to bear on parallel simulation:
parallel prefix computation, parallel merging
, and
iterative folding
. Efficient parallel simulations are given for (in turn) the G/G/1 queue, a variety of queueing networks having a global first come first served structure (e.g., a series of queues with finite buffers), acyclic networks of queues, and networks of queues with feedbacks and cycles. In particular, the problem of simulating the arrival and departure times for the first
N
jobs to a single G/G/1 queue is solved in time proportional to
N/P
+ log
P
using
P
processors.
Techniques for efficient inline tracing on a shared-memory multiprocessor
Authors: Eggers S. J. , Keppel David R. , Koldinger Eric J. , Levy Henry M.
Published: January 2007

While much current research concerns multiprocessor design, few traces of parallel programs are available for analyzing the effect of design trade-offs. Existing trace collection methods have serious drawbacks: trap-driven methods often slow down program execution by more than 1000 times, significantly perturbing program behavior; microcode modification is faster, but the technique is neither general nor portable.

This paper describes a new tool, called MPTRACE, for collecting traces of multithreaded parallel programs executing on shared-memory multiprocessors. MPTRACE requires no hardware or microcode modification; it collects complete program traces; it is portable; and it reduces execution-time dilation to less than a factor 3. MPTRACE is based on inline tracing, in which a program is automatically modified to produce trace information as it executes. We show how the use of compiler flow analysis techniques can reduce the amount of data collected and therefore the runtime dilation of the traced program. We also discuss problematic issues concerning buffering and writing of trace data on a multiprocessor.
Probabilistic language analysis of weighted voting algorithms
Authors: Moser Louise E. , Kapur Vikas , Melliar-Smith P. M.
Published: January 2007

We present a method of analyzing the performance of weighted voting algorithms in a fault-tolerant distributed system. In many distributed systems, some processors send messages more frequently than others and all processors share a common communication medium, such as an Ethernet. Typical fault-tolerant voting algorithms require that a certain minimum number of votes be collected from different processors. System performance is significantly affected by the time required to collect those votes. We formulate the problem of weighted voting in terms of probabilistic languages and then use the calculus of generating functions to compute the expected delay to collect that number of votes. An application of the method to a particular voting algorithm, the Total protocol, is given.
Approximate analysis of reader and writer access to a shared resource
Authors: Johnson Theodore
Published: January 2007

In this paper we present a queue that has two classes of customers: readers and writers. Readers access the resource concurrently and writers access the resource serially. The queue discipline is FCFS: readers must wait until all writers that arrived earlier have completed service, and vice versa. The approximation can predict both the expected waiting times for readers and writers and the capacity of the queue. The queue can be used for the analysis of operating system and software resources that can be accessed both serially and concurrently, such as shared files. We have used the queue to analyze the performance of concurrent B-tree algorithms.
A calculus of variations approach to file allocation problems in computer systems
Authors: Pattipati Krishna R. , Wolf Joel , Deb Somnath
Published: January 2007

This paper is concerned with the parameter optimization in closed product-form queueing networks. Our approach is to combine the techniques of the calculus of variations with the mean value analysis (MVA) recursion of closed queueing networks. We view the MVA recursion as nonlinear difference equations describing a multi-stage system, wherein a stage corresponds to the network population, and the response times at each node constitute the state variables of the multi-stage system. This viewpoint leads to a two-point boundary value problem , in which the forward system corresponds to the MVA recursion and the backward system corresponds to an MVA-like adjoint recursion. The method allows for a very general class of objective functions, and the adjoint equations provide the necessary information to compute the gradient of the cost function. The optimization problem can then be solved by any of the gradient-based methods. For the special case when the objective function is the network delay function, the gradient vector is shown to be related to the moments of the queue lengths. In addition, the adjoint vector offers the potential for the on-line adaptive control of queueing networks based on the state information (e.g., actual degree of multi-programming, response times at the devices.) The theory is illustrated via application to the problem of determining the optimal disk routing probabilities in a large scale, modern I/O (Input/Output) subsystem. A subsequent paper will deal with extensions of the theory to multi-class networks.
An approximate analysis of the LRU and FIFO buffer replacement schemes
Authors: Dan Asit , Towsley Don
Published: January 2007

In this paper, we develop approximate analytical models for predicting the buffer hit probability under the Least Recently Used (LRU) and First In First Out (FIFO) buffer replacement policies under the independent reference model. In the case of the analysis of the LRU policy, the computational complexity for estimating the buffer hit probability is
O
(
KB
) where
B
is the size of the buffer and
K
denotes the number of items having distinct access probabilities. In the case of the FIFO policy, the solution algorithm is iterative and the computational complexity of each iteration is
O
(
K
). Results from these models are compared to exact results for models originally developed by King [KING71] for small values of the buffer size,
B
, and the total number of items sharing the buffer,
D
. Results are also compared with results from a simulation for large values of
B
and
D
. In most cases, the error is extremely small (less than 0.1%) for both LRU and FIFO, and a maximum error of 3% is observed for very small buffer size (less than 5) when the access probabilities are extremely skewed. To demonstrate the usefulness of the model, we consider two applications. In our first application, we compare the LRU and FIFO policies to an optimal static buffer allocation policy for a database consisting of two classes of data items. We observe that the performance of LRU is close to that of the optimal allocation. As the optimal allocation requires knowledge of the access probabilities, the LRU policy is preferred when this information is unavailable. We also observe that the LRU policy always performs better than the FIFO policy in our experiments. In our second application, we show that if multiple independent reference streams on mutually disjoint sets of data compete for the same buffer, it is better to partition the buffer using an optimal allocation policy than to share a common buffer.
Performance evaluation of a commercial cache-coherent shared memory multiprocessor
Authors: Jog Rajeev , Vitale Philip L. , Callister James R.
Published: January 2007

This paper describes an approximate Mean Value Analysis (MVA) model developed to project the performance of a small-scale shared-memory commercial symmetric multiprocessor system. The system, based on Hewlett Packard Precision Architecture processors, supports multiple active user processes and multiple execution threads within the operating system.

Using detailed timing for hardware delays, a customized approximate closed queueing model is developed for the multiprocessor system. The model evaluates delays due to bus and memory contention, and cache interference. It predicts bus bandwidth requirements and utilizations for the bus and memory controllers. An extension to handle I/O traffic is outlined.

Applications are profiled on the basis of execution traces on uniprocessor systems to provide inputs parameters for the model. Performance effects of various detailed architectural tradeoffs (memory interleaving, lower memory latencies) are examined. The sensitivity of overall system performance to various parameters is explored. Preliminary measurements of uniprocessor systems are compared against the model predictions. A prototype multiprocessor system is under development. We intend to validate the modeling results against measurements.
An analytic model of multistage interconnection networks
Authors: Willick Darryl L. , Eager D. L.
Published: January 2007

Multiprocessors require an interconnection network to connect processors with memory modules. The performance of the interconnection network can have a large effect upon overall system performance, and, therefore, methods are needed to model and compare alternative network architectures.

This paper is concerned with evaluating the performance of multistage interconnection networks consisting of
k
×
s
switching elements. Examples of such networks include omega, binary n-cube and baseline networks. We consider clocked, packet switched networks with buffers at switch output ports. An analytical model based on approximate Mean Value Analysis is developed, then validated through simulations.