Most research into similarity search in metric spaces relies on the triangle inequality property. This property allows the space to be arranged according to relative distances to avoid searching some subspaces. We show that many common metric spaces, notably including those using Euclidean and Jensen-Shannon distances, also have a stronger property, sometimes called the four-point property: In essence, these spaces allow an isometric embedding of any four points in three-dimensional Euclidean space, as well as any three points in two-dimensional Euclidean space. In fact, we show that any space that is isometrically embeddable in Hilbert space has the stronger property. This property gives stronger geometric guarantees, and one in particular, which we name the Hilbert Exclusion property, allows any indexing mechanism which uses hyperplane partitioning to perform better. One outcome of this observation is that a number of state-of-the-art indexing mechanisms over high-dimensional spaces can be easily refined to give a significant increase in performance; furthermore, the improvement given is greater in higher dimensions. This therefore leads to a significant improvement in the cost of metric search in these spaces.

In this paper, we propose a technique for automatic element detection from Laser Induced Breakdown Spectroscopy (LIBS) spectra. The presented approach uses a technique derived from information retrieval and, more specifically, from the Vector Space Model, to compute the similarity between spectra of elements and samples. These spectra, obtained by LIBS methods, can be represented as sequences of peaks of light emissions of specific wavelengths and intensities. In text retrieval, vectors are built using terms of the vocabulary and weight assessing the relevance of terms in documents or queries. In our case, peaks play the role of terms, elements that of documents, and samples that of queries. We will discuss how to define vectors, weights, and similarity between spectra. Experiments prove the validity of the method.

Efficient processing of similarity joins is important for a large class of data analysis and data-mining applications. This primitive finds all pairs of records within a predefined distance threshold of each other. However, most of the existing approaches have been based on spatial join techniques designed primarily for data in a vector space. Treating data collections as metric objects brings a great advantage in generality, because a single metric technique can be applied to many specific search problems quite different in nature. In this paper, we concentrate our attention on a special form of join, the Self Similarity Join, which retrieves pairs from the same dataset. In particular, we consider the case in which the dataset is split into subsets that are searched for self similarity join independently (e. g, as in a distributed computing environment). To this end, we formalize the abstract concept of ¿-Cover, prove its correctness, and demonstrate its effectiveness by applying it to two real implementations on a real-life large dataset.

In order to become an effective complement to traditional Web-scale text-based image retrieval solutions, content-based image retrieval must address scalability and efficiency issues. In this paper we investigate the possibility of caching the answers to content-based image retrieval queries in metric space, with the aim of reducing the average cost of query processing, and boosting the overall system throughput. Our proposal exploits the similarity between the query object and the cache content, and allows the cache to return approximate answers with acceptable quality guarantee even if the query processed has never been encountered in the past. Moreover, since popular images that are likely to be used as query have several near-duplicate versions, we show that our caching algorithm is robust, and does not suffer of cache pollution problems due to near-duplicate query objects. We report on very promising results obtained with a collection of one million high-quality digital photos. We show that it is worth pursuing caching strategies also in similarity search systems, since the proposed caching techniques can have a significant impact on performance, like caching on text queries has been proven effective for traditional Web search engines.

Similarity search structures for metric data typically bound object partitions by ball regions. Since regions can overlap, a relevant issue is to estimate the proximity of regions in order to predict the number of objects in the regions' intersection. This paper analyzes the problem using a probabilistic approach and provides a solution that effectively computes the proximity through realistic heuristics that only require small amounts of auxiliary data. An extensive simulation to validate the technique is provided. An application is developed to demonstrate how the proximity measure can be successfully applied to the approximate similarity search. Search speedup is achieved by ignoring data regions whose proximity to the query region is smaller than a user-defined threshold. This idea is implemented in a metric tree environment for the similarity range and "nearest neighbors" queries. Several measures of efficiency and effectiveness are applied to evaluate proposed approximate search algorithms on real-life data sets. An analytical model is developed to relate proximity parameters and the quality of search. Improvements of two orders of magnitude are achieved for moderately approximated search results. We demonstrate that the precision of proximity measures can significantly influence the quality of approximated algorithms.

