NDLI: Distributed Pattern Matching for P2P Systems

Content Provider	IEEE Xplore Digital Library
Author	Ahmed, R. Boutaba, R.
Copyright Year	2006
Description	Author affiliation: Sch. of Comput. Sci., Waterloo Univ., Ont. (Ahmed, R.; Boutaba, R.)
Abstract	Flexibility and efficiency are the prime requirements for any P2P search mechanism. Existing P2P systems do not seem to provide satisfactory solution for achieving these two conflicting goals. Unstructured search protocols (as adopted in Gnutella and FastTrack), provide search flexibility but exhibit poor performance characteristics. Structured search techniques (mostly distributed hash table (DHT)-based), on the other hand, can efficiently route queries to target peers but support exact-match queries only. In this paper we present a novel P2P system, called distributed pattern matching system (DPMS), for enabling flexible and efficient search. Distributed pattern matching can be used to solve problems like wildcard searching (for file-sharing P2P systems), partial service description matching (for service discovery systems) etc. DPMS uses a hierarchy of indexing peers for disseminating advertised patterns. Patterns are aggregated and replicated at each level along the hierarchy. Replication improves availability and resilience to peer failure, and aggregation reduces storage overhead. An advertised pattern can be discovered using any subset of its 1-bits; this allows inexact matching and queries in conjunctive normal form. Search complexity (i.e., the number of peers to be probed) in DPMS is O (log N + zetalog N/log N), where N is the total number of peers and zeta is proportional to the number of matches, required in a search result. The impact of churn problem is less severe in DPMS than DHT-based systems. Moreover, DPMS provides guarantee on search completeness for moderately stable networks. We demonstrate the effectiveness of DPMS using mathematical analysis and simulation results
Starting Page	198
Ending Page	208
File Size	1094310
Page Count	11
File Format	PDF
ISBN	1424401429
ISSN	15421201
DOI	10.1109/NOMS.2006.1687551
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2006-04-03
Publisher Place	Canada
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Pattern matching Computer science Peer to peer computing Telephony Mathematical analysis Analytical models Fingerprint recognition Protocols Indexing Resilience
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Distributed Indexing for Resource Discovery in P2P Networks

Modeling Heterogeneous User Churn and Local Resilience of Unstructured P2P Networks

Distributed pattern matching: a key to flexible and efficient P2P search

A hierarchical resource locating and routing for SIP-based telephony systems

A Comparative Simulation Analysis of P2P System Architectures

Evaluating Large Scale Distributed Simulation of P2P Networks

PeerfactSim.KOM: A simulation framework for Peer-to-Peer systems

Strategy Optimization for P2P Security Using BloomFilter

Dynamic P2P Indexing and Search Based on Compact Clustering

Distributed Pattern Matching for P2P Systems

Similar Documents

Distributed Indexing for Resource Discovery in P2P Networks

Modeling Heterogeneous User Churn and Local Resilience of Unstructured P2P Networks

Distributed pattern matching: a key to flexible and efficient P2P search

A hierarchical resource locating and routing for SIP-based telephony systems

A Comparative Simulation Analysis of P2P System Architectures

Evaluating Large Scale Distributed Simulation of P2P Networks

PeerfactSim.KOM: A simulation framework for Peer-to-Peer systems

Strategy Optimization for P2P Security Using BloomFilter

Dynamic P2P Indexing and Search Based on Compact Clustering

Distributed Pattern Matching for P2P Systems