Progressive Deep Web Crawling Through Keyword Queries For Data Enrichment
CC Attribution 3.0 Germany:
You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal purpose as long as the work is attributed to the author in the manner specified by the author or licensor.
Wang, Pei
Shea, Ryan
Wang, Jiannan
Wu, Eugene
Data enrichment is the act of extending a local database with new attributes from external data sources. In this paper, we study a novel problem—how to progressively crawl the deep web (i.e., a hidden database) through a keyword-search API to enrich a local database in an e ective way. This is chal- lenging because these interfaces often limit the data access by enforcing the top-k constraint or limiting the number of queries that can be issued within a time window. In response, we propose SmartCrawl, a new framework to collect re- sults e ectively. Given a query budget b, SmartCrawl rst constructs a query pool based on the local database, and then iteratively issues a set of most bene cial queries to the hidden database such that the union of the query results can cover the maximum number of local records. The key technical challenge is how to estimate query bene t, i.e., the number of local records that can be covered by a given query. A simple approach is to estimate it as the query frequency in the local database. We nd that this is ine ective due to i) the impact of |?D|, where |?D| represents the number of local records that cannot be found in the hidden database, and ii) the top-k constraint enforced by the hidden database. We study how to mitigate the negative impacts of the two factors and propose e ective optimization techniques to improve performance. The experimental results show that on both simulated and real-world hidden databases, SmartCrawl signi cantly increases coverage over the local database as compared to the baselines.
 I'm Pei, I'm from Simon Freider University. I'm a PhD student there and it's my pleasure to present our paper, Progressive Deep Web Crawling Through Keyword Chorus for Data Enrichment. And I'm grateful to my collaborators, Ryan, Jenna, who is my supervisor, and Eugene over there. So data preparation is an important issue these days and a lot of projects are focusing on it. For example, the data civiliz- civilizor project which can help the user to find a relevant data set and the SNOCOL project which helps the user to build and manage the training data and the big-groud gorilla which is a collection of the data preparation libraries and the trifecta which is a data prep tool. But even before the data prep step, the big question is where does the data come from? So when I talk to my data scientist friend and in a data scientist class that we teach in school, the first step is actually to collect the data. But oftentimes, instead of having random data or studying from zero, we already have some data that we want to work with. So what we really want to do is to augment the data. And one type of the data augmentation is to add one more attribute or several more attributes to the existing data records. Like in this table, we want to add two more columns. So here in this example, we have a list of restaurants where we have the restaurant names, addresses, and cities. And we want to fill in the category and reading column so that we can build better models or obtaining new insights for the data. But how should we do it? So in the most extreme case, we can just search each record over the Yelp. And it will take hours of time just for thousands of rows. So here is an outline of my talk. And I like to start with the background. So data enrichment provides a lot of benefit and use cases. For example, we can get new insights for analysis and marketing. We can build better machine learning models. And we can construct knowledge base. And the enriched data can also help with the error detection. And there are two lines of existing research we can adopt to fulfill these tasks. The first existing research proposed to augment the local table with the web tables. But this is not realistic to a data scientist because, first of all, the web table copies are not available. For example, Google's web table and Microsoft has their own web table copies too. But it's not open to the data scientist. And even if we have the access to these tables, it's very hard to use because it's a huge corpus. And the logo here, the Common Crowd, which is public and open-sourced web table, which everyone can leverage, but it's just a sample of the whole web. And if we enrich the local table with it, the information may be incomplete in rows and columns. And for the second existing research, a company can also buy all the relevant data sets. But this is overkilling the problem. And you can imagine that you just have thousands of rows, but are you going to buy the whole Yelp database just to enrich this data set? And also some markets sell by API costs rather than the full data sets. So in this case, how to issue the corpus efficiently is also important. So let's start with what is DIP-WAP. It refers to the websites with their own online databases. For example, here, Yelp contains all the restaurant information. Red Fan is a DIP-WAP for real estate and the MDB for movie and Goodreads for books. And this collection of websites, they have three properties which are nice for data enrichment. First, they have a very big volume of data. Because if you imagine Yelp, it probably covers all the restaurant you know. And they have very rich attribute information for each entity they have. And they're of high quality because they're often human curated. And we also call this hidden database. I'd also like to talk a bit more about the search interface. So in this, so we formulated the keyword search interface as the follows. So they're matched based on the index fields. For example, the restaurant title and the tokens, if the tokens are exact match, then the result will be returned. But the search interface only returned top key match results by an unknown ranking function divided by the website. And in this paper, we treat the search interface as a conjunctive queries. And we surveyed a lot of existing APIs and we found many of them just satisfied the assumptions here. So next, I'd like to talk about our problem and the challenge and our solutions. So we further decompose the challenge to two levels. At the technical level, we handle the process of crawling. We study how to make the crawling process efficient. In this work, we just focus on the API service provided by the website. So to be more formally, given a query barred B and a local database and keyword search interface over a hidden database, our goal is to select a set of queries to be issued to each. And we want to maximize the coverage of the local table. And then most naive way is just to match one record at a time. And this is how it works in a famous data prep to open a reform as Google reform. And so if you have a restaurant data set, and we just concatenate all the tokens in a restaurant title and then issue it to the Yelp or something else. So this naive approach has two limitations. First, it has very high query cost. Remember that query cost is a very precious resource in this case. For example, Yelp API is restricted to 25,000 free requests per day. And Google map API only allows 2,500 free requests per day. And we want to leverage this resource really well. And secondly, it is not able to tolerate the keyword misspelling. As I mentioned, most of the APIs, most of the keyword search interface, they just can handle the exact match at the token level. So if there are some errors in the token, so the naive crowd will miss the result. So to this end, I'd like to propose our frameworks macro, and I'll start with this simple toy example. So in the left side, it is a local table we have. And we have four restaurant names here. And in the right side, it is the hidden database. And it is not visible to the user, and it can be just queried by API. So our first idea is to generate a query pool with both specific and general queries so that all the records in the local database has a chance to be covered. For example, here Q1 to Q4 are specific queries just the same as the ones we use for naive crowd. And Q5 to Q7 are the general queries, which have a chance to cover multiple records for the local table. So in the most ideal situation, if we know the result, if we know what kind of result will be returned if we issue a query, this problem can be easily reduced to a side cover problem. Like if we know the tie will return us these three records and the Q4 will return this, then we can just issue these two queries and then the problem is down. However, this is hard because the search API will just return us the top key results. For example, the Haas keyword here, it is extremely frequent in the hidden database. And if we issue it, we don't know which of them will appear in the top key result. It might not be so beneficial. So it's not a good choice to issue it. So our second idea is to select the queries with the highest estimated benefit. And in our paper, we propose to estimate the benefit of queries with a small sample collected from the hidden database. And we proposed several estimators to estimate the benefit of each query. And in this week, we can reduce the problem to a side cover problem. And if you're interested in technical details, please refer to the paper. And remember that SMACRA is just an algorithm and it's not intuitive about how to put it into real use because it is coupled with several other components too. For example, we need to handle schema matching, we need to handle under evolution, and we need to interact with the user and let them decide what is the data set that they want. So for the schema matching, here is a screenshot of our system. So the user just need to click the buttons to decide what schemas are the matches. And then based on this matched schema, we can do the interolution using a similarity function. And the user can also click and un-click the attributes below the yellow labels to decide what are the attributes he wants to include or exclude in his result data set. So here is the website of our system or demo, you can play with it. And we open sourced our library and a developer just need to configure the algorithm and call the SMACRA function and he can enrich his local table just in minutes or seconds. And next I'm going to show you a demo. And in this demo, I will start with a set in the asset with two columns and I will show three things. One is the basic functionalities, which is how to enrich the asset with a DBLP API. And then to prove that our SMACRA algorithm is more tolerant to data errors, I will randomly add some errors to the data set and see how it goes. And finally, because the Manner is another citation website, which can provide us some attributes that are not available in DBLP API, for example, the citation counts. So we also enable the user to re-enrich the data set produced by the previous step. Okay, so here we have this example data set with two columns, title and author. And we want to enrich it with the DBLP API. And if we click try it now, and as I mentioned, user just need to click the schemas to be matched. And then the SMACRA algorithm runs in a background. And just within seconds, we get the result. As you can see, the SMACRA is able to cover 35 records within four queries, but Naive only covers four records with four queries. So now we have the matched result and we can decide what attribute to be enriched or excluded. So this is the original data set. We can randomly add some errors like the red text and we run it again and repeat the process. Because the SMACRA issued the general queries more, so this time SMACRA does not have much decrease, but the Naive crowd just covered one result. And for the label here, that means there are several matches for the local record and the user can adjust the true match based on their justification. So now we can re-enrich the data set we have using the in-manner API. And the goal is to obtain extra attribute which does not exist in the DBLP API. And we repeat the process. And now we can add the number of citations to our result data table. So finally for the experiment part, firstly we want to understand how our algorithm performs. So we did a simulation experiment on the DBLP data set. For this experiment, we sampled 10,000 citation records from the whole data set. And we treated the whole data set as the hidden database which has more than 5 million of records and we fixed the query budget as 2,000. So in this result figure, you can see the green line is the SMACRA and the orange line is the Naive crowd. And the SMACRA is able to cover 4.5 times records compared with the Naive crowd. And we also tested our algorithm using the reward data set. So we sampled 3,000 of records from a restaurant data set and we issue queries against the YOP.com in an exhaustive way. And we want to understand how the algorithm will perform in the end instead of using a fixed budget. But if you see this figure, the SMACRA algorithm can quickly cover a large amount of records compared with the Naive crowd which almost increased linearly. So if we fix the query budget as 900, the SMACRA can almost cover 2 times of records than the Naive crowd. And if you look at the end of the line, the SMACRA actually covers more records than the Naive crowd which means SMACRA is more robust to the data errors. So finally for the takeaways. So in this work, we are motivated by the needs of data enrichment and we are the first to study this problem by leveraging the deep web. And we developed an end system to reduce the energy time from hours to minutes. And we demonstrate that SMACRA covers up to 4 times more records than the baselines. Thank you and I'm happy to take questions.
 I'm Pei, I'm from Simon Freider University.  I'm a PhD student there and it's my pleasure to present our paper, Progressive Deep Web  Crawling Through Keyword Chorus for Data Enrichment.  And I'm grateful to my collaborators, Ryan, Jenna, who is my supervisor, and Eugene over  there.  So data preparation is an important issue these days and a lot of projects are focusing  on it.  For example, the data civiliz- civilizor project which can help the user to find a relevant  data set and the SNOCOL project which helps the user to build and manage the training  data and the big-groud gorilla which is a collection of the data preparation libraries  and the trifecta which is a data prep tool.  But even before the data prep step, the big question is where does the data come from?  So when I talk to my data scientist friend and in a data scientist class that we teach  in school, the first step is actually to collect the data.  But oftentimes, instead of having random data or studying from zero, we already have some  data that we want to work with.  So what we really want to do is to augment the data.  And one type of the data augmentation is to add one more attribute or several more attributes  to the existing data records.  Like in this table, we want to add two more columns.  So here in this example, we have a list of restaurants where we have the restaurant names,  addresses, and cities.  And we want to fill in the category and reading column so that we can build better models  or obtaining new insights for the data.  But how should we do it?  So in the most extreme case, we can just search each record over the Yelp.  And it will take hours of time just for thousands of rows.  So here is an outline of my talk.  And I like to start with the background.  So data enrichment provides a lot of benefit and use cases.  For example, we can get new insights for analysis and marketing.  We can build better machine learning models.  And we can construct knowledge base.  And the enriched data can also help with the error detection.  And there are two lines of existing research we can adopt to fulfill these tasks.  The first existing research proposed to augment the local table with the web tables.  But this is not realistic to a data scientist because, first of all, the web table copies  are not available.  For example, Google's web table and Microsoft has their own web table copies too.  But it's not open to the data scientist.  And even if we have the access to these tables, it's very hard to use because it's a huge  corpus.  And the logo here, the Common Crowd, which is public and open-sourced web table, which  everyone can leverage, but it's just a sample of the whole web.  And if we enrich the local table with it, the information may be incomplete in rows  and columns.  And for the second existing research, a company can also buy all the relevant data sets.  But this is overkilling the problem.  And you can imagine that you just have thousands of rows, but are you going to buy the whole  Yelp database just to enrich this data set?  And also some markets sell by API costs rather than the full data sets.  So in this case, how to issue the corpus efficiently is also important.  So let's start with what is DIP-WAP.  It refers to the websites with their own online databases.  For example, here, Yelp contains all the restaurant information.  Red Fan is a DIP-WAP for real estate and the MDB for movie and Goodreads for books.  And this collection of websites, they have three properties which are nice for data enrichment.  First, they have a very big volume of data.  Because if you imagine Yelp, it probably covers all the restaurant you know.  And they have very rich attribute information for each entity they have.  And they're of high quality because they're often human curated.  And we also call this hidden database.  I'd also like to talk a bit more about the search interface.  So in this, so we formulated the keyword search interface as the follows.  So they're matched based on the index fields.  For example, the restaurant title and the tokens, if the tokens are exact match, then  the result will be returned.  But the search interface only returned top key match results by an unknown ranking function  divided by the website.  And in this paper, we treat the search interface as a conjunctive queries.  And we surveyed a lot of existing APIs and we found many of them just satisfied the assumptions  here.  So next, I'd like to talk about our problem and the challenge and our solutions.  So we further decompose the challenge to two levels.  At the technical level, we handle the process of crawling.  We study how to make the crawling process efficient.  In this work, we just focus on the API service provided by the website.  So to be more formally, given a query barred B and a local database and keyword search interface  over a hidden database, our goal is to select a set of queries to be issued to each.  And we want to maximize the coverage of the local table.  And then most naive way is just to match one record at a time.  And this is how it works in a famous data prep to open a reform as Google reform.  And so if you have a restaurant data set, and we just concatenate all the tokens in  a restaurant title and then issue it to the Yelp or something else.  So this naive approach has two limitations.  First, it has very high query cost.  Remember that query cost is a very precious resource in this case.  For example, Yelp API is restricted to 25,000 free requests per day.  And Google map API only allows 2,500 free requests per day.  And we want to leverage this resource really well.  And secondly, it is not able to tolerate the keyword misspelling.  As I mentioned, most of the APIs, most of the keyword search interface, they just can  handle the exact match at the token level.  So if there are some errors in the token, so the naive crowd will miss the result.  So to this end, I'd like to propose our frameworks macro, and I'll start with this simple toy  example.  So in the left side, it is a local table we have.  And we have four restaurant names here.  And in the right side, it is the hidden database.  And it is not visible to the user, and it can be just queried by API.  So our first idea is to generate a query pool with both specific and general queries  so that all the records in the local database has a chance to be covered.  For example, here Q1 to Q4 are specific queries just the same as the ones we use for naive  crowd.  And Q5 to Q7 are the general queries, which have a chance to cover multiple records for  the local table.  So in the most ideal situation, if we know the result, if we know what kind of result  will be returned if we issue a query, this problem can be easily reduced to a side cover  problem.  Like if we know the tie will return us these three records and the Q4 will return this,  then we can just issue these two queries and then the problem is down.  However, this is hard because the search API will just return us the top key results.  For example, the Haas keyword here, it is extremely frequent in the hidden database.  And if we issue it, we don't know which of them will appear in the top key result.  It might not be so beneficial.  So it's not a good choice to issue it.  So our second idea is to select the queries with the highest estimated benefit.  And in our paper, we propose to estimate the benefit of queries with a small sample collected  from the hidden database.  And we proposed several estimators to estimate the benefit of each query.  And in this week, we can reduce the problem to a side cover problem.  And if you're interested in technical details, please refer to the paper.  And remember that SMACRA is just an algorithm and it's not intuitive about how to put it  into real use because it is coupled with several other components too.  For example, we need to handle schema matching, we need to handle under evolution, and we  need to interact with the user and let them decide what is the data set that they want.  So for the schema matching, here is a screenshot of our system.  So the user just need to click the buttons to decide what schemas are the matches.  And then based on this matched schema, we can do the interolution using a similarity function.  And the user can also click and un-click the attributes below the yellow labels to decide  what are the attributes he wants to include or exclude in his result data set.  So here is the website of our system or demo, you can play with it.  And we open sourced our library and a developer just need to configure the algorithm and call  the SMACRA function and he can enrich his local table just in minutes or seconds.  And next I'm going to show you a demo.  And in this demo, I will start with a set in the asset with two columns and I will show  three things.  One is the basic functionalities, which is how to enrich the asset with a DBLP API.  And then to prove that our SMACRA algorithm is more tolerant to data errors, I will randomly  add some errors to the data set and see how it goes.  And finally, because the Manner is another citation website, which can provide us some  attributes that are not available in DBLP API, for example, the citation counts.  So we also enable the user to re-enrich the data set produced by the previous step.  Okay, so here we have this example data set with two columns, title and author.  And we want to enrich it with the DBLP API.  And if we click try it now, and as I mentioned, user just need to click the schemas to be  matched.  And then the SMACRA algorithm runs in a background.  And just within seconds, we get the result.  As you can see, the SMACRA is able to cover 35 records within four queries, but Naive  only covers four records with four queries.  So now we have the matched result and we can decide what attribute to be enriched or excluded.  So this is the original data set.  We can randomly add some errors like the red text and we run it again and repeat the process.  Because the SMACRA issued the general queries more, so this time SMACRA does not have much  decrease, but the Naive crowd just covered one result.  And for the label here, that means there are several matches for the local record and the  user can adjust the true match based on their justification.  So now we can re-enrich the data set we have using the in-manner API.  And the goal is to obtain extra attribute which does not exist in the DBLP API.  And we repeat the process.  And now we can add the number of citations to our result data table.  So finally for the experiment part, firstly we want to understand how our algorithm performs.  So we did a simulation experiment on the DBLP data set.  For this experiment, we sampled 10,000 citation records from the whole data set.  And we treated the whole data set as the hidden database which has more than 5 million of  records and we fixed the query budget as 2,000.  So in this result figure, you can see the green line is the SMACRA and the orange line  is the Naive crowd.  And the SMACRA is able to cover 4.5 times records compared with the Naive crowd.  And we also tested our algorithm using the reward data set.  So we sampled 3,000 of records from a restaurant data set and we issue queries against the  YOP.com in an exhaustive way.  And we want to understand how the algorithm will perform in the end instead of using a  fixed budget.  But if you see this figure, the SMACRA algorithm can quickly cover a large amount of records  compared with the Naive crowd which almost increased linearly.  So if we fix the query budget as 900, the SMACRA can almost cover 2 times of records  than the Naive crowd.  And if you look at the end of the line, the SMACRA actually covers more records than the  Naive crowd which means SMACRA is more robust to the data errors.  So finally for the takeaways.  So in this work, we are motivated by the needs of data enrichment and we are the first to  study this problem by leveraging the deep web.  And we developed an end system to reduce the energy time from hours to minutes.  And we demonstrate that SMACRA covers up to 4 times more records than the baselines.  Thank you and I'm happy to take questions.
