Font Size: a A A

Study And Implementation On Distributed Hash Index Structure In P2P Environments

Posted on:2009-05-13Degree:MasterType:Thesis
Country:ChinaCandidate:J M FanFull Text:PDF
GTID:2178360308978351Subject:Computer application technology
Abstract/Summary:PDF Full Text Request
With the rapid development of Internet, Peer-to-Peer (P2P) data management technology is becoming a hotspot in the research field. The P2P system offers the possibility for digging the idle resources sufficiently. The sharing and cooperating of the entire network resources are realized. How to design a distributed index structure to support astronomical data for efficient interaction became the core of the current P2P technology.Bloom Filter hash algorithm uses a bit vector to denote data set, and it is able to support hash query efficiently. Bloom Filter is an excellent data structure, which can succinctly represent a data set in order to support membership queries. It is widely used in databases, networks and distributed system. However, the false positive of Bloom Filter causes the query processing inefficiency, and its dynamic storage capacity is poor.Division Bloom Filter (DBF) hash algorithm is presented, which using dividual bit vector to denote data set. Division Bloom Filter increases the number of the hash functions with no impact on the fill rate of the bit vectors, and thus it can reduce the false positive rate. Furthermore, Division Bloom Filter can dynamically change the number of bit vectors to adapt to the changes of data set in, so that it fits in with the dynamic nature of P2P system. We also analyze the usage of the Division Bloom Filter as an index structure to simplify data set operations, and discuss the applicability of Division Bloom Filter in four data set operations (and/or/xor/sub).The performance evaluation and analysis show that Division Bloom Filter can reduce the false positive rate of Bloom Filter hash algorithm, and it has a good dynamic nature. Division Bloom Filter, used as index structure, can effectively simplify the data set operation, reduce the communication cost and improve the query efficiency.
Keywords/Search Tags:P2P system, Bloom Filter, Division Bloom Filter, distributed index, set operation
PDF Full Text Request
Related items