Persistent clustered main memory index for accelerating <Emphasis Type="Italic">k</Emphasis>-NN queries on high dimensional datasets

Similarity search implemented via k-nearest neighbor— k-NN queries on multidimensional indices is an extremely useful paradigm for content-based image retrieval. As the dimensionality of feature vectors increases the curse of dimensionality sets in, i.e., the performance of k-NN search of disk-resident indices in the R-tree family degrades rapidly due to the overlap in index pages in high dimensions. This problem is dealt with in this study by utilizing the double filtering effect of clustering and indexing. The clustering algorithm ensures that the largest cluster fits into main memory and that only clusters closest to a query point need to be searched and hence loaded into main memory. We organize the data in each cluster according to the ordered-partition—OP-tree main memory resident index, which is not prone to the curse of dimensionality and highly efficient for processing k-NN queries. We serialize an OP-tree by writing its dynamically allocated nodes into contiguous memory locations, optimize its parameters, and make it persistent by writing it to disk. The time to read and write clusters constituting an OP-tree with a single sequential access to disk benefits from higher data transfer rates of modern disk drives. The performance of the index is further improved by applying the Karhunen–Loève transformation—KLT to the dataset, since this results in a more efficient computation of distances for k-NN queries. We compare OP-trees and sequential scans with and without a KL-transformation and with and without using a shortcut method in calculating Euclidean distances. A comparison against the OMNI-sequential scan is also reported. We finally compare a clustered and persistent version of the OP-tree against a clustered version of the SR-tree and the VA-file method. CPU time is measured and elapsed time is estimated in this study. It is observed that the OP-tree index outperforms the other two methods and that the improvement increases with the number of dimensions.

Just in Time Control of Constrained (<Emphasis Type="Italic">max</Emphasis>,+)-Linear Systems

This paper deals with just in time control of (max,+)-linear systems. The output tracking problem, considered in previous studies, is generalized by considering additional constraints in the control objective. The problem is formulated as an extremal fixed point computation. This control is applied to timetables computation for urban bus networks.

<Emphasis Type="Italic">Sotto Voce:</Emphasis> Facilitating Social Learning in a Historic House

This study examines visitors’ use of two different electronic guidebook prototypes, the second an iteration of the first, that were developed to support social interaction between companions as they tour a historic house. Three studies were conducted in which paired visitors’ social interactions were video- and audio-recorded for analysis. Using conversation analysis, the data from the use of prototype 1 and prototype 2 were compared. It was found that audio delivery methods were consequential to the ways in which visitors structurally organized their social activity. Further, the availability of structural opportunities for social interaction between visitors has implications for the ways in which the learning process occurs in museum settings.

Periodicity and stability issues of a <Emphasis Type="Italic">chaotic</Emphasis> pattern recognition neural network

Traditional pattern recognition (PR) systems work with the model that the object to be recognized is characterized by a set of features, which are treated as the inputs. In this paper, we propose a new model for PR, namely one that involves chaotic neural networks (CNNs). To achieve this, we enhance the basic model proposed by Adachi (Neural Netw 10:83–98, 1997), referred to as Adachi’s Neural Network (AdNN), which though dynamic, is not chaotic. We demonstrate that by decreasing the multiplicity of the eigenvalues of the AdNN’s control system, we can effectively drive the system into chaos. We prove this result here by eigenvalue computations and the evaluation of the Lyapunov exponent. With this premise, we then show that such a Modified AdNN (M-AdNN) has the desirable property that it recognizes various input patterns. The way that this PR is achieved is by the system essentially sympathetically “resonating” with a finite periodicity whenever these samples (or their reasonable resemblances) are presented. In this paper, we analyze the M-AdNN for its periodicity, stability and the length of the transient phase of the retrieval process. The M-AdNN has been tested for Adachi’s dataset and for a real-life PR problem involving numerals. We believe that this research also opens a host of new research avenues. Research partially supported by the Natural Sciences and Engineering Research Council of Canada.

---

A powerful relevance feedback mechanism for content-based 3D model retrieval

