Efficient Currency Determination Algorithms for Dynamic Data

• 来源期刊: 清华大学学报自然科学版（英文版）
• 年，卷（期）: 2017,（3）
• 页码范围: 227-242
• 页数: 16页
• 语种: 英文

摘要

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.