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.
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.
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