Determining query term synonyms within query context

Share
Save

Share On Facebook Share On Twitter Share By Email
Save Item
Add to
my lists

Filing Information

  • Patent Number: US7636714
  • Application Number: US11096726
  • Filing date: 03/31/2005
  • Issue date: 12/22/2009
  • Predicted expiration date: 01/25/2026
  • Patent term adjustment: 300
Explore Your Innovation Network™ for an introduction to:

Innovation Network Your First Name:
 Last Name:
  
Already a member? Sign In
  • U.S. Classifications: 707/5  · 707/2  ·
  • International Classifications: G06F1730 ·
19 Claims, 5 Drawings


Abstract

A method is applied to search terms for determining synonyms or other replacement terms used in an information retrieval system. User queries are first sorted by user identity and session. For each user query, a plurality of pseudo-queries is determined, each pseudo-query derived from a user query by replacing a phrase of the user query with a token. For each phrase, at least one candidate synonym is determined. The candidate synonym is a term that was used within a user query in place of the phrase, and in the context of a pseudo-query. The strength or quality of candidate synonyms is evaluated. Validated synonyms may be either suggested to the user or automatically added to user search strings.

References Cited

U.S. Patent Documents

Document NumberAssigneesInventorsIssue/Pub Date
US5826260 International Business Machines Corporation Byrd et al. Oct 1998
US6285999 The Board of Trustees of the Leland Stanford Junior University Page Sep 2001
US6519585* Infospace, Inc. Kohli Feb 2003
US6651054 International Business Machines Corporation de Judicibus Nov 2003
US6671711 Xerox Corporation Pirolli et al. Dec 2003
US6675159* SCIENCE APPLIC INT CORP Lin et al. Jan 2004
US6701309* Lycos, Inc. Beeferman et al. Mar 2004
US6718363 Verizon Laboratories, Inc. Ponte Apr 2004
US6732088* Xerox Corporation Glance May 2004
US6751611 Krupin et al. Jun 2004
US6829599 Xerox Corporation Chidlovskii Dec 2004
US6856957 Nuance Communications Dumoulin Feb 2005
US7031961 Google, Inc. Pitkow et al. Apr 2006
US20020002438 Ohmura et al. Jan 2002
US20030014399 Hansen et al. Jan 2003
US20030093408 Brown et al. May 2003
US20030135413 Nishi et al. Jul 2003
US20030210666 Nokia Corporation Trossen et al. Nov 2003
US20030212666 Basu et al. Nov 2003
US20030217052 Celebros Ltd. Rubenczyk et al. Nov 2003
US20040083211 Bradford Apr 2004
US20040199419* International Business Machines Corporation Kim et al. Oct 2004
US20040199498* Yahoo! Inc. Kapur et al. Oct 2004
US20050027691 Brin et al. Feb 2005
US20050044224 Jun et al. Feb 2005
US20050071337 INTERNATIONAL BUSINESS MACHINES CORPORATION Baranczyk et al. Mar 2005
US20050125215* Microsoft Corporation Wu et al. Jun 2005
US20050149499* Google Inc., A DELAWARE CORPORATION Franz et al. Jul 2005
US20050198068* Mukherjee et al. Sep 2005
US20050256848* International Business Machines Corporation Alpert et al. Nov 2005
US20060031214 Microsoft Corporation Solaro et al. Feb 2006
US20060074883 Microsoft Corporation Teevan et al. Apr 2006
US20070106937 MICROSOFT CORPORATION Cucerzan et al. May 2007
* cited by examiner

Other Publications

Jaczynski, M. et al., “Broadway: A Case-Based System for Cooperative Information Browsing on the World-Wide-Web,” INRIA Sophia-Antipolis, Action AID, 12 pages.
Cui, Hang et al., “Probabilistic Query Expansion Using Query Logs”, Proceedings of the 11th International Conference on the World Wide Web, May 7-11, 2002, Honolulu, HI, 8 pages.
U.S. Appl. No. 11/096,726, filed Mar. 30, 2005, Lamping et al.
U.S. Appl. No. 11/090,302, filed Mar. 28, 2005, Lamping et al.
U.S. Appl. No. 10/900,021, filed Jul. 26, 2004, Patterson.
U.S. Appl. No. 10/878,926, filed Jun. 28, 2004, Battle et al.
U.S. Appl. No. 10/734,584, filed Dec. 15, 2003, Bem et al.
U.S. Appl. No. 11/676,571, filed Sep. 30, 2003, Harik et al.
U.S. Appl. No. 10/668,721, filed Sep. 22, 2003, Haahr et al.
PCT International Search Report and Written Opinion, PCT/US05/10681, Oct. 18, 2006, 7 Pages.
PCT International Search Report and Written Opinion, PCT/US06/09076, Sep. 20, 2007, 8 pages.
“How the Vivisimo Clustering Engine Works”, Vivisimo, Inc., 2003, 2 pages.
Chang, D. T., “HieNet: A User-Centered Approach for Automatic Link Generation,” ACM, Hypertext '93 Proceedings, Nov. 1993, pp. 145-158.
Boyan, J.A. et al., “Learning Evaluation Functions for Global Optimization and Boolean Satisfiability,” 1998, [online] Retrieved from the Internet .

Referenced By

The current document is not referenced by other documents.

Patent Family

The current document is not in a family.

Read Patent

