DAF : An adaptive computing framework for multimedia data streams analysis

Abstract

We consider the problem of efficiently online computing/filtering or analysis multimedia streams. In this scenario, we register a large scale of continuous analysis queries to filter pornographic stream items. Each query is a conjunction of filters. For instance, the query “does this image contain a people basking in the beach?” can be resolved by applying the conjunction of water, people, sand, sea filters successively on the stream item. However, the online evaluation of multimedia filters is indeed very expensive, fortunately there usually exist multiple filters shared among a lot of queries. In other words, each filter may occur in multiple queries. An open problem in such a filtering scenario is how to order the filters in an optimal sequence to achieve significant performance. Existing methods are based on a greedy strategy which orders the filters according to three factors (selectivity, popularity, cost). Although all these methods achieve good results, there are still some problems that haven’t addressed yet. First, the selectivity factor is set empirically, which can not adaptively adjust with multimedia stream. Second, the proportion relationships among the three factors (selectivity, cost, popularity) were not considerably explored. Under these observations,in this paper, we propose a Dynamic-Analytic hierarchy process Framework (DAF) which use a time-based compositional forecasting method, which is based on the idea of exponential smoothing, to deal with the factors’ proportion relationships dynamics. Experiments on both synthetic and real lift multimedia streams demonstrate that our proposed framework (DAF) provides much great adaptability in modeling the factors proportion relationships changing over multimedia stream environment.

Keywords

Multimedia streams analytic hierarchy process pipeline filter ordering

1. Introduction

Many popular applications deal with multimedia that is pushed continuously and needs to be processed in real-time. Multimedia stream filtering which is a typical application example that users subscribe to many kinds of multimedia streams such as image streams, video streams, …, text streams. These streams may contain insalubrious items. To filter these items, we should register many continuous queries on these streams. Each query is a conjunction of filters and each filter occur in multiple queries. For instance, we register four queries just like in Table 1. Query $Q_{1}$ is consist of $F_{\textit{Court}}$ and $F_{\textit{Person}}$ . Query $Q_{2}$ is a conjunction of $F_{\textit{Court}}$ , $F_{\textit{Person}}$ and $F_{\textit{Hill}}$ . Filter $F_{\textit{Person}}$ is shared among $Q_{1}$ , $Q_{2}$ , $Q_{3}$ and $Q_{4}$ . However, the evaluation of these filters on image or videos are very expensive. Applying a single filter on a image (1024*768) typically takes several hundreds of milliseconds or even longer in most multimedia retrieval systems such as IMARS. The most expensive filters in our stream filtering system usually take about 0.25 seconds average on an usually 800*600 image. Fortunately multiple queries in our system is overlapping. For example in Table 1, Query $Q_{1}$ and $Q_{2}$ shared filters $F_{\textit{Court}}$ and $F_{\textit{Person}}$ . So sharing expensive filters will achieve significant performance.

Table 1
Query example: $Q_{1}$ , $Q_{2}$ , $Q_{3}$ , $Q_{4}$

Query Examples:

t

: current item in multimedia stream $S_{i}$

F_{\textit{Court}}

: filter that evaluate an image contain Court

F_{\textit{Person}}

: filter that evaluate an image contain Person

F_{\textit{Bicycle}}

: filter that evaluate an image contain Bicycle

F_{\textit{Hill}}

: filter that evaluate an image contain Hill

Q_{1}

: Select * From $S_{i}$ Where $F_{\textit{Court}}(t)\wedge F_{\textit{Person}}(t)$

Objective: does this image contain a people running in court?

Q_{2}

: Select * From $S_{i}$ Where $F_{\textit{Court}}(t)\wedge F_{\textit{Person}}(t)\wedge F_{\textit{Bicycle}}(t)$

Objective: does this image contain a people participating cycle track?

Q_{3}

: Select * From $S_{i}$ Where $F_{\textit{Hill}}(t)\wedge F_{\textit{Person}}(t)\wedge F_{\textit{Bicycle}}(t)$

Objective: does this image contain a people Mountain biking?

Q_{4}

: Select * From $S_{i}$ Where $F_{\textit{Hill}}(t)\wedge F_{\textit{Person}}(t)$

Objective: does this image contain a people standing in hill?

So we consider the problem of evaluating multiple overlapping queries defined on multimedia streams. Each query is a conjunction of filters and each expensive filter share across queries. We could achieve significant performance by sharing filters results among queries. If all filters contained a query return true, we say that the query was satisfied. Shared filter ordering is our central optimization problems. The goal of our optimization is to minimize the overall cost of evaluating the filters through sharing filters result across multiple queries. Through our optimization, we could decide the subset of queries that are satisfied by the coming data stream item.

