The Web is a constantly updating source of information. A large number of latest developments, events and commentaries are constantly being posted on the Web in the form of blogs, news articles, usenet posts etc. In order to help the users avoid the tedious task of periodically searching for updated information on the Web, some of the search engines provide an ``alert'' service (e.g. Google alerts  or Live alerts ). The main idea is to let the users create profiles (e.g. by specifying a few query keywords) describing the information for which they would like to receive updates. After that, the search engines are continuously monitoring the newly collected information from the Web and will alert the user (e.g. through email) whenever there is new information that matches the user's profile. In this way, the user can stay current with a developing news story, track a good deal on a desired product or follow who is writing about her blog.
The continuous monitoring of the Web to match a given set of user-defined keywords, is also known as continuous querying. Typically, the results of a continuous query can be returned to the user either in an ``as-found'' basis or ``in-batch'' after a particular time interval (e.g. once a day).
Although running continuous queries on the Web can potentially help the users to stay current with important updates, in general, the amount of information returned as updates to the user can be ``unbounded''. For example, if the user is following a very controversial or popular topic, she may receive hundreds of updated pages as an alert, and may thus be overwhelmed by this huge amount of information.
Since a user typically can allow a limited time for comprehending the information delivered to her, one way to alleviate this problem is to allow the user to restrict (or bound)1 the number of returned results within a particular time interval. More specifically, the user may decide that, say, every day, she is interested in reading only the 10 most relevant updates to her continuous query and would like to receive only those updates. For the cases where it is acceptable to return the results in-batch the solution is straightforward: we first collect all the relevant results within a day, we rank them and then return the top-10 to the user. However, in the cases where the ``freshness'' of the results is very important, and thus we need to return them as-found, the user is not willing to wait until we collect all the relevant results and return them at the end of the query period. For example, if a user is tracking Web pages describing digital cameras offered for sale, she would like to know the 10 best pages according to some specification as soon as they appear, since the cameras may be sold after a short period of time.
Returning the best results in an as-found basis to a given continuous query involves two main challenges. First, the potentially relevant results within a time period (e.g. a day) are not known in advance. Without knowing all the relevant results how can we find the top- among them to return to the user? Second, the points in time where the top- relevant results will appear are also not known in advance. Given that the freshness of results is very important, how can we ensure that we return the top- results as soon as they appear?
Regarding the first challenge, clearly we will have to wait until we see all results in order to calculate the exact top-. However, in a practical scenario, we may safely assume that the user is willing to exchange some imprecision in the top- results for a greater freshness. For example, in our digital camera example, the user may be happy to receive the 10 deals out of which only 9 belong to the top-10, but receive them soon enough to actually be able to buy the products.
Given this relevance/freshness tradeoff, in this paper we present an optimization method for bounded continuous search queries on the Web. More specifically, our goal is to extract the top- relevant pages that appear over a specified time interval on the Web and return them to the user as soon as possible. Our proposed solution utilizes principles from the field of optimal stopping  in order to realize fresh, high quality and a bounded number of search results during a specified execution time of a continuous query. Optimal stopping is a well-known problem in the field of financial mathematics. The main idea of this paper is to consider the development of the relevance of versions of Web pages as relevance charts and to treat the problem of estimating top-k results as-found similar to a basic problem in financial mathematics, the problem of finding the buying or selling points for stocks at optimal prices.
In summary, our contributions in this paper are:
- We define bounded continuous search queries as standing search queries that extract the estimated top-k documents from a specific Web area over a period of time. Bounded search queries have the advantage that the amount of information returned to a user is controlled without further user interaction in contrast to many previous approaches in the field of document filtering or topic tracking.
- Considering bounded continuous queries we demonstrate that there is a tradeoff between freshness and the quality of query results.
- We present and evaluate a new method to optimize the retrieval quality for the cases where up-to-date information is required by the user. The new approach is based on the optimal stopping theory and estimates the relative ranking values of future documents based on previous observations in a stream of documents.
In the next section we start our discussion by presenting the strategy that is presently employed by the current search engines. In section we demonstrate that in the cases where we need to obtain information as up-to-date as possible, current approaches may return sub-optimal results to the users. In Section we define a new language for bounded continuous search queries and present our optimization approach which utilizes principles from the field of optimal stopping . Finally, in the experimental section we verify that our new method can generate fresher and more relevant results for a variety of continuous queries. We conclude with an overview of related research and a summary.
In this section we give basic
definitions and present a common strategy to process bounded
continuous search queries that is applied by Web search systems
and used as a reference strategy in this paper.
1 Periodic Evaluation Method
In this work we consider a simple stream of documents or versions of a specific document . The index corresponds to the time a document is obtained from the Web in a push or a pull manner .2
We consider bounding conditions that are specified by the maximal number of documents to be returned. A bounding condition provided by a user corresponds to the maximal information load a user is willing to accept with respect to a query. It is obvious that threshold-based information filtering methods presented in the field of topic tracking and detection  are not bounded. We consider query profiles that are determined by a set of query terms provided by a user. We may thereby assume that query profiles, similar to documents, may be expressed in a term vector space. Well-known methods from Information Retrieval may therefore be applied to compute a distance between a query profile and a document.
Based on the tf-idf measure  we may apply the function
A problem of this measure is the computation of the
term. At a specific point in
time the entire set of documents appearing in the stream is not
yet available. Possible approaches to this problem have been
presented in ,
 and . In this work we consider each
