Described is a paid search advertising technology in which advertisements associated with bidding keywords are ranked by relevance when returning one or more advertisements in a response to a query. A relevance score is computed for an advertisement based on the bidding keyword and page data (text and/or other page content) of the advertisement. The relevance score may be based on a similarity vector score computed from a keyword vector and page data vector relationship, combined with a proximity score computed from the keyword's bigram set and the page data bigram set. When a query is received, advertisements are selected based on the proximity of the query to each advertisement's bidding keyword, providing candidate scores. Each candidate score is modified (e.g., multiplied) into a final score based on its respective advertisement's relevance score. The final scores are then used to re-rank the advertisements relative to one another.