Part 3:
III. SYSTEM MODEL AND THE INDEX TREES A. PRODUCT RETRIEVAL SYSTEM 
As shown in Fig. 1, the entire product retrieval system model is composed primarily of three entities: the data manager, the cloud server and the data user. The primary responsibili ties of these three entities are presented in the following. 
The data manager is responsible for managing the product and collecting the product information. In addition, the data manager needs to encrypt the product information file by a symmetric encryption technique before outsourcing the data to the cloud server. To improve the security of the files, each file is encrypted by a single secret key, and the keys of different files are independent. Furthermore, to improve the search efficiency, an index structure is constructed for the outsourced data. At first, an identifier index structure is constructed based on the hash function and height-balanced binary search tree. Then, a feature vector tree is built for all the feature vectors of the product, and it is encrypted by the secure kNN algorithm. 
When a data user wants to search a set of chosen products, she needs to generate a trapdoor to describe her interest. Two types of the trapdoor can be provided, i.e., a set of 
FIGURE 1. Encrypted product information retrieval system model. 
hash values of the desired product information files or a set of feature vectors. For the first type of trapdoor, a set of encrypted files with the same hash identifiers are returned, and for the second type trapdoor, the most relevant encrypted files are returned. The data user can obtain the plaintext files by decrypting the returned files with the help of the symmetric secret keys. These secret keys are provided by the data manager. 
The cloud server stores all the data uploaded by the data manager. When a data user needs to search the data in the cloud, she first generates a trapdoor, which is sent to the cloud server. A search engineer is employed by the cloud server to act as a bridge between the data users and the encrypted data. Though the cloud server cannot get the plaintexts of the data, it should be capable of sending the accurate search result of the trapdoor to the data users. Of course, the returned data are ciphertext, and the data user needs to decrypt them by the symmetric secret keys which are provided by the data manager. 

