Method and apparatus for representation of unstructured data

• US 7,467,155 B2
• Filed: 07/12/2005
• Issued: 12/16/2008
• Est. Priority Date: 07/12/2005
• Status: Expired due to Fees

• Current Assignee: SAND Technology, Inc.
• Original Assignee: SAND Technology, Inc.
• Inventors: McCool, Michael, Wald, Linda Ann
• Primary Examiner(s): Vital, Pierre M.
• Assistant Examiner(s): Rostami, Mohammad S
• Application Number:
  US11/180,053
• Publication Number:
  US 20070016602A1
• Time in Patent Office: 1,253 Days
• Field of Search: 707/1, 707/2, 707/3, 707/4, 707/5, 707/6, 707/7, 707/8, 707/9, 707/10, 707/100, 707/102, 707/103
• US Class Current: 1/1
• CPC Class Codes: G06F 16/3347 using vector based model
• CPC Class Codes: G06F 16/335 Filtering based on additional data, e.g. user or group profiles filtering in web context G06F16/9535, G06F16/9536
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

Method and apparatus providing a binary representation of a document storing unstructured data. A unique word identifier is obtained for each word included in the document. A word select vector includes positions identified by different word identifiers. A 1-bit value is stored at positions identified by the word identifiers of the words included in the document. A unique position identifier is further assigned to each word appearing in the document. A word use set includes vectors for each unique word identifier for which a 1-bit is stored in the word select vector. Each vector in the word use set indicates the position identifiers of the instances of a particular word included in the document. Once the binary representation is generated, it may be efficiently searched to determine whether particular words appear in the document.

Claims

1. A system for representing and searching a document including unstructured data, the system comprising:

a data store storing a plurality of documents;

a processor executing program instructions, the program instructions including generating a binary representation of the unstructured data in the plurality of documents and searching the binary representation in response to a search request, the processor generating an output based on the search; and

a memory storing the binary representation of the unstructured data in a plurality of data structures, the data structures including;

a first binary bit vector identifying a plurality of unstructured data included in the plurality of documents;

a plurality of second binary bit vectors, wherein for each of the plurality of unstructured data identified in the first binary bit vector, a corresponding second binary bit vector sets one or more bits for one or more position identifiers assigned to one or more instances of the associated unstructured data appearing in one or more of the plurality of documents, wherein the instance of an unstructured data appearing at the end of a first one of the plurality of documents is assigned a position identifier of n, and the instance of an unstructured data appearing at the beginning of a second one of the plurality of documents is assigned a position identifier of n+1, wherein n is an integer greater than 0; and

a positional ID vector indicating a start position identifier of each word appearing at the beginning of each of the plurality of documents, wherein the program instructions for searching the binary representation include;

determining if a particular search term provided with the search request is identified in the first binary bit vector;

if the particular search term is identified in the first binary bit vector, retrieving the corresponding second binary bit vector;

identifying from the positional ID vector the start position identifier of the word at the beginning of a particular one of the plurality of documents to be searched;

deducing from the positional ID vector an end position identifier of a word at the end of the particular one of the plurality of documents to be searched; and

identifying one or more bits set for one or more of the position identifiers in the retrieved secondary binary bit vector between the start position identifier and the end position identifier for identifying all instances of the search term occurring in the particular document.

2. The system of claim 1, wherein the unstructured data is a word.

3. The system of claim 2 further comprising a dictionary of words, the dictionary providing a unique word identifier for each word in the dictionary, each position of the first binary bit vector being associated with a particular word identifier provided by the dictionary.

4. The system of claim 3, wherein the search term includes a search word, and the processor retrieves a word identifier for the search word.

5. The system of claim 1, wherein the program instructions further include:

storing 1-bit values in a temporary vector from a start position identified by the start position identifier to an end position identified by the end position identifier; and

performing a logical AND operation based on the temporary vector and the retrieved second binary bit vector for identifying all position identifiers for all instances of the search term occurring in the particular document.

6. The system of claim 1, wherein the search term is a phrase including a plurality of search words.

7. The system of claim 1, wherein the data structures further include:

a fourth binary vector indicating a document position of each unstructured data in the document.

8. A computer-implemented method for representing and searching a document including unstructured data, the method comprising:

generating, under control of the computer, a binary representation of the unstructured data in a plurality of documents;

storing the binary representation of the unstructured data in a plurality of data structures, the data structures including;

a first binary bit vector identifying a plurality of unstructured data stored in the plurality of documents;

a plurality of second binary bit vectors, wherein for each of the plurality of unstructured data identified in the first binary bit vector, a corresponding second binary bit vector sets one or more bits for one or more position identifiers assigned to one or more instances of the associated unstructured data appearing in one or more of the plurality of documents, wherein the instance of an unstructured data appearing at the end of a first one of the plurality of documents is assigned a position identifier of n, and the instance of an unstructured data appearing at the beginning of a second one of the plurality of documents is assigned a position identifier of n+1, wherein n is an integer greater than 0; and

a positional ID vector indicating a start position identifier of each word appearing at the beginning of each of the plurality of documents;

receiving a search request including a search term;

