Project

General

Profile

Bug #4946

Look-ahead search freezes

Added by ben leinfelder almost 10 years ago. Updated over 6 years ago.

Status:
New
Priority:
Normal
Category:
Morpho Plugin
Target version:
Start date:
04/19/2010
Due date:
% Done:

0%

Estimated time:
Bugzilla-Id:
4946

Description

In the ontology browser, quick typing will render the popup useless.
My hunch is that it will go away when we stop searching the class descriptions.

History

#1 Updated by ben leinfelder almost 10 years ago

This still isn't the speediest feature. The implementation is naive in that it reconstructs the entire tree from the ontology model after each letter is typed (or if a letter is deleted).
A better approach might be to keep a Map<node, path> where the nodes are the classnames and those are searched each time - if the node has a match, it is included (perhaps added in the case that we end up deleting a few letters and therefore loosening the search criteria).
We'd still be creating the tree each time, but not searching the ontology for sub/superclasses.

#2 Updated by Matt Jones almost 10 years ago

To make this fast, I think you'll want to use a specialized tree structure for the lookup index, rather than running queries per se. Ternary search trees, Patricia trees/Radix trees have been used for this in the past. Here are a couple of links to relevant information, including a couple of Java libs that implement them.

For ternary search trees:
http://www.javaworld.com/javaworld/jw-02-2001/jw-0216-ternary.html
http://en.wikipedia.org/wiki/Ternary_search_tree

For Radix and Patricia trees:
http://en.wikipedia.org/wiki/Radix_tree

Implementations:
http://lucene.apache.org/java/2_4_0/api/org/apache/lucene/analysis/compound/hyphenation/TernaryTree.html
http://code.google.com/p/kunyittst/
http://www.koders.com/java/fid910AA2B18B43D325FF27AE35AC25F9CBBF9F9E64.aspx?s=cdef:tree+mdef:insert#L109
http://jstock.cvs.sourceforge.net/viewvc/jstock/jstock/src/org/yccheok/jstock/engine/TernarySearchTree.java?view=markup
http://code.google.com/p/patricia-trie/
http://code.google.com/p/radixtree/

I haven't used these particular libraries, so I'm not sure how well they are implemented. They'd need to be tested at least. Hope this helps.

#3 Updated by ben leinfelder almost 10 years ago

with the new[er] ontology palette, the look ahead searching might become less important. It's nearly impossible to get the cursor to stay in the field that "launches" the palette because it is brought to the front and receives focus. The search field that the palette provides does not do look-ahead searching and instead waits for you to hit enter/search button.

#4 Updated by Redmine Admin about 7 years ago

Original Bugzilla ID was 4946

#5 Updated by ben leinfelder over 6 years ago

  • Target version changed from Unspecified to morpho-plugin-0.9.0

Also available in: Atom PDF