Web wrappers access databases hidden in the deep web by first interacting with web sites by, e.g., filling forms or clicking buttons, to extract the relevant data from the thus unearthed result pages. Though the (semi-)automatic induction and maintenance of such wrappers has been extensively studied, the efficient execution and optimization of wrappers has seen far less attention. We demonstrate that static and adaptive optimisation techniques, as used for query languages, significantly improve the wrapper execution performance. At the same time, we highlight difference between wrapper optimisation and common query optimisation for databases: (1) The runtime of wrappers is entirely dominated by page loads, while other operations (such as querying DOMs) have almost no impact, requiring a new cost model to guide the optimisation. (2) While adaptive query planning is otherwise often considered inessential, wrappers need to be optimised during runtime, since crucial information on the structure of the visited pages becomes only accessible at runtime. We introduce two basic, but highly effective optimisation techniques, one static, one adaptive, and show that they can easily cut wrapper evaluation time by one order of magnitude. We demonstrate our approach with wrappers specified in OXPath.
The research leading to these results has received funding from the European Research Council under the European Community’s Seventh Framework Programme (FP7/2007–2013) / ERC grant agreement DIADEM, no. 246858.
Copyright c 2012 for the individual papers by the papers’ authors. Copying permitted for private and academic purposes. This volume is published and copyrighted by its editors.
Antonino Rullo 1.
Facing ever growing amounts of information, we are surrounded by new, exciting opportunities – which we can only realize by automatizing web data extraction further. But next to reducing the amount of human assistance in wrapper generation, large-scale extraction tasks also require efficient wrapper execution, particularly by avoiding unnecessary page loads. To achieve this goal, we have to statically optimize our wrappers, and even more importantly, we need to apply some crucial adaptive optimizations during runtime to exploit information on the underlying page template: For example, after learning that following the “contact” link in a given page template never leads to pages relevant to the extraction task at hand, we might want to filter the “contact” link.
In response, we propose a framework for static and dynamic
wrappers optimization. We base our optimization on a model, where
wrappers alternate local selection and extraction steps with action
steps, executed on DOM nodes, such as clicking on links. As the
performance of a wrapper is overwhelmingly dominated by the
number of pages loads, our optimizations aim to (
We evaluate our approach with OXPath [4], a wrapper language which extends XPath with actions, Kleene stars, extraction facilities, and access to the dynamic DOM of the pages under scrutiny, including all computed styles (briefly introduced in Section 3).
Contributions. (
Wrappers extract data from many web pages and typically run several minutes or hours rather than seconds as traditional database queries. Almost all existing wrapper languages execute wrappers as a sequence of selection and extraction operations partitioned by action operations. Selection operations determine which DOM elements extraction operations or actions are performed on. Extraction operations specify how to extract those nodes, and action operations specify browser actions such as submitting a form or clicking a link. Together we refer to all three as wrapper operations. We say that action operations partition wrapper executions, as all selection and extraction operations between two such actions involve the same DOM (resulting from the preceding action). In case of an, e.g., OXPath wrapper, sequences of XPath steps (selection operations) and extraction markers (extraction operations) alternate with action steps.
DEFINITION 1. A wrapper plan is a (possibly cyclic) graph with selection and extraction operations as node labels and action operations as edge labels, all possibly empty. Aside normal edges, we distinguish two edges types: Branch edges indicate where results from one branch are used to filter another branch. Cycle edges indicate cycles in the evaluation plan. If we eliminate all cycle edges, a wrapper plan is a directed, acyclic graph with a dedicated start node.
Figure 1 shows an example plan with actions ai and selection and extraction operations si. It contains a cycle, from s1 to s4, which indicates that these expressions are executed as long as they match. Typically such cycles represent repeated actions, such as clicking on “next” links to traverse all paginated results obtained after some query. It also contains a branch at s1 to indicate that the wrapper explores the web site in two different ways starting from the page obtained by fa1g. The branch specifies an additional restriction on the extracted nodes, indicated by the red, dashed link rejoining the main branch, and thus acts like predicates in XPath or where clauses in XQuery. Figure 3 shows branches used to filter another branch.
We call a sequence S of visited pages the page footprint of a wrapper plan W (or one of its connected subgraphs), if executing W touches the pages in S in order. A wrapper plan is sequential if no node has more than one incoming branch edge. We denote with SUCC(o) the successor to an operation o following only normal edges, disregarding branch or cycle edges.
For the purpose of this paper, we model the cost of a wrapper with a rough, static cost model, while our results are easily adjusted to richer cost models. We assume that we can estimate selectivity and cost of each operation o, denoted with SELECTIVITY(o) and COST(o). Then the cost of a wrapper W is:
COST(W ) = å s(o) o2W
where STRUCT(o) = s(o) = s(o0)
Õ p incoming edge e >:1 8k > < if e is a cycle edge if e is a branch edge otherwise As the focus of this paper is not a sophisticated cost model, we approximate the impact of cycles and branches roughly through fixed multiplicative factors k and p (typically, k = 3 and p = 0:5).
DEFINITION 2. Let W be a wrapper plan. A sequential wrapper plan O is HTML-optimal for W , if O produces the same output as W on all HTML pages and has minimal cost among such plans. Let C be a cycle in W and P a set of page footprints of C. Then O is template-optimal to W under C and P if W and O produce the same output on all page footprints in P while O has minimal cost among all such sequences.
In the following, we focus on a particular aspect of optimizing wrapper plans: As shown in [4] and further substantiated in Section 6, actions dominate the execution of wrappers, as they lead to page loading necessitating network communication and page rendering. Thus, we focus on optimizations that reduce the number of actions to be performed. Corresponding to the two types of optimality introduced above, we introduce static optimizations, based on HTML schema and usage statistics, as well as dynamic optimizations, adapting a wrapper’s execution according to observations on already visited pages.
(
(
Suppose you are looking for an apartment in the city center, not
larger than 70 m2, newly refurbished, with balcony and garage,
preferably close to a bus stop and a school for your children. All
this information is readily available on the web, but even modern
aggregators will fail to (
To overcome these drawbacks, we designed OXPath, an
extension of XPath, which facilitates interactions with modern web
applications for the sake of data extraction: (
Figure 2 showcases all OXPath extensions mentioned above,
marking all actions (
<paper><title>The diameter of the world..</title> 2 <authors>R Albert, H Jeong, ...</authors>
<cited_by> 4 <title>Emergence of scaling in ... </title>
<authors>AL Barabasi...</authors></cited_by> 6 <cited_by> .....</paper>
Wrapper plans for OXPath. To build a wrapper plan from an OXPath expression E, we segment E into actions and actionfree chunks. Then, we form an automaton with actions on edges, 2 4
In this section, we focus on static optimization striving for
HTMLoptimality, i.e., optimizations which are valid on all HTML
documents (Definition 2). To that end, we (
Let W be a sequential wrapper plan with a sequence S of nodes each with incoming branch edges, but connected into a path through normal edges. We further assume a function FIXED(p) that determines if p may be commuted with other branches. In OXPath, FIXED(p) holds only for branches containing extraction markers or positional functions (i.e., position() or last()). All other branches can be commuted as necessary. Then, S = ~p0q1~p1q2 : : : qn~pn where q1; : : : ; qn are fixed branches in S and ~pi a sequence of commutable ones. We sort each ~pi by cost. In most cases, this means moving predicates without actions first, predicate with actions last as the cost of action execution dominates the overall wrapper cost.
Recall the example from Section 3 with the wrapper plan shown in Figure 3. The following wrapper is obtained by reordering the predicates, both in the outer case and in the inner one. doc(’url’)//div[@class=’person’] [a/{click/}//div[@class=’woman’]
[a/{click/}//h1~=’Person’)]]
It is not possible to move the last two predicates before the one with the actions, as the one starting with h1 contains an extraction marker and thus partitions the set of predicates.
Our cost model with p = 0:5 suggests that the additional predicates, applied before the action execution, lead to 50% less action executions each, thus leading to only 25% of the second click actions compared to the naive case. In this example, however, the reduction is actually even more significant, since the reordered predicates preclude almost all matching links from being followed. doc
a h1[1] :<name> click //div
a click
con.t.a.ins presence of such a schema are computationally highly expensive tasks, provably intractable for rich wrapper languages going well beyond navigational XPath [10]. Since we are adapting the wrapper plan during execution, such complete optimization approaches are infeasible, and hence, we choose a set of simple local heuristics, instead. The local heuristics generate alternative expressions for selecting the final node set selected by each si using attributes such as id and class, the direct children or parents, the content etc. We use these expression generators also to determine if P is a template cluster (rather than more complete methods such as [7]): If we can find succinct expressions for most si there is a good likelihood that the pages come from the same template.
To illustrate the process, consider an example from the realestate domain, where we want to extract the URLs to floor plans. Unfortunately, many real estate websites, particularly aggregators, present floor plans mixed with photos of the property. Therefore, a user, tasked with generating a wrapper to extract floor plans, may create the following wrapper: After clicking on all image links, it checks on the resulting page for a floor plan (by considering the alt text not available on the first page). //li//div//a/img/{click/}//img[@alt ~= "floor plan"]:<A=string(@src)>
Wrapping template-based websites usually involves dynamically
generated pages, which are similar in structure but different in
content. Also, different pages link to a certain number of common
pages, e.g., “contact us” info or details pages for products.
Therefore, for long running wrappers, e.g., for the exhaustive extraction
from a products website, it is possible to (
For (
For (
It is part of a wrapper that cycles on all properties of the website at hand. Properties on a page are located by //li, while their respective picture sections are grouped in a descendant div as image links (a elements with contained images). These links point to pages with the actual image in full resolution. We identify it using it’s alt text (i.e., tooltip) that contains the phrase “floor plan”.
This is an easy to understand and probably rather robust wrapper, however, it requires one action (and thus page load) for every image. When executing this wrapper, the system finds that in all the pages touched by the cycle, the floor plan images can actually Re-plan by Adaptive Rewriting. Let W be a sequential wrap- identified already on the initial page: They occur only in specific per plan with a cycle C, where P is a footprint of C during an eval- li’s that represent offers and have data-ajax attributes. Although uation of W , such that P forms a template cluster [7], i.e., a set of together this forms a very specific selection expression it is also a pages likely from the same template. We have C = s0fa1ga1 : : : fangsn very fragile expression (as, e.g., the IDs are often auto-generated where each si is an action-free expression (possibly involving branches) and the data-ajax attributes are an artefact of using a specific genand each ai is an action. Then we build a new sequential wrap- eration library). Thus neither human wrapper authors nor wrapper per W 0 as optimisation of W by replacing si with si0, such that induction systems are likely to generate these expressions. At runsi0 is more selective than si, yet s00 fa1g : : : fangsn0 is template- time, however, we do not care about robustness across different equivalent to C under P. Hence, W 0 is template-equivalent to W runs and thus use the more fragile, but less expensive selection: under P and has lower cost (in particular it executes less actions).
How do we obtain si0? Unfortunately, both inferring the regular structure (or DTD) for P [1] and the optimization of wrappers in naive evaluation time (sec) optimized evaluation time (sec) naive evaluation time (sec) optimized evaluation time (sec)
With the new wrapper, we only execute one action per floor plan (rather than one per image). The new wrapper is significantly cheaper according to the cost model in Section 2, which estimates that only 2p of the context nodes in the original wrapper will also be context nodes for {click/} in the new wrapper, i.e., a reduction by 75%. For the actual web site (zoopla.co.uk) the reduction is actually over 90%.
Recall by Action Tabling. For the second optimization, we recall the results of expressions already evaluated on pages touched repeatedly by a wrapper plan. Let E = s1a1r be a connected subgraph of a wrapper plan W where s1 is some action-free expression, a1 an action, and r the rest of a branch in the wrapper plan.
For recall, we maintain a table that maps action expressions, such as a1, together with URLs of the resulting pages to the results of evaluating the rest of the wrapper branch (here: r) on those pages.
An entry is only created if an action yields a new page (rather than modifications to an existing one).
Unfortunately, this still requires that the action is performed each
time, though all actions in r are skipped. To avoid the initial
action, we use a simple heuristic for recognizing nodes on which an
action for sure leads to a new page and we can determine that page
from the node. For space reasons, we only give a sample of these
heuristics: (
To illustrate this, consider a wrapper on rightmove.co.uk that aims to extract properties together with contact information about the agent. Unfortunately, those contact information are available only from the “Contact us” page, which remains the same for the same agent. Thus, in the following wrapper, we table the href attributes of the .contactUs links and recall of extracted agent information, if the same href is encountered again. 2 //a.contactUs/{click/}//div[1]:<agent>
[.//li.agency:<name=string(.)>][.//li.addr:<addr=string(.)>] Rather than one action for each of the over 650; 000 properties, we thus only perform one for each of the about 10; 000 agents.
We show the effectiveness of the presented optimization techniques, using OXPath as wrapping language.
Static. In this experiment on rightmove.co.uk, the largest aggregator for the real estate in UK, we extract the addresses of properties offered by agents supplying more than 100 sale offers. To this end, we apply the following expression on each result page: This expression visits all div elements, and – in the assumption that these div-s represent indeed offers – attempts to navigate to the agent’s logo next to each property, click it, click another image to reach all the agent’s offers to finally check the number of these offers. Next, the expression also checks that the div has class ’summarymaincontent’, before extracting the relevant address.
We apply static optimizations (Section 4) to reorder adjacent predicates to minimize the impact of actions. Since predicate Ê contains actions while Ë is action free, our static optimization produces an equivalent expression by reordering them such that Ë precedes Ê. Hence, the wrapper avoids clicking on logos which are not part of property summaries – avoiding many unnecessary page loads. Also, if the template changes, dropping or changing the ’summarymaincontent’ class, thus spoiling the wrapper, we avoid loading pages without extracting any data at the end.
The evaluation of the original expression takes on a single result page 60 seconds in average, while our optimized expression terminates in 2 seconds on average.
Re-plan. spareroom.co.uk/flatshare/oxford lists rooms for rent, that we want to extract as records R, each described with a div#summary node on the page. To this end, we run several times the following wrapper Qx, parametrized with x, an upper iteration bound we use to scale the impact of adaptive rewriting. (//a#next/{click/})*{0,x}//div#summary:<R> 2 [.//div[last()]/a/{click/}//h1.about:<contactUs=string(.)>] Among other attributes (omitted for brevity), we also extract contact information visiting the website’s about page by clicking on the corresponding link. This link is located at the bottom of the listed rooms (last div), searched for via //div[last()]/a. As a result, we select too many links and need to identify the targeted data by matching h1 elements on the visited pages afterwards. This is a common situation, especially with wrappers generated by some (un-)supervised tool.
As shown in Figure 4, a naive evaluation is very wasteful in time due to the number of unnecessary actions. Indeed, after observing a number of pages generated from the same template, our wrapper is dynamically optimized in considering only those links which lead to successful data extraction. In our case, we re-plan by replacing //div[last()]/a with //div[last()]/a[position()=1 | @name], i.e., selecting only links in first position or with attribute name. Recall. For this experiment, we run the following expression Qx, again on the UK real-estate aggregator rightmove.co.uk. We extract a record R for each listed property, including the agent’s name and phone number. To reach this data, we first click on the agent’s logo in each property //div.branchlogo/img to open a further page where we extract the relevant data. Throughout evaluation, the same contact data is likely to be extracted multiple times. As described in Section 5, tabling is applicable to sub-expressions preceding actions. In this case, we retain the result of evaluating //div.branchlogo/img together with the image’s src attribute value. Thus, once retained, we reuse the same data instead of re-executing the necessary but now redundant actions. Figure 5 compares the time of naive versus optimized evaluation with an increasing number of loops. While the naive evaluation is basically linear in the number of loops, the optimized evaluation varies irregularly, as it depends on the hit rate of the ongoing tabling. But in any case, it takes significantly less time, with a more pronounced effect at greater iteration numbers, cutting the evaluation time more than half at 20 iterations. 7.
Though web wrapper induction and maintenance is an extensively studied problem, this is not the case for wrapper optimization. In most cases, optimization is performed as an integral part of wrapper induction [14, 8], however, optimizing more for coverage and precision of the wrapper than for efficiency. In [3], e.g., candidate wrapping rules are filtered based on the expected schema of the data to be extracted, improving the precision of the wrapper.
One might suspect that the wrappers created by wrapper induction systems are close to optimal and thus further optimization is not necessary. However, learning efficient tree patterns or XPath queries is fundamental to many wrapper approaches, while proving to be inherently hard [12], even more so in presence of negative examples. This theoretical concern is underlined by the poor performance of existing wrapper engines demonstrated in [4]. Indeed, the results of this paper illustrate that, considering the vast resources used even by efficient wrapper engines such as OXPath, wrapper optimisation can have significant impact.
Many wrapper induction systems are based partially on standard XML query languages such as XPath or (less frequently) XQuery and can thus profit from existing optimization techniques for these languages. XPath optimization can be distinguished into static, syntactic rewriting techniques, such as [11, 10, 5], and cost-based plan selection as considered in [6, 2]. However, in most wrapping scenarios the cost of action steps dominates all other costs, yet actions are not part of XPath or XQuery and thus existing techniques are only pertinent to action-free parts. Optimizing action-free parts, however, has only little overall impact.
Our static and dynamic optimization methods are both variants of well-known query optimization techniques. The static optimization is an instance of the selection ordering problem [9], which refers to the problem of determining an order for applying a given set of commutative selection predicates (filters) to all tuples of a relation. The dynamic optimization is an instance of adaptive query planning [9] and of tabling techniques used for the evaluation of recursive or fixpoint languages [13]. However, neither has been applied to web wrappers before, where the presence of browser actions significantly affects their application. E.g., for tabling, it is sufficient to store the results for each unique page, as in-page selection and extraction does not significantly affect the overall performance, leading to smaller and more efficient tables. 8.
We have introduced wrapper optimization as problem in its own
right, observing two idiosyncrasies: (
After showing the effectiveness of a fundamental set of optimizations in this paper, in our future work, we will fully implement our approach, possibly with a refined cost model, altogether with further optimizations.