China
Africa
Explore chapters and articles related to this topic
External Memory Data Structures
Published in Suman Saha, Shailendra Shukla, Advanced Data Structures, 2019
In the B+ tree variant, all the items are stored in the leaves, and the leaves are linked together in symmetric order to facilitate range queries and sequential access. The internal nodes store only key values and pointers and thus can have a higher branching factor. In the most popular variant of B+ trees, called B* trees, splitting can usually be postponed when a node overflows, by sharing the node’s data with one of its adjacent siblings. The node needs to be split into two nodes when sibling is also full and in that case the keys of the node and its full sibling are redistributed evenly to make all three nodes to about 2/3 full, which allows space for future sharing. This local optimization reduces the number of times new nodes must be created and thus increases storage capacity. And since there are fewer nodes in the tree, search I/O costs are lower. Storage utilization can be increased further by sharing among several siblings, at the cost of more complicated insertions and deletions. Some helpful space-saving techniques borrowed from hashing are partial expansions and use of overflow nodes.
Real-Time Search in the Sensor Internet
Published in Ioanis Nikolaidis, Krzysztof Iniewski, Building Sensor Networks, 2017
A forward index stores for every document the list of extracted words. So, the data structure is a list of mappings between a website and a word, grouped and sorted by the website. If the forward index is rearranged in the sense that it is sorted and grouped by words, a record-level inverted index is formed (see Figure 4.2). Typically, a word-level inverted index, i.e., a record-level inverted index with the position for each word in the document, is formed because it allows easier search for phrases and words with a certain proximity in the document. As billions of websites exist, the size of an inverted index can grow up to thousands of terabytes, as is the case for Google. Hence, compression is used to lessen storage at the cost of greater power consumption associated with the higher processor utilization for compression and decompression. The performance of update and delete operations of an inverted index is dependent on the underlying data structure. Usually, a tree data structure, such as a B-Tree, is used, resulting in O(log n) runtime. With millions of entries in an inverted index, these operations can be rather expensive with respect to time and disc accesses.
A novel P2P information retrieval framework using locality-sensitive hashing and B+ tree
Published in Amir Hussain, Mirjana Ivanovic, Electronics, Communications and Networks IV, 2015
AB+ tree is an n-ary tree with a variable but often large number of children per node. The structure of a B+ tree consists of a root, many internal nodes and leaves. The root may be either a leaf or a node with two or more children. In a B+ tree each internal node only contains keys and the values are stored in the leaves. It is a dynamic, multilevel index, with maximum and minimum bounds on the number of keys in each index segment. Figure 4 shows an example of a B+ tree, where the key is integer range from 1 to 25, and the value are labelled with "D" stored on the leaf only.
A spatial multi-scale integer coding method and its application to three-dimensional model organization
Published in International Journal of Digital Earth, 2020
Guangling Lai, Xiaochong Tong, Yongsheng Zhang, Lu Ding, Yinling Sui, Yi Lei, Yong Zhang
This study selected the Geohash code as the contrast object (Niemeyer 2013) because the three-dimensional Geohash can convert the three-dimensional index problem into a one-dimensional index to obtain a solution, which is widely used and has high efficiency with respect to three-dimensional data organization. Second, we selected the three-dimensional Geohash because it is also based on the spatial recursive octree and Z-order curve coding, which is similar to the method in this study. The third reason we selected the Geohash is that when the three-dimensional Geohash organizes three-dimensional data, the Geohash coding organization is performed first. Based on this, one-dimensional indices, such as the B-tree and B+ tree, are established to obtain the index of the three-dimensional data. The advantage of this is that it is convenient to use the database for unified comparison.
Decomposition methods for solving Markov decision processes with multiple models of the parameters
Published in IISE Transactions, 2021
Lauren N. Steimle, Vinayak S. Ahluwalia, Charmee Kamdar, Brian T. Denton
PB-B&B algorithms have a worst-case running time of where b is the branching factor, d is the depth of the tree, and U is an upper bound on the time required to solve a subproblem (Morrison et al., 2016). The branching factor of the PB-B&B tree described above is A and the depth of the tree is ST. The worst-case running time to solve a subproblem is the time required to solve M MDPs in the worst-case. The worst-case time to solve a single MDP is ) (Puterman 1994; p. 93).□
NAM: a nearest acquaintance modeling approach for VM allocation using R-Tree
Published in International Journal of Computers and Applications, 2021
Ankita Jiyani, Mehul Mahrishi, Yogesh Meena, Girdhari Singh
A R-Tree is a generalization of B+ trees in multidimensional space. It blends the features of Quad trees and B-Trees. From Quad trees, it adapts the flexibility of dynamically adjusting to maintain their grouping in dense or dead space. From B-Tree, it adapts the height balancing. It is used to configure a set of dynamic d-dimensional objects and representing them by minimum bounding d-dimensional rectangles (MBRs) [29]. The insertion and deletion operations are based on the overlapping and minimum enlargement of the MBRs. The operations are such that the resultant tree is balanced after every insertion or deletion.