A family of perfect hashing methods

Minimal perfect hash functions are used for memory efficient storage and fast retrieval of items from static sets. We present an infinite family of efficient and practical algorithms for generating order preserving minimal perfect hash functions. We show that almost all members of the family construct space and time optimal order preserving minimal perfect hash functions, and we identify the one with minimum constants. Members of the family generate a hash function in two steps. First a special kind of function into an r-graph is computed probabilistically. Then this function is refined deterministically to a minimal perfect hash function. We give strong theoretical evidence that the first step uses linear random time. The second step runs in linear deterministic time. The family not only has theoretical importance, but also offers the fastest known method for generating perfect hash functions.

The effect of spatial definition on the allocation of clients to screening clinics

We compared four strategies for inviting 91,456 women aged 50-69 years to one of six clinics for mammography screening and 40,142 men aged 60-79 years to one of 10 clinics for abdominal aortic aneurysm (AAA) screening. The strategies were invitation to the clinic nearest to the client and invitation to the clinic nearest to the client's area of residence defined by census small area, postcode and local government area. For each strategy we calculated the expected demand at each clinic and the travel distances for clients. We found that when women were allocated to mammography clinics on the basis of the local government area instead of their individual address, expected demand at one clinic increased by 60%, and 19% of clients were invited to attend a more remote clinic, entailing 99,000 km of additional travel. Similar results were obtained for men allocated to AAA clinics by their postcode of residence instead of their individual address: 55% difference in expected demand, 13% to a more remote clinic and 60,000 km of extra travel. Allocation on the basis of small areas did not show such great differences, except for travel distance, which was about 5% higher for each clinic type. We recommend that allocation of clients to screening clinics be made according to residential address, that assessment of the location of clinics be based on distances between residences and nearest clinic, but that planning new locations for clinics be aided with spatial analysis tools using small area demographic and social data. (C) 1997 Elsevier Science Ltd.

An association rule-based method to support medical image diagnosis with efficiency

In this paper, we propose a method based on association rule-mining to enhance the diagnosis of medical images (mammograms). It combines low-level features automatically extracted from images and high-level knowledge from specialists to search for patterns. Our method analyzes medical images and automatically generates suggestions of diagnoses employing mining of association rules. The suggestions of diagnosis are used to accelerate the image analysis performed by specialists as well as to provide them an alternative to work on. The proposed method uses two new algorithms, PreSAGe and HiCARe. The PreSAGe algorithm combines, in a single step, feature selection and discretization, and reduces the mining complexity. Experiments performed on PreSAGe show that this algorithm is highly suitable to perform feature selection and discretization in medical images. HiCARe is a new associative classifier. The HiCARe algorithm has an important property that makes it unique: it assigns multiple keywords per image to suggest a diagnosis with high values of accuracy. Our method was applied to real datasets, and the results show high sensitivity (up to 95%) and accuracy (up to 92%), allowing us to claim that the use of association rules is a powerful means to assist in the diagnosing task.

MDA-based re-engineering with Object-Z

This paper describes a practical application of MDA and reverse engineering based on a domain-specific modelling language. A well defined metamodel of a domain-specific language is useful for verification and validation of associated tools. We apply this approach to SIFA, a security analysis tool. SIFA has evolved as requirements have changed, and it has no metamodel. Hence, testing SIFA’s correctness is difficult. We introduce a formal metamodelling approach to develop a well-defined metamodel of the domain. Initially, we develop a domain model in EMF by reverse engineering the SIFA implementation. Then we transform EMF to Object-Z using model transformation. Finally, we complete the Object-Z model by specifying system behavior. The outcome is a well-defined metamodel that precisely describes the domain and the security properties that it analyses. It also provides a reliable basis for testing the current SIFA implementation and forward engineering its successor.