权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Design and Implementation of a Parallel Processing Scheme for Complex Object Index

复杂对象索引并行处理方案的设计与实现

基本信息

批准号：
12680341
负责人：
TUJI Tatsuo
金额：
$ 1.92万
依托单位：
Fukui University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
2000
资助国家：
日本
起止时间：
2000 至 2001
项目状态：
已结题

项目摘要

In this research, we have studied parallel indexing schemes for complex objects. The following major contributions have been made.(1) Horizontal and vertical index splitting schemes are proposed, and parallel index retrieval methods are presented and evaluated.2) Parallel index system with online modification capability is proposed and evaluated.(3) A parallel index retrieval scheme is provided and implemented for complex queries combined by AND, OR, NOT logical operators.A fundamental problem on retrieval performance is recognized in the process of constructing above prototype systems. That is, many data packets of low filling up ratio are produced and the communication cost among the related processors much increases. Against this problem, we have invented a scheme of merging more than one packets into a single packet. The scheme incorporates increasing the filling up ratio of packets and effective parallel retrieval termination detecting mechanism. But it was recognized that the scheme suffers from the following drawbacks. That is, a retrieval request may be outrun by the one issued later due to the assumed asynchronous parallel retrieving environment. To incorporate an efficient termination detection scheme, the filling up ratio would be inevitably decreased and the average turnaround time would be increased due to the increase of the communication cost. Against this problem, we have proposed a implementation scheme in which the outrunning of the retrieval requests never occur by scheduling and activating a different set of machines for a new request.We have constructed a parallel index retrieval system that incorporate the scheme and evaluated its performance.

在这项研究中，我们研究了复杂对象的并行索引方案。作出了以下主要贡献。(1)提出了水平和垂直方向的索引分割方案，给出了并行索引检索方法并进行了评价。2）提出了具有在线修改能力的并行索引系统并进行了评价。(3)针对由AND、OR、NOT逻辑运算符组成的复杂查询，提出并实现了一种并行索引检索方案。也就是说，产生了许多低填充率的数据包，并且相关处理器之间的通信成本大大增加。针对这个问题，我们发明了一种将多个数据包合并为一个数据包的方案。该方案结合了提高数据包填充率和有效的并行检索终止检测机制。但人们认识到，该计划有以下缺点。也就是说，由于假定的异步并行检索环境，检索请求可能会被稍后发出的检索请求超过。为了结合有效的终止检测方案，填充率将不可避免地降低，并且由于通信成本的增加，平均周转时间将增加。针对这一问题，我们提出了一种实现方案，在该方案中，通过为新的请求调度和激活不同的机器集，使得检索请求永远不会发生溢出，并构建了一个包含该方案的并行索引检索系统，并对其性能进行了评估。