检索结果-内蒙古大学图书馆

indexing temporal relations for range-duration queries

DISTRIBUTED AND PARALLEL dataBASES 2025年第1期43卷 1-39页

作者： Ceccarello, Matteo Dignoes, Anton Gamper, Johann Khnaisser, Christina Univ Padua Dept Informat Engn Padua Italy Free Univ Bozen Bolzano Fac Engn Bolzano Italy Univ Sherbrooke Fac Med & Sci Sante Sherbrooke PQ Canada

Temporal information plays a crucial role in many database applications, however support for queries on such data is limited. We present an index structure, termed RD-index, to support range-duration queries over interval timestamped relations, which constrain both the range of the tuples' positions on the timeline and their duration. RD-index is a grid structure in the two-dimensional space, representing the position on the timeline and the duration of timestamps, respectively. Instead of using a regular grid, we consider the data distribution for the construction of the grid in order to ensure that each grid cell contains approximately the same number of intervals. RD-index features provable bounds on the running time of all the operations, allows for a simple implementation, supports very predictable query performance, and can be constructed and queried in parallel using multithreading. We benchmark our solution on a variety of datasets and query workloads, investigating both the query rate and the behavior of the individual queries. The results show that RD-index performs better than the baselines on range-duration queries, for which it is explicitly designed. Furthermore, it outperforms state of the art indexes also on mixed workloads containing queries that constrain either only the duration or the range along with range-duration queries. Finally, the size of the RD-index is in all settings smaller than the competitors, its construction scales with the number of threads, and parallelization helps improving the runtime of expensive moderate and lowly selective queries.

关键词： Temporal databases index data structures database queries

来源：评论

学校读者我要写书评

暂无评论

HLN-Tree: A Memory-efficient B+-Tree with Huge Leaf Nodes and Locality Predictors

引用

ACM Transactions on Storage 2025年第2期21卷 1-27页

作者： Brinkmann, André Salkhordeh, Reza Wiegert, Florian Wang, Peng Xin, Yao Chen, Renhai Keji, Huang Zhang, Gong Institute of Computer Science Johannes Gutenberg University Mainz Mainz Germany Huawei Technology Hong Kong Huawei Technologies Co Ltd Shenzhen China

Key-value stores in Cloud environments can contain more than 245 unique elements and be larger than 100 PByte. B+-Trees are well suited for these larger-than-memory datasets and seamlessly index data stored on thousands of secondary storage devices. Unfortunately, it is often uneconomical to even store all inner tree nodes in memory for these dataset sizes. Therefore, lookup performance is affected by the additional IOs for reading inner nodes. This number of inner nodes can be reduced by increasing the size of leaf nodes. We propose HLN-Trees, which support huge leaf nodes without increasing the IO sizes for individual index operations. They partition leaf nodes in arrays of independent subnodes and combine ideas from BD-trees with rebalancing, learning key deviations, and storing locality predictors. HLN-Trees have been initially designed for uniform random key distributions and support arbitrary key distributions through an additional layer of hashing in leaf nodes. HLN-Trees decrease the number of inner nodes by up to 256× for uniform random key distributions and by 16× to 64× for arbitrary ones compared to B+-Trees, while keeping their performance at the same level even at high concurrency levels. We show analytically and through real-world and synthetic benchmarks that HLN-Trees also outperform state-of-the-art learned indexes for secondary storage. © 2025 Copyright held by the owner/author(s).

关键词： SSDs index data structures learned indexes

来源：评论

学校读者我要写书评

暂无评论

Future-Based Persistent Spatial data Structure for NVM-Based Manycore Machines

引用

IEEE ACCESS 2022年 10卷 114711-114724页

作者： Salam, Abdul Jamil, Safdar Jung, Sungwon Park, Sung-Soon Kim, Youngjae Sogang Univ Dept Comp Sci & Engn Seoul 04107 South Korea Gluesys Co Ltd Anyang 951074 South Korea Anyang Univ Dept Comp Engn Anyan Si 14028 South Korea

R-trees have been popular for their support of multidimensional data and high-performing queries. FBR-tree is the state-of-the-art concurrent variant of the R-tree for Intel DC Persistent Memory (DCPM). However, its adoption on manycore servers is impeded by concurrency limitations due to lengthy, lock-based synchronization, including structure modification operations, split and merge. Additionally, emerging DCPM-based machines are equipped with multiple CPU sockets, forming a non-uniform memory access (NUMA) architecture. FBR-tree's lack of NUMA-awareness induces further performance overhead from remote memory accesses. In this paper, we propose MPR-tree, a concurrent, NUMA-aware and persistent future-based R-tree for DCPM servers. MPR-tree focuses on insert operations due to their laborious nature. MPR-tree relies on per-thread local future objects and a global R-tree. To introduce NUMAawareness and minimize remote memory accesses, MPR-tree adopts per-socket dedicated asynchronous evaluate threads to checkpoint future objects to the global R-tree. MPR-tree employs an in-memory hash table to mitigate the read overhead of key searches over the future objects. We implemented MPR-tree atop FBR-tree and evaluated its performance on a server with 40 physical cores for insert and lookup queries, and it showed that MPR-tree outperforms FBR-tree on average by 2x on log10 scale.

