USOO8433696B2
`
`(12) United States Patent
`Venkataraman et al.
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 8.433,696 B2
`*Apr. 30, 2013
`
`(54)
`
`(75)
`
`(73)
`(*)
`
`(21)
`(22)
`(65)
`
`(63)
`
`(60)
`
`(51)
`
`(52)
`
`(58)
`
`METHOD AND SYSTEM FOR PROCESSING
`AMBIGUOUS, MULTITERM SEARCH
`QUERIES
`
`Inventors: Sashikumar Venkataraman, Andover,
`MA (US); Rakesh Barve, Bangalore
`(IN); Pankaj Garg, Patiala (IN); Pranav
`Rajanala, Bangalore (IN); Murali
`Aravamudan, Windham, NH (US); Ajit
`Rajasekharan, West Windsor, NJ (US)
`Assignee: Veved, Inc., Andover, MA (US)
`Notice:
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 25 days.
`This patent is Subject to a terminal dis
`claimer.
`
`Appl. No.: 12/869,991
`Filed:
`Aug. 27, 2010
`
`Prior Publication Data
`US 2010/0325 106A1
`Dec. 23, 2010
`
`Related U.S. Application Data
`Continuation of application No. 1 1/235,928, filed on
`Sep. 27, 2005, now Pat. No. 7,788, 266.
`Provisional application No. 60/711,866, filed on Aug.
`26, 2005, provisional application No. 60/716,101,
`filed on Sep. 12, 2005.
`
`(2006.01)
`
`Int. C.
`G06F 7700
`U.S. C.
`USPC ............ 707/706; 707/723; 707/748; 707/752
`Field of Classification Search .............. 707/6, 723,
`707/706, 748,752
`See application file for complete search history.
`
`(56)
`
`References Cited
`
`EP
`EP
`
`U.S. PATENT DOCUMENTS
`1,261,167 A
`4, 1918 Russell
`4,045,777 A
`8, 1977 Mierzwinski et al.
`(Continued)
`FOREIGN PATENT DOCUMENTS
`1050794 A2 11/2000
`1143691 A1 10, 2001
`(Continued)
`OTHER PUBLICATIONS
`Ardissono, L. et al., User Modeling and Recommendation Tech
`niques for Personalized Electronic Program Guides, Personalized
`Digital Television, Editors: Ardissono, et al., Kluwer Academic
`Press, 2004.
`
`(Continued)
`Primary Examiner — Cindy Nguyen
`(74) Attorney, Agent, or Firm — Wolf, Greenfield & Sacks,
`P.C.
`
`ABSTRACT
`(57)
`In accordance with one or more embodiments of the inven
`tion, a method and system are provided of processing a search
`query entered by a user of a device having a text input inter
`face with overloaded keys. The search query is directed at
`identifying an item from a set of items. Each of the items has
`one or more associated descriptors. The system receives from
`the user an ambiguous search query directed at identifying a
`desired item. The search query is a prefix substring of each of
`at least two words relating to the desired item. The system
`dynamically identifies a group of one or more items from the
`set of items having one or more descriptors matching the
`search query as the user enters each character of the search
`query. The system outputs identification of the one or more
`items of the identified group to be displayed on the device
`operated by the user.
`
`31 Claims, 9 Drawing Sheets
`
`
`
`
`
`AND HEL
`EVCE
`
`SERVER FAR,
`
`NEWORK
`204
`
`
`
`o REMOTE CONR
`
`E.
`
`COMPUER
`
`1
`
`Comcast, Exhibit-1205
`
`

`

