China
Africa
Explore chapters and articles related to this topic
RFID Data Warehousing and Analysis
Published in Lu Yan, Yan Zhang, Laurence T. Yang, Huansheng Ning, The Internet of Things, 2008
An alternative compression mechanism is to store a single transition record for the 50 CDs that move together from the warehouse to the shelf, i.e., to group transitions and not stays. The problem with transition compression is that it makes it difficult to answer queries about items at a given location or going through a series of locations. For example, in order to answer the query: What is the average time that CDs stay at the shelf? you can directly get the information from the stay records with location = shelf, but if only transition records are available, you need to find all the transition records with origin = shelf and the ones with destination = shelf join them on the EPC and compute departure time–arrival time. Another method of compression would be to look at the sequence of locations that an item goes through as a string, and use a Trie [6] to store the strings. The Trie data structure is a tree where each node is associated with a string prefix, and all descendant of the node share the prefix. The problem with this approach is that you lose compression power. In the CDs example, if the 50 items all stay at the warehouse together, but they come from different locations, a trie would have to create distinct nodes for each, thus gaining no compression.
Efficient Data Structures for Bursty Access Patterns
Published in Weidong Wu, Packet Forwarding Technologies, 2007
For simplicity, we only consider the STL problem with two memory types (cj = 0 in Equation 6.1), type 1 fast, type 2 slow; that is, for every lookup there are no more than two access memories. Then we select a data structure for IP-address lookup. A binary tree is one of the simplest representations of a set of prefixes. Each prefix is represented by a node in the tree. Each node has at most two children. The implementation of a binary tree involves bit-by-bit manipulation, which is inefficient for long prefixes. A trie is a more general data structure than a binary tree, and each node in it can have any number of children. A level-compressed trie [6] is a trie in which each complete subtree of height h is collapsed into a subtree of height 1 with 2h children, and all the intermediate nodes from level 1 to level h – 1 can be replaced by 2h children. We can represent a set of prefixes with some small tables; they fit into different memory types. For the lookup tables, we make the following design decision: given a set of prefixes by a binary tree, stage 1 transforms it to a complete prefixes tree; stage 2 transforms it to a level-compressed trie.
Finding Experts in Community Question Answering System Using Trie String Matching Algorithm with Domain Knowledge
Published in IETE Journal of Research, 2023
In the trie data structure, the time complexity to locate the string is O (L), where L is the length of the word. The trie data structure helps to find the largest prefix matching. Moreover, trie takes less space when compared to BST. The question keywords are searched in the trie tree. The searching process is made case insensitive. i.e. HTML can be mapped to both html and Html. This helps to locate the keyword even if there is a mismatch in uppercase and lowercase letters. If the sequence of letters in the question keyword is matched with the characters in the trie tree, then it is decided as a tag. The question keywords may match with more than one tag in the same domain. For example, if the extracted question keywords are ‘plsql’, and ‘database’ then two tags would be matched in the domain trie tree. As a result, the domain and the tags are identified for the given question.