As shown in Fig. 1, we need to decide all queries that are satisfied by the coming stream tuple. (In Fig. 1, the evaluation of a specific filter on the coming tuple in the multimedia stream results in a Boolean value).

Figure 1.

This shows a figure consisting of four queries ( $Q_{1}$ , $Q_{2}$ , $Q_{3}$ , $Q_{4}$ ) and four filters ( $F_{1}$ , $F_{2}$ , $F_{3}$ , $F_{4}$ ). They are connected in a many-to-many way. Each query is a conjunction of filters and each filter is shared across multiple queries. The objective is to evaluate all filters in a lowest cost by properly ordering all filters. For instance, when evaluating query $Q_{2}$ , if $F_{2}$ is first evaluated false, we can decide that query $Q_{2}$ , $Q_{1}$ , $Q_{3}$ , $Q_{4}$ are not satisfied. Otherwise, if $F_{1}$ is firstly evaluated true,we also need to evaluate $F_{2}$ and $F_{3}$ to decide $Q_{2}$ .

Shared filters ordering problem is very common in stream applications [14,29]. In general,the main factors of filters is cost, selectivity and popularity. These factors usually vary considerably in multimedia stream environment.

•

selectivity: For every filter, the selectivity of the filter is refer to average probability that a stream item satisfies the filter. We preferably evaluate the filters with lower selectivity value, since they are more likely to decide queries if the evaluation result false.

•

cost: The time taken to evaluate a given filter. We should preferably evaluate filters with lower cost.

•

popularity: The number of queries that contain a given filter. We should preferably evaluated filters with higher popularity value. Since filters with higher popularity could decide more queries.

The Shared Filter Ordering problem should be solved by taking all of the factors (selectivity, cost, popularity) into account. A simple execution strategy for such ordering problem is to evaluate every filter in each query independently on all incoming stream item. However, motivated by the need for efficient stream filtering, we could use a shared execution strategy, In which the filters are evaluated on every stream item in some shared result order for a set of queries. In this shared strategy, the evaluation result of All filters are shared across all queries registered in filtering system. In this paper, we tackle the central problem of finding the shared ordering in which filters are evaluated for every data stream item.

The shared filter ordering problem was introduced by [9]. They prove that it is NP-hard problem to find an optimal ordering with given filters and queries. They imply that efficient polynomial time algorithms for solving the shared filter ordering problem are impossible to exist.

However, the previously proposed greedy-based approaches have a most important limitations that we seek to address in this work:

•

Most greedy-based [8, 10] approaches set a fix value on all factors. Hence, these approaches result in a fixed filter evaluation ordering, which would be very inefficient in today’s rapidly changing environment context.

•

[10, 8] propose their typical ordering evaluation method is by performing a simple weight function joint all the fixed factors, which cannot reflect the real priority weight among all factors.

Shared Filter Ordering problem poses the following major challenges:

The adaptivity re-evaluation of selectivity

The selectivity of filters is set empirically, which can not adaptively adjust with multimedia stream environment. The characteristics of streams is ever-changing, it is of primary importance to be able to follow re-evaluate the selectivity over time as to enable the system to respond adaptivity and continuously.

The proportion relationships among factors dynamic

For a given filter, these factors may give contradictory suggestions for the result of filter ordering. So we must evaluate the proportion relationships among all factors (selectivity, cost, popularity) to taken all factor in a unify form. In multimedia stream environment, filter characteristics may change unpredictably during the evaluation on stream. The proportion relationships among all factors always not stabilize. It is important to be able to devise an strategy to take the proportion relationships among all factors in a unify form adaptively.

Therefore, to fill in this niche and to better deal with the factor priorities change over time in today’s rapidly changing environment, In this paper, we present a Dynamic Analytic hierarchy process Framework (DAF) which achieve efficiently pipeline filter ordering, DAF uses an analytic hierarchy process (AHP [7])-based ordering strategy for evaluating the factors’ priorities precisely. By carefully designing the underlying infrastructure and algorithms, DAF is able to unify the priorities factors of filters. In DAF, we propose a time-based compositional forecasting method, which is based on the fundamental of compositional data, to deal with the AHP [7] priority dynamics. Our proposed method is particularly useful when there is a large number of historical data in multimedia stream environment. Our framework addresses the above limitations of previously proposed approaches, including the following key features:

We develop an effective method to re-evaluate the selectivity factor.

We define a notion of an uniform priorities function and show that DAF can effectively evaluate the ordering of filters use our method. We show by experiment that choosing the optimal filter ordering can improve performance.