`U.S. PATENT DOCUMENTS
`4,453,217 A
`6/1984 Boivie
`4,760,528 A
`7/1988 Levin
`3. A
`E. Vines
`5,337,347 A
`8, 1994 Halstead-Nussloch et al.
`5,369,605 A 11, 1994 Parks
`- W -
`5.487,616 A
`1/1996 Ichbiah
`5.532,754 A
`7/1996 Young et al.
`5,623.406 A
`4/1997 Ichbiah
`5,635,989 A
`6/1997 Rothmuller
`5,745,889. A
`4, 1998 Burrows
`5,774,588 A
`6/1998 Li
`5,802,361. A
`9, 1998 Wang et al.
`5,805,155. A
`9/1998 Allibhoy et al.
`5,818,437 A 10/1998 Grover et al.
`5,828,420 A 10, 1998 Marshall et al.
`5,828,991. A 10/1998 Skiena et al.
`3.63 A 1998 st et al. al
`5,880,768 A
`3, 1999 E. etal
`sys-w
`5,912,664 A
`6/1999 Eicket al.
`5.937,422 A
`8/1999 Nelson et al.
`5,945,928 A
`8/1999 Kushler et al.
`5.945.987. A
`8, 1999 Dunn
`5,953,541 A
`9/1999 King et al.
`6,005,565 A 12/1999 Legall et al.
`6,005,597 A 12/1999 Barrett et al.
`88. A 39. Ea et al
`601,554 A
`1, 2000 E. st al.
`W .
`.
`.
`get al.
`6,041,311 A
`3/2000 Chislenko et al.
`6,047.300 A
`4/2000 Walfish et al.
`6,075,526. A
`6/2000 Rothmuller
`6,133,909 A 1929. Shint al.
`g: R 58. ES
`1
`6.189002 B
`2/2001
`set al.
`J. V-1
`85.83 R 299; it,
`6,266.048 B
`72001 ES
`4. ww.
`au.
`6.266,814 B1
`7/2001 Lemmons et al.
`85.8 R 658: E. al
`6.292.804 B
`9/2001 SE,1
`6,307.548 B1
`10/2001 Flinchem et al.
`6.307.549 B1
`10, 2001 King et al.
`73;
`S36 R.E.
`-
`55: R
`29: test et h
`6,466.933 B1
`10/2002 syst al.
`s
`ang et al.
`6,529,903 B2
`3/2003 Smith
`E. R
`3. sal. .
`
`US 8,433,696 B2
`Page 2
`
`5/2007 Kikinis
`7,213,256 B1
`5/2007 Donaldson et al.
`7,225, 180 B2
`5/2007 Carrasco et al.
`7.225,184 B2
`5/2007 Bennington et al.
`7.225,455 B2
`9/2007 Fux et al.
`7,269,548 B2
`1
`23i R 1399, SM et al.
`I w
`amamoto et al.
`7,536,384 B2
`5/2009 Venkataraman et al.
`7,594,244 B2
`9/2009 Scholl et al.
`2002fOOO2550 A1
`1/2002 Berman
`2002fOO42791 A1
`4, 2002 Smith et al.
`2002/0052873 A1
`5/2002 Delgado et al.
`2002/005.9621 A1
`5/2002 Thomas et al.
`2002/0083448 A1
`6/2002 Johnson
`2002/0133481 A1
`9, 2002 Smith et al.
`2002fO144267 A1 10, 2002 Gutta et al.
`2002/0152190 A1 10, 2002 Biebesheimer et al.
`2002fO184373 A1 12/2002 Maes
`2002fO188488 A1 12/2002 Hinkle
`2002/0199.194 A1 12/2002 Ali
`2003/0005452 A1
`1/2003 Rodriguez
`2003/0005462 A1
`1/2003 Broadus et al.
`2003, OO11573 A1
`1/2003 Villet et al.
`2003/00 14753 A1
`1/2003 Beach et al.
`2003/0023976 A1
`1/2003 Kamen et al.
`2003/0037043 A1
`2/2003 Chang et al.
`2003/0037333 A1
`2/2003 Ghashghai et al.
`2003/0046698 A1
`3/2003 Kamen et al.
`2003/0051240 A1
`3, 2003 Schaffer et al.
`2003/0066068 A1
`4/2003 Gutta et al.
`2003/0066079 A1
`4/2003 Suga
`2003, OO84270 A1
`5.2003 Coon et al.
`2003/0103088 A1
`6/2003 Dresti et al.
`2003/0217121 A1 11/2003 Willis
`2003/0226,146 A1 12/2003 Thurston et al.
`2003,0229.900 A1 12/2003 Reisman
`2003/0237.096 A1 12/2003 Barrett et al.
`2004/0013909 A1
`1/2004 Shimizu et al.
`2004/0021691 A1
`2/2004 Dostie et al.
`2004/OO24777 A1
`2/2004 Schaffer
`2004/0046744 A1
`3/2004 Rafi et al.
`2004/0049783 A1
`3/2004 Lemmons et al.
`2004/0054520 A1
`3/2004 Dehlinger et al.
`2004/0073926 A1
`4/2004 Nakamura et al.
`2004/0078815 A1
`4/2004 Lemmons et al.
`58.858 A. 2. Syn
`CK
`2004/0083. 198 A1
`4/2004 Bradford et al.
`5/2004 Johnson
`2004/00936.16 A1
`2004/0111745 A1
`6/2004 Schein et al.
`2004/0128686 A1
`7/2004 Boyer et al.
`2004/O139091 A1
`7, 2004 Shin
`2004.0143569 A1
`7/2004 Gross et al.
`2004/0163032 A1
`8/2004 Guo et al.
`
`9, 2004 Sanders
`2004/0194141 A1
`2004/0216160 A1 10, 2004 Lemmons et al.
`2004/0220926 A1 11/2004 Lamkin et al.
`2004/0221308 Al
`11/2004 Cuttner et al.
`2004/0261021 A1 12/2004 Mittal et al.
`2005/0015366 A1
`1/2005 Carrasco et al.
`2005, 0071874 A1
`3, 2005 Elcock et al.
`2005/0086234 A1
`4/2005 Tosey
`2005/0086691 A1
`4/2005 Dudkiewicz et al.
`2005/0086692 A1
`4/2005 Dudkiewicz et al.
`2005/0174333 A1
`8/2005 Robinson et al.
`2005, 0192944 A1
`9, 2005 Finchem
`2005/0210020 A1
`9, 2005 Gunn et al.
`2005/0210383 Al
`9, 2005 Cucerzan et al.
`2005/0210402 A1
`9, 2005 Gunn et al.
`2005/0223308 A1 10, 2005 Gunn et al.
`2005/0240580 A1 10, 2005 Zamir et al.
`2005/0246311 A1 11/2005 Whelan et al.
`
`2005/0278175 A1 12/2005 Hyvonen
`2005/0283468 A1 12/2005 Kamvar et al.
`2006, OO 10477 A1
`1, 2006 Yu
`2006/0013487 A1
`1/2006 Longe et al.
`2006/0036640 A1
`2/2006 Tateno et al.
`2006, OO59044 A1
`3, 2006 Chan et al.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 1f1
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`7/2003 five yet al
`6594657 Bi
`-- I
`gig R 658, St. et al
`6615.348 B
`9/2003 Ers et al.
`wk -
`g: R 1939 in
`6.732,369 B
`5/2004 SSN al
`- 4
`6,757,906 B1
`$39. R. et al.
`25g. R
`38: Eis
`6,785,671 B1
`8/2004 E. etal
`w-
`yet al.
`52: R 1939. Rise t al.
`6839.705 B1
`1/2005 sal
`6.850,653 B3
`2.2005 Young etal
`6865,575 B1
`3/2005 SE
`6,865,746 B1
`3/2005 Herrington et al.
`6,907.273 Bi
`6/2005 Smethers
`
`3/2006 Schuetze et al.
`7,013,304 B1
`10/2006 Kerschberg et al.
`7,117.207 B1
`7,130,866 B2 10/2006 Schaffer
`7,136,854 B2 11/2006 Smith
`7,146,627 B1
`12/2006 Ismail et al.
`7,149,983 B1
`12/2006 Robertson et al.
`
`2
`
`

`

