Monday, October 3, 2011
THE COQUOS APPROACH TO CONTINUOUS QUERIES IN UNSTRUCTURED OVERLAYS
THE COQUOS APPROACH TO CONTINUOUS QUERIES IN UNSTRUCTURED OVERLAYS
ABSTRACT:
The current peer-to-peer (P2P) content distribution systems are constricted by their simple on-demand content discovery mechanism. The utility of these systems can be greatly enhanced by incorporating two capabilities, namely a mechanism through which peers can register their long term interests with the network so that they can be continuously notified of new data items, and a means for the peers to advertise their contents. Although researchers have proposed a few unstructured overlay-based publish-subscribe systems that provide the above capabilities, most of these systems require intricate indexing and routing schemes, which not only make them highly complex but also render the overlay network less flexible toward transient peers. This paper argues that for many P2P applications, implementing full-fledged publish-subscribe systems is an overkill. For these applications, we study the alternate continuous query paradigm, which is a best-effort service providing the above two capabilities. We present a scalable and effective middleware, called CoQUOS, for supporting continuous queries in unstructured overlay networks. Besides being independent of the overlay topology, CoQUOS preserves the simplicity and flexibility of the unstructured P2P network. Our design of the CoQUOS system is characterized by two novel techniques, namely cluster-resilient random walk algorithm for propagating the queries to various regions of the network and dynamic probability-based query registration scheme to ensure that the registrations are well distributed in the overlay. Further, we also develop effective and efficient schemes for providing resilience to the churn of the P2P network and for ensuring a fair distribution of the notification load among the peers. This paper studies the properties of our algorithms through theoretical analysis. We also report series of experiments evaluating the effectiveness and the costs of the proposed schemes.
System Architecture:
Existing System:
Despite their popularity, most of the current unstructured P2P content distribution systems suffer from certain serious limitations. One such limitation is their simple, on demand mechanism for content discovery. Peers in these systems discover data items by circulating queries within the overlay network. A peer receiving a query responds back to the initiating node if it has any matching content. Upon processing a query, the recipient node removes it from its local buffers1. Thus, a query expires after it completes its circulation within the network. In other words, the network forgets the queries once they have completed their circulation. For clarity purposes, we call this the ad hoc query model, and we refer to the queries as ad hoc queries.
Disadvantages:
1. One such limitation is their simple, on demand mechanism for content discovery.
2. However, this approach is unviable. Besides heavy messaging overheads, this scheme could overwhelm the peers with unwanted advertisements.
3. The ad hoc query model suffers from two main shortcomings. First, an ad hoc query is only capable of searching and retrieving content that exists in the P2P network at the time the query was issued.
Proposed System:
We Propose,
We focus on an alternate notification paradigm called the continuous query model. Similar to content-based pub-sub systems this model provides a mechanism through which peers can register their queries, which are maintained in the network for extended durations of time. However, in contrast to traditional pub-sub model, a system implementing the continuous query model provides a best-effort notification service for the registered queries informing their initiating nodes of new content that may have been added in the recent past.
. Peers in these systems discover data items by circulating queries within the overlay network. A peer receiving a query responds back to the initiating node if it has any matching content. Upon processing a query, the recipient node removes it from its local buffers1. Thus, a query expires after it completes its circulation within the network. In other words, the network forgets the queries once they have completed their circulation. For clarity purposes, we call this the ad hoc query model, and we refer to the queries as ad hoc queries.
Advantages:
1. First, we present a novel query propagation technique called Cluster Resilient Random Walk (CRW). This technique retains the overall framework of the random walk paradigm. However, at each step of propagation, CRW favors neighbors that are more likely to send messages deeper into the network thereby enabling the continuous queries to reach different topological regions of the overlay network.
2. Second, a dynamic probability scheme is proposed for enabling the recipients of a continuous query to make independent decisions on whether to register the query. In this scheme, a query that has not been registered in the past several hops has a higher chance of getting registered in its next hop, which ensures that registrations are well distributed along the path of a query message.
3. Third, we discuss a passive replication-based scheme for preserving high notification effectiveness of the system even when the underlying P2P network experiences significant churn.
Module Description:
- Cluster Resilient Random Walk
- Dynamic Probability Scheme
- Passive Replication
- Overlay Churn
Cluster Resilient Random Walk:
Random walk corresponds to a depth first traversal of the network, and a message propagated through random walks has a higher probability of reaching remote regions of the network than its flooding-based counterpart. In this paper we use the terms random walk and pure random walk (PRW) interchangeably.
The above property of the random walk makes it an attractive paradigm for propagating continuous queries. Unfortunately, the random walk protocol suffers from one significant drawback that undermines its utility for propagating queries in the CoQUOS system.
we have designed a novel query dissemination scheme called cluster resilient random walk (CRW). This scheme is motivated by a crucial observation: Two peers belonging to the same cluster generally have large numbers of common neighbors.
Dynamic Probability Scheme:
The CRW scheme provides a mechanism for propagating a continuous query. But, how does a node receiving this message decide whether to register the query? A straightforward solution would be to register a query at every node it visits. However, this would result in large numbers of unnecessary subscriptions, which affects the efficiency of the network.
The reason is that for some continuous queries a long series of peers in the path of the query message may all decide not to register the query, whereas another sequence of consecutive nodes may all decide to host the query. The announcements originated near the dry patches of a query's path might fail to reach any of its beacon nodes, thus leading to low success rates. Considering these requirements, we have designed a novel dynamic probability-based technique (DP scheme, for short) for peers to decide whether to register a continuous query. However, the registration probability of a query varies as the query traverses along its route. The central idea of the dynamic probability scheme can be summarized as follows:
The probability of registering a query at a peer node would be high if the query has not been registered at the nodes it visited in the recent past. In contrast, if the query has been registered at a node that visited in the past few hops, the probability of it getting registered at the
Current peer would be low.
Passive Replication:
We discuss a passive replication-based scheme for preserving high notification effectiveness of the system even when the underlying P2P network experiences significant churn.
This churn of the overlay network can adversely impact the success of continuous queries and announcements. When a node Pi gracefully leaves the system, it asks one of its neighbors to handle all registered queries at Pi and also notifies all the beacon nodes with queries issued by Pi to remove the queries. However, when Pi exits the system unexpectedly, all the registrations are lost and the notification success rates of the respective queries and the matching announcements drop. Thus, effective mechanisms are needed to alleviate the negative effects of churn in the overlay network.
Overlay Churn:
In order to counter the adverse effects of network churn, we have designed a low-cost technique wherein the query registrations present on a peer are replicated on one or more of its neighbors. Failures are detected through periodic exchange of heartbeat messages between the beacon node and the peers maintaining its replicas. The beacon node that does not respond to two consecutive messages is assumed to have failed. In the interest of better load distribution, two or more neighbors may takeover subsets of the queries registered at the failed node. The communication costs of maintaining query replicas are optimized through lazy replication and piggybacking the information they utilize. They only require interactions between neighboring peers, thus making them suitable for generic unstructured P2P networks. In both schemes, neighboring peers periodically (at the end of pre-specified cycles) exchange information about their loads. Based on the load information obtained from its neighbors, a peer decides whether it is overloaded.
System Configuration:-
H/W System Configuration:-
Processor - Pentium –III
Speed - 1.1 Ghz
RAM - 256 MB(min)
Hard Disk - 20 GB
Floppy Drive - 1.44 MB
Key Board - Standard Windows Keyboard
Mouse - Two or Three Button Mouse
Monitor - SVGA
S/W System Configuration:-
v Operating System :Windows95/98/2000/XP
v Application Server : Tomcat5.0/6.X
v Front End : HTML, Java, Jsp, jquery
v Scripts : JavaScript.
v Server side Script : Java Server Pages.
v Database : Mysql
v Database Connectivity : JDBC.
SKETCH4MATCH – CONTENT-BASED IMAGE RETRIEVAL SYSTEM USING SKETCHES
SKETCH4MATCH – CONTENT-BASED IMAGE RETRIEVAL
SYSTEM USING SKETCHES
ABSTRACT:
The content based image retrieval (CBIR) is one of the most popular, rising research areas of the digital image processing. Most of the available image search tools, such as Google Images and Yahoo! Image search, are based on textual annotation of images. In these tools, images are manually annotated with keywords and then retrieved using text-based search methods. The performances of these systems are not satisfactory. The goal of CBIR is to extract visual content of an image automatically, like color, texture, or shape. This paper aims to introduce the problems and challenges concerned with the design and the creation of CBIR systems, which is based on a free hand sketch (Sketch based image retrieval – SBIR). With the help of the existing methods, describe a possible solution how to design and implement a task specific descriptor, which can handle the informational gap between a sketch and a colored image, making an opportunity for the efficient search hereby. The used descriptor is constructed after such special sequence of preprocessing steps that the transformed full color image and the sketch can be compared. We have studied EHD, HOG and SIFT. Experimental results on two sample databases showed good results. Overall, the results show that the sketch based system allows users an intuitive access to search-tools. The SBIR technology can be used in several applications such as digital libraries, crime prevention, and photo sharing sites. Such a system has great value in apprehending suspects and identifying victims in forensics and law enforcement. A possible application is matching a forensic sketch to a gallery of mug shot images. The area of retrieve images based on the visual content of the query picture intensified recently, which demands on the quite wide methodology spectrum on the area of the image processing.
EXISTING SYSTEM:
In earlier days, image retrieving from large image database can be done by following ways. We will discuss briefly about the image retrieving of various steps
Ø Automatic Image Annotation and Retrieval using Cross Media Relevance Models
Ø Concept Based Query Expansion
Ø Query System Bridging The Semantic Gap For Large Image Databases
Ø Ontology-Based Query Expansion Widget for information Retrieval
Ø Detecting image purpose in World-Wide Web documents
PROPOSED SYSTEM:
Relevance feedback is an interactive process that starts with normal CBIR. The user input a query, and then the system extracts the image feature and measure the distance with images in the database. An initial retrieval list is then generated.
User can choose the relevant image to further refine the query, and this process can be iterated many times until the user find the desired images.
ALGORITHM USED:
The k-means algorithm:
Algorithm: k-means. The k-means algorithm for partitioning based on the mean value of the objects in the cluster.
Input: The number of clusters k and a database containing n objects.
Output: A set of k clusters that minimizes the squared-error criterion.
Method:
(1) arbitrarily choose k objects as the initial cluster centers:
(2) repeat
(3) (re)assign each object to the cluster to which the object is the most similar, based on the mean value of the objects in the cluster;
(4) Update the cluster means, i.e., calculate the mean value of the objects for each cluster;
(5) Until no change.
HARDWARE REQUIREMENTS:
• System : Pentium IV 2.4 GHz.
• Hard Disk : 40 GB.
• Floppy Drive : 1.44 Mb.
• Monitor : 15 VGA Colour.
• Mouse : Logitech.
• Ram : 256 Mb.
SOFTWARE REQUIREMENTS:
• Operating system : - Windows XP Professional.
• Coding Language : - Java.
• Tool Used : - Eclipse.
REFERENCE:
B.Szanto, P. Pozsegovics, Z.Vamossy, Sz.Sergyan, “Sketch4Match – Content Based Image Retrieval System Using Sketches”, SAMI 2011, 9th IEEE International Symposium on Applied Machine Intelligence and Informatics, IEEE January 2011.
SECURE AND PRACTICAL OUTSOURCING OF LINEAR PROGRAMMING IN CLOUD COMPUTING
SECURE AND PRACTICAL OUTSOURCING OF LINEAR
PROGRAMMING IN CLOUD COMPUTING
Abstract:
Cloud Computing has great potential of providing robust computational power to the society at reduced cost. It enables customers with limited computational resources to outsource their large computation workloads to the cloud, and economically enjoy the massive computational power, bandwidth, storage, and even appropriate software that can be shared in a pay-per-use manner. Despite the tremendous benefits, security is the primary obstacle that prevents the wide adoption of this promising computing model, especially for customers when their confidential data are consumed and produced during the computation.
On the one hand, the outsourced computation workloads often contain sensitive information, such as the business financial records, proprietary research data, or personally identifiable health information etc. To combat against unauthorized information leakage, sensitive data have to be encrypted before outsourcing so as to provide end to- end data confidentiality assurance in the cloud and beyond. However, ordinary data encryption techniques in essence prevent cloud from performing any meaningful operation of the underlying plaintext data, making the computation over encrypted data a very hard problem. On the other hand, the operational details inside the cloud are not transparent enough to customers. As a result, there do exist various motivations for cloud server to behave unfaithfully and to return incorrect results, i.e., they may behave beyond the classical semi honest model.
Existing System:
Despite the tremendous benefits, outsourcing computation to the commercial public cloud is also depriving customers’ direct control over the systems that consume and produce their data during the computation, which inevitably brings in new security concerns and challenges towards this promising computing model. On the one hand, the outsourced computation workloads often contain sensitive information, such as the business financial records, proprietary research data, or personally identifiable health information etc.
To combat against unauthorized information leakage, sensitive data have to be encrypted before outsourcing. so as to provide end to- end data confidentiality assurance in the cloud and beyond. However, ordinary data encryption techniques in essence prevent cloud from performing any meaningful operation of the underlying plaintext data, making the computation over encrypted data a very hard problem. On the other hand, the operational details inside the cloud are not transparent enough to customers. As a result, there do exist various motivations for cloud server to behave unfaithfully and to return incorrect results, i.e., they may behave beyond the classical semi hones model. For example, for the computations that require a large amount of computing resources, there are huge financial incentives for the cloud to be “lazy” if the customers cannot tell the correctness of the output. Besides, possible software bugs, hardware failures, or even outsider attacks might also affect the quality of the computed results.
Thus, we argue that the cloud is intrinsically not secure from the viewpoint of customers. Without providing a mechanism for secure computation outsourcing, i.e., to protect the sensitive input and output information of the workloads and to validate the integrity of the computation result, it would be hard to expect cloud customers to turn over control of their workloads from local machines to cloud solely based on its economic savings and resource flexibility. For practical consideration, such a design should further ensure that customers perform less amount of operations following the mechanism than completing the computations by themselves directly. Otherwise, there is no point for customers to seek help from cloud. Recent researches in both the cryptography and the theoretical computer science communities have made steady advances in “secure outsourcing expensive computations”
Proposed System:
On the one hand, the outsourced computation workloads often contain sensitive information, such as the business financial records, proprietary research data, or personally identifiable health information etc. To combat against unauthorized information leakage, sensitive data have to be encrypted before outsourcing so as to provide end to- end data confidentiality assurance in the cloud and beyond. However, ordinary data encryption techniques in essence prevent cloud from performing any meaningful operation of the underlying plaintext data, making the computation over encrypted data a very hard problem. On the other hand, the operational details inside the cloud are not transparent enough to customers. As a result, there do exist various motivations for cloud server to behave unfaithfully and to return incorrect results, i.e., they may behave beyond the classical semi honest model.
Fully homomorphic encryption (FHE) scheme, a general result of secure computation outsourcing has been shown viable in theory, where the computation is represented by an encrypted combinational Boolean circuit that allows to be evaluated with encrypted private inputs.
Module Description:
1. Mechanism Design Framework
2. Basic Techniques
3. Enhanced Techniques via Affine Mapping
4. Result Verification
Mechanism Design Framework:
We propose to apply problem transformation for mechanism design. The general framework is adopted from a generic approach, while our instantiation is completely different and novel. In this framework, the process on cloud server can be represented by algorithm ProofGen and the process on customer can be organized into three algorithms (KeyGen, ProbEnc, ResultDec). These four algorithms are summarized below and will be instantiated later.
• KeyGen(1k) → {K}. This is a randomized key generation algorithm which takes a system security parameter k, and returns a secret key K that is used later by customer to encrypt the target LP problem.
• ProbEnc(K,_) → {_K}. This algorithm encrypts the input tuple _ into _K with the secret key K. According to problem transformation, the encrypted input _K has the same form as _, and thus defines the problem to be solved in the cloud.
• ProofGen(_K) → {(y, )}. This algorithm augments a generic solver that solves the problem _K to produce both the output y and a proof . The output y later
decrypts to x, and is used later by the customer to verify the correctness of y or x.
• ResultDec(K,_, y, ) → {x,⊥}. This algorithm may choose to verify either y or x via the proof . In any case, a correct output x is produced by decrypting y using the secret K. The algorithm outputs ⊥ when the validation fails, indicating the cloud server was not performing the computation faithfully.
Basic Techniques
Before presenting the details of our proposed mechanism, we study in this subsection a few basic techniques and show that the input encryption based on these techniques along may result in an unsatisfactory mechanism. However, the analysis will give insights on how a stronger mechanism should be designed. Note that to simplify the presentation, we assume that the cloud server honestly performs the computation, and defer the discussion on soundness to a later section.
1) Hiding equality constraints (A, b): First of all, a randomly generated m × m non-singular matrix Q can be part of the secret key K. The customer can apply the matrix to Eq. (2) for the following constraints transformation, Ax = b ⇒ A′x = b′
where A′ = QA and b′ = Qb.
Enhanced Techniques via Affine Mapping
To enhance the security strength of LP outsourcing, we must be able to change the feasible region of original LP and at the same time hide output vector x during the problem input encryption. We propose to encrypt the feasible region of _ by applying an affine mapping on the decision variables x. This design principle is based on the following observation: ideally, if we can arbitrarily transform the feasible area of problem _ from one vector space to another and keep the mapping
function as the secret key, there is no way for cloud server to learn the original feasible area information. Further, such a linear mapping also serves the important purpose of output hiding.
Result Verification
Till now, we have been assuming the server is honestly performing the computation, while being interested learning information of original LP problem. However, such semihonest model is not strong enough to capture the adversary behaviors in the real world. In many cases, especially when the computation on the cloud requires a huge amount of computing resources, there exists strong financial incentives for the cloud server to be “lazy”. They might either be not willing to commit service-level-agreed computing resources to save cost, or even be malicious just to sabotage any following up computation at the customers. Since the cloud server promises to solve the LP problem _K = (A′,B′, b′, c′), we propose to solve the result verification problem by designing a method to verify the correctness of the solution y of _K. The soundness condition would be a corollary thereafter when we present the whole mechanism in the next section. Note that
in our design, the workload required for customers on the result verification is substantially cheaper than solving the LP problem on their own, which ensures the great computation savings for secure LP outsourcing.
The LP problem does not necessarily have an optimal solution. There are three cases as follows.
• Normal: There is an optimal solution with finite objective value.
• Infeasible: The constraints cannot be all satisfied at the same time.
• Unbounded: For the standard form in Eq. (1), the objective function can be arbitrarily small while the constraints are all satisfied.
System Architecture:
Algorithm Used:
KeyGen(1k) → {K}.
This is a randomized key generation algorithm which takes a system security parameter k, and returns a secret key K that is used later by customer to encrypt the target LP problem.
ProbEnc(K,_) → {_K}.
This algorithm encrypts the input tuple _ into _K with the secret key K. According to problem transformation, the encrypted input _K has the same form as _, and thus defines the problem to be solved in the cloud.
ProofGen(_K) → {(y, )}.
This algorithm augments a generic solver that solves the problem _K to produce
both the output y and a proof . The output y later decrypts to x, and is used later by the customer to verify the correctness of y or x.
ResultDec(K,_, y, ) → {x,⊥}.
This algorithm may choose to verify either y or x via the proof . In any case, a correct output x is produced by decrypting y using the secret K. The algorithm outputs ⊥ when the validation fails, indicating the cloud server was not performing the computation faithfully.
System Specification:
Hardware System Requirement
Processor - Pentium –III
Speed - 1.1 Ghz
RAM - 256 MB(min)
Hard Disk - 20 GB
Floppy Drive - 1.44 MB
Key Board - Standard Windows Keyboard
Mouse - Two or Three Button Mouse
Monitor - SVGA
S/W System Requirement
v Operating System : Windows 95/98/2000/NT4.0.
v Application Server : Tomcat6.0
v Front End : HTML, Java.
v Scripts : JavaScript.
v Server side Script : Java Server Pages.
v Database : Mysql.
v Database Connectivity : JDBC.
Subscribe to:
Posts (Atom)