ACM通信
研究突出了
技术视角:数据结构能公平对待我们吗?
来源:盖蒂图片社
当被要求从Facebook好友列表中随机挑选一个好友时，我们可能会很纠结，因为我们的提名很可能偏向于与我们互动更频繁的人。在这种情况下，计算机的辅助将使事情变得更容易:我们只需将朋友的名字存储在数组中。每当有查询时，计算机生成一个随机数组索引并返回存储在相应位置的名称。现在的问题是，对于任何给定的数据结构问题，我们是否可以构建一个在保持查询效率的同时生成“公平”输出的数据结构。
在数据结构查询应答的上下文中，公平性可以定义为:我们要么返回所有有效的答案，要么只返回一个均匀随机的答案。尽管这个定义没有包含人类对公平的所有期望，但从技术意义上来说，它是数据结构最自然的定义。挑战在于，返回所有有效答案可能会占用大量时间，而由于特定的数据存储命令和查询回答程序，及时返回统一的随机答案也很困难。考虑在二叉树中寻找红节点的问题，其中一半节点是红色的，另一半是蓝色的。我们当然可以使用我们最喜欢的树遍历算法，例如广度优先搜索，来查找树中的所有红节点，但这样做将花费与树的大小成正比的时间。我们也可以取随机的根叶路径来找到一个红节点;这种方法更节省时间，但它更倾向于靠近根的红节点，导致输出不是均匀随机的。
设计有效的数据结构一直被认为是计算机科学中最重要的问题之一，它已经被研究了几十年。然而，令人惊讶的是，设计公平数据结构的主题并没有得到太多关注。虽然在(机器学习)算法中存在一些公平的一般原则，如“对相似项目的相似处理”和“输出独立于敏感变量(例如，个人的性别、种族等)”，但由于社会技术系统的复杂性，公平的定义有时可能存在争议。幸运的是，如前所述，为数据结构问题定义公平性相对容易。然而，实现效率和公平的双重目标可能仍然具有挑战性。
在接下来的论文中，Aumüller等人研究了相似度搜索中的一个基本问题称为附近的邻居在公平数据结构的背景下。在这个问题中，给定度量空间中的一组点和距离阈值，任务是构建一个数据结构来存储这些点，以便给定任何查询点，我们可以有效地从查询点返回距离阈值内的点。相似度搜索在大数据时代变得越来越重要，在数据库、推荐系统、机器学习等众多应用中被用作构建模块。公平(或均匀随机)近邻对于增加输出的多样性和在查询点的近邻中估计一些所需的属性/统计信息特别有用。
本文研究了公平数据结构下相似性搜索的一个基本问题——近邻问题。
有效地从邻近集合中检索点的标准方法是局部敏感哈希(LSH)。在这个方法中，我们将所有输入点散列到一个桶集合中。要处理每个查询，只需搜索该查询点散列到的桶中的所有点。我们通常使用独立的哈希函数多次重复这个过程，以增加找到近邻的成功概率。不幸的是，LSH不会产生一致随机的近邻，因为它倾向于更接近查询点的点。
Aumüller等人的工作为LSH算法添加了一个公平性组件。作者通过考虑一个更通用但仍然相当基本的数据结构问题来实现这一点，在这个问题中，我们得到一组项的集合(将每个集合看作包含一组点的桶)。任务是对集合的集合进行预处理，以便对于指定集合的子集合的每个查询，我们可以从该子集合中的集合并中返回统一随机项，不包括标记的异常值集。解决这个普遍问题需要一些新的、有趣的技术想法，这些想法可能被应用到其他各种公平的数据结构问题中。这项工作为未来公平数据结构设计的研究开辟了道路，尽管公平数据结构设计具有重要意义，但目前还没有得到足够的重视。我们可以期待未来几年在这一领域有更多令人兴奋的研究。
数字图书馆是由计算机协会出版的。版权所有©2022 ACM, Inc.
没有发现记录