In the most paper[1], kNN authentication is partitioned into two parts:
- use the traditional incremental kNN find algorithm ( best first search) to find the kth point (data).
- use a circle with the query point as its center and the distance between the kth point and the query point as the radius to create a traditional range query
- use the mature range query authentication method to construct the verification objects by which the client can reconstruct the root hash value.
However, we want an algorithm that can both compute the results of kNN and construct the verification objects during the traverse of MR-tree. Normally the best first search will destroy the order of the sub-trees and nodes so that it will incur that the verification process will be difficult to reconstruct the root hash value.
In range query authentication, we process the depth first search to the MR-tree to see whether the internal node is intersect with the query range. The whole structure can be written recursively. And the object in VO is in recursive pattern. The objects in the same sub-tree are put between the two '[' and ']' bracket.
(MBR Value, HashValue)=RootHash(VerObj VO) //Client
1. Set str=∅ and MBR=NULL
2. While VO still has entries
3. Get next entry eV from VO
4. If eV is a data object P
5. If P overlaps the query, Add P to the result set
6. Enlarge MBR to include P
7. str = str | P
8. If eV is a pair of MBR/digest (MBR_c, H_c)
9. Enlarge MBR to include MBR_c
10. str = str | MBR_c | H_c
11. If eV is [
12. (MBR_c, H_c) = RootHash(VO)
13. Enlarge MBR to include MBR_c
14. str = str | MBR_c | H_c
15. If eV is ], Return (MBR, hash(str))
The RootHash algorithm merges all of the objects between the brackets and recursively compute the internal node's MBR and hash value.
Method in top-k query authentication[2]
Algorithm 1: kSKQ Processing and VO Generation over MIR-tree
Input: A kSKQ request, MIR-tree
Output: The result set and VO
1 Put each entry Ri in the root into a priority queue and initialize VO with (1)
‘[’; (2) each Ri and H(Ri); (3)the inverted file associated with the root; (4) ‘]’;
2 while k objects have not been found do
3 Pick the entry with the smallest ranking score from the priority queue;
4 if the picked entry is an MBR Ri then
5 Put each Rj (or Oj) in Ri’s child node into the priority queue again;
6 Replace Ri and H(Ri) with (1) ‘[’; (2) each Rj and H(Rj) (or Oj) in Ri’s child node;
(3) the inverted file associated with Ri’s child node; (4) ‘]’ in VO;
7 else
8 //the picked entry is an object Oi
9 Put Oi into the result set;
10 Return the result set and VO;
As in kNN, the extra documents(inverted file) are not in the record. The VO only contains MBR and hash value. The core thinking is similar to the range query. In range query, the internal node needs to expand its sub-trees while it intersects with the query range. In kNN query, we replace the intersection process with the nearest process. We find the nearest nodes or data points by using the function: minimumDistance. And replace the nearest node with its corresponding sub-tree nodes in the VO list. There is only one problem is that in the implementing process, the VO list must contains both the String '[' ']' objects and the MR-tree node objects.
We need to transform all of the node objects into its corresponding String objects for the client's verification.
The sample JAVA implementation of kNN query with construction of VO is below:
public void securenearestNeighborQuery(int k, final IShape query,HashMap<String, String> hashnode,HashMap<String, String> hashdata,LinkedList VO)
{
if (query.getDimension() != m_dimension) throw new IllegalArgumentException("nearestNeighborQuery: Shape has the wrong number of dimensions.");
Node n = readNode(m_rootID);
//add the root entry with nearest distance
VO.add(new NNEntry(n,0.0));
int minindex = 0;
int counter = 0;
double knearest = 0.0;
while(counter<k) {
double min = 9999999;
//first find the nearest distance and index
NNEntry t = null;
for(int i=0;i<VO.size();i++) {
Object item = VO.get(i);
if(!(item instanceof String))
{
t = (NNEntry)item;
double mindis = t.m_minDist;
if(mindis < min) {
min = mindis;
minindex = i;
}
}
}
//t is the closest entry
t = (NNEntry)VO.get(minindex);
if(t.m_pEntry instanceof Node) {
VO.remove(minindex);
n = (Node)t.m_pEntry;
VO.add(minindex,"[");
//expand the children of t and add them to the linkedlist VO
for (int cChild = 0; cChild < n.m_children; cChild++) {
IEntry e;
if(n.m_level != 0)
{
e = readNode(n.m_pIdentifier[cChild]);
}
else
{
e = new Data(n.m_pData[cChild], n.m_pMBR[cChild], n.m_pIdentifier[cChild]);
}
NNEntry e2 = new NNEntry(e,query.getMinimumDistance(e.getShape()));
VO.add(minindex+cChild+1,e2);
}
VO.add(minindex+n.m_children+1,"]");
}
//the entry is a point not a node!
else {
t.m_minDist = 10000000;
Data d = (Data)t.m_pEntry;
System.out.println(d.getIdentifier());
counter++;
knearest = t.m_minDist;
}
}
//transform all of the non-string entry to String format in VO
for(int it=0;it<VO.size();it++) {
Object item = VO.get(it);
if(item instanceof NNEntry)
{
VO.remove(it);
NNEntry entry = (NNEntry)item;
if(entry.m_pEntry instanceof Node) {
Node node = (Node)entry.m_pEntry;
VO.add(it,"("+node.getShape().toString()+hashnode.get(""+node.m_identifier)+")");//non expanded internal node
}
else {
Data data = (Data)entry.m_pEntry;
VO.add(it,data.getShape().toString());//data points in expanded node
}
}
}
}
[1] Authenticated indexing for outsourced spatial databases
[2] Authentication of Top-k Spatial Keyword Queries in Outsourced Databases