Read patent

Independent Claims | See all claims (19)

  1. 1. A computer-implemented method of searching for information in an information retrieval system, the computer-implemented method comprising: receiving a search query comprising a plurality of terms; selecting one of the plurality of terms, wherein unselected terms of the plurality of terms comprise remaining terms of the received search query and the selected term has a position relative to the remaining unselected terms of the received search query; selecting, for the selected term, a replacement term that appears in a plurality of previously received multi-term search queries in a same position within the previously received multi-term search queries as the position of the selected term relative to the remaining unselected terms of the received search query; deriving an altered query by replacing the selected term in the received query with a disjunction of the selected term and the replacement term; and generating a list of search results for the altered query.
  2. 11. A computer-implemented method of searching for information in an information retrieval system, the computer-implemented method comprising: receiving a search query comprising a plurality of terms; generating search results for the search query; selecting one of the plurality of terms, wherein unselected terms of the plurality of terms comprise remaining terms of the received search query and the selected term has a position relative to the remaining unselected terms of the received search query; selecting, for the selected term, a replacement term that appears in a plurality of previously received multi-term search queries in a same position within the previously received multi-term search queries of as the position of the selected term relative to the remaining unselected terms of the received search query; providing a ranking of the search results; and modifying the ranking of the search results based on whether the search results include the replacement term.
  3. 12. A computer-implemented method of searching for information in an information retrieval system, the computer-implemented method comprising: receiving a search query comprising a plurality of terms; generating a list of search results for the search query; selecting one of the plurality of terms, wherein unselected terms of the plurality of terms comprise remaining terms of the received search query and the selected term has a position relative to the remaining unselected terms of the received search query; selecting, for the selected term, a replacement term that appears in a plurality of previously received multi-term search queries in a same position within the previously received multi-term search queries as the position of the selected term relative to the remaining unselected terms of the received search query; deriving an altered query by replacing the selected term in the received query with a disjunction of the selected term and the replacement term; and generating a list of altered search results for the altered query.
  4. 13. A computer program product for searching for information in an information retrieval system, the computer program product comprising: a computer-readable storage medium; and computer program code, coded on the medium, for: receiving a search query comprising a plurality of terms; generating a list of search results for the search query; selecting one of the plurality of terms, wherein unselected terms of the plurality of terms comprise remaining terms of the received search query and the selected term has a position relative to the remaining unselected terms of the received search query; selecting, for the selected term, a replacement term that appears in a plurality of previously received multi-term search queries in a same position within the previously received multi-term search queries as the position of the selected term relative to the remaining unselected terms of the received search query; deriving an altered query by replacing the selected term in the received query with a disjunction of the selected term and the replacement term; and generating a list of altered search results for the altered query.
  5. 14. A computer program product for searching for information in an information retrieval system, the computer program product comprising: a computer-readable storage medium; and computer program code, coded on the medium, for: receiving a search query comprising a plurality of terms; selecting one of the plurality of terms, wherein unselected terms of the plurality of terms comprise remaining terms of the received search query and the selected term has a position relative to the remaining unselected terms of the received search query; selecting, for the selected term, a replacement term that appears in a plurality of previously received multi-term search queries in a same position within the previously received multi-term search queries as the position of the selected term relative to the remaining unselected terms of the received search query; deriving an altered query by replacing the selected term in the received query with a disjunction of the selected term and the replacement term; and generating a list of search results for the altered query.
  6. 15. A computer program product for determining synonyms for search query terms, the computer program product comprising: a computer-readable storage medium; and computer program code, coded on the medium, for: receiving a search query comprising a plurality of terms; generating a list of search results for the search query; selecting one of the plurality of terms, wherein unselected terms of the plurality of terms comprise remaining terms of the received search query and the selected term has a position relative to the remaining unselected terms of the received search query; selecting, for the selected term, a replacement term that appears in a plurality of previously received multi-term search queries in a same position within the previously received multi-term search queries as the position of the selected term relative to the remaining unselected terms of the received search query; providing a ranking of the search results; and modifying the ranking of the search results based on whether the search results include the replacement term.
  7. 16. A computer-implemented method of searching for information in an information retrieval system, the computer-implemented method comprising: receiving a search query comprising a plurality of terms; selecting one of the plurality of terms, wherein unselected terms of the plurality of terms comprise remaining terms of the received search query and the selected term has a position relative to the remaining unselected terms of the received search query; selecting, for the selected terms, a replacement term that appears in a plurality of previously received multi-term search queries in a same position within the previously received multi-term search queries as the position of the selected term relative to the remaining unselected terms of the received search query; deriving an altered query by replacing the selected terms in the received query with the replacement term; and generating a list of search results for the altered query.
  8. 19. A computer program product for searching for information in an information retrieval system, the computer program product comprising: a computer-readable storage medium; and computer program code, coded on the medium, for: receiving a search query comprising a plurality of terms; selecting one of the plurality of terms, wherein unselected terms of the plurality of terms comprise remaining terms of the received search query and the selected term has a position relative to the remaining unselected terms of the received search query; selecting, for the selected terms, a replacement term that appears in a plurality of previously received multi-term search queries in a same position within the previously received multi-term search queries as the position of the selected term relative to the remaining unselected terms of the received search query; deriving an altered query by replacing the selected terms in the received query with the replacement term; and generating a list of search results for the altered query.