CIS 115

Searching & Information Retrieval

kst8r

K-State's new social network!

• What features should it have?
• What data do we need?
• How should it be stored?
• How can we retrieve it?

Relational Database

Why Normalize Data?

• Avoid data anomalies
• Make redesigning easier
• Mirror real-world concepts
• Simplify queries

Relational Database

Related Tables

Storing Phone Numbers

Many-to-One?

One-to-Many

Algorithm

INPUT: a two-word phrase of form,  "Word1 Word2"
OUTPUT: an  AnswerList,  a list of the numbers of the Web pages that
contain the phrase

ALGORITHM:
(0.  The  AnswerList  starts with nothing saved in it.)

1. Extract from the table the list of  Page#-Position#  pairs for  Word1.  Call it  List1.

2. Extract from the table the list of  Page#-Position#  pairs for  Word2.  Call it  List2.

3. For each  page#-pos#  pair in List1,
      search  List2  to see if there is a pair,  page#-(pos#+1).
        (that is, the page# is the same and pos# differs by +1)
      if yes, then include  page#  in the  AnswerList.
      if no, then ignore this pair.

4. Announce all the page numbers in  AnswerList

Nearness

• Look up "cat sat" using the list
• Look up:
  • cat stood
  • "cat stood"
  • cat OR stood
• How would that algorithm change?

Ranking

• Which page is more likely to be about dogs? Cats? How could you tell?
• How would you modify the algorithm to account for that?

AltaVista

• Early web search engine with crawler and indexer
• 1996: 5 servers, 210 GB storage & 4GB RAM on main indexer
• 1998: 20 servers, 500 GB storage & 130 GB RAM, 13 million queries daily
• Bought by Yahoo in in 2003, shut down in 2011

Page Rank Example

Image Source: Ian Rogers - Princeton

Page Rank Example

Image Source: Ian Rogers - Princeton

Problems?

• Web Spam
• Computation Time
• Non-textual Data
• Structured Data


• Others?

Source: New Tools Workshop

Assignments

• Read and be prepared to discuss:
  • 9ALG 4: Public Key Cryptography
  • Blog 6 - Due 11/14 10:00 PM
  • Wiki Draft - Due 11/11 10:00 PM

Blog 6: Computing Science & Mathematics

As we embark on reading the last textbook, it should be very obvious by now that mathematics is a core aspect of Computing Science. In fact, most Computing Science departments and disciplines have a direct foundation in the study of mathematics. Here’s a good quote summing it up from Harold Abelson: “Mathematics provides a framework for dealing precisely with notions of "what is". Computation provides a framework for dealing precisely with notions of "how to".” For this article, write about how Computing Science and Mathematics are related. (Food for thought - Read up on Theoretical Computer Science and Applied Mathematics.) Things you can talk about:

• What mathematical concepts are you most interested in? How do they relate to Computing Science?
• Which algorithms do you think are most closely tied to mathematics? Which ones only make sense when applied to a computer?
• What areas of theoretical computer science do you find most interesting? Why are those interesting to you?
• What have you read in the textbooks so far that relates closely to mathematics?
• Who are some major historical figures that are important to both mathematics and Computing Science? Why do you think they are important in both fields?