Gianni Franceschini

STOC Conference 2007 Conference Paper

Optimal suffix selection

• Gianni Franceschini
• S. Muthukrishnan 0001

Given a string S[1·s n], the suffix selection problemis to find the k th lexicographically smallest amongst the n suffixes S[i·s n], for i=1,...,n. In particular, the fundamental question is if selection can be performed more efficiently than sorting all the suffixes. If one considered n numbers, they can be sorted using Θ(n log n) comparisonsand the classical result from 70's is that selection can be done using O(n) comparisons. Thus selection is provably more efficient than sorting, for n numbers. Suffix sorting can be done using Θ(n log n) comparisons, but does suffix selection need suffix sorting? We settle this fundamental problem by presenting an optimal, deterministic algorithm for suffix selection using O(n) comparisons.

SODA Conference 2006 Conference Paper

Implicit dictionaries with O (1) modifications per update and fast search

• Gianni Franceschini
• J. Ian Munro

FOCS Conference 2004 Conference Paper

No Sorting? Better Searching!

• Gianni Franceschini
• Roberto Grossi

Sorting is commonly meant as the task of arranging keys in increasing or decreasing order (or small variations of this order). Given n keys underlying a total order, the best organization in an array is maintaining them in sorted order. Searching requires /spl Theta/ (log n) comparisons in the worst case, which is optimal. We demonstrate that this basic fact in data structures does not hold for the general case of multidimensional keys, whose comparison cost is proportional to their length. In two papers by Andersson et al. (1994) and Andersson et al. (1995) and the full version in 2001, Andersson et al. study the complexity of searching a sorted array of n keys, each of length k, arranged in lexicographic (or alphabetic) order for an arbitrary, possibly unbounded, ordered alphabet. They give sophisticated arguments for proving a tight bound in the worst case for this basic data organization, up to a constant factor, obtaining /spl Theta/(((k log log n)/(log log (4 + ((k log log n)/log n)))) + k log n) character comparisons (or probes). Note that the bound is /spl Theta/ (log n) when k = 1, which is the case that is well known in algorithmics. We describe a permutation of the n keys that is different from the sorted order, and sorting is just the starting point for describing our preprocessing. When keys are stored according to this "unsorted" order in the array, the complexity of searching drops to /spl Theta/ (k + log n) character comparisons (or probes) in the worst case, which is optimal among all possible permutations of the n keys in the array, up to a constant factor. Again, the bound is /spl Theta/ (log n) when k = 1. Jointly with the aforementioned result of Anders son et al. , our finding provably shows that keeping k-dimensional keys sorted in an array is not the best data organization for searching. This fact was not observable before by just considering k = O(1) as sorting is an optimal organization in this case. More implications of our result are commented in the introduction.

SODA Conference 2004 Conference Paper

Proximity Mergesort: optimal in-place sorting in the cache-oblivious model

• Gianni Franceschini

FOCS Conference 2003 Conference Paper

An In-Place Sorting with O(n log n) Comparisons and O(n) Moves

• Gianni Franceschini
• Viliam Geffert

We present the first in-place algorithm for sorting an array of size n that performs, in the worst case, at most O(n log n) element comparisons and O(n) element transports. This solves a long-standing open problem, stated explicitly, e. g. , in J. I. Munro and V. Raman (1992), of whether there exists a sorting algorithm that matches the asymptotic lower bounds on all computational resources simultaneously.

SODA Conference 2003 Conference Paper

Implicit dictionaries supporting searches and amortized updates in O(log n log log n) time

• Gianni Franceschini
• Roberto Grossi

FOCS Conference 2002 Conference Paper

Implicit B-Trees: New Results for the Dictionary Problem

• Gianni Franceschini
• Roberto Grossi
• J. Ian Munro
• Linda Pagli

We reopen the issue of finding an implicit data structure for the dictionary problem. In particular, we examine the problem of maintaining n data values in the first n locations of an array in such a way that we can efficiently perform the operations insert, delete and search. No information other than n and the data is to be retained; and the only operations which we may perform on the data values (other than reads and writes) are comparisons. Our structure supports these operations in O(log/sup 2/ n/log log n) time, marking the first improvement on the problem since the mid 1980's. En route we develop a number of space efficient techniques for handling segments of a large array in a memory hierarchy. We achieve a cost of O(log/sub B/ n) block transfers like in regular B-trees, under the realistic assumption that a block stores B = /spl Omega/(log n) keys, so that reporting r consecutive keys in sorted order has a cost of O(log/sub B/n+r/B) block transfers. Being implicit, our B-tree occupies exactly [n/B] blocks after each update.