determining if a particular search term provided with the search request is identified in the first binary bit vector;

if the particular search term is identified in the first binary bit vector, retrieving the corresponding second binary bit vector;

identifying from the positional ID vector the start position identifier of the word at the beginning of a particular one of the plurality of documents to be searched;

deducing from the positional ID vector an end position identifier of a word at the end of the particular one of the plurality of documents to be searched;

identifying one or more bits set for one or more of the position identifiers in the retrieved secondary binary bit vector between the start position identifier and the end position identifier for identifying all instances of the search term occurring in the particular document; and

generating, under control of the computer, an output based on the search.

9. The method of claim 8, wherein the unstructured data is a word.

10. The method of claim 9, wherein a dictionary of words provide a unique word identifier for each word in the dictionary, and each position of the first binary bit vector is associated with a particular word identifier provided by the dictionary.

11. The method of claim 10, wherein the search term includes a search word, and the processor retrieves a word identifier for the search word.

12. The method of claim 10 further comprising:

storing 1-bit values in a temporary vector from a start position identified by the start position identifier to an end position identified by the end position identifier; and

performing a logical AND operation based on the temporary vector and the retrieved second binary bit vector for identifying all position identifiers for all instances of the search term occurring in the particular document.

13. The method of claim 8, wherein the search term is a phrase including a plurality of search words.

14. The method of claim 8, wherein the data structures further include:

a fourth binary vector indicating a document position of each unstructured data in the document.

15. A method for representing unstructured data included in a plurality of documents, the method comprising:

parsing the plurality of documents;

obtaining a unique word identifier for each unstructured data included in the plurality of documents;

storing a first bit-value at each position of a first binary bit vector identified by each obtained unique word identifier;

assigning a unique position identifier to each unstructured data included in the plurality of documents, wherein the unstructured data appearing at the end of a first one of the plurality of documents is assigned a position identifier of n, and the unstructured data appearing at the beginning of a second one of the plurality of documents is assigned a position identifier of n+1, wherein n is an integer greater than 0;

retrieving a second binary bit vector for each of the unique word identifiers for which the first bit-value is set in the first binary bit vector;

storing a second bit-value at each position of the retrieved second binary bit vector identified by one or more of the position identifiers assigned to one or more instances of the corresponding unstructured data identified by the unique word identifier; and

setting a positional ID vector indicating a start position identifier of each word appearing at the beginning of each of the plurality of documents, and a word appearing at the beginning of a future document to the added to the plurality of documents.

16. The method of claim 15, wherein the unstructured data is a word.

17. A computer-implemented method for representing and searching a document including unstructured data, the method comprising:

providing access to a plurality of document collections, each document collection storing a plurality of documents;

representing the plurality of documents in a particular one of the document collections via a single text object, the single text object including a plurality of structures providing a binary representation of the plurality of the documents, the plurality of structures including;

an inverted index including a word select vector and a word use set for indexing a plurality of words appearing in the plurality of documents, the word select vector setting a bit for each of the plurality of words, and the word use set including a position vector for each of the words having a bit set in the word select vector, the position vector setting a bit for each position identifier assigned to each instance of the corresponding word appearing in one or more of the plurality of documents, wherein the instance of a word appearing at the end of a first one of the plurality of documents is assigned a position identifier of n, and the instance of a word appearing at the beginning of a second one of the plurality of documents is assigned a position identifier of n+1, wherein n is an integer greater than 0;

a positional ID vector indicating a start position identifier of each indexed word appearing at the beginning of each of the plurality of documents, and an indexed word appearing at the beginning of a future document to the added to the plurality of documents; and

a document positions vector indicating, for each of the plurality of documents, an actual position in the corresponding document in which an instance of the indexed word occurs;

receiving a search term;

determining whether the bit corresponding to the search term is set in the word select vector;

if the bit corresponding to the search term is set in the word select vector, retrieving the corresponding position vector from the word use set;

selecting a first document to be searched from the plurality of documents in the particular document collection;

retrieving the start position identifier of the indexed word at the beginning of the first document to be searched from the positional ID vector;

deducing an end position identifier corresponding to an indexed word at the end of the first document to be searched from the positional ID vector;

setting bits in a mask vector from a start position identified by the start position identifier to an end position identified by the end position identifier;

performing a logical AND operation with the mask vector and the retrieved position vector for identifying all position identifiers for all instances of the search term occurring in the first document; and

identifying actual locations of the identified instances of the search term in the first document from the document positions vector.

18. The method of claim 17, wherein the actual positions indicated in the document positions vector are character positions in the corresponding document.

19. The method of claim 17, wherein the position identifiers in the positional ID vector do not reflect the actual positions of the words in the corresponding documents.

20. The method of claim 19, wherein the second one of the plurality of documents appears sequentially in the document collection after the first one of the plurality of documents.

21. The method of claim 17, wherein the end position identifier corresponding to the word at the end of the first document is based on the start position identifier corresponding to the word at the beginning of a second document consecutively following the first document in the particular document collection.

22. The method of claim 17, wherein the start position identifier stored in the positional ID vector for the second one of the plurality of documents is n+1.