Request basic data request

Question

What is the secret of pulling up items that match the characters entered in the search bar that respond instantly? For example, if I type the letter “W” in the search bar, all phrases containing the letter “W” at any position of the character within the phrase are returned immediately.

So, if the database of 20,000 phrases contains 500 phrases with the letter "W", they will appear as soon as the user types the first character. Then, when additional characters are typed, the list will automatically decrease.

I can send a query to the SQL server from the iPhone and get this type of response, however, no matter what we try to use other offers, we still cannot get a good response time when storing the database locally on the iPhone.

I know that this performance is available because there are many other applications that display results immediately after entering text.

Please note that this is not the same as indexing all the words in each phrase, as this will only result in matches when the word begins with the character entered. In this case, we are looking for characters in words.

Answer 1

I think asynchronous filtering of results is the answer. Instead of updating the search results each time the user enters a new character, put the db query in the background stream when entering the first character. If a new character is entered before the query is completed, cancel the old query and start a new one. Finally, you get to the point where the user stops typing long enough for the request to return. Thus, the request itself never blocks user input.

I believe that the UISearchDisplayController class offers this type of asynchronous search, although whether you want to use this class or just accept an asynchronous design pattern from it is up to you.

Answer 2

If you want to leave the database for this, you can use a generalized suffix tree with all the conditions in your phrases. You can build a suffix tree in linear time and, I suppose, use it to quickly find all occurrences of a substring. There are many pages on the Internet about suffix trees and suffix arrays. Wikipedia is probably a good place to start.

Answer 3

I have a funny circuit for you. You can create an index of characters existing in each phrase through a 32-bit integer. Flip bits [0-25] to represent the case-insensitive az characters that exist in the phrase. Create a second query string bitmap. You can now perform comparisons using bitwise operations (& and |) to determine matches. It is very fast and believe that SQLite actually supports bitwise operations in queries, so you can even use this scheme to go directly to the database. I have working code that makes this embedded in one of our iPhone apps - Alphagram.