China
Africa
Explore chapters and articles related to this topic
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.
Applications to Databases
Published in Suman Saha, Shailendra Shukla, Advanced Data Structures, 2019
CouchDB uses a B+ structure to store huge amounts of data. B trees typical have single-digit heights even when storing millions of entries. The advantage of a B tree is the ability to store leaves on a slow medium such as a hard drive. CouchDB utilizes that feature. An operating system is likely to cache the upper tree nodes so only the final leaf nodes are stored on a hard disk. B tree access time is fewer than 10 ms, even for extremely large amounts of data. CouchDB, B tree appends data only to the database file that keeps the B tree on disk and append-only leaf nodes. B Tree provides a robust database file. Inclusion of B tree features in CouchDB helps avoid data corruption by not overwriting existing data on hard disks.
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.
A new branch-and-bound algorithm for standard quadratic programming problems
Published in Optimization Methods and Software, 2019
G. Liuzzi, M. Locatelli, V. Piccialli
We denote by problem (1), i.e., the root node of the branch-and-bound tree, and its lower bound. We also denote by z the global upper bound and initialize it with the best value obtained by means of a certain number of local minimizations (we perform 10 local minimizations in the experiments). At each node of the B&B tree, we associate a vector of variable statuses. Specifically, Then, at the root note, .
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).□