We lifted 7 functions out of this paper's own repositories and ran 6 of them in a sandbox. "Ran" means the function executed on a synthesized input and returned a value. It is not a reproduction of the paper's results.
| Repository | Role | Ran |
|---|---|---|
| alfahaf/fair-near-neighbor-search | canonical | 6 of 7 |
| Function | Status | Where it lives |
|---|---|---|
| avg_set_size | Ran | alfahaf/fair-near-neighbor-search/src/dataset_reader.py code served (permissive licence) · get_code("e54efe3e7829f75d") |
| compute_recall | Ran | alfahaf/fair-near-neighbor-search/src/helpers.py code served (permissive licence) · get_code("e47a2eb123973f49") |
| del_weights | Ran | alfahaf/fair-near-neighbor-search/src/dataset_reader.py code served (permissive licence) · get_code("f6116f04374906cb") |
| get_max_ID | Ran | alfahaf/fair-near-neighbor-search/src/dataset_reader.py code served (permissive licence) · get_code("f93f2d796de67eb7") |
| jaccard | Ran | alfahaf/fair-near-neighbor-search/src/helpers.py code served (permissive licence) · get_code("d2e7a454839ef1f4") |
| to_set | Ran | alfahaf/fair-near-neighbor-search/src/get_groundtruth.py code served (permissive licence) · get_code("353aef875d1569e9") |
| compute_ball_ratio | Not yet run | alfahaf/fair-near-neighbor-search/src/experiment_minhash.py code served (permissive licence) · get_code("034aed5d6d986deb") |
Some links come from the archived Papers with Code dataset (CC BY-SA 4.0): attribution and licence.
Similarity search is a fundamental algorithmic primitive, widely used in many computer science disciplines. There are several variants of the similarity search problem, and one of the most relevant is the $r$-near neighbor ($r$-NN) problem: given a radius $r>0$ and a set of points $S$, construct a data structure that, for any given query point $q$, returns a point $p$ within distance at most $r$ from $q$. In this paper, we study the $r$-NN problem in the light of fairness. We consider fairness in the sense of equal opportunity: all points that are within distance $r$ from the query should have the same probability to be returned. In the low-dimensional case, this problem was first studied by Hu, Qiao, and Tao (PODS 2014). Locality sensitive hashing (LSH), the theoretically strongest approach to similarity search in high dimensions, does not provide such a fairness guarantee. To address this, we propose efficient data structures for $r$-NN where all points in $S$ that are near $q$ have the same probability to be selected and returned by the query. Specifically, we first propose a black-box approach that, given any LSH scheme, constructs a data structure for uniformly sampling points in the neighborhood of a query. Then, we develop a data structure for fair similarity search under inner product that requires nearly-linear space and exploits locality sensitive filters. The paper concludes with an experimental evaluation that highlights (un)fairness in a recommendation setting on real-world datasets and discusses the inherent unfairness introduced by solving other variants of the problem.
The same record, over MCP at https://syntology.ai/mcp:
get_harvested_code_for_paper("1906.01859")
get_code_for_paper("1906.01859")
have("1906.01859")
Connect an agent — have() is free.