Communications of the ACM
Technical Perspective: Can Data Structures Treat Us Fairly?
Credit: Getty Images
When asked to pick a random buddy from our Facebook friends list, we may struggle since our nomination is likely to be biased toward individuals with whom we interact more frequently. Computer assistance in such a case would make things easier: we can just store our friends' names in an array. Whenever a query comes, the computer generates a random array index and returns the name stored in the corresponding location. The question now is whether, for any given data structure problem, we can build a data structure that generates "fair" output while maintaining query efficiency.
In the context of data structure query-answering, fairness can be defined as follows: we either return all valid answers or just return a uniformly random one. Although this definition does not capture all human expectations of fairness, it is the most natural one for data structures from a technical sense. The challenge is that returning all valid answers may be time prohibitive, while returning a uniformly random one in a timely manner could also be difficult due to specific data storage orders and query-answering procedures. Consider the problem of finding red nodes in a binary tree with half of the nodes colored red and the other half blue. We can certainly use our favorite tree traversal algorithms, such as breadth-first search, to find all red nodes in the tree, but doing so will take time proportional to the size of the tree. We can also take random root-leaf paths to find one red node; this approach is much more time-efficient, but it favors red nodes closer to the root, resulting in an output that is not uniformly random.
No entries found