Internet of Things (IoT) is one of the trending topics in the technological revolution of the last decade. The huge amount of sensors composing IoT systems implies the need for powerful back-end infrastructures that find a perfect habitat in cloud services. Nowadays, many players offer cloud services and it is thus essential for the user to consciously learn which one mostly fits his needs. Among cloud providers, three conquered a leader position in the sector: 1) Amazon Web services; 2) Google cloud platform; and 3) Microsoft azure. In this article, we thoroughly test these providers to highlight their strengths and weaknesses. To produce relevant results, we stress a back-end infrastructure designed to handle a national-sized network of IoT nodes. Our analysis is not limited to the cloud provider performance as a whole, while it also investigates and compares several cloud components separately. As part of the contribution, we also test different time-series databases and we discuss the advantages of such kind of technologies. Finally, an in-depth pricing analysis is conducted to better understand the differences between each platform from an economic perspective.

Semi-supervised learning techniques are gaining importance in the scenario of constantly growing data collections. CBIR systems must be able to autonomously analyze the patterns available, to fully exploit unlabeled data with the final objective of identifying an optimal representation space where data belonging to the same semantic class are close to each other. In this work we propose to adopt relevance feedback as a mean of collecting information about the semantic classes perceived by the user and to exploit this information for a long-term learning process where a more effective feature space can be obtained by a proper metric learning technique and class labels can be automatically assigned to unlabeled patterns. The process can iterate as new data become available thus providing a tool for successfully managing new incoming data. The experimental results will confirm the advantages of the proposed learning approach.

In this paper we propose a novel technique to implement secure and efficient applications for the agri-food certification chain. Our proposal relies on RFID technologies which is probably the most relevant enabling solution for ubiquitous IoT systems. We analyze a recently introduced and promising RFID tag and we prove it is possible to certify its genuineness without installing any third party application upon the consumer smartphone. The proposed solution is based on a lightweight security technique which provides the mirroring of the tag identifier combined with the encryption of a NDEF formatted file.

The classical Bloom filter data structure is a crucial component of hundreds of cryptographic protocols. It has been used in privacy preservation and secure computation settings, often in conjunction with the (somewhat) homomorphic properties of ciphers such as Paillier's. In 2014, a new data structure extending and surpassing the capabilities of the classical Bloom filter has been proposed. The new primitive, called spatial Bloom filter (SBF) retains the hash-based membership-query design of the Bloom filter, but applies it to elements from multiple sets. Since its introduction, the SBF has been used in the design of cryptographic protocols for a number of domains, including location privacy and network security. However, due to the complex nature of this probabilistic data structure, its properties had not been fully understood. In this paper, we address this gap in knowledge and we fully explore the probabilistic properties of the SBF. In doing so, we define a number of metrics (such as emersion and safeness) useful in determining the parameters needed to achieve certain characteristics in a filter, including the false positive probability and inter-set error rate. This will in turn enable the design of more efficient cryptographic protocols based on the SBF, opening the way to their practical application in a number of security and privacy settings.

