System and method for dynamic index-probe optimizations for high-dimensional similarity search
AssigneeInternational Business Machines Corporation
InventorSoumen Chakrabarti
Life of this patent
Estimating the term…
Abstract
A system and method for optimizing I/O to low-level index access during bulk-routing through a taxonomy to classify documents, e.g., Web pages, in the taxonomy. In a first optimization, bulk-routing is regarded as a generalized join operation in a relational database framework. In a second optimization, instead of processing each document individually through nodes of the taxonomy, a group of documents are processed node by node in a wavefront-style routing scheme for better amortization of index probes.
Claims19
A general purpose computer including a data storage device including a computer usable medium having computer readable code means for document classification, comprising:
- computer readable code means for establishing plural data tables, the data tables including at least a taxonomy table containing data related to at least one classification taxonomy, at least one of the tables containing data representing statistics related to occurrences of terms in nodes of the taxonomy;
- computer readable code means for receiving at least one document;
- and
- computer readable code means for classifying the document with respect to the taxonomy by undertaking at least one table join using the plural data tables and the document, such that data access is optimized.
A computer-implemented method for classifying at least one group of documents with respect to a taxonomy while optimizing I/O access, comprising the acts of:
- establishing plural data tables including at least a taxonomy table containing data related to the taxonomy and at least a statistic table containing data representing statistics related to occurrences of terms in nodes of the taxonomy;
- classifying documents in the group of documents with respect to the taxonomy by executing an inner table join and an outer table join, at least one of the joins using elements from at least the taxonomy table and the statistic table, all documents in the group being tested at a test node in the taxonomy prior to testing any document at a node other than the test node.
A computer program device comprising:
- a computer program storage device readable by a digital processing apparatus;
- and
- a program on the program storage device and including instructions executable by the digital processing apparatus for performing method steps for classifying at least one group of documents with respect to a taxonomy, the method steps comprising the acts of:
- establishing plural data tables including at least a taxonomy table containing data related to the taxonomy and at least a statistic table containing data representing statistics related to occurrences of terms in nodes of the taxonomy;
- classifying documents in the group of documents with respect to the taxonomy by executing an inner table join and an outer table join using elements from at least the taxonomy table and the statistic table, the documents being processed in a wave-front relative to the taxonomy.
Dependencies are inferred from the claim text.