Algorithms

 In this section, we discuss the algorithms devised for manipulation of the proposed access structure. The insertion algorithm is a crucial one, as it determines the shape of the structure and hence the efficiency of other algorithms. When a node overflows, it invokes the decision metric algorithm and chooses the most suitable expansion method. Each type of expansion is handled by a separate self contained procedure. These procedures are recursive. It is possible to have a lateral expansion during a longitudinal expansion or seed another lateral expansion during a lateral expansion.

We devise algorithms for three types of queries: exact match, range query and k-nearest neighbor queries. These are the basic queries encountered in spatial data retrieval. Other types of queries are easily deduced from them.


Algorithm insertion.


Given a structure whose root node T, insert new object O into corresponding leaf bucket.

I1: [Search object]. Invoke Exact_match_query() to search whether the object exists and to locate the corresponding leaf bucket to insert new object.

I2: [Object exists]. If object found, stop.

I3: [Insert new object]. If leaf bucket is not full, insert new object. Otherwise, if overflow bucket is not full, insert object in overflow bucket.

I4: [Expansion occurs]. If longitudinal expansion is possible, invoke longitudinal_expand(). Otherwise invoke lateral_expand() to expand the tree and insert new object.

Algorithm longitudinal_expand.


Expand child buckets of b_parent into a new set of buckets and insert the new object, O.

LG1: [Create new buckets]. Create a new set of buckets to accommodate existing objects and new object.

LG2: [Reinsert objects]. For all the child buckets b_child of b_parent; if b_child is a leaf bucket, compute new hash function for each object in b_child.
If corresponding new bucket has room to accommodate it,
insert object
otherwise, invoke lateral_expand() for corresponding new bucket.

LG3: [Recursively insert branches]. If b_child is a non-leaf bucket, invoke reinsert_objects().

LG4: [Insert new object]. Compute new mapping function for new object, O and insert it in corresponding new bucket.

LG5: [Dispose old buckets]. Dispose all child buckets of b_parent and their branches.

LG6: [Attach new buckets]. update b_parent, to attach new buckets to the structure.

Algorithm lateral_expand.


Expand an overfilled bucket b_old into a new set of buckets and insert the new object, O.

LT1: [Create new buckets]. Create a new set of buckets to accommodate existing objects and new object.

LT2: [Reinsert objects]. For all the objects in bucket b_old, compute new hash function and insert in the corresponding new bucket.

LT3: [Insert new object]. Compute new mapping function for new object O. If corresponding bucket has enough space to accommodate it, insert, otherwise invoke lateral_expand() for corresponding new bucket.

LT4: [Attach new buckets]. Update b_old to attach new buckets to the structure.

Algorithm reinsert_objects.


Reinsert objects in child buckets of b_i by recursively traversing the branches.

RE1: [Recursive call]. For all the child buckets b_j of b_i, if b_j is not a leaf bucket, invoke Reinsert_objects().

RE2: [Reinsert objects]. If b_j is a leaf bucket, for all the objects in b_j, compute new mapping function.
If corresponding new bucket has enough space to accommodate
insert it
otherwise, invoke lateral_expand() for the corresponding new bucket.

Algorithm exact_match_query.


Given a structure whose root node is T, search whether a given object Q exists.

EQ1: [Search subtrees]. If T is not a leaf bucket, traverse the tree downwards, computing subsequent mapping functions found in branches until a leaf bucket is encountered.

EQ2: [Search leaf bucket]. If leaf bucket is encountered, search objects to check whether query object Q already exists and return the result accordingly.

Algorithm range_query.


Given a structure whose root node is T, search for all the objects intersecting with query rectangle $q\_rect$.

RQ1: [Search subtrees]. If T is not a leaf bucket, for all the child buckets of T which intersects with query rectangle $q\_rect$, b_child, invoke search_range().

RQ2: [Search leaf bucket]. If leaf bucket encountered, output all the qualifying objects.

Algorithm search_range.


Given a query rectangle $q\_rect$, search for qualifying objects by traversing the branches of b_i, recursively.

SR1: [Recursive call]. If b_i is not a leaf bucket, for all the intersecting branches b_j of b_i, invoke search_range().

SR2: [Search leaf bucket]. If b_i is a leaf bucket, output all the qualifying objects.

Algorithm k_nearest_neighbor_query.


Given a query object Q, find k nearest neighbor objects in the structure rooted at T.

KN1: [Traverse downwards]. If T is not a leaf bucket, traverse the tree downwards, computing subsequent hash functions found in branches, until a leaf bucket is encountered. Store the bucket addresses visited in traversal in the list visited.

KN2: [Search leaf bucket]. If leaf bucket is encountered, and if it is not empty, find k most closest objects to Q (or if less objects exists, all of them) and store them in the list $k\_NN$.

KN3: [Traverse upwards]. Traverse the tree upwards, until root encountered, by retrieving bucket addresses in list, visited. For each bucket in list, visited; for all their child buckets, b_child, invoke search_neighbor(), if
1. b_child is not visited
AND EITHER
2. MAXDIST(b_child, Q ) < farthest nearest neighbor
OR
3. Not enough nearest neighbors (k objects) not found so far.

KN4: [Return result]. Return the list $k\_NN$.

Algorithm search_neighbor.


Given a query object Q, an unvisited bucket b_i and a list of nearest neighbors $k\_NN$, find more suitable candidate objects for k-nearest neighbors, by traversing the branches of unvisited buckets, recursively.

SN1: [Recursively traverse downwards]. If b_i is not a leaf bucket, for all the child buckets b_child of b_i, invoke search_neighbor(), if
1. MAXDIST(b_child, Q ) < farthest nearest neighbor
OR
2. Not enough nearest neighbors (k objects) not found so far. )

SN2: [Update $k\_NN$]. If leaf bucket encountered, update list of nearest neighbors, $k\_NN$, comparing objects in the leaf bucket with the farthest nearest neighbor found so far.