We demonstrate how DAF can adaptively change the evaluation plan as continuous queries run and that an adaptive ordering can outperform a static plan significantly when characteristics of incoming stream change.

We also develop a suite of variants on preview work [8, 10]. We have implemented our DAF algorithm in our multimedia data stream filtering system. Through experiment,we show that our DAF algorithm could significantly improve upon the performance of filter ordering. It is also shown that our proposed method provides much greater adaptability in modeling the factors priorities changing over multimedia stream compared to that of recently developed methods.

The rest of the paper is organized as follows: We formulate the shared filter ordering problem in Section 2. In Section 3 we present a brief description of the fundamentals which is used in this paper; The main contribution of this paper, which is the design the dynamic AHP[7]-based proprietors function, will be elaborated in Section 4. In Section 5, we report the experimental results obtained through our DAF framework. We discuss the related work in Section 6 and conclude the paper in Section 7.

2. Problem definition and simple solution

2.1 Problem definition

Let query $Q$ process input stream $S$ , applying the conjunction of n commutative filters $F_{1},F_{2},F_{3},\ldots,$ $F_{n}$ . For instance, in Fig. 1, there are four queries ( $Q_{1}$ , $Q_{2}$ , $Q_{3}$ , $Q_{4}$ ) and four filters ( $F_{1}$ , $F_{2}$ , $F_{3}$ , $F_{4}$ ). Every filter ${F_{i}}$ takes a stream item $t$ as input and returns a boolean value (true or false). If $F_{i}$ returns false for tuple $t$ , we say that the stream tuple $t$ satisfies the filter $F_{i}$ . If an stream item $t$ satisfies all the filters contained in a query $Q$ , we say the item satisfy the query $Q$ . For each item $t$ in the stream, we need to decide the subset of queries that are satisfied by this stream item $t$ . A plan for executing $Q$ consists of an ordering $O=F_{o(1)},F_{o(2)},\ldots,F_{o(n)}$ . When a stream item $t$ is processed by $O$ , $F_{o(1)}$ is evaluated firstly on $t$ , and $F_{o(2)}$ is evaluated secondly, and so on. For example, if we set $O=F_{2},F_{1},F_{4},F_{3}$ in Fig. 1, $F_{2}$ will be evaluated firstly for current stream item. The cost of an ordering $O$ is the expected time to process an incoming stream item $t$ to evaluation.We also use $p(i|j)$ to denote the conditional probability that $F_{o(i)}$ will return false for incoming stream item $t$ , given that $t$ satisfies any of $F_{o(1)},F_{o(2)},\ldots,F_{o(j)}$ . The unconditional probability that $t$ will return false for any stream item is denoted as $p(i|0)$ . We use $c_{i}$ to denote the expected time for $F_{i}$ to process one stream item. Note that $p(i|j)$ and $c_{i}$ maybe vary over time as input multimedia stream characteristics change; we always refer to their real-time values. With this notation we can now denote the cost of $O=F_{o(1)},F_{o(2)},\ldots,F_{o(n)}$ as:

$\displaystyle\sum\limits_{i=1}^{n}c_{i}V_{i},\ \text{where}\ V_{i}=\left\{% \begin{array}[]{ll}1&i=1\\ \prod_{j=1}^{i-1}(1-p(j|(j-1)))&i>1\end{array}\right\}$

In rapidly changing multimedia stream environment, it is very likely that the AHP priorities derived at one point in time might change in next stream window. A timely update strategy has to be carried out in order not to make a fallacious decision thereafter. In other words, to enable the multimedia data stream filtering system to respond adaptively and continuously over time of its filtering operations, there is a significant need to adaptive the changes over stream windows as to better anticipate the future stream tuples. Our goal is to decide the subset of queries that are satisfied by each incoming stream item $t$ , while minimizing the total cost incurred by the evaluation process. This problem also generalizes the well-studied classical set-cover problem[23]. We also need to maintain several data structures. Assume that $Q$ is a set of registered queries,

$\displaystyle F=\{{f_{i}}\}_{i=1}^{l}$

is the query set where $f_{i}$ is the filter. For each filter $f_{i}$ , we create a data structure $(s_{i},c_{i},a_{i},t_{i})$ , where $s_{i}$ is the selectivity of filtering unit $f_{i}$ , $c_{i}$ is the cost, $a_{i}$ is the times that $f_{i}$ is evaluated and gives a “negative” response. $t_{i}$ records the time windows from the last time of $f_{i}$ being evaluated “negative”.

