Efficient currency determination algorithms for dynamic data

Xiaoou Ding, Hongzhi Wang, Yitong Gao, Jianzhong Li, Hong GaoTsinghua 2017 · DOI

Abstract

Data quality is a critical dimension in data management, with currency—the up-to-dateness of information—being a primary factor. In real-world applications, timestamps are often missing, inconsistent, or absent, making it difficult to determine which records are most current. This paper proposes a series of efficient algorithms for determining data currency in dynamic datasets by leveraging semantic rules instead of clock times. By introducing specialized indexing structures—the Entity Query B-Tree (EQB-Tree) and Entity Storage Dynamic Linked List (ES-DLL)—the proposed system achieves constant-time updates (under 14ms) regardless of dataset size, ensuring high-velocity data remains fresh and accurate.

Introduction

In modern data management, "stale" information represents a significant economic burden. Traditionally, data currency relies on timestamps to identify the most recent record for an entity. However, in integrated systems, timestamps are frequently missing or unreliable. For instance, a database might contain multiple conflicting records for a single individual, as shown in the sample dataset below.

Sample dataset showing multiple records for entities Alice and Tom with varying attributes.

Without reliable temporal markers, determining whether "Alice" is currently a student or a programmer becomes a complex logical challenge. Existing rule-based methods can resolve these conflicts but often struggle with the high velocity of incoming "big data," where re-calculating the entire dataset's currency for every new update is computationally prohibitive.

The Proposed Framework

To address these challenges, we propose a two-phase framework designed for both accuracy and speed. The system decouples the initial setup from the real-time update process, allowing it to scale effectively.

Overview of the two-phase framework: Preprocessing and Dynamic Determination.

1. Offline Preprocessing

The preprocessing phase prepares the system for rapid querying and updating:

  • Attribute Processing Order: A topological graph is constructed to determine the evaluation sequence of attributes based on their logical dependencies (e.g., a change in "Degree" often precedes a change in "Position").
  • Indexing Structures: We introduce the Entity Query B-Tree (EQB-Tree) to facilitate rapid entity lookups ($O(\log n)$). Complementing this is the Entity Storage Dynamic Linked List (ES-DLL), which maintains tuples in their determined currency order. This structure allows new data to be inserted into the correct temporal position with minimal overhead.

2. Online Dynamic Determination

When a new data tuple arrives, the system performs the following steps in real-time:

  • Entity Localization: The EQB-Tree identifies the existing records for the entity.
  • Rule Application: Semantic constraints (e.g., "Status moves from Single to Married") are applied to update a local Currency Graph.
  • Score Calculation: A numerical Currency Score is computed, providing a granular measure of how "fresh" the new tuple is relative to the entity's history.
  • List Update: The new tuple is inserted into its logical position within the ES-DLL.

Experimental Results

The framework was evaluated using both real-life student records and large-scale synthetic datasets (up to 500,000 tuples).

Key findings include:

  • Constant-Time Performance: The time required to process a new update remained stable at approximately 12–14 milliseconds, independent of the total number of entities in the database.
  • Scalability: Preprocessing time scales linearly with the number of entities and attributes, confirming the system's suitability for industrial-scale applications.
  • Rule Complexity: The system maintained high performance even when subjected to complex rule sets (up to 140 rules), demonstrating that the topological sorting of attributes effectively eliminates redundant computations.

Conclusion

By shifting the focus from physical timestamps to semantic logic and optimized data structures, this research provides a robust solution for maintaining data currency in high-velocity environments. While the system currently relies on expert-defined rules, future work will explore automated rule discovery and more advanced conflict resolution strategies to further enhance the autonomy of data quality management.

Summary updated

Abstract

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.
BibTeX
@inproceedings{ding2017efficient,
  author = {Xiaoou Ding and Hongzhi Wang and Yitong Gao and Jianzhong Li and Hong Gao},
  title = {{Efficient currency determination algorithms for dynamic data}},
  booktitle = {Tsinghua},
  year = {2017},
  doi = {10.23919/tst.2017.7914196},
}
Figure