This paper describes the processing of queries, expressing conditions on the content of images, in large image databases.The query language assumes that a semantic interpretation of the image content is available (i.e. an image symbolic interpretation), as result of an image analysis process.The image query language addresses important aspects of the image interpretations resulting from image analysis, by defining partial conditions on the composition of the complex objects, requirements on tkir degree of recognition, and requirements on their position in tk image interpretation.Particukzr emphasis is given on the definition of suitable content-based access structures to make more ejjicient the query processing.An approach based on multi-level signatures is adopted.The query is pre-processed on the signatures to jilter-out most of the images not sati~ing the query.Finally, an evaluation of the ejjiciency and precision of the signature technique is given.

The conventional models of authorization have been designed for database systems supporting the hierarchical, network, and relational models of data. However, these models are not adequate for next-generation database systems that support richer data models that include object-oriented concepts and semantic data modeling concepts. Rabitti, Woelk, and Kim [14] presented a preliminary model of authorization for use as the basis of an authorization mechanism in such database systems. In this paper we present a fuller model of authorization that fills a few major gaps that the conventional models of authorization cannot fill for next-generation database systems. We also further formalize the notion of implicit authorization and refine the application of the notion of implicit authorization to object-oriented and semantic modeling concepts. We also describe a user interface for using the model of authorization and consider key issues in implementing the authorization model.

The signature file access method has proved to be a convenient indexing technique, in particular for text data Because it can deal with unformatted data, many application domains have shown interest in signature file techniques, e.g., office information systems, statistical and logic databases.We argue that multimedia databases should also take advantage of this method, provided convenient storage structures for organizing signature tiles are available, Our main concern here is the dynamic organization of signatures based on a partitioning paradigm called Quick Filter.A signature file is partitioned by a hashing function and the partitions are orgamzed by linear hashing, Thorough performance evaluation of the new scheme is provided, and it is compared with single-level and multdevel storage structures Results show that quick filter is economical in space and very convenient for applications dealing with large files of dynamic data, and where user queries result in signatures with high weights.These characteristics are particularly interesting for multimedia databases, where integrated access to attributes, text and images must be provided.

A signature file acts as a filtering mechanism to reduce the amount of data that needs to be searched during query evaluation. Even though several techniques for organizing and searching signature files have been proposed in literature, they have serious limitations when applied to multimedia databases, where integrated access methods to text and image content are needed. A new signature technique, called Quick Filter, is proposed in the paper. According to this technique, signatures are divided into partitions, each of which holds signatures sharing the same characteristic key. As a result, it is possible to determine if the signatures in a partition satisfy a query by merely examining the key. Partitions not matching the key need not be searched. This method is based on dynamic hashing since signatures are hashed into partitions according to the keys and the file size, computed algorithmically from the signatures. Implementation of this technique is illustrated using an example and is verified by analytical performance evaluation. The result is a signature technique which satisfies the requirements for access methods in multimedia databases: dynamicity, with respect to insertions and updates, good query processing performance on large databases for high-weight queries.

Query processing in a multimedia document system is described. Multimedia documents are information objects containing formatted data, text, image, graphics, and voice. The query language is based on a conceptual document model that allows the users to formulate queries on both document content and structure. The architecture of the system is outlined, with focus on the storage organization in which both optical and magnetic devices can coexist. Query processing and the different strategies evaluated by our optimization algorithm are discussed.

In this paper we address the problem of retrieving images from large image databases, giving a partial description of the image content. This approach allows a limited automatic analysis for image belonging to a domain described in advance to the system using a formalism based on fuzzy sets. The image query processing is based on special access structures generated from the image analysis process.

Message systems send and receive messages but do not manage the information the messages contain. Database management systems manage the information of a global database but do not have a notion of address. In this paper the authors outline a prototype system which integrates the facilities of message systems and database management systems. The system manages structured messages according to their contents. The messages can be stored within a station and transferred between stations. Information present in the messages can be queried in a distributed manner. Message structure can also be exploited by automatic procedures which recognize triggering conditions and perform user specified actions.