Definition 1. A residual graph $G=(A,B,E)$ is a bipartite graph which consists of the need-to-be evaluated filters and the need-to-be decided queries; an edge $\{i,j\}\in E$ between filter $i$ and filter $j$ appears in this bipartite graph if filter $i\in F(j)$ .

2.2 Simple solution

In this section, we introduce two simple solution to ordering the shared filters in multimedia data stream environment. Specifically,we first formulate a generic strategy by taking all factors static just like [10]. After that,we can formulate a more effective strategy by set the selectivity value adaptive.

1.
Edge-Coverage Based Greedy algorithm (ECBG)

ECBG algorithm will not stop evaluating filters until all the queries have been decided. The choice of next being computed filter is determined by the current residual graph. Specifically, let ${G_{i}}=({A_{i}},{B_{i}},{E_{i}})$ denote the current residual graph before ECBG algorithm starts the ${i_{th}}$ filter evaluation. The ${i_{th}}$ filter to be evaluated is decided as follows: we compute the priority value of every filter in current residual graph $G_{i}$ ; we select the filter with the least priority value. After this evaluation, the current filter is removed from the residual graph. In addition, any filters whose are already not part of current residual graph and any queries that have been decided are also removed from the residual graph. We will re-compute the priority value of all the filters that are affected by the removed queries or the removed filters from current residual graph.
2.
Entry-Point Adjust Base Slider-window stream (EPABS)

We find that the selectivity of every filter is set by prior-knowledge in ECBG, so the selectivity of filters will not change over multimedia stream. This strategy can’t reflex the local information of multimedia streams. EPABS considers the special characteristics of multimedia window stream. For example, let $W_{i}$ be the $i_{th}$ stream window, we use $n$ to denote the size of multimedia stream window. After we evaluate all the $n$ items in current multimedia stream window, we should record all the outcomes of filters, and then reorder them by results. We will select the most probably-false filter as the entry-point in next multimedia stream window. We also use ECBG algorithm as the base algorithm to fulfill every stream item evaluation.

3. Our DAF framework

3.1 Simplex sample space and operations

The sample space of the compositional data is called the Simplex space[5, 6]. Specifically,in our DAF framework, we use the $P$ -part simplex space to define the priorities among all factors (selectivity, cost, popularity). So our $P$ -part simplex space can be expressed as follows:

$\displaystyle S^{P}=\left\{Y=\left[y_{1},y_{2},\ldots,y_{p}\right];y_{i}>0;% \sum_{i=1}^{P}y_{i}=k\right\}$

Where $k$ is a constant. $P$ is defined as the number of factors. $y_{i}$ is the priority of the $i_{th}$ factor.In the context of the AHP priorities, the value of $k$ is equal to 1 since the priority of each entity or alternative is a normalized score resulting from the AHP internal procedure.

We define four important terminologies in terms of the operations in our simplex space, namely, the closure operator, the perturbation operation, the power transformation, and the inner product. For any vector $Z=[z_{1},\ldots,z_{p}]$ , the closure operator $C[\bullet]$ is obtained by dividing each component by the sum of all the components and multiplying the result by the constant $k$ .

$\displaystyle C[Z]=\left(\frac{kz_{1}}{\sum\nolimits_{i=1}^{p}z_{i}},\frac{kz_% {2}}{\sum\nolimits_{i=1}^{p}z_{i}},\ldots,\frac{kz_{p}}{\sum\nolimits_{i=1}^{p% }z_{i}}\right)$

Let $X=[x_{1},\ldots,x_{p}]$ and $Y=[y_{1},\ldots,y_{p}]$ , where $X,Y\in P$ , then the main two operations in the simplex, namely, the perturbation and the power transformation, can be written as follows, respectively $A\oplus B=C[a_{1}b_{1},a_{2}b_{2},\ldots,a_{P}b_{P}]$ , $k\otimes A=C[a_{1}^{k},a_{2}^{k},\ldots,a_{P}^{k}]$ , $k\odot A=C[ka_{1},ka_{2},\ldots,ka_{P}]$ . We also define other important operations such as difference operations. These operations could be simply derived from the above operations, for example: $A\Theta B=A\oplus(-1\otimes B)$ .

The inner product of two vectors such as can be denoted as follows:

$\displaystyle<X,Y>_{a}=\sum_{k=1}^{P}\ln x_{i}/g(X)*\ln y_{i}/g(Y)$

3.2 Adaptive Composition Priorities Forecasting (ACPF)

In this section, we propose our priorities method – Adaptive Composition Priorities Forecasting (ACPF), which can be applied using a simple forecasting procedure to fit the historical priorities data on current multimedia stream. We use $W_{t}=[w_{t1},w_{t2},\ldots,w_{tp}]$ to denote the observation of compositional priorities at time point $t$ in current stream window.The ${W_{t}}$ subject to the sum

