Data search employing metric spaces, multigrid indexes, and B-grid trees

• US 6,636,849 B1
• Filed: 11/22/2000
• Issued: 10/21/2003
• Est. Priority Date: 11/23/1999
• Status: Expired due to Fees

• Current Assignee: Genmetrics
• Original Assignee: Genmetrics
• Inventors: Yang, Yonghong Grace, Tang, Yuanhua Tom
• Primary Examiner(s): Robinson, Greta
• Assistant Examiner(s): Black, Linh
• Application Number:
  US09/718,573
• Time in Patent Office: 1,063 Days
• Field of Search: 707/1-10, 707/100-104
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• 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/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

Systems and methods for generating indexes and fast searching of “approximate”, “fuzzy”, or “homologous” matches for a large quantity of data in a metric space are provided. The data is indexed to generate a search tree taxonomy. Once the index is generated, a query can be provided to report all hits within a certain neighborhood of the query. In an even faster implementation, the invention may be used together with existing approximate sequence comparison algorithms, such as FASTA and BLAST. Here, a local distance of a local metric space is used to generate local search tree branches. Applications of this invention may include homology search for DNA and/or protein sequences, textual or byte-based searches, literature search based on lists of keywords, and vector and matrix based indexing and searching.

Claims

1. A computer implemented method to search data via a query comprising the acts of:

creating a multigrid tree taxonomy in metric space for said data using distance functions; and

comparing said query with said multi-grid tree taxonomy to find matches within a given neighborhood of said query.

2. The method recited in claim 1, wherein said creating step further comprises the act of constructing at least one grid, said grid having a grid point, radius, and descriptors that define the scope of the data elements of said data residing in said grids.

3. The method recited in claim 2, wherein said grid point exists outside of said data.

4. The method recited in claim 2, wherein said creating step further comprises the acts of identifying a root grid, and constructing children grids for connection to said root grid and to constructed said children grids, said connection of children grids to said root grid creating a tree branch at a first level, and said connection of children grids to said connected children grids creating a tree branch at a second level, said children grids constructed and connected until all of said data is represented in said tree.

5. The method recited in claim 4, wherein said radius of said grids decrease in size the further the grid is away from said identified root.

6. The method recited in claim 4, wherein said creating step is realized by performing distance calculations on said data in metric space.

7. The method recited in claim 4, wherein said creating step produces a balanced multigrid tree, said balanced multigrid tree (B-grid tree) having distributed a uniform number of data elements in said grids, and a uniform number of grids on said levels of said tree.

8. The method recited in claim 7, wherein said creating step produces a B-grid tree having non-overlapping grids.

9. The method recited in claim 1, wherein said comparing step further comprises the steps of calculating distance functions on said multi-grid tree to eliminate grids that do not contain desired data elements and reporting matches from those grids that could contain desired data elements.

10. The method recited in claim 9, wherein said comparing step is realized by verifying the triangle inequality of metric space distance functions.

11. The method recited in claim 1 or 7, wherein said creating act further comprising the acts of calculating distances in metric space comprising any of global distance and local distance.

12. A computer readable storage medium comprising computer-executable instructions for instructing a computer to perform the acts recited in claim 1.

13. A system to provide efficient data searches comprising:

a data store containing data; and

a computing application cooperating with said data store, said computing application having a user interface to accept search queries and processing abilities to process said data of said data store to create a balanced multigrid tree (B-grid tree), said B-grid tree representative of said data of said data store.

14. The system recited in claim 13, wherein said computing application creates said B-grid tree by transposing said processed data into metric space, said computing application calculating distance functions for said data to construct at least one grid, having a grid point, a radius and descriptors, said grid representative of a subset of said data, said at least one grid acting as a component of a grid tree which comprises a root level and plurality of branch levels such that a plurality of grids can reside on a given level of said tree, said tree having as many levels as required to fully represent said data.

15. The system recited in claim 14, wherein said at least one grid is placed on said one of a plurality of branch levels based on the results of a distance function calculation performed by said computing application.

16. The system recited in claim 15, wherein grids have decreasing radii with increasing levels apart from said root level.

17. The system recited in claim 13, wherein a grid point of said B-tree grid is not representative of a data element of said data.

18. The system recited in claim 13, wherein said data store resides on a database.

19. The system recited in claim 18, wherein said data comprises any of words of a dictionary, biological sequence data, map vectors, keyword list for scientific literature, and Internet based addressing information.

20. The system recited in claim 18, wherein said database is part of said computing application.

21. The system recited in claim 13, wherein said data store resides on a computer server that communicates to said computing application over a communications network comprising any of a LAN, WAN, an intranet, and the Internet.

22. The system recited in claim 20, wherein said computer server hosting said data store comprises any of a storage area network (SAN) and distributive storage and processing systems (peer-to-peer).

23. The system recited in claim 13, wherein said computing application comprises a Web browser computing application.

24. The system recited in claim 22, wherein said Web browser computing application executes code comprising of a JAVA applet, JAVA script, HTML, HTML script, XML, WML, and HDML to create said B-grid tree index.

25. A method to provide searchable biological sequencing data comprising the acts of:

storing biological sequence data in a easy to distribute format, such that said data is represented by a B-grid tree in metric space; and

distributing said updated biological sequence data having said B-grid tree.

26. The method recited in claim 25 further comprising the act of updating said biological sequence data with new biological sequence information, said B-grid tree being regenerated when said biological sequence data is updated.

27. In a computing system having a data store containing data, a method to search data to provide approximate search results comprising the steps of:

processing said data by a computing application, said computing application performing a sort of said data using an approximation sequence comparison algorithm; and

creating a B-grid tree for said data by said computing application such that said B-grid tree is representative of said data of said data store.

28. The method recited in claim 27, wherein said processing step further comprises the step of choosing the approximation sequence comparison algorithm to employ to index said data, said indexing algorithm comprising any of FASTA, FASTB, BLAST, and BLASTP approximation sequence comparison algorithm.

29. The method recited in claim 27, further comprising the steps of comparing a search query received by said computing application against said created B-grid tree to determine matches between said received search query and said data of said data store.