Similarity-based Ranking and Query Processing in Multimedia Databases

K. Selc uk Candan Computer Science and Engineering Dept. Arizona State University, Box 875406 Tempe, AZ 85287-5406, USA. candan@[Link] M. Lakshmi Priya Computer Science and Engineering Dept. Arizona State University, Box 875406 Tempe, AZ 85287-5406, USA. mpriya@[Link] Wen-Syan Li C&C Research Laboratories NEC USA, Inc., MS/SJ10 San Jose, CA 95134,USA. wen@[Link]

Abstract Since media-based evaluation yields similarity values, results to a multimedia database query, is dened as an ordered list of n-tuples of the form

. The query itself is composed of a set

of fuzzy and crisp predicates, constants, variables, and conjunction, disjunction, and negation operators. Since many multimedia applications require partial matches, includes results which do not satisfy all predicates. Due to the ranking and partial match requirements, traditional query processing techniques do not apply to multimedia databases. In this paper, we rst focus on the problem of given a multimedia query which consists of multiple fuzzy and crisp predicates, providing the user with a meaningful nal ranking. More specically, we study the problem of merging similarity values in queries with multiple fuzzy predicates. We describe the essential multimedia retrieval semantics, compare these with the known approaches, and propose a semantics which captures the requirements of multimedia retrieval problem. We then build on these results in answering the related problem of given a multimedia query which consists of multiple fuzzy and crisp predicates, nding an efcient way to process the query. We develop an algorithm to efciently process queries with unordered fuzzy predicates (sub-queries). Although, this algorithm can work with different fuzzy semantics, it benets from the statistical properties of the semantics proposed in this paper. We also present experimental results for evaluating the proposed algorithm in terms of quality of results and search space reduction.

frame20
man 0.87 woman 0.43

computer 0.84 television 0.75

Figure 1: Fuzzy media modeling example

Introduction

Multimedia data includes image and video data which are very complex in terms of their visual and semantic contents. Depending on the application, multimedia objects are modeled and indexed using their (1) visual properties (or a set of relevant visual features), (2) semantic properties, and/or (3) the spatial/temporal relationships of subobjects. Example 1.1 For instance, Figure 1 gives an example where multimedia data is modeled using both visual and semantic features. Figure 1(a) shows an image, Boy [Link], whose structure is viewed as a hierarchy with two image components (i.e. boy and bicycle). These components are identied based on color/shape region division (visual interpretation) and their real world meanings (semantic interpretation). The relationship between an image and its components is contains. The spatial relationships can be described in 2D-String representation [1]. Objects, Obj1 and Obj2, have both visual and semantic properties that can be used in retrieval. Figure 1 shows a video frame whose structure can be viewed as a hierarchy with two image components identied based on color/shape region division (visual interpretation) and their real world meanings (semantic interpretation). The spatial relationships of these components can be described using various techniques [1, 2]. These components, or objects, have both visual and semantic properties that can be used in retrieval. In this example, objects have multiple candidate semantics, each with an associated condence value (smaller than 1.0 due to the limitations of the recognition engine). Therefore, retrieval in multimedia databases is inherently fuzzy:

similarity of media features, such as correlation between color (red vs. orange) or shape (circle vs. ellipse) features, imperfections in the feature extraction algorithms, such as the high error rate in motion estimation due to the multitude of factors involved, including camera and object speed, and camera effects, imperfections in the query formulation methods, such as the Query by Example (QBE) method where user provides an example but is not aware of which features will be used for retrieval, partial match requirements, where objects in the database fail to satisfy all requirements in the query, and 2

imperfections in the available index structures, such as low precision or recall rates due to the imperfections in clustering algorithms.

In many multimedia applications, more than one of these reasons coexist and, consequently, the system must take each of them into consideration. This requires quantication of different sources of fuzziness and merging into a single combined value for users reference. The following example describes this requirement in greater detail. Example 1.2 A query for retrieving images containing Fuji Mountain and a lake can be specied with an SQL3 like query statement [3, 4, 5] as follows:
select image P, object object1, object object2 where P contains object1 and P contains object2 and [Link] property s like mountain and [Link] property image match Fuji [Link] and [Link] property is lake and [Link] property image match lake image [Link] and [Link] is above [Link]

The above query contains two crisp query predicates: contains and is . It also contains a set of fuzzy query predicates:

s like (i.e. semantically similar) which evaluates the degree of semantic similarity between two terms. Helps resolving correlations between semantic features, imperfections in the semantics extraction algorithms, in the index structures, and in the user queries; image match (i.e. visually like) which evaluates the visual similarity between two images. Helps resolving correlations between visual features and imperfections in the index structures; and is above (a spatial condition) which compares the spatial position between two objects). Helps resolving correlations between spatial features, imperfections in the spatial information extraction algorithms, imperfections in the index structures, and imperfections in the user queries.

This query returns a set of 3-tuples of the form overall scores for quicker access to relevant results.

that satisfy all crisp conditions and that

has a combined fuzzy score above a given threshold. If users desire, the results may be sorted based on their Figure 2(Query) shows the conceptual representation of the above query. Figure 2(a), (b), (c), and (d) shows examples of candidate images that may match this query. The numbers next to the objects in these candidate images denote the similarity values for the object level matching. As explained earlier, in this example, the comparisons on spatial relationships are also fuzzy to account for correlations between spatial features. The keyword, where, used in the query does not correspond to a predicate.

Query Fuji Mountain

(a) Lake 0.98 0.0 Lake 0.98 Fuji Mountain

(b) Mountain 0.5 1.0 Lake 0.5

(c) Fuji Mountain 0.5 0.8 Forest 0.0

(d) Fuji Mountain 1.0 Lake 0.5

0.8

Figure 2: Partial matches

The candidate image in Figure 2(a) satises object matching conditions but its layout does not match user specication. Figures 2(b) and (d) satisfy image layout condition but objects do not perfectly match the specication. Figure 2(c) has structural and object matching with low scores. Note that in Figure 2(a), the spatial predicate, and in Figure 2(c), the image similarity predicate for lake completely fail (i.e., the match is a certain unied criterion.

).

A multimedia database engine must consider all four images as candidates and must rank them according to

In this paper, we rst address the problem of given a query which consists of multiple fuzzy and crisp predicates, how to provide a meaningful nal ranking to the users. We propose an alternative scoring approach which captures the multimedia semantics well and which does not face the above problem while handling partial matches. Although it is not based on weighing, the proposed approach can be used along with weighing strategies, if weighing is requested by the user. We then focus on the problem of given a query which consists of multiple fuzzy and crisp predicates and a scoring function, how to efciently process the query. It is clear that current database engines are not designed to answer the needs of these kind of queries. Recently, there has been attempts to address challenges associated with processing queries of the above kind. In [9], Adal et al. proposes an algebra for similarity-based queries. In [10, 11], Fagin proposes a set of efcient query execution algorithms for databases with fuzzy (similarity based) queries. The algorithms proposed by Fagin assume that (1) individual sources can progressively (in decreasing order of score) output results, and (2) users are interested in the best matches to the query. This for instance would require both of the s like and image match predicates, used in the above example, to return ordered results. This assumption, however, may be invalid due to limited binding and processing capabilities of the sources. For instance, the second assumption may be invalid due to the binding rules imposed by the predicates. Example 1.3 (Motivating Example) Consider the following SQL-like query which asks for 10 pairs of visually similar images, such that both images in a given pair contains at least one object, a mountain and a tree, respectively: select 10 P1, P2 where semantically like([Link] property, mountain) 4

and semantically like ([Link] property, tree) and image match ([Link] property, [Link] property). This query contains three fuzzy conditions: two semantically like predicates and one image match predicate. Let us assume that the image match predicate is implemented as an external function, which can be invoked only by providing two input images (i.e., both arguments have to be bound). The image match predicate then returns a score denoting the visual similarity of its inputs. Hence, the predicate is fuzzy, but it can not generate results in the order of score; i.e., it is a non-progressive fuzzy predicate. Let us also assume that the semantically like predicate is implemented as an external function such that, when invoked with the second argument bound, can return matching images (using an index structure) in the order of decreasing scores. Consequently, in this example, we have two sources (semantically like predicates) which can output images progressively through database access and one source (image match) which can not, and results from all these sources have to be merges to get the nal set of results. Unfortunately, due to the existence of a nonprogressive predicate, nding and returning the of the database, which is clearly undesirable.

best matching pairs of pictures would require a complete scan

In this paper, we propose a query processing approach which uses score distribution function estimates/statistics [12] and the statistical properties of the score merging functions for computing approximate top- results when some of the predicates can not return ordered results. More specically, we propose a query processing algorithm, which, given a query , uses the available score distribution function estimates/statistics [12], , of the individual predicates and the statistical properties of the corresponding score merging function ( s) for computing approximate top- results when some of the predicates in can not return ordered results. More specically, we return a set of results, . provide a solution to the following problem: Given a query , a positive number , and an error threshold, results, such that each result

is most probably (

) in the top

