Efficient Currency Determination Algorithms for Dynamic Data  

作　　者：Xiaoou Ding Hongzhi Wang Yitong Gao Jianzhong Li Hong Gao 

机构地区：[1]School of Computer Science andTechnology,Harbin Institute of Technology,Harbin 150001,China

出　　处：《Tsinghua Science and Technology》2017年第3期227-242,共16页清华大学学报（自然科学版（英文版）

基　　金：supported by the National Natural Science Foundation of China(Nos.U1509216 and 61472099);National Key Technology Research and Development Program(No.2015BAH10F01);the Scientific Research Foundation for the Returned Overseas Chinese Scholars of Heilongjiang Province(No.LC2016026);MOE-Microsoft Key Laboratory of Natural Language Processing and Speech,Harbin Institute of Technology

摘　　要：Data quality is an important aspect in data application and management, and currency is one of the major dimensions influencing its quality. In real applications, datasets timestamps are often incomplete and unavailable, or even absent. With the increasing requirements to update real-time data, existing methods can fail to adequately determine the currency of entities. In consideration of the velocity of big data, we propose a series of efficient algorithms for determining the currency of dynamic datasets, which we divide into two steps. In the preprocessing step, to better determine data currency and accelerate dataset updating, we propose the use of a topological graph of the processing order of the entity attributes. Then, we construct an Entity Query B-Tree （EQB-Tree） structure and an Entity Storage Dynamic Linked List （ES-DLL） to improve the querying and updating processes of both the data currency graph and currency scores. In the currency determination step, we propose definitions of the currency score and currency information for tuples referring to the same entity and use examples to discuss methods and algorithms for their computation. Based on our experimental results with both real and synthetic data, we verify that our methods can efficiently update data in the correct order of currency.Data quality is an important aspect in data application and management, and currency is one of the major dimensions influencing its quality. In real applications, datasets timestamps are often incomplete and unavailable, or even absent. With the increasing requirements to update real-time data, existing methods can fail to adequately determine the currency of entities. In consideration of the velocity of big data, we propose a series of efficient algorithms for determining the currency of dynamic datasets, which we divide into two steps. In the preprocessing step, to better determine data currency and accelerate dataset updating, we propose the use of a topological graph of the processing order of the entity attributes. Then, we construct an Entity Query B-Tree （EQB-Tree） structure and an Entity Storage Dynamic Linked List （ES-DLL） to improve the querying and updating processes of both the data currency graph and currency scores. In the currency determination step, we propose definitions of the currency score and currency information for tuples referring to the same entity and use examples to discuss methods and algorithms for their computation. Based on our experimental results with both real and synthetic data, we verify that our methods can efficiently update data in the correct order of currency.

关 键 词：data quality management data currency dynamic determining 

分 类 号：F270[经济管理—企业管理] TN98[经济管理—国民经济]