At last something interesing to discuss: What is the fastest way to search a client-side database?

[Harry Haller]

What is the fastest way to search a client-side database?

I have about 60-65 kb of data downloaded to the client which is
present in 3 dynamically created list boxes. The boxes are filled from
3 string arrays, which are just lists of people or companies in
alphabetic order. These names may have accented and umlauted
characters (which are present as the plain ASCII - not as the entity
&# character). The page is UTF-8 encoded.

e.g. strManager = "Adele Brown|Albert Meinstein|Alicia Perkins ..."

The first defect of the search is that it won't look for items
beginning with an umlaut etc.

The second defect is that it's far too slow.

The current page uses a regular expression search on the whole string
(it was taken from the O'Reilly regular expression book. Entering, for
instance, a 'b' in the search box results in the corresponding list
box showing ONLY those items beginning with a 'b' or 'B'. Likewise
entering 'Ba' narrows the search down even further. Unfortunately the
first letter search takes too much time.

What data structure is best used for holding the data for this search?
Should I construct a binary-search-tree on the server using the ids of
the actual data items (with left and right pointers) - created using
an associative array? With such a structure would a binary search
algorithm give me the fastest search?

PS: in the server database all these names have ids (but the previous
developer didn't download them to the client (to "save space").

[Harry Haller]

On Sun, 29 Oct 2006 21:41:55 GMT, Harry Haller <Ha***@Steppenwolf.com>
wrote:

>What is the fastest way to search a client-side database?

Please ignore this post - the following post supersedes it.

[marss]

Harry Haller напи�ав:

The current page uses a regular expression search on the whole string
(it was taken from the O'Reilly regular expression book. Entering, for
instance, a 'b' in the search box results in the corresponding list
box showing ONLY those items beginning with a 'b' or 'B'. Likewise
entering 'Ba' narrows the search down even further. Unfortunately the
first letter search takes too much time.

I can't offer your problem solution, but I suppose you are wrong in the
problem statement.
Regular expression search is fast enough independently of "one letter"
or "two letters" search is it.
Filling the listbox with new items is much more time consuming task and
the more values your search returns the more
continuous filling will be.
That is why guess your problem not search but filling speed.

[Harry Haller]

On 30 Oct 2006 01:25:51 -0800, "marss" <ma***@ukr.netwrote:

>
Harry Haller ???????:

>The current page uses a regular expression search on the whole string
(it was taken from the O'Reilly regular expression book. Entering, for
instance, a 'b' in the search box results in the corresponding list
box showing ONLY those items beginning with a 'b' or 'B'. Likewise
entering 'Ba' narrows the search down even further. Unfortunately the
first letter search takes too much time.

I can't offer your problem solution, but I suppose you are wrong in the
problem statement.
Regular expression search is fast enough independently of "one letter"
or "two letters" search is it.
Filling the listbox with new items is much more time consuming task and
the more values your search returns the more
continuous filling will be.
That is why guess your problem not search but filling speed.

I noticed this too. It's about 50:50 at the moment - taking about 2-3
seconds, on average, for the longest list.

The first search is on a string about 47kb long containing about 1000
pipe (|) delimited phrases. E.g. a search on "n" loads the options
list with all phrases beginning with N or n (but not those with an
accented n). The second search is must less time consuming because it
searches on the second letter of all phrases beginning with n/N.

Should these 3 linear lists should be in 3 hash tables (javascript
"associative arrays"). In every case the value of the Options list
will be an integer corresponding to the ID of that SQL database entry.
The text will be the phrase.

It then looks like a pretty simple problem. The binary search is not
problem as the associative arrays will be ordered alphabetically. This
solution will also deal with the accented characters which are
currently being ignored by the search.

I should really post this page up on the internet, but before I do
that I should attempt the solution I outlined. I've been putting it
off because I'm busy doing other things and it's isn't a critical
issue - in that the current solution 'works'.

PS: the page uses UTF-8 encoding and all accented characters seem to
be in the extended ASCII set: 128-255 (I haven't noticed any accented
characters outside that range)