A Lower Bound on the Complexity of Orthogonal Range Queries
A Lower Bound on the Complexity of Orthogonal Range Queries
复制标题
正交范围查询复杂度的下界
DOI：
--
复制
发表时间：
1981
期刊：
影响因子：
--
通讯作者：
M. Fredman
中科院分区：
文献类型：
--
作者：
M. Fredman
设S是任意可交换半群（在交换结合加法运算下闭的元素集）.给定一个有序键空间上的一组具有d维键向量的记录，使得每个记录都与S中的一个值相关联，正交范围查询是对与某个指定超立方体中的每个记录相关联的值之和的请求（区间的叉积）。G. Lueker和D.沃德拉德本文证明了fi（n（logn）~）是处理n个混合的插入子、删除子和范围查询序列所需的固有最坏情况时间的下界，这意味着Lueker和Wdlard数据结构在某种意义上是最优的。
Let S be an arbitrary commutaUve semigroup (set of elements closed under a commutative and associative addmon operation, +). Given a set of records wtth d-dimensional key vectors over an ordered key space, such that each record has associated with it a value in S, an orthogonal range query is a request for the sum of the values associated with each record in some specified hypercube (cross product of mtervals). Data structures which accommodate inserUons and delettons of records and orthogonal range queries, such that an arbitrary sequence of n such operations takes time O(n(log n)a), have been presented by G. Lueker and D. Wdlard. It is shown here that fi(n(logn) ~) is a lower bound on the inherent worst case time reqmred to process a sequence of n intermixed insemons, deleuons, and range queries, which imphes that the Lueker and Wdlard data structures are in some sense optimal.