Library

X
feed icon rss

Your email was sent successfully. Check your inbox.

An error occurred while sending the email. Please try again.

Proceed reservation?

Export
  • 1
    Electronic Resource
    Electronic Resource
    Improved bounds for the expected behaviour of AVL trees (1992)
    Springer
    BIT 32 (1992), S. 297-315 
    Details
    ISSN: 1572-9125
    Keywords: E.1 ; F.2.2 ; G.2.1
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract In this paper we improve previous bounds on expected measures of AVL trees by using fringe analysis. A new way of handling larger tree collections that are not closed is presented. An inherent difficulty posed by the transformations necessary to keep the AVL tree balanced makes its analysis difficult when using fringe analysis methods. We derive a technique to cope with this difficulty obtaining the exact solution for fringe parameters even when unknown probabilities are involved. We show that the probability of a rotation in an insertion is between 0.37 and 0.73 (and seems to be less than 0.56), that the fraction of balanced nodes is between 0.56 and 0.78, and that the expected number of comparisons in a search seems to be at most 12% more than in the complete balanced tree.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01994883
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    A trivial algorithm whose analysis is not: A continuation (1989)
    Springer
    BIT 29 (1989), S. 378-394 
    Details
    ISSN: 1572-9125
    Keywords: F.2.2 ; Binary search trees ; deletion algorithms
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract This work analyzes insertion/deletion cycles in binary search trees with three and four elements, extending previous results of Jonassen and Knuth. We compare the symmetric and asymmetric deletion algorithms, and the results show that the symmetric algorithm works better, for trees with four elements, in accordance with many empirical measures.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02219226
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    Electronic Resource
    Electronic Resource
    Adding Compression to Block Addressing Inverted Indexes (2000)
    Springer
    Information retrieval 3 (2000), S. 49-77 
    Details
    ISSN: 1573-7659
    Keywords: text compression ; inverted files ; block addressing ; text databases
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract Inverted index compression, block addressing and sequential search on compressed text are three techniques that have been separately developed for efficient, low-overhead text retrieval. Modern text compression techniques can reduce the text to less than 30% of its size and allow searching it directly and faster than the uncompressed text. Inverted index compression obtains significant reduction of its original size at the same processing speed. Block addressing makes the inverted lists point to text blocks instead of exact positions and pay the reduction in space with some sequential text scanning. In this work we combine the three ideas in a single scheme. We present a compressed inverted file that indexes compressed text and uses block addressing. We consider different techniques to compress the index and study their performance with respect to the block size. We compare the index against three separate techniques for varying block sizes, showing that our index is superior to each isolated approach. For instance, with just 4% of extra space overhead the index has to scan less than 12% of the text for exact searches and about 20% allowing one error in the matches.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1023/A:1009934302807
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 4
    Electronic Resource
    Electronic Resource
    On efficient entreeings (1993)
    Springer
    Acta informatica 30 (1993), S. 203-213 
    Details
    ISSN: 1432-0525
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract A data encoding is a formal model of how a logical data structure is mapped into or represented in a physical storage structure. Both structures are complete trees in this paper, and we encode the logical or guest tree in the leaves of the physical or host tree giving a restricted class of encodings called entreeings. The cost of an entreeing is the total amount that the edges of the guest tree are stretched or dilated when they are replaced by shortest paths in the host tree. We are particularly interested in the asymptotic average cost of families of similar entreeings. Our investigation is a continuation of the study initiated by Rosenberg et al. In particular, the paper contains the following results. 1. We refute a conjecture of Rosenberg et al. that a particular family of entreeings of binary guests into binary hosts is optimal. 2. We provide an efficient family of entreeings fork-ary guests intok-ary hosts, fork≧2. 3. We provide an efficient family of entreeings ofk-ary guests into binary hosts, fork≧3. 4. We provide a new simple lower-bound technique that can be applied to the entreeings in part 2 to prove that they are very close to optimal. Moreover, it can be adapted for the entreeings of part 3, in which case we are able to show near optimality whenk is sufficiently large.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01179370
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 5
    Electronic Resource
    Electronic Resource
    Modeling splits in file structures (1989)
    Springer
    Acta informatica 26 (1989), S. 349-362 
    Details
    ISSN: 1432-0525
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Summary We analyze the expected behaviour of file structures where splits are used to handle overflows. Two cases are analyzed. The first model is of a file with an index on top of the data structure. We analyze the effect of unbalanced splits, and the effect of splitting in more than two buckets. The second model is of an ideal hash file, in which the probability of insertion remains the same for every bucket, regardless of how many times the bucket has been split. The result is an upper bound in any dynamic hashing method that uses splitting and does not allow overflow records. In both cases, the effect of using partial expansions is included.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00276022
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 6
    Electronic Resource
    Electronic Resource
    Expected behaviour of B+-trees under random insertions (1989)
    Springer
    Acta informatica 26 (1989), S. 439-471 
    Details
    ISSN: 1432-0525
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Summary Fringe analysis is used to study the behaviour of B+-trees (B-trees where all the records are stored in the leaves) under random insertions. We obtain bounds for the expected memory utilization and the expected number of accesses to secondary memory per insertion of trees built using the usual insertion algorithm, the B* overflow handling technique, and other techniques derived from the latter. Several other performance measures are also derived, such as bounds for the number of index nodes, the expected height, the expected number of splits per insertion, and the probabilities of 0, 1 and 2 or more splits per insertion. Special emphasis is placed on 2–3 trees. A technique for concurrency in B+-trees is also analyzed.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00289146
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 7
    Electronic Resource
    Electronic Resource
    Unbalanced multiway trees improved by partial expansions (1992)
    Springer
    Acta informatica 29 (1992), S. 443-460 
    Details
    ISSN: 1432-0525
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract Unbalanced multiway trees are generally impractical external data structures because of their poor space performance. In order to avoid this handicap, we have adapted the technique of partial expansions to these trees. Compared to partially expandedB +-trees in terms of average performance, the method proposed is faster, has more compact indexes, and shows the same almostoptimal asymptotic space performance at the data bucket level.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01193577
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 8
    Book
    Book
    Modern information retrieval (1999)
    New York; Addison-Wesley, Harlow, Engl. u.a. :ACM Pr.,
    Details
    Title: Modern information retrieval
    Author: Baeza-Yates, Ricardo
    Contributer: Ribeiro-Neto, Berthier
    Publisher: New York; Addison-Wesley, Harlow, Engl. u.a. :ACM Pr.,
    Year of publication: 1999
    Pages: 513 S.
    Type of Medium: Book
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    ZIB Catalog
    Zuse Institute Berlin get availability status
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...