Prior Art for Apple Heuristic Search Algorithm (Pub No. 2012-0166477)

Question

Looking for prior art for Apple's search algorithm patent.

In January 2000, Apple filed its original patent application to a heuristic search approach that uses a variety of algorithms that depend upon the area being searched. The application also suggests that some of the searches will be done on the local computer while others will be over the network. Although developed much later, Apple has claimed that this invention is embodied by its iPhone Siri application. Apple has also sued Samsung for infringing one of the resulting patents. The courts have rejected that claim, but Apple still has a continuation application pending in the case. (Published as US Pub. No. 2012-0166477)

The new application claims:

A computerized method, comprising

receiving at least a partial search query;

storing the at least partial search query on a non-transitory computer readable medium;

searching a first plurality of files for matches with the at least partial search query, wherein the first plurality of files is located across an internet connection coupled to the non-transitory computer readable medium;

searching a second plurality of files for matches with the at least partial search query, wherein the second plurality of files is only available via local access from a computer that includes the non-transitory computer readable medium; and

receiving a notification of at least one search result;

The USPTO has identified two relevant references: Patent Nos. 6,185,567 and 6,070,158, but I suspect that others are available. Prior art must be submitted to the USPTO before December 28, 2012. Directions for Sending Prior Art to USPTO

Note: This application is related to Apple's Patent No. 8,086,604 discussed in a different AskPatents question.

Answer 1

This document from 1999 describes a distributed search system, and the claims from the Apple patent look like a subset of the capabilities:

http://www.kmworld.com/Articles/Editorial/Feature/Excalibur-RetrievalWare-more-than-information-retrieval--9139.aspx

This paragraph is illustrative.

"The product offers a single interface for searching for information across multiple data sources, seamlessly presenting returned results within a single result list. Right from a Web browser, users can search and retrieve information--including text, word processing documents, PDF files, news feeds, images, messages and data from e-mail and groupware systems, and information from relational databases--without knowing or caring where the information is located. Information can be presented to users in a familiar folder hierarchy, making the software easy for users to learn."

Good luck killing this presposterous patent.

Answer 2

Interestingly - patent US7836044 (Google instant) sounds exceedingly similar.

A search system monitors the input of a search query by a user. Before the user finishes entering the search query, the search system identifies and sends a portion of the query as a partial query to the search engine. Based on the partial query, the search engine creates a set of predicted queries. This process may take into account prior queries submitted by a community of users, and may take into account a user profile. The predicted queries are be sent back to the user for possible selection. The search system may also cache search results corresponding to one or more of the predicted queries in anticipation of the user selecting one of the predicted queries. The search engine may also return at least a portion of the search results corresponding to one or more of the predicted queries.

Sounds very similar.

receiving at least a partial search query;

same as the search system identifies and sends a portion of the query as a partial query to the search engine.

storing the at least partial search query on a non-transitory computer readable medium;

searching a first plurality of files for matches with the at least partial search query, wherein the first plurality of files is located across an internet connection coupled to the non-transitory computer readable medium;

searching a second plurality of files for matches with the at least partial search query, wherein the second plurality of files is only available via local access from a computer that includes the non-transitory computer readable medium; and

receiving a notification of at least one search result;

The search system may also cache search results corresponding to one or more of the predicted queries - storing on computer readable medium (memory); and The search system may also cache search results corresponding to one or more of the predicted queries in anticipation of the user selecting one of the predicted queries. The search engine may also return at least a portion of the search results corresponding to one or more of the predicted queries. - a "cache" may be stored to disk (or RAM), creating a "plurality of files" that are utilized in the searching operation; both locally and over a network.

Answer 3

In Delphi7 there were several DBLookup components which make that, take an input and show a list of results using the input as a partial input.

DBLookup Text v.2.0 FWS 4 k 09 Apr 1999 By Steve Flynn. Its a Label control that sources its text from a Database Field. The contents of this field is not actually displayed, but is used as a Lookup reference for a second Database. The result of the Lookup operation is used as the Text that is displayed in the Label.

Fully functional Source: Included Download: D1 D2 D3 D4

Answer 4

Is there anything in the claim that is not in a query made to a distributed database where some of the database is accessed over a network and some of it is on disks attached to the local machine? For example, the textbook, Principles of distributed database systems, by M. Tamer Özsu, Patrick Valduriez, second edition published 1999 discusses not just distributed databases but discusses implementations over the world wide web.

NEW TO THIS EDITION

The relationship of distributed DBMSs with the new networking technologies is discussed.

The query processing/optimization chapters now focus on techniques employed in commercial systems and include new algorithms such as randomized search strategies.

[...]

Full chapters are devoted to parallel DBMSs and distributed object DBMSs.

Current issues are discussed in a new chapter, including sections on data warehousing, world wide web and databases, push-based technologies, and mobile DBMSs.

Answer 5

