Bioinformatics.org


Research

Online databases
Online analysis tools
Online education tools

Development


Forums

News & Commentary
Jobs Forum (Career Center)


News & Commentary  Message forums




Software: Accelerating the neighborjoining algorithm using the adaptive bucket data structure
Submitted by Dr. Leonid Zaslavsky; posted on Tuesday, May 27, 2008

ABSTRACT
The complexity of the neighbor joining method is determined by the complexity of the search for an optimal pair ("neighbors to join") performed globally at each iteration. Accelerating the neighborjoining method requires performing a smarter search for an optimal pair of neighbors, avoiding reevaluation of all possible pairs of points at each iteration. We developed an acceleration technique for the neighborjoining method that significantly decreases complexity for important applications without any change in the neighborjoining method. This technique utilizes the bucket data structure. The pairs of nodes are arranged in buckets according to values of the goal function delta(ij) = u(i) + u(j)  d(ij). Buckets are adaptively rearranged after each neighborjoining step. While the pairs of nodes in the top bucket are reevaluated at every iteration, pairs in lower buckets are accessed more rarely, when the algorithm determines that the elements of the bucket need to be reevaluated based on new values of delta(ij). As a result, only a small portion of candidate pairs of nodes is examined at each iteration. The algorithm is cache efficient, since the bucket data structures are able to exploit locality and adjust to cache properties.


Expanded view  Monitor forum  Save place
Start a new thread:
You have to be to post a reply.

