Search

Modern Database Management Systems (DBMSs) retrieve songs that resemble those in a music dataset, identify plagiarism in a set of documents, or provide past cases to physicians by taking into account the characteristics of a query exam. All such tasks require the comparison of data by similarity, which can be expressed in terms of distance-based queries in metric spaces. Traditional query processing relies mostly on histograms for describing the data distribution space and choosing a data retrieval path that quickly leads to the answer, discarding comparisons of most unwanted data. However, DBMSs still lack adequate support for selectivity estimation of query operators for data types embedded in metric spaces. This article addresses a novel strategy that extends the query optimizer of a DBMS, so that it can also perform both logical and physical query plan optimizations in searches that include similarity predicates. The proposal, named Merkurion, updates the concept of Data Distribution Space and captures data distributions according to the distances between the elements within a dataset. Moreover, it employs concise representations of such distributions, called synopses, for the definition of rules that enable similarity searching optimization. An extensive evaluation of Merkurion in real-world datasets has proven its effectiveness and broad applicability to many data domains. [ABSTRACT FROM AUTHOR]

In this paper, we present a novel approach to perform similarity queries over medical images, maintaining the semantics of a given query posted by the user. Content-based image retrieval systems relying on relevance feedback techniques usually request the users to label relevant/irrelevant images. Thus, we present a highly effective strategy to survey user profiles, taking advantage of such labeling to implicitly gather the user perceptual similarity. The profiles maintain the settings desired for each user, allowing tuning of the similarity assessment, which encompasses the dynamic change of the distance function employed through an interactive process. Experiments on medical images show that the method is effective and can improve the decision making process during analysis. [ABSTRACT FROM AUTHOR]

Environmental planners take advantage of Spatial Decision Support Systems (SDSS) to deal with data and models for problem solving. However, these kinds of software usually provide generic models, which require considerable effort to be specialized to fit particular situations. This paper explores a solution which couples Case-Based Reasoning (CBR) to an existing SDSS, named WOODSS, to help planners to profit from others'' experiences. WOODSS is based on a Geographic Information System, and interactively documents planners'' modeling activities by means of scientific workflows, that are stored in a database. This paper describes how CBR has been used as part of WOODSS'' retrieval and storage mechanisms, to identify similar models to reuse in new decision processes. This adds a new dimension to the functionality of available SDSS. [Copyright &y& Elsevier]

Constant technological advances in electronic devices have led to the growth of elaborated data such as large texts, time series, georeferenced imagery, genetic sequences, photos, videos and several other types of complex data. Differently from scalar, traditional data types such as numbers and strings, complex data do not present the order relation property, which allows identifying whether an element precedes another according to some criterion. Therefore, these data are usually compared by the similarity degree among them. The Metric Access Methods (MAMs) are recognized as well-suited to perform similarity queries over such kind of data more efficiently than other access methods. MAMs can be considered dynamic or static depending on the pivot type used to construct them. Pivots are often employed to narrow the search for data. Global pivots can be employed to look into elements in the whole dataset, thus they have a high impact in the process of pruning irrelevant elements, since a single global pivot can be used to discard a large amount of irrelevant elements. Nevertheless, MAMs based on global pivots may have their dynamicity compromised by the fact that eventual pivot-related updates must be propagated through the entire structure. Local pivots, on the other hand, allow the maintenance to occur locally at the price of a lower pruning ability. In this paper, we propose novel techniques for improving the performance of dynamic MAMs without harming their dynamicity, once that several applications handle online complex data and, consequently, demand efficient dynamic indexes to be successful. Specifically, our main contributions are three techniques: (i) CLAP, which consists of employing local additional pivots to reduce distance calculations; (ii) ACIR, which is combined with CLAP and anticipates information from child nodes to reduce unnecessary disk accesses; and (iii) SCOOP, which is combined with CLAP as an extended version of ACIR, anticipating a larger amount of information from child nodes. The techniques have been applied to a dynamic MAM and evaluated over real datasets ranging from moderate to high dimensionality and cardinality. The experimental results show that our techniques were able to reduce query execution time in up to 63% for point queries and up to 53% for queries retrieving multiple elements. [ABSTRACT FROM AUTHOR]

