Chinese Journal of Computers   Full Text
Title	A Trustworthy Index for Inserting Random Sequences
Authors	LIU Feng-Chen1) HUANG He2) LIU Qing-Wen3) DING Yong-Sheng1),4)
Address	1)(College of Information Sciences and Technology, Donghua University, Shanghai 201620) 2)(College of Software, Beihang University, Beijing 100083) 3)(School of Information Engineering, University of Science and Technology Beijing, Beijing 100083) 4)(Engineering Research Center of Digitized Textile & Fashion Technology of Ministry of Education, Shanghai 201620)
Year	2009
Issue	No.5(974—981)
Abstract &   Background	Abstract Jump Index is a kind of trustworthy index which can only build index for strictly monotonically increased sequences rather than unordered sequences. To solve this problem, this paper proposes a novel index supporting building index for random sequences, without losing the trustworthy of jump index. By adding left pointers on the node of jump index, the candidate node in random sequences can be indexed into one of the left or right pointers of a node in the index. The left jump pointers are used to index nodes with less value than current node’s value, while right jump pointers point to those nodes with higher value. Every node in the index has the unique and permanent path from root node, which ensures the trustworthy in the index. Experiment results and proofs in this paper show that the index is trustworthy and supports indexing for random sequences, also it has more efficiency of building index and same complexity of search compared with jump index. The contribution of this paper is that the new index with trustworthy solve the problem that jump index cannot insert and build index for random sequences. Keywords trustworthy; inverted index; index; B+tree; retrieval; algorithm Background This research is partly supported by the Science and Technology Program of China under grant No.A2120061061, Project of the Shanghai Committee of Science and Technology (No.08JC1400100), Shanghai Talent Developing Foundation (No.001), Specialized Foundation for Excellent Talent from Shanghai. In the recent few years, the trustworthy problem in write once read many devices is raised by many researches. To address this issue some researchers proposed a kind of indexes with trustworthy, such as fossilized index and jump index. The former prohibits some manipulation on index after index has been built to keep the trustworthy, later ensures that every node in the index has the unique and permanent path from root node to make sure the index is trustworthy. Although jump index is a better way to handle this problem, it still has difficulty with building index for sequences without orders. Because it requires that sequences must be strictly monotonically increased, this requirements makes it is impossible for inserting random sequences. The authors’ main object is to design an index which can insert and build index for random sequences. How to maintain the trustworthy and efficiency of query is also important. In this paper, authors proposes a solution that adding left pointers on the current node in index as the counterpart of the right pointers in jump index to record nodes with less value than current node, while right jump pointers are used to record with higher value. Therefore the candidate nodes in random sequences can be indexed into one of the left or right pointers depending on its value. Also, this changing on structure does not change the unique and permanent path from root node to any node in the index, which keeps the trustworthy. Compared with jump index, new structure makes building index and inserting records become more flexible and efficient.