IR-Tree: An Efficient Index for Geographic Document Search

[attachment=18437]

INTRODUCTION
THE World Wide Web (WWW) has become the most
popular and ubiquitous information media. According
to wikipedia, there are 25 billion indexable webpages and
over 100 million websites recorded in 2009, and these
numbers continue to grow. Due to the massive number of
webpages, search engines that search and rank documents
based on their relevances to user queries become essential
for information seeking. Search engines are required to
determine relevant webpages within a short latency. In
other words, high search efficiency is one of the key design
and implementation objectives of search engines. Thus,
efficient indexing techniques that organize webpages
according to their contents are demanded.


PRELIMINARIES
In this section, we first define both geographic document
search and geographic document ranking based on textual
relevance and spatial relevance. Then, we discuss the
measurements of textual relevances and spatial relevances,
and review existing works proposed for geographic
search engines.

2.1 Geographic Document Search and Ranking
We assume each document d in a given document set D is
composed of a set of words Wd, and is associated with a
location Ld. Given a query q that specifies a set of query
keywords Wq and a query spatial scope Sq, the textual
relevance and spatial relevance of a document d to q are
formalized in Definitions 1 and 2, respectively.


2.2 Document Relevance Measurement
The accurate estimation of the relevance between documents
and user queries is critical to the perceived quality
and performance of search engines. Specific to geographic
search engines, we study some existing weighting functions
for estimating textual relevance and spatial relevance.


2.3.3 Geographic Search Engine
Currently, two types of approaches are used by existing
geographic search engines, namely, Approach I that uses
separated indexes for spatial information and textual
information, and Approach II that uses a combined index
[12], [15], [18], [22], [26]. However, they both are not efficient.
Approach I logically extends conventional textual search
engines with spatial filtering capability of Quad-tree, R-tree,
and Grid index as suggested in [5], [18], [22], respectively.
As an example, in [5], the most recent work of Approach I,
an inverted file is created to index words of documents and
a grid index is created to index locations of documents.
Based on two indexes, a search generally follows a threestep
process.
. Step 1: retrieving textually relevant documents with
respect to query keywords via a conventional textual
index.
. Step 2: filtering out the documents obtained from
Step 1 that are not covered by the query spatial
scope.
. Step 3: ranking the documents from Step 2 based on
the joint textual and spatial relevances in order to
return the ranked results to the user.
We use the running example (i.e., Example 1) to illustrate
the above three-step process. First, Step 1 retrieves all
documents textually relevant to query keywords and
ignores those textually irrelevant documents (i.e., d1). As
Alice is only interested in the query spatial scope “Boston,”
documents outside the scope are discarded in Step 2, i.e.,
d7; d8; d9, and d10. Finally, in Step 3, the remaining
documents are ranked according to their TF-IDF scores as
listed in Table 1; and the top-3 documents (i.e., d6; d3, and
d5) are returned.