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.

Finding Similar Users in Social Networks

We consider a system where users wish to find similar users. To model similarity, we assume the existence of a set of queries, and two users are deemed similar if their answers to these queries are (mostly) identical. Technically, each user has a vector of preferences (answers to queries), and two users are similar if their preference vectors differ in only a few coordinates. The preferences are unknown to the system initially, and the goal of the algorithm is to classify the users into classes of roughly the same preferences by asking each user to answer the least possible number of queries. We prove nearly matching lower and upper bounds on the maximal number of queries required to solve the problem. Specifically, we present an “anytime” algorithm that asks each user at most one query in each round, while maintaining a partition of the users. The quality of the partition improves over time: for n users and time T, groups of [(O)\tilde](n/T)\tilde{O}(n/T) users with the same preferences will be separated (with high probability) if they differ in sufficiently many queries. We present a lower bound that matches the upper bound, up to a constant factor, for nearly all possible distances between user groups.     

Conjunctions of Unate DNF Formulas: Learning and Structure

A central topic in query learning is to determine which classes of Boolean formulas are efficiently learnable with membership and equivalence queries. We consider the class ^kconsisting of conjunctions ofkunate DNF formulas. This class generalizes the class ofk-clause CNF formulas and the class of unate DNF formulas, both of which are known to be learnable in polynomial time with membership and equivalence queries. We prove that ²can be properly learned with a polynomial number of polynomial-size membership and equivalence queries, but can be properly learned in polynomial time with such queries if and only if P=NP. Thus the barrier to properly learning ²with membership and equivalence queries is computational rather than informational. Few results of this type are known. In our proofs, we use recent results of Hellersteinet al.(1997,J. Assoc. Comput. Mach.43(5), 840–862), characterizing the classes that are polynomial-query learnable, together with work of Bshouty on the monotone dimension of Boolean functions. We extend some of our results to ^kand pose open questions on learning DNF formulas of small monotone dimension. We also prove structural results for ^k. We construct, for any fixedk2, a class of functionsfthat cannot be represented by any formula in ^k, but which cannot be “easily” shown to have this property. More precisely, for any functionfonnvariables in the class, the value offon any polynomial-size set of points in its domain is not a witness thatfcannot be represented by a formula in ^k. Our construction is based on BCH codes.     

Metaform: updatable form screens and their application to the use of office metaphors in query language instruction

Abstract

A database interface language and system, called Metaform, which automatically generates multi-relational form screen interfaces for use by non-computer professionals has been developed. A form screen is a subset of the relational database, with a particular relation or combination of relations being represented. Through form screens, users can simultaneously query and update several relations in the database without having to know about its underlying structure. An overview of the Metaform system is presented and several examples of the use of the Metaform query language and update operators are described.

A series of ‘usability’ studies were conducted on a prototype of the Metaform system to examine the claims that the form concept aids computer-naive users in building complex database queries. These studies adopted the form screen concept to present six office paper work analogies to users to help them to understand the database retrieval concepts. The analogies of a file cabinet, a file folder, a stack of forms, a single form, a table of information on a form and a field of information were used in a two-staged training module.

At the end of each training sequence, users answered questions with the prototype and with paper and pencil which tapped their understanding of the database retrievals they were learning to perform. The results from these questionnaires were mixed. Users performed successful relational queries for simple retrievals and for those using existential quantifiers. They had difficulty with queries involving multiple steps and intermediate stages. Although users understood and used the analogies, they ran into difficulties with the ambiguities in the English statements of the queries, thus suggesting a need for another level of metaphors and/or problem representation tools not associated with the machine but with the user's comprehension of database retrieval problems.     

Multidimensional reverse <Emphasis Type="Italic">k</Emphasis>NN search

Given a multidimensional point q, a reverse k nearest neighbor (RkNN) query retrieves all the data points that have q as one of their k nearest neighbors. Existing methods for processing such queries have at least one of the following deficiencies: they (i) do not support arbitrary values of k, (ii) cannot deal efficiently with database updates, (iii) are applicable only to 2D data but not to higher dimensionality, and (iv) retrieve only approximate results. Motivated by these shortcomings, we develop algorithms for exact RkNN processing with arbitrary values of k on dynamic, multidimensional datasets. Our methods utilize a conventional data-partitioning index on the dataset and do not require any pre-computation. As a second step, we extend the proposed techniques to continuous RkNN search, which returns the RkNN results for every point on a line segment. We evaluate the effectiveness of our algorithms with extensive experiments using both real and synthetic datasets.     

<Emphasis Type="Italic">I-Quest</Emphasis>: an <Emphasis Type="Italic">i</Emphasis>ntelligent <Emphasis Type="Italic">que</Emphasis>ry <Emphasis Type="Italic">st</Emphasis>ructuring based on user browsing feedback for semantic retrieval of video data