Extracting accurately the shape of a leaf is a crucial step in image-based plant identification systems. The partial or total absence of textures on leaf surface and the high color variability of leaves belonging to same species make shape as the main recognition element. For such reason, leaf segmentation plays a decisive role in the leaf recognition process. Even though many general segmentation methods have been proposed in the last decades, leaf segmentation presents specific challenges. In particular, a pixel-level precision is required in order to highlight fine scale boundary structures and discriminate similar global shapes. Moreover, even if the input image can typically be taken in controlled conditions, where the leaf is the only visible object over a white background, the user taking the picture is not necessarily an expert and the conditions are often not ideal: the leaf exhibits specular reflections, casts shadows, the background is never exactly white and is usually non-uniform, and the image can be blurry. Recently, a solution for the problem at hand has been proposed in [1] where leaf segmentation is carried out by estimating the probability distribution of foreground and background pixels. However, several drawbacks appear in this formulation due to challenging leaves like pine needles, false positives detection related to shadows and false negatives detection related to specularities. Prior distributions and post-processing operations are employed to tackle such problem, with the risk of hurting the final leaf shape. In this paper we introduce a new solution by training a pixel-wise classifier [3] that learns filter responses associated to background and foreground regions in images of leaves. Our classifier is trained by selecting positive (leaf) and negative (non-leaf) feature samples that lie on the neighboorhod of the leaf boundary thus focusing learning only on sensitive pixels. Such classifier is then applied to each pixel location of a given unknown test image. This provides a score map that we then threshold using two different thresholds to detect pixels that belong to foreground and background with a high level of probability. With these pixels at hand we initialize an EM algorithm with a good initial estimate of foreground and background cluster parameters in the saturation-value color space, differently from [1] which has to initialize the EM segmentation with the same values for all the images. The other difference with [1] is that we can consider as unlabeled data only the pixels that are in the neighborhood of the detected leaf boundary. This allows to keep focusing on segmenting correctly the pixels around the leaf boundary, and in practice it is enough to get a good segmentation of the other pixels, which are easier to classify. For evaluation we use the Leafsnap Field image dataset publicly available online [1] where different leaves of different species are acquired against solid background and variable light conditions thus simulating typical images that a user could provide for plant recognition. To train our pixel-wise classifier we randomly select one image for each species and we manually produce segmentation and thicker contours to discriminate between positive and negative training samples placed in the neighborhood of boundary. Since segmentation ground truth is not available and its manual production for thousands of images would require an inestimable amount of time, we considered a subset of the original Field dataset. Our testing set is made of 300 images: 150 images for which the EM approach of [1] performs already well thus producing faithful segmentation in accordance with the leaf shape plus 150 more challenging images for which EM partially or totally fails. The general behavior of different methods can be qualitatively appreciated looking at Fig. 1 where results returned by Leafsnap, Leafsnap without post-processing (marked with *), GrabCut and our method are reported. As the reader can see comparing ground truth details with real segmentations, it is confirmed that post-processing hurts quality of (a) Leaf image (b) Ground truth

Sketch recognition for forensic applications is a very challenging task and several solutions have been recently proposed. Considering that real mug shot databases can be very large, one important aspect to consider in this scenario is also the efficiency of the search procedure. This work proposes the use of shape features for a preliminary selection of the candidate photos to be successively analyzed by more complex state-of-the-art techniques. The proposed features can be computed and matched in a very short time, and at the same time they are able to significantly reduce the search space, thus allowing to speed up the recognition process.

A new approach for video-based face recognition is presented in this paper. The proposed technique is based on the use of key points and related descriptors for image representation. In particular this work introduces a general approach to extend to the temporal dimension the analysis usually carried out on single images, with the aim of deriving a more stable and compact representation of video information. The algorithm, which can easily be coupled with different techniques for key point extraction and representation, has been designed taking into account two fundamental requirements in this application scenario: recognition accuracy and efficiency of the matching process. The extensive experiments carried out on public datasets using a specific implementation based on SURF demonstrate the validity of the proposed technique.

Face images to be included into machine readable travel documents have to fulfill quality requirements defined by international ISO standards. The concept of quality in this context extends the common idea of image quality: usually a bad quality image presents visual defects such as blurring or noise while, according to ISO/ICAO standard, other factors could make a given sample a poor quality image (e.g., presence of dark glasses or mouth open). The verification of face image conformance to ISO/ICAO standards is carried out mostly by humans today, through visual inspection, since a totally automatic evaluation is still not satisfactory. The objective of this work is to present the BioLab-ICAO framework, an evaluation benchmark which will be made available to the scientific community, designed to encourage the research on this topic; it consists of a large ground truth database, a well-defined testing protocol, and baseline algorithms for image compliance verification.

