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.

Other than the (K, L) metric, other metrics have been proposed that use inversions, which measure the number of pairs in incorrect order, runs, which measure the number of contiguous increasing subsequences in the collection, and exchanges, which measures the least number of swaps to bring the data back in order. Each of these has flaws that make them unsuitable for use in a sortedness benchmark for indexing.