`US 8,433,696 B2
`Page 3
`
`4/2006 Istvan et al.
`2006.0075429 A1
`4/2006 Horowitz et al.
`2006/009082 A1
`4/2006 Zito et al.
`2006/0090.185 A1
`5/2006 Aravamudan et al.
`2006/0101499 A1
`5/2006 Venkataraman
`2006/0101503 A1
`5/2006 Aravamudan et al.
`2006/0101504 A1
`5, 2006 Marot et al.
`2006, O112162 A1
`6/2006 Sylthe et al.
`2006/01 17019 A1
`7, 2006 Unruh
`2006, O163337 A1
`7, 2006 Plumb
`2006.0167676 A1
`2006/0167859 A1* 7/2006 Verbeck Sibley et al. ........ 707/3
`2006/0173818 A1
`8, 2006 Berstis et al.
`2006, O1903O8 A1
`8/2006 Janssens et al.
`2006, O195435 A1
`8/2006 Laird-McConnell et al.
`2006/0206454 A1
`9, 2006 Forstall et al.
`2006/0242178 A1
`10, 2006 Butterfield et al.
`2006/0256O78 A1
`11/2006 Flinchem et al.
`2006, O259344 A1
`11/2006 Patel et al.
`12/2006 Longe et al.
`2006/0274051 A1
`2006/0282856 A1
`12/2006 Errico et al.
`1/2007 Whitney et al.
`2007,0005526 A1
`2007,0005563 A1
`1/2007 Aravamudan
`1/2007 Hoffberg et al.
`2007, OO16476 A1
`2007/0027852 A1
`2/2007 Howard et al.
`2007/0027861 A1
`2/2007 Huentelman et al.
`2007/0044122 A1
`2/2007 Scholl et al.
`2007/0050337 A1
`3/2007 Venkataraman et al.
`2007/0050348 A1
`3/2007 Aharoni et al.
`2007/0061244 A1
`3/2007 Ramer et al.
`2007/0061317 A1
`3/2007 Ramer et al.
`2007/0061321 A1
`3/2007 Venkataraman
`2007, OO61754 A1
`3/2007 Ardhanari et al.
`3/2007 Flynt et al.
`2007, OO67272 A1
`2007/0088681 A1
`4/2007 Aravamudan et al.
`2007/01OO650 A1
`5, 2007 Ramer et al.
`6/2007 Garg et al.
`2007. O13.0128 A1
`2007. O143567 A1
`6, 2007 Gorobets
`2007. O150606 A1
`6, 2007 Flinchem et al.
`2007/02O8718 A1
`9, 2007 Javid et al.
`2007/0219984 A1
`9/2007 Aravamudan et al.
`2007/0219985 A1
`9/2007 Aravamudan et al.
`11/2007 Ramaswamy et al.
`2007/0255693 A1
`1 1/2007 Bykov et al.
`2007/0256O70 A1
`2007/026O703 A1
`11/2007 Ardhanari et al.
`2007,0266021 A1
`11/2007 Aravamudan et al.
`2007,0266026 A1
`11/2007 Aravamudan et al.
`2007,0266406 A1
`11/2007 Aravamudan et al.
`2007/0271205 A1
`11/2007 Aravamudan et al.
`2007/0276773 A1
`11/2007 Aravamudan et al.
`2007/0276821 A1
`11/2007 Aravamudan et al.
`2007/0276859 A1
`11/2007 Aravamudan et al.
`2007/0288456 A1
`12/2007 Aravamudan et al.
`2007/02884.57 A1
`12/2007 Aravamudan et al.
`2008/0086704 A1
`4/2008 Aravamudan
`2008.0114743 A1
`5/2008 Venkataraman et al.
`2008/0209229 A1
`8/2008 Ramakrishnan et al.
`
`FOREIGN PATENT DOCUMENTS
`1338967 A2
`8, 2003
`EP
`1463307 A2
`9, 2004
`EP
`WOOOf70505 A1 11, 2000
`WO
`WO WO 2004/O10326 A1
`1, 2004
`WO WO 2004/03.1931 A1
`4/2004
`WO WO 2005/033967 A2
`4/2005
`WO WO 2005/084.235 A2
`9, 2005
`
`OTHER PUBLICATIONS
`Dalianis, Improving Search Engine Retrieval Using a Compound
`Splitter for Swedish, Abstract of Presentation at NODALIDA 2005–
`15th Nordic Conference on Computational Linguistics, Joensuu Fin
`land, May 21-22, 2005. Retrieved Jan. 5, 2006 from http://phon.
`joensuu.fi/nodalida/abstract/03.shtml.
`Digital Video Broadcasting, http://www.dvb.org (Oct. 12, 2007).
`Flinchem, E., U.S. Appl. No. 60/548,589, filed Sep. 1, 2005.
`Gadd, T.N., Phonix: The Algorithm, Program 24(4), Oct. 1990, pp.
`363-369.
`
`Good, N. et al., Combining Collaborative Filtering with Personal
`Agents for Better Recommendations, in Proc. of the 16th National
`Conference on Artificial Intelligence, pp. 439-446, Orlando, Florida,
`Jul. 18-22, 1999.
`International Search Report, International Application No. PCT/
`US06/25249, mailed Jan. 29, 2008 (2 pages).
`International Search Report, International Application No. PCT/
`US06/33204, mailed Sep. 21, 2007 (2 pages).
`International Search Report, International Application No. PCT/
`US06/33257, mailed Mar. 26, 2008 (2 pages).
`International Search Report, International Application No. PCT/
`US06/33258, mailed Mar. 26, 2008 (2 pages).
`International Search Report, International Application No. PCT/
`US06/40005, mailed Jul. 3, 2007 (4 pages).
`International Search Report, International Application No. PCT/
`US07/65703, mailed Jan. 25, 2008 (2 pages).
`International Search Report, International Application No. PCT/
`US07/67100, mailed Mar. 7, 2008 (2 pages).
`Kurapati, et al., “A Multi-Agent TV Recommender.” In Proceedings
`of the UM 2001 Workshop “Personalization in Future TV.” 2001, 8
`pageS.
`Mackenzie et al., Letterwise: Prefix-Based Disambiguation for
`Mobile Text Input, Proceedings of the ACM Symposium on User
`Interface Software and Technology UIST 2001, pp. 111-120.
`Matthom, “Text Highlighting in Search Results”, Jul. 22, 2005.
`Available at www.matthom.com/archive/2005/07/22/text-highlight
`ing-in-search-results- ; retrieved Jun. 23, 2006. (4 pages).
`Mokotoff, Soundexing and Geneaology, Available at http://www.
`avotaynu.com/soundex.html, retrieved Mar. 19, 2008, last updated
`Sep. 8, 2007 (6 pages).
`Nardi, et al., “Integrating Communications and Information Through
`Contact Map.” Communications of the ACM, vol. 45, No. 4, Apr.
`2002, 7 pages, retrieved from URL:http://portal.acm.org/citation.
`cfm?id-505251).
`Press Release From TEGIC Communications, TEGIC Communica
`tions is Awarded Patent for Japanese T9(R) TextInputSoftware From
`the Japan Patent Office, Oct. 12, 2004. Retrieved Nov. 18, 2005 From
`http://www.tegic.com/press. Sub.--view.html?release. Sub.--
`num=55254242.
`Review of Personalization Technologies: Collaborative Filtering vs.
`ChoiceStream's Attributized Bayesian Choice Modeling, Technol
`ogy Brief, ChoiceStream Technologies, Cambridge, MA.
`Roe, David et al., “Mapping UML Models Incorporating OCL Con
`straints into Object-Z”, Technical Report, Sep. 2003, Department of
`Computing Imperial College London (17 pages).
`Silfverberg et al., Predicting Text Entry Speed on Mobile Phones,
`Proceedings of the ACM Conference on Human Factors in Comput
`ing Systems—CHI 2000. pp. 9-16.
`Supplemental European Search Report for 05826114.0 dated Aug.
`20, 2009, 13 pages.
`Supplemental European Search Report for 05826129.8 dated Aug.
`11, 2009, 15 pages.
`Supplemental European Search Report for 068381797.7 dated Dec.
`9, 2009, 7 pages.
`Supplemental European Search Report for 07761026.9 dated Jan. 28,
`2010, 8 pages.
`Supplemental European Search Report for PCT/US2005/040415
`dated Aug. 11, 2009, 15 pages.
`Supplemental European Search Report for PCT/US2005/040424
`dated Aug. 20, 2009, 13 pages.
`Talbot, David. “Soul of a New Mobile Machine.” Technology
`Review: The Design Issue May/Jun. 2007. (pp. 46-53).
`Turski, et al., “Inner Circl—People Centered Email Client.” CHI
`2005 Conference on Human Factors in Computing Systems, Apr.
`2005, pp. 1845-1848, 4 pages, retrieved from URL:http://portal.acm.
`org/citation.cfm?id--1056808. 1057037.
`Wikipedia's entry for Levenshtein distance (n.d.). Retrieved Nov. 15,
`2006 from http://en.wikipedia.org/wiki/Levenshtein. Sub.--distance.
`Written Opinion of the International Searching Authority, Interna
`tional Application No. PCT/US06/25249, mailed Jan. 29, 2008.
`Written Opinion of the International Searching Authority, Interna
`tional Application No. PCT/US06/33204, mailed Sep. 21, 2007 (3
`pages).
`
`3
`
`

`

`US 8,433,696 B2
`Page 4
`
`Written Opinion of the International Searching Authority, Interna
`tional Application No. PCT/US06/33257, mailed Mar. 26, 2008 (4
`pages).
`Written Opinion of the International Searching Authority, Interna
`tional Application No. PCT/US06/33258, mailed Mar. 26, 2008 (4
`pages).
`Written Opinion of the International Searching Authority, Interna
`tional Application No. PCT/US06/40005, mailed Jul. 3, 2007 (4
`pages).
`Written Opinion of the International Searching Authority, Interna
`tional Application No. PCT/US07/65703, mailed Jan. 25, 2008 (4
`pages).
`Written Opinion of the International Searching Authority, Interna
`tional Application No. PCT/US07/67100, mailed Mar. 7, 2008 (3
`pages).
`
`Complaint in Veveo, Inc. v. Verizon Services Corp., Verizon Commu
`nications Inc., and Verizon Data Services India Pvt. Ltd., U.S. Dis
`trict Court Southern District of New York, Civil Action No. 10-CIV
`6709 (JFK), filed Sep. 9, 2010, pp. 1-14.
`First Amended Complain in Veveo, Inc. v. Verizon Services Corp.,
`Verizon Communications Inc., and Verizon Data Services LLC, U.S.
`District Court Southern District of New York, Civil Action No.
`10-CIV-6709 (JFK), filed Nov. 16, 2010, 16 pages.
`Verizon's Answer to First Amended Complain and Counterclaims in
`Veveo, Inc. v. Verizon Services Corp., Verizon Communications Inc.,
`and Verizon Data Services LLC, U.S. District Court Southern District
`of New York, Civil Action No. 10-CIV-6709 (JFK), filed Dec. 9,
`2010, pp. 1-17.
`* cited by examiner
`
`4
`
`

`

