摘要:大數據時代的到來給傳統的數據查詢帶來了性能挑戰,即使查詢算法有著O(n)的線性復雜度,但當n極大時其時間開銷也難以滿足用戶需求。在很多實際應用中,人們并不需要精確的查詢結果,但要求在給定時間內完成查詢,因此可適當犧牲查詢精度以滿足性能約束。采樣查詢通過約簡查詢范圍來提高查詢性能,現有的采樣方法多針對特定的算法和特定的應用場景,缺乏大數據環境下一般性的采樣查詢方法以及保證性能和精度的研究。文中研究大數據環境下列存儲的采樣查詢處理,從數據劃分和數據采樣兩方面改進大數據的查詢效率。提出了基于加速比和勢分布的采樣方法,其支持各類采樣算法,實現了分布式環境下采樣查詢的隨機性保證、性能保證和近似性評價,并兼容了精確查詢。該方法可以快速應用到已有大量數據的列存儲中,具備良好的擴展性和可維護性。以Top-K為查詢用例的實驗結果證明,在不同數據量、不同數據分布和不同采樣算法下,實際采樣率與給定采樣率的誤差低于2%,查詢準確度(Accuracy)穩定,方差在0.10和0.12之間,因此提出的基于段勢的數據劃分的采樣效率高于平均劃分和線性劃分。
注:因版權方要求,不能公開全文,如需全文,請咨詢雜志社。
計算機科學雜志, 月刊,本刊重視學術導向,堅持科學性、學術性、先進性、創新性,刊載內容涉及的欄目:網絡與通信、信息安全、軟件與數據庫技術、人工智能、圖形圖像與模式識別等。于1974年經新聞總署批準的正規刊物。