This article combines heuristic web searches:

@article{gauch1996profusion, title={ProFusion*: Intelligent fusion from multiple, distributed search engines}, author={Gauch, S. and Wang, G. and Gomez, M.}, journal={Journal of Universal Computer Science}, volume={2}, number={9}, pages={637--649}, year={1996} }

This article implements local site webs and web search:

@article{miller1998sphinx, title={SPHINX: a framework for creating personal, site-specific Web crawlers}, author={Miller, R.C. and Bharat, K.}, journal={Computer Networks and ISDN systems}, volume={30}, number={1}, pages={119--130}, year={1998}, publisher={Elsevier} }

Combining these two teachings in a way obvious to a practitioner skilled in the arts (or indeed to a primary school student) would lead to a system with the local and remote search capabilities proposed in this patent.

Answer 6

This is another system which searches local files and remote storage

http://radiographics.rsna.com/content/19/2/523.full

1. List item

"To find a requested image, a strategy called “multipath search” is implemented for view stations in our PACS. When an image is requested, the view station used for retrieval searches the local hard disk first. If the image is not on the local disk, the retrieval process shifts to the related cache server. If the image is not in the cache server, the index database is used to find the image. If it is a current image, it will be retrieved from the central image server; otherwise, it will be retrieved from one of the CD-ROM jukebox readers" (source: March 1999 RadioGraphics)

Answer 7

Sherlock in MacOS 8.5 does not cover everything in the patent claim, but it does most of it and could serve to restrict what is considered novel in the claim and show it to be obvious.

Sherlock was a feature introduced by Apple in Mac OS 8.5, released in 1998. It was a search tool with two tabs, one for local file search, one for Internet search.

This patent claim is a computerized method of clicking one tab in Sherlock, then clicking the other tab.

Here is an Apple archived document on Sherlock features in MacOS 8.5:

http://support.apple.com/kb/TA25758

The correspondence to the claim is

A computerized method
It is done on a Mac running MacOS 8.5

receiving at least a partial search query
query is typed by user in the search terms box

storing the at least partial search query on a non-transitory computer readable medium
query is kept in memory and displayed to the user. Also there is a "save search" option

searching ... across an internet connection
This is done when the user clicks on the Search Internet tab and clicks the Search button

searching a second ... only available via local access
This is done when the user clicks on the Find By Content tab and clicks the Search button

Note that the patent claim does not say that the computer does everything without a user having to click any buttons. In any case combining the two clicks into one can be considered an obvious refinement, especially since the Search Internet of Sherlock already combined multiple sources to be searched, with additional sources configurable by adding plugin files.

Answer 8

Isn't this effectively what WebFerret does?

This was developed in 1995-1996 by Vironix Software Laboratories, and copied by Symantec with their FastFind product.

At very least Webferret should illustrate the obviousness of the patent.

Answer 9

Other than the "coupled to the non-transitory computer readable medium" clause which I don't understand, it seems like the DNS system fits this pretty well:

A caching resolver will store the query on a non-transitory computer readable medium.

A DNS nameserver is the remote resource searched for matches, hosts files are the local resource, and nsswitch.conf allows you to configure the remote server to be queried before the local files.

Partial queries are supported to a limited extent by wildcard records. (The system has far more provision for partial responses.)

Answer 10

Has someone alerted SAP/Sybase, Microsoft or Oracle to this scam patent?

This is an EXACT description of how Sybase Adaptive Server handles multiple database, multi-vendor databases when joint querying with a local database. Since Microsoft is derived from Sybase it does similar things and Oracle developed a product to compete with Sybase Adaptive Server (but whose product name I can not currently recall). I was part of Alpha test for the Sybase product as well as many releases of Microsoft SQL Server.

Answer 11

There seem to be a ton of patents that are relevant, and could be combined to predict Apple's patent following at least one of the factors laid out in MPEP 2143.

This patent: "Information management system" US5634051 Issue date: May 27, 1997

The first claim seems that it could be paired with prior referenced patents to suggest the approach Apple employed:

An information storage, searching and retrieval system for large domain archived data of various types comprising:

means for storing a large domain of data contained in multiple source records, at least some of the source records being comprised of individual documents of multiple document types;

means for searching at least a substantial portion of such data based on a search query to identify documents of multiple types responsive to the query; and

means for categorizing documents responsive to the query based on document type, including

means for generating a summary of the number of documents responsive to the query which fall within various predetermined categories of document types.

Additionally, although this patent deals with coordinates the drawings describe a very similar invention to Apple's patent: "Information search and retrieval with geographical coordinates" US5893093 Issue date: Apr 6, 1999

Claim 1 reads:

An information search and retrieval process using geographical coordinates, which process comprises:

building an index of coordinates for a plurality of text based references, resources or sites, each having a set of said coordinates;

accepting a user inquiry containing a text reference;

converting said text reference specified in said user inquiry to a set of coordinates;