Palmprint recognition is a challenging problem, mainly due to low quality of the pattern, large nonlinear distortion between different impressions of the same palm and large image size, which makes feature extraction and matching computationally demanding. This paper introduces a high-resolution palmprint recognition system based on minutiae. The proposed system follows the typical sequence of steps used in fingerprint recognition, but each step has been specifically designed and optimized to process large palmprint images with a good tradeoff between accuracy and speed. A sequence of robust feature extraction steps allows to reliably detect minutiae; moreover, the matching algorithm is very efficient and robust to skin distortion, being based on a local matching strategy and an efficient and compact representation of the minutiae. Experimental results show that the proposed system compares very favorably with the state of the art.

This correspondence proposes new candidate list reduction criteria for fingerprint indexing approaches. The basic idea is that, given a query fingerprint, the initial set of scores produced by an indexer could contain useful information to reduce the candidate list. Novel reduction criteria have been proposed, and extensive experiments have been carried out over five publicly available benchmarks, using two state-of-the-art fingerprint indexing techniques. Although quite simple, the proposed criteria achieved remarkable results, allowing a substantial reduction of the candidate list: for instance, at 1% error rate, the average penetration rate of a state-of-the-art minutiae-based indexer decreases from 27% to 3.9% on FVC2000 DB2. The new reduction criteria are applicable to any indexing approach, since they only require a list of scores as input.

Computation of local orientations is a primary step in fingerprint recognition. A large number of approaches have been proposed in the literature, but no systematic quantitative evaluations have been done yet. We implemented and tested several well know methods and a plethora of their variants over a novel, specifically designed, benchmark, made available in the FVC-onGoing framework. We proved that parameter optimizations, pre- and post-processing stages can markedly improve accuracy of the baseline methods on bad quality fingerprints. Finally, in this paper we propose a novel adaptive method which selectively exploits accuracy of local-based analysis and learning-based global methods, thus achieving the overall best performance on a challenging dataset.

This work focuses on performance assessment of software applications designed to evaluate the compliance of a face image to the ISO/ICAO standards for machine readable travel documents. In this paper we describe the new large database (of compliant and non-compliant images) we gathered, the associated testing protocol and the preliminary results measured on some existing algorithms.

A minutiae-based template is a very compact representation of a fingerprint image and for a long time it has been assumed that it did not contain enough information to allow the reconstruction of the original fingerprint. This work proposes a novel approach to reconstruct fingerprint images from standard templates and investigates to what extent the reconstructed images are similar to the original ones (i.e., those the templates were extracted from). The efficacy of the reconstruction technique has been assessed by estimating the success chances of a masquerade attack against nine different fingerprint recognition algorithms. The experimental results show that the reconstructed images are very realistic and that, although it is unlikely they can fool a human expert, there is a high chance to deceive state-of-the-art commercial fingerprint recognition systems.

For a long time it has been assumed that a minutiae-based fingerprint template did not contain enough information to allow reconstructing the original fingerprint image. This work proposes an approach to reconstruct fingerprint images from ISO standard templates and investigates to what extent the reconstructed fingerprints are similar to the original ones. The results show that the reconstructed images have a very good quality and may be used to attack existing fingerprint recognition systems. Systematic studies to understand the success chances of such attacks are currently being carried out

This paper is concerned with the performance evaluation of fingerprint verification systems. After an initial classification of biometric testing initiatives, we explore both the theoretical and practical issues related to performance evaluation by presenting the outcome of the recent Fingerprint Verification Competition (FVC2004). FVC2004 was organized by the authors of this work for the purpose of assessing the state-of-the-art in this challenging pattern recognition application and making available a new common benchmark for an unambiguous comparison of fingerprint-based biometric systems. FVC2004 is an independent, strongly supervised evaluation performed at the evaluators' site on evaluators' hardware. This allowed the test to be completely controlled and the computation times of different algorithms to be fairly compared. The experience and feedback received from previous, similar competitions (FVC2000 and FVC2002) allowed us to improve the organization and methodology of FVC2004 and to capture the attention of a significantly higher number of academic and commercial organizations (67 algorithms were submitted for FVC2004). A new, "Light" competition category was included to estimate the loss of matching performance caused by imposing computational constraints. This paper discusses data collection and testing protocols, and includes a detailed analysis of the results. We introduce a simple but effective method for comparing algorithms at the score level, allowing us to isolate difficult cases (images) and to study error correlations and algorithm "fusion." The huge amount of information obtained, including a structured classification of the submitted algorithms on the basis of their features, makes it possible to better understand how current fingerprint recognition systems work and to delineate useful research directions for the future.

