[發明專利]一種眾包TOP-k查詢中的降低成本方法

有效

• 申請號: 201811097218.8
• 申請日: 2018-09-19
• 公開（公告）號: CN109254983B
• 公開（公告）日: 2021-07-13
• 發明（設計）人: 崔宗敏;高宇;喻靜
• 申請（專利權）人: 九江學院
• 主分類號: G06F16/2458
• 分類號: G06F16/2458
• 代理公司: 南昌新天下專利商標代理有限公司 36115
• 代理人: 謝德珍

一種眾包TOP?k查詢中的降低成本方法，該方法包括以下步驟：首先將問題分成若干個小任務，通過眾包平臺發布給用戶進行評分，得到用戶判斷的偏好；再根據所獲得偏好包對項目進行選擇分區排序；最后得到最終的top?k結果。該方法減少了比較工作量，從而達到降低成本的目的。

技術領域

本發明涉及一種眾包TOP-k查詢中的降低成本方法。

背景技術

近期，眾包被用于多種數據庫查詢，包括最大值查詢、連接查詢和Top-k查詢。在本文中，主要收集眾包Top-k查詢。其中，人們對項目集的排序結果產生決定性作用。Top-k查詢已經應用于很多方面如，在線翻譯,藥品不良反映評估，排行榜等等。

眾包Top-k查詢對計算機不擅長，但是人們可以給出更好的回答的事情。這些大多都需要一定的知識或者自然感情來判別。這些都是計算機無法給出判斷但對擁有響應能力的人們來說是一件極其簡單的事情。它主要分為兩大部分內容，首先通過眾包平臺將若干小任務分發給用戶，用戶根據任務作出判斷并反饋；其次再通過本文發明方法對反饋答案進行排序得出Top-k。

現有幾種方法被用于判斷，比較簡單的方法是，讓用戶對所有項進行判斷，然后通過收集判斷進行排名，最后返回最好的k個項目的排序。這個方法需要復雜的用戶界面，并且從用戶的角度講不是十分便利。另一種方法是，讓用戶對所有項進行分級，然后和平均等級相比，返回最好的k項。然而，分級判斷規模不同，眾包只會讓結果更加難以獲得，分級判斷則很難校準(每個用戶的分數公平化)。所以，近期的眾包top-k查詢處理主要被用于兩兩判斷，兩兩偏好判斷只需比較兩項之間的偏好值，可以降低人為誤差。這些方法都存在一定問題使得比較工作量大，成本更高。因此一種可以降低成本的方法的出現是很有意義的。

發明內容

本發明其目的就在于提供一種眾包TOP-k查詢中的降低成本方法，解決了現有技術方法存在使得比較工作量大，成本更高的問題。

為實現上述目的而采取的技術方案是，一種眾包TOP-k查詢中的降低成本方法，該方法包括以下步驟：

(1)首先將問題分成若干個小任務，通過眾包平臺發布給用戶進行評分，得到用戶判斷的偏好：將問題分成若干個小任務，通過眾包平臺發布給用戶進行評分，每個項目采用分級判斷評分規則，即每個用戶給每個項目打分，分值必須在一個評分區間V(G^*_i,G^*_j)∈[-1,1]，分值代表了該用戶在這兩項中判斷的偏好；顯然，假如每個用戶給出的評分機制不同，那所得評分相差太大，得出的結果是不符合實際的，其絕對值表明其偏愛程度，對G^*_i,G^*_j所有的比較完成后，產生了W_i,j的工作量，相應產生一個偏好值包V_i,j＝{V₁(G_i,G_j),……，V_Wi,j(G_i,G_j)；

(2)再根據所獲得偏好包對項目進行選擇分區排序：選擇分區排序的步驟為：(a)在所有候選項中選擇出一個參考項r：在項目候選集中進行隨機抽取m組樣本，選擇每一組中的最大值，再在這m個最大值中選擇中值作為參考項r；(b)候選項基于r項做比較，將所有候選項分區；(c)將最后的分區根據k值進行排序；

(3)最后得到最終的top-k結果。

所述的步驟(2)中，在選擇了參考項r之后，利用選擇分區排序算法，將所有候選項依次和r比較，得到的結果將分成三組：優于r的Wr，和r相近的Lr，比r差的Tr；其中和r相近的是，由于比較值幾乎相等，導致無法確定排名，這樣的項成為相近，假設不考慮相近問題，且每兩組項都可以在預計的工作量中完成比較，得出結果；在選擇了一個恰當的r之后，r仍然可以修剪無結果的項。

有益效果