Browsing by Author "Lamoureux, Michael, G."

Now showing 1 - 3 of 3
  • Thumbnail Image
    Item
    An implementation of a multidimensional dynamic range tree based on an AVL tree
    (1995) Lamoureux, Michael, G.
    In this paper we develop a dynamic multidimensional range tree data structure based on the AVL tree. The range tree was originally defined as a static data structure which is optimal (O(lg[superscript k]n + t) for t points in range), in a worst case analysis, for answering k-dimensional range queries on k-dimensional data when only O(nlg[superscript k-1]n) space is used. Theoretical modifications to the structure do exist such that the structure can be used in a dynamic environment and maintain both its low range search time and storage requirements (in fact, the structure is optimally balanced), but, to the extent of the author's knowledge, a detailed specification of the structure along with a corresponding implementation does not yet exist in the literature. This paper defines the necessary transformations that are needed to transform the AVL tree into a 1-d dynamic range tree and the necessary modifications that are needed to extend this structure into a k-dimensional structure that can handle k-dimensional data. The resulting structure satisfies the specifications for a dynamic range tree and is optimally balanced. It is implemented in Pascal with complete code being provided in the appendices. This structure is important as it provides us with a baseline structure against which other structures, and their implementations, designed to handle multidimensional range queries on multidimensional data can be compared. Keywords: range tree, AVL tree, range query, multidimensional data, dynamic data structures, optimally balanced data structures
  • Thumbnail Image
    Item
    Deterministic skip lists for k-dimensional range search
    (1995) Lamoureux, Michael, G.; Nickerson, Bradford, G.
    This report presents a new data structure for multidimensional data which is based on an extension of the deterministic skip list data structure projected into k-dimensions. The data structure is labeled the k -d Range DSL and it allows for efficient multidimensional range search on point data. This structure supports fast insertions, deletions, and search and the k-d Range DSL is shown to be opthual (i.e. O(lgkn + t) to find t points in range) for k-d range search on n points in a dynamic environment with a pointer based memory model where we impose restrictions on worst-case search time, dynamic operations, and storage. The structure is extendible and it does pennit for multidimensional semi-infinite range queries in an equivalent !hue. The k-d Range DSL, by nature of the skip list structure, is well suited for range search in a parallel processing environment. Algorithms for building, insertion, deletion, and range search are provided for the data structure along with proofs of validity and worst-case complexity for these operations. Also, complete working code in (Borland's Turbo) Pascal is provided in the appendices. Keywords: dynamic data structures, algorithms, range search, orthogonal range query, multidimensional data, skip lists, searching, worst-case complexity
  • Thumbnail Image
    Item
    On the equivalence of B-trees and deterministic skip list
    (1996) Lamoureux, Michael, G.; Nickerson, Bradford, G.
    In this paper we show the functional and structural equivalence of B-trees and deterministic skip lists by defining two new B-tree structures, the Bd-tree and Bd[superscript +] -tree, which we use to provide an explicit mapping between deterministic skip lists (DSLs) and B-trees. This mapping is invertible and formalizes the correspondence that exists between the structures, allowing us to prove the equivalence of B-tree and deterministic skip list data structures. This result is important for a number of reasons. It validates the use of deterministic skip lists as index structures while allowing one to determine the relationship of deterministic skip lists to other balanced search tree structures. This equivalence provides further insight into a comparison of the 1-3 deterministic skip list to the red-black tree and to the 1-d range tree. We now know that we can interchange between the red-black tree and the 1-3 DSL and that the dynamic 1-d range tree and 1-3 DSL are equivalent structures. Keywords: B-trees, deterministic skip lists, equivalent data structures, balanced search tree structures, Bd-trees, Bd[superscript +]-trees