Abstract:
An efficient and intuitive means, method and apparatus for displaying and searching information organized in a hierarchical manner. The presented method for displaying and searching information utilizes methods residing at the nodes of the hierarchically organized information.

Description:
BACKGROUND OF THE INVENTION 
     Much of the information presented to computer users today is presented using a tree structure. A tree structure, when referring to a computer user interface, is a structure where groups are associated with entities within the groups which may be associated with even more refined entities within a group. It provides a hierarchical view of a collection of information. An example of this would be a tree structure (a part of which is shown in FIG. 1) where the countries of the world are listed, each country containing its associated states, each state containing its associated counties and each county having its associated towns. As shown in FIG. 1 when looking at North Carolina, much of the tree is not visible on the screen due to the substantial amount of information contained within the tree. 
     A large percentage of network management programs today are required to be scalable. In order to manage a large number of users with respect to different applications, the applications must group users and networks in some form of hierarchy. The hierarchy is typically mapped on to the tree display for the user of the program. As seen in FIG. 1, as the number of users and information in the tree increase, the tree becomes difficult to view, search and manage. Simple search mechanisms are typically offered and these have limited use for finding simple strings within the data. There are no known methods or systems for providing a contextual search within the hierarchy of a tree. A need exists for an uncomplicated method to subset and display hierarchical information to a user without significantly increasing the screen clutter and requiring significant amounts of screen space. 
     OBJECTS OF THE INVENTION 
     In view of the above, it is an object of the present invention to provide an efficient means for searching hierarchically organized information. It is another object of the present invention to minimize the screen utilization introduced by this searching mechanism. It is yet another objective to provide means for the user to receive additional information or assistance in the searching without requiring additional screen space. It is yet another object of the present invention to enable the user to fold levels of information that are currently uninteresting without disturbing the association with parent nodes. 
     SUMMARY OF THE INVENTION 
     The present invention achieves the foregoing objects by providing a method, system and program product for searching hierarchical trees more effectively. The hierarchical set of information has at least three pieces of information contained at each node of the tree. The three components are (1) the data contained at the node (2) a text entry field for a subset key for the node, and (3) the count of children for the node. This enables more efficient searching and reporting of the information contained within the hierarchical structure. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 is an example of information stored within a tree structure. 
     FIG. 2 a  is an example of the subset search tree control of the present invention having three tiers. 
     FIG. 2 b  is an example of the subset search tree control of the present invention depicting further information available at the nodes. 
     FIG. 2 c  is an example of the subset search tree control of the present invention having four tiers with some of the fourth tier expanded. 
     FIGS. 3 a  through  3   c  are alternative examples of depicting the subset search tree control. 
     FIG. 4 a  depicts a fast-path subset selection of the present invention. 
     FIG. 4 b  depicts a folded mode implemented in the present invention. 
     FIG. 5 a  depicts an alternative information display for the present invention. 
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT 
     The present invention will now be described in greater detail with respect the figures and a preferred embodiment. This invention may, however, be embodied in many different forms and should not be construed as limited to the embodiments set forth herein; rather, these embodiments are provided so that this disclosure will be thorough and complete, and will fully convey the scope of the invention to those skilled in the art. Like numbers refer to like elements throughout. 
     As will be appreciated by one of skill in the art, the present invention may be embodied as a method, data processing system or program product. Accordingly, the present invention may take the form of an entirely hardware embodiment, an entirely software embodiment or an embodiment combining hardware and software. Furthermore, the present invention may take the form of a computer program product on a computer-readable storage medium having computer-readable program code means embodied on the medium. Any computer readable medium, including disk drives, CD-ROMs, optical storage devices, magnetic storage devices or storage medium of the world wide web are applicable. 
     The preferred embodiment of the present invention is implemented using object oriented design such that the control does not process a key that is to be searched directly. When the key value changes, the control calls a method at the node of the tree to have the method determine the count of children that match the new or changed key. This allows great flexibility in matching the keys using any criteria desired. This also enables the use of wildcard characters and allows for contextual searching to be done. When the key is entered at a node, the key is passed to the node&#39;s keyCheck method. The method uses the new key value to determine the number of nodes that match the key and are therefore in the subset. This is done at each of the nodes rather than being stored in a centralized location. Examples of searches are an empty key, which may depict either all nodes in the subset or no nodes in the subset depending on programmer preferences; “char(s)*” which would depict any string beginning with the specified characters; “*char(s)” which would depict any string ending with the specified characters; or “*char(s)*” which would depict any string containing the specified characters. This syntax is customizable by the programmer and is not limited to or restricted by the above examples. 
     FIG. 2 a  depicts a subset tree control utilizing the present invention. The example depicts a search of states contained within the United States, the states within the U.S. and the counties contained therein being the hierarchical structure  202 . The searcher entered “north car” as the search string into the search field  204 , which resulted in North Carolina being the only state that matched the criteria. The status indicator  206  on the right of the search field indicates that only one of the fifty entries for the United States matched the search criteria. The “−” within the box to the left of the United States  208  indicates that this node of the tree can be collapsed. If the field were completely collapsed and there was information available for expansion the box would contain a “+” in the preferred embodiment of the present invention. Continuing downward in FIG. 2 a , the user then chooses to search for the counties in North Carolina which begin with the letters “al”, in North Carolina there are three, Alamance, Alexander, and Alleghany which are displayed in a hierarchical manner subordinate to North Carolina and the status indicator for that search indicates that there are 100 counties in North Carolina, three of which match the search criteria. 
     FIG. 2 b  indicates a search of the United States where again, the user was searching for North Carolina, but this time the user entered the search criteria “wa” in the search for the counties. The status indicator  206  indicates that five of the 100 counties in North Carolina match this criteria. The counties that match this criteria are Wake, Warren, Washington, Watauga and Wayne. The “+” indication in the box next to Wake and Watauga counties indicate that there is further subordinate information that can be expanded in those counties. In our particular example we are searching for colleges in North Carolina. FIG. 2 c  depicts the expansion of the “Wake” item in the hierarchy. This could be accomplished, for instance, by placing the pointer over the “+” in the box next to “Wake”  209  and clicking on that box. In the preferred embodiment of the present invention, this would expand the contents of the “Wake” item. Since there was no search criteria placed into the search field, the entire list is shown which is indicated by “(4 of 4)” in the status field. An alternative to allow the user to view the entire contents of the list would be to use a wild-card indicator, such as a “*”, to indicate the desire to view the entire list. 
     FIG. 3 a  depicts an alternative means of accomplishing the same type of searching yet further conserving screen space. In FIG. 3 a , an indicator (in the preferred embodiment, circles such as are used for Consumer&#39;s Reports Customer Satisfaction Indicator Ratings but this could be any visual representation) is used to tell the user whether part of the information is displayed or all of the information is displayed. If a partially full circle  302  is displayed, this indicates that only some of the available information has been presented. If a solid circle  304  is displayed, this indicates that all of the available information is presented to the user. This conserves screen space and screen clutter while conveying the most critical of the information to the user. 
     FIG. 3 b  further refines the alternative of FIG. 3 a  in that FIG. 3 b  utilizes a form of balloon help or balloon activation. In this instance, if the user places the cursor over the partially full circle and indicates activation as with a click, information containing the details of the search are expanded  306 . In the example of FIG. 3 b , the search used was “wa*” and the results were the display of 5 of the 100 counties in North Carolina. 
     FIG. 3 c  depicts a balloon-type activation where, when the user places the cursor over the partially or completely filled circle, a window  308  is displayed showing the user the search criteria and allowing the user to modify or apply a new search. It also displays statistics of the results. 
     FIG. 4 a  is an example of fast-path searching  402  where the user uses a delimiter, in the preferred embodiment a period, to separate the fields for the levels of searching and they enter the entire search into a single search field input. This allows the user to reduce the number of key strokes and mouse clicks while still viewing the searchable selections. 
     FIG. 4 b  depicts what is referred to in the present invention as a “folded mode”. In several hierarchical structures, the information is segmented and stored in several layers. As a user goes through these layers, the information can easily be presented off of the right edge of the screen so that the user will be forced to scroll back and forth to comprehend the information. The preferred embodiment of the present invention implements a folded mode so that the user may, by a predefined set of key strokes, collapse the view such that only the root and the ultimate final results of the search are displayed  410 . In the preferred embodiment, this is implemented as a toggle so that the user may then “unfold” the information using the same key strokes. This enhancement to the present invention significantly reduces the amount of display device real estate required for multi-tiered searches. 
     A further enhancement to the present invention would be to implement thresholds on the subset searching. This would require that a control be programmed to allow the node to show a subset of its subset of children only when some subset threshold has been met. As the user enters a subset key and the count of matching nodes drops below the threshold value, the subset of items would be enabled for display such as by enabling or darkening the indicator allowing the user to expand the information. If the user enters a subset key and the count of the matching nodes exceeds the threshold value, an indication of some kind, such as greying the handle, would be presented to the user so that they could further refine their search. Similar techniques are used in advanced searching engines such as Lexis-Nexis to allow only a manageable amount of information to be retrieved. 
     Yet another modification to the present invention is an implementation such that the user is not shown the total number of items within the hierarchy. This would result in only the number of items matching the search criteria being displayed as shown in  502  of FIG. 5 a . The top most node would segment the search key and pass the appropriate values of the key to the appropriate nodes. The nodes would recursively process the key and pass the result to the top most node for presentation to the user. Only the top most node and the ultimate search results would be shown with all intermediate nodes being in folded mode. 
     A further modification to the present invention is to allow the subsetting to be turned on or turned off. This can be done on a per node basis, for example, to enable the creator of a hierarchy to prohibit subsetting on certain levels which are believed to be critical for understanding the information presented.