The technique of relevance feedback has been introduced to content-based 3D model retrieval, however, two essential issues which affect the retrieval performance have not been addressed. In this paper, a novel relevance feedback mechanism is presented, which effectively makes use of strengths of different feature vectors and perfectly solves the problem of small sample and asymmetry. During the retrieval process, the proposed method takes the user’s feedback details as the relevant information of query model, and then dynamically updates two important parameters of each feature vector, narrowing the gap between high-level semantic knowledge and low-level object representation. The experiments, based on the publicly available 3D model database Princeton Shape Benchmark (PSB), show that the proposed approach not only precisely captures the user’s semantic knowledge, but also significantly improves the retrieval performance of 3D model retrieval. Compared with three state-of-the-art query refinement schemes for 3D model retrieval, it provides superior retrieval effectiveness only with a few rounds of relevance feedback based on several standard measures.

<Emphasis Type="Italic">AtelierM</Emphasis>++: a fast and accurate marbling system

We present AtelierM++, a new interactive marbling image rendering system which allows artists to create marbling textures with real-time visual feedback on mega-pixel sized images. Marbling is a method of aqueous surface design, which can produce patterns similar to marble or other stone, hence the name. The system is based on the physical model of the traditional marbling process. We simulate real marbling by solving the Navier-Stokes equations on the graphics processing unit. We employ a third-order accurate but fast Unsplit semi-Lagragian Constrained Interpolation Profile method to reduce the numerical dissipation while retaining the stability. To simulate very sharp interface lines among different paints, a simple yet effective transformation function is applied to the paint concentrations. Several intuitive interfaces are implemented to provide flexible control for users. Extensive experimental results are shown to demonstrate both the effectiveness and efficiency of the proposed approach.

Panconnectivity and edge-pancyclicity of 3-ary <Emphasis Type="Italic">N</Emphasis>-cubes

We study two topological properties of the 3-ary n-cube Q _n ³. Given two arbitrary distinct nodes x and y in Q _n ³, we prove that there exists an x–y path of every length ranging from d(x,y) to 3 ⁿ −1, where d(x,y) is the length of a shortest path between x and y. Based on this result, we prove that Q _n ³ is edge-pancyclic by showing that every edge in Q _n ³ lies on a cycle of every length ranging from 3 to 3 ⁿ .

Improving the space cost of <Emphasis Type="Italic">k</Emphasis>-NN search in metric spaces by using distance estimators

Similarity searching in metric spaces has a vast number of applications in several fields like multimedia databases, text retrieval, computational biology, and pattern recognition. In this context, one of the most important similarity queries is the k nearest neighbor (k-NN) search. The standard best-first k-NN algorithm uses a lower bound on the distance to prune objects during the search. Although optimal in several aspects, the disadvantage of this method is that its space requirements for the priority queue that stores unprocessed clusters can be linear in the database size. Most of the optimizations used in spatial access methods (for example, pruning using MinMaxDist) cannot be applied in metric spaces, due to the lack of geometric properties. We propose a new k-NN algorithm that uses distance estimators, aiming to reduce the storage requirements of the search algorithm. The method stays optimal, yet it can significantly prune the priority queue without altering the output of the query. Experimental results with synthetic and real datasets confirm the reduction in storage space of our proposed algorithm, showing savings of up to 80% of the original space requirement.

Staged self-assembly: nanomanufacture of arbitrary shapes with <Emphasis Type="Italic">O</Emphasis>(1) glues

We introduce staged self-assembly of Wang tiles, where tiles can be added dynamically in sequence and where intermediate constructions can be stored for later mixing. This model and its various constraints and performance measures are motivated by a practical nanofabrication scenario through protein-based bioengineering. Staging allows us to break through the traditional lower bounds in tile self-assembly by encoding the shape in the staging algorithm instead of the tiles. All of our results are based on the practical assumption that only a constant number of glues, and thus only a constant number of tiles, can be engineered. Under this assumption, traditional tile self-assembly cannot even manufacture an n × n square; in contrast, we show how staged assembly in theory enables manufacture of arbitrary shapes in a variety of precise formulations of the model.

Efficiently support concurrent queries in multiuser CBIR systems

Various techniques have been developed for different query types in content-based image retrieval systems such as sampling queries, constrained sampling queries, multiple constrained sampling queries, k-NN queries, constrained k-NN queries, and multiple localized k-NN queries. In this paper, we propose a generalized query model suitable for expressing queries of different types, and investigate efficient processing techniques for this new framework. We exploit sequential access and data sharing by developing new storage and query processing techniques to leverage inter-query concurrency. Our experimental results, based on the Corel dataset, indicate that the proposed optimization can significantly reduce average response time in a multiuser environment, and achieve better retrieval precision and recall compared to two recent techniques.