B. ID-AVL TREE 
To construct the ID-AVL tree, we first encrypt all the product identifiers based on a hash function, hash(). Next, each node in the ID-AVL tree contains a hash value of the product ID, and all of the hash values are organized based on an AVL tree [31] as shown in Fig. 2. Two important properties of AVL, which can help us to maintain the hash values, are presented as follows. First, the ID-AVL tree can be updated flexibly by inserting a node, deleting a node and modifying a node. Correspondingly, we can update the ID-AVL tree from time to time by changing the product information. Second, the values of the left child nodes of a parent node are always smaller than that of the parent node; the values of the right child nodes of a parent node are always larger than that of the parent node. In theory, the time complexity of inserting, deleting and searching a node are all log(N), where N is the number of nodes in the tree. In this paper, we construct the ID-AVL tree based on the algorithm in [31]. 
FIGURE 2. Product hash value index tree
C. PRODUCT RETRIEVAL TREE
The feature dictionary of the products is denoted as D ={f1, f2, · · · , fm}, and the feature set Si of any product Pi must be a subset of D, i.e., Si ∈ 2^{f1,f2,··· ,fm}. Then, the feature vector Vi of product Pi is constructed as follows.
• The initial vector of Pi is a 1 × m vector, and all the elements in the vector are 0;
• We orderly scan all the elements in the initial vector and assign a value to the element of feature fi if the feature of Pi can be quantized.
• Based on the different degrees of importance of the features, a weight is employed to multiply the elements in the vector to reflect this.
To search the product information, a trapdoor needs to be constructed by the data user in a similar way, and the similarities between the trapdoor VQ and the product feature Vi is calculated as sim (Vi, VQ)= Vi·VQ. Moreover, the similarity
between two the vectors Vi and Vj is defined as sim (Vi,Vj)=Vi· Vj. Next, the product feature vectors are organized as hierarchical clusters according to their similarities. Each node in the tree represents a cluster composed of a set of product feature vectors or sub-clusters. The PRF vector of a node is a
quintuple summarization about a cluster.
Given K m-dimensional product feature vectors in a cluster:{Vj} where j = 1, 2, · · · ,K, the PRF vector of the cluster is denoted as a quintuple: PRF = (K, LS, SS, Vmin, Vmax ),
where K is the number of product feature vectors in the cluster, LS is the linear sum of the K product feature vectors, i.e., LS =PKj=1 Vj, SS is the square sum of the K product
feature vectors, i.e., SS =PKj=1 Vj (SS is a numerical value rather than a vector), Vmin denotes a vector consisting of m values which are calculated as follows:Vmin [i] = min(V1 [i] , V2[i], · · · , VK [i]), (1) where Vj[i] is the i-th dimensional value of Vj, and similarly, Vmax is calculated as follows: Vmax [i] = max(V1 [i] , V2[i], · · · , VK [i]). (2)
Based on a PRF vector, the centroid of a cluster C can be easily calculated as c = LS/K, (3)
FIGURE 3. Product retrieval feature tree
and the relevance score between cluster C and a product vector Vjis defined as 
RScore(C, Vj) = c · Vj. (4) 
Similarly, the relevance score between cluster C and a query vector VQ is defined as 
RScore(C, VQ) = c · VQ. (5) 
Further, the radius of cluster C is defined as follows:
R =sXK j=1 (Vj − c)^2 / K, (6)
and it can be calculated by the PRF vector as follows:
R =r (SS − LS^2 / K) / K. (7)
Theorem 1 (PRF Additivity Theorem): If we merge two disjoint clusters with PRF vectors: PRF1 = (K1, LS1, SS1, Vmin1, Vmax1) and PRF2 = (K2, LS2, SS2, Vmin2, V max2 ), then the PRF vector of the combined cluster is PRF = PRF1 + PRF2 = (K1 + K2, LS1 + LS2, SS1 + SS2, Vmin, Vmax ), (8)
where Vmin [i] = min (Vmin1 [i] , Vmin2 [i]) and Vmax [i] = max(Vmax1 [i] , Vmax2 [i]). 
Proof: The proof consists of straightforward algebra. 
In the similar way, we can obtain the PRF Subtraction Theorem, which can be used to divide two clusters, though Vmin and Vmax need to be recalculated. The structure of a PRF tree is presented in Fig. 3. It can be observed that each leaf node is composed of a set of similar product vectors and its PRF vector is directly extracted from the product vectors. The similar leaf nodes agglomerate with each other to compose the non-leaf nodes until all the product vectors belong to a huge cluster at the a root node. Based on Theorem 1, the PRF vectors of the non-leaf nodes and the root node are calculated based on the PRF vectors of all their child nodes.
파트 3:III. 시스템 모델 및 인덱스 트리 A. 상품 검색 시스템 그림 1에서 볼 수 있듯이 전체 상품 검색 시스템 모델은 크게 데이터 관리자, 클라우드 서버, 데이터 사용자라는 세 개의 엔티티로 구성됩니다. 이 세 개체의 주요 책임 관계는 다음과 같습니다. 데이터 관리자는 제품을 관리하고 제품 정보를 수집할 책임이 있습니다. 또한 데이터 관리자는 클라우드 서버에 데이터를 아웃소싱하기 전에 대칭 암호화 기법으로 제품 정보 파일을 암호화해야 합니다. 파일 보안을 강화하기 위해 각 파일은 하나의 비밀 키로 암호화되며, 서로 다른 파일의 키는 독립적입니다. 또한 검색 효율을 높이기 위해 아웃소싱된 데이터에 대한 인덱스 구조를 구성합니다. 먼저 해시 함수와 높이 균형 이진 검색 트리를 기반으로 식별자 인덱스 구조를 구성합니다. 그런 다음 상품의 모든 특징 벡터에 대해 특징 벡터 트리를 구축하고, 보안이 강화된 kNN 알고리즘으로 암호화합니다. 데이터 사용자가 선택한 제품 세트를 검색하려면 관심 분야를 설명하기 위해 트랩도어를 생성해야 합니다. 트랩도어는 두 가지 유형이 제공될 수 있습니다. 그림 1. 암호화된 상품 정보 검색 시스템 모델. 원하는 제품 정보 파일의 해시값 또는 특징 벡터 집합입니다. 첫 번째 유형의 트랩도어의 경우 동일한 해시 식별자를 가진 암호화된 파일 집합이 반환되고, 두 번째 유형의 트랩도어의 경우 가장 관련성이 높은 암호화된 파일이 반환됩니다. 데이터 사용자는 대칭 비밀 키를 사용하여 반환된 파일의 암호를 해독하여 일반 텍스트 파일을 얻을 수 있습니다. 이러한 비밀 키는 데이터 관리자가 제공합니다. 클라우드 서버는 데이터 관리자가 업로드한 모든 데이터를 저장합니다. 데이터 사용자가 클라우드에서 데이터를 검색해야 하는 경우, 먼저 트랩도어를 생성하여 클라우드 서버로 전송합니다. 클라우드 서버는 검색 엔지니어를 고용하여 데이터 사용자와 암호화된 데이터 사이의 가교 역할을 합니다. 클라우드 서버는 데이터의 평문을 얻을 수는 없지만 트랩도어의 정확한 검색 결과를 데이터 사용자에게 전송할 수 있어야 합니다. 물론 반환된 데이터는 암호문이며, 데이터 사용자는 데이터 관리자가 제공한 대칭 비밀 키로 암호를 해독해야 합니다. B. ID-AVL 트리 ID-AVL 트리를 구성하기 위해 먼저 해시 함수 해시()를 기반으로 모든 상품 식별자를 암호화합니다. 다음으로, ID-AVL 트리의 각 노드에는 상품 ID의 해시값이 포함되며, 모든 해시값은 그림 2와 같이 AVL 트리[31]를 기반으로 구성됩니다. 해시값을 유지하는 데 도움이 되는 AVL의 두 가지 중요한 속성은 다음과 같습니다. 첫째, 노드 삽입, 노드 삭제, 노드 수정을 통해 ID-AVL 트리를 유연하게 업데이트할 수 있습니다. 이에 따라 상품 정보를 변경하여 ID-AVL 트리를 수시로 업데이트할 수 있습니다. 둘째, 부모 노드의 왼쪽 자식 노드의 값은 항상 부모 노드의 값보다 작고, 부모 노드의 오른쪽 자식 노드의 값은 항상 부모 노드의 값보다 큽니다. 이론적으로 노드 삽입, 삭제, 검색의 시간 복잡도는 모두 로그(N)이며, 여기서 N은 트리의 노드 수입니다. 본 논문에서는 [31]의 알고리즘을 기반으로 ID-AVL 트리를 구성합니다. 그림 2. 제품 해시값 인덱스 트리C. 상품 검색 트리곱의 특징 사전은 D ={f1, f2, - - - , fm}으로 표시되며, 모든 곱 Pi의 특징 집합 Si는 D의 부분 집합, 즉 Si ∈ 2^{f1,f2,--- ,fm}이어야 합니다. 그러면 곱 Pi의 특징 벡터 Vi는 다음과 같이 구성됩니다.- Pi의 초기 벡터는 1 × m 벡터이며 벡터의 모든 요소는 0입니다;- 초기 벡터의 모든 요소를 순서대로 스캔하고 Pi의 특징을 양자화할 수 있는 경우 특징 fi의 요소에 값을 할당합니다.- 특징의 중요도에 따라 가중치를 적용하여 벡터의 요소에 가중치를 곱하여 이를 반영합니다.상품 정보를 검색하기 위해서는 데이터 사용자가 비슷한 방식으로 트랩도어를 구성해야 하며, 트랩도어 VQ와 상품 특징 Vi 간의 유사도는 sim (Vi, VQ)= Vi-VQ로 계산됩니다. 또한, 두 벡터 Vi와 VQ 사이의 유사성는 심(Vi,Vj)=Vi-Vj로 정의됩니다. 다음으로, 제품 특징 벡터는 유사도에 따라 계층적 클러스터로 구성됩니다. 트리의 각 노드는 제품 특징 벡터 집합 또는 하위 클러스터로 구성된 클러스터를 나타냅니다. 노드의 PRF 벡터는 노드에 대한클러스터에 대한 5중 요약입니다.클러스터에 K개의 m차원 제품 특징 벡터가 주어졌을 때:{Vj}에서 j = 1, 2, - - - ,K인 경우 클러스터의 PRF 벡터는 5중으로 표시됩니다: PRF = (K, LS, SS, Vmin, Vmax ),여기서 K는 클러스터의 제품 특징 벡터 수이고, LS는 K 제품 특징 벡터의 선형 합(즉, LS =PKj=1 Vj)이며, SS는 제곱입니다.