• dp -BREATH provides well-segmented lung regions by classifying superpixels in CT scans. • dp -BREATH models pathological lung patterns as a Gaussian Mixing Model. • dp -Breath gives the probability of a region to contain each pathology being analyzed. • dp -BREATH highlights abnormal superpixel regions within the CT scan using heat maps. • Highlighted regions provide probabilities information regarding abnormal findings. Background and Objective: Identifying abnormalities in chest CT scans is an important and challenging task, demanding time and effort from specialists. Different parts of a single lung image may present both normal and abnormal characteristics. Thus, detecting a single lung as healthy (normal) or not is inaccurate. Methods: In this work we propose dp- BREATH, a method capable of detecting abnormalities in pulmonary tissue regions and directing the specialist's attention to the lung region containing them. It starts by highlighting regions that may indicate pulmonary abnormalities based on the healthy pulmonary tissue behavior using a superpixel-based approach and a heat map visualization. This is achieved by modeling regions of healthy tissue using a statistical model. All regions considered abnormal are modeled and classified according to their probability of containing each of the studied abnormalities. Further, dp- BREATH provides a better recognition of radiological patterns, with the likelihood of a selected lung region to contain abnormalities. Results: We validate the statistical model of healthy and abnormal detection using a representative dataset of chest CT scans. The model has shown almost no overlap between healthy and abnormal regions, and the detection of abnormalities presented precision higher than 86%, for all recall values. Additionally, the fitted models describing pulmonary radiological patterns present precision of up to 87%, with a high separation for three of five radiological patterns. Conclusions: dp- BREATH's heat map representation and its list of radiological patterns probabilities provided are intuitive methods to assist physicians during diagnosis. [ABSTRACT FROM AUTHOR]

Similarity searches retrieve elements in a dataset with similar characteristics to the input query element. Recent works show that graph-based methods have outperformed others in the literature, such as tree-based and hash-based methods. However, graphs are highly parameter-sensitive for indexing and searching, which usually demands extra time for finding a suitable trade-off for specific user requirements. Current approaches to select parameters rely on observing published experimental results or Grid Search procedures. While the former has no guarantees that good settings for a dataset will also perform well on a different one, the latter is computationally expensive and limited to a small range of values. In this work, we propose a meta-learning-based recommender framework capable of providing a suitable graph configuration according to the characteristics of the input dataset. We present two instantiations of the framework: a global instantiation that uses the whole meta-database to train meta-models and a dataset-similarity-based instantiation that relies on clustering to generate meta-models tailored to datasets with similar characteristics. We also developed generic and tuned versions of the instantiations. The generic versions can satisfy user requirements in orders of magnitude faster than the traditional Grid Search. The tuned versions provide more accurate predictions at a higher cost. Our results show that the tuned methods outperform the Grid Search for most cases, providing recommendations close to the optimal one and being a suitable alternative, particularly for more challenging datasets. • Framework based on meta-learning to automatically select and configure proximity graphs. • Intelligent index parameterization for image databases. • Meaningful dataset descriptors for approximate nearest neighbor searches. • Strategies for instantiating the proposed recommender system. [ABSTRACT FROM AUTHOR]

Technology development has accelerated the volume growth of complex data, such as images, videos, time series, and georeferenced data. Similarity search is a widely used approach to retrieve complex data, which aims at retrieving similar data according to intrinsic characteristics of the data. Therefore, to facilitate the retrieval of complex data using similarity searches, one needs to organize large collections of data in a way that similar data can be retrieved efficiently. Many access methods were proposed in the literature to speed up similarity data retrieval from large databases. Recently, graph-based methods have emerged as a very efficient alternative for similarity retrieval, with reports indicating those methods outperformed other non-graph-based methods in several scenarios. However, to the best of our knowledge, there is no previous work with experimental analysis on a comprehensive number of graph-based methods using the same search algorithm and execution environment. Our main contribution is a survey on graph-based methods used for similarity searches. We present a review on graph-based methods (types of graphs and search algorithms) as well as a detailed discussion on the applicability of search algorithms (with exact or approximate answers) in each graph type. Our main focus is on static methods in metric spaces. This survey also includes an experimental evaluation of representative graphs implemented in a common platform. We evaluate the relative performance behavior of these graphs concerning the main construction and query parameters for a variety of real-world datasets. We also show results using synthetic datasets evaluating the performance of different graph types according to different dataset features. Our experimental results reinforce the tradeoff between graph construction cost and search performance according to the construction and search parameters. • Review of graph-based methods for similarity searches categorized by graph type. • Discussion on the applicability and exactness of search algorithms in each graph type. • Tradeoff between graph construction and search performance according to parameters. • For a given recall rate, no graph type was the winner for all cases. • Dimensionality and graph connectivity affects the graph performance. [ABSTRACT FROM AUTHOR]