公开(公告)号：KR100327122B1

公开(公告)日：2002-03-13

申请号：KR1019990061940

申请日：1999-12-24

Applicant: 한국전자통신연구원

Inventor： 이장선 ,  김준 ,  이훈순 ,  김명준 ,  오길록 ,  유재수 ,  송석일

IPC: G06F7/00

CPC classification number: G06F11/1474 ,  Y10S707/99933 ,  Y10S707/99953

Abstract: 본발명은재삽입연산을수행하는고차원색인구조를위한회복방법과상기방법을실현시키기위한프로그램을기록한컴퓨터로읽을수 있는기록매체에관한것으로, 'ARIES'(Algorithm for Recovery and Isolation Exploiting Semantics)에기반하고, 페이지지향재시행및 페이지지향복귀를기본으로하여, 재삽입연산시효율적인회복을보장하는재삽입연산을수행하는고차원색인구조를위한회복방법과상기방법을실현시키기위한프로그램을기록한컴퓨터로읽을수 있는기록매체를제공하기위하여, 노드에엔트리를삽입하고, 최소경계영역을조정하고, 넘침을처리를하며, 해당하는로그레코드를저장하는제 1 단계; 및상기저장된로그레코드를회복시키는제 2 단계를포함하며, 고차원색인구조회복장치등에이용됨.

公开(公告)号：KR100419575B1

公开(公告)日：2004-02-19

申请号：KR1020000073539

申请日：2000-12-05

Applicant: 한국전자통신연구원

Inventor： 이훈순 ,  김준 ,  유재수 ,  송석일 ,  피준일

IPC: G06F17/30

CPC classification number: G06F17/30333 ,  Y10S707/99934 ,  Y10S707/99935

Abstract: A bulk loading method, for use in a high-dimensional index structure using some parts of dimensions based on an unbalanced binarization scheme, accelerates an index construction and improves a search performance. For the purpose, the bulk loading method calculates a topology of the index by recognizing information for the index to be constructed using a given data set, splits the given data set into sub-sets of data by repeatedly performing an establishment of a split strategy and a binarization based on the calculated topology of the index, if a leaf node is derived from the sub-sets of data divided through a top-down recursive split process, reflects a minimum bounding region of the leaf node on a higher node, and, if a non-leaf node is generated, repeatedly performing the above processes for another sub-set of data to thereby produce a final root node.

Abstract translation: 批量加载方法用于使用基于不平衡二值化方案的维度的某些部分的高维索引结构，加快了索引构建并提高了搜索性能。 为此目的，批量加载方法通过使用给定数据集识别要构建的索引的信息来计算索​​引的拓扑，通过重复执行分离策略的建立来将给定数据集拆分为数据的子集，并且 如果从通过自顶向下递归分割处理划分的数据子集导出叶节点，则基于所计算的索引拓扑的二值化反映了较高节点上的叶节点的最小边界区域， 如果生成了非叶节点，则对另一个数据子集重复执行上述过程，从而产生最终的根节点。

公开(公告)号：KR100349667B1

公开(公告)日：2002-08-23

申请号：KR1020000008238

申请日：2000-02-21

Applicant: 한국전자통신연구원

Inventor： 이장선 ,  이진수 ,  이훈순 ,  김명준 ,  유재수 ,  송석일 ,  이석희

IPC: G06F17/40

Abstract: 본 발명은 데이터베이스 시스템의 동시성 제어방법에 관한 것으로, 고차원 색인 구조에서 노드의 용량이 초과하여 넘침이 발생할 때에 재 삽입 연산 중 재 삽입을 위해 색인 구조의 노드에서 삭제된 객체들에 대해서도 탐색이 가능하도록 하는 동시성 제어방법 및 상기 방법을 실현시키기 위한 프로그램을 기록한 컴퓨터로 읽을 수 있는 기록 매체를 제공한다.
본 발명에 따른 동시성 제어방법은 전역계수기로 로그일련번호를 사용하여 비단말 노드의 엔트리에 논리일련번호가 포함되어 저장 효율을 떨어뜨리는 문제를 방지하고, 재 삽입을 위하여 트리에서 삭제한 엔트리를 특정노드(재 삽입 노드)에 보관하여 탐색연산이 이를 참조할 수 있도록 해 준다. 또한, 래치와 잠금을 혼용하여 색인노드에 대한 잠금은 탐색연산에 전혀 영향을 미치지 않고, 탐색 연산이 수행될 때 접근하려는 노드에 공유모드의 래치만 획득하므로 노드에 대한 삽입 또는 삭제 연산의 잠금으로 인한 지연이 발생하지 않아 높은 탐색 성능을 제공할 수 있다.