Attacking fingerprint-based biometric systems by presenting fake fingers at the sensor could be a serious threat for unattended applications. This work introduces a new approach for discriminating fake fingers from real ones, based on the analysis of skin distortion. The user is required to move the finger while pressing it against the scanner surface, thus deliberately exaggerating the skin distortion. Novel techniques for extracting, encoding and comparing skin distortion information are formally defined and systematically evaluated over a test set of real and fake fingers. The proposed approach is privacy friendly and does not require additional expensive hardware besides a fingerprint scanner capable of capturing and delivering frames at proper rate. The experimental results indicate the new approach to be a very promising technique for making fingerprint recognition systems more robust against fake-finger-based spoofing attempts.

This paper introduces a new noise model for the generation of synthetic fingerprints. Starting from several visual observations about noise in real fingerprints, the limits of the uniform noise generation adopted in our previous work are pointed out and a new model able to create realistic coherent noise is proposed. The results are very promising: the new images generated are definitely more realistic than those obtained with the original method.

Digital watermarking has recently emerged as a solution to the problem of providing guarantees about copyright protection of digital images. However, several problems related to robustness of invisible watermarking techniques to malicious or nonmalicious attacks still remain unsolved. However, visible watermarking is an effective technique for preventing unauthorized use of an image, based on the insertion of a translucent mark, which provides immediate claim of ownership. This paper describes an approach for adaptive positioning of a visible watermark based on the analysis of local characteristics of the host image. Watermark positioning deals with the problem of selecting the most suitable image position to place the visible mark. Our efforts have been directed to find the best region of the host image where watermark insertion can ensure robustness and unobtrusiveness to the watermark

This paper introduces a new face recognition approach that allows face variations (produced by aging and other appearance changes) to be dealt with. During the initial learning, a set of MKL subspaces is created for each individual, starting from the feature vectors extracted through a bank of Gabor filters. Then, during the normal system operation, an incremental updating technique can be applied to adjust the subspaces without recalculating the face models from scratch; this makes the method able to cope with gradual changes that occur over time. The results of the experimentation performed on three face databases prove the advantages of the proposed approach with respect to other well-known techniques; in particular, our method achieves better accuracy and higher robustness against face variations.

Reliable and accurate fingerprint recognition is a challenging pattern recognition problem, requiring algorithms robust in many contexts. FVC2000 competition attempted to establish the first common benchmark, allowing companies and academic institutions to unambiguously compare performance and track improvements in their fingerprint recognition algorithms. Three databases were created using different state-of-the-art sensors and a fourth database was artificially generated; 11 algorithms were extensively tested on the four data sets. We believe that FVC2000 protocol, databases, and results will be useful to all practitioners in the field not only as a benchmark for improving methods, but also for enabling an unbiased evaluation of algorithms.

This work introduces the multispace Karhunen-Loeve (MKL) as a new approach to unsupervised dimensionality reduction for pattern representation and classification. The training set is automatically partitioned into disjoint subsets, according to an optimality criterion; each subset then determines a different KL subspace which is specialized in representing a particular group of patterns. The extension of the classical KL operators and the definition of ad hoc distances allow MKL to be effectively used where KL is commonly employed. The limits of the standard KL transform are pointed out, in particular, MKL is shown to outperform KL when the data distribution is far from a multidimensional Gaussian and to better cope with large sets of patterns, which could cause a severe performance drop in KL.

