Search for: All records

Similarity search is a fundamental algorithmic primitive, widely used in many computer science disciplines. Given a set of points S and a radius parameter r > 0, the r -near neighbor ( r -NN) problem asks for a data structure that, given any 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 individual fairness and providing equal opportunities: all points that are within distance r from the query should have the same probability to be returned. The problem is of special interest in high dimensions, where Locality Sensitive Hashing (LSH), the theoretically leading approach to similarity search, does not provide any fairness guarantee. In this work, we show that LSH-based algorithms can be made fair, without a significant loss in efficiency. We propose several efficient data structures for the exact and approximate variants of the fair NN problem. Our approach works more generally for sampling uniformly from a sub-collection of sets of a given collection and can be used in a few other applications. We also carried out an experimental evaluation that highlights the inherent unfairness of existing NN data structures. 

The Central Italy earthquake sequence nominally began on 24 August 2016 with a M6.1 event on a normal fault that produced devastating effects in the town of Amatrice and several nearby villages and hamlets. A major international response was undertaken to record the effects of this disaster, including surface faulting, ground motions, landslides, and damage patterns to structures. This work targeted the development of high-value case histories useful to future research. Subsequent events in October 2016 exacerbated the damage in previously affected areas and caused damage to new areas in the north, particularly the relatively large town of Norcia. Additional reconnaissance after a M6.5 event on 30 October 2016 documented and mapped several large landslide features and increased damage states for structures in villages and hamlets throughout the region. This paper provides an overview of the reconnaissance activities undertaken to document and map these and other effects, and highlights valuable lessons learned regarding faulting and ground motions, engineering effects, and emergency response to this disaster.