DistOS-2011W Distributed Data Structures: a survey - Revision history

AbdelRahman at 09:24, 5 March 2011

2011-03-05T09:24:22Z

← Older revision		Revision as of 09:24, 5 March 2011
Line 157:		Line 157:

	*<i>k</i> > 1 <i>segments</i> are to be produced. The <i>i</i>-th segment <math>s_i</math> consists from <i>c</i> and from all the bits <math>s'_i</math>:		*<i>k</i> > 1 <i>segments</i> are to be produced. The <i>i</i>-th segment <math>s_i</math> consists from <i>c</i> and from all the bits <math>s'_i</math>:
	<math>s'_i = b_i b_{k+i} b_{2k+i}...</math>		<math>s'_i = b_i . b_{k+i} . b_{2k+i}...</math>
	*The <i>parity segment</i> <math>S_{k+1}</math> is to be produced that also contains <i>c</i> and the parity bits <math>S'_{k+1}</math>. An example for the even parity would be:		*The <i>parity segment</i> <math>S_{k+1}</math> is to be produced that also contains <i>c</i> and the parity bits <math>S'_{k+1}</math>. An example for the even parity would be:
	<math>s'_{k+1} = b'_{1} b'_{2} ... b'_{m}</math>		<math>s'_{k+1} = b'_{1} . b'_{2} ... b'_{m}</math>
	where bit <math>b'_{j}</math> is the parity bit for the string with the <i>j</i>-th bit of each segment; 1<math>\leq</math>j<math>\leq</math> <i>k</i>. If some segments <i>s</i> in <i>R</i> failed to be read, the parity segment allows to reconstruct <i>s</i>.		where bit <math>b'_{j}</math> is the parity bit for the string with the <i>j</i>-th bit of each segment; 1<math>\leq</math>j<math>\leq</math> <i>k</i>. If some segments <i>s</i> in <i>R</i> failed to be read, the parity segment allows to reconstruct <i>s</i>.

AbdelRahman at 09:12, 5 March 2011

2011-03-05T09:12:46Z

← Older revision		Revision as of 09:12, 5 March 2011
Line 131:		Line 131:

	==SDDS using Record Grouping==		==SDDS using Record Grouping==
	High availability can be achieved through record grouping <ref name="ref22">W. Litwin and T. Risch, “Lh*g: a high-availability scalable distributed data structure by record grouping,” Knowledge and Data Engineering, IEEE Transactions on, vol. 14, no. 4, pp. 923 –927, Jul. 2002.</ref>. A group can be defined as a logical structure of up to <i>k</i> records, such that <i>k</i> is a file parameter. The authors in <ref name="ref22" />. proposed such model in which their simulations showed its efficiency and scalability.		High availability can be achieved through record grouping <ref name="ref22">W. Litwin and T. Risch, “Lh*g: a high-availability scalable distributed data structure by record grouping,” Knowledge and Data Engineering, IEEE Transactions on, vol. 14, no. 4, pp. 923 –927, Jul. 2002.</ref>. A group can be defined as a logical structure of up to <i>k</i> records, such that <i>k</i> is a file parameter. The authors in <ref name="ref22" /> proposed such model in which their simulations showed its efficiency and scalability.

	=Security and Performance Parameters=		=Security and Performance Parameters=

AbdelRahman at 09:07, 5 March 2011

2011-03-05T09:07:42Z