Map building is an important issue for all the applications in mobile robotics in which the environment is unknown and, in general, in order to have a robot exhibit a fully autonomous behavior. A major problem in map building is due to the imprecision of sensor measures. In this paper, we propose a technique, called elastic correction, for correcting the dead-reckoning errors made during the exploration of an environment by a robot capable of identifying landmarks. Knowledge being acquired is modeled by a relational graph whose vertices and arcs represent, respectively, landmarks and routes. Elastic correction is based on an analogy between the graph modeling the environment and a mechanical structure: the map is regarded as a truss where each route is an elastic bar and each landmark a node. Errors are corrected as a result of the deformations induced from the forces arising within the structure as inconsistent measures are taken. The elasticity parameters characterizing the structure are used to model the uncertainty on odometry. The paper presents results from simulations showing the effectiveness of the method for reducing the overall metric error and proving its robustness with reference to topological errors and to unpredictable sensor errors.

Introduces a method for the generation of synthetic fingerprint images. Gabor-like space-variant filters are used for iteratively expanding an initially empty image containing just one or a few seeds. A directional image model, whose inputs are the number and location of the fingerprint cores and deltas, is used for tuning the filters according to the underlying ridge orientation. Very realistic fingerprint images are obtained after the final noising-and-rendering stage.

Describes a color-based approach to effectively resolve query-by-examples in an image database. We present a prototype database system designed to store and query a collection of ceramics. Our case study is a database of images representing ceramics from the International Museum of Ceramics in Faenza. We consider statistical features on color distribution, not requiring a strong segmentation procedure to detect the object from the background. Results on a collection of about 2000 images are reported providing a validation of the approach.

In this work, we introduce a new approach to automatic fingerprint classification. The directional image is partitioned into "homogeneous" connected regions according to the fingerprint topology, thus giving a synthetic representation which can be exploited as a basis for the classification. A set of dynamic masks, together with an optimization criterion, are used to guide the partitioning. The adaptation of the masks produces a numerical vector representing each fingerprint as a multidimensional point, which can be conceived as a continuous classification. Different search strategies are discussed to efficiently retrieve fingerprints both with continuous and exclusive classification. Experimental results have been given for the most commonly used fingerprint databases and the new method has been compared with other approaches known in the literature: As to fingerprint retrieval based on continuous classification, our method gives the best performance and exhibits a very high robustness.

In this paper we describe VisTool, a prototype tool for querying relational databases by means of the visual query language VISIONARY.

This paper introduces a new efficient method for estimating the local ridge-line density in digital images. A mathematical characterization of the local frequency of sinusoidal signals is given, and a 2D-model is developed in order to approximate the ridge-line patterns. Experimental results obtained through a discrete implementation of the method are presented both in terms of accuracy and efficiency.

Minutiae correspond essentially to the terminations and bifurcations of fingerprint patterns. Since the quality of fingerprint images is often low, automatic minutiae detection is a very difficult task and the extraction algorithms produce a large number of false alarms. We present an approach to minutiae filtering based on a neural network. The minutiae neighborhoods extracted by the algorithm presented by us (1997) are normalized with respect to rotation and scale, and their dimensionality is reduced via a KL transform. A neural classifier, whose topology has been designed to exploit the minutiae duality, is employed to perform the neighborhoods classification. The filtering proposed, as confirmed by simulations, allows a significant improvement in the overall performance to be achieved.

A major problem in map building is due to the imprecision of sensor measures. In this paper we propose a technique, called elastic correction, for correcting the dead-reckoning errors made during the exploration of an unknown environment by a robot capable of identifying landmarks. Knowledge of the environment being acquired is modelled by a relational graph whose vertices and arcs represent, respectively, landmarks and inter-landmark routes. Elastic correction is based on an analogy between this graph and a mechanical structure: the map is regarded as a truss where each route is an elastic bar and each landmark a node. Errors are corrected as a result of the deformations induced from the forces arising within the structure as inconsistent measures are taken. The uncertainty on odometry is modelled by the elasticity parameters characterizing the structure.

