Dynamic Data: Model, Sorting, Selection
Andrew Moreland · 2014
This paper is intended as an introduction to and explanation of Sorting and Selection on Dynamic Data[1], a paper published by Anagnostopoulos et al. in an attempt to address the problems that the authors encountered at Bix, a crowd-polling site that was operated by Yahoo in the mid-to-late 2000s. One of the unique issues that Bix faced was the problem of sorting a dataset that did not have an explicit total ordering, and which changed over time. In contrast to the classic problem of sorting integers, it is hard to compare the popularity of arbitrary reallife objects. So, Anagnostopoulos et al. extracted the essential features of the data they were working with into the “Dynamic Data Model” and then designed sorting and order-selection algorithms for this model. In particular, they present sorting algorithms which are able to achieve expected O(n log(n)) and O(n log log(n)) error-bounds on dynamic data.