Electronics and Telecommunications Research Institute

Jang Sun Lee

Jae Soo Yoo

Seok Il Song

Hun Soon Lee

Myung Joon Kim

Jin Soo Lee

June Hwan Kim

Myung-Joon Kim

Gil Rok Oh

Seok Hee Lee

Young-Kee Song

A recovery method for a high-dimensional index structure is disclosed, in which a reinsert operation is employed based on ARIES (algorithm for recovery and isolation exploiting semantics) and a page-oriented redo and a logical undo. Further, a recording medium on which a program for carrying out the above method is recorded is disclosed, the program being readable by a computer. The recovery method for a high-dimensional index structure employing a reinsert operation according to the present invention includes the following steps. At a first step, an entry is inserted into a node, a minimum bounding region is adjusted, an overflow is processed, and a log record is stored. At a second step, the log record thus stored is recovered.

Efficient recovery method for high-dimensional index structure employing reinsert operation

A concurrency control method for searching the high-dimensional index tree of a database is disclosed. The concurrency control includes: a) adding a root node to the queue and acquiring the shared lock for reinsertion node; b) determining whether the queue is empty or not, fetching a node from the queue and assigning the fetched node as a current node if queue is not empty, releasing the shared lock and terminating the search process if queue is empty; c) acquiring the shared latch in the current node, selecting the lower nodes which are within the query range and adding the selected nodes to the queue if current node is not leaf or to the result set if current node is leaf; and d) returning to the step b).

Concurrency control method for high-dimensional index structure using latch and lock

A concurrency control method for a high dimensional index structure that provides efficient concurrency control method for a high dimensional index structure, which performs reinsertion of certain objects to cope with node overflow. The concurrency controlled searching method includes the following steps. First, an entry is obtained from a queue storing the root node and an object relating to the entry is selected. Second, whether a logic sequence number (LSN) of a lower level node is larger than an expected LSN stored in the upper node is determined. Third, the process moves to a neighbor node of the lower level node if the LSN is bigger than an expected LSN stored in the upper node in the second step, selects a relating object, and performs from the second step repeatedly. Fourth, an object of a node of a level corresponding to the lower level node in a reinsertion table is selected when a search on an index tree is finished if the LSN is not bigger than the expected LSN stored in the upper node in the second step.

Efficient concurrency control method for high dimensional index structures

Growing community of inventors

Taejon, South Korea

Jang Sun Lee