41 citations · 157 across the 29 of their papers we have counts for
11 papers · 1 filter
Fast Prefix Search in Little Space, with Applications
Djamal Belazzougui, Paolo Boldi, Rasmus Pagh +1
It has been shown in the indexing literature that there is an essential difference between prefix/range searches on the one hand, and predecessor/rank searches on the other hand, i…
Local Ranking Problem on the BrowseGraph
Michele Trevisiol, Luca Maria Aiello, Paolo Boldi +1
The "Local Ranking Problem" (LRP) is related to the computation of a centrality-like rank on a local graph, where the scores of the nodes could significantly differ from the ones c…
Entity-Linking via Graph-Distance Minimization
Roi Blanco, Paolo Boldi, Andrea Marino
Entity-linking is a natural-language-processing task that consists in identifying the entities mentioned in a piece of text, linking each to an appropriate item in some knowledge b…
Cache-Oblivious Peeling of Random Hypergraphs
Djamal Belazzougui, Paolo Boldi, Giuseppe Ottaviano +2
The computation of a peeling order in a randomly generated hypergraph is the most time-consuming step in a number of constructions, such as perfect hashing schemes, random -SAT…
In-Core Computation of Geometric Centralities with HyperBall: A Hundred Billion Nodes and Beyond
Paolo Boldi, Sebastiano Vigna
Given a social network, which of its nodes are more central? This question has been asked many times in sociology, psychology and computer science, and a whole plethora of centrali…
Predecessor search with distance-sensitive query time
Djamal Belazzougui, Paolo Boldi, Sebastiano Vigna
A predecessor (successor) search finds the largest element smaller than the input string (the smallest element larger than or equal to , respectively) out of a g…
E = I + T: The internal extent formula for compacted tries
Paolo Boldi, Sebastiano Vigna
It is well known that in a binary tree the external path length minus the internal path length is exactly 2n-2, where n is the number of external nodes. We show that a generalizati…
HyperANF: Approximating the Neighbourhood Function of Very Large Graphs on a Budget
Paolo Boldi, Marco Rosa, Sebastiano Vigna
The neighbourhood function N(t) of a graph G gives, for each t, the number of pairs of nodes <x, y> such that y is reachable from x in less that t hops. The neighbourhood function…
Layered Label Propagation: A MultiResolution Coordinate-Free Ordering for Compressing Social Networks
Paolo Boldi, Marco Rosa, Massimo Santini +1
We continue the line of research on graph compression started with WebGraph, but we move our focus to the compression of social networks in a proper sense (e.g., LiveJournal): the…
Efficient Optimally Lazy Algorithms for Minimal-Interval Semantics
Sebastiano Vigna, Paolo Boldi
Minimal-interval semantics associates with each query over a document a set of intervals, called witnesses, that are incomparable with respect to inclusion (i.e., they form an anti…
Compact Approximation of Lattice Functions with Applications to Large-Alphabet Text Search
Paolo Boldi, Sebastiano Vigna
We propose a very simple randomised data structure that stores an approximation from above of a lattice-valued function. Computing the function value requires a constant number of…