[KPhotoAlbum] Idea for quick search feature

Shawn Willden shawn-kimdaba at willden.org
Wed Apr 25 16:39:41 CEST 2007


On Wednesday 25 April 2007 02:12:35 am Jesper K. Pedersen wrote:
> I like the idea, but do have a few concerns/ideas/whatever.
> - First, It might be usefull with some way to specify wheather searching
> should be incremental, or when enter is pressed (in the case for searching
> taking 20 sec :-)

I've been struggling with that as well.  My current thought is that I'd like 
it always to be incremental, but to see if we can apply enough cleverness (uh 
oh!) to keep it responsive.

I think even a fairly straightforward implementation will be pretty fast for 
the XML backend, especially since I expect once the SQL backend is fully 
functional, everyone with large databases will move to it.

Still, I do have a couple of ideas about making the queries fast for XMLDB.  
The first, and most obvious, is that the in-memory incremental searches will 
be a process of successive refinement.  Adding another character to the 
search string will only narrow the search, so there's no need to search the 
whole database again.  This means that, usually, only the first few 
characters you type will be slow.

To address this slowness, I'm thinking that the search engine should run in a 
separate thread.  Obviously, that poses some potentially serious 
concurrent-access issues.  I haven't yet looked into what locking 
infrastructure is in place to avoid them.

(Aside:  As a future refinement, it might be good to look into the possibility 
of searching in multiple threads.  Search is easily parallelizable, and given 
the trend towards multi-core machines, in a few years it could be a big help.  
Both of my computers now, laptop and desktop, are dual-core, and I wouldn't 
be surprised to have a quad-core by 2010).

Another possibility I'm experimenting with is to use a patricia trie to 
accelerate tag searches.  Constructing the trie would take a little time, but 
I'm more concerned about how much memory it would consume, so that's what I'm 
fiddling with now.  It's also possible that using a trie rather than a 
standard tree won't gain much.  In any case, if those approaches prove 
workable, they should make searching the tags very fast.  One downside of 
using a trie (or a tree) is that it will search tags by prefix.  That's not 
so bad, though, and it's what the search bar currently does for 

Anyway, I'm fairly confident that as-you-type searching for in-memory 
databases is feasible, although the thumbnails/counts displayed may be slow 
to update for the first few letters.

SQL databases are another can of worms, both because they're going to be a lot 
bigger, and because of the nature of SQL queries.  Allowing interactive, 
incremental searching with a SQL database is either easier or harder 
depending on your point of view, because there's just not very much you can 
do.

The only things I can see that we can do are:

1.  Run queries in a separate thread.  Pleasantly, there are no concurrency 
issues with this.
2.  Delay execution of queries.  Perhaps we can wait until the user stops 
typing (more precisely, hasn't typed a character for some period of time) or 
hits enter before initiating the query.  The delay could be automatically 
tuned based on how long queries take, because there's little point in having 
a delay that's significantly longer than the query would have taken.
3.  Try to optimize the queries, by structuring them well and by making sure 
that all applicable indexes are in place.

Any other ideas?

> - Imagine this use case:
>   I type June in the search bar.
>   I then see I have 2000 images from June, and want to start drilling
>   I therefore press persons
>
> Will the search bar still say June? and if so, can I now not search in the
> persons list?

Good point, and a blindingly obvious one that I somehow missed.  I'm liking 
Angel's idea about adding the click-selected criteria to the search bar more 
and more.

In that case, your scenario would go like this:

1.  You type June, and see you have 2000 images.
2.  You click "People"and the list of people categories comes up.  The search 
bar contains "June People:" and your cursor is positioned after the colon. 
3.  You type "s" and the list is narrowed to names beginning with s.
4.  You click on "Shawn Willden" and the search bar contains 'June 
People:"Shawn Willden"' and you get back to the "counts" view, with the 
appropriate numbers.

Obviously, you could also have just typed the search string to begin with.  As 
a power user and fast typist, that's probably what I would have done.  For 
novices and those who prefer the mouse, they can construct queries by 
clicking -- and in the process the app will teach them how to construct query 
strings, leading them towards power-userhood.

> Jesper (Who still only have internet when he goes to a bar)

Well, that should make for some interesting posts!

	Shawn (currently sitting on a beach in Daytona Beach, Florida)


More information about the KPhotoAlbum mailing list