$\displaystyle\sum_{i=1}^{P}w_{ti}=k,\ \text{where}\ \left(0\leqslant k% \leqslant 1\right)$

constraint, then $t$ can be regarded as a correlation weight of all proprieties results in current stream window. $1-k$ was regarded as a correlation weight results of latest $n$ stream windows. $a_{i}$ is the weight priorities of the latest $i_{th}$ stream window. The $a_{i}$ subject to the sum

$\displaystyle\sum_{i=1}^{n}a_{i}=1-k,\ \text{where}\ \left(0\leqslant k% \leqslant 1\right)$

Following the widely known single exponential smoothing formula[2] and moving average method, Our adaptive composition priorities forecasting (ACPF) formula can be analogously expressed as in:

$\displaystyle W_{t}=a_{1}\odot R_{t-n}\oplus\ldots\oplus a_{n}\odot R_{t-1}% \oplus b\otimes W_{t-1}\oplus(k-b)\otimes W_{t-1}.$

Note that $C[1,1,\ldots,1]$ is the identity vector in the simplex space. By the same token, when $b=k$ , ${W_{t}}$ then would be reduced to:

$\displaystyle a_{1}\odot R_{t-n}\oplus a_{2}\odot R_{t-n-1}\oplus\ldots\oplus a% _{n}\odot R_{t-1}\oplus W_{t-1}$

Symbol $b$ denote the priority between the exponential smoothing and the real space. Therefore, when $b$ ranges between 0 and k, it is hoped that it can perform equally well and give time-efficient forecasts as in the real space. Then we use the ACPF to forecast the priorities of all factors (connectivity, cost, selectivity), we formula our weight function for every filter just showed as follow:

$\displaystyle\textit{price}(F_{i})=w_{\cos t}*{c_{i}}^{-1}+w_{\textit{conn}}*{% a_{i}}+w_{\textit{sele}}*({s_{i}}*{T_{i}}+(1-{s_{i}})*{F_{i}})$

In brief, in our shared filter ordering algorithm we use the last price function to finish the filter ordering evaluation.

3.3 General adaptive procedure of DAF

The proposed priorities method, which was described in the last subsections, was applied using a simple forecasting procedure. Generally, the procedure to use the proposed method can be described in Algorithm 3.3. In line 9–18, we collect the necessary historical result data on current multimedia stream, that is, the AHP final priorities of the entities or alternatives over stream window. This step uses the AHP to evaluation the priorities of all factors for a certain period of time, and the AHP was used to derive the importance of factors with respect to the existing condition during that period. In addition, these priorities evaluate from current multimedia stream over time should come from consistent judgments, as prescribed by the AHP internal mechanism. In line 22, we obtain a visual view of the change of the historical AHP priorities data of all factors over stream windows. A time series plot can be drawn using Cartesian coordinate system or a ternary diagram. In line 23, we use the proposed method, namely, the adaptive composition priorities forecasting (ACPF) method, which is described in the next subsections, to fit the historical priorities data on current multimedia stream. In this step, we select the best coefficient of the model based on which that gives the lowest value of fitting error. We use Aitchison distance[1] to evaluate the lowest fitting parameter. Next, we fit the historical priorities data using the optimal model parameter, and obtain the next period forecast.

[!hbp] : Our Adaptive Shared Filter Ordering Algorithm in DAF.[1] MultimediaStream StreamQuerySet: $Q$ FilterSet: $F$ RecordWindow: $n$ MaxSetUpSize: uMaxSetUpSize ResultVector vRes

$(i=0$ ; $i<\textit{vFilter.size()};i++)$ Filter f $=$ vFilter[i]; compute( $s_{i}$ , $c_{i}$ , $a_{i}$ , $t_{i}$ ); update( $s_{i}$ , $c_{i}$ , $a_{i}$ , $t_{i}$ );

int curItemSize $=$ 0; $\textit{vector}<\textit{priorit}>\textit{vHistory}$ ;

init_priorit();//init the vector of all history priorities factors use AHP

(!S.Empty()) AND curItemSize $<$ uMaxSetUpSize StreamItem $t=$ CurWindow(Stream).Pop(); QuerySet qs $=$ Evaluate(t); record(qs, t); curItemSize $++$ ; (CurWindow(S).end()) AHP_priorit(); Record_AHP_result();

Record_history(vHistory);//Record all AHP history result data into vHistory;

sliding window $w$

(Stream.BEGIN())

