Batched Predecessor and Sorting with Size-Priced Information in External Memory
Batched Predecessor and Sorting with Size-Priced Information in External Memory
复制标题
批处理前驱和外部存储器中按大小定价的信息排序
DOI：
10.1007/978-3-030-61792-9_13
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Tsichlas, Kostas
中科院分区：
文献类型：
--
作者：
Bender, Michael A;Goswami, Mayank;Medjedovic, Dzejla;Montes, Pablo;Tsichlas, Kostas
排序和搜索的基本问题，传统上在单位成本比较模型中研究，已被推广到包括价格信息，其中不同的项目对具有不同的比较成本。这些费用可以是任意的(Charikar等人。STOEC 2000)，结构化(Gupta等人Focs 2001)，或随机(Angelov等人)。拉丁语(2008)。受比较代价依赖于记录大小的数据库环境的启发，我们考虑了排序和分批前身问题，其中两个非均匀的项集A和B被作为输入。在RAM模型中，成对比较(A-A、A-Band和B-B)具有各自的比较代价a、b。我们给出了情形的上界和下界，为推广到外部记忆模型做了一个预热。在磁盘访问模型(DAM)中，元素在磁盘和RAM之间的传输是主要瓶颈，我们考虑了BAR中的元素大于ANA中的元素的情况。所有项目都需要完整地在RAM中进行比较。一个关键的观察是，排序的复杂性取决于最终排序顺序中小项和大项的交错，并且在交错程度较高的情况下，下界由关联的分批前置问题主导。我们给出了批处理的前导函数和排序的输出敏感界限；在大多数情况下，我们的界限很紧。我们的下限要求在外部存储器中对下限技术进行新的概括，以适应非统一密钥。
The fundamental problems of sorting and searching, traditionally studied in the unit-cost comparison model, have been generalized to include priced information, where different pairs of items have different comparison costs. These costs can be arbitrary (Charikar et al. STOC 2000), structured (Gupta et al. FOCS 2001), or stochastic (Angelov et al. LATIN 2008). Motivated by the database setting where the comparison cost depends on the sizes of the records, we consider the problems of sorting and batched predecessor where two non-uniform sets of itemsAandBare given as input. In the RAM model, pairwise comparisons (A-A,A-BandB-B) have respective comparison costsa,bandc. We give upper and lower bounds for the case, which serves as a warmup for the generalization to the external-memory model. In the Disk-Access Model (DAM), where transferring elements between disk and RAM is the main bottleneck, we consider the scenario where elements inBare larger than elements inA. All items are required in their entirety for comparisons in RAM. A key observation is that the complexity of sorting depends on the interleaving of the small and large items in the final sorted order, and with a high degree of interleaving, the lower bound is dominated by an associated batched predecessor problem. We give output-sensitive bounds on the batched predecessor and sorting; our bounds are tight in most cases. Our lower bounds require novel generalizations of lower bound techniques in external memory to accommodate non-uniform keys.
登录
查看更多内容
维护字典：B 树的节省空间的修改
DOI：
--
发表时间：
1992
期刊：
International Conference on Database Theory
影响因子：
--
作者：
A. 0. Pinchuk;K. Shvachko
通讯作者：
K. Shvachko
具有可变长度记录的 B* 树的分页
DOI：
--
发表时间：
1977
期刊：
CACM
影响因子：
--
作者：
E. McCreight
通讯作者：
E. McCreight
基于比较的算法的 I/O 复杂度的一般下界
DOI：
--
发表时间：
1992
期刊：
Workshop on Algorithms and Data Structures
影响因子：
--
作者：
L. Arge;Mikael B. Knudsen;Kirsten Larsen
通讯作者：
Kirsten Larsen
DOI：
--
发表时间：
2005
期刊：
影响因子：
--
作者：
Amr Elmasry
通讯作者：
Amr Elmasry
高效的最佳卷轴分页
DOI：
--
发表时间：
1985
期刊：
CACM
影响因子：
--
作者：
L. Larmore;D. Hirschberg
通讯作者：
D. Hirschberg