Multiple <Emphasis Type="Italic">k</Emphasis> nearest neighbor search

The problem of kNN (k Nearest Neighbor) queries has received considerable attention in the database and information retrieval communities. Given a dataset D and a kNN query q, the k nearest neighbor algorithm finds the closest k data points to q. The applications of kNN queries are board, not only in spatio-temporal databases but also in many areas. For example, they can be used in multimedia databases, data mining, scientific databases and video retrieval. The past studies of kNN query processing did not consider the case that the server may receive multiple kNN queries at one time. Their algorithms process queries independently. Thus, the server will be busy with continuously reaccessing the database to obtain the data that have already been acquired. This results in wasting I/O costs and degrading the performance of the whole system. In this paper, we focus on this problem and propose an algorithm named COrrelated kNN query Evaluation (COKE). The main idea of COKE is an “information sharing” strategy whereby the server reuses the query results of previously executed queries for efficiently processing subsequent queries. We conduct a comprehensive set of experiments to analyze the performance of COKE and compare it with the Best-First Search (BFS) algorithm. Empirical studies indicate that COKE outperforms BFS, and achieves lower I/O costs and less running time.     

Video scene retrieval with interactive genetic algorithm

This paper proposes a video scene retrieval algorithm based on emotion. First, abrupt/gradual shot boundaries are detected in the video clip of representing a specific story. Then, five video features such as “average color histogram,” “average brightness,” “average edge histogram,” “average shot duration,” and “gradual change rate” are extracted from each of the videos, and mapping through an interactive genetic algorithm is conducted between these features and the emotional space that a user has in mind. After the proposed algorithm selects the videos that contain the corresponding emotion from the initial population of videos, the feature vectors from them are regarded as chromosomes, and a genetic crossover is applied to those feature vectors. Next, new chromosomes after crossover and feature vectors in the database videos are compared based on a similarity function to obtain the most similar videos as solutions of the next generation. By iterating this process, a new population of videos that a user has in mind are retrieved. In order to show the validity of the proposed method, six example categories of “action,” “excitement,” “suspense,” “quietness,” “relaxation,” and “happiness” are used as emotions for experiments. This method of retrieval shows 70% of effectiveness on the average over 300 commercial videos.

OCRS: an interactive object-based image clustering and retrieval system

In this paper, we propose an Interactive Object-based Image Clustering and Retrieval System (OCRS). The system incorporates two major modules: Preprocessing and Object-based Image Retrieval. In preprocessing, an unsupervised segmentation method called WavSeg is used to segment images into meaningful semantic regions (image objects). This is an area where a huge number of image regions are involved. Therefore, we propose a Genetic Algorithm based algorithm to cluster these images objects and thus reduce the search space for object-based image retrieval. In the learning and retrieval module, the Diverse Density algorithm is adopted to analyze the user’s interest and generate the initial hypothesis which provides a prototype for future learning and retrieval. Relevance Feedback technique is incorporated to provide progressive guidance to the learning process. In interacting with user, we propose to use One-Class Support Vector Machine (SVM) to learn the user’s interest and refine the returned result. Performance is evaluated on a large image database and the effectiveness of our retrieval algorithm is demonstrated through comparative studies.

Content-based image retrieval using fuzzy perceptual feedback

In this paper, a new framework called fuzzy relevance feedback in interactive content-based image retrieval (CBIR) systems is introduced. Conventional binary labeling scheme in relevance feedback requires a crisp decision to be made on the relevance of the retrieved images. However, it is inflexible as user interpretation of visual content varies with respect to different information needs and perceptual subjectivity. In addition, users tend to learn from the retrieval results to further refine their information requests. It is, therefore, inadequate to describe the user’s fuzzy perception of image similarity with crisp logic. In view of this, we propose a fuzzy relevance feedback approach which enables the user to make a fuzzy judgement. It integrates the user’s fuzzy interpretation of visual content into the notion of relevance feedback. An efficient learning approach is proposed using a fuzzy radial basis function (FRBF) network. The network is constructed based on the user’s feedbacks. The underlying network parameters are optimized by adopting a gradient-descent training strategy due to its computational efficiency. Experimental results using a database of 10,000 images demonstrate the effectiveness of the proposed method.