← Older revision		Revision as of 09:07, 5 March 2011
Line 110:		Line 110:

	==Distributed Dynamic Hashing (DDH)==		==Distributed Dynamic Hashing (DDH)==
	Methods of handling overflows in static hashing increased the retrieval time as files approach their space limits. Dynamic hashing structures have been proposed to eliminate such problems <ref>R. J. Enbody and H. C. Du, “Dynamic hashing schemes,” ACM Comput. Surv., vol. 20, pp. 850–113, July 1988. [Online]. Available: http://doi.acm.org/10.1145/46157.330532</ref>. A distributed approach for dynamic hashing has been proposed and tested. It inherits the idea of dynamic hashing algorithms and apply it to distributed systems <ref name="ref18">R. Devine, “Design and implementation of ddh: A distributed dynamic hashing algorithm,” in Foundations of Data Organization and Algorithms, ser. Lecture Notes in Computer Science, D. Lomet, Ed. Springer Berlin / Heidelberg, 1993, vol. 730, pp. 101–114, 10.1007/3-540-57301-1 7. [Online]. Available: http://dx.doi.org/10.1007/3-540-57301-1 7 </ref>. Its main idea is to spread data across several servers using a new autonomous location discovery technique that replaces the use of a centralized directory for location buckets with eventual learning of bucket locations. It depends on a server splitting mechanism under certain circumstances, where each server decides when to split. Each ~~servers~~ retains the following information about each bucket: the bucket number, its split level and the bucket contents <ref name="ref18" />. In addition, each server stores a directory containing information about other server's buckets. When a server receives a request regarding a data item from a client, it checks if it is the correct recipient of the message. This is done by comparing the data item's key to the range of keys of its buckets. If the server finds out that it is not the intended one, it simply forwards the message to the correct recipient. Obviously, one of the problems of this design is that it requires each server to keep track of all other servers for correct message forwarding. Consequently, the server responds to the client with a reply indicating the success status of the operation, which allows the client to update its local perception of the hash table.		Methods of handling overflows in static hashing increased the retrieval time as files approach their space limits. Dynamic hashing structures have been proposed to eliminate such problems <ref>R. J. Enbody and H. C. Du, “Dynamic hashing schemes,” ACM Comput. Surv., vol. 20, pp. 850–113, July 1988. [Online]. Available: http://doi.acm.org/10.1145/46157.330532</ref>. A distributed approach for dynamic hashing has been proposed and tested. It inherits the idea of dynamic hashing algorithms and apply it to distributed systems <ref name="ref18">R. Devine, “Design and implementation of ddh: A distributed dynamic hashing algorithm,” in Foundations of Data Organization and Algorithms, ser. Lecture Notes in Computer Science, D. Lomet, Ed. Springer Berlin / Heidelberg, 1993, vol. 730, pp. 101–114, 10.1007/3-540-57301-1 7. [Online]. Available: http://dx.doi.org/10.1007/3-540-57301-1 7 </ref>. Its main idea is to spread data across several servers using a new autonomous location discovery technique that replaces the use of a centralized directory for location buckets with eventual learning of bucket locations. It depends on a server splitting mechanism under certain circumstances, where each server decides when to split. Each server retains the following information about each bucket: the bucket number, its split level and the bucket contents <ref name="ref18" />. In addition, each server stores a directory containing information about other server's buckets. When a server receives a request regarding a data item from a client, it checks if it is the correct recipient of the message. This is done by comparing the data item's key to the range of keys of its buckets. If the server finds out that it is not the intended one, it simply forwards the message to the correct recipient. Obviously, one of the problems of this design is that it requires each server to keep track of all other servers for correct message forwarding. Consequently, the server responds to the client with a reply indicating the success status of the operation, which allows the client to update its local perception of the hash table.

	In a test that used 50,000 records, almost 200,000 network messages were required to insert and then retrieve all records <ref name="ref18" />. The vast number of messages is deemed the bottleneck of this design. It is clear that the less latency that will be applied by the network, the better the model will perform.		In a test that used 50,000 records, almost 200,000 network messages were required to insert and then retrieve all records <ref name="ref18" />. The vast number of messages is deemed the bottleneck of this design. It is clear that the less latency that will be applied by the network, the better the model will perform.

AbdelRahman at 09:03, 5 March 2011

2011-03-05T09:03:21Z

← Older revision		Revision as of 09:03, 5 March 2011
Line 93:		Line 93:
	}		}
	</pre>		</pre>
			This model reduced the read query to O(Log(Log(N))) and the update query to constant complexity <ref name="habashy" />.

	==Task Queue==		==Task Queue==

AbdelRahman at 09:00, 5 March 2011

2011-03-05T09:00:52Z

