Distributed computer database system and method for performing object search
First Claim
1. A method for information retrieval using fuzzy queries in a distributed computer database system having a plurality of home nodes and a plurality of query nodes connected by a network, said method comprising the steps of:
- A) selecting a first one of said plurality of home nodes;
B) extracting, by said selected home node, a plurality of features from a query by a user;
C) fragmenting, by said selected home node, each said extracted feature of said plurality of extracted features into a plurality of query fragments;
D) hashing, by said selected home node, each said query fragment of said plurality of query fragments, said hashed query fragment having a first portion and a second portion;
E) transmitting, by said selected home node, each said hashed query fragment of said plurality of query fragments to a respective one of said plurality of query nodes indicated by said first portion of each said hashed query fragment;
F) using, by said query node, said second portion of said respective hashed query fragment to access data according to a local hash table located on said query node; and
G) returning, by each said query node accessing data according to said respective hashed query fragment, a plurality of object identifiers corresponding to said accessed data to said selected home node.
2 Assignments
0 Petitions
Accused Products
Abstract
A distributed computer database system including one or more front end computers and one or more computer nodes interconnected by a network into a search engine for retrieval of objects including images, sound and video streams, as well as plain and structured text. A query is an object in the same format as the objects to be retrieved. A query from a user is transmitted to one of the front end computers which forwards the query to one of the computer nodes, termed the home node, of the search engine. The home node extracts features from the query and hashes these features. Each hashed feature is transmitted to one node on the network. Each node on the network which receives a hashed feature uses the hashed feature of the query to perform a search on its respective partition of the database. The results of the searches of the local databases are gathered by the home node.
160 Citations
28 Claims
-
1. A method for information retrieval using fuzzy queries in a distributed computer database system having a plurality of home nodes and a plurality of query nodes connected by a network, said method comprising the steps of:
-
A) selecting a first one of said plurality of home nodes;
B) extracting, by said selected home node, a plurality of features from a query by a user;
C) fragmenting, by said selected home node, each said extracted feature of said plurality of extracted features into a plurality of query fragments;
D) hashing, by said selected home node, each said query fragment of said plurality of query fragments, said hashed query fragment having a first portion and a second portion;
E) transmitting, by said selected home node, each said hashed query fragment of said plurality of query fragments to a respective one of said plurality of query nodes indicated by said first portion of each said hashed query fragment;
F) using, by said query node, said second portion of said respective hashed query fragment to access data according to a local hash table located on said query node; and
G) returning, by each said query node accessing data according to said respective hashed query fragment, a plurality of object identifiers corresponding to said accessed data to said selected home node. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15)
F1) applying a matching function to the said accessed data to select a portion of the said plurality of object identifiers, said matching function being specific to the type of the said query fragment.
-
-
3. The method of claim 1 further comprising, prior to the step of extracting features from said query, the step of:
A1) receiving, at said home node, said query from said user.
-
4. The method of claim 3 further comprising, subsequent to the step of returning said plurality of object identifiers, the steps of:
-
H) determining, by said home node, a measure of similarity between said accessed data and said query; and
I) returning to said user, by said home node, accessed data having a predetermined degree of similarity.
-
-
5. The method of claim 4 wherein said measure of similarity is determined by a similarity function based on any of:
-
i) features possessed by both the said accessed data and the said query; and
ii) features possessed only by the said query.
-
-
6. The method of claim 5 wherein for each feature of said plurality of features, said similarity function uses a function specific to the type of the said feature.
-
7. The method of claim 1 wherein step F) includes:
-
F1) using, by said query node, said second portion of said respective hashed query fragment to access the plurality of object identifiers according to a local hash table located on said query node, each said object identifier having a first portion and a second portion; and
the method further comprises;
H) transmitting, by said selected home node, each said object identifier of said plurality of object identifiers to a respective one of a plurality of object nodes indicated by said first portion of each said object identifier;
I) using, by said object node, said second portion of said respective object node to access data according to a local object table located on said object node; and
J) returning, by each said object node accessing data according to said respective object identifier, object information comprising an object location and object features to said selected home node.
-
-
8. The method of claim 7 further comprising, prior to the step of returning the said portion of said plurality of object identifiers to said selected home node, the step of:
F2) applying a matching function to the said accessed data to select a portion of the said plurality of object identifiers, said matching function being specific to the type of the said query fragment.
-
9. The method of claim 7 further comprising, prior to the step of returning object information comprising an object location and object features to said selected home node, the steps of:
-
I1) downloading, by said object node, the object identified by said respective object identifier, from an external server located by said accessed data, if said returned object information comprises stale information; and
I2) extracting, by said object node, data from said object according to said query.
-
-
10. The method of claim 7 further comprising, prior to the step of extracting features from said query, the step of:
A1) receiving, at said home node, said query from said user.
-
11. The method of claim 7 wherein said query from said user contains a time sensitivity requirement specification.
-
12. The method of claim 7 further comprising, subsequent to the step of returning said object information, the steps of:
-
A) determining, by said home node, a measure of similarity between said accessed data and said query; and
B) returning to said user, by said home node, accessed data having a predetermined degree of similarity.
-
-
13. The method of claim 7 further comprising, subsequent to the step of returning accessed data to said selected home node, the step of:
I1) constructing, by said selected home node, a table containing, for each object of the plurality of objects, the said object location and said plurality of object features.
-
14. The method of claim 7 wherein said measure of similarity is determined by a similarity function based on any of:
-
i) features possessed by both the said accessed data and the said query;
ii) features possessed only by the said query; and
iii) features possessed only by said accessed data.
-
-
15. The method of claim 7 wherein for each feature of said plurality of features, said similarity function uses a function specific to the type of the said feature.
-
16. A method of storing objects or locations of objects in a manner which is conducive to information retrieval using fuzzy queries in a distributed computer database system having a plurality of home nodes and a plurality of query nodes connected by a network, said method comprising the steps of:
-
A) selecting a first one of said plurality of home nodes;
B) extracting, by said selected home node, a plurality of features from an object submitted by a user;
C) fragmenting, by said selected home node, each said extracted feature of said plurality of extracted features into a plurality of object fragments;
D) hashing, by said selected home node, each said object fragment of said plurality of object fragments, said hashed object fragment having a first portion and a second portion;
E) transmitting, by said selected home node, each said hashed object fragment of said plurality of fragments to a respective one of said plurality of query nodes indicated by said first portion of each said hashed object fragment; and
F) using, by said query node, said second portion of said respective hashed object fragment to store data according to a local hash table located on said query node. - View Dependent Claims (17, 18)
A1) receiving, at said home node, said object from said user.
-
-
18. The method of claim 16 wherein the distributed computer database system includes a plurality of object nodes, and the method further comprises:
-
G) selecting, by said selected home node, a unique object identifier for an object selected by a user, said object identifier having a first portion and a second portion;
H) using the first portion of said object identifier to select one of said plurality of object nodes;
I) transmitting, by said selected home node, the location of the said object, the said plurality of object features of the said object to a respective one of said plurality of object nodes indicated by said first portion of each object identifier; and
J) using, by said object node, said second portion of said object identifier to store data according to a local object table located on said object node.
-
-
19. A distributed computer database system having an information retrieval tool for handling queries from a user comprising:
-
A) a plurality of home nodes; and
B) a plurality of query nodes;
C) said plurality of home nodes and said plurality of query nodes connected by a network;
D) wherein each said home node, upon receiving a query from a user, extracts a plurality of features from said query, fragments each said query feature of said plurality of query features into a plurality of query fragments, hashes each said query fragment of said plurality of query fragments into a hashed query fragment having a first portion and a second portion, and transmits each said hashed query fragment to a respective one of said plurality of query nodes indicated by said first portion of said hashed query fragment, and E) further wherein each said query node uses said second portion of said hashed query fragment to access data according to a local hash table located on said query node and returns a plurality of object identifiers corresponding to said accessed data to said home node. - View Dependent Claims (20, 21, 22, 23)
A) features possessed by both the said accessed data and the said query; and
B) features possessed only by the said query.
-
-
23. The distributed computer database system of claim 19 wherein for each feature of said plurality of features, said similarity function uses a function specific to the type of the said feature.
-
24. A distributed computer database system for storage and retrieval of information objects or locations of information objects, comprising
A) a plurality of home nodes; - and
B) a plurality of query nodes;
C) said plurality of home nodes and said plurality of query nodes connected by a network; and
D) wherein each said home node, upon receiving an object from a user, extracts a plurality of features from said object, fragments each said object feature of said plurality of object features into a plurality of object fragments, hashes each said object fragment of said plurality of object fragments into a hashed object fragment having a first portion and a second portion, and transmits each said hashed object fragment to a respective one of said plurality of query nodes indicated by said first portion of said hashed object fragment, and wherein each said query node uses said second portion of said hashed object fragment to store objects or locations of objects according to a local hash table located on said query node.
- and
-
25. An information retrieval apparatus for processing a query for word based and non-word based retrieval of information from a database, comprising:
-
A) a mechanism for extracting a number of features from the query;
B) a mechanism coupled with the extracting mechanism for fragmenting each of the features into feature fragments; and
C) a mechanism coupled with the fragmenting mechanism for hashing each of the feature fragments into hashed feature fragments for use in accessing a hash table for obtaining object identifiers therefrom for use in obtaining information from the database relevant to the query.
-
-
26. A computer program product for processing a query for word based and non-word based retrieval of information from a database, the computer program product comprising a computer-executable program embodied on a computer-readable medium, the computer-executable program comprising:
-
A) a first code portion for extracting a number of features from the query;
B) a second code portion for fragmenting each of the features into feature fragments; and
C) a third code portion for hashing each of the feature fragments into hashed feature fragments for use in accessing a hash table for obtaining object identifiers therefrom for use in obtaining information from the database relevant to the query.
-
-
27. An information indexing system for indexing information for facilitated retrieval from a database, the system comprising:
-
A) a mechanism for extracting a number of features from the information;
B) a mechanism for fragmenting each of the features into feature fragments; and
C) a mechanism for hashing each of the feature fragments into hashed feature fragments for use in accessing a hash table for storing object identifiers specifying the information at locations thereof determined by the hashed feature fragments.
-
-
28. A computer program product for indexing information for facilitated retrieval from a database, the computer program product comprising a computer-executable program embodied on a computer-readable medium, the computer-executable program comprising:
-
A) a first program code portion for extracting a number of features from the information;
B) a second program code portion for fragmenting each of the features into feature fragments; and
C) a third program code portion for hashing each of the feature fragments into hashed feature fragments for use in accessing a hash table for storing object identifiers specifying the information at locations thereof determined by the hashed feature fragments.
-
Specification