Obtain_view();//Obtain a visual view of the change of the historical priorities. Forecast_acpf( $w_{i}$ );//Use our ACPF to forecast the $w_{i}$ .

(!Stream.Empty())

StreamItem $t=$ CurWindow(Stream).Pop();

QuerySet qs $=$ Evaluate(t,Q,F);

record(qs,t);

(Stream.END())

ReCompute_priority();//Re-Compute the priorities of all factors change in current window. Record_history(vHistory);//Record all history priority of all factors into vHistory.

;

4. Experiment

In this section, we describe a number of experiments we have run to evaluate the performance of DAF. We report experimental results and comparison of the simple solutions and our proposed DAF framework. The results show that our dynamic AHP-based algorithm consistently outperforms other algorithms under various settings. In this section, we first describe our evaluation methodology, and then present the experimental results in detail.

4.1 Evaluation methodology

Our prototype system can support various formats of multimedia data streams and their associated filtering operators. For our experiments, we use a set of 240 filters built through our similarity filtering system.We build the similarity filtering data structure by vectors extracted from training photos and each of these filtering operators detects the presence of one specific concept in an image. The set of filters contains all the concepts existed in Multimedia Analysis and Retrieval System (IMARS). For our test dataset, we crawling online image, video, text from Internet use larbin [24] spider and push them into our filtering system. We implement our prototype system for evaluating queries over multimedia streams and conduct extensive experiments in the context of image stream filtering. The experiment of our filtering system is conducted on a Linux server with a Duo 2.66 GHz CPU and 2 GB memory, using a variety of queries generated from different models and parameters. Our data stream filtering system consist of a server that keeps all queries plan and filter results. Our primary objectives were to evaluate all the queries in a low time cost by properly ordering all filters and by how much DAF can outperform those previously-proposed Greedy-based approach (EPABS, ECBC). All these algorithms are used to order pipelined filters over a single multimedia stream. In experiment comparison,the most important metric is the evaluation time, which is defined as the average time taken by our filtering system to evaluate one image item against all queries. The biggest difference between EPABS and ECBG is that EPABS adjusts the selectivity value of filters after a stream window has been evaluated. To achieve a fair and meaningful comparison, in one set of experiments, we vary only one factor parameter while fixing the other parameters as the feasible value. We repeat our experiments for 20 times and the results presented are the average of multiple runs.

4.2 Experiment results

4.2.1 Robustness to filters and queries

The first question we seek to answer in our experiments is how well different algorithms perform when the queries and filters grows. So we measure the scale of the graph by the number of filters and the number of queries. We conduct two groups of experiments to investigate these two aspects respectively. Firstly, we fix the number of queries as 4000 and increase the number of unique filters from 20 to 320, at every point we exhaust all available pre-defined image filters. Secondly, we fix 120 filters and gradually increase the number of queries from 200 to 7000. The experimental results are shown in Figs 2 and 3. We can observe from the figure that our DAF outperforms the other two algorithms in all conditions. When we increase the filters in our prototype system, the performance of system becomes more sensitive compared to that of the queries. This is because many queries share the same filters. Lastly, we can see that when the scale of filtering bipartite graph grows, all three algorithms can achieve sub-linear increase. Moreover, both our DAF framework and EPABS perform much better than ECBG in these experiments. This suggests that our improve strategy of heap-adjust number and priority computation number is helpful in finding the filters whose evaluation is most beneficial.

Figure 2.

Evaluation time vs. Number of queries.

Figure 3.

Evaluation time vs. Number of filters.

4.2.2 Robustness to stream Window Size

In this section, we study the impact of Slide Window Size (i.e., the number of stream items in one stream window). We fix all the other parameters while varying the window size in our experiments. Given that all three algorithms are designed for the multimedia stream filtering, we show the evaluation time of different window size in Fig. 4. We simulate the stream window in ECBG by dividing all stream items. Intuitively, the more stream items contained by one stream window, the better the performance one would expect from our DAF framework. Figure 4 results of evaluation time with different window sizes. We can make two observations from it. Firstly, our DAF framework performs best under various window sizes. Secondly, as the window size continues to increase, the performance gap between EPABS and DAF framework shrinks. Inversely, the performance gap between ECBG and DAF framework expands. This is because with bigger stream window size, many filters’ selectivity become more appropriate for current multimedia stream. It is much better than setting selectivity value of all filters by prior knowledge. ECBG is not able to reflex the accurate local information of the multimedia streams because of setting selectivity by prior knowledge.

Figure 4.

Filtering items vs. Number of filters.

Figure 5.

Evaluation time vs. Number of filters.

Figure 6.

Filtering items vs. Number of filters.

Figure 7.

Evaluation time vs. Number of filters.

