[發(fā)明專利]時間屬性優(yōu)先的時空軌跡數(shù)據(jù)文件在輔助存儲設備中的存儲方法

有效

• 申請?zhí)枺?/td>: 201710609573.8
• 申請日: 2017-07-25
• 公開（公告）號: CN107451233B
• 公開（公告）日: 2020-02-18
• 發(fā)明（設計）人: 吉根林;何浩奇;趙斌
• 申請（專利權）人: 南京師范大學
• 主分類號: G06F16/13
• 分類號: G06F16/13;G06F16/9537
• 代理公司: 南京蘇高專利商標事務所(普通合伙) 32204
• 代理人: 唐紅

本發(fā)明公開一種時間屬性優(yōu)先的時空軌跡數(shù)據(jù)文件在輔助存儲設備中的存儲方法，依據(jù)時間屬性對軌跡的點數(shù)據(jù)進行重新組織，同一時刻的點數(shù)據(jù)集中存儲，即：將移動對象同一時刻所有的點數(shù)據(jù)構成的結構稱之為“幀”，然后按照時刻將軌跡組織成幀數(shù)據(jù)文件，一幀對應于一個時刻，每一幀包含該時刻所有軌跡的點數(shù)據(jù)，同一幀數(shù)據(jù)在存儲設備中鄰近存儲；對存儲后的幀數(shù)據(jù)文件進行相關操作，包括新文件的初始化、軌跡添加、順序讀取和時間查詢。本發(fā)明根據(jù)用戶對于時空軌跡數(shù)據(jù)訪問時間屬性的特點針對性地設計了數(shù)據(jù)文件的格式，該存儲方法具有無數(shù)據(jù)缺失和易于實現(xiàn)的特點，適用于軌跡數(shù)據(jù)的存儲管理和數(shù)據(jù)分析與挖掘領域。

技術領域

本發(fā)明涉及一種時空數(shù)據(jù)存儲方法，具體涉及一種時間屬性優(yōu)先的時空軌跡數(shù)據(jù)文件在輔助存儲設備中的存儲方法。

背景技術

近年來，隨著全球定位技術和網絡通信技術的發(fā)展和成熟，移動終端產生的時空軌跡數(shù)據(jù)的規(guī)模越來越大。在綜合考慮存儲設備的技術性能與價格成本之后，通常軌跡數(shù)據(jù)采用輔助存儲設備(如磁盤)進行存儲。但是，軌跡數(shù)據(jù)的挖掘算法常常在執(zhí)行過程中引發(fā)大量的隨機I/O操作，這成為了影響算法性能提升的重要因素。本文通過研究時空軌跡數(shù)據(jù)在輔助存儲設備中的存儲方法，減少隨機I/O操作次數(shù)，縮短執(zhí)行時間，有效提升挖掘算法的執(zhí)行性能。

關于軌跡數(shù)據(jù)的存儲方案，工業(yè)界普遍采用成熟的數(shù)據(jù)庫技術。例如，甲骨文公司的Oracle Spatial產品基于對象-關系模式存儲和管理空間數(shù)據(jù)，其中的SDO_GEOMETRY對象類型可以用來存儲軌跡數(shù)據(jù)。又如，微軟公司的SQL Server同樣提供了對空間數(shù)據(jù)的支持功能。開源數(shù)據(jù)庫PostgreSQL的擴展插件PostGIS提供的空間數(shù)據(jù)類型也可以構造出Trajectory數(shù)據(jù)類型。上述軟件產品大多采用基于關系數(shù)據(jù)庫擴展出的空間數(shù)據(jù)庫來存儲軌跡數(shù)據(jù)。雖然此類解決方案提供了成熟的空間數(shù)據(jù)類型和空間訪問接口，使用方便。但是，軌跡數(shù)據(jù)本質上不是結構化數(shù)據(jù)，并不完全適合關系數(shù)據(jù)庫。因而，這樣的存儲方法無法針對軌跡的時空特性提供高效率的訪問方法，從而影響數(shù)據(jù)訪問的性能。

學術界針對此問題也展開了相關研究。Mediano M^[1]等人提出采用軌跡形式表示二維空間長矢量，在經過分段處理后按照原始順序依次存儲。實際操作時僅需讀取所需片段，避免非必要數(shù)據(jù)的讀取，提升了數(shù)據(jù)訪問效率。Chakka V^[2]等人也采用了基于軌跡段的存儲方法，但其存儲方法采用在線算法實現(xiàn)?；舅枷胧菍⑻砑拥能壽E分段處理后按照空間關系進行組織，將鄰近的軌跡段歸為一組，同組軌跡段在磁盤上連續(xù)存放，這樣的存儲方法可以有效提升鄰近空間軌跡的磁盤訪問效率。通常時空數(shù)據(jù)在空間分布上具有偏斜的特性，Botea V^[3]等人基于此觀察采用空間四象限劃分的方法將歷史時空點數(shù)據(jù)分組到不同大小的空間網格中，每個網格存儲的數(shù)據(jù)規(guī)模大致相同，并且相鄰時空點數(shù)據(jù)在磁盤上鄰近存儲。另一個相近的研究工作是Mauroux P提出的TrajStore^[4],它也研究軌跡數(shù)據(jù)的存儲問題，不同之處是TrajStore的存儲方法支持數(shù)據(jù)壓縮和新軌跡的添加功能。Wang HZ^[5]等人研究了內存中軌跡數(shù)據(jù)的組織方法。按照時間順序以“幀”為單位進行分組，并且采用壓縮和Cache優(yōu)化的技術提升數(shù)據(jù)訪問性能。由于該存儲方法是針對內存設備而設計的，因此無法直接移植到磁盤設備上。

軌跡數(shù)據(jù)存儲方法對軌跡數(shù)據(jù)挖掘算法的性能影響很大?，F(xiàn)有的軌跡數(shù)據(jù)挖掘包含軌跡模式挖掘、軌跡聚類、軌跡分類和時空圖挖掘等研究內容。其中不同的挖掘算法訪問軌跡數(shù)據(jù)的方式各不相同，因而在存儲設備上軌跡數(shù)據(jù)按照軌跡訪問方式進行存儲與組織最有利于算法性能的發(fā)揮。例如，軌跡伴隨模式算法的核心操作是對每個時刻的點數(shù)據(jù)集進行聚類運算。打破原始軌跡的點數(shù)據(jù)組織方式，按照時間屬性對點數(shù)據(jù)進行重新分組，顯然這種方法更優(yōu)。由此可見，軌跡數(shù)據(jù)存儲方法的設計應該充分考慮數(shù)據(jù)訪問的方式。

發(fā)明內容