This problem seems to be a Searching problem. One possible approach could be to use BST(Binary Search Tree) to store the element and its key together as a node and this BST should be keyed on the attribute which you are going to use as 'Key' to search elements. As we know the drawback of BST i.e., search could be O(n) in worst- case, as an improvement you may use some advanced structure like Red- Black Tree, B+ tree, Treaps, etc. to maintain the balance of the elements of your dynamic set so that search time is guaranteed to O(lg n).
On Feb 16, 11:15 am, parkurm <[email protected]> wrote: > In delicious.com, users are able to bookmark website links with > various meaningful tags, such as for a link titled "Sorting Algorithm > Animations", one can tag it as "algorithm", "sort", and later (maybe > after months) find this previously tagged bookmark by searching either > "sort" or "algorithm". It greatly improves our way of keeping and > organizing knowledge. > > Also in delicious.com, when you search for a tag, say "algorithm", it > is able to show all the associated tags to "algorithm". For example, > the user has several bookmarks, and they are tagged as following: > > Link1: algorithm sort > Link2: algorithm heap stack > Link3: algorithm heap fantastic > Link4: database architecture > > Then, the associated tags to "algorithm" will be "sort", "heap“, > ”stack", "fantastic" (all tags that showed up together with > "algorithm" in bookmarks). > > Further, we can also find associated tags to multiple tags. For > example, when I search "algorithm" and "heap", the associated tags to > these words will be "stack" and "fantastic". > > So, associated tags are tags that showed up together in some bookmarks > with the given tags. > > The problem is how to implement this associated tag searching. > > The naive way will be first searching all the links that have the > given tags (when I search for "algorithm" and "heap", it will return > Link2 and Link3), then by looking through all the returned links, I > get the tags that are associated to "algorithm" and "heap". > > This naive way surely works, but it's very time inefficient. > > Also, we cannot use indexing of tags. Say there're 3 links, each with > 2 tags: > > L1: t1, t2 > L2: t1, t3 > L3: t2, t3 > > Then, if I search for associated tags to both "t1, t2", I'll get > result as "t3", since t3 is indexed by both t1 in L2, and indexed by > t2 in L3. But in fact there's no link that contains all t1,t2 and t3, > so according to definition t3 should not appear in the result of > associated tags. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
