59 citations · 213 across the 21 of their papers we have counts for
20 papers · 1 filter
How many users have been here for a long time? Efficient solutions for counting long aggregated visits
Peyman Afshani, Rezaul Chowdhury, Inge Li Gørtz +3
This paper addresses the Counting Long Aggregated Visits problem, which is defined as follows. We are given users and regions, where each user spends some time visiting som…
Dimensionality Reduction on Complex Vector Spaces for Euclidean Distance with Dynamic Weights
Simone Moretti, Paolo Pellizzoni, Francesco Silvestri
The weighted Euclidean norm of a vector with weights is the Euclidean norm where the contribution of each dimension is scaled by a…
On the Bike Spreading Problem
Elia Costa, Francesco Silvestri
A free-floating bike-sharing system (FFBSS) is a dockless rental system where an individual can borrow a bike and returns it anywhere, within the service area. To improve the renta…
Sampling a Near Neighbor in High Dimensions -- Who is the Fairest of Them All?
Martin Aumüller, Sariel Har-Peled, Sepideh Mahabadi +2
Similarity search is a fundamental algorithmic primitive, widely used in many computer science disciplines. Given a set of points and a radius parameter , the -near nei…
Similarity Search with Tensor Core Units
Thomas D. Ahle, Francesco Silvestri
Tensor Core Units (TCUs) are hardware accelerators developed for deep neural networks, which efficiently support the multiplication of two dense matrices,…
A Computational Model for Tensor Core Units
Rezaul Chowdhury, Francesco Silvestri, Flavio Vella
To respond to the need of efficient training and inference of deep neural networks, a plethora of domain-specific hardware architectures have been introduced, such as Google Tensor…
Fair Near Neighbor Search: Independent Range Sampling in High Dimensions
Martin Aumüller, Rasmus Pagh, Francesco Silvestri
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…
Adaptive MapReduce Similarity Joins
Samuel McCauley, Francesco Silvestri
Similarity joins are a fundamental database operation. Given data sets S and R, the goal of a similarity join is to find all points x in S and y in R with distance at most r. Recen…
Distance-Sensitive hashing
Martin Aumüller, Tobias Christiani, Rasmus Pagh +1
Locality-sensitive hashing (LSH) is an important tool for managing high-dimensional noisy or uncertain data, for example in connection with data cleaning (similarity join) and nois…
Approximate Furthest Neighbor with Application to Annulus Query
Rasmus Pagh, Francesco Silvestri, Johan Sivertsen +1
Much recent work has been devoted to approximate nearest neighbor queries. Motivated by applications in recommender systems, we consider approximate furthest neighbor (AFN) queries…
Distance Sensitive Bloom Filters Without False Negatives
Mayank Goswami, Rasmus Pagh, Francesco Silvestri +1
A Bloom filter is a widely used data-structure for representing a set and answering queries of the form "Is in ?". By allowing some false positive answers (saying "yes"…
On the Complexity of Inner Product Similarity Join
Thomas D. Ahle, Rasmus Pagh, Ilya Razenshteyn +1
A number of tasks in classification, information retrieval, recommendation systems, and record linkage reduce to the core problem of inner product similarity join (IPS join): ident…
I/O-Efficient Similarity Join
Rasmus Pagh, Ninh Pham, Francesco Silvestri +1
We present an I/O-efficient algorithm for computing similarity joins based on locality-sensitive hashing (LSH). In contrast to the filtering methods commonly suggested our method h…
Network-Oblivious Algorithms
Gianfranco Bilardi, Andrea Pietracaprina, Geppino Pucci +2
A framework is proposed for the design and analysis of \emph{network-oblivious algorithms}, namely, algorithms that can run unchanged, yet efficiently, on a variety of machines cha…
Subgraph Enumeration in Massive Graphs
Francesco Silvestri
We consider the problem of enumerating all instances of a given pattern graph in a large data graph. Our focus is on determining the input/output (I/O) complexity of this problem.…
The Input/Output Complexity of Triangle Enumeration
Rasmus Pagh, Francesco Silvestri
We consider the well-known problem of enumerating all triangles of an undirected graph. Our focus is on determining the input/output (I/O) complexity of this problem. Let be th…
Communication Lower Bounds for Distributed-Memory Computations
Michele Scquizzato, Francesco Silvestri
We give lower bounds on the communication complexity required to solve several computational problems in a distributed-memory parallel machine, namely standard matrix multiplicatio…
Space-Efficient Parallel Algorithms for Combinatorial Search Problems
Andrea Pietracaprina, Geppino Pucci, Francesco Silvestri +1
We present space-efficient parallel strategies for two fundamental combinatorial search problems, namely, backtrack search and branch-and-bound, both involving the visit of an -…
Exploiting non-constant safe memory in resilient algorithms and data structures
Lorenzo De Stefani, Francesco Silvestri
We extend the Faulty RAM model by Finocchi and Italiano (2008) by adding a safe memory of arbitrary size , and we then derive tradeoffs between the performance of resilient algo…
Space-Round Tradeoffs for MapReduce Computations
Andrea Pietracaprina, Geppino Pucci, Matteo Riondato +2
This work explores fundamental modeling and algorithmic issues arising in the well-established MapReduce framework. First, we formally specify a computational model for MapReduce w…