5 ms·

Announcing Soulmate, a Redis-backed service for fast autocompleting

97 points by ericwaller 16y ago

dmix 16y ago
The example autocomplete on Seatgeek.com is indeed impressively fast. I might have to use this in my next service.
- ericwaller 16y ago
  Thanks. If you do, definitely let us (SeatGeek) know how it goes.
  - kscaldef 16y ago
    Quick bit of feedback: I thought it was odd that I couldn't type in my city name in conjunction with a band name to pare things down to just the show in my town. Instead, it shows no results.
    - ericwaller 16y ago
      Very good point. I think optimally a really solid autocompleter allows you to bypass search as often as possible, and location awareness is definitely an important part of that.
jarin 16y ago
How ironic, this is perfect for the dating site I'm working on :)
- ericwaller 16y ago
  Glad to hear the name works for someone. We thought it meshed nicely with some of the other hyperbole out there in ruby gem names (god, unicorn, thor, shotgun, etc.).
jbendotnet 16y ago
Nice work.
jedsmith 16y ago
As a UX note, I've always quietly loved autocompletes that aren't just a flat list of terms, but actually contain structured information organized in an intuitive fashion. The design of the suggestions on SeatGeek is fantastic.
- ericwaller 16y ago
  Thanks, very much agreed. I think Spotlight on OSX is probably the first place I saw it done really well. I remember on XP I used to use search all the time, but now on OSX I just autocomplete to what I want probably 95% of the time.
Detrus 16y ago
My first few searches took a while, then every search was pretty fast. Is it the load?
timr 16y ago
Are you really using the technique described in the Redis auto-complete page? Doesn't that method take a lot more RAM than is necessary using a more specialized approach (i.e. a trie)? Also, from what I can tell, every query is log(N) in the size of the completion set, instead of linear in the length of the query/suggestion (again, like a trie). Seems like this might have trouble scaling to large suggestion sets.
- ericwaller 16y ago
  We're actually using a slight variation of the second technique described, which involves maintaining a sorted set of the most relevant results for every possible prefix. A query for a single-prefix term (i.e. "yank") is technically O(log(N)+M), where N is the # of items in the sorted set, and M is the # of items returned. But since in practice we often want a small # of items, we can keep both N and M small. One tradeoff we made is that this approach doesn't support incremental updates easily, you can always add new items, but it would take a good bit of work to remove items that have expired, or update the scores of items that change. As for memory usage, we only store each item once (in a redis hash table), and use the unique ids as entries in the sorted sets. Which sort of approaches a trie, since instead of: ya -> yan -> yank -> yanke -> yankee -> yankees -> [data about yankees] we have: ya -> 101 yan -> 101 ... 101 -> [data about yankees]
  - timr 16y ago
    Yeah, that's what it sounded like. Aside from not supporting incremental updates, that approach has a high memory overhead. For every word of length N, you've got to store 1 + 2 + ... + N-1 + N characters, which is O(N^2). The constant is 1/2, and you do get some savings in shared prefixes, so that's definitely a worst-case upper bound -- but a trie grows with O(N). The O(log(N)) lookup time can also be a limiting factor with large sets. A trie is going to give you worst-case linear lookup time in the length of the longest string in your set. This can be a pretty dramatic difference as string sets get large.
    - Robin_Message 16y ago
ncavig 16y ago
Would be cool to have an example of this running on websockets and get rid of the request/response latency that most autocompletes have. Keep the socket open when the text field is focused and you should be able to cut down the response time even further without that overhead.
- ahrjay 16y ago
  Considering chrome and firefox are switching off websockets until they resolve the security issues that wouldn't be very viable. I guess you could fallback to flash sockets or long polling.
kingkilr 16y ago
The UI on seatgeek is almost identical to what rdio provides, I wonder if rdio is using it.
kin 16y ago
Awesome work guys! I really hope this type of UI becomes more widespread. On a side note, I've always thought the guys over at www.glyde.com execute it quite well.
siculars 16y ago
Oh, oh yes. Thank you kindly. I was literally about to embark on this very feature. Let's take a closer look...
dhruvbird 16y ago
How many phrases of length 30 could you handle with 1GB of RAM? Or do you have numbers on the mean length of a phrase you handle currently, the number of such phrases and how much memory it takes?
henriklied 16y ago
Great stuff! In curious: What do you think about exposing this service via WebSockets? Would that make it even faster?