Data warehousing systems enable enterprise managers to acquire and integrate information from heterogeneous sources and to query very large databases efficiently. Building a data warehouse requires adopting design and implementation techniques completely different from those underlying operational information systems. Though most scientific literature on the design of data warehouses concerns their logical and physical models, an accurate conceptual design is the necessary foundations for building a DW which is well-documented and fully satisfies requirements. In this paper we formalize a graphical conceptual model for data warehouses, called Dimensional Fact model, and propose a semi-automated methodology to build it from the pre-existing (conceptual or logical) schemes describing the enterprise relational database. The representation of reality built using our conceptual model consists of a set of fact schemes whose basic elements are facts, measures, attributes, dimensions and hierarchies; other features which may be represented on fact schemes are the additivity of fact attributes along dimensions, the optionality of dimension attributes and the existence of non-dimension attributes. Compatible fact schemes may be overlapped in order to relate and compare data for drill-across queries. Fact schemes should be integrated with information of the conjectured workload, to be used as the input of logical and physical design phases; to this end, we propose a simple language to denote data warehouse queries in terms of sets of fact instances.

We address the problem of performance evaluation in biometric verification systems. By formulating the optimum Bayesian decision criterion for a verification system and by assuming the data distributions to be multinormals, we derive two statistical expressions for calculating theoretically the false acceptance and false rejection rates. Generally, the adoption of a Bayesian parametric model does not allow for obtaining explicit expressions for the calculation of the system errors. As far as biometric verification systems are concerned, some hypotheses can be reasonably adopted, thus allowing simple and affordable expressions to be derived. By using two verification system prototypes. Based on hand shape and human face, respectively, we show our results are well founded.

Most automatic systems for fingerprint comparison are based on minutiae matching. Minutiae are essentially terminations and bifurcations of the ridge lines that constitute a fingerprint pattern. Automatic minutiae detection is an extremely critical process, especially in low-quality fingerprints where noise and contrast deficiency can originate pixel configurations similar to minutiae or hide real minutiae. Several approaches have been proposed in the literature; although rather different from each other, all these methods transform fingerprint images into binary images. In this work we propose an original technique, based on ridge line following, where the minutiae are extracted directly from gray scale images. The results achieved are compared with those obtained through some methods based on image binarization. In spite of a greater conceptual complexity, the method proposed performs better both in terms of efficiency and robustness.

A new structural approach to the fingerprint classification problem is presented. The fingerprint directional image is segmented in regions by minimizing the variance of the element directions within the regions. From the segmentation of the directional image a relational graph compactly summarising the macro-structure of the fingerprint is derived. Inexact graph matching techniques can be adopted to compare the obtained graph with the model graphs in order to classify the fingerprint, according to a given classification scheme.

Exploration is a central issue for autonomous agents which must carry out navigation tasks in environments of which a description is not known a priori. In our approach the environment is described, from a symbolic point of view, by means of a graph; clustering techniques allow for further levels of abstraction to be defined, leading to a multi-layered representation. In this work we propose an unsupervised exploration algorithm in which several agents cooperate to acquire knowledge of the environment at the different abstraction levels. All agents are equal and pursue the same local exploration strategy; nevertheless, the existence of multiple levels of abstraction in the environment representation allows for the agents' behavior to differ. Agents carry out exploration at different abstraction levels, aimed at reproducing an ideal exploration profile; each agent dynamically selects its exploration level, based on the current demand. Inter-agent communication allows for the agents to share their knowledge and to record acquaintances of the other agents. A communication protocol for organizing teams of agents is provided.