searching against said index of coordinates based on the converted coordinates of said user inquiry reference; and

returning all information retrieved from said searching in a text based format.

The list continues: "Information retrieval system" US5978803 Issue date: Nov 2, 1999

Claim 1:

An information retrieval system, comprising:

a plurality of retrieval servers for performing retrieval processing; and

a retrieval management server for managing operation of said plurality of retrieval servers;

wherein said retrieval management server divides a text base of a retrieval object and relating information regarding the text base into a number of parts based on a size of the text base and loads of the respective retrieval servers and selectively allocates the divided parts of the text base and the relating information corresponding to the divided parts in sets to some or all of said plurality of retrieval servers; and

said plurality of retrieval servers perform information retrieval for the divided parts of the text base allocated by said retrieval management server parallelly to and independently of each other.

And, one more: "System for storage and retrieval of diverse types of information obtained from different media sources which include video, audio, and text transcripts" US5729741 Issue date: Mar 17, 1998

Claim 1 reads as follows:

A method of processing information contained in different types of media, comprising the steps of:

(a) processing each and every of said different types of media by storing in memory a first, index storage file, which contains a text description of the contents of information contained in said any medium, and an identification of said first, index storage file; and

(b) for each respective medium processed in step (a), analyzing the contents of information of said respective medium, regardless of the type of the subject matter of said contents of information, for the presence of text, and generating a second, text file, that contains all text found in said medium and storing said second, text file in memory in association with said first, index storage file; and

wherein said respective medium comprises a video recording medium containing video and voice information signals associated with a video recorded activity, and a further medium containing a separate transcription of said voice information, and

wherein step (b) comprises processing said voice information signals through an automated voice recognition-to-text conversion mechanism, so as to generate a voice-converted text file, and processing said further medium containing said separate transcription of said voice information to generate a transcribed voice text file, and correlating successive words of said voice-converted text file and successive words of said transcribed voice text file to associate contents of said transcribed voice text file with said video information.

Answer 12

Patent number: 6377965 Filing date: Nov 7, 1997

A word completion system that can automatically predict unrestricted word completions for data entries in an unstructured portion of a data file. ...

Autocomplete, as we have come to know it. Further:

Claim 15 In a computer system, a method for suggesting word completions for partial data entries within data files open in a plurality of application programs, comprising the steps of:

running a word completion utility on the computer system;

selecting a suggestion list comprising a plurality of associated name-completion pairs to

be used in connection with the word completion utility, each name-completion pair including a name entry and a completion entry;

running a first application program on the computer system;

opening a first data file in the first application program and receiving a first partial data entry into the first data file;

identifying a first name entry in the suggestion list that corresponds to the first partial data entry;

applying prediction criteria to the first partial data entry, the first name entry, and a first completion entry associated with the first name entry; and

if the prediction criteria are met, displaying the first completion entry as a word completion suggestion for the first partial data entry;

running a second application program on the computer system;

opening a second data file in the second application program and receiving a second partial data entry into the second data file;

identifying a second name entry in the suggestion list that corresponds to the second partial data entry;

applying the prediction criteria to the second partial data entry, the second name entry, and the second completion entry associated with the second name entry; and

if the prediction are met, displaying the second completion entry as a word completion suggestion for the second partial data entry.

It "searches" one or more local files. Extending the reach over a network is not a great leap of innovation.

Answer 13

Yet another auto-complete patent 6377965 Filing date: Nov 7, 1997

A word completion system that can automatically predict unrestricted word completions for data entries in an unstructured portion of a data file. The word completion system applies prediction criteria to avoid annoying the user by displaying an excessive number of wrong suggestions. Suggested word completions, which may change as the user types a partial data entry, are displayed in a non-disruptive manner and selected using traditional acceptance keystrokes, such as the "tab" key or the "enter" key. The word completion system may be deployed on an individual application program basis or on a application-independent basis. Because different word suggestion lists may be appropriate for different application programs, and for different data files created with the same application program, the word completion system allows the user to select one or more suggestion lists for use with each data file. A user interface allows the user to customize each suggestion list on an on-going basis...

Again, it does not explicitly mention "remote" or Internet files, but it seems to cover the other claims made.

Answer 14

Without repopulating this page with all of the responses, you might want to consider the responses from Groklaw readers found here: http://www.groklaw.net/article.php?story=20121018133756787#comments

Answer 15

This patent is just so broad and generic that a lot of prior implementations could be described by it. My first thought was of NFS shares. Searching for files using GNU find or locate would return results on the local hard drive and files on the network in the hierarchy of the file system. I was doing this in the late 90's when I first started using Debian and later Mandrake.

Answer 16

This is a patent on searching here and there. Don't the examiners practice this patent every day during the course of their work? Haven't they done so for years? How can they do something all day every day year after year and then issue someone a patent for inventing it? Duh!