In spite of significant improvements in video data retrieval, a system has not yet been developed that can adequately respond to a user’s query. Typically, the user has to refine the query many times and view query results until eventually the expected videos are retrieved from the database. The complexity of video data and questionable query structuring by the user aggravates the retrieval process. Most previous research in this area has focused on retrieval based on low-level features. Managing imprecise queries using semantic (high-level) content is no easier than queries based on low-level features due to the absence of a proper continuous distance function. We provide a method to help users search for clips and videos of interest in video databases. The video clips are classified as interesting and uninteresting based on user browsing. The attribute values of clips are classified by commonality, presence, and frequency within each of the two groups to be used in computing the relevance of each clip to the user’s query. In this paper, we provide an intelligent query structuring system, called I-Quest, to rank clips based on user browsing feedback, where a template generation from the set of interesting and uninteresting sets is impossible or yields poor results.

Computing Stochastic Completion Fields in Linear-Time Using a Resolution Pyramid

We describe a linear-time algorithm for computing the likelihood that a completion joining two contour fragments passes through any given position and orientation in the image plane. Our algorithm is a resolution-pyramid-based method for solving a partial differential equation (PDE) characterizing a distribution of short, smooth completion shapes. The PDE consists of a set of independent advection equations in (x, y) coupled in the θ dimension by the diffusion equation. A previously described algorithm used a first-order, explicit finite difference scheme implemented on a rectangular grid. This algorithm required O(n³m) time for a grid of size n×n with m discrete orientations. Unfortunately, systematic error in solving the advection equations produced unwanted anisotropic smoothing in the (x, y) dimension. This resulted in visible artifacts in the completion fields. The amount of error and its dependence on θ have been previously characterized. We observe that by careful addition of extra spatial smoothing, the error can be made totally isotropic. The combined effect of this error and of intrinsic smoothness due to diffusion in the θ dimension is that the solution becomes smoother with increasing time, i.e., the high spatial frequencies drop out. By increasing Δx and Δt on a regular schedule, and using a second-order, implicit scheme for the diffusion term, it is possible to solve the modified PDE in O(n²m) time, i.e., time linear in the problem size. Using current hardware and for problems of typical size, this means that a solution which previously took 1 h to compute can now be computed in about 2 min.     

Space Complexity Vs. Query Complexity

Combinatorial property testing deals with the following relaxation of decision problems: Given a fixed property and an input x, one wants to decide whether x satisfies the property or is “far” from satisfying it. The main focus of property testing is in identifying large families of properties that can be tested with a certain number of queries to the input. In this paper we study the relation between the space complexity of a language and its query complexity. Our main result is that for any space complexity s(n) ≤ log n there is a language with space complexity O(s(n)) and query complexity 2^Ω(s(n)). Our result has implications with respect to testing languages accepted by certain restricted machines. Alon et al. [FOCS 1999] have shown that any regular language is testable with a constant number of queries. It is well known that any language in space o(log log n) is regular, thus implying that such languages can be so tested. It was previously known that there are languages in space O(log n) that are not testable with a constant number of queries and Newman [FOCS 2000] raised the question of closing the exponential gap between these two results. A special case of our main result resolves this problem as it implies that there is a language in space O(log log n) that is not testable with a constant number of queries. It was also previously known that the class of testable properties cannot be extended to all context-free languages. We further show that one cannot even extend the family of testable languages to the class of languages accepted by single counter machines.      

Color indexing for efficient image retrieval

Content based image retrieval is an active area of research. Many approaches have been proposed to retrieve images based on matching of some features derived from the image content. Color is an important feature of image content. The problem with many traditional matching-based retrieval methods is that the search time for retrieving similar images for a given query image increases linearly with the size of the image database. We present an efficient color indexing scheme for similarity-based retrieval which has a search time that increases logarithmically with the database size.In our approach, the color features are extracted automatically using a color clustering algorithm. Then the cluster centroids are used as representatives of the images in 3-dimensional color space and are indexed using a spatial indexing method that usesR-tree. The worst case search time complexity of this approach isOn _q log(N^* n_avg)), whereN is the number of images in the database, andn _q andn _avg are the number of colors in the query image and the average number of colors per image in the database respectively. We present the experimental results for the proposed approach on two databases consisting of 337 Trademark images and 200 Flag images.     

Efficient integration of fine-grained access control and resource brokering in grid

In this paper, we present a novel resource brokering service for grid systems which considers authorization policies of the grid nodes in the process of selecting the resources to be assigned to a request. We argue such an integration is needed to avoid scheduling requests onto resources the policies of which do not authorize their execution. Our service, implemented in Globus as a part of Monitoring and Discovery Service (MDS), is based on the concept of fine-grained access control (FGAC) which enables participating grid nodes to specify fine-grained policies concerning the conditions under which grid clients can access their resources. Since the process of evaluating authorization policies, in addition to checking the resource requirements, can be a potential bottleneck for a large scale grid, we also analyze the problem of the efficient evaluation of FGAC policies. In this context, we present GroupByRule, a novel method for policy organization and compare its performance with other strategies.