The problem of organizing and exploiting spatial knowledge for navigation is an important issue in the field of autonomous mobile systems. In particular, partitioning the environment map into connected clusters allows for significant topological features to be captured and enables decomposition of path-planning tasks through a divide-and-conquer policy. Clustering by discovery is a procedure for identifying clusters in a map being learned by exploration as the agent moves within the environment, and yields a valid clustering of the available knowledge at each exploration step. In this work, we define a fitness measure for clustering and propose two incremental heuristic algorithms to maximize it. Both algorithms determine clusters dynamically according to a set of topological and metric criteria. The first one is aimed at locally minimizing a measure of "scattering" of the entities belonging to clusters, and partially rearranges the existing clusters at each exploration step. The second estimates the positions and dimensions of clusters according to a global map of density. The two algorithms are compared in terms of optimality, efficiency, robustness, and stability.

The index selection problem (ISP) is an important optimization problem in the physical design of databases. The aim of this paper is to show that ISP, although NP-hard, can in practice be solved effectively through well-designed algorithms. We formulate ISP as a 0-1 integer linear program and describe an exact branch-and-bound algorithm based on the linear programming relaxation of the model. The performance of the algorithm is enhanced by means of procedures to reduce the size of the candidate index set. We also describe heuristic algorithms based on the solution of a suitably defined knapsack subproblem and on Lagrangian decomposition. Finally, computational results on several classes of test problems are given. We report the exact solution of large-scale ISP instances involving several hundred indexes and queries. We also evaluate one of the heuristic algorithms we propose on very large-scale instances involving several thousand indexes and queries and show that it consistently produces very tight approximate (and sometimes provably optimal) solutions. Finally, we discuss possible extensions and future directions of research.

Database optimizers require statistical information about data distributions in order to evaluate result sizes and access plan costs for processing user queries. In this context, we consider the problem of estimating the size of the projections of a database relation, when measures on attribute domain cardinalities are maintained in the system. Our main theoretical contribution is a new formal model, the AD (active domain) model, which is valid under the hypotheses of attribute independence and uniform distribution of attribute values, derived considering the difference between the time-invariant domain (the set of values that an attribute can assume) and the time-dependent ("active") domain (the set of values that are actually assumed, at a certain time). Early models developed under the same assumptions are shown to be formally incorrect. Since the AD model is computationally highly demanding, we also introduce an approximate, easy-to-compute model, the A/sup 2/D (approximate active domain) model that, unlike previous approximations, yields low errors on all the parameter space of the active domain cardinalities. Finally, we extend the A/sup 2/D model to the case of nonuniform distributions and present experimental results confirming the good behavior of the model.>

Building autonomous systems, self-learning while moving in an unknown environment, finds a variety of challenging applications. This paper presents a new approach, called clustering by discovery, for identification of clusters in a map which is being learned by exploration. The concomitance of exploration and clustering, we argue, is a mandatory feature for an autonomous system, hence the clustering technique we propose is an incremental process performed while the system is learning the map. Clusters supply an abstract description of the environment and can be used to decrease the complexity of the navigational tasks. The environment is viewed as a map of distinctive places which we assume to be sensed and recognized by the system. The presence of distinctive places and the environment scale are the only facts which we assume known apriori to the system. Clustering by discovery is based on a heuristic indicator called scattering, whose increment is minimized at each exploration step compatibly with a connectivity constraint imposed on clusters. Scattering is defined according to a number of functional and structural requirements. Two variants are presented, and their performance is discussed on a sample of maps including a real urban map and some randomly generated ones. In particular, one of the variants shows robust behaviour in terms of independence of the exploration strategy adopted.>

The operational efficiency of a relational DBMS is greatly dependent on the effectiveness of the physical design. A problem of considerable interest for the DBA is to provide an efficient set of access structures taking into account both memory constraints and workload characteristics. The paper presents an approximation algorithm which produces a near-optimal solution to the secondary index selection problem for the entire set of DB relations, given that primary access structures have already been chosen.