Patent Publication Number: US-9405853-B2

Title: Reading object queries

Description:
Search-by-Example is a database search in which objects are used as query terms instead of keywords. Such objects may include articles, movies, or pictures. Objects that are “similar” to the input objects may be returned in response to the query. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  is a block diagram of an example system in accordance with aspects of the present disclosure. 
         FIG. 2  is a flow diagram of an example method in accordance with aspects of the present disclosure. 
         FIG. 3  is an example graph database at different stages in accordance with aspects of the present disclosure. 
         FIG. 4  is the example graph of  FIG. 3  at further stages in accordance with aspects of the present disclosure. 
     
    
    
     DETAILED DESCRIPTION 
     As noted above, search-by-example queries may comprise objects as search terms such that the response thereto contains objects that are “similar” to the input objects. One way to respond to these queries is by using a predetermined weighted graph structure comprising multiple interlinked objects. Through the use of an algorithm known as random walk with restart (“RWR”), each input object may be located in the graph and other objects in the graph may be given a score that indicates its “similarity” or relevance to each input object. Some conventional techniques may invoke the RWR algorithm for each input object independently and may return a sum of the most relevant objects in response to the query. 
     Unfortunately, conventional techniques like the one described above may be inadequate when the input objects are very diverse or when there is a great contrast between the input objects. For example, if the input objects include a video concerning cats and a video concerning dogs, conventional techniques may return videos pertaining to domestic animals, which may be regarded as a quality result. However, if an input object concerns cats and the other concerns space travel, conventional techniques may not return quality results due to the vast difference between the two input objects. Instead, the results may be disproportionally associated with cats or disproportionally associated with space travel, but the results may not associate the two objects in a fairly balanced manner. 
     In view of the foregoing, disclosed herein are a system, non-transitory computer readable medium, and method for responding to object queries. In one example, a subgraph in a main graph of interconnected objects may be used to generate a list of objects that associates the input objects in a query. In another example, a link between each pair of objects in the main graph may represent a distance measure or metric between each pair of objects. In yet a further example, the subgraph may be such that a total distance between each pair of input objects and a central object in the subgraph is minimized. The techniques disclosed herein may generate quality results to queries comprising objects that seem very different from each other. Rather than analyzing each input object individually, the analysis may be based on a subgraph in the main graph with the shortest interconnect between the input objects. Thus, instead of providing a score indicative of a “similarity” or relevance to each input object, the score may be indicative of a similarity or relevance to the subgraph. Tests on different data sets have indicated that the system, non-transitory computer readable medium, and method of the present disclosure outperform conventional techniques. The aspects, features and advantages of the present disclosure will be appreciated when considered with reference to the following description of examples and accompanying figures. The following description does not limit the application; rather, the scope of the disclosure is defined by the appended claims and equivalents. 
       FIG. 1  presents a schematic diagram of an illustrative computer apparatus  100  for executing the techniques disclosed herein. The computer apparatus  100  may include all the components normally used in connection with a computer. For example, it may have a keyboard and mouse and/or various other types of input devices such as pen-inputs, joysticks, buttons, touch screens, etc., as well as a display, which could include, for instance, a CRT, LCD, plasma screen monitor, TV, projector, etc. Computer apparatus  100  may also comprise a network interface (not shown) to communicate with other devices over a network. The computer apparatus  100  may also contain a processor  110 , which may be any number of well known processors, such as processors from Intel® Corporation. In another example, processor  110  may be an application specific integrated circuit (“ASIC”). Non-transitory computer readable medium (“CRM”)  112  may store instructions that may be retrieved and executed by processor  110 . As will be discussed in more detail below, the instructions may include a query handler  114 . Furthermore, non-transitory CRM  112  may comprise an objects database  116  that may read and analyzed by processor  110 . As will also be discussed in more detail below, a main graph in objects database  116  may comprise a plurality of interconnected objects. Non-transitory CRM  112  may be used by or in connection with any instruction execution system that can fetch or obtain the logic therefrom and execute the instructions contained therein. 
     Non-transitory computer readable media may comprise any one of many physical media such as, for example, electronic, magnetic, optical, electromagnetic, or semiconductor media. More specific examples of suitable non-transitory computer-readable media include, but are not limited to, a portable magnetic computer diskette such as floppy diskettes or hard drives, a read-only memory (“ROM”), an erasable programmable read-only memory, a portable compact disc or other storage devices that may be coupled to computer apparatus  100  directly or indirectly. Alternatively, non-transitory CRM  112  may be a random access memory (“RAM”) device or may be divided into multiple memory segments organized as dual in-line memory modules (“DIMMs”). The non-transitory CRM  112  may also include any combination of one or more of the foregoing and/or other devices as well. While only one processor and one non-transitory CRM are shown in  FIG. 1 , computer apparatus  100  may actually comprise additional processors and memories that may or may not be stored within the same physical housing or location. 
     The instructions residing in query handler  114  may comprise any set of instructions to be executed directly (such as machine code) or indirectly (such as scripts) by processor  110 . In this regard, the terms “instructions,” “scripts,” and “applications” may be used interchangeably herein. The computer executable instructions may be stored in any computer language or format, such as in object code or modules of source code. Furthermore, it is understood that the instructions may be implemented in the form of hardware, software, or a combination of hardware and software and that the examples herein are merely illustrative. 
     In one example, objects database  116  may be arranged as a graph data structure that may be stored in computer registers, in a relational database as a table having a plurality of different fields and records, XML documents or flat files. The graph data structure in objects database  116  may be the main graph of the system and may comprise interconnected objects with a link between each pair of objects therein. The link may represent a distance measure between each pair of objects that indicates a similarity therebetween. Query handler  114  may instruct processor  110  to read a query comprising a plurality of input objects. Query handler  114  may also instruct processor  110  to locate each input object in the main graph. In a further example, query handler  114  may detect a subgraph in the main graph such that a total distance between each pair of input objects and a central object of the detected subgraph is minimized. In another aspect, query handler  114  may also generate an ordered list of objects from the main graph that associate the input objects in the query. The selection of each listed object may be based at least partially on the subgraph. 
     Working examples of the system, method, and non-transitory computer-readable medium are shown in  FIGS. 2-4 . In particular,  FIG. 2  illustrates a flow diagram of an example method  200  for responding to object queries.  FIGS. 3-4  show an example graph data structure at different stages in accordance with aspects of the present disclosure. The actions shown in  FIGS. 3-4  will be discussed below with regard to the flow diagram of  FIG. 2 . 
     As shown in block  202  of  FIG. 2 , a query comprising a plurality of input objects may be read. The input objects may be searched in the main graph contained in objects database  116 . Referring now to the example of  FIG. 3 , an example main graph  300  is shown at time T 0  and time T 1 . By way of example, the query handler may receive a query with the three following objects: “H,” “S,” and “D.” In the example graph  300 , the matching objects are located in nodes  302 ,  304 , and  306 . As noted above, the link or association between each pair of objects in main graph  300  may represent a distance measure between each pair of objects. In turn, the distance measure may be indicative of a similarity between each pair of objects of the graph. In the example of  FIG. 3 , each link between each pair of nodes of main graph  300  is shown with a number representative of the distance measure. 
     Referring back to  FIG. 2 , a list of objects that associate the input objects may be generated from the main graph such that the list is at least partially based on a subgraph, as shown in block  204 . In one example, a subgraph may be detected or identified such that the total distance between each input object and a central object in the subgraph is minimized. Construction of the subgraph may be carried out in a variety of ways. In one example, a message may be broadcast from each input object located in the main graph. In another aspect, it may be determined which object in the main graph is the first object to receive each message broadcast by each input object. In a further example, the first object to receive each message may be appointed as the central object of the subgraph. Referring back to  FIG. 3 , at time T 0 , input objects H, S, and D in nodes  302 ,  304 , and  306  respectively are shown broadcasting messages to their respective neighbors. Object H of node  302  is shown broadcasting a message to objects A, O, and I located in nodes  308 ,  310 , and  312  respectively; object S of node  304  is shown broadcasting a message to objects B, C, and E located in nodes  318 ,  320 , and  322  respectively; and, object D in node  306  is shown broadcasting a message to objects J, K, and N located in nodes  314 ,  316 , and  317  respectively. The content of the message may be irrelevant and may be any arbitrary information, since the purpose of the broadcast may be to detect the central object between the input objects. Referring now to the graph  300  at time T 1 , all the neighboring nodes are shown forwarding the message to their respective neighbors. Object A in node  308  is shown forwarding the message to objects B and O located in nodes  318  and  310  respectively; object C in node  320  is shown forwarding the message to objects E and G in nodes  322  and  324  respectively; object I is shown forwarding the message to objects O and G in nodes  310  and  324  respectively; and, object K is shown forwarding the message to object G in node  324 . 
     In the example of  FIG. 3 , at time T 1 , object G in node  324  has received the message originating from input object H in node  302  via object I in node  312 ; furthermore, at time T 1 , object G has received the message originating from input object S in node  304  via object C in node  320 . Referring now to  FIG. 4 , main graph  300  is shown at time T 2  and time T 3 . At time T 2 , object G in node  324  also receives the message originating from input object D in node  306  via object K in node  316 . Thus, in this example, object G may be deemed the central object, since it is the first object to receive each message transmitted by each input object (i.e., objects H, S, and D). 
     At time T 3  of  FIG. 4 , the subgraph is shown being constructed around the central object G in node  324 . The subgraph may comprise the originating input objects (i.e., H, S, and D) and the objects traveled through to arrive at the central object. In one example, each object on a shortest path between each input object and the central object may be detected and each detected object positioned on the shortest path may be included in the subgraph. The shortest distance may be determined based on the distance measure between the nodes. In this example, the shortest distance between input object H in node  302  and the central object G is via object I in node  312 . Thus, object I is included in the example subgraph. Furthermore, the shortest distance between input object S in node  304  and the central object G is via object C in node  320 . Therefore, object C is also included in the example subgraph. Moreover, the shortest distance between input object D in node  306  and the central object G is through object K in node  316 . As such, object K is also included in the example subgraph. In sum, the subgraph includes the following objects: H, I, G, C, S, K, and D. 
     As noted above, an ordered list of objects may be returned as a reply to the query. The selection of each listed object may be based at least partially on the subgraph. As also noted above, some conventional techniques use RWR to calculate the “similarity” between each object in the graph and each input object. In this instance, a given input object from the query may be used as a “starting node” in the RWR algorithm. A “random walker” may iteratively walk toward the neighbors of the starting node such that the probability of walking to a node may be proportional to the associative weight of the link connecting the each pair of nodes in the graph. A given node Q in the graph may receive a score based on the probability that the walker would travel back to the starting node S from Q. This probability score may indicate the similarity or relevancy between the given node Q and the starting node S. However, when the nodes in a properly constructed subgraph are collectively used as starting nodes, the quality of the results is enhanced. For example, the nodes H, I, G, C, S, K, and D in the sample subgraph shown at time T 3  of  FIG. 4  may used as the starting nodes in the RWR procedure. In this example, the RWR algorithm may score a given object in the main graph (e.g., object L) based on the probability that the “random walker” would return to any of the nodes in the subgraph. 
     Advantageously, test results show that the foregoing system, method, and non-transitory computer readable medium enhance the quality of results made to object queries. In this regard, rather than analyzing each input object individually, a preliminary subgraph may be generated and used as a basis for further analysis. For example, using a detected subgraph as starting nodes for the RWR algorithm generates a list of objects that are scored based on their “similarity” to the subgraph. In turn, the listed objects associate the input objects better than conventional techniques. 
     Although the disclosure herein has been described with reference to particular examples, it is to be understood that these examples are merely illustrative of the principles of the disclosure. It is therefore to be understood that numerous modifications may be made to the examples and that other arrangements may be devised without departing from the spirit and scope of the disclosure as defined by the appended claims. Furthermore, while particular processes are shown in a specific order in the appended drawings, such processes are not limited to any particular order unless such order is expressly set forth herein; rather, processes may be performed in a different order or concurrently and steps may be added or omitted.