Evaluating top-k queries over web-accessible databases
Evaluating top-k queries over web-accessible databases
复制标题
DOI：
10.1145/1005566.1005569
复制
发表时间：
2004-06-01
影响因子：
1.8
通讯作者：
Gravano, L
中科院分区：
文献类型：
--
作者：
Marian, A;Bruno, N;Gravano, L
对网络搜索引擎的查询通常由关键字列表组成，搜索引擎用该查询的最好或最前的k个页面来响应这些关键字。这种top-k查询模型通常适用于多媒体集合，但也适用于某些应用程序的普通关系数据。例如，考虑与可用餐厅信息的关系，包括它们的位置、一家餐厅的价格范围和总体食物评级。查询这种关系的用户可以简单地指定用户的位置和目标价格范围，并期望在与用户的接近程度、与目标价格范围的匹配度和总体食物评级的某种组合方面返回最佳的10家餐馆。高效地处理top-k查询具有挑战性，原因有很多。一个关键的原因是，在许多Web应用程序中，除了通过外部Web可访问的表单接口之外，关系属性可能不可用，我们将不得不重复查询这些接口以寻找潜在的大量候选对象。在本文中，我们研究如何在这种情况下高效地处理top-k查询，在这种情况下，用户为其指定目标值的属性可能由具有各种访问接口的外部自治源处理。我们提出了一种用于处理此类查询的顺序算法，但观察到任何顺序top-k查询处理策略都必然需要不必要的长查询处理时间，因为网络访问表现出高且可变的延迟。幸运的是，Web源可以并行探测，每个源通常可以处理并发请求，尽管源可能会对它们愿意接受的探测的类型和数量施加一些限制。我们调整了我们的顺序查询处理技术，引入了一种高效的算法，该算法最大化源访问并行度来最小化查询响应时间，同时满足源访问约束。我们使用人工和真实的Web可访问数据对我们的技术进行了实验评估，结果表明并行算法可以显著地比它们的顺序算法更高效。
A query to a web search engine usually consists of a list of keywords, to which the search engine responds with the best or "top" k pages for the query. This top-k query model is prevalent over multimedia collections in general, but also over plain relational data for certain applications. For example, consider a relation with information on available restaurants, including their location, price range for one diner, and overall food rating. A user who queries such a relation might simply specify the user's location and target price range, and expect in return the best 10 restaurants in terms of some combination of proximity to the user, closeness of match to the target price range, and overall food rating. Processing top-k queries efficiently is challenging for a number of reasons. One critical such reason is that, in many web applications, the relation attributes might not be available other than through external web-accessible form interfaces, which we will have to query repeatedly for a potentially large set of candidate objects. In this article, we study how to process top-k queries efficiently in this setting, where the attributes for which users specify target values might be handled by external, autonomous sources with a variety of access interfaces. We present a sequential algorithm for processing such queries, but observe that any sequential top-k query processing strategy is bound to require unnecessarily long query processing times, since web accesses exhibit high and variable latency. Fortunately, web sources can be probed in parallel, and each source can typically process concurrent requests, although sources may impose some restrictions on the type and number of probes that they are willing to accept. We adapt our sequential query processing technique and introduce an efficient algorithm that maximizes source-access parallelism to minimize query response time, while satisfying source-access constraints.We evaluate our techniques experimentally using both synthetic and real web-accessible data and show that parallel algorithms can be significantly more efficient than their sequential counterparts.