Mixture of KL subspaces for relevance feedback

Relevance feedback has recently emerged as a solution to the problem of improving the retrieval performance of an image retrieval system based on low-level information such as color, texture and shape features. Most of the relevance feedback approaches limit the utilization of the user’s feedback to a single search session, performing a short-term learning. In this paper we present a novel approach for short and long term learning, based on the definition of an adaptive similarity metric and of a high level representation of the images. For short-term learning, the relevant and non-relevant information given by the user during the feedback process is employed to create a positive and a negative subspace of the feature space. For long-term learning, the feedback history of all the users is exploited to create and update a representation of the images which is adopted for improving retrieval performance and progressively reducing the semantic gap between low-level features and high-level semantic concepts. The experimental results prove that the proposed method outperforms many other state of art methods in the short-term learning, and demonstrate the efficacy of the representation adopted for the long-term learning.

The <Emphasis Type="Italic">systems edge</Emphasis> of the Parameterized Linear Array with a Reconfigurable Pipelined Bus System (LARPBS(p)) optical bus parallel computing model

This paper is about exploring the various systems related aspects pertinent in the recent Parameterized Linear Array with a Reconfigurable Pipelined Bus System (LARPBS(p)) model. The two principal features of the LARPBS(p) model is, firstly, its bridging model definition similar to that of the BSP model leading to a more detailed algorithm cost analysis than other models, and secondly, the incorporation of several new communication primitives not defined in earlier models. This paper reviews the systems related aspects of earlier optical bus models and summarizes the LARPBS(p) model. The main part of this paper considers some practical systems related aspects of the LARPBS(p) model, specifically: fiber and free space based implementations, feasibility study, communication traffic analysis, bus collision avoidance, and the cost analysis of a MIMD algorithm. An overview perspective of the work is presented, thereby: the edge of systems related research is identified.

Independent query refinement and feature re-weighting using positive and negative examples for content-based image retrieval

Query refinement and feature re-weighting are the two core techniques underlying the relevance feedback of content-based image retrieval. Most existing relevance feedback mechanisms generally model the user’s query target with a single query point and weight each extracted feature with a single importance factor. A designed estimation procedure then estimates the best query point and all importance factors by optimizing a formulated criterion which measures the goodness of the estimation. This formulated criterion simultaneously encapsulates all positive and negative examples supplied from the user’s feedback. Under such formulation, the positive and negative examples may contribute contradictorily to the criterion and sometimes may introduce higher difficulty in attaining a good estimation. In this paper, we propose a different statistical formulation to estimate independently two pairs of query points and feature weights from the positive examples and negative examples, respectively. These two pairs then define the likelihood ratio, a criterion term used to rank the relevance of all database images. This approach simplifies the criterion formulation and also avoids the mutual impeditive influence between positive examples and negative examples. The experimental results demonstrate that the proposed approach outperforms some other related approaches.

Recognizing context for annotating a live life recording

In the near future, it will be possible to continuously record and store the entire audio–visual lifetime of a person together with all digital information that the person perceives or creates. While the storage of this data will be possible soon, retrieval and indexing into such large data sets are unsolved challenges. Since today’s retrieval cues seem insufficient we argue that additional cues, obtained from body-worn sensors, make associative retrieval by humans possible. We present three approaches to create such cues, each along with an experimental evaluation: the user’s physical activity from acceleration sensors, his social environment from audio sensors, and his interruptibility from multiple sensors.

RRSi: indexing XML data for proximity twig queries

Twig query pattern matching is a core operation in XML query processing. Indexing XML documents for twig query processing is of fundamental importance to supporting effective information retrieval. In practice, many XML documents on the web are heterogeneous and have their own formats; documents describing relevant information can possess different structures. Therefore some “user-interesting” documents having similar but non-exact structures against a user query are often missed out. In this paper, we propose the RRSi, a novel structural index designed for structure-based query lookup on heterogeneous sources of XML documents supporting proximate query answers. The index avoids the unnecessary processing of structurally irrelevant candidates that might show good content relevance. An optimized version of the index, oRRSi, is also developed to further reduce both space requirements and computational complexity. To our knowledge, these structural indexes are the first to support proximity twig queries on XML documents. The results of our preliminary experiments show that RRSi and oRRSi based query processing significantly outperform previously proposed techniques in XML repositories with structural heterogeneity.