`U.S. Patent
`
`Apr. 30, 2013
`
`Sheet 1 of 9
`
`US 8,433,696 B2
`
`
`
`CLEAR
`
`F.G. 1
`RORAR
`
`5
`
`

`

`U.S. Patent
`
`Apr. 30, 2013
`
`Sheet 2 of 9
`
`US 8,433,696 B2
`
`HHOMLAN
`
`y0E
`
`MaLLNdWIOD
`
`6Old
`
`
`
`QUISHCNVH
`
`SOAR
`
`6
`
`
`
`

`

`U.S. Patent
`
`Apr. 30, 2013
`
`Sheet 3 of 9
`
`US 8,433,696 B2
`
`SUDWIOA POE
`HOSSs00dd
`
`AWOWSN
`
`90¢
`
`ATSIC
`
`ole
`
`ANSLSiSdad
`:ALOWSe
`
`ADVHOLS
`|ALIALLOSNNOS
`
`
`
`LAGNILXSt
`
`OF
`
`eOld
`
`7
`
`

`

`U.S. Patent
`
`Apr. 30, 2013
`
`Sheet 4 of 9
`
`US 8,433,696 B2
`
`USER ENTERS CHARACTER(S)
`WSNG &YRESS OR
`AC CARACER
`
`
`
`
`
`
`
`SAY RESS WAC.NG
`QRY
`404
`
`
`
`
`
`1 USER FOUNDN
`NO
`< DESERED RESULTS >
`N
`46
`
`
`
`8
`
`

`