version of the information source or incoming document as a
single document 'collection'. The -term is based only on the state of the information
source at the current point in time. If is the state of the information source
at time we denote the respective ranking of document
with respect to
the query as
described above in this work we make the simplifying assumption
that at each point in time a single (new) document is available.
We may therefore define
The function is used to obtain relevance estimations for new documents in the sequence with respect to a query profile. In this work we simplify the search for optimal documents by defining quality as the estimation provided by the ranking function . Quality is used as a synonym for the relevance of documents.
In order to find optimal documents we have therefore simply to find documents with the highest ranking values according to . This quality definition is used because the development of estimation functions similar to (1) is not the focus of this paper but has been examined thoroughly in the field of information retrieval. In this paper we show that even if an optimal estimator for the quality of documents is given (or assumed) the optimization of bounded continuous search queries is not a trivial problem.
Based on the previous definitions we may now define a common strategy to process bounded document filtering.
In this work we consider a PE method that applies function (1) as the ranking or evaluation function. Obviously a PE method is a bounded filtering method according to definition 1 due to the bounding condition, which may e.g. imply a maximal number of pages returned in each evaluation period or a total maximal number. In the latter case the number of returned pages per evaluation period is determined by (the closest integer to) the total number of documents to be returned according to the bounding condition divided by , the number of evaluation periods. A PE-query may e.g. inquire about the 'best 10' pages each day with respect to a set of query terms, as e.g. realized by the GoogleAlert system . The PE-method is illustrated in figure . In the figure ''-symbols denote ranking values depending on the current state of a specific data source or a new document in a stream, a query profile and a ranking function (as e.g. function (1)). In this case the query execution time is . There are two evaluation periods. The bounding condition is 4, i.e. the best two documents in each evaluation period have to be selected and forwarded to a user as indicated by circled ranking values.
In this section we
demonstrate cases where the PE strategy is sub-optimal and
thereby illustrate the tradeoff-problem between freshness of
information and the quality of retrieved results.
2 The freshness/quality tradeoff
It is obvious from figure that by applying the PE strategy documents are returned with a certain delay between the point in time when a document is obtained3 and the time at the end of an evaluation period when a document or a respective notification is forwarded to a user. We may therefore define a freshness (or reciprocal: delay) metric as:
It may now be shown that a PE-method is not optimal if a high freshness is required.
The validity of this theorem may be demonstrated by
considering the example in figure 1. If
the best documents have to be selected that appear during the
query execution time the optimal
strategy is to store documents and to wait until . At this point the 4 highest ranked documents may be
returned if we assume that the bounding condition implies a
number of 4 documents to be returned. However, as shown in the
example in figure 1 the delay-value as
defined above may be significant.
href="#foot55">1 In order to acquire fresher
results, a larger number of evaluation periods has to be
considered. In figure 1 the query period
is subdivided into 2 evaluation periods. The bounding condition
in this case is 2 documents for each of the two evaluation
periods in order to fulfill the global bounding condition of
maximal 4 documents. The freshness of retrieved optimal documents
is obviously increased. However the selected documents (as
illustrated by circled ' '-symbols) are no longer the optimal ones and
represent a suboptimal choice.
The reason for this decrease of retrieval quality is the missing knowledge about future document rankings if objects are evaluated at an earlier point in time. This is obviously an intrinsic problem if the optimization of bounded continuous search queries is concerned. There is no method that has information about future data objects and therefore each conceivable method is subject to this problem, which we denote as freshness/quality tradeoff. lemmaLemma
It has to be noted that this tradeoff-problem is not valid for threshold-based filtering methods. In the example in figure we wouldn't have the restriction of the maximal number of objects to be returned and could forward each object above a specified threshold. However in this case not knowing future ranking values, a suboptimal threshold may be chosen, which affects precision and recall results.
3 A query method for bounded continuous search (BCS) queries
In this section we describe the
main syntax of a new query language to state bounded continuous
search (BCS) queries and in subsequent sections we describe how
these queries are answered within our prototype system.
1 The query language 'BCSQL'
At a high level, we employ a query model similar to the OpenCQ language . In OpenCQ a continuous query is a triple consisting of a normal query (e.g. written in SQL), a trigger condition and a termination criterion . In this work we consider only time-based trigger conditions. We extend the basic notation of OpenCQ in order to support continuous search queries. For this purpose we assume the availability of a ranking function for query results as provided by (1). A main extension with respect to many continuous query languages is the possibility to provide a bounding condition. In the considered query language a user has to define the number of estimated best results to be returned. This feature is well-known from common search engines. The best 'n' results are displayed on the first result page. A further specific attribute is the requirement to specify a user profile consisting of query terms. An example for the considered query language is the following:
- CREATE BCSQ:
- SalesWatch as
- SELECT ESTIMATED BEST
FROM SERVER www.ebay.com
WHERE query='camera 12 mega flash'
- 60 minutes
- 7 days
- 0 minutes
In the example the current version may contain the terms 'camera 12 mega' but a future version may contain the terms 'camera 12 mega' and 'flash' which declassifies the current version. However if the query engine waits until all versions have been available, the respective cameras may already be sold.
In the following we refer to this query language as bounded
continuous search query language (BCSQL).
In this section we
give an introduction into the considered optimal stopping
problem, frequently denoted as 'Secretary Selection problem'
(SSP). We first summarize results from the literature that are
the basis for the optimization method in this paper.
2 Answering queries: selecting the best k
In the classical SSP a sequence of ranked objects is presented to a 'player'. The player has the task to choose the best object. The choice is based only on previous observations. The ranking values of the objects are assumed to be distinct and equally distributed.6 An object has to be chosen immediately when presented to the player and may not be chosen later. This basic problem has been analyzed e.g. in  and . A well-known strategy for this problem is to observe a number of candidates without choosing them. The respective ranking values of candidates are stored. After this observation period the first subsequent candidate is chosen that has a higher ranking than the maximal ranking value of the candidates in the observation period. The main problem then is to find an optimal length of the observation period. An optimal strategy for this problem in order to maximize the probability of finding the best candidate is to choose an observation period of , where is the number of candidates and is the Euler number. In other words approximately one third of the candidates should be observed without being chosen. This result has been proved 'in the limit', for . Further strategies for the basic SSP are discussed in . Extensions of the basic SSP have been proposed in  and .
In contrast to the problem of selecting one single best candidate, in this paper we consider the more general problem of selecting the best candidates in a stream of ranked documents by choices, we denote as k-SSP. An obvious extension of the single SSP is not to consider a single observation period (needed to adjust the optimal selection probability) but to consider observation periods. Our method, following an approach in , first implies the choice of starting times .7 After rejecting the first candidates, the first candidate considered for selection is examined at or after time .
(1) If candidates have already been examined with objects accepted and rejected, the object is chosen if it is at least better than one of the objects already selected. It is rejected if it is worse than at least one of the objects rejected.
(2) If among all the candidates examined so far the is ranked (between the accepted and the rejected objects) it is chosen if and rejected if , where is the current point in time.
(3) If choices have been made where and candidates are left with respect to the entire sequence of input candidates to be evaluated, all of the remaining candidates must be chosen in order to guarantee that objects are chosen.
In this paper we do not provide a proof for the previous strategy but in the experiments the algorithm is evaluated with artificial and real relevance sequences.
An example is shown in figure . We denote
the sequence of candidates as
We consider a number of 2 candidates to be returned and two
are rejected due to the first observation phase. Candidate
at is accepted because it is better than all of
the previously rejected candidates.
is better than all the previously rejected candidates and worse
than all the previously accepted candidates. It is rejected
because it appears before the stopping time . It would have been accepted if
. is accepted because it is better than at least one
previously accepted candidate. Due to the previous choice of two
candidates, candidates and are not considered.
Based on this selection strategy the main problem is to find optimal times in order to maximize the probability of choosing the best candidates. Due to the equal distribution of ranking values intuitively the starting times should be spread evenly over the considered time period. In  a strategy is proposed to position starting times that is proved to be optimal and applied in section .
3 Application of the k-SSP for BCS processingIn the SSP as in the BCSQL optimization problem the candidates or versions of the data source appear sequentially ordered one after another. There exists a definite starting point and a definite endpoint in the BCSQL problem. In the SSP the starting point is determined by the time of the appearance of the first, the endpoint by the appearance of the last candidate. The trigger condition in the BCSQL corresponds to the considered candidates in the SSP. Each candidate is assigned a ranking value in the SSP. In the SSP the ranking values are assumed to be distinct. In the BCSQL problem this property depends on the applied ranking function and may not be fulfilled (especially if the data source did not change between 2 trigger executions). The condition of different ranking values may be guaranteed artificially by considering ranking values that depend on time, i.e. versions appearing later in the sequence are assigned a lower ranking value. In the SSP as in the CQ problem the selection strategy may be based only on previous observations. No information about future objects is available. In contrast to the general BCS query language in section the delay parameter is not adjustable if the SSP is applied to the optimization of retrieval results. Results are returned immediately (delay=0) if estimated to have a high ranking.
Figure shows the
basic steps of the BCS query processing algorithm. The input of
the algorithm are the start and the end time of the continuous
query, the trigger condition, a value '' for the number of estimated best items to be chosen and
a query profile .
4 A query engine for BCS processing
Based on the start, the end time and the trigger condition in steps 1 and 2 the number of reload operations (i.e. the number of 'candidates') and the times of reload operations are computed. Applying the k-SSP strategy in section the starting times are computed based on the number of candidates and the number 'k' of highly ranked candidates to be chosen. At time the first candidate is loaded in step 7 and the ranking with respect to the search query '' is computed (section 2.1). The ranking is compared to previous ranking values in step 9 which are available in the list and the relative ranking is computed. In step 10 it is determined if a new version is chosen as a highly ranked candidate according to section . In figure we assume the availability of a function isSelected(C) that indicates, if a candidate C has been selected. In step 11 the new candidate C is inserted into the list rankList at the position determined by the ranking value. If the candidate is chosen, a message is sent to the client. Finally the algorithm waits until the time of the subsequent reload time in step 13 and returns to step 6.
BCS-Query-Processing (Input: start-time s, end-time e, trigger-condition tc, 'number of best choices' k, Query Q)
- rankList := null
- compute number of candidates based on s,e,tc
- compute reload times based on s,e,tc
- compute starting times based on ,
- wait until
- for(i = 1,...)
- load candidate
- compute ranking based on ,
- compare to previous rankings
- select or reject according to
- selection strategy )
- insert into rankList
- if( isSelected(C) ) send message to client
In the following experiments we compare the new
BCS query method to the period evaluation (PE) method. The
considered quality parameters are the freshness of the retrieved
information according to eq. () and the
quality of search results according to definition . Applying
the k-SSP method (figure ) objects
that are estimated to be relevant are returned to a user
immediately after detection on the Web.8 In this case we
assume an immediate decision of the filtering method and the
delay value in formula () is
In definition we defined the quality or relevance of a single document retrieved by a search engine. In order to measure the quality of a set of retrieved documents we build the sum of quality values of the individual documents. In  a very similar relevance measure is presented that is based on graded relevance assessments (in contrast to binary relevance assessments usually considered in IR). In  the functions
for the graded recall (gr) and the graded precision (gp) are proposed, where denotes the entire set of documents and relevance is a function providing relevance values for documents, retr is the set of retrieved documents. In the experiments we apply the same measures and define the relevance function according to definition .
In the experiments we work with simulated and real data. In the k-SSP method a special distribution of ranking values, in particular an equal likelihood of each new ranking value, is assumed. Real data sometimes are not distributed like that.
1 Simulated dataIn this paragraph we demonstrate experiments with simulated data in order to analyze statistical properties of the presented BCS method compared to the PE method. The main advantage to consider simulated data is a simple and exactly known distribution of input data which helps to illustrate main properties of the new method. In these experiments sequences of distinct ranking values of candidate size with identical likelihoods are generated. An individual sequence is gradually provided as an input to the BCS and PE algorithms.
Comparison of the BCSQL and PE strategy (generated data)In the experiment shown in figure the retrieval quality of the BCS strategy is lower than the retrieval quality of the PE(1) strategy. However the BCSQL results are returned to a user immediately while the PE(1) strategy returns results at the end of a single evaluation period which is in this case identical to the query period. If fresher results are requested when using the PE method obviously a larger number of evaluation periods has to be considered during the query execution time. We proportion requested items to the number of evaluation periods. If the selected candidates are proportioned with an equal likelood to the evaluation periods. In the following we consider the tradeoff between retrieval quality and freshness of data.
The intersection point of the fitting lines of BCS and PE(n) strategy (IS) defines the (x-axis)-point ( in figure (left)) of the maximal number of evaluation periods where the graded recall of the PE strategy is better than the graded recall of the BCS strategy. I.e. if the number of intervals is further increased because fresher results shall be returned by the PE strategy, the retrieval quality is lower than the retrieval quality of the BCS method. Below the intersection point IS in figure (left) the PE strategy therefore becomes inferior to the BCS strategy. The BCS strategy provides maximal freshness due to an immediate delivery of results. In this situation also the retrieval quality is superior to the PE method in a probabilistic sense.
In order to quantify this situation, in figure (right) we consider the delay of the considered strategies according to definition (). The data points close to denote the delay of results of the PE strategy considering a single evaluation period (PE(1)). The figure shows that results are delivered with a delay of approximately 0.550% of the entire query execution time. If e.g. the query execution time is 40 days, results are returned with a delay of 20 days. Curve shows the delay of the PE(n) method where the number of evaluation periods is increased from 1 to N. Obviously the delay converges monotonically to 0. The main point in this graph is the y-value of the PE-delay (figure (right)) where the x value () corresponds to the x-value of the intersection point IS in the figure on the left. This point marks the minimal delay of the PE strategy where the retrieval quality is better than the retrieval quality of the BCS strategy. In other words: If results are requested by a user that are fresher than , a user should prefer the BCS strategy presuming he wants to acquire maximal retrieval quality. Otherwise, if less fresh results are sufficient, the PE strategy should be applied. We denote as -turning point in the following. The -turning point is obtained by a local linear fit of the PE and BCS recall close to the intersection point IS in figure (left) and by computing the intersection point of the respective PE and BCS fitting lines (close to and in figure , left). Then the point in the PE-delay graph (the intersection of the -value and the PE-delay graph) has to be extracted. In the example in figure (right) BCS should be used if results are requested that are fresher than 3.3% of the query execution time. If the entire query period is 40 days, the BCS strategy should be used if results should be fresher than 1.3 days.
In the following experiments we
applied the BCS strategy to data sources on the Web. In
particular we considered the homepages of diverse newspapers in
English or German. Before the experiments we first created a Web
archive over a period of a quarter of a year. By using a Web
crawler at regular points in time (twice a day) a mirror of the
sources was obtained and stored periodically.
2 Real information sources
Based on the obtained Web archive we extracted a number of query terms. These query terms were the most frequent terms in the archive not contained in the list of stop words. Thereby 480 German and 480 English query terms were extracted.
In the following experiments we considered BCS queries of the following structure:
Query: SELECT ESTIMATED BEST d
FROM PAGE url WHERE query='singleterm'
Trigger=9h and 17h, Start=now, Stop=80days
We applied the queries to the Web archive; the trigger condition corresponds to the versions available in the Web archive. The delay-parameter is 0 for the k-SSP estimation method and 80 days for the PE(1) method (single evaluation period).
|gr||gr depend. on maximal delay||optimal gr|
|source (language)||2 days||4 days||8 days||12 days||(in days)|
|normalized mean value||57%||18%||31%||58%||73%||100%|
Table shows a representative fraction of these experiments. The table shows the retrieval quality (graded recall) of the BCS, the PE(j) and the PE(1) strategy for 12 Web pages, 7 in German and 5 in English. We consider a number of the 4 best objects to be chosen (). Each entry in the table is the mean value of the respective quality parameters of all considered (480 German and 480 English) queries. In these experiments we specified a maximal delay of returned results of 2, 4, 8 and 12 days and adjusted the number of evaluation intervals in the PE(j) method respectively. The table shows the resulting graded recall (gr) values of the different methods and the turning point (in days) for each source.
As expected, the retrieval quality of the new BCS method is smaller than the quality of the PE(1) method which is the maximal retrieval quality with respect to the number of retrieved pages. If a higher freshness of results is requested, the retrieval quality of the PE(n) method decreased in the experiments. The value (in days) in table marks the maximal freshness where a user obtains the best results by the PE(n) method. Below this point the BCS strategy provides results of a higher retrieval quality. The last row of table shows the mean values of all data sources standardized by the maximal recall value provided by the PE(1) strategy.
5 Related researchQuery systems are available to automate and simplify similar search problems which are known as continuous, monitoring, notification, alert or information dissemination services. Many publishers provide e.g. table-of-contents or alert functions, such as ACM Table-of-Contents Alert , Springer Link Alert  or Elsevier Contents Direct . Independent mediating alerting services like Hermes  or Dias  provide access to heterogeneous digital libraries.
Query languages for continuous queries are well-known in the field of active databases , , . In this field the event-condition-action model (ECA) is used to define standing queries to databases. Every time the event occurs, a trigger condition is tested. The testing result may cause the execution of the defined action. The respective information is assumed to be structured. In many information dissemination systems, too , , the considered query languages concern structured or semistructured data , , , , , , . In  and  continuous query languages for information on the Web are presented that are more appropriate in a Web context and allow e.g. the evaluation of requests to Web forms. Although the basic syntax of the query language considered in this paper is similar to many of the previous languages, we focus on unstructured data, in particular documents extracted from Web pages, similar to the approaches in  and . The respective task to extract relevant documents from a stream of documents is well-known from the TREC-filtering track , , , , , ,  and the field of topic detection and tracking , , . In the filtering track of the Text Retrieval Conference (TREC)  streams of documents are considered. The task is to optimize methods that realize an immediate distribution of relevant documents. A binary decision is made to either accept or reject a document as it arrives. The information such classifiers are based on is usually a set of training examples, i.e. documents provided with a relevance label and possibly a topic description. This information is used to create a query profile which is applied to estimate the relevance of future documents by a distance computation between the generated query profile and a new document. The decision to either accept a document as relevant or not is finally based on a threshold value which may also be learned by the training examples. In the 'adaptive' filtering track  the query profile or the threshold are tuned by feedback provided by a user after the appearance of a new document.10 Similar to the TREC filtering track the field of topic detection and tracking (TDT) , ,  deals with the problem of finding relevant documents in a document stream. In this case the classifications are based on a significantly smaller training set and tracking (of events or topics) should start immediately, which is more appropriate for real applications.
These previous filtering or tracking methods are usually threshold-based . The returned information load is 'unbounded' according to definition 1. In contrast to this in order to control the amount of information returned by a query engine without the need of further user interaction in this paper we consider bounded continuous search queries. Although bounded query strategies are well-known and applied in current Web search systems , , to our knowledge the quality/freshness tradeoff has not been thoroughly examined for bounded continuous search queries. Following approaches developed in the field of optimal stopping , , , , ,  we develop a new solution for the optimization of bounded continuous search queries.
6 ConclusionIn this paper we consider continuous search queries as a means to search for information appearing in a specific Web area over a period of time. Assuming a query profile and a distance measure between profile and documents there are two basic strategies to process continuous search queries. A first strategy is to adjust a quality threshold in order to extract relevant documents. The second strategy is to estimate the best 'k' documents that appear in the document stream. In this paper we focus on the latter query method which we denote as bounded continuous search. The main advantages to consider bounded queries is a simple query formulation since no threshold (except the maximal amount of information to be returned) has to be provided. Second, there is no risk for a user to spend too much time reviewing the documents or to overlook important documents because of an information overflow. On the other hand if bounded continuous search queries are concerned there is a tradeoff between freshness and quality of the retrieved information. In this paper we show that this freshness/quality tradeoff may lead to suboptimal choices of documents if very fresh information is required. We show in experiments that in this case by applying optimal stopping theory the quality of retrieved information may be improved significantly.
Optimal stopping is a problem well-known in the field of financial mathematics . The results of this paper indicate that, considering charts of the relevance of document versions, further instruments from the field of financial mathematics may be applied to improve continuous search queries.
- ACM Table-of-Contents Alert.
URL: http://portal.acm.org, 2006.
- J. Allan, J. Carbonell, G. Doddington, J. Yamron, and Y.
Topic detection and tracking pilot study: Final report.
In Proc. of the DARPA Broadcast News Transcription and Understanding Workshop, pages 194-218, 1998.
- J. Allan, R. Papka, and V. Lavrenko.
On-line new event detection and tracking.
In SIGIR '98: Proc. of the 21st annual international ACM SIGIR conf. on Research and development in information retrieval, pages 37-45, New York, NY, USA, 1998. ACM Press.
- A. Arampatzis and A. van Hameran.
The score-distributional threshold optimization for adaptive binary classification tasks.
In SIGIR '01: Proc. of the 24th annual international ACM SIGIR conf. on Research and development in information retrieval, pages 285-293, New York, NY, USA, 2001. ACM Press.
- A. Arasu, S.Babu, and J.Widom.
The cql continuous query language: semantic foundations and query execution.
VLDB J., 15(2):121-142, 2006.
- S. Babu and J.Widom.
Continuous queries over data streams.
SIGMOD Rec., 30(3):109-120, 2001.
- K. Collins-Thompson, P. Ogilvie, Y. Zhang, and J.
Information filtering, novelty detection, and named-page finding.
In TREC 2002. Gaithersburg, 2002.
- Elsevier contents direct.
URL: http://www.sciencedirect.com/, 2006.
- P. T. Eugster, P. A. Felber, R. Guerraoui, and A.-M.
The many faces of publish/subscribe.
ACM Comput. Surv., 35(2):114-131, 2003.
- F. Fabret, H. A. Jacobsen, F. Llirbat, J. Pereira, K. A.
Ross, and D. Shasha.
Filtering algorithms and implementation for very fast publish/subscribe systems.
In SIGMOD '01: Proc. of the 2001 ACM SIGMOD international conf. on Management of data, pages 115-126, New York, NY, USA, 2001. ACM Press.
- D. Faensen, L. Faulstich, H. Schweppe, A. Hinze, and A.
Hermes: a notification service for digital libraries.
In JCDL '01: Proc. of the 1st ACM/IEEE-CS joint conf. on digital libraries, pages 373-380, New York, NY, USA, 2001. ACM Press.
- T. Ferguson.
Who solved the secretary problem?
Statistical Science, 4(3):282-289, 1988.
- P. Foltz and S. Dumais.
Personalized information delivery: an analysis of information filtering methods.
Commun. ACM, 35(12):51-60, 1992.
- P. Freeman.
The secretary problem and its extensions: a review.
Int. Statistical Review, 51:189-206, 1983.
- K. S. Glasser, R.Holzsager, and A. Barron.
The d choice secretary problem.
Comm. Statist. -Sequential Anal., 2(3):177-199, 1983.
- Google alert.
URL: http://www.googlealert.com, 2006.
- A. Hinze.
Efficient filtering of composite events.
In Proc. of the 20th British National Database Conf., 2003.
- D. Hull.
The TREC 6 filtering track: Description and analysis.
In The Sixth Text Retrieval Conf. (TREC-6), pages 45-68. Gaithersburg, 1997.
- R. Kadison.
Strategies in the secretary problem.
Expo. Math., 12(2):125-144, 1994.
- J. Kekalainen and K.Jarvelin.
Using graded relevance assessments in IR evaluation.
J. of the American Society for Information Science and Technology, 53(13), 2002.
- J. Kendall and K. Kendall.
Information delivery systems: an exploration of web pull and push technologies.
Commun. AIS, 1(4es):1-43, 1999.
- M. Koubarakis, T. Koutris, C. Tryfonopoulos, and P.
Information alert in distributed digital libraries: The models, languages, and architecture of DIAS.
In ECDL '02: Proc. of the 6th European Conf. on Research and Advanced Technology for Digital Libraries, pages 527-542, London, UK, 2002. Springer.
- L. Liu, C.Pu, and W.Tang.
Continual queries for internet scale event-driven information delivery.
Knowledge and Data Engineering, 11(4):610-628, 1999.
- L. Liu, C.Pu, and W.Tang.
Webcq-detecting and delivering information changes on the web.
In CIKM '00: Proc. of the 9th int. conf. on Information and knowledge management, pages 512-519, New York, NY, USA, 2000. ACM Press.
- R.-L. Liu and W.-J. Lin.
Adaptive sampling for thresholding in document filtering and classification.
Inf. Process. Manage., 41(4):745-758, 2005.
- Windows live alerts.
URL: http://alerts.live.com/Alerts/Default.aspx, 2006.
- G. Mhl.
Large-Scale Content-Based Publish /Subscribe Systems.
PhD thesis, Darmstadt University of Technology, 2002.
- S. Pandey, K. Ramamritham, and S. Chakrabarti.
Monitoring the dynamic web to respond to continuous queries.
In WWW '03: Proc. of the 12th international conf. on World Wide Web, pages 659-668. ACM Press, 2003.
- J. Pereira, F. Fabret, F. Llirbat, R. Preotiuc-Pietro, K.
A. Ross, and D. Shasha.
Publish/subscribe on the web at extreme speed.
In VLDB, pages 627-630, 2000.
- J. Praeter.
On multiple choice secretary problems.
Mathematics of Operations Research, 19(3):597-602, 1994.
- S. Robertson and I.Soboroff.
The TREC 2002 filtering track report.
In The Eleventh Text Retrieval Conf. (TREC 2002), 2002.
- G. Salton and M.J.McGill.
Introduction to modern information retrieval.
- U. Schreier, H.Pirahesh, R.Agrawal, and C. Mohan.
Alert: An architecture for transforming a passive dbms into an active dbms.
In 17th Int. Conf. on Very Large Data Bases (VLDB), pages 469-478, 1991.
- A. Shiryaev and G.Peskir.
Optimal Stopping and Free-Boundary Problems (Lectures in Mathematics. ETH Zrich).
- Springer link alert.
URL: http://www.springerlink.com, 2006.
- T. W. Yan and H.Garcia-Molina.
The SIFT information dissemination system.
ACM Transactions on Database Systems, 24(4):529-565, 1999.
- Y. Yang.
A study on thresholding strategies for text categorization.
In W. B. Croft, D. J. Harper, D. H. Kraft, and J. Zobel, editors, Proc. of SIGIR-01, 24th ACM International Conf. on Research and Development in Information Retrieval, pages 137-145, New Orleans, US, 2001. ACM Press, New York, US.
- Y. Yang, T. Pierce, and J. Carbonell.
A study of retrospective and on-line event detection.
In SIGIR '98: Proc. of the 21st annual international ACM SIGIR conf. on Research and development in information retrieval, pages 28-36, New York, NY, USA, 1998. ACM Press.
- B. Yuwono, S. L. Y. Lam, J. H. Ying, and D. L. Lee.
A World Wide Web resource discovery system.
In In Fourth International World Wide Web Conf., Boston, pages 145-158, 1995.
- C. Zhai, P.Jansen, E.Stoica, N.Grot, and D.A.Evans.
Threshold calibration in CLARIT adaptive filtering.
In Text REtrieval Conf. 1998, pages 96-103, 1998.
- Y. Zhang and J. Callan.
Maximum likelihood estimation for filtering thresholds.
In SIGIR '01: Proc. of the 24th annual international ACM SIGIR conf. on Research and development in information retrieval, pages 294-302, New York, NY, USA, 2001. ACM Press.
- ... bound)1
- A bounded information load is very familiar to users with respect to other media like television or magazines. Newscasts and other transmissions on television typically take a well-defined amount of time.
- The extension to a stream of document-sets consisting of documents respectively , where is a set of (new) documents , is not the focus of this paper. In this case the applied information retrieval measures presented here have to be modified as described e.g. in .
- ... obtained3
- We consider the time needed to compute a ranking value negligible. Therefore the time a document is obtained corresponds to the x-axis values of ''-symbols in figure .
- Obviously by this method results are returned with a delay of 50% of the query execution time on average assuming equally distributed ranking values.
- ... Web.5
- If 'Delay = 1 week' obviously the optimal objects may be selected (at the end of the week). If however Delay 1 week, usually only a suboptimal choice is possible.
- ... distributed.6
- If denotes the ranking position of object with respect to objects , then the independence assumption is , .
- We consider discrete times. If e.g. candidates have been rejected and accepted we are at time . A rank of '1' marks the best object.
- ... Web.8
- We ignore the time to perform the relevance estimation. Objects that are rejected due to the learning period of the filter affect the quality but not freshness value.
- ... 1.9
- Considering PE(1) there is a slight decrease of the graded precision for increasing -value due to definition ().
- ... document.10
- On-line feedback may be simulated by successive revealing of training data.