UNIFORM RESOURCE IDENTIFIER ALIGNMENT

• US 20090240670A1
• Filed: 03/20/2008
• Published: 09/24/2009
• Est. Priority Date: 03/20/2008
• Status: Abandoned Application

• Current Assignee: Oath Inc. (Verizon Communications Inc.)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Tiyyagura, Mahesh, Poola, Krishna Leela
• Application Number:
  US12/051,956
• Publication Number:
  US 20090240670A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/00 Information retrieval; Database structures therefor; File system structures therefor

Abstract

Subject matter disclosed herein may relate to alignment of uniform resource identifiers associated with web pages, and further may relate to multiple sequence alignment of uniform resource identifiers. In one or more example embodiments, multiple sequence alignment techniques may provide improved tokenization of uniform resource identifiers associated with web pages, which may provide improved performance of applications such as, for example, uniform resource identifier normalization, sitemap construction, etc.

Claims

1. A method, comprising:

segmenting a plurality of uniform resource identifiers into one or more tokens to produce one or more sequences; and

analyzing the one or more sequences using a multiple sequence alignment process to produce a plurality of aligned sequence sets corresponding to the plurality of uniform resource identifiers.

2. The method of claim 1, wherein said multiple sequence alignment process comprises a dynamic programming technique to identify the plurality of aligned sequence sets.

3. The method of claim 1, wherein said multiple sequence alignment process comprises a progressive alignment technique.

4. The method of claim 3, wherein said progressing alignment technique comprises aligning a plurality of most similar sequences and performing a series of subsequent alignments on successively less closely related sequences.

5. The method of claim 1, wherein said multiple sequence alignment process comprises an iterative method.

6. The method of claim 1, further comprising grouping the plurality of uniform resource identifiers into one or more clusters prior to said analyzing the one or more tokens of the plurality of uniform resource locators.

7. The method of claim 6, wherein said grouping the plurality of uniform resource identifiers into one or more clusters comprises grouping the plurality of uniform resource identifiers based, at least in part, on one or more scripts associated with a web site, wherein said one or more scripts are utilized to generate one or more pages in the web site.

8. The method of claim 6, wherein said grouping the plurality of uniform resource identifiers into one or more clusters comprises grouping together one or more subsets of uniform resource identifiers, wherein each of the subsets comprises one or more uniform resource identifiers that represent pages from a web site that are essentially syntactically similar to each other.

9. The method of claim 1, further comprising normalizing the plurality of uniform resource identifiers based, at least in part, on the plurality of aligned sequence sets.

10. The method of claim 1, further comprising creating a site map of at least a portion of a web site based, at least in part, on the plurality of aligned sequence sets.

11. The method of claim 1, further comprising utilizing the plurality of aligned sequence sets in one or more of the following applications:

information retrieval, advertisement, search engines, search relevance, and/or information extraction.

12. An article, comprising:

a storage medium having stored thereon instructions that, if executed, direct a computing platform to;

segment a plurality of uniform resource identifiers into one or more tokens to produce one or more sequences; and

analyze the one or more sequences using a multiple sequence alignment process to produce a plurality of aligned sequence sets corresponding to the plurality of uniform resource identifiers.

13. The article of claim 12, wherein said storage medium has stored thereon further instructions that, if executed, direct the computing platform to perform the multiple sequence alignment process using a dynamic programming technique to identify the plurality of aligned sequence sets.

14. The article of claim 12, wherein said storage medium has stored thereon further instructions that, if executed, direct the computing platform to perform the multiple sequence alignment process using a progressive alignment technique.

15. The article of claim 14, wherein said storage medium has stored thereon further instructions that, if executed, direct the computing platform to perform said progressive alignment technique by aligning a plurality of most similar sequences and performing a series of subsequent alignments on successively less closely related sequences.

16. The article of claim 12, wherein said storage medium has stored thereon further instructions that, if executed, direct the computing platform to perform said multiple sequence alignment process using an iterative method.

17. The article of claim 12, wherein the storage medium has stored thereon further instructions that, if executed, direct the computing platform to group the plurality of uniform resource identifiers into one or more clusters prior to said analyzing the one or more tokens of the plurality of uniform resource identifiers.

18. The article of claim 17, wherein the storage medium has stored thereon further instructions that, if executed, direct the computing platform to group the plurality of uniform resource identifiers based, at least in part, on one or more scripts associated with a web site, wherein said one or more scripts are utilized to generate one or more pages in the web site.

19. The article of claim 17, wherein the storage medium has stored thereon further instructions that, if executed, direct the computing platform to group together one or more subsets of uniform resource identifiers, wherein each of the subsets comprises on or more uniform resource identifiers that represent pages from a web site that are essentially syntactically similar to each other.

20. The article of claim 12, wherein the storage medium has stored thereon further instructions that, if executed, direct the computing platform to normalize the plurality of uniform resource identifiers based, at least in part, on the plurality of aligned sequence sets.

21. The article of claim 12, wherein the storage medium has stored thereon further instructions that, if executed, direct the computing platform to create a site map of a web site based, at least in part, on the plurality of aligned sequence sets.

22. The article of claim 12, wherein the storage medium has stored thereon further instructions that, if executed, direct the computing platform to utilize the plurality of aligned sequence sets in one or more of the following applications:

information retrieval, advertisement, search engines, search relevance, and/or information extraction.

23. An apparatus, comprising:

means for segmenting a plurality of uniform resource identifiers into one or more tokens to produce one or more sequences; and

means for analyzing the one or more sequences using a multiple sequence alignment process to produce a plurality of aligned sequence sets corresponding to the plurality of uniform resource identifiers.

24. The apparatus of claim 23, wherein said multiple sequence alignment process comprises a dynamic programming technique to identify the plurality of aligned sequence sets.

25. The apparatus of claim 23, wherein said multiple sequence alignment process comprises a progressive alignment technique.

26. The apparatus of claim 25, wherein said progressive alignment technique comprises aligning a plurality of most similar sequences and performing a series of subsequent alignments on successively less closely related sequences.

27. The apparatus of claim 23, wherein said multiple sequence alignment process comprises an iterative method.

28. The apparatus of claim 23, further comprising means for grouping the plurality of uniform resource identifiers into one or more clusters prior to said analyzing the one or more tokens of the plurality of uniform resource identifiers.

29. The apparatus of claim 28, wherein said means for grouping the plurality of uniform resource identifiers into one or more clusters comprises means for grouping the plurality of uniform resource identifiers based, at least in part, on one or more scripts associated with a web site, wherein said one or more scripts are utilized to generate one or more pages in the web site.

30. The apparatus of claim 28, wherein said means for grouping the plurality of uniform resource identifiers into one or more clusters comprises means for grouping together one or more subsets of uniform resource identifiers, wherein each of the subsets comprises on or more uniform resource identifiers that represent pages from a web site that are essentially syntactically similar to each other.

31. The apparatus of claim 23, further comprising means for normalizing the plurality of uniform resource identifiers based, at least in part, on the plurality of aligned sequence sets.

32. The apparatus of claim 23, further comprising means for creating a site map of a web site based, at least in part, on the plurality of aligned sequence sets.

33. The apparatus of claim 23, further comprising means for utilizing the plurality of aligned sequence sets in one or more of the following applications:

information retrieval, advertisement, search engines, search relevance, and/or information extraction.