Extending peer-to-peer networks for approximate search

ABSTRACT

This paper proposes a way to enable approximate queries in a peer-to-peer network by using a special encoding function and error correcting codes. The encoding function maintains neighborhood relationships so that two similar inputs will result in two similar outputs. The error correcting code is then used to group the similar encoded values around special codewords. In this manner, similar content is located as close as possible in the network. The algorithm is tested in a simulated environment on a HyperCube network overlay.

REFERENCES

• 1: M. Aharia, A. Chandel, S. Saroiu, and S. Keshav. Finding content in file-sharing networks when you cant even spell. In Proceedings of the 6th international Workshop on Peer-to-Peer Systems (IPTPS07), 2007.
• 2: R. Ahmed and R. Boutaba. A scalable peer-to-peer protocol enabling efficient and flexible search, 2006.
• 3: R. Ahmed and R. Boutaba. Distributed pattern matching for p2p systems. In Proceedings of the 10th IEEE/IFIP Network Operations and Management Symposium (NOMS06), April 2007.
• 4: Marcel Karnstedt , Kai-Uwe Sattler , Manfred Hauswirth , Roman Schmidt, Similarity Queries on Structured Data in Structured Overlays, Proceedings of the 22nd International Conference on Data Engineering Workshops, p.32, April 03-07, 2006 [doi>10.1109/ICDEW.2006.137]
• 5: Cristina Schmidt , Manish Parashar, Flexible Information Discovery in Decentralized Distributed Systems, Proceedings of the 12th IEEE International Symposium on High Performance Distributed Computing, p.226, June 22-24, 2003
• 6: C. Schmidt and M. Parashar. Analyzing the search characteristics of space filling curve-based indexing within the squid p2p data discovery system, 2004.
• 7: Bernard Wong , Ymir Vigfússon , Emin Gün Sirer, Hyperspaces for object clustering and approximate matching in peer-to-peer overlays, Proceedings of the 11th USENIX workshop on Hot topics in operating systems, p.1-6, May 07-09, 2007, San Diego, CA