Background Information

Background Information

Data Sortedness

In database systems, indexes are crucial for accelerating data access by adding structure to unstructured data, which enhances query performance. Traditional indexing techniques are optimized for two extremes: fully sorted data and completely unsorted (random) data. However, real-world datasets often fall between these extremes, exhibiting partial or near-sortedness. Examples include time-series data, stock market records, and datasets resulting from prior query operations or sorting based on correlated attributes.

(K,L)-Sortedness Metric

To effectively measure and generate datasets with varying degrees of sortedness, BoDS employs the (K,L)-sortedness metric. In this context:

• K represents the number of elements that are out of order.
• L denotes the maximum displacement of an out-of-order element from its ideal sorted position.

By adjusting K and L, users can create datasets ranging from fully sorted to completely unsorted, allowing for comprehensive benchmarking across different sortedness levels.