Applications of the Dynamic N-Dimensional K-Vector

Abstract

The n-dimensional k-vector (NDKV) is an appealing alternative to binary tress for resolving complex queries in large relational databases. The method has excelled in several applications involving static databases. The present paper extends the theory supporting the NDKV to handle dynamic databases, where the data is updated frequently. This includes deleting records, adding new entries, or editing existing elements. The merit of this new version of the NDKV, the dynamic n-dimensional k-vector (DNDKV), is that it is no longer necessary to recompute the entire k-vector (the main structure that indexes the data) every time a record changes. The algorithm updates the four constituents of the standard NDKV on the fly: the database, sorted database, index, and k-vector tables. As a result, the DNDKV becomes comparable in terms of capabilities and flexibility to stateof-the-art storage engines relying on structured query languages (SQL). The performance of the DNDKV is assessed by running typical read/write operations on a database that contains millions of pre-computed missions to celestial bodies. This database requires frequent updates whenever an orbit solution is refined or new bodies are discovered. The DNDKV is faster than rebuilding the k-vector tables completely, provided that the number of elements being added or removed is not excessively large. Direct runtime comparisons with MySQL suggest that the DNDKV is several times faster for reading but might be slower for writing and updating the database. One limit of the technique is the elements being added must be within the range of the current k-vector tables. If this is not the case, the technique cannot be used and the k-vector tables must be rebuilt from scratch.