Process and system for sparse vector and matrix representation of document indexing and retrieval
View Patent ↗A new data structure and algorithms which offer at least equal performance in common sparse matrix tasks, and improved performance in many. This is applied to a word-document index to produce fast build and query times for document retrieval.
1. A method to produce fast build and query times for document retrieval by querying a collection of documents for documents satisfying a pre-determined condition, wherein the collection of documents is represented by sparse vectors, said method comprising the steps:
processing text of the collection of documents to produce a word vector, wherein words are keys, and values are chosen as desired,
scanning word vectors and adding each value to a index matrix,
receiving a query, and, for each word in the query, retrieving its document vector from the index matrix in constant time,
if the words in the query are weighted, applying their weights with a linear time scale operation on each vector,
combining the vectors into a single vector by means of a binary function and yielding total scores for each document, the single vector having document identifiers as keys and having merged data from each corresponding word vector as values,
mapping a function across the values of the single vector to complete the scoring process,
using the vector to display results to a user, which results identify the documents from the collection of documents satisfying the predetermined condition.
2. The method of claim 1 , wherein the binary function is chosen from the group consisting of a union set operation, an intersection set operation, and a filter operation.
3. The method of claim 1 , wherein the document-score pairs can be removed from vector form when constant time access is no longer desired.
4. The method of claim 1 , wherein the index can be queried and built simultaneously.
5. The method of claim 1 , wherein the sparse vectors are hash tables.
6. The method of claim 5 , wherein the hash tables contain integer pairs.
7. The method of claim 6 , wherein the hash tables has keys as indices, a unique word identifier as a primary key, a unique document identifier as a secondary key, and values as entires, said values are non-null if a given word occurs in a document.
8. A method to produce fast build and query times for document retrieval by querying a collection of documents for documents satisfying a pre-determined condition, the collection of documents represented by sparse vectors using hash tables representing occurrences of words in the collection of documents wherein:
said sparse vectors are hash tables of integer-number pairs,
said hash tables has keys as indices, a unique word identifier as a primary key, a unique document identifier as a secondary key, and values as entries, said values are non-null if a given word occurs in a document,
modification of values occur in constant time,
operations on vectors occur in linear time as appropriate, and
total memory consumption being linear with respect to the number of non-zero values, said method comprising:
processing text of the collection of documents to produce a word vector, wherein words are keys, and values are chosen as desired,
scanning word vectors and adding each value to a index matrix,
receiving a query, and, for each word in the query, retrieving its document vector from the index matrix in constant time,
if the words in the query are weighted, applying their weights with a linear time scale operation on each vector,
combining the vectors into a single vector by means of a binary function and yielding total scores for each document, the single vector having document identifiers as keys and having merged data from each corresponding word vector as values,
mapping a function across the values of the single vector to complete the scoring process,
using the vector to display results to a user, which results identify the documents from the collection of documents satisfying the predetermined condition.
9. The method of claim 8 , wherein the binary function is chosen from the group consisting of a union set operation, an intersection set operation, and a filter operation.
10. The method of claim 8 , wherein the document-score pairs can be removed from vector form when constant time access is no longer desired.
11. The method of claim 8 , wherein the index can be queried and built simultaneously.