关键词： Futures index data structures non-volatile memory manycore machines

来源：评论

学校读者我要写书评

暂无评论

On-line construction of two-dimensional suffix trees in O(n² log n) time

引用

ALGORITHMICA 2007年第2期48卷 173-186页

作者： Na, Joong Chae Giancarlo, Raffaele Park, Kunsoo Seoul Natl Univ Sch Comp Sci & Engn Seoul 151742 South Korea Univ Palermo Dipartimento Matemat & Applicaz I-90123 Palermo Italy

The two-dimensional suffix tree of an n x n square matrix A is a compacted trie that represents all square submatrices of A [11]. For the off-line case, i.e., A is given in advance to the algorithm, it is known how to build it in optimal time, for any type of alphabet size [11], [18]. Motivated by applications in Image Compression [22], Giancarlo and Guaiana [14] considered the on-line version of the two-dimensional suffix tree and presented an 0(n(2) log(2) n)-time algorithm, which we refer to as GG. That algorithm is a nontrivial generalization of Ukkonen's on-line algorithm for standard suffix trees [23]. The main contribution in this paper is an 0(log n) factor improvement in the time complexity of the GG algorithm, making it optimal for unbounded alphabets [9]. Moreover, the ideas presented here also lead to a major simplification of the GG algorithm. Technically, we are able to preserve most of the structure of the original GG algorithm, by reducing a computational bottleneck to a primitive operation, i.e., comparison of Lcharacters, which is here implemented in constant time rather than 0 (log n) time as in GG. However, preserving that structure comes at a price. Indeed, in order to make everything work, we need a careful reorganization of another fundamental algorithm: Weiner's algorithm for the construction of standard suffix trees [24]. Specifically, here we provide a version of that algorithm which takes linear time and works on-line and concurrently over a set of strings.

关键词： two-dimensional suffix tree on-line algorithm index data structures

来源：评论

学校读者我要写书评

暂无评论

Linearized Suffix Tree: an Efficient index data Structure with the Capabilities of Suffix Trees and Suffix Arrays

引用

ALGORITHMICA 2008年第3期52卷 350-377页

作者： Kim, Dong Kyue Kim, Minhwan Park, Heejin Hanyang Univ Coll Informat & Commun Seoul 133791 South Korea Pusan Natl Univ Div Comp Engn Pusan 609735 South Korea Hanyang Univ Div Elect & Comp Engn Seoul 133791 South Korea

Suffix trees and suffix arrays are fundamental full-text index data structures to solve problems occurring in string processing. Since suffix trees and suffix arrays have different capabilities, some problems are solved more efficiently using suffix trees and others are solved more efficiently using suffix arrays. We consider efficient index data structures with the capabilities of both suffix trees and suffix arrays without requiring much space. When the size of an alphabet is small, enhanced suffix arrays are such index data structures. However, when the size of an alphabet is large, enhanced suffix arrays lose the power of suffix trees. Pattern searching in an enhanced suffix array takes O(m vertical bar Sigma vertical bar) time while pattern searching in a suffix tree takes O(m log vertical bar Sigma vertical bar) time where m is the length of a pattern and Sigma is an alphabet. In this paper, we present linearized suffix trees which are efficient index data structures with the capabilities of both suffix trees and suffix arrays even when the size of an alphabet is large. A linearized suffix tree has all the functionalities of the enhanced suffix array and supports the pattern search in O(m log vertical bar Sigma vertical bar) time. In a different point of view, it can be considered a practical implementation of the suffix tree supporting O(m log vertical bar Sigma vertical bar)-time pattern search. In addition, we also present two efficient algorithms for computing suffix links on the enhanced suffix array and the linearized suffix tree. These are the first algorithms that run in O(n) time without using the range minima query. Our experimental results show that our algorithms are faster than the previous algorithms.

关键词： Suffix trees Suffix arrays index data structures String algorithms

来源：评论

学校读者我要写书评

暂无评论

A scalable data structure for real-time estimation of resource availability in build-to-order environments

引用

JOURNAL OF INTELLIGENT MANUFACTURING 2008年第5期19卷 611-622页

作者： Moses, Scott A. Gruenwald, Le Dadachanji, Khushru Univ Oklahoma Sch Ind Engn Norman OK 73019 USA Univ Oklahoma Sch Comp Sci Norman OK 73019 USA

This paper defines a highly scalable interval index structure called the Temporal Bin tree (TB-tree) that can be embedded in any resource planning application whose algorithms require efficiently estimating either the time that a resource will be available to process a specific task of known length or the net availability of a resource during a specified period of time. It is specifically engineered to meet the real-time response and space efficiency requirements of large-scale resource planning applications that are required for mass customization. Basically, the TB-tree is a binary tree structure that represents availability of a resource across a planning horizon. Representing intervals of availability hierarchically using a tree structure increases the efficiency of search for resource availability when the discretization of time is fine-grained or the planning horizon is long. The tree forms a backbone structure that does not require disruptive rebalancing during update operations, which would mitigate the ability of the tree to respond to queries in real time. Its specific implementation allows for random access at any level of the tree to further improve scalability. An application of planning to real-time promising of order due dates for custom built products provides the context for empirical evaluation. Results of analytical evaluations and simulation experiments clearly demonstrate the scalability of the TB-tree relative to existing index structures in terms of both time and space.

