[發明專利]基于自適應數據集劃分方式的大數據Top-k查詢方法

有效

• 申請號: 201711305053.4
• 申請日: 2017-12-11
• 公開（公告）號: CN108304449B
• 公開（公告）日: 2022-02-15
• 發明（設計）人: 徐維祥;趙博
• 申請（專利權）人: 北京交通大學
• 主分類號: G06F16/903
• 分類號: G06F16/903
• 代理公司: 北京正理專利代理有限公司 11257
• 代理人: 付生輝;段俊峰

本發明公開一種基于自適應數據集劃分方式的大數據Top?k查詢方法，包括以下步驟：對系統進行初始化操作，構建超平面簇及數據集；對數據集進行自適應劃分，獲得穩定的k?切割點；對所述數據集進行Top?k排序查詢；自適應調整系統數據集并建立常用數據集。本發明中提供一種基于自適應數據集劃分方式的大數據Top?k查詢方法，該方法適用于云環境下的大數據Top?k查詢，通過對數據集進行自適應劃分，降低了查詢的數據量，提高了查詢速度，并對系統的數據集進行自適應調整，建立常用數據集，能夠進一步減少數據集讀取次數，提高查詢效率。

技術領域

本發明涉及Top-k查詢方法。更具體地，涉及一種基于自適應數據集劃分方式的大數據Top-k查詢方法。

背景技術

隨著數據量的增大，分布式Top-k查詢越來越受到關注。分布式Top-k(前k項)查詢是由中心計算節點通過匯聚分布在不同地理位置的數據列表，計算出全局匯聚值最大的前k個對象及匯聚值。其中數據列表的每一項都是一個數據對對象，對象值，數據對中的對象和對象值都包含有數據提供方的敏感信息。分布式Top-k查詢計算在網絡和系統監控、信息采集、傳感器網絡、P2P系統以及數據流控制系統等技術領域都有廣泛的應。

從數據劃分的方式來看，分布式環境下的Top-k問題可以歸納為垂直劃分和水平劃分兩大類。所謂的垂直劃分是數據按屬性進行劃分，類似于關系數據庫的列存儲方式，早期的分布式Top-k查詢研究多使用這種劃分方式。圍繞著Top-k查詢問題，近些年來開展了很多有益的研究工作。但是關系數據庫以及傳統的分布式環境都很難有效應對大數據環境下的Top-k查詢，主要原因在于數據對象及處理方法產生了很大的變化

目前，大數據環境主要涉及到云環境，云環境下數據劃分的基本原則是：盡可能地將數據均勻地劃分到各個服務器上。這種均勻不僅體現在數據量的均勻上，更重要的是面對特定應用時，這種劃分能夠盡可能地保證每個服務器上的數據對最后結果均有貢獻。進一步地，在Top-k領域具有代表性的水平劃分方式有如下幾種：隨機劃分、基于網格、基于角度和基于超平面。云環境下的大數據Top-k查詢面臨著新的挑戰。Top-k問題在MapReduce框架下有很直接的解決方案，即利用MapReduce進行數據排序再返回前k個值。這種方案既符合MapReduce批處理的特點，也容易實現，但其最大的缺點就是處理時間過長。每次到來一個新的查詢，就要對全部數據進行一次處理，數據量巨大和查詢頻繁時該方法均不可取。

因此，需要提供一種基于自適應數據集劃分方式的大數據Top-k查詢方法。

發明內容

本發明的目的在于提供一種基于自適應數據集劃分方式的大數據Top-k查詢方法。

為達到上述目的，本發明采用下述技術方案：

一種基于自適應數據集劃分方式的大數據Top-k查詢方法，包括以下步驟：

S1：對系統進行初始化操作，構建超平面簇及數據集；

S2：對數據集進行自適應劃分，獲得穩定的k-切割點；

S3：對所述數據集進行Top-k排序查詢；

S4：自適應調整系統數據集并建立常用數據集。

優選地，步驟S1包括：

S101：設用戶查詢請求中第j個元素分配的請求權重值為p_j，各p_j組合成的列向量為P，且

S102：設第j維屬性變量為y_j，各y_j組合成的列向量為Y，且

Y^T＝[y₁,y₂,y₃,…]；