The paper is structured as follows: In Section 2, we provide an overview of the multimedia retrieval semantics. We show the similarities between multimedia queries and fuzzy logic statements. Then, in Section 3, we provide an overview of the popular fuzzy logic semantics and compare them with respect to the essential requirements of multimedia retrieval problem. In Section 4 we propose an algorithm for generating approximate results for queries with non-progressive fuzzy predicates. In Section 5, we investigate the statistical properties of popular fuzzy logic semantics and we describe a generic function that approximates score distributions used in the algorithm, when such distributions are not readily available. In Section 6 we experimentally evaluate the proposed algorithm. In Section 7 we compare our approach with existing work. Finally, we present our concluding remarks.

F2

F1

Figure 3: Clustering error which results in imperfections in the index structures: the squares denote the matching objects, circles denote the non-matching objects, and the dashed rectangle denotes the cluster used by the index for efcient storage and retrieval

Multimedia Retrieval Semantics

In this section, we rst provide an overview of the multimedia retrieval semantics; i.e., we describe what we mean by retrieval of multimedia data. We then review some of the approaches to deal with multimedia queries that involve multiple fuzzy predicates.

2.1

Fuzziness in Multimedia Retrieval

It is possible to classify the fuzziness in the multimedia queries into three categories: precision-related, recallrelated, and partiality-related fuzziness. Precision related class captures fuzziness due to similarity of features, imperfections in the feature extraction algorithms, imperfections in the query formulation methods, and the precision rate of the utilized index structures (Figure 3). Recall- and partiality-related classes are self explanatory. Note that, in information retrieval, the precision/recall values are mainly used in evaluating the effectiveness of a given retrieval operation or the effectiveness of a given index structure. Here, we are using these terms more as statistics which can be utilized to estimate the quality of query results. We have used this approach, in SEMCOG image retrieval system [4, 3, 5], to provide pre- and post-query feedback to users. The two examples given below, show why precision and recall are important in processing multimedia queries. Example 2.1 (Handling precision related fuzziness) Let us assume that we are given a query of the form

Let for a given object , the corresponding Let us assume that the semantic precision implement the predicate

is . This means that the index structure and semantic clusters used to

be woman and be a . of is and the image matching precision

guarantee that 80% of the returned results are semantically similar to man. These

semantic similarities can be evaluated using various algorithms [14, 15]. Similarly, the predicate 6

guarantees that 60% of the returned results are visually similar to are not correlated, maintain

precision; then, by replacing the

should be

. Then, assuming that the two predicates

: By replacing

in

remaining precision. The nal precision (or condence) is

in

with , we maintain

with , we of the

Example 2.2 (Handling recall related fuzziness) Recall rate is the ratio of the number of returned results to the ratio of the number of all relevant results. Let us assume that we have the query used in the earlier example. Let us also assume that

returns and

returns

of all applicable

results in the database. Let us further assume that both functions work perfectly when both variables are bound. Then (1) a left to right query execution plan would return plan would return

2.2

of all the applicable results. Consequently, given a query execution plan and assuming that the

, (2) a right to left query execution

, and a parallel execution of the predicates followed by a join would return

predicates are independent, the recall rate can be found by multiplying the recall rates of the predicates.

Query Semantics in the Presence of Imperfections and Similarities

Traditional query languages are based on boolean logic, where a predicate is treated as a propositional function, which returns one of the two values: between

or

. However, due to the stated imperfections, predicates related

to visual or semantic features do not correspond to propositional functions, but to functions which return values

hand, is dened as an ordered set of n-tuples of the form , where (1) is the number of variables in query , (2) each corresponds to a variable in , and (3) each satises the type constraints of the corresponding predicates in . The order of the set denotes the relevance ranking of the solutions. The rst, trivial, way to process multimedia queries is by transforming similarity functions into propositional functions by choosing a cutoff point, and by mapping all numbers in to false and numbers in to . Intuitively, such a cutoff point will correspond to a similarity degree which denotes

and . Consequently, the solution of a query of the form where s are fuzzy or crisp predicates, is a logic formula, and are free variables. The solution, on the other

dissimilarity. The main advantage of this approach is that, predicates can refute (conjunctive queries) or validate (disjunctive queries) solutions as soon as they are evaluated so that optimizations can be employed. In [16], Chaudhuri and Gravano discuss cost-based query optimization techniques for such lter queries . If users only consider full matching this method is preferred because it allows query optimization by early pruning of the search space. However, when partial matches are also acceptable, this approach fails to produce appropriate solutions. For instance, in Example 1.1, candidate images shown in Figures 2(a) and (c) will not be considered. Their techniques assume that queries do not contain negation.

The second way to process multimedia queries is to leave the nal decision, not to the constituent predicates but, to the n-tuple as a whole. This can be done by dening a scoring function a value between where

and . In this method a candidate object, , is returned as a solution if

which maps a given object to

is the solution acceptance threshold. since determining an appropriate threshold is not always is a user dened parameter. Related problems are studied within the domains of fuzzy set

possible, an alternative approach is to rank all candidate objects according to their scores and return the rst candidates, where theory [17], fuzzy relational databases [18], and probabilistic databases [19]. If users are also interested in partial matches, the second method is more suitable. The techniques proposed in [16] do not address queries with partial matches since for a given object if any lter condition fails, the object is omitted from the set of results. Furthermore, the proposed algorithms are tailored towards the

semantics

which, as discussed later in this section, despite of the many proven advantages, are not suitable for multimedia applications. In this paper, we focus on the second approach. As discussed above, multimedia predicates, by their nature, have associated scoring functions. Fuzzy sets and the corresponding fuzzy predicates also have similar scoring or membership functions. Consequently, we will examine the use of fuzzy logic for multimedia retrieval. The major challenge with the use of the second approach is that early ltering can not always be applied. As mentioned earlier, Fagin [11, 10] has proposed algorithms for efcient query processing when all fuzzy predicates are ordered. In contrast, our aim is to develop an algorithm that uses statistics to efciently process such queries even when not all of the fuzzy predicates are ordered.

Application of Fuzzy Logic for Multimedia Databases

In this section we provide an overview of fuzzy logic and, then, we introduce properties of different fuzzy logic operators. A fuzzy set, (or conventional) set, an element , with domain can be dened using a membership function, is in ( , on the other hand, has a membership function of the form

, we say that

. A crisp . When for

), otherwise we say that

is not in

). Note

that a crisp set is a special case of a fuzzy set.

A fuzzy predicate is dened as a predicate which corresponds to a fuzzy set. Instead of returning true( ) or false( ) values for propositional functions (or conventional predicates which correspond to crisp sets), fuzzy predicates return the corresponding membership values. Binary logical operators ( return a new truth value. The unary logical operator, other truth value. Similarly, binary fuzzy logical operators take two values between ) take two truth values and , on the other hand takes one truth value and returns an

and and return a third value between and . A unary fuzzy logical operator, on the other hand, takes one value between and and returns an other value between and .

 semantics

semantics

Table 1: Min and products semantics for fuzzy logical operators

T-conorm binary function

(for )

Table 2: Properties of triangular-norm and triangular-conorm functions

3.1

Relevant Fuzzy Logic Operator Semantics

There are a multitude of functions [20, 21, 22], each useful in a different application domain, proposed as semantics for fuzzy logic operators ( ). In this section, we introduce the popular scoring functions, discuss their properties, and show why these semantics may not be suitable for multimedia retrieval. Two of the most popular scoring functions are the min and product semantics of fuzzy logical operators. We can state these two semantics in the form of a table as follows: Given a set, sets and semantics. These two semantics (along with some others) have the following properties: Dened as such, binary conjunction and disjunction operators are triangular-norms (t-norms) and triangular-conorms (t-conorms). Table 2 shows the properties of t-norm and t-conorm functions. Intuitively, t-norm functions reect the properties of the crisp conjunction operation and t-conorm functions reect those of the crisp disjunction operation. Although the property of capturing crisp semantics is desirable in many cases, for multimedia applications, this is not always true. For instance, the partial match requirements invalidate the boundary conditions. In addition, monotonicity is too weak of a condition for multimedia applications. An increase in the score of a single query criterion should increase the combined score; whereas the monotonicity condition dictates such a combined increase only if the scores for all of the query criteria increases simultaneously. A stronger condition ( increases even if only or only increases) is called strictly increasing property . The Clearly,

of fuzzy

of corresponding membership functions, Table 1 shows the min and product

is not

strictly increasing. Another desirable property for fuzzy conjunction and disjunction operators is distributivity.

semantics is known [23, 10, 24] to be the only semantics for conjunction and disjunction that preserves logical equivalence (in the absence of negation) and be monotone at the same time. This property of the
This is not the same denition of strictness used in [10].

Table 3: N-ary arithmetic average and geometric average semantics semantics makes it the preferred fuzzy semantics for most cases. Furthermore, in addition to satisfying the properties of being t-norm and t-conorm, the Although it has nice features, the in Example 1.2, according to the would be

although they partially match the query. Furthermore, scores of the images in Figure 2(b) and (d) would both be , although Figure 2(d) intuitively has a higher score. The product semantics [21], on the other hand, satises idempotency only if . On the other hand, when , it has the property of being strictly increasing (when or is different from ) and Archimedean ( and ). The Archimedean property is weaker than the idempotency, yet it provides an
upper bound on the combined score, allowing for optimizations.

