Scoring members of a set dependent on eliciting preference data amongst subsets selected according to a height-balanced tree

• US 10,545,938 B2
• Filed: 09/30/2013
• Issued: 01/28/2020
• Est. Priority Date: 09/30/2013
• Status: Active Grant

• Current Assignee: Katharyn E. Owen
• Original Assignee: Spigit Incorporated (Planview Incorporated)
• Inventors: Hardas, Manas, Purvis, Lisa, Gardner, James, Bennet, Kate
• Primary Examiner(s): Le, Thu Nguyet T
• Application Number:
  US15/025,862
• Publication Number:
  US 20160224565A1
• Time in Patent Office: 2,311 Days
• Field of Search: 707748, 707797
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/322 Trees
• CPC Class Codes: G06F 16/9027 Trees
• CPC Class Codes: G06F 3/04812 Interaction techniques based on cursor appearance or behaviour, e.g. being affected by the presence of displayed objects
• CPC Class Codes: G06F 3/04842 Selection of displayed objects or displayed text elements G06F3/0482 takes precedence
• CPC Class Codes: G06N 5/022 Knowledge engineering; Knowledge acquisition
• CPC Class Codes: G06Q 10/101 Collaborative creation, e.g. joint development of products or services
• CPC Class Codes: G06Q 30/0203 Market surveys; Market polls
• CPC Class Codes: H04L 67/02 based on web technology, e.g. hypertext transfer protocol [HTTP]

Abstract

A software voting or prediction system iteratively solicits participant preferences between members of a set, with a binary tree built used to minimize the number of iterations required. As each member of the set is considered, it is pairwise-compared with select members represented by nodes already in the binary tree, with iterations beginning at a root node of the tree and continuing to a leaf node. The newly considered member is placed as a new leaf node, and the tree is height-rebalanced as appropriate. Red-black tree coloring and tree rotation rules are optionally used for this purpose. Yes/no preference tallies are kept for each member of the set throughout the tree-building process and are ultimately used for scoring. Height-rebalancing of the tree helps minimize the number of iterations needed to precisely score each member of the set relative to its alternatives.

Claims

1. A method of scoring members of a set relative to one another, wherein the members of the set include first members for which relative preference data has been received from individuals in a group and second members for which relative preference data has not been received from individuals in the group, the first members organized according to a plurality of tree structures, wherein each tree structure corresponds to an individual'"'"'s relative preference data, the method comprising:

for each individual in the group, performing iterations;

selecting subsets, using a computer, comprised of at least one of the first members and a second member of the set and eliciting from the individual the individual'"'"'s preference between members of the subsets to determine relative preference data between at least the first member and the second member of each selected subsets;

wherein the at least one of the first members for each subset is selected by following a path in the individual'"'"'s corresponding tree structure beginning with a root node and continuing through the tree structure until a leaf node is reached according to the elicited relative preference data from any previous iterations such that in a first iteration the first member is selected as a root node in the individual'"'"'s corresponding tree structure and selecting a second member from the subset and using the relative preference data to determine if the first member or the second member is preferred, if the first member is preferred a left child node of the root node is selected for the next iteration for comparison with a second member and if a second member is preferred a right child node of the root node is selected for the next iteration for comparison with a second member,

whereupon the second member becomes one of the first members,

height-balancing the individual'"'"'s corresponding tree structure if height-unbalanced, and

repeating the iterative process of selecting, placing, and height-balancing for a new second member;

assigning a score to each member of each individual'"'"'s corresponding tree structure based on the number of times each member was preferred or not preferred in the elicited relative preference data; and

building a group score for each member of the set by combining the score corresponding to each member of all individuals in a group.

2. The method of claim 1, implemented on one or more network servers, wherein the iteratively selecting and eliciting includes generating a browser-displayable page for presentation to the individual via a digital device associated with the individual, wherein the browser-displayable page is to visually present one of the subsets to the individual and to responsively receive input from the individual of the relative preference data corresponding to the visually-presented one of the subsets.

3. The method of claim 1, wherein the tree structure comprises a red-black tree structure, and wherein height-balancing the tree structure if height unbalanced includes recoloring at least one node of the red-black tree structure.

4. The method of claim 1, wherein height-balancing the tree structure occurs if height-unbalanced includes rotating the tree structure and, in so doing, changing the root node of the tree structure.

5. The method of claim 1, wherein each of the subsets consists exactly of a pair of members, including the second member and exactly one of the first members, such that the relative preference data elicited from the individual represents a pairwise comparison between members of the set, and such that the second member is scored relative to all members of the set using a number of pairwise comparisons that is no more than approximately the binary logarithm of a total number of first members in the set.

