Geometric and Spatial Data Structures in External Memory:Conclusions

By -

Conclusions

In this chapter we have surveyed several useful paradigms and techniques for the design and implementation of efficient data structures for external memory. A variety of interesting challenges remain in geometric search applications, such as methods for high-dimensional and nonorthogonal range searches as well as the analysis of R-trees and linear-space methods for typical-case scenarios. A continuing goal is to translate theoretical gains into observable improvements in practice. For some of the problems that can be solved optimally up to a constant factor, the constant overhead is too large for the algorithm to be of practical use, and simpler approaches are needed.

Comments

Post a Comment

Popular posts from this blog

Data Structures in Web Information Retrieval:Fingerprints

By -
Image
Fingerprints Fingerprints are short strings that represent larger strings and have the following properties: • If the fingerprints of two strings are different then the strings are guaranteed to be different. • If the fingerprints of two strings are identical then there is only a small probability that the strings are different. If two different strings have the same fingerprint, it is called a c o l l i sion . Thus, fingerprints are a type of hash functions where the hash table is populated only very sparsely in exchange for a very low collision probability. Fingerprints are very useful. For example, search engines can use them to quickly check whether a URL that is contained on a web page is already stored in the index. We will describe how they are useful for finding near-duplicate documents in the next section. One fingerprinting scheme is due to Rabin [12] and is equivalent to cyclic redundancy checks. We follow here the presentation by Broder [3]. Let s be a binary string a...
Read more

Double-Ended Priority Queues:Interval Heaps.

By -
Image
Interval Heaps The twin heaps of [21], the min-max pair heaps of [17], the interval heaps of [11, 16], and the diamond deques of [5] are virtually identical data structures. In each of these structures, an n element DEPQ is represented by a min heap with I n/ 2 l elements and a max heap with the remaining l n/ 2 J elements. The two heaps satisfy the property that each element in the min heap is ≤ the corresponding element (two elements correspond if they occupy the same position in their respective binary trees) in the max heap. When the number of elements in the DEPQ is odd, the min heap has one element (i.e., element I n/ 2 l ) that has no corresponding element in the max heap. In the twin heaps of [21], this is handled as a special case and one element is kept outside of the two heaps. In min-max pair heaps, interval heaps, and diamond deques, the case when n is odd is handled by requiring element I n/ 2 l of the min heap to be ≤ element l n/ 4 J of the max heap. In the twin hea...
Read more

Double-Ended Priority Queues: Deaps.

By -
Image
Deaps The deap structure of [4] is similar to the two-heap structures of [5, 16, 17, 21]. At the conceptual level, we have a min heap and a max heap. However, the distribution of elements between the two is not I n/ 2 l and l n/ 2 J . Rather, we begin with an ( n + 1)-node complete binary tree. Its left subtree is the min heap and its right subtree is the max heap (Fig ure 8.21, max-heap nodes are shaded). The correspondence property for deaps is slightly more complex than that for the two-heap structures of [5, 16, 17, 21]. A d e a p is a complete binary tree that is either empty or satisfies the following condi tions: 1. The root is empty. 2. The left subtree is a min heap and the right subtree is a max heap. 3. Cor r es p o n de n c e property. Suppose that the right subtree is not empty. For every node x in the left subtree, define its corresponding node y in the right subtree to be the node in the same position as x . In case such a y doesn’t exist, let y be the cor...
Read more