4.2.3 Robustness to adaptivity

We use a large scale of filters with different selectivities and periodically change the filters’s selectivities. Figure 5 shows a timeline from experiments where we varies the stream and filter characteristics over time. For instance, Fig. 5 shows that a change has been made after our filtering system have already processed 1000000 stream tuples. The y-axis in Fig. 5 shows the number of filters evaluated per 2500 multimedia stream tuples. As expected,when multimedia stream environment dynamic changes, Fig. 6 shows that DAF is always converges to more optimal ordering must faster than any other algorithms such as EPABS,ECBG. In general, DAF has higher run-time overhead but faster adaptivity to changes than EPABS or ECBG. Figure 7 shows this tradeoff by plotting on the y-axis the total time to process a workload where filter characteristics are varied periodically, with the period shown on the x-axis. The lower this period, the higher the rate of change, we used 160 filters, these filters’s parameter is: 100 filters’ cost is ten, 60 filters’ cost is two. We randomly change the selectivity of all filters. Figure 7 shows that when the rate of change is high, the faster adaptivity of DAF enable it to significantly outperform EPABS and ECBG. However, the advantage of DAF diminishes when we reduce the rate of change.

4.2.4 Run-time overhead comparison

Figures 3 and 6 show the processing rate and run-time break-down of all our adaptive algorithms under convergence, varying n. We use a drop-profiling probability of 0.07 in this experiment to better illustrate the differences between these algorithms. Now we see the benefits of the lower run-time overhead of EPABS and ECBG. Figure 3 shows that the gap between DAF and EPABS and ECBG increases with n. Figure 6 shows that this widening gap is solely because of DAF’s runtime overhead.

5. Related work

The problem of multi-query optimization has been tackled in[10, 11]. These works focused on relational operators of database. This is the most important difference between our problem and the multi-query in relational database. We consider the operators as arbitrary action. Adaptive Continuous Queries [12] wanted to optimize the evaluation of continuous queries defined on data streams by sharing relational operators across queries. Their strategy adapted to changes in operator costs and selectivity over time. In order to optimize a large number of continuous queries in the Internet, [12] and its extension [13, 14] proposed different grouping mechanisms for continuous queries. But they also considered the operation as the relational operator. Hence, many of their strategies are not applicable in our context. The term “shared filter ordering” was introduced by [9]. They present two different strategies to solve this problem and showed that the adaptive strategy outperformed the non-adaptive strategy. The adaptive strategy in [9] was a query-coverage base greedy algorithm. Then [10] improved upon those of [9, 10] proposed an edge-coverage based greedy algorithm whose performance was better than [9] under various settings. Our problem also generalizes the shared ordering problem [8, 9, 10].

6. Conclusion

In multimedia data streams analysis/filtering/computing scenario, each filter occur in multiple analysis queries and each query is a conjunction of filters. There usually exist multiple continuous analysis queries and the evaluation of online multimedia stream filters is indeed very expensive. An open problem in such a filtering scenario is how to order the filters in an optimal sequence to achieve significant performance. Existing works are based on a greedy strategy which orders the filters according to three factors. Although all these methods achieve good results, there are still some problems that haven’t addressed yet. First, the selectivity factor is set empirically, which can not adaptively adjust with multimedia stream.Second, the proportion relationships among the three factors were not considerably explored. Under these observations, in this paper, we propose a Dynamic-Analytic hierarchy process Framework (DAF) which use a time-based compositonal forecasting method, which is based on the idea of exponential smoothing, to deal with the factors’ proportion relationships dynamics. Experiments on both synthetic and real lift multimedia streams demonstrate that our proposed analysis framework (DAF) provides much great adaptability in modeling the factors proportion relationships changing over multimedia data stream environment.

Footnotes

Acknowledgments

This work is supported by the Joint Funds of the National Natural Science Foundation of China (Grant No. U1936111).

References

Aitchison

J.A.

Barcelo-Vidal

Martin-Fernandez

J.A.

and Pawlowsky-Glahn

, Logratio analysis and compositional distance, J Mathematical Geology 32(3) (2000), 271–275.

Hanke

J.E.

and Wichern

D.W.

, Business Forecasting, J Pearson Prentice Hall, Upper Saddle River 32(3) (2005), 271–275.

Raharjo

Xie

and Brombacher

A.C.

, On modeling dynamic priorities in the analytic hierarchy process using compositional data analysis, European Journal of Operational Research 194 (2009), 834–836.

Viglas

Naughton

and Burger

, Maximizing the output rate of multi-join queries over streaming information sources, In Proc. of the 2003 Intl. Conf. on Very Large Data Bases, Sept 2003.

