New Data Structures for Orthogonal Queries

摘要

The application of pyramid-like data structures to multidimensional queries has been explored in three recent papers. This report shows that many of the earlier results (including some of our own) can be improved by a factor of log N with a slightly modified data structure that enables k-dimensional searches to be performed in O(log N) to the k-1 power) time. The new revised pyramid structure can be made sufficiently efficient in a dynamic environment to have an O(log N) to the k-1 power) record-insertion and deletion runtime. Queries for the special two-dimensional version of the proposed pyramid will have the same combination of O(log N) retrieval, insertion and deletion runtimes that has traditionally been associated with one-dimensional sorted lists. Our k-dimensional pyramid data structure will occupy O(N(log N) to the K-1 power) space. The coefficient associated with its memory space utilization will only be approximately 50 percent larger than that of the otherwise considerably less efficient pyramids in previous papers. Also, it is shown how the combination of the concepts of this paper long with other cited concepts can be used to develop very useful partial match data structures.