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

在本研究中，我们研究了复杂对象的并行索引方案。主要贡献有：(1)提出了水平和垂直索引分割方案，并对并行索引检索方法进行了研究和评价。2)提出并评价了具有在线修改能力的并行指标体系。(3)提供并实现了由and、OR、NOT逻辑运算符组合的复杂查询并行索引检索方案。在构建上述原型系统的过程中，认识到检索性能的一个基本问题。即产生大量低填充率的数据包，大大增加了相关处理器之间的通信成本。针对这个问题，我们发明了一种将多个数据包合并为单个数据包的方案。该方案结合了提高数据包填充率和有效的并行检索终止检测机制。但人们认识到，该方案存在以下缺点。也就是说，由于假定的异步并行检索环境，一个检索请求可能会被后面发出的请求跑得更快。为了采用有效的终端检测方案，由于通信成本的增加，不可避免地会降低填充率，增加平均周转时间。针对这一问题，我们提出了一种实现方案，通过为新请求调度和激活一组不同的机器，永远不会出现检索请求跑路的情况。我们构建了一个包含该方案的并行索引检索系统，并对其性能进行了评价。

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.