Searching Large Indexes on Tiny Devices

Guy Shani et al., Microsoft Research

Summary

This paper proposes a novel technique for searching large indexes on devices with limited UI (5 keys and one line display). It employs a distribution based OBST (Optimal BST) extended to an OTST (Optimal Ternary Search Tree) using pinning. With shrinking mobile media devices, UI options become increasingly limited and a technique to allow user entry faster with lesser keystrokes is desirable.

Details

OBST relying on probability distribution of search strings would be faster than lexicographic BSTs. Authors extend this structure to an OTST by adding pinning. So while up and down keys traverse OTST in conventional sense to left and right subtree, and left key retraces route taken, right key traverses OTST to middle subtree which is a subtree with an extra character ‘pinned’ in the prefix string shared amongst all the child nodes. Authors argue that with prefixes often shared amongst artist and album names adding this new subtree enhances the search experience. Authors present quantitative comparison showing OTST to be the best technique amongst various other techniques. ROTST (Restricted OTST) represents a design choice based on user feedback where the middle subtree retains previous root as one of the options (even though users can simply end the search by pressing ‘enter’).

User study shows lowest keystroke count and search times for ternary searches although spelling bases searches had lowest error rate because of being a well familiar concept. This tone was also reflected in user comments where though they preferred ternary searches, they recommended spelling based searches for an average user. Ternary searches register an improvement over binary searches in average time for single keystroke as users need to focus only on the working prefix string.

Review

Perhaps this paper represents the classic struggle between the ‘best thing to do’ and ‘simplest thing to do’. While OTST and ROTST ranked highest in the quantitative study, user preference for average user lied squarely with spelling based linear search. In the words of author, a key question that remains unanswered is what an average user thinks about this technique. Authors admit that their results might be skewed by their sample space which consisted entirely of Microsoft employees. Having said that, the technique is very innovative and consolidates existing search techniques in a neat manner.

Disclaimer

The work discussed above is an original work presented at IUI 2009 by the authors/affiliations indicated at the starting of this post. This post in itself was created as part of course requirement of CPSC 436.