关键词： mass customization build-to-order resource planning resource availability due date assignment index data structures

来源：评论

学校读者我要写书评

暂无评论

Improving on-line construction of two-dimensional suffix trees for square matrices

引用

INFORMATION PROCESSING LETTERS 2009年第10期109卷 504-508页

作者： Na, Joong Chae Kim, Namhee Sim, Jeong Seop Kim, Dong Kyue Hanyang Univ Div Elect & Comp Engn Seoul 133791 South Korea Sejong Univ Dept Comp Sci & Engn Seoul 143747 South Korea Inha Univ Sch Comp & Informat Engn Inchon 402751 South Korea

The two-dimensional (2-D) suffix tree of an n x n square matrix A is a compacted trie that represents all square submatrices of A. We consider constructing 2-D suffix trees on-line, which means, instead of giving the whole matrix A in advance, A is separated and each part of A is given at different time as algorithms proceed. In general, developing an on-line algorithm is more difficult than developing an off-line algorithm. Moreover, the smaller the input grain size is, the harder it is to develop an on-line algorithm. In the case of 2-D suffix tree construction, dealing with a character at a time is harder than dealing with a row or a column at a time. In this paper we propose a randomized linear-time algorithm for constructing 2-D suffix trees on-line. This algorithm is superior to previous algorithms in two ways: (1) This is the first linear-time algorithm for constructing 2-D suffix trees on-line. Although there have been some linear-time algorithms for off-line construction, there were no linear-time algorithms for on-line construction. (2) We deal with the most fine-grain on-line case, i.e., our algorithm can construct a 2-D suffix tree even though only one character of A is given at a time, while previous on-line algorithms require at least a row and/or a column at a time. (C) 2009 Elsevier B.V.. All rights reserved.

关键词： Design of algorithms Two-dimensional suffix trees index data structures On-line algorithms Randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

iDMS: An index-Based Framework for Tracking Distributed Multidimensional data Streams

iDMS: An Index-Based Framework for Tracking Distributed Mult...

引用

2023 Congress in Computer Science, Computer Engineering, and Applied Computing, CSCE 2023

作者： Razavi, Zhinoos Sellis, Timos Liao, Kewen Razavi, Shahab Rmit University Dept. Computer Science Melbourne Australia Swinburne University Dept. Computer Science Melbourne Australia Australian Catholic University Dept. Law and Business Sydney Australia Vanderbilt University Medical Center Dept. Medicine Nashville United States

ISBN: (纸本)9798350327595

Histograms are a compact and effective way to summarize large datasets, representing data distribution by partitioning it into blocks or buckets for visualization and analysis. They find widespread use in diverse fields, from image processing to statistical analysis and database optimization. This paper focuses on merging and maintaining a centralized histogram for distributed summaries in multidimensional spaces. The proposed framework employs a dynamic index data structure to efficiently approximate data distribution from continuous distributed data streams. It offers a simple and implementable solution, gener-ating an up-to-date histogram for aggregated multidimensional data summaries while supporting both centralized and local histograms. Experimental results demonstrate its performance in parallel and distributed settings, considering communication cost, error rate, and practicality. © 2023 IEEE.

关键词： data Summarization Distributed computing Generative models Histograms index data structures

来源：评论

学校读者我要写书评

暂无评论

Constructing suffix arrays in linear time

引用

JOURNAL OF DISCRETE ALGORITHMS 2005年第2-4期3卷 126-142页

作者： Kim, Dong Kyue Sim, Jeong Seop Park, Heejin Park, Kunsoo Pusan Natl Univ Sch Elect & Comp Engn Busan 609735 South Korea Inha Univ Sch Comp Sci & Engn Incheon 402751 South Korea Hanyang Univ Coll Informat & Commun Seoul 133791 South Korea Seoul Natl Univ Sch Comp Sci & Engn Seoul 151742 South Korea

The time complexity of suffix tree construction has been shown to be equivalent to that of sorting: O(n) for a constant-size alphabet or an integer alphabet and O( n log n) for a general alphabet. However, previous algorithms for constructing suffix arrays have the time complexity of O( n log n) even for a constant-size alphabet. In this paper we present a linear-time algorithm to con struct suffix arrays for integer alphabets, which do not use suffix trees as intermediate data structures during its construction. Since the case of a constant-size alphabet can be subsumed in that of an integer alphabet, our result implies that the time complexity of directly constructing suffix arrays matches that of constructing suffix trees. (C) 2004 Elsevier B.V. All rights reserved.

关键词： index data structures Suffix arrays

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：