Deterministic skip lists for k-dimensional range search
| dc.contributor.author | Lamoureux, Michael, G. | |
| dc.contributor.author | Nickerson, Bradford, G. | |
| dc.date.accessioned | 2023-03-01T18:28:17Z | |
| dc.date.available | 2023-03-01T18:28:17Z | |
| dc.date.issued | 1995 | |
| dc.description.abstract | 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 | |
| dc.description.copyright | Copyright @ Michael G. Lamoureux and Bradford G. Nickerson, 1995. | |
| dc.identifier.uri | https://unbscholar.lib.unb.ca/handle/1882/14832 | |
| dc.rights | http://purl.org/coar/access_right/c_abf2 | |
| dc.subject.discipline | Computer Science | |
| dc.title | Deterministic skip lists for k-dimensional range search | |
| dc.type | technical report |
Files
Original bundle
1 - 1 of 1