Aitchison

, The statistical analysis of compositional data, Journal of the Royal Statistical Society, Series B (Methodological) 44(2) (1982), 139–177.

Aitchison

, The statistical analysis of compositional data, Monographs on Statistics and Applied Probability, Chapman and Hall, London, 1986.

Saaty

T.L.

, A scaling method for priorities in Hierarchical structures, Journal of Mathematical Psychology 15 (1977), 59–62.

Babu

Motwani

Munagala

Nishizawa

and Widom

, Adaptive ordering of pipelined stream filters, In SIGMOD’04: Proceedings of the ACM SIGMOD International Conference on Management of Data, 2004, pp. 407–418.

Munagala

Srivastava

and Widom

, Optimization of continuous queries with shared expensive filters, In PODS’07: Proceedings of the 26th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2007, pp. 215–224.

10.

Liu

Parthasarathy

Ranganathan

and Yang

, Near-optimal algorithms for shared filter evaluation in data stream systems, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, 2008,

11.

Mistry

Roy

Sudarshan

and Ramamritham

, Materialized view selection and maintenance using multi-query optimization, In SIGMOD’01: Proceedings of the ACM SIGMOD International Conference on Management of Data, 2001, pp. 307–318.

12.

Madden

Shah

Hellerstein

J.M.

and Raman

, Continuously adaptive continuous queries over streams, In SIGMOD’02: Proceedings of the ACM SIGMOD International Conference on Management of Data, 2002, pp. 49–60.

13.

Chen

DeWitt

and Naughton

, Design and evaluation of alternative selection placement strategies in optimizing continuous queries, In ICDE’02:Proceedings of the 18th International Conference on Data Engineering, 2002, pp. 345–356.

14.

Chen

DeWitt

Tian

and Wang

, NiagaraCQ: A scalable continuous query system for Internet databases, In SIGMOD’00: Proceedings of the ACM SIGMOD International Conference on Management of Data, 2000, pp. 379–390.

15.

Goemans

and Vondrak

, Stochastic covering and adaptivity, In LATIN’06: Proceedings of the 7th Latin American Symposium on Theoretical Informatics, 2006.

16.

Aguilera

Strom

Sturman

Astley

and Chandra

, Matching events in a content-based subscription system, In PODC’99: Proceedings of the 18th ACM Symposium on Principles of Distributed Computing, 1999, pp. 53–61.

17.

Cugola

Nitto

E.D.

and Fuggetta

, Exploiting an event-based infrastructure to develop complex distributed systems, In ICSE’98: Proceedings of the 20th International Conference on Software Engineering, 1998, pp. 261–270.

18.

Cilia

Bornhoevd

and Buchmann

A.P.

, CREAM: An infrastructure for distributed,heterogeneous event-based applications, In Proceedings of International Conference on Cooperative Information Systems, 2003, pp. 482–502.

19.

Petrovic

Burcea

and Jacobsen

H.-A.

, S-ToPSS:Semantic Toronto publish/subscribe system, In VLDB’03: Proceedings of the 29th International Conference on Very Large Data Bases, 2003, pp. 101–1104.

20.

Petrovic

Liu

and Jacobsen

H.-A.

, G-ToPSS:Fast filtering of graph-based metadata, In WWW’05: Proceedings of the 14th International Conference on World Wide Web, 2005, pp. 539–547.

21.

Narasimhan

, An analytical approach to supplier selection, Journal of Purchasing and Materials Management 19(1) (1983), 27–32.

22.

See Thomas Saaty

, The Analytic Hierarchy Process (New York: McGraw-Hill) for a more extensive discussion of AHP, 1980.

23.

Vazirani

V.V.

, Approximation algorithms.Springer-Verlag, Inc., New York, NY, USA, 2001.

24.

Sebastien Ailleret http://larbin.sourceforge.net/index-eng.html.

DAF : An adaptive computing framework for multimedia data streams analysis

Abstract

Keywords

1. Introduction

Table 1 Query example: Q 1 , Q 2 , Q 3 , Q 4

2.1 Problem definition

2.2 Simple solution

3.1 Simplex sample space and operations

3.2 Adaptive Composition Priorities Forecasting (ACPF)

3.3 General adaptive procedure of DAF

4. Experiment

4.1 Evaluation methodology

4.2 Experiment results

4.2.1 Robustness to filters and queries

4.2.4 Run-time overhead comparison

5. Related work

6. Conclusion

Footnotes

Acknowledgments

References

Table 1
Query example: $Q_{1}$ , $Q_{2}$ , $Q_{3}$ , $Q_{4}$