公开(公告)号：KR1020030013619A

公开(公告)日：2003-02-15

申请号：KR1020010047715

申请日：2001-08-08

Applicant: 한국전자통신연구원

Inventor： 박춘서 ,  김창수 ,  김경배 ,  신범주 ,  유재수 ,  송석일 ,  신재룡

IPC: G06F17/30

Abstract: PURPOSE: A method for inserting and searching data of a parallel higher index structure is provided to search a higher index effectively by transforming a higher index structure which uses a parallel property of a SAN(Storage Area Network) thereby increasing a fan out, reducing a height of a tree, and maximizing a parallel property of an input/output at searching a range in searching a similarity. CONSTITUTION: For performing a partial K-most access query in a main server and all sub servers simultaneously, if a K-access query is entered, all servers access to a root node(1300). It is judged whether the accessed root node is a non-terminal node or not(1301). If the accessed root node is a non-terminal node, all servers calculates a similarity with a query and an entry, and each entry is sorted in a list in order of similarity(1302). All servers access to a child node of the first entry stored in the list in parallel and allocate the current node as a root node(1303), and the current stage is returned to the above stage (1301) for judging a non-terminal node of not of the root node.

Abstract translation: 目的：提供一种用于插入和搜索并行较高索引结构的数据的方法，通过转换使用SAN（存储区域网络）的并行属性的较高索引结构，有效地搜索较高索引，从而增加扇出，减少 在搜索相似度的范围内最大化输入/输出的并行属性。 规定：为了在主服务器和所有子服务器中同时执行部分K最多访问查询，如果输入K访问查询，则所有服务器都访问根节点（1300）。 判断所访问的根节点是否是非终端节点（1301）。 如果所访问的根节点是非终端节点，则所有服务器计算与查询和条目的相似性，并且每个条目按照相似度的顺序排列在列表中（1302）。 所有服务器并行地存储在列表中的第一条目的子节点并分配当前节点作为根节点（1303），并且当前阶段返回到上述阶段（1301），以判断非终端节点 不是根节点。

公开(公告)号：KR1020010063839A

公开(公告)日：2001-07-09

申请号：KR1019990061940

申请日：1999-12-24

Applicant: 한국전자통신연구원

Inventor： 이장선 ,  김준 ,  이훈순 ,  김명준 ,  오길록 ,  유재수 ,  송석일

IPC: G06F7/00

CPC classification number: G06F11/1474 ,  Y10S707/99933 ,  Y10S707/99953

Abstract: PURPOSE: A method for recovering for a high dimensional index structure is provided to secure an efficient recovery in a reinsertion calculation based on an ARIES(Algorithm for recovery and isolation exploiting semantics) and a page-oriented re-performing and a page-oriented recovery. CONSTITUTION: An "NTA" is started for recovering a deletion of one reinsertion entry(200). The number of remaining entries which are not inserted in a node to be performed a recovery are read, and the entries are inserted in a node to be performed a recovery as the number of entries which are not inserted and remains out of the deleted entries which are recorded in a log record. In addition, a log record in the case that a partial or all reinsertion entries are inserted is recorded when a log record is recovered at a deletion of a reinsertion entry selected in a terminal or non-terminal node(201). After the entry is inserted, the changed minimum boundary area is reflected in an ancestor node(202), and the "dummyCLR" meaning that one recovery process of a reinsertion entry is completed is recorded(203), and the process is restored.

Abstract translation: 目的：提供一种恢复高维度索引结构的方法，以确保基于ARIES（恢复和隔离开发语义的算法）和面向页面的重新执行和面向页面的恢复的重新插入计算中的有效恢复 。 构成：启动“NTA”以恢复一个重新插入条目（200）的删除。 读取未插入到要执行恢复的节点中的剩余条目的数量，并且将条目插入到要执行恢复的节点中作为未被插入并保留在删除条目之外的条目的数量 记录在日志记录中。 此外，当在终端或非终端节点（201）中选择的重新插入条目的删除中恢复日志记录时，记录插入部分或所有重新插入条目的情况下的日志记录。 在插入条目之后，改变的最小边界区域被反映在祖先节点（202）中，并且记录表示重新插入条目的一个恢复处理完成的“dummyCLR”（203），并且处理被恢复。

公开(公告)号：KR100289331B1

公开(公告)日：2001-05-02

申请号：KR1019980044943

申请日：1998-10-27

Applicant: 한국전자통신연구원

Inventor： 이장선 ,  송영기 ,  김명준 ,  유재수 ,  송석일

