 |
Visualizing
Internet Queries
Using Ant-based Heuristics
Locating
information in large unstructured document collections, such as
the World Wide Web, is a task of increasing practical relevance.
Unfortunately, it is also rapidly becoming more difficult: the web,
already estimated at 3 billion documents, grows at a daily rate
of more than 7 million pages. Information retrieval research backs
the common experience that the conventional ranked hit lists are
insufficient for efficient web search. We have devised an novel
search interface that uses topographic maps as a metaphor to visualize
web query results. Topic-maps allow the concrete visualization of
the high-dimensional abstract semantic space that is spanned by
the retrieved documents. Semantically similar documents appear in
spatial proximity, whereas unrelated documents are clearly separated.
While the general idea of a map metaphor is not completely new,
we use a refined type of topic-map which uses clustering in addition
to multi-dimensional scaling and we demonstrate its superiority
over previous methods. Documents are clustered around central topics
represented by mountains in the landscape, in which the "height"
of a document corresponds to its relevance for the topic. As such
contents-based clustering allows the viewer to focus attention more
readily, the resulting maps make the analysis of query results comparatively
easy through a familiar and appealing visualization.
Generating
topic-maps is a computationally hard optimisation task, for which
we present a novel stochastic meta-heuristic based on heuristics
inspired by the behaviour of ants. Sorting and clustering methods
are among the earliest methods in Ant-based Meta-Heuristics. We
have refined these methods in the context of this application
and introduce some modifications that yield significant improvements
in terms of both quality and efficiency.
The improved algorithms are used as the core mechanism in the visual
document retrieval system for world-wide web searches which classifies
contents-similarity of documents on the fly.
Core Reference
"Improved Ant-based Clustering and Sorting in a Document
Retrieval Interface". Julia Handl and Bernd Meyer. In:
Parallel Problem Solving Nature (PPSN-VII), Granada, Spain, September
2002. pp. 913-923.
Student
Julia Handl
Supervisor
Bernd
Meyer
Type
Bachelor Computer Science (Honours)
Project Start
February 2001
Completion
November 2001
|
|
|
Click
to print
