Efficient support for multi-attribute top-k relational queries: a cost-based approach

高效支持多属性top-k关系查询：基于成本的方法

• 批准号: 328087-2006
• 负责人: Ayanso, Anteneh
• 金额: $ 0.95万
• 依托单位: Brock University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2008
• 资助国家: 加拿大
• 起止时间: 2008-01-01 至 2009-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=397997
• 关键词: Efficient; support; multi; attribute; top

Querying for "approximate matches" is very common in document and multimedia retrieval systems.  In search engines, for example, users specify a set of keywords and expect in return a ranking of relevant pages or documents related to the keywords.  In contrast, the querying methods available in relational database management systems (RDBMSs) are designed to return only results found within specified selection conditions.  Due to this, users of online business applications such as product recommendation systems, price comparison and shopping agents routinely face the challenge of specifying value ranges of attributes in search of relevant results.  Often, they get either too few or too many results that are of limited relevance to their request.  This conventional querying process is very frustrating for the user and extremely inefficient for the system.          Alternatively, users of the above applications should be able to specify target values of attributes and expect to obtain a ranked set of a desired number of results that best match the specified values across all the attributes (e.g., the top 10 best matches).  In this type of querying, also known as top-k querying, results are not limited to exact matches but include close matches around the target values of interest.  This research studies cost-based strategies for efficient support of this class of queries in RDBMSs.  The objective is to provide methods that work within the technical constraints of the existing design of RDBMSs but avoid a full sequential scan of the database to obtain the top-k set.  In particular, the proposed research introduces techniques that systematically incorporate the relevant performance cost factors and their underlying trade-offs for efficient top-k retrieval.  The methodology encompasses analytical modelling and extensive computational and experimental analyses using real and synthetic data sets over a wide range of experimental settings.

查询“近似匹配”在文档和多媒体检索系统中非常常见。例如，在搜索引擎中，用户指定一组关键字，并期望返回与关键字相关的相关页面或文档的排名。相反，关系数据库管理系统（RDBMS）中可用的查询方法被设计为仅返回在指定选择条件内找到的结果。由于这一点，例如产品推荐系统、价格比较和购物代理的在线商业应用的用户通常面临在搜索相关结果时指定属性的值范围的挑战。通常，他们得到的结果太少或太多，这些结果与他们的请求的相关性有限。这种传统的查询过程对于用户来说非常令人沮丧，并且对于系统来说效率极低。 或者，上述应用的用户应当能够指定属性的目标值，并且期望获得跨所有属性最佳匹配指定值的期望数量的结果的经排名的集合（例如，前10个最佳匹配）。在这种类型的查询中，也称为前k查询，结果不限于精确匹配，但包括围绕感兴趣的目标值的密切匹配。这项研究的成本-的策略，以有效地支持这类查询的关系数据库管理系统。其目标是提供的方法，工作在现有的关系数据库管理系统设计的技术限制，但避免全面顺序扫描的数据库，以获得的top-k集。特别是，拟议的研究引入技术，系统地将相关的性能成本因素和他们的基本权衡有效的top-k retrieval. The方法包括分析建模和广泛的计算和实验分析，使用真实的和合成数据集在广泛的实验设置。