← Older revision		Revision as of 09:00, 5 March 2011
Line 65:		Line 65:
	Balancing is preserved via rotations during a bottom-up height adjusting traversal. In SD-Rtrees particularly, balancing exploits the fact that the rectangle containment relationship allows for more freedom for reorganizing an unbalanced tree.		Balancing is preserved via rotations during a bottom-up height adjusting traversal. In SD-Rtrees particularly, balancing exploits the fact that the rectangle containment relationship allows for more freedom for reorganizing an unbalanced tree.

	The authors in <ref name="ref11" />. claim that SD-Rtrees constitute scalable, compact and efficient structure that make use of the processing and storage space of a pool of distributed data servers and that they are particularly important in clusters of servers.		The authors in <ref name="ref11" /> claim that SD-Rtrees constitute scalable, compact and efficient structure that make use of the processing and storage space of a pool of distributed data servers and that they are particularly important in clusters of servers.

	==Binary Indexed Trees (BITs)==		==Binary Indexed Trees (BITs)==

AbdelRahman at 08:56, 5 March 2011

2011-03-05T08:56:04Z

← Older revision		Revision as of 08:56, 5 March 2011
Line 47:		Line 47:
	[[File:Fig2_Sojan1_Abdo.png\|300px\|thumb\|right\|Fig. 2. The bottom up recursive algorithm <ref name="ref6" />]]		[[File:Fig2_Sojan1_Abdo.png\|300px\|thumb\|right\|Fig. 2. The bottom up recursive algorithm <ref name="ref6" />]]

	Upon the implementation of a distributed version of octrees, two challenges arise. The first is how to disseminate the octree nodes between processors while retaining good load balancing and locality. The second is how to decrease the cost of remote node accessing for higher efficiency <ref name="~~ref5~~" />. It can be argued that an octree needs to be partitioned across processors to allow equal number of inter-particle interactions in order to achieve good load balancing <ref name="ref4" />. Besides, it is highly preferable that tree distribution among processors occurs such that each processor gets a complete subtree(s). This will help in preserving locality. Obviously, this approach can guarantee minimum number of remote accesses for the computation entirety <ref name="~~ref5~~" />.		Upon the implementation of a distributed version of octrees, two challenges arise. The first is how to disseminate the octree nodes between processors while retaining good load balancing and locality. The second is how to decrease the cost of remote node accessing for higher efficiency <ref name="ref4" />. It can be argued that an octree needs to be partitioned across processors to allow equal number of inter-particle interactions in order to achieve good load balancing <ref name="ref4" />. Besides, it is highly preferable that tree distribution among processors occurs such that each processor gets a complete subtree(s). This will help in preserving locality. Obviously, this approach can guarantee minimum number of remote accesses for the computation entirety <ref name="ref4" />.

	==Distributed Search Trees (DST)==		==Distributed Search Trees (DST)==

AbdelRahman at 08:50, 5 March 2011

2011-03-05T08:50:14Z

← Older revision		Revision as of 08:50, 5 March 2011
Line 14:		Line 14:

	=Introduction=		=Introduction=
	Multicomputers are collections of autonomous workstations or PCs on a network (network multicomputers), or of share-nothing processors with local storage linked through a high-speed network or bus (switched multicomputer)<ref> A. S. Tanenbaum, Distributed Operating Systems. Prentice Hall, 1995.</ref>. Recent advances in multicomputers showed that they became in need for new data structures that scale well with the number of components to make effective use of their aggregate performance <ref> W. Litwin, R. Moussa, and T. Schwarz, “Lh<sub>RS</sub> —a highly- available scalable distributed data structure,” ACM Trans. Database Syst., vol. 30, pp. 769–811, September 2005. [Online]. Available: http://doi.acm.org/10.1145/1093382.1093386 </ref>. In addition, low latency interconnected mulicomputers allow significant flexibility to the size of data structure without suffering from space utilization or access time penalties <ref>V. Gupta, M. Modi, and A. D. Pimentel, “Performance evaluation of the lhlh scalable, distributed data structure for a cluster of workstations,” in Proceedings of the 2001 ACM symposium on Applied computing, ser. SAC ’01. New York, NY, USA: ACM, 2001, pp. 544–548. [Online]. Available: http://doi.acm.org/10.1145/372202.372458</ref>		Multicomputers are collections of autonomous workstations or PCs on a network (network multicomputers), or of share-nothing processors with local storage linked through a high-speed network or bus (switched multicomputer)<ref> A. S. Tanenbaum, Distributed Operating Systems. Prentice Hall, 1995.</ref>. Recent advances in multicomputers showed that they became in need for new data structures that scale well with the number of components to make effective use of their aggregate performance <ref> W. Litwin, R. Moussa, and T. Schwarz, “Lh<sub>RS</sub> —a highly- available scalable distributed data structure,” ACM Trans. Database Syst., vol. 30, pp. 769–811, September 2005. [Online]. Available: http://doi.acm.org/10.1145/1093382.1093386 </ref>. In addition, low latency interconnected mulicomputers allow significant flexibility to the size of data structure without suffering from space utilization or access time penalties <ref>V. Gupta, M. Modi, and A. D. Pimentel, “Performance evaluation of the lhlh scalable, distributed data structure for a cluster of workstations,” in Proceedings of the 2001 ACM symposium on Applied computing, ser. SAC ’01. New York, NY, USA: ACM, 2001, pp. 544–548. [Online]. Available: http://doi.acm.org/10.1145/372202.372458</ref>.

	The rest of this paper is organized as follows. Section 2 presents the work done to implement a distributed version of classical data structures including trees, sets, lists, graphs and queues, binary indexed trees (BITs) and distributed hash tables (DHT). The described work hide the distinction between local and distributed data structure manipulation, simplifying the programming model at some performance cost. Section 3 focuses on scalability issues in distributed data structure models that are based on linear hashing. Section 4 provides a performance parameters dealing with SDDS research outcomes. Finally, in section 5, a conclusion is drawn summarizing the presented work.		The rest of this paper is organized as follows. Section 2 presents the work done to implement a distributed version of classical data structures including trees, sets, lists, graphs and queues, binary indexed trees (BITs) and distributed hash tables (DHT). The described work hide the distinction between local and distributed data structure manipulation, simplifying the programming model at some performance cost. Section 3 focuses on scalability issues in distributed data structure models that are based on linear hashing. Section 4 provides a performance parameters dealing with SDDS research outcomes. Finally, in section 5, a conclusion is drawn summarizing the presented work.

