梁活民 肖文俊 魏文红

(1.华南理工大学计算机科学与工程学院，广东广州510006;2.华南理工大学软件学院，广东广州510006;3.华南理工大学电子与信息学院，广东广州510640)

对等覆盖网络已经成为网络应用的重要基础，而结构化对等覆盖网络因其可扩展性而得到了广泛的应用.结构化对等覆盖网络通过分布式哈希表来计算被存储对象的地址，将键值映射到网络的节点，这种工作方式对于单个精确文件名的搜索效率非常高，但对于实际应用中常见的不限定搜索形式的复杂搜索，结构化覆盖网络则缺乏支持，这使其可应用的场合大大减少.这里所谓的复杂搜索是指不限定搜索形式和语法的搜索(多关键字搜索、前缀搜索、全文搜索等，或这些搜索形式的结合)，例如在Google上常用的支持并、或的多关键字查询对于一般的结构化覆盖网络是非常困难的，对于更复杂的正则语言或SQL语言式的查询更是无能为力.

以多关键字搜索为例，由于分布式哈希表(DHT)的机制只支持单关键字搜索，文献［1］中试图通过倒排表来解决这个问题，但该方法存在索引过载、单点失效等缺点，而且倒排表可能会很大，在相关节点间传输用于交集运算的倒排表的代价也非常高.文献［2］中使用超立方体作为逻辑的关键字搜索层，这种方法在pin搜索［2］时效率较高，对于给定较少关键字的超集搜索效率却很低，此外这种方法还需要预先知道整个关键字集合.所以对于复杂的搜索……