[發(fā)明專利]大數(shù)據(jù)的非精準(zhǔn)排序方法

在審

• 申請?zhí)枺?/td>: 201810192740.8
• 申請日: 2018-03-09
• 公開（公告）號: CN108416025A
• 公開（公告）日: 2018-08-17
• 發(fā)明（設(shè)計）人: 李凌瑤;張業(yè)嶺;蔣可安;張菁菁;王寧駿;胡天然
• 申請（專利權(quán)）人: 王寧駿;張菁菁;胡天然;張業(yè)嶺;蔣可安;李凌瑤
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 上海驍象知識產(chǎn)權(quán)代理有限公司 31315
• 代理人: 林煒

一種大數(shù)據(jù)的非精準(zhǔn)排序方法，涉及數(shù)據(jù)處理技術(shù)領(lǐng)域，所解決的是海量數(shù)據(jù)檢索的技術(shù)問題。該方法從目標(biāo)數(shù)據(jù)庫中隨機截取一段數(shù)據(jù)樣本，再根據(jù)樣本構(gòu)建樣本值數(shù)組、樣本頻數(shù)數(shù)組，利用樣本值數(shù)組存放樣本的參考數(shù)值，利用樣本頻數(shù)數(shù)組記錄各個參考數(shù)值的出現(xiàn)頻率；并對樣本值數(shù)組及樣本頻數(shù)數(shù)組進(jìn)行優(yōu)化；然后再構(gòu)建一個累計值數(shù)組，并根據(jù)樣本頻數(shù)數(shù)組為累計值數(shù)組賦值；然后利用樣本值數(shù)組檢測待排序的目標(biāo)數(shù)據(jù)在目標(biāo)數(shù)據(jù)庫中的排列位置，根據(jù)累計值數(shù)組中的對應(yīng)元素，計算目標(biāo)數(shù)據(jù)在目標(biāo)數(shù)據(jù)庫中的排序百分比值，從而得出目標(biāo)數(shù)據(jù)在目標(biāo)數(shù)據(jù)庫中的排序位置。本發(fā)明提供的方法，適用于不需要精確查詢排序結(jié)果的場景。

技術(shù)領(lǐng)域

本發(fā)明涉及數(shù)據(jù)處理的技術(shù)，特別是涉及一種大數(shù)據(jù)的非精準(zhǔn)排序方法的技術(shù)。

背景技術(shù)

在某些場合中，對海量數(shù)據(jù)進(jìn)行排序并不需要很精準(zhǔn)的排序結(jié)果(比如，查詢一個數(shù)據(jù)在海量數(shù)據(jù)中的大致位置)，以較小的代價實現(xiàn)非精準(zhǔn)的排序可以快速得到查詢結(jié)果。

但是，常規(guī)的數(shù)值排序方法都是嚴(yán)格的比較數(shù)值大小，按照一定順序排列，采用常規(guī)的數(shù)值排序方法對海量數(shù)據(jù)進(jìn)行排序需要開辟較大的緩存和較多的計算時間，花費的代價是巨大的，需要大量硬件投資來保證查詢結(jié)果的實現(xiàn)。

發(fā)明內(nèi)容

針對上述現(xiàn)有技術(shù)中存在的缺陷，本發(fā)明所要解決的技術(shù)問題是提供一種計算時間短，且硬件投資成本低的大數(shù)據(jù)的非精準(zhǔn)排序方法。

為了解決上述技術(shù)問題，本發(fā)明所提供的一種大數(shù)據(jù)的非精準(zhǔn)排序方法，其特征在于，具體步驟如下：

1)從目標(biāo)數(shù)據(jù)庫中隨機截取一段包含有N個數(shù)據(jù)的數(shù)據(jù)樣本Y，并設(shè)定一個計算精度α，1E+8<N<1E+10，1E-6≤α≤1E-4；

2)令m等于1/α的整數(shù)部分；

3)構(gòu)建一個m維的樣本值數(shù)組Lv，為樣本值數(shù)組Lv中的每個元素賦值，賦值計算公式為：

Lv_(i)＝V_min+i×(V_max-V_min)/m

其中，Lv_(i)為樣本值數(shù)組Lv中的第i個元素，V_max為數(shù)據(jù)樣本Y中的數(shù)據(jù)最大值，V_min為數(shù)據(jù)樣本Y中的數(shù)據(jù)最小值，0<i≤m；；

4)構(gòu)建一個m維的樣本頻數(shù)數(shù)組Ln，為樣本頻數(shù)數(shù)組Ln中的每個元素賦值，賦值方法為：統(tǒng)計數(shù)據(jù)樣本Y中的大于Lv_(i)并且小于Lv_(i+1)的數(shù)據(jù)的數(shù)量，并將統(tǒng)計的數(shù)量值賦給Ln_(i)；

其中，Ln_(i)為樣本頻數(shù)數(shù)組Ln中的第i個元素，Lv_(i)為樣本值數(shù)組Lv中的第i個元素，Lv_(i+1)為Lv_(i)后序相鄰的元素；

5)按照規(guī)則A、規(guī)則B優(yōu)化樣本值數(shù)組Lv及樣本頻數(shù)數(shù)組Ln，直到樣本頻數(shù)數(shù)組Ln中的所有元素都不滿足規(guī)則A，并且也不滿足規(guī)則B；

規(guī)則A：對于樣本頻數(shù)數(shù)組Ln中的任意一個元素Ln_(i)，如果Ln_(i)＜η×N/m，則令令N＝N-Ln_(i)/2，令m＝m-1，并刪除樣本值數(shù)組Lv中的第i個元素Lv_(i)，并刪除樣本頻數(shù)數(shù)組Ln中的第i個元素Ln_(i)，η的取值為0.1；