AbdelRahman at 08:48, 5 March 2011

2011-03-05T08:48:38Z

← Older revision		Revision as of 08:48, 5 March 2011
Line 1:		Line 1:
	(A PDF version of the full document can be found [http://www3.bell.net/abdo57/Distributed%20Data%20Structures,%20a%20survey.pdf here])		(A PDF version of the full document can be found [http://www3.bell.net/abdo57/Distributed%20Data%20Structures,%20a%20survey.pdf here])

	~~<center>BY</center>~~

	<center>A. M. AbdelRahman<br/></center>		<center>A. M. AbdelRahman<br/></center>

AbdelRahman at 08:48, 5 March 2011

2011-03-05T08:48:18Z

← Older revision		Revision as of 08:48, 5 March 2011
Line 1:		Line 1:
	A PDF version of the full document can be found [http://www3.bell.net/abdo57/Distributed%20Data%20Structures,%20a%20survey.pdf here]		(A PDF version of the full document can be found [http://www3.bell.net/abdo57/Distributed%20Data%20Structures,%20a%20survey.pdf here])

	A. M. AbdelRahman<br/>		<center>BY</center>
	PhD Student<br/>
	Dept. of Systems and Computer Engineering<br/>		<center>A. M. AbdelRahman<br/></center>
	Carleton University<br/>		<center>PhD Student<br/></center>
	Ottawa, ON<br/>		<center>Dept. of Systems and Computer Engineering<br/></center>
	Canada K1S 5B6<br/>		<center>Carleton University<br/></center>
	[mailto:amoham16@connect.carleton.ca amoham16@connect.carleton.ca]		<center>Ottawa, ON<br/></center>
			<center>Canada K1S 5B6<br/></center>
			<center>[mailto:amoham16@connect.carleton.ca amoham16@connect.carleton.ca]</center>

AbdelRahman at 08:45, 5 March 2011

2011-03-05T08:45:02Z

← Older revision		Revision as of 08:45, 5 March 2011
Line 103:		Line 103:
	Linear hashing can be applied in a distributed manner <ref name="ref15">W. Litwin, M. A. Neimat, and D. A. Schneider, “Lh: Linear hashing for distributed ﬁles,” SIGMOD Rec., vol. 22, pp. 327–336, June 1993. [Online]. Available: http://doi.acm.org/10.1145/170036.170084</ref>. To do so, each bucket is placed at a different server and retains its bucket level in its header (figure 3).		Linear hashing can be applied in a distributed manner <ref name="ref15">W. Litwin, M. A. Neimat, and D. A. Schneider, “Lh: Linear hashing for distributed ﬁles,” SIGMOD Rec., vol. 22, pp. 327–336, June 1993. [Online]. Available: http://doi.acm.org/10.1145/170036.170084</ref>. To do so, each bucket is placed at a different server and retains its bucket level in its header (figure 3).

	[[File:Fig3.png\|~~200px~~\|thumb\|right\|Fig. 3. Principle of distributing of linear hashing <ref name="ref15" />]]		[[File:Fig3.png\|300px\|thumb\|right\|Fig. 3. Principle of distributing of linear hashing <ref name="ref15" />]]

	Expansion of linear hashing occurs as an LH file. If a bucket <i>n</i> overflows, it splits and bucket <i>n+1</i> is created. The definition of a <i>bucket overflow</i> is beyond the scope of this paper (please refer to <ref name="ref14"/> for a detailed description). In addition, if collision occurs, another splitting occurs for the bucket that suffered collision.		Expansion of linear hashing occurs as an LH file. If a bucket <i>n</i> overflows, it splits and bucket <i>n+1</i> is created. The definition of a <i>bucket overflow</i> is beyond the scope of this paper (please refer to <ref name="ref14"/> for a detailed description). In addition, if collision occurs, another splitting occurs for the bucket that suffered collision.
Line 121:		Line 121:
	A novel method that used Reed Solomon codes for the parity calculus was proposed by Witold Litwin and Thomas Schwarz <ref name="ref20">W. Litwin and T. Schwarz, “Lh*rs: a high-availability scalable distributed data structure using reed solomon codes,” in Proceedings of the 2000 ACM SIGMOD international conference on Management of data, ser. SIGMOD ’00. New York, NY, USA: ACM, 2000, pp. 237–248. [Online]. Available: http://doi.acm.org/10.1145/342009.335418 </ref>. It used the concept of record grouping to provide scalability and high availability. Record grouping is done as follows: a data record is identified by its key <i>c</i> as well as other non-key part. A linear hash function gives the correct bucket <i>a</i> for the data record <i>c</i>. A <i>bucket group</i> is a successively created bucket; they all have the same size (perhaps not the last one). Bucket <i>a</i> belongs to the group numbered <i>g</i> = <math>frac{a}{m}</math> (integer division). Every bucket group is provided with <i>k</i><math>\geq</math>1 parity buckets in which the parity records for the group are stored. Figure 4(a) shows a bucket group containing four data buckets plus their data records and two parity buckets plus their parity records.		A novel method that used Reed Solomon codes for the parity calculus was proposed by Witold Litwin and Thomas Schwarz <ref name="ref20">W. Litwin and T. Schwarz, “Lh*rs: a high-availability scalable distributed data structure using reed solomon codes,” in Proceedings of the 2000 ACM SIGMOD international conference on Management of data, ser. SIGMOD ’00. New York, NY, USA: ACM, 2000, pp. 237–248. [Online]. Available: http://doi.acm.org/10.1145/342009.335418 </ref>. It used the concept of record grouping to provide scalability and high availability. Record grouping is done as follows: a data record is identified by its key <i>c</i> as well as other non-key part. A linear hash function gives the correct bucket <i>a</i> for the data record <i>c</i>. A <i>bucket group</i> is a successively created bucket; they all have the same size (perhaps not the last one). Bucket <i>a</i> belongs to the group numbered <i>g</i> = <math>frac{a}{m}</math> (integer division). Every bucket group is provided with <i>k</i><math>\geq</math>1 parity buckets in which the parity records for the group are stored. Figure 4(a) shows a bucket group containing four data buckets plus their data records and two parity buckets plus their parity records.

	[[File:Fig4.png\|~~200px~~\|thumb\|right\|Fig. 4. Litwin and Schwarz implementation of an LH ﬁle using Reed Solomon codes (a): 2 available bucket group, (b): data and parity records <ref name="ref20" />]]		[[File:Fig4.png\|300px\|thumb\|right\|Fig. 4. Litwin and Schwarz implementation of an LH ﬁle using Reed Solomon codes (a): 2 available bucket group, (b): data and parity records <ref name="ref20" />]]

	Each data record has a <i>rank</i> which resembles its position in its data bucket. A <i>record group</i> contains all the data records having the same rank <i>r</i> within the same bucket group. The <i>k</i> parity buckets include parity records for all record groups. A parity record has a rank <i>r</i> of the record group in the first place, then primary keys of all the data records in the record group, then <i>parity data</i> calculated from the data records and the number of the parity bucket.		Each data record has a <i>rank</i> which resembles its position in its data bucket. A <i>record group</i> contains all the data records having the same rank <i>r</i> within the same bucket group. The <i>k</i> parity buckets include parity records for all record groups. A parity record has a rank <i>r</i> of the record group in the first place, then primary keys of all the data records in the record group, then <i>parity data</i> calculated from the data records and the number of the parity bucket.
Line 144:		Line 144:
	Insightful allocation and access of distributed data can yield substantial performance gain. Arguably, the use of dynamic data management policies can aid the operation of insightful allocation. The authors in <ref name="ref26"> B. Totty and D. Reed, “Dynamic object management for distributed data structures,” in Supercomputing ’92. Proceedings, Nov. 1992, pp. 692 – 701. </ref> proposed a methodology to evaluate the variation of policy performance across algorithms. They defined a set of data management mechanisms, simulated various policies for each of them and analyzed the efficacy of the policies on various parallel scientific benchmarks. A single data management model can lead to great and adequate performance for instruction and uniprocessor data streams respectively. However, on parallel systems, its performance can be very poor. In addition, the interactions of concurrent access techniques are chaotic and dependent to data structure. Access policies alternate messages between nodes of a distributed memory multiprocessor to execute the data management protocol. Four protocols are depicted graphically in figure 5. Figure 5(a) shows the <i>remote</i> policy, which is the simplest policy that initiates a request and a reply message between and accessing node and the one that owns the object data. The other three policies allow constituent object data to dynamically relocate.		Insightful allocation and access of distributed data can yield substantial performance gain. Arguably, the use of dynamic data management policies can aid the operation of insightful allocation. The authors in <ref name="ref26"> B. Totty and D. Reed, “Dynamic object management for distributed data structures,” in Supercomputing ’92. Proceedings, Nov. 1992, pp. 692 – 701. </ref> proposed a methodology to evaluate the variation of policy performance across algorithms. They defined a set of data management mechanisms, simulated various policies for each of them and analyzed the efficacy of the policies on various parallel scientific benchmarks. A single data management model can lead to great and adequate performance for instruction and uniprocessor data streams respectively. However, on parallel systems, its performance can be very poor. In addition, the interactions of concurrent access techniques are chaotic and dependent to data structure. Access policies alternate messages between nodes of a distributed memory multiprocessor to execute the data management protocol. Four protocols are depicted graphically in figure 5. Figure 5(a) shows the <i>remote</i> policy, which is the simplest policy that initiates a request and a reply message between and accessing node and the one that owns the object data. The other three policies allow constituent object data to dynamically relocate.

	[[File:Fig5.png\|~~200px~~\|thumb\|right\|Fig. 5. Data management protocols as depicted by the authors in <ref name="ref26" />]]		[[File:Fig5.png\|400px\|thumb\|right\|Fig. 5. Data management protocols as depicted by the authors in <ref name="ref26" />]]

	The authors (in <ref name="ref26" />) carried experiments that supported the assumption that data structure-specific data management can cause high performance improve over a single policy that is system-imposed. Their experiments also showed that simple yet dynamic policies generate relatively higher memory locality than static placement schemes. Obviously, protocol message count and volume are the payments for such locality increase.		The authors (in <ref name="ref26" />) carried experiments that supported the assumption that data structure-specific data management can cause high performance improve over a single policy that is system-imposed. Their experiments also showed that simple yet dynamic policies generate relatively higher memory locality than static placement schemes. Obviously, protocol message count and volume are the payments for such locality increase.
Line 161:		Line 161:
	where bit <math>b'_{j}</math> is the parity bit for the string with the <i>j</i>-th bit of each segment; 1<math>\leq</math>j<math>\leq</math> <i>k</i>. If some segments <i>s</i> in <i>R</i> failed to be read, the parity segment allows to reconstruct <i>s</i>.		where bit <math>b'_{j}</math> is the parity bit for the string with the <i>j</i>-th bit of each segment; 1<math>\leq</math>j<math>\leq</math> <i>k</i>. If some segments <i>s</i> in <i>R</i> failed to be read, the parity segment allows to reconstruct <i>s</i>.

	[[File:Fig6.png\|~~200px~~\|thumb\|right\|Fig. 6. Securing SDDS as proposed in <ref name="ref26" />. Scattering of a record]]		[[File:Fig6.png\|300px\|thumb\|right\|Fig. 6. Securing SDDS as proposed in <ref name="ref26" />. Scattering of a record]]

	File <math>S_{i}</math> stores all the segments <math>s_i</math>. The address of segment <math>s_i</math> is calculated from its key <i>c</i>, which is considered the same key <i>R</i>.		File <math>S_{i}</math> stores all the segments <math>s_i</math>. The address of segment <math>s_i</math> is calculated from its key <i>c</i>, which is considered the same key <i>R</i>.
Line 171:		Line 171:
	One more security aspect proposal was made by the authors in <ref name="ref29"> T. Schwarz, P. Tsui, and W. Litwin, “An encrypted, content searchable scalable distributed data structure,” in Data Engineering Workshops, 2006. Proceedings. 22nd International Conference on, 2006, p. 18. </ref> for the sake of encrypting the content of an SDDS. Along with the encryption idea, a challenge arises which is how to preserve the capability of parallel search. In <ref name="ref29" />, the authors proposed a scheme that achieves encryption while preserving parallel search capabilities by creating a collection of additional SDDS indices. Those indices are encrypted so that parallel string searches can still be performed at the storage sites. To implement this, a record should consist of a key (acts as a Record Identifier (RI)) and a Record Content Field (RC). The database (which is a collection of records) is stored over multiple sites in strongly encrypted form. The index record can then be generated as follows: an RC is equally chunked such that each chunk is encrypted using Electronic Code Book (ECB) encryption. The ECB encryption can be further strengthened by using lossy compression for removing redundancy. In addition, index records are to be dispersed over multiple sites so as to limit the amount of information available to the attacker at any site. Figure 7 shows this scheme.		One more security aspect proposal was made by the authors in <ref name="ref29"> T. Schwarz, P. Tsui, and W. Litwin, “An encrypted, content searchable scalable distributed data structure,” in Data Engineering Workshops, 2006. Proceedings. 22nd International Conference on, 2006, p. 18. </ref> for the sake of encrypting the content of an SDDS. Along with the encryption idea, a challenge arises which is how to preserve the capability of parallel search. In <ref name="ref29" />, the authors proposed a scheme that achieves encryption while preserving parallel search capabilities by creating a collection of additional SDDS indices. Those indices are encrypted so that parallel string searches can still be performed at the storage sites. To implement this, a record should consist of a key (acts as a Record Identifier (RI)) and a Record Content Field (RC). The database (which is a collection of records) is stored over multiple sites in strongly encrypted form. The index record can then be generated as follows: an RC is equally chunked such that each chunk is encrypted using Electronic Code Book (ECB) encryption. The ECB encryption can be further strengthened by using lossy compression for removing redundancy. In addition, index records are to be dispersed over multiple sites so as to limit the amount of information available to the attacker at any site. Figure 7 shows this scheme.

	[[File:Fig7.png\|~~200px~~\|thumb\|right\|Fig. 7. The scheme of record generation as depicted by the authors in <ref name="ref29" />. Nine different sites store a single record, one (at the top) contains a strongly encrypted form of the record. The other eight are for record indexing; they contain the result of dispersing the chunks of records that are processed and that were generated from two different chunking]]		[[File:Fig7.png\|400px\|thumb\|right\|Fig. 7. The scheme of record generation as depicted by the authors in <ref name="ref29" />. Nine different sites store a single record, one (at the top) contains a strongly encrypted form of the record. The other eight are for record indexing; they contain the result of dispersing the chunks of records that are processed and that were generated from two different chunking]]

	The results of testing this work shown the effectiveness of redundancy removal in allowing the index records to appear as more random. The results roughly showed that a chunk size of 6 ASCII characters plus with dispersing index records into 3 records could result in a relatively secure code.		The results of testing this work shown the effectiveness of redundancy removal in allowing the index records to appear as more random. The results roughly showed that a chunk size of 6 ASCII characters plus with dispersing index records into 3 records could result in a relatively secure code.