Re: Nearest Neighbour / Ternary Search Tree
- From: "David J Mark" <nntp45534-22@xxxxxxxxxxxx>
- Date: Tue, 10 Jan 2006 11:41:32 GMT
<maryjones11289@xxxxxxxxxxx> wrote in message
news:1136777727.945175.152250@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
> Hi All,
>
> I'm trying to write/find code that creates a Ternary Search Tree in
> Visual Basic (VB6 or .NET).
>
> Here's my situation:
> What I have is an array consisting of 60,000 string elements.
> All elements are exactly 225 characters in length.
> All elements are made up of 1's and 0's
>
> Eg:
>
> 1001101001.....
> 1110111000.....
> 1101101011.....
> Etc
>
>
> What I'm trying to do:
> My aim is to take an arbitrary search key (225 chars in length,
> consisting of 1's and 0's) and find all elements in the array where
> the hamming distance between the search key and the element is 22 or
> less (ie 90% similar).
As mentioned, strings should not be used to store binary data.
>
> I could do a brute-force search, but this takes quite some time and is
> clearly not optimum.
>
> I have spent the last 3 or so months searching the Internet researching
> on the best way to solve this nearest neighbour problem. To date I have
> not found anything written in VB. I have found numerous documents that
> outline several algorithms, but they have been written in such a way
> that I'd need a PHD in something just to understand them.
>
> The latest documentation I have found all indicate that Ternary Search
> Trees are the way to go and that implementing a NN search function is
> easy with them. The problem is that I cannot find any information on
> how to construct the tree. I did find one example written in C, but
> with my limited knowledge of C, I was unable to translate into VB.
The thing is that VB is really lousy for this kind of solution. It has no
intrinsic data structures to accomodate a tree search. You really should
wrap this in a DLL (written in C++) and call it from VB. Or if you want to
use .net, somebody wrote a TTS dictionary object:
http://www.codeproject.com/csharp/tst.asp
I don't recommend this as it turns the problem into a search for partial
string matches. This is an odd solution for binary data.
>
> So now I'm here asking for your assistance please. Can anyone show me
> (VB code if possible) how to construct a Ternary Tree as well as the NN
> search function or alternatively, point me in the direction of a site
> that could help.
>
> Thanks in advance,
>
> Mary.
>
.
- References:
- Nearest Neighbour / Ternary Search Tree
- From: maryjones11289
- Nearest Neighbour / Ternary Search Tree
- Prev by Date: Need Help with DLL Variable Access
- Next by Date: Re: Form_Activate not fired when program run as Scheduled Task
- Previous by thread: Re: Nearest Neighbour / Ternary Search Tree
- Next by thread: Re: Nearest Neighbour / Ternary Search Tree
- Index(es):
Relevant Pages
|
