Granted Patent B2

US 12,380,121 · App. 18/053,738 · Granted Aug 5, 2025

Inventors: Xi Cheng (Kirkland, WA); Zichuan Ye (Mountain View, CA); Peng Lin (Mountain View, CA); Jiashang Liu (Kirkland, WA); Amir Hormati (Mountain View, CA); Mingge Deng (Kirkland, WA)

Assignee: Google LLC

G06F16/2462G06F16/215G06F16/256

Abstract

Claims (42)

1. A computer-implemented method when executed by data processing hardware causes the data processing hardware to perform operations comprising:

receiving an anomaly detection query from a user, the anomaly detection query requesting the data processing hardware to determine one or more anomalies in a dataset comprising a plurality of examples, each example in the plurality of examples associated with one or more features;

training a model using the dataset, the trained model configured to use a standard local outlier factor (LOF) algorithm and a randomized LOF algorithm, the randomized LOF algorithm having a greater scalability for large datasets relative to the standard LOF;

determining that a size of the dataset satisfies a size threshold;

based on determining that the size of the dataset satisfies the size threshold, selecting the randomized LOF algorithm; and

for each respective example of the plurality of examples in the dataset:

determining, using the trained model and the selected randomized LOF algorithm, a respective local deviation score based on the one or more features;

determining that the respective local deviation score satisfies a deviation score threshold,

based on the deviation score satisfying the deviation score threshold, determining that the respective example is anomalous; and

reporting the respective anomalous example to the user.

2. The method of claim 1 , wherein the trained model uses locality sensitive hashing to determine pairwise distance computations between pairs of respective examples of the plurality of examples.

3. The method of claim 2 , wherein the trained model uses the randomized LOF algorithm based on random projection to generate a random vector based on the dataset.

4. The method of claim 2 , wherein the pairwise distance computations determined by the locality sensitive hashing comprise cosine distances.

5. The method of claim 2 , wherein the pairwise distance computations determined by the locality sensitive hashing comprise Euclidean distances.

6. The method of claim 2 , wherein determining, using the trained model, the respective local deviation score comprises:

determining, using the trained model, a number of nearest neighbors to the respective example; and

determining, using the trained model, a local reachable density of the respective example.

7. The method of claim 1 , wherein the anomaly detection query comprises a single Structured Query Language (SQL) query.

8. The method of claim 1 , wherein the data processing hardware resides on a cloud database system.

9. The method of claim 1 , wherein the operations further comprise removing duplicate examples from the plurality of examples.

10. A system comprising:

data processing hardware; and

memory hardware in communication with the data processing hardware, the memory hardware storing instructions that when executed on the data processing hardware cause the data processing hardware to perform operations comprising:

receiving an anomaly detection query from a user, the anomaly detection query requesting the data processing hardware to determine one or more anomalies in a dataset comprising a plurality of examples, each example in the plurality of examples associated with one or more features;

training a model using the dataset, the trained model configured to use a standard local outlier factor (LOF) algorithm and a randomized LOF algorithm, the randomized LOF algorithm having a greater scalability for large datasets relative to the standard LOF;

determining that a size of the dataset satisfies a size threshold;

based on determining that the size of the dataset satisfies the size threshold, selecting the randomized LOF algorithm; and

for each respective example of the plurality of examples in the dataset:

determining, using the trained model and the selected randomized LOF algorithm, a respective local deviation score based on the one or more features;

determining that the respective local deviation score satisfies a deviation score threshold,

based on the deviation score satisfying the deviation score threshold, determining that the respective example is anomalous; and

reporting the respective anomalous example to the user.

11. The system of claim 10 , wherein the trained model uses locality sensitive hashing to determine pairwise distance computations between pairs of respective examples of the plurality of examples.

12. The system of claim 11 , wherein the trained model uses the randomized LOF algorithm based on random projection to generate a random vector based on the dataset.

13. The system of claim 11 , wherein the pairwise distance computations determined by the locality sensitive hashing comprise cosine distances.

14. The system of claim 11 , wherein the pairwise distance computations determined by the locality sensitive hashing comprise Euclidean distances.

15. The system of claim 11 , wherein determining, using the trained model, the respective local deviation score comprises:

determining, using the trained model, a number of nearest neighbors to the respective example; and

determining, using the trained model, a local reachable density of the respective example.

16. The system of claim 10 , wherein the anomaly detection query comprises a single Structured Query Language (SQL) query.

17. The system of claim 10 , wherein the data processing hardware resides on a cloud database system.

18. The system of claim 10 , wherein the operations further comprise removing duplicate examples from the plurality of examples.

Assignments (1)

Continuity (2)

References Cited (27)