Results 1 to 2 of 2

Thread: Autocompletion

  1. #1
    Join Date
    Feb 2011
    Waterloo, Ontario, Canada


    Hey all. Lately, I've been thinking a lot about searching autocompletion for my website. The functionality is very similar to say, something like Youtube (start typing in a song name or artist name). I've been milling over the idea of using a Trie data structure for the search. On the web, this can be problematic as there's no pointers and such that make tree-like structures easy. I would have to store a list of words somehow (in a Trie structure) and would have to fetch and parse this string every time I went to do a search (not to mention inserting and deleting from the structure wouldn't be trivial).

    Currently, I just use jQuery's autocomplete that reads from an XML file (which I'm guessing just does a linear time search that has to parse the whole file anyway). It works fine I suppose, but it actually looks for matches in the entire string (not just matching prefixes) and returns them in the order they appear in the XML file (I would prefer if they ranked based on number of queries which is also stored in the XML file).

    At one point I was just considering an AJAX request to a page that would just query the database for matches. I'm guessing this would be quite a hit to the server (you'd have to do the request on literally every letter typed) but it may be preferential to having users do this processing themselves (especially if they're on a mobile device).

    Do any of you have some success stories on implementing your own autocomplete or can point me in the right direction?

  2. #2
    Join Date
    Jul 2008
    urbana, il
    performance-wise, you should be able to afford to run a full-table scan for every few letters typed on either the client or server.
    if you have a persistent backend like node.js, it's almost surely going to be less than a 50ms turn-around, since node can search objects in RAM.
    if you have to query a db or load a flat file in asp or php, your're probably looking at 50-500ms per request.
    you can use PHP's APC to ram-cache your data structure, drastically lowering the cost of each request on that server.

    if you wait, say half a second from the time typing stops, resetting the timer with each keypress, a 500ms turnaround is usable. not zippy, but usable.

    i'm not sure how detailed your search needs to be or how much data your searching, but i would throw out a soft-limit of 2mb of JSON to be processed by a JS client to cover phones and other weak devices.
    don't use XML, it requires FAR more CPU power to build it's DOM, and a bit more network bandwidth to double-send each key name to utilize the same data with XML as with JSON.

    2mb is a lot of text, the bible is only ~1.2mb, so if all you want to search are <title>s and <meta description>s, there's no reason a simple index cannot be served to the client.
    if the index is under 250kb, and you're doing it client-side, you can go ahead and suggest each keypress, without a pause; the search will be instant.

    you can even make an excel spreadsheet of your fields, save it as CSV, and use ajax to grab to CSV, which is a lot more efficient of a format than JSON, since key names are not repeated each row, and strings need no quotes...
    this would likely be the same type of file you would load in PHP or ASP, and the over-all routine is related, it's just a matter of where and when it's performed.

    anyways, there's a lot of different ways to do it. the easiest and cheapest way is probably to use javascript. the most powerful way for tons and tons of data is via a self-caching server.

    if you expand upon your data collection, # of files, #of fields, #of indexed fields, etc, i can probably help you find a good technological match for your needs, but it's hard to say universally.
    Create, Share, and Debug HTML pages and snippets with a cool new web app I helped create: pagedemos.com

Thread Information

Users Browsing this Thread

There are currently 1 users browsing this thread. (0 members and 1 guests)

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
HTML5 Development Center



X vBulletin 4.2.2 Debug Information

  • Page Generation 0.08871 seconds
  • Memory Usage 2,844KB
  • Queries Executed 15 (?)
More Information
Template Usage (32):
  • (1)ad_footer_end
  • (1)ad_footer_start
  • (1)ad_global_above_footer
  • (1)ad_global_below_navbar
  • (1)ad_global_header1
  • (1)ad_global_header2
  • (1)ad_navbar_below
  • (1)ad_showthread_firstpost_sig
  • (1)ad_showthread_firstpost_start
  • (1)ad_thread_first_post_content
  • (1)ad_thread_last_post_content
  • (1)footer
  • (1)forumjump
  • (1)forumrules
  • (1)gobutton
  • (1)header
  • (1)headinclude
  • (1)headinclude_bottom
  • (2)memberaction_dropdown
  • (1)navbar
  • (4)navbar_link
  • (1)navbar_moderation
  • (1)navbar_noticebit
  • (1)navbar_tabs
  • (2)option
  • (2)postbit
  • (2)postbit_onlinestatus
  • (2)postbit_wrapper
  • (1)spacer_close
  • (1)spacer_open
  • (1)tagbit_wrapper 

Phrase Groups Available (6):
  • global
  • inlinemod
  • postbit
  • posting
  • reputationlevel
  • showthread
Included Files (26):
  • ./showthread.php
  • ./global.php
  • ./includes/class_bootstrap.php
  • ./includes/init.php
  • ./includes/class_core.php
  • ./includes/config.php
  • ./includes/functions.php
  • ./includes/functions_navigation.php
  • ./includes/class_friendly_url.php
  • ./includes/class_hook.php
  • ./includes/class_bootstrap_framework.php
  • ./vb/vb.php
  • ./vb/phrase.php
  • ./includes/functions_facebook.php
  • ./includes/functions_calendar.php
  • ./includes/functions_bigthree.php
  • ./includes/class_postbit.php
  • ./includes/class_bbcode.php
  • ./includes/functions_reputation.php
  • ./includes/functions_notice.php
  • ./packages/vbattach/attach.php
  • ./vb/types.php
  • ./vb/cache.php
  • ./vb/cache/db.php
  • ./vb/cache/observer/db.php
  • ./vb/cache/observer.php 

Hooks Called (73):
  • init_startup
  • friendlyurl_resolve_class
  • init_startup_session_setup_start
  • database_pre_fetch_array
  • database_post_fetch_array
  • init_startup_session_setup_complete
  • global_bootstrap_init_start
  • global_bootstrap_init_complete
  • cache_permissions
  • fetch_postinfo_query
  • fetch_postinfo
  • fetch_threadinfo_query
  • fetch_threadinfo
  • fetch_foruminfo
  • load_show_variables
  • load_forum_show_variables
  • global_state_check
  • global_bootstrap_complete
  • global_start
  • style_fetch
  • global_setup_complete
  • showthread_start
  • showthread_getinfo
  • strip_bbcode
  • friendlyurl_clean_fragment
  • friendlyurl_geturl
  • forumjump
  • cache_templates
  • cache_templates_process
  • template_register_var
  • template_render_output
  • fetch_template_start
  • fetch_template_complete
  • parse_templates
  • fetch_musername
  • notices_check_start
  • notices_noticebit
  • process_templates_complete
  • friendlyurl_redirect_canonical
  • showthread_post_start
  • showthread_query_postids
  • showthread_query
  • bbcode_fetch_tags
  • bbcode_create
  • showthread_postbit_create
  • postbit_factory
  • postbit_display_start
  • postbit_imicons
  • bbcode_parse_start
  • bbcode_parse_complete_precache
  • bbcode_parse_complete
  • postbit_display_complete
  • memberaction_dropdown
  • tag_fetchbit
  • tag_fetchbit_complete
  • forumrules
  • navbits
  • navbits_complete
  • build_navigation_data
  • build_navigation_array
  • check_navigation_permission
  • process_navigation_links_start
  • process_navigation_links_complete
  • set_navigation_menu_element
  • build_navigation_menudata
  • build_navigation_listdata
  • build_navigation_list
  • set_navigation_tab_main
  • set_navigation_tab_fallback
  • navigation_tab_complete
  • fb_like_button
  • showthread_complete
  • page_templates