Wang_Shea_Wang_Wu_0_155.png Wang_Shea_Wang_Wu_156_587.png Wang_Shea_Wang_Wu_588_2375.png Wang_Shea_Wang_Wu_2376_3359.png Wang_Shea_Wang_Wu_3360_3491.png Wang_Shea_Wang_Wu_3492_4043.png Wang_Shea_Wang_Wu_4044_5507.png Wang_Shea_Wang_Wu_5508_6371.png Wang_Shea_Wang_Wu_6372_7715.png Wang_Shea_Wang_Wu_7716_8963.png Wang_Shea_Wang_Wu_8964_9599.png Wang_Shea_Wang_Wu_9600_10091.png Wang_Shea_Wang_Wu_10092_10703.png Wang_Shea_Wang_Wu_10704_12035.png Wang_Shea_Wang_Wu_12036_16067.png Wang_Shea_Wang_Wu_16068_17675.png Wang_Shea_Wang_Wu_17676_19547.png Wang_Shea_Wang_Wu_19548_19655.png Wang_Shea_Wang_Wu_19656_20471.png Wang_Shea_Wang_Wu_20472_21083.png Wang_Shea_Wang_Wu_21084_21467.png Wang_Shea_Wang_Wu_21468_22511.png Wang_Shea_Wang_Wu_22512_22979.png Wang_Shea_Wang_Wu_22980_23387.png Wang_Shea_Wang_Wu_23388_23447.png Wang_Shea_Wang_Wu_23448_26171.png Wang_Shea_Wang_Wu_26172_26915.png Wang_Shea_Wang_Wu_26916_27034.png