A search feature that filters records in real time as you type would probably be a good idea to include. Another would be the possibility to sort the records.
Since there may be a lot of records, the best choice in this case is probably to have a separate area which displays what you have already chosen, so that the user won't have to scroll around the selection areas to find what they already have.
I think that what you have mocked up is a pretty good way to do it. When you think about the tags-to-posts relationship on a blog (or on SO even), that is many-to-many and it is usually implemented very similarly: for one post, you search for (or, since they are simple strings, directly enter) as many tags as you want to associate with it. I can't really think of any many-to-many relationships I encounter often, although I know there are probably many...
I'd suggest not having to click add more to be able to search. The warning at the right is nice, but IMHO it should only say the search displays results as the user types.
Sorting a column (maybe along with the search) would also be a nice functionality. I'd suggesting it being done by clicking on the header of the table, with some icon indicating whether the sort is ascending or descending.
I'd suggest also the search to do an approximate string matching in case there are no or few results. It is so annoying not being able to find something you don't remember exactly.
Finally, for testing the first impression (though not the functionality itself), I'd suggest uploading it to the 5 second test and see what you get.
Hi, It's an interesting and fairly common UI problem, how to efficiently select items. I'm assuming that you are intending on having the user first select a single item and that the mechanism you are interested is how to choose other items that get related to this first single item.
There ares various select methods. From a usability standpoint, it would be preferable to just have ONE method used for each scenario. Then when the user sees it, they will know what to do.
various selection techniques:
You've said that you'll have thousands of possible choices, so that eliminates 1 and 5. Really, thousands will eliminate all of them, as the usability doesn't scale well with more than a few hundred in the list.
If you can count on the user to filter the list, like in your example, then 6 may be suitable. If you think of how Facebook picture tagging works, I think that it fairly efficient for long lists: background: Facebook picture tagging is a mechanism that allows you to assign one or more people to portions of an image - ie 'tag' them.
When you select an image to tag (ie the 'single item') and wish to relate other items(people) to it, A dialog box pops up. It contains the top 6 or so names that you've used in the past, and a textbox where you can start to type the person's name you wish to use. As you type, the list dynamically changes to reduce the number of people to only those who contain the letter sequence you've typed. This works very well for large lists, but it does rely on the user typing to filter. It also will rely on use of scripting to intelligently reduce the list based on the user's input.
For your application it would rely on the user performing this step once for each association, as I'm assuming that the other items won't all have similar names!
Here's an image of the Facebook tagging application: http://screencast.com/t/9MPlpJQJzBQ
There are a number of important questions to consider - how many records will typically be used (as opposed to available for association)? Will there be a large number of records on one side of the association (given the switch from 1->M, this seems likely)?
If one of the quantities of records is usually very small (<10, I'd say), call this the LHS (because it usually is), then the best way to associate may be to allow searches for LHS and RHS items, then drag-and-drop them onto a list - LHS items onto the list proper; RHS items into the existing LHS items. That way, it's intuitive to specify a relation between to items. You could also add other options like "associate with all", or a grouping pen so you can assign several records to several other records - nothing is tedious like having to do 15 drags-and-drops of the same record.
In fact, I think that's the most crucial bit of any M->M UI design - minimize repetition. Doing the same thing over for 100s of records (remember that if "nobody will ever...", they will) is unfun, especially if it's complex. I know this seems to contradict my earlier advice, but I don't think it does - design for the typical use case, but make sure that the atypical ones do not make the program unusable.