This page shows all publications that appeared in the IASI annual research reports. Authors currently affiliated with the Institute are always listed with the full name.

You can browse through them using either the links of the following line or those associated with author names.

Show all publications of the year  1997, with author Gaibisso C., in the category IASI Research Reports (or show them all):

---

IASI Research Report n. 456  (Previous    Next) 


Carlo Gaibisso, Guido Proietti

Efficient insertion of approximately sorted sequences of items into a dictionary

ABSTRACT

In this paper we propose a new data structure for the classical dictionary problem, supporting efficient on-line inserting of a sequence S of keys by taking advantage of ordering relationships existing among the sorted subsequences in which S can be decomposed. More precisely, we will show that any sorted subsequences S_k of k keys contained in S can be inserted into the dictionary in O(p log n + (n - p)), where n is the size of the dictionary and p is the number of fragments in which S_k breaks up when inserted into the dictionary (where a fragment is a set of adjacent keys of S_k which maintain their adjancency into the dictionary). Some applications, as specified in the paper, specifically require for this property.