`U.S. Patent
`
`Apr. 30, 2013
`
`Sheet 5 of 9
`
`US 8,433,696 B2
`
`OON: CARTOON
`TOM HANKS
`TOMMY BOY
`
`TOONS
`
`-E86
`
`e--- - G8666
`TOMMY2 --
`
`
`
`rock 86669
`
`9
`
`

`

`U.S. Patent
`U.S. Patent
`
`Apr. 30, 2013
`
`Sheet 6 of 9
`
`US 8,433,696 B2
`US 8,433,696 B2
`
`
`
`AdanXidaddWSLFILINN
`
`c0S
`
`
`WOL-
`
`CHOMATYYONYSIAWNHOLOYGe)
`
`CTIVEASTIOA
`
`
`
`idtadWHILWILLINW
`
`“330ASHOA}JOAO}
`
`SOD-SINWNSIAOW‘6'e)
`{AZWHOFaLSNWW
`
`
`
`
`
`XidceidWeIcLLDINA
`
`"918210OB‘nuiob
`
`909
`
`¥09
`
`9Ola
`
`10
`
`10
`
`
`

`

`U.S. Patent
`U.S. Patent
`
`Apr. 30, 2013
`Apr. 30, 2013
`
`Sheet 7 Of 9
`Sheet 7 of 9
`
`US 8,433,696 B2
`US 8,433,696 B2
`
`
`
`EEE
`
`11
`
`11
`
`

`

`U.S. Patent
`
`Apr. 30, 2013
`
`Sheet 8 of 9
`
`US 8,433,696 B2
`
`802
`
`he Koaia 3 otherS. Aichie's Cose oot
`
`'e
`
`The Koala Brothers: George's Day Off; Archie
`
`The Koala Brothers: Alice Rides Again, Ned
`
`Charlie and loia: 'm Not Feeling Wei
`
`Rockos viodern life: unk Junkies, Day of the
`
`Rockos Modern life: Born to Spawn; uniforn
`Charlie and oia: it's My Book
`
`INPUTTERM: 5 (J)
`FG. 8A
`
`
`
`
`
`
`
`804.
`
`he Koaia Brothers: Archie's loose ooth, Pe
`
`The Koaia Brothers: George's Day Off; Archie
`
`Rockos viodern life. Born to Spawn, Uniform
`
`he New Advertures of Wire the OO
`
`e
`
`Charlie and loia: My Wobby Tooth
`
`Charlie and Cia: he ViOS joineffiest Pic
`
`izzie McGuire: Educating Ethan
`
`INPUTTERM 586 (JTO)
`FG. 8B
`
`
`
`
`
`
`
`
`
`
`
`12
`
`

`

`U.S. Patent
`
`Apr. 30, 2013
`
`Sheet 9 Of 9
`
`US 8,433,696 B2
`
`age
`Tom and Jerry Kids: Circus Antics, res. Sheil
`
`on and Jerry Kids: No Biz likeSnow Biz, via
`
`on and Jerry Kids: Cleocatra, Me Wolferste
`
`on and Jerry Kids: Zorrito, Deep Seep Droo
`
`Tom and Jerry Kids: Who Are You Kitten?: B
`
`on and Jerry Kids: Catch That Mouse, Good
`
`on and Jerry Kids. Father's Day, Scourge of
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`INPUTTERM: 5866 (JTOM)
`
`F.G. 8C
`
`13
`
`

`

`US 8,433,696 B2
`
`1.
`METHOD AND SYSTEM FOR PROCESSING
`AMBIGUOUS, MULTITERM SEARCH
`QUERIES
`
`2
`disambiguates each word by performing a word completion
`action to resolve that word before proceeding to the next word
`in the composition.
`
`RELATED APPLICATIONS
`
`BRIEF SUMMARY OF EMBODIMENTS OF THE
`INVENTION
`
`This application is a continuation of U.S. patent applica
`tion Ser. No. 1 1/235,928, entitled Method And System For
`Processing Ambiguous, Multi-Term Search Queries, filed
`Sep. 27, 2005, now U.S. Pat. No. 7,788.266, which claims the
`benefit under 35 U.S.C. S 119(e) of U.S. Provisional Patent
`Application Ser. No. 60/716,101, filed Sep. 12, 2005, and
`entitled Method And System For Incremental Search With
`Reduced Text Entry Using A Reduced Keypad With Over
`loaded Keys, and U.S. patent application No. 60/711,866,
`filed Aug. 26, 2005, and entitled A Dynamic Highlighting
`Interface of Multi Word Prefixes of Results Obtained by
`Incremental Search with Reduced Text Entry on Television
`and Mobile Devices Using a Keypad with Overloaded Keys:
`U.S. Pat. No. 7,788.266 and U.S. Provisional Patent Appli
`cation Ser. No. 60/716,101 are incorporated by reference
`herein in their entirety.
`
`10
`
`15
`
`BACKGROUND OF THE INVENTION
`
`25
`
`1. Field of Invention
`The present invention generally relates to processing
`search queries and, more particularly, to methods and systems
`for processing ambiguous, reduced text, multi-term search
`queries.
`2. Description of Related Art
`There are many user-operated devices such as mobile
`phones, PDAs (personal digital assistants), and television
`remote control devices that have Small keypads, which a user
`can use for text entry. In many of these devices, largely
`because of device size restrictions, the keypad is Small and
`has only a small number of keys, which are overloaded with
`alpha-numeric characters. Text input using these keypads is
`cumbersome.
`FIG. 1 illustrates a common twelve-key keypad interface
`found in many cellphones and other mobile devices, and also
`increasingly in television remote control devices. The keypad
`10 includes twelve keys 12, most of which are overloaded
`with multiple alpha-numeric characters or functions. The
`same key can be used to enter different characters. For
`instance, the “2 key can be used to enter the number 2 and
`the letters “A”, “B” and “C”. Text entry using such a keypad
`with overloaded keys can result in an ambiguous text entry,
`which requires some type of a disambiguation action. For
`instance, with a multi-press interface, a user can press a
`particular key multiple times in quick Succession to select a
`desired character (e.g., to choose “B”, the user would press
`the “2 key twice quickly, and to choose “C”, the user would
`press the key three times). Alternatively, text entry can be
`performed using T9 and other text input mechanisms that
`provide vocabulary based completion choices for each word
`entered. Neither of these methods is however particularly
`useful for performing searches because of the number of steps
`needed to get to the result. One deficiency of the multi-press
`interface is that too many key strokes are needed. A drawback
`of applying a vocabulary based word completion interface is
`the need for the additional step of making a choice from a list
`of all possible word matches generated by the ambiguous text
`input. Furthermore vocabulary based word disambiguation
`systems are designed typically for composition applications
`(as opposed to search applications) where user explicitly
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`In accordance with one or more embodiments of the inven
`tion, a method and system are provided of processing a search
`query entered by a user of a device having a text input inter
`face with overloaded keys. The search query is directed at
`identifying an item from a set of items. Each of the items has
`one or more associated descriptors. The system receives from
`the user an ambiguous search query directed at identifying a
`desired item. The search query comprises a prefix substring of
`each of at least two words relating to the desired item. The
`system dynamically identifies a group of one or more items
`from the set of items having one or more descriptors matching
`the search query as the user enters each character of the search
`query. The system outputs identification of the one or more
`items of the identified group to be displayed on the device
`operated by the user.
`These and other features will become readily apparent
`from the following detailed description wherein embodi
`ments of the invention are shown and described by way of
`illustration. As will be realized, the invention is capable of
`other and different embodiments and its several details may
`be capable of modifications in various respects, all without
`departing from the invention. Accordingly, the drawings and
`description are to be regarded as illustrative in nature and not
`in a restrictive or limiting sense with the scope of the appli
`cation being indicated in the claims.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`For a more complete understanding of various embodi
`ments of the present invention, reference is now made to the
`following descriptions taken in connection with the accom
`panying drawings in which:
`FIG. 1 illustrates a keypad with overloaded keys in accor
`dance with the prior art.
`FIG. 2 illustrates a search system in accordance with one or
`more embodiments of the invention.
`FIG.3 illustrates various device configuration options for a
`device for performing searches in accordance with one or
`more embodiments of the invention.
`FIG. 4 is a flow chart illustrating a method for finding
`results with reduced text entry using an overloaded keypad in
`accordance with one or more embodiments of the invention.
`FIG. 5 illustrates a many-to-many mapping of terms to the
`numeric equivalents.
`FIG. 6 illustrates the two different couplings between mul
`tiple terms in a query.
`FIG. 7 illustrates a data structure for retrieving results
`incrementally for each character input using the many-to
`many mapping scheme in accordance with one or more
`embodiments of the invention.
`FIGS. 8A to 8C illustrate the incremental results retrieved
`when a user enters characters in a search query in accordance
`with one or more embodiments of the invention.
`Like reference numerals generally refer to like elements in
`the drawings.
`
`DETAILED DESCRIPTION OF EMBODIMENTS
`OF THE INVENTION
`
`Briefly, methods and systems are provided in accordance
`with various embodiments of the invention for performing
`searches using ambiguous text input from devices having
`limited text input interfaces.
`
`14
`
`

`

`US 8,433,696 B2
`
`10
`
`15
`
`25
`
`30
`
`35
`
`3
`As described in further detail below, in accordance with
`various embodiments of the invention, methods and systems
`are provided for processing a search query entered by a user
`of a device having a text input interface with overloaded keys.
`The search query is directed at identifying an item from a set
`of items. Each of the items has one or more associated
`descriptors. The descriptors can include words in the name of
`the item or other information relating to the item. For
`example, in a television application, the item can be a televi
`sion content item such as a movie, and the descriptors can be
`information on the title of the movie, the cast, directors, and
`other keywords and descriptions of the movie.
`Using the text input interface, the user can enteran ambigu
`ous search query directed at identifying a desired item. The
`search query comprises a prefix Substring of each of at least
`two words relating to the desired item. A prefix substring of a
`word is a variable length string of characters that contains
`fewer than all the characters making up the word.
`The system dynamically identifies a group of one or more
`items from the set of items having one or more descriptors
`matching the search query as the user enters each character of
`the search query. The group of the one or more items is
`displayed on the device operated by the user. The items are
`preferably displayed in an order of expected interest to the
`USC.
`The user types in the multiple term prefix input query by
`pressing overloaded keys of the text input interface once to
`form an ambiguous query string. In accordance with one or
`more embodiments of the invention, the search space is ini
`tially indexed by performing a many-to-many mapping from
`the alphanumeric space of terms to numeric Strings corre
`sponding to the various prefixes of each alphanumeric term
`constituting the query string. In a numeric string, each alpha
`numeric character in the string is replaced by its correspond
`ing numeric equivalent based on, e.g., the arrangement of
`characters on the commonly used twelve-key reduced keypad
`shown in FIG.1. This mapping scheme enables the system in
`accordance with one or more embodiments to incrementally
`retrieve results matching the ambiguous alphanumeric input
`query, as the user types in each character of the query. The
`40
`user does not have to explicitly specify the termination of
`each term to assist the system in disambiguating the input
`query; instead, the user only enters an input query that
`includes prefix Substrings from multiple terms. The system
`can leverage off the multiple term prefixes to disambiguate it.
`The multiple term prefix based disambiguation method in
`accordance with one or more embodiments of the invention
`reduces the amount of text and steps needed to enter a mul
`tiple term input query and retrieve results.
`There are various possible applications for the search tech
`niques described herein including, e.g., assisting television
`viewers in identifying desired television content items and
`channels, and assisting users of mobile devices Such as cell
`phones and PDAS in performing searches for items in various
`databases (e.g., performing searches in directories of people
`or businesses, and searching for and purchasing products/
`services like airline tickets).
`In the context of television systems, the term “television
`content items’ can include a wide variety of video/audio
`content including, but not limited to, television shows, mov
`60
`ies, music videos, or any other identifiable content that can be
`selected by a television viewer. Searching for television con
`tent items can be performed across disparate content sources
`including, but not limited to, broadcast television, VOD,
`IPTV, and PVR (local and network).
`FIG. 2 schematically illustrates an overall system for per
`forming searches with reduced text entry using various
`
`50
`
`45
`
`55
`
`65
`
`4
`devices in accordance with one or more embodiments of the
`invention. The system includes a server farm or system 202, a
`network 204, and a variety of devices 206, 208,210 operated
`by users with text input interfaces. In accordance with one or
`more embodiments of the invention, the server 202 processes
`search queries received from the user devices 206, 208, 210.
`In other embodiments, the search queries are processed on the
`devices themselves. As discussed below, the server 202 can be
`the source of search data and relevance updates. If part of a
`television system, the server 202 can also be the source of or
`be linked to a source of at least some of the available televi
`sion content (e.g., a cable or satellite television operator).
`The network 204 functions as the distribution framework
`for transmitting data from the server 202 to the devices oper
`ated by the users. The distribution network 204 could be
`wired or wireless connections or some combination thereof.
`Examples of possible networks include computer networks,
`cable television networks, satellite television networks, IP
`based television networks, and mobile communications net
`works (such as, e.g., wireless CDMA and GSM networks).
`The search devices could have a wide range of interface
`capabilities. A device, e.g., could be a hand-held mobile com
`munications device 206 such as a phone or PDA having a
`limited display size and a reduced keypad with overloaded
`keys. Another type of search device is a television system 207
`with a remote control device 208 having an overloaded key
`pad. Another possible search device is a Personal Computer
`(PC) 210 with a full or reduced keyboard and a computer
`display.
`FIG. 3 illustrates multiple exemplary configurations for
`search devices in accordance with various embodiments of
`the invention. In one configuration, a search device (e.g., PC
`210) can have a display 302, a processor 304, volatile memory
`306, text input interface 308, remote connectivity 310 to the
`server 202 through the network 204, and a persistent storage
`312. A device configuration for a device such as the hand-held
`device 206 might not include local persistent storage 312. In
`this case, the device 206 could have remote connectivity 310
`to submit the query to the server 202 and retrieve results from
`it. Another configuration of the devices 206, 208,210 may not
`have remote connectivity 310. In this case, the search data
`base may be locally resident on a local persistent storage 312.
`The persistent storage 312 may be, e.g., a removable storage
`element such as SD. SmartMedia, CompactFlash card etc. In
`a configuration of the device with remote connectivity 310
`and persistent storage 312 for performing searches (e.g., a
`television system 207), the device may use the remote con
`nectivity for search relevance data update or for the case
`where the search database is distributed on the local storage
`312 and on the server 202. A preferred configurati