semantics, the score of the candidate images given in Figures 2(a) and (c)

semantics is not suitable for multimedia applications.

semantics also has the property of being idempotent.

3.2

N-ary Operator Semantics

In information retrieval research (which also shows the characteristics of multimedia applications), other fuzzy semantics, including the arithmetic mean [26] are suggested. The arithmetic mean semantics (Table 3) provides an n-ary scoring function (

). Note that the binary version of arithmetic mean does not satisfy

the requirements of being a t-norm: it does not satisfy boundary conditions and it is not associative. Hence, it does not subsume crisp semantics. On the other hand, it is idempotent and strictly increasing. Arithmetic average semantics emulate the behavior of the dot product based similarity calculation popular, in information retrieval: effectively, each predicate is treated like an independent dimension in an -dimensional the complete truth, space (where is the number of predicates), and the merged score is dened as the dot-product distance between

. Although this approach is shown to be suitable for many information retrieval applications it does not capture the semantics of

, and the given values of the predicates,

multimedia retrieval applications, introduced in Section 2, which are multiplicative in nature. Therefore, we can use the -ary geometric average semantics instead. Note that, as it was the case in the original product semantics, the geometric average semantics is also
is a query which consists of a set of fuzzy predicates, variables, constants, and conjunction, disjunction, and negation operators, and if is the disjunctive normal representation of , then, we dene the normal fuzzy semantics of as the fuzzy semantics of

not distributive. Therefore, if

. In general, . The former semantics would be used when logical equivalence of queries is not expected. The latter, on the other hand, would be used when the logical equivalence is required.

10

3.3

Accounting for Partial Matches

Both the

and the geometric mean functions have weaknesses in supporting partial matches.

the involved predicates returns zero, then both of these functions return with

as the combined score.

When, one of However, in

multimedia retrieval, partial matches are required (see Section 1). In such cases, having a few number of terms

score value in a conjunction should not eliminate the whole conjunctive term from consideration.

One proposed [6] way to deal with the partial match requirement is to weigh different query criteria in such a way that those criterion that are not important for the user are effectively omitted. For instance, in the query given in Figure 2(Query), if the user knows that spatial information is not important, then the user can choose to provide a lower weight to spatial constraints. Consequently, using a weighting technique, the image given in Figure 2(a) can be maintained although the spatial condition is not satised. This approach, however, presupposes that users can identify and weigh different query criteria. This assumption may not be applicable to many situations, including databases for naive users or retrieval by QBE (query by example). Furthermore, it is always possible that for each feature or criterion in the query, there may be a set of images in the database that fails it. In such a case, no weighting scheme will be able to handle the partial match requirement for all images. Example 3.1 Let us assume that a user wants to nd all images in the database that are similar to image . Let us also assume that the database uses three features, , , and to compare images, and that the database contains three images,

, , and .
Shape 0.0

Finally let us assume that the following table gives

the matching degrees of the images in the database for each feature:
Image Color Edge

0.0

0.0

According to this table, it is clear that if the user does not specify a priority among the three features, the system should treat all three candidates equally. On the other hand, since for each of the three features, there is a different image which fails it completely, even if we have a priori knowledge regarding the feature distribution of the data, we can not use feature weighing to eliminate low scoring features.

To account for partial matches, we need to modify the semantics of the n-ary logical operators and eliminate the undesirable nullifying effect of [3]. Note that a similar modication can also be done for the min semantics: Given a set,

of fuzzy sets and

of corresponding scoring

functions, the semantics of n-ary fuzzy conjunction operator is as follows:

where

is the number of predicates in ,

 is the truth cutoff point, i.e., it is the minimum valid score, is an offset value greater than and less than ; it corresponds to the fuzzy value of false and it

is the score of predicate for n-tuple . The term returns a value between and . Subtraction of from it and the subsequent division to normalizes the result to values between and . An additional

prevents the combined score to be

when one of the predicates has a score, and

improvement could be to allow the conjunction to give extra importance to the predicates which are above the truth cutoff value, . To achieve this, one can modify the scoring function as follows:

where and are values between and such that ,

The following is an example where various semantics for logical operators are compared. Among other things, this example clearly shows that any semantics which capture the crisp semantics are not suitable for multimedia retrieval. Example 3.2 In this example, we use the query which was presented in the introduction section to compare scores corresponding to different approaches. Figure 4 shows a set of candidate images and the associated scores computed by different methods. Numbers next to the objects in the candidate images denote the similarity values for the object level matching. The gure shows the score of the candidate images as well as their relative ranks. and The cutoff parameters used in this example are

and

, and the structural weights are

Evaluation of Queries with Unordered Fuzzy Predicates

In the earlier sections, we have investigated characteristics of multimedia retrieval and semantic properties of different fuzzy retrieval options. In this section, we focus on the query processing requirements for multimedia retrieval and provide an efcient algorithm. Although the algorithm is independent of the chosen semantics of the fuzzy logic operators described above, it uses their statistical properties to deal with unknown system parameters.

4.1

Essentials of Multimedia Query Processing

Recently, many researchers studied query optimization (mostly through algebraic manipulations) in non-traditional forms of databases. [28, 29, 30, 31, 32] provide overviews of techniques used for query processing and retrieval 12

Query
Fuji Mountain

Candidate 4
Fuji Mountain 1.0
Lake

Candidate 1
Lake 0.98 0.0

Candidate 2
Mountain 0.5 1.0

Candidate 3
Fuji Mountain 0.5 0.0

0.8

Lake 0.5
0.98

Fuji Mountain

Lake 0.5

0.8 Forest

Semantics min product arithmetic average geometric average geometric geometric averaver-

Score 0.50 0.40 0.76 0.74 0.56 0.65

Rank 1-2 1 1 1 1 1

Score 0.00 0.00 0.65 0.00 0.55 0.57

Rank 3-4 3-4 3 3-4 2 2

Score 0.50 0.25 0.66 0.63 0.38 0.51

Rank 1-2 2 2 2 3 3

Score 0.00 0.00 0.43 0.00 0.24 0.32

Rank 3-4 3-4 4 3-4 4 4

age with cutoff age with weights

Figure 4: Comparison of different scoring mechanisms in such databases. Solutions in such non-traditional databases vary from the use of database statistics and domain knowledge to facilitate query rewriting and intelligent use of cached information [33] to the use of domain knowledge to discover and prune redundant queries [34]. Li et al. also used off-line feedback mechanisms to prevent users from asking redundant or irrelevant queries [35]. In [16] Chaudhuri and Gravano discuss query optimization issues and ranking in multimedia databases. In [36], Chaudhuri and Shim discuss approaches for query processing in the presence of external predicates, or user dened functions which are very common in multimedia systems. The above work and others in the literature collectively point to the following essential requirements for multimedia query processing:

As discussed in earlier sections, fuzziness is inherent in multimedia retrieval due to many reasons including similarity of features, imperfections in the feature extraction algorithms, imperfections in the query formulation methods, partial match requirements, and imperfections in the available index structures. Users are usually not interested in a single result, but interested in. We would prefer to generate result, after we generate enumerate all solutions.

ranked results, where

is provided by the user.

This is mainly due to the inherent fuzziness, users want to have more alternatives to choose what they are result, as progressively as possible.

Since the solution space is large, we can not perform any processing which would require us to touch or

13

In [10, 11], Fagin proposes a set of efcient query execution algorithms for databases with fuzzy queries. These algorithms assume that

the query has a monotone increasing combined scoring function, individual sources can progressively (in decreasing order of score) output results, and the user is interested in the best matches to the query. matches to the

If all these conditions hold, then these algorithms can be used to progressively nd the best given query. Note that, if the

semantics for conjunction

is used and if the query does not contain negation, then

scoring function of queries are guaranteed to be monotone increasing. Similarly, for arithmetic average, product, and geometric average semantics, (if the query does not contain negation, then) the combined scoring function will be monotone. Consequently, the algorithms proposed by Fagin can be applied.

4.2

Negation

If the query contains negation, on the other hand, then the scoring function may not be monotone increasing, invalidating one of the assumptions. This, however, can be taken care of if we can assume that some of the sources (the negated ones) can also output results in increasing order of score. Since a multimedia predicate is more likely to return lower scores, the execution cost of such a query is expected to be higher. Although, the algorithm we introduce in this paper can take into account negated goals, when such an index is available, the actual focus of the algorithm is to deal with unordered subgoals.

4.3

Unordered Subgoals

The second assumption can also be invalid for various reasons, including the binding rules imposed by the predicates. Example 4.1 For example, consider the following query which is aimed at receiving all pairs of images, each containing at least one object, a mountain and a tree, respectively, and that are visually similar to each other:
select image P1, P2 where [Link] property s like mountain and [Link] property s like tree and [Link] property image match [Link] property

The above query contains three fuzzy conditions (two s like predicates and one image match predicate). Let us assume that the image match predicate is implemented as an external function, which can be invoked only by providing two input images. The image match predicate then returns a score denoting the visual similarity of its inputs. In this case, we have two sources (s like predicates) which can output images progressively through database access and one source (image match) which can not. 14

