Evaluating Top-N queries in n-dimensional normed spaces

详细信息    查看全文

• 作者：Liang Zhu^a ; ^{zhu@hbu.edu.cn" class="auth_mail" title="E-mail the corresponding author} ; Feifei Liu^a ; ^{liufeifei9476@126.com" class="auth_mail" title="E-mail the corresponding author} ; Weiyi Meng^b ; ^{meng@cs.binghamton.edu" class="auth_mail" title="E-mail the corresponding author} ; Qin Ma^c ; ^{maqin@hbu.edu.cn" class="auth_mail" title="E-mail the corresponding author} ; Yu Wang^a ; ^{wy@hbu.edu.cn" class="auth_mail" title="E-mail the corresponding author} ; Fang Yuan^d ; ^{yuanfang@hbu.edu.cn" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Top-N query ; n-dimensional normed space ; Relational database ; Ranking function
• 刊名：Information Sciences
• 出版年：2016
• 出版时间：20 December 2016
• 年：2016
• 卷：374
• 期：Complete
• 页码：255-275
• 全文大小：1980 K

文摘

For the problem of processing top-N queries, the threshold algorithm (TA) is an important method in many scenarios. The model of top-N queries with TA has three characteristics: (1) the ranking function is monotone, (2) the query point is fixed, and (3) TA scans the sorted index lists unidirectionally. In many database applications, however, there are opportunities for evaluating top-N queries with arbitrary query points and generic (not necessarily monotone) ranking functions. In this paper, we propose an approach for evaluating top-N queries in n-dimensional normed spaces. Given a query point Q = (q₁,…, q_n) in the real vector space ℜⁿ and a generic norm distance d as ranking function, our method employs the norm equivalence theorem in Functional Analysis so that the candidate tuples of top-N query Q with d can be obtained using the Maximum distance d_∞. This method projects each q_i on its corresponding axis and constructs an interval centered at q_i, and then enlarges each interval bidirectionally until the n-dimensional hyperrectangle contains enough candidate tuples so that the top-N tuples are retrieved according to the given norm distance d. Extensive experiments are conducted to measure the performance of our approach for both low-dimensional and high-dimensional data.