IPC: G06F15/00

Abstract: 본 발명은 데이터베이스의 동시성 제어 방법에 관한 것이며, 특히, 노드의 용량이 초과하여 넘침(overflow)이 발생할 때에 노드 내의 일부 객체에 대한 재 삽입을 수행하는 고차원 색인 구조를 위한 동시성 제어 방법을 제공하는 데 그 목적이 있다.
본 발명에 따르면, 데이터베이스에 적용되는 고차원 색인 구조의 동시성 제어 방법에 있어서, 뿌리 노드를 저장하고 있는 큐로부터 엔트리를 가져온 후에, 가져온 엔트리에 대한 객체를 선택하는 제 1 단계; 하위 노드가 가지고 있는 논리일련번호가 상위 노드에 저장되어 있는 예상논리일련번호보다 큰지를 판단하는 제 2 단계; 상기 제 2 단계의 판단 결과, 크면 하위 노드의 이웃 노드로 이동하면서 객체를 선택한 후에, 상기 제 2 단계부터 반복 수행하는 제 3 단계; 및 상기 제 3 단계의 판단 결과, 크지않으면 색인 트리에 대한 검색이 완료됨에 따라 재 삽입 테이블에 존재하는 하위 노드에 해당하는 레벨의 노드로부터 객체를 선택하는 제 4 단계를 포함하여 이루어진 동시성이 제어된 탐색 방법이 제공된다.

公开(公告)号：KR100284778B1

公开(公告)日：2001-03-15

申请号：KR1019980045434

申请日：1998-10-28

Applicant: 한국전자통신연구원

Inventor： 김준 ,  허대영 ,  이진수 ,  유재수 ,  이석희

IPC: G06F17/30

Abstract: 본 발명은 내용기반 이미지 검색을 위한 고차원 색인구조의 삽입 방법에 관한 것이다.
본 발명은 기존 CIR 트리와 유사하게 색인에 사용되는 특징 차원을 가변적으로 사용하고 필요에 따라 정상 노드의 정수배 크기이면서 디스크의 연속적인 위치에 저장되는 확장 노드를 사용하여 고차원 특징을 효율적으로 수용할 수 있도록 한다. 또한 새로운 객체의 삽입시에 효율적인 하위 노드 선택 기준을 제시하고, 색인구조의 검색 효율을 높일 수 있는 분기 노드 및 단말 노드의 분할 알고리즘을 사용하여 검색과 삽입시 성능을 높일 수 있도록 한다. 그리고 색인구조 생성시 노드에 넘침(overflow)이 발생할 때 무게 중심점을 기반으로 재삽입 객체를 선택하여 재삽입을 실시한다.
따라서, 본 발명은 많은 특징 차원을 포함하고 있는 이미지 정보를 데이터베이스로 구성했을 때 원하는 이미지를 효율적으로 검색할 수 있다.

公开(公告)号：KR1020020044029A

公开(公告)日：2002-06-14

申请号：KR1020000073539

申请日：2000-12-05

Applicant: 한국전자통신연구원

Inventor： 이훈순 ,  김준 ,  유재수 ,  송석일 ,  피준일

IPC: G06F17/30

CPC classification number: G06F17/30333 ,  Y10S707/99934 ,  Y10S707/99935

Abstract: PURPOSE: A bulk loading method for a high dimensional index structure is provided to be suitable to the high dimensional index structure using a partial dimension based on an unbalanced bisection method of the UBBT(Unbalance Bisectional Bulk-loading) and to improve the index configuration time and a search function. CONSTITUTION: The bulk loading method for high dimensional index structure comprises the steps of calculating a format of an index structure by understanding the information for the index to be formed as a given data set, dividing the given data set into the sub data set while repeatedly executing the establishment of the division strategy and the bisection method on a basis of the calculated index structure, reflecting a minimum border area of an end node to an upper level if only one end node is generated from the sub data set by executing the repeated dividing process, and generating a final root node by repeated executing the previous steps for the other sub data set if one non-end node is generated.

Abstract translation: 目的：提供一种适用于高尺寸折射率结构的体积加载方法，适用于使用基于UBBT（不平衡二分批装载）的不平衡二分法的部分维度的高维度索引结构，并提高索引配置时间 和搜索功能。 构成：用于高维度索引结构的批量加载方法包括以下步骤：通过理解要形成为给定数据集的索引的信息来计算索​​引结构的格式，同时重复地将给定的数据集划分为子数据集 在计算出的索引结构的基础上执行划分策略和二分法的建立，如果仅通过执行重复划分从子数据集生成一个端节点，则将端节点的最小边界区域反映到较高级别 过程，并且如果生成了一个非端节点，则通过重复执行其他子数据集的前述步骤来生成最终根节点。