P(X) and Q(Y) and R(X,Y) -------------------<x1,0.9> <y1,0.8> <x2,0.9> <y2,0.7> <x3,0.9> <y3,0.6> <x3,y2,0.8> <x1,y1,0.78> <x2,y1,0.75>

P(X) and Q(Y) and R(X,Y) -------------------<x1,0.9> <y1,0.8> <x2,0.9> <y2,0.7> <x3,0.9> <y3,0.6> <x1,y1,0.78> <x2,y2,0.1> <x3,y3,0.7>

(ordered) (ordered)

(ordered)

(ordered) (ordered) (unordered)

Three results can be merged in order (a)

Only two results can be merged in order (b)

Figure 5: The effect of having non-progressive fuzzy predicates (numbers in the gure denote scores of the results): In (a) all predicates are progressive (results are ordered); hence, the results can be merged using algorithms presented in [11] to nd the top ranking results. In (b) only two of the three fuzzy predicates are progressive; hence the merging can be done on two predicates only. However, in this case, the ranking generated by merging two predicates may not be equal to the ranking that would be generated by merging three of the scores. As shown in Figure 5, because of such non-progressive fuzzy predicates, nding and returning the best

matching results may require a complete scan of the database. Consequently, in order to avoid the complete scan of the database, our algorithm uses the score distribution estimates/statistics of the individual predicates and the statistical properties of the score merging function to compute an approximate set of top- results. In [16] Chaudhuri and Gravano discuss query optimization issues and ranking in multimedia databases. In their framework, they differentiate between top search (access through an index) and probe (testing the predicate for given object). Top search and probe can be looked as the same as sorted access and random access described in [11]. In the next subsection, we provide an algorithm that has a similar search/probe structure. However, unlike the techniques proposed in [16], the algorithm we propose is aimed at dealing with queries with partial matches, is not tied with

semantics, and can deal with negation as long as sources (the negated ones) can also output
results, such that each result

results in increasing order of score. In order to deal with the non-progressive predicates, the algorithm we propose

, as input and it returns a set of probably ( ) in the top results, .

is most

Note that the algorithm uses score distribution function estimates/statistics [33, 35] and the statistical properties of the score merging functions for computing approximate top- results. Note also that the algorithm is exible in the sense that both strict (such a product) and monotone (such as operators are acceptable.

) semantics of fuzzy logic

15

Algorithm 4.1 Query Evaluation Algorithm Input:

A query, , A set of ordered predicates, , a set of non-ordered predicates, , and a set of crisp predicates, , A positive integer, , A threshold, .

1. Identify a scoring function, predicate 2.

. Find the sign (

) of the slope of

with respect to each

. do

3. while

(a) Use the decreasingly (if

(b)

) or increasingly (if ) ordered outputs of predicates to construct a set, , of at least n-tuple satisfying all crisp predicates, . Order the resulting tuples with respect to , which encapsulate predicates in , as well as those in . Let denote the score of the n-tuple with respect to the predicate .

(c)

(d) For every n-tuple

, nd

(assuming that

predicates in are independent). (e) Put n-tuples in such that

into

. .

(f) Let the number of n-tuples put into 4. Let be the best solutions in ; output .

in the previous step be

Figure 6: Query evaluation algorithm.

4.4
Let

Query Evaluation Algorithm

be a query and let be the set of all fuzzy predicates in , such that predicates in can output ordered results and those in can not output ordered results. Let the query also contain a set, ,

of crisp (non-fuzzy) predicates, including those which check the equalities of variables. Let us also assume that the user is interested in a set of results, such that each result in the top The main inputs to this algorithm are results, . The proposed query execution algorithm is given in Figure 6.

is most probably ( )

a query, ,

a set of ordered predicates, , a set of non-ordered predicates, , and a set of crisp predicates, , a positive integer, , an error threshold, , n-tuples. Below, we provide detailed description of the algorithm. 16

and the output is a set, , of

The rst step of the algorithm calculates the combined scoring function for the query. If this combined scoring function is not monotone (i.e., there are some negated subgoals), the algorithm identies the predicates which are negated. For all negated predicates which may have an inversely ordered index (if such an index is available), the algorithm will use the results in the increase order of score. For all negated predicates which do not have such an inverse index (which is more likely) the algorithm will treat them as non-progressive predicates. The second step of the algorithm, initializes certain temporary data structures. number of candidate solutions generated, and

keeps track of the

is the set of all tuples generated (candidate solution or not),

is the set of all candidate solutions. n-tuples which satisfy

In steps 3(a) through 3(d), the algorithm uses an algorithm similar to the one presented in [11, 10], to merge results using the ordered predicates (see Figure 5(b)). The algorithm stops when it nds the condition in step 3e. Note that an n-tuple, , satises this condition if and only if

. Let us refer to this condition as . Intuitively, if is true, then the probability of having another n-tuple, , with a better combined score than the score of , is less than .

the probability of having another n-tuple,

, with a better score is less than

, i.e., when

At the end of the third step,

contains

n-tuples which satisfy the condition. However, in the fourth

step, the algorithm revisits all the n-tuples generated and put into better solutions in those that are visited. The best output, .

earlier, to see whether there are any

n-tuples generated during this process are returned as the

Intuitively, the algorithm uses a technique similar to the ones presented in [11, 10] to generate a sequence of results that are ranked with respect to the ordered predicates. As we mentioned above, this order does not necessarily correspond the the nal order of the predicates, because it does not take the unordered scores into account. Therefore, for each tuple generated in the rst stage, using the database statistics and statistical properties of , the algorithm estimates the probability of having a better result in the remainder of the database. If for a given tuple, this probability is below a certain level, then this tuple is said to be a candidate to be in the top Note that, for the algorithm to work, we need to be able to calculate for the query. For each different semantics, examples show how to calculate

for product and min semantics we covered in Section 3.

must be calculated in a different way.

for the fuzzy semantics chosen

results.

Example 4.2 Let us assume the is a scoring function that has the product semantics. Let be the combined score of the ordered predicates and let be the combined score of the unordered predicates. Then, given the tuple, , ranked with respect to the ordered predicates, is equal to

17


Example 4.3 Let us assume the is a scoring function that has the min semantics. Then, given the tuple, , ranked with respect to the ordered predicates, is equal to

Since is a non-increasing function, is smaller than or equal to . Consequently, if , then

As seen in the above examples, in order to nd the value of

, we need to know the distributions of

the scoring functions and . In Section 5.1, we will show how these statistical values can be calculated for different fuzzy semantics. However, in some cases, such a score distribution function may not be readily available. In such cases, we need to approximate the score distribution using the database statistics. Obviously, such an approximation is likely to cause deviations from the expected results obtained using the algorithm. In Section 5, we describe a method for approximating score distributions.

4.5

Correctness of the Algorithm

In this subsection, we show that the expected ratio of the relevant results, within the algorithm, is within the error bounds; i.e., we prove the correctness of the algorithm. Theorem 4.1 Given an n-tuple,

) in the set, , of top

, which is in the top

n-tuples returned in