97 points by ericwaller 16y ago

dmix 16y ago

The example autocomplete on Seatgeek.com is indeed impressively fast. I might have to use this in my next service.

ericwaller 16y ago
Thanks. If you do, definitely let us (SeatGeek) know how it goes.
- kscaldef 16y ago
  Quick bit of feedback: I thought it was odd that I couldn't type in my city name in conjunction with a band name to pare things down to just the show in my town. Instead, it shows no results.
  - ericwaller 16y ago
    Very good point. I think optimally a really solid autocompleter allows you to bypass search as often as possible, and location awareness is definitely an important part of that.

jarin 16y ago

How ironic, this is perfect for the dating site I'm working on :)

ericwaller 16y ago
Glad to hear the name works for someone. We thought it meshed nicely with some of the other hyperbole out there in ruby gem names (god, unicorn, thor, shotgun, etc.).

jbendotnet 16y ago

Nice work.

jedsmith 16y ago

As a UX note, I've always quietly loved autocompletes that aren't just a flat list of terms, but actually contain structured information organized in an intuitive fashion. The design of the suggestions on SeatGeek is fantastic.

ericwaller 16y ago
Thanks, very much agreed. I think Spotlight on OSX is probably the first place I saw it done really well. I remember on XP I used to use search all the time, but now on OSX I just autocomplete to what I want probably 95% of the time.

Detrus 16y ago

My first few searches took a while, then every search was pretty fast. Is it the load?

timr 16y ago

Are you really using the technique described in the Redis auto-complete page? Doesn't that method take a lot more RAM than is necessary using a more specialized approach (i.e. a trie)? Also, from what I can tell, every query is log(N) in the size of the completion set, instead of linear in the length of the query/suggestion (again, like a trie). Seems like this might have trouble scaling to large suggestion sets.

ericwaller 16y ago
We're actually using a slight variation of the second technique described, which involves maintaining a sorted set of the most relevant results for every possible prefix. A query for a single-prefix term (i.e. "yank") is technically O(log(N)+M), where N is the # of items in the sorted set, and M is the # of items returned. But since in practice we often want a small # of items, we can keep both N and M small. One tradeoff we made is that this approach doesn't support incremental updates easily, you can always add new items, but it would take a good bit of work to remove items that have expired, or update the scores of items that change. As for memory usage, we only store each item once (in a redis hash table), and use the unique ids as entries in the sorted sets. Which sort of approaches a trie, since instead of: ya -> yan -> yank -> yanke -> yankee -> yankees -> [data about yankees] we have: ya -> 101 yan -> 101 ... 101 -> [data about yankees]
- timr 16y ago
  Yeah, that's what it sounded like. Aside from not supporting incremental updates, that approach has a high memory overhead. For every word of length N, you've got to store 1 + 2 + ... + N-1 + N characters, which is O(N^2). The constant is 1/2, and you do get some savings in shared prefixes, so that's definitely a worst-case upper bound -- but a trie grows with O(N). The O(log(N)) lookup time can also be a limiting factor with large sets. A trie is going to give you worst-case linear lookup time in the length of the longest string in your set. This can be a pretty dramatic difference as string sets get large.
  - Robin_Message 16y ago

ncavig 16y ago

Would be cool to have an example of this running on websockets and get rid of the request/response latency that most autocompletes have. Keep the socket open when the text field is focused and you should be able to cut down the response time even further without that overhead.

ahrjay 16y ago
Considering chrome and firefox are switching off websockets until they resolve the security issues that wouldn't be very viable. I guess you could fallback to flash sockets or long polling.

kingkilr 16y ago

The UI on seatgeek is almost identical to what rdio provides, I wonder if rdio is using it.

kin 16y ago

Awesome work guys! I really hope this type of UI becomes more widespread. On a side note, I've always thought the guys over at www.glyde.com execute it quite well.

siculars 16y ago

Oh, oh yes. Thank you kindly. I was literally about to embark on this very feature. Let's take a closer look...

dhruvbird 16y ago

How many phrases of length 30 could you handle with 1GB of RAM? Or do you have numbers on the mean length of a phrase you handle currently, the number of such phrases and how much memory it takes?

henriklied 16y ago

Great stuff! In curious: What do you think about exposing this service via WebSockets? Would that make it even faster?