Multimedia retrieval relies on the underlying metadata format for e ective querying of multimedia information. Most of the metadata formats are XML-based (for instance MPEG7 or P/META). In this context, the XQuery query language is a natural choice for querying these data based on exact matches. However, XQuery lacks in expressing and evaluating multimedia speci c requests (e.q., spatial, fuzzy requests). Therefore, the MPEG Query Format (MPQF), a novel XML based query language tuned for standardized multimedia requests, has been developed. Based on this, the paper introduces a MPQF aware XQuery framework which features a.) a plug-in architecture for external multimedia routines, b.) an automatic approach for MPQF to XQuery transformation and c.) an injection of information retrieval capabilities to XQuery (e.g., scoring, ranking). Besides, the framework can be adopted to any available XQuery repository and allows the retrieval in any XML based multimedia metadata format.
H.2.4 [Systems]: Query Processing|Multimedia Databases ; H.3.3 [Information Storage and Retrieval]: Information Search and Retrieval|Query Formulation
Retrieving information in multimedia repositories is one of the major challenging tasks in the multimedia life cycle. Whenever, multimedia retrieval is discussed, one has to deal with the related metadata (formats) which are often XML based (e.g. MPEG-71). In series, by investigating XML based retrieval techniques, one nally ends up by the
well known and established XQuery2 language. The XQuery
language has its strengthens in expressing data centric and
exact queries over XML data such as Give me all images
whose lesize > 100 kByte, but lack the ability to express
fuzzy requests common in multimedia retrieval (e.g.,
QueryBy-Example). To ll this gap, a new multimedia query
language, the MPEG Query Format [
In this context, the paper contributes with a XQuery framework for multimedia search that features a.) a plugin architecture for external multimedia routines, b.) an automatic approach for MPQF to XQuery transformation and c.) an injection of information retrieval capabilities to XQuery (e.g., scoring, ranking). Besides, the framework can be adopted to any available XQuery repository and allows the retrieval in any XML based multimedia metadata format. Another bene t of adopting XQuery for multimedia retrieval is the broad diversity of available XQuery tools (databases, parsers, etc.).
The paper uses the MPEG Query Format (MPQF). The
de nition of the format is out of scope of this paper and has
been published elsewhere. Readers not familiar with MPQF
may look in [
The reminder of this paper is organized as follows: Section 2 introduces related work in the area of XQuery extensions for fuzzy retrieval. This is followed by Section 3 where the proposed MPQF to XQuery framework is described. In this context, Section 4 speci es our mapping approach for a MPQF to XQuery transformation. The speci cation is evaluated by a small example in Section 5. Performance analysis results are presented in Section 6. Finally, this article is concluded in Section 7. 2.
As highlighted in the introduction, multimedia retrieval considers (to an high extend) multimedia metadata which is often XML-based (e.g., TV-Anytime, MPEG-7, etc.). In this context, in the past several query languages that are especially designed for XML data have been developed such as
XIRQL [
MPQF BASED XQUERY FRAMEWORK This section describes the overall structure and architecture of the proposed MPQF based XQuery framework. 3.1
The MPQF syntax tree is forwarded to the transformation module which executes a mapping algorithm for producing an equivalent XQuery request. The plug-in system (see Subsection 3.2) supports the integration and evaluation of external information retrieval routines (e.g. query by example). After the nalization of the transformation process, a nal XQuery instance is available. In series, this XQuery request is forwarded to the connected XQuery database for execution. 3.2
In order to support a exible system, the framework introduces a plug-in system. Figure 2 demonstrates where plug-ins take action in the transformation life cycle.
The framework identi es di erent categories of plug-ins: support for individual query types (e.g., QueryByMedia), extension of the XQuery language set (e.g., power function), data model dependent transformations (e.g., MIME type ltering) or functionality speci c for the underlying XQuery database. In general, a plug-in is a Java module which receives a xed set of input parameters and is able to manipulate the internal context of the transformation process. For instance, the plug-in module for our QueryByMedia implementation receives as input parameters the possible elements and attributes of the speci ed MPQF query type (e.g., matchT ype and M ediaResource). Then, the module performs a similarity search at an external PostgreSQL3 database where the ScalableColor features of MPEG-7 are stored. After nalization, the module responds with the results as presented by Transformation Rules 7 and 8. 4.
MPQF TO XQUERY TRANSFORMATION RULES
The transformation formalism presented in this paper concentrates on the implementation of a global framework for fuzzy retrieval within XQuery based on the MPQF standard. In general, the rules distinguish between data model depended and data model independent transformation. That is, data model depended rules need to be adopted to the underlying metadata format as the required information can not be addressed by a given XPath4 within the MPQF query request but need additional domain speci c data. 4.1
The transformation rules for selection cover the mapping of the ltering step which is described by the QueryCondition element in an MPQF request. In this context, the skeleton for integrating a single MPQF condition (e.g., query type or comparison condition) into XQuery is implemented as follows:
Let Score i be a substitute for the transformation of an expression (e.g, comparison evaluation see Transformation Rule 6), a boolean operator (see Transformation Rule 5) or a query type which refers to external processing (see Transformation Rule 8) for e.g., information retrieval evaluation. Furthermore, let T hreshold i be the user given limit of the minimum similarity score for an operation (where 1 i n and n 2 N). Then the transformation of a MPQF query condition to XQuery is embedded as: l e t $ s c o r e V a r i := <<S c o r e i >>, . . . where $ s c o r e V a r i >= <<T h r e s h o l d i >>
Note, $scoreV ar i is a variable keeping the score value of the evaluation.
Constitutively on the abstract transformation of query conditions to score values, a closer look to its speci c substitutions has to be performed. As de ned in MPQF, an individual query condition can contain comparison, string and arithmetic operations. Exemplarily for this set of operations, the contains operation (see Transformation Rule 2) and comparison operation (see Transformation Rule 3) are de ned.
Let Opi be the respective operands of a MPQF contains condition where 1 i 2. Then the corresponding transformation to XQuery is de ned as: c o n t a i n s (<<Op1>>, <<Op2>>)
Let Operand i be the respective operands of a MPQF comparison operation where 1 i 2 and Operator is the substitute of one of the de ned MPQF operators (e.g., EQUAL to =). Then the transformation of a MPQF comparison condition to XQuery is de ned as: <<Operand 1 >> <<O p e r a t o r >> <<Operand 2 >>
A special role plays the fuzzy boolean operators as they combine the results of preceding evaluations by the means of scoring functions. In this context, the fuzzy boolean operators of MPQF (OR, AND, etc.) are transformed as follows:
Let scoreV ar i be the score value as described in Rule 1. Further, pref V ar i speci es the given user preference value (where i in [1 .. n] and n 2 N) for the respective operation. Then, the mapping of fuzzy boolean operators (AND, OR, XOR) follows the following interface: <<OP>> (<<scoreVar 1 >>,<<prefVar 1 >>,...,<< scoreVar n >>,<<prefVar n >>)
Based on the abstract de nition for fuzzy boolean operators in Rule 4 one example for a fuzzy AND operator is speci ed in Rule 5.
Let scoreV ar i and pref V ar i be speci ed as presented in Rule 4 and $scoreV ar (N + 1) the variable for holding the nal result. Then, a mapping for the AND fuzzy boolean operator to a scoring function using the product tnorm is de ned as follows: $ sc o re Va r (N+1) := math : pow ( math : pow(<<scoreVar 1 >>, <<prefVar 1 >>) . . . math : pow(<<scoreVar n >>, <<prefVar n >>), <<N>>)
Note, as the MPQF boolean operators rely on the fuzzy set
theory, the scoring functions should cope the t-norm and
tconorm fuzzy logics [
The integration of data centric evaluations (e.g., comparison operators) which base on a true/false basis is applied by Transformation Rule 6.
Let Expression be any expression derived by the Rules 2 and 3. Then the score of those operations is gathered by the following transformation: i f (<<Expression >>) then 1.0 e l s e 0.0
For the evaluation of information retrieval related techniques (e.g., the QueryByMedia or SpatialQuery query type) separate external processes have to be applied. These processes lter the document set and produce document id and score value pairs which are integrated into the nal XQuery request. For instance, as described in Subsection 3.2, the QueryByMedia query type can be implemented by forwarding this part of the MPQF request to a specialized similarity search engine for image retrieval by example. The result of such an evaluation is then integrated as speci ed by Rule 7.
Let $qbmVar be the container variable for results of an external evaluation and anyU RI i an unique identi er of an XML instance document and anyScore i its respective score value (where i in [1 .. n] and n 2 N). Then, the external result is integrated by the following format: $qbmVar := ( <qbm> <doc i d='<<anyURI 1 >>' s c o r e='<<anyScore 1 >>'/> . . .
<doc i d='<<anyURI n>>' s c o r e='<<anyScore n >>'/> </qbm> )
Note, this approach assumes that there is a unique identi er for every document. However, parts of a description (e.g. low level features) can be swapped to specialized retrieval stores but the unique identi er remains as link between those parts.
Besides, the intermediate result set (stored in a variable) is integrated into the overall evaluation by Rule 8 supporting the access to already existing score results.
Let qbmVar be the container as speci ed in Rule 7. Then, access to individual score values is accomplished as follows: i f ( e x i s t s ( $qbmVar/ doc [ @id = base u r i ( $doc ) ] ) ) then ( number ( $qbmVar/ doc [ @id = base u r i ( $doc ) ] / @score ) ) e l s e ( 0 . 0 )
The TargetMediaType element of MPQF restricts the multimedia data set according to their mime type. This ltering is data model depended as no additional information (e.g. XPath to the data) is provided within the MPQF query itself. Therefore, the evaluation is embedded as follows:
Let M IM E type i be de ned as a MIME type description where i in [1 .. n] and n 2 N. Then, the lter criterion extends the XQuery where clause as follows: where f<<MIME type 1>> OR . . . . <<MIME type n>>g AND
Finally, the resulting documents are ordered by their score evaluation and stored in an internal format for further processing (see Rule 10).
Let $scoreVarN contain the nal score value after N calculation steps, then the resulting documents are ordered and preliminary stored as follows: where
. . . order by
$scoreVarN d e s c e n d i n g r e t u r n
<Doc s c o r e ='f $scoreVarN g ' i d ='f $ i d g'>f $docg</Doc> 4.2
In a nal step, the desired information is extracted from the ltered documents and integrated in a valid MPQF output instance. As the wanted elements are addressed as XPath expressions within an MPQF query, they can be recycled in the transformation as well. Note, the nal MPQF query result is embedded in an internal proprietary format in order to support enhanced functionalities such as caching, paging, relevance feedback, etc. by the framework. 4.3
The so far introduced Transformation Rules (TR) describe techniques for mapping parts of a MPQF request to its equivalents in XQuery. The overall transformation process creates a rule chain during the evaluation of the query in order to map the entire MPQF request. Input of the chain is the MPQF request. Then, a post order traversal is applied which responds with a list of nodes (MPQF conditions) of the QueryCondition element. By parsing this list, the type of the current node is identi ed and the respective (set of) Transformation Rule(s) is/are accomplished. Then, the algorithm applies optional Rules for existing aggregation or sorting parts. Finally, the rest of MPQF's OutputDescription element is evaluated by applying the Projection rule (not shown in this paper). Finally, the output of this mapping process is an equivalent XQuery instance.
For a better understanding of the de ned Transformation Rules, a simple example transformation is demonstrated by the following MPQF query request (see Figure 3)5. The example request addresses MPEG-7 based image descriptions and selects the title and the creator information of all JPEG images whose le size is greater or equal to 500000 Bytes and where the creators family name contains the string Bob. Besides, the threshold of the combined score result must exceed 0.5. Furthermore, the nal result set should contain not more then 30 elements.
The processing engine of the incoming query tree applies a post order traversal to extract the internal nodes. For our example, this results on the following sequence: Contains, GreaterThanEqual, AND, TargetMediaType. Then, by traversing this sequence, the assigned transformation rules are executed.
In the following, Subsection 5.1 describes the used rules for the selection phase. Finally, in the project phase (see Subsection 5.2) the desired information is extracted and the entire XQuery is consolidated. 5Note, the request as MPQF language can be found in the extended version of this article. 5.1
The transformation mechanism starts by parsing all elements of the generated sequence. The rst element is the contains condition which belongs to the set of expressions. and triggers the execution of Transformation Rule 2. This results in the following XQuery snippet (see Code 1). Code 1 Transformation of the contains condition contains($doc//mpeg7:FamilyName, 'Bob')
This is followed by Transformation Rule 6 which is used for the integration of expressions into XQuery (see Code 2) Code 2 Integrating the contains condition $scoreVar1 = if (contains($doc//mpeg7:FamilyName, 'Bob')) then 1.0 else 0.0
Similarly to the contains condition, the next element in the sequence is processed, namely the GreaterT hanEqual condition. Here, in our example, the Transformation Rule 3 followed by Rule 6 are evaluated, which results in the XQuery snippet given in Code 3.
Code 3 Transformation of GreaterThanEqual $scoreVar2 = if ($doc//mpeg7:FileSize >= 500000)
then 1.0 else 0.0
After applying the Transformation Rules for the leaf nodes, our approach concentrates on the inner nodes (the boolean operators). The inner nodes regulate how the results of the leaf nodes are combined. For this purpose, scoring functions are assigned to the respective boolean operators according to t-norm and t-conorm rules. Our example uses the Product function for the AND operation in order to combine the individual score values. In this context, applying Transformation Rule 5 results in Code 4 for the AN D condition.
The resulting score value and the threshold of an condition are integrated into the XQuery request by evaluating Transformation Rule 1. Due to space constraints in this paper, the nal result for integrating the given thresholds is shown in Code 5. If no threshold is assigned, the minimum value is used (0).
As our example makes use of the TargetMediaType element for restricting the result set according to the le format, a data model depended ltering has to be found. In our example, we assume that the respective information is annotated in the Content and FileFormat elements of the MPEG-7 description. In assuming so, the following transformation for MIME-types (see Rule 9) has to be applied (see Code 6).
The nal result of all combined transformations of the selection phase can be found in Code 7. 5.2
The last stage in the transformation process is the creation of a valid MPQF response and the integration of the requested information of the target data model. Our example only instantiates the TextResult and Description elements. As described beforehand, the nal MPQF output description is wrapped in a proprietary format (ResultDocuCode 4 Applying Transformation Rule for scoring function $scoreVar3 = math:pow(math:pow($scoreVar1, 0.5)*
math:pow($scoreVar2, 0.5), 2) ment element) in order to support caching, paging, relevance feedback, etc.
This section describes the series of experiments we
performed in order to evaluate the e ectiveness of our
transformation approach. The tests were carried out on a subset of
the CoPhiR6 [
The overall performance evaluation is divided into two main parts. First, the processing time of parsing and executing the Transformation Rules has been analyzed in Subsection 6.1. The nal execution of the resulting XQuery instance at the mentioned databases is demonstrated in Subsection 6.2. 6.1
This subsection describes the set of experiments for evaluating the performance of applying the Transformation Rules. Input is a MPQF query request and output an equivalent XQuery query request. In order to receive clear di erences between the used query classes a less powerful system con guration has been applied, namely an Intel Premium M 1.60 GHz CPU with 512 MB DDR2 400 main memory running Windows XP.
The complexity of the queries is divided into the following six classes in order to demonstrate the evaluation time for di erent compositions of Transformation Rules: queries where either aggregation or sorting is used (classes NoAgg/Sort, NoAgg/Sort Complex, Agg/NoSort), queries where both (class Agg/Sort) and queries where none (class NoAgg/NoSort) of these features have been used. Except the NoAgg/Sort Complex class, the example queries contain only one condition (e.g. EQUAL condition). The complex query class demonstrates the use of Boolean operators (AND/OR) and multiple other conditions (e.g., contains or comparison).
Finally, the sixth query class addresses the performance of the plug-in system by demonstrating a QueryByMedia query type which requires external processing. The external processing has been realized by the integration of a relational
7http://saxon.sourceforge.net 8http://www.oracle.com/database/berkeley-db/xml/ index.html 9http://exist.sourceforge.net/ Code 6 Transformation of MIME type ltering ( exists($doc//mpeg7:Content[@href = 'image']) and string($doc//mpeg7:FileFormat/mpeg7:Name/text()) = 'JPEG' ) Code 7 Result of selection phase $selected := (for $doc in collection('db.dbxml')/* let $scoreVar1 = if (contains($doc//mpeg7:FamilyName, 'Bob')) then 1.0 else 0.0, $scoreVar2 = if ($doc//mpeg7:FileSize >= 500000)
then 1.0 else 0.0, $scoreVar3 = math:pow(math:pow($scoreVar1, 0.5) *
math:pow($scoreVar2, 0.5), 2), $id := base_uri($doc) where (( exists($doc//mpeg7:Content[@href = 'image']) and string($doc//mpeg7:FileFormat/mpeg7:Name/text()) = 'JPEG' )) and $scoreVar1 >= 0.0 and $scoreVar2 >= 0.0 and $scoreVar3 >= 0.5 order by
$scoreVar3 descending return <Doc score='{$scoreVar3}' id='{$id}'>{$doc}</Doc>), PostgreSQL10 database coping with low level features (color, texture, etc.) of images. Similarity calculation has been simpli ed on the basis of color features and the Euclidean distance (no index has been used). Figure 4 presents the average run time needed for the transformation of an MPQF query request to an appropriate XQuery request. The tests have been repeated 50 times. The evaluation shows that there is a slight increase of time consumption depending on the increase of query complexity. However, the maximum di erences between query classes do not increase 17%. 6.2
The experiments have been executed on a Windows based stand-alone PC with Intel Core i7 1,6GHz (4 cores) CPU and 4 GB main memory. All databases have been tested out of the box without optimization. Similar to Subsection 6.1 six di erent query classes have been used during the evaluation, whereas exemplarily only two are demonstrated in this article. Note, the presented performance behavior is also valid for the rest of the tests. Figure 5 show the results of our experiments for a query where sorting has been enabled. The y-axis describes the average processing time per document (average processing time divided by the amount of documents in the database) and the x-axis shows the amount of MPEG-7 documents stored in the database. The measured overall processing time for one MPQF query consists of the transformation time applied by our module and the time needed for processing the resulting XQuery.
By evaluating the performance results, one can identify a linear scaling of the Saxon and Berkeley DB XML engines, which is stable over the increasing size of the test data set. The impact of the initial phase needed by the engines can 10http://www.postgresql.org/ be observed by small test data sets (100 documents) and here the Berkeley DB XML is outperformed by the others. In contrast to Saxon and Berkeley DB, the eXist engine is outperformed clearly for larger test data sets as it shows a nearly quadratic scale factor.
In general, the processing time for the MPQF-XQuery transformation is in average under 7% of the overall processing time for evaluating the nal XQuery request and therefore negligible.
The last experiment targets on the evaluation of the plugin injection process by the means of a QueryByMedia query type which realizes similarity search on multimedia data. As described beforehand, the test environment consists of a PostgresSQL database storing the low level features (ScalableColor of MPEG-7). As a proof of concept, similarity search is implemented by an SQL function in the target database. Of course, here is room for improvements (e.g., use of index structures or enhanced multimedia retrieval modules). Figure 6 show the results for the QueryByMedia evaluation.
This article proposed a MPQF based XQuery framework which provides a speci cation of a set of Transformation Rules for mapping a MPEG query format request to an equivalent XQuery request. Based on this, a framework has been developed featuring a plug-in system for external multimedia retrieval routines, a threading model for fast and scalable processing and an internal result set format enabling caching, paging and relevance feedback operations. The framework is able to connect to any available XQuery repository. By using the proposed framework, XQuery repositories can be enhanced for multimedia retrieval on any XML based multimedia metadata format in a standardized way.
Future work will concentrate on further developments for the projection and output description part and the integration of additional plug-in elements coping for instance spatial and temporal retrieval.
This work has been supported in part by the THESEUS Program, which is funded by the German Federal Ministry of Economics and Technology.