Lamoureux, Michael, G.Nickerson, Bradford, G.2023-03-012023-03-011995https://unbscholar.lib.unb.ca/handle/1882/14832This 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 complexityhttp://purl.org/coar/access_right/c_abf2technical reportComputer Science