[發明專利]一種面向同構對稱發布及訂閱系統的Top-k查詢方法

有效

• 申請號: 201210544907.5
• 申請日: 2012-12-17
• 公開（公告）號: CN103020234A
• 公開（公告）日: 2013-04-03
• 發明（設計）人: 王波濤;王國仁;馬素華;劉蘋蘋
• 申請（專利權）人: 東北大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 暫無信息
• 代理人: 暫無信息

技術領域

本發明屬于數據庫管理技術領域，尤其涉及一種面向同構對稱發布及訂閱系統的Top-k查詢方法。

背景技術

在同構對稱發布/訂閱(HSPub/Sub)應用中，匹配除了包括一對一交換以外，還包括發生在兩個以上的訂閱之間通過傳遞關系形成的環匹配。對發布訂閱系統來說，可以成功交換的物品數目越多，系統和用戶的收益更大。同兩兩匹配相比，環匹配可以實現讓更多的用戶參與，增大成功交換的概率。在大型的HSPub/Sub中，候選匹配極有可能是海量的，用戶需要從海量候選匹配中選擇出一些用戶偏好的匹配。

發布/訂閱系統是一種使分布式系統中的各個參與者，以發布/訂閱的方式進行交互式通信的中間件系統。在發布/訂閱系統中，信息的生產者和消費者所交互的信息稱為事件。生產者將事件發送到發布/訂閱系統的中間件系統；消費者則向發布/訂閱系統的中間件系統發出一個訂閱條件，來表示消費者對系統中感興趣的事件，如果不再感興趣，可以取消訂閱；而發布/訂閱系統的中間件系統則支持將生產者發布的事件及時、可靠地傳送給所有對之感興趣的消費者。信息的生產者稱為發布者(Publisher)，信息的消費者稱為訂閱者(Subscriber)，發布者和訂閱者都稱作客戶端。匹配算法或過濾算法負責高效地找到與給定的事件相匹配的所有的訂閱；而路由算法則負責選擇一條適當的路徑，將一個事件從發布者傳送給訂閱者。

隨著數據采集技術的提高和網絡的迅猛發展，HsPub/Sub返回給用戶的數據量越來越大甚至是海量的。如何從海量數據中篩選出滿足用戶查詢條件的數據成為數據管理和信息檢索的重點研究和探索對象。為避免最終返回海量查詢結果，在大數據量的查詢應用Top-k查詢處理勢在必行。

如果一個數據對象有多個屬性，系統在數據對象存儲時依據屬性對象排序而且生成不同的屬性列，在查詢時，系統要把列表聚合起來以獲取到數據對象全部屬性分值并且排序完成。將分散在多個列表中的分值聚合形成全局分值并且查詢出全局分值最優的k個對象的過程，就是Top-k查詢過程。

Skyline查詢問題也是一種傳統的多目標優化問題。一個多維數據集的Skyline指的是該數據集上不被其它數據點所支配的點所組成的集合。Skyline查詢返回一組在任意維度上都不被其它對象所控制的對象，支持用戶在復雜的情況下進行決策，如多標準決策支持系統、用戶偏好查詢等。

2006年，Chee-Yong?Chan等人提出基于Skyline?Frequency的Top-kSkyline查詢，只是查詢一個點在不同子空間中成為Skyline點的次數，Top-k返回Skyline最頻繁的k個點。為了計算出有點表性的Skyline點，Chee-YongChan等人提出了Distance-based?Representative?Skyline概念，很好地把與周圍其他的Skyline點的距離考慮進來，也證明了這問題也是NP難問題。

2007年Xuemin?Lin等人提出了Representative?Skyline概念，并且證明在維數不低于3的空間中，Representative?Skyline查詢是NP難問題。同時還提出了兩種算法，分別是Greedy和FM-based。這兩種算法都是從數據點集合中返回k個數據點，這k個數據點是控制非Skyline點點數量最大的k個點，也被認為是最具有代表性的Skyline點。Representative?Skyline在實踐中有時候不具有代表性，尤其是數據分布有明顯的塊聚集性，這時返回的Skyline點就不能很好的代表每個塊中全部點的信息。

實踐證明，數據集中的對象越多，Skyline結果數據量也會相應增多，尤其是在高維數據環境下，這種情況的話對用戶的決策支持中意義不大。本發明提出將Top-k引入到Skyline查詢中，利用引入的評價準則，只返回最優的k個Skyline點給用戶，來簡化用戶的篩選過程。

隨著互聯網絡技術發展，同構對稱發布/訂閱系統的應用也越來越普及。由于在同構對稱發布/訂閱系統中，產生的候選環匹配結果集很大，特別是在大型的HSPub/Sub中，訂閱的數量更大的話，候選匹配可能是海量的。大的數據量阻礙了用戶對它的有效利用，顯然如果僅僅是人為的去篩選用戶偏好的數據，是相當低效而且不現實的。如何快速、高效的為用戶推薦k個最優的候選環匹配是同構對稱發布/訂閱系統中研究的關鍵問題之一。在同構對稱發布/訂閱系統的不同應用中，有時匹配結果可以調用打分函數為其打分，依據分值排序求出前k個最優的。有時無法調用打分函數打分，不能對其排序，無法求出k個最優的。