is most probably (

Proof 4.1 Given the n-tuple, (

) in , is either in

or not. , we can conclude that the probability that out of is less than or equal to

, then it satises the condition in step 3e, and the probability that there is another tuple with

a better combined probability is less than or equal to the subsequent searches will yield to

. In other words, the probability that the subsequent searches will push . Consequently, the probability that is in is greater than .
If

tuples with a better combined probability is also less than or equal

. Since

Consequently, the probability that is in is again greater than

, then there is an

and satises the condition in Step 3e.

Theorem 4.2 The expected number of n-tuples that are in that are also in is greater than 18

 with a worst-case probability (Theorem 4.1), the number, , of the elements of that are also in is a random variable that has a binomial and . Consequently, the expected value of is greater than distribution with parameters
Proof 4.2 Given a set,

, of

n-tuples such that each one is in

4.6

Complexity of the Algorithm

Note that the main loop of the proposed algorithm can be iterated many times during which no tuples are added to the

set. The following theorem states the affect of this on the complexity of the algorithm.

Theorem 4.3 If N is the database size (the number of all possible n-tuples) and is

and if predicates are independent, then the expected running time of the algorithm, with arbitrarily high probability, is .

is geometrically

and if

distributed with parameter

Proof 4.3 If we assume that the probability of having one n-tuple satisfying the condition in step 3e is geometrically distributed with parameter is

, the expected number of n-tuples to be tested until the rst suitable n-tuple

In reality,

is not a constant and it tends to be higher for lower values of . Consequently, the actual matches, the expected number of times the loop will be repeated is . Step 3a (according to Fagin [10, 11]), with arbitrarily high probability, where N is the

number of visited tuples is lower than the value provided by this assumption. See the results in Section 6 for details. Consequently, for of the algorithm takes

database size, i.e., the number of all possible n-tuples. Consequently, the expected running time of the while loop (or the expected number of tuples to be evaluated), with arbitrarily high probability, is . The nal selection of

time. Consequently, . the expected running time of the algorithm, with arbitrarily high probability, is
best solutions among the candidates, then, takes

Note that when

, the proposed algorithm accomplishes its task:

of the database, yet generates approximately good results. This means that if Note that the theorem assumes that

it visits a very small portion , then the algorithm will The

work most efciently. In Section 6, we will show experiment results that verify these expectations.

is geometrically distributed.

results presented in Section 6 will show that, if we replace the geometric distribution assumption with a more skewed distribution, the complexity of the algorithm relative to the database size will be less than predicted by the above theorem. Note also that, similar to the case in [11], although positive correlations between predicates may help reduce the complexity predicted above, negative correlations between predicates may result in higher complexities.

Approximating the Score Distribution using Statistics

In the previous section, we have seen that in order to use the proposed query evaluation algorithm, we need to calculate the score distribution for the combined scoring functions, and . In this section, we discuss the 19

Conjunction - geometric average 1 0.8 0.6 0.4 0.2 0 1 0.5 pred2 0.8 1 0.4 0.6 0 0.2 pred1

Conjunction - arithmetic average 1 0.8 0.6 0.4 0.2 0 1 0.5 pred2 0.8 1 0.4 0.6 0 0.2 pred1 1 0.8 0.6 0.4 0.2 0 1

Conjunction - minimum

0.5 pred2

0.8 1 0.4 0.6 0 0.2 pred1

(a)

(b)

(c)

Figure 7: The effect of (a) geometric average, (b) arithmetic average, and (c) minimum function with two predicates. Horizontal axes correspond to the values of the two input predicates and the vertical axis corresponds to the value of the conjunct according to the respective function.

differences in score distributions for various fuzzy semantics, followed by our proposed method for approximating the score distribution using statistics.

5.1

Statistical Properties of Fuzzy Semantics

We rst investigate the score distributions and statistical properties of different fuzzy semantics. Figure 7 depicts three mechanisms to evaluate conjunction. Figure 7(a) depicts the geometric averaging method (which is product followed by a root operation), (b) depicts the arithmetic averaging mechanism used by other researchers [26], and (c) the minimum function as described by Zadeh [17] and Fagin [10, 11]. In this section, we compare various statistical properties of these semantics. These properties describe the shape of the combined score distribution histograms.

5.2

Relative Importance of Query Criteria

An important advantage of the geometric average, against the arithmetic average and the

functions, is that

although it shows a linear behavior when the similarity values of the predicates are close to each other:

it shows a non-linear behavior when one of the predicates has lower similarity compared to the others:

Example 5.1 The rst item below shows the linear increase in the score of the geometric average when the input values are closer to each other. The second item, on the other hand, shows that non-linearity of the increase when input values are different:

20

Arithmetic average

Min

Geometric average

Table 4: Average score of various scoring semantics Arithmetic average Min Geometric average

Table 5: Score distribution (relative cardinality of a strong -cut) of various scoring semantics

It is claimed that according to real-world and articial nearest-neighbor workloads, the highest-scoring predicates are interesting and the rest is not interesting [27]. This implies that the semantics, unlike the

semantics which gives the

highest importance on the lowest scoring predicate may not be suitable for real workloads. The geometric average

semantics, on the other hand, does not suffer from this behavior.

Furthermore, the effect of an increase in the score of a sub-query (due to a modication/relaxation on the query by the user or the system) with a small score value is larger than an equivalent increase in the score of a sub-query with a large score value. This implies that, although the sub-queries with a high score have a larger role in determining the nal score, relaxing a non-satised sub-query may have a signicant impact on improving the nal score. This makes sense as an increase in a low scoring sub-query increases the interestingness of the sub-query itself. Average score: The rst statistical property that we consider in this section is the average score, which measures, assuming a uniform distribution of input scores, the average output score. The average score, or the relative cardinality, of a fuzzy set with respect to its discourse (or domain) is dened as the cardinality of the set divided by the cardinality of its discourse. We can dene the relative cardinality of a fuzzy set with a scoring function , where ranges between and as Consequently, the average score of conjunction semantics can be computed as shown in Table 4. Note that, if analogously dened, the relative cardinality of the crisp

conjunction is

If no score distribution information is available, the average score (assuming a uniform distribution of inputs) can be used to calculate a crude estimate of the ratio of the inputs that have a score greater than a given value. However, a better choice is obviously to look at the expected score distributions of the merge functions.

21

1 0.8 0.6 0.4 0.2

1 0.8 0.6 0.4 0.2

0.1 0.2 x 0.3 0.4 0.5

0 0.5 0.6 0.7 x 0.8 0.9

Figure 8: Score distribution of various score merging semantics (lower curve = min, middle curve = geometric average, and upper curve = arithmetic average)
Uniform Distribution of Scores 1
0.8 0.6 0.2 0.4 0.2 0.2 0.15 0.1 0.05 0 2 4 k 6 8 10 2 4 k 6 8 10 0 0.2 0.4 x 0.6 0.8 1 0.1 0.35

Zipfs Distribution of Scores

Vector-space Dist. of Scores

0.25

0.3

(a)

(b)

(c)

Figure 9: Various score distributions: (a) Uniform distribution, (b) Zipfs distribution, (c) vector-space distribution Score Distribution: The second property we investigate is score distribution. The study of the score distribution of fuzzy algebraic operators is essential in creating histograms that can be used in the algorithm we proposed. or larger than . The relative cardinality of a strong -cut ( ) of a conjunction with respect to its overall cardinality ( ) describes the concentration of scores above a threshold . Table 5 and Figure 8 show the Strong -cut of a fuzzy set is dened as the set of elements of the discourse that have score values equal to

close to , the relative cardinality of the strong -cut of the geometric average behaves like arithmetic average.

score distribution of various scoring semantics(assuming a uniform distribution of inputs). Note that when, is

5.3

Approximation of Score Distributions

In the previous subsection, we studied the score distribution of various merge functions. These distributions were generated assuming a uniform distribution of input values and can be used when there is no other information. An alternative approach, on the other hand, is to approximate the score distribution function using database statistics or domain knowledge. 5.3.1 Score Distributions

There are various ways in which the scoring function of a predicate can behave. The following is a selection of possible distributions: 22

0.3 0.2 0.1 0 0.1 0.2 0.3 0.3 0.2 0.1 0 0.1 0.2 0.3 0.3 0.2 0.1 0 0.1 0.3 0.2

Figure 10: The equi-distance spheres enveloping a query point in a three-dimensional space

Uniform distribution of scores: In this case, the probability that a fuzzy predicate will return a score within the range

, where

, is . Figure 9(a) shows this behavior.

Zipfs distribution of scores: It is generally the case that multimedia predicates have small number of highscoring and a very high number of low-scoring inputs. For instance, according to Zipfs distribution [37, 38], the probability that for a given data element, a fuzzy predicate will return a score within the range , is

(Figure 9(b)).

, where

Vector-space distribution of scores:

In information retrieval or multimedia databases, documents or media

objects are generally represented as points in an

space.

This is called the vector-model rep-

resentation of the data [28, ?]. The predicates use the distance (Euclidean, city-block etc.) between the points in this space to evaluate the dissimilarities of the objects. Therefore, the further apart the objects are from each other the more dissimilar they are. Hence, given two objects, be measured as

and , in the vector space, their similarity can

where

is the distance between and and is the maximum distance between any two points in the database. Note that is equal to and the minimum possible score is .
Given a nearest-neighbor query (which is a very common type of query that asks for objects that fall near a given query point) , we can divide the space into using spheres each of which is is equal to 10.

apart from each

other. Figure 10 shows three spheres enveloping a query point in a three-dimensional space. In this example, each of these spheres is Note that in an -dimensional space, the volume of a sphere of radius is (for example, in two dimensional space, the area of a circle is of a sphere is

units apart from each other; i.e.,

Consequently, in an -dimensional space, the volume between two consecutive, and 23

and in a three dimensional space, the volume

, where

is some constant

(a)

(b)

Figure 11: Two example queries to an image database

, spheres can be calculated as

Hence, assuming that the points are uniformly distributed in the space, the expected ratio of points that fall into Therefore, if the number this volume to the points that fall into the next larger slice is approximately of points in the innermost sphere is , then the number of points in the second slice is , the third slice is , the fourth slice is , and so on.

Hence, assuming uniform distribution of points in the space, the probability that for a given data element, a fuzzy , where predicate will return a score within the range , is , where is a positive constant and

is the number of dimension in the vector space.

Figure 9(c) shows this behavior. Note

that, when the number of dimensions is higher, the curve becomes steeper. Clustered Score Distributions: In the real world, the assumption that points are uniformly distributed across the vector space does not always hold. Figure 11 provides two example score distributions from an image database, ImageRoadMap [?]. This particular database contains 25000 images. The retrieval predicate omits those images that are beyond a certain threshold distance from the query point and, then, it appropriately scales the scores to cover the range

Therefore, although not shown in the gure, the bin corresponding to

score is, in

actuality, very large. Figure 11(a) and (b), both shows a rapid increase in the score distribution as predicated by the zipan and vector-based models. However, both gures shows an other phenomenon unpredicted by these models: the distribution starts decreasing after a point instead of continuously increasing. This is due to the fact that points in the vector space are not uniformly distributed; instead, they tend to form clusters. This is especially apparent in Figure 11(b), where there are not only one, but two local maximas, corresponding to two different clusters. Note, however, that the fact that clusters exist in the vector space does not mean that the vector space model described earlier can not be used to reason about score distribution: since the volume between slices in the vector 24

More Points

Actual distribution Envelop

Higher Score

Figure 12: A clustered distribution and the enveloping curve space increases as we get further away from the center, slices away from the query point is likely to contain more clusters then the closer ones (assuming that clusters themselves are uniformly distributed). Therefore, a zipan or vector-based model can be used to model an envelop curve for a large vector space with clusters of points (Figure 12). Merged Score Distributions: When cached results and materialized views are used for answering queries or subqueries, a single predicate in a given query may correspond to a cached combination of multiple sub-predicates put together (in advance) using a merge function. As we have seen in Section 5.1, even when their inputs are uniformly distributed, the score distributions corresponding to such score merge functions show a skewed behavior: the number of low-scoring inputs is much larger than the number of high-scoring inputs. Summary: Since, in most cases the number of low-scoring inputs is much larger than the number of high-scoring inputs, in the rest of the paper, we will focus our attention to these kind of scoring functions. However, this does not mean that scoring functions with other behaviors can not exist. 5.3.2 Selection of an Appropriate Appropriate Scoring Function

Since in this section we concentrate on score distributions where the number of low-scoring inputs is much larger than the number of high-scoring inputs, in order to model and approximate and , we need to nd a generic scoring function which has a similar behavior. Clearly various functions can be used for approximating the scoring function. We see that two good candidates are and .

Intuitively, in both cases,

gives the highest score of the predicate. Depending on the values of , , and

) and it

parameters, these functions can describe rapidly and slowly decreasing scoring functions. The advantage of the rst function over the second one is that it does not need the maximum rank information ( and convex (Figure 13(a,b,c,d)). Therefore, we use in the rest of this paper. can be evaluated much easily. Note also that the rst function can describe a large set of curvatures, both concave

25

alpha=207, beta=197, phi=0 0.8 score 0.6 0.4 0.2 200 400 600 rank 800 1000 350 300 250 200 num 150 100 50 0

alpha=207, beta=197, phi=0

P(X) and Q(Y) 1.2

0.2

0.4

0.6 score

0.8

1
Score

0.8

- :statistics

(a)
alpha=1333.9, beta=447.3, phi=1.34 1 0.8 0.6 score 0.4 0.2 0 200 400 600 rank 800 1000
num 250

(b)
alpha=1333.9, beta=447.3, phi=1.34

0.6

. :appx 1

0.4

+ :appx 2

0.2

200 150 100 50 0 0 0.2 0.4 0.6 score 0.8 1

(e)

(c)

(d)

Figure 13: The rst score approximation function: two functions (a and c) and the corresponding score distributions (b and d); (e) approximation of the combined score of a query,

Figure 13(e) shows two possible approximations, each with different parameters, for the combined score of a query of the form

, where and are ordered and both satisfying Zipfs distribution.

This gure shows that, the function does not only approximate the predicate scores, but can also approximate combined scores for a query. Therefore, we can conclude that the proposed approximation function (1) is not limited to the predicates with a Zipan distribution and (2) can handle merged scores with non-uniformly distributed inputs.

using the Approximate Scoring Function Note that an approximate scoring function, , for the highest score, is not enough for the algorithm proposed in Section 4.4. Instead, the algorithm needs the value of , assuming that the behaviors of and . and are approximated with functions
5.3.3 Calculating

Let us assume that is a scoring function that has the product semantics. Let be the combined score of the ordered predicates and let be the combined score of the unordered predicates. Let and be approximated with functions and . Then, given the tuple, , ranked with respect to the ordered predicates in , is equal to

Reminder: If

is true, then given a tuple , the probability of having another tuple, score of , is less than .
26

, with a better combined score than the

Score
ij

f (X) u u

11111111111111 00000000000000 00000000000000 11111111111111

Rank

Figure 14: The ratio of the unordered tuples that could satisfy the constraint is

Note that

and

are used as shorthands. To simplify the calculations, let us split the above inequality into

two parts as follows:

estimate the implicit rank at which

Since, is the combined score of the unordered predicates, given a rank calculated with respect to the ordered predicates, we can not estimate the value of . However, using the function, , we can

is equal to

as follows:

27

Note, on the other hand, that, as shown as the shaded region in Figure 14, the ratio of all tuples, , such that is . Hence, we have

Since this ratio corresponds to a probability, we must make sure that

which means that we can nd two limits such that

. In other words

Consequently,

will be . Hence , then there will be at least one such that ; and assuming that the error ratio, , is less than , the condition . will be . Hence, and If, on the other hand, , for all , . , we have Finally, if neither is the case, if , then since for all

if

where Therefore, can be rewritten as

Note that we can further rewrite as

where

and are used as shorthands .

Since we have guaranteed that the ratio, is always between into summation by taking the logarithm of both sides of the equation:

and , we can convert the product

Note that since it is not straight forward to solve the above summation, we can instead replace the equality with two inequalities that bound the value of

can be calculated as

where

. But, we will provide an alternative formulation.

from above and below. These two inequalities are

28

Using the second of the two inequalities, we can get

Since

, we can conclude that

Consequently, putting altogether the different cases encountered so far, we have

if

then

else if

else

) if

Note that, therefore, given a tuple , ranked with respect to the ordered predicates, which satisfy the boundary conditions is most probably in the result (

Final note: If the approximate score function overestimates , then the value of the (the limit rank below which the probability of nding a larger combined score goes to 0) is also overestimated. An important consequence of this overestimation, however, is that to essary. Therefore, in order to balance such overestimations, we can introduce a new parameter

may evaluate to false in more situations then nec and set

. However, since the approximation function given in the previous section is exible enough to t into
parameter as well.

various situations, we believe that this parameter will not be necessary in most situations. Nevertheless, in the experiments section, we experimented with different values of the

Experimental Evaluation

We have conducted a set of experiments to evaluate the algorithm we proposed to reduce the number of tuples searched when looking for the best matches to a fuzzy query. The primary goal of the experiments was to see whether (a) the proposed algorithm returns the expected percentage of the results by (b) exploring only a small 29

alpha=197315, beta=207807, phi=0 1 0.8 0.6 score 0.4 0.2 0 200 400 600 rank*1000 800 1000

Figure 15: The distribution of

and its overestimating approximation

fraction of the entire search space. These experiments were also aimed at investigating whether (c) the proposed, approximation of predicates through their statistical properties, approach affects the solutions obtained by the algorithm negatively or not. In this section, we report on the observations we obtained through simulations.

6.1

Experiment Setup

In our experiments, we have varied (1) the number of top results required ( ), (2) the database size (or the search space size), and (3) the error threshold. The query that we used for the simulations contains two ordered predicates,

. We have ranged the sizes of predicates and between 100 and 1,000. Note that this means that there are up to 1,000,000 tuples in the database .
We ran the experiments on a Linux platform with a 300MHz Pentium machine with 128 MB main memory. Each experiment was run 20 times and the results were averaged. We have generated the fuzzy values for the predicate scores according to Zipfs distribution [37, 38]. This distribution guarantees that the number of high scores returned by the algorithm is less than the number of low scores, tting into the prole of many multimedia predicates. More specically, we set the probability that for a given data element, a fuzzy predicate will return a score within the range

and , and one unordered predicate,

This is similar to the case when there are 1,000,000 images in the database, and we are using features with 1,000 different values for retrieval.

, where

, to

as shown in Figure 13(e)) and that the parameters are chosen such that the approximation for account for this overestimation, we varied between and .
the corresponding approximation parameters are chosen as

We used product semantics as the fuzzy semantics for retrieval. We have approximated and with functions and . For instance, for the case when the size of the database is 1,000,000,

(for ). Note (for overestimates the scores (Figure 15). To

For comparison purposes we have also implemented a brute force algorithm which explores all the search 30

Ratio of tuples in top K (exp:%20,win:2)

Ratio of tuples in top K (exp:%80,win:4)

Ratio of tuples

0.6

1 0.9 0.8 0.7

Ratio of tuples

0.5 0.4 0.3 0.2 0

0.6 100 90 80 70 60 50 40 30 sqrt(database size) K 20 1000 800 sqrt(database size) 600 400 200 0 200 80 400 60 600 40 K 800 20 1000

0.1 100

(a)
Tuples visited (exp:%20,win:2)

(b)
Tuples visited (exp:%80,win:4)

300 250

2500 2000

# of tuples

200 150 100 50

# of tuples
800 600 400 80 60 0 20 40 K

1500 1000 500 0 1000

0 1000 100

800 600 400 200 sqrt(database size) 0 20 40 K 60 80

100

200 sqrt(database size)

(c)

(d)

Figure 16: (a)-(c) Percentage of real top- results among the tuples returned by the algorithm and (b)-(d) the number of tuples enumerated (gures are plotted to the

scale for database size)

space and returns the actual rank of each element in the database with respect to a given query. In the next section, we describe our observations.

6.2

Experiment Results

The initial set of experiments showed that as expected due to the overestimation of the (Figure 15) the algorithm found all the data elements in top , it performed signicantly more comparisons than required, and in the worst case, it degenerated to checking all tuples. This condition, however, gave us a reasonable framework in which we can study the effect of correcting imperfect approximations through the use of the which limits the look-ahead. Figures 16(a) and (b) show the percentage of real top- results among the tuples returned by the algorithm for two different expected percentages: (a) %20 and (b) %80 (or 0.8 and 0.2 error thresholds, respectively). For the rst case, we used

parameter

and for the second case, we used

. The reason why, in this particular

gure, we are using a larger win value for the smaller error threshold is that, when we want smaller errors, the algorithm must make its estimations using more information. Results for the other parameter assignments are provided in the Appendix. Both of these gures show that, as the value of increases, the algorithm performs better; in the sense that it returns closer to the expected ratio of real top- results. Note, on the other hand, that

31

for the %20 case, when the database is small, the effect is higher number of top- results (which means that the algorithm visits more tuples then it should for the percentage provided by the user). Note that in both cases, when and database size are sufciently large (50 and 5000 respectively), the algorithm provides at least the expected ratio of top- results. Figures 16(c) and (d) show the number of tuples visited by the algorithm. According to these gures, the proposed algorithm works very efciently. For instance, when the database size is 1,000,000, is 100, and expected ratio of top- matches is %80, the algorithm visits around 2000 tuples; i.e., %0.2 of the database. Note that Theorem 4.3 implies that the number of tuples visited should be , where is the database size,

. This expectation is conrmed by both gures. Again according to the theorem, since is a constant, the number of visited tuples must be

is the number of ordered predicates (2 in our case),

is the number of results, and

According to this, the number of tuples visited must increase linearly with

assuming that plotted to the condition

. In the simulation, we have actually

, for a given

and

seen an even smaller increase in the number of tuples by increase in the database size (note that the gures are

scale for database size to provide a better visualization of the results). This is because the . In the simulations, however, since we used is not geometrical. Consequently, the algorithm

theorem gives an upper bound on the number of tuples visited: the proof assumes that -tuples satisfying the

are geometrically distributed with parameter

Zipfs distribution of the predicates, the actual distribution of nds the matches much earlier than the upper-bound suggests.

A complete set of experiment results with various parameter settings are given in Appendix. The results presented in the appendix mimic the sample of results presented in this section.

Comparison with the Related Work

In addition to various related work we mention along with the presentation of our approach, a notable recent work by Donjerkovic and Ramakrishnan [?] aims at optimizing a top results type of a query probabilistically by viewing the selectivity estimates as probability distributions. However, unlike our approach, it does not address fuzzy queries, but exact match queries on data that have an inherent order (such as salaries). Also, instead of allowing a limited error on the results themselves, it uses the selectivity estimates in optimizing the cost of exact retrieval of rst results by providing probabilistic guarantees for the optimization cost. Also recently, Chauduri selection queries effectively, their work has a different focus queries into regular database queries. A more relevant and Gravano[?] considered the problem of top

from ours. It focuses on providing a way to convert top

work is by Acharya et al.[?], which proposes algorithms aimed at providing approximate answers to warehouse queries using statistics about database content. Unlike our approach, it does not provide mechanisms to deal with similarity-based query processing and they do not address the problem of nding top results incrementally.

32

Conclusion

In this paper, we have rst presented the difference between the general fuzzy query and multimedia query evaluation problems. More specically, we have pointed to the multimedia precision/recall semantics, partial match requirement, and unavoidable necessity of fuzzy, but non-progressive predicates. Next, we have presented an approximate query evaluation algorithm that builds on [10, 11] to address the existence of non-progressive fuzzy predicates. The proposed algorithm returns a set probably in the set,

of

results, such that each result

is most

, of top

results of the query. This algorithm uses the statistical properties of the fuzzy

predicates as well as the merge functions used to combine the fuzzy values returned by individual predicates. It minimizes the unnecessary accesses to non-progressive predicates, while providing error-bounds on the topretrieval results. Since, the performance of the algorithm depends on the accuracy of the database statistics; we have discussed techniques to generate and maintain relevant statistics. Finally, we presented simulation results for evaluating the proposed algorithm in terms of quality of results and search space reduction.

Acknowledgements
We thank Dr. Golshani and Y.-C. Park for providing us with data distributions, which we used for evaluating the score approximations, from their image database, ImageRoadMap.

References
[1] S. Y. Lee, M. K. Shan, and W. P. Yang. Similarity Retrieval of ICONIC Image Databases Systems. Pattern Recognition, 22(6):675682, 1989. [2] A. Prasad Sistla, Clement Yu, Chengwen Liu, and King Liu. Similarity based Retrieval of Pictures Using indices on Spatial Relationships. In Proceedings of the 1995 VLDB Conference, Zurich, Switzerland, September23-25 1995. [3] Wen-Syan Li and K. Selc uk Candan. SEMCOG: A Hybrid Object-based Image Database System and Its Modeling, Language, and Query Processing. In Proceedings of the 14th International Conference on Data Engineering, Orlando, Florida, USA, February 1998. [4] Wen-Syan Li, K. Selc uk Candan, Kyoji Hirata, and Yoshinori Hara. Facilitating Multimedia Database Exploration through Visual Interfaces and Perpetual Query Reformulations. In Proceedings of the 23th International Conference on Very Large Data Bases, pages 538547, Athens, Greece, August 1997. VLDB. [5] Wen-Syan Li, K. Selc uk Candan, Kyoji Hirata, and Yoshinori Hara. Hierarchical Image Modeling for Object-based Media Retrieval. Data & Knowledge Engineering, 27(2):139176, July 1998.

33

[6] R. Fagin and E. L. Wimmers. Incorporating user preferences in multimedia queries. In F. Afrati and P. Koliatis, editors, Database Theory ICDT 97, volume 1186 of LNCS, pages 247261, Berlin, Germany, 1997. Springer Verlag. [7] R. Fagin and Y. S. Maarek. Allowing users to weight search terms. Technical Report RJ10108, IBM Almaden Research Center, San Jose, CA, 1998. [8] S. Y. Sung. A linear transform scheme for combining weights into scores. Technical Report TR98-327, Rice University, Houston, TX, 1998. [9] S. Adali, Piero A. Bonatti, Maria Luisa Sapino, and V. S. Subrahmanian. A Multi-Similarity Algebra. In Proceedings of the 1998 ACM SIGMOD Conference, pages 402413, Seattle, WA, USA, June 1998. [10] Ronald Fagin. Fuzzy Queries in Multimedia Database Systems. In 17 ACM Symposium on Principles of Database Systems, pages 110, June 1998. [11] Ronald Fagin. Combining Fuzzy Information from Multiple Systems. In 15 ACM Symposium on Principles of Database Systems, pages 216226, 1996. [12] Wen-Syan Li, K. Selc uk Candan, Kyoji Hirata, and Yoshinori Hara. Facilitating Multimedia Database Exploration through Visual Interfaces and Perpetual Query Reformulations. In Proceedings of the 23th International Conference on Very Large Data Bases, pages 538547, Athens, Greece, August 1997. VLDB. [13] Christos Faloutsos. Searching Multimedia Databases by Content. Kluwer Academic Publishers, Boston, 1996. [14] R. Richardson, Alan Smeaton, and John Murphy. Using Wordnet as a Knowledge base for Measuring Conceptual Similarity between Words. In Proceedings of Articial Intelligence and Cognitive Science Conference, Trinity College, Dublin, 1994. [15] Weining Zhang, Clement Yu, Bryan Reagan, and Hiroshi Nakajima. Context-Dependent Interpretations of Linguistic Terms in Fuzzy Relational Databases. In Proceedings of the 11th International Conference on Data Engineering, Taipei, Taiwan, March 1995. IEEE. [16] Surajit Chaudhuri and Luis Gravano. Optimizing Queries over Multimedia Repositories. In Proceedings of the 1996 ACM SIGMOD Conference, pages 91102, Montreal, Canada, June 1996. [17] L. Zadeh. Fuzzy Sets. Information and Control, pages 338353, 1965. [18] H. Nakajima. Development of Efcient Fuzzy SQL for Large Scale Fuzzy Relational Database. In Proceedings of the 5 International Fuzzy Systems Association World Conference, pages 517520, 1993.

34

[19] V.S. Lakshmanan, N. Leone, R. Ross, and V.S. Subrahmanian. ProbView: A Flexible Probabilistic Database System. ACM Transactions on Database Systems, 22(3):419469, September 1997. [20] H. Bandermer and S. Gottwald. Fuzzy Sets, Fuzzy Logic, Fuzzy Methods with Applications. John Wiley and Sons Ltd., England, 1995. [21] U. Thole, H.-J. Zimmerman, and P. Zysno. On the Suitability of Minimum and Product operators for the Intersection of Fuzzy Sets. Fuzzy Sets and systems, pages 167180, 1979. [22] J. Yen. Fuzzy logica modern perspective. IEEE Transactions on Knowledge and Data Engineering, 11(1):153165, January 1999. [23] D. Dubois and H. Prade. Criteria Aggregation and Ranking of Alternatives in the Framework of Fuzzy Set Theory. Fuzzy Sets and Decision Analysis, TIMS Studies in Management Sciences, 20:209240, 1984. [24] R.R. Yager. Some Procedures for Selecting Fuzzy Set-Theoretic Operations. International Jounral General Systems, pages 115124, 1965. [25] S. Adali, K.S. Candan, Y. Papakonstantinou, and V.S. Subrahmanian. Query Caching and Optimization in Distributed Mediator Systems. In Proceedings of the 1996 ACM SIGMOD Conference, pages 137147, Montreal, Canada, June 1996. [26] Y. Alp Aslandogan, Chuck Thier, Clement Yu, Chengwen Liu, and Krishnakumar R. Nair. Design, Implementation and Evaluation of SCORE. In Proceedings of the 11th International Conference on Data Engineering, Taipei, Taiwan, March 1995. IEEE. [27] K. Beyer, J. Goldstein, R. Ramakrishnan, and U. Shaft. When is nearest neighbor meaningful? Database Theory ICDT 99, Berlin, Germany, 1999. Springer Verlag. to appear. [28] C. Faloutsos. Searching Multimedia Databases by Content. Kluwer Academic Publishers, 1996. [29] C.T. Yu and W. Meng. Principles of Database Query Processing for Advanced Applications. Morgan Kauffman Publishers, 1998. [30] A. Yoshitaka and T. Ichikawa. A survey on content-based retrieval for multimedia databases. IEEE Transactions on Knowledge and Data Engineering, 11(1):8193, January 1999. [31] F. Idris and S. Panchanathan. Review of image and video indexing techniques. Journal of Visual Communication and Image Representation-Special Issue on Indexing, Storage and Retrieval of Images and Video Part II, 8(2):146166, June 1997. [32] Y.A. Aslandogan and C.T. Yu. Techniques and systems for image and video retrieval. IEEE Transactions on Knowledge and Data Engineering, 11(1):5663, 1999. 35 In

[33] S. Adal, K.S. Candan, Y. Papakonstantinou, and V.S. Subrahmanian. Query Caching and Optimization in Distributed Mediator System. In Proc. of the 1996 ACM SIGMOD Conference, Montreal, Canada, June 1996. [34] O. Etzioni, K. Golden, and D. Weld. Sound and efcient closed-world reasoning for planning. Articial Intelligence, 89(1-2):113148, 1997. [35] W.-S. Li, K.S. Candan, K. Hirata, and Y. Hara. Facilitating multimedia database exploration through visual interfaces and perpetual query reformulations. In Proceddings of the 23 International Conference on VLDB, pages 538547, Athens, Greece, August 1997. [36] S. Chaudhuri and K. Shim. Optimization of queries with user-dened predicates. In VLDB96, pages 8798, 1996. [37] G. K. Zipf. Relative Frequency as a Determinant of Phonetic Change. Harvard Studies in Classical Philiology, 1929. [38] Lee Breslau, Pei Cao, Li Fan, Graham Phillips, and Scott Shenker. On the implications of zipfs law for web caching. In INFOCOM 99, New York, USA, March 1999.

36

Appendix

Tuples visited (exp:%20,win:1)

Tuples visited (exp:%20,win:2)

250 200

300 250

# of tuples
800 600 400 200 40 0 20 K 60 80

200 150 100 50

# of tuples

150 100 50

0 1000 100

0 1000 800 600 400 200 sqrt(database size) 0 20 40 K 60 80 100

sqrt(database size)

Tuples visited (exp:%20,win:3)

Tuples visited (exp:%20,win:4)

300 250 200

400 350 300

# of tuples

# of tuples
800 600 400 200 40 0 20 K 60 80

250 200 150 100

150 100 50

0 1000 100

50 1000 800 600 400 200 sqrt(database size) 0 20 40 K 60 80 100

sqrt(database size)

Tuples visited (exp:%20,win:5)

Tuples visited (exp:%50,win:1)

400 350 300

300 250 200

# of tuples

250 200 150 100

# of tuples
800 600 400 200 40 0 20 K 60 80

150 100 50

50 1000 100

0 1000 800 600 400 200 sqrt(database size) 0 20 40 K 60 80 100

sqrt(database size)

Figure 17: Number of tuples enumerated by the algorithm

37

Tuples visited (exp:%50,win:2)

Tuples visited (exp:%50,win:3)

400 350 300

500 400

# of tuples

# of tuples
800 600 400 200 40 0 20 K 60 80

250 200 150 100

300 200 100

50 1000 100

0 1000 800 600 400 200 sqrt(database size) 0 20 40 K 60 80 100

sqrt(database size)

Tuples visited (exp:%50,win:4)

Tuples visited (exp:%50,win:5)

700 600 500

800 700 600

# of tuples

400 300 200 100

# of tuples
800 600 400 200 40 0 20 K 60 80

500 400 300 200

0 1000 100

100 1000 800 600 400 200 sqrt(database size) 0 20 40 K 60 80 100

sqrt(database size)

Tuples visited (exp:%80,win:1)

Tuples visited (exp:%80,win:2)

500 400

1000 800

# of tuples

300 200 100

# of tuples
800 600 400 200 40 0 20 K 60 80

600 400 200 0 1000

0 1000 100

800 600 400 200 sqrt(database size) 0 20 40 K 60 80

100

sqrt(database size)

Figure 18: Number of tuples enumerated by the algorithm

38

Tuples visited (exp:%80,win:3)

Tuples visited (exp:%80,win:4)

1500

2500 2000

1000

# of tuples

# of tuples

1500 1000 500

500

0 1000 800 600 400 200 sqrt(database size) 0 20 40 K 60 80 100

0 1000 800 600 400 200 sqrt(database size) 0 20 40 K 60 80 100

Tuples visited (exp:%80,win:5)

3000 2500 2000

# of tuples

1500 1000 500 0 1000 800 600 400 200 sqrt(database size) 0 20 40 K 60 80 100

Figure 19: Number of tuples enumerated by the algorithm

39

Ratio of tuples in top K (exp:%20,win:1)

Ratio of tuples in top K (exp:%20,win:2)

0.5

0.6

Ratio of tuples

0.4

0.5 0.4 0.3 0.2

Ratio of tuples

0.3 0.2 0.1 0

0 0.1 100 200 80 400 60 600 40 K

0 100 80 60 40 20 K 1000 800 600

200 400

sqrt(database size)

800 20 1000

sqrt(database size)

Ratio of tuples in top K (exp:%20,win:3)

0.6 0.5

0.7 0.6

Ratio of tuples

0.4 0.3 0.2 0

Ratio of tuples

0.5 0.4 0.3 0.2 0

0.1 100 80 60 40 20 K 1000 800 600

200 400

0.1 100 80 60 40 20 K 1000 800 600

200 400

sqrt(database size)

sqrt(database size)

Ratio of tuples in top K (exp:%20,win:5)

Ratio of tuples in top K (exp:%50,win:1)

0.7 0.6

0.6 0.5

Ratio of tuples

Ratio of tuples
0

0.5 0.4 0.3 0.2

0.4 0.3 0.2 0

0.1 100 80 60 40 20 K 1000 800 600

200 400

0.1 100 80 60 40 20 K 1000 800 600

200 400

sqrt(database size)

sqrt(database size)

Figure 20: Percentage of real top- results among the tuples returned by the algorithm

40

Ratio of tuples in top K (exp:%50,win:2)

Ratio of tuples in top K (exp:%50,win:3)

0.7 0.6

0.7 0.6

Ratio of tuples

Ratio of tuples
0

0.5 0.4 0.3 0.2

0.5 0.4 0.3 0

0.1 100 80 60 40 20 K 1000 800 600

200 400

0.2 100 80 60 40 20 K 1000 800 600

200 400

sqrt(database size)

sqrt(database size)

Ratio of tuples in top K (exp:%50,win:4)

Ratio of tuples in top K (exp:%50,win:5)

0.7 0.6

0.8 0.7

Ratio of tuples

0.5 0.4 0.3 0

Ratio of tuples

0.6 0.5 0.4 0.3 0

0.2 100 80 60 40 20 K 1000 800 600

200 400

0.2 100 80 60 40 20 K 1000 800 600

200 400

sqrt(database size)

sqrt(database size)

Ratio of tuples in top K (exp:%80,win:1)

Ratio of tuples in top K (exp:%80,win:2)

0.7 0.6

0.9 0.8

Ratio of tuples

0.5 0.4 0.3 0

Ratio of tuples

0.7 0.6 0.5 0.4 0

0.2 100 80 60 40 20 K 1000 800 600

200 400

0.3 100 80 60 40 20 K 1000 800 600

200 400

sqrt(database size)

sqrt(database size)

Figure 21: Percentage of real top- results among the tuples returned by the algorithm

41

Ratio of tuples in top K (exp:%80,win:3)

Ratio of tuples in top K (exp:%80,win:4)

Ratio of tuples

0.9 0.8

1 0.9 0.8 0.7

Ratio of tuples

0.7 0.6 0.5 0.4 0

0.6 100 90 80 70 60 50 40 30
sqrt(database size)

0 200 400 600 800 20 1000 sqrt(database size)

0.3 100 80 60 40 20 K 1000 800 600

200 400

Ratio of tuples in top K (exp:%80,win:5)

Ratio of tuples

0.9 0.8 0.7

0.6 100 90 80 70 60 50 40 30 K 20 1000 800 sqrt(database size) 600 400 200 0

Figure 22: Percentage of real top- results among the tuples returned by the algorithm

42