Computer Science – Information Retrieval
Scientific paper
2011-08-12
Computer Science
Information Retrieval
Scientific paper
Web search engines and specialized online verticals are increasingly incorporating results from structured data sources to answer semantically rich user queries. For example, the query \WebQuery{Samsung 50 inch led tv} can be answered using information from a table of television data. However, the users are not domain experts and quite often enter values that do not match precisely the underlying data. Samsung makes 46- or 55- inch led tvs, but not 50-inch ones. So a literal execution of the above mentioned query will return zero results. For optimal user experience, a search engine would prefer to return at least a minimum number of results as close to the original query as possible. Furthermore, due to typical fast retrieval speeds in web-search, a search engine query execution is time-bound. In this paper, we address these challenges by proposing algorithms that rewrite the user query in a principled manner, surfacing at least the required number of results while satisfying the low-latency constraint. We formalize these requirements and introduce a general formulation of the problem. We show that under a natural formulation, the problem is NP-Hard to solve optimally, and present approximation algorithms that produce good rewrites. We empirically validate our algorithms on large-scale data obtained from a commercial search engine's shopping vertical.
Gollapudi Sreenivas
Ieong Samuel
Ntoulas Alexandros
Paparizos Stelios
No associations
LandOfFree
Efficient Query Rewrite for Structured Web Queries does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Efficient Query Rewrite for Structured Web Queries, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient Query Rewrite for Structured Web Queries will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-16850