6. An apparatus, comprising:

a processor, a memory unit, and instructions stored on non-transitory machine-readable media, the instructions adapted when executed to cause at least one machine to score members of a set relative to one another, wherein the members of the set include first members for which relative preference data has been received from individuals in a group and second members for which relative preference data has not been received from individuals in the group, the first members organized according to a plurality of tree structures, wherein each tree structure corresponds to an individual'"'"'s relative preference data, the instructions adapted when executed to cause the at least one machine to;

for each individual in the group, perform the following iterations;

select subsets comprised of at least one of the first members and a second member of the set and elicit from the individual the individual'"'"'s preference between members of the subsets to determine relative preference data between at least the first member and the second member of each selected subset;

wherein the at least one of the first members for each subset is selected by following a path in the individual'"'"'s corresponding tree structure beginning with a root node and continuing through the tree structure until a leaf node is reached according to the elicited relative preference data from any previous iterations such that in a first iteration the first member is selected as a root node in the individual'"'"'s corresponding tree structure and selecting a second member from the subset and using the relative preference data to determine if the first member or the second member is preferred, if the first member is preferred a left child node of the root node is selected for the next iteration for comparison with a second member and if a second member is preferred a right child node of the root node is selected for the next iteration for comparison with a second member,

whereupon the second member becomes one of the first members

height-balance the individual'"'"'s corresponding tree structure if height-unbalanced, and

repeat the iterative process of selection, placement, and height balancing for a new second member;

assign a score to each member of each individual'"'"'s corresponding tree structure based on the number of times each member was preferred or not preferred in the elicited relative preference data; and

building a group score for each member of the set by combining the score corresponding to each member of all individuals in a group.

7. The apparatus of claim 6, wherein the instructions when executed are adapted to cause the at least one machine to, in association with the iterative selection and the eliciting of relative preference data, generate a browser-displayable page for presentation to the individual via a computer associated with the individual, wherein the browser-displayable page is to visually present one of the subsets and responsively receive input from the individual of the relative preference data corresponding to the visually-presented one of the subsets.

8. The apparatus of claim 6, wherein the tree structure comprises a red-black tree structure, and wherein the instructions are adapted to, when executed, cause the at least one machine to recolor at least one node of the red-black tree structure.

9. The apparatus of claim 6, wherein the instructions are adapted to, when executed, cause the at least one machine to perform as part of the height-balancing of the tree structure if height-unbalanced, rotating of the tree structure and, in so doing, changing of the root node of the tree structure.

10. An apparatus to score members of a set relative to one another, wherein the members of the set include first members for which relative preference data has been received from individuals in a group and second members for which relative preference data has not been received from individuals in the group, the first members organized according to a plurality of tree structures, wherein each tree structure corresponds to an individual'"'"'s relative preference data, the apparatus comprising a computer, comprising a processor and a memory, adapted to perform, for each individual in the group, the following iterations:

selecting subsets comprised of at least one of the first members and a second member of the set and eliciting from the individual the individual'"'"'s preference between members of the subsets to determine relative preference data between at least the first member and the second members of each selected subset;

wherein the at least one of the first members for each subset is selected by following a path in the individual'"'"'s corresponding tree structure beginning with a root node and continuing through the tree structure until a leaf node is reached according to the elicited relative preference data from any previous iterations such that in a first iteration the first member is selected as a root node in the individual'"'"'s corresponding tree structure and selecting a second member from the subset and using the relative preference data to determine if the first member or the second member is preferred, if the first member is preferred a left child node of the root node is selected for the next iteration for comparison with a second member and if a second member is preferred a right child node of the root node is selected for the next iteration for comparison with a second member,

whereupon the second member becomes one of the first members,

height-balancing the individual'"'"'s corresponding tree structure if height-unbalanced, and repeating the iterative process of selection, placement, and height balancing for a new second member;

a computer adapted to assign a score to each member of each individual'"'"'s corresponding tree structure based on the number of times each member was preferred or not preferred in the elicited relative preference data; and

building a group score for each member of the set by combining the score corresponding to each member of all individuals in group.

11. The apparatus of claim 10, further comprising at least one computer adapted to transmit to a remote digital device a browser-displayable page that visually presents the scores for at least two members of the set.

12. The apparatus of claim 11, further comprising a computer to maintain for-fee subscription information, where the at least one computer adapted to transmit is to transmit the browser-displayable page to the remote digital device only upon verification of a valid subscription associated with a user of the remote digital device.