公开(公告)号：KR1020010066737A

公开(公告)日：2001-07-11

申请号：KR1020000008238

申请日：2000-02-21

Applicant: 한국전자통신연구원

Inventor： 이장선 ,  이진수 ,  이훈순 ,  김명준 ,  유재수 ,  송석일 ,  이석희

IPC: G06F17/40

Abstract: PURPOSE: A method for controlling a consistency of a higher-order index structure is provided to increase the performance of a search by obtaining a latch of a common mode in case that a search operation is performed, thereby preventing a delay from being generated from an insertion to a node or a lock of a deletion operation. CONSTITUTION: A route node is stored in a queue(910). A common lock is obtained(912). It is judged whether the queue is empty(914). In case that the queue isn't empty, a node is picked out from the queue and set as a current node(916). In case that the queue is empty, a lock to a reinsertion node is released. In addition, a search is terminated(938). It is judged whether a level of the current node is lower than a present level(918). A common latch is obtained(928). It is judged whether the current node is a terminal(930). In case that the current node isn't the terminal, child nodes in a range of question are put in(932). The common latch is released(936).

Abstract translation: 目的：提供一种用于控制高阶索引结构的一致性的方法，用于通过在进行搜索操作的情况下获得共模的锁存来增加搜索的性能，从而防止从 插入节点或锁定的删除操作。 构成：路由节点存储在队列（910）中。 获得公共锁（912）。 判断队列是否空（914）。 如果队列不为空，则从队列中选出一个节点并设置为当前节点（916）。 如果队列为空，则会释放对重新插入节点的锁定。 此外，搜索终止（938）。 判断当前节点的电平是否低于当前电平（918）。 获得一个共同的锁存器（928）。 判断当前节点是否为终端（930）。 在当前节点不是终端的情况下，将问题范围内的子节点放入（932）中。 公共锁存器被释放（936）。

公开(公告)号：KR1020000027489A

公开(公告)日：2000-05-15

申请号：KR1019980045434

申请日：1998-10-28

Applicant: 한국전자통신연구원

Inventor： 김준 ,  허대영 ,  이진수 ,  유재수 ,  이석희

IPC: G06F17/30

CPC classification number: G06F17/30256 ,  Y10S707/99942

Abstract: PURPOSE: A method for inserting a higher dimension index structure is provided to enhance a clustering effect in an index structure through an application of a weight center point. CONSTITUTION: In a method for inserting a higher dimension index structure, an object is inserted to a root node when a tree is only composed of the root node. If an overflow occurs at the root node to which the object is inserted, a new root node is generated. If a lower node of the root node is a branch node, after inserting an object, branch nodes that the increase of the overlap number with peripheral nodes is less, branch nodes having the same values at many dimensions, branch nodes that the size increase of a minimum bounding region is less, and branch nodes closely adjacent to a center are selected in this order. In case where an overflow occurs at the selected branch node, a reinsertion object is selected in the base on the weight center point so as to be reinserted to the branch node. If an overflow occurs at a branch node at which the reinsertion is performed, the branch node is divided. If an overflow does not occur, the minimum bounding region is adjusted. A terminal node is selected so as to insert an object when the lower node of the root node or of the branch node is the terminal node. A reinsertion object based on the weight center point is selected so as to be inserted to the terminal node when an overflow occurs at the terminal node.

Abstract translation: 目的：提供一种用于插入较高维度索引结构的方法，以通过应用重量中心点来增强索引结构中的聚类效果。 构成：在一种用于插入较高维度索引结构的方法中，当树仅由根节点组成时，将对象插入根节点。 如果在插入对象的根节点发生溢出，则会生成新的根节点。 如果根节点的下层节点是分支节点，则在插入对象之后，与外围节点的重叠数量增加的分支节点较少，分支节点在许多维度上具有相同的值，分支节点的大小增加 最小边界区域较小，并且以这个顺序选择与中心紧密相邻的分支节点。 在所选择的分支节点发生溢出的情况下，在权重中心点的基地中选择重新插入对象，以便重新插入到分支节点。 如果在执行重新插入的分支节点发生溢出，则分支节点被分割。 如果不发生溢出，则调整最小边界区域。 选择终端节点，以便当根节点或分支节点的下级节点为终端节点时插入对象。 选择基于权重中心点的重新插入对象，以便在终端节点处发生溢出时插入终端节点。